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.deprecated_graph import (node_distances, select_farthest)
22
from bzrlib.revision import NULL_REVISION
24
# DIAGRAM of terminology
34
# In this diagram, relative to G and H:
35
# A, B, C, D, E are common ancestors.
36
# C, D and E are border ancestors, because each has a non-common descendant.
37
# D and E are least common ancestors because none of their descendants are
39
# C is not a least common ancestor because its descendant, E, is a common
42
# The find_unique_lca algorithm will pick A in two steps:
43
# 1. find_lca('G', 'H') => ['D', 'E']
44
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
48
class _StackedParentsProvider(object):
50
def __init__(self, parent_providers):
51
self._parent_providers = parent_providers
54
return "_StackedParentsProvider(%r)" % self._parent_providers
56
def get_parents(self, revision_ids):
57
"""Find revision ids of the parents of a list of revisions
59
A list is returned of the same length as the input. Each entry
60
is a list of parent ids for the corresponding input revision.
62
[NULL_REVISION] is used as the parent of the first user-committed
63
revision. Its parent list is empty.
65
If the revision is not present (i.e. a ghost), None is used in place
66
of the list of parents.
69
for parents_provider in self._parent_providers:
70
pending_revisions = [r for r in revision_ids if r not in found]
71
parent_list = parents_provider.get_parents(pending_revisions)
72
new_found = dict((k, v) for k, v in zip(pending_revisions,
73
parent_list) if v is not None)
74
found.update(new_found)
75
if len(found) == len(revision_ids):
77
return [found.get(r, None) for r in revision_ids]
81
"""Provide incremental access to revision graphs.
83
This is the generic implementation; it is intended to be subclassed to
84
specialize it for other repository types.
87
def __init__(self, parents_provider):
88
"""Construct a Graph that uses several graphs as its input
90
This should not normally be invoked directly, because there may be
91
specialized implementations for particular repository types. See
92
Repository.get_graph()
94
:param parents_func: an object providing a get_parents call
95
conforming to the behavior of StackedParentsProvider.get_parents
97
self.get_parents = parents_provider.get_parents
98
self._parents_provider = parents_provider
101
return 'Graph(%r)' % self._parents_provider
103
def find_lca(self, *revisions):
104
"""Determine the lowest common ancestors of the provided revisions
106
A lowest common ancestor is a common ancestor none of whose
107
descendants are common ancestors. In graphs, unlike trees, there may
108
be multiple lowest common ancestors.
110
This algorithm has two phases. Phase 1 identifies border ancestors,
111
and phase 2 filters border ancestors to determine lowest common
114
In phase 1, border ancestors are identified, using a breadth-first
115
search starting at the bottom of the graph. Searches are stopped
116
whenever a node or one of its descendants is determined to be common
118
In phase 2, the border ancestors are filtered to find the least
119
common ancestors. This is done by searching the ancestries of each
122
Phase 2 is perfomed on the principle that a border ancestor that is
123
not an ancestor of any other border ancestor is a least common
126
Searches are stopped when they find a node that is determined to be a
127
common ancestor of all border ancestors, because this shows that it
128
cannot be a descendant of any border ancestor.
130
The scaling of this operation should be proportional to
131
1. The number of uncommon ancestors
132
2. The number of border ancestors
133
3. The length of the shortest path between a border ancestor and an
134
ancestor of all border ancestors.
136
border_common, common, sides = self._find_border_ancestors(revisions)
137
return self._filter_candidate_lca(border_common)
139
def find_difference(self, left_revision, right_revision):
140
"""Determine the graph difference between two revisions"""
141
border, common, (left, right) = self._find_border_ancestors(
142
[left_revision, right_revision])
143
return (left.difference(right).difference(common),
144
right.difference(left).difference(common))
146
def _make_breadth_first_searcher(self, revisions):
147
return _BreadthFirstSearcher(revisions, self)
149
def _find_border_ancestors(self, revisions):
150
"""Find common ancestors with at least one uncommon descendant.
152
Border ancestors are identified using a breadth-first
153
search starting at the bottom of the graph. Searches are stopped
154
whenever a node or one of its descendants is determined to be common.
156
This will scale with the number of uncommon ancestors.
158
As well as the border ancestors, a set of seen common ancestors and a
159
list of sets of seen ancestors for each input revision is returned.
160
This allows calculation of graph difference from the results of this
163
if None in revisions:
164
raise errors.InvalidRevisionId(None, self)
165
common_searcher = self._make_breadth_first_searcher([])
166
common_ancestors = set()
167
searchers = [self._make_breadth_first_searcher([r])
169
active_searchers = searchers[:]
170
border_ancestors = set()
171
def update_common(searcher, revisions):
172
w_seen_ancestors = searcher.find_seen_ancestors(
174
stopped = searcher.stop_searching_any(w_seen_ancestors)
175
common_ancestors.update(w_seen_ancestors)
176
common_searcher.start_searching(stopped)
179
if len(active_searchers) == 0:
180
return border_ancestors, common_ancestors, [s.seen for s in
183
new_common = common_searcher.next()
184
common_ancestors.update(new_common)
185
except StopIteration:
188
for searcher in active_searchers:
189
for revision in new_common.intersection(searcher.seen):
190
update_common(searcher, revision)
193
new_active_searchers = []
194
for searcher in active_searchers:
196
newly_seen.update(searcher.next())
197
except StopIteration:
200
new_active_searchers.append(searcher)
201
active_searchers = new_active_searchers
202
for revision in newly_seen:
203
if revision in common_ancestors:
204
for searcher in searchers:
205
update_common(searcher, revision)
207
for searcher in searchers:
208
if revision not in searcher.seen:
211
border_ancestors.add(revision)
212
for searcher in searchers:
213
update_common(searcher, revision)
215
def _filter_candidate_lca(self, candidate_lca):
216
"""Remove candidates which are ancestors of other candidates.
218
This is done by searching the ancestries of each border ancestor. It
219
is perfomed on the principle that a border ancestor that is not an
220
ancestor of any other border ancestor is a lowest common ancestor.
222
Searches are stopped when they find a node that is determined to be a
223
common ancestor of all border ancestors, because this shows that it
224
cannot be a descendant of any border ancestor.
226
This will scale with the number of candidate ancestors and the length
227
of the shortest path from a candidate to an ancestor common to all
230
searchers = dict((c, self._make_breadth_first_searcher([c]))
231
for c in candidate_lca)
232
active_searchers = dict(searchers)
233
# skip over the actual candidate for each searcher
234
for searcher in active_searchers.itervalues():
236
while len(active_searchers) > 0:
237
for candidate in active_searchers.keys():
239
searcher = active_searchers[candidate]
241
# rare case: we deleted candidate in a previous iteration
242
# through this for loop, because it was determined to be
243
# a descendant of another candidate.
246
ancestors = searcher.next()
247
except StopIteration:
248
del active_searchers[candidate]
250
for ancestor in ancestors:
251
if ancestor in candidate_lca:
252
candidate_lca.remove(ancestor)
253
del searchers[ancestor]
254
if ancestor in active_searchers:
255
del active_searchers[ancestor]
256
for searcher in searchers.itervalues():
257
if ancestor not in searcher.seen:
260
# if this revision was seen by all searchers, then it
261
# is a descendant of all candidates, so we can stop
262
# searching it, and any seen ancestors
263
for searcher in searchers.itervalues():
265
searcher.find_seen_ancestors(ancestor)
266
searcher.stop_searching_any(seen_ancestors)
269
def find_unique_lca(self, left_revision, right_revision):
270
"""Find a unique LCA.
272
Find lowest common ancestors. If there is no unique common
273
ancestor, find the lowest common ancestors of those ancestors.
275
Iteration stops when a unique lowest common ancestor is found.
276
The graph origin is necessarily a unique lowest common ancestor.
278
Note that None is not an acceptable substitute for NULL_REVISION.
279
in the input for this method.
281
revisions = [left_revision, right_revision]
283
lca = self.find_lca(*revisions)
287
raise errors.NoCommonAncestor(left_revision, right_revision)
290
def iter_topo_order(self, revisions):
291
"""Iterate through the input revisions in topological order.
293
This sorting only ensures that parents come before their children.
294
An ancestor may sort after a descendant if the relationship is not
295
visible in the supplied list of revisions.
297
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
298
return sorter.iter_topo_order()
300
def is_ancestor(self, candidate_ancestor, candidate_descendant):
301
"""Determine whether a revision is an ancestor of another.
303
There are two possible outcomes: True and False, but there are three
304
possible relationships:
306
a) candidate_ancestor is an ancestor of candidate_descendant
307
b) candidate_ancestor is an descendant of candidate_descendant
308
c) candidate_ancestor is an sibling of candidate_descendant
310
To check for a, we walk from candidate_descendant, looking for
313
To check for b, we walk from candidate_ancestor, looking for
314
candidate_descendant.
316
To make a and b more efficient, we can stop any searches that hit
319
If we exhaust our searches, but neither a or b is true, then c is true.
321
In order to find c efficiently, we must avoid searching from
322
candidate_descendant or candidate_ancestor into common ancestors. But
323
if we don't search common ancestors at all, we won't know if we hit
324
common ancestors. So we have a walker for common ancestors. Note that
325
its searches are not required to terminate in order to determine c to
328
ancestor_walker = self._make_breadth_first_searcher(
329
[candidate_ancestor])
330
descendant_walker = self._make_breadth_first_searcher(
331
[candidate_descendant])
332
common_walker = self._make_breadth_first_searcher([])
333
active_ancestor = True
334
active_descendant = True
335
while (active_ancestor or active_descendant):
337
if active_descendant:
339
nodes = descendant_walker.next()
340
except StopIteration:
341
active_descendant = False
343
if candidate_ancestor in nodes:
345
new_common.update(nodes.intersection(ancestor_walker.seen))
348
nodes = ancestor_walker.next()
349
except StopIteration:
350
active_ancestor = False
352
if candidate_descendant in nodes:
354
new_common.update(nodes.intersection(
355
descendant_walker.seen))
357
new_common.update(common_walker.next())
358
except StopIteration:
360
for walker in (ancestor_walker, descendant_walker):
361
for node in new_common:
362
c_ancestors = walker.find_seen_ancestors(node)
363
walker.stop_searching_any(c_ancestors)
364
common_walker.start_searching(new_common)
368
class _BreadthFirstSearcher(object):
369
"""Parallel search the breadth-first the ancestry of revisions.
371
This class implements the iterator protocol, but additionally
372
1. provides a set of seen ancestors, and
373
2. allows some ancestries to be unsearched, via stop_searching_any
376
def __init__(self, revisions, parents_provider):
377
self._start = set(revisions)
378
self._search_revisions = None
379
self.seen = set(revisions)
380
self._parents_provider = parents_provider
383
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
384
' self.seen=%r)' % (self._search_revisions, self.seen))
387
"""Return the next ancestors of this revision.
389
Ancestors are returned in the order they are seen in a breadth-first
390
traversal. No ancestor will be returned more than once.
392
if self._search_revisions is None:
393
self._search_revisions = self._start
395
new_search_revisions = set()
396
for parents in self._parents_provider.get_parents(
397
self._search_revisions):
400
new_search_revisions.update(p for p in parents if
402
self._search_revisions = new_search_revisions
403
if len(self._search_revisions) == 0:
404
raise StopIteration()
405
self.seen.update(self._search_revisions)
406
return self._search_revisions
411
def find_seen_ancestors(self, revision):
412
"""Find ancestors of this revision that have already been seen."""
413
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
414
seen_ancestors = set()
415
for ancestors in searcher:
416
for ancestor in ancestors:
417
if ancestor not in self.seen:
418
searcher.stop_searching_any([ancestor])
420
seen_ancestors.add(ancestor)
421
return seen_ancestors
423
def stop_searching_any(self, revisions):
425
Remove any of the specified revisions from the search list.
427
None of the specified revisions are required to be present in the
428
search list. In this case, the call is a no-op.
430
stopped = self._search_revisions.intersection(revisions)
431
self._search_revisions = self._search_revisions.difference(revisions)
434
def start_searching(self, revisions):
435
if self._search_revisions is None:
436
self._start = set(revisions)
438
self._search_revisions.update(revisions.difference(self.seen))
439
self.seen.update(revisions)
added
removed
bzrlib/graph.py
