1 #!/usr/bin/env python2.5

     2 # Copyright 2006 Google, Inc. All Rights Reserved.

     3 # Licensed to PSF under a Contributor Agreement.

     4 

     5 """Unit tests for pytree.py.

     6 

     7 NOTE: Please *don't* add doc strings to individual test methods!

     8 In verbose mode, printing of the module, class and method name is much

     9 more helpful than printing of (the first line of) the docstring,

    10 especially when debugging a test.

    11 """

    12 

    13 # Testing imports

    14 from . import support

    15 

    16 # Local imports (XXX should become a package)

    17 from .. import pytree

    18 

    19 try:

    20     sorted

    21 except NameError:

    22     def sorted(lst):

    23         l = list(lst)

    24         l.sort()

    25         return l

    26 

    27 class TestNodes(support.TestCase):

    28 

    29     """Unit tests for nodes (Base, Leaf, Node)."""

    30 

    31     def testBaseCantConstruct(self):

    32         if __debug__:

    33             # Test that instantiating Base() raises an AssertionError

    34             self.assertRaises(AssertionError, pytree.Base)

    35 

    36     def testLeaf(self):

    37         l1 = pytree.Leaf(100, "foo")

    38         self.assertEqual(l1.type, 100)

    39         self.assertEqual(l1.value, "foo")

    40 

    41     def testLeafRepr(self):

    42         l1 = pytree.Leaf(100, "foo")

    43         self.assertEqual(repr(l1), "Leaf(100, 'foo')")

    44 

    45     def testLeafStr(self):

    46         l1 = pytree.Leaf(100, "foo")

    47         self.assertEqual(str(l1), "foo")

    48         l2 = pytree.Leaf(100, "foo", context=(" ", (10, 1)))

    49         self.assertEqual(str(l2), " foo")

    50 

    51     def testLeafStrNumericValue(self):

    52         # Make sure that the Leaf's value is stringified. Failing to

    53         #  do this can cause a TypeError in certain situations.

    54         l1 = pytree.Leaf(2, 5)

    55         l1.set_prefix("foo_")

    56         self.assertEqual(str(l1), "foo_5")

    57 

    58     def testLeafEq(self):

    59         l1 = pytree.Leaf(100, "foo")

    60         l2 = pytree.Leaf(100, "foo", context=(" ", (1, 0)))

    61         self.assertEqual(l1, l2)

    62         l3 = pytree.Leaf(101, "foo")

    63         l4 = pytree.Leaf(100, "bar")

    64         self.assertNotEqual(l1, l3)

    65         self.assertNotEqual(l1, l4)

    66 

    67     def testLeafPrefix(self):

    68         l1 = pytree.Leaf(100, "foo")

    69         self.assertEqual(l1.get_prefix(), "")

    70         self.failIf(l1.was_changed)

    71         l1.set_prefix("  ##\n\n")

    72         self.assertEqual(l1.get_prefix(), "  ##\n\n")

    73         self.failUnless(l1.was_changed)

    74 

    75     def testNode(self):

    76         l1 = pytree.Leaf(100, "foo")

    77         l2 = pytree.Leaf(200, "bar")

    78         n1 = pytree.Node(1000, [l1, l2])

    79         self.assertEqual(n1.type, 1000)

    80         self.assertEqual(n1.children, [l1, l2])

    81 

    82     def testNodeRepr(self):

    83         l1 = pytree.Leaf(100, "foo")

    84         l2 = pytree.Leaf(100, "bar", context=(" ", (1, 0)))

    85         n1 = pytree.Node(1000, [l1, l2])

    86         self.assertEqual(repr(n1),

    87                          "Node(1000, [%s, %s])" % (repr(l1), repr(l2)))

    88 

    89     def testNodeStr(self):

    90         l1 = pytree.Leaf(100, "foo")

    91         l2 = pytree.Leaf(100, "bar", context=(" ", (1, 0)))

    92         n1 = pytree.Node(1000, [l1, l2])

    93         self.assertEqual(str(n1), "foo bar")

    94 

    95     def testNodePrefix(self):

    96         l1 = pytree.Leaf(100, "foo")

    97         self.assertEqual(l1.get_prefix(), "")

    98         n1 = pytree.Node(1000, [l1])

    99         self.assertEqual(n1.get_prefix(), "")

   100         n1.set_prefix(" ")

   101         self.assertEqual(n1.get_prefix(), " ")

   102         self.assertEqual(l1.get_prefix(), " ")

   103 

   104     def testGetSuffix(self):

   105         l1 = pytree.Leaf(100, "foo", prefix="a")

   106         l2 = pytree.Leaf(100, "bar", prefix="b")

   107         n1 = pytree.Node(1000, [l1, l2])

   108 

   109         self.assertEqual(l1.get_suffix(), l2.get_prefix())

   110         self.assertEqual(l2.get_suffix(), "")

   111         self.assertEqual(n1.get_suffix(), "")

   112 

   113         l3 = pytree.Leaf(100, "bar", prefix="c")

   114         n2 = pytree.Node(1000, [n1, l3])

   115 

   116         self.assertEqual(n1.get_suffix(), l3.get_prefix())

   117         self.assertEqual(l3.get_suffix(), "")

   118         self.assertEqual(n2.get_suffix(), "")

   119 

   120     def testNodeEq(self):

   121         n1 = pytree.Node(1000, ())

   122         n2 = pytree.Node(1000, [], context=(" ", (1, 0)))

   123         self.assertEqual(n1, n2)

   124         n3 = pytree.Node(1001, ())

   125         self.assertNotEqual(n1, n3)

   126 

   127     def testNodeEqRecursive(self):

   128         l1 = pytree.Leaf(100, "foo")

   129         l2 = pytree.Leaf(100, "foo")

   130         n1 = pytree.Node(1000, [l1])

   131         n2 = pytree.Node(1000, [l2])

   132         self.assertEqual(n1, n2)

   133         l3 = pytree.Leaf(100, "bar")

   134         n3 = pytree.Node(1000, [l3])

   135         self.assertNotEqual(n1, n3)

   136 

   137     def testReplace(self):

   138         l1 = pytree.Leaf(100, "foo")

   139         l2 = pytree.Leaf(100, "+")

   140         l3 = pytree.Leaf(100, "bar")

   141         n1 = pytree.Node(1000, [l1, l2, l3])

   142         self.assertEqual(n1.children, [l1, l2, l3])

   143         self.failUnless(isinstance(n1.children, list))

   144         self.failIf(n1.was_changed)

   145         l2new = pytree.Leaf(100, "-")

   146         l2.replace(l2new)

   147         self.assertEqual(n1.children, [l1, l2new, l3])

   148         self.failUnless(isinstance(n1.children, list))

   149         self.failUnless(n1.was_changed)

   150 

   151     def testReplaceWithList(self):

   152         l1 = pytree.Leaf(100, "foo")

   153         l2 = pytree.Leaf(100, "+")

   154         l3 = pytree.Leaf(100, "bar")

   155         n1 = pytree.Node(1000, [l1, l2, l3])

   156 

   157         l2.replace([pytree.Leaf(100, "*"), pytree.Leaf(100, "*")])

   158         self.assertEqual(str(n1), "foo**bar")

   159         self.failUnless(isinstance(n1.children, list))

   160 

   161     def testPostOrder(self):

   162         l1 = pytree.Leaf(100, "foo")

   163         l2 = pytree.Leaf(100, "bar")

   164         n1 = pytree.Node(1000, [l1, l2])

   165         self.assertEqual(list(n1.post_order()), [l1, l2, n1])

   166 

   167     def testPreOrder(self):

   168         l1 = pytree.Leaf(100, "foo")

   169         l2 = pytree.Leaf(100, "bar")

   170         n1 = pytree.Node(1000, [l1, l2])

   171         self.assertEqual(list(n1.pre_order()), [n1, l1, l2])

   172 

   173     def testChangedLeaf(self):

   174         l1 = pytree.Leaf(100, "f")

   175         self.failIf(l1.was_changed)

   176 

   177         l1.changed()

   178         self.failUnless(l1.was_changed)

   179 

   180     def testChangedNode(self):

   181         l1 = pytree.Leaf(100, "f")

   182         n1 = pytree.Node(1000, [l1])

   183         self.failIf(n1.was_changed)

   184 

   185         n1.changed()

   186         self.failUnless(n1.was_changed)

   187 

   188     def testChangedRecursive(self):

   189         l1 = pytree.Leaf(100, "foo")

   190         l2 = pytree.Leaf(100, "+")

   191         l3 = pytree.Leaf(100, "bar")

   192         n1 = pytree.Node(1000, [l1, l2, l3])

   193         n2 = pytree.Node(1000, [n1])

   194         self.failIf(l1.was_changed)

   195         self.failIf(n1.was_changed)

   196         self.failIf(n2.was_changed)

   197 

   198         n1.changed()

   199         self.failUnless(n1.was_changed)

   200         self.failUnless(n2.was_changed)

   201         self.failIf(l1.was_changed)

   202 

   203     def testLeafConstructorPrefix(self):

   204         for prefix in ("xyz_", ""):

   205             l1 = pytree.Leaf(100, "self", prefix=prefix)

   206             self.failUnless(str(l1), prefix + "self")

   207             self.assertEqual(l1.get_prefix(), prefix)

   208 

   209     def testNodeConstructorPrefix(self):

   210         for prefix in ("xyz_", ""):

   211             l1 = pytree.Leaf(100, "self")

   212             l2 = pytree.Leaf(100, "foo", prefix="_")

   213             n1 = pytree.Node(1000, [l1, l2], prefix=prefix)

   214             self.failUnless(str(n1), prefix + "self_foo")

   215             self.assertEqual(n1.get_prefix(), prefix)

   216             self.assertEqual(l1.get_prefix(), prefix)

   217             self.assertEqual(l2.get_prefix(), "_")

   218 

   219     def testRemove(self):

   220         l1 = pytree.Leaf(100, "foo")

   221         l2 = pytree.Leaf(100, "foo")

   222         n1 = pytree.Node(1000, [l1, l2])

   223         n2 = pytree.Node(1000, [n1])

   224 

   225         self.assertEqual(n1.remove(), 0)

   226         self.assertEqual(n2.children, [])

   227         self.assertEqual(l1.parent, n1)

   228         self.assertEqual(n1.parent, None)

   229         self.assertEqual(n2.parent, None)

   230         self.failIf(n1.was_changed)

   231         self.failUnless(n2.was_changed)

   232 

   233         self.assertEqual(l2.remove(), 1)

   234         self.assertEqual(l1.remove(), 0)

   235         self.assertEqual(n1.children, [])

   236         self.assertEqual(l1.parent, None)

   237         self.assertEqual(n1.parent, None)

   238         self.assertEqual(n2.parent, None)

   239         self.failUnless(n1.was_changed)

   240         self.failUnless(n2.was_changed)

   241 

   242     def testRemoveParentless(self):

   243         n1 = pytree.Node(1000, [])

   244         n1.remove()

   245         self.assertEqual(n1.parent, None)

   246 

   247         l1 = pytree.Leaf(100, "foo")

   248         l1.remove()

   249         self.assertEqual(l1.parent, None)

   250 

   251     def testNodeSetChild(self):

   252         l1 = pytree.Leaf(100, "foo")

   253         n1 = pytree.Node(1000, [l1])

   254 

   255         l2 = pytree.Leaf(100, "bar")

   256         n1.set_child(0, l2)

   257         self.assertEqual(l1.parent, None)

   258         self.assertEqual(l2.parent, n1)

   259         self.assertEqual(n1.children, [l2])

   260 

   261         n2 = pytree.Node(1000, [l1])

   262         n2.set_child(0, n1)

   263         self.assertEqual(l1.parent, None)

   264         self.assertEqual(n1.parent, n2)

   265         self.assertEqual(n2.parent, None)

   266         self.assertEqual(n2.children, [n1])

   267 

   268         self.assertRaises(IndexError, n1.set_child, 4, l2)

   269         # I don't care what it raises, so long as it's an exception

   270         self.assertRaises(Exception, n1.set_child, 0, list)

   271 

   272     def testNodeInsertChild(self):

   273         l1 = pytree.Leaf(100, "foo")

   274         n1 = pytree.Node(1000, [l1])

   275 

   276         l2 = pytree.Leaf(100, "bar")

   277         n1.insert_child(0, l2)

   278         self.assertEqual(l2.parent, n1)

   279         self.assertEqual(n1.children, [l2, l1])

   280 

   281         l3 = pytree.Leaf(100, "abc")

   282         n1.insert_child(2, l3)

   283         self.assertEqual(n1.children, [l2, l1, l3])

   284 

   285         # I don't care what it raises, so long as it's an exception

   286         self.assertRaises(Exception, n1.insert_child, 0, list)

   287 

   288     def testNodeAppendChild(self):

   289         n1 = pytree.Node(1000, [])

   290 

   291         l1 = pytree.Leaf(100, "foo")

   292         n1.append_child(l1)

   293         self.assertEqual(l1.parent, n1)

   294         self.assertEqual(n1.children, [l1])

   295 

   296         l2 = pytree.Leaf(100, "bar")

   297         n1.append_child(l2)

   298         self.assertEqual(l2.parent, n1)

   299         self.assertEqual(n1.children, [l1, l2])

   300 

   301         # I don't care what it raises, so long as it's an exception

   302         self.assertRaises(Exception, n1.append_child, list)

   303 

   304     def testNodeNextSibling(self):

   305         n1 = pytree.Node(1000, [])

   306         n2 = pytree.Node(1000, [])

   307         p1 = pytree.Node(1000, [n1, n2])

   308 

   309         self.failUnless(n1.get_next_sibling() is n2)

   310         self.assertEqual(n2.get_next_sibling(), None)

   311         self.assertEqual(p1.get_next_sibling(), None)

   312 

   313     def testLeafNextSibling(self):

   314         l1 = pytree.Leaf(100, "a")

   315         l2 = pytree.Leaf(100, "b")

   316         p1 = pytree.Node(1000, [l1, l2])

   317 

   318         self.failUnless(l1.get_next_sibling() is l2)

   319         self.assertEqual(l2.get_next_sibling(), None)

   320         self.assertEqual(p1.get_next_sibling(), None)

   321 

   322     def testNodePrevSibling(self):

   323         n1 = pytree.Node(1000, [])

   324         n2 = pytree.Node(1000, [])

   325         p1 = pytree.Node(1000, [n1, n2])

   326 

   327         self.failUnless(n2.get_prev_sibling() is n1)

   328         self.assertEqual(n1.get_prev_sibling(), None)

   329         self.assertEqual(p1.get_prev_sibling(), None)

   330 

   331     def testLeafPrevSibling(self):

   332         l1 = pytree.Leaf(100, "a")

   333         l2 = pytree.Leaf(100, "b")

   334         p1 = pytree.Node(1000, [l1, l2])

   335 

   336         self.failUnless(l2.get_prev_sibling() is l1)

   337         self.assertEqual(l1.get_prev_sibling(), None)

   338         self.assertEqual(p1.get_prev_sibling(), None)

   339 

   340 

   341 class TestPatterns(support.TestCase):

   342 

   343     """Unit tests for tree matching patterns."""

   344 

   345     def testBasicPatterns(self):

   346         # Build a tree

   347         l1 = pytree.Leaf(100, "foo")

   348         l2 = pytree.Leaf(100, "bar")

   349         l3 = pytree.Leaf(100, "foo")

   350         n1 = pytree.Node(1000, [l1, l2])

   351         n2 = pytree.Node(1000, [l3])

   352         root = pytree.Node(1000, [n1, n2])

   353         # Build a pattern matching a leaf

   354         pl = pytree.LeafPattern(100, "foo", name="pl")

   355         r = {}

   356         self.assertFalse(pl.match(root, results=r))

   357         self.assertEqual(r, {})

   358         self.assertFalse(pl.match(n1, results=r))

   359         self.assertEqual(r, {})

   360         self.assertFalse(pl.match(n2, results=r))

   361         self.assertEqual(r, {})

   362         self.assertTrue(pl.match(l1, results=r))

   363         self.assertEqual(r, {"pl": l1})

   364         r = {}

   365         self.assertFalse(pl.match(l2, results=r))

   366         self.assertEqual(r, {})

   367         # Build a pattern matching a node

   368         pn = pytree.NodePattern(1000, [pl], name="pn")

   369         self.assertFalse(pn.match(root, results=r))

   370         self.assertEqual(r, {})

   371         self.assertFalse(pn.match(n1, results=r))

   372         self.assertEqual(r, {})

   373         self.assertTrue(pn.match(n2, results=r))

   374         self.assertEqual(r, {"pn": n2, "pl": l3})

   375         r = {}

   376         self.assertFalse(pn.match(l1, results=r))

   377         self.assertEqual(r, {})

   378         self.assertFalse(pn.match(l2, results=r))

   379         self.assertEqual(r, {})

   380 

   381     def testWildcardPatterns(self):

   382         # Build a tree for testing

   383         l1 = pytree.Leaf(100, "foo")

   384         l2 = pytree.Leaf(100, "bar")

   385         l3 = pytree.Leaf(100, "foo")

   386         n1 = pytree.Node(1000, [l1, l2])

   387         n2 = pytree.Node(1000, [l3])

   388         root = pytree.Node(1000, [n1, n2])

   389         # Build a pattern

   390         pl = pytree.LeafPattern(100, "foo", name="pl")

   391         pn = pytree.NodePattern(1000, [pl], name="pn")

   392         pw = pytree.WildcardPattern([[pn], [pl, pl]], name="pw")

   393         r = {}

   394         self.assertFalse(pw.match_seq([root], r))

   395         self.assertEqual(r, {})

   396         self.assertFalse(pw.match_seq([n1], r))

   397         self.assertEqual(r, {})

   398         self.assertTrue(pw.match_seq([n2], r))

   399         # These are easier to debug

   400         self.assertEqual(sorted(r.keys()), ["pl", "pn", "pw"])

   401         self.assertEqual(r["pl"], l1)

   402         self.assertEqual(r["pn"], n2)

   403         self.assertEqual(r["pw"], [n2])

   404         # But this is equivalent

   405         self.assertEqual(r, {"pl": l1, "pn": n2, "pw": [n2]})

   406         r = {}

   407         self.assertTrue(pw.match_seq([l1, l3], r))

   408         self.assertEqual(r, {"pl": l3, "pw": [l1, l3]})

   409         self.assert_(r["pl"] is l3)

   410         r = {}

   411 

   412     def testGenerateMatches(self):

   413         la = pytree.Leaf(1, "a")

   414         lb = pytree.Leaf(1, "b")

   415         lc = pytree.Leaf(1, "c")

   416         ld = pytree.Leaf(1, "d")

   417         le = pytree.Leaf(1, "e")

   418         lf = pytree.Leaf(1, "f")

   419         leaves = [la, lb, lc, ld, le, lf]

   420         root = pytree.Node(1000, leaves)

   421         pa = pytree.LeafPattern(1, "a", "pa")

   422         pb = pytree.LeafPattern(1, "b", "pb")

   423         pc = pytree.LeafPattern(1, "c", "pc")

   424         pd = pytree.LeafPattern(1, "d", "pd")

   425         pe = pytree.LeafPattern(1, "e", "pe")

   426         pf = pytree.LeafPattern(1, "f", "pf")

   427         pw = pytree.WildcardPattern([[pa, pb, pc], [pd, pe],

   428                                      [pa, pb], [pc, pd], [pe, pf]],

   429                                     min=1, max=4, name="pw")

   430         self.assertEqual([x[0] for x in pw.generate_matches(leaves)],

   431                          [3, 5, 2, 4, 6])

   432         pr = pytree.NodePattern(type=1000, content=[pw], name="pr")

   433         matches = list(pytree.generate_matches([pr], [root]))

   434         self.assertEqual(len(matches), 1)

   435         c, r = matches[0]

   436         self.assertEqual(c, 1)

   437         self.assertEqual(str(r["pr"]), "abcdef")

   438         self.assertEqual(r["pw"], [la, lb, lc, ld, le, lf])

   439         for c in "abcdef":

   440             self.assertEqual(r["p" + c], pytree.Leaf(1, c))

   441 

   442     def testHasKeyExample(self):

   443         pattern = pytree.NodePattern(331,

   444                                      (pytree.LeafPattern(7),

   445                                       pytree.WildcardPattern(name="args"),

   446                                       pytree.LeafPattern(8)))

   447         l1 = pytree.Leaf(7, "(")

   448         l2 = pytree.Leaf(3, "x")

   449         l3 = pytree.Leaf(8, ")")

   450         node = pytree.Node(331, [l1, l2, l3])

   451         r = {}

   452         self.assert_(pattern.match(node, r))

   453         self.assertEqual(r["args"], [l2])

   454 

   455 

   456 if __name__ == "__main__":

   457     import __main__

   458     support.run_all_tests(__main__)