1# Copyright 2006 Google, Inc. All Rights Reserved.
2# Licensed to PSF under a Contributor Agreement.
3
4"""Unit tests for pytree.py.
5
6NOTE: Please *don't* add doc strings to individual test methods!
7In verbose mode, printing of the module, class and method name is much
8more helpful than printing of (the first line of) the docstring,
9especially when debugging a test.
10"""
11
12from __future__ import with_statement
13
14import sys
15import warnings
16
17# Testing imports
18from . import support
19
20from lib2to3 import pytree
21
22try:
23    sorted
24except NameError:
25    def sorted(lst):
26        l = list(lst)
27        l.sort()
28        return l
29
30class TestNodes(support.TestCase):
31
32    """Unit tests for nodes (Base, Leaf, Node)."""
33
34    if sys.version_info >= (2,6):
35        # warnings.catch_warnings is new in 2.6.
36        def test_deprecated_prefix_methods(self):
37            l = pytree.Leaf(100, "foo")
38            with warnings.catch_warnings(record=True) as w:
39                warnings.simplefilter("always", DeprecationWarning)
40                self.assertEqual(l.get_prefix(), "")
41                l.set_prefix("hi")
42            self.assertEqual(l.prefix, "hi")
43            self.assertEqual(len(w), 2)
44            for warning in w:
45                self.assertTrue(warning.category is DeprecationWarning)
46            self.assertEqual(str(w[0].message), "get_prefix() is deprecated; " \
47                                 "use the prefix property")
48            self.assertEqual(str(w[1].message), "set_prefix() is deprecated; " \
49                                 "use the prefix property")
50
51    def test_instantiate_base(self):
52        if __debug__:
53            # Test that instantiating Base() raises an AssertionError
54            self.assertRaises(AssertionError, pytree.Base)
55
56    def test_leaf(self):
57        l1 = pytree.Leaf(100, "foo")
58        self.assertEqual(l1.type, 100)
59        self.assertEqual(l1.value, "foo")
60
61    def test_leaf_repr(self):
62        l1 = pytree.Leaf(100, "foo")
63        self.assertEqual(repr(l1), "Leaf(100, 'foo')")
64
65    def test_leaf_str(self):
66        l1 = pytree.Leaf(100, "foo")
67        self.assertEqual(str(l1), "foo")
68        l2 = pytree.Leaf(100, "foo", context=(" ", (10, 1)))
69        self.assertEqual(str(l2), " foo")
70
71    def test_leaf_str_numeric_value(self):
72        # Make sure that the Leaf's value is stringified. Failing to
73        #  do this can cause a TypeError in certain situations.
74        l1 = pytree.Leaf(2, 5)
75        l1.prefix = "foo_"
76        self.assertEqual(str(l1), "foo_5")
77
78    def test_leaf_equality(self):
79        l1 = pytree.Leaf(100, "foo")
80        l2 = pytree.Leaf(100, "foo", context=(" ", (1, 0)))
81        self.assertEqual(l1, l2)
82        l3 = pytree.Leaf(101, "foo")
83        l4 = pytree.Leaf(100, "bar")
84        self.assertNotEqual(l1, l3)
85        self.assertNotEqual(l1, l4)
86
87    def test_leaf_prefix(self):
88        l1 = pytree.Leaf(100, "foo")
89        self.assertEqual(l1.prefix, "")
90        self.assertFalse(l1.was_changed)
91        l1.prefix = "  ##\n\n"
92        self.assertEqual(l1.prefix, "  ##\n\n")
93        self.assertTrue(l1.was_changed)
94
95    def test_node(self):
96        l1 = pytree.Leaf(100, "foo")
97        l2 = pytree.Leaf(200, "bar")
98        n1 = pytree.Node(1000, [l1, l2])
99        self.assertEqual(n1.type, 1000)
100        self.assertEqual(n1.children, [l1, l2])
101
102    def test_node_repr(self):
103        l1 = pytree.Leaf(100, "foo")
104        l2 = pytree.Leaf(100, "bar", context=(" ", (1, 0)))
105        n1 = pytree.Node(1000, [l1, l2])
106        self.assertEqual(repr(n1),
107                         "Node(1000, [%s, %s])" % (repr(l1), repr(l2)))
108
109    def test_node_str(self):
110        l1 = pytree.Leaf(100, "foo")
111        l2 = pytree.Leaf(100, "bar", context=(" ", (1, 0)))
112        n1 = pytree.Node(1000, [l1, l2])
113        self.assertEqual(str(n1), "foo bar")
114
115    def test_node_prefix(self):
116        l1 = pytree.Leaf(100, "foo")
117        self.assertEqual(l1.prefix, "")
118        n1 = pytree.Node(1000, [l1])
119        self.assertEqual(n1.prefix, "")
120        n1.prefix = " "
121        self.assertEqual(n1.prefix, " ")
122        self.assertEqual(l1.prefix, " ")
123
124    def test_get_suffix(self):
125        l1 = pytree.Leaf(100, "foo", prefix="a")
126        l2 = pytree.Leaf(100, "bar", prefix="b")
127        n1 = pytree.Node(1000, [l1, l2])
128
129        self.assertEqual(l1.get_suffix(), l2.prefix)
130        self.assertEqual(l2.get_suffix(), "")
131        self.assertEqual(n1.get_suffix(), "")
132
133        l3 = pytree.Leaf(100, "bar", prefix="c")
134        n2 = pytree.Node(1000, [n1, l3])
135
136        self.assertEqual(n1.get_suffix(), l3.prefix)
137        self.assertEqual(l3.get_suffix(), "")
138        self.assertEqual(n2.get_suffix(), "")
139
140    def test_node_equality(self):
141        n1 = pytree.Node(1000, ())
142        n2 = pytree.Node(1000, [], context=(" ", (1, 0)))
143        self.assertEqual(n1, n2)
144        n3 = pytree.Node(1001, ())
145        self.assertNotEqual(n1, n3)
146
147    def test_node_recursive_equality(self):
148        l1 = pytree.Leaf(100, "foo")
149        l2 = pytree.Leaf(100, "foo")
150        n1 = pytree.Node(1000, [l1])
151        n2 = pytree.Node(1000, [l2])
152        self.assertEqual(n1, n2)
153        l3 = pytree.Leaf(100, "bar")
154        n3 = pytree.Node(1000, [l3])
155        self.assertNotEqual(n1, n3)
156
157    def test_replace(self):
158        l1 = pytree.Leaf(100, "foo")
159        l2 = pytree.Leaf(100, "+")
160        l3 = pytree.Leaf(100, "bar")
161        n1 = pytree.Node(1000, [l1, l2, l3])
162        self.assertEqual(n1.children, [l1, l2, l3])
163        self.assertTrue(isinstance(n1.children, list))
164        self.assertFalse(n1.was_changed)
165        l2new = pytree.Leaf(100, "-")
166        l2.replace(l2new)
167        self.assertEqual(n1.children, [l1, l2new, l3])
168        self.assertTrue(isinstance(n1.children, list))
169        self.assertTrue(n1.was_changed)
170
171    def test_replace_with_list(self):
172        l1 = pytree.Leaf(100, "foo")
173        l2 = pytree.Leaf(100, "+")
174        l3 = pytree.Leaf(100, "bar")
175        n1 = pytree.Node(1000, [l1, l2, l3])
176
177        l2.replace([pytree.Leaf(100, "*"), pytree.Leaf(100, "*")])
178        self.assertEqual(str(n1), "foo**bar")
179        self.assertTrue(isinstance(n1.children, list))
180
181    def test_leaves(self):
182        l1 = pytree.Leaf(100, "foo")
183        l2 = pytree.Leaf(100, "bar")
184        l3 = pytree.Leaf(100, "fooey")
185        n2 = pytree.Node(1000, [l1, l2])
186        n3 = pytree.Node(1000, [l3])
187        n1 = pytree.Node(1000, [n2, n3])
188
189        self.assertEqual(list(n1.leaves()), [l1, l2, l3])
190
191    def test_depth(self):
192        l1 = pytree.Leaf(100, "foo")
193        l2 = pytree.Leaf(100, "bar")
194        n2 = pytree.Node(1000, [l1, l2])
195        n3 = pytree.Node(1000, [])
196        n1 = pytree.Node(1000, [n2, n3])
197
198        self.assertEqual(l1.depth(), 2)
199        self.assertEqual(n3.depth(), 1)
200        self.assertEqual(n1.depth(), 0)
201
202    def test_post_order(self):
203        l1 = pytree.Leaf(100, "foo")
204        l2 = pytree.Leaf(100, "bar")
205        l3 = pytree.Leaf(100, "fooey")
206        c1 = pytree.Node(1000, [l1, l2])
207        n1 = pytree.Node(1000, [c1, l3])
208        self.assertEqual(list(n1.post_order()), [l1, l2, c1, l3, n1])
209
210    def test_pre_order(self):
211        l1 = pytree.Leaf(100, "foo")
212        l2 = pytree.Leaf(100, "bar")
213        l3 = pytree.Leaf(100, "fooey")
214        c1 = pytree.Node(1000, [l1, l2])
215        n1 = pytree.Node(1000, [c1, l3])
216        self.assertEqual(list(n1.pre_order()), [n1, c1, l1, l2, l3])
217
218    def test_changed(self):
219        l1 = pytree.Leaf(100, "f")
220        self.assertFalse(l1.was_changed)
221        l1.changed()
222        self.assertTrue(l1.was_changed)
223
224        l1 = pytree.Leaf(100, "f")
225        n1 = pytree.Node(1000, [l1])
226        self.assertFalse(n1.was_changed)
227        n1.changed()
228        self.assertTrue(n1.was_changed)
229
230        l1 = pytree.Leaf(100, "foo")
231        l2 = pytree.Leaf(100, "+")
232        l3 = pytree.Leaf(100, "bar")
233        n1 = pytree.Node(1000, [l1, l2, l3])
234        n2 = pytree.Node(1000, [n1])
235        self.assertFalse(l1.was_changed)
236        self.assertFalse(n1.was_changed)
237        self.assertFalse(n2.was_changed)
238
239        n1.changed()
240        self.assertTrue(n1.was_changed)
241        self.assertTrue(n2.was_changed)
242        self.assertFalse(l1.was_changed)
243
244    def test_leaf_constructor_prefix(self):
245        for prefix in ("xyz_", ""):
246            l1 = pytree.Leaf(100, "self", prefix=prefix)
247            self.assertTrue(str(l1), prefix + "self")
248            self.assertEqual(l1.prefix, prefix)
249
250    def test_node_constructor_prefix(self):
251        for prefix in ("xyz_", ""):
252            l1 = pytree.Leaf(100, "self")
253            l2 = pytree.Leaf(100, "foo", prefix="_")
254            n1 = pytree.Node(1000, [l1, l2], prefix=prefix)
255            self.assertTrue(str(n1), prefix + "self_foo")
256            self.assertEqual(n1.prefix, prefix)
257            self.assertEqual(l1.prefix, prefix)
258            self.assertEqual(l2.prefix, "_")
259
260    def test_remove(self):
261        l1 = pytree.Leaf(100, "foo")
262        l2 = pytree.Leaf(100, "foo")
263        n1 = pytree.Node(1000, [l1, l2])
264        n2 = pytree.Node(1000, [n1])
265
266        self.assertEqual(n1.remove(), 0)
267        self.assertEqual(n2.children, [])
268        self.assertEqual(l1.parent, n1)
269        self.assertEqual(n1.parent, None)
270        self.assertEqual(n2.parent, None)
271        self.assertFalse(n1.was_changed)
272        self.assertTrue(n2.was_changed)
273
274        self.assertEqual(l2.remove(), 1)
275        self.assertEqual(l1.remove(), 0)
276        self.assertEqual(n1.children, [])
277        self.assertEqual(l1.parent, None)
278        self.assertEqual(n1.parent, None)
279        self.assertEqual(n2.parent, None)
280        self.assertTrue(n1.was_changed)
281        self.assertTrue(n2.was_changed)
282
283    def test_remove_parentless(self):
284        n1 = pytree.Node(1000, [])
285        n1.remove()
286        self.assertEqual(n1.parent, None)
287
288        l1 = pytree.Leaf(100, "foo")
289        l1.remove()
290        self.assertEqual(l1.parent, None)
291
292    def test_node_set_child(self):
293        l1 = pytree.Leaf(100, "foo")
294        n1 = pytree.Node(1000, [l1])
295
296        l2 = pytree.Leaf(100, "bar")
297        n1.set_child(0, l2)
298        self.assertEqual(l1.parent, None)
299        self.assertEqual(l2.parent, n1)
300        self.assertEqual(n1.children, [l2])
301
302        n2 = pytree.Node(1000, [l1])
303        n2.set_child(0, n1)
304        self.assertEqual(l1.parent, None)
305        self.assertEqual(n1.parent, n2)
306        self.assertEqual(n2.parent, None)
307        self.assertEqual(n2.children, [n1])
308
309        self.assertRaises(IndexError, n1.set_child, 4, l2)
310        # I don't care what it raises, so long as it's an exception
311        self.assertRaises(Exception, n1.set_child, 0, list)
312
313    def test_node_insert_child(self):
314        l1 = pytree.Leaf(100, "foo")
315        n1 = pytree.Node(1000, [l1])
316
317        l2 = pytree.Leaf(100, "bar")
318        n1.insert_child(0, l2)
319        self.assertEqual(l2.parent, n1)
320        self.assertEqual(n1.children, [l2, l1])
321
322        l3 = pytree.Leaf(100, "abc")
323        n1.insert_child(2, l3)
324        self.assertEqual(n1.children, [l2, l1, l3])
325
326        # I don't care what it raises, so long as it's an exception
327        self.assertRaises(Exception, n1.insert_child, 0, list)
328
329    def test_node_append_child(self):
330        n1 = pytree.Node(1000, [])
331
332        l1 = pytree.Leaf(100, "foo")
333        n1.append_child(l1)
334        self.assertEqual(l1.parent, n1)
335        self.assertEqual(n1.children, [l1])
336
337        l2 = pytree.Leaf(100, "bar")
338        n1.append_child(l2)
339        self.assertEqual(l2.parent, n1)
340        self.assertEqual(n1.children, [l1, l2])
341
342        # I don't care what it raises, so long as it's an exception
343        self.assertRaises(Exception, n1.append_child, list)
344
345    def test_node_next_sibling(self):
346        n1 = pytree.Node(1000, [])
347        n2 = pytree.Node(1000, [])
348        p1 = pytree.Node(1000, [n1, n2])
349
350        self.assertTrue(n1.next_sibling is n2)
351        self.assertEqual(n2.next_sibling, None)
352        self.assertEqual(p1.next_sibling, None)
353
354    def test_leaf_next_sibling(self):
355        l1 = pytree.Leaf(100, "a")
356        l2 = pytree.Leaf(100, "b")
357        p1 = pytree.Node(1000, [l1, l2])
358
359        self.assertTrue(l1.next_sibling is l2)
360        self.assertEqual(l2.next_sibling, None)
361        self.assertEqual(p1.next_sibling, None)
362
363    def test_node_prev_sibling(self):
364        n1 = pytree.Node(1000, [])
365        n2 = pytree.Node(1000, [])
366        p1 = pytree.Node(1000, [n1, n2])
367
368        self.assertTrue(n2.prev_sibling is n1)
369        self.assertEqual(n1.prev_sibling, None)
370        self.assertEqual(p1.prev_sibling, None)
371
372    def test_leaf_prev_sibling(self):
373        l1 = pytree.Leaf(100, "a")
374        l2 = pytree.Leaf(100, "b")
375        p1 = pytree.Node(1000, [l1, l2])
376
377        self.assertTrue(l2.prev_sibling is l1)
378        self.assertEqual(l1.prev_sibling, None)
379        self.assertEqual(p1.prev_sibling, None)
380
381
382class TestPatterns(support.TestCase):
383
384    """Unit tests for tree matching patterns."""
385
386    def test_basic_patterns(self):
387        # Build a tree
388        l1 = pytree.Leaf(100, "foo")
389        l2 = pytree.Leaf(100, "bar")
390        l3 = pytree.Leaf(100, "foo")
391        n1 = pytree.Node(1000, [l1, l2])
392        n2 = pytree.Node(1000, [l3])
393        root = pytree.Node(1000, [n1, n2])
394        # Build a pattern matching a leaf
395        pl = pytree.LeafPattern(100, "foo", name="pl")
396        r = {}
397        self.assertFalse(pl.match(root, results=r))
398        self.assertEqual(r, {})
399        self.assertFalse(pl.match(n1, results=r))
400        self.assertEqual(r, {})
401        self.assertFalse(pl.match(n2, results=r))
402        self.assertEqual(r, {})
403        self.assertTrue(pl.match(l1, results=r))
404        self.assertEqual(r, {"pl": l1})
405        r = {}
406        self.assertFalse(pl.match(l2, results=r))
407        self.assertEqual(r, {})
408        # Build a pattern matching a node
409        pn = pytree.NodePattern(1000, [pl], name="pn")
410        self.assertFalse(pn.match(root, results=r))
411        self.assertEqual(r, {})
412        self.assertFalse(pn.match(n1, results=r))
413        self.assertEqual(r, {})
414        self.assertTrue(pn.match(n2, results=r))
415        self.assertEqual(r, {"pn": n2, "pl": l3})
416        r = {}
417        self.assertFalse(pn.match(l1, results=r))
418        self.assertEqual(r, {})
419        self.assertFalse(pn.match(l2, results=r))
420        self.assertEqual(r, {})
421
422    def test_wildcard(self):
423        # Build a tree for testing
424        l1 = pytree.Leaf(100, "foo")
425        l2 = pytree.Leaf(100, "bar")
426        l3 = pytree.Leaf(100, "foo")
427        n1 = pytree.Node(1000, [l1, l2])
428        n2 = pytree.Node(1000, [l3])
429        root = pytree.Node(1000, [n1, n2])
430        # Build a pattern
431        pl = pytree.LeafPattern(100, "foo", name="pl")
432        pn = pytree.NodePattern(1000, [pl], name="pn")
433        pw = pytree.WildcardPattern([[pn], [pl, pl]], name="pw")
434        r = {}
435        self.assertFalse(pw.match_seq([root], r))
436        self.assertEqual(r, {})
437        self.assertFalse(pw.match_seq([n1], r))
438        self.assertEqual(r, {})
439        self.assertTrue(pw.match_seq([n2], r))
440        # These are easier to debug
441        self.assertEqual(sorted(r.keys()), ["pl", "pn", "pw"])
442        self.assertEqual(r["pl"], l1)
443        self.assertEqual(r["pn"], n2)
444        self.assertEqual(r["pw"], [n2])
445        # But this is equivalent
446        self.assertEqual(r, {"pl": l1, "pn": n2, "pw": [n2]})
447        r = {}
448        self.assertTrue(pw.match_seq([l1, l3], r))
449        self.assertEqual(r, {"pl": l3, "pw": [l1, l3]})
450        self.assertTrue(r["pl"] is l3)
451        r = {}
452
453    def test_generate_matches(self):
454        la = pytree.Leaf(1, "a")
455        lb = pytree.Leaf(1, "b")
456        lc = pytree.Leaf(1, "c")
457        ld = pytree.Leaf(1, "d")
458        le = pytree.Leaf(1, "e")
459        lf = pytree.Leaf(1, "f")
460        leaves = [la, lb, lc, ld, le, lf]
461        root = pytree.Node(1000, leaves)
462        pa = pytree.LeafPattern(1, "a", "pa")
463        pb = pytree.LeafPattern(1, "b", "pb")
464        pc = pytree.LeafPattern(1, "c", "pc")
465        pd = pytree.LeafPattern(1, "d", "pd")
466        pe = pytree.LeafPattern(1, "e", "pe")
467        pf = pytree.LeafPattern(1, "f", "pf")
468        pw = pytree.WildcardPattern([[pa, pb, pc], [pd, pe],
469                                     [pa, pb], [pc, pd], [pe, pf]],
470                                    min=1, max=4, name="pw")
471        self.assertEqual([x[0] for x in pw.generate_matches(leaves)],
472                         [3, 5, 2, 4, 6])
473        pr = pytree.NodePattern(type=1000, content=[pw], name="pr")
474        matches = list(pytree.generate_matches([pr], [root]))
475        self.assertEqual(len(matches), 1)
476        c, r = matches[0]
477        self.assertEqual(c, 1)
478        self.assertEqual(str(r["pr"]), "abcdef")
479        self.assertEqual(r["pw"], [la, lb, lc, ld, le, lf])
480        for c in "abcdef":
481            self.assertEqual(r["p" + c], pytree.Leaf(1, c))
482
483    def test_has_key_example(self):
484        pattern = pytree.NodePattern(331,
485                                     (pytree.LeafPattern(7),
486                                      pytree.WildcardPattern(name="args"),
487                                      pytree.LeafPattern(8)))
488        l1 = pytree.Leaf(7, "(")
489        l2 = pytree.Leaf(3, "x")
490        l3 = pytree.Leaf(8, ")")
491        node = pytree.Node(331, [l1, l2, l3])
492        r = {}
493        self.assertTrue(pattern.match(node, r))
494        self.assertEqual(r["args"], [l2])
495