← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph_walker.py

  • Committer: Aaron Bentley
  • Date: 2007-05-26 00:20:09 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: aaron.bentley@utoronto.ca-20070526002009-8wekbvf32o7rufn2
Implement new merge base picker

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph_walker.py
4
4
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
5
5
              'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
6
6
 
 
7
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
8
               'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
 
9
 
7
10
class TestGraphWalker(TestCaseWithMemoryTransport):
8
11
 
9
12
    def test_distance_from_origin(self):
10
 
        tree = self.build_ancestry(ancestry_1)
11
 
        graph_walker = tree.branch.repository.get_graph_walker()
 
13
        graph_walker = self.make_walker(ancestry_1)
12
14
        self.assertEqual([1, 0, 2, 4],
13
15
                         graph_walker.distance_from_origin(['rev1', 'null:',
14
16
                         'rev2b', 'rev4']))
15
17
 
 
18
    def make_walker(self, ancestors):
 
19
        tree = self.build_ancestry(ancestors)
 
20
        return tree.branch.repository.get_graph_walker()
 
21
 
16
22
    def build_ancestry(self, ancestors):
17
23
        tree = self.make_branch_and_memory_tree('.')
18
24
        tree.lock_write()
25
31
        while len(pending) > 0:
26
32
            cur_node = pending.pop()
27
33
            for descendant in descendants.get(cur_node, []):
 
34
                if tree.branch.repository.has_revision(descendant):
 
35
                    continue
28
36
                parents = [p for p in ancestors[descendant] if p is not
29
37
                           NULL_REVISION]
30
38
                if len([p for p in parents if not
31
39
                    tree.branch.repository.has_revision(p)]) > 0:
32
40
                    continue
33
41
                tree.set_parent_ids(parents)
 
42
                if len(parents) > 0:
 
43
                    left_parent = parents[0]
 
44
                else:
 
45
                    left_parent = NULL_REVISION
34
46
                tree.branch.set_last_revision_info(
35
 
                    len(tree.branch._lefthand_history(cur_node)),
36
 
                    cur_node)
 
47
                    len(tree.branch._lefthand_history(left_parent)),
 
48
                    left_parent)
37
49
                tree.commit(descendant, rev_id=descendant)
38
50
                pending.append(descendant)
39
51
        tree.unlock()
40
52
        return tree
41
53
 
42
54
    def test_mca(self):
43
 
        tree = self.build_ancestry(ancestry_1)
44
 
        graph_walker = tree.branch.repository.get_graph_walker()
45
 
        self.assertEqual(set([NULL_REVISION]),
46
 
                         graph_walker.minimal_common(NULL_REVISION,
47
 
                                                     NULL_REVISION))
48
 
        self.assertEqual(set([NULL_REVISION]),
49
 
                         graph_walker.minimal_common(NULL_REVISION,
50
 
                                                     'rev1'))
 
55
        """Test finding minimal common ancestor.
 
56
 
 
57
        ancestry_1 should always have a single common ancestor
 
58
        """
 
59
        graph_walker = self.make_walker(ancestry_1)
 
60
        self.assertEqual(set([NULL_REVISION]),
 
61
                         graph_walker.minimal_common(NULL_REVISION,
 
62
                                                     NULL_REVISION))
 
63
        self.assertEqual(set([NULL_REVISION]),
 
64
                         graph_walker.minimal_common(NULL_REVISION,
 
65
                                                     'rev1'))
 
66
        self.assertEqual(set(['rev1']),
 
67
                         graph_walker.minimal_common('rev1', 'rev1'))
 
68
        self.assertEqual(set(['rev1']),
 
69
                         graph_walker.minimal_common('rev2a', 'rev2b'))
 
70
 
 
71
    def test_mca_criss_cross(self):
 
72
        graph_walker = self.make_walker(criss_cross)
 
73
        self.assertEqual(set(['rev2a', 'rev2b']),
 
74
                         graph_walker.minimal_common('rev3a', 'rev3b'))
 
75
        self.assertEqual(set(['rev2b']),
 
76
                         graph_walker.minimal_common('rev3a', 'rev3b',
 
77
                                                     'rev2b'))
 
78
 
 
79
    def test_recursive_unique_mca(self):
 
80
        """Test finding a unique minimal common ancestor.
 
81
 
 
82
        ancestry_1 should always have a single common ancestor
 
83
        """
 
84
        graph_walker = self.make_walker(ancestry_1)
 
85
        self.assertEqual(NULL_REVISION,
 
86
                         graph_walker.unique_common(NULL_REVISION,
 
87
                                                     NULL_REVISION))
 
88
        self.assertEqual(NULL_REVISION,
 
89
                         graph_walker.unique_common(NULL_REVISION,
 
90
                                                     'rev1'))
 
91
        self.assertEqual('rev1', graph_walker.unique_common('rev1', 'rev1'))
 
92
        self.assertEqual('rev1', graph_walker.unique_common('rev2a', 'rev2b'))
 
93
 
 
94
    def test_mca_criss_cross(self):
 
95
        graph_walker = self.make_walker(criss_cross)
 
96
        self.assertEqual(set(['rev2a', 'rev2b']),
 
97
                         graph_walker.minimal_common('rev3a', 'rev3b'))
 
98
        self.assertEqual(set(['rev2b']),
 
99
                         graph_walker.minimal_common('rev3a', 'rev3b',
 
100
                                                     'rev2b'))
 
101
 
 
102
    def test_unique_common_criss_cross(self):
 
103
        """Ensure we don't pick non-unique mcas in a criss-cross"""
 
104
        graph_walker = self.make_walker(criss_cross)
 
105
        self.assertEqual('rev1',
 
106
                         graph_walker.unique_common('rev3a', 'rev3b'))