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 12# Testing imports 13from . import support 14 15from lib2to3 import pytree 16 17try: 18 sorted 19except NameError: 20 def sorted(lst): 21 l = list(lst) 22 l.sort() 23 return l 24 25class TestNodes(support.TestCase): 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 360class TestPatterns(support.TestCase): 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]) 473