1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 '''
31 Graph traversal - supports generic Python classes, but has extensions for
32 classes that record their own constructor arguments (and so allow deep
33 cloning of graphs).
34
35 The fundamental `dfs_edges` routine will traverse over (ie provides an iterator
36 that returns (flag, node) pairs, where flag describes the type of node and
37 ordering) a graph made of iterable Python objects. Only the __iter__ method
38 (implemented by all containers) is required. However, in general this is too
39 broad (for example, Strings are iterable, and single character strings contain
40 themselves), so a type can be specified which identifies those nodes to
41 be treated as "interior" nodes. Children of interior nodes are returned as
42 "leaf" nodes, but are not iterated over themselves.
43
44 The `order` function provides a simpler interface to this traversal, allowing
45 a particular order to be generated, and, for example, optionally excluding leaf
46 nodes.
47
48 `ConstructorGraphNode` is motivated by data constructors and exposes its
49 constructor arguments (this is important because if we are cloning a graph
50 we want to replace constructor arguments that correspond to child nodes with
51 their clones). This currently has a single implementation,
52 `ArgAsAttributeMixin` (there used to be another, but it was equivalent to
53 the generic case with `SimpleWalker`).
54
55 The 'Walker' (`SimpleWalker` and `ConstructorWalker`) and `Visitor` classes
56 provide a different approach to traversing the graph (compared to the simple
57 sequences of nodes provided by `dfs_edges` et al), that reflects the emphasis
58 on constructors described above: the walker takes a visitor sub-class and
59 calls it in a way that replicates the original calls to the node constructors.
60 '''
61
62 from collections import Sequence, deque
63
64 from lepl.support.lib import compose, safe_in, safe_add, empty, fmt,\
65 fallback_add
66
67
68 FORWARD = 1
69 BACKWARD = 2
70 NONTREE = 4
71 ROOT = 8
72 NODE = 16
73 LEAF = 32
74
75 POSTORDER = BACKWARD | NONTREE
76 PREORDER = FORWARD | NONTREE
82 '''
83 Iterative DFS, based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
84
85 Returns forward and reverse edges. Also returns root node in correct
86 order for pre- (FORWARD) and post- (BACKWARD) ordering.
87
88 ``type_`` selects which values are iterated over. Children which are
89 not of this type are flagged with LEAF.
90 '''
91 while isinstance(node, type_):
92 try:
93 stack = [(node, iter(node), ROOT)]
94 yield node, node, FORWARD | ROOT
95 visited = set()
96 visited = fallback_add(visited, node)
97 while stack:
98 parent, children, ptype = stack[-1]
99 try:
100 child = next(children)
101 if isinstance(child, type_):
102 if safe_in(child, visited, False):
103 yield parent, child, NONTREE
104 else:
105 stack.append((child, iter(child), NODE))
106 yield parent, child, FORWARD | NODE
107 visited = fallback_add(visited, child)
108 else:
109 stack.append((child, empty(), LEAF))
110 yield parent, child, FORWARD | LEAF
111 except StopIteration:
112 stack.pop()
113 if stack:
114 yield stack[-1][0], parent, BACKWARD | ptype
115 yield node, node, BACKWARD | ROOT
116 return
117 except Reset:
118 yield
119
120
121 -class Reset(Exception):
122 '''
123 An exception that can be passed to dfs_edges to reset the traversal.
124 '''
125 pass
126
127
128 -def reset(generator):
129 '''
130 Reset the traversal by raising Reset.
131 '''
132 generator.throw(Reset())
133
134
135 -def order(node, include, type_, exclude=0):
136 '''
137 An ordered sequence of nodes. The ordering is given by 'include' (see
138 the constants PREORDER etc above).
139 '''
140 while True:
141 try:
142 for (_parent, child, direction) in dfs_edges(node, type_):
143 if (direction & include) and not (direction & exclude):
144 yield child
145 return
146 except Reset:
147 yield
148
149
150 -def preorder(node, type_, exclude=0):
151 '''
152 The nodes in preorder.
153 '''
154 return order(node, PREORDER, type_, exclude=exclude)
155
156
157 -def postorder(node, type_, exclude=0):
158 '''
159 The nodes in postorder.
160 '''
161 return order(node, POSTORDER, type_, exclude=exclude)
162
163
164 -def leaves(node, type_=None):
171
172
173 -def loops(node, type_):
174 '''
175 Return all loops from the given node.
176
177 Each loop is a list that starts and ends with the given node.
178 '''
179 stack = [[node]]
180 known = set([node])
181 while stack:
182 ancestors = stack.pop()
183 parent = ancestors[-1]
184 if isinstance(parent, type_):
185 for child in parent:
186 family = list(ancestors)
187 family.append(child)
188 if child is node:
189 yield family
190 else:
191 if not safe_in(child, known):
192 stack.append(family)
193 known = fallback_add(known, child)
194
199 '''
200 An interface that provides information on constructor arguments.
201
202 This is used by `ConstructorWalker` to provide the results of
203 walking child nodes in the same fmt as those nodes were provided in
204 the constructor. The main advantage is that the names of named
205 arguments are associated with the appropriate results.
206
207 For this to work correctly there is assumed to be a close relationship
208 between constructor arguments and children (there is a somewhat implicit
209 link between Python object constructors and type constructors in, say,
210 Haskell). Exactly how constructor argmuents and children match depends
211 on the implementation, but `ConstructorWalker` assumes that child
212 nodes (from __iter__()) are visited before the same nodes appear in
213 constructor arguments during depth-first postorder traversal.
214 '''
215
216
217
219 '''
220 Regenerate the constructor arguments (returns (args, kargs)).
221 '''
222 raise Exception('Not implemented')
223
226 '''
227 Constructor arguments are stored as attributes; their names are also
228 stored in order so that the arguments can be constructed. This assumes
229 that all names are unique. '*args' are named "without the *".
230 '''
231
236
238 '''
239 Add a single argument as a simple property.
240 '''
241 setattr(self, name, value)
242 return name
243
244 - def _arg(self, **kargs):
245 '''
246 Set a single named argument as an attribute (the signature uses kargs
247 so that the name does not need to be quoted). The attribute name is
248 added to self.__arg_names.
249 '''
250 assert len(kargs) == 1
251 for name in kargs:
252 self.__arg_names.append(self.__set_attribute(name, kargs[name]))
253
254 - def _karg(self, **kargs):
255 '''
256 Set a single keyword argument (ie with default) as an attribute (the
257 signature uses kargs so that the name does not need to be quoted).
258 The attribute name is added to self.__karg_names.
259 '''
260 assert len(kargs) == 1
261 for name in kargs:
262 self.__karg_names.append(self.__set_attribute(name, kargs[name]))
263
264 - def _args(self, **kargs):
275
283
285 '''
286 All (non-keyword) arguments.
287 '''
288 args = [getattr(self, name)
289 for name in self.__arg_names if not name.startswith('*')]
290 for name in self.__arg_names:
291 if name.startswith('*'):
292 args.extend(getattr(self, name[1:]))
293 return args
294
296 '''
297 All keyword argmuents.
298 '''
299 return dict((name, getattr(self, name)) for name in self.__karg_names)
300
302 '''
303 Regenerate the constructor arguments.
304 '''
305 return (self.__args(), self.__kargs())
306
308 '''
309 Return all children, in order.
310 '''
311 for arg in self.__args():
312 yield arg
313 for name in self.__karg_names:
314 yield getattr(self, name)
315
318 '''
319 The interface required by the walkers.
320
321 ``loop`` is value returned when a node is re-visited.
322
323 ``type_`` is set with the node type before constructor() is called. This
324 allows constructor() itself to be invoked with the Python arguments used to
325 construct the original graph.
326 '''
327
328 - def loop(self, value):
329 '''
330 Called on nodes that belong to a loop (eg. in the `ConstructorWalker`
331 nodes are visited in postorder, and this is called when a node is
332 *first* found as a constructor argument (before bing found in the
333 "postorder" traversal)).
334
335 By default, do nothing.
336 '''
337 pass
338
339 - def node(self, node):
340 '''
341 Called when first visiting a node.
342
343 By default, do nothing.
344 '''
345 pass
346
348 '''
349 Called for node instances. The args and kargs are the values for
350 the corresponding child nodes, as returned by this visitor.
351
352 By default, do nothing.
353 '''
354 pass
355
356 - def leaf(self, value):
357 '''
358 Called for children that are not node instances.
359
360 By default, do nothing.
361 '''
362 pass
363
364
365
366 - def postprocess(self, result):
367 '''
368 Called after walking, passed the match to the initial node.
369 '''
370 return result
371
374 '''
375 Tree walker (it handles cyclic graphs by ignoring repeated nodes).
376
377 This is based directly on the catamorphism of the graph. The visitor
378 encodes the type information. It may help to see the constructor
379 arguments as type constructors.
380
381 Nodes should be subclasses of `ConstructorGraphNode`.
382 '''
383
385 self.__root = root
386 self.__type = type_
387
399
401 '''
402 Collect arguments for the constructor.
403 '''
404
405
406
407 (old_args, old_kargs) = node._constructor_args()
408 (new_args, new_kargs) = ([], {})
409 for arg in old_args:
410 new_args.append(self.__value(arg, visitor, results))
411 for name in old_kargs:
412 new_kargs[name] = self.__value(old_kargs[name], visitor, results)
413 return (new_args, new_kargs)
414
415 - def __value(self, node, visitor, results):
416 '''
417 Get a value for a particular constructor argument.
418 '''
419 if isinstance(node, self.__type):
420 if node in results:
421 return results[node]
422 else:
423 return visitor.loop(node)
424 else:
425 return visitor.leaf(node)
426
429 '''
430 This works like `ConstructorWalker` for generic classes.
431 Since it has no knowledge of constructor arguments it assumes that all
432 children are passed like '*args'.
433
434 This allows visitors written for `ConstructorGraphNode` trees to be
435 used with arbitrary objects (as long as they follow the convention
436 described above).
437 '''
438
440 '''
441 Create a walker for the graph starting at the given node.
442 '''
443 self.__root = root
444 self.__type = type_
445
447 '''
448 Apply the visitor to the nodes in the graph, in postorder.
449 '''
450
451
452 pending = {}
453 for (parent, node, kind) in dfs_edges(self.__root, self.__type):
454 if kind & POSTORDER:
455 if safe_in(node, pending):
456 args = pending[node]
457 del pending[node]
458 else:
459 args = []
460 if parent not in pending:
461 pending[parent] = []
462 visitor.node(node)
463 if kind & LEAF:
464 pending[parent].append(visitor.leaf(node))
465 elif kind & NONTREE:
466 pending[parent].append(visitor.loop(node))
467 else:
468 pending[parent].append(visitor.constructor(*args))
469 return pending[self.__root][0]
470
471
472 -class PostorderWalkerMixin(object):
473 '''
474 Add a 'postorder' method.
475 '''
476
477 - def __init__(self):
478 super(PostorderWalkerMixin, self).__init__()
479 self.__postorder = None
480 self.__postorder_type = None
481
482 - def postorder(self, visitor, type_):
483 '''
484 A shortcut that allows a visitor to be applied postorder.
485 '''
486 if self.__postorder is None or self.__postorder_type != type_:
487 self.__postorder = ConstructorWalker(self, type_)
488 self.__postorder_type = type_
489 return self.__postorder(visitor)
490
493 '''
494 Used internally in `ConstructorStr`.
495 '''
496 pass
497
500 '''
501 Reconstruct the constructors used to generate the graph as a string
502 (useful for repr).
503
504 Internally, data is stored as a list of (indent, line) pairs.
505 '''
506
511
512 - def node(self, node):
513 '''
514 Store the node's class name for later use.
515 '''
516 try:
517 self.__name = node.delegate.__class__.__name__
518 except AttributeError:
519 self.__name = node.__class__.__name__
520
521 - def loop(self, value):
522 '''
523 Replace loop nodes by a <loop> marker.
524 '''
525 return [[0, '<loop>']]
526
528 '''
529 Build the constructor string, given the node and arguments.
530 '''
531 contents = []
532 for arg in args:
533 if contents:
534 contents[-1][1] += ', '
535 contents.extend([indent+1, line] for (indent, line) in arg)
536 for name in kargs:
537 if contents:
538 contents[-1][1] += ', '
539 arg = kargs[name]
540 contents.append([arg[0][0]+1, name + '=' + arg[0][1]])
541 contents.extend([indent+1, line] for (indent, line) in arg[1:])
542 lines = [[0, self.__name + '(']] + contents
543 lines[-1][1] += ')'
544 return lines
545
546 - def leaf(self, value):
547 '''
548 Non-node nodes (attributes) are displayed using repr.
549 '''
550 return [[0, repr(value)]]
551
552 - def postprocess(self, lines):
553 '''
554 This is an ad-hoc algorithm to make the final string reasonably
555 compact. It's ugly, bug-prone and completely arbitrary, but it
556 seems to work....
557 '''
558 sections = deque()
559 (scan, indent) = (0, -1)
560 while scan < len(lines):
561 (i, _) = lines[scan]
562 if i > indent:
563 indent = i
564 sections.append((indent, scan))
565 elif i < indent:
566 (scan, indent) = self.__compress(lines, sections.pop()[1], scan)
567 scan = scan + 1
568 while sections:
569 self.__compress(lines, sections.pop()[1], len(lines))
570 return self.__fmt(lines)
571
580
582 '''
583 Scrunch adjacent lines together.
584 '''
585 (indent, _) = lines[start]
586 while start+1 < stop:
587 if indent == lines[start][0] and \
588 (start+1 >= stop or indent == lines[start+1][0]) and \
589 (start+2 >= stop or indent == lines[start+2][0]) and \
590 indent + len(lines[start][1]) + len(lines[start+1][1]) < \
591 self.__line_length:
592 lines[start][1] += lines[start+1][1]
593 del lines[start+1]
594 stop -= 1
595 else:
596 start += 1
597 return (stop, indent-1)
598
615
616 @staticmethod
622
625 '''
626 Generate an ASCII graph of the nodes.
627
628 This should be used with `ConstructorWalker` and works rather like
629 cloning, except that instead of generating a new set of nodes we
630 generate a nested set of functions. This set of functions has the
631 same structure as the tree of nodes (we break cycles via loop).
632 The leaf functions take prefixes and return an ASCII picture of
633 what the leaf values should look like (including the prefixes).
634 Functions higher up the tree are similar, except instead of returning
635 a picture directly they extend the prefix and then call the functions
636 that are their children.
637
638 Once we have an entire tree of functions, we can call the root with
639 an empty prefix and the functions will "cascade" down, building the
640 prefixes necessary and passing them to the root functions that
641 generate the final ASCII data.
642 '''
643
647
648 - def loop(self, value):
649 '''
650 Mark loops (what else could we do?)
651 '''
652 return lambda first, rest, name: \
653 [first + name + (' ' if name else '') + '<loop>']
654
655 - def node(self, node):
656 '''
657 Store the class name.
658 '''
659 self._type = node.__class__.__name__
660
662 '''
663 Generate a function that can construct the local section of the
664 graph when given the appropriate prefixes.
665 '''
666 def fun(first, rest, name, type_=self._type):
667 '''
668 Build the ASCII picture; this is rather terse... First is the
669 prefix to the first line; rest is the prefix to the rest. Args
670 and Kargs are the equivalent functions for the constructor
671 arguments; we evaluate them here as we "expend" the ASCII
672 picture.
673
674 Does this need to be so complex - see my answer at
675 https://www.quora.com/Is-there-an-easy-way-to-print-trees-with-nodes-and-lines-maybe
676 '''
677 spec = []
678 for arg in args:
679 spec.append((' +- ', ' | ', '', arg))
680 for arg in kargs:
681 spec.append((' +- ', ' | ', arg, kargs[arg]))
682
683 if spec:
684 spec[-1] = (' `- ', ' ', spec[-1][2], spec[-1][3])
685 yield first + name + (' ' if name else '') + type_
686 for (first_, rest_, name_, fun_) in spec:
687 for line in fun_(first_, rest_, name_):
688 yield rest + line
689 return fun
690
691 - def leaf(self, value):
692 '''
693 Generate a function that can construct the local section of the
694 graph when given the appropriate prefixes.
695 '''
696 return lambda first, rest, name: \
697 [first + name + (' ' if name else '') + repr(value)]
698
699 - def postprocess(self, fun):
700 '''
701 Invoke the functions generated above and join the resulting lines.
702 '''
703 return '\n'.join(fun('', '', ''))
704
707 '''
708 A simple proxy that allows us to re-construct cyclic graphs. Used via
709 `make_proxy`.
710
711 Note - this is only used locally (in this module). When cloning LEPL
712 matcher graphs a different approach is used, based on `Delayed`.
713 '''
714
716 self.__mutable_delegate = mutable_delegate
717
719 return getattr(self.__mutable_delegate[0], name)
720
723 '''
724 Generate (setter, Proxy) pairs. The setter will supply the value to
725 be proxied later; the proxy itself can be place in the graph immediately.
726 '''
727 mutable_delegate = [None]
728 def setter(value):
729 '''
730 This is called later to "tie the knot".
731 '''
732 mutable_delegate[0] = value
733 return (setter, Proxy(mutable_delegate))
734
735
736 -def clone(node, args, kargs):
737 '''
738 The basic clone function that is supplied to `Clone`. This recreates
739 an instance based on its type and arguments.
740 '''
741 try:
742
743 return type(node)(*args, **kargs)
744 except TypeError as err:
745 raise TypeError(fmt('Error cloning {0} with ({1}, {2}): {3}',
746 type(node), args, kargs, err))
747
748
749 -class Clone(Visitor):
750 '''
751 Clone the graph, applying a particular clone function.
752 '''
753
755 super(Clone, self).__init__()
756 self._clone = clone_
757 self._proxies = {}
758 self._node = None
759
760 - def loop(self, node):
761 '''
762 Wrap loop nodes in proxies.
763 '''
764 if node not in self._proxies:
765 self._proxies[node] = make_proxy()
766 return self._proxies[node][1]
767
768 - def node(self, node):
769 '''
770 Store the current node.
771 '''
772 self._node = node
773
775 '''
776 Clone the node, back-patching proxies as necessary.
777 '''
778 node = self._clone(self._node, args, kargs)
779 if self._node in self._proxies:
780 self._proxies[self._node][0](node)
781 return node
782
783 - def leaf(self, value):
784 '''
785 Don't clone leaf nodes.
786 '''
787 return value
788
789
790 -def post_clone(function):
791 '''
792 Generate a clone function that applies the given function to the newly
793 constructed node (so, when used with `Clone`, effectively performs a
794 map on the graph).
795 '''
796 return compose(function, clone)
797