42
42
self.assertTrue(len(common) <= len(key))
43
43
self.assertStartsWith(prefix, common)
44
44
self.assertStartsWith(key, common)
45
self.assertEquals(expected_common, common)
45
self.assertEqual(expected_common, common)
47
47
def test_common_prefix(self):
48
self.assertCommonPrefix('beg', 'beg', 'begin')
48
self.assertCommonPrefix(b'beg', b'beg', b'begin')
50
50
def test_no_common_prefix(self):
51
self.assertCommonPrefix('', 'begin', 'end')
51
self.assertCommonPrefix(b'', b'begin', b'end')
53
53
def test_equal(self):
54
self.assertCommonPrefix('begin', 'begin', 'begin')
54
self.assertCommonPrefix(b'begin', b'begin', b'begin')
56
56
def test_not_a_prefix(self):
57
self.assertCommonPrefix('b', 'begin', 'b')
57
self.assertCommonPrefix(b'b', b'begin', b'b')
59
59
def test_empty(self):
60
self.assertCommonPrefix('', '', 'end')
61
self.assertCommonPrefix('', 'begin', '')
62
self.assertCommonPrefix('', '', '')
60
self.assertCommonPrefix(b'', b'', b'end')
61
self.assertCommonPrefix(b'', b'begin', b'')
62
self.assertCommonPrefix(b'', b'', b'')
65
65
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
113
113
def make_root_only_map(self, search_key_func=None):
114
114
return self.get_map({
115
('aaa',): 'initial aaa content',
116
('abb',): 'initial abb content',
115
(b'aaa',): b'initial aaa content',
116
(b'abb',): b'initial abb content',
117
117
}, search_key_func=search_key_func)
119
119
def make_root_only_aaa_ddd_map(self, search_key_func=None):
120
120
return self.get_map({
121
('aaa',): 'initial aaa content',
122
('ddd',): 'initial ddd content',
121
(b'aaa',): b'initial aaa content',
122
(b'ddd',): b'initial ddd content',
123
123
}, search_key_func=search_key_func)
125
125
def make_one_deep_map(self, search_key_func=None):
126
126
# Same as root_only_map, except it forces an InternalNode at the root
127
127
return self.get_map({
128
('aaa',): 'initial aaa content',
129
('abb',): 'initial abb content',
130
('ccc',): 'initial ccc content',
131
('ddd',): 'initial ddd content',
128
(b'aaa',): b'initial aaa content',
129
(b'abb',): b'initial abb content',
130
(b'ccc',): b'initial ccc content',
131
(b'ddd',): b'initial ddd content',
132
132
}, search_key_func=search_key_func)
134
134
def make_two_deep_map(self, search_key_func=None):
136
136
# _search_key_plain and for _search_key_16
137
137
# Also so that things line up with make_one_deep_two_prefix_map
138
138
return self.get_map({
139
('aaa',): 'initial aaa content',
140
('abb',): 'initial abb content',
141
('acc',): 'initial acc content',
142
('ace',): 'initial ace content',
143
('add',): 'initial add content',
144
('adh',): 'initial adh content',
145
('adl',): 'initial adl content',
146
('ccc',): 'initial ccc content',
147
('ddd',): 'initial ddd content',
139
(b'aaa',): b'initial aaa content',
140
(b'abb',): b'initial abb content',
141
(b'acc',): b'initial acc content',
142
(b'ace',): b'initial ace content',
143
(b'add',): b'initial add content',
144
(b'adh',): b'initial adh content',
145
(b'adl',): b'initial adl content',
146
(b'ccc',): b'initial ccc content',
147
(b'ddd',): b'initial ddd content',
148
148
}, search_key_func=search_key_func)
150
150
def make_one_deep_two_prefix_map(self, search_key_func=None):
407
407
map_two = CHKMap(store, None)
408
408
map_two._root_node.set_maximum_size(20)
409
409
self.assertMapLayoutEqual(map_one, map_two)
410
map_one.map('aaa', 'value')
410
map_one.map(b'aaa', b'value')
411
411
self.assertRaises(AssertionError,
412
412
self.assertMapLayoutEqual, map_one, map_two)
413
map_two.map('aaa', 'value')
413
map_two.map(b'aaa', b'value')
414
414
self.assertMapLayoutEqual(map_one, map_two)
415
415
# Split the tree, so we ensure that internal nodes and leaf nodes are
416
416
# properly checked
417
map_one.map('aab', 'value')
417
map_one.map(b'aab', b'value')
418
418
self.assertIsInstance(map_one._root_node, InternalNode)
419
419
self.assertRaises(AssertionError,
420
420
self.assertMapLayoutEqual, map_one, map_two)
421
map_two.map('aab', 'value')
421
map_two.map(b'aab', b'value')
422
422
self.assertMapLayoutEqual(map_one, map_two)
423
map_one.map('aac', 'value')
423
map_one.map(b'aac', b'value')
424
424
self.assertRaises(AssertionError,
425
425
self.assertMapLayoutEqual, map_one, map_two)
426
426
self.assertCanonicalForm(map_one)
468
468
self.assertEqual(new_root, chkmap._root_node._key)
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((b'small',), b'value')
479
chkmap.map((b'little',), b'value')
480
chkmap.map((b'very-big',), b'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 = [((b'very-big',), None, None)]
485
chkmap.apply_delta(delta)
486
self.assertCanonicalForm(chkmap)
487
self.assertIsInstance(chkmap._root_node, LeafNode)
470
489
def test_apply_new_keys_must_be_new(self):
471
490
# applying a delta (None, "a", "b") to a map with 'a' in it generates
473
492
chk_bytes = self.get_chk_bytes()
474
root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
493
root_key = CHKMap.from_dict(chk_bytes, {(b"a",):b"b"})
475
494
chkmap = CHKMap(chk_bytes, root_key)
476
495
self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
477
[(None, ("a",), "b")])
496
[(None, (b"a",), b"b")])
478
497
# As an error occured, the update should have left us without changing
479
498
# anything (the root should be unchanged).
480
499
self.assertEqual(root_key, chkmap._root_node._key)
483
502
chk_bytes = self.get_chk_bytes()
484
503
chkmap1 = CHKMap(chk_bytes, None)
485
504
chkmap1._root_node.set_maximum_size(10)
486
chkmap1.apply_delta([(None, ('aaa',), 'common'),
487
(None, ('bba',), 'target2'),
488
(None, ('bbb',), 'common')])
505
chkmap1.apply_delta([(None, (b'aaa',), b'common'),
506
(None, (b'bba',), b'target2'),
507
(None, (b'bbb',), b'common')])
489
508
root_key1 = chkmap1._save()
490
509
self.assertCanonicalForm(chkmap1)
492
511
chkmap2 = CHKMap(chk_bytes, None)
493
512
chkmap2._root_node.set_maximum_size(10)
494
chkmap2.apply_delta([(None, ('bbb',), 'common'),
495
(None, ('bba',), 'target2'),
496
(None, ('aaa',), 'common')])
513
chkmap2.apply_delta([(None, (b'bbb',), b'common'),
514
(None, (b'bba',), b'target2'),
515
(None, (b'aaa',), b'common')])
497
516
root_key2 = chkmap2._save()
498
517
self.assertEqualDiff(chkmap1._dump_tree(include_keys=True),
499
518
chkmap2._dump_tree(include_keys=True))
830
849
chkmap = CHKMap(store, chkmap._save())
831
850
# Mapping an 'aa' key loads the internal node, but should not map the
832
851
# 'ab' and 'ac' nodes
833
chkmap.map(('aad',), 'v')
834
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)
852
chkmap.map((b'aad',), b'v')
853
self.assertIsInstance(chkmap._root_node._items[b'aa'], InternalNode)
854
self.assertIsInstance(chkmap._root_node._items[b'ab'], StaticTuple)
855
self.assertIsInstance(chkmap._root_node._items[b'ac'], StaticTuple)
837
856
# Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
839
chkmap.unmap(('acd',))
840
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
841
self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
858
chkmap.unmap((b'acd',))
859
self.assertIsInstance(chkmap._root_node._items[b'aa'], InternalNode)
860
self.assertIsInstance(chkmap._root_node._items[b'ab'], StaticTuple)
843
862
def test_unmap_without_fitting_doesnt_page_in(self):
844
863
store = self.get_chk_bytes()
845
864
chkmap = CHKMap(store, None)
846
865
# Should fit 2 keys per LeafNode
847
866
chkmap._root_node.set_maximum_size(20)
848
chkmap.map(('aaa',), 'v')
849
chkmap.map(('aab',), 'v')
867
chkmap.map((b'aaa',), b'v')
868
chkmap.map((b'aab',), b'v')
850
869
self.assertEqualDiff("'' InternalNode\n"
851
870
" 'aaa' LeafNode\n"
852
871
" ('aaa',) 'v'\n"
855
874
chkmap._dump_tree())
856
875
# Save everything to the map, and start over
857
876
chkmap = CHKMap(store, chkmap._save())
858
chkmap.map(('aac',), 'v')
859
chkmap.map(('aad',), 'v')
860
chkmap.map(('aae',), 'v')
861
chkmap.map(('aaf',), 'v')
877
chkmap.map((b'aac',), b'v')
878
chkmap.map((b'aad',), b'v')
879
chkmap.map((b'aae',), b'v')
880
chkmap.map((b'aaf',), b'v')
862
881
# At this point, the previous nodes should not be paged in, but the
863
882
# newly added nodes would be
864
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
865
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
866
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
867
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
868
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
869
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
883
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
884
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
885
self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
886
self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
887
self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
888
self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
870
889
# Now unmapping one of the new nodes will use only the already-paged-in
871
890
# nodes to determine that we don't need to do more.
872
chkmap.unmap(('aaf',))
873
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
874
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
875
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
876
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
877
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
891
chkmap.unmap((b'aaf',))
892
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
893
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
894
self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
895
self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
896
self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
879
898
def test_unmap_pages_in_if_necessary(self):
880
899
store = self.get_chk_bytes()
881
900
chkmap = CHKMap(store, None)
882
901
# Should fit 2 keys per LeafNode
883
902
chkmap._root_node.set_maximum_size(30)
884
chkmap.map(('aaa',), 'val')
885
chkmap.map(('aab',), 'val')
886
chkmap.map(('aac',), 'val')
903
chkmap.map((b'aaa',), b'val')
904
chkmap.map((b'aab',), b'val')
905
chkmap.map((b'aac',), b'val')
887
906
self.assertEqualDiff("'' InternalNode\n"
888
907
" 'aaa' LeafNode\n"
889
908
" ('aaa',) 'val'\n"
895
914
root_key = chkmap._save()
896
915
# Save everything to the map, and start over
897
916
chkmap = CHKMap(store, root_key)
898
chkmap.map(('aad',), 'v')
917
chkmap.map((b'aad',), b'v')
899
918
# At this point, the previous nodes should not be paged in, but the
900
919
# 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)
904
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
920
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
921
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
922
self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
923
self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
905
924
# Unmapping the new node will check the existing nodes to see if they
907
926
# Clear the page cache so we ensure we have to read all the children
908
927
chk_map.clear_cache()
909
chkmap.unmap(('aad',))
910
self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
911
self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
912
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
928
chkmap.unmap((b'aad',))
929
self.assertIsInstance(chkmap._root_node._items[b'aaa'], LeafNode)
930
self.assertIsInstance(chkmap._root_node._items[b'aab'], LeafNode)
931
self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
914
933
def test_unmap_pages_in_from_page_cache(self):
915
934
store = self.get_chk_bytes()
916
935
chkmap = CHKMap(store, None)
917
936
# Should fit 2 keys per LeafNode
918
937
chkmap._root_node.set_maximum_size(30)
919
chkmap.map(('aaa',), 'val')
920
chkmap.map(('aab',), 'val')
921
chkmap.map(('aac',), 'val')
938
chkmap.map((b'aaa',), b'val')
939
chkmap.map((b'aab',), b'val')
940
chkmap.map((b'aac',), b'val')
922
941
root_key = chkmap._save()
923
942
# Save everything to the map, and start over
924
943
chkmap = CHKMap(store, root_key)
925
chkmap.map(('aad',), 'val')
944
chkmap.map((b'aad',), b'val')
926
945
self.assertEqualDiff("'' InternalNode\n"
927
946
" 'aaa' LeafNode\n"
928
947
" ('aaa',) 'val'\n"
935
954
chkmap._dump_tree())
936
955
# Save everything to the map, start over after _dump_tree
937
956
chkmap = CHKMap(store, root_key)
938
chkmap.map(('aad',), 'v')
957
chkmap.map((b'aad',), b'v')
939
958
# At this point, the previous nodes should not be paged in, but the
940
959
# 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)
944
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
960
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
961
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
962
self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
963
self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
945
964
# Now clear the page cache, and only include 2 of the children in the
947
aab_key = chkmap._root_node._items['aab']
966
aab_key = chkmap._root_node._items[b'aab']
948
967
aab_bytes = chk_map._get_cache()[aab_key]
949
aac_key = chkmap._root_node._items['aac']
968
aac_key = chkmap._root_node._items[b'aac']
950
969
aac_bytes = chk_map._get_cache()[aac_key]
951
970
chk_map.clear_cache()
952
971
chk_map._get_cache()[aab_key] = aab_bytes
955
974
# Unmapping the new node will check the nodes from the page cache
956
975
# first, and not have to read in 'aaa'
957
chkmap.unmap(('aad',))
958
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
959
self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
960
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
976
chkmap.unmap((b'aad',))
977
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
978
self.assertIsInstance(chkmap._root_node._items[b'aab'], LeafNode)
979
self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
962
981
def test_unmap_uses_existing_items(self):
963
982
store = self.get_chk_bytes()
964
983
chkmap = CHKMap(store, None)
965
984
# Should fit 2 keys per LeafNode
966
985
chkmap._root_node.set_maximum_size(30)
967
chkmap.map(('aaa',), 'val')
968
chkmap.map(('aab',), 'val')
969
chkmap.map(('aac',), 'val')
986
chkmap.map((b'aaa',), b'val')
987
chkmap.map((b'aab',), b'val')
988
chkmap.map((b'aac',), b'val')
970
989
root_key = chkmap._save()
971
990
# Save everything to the map, and start over
972
991
chkmap = CHKMap(store, root_key)
973
chkmap.map(('aad',), 'val')
974
chkmap.map(('aae',), 'val')
975
chkmap.map(('aaf',), 'val')
992
chkmap.map((b'aad',), b'val')
993
chkmap.map((b'aae',), b'val')
994
chkmap.map((b'aaf',), b'val')
976
995
# At this point, the previous nodes should not be paged in, but the
977
996
# 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)
981
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
982
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
983
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
997
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
998
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
999
self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
1000
self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
1001
self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
1002
self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
985
1004
# Unmapping a new node will see the other nodes that are already in
986
1005
# memory, and not need to page in anything else
987
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)
991
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
992
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1006
chkmap.unmap((b'aad',))
1007
self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
1008
self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
1009
self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
1010
self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
1011
self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
994
1013
def test_iter_changes_empty_ab(self):
995
1014
# Asking for changes between an empty dict to a dict with keys returns
997
1016
basis = self._get_map({}, maximum_size=10)
998
1017
target = self._get_map(
999
{('a',): 'content here', ('b',): 'more content'},
1018
{(b'a',): b'content here', (b'b',): b'more content'},
1000
1019
chk_bytes=basis._store, maximum_size=10)
1001
self.assertEqual([(('a',), None, 'content here'),
1002
(('b',), None, 'more content')],
1020
self.assertEqual([((b'a',), None, b'content here'),
1021
((b'b',), None, b'more content')],
1003
1022
sorted(list(target.iter_changes(basis))))
1005
1024
def test_iter_changes_ab_empty(self):
1006
1025
# Asking for changes between a dict with keys to an empty dict returns
1007
1026
# all the keys.
1008
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1027
basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1009
1028
maximum_size=10)
1010
1029
target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)
1011
self.assertEqual([(('a',), 'content here', None),
1012
(('b',), 'more content', None)],
1030
self.assertEqual([((b'a',), b'content here', None),
1031
((b'b',), b'more content', None)],
1013
1032
sorted(list(target.iter_changes(basis))))
1015
1034
def test_iter_changes_empty_empty_is_empty(self):
1018
1037
self.assertEqual([], sorted(list(target.iter_changes(basis))))
1020
1039
def test_iter_changes_ab_ab_is_empty(self):
1021
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1040
basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1022
1041
maximum_size=10)
1023
1042
target = self._get_map(
1024
{('a',): 'content here', ('b',): 'more content'},
1043
{(b'a',): b'content here', (b'b',): b'more content'},
1025
1044
chk_bytes=basis._store, maximum_size=10)
1026
1045
self.assertEqual([], sorted(list(target.iter_changes(basis))))
1028
1047
def test_iter_changes_ab_ab_nodes_not_loaded(self):
1029
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1048
basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1030
1049
maximum_size=10)
1031
1050
target = self._get_map(
1032
{('a',): 'content here', ('b',): 'more content'},
1051
{(b'a',): b'content here', (b'b',): b'more content'},
1033
1052
chk_bytes=basis._store, maximum_size=10)
1034
1053
list(target.iter_changes(basis))
1035
1054
self.assertIsInstance(target._root_node, StaticTuple)
1036
1055
self.assertIsInstance(basis._root_node, StaticTuple)
1038
1057
def test_iter_changes_ab_ab_changed_values_shown(self):
1039
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1058
basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1040
1059
maximum_size=10)
1041
1060
target = self._get_map(
1042
{('a',): 'content here', ('b',): 'different content'},
1061
{(b'a',): b'content here', (b'b',): b'different content'},
1043
1062
chk_bytes=basis._store, maximum_size=10)
1044
1063
result = sorted(list(target.iter_changes(basis)))
1045
self.assertEqual([(('b',), 'more content', 'different content')],
1064
self.assertEqual([((b'b',), b'more content', b'different content')],
1048
1067
def test_iter_changes_mixed_node_length(self):
1057
1076
# aaa to be not loaded (later test)
1058
1077
# aab, b, at to be returned.
1059
1078
# basis splits at byte 0,1,2, aaa is commonb is basis only
1060
basis_dict = {('aaa',): 'foo bar',
1061
('aab',): 'common altered a', ('b',): 'foo bar b'}
1079
basis_dict = {(b'aaa',): b'foo bar',
1080
(b'aab',): b'common altered a', (b'b',): b'foo bar b'}
1062
1081
# target splits at byte 1,2, at is target only
1063
target_dict = {('aaa',): 'foo bar',
1064
('aab',): 'common altered b', ('at',): 'foo bar t'}
1082
target_dict = {(b'aaa',): b'foo bar',
1083
(b'aab',): b'common altered b', (b'at',): b'foo bar t'}
1066
(('aab',), 'common altered a', 'common altered b'),
1067
(('at',), None, 'foo bar t'),
1068
(('b',), 'foo bar b', None),
1085
((b'aab',), b'common altered a', b'common altered b'),
1086
((b'at',), None, b'foo bar t'),
1087
((b'b',), b'foo bar b', None),
1070
1089
basis = self._get_map(basis_dict, maximum_size=10)
1071
1090
target = self._get_map(target_dict, maximum_size=10,
1081
1100
# aaa to be not loaded
1082
1101
# aaa not to be in result.
1083
basis_dict = {('aaa',): 'foo bar',
1084
('aab',): 'common altered a', ('b',): 'foo bar b'}
1102
basis_dict = {(b'aaa',): b'foo bar',
1103
(b'aab',): b'common altered a', (b'b',): b'foo bar b'}
1085
1104
# target splits at byte 1, at is target only
1086
target_dict = {('aaa',): 'foo bar',
1087
('aab',): 'common altered b', ('at',): 'foo bar t'}
1105
target_dict = {(b'aaa',): b'foo bar',
1106
(b'aab',): b'common altered b', (b'at',): b'foo bar t'}
1088
1107
basis = self._get_map(basis_dict, maximum_size=10)
1089
1108
target = self._get_map(target_dict, maximum_size=10,
1090
1109
chk_bytes=basis._store)
1091
1110
basis_get = basis._store.get_record_stream
1092
1111
def get_record_stream(keys, order, fulltext):
1093
if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
1094
self.fail("'aaa' pointer was followed %r" % keys)
1112
if (b'sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
1113
raise AssertionError("'aaa' pointer was followed %r" % keys)
1095
1114
return basis_get(keys, order, fulltext)
1096
1115
basis._store.get_record_stream = get_record_stream
1097
1116
result = sorted(list(target.iter_changes(basis)))
1098
1117
for change in result:
1099
if change[0] == ('aaa',):
1118
if change[0] == (b'aaa',):
1100
1119
self.fail("Found unexpected change: %s" % change)
1102
1121
def test_iter_changes_unchanged_keys_in_multi_key_leafs_ignored(self):
1103
1122
# Within a leaf there are no hash's to exclude keys, make sure multi
1104
1123
# value leaf nodes are handled well.
1105
basis_dict = {('aaa',): 'foo bar',
1106
('aab',): 'common altered a', ('b',): 'foo bar b'}
1107
target_dict = {('aaa',): 'foo bar',
1108
('aab',): 'common altered b', ('at',): 'foo bar t'}
1124
basis_dict = {(b'aaa',): b'foo bar',
1125
(b'aab',): b'common altered a', (b'b',): b'foo bar b'}
1126
target_dict = {(b'aaa',): b'foo bar',
1127
(b'aab',): b'common altered b', (b'at',): b'foo bar t'}
1110
(('aab',), 'common altered a', 'common altered b'),
1111
(('at',), None, 'foo bar t'),
1112
(('b',), 'foo bar b', None),
1129
((b'aab',), b'common altered a', b'common altered b'),
1130
((b'at',), None, b'foo bar t'),
1131
((b'b',), b'foo bar b', None),
1114
1133
basis = self._get_map(basis_dict)
1115
1134
target = self._get_map(target_dict, chk_bytes=basis._store)
1124
1143
def test_iteritems_two_items(self):
1125
1144
chk_bytes = self.get_chk_bytes()
1126
1145
root_key = CHKMap.from_dict(chk_bytes,
1127
{"a":"content here", "b":"more content"})
1146
{b"a": b"content here", b"b": b"more content"})
1128
1147
chkmap = CHKMap(chk_bytes, root_key)
1129
self.assertEqual([(("a",), "content here"), (("b",), "more content")],
1148
self.assertEqual([((b"a",), b"content here"), ((b"b",), b"more content")],
1130
1149
sorted(list(chkmap.iteritems())))
1132
1151
def test_iteritems_selected_one_of_two_items(self):
1133
chkmap = self._get_map( {("a",):"content here", ("b",):"more content"})
1134
self.assertEqual({("a",): "content here"},
1135
self.to_dict(chkmap, [("a",)]))
1152
chkmap = self._get_map({(b"a",):b"content here", (b"b",):b"more content"})
1153
self.assertEqual({(b"a",): b"content here"},
1154
self.to_dict(chkmap, [(b"a",)]))
1137
1156
def test_iteritems_keys_prefixed_by_2_width_nodes(self):
1138
1157
chkmap = self._get_map(
1139
{("a","a"):"content here", ("a", "b",):"more content",
1140
("b", ""): 'boring content'},
1158
{(b"a", b"a"): b"content here", (b"a", b"b",):b"more content",
1159
(b"b", b""): b'boring content'},
1141
1160
maximum_size=10, key_width=2)
1142
1161
self.assertEqual(
1143
{("a", "a"): "content here", ("a", "b"): 'more content'},
1144
self.to_dict(chkmap, [("a",)]))
1162
{(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1163
self.to_dict(chkmap, [(b"a",)]))
1146
1165
def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1147
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', '')))
1166
search_key_func = chk_map.search_key_registry.get(b'hash-16-way')
1167
self.assertEqual(b'E8B7BE43\x00E8B7BE43',
1168
search_key_func(StaticTuple(b'a', b'a')))
1169
self.assertEqual(b'E8B7BE43\x0071BEEFF9',
1170
search_key_func(StaticTuple(b'a', b'b')))
1171
self.assertEqual(b'71BEEFF9\x0000000000',
1172
search_key_func(StaticTuple(b'b', b'')))
1154
1173
chkmap = self._get_map(
1155
{("a","a"):"content here", ("a", "b",):"more content",
1156
("b", ""): 'boring content'},
1174
{(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",
1175
(b"b", b""): b'boring content'},
1157
1176
maximum_size=10, key_width=2, search_key_func=search_key_func)
1158
1177
self.assertEqual(
1159
{("a", "a"): "content here", ("a", "b"): 'more content'},
1160
self.to_dict(chkmap, [("a",)]))
1178
{(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1179
self.to_dict(chkmap, [(b"a",)]))
1162
1181
def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):
1163
1182
chkmap = self._get_map(
1164
{("a","a"):"content here", ("a", "b",):"more content",
1165
("b", ""): 'boring content'}, key_width=2)
1183
{(b"a", b"a"):b"content here", (b"a", b"b",): b"more content",
1184
(b"b", b""): b'boring content'}, key_width=2)
1166
1185
self.assertEqual(
1167
{("a", "a"): "content here", ("a", "b"): 'more content'},
1168
self.to_dict(chkmap, [("a",)]))
1186
{(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1187
self.to_dict(chkmap, [(b"a",)]))
1170
1189
def test___len__empty(self):
1171
1190
chkmap = self._get_map({})
1172
1191
self.assertEqual(0, len(chkmap))
1174
1193
def test___len__2(self):
1175
chkmap = self._get_map({("foo",):"bar", ("gam",):"quux"})
1194
chkmap = self._get_map({(b"foo",): b"bar", (b"gam",): b"quux"})
1176
1195
self.assertEqual(2, len(chkmap))
1178
1197
def test_max_size_100_bytes_new(self):
1179
1198
# When there is a 100 byte upper node limit, a tree is formed.
1180
chkmap = self._get_map({("k1"*50,):"v1", ("k2"*50,):"v2"}, maximum_size=100)
1199
chkmap = self._get_map({(b"k1"*50,):b"v1", (b"k2"*50,):b"v2"}, maximum_size=100)
1181
1200
# We expect three nodes:
1182
1201
# A root, with two children, and with two key prefixes - k1 to one, and
1183
1202
# k2 to the other as our node splitting is only just being developed.
1197
1216
nodes = sorted(chkmap._root_node._items.items())
1198
1217
ptr1 = nodes[0]
1199
1218
ptr2 = nodes[1]
1200
self.assertEqual('k1', ptr1[0])
1201
self.assertEqual('k2', ptr2[0])
1219
self.assertEqual(b'k1', ptr1[0])
1220
self.assertEqual(b'k2', ptr2[0])
1202
1221
node1 = chk_map._deserialise(chkmap._read_bytes(ptr1[1]), ptr1[1], None)
1203
1222
self.assertIsInstance(node1, LeafNode)
1204
1223
self.assertEqual(1, len(node1))
1205
self.assertEqual({('k1'*50,): 'v1'}, self.to_dict(node1, chkmap._store))
1224
self.assertEqual({(b'k1'*50,): b'v1'}, self.to_dict(node1, chkmap._store))
1206
1225
node2 = chk_map._deserialise(chkmap._read_bytes(ptr2[1]), ptr2[1], None)
1207
1226
self.assertIsInstance(node2, LeafNode)
1208
1227
self.assertEqual(1, len(node2))
1209
self.assertEqual({('k2'*50,): 'v2'}, self.to_dict(node2, chkmap._store))
1228
self.assertEqual({(b'k2'*50,): b'v2'}, self.to_dict(node2, chkmap._store))
1210
1229
# Having checked we have a good structure, check that the content is
1211
1230
# still accessible.
1212
1231
self.assertEqual(2, len(chkmap))
1213
self.assertEqual({("k1"*50,): "v1", ("k2"*50,): "v2"},
1232
self.assertEqual({(b"k1"*50,): b"v1", (b"k2"*50,): b"v2"},
1214
1233
self.to_dict(chkmap))
1216
1235
def test_init_root_is_LeafNode_new(self):
1230
1249
def test_map_first_item_new(self):
1231
1250
chk_bytes = self.get_chk_bytes()
1232
1251
chkmap = CHKMap(chk_bytes, None)
1233
chkmap.map(("foo,",), "bar")
1234
self.assertEqual({('foo,',): 'bar'}, self.to_dict(chkmap))
1252
chkmap.map((b"foo,",), b"bar")
1253
self.assertEqual({(b'foo,',): b'bar'}, self.to_dict(chkmap))
1235
1254
self.assertEqual(1, len(chkmap))
1236
1255
key = chkmap._save()
1237
1256
leaf_node = LeafNode()
1238
leaf_node.map(chk_bytes, ("foo,",), "bar")
1257
leaf_node.map(chk_bytes, (b"foo,",), b"bar")
1239
1258
self.assertEqual([key], leaf_node.serialise(chk_bytes))
1241
1260
def test_unmap_last_item_root_is_leaf_new(self):
1242
chkmap = self._get_map({("k1"*50,): "v1", ("k2"*50,): "v2"})
1243
chkmap.unmap(("k1"*50,))
1244
chkmap.unmap(("k2"*50,))
1261
chkmap = self._get_map({(b"k1"*50,): b"v1", (b"k2"*50,): b"v2"})
1262
chkmap.unmap((b"k1"*50,))
1263
chkmap.unmap((b"k2"*50,))
1245
1264
self.assertEqual(0, len(chkmap))
1246
1265
self.assertEqual({}, self.to_dict(chkmap))
1247
1266
key = chkmap._save()
1315
1334
def _test_search_key(key):
1316
return 'test:' + '\x00'.join(key)
1335
return b'test:' + b'\x00'.join(key)
1319
1338
class TestMapSearchKeys(TestCaseWithStore):
1321
1340
def test_default_chk_map_uses_flat_search_key(self):
1322
1341
chkmap = chk_map.CHKMap(self.get_chk_bytes(), None)
1323
self.assertEqual('1',
1324
chkmap._search_key_func(('1',)))
1325
self.assertEqual('1\x002',
1326
chkmap._search_key_func(('1', '2')))
1327
self.assertEqual('1\x002\x003',
1328
chkmap._search_key_func(('1', '2', '3')))
1342
self.assertEqual(b'1',
1343
chkmap._search_key_func((b'1',)))
1344
self.assertEqual(b'1\x002',
1345
chkmap._search_key_func((b'1', b'2')))
1346
self.assertEqual(b'1\x002\x003',
1347
chkmap._search_key_func((b'1', b'2', b'3')))
1330
1349
def test_search_key_is_passed_to_root_node(self):
1331
1350
chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,
1332
1351
search_key_func=_test_search_key)
1333
1352
self.assertIs(_test_search_key, chkmap._search_key_func)
1334
self.assertEqual('test:1\x002\x003',
1335
chkmap._search_key_func(('1', '2', '3')))
1336
self.assertEqual('test:1\x002\x003',
1337
chkmap._root_node._search_key(('1', '2', '3')))
1353
self.assertEqual(b'test:1\x002\x003',
1354
chkmap._search_key_func((b'1', b'2', b'3')))
1355
self.assertEqual(b'test:1\x002\x003',
1356
chkmap._root_node._search_key((b'1', b'2', b'3')))
1339
1358
def test_search_key_passed_via__ensure_root(self):
1340
1359
chk_bytes = self.get_chk_bytes()
1344
1363
chkmap = chk_map.CHKMap(chk_bytes, root_key,
1345
1364
search_key_func=_test_search_key)
1346
1365
chkmap._ensure_root()
1347
self.assertEqual('test:1\x002\x003',
1348
chkmap._root_node._search_key(('1', '2', '3')))
1366
self.assertEqual(b'test:1\x002\x003',
1367
chkmap._root_node._search_key((b'1', b'2', b'3')))
1350
1369
def test_search_key_with_internal_node(self):
1351
1370
chk_bytes = self.get_chk_bytes()
1352
1371
chkmap = chk_map.CHKMap(chk_bytes, None,
1353
1372
search_key_func=_test_search_key)
1354
1373
chkmap._root_node.set_maximum_size(10)
1355
chkmap.map(('1',), 'foo')
1356
chkmap.map(('2',), 'bar')
1357
chkmap.map(('3',), 'baz')
1374
chkmap.map((b'1',), b'foo')
1375
chkmap.map((b'2',), b'bar')
1376
chkmap.map((b'3',), b'baz')
1358
1377
self.assertEqualDiff("'' InternalNode\n"
1359
1378
" 'test:1' LeafNode\n"
1360
1379
" ('1',) 'foo'\n"
1472
1491
def test_current_size_items(self):
1473
1492
node = LeafNode()
1474
1493
base_size = node._current_size()
1475
node.map(None, ("foo bar",), "baz")
1494
node.map(None, (b"foo bar",), b"baz")
1476
1495
self.assertEqual(base_size + 14, node._current_size())
1478
1497
def test_deserialise_empty(self):
1479
node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
1498
node = LeafNode.deserialise(b"chkleaf:\n10\n1\n0\n\n", (b"sha1:1234",))
1480
1499
self.assertEqual(0, len(node))
1481
1500
self.assertEqual(10, node.maximum_size)
1482
self.assertEqual(("sha1:1234",), node.key())
1501
self.assertEqual((b"sha1:1234",), node.key())
1483
1502
self.assertIs(None, node._search_prefix)
1484
1503
self.assertIs(None, node._common_serialised_prefix)
1486
1505
def test_deserialise_items(self):
1487
1506
node = LeafNode.deserialise(
1488
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1507
b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1490
1509
self.assertEqual(2, len(node))
1491
self.assertEqual([(("foo bar",), "baz"), (("quux",), "blarh")],
1510
self.assertEqual([((b"foo bar",), b"baz"), ((b"quux",), b"blarh")],
1492
1511
sorted(node.iteritems(None)))
1494
1513
def test_deserialise_item_with_null_width_1(self):
1495
1514
node = LeafNode.deserialise(
1496
"chkleaf:\n0\n1\n2\n\nfoo\x001\nbar\x00baz\nquux\x001\nblarh\n",
1515
b"chkleaf:\n0\n1\n2\n\nfoo\x001\nbar\x00baz\nquux\x001\nblarh\n",
1498
1517
self.assertEqual(2, len(node))
1499
self.assertEqual([(("foo",), "bar\x00baz"), (("quux",), "blarh")],
1518
self.assertEqual([((b"foo",), b"bar\x00baz"), ((b"quux",), b"blarh")],
1500
1519
sorted(node.iteritems(None)))
1502
1521
def test_deserialise_item_with_null_width_2(self):
1503
1522
node = LeafNode.deserialise(
1504
"chkleaf:\n0\n2\n2\n\nfoo\x001\x001\nbar\x00baz\n"
1505
"quux\x00\x001\nblarh\n",
1523
b"chkleaf:\n0\n2\n2\n\nfoo\x001\x001\nbar\x00baz\n"
1524
b"quux\x00\x001\nblarh\n",
1507
1526
self.assertEqual(2, len(node))
1508
self.assertEqual([(("foo", "1"), "bar\x00baz"), (("quux", ""), "blarh")],
1527
self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"quux", b""), b"blarh")],
1509
1528
sorted(node.iteritems(None)))
1511
1530
def test_iteritems_selected_one_of_two_items(self):
1512
1531
node = LeafNode.deserialise(
1513
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1532
b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1515
1534
self.assertEqual(2, len(node))
1516
self.assertEqual([(("quux",), "blarh")],
1517
sorted(node.iteritems(None, [("quux",), ("qaz",)])))
1535
self.assertEqual([((b"quux",), b"blarh")],
1536
sorted(node.iteritems(None, [(b"quux",), (b"qaz",)])))
1519
1538
def test_deserialise_item_with_common_prefix(self):
1520
1539
node = LeafNode.deserialise(
1521
"chkleaf:\n0\n2\n2\nfoo\x00\n1\x001\nbar\x00baz\n2\x001\nblarh\n",
1540
b"chkleaf:\n0\n2\n2\nfoo\x00\n1\x001\nbar\x00baz\n2\x001\nblarh\n",
1523
1542
self.assertEqual(2, len(node))
1524
self.assertEqual([(("foo", "1"), "bar\x00baz"), (("foo", "2"), "blarh")],
1543
self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"foo", b"2"), b"blarh")],
1525
1544
sorted(node.iteritems(None)))
1526
1545
self.assertIs(chk_map._unknown, node._search_prefix)
1527
self.assertEqual('foo\x00', node._common_serialised_prefix)
1546
self.assertEqual(b'foo\x00', node._common_serialised_prefix)
1529
1548
def test_deserialise_multi_line(self):
1530
1549
node = LeafNode.deserialise(
1531
"chkleaf:\n0\n2\n2\nfoo\x00\n1\x002\nbar\nbaz\n2\x002\nblarh\n\n",
1550
b"chkleaf:\n0\n2\n2\nfoo\x00\n1\x002\nbar\nbaz\n2\x002\nblarh\n\n",
1533
1552
self.assertEqual(2, len(node))
1534
self.assertEqual([(("foo", "1"), "bar\nbaz"),
1535
(("foo", "2"), "blarh\n"),
1553
self.assertEqual([((b"foo", b"1"), b"bar\nbaz"),
1554
((b"foo", b"2"), b"blarh\n"),
1536
1555
], sorted(node.iteritems(None)))
1537
1556
self.assertIs(chk_map._unknown, node._search_prefix)
1538
self.assertEqual('foo\x00', node._common_serialised_prefix)
1557
self.assertEqual(b'foo\x00', node._common_serialised_prefix)
1540
1559
def test_key_new(self):
1541
1560
node = LeafNode()
1549
1568
def test_key_after_unmap(self):
1550
1569
node = LeafNode.deserialise(
1551
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1553
node.unmap(None, ("foo bar",))
1570
b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1572
node.unmap(None, (b"foo bar",))
1554
1573
self.assertEqual(None, node.key())
1556
1575
def test_map_exceeding_max_size_only_entry_new(self):
1557
1576
node = LeafNode()
1558
1577
node.set_maximum_size(10)
1559
result = node.map(None, ("foo bar",), "baz quux")
1560
self.assertEqual(("foo bar", [("", node)]), result)
1578
result = node.map(None, (b"foo bar",), b"baz quux")
1579
self.assertEqual((b"foo bar", [(b"", node)]), result)
1561
1580
self.assertTrue(10 < node._current_size())
1563
1582
def test_map_exceeding_max_size_second_entry_early_difference_new(self):
1564
1583
node = LeafNode()
1565
1584
node.set_maximum_size(10)
1566
node.map(None, ("foo bar",), "baz quux")
1567
prefix, result = list(node.map(None, ("blue",), "red"))
1568
self.assertEqual("", prefix)
1585
node.map(None, (b"foo bar",), b"baz quux")
1586
prefix, result = list(node.map(None, (b"blue",), b"red"))
1587
self.assertEqual(b"", prefix)
1569
1588
self.assertEqual(2, len(result))
1570
split_chars = set([result[0][0], result[1][0]])
1571
self.assertEqual(set(["f", "b"]), split_chars)
1589
split_chars = {result[0][0], result[1][0]}
1590
self.assertEqual({b"f", b"b"}, split_chars)
1572
1591
nodes = dict(result)
1574
self.assertEqual({("foo bar",): "baz quux"}, self.to_dict(node, None))
1593
self.assertEqual({(b"foo bar",): b"baz quux"}, self.to_dict(node, None))
1575
1594
self.assertEqual(10, node.maximum_size)
1576
1595
self.assertEqual(1, node._key_width)
1578
self.assertEqual({("blue",): "red"}, self.to_dict(node, None))
1597
self.assertEqual({(b"blue",): b"red"}, self.to_dict(node, None))
1579
1598
self.assertEqual(10, node.maximum_size)
1580
1599
self.assertEqual(1, node._key_width)
1582
1601
def test_map_first(self):
1583
1602
node = LeafNode()
1584
result = node.map(None, ("foo bar",), "baz quux")
1585
self.assertEqual(("foo bar", [("", node)]), result)
1586
self.assertEqual({("foo bar",):"baz quux"}, self.to_dict(node, None))
1603
result = node.map(None, (b"foo bar",), b"baz quux")
1604
self.assertEqual((b"foo bar", [(b"", node)]), result)
1605
self.assertEqual({(b"foo bar",):b"baz quux"}, self.to_dict(node, None))
1587
1606
self.assertEqual(1, len(node))
1589
1608
def test_map_second(self):
1590
1609
node = LeafNode()
1591
node.map(None, ("foo bar",), "baz quux")
1592
result = node.map(None, ("bingo",), "bango")
1593
self.assertEqual(("", [("", node)]), result)
1594
self.assertEqual({("foo bar",):"baz quux", ("bingo",):"bango"},
1610
node.map(None, (b"foo bar",), b"baz quux")
1611
result = node.map(None, (b"bingo",), b"bango")
1612
self.assertEqual((b"", [(b"", node)]), result)
1613
self.assertEqual({(b"foo bar",): b"baz quux", (b"bingo",): b"bango"},
1595
1614
self.to_dict(node, None))
1596
1615
self.assertEqual(2, len(node))
1598
1617
def test_map_replacement(self):
1599
1618
node = LeafNode()
1600
node.map(None, ("foo bar",), "baz quux")
1601
result = node.map(None, ("foo bar",), "bango")
1602
self.assertEqual(("foo bar", [("", node)]), result)
1603
self.assertEqual({("foo bar",): "bango"},
1619
node.map(None, (b"foo bar",), b"baz quux")
1620
result = node.map(None, (b"foo bar",), b"bango")
1621
self.assertEqual((b"foo bar", [(b"", node)]), result)
1622
self.assertEqual({(b"foo bar",): b"bango"},
1604
1623
self.to_dict(node, None))
1605
1624
self.assertEqual(1, len(node))
1608
1627
store = self.get_chk_bytes()
1609
1628
node = LeafNode()
1610
1629
node.set_maximum_size(10)
1611
expected_key = ("sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)
1630
expected_key = (b"sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)
1612
1631
self.assertEqual([expected_key],
1613
1632
list(node.serialise(store)))
1614
self.assertEqual("chkleaf:\n10\n1\n0\n\n", self.read_bytes(store, expected_key))
1633
self.assertEqual(b"chkleaf:\n10\n1\n0\n\n", self.read_bytes(store, expected_key))
1615
1634
self.assertEqual(expected_key, node.key())
1617
1636
def test_serialise_items(self):
1618
1637
store = self.get_chk_bytes()
1619
1638
node = LeafNode()
1620
1639
node.set_maximum_size(10)
1621
node.map(None, ("foo bar",), "baz quux")
1622
expected_key = ("sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)
1623
self.assertEqual('foo bar', node._common_serialised_prefix)
1640
node.map(None, (b"foo bar",), b"baz quux")
1641
expected_key = (b"sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)
1642
self.assertEqual(b'foo bar', node._common_serialised_prefix)
1624
1643
self.assertEqual([expected_key],
1625
1644
list(node.serialise(store)))
1626
self.assertEqual("chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",
1645
self.assertEqual(b"chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",
1627
1646
self.read_bytes(store, expected_key))
1628
1647
self.assertEqual(expected_key, node.key())
1634
1653
def test_unique_serialised_prefix_one_item_new(self):
1635
1654
node = LeafNode()
1636
node.map(None, ("foo bar", "baz"), "baz quux")
1637
self.assertEqual("foo bar\x00baz", node._compute_search_prefix())
1655
node.map(None, (b"foo bar", b"baz"), b"baz quux")
1656
self.assertEqual(b"foo bar\x00baz", node._compute_search_prefix())
1639
1658
def test_unmap_missing(self):
1640
1659
node = LeafNode()
1641
self.assertRaises(KeyError, node.unmap, None, ("foo bar",))
1660
self.assertRaises(KeyError, node.unmap, None, (b"foo bar",))
1643
1662
def test_unmap_present(self):
1644
1663
node = LeafNode()
1645
node.map(None, ("foo bar",), "baz quux")
1646
result = node.unmap(None, ("foo bar",))
1664
node.map(None, (b"foo bar",), b"baz quux")
1665
result = node.unmap(None, (b"foo bar",))
1647
1666
self.assertEqual(node, result)
1648
1667
self.assertEqual({}, self.to_dict(node, None))
1649
1668
self.assertEqual(0, len(node))
1651
1670
def test_map_maintains_common_prefixes(self):
1652
1671
node = LeafNode()
1653
1672
node._key_width = 2
1654
node.map(None, ("foo bar", "baz"), "baz quux")
1655
self.assertEqual('foo bar\x00baz', node._search_prefix)
1656
self.assertEqual('foo bar\x00baz', node._common_serialised_prefix)
1657
node.map(None, ("foo bar", "bing"), "baz quux")
1658
self.assertEqual('foo bar\x00b', node._search_prefix)
1659
self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
1660
node.map(None, ("fool", "baby"), "baz quux")
1661
self.assertEqual('foo', node._search_prefix)
1662
self.assertEqual('foo', node._common_serialised_prefix)
1663
node.map(None, ("foo bar", "baz"), "replaced")
1664
self.assertEqual('foo', node._search_prefix)
1665
self.assertEqual('foo', node._common_serialised_prefix)
1666
node.map(None, ("very", "different"), "value")
1667
self.assertEqual('', node._search_prefix)
1668
self.assertEqual('', node._common_serialised_prefix)
1673
node.map(None, (b"foo bar", b"baz"), b"baz quux")
1674
self.assertEqual(b'foo bar\x00baz', node._search_prefix)
1675
self.assertEqual(b'foo bar\x00baz', node._common_serialised_prefix)
1676
node.map(None, (b"foo bar", b"bing"), b"baz quux")
1677
self.assertEqual(b'foo bar\x00b', node._search_prefix)
1678
self.assertEqual(b'foo bar\x00b', node._common_serialised_prefix)
1679
node.map(None, (b"fool", b"baby"), b"baz quux")
1680
self.assertEqual(b'foo', node._search_prefix)
1681
self.assertEqual(b'foo', node._common_serialised_prefix)
1682
node.map(None, (b"foo bar", b"baz"), b"replaced")
1683
self.assertEqual(b'foo', node._search_prefix)
1684
self.assertEqual(b'foo', node._common_serialised_prefix)
1685
node.map(None, (b"very", b"different"), b"value")
1686
self.assertEqual(b'', node._search_prefix)
1687
self.assertEqual(b'', node._common_serialised_prefix)
1670
1689
def test_unmap_maintains_common_prefixes(self):
1671
1690
node = LeafNode()
1672
1691
node._key_width = 2
1673
node.map(None, ("foo bar", "baz"), "baz quux")
1674
node.map(None, ("foo bar", "bing"), "baz quux")
1675
node.map(None, ("fool", "baby"), "baz quux")
1676
node.map(None, ("very", "different"), "value")
1677
self.assertEqual('', node._search_prefix)
1678
self.assertEqual('', node._common_serialised_prefix)
1679
node.unmap(None, ("very", "different"))
1680
self.assertEqual("foo", node._search_prefix)
1681
self.assertEqual("foo", node._common_serialised_prefix)
1682
node.unmap(None, ("fool", "baby"))
1683
self.assertEqual('foo bar\x00b', node._search_prefix)
1684
self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
1685
node.unmap(None, ("foo bar", "baz"))
1686
self.assertEqual('foo bar\x00bing', node._search_prefix)
1687
self.assertEqual('foo bar\x00bing', node._common_serialised_prefix)
1688
node.unmap(None, ("foo bar", "bing"))
1692
node.map(None, (b"foo bar", b"baz"), b"baz quux")
1693
node.map(None, (b"foo bar", b"bing"), b"baz quux")
1694
node.map(None, (b"fool", b"baby"), b"baz quux")
1695
node.map(None, (b"very", b"different"), b"value")
1696
self.assertEqual(b'', node._search_prefix)
1697
self.assertEqual(b'', node._common_serialised_prefix)
1698
node.unmap(None, (b"very", b"different"))
1699
self.assertEqual(b"foo", node._search_prefix)
1700
self.assertEqual(b"foo", node._common_serialised_prefix)
1701
node.unmap(None, (b"fool", b"baby"))
1702
self.assertEqual(b'foo bar\x00b', node._search_prefix)
1703
self.assertEqual(b'foo bar\x00b', node._common_serialised_prefix)
1704
node.unmap(None, (b"foo bar", b"baz"))
1705
self.assertEqual(b'foo bar\x00bing', node._search_prefix)
1706
self.assertEqual(b'foo bar\x00bing', node._common_serialised_prefix)
1707
node.unmap(None, (b"foo bar", b"bing"))
1689
1708
self.assertEqual(None, node._search_prefix)
1690
1709
self.assertEqual(None, node._common_serialised_prefix)
1711
1730
keys = list(node.serialise(chk_bytes))
1712
1731
child_key = child.serialise(chk_bytes)[0]
1713
1732
self.assertEqual(
1714
[child_key, ('sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
1733
[child_key, (b'sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
1716
1735
# We should be able to access deserialised content.
1717
1736
bytes = self.read_bytes(chk_bytes, keys[1])
1718
1737
node = chk_map._deserialise(bytes, keys[1], None)
1719
1738
self.assertEqual(1, len(node))
1720
self.assertEqual({('foo',): 'bar'}, self.to_dict(node, chk_bytes))
1739
self.assertEqual({(b'foo',): b'bar'}, self.to_dict(node, chk_bytes))
1721
1740
self.assertEqual(3, node._node_width)
1723
1742
def test_add_node_resets_key_new(self):
1724
node = InternalNode('fo')
1743
node = InternalNode(b'fo')
1725
1744
child = LeafNode()
1726
1745
child.set_maximum_size(100)
1727
child.map(None, ("foo",), "bar")
1728
node.add_node("foo", child)
1746
child.map(None, (b"foo",), b"bar")
1747
node.add_node(b"foo", child)
1729
1748
chk_bytes = self.get_chk_bytes()
1730
1749
keys = list(node.serialise(chk_bytes))
1731
1750
self.assertEqual(keys[1], node._key)
1732
node.add_node("fos", child)
1751
node.add_node(b"fos", child)
1733
1752
self.assertEqual(None, node._key)
1735
1754
# def test_add_node_empty_oversized_one_ok_new(self):
1738
1757
# def test_add_node_one_oversized_second_splits_errors(self):
1740
1759
def test__iter_nodes_no_key_filter(self):
1741
node = InternalNode('')
1743
child.set_maximum_size(100)
1744
child.map(None, ("foo",), "bar")
1745
node.add_node("f", child)
1747
child.set_maximum_size(100)
1748
child.map(None, ("bar",), "baz")
1749
node.add_node("b", child)
1760
node = InternalNode(b'')
1762
child.set_maximum_size(100)
1763
child.map(None, (b"foo",), b"bar")
1764
node.add_node(b"f", child)
1766
child.set_maximum_size(100)
1767
child.map(None, (b"bar",), b"baz")
1768
node.add_node(b"b", child)
1751
1770
for child, node_key_filter in node._iter_nodes(None, key_filter=None):
1752
1771
self.assertEqual(None, node_key_filter)
1754
1773
def test__iter_nodes_splits_key_filter(self):
1755
node = InternalNode('')
1757
child.set_maximum_size(100)
1758
child.map(None, ("foo",), "bar")
1759
node.add_node("f", child)
1761
child.set_maximum_size(100)
1762
child.map(None, ("bar",), "baz")
1763
node.add_node("b", child)
1774
node = InternalNode(b'')
1776
child.set_maximum_size(100)
1777
child.map(None, (b"foo",), b"bar")
1778
node.add_node(b"f", child)
1780
child.set_maximum_size(100)
1781
child.map(None, (b"bar",), b"baz")
1782
node.add_node(b"b", child)
1765
1784
# foo and bar both match exactly one leaf node, but 'cat' should not
1766
1785
# match any, and should not be placed in one.
1767
key_filter = (('foo',), ('bar',), ('cat',))
1786
key_filter = ((b'foo',), (b'bar',), (b'cat',))
1768
1787
for child, node_key_filter in node._iter_nodes(None,
1769
1788
key_filter=key_filter):
1770
1789
# each child could only match one key filter, so make sure it was
1772
1791
self.assertEqual(1, len(node_key_filter))
1774
1793
def test__iter_nodes_with_multiple_matches(self):
1775
node = InternalNode('')
1777
child.set_maximum_size(100)
1778
child.map(None, ("foo",), "val")
1779
child.map(None, ("fob",), "val")
1780
node.add_node("f", child)
1782
child.set_maximum_size(100)
1783
child.map(None, ("bar",), "val")
1784
child.map(None, ("baz",), "val")
1785
node.add_node("b", child)
1794
node = InternalNode(b'')
1796
child.set_maximum_size(100)
1797
child.map(None, (b"foo",), b"val")
1798
child.map(None, (b"fob",), b"val")
1799
node.add_node(b"f", child)
1801
child.set_maximum_size(100)
1802
child.map(None, (b"bar",), b"val")
1803
child.map(None, (b"baz",), b"val")
1804
node.add_node(b"b", child)
1787
1806
# Note that 'ram' doesn't match anything, so it should be freely
1789
key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
1808
key_filter = ((b'foo',), (b'fob',), (b'bar',), (b'baz',), (b'ram',))
1790
1809
for child, node_key_filter in node._iter_nodes(None,
1791
1810
key_filter=key_filter):
1792
1811
# each child could match two key filters, so make sure they were
1794
1813
self.assertEqual(2, len(node_key_filter))
1796
1815
def make_fo_fa_node(self):
1797
node = InternalNode('f')
1799
child.set_maximum_size(100)
1800
child.map(None, ("foo",), "val")
1801
child.map(None, ("fob",), "val")
1802
node.add_node('fo', child)
1804
child.set_maximum_size(100)
1805
child.map(None, ("far",), "val")
1806
child.map(None, ("faz",), "val")
1807
node.add_node("fa", child)
1816
node = InternalNode(b'f')
1818
child.set_maximum_size(100)
1819
child.map(None, (b"foo",), b"val")
1820
child.map(None, (b"fob",), b"val")
1821
node.add_node(b'fo', child)
1823
child.set_maximum_size(100)
1824
child.map(None, (b"far",), b"val")
1825
child.map(None, (b"faz",), b"val")
1826
node.add_node(b"fa", child)
1810
1829
def test__iter_nodes_single_entry(self):
1811
1830
node = self.make_fo_fa_node()
1812
key_filter = [('foo',)]
1831
key_filter = [(b'foo',)]
1813
1832
nodes = list(node._iter_nodes(None, key_filter=key_filter))
1814
1833
self.assertEqual(1, len(nodes))
1815
1834
self.assertEqual(key_filter, nodes[0][1])
1817
1836
def test__iter_nodes_single_entry_misses(self):
1818
1837
node = self.make_fo_fa_node()
1819
key_filter = [('bar',)]
1838
key_filter = [(b'bar',)]
1820
1839
nodes = list(node._iter_nodes(None, key_filter=key_filter))
1821
1840
self.assertEqual(0, len(nodes))
1823
1842
def test__iter_nodes_mixed_key_width(self):
1824
1843
node = self.make_fo_fa_node()
1825
key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
1844
key_filter = [(b'foo', b'bar'), (b'foo',), (b'fo',), (b'b',)]
1826
1845
nodes = list(node._iter_nodes(None, key_filter=key_filter))
1827
1846
self.assertEqual(1, len(nodes))
1828
1847
matches = key_filter[:]
1829
matches.remove(('b',))
1848
matches.remove((b'b',))
1830
1849
self.assertEqual(sorted(matches), sorted(nodes[0][1]))
1832
1851
def test__iter_nodes_match_all(self):
1833
1852
node = self.make_fo_fa_node()
1834
key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
1853
key_filter = [(b'foo', b'bar'), (b'foo',), (b'fo',), (b'f',)]
1835
1854
nodes = list(node._iter_nodes(None, key_filter=key_filter))
1836
1855
self.assertEqual(2, len(nodes))
1838
1857
def test__iter_nodes_fixed_widths_and_misses(self):
1839
1858
node = self.make_fo_fa_node()
1840
1859
# foo and faa should both match one child, baz should miss
1841
key_filter = [('foo',), ('faa',), ('baz',)]
1860
key_filter = [(b'foo',), (b'faa',), (b'baz',)]
1842
1861
nodes = list(node._iter_nodes(None, key_filter=key_filter))
1843
1862
self.assertEqual(2, len(nodes))
1844
1863
for node, matches in nodes:
1851
1870
def test_iteritems_two_children(self):
1852
1871
node = InternalNode()
1853
1872
leaf1 = LeafNode()
1854
leaf1.map(None, ('foo bar',), 'quux')
1873
leaf1.map(None, (b'foo bar',), b'quux')
1855
1874
leaf2 = LeafNode()
1856
leaf2.map(None, ('strange',), 'beast')
1857
node.add_node("f", leaf1)
1858
node.add_node("s", leaf2)
1859
self.assertEqual([(('foo bar',), 'quux'), (('strange',), 'beast')],
1875
leaf2.map(None, (b'strange',), b'beast')
1876
node.add_node(b"f", leaf1)
1877
node.add_node(b"s", leaf2)
1878
self.assertEqual([((b'foo bar',), b'quux'), ((b'strange',), b'beast')],
1860
1879
sorted(node.iteritems(None)))
1862
1881
def test_iteritems_two_children_partial(self):
1863
1882
node = InternalNode()
1864
1883
leaf1 = LeafNode()
1865
leaf1.map(None, ('foo bar',), 'quux')
1884
leaf1.map(None, (b'foo bar',), b'quux')
1866
1885
leaf2 = LeafNode()
1867
leaf2.map(None, ('strange',), 'beast')
1868
node.add_node("f", leaf1)
1886
leaf2.map(None, (b'strange',), b'beast')
1887
node.add_node(b"f", leaf1)
1869
1888
# This sets up a path that should not be followed - it will error if
1870
1889
# the code tries to.
1871
node._items['f'] = None
1872
node.add_node("s", leaf2)
1873
self.assertEqual([(('strange',), 'beast')],
1874
sorted(node.iteritems(None, [('strange',), ('weird',)])))
1890
node._items[b'f'] = None
1891
node.add_node(b"s", leaf2)
1892
self.assertEqual([((b'strange',), b'beast')],
1893
sorted(node.iteritems(None, [(b'strange',), (b'weird',)])))
1876
1895
def test_iteritems_two_children_with_hash(self):
1877
search_key_func = chk_map.search_key_registry.get('hash-255-way')
1896
search_key_func = chk_map.search_key_registry.get(b'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, StaticTuple(b'foo bar',), b'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',)))
1885
node.add_node("\xbe", leaf1)
1901
leaf2.map(None, StaticTuple(b'strange',), b'beast')
1902
self.assertEqual(b'\xbeF\x014', search_key_func(StaticTuple(b'foo bar',)))
1903
self.assertEqual(b'\x85\xfa\xf7K', search_key_func(StaticTuple(b'strange',)))
1904
node.add_node(b"\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
node._items['\xbe'] = None
1889
node.add_node("\x85", leaf2)
1890
self.assertEqual([(('strange',), 'beast')],
1891
sorted(node.iteritems(None, [StaticTuple('strange',),
1892
StaticTuple('weird',)])))
1907
node._items[b'\xbe'] = None
1908
node.add_node(b"\x85", leaf2)
1909
self.assertEqual([((b'strange',), b'beast')],
1910
sorted(node.iteritems(None, [StaticTuple(b'strange',),
1911
StaticTuple(b'weird',)])))
1894
1913
def test_iteritems_partial_empty(self):
1895
1914
node = InternalNode()
1896
self.assertEqual([], sorted(node.iteritems([('missing',)])))
1915
self.assertEqual([], sorted(node.iteritems([(b'missing',)])))
1898
1917
def test_map_to_new_child_new(self):
1899
chkmap = self._get_map({('k1',):'foo', ('k2',):'bar'}, maximum_size=10)
1918
chkmap = self._get_map({(b'k1',): b'foo', (b'k2',): b'bar'}, maximum_size=10)
1900
1919
chkmap._ensure_root()
1901
1920
node = chkmap._root_node
1902
1921
# Ensure test validity: nothing paged in below the root.
1903
1922
self.assertEqual(2,
1904
1923
len([value for value in node._items.values()
1905
if type(value) is StaticTuple]))
1924
if isinstance(value, StaticTuple)]))
1906
1925
# now, mapping to k3 should add a k3 leaf
1907
prefix, nodes = node.map(None, ('k3',), 'quux')
1908
self.assertEqual("k", prefix)
1909
self.assertEqual([("", node)], nodes)
1926
prefix, nodes = node.map(None, (b'k3',), b'quux')
1927
self.assertEqual(b"k", prefix)
1928
self.assertEqual([(b"", node)], nodes)
1910
1929
# check new child details
1911
child = node._items['k3']
1930
child = node._items[b'k3']
1912
1931
self.assertIsInstance(child, LeafNode)
1913
1932
self.assertEqual(1, len(child))
1914
self.assertEqual({('k3',): 'quux'}, self.to_dict(child, None))
1933
self.assertEqual({(b'k3',): b'quux'}, self.to_dict(child, None))
1915
1934
self.assertEqual(None, child._key)
1916
1935
self.assertEqual(10, child.maximum_size)
1917
1936
self.assertEqual(1, child._key_width)
1918
1937
# Check overall structure:
1919
1938
self.assertEqual(3, len(chkmap))
1920
self.assertEqual({('k1',): 'foo', ('k2',): 'bar', ('k3',): 'quux'},
1939
self.assertEqual({(b'k1',): b'foo', (b'k2',): b'bar', (b'k3',): b'quux'},
1921
1940
self.to_dict(chkmap))
1922
1941
# serialising should only serialise the new data - k3 and the internal
1941
1960
# Ensure test validity: nothing paged in below the root.
1942
1961
self.assertEqual(2,
1943
1962
len([value for value in node._items.values()
1944
if type(value) is StaticTuple]))
1963
if isinstance(value, StaticTuple)]))
1945
1964
# now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1946
1965
# k23, which for simplicity in the current implementation generates
1947
1966
# a new internal node between node, and k22/k23.
1948
prefix, nodes = node.map(chkmap._store, ('k23',), 'quux')
1949
self.assertEqual("k", prefix)
1950
self.assertEqual([("", node)], nodes)
1967
prefix, nodes = node.map(chkmap._store, (b'k23',), b'quux')
1968
self.assertEqual(b"k", prefix)
1969
self.assertEqual([(b"", node)], nodes)
1951
1970
# check new child details
1952
child = node._items['k2']
1971
child = node._items[b'k2']
1953
1972
self.assertIsInstance(child, InternalNode)
1954
1973
self.assertEqual(2, len(child))
1955
self.assertEqual({('k22',): 'bar', ('k23',): 'quux'},
1974
self.assertEqual({(b'k22',): b'bar', (b'k23',): b'quux'},
1956
1975
self.to_dict(child, None))
1957
1976
self.assertEqual(None, child._key)
1958
1977
self.assertEqual(10, child.maximum_size)
2011
2030
node = chkmap._root_node
2012
2031
# unmapping k23 should give us a root, with k1 and k22 as direct
2014
result = node.unmap(chkmap._store, ('k23',))
2033
result = node.unmap(chkmap._store, (b'k23',))
2015
2034
# check the pointed-at object within node - k2 should now point at the
2016
2035
# k22 leaf (which has been paged in to see if we can collapse the tree)
2017
child = node._items['k2']
2036
child = node._items[b'k2']
2018
2037
self.assertIsInstance(child, LeafNode)
2019
2038
self.assertEqual(1, len(child))
2020
self.assertEqual({('k22',): 'bar'},
2039
self.assertEqual({(b'k22',): b'bar'},
2021
2040
self.to_dict(child, None))
2022
2041
# Check overall structure is instact:
2023
2042
self.assertEqual(2, len(chkmap))
2024
self.assertEqual({('k1',): 'foo', ('k22',): 'bar'},
2043
self.assertEqual({(b'k1',): b'foo', (b'k22',): b'bar'},
2025
2044
self.to_dict(chkmap))
2026
2045
# serialising should only serialise the new data - the root node.
2027
2046
keys = list(node.serialise(chkmap._store))
2121
2140
def test__init__(self):
2122
2141
c_map = self.make_root_only_map()
2123
2142
key1 = c_map.key()
2124
c_map.map(('aaa',), 'new aaa content')
2143
c_map.map((b'aaa',), b'new aaa content')
2125
2144
key2 = c_map._save()
2126
2145
diff = self.get_difference([key2], [key1])
2127
self.assertEqual(set([key1]), diff._all_old_chks)
2146
self.assertEqual({key1}, diff._all_old_chks)
2128
2147
self.assertEqual([], diff._old_queue)
2129
2148
self.assertEqual([], diff._new_queue)
2131
2150
def help__read_all_roots(self, search_key_func):
2132
2151
c_map = self.make_root_only_map(search_key_func=search_key_func)
2133
2152
key1 = c_map.key()
2134
c_map.map(('aaa',), 'new aaa content')
2153
c_map.map((b'aaa',), b'new aaa content')
2135
2154
key2 = c_map._save()
2136
2155
diff = self.get_difference([key2], [key1], search_key_func)
2137
2156
root_results = [record.key for record in diff._read_all_roots()]
2138
2157
self.assertEqual([key2], root_results)
2139
2158
# We should have queued up only items that aren't in the old
2141
self.assertEqual([(('aaa',), 'new aaa content')],
2160
self.assertEqual([((b'aaa',), b'new aaa content')],
2142
2161
diff._new_item_queue)
2143
2162
self.assertEqual([], diff._new_queue)
2144
2163
# And there are no old references, so that queue should be
2183
2202
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2184
2203
key1 = c_map.key()
2185
2204
c_map._dump_tree() # load everything
2186
key1_a = c_map._root_node._items['a'].key()
2187
key1_c = c_map._root_node._items['c'].key()
2188
c_map.map(('abb',), 'new abb content')
2205
key1_a = c_map._root_node._items[b'a'].key()
2206
key1_c = c_map._root_node._items[b'c'].key()
2207
c_map.map((b'abb',), b'new abb content')
2189
2208
key2 = c_map._save()
2190
key2_a = c_map._root_node._items['a'].key()
2191
key2_c = c_map._root_node._items['c'].key()
2209
key2_a = c_map._root_node._items[b'a'].key()
2210
key2_c = c_map._root_node._items[b'c'].key()
2192
2211
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2193
2212
chk_map._search_key_plain)
2194
c_map.map(('ccc',), 'new ccc content')
2213
c_map.map((b'ccc',), b'new ccc content')
2195
2214
key3 = c_map._save()
2196
key3_a = c_map._root_node._items['a'].key()
2197
key3_c = c_map._root_node._items['c'].key()
2215
key3_a = c_map._root_node._items[b'a'].key()
2216
key3_c = c_map._root_node._items[b'c'].key()
2198
2217
diff = self.get_difference([key2, key3], [key1],
2199
2218
chk_map._search_key_plain)
2200
2219
root_results = [record.key for record in diff._read_all_roots()]
2201
2220
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2202
2221
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2203
self.assertEqual([key2_a, key3_c], diff._new_queue)
2222
self.assertEqual({key2_a, key3_c}, set(diff._new_queue))
2204
2223
self.assertEqual([], diff._new_item_queue)
2205
2224
# And we should have queued up both a and c for the old set
2206
self.assertEqual([key1_a, key1_c], diff._old_queue)
2225
self.assertEqual({key1_a, key1_c}, set(diff._old_queue))
2208
2227
def test__read_all_roots_different_depths(self):
2209
2228
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2210
2229
c_map._dump_tree() # load everything
2211
2230
key1 = c_map.key()
2212
key1_a = c_map._root_node._items['a'].key()
2213
key1_c = c_map._root_node._items['c'].key()
2214
key1_d = c_map._root_node._items['d'].key()
2231
key1_a = c_map._root_node._items[b'a'].key()
2232
key1_c = c_map._root_node._items[b'c'].key()
2233
key1_d = c_map._root_node._items[b'd'].key()
2216
2235
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2217
2236
c_map2._dump_tree()
2218
2237
key2 = c_map2.key()
2219
key2_aa = c_map2._root_node._items['aa'].key()
2220
key2_ad = c_map2._root_node._items['ad'].key()
2238
key2_aa = c_map2._root_node._items[b'aa'].key()
2239
key2_ad = c_map2._root_node._items[b'ad'].key()
2222
2241
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2223
2242
root_results = [record.key for record in diff._read_all_roots()]
2225
2244
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2227
2246
self.assertEqual([key1_a], diff._old_queue)
2228
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2247
self.assertEqual({key2_aa, key2_ad}, set(diff._new_queue))
2229
2248
self.assertEqual([], diff._new_item_queue)
2231
2250
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2232
2251
root_results = [record.key for record in diff._read_all_roots()]
2233
2252
self.assertEqual([key1], root_results)
2235
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2236
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2254
self.assertEqual({key2_aa, key2_ad}, set(diff._old_queue))
2255
self.assertEqual({key1_a, key1_c, key1_d}, set(diff._new_queue))
2237
2256
self.assertEqual([], diff._new_item_queue)
2239
2258
def test__read_all_roots_different_depths_16(self):
2240
2259
c_map = self.make_two_deep_map(chk_map._search_key_16)
2241
2260
c_map._dump_tree() # load everything
2242
2261
key1 = c_map.key()
2243
key1_2 = c_map._root_node._items['2'].key()
2244
key1_4 = c_map._root_node._items['4'].key()
2245
key1_C = c_map._root_node._items['C'].key()
2246
key1_F = c_map._root_node._items['F'].key()
2262
key1_2 = c_map._root_node._items[b'2'].key()
2263
key1_4 = c_map._root_node._items[b'4'].key()
2264
key1_C = c_map._root_node._items[b'C'].key()
2265
key1_F = c_map._root_node._items[b'F'].key()
2248
2267
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2249
2268
c_map2._dump_tree()
2250
2269
key2 = c_map2.key()
2251
key2_F0 = c_map2._root_node._items['F0'].key()
2252
key2_F3 = c_map2._root_node._items['F3'].key()
2253
key2_F4 = c_map2._root_node._items['F4'].key()
2254
key2_FD = c_map2._root_node._items['FD'].key()
2270
key2_F0 = c_map2._root_node._items[b'F0'].key()
2271
key2_F3 = c_map2._root_node._items[b'F3'].key()
2272
key2_F4 = c_map2._root_node._items[b'F4'].key()
2273
key2_FD = c_map2._root_node._items[b'FD'].key()
2256
2275
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2257
2276
root_results = [record.key for record in diff._read_all_roots()]
2432
2451
c_map = self.make_two_deep_map()
2433
2452
key1 = c_map.key()
2434
2453
c_map._dump_tree() # load everything
2435
key1_a = c_map._root_node._items['a'].key()
2436
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2437
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2438
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2439
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2440
c_map.map(('aaa',), 'new aaa value')
2454
key1_a = c_map._root_node._items[b'a'].key()
2455
key1_aa = c_map._root_node._items[b'a']._items[b'aa'].key()
2456
key1_ab = c_map._root_node._items[b'a']._items[b'ab'].key()
2457
key1_ac = c_map._root_node._items[b'a']._items[b'ac'].key()
2458
key1_ad = c_map._root_node._items[b'a']._items[b'ad'].key()
2459
c_map.map((b'aaa',), b'new aaa value')
2441
2460
key2 = c_map._save()
2442
key2_a = c_map._root_node._items['a'].key()
2443
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2444
c_map.map(('acc',), 'new acc content')
2461
key2_a = c_map._root_node._items[b'a'].key()
2462
key2_aa = c_map._root_node._items[b'a']._items[b'aa'].key()
2463
c_map.map((b'acc',), b'new acc content')
2445
2464
key3 = c_map._save()
2446
key3_a = c_map._root_node._items['a'].key()
2447
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2465
key3_a = c_map._root_node._items[b'a'].key()
2466
key3_ac = c_map._root_node._items[b'a']._items[b'ac'].key()
2448
2467
diff = self.get_difference([key3], [key1, key2],
2449
2468
chk_map._search_key_plain)
2450
2469
root_results = [record.key for record in diff._read_all_roots()]
2491
2510
self.assertEqual(sorted(items), sorted(all_items))
2493
2512
def test_empty_to_one_keys(self):
2494
target = self.get_map_key({('a',): 'content'})
2513
target = self.get_map_key({(b'a',): b'content'})
2495
2514
self.assertIterInteresting([target],
2496
[(('a',), 'content')],
2515
[((b'a',), b'content')],
2499
2518
def test_none_to_one_key(self):
2500
2519
basis = self.get_map_key({})
2501
target = self.get_map_key({('a',): 'content'})
2520
target = self.get_map_key({(b'a',): b'content'})
2502
2521
self.assertIterInteresting([target],
2503
[(('a',), 'content')],
2522
[((b'a',), b'content')],
2504
2523
[target], [basis])
2506
2525
def test_one_to_none_key(self):
2507
basis = self.get_map_key({('a',): 'content'})
2526
basis = self.get_map_key({(b'a',): b'content'})
2508
2527
target = self.get_map_key({})
2509
2528
self.assertIterInteresting([target],
2511
2530
[target], [basis])
2513
2532
def test_common_pages(self):
2514
basis = self.get_map_key({('a',): 'content',
2533
basis = self.get_map_key({(b'a',): b'content',
2534
(b'b',): b'content',
2535
(b'c',): b'content',
2518
target = self.get_map_key({('a',): 'content',
2519
('b',): 'other content',
2537
target = self.get_map_key({(b'a',): b'content',
2538
(b'b',): b'other content',
2539
(b'c',): b'content',
2522
2541
target_map = CHKMap(self.get_chk_bytes(), target)
2523
2542
self.assertEqualDiff(
2601
2620
" ('bbb',) 'new'\n",
2602
2621
target3_map._dump_tree())
2603
2622
aaa_key = target1_map._root_node.key()
2604
b_key = target2_map._root_node._items['b'].key()
2605
a_key = target3_map._root_node._items['a'].key()
2606
aac_key = target3_map._root_node._items['a']._items['aac'].key()
2623
b_key = target2_map._root_node._items[b'b'].key()
2624
a_key = target3_map._root_node._items[b'a'].key()
2625
aac_key = target3_map._root_node._items[b'a']._items[b'aac'].key()
2607
2626
self.assertIterInteresting(
2608
2627
[target1, target2, target3, a_key, aac_key, b_key],
2609
[(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
2628
[((b'aaa',), b'common'), ((b'bbb',), b'new'), ((b'aac',), b'other')],
2610
2629
[target1, target2, target3], [basis])
2612
2631
self.assertIterInteresting(
2613
2632
[target2, target3, a_key, aac_key, b_key],
2614
[(('bbb',), 'new'), (('aac',), 'other')],
2633
[((b'bbb',), b'new'), ((b'aac',), b'other')],
2615
2634
[target2, target3], [target1])
2617
2636
# Technically, target1 could be filtered out, but since it is a root
2744
2763
# Test behaviour
2745
2764
self.assertIterInteresting(
2746
2765
[right, left, l_d_key],
2747
[(('ddd',), 'change')],
2766
[((b'ddd',), b'change')],
2748
2767
[left, right], [basis])
2750
2769
def test_multiple_maps_similar(self):
2751
2770
# We want to have a depth=2 tree, with multiple entries in each leaf
2753
2772
basis = self.get_map_key({
2754
('aaa',): 'unchanged',
2755
('abb',): 'will change left',
2756
('caa',): 'unchanged',
2757
('cbb',): 'will change right',
2773
(b'aaa',): b'unchanged',
2774
(b'abb',): b'will change left',
2775
(b'caa',): b'unchanged',
2776
(b'cbb',): b'will change right',
2758
2777
}, maximum_size=60)
2759
2778
left = self.get_map_key({
2760
('aaa',): 'unchanged',
2761
('abb',): 'changed left',
2762
('caa',): 'unchanged',
2763
('cbb',): 'will change right',
2779
(b'aaa',): b'unchanged',
2780
(b'abb',): b'changed left',
2781
(b'caa',): b'unchanged',
2782
(b'cbb',): b'will change right',
2764
2783
}, maximum_size=60)
2765
2784
right = self.get_map_key({
2766
('aaa',): 'unchanged',
2767
('abb',): 'will change left',
2768
('caa',): 'unchanged',
2769
('cbb',): 'changed right',
2785
(b'aaa',): b'unchanged',
2786
(b'abb',): b'will change left',
2787
(b'caa',): b'unchanged',
2788
(b'cbb',): b'changed right',
2770
2789
}, maximum_size=60)
2771
2790
basis_map = CHKMap(self.get_chk_bytes(), basis)
2772
2791
self.assertEqualDiff(
added
removed
breezy/tests/test_chk_map.py
