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 TestGraph(TestCaseWithMemoryTransport):
150
def make_graph(self, ancestors):
151
tree = self.prepare_memory_tree('.')
152
self.build_ancestry(tree, ancestors)
153
self.addCleanup(tree.unlock)
154
return tree.branch.repository.get_graph()
156
def prepare_memory_tree(self, location):
157
tree = self.make_branch_and_memory_tree(location)
162
def build_ancestry(self, tree, ancestors):
163
"""Create an ancestry as specified by a graph dict
165
:param tree: A tree to use
166
:param ancestors: a dict of {node: [node_parent, ...]}
168
pending = [NULL_REVISION]
170
for descendant, parents in ancestors.iteritems():
171
for parent in parents:
172
descendants.setdefault(parent, []).append(descendant)
173
while len(pending) > 0:
174
cur_node = pending.pop()
175
for descendant in descendants.get(cur_node, []):
176
if tree.branch.repository.has_revision(descendant):
178
parents = [p for p in ancestors[descendant] if p is not
180
if len([p for p in parents if not
181
tree.branch.repository.has_revision(p)]) > 0:
183
tree.set_parent_ids(parents)
185
left_parent = parents[0]
187
left_parent = NULL_REVISION
188
tree.branch.set_last_revision_info(
189
len(tree.branch._lefthand_history(left_parent)),
191
tree.commit(descendant, rev_id=descendant)
192
pending.append(descendant)
195
"""Test finding least common ancestor.
197
ancestry_1 should always have a single common ancestor
199
graph = self.make_graph(ancestry_1)
200
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
201
self.assertEqual(set([NULL_REVISION]),
202
graph.find_lca(NULL_REVISION, NULL_REVISION))
203
self.assertEqual(set([NULL_REVISION]),
204
graph.find_lca(NULL_REVISION, 'rev1'))
205
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
206
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
208
def test_no_unique_lca(self):
209
"""Test error when one revision is not in the graph"""
210
graph = self.make_graph(ancestry_1)
211
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
214
def test_lca_criss_cross(self):
215
"""Test least-common-ancestor after a criss-cross merge."""
216
graph = self.make_graph(criss_cross)
217
self.assertEqual(set(['rev2a', 'rev2b']),
218
graph.find_lca('rev3a', 'rev3b'))
219
self.assertEqual(set(['rev2b']),
220
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
222
def test_lca_shortcut(self):
223
"""Test least-common ancestor on this history shortcut"""
224
graph = self.make_graph(history_shortcut)
225
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
227
def test_recursive_unique_lca(self):
228
"""Test finding a unique least common ancestor.
230
ancestry_1 should always have a single common ancestor
232
graph = self.make_graph(ancestry_1)
233
self.assertEqual(NULL_REVISION,
234
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
235
self.assertEqual(NULL_REVISION,
236
graph.find_unique_lca(NULL_REVISION, 'rev1'))
237
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
238
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
239
self.assertEqual(('rev1', 1,),
240
graph.find_unique_lca('rev2a', 'rev2b',
243
def test_unique_lca_criss_cross(self):
244
"""Ensure we don't pick non-unique lcas in a criss-cross"""
245
graph = self.make_graph(criss_cross)
246
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
247
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
248
self.assertEqual('rev1', lca)
249
self.assertEqual(2, steps)
251
def test_unique_lca_null_revision(self):
252
"""Ensure we pick NULL_REVISION when necessary"""
253
graph = self.make_graph(criss_cross2)
254
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
255
self.assertEqual(NULL_REVISION,
256
graph.find_unique_lca('rev2a', 'rev2b'))
258
def test_unique_lca_null_revision2(self):
259
"""Ensure we pick NULL_REVISION when necessary"""
260
graph = self.make_graph(ancestry_2)
261
self.assertEqual(NULL_REVISION,
262
graph.find_unique_lca('rev4a', 'rev1b'))
264
def test_common_ancestor_two_repos(self):
265
"""Ensure we do unique_lca using data from two repos"""
266
mainline_tree = self.prepare_memory_tree('mainline')
267
self.build_ancestry(mainline_tree, mainline)
268
self.addCleanup(mainline_tree.unlock)
270
# This is cheating, because the revisions in the graph are actually
271
# different revisions, despite having the same revision-id.
272
feature_tree = self.prepare_memory_tree('feature')
273
self.build_ancestry(feature_tree, feature_branch)
274
self.addCleanup(feature_tree.unlock)
276
graph = mainline_tree.branch.repository.get_graph(
277
feature_tree.branch.repository)
278
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
280
def test_graph_difference(self):
281
graph = self.make_graph(ancestry_1)
282
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
283
self.assertEqual((set(), set(['rev1'])),
284
graph.find_difference(NULL_REVISION, 'rev1'))
285
self.assertEqual((set(['rev1']), set()),
286
graph.find_difference('rev1', NULL_REVISION))
287
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
288
graph.find_difference('rev3', 'rev2b'))
289
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
290
graph.find_difference('rev4', 'rev2b'))
292
def test_graph_difference_criss_cross(self):
293
graph = self.make_graph(criss_cross)
294
self.assertEqual((set(['rev3a']), set(['rev3b'])),
295
graph.find_difference('rev3a', 'rev3b'))
296
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
297
graph.find_difference('rev2a', 'rev3b'))
299
def test_stacked_parents_provider(self):
301
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
302
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
303
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
304
self.assertEqual([['rev4',], ['rev3']],
305
stacked.get_parents(['rev1', 'rev2']))
306
self.assertEqual([['rev3',], ['rev4']],
307
stacked.get_parents(['rev2', 'rev1']))
308
self.assertEqual([['rev3',], ['rev3']],
309
stacked.get_parents(['rev2', 'rev2']))
310
self.assertEqual([['rev4',], ['rev4']],
311
stacked.get_parents(['rev1', 'rev1']))
313
def test_iter_topo_order(self):
314
graph = self.make_graph(ancestry_1)
315
args = ['rev2a', 'rev3', 'rev1']
316
topo_args = list(graph.iter_topo_order(args))
317
self.assertEqual(set(args), set(topo_args))
318
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
319
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
321
def test_is_ancestor(self):
322
graph = self.make_graph(ancestry_1)
323
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
324
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
325
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
326
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
327
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
328
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
329
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
330
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
331
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
332
instrumented_provider = InstrumentedParentsProvider(graph)
333
instrumented_graph = _mod_graph.Graph(instrumented_provider)
334
instrumented_graph.is_ancestor('rev2a', 'rev2b')
335
self.assertTrue('null:' not in instrumented_provider.calls)
337
def test_is_ancestor_boundary(self):
338
"""Ensure that we avoid searching the whole graph.
340
This requires searching through b as a common ancestor, so we
341
can identify that e is common.
343
graph = self.make_graph(boundary)
344
instrumented_provider = InstrumentedParentsProvider(graph)
345
graph = _mod_graph.Graph(instrumented_provider)
346
self.assertFalse(graph.is_ancestor('a', 'c'))
347
self.assertTrue('null:' not in instrumented_provider.calls)
349
def test_filter_candidate_lca(self):
350
"""Test filter_candidate_lca for a corner case
352
This tests the case where we encounter the end of iteration for 'e'
353
in the same pass as we discover that 'd' is an ancestor of 'e', and
354
therefore 'e' can't be an lca.
356
To compensate for different dict orderings on other Python
357
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
359
# This test is sensitive to the iteration order of dicts. It will
360
# pass incorrectly if 'e' and 'a' sort before 'c'
369
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
370
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
371
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
373
def test_heads_null(self):
374
graph = self.make_graph(ancestry_1)
375
self.assertEqual(set(['null:']), graph.heads(['null:']))
376
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
377
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
378
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
379
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
381
def test_heads_one(self):
382
# A single node will always be a head
383
graph = self.make_graph(ancestry_1)
384
self.assertEqual(set(['null:']), graph.heads(['null:']))
385
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
386
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
387
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
388
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
389
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
391
def test_heads_single(self):
392
graph = self.make_graph(ancestry_1)
393
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
394
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
395
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
396
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
397
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
398
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
399
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
400
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
402
def test_heads_two_heads(self):
403
graph = self.make_graph(ancestry_1)
404
self.assertEqual(set(['rev2a', 'rev2b']),
405
graph.heads(['rev2a', 'rev2b']))
406
self.assertEqual(set(['rev3', 'rev2b']),
407
graph.heads(['rev3', 'rev2b']))
409
def test_heads_criss_cross(self):
410
graph = self.make_graph(criss_cross)
411
self.assertEqual(set(['rev2a']),
412
graph.heads(['rev2a', 'rev1']))
413
self.assertEqual(set(['rev2b']),
414
graph.heads(['rev2b', 'rev1']))
415
self.assertEqual(set(['rev3a']),
416
graph.heads(['rev3a', 'rev1']))
417
self.assertEqual(set(['rev3b']),
418
graph.heads(['rev3b', 'rev1']))
419
self.assertEqual(set(['rev2a', 'rev2b']),
420
graph.heads(['rev2a', 'rev2b']))
421
self.assertEqual(set(['rev3a']),
422
graph.heads(['rev3a', 'rev2a']))
423
self.assertEqual(set(['rev3a']),
424
graph.heads(['rev3a', 'rev2b']))
425
self.assertEqual(set(['rev3a']),
426
graph.heads(['rev3a', 'rev2a', 'rev2b']))
427
self.assertEqual(set(['rev3b']),
428
graph.heads(['rev3b', 'rev2a']))
429
self.assertEqual(set(['rev3b']),
430
graph.heads(['rev3b', 'rev2b']))
431
self.assertEqual(set(['rev3b']),
432
graph.heads(['rev3b', 'rev2a', 'rev2b']))
433
self.assertEqual(set(['rev3a', 'rev3b']),
434
graph.heads(['rev3a', 'rev3b']))
435
self.assertEqual(set(['rev3a', 'rev3b']),
436
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
438
def test_heads_shortcut(self):
439
graph = self.make_graph(history_shortcut)
441
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
442
graph.heads(['rev2a', 'rev2b', 'rev2c']))
443
self.assertEqual(set(['rev3a', 'rev3b']),
444
graph.heads(['rev3a', 'rev3b']))
445
self.assertEqual(set(['rev3a', 'rev3b']),
446
graph.heads(['rev2a', 'rev3a', 'rev3b']))
447
self.assertEqual(set(['rev2a', 'rev3b']),
448
graph.heads(['rev2a', 'rev3b']))
449
self.assertEqual(set(['rev2c', 'rev3a']),
450
graph.heads(['rev2c', 'rev3a']))
452
def _run_heads_break_deeper(self, graph_dict, search):
453
"""Run heads on a graph-as-a-dict.
455
If the search asks for the parents of 'deeper' the test will fail.
459
def get_parents(keys):
463
self.fail('key deeper was accessed')
464
result.append(graph_dict[key])
467
an_obj.get_parents = get_parents
468
graph = _mod_graph.Graph(an_obj)
469
return graph.heads(search)
471
def test_heads_limits_search(self):
472
# test that a heads query does not search all of history
478
self.assertEqual(set(['left', 'right']),
479
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
481
def test_heads_limits_search_assymetric(self):
482
# test that a heads query does not search all of history
485
'midleft':['common'],
487
'common':['aftercommon'],
488
'aftercommon':['deeper'],
490
self.assertEqual(set(['left', 'right']),
491
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
493
def test_heads_limits_search_common_search_must_continue(self):
494
# test that common nodes are still queried, preventing
495
# all-the-way-to-origin behaviour in the following graph:
497
'h1':['shortcut', 'common1'],
499
'shortcut':['common2'],
500
'common1':['common2'],
501
'common2':['deeper'],
503
self.assertEqual(set(['h1', 'h2']),
504
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
added
removed
bzrlib/tests/test_graph.py
