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_no_unique_lca(self):
185
"""Test error when one revision is not in the graph"""
186
graph = self.make_graph(ancestry_1)
187
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
190
def test_lca_criss_cross(self):
191
"""Test least-common-ancestor after a criss-cross merge."""
192
graph = self.make_graph(criss_cross)
193
self.assertEqual(set(['rev2a', 'rev2b']),
194
graph.find_lca('rev3a', 'rev3b'))
195
self.assertEqual(set(['rev2b']),
196
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
198
def test_lca_shortcut(self):
199
"""Test least-common ancestor on this history shortcut"""
200
graph = self.make_graph(history_shortcut)
201
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
203
def test_recursive_unique_lca(self):
204
"""Test finding a unique least common ancestor.
206
ancestry_1 should always have a single common ancestor
208
graph = self.make_graph(ancestry_1)
209
self.assertEqual(NULL_REVISION,
210
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
211
self.assertEqual(NULL_REVISION,
212
graph.find_unique_lca(NULL_REVISION, 'rev1'))
213
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
214
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
216
def test_unique_lca_criss_cross(self):
217
"""Ensure we don't pick non-unique lcas in a criss-cross"""
218
graph = self.make_graph(criss_cross)
219
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
221
def test_unique_lca_null_revision(self):
222
"""Ensure we pick NULL_REVISION when necessary"""
223
graph = self.make_graph(criss_cross2)
224
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
225
self.assertEqual(NULL_REVISION,
226
graph.find_unique_lca('rev2a', 'rev2b'))
228
def test_unique_lca_null_revision2(self):
229
"""Ensure we pick NULL_REVISION when necessary"""
230
graph = self.make_graph(ancestry_2)
231
self.assertEqual(NULL_REVISION,
232
graph.find_unique_lca('rev4a', 'rev1b'))
234
def test_common_ancestor_two_repos(self):
235
"""Ensure we do unique_lca using data from two repos"""
236
mainline_tree = self.prepare_memory_tree('mainline')
237
self.build_ancestry(mainline_tree, mainline)
238
mainline_tree.unlock()
240
# This is cheating, because the revisions in the graph are actually
241
# different revisions, despite having the same revision-id.
242
feature_tree = self.prepare_memory_tree('feature')
243
self.build_ancestry(feature_tree, feature_branch)
244
feature_tree.unlock()
245
graph = mainline_tree.branch.repository.get_graph(
246
feature_tree.branch.repository)
247
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
249
def test_graph_difference(self):
250
graph = self.make_graph(ancestry_1)
251
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
252
self.assertEqual((set(), set(['rev1'])),
253
graph.find_difference(NULL_REVISION, 'rev1'))
254
self.assertEqual((set(['rev1']), set()),
255
graph.find_difference('rev1', NULL_REVISION))
256
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
257
graph.find_difference('rev3', 'rev2b'))
258
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
259
graph.find_difference('rev4', 'rev2b'))
261
def test_graph_difference_criss_cross(self):
262
graph = self.make_graph(criss_cross)
263
self.assertEqual((set(['rev3a']), set(['rev3b'])),
264
graph.find_difference('rev3a', 'rev3b'))
265
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
266
graph.find_difference('rev2a', 'rev3b'))
268
def test_stacked_parents_provider(self):
270
class ParentsProvider(object):
272
def __init__(self, ancestry):
273
self.ancestry = ancestry
275
def get_parents(self, revisions):
276
return [self.ancestry.get(r, None) for r in revisions]
278
parents1 = ParentsProvider({'rev2': ['rev3']})
279
parents2 = ParentsProvider({'rev1': ['rev4']})
280
stacked = graph._StackedParentsProvider([parents1, parents2])
281
self.assertEqual([['rev4',], ['rev3']],
282
stacked.get_parents(['rev1', 'rev2']))
283
self.assertEqual([['rev3',], ['rev4']],
284
stacked.get_parents(['rev2', 'rev1']))
285
self.assertEqual([['rev3',], ['rev3']],
286
stacked.get_parents(['rev2', 'rev2']))
287
self.assertEqual([['rev4',], ['rev4']],
288
stacked.get_parents(['rev1', 'rev1']))
290
def test_iter_topo_order(self):
291
graph = self.make_graph(ancestry_1)
292
args = ['rev2a', 'rev3', 'rev1']
293
topo_args = list(graph.iter_topo_order(args))
294
self.assertEqual(set(args), set(topo_args))
295
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
296
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
added
removed
bzrlib/tests/test_graph.py
