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 """
143 self.input_lines = None
144 """`StringList` of input lines (without newlines).
145 Filled by `self.run()`."""
147 self.input_offset = 0
148 """Offset of `self.input_lines` from the beginning of the file."""
150 self.line = None
151 """Current input line."""
153 self.line_offset = -1
154 """Current input line offset from beginning of `self.input_lines`."""
156 self.debug = debug
157 """Debugging mode on/off."""
159 self.initial_state = initial_state
160 """The name of the initial state (key to `self.states`)."""
162 self.current_state = initial_state
163 """The name of the current state (key to `self.states`)."""
165 self.states = {}
166 """Mapping of {state_name: State_object}."""
168 self.add_states(state_classes)
170 self.observers = []
171 """List of bound methods or functions to call whenever the current
172 line changes. Observers are called with one argument, ``self``.
173 Cleared at the end of `run()`."""
175 def unlink(self) -> None:
176 """Remove circular references to objects no longer required."""
177 for state in self.states.values():
178 state.unlink()
179 self.states = None
181 def run(self, input_lines, input_offset=0, context=None,
182 input_source=None, initial_state=None):
183 """
184 Run the state machine on `input_lines`. Return results (a list).
186 Reset `self.line_offset` and `self.current_state`. Run the
187 beginning-of-file transition. Input one line at a time and check for a
188 matching transition. If a match is found, call the transition method
189 and possibly change the state. Store the context returned by the
190 transition method to be passed on to the next transition matched.
191 Accumulate the results returned by the transition methods in a list.
192 Run the end-of-file transition. Finally, return the accumulated
193 results.
195 Parameters:
197 - `input_lines`: a list of strings without newlines, or `StringList`.
198 - `input_offset`: the line offset of `input_lines` from the beginning
199 of the file.
200 - `context`: application-specific storage.
201 - `input_source`: name or path of source of `input_lines`.
202 - `initial_state`: name of initial state.
203 """
204 self.runtime_init()
205 if isinstance(input_lines, StringList):
206 self.input_lines = input_lines
207 else:
208 self.input_lines = StringList(input_lines, source=input_source)
209 self.input_offset = input_offset
210 self.line_offset = -1
211 self.current_state = initial_state or self.initial_state
212 if self.debug:
213 print('\nStateMachine.run: input_lines (line_offset=%s):\n| %s'
214 % (self.line_offset, '\n| '.join(self.input_lines)),
215 file=sys.stderr)
216 transitions = None
217 results = []
218 state = self.get_state()
219 try:
220 if self.debug:
221 print('\nStateMachine.run: bof transition', file=sys.stderr)
222 context, result = state.bof(context)
223 results.extend(result)
224 while True:
225 try:
226 try:
227 self.next_line()
228 if self.debug:
229 source, offset = self.input_lines.info(
230 self.line_offset)
231 print(f'\nStateMachine.run: line '
232 f'(source={source!r}, offset={offset!r}):\n'
233 f'| {self.line}', file=sys.stderr)
234 context, next_state, result = self.check_line(
235 context, state, transitions)
236 except EOFError:
237 if self.debug:
238 print('\nStateMachine.run: %s.eof transition'
239 % state.__class__.__name__, file=sys.stderr)
240 result = state.eof(context)
241 results.extend(result)
242 break
243 else:
244 results.extend(result)
245 except TransitionCorrection as exception:
246 self.previous_line() # back up for another try
247 transitions = (exception.args[0],)
248 if self.debug:
249 print('\nStateMachine.run: TransitionCorrection to '
250 f'state "{state.__class__.__name__}", '
251 f'transition {transitions[0]}.',
252 file=sys.stderr)
253 continue
254 except StateCorrection as exception:
255 self.previous_line() # back up for another try
256 next_state = exception.args[0]
257 if len(exception.args) == 1:
258 transitions = None
259 else:
260 transitions = (exception.args[1],)
261 if self.debug:
262 print('\nStateMachine.run: StateCorrection to state '
263 f'"{next_state}", transition {transitions[0]}.',
264 file=sys.stderr)
265 else:
266 transitions = None
267 state = self.get_state(next_state)
268 except: # NoQA: E722 (catchall)
269 if self.debug:
270 self.error()
271 raise
272 self.observers = []
273 return results
275 def get_state(self, next_state=None):
276 """
277 Return current state object; set it first if `next_state` given.
279 Parameter `next_state`: a string, the name of the next state.
281 Exception: `UnknownStateError` raised if `next_state` unknown.
282 """
283 if next_state:
284 if self.debug and next_state != self.current_state:
285 print('\nStateMachine.get_state: Changing state from '
286 '"%s" to "%s" (input line %s).'
287 % (self.current_state, next_state,
288 self.abs_line_number()), file=sys.stderr)
289 self.current_state = next_state
290 try:
291 return self.states[self.current_state]
292 except KeyError:
293 raise UnknownStateError(self.current_state)
295 def next_line(self, n=1):
296 """Load `self.line` with the `n`'th next line and return it."""
297 try:
298 try:
299 self.line_offset += n
300 self.line = self.input_lines[self.line_offset]
301 except IndexError:
302 self.line = None
303 raise EOFError
304 return self.line
305 finally:
306 self.notify_observers()
308 def is_next_line_blank(self):
309 """Return True if the next line is blank or non-existent."""
310 try:
311 return not self.input_lines[self.line_offset + 1].strip()
312 except IndexError:
313 return 1
315 def at_eof(self):
316 """Return 1 if the input is at or past end-of-file."""
317 return self.line_offset >= len(self.input_lines) - 1
319 def at_bof(self):
320 """Return 1 if the input is at or before beginning-of-file."""
321 return self.line_offset <= 0
323 def previous_line(self, n=1):
324 """Load `self.line` with the `n`'th previous line and return it."""
325 self.line_offset -= n
326 if self.line_offset < 0:
327 self.line = None
328 else:
329 self.line = self.input_lines[self.line_offset]
330 self.notify_observers()
331 return self.line
333 def goto_line(self, line_offset):
334 """Jump to absolute line offset `line_offset`, load and return it."""
335 try:
336 try:
337 self.line_offset = line_offset - self.input_offset
338 self.line = self.input_lines[self.line_offset]
339 except IndexError:
340 self.line = None
341 raise EOFError
342 return self.line
343 finally:
344 self.notify_observers()
346 def get_source(self, line_offset):
347 """Return source of line at absolute line offset `line_offset`."""
348 return self.input_lines.source(line_offset - self.input_offset)
350 def abs_line_offset(self):
351 """Return line offset of current line, from beginning of file."""
352 return self.line_offset + self.input_offset
354 def abs_line_number(self):
355 """Return line number of current line (counting from 1)."""
356 return self.line_offset + self.input_offset + 1
358 def get_source_and_line(self, lineno=None):
359 """Return (source, line) tuple for current or given line number.
361 Looks up the source and line number in the `self.input_lines`
362 StringList instance to count for included source files.
364 If the optional argument `lineno` is given, convert it from an
365 absolute line number to the corresponding (source, line) pair.
366 """
367 if lineno is None:
368 offset = self.line_offset
369 else:
370 offset = lineno - self.input_offset - 1
371 try:
372 src, srcoffset = self.input_lines.info(offset)
373 srcline = srcoffset + 1
374 except TypeError:
375 # line is None if index is "Just past the end"
376 src, srcline = self.get_source_and_line(offset + self.input_offset)
377 return src, srcline + 1
378 except IndexError: # `offset` is off the list
379 src, srcline = None, None
380 # raise AssertionError('cannot find line %d in %s lines' %
381 # (offset, len(self.input_lines)))
382 # # list(self.input_lines.lines())))
383 return src, srcline
385 def insert_input(self, input_lines, source) -> None:
386 self.input_lines.insert(self.line_offset + 1, '',
387 source='internal padding after '+source,
388 offset=len(input_lines))
389 self.input_lines.insert(self.line_offset + 1, '',
390 source='internal padding before '+source,
391 offset=-1)
392 self.input_lines.insert(self.line_offset + 2,
393 StringList(input_lines, source))
395 def get_text_block(self, flush_left=False):
396 """
397 Return a contiguous block of text.
399 If `flush_left` is true, raise `UnexpectedIndentationError` if an
400 indented line is encountered before the text block ends (with a blank
401 line).
402 """
403 try:
404 block = self.input_lines.get_text_block(self.line_offset,
405 flush_left)
406 self.next_line(len(block) - 1)
407 return block
408 except UnexpectedIndentationError as err:
409 block = err.args[0]
410 self.next_line(len(block) - 1) # advance to last line of block
411 raise
413 def check_line(self, context, state, transitions=None):
414 """
415 Examine one line of input for a transition match & execute its method.
417 Parameters:
419 - `context`: application-dependent storage.
420 - `state`: a `State` object, the current state.
421 - `transitions`: an optional ordered list of transition names to try,
422 instead of ``state.transition_order``.
424 Return the values returned by the transition method:
426 - context: possibly modified from the parameter `context`;
427 - next state name (`State` subclass name);
428 - the result output of the transition, a list.
430 When there is no match, ``state.no_match()`` is called and its return
431 value is returned.
432 """
433 if transitions is None:
434 transitions = state.transition_order
435 if self.debug:
436 print('\nStateMachine.check_line: state="%s", transitions=%r.'
437 % (state.__class__.__name__, transitions), file=sys.stderr)
438 for name in transitions:
439 pattern, method, next_state = state.transitions[name]
440 match = pattern.match(self.line)
441 if match:
442 if self.debug:
443 print('\nStateMachine.check_line: Matched transition '
444 f'"{name}" in state "{state.__class__.__name__}".',
445 file=sys.stderr)
446 return method(match, context, next_state)
447 else:
448 if self.debug:
449 print('\nStateMachine.check_line: No match in state "%s".'
450 % state.__class__.__name__, file=sys.stderr)
451 return state.no_match(context, transitions)
453 def add_state(self, state_class):
454 """
455 Initialize & add a `state_class` (`State` subclass) object.
457 Exception: `DuplicateStateError` raised if `state_class` was already
458 added.
459 """
460 statename = state_class.__name__
461 if statename in self.states:
462 raise DuplicateStateError(statename)
463 self.states[statename] = state_class(self, self.debug)
465 def add_states(self, state_classes) -> None:
466 """
467 Add `state_classes` (a list of `State` subclasses).
468 """
469 for state_class in state_classes:
470 self.add_state(state_class)
472 def runtime_init(self) -> None:
473 """
474 Initialize `self.states`.
475 """
476 for state in self.states.values():
477 state.runtime_init()
479 def error(self) -> None:
480 """Report error details."""
481 type_name, value, module, line, function = _exception_data()
482 print('%s: %s' % (type_name, value), file=sys.stderr)
483 print('input line %s' % (self.abs_line_number()), file=sys.stderr)
484 print('module %s, line %s, function %s' % (module, line, function),
485 file=sys.stderr)
487 def attach_observer(self, observer) -> None:
488 """
489 The `observer` parameter is a function or bound method which takes two
490 arguments, the source and offset of the current line.
491 """
492 self.observers.append(observer)
494 def detach_observer(self, observer) -> None:
495 self.observers.remove(observer)
497 def notify_observers(self) -> None:
498 for observer in self.observers:
499 try:
500 info = self.input_lines.info(self.line_offset)
501 except IndexError:
502 info = (None, None)
503 observer(*info)
506class State:
508 """
509 State superclass. Contains a list of transitions, and transition methods.
511 Transition methods all have the same signature. They take 3 parameters:
513 - An `re` match object. ``match.string`` contains the matched input line,
514 ``match.start()`` gives the start index of the match, and
515 ``match.end()`` gives the end index.
516 - A context object, whose meaning is application-defined (initial value
517 ``None``). It can be used to store any information required by the state
518 machine, and the returned context is passed on to the next transition
519 method unchanged.
520 - The name of the next state, a string, taken from the transitions list;
521 normally it is returned unchanged, but it may be altered by the
522 transition method if necessary.
524 Transition methods all return a 3-tuple:
526 - A context object, as (potentially) modified by the transition method.
527 - The next state name (a return value of ``None`` means no state change).
528 - The processing result, a list, which is accumulated by the state
529 machine.
531 Transition methods may raise an `EOFError` to cut processing short.
533 There are two implicit transitions, and corresponding transition methods
534 are defined: `bof()` handles the beginning-of-file, and `eof()` handles
535 the end-of-file. These methods have non-standard signatures and return
536 values. `bof()` returns the initial context and results, and may be used
537 to return a header string, or do any other processing needed. `eof()`
538 should handle any remaining context and wrap things up; it returns the
539 final processing result.
541 Typical applications need only subclass `State` (or a subclass), set the
542 `patterns` and `initial_transitions` class attributes, and provide
543 corresponding transition methods. The default object initialization will
544 take care of constructing the list of transitions.
545 """
547 patterns = None
548 """
549 {Name: pattern} mapping, used by `make_transition()`. Each pattern may
550 be a string or a compiled `re` pattern. Override in subclasses.
551 """
553 initial_transitions = None
554 """
555 A list of transitions to initialize when a `State` is instantiated.
556 Each entry is either a transition name string, or a (transition name, next
557 state name) pair. See `make_transitions()`. Override in subclasses.
558 """
560 nested_sm = None
561 """
562 The `StateMachine` class for handling nested processing.
564 If left as ``None``, `nested_sm` defaults to the class of the state's
565 controlling state machine. Override it in subclasses to avoid the default.
566 """
568 nested_sm_kwargs = None
569 """
570 Keyword arguments dictionary, passed to the `nested_sm` constructor.
572 Two keys must have entries in the dictionary:
574 - Key 'state_classes' must be set to a list of `State` classes.
575 - Key 'initial_state' must be set to the name of the initial state class.
577 If `nested_sm_kwargs` is left as ``None``, 'state_classes' defaults to the
578 class of the current state, and 'initial_state' defaults to the name of
579 the class of the current state. Override in subclasses to avoid the
580 defaults.
581 """
583 def __init__(self, state_machine, debug=False) -> None:
584 """
585 Initialize a `State` object; make & add initial transitions.
587 Parameters:
589 - `statemachine`: the controlling `StateMachine` object.
590 - `debug`: a boolean; produce verbose output if true.
591 """
593 self.transition_order = []
594 """A list of transition names in search order."""
596 self.transitions = {}
597 """
598 A mapping of transition names to 3-tuples containing
599 (compiled_pattern, transition_method, next_state_name). Initialized as
600 an instance attribute dynamically (instead of as a class attribute)
601 because it may make forward references to patterns and methods in this
602 or other classes.
603 """
605 self.add_initial_transitions()
607 self.state_machine = state_machine
608 """A reference to the controlling `StateMachine` object."""
610 self.debug = debug
611 """Debugging mode on/off."""
613 if self.nested_sm is None:
614 self.nested_sm = self.state_machine.__class__
615 if self.nested_sm_kwargs is None:
616 self.nested_sm_kwargs = {'state_classes': [self.__class__],
617 'initial_state': self.__class__.__name__}
619 def runtime_init(self) -> None:
620 """
621 Initialize this `State` before running the state machine; called from
622 `self.state_machine.run()`.
623 """
625 def unlink(self) -> None:
626 """Remove circular references to objects no longer required."""
627 self.state_machine = None
629 def add_initial_transitions(self) -> None:
630 """Make and add transitions listed in `self.initial_transitions`."""
631 if self.initial_transitions:
632 names, transitions = self.make_transitions(
633 self.initial_transitions)
634 self.add_transitions(names, transitions)
636 def add_transitions(self, names, transitions):
637 """
638 Add a list of transitions to the start of the transition list.
640 Parameters:
642 - `names`: a list of transition names.
643 - `transitions`: a mapping of names to transition tuples.
645 Exceptions: `DuplicateTransitionError`, `UnknownTransitionError`.
646 """
647 for name in names:
648 if name in self.transitions:
649 raise DuplicateTransitionError(name)
650 if name not in transitions:
651 raise UnknownTransitionError(name)
652 self.transition_order[:0] = names
653 self.transitions.update(transitions)
655 def add_transition(self, name, transition):
656 """
657 Add a transition to the start of the transition list.
659 Parameter `transition`: a ready-made transition 3-tuple.
661 Exception: `DuplicateTransitionError`.
662 """
663 if name in self.transitions:
664 raise DuplicateTransitionError(name)
665 self.transition_order[:0] = [name]
666 self.transitions[name] = transition
668 def remove_transition(self, name):
669 """
670 Remove a transition by `name`.
672 Exception: `UnknownTransitionError`.
673 """
674 try:
675 del self.transitions[name]
676 self.transition_order.remove(name)
677 except: # NoQA: E722 (catchall)
678 raise UnknownTransitionError(name)
680 def make_transition(self, name, next_state=None):
681 """
682 Make & return a transition tuple based on `name`.
684 This is a convenience function to simplify transition creation.
686 Parameters:
688 - `name`: a string, the name of the transition pattern & method. This
689 `State` object must have a method called '`name`', and a dictionary
690 `self.patterns` containing a key '`name`'.
691 - `next_state`: a string, the name of the next `State` object for this
692 transition. A value of ``None`` (or absent) implies no state change
693 (i.e., continue with the same state).
695 Exceptions: `TransitionPatternNotFound`, `TransitionMethodNotFound`.
696 """
697 if next_state is None:
698 next_state = self.__class__.__name__
699 try:
700 pattern = self.patterns[name]
701 if not hasattr(pattern, 'match'):
702 pattern = self.patterns[name] = re.compile(pattern)
703 except KeyError:
704 raise TransitionPatternNotFound(
705 '%s.patterns[%r]' % (self.__class__.__name__, name))
706 try:
707 method = getattr(self, name)
708 except AttributeError:
709 raise TransitionMethodNotFound(
710 '%s.%s' % (self.__class__.__name__, name))
711 return pattern, method, next_state
713 def make_transitions(self, name_list):
714 """
715 Return a list of transition names and a transition mapping.
717 Parameter `name_list`: a list, where each entry is either a transition
718 name string, or a 1- or 2-tuple (transition name, optional next state
719 name).
720 """
721 names = []
722 transitions = {}
723 for namestate in name_list:
724 if isinstance(namestate, str):
725 transitions[namestate] = self.make_transition(namestate)
726 names.append(namestate)
727 else:
728 transitions[namestate[0]] = self.make_transition(*namestate)
729 names.append(namestate[0])
730 return names, transitions
732 def no_match(self, context, transitions):
733 """
734 Called when there is no match from `StateMachine.check_line()`.
736 Return the same values returned by transition methods:
738 - context: unchanged;
739 - next state name: ``None``;
740 - empty result list.
742 Override in subclasses to catch this event.
743 """
744 return context, None, []
746 def bof(self, context):
747 """
748 Handle beginning-of-file. Return unchanged `context`, empty result.
750 Override in subclasses.
752 Parameter `context`: application-defined storage.
753 """
754 return context, []
756 def eof(self, context):
757 """
758 Handle end-of-file. Return empty result.
760 Override in subclasses.
762 Parameter `context`: application-defined storage.
763 """
764 return []
766 def nop(self, match, context, next_state):
767 """
768 A "do nothing" transition method.
770 Return unchanged `context` & `next_state`, empty result. Useful for
771 simple state changes (actionless transitions).
772 """
773 return context, next_state, []
776class StateMachineWS(StateMachine):
778 """
779 `StateMachine` subclass specialized for whitespace recognition.
781 There are three methods provided for extracting indented text blocks:
783 - `get_indented()`: use when the indent is unknown.
784 - `get_known_indented()`: use when the indent is known for all lines.
785 - `get_first_known_indented()`: use when only the first line's indent is
786 known.
787 """
789 def get_indented(self, until_blank=False, strip_indent=True):
790 """
791 Return a block of indented lines of text, and info.
793 Extract an indented block where the indent is unknown for all lines.
795 :Parameters:
796 - `until_blank`: Stop collecting at the first blank line if true.
797 - `strip_indent`: Strip common leading indent if true (default).
799 :Return:
800 - the indented block (a list of lines of text),
801 - its indent,
802 - its first line offset from BOF, and
803 - whether or not it finished with a blank line.
804 """
805 offset = self.abs_line_offset()
806 indented, indent, blank_finish = self.input_lines.get_indented(
807 self.line_offset, until_blank, strip_indent)
808 if indented:
809 self.next_line(len(indented) - 1) # advance to last indented line
810 while indented and not indented[0].strip():
811 indented.trim_start()
812 offset += 1
813 return indented, indent, offset, blank_finish
815 def get_known_indented(self, indent, until_blank=False, strip_indent=True):
816 """
817 Return an indented block and info.
819 Extract an indented block where the indent is known for all lines.
820 Starting with the current line, extract the entire text block with at
821 least `indent` indentation (which must be whitespace, except for the
822 first line).
824 :Parameters:
825 - `indent`: The number of indent columns/characters.
826 - `until_blank`: Stop collecting at the first blank line if true.
827 - `strip_indent`: Strip `indent` characters of indentation if true
828 (default).
830 :Return:
831 - the indented block,
832 - its first line offset from BOF, and
833 - whether or not it finished with a blank line.
834 """
835 offset = self.abs_line_offset()
836 indented, indent, blank_finish = self.input_lines.get_indented(
837 self.line_offset, until_blank, strip_indent,
838 block_indent=indent)
839 self.next_line(len(indented) - 1) # advance to last indented line
840 while indented and not indented[0].strip():
841 indented.trim_start()
842 offset += 1
843 return indented, offset, blank_finish
845 def get_first_known_indented(self, indent, until_blank=False,
846 strip_indent=True, strip_top=True):
847 """
848 Return an indented block and info.
850 Extract an indented block where the indent is known for the first line
851 and unknown for all other lines.
853 :Parameters:
854 - `indent`: The first line's indent (# of columns/characters).
855 - `until_blank`: Stop collecting at the first blank line if true
856 (1).
857 - `strip_indent`: Strip `indent` characters of indentation if true
858 (1, default).
859 - `strip_top`: Strip blank lines from the beginning of the block.
861 :Return:
862 - the indented block,
863 - its indent,
864 - its first line offset from BOF, and
865 - whether or not it finished with a blank line.
866 """
867 offset = self.abs_line_offset()
868 indented, indent, blank_finish = self.input_lines.get_indented(
869 self.line_offset, until_blank, strip_indent,
870 first_indent=indent)
871 self.next_line(len(indented) - 1) # advance to last indented line
872 if strip_top:
873 while indented and not indented[0].strip():
874 indented.trim_start()
875 offset += 1
876 return indented, indent, offset, blank_finish
879class StateWS(State):
881 """
882 State superclass specialized for whitespace (blank lines & indents).
884 Use this class with `StateMachineWS`. The transitions 'blank' (for blank
885 lines) and 'indent' (for indented text blocks) are added automatically,
886 before any other transitions. The transition method `blank()` handles
887 blank lines and `indent()` handles nested indented blocks. Indented
888 blocks trigger a new state machine to be created by `indent()` and run.
889 The class of the state machine to be created is in `indent_sm`, and the
890 constructor keyword arguments are in the dictionary `indent_sm_kwargs`.
892 The methods `known_indent()` and `firstknown_indent()` are provided for
893 indented blocks where the indent (all lines' and first line's only,
894 respectively) is known to the transition method, along with the attributes
895 `known_indent_sm` and `known_indent_sm_kwargs`. Neither transition method
896 is triggered automatically.
897 """
899 indent_sm = None
900 """
901 The `StateMachine` class handling indented text blocks.
903 If left as ``None``, `indent_sm` defaults to the value of
904 `State.nested_sm`. Override it in subclasses to avoid the default.
905 """
907 indent_sm_kwargs = None
908 """
909 Keyword arguments dictionary, passed to the `indent_sm` constructor.
911 If left as ``None``, `indent_sm_kwargs` defaults to the value of
912 `State.nested_sm_kwargs`. Override it in subclasses to avoid the default.
913 """
915 known_indent_sm = None
916 """
917 The `StateMachine` class handling known-indented text blocks.
919 If left as ``None``, `known_indent_sm` defaults to the value of
920 `indent_sm`. Override it in subclasses to avoid the default.
921 """
923 known_indent_sm_kwargs = None
924 """
925 Keyword arguments dictionary, passed to the `known_indent_sm` constructor.
927 If left as ``None``, `known_indent_sm_kwargs` defaults to the value of
928 `indent_sm_kwargs`. Override it in subclasses to avoid the default.
929 """
931 ws_patterns = {'blank': re.compile(' *$'),
932 'indent': re.compile(' +')}
933 """Patterns for default whitespace transitions. May be overridden in
934 subclasses."""
936 ws_initial_transitions = ('blank', 'indent')
937 """Default initial whitespace transitions, added before those listed in
938 `State.initial_transitions`. May be overridden in subclasses."""
940 def __init__(self, state_machine, debug=False) -> None:
941 """
942 Initialize a `StateSM` object; extends `State.__init__()`.
944 Check for indent state machine attributes, set defaults if not set.
945 """
946 State.__init__(self, state_machine, debug)
947 if self.indent_sm is None:
948 self.indent_sm = self.nested_sm
949 if self.indent_sm_kwargs is None:
950 self.indent_sm_kwargs = self.nested_sm_kwargs
951 if self.known_indent_sm is None:
952 self.known_indent_sm = self.indent_sm
953 if self.known_indent_sm_kwargs is None:
954 self.known_indent_sm_kwargs = self.indent_sm_kwargs
956 def add_initial_transitions(self) -> None:
957 """
958 Add whitespace-specific transitions before those defined in subclass.
960 Extends `State.add_initial_transitions()`.
961 """
962 State.add_initial_transitions(self)
963 if self.patterns is None:
964 self.patterns = {}
965 self.patterns.update(self.ws_patterns)
966 names, transitions = self.make_transitions(
967 self.ws_initial_transitions)
968 self.add_transitions(names, transitions)
970 def blank(self, match, context, next_state):
971 """Handle blank lines. Does nothing. Override in subclasses."""
972 return self.nop(match, context, next_state)
974 def indent(self, match, context, next_state):
975 """
976 Handle an indented text block. Extend or override in subclasses.
978 Recursively run the registered state machine for indented blocks
979 (`self.indent_sm`).
980 """
981 (indented, indent, line_offset, blank_finish
982 ) = self.state_machine.get_indented()
983 sm = self.indent_sm(debug=self.debug, **self.indent_sm_kwargs)
984 results = sm.run(indented, input_offset=line_offset)
985 return context, next_state, results
987 def known_indent(self, match, context, next_state):
988 """
989 Handle a known-indent text block. Extend or override in subclasses.
991 Recursively run the registered state machine for known-indent indented
992 blocks (`self.known_indent_sm`). The indent is the length of the
993 match, ``match.end()``.
994 """
995 (indented, line_offset, blank_finish
996 ) = self.state_machine.get_known_indented(match.end())
997 sm = self.known_indent_sm(debug=self.debug,
998 **self.known_indent_sm_kwargs)
999 results = sm.run(indented, input_offset=line_offset)
1000 return context, next_state, results
1002 def first_known_indent(self, match, context, next_state):
1003 """
1004 Handle an indented text block (first line's indent known).
1006 Extend or override in subclasses.
1008 Recursively run the registered state machine for known-indent indented
1009 blocks (`self.known_indent_sm`). The indent is the length of the
1010 match, ``match.end()``.
1011 """
1012 (indented, line_offset, blank_finish
1013 ) = self.state_machine.get_first_known_indented(match.end())
1014 sm = self.known_indent_sm(debug=self.debug,
1015 **self.known_indent_sm_kwargs)
1016 results = sm.run(indented, input_offset=line_offset)
1017 return context, next_state, results
1020class _SearchOverride:
1022 """
1023 Mix-in class to override `StateMachine` regular expression behavior.
1025 Changes regular expression matching, from the default `re.match()`
1026 (succeeds only if the pattern matches at the start of `self.line`) to
1027 `re.search()` (succeeds if the pattern matches anywhere in `self.line`).
1028 When subclassing a `StateMachine`, list this class **first** in the
1029 inheritance list of the class definition.
1030 """
1032 def match(self, pattern):
1033 """
1034 Return the result of a regular expression search.
1036 Overrides `StateMachine.match()`.
1038 Parameter `pattern`: `re` compiled regular expression.
1039 """
1040 return pattern.search(self.line)
1043class SearchStateMachine(_SearchOverride, StateMachine):
1044 """`StateMachine` which uses `re.search()` instead of `re.match()`."""
1047class SearchStateMachineWS(_SearchOverride, StateMachineWS):
1048 """`StateMachineWS` which uses `re.search()` instead of `re.match()`."""
1051class ViewList:
1053 """
1054 List with extended functionality: slices of ViewList objects are child
1055 lists, linked to their parents. Changes made to a child list also affect
1056 the parent list. A child list is effectively a "view" (in the SQL sense)
1057 of the parent list. Changes to parent lists, however, do *not* affect
1058 active child lists. If a parent list is changed, any active child lists
1059 should be recreated.
1061 The start and end of the slice can be trimmed using the `trim_start()` and
1062 `trim_end()` methods, without affecting the parent list. The link between
1063 child and parent lists can be broken by calling `disconnect()` on the
1064 child list.
1066 Also, ViewList objects keep track of the source & offset of each item.
1067 This information is accessible via the `source()`, `offset()`, and
1068 `info()` methods.
1069 """
1071 def __init__(self, initlist=None, source=None, items=None,
1072 parent=None, parent_offset=None) -> None:
1073 self.data = []
1074 """The actual list of data, flattened from various sources."""
1076 self.items = []
1077 """A list of (source, offset) pairs, same length as `self.data`: the
1078 source of each line and the offset of each line from the beginning of
1079 its source."""
1081 self.parent = parent
1082 """The parent list."""
1084 self.parent_offset = parent_offset
1085 """Offset of this list from the beginning of the parent list."""
1087 if isinstance(initlist, ViewList):
1088 self.data = initlist.data[:]
1089 self.items = initlist.items[:]
1090 elif initlist is not None:
1091 self.data = list(initlist)
1092 if items:
1093 self.items = items
1094 else:
1095 self.items = [(source, i) for i in range(len(initlist))]
1096 assert len(self.data) == len(self.items), 'data mismatch'
1098 def __str__(self) -> str:
1099 return str(self.data)
1101 def __repr__(self) -> str:
1102 return f'{self.__class__.__name__}({self.data}, items={self.items})'
1104 def __lt__(self, other):
1105 return self.data < self.__cast(other)
1107 def __le__(self, other):
1108 return self.data <= self.__cast(other)
1110 def __eq__(self, other):
1111 return self.data == self.__cast(other)
1113 def __ne__(self, other):
1114 return self.data != self.__cast(other)
1116 def __gt__(self, other):
1117 return self.data > self.__cast(other)
1119 def __ge__(self, other):
1120 return self.data >= self.__cast(other)
1122 def __cast(self, other):
1123 if isinstance(other, ViewList):
1124 return other.data
1125 else:
1126 return other
1128 def __contains__(self, item) -> bool:
1129 return item in self.data
1131 def __len__(self) -> int:
1132 return len(self.data)
1134 # The __getitem__()/__setitem__() methods check whether the index
1135 # is a slice first, since indexing a native list with a slice object
1136 # just works.
1138 def __getitem__(self, i):
1139 if isinstance(i, slice):
1140 assert i.step in (None, 1), 'cannot handle slice with stride'
1141 return self.__class__(self.data[i.start:i.stop],
1142 items=self.items[i.start:i.stop],
1143 parent=self, parent_offset=i.start or 0)
1144 else:
1145 return self.data[i]
1147 def __setitem__(self, i, item) -> None:
1148 if isinstance(i, slice):
1149 assert i.step in (None, 1), 'cannot handle slice with stride'
1150 if not isinstance(item, ViewList):
1151 raise TypeError('assigning non-ViewList to ViewList slice')
1152 self.data[i.start:i.stop] = item.data
1153 self.items[i.start:i.stop] = item.items
1154 assert len(self.data) == len(self.items), 'data mismatch'
1155 if self.parent:
1156 k = (i.start or 0) + self.parent_offset
1157 n = (i.stop or len(self)) + self.parent_offset
1158 self.parent[k:n] = item
1159 else:
1160 self.data[i] = item
1161 if self.parent:
1162 self.parent[i + self.parent_offset] = item
1164 def __delitem__(self, i) -> None:
1165 try:
1166 del self.data[i]
1167 del self.items[i]
1168 if self.parent:
1169 del self.parent[i + self.parent_offset]
1170 except TypeError:
1171 assert i.step is None, 'cannot handle slice with stride'
1172 del self.data[i.start:i.stop]
1173 del self.items[i.start:i.stop]
1174 if self.parent:
1175 k = (i.start or 0) + self.parent_offset
1176 n = (i.stop or len(self)) + self.parent_offset
1177 del self.parent[k:n]
1179 def __add__(self, other):
1180 if isinstance(other, ViewList):
1181 return self.__class__(self.data + other.data,
1182 items=(self.items + other.items))
1183 else:
1184 raise TypeError('adding non-ViewList to a ViewList')
1186 def __radd__(self, other):
1187 if isinstance(other, ViewList):
1188 return self.__class__(other.data + self.data,
1189 items=(other.items + self.items))
1190 else:
1191 raise TypeError('adding ViewList to a non-ViewList')
1193 def __iadd__(self, other):
1194 if isinstance(other, ViewList):
1195 self.data += other.data
1196 else:
1197 raise TypeError('argument to += must be a ViewList')
1198 return self
1200 def __mul__(self, n):
1201 return self.__class__(self.data * n, items=(self.items * n))
1203 __rmul__ = __mul__
1205 def __imul__(self, n):
1206 self.data *= n
1207 self.items *= n
1208 return self
1210 def extend(self, other):
1211 if not isinstance(other, ViewList):
1212 raise TypeError('extending a ViewList with a non-ViewList')
1213 if self.parent:
1214 self.parent.insert(len(self.data) + self.parent_offset, other)
1215 self.data.extend(other.data)
1216 self.items.extend(other.items)
1218 def append(self, item, source=None, offset=0) -> None:
1219 if source is None:
1220 self.extend(item)
1221 else:
1222 if self.parent:
1223 self.parent.insert(len(self.data) + self.parent_offset, item,
1224 source, offset)
1225 self.data.append(item)
1226 self.items.append((source, offset))
1228 def insert(self, i, item, source=None, offset=0):
1229 if source is None:
1230 if not isinstance(item, ViewList):
1231 raise TypeError('inserting non-ViewList with no source given')
1232 self.data[i:i] = item.data
1233 self.items[i:i] = item.items
1234 if self.parent:
1235 index = (len(self.data) + i) % len(self.data)
1236 self.parent.insert(index + self.parent_offset, item)
1237 else:
1238 self.data.insert(i, item)
1239 self.items.insert(i, (source, offset))
1240 if self.parent:
1241 index = (len(self.data) + i) % len(self.data)
1242 self.parent.insert(index + self.parent_offset, item,
1243 source, offset)
1245 def pop(self, i=-1):
1246 if self.parent:
1247 index = (len(self.data) + i) % len(self.data)
1248 self.parent.pop(index + self.parent_offset)
1249 self.items.pop(i)
1250 return self.data.pop(i)
1252 def trim_start(self, n=1):
1253 """
1254 Remove items from the start of the list, without touching the parent.
1255 """
1256 if n > len(self.data):
1257 raise IndexError("Size of trim too large; can't trim %s items "
1258 "from a list of size %s." % (n, len(self.data)))
1259 elif n < 0:
1260 raise IndexError('Trim size must be >= 0.')
1261 del self.data[:n]
1262 del self.items[:n]
1263 if self.parent:
1264 self.parent_offset += n
1266 def trim_end(self, n=1):
1267 """
1268 Remove items from the end of the list, without touching the parent.
1269 """
1270 if n > len(self.data):
1271 raise IndexError("Size of trim too large; can't trim %s items "
1272 "from a list of size %s." % (n, len(self.data)))
1273 elif n < 0:
1274 raise IndexError('Trim size must be >= 0.')
1275 del self.data[-n:]
1276 del self.items[-n:]
1278 def remove(self, item) -> None:
1279 index = self.index(item)
1280 del self[index]
1282 def count(self, item):
1283 return self.data.count(item)
1285 def index(self, item):
1286 return self.data.index(item)
1288 def reverse(self) -> None:
1289 self.data.reverse()
1290 self.items.reverse()
1291 self.parent = None
1293 def sort(self, *args) -> None:
1294 tmp = sorted(zip(self.data, self.items), *args)
1295 self.data = [entry[0] for entry in tmp]
1296 self.items = [entry[1] for entry in tmp]
1297 self.parent = None
1299 def info(self, i):
1300 """Return source & offset for index `i`."""
1301 try:
1302 return self.items[i]
1303 except IndexError:
1304 if i == len(self.data): # Just past the end
1305 return self.items[i - 1][0], None
1306 else:
1307 raise
1309 def source(self, i):
1310 """Return source for index `i`."""
1311 return self.info(i)[0]
1313 def offset(self, i):
1314 """Return offset for index `i`."""
1315 return self.info(i)[1]
1317 def disconnect(self) -> None:
1318 """Break link between this list and parent list."""
1319 self.parent = None
1321 def xitems(self):
1322 """Return iterator yielding (source, offset, value) tuples."""
1323 for (value, (source, offset)) in zip(self.data, self.items):
1324 yield source, offset, value
1326 def pprint(self) -> None:
1327 """Print the list in `grep` format (`source:offset:value` lines)"""
1328 for line in self.xitems():
1329 print("%s:%d:%s" % line)
1332class StringList(ViewList):
1334 """A `ViewList` with string-specific methods."""
1336 def trim_left(self, length, start=0, end=sys.maxsize) -> None:
1337 """
1338 Trim `length` characters off the beginning of each item, in-place,
1339 from index `start` to `end`. No whitespace-checking is done on the
1340 trimmed text. Does not affect slice parent.
1341 """
1342 self.data[start:end] = [line[length:]
1343 for line in self.data[start:end]]
1345 def get_text_block(self, start, flush_left=False):
1346 """
1347 Return a contiguous block of text.
1349 If `flush_left` is true, raise `UnexpectedIndentationError` if an
1350 indented line is encountered before the text block ends (with a blank
1351 line).
1352 """
1353 end = start
1354 last = len(self.data)
1355 while end < last:
1356 line = self.data[end]
1357 if not line.strip():
1358 break
1359 if flush_left and (line[0] == ' '):
1360 source, offset = self.info(end)
1361 raise UnexpectedIndentationError(self[start:end], source,
1362 offset + 1)
1363 end += 1
1364 return self[start:end]
1366 def get_indented(self, start=0, until_blank=False, strip_indent=True,
1367 block_indent=None, first_indent=None):
1368 """
1369 Extract and return a StringList of indented lines of text.
1371 Collect all lines with indentation, determine the minimum indentation,
1372 remove the minimum indentation from all indented lines (unless
1373 `strip_indent` is false), and return them. All lines up to but not
1374 including the first unindented line will be returned.
1376 :Parameters:
1377 - `start`: The index of the first line to examine.
1378 - `until_blank`: Stop collecting at the first blank line if true.
1379 - `strip_indent`: Strip common leading indent if true (default).
1380 - `block_indent`: The indent of the entire block, if known.
1381 - `first_indent`: The indent of the first line, if known.
1383 :Return:
1384 - a StringList of indented lines with minimum indent removed;
1385 - the amount of the indent;
1386 - a boolean: did the indented block finish with a blank line or EOF?
1387 """
1388 indent = block_indent # start with None if unknown
1389 end = start
1390 if block_indent is not None and first_indent is None:
1391 first_indent = block_indent
1392 if first_indent is not None:
1393 end += 1
1394 last = len(self.data)
1395 while end < last:
1396 line = self.data[end]
1397 if line and (line[0] != ' '
1398 or (block_indent is not None
1399 and line[:block_indent].strip())):
1400 # Line not indented or insufficiently indented.
1401 # Block finished properly iff the last indented line blank:
1402 blank_finish = ((end > start)
1403 and not self.data[end - 1].strip())
1404 break
1405 stripped = line.lstrip()
1406 if not stripped: # blank line
1407 if until_blank:
1408 blank_finish = True
1409 break
1410 elif block_indent is None:
1411 line_indent = len(line) - len(stripped)
1412 if indent is None:
1413 indent = line_indent
1414 else:
1415 indent = min(indent, line_indent)
1416 end += 1
1417 else:
1418 blank_finish = True # block ends at end of lines
1419 block = self[start:end]
1420 if first_indent is not None and block:
1421 block.data[0] = block.data[0][first_indent:]
1422 if indent and strip_indent:
1423 block.trim_left(indent, start=(first_indent is not None))
1424 return block, indent or 0, blank_finish
1426 def get_2D_block(self, top, left, bottom, right, strip_indent=True):
1427 block = self[top:bottom]
1428 indent = right
1429 for i, line in enumerate(block.data):
1430 # trim line to block borders, allow for for combining characters
1431 adjusted_indices = utils.column_indices(line)
1432 try:
1433 left_i = adjusted_indices[left]
1434 except IndexError:
1435 left_i = left
1436 try:
1437 right_i = adjusted_indices[right]
1438 except IndexError:
1439 right_i = len(line)
1440 block.data[i] = line = line[left_i:right_i].rstrip()
1441 if line:
1442 indent = min(indent, len(line) - len(line.lstrip()))
1443 if strip_indent and 0 < indent < right:
1444 block.data = [line[indent:] for line in block.data]
1445 return block
1447 def pad_double_width(self, pad_char) -> None:
1448 """Pad all double-width characters in `self` appending `pad_char`.
1450 For East Asian language support.
1451 """
1452 for i in range(len(self.data)):
1453 line = self.data[i]
1454 if isinstance(line, str):
1455 new = []
1456 for char in line:
1457 new.append(char)
1458 if east_asian_width(char) in 'WF': # Wide & Full-width
1459 new.append(pad_char)
1460 self.data[i] = ''.join(new)
1462 def replace(self, old, new) -> None:
1463 """Replace all occurrences of substring `old` with `new`."""
1464 for i in range(len(self.data)):
1465 self.data[i] = self.data[i].replace(old, new)
1468class StateMachineError(Exception): pass
1469class UnknownStateError(StateMachineError): pass
1470class DuplicateStateError(StateMachineError): pass
1471class UnknownTransitionError(StateMachineError): pass
1472class DuplicateTransitionError(StateMachineError): pass
1473class TransitionPatternNotFound(StateMachineError): pass
1474class TransitionMethodNotFound(StateMachineError): pass
1475class UnexpectedIndentationError(StateMachineError): pass
1478class TransitionCorrection(Exception):
1480 """
1481 Raise from within a transition method to switch to another transition.
1483 Raise with one argument, the new transition name.
1484 """
1487class StateCorrection(Exception):
1489 """
1490 Raise from within a transition method to switch to another state.
1492 Raise with one or two arguments: new state name, and an optional new
1493 transition name.
1494 """
1497def string2lines(astring, tab_width=8, convert_whitespace=False,
1498 whitespace=re.compile('[\v\f]')):
1499 """
1500 Return a list of one-line strings with tabs expanded, no newlines, and
1501 trailing whitespace stripped.
1503 Each tab is expanded with between 1 and `tab_width` spaces, so that the
1504 next character's index becomes a multiple of `tab_width` (8 by default).
1506 Parameters:
1508 - `astring`: a multi-line string.
1509 - `tab_width`: the number of columns between tab stops.
1510 - `convert_whitespace`: convert form feeds and vertical tabs to spaces?
1511 - `whitespace`: pattern object with the to-be-converted
1512 whitespace characters (default [\\v\\f]).
1513 """
1514 if convert_whitespace:
1515 astring = whitespace.sub(' ', astring)
1516 return [s.expandtabs(tab_width).rstrip() for s in astring.splitlines()]
1519def _exception_data():
1520 """
1521 Return exception information:
1523 - the exception's class name;
1524 - the exception object;
1525 - the name of the file containing the offending code;
1526 - the line number of the offending code;
1527 - the function name of the offending code.
1528 """
1529 typ, value, traceback = sys.exc_info()
1530 while traceback.tb_next:
1531 traceback = traceback.tb_next
1532 code = traceback.tb_frame.f_code
1533 return (typ.__name__, value, code.co_filename, traceback.tb_lineno,
1534 code.co_name)