← 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: Andrew Bennetts
  • Date: 2009-09-15 03:00:23 UTC
  • mto: This revision was merged to the branch mainline in revision 4702.
  • Revision ID: andrew.bennetts@canonical.com-20090915030023-36kgbugmn9xv140m
Refactor bzr_serve more so that it is possible to use a function other than os.path.expanduser for the userdir expansion.

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
16
16
 
17
17
"""Tests for maps built on a CHK versionedfiles facility."""
18
18
 
 
19
from itertools import izip
 
20
 
19
21
from bzrlib import (
20
22
    chk_map,
21
23
    errors,
29
31
    LeafNode,
30
32
    Node,
31
33
    )
32
 
from bzrlib.static_tuple import StaticTuple
33
34
 
34
35
 
35
36
class TestNode(tests.TestCase):
224
225
            "      ('ddd',) 'initial ddd content'\n",
225
226
            c_map._dump_tree())
226
227
 
227
 
    def test_root_only_aaa_ddd_16(self):
 
228
    def test_one_deep_map_16(self):
228
229
        c_map = self.make_root_only_aaa_ddd_map(
229
230
                search_key_func=chk_map._search_key_16)
230
231
        # We use 'aaa' and 'ddd' because they happen to map to 'F' when using
465
466
        # updated key.
466
467
        self.assertEqual(new_root, chkmap._root_node._key)
467
468
 
468
 
    def test_apply_delete_to_internal_node(self):
469
 
        # applying a delta should be convert an internal root node to a leaf
470
 
        # node if the delta shrinks the map enough.
471
 
        store = self.get_chk_bytes()
472
 
        chkmap = CHKMap(store, None)
473
 
        # Add three items: 2 small enough to fit in one node, and one huge to
474
 
        # force multiple nodes.
475
 
        chkmap._root_node.set_maximum_size(100)
476
 
        chkmap.map(('small',), 'value')
477
 
        chkmap.map(('little',), 'value')
478
 
        chkmap.map(('very-big',), 'x' * 100)
479
 
        # (Check that we have constructed the scenario we want to test)
480
 
        self.assertIsInstance(chkmap._root_node, InternalNode)
481
 
        # Delete the huge item so that the map fits in one node again.
482
 
        delta = [(('very-big',), None, None)]
483
 
        chkmap.apply_delta(delta)
484
 
        self.assertCanonicalForm(chkmap)
485
 
        self.assertIsInstance(chkmap._root_node, LeafNode)
486
 
 
487
469
    def test_apply_new_keys_must_be_new(self):
488
470
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
489
471
        # an error.
849
831
        # 'ab' and 'ac' nodes
850
832
        chkmap.map(('aad',), 'v')
851
833
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
852
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
853
 
        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)
854
836
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
855
837
        # to map in 'ab'
856
838
        chkmap.unmap(('acd',))
857
839
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
858
 
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
840
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
859
841
 
860
842
    def test_unmap_without_fitting_doesnt_page_in(self):
861
843
        store = self.get_chk_bytes()
878
860
        chkmap.map(('aaf',), 'v')
879
861
        # At this point, the previous nodes should not be paged in, but the
880
862
        # newly added nodes would be
881
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
882
 
        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)
883
865
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
884
866
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
885
867
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
887
869
        # Now unmapping one of the new nodes will use only the already-paged-in
888
870
        # nodes to determine that we don't need to do more.
889
871
        chkmap.unmap(('aaf',))
890
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
891
 
        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)
892
874
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
893
875
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
894
876
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
915
897
        chkmap.map(('aad',), 'v')
916
898
        # At this point, the previous nodes should not be paged in, but the
917
899
        # newly added node would be
918
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
919
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
920
 
        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)
921
903
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
922
904
        # Unmapping the new node will check the existing nodes to see if they
923
905
        # would fit.
924
906
        # Clear the page cache so we ensure we have to read all the children
925
 
        chk_map.clear_cache()
 
907
        chk_map._page_cache.clear()
926
908
        chkmap.unmap(('aad',))
927
909
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
928
910
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
955
937
        chkmap.map(('aad',), 'v')
956
938
        # At this point, the previous nodes should not be paged in, but the
957
939
        # newly added node would be
958
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
959
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
960
 
        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)
961
943
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
962
944
        # Now clear the page cache, and only include 2 of the children in the
963
945
        # cache
964
946
        aab_key = chkmap._root_node._items['aab']
965
 
        aab_bytes = chk_map._get_cache()[aab_key]
 
947
        aab_bytes = chk_map._page_cache[aab_key]
966
948
        aac_key = chkmap._root_node._items['aac']
967
 
        aac_bytes = chk_map._get_cache()[aac_key]
968
 
        chk_map.clear_cache()
969
 
        chk_map._get_cache()[aab_key] = aab_bytes
970
 
        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
971
953
 
972
954
        # Unmapping the new node will check the nodes from the page cache
973
955
        # first, and not have to read in 'aaa'
974
956
        chkmap.unmap(('aad',))
975
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
957
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
976
958
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
977
959
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
978
960
 
992
974
        chkmap.map(('aaf',), 'val')
993
975
        # At this point, the previous nodes should not be paged in, but the
994
976
        # newly added node would be
995
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
996
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
997
 
        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)
998
980
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
999
981
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1000
982
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1002
984
        # Unmapping a new node will see the other nodes that are already in
1003
985
        # memory, and not need to page in anything else
1004
986
        chkmap.unmap(('aad',))
1005
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1006
 
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1007
 
        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)
1008
990
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1009
991
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1010
992
 
1049
1031
            {('a',): 'content here', ('b',): 'more content'},
1050
1032
            chk_bytes=basis._store, maximum_size=10)
1051
1033
        list(target.iter_changes(basis))
1052
 
        self.assertIsInstance(target._root_node, StaticTuple)
1053
 
        self.assertIsInstance(basis._root_node, StaticTuple)
 
1034
        self.assertIsInstance(target._root_node, tuple)
 
1035
        self.assertIsInstance(basis._root_node, tuple)
1054
1036
 
1055
1037
    def test_iter_changes_ab_ab_changed_values_shown(self):
1056
1038
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1108
1090
        basis_get = basis._store.get_record_stream
1109
1091
        def get_record_stream(keys, order, fulltext):
1110
1092
            if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
1111
 
                raise AssertionError("'aaa' pointer was followed %r" % keys)
 
1093
                self.fail("'aaa' pointer was followed %r" % keys)
1112
1094
            return basis_get(keys, order, fulltext)
1113
1095
        basis._store.get_record_stream = get_record_stream
1114
1096
        result = sorted(list(target.iter_changes(basis)))
1162
1144
 
1163
1145
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1164
1146
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1165
 
        self.assertEqual('E8B7BE43\x00E8B7BE43',
1166
 
                         search_key_func(StaticTuple('a', 'a')))
1167
 
        self.assertEqual('E8B7BE43\x0071BEEFF9',
1168
 
                         search_key_func(StaticTuple('a', 'b')))
1169
 
        self.assertEqual('71BEEFF9\x0000000000',
1170
 
                         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', '')))
1171
1150
        chkmap = self._get_map(
1172
1151
            {("a","a"):"content here", ("a", "b",):"more content",
1173
1152
             ("b", ""): 'boring content'},
1470
1449
                             , chkmap._dump_tree())
1471
1450
 
1472
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
 
1473
1487
class TestLeafNode(TestCaseWithStore):
1474
1488
 
1475
1489
    def test_current_size_empty(self):
1894
1908
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1895
1909
        node = InternalNode(search_key_func=search_key_func)
1896
1910
        leaf1 = LeafNode(search_key_func=search_key_func)
1897
 
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
 
1911
        leaf1.map(None, ('foo bar',), 'quux')
1898
1912
        leaf2 = LeafNode(search_key_func=search_key_func)
1899
 
        leaf2.map(None, StaticTuple('strange',), 'beast')
1900
 
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
1901
 
        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',)))
1902
1916
        node.add_node("\xbe", leaf1)
1903
1917
        # This sets up a path that should not be followed - it will error if
1904
1918
        # the code tries to.
1905
1919
        node._items['\xbe'] = None
1906
1920
        node.add_node("\x85", leaf2)
1907
1921
        self.assertEqual([(('strange',), 'beast')],
1908
 
            sorted(node.iteritems(None, [StaticTuple('strange',),
1909
 
                                         StaticTuple('weird',)])))
 
1922
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1910
1923
 
1911
1924
    def test_iteritems_partial_empty(self):
1912
1925
        node = InternalNode()
1919
1932
        # Ensure test validity: nothing paged in below the root.
1920
1933
        self.assertEqual(2,
1921
1934
            len([value for value in node._items.values()
1922
 
                if type(value) is StaticTuple]))
 
1935
                if type(value) == tuple]))
1923
1936
        # now, mapping to k3 should add a k3 leaf
1924
1937
        prefix, nodes = node.map(None, ('k3',), 'quux')
1925
1938
        self.assertEqual("k", prefix)
1958
1971
        # Ensure test validity: nothing paged in below the root.
1959
1972
        self.assertEqual(2,
1960
1973
            len([value for value in node._items.values()
1961
 
                if type(value) is StaticTuple]))
 
1974
                if type(value) == tuple]))
1962
1975
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1963
1976
        # k23, which for simplicity in the current implementation generates
1964
1977
        # a new internal node between node, and k22/k23.
2003
2016
        node = InternalNode(search_key_func=search_key_func)
2004
2017
        node._key_width = 2
2005
2018
        node._node_width = 4
2006
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
2007
 
            StaticTuple('a', 'b')))
2008
 
        self.assertEqual('E8B7', node._search_prefix_filter(
2009
 
            StaticTuple('a', 'b')))
2010
 
        self.assertEqual('E8B7', node._search_prefix_filter(
2011
 
            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',)))
2012
2022
 
2013
2023
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2014
2024
        chkmap = self._get_map(