tokenizer.py 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564
  1. # Copyright (C) 2003-2007, 2009-2011 Nominum, Inc.
  2. #
  3. # Permission to use, copy, modify, and distribute this software and its
  4. # documentation for any purpose with or without fee is hereby granted,
  5. # provided that the above copyright notice and this permission notice
  6. # appear in all copies.
  7. #
  8. # THE SOFTWARE IS PROVIDED "AS IS" AND NOMINUM DISCLAIMS ALL WARRANTIES
  9. # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10. # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL NOMINUM BE LIABLE FOR
  11. # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12. # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13. # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  14. # OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15. """Tokenize DNS master file format"""
  16. from io import StringIO
  17. import sys
  18. import dns.exception
  19. import dns.name
  20. import dns.ttl
  21. from ._compat import long, text_type, binary_type
  22. _DELIMITERS = {
  23. ' ': True,
  24. '\t': True,
  25. '\n': True,
  26. ';': True,
  27. '(': True,
  28. ')': True,
  29. '"': True}
  30. _QUOTING_DELIMITERS = {'"': True}
  31. EOF = 0
  32. EOL = 1
  33. WHITESPACE = 2
  34. IDENTIFIER = 3
  35. QUOTED_STRING = 4
  36. COMMENT = 5
  37. DELIMITER = 6
  38. class UngetBufferFull(dns.exception.DNSException):
  39. """An attempt was made to unget a token when the unget buffer was full."""
  40. class Token(object):
  41. """A DNS master file format token.
  42. @ivar ttype: The token type
  43. @type ttype: int
  44. @ivar value: The token value
  45. @type value: string
  46. @ivar has_escape: Does the token value contain escapes?
  47. @type has_escape: bool
  48. """
  49. def __init__(self, ttype, value='', has_escape=False):
  50. """Initialize a token instance.
  51. @param ttype: The token type
  52. @type ttype: int
  53. @param value: The token value
  54. @type value: string
  55. @param has_escape: Does the token value contain escapes?
  56. @type has_escape: bool
  57. """
  58. self.ttype = ttype
  59. self.value = value
  60. self.has_escape = has_escape
  61. def is_eof(self):
  62. return self.ttype == EOF
  63. def is_eol(self):
  64. return self.ttype == EOL
  65. def is_whitespace(self):
  66. return self.ttype == WHITESPACE
  67. def is_identifier(self):
  68. return self.ttype == IDENTIFIER
  69. def is_quoted_string(self):
  70. return self.ttype == QUOTED_STRING
  71. def is_comment(self):
  72. return self.ttype == COMMENT
  73. def is_delimiter(self):
  74. return self.ttype == DELIMITER
  75. def is_eol_or_eof(self):
  76. return self.ttype == EOL or self.ttype == EOF
  77. def __eq__(self, other):
  78. if not isinstance(other, Token):
  79. return False
  80. return (self.ttype == other.ttype and
  81. self.value == other.value)
  82. def __ne__(self, other):
  83. if not isinstance(other, Token):
  84. return True
  85. return (self.ttype != other.ttype or
  86. self.value != other.value)
  87. def __str__(self):
  88. return '%d "%s"' % (self.ttype, self.value)
  89. def unescape(self):
  90. if not self.has_escape:
  91. return self
  92. unescaped = ''
  93. l = len(self.value)
  94. i = 0
  95. while i < l:
  96. c = self.value[i]
  97. i += 1
  98. if c == '\\':
  99. if i >= l:
  100. raise dns.exception.UnexpectedEnd
  101. c = self.value[i]
  102. i += 1
  103. if c.isdigit():
  104. if i >= l:
  105. raise dns.exception.UnexpectedEnd
  106. c2 = self.value[i]
  107. i += 1
  108. if i >= l:
  109. raise dns.exception.UnexpectedEnd
  110. c3 = self.value[i]
  111. i += 1
  112. if not (c2.isdigit() and c3.isdigit()):
  113. raise dns.exception.SyntaxError
  114. c = chr(int(c) * 100 + int(c2) * 10 + int(c3))
  115. unescaped += c
  116. return Token(self.ttype, unescaped)
  117. # compatibility for old-style tuple tokens
  118. def __len__(self):
  119. return 2
  120. def __iter__(self):
  121. return iter((self.ttype, self.value))
  122. def __getitem__(self, i):
  123. if i == 0:
  124. return self.ttype
  125. elif i == 1:
  126. return self.value
  127. else:
  128. raise IndexError
  129. class Tokenizer(object):
  130. """A DNS master file format tokenizer.
  131. A token is a (type, value) tuple, where I{type} is an int, and
  132. I{value} is a string. The valid types are EOF, EOL, WHITESPACE,
  133. IDENTIFIER, QUOTED_STRING, COMMENT, and DELIMITER.
  134. @ivar file: The file to tokenize
  135. @type file: file
  136. @ivar ungotten_char: The most recently ungotten character, or None.
  137. @type ungotten_char: string
  138. @ivar ungotten_token: The most recently ungotten token, or None.
  139. @type ungotten_token: (int, string) token tuple
  140. @ivar multiline: The current multiline level. This value is increased
  141. by one every time a '(' delimiter is read, and decreased by one every time
  142. a ')' delimiter is read.
  143. @type multiline: int
  144. @ivar quoting: This variable is true if the tokenizer is currently
  145. reading a quoted string.
  146. @type quoting: bool
  147. @ivar eof: This variable is true if the tokenizer has encountered EOF.
  148. @type eof: bool
  149. @ivar delimiters: The current delimiter dictionary.
  150. @type delimiters: dict
  151. @ivar line_number: The current line number
  152. @type line_number: int
  153. @ivar filename: A filename that will be returned by the L{where} method.
  154. @type filename: string
  155. """
  156. def __init__(self, f=sys.stdin, filename=None):
  157. """Initialize a tokenizer instance.
  158. @param f: The file to tokenize. The default is sys.stdin.
  159. This parameter may also be a string, in which case the tokenizer
  160. will take its input from the contents of the string.
  161. @type f: file or string
  162. @param filename: the name of the filename that the L{where} method
  163. will return.
  164. @type filename: string
  165. """
  166. if isinstance(f, text_type):
  167. f = StringIO(f)
  168. if filename is None:
  169. filename = '<string>'
  170. elif isinstance(f, binary_type):
  171. f = StringIO(f.decode())
  172. if filename is None:
  173. filename = '<string>'
  174. else:
  175. if filename is None:
  176. if f is sys.stdin:
  177. filename = '<stdin>'
  178. else:
  179. filename = '<file>'
  180. self.file = f
  181. self.ungotten_char = None
  182. self.ungotten_token = None
  183. self.multiline = 0
  184. self.quoting = False
  185. self.eof = False
  186. self.delimiters = _DELIMITERS
  187. self.line_number = 1
  188. self.filename = filename
  189. def _get_char(self):
  190. """Read a character from input.
  191. @rtype: string
  192. """
  193. if self.ungotten_char is None:
  194. if self.eof:
  195. c = ''
  196. else:
  197. c = self.file.read(1)
  198. if c == '':
  199. self.eof = True
  200. elif c == '\n':
  201. self.line_number += 1
  202. else:
  203. c = self.ungotten_char
  204. self.ungotten_char = None
  205. return c
  206. def where(self):
  207. """Return the current location in the input.
  208. @rtype: (string, int) tuple. The first item is the filename of
  209. the input, the second is the current line number.
  210. """
  211. return (self.filename, self.line_number)
  212. def _unget_char(self, c):
  213. """Unget a character.
  214. The unget buffer for characters is only one character large; it is
  215. an error to try to unget a character when the unget buffer is not
  216. empty.
  217. @param c: the character to unget
  218. @type c: string
  219. @raises UngetBufferFull: there is already an ungotten char
  220. """
  221. if self.ungotten_char is not None:
  222. raise UngetBufferFull
  223. self.ungotten_char = c
  224. def skip_whitespace(self):
  225. """Consume input until a non-whitespace character is encountered.
  226. The non-whitespace character is then ungotten, and the number of
  227. whitespace characters consumed is returned.
  228. If the tokenizer is in multiline mode, then newlines are whitespace.
  229. @rtype: int
  230. """
  231. skipped = 0
  232. while True:
  233. c = self._get_char()
  234. if c != ' ' and c != '\t':
  235. if (c != '\n') or not self.multiline:
  236. self._unget_char(c)
  237. return skipped
  238. skipped += 1
  239. def get(self, want_leading=False, want_comment=False):
  240. """Get the next token.
  241. @param want_leading: If True, return a WHITESPACE token if the
  242. first character read is whitespace. The default is False.
  243. @type want_leading: bool
  244. @param want_comment: If True, return a COMMENT token if the
  245. first token read is a comment. The default is False.
  246. @type want_comment: bool
  247. @rtype: Token object
  248. @raises dns.exception.UnexpectedEnd: input ended prematurely
  249. @raises dns.exception.SyntaxError: input was badly formed
  250. """
  251. if self.ungotten_token is not None:
  252. token = self.ungotten_token
  253. self.ungotten_token = None
  254. if token.is_whitespace():
  255. if want_leading:
  256. return token
  257. elif token.is_comment():
  258. if want_comment:
  259. return token
  260. else:
  261. return token
  262. skipped = self.skip_whitespace()
  263. if want_leading and skipped > 0:
  264. return Token(WHITESPACE, ' ')
  265. token = ''
  266. ttype = IDENTIFIER
  267. has_escape = False
  268. while True:
  269. c = self._get_char()
  270. if c == '' or c in self.delimiters:
  271. if c == '' and self.quoting:
  272. raise dns.exception.UnexpectedEnd
  273. if token == '' and ttype != QUOTED_STRING:
  274. if c == '(':
  275. self.multiline += 1
  276. self.skip_whitespace()
  277. continue
  278. elif c == ')':
  279. if self.multiline <= 0:
  280. raise dns.exception.SyntaxError
  281. self.multiline -= 1
  282. self.skip_whitespace()
  283. continue
  284. elif c == '"':
  285. if not self.quoting:
  286. self.quoting = True
  287. self.delimiters = _QUOTING_DELIMITERS
  288. ttype = QUOTED_STRING
  289. continue
  290. else:
  291. self.quoting = False
  292. self.delimiters = _DELIMITERS
  293. self.skip_whitespace()
  294. continue
  295. elif c == '\n':
  296. return Token(EOL, '\n')
  297. elif c == ';':
  298. while 1:
  299. c = self._get_char()
  300. if c == '\n' or c == '':
  301. break
  302. token += c
  303. if want_comment:
  304. self._unget_char(c)
  305. return Token(COMMENT, token)
  306. elif c == '':
  307. if self.multiline:
  308. raise dns.exception.SyntaxError(
  309. 'unbalanced parentheses')
  310. return Token(EOF)
  311. elif self.multiline:
  312. self.skip_whitespace()
  313. token = ''
  314. continue
  315. else:
  316. return Token(EOL, '\n')
  317. else:
  318. # This code exists in case we ever want a
  319. # delimiter to be returned. It never produces
  320. # a token currently.
  321. token = c
  322. ttype = DELIMITER
  323. else:
  324. self._unget_char(c)
  325. break
  326. elif self.quoting:
  327. if c == '\\':
  328. c = self._get_char()
  329. if c == '':
  330. raise dns.exception.UnexpectedEnd
  331. if c.isdigit():
  332. c2 = self._get_char()
  333. if c2 == '':
  334. raise dns.exception.UnexpectedEnd
  335. c3 = self._get_char()
  336. if c == '':
  337. raise dns.exception.UnexpectedEnd
  338. if not (c2.isdigit() and c3.isdigit()):
  339. raise dns.exception.SyntaxError
  340. c = chr(int(c) * 100 + int(c2) * 10 + int(c3))
  341. elif c == '\n':
  342. raise dns.exception.SyntaxError('newline in quoted string')
  343. elif c == '\\':
  344. #
  345. # It's an escape. Put it and the next character into
  346. # the token; it will be checked later for goodness.
  347. #
  348. token += c
  349. has_escape = True
  350. c = self._get_char()
  351. if c == '' or c == '\n':
  352. raise dns.exception.UnexpectedEnd
  353. token += c
  354. if token == '' and ttype != QUOTED_STRING:
  355. if self.multiline:
  356. raise dns.exception.SyntaxError('unbalanced parentheses')
  357. ttype = EOF
  358. return Token(ttype, token, has_escape)
  359. def unget(self, token):
  360. """Unget a token.
  361. The unget buffer for tokens is only one token large; it is
  362. an error to try to unget a token when the unget buffer is not
  363. empty.
  364. @param token: the token to unget
  365. @type token: Token object
  366. @raises UngetBufferFull: there is already an ungotten token
  367. """
  368. if self.ungotten_token is not None:
  369. raise UngetBufferFull
  370. self.ungotten_token = token
  371. def next(self):
  372. """Return the next item in an iteration.
  373. @rtype: (int, string)
  374. """
  375. token = self.get()
  376. if token.is_eof():
  377. raise StopIteration
  378. return token
  379. __next__ = next
  380. def __iter__(self):
  381. return self
  382. # Helpers
  383. def get_int(self):
  384. """Read the next token and interpret it as an integer.
  385. @raises dns.exception.SyntaxError:
  386. @rtype: int
  387. """
  388. token = self.get().unescape()
  389. if not token.is_identifier():
  390. raise dns.exception.SyntaxError('expecting an identifier')
  391. if not token.value.isdigit():
  392. raise dns.exception.SyntaxError('expecting an integer')
  393. return int(token.value)
  394. def get_uint8(self):
  395. """Read the next token and interpret it as an 8-bit unsigned
  396. integer.
  397. @raises dns.exception.SyntaxError:
  398. @rtype: int
  399. """
  400. value = self.get_int()
  401. if value < 0 or value > 255:
  402. raise dns.exception.SyntaxError(
  403. '%d is not an unsigned 8-bit integer' % value)
  404. return value
  405. def get_uint16(self):
  406. """Read the next token and interpret it as a 16-bit unsigned
  407. integer.
  408. @raises dns.exception.SyntaxError:
  409. @rtype: int
  410. """
  411. value = self.get_int()
  412. if value < 0 or value > 65535:
  413. raise dns.exception.SyntaxError(
  414. '%d is not an unsigned 16-bit integer' % value)
  415. return value
  416. def get_uint32(self):
  417. """Read the next token and interpret it as a 32-bit unsigned
  418. integer.
  419. @raises dns.exception.SyntaxError:
  420. @rtype: int
  421. """
  422. token = self.get().unescape()
  423. if not token.is_identifier():
  424. raise dns.exception.SyntaxError('expecting an identifier')
  425. if not token.value.isdigit():
  426. raise dns.exception.SyntaxError('expecting an integer')
  427. value = long(token.value)
  428. if value < 0 or value > long(4294967296):
  429. raise dns.exception.SyntaxError(
  430. '%d is not an unsigned 32-bit integer' % value)
  431. return value
  432. def get_string(self, origin=None):
  433. """Read the next token and interpret it as a string.
  434. @raises dns.exception.SyntaxError:
  435. @rtype: string
  436. """
  437. token = self.get().unescape()
  438. if not (token.is_identifier() or token.is_quoted_string()):
  439. raise dns.exception.SyntaxError('expecting a string')
  440. return token.value
  441. def get_identifier(self, origin=None):
  442. """Read the next token and raise an exception if it is not an identifier.
  443. @raises dns.exception.SyntaxError:
  444. @rtype: string
  445. """
  446. token = self.get().unescape()
  447. if not token.is_identifier():
  448. raise dns.exception.SyntaxError('expecting an identifier')
  449. return token.value
  450. def get_name(self, origin=None):
  451. """Read the next token and interpret it as a DNS name.
  452. @raises dns.exception.SyntaxError:
  453. @rtype: dns.name.Name object"""
  454. token = self.get()
  455. if not token.is_identifier():
  456. raise dns.exception.SyntaxError('expecting an identifier')
  457. return dns.name.from_text(token.value, origin)
  458. def get_eol(self):
  459. """Read the next token and raise an exception if it isn't EOL or
  460. EOF.
  461. @raises dns.exception.SyntaxError:
  462. @rtype: string
  463. """
  464. token = self.get()
  465. if not token.is_eol_or_eof():
  466. raise dns.exception.SyntaxError(
  467. 'expected EOL or EOF, got %d "%s"' % (token.ttype,
  468. token.value))
  469. return token.value
  470. def get_ttl(self):
  471. token = self.get().unescape()
  472. if not token.is_identifier():
  473. raise dns.exception.SyntaxError('expecting an identifier')
  474. return dns.ttl.from_text(token.value)