161
def old_common_ancestor(revision_a, revision_b, revision_source):
162
"""Find the ancestor common to both revisions that is closest to both.
164
from bzrlib.trace import mutter
165
a_ancestors = find_present_ancestors(revision_a, revision_source)
166
b_ancestors = find_present_ancestors(revision_b, revision_source)
169
# a_order is used as a tie-breaker when two equally-good bases are found
170
for revision, (a_order, a_distance) in a_ancestors.iteritems():
171
if b_ancestors.has_key(revision):
172
a_intersection.append((a_distance, a_order, revision))
173
b_intersection.append((b_ancestors[revision][1], a_order, revision))
174
mutter("a intersection: %r", a_intersection)
175
mutter("b intersection: %r", b_intersection)
177
a_closest = __get_closest(a_intersection)
178
if len(a_closest) == 0:
180
b_closest = __get_closest(b_intersection)
181
assert len(b_closest) != 0
182
mutter ("a_closest %r", a_closest)
183
mutter ("b_closest %r", b_closest)
184
if a_closest[0] in b_closest:
186
elif b_closest[0] in a_closest:
189
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
192
163
def revision_graph(revision, revision_source):
193
164
"""Produce a graph of the ancestry of the specified revision.
194
Return root, ancestors map, descendants map
196
TODO: Produce graphs with the NULL revision as root, so that we can find
197
a common even when trees are not branches don't represent a single line
199
RBC: 20051024: note that when we have two partial histories, this may not
200
be possible. But if we are willing to pretend :)... sure.
166
:return: root, ancestors map, descendants map
168
revision_source.lock_read()
170
return _revision_graph(revision, revision_source)
172
revision_source.unlock()
175
def _revision_graph(revision, revision_source):
176
"""See revision_graph."""
177
from bzrlib.tsort import topo_sort
178
graph = revision_source.get_revision_graph(revision)
179
# mark all no-parent revisions as being NULL_REVISION parentage.
180
for node, parents in graph.items():
181
if len(parents) == 0:
182
graph[node] = [NULL_REVISION]
183
# add NULL_REVISION to the graph
184
graph[NULL_REVISION] = []
186
# pick a root. If there are multiple roots
187
# this could pick a random one.
188
topo_order = topo_sort(graph.items())
206
descendants[revision] = {}
207
while len(lines) > 0:
210
if line == NULL_REVISION:
215
rev = revision_source.get_revision(line)
216
parents = list(rev.parent_ids)
217
if len(parents) == 0:
218
parents = [NULL_REVISION]
219
except bzrlib.errors.NoSuchRevision:
223
if parents is not None:
224
for parent in parents:
225
if parent not in ancestors:
226
new_lines.add(parent)
227
if parent not in descendants:
228
descendants[parent] = {}
229
descendants[parent][line] = 1
230
if parents is not None:
231
ancestors[line] = set(parents)
234
# The history for revision becomes inaccessible without
235
# actually hitting a no-parents revision. This then
236
# makes these asserts below trigger. So, if root is None
237
# determine the actual root by walking the accessible tree
238
# and then stash NULL_REVISION at the end.
240
descendants[root] = {}
241
# for every revision, check we can access at least
242
# one parent, if we cant, add NULL_REVISION and
244
for rev in ancestors:
245
if len(ancestors[rev]) == 0:
246
raise RuntimeError('unreachable code ?!')
248
for parent in ancestors[rev]:
249
if parent in ancestors:
253
descendants[root][rev] = 1
254
ancestors[rev].add(root)
255
ancestors[root] = set()
194
# map the descendants of the graph.
195
# and setup our set based return graph.
196
for node in graph.keys():
197
descendants[node] = {}
198
for node, parents in graph.items():
199
for parent in parents:
200
descendants[parent][node] = 1
201
ancestors[node] = set(parents)
256
203
assert root not in descendants[root]
257
204
assert root not in ancestors[root]
258
205
return root, ancestors, descendants
261
208
def combined_graph(revision_a, revision_b, revision_source):
262
209
"""Produce a combined ancestry graph.
263
210
Return graph root, ancestors map, descendants map, set of common nodes"""
264
root, ancestors, descendants = revision_graph(revision_a, revision_source)
265
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
211
root, ancestors, descendants = revision_graph(
212
revision_a, revision_source)
213
root_b, ancestors_b, descendants_b = revision_graph(
214
revision_b, revision_source)
267
215
if root != root_b:
268
216
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
added
removed
bzrlib/revision.py
