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