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
23
from bzrlib.deprecated_graph import (node_distances, select_farthest)
25
# DIAGRAM of terminology
35
# In this diagram, relative to G and H:
36
# A, B, C, D, E are common ancestors.
37
# C, D and E are border ancestors, because each has a non-common descendant.
38
# D and E are least common ancestors because none of their descendants are
40
# C is not a least common ancestor because its descendant, E, is a common
43
# The find_unique_lca algorithm will pick A in two steps:
44
# 1. find_lca('G', 'H') => ['D', 'E']
45
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
48
class DictParentsProvider(object):
50
def __init__(self, ancestry):
51
self.ancestry = ancestry
54
return 'DictParentsProvider(%r)' % self.ancestry
56
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
57
def get_parents(self, revisions):
58
return [self.ancestry.get(r, None) for r in revisions]
60
def get_parent_map(self, keys):
61
"""See _StackedParentsProvider.get_parent_map"""
62
ancestry = self.ancestry
63
return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
class _StackedParentsProvider(object):
68
def __init__(self, parent_providers):
69
self._parent_providers = parent_providers
72
return "_StackedParentsProvider(%r)" % self._parent_providers
74
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
75
def get_parents(self, revision_ids):
76
"""Find revision ids of the parents of a list of revisions
78
A list is returned of the same length as the input. Each entry
79
is a list of parent ids for the corresponding input revision.
81
[NULL_REVISION] is used as the parent of the first user-committed
82
revision. Its parent list is empty.
84
If the revision is not present (i.e. a ghost), None is used in place
85
of the list of parents.
87
found = self.get_parent_map(revision_ids)
88
return [found.get(r, None) for r in revision_ids]
90
def get_parent_map(self, keys):
91
"""Get a mapping of keys => parents
93
A dictionary is returned with an entry for each key present in this
94
source. If this source doesn't have information about a key, it should
97
[NULL_REVISION] is used as the parent of the first user-committed
98
revision. Its parent list is empty.
100
:param keys: An iterable returning keys to check (eg revision_ids)
101
:return: A dictionary mapping each key to its parents
104
remaining = set(keys)
105
for parents_provider in self._parent_providers:
106
new_found = parents_provider.get_parent_map(remaining)
107
found.update(new_found)
108
remaining.difference_update(new_found)
114
class CachingParentsProvider(object):
115
"""A parents provider which will cache the revision => parents in a dict.
117
This is useful for providers that have an expensive lookup.
120
def __init__(self, parent_provider):
121
self._real_provider = parent_provider
122
# Theoretically we could use an LRUCache here
126
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
128
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
129
def get_parents(self, revision_ids):
130
"""See _StackedParentsProvider.get_parents"""
131
found = self.get_parent_map(revision_ids)
132
return [found.get(r, None) for r in revision_ids]
134
def get_parent_map(self, keys):
135
"""See _StackedParentsProvider.get_parent_map"""
137
# If the _real_provider doesn't have a key, we cache a value of None,
138
# which we then later use to realize we cannot provide a value for that
145
if value is not None:
146
parent_map[key] = value
151
new_parents = self._real_provider.get_parent_map(needed)
152
cache.update(new_parents)
153
parent_map.update(new_parents)
154
needed.difference_update(new_parents)
155
cache.update(dict.fromkeys(needed, None))
160
"""Provide incremental access to revision graphs.
162
This is the generic implementation; it is intended to be subclassed to
163
specialize it for other repository types.
166
def __init__(self, parents_provider):
167
"""Construct a Graph that uses several graphs as its input
169
This should not normally be invoked directly, because there may be
170
specialized implementations for particular repository types. See
171
Repository.get_graph()
173
:param parents_provider: An object providing a get_parents call
174
conforming to the behavior of StackedParentsProvider.get_parents
176
self.get_parents = parents_provider.get_parents
177
self.get_parent_map = parents_provider.get_parent_map
178
self._parents_provider = parents_provider
181
return 'Graph(%r)' % self._parents_provider
183
def find_lca(self, *revisions):
184
"""Determine the lowest common ancestors of the provided revisions
186
A lowest common ancestor is a common ancestor none of whose
187
descendants are common ancestors. In graphs, unlike trees, there may
188
be multiple lowest common ancestors.
190
This algorithm has two phases. Phase 1 identifies border ancestors,
191
and phase 2 filters border ancestors to determine lowest common
194
In phase 1, border ancestors are identified, using a breadth-first
195
search starting at the bottom of the graph. Searches are stopped
196
whenever a node or one of its descendants is determined to be common
198
In phase 2, the border ancestors are filtered to find the least
199
common ancestors. This is done by searching the ancestries of each
202
Phase 2 is perfomed on the principle that a border ancestor that is
203
not an ancestor of any other border ancestor is a least common
206
Searches are stopped when they find a node that is determined to be a
207
common ancestor of all border ancestors, because this shows that it
208
cannot be a descendant of any border ancestor.
210
The scaling of this operation should be proportional to
211
1. The number of uncommon ancestors
212
2. The number of border ancestors
213
3. The length of the shortest path between a border ancestor and an
214
ancestor of all border ancestors.
216
border_common, common, sides = self._find_border_ancestors(revisions)
217
# We may have common ancestors that can be reached from each other.
218
# - ask for the heads of them to filter it down to only ones that
219
# cannot be reached from each other - phase 2.
220
return self.heads(border_common)
222
def find_difference(self, left_revision, right_revision):
223
"""Determine the graph difference between two revisions"""
224
border, common, (left, right) = self._find_border_ancestors(
225
[left_revision, right_revision])
226
return (left.difference(right).difference(common),
227
right.difference(left).difference(common))
229
def _make_breadth_first_searcher(self, revisions):
230
return _BreadthFirstSearcher(revisions, self)
232
def _find_border_ancestors(self, revisions):
233
"""Find common ancestors with at least one uncommon descendant.
235
Border ancestors are identified using a breadth-first
236
search starting at the bottom of the graph. Searches are stopped
237
whenever a node or one of its descendants is determined to be common.
239
This will scale with the number of uncommon ancestors.
241
As well as the border ancestors, a set of seen common ancestors and a
242
list of sets of seen ancestors for each input revision is returned.
243
This allows calculation of graph difference from the results of this
246
if None in revisions:
247
raise errors.InvalidRevisionId(None, self)
248
common_searcher = self._make_breadth_first_searcher([])
249
common_ancestors = set()
250
searchers = [self._make_breadth_first_searcher([r])
252
active_searchers = searchers[:]
253
border_ancestors = set()
254
def update_common(searcher, revisions):
255
w_seen_ancestors = searcher.find_seen_ancestors(
257
stopped = searcher.stop_searching_any(w_seen_ancestors)
258
common_ancestors.update(w_seen_ancestors)
259
common_searcher.start_searching(stopped)
262
if len(active_searchers) == 0:
263
return border_ancestors, common_ancestors, [s.seen for s in
266
new_common = common_searcher.next()
267
common_ancestors.update(new_common)
268
except StopIteration:
271
for searcher in active_searchers:
272
for revision in new_common.intersection(searcher.seen):
273
update_common(searcher, revision)
276
new_active_searchers = []
277
for searcher in active_searchers:
279
newly_seen.update(searcher.next())
280
except StopIteration:
283
new_active_searchers.append(searcher)
284
active_searchers = new_active_searchers
285
for revision in newly_seen:
286
if revision in common_ancestors:
287
for searcher in searchers:
288
update_common(searcher, revision)
290
for searcher in searchers:
291
if revision not in searcher.seen:
294
border_ancestors.add(revision)
295
for searcher in searchers:
296
update_common(searcher, revision)
298
def heads(self, keys):
299
"""Return the heads from amongst keys.
301
This is done by searching the ancestries of each key. Any key that is
302
reachable from another key is not returned; all the others are.
304
This operation scales with the relative depth between any two keys. If
305
any two keys are completely disconnected all ancestry of both sides
308
:param keys: An iterable of keys.
309
:return: A set of the heads. Note that as a set there is no ordering
310
information. Callers will need to filter their input to create
311
order if they need it.
313
candidate_heads = set(keys)
314
if revision.NULL_REVISION in candidate_heads:
315
# NULL_REVISION is only a head if it is the only entry
316
candidate_heads.remove(revision.NULL_REVISION)
317
if not candidate_heads:
318
return set([revision.NULL_REVISION])
319
if len(candidate_heads) < 2:
320
return candidate_heads
321
searchers = dict((c, self._make_breadth_first_searcher([c]))
322
for c in candidate_heads)
323
active_searchers = dict(searchers)
324
# skip over the actual candidate for each searcher
325
for searcher in active_searchers.itervalues():
327
# The common walker finds nodes that are common to two or more of the
328
# input keys, so that we don't access all history when a currently
329
# uncommon search point actually meets up with something behind a
330
# common search point. Common search points do not keep searches
331
# active; they just allow us to make searches inactive without
332
# accessing all history.
333
common_walker = self._make_breadth_first_searcher([])
334
while len(active_searchers) > 0:
339
except StopIteration:
340
# No common points being searched at this time.
342
for candidate in active_searchers.keys():
344
searcher = active_searchers[candidate]
346
# rare case: we deleted candidate in a previous iteration
347
# through this for loop, because it was determined to be
348
# a descendant of another candidate.
351
ancestors.update(searcher.next())
352
except StopIteration:
353
del active_searchers[candidate]
355
# process found nodes
357
for ancestor in ancestors:
358
if ancestor in candidate_heads:
359
candidate_heads.remove(ancestor)
360
del searchers[ancestor]
361
if ancestor in active_searchers:
362
del active_searchers[ancestor]
363
# it may meet up with a known common node
364
if ancestor in common_walker.seen:
365
# some searcher has encountered our known common nodes:
367
ancestor_set = set([ancestor])
368
for searcher in searchers.itervalues():
369
searcher.stop_searching_any(ancestor_set)
371
# or it may have been just reached by all the searchers:
372
for searcher in searchers.itervalues():
373
if ancestor not in searcher.seen:
376
# The final active searcher has just reached this node,
377
# making it be known as a descendant of all candidates,
378
# so we can stop searching it, and any seen ancestors
379
new_common.add(ancestor)
380
for searcher in searchers.itervalues():
382
searcher.find_seen_ancestors(ancestor)
383
searcher.stop_searching_any(seen_ancestors)
384
common_walker.start_searching(new_common)
385
return candidate_heads
387
def find_unique_lca(self, left_revision, right_revision,
389
"""Find a unique LCA.
391
Find lowest common ancestors. If there is no unique common
392
ancestor, find the lowest common ancestors of those ancestors.
394
Iteration stops when a unique lowest common ancestor is found.
395
The graph origin is necessarily a unique lowest common ancestor.
397
Note that None is not an acceptable substitute for NULL_REVISION.
398
in the input for this method.
400
:param count_steps: If True, the return value will be a tuple of
401
(unique_lca, steps) where steps is the number of times that
402
find_lca was run. If False, only unique_lca is returned.
404
revisions = [left_revision, right_revision]
408
lca = self.find_lca(*revisions)
416
raise errors.NoCommonAncestor(left_revision, right_revision)
419
def iter_topo_order(self, revisions):
420
"""Iterate through the input revisions in topological order.
422
This sorting only ensures that parents come before their children.
423
An ancestor may sort after a descendant if the relationship is not
424
visible in the supplied list of revisions.
426
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
427
return sorter.iter_topo_order()
429
def is_ancestor(self, candidate_ancestor, candidate_descendant):
430
"""Determine whether a revision is an ancestor of another.
432
We answer this using heads() as heads() has the logic to perform the
433
smallest number of parent lookups to determine the ancestral
434
relationship between N revisions.
436
return set([candidate_descendant]) == self.heads(
437
[candidate_ancestor, candidate_descendant])
440
class HeadsCache(object):
441
"""A cache of results for graph heads calls."""
443
def __init__(self, graph):
447
def heads(self, keys):
448
"""Return the heads of keys.
450
This matches the API of Graph.heads(), specifically the return value is
451
a set which can be mutated, and ordering of the input is not preserved
454
:see also: Graph.heads.
455
:param keys: The keys to calculate heads for.
456
:return: A set containing the heads, which may be mutated without
457
affecting future lookups.
459
keys = frozenset(keys)
461
return set(self._heads[keys])
463
heads = self.graph.heads(keys)
464
self._heads[keys] = heads
468
class HeadsCache(object):
469
"""A cache of results for graph heads calls."""
471
def __init__(self, graph):
475
def heads(self, keys):
476
"""Return the heads of keys.
478
:see also: Graph.heads.
479
:param keys: The keys to calculate heads for.
480
:return: A set containing the heads, which may be mutated without
481
affecting future lookups.
483
keys = frozenset(keys)
485
return set(self._heads[keys])
487
heads = self.graph.heads(keys)
488
self._heads[keys] = heads
492
class _BreadthFirstSearcher(object):
493
"""Parallel search breadth-first the ancestry of revisions.
495
This class implements the iterator protocol, but additionally
496
1. provides a set of seen ancestors, and
497
2. allows some ancestries to be unsearched, via stop_searching_any
500
def __init__(self, revisions, parents_provider):
501
self._start = set(revisions)
502
self._search_revisions = None
503
self.seen = set(revisions)
504
self._parents_provider = parents_provider
507
if self._search_revisions is not None:
508
search = 'searching=%r' % (list(self._search_revisions),)
510
search = 'starting=%r' % (list(self._start),)
511
return ('_BreadthFirstSearcher(%s,'
512
' seen=%r)' % (search, list(self.seen)))
515
"""Return the next ancestors of this revision.
517
Ancestors are returned in the order they are seen in a breadth-first
518
traversal. No ancestor will be returned more than once.
520
if self._search_revisions is None:
521
self._search_revisions = self._start
523
new_search_revisions = set()
524
parent_map = self._parents_provider.get_parent_map(
525
self._search_revisions)
526
for parents in parent_map.itervalues():
527
new_search_revisions.update(p for p in parents if
529
self._search_revisions = new_search_revisions
530
if len(self._search_revisions) == 0:
531
raise StopIteration()
532
self.seen.update(self._search_revisions)
533
return self._search_revisions
538
def find_seen_ancestors(self, revision):
539
"""Find ancestors of this revision that have already been seen."""
540
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
541
seen_ancestors = set()
542
for ancestors in searcher:
543
for ancestor in ancestors:
544
if ancestor not in self.seen:
545
searcher.stop_searching_any([ancestor])
547
seen_ancestors.add(ancestor)
548
return seen_ancestors
550
def stop_searching_any(self, revisions):
552
Remove any of the specified revisions from the search list.
554
None of the specified revisions are required to be present in the
555
search list. In this case, the call is a no-op.
557
stopped = self._search_revisions.intersection(revisions)
558
self._search_revisions = self._search_revisions.difference(revisions)
561
def start_searching(self, revisions):
562
if self._search_revisions is None:
563
self._start = set(revisions)
565
self._search_revisions.update(revisions.difference(self.seen))
566
self.seen.update(revisions)
added
removed
bzrlib/graph.py
