← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-10 18:58:02 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090610185802-wsybzjfil447yhy2
Change VF.annotate to use the new KnownGraph code.

This shows a significant savings in the time for 'annotate NEWS', of about 5s/20s
for knit formats, and 45s => 20s for GC formats.


Also, factor the code into a helper, so that we can prepare for writing
a pyrex version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
22
22
    )
23
23
from bzrlib.revision import NULL_REVISION
24
24
from bzrlib.tests import TestCaseWithMemoryTransport
25
 
from bzrlib.symbol_versioning import deprecated_in 
 
25
from bzrlib.symbol_versioning import deprecated_in
26
26
 
27
27
 
28
28
# Ancestry 1:
1381
1381
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1382
1382
 
1383
1383
 
1384
 
class TestKnownGraph(tests.TestCase):
1385
 
 
1386
 
    def make_known_graph(self, ancestry):
1387
 
        return _mod_graph.KnownGraph(ancestry)
1388
 
 
1389
 
    def assertDominator(self, graph, rev, dominator, distance):
1390
 
        node = graph._nodes[rev]
1391
 
        self.assertEqual(dominator, node.linear_dominator)
1392
 
        self.assertEqual(distance, node.dominator_distance)
1393
 
 
1394
 
    def assertGDFO(self, graph, rev, gdfo):
1395
 
        node = graph._nodes[rev]
1396
 
        self.assertEqual(gdfo, node.gdfo)
1397
 
 
1398
 
    def test_children_ancestry1(self):
1399
 
        graph = self.make_known_graph(ancestry_1)
1400
 
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
1401
 
        self.assertEqual(['rev2a', 'rev2b'],
1402
 
                         sorted(graph._nodes['rev1'].child_keys))
1403
 
        self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
1404
 
        self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
1405
 
        self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
1406
 
 
1407
 
    def test_dominators_ancestry_1(self):
1408
 
        graph = self.make_known_graph(ancestry_1)
1409
 
        self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
1410
 
        self.assertDominator(graph, 'rev2b', 'rev2b', 0)
1411
 
        self.assertDominator(graph, 'rev2a', 'rev2a', 0)
1412
 
        self.assertDominator(graph, 'rev3', 'rev2a', 1)
1413
 
        self.assertDominator(graph, 'rev4', 'rev4', 0)
1414
 
 
1415
 
    def test_dominators_feature_branch(self):
1416
 
        graph = self.make_known_graph(feature_branch)
1417
 
        self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
1418
 
        self.assertDominator(graph, 'rev2b', NULL_REVISION, 2)
1419
 
        self.assertDominator(graph, 'rev3b', NULL_REVISION, 3)
1420
 
 
1421
 
    def test_dominators_extended_history_shortcut(self):
1422
 
        graph = self.make_known_graph(extended_history_shortcut)
1423
 
        self.assertDominator(graph, 'a', NULL_REVISION, 1)
1424
 
        self.assertDominator(graph, 'b', 'b', 0)
1425
 
        self.assertDominator(graph, 'c', 'b', 1)
1426
 
        self.assertDominator(graph, 'd', 'b', 2)
1427
 
        self.assertDominator(graph, 'e', 'e', 0)
1428
 
        self.assertDominator(graph, 'f', 'f', 0)
1429
 
 
1430
 
    def test_gdfo_ancestry_1(self):
1431
 
        graph = self.make_known_graph(ancestry_1)
1432
 
        self.assertGDFO(graph, 'rev1', 2)
1433
 
        self.assertGDFO(graph, 'rev2b', 3)
1434
 
        self.assertGDFO(graph, 'rev2a', 3)
1435
 
        self.assertGDFO(graph, 'rev3', 4)
1436
 
        self.assertGDFO(graph, 'rev4', 5)
1437
 
 
1438
 
    def test_gdfo_feature_branch(self):
1439
 
        graph = self.make_known_graph(feature_branch)
1440
 
        self.assertGDFO(graph, 'rev1', 2)
1441
 
        self.assertGDFO(graph, 'rev2b', 3)
1442
 
        self.assertGDFO(graph, 'rev3b', 4)
1443
 
 
1444
 
    def test_gdfo_extended_history_shortcut(self):
1445
 
        graph = self.make_known_graph(extended_history_shortcut)
1446
 
        self.assertGDFO(graph, 'a', 2)
1447
 
        self.assertGDFO(graph, 'b', 3)
1448
 
        self.assertGDFO(graph, 'c', 4)
1449
 
        self.assertGDFO(graph, 'd', 5)
1450
 
        self.assertGDFO(graph, 'e', 6)
1451
 
        self.assertGDFO(graph, 'f', 6)
1452
 
 
1453
 
    def test_gdfo_with_ghost(self):
1454
 
        graph = self.make_known_graph(with_ghost)
1455
 
        self.assertGDFO(graph, 'f', 2)
1456
 
        self.assertGDFO(graph, 'e', 3)
1457
 
        self.assertGDFO(graph, 'g', 1)
1458
 
        self.assertGDFO(graph, 'b', 4)
1459
 
        self.assertGDFO(graph, 'd', 4)
1460
 
        self.assertGDFO(graph, 'a', 5)
1461
 
        self.assertGDFO(graph, 'c', 5)
1462
 
 
1463
 
    def test_heads_null(self):
1464
 
        graph = self.make_known_graph(ancestry_1)
1465
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
1466
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
1467
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
1468
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
1469
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
1470
 
 
1471
 
    def test_heads_one(self):
1472
 
        # A single node will always be a head
1473
 
        graph = self.make_known_graph(ancestry_1)
1474
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
1475
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
1476
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
1477
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
1478
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
1479
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
1480
 
 
1481
 
    def test_heads_single(self):
1482
 
        graph = self.make_known_graph(ancestry_1)
1483
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
1484
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
1485
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
1486
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
1487
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
1488
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
1489
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
1490
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
1491
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
1492
 
 
1493
 
    def test_heads_two_heads(self):
1494
 
        graph = self.make_known_graph(ancestry_1)
1495
 
        self.assertEqual(set(['rev2a', 'rev2b']),
1496
 
                         graph.heads(['rev2a', 'rev2b']))
1497
 
        self.assertEqual(set(['rev3', 'rev2b']),
1498
 
                         graph.heads(['rev3', 'rev2b']))
1499
 
 
1500
 
    def test_heads_criss_cross(self):
1501
 
        graph = self.make_known_graph(criss_cross)
1502
 
        self.assertEqual(set(['rev2a']),
1503
 
                         graph.heads(['rev2a', 'rev1']))
1504
 
        self.assertEqual(set(['rev2b']),
1505
 
                         graph.heads(['rev2b', 'rev1']))
1506
 
        self.assertEqual(set(['rev3a']),
1507
 
                         graph.heads(['rev3a', 'rev1']))
1508
 
        self.assertEqual(set(['rev3b']),
1509
 
                         graph.heads(['rev3b', 'rev1']))
1510
 
        self.assertEqual(set(['rev2a', 'rev2b']),
1511
 
                         graph.heads(['rev2a', 'rev2b']))
1512
 
        self.assertEqual(set(['rev3a']),
1513
 
                         graph.heads(['rev3a', 'rev2a']))
1514
 
        self.assertEqual(set(['rev3a']),
1515
 
                         graph.heads(['rev3a', 'rev2b']))
1516
 
        self.assertEqual(set(['rev3a']),
1517
 
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
1518
 
        self.assertEqual(set(['rev3b']),
1519
 
                         graph.heads(['rev3b', 'rev2a']))
1520
 
        self.assertEqual(set(['rev3b']),
1521
 
                         graph.heads(['rev3b', 'rev2b']))
1522
 
        self.assertEqual(set(['rev3b']),
1523
 
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
1524
 
        self.assertEqual(set(['rev3a', 'rev3b']),
1525
 
                         graph.heads(['rev3a', 'rev3b']))
1526
 
        self.assertEqual(set(['rev3a', 'rev3b']),
1527
 
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
1528
 
 
1529
 
    def test_heads_shortcut(self):
1530
 
        graph = self.make_known_graph(history_shortcut)
1531
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
1532
 
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
1533
 
        self.assertEqual(set(['rev3a', 'rev3b']),
1534
 
                         graph.heads(['rev3a', 'rev3b']))
1535
 
        self.assertEqual(set(['rev3a', 'rev3b']),
1536
 
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
1537
 
        self.assertEqual(set(['rev2a', 'rev3b']),
1538
 
                         graph.heads(['rev2a', 'rev3b']))
1539
 
        self.assertEqual(set(['rev2c', 'rev3a']),
1540
 
                         graph.heads(['rev2c', 'rev3a']))
1541
 
 
1542
 
 
1543
 
 
1544
1384
class TestFindMergeOrder(TestGraphBase):
1545
1385
 
1546
1386
    def assertMergeOrder(self, expected, graph, tip, base_revisions):