← 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-08-15 09:15:03 UTC
  • mfrom: (4595.7.4 409137-lsb-release)
  • Revision ID: pqm@pqm.ubuntu.com-20090815091503-qwbm6glvv31rnujw
(mbp) show platform in selftest, version and backtrace

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):
467
466
        # updated key.
468
467
        self.assertEqual(new_root, chkmap._root_node._key)
469
468
 
470
 
    def test_apply_delete_to_internal_node(self):
471
 
        # applying a delta should be convert an internal root node to a leaf
472
 
        # node if the delta shrinks the map enough.
473
 
        store = self.get_chk_bytes()
474
 
        chkmap = CHKMap(store, None)
475
 
        # Add three items: 2 small enough to fit in one node, and one huge to
476
 
        # force multiple nodes.
477
 
        chkmap._root_node.set_maximum_size(100)
478
 
        chkmap.map(('small',), 'value')
479
 
        chkmap.map(('little',), 'value')
480
 
        chkmap.map(('very-big',), 'x' * 100)
481
 
        # (Check that we have constructed the scenario we want to test)
482
 
        self.assertIsInstance(chkmap._root_node, InternalNode)
483
 
        # Delete the huge item so that the map fits in one node again.
484
 
        delta = [(('very-big',), None, None)]
485
 
        chkmap.apply_delta(delta)
486
 
        self.assertCanonicalForm(chkmap)
487
 
        self.assertIsInstance(chkmap._root_node, LeafNode)
488
 
 
489
469
    def test_apply_new_keys_must_be_new(self):
490
470
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
491
471
        # an error.
851
831
        # 'ab' and 'ac' nodes
852
832
        chkmap.map(('aad',), 'v')
853
833
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
854
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
855
 
        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)
856
836
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
857
837
        # to map in 'ab'
858
838
        chkmap.unmap(('acd',))
859
839
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
860
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
840
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
861
841
 
862
842
    def test_unmap_without_fitting_doesnt_page_in(self):
863
843
        store = self.get_chk_bytes()
880
860
        chkmap.map(('aaf',), 'v')
881
861
        # At this point, the previous nodes should not be paged in, but the
882
862
        # newly added nodes would be
883
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
884
 
        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)
885
865
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
886
866
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
887
867
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
889
869
        # Now unmapping one of the new nodes will use only the already-paged-in
890
870
        # nodes to determine that we don't need to do more.
891
871
        chkmap.unmap(('aaf',))
892
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
893
 
        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)
894
874
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
895
875
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
896
876
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
917
897
        chkmap.map(('aad',), 'v')
918
898
        # At this point, the previous nodes should not be paged in, but the
919
899
        # newly added node would be
920
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
921
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
922
 
        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)
923
903
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
924
904
        # Unmapping the new node will check the existing nodes to see if they
925
905
        # would fit.
926
906
        # Clear the page cache so we ensure we have to read all the children
927
 
        chk_map.clear_cache()
 
907
        chk_map._page_cache.clear()
928
908
        chkmap.unmap(('aad',))
929
909
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
930
910
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
957
937
        chkmap.map(('aad',), 'v')
958
938
        # At this point, the previous nodes should not be paged in, but the
959
939
        # newly added node would be
960
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
961
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
962
 
        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)
963
943
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
964
944
        # Now clear the page cache, and only include 2 of the children in the
965
945
        # cache
966
946
        aab_key = chkmap._root_node._items['aab']
967
 
        aab_bytes = chk_map._get_cache()[aab_key]
 
947
        aab_bytes = chk_map._page_cache[aab_key]
968
948
        aac_key = chkmap._root_node._items['aac']
969
 
        aac_bytes = chk_map._get_cache()[aac_key]
970
 
        chk_map.clear_cache()
971
 
        chk_map._get_cache()[aab_key] = aab_bytes
972
 
        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
973
953
 
974
954
        # Unmapping the new node will check the nodes from the page cache
975
955
        # first, and not have to read in 'aaa'
976
956
        chkmap.unmap(('aad',))
977
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
957
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
978
958
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
979
959
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
980
960
 
994
974
        chkmap.map(('aaf',), 'val')
995
975
        # At this point, the previous nodes should not be paged in, but the
996
976
        # newly added node would be
997
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
998
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
999
 
        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)
1000
980
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1001
981
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1002
982
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1004
984
        # Unmapping a new node will see the other nodes that are already in
1005
985
        # memory, and not need to page in anything else
1006
986
        chkmap.unmap(('aad',))
1007
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1008
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1009
 
        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)
1010
990
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1011
991
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1012
992
 
1051
1031
            {('a',): 'content here', ('b',): 'more content'},
1052
1032
            chk_bytes=basis._store, maximum_size=10)
1053
1033
        list(target.iter_changes(basis))
1054
 
        self.assertIsInstance(target._root_node, StaticTuple)
1055
 
        self.assertIsInstance(basis._root_node, StaticTuple)
 
1034
        self.assertIsInstance(target._root_node, tuple)
 
1035
        self.assertIsInstance(basis._root_node, tuple)
1056
1036
 
1057
1037
    def test_iter_changes_ab_ab_changed_values_shown(self):
1058
1038
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1164
1144
 
1165
1145
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1166
1146
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1167
 
        self.assertEqual('E8B7BE43\x00E8B7BE43',
1168
 
                         search_key_func(StaticTuple('a', 'a')))
1169
 
        self.assertEqual('E8B7BE43\x0071BEEFF9',
1170
 
                         search_key_func(StaticTuple('a', 'b')))
1171
 
        self.assertEqual('71BEEFF9\x0000000000',
1172
 
                         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', '')))
1173
1150
        chkmap = self._get_map(
1174
1151
            {("a","a"):"content here", ("a", "b",):"more content",
1175
1152
             ("b", ""): 'boring content'},
1472
1449
                             , chkmap._dump_tree())
1473
1450
 
1474
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
 
1475
1487
class TestLeafNode(TestCaseWithStore):
1476
1488
 
1477
1489
    def test_current_size_empty(self):
1896
1908
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1897
1909
        node = InternalNode(search_key_func=search_key_func)
1898
1910
        leaf1 = LeafNode(search_key_func=search_key_func)
1899
 
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
 
1911
        leaf1.map(None, ('foo bar',), 'quux')
1900
1912
        leaf2 = LeafNode(search_key_func=search_key_func)
1901
 
        leaf2.map(None, StaticTuple('strange',), 'beast')
1902
 
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
1903
 
        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',)))
1904
1916
        node.add_node("\xbe", leaf1)
1905
1917
        # This sets up a path that should not be followed - it will error if
1906
1918
        # the code tries to.
1907
1919
        node._items['\xbe'] = None
1908
1920
        node.add_node("\x85", leaf2)
1909
1921
        self.assertEqual([(('strange',), 'beast')],
1910
 
            sorted(node.iteritems(None, [StaticTuple('strange',),
1911
 
                                         StaticTuple('weird',)])))
 
1922
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1912
1923
 
1913
1924
    def test_iteritems_partial_empty(self):
1914
1925
        node = InternalNode()
1921
1932
        # Ensure test validity: nothing paged in below the root.
1922
1933
        self.assertEqual(2,
1923
1934
            len([value for value in node._items.values()
1924
 
                if type(value) is StaticTuple]))
 
1935
                if type(value) == tuple]))
1925
1936
        # now, mapping to k3 should add a k3 leaf
1926
1937
        prefix, nodes = node.map(None, ('k3',), 'quux')
1927
1938
        self.assertEqual("k", prefix)
1960
1971
        # Ensure test validity: nothing paged in below the root.
1961
1972
        self.assertEqual(2,
1962
1973
            len([value for value in node._items.values()
1963
 
                if type(value) is StaticTuple]))
 
1974
                if type(value) == tuple]))
1964
1975
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1965
1976
        # k23, which for simplicity in the current implementation generates
1966
1977
        # a new internal node between node, and k22/k23.
2005
2016
        node = InternalNode(search_key_func=search_key_func)
2006
2017
        node._key_width = 2
2007
2018
        node._node_width = 4
2008
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
2009
 
            StaticTuple('a', 'b')))
2010
 
        self.assertEqual('E8B7', node._search_prefix_filter(
2011
 
            StaticTuple('a', 'b')))
2012
 
        self.assertEqual('E8B7', node._search_prefix_filter(
2013
 
            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',)))
2014
2022
 
2015
2023
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2016
2024
        chkmap = self._get_map(