1class NodeVisitor(object):
2    def visit(self, node):
3        # This is ugly as hell, but we don't have multimethods and
4        # they aren't trivial to fake without access to the class
5        # object from the class body
6        func = getattr(self, "visit_%s" % (node.__class__.__name__))
7        return func(node)
8
9
10class Node(object):
11    def __init__(self, data=None):
12        self.data = data
13        self.parent = None
14        self.children = []
15
16    def append(self, other):
17        other.parent = self
18        self.children.append(other)
19
20    def remove(self):
21        self.parent.children.remove(self)
22
23    def __repr__(self):
24        return "<%s %s>" % (self.__class__.__name__, self.data)
25
26    def __str__(self):
27        rv = [repr(self)]
28        for item in self.children:
29            rv.extend("  %s" % line for line in str(item).split("\n"))
30        return "\n".join(rv)
31
32    def __eq__(self, other):
33        if not (self.__class__ == other.__class__ and
34                self.data == other.data and
35                len(self.children) == len(other.children)):
36            return False
37        for child, other_child in zip(self.children, other.children):
38            if not child == other_child:
39                return False
40        return True
41
42    def copy(self):
43        new = self.__class__(self.data)
44        for item in self.children:
45            new.append(item.copy())
46        return new
47
48
49class DataNode(Node):
50    def append(self, other):
51        # Append that retains the invariant that child data nodes
52        # come after child nodes of other types
53        other.parent = self
54        if isinstance(other, DataNode):
55            self.children.append(other)
56        else:
57            index = len(self.children)
58            while index > 0 and isinstance(self.children[index - 1], DataNode):
59                index -= 1
60            for i in range(index):
61                if other.data == self.children[i].data:
62                    raise ValueError("Duplicate key %s" % self.children[i].data)
63            self.children.insert(index, other)
64
65
66class KeyValueNode(Node):
67    def append(self, other):
68        # Append that retains the invariant that conditional nodes
69        # come before unconditional nodes
70        other.parent = self
71        if not isinstance(other, (ListNode, ValueNode, ConditionalNode)):
72            raise TypeError
73        if isinstance(other, (ListNode, ValueNode)):
74            if self.children:
75                assert not isinstance(self.children[-1], (ListNode, ValueNode))
76            self.children.append(other)
77        else:
78            if self.children and isinstance(self.children[-1], ValueNode):
79                self.children.insert(len(self.children) - 1, other)
80            else:
81                self.children.append(other)
82
83
84class ListNode(Node):
85    def append(self, other):
86        other.parent = self
87        self.children.append(other)
88
89
90class ValueNode(Node):
91    def append(self, other):
92        raise TypeError
93
94
95class AtomNode(ValueNode):
96    pass
97
98
99class ConditionalNode(Node):
100    def append(self, other):
101        if not len(self.children):
102            if not isinstance(other, (BinaryExpressionNode, UnaryExpressionNode, VariableNode)):
103                raise TypeError
104        else:
105            if len(self.children) > 1:
106                raise ValueError
107            if not isinstance(other, (ListNode, ValueNode)):
108                raise TypeError
109        other.parent = self
110        self.children.append(other)
111
112
113class UnaryExpressionNode(Node):
114    def __init__(self, operator, operand):
115        Node.__init__(self)
116        self.append(operator)
117        self.append(operand)
118
119    def append(self, other):
120        Node.append(self, other)
121        assert len(self.children) <= 2
122
123    def copy(self):
124        new = self.__class__(self.children[0].copy(),
125                             self.children[1].copy())
126        return new
127
128
129class BinaryExpressionNode(Node):
130    def __init__(self, operator, operand_0, operand_1):
131        Node.__init__(self)
132        self.append(operator)
133        self.append(operand_0)
134        self.append(operand_1)
135
136    def append(self, other):
137        Node.append(self, other)
138        assert len(self.children) <= 3
139
140    def copy(self):
141        new = self.__class__(self.children[0].copy(),
142                             self.children[1].copy(),
143                             self.children[2].copy())
144        return new
145
146
147class UnaryOperatorNode(Node):
148    def append(self, other):
149        raise TypeError
150
151
152class BinaryOperatorNode(Node):
153    def append(self, other):
154        raise TypeError
155
156
157class IndexNode(Node):
158    pass
159
160
161class VariableNode(Node):
162    pass
163
164
165class StringNode(Node):
166    pass
167
168
169class NumberNode(ValueNode):
170    pass
171