~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

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

• reverse the comparison (3823.3.2 to 5076.4.6)
• stop comparing with revision 5076.4.6

Show diffs side-by-side

added

removed

bzrlib/tests/test_index.py

1

 

# Copyright (C) 2007-2010 Canonical Ltd

 

1

# Copyright (C) 2007 Canonical Ltd

2

2

#

3

3

# This program is free software; you can redistribute it and/or modify

4

4

# it under the terms of the GNU General Public License as published by

12

12

#

13

13

# You should have received a copy of the GNU General Public License

14

14

# along with this program; if not, write to the Free Software

15

 

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

 

15

# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

16

16

 

17

17

"""Tests for indices."""

18

18

 

173

173

            "key\x00\x00\t\x00data\n"

174

174

            "\n", contents)

175

175

 

176

 

    def test_clear_cache(self):

177

 

        builder = GraphIndexBuilder(reference_lists=2)

178

 

        # This is a no-op, but the api should exist

179

 

        builder.clear_cache()

180

 

 

181

176

    def test_node_references_are_byte_offsets(self):

182

177

        builder = GraphIndexBuilder(reference_lists=1)

183

178

        builder.add_node(('reference', ), 'data', ([], ))

235

230

        builder.add_node(('2-key', ), '', (references, ))

236

231

        stream = builder.finish()

237

232

        contents = stream.read()

238

 

        self.assertEqualDiff(

 

233

        self.assertEqual(

239

234

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"

240

235

            "0\x00a\x00\x00\n"

241

236

            "1\x00a\x00\x00\n"

388

383

        size = trans.put_file('index', stream)

389

384

        return GraphIndex(trans, 'index', size)

390

385

 

391

 

    def test_clear_cache(self):

392

 

        index = self.make_index()

393

 

        # For now, we just want to make sure the api is available. As this is

394

 

        # old code, we don't really worry if it *does* anything.

395

 

        index.clear_cache()

396

 

 

397

386

    def test_open_bad_index_no_error(self):

398

387

        trans = self.get_transport()

399

388

        trans.put_bytes('name', "not an index\n")

569

558

        # not create a new transport request, and should return False (cannot

570

559

        # be in the index) - even when the byte location we ask for is outside

571

560

        # the parsed region

572

 

        #

 

561

        # 

573

562

        result = index._lookup_keys_via_location([(4000, self.make_key(40))])

574

563

        self.assertEqual(

575

564

            [((4000, self.make_key(40)),

933

922

        index = self.make_index(nodes=[(('key', ), 'value', ())])

934

923

        index.validate()

935

924

 

936

 

    # XXX: external_references tests are duplicated in test_btree_index.  We

937

 

    # probably should have per_graph_index tests...

938

 

    def test_external_references_no_refs(self):

939

 

        index = self.make_index(ref_lists=0, nodes=[])

940

 

        self.assertRaises(ValueError, index.external_references, 0)

941

 

 

942

 

    def test_external_references_no_results(self):

943

 

        index = self.make_index(ref_lists=1, nodes=[

944

 

            (('key',), 'value', ([],))])

945

 

        self.assertEqual(set(), index.external_references(0))

946

 

 

947

 

    def test_external_references_missing_ref(self):

948

 

        missing_key = ('missing',)

949

 

        index = self.make_index(ref_lists=1, nodes=[

950

 

            (('key',), 'value', ([missing_key],))])

951

 

        self.assertEqual(set([missing_key]), index.external_references(0))

952

 

 

953

 

    def test_external_references_multiple_ref_lists(self):

954

 

        missing_key = ('missing',)

955

 

        index = self.make_index(ref_lists=2, nodes=[

956

 

            (('key',), 'value', ([], [missing_key]))])

957

 

        self.assertEqual(set([]), index.external_references(0))

958

 

        self.assertEqual(set([missing_key]), index.external_references(1))

959

 

 

960

 

    def test_external_references_two_records(self):

961

 

        index = self.make_index(ref_lists=1, nodes=[

962

 

            (('key-1',), 'value', ([('key-2',)],)),

963

 

            (('key-2',), 'value', ([],)),

964

 

            ])

965

 

        self.assertEqual(set([]), index.external_references(0))

966

 

 

967

 

    def test__find_ancestors(self):

968

 

        key1 = ('key-1',)

969

 

        key2 = ('key-2',)

970

 

        index = self.make_index(ref_lists=1, key_elements=1, nodes=[

971

 

            (key1, 'value', ([key2],)),

972

 

            (key2, 'value', ([],)),

973

 

            ])

974

 

        parent_map = {}

975

 

        missing_keys = set()

976

 

        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)

977

 

        self.assertEqual({key1: (key2,)}, parent_map)

978

 

        self.assertEqual(set(), missing_keys)

979

 

        self.assertEqual(set([key2]), search_keys)

980

 

        search_keys = index._find_ancestors(search_keys, 0, parent_map,

981

 

                                            missing_keys)

982

 

        self.assertEqual({key1: (key2,), key2: ()}, parent_map)

983

 

        self.assertEqual(set(), missing_keys)

984

 

        self.assertEqual(set(), search_keys)

985

 

 

986

 

    def test__find_ancestors_w_missing(self):

987

 

        key1 = ('key-1',)

988

 

        key2 = ('key-2',)

989

 

        key3 = ('key-3',)

990

 

        index = self.make_index(ref_lists=1, key_elements=1, nodes=[

991

 

            (key1, 'value', ([key2],)),

992

 

            (key2, 'value', ([],)),

993

 

            ])

994

 

        parent_map = {}

995

 

        missing_keys = set()

996

 

        search_keys = index._find_ancestors([key2, key3], 0, parent_map,

997

 

                                            missing_keys)

998

 

        self.assertEqual({key2: ()}, parent_map)

999

 

        self.assertEqual(set([key3]), missing_keys)

1000

 

        self.assertEqual(set(), search_keys)

1001

 

 

1002

 

    def test__find_ancestors_dont_search_known(self):

1003

 

        key1 = ('key-1',)

1004

 

        key2 = ('key-2',)

1005

 

        key3 = ('key-3',)

1006

 

        index = self.make_index(ref_lists=1, key_elements=1, nodes=[

1007

 

            (key1, 'value', ([key2],)),

1008

 

            (key2, 'value', ([key3],)),

1009

 

            (key3, 'value', ([],)),

1010

 

            ])

1011

 

        # We already know about key2, so we won't try to search for key3

1012

 

        parent_map = {key2: (key3,)}

1013

 

        missing_keys = set()

1014

 

        search_keys = index._find_ancestors([key1], 0, parent_map,

1015

 

                                            missing_keys)

1016

 

        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)

1017

 

        self.assertEqual(set(), missing_keys)

1018

 

        self.assertEqual(set(), search_keys)

1019

 

 

1020

 

    def test_supports_unlimited_cache(self):

1021

 

        builder = GraphIndexBuilder(0, key_elements=1)

1022

 

        stream = builder.finish()

1023

 

        trans = get_transport(self.get_url())

1024

 

        size = trans.put_file('index', stream)

1025

 

        # It doesn't matter what unlimited_cache does here, just that it can be

1026

 

        # passed

1027

 

        index = GraphIndex(trans, 'index', size, unlimited_cache=True)

1028

 

 

1029

925

 

1030

926

class TestCombinedGraphIndex(TestCaseWithMemoryTransport):

1031

927

 

1082

978

        index.insert_index(0, index1)

1083

979

        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))

1084

980

 

1085

 

    def test_clear_cache(self):

1086

 

        log = []

1087

 

 

1088

 

        class ClearCacheProxy(object):

1089

 

 

1090

 

            def __init__(self, index):

1091

 

                self._index = index

1092

 

 

1093

 

            def __getattr__(self, name):

1094

 

                return getattr(self._index)

1095

 

 

1096

 

            def clear_cache(self):

1097

 

                log.append(self._index)

1098

 

                return self._index.clear_cache()

1099

 

 

1100

 

        index = CombinedGraphIndex([])

1101

 

        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])

1102

 

        index.insert_index(0, ClearCacheProxy(index1))

1103

 

        index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])

1104

 

        index.insert_index(1, ClearCacheProxy(index2))

1105

 

        # CombinedGraphIndex should call 'clear_cache()' on all children

1106

 

        index.clear_cache()

1107

 

        self.assertEqual(sorted([index1, index2]), sorted(log))

1108

 

 

1109

981

    def test_iter_all_entries_empty(self):

1110

982

        index = CombinedGraphIndex([])

1111

983

        self.assertEqual([], list(index.iter_all_entries()))

1175

1047

        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),

1176

1048

            (index2, ('ref', ), 'refdata', ((), ))]),

1177

1049

            set(index.iter_entries([('name', ), ('ref', )])))

1178

 

 

 

1050

 

1179

1051

    def test_iter_all_keys_dup_entry(self):

1180

1052

        index1 = self.make_index('1', 1, nodes=[

1181

1053

            (('name', ), 'data', ([('ref', )], )),

1186

1058

        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),

1187

1059

            (index1, ('ref', ), 'refdata', ((), ))]),

1188

1060

            set(index.iter_entries([('name', ), ('ref', )])))

1189

 

 

 

1061

 

1190

1062

    def test_iter_missing_entry_empty(self):

1191

1063

        index = CombinedGraphIndex([])

1192

1064

        self.assertEqual([], list(index.iter_entries([('a', )])))

1201

1073

        index2 = self.make_index('2')

1202

1074

        index = CombinedGraphIndex([index1, index2])

1203

1075

        self.assertEqual([], list(index.iter_entries([('a', )])))

1204

 

 

 

1076

 

1205

1077

    def test_iter_entry_present_one_index_only(self):

1206

1078

        index1 = self.make_index('1', nodes=[(('key', ), '', ())])

1207

1079

        index2 = self.make_index('2', nodes=[])

1368

1240

                                    ['1', '2', '3'])

1369

1241

        self.assertRaises(errors.NoSuchFile, index.validate)

1370

1242

 

1371

 

    def test_find_ancestors_across_indexes(self):

1372

 

        key1 = ('key-1',)

1373

 

        key2 = ('key-2',)

1374

 

        key3 = ('key-3',)

1375

 

        key4 = ('key-4',)

1376

 

        index1 = self.make_index('12', ref_lists=1, nodes=[

1377

 

            (key1, 'value', ([],)),

1378

 

            (key2, 'value', ([key1],)),

1379

 

            ])

1380

 

        index2 = self.make_index('34', ref_lists=1, nodes=[

1381

 

            (key3, 'value', ([key2],)),

1382

 

            (key4, 'value', ([key3],)),

1383

 

            ])

1384

 

        c_index = CombinedGraphIndex([index1, index2])

1385

 

        parent_map, missing_keys = c_index.find_ancestry([key1], 0)

1386

 

        self.assertEqual({key1: ()}, parent_map)

1387

 

        self.assertEqual(set(), missing_keys)

1388

 

        # Now look for a key from index2 which requires us to find the key in

1389

 

        # the second index, and then continue searching for parents in the

1390

 

        # first index

1391

 

        parent_map, missing_keys = c_index.find_ancestry([key3], 0)

1392

 

        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)

1393

 

        self.assertEqual(set(), missing_keys)

1394

 

 

1395

 

    def test_find_ancestors_missing_keys(self):

1396

 

        key1 = ('key-1',)

1397

 

        key2 = ('key-2',)

1398

 

        key3 = ('key-3',)

1399

 

        key4 = ('key-4',)

1400

 

        index1 = self.make_index('12', ref_lists=1, nodes=[

1401

 

            (key1, 'value', ([],)),

1402

 

            (key2, 'value', ([key1],)),

1403

 

            ])

1404

 

        index2 = self.make_index('34', ref_lists=1, nodes=[

1405

 

            (key3, 'value', ([key2],)),

1406

 

            ])

1407

 

        c_index = CombinedGraphIndex([index1, index2])

1408

 

        # Searching for a key which is actually not present at all should

1409

 

        # eventually converge

1410

 

        parent_map, missing_keys = c_index.find_ancestry([key4], 0)

1411

 

        self.assertEqual({}, parent_map)

1412

 

        self.assertEqual(set([key4]), missing_keys)

1413

 

 

1414

 

    def test_find_ancestors_no_indexes(self):

1415

 

        c_index = CombinedGraphIndex([])

1416

 

        key1 = ('key-1',)

1417

 

        parent_map, missing_keys = c_index.find_ancestry([key1], 0)

1418

 

        self.assertEqual({}, parent_map)

1419

 

        self.assertEqual(set([key1]), missing_keys)

1420

 

 

1421

 

    def test_find_ancestors_ghost_parent(self):

1422

 

        key1 = ('key-1',)

1423

 

        key2 = ('key-2',)

1424

 

        key3 = ('key-3',)

1425

 

        key4 = ('key-4',)

1426

 

        index1 = self.make_index('12', ref_lists=1, nodes=[

1427

 

            (key1, 'value', ([],)),

1428

 

            (key2, 'value', ([key1],)),

1429

 

            ])

1430

 

        index2 = self.make_index('34', ref_lists=1, nodes=[

1431

 

            (key4, 'value', ([key2, key3],)),

1432

 

            ])

1433

 

        c_index = CombinedGraphIndex([index1, index2])

1434

 

        # Searching for a key which is actually not present at all should

1435

 

        # eventually converge

1436

 

        parent_map, missing_keys = c_index.find_ancestry([key4], 0)

1437

 

        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},

1438

 

                         parent_map)

1439

 

        self.assertEqual(set([key3]), missing_keys)

1440

 

 

1441

 

    def test__find_ancestors_empty_index(self):

1442

 

        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])

1443

 

        parent_map = {}

1444

 

        missing_keys = set()

1445

 

        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,

1446

 

                                            missing_keys)

1447

 

        self.assertEqual(set(), search_keys)

1448

 

        self.assertEqual({}, parent_map)

1449

 

        self.assertEqual(set([('one',), ('two',)]), missing_keys)

1450

 

 

1451

1243

 

1452

1244

class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):

1453

1245

 

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1