Lib/idlelib/PyParse.py

   1 import string
   2 import re
   3 import sys
   4
   5 # Reason last stmt is continued (or C_NONE if it's not).
   6 C_NONE, C_BACKSLASH, C_STRING, C_BRACKET = range(4)
   7
   8 if 0:   # for throwaway debugging output
   9     def dump(*stuff):
  10         sys.__stdout__.write(string.join(map(str, stuff), " ") + "\n")
  11
  12 # Find what looks like the start of a popular stmt.
  13
  14 _synchre = re.compile(r"""
  15     ^
  16     [ \t]*
  17     (?: if
  18     |   for
  19     |   while
  20     |   else
  21     |   def
  22     |   return
  23     |   assert
  24     |   break
  25     |   class
  26     |   continue
  27     |   elif
  28     |   try
  29     |   except
  30     |   raise
  31     |   import
  32     )
  33     \b
  34 """, re.VERBOSE | re.MULTILINE).search
  35
  36 # Match blank line or non-indenting comment line.
  37
  38 _junkre = re.compile(r"""
  39     [ \t]*
  40     (?: \# \S .* )?
  41     \n
  42 """, re.VERBOSE).match
  43
  44 # Match any flavor of string; the terminating quote is optional
  45 # so that we're robust in the face of incomplete program text.
  46
  47 _match_stringre = re.compile(r"""
  48     \""" [^"\\]* (?:
  49                      (?: \\. | "(?!"") )
  50                      [^"\\]*
  51                  )*
  52     (?: \""" )?
  53
  54 |   " [^"\\\n]* (?: \\. [^"\\\n]* )* "?
  55
  56 |   ''' [^'\\]* (?:
  57                    (?: \\. | '(?!'') )
  58                    [^'\\]*
  59                 )*
  60     (?: ''' )?
  61
  62 |   ' [^'\\\n]* (?: \\. [^'\\\n]* )* '?
  63 """, re.VERBOSE | re.DOTALL).match
  64
  65 # Match a line that starts with something interesting;
  66 # used to find the first item of a bracket structure.
  67
  68 _itemre = re.compile(r"""
  69     [ \t]*
  70     [^\s#\\]    # if we match, m.end()-1 is the interesting char
  71 """, re.VERBOSE).match
  72
  73 # Match start of stmts that should be followed by a dedent.
  74
  75 _closere = re.compile(r"""
  76     \s*
  77     (?: return
  78     |   break
  79     |   continue
  80     |   raise
  81     |   pass
  82     )
  83     \b
  84 """, re.VERBOSE).match
  85
  86 # Chew up non-special chars as quickly as possible.  If match is
  87 # successful, m.end() less 1 is the index of the last boring char
  88 # matched.  If match is unsuccessful, the string starts with an
  89 # interesting char.
  90
  91 _chew_ordinaryre = re.compile(r"""
  92     [^[\](){}#'"\\]+
  93 """, re.VERBOSE).match
  94
  95 # Build translation table to map uninteresting chars to "x", open
  96 # brackets to "(", and close brackets to ")".
  97
  98 _tran = ['x'] * 256
  99 for ch in "({[":
 100     _tran[ord(ch)] = '('
 101 for ch in ")}]":
 102     _tran[ord(ch)] = ')'
 103 for ch in "\"'\\\n#":
 104     _tran[ord(ch)] = ch
 105 _tran = string.join(_tran, '')
 106 del ch
 107
 108 class Parser:
 109
 110     def __init__(self, indentwidth, tabwidth):
 111         self.indentwidth = indentwidth
 112         self.tabwidth = tabwidth
 113
 114     def set_str(self, str):
 115         assert len(str) == 0 or str[-1] == '\n'
 116         self.str = str
 117         self.study_level = 0
 118
 119     # Return index of a good place to begin parsing, as close to the
 120     # end of the string as possible.  This will be the start of some
 121     # popular stmt like "if" or "def".  Return None if none found:
 122     # the caller should pass more prior context then, if possible, or
 123     # if not (the entire program text up until the point of interest
 124     # has already been tried) pass 0 to set_lo.
 125     #
 126     # This will be reliable iff given a reliable is_char_in_string
 127     # function, meaning that when it says "no", it's absolutely
 128     # guaranteed that the char is not in a string.
 129     #
 130     # Ack, hack: in the shell window this kills us, because there's
 131     # no way to tell the differences between output, >>> etc and
 132     # user input.  Indeed, IDLE's first output line makes the rest
 133     # look like it's in an unclosed paren!:
 134     # Python 1.5.2 (#0, Apr 13 1999, ...
 135
 136     def find_good_parse_start(self, use_ps1, is_char_in_string=None,
 137                               _rfind=string.rfind,
 138                               _synchre=_synchre):
 139         str, pos = self.str, None
 140         if use_ps1:
 141             # shell window
 142             ps1 = '\n' + sys.ps1
 143             i = _rfind(str, ps1)
 144             if i >= 0:
 145                 pos = i + len(ps1)
 146                 # make it look like there's a newline instead
 147                 # of ps1 at the start -- hacking here once avoids
 148                 # repeated hackery later
 149                 self.str = str[:pos-1] + '\n' + str[pos:]
 150             return pos
 151
 152         # File window -- real work.
 153         if not is_char_in_string:
 154             # no clue -- make the caller pass everything
 155             return None
 156
 157         # Peek back from the end for a good place to start,
 158         # but don't try too often; pos will be left None, or
 159         # bumped to a legitimate synch point.
 160         limit = len(str)
 161         for tries in range(5):
 162             i = _rfind(str, ":\n", 0, limit)
 163             if i < 0:
 164                 break
 165             i = _rfind(str, '\n', 0, i) + 1  # start of colon line
 166             m = _synchre(str, i, limit)
 167             if m and not is_char_in_string(m.start()):
 168                 pos = m.start()
 169                 break
 170             limit = i
 171         if pos is None:
 172             # Nothing looks like a block-opener, or stuff does
 173             # but is_char_in_string keeps returning true; most likely
 174             # we're in or near a giant string, the colorizer hasn't
 175             # caught up enough to be helpful, or there simply *aren't*
 176             # any interesting stmts.  In any of these cases we're
 177             # going to have to parse the whole thing to be sure, so
 178             # give it one last try from the start, but stop wasting
 179             # time here regardless of the outcome.
 180             m = _synchre(str)
 181             if m and not is_char_in_string(m.start()):
 182                 pos = m.start()
 183             return pos
 184
 185         # Peeking back worked; look forward until _synchre no longer
 186         # matches.
 187         i = pos + 1
 188         while 1:
 189             m = _synchre(str, i)
 190             if m:
 191                 s, i = m.span()
 192                 if not is_char_in_string(s):
 193                     pos = s
 194             else:
 195                 break
 196         return pos
 197
 198     # Throw away the start of the string.  Intended to be called with
 199     # find_good_parse_start's result.
 200
 201     def set_lo(self, lo):
 202         assert lo == 0 or self.str[lo-1] == '\n'
 203         if lo > 0:
 204             self.str = self.str[lo:]
 205
 206     # As quickly as humanly possible <wink>, find the line numbers (0-
 207     # based) of the non-continuation lines.
 208     # Creates self.{goodlines, continuation}.
 209
 210     def _study1(self, _replace=string.replace, _find=string.find):
 211         if self.study_level >= 1:
 212             return
 213         self.study_level = 1
 214
 215         # Map all uninteresting characters to "x", all open brackets
 216         # to "(", all close brackets to ")", then collapse runs of
 217         # uninteresting characters.  This can cut the number of chars
 218         # by a factor of 10-40, and so greatly speed the following loop.
 219         str = self.str
 220         str = string.translate(str, _tran)
 221         str = _replace(str, 'xxxxxxxx', 'x')
 222         str = _replace(str, 'xxxx', 'x')
 223         str = _replace(str, 'xx', 'x')
 224         str = _replace(str, 'xx', 'x')
 225         str = _replace(str, '\nx', '\n')
 226         # note that replacing x\n with \n would be incorrect, because
 227         # x may be preceded by a backslash
 228
 229         # March over the squashed version of the program, accumulating
 230         # the line numbers of non-continued stmts, and determining
 231         # whether & why the last stmt is a continuation.
 232         continuation = C_NONE
 233         level = lno = 0     # level is nesting level; lno is line number
 234         self.goodlines = goodlines = [0]
 235         push_good = goodlines.append
 236         i, n = 0, len(str)
 237         while i < n:
 238             ch = str[i]
 239             i = i+1
 240
 241             # cases are checked in decreasing order of frequency
 242             if ch == 'x':
 243                 continue
 244
 245             if ch == '\n':
 246                 lno = lno + 1
 247                 if level == 0:
 248                     push_good(lno)
 249                     # else we're in an unclosed bracket structure
 250                 continue
 251
 252             if ch == '(':
 253                 level = level + 1
 254                 continue
 255
 256             if ch == ')':
 257                 if level:
 258                     level = level - 1
 259                     # else the program is invalid, but we can't complain
 260                 continue
 261
 262             if ch == '"' or ch == "'":
 263                 # consume the string
 264                 quote = ch
 265                 if str[i-1:i+2] == quote * 3:
 266                     quote = quote * 3
 267                 w = len(quote) - 1
 268                 i = i+w
 269                 while i < n:
 270                     ch = str[i]
 271                     i = i+1
 272
 273                     if ch == 'x':
 274                         continue
 275
 276                     if str[i-1:i+w] == quote:
 277                         i = i+w
 278                         break
 279
 280                     if ch == '\n':
 281                         lno = lno + 1
 282                         if w == 0:
 283                             # unterminated single-quoted string
 284                             if level == 0:
 285                                 push_good(lno)
 286                             break
 287                         continue
 288
 289                     if ch == '\\':
 290                         assert i < n
 291                         if str[i] == '\n':
 292                             lno = lno + 1
 293                         i = i+1
 294                         continue
 295
 296                     # else comment char or paren inside string
 297
 298                 else:
 299                     # didn't break out of the loop, so we're still
 300                     # inside a string
 301                     continuation = C_STRING
 302                 continue    # with outer loop
 303
 304             if ch == '#':
 305                 # consume the comment
 306                 i = _find(str, '\n', i)
 307                 assert i >= 0
 308                 continue
 309
 310             assert ch == '\\'
 311             assert i < n
 312             if str[i] == '\n':
 313                 lno = lno + 1
 314                 if i+1 == n:
 315                     continuation = C_BACKSLASH
 316             i = i+1
 317
 318         # The last stmt may be continued for all 3 reasons.
 319         # String continuation takes precedence over bracket
 320         # continuation, which beats backslash continuation.
 321         if continuation != C_STRING and level > 0:
 322             continuation = C_BRACKET
 323         self.continuation = continuation
 324
 325         # Push the final line number as a sentinel value, regardless of
 326         # whether it's continued.
 327         assert (continuation == C_NONE) == (goodlines[-1] == lno)
 328         if goodlines[-1] != lno:
 329             push_good(lno)
 330
 331     def get_continuation_type(self):
 332         self._study1()
 333         return self.continuation
 334
 335     # study1 was sufficient to determine the continuation status,
 336     # but doing more requires looking at every character.  study2
 337     # does this for the last interesting statement in the block.
 338     # Creates:
 339     #     self.stmt_start, stmt_end
 340     #         slice indices of last interesting stmt
 341     #     self.lastch
 342     #         last non-whitespace character before optional trailing
 343     #         comment
 344     #     self.lastopenbracketpos
 345     #         if continuation is C_BRACKET, index of last open bracket
 346
 347     def _study2(self, _rfind=string.rfind, _find=string.find,
 348                       _ws=string.whitespace):
 349         if self.study_level >= 2:
 350             return
 351         self._study1()
 352         self.study_level = 2
 353
 354         # Set p and q to slice indices of last interesting stmt.
 355         str, goodlines = self.str, self.goodlines
 356         i = len(goodlines) - 1
 357         p = len(str)    # index of newest line
 358         while i:
 359             assert p
 360             # p is the index of the stmt at line number goodlines[i].
 361             # Move p back to the stmt at line number goodlines[i-1].
 362             q = p
 363             for nothing in range(goodlines[i-1], goodlines[i]):
 364                 # tricky: sets p to 0 if no preceding newline
 365                 p = _rfind(str, '\n', 0, p-1) + 1
 366             # The stmt str[p:q] isn't a continuation, but may be blank
 367             # or a non-indenting comment line.
 368             if  _junkre(str, p):
 369                 i = i-1
 370             else:
 371                 break
 372         if i == 0:
 373             # nothing but junk!
 374             assert p == 0
 375             q = p
 376         self.stmt_start, self.stmt_end = p, q
 377
 378         # Analyze this stmt, to find the last open bracket (if any)
 379         # and last interesting character (if any).
 380         lastch = ""
 381         stack = []  # stack of open bracket indices
 382         push_stack = stack.append
 383         while p < q:
 384             # suck up all except ()[]{}'"#\\
 385             m = _chew_ordinaryre(str, p, q)
 386             if m:
 387                 # we skipped at least one boring char
 388                 p = m.end()
 389                 # back up over totally boring whitespace
 390                 i = p-1    # index of last boring char
 391                 while i >= 0 and str[i] in " \t\n":
 392                     i = i-1
 393                 if i >= 0:
 394                     lastch = str[i]
 395                 if p >= q:
 396                     break
 397
 398             ch = str[p]
 399
 400             if ch in "([{":
 401                 push_stack(p)
 402                 lastch = ch
 403                 p = p+1
 404                 continue
 405
 406             if ch in ")]}":
 407                 if stack:
 408                     del stack[-1]
 409                 lastch = ch
 410                 p = p+1
 411                 continue
 412
 413             if ch == '"' or ch == "'":
 414                 # consume string
 415                 # Note that study1 did this with a Python loop, but
 416                 # we use a regexp here; the reason is speed in both
 417                 # cases; the string may be huge, but study1 pre-squashed
 418                 # strings to a couple of characters per line.  study1
 419                 # also needed to keep track of newlines, and we don't
 420                 # have to.
 421                 lastch = ch
 422                 p = _match_stringre(str, p, q).end()
 423                 continue
 424
 425             if ch == '#':
 426                 # consume comment and trailing newline
 427                 p = _find(str, '\n', p, q) + 1
 428                 assert p > 0
 429                 continue
 430
 431             assert ch == '\\'
 432             p = p+1     # beyond backslash
 433             assert p < q
 434             if str[p] != '\n':
 435                 # the program is invalid, but can't complain
 436                 lastch = ch + str[p]
 437             p = p+1     # beyond escaped char
 438
 439         # end while p < q:
 440
 441         self.lastch = lastch
 442         if stack:
 443             self.lastopenbracketpos = stack[-1]
 444
 445     # Assuming continuation is C_BRACKET, return the number
 446     # of spaces the next line should be indented.
 447
 448     def compute_bracket_indent(self, _find=string.find):
 449         self._study2()
 450         assert self.continuation == C_BRACKET
 451         j = self.lastopenbracketpos
 452         str = self.str
 453         n = len(str)
 454         origi = i = string.rfind(str, '\n', 0, j) + 1
 455         j = j+1     # one beyond open bracket
 456         # find first list item; set i to start of its line
 457         while j < n:
 458             m = _itemre(str, j)
 459             if m:
 460                 j = m.end() - 1     # index of first interesting char
 461                 extra = 0
 462                 break
 463             else:
 464                 # this line is junk; advance to next line
 465                 i = j = _find(str, '\n', j) + 1
 466         else:
 467             # nothing interesting follows the bracket;
 468             # reproduce the bracket line's indentation + a level
 469             j = i = origi
 470             while str[j] in " \t":
 471                 j = j+1
 472             extra = self.indentwidth
 473         return len(string.expandtabs(str[i:j],
 474                                      self.tabwidth)) + extra
 475
 476     # Return number of physical lines in last stmt (whether or not
 477     # it's an interesting stmt!  this is intended to be called when
 478     # continuation is C_BACKSLASH).
 479
 480     def get_num_lines_in_stmt(self):
 481         self._study1()
 482         goodlines = self.goodlines
 483         return goodlines[-1] - goodlines[-2]
 484
 485     # Assuming continuation is C_BACKSLASH, return the number of spaces
 486     # the next line should be indented.  Also assuming the new line is
 487     # the first one following the initial line of the stmt.
 488
 489     def compute_backslash_indent(self):
 490         self._study2()
 491         assert self.continuation == C_BACKSLASH
 492         str = self.str
 493         i = self.stmt_start
 494         while str[i] in " \t":
 495             i = i+1
 496         startpos = i
 497
 498         # See whether the initial line starts an assignment stmt; i.e.,
 499         # look for an = operator
 500         endpos = string.find(str, '\n', startpos) + 1
 501         found = level = 0
 502         while i < endpos:
 503             ch = str[i]
 504             if ch in "([{":
 505                 level = level + 1
 506                 i = i+1
 507             elif ch in ")]}":
 508                 if level:
 509                     level = level - 1
 510                 i = i+1
 511             elif ch == '"' or ch == "'":
 512                 i = _match_stringre(str, i, endpos).end()
 513             elif ch == '#':
 514                 break
 515             elif level == 0 and ch == '=' and \
 516                    (i == 0 or str[i-1] not in "=<>!") and \
 517                    str[i+1] != '=':
 518                 found = 1
 519                 break
 520             else:
 521                 i = i+1
 522
 523         if found:
 524             # found a legit =, but it may be the last interesting
 525             # thing on the line
 526             i = i+1     # move beyond the =
 527             found = re.match(r"\s*\\", str[i:endpos]) is None
 528
 529         if not found:
 530             # oh well ... settle for moving beyond the first chunk
 531             # of non-whitespace chars
 532             i = startpos
 533             while str[i] not in " \t\n":
 534                 i = i+1
 535
 536         return len(string.expandtabs(str[self.stmt_start :
 537                                          i],
 538                                      self.tabwidth)) + 1
 539
 540     # Return the leading whitespace on the initial line of the last
 541     # interesting stmt.
 542
 543     def get_base_indent_string(self):
 544         self._study2()
 545         i, n = self.stmt_start, self.stmt_end
 546         j = i
 547         str = self.str
 548         while j < n and str[j] in " \t":
 549             j = j + 1
 550         return str[i:j]
 551
 552     # Did the last interesting stmt open a block?
 553
 554     def is_block_opener(self):
 555         self._study2()
 556         return self.lastch == ':'
 557
 558     # Did the last interesting stmt close a block?
 559
 560     def is_block_closer(self):
 561         self._study2()
 562         return _closere(self.str, self.stmt_start) is not None
 563
 564     # index of last open bracket ({[, or None if none
 565     lastopenbracketpos = None
 566
 567     def get_last_open_bracket_pos(self):
 568         self._study2()
 569         return self.lastopenbracketpos