1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
1
# Copyright (C) 2008-2011, 2016 Canonical Ltd
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
17
17
"""Tests for maps built on a CHK versionedfiles facility."""
19
from itertools import izip
28
from bzrlib.chk_map import (
28
from ..bzr.chk_map import (
34
from bzrlib.static_tuple import StaticTuple
34
from ..static_tuple import StaticTuple
37
37
class TestNode(tests.TestCase):
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
48
self.assertCommonPrefix('beg', 'beg', 'begin')
88
88
def read_bytes(self, chk_bytes, key):
89
89
stream = chk_bytes.get_record_stream([key], 'unordered', True)
90
record = stream.next()
91
91
if record.storage_kind == 'absent':
92
92
self.fail('Store does not contain the key %s' % (key,))
93
93
return record.get_bytes_as("fulltext")
226
226
" ('ddd',) 'initial ddd content'\n",
227
227
c_map._dump_tree())
229
def test_one_deep_map_16(self):
229
def test_root_only_aaa_ddd_16(self):
230
230
c_map = self.make_root_only_aaa_ddd_map(
231
231
search_key_func=chk_map._search_key_16)
232
232
# We use 'aaa' and 'ddd' because they happen to map to 'F' when using
380
380
# Leaf nodes must have identical contents
381
381
self.assertEqual(node_one._items, node_two._items)
382
self.assertEquals([], node_two_stack)
382
self.assertEqual([], node_two_stack)
384
384
def assertCanonicalForm(self, chkmap):
385
385
"""Assert that the chkmap is in 'canonical' form.
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(('small',), 'value')
479
chkmap.map(('little',), 'value')
480
chkmap.map(('very-big',), 'x' * 100)
481
# (Check that we have constructed the scenario we want to test)
482
self.assertIsInstance(chkmap._root_node, InternalNode)
483
# Delete the huge item so that the map fits in one node again.
484
delta = [(('very-big',), None, None)]
485
chkmap.apply_delta(delta)
486
self.assertCanonicalForm(chkmap)
487
self.assertIsInstance(chkmap._root_node, LeafNode)
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
1091
1110
basis_get = basis._store.get_record_stream
1092
1111
def get_record_stream(keys, order, fulltext):
1093
1112
if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
1094
self.fail("'aaa' pointer was followed %r" % 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)))
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",
1158
{("a", "a"):"content here", ("a", "b",):"more content",
1140
1159
("b", ""): 'boring content'},
1141
1160
maximum_size=10, key_width=2)
1142
1161
self.assertEqual(
1152
1171
self.assertEqual('71BEEFF9\x0000000000',
1153
1172
search_key_func(StaticTuple('b', '')))
1154
1173
chkmap = self._get_map(
1155
{("a","a"):"content here", ("a", "b",):"more content",
1174
{("a", "a"):"content here", ("a", "b",):"more content",
1156
1175
("b", ""): 'boring content'},
1157
1176
maximum_size=10, key_width=2, search_key_func=search_key_func)
1158
1177
self.assertEqual(
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",
1183
{("a", "a"):"content here", ("a", "b",):"more content",
1165
1184
("b", ""): 'boring content'}, key_width=2)
1166
1185
self.assertEqual(
1167
1186
{("a", "a"): "content here", ("a", "b"): 'more content'},
1567
1586
prefix, result = list(node.map(None, ("blue",), "red"))
1568
1587
self.assertEqual("", 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({"f", "b"}, split_chars)
1572
1591
nodes = dict(result)
1573
1592
node = nodes["f"]
1574
1593
self.assertEqual({("foo bar",): "baz quux"}, self.to_dict(node, None))
1874
1893
sorted(node.iteritems(None, [('strange',), ('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
1899
leaf1.map(None, StaticTuple('foo bar',), 'quux')
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
1926
prefix, nodes = node.map(None, ('k3',), 'quux')
1908
1927
self.assertEqual("k", prefix)
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.
2124
2143
c_map.map(('aaa',), '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)