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']}
133
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
137
class InstrumentedParentsProvider(object):
139
def __init__(self, parents_provider):
141
self._real_parents_provider = parents_provider
143
def get_parents(self, nodes):
144
self.calls.extend(nodes)
145
return self._real_parents_provider.get_parents(nodes)
148
class DictParentsProvider(object):
150
def __init__(self, ancestry):
151
self.ancestry = ancestry
154
return 'DictParentsProvider(%r)' % self.ancestry
156
def get_parents(self, revisions):
157
return [self.ancestry.get(r, None) for r in revisions]
160
class TestGraph(TestCaseWithMemoryTransport):
162
def make_graph(self, ancestors):
163
tree = self.prepare_memory_tree('.')
164
self.build_ancestry(tree, ancestors)
166
return tree.branch.repository.get_graph()
168
def prepare_memory_tree(self, location):
169
tree = self.make_branch_and_memory_tree(location)
174
def build_ancestry(self, tree, ancestors):
175
"""Create an ancestry as specified by a graph dict
177
:param tree: A tree to use
178
:param ancestors: a dict of {node: [node_parent, ...]}
180
pending = [NULL_REVISION]
182
for descendant, parents in ancestors.iteritems():
183
for parent in parents:
184
descendants.setdefault(parent, []).append(descendant)
185
while len(pending) > 0:
186
cur_node = pending.pop()
187
for descendant in descendants.get(cur_node, []):
188
if tree.branch.repository.has_revision(descendant):
190
parents = [p for p in ancestors[descendant] if p is not
192
if len([p for p in parents if not
193
tree.branch.repository.has_revision(p)]) > 0:
195
tree.set_parent_ids(parents)
197
left_parent = parents[0]
199
left_parent = NULL_REVISION
200
tree.branch.set_last_revision_info(
201
len(tree.branch._lefthand_history(left_parent)),
203
tree.commit(descendant, rev_id=descendant)
204
pending.append(descendant)
207
"""Test finding least common ancestor.
209
ancestry_1 should always have a single common ancestor
211
graph = self.make_graph(ancestry_1)
212
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
213
self.assertEqual(set([NULL_REVISION]),
214
graph.find_lca(NULL_REVISION, NULL_REVISION))
215
self.assertEqual(set([NULL_REVISION]),
216
graph.find_lca(NULL_REVISION, 'rev1'))
217
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
218
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
220
def test_no_unique_lca(self):
221
"""Test error when one revision is not in the graph"""
222
graph = self.make_graph(ancestry_1)
223
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
226
def test_lca_criss_cross(self):
227
"""Test least-common-ancestor after a criss-cross merge."""
228
graph = self.make_graph(criss_cross)
229
self.assertEqual(set(['rev2a', 'rev2b']),
230
graph.find_lca('rev3a', 'rev3b'))
231
self.assertEqual(set(['rev2b']),
232
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
234
def test_lca_shortcut(self):
235
"""Test least-common ancestor on this history shortcut"""
236
graph = self.make_graph(history_shortcut)
237
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
239
def test_recursive_unique_lca(self):
240
"""Test finding a unique least common ancestor.
242
ancestry_1 should always have a single common ancestor
244
graph = self.make_graph(ancestry_1)
245
self.assertEqual(NULL_REVISION,
246
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
247
self.assertEqual(NULL_REVISION,
248
graph.find_unique_lca(NULL_REVISION, 'rev1'))
249
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
250
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
252
def test_unique_lca_criss_cross(self):
253
"""Ensure we don't pick non-unique lcas in a criss-cross"""
254
graph = self.make_graph(criss_cross)
255
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
257
def test_unique_lca_null_revision(self):
258
"""Ensure we pick NULL_REVISION when necessary"""
259
graph = self.make_graph(criss_cross2)
260
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
261
self.assertEqual(NULL_REVISION,
262
graph.find_unique_lca('rev2a', 'rev2b'))
264
def test_unique_lca_null_revision2(self):
265
"""Ensure we pick NULL_REVISION when necessary"""
266
graph = self.make_graph(ancestry_2)
267
self.assertEqual(NULL_REVISION,
268
graph.find_unique_lca('rev4a', 'rev1b'))
270
def test_common_ancestor_two_repos(self):
271
"""Ensure we do unique_lca using data from two repos"""
272
mainline_tree = self.prepare_memory_tree('mainline')
273
self.build_ancestry(mainline_tree, mainline)
274
mainline_tree.unlock()
276
# This is cheating, because the revisions in the graph are actually
277
# different revisions, despite having the same revision-id.
278
feature_tree = self.prepare_memory_tree('feature')
279
self.build_ancestry(feature_tree, feature_branch)
280
feature_tree.unlock()
281
graph = mainline_tree.branch.repository.get_graph(
282
feature_tree.branch.repository)
283
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
285
def test_graph_difference(self):
286
graph = self.make_graph(ancestry_1)
287
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
288
self.assertEqual((set(), set(['rev1'])),
289
graph.find_difference(NULL_REVISION, 'rev1'))
290
self.assertEqual((set(['rev1']), set()),
291
graph.find_difference('rev1', NULL_REVISION))
292
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
293
graph.find_difference('rev3', 'rev2b'))
294
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
295
graph.find_difference('rev4', 'rev2b'))
297
def test_graph_difference_criss_cross(self):
298
graph = self.make_graph(criss_cross)
299
self.assertEqual((set(['rev3a']), set(['rev3b'])),
300
graph.find_difference('rev3a', 'rev3b'))
301
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
302
graph.find_difference('rev2a', 'rev3b'))
304
def test_stacked_parents_provider(self):
306
parents1 = DictParentsProvider({'rev2': ['rev3']})
307
parents2 = DictParentsProvider({'rev1': ['rev4']})
308
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
309
self.assertEqual([['rev4',], ['rev3']],
310
stacked.get_parents(['rev1', 'rev2']))
311
self.assertEqual([['rev3',], ['rev4']],
312
stacked.get_parents(['rev2', 'rev1']))
313
self.assertEqual([['rev3',], ['rev3']],
314
stacked.get_parents(['rev2', 'rev2']))
315
self.assertEqual([['rev4',], ['rev4']],
316
stacked.get_parents(['rev1', 'rev1']))
318
def test_iter_topo_order(self):
319
graph = self.make_graph(ancestry_1)
320
args = ['rev2a', 'rev3', 'rev1']
321
topo_args = list(graph.iter_topo_order(args))
322
self.assertEqual(set(args), set(topo_args))
323
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
324
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
326
def test_is_ancestor(self):
327
graph = self.make_graph(ancestry_1)
328
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
329
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
330
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
331
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
332
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
333
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
334
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
335
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
336
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
337
instrumented_provider = InstrumentedParentsProvider(graph)
338
instrumented_graph = _mod_graph.Graph(instrumented_provider)
339
instrumented_graph.is_ancestor('rev2a', 'rev2b')
340
self.assertTrue('null:' not in instrumented_provider.calls)
342
def test_is_ancestor_boundary(self):
343
"""Ensure that we avoid searching the whole graph.
345
This requires searching through b as a common ancestor, so we
346
can identify that e is common.
348
graph = self.make_graph(boundary)
349
instrumented_provider = InstrumentedParentsProvider(graph)
350
graph = _mod_graph.Graph(instrumented_provider)
351
self.assertFalse(graph.is_ancestor('a', 'c'))
352
self.assertTrue('null:' not in instrumented_provider.calls)
354
def test_filter_candidate_lca(self):
355
"""Test filter_candidate_lca for a corner case
357
This tests the case where we encounter the end of iteration for 'e'
358
in the same pass as we discover that 'd' is an ancestor of 'e', and
359
therefore 'e' can't be an lca.
361
To compensate for different dict orderings on other Python
362
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
364
# This test is sensitive to the iteration order of dicts. It will
365
# pass incorrectly if 'e' and 'a' sort before 'c'
374
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
375
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
376
self.assertEqual(['c'], graph._filter_candidate_lca(['a', 'c', 'e']))
added
removed
bzrlib/tests/test_graph.py
