← 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: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

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