/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

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

Show diffs side-by-side

added

removed

bzrlib/tests/test_graph.py

283

283

#     |/

284

284

#     j

285

285

#

286

 

# y is found to be common right away, but is the start of a long series of

 

286

# x is found to be common right away, but is the start of a long series of

287

287

# common commits.

288

288

# o is actually common, but the i-j shortcut makes it look like it is actually

289

 

# unique to j at first, you have to traverse all of y->o to find it.

290

 

# q,n give the walker from j a common point to stop searching, as does p,f.

 

289

# unique to j at first, you have to traverse all of x->o to find it.

 

290

# q,m gives the walker from j a common point to stop searching, as does p,f.

291

291

# k-n exists so that the second pass still has nodes that are worth searching,

292

292

# rather than instantly cancelling the extra walker.

293

293

 

396

396

with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],

397

397

              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}

398

398

 

 

399

# A graph that shows we can shortcut finding revnos when reaching them from the

 

400

# side.

 

401

#  NULL_REVISION

 

402

#       |

 

403

#       a

 

404

#       |

 

405

#       b

 

406

#       |

 

407

#       c

 

408

#       |

 

409

#       d

 

410

#       |

 

411

#       e

 

412

#      / \

 

413

#     f   g

 

414

#     |

 

415

#     h

 

416

#     |

 

417

#     i

 

418

 

 

419

with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],

 

420

             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}

399

421

 

400

422

 

401

423

class InstrumentedParentsProvider(object):

409

431

        return self._real_parents_provider.get_parent_map(nodes)

410

432

 

411

433

 

 

434

class TestGraphBase(tests.TestCase):

 

435

 

 

436

    def make_graph(self, ancestors):

 

437

        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))

 

438

 

 

439

    def make_breaking_graph(self, ancestors, break_on):

 

440

        """Make a Graph that raises an exception if we hit a node."""

 

441

        g = self.make_graph(ancestors)

 

442

        orig_parent_map = g.get_parent_map

 

443

        def get_parent_map(keys):

 

444

            bad_keys = set(keys).intersection(break_on)

 

445

            if bad_keys:

 

446

                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))

 

447

            return orig_parent_map(keys)

 

448

        g.get_parent_map = get_parent_map

 

449

        return g

 

450

 

 

451

 

412

452

class TestGraph(TestCaseWithMemoryTransport):

413

453

 

414

454

    def make_graph(self, ancestors):

1138

1178

        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())

1139

1179

 

1140

1180

 

1141

 

class TestFindUniqueAncestors(tests.TestCase):

1142

 

 

1143

 

    def make_graph(self, ancestors):

1144

 

        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))

1145

 

 

1146

 

    def make_breaking_graph(self, ancestors, break_on):

1147

 

        """Make a Graph that raises an exception if we hit a node."""

1148

 

        g = self.make_graph(ancestors)

1149

 

        orig_parent_map = g.get_parent_map

1150

 

        def get_parent_map(keys):

1151

 

            bad_keys = set(keys).intersection(break_on)

1152

 

            if bad_keys:

1153

 

                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))

1154

 

            return orig_parent_map(keys)

1155

 

        g.get_parent_map = get_parent_map

1156

 

        return g

 

1181

class TestFindUniqueAncestors(TestGraphBase):

1157

1182

 

1158

1183

    def assertFindUniqueAncestors(self, graph, expected, node, common):

1159

1184

        actual = graph.find_unique_ancestors(node, common)

1228

1253

            ['h', 'i', 'j', 'y'], 'j', ['z'])

1229

1254

 

1230

1255

 

 

1256

class TestGraphFindDistanceToNull(TestGraphBase):

 

1257

    """Test an api that should be able to compute a revno"""

 

1258

 

 

1259

    def assertFindDistance(self, revno, graph, target_id, known_ids):

 

1260

        """Assert the output of Graph.find_distance_to_null()"""

 

1261

        actual = graph.find_distance_to_null(target_id, known_ids)

 

1262

        self.assertEqual(revno, actual)

 

1263

 

 

1264

    def test_nothing_known(self):

 

1265

        graph = self.make_graph(ancestry_1)

 

1266

        self.assertFindDistance(0, graph, NULL_REVISION, [])

 

1267

        self.assertFindDistance(1, graph, 'rev1', [])

 

1268

        self.assertFindDistance(2, graph, 'rev2a', [])

 

1269

        self.assertFindDistance(2, graph, 'rev2b', [])

 

1270

        self.assertFindDistance(3, graph, 'rev3', [])

 

1271

        self.assertFindDistance(4, graph, 'rev4', [])

 

1272

 

 

1273

    def test_rev_is_ghost(self):

 

1274

        graph = self.make_graph(ancestry_1)

 

1275

        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,

 

1276

                              graph.find_distance_to_null, 'rev_missing', [])

 

1277

        self.assertEqual('rev_missing', e.revision_id)

 

1278

        self.assertEqual('rev_missing', e.ghost_revision_id)

 

1279

 

 

1280

    def test_ancestor_is_ghost(self):

 

1281

        graph = self.make_graph({'rev':['parent']})

 

1282

        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,

 

1283

                              graph.find_distance_to_null, 'rev', [])

 

1284

        self.assertEqual('rev', e.revision_id)

 

1285

        self.assertEqual('parent', e.ghost_revision_id)

 

1286

 

 

1287

    def test_known_in_ancestry(self):

 

1288

        graph = self.make_graph(ancestry_1)

 

1289

        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])

 

1290

        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])

 

1291

 

 

1292

    def test_known_in_ancestry_limits(self):

 

1293

        graph = self.make_breaking_graph(ancestry_1, ['rev1'])

 

1294

        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])

 

1295

 

 

1296

    def test_target_is_ancestor(self):

 

1297

        graph = self.make_graph(ancestry_1)

 

1298

        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])

 

1299

 

 

1300

    def test_target_is_ancestor_limits(self):

 

1301

        """We shouldn't search all history if we run into ourselves"""

 

1302

        graph = self.make_breaking_graph(ancestry_1, ['rev1'])

 

1303

        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])

 

1304

 

 

1305

    def test_target_parallel_to_known_limits(self):

 

1306

        # Even though the known revision isn't part of the other ancestry, they

 

1307

        # eventually converge

 

1308

        graph = self.make_breaking_graph(with_tail, ['a'])

 

1309

        self.assertFindDistance(6, graph, 'f', [('g', 6)])

 

1310

        self.assertFindDistance(7, graph, 'h', [('g', 6)])

 

1311

        self.assertFindDistance(8, graph, 'i', [('g', 6)])

 

1312

        self.assertFindDistance(6, graph, 'g', [('i', 8)])

 

1313

 

 

1314

 

 

1315

class TestFindMergeOrder(TestGraphBase):

 

1316

 

 

1317

    def assertMergeOrder(self, expected, graph, tip, base_revisions):

 

1318

        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))

 

1319

 

 

1320

    def test_parents(self):

 

1321

        graph = self.make_graph(ancestry_1)

 

1322

        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',

 

1323

                                                        ['rev3', 'rev2b'])

 

1324

        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',

 

1325

                                                        ['rev2b', 'rev3'])

 

1326

 

 

1327

    def test_ancestors(self):

 

1328

        graph = self.make_graph(ancestry_1)

 

1329

        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',

 

1330

                                                        ['rev1', 'rev2b'])

 

1331

        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',

 

1332

                                                        ['rev2b', 'rev1'])

 

1333

 

 

1334

    def test_shortcut_one_ancestor(self):

 

1335

        # When we have enough info, we can stop searching

 

1336

        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])

 

1337

        # Single ancestors shortcut right away

 

1338

        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])

 

1339

 

 

1340

    def test_shortcut_after_one_ancestor(self):

 

1341

        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])

 

1342

        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])

 

1343

 

 

1344

 

1231

1345

class TestCachingParentsProvider(tests.TestCase):

1232

1346

 

1233

1347

    def setUp(self):

1270

1384

        # Use sorted because we don't care about the order, just that each is

1271

1385

        # only present 1 time.

1272

1386

        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))

 

1387

 

 

1388

 

 

1389

class TestCollapseLinearRegions(tests.TestCase):

 

1390

 

 

1391

    def assertCollapsed(self, collapsed, original):

 

1392

        self.assertEqual(collapsed,

 

1393

                         _mod_graph.collapse_linear_regions(original))

 

1394

 

 

1395

    def test_collapse_nothing(self):

 

1396

        d = {1:[2, 3], 2:[], 3:[]}

 

1397

        self.assertCollapsed(d, d)

 

1398

        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}

 

1399

        self.assertCollapsed(d, d)

 

1400

 

 

1401

    def test_collapse_chain(self):

 

1402

        # Any time we have a linear chain, we should be able to collapse

 

1403

        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}

 

1404

        self.assertCollapsed({1:[5], 5:[]}, d)

 

1405

        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}

 

1406

        self.assertCollapsed({5:[1], 1:[]}, d)

 

1407

        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}

 

1408

        self.assertCollapsed({5:[2], 2:[]}, d)

 

1409

 

 

1410

    def test_collapse_with_multiple_children(self):

 

1411

        #    7

 

1412

        #    |

 

1413

        #    6

 

1414

        #   / \

 

1415

        #  4   5

 

1416

        #  |   |

 

1417

        #  2   3

 

1418

        #   \ /

 

1419

        #    1

 

1420

        #

 

1421

        # 4 and 5 cannot be removed because 6 has 2 children

 

1422

        # 2 and 3 cannot be removed because 1 has 2 parents

 

1423

        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}

 

1424

        self.assertCollapsed(d, d)

• Older »

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