/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/tests/test_chk_map.py

• browse files at revision 7143.15.2
• compare with another revision
• compare with revision 7492.1.1
• download diff
• download tarball
• view history from revision 7143.15.2

Show diffs side-by-side

added

removed

breezy/tests/test_chk_map.py

75

75

        if chk_bytes is None:

76

76

            chk_bytes = self.get_chk_bytes()

77

77

        root_key = CHKMap.from_dict(chk_bytes, a_dict,

78

 

            maximum_size=maximum_size, key_width=key_width,

79

 

            search_key_func=search_key_func)

 

78

                                    maximum_size=maximum_size, key_width=key_width,

 

79

                                    search_key_func=search_key_func)

80

80

        root_key2 = CHKMap._create_via_map(chk_bytes, a_dict,

81

 

            maximum_size=maximum_size, key_width=key_width,

82

 

            search_key_func=search_key_func)

 

81

                                           maximum_size=maximum_size, key_width=key_width,

 

82

                                           search_key_func=search_key_func)

83

83

        self.assertEqual(root_key, root_key2, "CHKMap.from_dict() did not"

84

84

                         " match CHKMap._create_via_map")

85

85

        chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)

228

228

 

229

229

    def test_root_only_aaa_ddd_16(self):

230

230

        c_map = self.make_root_only_aaa_ddd_map(

231

 

                search_key_func=chk_map._search_key_16)

 

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

233

233

        # _search_key_16

234

234

        self.assertEqualDiff(

349

349

    def assertHasEmptyMap(self, chk_bytes):

350

350

        empty_leaf_bytes = b'chkleaf:\n0\n1\n0\n\n'

351

351

        empty_sha1 = osutils.sha_string(empty_leaf_bytes)

352

 

        self.assertEqual(b'8571e09bf1bcc5b9621ce31b3d4c93d6e9a1ed26', empty_sha1)

 

352

        self.assertEqual(

 

353

            b'8571e09bf1bcc5b9621ce31b3d4c93d6e9a1ed26', empty_sha1)

353

354

        root_key = (b'sha1:' + empty_sha1,)

354

 

        self.assertEqual(empty_leaf_bytes, self.read_bytes(chk_bytes, root_key))

 

355

        self.assertEqual(empty_leaf_bytes,

 

356

                         self.read_bytes(chk_bytes, root_key))

355

357

        return root_key

356

358

 

357

359

    def assertMapLayoutEqual(self, map_one, map_two):

411

413

        self.assertMapLayoutEqual(map_one, map_two)

412

414

        map_one.map((b'aaa', ), b'value')

413

415

        self.assertRaises(AssertionError,

414

 

            self.assertMapLayoutEqual, map_one, map_two)

 

416

                          self.assertMapLayoutEqual, map_one, map_two)

415

417

        map_two.map((b'aaa', ), b'value')

416

418

        self.assertMapLayoutEqual(map_one, map_two)

417

419

        # Split the tree, so we ensure that internal nodes and leaf nodes are

419

421

        map_one.map((b'aab', ), b'value')

420

422

        self.assertIsInstance(map_one._root_node, InternalNode)

421

423

        self.assertRaises(AssertionError,

422

 

            self.assertMapLayoutEqual, map_one, map_two)

 

424

                          self.assertMapLayoutEqual, map_one, map_two)

423

425

        map_two.map((b'aab', ), b'value')

424

426

        self.assertMapLayoutEqual(map_one, map_two)

425

427

        map_one.map((b'aac', ), b'value')

426

428

        self.assertRaises(AssertionError,

427

 

            self.assertMapLayoutEqual, map_one, map_two)

 

429

                          self.assertMapLayoutEqual, map_one, map_two)

428

430

        self.assertCanonicalForm(map_one)

429

431

 

430

432

    def test_from_dict_empty(self):

459

461

        # applying a delta ("a", None, None) to a map with 'a' in it generates

460

462

        # an empty map.

461

463

        chk_bytes = self.get_chk_bytes()

462

 

        root_key = CHKMap.from_dict(chk_bytes, {(b"a",):b"b"})

 

464

        root_key = CHKMap.from_dict(chk_bytes, {(b"a",): b"b"})

463

465

        chkmap = CHKMap(chk_bytes, root_key)

464

466

        new_root = chkmap.apply_delta([((b"a",), None, None)])

465

467

        # Check the data was saved and inserted correctly.

492

494

        # applying a delta (None, "a", "b") to a map with 'a' in it generates

493

495

        # an error.

494

496

        chk_bytes = self.get_chk_bytes()

495

 

        root_key = CHKMap.from_dict(chk_bytes, {(b"a",):b"b"})

 

497

        root_key = CHKMap.from_dict(chk_bytes, {(b"a",): b"b"})

496

498

        chkmap = CHKMap(chk_bytes, root_key)

497

499

        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,

498

 

            [(None, (b"a",), b"b")])

 

500

                          [(None, (b"a",), b"b")])

499

501

        # As an error occured, the update should have left us without changing

500

502

        # anything (the root should be unchanged).

501

503

        self.assertEqual(root_key, chkmap._root_node._key)

1020

1022

            {(b'a',): b'content here', (b'b',): b'more content'},

1021

1023

            chk_bytes=basis._store, maximum_size=10)

1022

1024

        self.assertEqual([((b'a',), None, b'content here'),

1023

 

            ((b'b',), None, b'more content')],

1024

 

            sorted(list(target.iter_changes(basis))))

 

1025

                          ((b'b',), None, b'more content')],

 

1026

                         sorted(list(target.iter_changes(basis))))

1025

1027

 

1026

1028

    def test_iter_changes_ab_empty(self):

1027

1029

        # Asking for changes between a dict with keys to an empty dict returns

1028

1030

        # all the keys.

1029

1031

        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},

1030

 

            maximum_size=10)

 

1032

                              maximum_size=10)

1031

1033

        target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)

1032

1034

        self.assertEqual([((b'a',), b'content here', None),

1033

 

            ((b'b',), b'more content', None)],

1034

 

            sorted(list(target.iter_changes(basis))))

 

1035

                          ((b'b',), b'more content', None)],

 

1036

                         sorted(list(target.iter_changes(basis))))

1035

1037

 

1036

1038

    def test_iter_changes_empty_empty_is_empty(self):

1037

1039

        basis = self._get_map({}, maximum_size=10)

1040

1042

 

1041

1043

    def test_iter_changes_ab_ab_is_empty(self):

1042

1044

        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},

1043

 

            maximum_size=10)

 

1045

                              maximum_size=10)

1044

1046

        target = self._get_map(

1045

1047

            {(b'a',): b'content here', (b'b',): b'more content'},

1046

1048

            chk_bytes=basis._store, maximum_size=10)

1048

1050

 

1049

1051

    def test_iter_changes_ab_ab_nodes_not_loaded(self):

1050

1052

        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},

1051

 

            maximum_size=10)

 

1053

                              maximum_size=10)

1052

1054

        target = self._get_map(

1053

1055

            {(b'a',): b'content here', (b'b',): b'more content'},

1054

1056

            chk_bytes=basis._store, maximum_size=10)

1058

1060

 

1059

1061

    def test_iter_changes_ab_ab_changed_values_shown(self):

1060

1062

        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},

1061

 

            maximum_size=10)

 

1063

                              maximum_size=10)

1062

1064

        target = self._get_map(

1063

1065

            {(b'a',): b'content here', (b'b',): b'different content'},

1064

1066

            chk_bytes=basis._store, maximum_size=10)

1065

1067

        result = sorted(list(target.iter_changes(basis)))

1066

1068

        self.assertEqual([((b'b',), b'more content', b'different content')],

1067

 

            result)

 

1069

                         result)

1068

1070

 

1069

1071

    def test_iter_changes_mixed_node_length(self):

1070

1072

        # When one side has different node lengths than the other, common

1079

1081

        # aab, b, at to be returned.

1080

1082

        # basis splits at byte 0,1,2, aaa is commonb is basis only

1081

1083

        basis_dict = {(b'aaa',): b'foo bar',

1082

 

            (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

 

1084

                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

1083

1085

        # target splits at byte 1,2, at is target only

1084

1086

        target_dict = {(b'aaa',): b'foo bar',

1085

 

            (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

 

1087

                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

1086

1088

        changes = [

1087

1089

            ((b'aab',), b'common altered a', b'common altered b'),

1088

1090

            ((b'at',), None, b'foo bar t'),

1090

1092

            ]

1091

1093

        basis = self._get_map(basis_dict, maximum_size=10)

1092

1094

        target = self._get_map(target_dict, maximum_size=10,

1093

 

            chk_bytes=basis._store)

 

1095

                               chk_bytes=basis._store)

1094

1096

        self.assertEqual(changes, sorted(list(target.iter_changes(basis))))

1095

1097

 

1096

1098

    def test_iter_changes_common_pages_not_loaded(self):

1102

1104

        # aaa to be not loaded

1103

1105

        # aaa not to be in result.

1104

1106

        basis_dict = {(b'aaa',): b'foo bar',

1105

 

            (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

 

1107

                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

1106

1108

        # target splits at byte 1, at is target only

1107

1109

        target_dict = {(b'aaa',): b'foo bar',

1108

 

            (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

 

1110

                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

1109

1111

        basis = self._get_map(basis_dict, maximum_size=10)

1110

1112

        target = self._get_map(target_dict, maximum_size=10,

1111

 

            chk_bytes=basis._store)

 

1113

                               chk_bytes=basis._store)

1112

1114

        basis_get = basis._store.get_record_stream

 

1115

 

1113

1116

        def get_record_stream(keys, order, fulltext):

1114

1117

            if (b'sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:

1115

1118

                raise AssertionError("'aaa' pointer was followed %r" % keys)

1124

1127

        # Within a leaf there are no hash's to exclude keys, make sure multi

1125

1128

        # value leaf nodes are handled well.

1126

1129

        basis_dict = {(b'aaa',): b'foo bar',

1127

 

            (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

 

1130

                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}

1128

1131

        target_dict = {(b'aaa',): b'foo bar',

1129

 

            (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

 

1132

                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}

1130

1133

        changes = [

1131

1134

            ((b'aab',), b'common altered a', b'common altered b'),

1132

1135

            ((b'at',), None, b'foo bar t'),

1145

1148

    def test_iteritems_two_items(self):

1146

1149

        chk_bytes = self.get_chk_bytes()

1147

1150

        root_key = CHKMap.from_dict(chk_bytes,

1148

 

            {(b"a", ): b"content here", (b"b", ): b"more content"})

 

1151

                                    {(b"a", ): b"content here", (b"b", ): b"more content"})

1149

1152

        chkmap = CHKMap(chk_bytes, root_key)

1150

1153

        self.assertEqual([((b"a",), b"content here"), ((b"b",), b"more content")],

1151

 

            sorted(list(chkmap.iteritems())))

 

1154

                         sorted(list(chkmap.iteritems())))

1152

1155

 

1153

1156

    def test_iteritems_selected_one_of_two_items(self):

1154

 

        chkmap = self._get_map({(b"a",):b"content here", (b"b",):b"more content"})

 

1157

        chkmap = self._get_map(

 

1158

            {(b"a",): b"content here", (b"b",): b"more content"})

1155

1159

        self.assertEqual({(b"a",): b"content here"},

1156

 

            self.to_dict(chkmap, [(b"a",)]))

 

1160

                         self.to_dict(chkmap, [(b"a",)]))

1157

1161

 

1158

1162

    def test_iteritems_keys_prefixed_by_2_width_nodes(self):

1159

1163

        chkmap = self._get_map(

1160

 

            {(b"a", b"a"): b"content here", (b"a", b"b",):b"more content",

 

1164

            {(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",

1161

1165

             (b"b", b""): b'boring content'},

1162

1166

            maximum_size=10, key_width=2)

1163

1167

        self.assertEqual(

1182

1186

 

1183

1187

    def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):

1184

1188

        chkmap = self._get_map(

1185

 

            {(b"a", b"a"):b"content here", (b"a", b"b",): b"more content",

 

1189

            {(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",

1186

1190

             (b"b", b""): b'boring content'}, key_width=2)

1187

1191

        self.assertEqual(

1188

1192

            {(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},

1198

1202

 

1199

1203

    def test_max_size_100_bytes_new(self):

1200

1204

        # When there is a 100 byte upper node limit, a tree is formed.

1201

 

        chkmap = self._get_map({(b"k1"*50,):b"v1", (b"k2"*50,):b"v2"}, maximum_size=100)

 

1205

        chkmap = self._get_map(

 

1206

            {(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"}, maximum_size=100)

1202

1207

        # We expect three nodes:

1203

1208

        # A root, with two children, and with two key prefixes - k1 to one, and

1204

1209

        # k2 to the other as our node splitting is only just being developed.

1220

1225

        ptr2 = nodes[1]

1221

1226

        self.assertEqual(b'k1', ptr1[0])

1222

1227

        self.assertEqual(b'k2', ptr2[0])

1223

 

        node1 = chk_map._deserialise(chkmap._read_bytes(ptr1[1]), ptr1[1], None)

 

1228

        node1 = chk_map._deserialise(

 

1229

            chkmap._read_bytes(ptr1[1]), ptr1[1], None)

1224

1230

        self.assertIsInstance(node1, LeafNode)

1225

1231

        self.assertEqual(1, len(node1))

1226

 

        self.assertEqual({(b'k1'*50,): b'v1'}, self.to_dict(node1, chkmap._store))

1227

 

        node2 = chk_map._deserialise(chkmap._read_bytes(ptr2[1]), ptr2[1], None)

 

1232

        self.assertEqual({(b'k1' * 50,): b'v1'},

 

1233

                         self.to_dict(node1, chkmap._store))

 

1234

        node2 = chk_map._deserialise(

 

1235

            chkmap._read_bytes(ptr2[1]), ptr2[1], None)

1228

1236

        self.assertIsInstance(node2, LeafNode)

1229

1237

        self.assertEqual(1, len(node2))

1230

 

        self.assertEqual({(b'k2'*50,): b'v2'}, self.to_dict(node2, chkmap._store))

 

1238

        self.assertEqual({(b'k2' * 50,): b'v2'},

 

1239

                         self.to_dict(node2, chkmap._store))

1231

1240

        # Having checked we have a good structure, check that the content is

1232

1241

        # still accessible.

1233

1242

        self.assertEqual(2, len(chkmap))

1234

 

        self.assertEqual({(b"k1"*50,): b"v1", (b"k2"*50,): b"v2"},

1235

 

            self.to_dict(chkmap))

 

1243

        self.assertEqual({(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"},

 

1244

                         self.to_dict(chkmap))

1236

1245

 

1237

1246

    def test_init_root_is_LeafNode_new(self):

1238

1247

        chk_bytes = self.get_chk_bytes()

1260

1269

        self.assertEqual([key], leaf_node.serialise(chk_bytes))

1261

1270

 

1262

1271

    def test_unmap_last_item_root_is_leaf_new(self):

1263

 

        chkmap = self._get_map({(b"k1"*50,): b"v1", (b"k2"*50,): b"v2"})

1264

 

        chkmap.unmap((b"k1"*50,))

1265

 

        chkmap.unmap((b"k2"*50,))

 

1272

        chkmap = self._get_map({(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"})

 

1273

        chkmap.unmap((b"k1" * 50,))

 

1274

        chkmap.unmap((b"k2" * 50,))

1266

1275

        self.assertEqual(0, len(chkmap))

1267

1276

        self.assertEqual({}, self.to_dict(chkmap))

1268

1277

        key = chkmap._save()

1271

1280

 

1272

1281

    def test__dump_tree(self):

1273

1282

        chkmap = self._get_map({(b"aaa",): b"value1", (b"aab",): b"value2",

1274

 

                                (b"bbb",): b"value3",},

 

1283

                                (b"bbb",): b"value3", },

1275

1284

                               maximum_size=15)

1276

1285

        self.assertEqualDiff("'' InternalNode\n"

1277

1286

                             "  'a' InternalNode\n"

1333

1342

    """A search key function that maps all nodes to the same value"""

1334

1343

    return 'value'

1335

1344

 

 

1345

 

1336

1346

def _test_search_key(key):

1337

1347

    return b'test:' + b'\x00'.join(key)

1338

1348

 

1382

1392

                             "  'test:2' LeafNode\n"

1383

1393

                             "      ('2',) 'bar'\n"

1384

1394

                             "  'test:3' LeafNode\n"

1385

 

                             "      ('3',) 'baz'\n"

1386

 

                             , chkmap._dump_tree())

 

1395

                             "      ('3',) 'baz'\n", chkmap._dump_tree())

1387

1396

        root_key = chkmap._save()

1388

1397

        chkmap = chk_map.CHKMap(chk_bytes, root_key,

1389

1398

                                search_key_func=_test_search_key)

1393

1402

                             "  'test:2' LeafNode\n"

1394

1403

                             "      ('2',) 'bar'\n"

1395

1404

                             "  'test:3' LeafNode\n"

1396

 

                             "      ('3',) 'baz'\n"

1397

 

                             , chkmap._dump_tree())

 

1405

                             "      ('3',) 'baz'\n", chkmap._dump_tree())

1398

1406

 

1399

1407

    def test_search_key_16(self):

1400

1408

        chk_bytes = self.get_chk_bytes()

1410

1418

                             "  '6' LeafNode\n"

1411

1419

                             "      ('3',) 'baz'\n"

1412

1420

                             "  '8' LeafNode\n"

1413

 

                             "      ('1',) 'foo'\n"

1414

 

                             , chkmap._dump_tree())

 

1421

                             "      ('1',) 'foo'\n", chkmap._dump_tree())

1415

1422

        root_key = chkmap._save()

1416

1423

        chkmap = chk_map.CHKMap(chk_bytes, root_key,

1417

1424

                                search_key_func=chk_map._search_key_16)

1424

1431

                             "  '6' LeafNode\n"

1425

1432

                             "      ('3',) 'baz'\n"

1426

1433

                             "  '8' LeafNode\n"

1427

 

                             "      ('1',) 'foo'\n"

1428

 

                             , chkmap._dump_tree())

 

1434

                             "      ('1',) 'foo'\n", chkmap._dump_tree())

1429

1435

 

1430

1436

    def test_search_key_255(self):

1431

1437

        chk_bytes = self.get_chk_bytes()

1441

1447

                             "  'm' LeafNode\n"

1442

1448

                             "      ('3',) 'baz'\n"

1443

1449

                             "  '\\x83' LeafNode\n"

1444

 

                             "      ('1',) 'foo'\n"

1445

 

                             , chkmap._dump_tree(encoding='latin1'))

 

1450

                             "      ('1',) 'foo'\n", chkmap._dump_tree(encoding='latin1'))

1446

1451

        root_key = chkmap._save()

1447

1452

        chkmap = chk_map.CHKMap(chk_bytes, root_key,

1448

1453

                                search_key_func=chk_map._search_key_255)

1455

1460

                             "  'm' LeafNode\n"

1456

1461

                             "      ('3',) 'baz'\n"

1457

1462

                             "  '\\x83' LeafNode\n"

1458

 

                             "      ('1',) 'foo'\n"

1459

 

                             , chkmap._dump_tree(encoding='latin1'))

 

1463

                             "      ('1',) 'foo'\n", chkmap._dump_tree(encoding='latin1'))

1460

1464

 

1461

1465

    def test_search_key_collisions(self):

1462

1466

        chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,

1470

1474

        self.assertEqualDiff("'' LeafNode\n"

1471

1475

                             "      ('1',) 'foo'\n"

1472

1476

                             "      ('2',) 'bar'\n"

1473

 

                             "      ('3',) 'baz'\n"

1474

 

                             , chkmap._dump_tree())

 

1477

                             "      ('3',) 'baz'\n", chkmap._dump_tree())

1475

1478

 

1476

1479

 

1477

1480

class TestLeafNode(TestCaseWithStore):

1510

1513

            (b"sha1:1234",))

1511

1514

        self.assertEqual(2, len(node))

1512

1515

        self.assertEqual([((b"foo bar",), b"baz"), ((b"quux",), b"blarh")],

1513

 

            sorted(node.iteritems(None)))

 

1516

                         sorted(node.iteritems(None)))

1514

1517

 

1515

1518

    def test_deserialise_item_with_null_width_1(self):

1516

1519

        node = LeafNode.deserialise(

1518

1521

            (b"sha1:1234",))

1519

1522

        self.assertEqual(2, len(node))

1520

1523

        self.assertEqual([((b"foo",), b"bar\x00baz"), ((b"quux",), b"blarh")],

1521

 

            sorted(node.iteritems(None)))

 

1524

                         sorted(node.iteritems(None)))

1522

1525

 

1523

1526

    def test_deserialise_item_with_null_width_2(self):

1524

1527

        node = LeafNode.deserialise(

1527

1530

            (b"sha1:1234",))

1528

1531

        self.assertEqual(2, len(node))

1529

1532

        self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"quux", b""), b"blarh")],

1530

 

            sorted(node.iteritems(None)))

 

1533

                         sorted(node.iteritems(None)))

1531

1534

 

1532

1535

    def test_iteritems_selected_one_of_two_items(self):

1533

1536

        node = LeafNode.deserialise(

1535

1538

            (b"sha1:1234",))

1536

1539

        self.assertEqual(2, len(node))

1537

1540

        self.assertEqual([((b"quux",), b"blarh")],

1538

 

            sorted(node.iteritems(None, [(b"quux",), (b"qaz",)])))

 

1541

                         sorted(node.iteritems(None, [(b"quux",), (b"qaz",)])))

1539

1542

 

1540

1543

    def test_deserialise_item_with_common_prefix(self):

1541

1544

        node = LeafNode.deserialise(

1543

1546

            (b"sha1:1234",))

1544

1547

        self.assertEqual(2, len(node))

1545

1548

        self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"foo", b"2"), b"blarh")],

1546

 

            sorted(node.iteritems(None)))

 

1549

                         sorted(node.iteritems(None)))

1547

1550

        self.assertIs(chk_map._unknown, node._search_prefix)

1548

1551

        self.assertEqual(b'foo\x00', node._common_serialised_prefix)

1549

1552

 

1554

1557

        self.assertEqual(2, len(node))

1555

1558

        self.assertEqual([((b"foo", b"1"), b"bar\nbaz"),

1556

1559

                          ((b"foo", b"2"), b"blarh\n"),

1557

 

                         ], sorted(node.iteritems(None)))

 

1560

                          ], sorted(node.iteritems(None)))

1558

1561

        self.assertIs(chk_map._unknown, node._search_prefix)

1559

1562

        self.assertEqual(b'foo\x00', node._common_serialised_prefix)

1560

1563

 

1592

1595

        self.assertEqual({b"f", b"b"}, split_chars)

1593

1596

        nodes = dict(result)

1594

1597

        node = nodes[b"f"]

1595

 

        self.assertEqual({(b"foo bar",): b"baz quux"}, self.to_dict(node, None))

 

1598

        self.assertEqual({(b"foo bar",): b"baz quux"},

 

1599

                         self.to_dict(node, None))

1596

1600

        self.assertEqual(10, node.maximum_size)

1597

1601

        self.assertEqual(1, node._key_width)

1598

1602

        node = nodes[b"b"]

1604

1608

        node = LeafNode()

1605

1609

        result = node.map(None, (b"foo bar",), b"baz quux")

1606

1610

        self.assertEqual((b"foo bar", [(b"", node)]), result)

1607

 

        self.assertEqual({(b"foo bar",):b"baz quux"}, self.to_dict(node, None))

 

1611

        self.assertEqual({(b"foo bar",): b"baz quux"},

 

1612

                         self.to_dict(node, None))

1608

1613

        self.assertEqual(1, len(node))

1609

1614

 

1610

1615

    def test_map_second(self):

1613

1618

        result = node.map(None, (b"bingo",), b"bango")

1614

1619

        self.assertEqual((b"", [(b"", node)]), result)

1615

1620

        self.assertEqual({(b"foo bar",): b"baz quux", (b"bingo",): b"bango"},

1616

 

            self.to_dict(node, None))

 

1621

                         self.to_dict(node, None))

1617

1622

        self.assertEqual(2, len(node))

1618

1623

 

1619

1624

    def test_map_replacement(self):

1622

1627

        result = node.map(None, (b"foo bar",), b"bango")

1623

1628

        self.assertEqual((b"foo bar", [(b"", node)]), result)

1624

1629

        self.assertEqual({(b"foo bar",): b"bango"},

1625

 

            self.to_dict(node, None))

 

1630

                         self.to_dict(node, None))

1626

1631

        self.assertEqual(1, len(node))

1627

1632

 

1628

1633

    def test_serialise_empty(self):

1631

1636

        node.set_maximum_size(10)

1632

1637

        expected_key = (b"sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)

1633

1638

        self.assertEqual([expected_key],

1634

 

            list(node.serialise(store)))

1635

 

        self.assertEqual(b"chkleaf:\n10\n1\n0\n\n", self.read_bytes(store, expected_key))

 

1639

                         list(node.serialise(store)))

 

1640

        self.assertEqual(b"chkleaf:\n10\n1\n0\n\n",

 

1641

                         self.read_bytes(store, expected_key))

1636

1642

        self.assertEqual(expected_key, node.key())

1637

1643

 

1638

1644

    def test_serialise_items(self):

1643

1649

        expected_key = (b"sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)

1644

1650

        self.assertEqual(b'foo bar', node._common_serialised_prefix)

1645

1651

        self.assertEqual([expected_key],

1646

 

            list(node.serialise(store)))

 

1652

                         list(node.serialise(store)))

1647

1653

        self.assertEqual(b"chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",

1648

 

            self.read_bytes(store, expected_key))

 

1654

                         self.read_bytes(store, expected_key))

1649

1655

        self.assertEqual(expected_key, node.key())

1650

1656

 

1651

1657

    def test_unique_serialised_prefix_empty_new(self):

1878

1884

        node.add_node(b"f", leaf1)

1879

1885

        node.add_node(b"s", leaf2)

1880

1886

        self.assertEqual([((b'foo bar',), b'quux'), ((b'strange',), b'beast')],

1881

 

            sorted(node.iteritems(None)))

 

1887

                         sorted(node.iteritems(None)))

1882

1888

 

1883

1889

    def test_iteritems_two_children_partial(self):

1884

1890

        node = InternalNode()

1892

1898

        node._items[b'f'] = None

1893

1899

        node.add_node(b"s", leaf2)

1894

1900

        self.assertEqual([((b'strange',), b'beast')],

1895

 

            sorted(node.iteritems(None, [(b'strange',), (b'weird',)])))

 

1901

                         sorted(node.iteritems(None, [(b'strange',), (b'weird',)])))

1896

1902

 

1897

1903

    def test_iteritems_two_children_with_hash(self):

1898

1904

        search_key_func = chk_map.search_key_registry.get(b'hash-255-way')

1901

1907

        leaf1.map(None, StaticTuple(b'foo bar',), b'quux')

1902

1908

        leaf2 = LeafNode(search_key_func=search_key_func)

1903

1909

        leaf2.map(None, StaticTuple(b'strange',), b'beast')

1904

 

        self.assertEqual(b'\xbeF\x014', search_key_func(StaticTuple(b'foo bar',)))

1905

 

        self.assertEqual(b'\x85\xfa\xf7K', search_key_func(StaticTuple(b'strange',)))

 

1910

        self.assertEqual(b'\xbeF\x014', search_key_func(

 

1911

            StaticTuple(b'foo bar',)))

 

1912

        self.assertEqual(b'\x85\xfa\xf7K', search_key_func(

 

1913

            StaticTuple(b'strange',)))

1906

1914

        node.add_node(b"\xbe", leaf1)

1907

1915

        # This sets up a path that should not be followed - it will error if

1908

1916

        # the code tries to.

1909

1917

        node._items[b'\xbe'] = None

1910

1918

        node.add_node(b"\x85", leaf2)

1911

1919

        self.assertEqual([((b'strange',), b'beast')],

1912

 

            sorted(node.iteritems(None, [StaticTuple(b'strange',),

1913

 

                                         StaticTuple(b'weird',)])))

 

1920

                         sorted(node.iteritems(None, [StaticTuple(b'strange',),

 

1921

                                                      StaticTuple(b'weird',)])))

1914

1922

 

1915

1923

    def test_iteritems_partial_empty(self):

1916

1924

        node = InternalNode()

1917

1925

        self.assertEqual([], sorted(node.iteritems([(b'missing',)])))

1918

1926

 

1919

1927

    def test_map_to_new_child_new(self):

1920

 

        chkmap = self._get_map({(b'k1',): b'foo', (b'k2',): b'bar'}, maximum_size=10)

 

1928

        chkmap = self._get_map(

 

1929

            {(b'k1',): b'foo', (b'k2',): b'bar'}, maximum_size=10)

1921

1930

        chkmap._ensure_root()

1922

1931

        node = chkmap._root_node

1923

1932

        # Ensure test validity: nothing paged in below the root.

1924

1933

        self.assertEqual(2,

1925

 

            len([value for value in node._items.values()

1926

 

                if isinstance(value, StaticTuple)]))

 

1934

                         len([value for value in node._items.values()

 

1935

                              if isinstance(value, StaticTuple)]))

1927

1936

        # now, mapping to k3 should add a k3 leaf

1928

1937

        prefix, nodes = node.map(None, (b'k3',), b'quux')

1929

1938

        self.assertEqual(b"k", prefix)

1939

1948

        # Check overall structure:

1940

1949

        self.assertEqual(3, len(chkmap))

1941

1950

        self.assertEqual({(b'k1',): b'foo', (b'k2',): b'bar', (b'k3',): b'quux'},

1942

 

            self.to_dict(chkmap))

 

1951

                         self.to_dict(chkmap))

1943

1952

        # serialising should only serialise the new data - k3 and the internal

1944

1953

        # node.

1945

1954

        keys = list(node.serialise(chkmap._store))

1947

1956

        self.assertEqual([child_key, keys[1]], keys)

1948

1957

 

1949

1958

    def test_map_to_child_child_splits_new(self):

1950

 

        chkmap = self._get_map({(b'k1',): b'foo', (b'k22',): b'bar'}, maximum_size=10)

 

1959

        chkmap = self._get_map(

 

1960

            {(b'k1',): b'foo', (b'k22',): b'bar'}, maximum_size=10)

1951

1961

        # Check for the canonical root value for this tree:

1952

1962

        self.assertEqualDiff("'' InternalNode\n"

1953

1963

                             "  'k1' LeafNode\n"

1954

1964

                             "      ('k1',) 'foo'\n"

1955

1965

                             "  'k2' LeafNode\n"

1956

 

                             "      ('k22',) 'bar'\n"

1957

 

                             , chkmap._dump_tree())

 

1966

                             "      ('k22',) 'bar'\n", chkmap._dump_tree())

1958

1967

        # _dump_tree pages everything in, so reload using just the root

1959

1968

        chkmap = CHKMap(chkmap._store, chkmap._root_node)

1960

1969

        chkmap._ensure_root()

1961

1970

        node = chkmap._root_node

1962

1971

        # Ensure test validity: nothing paged in below the root.

1963

1972

        self.assertEqual(2,

1964

 

            len([value for value in node._items.values()

1965

 

                if isinstance(value, StaticTuple)]))

 

1973

                         len([value for value in node._items.values()

 

1974

                              if isinstance(value, StaticTuple)]))

1966

1975

        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and

1967

1976

        # k23, which for simplicity in the current implementation generates

1968

1977

        # a new internal node between node, and k22/k23.

1974

1983

        self.assertIsInstance(child, InternalNode)

1975

1984

        self.assertEqual(2, len(child))

1976

1985

        self.assertEqual({(b'k22',): b'bar', (b'k23',): b'quux'},

1977

 

            self.to_dict(child, None))

 

1986

                         self.to_dict(child, None))

1978

1987

        self.assertEqual(None, child._key)

1979

1988

        self.assertEqual(10, child.maximum_size)

1980

1989

        self.assertEqual(1, child._key_width)

1982

1991

        # Check overall structure:

1983

1992

        self.assertEqual(3, len(chkmap))

1984

1993

        self.assertEqual({(b'k1',): b'foo', (b'k22',): b'bar', (b'k23',): b'quux'},

1985

 

            self.to_dict(chkmap))

 

1994

                         self.to_dict(chkmap))

1986

1995

        # serialising should only serialise the new data - although k22 hasn't

1987

1996

        # changed because its a special corner case (splitting on with only one

1988

1997

        # key leaves one node unaltered), in general k22 is serialised, so we

1999

2008

                             "    'k22' LeafNode\n"

2000

2009

                             "      ('k22',) 'bar'\n"

2001

2010

                             "    'k23' LeafNode\n"

2002

 

                             "      ('k23',) 'quux'\n"

2003

 

                             , chkmap._dump_tree())

 

2011

                             "      ('k23',) 'quux'\n", chkmap._dump_tree())

2004

2012

 

2005

2013

    def test__search_prefix_filter_with_hash(self):

2006

2014

        search_key_func = chk_map.search_key_registry.get(b'hash-16-way')

2025

2033

                             "    'k22' LeafNode\n"

2026

2034

                             "      ('k22',) 'bar'\n"

2027

2035

                             "    'k23' LeafNode\n"

2028

 

                             "      ('k23',) 'quux'\n"

2029

 

                             , chkmap._dump_tree())

 

2036

                             "      ('k23',) 'quux'\n", chkmap._dump_tree())

2030

2037

        chkmap = CHKMap(chkmap._store, chkmap._root_node)

2031

2038

        chkmap._ensure_root()

2032

2039

        node = chkmap._root_node

2039

2046

        self.assertIsInstance(child, LeafNode)

2040

2047

        self.assertEqual(1, len(child))

2041

2048

        self.assertEqual({(b'k22',): b'bar'},

2042

 

            self.to_dict(child, None))

 

2049

                         self.to_dict(child, None))

2043

2050

        # Check overall structure is instact:

2044

2051

        self.assertEqual(2, len(chkmap))

2045

2052

        self.assertEqual({(b'k1',): b'foo', (b'k22',): b'bar'},

2046

 

            self.to_dict(chkmap))

 

2053

                         self.to_dict(chkmap))

2047

2054

        # serialising should only serialise the new data - the root node.

2048

2055

        keys = list(node.serialise(chkmap._store))

2049

2056

        self.assertEqual([keys[-1]], keys)

2052

2059

                             "  'k1' LeafNode\n"

2053

2060

                             "      ('k1',) 'foo'\n"

2054

2061

                             "  'k2' LeafNode\n"

2055

 

                             "      ('k22',) 'bar'\n"

2056

 

                             , chkmap._dump_tree())

 

2062

                             "      ('k22',) 'bar'\n", chkmap._dump_tree())

2057

2063

 

2058

2064

    def test_unmap_k1_from_k1_k22_k23_gives_k22_k23_tree_new(self):

2059

2065

        chkmap = self._get_map(

2065

2071

                             "    'k22' LeafNode\n"

2066

2072

                             "      ('k22',) 'bar'\n"

2067

2073

                             "    'k23' LeafNode\n"

2068

 

                             "      ('k23',) 'quux'\n"

2069

 

                             , chkmap._dump_tree())

 

2074

                             "      ('k23',) 'quux'\n", chkmap._dump_tree())

2070

2075

        orig_root = chkmap._root_node

2071

2076

        chkmap = CHKMap(chkmap._store, orig_root)

2072

2077

        chkmap._ensure_root()

2084

2089

                             "  'k22' LeafNode\n"

2085

2090

                             "      ('k22',) 'bar'\n"

2086

2091

                             "  'k23' LeafNode\n"

2087

 

                             "      ('k23',) 'quux'\n"

2088

 

                             , chkmap._dump_tree())

 

2092

                             "      ('k23',) 'quux'\n", chkmap._dump_tree())

2089

2093

 

2090

2094

 

2091

2095

# leaf:

2137

2141

        if search_key_func is None:

2138

2142

            search_key_func = chk_map._search_key_plain

2139

2143

        return chk_map.CHKMapDifference(self.get_chk_bytes(),

2140

 

            new_roots, old_roots, search_key_func)

 

2144

                                        new_roots, old_roots, search_key_func)

2141

2145

 

2142

2146

    def test__init__(self):

2143

2147

        c_map = self.make_root_only_map()

2186

2190

    def test__read_all_roots_prepares_queues(self):

2187

2191

        c_map = self.make_one_deep_map(chk_map._search_key_plain)

2188

2192

        key1 = c_map.key()

2189

 

        c_map._dump_tree() # load everything

 

2193

        c_map._dump_tree()  # load everything

2190

2194

        key1_a = c_map._root_node._items[b'a'].key()

2191

2195

        c_map.map((b'abb',), b'new abb content')

2192

2196

        key2 = c_map._save()

2203

2207

    def test__read_all_roots_multi_new_prepares_queues(self):

2204

2208

        c_map = self.make_one_deep_map(chk_map._search_key_plain)

2205

2209

        key1 = c_map.key()

2206

 

        c_map._dump_tree() # load everything

 

2210

        c_map._dump_tree()  # load everything

2207

2211

        key1_a = c_map._root_node._items[b'a'].key()

2208

2212

        key1_c = c_map._root_node._items[b'c'].key()

2209

2213

        c_map.map((b'abb',), b'new abb content')

2228

2232

 

2229

2233

    def test__read_all_roots_different_depths(self):

2230

2234

        c_map = self.make_two_deep_map(chk_map._search_key_plain)

2231

 

        c_map._dump_tree() # load everything

 

2235

        c_map._dump_tree()  # load everything

2232

2236

        key1 = c_map.key()

2233

2237

        key1_a = c_map._root_node._items[b'a'].key()

2234

2238

        key1_c = c_map._root_node._items[b'c'].key()

2259

2263

 

2260

2264

    def test__read_all_roots_different_depths_16(self):

2261

2265

        c_map = self.make_two_deep_map(chk_map._search_key_16)

2262

 

        c_map._dump_tree() # load everything

 

2266

        c_map._dump_tree()  # load everything

2263

2267

        key1 = c_map.key()

2264

2268

        key1_2 = c_map._root_node._items[b'2'].key()

2265

2269

        key1_4 = c_map._root_node._items[b'4'].key()

2295

2299

 

2296

2300

    def test__read_all_roots_mixed_depth(self):

2297

2301

        c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)

2298

 

        c_map._dump_tree() # load everything

 

2302

        c_map._dump_tree()  # load everything

2299

2303

        key1 = c_map.key()

2300

2304

        key1_aa = c_map._root_node._items[b'aa'].key()

2301

2305

        key1_ad = c_map._root_node._items[b'ad'].key()

2339

2343

        # This allows us to yield a root node record immediately, without any

2340

2344

        # buffering.

2341

2345

        c_map = self.make_two_deep_map(chk_map._search_key_plain)

2342

 

        c_map._dump_tree() # load all keys

 

2346

        c_map._dump_tree()  # load all keys

2343

2347

        key1 = c_map.key()

2344

2348

        key1_a = c_map._root_node._items[b'a'].key()

2345

2349

        c_map2 = self.get_map({

2361

2365

        self.assertEqual([key1_a], diff._old_queue)

2362

2366

        self.assertEqual({((b'acc',), b'initial acc content'),

2363

2367

                          ((b'ace',), b'initial ace content'),

2364

 

                         }, set(diff._new_item_queue))

 

2368

                          }, set(diff._new_item_queue))

2365

2369

 

2366

2370

    def test__read_all_roots_multiple_targets(self):

2367

2371

        c_map = self.make_root_only_map()

2431

2435

    def test__read_all_roots_multiple_old(self):

2432

2436

        c_map = self.make_two_deep_map()

2433

2437

        key1 = c_map.key()

2434

 

        c_map._dump_tree() # load everything

 

2438

        c_map._dump_tree()  # load everything

2435

2439

        key1_a = c_map._root_node._items[b'a'].key()

2436

2440

        c_map.map((b'ccc',), b'new ccc value')

2437

2441

        key2 = c_map._save()

2452

2456

    def test__process_next_old_batched_no_dupes(self):

2453

2457

        c_map = self.make_two_deep_map()

2454

2458

        key1 = c_map.key()

2455

 

        c_map._dump_tree() # load everything

 

2459

        c_map._dump_tree()  # load everything

2456

2460

        key1_a = c_map._root_node._items[b'a'].key()

2457

2461

        key1_aa = c_map._root_node._items[b'a']._items[b'aa'].key()

2458

2462

        key1_ab = c_map._root_node._items[b'a']._items[b'ab'].key()

2535

2539

        basis = self.get_map_key({(b'a',): b'content',

2536

2540

                                  (b'b',): b'content',

2537

2541

                                  (b'c',): b'content',

2538

 

                                 })

 

2542

                                  })

2539

2543

        target = self.get_map_key({(b'a',): b'content',

2540

2544

                                   (b'b',): b'other content',

2541

2545

                                   (b'c',): b'content',

2542

 

                                  })

 

2546

                                   })

2543

2547

        target_map = CHKMap(self.get_chk_bytes(), target)

2544

2548

        self.assertEqualDiff(

2545

2549

            "'' InternalNode\n"

2559

2563

    def test_common_sub_page(self):

2560

2564

        basis = self.get_map_key({(b'aaa',): b'common',

2561

2565

                                  (b'c',): b'common',

2562

 

                                 })

 

2566

                                  })

2563

2567

        target = self.get_map_key({(b'aaa',): b'common',

2564

2568

                                   (b'aab',): b'new',

2565

2569

                                   (b'c',): b'common',

2566

 

                                  })

 

2570

                                   })

2567

2571

        target_map = CHKMap(self.get_chk_bytes(), target)

2568

2572

        self.assertEqualDiff(

2569

2573

            "'' InternalNode\n"

2589

2593

        target1 = self.get_map_key({(b'aaa',): b'common'})

2590

2594

        target2 = self.get_map_key({(b'aaa',): b'common',

2591

2595

                                    (b'bbb',): b'new',

2592

 

                                   })

 

2596

                                    })

2593

2597

        target3 = self.get_map_key({(b'aaa',): b'common',

2594

2598

                                    (b'aac',): b'other',

2595

2599

                                    (b'bbb',): b'new',

2596

 

                                   })

 

2600

                                    })

2597

2601

        # The LeafNode containing 'aaa': 'common' occurs at 3 different levels.

2598

2602

        # Once as a root node, once as a second layer, and once as a third

2599

2603

        # layer. It should only be returned one time regardless

2646

2650

    def test_multiple_maps(self):

2647

2651

        basis1 = self.get_map_key({(b'aaa',): b'common',

2648

2652

                                   (b'aab',): b'basis1',

2649

 

                                  })

 

2653

                                   })

2650

2654

        basis2 = self.get_map_key({(b'bbb',): b'common',

2651

2655

                                   (b'bbc',): b'basis2',

2652

 

                                  })

 

2656

                                   })

2653

2657

        target1 = self.get_map_key({(b'aaa',): b'common',

2654

2658

                                    (b'aac',): b'target1',

2655

2659

                                    (b'bbb',): b'common',

2656

 

                                   })

 

2660

                                    })

2657

2661

        target2 = self.get_map_key({(b'aaa',): b'common',

2658

2662

                                    (b'bba',): b'target2',

2659

2663

                                    (b'bbb',): b'common',

2660

 

                                   })

 

2664

                                    })

2661

2665

        target1_map = CHKMap(self.get_chk_bytes(), target1)

2662

2666

        self.assertEqualDiff(

2663

2667

            "'' InternalNode\n"

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0