This repository was archived by the owner on Jan 3, 2026. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 24
Expand file tree
/
Copy pathalgorithm.py
More file actions
117 lines (97 loc) · 4.07 KB
/
algorithm.py
File metadata and controls
117 lines (97 loc) · 4.07 KB
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
"""
The :mod:`Diagnostic` module provides several commonly useful
algorithms that operate on abstract syntax trees.
"""
from __future__ import absolute_import, division, print_function, unicode_literals
from . import ast
class Visitor:
"""
A node visitor base class that does a traversal
of the abstract syntax tree.
This class is meant to be subclassed, with the subclass adding
visitor methods. The visitor method should call ``self.generic_visit(node)``
to continue the traversal; this allows to perform arbitrary
actions both before and after traversing the children of a node.
The visitor methods for the nodes are ``'visit_'`` +
class name of the node. So a `Try` node visit function would
be `visit_Try`.
"""
def generic_visit(self, node):
"""Called if no explicit visitor function exists for a node."""
for field_name in node._fields:
self.visit(getattr(node, field_name))
def _visit_one(self, node):
visit_attr = "visit_" + type(node).__name__
if hasattr(self, visit_attr):
return getattr(self, visit_attr)(node)
else:
return self.generic_visit(node)
def visit(self, obj):
"""Visit a node or a list of nodes. Other values are ignored"""
if isinstance(obj, list):
return [self.visit(elt) for elt in obj]
elif isinstance(obj, ast.AST):
return self._visit_one(obj)
class Transformer:
"""
A node transformer base class that does a post-order traversal
of the abstract syntax tree while allowing to replace or remove
the nodes being traversed.
The return value of the visitor methods is used to replace or remove
the old node. If the return value of the visitor method is ``None``,
the node will be removed from its location, otherwise it is replaced
with the return value. The return value may be the original node
in which case no replacement takes place.
This class is meant to be subclassed, with the subclass adding
visitor methods. The visitor method should call ``self.generic_visit(node)``
to continue the traversal; this allows to perform arbitrary
actions both before and after traversing the children of a node.
The visitor methods for the nodes are ``'visit_'`` +
class name of the node. So a `Try` node visit function would
be `visit_Try`.
"""
def generic_visit(self, node):
"""Called if no explicit visitor function exists for a node."""
for field_name in node._fields:
setattr(node, field_name, self.visit(getattr(node, field_name)))
return node
def _visit_one(self, node):
visit_attr = "visit_" + type(node).__name__
if hasattr(self, visit_attr):
return getattr(self, visit_attr)(node)
else:
return self.generic_visit(node)
def visit(self, obj):
"""Visit a node or a list of nodes. Other values are ignored"""
if isinstance(obj, list):
return list(filter(lambda x: x is not None, map(self.visit, obj)))
elif isinstance(obj, ast.AST):
return self._visit_one(obj)
else:
return obj
def compare(left, right, compare_locs=False):
"""
An AST comparison function. Returns ``True`` if all fields in
``left`` are equal to fields in ``right``; if ``compare_locs`` is
true, all locations should match as well.
"""
if type(left) != type(right):
return False
if isinstance(left, ast.AST):
for field in left._fields:
if not compare(getattr(left, field), getattr(right, field)):
return False
if compare_locs:
for loc in left._locs:
if getattr(left, loc) != getattr(right, loc):
return False
return True
elif isinstance(left, list):
if len(left) != len(right):
return False
for left_elt, right_elt in zip(left, right):
if not compare(left_elt, right_elt):
return False
return True
else:
return left == right