← 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-10-20 22:13:23 UTC
  • mto: This revision was merged to the branch mainline in revision 4771.
  • Revision ID: john@arbash-meinel.com-20091020221323-vvukgazqxkicb70n
A bit broken, but getting there.

Start being much stricter about requiring StaticTuples everywhere.
I may go back and loosen this restriction, but getting the code base
StaticTuple pure is probably a good idea. The main reason to be 'looser'
is so that things don't fail 'in the wild' just because someone
calls an api with a tuple rather than a StaticTuple.
However, I'd like the internals to be 'pure' if possible.
We'll see.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_chk_map.py
31
31
    LeafNode,
32
32
    Node,
33
33
    )
 
34
from bzrlib.static_tuple import StaticTuple
34
35
 
35
 
key_types = (tuple, chk_map._key_type)
36
36
 
37
37
class TestNode(tests.TestCase):
38
38
 
74
74
                 search_key_func=None):
75
75
        if chk_bytes is None:
76
76
            chk_bytes = self.get_chk_bytes()
 
77
        a_dict = dict((StaticTuple(*k), v) for k, v in a_dict.iteritems())
77
78
        root_key = CHKMap.from_dict(chk_bytes, a_dict,
78
79
            maximum_size=maximum_size, key_width=key_width,
79
80
            search_key_func=search_key_func)
832
833
        # 'ab' and 'ac' nodes
833
834
        chkmap.map(('aad',), 'v')
834
835
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
835
 
        self.assertIsInstance(chkmap._root_node._items['ab'], key_types)
836
 
        self.assertIsInstance(chkmap._root_node._items['ac'], key_types)
 
836
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
837
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
837
838
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
838
839
        # to map in 'ab'
839
840
        chkmap.unmap(('acd',))
840
841
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
841
 
        self.assertIsInstance(chkmap._root_node._items['ab'], key_types)
 
842
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
842
843
 
843
844
    def test_unmap_without_fitting_doesnt_page_in(self):
844
845
        store = self.get_chk_bytes()
861
862
        chkmap.map(('aaf',), 'v')
862
863
        # At this point, the previous nodes should not be paged in, but the
863
864
        # newly added nodes would be
864
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
865
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
 
865
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
866
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
866
867
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
867
868
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
868
869
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
870
871
        # Now unmapping one of the new nodes will use only the already-paged-in
871
872
        # nodes to determine that we don't need to do more.
872
873
        chkmap.unmap(('aaf',))
873
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
874
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
 
874
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
875
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
875
876
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
876
877
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
877
878
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
898
899
        chkmap.map(('aad',), 'v')
899
900
        # At this point, the previous nodes should not be paged in, but the
900
901
        # newly added node would be
901
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
902
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
903
 
        self.assertIsInstance(chkmap._root_node._items['aac'], key_types)
 
902
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
903
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
904
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
904
905
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
905
906
        # Unmapping the new node will check the existing nodes to see if they
906
907
        # would fit.
938
939
        chkmap.map(('aad',), 'v')
939
940
        # At this point, the previous nodes should not be paged in, but the
940
941
        # newly added node would be
941
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
942
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
943
 
        self.assertIsInstance(chkmap._root_node._items['aac'], key_types)
 
942
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
943
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
944
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
944
945
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
945
946
        # Now clear the page cache, and only include 2 of the children in the
946
947
        # cache
955
956
        # Unmapping the new node will check the nodes from the page cache
956
957
        # first, and not have to read in 'aaa'
957
958
        chkmap.unmap(('aad',))
958
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
 
959
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
959
960
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
960
961
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
961
962
 
975
976
        chkmap.map(('aaf',), 'val')
976
977
        # At this point, the previous nodes should not be paged in, but the
977
978
        # newly added node would be
978
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
979
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
980
 
        self.assertIsInstance(chkmap._root_node._items['aac'], key_types)
 
979
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
980
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
981
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
981
982
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
982
983
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
983
984
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
985
986
        # Unmapping a new node will see the other nodes that are already in
986
987
        # memory, and not need to page in anything else
987
988
        chkmap.unmap(('aad',))
988
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], key_types)
989
 
        self.assertIsInstance(chkmap._root_node._items['aab'], key_types)
990
 
        self.assertIsInstance(chkmap._root_node._items['aac'], key_types)
 
989
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
990
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
991
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
991
992
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
992
993
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
993
994
 
1032
1033
            {('a',): 'content here', ('b',): 'more content'},
1033
1034
            chk_bytes=basis._store, maximum_size=10)
1034
1035
        list(target.iter_changes(basis))
1035
 
        self.assertIsInstance(target._root_node, key_types)
1036
 
        self.assertIsInstance(basis._root_node, key_types)
 
1036
        self.assertIsInstance(target._root_node, StaticTuple)
 
1037
        self.assertIsInstance(basis._root_node, StaticTuple)
1037
1038
 
1038
1039
    def test_iter_changes_ab_ab_changed_values_shown(self):
1039
1040
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1132
1133
    def test_iteritems_selected_one_of_two_items(self):
1133
1134
        chkmap = self._get_map( {("a",):"content here", ("b",):"more content"})
1134
1135
        self.assertEqual({("a",): "content here"},
1135
 
            self.to_dict(chkmap, [("a",)]))
 
1136
            self.to_dict(chkmap, [StaticTuple("a",)]))
1136
1137
 
1137
1138
    def test_iteritems_keys_prefixed_by_2_width_nodes(self):
1138
1139
        chkmap = self._get_map(
1141
1142
            maximum_size=10, key_width=2)
1142
1143
        self.assertEqual(
1143
1144
            {("a", "a"): "content here", ("a", "b"): 'more content'},
1144
 
            self.to_dict(chkmap, [("a",)]))
 
1145
            self.to_dict(chkmap, [StaticTuple("a",)]))
1145
1146
 
1146
1147
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1147
1148
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1148
 
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
1149
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1150
 
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
 
1149
        self.assertEqual('E8B7BE43\x00E8B7BE43',
 
1150
                         search_key_func(StaticTuple('a', 'a')))
 
1151
        self.assertEqual('E8B7BE43\x0071BEEFF9',
 
1152
                         search_key_func(StaticTuple('a', 'b')))
 
1153
        self.assertEqual('71BEEFF9\x0000000000',
 
1154
                         search_key_func(StaticTuple('b', '')))
1151
1155
        chkmap = self._get_map(
1152
1156
            {("a","a"):"content here", ("a", "b",):"more content",
1153
1157
             ("b", ""): 'boring content'},
1154
1158
            maximum_size=10, key_width=2, search_key_func=search_key_func)
1155
1159
        self.assertEqual(
1156
1160
            {("a", "a"): "content here", ("a", "b"): 'more content'},
1157
 
            self.to_dict(chkmap, [("a",)]))
 
1161
            self.to_dict(chkmap, [StaticTuple("a",)]))
1158
1162
 
1159
1163
    def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):
1160
1164
        chkmap = self._get_map(
1162
1166
             ("b", ""): 'boring content'}, key_width=2)
1163
1167
        self.assertEqual(
1164
1168
            {("a", "a"): "content here", ("a", "b"): 'more content'},
1165
 
            self.to_dict(chkmap, [("a",)]))
 
1169
            self.to_dict(chkmap, [StaticTuple("a",)]))
1166
1170
 
1167
1171
    def test___len__empty(self):
1168
1172
        chkmap = self._get_map({})
1377
1381
        chkmap = chk_map.CHKMap(chk_bytes, None,
1378
1382
                                search_key_func=chk_map._search_key_16)
1379
1383
        chkmap._root_node.set_maximum_size(10)
1380
 
        chkmap.map(('1',), 'foo')
1381
 
        chkmap.map(('2',), 'bar')
1382
 
        chkmap.map(('3',), 'baz')
 
1384
        chkmap.map(StaticTuple('1',), 'foo')
 
1385
        chkmap.map(StaticTuple('2',), 'bar')
 
1386
        chkmap.map(StaticTuple('3',), 'baz')
1383
1387
        self.assertEqualDiff("'' InternalNode\n"
1384
1388
                             "  '1' LeafNode\n"
1385
1389
                             "      ('2',) 'bar'\n"
1393
1397
                                search_key_func=chk_map._search_key_16)
1394
1398
        # We can get the values back correctly
1395
1399
        self.assertEqual([(('1',), 'foo')],
1396
 
                         list(chkmap.iteritems([('1',)])))
 
1400
                         list(chkmap.iteritems([StaticTuple('1',)])))
1397
1401
        self.assertEqualDiff("'' InternalNode\n"
1398
1402
                             "  '1' LeafNode\n"
1399
1403
                             "      ('2',) 'bar'\n"
1408
1412
        chkmap = chk_map.CHKMap(chk_bytes, None,
1409
1413
                                search_key_func=chk_map._search_key_255)
1410
1414
        chkmap._root_node.set_maximum_size(10)
1411
 
        chkmap.map(('1',), 'foo')
1412
 
        chkmap.map(('2',), 'bar')
1413
 
        chkmap.map(('3',), 'baz')
 
1415
        chkmap.map(StaticTuple('1',), 'foo')
 
1416
        chkmap.map(StaticTuple('2',), 'bar')
 
1417
        chkmap.map(StaticTuple('3',), 'baz')
1414
1418
        self.assertEqualDiff("'' InternalNode\n"
1415
1419
                             "  '\\x1a' LeafNode\n"
1416
1420
                             "      ('2',) 'bar'\n"
1424
1428
                                search_key_func=chk_map._search_key_255)
1425
1429
        # We can get the values back correctly
1426
1430
        self.assertEqual([(('1',), 'foo')],
1427
 
                         list(chkmap.iteritems([('1',)])))
 
1431
                         list(chkmap.iteritems([StaticTuple('1',)])))
1428
1432
        self.assertEqualDiff("'' InternalNode\n"
1429
1433
                             "  '\\x1a' LeafNode\n"
1430
1434
                             "      ('2',) 'bar'\n"
1450
1454
                             , chkmap._dump_tree())
1451
1455
 
1452
1456
 
1453
 
class TestSearchKeyFuncs(tests.TestCase):
1454
 
 
1455
 
    def assertSearchKey16(self, expected, key):
1456
 
        self.assertEqual(expected, chk_map._search_key_16(key))
1457
 
 
1458
 
    def assertSearchKey255(self, expected, key):
1459
 
        actual = chk_map._search_key_255(key)
1460
 
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1461
 
 
1462
 
    def test_simple_16(self):
1463
 
        self.assertSearchKey16('8C736521', ('foo',))
1464
 
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1465
 
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1466
 
        self.assertSearchKey16('ED82CD11', ('abcd',))
1467
 
 
1468
 
    def test_simple_255(self):
1469
 
        self.assertSearchKey255('\x8cse!', ('foo',))
1470
 
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1471
 
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1472
 
        # The standard mapping for these would include '\n', so it should be
1473
 
        # mapped to '_'
1474
 
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1475
 
 
1476
 
    def test_255_does_not_include_newline(self):
1477
 
        # When mapping via _search_key_255, we should never have the '\n'
1478
 
        # character, but all other 255 values should be present
1479
 
        chars_used = set()
1480
 
        for char_in in range(256):
1481
 
            search_key = chk_map._search_key_255((chr(char_in),))
1482
 
            chars_used.update(search_key)
1483
 
        all_chars = set([chr(x) for x in range(256)])
1484
 
        unused_chars = all_chars.symmetric_difference(chars_used)
1485
 
        self.assertEqual(set('\n'), unused_chars)
1486
 
 
1487
 
 
1488
1457
class TestLeafNode(TestCaseWithStore):
1489
1458
 
1490
1459
    def test_current_size_empty(self):
1909
1878
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1910
1879
        node = InternalNode(search_key_func=search_key_func)
1911
1880
        leaf1 = LeafNode(search_key_func=search_key_func)
1912
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1881
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1913
1882
        leaf2 = LeafNode(search_key_func=search_key_func)
1914
 
        leaf2.map(None, ('strange',), 'beast')
1915
 
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1916
 
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
 
1883
        leaf2.map(None, StaticTuple('strange',), 'beast')
 
1884
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
 
1885
        self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1917
1886
        node.add_node("\xbe", leaf1)
1918
1887
        # This sets up a path that should not be followed - it will error if
1919
1888
        # the code tries to.
1920
1889
        node._items['\xbe'] = None
1921
1890
        node.add_node("\x85", leaf2)
1922
1891
        self.assertEqual([(('strange',), 'beast')],
1923
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1892
            sorted(node.iteritems(None, [StaticTuple('strange',), StaticTuple('weird',)])))
1924
1893
 
1925
1894
    def test_iteritems_partial_empty(self):
1926
1895
        node = InternalNode()
1933
1902
        # Ensure test validity: nothing paged in below the root.
1934
1903
        self.assertEqual(2,
1935
1904
            len([value for value in node._items.values()
1936
 
                if type(value) in key_types]))
 
1905
                if type(value) is StaticTuple]))
1937
1906
        # now, mapping to k3 should add a k3 leaf
1938
1907
        prefix, nodes = node.map(None, ('k3',), 'quux')
1939
1908
        self.assertEqual("k", prefix)
1972
1941
        # Ensure test validity: nothing paged in below the root.
1973
1942
        self.assertEqual(2,
1974
1943
            len([value for value in node._items.values()
1975
 
                if type(value) in key_types]))
 
1944
                if type(value) is StaticTuple]))
1976
1945
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1977
1946
        # k23, which for simplicity in the current implementation generates
1978
1947
        # a new internal node between node, and k22/k23.
2017
1986
        node = InternalNode(search_key_func=search_key_func)
2018
1987
        node._key_width = 2
2019
1988
        node._node_width = 4
2020
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
2021
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
2022
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
 
1989
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
 
1990
            StaticTuple('a', 'b')))
 
1991
        self.assertEqual('E8B7', node._search_prefix_filter(
 
1992
            StaticTuple('a', 'b')))
 
1993
        self.assertEqual('E8B7', node._search_prefix_filter(
 
1994
            StaticTuple('a',)))
2023
1995
 
2024
1996
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2025
1997
        chkmap = self._get_map(
2159
2131
    def help__read_all_roots(self, search_key_func):
2160
2132
        c_map = self.make_root_only_map(search_key_func=search_key_func)
2161
2133
        key1 = c_map.key()
2162
 
        c_map.map(('aaa',), 'new aaa content')
 
2134
        c_map.map(StaticTuple('aaa',), 'new aaa content')
2163
2135
        key2 = c_map._save()
2164
2136
        diff = self.get_difference([key2], [key1], search_key_func)
2165
2137
        root_results = [record.key for record in diff._read_all_roots()]