Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# $Id$
2# Author: David Goodger <goodger@python.org>
3# Copyright: This module has been placed in the public domain.
5"""
6A finite state machine specialized for regular-expression-based text filters,
7this module defines the following classes:
9- `StateMachine`, a state machine
10- `State`, a state superclass
11- `StateMachineWS`, a whitespace-sensitive version of `StateMachine`
12- `StateWS`, a state superclass for use with `StateMachineWS`
13- `SearchStateMachine`, uses `re.search()` instead of `re.match()`
14- `SearchStateMachineWS`, uses `re.search()` instead of `re.match()`
15- `ViewList`, extends standard Python lists.
16- `StringList`, string-specific ViewList.
18Exception classes:
20- `StateMachineError`
21- `UnknownStateError`
22- `DuplicateStateError`
23- `UnknownTransitionError`
24- `DuplicateTransitionError`
25- `TransitionPatternNotFound`
26- `TransitionMethodNotFound`
27- `UnexpectedIndentationError`
28- `TransitionCorrection`: Raised to switch to another transition.
29- `StateCorrection`: Raised to switch to another state & transition.
31Functions:
33- `string2lines()`: split a multi-line string into a list of one-line strings
36How To Use This Module
37======================
38(See the individual classes, methods, and attributes for details.)
401. Import it: ``import statemachine`` or ``from statemachine import ...``.
41 You will also need to ``import re``.
432. Derive a subclass of `State` (or `StateWS`) for each state in your state
44 machine::
46 class MyState(statemachine.State):
48 Within the state's class definition:
50 a) Include a pattern for each transition, in `State.patterns`::
52 patterns = {'atransition': r'pattern', ...}
54 b) Include a list of initial transitions to be set up automatically, in
55 `State.initial_transitions`::
57 initial_transitions = ['atransition', ...]
59 c) Define a method for each transition, with the same name as the
60 transition pattern::
62 def atransition(self, match, context, next_state):
63 # do something
64 result = [...] # a list
65 return context, next_state, result
66 # context, next_state may be altered
68 Transition methods may raise an `EOFError` to cut processing short.
70 d) You may wish to override the `State.bof()` and/or `State.eof()` implicit
71 transition methods, which handle the beginning- and end-of-file.
73 e) In order to handle nested processing, you may wish to override the
74 attributes `State.nested_sm` and/or `State.nested_sm_kwargs`.
76 If you are using `StateWS` as a base class, in order to handle nested
77 indented blocks, you may wish to:
79 - override the attributes `StateWS.indent_sm`,
80 `StateWS.indent_sm_kwargs`, `StateWS.known_indent_sm`, and/or
81 `StateWS.known_indent_sm_kwargs`;
82 - override the `StateWS.blank()` method; and/or
83 - override or extend the `StateWS.indent()`, `StateWS.known_indent()`,
84 and/or `StateWS.firstknown_indent()` methods.
863. Create a state machine object::
88 sm = StateMachine(state_classes=[MyState, ...],
89 initial_state='MyState')
914. Obtain the input text, which needs to be converted into a tab-free list of
92 one-line strings. For example, to read text from a file called
93 'inputfile'::
95 with open('inputfile', encoding='utf-8') as fp:
96 input_string = fp.read()
97 input_lines = statemachine.string2lines(input_string)
995. Run the state machine on the input text and collect the results, a list::
101 results = sm.run(input_lines)
1036. Remove any lingering circular references::
105 sm.unlink()
106"""
108__docformat__ = 'restructuredtext'
110import sys
111import re
112from unicodedata import east_asian_width
114from docutils import utils
117class StateMachine:
119 """
120 A finite state machine for text filters using regular expressions.
122 The input is provided in the form of a list of one-line strings (no
123 newlines). States are subclasses of the `State` class. Transitions consist
124 of regular expression patterns and transition methods, and are defined in
125 each state.
127 The state machine is started with the `run()` method, which returns the
128 results of processing in a list.
129 """
131 def __init__(self, state_classes, initial_state, debug=False) -> None:
132 """
133 Initialize a `StateMachine` object; add state objects.
135 Parameters:
137 - `state_classes`: a list of `State` (sub)classes.
138 - `initial_state`: a string, the class name of the initial state.
139 - `debug`: a boolean; produce verbose output if true (nonzero).
140 """
142 self.input_lines = None
143 """`StringList` of input lines (without newlines).
144 Filled by `self.run()`."""
146 self.input_offset = 0
147 """Offset of `self.input_lines` from the beginning of the file."""
149 self.line = None
150 """Current input line."""
152 self.line_offset = -1
153 """Current input line offset from beginning of `self.input_lines`."""
155 self.debug = debug
156 """Debugging mode on/off."""
158 self.initial_state = initial_state
159 """The name of the initial state (key to `self.states`)."""
161 self.current_state = initial_state
162 """The name of the current state (key to `self.states`)."""
164 self.states = {}
165 """Mapping of {state_name: State_object}."""
167 self.add_states(state_classes)
169 self.observers = []
170 """List of bound methods or functions to call whenever the current
171 line changes. Observers are called with one argument, ``self``.
172 Cleared at the end of `run()`."""
174 def unlink(self) -> None:
175 """Remove circular references to objects no longer required."""
176 for state in self.states.values():
177 state.unlink()
178 self.states = None
180 def run(self, input_lines, input_offset=0, context=None,
181 input_source=None, initial_state=None):
182 """
183 Run the state machine on `input_lines`. Return results (a list).
185 Reset `self.line_offset` and `self.current_state`. Run the
186 beginning-of-file transition. Input one line at a time and check for a
187 matching transition. If a match is found, call the transition method
188 and possibly change the state. Store the context returned by the
189 transition method to be passed on to the next transition matched.
190 Accumulate the results returned by the transition methods in a list.
191 Run the end-of-file transition. Finally, return the accumulated
192 results.
194 Parameters:
196 - `input_lines`: a list of strings without newlines, or `StringList`.
197 - `input_offset`: the line offset of `input_lines` from the beginning
198 of the file.
199 - `context`: application-specific storage.
200 - `input_source`: name or path of source of `input_lines`.
201 - `initial_state`: name of initial state.
202 """
203 self.runtime_init()
204 if isinstance(input_lines, StringList):
205 self.input_lines = input_lines
206 else:
207 self.input_lines = StringList(input_lines, source=input_source)
208 self.input_offset = input_offset
209 self.line_offset = -1
210 self.current_state = initial_state or self.initial_state
211 if self.debug:
212 print('\nStateMachine.run: input_lines (line_offset=%s):\n| %s'
213 % (self.line_offset, '\n| '.join(self.input_lines)),
214 file=sys.stderr)
215 transitions = None
216 results = []
217 state = self.get_state()
218 try:
219 if self.debug:
220 print('\nStateMachine.run: bof transition', file=sys.stderr)
221 context, result = state.bof(context)
222 results.extend(result)
223 while True:
224 try:
225 try:
226 self.next_line()
227 if self.debug:
228 source, offset = self.input_lines.info(
229 self.line_offset)
230 print(f'\nStateMachine.run: line '
231 f'(source={source!r}, offset={offset!r}):\n'
232 f'| {self.line}', file=sys.stderr)
233 context, next_state, result = self.check_line(
234 context, state, transitions)
235 except EOFError:
236 if self.debug:
237 print('\nStateMachine.run: %s.eof transition'
238 % state.__class__.__name__, file=sys.stderr)
239 result = state.eof(context)
240 results.extend(result)
241 break
242 else:
243 results.extend(result)
244 except TransitionCorrection as exception:
245 self.previous_line() # back up for another try
246 transitions = (exception.args[0],)
247 if self.debug:
248 print('\nStateMachine.run: TransitionCorrection to '
249 f'state "{state.__class__.__name__}", '
250 f'transition {transitions[0]}.',
251 file=sys.stderr)
252 continue
253 except StateCorrection as exception:
254 self.previous_line() # back up for another try
255 next_state = exception.args[0]
256 if len(exception.args) == 1:
257 transitions = None
258 else:
259 transitions = (exception.args[1],)
260 if self.debug:
261 print('\nStateMachine.run: StateCorrection to state '
262 f'"{next_state}", transition {transitions[0]}.',
263 file=sys.stderr)
264 else:
265 transitions = None
266 state = self.get_state(next_state)
267 except: # NoQA: E722 (catchall)
268 if self.debug:
269 self.error()
270 raise
271 self.observers = []
272 return results
274 def get_state(self, next_state=None):
275 """
276 Return current state object; set it first if `next_state` given.
278 Parameter `next_state`: a string, the name of the next state.
280 Exception: `UnknownStateError` raised if `next_state` unknown.
281 """
282 if next_state:
283 if self.debug and next_state != self.current_state:
284 print('\nStateMachine.get_state: Changing state from '
285 '"%s" to "%s" (input line %s).'
286 % (self.current_state, next_state,
287 self.abs_line_number()), file=sys.stderr)
288 self.current_state = next_state
289 try:
290 return self.states[self.current_state]
291 except KeyError:
292 raise UnknownStateError(self.current_state)
294 def next_line(self, n=1):
295 """Load `self.line` with the `n`'th next line and return it."""
296 try:
297 try:
298 self.line_offset += n
299 self.line = self.input_lines[self.line_offset]
300 except IndexError:
301 self.line = None
302 raise EOFError
303 return self.line
304 finally:
305 self.notify_observers()
307 def is_next_line_blank(self):
308 """Return True if the next line is blank or non-existent."""
309 try:
310 return not self.input_lines[self.line_offset + 1].strip()
311 except IndexError:
312 return 1
314 def at_eof(self):
315 """Return 1 if the input is at or past end-of-file."""
316 return self.line_offset >= len(self.input_lines) - 1
318 def at_bof(self):
319 """Return 1 if the input is at or before beginning-of-file."""
320 return self.line_offset <= 0
322 def previous_line(self, n=1):
323 """Load `self.line` with the `n`'th previous line and return it."""
324 self.line_offset -= n
325 if self.line_offset < 0:
326 self.line = None
327 else:
328 self.line = self.input_lines[self.line_offset]
329 self.notify_observers()
330 return self.line
332 def goto_line(self, line_offset):
333 """Jump to absolute line offset `line_offset`, load and return it."""
334 try:
335 try:
336 self.line_offset = line_offset - self.input_offset
337 self.line = self.input_lines[self.line_offset]
338 except IndexError:
339 self.line = None
340 raise EOFError
341 return self.line
342 finally:
343 self.notify_observers()
345 def get_source(self, line_offset):
346 """Return source of line at absolute line offset `line_offset`."""
347 return self.input_lines.source(line_offset - self.input_offset)
349 def abs_line_offset(self):
350 """Return line offset of current line, from beginning of file."""
351 return self.line_offset + self.input_offset
353 def abs_line_number(self):
354 """Return line number of current line (counting from 1)."""
355 return self.line_offset + self.input_offset + 1
357 def get_source_and_line(self, lineno=None):
358 """Return (source, line) tuple for current or given line number.
360 Looks up the source and line number in the `self.input_lines`
361 StringList instance to count for included source files.
363 If the optional argument `lineno` is given, convert it from an
364 absolute line number to the corresponding (source, line) pair.
365 """
366 if lineno is None:
367 offset = self.line_offset
368 else:
369 offset = lineno - self.input_offset - 1
370 try:
371 src, srcoffset = self.input_lines.info(offset)
372 srcline = srcoffset + 1
373 except TypeError:
374 # line is None if index is "Just past the end"
375 src, srcline = self.get_source_and_line(offset + self.input_offset)
376 return src, srcline + 1
377 except IndexError: # `offset` is off the list
378 src, srcline = None, None
379 # raise AssertionError('cannot find line %d in %s lines' %
380 # (offset, len(self.input_lines)))
381 # # list(self.input_lines.lines())))
382 return src, srcline
384 def insert_input(self, input_lines, source) -> None:
385 self.input_lines.insert(self.line_offset + 1, '',
386 source='internal padding after '+source,
387 offset=len(input_lines))
388 self.input_lines.insert(self.line_offset + 1, '',
389 source='internal padding before '+source,
390 offset=-1)
391 self.input_lines.insert(self.line_offset + 2,
392 StringList(input_lines, source))
394 def get_text_block(self, flush_left=False):
395 """
396 Return a contiguous block of text.
398 If `flush_left` is true, raise `UnexpectedIndentationError` if an
399 indented line is encountered before the text block ends (with a blank
400 line).
401 """
402 try:
403 block = self.input_lines.get_text_block(self.line_offset,
404 flush_left)
405 self.next_line(len(block) - 1)
406 return block
407 except UnexpectedIndentationError as err:
408 block = err.args[0]
409 self.next_line(len(block) - 1) # advance to last line of block
410 raise
412 def check_line(self, context, state, transitions=None):
413 """
414 Examine one line of input for a transition match & execute its method.
416 Parameters:
418 - `context`: application-dependent storage.
419 - `state`: a `State` object, the current state.
420 - `transitions`: an optional ordered list of transition names to try,
421 instead of ``state.transition_order``.
423 Return the values returned by the transition method:
425 - context: possibly modified from the parameter `context`;
426 - next state name (`State` subclass name);
427 - the result output of the transition, a list.
429 When there is no match, ``state.no_match()`` is called and its return
430 value is returned.
431 """
432 if transitions is None:
433 transitions = state.transition_order
434 if self.debug:
435 print('\nStateMachine.check_line: state="%s", transitions=%r.'
436 % (state.__class__.__name__, transitions), file=sys.stderr)
437 for name in transitions:
438 pattern, method, next_state = state.transitions[name]
439 match = pattern.match(self.line)
440 if match:
441 if self.debug:
442 print('\nStateMachine.check_line: Matched transition '
443 f'"{name}" in state "{state.__class__.__name__}".',
444 file=sys.stderr)
445 return method(match, context, next_state)
446 else:
447 if self.debug:
448 print('\nStateMachine.check_line: No match in state "%s".'
449 % state.__class__.__name__, file=sys.stderr)
450 return state.no_match(context, transitions)
452 def add_state(self, state_class):
453 """
454 Initialize & add a `state_class` (`State` subclass) object.
456 Exception: `DuplicateStateError` raised if `state_class` was already
457 added.
458 """
459 statename = state_class.__name__
460 if statename in self.states:
461 raise DuplicateStateError(statename)
462 self.states[statename] = state_class(self, self.debug)
464 def add_states(self, state_classes) -> None:
465 """
466 Add `state_classes` (a list of `State` subclasses).
467 """
468 for state_class in state_classes:
469 self.add_state(state_class)
471 def runtime_init(self) -> None:
472 """
473 Initialize `self.states`.
474 """
475 for state in self.states.values():
476 state.runtime_init()
478 def error(self) -> None:
479 """Report error details."""
480 type_name, value, module, line, function = _exception_data()
481 print('%s: %s' % (type_name, value), file=sys.stderr)
482 print('input line %s' % (self.abs_line_number()), file=sys.stderr)
483 print('module %s, line %s, function %s' % (module, line, function),
484 file=sys.stderr)
486 def attach_observer(self, observer) -> None:
487 """
488 The `observer` parameter is a function or bound method which takes two
489 arguments, the source and offset of the current line.
490 """
491 self.observers.append(observer)
493 def detach_observer(self, observer) -> None:
494 self.observers.remove(observer)
496 def notify_observers(self) -> None:
497 for observer in self.observers:
498 try:
499 info = self.input_lines.info(self.line_offset)
500 except IndexError:
501 info = (None, None)
502 observer(*info)
505class State:
507 """
508 State superclass. Contains a list of transitions, and transition methods.
510 Transition methods all have the same signature. They take 3 parameters:
512 - An `re` match object. ``match.string`` contains the matched input line,
513 ``match.start()`` gives the start index of the match, and
514 ``match.end()`` gives the end index.
515 - A context object, whose meaning is application-defined (initial value
516 ``None``). It can be used to store any information required by the state
517 machine, and the returned context is passed on to the next transition
518 method unchanged.
519 - The name of the next state, a string, taken from the transitions list;
520 normally it is returned unchanged, but it may be altered by the
521 transition method if necessary.
523 Transition methods all return a 3-tuple:
525 - A context object, as (potentially) modified by the transition method.
526 - The next state name (a return value of ``None`` means no state change).
527 - The processing result, a list, which is accumulated by the state
528 machine.
530 Transition methods may raise an `EOFError` to cut processing short.
532 There are two implicit transitions, and corresponding transition methods
533 are defined: `bof()` handles the beginning-of-file, and `eof()` handles
534 the end-of-file. These methods have non-standard signatures and return
535 values. `bof()` returns the initial context and results, and may be used
536 to return a header string, or do any other processing needed. `eof()`
537 should handle any remaining context and wrap things up; it returns the
538 final processing result.
540 Typical applications need only subclass `State` (or a subclass), set the
541 `patterns` and `initial_transitions` class attributes, and provide
542 corresponding transition methods. The default object initialization will
543 take care of constructing the list of transitions.
544 """
546 patterns = None
547 """
548 {Name: pattern} mapping, used by `make_transition()`. Each pattern may
549 be a string or a compiled `re` pattern. Override in subclasses.
550 """
552 initial_transitions = None
553 """
554 A list of transitions to initialize when a `State` is instantiated.
555 Each entry is either a transition name string, or a (transition name, next
556 state name) pair. See `make_transitions()`. Override in subclasses.
557 """
559 nested_sm = None
560 """
561 The `StateMachine` class for handling nested processing.
563 If left as ``None``, `nested_sm` defaults to the class of the state's
564 controlling state machine. Override it in subclasses to avoid the default.
565 """
567 nested_sm_kwargs = None
568 """
569 Keyword arguments dictionary, passed to the `nested_sm` constructor.
571 Two keys must have entries in the dictionary:
573 - Key 'state_classes' must be set to a list of `State` classes.
574 - Key 'initial_state' must be set to the name of the initial state class.
576 If `nested_sm_kwargs` is left as ``None``, 'state_classes' defaults to the
577 class of the current state, and 'initial_state' defaults to the name of
578 the class of the current state. Override in subclasses to avoid the
579 defaults.
580 """
582 def __init__(self, state_machine, debug=False) -> None:
583 """
584 Initialize a `State` object; make & add initial transitions.
586 Parameters:
588 - `statemachine`: the controlling `StateMachine` object.
589 - `debug`: a boolean; produce verbose output if true.
590 """
592 self.transition_order = []
593 """A list of transition names in search order."""
595 self.transitions = {}
596 """
597 A mapping of transition names to 3-tuples containing
598 (compiled_pattern, transition_method, next_state_name). Initialized as
599 an instance attribute dynamically (instead of as a class attribute)
600 because it may make forward references to patterns and methods in this
601 or other classes.
602 """
604 self.add_initial_transitions()
606 self.state_machine = state_machine
607 """A reference to the controlling `StateMachine` object."""
609 self.debug = debug
610 """Debugging mode on/off."""
612 if self.nested_sm is None:
613 self.nested_sm = self.state_machine.__class__
614 if self.nested_sm_kwargs is None:
615 self.nested_sm_kwargs = {'state_classes': [self.__class__],
616 'initial_state': self.__class__.__name__}
618 def runtime_init(self) -> None:
619 """
620 Initialize this `State` before running the state machine; called from
621 `self.state_machine.run()`.
622 """
624 def unlink(self) -> None:
625 """Remove circular references to objects no longer required."""
626 self.state_machine = None
628 def add_initial_transitions(self) -> None:
629 """Make and add transitions listed in `self.initial_transitions`."""
630 if self.initial_transitions:
631 names, transitions = self.make_transitions(
632 self.initial_transitions)
633 self.add_transitions(names, transitions)
635 def add_transitions(self, names, transitions):
636 """
637 Add a list of transitions to the start of the transition list.
639 Parameters:
641 - `names`: a list of transition names.
642 - `transitions`: a mapping of names to transition tuples.
644 Exceptions: `DuplicateTransitionError`, `UnknownTransitionError`.
645 """
646 for name in names:
647 if name in self.transitions:
648 raise DuplicateTransitionError(name)
649 if name not in transitions:
650 raise UnknownTransitionError(name)
651 self.transition_order[:0] = names
652 self.transitions.update(transitions)
654 def add_transition(self, name, transition):
655 """
656 Add a transition to the start of the transition list.
658 Parameter `transition`: a ready-made transition 3-tuple.
660 Exception: `DuplicateTransitionError`.
661 """
662 if name in self.transitions:
663 raise DuplicateTransitionError(name)
664 self.transition_order[:0] = [name]
665 self.transitions[name] = transition
667 def remove_transition(self, name):
668 """
669 Remove a transition by `name`.
671 Exception: `UnknownTransitionError`.
672 """
673 try:
674 del self.transitions[name]
675 self.transition_order.remove(name)
676 except: # NoQA: E722 (catchall)
677 raise UnknownTransitionError(name)
679 def make_transition(self, name, next_state=None):
680 """
681 Make & return a transition tuple based on `name`.
683 This is a convenience function to simplify transition creation.
685 Parameters:
687 - `name`: a string, the name of the transition pattern & method. This
688 `State` object must have a method called '`name`', and a dictionary
689 `self.patterns` containing a key '`name`'.
690 - `next_state`: a string, the name of the next `State` object for this
691 transition. A value of ``None`` (or absent) implies no state change
692 (i.e., continue with the same state).
694 Exceptions: `TransitionPatternNotFound`, `TransitionMethodNotFound`.
695 """
696 if next_state is None:
697 next_state = self.__class__.__name__
698 try:
699 pattern = self.patterns[name]
700 if not hasattr(pattern, 'match'):
701 pattern = self.patterns[name] = re.compile(pattern)
702 except KeyError:
703 raise TransitionPatternNotFound(
704 '%s.patterns[%r]' % (self.__class__.__name__, name))
705 try:
706 method = getattr(self, name)
707 except AttributeError:
708 raise TransitionMethodNotFound(
709 '%s.%s' % (self.__class__.__name__, name))
710 return pattern, method, next_state
712 def make_transitions(self, name_list):
713 """
714 Return a list of transition names and a transition mapping.
716 Parameter `name_list`: a list, where each entry is either a transition
717 name string, or a 1- or 2-tuple (transition name, optional next state
718 name).
719 """
720 names = []
721 transitions = {}
722 for namestate in name_list:
723 if isinstance(namestate, str):
724 transitions[namestate] = self.make_transition(namestate)
725 names.append(namestate)
726 else:
727 transitions[namestate[0]] = self.make_transition(*namestate)
728 names.append(namestate[0])
729 return names, transitions
731 def no_match(self, context, transitions):
732 """
733 Called when there is no match from `StateMachine.check_line()`.
735 Return the same values returned by transition methods:
737 - context: unchanged;
738 - next state name: ``None``;
739 - empty result list.
741 Override in subclasses to catch this event.
742 """
743 return context, None, []
745 def bof(self, context):
746 """
747 Handle beginning-of-file. Return unchanged `context`, empty result.
749 Override in subclasses.
751 Parameter `context`: application-defined storage.
752 """
753 return context, []
755 def eof(self, context):
756 """
757 Handle end-of-file. Return empty result.
759 Override in subclasses.
761 Parameter `context`: application-defined storage.
762 """
763 return []
765 def nop(self, match, context, next_state):
766 """
767 A "do nothing" transition method.
769 Return unchanged `context` & `next_state`, empty result. Useful for
770 simple state changes (actionless transitions).
771 """
772 return context, next_state, []
775class StateMachineWS(StateMachine):
777 """
778 `StateMachine` subclass specialized for whitespace recognition.
780 There are three methods provided for extracting indented text blocks:
782 - `get_indented()`: use when the indent is unknown.
783 - `get_known_indented()`: use when the indent is known for all lines.
784 - `get_first_known_indented()`: use when only the first line's indent is
785 known.
786 """
788 def get_indented(self, until_blank=False, strip_indent=True):
789 """
790 Return a block of indented lines of text, and info.
792 Extract an indented block where the indent is unknown for all lines.
794 :Parameters:
795 - `until_blank`: Stop collecting at the first blank line if true.
796 - `strip_indent`: Strip common leading indent if true (default).
798 :Return:
799 - the indented block (a list of lines of text),
800 - its indent,
801 - its first line offset from BOF, and
802 - whether or not it finished with a blank line.
803 """
804 offset = self.abs_line_offset()
805 indented, indent, blank_finish = self.input_lines.get_indented(
806 self.line_offset, until_blank, strip_indent)
807 if indented:
808 self.next_line(len(indented) - 1) # advance to last indented line
809 while indented and not indented[0].strip():
810 indented.trim_start()
811 offset += 1
812 return indented, indent, offset, blank_finish
814 def get_known_indented(self, indent, until_blank=False, strip_indent=True):
815 """
816 Return an indented block and info.
818 Extract an indented block where the indent is known for all lines.
819 Starting with the current line, extract the entire text block with at
820 least `indent` indentation (which must be whitespace, except for the
821 first line).
823 :Parameters:
824 - `indent`: The number of indent columns/characters.
825 - `until_blank`: Stop collecting at the first blank line if true.
826 - `strip_indent`: Strip `indent` characters of indentation if true
827 (default).
829 :Return:
830 - the indented block,
831 - its first line offset from BOF, and
832 - whether or not it finished with a blank line.
833 """
834 offset = self.abs_line_offset()
835 indented, indent, blank_finish = self.input_lines.get_indented(
836 self.line_offset, until_blank, strip_indent,
837 block_indent=indent)
838 self.next_line(len(indented) - 1) # advance to last indented line
839 while indented and not indented[0].strip():
840 indented.trim_start()
841 offset += 1
842 return indented, offset, blank_finish
844 def get_first_known_indented(self, indent, until_blank=False,
845 strip_indent=True, strip_top=True):
846 """
847 Return an indented block and info.
849 Extract an indented block where the indent is known for the first line
850 and unknown for all other lines.
852 :Parameters:
853 - `indent`: The first line's indent (# of columns/characters).
854 - `until_blank`: Stop collecting at the first blank line if true
855 (1).
856 - `strip_indent`: Strip `indent` characters of indentation if true
857 (1, default).
858 - `strip_top`: Strip blank lines from the beginning of the block.
860 :Return:
861 - the indented block,
862 - its indent,
863 - its first line offset from BOF, and
864 - whether or not it finished with a blank line.
865 """
866 offset = self.abs_line_offset()
867 indented, indent, blank_finish = self.input_lines.get_indented(
868 self.line_offset, until_blank, strip_indent,
869 first_indent=indent)
870 self.next_line(len(indented) - 1) # advance to last indented line
871 if strip_top:
872 while indented and not indented[0].strip():
873 indented.trim_start()
874 offset += 1
875 return indented, indent, offset, blank_finish
878class StateWS(State):
880 """
881 State superclass specialized for whitespace (blank lines & indents).
883 Use this class with `StateMachineWS`. The transitions 'blank' (for blank
884 lines) and 'indent' (for indented text blocks) are added automatically,
885 before any other transitions. The transition method `blank()` handles
886 blank lines and `indent()` handles nested indented blocks. Indented
887 blocks trigger a new state machine to be created by `indent()` and run.
888 The class of the state machine to be created is in `indent_sm`, and the
889 constructor keyword arguments are in the dictionary `indent_sm_kwargs`.
891 The methods `known_indent()` and `firstknown_indent()` are provided for
892 indented blocks where the indent (all lines' and first line's only,
893 respectively) is known to the transition method, along with the attributes
894 `known_indent_sm` and `known_indent_sm_kwargs`. Neither transition method
895 is triggered automatically.
896 """
898 indent_sm = None
899 """
900 The `StateMachine` class handling indented text blocks.
902 If left as ``None``, `indent_sm` defaults to the value of
903 `State.nested_sm`. Override it in subclasses to avoid the default.
904 """
906 indent_sm_kwargs = None
907 """
908 Keyword arguments dictionary, passed to the `indent_sm` constructor.
910 If left as ``None``, `indent_sm_kwargs` defaults to the value of
911 `State.nested_sm_kwargs`. Override it in subclasses to avoid the default.
912 """
914 known_indent_sm = None
915 """
916 The `StateMachine` class handling known-indented text blocks.
918 If left as ``None``, `known_indent_sm` defaults to the value of
919 `indent_sm`. Override it in subclasses to avoid the default.
920 """
922 known_indent_sm_kwargs = None
923 """
924 Keyword arguments dictionary, passed to the `known_indent_sm` constructor.
926 If left as ``None``, `known_indent_sm_kwargs` defaults to the value of
927 `indent_sm_kwargs`. Override it in subclasses to avoid the default.
928 """
930 ws_patterns = {'blank': re.compile(' *$'),
931 'indent': re.compile(' +')}
932 """Patterns for default whitespace transitions. May be overridden in
933 subclasses."""
935 ws_initial_transitions = ('blank', 'indent')
936 """Default initial whitespace transitions, added before those listed in
937 `State.initial_transitions`. May be overridden in subclasses."""
939 def __init__(self, state_machine, debug=False) -> None:
940 """
941 Initialize a `StateSM` object; extends `State.__init__()`.
943 Check for indent state machine attributes, set defaults if not set.
944 """
945 State.__init__(self, state_machine, debug)
946 if self.indent_sm is None:
947 self.indent_sm = self.nested_sm
948 if self.indent_sm_kwargs is None:
949 self.indent_sm_kwargs = self.nested_sm_kwargs
950 if self.known_indent_sm is None:
951 self.known_indent_sm = self.indent_sm
952 if self.known_indent_sm_kwargs is None:
953 self.known_indent_sm_kwargs = self.indent_sm_kwargs
955 def add_initial_transitions(self) -> None:
956 """
957 Add whitespace-specific transitions before those defined in subclass.
959 Extends `State.add_initial_transitions()`.
960 """
961 State.add_initial_transitions(self)
962 if self.patterns is None:
963 self.patterns = {}
964 self.patterns.update(self.ws_patterns)
965 names, transitions = self.make_transitions(
966 self.ws_initial_transitions)
967 self.add_transitions(names, transitions)
969 def blank(self, match, context, next_state):
970 """Handle blank lines. Does nothing. Override in subclasses."""
971 return self.nop(match, context, next_state)
973 def indent(self, match, context, next_state):
974 """
975 Handle an indented text block. Extend or override in subclasses.
977 Recursively run the registered state machine for indented blocks
978 (`self.indent_sm`).
979 """
980 (indented, indent, line_offset, blank_finish
981 ) = self.state_machine.get_indented()
982 sm = self.indent_sm(debug=self.debug, **self.indent_sm_kwargs)
983 results = sm.run(indented, input_offset=line_offset)
984 return context, next_state, results
986 def known_indent(self, match, context, next_state):
987 """
988 Handle a known-indent text block. Extend or override in subclasses.
990 Recursively run the registered state machine for known-indent indented
991 blocks (`self.known_indent_sm`). The indent is the length of the
992 match, ``match.end()``.
993 """
994 (indented, line_offset, blank_finish
995 ) = self.state_machine.get_known_indented(match.end())
996 sm = self.known_indent_sm(debug=self.debug,
997 **self.known_indent_sm_kwargs)
998 results = sm.run(indented, input_offset=line_offset)
999 return context, next_state, results
1001 def first_known_indent(self, match, context, next_state):
1002 """
1003 Handle an indented text block (first line's indent known).
1005 Extend or override in subclasses.
1007 Recursively run the registered state machine for known-indent indented
1008 blocks (`self.known_indent_sm`). The indent is the length of the
1009 match, ``match.end()``.
1010 """
1011 (indented, line_offset, blank_finish
1012 ) = self.state_machine.get_first_known_indented(match.end())
1013 sm = self.known_indent_sm(debug=self.debug,
1014 **self.known_indent_sm_kwargs)
1015 results = sm.run(indented, input_offset=line_offset)
1016 return context, next_state, results
1019class _SearchOverride:
1021 """
1022 Mix-in class to override `StateMachine` regular expression behavior.
1024 Changes regular expression matching, from the default `re.match()`
1025 (succeeds only if the pattern matches at the start of `self.line`) to
1026 `re.search()` (succeeds if the pattern matches anywhere in `self.line`).
1027 When subclassing a `StateMachine`, list this class **first** in the
1028 inheritance list of the class definition.
1029 """
1031 def match(self, pattern):
1032 """
1033 Return the result of a regular expression search.
1035 Overrides `StateMachine.match()`.
1037 Parameter `pattern`: `re` compiled regular expression.
1038 """
1039 return pattern.search(self.line)
1042class SearchStateMachine(_SearchOverride, StateMachine):
1043 """`StateMachine` which uses `re.search()` instead of `re.match()`."""
1046class SearchStateMachineWS(_SearchOverride, StateMachineWS):
1047 """`StateMachineWS` which uses `re.search()` instead of `re.match()`."""
1050class ViewList:
1052 """
1053 List with extended functionality: slices of ViewList objects are child
1054 lists, linked to their parents. Changes made to a child list also affect
1055 the parent list. A child list is effectively a "view" (in the SQL sense)
1056 of the parent list. Changes to parent lists, however, do *not* affect
1057 active child lists. If a parent list is changed, any active child lists
1058 should be recreated.
1060 The start and end of the slice can be trimmed using the `trim_start()` and
1061 `trim_end()` methods, without affecting the parent list. The link between
1062 child and parent lists can be broken by calling `disconnect()` on the
1063 child list.
1065 Also, ViewList objects keep track of the source & offset of each item.
1066 This information is accessible via the `source()`, `offset()`, and
1067 `info()` methods.
1068 """
1070 def __init__(self, initlist=None, source=None, items=None,
1071 parent=None, parent_offset=None) -> None:
1072 self.data = []
1073 """The actual list of data, flattened from various sources."""
1075 self.items = []
1076 """A list of (source, offset) pairs, same length as `self.data`: the
1077 source of each line and the offset of each line from the beginning of
1078 its source."""
1080 self.parent = parent
1081 """The parent list."""
1083 self.parent_offset = parent_offset
1084 """Offset of this list from the beginning of the parent list."""
1086 if isinstance(initlist, ViewList):
1087 self.data = initlist.data[:]
1088 self.items = initlist.items[:]
1089 elif initlist is not None:
1090 self.data = list(initlist)
1091 if items:
1092 self.items = items
1093 else:
1094 self.items = [(source, i) for i in range(len(initlist))]
1095 assert len(self.data) == len(self.items), 'data mismatch'
1097 def __str__(self) -> str:
1098 return str(self.data)
1100 def __repr__(self) -> str:
1101 return f'{self.__class__.__name__}({self.data}, items={self.items})'
1103 def __lt__(self, other):
1104 return self.data < self.__cast(other)
1106 def __le__(self, other):
1107 return self.data <= self.__cast(other)
1109 def __eq__(self, other):
1110 return self.data == self.__cast(other)
1112 def __ne__(self, other):
1113 return self.data != self.__cast(other)
1115 def __gt__(self, other):
1116 return self.data > self.__cast(other)
1118 def __ge__(self, other):
1119 return self.data >= self.__cast(other)
1121 def __cast(self, other):
1122 if isinstance(other, ViewList):
1123 return other.data
1124 else:
1125 return other
1127 def __contains__(self, item) -> bool:
1128 return item in self.data
1130 def __len__(self) -> int:
1131 return len(self.data)
1133 # The __getitem__()/__setitem__() methods check whether the index
1134 # is a slice first, since indexing a native list with a slice object
1135 # just works.
1137 def __getitem__(self, i):
1138 if isinstance(i, slice):
1139 assert i.step in (None, 1), 'cannot handle slice with stride'
1140 return self.__class__(self.data[i.start:i.stop],
1141 items=self.items[i.start:i.stop],
1142 parent=self, parent_offset=i.start or 0)
1143 else:
1144 return self.data[i]
1146 def __setitem__(self, i, item) -> None:
1147 if isinstance(i, slice):
1148 assert i.step in (None, 1), 'cannot handle slice with stride'
1149 if not isinstance(item, ViewList):
1150 raise TypeError('assigning non-ViewList to ViewList slice')
1151 self.data[i.start:i.stop] = item.data
1152 self.items[i.start:i.stop] = item.items
1153 assert len(self.data) == len(self.items), 'data mismatch'
1154 if self.parent:
1155 k = (i.start or 0) + self.parent_offset
1156 n = (i.stop or len(self)) + self.parent_offset
1157 self.parent[k:n] = item
1158 else:
1159 self.data[i] = item
1160 if self.parent:
1161 self.parent[i + self.parent_offset] = item
1163 def __delitem__(self, i) -> None:
1164 try:
1165 del self.data[i]
1166 del self.items[i]
1167 if self.parent:
1168 del self.parent[i + self.parent_offset]
1169 except TypeError:
1170 assert i.step is None, 'cannot handle slice with stride'
1171 del self.data[i.start:i.stop]
1172 del self.items[i.start:i.stop]
1173 if self.parent:
1174 k = (i.start or 0) + self.parent_offset
1175 n = (i.stop or len(self)) + self.parent_offset
1176 del self.parent[k:n]
1178 def __add__(self, other):
1179 if isinstance(other, ViewList):
1180 return self.__class__(self.data + other.data,
1181 items=(self.items + other.items))
1182 else:
1183 raise TypeError('adding non-ViewList to a ViewList')
1185 def __radd__(self, other):
1186 if isinstance(other, ViewList):
1187 return self.__class__(other.data + self.data,
1188 items=(other.items + self.items))
1189 else:
1190 raise TypeError('adding ViewList to a non-ViewList')
1192 def __iadd__(self, other):
1193 if isinstance(other, ViewList):
1194 self.data += other.data
1195 else:
1196 raise TypeError('argument to += must be a ViewList')
1197 return self
1199 def __mul__(self, n):
1200 return self.__class__(self.data * n, items=(self.items * n))
1202 __rmul__ = __mul__
1204 def __imul__(self, n):
1205 self.data *= n
1206 self.items *= n
1207 return self
1209 def extend(self, other):
1210 if not isinstance(other, ViewList):
1211 raise TypeError('extending a ViewList with a non-ViewList')
1212 if self.parent:
1213 self.parent.insert(len(self.data) + self.parent_offset, other)
1214 self.data.extend(other.data)
1215 self.items.extend(other.items)
1217 def append(self, item, source=None, offset=0) -> None:
1218 if source is None:
1219 self.extend(item)
1220 else:
1221 if self.parent:
1222 self.parent.insert(len(self.data) + self.parent_offset, item,
1223 source, offset)
1224 self.data.append(item)
1225 self.items.append((source, offset))
1227 def insert(self, i, item, source=None, offset=0):
1228 if source is None:
1229 if not isinstance(item, ViewList):
1230 raise TypeError('inserting non-ViewList with no source given')
1231 self.data[i:i] = item.data
1232 self.items[i:i] = item.items
1233 if self.parent:
1234 index = (len(self.data) + i) % len(self.data)
1235 self.parent.insert(index + self.parent_offset, item)
1236 else:
1237 self.data.insert(i, item)
1238 self.items.insert(i, (source, offset))
1239 if self.parent:
1240 index = (len(self.data) + i) % len(self.data)
1241 self.parent.insert(index + self.parent_offset, item,
1242 source, offset)
1244 def pop(self, i=-1):
1245 if self.parent:
1246 index = (len(self.data) + i) % len(self.data)
1247 self.parent.pop(index + self.parent_offset)
1248 self.items.pop(i)
1249 return self.data.pop(i)
1251 def trim_start(self, n=1):
1252 """
1253 Remove items from the start of the list, without touching the parent.
1254 """
1255 if n > len(self.data):
1256 raise IndexError("Size of trim too large; can't trim %s items "
1257 "from a list of size %s." % (n, len(self.data)))
1258 elif n < 0:
1259 raise IndexError('Trim size must be >= 0.')
1260 del self.data[:n]
1261 del self.items[:n]
1262 if self.parent:
1263 self.parent_offset += n
1265 def trim_end(self, n=1):
1266 """
1267 Remove items from the end of the list, without touching the parent.
1268 """
1269 if n > len(self.data):
1270 raise IndexError("Size of trim too large; can't trim %s items "
1271 "from a list of size %s." % (n, len(self.data)))
1272 elif n < 0:
1273 raise IndexError('Trim size must be >= 0.')
1274 del self.data[-n:]
1275 del self.items[-n:]
1277 def remove(self, item) -> None:
1278 index = self.index(item)
1279 del self[index]
1281 def count(self, item):
1282 return self.data.count(item)
1284 def index(self, item):
1285 return self.data.index(item)
1287 def reverse(self) -> None:
1288 self.data.reverse()
1289 self.items.reverse()
1290 self.parent = None
1292 def sort(self, *args) -> None:
1293 tmp = sorted(zip(self.data, self.items), *args)
1294 self.data = [entry[0] for entry in tmp]
1295 self.items = [entry[1] for entry in tmp]
1296 self.parent = None
1298 def info(self, i):
1299 """Return source & offset for index `i`."""
1300 try:
1301 return self.items[i]
1302 except IndexError:
1303 if i == len(self.data): # Just past the end
1304 return self.items[i - 1][0], None
1305 else:
1306 raise
1308 def source(self, i):
1309 """Return source for index `i`."""
1310 return self.info(i)[0]
1312 def offset(self, i):
1313 """Return offset for index `i`."""
1314 return self.info(i)[1]
1316 def disconnect(self) -> None:
1317 """Break link between this list and parent list."""
1318 self.parent = None
1320 def xitems(self):
1321 """Return iterator yielding (source, offset, value) tuples."""
1322 for (value, (source, offset)) in zip(self.data, self.items):
1323 yield source, offset, value
1325 def pprint(self) -> None:
1326 """Print the list in `grep` format (`source:offset:value` lines)"""
1327 for line in self.xitems():
1328 print("%s:%d:%s" % line)
1331class StringList(ViewList):
1333 """A `ViewList` with string-specific methods."""
1335 def trim_left(self, length, start=0, end=sys.maxsize) -> None:
1336 """
1337 Trim `length` characters off the beginning of each item, in-place,
1338 from index `start` to `end`. No whitespace-checking is done on the
1339 trimmed text. Does not affect slice parent.
1340 """
1341 self.data[start:end] = [line[length:]
1342 for line in self.data[start:end]]
1344 def get_text_block(self, start, flush_left=False):
1345 """
1346 Return a contiguous block of text.
1348 If `flush_left` is true, raise `UnexpectedIndentationError` if an
1349 indented line is encountered before the text block ends (with a blank
1350 line).
1351 """
1352 end = start
1353 last = len(self.data)
1354 while end < last:
1355 line = self.data[end]
1356 if not line.strip():
1357 break
1358 if flush_left and (line[0] == ' '):
1359 source, offset = self.info(end)
1360 raise UnexpectedIndentationError(self[start:end], source,
1361 offset + 1)
1362 end += 1
1363 return self[start:end]
1365 def get_indented(self, start=0, until_blank=False, strip_indent=True,
1366 block_indent=None, first_indent=None):
1367 """
1368 Extract and return a StringList of indented lines of text.
1370 Collect all lines with indentation, determine the minimum indentation,
1371 remove the minimum indentation from all indented lines (unless
1372 `strip_indent` is false), and return them. All lines up to but not
1373 including the first unindented line will be returned.
1375 :Parameters:
1376 - `start`: The index of the first line to examine.
1377 - `until_blank`: Stop collecting at the first blank line if true.
1378 - `strip_indent`: Strip common leading indent if true (default).
1379 - `block_indent`: The indent of the entire block, if known.
1380 - `first_indent`: The indent of the first line, if known.
1382 :Return:
1383 - a StringList of indented lines with minimum indent removed;
1384 - the amount of the indent;
1385 - a boolean: did the indented block finish with a blank line or EOF?
1386 """
1387 indent = block_indent # start with None if unknown
1388 end = start
1389 if block_indent is not None and first_indent is None:
1390 first_indent = block_indent
1391 if first_indent is not None:
1392 end += 1
1393 last = len(self.data)
1394 while end < last:
1395 line = self.data[end]
1396 if line and (line[0] != ' '
1397 or (block_indent is not None
1398 and line[:block_indent].strip())):
1399 # Line not indented or insufficiently indented.
1400 # Block finished properly iff the last indented line blank:
1401 blank_finish = ((end > start)
1402 and not self.data[end - 1].strip())
1403 break
1404 stripped = line.lstrip()
1405 if not stripped: # blank line
1406 if until_blank:
1407 blank_finish = 1
1408 break
1409 elif block_indent is None:
1410 line_indent = len(line) - len(stripped)
1411 if indent is None:
1412 indent = line_indent
1413 else:
1414 indent = min(indent, line_indent)
1415 end += 1
1416 else:
1417 blank_finish = 1 # block ends at end of lines
1418 block = self[start:end]
1419 if first_indent is not None and block:
1420 block.data[0] = block.data[0][first_indent:]
1421 if indent and strip_indent:
1422 block.trim_left(indent, start=(first_indent is not None))
1423 return block, indent or 0, blank_finish
1425 def get_2D_block(self, top, left, bottom, right, strip_indent=True):
1426 block = self[top:bottom]
1427 indent = right
1428 for i in range(len(block.data)):
1429 # get slice from line, care for combining characters
1430 ci = utils.column_indices(block.data[i])
1431 try:
1432 left = ci[left]
1433 except IndexError:
1434 left += len(block.data[i]) - len(ci)
1435 try:
1436 right = ci[right]
1437 except IndexError:
1438 right += len(block.data[i]) - len(ci)
1439 block.data[i] = line = block.data[i][left:right].rstrip()
1440 if line:
1441 indent = min(indent, len(line) - len(line.lstrip()))
1442 if strip_indent and 0 < indent < right:
1443 block.data = [line[indent:] for line in block.data]
1444 return block
1446 def pad_double_width(self, pad_char) -> None:
1447 """Pad all double-width characters in `self` appending `pad_char`.
1449 For East Asian language support.
1450 """
1451 for i in range(len(self.data)):
1452 line = self.data[i]
1453 if isinstance(line, str):
1454 new = []
1455 for char in line:
1456 new.append(char)
1457 if east_asian_width(char) in 'WF': # Wide & Full-width
1458 new.append(pad_char)
1459 self.data[i] = ''.join(new)
1461 def replace(self, old, new) -> None:
1462 """Replace all occurrences of substring `old` with `new`."""
1463 for i in range(len(self.data)):
1464 self.data[i] = self.data[i].replace(old, new)
1467class StateMachineError(Exception): pass
1468class UnknownStateError(StateMachineError): pass
1469class DuplicateStateError(StateMachineError): pass
1470class UnknownTransitionError(StateMachineError): pass
1471class DuplicateTransitionError(StateMachineError): pass
1472class TransitionPatternNotFound(StateMachineError): pass
1473class TransitionMethodNotFound(StateMachineError): pass
1474class UnexpectedIndentationError(StateMachineError): pass
1477class TransitionCorrection(Exception):
1479 """
1480 Raise from within a transition method to switch to another transition.
1482 Raise with one argument, the new transition name.
1483 """
1486class StateCorrection(Exception):
1488 """
1489 Raise from within a transition method to switch to another state.
1491 Raise with one or two arguments: new state name, and an optional new
1492 transition name.
1493 """
1496def string2lines(astring, tab_width=8, convert_whitespace=False,
1497 whitespace=re.compile('[\v\f]')):
1498 """
1499 Return a list of one-line strings with tabs expanded, no newlines, and
1500 trailing whitespace stripped.
1502 Each tab is expanded with between 1 and `tab_width` spaces, so that the
1503 next character's index becomes a multiple of `tab_width` (8 by default).
1505 Parameters:
1507 - `astring`: a multi-line string.
1508 - `tab_width`: the number of columns between tab stops.
1509 - `convert_whitespace`: convert form feeds and vertical tabs to spaces?
1510 - `whitespace`: pattern object with the to-be-converted
1511 whitespace characters (default [\\v\\f]).
1512 """
1513 if convert_whitespace:
1514 astring = whitespace.sub(' ', astring)
1515 return [s.expandtabs(tab_width).rstrip() for s in astring.splitlines()]
1518def _exception_data():
1519 """
1520 Return exception information:
1522 - the exception's class name;
1523 - the exception object;
1524 - the name of the file containing the offending code;
1525 - the line number of the offending code;
1526 - the function name of the offending code.
1527 """
1528 typ, value, traceback = sys.exc_info()
1529 while traceback.tb_next:
1530 traceback = traceback.tb_next
1531 code = traceback.tb_frame.f_code
1532 return (typ.__name__, value, code.co_filename, traceback.tb_lineno,
1533 code.co_name)