1# -*- coding: utf-8 -*-
2
3import os
4import unittest
5from StringIO import StringIO
6
7from antlr3.tree import (CommonTreeNodeStream, CommonTree, CommonTreeAdaptor,
8                         TreeParser, TreeVisitor, TreeIterator)
9from antlr3 import CommonToken, UP, DOWN, EOF
10from antlr3.treewizard import TreeWizard
11
12class TestTreeNodeStream(unittest.TestCase):
13    """Test case for the TreeNodeStream class."""
14
15    def setUp(self):
16        self.adaptor = CommonTreeAdaptor()
17
18
19    def newStream(self, t):
20        """Build new stream; let's us override to test other streams."""
21        return CommonTreeNodeStream(t)
22
23
24    def testSingleNode(self):
25        t = CommonTree(CommonToken(101))
26
27        stream = self.newStream(t)
28        expecting = "101"
29        found = self.toNodesOnlyString(stream)
30        self.failUnlessEqual(expecting, found)
31
32        expecting = "101"
33        found = str(stream)
34        self.failUnlessEqual(expecting, found)
35
36
37    def testTwoChildrenOfNilRoot(self):
38        class V(CommonTree):
39            def __init__(self, token=None, ttype=None, x=None):
40                if x is not None:
41                    self.x = x
42
43                if ttype is not None and token is None:
44                    self.token = CommonToken(type=ttype)
45
46                if token is not None:
47                    self.token = token
48
49            def __str__(self):
50                if self.token is not None:
51                    txt = self.token.text
52                else:
53                    txt = ""
54
55                txt += "<V>"
56                return txt
57
58        root_0 = self.adaptor.nil();
59        t = V(ttype=101, x=2)
60        u = V(token=CommonToken(type=102, text="102"))
61        self.adaptor.addChild(root_0, t)
62        self.adaptor.addChild(root_0, u)
63        self.assert_(root_0.parent is None)
64        self.assertEquals(-1, root_0.childIndex)
65        self.assertEquals(0, t.childIndex)
66        self.assertEquals(1, u.childIndex)
67
68
69    def test4Nodes(self):
70        # ^(101 ^(102 103) 104)
71        t = CommonTree(CommonToken(101))
72        t.addChild(CommonTree(CommonToken(102)))
73        t.getChild(0).addChild(CommonTree(CommonToken(103)))
74        t.addChild(CommonTree(CommonToken(104)))
75
76        stream = self.newStream(t)
77        expecting = "101 102 103 104"
78        found = self.toNodesOnlyString(stream)
79        self.failUnlessEqual(expecting, found)
80
81        expecting = "101 2 102 2 103 3 104 3"
82        found = str(stream)
83        self.failUnlessEqual(expecting, found)
84
85
86    def testList(self):
87        root = CommonTree(None)
88
89        t = CommonTree(CommonToken(101))
90        t.addChild(CommonTree(CommonToken(102)))
91        t.getChild(0).addChild(CommonTree(CommonToken(103)))
92        t.addChild(CommonTree(CommonToken(104)))
93
94        u = CommonTree(CommonToken(105))
95
96        root.addChild(t)
97        root.addChild(u)
98
99        stream = CommonTreeNodeStream(root)
100        expecting = "101 102 103 104 105"
101        found = self.toNodesOnlyString(stream)
102        self.failUnlessEqual(expecting, found)
103
104        expecting = "101 2 102 2 103 3 104 3 105"
105        found = str(stream)
106        self.failUnlessEqual(expecting, found)
107
108
109    def testFlatList(self):
110        root = CommonTree(None)
111
112        root.addChild(CommonTree(CommonToken(101)))
113        root.addChild(CommonTree(CommonToken(102)))
114        root.addChild(CommonTree(CommonToken(103)))
115
116        stream = CommonTreeNodeStream(root)
117        expecting = "101 102 103"
118        found = self.toNodesOnlyString(stream)
119        self.failUnlessEqual(expecting, found)
120
121        expecting = "101 102 103"
122        found = str(stream)
123        self.failUnlessEqual(expecting, found)
124
125
126    def testListWithOneNode(self):
127        root = CommonTree(None)
128
129        root.addChild(CommonTree(CommonToken(101)))
130
131        stream = CommonTreeNodeStream(root)
132        expecting = "101"
133        found = self.toNodesOnlyString(stream)
134        self.failUnlessEqual(expecting, found)
135
136        expecting = "101"
137        found = str(stream)
138        self.failUnlessEqual(expecting, found)
139
140
141    def testAoverB(self):
142        t = CommonTree(CommonToken(101))
143        t.addChild(CommonTree(CommonToken(102)))
144
145        stream = self.newStream(t)
146        expecting = "101 102"
147        found = self.toNodesOnlyString(stream)
148        self.failUnlessEqual(expecting, found)
149
150        expecting = "101 2 102 3"
151        found = str(stream)
152        self.failUnlessEqual(expecting, found)
153
154
155    def testLT(self):
156        # ^(101 ^(102 103) 104)
157        t = CommonTree(CommonToken(101))
158        t.addChild(CommonTree(CommonToken(102)))
159        t.getChild(0).addChild(CommonTree(CommonToken(103)))
160        t.addChild(CommonTree(CommonToken(104)))
161
162        stream = self.newStream(t)
163        self.failUnlessEqual(101, stream.LT(1).getType())
164        self.failUnlessEqual(DOWN, stream.LT(2).getType())
165        self.failUnlessEqual(102, stream.LT(3).getType())
166        self.failUnlessEqual(DOWN, stream.LT(4).getType())
167        self.failUnlessEqual(103, stream.LT(5).getType())
168        self.failUnlessEqual(UP, stream.LT(6).getType())
169        self.failUnlessEqual(104, stream.LT(7).getType())
170        self.failUnlessEqual(UP, stream.LT(8).getType())
171        self.failUnlessEqual(EOF, stream.LT(9).getType())
172        # check way ahead
173        self.failUnlessEqual(EOF, stream.LT(100).getType())
174
175
176    def testMarkRewindEntire(self):
177        # ^(101 ^(102 103 ^(106 107) ) 104 105)
178        # stream has 7 real + 6 nav nodes
179        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
180        r0 = CommonTree(CommonToken(101))
181        r1 = CommonTree(CommonToken(102))
182        r0.addChild(r1)
183        r1.addChild(CommonTree(CommonToken(103)))
184        r2 = CommonTree(CommonToken(106))
185        r2.addChild(CommonTree(CommonToken(107)))
186        r1.addChild(r2)
187        r0.addChild(CommonTree(CommonToken(104)))
188        r0.addChild(CommonTree(CommonToken(105)))
189
190        stream = CommonTreeNodeStream(r0)
191        m = stream.mark() # MARK
192        for _ in range(13): # consume til end
193            stream.LT(1)
194            stream.consume()
195
196        self.failUnlessEqual(EOF, stream.LT(1).getType())
197        self.failUnlessEqual(UP, stream.LT(-1).getType())  #TODO: remove?
198        stream.rewind(m)      # REWIND
199
200        # consume til end again :)
201        for _ in range(13): # consume til end
202            stream.LT(1)
203            stream.consume()
204
205        self.failUnlessEqual(EOF, stream.LT(1).getType())
206        self.failUnlessEqual(UP, stream.LT(-1).getType())  #TODO: remove?
207
208
209    def testMarkRewindInMiddle(self):
210        # ^(101 ^(102 103 ^(106 107) ) 104 105)
211        # stream has 7 real + 6 nav nodes
212        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
213        r0 = CommonTree(CommonToken(101))
214        r1 = CommonTree(CommonToken(102))
215        r0.addChild(r1)
216        r1.addChild(CommonTree(CommonToken(103)))
217        r2 = CommonTree(CommonToken(106))
218        r2.addChild(CommonTree(CommonToken(107)))
219        r1.addChild(r2)
220        r0.addChild(CommonTree(CommonToken(104)))
221        r0.addChild(CommonTree(CommonToken(105)))
222
223        stream = CommonTreeNodeStream(r0)
224        for _ in range(7): # consume til middle
225            #System.out.println(tream.LT(1).getType())
226            stream.consume()
227
228        self.failUnlessEqual(107, stream.LT(1).getType())
229        m = stream.mark() # MARK
230        stream.consume() # consume 107
231        stream.consume() # consume UP
232        stream.consume() # consume UP
233        stream.consume() # consume 104
234        stream.rewind(m)      # REWIND
235
236        self.failUnlessEqual(107, stream.LT(1).getType())
237        stream.consume()
238        self.failUnlessEqual(UP, stream.LT(1).getType())
239        stream.consume()
240        self.failUnlessEqual(UP, stream.LT(1).getType())
241        stream.consume()
242        self.failUnlessEqual(104, stream.LT(1).getType())
243        stream.consume()
244        # now we're past rewind position
245        self.failUnlessEqual(105, stream.LT(1).getType())
246        stream.consume()
247        self.failUnlessEqual(UP, stream.LT(1).getType())
248        stream.consume()
249        self.failUnlessEqual(EOF, stream.LT(1).getType())
250        self.failUnlessEqual(UP, stream.LT(-1).getType())
251
252
253    def testMarkRewindNested(self):
254        # ^(101 ^(102 103 ^(106 107) ) 104 105)
255        # stream has 7 real + 6 nav nodes
256        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
257        r0 = CommonTree(CommonToken(101))
258        r1 = CommonTree(CommonToken(102))
259        r0.addChild(r1)
260        r1.addChild(CommonTree(CommonToken(103)))
261        r2 = CommonTree(CommonToken(106))
262        r2.addChild(CommonTree(CommonToken(107)))
263        r1.addChild(r2)
264        r0.addChild(CommonTree(CommonToken(104)))
265        r0.addChild(CommonTree(CommonToken(105)))
266
267        stream = CommonTreeNodeStream(r0)
268        m = stream.mark() # MARK at start
269        stream.consume() # consume 101
270        stream.consume() # consume DN
271        m2 = stream.mark() # MARK on 102
272        stream.consume() # consume 102
273        stream.consume() # consume DN
274        stream.consume() # consume 103
275        stream.consume() # consume 106
276        stream.rewind(m2)      # REWIND to 102
277        self.failUnlessEqual(102, stream.LT(1).getType())
278        stream.consume()
279        self.failUnlessEqual(DOWN, stream.LT(1).getType())
280        stream.consume()
281        # stop at 103 and rewind to start
282        stream.rewind(m) # REWIND to 101
283        self.failUnlessEqual(101, stream.LT(1).getType())
284        stream.consume()
285        self.failUnlessEqual(DOWN, stream.LT(1).getType())
286        stream.consume()
287        self.failUnlessEqual(102, stream.LT(1).getType())
288        stream.consume()
289        self.failUnlessEqual(DOWN, stream.LT(1).getType())
290
291
292    def testSeek(self):
293        # ^(101 ^(102 103 ^(106 107) ) 104 105)
294        # stream has 7 real + 6 nav nodes
295        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
296        r0 = CommonTree(CommonToken(101))
297        r1 = CommonTree(CommonToken(102))
298        r0.addChild(r1)
299        r1.addChild(CommonTree(CommonToken(103)))
300        r2 = CommonTree(CommonToken(106))
301        r2.addChild(CommonTree(CommonToken(107)))
302        r1.addChild(r2)
303        r0.addChild(CommonTree(CommonToken(104)))
304        r0.addChild(CommonTree(CommonToken(105)))
305
306        stream = CommonTreeNodeStream(r0)
307        stream.consume() # consume 101
308        stream.consume() # consume DN
309        stream.consume() # consume 102
310        stream.seek(7)   # seek to 107
311        self.failUnlessEqual(107, stream.LT(1).getType())
312        stream.consume() # consume 107
313        stream.consume() # consume UP
314        stream.consume() # consume UP
315        self.failUnlessEqual(104, stream.LT(1).getType())
316
317
318    def testSeekFromStart(self):
319        # ^(101 ^(102 103 ^(106 107) ) 104 105)
320        # stream has 7 real + 6 nav nodes
321        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
322        r0 = CommonTree(CommonToken(101))
323        r1 = CommonTree(CommonToken(102))
324        r0.addChild(r1)
325        r1.addChild(CommonTree(CommonToken(103)))
326        r2 = CommonTree(CommonToken(106))
327        r2.addChild(CommonTree(CommonToken(107)))
328        r1.addChild(r2)
329        r0.addChild(CommonTree(CommonToken(104)))
330        r0.addChild(CommonTree(CommonToken(105)))
331
332        stream = CommonTreeNodeStream(r0)
333        stream.seek(7)   # seek to 107
334        self.failUnlessEqual(107, stream.LT(1).getType())
335        stream.consume() # consume 107
336        stream.consume() # consume UP
337        stream.consume() # consume UP
338        self.failUnlessEqual(104, stream.LT(1).getType())
339
340
341    def testReset(self):
342        # ^(101 ^(102 103 ^(106 107) ) 104 105)
343        # stream has 7 real + 6 nav nodes
344        # Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
345        r0 = CommonTree(CommonToken(101))
346        r1 = CommonTree(CommonToken(102))
347        r0.addChild(r1)
348        r1.addChild(CommonTree(CommonToken(103)))
349        r2 = CommonTree(CommonToken(106))
350        r2.addChild(CommonTree(CommonToken(107)))
351        r1.addChild(r2)
352        r0.addChild(CommonTree(CommonToken(104)))
353        r0.addChild(CommonTree(CommonToken(105)))
354
355        stream = CommonTreeNodeStream(r0)
356        v1 = self.toNodesOnlyString(stream) # scan all
357        stream.reset()
358        v2 = self.toNodesOnlyString(stream) # scan all
359        self.assertEquals(v1, v2)
360
361
362    def testIterator(self):
363        r0 = CommonTree(CommonToken(101))
364        r1 = CommonTree(CommonToken(102))
365        r0.addChild(r1)
366        r1.addChild(CommonTree(CommonToken(103)))
367        r2 = CommonTree(CommonToken(106))
368        r2.addChild(CommonTree(CommonToken(107)))
369        r1.addChild(r2)
370        r0.addChild(CommonTree(CommonToken(104)))
371        r0.addChild(CommonTree(CommonToken(105)))
372
373        stream = CommonTreeNodeStream(r0)
374
375        expecting = [
376            101, DOWN, 102, DOWN, 103, 106, DOWN, 107, UP, UP, 104, 105, UP]
377        found = [t.type for t in stream]
378        self.assertEqual(expecting, found)
379
380
381    def toNodesOnlyString(self, nodes):
382        buf = []
383        for i in range(nodes.size()):
384            t = nodes.LT(i+1)
385            type = nodes.getTreeAdaptor().getType(t)
386            if not (type==DOWN or type==UP):
387                buf.append(str(type))
388
389        return ' '.join(buf)
390
391
392class TestCommonTreeNodeStream(unittest.TestCase):
393    """Test case for the CommonTreeNodeStream class."""
394
395    def testPushPop(self):
396        # ^(101 ^(102 103) ^(104 105) ^(106 107) 108 109)
397        # stream has 9 real + 8 nav nodes
398        # Sequence of types: 101 DN 102 DN 103 UP 104 DN 105 UP 106 DN 107 UP 108 109 UP
399        r0 = CommonTree(CommonToken(101))
400        r1 = CommonTree(CommonToken(102))
401        r1.addChild(CommonTree(CommonToken(103)))
402        r0.addChild(r1)
403        r2 = CommonTree(CommonToken(104))
404        r2.addChild(CommonTree(CommonToken(105)))
405        r0.addChild(r2)
406        r3 = CommonTree(CommonToken(106))
407        r3.addChild(CommonTree(CommonToken(107)))
408        r0.addChild(r3)
409        r0.addChild(CommonTree(CommonToken(108)))
410        r0.addChild(CommonTree(CommonToken(109)))
411
412        stream = CommonTreeNodeStream(r0)
413        expecting = "101 2 102 2 103 3 104 2 105 3 106 2 107 3 108 109 3"
414        found = str(stream)
415        self.failUnlessEqual(expecting, found)
416
417        # Assume we want to hit node 107 and then "call 102" then return
418
419        indexOf102 = 2
420        indexOf107 = 12
421        for _ in range(indexOf107):# consume til 107 node
422            stream.consume()
423
424        # CALL 102
425        self.failUnlessEqual(107, stream.LT(1).getType())
426        stream.push(indexOf102)
427        self.failUnlessEqual(102, stream.LT(1).getType())
428        stream.consume() # consume 102
429        self.failUnlessEqual(DOWN, stream.LT(1).getType())
430        stream.consume() # consume DN
431        self.failUnlessEqual(103, stream.LT(1).getType())
432        stream.consume() # consume 103
433        self.failUnlessEqual(UP, stream.LT(1).getType())
434        # RETURN
435        stream.pop()
436        self.failUnlessEqual(107, stream.LT(1).getType())
437
438
439    def testNestedPushPop(self):
440        # ^(101 ^(102 103) ^(104 105) ^(106 107) 108 109)
441        # stream has 9 real + 8 nav nodes
442        # Sequence of types: 101 DN 102 DN 103 UP 104 DN 105 UP 106 DN 107 UP 108 109 UP
443        r0 = CommonTree(CommonToken(101))
444        r1 = CommonTree(CommonToken(102))
445        r1.addChild(CommonTree(CommonToken(103)))
446        r0.addChild(r1)
447        r2 = CommonTree(CommonToken(104))
448        r2.addChild(CommonTree(CommonToken(105)))
449        r0.addChild(r2)
450        r3 = CommonTree(CommonToken(106))
451        r3.addChild(CommonTree(CommonToken(107)))
452        r0.addChild(r3)
453        r0.addChild(CommonTree(CommonToken(108)))
454        r0.addChild(CommonTree(CommonToken(109)))
455
456        stream = CommonTreeNodeStream(r0)
457
458        # Assume we want to hit node 107 and then "call 102", which
459        # calls 104, then return
460
461        indexOf102 = 2
462        indexOf107 = 12
463        for _ in range(indexOf107): # consume til 107 node
464            stream.consume()
465
466        self.failUnlessEqual(107, stream.LT(1).getType())
467        # CALL 102
468        stream.push(indexOf102)
469        self.failUnlessEqual(102, stream.LT(1).getType())
470        stream.consume() # consume 102
471        self.failUnlessEqual(DOWN, stream.LT(1).getType())
472        stream.consume() # consume DN
473        self.failUnlessEqual(103, stream.LT(1).getType())
474        stream.consume() # consume 103
475
476        # CALL 104
477        indexOf104 = 6
478        stream.push(indexOf104)
479        self.failUnlessEqual(104, stream.LT(1).getType())
480        stream.consume() # consume 102
481        self.failUnlessEqual(DOWN, stream.LT(1).getType())
482        stream.consume() # consume DN
483        self.failUnlessEqual(105, stream.LT(1).getType())
484        stream.consume() # consume 103
485        self.failUnlessEqual(UP, stream.LT(1).getType())
486        # RETURN (to UP node in 102 subtree)
487        stream.pop()
488
489        self.failUnlessEqual(UP, stream.LT(1).getType())
490        # RETURN (to empty stack)
491        stream.pop()
492        self.failUnlessEqual(107, stream.LT(1).getType())
493
494
495    def testPushPopFromEOF(self):
496        # ^(101 ^(102 103) ^(104 105) ^(106 107) 108 109)
497        # stream has 9 real + 8 nav nodes
498        # Sequence of types: 101 DN 102 DN 103 UP 104 DN 105 UP 106 DN 107 UP 108 109 UP
499        r0 = CommonTree(CommonToken(101))
500        r1 = CommonTree(CommonToken(102))
501        r1.addChild(CommonTree(CommonToken(103)))
502        r0.addChild(r1)
503        r2 = CommonTree(CommonToken(104))
504        r2.addChild(CommonTree(CommonToken(105)))
505        r0.addChild(r2)
506        r3 = CommonTree(CommonToken(106))
507        r3.addChild(CommonTree(CommonToken(107)))
508        r0.addChild(r3)
509        r0.addChild(CommonTree(CommonToken(108)))
510        r0.addChild(CommonTree(CommonToken(109)))
511
512        stream = CommonTreeNodeStream(r0)
513
514        while stream.LA(1) != EOF:
515            stream.consume()
516
517        indexOf102 = 2
518        indexOf104 = 6
519        self.failUnlessEqual(EOF, stream.LT(1).getType())
520
521        # CALL 102
522        stream.push(indexOf102)
523        self.failUnlessEqual(102, stream.LT(1).getType())
524        stream.consume() # consume 102
525        self.failUnlessEqual(DOWN, stream.LT(1).getType())
526        stream.consume() # consume DN
527        self.failUnlessEqual(103, stream.LT(1).getType())
528        stream.consume() # consume 103
529        self.failUnlessEqual(UP, stream.LT(1).getType())
530        # RETURN (to empty stack)
531        stream.pop()
532        self.failUnlessEqual(EOF, stream.LT(1).getType())
533
534        # CALL 104
535        stream.push(indexOf104)
536        self.failUnlessEqual(104, stream.LT(1).getType())
537        stream.consume() # consume 102
538        self.failUnlessEqual(DOWN, stream.LT(1).getType())
539        stream.consume() # consume DN
540        self.failUnlessEqual(105, stream.LT(1).getType())
541        stream.consume() # consume 103
542        self.failUnlessEqual(UP, stream.LT(1).getType())
543        # RETURN (to empty stack)
544        stream.pop()
545        self.failUnlessEqual(EOF, stream.LT(1).getType())
546
547
548class TestCommonTree(unittest.TestCase):
549    """Test case for the CommonTree class."""
550
551    def setUp(self):
552        """Setup test fixure"""
553
554        self.adaptor = CommonTreeAdaptor()
555
556
557    def testSingleNode(self):
558        t = CommonTree(CommonToken(101))
559        self.failUnless(t.parent is None)
560        self.failUnlessEqual(-1, t.childIndex)
561
562
563    def test4Nodes(self):
564        # ^(101 ^(102 103) 104)
565        r0 = CommonTree(CommonToken(101))
566        r0.addChild(CommonTree(CommonToken(102)))
567        r0.getChild(0).addChild(CommonTree(CommonToken(103)))
568        r0.addChild(CommonTree(CommonToken(104)))
569
570        self.failUnless(r0.parent is None)
571        self.failUnlessEqual(-1, r0.childIndex)
572
573
574    def testList(self):
575        # ^(nil 101 102 103)
576        r0 = CommonTree(None)
577        c0=CommonTree(CommonToken(101))
578        r0.addChild(c0)
579        c1=CommonTree(CommonToken(102))
580        r0.addChild(c1)
581        c2=CommonTree(CommonToken(103))
582        r0.addChild(c2)
583
584        self.failUnless(r0.parent is None)
585        self.failUnlessEqual(-1, r0.childIndex)
586        self.failUnlessEqual(r0, c0.parent)
587        self.failUnlessEqual(0, c0.childIndex)
588        self.failUnlessEqual(r0, c1.parent)
589        self.failUnlessEqual(1, c1.childIndex)
590        self.failUnlessEqual(r0, c2.parent)
591        self.failUnlessEqual(2, c2.childIndex)
592
593
594    def testList2(self):
595        # Add child ^(nil 101 102 103) to root 5
596        # should pull 101 102 103 directly to become 5's child list
597        root = CommonTree(CommonToken(5))
598
599        # child tree
600        r0 = CommonTree(None)
601        c0=CommonTree(CommonToken(101))
602        r0.addChild(c0)
603        c1=CommonTree(CommonToken(102))
604        r0.addChild(c1)
605        c2=CommonTree(CommonToken(103))
606        r0.addChild(c2)
607
608        root.addChild(r0)
609
610        self.failUnless(root.parent is None)
611        self.failUnlessEqual(-1, root.childIndex)
612        # check children of root all point at root
613        self.failUnlessEqual(root, c0.parent)
614        self.failUnlessEqual(0, c0.childIndex)
615        self.failUnlessEqual(root, c0.parent)
616        self.failUnlessEqual(1, c1.childIndex)
617        self.failUnlessEqual(root, c0.parent)
618        self.failUnlessEqual(2, c2.childIndex)
619
620
621    def testAddListToExistChildren(self):
622        # Add child ^(nil 101 102 103) to root ^(5 6)
623        # should add 101 102 103 to end of 5's child list
624        root = CommonTree(CommonToken(5))
625        root.addChild(CommonTree(CommonToken(6)))
626
627        # child tree
628        r0 = CommonTree(None)
629        c0=CommonTree(CommonToken(101))
630        r0.addChild(c0)
631        c1=CommonTree(CommonToken(102))
632        r0.addChild(c1)
633        c2=CommonTree(CommonToken(103))
634        r0.addChild(c2)
635
636        root.addChild(r0)
637
638        self.failUnless(root.parent is None)
639        self.failUnlessEqual(-1, root.childIndex)
640        # check children of root all point at root
641        self.failUnlessEqual(root, c0.parent)
642        self.failUnlessEqual(1, c0.childIndex)
643        self.failUnlessEqual(root, c0.parent)
644        self.failUnlessEqual(2, c1.childIndex)
645        self.failUnlessEqual(root, c0.parent)
646        self.failUnlessEqual(3, c2.childIndex)
647
648
649    def testDupTree(self):
650        # ^(101 ^(102 103 ^(106 107) ) 104 105)
651        r0 = CommonTree(CommonToken(101))
652        r1 = CommonTree(CommonToken(102))
653        r0.addChild(r1)
654        r1.addChild(CommonTree(CommonToken(103)))
655        r2 = CommonTree(CommonToken(106))
656        r2.addChild(CommonTree(CommonToken(107)))
657        r1.addChild(r2)
658        r0.addChild(CommonTree(CommonToken(104)))
659        r0.addChild(CommonTree(CommonToken(105)))
660
661        dup = self.adaptor.dupTree(r0)
662
663        self.failUnless(dup.parent is None)
664        self.failUnlessEqual(-1, dup.childIndex)
665        dup.sanityCheckParentAndChildIndexes()
666
667
668    def testBecomeRoot(self):
669        # 5 becomes root of ^(nil 101 102 103)
670        newRoot = CommonTree(CommonToken(5))
671
672        oldRoot = CommonTree(None)
673        oldRoot.addChild(CommonTree(CommonToken(101)))
674        oldRoot.addChild(CommonTree(CommonToken(102)))
675        oldRoot.addChild(CommonTree(CommonToken(103)))
676
677        self.adaptor.becomeRoot(newRoot, oldRoot)
678        newRoot.sanityCheckParentAndChildIndexes()
679
680
681    def testBecomeRoot2(self):
682        # 5 becomes root of ^(101 102 103)
683        newRoot = CommonTree(CommonToken(5))
684
685        oldRoot = CommonTree(CommonToken(101))
686        oldRoot.addChild(CommonTree(CommonToken(102)))
687        oldRoot.addChild(CommonTree(CommonToken(103)))
688
689        self.adaptor.becomeRoot(newRoot, oldRoot)
690        newRoot.sanityCheckParentAndChildIndexes()
691
692
693    def testBecomeRoot3(self):
694        # ^(nil 5) becomes root of ^(nil 101 102 103)
695        newRoot = CommonTree(None)
696        newRoot.addChild(CommonTree(CommonToken(5)))
697
698        oldRoot = CommonTree(None)
699        oldRoot.addChild(CommonTree(CommonToken(101)))
700        oldRoot.addChild(CommonTree(CommonToken(102)))
701        oldRoot.addChild(CommonTree(CommonToken(103)))
702
703        self.adaptor.becomeRoot(newRoot, oldRoot)
704        newRoot.sanityCheckParentAndChildIndexes()
705
706
707    def testBecomeRoot5(self):
708        # ^(nil 5) becomes root of ^(101 102 103)
709        newRoot = CommonTree(None)
710        newRoot.addChild(CommonTree(CommonToken(5)))
711
712        oldRoot = CommonTree(CommonToken(101))
713        oldRoot.addChild(CommonTree(CommonToken(102)))
714        oldRoot.addChild(CommonTree(CommonToken(103)))
715
716        self.adaptor.becomeRoot(newRoot, oldRoot)
717        newRoot.sanityCheckParentAndChildIndexes()
718
719
720    def testBecomeRoot6(self):
721        # emulates construction of ^(5 6)
722        root_0 = self.adaptor.nil()
723        root_1 = self.adaptor.nil()
724        root_1 = self.adaptor.becomeRoot(CommonTree(CommonToken(5)), root_1)
725
726        self.adaptor.addChild(root_1, CommonTree(CommonToken(6)))
727
728        self.adaptor.addChild(root_0, root_1)
729
730        root_0.sanityCheckParentAndChildIndexes()
731
732
733    # Test replaceChildren
734
735    def testReplaceWithNoChildren(self):
736        t = CommonTree(CommonToken(101))
737        newChild = CommonTree(CommonToken(5))
738        error = False
739        try:
740        	t.replaceChildren(0, 0, newChild)
741
742        except IndexError:
743        	error = True
744
745        self.failUnless(error)
746
747
748    def testReplaceWithOneChildren(self):
749        # assume token type 99 and use text
750        t = CommonTree(CommonToken(99, text="a"))
751        c0 = CommonTree(CommonToken(99, text="b"))
752        t.addChild(c0)
753
754        newChild = CommonTree(CommonToken(99, text="c"))
755        t.replaceChildren(0, 0, newChild)
756        expecting = "(a c)"
757        self.failUnlessEqual(expecting, t.toStringTree())
758        t.sanityCheckParentAndChildIndexes()
759
760
761    def testReplaceInMiddle(self):
762        t = CommonTree(CommonToken(99, text="a"))
763        t.addChild(CommonTree(CommonToken(99, text="b")))
764        t.addChild(CommonTree(CommonToken(99, text="c"))) # index 1
765        t.addChild(CommonTree(CommonToken(99, text="d")))
766
767        newChild = CommonTree(CommonToken(99, text="x"))
768        t.replaceChildren(1, 1, newChild)
769        expecting = "(a b x d)"
770        self.failUnlessEqual(expecting, t.toStringTree())
771        t.sanityCheckParentAndChildIndexes()
772
773
774    def testReplaceAtLeft(self):
775        t = CommonTree(CommonToken(99, text="a"))
776        t.addChild(CommonTree(CommonToken(99, text="b"))) # index 0
777        t.addChild(CommonTree(CommonToken(99, text="c")))
778        t.addChild(CommonTree(CommonToken(99, text="d")))
779
780        newChild = CommonTree(CommonToken(99, text="x"))
781        t.replaceChildren(0, 0, newChild)
782        expecting = "(a x c d)"
783        self.failUnlessEqual(expecting, t.toStringTree())
784        t.sanityCheckParentAndChildIndexes()
785
786
787    def testReplaceAtRight(self):
788        t = CommonTree(CommonToken(99, text="a"))
789        t.addChild(CommonTree(CommonToken(99, text="b")))
790        t.addChild(CommonTree(CommonToken(99, text="c")))
791        t.addChild(CommonTree(CommonToken(99, text="d"))) # index 2
792
793        newChild = CommonTree(CommonToken(99, text="x"))
794        t.replaceChildren(2, 2, newChild)
795        expecting = "(a b c x)"
796        self.failUnlessEqual(expecting, t.toStringTree())
797        t.sanityCheckParentAndChildIndexes()
798
799
800    def testReplaceOneWithTwoAtLeft(self):
801        t = CommonTree(CommonToken(99, text="a"))
802        t.addChild(CommonTree(CommonToken(99, text="b")))
803        t.addChild(CommonTree(CommonToken(99, text="c")))
804        t.addChild(CommonTree(CommonToken(99, text="d")))
805
806        newChildren = self.adaptor.nil()
807        newChildren.addChild(CommonTree(CommonToken(99, text="x")))
808        newChildren.addChild(CommonTree(CommonToken(99, text="y")))
809
810        t.replaceChildren(0, 0, newChildren)
811        expecting = "(a x y c d)"
812        self.failUnlessEqual(expecting, t.toStringTree())
813        t.sanityCheckParentAndChildIndexes()
814
815
816    def testReplaceOneWithTwoAtRight(self):
817        t = CommonTree(CommonToken(99, text="a"))
818        t.addChild(CommonTree(CommonToken(99, text="b")))
819        t.addChild(CommonTree(CommonToken(99, text="c")))
820        t.addChild(CommonTree(CommonToken(99, text="d")))
821
822        newChildren = self.adaptor.nil()
823        newChildren.addChild(CommonTree(CommonToken(99, text="x")))
824        newChildren.addChild(CommonTree(CommonToken(99, text="y")))
825
826        t.replaceChildren(2, 2, newChildren)
827        expecting = "(a b c x y)"
828        self.failUnlessEqual(expecting, t.toStringTree())
829        t.sanityCheckParentAndChildIndexes()
830
831
832    def testReplaceOneWithTwoInMiddle(self):
833        t = CommonTree(CommonToken(99, text="a"))
834        t.addChild(CommonTree(CommonToken(99, text="b")))
835        t.addChild(CommonTree(CommonToken(99, text="c")))
836        t.addChild(CommonTree(CommonToken(99, text="d")))
837
838        newChildren = self.adaptor.nil()
839        newChildren.addChild(CommonTree(CommonToken(99, text="x")))
840        newChildren.addChild(CommonTree(CommonToken(99, text="y")))
841
842        t.replaceChildren(1, 1, newChildren)
843        expecting = "(a b x y d)"
844        self.failUnlessEqual(expecting, t.toStringTree())
845        t.sanityCheckParentAndChildIndexes()
846
847
848    def testReplaceTwoWithOneAtLeft(self):
849        t = CommonTree(CommonToken(99, text="a"))
850        t.addChild(CommonTree(CommonToken(99, text="b")))
851        t.addChild(CommonTree(CommonToken(99, text="c")))
852        t.addChild(CommonTree(CommonToken(99, text="d")))
853
854        newChild = CommonTree(CommonToken(99, text="x"))
855
856        t.replaceChildren(0, 1, newChild)
857        expecting = "(a x d)"
858        self.failUnlessEqual(expecting, t.toStringTree())
859        t.sanityCheckParentAndChildIndexes()
860
861
862    def testReplaceTwoWithOneAtRight(self):
863        t = CommonTree(CommonToken(99, text="a"))
864        t.addChild(CommonTree(CommonToken(99, text="b")))
865        t.addChild(CommonTree(CommonToken(99, text="c")))
866        t.addChild(CommonTree(CommonToken(99, text="d")))
867
868        newChild = CommonTree(CommonToken(99, text="x"))
869
870        t.replaceChildren(1, 2, newChild)
871        expecting = "(a b x)"
872        self.failUnlessEqual(expecting, t.toStringTree())
873        t.sanityCheckParentAndChildIndexes()
874
875
876    def testReplaceAllWithOne(self):
877        t = CommonTree(CommonToken(99, text="a"))
878        t.addChild(CommonTree(CommonToken(99, text="b")))
879        t.addChild(CommonTree(CommonToken(99, text="c")))
880        t.addChild(CommonTree(CommonToken(99, text="d")))
881
882        newChild = CommonTree(CommonToken(99, text="x"))
883
884        t.replaceChildren(0, 2, newChild)
885        expecting = "(a x)"
886        self.failUnlessEqual(expecting, t.toStringTree())
887        t.sanityCheckParentAndChildIndexes()
888
889
890    def testReplaceAllWithTwo(self):
891        t = CommonTree(CommonToken(99, text="a"))
892        t.addChild(CommonTree(CommonToken(99, text="b")))
893        t.addChild(CommonTree(CommonToken(99, text="c")))
894        t.addChild(CommonTree(CommonToken(99, text="d")))
895
896        newChildren = self.adaptor.nil()
897        newChildren.addChild(CommonTree(CommonToken(99, text="x")))
898        newChildren.addChild(CommonTree(CommonToken(99, text="y")))
899
900        t.replaceChildren(0, 2, newChildren)
901        expecting = "(a x y)"
902        self.failUnlessEqual(expecting, t.toStringTree())
903        t.sanityCheckParentAndChildIndexes()
904
905
906class TestTreeContext(unittest.TestCase):
907    """Test the TreeParser.inContext() method"""
908
909    tokenNames = [
910        "<invalid>", "<EOR>", "<DOWN>", "<UP>", "VEC", "ASSIGN", "PRINT",
911        "PLUS", "MULT", "DOT", "ID", "INT", "WS", "'['", "','", "']'"
912        ]
913
914    def testSimpleParent(self):
915        tree = "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3]))))"
916        adaptor = CommonTreeAdaptor()
917        wiz = TreeWizard(adaptor, self.tokenNames)
918        t = wiz.create(tree)
919
920        labels = {}
921        valid = wiz.parse(
922            t,
923            "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID (VEC INT %x:INT INT))))",
924            labels)
925        self.assertTrue(valid)
926        node = labels.get("x")
927
928        expecting = True
929        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC")
930        self.assertEquals(expecting, found)
931
932
933    def testNoParent(self):
934        tree = "(PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3])))"
935        adaptor = CommonTreeAdaptor()
936        wiz = TreeWizard(adaptor, self.tokenNames)
937        t = wiz.create(tree)
938
939        labels = {}
940        valid = wiz.parse(
941            t,
942            "(%x:PRINT (MULT ID (VEC INT INT INT)))",
943            labels)
944        self.assertTrue(valid)
945        node = labels.get("x")
946
947        expecting = False
948        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC")
949        self.assertEquals(expecting, found)
950
951
952    def testParentWithWildcard(self):
953        tree = "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3]))))"
954        adaptor = CommonTreeAdaptor()
955        wiz = TreeWizard(adaptor, self.tokenNames)
956        t = wiz.create(tree)
957
958        labels = {}
959        valid = wiz.parse(
960            t,
961            "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID (VEC INT %x:INT INT))))",
962            labels)
963        self.assertTrue(valid)
964        node = labels.get("x")
965
966        expecting = True
967        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC ...")
968        self.assertEquals(expecting, found)
969
970
971    def testWildcardAtStartIgnored(self):
972        tree = "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3]))))"
973        adaptor = CommonTreeAdaptor()
974        wiz = TreeWizard(adaptor, self.tokenNames)
975        t = wiz.create(tree)
976
977        labels = {}
978        valid = wiz.parse(
979            t,
980            "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID (VEC INT %x:INT INT))))",
981            labels)
982        self.assertTrue(valid)
983        node = labels.get("x")
984
985        expecting = True
986        found = TreeParser._inContext(adaptor, self.tokenNames, node, "...VEC")
987        self.assertEquals(expecting, found)
988
989
990    def testWildcardInBetween(self):
991        tree = "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3]))))"
992        adaptor = CommonTreeAdaptor()
993        wiz = TreeWizard(adaptor, self.tokenNames)
994        t = wiz.create(tree)
995
996        labels = {}
997        valid = wiz.parse(
998            t,
999            "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID (VEC INT %x:INT INT))))",
1000            labels)
1001        self.assertTrue(valid)
1002        node = labels.get("x")
1003
1004        expecting = True
1005        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT...VEC")
1006        self.assertEquals(expecting, found)
1007
1008
1009    def testLotsOfWildcards(self):
1010        tree = "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID[x] (VEC INT[1] INT[2] INT[3]))))"
1011        adaptor = CommonTreeAdaptor()
1012        wiz = TreeWizard(adaptor, self.tokenNames)
1013        t = wiz.create(tree)
1014
1015        labels = {}
1016        valid = wiz.parse(
1017            t,
1018            "(nil (ASSIGN ID[x] INT[3]) (PRINT (MULT ID (VEC INT %x:INT INT))))",
1019            labels)
1020        self.assertTrue(valid)
1021        node = labels.get("x")
1022
1023        expecting = True
1024        found = TreeParser._inContext(adaptor, self.tokenNames, node, "... PRINT ... VEC ...")
1025        self.assertEquals(expecting, found)
1026
1027
1028    def testDeep(self):
1029        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1030        adaptor = CommonTreeAdaptor()
1031        wiz = TreeWizard(adaptor, self.tokenNames)
1032        t = wiz.create(tree)
1033
1034        labels = {}
1035        valid = wiz.parse(
1036            t,
1037            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1038            labels)
1039        self.assertTrue(valid)
1040        node = labels.get("x")
1041
1042        expecting = True
1043        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC ...")
1044        self.assertEquals(expecting, found)
1045
1046
1047    def testDeepAndFindRoot(self):
1048        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1049        adaptor = CommonTreeAdaptor()
1050        wiz = TreeWizard(adaptor, self.tokenNames)
1051        t = wiz.create(tree)
1052
1053        labels = {}
1054        valid = wiz.parse(
1055            t,
1056            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1057            labels)
1058        self.assertTrue(valid)
1059        node = labels.get("x")
1060
1061        expecting = True
1062        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT ...")
1063        self.assertEquals(expecting, found)
1064
1065
1066    def testDeepAndFindRoot2(self):
1067        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1068        adaptor = CommonTreeAdaptor()
1069        wiz = TreeWizard(adaptor, self.tokenNames)
1070        t = wiz.create(tree)
1071
1072        labels = {}
1073        valid = wiz.parse(
1074            t,
1075            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1076            labels)
1077        self.assertTrue(valid)
1078        node = labels.get("x")
1079
1080        expecting = True
1081        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT ... VEC ...")
1082        self.assertEquals(expecting, found)
1083
1084
1085    def testChain(self):
1086        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1087        adaptor = CommonTreeAdaptor()
1088        wiz = TreeWizard(adaptor, self.tokenNames)
1089        t = wiz.create(tree)
1090
1091        labels = {}
1092        valid = wiz.parse(
1093            t,
1094            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1095            labels)
1096        self.assertTrue(valid)
1097        node = labels.get("x")
1098
1099        expecting = True
1100        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT MULT VEC MULT")
1101        self.assertEquals(expecting, found)
1102
1103
1104    ## TEST INVALID CONTEXTS
1105
1106    def testNotParent(self):
1107        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1108        adaptor = CommonTreeAdaptor()
1109        wiz = TreeWizard(adaptor, self.tokenNames)
1110        t = wiz.create(tree)
1111
1112        labels = {}
1113        valid = wiz.parse(
1114            t,
1115            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1116            labels)
1117        self.assertTrue(valid)
1118        node = labels.get("x")
1119
1120        expecting = False
1121        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC")
1122        self.assertEquals(expecting, found)
1123
1124
1125    def testMismatch(self):
1126        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1127        adaptor = CommonTreeAdaptor()
1128        wiz = TreeWizard(adaptor, self.tokenNames)
1129        t = wiz.create(tree)
1130
1131        labels = {}
1132        valid = wiz.parse(
1133            t,
1134            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1135            labels)
1136        self.assertTrue(valid)
1137        node = labels.get("x")
1138
1139        expecting = False
1140        ## missing MULT
1141        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT VEC MULT")
1142        self.assertEquals(expecting, found)
1143
1144
1145    def testMismatch2(self):
1146        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1147        adaptor = CommonTreeAdaptor()
1148        wiz = TreeWizard(adaptor, self.tokenNames)
1149        t = wiz.create(tree)
1150
1151        labels = {}
1152        valid = wiz.parse(
1153            t,
1154            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1155            labels)
1156        self.assertTrue(valid)
1157        node = labels.get("x")
1158
1159        expecting = False
1160        found = TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT VEC ...")
1161        self.assertEquals(expecting, found)
1162
1163
1164    def testMismatch3(self):
1165        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1166        adaptor = CommonTreeAdaptor()
1167        wiz = TreeWizard(adaptor, self.tokenNames)
1168        t = wiz.create(tree)
1169
1170        labels = {}
1171        valid = wiz.parse(
1172            t,
1173            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1174            labels)
1175        self.assertTrue(valid)
1176        node = labels.get("x")
1177
1178        expecting = False
1179        found = TreeParser._inContext(adaptor, self.tokenNames, node, "VEC ... VEC MULT")
1180        self.assertEquals(expecting, found)
1181
1182
1183    def testDoubleEtc(self):
1184        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1185        adaptor = CommonTreeAdaptor()
1186        wiz = TreeWizard(adaptor, self.tokenNames)
1187        t = wiz.create(tree)
1188
1189        labels = {}
1190        valid = wiz.parse(
1191            t,
1192            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1193            labels)
1194        self.assertTrue(valid)
1195        node = labels.get("x")
1196
1197        try:
1198            TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT ... ... VEC")
1199            self.fail()
1200        except ValueError, exc:
1201            expecting = "invalid syntax: ... ..."
1202            found = str(exc)
1203            self.assertEquals(expecting, found)
1204
1205
1206    def testDotDot(self):
1207        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1208        adaptor = CommonTreeAdaptor()
1209        wiz = TreeWizard(adaptor, self.tokenNames)
1210        t = wiz.create(tree)
1211
1212        labels = {}
1213        valid = wiz.parse(
1214            t,
1215            "(PRINT (MULT ID (VEC (MULT INT %x:INT) INT INT)))",
1216            labels)
1217        self.assertTrue(valid)
1218        node = labels.get("x")
1219
1220        try:
1221            TreeParser._inContext(adaptor, self.tokenNames, node, "PRINT .. VEC")
1222            self.fail()
1223        except ValueError, exc:
1224            expecting = "invalid syntax: .."
1225            found = str(exc)
1226            self.assertEquals(expecting, found)
1227
1228
1229class TestTreeVisitor(unittest.TestCase):
1230    """Test of the TreeVisitor class."""
1231
1232    tokenNames = [
1233        "<invalid>", "<EOR>", "<DOWN>", "<UP>", "VEC", "ASSIGN", "PRINT",
1234        "PLUS", "MULT", "DOT", "ID", "INT", "WS", "'['", "','", "']'"
1235        ]
1236
1237    def testTreeVisitor(self):
1238        tree = "(PRINT (MULT ID[x] (VEC (MULT INT[9] INT[1]) INT[2] INT[3])))"
1239        adaptor = CommonTreeAdaptor()
1240        wiz = TreeWizard(adaptor, self.tokenNames)
1241        t = wiz.create(tree)
1242
1243        found = []
1244        def pre(t):
1245            found.append("pre(%s)" % t)
1246            return t
1247        def post(t):
1248            found.append("post(%s)" % t)
1249            return t
1250
1251        visitor = TreeVisitor(adaptor)
1252        visitor.visit(t, pre, post)
1253
1254        expecting = [ "pre(PRINT)", "pre(MULT)", "pre(x)", "post(x)",
1255                      "pre(VEC)", "pre(MULT)", "pre(9)", "post(9)", "pre(1)",
1256                      "post(1)", "post(MULT)", "pre(2)", "post(2)", "pre(3)",
1257                      "post(3)", "post(VEC)", "post(MULT)", "post(PRINT)" ]
1258
1259        self.assertEquals(expecting, found)
1260
1261
1262class TestTreeIterator(unittest.TestCase):
1263    tokens = [
1264        "<invalid>", "<EOR>", "<DOWN>", "<UP>",
1265        "A", "B", "C", "D", "E", "F", "G" ]
1266
1267    def testNode(self):
1268        adaptor = CommonTreeAdaptor()
1269        wiz = TreeWizard(adaptor, self.tokens)
1270        t = wiz.create("A")
1271        it = TreeIterator(t)
1272        expecting = "A EOF"
1273        found = self.toString(it)
1274        self.assertEquals(expecting, found)
1275
1276
1277    def testFlatAB(self):
1278        adaptor = CommonTreeAdaptor()
1279        wiz = TreeWizard(adaptor, self.tokens)
1280        t = wiz.create("(nil A B)")
1281        it = TreeIterator(t)
1282        expecting = "nil DOWN A B UP EOF"
1283        found = self.toString(it)
1284        self.assertEquals(expecting, found)
1285
1286
1287    def testAB(self):
1288        adaptor = CommonTreeAdaptor()
1289        wiz = TreeWizard(adaptor, self.tokens)
1290        t = wiz.create("(A B)")
1291        it = TreeIterator(t)
1292        expecting = "A DOWN B UP EOF"
1293        found = self.toString(it)
1294        self.assertEquals(expecting, found)
1295
1296
1297    def testABC(self):
1298        adaptor = CommonTreeAdaptor()
1299        wiz = TreeWizard(adaptor, self.tokens)
1300        t = wiz.create("(A B C)")
1301        it = TreeIterator(t)
1302        expecting = "A DOWN B C UP EOF"
1303        found = self.toString(it)
1304        self.assertEquals(expecting, found)
1305
1306
1307    def testVerticalList(self):
1308        adaptor = CommonTreeAdaptor()
1309        wiz = TreeWizard(adaptor, self.tokens)
1310        t = wiz.create("(A (B C))")
1311        it = TreeIterator(t)
1312        expecting = "A DOWN B DOWN C UP UP EOF"
1313        found = self.toString(it)
1314        self.assertEquals(expecting, found)
1315
1316
1317    def testComplex(self):
1318        adaptor = CommonTreeAdaptor()
1319        wiz = TreeWizard(adaptor, self.tokens)
1320        t = wiz.create("(A (B (C D E) F) G)")
1321        it = TreeIterator(t)
1322        expecting = "A DOWN B DOWN C DOWN D E UP F UP G UP EOF"
1323        found = self.toString(it)
1324        self.assertEquals(expecting, found)
1325
1326
1327    def testReset(self):
1328        adaptor = CommonTreeAdaptor()
1329        wiz = TreeWizard(adaptor, self.tokens)
1330        t = wiz.create("(A (B (C D E) F) G)")
1331        it = TreeIterator(t)
1332        expecting = "A DOWN B DOWN C DOWN D E UP F UP G UP EOF"
1333        found = self.toString(it)
1334        self.assertEquals(expecting, found)
1335
1336        it.reset()
1337        expecting = "A DOWN B DOWN C DOWN D E UP F UP G UP EOF"
1338        found = self.toString(it)
1339        self.assertEquals(expecting, found)
1340
1341
1342    def toString(self, it):
1343        buf = []
1344        for n in it:
1345            buf.append(str(n))
1346
1347        return ' '.join(buf)
1348
1349
1350if __name__ == "__main__":
1351    unittest.main(testRunner=unittest.TextTestRunner(verbosity=2))
1352