← 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: INADA Naoki
  • Date: 2011-05-18 06:01:08 UTC
  • mto: This revision was merged to the branch mainline in revision 5894.
  • Revision ID: songofacandy@gmail.com-20110518060108-86t2kffcrzu0nf6i
Update Japanese docs.

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
16
16
 
17
17
"""Tests for maps built on a CHK versionedfiles facility."""
18
18
 
19
 
from itertools import izip
20
 
 
21
19
from bzrlib import (
22
20
    chk_map,
23
21
    errors,
31
29
    LeafNode,
32
30
    Node,
33
31
    )
 
32
from bzrlib.static_tuple import StaticTuple
34
33
 
35
34
 
36
35
class TestNode(tests.TestCase):
466
465
        # updated key.
467
466
        self.assertEqual(new_root, chkmap._root_node._key)
468
467
 
 
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
 
469
487
    def test_apply_new_keys_must_be_new(self):
470
488
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
471
489
        # an error.
831
849
        # 'ab' and 'ac' nodes
832
850
        chkmap.map(('aad',), 'v')
833
851
        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)
 
852
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
853
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
836
854
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
837
855
        # to map in 'ab'
838
856
        chkmap.unmap(('acd',))
839
857
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
840
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
858
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
841
859
 
842
860
    def test_unmap_without_fitting_doesnt_page_in(self):
843
861
        store = self.get_chk_bytes()
860
878
        chkmap.map(('aaf',), 'v')
861
879
        # At this point, the previous nodes should not be paged in, but the
862
880
        # newly added nodes would be
863
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
864
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
881
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
882
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
865
883
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
866
884
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
867
885
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
869
887
        # Now unmapping one of the new nodes will use only the already-paged-in
870
888
        # nodes to determine that we don't need to do more.
871
889
        chkmap.unmap(('aaf',))
872
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
873
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
890
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
891
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
874
892
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
875
893
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
876
894
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
897
915
        chkmap.map(('aad',), 'v')
898
916
        # At this point, the previous nodes should not be paged in, but the
899
917
        # 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)
 
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)
903
921
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
904
922
        # Unmapping the new node will check the existing nodes to see if they
905
923
        # would fit.
906
924
        # Clear the page cache so we ensure we have to read all the children
907
 
        chk_map._page_cache.clear()
 
925
        chk_map.clear_cache()
908
926
        chkmap.unmap(('aad',))
909
927
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
910
928
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
937
955
        chkmap.map(('aad',), 'v')
938
956
        # At this point, the previous nodes should not be paged in, but the
939
957
        # 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)
 
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)
943
961
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
944
962
        # Now clear the page cache, and only include 2 of the children in the
945
963
        # cache
946
964
        aab_key = chkmap._root_node._items['aab']
947
 
        aab_bytes = chk_map._page_cache[aab_key]
 
965
        aab_bytes = chk_map._get_cache()[aab_key]
948
966
        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
 
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
953
971
 
954
972
        # Unmapping the new node will check the nodes from the page cache
955
973
        # first, and not have to read in 'aaa'
956
974
        chkmap.unmap(('aad',))
957
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
975
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
958
976
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
959
977
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
960
978
 
974
992
        chkmap.map(('aaf',), 'val')
975
993
        # At this point, the previous nodes should not be paged in, but the
976
994
        # 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)
 
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)
980
998
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
981
999
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
982
1000
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
984
1002
        # Unmapping a new node will see the other nodes that are already in
985
1003
        # memory, and not need to page in anything else
986
1004
        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)
 
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)
990
1008
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
991
1009
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
992
1010
 
1031
1049
            {('a',): 'content here', ('b',): 'more content'},
1032
1050
            chk_bytes=basis._store, maximum_size=10)
1033
1051
        list(target.iter_changes(basis))
1034
 
        self.assertIsInstance(target._root_node, tuple)
1035
 
        self.assertIsInstance(basis._root_node, tuple)
 
1052
        self.assertIsInstance(target._root_node, StaticTuple)
 
1053
        self.assertIsInstance(basis._root_node, StaticTuple)
1036
1054
 
1037
1055
    def test_iter_changes_ab_ab_changed_values_shown(self):
1038
1056
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1144
1162
 
1145
1163
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1146
1164
        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', '')))
 
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', '')))
1150
1171
        chkmap = self._get_map(
1151
1172
            {("a","a"):"content here", ("a", "b",):"more content",
1152
1173
             ("b", ""): 'boring content'},
1449
1470
                             , chkmap._dump_tree())
1450
1471
 
1451
1472
 
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
1473
class TestLeafNode(TestCaseWithStore):
1488
1474
 
1489
1475
    def test_current_size_empty(self):
1908
1894
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1909
1895
        node = InternalNode(search_key_func=search_key_func)
1910
1896
        leaf1 = LeafNode(search_key_func=search_key_func)
1911
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1897
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1912
1898
        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',)))
 
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',)))
1916
1902
        node.add_node("\xbe", leaf1)
1917
1903
        # This sets up a path that should not be followed - it will error if
1918
1904
        # the code tries to.
1919
1905
        node._items['\xbe'] = None
1920
1906
        node.add_node("\x85", leaf2)
1921
1907
        self.assertEqual([(('strange',), 'beast')],
1922
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1908
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1909
                                         StaticTuple('weird',)])))
1923
1910
 
1924
1911
    def test_iteritems_partial_empty(self):
1925
1912
        node = InternalNode()
1932
1919
        # Ensure test validity: nothing paged in below the root.
1933
1920
        self.assertEqual(2,
1934
1921
            len([value for value in node._items.values()
1935
 
                if type(value) == tuple]))
 
1922
                if type(value) is StaticTuple]))
1936
1923
        # now, mapping to k3 should add a k3 leaf
1937
1924
        prefix, nodes = node.map(None, ('k3',), 'quux')
1938
1925
        self.assertEqual("k", prefix)
1971
1958
        # Ensure test validity: nothing paged in below the root.
1972
1959
        self.assertEqual(2,
1973
1960
            len([value for value in node._items.values()
1974
 
                if type(value) == tuple]))
 
1961
                if type(value) is StaticTuple]))
1975
1962
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1976
1963
        # k23, which for simplicity in the current implementation generates
1977
1964
        # a new internal node between node, and k22/k23.
2016
2003
        node = InternalNode(search_key_func=search_key_func)
2017
2004
        node._key_width = 2
2018
2005
        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',)))
 
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',)))
2022
2012
 
2023
2013
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2024
2014
        chkmap = self._get_map(