1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
from bzrlib.revision import NULL_REVISION
22
from bzrlib.tests import TestCaseWithMemoryTransport
36
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
37
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
51
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
52
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
55
# Criss cross ancestry
66
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
67
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
81
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
82
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
94
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
107
feature_branch = {'rev1': [NULL_REVISION],
108
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
119
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
120
'rev2b': ['rev1'], 'rev2c': ['rev1'],
121
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
124
class TestGraph(TestCaseWithMemoryTransport):
126
def make_graph(self, ancestors):
127
tree = self.prepare_memory_tree('.')
128
self.build_ancestry(tree, ancestors)
130
return tree.branch.repository.get_graph()
132
def prepare_memory_tree(self, location):
133
tree = self.make_branch_and_memory_tree(location)
138
def build_ancestry(self, tree, ancestors):
139
"""Create an ancestry as specified by a graph dict
141
:param tree: A tree to use
142
:param ancestors: a dict of {node: [node_parent, ...]}
144
pending = [NULL_REVISION]
146
for descendant, parents in ancestors.iteritems():
147
for parent in parents:
148
descendants.setdefault(parent, []).append(descendant)
149
while len(pending) > 0:
150
cur_node = pending.pop()
151
for descendant in descendants.get(cur_node, []):
152
if tree.branch.repository.has_revision(descendant):
154
parents = [p for p in ancestors[descendant] if p is not
156
if len([p for p in parents if not
157
tree.branch.repository.has_revision(p)]) > 0:
159
tree.set_parent_ids(parents)
161
left_parent = parents[0]
163
left_parent = NULL_REVISION
164
tree.branch.set_last_revision_info(
165
len(tree.branch._lefthand_history(left_parent)),
167
tree.commit(descendant, rev_id=descendant)
168
pending.append(descendant)
171
"""Test finding least common ancestor.
173
ancestry_1 should always have a single common ancestor
175
graph = self.make_graph(ancestry_1)
176
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
177
self.assertEqual(set([NULL_REVISION]),
178
graph.find_lca(NULL_REVISION, NULL_REVISION))
179
self.assertEqual(set([NULL_REVISION]),
180
graph.find_lca(NULL_REVISION, 'rev1'))
181
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
182
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
184
def test_lca_criss_cross(self):
185
"""Test least-common-ancestor after a criss-cross merge."""
186
graph = self.make_graph(criss_cross)
187
self.assertEqual(set(['rev2a', 'rev2b']),
188
graph.find_lca('rev3a', 'rev3b'))
189
self.assertEqual(set(['rev2b']),
190
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
192
def test_lca_shortcut(self):
193
"""Test least-common ancestor on this history shortcut"""
194
graph = self.make_graph(history_shortcut)
195
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
197
def test_recursive_unique_lca(self):
198
"""Test finding a unique least common ancestor.
200
ancestry_1 should always have a single common ancestor
202
graph = self.make_graph(ancestry_1)
203
self.assertEqual(NULL_REVISION,
204
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
205
self.assertEqual(NULL_REVISION,
206
graph.find_unique_lca(NULL_REVISION, 'rev1'))
207
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
208
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
210
def test_unique_lca_criss_cross(self):
211
"""Ensure we don't pick non-unique lcas in a criss-cross"""
212
graph = self.make_graph(criss_cross)
213
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
215
def test_unique_lca_null_revision(self):
216
"""Ensure we pick NULL_REVISION when necessary"""
217
graph = self.make_graph(criss_cross2)
218
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
219
self.assertEqual(NULL_REVISION,
220
graph.find_unique_lca('rev2a', 'rev2b'))
222
def test_unique_lca_null_revision2(self):
223
"""Ensure we pick NULL_REVISION when necessary"""
224
graph = self.make_graph(ancestry_2)
225
self.assertEqual(NULL_REVISION,
226
graph.find_unique_lca('rev4a', 'rev1b'))
228
def test_common_ancestor_two_repos(self):
229
"""Ensure we do unique_lca using data from two repos"""
230
mainline_tree = self.prepare_memory_tree('mainline')
231
self.build_ancestry(mainline_tree, mainline)
232
mainline_tree.unlock()
234
# This is cheating, because the revisions in the graph are actually
235
# different revisions, despite having the same revision-id.
236
feature_tree = self.prepare_memory_tree('feature')
237
self.build_ancestry(feature_tree, feature_branch)
238
feature_tree.unlock()
239
graph = mainline_tree.branch.repository.get_graph(
240
feature_tree.branch.repository)
241
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
243
def test_graph_difference(self):
244
graph = self.make_graph(ancestry_1)
245
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
246
self.assertEqual((set(), set(['rev1'])),
247
graph.find_difference(NULL_REVISION, 'rev1'))
248
self.assertEqual((set(['rev1']), set()),
249
graph.find_difference('rev1', NULL_REVISION))
250
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
251
graph.find_difference('rev3', 'rev2b'))
252
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
253
graph.find_difference('rev4', 'rev2b'))
255
def test_graph_difference_criss_cross(self):
256
graph = self.make_graph(criss_cross)
257
self.assertEqual((set(['rev3a']), set(['rev3b'])),
258
graph.find_difference('rev3a', 'rev3b'))
259
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
260
graph.find_difference('rev2a', 'rev3b'))
262
def test_stacked_parents_provider(self):
264
class ParentsProvider(object):
266
def __init__(self, ancestry):
267
self.ancestry = ancestry
269
def get_parents(self, revisions):
270
return [self.ancestry.get(r, None) for r in revisions]
272
parents1 = ParentsProvider({'rev2': ['rev3']})
273
parents2 = ParentsProvider({'rev1': ['rev4']})
274
stacked = graph._StackedParentsProvider([parents1, parents2])
275
self.assertEqual([['rev4',], ['rev3']],
276
stacked.get_parents(['rev1', 'rev2']))
277
self.assertEqual([['rev3',], ['rev4']],
278
stacked.get_parents(['rev2', 'rev1']))
279
self.assertEqual([['rev3',], ['rev3']],
280
stacked.get_parents(['rev2', 'rev2']))
281
self.assertEqual([['rev4',], ['rev4']],
282
stacked.get_parents(['rev1', 'rev1']))
284
def test_iter_topo_order(self):
285
graph = self.make_graph(ancestry_1)
286
args = ['rev2a', 'rev3', 'rev1']
287
topo_args = list(graph.iter_topo_order(args))
288
self.assertEqual(set(args), set(topo_args))
289
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
290
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
added
removed
bzrlib/tests/test_graph.py
