1
# Copyright (C) 2007-2011 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
28
STEP_UNIQUE_SEARCHER_EVERY = 5
30
# DIAGRAM of terminology
40
# In this diagram, relative to G and H:
41
# A, B, C, D, E are common ancestors.
42
# C, D and E are border ancestors, because each has a non-common descendant.
43
# D and E are least common ancestors because none of their descendants are
45
# C is not a least common ancestor because its descendant, E, is a common
48
# The find_unique_lca algorithm will pick A in two steps:
49
# 1. find_lca('G', 'H') => ['D', 'E']
50
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
53
class DictParentsProvider(object):
54
"""A parents provider for Graph objects."""
56
def __init__(self, ancestry):
57
self.ancestry = ancestry
60
return 'DictParentsProvider(%r)' % self.ancestry
62
def get_parent_map(self, keys):
63
"""See StackedParentsProvider.get_parent_map"""
64
ancestry = self.ancestry
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
68
class StackedParentsProvider(object):
69
"""A parents provider which stacks (or unions) multiple providers.
71
The providers are queries in the order of the provided parent_providers.
74
def __init__(self, parent_providers):
75
self._parent_providers = parent_providers
78
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
80
def get_parent_map(self, keys):
81
"""Get a mapping of keys => parents
83
A dictionary is returned with an entry for each key present in this
84
source. If this source doesn't have information about a key, it should
87
[NULL_REVISION] is used as the parent of the first user-committed
88
revision. Its parent list is empty.
90
:param keys: An iterable returning keys to check (eg revision_ids)
91
:return: A dictionary mapping each key to its parents
95
for parents_provider in self._parent_providers:
96
new_found = parents_provider.get_parent_map(remaining)
97
found.update(new_found)
98
remaining.difference_update(new_found)
104
class CachingParentsProvider(object):
105
"""A parents provider which will cache the revision => parents as a dict.
107
This is useful for providers which have an expensive look up.
109
Either a ParentsProvider or a get_parent_map-like callback may be
110
supplied. If it provides extra un-asked-for parents, they will be cached,
111
but filtered out of get_parent_map.
113
The cache is enabled by default, but may be disabled and re-enabled.
115
def __init__(self, parent_provider=None, get_parent_map=None):
118
:param parent_provider: The ParentProvider to use. It or
119
get_parent_map must be supplied.
120
:param get_parent_map: The get_parent_map callback to use. It or
121
parent_provider must be supplied.
123
self._real_provider = parent_provider
124
if get_parent_map is None:
125
self._get_parent_map = self._real_provider.get_parent_map
127
self._get_parent_map = get_parent_map
129
self.enable_cache(True)
132
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
134
def enable_cache(self, cache_misses=True):
136
if self._cache is not None:
137
raise AssertionError('Cache enabled when already enabled.')
139
self._cache_misses = cache_misses
140
self.missing_keys = set()
142
def disable_cache(self):
143
"""Disable and clear the cache."""
145
self._cache_misses = None
146
self.missing_keys = set()
148
def get_cached_map(self):
149
"""Return any cached get_parent_map values."""
150
if self._cache is None:
152
return dict(self._cache)
154
def get_parent_map(self, keys):
155
"""See StackedParentsProvider.get_parent_map."""
158
cache = self._get_parent_map(keys)
160
needed_revisions = set(key for key in keys if key not in cache)
161
# Do not ask for negatively cached keys
162
needed_revisions.difference_update(self.missing_keys)
164
parent_map = self._get_parent_map(needed_revisions)
165
cache.update(parent_map)
166
if self._cache_misses:
167
for key in needed_revisions:
168
if key not in parent_map:
169
self.note_missing_key(key)
172
value = cache.get(key)
173
if value is not None:
177
def note_missing_key(self, key):
178
"""Note that key is a missing key."""
179
if self._cache_misses:
180
self.missing_keys.add(key)
184
"""Provide incremental access to revision graphs.
186
This is the generic implementation; it is intended to be subclassed to
187
specialize it for other repository types.
190
def __init__(self, parents_provider):
191
"""Construct a Graph that uses several graphs as its input
193
This should not normally be invoked directly, because there may be
194
specialized implementations for particular repository types. See
195
Repository.get_graph().
197
:param parents_provider: An object providing a get_parent_map call
198
conforming to the behavior of
199
StackedParentsProvider.get_parent_map.
201
if getattr(parents_provider, 'get_parents', None) is not None:
202
self.get_parents = parents_provider.get_parents
203
if getattr(parents_provider, 'get_parent_map', None) is not None:
204
self.get_parent_map = parents_provider.get_parent_map
205
self._parents_provider = parents_provider
208
return 'Graph(%r)' % self._parents_provider
210
def find_lca(self, *revisions):
211
"""Determine the lowest common ancestors of the provided revisions
213
A lowest common ancestor is a common ancestor none of whose
214
descendants are common ancestors. In graphs, unlike trees, there may
215
be multiple lowest common ancestors.
217
This algorithm has two phases. Phase 1 identifies border ancestors,
218
and phase 2 filters border ancestors to determine lowest common
221
In phase 1, border ancestors are identified, using a breadth-first
222
search starting at the bottom of the graph. Searches are stopped
223
whenever a node or one of its descendants is determined to be common
225
In phase 2, the border ancestors are filtered to find the least
226
common ancestors. This is done by searching the ancestries of each
229
Phase 2 is perfomed on the principle that a border ancestor that is
230
not an ancestor of any other border ancestor is a least common
233
Searches are stopped when they find a node that is determined to be a
234
common ancestor of all border ancestors, because this shows that it
235
cannot be a descendant of any border ancestor.
237
The scaling of this operation should be proportional to
238
1. The number of uncommon ancestors
239
2. The number of border ancestors
240
3. The length of the shortest path between a border ancestor and an
241
ancestor of all border ancestors.
243
border_common, common, sides = self._find_border_ancestors(revisions)
244
# We may have common ancestors that can be reached from each other.
245
# - ask for the heads of them to filter it down to only ones that
246
# cannot be reached from each other - phase 2.
247
return self.heads(border_common)
249
def find_difference(self, left_revision, right_revision):
250
"""Determine the graph difference between two revisions"""
251
border, common, searchers = self._find_border_ancestors(
252
[left_revision, right_revision])
253
self._search_for_extra_common(common, searchers)
254
left = searchers[0].seen
255
right = searchers[1].seen
256
return (left.difference(right), right.difference(left))
258
def find_descendants(self, old_key, new_key):
259
"""Find descendants of old_key that are ancestors of new_key."""
260
child_map = self.get_child_map(self._find_descendant_ancestors(
262
graph = Graph(DictParentsProvider(child_map))
263
searcher = graph._make_breadth_first_searcher([old_key])
267
def _find_descendant_ancestors(self, old_key, new_key):
268
"""Find ancestors of new_key that may be descendants of old_key."""
269
stop = self._make_breadth_first_searcher([old_key])
270
descendants = self._make_breadth_first_searcher([new_key])
271
for revisions in descendants:
272
old_stop = stop.seen.intersection(revisions)
273
descendants.stop_searching_any(old_stop)
274
seen_stop = descendants.find_seen_ancestors(stop.step())
275
descendants.stop_searching_any(seen_stop)
276
return descendants.seen.difference(stop.seen)
278
def get_child_map(self, keys):
279
"""Get a mapping from parents to children of the specified keys.
281
This is simply the inversion of get_parent_map. Only supplied keys
282
will be discovered as children.
283
:return: a dict of key:child_list for keys.
285
parent_map = self._parents_provider.get_parent_map(keys)
287
for child, parents in sorted(parent_map.items()):
288
for parent in parents:
289
parent_child.setdefault(parent, []).append(child)
292
def find_distance_to_null(self, target_revision_id, known_revision_ids):
293
"""Find the left-hand distance to the NULL_REVISION.
295
(This can also be considered the revno of a branch at
298
:param target_revision_id: A revision_id which we would like to know
300
:param known_revision_ids: [(revision_id, revno)] A list of known
301
revno, revision_id tuples. We'll use this to seed the search.
303
# Map from revision_ids to a known value for their revno
304
known_revnos = dict(known_revision_ids)
305
cur_tip = target_revision_id
307
NULL_REVISION = revision.NULL_REVISION
308
known_revnos[NULL_REVISION] = 0
310
searching_known_tips = list(known_revnos.keys())
312
unknown_searched = {}
314
while cur_tip not in known_revnos:
315
unknown_searched[cur_tip] = num_steps
317
to_search = set([cur_tip])
318
to_search.update(searching_known_tips)
319
parent_map = self.get_parent_map(to_search)
320
parents = parent_map.get(cur_tip, None)
321
if not parents: # An empty list or None is a ghost
322
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
326
for revision_id in searching_known_tips:
327
parents = parent_map.get(revision_id, None)
331
next_revno = known_revnos[revision_id] - 1
332
if next in unknown_searched:
333
# We have enough information to return a value right now
334
return next_revno + unknown_searched[next]
335
if next in known_revnos:
337
known_revnos[next] = next_revno
338
next_known_tips.append(next)
339
searching_known_tips = next_known_tips
341
# We reached a known revision, so just add in how many steps it took to
343
return known_revnos[cur_tip] + num_steps
345
def find_lefthand_distances(self, keys):
346
"""Find the distance to null for all the keys in keys.
348
:param keys: keys to lookup.
349
:return: A dict key->distance for all of keys.
351
# Optimisable by concurrent searching, but a random spread should get
352
# some sort of hit rate.
359
(key, self.find_distance_to_null(key, known_revnos)))
360
except errors.GhostRevisionsHaveNoRevno:
363
known_revnos.append((key, -1))
364
return dict(known_revnos)
366
def find_unique_ancestors(self, unique_revision, common_revisions):
367
"""Find the unique ancestors for a revision versus others.
369
This returns the ancestry of unique_revision, excluding all revisions
370
in the ancestry of common_revisions. If unique_revision is in the
371
ancestry, then the empty set will be returned.
373
:param unique_revision: The revision_id whose ancestry we are
375
XXX: Would this API be better if we allowed multiple revisions on
377
:param common_revisions: Revision_ids of ancestries to exclude.
378
:return: A set of revisions in the ancestry of unique_revision
380
if unique_revision in common_revisions:
383
# Algorithm description
384
# 1) Walk backwards from the unique node and all common nodes.
385
# 2) When a node is seen by both sides, stop searching it in the unique
386
# walker, include it in the common walker.
387
# 3) Stop searching when there are no nodes left for the unique walker.
388
# At this point, you have a maximal set of unique nodes. Some of
389
# them may actually be common, and you haven't reached them yet.
390
# 4) Start new searchers for the unique nodes, seeded with the
391
# information you have so far.
392
# 5) Continue searching, stopping the common searches when the search
393
# tip is an ancestor of all unique nodes.
394
# 6) Aggregate together unique searchers when they are searching the
395
# same tips. When all unique searchers are searching the same node,
396
# stop move it to a single 'all_unique_searcher'.
397
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
398
# Most of the time this produces very little important information.
399
# So don't step it as quickly as the other searchers.
400
# 8) Search is done when all common searchers have completed.
402
unique_searcher, common_searcher = self._find_initial_unique_nodes(
403
[unique_revision], common_revisions)
405
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
409
(all_unique_searcher,
410
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
411
unique_searcher, common_searcher)
413
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
414
unique_tip_searchers, common_searcher)
415
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
416
if 'graph' in debug.debug_flags:
417
trace.mutter('Found %d truly unique nodes out of %d',
418
len(true_unique_nodes), len(unique_nodes))
419
return true_unique_nodes
421
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
422
"""Steps 1-3 of find_unique_ancestors.
424
Find the maximal set of unique nodes. Some of these might actually
425
still be common, but we are sure that there are no other unique nodes.
427
:return: (unique_searcher, common_searcher)
430
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
431
# we know that unique_revisions aren't in common_revisions, so skip
433
unique_searcher.next()
434
common_searcher = self._make_breadth_first_searcher(common_revisions)
436
# As long as we are still finding unique nodes, keep searching
437
while unique_searcher._next_query:
438
next_unique_nodes = set(unique_searcher.step())
439
next_common_nodes = set(common_searcher.step())
441
# Check if either searcher encounters new nodes seen by the other
443
unique_are_common_nodes = next_unique_nodes.intersection(
444
common_searcher.seen)
445
unique_are_common_nodes.update(
446
next_common_nodes.intersection(unique_searcher.seen))
447
if unique_are_common_nodes:
448
ancestors = unique_searcher.find_seen_ancestors(
449
unique_are_common_nodes)
450
# TODO: This is a bit overboard, we only really care about
451
# the ancestors of the tips because the rest we
452
# already know. This is *correct* but causes us to
453
# search too much ancestry.
454
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
455
unique_searcher.stop_searching_any(ancestors)
456
common_searcher.start_searching(ancestors)
458
return unique_searcher, common_searcher
460
def _make_unique_searchers(self, unique_nodes, unique_searcher,
462
"""Create a searcher for all the unique search tips (step 4).
464
As a side effect, the common_searcher will stop searching any nodes
465
that are ancestors of the unique searcher tips.
467
:return: (all_unique_searcher, unique_tip_searchers)
469
unique_tips = self._remove_simple_descendants(unique_nodes,
470
self.get_parent_map(unique_nodes))
472
if len(unique_tips) == 1:
473
unique_tip_searchers = []
474
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
476
unique_tip_searchers = []
477
for tip in unique_tips:
478
revs_to_search = unique_searcher.find_seen_ancestors([tip])
479
revs_to_search.update(
480
common_searcher.find_seen_ancestors(revs_to_search))
481
searcher = self._make_breadth_first_searcher(revs_to_search)
482
# We don't care about the starting nodes.
483
searcher._label = tip
485
unique_tip_searchers.append(searcher)
487
ancestor_all_unique = None
488
for searcher in unique_tip_searchers:
489
if ancestor_all_unique is None:
490
ancestor_all_unique = set(searcher.seen)
492
ancestor_all_unique = ancestor_all_unique.intersection(
494
# Collapse all the common nodes into a single searcher
495
all_unique_searcher = self._make_breadth_first_searcher(
497
if ancestor_all_unique:
498
# We've seen these nodes in all the searchers, so we'll just go to
500
all_unique_searcher.step()
502
# Stop any search tips that are already known as ancestors of the
504
stopped_common = common_searcher.stop_searching_any(
505
common_searcher.find_seen_ancestors(ancestor_all_unique))
508
for searcher in unique_tip_searchers:
509
total_stopped += len(searcher.stop_searching_any(
510
searcher.find_seen_ancestors(ancestor_all_unique)))
511
if 'graph' in debug.debug_flags:
512
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
513
' (%d stopped search tips, %d common ancestors'
514
' (%d stopped common)',
515
len(unique_nodes), len(unique_tip_searchers),
516
total_stopped, len(ancestor_all_unique),
518
return all_unique_searcher, unique_tip_searchers
520
def _step_unique_and_common_searchers(self, common_searcher,
521
unique_tip_searchers,
523
"""Step all the searchers"""
524
newly_seen_common = set(common_searcher.step())
525
newly_seen_unique = set()
526
for searcher in unique_tip_searchers:
527
next = set(searcher.step())
528
next.update(unique_searcher.find_seen_ancestors(next))
529
next.update(common_searcher.find_seen_ancestors(next))
530
for alt_searcher in unique_tip_searchers:
531
if alt_searcher is searcher:
533
next.update(alt_searcher.find_seen_ancestors(next))
534
searcher.start_searching(next)
535
newly_seen_unique.update(next)
536
return newly_seen_common, newly_seen_unique
538
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
540
newly_seen_unique, step_all_unique):
541
"""Find nodes that are common to all unique_tip_searchers.
543
If it is time, step the all_unique_searcher, and add its nodes to the
546
common_to_all_unique_nodes = newly_seen_unique.copy()
547
for searcher in unique_tip_searchers:
548
common_to_all_unique_nodes.intersection_update(searcher.seen)
549
common_to_all_unique_nodes.intersection_update(
550
all_unique_searcher.seen)
551
# Step all-unique less frequently than the other searchers.
552
# In the common case, we don't need to spider out far here, so
553
# avoid doing extra work.
555
tstart = time.clock()
556
nodes = all_unique_searcher.step()
557
common_to_all_unique_nodes.update(nodes)
558
if 'graph' in debug.debug_flags:
559
tdelta = time.clock() - tstart
560
trace.mutter('all_unique_searcher step() took %.3fs'
561
'for %d nodes (%d total), iteration: %s',
562
tdelta, len(nodes), len(all_unique_searcher.seen),
563
all_unique_searcher._iterations)
564
return common_to_all_unique_nodes
566
def _collapse_unique_searchers(self, unique_tip_searchers,
567
common_to_all_unique_nodes):
568
"""Combine searchers that are searching the same tips.
570
When two searchers are searching the same tips, we can stop one of the
571
searchers. We also know that the maximal set of common ancestors is the
572
intersection of the two original searchers.
574
:return: A list of searchers that are searching unique nodes.
576
# Filter out searchers that don't actually search different
577
# nodes. We already have the ancestry intersection for them
578
unique_search_tips = {}
579
for searcher in unique_tip_searchers:
580
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
581
will_search_set = frozenset(searcher._next_query)
582
if not will_search_set:
583
if 'graph' in debug.debug_flags:
584
trace.mutter('Unique searcher %s was stopped.'
585
' (%s iterations) %d nodes stopped',
587
searcher._iterations,
589
elif will_search_set not in unique_search_tips:
590
# This searcher is searching a unique set of nodes, let it
591
unique_search_tips[will_search_set] = [searcher]
593
unique_search_tips[will_search_set].append(searcher)
594
# TODO: it might be possible to collapse searchers faster when they
595
# only have *some* search tips in common.
596
next_unique_searchers = []
597
for searchers in unique_search_tips.itervalues():
598
if len(searchers) == 1:
599
# Searching unique tips, go for it
600
next_unique_searchers.append(searchers[0])
602
# These searchers have started searching the same tips, we
603
# don't need them to cover the same ground. The
604
# intersection of their ancestry won't change, so create a
605
# new searcher, combining their histories.
606
next_searcher = searchers[0]
607
for searcher in searchers[1:]:
608
next_searcher.seen.intersection_update(searcher.seen)
609
if 'graph' in debug.debug_flags:
610
trace.mutter('Combining %d searchers into a single'
611
' searcher searching %d nodes with'
614
len(next_searcher._next_query),
615
len(next_searcher.seen))
616
next_unique_searchers.append(next_searcher)
617
return next_unique_searchers
619
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
620
unique_tip_searchers, common_searcher):
621
"""Steps 5-8 of find_unique_ancestors.
623
This function returns when common_searcher has stopped searching for
626
# We step the ancestor_all_unique searcher only every
627
# STEP_UNIQUE_SEARCHER_EVERY steps.
628
step_all_unique_counter = 0
629
# While we still have common nodes to search
630
while common_searcher._next_query:
632
newly_seen_unique) = self._step_unique_and_common_searchers(
633
common_searcher, unique_tip_searchers, unique_searcher)
634
# These nodes are common ancestors of all unique nodes
635
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
636
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
637
step_all_unique_counter==0)
638
step_all_unique_counter = ((step_all_unique_counter + 1)
639
% STEP_UNIQUE_SEARCHER_EVERY)
641
if newly_seen_common:
642
# If a 'common' node is an ancestor of all unique searchers, we
643
# can stop searching it.
644
common_searcher.stop_searching_any(
645
all_unique_searcher.seen.intersection(newly_seen_common))
646
if common_to_all_unique_nodes:
647
common_to_all_unique_nodes.update(
648
common_searcher.find_seen_ancestors(
649
common_to_all_unique_nodes))
650
# The all_unique searcher can start searching the common nodes
651
# but everyone else can stop.
652
# This is the sort of thing where we would like to not have it
653
# start_searching all of the nodes, but only mark all of them
654
# as seen, and have it search only the actual tips. Otherwise
655
# it is another get_parent_map() traversal for it to figure out
656
# what we already should know.
657
all_unique_searcher.start_searching(common_to_all_unique_nodes)
658
common_searcher.stop_searching_any(common_to_all_unique_nodes)
660
next_unique_searchers = self._collapse_unique_searchers(
661
unique_tip_searchers, common_to_all_unique_nodes)
662
if len(unique_tip_searchers) != len(next_unique_searchers):
663
if 'graph' in debug.debug_flags:
664
trace.mutter('Collapsed %d unique searchers => %d'
666
len(unique_tip_searchers),
667
len(next_unique_searchers),
668
all_unique_searcher._iterations)
669
unique_tip_searchers = next_unique_searchers
671
def get_parent_map(self, revisions):
672
"""Get a map of key:parent_list for revisions.
674
This implementation delegates to get_parents, for old parent_providers
675
that do not supply get_parent_map.
678
for rev, parents in self.get_parents(revisions):
679
if parents is not None:
680
result[rev] = parents
683
def _make_breadth_first_searcher(self, revisions):
684
return _BreadthFirstSearcher(revisions, self)
686
def _find_border_ancestors(self, revisions):
687
"""Find common ancestors with at least one uncommon descendant.
689
Border ancestors are identified using a breadth-first
690
search starting at the bottom of the graph. Searches are stopped
691
whenever a node or one of its descendants is determined to be common.
693
This will scale with the number of uncommon ancestors.
695
As well as the border ancestors, a set of seen common ancestors and a
696
list of sets of seen ancestors for each input revision is returned.
697
This allows calculation of graph difference from the results of this
700
if None in revisions:
701
raise errors.InvalidRevisionId(None, self)
702
common_ancestors = set()
703
searchers = [self._make_breadth_first_searcher([r])
705
active_searchers = searchers[:]
706
border_ancestors = set()
710
for searcher in searchers:
711
new_ancestors = searcher.step()
713
newly_seen.update(new_ancestors)
715
for revision in newly_seen:
716
if revision in common_ancestors:
717
# Not a border ancestor because it was seen as common
719
new_common.add(revision)
721
for searcher in searchers:
722
if revision not in searcher.seen:
725
# This is a border because it is a first common that we see
726
# after walking for a while.
727
border_ancestors.add(revision)
728
new_common.add(revision)
730
for searcher in searchers:
731
new_common.update(searcher.find_seen_ancestors(new_common))
732
for searcher in searchers:
733
searcher.start_searching(new_common)
734
common_ancestors.update(new_common)
736
# Figure out what the searchers will be searching next, and if
737
# there is only 1 set being searched, then we are done searching,
738
# since all searchers would have to be searching the same data,
739
# thus it *must* be in common.
740
unique_search_sets = set()
741
for searcher in searchers:
742
will_search_set = frozenset(searcher._next_query)
743
if will_search_set not in unique_search_sets:
744
# This searcher is searching a unique set of nodes, let it
745
unique_search_sets.add(will_search_set)
747
if len(unique_search_sets) == 1:
748
nodes = unique_search_sets.pop()
749
uncommon_nodes = nodes.difference(common_ancestors)
751
raise AssertionError("Somehow we ended up converging"
752
" without actually marking them as"
755
"\nuncommon_nodes: %s"
756
% (revisions, uncommon_nodes))
758
return border_ancestors, common_ancestors, searchers
760
def heads(self, keys):
761
"""Return the heads from amongst keys.
763
This is done by searching the ancestries of each key. Any key that is
764
reachable from another key is not returned; all the others are.
766
This operation scales with the relative depth between any two keys. If
767
any two keys are completely disconnected all ancestry of both sides
770
:param keys: An iterable of keys.
771
:return: A set of the heads. Note that as a set there is no ordering
772
information. Callers will need to filter their input to create
773
order if they need it.
775
candidate_heads = set(keys)
776
if revision.NULL_REVISION in candidate_heads:
777
# NULL_REVISION is only a head if it is the only entry
778
candidate_heads.remove(revision.NULL_REVISION)
779
if not candidate_heads:
780
return set([revision.NULL_REVISION])
781
if len(candidate_heads) < 2:
782
return candidate_heads
783
searchers = dict((c, self._make_breadth_first_searcher([c]))
784
for c in candidate_heads)
785
active_searchers = dict(searchers)
786
# skip over the actual candidate for each searcher
787
for searcher in active_searchers.itervalues():
789
# The common walker finds nodes that are common to two or more of the
790
# input keys, so that we don't access all history when a currently
791
# uncommon search point actually meets up with something behind a
792
# common search point. Common search points do not keep searches
793
# active; they just allow us to make searches inactive without
794
# accessing all history.
795
common_walker = self._make_breadth_first_searcher([])
796
while len(active_searchers) > 0:
801
except StopIteration:
802
# No common points being searched at this time.
804
for candidate in active_searchers.keys():
806
searcher = active_searchers[candidate]
808
# rare case: we deleted candidate in a previous iteration
809
# through this for loop, because it was determined to be
810
# a descendant of another candidate.
813
ancestors.update(searcher.next())
814
except StopIteration:
815
del active_searchers[candidate]
817
# process found nodes
819
for ancestor in ancestors:
820
if ancestor in candidate_heads:
821
candidate_heads.remove(ancestor)
822
del searchers[ancestor]
823
if ancestor in active_searchers:
824
del active_searchers[ancestor]
825
# it may meet up with a known common node
826
if ancestor in common_walker.seen:
827
# some searcher has encountered our known common nodes:
829
ancestor_set = set([ancestor])
830
for searcher in searchers.itervalues():
831
searcher.stop_searching_any(ancestor_set)
833
# or it may have been just reached by all the searchers:
834
for searcher in searchers.itervalues():
835
if ancestor not in searcher.seen:
838
# The final active searcher has just reached this node,
839
# making it be known as a descendant of all candidates,
840
# so we can stop searching it, and any seen ancestors
841
new_common.add(ancestor)
842
for searcher in searchers.itervalues():
844
searcher.find_seen_ancestors([ancestor])
845
searcher.stop_searching_any(seen_ancestors)
846
common_walker.start_searching(new_common)
847
return candidate_heads
849
def find_merge_order(self, tip_revision_id, lca_revision_ids):
850
"""Find the order that each revision was merged into tip.
852
This basically just walks backwards with a stack, and walks left-first
853
until it finds a node to stop.
855
if len(lca_revision_ids) == 1:
856
return list(lca_revision_ids)
857
looking_for = set(lca_revision_ids)
858
# TODO: Is there a way we could do this "faster" by batching up the
859
# get_parent_map requests?
860
# TODO: Should we also be culling the ancestry search right away? We
861
# could add looking_for to the "stop" list, and walk their
862
# ancestry in batched mode. The flip side is it might mean we walk a
863
# lot of "stop" nodes, rather than only the minimum.
864
# Then again, without it we may trace back into ancestry we could have
866
stack = [tip_revision_id]
869
while stack and looking_for:
872
if next in looking_for:
874
looking_for.remove(next)
875
if len(looking_for) == 1:
876
found.append(looking_for.pop())
879
parent_ids = self.get_parent_map([next]).get(next, None)
880
if not parent_ids: # Ghost, nothing to search here
882
for parent_id in reversed(parent_ids):
883
# TODO: (performance) We see the parent at this point, but we
884
# wait to mark it until later to make sure we get left
885
# parents before right parents. However, instead of
886
# waiting until we have traversed enough parents, we
887
# could instead note that we've found it, and once all
888
# parents are in the stack, just reverse iterate the
890
if parent_id not in stop:
891
# this will need to be searched
892
stack.append(parent_id)
896
def find_lefthand_merger(self, merged_key, tip_key):
897
"""Find the first lefthand ancestor of tip_key that merged merged_key.
899
We do this by first finding the descendants of merged_key, then
900
walking through the lefthand ancestry of tip_key until we find a key
901
that doesn't descend from merged_key. Its child is the key that
904
:return: The first lefthand ancestor of tip_key to merge merged_key.
905
merged_key if it is a lefthand ancestor of tip_key.
906
None if no ancestor of tip_key merged merged_key.
908
descendants = self.find_descendants(merged_key, tip_key)
909
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
910
last_candidate = None
911
for candidate in candidate_iterator:
912
if candidate not in descendants:
913
return last_candidate
914
last_candidate = candidate
916
def find_unique_lca(self, left_revision, right_revision,
918
"""Find a unique LCA.
920
Find lowest common ancestors. If there is no unique common
921
ancestor, find the lowest common ancestors of those ancestors.
923
Iteration stops when a unique lowest common ancestor is found.
924
The graph origin is necessarily a unique lowest common ancestor.
926
Note that None is not an acceptable substitute for NULL_REVISION.
927
in the input for this method.
929
:param count_steps: If True, the return value will be a tuple of
930
(unique_lca, steps) where steps is the number of times that
931
find_lca was run. If False, only unique_lca is returned.
933
revisions = [left_revision, right_revision]
937
lca = self.find_lca(*revisions)
945
raise errors.NoCommonAncestor(left_revision, right_revision)
948
def iter_ancestry(self, revision_ids):
949
"""Iterate the ancestry of this revision.
951
:param revision_ids: Nodes to start the search
952
:return: Yield tuples mapping a revision_id to its parents for the
953
ancestry of revision_id.
954
Ghosts will be returned with None as their parents, and nodes
955
with no parents will have NULL_REVISION as their only parent. (As
956
defined by get_parent_map.)
957
There will also be a node for (NULL_REVISION, ())
959
pending = set(revision_ids)
962
processed.update(pending)
963
next_map = self.get_parent_map(pending)
965
for item in next_map.iteritems():
967
next_pending.update(p for p in item[1] if p not in processed)
968
ghosts = pending.difference(next_map)
971
pending = next_pending
973
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
974
if stop_keys is None:
977
def get_parents(key):
979
return self._parents_provider.get_parent_map([key])[key]
981
raise errors.RevisionNotPresent(next_key, self)
983
if next_key in stop_keys:
985
parents = get_parents(next_key)
987
if len(parents) == 0:
990
next_key = parents[0]
992
def iter_topo_order(self, revisions):
993
"""Iterate through the input revisions in topological order.
995
This sorting only ensures that parents come before their children.
996
An ancestor may sort after a descendant if the relationship is not
997
visible in the supplied list of revisions.
999
from bzrlib import tsort
1000
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1001
return sorter.iter_topo_order()
1003
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1004
"""Determine whether a revision is an ancestor of another.
1006
We answer this using heads() as heads() has the logic to perform the
1007
smallest number of parent lookups to determine the ancestral
1008
relationship between N revisions.
1010
return set([candidate_descendant]) == self.heads(
1011
[candidate_ancestor, candidate_descendant])
1013
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1014
"""Determine whether a revision is between two others.
1016
returns true if and only if:
1017
lower_bound_revid <= revid <= upper_bound_revid
1019
return ((upper_bound_revid is None or
1020
self.is_ancestor(revid, upper_bound_revid)) and
1021
(lower_bound_revid is None or
1022
self.is_ancestor(lower_bound_revid, revid)))
1024
def _search_for_extra_common(self, common, searchers):
1025
"""Make sure that unique nodes are genuinely unique.
1027
After _find_border_ancestors, all nodes marked "common" are indeed
1028
common. Some of the nodes considered unique are not, due to history
1029
shortcuts stopping the searches early.
1031
We know that we have searched enough when all common search tips are
1032
descended from all unique (uncommon) nodes because we know that a node
1033
cannot be an ancestor of its own ancestor.
1035
:param common: A set of common nodes
1036
:param searchers: The searchers returned from _find_border_ancestors
1039
# Basic algorithm...
1040
# A) The passed in searchers should all be on the same tips, thus
1041
# they should be considered the "common" searchers.
1042
# B) We find the difference between the searchers, these are the
1043
# "unique" nodes for each side.
1044
# C) We do a quick culling so that we only start searching from the
1045
# more interesting unique nodes. (A unique ancestor is more
1046
# interesting than any of its children.)
1047
# D) We start searching for ancestors common to all unique nodes.
1048
# E) We have the common searchers stop searching any ancestors of
1049
# nodes found by (D)
1050
# F) When there are no more common search tips, we stop
1052
# TODO: We need a way to remove unique_searchers when they overlap with
1053
# other unique searchers.
1054
if len(searchers) != 2:
1055
raise NotImplementedError(
1056
"Algorithm not yet implemented for > 2 searchers")
1057
common_searchers = searchers
1058
left_searcher = searchers[0]
1059
right_searcher = searchers[1]
1060
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1061
if not unique: # No unique nodes, nothing to do
1063
total_unique = len(unique)
1064
unique = self._remove_simple_descendants(unique,
1065
self.get_parent_map(unique))
1066
simple_unique = len(unique)
1068
unique_searchers = []
1069
for revision_id in unique:
1070
if revision_id in left_searcher.seen:
1071
parent_searcher = left_searcher
1073
parent_searcher = right_searcher
1074
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1075
if not revs_to_search: # XXX: This shouldn't be possible
1076
revs_to_search = [revision_id]
1077
searcher = self._make_breadth_first_searcher(revs_to_search)
1078
# We don't care about the starting nodes.
1080
unique_searchers.append(searcher)
1082
# possible todo: aggregate the common searchers into a single common
1083
# searcher, just make sure that we include the nodes into the .seen
1084
# properties of the original searchers
1086
ancestor_all_unique = None
1087
for searcher in unique_searchers:
1088
if ancestor_all_unique is None:
1089
ancestor_all_unique = set(searcher.seen)
1091
ancestor_all_unique = ancestor_all_unique.intersection(
1094
trace.mutter('Started %s unique searchers for %s unique revisions',
1095
simple_unique, total_unique)
1097
while True: # If we have no more nodes we have nothing to do
1098
newly_seen_common = set()
1099
for searcher in common_searchers:
1100
newly_seen_common.update(searcher.step())
1101
newly_seen_unique = set()
1102
for searcher in unique_searchers:
1103
newly_seen_unique.update(searcher.step())
1104
new_common_unique = set()
1105
for revision in newly_seen_unique:
1106
for searcher in unique_searchers:
1107
if revision not in searcher.seen:
1110
# This is a border because it is a first common that we see
1111
# after walking for a while.
1112
new_common_unique.add(revision)
1113
if newly_seen_common:
1114
# These are nodes descended from one of the 'common' searchers.
1115
# Make sure all searchers are on the same page
1116
for searcher in common_searchers:
1117
newly_seen_common.update(
1118
searcher.find_seen_ancestors(newly_seen_common))
1119
# We start searching the whole ancestry. It is a bit wasteful,
1120
# though. We really just want to mark all of these nodes as
1121
# 'seen' and then start just the tips. However, it requires a
1122
# get_parent_map() call to figure out the tips anyway, and all
1123
# redundant requests should be fairly fast.
1124
for searcher in common_searchers:
1125
searcher.start_searching(newly_seen_common)
1127
# If a 'common' node is an ancestor of all unique searchers, we
1128
# can stop searching it.
1129
stop_searching_common = ancestor_all_unique.intersection(
1131
if stop_searching_common:
1132
for searcher in common_searchers:
1133
searcher.stop_searching_any(stop_searching_common)
1134
if new_common_unique:
1135
# We found some ancestors that are common
1136
for searcher in unique_searchers:
1137
new_common_unique.update(
1138
searcher.find_seen_ancestors(new_common_unique))
1139
# Since these are common, we can grab another set of ancestors
1141
for searcher in common_searchers:
1142
new_common_unique.update(
1143
searcher.find_seen_ancestors(new_common_unique))
1145
# We can tell all of the unique searchers to start at these
1146
# nodes, and tell all of the common searchers to *stop*
1147
# searching these nodes
1148
for searcher in unique_searchers:
1149
searcher.start_searching(new_common_unique)
1150
for searcher in common_searchers:
1151
searcher.stop_searching_any(new_common_unique)
1152
ancestor_all_unique.update(new_common_unique)
1154
# Filter out searchers that don't actually search different
1155
# nodes. We already have the ancestry intersection for them
1156
next_unique_searchers = []
1157
unique_search_sets = set()
1158
for searcher in unique_searchers:
1159
will_search_set = frozenset(searcher._next_query)
1160
if will_search_set not in unique_search_sets:
1161
# This searcher is searching a unique set of nodes, let it
1162
unique_search_sets.add(will_search_set)
1163
next_unique_searchers.append(searcher)
1164
unique_searchers = next_unique_searchers
1165
for searcher in common_searchers:
1166
if searcher._next_query:
1169
# All common searcher have stopped searching
1172
def _remove_simple_descendants(self, revisions, parent_map):
1173
"""remove revisions which are children of other ones in the set
1175
This doesn't do any graph searching, it just checks the immediate
1176
parent_map to find if there are any children which can be removed.
1178
:param revisions: A set of revision_ids
1179
:return: A set of revision_ids with the children removed
1181
simple_ancestors = revisions.copy()
1182
# TODO: jam 20071214 we *could* restrict it to searching only the
1183
# parent_map of revisions already present in 'revisions', but
1184
# considering the general use case, I think this is actually
1187
# This is the same as the following loop. I don't know that it is any
1189
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1190
## if p_ids is not None and revisions.intersection(p_ids))
1191
## return simple_ancestors
1193
# Yet Another Way, invert the parent map (which can be cached)
1195
## for revision_id, parent_ids in parent_map.iteritems():
1196
## for p_id in parent_ids:
1197
## descendants.setdefault(p_id, []).append(revision_id)
1198
## for revision in revisions.intersection(descendants):
1199
## simple_ancestors.difference_update(descendants[revision])
1200
## return simple_ancestors
1201
for revision, parent_ids in parent_map.iteritems():
1202
if parent_ids is None:
1204
for parent_id in parent_ids:
1205
if parent_id in revisions:
1206
# This node has a parent present in the set, so we can
1208
simple_ancestors.discard(revision)
1210
return simple_ancestors
1213
class HeadsCache(object):
1214
"""A cache of results for graph heads calls."""
1216
def __init__(self, graph):
1220
def heads(self, keys):
1221
"""Return the heads of keys.
1223
This matches the API of Graph.heads(), specifically the return value is
1224
a set which can be mutated, and ordering of the input is not preserved
1227
:see also: Graph.heads.
1228
:param keys: The keys to calculate heads for.
1229
:return: A set containing the heads, which may be mutated without
1230
affecting future lookups.
1232
keys = frozenset(keys)
1234
return set(self._heads[keys])
1236
heads = self.graph.heads(keys)
1237
self._heads[keys] = heads
1241
class FrozenHeadsCache(object):
1242
"""Cache heads() calls, assuming the caller won't modify them."""
1244
def __init__(self, graph):
1248
def heads(self, keys):
1249
"""Return the heads of keys.
1251
Similar to Graph.heads(). The main difference is that the return value
1252
is a frozen set which cannot be mutated.
1254
:see also: Graph.heads.
1255
:param keys: The keys to calculate heads for.
1256
:return: A frozenset containing the heads.
1258
keys = frozenset(keys)
1260
return self._heads[keys]
1262
heads = frozenset(self.graph.heads(keys))
1263
self._heads[keys] = heads
1266
def cache(self, keys, heads):
1267
"""Store a known value."""
1268
self._heads[frozenset(keys)] = frozenset(heads)
1271
class _BreadthFirstSearcher(object):
1272
"""Parallel search breadth-first the ancestry of revisions.
1274
This class implements the iterator protocol, but additionally
1275
1. provides a set of seen ancestors, and
1276
2. allows some ancestries to be unsearched, via stop_searching_any
1279
def __init__(self, revisions, parents_provider):
1280
self._iterations = 0
1281
self._next_query = set(revisions)
1283
self._started_keys = set(self._next_query)
1284
self._stopped_keys = set()
1285
self._parents_provider = parents_provider
1286
self._returning = 'next_with_ghosts'
1287
self._current_present = set()
1288
self._current_ghosts = set()
1289
self._current_parents = {}
1292
if self._iterations:
1293
prefix = "searching"
1296
search = '%s=%r' % (prefix, list(self._next_query))
1297
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1298
' seen=%r)' % (self._iterations, search, list(self.seen)))
1300
def get_result(self):
1301
"""Get a SearchResult for the current state of this searcher.
1303
:return: A SearchResult for this search so far. The SearchResult is
1304
static - the search can be advanced and the search result will not
1305
be invalidated or altered.
1307
if self._returning == 'next':
1308
# We have to know the current nodes children to be able to list the
1309
# exclude keys for them. However, while we could have a second
1310
# look-ahead result buffer and shuffle things around, this method
1311
# is typically only called once per search - when memoising the
1312
# results of the search.
1313
found, ghosts, next, parents = self._do_query(self._next_query)
1314
# pretend we didn't query: perhaps we should tweak _do_query to be
1315
# entirely stateless?
1316
self.seen.difference_update(next)
1317
next_query = next.union(ghosts)
1319
next_query = self._next_query
1320
excludes = self._stopped_keys.union(next_query)
1321
included_keys = self.seen.difference(excludes)
1322
return SearchResult(self._started_keys, excludes, len(included_keys),
1328
except StopIteration:
1332
"""Return the next ancestors of this revision.
1334
Ancestors are returned in the order they are seen in a breadth-first
1335
traversal. No ancestor will be returned more than once. Ancestors are
1336
returned before their parentage is queried, so ghosts and missing
1337
revisions (including the start revisions) are included in the result.
1338
This can save a round trip in LCA style calculation by allowing
1339
convergence to be detected without reading the data for the revision
1340
the convergence occurs on.
1342
:return: A set of revision_ids.
1344
if self._returning != 'next':
1345
# switch to returning the query, not the results.
1346
self._returning = 'next'
1347
self._iterations += 1
1350
if len(self._next_query) == 0:
1351
raise StopIteration()
1352
# We have seen what we're querying at this point as we are returning
1353
# the query, not the results.
1354
self.seen.update(self._next_query)
1355
return self._next_query
1357
def next_with_ghosts(self):
1358
"""Return the next found ancestors, with ghosts split out.
1360
Ancestors are returned in the order they are seen in a breadth-first
1361
traversal. No ancestor will be returned more than once. Ancestors are
1362
returned only after asking for their parents, which allows us to detect
1363
which revisions are ghosts and which are not.
1365
:return: A tuple with (present ancestors, ghost ancestors) sets.
1367
if self._returning != 'next_with_ghosts':
1368
# switch to returning the results, not the current query.
1369
self._returning = 'next_with_ghosts'
1371
if len(self._next_query) == 0:
1372
raise StopIteration()
1374
return self._current_present, self._current_ghosts
1377
"""Advance the search.
1379
Updates self.seen, self._next_query, self._current_present,
1380
self._current_ghosts, self._current_parents and self._iterations.
1382
self._iterations += 1
1383
found, ghosts, next, parents = self._do_query(self._next_query)
1384
self._current_present = found
1385
self._current_ghosts = ghosts
1386
self._next_query = next
1387
self._current_parents = parents
1388
# ghosts are implicit stop points, otherwise the search cannot be
1389
# repeated when ghosts are filled.
1390
self._stopped_keys.update(ghosts)
1392
def _do_query(self, revisions):
1393
"""Query for revisions.
1395
Adds revisions to the seen set.
1397
:param revisions: Revisions to query.
1398
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1399
set(parents_of_found_revisions), dict(found_revisions:parents)).
1401
found_revisions = set()
1402
parents_of_found = set()
1403
# revisions may contain nodes that point to other nodes in revisions:
1404
# we want to filter them out.
1405
self.seen.update(revisions)
1406
parent_map = self._parents_provider.get_parent_map(revisions)
1407
found_revisions.update(parent_map)
1408
for rev_id, parents in parent_map.iteritems():
1411
new_found_parents = [p for p in parents if p not in self.seen]
1412
if new_found_parents:
1413
# Calling set.update() with an empty generator is actually
1415
parents_of_found.update(new_found_parents)
1416
ghost_revisions = revisions - found_revisions
1417
return found_revisions, ghost_revisions, parents_of_found, parent_map
1422
def find_seen_ancestors(self, revisions):
1423
"""Find ancestors of these revisions that have already been seen.
1425
This function generally makes the assumption that querying for the
1426
parents of a node that has already been queried is reasonably cheap.
1427
(eg, not a round trip to a remote host).
1429
# TODO: Often we might ask one searcher for its seen ancestors, and
1430
# then ask another searcher the same question. This can result in
1431
# searching the same revisions repeatedly if the two searchers
1432
# have a lot of overlap.
1433
all_seen = self.seen
1434
pending = set(revisions).intersection(all_seen)
1435
seen_ancestors = set(pending)
1437
if self._returning == 'next':
1438
# self.seen contains what nodes have been returned, not what nodes
1439
# have been queried. We don't want to probe for nodes that haven't
1440
# been searched yet.
1441
not_searched_yet = self._next_query
1443
not_searched_yet = ()
1444
pending.difference_update(not_searched_yet)
1445
get_parent_map = self._parents_provider.get_parent_map
1447
parent_map = get_parent_map(pending)
1449
# We don't care if it is a ghost, since it can't be seen if it is
1451
for parent_ids in parent_map.itervalues():
1452
all_parents.extend(parent_ids)
1453
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1454
seen_ancestors.update(next_pending)
1455
next_pending.difference_update(not_searched_yet)
1456
pending = next_pending
1458
return seen_ancestors
1460
def stop_searching_any(self, revisions):
1462
Remove any of the specified revisions from the search list.
1464
None of the specified revisions are required to be present in the
1467
It is okay to call stop_searching_any() for revisions which were seen
1468
in previous iterations. It is the callers responsibility to call
1469
find_seen_ancestors() to make sure that current search tips that are
1470
ancestors of those revisions are also stopped. All explicitly stopped
1471
revisions will be excluded from the search result's get_keys(), though.
1473
# TODO: does this help performance?
1476
revisions = frozenset(revisions)
1477
if self._returning == 'next':
1478
stopped = self._next_query.intersection(revisions)
1479
self._next_query = self._next_query.difference(revisions)
1481
stopped_present = self._current_present.intersection(revisions)
1482
stopped = stopped_present.union(
1483
self._current_ghosts.intersection(revisions))
1484
self._current_present.difference_update(stopped)
1485
self._current_ghosts.difference_update(stopped)
1486
# stopping 'x' should stop returning parents of 'x', but
1487
# not if 'y' always references those same parents
1488
stop_rev_references = {}
1489
for rev in stopped_present:
1490
for parent_id in self._current_parents[rev]:
1491
if parent_id not in stop_rev_references:
1492
stop_rev_references[parent_id] = 0
1493
stop_rev_references[parent_id] += 1
1494
# if only the stopped revisions reference it, the ref count will be
1496
for parents in self._current_parents.itervalues():
1497
for parent_id in parents:
1499
stop_rev_references[parent_id] -= 1
1502
stop_parents = set()
1503
for rev_id, refs in stop_rev_references.iteritems():
1505
stop_parents.add(rev_id)
1506
self._next_query.difference_update(stop_parents)
1507
self._stopped_keys.update(stopped)
1508
self._stopped_keys.update(revisions)
1511
def start_searching(self, revisions):
1512
"""Add revisions to the search.
1514
The parents of revisions will be returned from the next call to next()
1515
or next_with_ghosts(). If next_with_ghosts was the most recently used
1516
next* call then the return value is the result of looking up the
1517
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1519
revisions = frozenset(revisions)
1520
self._started_keys.update(revisions)
1521
new_revisions = revisions.difference(self.seen)
1522
if self._returning == 'next':
1523
self._next_query.update(new_revisions)
1524
self.seen.update(new_revisions)
1526
# perform a query on revisions
1527
revs, ghosts, query, parents = self._do_query(revisions)
1528
self._stopped_keys.update(ghosts)
1529
self._current_present.update(revs)
1530
self._current_ghosts.update(ghosts)
1531
self._next_query.update(query)
1532
self._current_parents.update(parents)
1536
class AbstractSearchResult(object):
1537
"""The result of a search, describing a set of keys.
1539
Search results are typically used as the 'fetch_spec' parameter when
1542
:seealso: AbstractSearch
1545
def get_recipe(self):
1546
"""Return a recipe that can be used to replay this search.
1548
The recipe allows reconstruction of the same results at a later date.
1550
:return: A tuple of (search_kind_str, *details). The details vary by
1551
kind of search result.
1553
raise NotImplementedError(self.get_recipe)
1555
def get_network_struct(self):
1556
"""Return a tuple that can be transmitted via the HPSS protocol."""
1557
raise NotImplementedError(self.get_network_struct)
1560
"""Return the keys found in this search.
1562
:return: A set of keys.
1564
raise NotImplementedError(self.get_keys)
1567
"""Return false if the search lists 1 or more revisions."""
1568
raise NotImplementedError(self.is_empty)
1570
def refine(self, seen, referenced):
1571
"""Create a new search by refining this search.
1573
:param seen: Revisions that have been satisfied.
1574
:param referenced: Revision references observed while satisfying some
1576
:return: A search result.
1578
raise NotImplementedError(self.refine)
1581
class AbstractSearch(object):
1582
"""A search that can be executed, producing a search result.
1584
:seealso: AbstractSearchResult
1588
"""Construct a network-ready search result from this search description.
1590
This may take some time to search repositories, etc.
1592
:return: A search result (an object that implements
1593
AbstractSearchResult's API).
1595
raise NotImplementedError(self.execute)
1598
class SearchResult(AbstractSearchResult):
1599
"""The result of a breadth first search.
1601
A SearchResult provides the ability to reconstruct the search or access a
1602
set of the keys the search found.
1605
def __init__(self, start_keys, exclude_keys, key_count, keys):
1606
"""Create a SearchResult.
1608
:param start_keys: The keys the search started at.
1609
:param exclude_keys: The keys the search excludes.
1610
:param key_count: The total number of keys (from start to but not
1612
:param keys: The keys the search found. Note that in future we may get
1613
a SearchResult from a smart server, in which case the keys list is
1614
not necessarily immediately available.
1616
self._recipe = ('search', start_keys, exclude_keys, key_count)
1617
self._keys = frozenset(keys)
1620
kind, start_keys, exclude_keys, key_count = self._recipe
1621
if len(start_keys) > 5:
1622
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1624
start_keys_repr = repr(start_keys)
1625
if len(exclude_keys) > 5:
1626
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1628
exclude_keys_repr = repr(exclude_keys)
1629
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1630
kind, start_keys_repr, exclude_keys_repr, key_count)
1632
def get_recipe(self):
1633
"""Return a recipe that can be used to replay this search.
1635
The recipe allows reconstruction of the same results at a later date
1636
without knowing all the found keys. The essential elements are a list
1637
of keys to start and to stop at. In order to give reproducible
1638
results when ghosts are encountered by a search they are automatically
1639
added to the exclude list (or else ghost filling may alter the
1642
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1643
revision_count). To recreate the results of this search, create a
1644
breadth first searcher on the same graph starting at start_keys.
1645
Then call next() (or next_with_ghosts()) repeatedly, and on every
1646
result, call stop_searching_any on any keys from the exclude_keys
1647
set. The revision_count value acts as a trivial cross-check - the
1648
found revisions of the new search should have as many elements as
1649
revision_count. If it does not, then additional revisions have been
1650
ghosted since the search was executed the first time and the second
1655
def get_network_struct(self):
1656
start_keys = ' '.join(self._recipe[1])
1657
stop_keys = ' '.join(self._recipe[2])
1658
count = str(self._recipe[3])
1659
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1662
"""Return the keys found in this search.
1664
:return: A set of keys.
1669
"""Return false if the search lists 1 or more revisions."""
1670
return self._recipe[3] == 0
1672
def refine(self, seen, referenced):
1673
"""Create a new search by refining this search.
1675
:param seen: Revisions that have been satisfied.
1676
:param referenced: Revision references observed while satisfying some
1679
start = self._recipe[1]
1680
exclude = self._recipe[2]
1681
count = self._recipe[3]
1682
keys = self.get_keys()
1683
# New heads = referenced + old heads - seen things - exclude
1684
pending_refs = set(referenced)
1685
pending_refs.update(start)
1686
pending_refs.difference_update(seen)
1687
pending_refs.difference_update(exclude)
1688
# New exclude = old exclude + satisfied heads
1689
seen_heads = start.intersection(seen)
1690
exclude.update(seen_heads)
1691
# keys gets seen removed
1693
# length is reduced by len(seen)
1695
return SearchResult(pending_refs, exclude, count, keys)
1698
class PendingAncestryResult(AbstractSearchResult):
1699
"""A search result that will reconstruct the ancestry for some graph heads.
1701
Unlike SearchResult, this doesn't hold the complete search result in
1702
memory, it just holds a description of how to generate it.
1705
def __init__(self, heads, repo):
1708
:param heads: an iterable of graph heads.
1709
:param repo: a repository to use to generate the ancestry for the given
1712
self.heads = frozenset(heads)
1716
if len(self.heads) > 5:
1717
heads_repr = repr(list(self.heads)[:5])[:-1]
1718
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1720
heads_repr = repr(self.heads)
1721
return '<%s heads:%s repo:%r>' % (
1722
self.__class__.__name__, heads_repr, self.repo)
1724
def get_recipe(self):
1725
"""Return a recipe that can be used to replay this search.
1727
The recipe allows reconstruction of the same results at a later date.
1729
:seealso SearchResult.get_recipe:
1731
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1732
To recreate this result, create a PendingAncestryResult with the
1735
return ('proxy-search', self.heads, set(), -1)
1737
def get_network_struct(self):
1738
parts = ['ancestry-of']
1739
parts.extend(self.heads)
1743
"""See SearchResult.get_keys.
1745
Returns all the keys for the ancestry of the heads, excluding
1748
return self._get_keys(self.repo.get_graph())
1750
def _get_keys(self, graph):
1751
NULL_REVISION = revision.NULL_REVISION
1752
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1753
if key != NULL_REVISION and parents is not None]
1757
"""Return false if the search lists 1 or more revisions."""
1758
if revision.NULL_REVISION in self.heads:
1759
return len(self.heads) == 1
1761
return len(self.heads) == 0
1763
def refine(self, seen, referenced):
1764
"""Create a new search by refining this search.
1766
:param seen: Revisions that have been satisfied.
1767
:param referenced: Revision references observed while satisfying some
1770
referenced = self.heads.union(referenced)
1771
return PendingAncestryResult(referenced - seen, self.repo)
1774
class EmptySearchResult(AbstractSearchResult):
1775
"""An empty search result."""
1781
class EverythingResult(AbstractSearchResult):
1782
"""A search result that simply requests everything in the repository."""
1784
def __init__(self, repo):
1788
return '%s(%r)' % (self.__class__.__name__, self._repo)
1790
def get_recipe(self):
1791
raise NotImplementedError(self.get_recipe)
1793
def get_network_struct(self):
1794
return ('everything',)
1797
if 'evil' in debug.debug_flags:
1798
from bzrlib import remote
1799
if isinstance(self._repo, remote.RemoteRepository):
1800
# warn developers (not users) not to do this
1801
trace.mutter_callsite(
1802
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1803
return self._repo.all_revision_ids()
1806
# It's ok for this to wrongly return False: the worst that can happen
1807
# is that RemoteStreamSource will initiate a get_stream on an empty
1808
# repository. And almost all repositories are non-empty.
1811
def refine(self, seen, referenced):
1812
heads = set(self._repo.all_revision_ids())
1813
heads.difference_update(seen)
1814
heads.update(referenced)
1815
return PendingAncestryResult(heads, self._repo)
1818
class EverythingNotInOther(AbstractSearch):
1819
"""Find all revisions in that are in one repo but not the other."""
1821
def __init__(self, to_repo, from_repo, find_ghosts=False):
1822
self.to_repo = to_repo
1823
self.from_repo = from_repo
1824
self.find_ghosts = find_ghosts
1827
return self.to_repo.search_missing_revision_ids(
1828
self.from_repo, find_ghosts=self.find_ghosts)
1831
class NotInOtherForRevs(AbstractSearch):
1832
"""Find all revisions missing in one repo for a some specific heads."""
1834
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1838
:param required_ids: revision IDs of heads that must be found, or else
1839
the search will fail with NoSuchRevision. All revisions in their
1840
ancestry not already in the other repository will be included in
1842
:param if_present_ids: revision IDs of heads that may be absent in the
1843
source repository. If present, then their ancestry not already
1844
found in other will be included in the search result.
1846
self.to_repo = to_repo
1847
self.from_repo = from_repo
1848
self.find_ghosts = find_ghosts
1849
self.required_ids = required_ids
1850
self.if_present_ids = if_present_ids
1853
if len(self.required_ids) > 5:
1854
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1856
reqd_revs_repr = repr(self.required_ids)
1857
if self.if_present_ids and len(self.if_present_ids) > 5:
1858
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1860
ifp_revs_repr = repr(self.if_present_ids)
1862
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1863
self.__class__.__name__, self.from_repo, self.to_repo,
1864
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1867
return self.to_repo.search_missing_revision_ids(
1868
self.from_repo, revision_ids=self.required_ids,
1869
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1872
def collapse_linear_regions(parent_map):
1873
"""Collapse regions of the graph that are 'linear'.
1879
can be collapsed by removing B and getting::
1883
:param parent_map: A dictionary mapping children to their parents
1884
:return: Another dictionary with 'linear' chains collapsed
1886
# Note: this isn't a strictly minimal collapse. For example:
1894
# Will not have 'D' removed, even though 'E' could fit. Also:
1900
# A and C are both kept because they are edges of the graph. We *could* get
1901
# rid of A if we wanted.
1909
# Will not have any nodes removed, even though you do have an
1910
# 'uninteresting' linear D->B and E->C
1912
for child, parents in parent_map.iteritems():
1913
children.setdefault(child, [])
1915
children.setdefault(p, []).append(child)
1917
orig_children = dict(children)
1919
result = dict(parent_map)
1920
for node in parent_map:
1921
parents = result[node]
1922
if len(parents) == 1:
1923
parent_children = children[parents[0]]
1924
if len(parent_children) != 1:
1925
# This is not the only child
1927
node_children = children[node]
1928
if len(node_children) != 1:
1930
child_parents = result.get(node_children[0], None)
1931
if len(child_parents) != 1:
1932
# This is not its only parent
1934
# The child of this node only points at it, and the parent only has
1935
# this as a child. remove this node, and join the others together
1936
result[node_children[0]] = parents
1937
children[parents[0]] = node_children
1945
class GraphThunkIdsToKeys(object):
1946
"""Forwards calls about 'ids' to be about keys internally."""
1948
def __init__(self, graph):
1951
def topo_sort(self):
1952
return [r for (r,) in self._graph.topo_sort()]
1954
def heads(self, ids):
1955
"""See Graph.heads()"""
1956
as_keys = [(i,) for i in ids]
1957
head_keys = self._graph.heads(as_keys)
1958
return set([h[0] for h in head_keys])
1960
def merge_sort(self, tip_revision):
1961
return self._graph.merge_sort((tip_revision,))
1963
def add_node(self, revision, parents):
1964
self._graph.add_node((revision,), [(p,) for p in parents])
1967
_counters = [0,0,0,0,0,0,0]
1969
from bzrlib._known_graph_pyx import KnownGraph
1970
except ImportError, e:
1971
osutils.failed_to_load_extension(e)
1972
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
