/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_chk_map.py

  • Committer: Aaron Bentley
  • Date: 2009-07-19 04:47:49 UTC
  • mto: This revision was merged to the branch mainline in revision 4549.
  • Revision ID: aaron@aaronbentley.com-20090719044749-mw2ddxyf7uflp18j
Fix tabs.

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
20
20
 
21
21
from bzrlib import (
22
22
    chk_map,
23
 
    errors,
24
23
    groupcompress,
25
24
    osutils,
26
25
    tests,
31
30
    LeafNode,
32
31
    Node,
33
32
    )
34
 
from bzrlib.static_tuple import StaticTuple
35
33
 
36
34
 
37
35
class TestNode(tests.TestCase):
65
63
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
66
64
 
67
65
    def get_chk_bytes(self):
68
 
        # This creates a standalone CHK store.
 
66
        # The easiest way to get a CHK store is a development6 repository and
 
67
        # then work with the chk_bytes attribute directly.
69
68
        factory = groupcompress.make_pack_factory(False, False, 1)
70
69
        self.chk_bytes = factory(self.get_transport())
71
70
        return self.chk_bytes
467
466
        # updated key.
468
467
        self.assertEqual(new_root, chkmap._root_node._key)
469
468
 
470
 
    def test_apply_new_keys_must_be_new(self):
471
 
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
472
 
        # an error.
473
 
        chk_bytes = self.get_chk_bytes()
474
 
        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
475
 
        chkmap = CHKMap(chk_bytes, root_key)
476
 
        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
477
 
            [(None, ("a",), "b")])
478
 
        # As an error occured, the update should have left us without changing
479
 
        # anything (the root should be unchanged).
480
 
        self.assertEqual(root_key, chkmap._root_node._key)
481
 
 
482
469
    def test_apply_delta_is_deterministic(self):
483
470
        chk_bytes = self.get_chk_bytes()
484
471
        chkmap1 = CHKMap(chk_bytes, None)
832
819
        # 'ab' and 'ac' nodes
833
820
        chkmap.map(('aad',), 'v')
834
821
        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)
 
822
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
823
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
837
824
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
838
825
        # to map in 'ab'
839
826
        chkmap.unmap(('acd',))
840
827
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
841
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
828
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
842
829
 
843
830
    def test_unmap_without_fitting_doesnt_page_in(self):
844
831
        store = self.get_chk_bytes()
861
848
        chkmap.map(('aaf',), 'v')
862
849
        # At this point, the previous nodes should not be paged in, but the
863
850
        # newly added nodes would be
864
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
865
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
851
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
852
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
866
853
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
867
854
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
868
855
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
870
857
        # Now unmapping one of the new nodes will use only the already-paged-in
871
858
        # nodes to determine that we don't need to do more.
872
859
        chkmap.unmap(('aaf',))
873
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
874
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
860
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
861
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
875
862
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
876
863
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
877
864
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
898
885
        chkmap.map(('aad',), 'v')
899
886
        # At this point, the previous nodes should not be paged in, but the
900
887
        # 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)
 
888
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
889
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
890
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
904
891
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
905
892
        # Unmapping the new node will check the existing nodes to see if they
906
893
        # would fit.
907
894
        # Clear the page cache so we ensure we have to read all the children
908
 
        chk_map.clear_cache()
 
895
        chk_map._page_cache.clear()
909
896
        chkmap.unmap(('aad',))
910
897
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
911
898
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
938
925
        chkmap.map(('aad',), 'v')
939
926
        # At this point, the previous nodes should not be paged in, but the
940
927
        # 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)
 
928
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
929
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
930
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
944
931
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
945
932
        # Now clear the page cache, and only include 2 of the children in the
946
933
        # cache
947
934
        aab_key = chkmap._root_node._items['aab']
948
 
        aab_bytes = chk_map._get_cache()[aab_key]
 
935
        aab_bytes = chk_map._page_cache[aab_key]
949
936
        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
 
937
        aac_bytes = chk_map._page_cache[aac_key]
 
938
        chk_map._page_cache.clear()
 
939
        chk_map._page_cache[aab_key] = aab_bytes
 
940
        chk_map._page_cache[aac_key] = aac_bytes
954
941
 
955
942
        # Unmapping the new node will check the nodes from the page cache
956
943
        # first, and not have to read in 'aaa'
957
944
        chkmap.unmap(('aad',))
958
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
945
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
959
946
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
960
947
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
961
948
 
975
962
        chkmap.map(('aaf',), 'val')
976
963
        # At this point, the previous nodes should not be paged in, but the
977
964
        # 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)
 
965
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
966
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
967
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
981
968
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
982
969
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
983
970
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
985
972
        # Unmapping a new node will see the other nodes that are already in
986
973
        # memory, and not need to page in anything else
987
974
        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)
 
975
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
976
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
977
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
991
978
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
992
979
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
993
980
 
1032
1019
            {('a',): 'content here', ('b',): 'more content'},
1033
1020
            chk_bytes=basis._store, maximum_size=10)
1034
1021
        list(target.iter_changes(basis))
1035
 
        self.assertIsInstance(target._root_node, StaticTuple)
1036
 
        self.assertIsInstance(basis._root_node, StaticTuple)
 
1022
        self.assertIsInstance(target._root_node, tuple)
 
1023
        self.assertIsInstance(basis._root_node, tuple)
1037
1024
 
1038
1025
    def test_iter_changes_ab_ab_changed_values_shown(self):
1039
1026
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1145
1132
 
1146
1133
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1147
1134
        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', '')))
 
1135
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
 
1136
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
 
1137
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
1154
1138
        chkmap = self._get_map(
1155
1139
            {("a","a"):"content here", ("a", "b",):"more content",
1156
1140
             ("b", ""): 'boring content'},
1453
1437
                             , chkmap._dump_tree())
1454
1438
 
1455
1439
 
 
1440
class TestSearchKeyFuncs(tests.TestCase):
 
1441
 
 
1442
    def assertSearchKey16(self, expected, key):
 
1443
        self.assertEqual(expected, chk_map._search_key_16(key))
 
1444
 
 
1445
    def assertSearchKey255(self, expected, key):
 
1446
        actual = chk_map._search_key_255(key)
 
1447
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
 
1448
 
 
1449
    def test_simple_16(self):
 
1450
        self.assertSearchKey16('8C736521', ('foo',))
 
1451
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
 
1452
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
 
1453
        self.assertSearchKey16('ED82CD11', ('abcd',))
 
1454
 
 
1455
    def test_simple_255(self):
 
1456
        self.assertSearchKey255('\x8cse!', ('foo',))
 
1457
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
 
1458
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
 
1459
        # The standard mapping for these would include '\n', so it should be
 
1460
        # mapped to '_'
 
1461
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
 
1462
 
 
1463
    def test_255_does_not_include_newline(self):
 
1464
        # When mapping via _search_key_255, we should never have the '\n'
 
1465
        # character, but all other 255 values should be present
 
1466
        chars_used = set()
 
1467
        for char_in in range(256):
 
1468
            search_key = chk_map._search_key_255((chr(char_in),))
 
1469
            chars_used.update(search_key)
 
1470
        all_chars = set([chr(x) for x in range(256)])
 
1471
        unused_chars = all_chars.symmetric_difference(chars_used)
 
1472
        self.assertEqual(set('\n'), unused_chars)
 
1473
 
 
1474
 
1456
1475
class TestLeafNode(TestCaseWithStore):
1457
1476
 
1458
1477
    def test_current_size_empty(self):
1877
1896
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1878
1897
        node = InternalNode(search_key_func=search_key_func)
1879
1898
        leaf1 = LeafNode(search_key_func=search_key_func)
1880
 
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
 
1899
        leaf1.map(None, ('foo bar',), 'quux')
1881
1900
        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',)))
 
1901
        leaf2.map(None, ('strange',), 'beast')
 
1902
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
 
1903
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
1885
1904
        node.add_node("\xbe", leaf1)
1886
1905
        # This sets up a path that should not be followed - it will error if
1887
1906
        # the code tries to.
1888
1907
        node._items['\xbe'] = None
1889
1908
        node.add_node("\x85", leaf2)
1890
1909
        self.assertEqual([(('strange',), 'beast')],
1891
 
            sorted(node.iteritems(None, [StaticTuple('strange',),
1892
 
                                         StaticTuple('weird',)])))
 
1910
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1893
1911
 
1894
1912
    def test_iteritems_partial_empty(self):
1895
1913
        node = InternalNode()
1902
1920
        # Ensure test validity: nothing paged in below the root.
1903
1921
        self.assertEqual(2,
1904
1922
            len([value for value in node._items.values()
1905
 
                if type(value) is StaticTuple]))
 
1923
                if type(value) == tuple]))
1906
1924
        # now, mapping to k3 should add a k3 leaf
1907
1925
        prefix, nodes = node.map(None, ('k3',), 'quux')
1908
1926
        self.assertEqual("k", prefix)
1941
1959
        # Ensure test validity: nothing paged in below the root.
1942
1960
        self.assertEqual(2,
1943
1961
            len([value for value in node._items.values()
1944
 
                if type(value) is StaticTuple]))
 
1962
                if type(value) == tuple]))
1945
1963
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1946
1964
        # k23, which for simplicity in the current implementation generates
1947
1965
        # a new internal node between node, and k22/k23.
1986
2004
        node = InternalNode(search_key_func=search_key_func)
1987
2005
        node._key_width = 2
1988
2006
        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',)))
 
2007
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
 
2008
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
 
2009
        self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
1995
2010
 
1996
2011
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1997
2012
        chkmap = self._get_map(