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"""
108from __future__ import annotations
110__docformat__ = 'restructuredtext'
112import sys
113import re
114from unicodedata import east_asian_width
116from docutils import utils
119class StateMachine:
121 """
122 A finite state machine for text filters using regular expressions.
124 The input is provided in the form of a list of one-line strings (no
125 newlines). States are subclasses of the `State` class. Transitions consist
126 of regular expression patterns and transition methods, and are defined in
127 each state.
129 The state machine is started with the `run()` method, which returns the
130 results of processing in a list.
131 """
133 def __init__(self, state_classes, initial_state, debug=False) -> None:
134 """
135 Initialize a `StateMachine` object; add state objects.
137 Parameters:
139 - `state_classes`: a list of `State` (sub)classes.
140 - `initial_state`: a string, the class name of the initial state.
141 - `debug`: a boolean; produce verbose output if true (nonzero).
142 """
144 self.input_lines = None
145 """`StringList` of input lines (without newlines).
146 Filled by `self.run()`."""
148 self.input_offset = 0
149 """Offset of `self.input_lines` from the beginning of the file."""
151 self.line = None
152 """Current input line."""
154 self.line_offset = -1
155 """Current input line offset from beginning of `self.input_lines`."""
157 self.debug = debug
158 """Debugging mode on/off."""
160 self.initial_state = initial_state
161 """The name of the initial state (key to `self.states`)."""
163 self.current_state = initial_state
164 """The name of the current state (key to `self.states`)."""
166 self.states = {}
167 """Mapping of {state_name: State_object}."""
169 self.add_states(state_classes)
171 self.observers = []
172 """List of bound methods or functions to call whenever the current
173 line changes. Observers are called with one argument, ``self``.
174 Cleared at the end of `run()`."""
176 def unlink(self) -> None:
177 """Remove circular references to objects no longer required."""
178 for state in self.states.values():
179 state.unlink()
180 self.states = None
182 def run(self, input_lines, input_offset=0, context=None,
183 input_source=None, initial_state=None):
184 """
185 Run the state machine on `input_lines`. Return results (a list).
187 Reset `self.line_offset` and `self.current_state`. Run the
188 beginning-of-file transition. Input one line at a time and check for a
189 matching transition. If a match is found, call the transition method
190 and possibly change the state. Store the context returned by the
191 transition method to be passed on to the next transition matched.
192 Accumulate the results returned by the transition methods in a list.
193 Run the end-of-file transition. Finally, return the accumulated
194 results.
196 Parameters:
198 - `input_lines`: a list of strings without newlines, or `StringList`.
199 - `input_offset`: the line offset of `input_lines` from the beginning
200 of the file.
201 - `context`: application-specific storage.
202 - `input_source`: name or path of source of `input_lines`.
203 - `initial_state`: name of initial state.
204 """
205 self.runtime_init()
206 if isinstance(input_lines, StringList):
207 self.input_lines = input_lines
208 else:
209 self.input_lines = StringList(input_lines, source=input_source)
210 self.input_offset = input_offset
211 self.line_offset = -1
212 self.current_state = initial_state or self.initial_state
213 if self.debug:
214 print('\nStateMachine.run: input_lines (line_offset=%s):\n| %s'
215 % (self.line_offset, '\n| '.join(self.input_lines)),
216 file=sys.stderr)
217 transitions = None
218 results = []
219 state = self.get_state()
220 try:
221 if self.debug:
222 print('\nStateMachine.run: bof transition', file=sys.stderr)
223 context, result = state.bof(context)
224 results.extend(result)
225 while True:
226 try:
227 try:
228 self.next_line()
229 if self.debug:
230 source, offset = self.input_lines.info(
231 self.line_offset)
232 print(f'\nStateMachine.run: line '
233 f'(source={source!r}, offset={offset!r}):\n'
234 f'| {self.line}', file=sys.stderr)
235 context, next_state, result = self.check_line(
236 context, state, transitions)
237 except EOFError:
238 if self.debug:
239 print('\nStateMachine.run: %s.eof transition'
240 % state.__class__.__name__, file=sys.stderr)
241 result = state.eof(context)
242 results.extend(result)
243 break
244 else:
245 results.extend(result)
246 except TransitionCorrection as exception:
247 self.previous_line() # back up for another try
248 transitions = (exception.args[0],)
249 if self.debug:
250 print('\nStateMachine.run: TransitionCorrection to '
251 f'state "{state.__class__.__name__}", '
252 f'transition {transitions[0]}.',
253 file=sys.stderr)
254 continue
255 except StateCorrection as exception:
256 self.previous_line() # back up for another try
257 next_state = exception.args[0]
258 if len(exception.args) == 1:
259 transitions = None
260 else:
261 transitions = (exception.args[1],)
262 if self.debug:
263 print('\nStateMachine.run: StateCorrection to state '
264 f'"{next_state}", transition {transitions[0]}.',
265 file=sys.stderr)
266 else:
267 transitions = None
268 state = self.get_state(next_state)
269 except: # NoQA: E722 (catchall)
270 if self.debug:
271 self.error()
272 raise
273 self.observers = []
274 return results
276 def get_state(self, next_state=None):
277 """
278 Return current state object; set it first if `next_state` given.
280 Parameter `next_state`: a string, the name of the next state.
282 Exception: `UnknownStateError` raised if `next_state` unknown.
283 """
284 if next_state:
285 if self.debug and next_state != self.current_state:
286 print('\nStateMachine.get_state: Changing state from '
287 '"%s" to "%s" (input line %s).'
288 % (self.current_state, next_state,
289 self.abs_line_number()), file=sys.stderr)
290 self.current_state = next_state
291 try:
292 return self.states[self.current_state]
293 except KeyError:
294 raise UnknownStateError(self.current_state)
296 def next_line(self, n=1):
297 """Load `self.line` with the `n`'th next line and return it."""
298 try:
299 try:
300 self.line_offset += n
301 self.line = self.input_lines[self.line_offset]
302 except IndexError:
303 self.line = None
304 raise EOFError
305 return self.line
306 finally:
307 self.notify_observers()
309 def is_next_line_blank(self):
310 """Return True if the next line is blank or non-existent."""
311 try:
312 return not self.input_lines[self.line_offset + 1].strip()
313 except IndexError:
314 return 1
316 def at_eof(self):
317 """Return 1 if the input is at or past end-of-file."""
318 return self.line_offset >= len(self.input_lines) - 1
320 def at_bof(self):
321 """Return 1 if the input is at or before beginning-of-file."""
322 return self.line_offset <= 0
324 def previous_line(self, n=1):
325 """Load `self.line` with the `n`'th previous line and return it."""
326 self.line_offset -= n
327 if self.line_offset < 0:
328 self.line = None
329 else:
330 self.line = self.input_lines[self.line_offset]
331 self.notify_observers()
332 return self.line
334 def goto_line(self, line_offset):
335 """Jump to absolute line offset `line_offset`, load and return it."""
336 try:
337 try:
338 self.line_offset = line_offset - self.input_offset
339 self.line = self.input_lines[self.line_offset]
340 except IndexError:
341 self.line = None
342 raise EOFError
343 return self.line
344 finally:
345 self.notify_observers()
347 def get_source(self, line_offset):
348 """Return source of line at absolute line offset `line_offset`."""
349 return self.input_lines.source(line_offset - self.input_offset)
351 def abs_line_offset(self):
352 """Return line offset of current line, from beginning of file."""
353 return self.line_offset + self.input_offset
355 def abs_line_number(self):
356 """Return line number of current line (counting from 1)."""
357 return self.line_offset + self.input_offset + 1
359 def get_source_and_line(self, lineno=None):
360 """Return (source, line) tuple for current or given line number.
362 Looks up the source and line number in the `self.input_lines`
363 StringList instance to count for included source files.
365 If the optional argument `lineno` is given, convert it from an
366 absolute line number to the corresponding (source, line) pair.
367 """
368 if lineno is None:
369 offset = self.line_offset
370 else:
371 offset = lineno - self.input_offset - 1
372 try:
373 src, srcoffset = self.input_lines.info(offset)
374 srcline = srcoffset + 1
375 except TypeError:
376 # line is None if index is "Just past the end"
377 src, srcline = self.get_source_and_line(offset + self.input_offset)
378 return src, srcline + 1
379 except IndexError: # `offset` is off the list
380 src, srcline = None, None
381 # raise AssertionError('cannot find line %d in %s lines' %
382 # (offset, len(self.input_lines)))
383 # # list(self.input_lines.lines())))
384 return src, srcline
386 def insert_input(self, input_lines, source) -> None:
387 self.input_lines.insert(self.line_offset + 1, '',
388 source='internal padding after '+source,
389 offset=len(input_lines))
390 self.input_lines.insert(self.line_offset + 1, '',
391 source='internal padding before '+source,
392 offset=-1)
393 self.input_lines.insert(self.line_offset + 2,
394 StringList(input_lines, source))
396 def get_text_block(self, flush_left=False):
397 """
398 Return a contiguous block of text.
400 If `flush_left` is true, raise `UnexpectedIndentationError` if an
401 indented line is encountered before the text block ends (with a blank
402 line).
403 """
404 try:
405 block = self.input_lines.get_text_block(self.line_offset,
406 flush_left)
407 self.next_line(len(block) - 1)
408 return block
409 except UnexpectedIndentationError as err:
410 block = err.args[0]
411 self.next_line(len(block) - 1) # advance to last line of block
412 raise
414 def check_line(self, context, state, transitions=None):
415 """
416 Examine one line of input for a transition match & execute its method.
418 Parameters:
420 - `context`: application-dependent storage.
421 - `state`: a `State` object, the current state.
422 - `transitions`: an optional ordered list of transition names to try,
423 instead of ``state.transition_order``.
425 Return the values returned by the transition method:
427 - context: possibly modified from the parameter `context`;
428 - next state name (`State` subclass name);
429 - the result output of the transition, a list.
431 When there is no match, ``state.no_match()`` is called and its return
432 value is returned.
433 """
434 if transitions is None:
435 transitions = state.transition_order
436 if self.debug:
437 print('\nStateMachine.check_line: state="%s", transitions=%r.'
438 % (state.__class__.__name__, transitions), file=sys.stderr)
439 for name in transitions:
440 pattern, method, next_state = state.transitions[name]
441 match = pattern.match(self.line)
442 if match:
443 if self.debug:
444 print('\nStateMachine.check_line: Matched transition '
445 f'"{name}" in state "{state.__class__.__name__}".',
446 file=sys.stderr)
447 return method(match, context, next_state)
448 else:
449 if self.debug:
450 print('\nStateMachine.check_line: No match in state "%s".'
451 % state.__class__.__name__, file=sys.stderr)
452 return state.no_match(context, transitions)
454 def add_state(self, state_class):
455 """
456 Initialize & add a `state_class` (`State` subclass) object.
458 Exception: `DuplicateStateError` raised if `state_class` was already
459 added.
460 """
461 statename = state_class.__name__
462 if statename in self.states:
463 raise DuplicateStateError(statename)
464 self.states[statename] = state_class(self, self.debug)
466 def add_states(self, state_classes) -> None:
467 """
468 Add `state_classes` (a list of `State` subclasses).
469 """
470 for state_class in state_classes:
471 self.add_state(state_class)
473 def runtime_init(self) -> None:
474 """
475 Initialize `self.states`.
476 """
477 for state in self.states.values():
478 state.runtime_init()
480 def error(self) -> None:
481 """Report error details."""
482 type_name, value, module, line, function = _exception_data()
483 print('%s: %s' % (type_name, value), file=sys.stderr)
484 print('input line %s' % (self.abs_line_number()), file=sys.stderr)
485 print('module %s, line %s, function %s' % (module, line, function),
486 file=sys.stderr)
488 def attach_observer(self, observer) -> None:
489 """
490 The `observer` parameter is a function or bound method which takes two
491 arguments, the source and offset of the current line.
492 """
493 self.observers.append(observer)
495 def detach_observer(self, observer) -> None:
496 self.observers.remove(observer)
498 def notify_observers(self) -> None:
499 for observer in self.observers:
500 try:
501 info = self.input_lines.info(self.line_offset)
502 except IndexError:
503 info = (None, None)
504 observer(*info)
507class State:
509 """
510 State superclass. Contains a list of transitions, and transition methods.
512 Transition methods all have the same signature. They take 3 parameters:
514 - An `re` match object. ``match.string`` contains the matched input line,
515 ``match.start()`` gives the start index of the match, and
516 ``match.end()`` gives the end index.
517 - A context object, whose meaning is application-defined (initial value
518 ``None``). It can be used to store any information required by the state
519 machine, and the returned context is passed on to the next transition
520 method unchanged.
521 - The name of the next state, a string, taken from the transitions list;
522 normally it is returned unchanged, but it may be altered by the
523 transition method if necessary.
525 Transition methods all return a 3-tuple:
527 - A context object, as (potentially) modified by the transition method.
528 - The next state name (a return value of ``None`` means no state change).
529 - The processing result, a list, which is accumulated by the state
530 machine.
532 Transition methods may raise an `EOFError` to cut processing short.
534 There are two implicit transitions, and corresponding transition methods
535 are defined: `bof()` handles the beginning-of-file, and `eof()` handles
536 the end-of-file. These methods have non-standard signatures and return
537 values. `bof()` returns the initial context and results, and may be used
538 to return a header string, or do any other processing needed. `eof()`
539 should handle any remaining context and wrap things up; it returns the
540 final processing result.
542 Typical applications need only subclass `State` (or a subclass), set the
543 `patterns` and `initial_transitions` class attributes, and provide
544 corresponding transition methods. The default object initialization will
545 take care of constructing the list of transitions.
546 """
548 patterns = None
549 """
550 {Name: pattern} mapping, used by `make_transition()`. Each pattern may
551 be a string or a compiled `re` pattern. Override in subclasses.
552 """
554 initial_transitions = None
555 """
556 A list of transitions to initialize when a `State` is instantiated.
557 Each entry is either a transition name string, or a (transition name, next
558 state name) pair. See `make_transitions()`. Override in subclasses.
559 """
561 nested_sm = None
562 """
563 The `StateMachine` class for handling nested processing.
565 If left as ``None``, `nested_sm` defaults to the class of the state's
566 controlling state machine. Override it in subclasses to avoid the default.
567 """
569 nested_sm_kwargs = None
570 """
571 Keyword arguments dictionary, passed to the `nested_sm` constructor.
573 Two keys must have entries in the dictionary:
575 - Key 'state_classes' must be set to a list of `State` classes.
576 - Key 'initial_state' must be set to the name of the initial state class.
578 If `nested_sm_kwargs` is left as ``None``, 'state_classes' defaults to the
579 class of the current state, and 'initial_state' defaults to the name of
580 the class of the current state. Override in subclasses to avoid the
581 defaults.
582 """
584 def __init__(self, state_machine, debug=False) -> None:
585 """
586 Initialize a `State` object; make & add initial transitions.
588 Parameters:
590 - `statemachine`: the controlling `StateMachine` object.
591 - `debug`: a boolean; produce verbose output if true.
592 """
594 self.transition_order = []
595 """A list of transition names in search order."""
597 self.transitions = {}
598 """
599 A mapping of transition names to 3-tuples containing
600 (compiled_pattern, transition_method, next_state_name). Initialized as
601 an instance attribute dynamically (instead of as a class attribute)
602 because it may make forward references to patterns and methods in this
603 or other classes.
604 """
606 self.add_initial_transitions()
608 self.state_machine = state_machine
609 """A reference to the controlling `StateMachine` object."""
611 self.debug = debug
612 """Debugging mode on/off."""
614 if self.nested_sm is None:
615 self.nested_sm = self.state_machine.__class__
616 if self.nested_sm_kwargs is None:
617 self.nested_sm_kwargs = {'state_classes': [self.__class__],
618 'initial_state': self.__class__.__name__}
620 def runtime_init(self) -> None:
621 """
622 Initialize this `State` before running the state machine; called from
623 `self.state_machine.run()`.
624 """
626 def unlink(self) -> None:
627 """Remove circular references to objects no longer required."""
628 self.state_machine = None
630 def add_initial_transitions(self) -> None:
631 """Make and add transitions listed in `self.initial_transitions`."""
632 if self.initial_transitions:
633 names, transitions = self.make_transitions(
634 self.initial_transitions)
635 self.add_transitions(names, transitions)
637 def add_transitions(self, names, transitions):
638 """
639 Add a list of transitions to the start of the transition list.
641 Parameters:
643 - `names`: a list of transition names.
644 - `transitions`: a mapping of names to transition tuples.
646 Exceptions: `DuplicateTransitionError`, `UnknownTransitionError`.
647 """
648 for name in names:
649 if name in self.transitions:
650 raise DuplicateTransitionError(name)
651 if name not in transitions:
652 raise UnknownTransitionError(name)
653 self.transition_order[:0] = names
654 self.transitions.update(transitions)
656 def add_transition(self, name, transition):
657 """
658 Add a transition to the start of the transition list.
660 Parameter `transition`: a ready-made transition 3-tuple.
662 Exception: `DuplicateTransitionError`.
663 """
664 if name in self.transitions:
665 raise DuplicateTransitionError(name)
666 self.transition_order[:0] = [name]
667 self.transitions[name] = transition
669 def remove_transition(self, name):
670 """
671 Remove a transition by `name`.
673 Exception: `UnknownTransitionError`.
674 """
675 try:
676 del self.transitions[name]
677 self.transition_order.remove(name)
678 except: # NoQA: E722 (catchall)
679 raise UnknownTransitionError(name)
681 def make_transition(self, name, next_state=None):
682 """
683 Make & return a transition tuple based on `name`.
685 This is a convenience function to simplify transition creation.
687 Parameters:
689 - `name`: a string, the name of the transition pattern & method. This
690 `State` object must have a method called '`name`', and a dictionary
691 `self.patterns` containing a key '`name`'.
692 - `next_state`: a string, the name of the next `State` object for this
693 transition. A value of ``None`` (or absent) implies no state change
694 (i.e., continue with the same state).
696 Exceptions: `TransitionPatternNotFound`, `TransitionMethodNotFound`.
697 """
698 if next_state is None:
699 next_state = self.__class__.__name__
700 try:
701 pattern = self.patterns[name]
702 if not hasattr(pattern, 'match'):
703 pattern = self.patterns[name] = re.compile(pattern)
704 except KeyError:
705 raise TransitionPatternNotFound(
706 '%s.patterns[%r]' % (self.__class__.__name__, name))
707 try:
708 method = getattr(self, name)
709 except AttributeError:
710 raise TransitionMethodNotFound(
711 '%s.%s' % (self.__class__.__name__, name))
712 return pattern, method, next_state
714 def make_transitions(self, name_list):
715 """
716 Return a list of transition names and a transition mapping.
718 Parameter `name_list`: a list, where each entry is either a transition
719 name string, or a 1- or 2-tuple (transition name, optional next state
720 name).
721 """
722 names = []
723 transitions = {}
724 for namestate in name_list:
725 if isinstance(namestate, str):
726 transitions[namestate] = self.make_transition(namestate)
727 names.append(namestate)
728 else:
729 transitions[namestate[0]] = self.make_transition(*namestate)
730 names.append(namestate[0])
731 return names, transitions
733 def no_match(self, context, transitions):
734 """
735 Called when there is no match from `StateMachine.check_line()`.
737 Return the same values returned by transition methods:
739 - context: unchanged;
740 - next state name: ``None``;
741 - empty result list.
743 Override in subclasses to catch this event.
744 """
745 return context, None, []
747 def bof(self, context):
748 """
749 Handle beginning-of-file. Return unchanged `context`, empty result.
751 Override in subclasses.
753 Parameter `context`: application-defined storage.
754 """
755 return context, []
757 def eof(self, context):
758 """
759 Handle end-of-file. Return empty result.
761 Override in subclasses.
763 Parameter `context`: application-defined storage.
764 """
765 return []
767 def nop(self, match, context, next_state):
768 """
769 A "do nothing" transition method.
771 Return unchanged `context` & `next_state`, empty result. Useful for
772 simple state changes (actionless transitions).
773 """
774 return context, next_state, []
777class StateMachineWS(StateMachine):
779 """
780 `StateMachine` subclass specialized for whitespace recognition.
782 There are three methods provided for extracting indented text blocks:
784 - `get_indented()`: use when the indent is unknown.
785 - `get_known_indented()`: use when the indent is known for all lines.
786 - `get_first_known_indented()`: use when only the first line's indent is
787 known.
788 """
790 def get_indented(self, until_blank=False, strip_indent=True):
791 """
792 Return a block of indented lines of text, and info.
794 Extract an indented block where the indent is unknown for all lines.
796 :Parameters:
797 - `until_blank`: Stop collecting at the first blank line if true.
798 - `strip_indent`: Strip common leading indent if true (default).
800 :Return:
801 - the indented block (a list of lines of text),
802 - its indent,
803 - its first line offset from BOF, and
804 - whether or not it finished with a blank line.
805 """
806 offset = self.abs_line_offset()
807 indented, indent, blank_finish = self.input_lines.get_indented(
808 self.line_offset, until_blank, strip_indent)
809 if indented:
810 self.next_line(len(indented) - 1) # advance to last indented line
811 while indented and not indented[0].strip():
812 indented.trim_start()
813 offset += 1
814 return indented, indent, offset, blank_finish
816 def get_known_indented(self, indent, until_blank=False, strip_indent=True):
817 """
818 Return an indented block and info.
820 Extract an indented block where the indent is known for all lines.
821 Starting with the current line, extract the entire text block with at
822 least `indent` indentation (which must be whitespace, except for the
823 first line).
825 :Parameters:
826 - `indent`: The number of indent columns/characters.
827 - `until_blank`: Stop collecting at the first blank line if true.
828 - `strip_indent`: Strip `indent` characters of indentation if true
829 (default).
831 :Return:
832 - the indented block,
833 - its first line offset from BOF, and
834 - whether or not it finished with a blank line.
835 """
836 offset = self.abs_line_offset()
837 indented, indent, blank_finish = self.input_lines.get_indented(
838 self.line_offset, until_blank, strip_indent,
839 block_indent=indent)
840 self.next_line(len(indented) - 1) # advance to last indented line
841 while indented and not indented[0].strip():
842 indented.trim_start()
843 offset += 1
844 return indented, offset, blank_finish
846 def get_first_known_indented(self, indent, until_blank=False,
847 strip_indent=True, strip_top=True):
848 """
849 Return an indented block and info.
851 Extract an indented block where the indent is known for the first line
852 and unknown for all other lines.
854 :Parameters:
855 - `indent`: The first line's indent (# of columns/characters).
856 - `until_blank`: Stop collecting at the first blank line if true
857 (1).
858 - `strip_indent`: Strip `indent` characters of indentation if true
859 (1, default).
860 - `strip_top`: Strip blank lines from the beginning of the block.
862 :Return:
863 - the indented block,
864 - its indent,
865 - its first line offset from BOF, and
866 - whether or not it finished with a blank line.
867 """
868 offset = self.abs_line_offset()
869 indented, indent, blank_finish = self.input_lines.get_indented(
870 self.line_offset, until_blank, strip_indent,
871 first_indent=indent)
872 self.next_line(len(indented) - 1) # advance to last indented line
873 if strip_top:
874 while indented and not indented[0].strip():
875 indented.trim_start()
876 offset += 1
877 return indented, indent, offset, blank_finish
880class StateWS(State):
882 """
883 State superclass specialized for whitespace (blank lines & indents).
885 Use this class with `StateMachineWS`. The transitions 'blank' (for blank
886 lines) and 'indent' (for indented text blocks) are added automatically,
887 before any other transitions. The transition method `blank()` handles
888 blank lines and `indent()` handles nested indented blocks. Indented
889 blocks trigger a new state machine to be created by `indent()` and run.
890 The class of the state machine to be created is in `indent_sm`, and the
891 constructor keyword arguments are in the dictionary `indent_sm_kwargs`.
893 The methods `known_indent()` and `firstknown_indent()` are provided for
894 indented blocks where the indent (all lines' and first line's only,
895 respectively) is known to the transition method, along with the attributes
896 `known_indent_sm` and `known_indent_sm_kwargs`. Neither transition method
897 is triggered automatically.
898 """
900 indent_sm = None
901 """
902 The `StateMachine` class handling indented text blocks.
904 If left as ``None``, `indent_sm` defaults to the value of
905 `State.nested_sm`. Override it in subclasses to avoid the default.
906 """
908 indent_sm_kwargs = None
909 """
910 Keyword arguments dictionary, passed to the `indent_sm` constructor.
912 If left as ``None``, `indent_sm_kwargs` defaults to the value of
913 `State.nested_sm_kwargs`. Override it in subclasses to avoid the default.
914 """
916 known_indent_sm = None
917 """
918 The `StateMachine` class handling known-indented text blocks.
920 If left as ``None``, `known_indent_sm` defaults to the value of
921 `indent_sm`. Override it in subclasses to avoid the default.
922 """
924 known_indent_sm_kwargs = None
925 """
926 Keyword arguments dictionary, passed to the `known_indent_sm` constructor.
928 If left as ``None``, `known_indent_sm_kwargs` defaults to the value of
929 `indent_sm_kwargs`. Override it in subclasses to avoid the default.
930 """
932 ws_patterns = {'blank': re.compile(' *$'),
933 'indent': re.compile(' +')}
934 """Patterns for default whitespace transitions. May be overridden in
935 subclasses."""
937 ws_initial_transitions = ('blank', 'indent')
938 """Default initial whitespace transitions, added before those listed in
939 `State.initial_transitions`. May be overridden in subclasses."""
941 def __init__(self, state_machine, debug=False) -> None:
942 """
943 Initialize a `StateSM` object; extends `State.__init__()`.
945 Check for indent state machine attributes, set defaults if not set.
946 """
947 State.__init__(self, state_machine, debug)
948 if self.indent_sm is None:
949 self.indent_sm = self.nested_sm
950 if self.indent_sm_kwargs is None:
951 self.indent_sm_kwargs = self.nested_sm_kwargs
952 if self.known_indent_sm is None:
953 self.known_indent_sm = self.indent_sm
954 if self.known_indent_sm_kwargs is None:
955 self.known_indent_sm_kwargs = self.indent_sm_kwargs
957 def add_initial_transitions(self) -> None:
958 """
959 Add whitespace-specific transitions before those defined in subclass.
961 Extends `State.add_initial_transitions()`.
962 """
963 State.add_initial_transitions(self)
964 if self.patterns is None:
965 self.patterns = {}
966 self.patterns.update(self.ws_patterns)
967 names, transitions = self.make_transitions(
968 self.ws_initial_transitions)
969 self.add_transitions(names, transitions)
971 def blank(self, match, context, next_state):
972 """Handle blank lines. Does nothing. Override in subclasses."""
973 return self.nop(match, context, next_state)
975 def indent(self, match, context, next_state):
976 """
977 Handle an indented text block. Extend or override in subclasses.
979 Recursively run the registered state machine for indented blocks
980 (`self.indent_sm`).
981 """
982 (indented, indent, line_offset, blank_finish
983 ) = self.state_machine.get_indented()
984 sm = self.indent_sm(debug=self.debug, **self.indent_sm_kwargs)
985 results = sm.run(indented, input_offset=line_offset)
986 return context, next_state, results
988 def known_indent(self, match, context, next_state):
989 """
990 Handle a known-indent text block. Extend or override in subclasses.
992 Recursively run the registered state machine for known-indent indented
993 blocks (`self.known_indent_sm`). The indent is the length of the
994 match, ``match.end()``.
995 """
996 (indented, line_offset, blank_finish
997 ) = self.state_machine.get_known_indented(match.end())
998 sm = self.known_indent_sm(debug=self.debug,
999 **self.known_indent_sm_kwargs)
1000 results = sm.run(indented, input_offset=line_offset)
1001 return context, next_state, results
1003 def first_known_indent(self, match, context, next_state):
1004 """
1005 Handle an indented text block (first line's indent known).
1007 Extend or override in subclasses.
1009 Recursively run the registered state machine for known-indent indented
1010 blocks (`self.known_indent_sm`). The indent is the length of the
1011 match, ``match.end()``.
1012 """
1013 (indented, line_offset, blank_finish
1014 ) = self.state_machine.get_first_known_indented(match.end())
1015 sm = self.known_indent_sm(debug=self.debug,
1016 **self.known_indent_sm_kwargs)
1017 results = sm.run(indented, input_offset=line_offset)
1018 return context, next_state, results
1021class _SearchOverride:
1023 """
1024 Mix-in class to override `StateMachine` regular expression behavior.
1026 Changes regular expression matching, from the default `re.match()`
1027 (succeeds only if the pattern matches at the start of `self.line`) to
1028 `re.search()` (succeeds if the pattern matches anywhere in `self.line`).
1029 When subclassing a `StateMachine`, list this class **first** in the
1030 inheritance list of the class definition.
1031 """
1033 def match(self, pattern):
1034 """
1035 Return the result of a regular expression search.
1037 Overrides `StateMachine.match()`.
1039 Parameter `pattern`: `re` compiled regular expression.
1040 """
1041 return pattern.search(self.line)
1044class SearchStateMachine(_SearchOverride, StateMachine):
1045 """`StateMachine` which uses `re.search()` instead of `re.match()`."""
1048class SearchStateMachineWS(_SearchOverride, StateMachineWS):
1049 """`StateMachineWS` which uses `re.search()` instead of `re.match()`."""
1052class ViewList:
1054 """
1055 List with extended functionality: slices of ViewList objects are child
1056 lists, linked to their parents. Changes made to a child list also affect
1057 the parent list. A child list is effectively a "view" (in the SQL sense)
1058 of the parent list. Changes to parent lists, however, do *not* affect
1059 active child lists. If a parent list is changed, any active child lists
1060 should be recreated.
1062 The start and end of the slice can be trimmed using the `trim_start()` and
1063 `trim_end()` methods, without affecting the parent list. The link between
1064 child and parent lists can be broken by calling `disconnect()` on the
1065 child list.
1067 Also, ViewList objects keep track of the source & offset of each item.
1068 This information is accessible via the `source()`, `offset()`, and
1069 `info()` methods.
1070 """
1072 def __init__(self, initlist=None, source=None, items=None,
1073 parent=None, parent_offset=None) -> None:
1074 self.data = []
1075 """The actual list of data, flattened from various sources."""
1077 self.items = []
1078 """A list of (source, offset) pairs, same length as `self.data`: the
1079 source of each line and the offset of each line from the beginning of
1080 its source."""
1082 self.parent = parent
1083 """The parent list."""
1085 self.parent_offset = parent_offset
1086 """Offset of this list from the beginning of the parent list."""
1088 if isinstance(initlist, ViewList):
1089 self.data = initlist.data[:]
1090 self.items = initlist.items[:]
1091 elif initlist is not None:
1092 self.data = list(initlist)
1093 if items:
1094 self.items = items
1095 else:
1096 self.items = [(source, i) for i in range(len(initlist))]
1097 assert len(self.data) == len(self.items), 'data mismatch'
1099 def __str__(self) -> str:
1100 return str(self.data)
1102 def __repr__(self) -> str:
1103 return f'{self.__class__.__name__}({self.data}, items={self.items})'
1105 def __lt__(self, other):
1106 return self.data < self.__cast(other)
1108 def __le__(self, other):
1109 return self.data <= self.__cast(other)
1111 def __eq__(self, other):
1112 return self.data == self.__cast(other)
1114 def __ne__(self, other):
1115 return self.data != self.__cast(other)
1117 def __gt__(self, other):
1118 return self.data > self.__cast(other)
1120 def __ge__(self, other):
1121 return self.data >= self.__cast(other)
1123 def __cast(self, other):
1124 if isinstance(other, ViewList):
1125 return other.data
1126 else:
1127 return other
1129 def __contains__(self, item) -> bool:
1130 return item in self.data
1132 def __len__(self) -> int:
1133 return len(self.data)
1135 # The __getitem__()/__setitem__() methods check whether the index
1136 # is a slice first, since indexing a native list with a slice object
1137 # just works.
1139 def __getitem__(self, i):
1140 if isinstance(i, slice):
1141 assert i.step in (None, 1), 'cannot handle slice with stride'
1142 return self.__class__(self.data[i.start:i.stop],
1143 items=self.items[i.start:i.stop],
1144 parent=self, parent_offset=i.start or 0)
1145 else:
1146 return self.data[i]
1148 def __setitem__(self, i, item) -> None:
1149 if isinstance(i, slice):
1150 assert i.step in (None, 1), 'cannot handle slice with stride'
1151 if not isinstance(item, ViewList):
1152 raise TypeError('assigning non-ViewList to ViewList slice')
1153 self.data[i.start:i.stop] = item.data
1154 self.items[i.start:i.stop] = item.items
1155 assert len(self.data) == len(self.items), 'data mismatch'
1156 if self.parent:
1157 k = (i.start or 0) + self.parent_offset
1158 n = (i.stop or len(self)) + self.parent_offset
1159 self.parent[k:n] = item
1160 else:
1161 self.data[i] = item
1162 if self.parent:
1163 self.parent[i + self.parent_offset] = item
1165 def __delitem__(self, i) -> None:
1166 try:
1167 del self.data[i]
1168 del self.items[i]
1169 if self.parent:
1170 del self.parent[i + self.parent_offset]
1171 except TypeError:
1172 assert i.step is None, 'cannot handle slice with stride'
1173 del self.data[i.start:i.stop]
1174 del self.items[i.start:i.stop]
1175 if self.parent:
1176 k = (i.start or 0) + self.parent_offset
1177 n = (i.stop or len(self)) + self.parent_offset
1178 del self.parent[k:n]
1180 def __add__(self, other):
1181 if isinstance(other, ViewList):
1182 return self.__class__(self.data + other.data,
1183 items=(self.items + other.items))
1184 else:
1185 raise TypeError('adding non-ViewList to a ViewList')
1187 def __radd__(self, other):
1188 if isinstance(other, ViewList):
1189 return self.__class__(other.data + self.data,
1190 items=(other.items + self.items))
1191 else:
1192 raise TypeError('adding ViewList to a non-ViewList')
1194 def __iadd__(self, other):
1195 if isinstance(other, ViewList):
1196 self.data += other.data
1197 else:
1198 raise TypeError('argument to += must be a ViewList')
1199 return self
1201 def __mul__(self, n):
1202 return self.__class__(self.data * n, items=(self.items * n))
1204 __rmul__ = __mul__
1206 def __imul__(self, n):
1207 self.data *= n
1208 self.items *= n
1209 return self
1211 def extend(self, other):
1212 if not isinstance(other, ViewList):
1213 raise TypeError('extending a ViewList with a non-ViewList')
1214 if self.parent:
1215 self.parent.insert(len(self.data) + self.parent_offset, other)
1216 self.data.extend(other.data)
1217 self.items.extend(other.items)
1219 def append(self, item, source=None, offset=0) -> None:
1220 if source is None:
1221 self.extend(item)
1222 else:
1223 if self.parent:
1224 self.parent.insert(len(self.data) + self.parent_offset, item,
1225 source, offset)
1226 self.data.append(item)
1227 self.items.append((source, offset))
1229 def insert(self, i, item, source=None, offset=0):
1230 if source is None:
1231 if not isinstance(item, ViewList):
1232 raise TypeError('inserting non-ViewList with no source given')
1233 self.data[i:i] = item.data
1234 self.items[i:i] = item.items
1235 if self.parent:
1236 index = (len(self.data) + i) % len(self.data)
1237 self.parent.insert(index + self.parent_offset, item)
1238 else:
1239 self.data.insert(i, item)
1240 self.items.insert(i, (source, offset))
1241 if self.parent:
1242 index = (len(self.data) + i) % len(self.data)
1243 self.parent.insert(index + self.parent_offset, item,
1244 source, offset)
1246 def pop(self, i=-1):
1247 if self.parent:
1248 index = (len(self.data) + i) % len(self.data)
1249 self.parent.pop(index + self.parent_offset)
1250 self.items.pop(i)
1251 return self.data.pop(i)
1253 def trim_start(self, n=1):
1254 """
1255 Remove items from the start of the list, without touching the parent.
1256 """
1257 if n > len(self.data):
1258 raise IndexError("Size of trim too large; can't trim %s items "
1259 "from a list of size %s." % (n, len(self.data)))
1260 elif n < 0:
1261 raise IndexError('Trim size must be >= 0.')
1262 del self.data[:n]
1263 del self.items[:n]
1264 if self.parent:
1265 self.parent_offset += n
1267 def trim_end(self, n=1):
1268 """
1269 Remove items from the end of the list, without touching the parent.
1270 """
1271 if n > len(self.data):
1272 raise IndexError("Size of trim too large; can't trim %s items "
1273 "from a list of size %s." % (n, len(self.data)))
1274 elif n < 0:
1275 raise IndexError('Trim size must be >= 0.')
1276 del self.data[-n:]
1277 del self.items[-n:]
1279 def remove(self, item) -> None:
1280 index = self.index(item)
1281 del self[index]
1283 def count(self, item):
1284 return self.data.count(item)
1286 def index(self, item):
1287 return self.data.index(item)
1289 def reverse(self) -> None:
1290 self.data.reverse()
1291 self.items.reverse()
1292 self.parent = None
1294 def sort(self, *args) -> None:
1295 tmp = sorted(zip(self.data, self.items), *args)
1296 self.data = [entry[0] for entry in tmp]
1297 self.items = [entry[1] for entry in tmp]
1298 self.parent = None
1300 def info(self, i):
1301 """Return source & offset for index `i`."""
1302 try:
1303 return self.items[i]
1304 except IndexError:
1305 if i == len(self.data): # Just past the end
1306 return self.items[i - 1][0], None
1307 else:
1308 raise
1310 def source(self, i):
1311 """Return source for index `i`."""
1312 return self.info(i)[0]
1314 def offset(self, i):
1315 """Return offset for index `i`."""
1316 return self.info(i)[1]
1318 def disconnect(self) -> None:
1319 """Break link between this list and parent list."""
1320 self.parent = None
1322 def xitems(self):
1323 """Return iterator yielding (source, offset, value) tuples."""
1324 for (value, (source, offset)) in zip(self.data, self.items):
1325 yield source, offset, value
1327 def pprint(self) -> None:
1328 """Print the list in `grep` format (`source:offset:value` lines)"""
1329 for line in self.xitems():
1330 print("%s:%d:%s" % line)
1333class StringList(ViewList):
1335 """A `ViewList` with string-specific methods."""
1337 def trim_left(self, length, start=0, end=sys.maxsize) -> None:
1338 """
1339 Trim `length` characters off the beginning of each item, in-place,
1340 from index `start` to `end`. No whitespace-checking is done on the
1341 trimmed text. Does not affect slice parent.
1342 """
1343 self.data[start:end] = [line[length:]
1344 for line in self.data[start:end]]
1346 def get_text_block(self, start, flush_left=False):
1347 """
1348 Return a contiguous block of text.
1350 If `flush_left` is true, raise `UnexpectedIndentationError` if an
1351 indented line is encountered before the text block ends (with a blank
1352 line).
1353 """
1354 end = start
1355 last = len(self.data)
1356 while end < last:
1357 line = self.data[end]
1358 if not line.strip():
1359 break
1360 if flush_left and (line[0] == ' '):
1361 source, offset = self.info(end)
1362 raise UnexpectedIndentationError(self[start:end], source,
1363 offset + 1)
1364 end += 1
1365 return self[start:end]
1367 def get_indented(self, start=0, until_blank=False, strip_indent=True,
1368 block_indent=None, first_indent=None):
1369 """
1370 Extract and return a StringList of indented lines of text.
1372 Collect all lines with indentation, determine the minimum indentation,
1373 remove the minimum indentation from all indented lines (unless
1374 `strip_indent` is false), and return them. All lines up to but not
1375 including the first unindented line will be returned.
1377 :Parameters:
1378 - `start`: The index of the first line to examine.
1379 - `until_blank`: Stop collecting at the first blank line if true.
1380 - `strip_indent`: Strip common leading indent if true (default).
1381 - `block_indent`: The indent of the entire block, if known.
1382 - `first_indent`: The indent of the first line, if known.
1384 :Return:
1385 - a StringList of indented lines with minimum indent removed;
1386 - the amount of the indent;
1387 - a boolean: did the indented block finish with a blank line or EOF?
1388 """
1389 indent = block_indent # start with None if unknown
1390 end = start
1391 if block_indent is not None and first_indent is None:
1392 first_indent = block_indent
1393 if first_indent is not None:
1394 end += 1
1395 last = len(self.data)
1396 while end < last:
1397 line = self.data[end]
1398 if line and (line[0] != ' '
1399 or (block_indent is not None
1400 and line[:block_indent].strip())):
1401 # Line not indented or insufficiently indented.
1402 # Block finished properly iff the last indented line blank:
1403 blank_finish = ((end > start)
1404 and not self.data[end - 1].strip())
1405 break
1406 stripped = line.lstrip()
1407 if not stripped: # blank line
1408 if until_blank:
1409 blank_finish = 1
1410 break
1411 elif block_indent is None:
1412 line_indent = len(line) - len(stripped)
1413 if indent is None:
1414 indent = line_indent
1415 else:
1416 indent = min(indent, line_indent)
1417 end += 1
1418 else:
1419 blank_finish = 1 # block ends at end of lines
1420 block = self[start:end]
1421 if first_indent is not None and block:
1422 block.data[0] = block.data[0][first_indent:]
1423 if indent and strip_indent:
1424 block.trim_left(indent, start=(first_indent is not None))
1425 return block, indent or 0, blank_finish
1427 def get_2D_block(self, top, left, bottom, right, strip_indent=True):
1428 block = self[top:bottom]
1429 indent = right
1430 for i in range(len(block.data)):
1431 # get slice from line, care for combining characters
1432 ci = utils.column_indices(block.data[i])
1433 try:
1434 left = ci[left]
1435 except IndexError:
1436 left += len(block.data[i]) - len(ci)
1437 try:
1438 right = ci[right]
1439 except IndexError:
1440 right += len(block.data[i]) - len(ci)
1441 block.data[i] = line = block.data[i][left:right].rstrip()
1442 if line:
1443 indent = min(indent, len(line) - len(line.lstrip()))
1444 if strip_indent and 0 < indent < right:
1445 block.data = [line[indent:] for line in block.data]
1446 return block
1448 def pad_double_width(self, pad_char) -> None:
1449 """Pad all double-width characters in `self` appending `pad_char`.
1451 For East Asian language support.
1452 """
1453 for i in range(len(self.data)):
1454 line = self.data[i]
1455 if isinstance(line, str):
1456 new = []
1457 for char in line:
1458 new.append(char)
1459 if east_asian_width(char) in 'WF': # Wide & Full-width
1460 new.append(pad_char)
1461 self.data[i] = ''.join(new)
1463 def replace(self, old, new) -> None:
1464 """Replace all occurrences of substring `old` with `new`."""
1465 for i in range(len(self.data)):
1466 self.data[i] = self.data[i].replace(old, new)
1469class StateMachineError(Exception): pass
1470class UnknownStateError(StateMachineError): pass
1471class DuplicateStateError(StateMachineError): pass
1472class UnknownTransitionError(StateMachineError): pass
1473class DuplicateTransitionError(StateMachineError): pass
1474class TransitionPatternNotFound(StateMachineError): pass
1475class TransitionMethodNotFound(StateMachineError): pass
1476class UnexpectedIndentationError(StateMachineError): pass
1479class TransitionCorrection(Exception):
1481 """
1482 Raise from within a transition method to switch to another transition.
1484 Raise with one argument, the new transition name.
1485 """
1488class StateCorrection(Exception):
1490 """
1491 Raise from within a transition method to switch to another state.
1493 Raise with one or two arguments: new state name, and an optional new
1494 transition name.
1495 """
1498def string2lines(astring, tab_width=8, convert_whitespace=False,
1499 whitespace=re.compile('[\v\f]')):
1500 """
1501 Return a list of one-line strings with tabs expanded, no newlines, and
1502 trailing whitespace stripped.
1504 Each tab is expanded with between 1 and `tab_width` spaces, so that the
1505 next character's index becomes a multiple of `tab_width` (8 by default).
1507 Parameters:
1509 - `astring`: a multi-line string.
1510 - `tab_width`: the number of columns between tab stops.
1511 - `convert_whitespace`: convert form feeds and vertical tabs to spaces?
1512 - `whitespace`: pattern object with the to-be-converted
1513 whitespace characters (default [\\v\\f]).
1514 """
1515 if convert_whitespace:
1516 astring = whitespace.sub(' ', astring)
1517 return [s.expandtabs(tab_width).rstrip() for s in astring.splitlines()]
1520def _exception_data():
1521 """
1522 Return exception information:
1524 - the exception's class name;
1525 - the exception object;
1526 - the name of the file containing the offending code;
1527 - the line number of the offending code;
1528 - the function name of the offending code.
1529 """
1530 typ, value, traceback = sys.exc_info()
1531 while traceback.tb_next:
1532 traceback = traceback.tb_next
1533 code = traceback.tb_frame.f_code
1534 return (typ.__name__, value, code.co_filename, traceback.tb_lineno,
1535 code.co_name)