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):
49
"""A parents provider for Graph objects."""
51
def __init__(self, ancestry):
52
self.ancestry = ancestry
55
return 'DictParentsProvider(%r)' % self.ancestry
57
def get_parent_map(self, keys):
58
"""See _StackedParentsProvider.get_parent_map"""
59
ancestry = self.ancestry
60
return dict((k, ancestry[k]) for k in keys if k in ancestry)
63
class _StackedParentsProvider(object):
65
def __init__(self, parent_providers):
66
self._parent_providers = parent_providers
69
return "_StackedParentsProvider(%r)" % self._parent_providers
71
def get_parent_map(self, keys):
72
"""Get a mapping of keys => parents
74
A dictionary is returned with an entry for each key present in this
75
source. If this source doesn't have information about a key, it should
78
[NULL_REVISION] is used as the parent of the first user-committed
79
revision. Its parent list is empty.
81
:param keys: An iterable returning keys to check (eg revision_ids)
82
:return: A dictionary mapping each key to its parents
86
for parents_provider in self._parent_providers:
87
new_found = parents_provider.get_parent_map(remaining)
88
found.update(new_found)
89
remaining.difference_update(new_found)
95
class CachingParentsProvider(object):
96
"""A parents provider which will cache the revision => parents in a dict.
98
This is useful for providers that have an expensive lookup.
101
def __init__(self, parent_provider):
102
self._real_provider = parent_provider
103
# Theoretically we could use an LRUCache here
107
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
109
def get_parent_map(self, keys):
110
"""See _StackedParentsProvider.get_parent_map"""
112
# If the _real_provider doesn't have a key, we cache a value of None,
113
# which we then later use to realize we cannot provide a value for that
120
if value is not None:
121
parent_map[key] = value
126
new_parents = self._real_provider.get_parent_map(needed)
127
cache.update(new_parents)
128
parent_map.update(new_parents)
129
needed.difference_update(new_parents)
130
cache.update(dict.fromkeys(needed, None))
135
"""Provide incremental access to revision graphs.
137
This is the generic implementation; it is intended to be subclassed to
138
specialize it for other repository types.
141
def __init__(self, parents_provider):
142
"""Construct a Graph that uses several graphs as its input
144
This should not normally be invoked directly, because there may be
145
specialized implementations for particular repository types. See
146
Repository.get_graph().
148
:param parents_provider: An object providing a get_parent_map call
149
conforming to the behavior of
150
StackedParentsProvider.get_parent_map.
152
if getattr(parents_provider, 'get_parents', None) is not None:
153
self.get_parents = parents_provider.get_parents
154
if getattr(parents_provider, 'get_parent_map', None) is not None:
155
self.get_parent_map = parents_provider.get_parent_map
156
self._parents_provider = parents_provider
159
return 'Graph(%r)' % self._parents_provider
161
def find_lca(self, *revisions):
162
"""Determine the lowest common ancestors of the provided revisions
164
A lowest common ancestor is a common ancestor none of whose
165
descendants are common ancestors. In graphs, unlike trees, there may
166
be multiple lowest common ancestors.
168
This algorithm has two phases. Phase 1 identifies border ancestors,
169
and phase 2 filters border ancestors to determine lowest common
172
In phase 1, border ancestors are identified, using a breadth-first
173
search starting at the bottom of the graph. Searches are stopped
174
whenever a node or one of its descendants is determined to be common
176
In phase 2, the border ancestors are filtered to find the least
177
common ancestors. This is done by searching the ancestries of each
180
Phase 2 is perfomed on the principle that a border ancestor that is
181
not an ancestor of any other border ancestor is a least common
184
Searches are stopped when they find a node that is determined to be a
185
common ancestor of all border ancestors, because this shows that it
186
cannot be a descendant of any border ancestor.
188
The scaling of this operation should be proportional to
189
1. The number of uncommon ancestors
190
2. The number of border ancestors
191
3. The length of the shortest path between a border ancestor and an
192
ancestor of all border ancestors.
194
border_common, common, sides = self._find_border_ancestors(revisions)
195
# We may have common ancestors that can be reached from each other.
196
# - ask for the heads of them to filter it down to only ones that
197
# cannot be reached from each other - phase 2.
198
return self.heads(border_common)
200
def find_difference(self, left_revision, right_revision):
201
"""Determine the graph difference between two revisions"""
202
border, common, (left, right) = self._find_border_ancestors(
203
[left_revision, right_revision])
204
return (left.difference(right).difference(common),
205
right.difference(left).difference(common))
207
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
def get_parents(self, revisions):
209
"""Find revision ids of the parents of a list of revisions
211
A list is returned of the same length as the input. Each entry
212
is a list of parent ids for the corresponding input revision.
214
[NULL_REVISION] is used as the parent of the first user-committed
215
revision. Its parent list is empty.
217
If the revision is not present (i.e. a ghost), None is used in place
218
of the list of parents.
220
Deprecated in bzr 1.2 - please see get_parent_map.
222
parents = self.get_parent_map(revisions)
223
return [parent.get(r, None) for r in revisions]
225
def get_parent_map(self, revisions):
226
"""Get a map of key:parent_list for revisions.
228
This implementation delegates to get_parents, for old parent_providers
229
that do not supply get_parent_map.
232
for rev, parents in self.get_parents(revisions):
233
if parents is not None:
234
result[rev] = parents
237
def _make_breadth_first_searcher(self, revisions):
238
return _BreadthFirstSearcher(revisions, self)
240
def _find_border_ancestors(self, revisions):
241
"""Find common ancestors with at least one uncommon descendant.
243
Border ancestors are identified using a breadth-first
244
search starting at the bottom of the graph. Searches are stopped
245
whenever a node or one of its descendants is determined to be common.
247
This will scale with the number of uncommon ancestors.
249
As well as the border ancestors, a set of seen common ancestors and a
250
list of sets of seen ancestors for each input revision is returned.
251
This allows calculation of graph difference from the results of this
254
if None in revisions:
255
raise errors.InvalidRevisionId(None, self)
256
common_searcher = self._make_breadth_first_searcher([])
257
common_ancestors = set()
258
searchers = [self._make_breadth_first_searcher([r])
260
active_searchers = searchers[:]
261
border_ancestors = set()
262
def update_common(searcher, revisions):
263
w_seen_ancestors = searcher.find_seen_ancestors(
265
stopped = searcher.stop_searching_any(w_seen_ancestors)
266
common_ancestors.update(w_seen_ancestors)
267
common_searcher.start_searching(stopped)
270
if len(active_searchers) == 0:
271
return border_ancestors, common_ancestors, [s.seen for s in
274
new_common = common_searcher.next()
275
common_ancestors.update(new_common)
276
except StopIteration:
279
for searcher in active_searchers:
280
for revision in new_common.intersection(searcher.seen):
281
update_common(searcher, revision)
284
new_active_searchers = []
285
for searcher in active_searchers:
287
newly_seen.update(searcher.next())
288
except StopIteration:
291
new_active_searchers.append(searcher)
292
active_searchers = new_active_searchers
293
for revision in newly_seen:
294
if revision in common_ancestors:
295
for searcher in searchers:
296
update_common(searcher, revision)
298
for searcher in searchers:
299
if revision not in searcher.seen:
302
border_ancestors.add(revision)
303
for searcher in searchers:
304
update_common(searcher, revision)
306
def heads(self, keys):
307
"""Return the heads from amongst keys.
309
This is done by searching the ancestries of each key. Any key that is
310
reachable from another key is not returned; all the others are.
312
This operation scales with the relative depth between any two keys. If
313
any two keys are completely disconnected all ancestry of both sides
316
:param keys: An iterable of keys.
317
:return: A set of the heads. Note that as a set there is no ordering
318
information. Callers will need to filter their input to create
319
order if they need it.
321
candidate_heads = set(keys)
322
if revision.NULL_REVISION in candidate_heads:
323
# NULL_REVISION is only a head if it is the only entry
324
candidate_heads.remove(revision.NULL_REVISION)
325
if not candidate_heads:
326
return set([revision.NULL_REVISION])
327
if len(candidate_heads) < 2:
328
return candidate_heads
329
searchers = dict((c, self._make_breadth_first_searcher([c]))
330
for c in candidate_heads)
331
active_searchers = dict(searchers)
332
# skip over the actual candidate for each searcher
333
for searcher in active_searchers.itervalues():
335
# The common walker finds nodes that are common to two or more of the
336
# input keys, so that we don't access all history when a currently
337
# uncommon search point actually meets up with something behind a
338
# common search point. Common search points do not keep searches
339
# active; they just allow us to make searches inactive without
340
# accessing all history.
341
common_walker = self._make_breadth_first_searcher([])
342
while len(active_searchers) > 0:
347
except StopIteration:
348
# No common points being searched at this time.
350
for candidate in active_searchers.keys():
352
searcher = active_searchers[candidate]
354
# rare case: we deleted candidate in a previous iteration
355
# through this for loop, because it was determined to be
356
# a descendant of another candidate.
359
ancestors.update(searcher.next())
360
except StopIteration:
361
del active_searchers[candidate]
363
# process found nodes
365
for ancestor in ancestors:
366
if ancestor in candidate_heads:
367
candidate_heads.remove(ancestor)
368
del searchers[ancestor]
369
if ancestor in active_searchers:
370
del active_searchers[ancestor]
371
# it may meet up with a known common node
372
if ancestor in common_walker.seen:
373
# some searcher has encountered our known common nodes:
375
ancestor_set = set([ancestor])
376
for searcher in searchers.itervalues():
377
searcher.stop_searching_any(ancestor_set)
379
# or it may have been just reached by all the searchers:
380
for searcher in searchers.itervalues():
381
if ancestor not in searcher.seen:
384
# The final active searcher has just reached this node,
385
# making it be known as a descendant of all candidates,
386
# so we can stop searching it, and any seen ancestors
387
new_common.add(ancestor)
388
for searcher in searchers.itervalues():
390
searcher.find_seen_ancestors(ancestor)
391
searcher.stop_searching_any(seen_ancestors)
392
common_walker.start_searching(new_common)
393
return candidate_heads
395
def find_unique_lca(self, left_revision, right_revision,
397
"""Find a unique LCA.
399
Find lowest common ancestors. If there is no unique common
400
ancestor, find the lowest common ancestors of those ancestors.
402
Iteration stops when a unique lowest common ancestor is found.
403
The graph origin is necessarily a unique lowest common ancestor.
405
Note that None is not an acceptable substitute for NULL_REVISION.
406
in the input for this method.
408
:param count_steps: If True, the return value will be a tuple of
409
(unique_lca, steps) where steps is the number of times that
410
find_lca was run. If False, only unique_lca is returned.
412
revisions = [left_revision, right_revision]
416
lca = self.find_lca(*revisions)
424
raise errors.NoCommonAncestor(left_revision, right_revision)
427
def iter_topo_order(self, revisions):
428
"""Iterate through the input revisions in topological order.
430
This sorting only ensures that parents come before their children.
431
An ancestor may sort after a descendant if the relationship is not
432
visible in the supplied list of revisions.
434
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
435
return sorter.iter_topo_order()
437
def is_ancestor(self, candidate_ancestor, candidate_descendant):
438
"""Determine whether a revision is an ancestor of another.
440
We answer this using heads() as heads() has the logic to perform the
441
smallest number of parent lookups to determine the ancestral
442
relationship between N revisions.
444
return set([candidate_descendant]) == self.heads(
445
[candidate_ancestor, candidate_descendant])
448
class HeadsCache(object):
449
"""A cache of results for graph heads calls."""
451
def __init__(self, graph):
455
def heads(self, keys):
456
"""Return the heads of keys.
458
This matches the API of Graph.heads(), specifically the return value is
459
a set which can be mutated, and ordering of the input is not preserved
462
:see also: Graph.heads.
463
:param keys: The keys to calculate heads for.
464
:return: A set containing the heads, which may be mutated without
465
affecting future lookups.
467
keys = frozenset(keys)
469
return set(self._heads[keys])
471
heads = self.graph.heads(keys)
472
self._heads[keys] = heads
476
class FrozenHeadsCache(object):
477
"""Cache heads() calls, assuming the caller won't modify them."""
479
def __init__(self, graph):
483
def heads(self, keys):
484
"""Return the heads of keys.
486
This matches the API of Graph.heads(), specifically the return value is
487
a set which can be mutated, and ordering of the input is not preserved
490
:see also: Graph.heads.
491
:param keys: The keys to calculate heads for.
492
:return: A set containing the heads, which may be mutated without
493
affecting future lookups.
495
keys = frozenset(keys)
497
return self._heads[keys]
499
heads = frozenset(self.graph.heads(keys))
500
self._heads[keys] = heads
503
def cache(self, keys, heads):
504
"""Store a known value."""
505
self._heads[frozenset(keys)] = frozenset(heads)
508
class _BreadthFirstSearcher(object):
509
"""Parallel search breadth-first the ancestry of revisions.
511
This class implements the iterator protocol, but additionally
512
1. provides a set of seen ancestors, and
513
2. allows some ancestries to be unsearched, via stop_searching_any
516
def __init__(self, revisions, parents_provider):
518
self._next_query = set(revisions)
520
self._started_keys = set(self._next_query)
521
self._stopped_keys = set()
522
self._parents_provider = parents_provider
523
self._returning = 'next_with_ghosts'
524
self._current_present = set()
525
self._current_ghosts = set()
526
self._current_parents = {}
533
search = '%s=%r' % (prefix, list(self._next_query))
534
return ('_BreadthFirstSearcher(iterations=%d, %s,'
535
' seen=%r)' % (self._iterations, search, list(self.seen)))
537
def get_result(self):
538
"""Get a SearchResult for the current state of this searcher.
540
:return: A SearchResult for this search so far. The SearchResult is
541
static - the search can be advanced and the search result will not
542
be invalidated or altered.
544
if self._returning == 'next':
545
# We have to know the current nodes children to be able to list the
546
# exclude keys for them. However, while we could have a second
547
# look-ahead result buffer and shuffle things around, this method
548
# is typically only called once per search - when memoising the
549
# results of the search.
550
found, ghosts, next, parents = self._do_query(self._next_query)
551
# pretend we didn't query: perhaps we should tweak _do_query to be
552
# entirely stateless?
553
self.seen.difference_update(next)
554
next_query = next.union(ghosts)
556
next_query = self._next_query
557
excludes = self._stopped_keys.union(next_query)
558
included_keys = self.seen.difference(excludes)
559
return SearchResult(self._started_keys, excludes, len(included_keys),
563
"""Return the next ancestors of this revision.
565
Ancestors are returned in the order they are seen in a breadth-first
566
traversal. No ancestor will be returned more than once. Ancestors are
567
returned before their parentage is queried, so ghosts and missing
568
revisions (including the start revisions) are included in the result.
569
This can save a round trip in LCA style calculation by allowing
570
convergence to be detected without reading the data for the revision
571
the convergence occurs on.
573
:return: A set of revision_ids.
575
if self._returning != 'next':
576
# switch to returning the query, not the results.
577
self._returning = 'next'
578
self._iterations += 1
581
if len(self._next_query) == 0:
582
raise StopIteration()
583
# We have seen what we're querying at this point as we are returning
584
# the query, not the results.
585
self.seen.update(self._next_query)
586
return self._next_query
588
def next_with_ghosts(self):
589
"""Return the next found ancestors, with ghosts split out.
591
Ancestors are returned in the order they are seen in a breadth-first
592
traversal. No ancestor will be returned more than once. Ancestors are
593
returned only after asking for their parents, which allows us to detect
594
which revisions are ghosts and which are not.
596
:return: A tuple with (present ancestors, ghost ancestors) sets.
598
if self._returning != 'next_with_ghosts':
599
# switch to returning the results, not the current query.
600
self._returning = 'next_with_ghosts'
602
if len(self._next_query) == 0:
603
raise StopIteration()
605
return self._current_present, self._current_ghosts
608
"""Advance the search.
610
Updates self.seen, self._next_query, self._current_present,
611
self._current_ghosts, self._current_parents and self._iterations.
613
self._iterations += 1
614
found, ghosts, next, parents = self._do_query(self._next_query)
615
self._current_present = found
616
self._current_ghosts = ghosts
617
self._next_query = next
618
self._current_parents = parents
619
# ghosts are implicit stop points, otherwise the search cannot be
620
# repeated when ghosts are filled.
621
self._stopped_keys.update(ghosts)
623
def _do_query(self, revisions):
624
"""Query for revisions.
626
Adds revisions to the seen set.
628
:param revisions: Revisions to query.
629
:return: A tuple: (set(found_revisions), set(ghost_revisions),
630
set(parents_of_found_revisions), dict(found_revisions:parents)).
632
found_parents = set()
633
parents_of_found = set()
634
# revisions may contain nodes that point to other nodes in revisions:
635
# we want to filter them out.
636
self.seen.update(revisions)
637
parent_map = self._parents_provider.get_parent_map(revisions)
638
for rev_id, parents in parent_map.iteritems():
639
found_parents.add(rev_id)
640
parents_of_found.update(p for p in parents if p not in self.seen)
641
ghost_parents = revisions - found_parents
642
return found_parents, ghost_parents, parents_of_found, parent_map
647
def find_seen_ancestors(self, revision):
648
"""Find ancestors of this revision that have already been seen."""
649
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
650
seen_ancestors = set()
651
for ancestors in searcher:
652
for ancestor in ancestors:
653
if ancestor not in self.seen:
654
searcher.stop_searching_any([ancestor])
656
seen_ancestors.add(ancestor)
657
return seen_ancestors
659
def stop_searching_any(self, revisions):
661
Remove any of the specified revisions from the search list.
663
None of the specified revisions are required to be present in the
664
search list. In this case, the call is a no-op.
666
revisions = frozenset(revisions)
667
if self._returning == 'next':
668
stopped = self._next_query.intersection(revisions)
669
self._next_query = self._next_query.difference(revisions)
671
stopped_present = self._current_present.intersection(revisions)
672
stopped = stopped_present.union(
673
self._current_ghosts.intersection(revisions))
674
self._current_present.difference_update(stopped)
675
self._current_ghosts.difference_update(stopped)
676
# stopping 'x' should stop returning parents of 'x', but
677
# not if 'y' always references those same parents
678
stop_rev_references = {}
679
for rev in stopped_present:
680
for parent_id in self._current_parents[rev]:
681
if parent_id not in stop_rev_references:
682
stop_rev_references[parent_id] = 0
683
stop_rev_references[parent_id] += 1
684
# if only the stopped revisions reference it, the ref count will be
686
for parents in self._current_parents.itervalues():
687
for parent_id in parents:
689
stop_rev_references[parent_id] -= 1
693
for rev_id, refs in stop_rev_references.iteritems():
695
stop_parents.add(rev_id)
696
self._next_query.difference_update(stop_parents)
697
self._stopped_keys.update(stopped)
700
def start_searching(self, revisions):
701
"""Add revisions to the search.
703
The parents of revisions will be returned from the next call to next()
704
or next_with_ghosts(). If next_with_ghosts was the most recently used
705
next* call then the return value is the result of looking up the
706
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
708
revisions = frozenset(revisions)
709
self._started_keys.update(revisions)
710
new_revisions = revisions.difference(self.seen)
711
revs, ghosts, query, parents = self._do_query(revisions)
712
self._stopped_keys.update(ghosts)
713
if self._returning == 'next':
714
self._next_query.update(new_revisions)
716
# perform a query on revisions
717
self._current_present.update(revs)
718
self._current_ghosts.update(ghosts)
719
self._next_query.update(query)
720
self._current_parents.update(parents)
724
class SearchResult(object):
725
"""The result of a breadth first search.
727
A SearchResult provides the ability to reconstruct the search or access a
728
set of the keys the search found.
731
def __init__(self, start_keys, exclude_keys, key_count, keys):
732
"""Create a SearchResult.
734
:param start_keys: The keys the search started at.
735
:param exclude_keys: The keys the search excludes.
736
:param key_count: The total number of keys (from start to but not
738
:param keys: The keys the search found. Note that in future we may get
739
a SearchResult from a smart server, in which case the keys list is
740
not necessarily immediately available.
742
self._recipe = (start_keys, exclude_keys, key_count)
743
self._keys = frozenset(keys)
745
def get_recipe(self):
746
"""Return a recipe that can be used to replay this search.
748
The recipe allows reconstruction of the same results at a later date
749
without knowing all the found keys. The essential elements are a list
750
of keys to start and and to stop at. In order to give reproducible
751
results when ghosts are encountered by a search they are automatically
752
added to the exclude list (or else ghost filling may alter the
755
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
756
recreate the results of this search, create a breadth first
757
searcher on the same graph starting at start_keys. Then call next()
758
(or next_with_ghosts()) repeatedly, and on every result, call
759
stop_searching_any on any keys from the exclude_keys set. The
760
revision_count value acts as a trivial cross-check - the found
761
revisions of the new search should have as many elements as
762
revision_count. If it does not, then additional revisions have been
763
ghosted since the search was executed the first time and the second
769
"""Return the keys found in this search.
771
:return: A set of keys.
added
removed
bzrlib/graph.py
