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.assertIsInstance(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.assertIsInstance(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.assertIsInstance(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.assertIs(n1.next_sibling, 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.assertIs(l1.next_sibling, 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.assertIs(n2.prev_sibling, 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.assertIs(l2.prev_sibling, 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.assertIs(r["pl"], 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