← 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: Canonical.com Patch Queue Manager
  • Date: 2009-10-26 15:59:54 UTC
  • mfrom: (4679.9.25 2.1-static-tuple-chk-map)
  • Revision ID: pqm@pqm.ubuntu.com-20091026155954-r9gw2rizkikw7cg7
(jam) Start using StaticTuple as part of the chk_map code.

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
36
 
36
37
class TestNode(tests.TestCase):
831
832
        # 'ab' and 'ac' nodes
832
833
        chkmap.map(('aad',), 'v')
833
834
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
834
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
835
 
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
 
835
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
836
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
836
837
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
837
838
        # to map in 'ab'
838
839
        chkmap.unmap(('acd',))
839
840
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
840
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
841
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
841
842
 
842
843
    def test_unmap_without_fitting_doesnt_page_in(self):
843
844
        store = self.get_chk_bytes()
860
861
        chkmap.map(('aaf',), 'v')
861
862
        # At this point, the previous nodes should not be paged in, but the
862
863
        # newly added nodes would be
863
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
864
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
864
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
865
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
865
866
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
866
867
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
867
868
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
869
870
        # Now unmapping one of the new nodes will use only the already-paged-in
870
871
        # nodes to determine that we don't need to do more.
871
872
        chkmap.unmap(('aaf',))
872
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
873
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
873
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
874
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
874
875
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
875
876
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
876
877
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
897
898
        chkmap.map(('aad',), 'v')
898
899
        # At this point, the previous nodes should not be paged in, but the
899
900
        # newly added node would be
900
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
901
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
902
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
901
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
902
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
903
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
903
904
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
904
905
        # Unmapping the new node will check the existing nodes to see if they
905
906
        # would fit.
937
938
        chkmap.map(('aad',), 'v')
938
939
        # At this point, the previous nodes should not be paged in, but the
939
940
        # newly added node would be
940
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
941
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
942
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
941
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
942
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
943
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
943
944
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
944
945
        # Now clear the page cache, and only include 2 of the children in the
945
946
        # cache
954
955
        # Unmapping the new node will check the nodes from the page cache
955
956
        # first, and not have to read in 'aaa'
956
957
        chkmap.unmap(('aad',))
957
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
958
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
958
959
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
959
960
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
960
961
 
974
975
        chkmap.map(('aaf',), 'val')
975
976
        # At this point, the previous nodes should not be paged in, but the
976
977
        # newly added node would be
977
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
978
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
979
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
978
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
979
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
980
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
980
981
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
981
982
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
982
983
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
984
985
        # Unmapping a new node will see the other nodes that are already in
985
986
        # memory, and not need to page in anything else
986
987
        chkmap.unmap(('aad',))
987
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
988
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
989
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
988
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
989
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
990
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
990
991
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
991
992
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
992
993
 
1031
1032
            {('a',): 'content here', ('b',): 'more content'},
1032
1033
            chk_bytes=basis._store, maximum_size=10)
1033
1034
        list(target.iter_changes(basis))
1034
 
        self.assertIsInstance(target._root_node, tuple)
1035
 
        self.assertIsInstance(basis._root_node, tuple)
 
1035
        self.assertIsInstance(target._root_node, StaticTuple)
 
1036
        self.assertIsInstance(basis._root_node, StaticTuple)
1036
1037
 
1037
1038
    def test_iter_changes_ab_ab_changed_values_shown(self):
1038
1039
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1144
1145
 
1145
1146
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1146
1147
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1147
 
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
1148
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1149
 
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
 
1148
        self.assertEqual('E8B7BE43\x00E8B7BE43',
 
1149
                         search_key_func(StaticTuple('a', 'a')))
 
1150
        self.assertEqual('E8B7BE43\x0071BEEFF9',
 
1151
                         search_key_func(StaticTuple('a', 'b')))
 
1152
        self.assertEqual('71BEEFF9\x0000000000',
 
1153
                         search_key_func(StaticTuple('b', '')))
1150
1154
        chkmap = self._get_map(
1151
1155
            {("a","a"):"content here", ("a", "b",):"more content",
1152
1156
             ("b", ""): 'boring content'},
1449
1453
                             , chkmap._dump_tree())
1450
1454
 
1451
1455
 
1452
 
class TestSearchKeyFuncs(tests.TestCase):
1453
 
 
1454
 
    def assertSearchKey16(self, expected, key):
1455
 
        self.assertEqual(expected, chk_map._search_key_16(key))
1456
 
 
1457
 
    def assertSearchKey255(self, expected, key):
1458
 
        actual = chk_map._search_key_255(key)
1459
 
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1460
 
 
1461
 
    def test_simple_16(self):
1462
 
        self.assertSearchKey16('8C736521', ('foo',))
1463
 
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1464
 
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1465
 
        self.assertSearchKey16('ED82CD11', ('abcd',))
1466
 
 
1467
 
    def test_simple_255(self):
1468
 
        self.assertSearchKey255('\x8cse!', ('foo',))
1469
 
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1470
 
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1471
 
        # The standard mapping for these would include '\n', so it should be
1472
 
        # mapped to '_'
1473
 
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1474
 
 
1475
 
    def test_255_does_not_include_newline(self):
1476
 
        # When mapping via _search_key_255, we should never have the '\n'
1477
 
        # character, but all other 255 values should be present
1478
 
        chars_used = set()
1479
 
        for char_in in range(256):
1480
 
            search_key = chk_map._search_key_255((chr(char_in),))
1481
 
            chars_used.update(search_key)
1482
 
        all_chars = set([chr(x) for x in range(256)])
1483
 
        unused_chars = all_chars.symmetric_difference(chars_used)
1484
 
        self.assertEqual(set('\n'), unused_chars)
1485
 
 
1486
 
 
1487
1456
class TestLeafNode(TestCaseWithStore):
1488
1457
 
1489
1458
    def test_current_size_empty(self):
1908
1877
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1909
1878
        node = InternalNode(search_key_func=search_key_func)
1910
1879
        leaf1 = LeafNode(search_key_func=search_key_func)
1911
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1880
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1912
1881
        leaf2 = LeafNode(search_key_func=search_key_func)
1913
 
        leaf2.map(None, ('strange',), 'beast')
1914
 
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1915
 
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
 
1882
        leaf2.map(None, StaticTuple('strange',), 'beast')
 
1883
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
 
1884
        self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1916
1885
        node.add_node("\xbe", leaf1)
1917
1886
        # This sets up a path that should not be followed - it will error if
1918
1887
        # the code tries to.
1919
1888
        node._items['\xbe'] = None
1920
1889
        node.add_node("\x85", leaf2)
1921
1890
        self.assertEqual([(('strange',), 'beast')],
1922
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1891
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1892
                                         StaticTuple('weird',)])))
1923
1893
 
1924
1894
    def test_iteritems_partial_empty(self):
1925
1895
        node = InternalNode()
1932
1902
        # Ensure test validity: nothing paged in below the root.
1933
1903
        self.assertEqual(2,
1934
1904
            len([value for value in node._items.values()
1935
 
                if type(value) == tuple]))
 
1905
                if type(value) is StaticTuple]))
1936
1906
        # now, mapping to k3 should add a k3 leaf
1937
1907
        prefix, nodes = node.map(None, ('k3',), 'quux')
1938
1908
        self.assertEqual("k", prefix)
1971
1941
        # Ensure test validity: nothing paged in below the root.
1972
1942
        self.assertEqual(2,
1973
1943
            len([value for value in node._items.values()
1974
 
                if type(value) == tuple]))
 
1944
                if type(value) is StaticTuple]))
1975
1945
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1976
1946
        # k23, which for simplicity in the current implementation generates
1977
1947
        # a new internal node between node, and k22/k23.
2016
1986
        node = InternalNode(search_key_func=search_key_func)
2017
1987
        node._key_width = 2
2018
1988
        node._node_width = 4
2019
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
2020
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
2021
 
        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',)))
2022
1995
 
2023
1996
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2024
1997
        chkmap = self._get_map(