← 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: Ian Clatworthy
  • Date: 2009-09-09 00:49:50 UTC
  • mto: (4634.37.2 prepare-2.0)
  • mto: This revision was merged to the branch mainline in revision 4689.
  • Revision ID: ian.clatworthy@canonical.com-20090909004950-43z4zdicb5u91iet
tweak quick reference naming to make it consistent with other PDFs

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_chk_map.py
1
 
# Copyright (C) 2008, 2009, 2010 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
31
31
    LeafNode,
32
32
    Node,
33
33
    )
34
 
from bzrlib.static_tuple import StaticTuple
35
34
 
36
35
 
37
36
class TestNode(tests.TestCase):
832
831
        # 'ab' and 'ac' nodes
833
832
        chkmap.map(('aad',), 'v')
834
833
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
835
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
836
 
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
 
834
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
835
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
837
836
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
838
837
        # to map in 'ab'
839
838
        chkmap.unmap(('acd',))
840
839
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
841
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
840
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
842
841
 
843
842
    def test_unmap_without_fitting_doesnt_page_in(self):
844
843
        store = self.get_chk_bytes()
861
860
        chkmap.map(('aaf',), 'v')
862
861
        # At this point, the previous nodes should not be paged in, but the
863
862
        # newly added nodes would be
864
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
865
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
863
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
864
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
866
865
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
867
866
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
868
867
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
870
869
        # Now unmapping one of the new nodes will use only the already-paged-in
871
870
        # nodes to determine that we don't need to do more.
872
871
        chkmap.unmap(('aaf',))
873
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
874
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
872
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
873
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
875
874
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
876
875
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
877
876
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
898
897
        chkmap.map(('aad',), 'v')
899
898
        # At this point, the previous nodes should not be paged in, but the
900
899
        # newly added node would be
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)
 
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)
904
903
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
905
904
        # Unmapping the new node will check the existing nodes to see if they
906
905
        # would fit.
907
906
        # Clear the page cache so we ensure we have to read all the children
908
 
        chk_map.clear_cache()
 
907
        chk_map._page_cache.clear()
909
908
        chkmap.unmap(('aad',))
910
909
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
911
910
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
938
937
        chkmap.map(('aad',), 'v')
939
938
        # At this point, the previous nodes should not be paged in, but the
940
939
        # newly added node would be
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)
 
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)
944
943
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
945
944
        # Now clear the page cache, and only include 2 of the children in the
946
945
        # cache
947
946
        aab_key = chkmap._root_node._items['aab']
948
 
        aab_bytes = chk_map._get_cache()[aab_key]
 
947
        aab_bytes = chk_map._page_cache[aab_key]
949
948
        aac_key = chkmap._root_node._items['aac']
950
 
        aac_bytes = chk_map._get_cache()[aac_key]
951
 
        chk_map.clear_cache()
952
 
        chk_map._get_cache()[aab_key] = aab_bytes
953
 
        chk_map._get_cache()[aac_key] = aac_bytes
 
949
        aac_bytes = chk_map._page_cache[aac_key]
 
950
        chk_map._page_cache.clear()
 
951
        chk_map._page_cache[aab_key] = aab_bytes
 
952
        chk_map._page_cache[aac_key] = aac_bytes
954
953
 
955
954
        # Unmapping the new node will check the nodes from the page cache
956
955
        # first, and not have to read in 'aaa'
957
956
        chkmap.unmap(('aad',))
958
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
957
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
959
958
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
960
959
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
961
960
 
975
974
        chkmap.map(('aaf',), 'val')
976
975
        # At this point, the previous nodes should not be paged in, but the
977
976
        # newly added node would be
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)
 
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)
981
980
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
982
981
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
983
982
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
985
984
        # Unmapping a new node will see the other nodes that are already in
986
985
        # memory, and not need to page in anything else
987
986
        chkmap.unmap(('aad',))
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)
 
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)
991
990
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
992
991
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
993
992
 
1032
1031
            {('a',): 'content here', ('b',): 'more content'},
1033
1032
            chk_bytes=basis._store, maximum_size=10)
1034
1033
        list(target.iter_changes(basis))
1035
 
        self.assertIsInstance(target._root_node, StaticTuple)
1036
 
        self.assertIsInstance(basis._root_node, StaticTuple)
 
1034
        self.assertIsInstance(target._root_node, tuple)
 
1035
        self.assertIsInstance(basis._root_node, tuple)
1037
1036
 
1038
1037
    def test_iter_changes_ab_ab_changed_values_shown(self):
1039
1038
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1145
1144
 
1146
1145
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1147
1146
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
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', '')))
 
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', '')))
1154
1150
        chkmap = self._get_map(
1155
1151
            {("a","a"):"content here", ("a", "b",):"more content",
1156
1152
             ("b", ""): 'boring content'},
1453
1449
                             , chkmap._dump_tree())
1454
1450
 
1455
1451
 
 
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
 
1456
1487
class TestLeafNode(TestCaseWithStore):
1457
1488
 
1458
1489
    def test_current_size_empty(self):
1877
1908
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1878
1909
        node = InternalNode(search_key_func=search_key_func)
1879
1910
        leaf1 = LeafNode(search_key_func=search_key_func)
1880
 
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
 
1911
        leaf1.map(None, ('foo bar',), 'quux')
1881
1912
        leaf2 = LeafNode(search_key_func=search_key_func)
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',)))
 
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',)))
1885
1916
        node.add_node("\xbe", leaf1)
1886
1917
        # This sets up a path that should not be followed - it will error if
1887
1918
        # the code tries to.
1888
1919
        node._items['\xbe'] = None
1889
1920
        node.add_node("\x85", leaf2)
1890
1921
        self.assertEqual([(('strange',), 'beast')],
1891
 
            sorted(node.iteritems(None, [StaticTuple('strange',),
1892
 
                                         StaticTuple('weird',)])))
 
1922
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1893
1923
 
1894
1924
    def test_iteritems_partial_empty(self):
1895
1925
        node = InternalNode()
1902
1932
        # Ensure test validity: nothing paged in below the root.
1903
1933
        self.assertEqual(2,
1904
1934
            len([value for value in node._items.values()
1905
 
                if type(value) is StaticTuple]))
 
1935
                if type(value) == tuple]))
1906
1936
        # now, mapping to k3 should add a k3 leaf
1907
1937
        prefix, nodes = node.map(None, ('k3',), 'quux')
1908
1938
        self.assertEqual("k", prefix)
1941
1971
        # Ensure test validity: nothing paged in below the root.
1942
1972
        self.assertEqual(2,
1943
1973
            len([value for value in node._items.values()
1944
 
                if type(value) is StaticTuple]))
 
1974
                if type(value) == tuple]))
1945
1975
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1946
1976
        # k23, which for simplicity in the current implementation generates
1947
1977
        # a new internal node between node, and k22/k23.
1986
2016
        node = InternalNode(search_key_func=search_key_func)
1987
2017
        node._key_width = 2
1988
2018
        node._node_width = 4
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',)))
 
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',)))
1995
2022
 
1996
2023
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1997
2024
        chkmap = self._get_map(