Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/lark/parsers/earley_forest.py: 71%
459 statements
« prev ^ index » next coverage.py v7.3.1, created at 2023-09-25 06:30 +0000
« prev ^ index » next coverage.py v7.3.1, created at 2023-09-25 06:30 +0000
1""""This module implements an SPPF implementation
3This is used as the primary output mechanism for the Earley parser
4in order to store complex ambiguities.
6Full reference and more details is here:
7https://web.archive.org/web/20190616123959/http://www.bramvandersanden.com/post/2014/06/shared-packed-parse-forest/
8"""
10from random import randint
11from collections import deque
12from operator import attrgetter
13from importlib import import_module
14from functools import partial
16from ..parse_tree_builder import AmbiguousIntermediateExpander
17from ..visitors import Discard
18from ..utils import logger
19from ..tree import Tree
21class ForestNode:
22 pass
24class SymbolNode(ForestNode):
25 """
26 A Symbol Node represents a symbol (or Intermediate LR0).
28 Symbol nodes are keyed by the symbol (s). For intermediate nodes
29 s will be an LR0, stored as a tuple of (rule, ptr). For completed symbol
30 nodes, s will be a string representing the non-terminal origin (i.e.
31 the left hand side of the rule).
33 The children of a Symbol or Intermediate Node will always be Packed Nodes;
34 with each Packed Node child representing a single derivation of a production.
36 Hence a Symbol Node with a single child is unambiguous.
38 Parameters:
39 s: A Symbol, or a tuple of (rule, ptr) for an intermediate node.
40 start: The index of the start of the substring matched by this symbol (inclusive).
41 end: The index of the end of the substring matched by this symbol (exclusive).
43 Properties:
44 is_intermediate: True if this node is an intermediate node.
45 priority: The priority of the node's symbol.
46 """
47 __slots__ = ('s', 'start', 'end', '_children', 'paths', 'paths_loaded', 'priority', 'is_intermediate', '_hash')
48 def __init__(self, s, start, end):
49 self.s = s
50 self.start = start
51 self.end = end
52 self._children = set()
53 self.paths = set()
54 self.paths_loaded = False
56 ### We use inf here as it can be safely negated without resorting to conditionals,
57 # unlike None or float('NaN'), and sorts appropriately.
58 self.priority = float('-inf')
59 self.is_intermediate = isinstance(s, tuple)
60 self._hash = hash((self.s, self.start, self.end))
62 def add_family(self, lr0, rule, start, left, right):
63 self._children.add(PackedNode(self, lr0, rule, start, left, right))
65 def add_path(self, transitive, node):
66 self.paths.add((transitive, node))
68 def load_paths(self):
69 for transitive, node in self.paths:
70 if transitive.next_titem is not None:
71 vn = SymbolNode(transitive.next_titem.s, transitive.next_titem.start, self.end)
72 vn.add_path(transitive.next_titem, node)
73 self.add_family(transitive.reduction.rule.origin, transitive.reduction.rule, transitive.reduction.start, transitive.reduction.node, vn)
74 else:
75 self.add_family(transitive.reduction.rule.origin, transitive.reduction.rule, transitive.reduction.start, transitive.reduction.node, node)
76 self.paths_loaded = True
78 @property
79 def is_ambiguous(self):
80 """Returns True if this node is ambiguous."""
81 return len(self.children) > 1
83 @property
84 def children(self):
85 """Returns a list of this node's children sorted from greatest to
86 least priority."""
87 if not self.paths_loaded:
88 self.load_paths()
89 return sorted(self._children, key=attrgetter('sort_key'))
91 def __iter__(self):
92 return iter(self._children)
94 def __eq__(self, other):
95 if not isinstance(other, SymbolNode):
96 return False
97 return self is other or (type(self.s) == type(other.s) and self.s == other.s and self.start == other.start and self.end is other.end)
99 def __hash__(self):
100 return self._hash
102 def __repr__(self):
103 if self.is_intermediate:
104 rule = self.s[0]
105 ptr = self.s[1]
106 before = ( expansion.name for expansion in rule.expansion[:ptr] )
107 after = ( expansion.name for expansion in rule.expansion[ptr:] )
108 symbol = "{} ::= {}* {}".format(rule.origin.name, ' '.join(before), ' '.join(after))
109 else:
110 symbol = self.s.name
111 return "({}, {}, {}, {})".format(symbol, self.start, self.end, self.priority)
113class PackedNode(ForestNode):
114 """
115 A Packed Node represents a single derivation in a symbol node.
117 Parameters:
118 rule: The rule associated with this node.
119 parent: The parent of this node.
120 left: The left child of this node. ``None`` if one does not exist.
121 right: The right child of this node. ``None`` if one does not exist.
122 priority: The priority of this node.
123 """
124 __slots__ = ('parent', 's', 'rule', 'start', 'left', 'right', 'priority', '_hash')
125 def __init__(self, parent, s, rule, start, left, right):
126 self.parent = parent
127 self.s = s
128 self.start = start
129 self.rule = rule
130 self.left = left
131 self.right = right
132 self.priority = float('-inf')
133 self._hash = hash((self.left, self.right))
135 @property
136 def is_empty(self):
137 return self.left is None and self.right is None
139 @property
140 def sort_key(self):
141 """
142 Used to sort PackedNode children of SymbolNodes.
143 A SymbolNode has multiple PackedNodes if it matched
144 ambiguously. Hence, we use the sort order to identify
145 the order in which ambiguous children should be considered.
146 """
147 return self.is_empty, -self.priority, self.rule.order
149 @property
150 def children(self):
151 """Returns a list of this node's children."""
152 return [x for x in [self.left, self.right] if x is not None]
154 def __iter__(self):
155 yield self.left
156 yield self.right
158 def __eq__(self, other):
159 if not isinstance(other, PackedNode):
160 return False
161 return self is other or (self.left == other.left and self.right == other.right)
163 def __hash__(self):
164 return self._hash
166 def __repr__(self):
167 if isinstance(self.s, tuple):
168 rule = self.s[0]
169 ptr = self.s[1]
170 before = ( expansion.name for expansion in rule.expansion[:ptr] )
171 after = ( expansion.name for expansion in rule.expansion[ptr:] )
172 symbol = "{} ::= {}* {}".format(rule.origin.name, ' '.join(before), ' '.join(after))
173 else:
174 symbol = self.s.name
175 return "({}, {}, {}, {})".format(symbol, self.start, self.priority, self.rule.order)
177class TokenNode(ForestNode):
178 """
179 A Token Node represents a matched terminal and is always a leaf node.
181 Parameters:
182 token: The Token associated with this node.
183 term: The TerminalDef matched by the token.
184 priority: The priority of this node.
185 """
186 __slots__ = ('token', 'term', 'priority', '_hash')
187 def __init__(self, token, term, priority=None):
188 self.token = token
189 self.term = term
190 if priority is not None:
191 self.priority = priority
192 else:
193 self.priority = term.priority if term is not None else 0
194 self._hash = hash(token)
196 def __eq__(self, other):
197 if not isinstance(other, TokenNode):
198 return False
199 return self is other or (self.token == other.token)
201 def __hash__(self):
202 return self._hash
204 def __repr__(self):
205 return repr(self.token)
207class ForestVisitor:
208 """
209 An abstract base class for building forest visitors.
211 This class performs a controllable depth-first walk of an SPPF.
212 The visitor will not enter cycles and will backtrack if one is encountered.
213 Subclasses are notified of cycles through the ``on_cycle`` method.
215 Behavior for visit events is defined by overriding the
216 ``visit*node*`` functions.
218 The walk is controlled by the return values of the ``visit*node_in``
219 methods. Returning a node(s) will schedule them to be visited. The visitor
220 will begin to backtrack if no nodes are returned.
222 Parameters:
223 single_visit: If ``True``, non-Token nodes will only be visited once.
224 """
226 def __init__(self, single_visit=False):
227 self.single_visit = single_visit
229 def visit_token_node(self, node):
230 """Called when a ``Token`` is visited. ``Token`` nodes are always leaves."""
231 pass
233 def visit_symbol_node_in(self, node):
234 """Called when a symbol node is visited. Nodes that are returned
235 will be scheduled to be visited. If ``visit_intermediate_node_in``
236 is not implemented, this function will be called for intermediate
237 nodes as well."""
238 pass
240 def visit_symbol_node_out(self, node):
241 """Called after all nodes returned from a corresponding ``visit_symbol_node_in``
242 call have been visited. If ``visit_intermediate_node_out``
243 is not implemented, this function will be called for intermediate
244 nodes as well."""
245 pass
247 def visit_packed_node_in(self, node):
248 """Called when a packed node is visited. Nodes that are returned
249 will be scheduled to be visited. """
250 pass
252 def visit_packed_node_out(self, node):
253 """Called after all nodes returned from a corresponding ``visit_packed_node_in``
254 call have been visited."""
255 pass
257 def on_cycle(self, node, path):
258 """Called when a cycle is encountered.
260 Parameters:
261 node: The node that causes a cycle.
262 path: The list of nodes being visited: nodes that have been
263 entered but not exited. The first element is the root in a forest
264 visit, and the last element is the node visited most recently.
265 ``path`` should be treated as read-only.
266 """
267 pass
269 def get_cycle_in_path(self, node, path):
270 """A utility function for use in ``on_cycle`` to obtain a slice of
271 ``path`` that only contains the nodes that make up the cycle."""
272 index = len(path) - 1
273 while id(path[index]) != id(node):
274 index -= 1
275 return path[index:]
277 def visit(self, root):
278 # Visiting is a list of IDs of all symbol/intermediate nodes currently in
279 # the stack. It serves two purposes: to detect when we 'recurse' in and out
280 # of a symbol/intermediate so that we can process both up and down. Also,
281 # since the SPPF can have cycles it allows us to detect if we're trying
282 # to recurse into a node that's already on the stack (infinite recursion).
283 visiting = set()
285 # set of all nodes that have been visited
286 visited = set()
288 # a list of nodes that are currently being visited
289 # used for the `on_cycle` callback
290 path = []
292 # We do not use recursion here to walk the Forest due to the limited
293 # stack size in python. Therefore input_stack is essentially our stack.
294 input_stack = deque([root])
296 # It is much faster to cache these as locals since they are called
297 # many times in large parses.
298 vpno = getattr(self, 'visit_packed_node_out')
299 vpni = getattr(self, 'visit_packed_node_in')
300 vsno = getattr(self, 'visit_symbol_node_out')
301 vsni = getattr(self, 'visit_symbol_node_in')
302 vino = getattr(self, 'visit_intermediate_node_out', vsno)
303 vini = getattr(self, 'visit_intermediate_node_in', vsni)
304 vtn = getattr(self, 'visit_token_node')
305 oc = getattr(self, 'on_cycle')
307 while input_stack:
308 current = next(reversed(input_stack))
309 try:
310 next_node = next(current)
311 except StopIteration:
312 input_stack.pop()
313 continue
314 except TypeError:
315 ### If the current object is not an iterator, pass through to Token/SymbolNode
316 pass
317 else:
318 if next_node is None:
319 continue
321 if id(next_node) in visiting:
322 oc(next_node, path)
323 continue
325 input_stack.append(next_node)
326 continue
328 if isinstance(current, TokenNode):
329 vtn(current.token)
330 input_stack.pop()
331 continue
333 current_id = id(current)
334 if current_id in visiting:
335 if isinstance(current, PackedNode):
336 vpno(current)
337 elif current.is_intermediate:
338 vino(current)
339 else:
340 vsno(current)
341 input_stack.pop()
342 path.pop()
343 visiting.remove(current_id)
344 visited.add(current_id)
345 elif self.single_visit and current_id in visited:
346 input_stack.pop()
347 else:
348 visiting.add(current_id)
349 path.append(current)
350 if isinstance(current, PackedNode):
351 next_node = vpni(current)
352 elif current.is_intermediate:
353 next_node = vini(current)
354 else:
355 next_node = vsni(current)
356 if next_node is None:
357 continue
359 if not isinstance(next_node, ForestNode):
360 next_node = iter(next_node)
361 elif id(next_node) in visiting:
362 oc(next_node, path)
363 continue
365 input_stack.append(next_node)
367class ForestTransformer(ForestVisitor):
368 """The base class for a bottom-up forest transformation. Most users will
369 want to use ``TreeForestTransformer`` instead as it has a friendlier
370 interface and covers most use cases.
372 Transformations are applied via inheritance and overriding of the
373 ``transform*node`` methods.
375 ``transform_token_node`` receives a ``Token`` as an argument.
376 All other methods receive the node that is being transformed and
377 a list of the results of the transformations of that node's children.
378 The return value of these methods are the resulting transformations.
380 If ``Discard`` is raised in a node's transformation, no data from that node
381 will be passed to its parent's transformation.
382 """
384 def __init__(self):
385 super(ForestTransformer, self).__init__()
386 # results of transformations
387 self.data = dict()
388 # used to track parent nodes
389 self.node_stack = deque()
391 def transform(self, root):
392 """Perform a transformation on an SPPF."""
393 self.node_stack.append('result')
394 self.data['result'] = []
395 self.visit(root)
396 assert len(self.data['result']) <= 1
397 if self.data['result']:
398 return self.data['result'][0]
400 def transform_symbol_node(self, node, data):
401 """Transform a symbol node."""
402 return node
404 def transform_intermediate_node(self, node, data):
405 """Transform an intermediate node."""
406 return node
408 def transform_packed_node(self, node, data):
409 """Transform a packed node."""
410 return node
412 def transform_token_node(self, node):
413 """Transform a ``Token``."""
414 return node
416 def visit_symbol_node_in(self, node):
417 self.node_stack.append(id(node))
418 self.data[id(node)] = []
419 return node.children
421 def visit_packed_node_in(self, node):
422 self.node_stack.append(id(node))
423 self.data[id(node)] = []
424 return node.children
426 def visit_token_node(self, node):
427 transformed = self.transform_token_node(node)
428 if transformed is not Discard:
429 self.data[self.node_stack[-1]].append(transformed)
431 def _visit_node_out_helper(self, node, method):
432 self.node_stack.pop()
433 transformed = method(node, self.data[id(node)])
434 if transformed is not Discard:
435 self.data[self.node_stack[-1]].append(transformed)
436 del self.data[id(node)]
438 def visit_symbol_node_out(self, node):
439 self._visit_node_out_helper(node, self.transform_symbol_node)
441 def visit_intermediate_node_out(self, node):
442 self._visit_node_out_helper(node, self.transform_intermediate_node)
444 def visit_packed_node_out(self, node):
445 self._visit_node_out_helper(node, self.transform_packed_node)
448class ForestSumVisitor(ForestVisitor):
449 """
450 A visitor for prioritizing ambiguous parts of the Forest.
452 This visitor is used when support for explicit priorities on
453 rules is requested (whether normal, or invert). It walks the
454 forest (or subsets thereof) and cascades properties upwards
455 from the leaves.
457 It would be ideal to do this during parsing, however this would
458 require processing each Earley item multiple times. That's
459 a big performance drawback; so running a forest walk is the
460 lesser of two evils: there can be significantly more Earley
461 items created during parsing than there are SPPF nodes in the
462 final tree.
463 """
464 def __init__(self):
465 super(ForestSumVisitor, self).__init__(single_visit=True)
467 def visit_packed_node_in(self, node):
468 yield node.left
469 yield node.right
471 def visit_symbol_node_in(self, node):
472 return iter(node.children)
474 def visit_packed_node_out(self, node):
475 priority = node.rule.options.priority if not node.parent.is_intermediate and node.rule.options.priority else 0
476 priority += getattr(node.right, 'priority', 0)
477 priority += getattr(node.left, 'priority', 0)
478 node.priority = priority
480 def visit_symbol_node_out(self, node):
481 node.priority = max(child.priority for child in node.children)
483class PackedData():
484 """Used in transformationss of packed nodes to distinguish the data
485 that comes from the left child and the right child.
486 """
488 class _NoData():
489 pass
491 NO_DATA = _NoData()
493 def __init__(self, node, data):
494 self.left = self.NO_DATA
495 self.right = self.NO_DATA
496 if data:
497 if node.left is not None:
498 self.left = data[0]
499 if len(data) > 1:
500 self.right = data[1]
501 else:
502 self.right = data[0]
504class ForestToParseTree(ForestTransformer):
505 """Used by the earley parser when ambiguity equals 'resolve' or
506 'explicit'. Transforms an SPPF into an (ambiguous) parse tree.
508 Parameters:
509 tree_class: The tree class to use for construction
510 callbacks: A dictionary of rules to functions that output a tree
511 prioritizer: A ``ForestVisitor`` that manipulates the priorities of ForestNodes
512 resolve_ambiguity: If True, ambiguities will be resolved based on
513 priorities. Otherwise, `_ambig` nodes will be in the resulting tree.
514 use_cache: If True, the results of packed node transformations will be cached.
515 """
517 def __init__(self, tree_class=Tree, callbacks=dict(), prioritizer=ForestSumVisitor(), resolve_ambiguity=True, use_cache=True):
518 super(ForestToParseTree, self).__init__()
519 self.tree_class = tree_class
520 self.callbacks = callbacks
521 self.prioritizer = prioritizer
522 self.resolve_ambiguity = resolve_ambiguity
523 self._use_cache = use_cache
524 self._cache = {}
525 self._on_cycle_retreat = False
526 self._cycle_node = None
527 self._successful_visits = set()
529 def visit(self, root):
530 if self.prioritizer:
531 self.prioritizer.visit(root)
532 super(ForestToParseTree, self).visit(root)
533 self._cache = {}
535 def on_cycle(self, node, path):
536 logger.debug("Cycle encountered in the SPPF at node: %s. "
537 "As infinite ambiguities cannot be represented in a tree, "
538 "this family of derivations will be discarded.", node)
539 self._cycle_node = node
540 self._on_cycle_retreat = True
542 def _check_cycle(self, node):
543 if self._on_cycle_retreat:
544 if id(node) == id(self._cycle_node) or id(node) in self._successful_visits:
545 self._cycle_node = None
546 self._on_cycle_retreat = False
547 else:
548 return Discard
550 def _collapse_ambig(self, children):
551 new_children = []
552 for child in children:
553 if hasattr(child, 'data') and child.data == '_ambig':
554 new_children += child.children
555 else:
556 new_children.append(child)
557 return new_children
559 def _call_rule_func(self, node, data):
560 # called when transforming children of symbol nodes
561 # data is a list of trees or tokens that correspond to the
562 # symbol's rule expansion
563 return self.callbacks[node.rule](data)
565 def _call_ambig_func(self, node, data):
566 # called when transforming a symbol node
567 # data is a list of trees where each tree's data is
568 # equal to the name of the symbol or one of its aliases.
569 if len(data) > 1:
570 return self.tree_class('_ambig', data)
571 elif data:
572 return data[0]
573 return Discard
575 def transform_symbol_node(self, node, data):
576 if id(node) not in self._successful_visits:
577 return Discard
578 r = self._check_cycle(node)
579 if r is Discard:
580 return r
581 self._successful_visits.remove(id(node))
582 data = self._collapse_ambig(data)
583 return self._call_ambig_func(node, data)
585 def transform_intermediate_node(self, node, data):
586 if id(node) not in self._successful_visits:
587 return Discard
588 r = self._check_cycle(node)
589 if r is Discard:
590 return r
591 self._successful_visits.remove(id(node))
592 if len(data) > 1:
593 children = [self.tree_class('_inter', c) for c in data]
594 return self.tree_class('_iambig', children)
595 return data[0]
597 def transform_packed_node(self, node, data):
598 r = self._check_cycle(node)
599 if r is Discard:
600 return r
601 if self.resolve_ambiguity and id(node.parent) in self._successful_visits:
602 return Discard
603 if self._use_cache and id(node) in self._cache:
604 return self._cache[id(node)]
605 children = []
606 assert len(data) <= 2
607 data = PackedData(node, data)
608 if data.left is not PackedData.NO_DATA:
609 if node.left.is_intermediate and isinstance(data.left, list):
610 children += data.left
611 else:
612 children.append(data.left)
613 if data.right is not PackedData.NO_DATA:
614 children.append(data.right)
615 if node.parent.is_intermediate:
616 return self._cache.setdefault(id(node), children)
617 return self._cache.setdefault(id(node), self._call_rule_func(node, children))
619 def visit_symbol_node_in(self, node):
620 super(ForestToParseTree, self).visit_symbol_node_in(node)
621 if self._on_cycle_retreat:
622 return
623 return node.children
625 def visit_packed_node_in(self, node):
626 self._on_cycle_retreat = False
627 to_visit = super(ForestToParseTree, self).visit_packed_node_in(node)
628 if not self.resolve_ambiguity or id(node.parent) not in self._successful_visits:
629 if not self._use_cache or id(node) not in self._cache:
630 return to_visit
632 def visit_packed_node_out(self, node):
633 super(ForestToParseTree, self).visit_packed_node_out(node)
634 if not self._on_cycle_retreat:
635 self._successful_visits.add(id(node.parent))
637def handles_ambiguity(func):
638 """Decorator for methods of subclasses of ``TreeForestTransformer``.
639 Denotes that the method should receive a list of transformed derivations."""
640 func.handles_ambiguity = True
641 return func
643class TreeForestTransformer(ForestToParseTree):
644 """A ``ForestTransformer`` with a tree ``Transformer``-like interface.
645 By default, it will construct a tree.
647 Methods provided via inheritance are called based on the rule/symbol
648 names of nodes in the forest.
650 Methods that act on rules will receive a list of the results of the
651 transformations of the rule's children. By default, trees and tokens.
653 Methods that act on tokens will receive a token.
655 Alternatively, methods that act on rules may be annotated with
656 ``handles_ambiguity``. In this case, the function will receive a list
657 of all the transformations of all the derivations of the rule.
658 By default, a list of trees where each tree.data is equal to the
659 rule name or one of its aliases.
661 Non-tree transformations are made possible by override of
662 ``__default__``, ``__default_token__``, and ``__default_ambig__``.
664 Note:
665 Tree shaping features such as inlined rules and token filtering are
666 not built into the transformation. Positions are also not propagated.
668 Parameters:
669 tree_class: The tree class to use for construction
670 prioritizer: A ``ForestVisitor`` that manipulates the priorities of nodes in the SPPF.
671 resolve_ambiguity: If True, ambiguities will be resolved based on priorities.
672 use_cache (bool): If True, caches the results of some transformations,
673 potentially improving performance when ``resolve_ambiguity==False``.
674 Only use if you know what you are doing: i.e. All transformation
675 functions are pure and referentially transparent.
676 """
678 def __init__(self, tree_class=Tree, prioritizer=ForestSumVisitor(), resolve_ambiguity=True, use_cache=False):
679 super(TreeForestTransformer, self).__init__(tree_class, dict(), prioritizer, resolve_ambiguity, use_cache)
681 def __default__(self, name, data):
682 """Default operation on tree (for override).
684 Returns a tree with name with data as children.
685 """
686 return self.tree_class(name, data)
688 def __default_ambig__(self, name, data):
689 """Default operation on ambiguous rule (for override).
691 Wraps data in an '_ambig_' node if it contains more than
692 one element.
693 """
694 if len(data) > 1:
695 return self.tree_class('_ambig', data)
696 elif data:
697 return data[0]
698 return Discard
700 def __default_token__(self, node):
701 """Default operation on ``Token`` (for override).
703 Returns ``node``.
704 """
705 return node
707 def transform_token_node(self, node):
708 return getattr(self, node.type, self.__default_token__)(node)
710 def _call_rule_func(self, node, data):
711 name = node.rule.alias or node.rule.options.template_source or node.rule.origin.name
712 user_func = getattr(self, name, self.__default__)
713 if user_func == self.__default__ or hasattr(user_func, 'handles_ambiguity'):
714 user_func = partial(self.__default__, name)
715 if not self.resolve_ambiguity:
716 wrapper = partial(AmbiguousIntermediateExpander, self.tree_class)
717 user_func = wrapper(user_func)
718 return user_func(data)
720 def _call_ambig_func(self, node, data):
721 name = node.s.name
722 user_func = getattr(self, name, self.__default_ambig__)
723 if user_func == self.__default_ambig__ or not hasattr(user_func, 'handles_ambiguity'):
724 user_func = partial(self.__default_ambig__, name)
725 return user_func(data)
727class ForestToPyDotVisitor(ForestVisitor):
728 """
729 A Forest visitor which writes the SPPF to a PNG.
731 The SPPF can get really large, really quickly because
732 of the amount of meta-data it stores, so this is probably
733 only useful for trivial trees and learning how the SPPF
734 is structured.
735 """
736 def __init__(self, rankdir="TB"):
737 super(ForestToPyDotVisitor, self).__init__(single_visit=True)
738 self.pydot = import_module('pydot')
739 self.graph = self.pydot.Dot(graph_type='digraph', rankdir=rankdir)
741 def visit(self, root, filename):
742 super(ForestToPyDotVisitor, self).visit(root)
743 try:
744 self.graph.write_png(filename)
745 except FileNotFoundError as e:
746 logger.error("Could not write png: ", e)
748 def visit_token_node(self, node):
749 graph_node_id = str(id(node))
750 graph_node_label = "\"{}\"".format(node.value.replace('"', '\\"'))
751 graph_node_color = 0x808080
752 graph_node_style = "\"filled,rounded\""
753 graph_node_shape = "diamond"
754 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label)
755 self.graph.add_node(graph_node)
757 def visit_packed_node_in(self, node):
758 graph_node_id = str(id(node))
759 graph_node_label = repr(node)
760 graph_node_color = 0x808080
761 graph_node_style = "filled"
762 graph_node_shape = "diamond"
763 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label)
764 self.graph.add_node(graph_node)
765 yield node.left
766 yield node.right
768 def visit_packed_node_out(self, node):
769 graph_node_id = str(id(node))
770 graph_node = self.graph.get_node(graph_node_id)[0]
771 for child in [node.left, node.right]:
772 if child is not None:
773 child_graph_node_id = str(id(child.token if isinstance(child, TokenNode) else child))
774 child_graph_node = self.graph.get_node(child_graph_node_id)[0]
775 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node))
776 else:
777 #### Try and be above the Python object ID range; probably impl. specific, but maybe this is okay.
778 child_graph_node_id = str(randint(100000000000000000000000000000,123456789012345678901234567890))
779 child_graph_node_style = "invis"
780 child_graph_node = self.pydot.Node(child_graph_node_id, style=child_graph_node_style, label="None")
781 child_edge_style = "invis"
782 self.graph.add_node(child_graph_node)
783 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node, style=child_edge_style))
785 def visit_symbol_node_in(self, node):
786 graph_node_id = str(id(node))
787 graph_node_label = repr(node)
788 graph_node_color = 0x808080
789 graph_node_style = "\"filled\""
790 if node.is_intermediate:
791 graph_node_shape = "ellipse"
792 else:
793 graph_node_shape = "rectangle"
794 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label)
795 self.graph.add_node(graph_node)
796 return iter(node.children)
798 def visit_symbol_node_out(self, node):
799 graph_node_id = str(id(node))
800 graph_node = self.graph.get_node(graph_node_id)[0]
801 for child in node.children:
802 child_graph_node_id = str(id(child))
803 child_graph_node = self.graph.get_node(child_graph_node_id)[0]
804 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node))