My favorites | Sign in
Project Home Downloads Wiki Issues Source
Repository:
Checkout   Browse   Changes   Clones  
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
# The contents of this file are subject to the Mozilla Public License
# (MPL) Version 1.1 (the "License"); you may not use this file except
# in compliance with the License. You may obtain a copy of the License
# at http://www.mozilla.org/MPL/
#
# Software distributed under the License is distributed on an "AS IS"
# basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
# the License for the specific language governing rights and
# limitations under the License.
#
# The Original Code is LEPL (http://www.acooke.org/lepl)
# The Initial Developer of the Original Code is Andrew Cooke.
# Portions created by the Initial Developer are Copyright (C) 2009-2010
# Andrew Cooke (andrew@acooke.org). All Rights Reserved.
#
# Alternatively, the contents of this file may be used under the terms
# of the LGPL license (the GNU Lesser General Public License,
# http://www.gnu.org/licenses/lgpl.html), in which case the provisions
# of the LGPL License are applicable instead of those above.
#
# If you wish to allow use of your version of this file only under the
# terms of the LGPL License and not to allow others to use your version
# of this file under the MPL, indicate your decision by deleting the
# provisions above and replace them with the notice and other provisions
# required by the LGPL License. If you do not delete the provisions
# above, a recipient may use your version of this file under either the
# MPL or the LGPL License.

'''
Graph traversal - supports generic Python classes, but has extensions for
classes that record their own constructor arguments (and so allow deep
cloning of graphs).

The fundamental `dfs_edges` routine will traverse over (ie provides an iterator
that returns (flag, node) pairs, where flag describes the type of node and
ordering) a graph made of iterable Python objects. Only the __iter__ method
(implemented by all containers) is required. However, in general this is too
broad (for example, Strings are iterable, and single character strings contain
themselves), so a type can be specified which identifies those nodes to
be treated as "interior" nodes. Children of interior nodes are returned as
"leaf" nodes, but are not iterated over themselves.

The `order` function provides a simpler interface to this traversal, allowing
a particular order to be generated, and, for example, optionally excluding leaf
nodes.

`ConstructorGraphNode` is motivated by data constructors and exposes its
constructor arguments (this is important because if we are cloning a graph
we want to replace constructor arguments that correspond to child nodes with
their clones). This currently has a single implementation,
`ArgAsAttributeMixin` (there used to be another, but it was equivalent to
the generic case with `SimpleWalker`).

The 'Walker' (`SimpleWalker` and `ConstructorWalker`) and `Visitor` classes
provide a different approach to traversing the graph (compared to the simple
sequences of nodes provided by `dfs_edges` et al), that reflects the emphasis
on constructors described above: the walker takes a visitor sub-class and
calls it in a way that replicates the original calls to the node constructors.
'''

from collections import Sequence, deque

from lepl.support.lib import compose, safe_in, empty, fmt, fallback_add


FORWARD = 1 # forward edge
BACKWARD = 2 # backward edge
NON_TREE = 4 # cyclic edge
ROOT = 8 # root node (not an edge)
NODE = 16 # child is a 'normal' node (of the given type)
LEAF = 32 # child is a leaf node (not the given type)

POSTORDER = BACKWARD | NON_TREE
PREORDER = FORWARD | NON_TREE


def dfs_edges(node, type_):
'''
Iterative DFS, based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py

Returns forward and reverse edges. Also returns root node in correct
order for pre- (FORWARD) and post- (BACKWARD) ordering.

``type_`` selects which values are iterated over. Children which are
not of this type are flagged with LEAF.
'''
while isinstance(node, type_):
try:
stack = [(node, iter(node), ROOT)]
yield node, node, FORWARD | ROOT
visited = set()
visited = fallback_add(visited, node)
while stack:
parent, children, p_type = stack[-1]
try:
child = next(children)
if isinstance(child, type_):
if safe_in(child, visited, False):
yield parent, child, NON_TREE
else:
stack.append((child, iter(child), NODE))
yield parent, child, FORWARD | NODE
visited = fallback_add(visited, child)
else:
stack.append((child, empty(), LEAF))
yield parent, child, FORWARD | LEAF
except StopIteration:
stack.pop()
if stack:
yield stack[-1][0], parent, BACKWARD | p_type
yield node, node, BACKWARD | ROOT
return
except Reset:
yield # in response to the throw (ignored by caller)


class Reset(Exception):
'''
An exception that can be passed to dfs_edges to reset the traversal.
'''
pass


def reset(generator):
'''
Reset the traversal by raising Reset.
'''
generator.throw(Reset())


def order(node, include, type_, exclude=0):
'''
An ordered sequence of nodes. The ordering is given by 'include' (see
the constants PREORDER etc above).
'''
while True:
try:
for (_parent, child, direction) in dfs_edges(node, type_):
if (direction & include) and not (direction & exclude):
yield child
return
except Reset:
yield # in response to the throw (ignored by caller)


def preorder(node, type_, exclude=0):
'''
The nodes in preorder.
'''
return order(node, PREORDER, type_, exclude=exclude)


def postorder(node, type_, exclude=0):
'''
The nodes in postorder.
'''
return order(node, POSTORDER, type_, exclude=exclude)


def leaves(node, type_=None):
'''
The leaf nodes.
'''
if type_ is None:
type_ = type(node)
return order(node, FORWARD, type_, exclude=NODE|ROOT)


def loops(node, type_):
'''
Return all loops from the given node.

Each loop is a list that starts and ends with the given node.
'''
stack = [[node]]
known = {node} # avoid getting lost in sub-loops
while stack:
ancestors = stack.pop()
parent = ancestors[-1]
if isinstance(parent, type_):
for child in parent:
family = list(ancestors)
family.append(child)
if child is node:
yield family
else:
if not safe_in(child, known):
stack.append(family)
known = fallback_add(known, child)


class ConstructorGraphNode(object):
'''
An interface that provides information on constructor arguments.

This is used by `ConstructorWalker` to provide the results of
walking child nodes in the same fmt as those nodes were provided in
the constructor. The main advantage is that the names of named
arguments are associated with the appropriate results.

For this to work correctly there is assumed to be a close relationship
between constructor arguments and children (there is a somewhat implicit
link between Python object constructors and type constructors in, say,
Haskell). Exactly how constructor argmuents and children match depends
on the implementation, but `ConstructorWalker` assumes that child
nodes (from __iter__()) are visited before the same nodes appear in
constructor arguments during depth-first postorder traversal.
'''

def _constructor_args(self):
'''
Regenerate the constructor arguments (returns (args, kargs)).
'''
raise Exception('Not implemented')


class ArgAsAttributeMixin(ConstructorGraphNode):
'''
Constructor arguments are stored as attributes; their names are also
stored in order so that the arguments can be constructed. This assumes
that all names are unique. '*args' are named "without the *".
'''

def __init__(self):
super(ArgAsAttributeMixin, self).__init__()
self.__arg_names = []
self.__karg_names = []

def __set_attribute(self, name, value):
'''
Add a single argument as a simple property.
'''
setattr(self, name, value)
return name

def _arg(self, **kargs):
'''
Set a single named argument as an attribute (the signature uses kargs
so that the name does not need to be quoted). The attribute name is
added to self.__arg_names.
'''
assert len(kargs) == 1
for name in kargs:
self.__arg_names.append(self.__set_attribute(name, kargs[name]))

def _karg(self, **kargs):
'''
Set a single keyword argument (ie with default) as an attribute (the
signature uses kargs so that the name does not need to be quoted).
The attribute name is added to self.__karg_names.
'''
assert len(kargs) == 1
for name in kargs:
self.__karg_names.append(self.__set_attribute(name, kargs[name]))

def _args(self, **kargs):
'''
Set a *arg as an attribute (the signature uses kargs so that the
attribute name does not need to be quoted). The name (without '*')
is added to self.__arg_names.
'''
assert len(kargs) == 1
for name in kargs:
assert isinstance(kargs[name], Sequence), kargs[name]
self.__arg_names.append('*' +
self.__set_attribute(name, kargs[name]))

def _kargs(self, kargs):
'''
Set **kargs as attributes. The attribute names are added to
self.__arg_names.
'''
for name in kargs:
self.__karg_names.append(self.__set_attribute(name, kargs[name]))

def __args(self):
'''
All (non-keyword) arguments.
'''
args = [getattr(self, name)
for name in self.__arg_names if not name.startswith('*')]
for name in self.__arg_names:
if name.startswith('*'):
args.extend(getattr(self, name[1:]))
return args

def __kargs(self):
'''
All keyword argmuents.
'''
return dict((name, getattr(self, name)) for name in self.__karg_names)

def _constructor_args(self):
'''
Regenerate the constructor arguments.
'''
return (self.__args(), self.__kargs())

def __iter__(self):
'''
Return all children, in order.
'''
for arg in self.__args():
yield arg
for name in self.__karg_names:
yield getattr(self, name)


class Visitor(object):
'''
The interface required by the walkers.

``loop`` is value returned when a node is re-visited.

``type_`` is set with the node type before constructor() is called. This
allows constructor() itself to be invoked with the Python arguments used to
construct the original graph.
'''

def loop(self, value):
'''
Called on nodes that belong to a loop (eg. in the `ConstructorWalker`
nodes are visited in postorder, and this is called when a node is
*first* found as a constructor argument (before bing found in the
"postorder" traversal)).

By default, do nothing.
'''
pass

def node(self, node):
'''
Called when first visiting a node.

By default, do nothing.
'''
pass

def constructor(self, *args, **kargs):
'''
Called for node instances. The args and kargs are the values for
the corresponding child nodes, as returned by this visitor.

By default, do nothing.
'''
pass

def leaf(self, value):
'''
Called for children that are not node instances.

By default, do nothing.
'''
pass

def postprocess(self, result):
'''
Called after walking, passed the match to the initial node.
'''
return result


class ConstructorWalker(object):
'''
Tree walker (it handles cyclic graphs by ignoring repeated nodes).

This is based directly on the catamorphism of the graph. The visitor
encodes the type information. It may help to see the constructor
arguments as type constructors.

Nodes should be subclasses of `ConstructorGraphNode`.
'''

def __init__(self, root, type_):
self.__root = root
self.__type = type_

def __call__(self, visitor):
'''
Apply the visitor to each node in turn.
'''
results = {}
for node in postorder(self.__root, self.__type, exclude=LEAF):
visitor.node(node)
(args, kargs) = self.__arguments(node, visitor, results)
results[node] = visitor.constructor(*args, **kargs)
return visitor.postprocess(results[self.__root])

def __arguments(self, node, visitor, results):
'''
Collect arguments for the constructor.
'''
(old_args, old_kargs) = node._constructor_args()
(new_args, new_kargs) = ([], {})
for arg in old_args:
new_args.append(self.__value(arg, visitor, results))
for name in old_kargs:
new_kargs[name] = self.__value(old_kargs[name], visitor, results)
return (new_args, new_kargs)

def __value(self, node, visitor, results):
'''
Get a value for a particular constructor argument.
'''
if isinstance(node, self.__type):
if node in results:
return results[node]
else:
return visitor.loop(node)
else:
return visitor.leaf(node)


class SimpleWalker(object):
'''
This works like `ConstructorWalker` for generic classes.
Since it has no knowledge of constructor arguments it assumes that all
children are passed like '*args'.

This allows visitors written for `ConstructorGraphNode` trees to be
used with arbitrary objects (as long as they follow the convention
described above).
'''

def __init__(self, root, type_):
'''
Create a walker for the graph starting at the given node.
'''
self.__root = root
self.__type = type_

def __call__(self, visitor):
'''
Apply the visitor to the nodes in the graph, in postorder.
'''
pending = {}
for (parent, node, kind) in dfs_edges(self.__root, self.__type):
if kind & POSTORDER:
if safe_in(node, pending):
args = pending[node]
del pending[node]
else:
args = []
if parent not in pending:
pending[parent] = []
visitor.node(node)
if kind & LEAF:
pending[parent].append(visitor.leaf(node))
elif kind & NON_TREE:
pending[parent].append(visitor.loop(node))
else:
pending[parent].append(visitor.constructor(*args))
return pending[self.__root][0]


class PostorderWalkerMixin(object):
'''
Add a 'postorder' method.
'''

def __init__(self):
super(PostorderWalkerMixin, self).__init__()
self.__postorder = None
self.__postorder_type = None

def postorder(self, visitor, type_):
'''
A shortcut that allows a visitor to be applied postorder.
'''
if self.__postorder is None or self.__postorder_type != type_:
self.__postorder = ConstructorWalker(self, type_)
self.__postorder_type = type_
return self.__postorder(visitor)


class _LineOverflow(Exception):
'''
Used internally in `ConstructorStr`.
'''
pass


class GraphStr(Visitor):
'''
Generate an ASCII graph of the nodes.

This should be used with `ConstructorWalker` and works rather like
cloning, except that instead of generating a new set of nodes we
generate a nested set of functions. This set of functions has the
same structure as the tree of nodes (we break cycles via loop).
The leaf functions take prefixes and return an ASCII picture of
what the leaf values should look like (including the prefixes).
Functions higher up the tree are similar, except instead of returning
a picture directly they extend the prefix and then call the functions
that are their children.

Once we have an entire tree of functions, we can call the root with
an empty prefix and the functions will "cascade" down, building the
prefixes necessary and passing them to the root functions that
generate the final ASCII data.
'''

def __init__(self):
super(GraphStr, self).__init__()
self._type = None

def loop(self, value):
'''
Mark loops (what else could we do?)
'''
return lambda first, rest, name: \
[first + name + (' ' if name else '') + '<loop>']

def node(self, node):
'''
Store the class name.
'''
self._type = node.__class__.__name__

def constructor(self, *args, **kargs):
'''
Generate a function that can construct the local section of the
graph when given the appropriate prefixes.
'''
def fun(first, rest, name, type_=self._type):
'''
Build the ASCII picture; this is rather terse... First is the
prefix to the first line; rest is the prefix to the rest. Args
and Kargs are the equivalent functions for the constructor
arguments; we evaluate them here as we "expend" the ASCII
picture.

Does this need to be so complex - see my answer at
https://www.quora.com/Is-there-an-easy-way-to-print-trees-with-nodes-and-lines-maybe
'''
spec = []
for arg in args:
spec.append((' +- ', ' | ', '', arg))
for arg in kargs:
spec.append((' +- ', ' | ', arg, kargs[arg]))
# fix the last branch
if spec:
spec[-1] = (' `- ', ' ', spec[-1][2], spec[-1][3])
yield first + name + (' ' if name else '') + type_
for (first_, rest_, name_, fun_) in spec:
for line in fun_(first_, rest_, name_):
yield rest + line
return fun

def leaf(self, value):
'''
Generate a function that can construct the local section of the
graph when given the appropriate prefixes.
'''
return lambda first, rest, name: \
[first + name + (' ' if name else '') + repr(value)]

def postprocess(self, fun):
'''
Invoke the functions generated above and join the resulting lines.
'''
return '\n'.join(fun('', '', ''))


class Proxy(object):
'''
A simple proxy that allows us to re-construct cyclic graphs. Used via
`make_proxy`.

Note - this is only used locally (in this module). When cloning LEPL
matcher graphs a different approach is used, based on `Delayed`.
'''

def __init__(self, mutable_delegate):
self.__mutable_delegate = mutable_delegate

def __getattr__(self, name):
return getattr(self.__mutable_delegate[0], name)


def make_proxy():
'''
Generate (setter, Proxy) pairs. The setter will supply the value to
be proxied later; the proxy itself can be place in the graph immediately.
'''
mutable_delegate = [None]
def setter(value):
'''
This is called later to "tie the knot".
'''
mutable_delegate[0] = value
return (setter, Proxy(mutable_delegate))


def clone(node, args, kargs):
'''
The basic clone function that is supplied to `Clone`. This recreates
an instance based on its type and arguments.
'''
try:
return type(node)(*args, **kargs)
except TypeError as err:
raise TypeError(fmt('Error cloning {0} with ({1}, {2}): {3}',
type(node), args, kargs, err))


class Clone(Visitor):
'''
Clone the graph, applying a particular clone function.
'''

def __init__(self, clone_=clone):
super(Clone, self).__init__()
self._clone = clone_
self._proxies = {}
self._node = None

def loop(self, node):
'''
Wrap loop nodes in proxies.
'''
if node not in self._proxies:
self._proxies[node] = make_proxy()
return self._proxies[node][1]

def node(self, node):
'''
Store the current node.
'''
self._node = node

def constructor(self, *args, **kargs):
'''
Clone the node, back-patching proxies as necessary.
'''
node = self._clone(self._node, args, kargs)
if self._node in self._proxies:
self._proxies[self._node][0](node)
return node

def leaf(self, value):
'''
Don't clone leaf nodes.
'''
return value


def post_clone(function):
'''
Generate a clone function that applies the given function to the newly
constructed node (so, when used with `Clone`, effectively performs a
map on the graph).
'''
return compose(function, clone)

Change log

7ae6957ff515 by and...@acooke.org on Jan 22, 2012   Diff
looking at pypy speed; cleaning out code.
Go to: 
Project members, sign in to write a code review

Older revisions

c7bdff29546a by and...@acooke.org on Jun 23, 2011   Diff
getting tests running
d0c0c1b67cfa by andrew on Mar 12, 2011   Diff
all tests ok
249af3234ee4 by andrew on Mar 7, 2011   Diff
improved (i think) rmemo + start of
cache level for streams.
committing now as about to try redo
lmemo.
All revisions of this file

File info

Size: 22075 bytes, 655 lines
Powered by Google Project Hosting