← 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: Vincent Ladeuil
  • Date: 2011-09-09 13:30:12 UTC
  • mfrom: (5609.48.11 2.3)
  • mto: (6015.33.3 2.4)
  • mto: This revision was merged to the branch mainline in revision 6134.
  • Revision ID: v.ladeuil+lp@free.fr-20110909133012-jc1d1zyqgak57123
Merge 2.3 into 2.4

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007-2011 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
17
17
from bzrlib import (
18
18
    errors,
19
19
    graph as _mod_graph,
20
 
    symbol_versioning,
21
20
    tests,
22
21
    )
23
22
from bzrlib.revision import NULL_REVISION
24
23
from bzrlib.tests import TestCaseWithMemoryTransport
25
 
from bzrlib.symbol_versioning import deprecated_in
26
24
 
27
25
 
28
26
# Ancestry 1:
526
524
        graph = self.make_graph(history_shortcut)
527
525
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
528
526
 
 
527
    def test_lefthand_distance_smoke(self):
 
528
        """A simple does it work test for graph.lefthand_distance(keys)."""
 
529
        graph = self.make_graph(history_shortcut)
 
530
        distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
 
531
        self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
 
532
 
 
533
    def test_lefthand_distance_ghosts(self):
 
534
        """A simple does it work test for graph.lefthand_distance(keys)."""
 
535
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
 
536
        graph = self.make_graph(nodes)
 
537
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
 
538
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
 
539
 
529
540
    def test_recursive_unique_lca(self):
530
541
        """Test finding a unique least common ancestor.
531
542
 
687
698
        self.assertEqual({'rev2': ['rev1']},
688
699
                         stacked.get_parent_map(['rev2']))
689
700
 
690
 
    def test__stacked_parents_provider_deprecated(self):
691
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
692
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
693
 
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
694
 
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
695
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
696
 
                         stacked.get_parent_map(['rev1', 'rev2']))
697
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
698
 
                         stacked.get_parent_map(['rev2', 'rev1']))
699
 
        self.assertEqual({'rev2':['rev3']},
700
 
                         stacked.get_parent_map(['rev2', 'rev2']))
701
 
        self.assertEqual({'rev1':['rev4']},
702
 
                         stacked.get_parent_map(['rev1', 'rev1']))
703
 
 
704
701
    def test_iter_topo_order(self):
705
702
        graph = self.make_graph(ancestry_1)
706
703
        args = ['rev2a', 'rev3', 'rev1']
1411
1408
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1412
1409
 
1413
1410
 
 
1411
class TestFindDescendants(TestGraphBase):
 
1412
 
 
1413
    def test_find_descendants_rev1_rev3(self):
 
1414
        graph = self.make_graph(ancestry_1)
 
1415
        descendants = graph.find_descendants('rev1', 'rev3')
 
1416
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
 
1417
 
 
1418
    def test_find_descendants_rev1_rev4(self):
 
1419
        graph = self.make_graph(ancestry_1)
 
1420
        descendants = graph.find_descendants('rev1', 'rev4')
 
1421
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
 
1422
                         descendants)
 
1423
 
 
1424
    def test_find_descendants_rev2a_rev4(self):
 
1425
        graph = self.make_graph(ancestry_1)
 
1426
        descendants = graph.find_descendants('rev2a', 'rev4')
 
1427
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
 
1428
 
 
1429
class TestFindLefthandMerger(TestGraphBase):
 
1430
 
 
1431
    def check_merger(self, result, ancestry, merged, tip):
 
1432
        graph = self.make_graph(ancestry)
 
1433
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
 
1434
 
 
1435
    def test_find_lefthand_merger_rev2b(self):
 
1436
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
 
1437
 
 
1438
    def test_find_lefthand_merger_rev2a(self):
 
1439
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
 
1440
 
 
1441
    def test_find_lefthand_merger_rev4(self):
 
1442
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
 
1443
 
 
1444
    def test_find_lefthand_merger_f(self):
 
1445
        self.check_merger('i', complex_shortcut, 'f', 'm')
 
1446
 
 
1447
    def test_find_lefthand_merger_g(self):
 
1448
        self.check_merger('i', complex_shortcut, 'g', 'm')
 
1449
 
 
1450
    def test_find_lefthand_merger_h(self):
 
1451
        self.check_merger('n', complex_shortcut, 'h', 'n')
 
1452
 
 
1453
 
 
1454
class TestGetChildMap(TestGraphBase):
 
1455
 
 
1456
    def test_get_child_map(self):
 
1457
        graph = self.make_graph(ancestry_1)
 
1458
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
 
1459
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
 
1460
                          'rev2a': ['rev3'],
 
1461
                          'rev2b': ['rev4'],
 
1462
                          'rev3': ['rev4']},
 
1463
                          child_map)
 
1464
 
 
1465
 
1414
1466
class TestCachingParentsProvider(tests.TestCase):
1415
1467
    """These tests run with:
1416
1468
 
1569
1621
        self.assertCollapsed(d, d)
1570
1622
 
1571
1623
 
 
1624
class TestGraphThunkIdsToKeys(tests.TestCase):
 
1625
 
 
1626
    def test_heads(self):
 
1627
        # A
 
1628
        # |\
 
1629
        # B C
 
1630
        # |/
 
1631
        # D
 
1632
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
 
1633
             ('B',): [('A',)], ('A',): []}
 
1634
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
 
1635
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1636
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
 
1637
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
 
1638
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
 
1639
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
 
1640
 
 
1641
    def test_add_node(self):
 
1642
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1643
        g = _mod_graph.KnownGraph(d)
 
1644
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1645
        graph_thunk.add_node("D", ["A", "C"])
 
1646
        self.assertEqual(['B', 'D'],
 
1647
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
 
1648
 
 
1649
    def test_merge_sort(self):
 
1650
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1651
        g = _mod_graph.KnownGraph(d)
 
1652
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1653
        graph_thunk.add_node("D", ["A", "C"])
 
1654
        self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
 
1655
            [(n.key, n.merge_depth, n.revno, n.end_of_merge)
 
1656
                 for n in graph_thunk.merge_sort('C')])
 
1657
 
 
1658
 
1572
1659
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1573
1660
    """Tests for bzrlib.graph.PendingAncestryResult."""
1574
1661