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(set(['c']), graph.heads(['a', 'c', 'e']))
378
def test_heads_null(self):
379
graph = self.make_graph(ancestry_1)
380
self.assertEqual(set(['null:']), graph.heads(['null:']))
381
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
382
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
383
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
384
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
386
def test_heads_one(self):
387
# A single node will alwaya be a head
388
graph = self.make_graph(ancestry_1)
389
self.assertEqual(set(['null:']), graph.heads(['null:']))
390
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
391
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
392
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
393
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
394
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
396
def test_heads_single(self):
397
graph = self.make_graph(ancestry_1)
398
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
399
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
400
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
401
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
402
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
403
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
404
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
405
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
407
def test_heads_two_heads(self):
408
graph = self.make_graph(ancestry_1)
409
self.assertEqual(set(['rev2a', 'rev2b']),
410
graph.heads(['rev2a', 'rev2b']))
411
self.assertEqual(set(['rev3', 'rev2b']),
412
graph.heads(['rev3', 'rev2b']))
414
def test_heads_criss_cross(self):
415
graph = self.make_graph(criss_cross)
416
self.assertEqual(set(['rev2a']),
417
graph.heads(['rev2a', 'rev1']))
418
self.assertEqual(set(['rev2b']),
419
graph.heads(['rev2b', 'rev1']))
420
self.assertEqual(set(['rev3a']),
421
graph.heads(['rev3a', 'rev1']))
422
self.assertEqual(set(['rev3b']),
423
graph.heads(['rev3b', 'rev1']))
424
self.assertEqual(set(['rev2a', 'rev2b']),
425
graph.heads(['rev2a', 'rev2b']))
426
self.assertEqual(set(['rev3a']),
427
graph.heads(['rev3a', 'rev2a']))
428
self.assertEqual(set(['rev3a']),
429
graph.heads(['rev3a', 'rev2b']))
430
self.assertEqual(set(['rev3a']),
431
graph.heads(['rev3a', 'rev2a', 'rev2b']))
432
self.assertEqual(set(['rev3b']),
433
graph.heads(['rev3b', 'rev2a']))
434
self.assertEqual(set(['rev3b']),
435
graph.heads(['rev3b', 'rev2b']))
436
self.assertEqual(set(['rev3b']),
437
graph.heads(['rev3b', 'rev2a', 'rev2b']))
438
self.assertEqual(set(['rev3a', 'rev3b']),
439
graph.heads(['rev3a', 'rev3b']))
440
self.assertEqual(set(['rev3a', 'rev3b']),
441
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
443
def test_heads_shortcut(self):
444
graph = self.make_graph(history_shortcut)
446
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
447
graph.heads(['rev2a', 'rev2b', 'rev2c']))
448
self.assertEqual(set(['rev3a', 'rev3b']),
449
graph.heads(['rev3a', 'rev3b']))
450
self.assertEqual(set(['rev3a', 'rev3b']),
451
graph.heads(['rev2a', 'rev3a', 'rev3b']))
452
self.assertEqual(set(['rev2a', 'rev3b']),
453
graph.heads(['rev2a', 'rev3b']))
454
self.assertEqual(set(['rev2c', 'rev3a']),
455
graph.heads(['rev2c', 'rev3a']))
added
removed
bzrlib/tests/test_graph.py
