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