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