← 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-06-08 15:03:32 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: abentley@panoramicfeedback.com-20070608150332-jxt1yx9hy7dmhxhv
Update distinct -> lowest, refactor, add ParentsProvider concept

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph_walker.py
40
40
 
41
41
class TestGraphWalker(TestCaseWithMemoryTransport):
42
42
 
43
 
    def test_distance_from_origin(self):
44
 
        graph_walker = self.make_walker(ancestry_1)
45
 
        self.assertEqual([1, 0, 2, 4],
46
 
                         graph_walker.distance_from_origin(['rev1', 'null:',
47
 
                         'rev2b', 'rev4']))
48
 
 
49
43
    def make_walker(self, ancestors):
50
44
        tree = self.prepare_memory_tree('.')
51
45
        self.build_ancestry(tree, ancestors)
85
79
                tree.commit(descendant, rev_id=descendant)
86
80
                pending.append(descendant)
87
81
 
88
 
    def test_dca(self):
 
82
    def test_lca(self):
89
83
        """Test finding distinct common ancestor.
90
84
 
91
85
        ancestry_1 should always have a single common ancestor
92
86
        """
93
87
        graph_walker = self.make_walker(ancestry_1)
94
88
        self.assertEqual(set([NULL_REVISION]),
95
 
                         graph_walker.distinct_common(NULL_REVISION,
 
89
                         graph_walker.find_lca(NULL_REVISION,
96
90
                                                     NULL_REVISION))
97
91
        self.assertEqual(set([NULL_REVISION]),
98
 
                         graph_walker.distinct_common(NULL_REVISION,
 
92
                         graph_walker.find_lca(NULL_REVISION,
99
93
                                                     'rev1'))
100
94
        self.assertEqual(set(['rev1']),
101
 
                         graph_walker.distinct_common('rev1', 'rev1'))
 
95
                         graph_walker.find_lca('rev1', 'rev1'))
102
96
        self.assertEqual(set(['rev1']),
103
 
                         graph_walker.distinct_common('rev2a', 'rev2b'))
 
97
                         graph_walker.find_lca('rev2a', 'rev2b'))
104
98
 
105
 
    def test_dca_criss_cross(self):
 
99
    def test_lca_criss_cross(self):
106
100
        graph_walker = self.make_walker(criss_cross)
107
101
        self.assertEqual(set(['rev2a', 'rev2b']),
108
 
                         graph_walker.distinct_common('rev3a', 'rev3b'))
 
102
                         graph_walker.find_lca('rev3a', 'rev3b'))
109
103
        self.assertEqual(set(['rev2b']),
110
 
                         graph_walker.distinct_common('rev3a', 'rev3b',
 
104
                         graph_walker.find_lca('rev3a', 'rev3b',
111
105
                                                     'rev2b'))
112
106
 
113
 
    def test_dca_shortcut(self):
 
107
    def test_lca_shortcut(self):
114
108
        graph_walker = self.make_walker(history_shortcut)
115
109
        self.assertEqual(set(['rev2b']),
116
 
                         graph_walker.distinct_common('rev3a', 'rev3b'))
 
110
                         graph_walker.find_lca('rev3a', 'rev3b'))
117
111
 
118
 
    def test_recursive_unique_dca(self):
 
112
    def test_recursive_unique_lca(self):
119
113
        """Test finding a unique distinct common ancestor.
120
114
 
121
115
        ancestry_1 should always have a single common ancestor
122
116
        """
123
117
        graph_walker = self.make_walker(ancestry_1)
124
118
        self.assertEqual(NULL_REVISION,
125
 
                         graph_walker.unique_common(NULL_REVISION,
126
 
                                                     NULL_REVISION))
 
119
                         graph_walker.find_unique_lca(NULL_REVISION,
 
120
                                                      NULL_REVISION))
127
121
        self.assertEqual(NULL_REVISION,
128
 
                         graph_walker.unique_common(NULL_REVISION,
129
 
                                                     'rev1'))
130
 
        self.assertEqual('rev1', graph_walker.unique_common('rev1', 'rev1'))
131
 
        self.assertEqual('rev1', graph_walker.unique_common('rev2a', 'rev2b'))
 
122
                         graph_walker.find_unique_lca(NULL_REVISION,
 
123
                                                      'rev1'))
 
124
        self.assertEqual('rev1', graph_walker.find_unique_lca('rev1',
 
125
                                                              'rev1'))
 
126
        self.assertEqual('rev1', graph_walker.find_unique_lca('rev2a',
 
127
                                                              'rev2b'))
132
128
 
133
 
    def test_dca_criss_cross(self):
 
129
    def test_lca_criss_cross(self):
134
130
        graph_walker = self.make_walker(criss_cross)
135
131
        self.assertEqual(set(['rev2a', 'rev2b']),
136
 
                         graph_walker.distinct_common('rev3a', 'rev3b'))
 
132
                         graph_walker.find_lca('rev3a', 'rev3b'))
137
133
        self.assertEqual(set(['rev2b']),
138
 
                         graph_walker.distinct_common('rev3a', 'rev3b',
 
134
                         graph_walker.find_lca('rev3a', 'rev3b',
139
135
                                                      'rev2b'))
140
136
 
141
 
    def test_unique_common_criss_cross(self):
142
 
        """Ensure we don't pick non-unique dcas in a criss-cross"""
 
137
    def test_unique_lca_criss_cross(self):
 
138
        """Ensure we don't pick non-unique lcas in a criss-cross"""
143
139
        graph_walker = self.make_walker(criss_cross)
144
140
        self.assertEqual('rev1',
145
 
                         graph_walker.unique_common('rev3a', 'rev3b'))
 
141
                         graph_walker.find_unique_lca('rev3a', 'rev3b'))
146
142
 
147
 
    def test_unique_common_null_revision(self):
 
143
    def test_unique_lca_null_revision(self):
148
144
        """Ensure we pick NULL_REVISION when necessary"""
149
145
        graph_walker = self.make_walker(criss_cross2)
150
146
        self.assertEqual('rev1b',
151
 
                         graph_walker.unique_common('rev2a', 'rev1b'))
 
147
                         graph_walker.find_unique_lca('rev2a', 'rev1b'))
152
148
        self.assertEqual(NULL_REVISION,
153
 
                         graph_walker.unique_common('rev2a', 'rev2b'))
 
149
                         graph_walker.find_unique_lca('rev2a', 'rev2b'))
154
150
 
155
 
    def test_unique_common_null_revision2(self):
 
151
    def test_unique_lca_null_revision2(self):
156
152
        """Ensure we pick NULL_REVISION when necessary"""
157
153
        graph_walker = self.make_walker(ancestry_2)
158
154
        self.assertEqual(NULL_REVISION,
159
 
                         graph_walker.unique_common('rev4a', 'rev1b'))
 
155
                         graph_walker.find_unique_lca('rev4a', 'rev1b'))
160
156
 
161
157
    def test_common_ancestor_two_repos(self):
162
 
        """Ensure we do unique_common using data from two repos"""
 
158
        """Ensure we do unique_lca using data from two repos"""
163
159
        mainline_tree = self.prepare_memory_tree('mainline')
164
160
        self.build_ancestry(mainline_tree, mainline)
165
161
        mainline_tree.unlock()
171
167
        feature_tree.unlock()
172
168
        graph_walker = mainline_tree.branch.repository.get_graph_walker(
173
169
            feature_tree.branch.repository)
174
 
        self.assertEqual('rev2b', graph_walker.unique_common('rev2a', 'rev3b'))
 
170
        self.assertEqual('rev2b', graph_walker.find_unique_lca('rev2a',
 
171
                         'rev3b'))