← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_chk_map.py

  • Committer: John Arbash Meinel
  • Date: 2009-07-08 14:37:25 UTC
  • mfrom: (4516 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4517.
  • Revision ID: john@arbash-meinel.com-20090708143725-sc9sjy3mz4cxwxzz
Merge bzr.dev 4516

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_chk_map.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
78
78
        root_key = CHKMap.from_dict(chk_bytes, a_dict,
79
79
            maximum_size=maximum_size, key_width=key_width,
80
80
            search_key_func=search_key_func)
 
81
        root_key2 = CHKMap._create_via_map(chk_bytes, a_dict,
 
82
            maximum_size=maximum_size, key_width=key_width,
 
83
            search_key_func=search_key_func)
 
84
        self.assertEqual(root_key, root_key2, "CHKMap.from_dict() did not"
 
85
                         " match CHKMap._create_via_map")
81
86
        chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)
82
87
        return chkmap
83
88
 
1560
1565
        child.map(None, ("baz",), "val")
1561
1566
        node.add_node("b", child)
1562
1567
 
1563
 
        key_filter = (('foo',), ('fob',), ('bar',), ('baz',))
 
1568
        # Note that 'ram' doesn't match anything, so it should be freely
 
1569
        # ignored
 
1570
        key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
1564
1571
        for child, node_key_filter in node._iter_nodes(None,
1565
1572
                                                       key_filter=key_filter):
1566
 
            # each child could matches two key filters, so make sure they were
 
1573
            # each child could match two key filters, so make sure they were
1567
1574
            # both included.
1568
1575
            self.assertEqual(2, len(node_key_filter))
1569
1576
 
 
1577
    def make_fo_fa_node(self):
 
1578
        node = InternalNode('f')
 
1579
        child = LeafNode()
 
1580
        child.set_maximum_size(100)
 
1581
        child.map(None, ("foo",), "val")
 
1582
        child.map(None, ("fob",), "val")
 
1583
        node.add_node('fo', child)
 
1584
        child = LeafNode()
 
1585
        child.set_maximum_size(100)
 
1586
        child.map(None, ("far",), "val")
 
1587
        child.map(None, ("faz",), "val")
 
1588
        node.add_node("fa", child)
 
1589
        return node
 
1590
 
 
1591
    def test__iter_nodes_single_entry(self):
 
1592
        node = self.make_fo_fa_node()
 
1593
        key_filter = [('foo',)]
 
1594
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1595
        self.assertEqual(1, len(nodes))
 
1596
        self.assertEqual(key_filter, nodes[0][1])
 
1597
 
 
1598
    def test__iter_nodes_single_entry_misses(self):
 
1599
        node = self.make_fo_fa_node()
 
1600
        key_filter = [('bar',)]
 
1601
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1602
        self.assertEqual(0, len(nodes))
 
1603
 
 
1604
    def test__iter_nodes_mixed_key_width(self):
 
1605
        node = self.make_fo_fa_node()
 
1606
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
 
1607
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1608
        self.assertEqual(1, len(nodes))
 
1609
        matches = key_filter[:]
 
1610
        matches.remove(('b',))
 
1611
        self.assertEqual(sorted(matches), sorted(nodes[0][1]))
 
1612
 
 
1613
    def test__iter_nodes_match_all(self):
 
1614
        node = self.make_fo_fa_node()
 
1615
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
 
1616
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1617
        self.assertEqual(2, len(nodes))
 
1618
 
 
1619
    def test__iter_nodes_fixed_widths_and_misses(self):
 
1620
        node = self.make_fo_fa_node()
 
1621
        # foo and faa should both match one child, baz should miss
 
1622
        key_filter = [('foo',), ('faa',), ('baz',)]
 
1623
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1624
        self.assertEqual(2, len(nodes))
 
1625
        for node, matches in nodes:
 
1626
            self.assertEqual(1, len(matches))
 
1627
 
1570
1628
    def test_iteritems_empty_new(self):
1571
1629
        node = InternalNode()
1572
1630
        self.assertEqual([], sorted(node.iteritems(None)))
1836
1894
                                    self).get_chk_bytes()
1837
1895
        return self._chk_bytes
1838
1896
 
1839
 
    def get_map_key(self, a_dict):
1840
 
        c_map = self._get_map(a_dict, maximum_size=10,
 
1897
    def get_map_key(self, a_dict, maximum_size=10):
 
1898
        c_map = self._get_map(a_dict, maximum_size=maximum_size,
1841
1899
                              chk_bytes=self.get_chk_bytes())
1842
1900
        return c_map.key()
1843
1901
 
2060
2118
             (aac_key, [(('aac',), 'target1')]),
2061
2119
             (bba_key, [(('bba',), 'target2')]),
2062
2120
            ], [target1, target2], [basis1, basis2])
 
2121
 
 
2122
    def test_multiple_maps_overlapping_common_new(self):
 
2123
        # Test that when a node found through the interesting_keys iteration
 
2124
        # for *some roots* and also via the uninteresting keys iteration, that
 
2125
        # it is still scanned for uninteresting refs and items, because its
 
2126
        # not truely new. This requires 2 levels of InternalNodes to expose,
 
2127
        # because of the way the bootstrap in _find_children_info works.
 
2128
        # This suggests that the code is probably amenable to/benefit from
 
2129
        # consolidation.
 
2130
        # How does this test work?
 
2131
        # 1) We need a second level InternalNode present in a basis tree.
 
2132
        # 2) We need a left side new tree that uses that InternalNode
 
2133
        # 3) We need a right side new tree that does not use that InternalNode
 
2134
        #    at all but that has an unchanged *value* that was reachable inside
 
2135
        #    that InternalNode
 
2136
        basis = self.get_map_key({
 
2137
            # InternalNode, unchanged in left:
 
2138
            ('aaa',): 'left',
 
2139
            ('abb',): 'right',
 
2140
            # Forces an internalNode at 'a'
 
2141
            ('ccc',): 'common',
 
2142
            })
 
2143
        left = self.get_map_key({
 
2144
            # All of basis unchanged
 
2145
            ('aaa',): 'left',
 
2146
            ('abb',): 'right',
 
2147
            ('ccc',): 'common',
 
2148
            # And a new top level node so the root key is different
 
2149
            ('ddd',): 'change',
 
2150
            })
 
2151
        right = self.get_map_key({
 
2152
            # A value that is unchanged from basis and thus should be filtered
 
2153
            # out.
 
2154
            ('abb',): 'right'
 
2155
            })
 
2156
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2157
        self.assertEqualDiff(
 
2158
            "'' InternalNode\n"
 
2159
            "  'a' InternalNode\n"
 
2160
            "    'aa' LeafNode\n"
 
2161
            "      ('aaa',) 'left'\n"
 
2162
            "    'ab' LeafNode\n"
 
2163
            "      ('abb',) 'right'\n"
 
2164
            "  'c' LeafNode\n"
 
2165
            "      ('ccc',) 'common'\n",
 
2166
            basis_map._dump_tree())
 
2167
        # Get left expected data
 
2168
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2169
        self.assertEqualDiff(
 
2170
            "'' InternalNode\n"
 
2171
            "  'a' InternalNode\n"
 
2172
            "    'aa' LeafNode\n"
 
2173
            "      ('aaa',) 'left'\n"
 
2174
            "    'ab' LeafNode\n"
 
2175
            "      ('abb',) 'right'\n"
 
2176
            "  'c' LeafNode\n"
 
2177
            "      ('ccc',) 'common'\n"
 
2178
            "  'd' LeafNode\n"
 
2179
            "      ('ddd',) 'change'\n",
 
2180
            left_map._dump_tree())
 
2181
        # Keys from left side target
 
2182
        l_d_key = left_map._root_node._items['d'].key()
 
2183
        # Get right expected data
 
2184
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2185
        self.assertEqualDiff(
 
2186
            "'' LeafNode\n"
 
2187
            "      ('abb',) 'right'\n",
 
2188
            right_map._dump_tree())
 
2189
        # Keys from the right side target - none, the root is enough.
 
2190
        # Test behaviour
 
2191
        self.expectFailure("we don't properly filter different depths",
 
2192
            self.assertIterInteresting,
 
2193
            [(left, []),
 
2194
             (right, []),
 
2195
             (l_d_key, [(('ddd',), 'change')]),
 
2196
            ], [left, right], [basis])
 
2197
        self.assertIterInteresting(
 
2198
            [(left, []),
 
2199
             (right, []),
 
2200
             (l_d_key, [(('ddd',), 'change')]),
 
2201
            ], [left, right], [basis])
 
2202
 
 
2203
    def test_multiple_maps_similar(self):
 
2204
        # We want to have a depth=2 tree, with multiple entries in each leaf
 
2205
        # node
 
2206
        basis = self.get_map_key({
 
2207
            ('aaa',): 'unchanged',
 
2208
            ('abb',): 'will change left',
 
2209
            ('caa',): 'unchanged',
 
2210
            ('cbb',): 'will change right',
 
2211
            }, maximum_size=60)
 
2212
        left = self.get_map_key({
 
2213
            ('aaa',): 'unchanged',
 
2214
            ('abb',): 'changed left',
 
2215
            ('caa',): 'unchanged',
 
2216
            ('cbb',): 'will change right',
 
2217
            }, maximum_size=60)
 
2218
        right = self.get_map_key({
 
2219
            ('aaa',): 'unchanged',
 
2220
            ('abb',): 'will change left',
 
2221
            ('caa',): 'unchanged',
 
2222
            ('cbb',): 'changed right',
 
2223
            }, maximum_size=60)
 
2224
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2225
        self.assertEqualDiff(
 
2226
            "'' InternalNode\n"
 
2227
            "  'a' LeafNode\n"
 
2228
            "      ('aaa',) 'unchanged'\n"
 
2229
            "      ('abb',) 'will change left'\n"
 
2230
            "  'c' LeafNode\n"
 
2231
            "      ('caa',) 'unchanged'\n"
 
2232
            "      ('cbb',) 'will change right'\n",
 
2233
            basis_map._dump_tree())
 
2234
        # Get left expected data
 
2235
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2236
        self.assertEqualDiff(
 
2237
            "'' InternalNode\n"
 
2238
            "  'a' LeafNode\n"
 
2239
            "      ('aaa',) 'unchanged'\n"
 
2240
            "      ('abb',) 'changed left'\n"
 
2241
            "  'c' LeafNode\n"
 
2242
            "      ('caa',) 'unchanged'\n"
 
2243
            "      ('cbb',) 'will change right'\n",
 
2244
            left_map._dump_tree())
 
2245
        # Keys from left side target
 
2246
        l_a_key = left_map._root_node._items['a'].key()
 
2247
        l_c_key = left_map._root_node._items['c'].key()
 
2248
        # Get right expected data
 
2249
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2250
        self.assertEqualDiff(
 
2251
            "'' InternalNode\n"
 
2252
            "  'a' LeafNode\n"
 
2253
            "      ('aaa',) 'unchanged'\n"
 
2254
            "      ('abb',) 'will change left'\n"
 
2255
            "  'c' LeafNode\n"
 
2256
            "      ('caa',) 'unchanged'\n"
 
2257
            "      ('cbb',) 'changed right'\n",
 
2258
            right_map._dump_tree())
 
2259
        r_a_key = right_map._root_node._items['a'].key()
 
2260
        r_c_key = right_map._root_node._items['c'].key()
 
2261
        self.assertIterInteresting(
 
2262
            [(left, []),
 
2263
             (right, []),
 
2264
             (l_a_key, [(('abb',), 'changed left')]),
 
2265
             (r_c_key, [(('cbb',), 'changed right')]),
 
2266
            ], [left, right], [basis])