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
27
STEP_UNIQUE_SEARCHER_EVERY = 5
29
# DIAGRAM of terminology
39
# In this diagram, relative to G and H:
40
# A, B, C, D, E are common ancestors.
41
# C, D and E are border ancestors, because each has a non-common descendant.
42
# D and E are least common ancestors because none of their descendants are
44
# C is not a least common ancestor because its descendant, E, is a common
47
# The find_unique_lca algorithm will pick A in two steps:
48
# 1. find_lca('G', 'H') => ['D', 'E']
49
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
52
class DictParentsProvider(object):
53
"""A parents provider for Graph objects."""
55
def __init__(self, ancestry):
56
self.ancestry = ancestry
59
return 'DictParentsProvider(%r)' % self.ancestry
61
def get_parent_map(self, keys):
62
"""See StackedParentsProvider.get_parent_map"""
63
ancestry = self.ancestry
64
return dict((k, ancestry[k]) for k in keys if k in ancestry)
67
class StackedParentsProvider(object):
68
"""A parents provider which stacks (or unions) multiple providers.
70
The providers are queries in the order of the provided parent_providers.
73
def __init__(self, parent_providers):
74
self._parent_providers = parent_providers
77
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
79
def get_parent_map(self, keys):
80
"""Get a mapping of keys => parents
82
A dictionary is returned with an entry for each key present in this
83
source. If this source doesn't have information about a key, it should
86
[NULL_REVISION] is used as the parent of the first user-committed
87
revision. Its parent list is empty.
89
:param keys: An iterable returning keys to check (eg revision_ids)
90
:return: A dictionary mapping each key to its parents
94
for parents_provider in self._parent_providers:
95
new_found = parents_provider.get_parent_map(remaining)
96
found.update(new_found)
97
remaining.difference_update(new_found)
103
class CachingParentsProvider(object):
104
"""A parents provider which will cache the revision => parents as a dict.
106
This is useful for providers which have an expensive look up.
108
Either a ParentsProvider or a get_parent_map-like callback may be
109
supplied. If it provides extra un-asked-for parents, they will be cached,
110
but filtered out of get_parent_map.
112
The cache is enabled by default, but may be disabled and re-enabled.
114
def __init__(self, parent_provider=None, get_parent_map=None):
117
:param parent_provider: The ParentProvider to use. It or
118
get_parent_map must be supplied.
119
:param get_parent_map: The get_parent_map callback to use. It or
120
parent_provider must be supplied.
122
self._real_provider = parent_provider
123
if get_parent_map is None:
124
self._get_parent_map = self._real_provider.get_parent_map
126
self._get_parent_map = get_parent_map
128
self.enable_cache(True)
131
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
133
def enable_cache(self, cache_misses=True):
135
if self._cache is not None:
136
raise AssertionError('Cache enabled when already enabled.')
138
self._cache_misses = cache_misses
139
self.missing_keys = set()
141
def disable_cache(self):
142
"""Disable and clear the cache."""
144
self._cache_misses = None
145
self.missing_keys = set()
147
def get_cached_map(self):
148
"""Return any cached get_parent_map values."""
149
if self._cache is None:
151
return dict(self._cache)
153
def get_parent_map(self, keys):
154
"""See StackedParentsProvider.get_parent_map."""
157
cache = self._get_parent_map(keys)
159
needed_revisions = set(key for key in keys if key not in cache)
160
# Do not ask for negatively cached keys
161
needed_revisions.difference_update(self.missing_keys)
163
parent_map = self._get_parent_map(needed_revisions)
164
cache.update(parent_map)
165
if self._cache_misses:
166
for key in needed_revisions:
167
if key not in parent_map:
168
self.note_missing_key(key)
171
value = cache.get(key)
172
if value is not None:
176
def note_missing_key(self, key):
177
"""Note that key is a missing key."""
178
if self._cache_misses:
179
self.missing_keys.add(key)
182
class CallableToParentsProviderAdapter(object):
183
"""A parents provider that adapts any callable to the parents provider API.
185
i.e. it accepts calls to self.get_parent_map and relays them to the
186
callable it was constructed with.
189
def __init__(self, a_callable):
190
self.callable = a_callable
193
return "%s(%r)" % (self.__class__.__name__, self.callable)
195
def get_parent_map(self, keys):
196
return self.callable(keys)
200
"""Provide incremental access to revision graphs.
202
This is the generic implementation; it is intended to be subclassed to
203
specialize it for other repository types.
206
def __init__(self, parents_provider):
207
"""Construct a Graph that uses several graphs as its input
209
This should not normally be invoked directly, because there may be
210
specialized implementations for particular repository types. See
211
Repository.get_graph().
213
:param parents_provider: An object providing a get_parent_map call
214
conforming to the behavior of
215
StackedParentsProvider.get_parent_map.
217
if getattr(parents_provider, 'get_parents', None) is not None:
218
self.get_parents = parents_provider.get_parents
219
if getattr(parents_provider, 'get_parent_map', None) is not None:
220
self.get_parent_map = parents_provider.get_parent_map
221
self._parents_provider = parents_provider
224
return 'Graph(%r)' % self._parents_provider
226
def find_lca(self, *revisions):
227
"""Determine the lowest common ancestors of the provided revisions
229
A lowest common ancestor is a common ancestor none of whose
230
descendants are common ancestors. In graphs, unlike trees, there may
231
be multiple lowest common ancestors.
233
This algorithm has two phases. Phase 1 identifies border ancestors,
234
and phase 2 filters border ancestors to determine lowest common
237
In phase 1, border ancestors are identified, using a breadth-first
238
search starting at the bottom of the graph. Searches are stopped
239
whenever a node or one of its descendants is determined to be common
241
In phase 2, the border ancestors are filtered to find the least
242
common ancestors. This is done by searching the ancestries of each
245
Phase 2 is perfomed on the principle that a border ancestor that is
246
not an ancestor of any other border ancestor is a least common
249
Searches are stopped when they find a node that is determined to be a
250
common ancestor of all border ancestors, because this shows that it
251
cannot be a descendant of any border ancestor.
253
The scaling of this operation should be proportional to:
255
1. The number of uncommon ancestors
256
2. The number of border ancestors
257
3. The length of the shortest path between a border ancestor and an
258
ancestor of all border ancestors.
260
border_common, common, sides = self._find_border_ancestors(revisions)
261
# We may have common ancestors that can be reached from each other.
262
# - ask for the heads of them to filter it down to only ones that
263
# cannot be reached from each other - phase 2.
264
return self.heads(border_common)
266
def find_difference(self, left_revision, right_revision):
267
"""Determine the graph difference between two revisions"""
268
border, common, searchers = self._find_border_ancestors(
269
[left_revision, right_revision])
270
self._search_for_extra_common(common, searchers)
271
left = searchers[0].seen
272
right = searchers[1].seen
273
return (left.difference(right), right.difference(left))
275
def find_descendants(self, old_key, new_key):
276
"""Find descendants of old_key that are ancestors of new_key."""
277
child_map = self.get_child_map(self._find_descendant_ancestors(
279
graph = Graph(DictParentsProvider(child_map))
280
searcher = graph._make_breadth_first_searcher([old_key])
284
def _find_descendant_ancestors(self, old_key, new_key):
285
"""Find ancestors of new_key that may be descendants of old_key."""
286
stop = self._make_breadth_first_searcher([old_key])
287
descendants = self._make_breadth_first_searcher([new_key])
288
for revisions in descendants:
289
old_stop = stop.seen.intersection(revisions)
290
descendants.stop_searching_any(old_stop)
291
seen_stop = descendants.find_seen_ancestors(stop.step())
292
descendants.stop_searching_any(seen_stop)
293
return descendants.seen.difference(stop.seen)
295
def get_child_map(self, keys):
296
"""Get a mapping from parents to children of the specified keys.
298
This is simply the inversion of get_parent_map. Only supplied keys
299
will be discovered as children.
300
:return: a dict of key:child_list for keys.
302
parent_map = self._parents_provider.get_parent_map(keys)
304
for child, parents in sorted(parent_map.items()):
305
for parent in parents:
306
parent_child.setdefault(parent, []).append(child)
309
def find_distance_to_null(self, target_revision_id, known_revision_ids):
310
"""Find the left-hand distance to the NULL_REVISION.
312
(This can also be considered the revno of a branch at
315
:param target_revision_id: A revision_id which we would like to know
317
:param known_revision_ids: [(revision_id, revno)] A list of known
318
revno, revision_id tuples. We'll use this to seed the search.
320
# Map from revision_ids to a known value for their revno
321
known_revnos = dict(known_revision_ids)
322
cur_tip = target_revision_id
324
NULL_REVISION = revision.NULL_REVISION
325
known_revnos[NULL_REVISION] = 0
327
searching_known_tips = list(known_revnos.keys())
329
unknown_searched = {}
331
while cur_tip not in known_revnos:
332
unknown_searched[cur_tip] = num_steps
334
to_search = set([cur_tip])
335
to_search.update(searching_known_tips)
336
parent_map = self.get_parent_map(to_search)
337
parents = parent_map.get(cur_tip, None)
338
if not parents: # An empty list or None is a ghost
339
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
343
for revision_id in searching_known_tips:
344
parents = parent_map.get(revision_id, None)
348
next_revno = known_revnos[revision_id] - 1
349
if next in unknown_searched:
350
# We have enough information to return a value right now
351
return next_revno + unknown_searched[next]
352
if next in known_revnos:
354
known_revnos[next] = next_revno
355
next_known_tips.append(next)
356
searching_known_tips = next_known_tips
358
# We reached a known revision, so just add in how many steps it took to
360
return known_revnos[cur_tip] + num_steps
362
def find_lefthand_distances(self, keys):
363
"""Find the distance to null for all the keys in keys.
365
:param keys: keys to lookup.
366
:return: A dict key->distance for all of keys.
368
# Optimisable by concurrent searching, but a random spread should get
369
# some sort of hit rate.
376
(key, self.find_distance_to_null(key, known_revnos)))
377
except errors.GhostRevisionsHaveNoRevno:
380
known_revnos.append((key, -1))
381
return dict(known_revnos)
383
def find_unique_ancestors(self, unique_revision, common_revisions):
384
"""Find the unique ancestors for a revision versus others.
386
This returns the ancestry of unique_revision, excluding all revisions
387
in the ancestry of common_revisions. If unique_revision is in the
388
ancestry, then the empty set will be returned.
390
:param unique_revision: The revision_id whose ancestry we are
392
(XXX: Would this API be better if we allowed multiple revisions on
393
to be searched here?)
394
:param common_revisions: Revision_ids of ancestries to exclude.
395
:return: A set of revisions in the ancestry of unique_revision
397
if unique_revision in common_revisions:
400
# Algorithm description
401
# 1) Walk backwards from the unique node and all common nodes.
402
# 2) When a node is seen by both sides, stop searching it in the unique
403
# walker, include it in the common walker.
404
# 3) Stop searching when there are no nodes left for the unique walker.
405
# At this point, you have a maximal set of unique nodes. Some of
406
# them may actually be common, and you haven't reached them yet.
407
# 4) Start new searchers for the unique nodes, seeded with the
408
# information you have so far.
409
# 5) Continue searching, stopping the common searches when the search
410
# tip is an ancestor of all unique nodes.
411
# 6) Aggregate together unique searchers when they are searching the
412
# same tips. When all unique searchers are searching the same node,
413
# stop move it to a single 'all_unique_searcher'.
414
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
415
# Most of the time this produces very little important information.
416
# So don't step it as quickly as the other searchers.
417
# 8) Search is done when all common searchers have completed.
419
unique_searcher, common_searcher = self._find_initial_unique_nodes(
420
[unique_revision], common_revisions)
422
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
426
(all_unique_searcher,
427
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
428
unique_searcher, common_searcher)
430
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
431
unique_tip_searchers, common_searcher)
432
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
433
if 'graph' in debug.debug_flags:
434
trace.mutter('Found %d truly unique nodes out of %d',
435
len(true_unique_nodes), len(unique_nodes))
436
return true_unique_nodes
438
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
439
"""Steps 1-3 of find_unique_ancestors.
441
Find the maximal set of unique nodes. Some of these might actually
442
still be common, but we are sure that there are no other unique nodes.
444
:return: (unique_searcher, common_searcher)
447
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
448
# we know that unique_revisions aren't in common_revisions, so skip
450
unique_searcher.next()
451
common_searcher = self._make_breadth_first_searcher(common_revisions)
453
# As long as we are still finding unique nodes, keep searching
454
while unique_searcher._next_query:
455
next_unique_nodes = set(unique_searcher.step())
456
next_common_nodes = set(common_searcher.step())
458
# Check if either searcher encounters new nodes seen by the other
460
unique_are_common_nodes = next_unique_nodes.intersection(
461
common_searcher.seen)
462
unique_are_common_nodes.update(
463
next_common_nodes.intersection(unique_searcher.seen))
464
if unique_are_common_nodes:
465
ancestors = unique_searcher.find_seen_ancestors(
466
unique_are_common_nodes)
467
# TODO: This is a bit overboard, we only really care about
468
# the ancestors of the tips because the rest we
469
# already know. This is *correct* but causes us to
470
# search too much ancestry.
471
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
472
unique_searcher.stop_searching_any(ancestors)
473
common_searcher.start_searching(ancestors)
475
return unique_searcher, common_searcher
477
def _make_unique_searchers(self, unique_nodes, unique_searcher,
479
"""Create a searcher for all the unique search tips (step 4).
481
As a side effect, the common_searcher will stop searching any nodes
482
that are ancestors of the unique searcher tips.
484
:return: (all_unique_searcher, unique_tip_searchers)
486
unique_tips = self._remove_simple_descendants(unique_nodes,
487
self.get_parent_map(unique_nodes))
489
if len(unique_tips) == 1:
490
unique_tip_searchers = []
491
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
493
unique_tip_searchers = []
494
for tip in unique_tips:
495
revs_to_search = unique_searcher.find_seen_ancestors([tip])
496
revs_to_search.update(
497
common_searcher.find_seen_ancestors(revs_to_search))
498
searcher = self._make_breadth_first_searcher(revs_to_search)
499
# We don't care about the starting nodes.
500
searcher._label = tip
502
unique_tip_searchers.append(searcher)
504
ancestor_all_unique = None
505
for searcher in unique_tip_searchers:
506
if ancestor_all_unique is None:
507
ancestor_all_unique = set(searcher.seen)
509
ancestor_all_unique = ancestor_all_unique.intersection(
511
# Collapse all the common nodes into a single searcher
512
all_unique_searcher = self._make_breadth_first_searcher(
514
if ancestor_all_unique:
515
# We've seen these nodes in all the searchers, so we'll just go to
517
all_unique_searcher.step()
519
# Stop any search tips that are already known as ancestors of the
521
stopped_common = common_searcher.stop_searching_any(
522
common_searcher.find_seen_ancestors(ancestor_all_unique))
525
for searcher in unique_tip_searchers:
526
total_stopped += len(searcher.stop_searching_any(
527
searcher.find_seen_ancestors(ancestor_all_unique)))
528
if 'graph' in debug.debug_flags:
529
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
530
' (%d stopped search tips, %d common ancestors'
531
' (%d stopped common)',
532
len(unique_nodes), len(unique_tip_searchers),
533
total_stopped, len(ancestor_all_unique),
535
return all_unique_searcher, unique_tip_searchers
537
def _step_unique_and_common_searchers(self, common_searcher,
538
unique_tip_searchers,
540
"""Step all the searchers"""
541
newly_seen_common = set(common_searcher.step())
542
newly_seen_unique = set()
543
for searcher in unique_tip_searchers:
544
next = set(searcher.step())
545
next.update(unique_searcher.find_seen_ancestors(next))
546
next.update(common_searcher.find_seen_ancestors(next))
547
for alt_searcher in unique_tip_searchers:
548
if alt_searcher is searcher:
550
next.update(alt_searcher.find_seen_ancestors(next))
551
searcher.start_searching(next)
552
newly_seen_unique.update(next)
553
return newly_seen_common, newly_seen_unique
555
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
557
newly_seen_unique, step_all_unique):
558
"""Find nodes that are common to all unique_tip_searchers.
560
If it is time, step the all_unique_searcher, and add its nodes to the
563
common_to_all_unique_nodes = newly_seen_unique.copy()
564
for searcher in unique_tip_searchers:
565
common_to_all_unique_nodes.intersection_update(searcher.seen)
566
common_to_all_unique_nodes.intersection_update(
567
all_unique_searcher.seen)
568
# Step all-unique less frequently than the other searchers.
569
# In the common case, we don't need to spider out far here, so
570
# avoid doing extra work.
572
tstart = time.clock()
573
nodes = all_unique_searcher.step()
574
common_to_all_unique_nodes.update(nodes)
575
if 'graph' in debug.debug_flags:
576
tdelta = time.clock() - tstart
577
trace.mutter('all_unique_searcher step() took %.3fs'
578
'for %d nodes (%d total), iteration: %s',
579
tdelta, len(nodes), len(all_unique_searcher.seen),
580
all_unique_searcher._iterations)
581
return common_to_all_unique_nodes
583
def _collapse_unique_searchers(self, unique_tip_searchers,
584
common_to_all_unique_nodes):
585
"""Combine searchers that are searching the same tips.
587
When two searchers are searching the same tips, we can stop one of the
588
searchers. We also know that the maximal set of common ancestors is the
589
intersection of the two original searchers.
591
:return: A list of searchers that are searching unique nodes.
593
# Filter out searchers that don't actually search different
594
# nodes. We already have the ancestry intersection for them
595
unique_search_tips = {}
596
for searcher in unique_tip_searchers:
597
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
598
will_search_set = frozenset(searcher._next_query)
599
if not will_search_set:
600
if 'graph' in debug.debug_flags:
601
trace.mutter('Unique searcher %s was stopped.'
602
' (%s iterations) %d nodes stopped',
604
searcher._iterations,
606
elif will_search_set not in unique_search_tips:
607
# This searcher is searching a unique set of nodes, let it
608
unique_search_tips[will_search_set] = [searcher]
610
unique_search_tips[will_search_set].append(searcher)
611
# TODO: it might be possible to collapse searchers faster when they
612
# only have *some* search tips in common.
613
next_unique_searchers = []
614
for searchers in unique_search_tips.itervalues():
615
if len(searchers) == 1:
616
# Searching unique tips, go for it
617
next_unique_searchers.append(searchers[0])
619
# These searchers have started searching the same tips, we
620
# don't need them to cover the same ground. The
621
# intersection of their ancestry won't change, so create a
622
# new searcher, combining their histories.
623
next_searcher = searchers[0]
624
for searcher in searchers[1:]:
625
next_searcher.seen.intersection_update(searcher.seen)
626
if 'graph' in debug.debug_flags:
627
trace.mutter('Combining %d searchers into a single'
628
' searcher searching %d nodes with'
631
len(next_searcher._next_query),
632
len(next_searcher.seen))
633
next_unique_searchers.append(next_searcher)
634
return next_unique_searchers
636
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
637
unique_tip_searchers, common_searcher):
638
"""Steps 5-8 of find_unique_ancestors.
640
This function returns when common_searcher has stopped searching for
643
# We step the ancestor_all_unique searcher only every
644
# STEP_UNIQUE_SEARCHER_EVERY steps.
645
step_all_unique_counter = 0
646
# While we still have common nodes to search
647
while common_searcher._next_query:
649
newly_seen_unique) = self._step_unique_and_common_searchers(
650
common_searcher, unique_tip_searchers, unique_searcher)
651
# These nodes are common ancestors of all unique nodes
652
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
653
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
654
step_all_unique_counter==0)
655
step_all_unique_counter = ((step_all_unique_counter + 1)
656
% STEP_UNIQUE_SEARCHER_EVERY)
658
if newly_seen_common:
659
# If a 'common' node is an ancestor of all unique searchers, we
660
# can stop searching it.
661
common_searcher.stop_searching_any(
662
all_unique_searcher.seen.intersection(newly_seen_common))
663
if common_to_all_unique_nodes:
664
common_to_all_unique_nodes.update(
665
common_searcher.find_seen_ancestors(
666
common_to_all_unique_nodes))
667
# The all_unique searcher can start searching the common nodes
668
# but everyone else can stop.
669
# This is the sort of thing where we would like to not have it
670
# start_searching all of the nodes, but only mark all of them
671
# as seen, and have it search only the actual tips. Otherwise
672
# it is another get_parent_map() traversal for it to figure out
673
# what we already should know.
674
all_unique_searcher.start_searching(common_to_all_unique_nodes)
675
common_searcher.stop_searching_any(common_to_all_unique_nodes)
677
next_unique_searchers = self._collapse_unique_searchers(
678
unique_tip_searchers, common_to_all_unique_nodes)
679
if len(unique_tip_searchers) != len(next_unique_searchers):
680
if 'graph' in debug.debug_flags:
681
trace.mutter('Collapsed %d unique searchers => %d'
683
len(unique_tip_searchers),
684
len(next_unique_searchers),
685
all_unique_searcher._iterations)
686
unique_tip_searchers = next_unique_searchers
688
def get_parent_map(self, revisions):
689
"""Get a map of key:parent_list for revisions.
691
This implementation delegates to get_parents, for old parent_providers
692
that do not supply get_parent_map.
695
for rev, parents in self.get_parents(revisions):
696
if parents is not None:
697
result[rev] = parents
700
def _make_breadth_first_searcher(self, revisions):
701
return _BreadthFirstSearcher(revisions, self)
703
def _find_border_ancestors(self, revisions):
704
"""Find common ancestors with at least one uncommon descendant.
706
Border ancestors are identified using a breadth-first
707
search starting at the bottom of the graph. Searches are stopped
708
whenever a node or one of its descendants is determined to be common.
710
This will scale with the number of uncommon ancestors.
712
As well as the border ancestors, a set of seen common ancestors and a
713
list of sets of seen ancestors for each input revision is returned.
714
This allows calculation of graph difference from the results of this
717
if None in revisions:
718
raise errors.InvalidRevisionId(None, self)
719
common_ancestors = set()
720
searchers = [self._make_breadth_first_searcher([r])
722
active_searchers = searchers[:]
723
border_ancestors = set()
727
for searcher in searchers:
728
new_ancestors = searcher.step()
730
newly_seen.update(new_ancestors)
732
for revision in newly_seen:
733
if revision in common_ancestors:
734
# Not a border ancestor because it was seen as common
736
new_common.add(revision)
738
for searcher in searchers:
739
if revision not in searcher.seen:
742
# This is a border because it is a first common that we see
743
# after walking for a while.
744
border_ancestors.add(revision)
745
new_common.add(revision)
747
for searcher in searchers:
748
new_common.update(searcher.find_seen_ancestors(new_common))
749
for searcher in searchers:
750
searcher.start_searching(new_common)
751
common_ancestors.update(new_common)
753
# Figure out what the searchers will be searching next, and if
754
# there is only 1 set being searched, then we are done searching,
755
# since all searchers would have to be searching the same data,
756
# thus it *must* be in common.
757
unique_search_sets = set()
758
for searcher in searchers:
759
will_search_set = frozenset(searcher._next_query)
760
if will_search_set not in unique_search_sets:
761
# This searcher is searching a unique set of nodes, let it
762
unique_search_sets.add(will_search_set)
764
if len(unique_search_sets) == 1:
765
nodes = unique_search_sets.pop()
766
uncommon_nodes = nodes.difference(common_ancestors)
768
raise AssertionError("Somehow we ended up converging"
769
" without actually marking them as"
772
"\nuncommon_nodes: %s"
773
% (revisions, uncommon_nodes))
775
return border_ancestors, common_ancestors, searchers
777
def heads(self, keys):
778
"""Return the heads from amongst keys.
780
This is done by searching the ancestries of each key. Any key that is
781
reachable from another key is not returned; all the others are.
783
This operation scales with the relative depth between any two keys. If
784
any two keys are completely disconnected all ancestry of both sides
787
:param keys: An iterable of keys.
788
:return: A set of the heads. Note that as a set there is no ordering
789
information. Callers will need to filter their input to create
790
order if they need it.
792
candidate_heads = set(keys)
793
if revision.NULL_REVISION in candidate_heads:
794
# NULL_REVISION is only a head if it is the only entry
795
candidate_heads.remove(revision.NULL_REVISION)
796
if not candidate_heads:
797
return set([revision.NULL_REVISION])
798
if len(candidate_heads) < 2:
799
return candidate_heads
800
searchers = dict((c, self._make_breadth_first_searcher([c]))
801
for c in candidate_heads)
802
active_searchers = dict(searchers)
803
# skip over the actual candidate for each searcher
804
for searcher in active_searchers.itervalues():
806
# The common walker finds nodes that are common to two or more of the
807
# input keys, so that we don't access all history when a currently
808
# uncommon search point actually meets up with something behind a
809
# common search point. Common search points do not keep searches
810
# active; they just allow us to make searches inactive without
811
# accessing all history.
812
common_walker = self._make_breadth_first_searcher([])
813
while len(active_searchers) > 0:
818
except StopIteration:
819
# No common points being searched at this time.
821
for candidate in active_searchers.keys():
823
searcher = active_searchers[candidate]
825
# rare case: we deleted candidate in a previous iteration
826
# through this for loop, because it was determined to be
827
# a descendant of another candidate.
830
ancestors.update(searcher.next())
831
except StopIteration:
832
del active_searchers[candidate]
834
# process found nodes
836
for ancestor in ancestors:
837
if ancestor in candidate_heads:
838
candidate_heads.remove(ancestor)
839
del searchers[ancestor]
840
if ancestor in active_searchers:
841
del active_searchers[ancestor]
842
# it may meet up with a known common node
843
if ancestor in common_walker.seen:
844
# some searcher has encountered our known common nodes:
846
ancestor_set = set([ancestor])
847
for searcher in searchers.itervalues():
848
searcher.stop_searching_any(ancestor_set)
850
# or it may have been just reached by all the searchers:
851
for searcher in searchers.itervalues():
852
if ancestor not in searcher.seen:
855
# The final active searcher has just reached this node,
856
# making it be known as a descendant of all candidates,
857
# so we can stop searching it, and any seen ancestors
858
new_common.add(ancestor)
859
for searcher in searchers.itervalues():
861
searcher.find_seen_ancestors([ancestor])
862
searcher.stop_searching_any(seen_ancestors)
863
common_walker.start_searching(new_common)
864
return candidate_heads
866
def find_merge_order(self, tip_revision_id, lca_revision_ids):
867
"""Find the order that each revision was merged into tip.
869
This basically just walks backwards with a stack, and walks left-first
870
until it finds a node to stop.
872
if len(lca_revision_ids) == 1:
873
return list(lca_revision_ids)
874
looking_for = set(lca_revision_ids)
875
# TODO: Is there a way we could do this "faster" by batching up the
876
# get_parent_map requests?
877
# TODO: Should we also be culling the ancestry search right away? We
878
# could add looking_for to the "stop" list, and walk their
879
# ancestry in batched mode. The flip side is it might mean we walk a
880
# lot of "stop" nodes, rather than only the minimum.
881
# Then again, without it we may trace back into ancestry we could have
883
stack = [tip_revision_id]
886
while stack and looking_for:
889
if next in looking_for:
891
looking_for.remove(next)
892
if len(looking_for) == 1:
893
found.append(looking_for.pop())
896
parent_ids = self.get_parent_map([next]).get(next, None)
897
if not parent_ids: # Ghost, nothing to search here
899
for parent_id in reversed(parent_ids):
900
# TODO: (performance) We see the parent at this point, but we
901
# wait to mark it until later to make sure we get left
902
# parents before right parents. However, instead of
903
# waiting until we have traversed enough parents, we
904
# could instead note that we've found it, and once all
905
# parents are in the stack, just reverse iterate the
907
if parent_id not in stop:
908
# this will need to be searched
909
stack.append(parent_id)
913
def find_lefthand_merger(self, merged_key, tip_key):
914
"""Find the first lefthand ancestor of tip_key that merged merged_key.
916
We do this by first finding the descendants of merged_key, then
917
walking through the lefthand ancestry of tip_key until we find a key
918
that doesn't descend from merged_key. Its child is the key that
921
:return: The first lefthand ancestor of tip_key to merge merged_key.
922
merged_key if it is a lefthand ancestor of tip_key.
923
None if no ancestor of tip_key merged merged_key.
925
descendants = self.find_descendants(merged_key, tip_key)
926
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
927
last_candidate = None
928
for candidate in candidate_iterator:
929
if candidate not in descendants:
930
return last_candidate
931
last_candidate = candidate
933
def find_unique_lca(self, left_revision, right_revision,
935
"""Find a unique LCA.
937
Find lowest common ancestors. If there is no unique common
938
ancestor, find the lowest common ancestors of those ancestors.
940
Iteration stops when a unique lowest common ancestor is found.
941
The graph origin is necessarily a unique lowest common ancestor.
943
Note that None is not an acceptable substitute for NULL_REVISION.
944
in the input for this method.
946
:param count_steps: If True, the return value will be a tuple of
947
(unique_lca, steps) where steps is the number of times that
948
find_lca was run. If False, only unique_lca is returned.
950
revisions = [left_revision, right_revision]
954
lca = self.find_lca(*revisions)
962
raise errors.NoCommonAncestor(left_revision, right_revision)
965
def iter_ancestry(self, revision_ids):
966
"""Iterate the ancestry of this revision.
968
:param revision_ids: Nodes to start the search
969
:return: Yield tuples mapping a revision_id to its parents for the
970
ancestry of revision_id.
971
Ghosts will be returned with None as their parents, and nodes
972
with no parents will have NULL_REVISION as their only parent. (As
973
defined by get_parent_map.)
974
There will also be a node for (NULL_REVISION, ())
976
pending = set(revision_ids)
979
processed.update(pending)
980
next_map = self.get_parent_map(pending)
982
for item in next_map.iteritems():
984
next_pending.update(p for p in item[1] if p not in processed)
985
ghosts = pending.difference(next_map)
988
pending = next_pending
990
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
991
if stop_keys is None:
994
def get_parents(key):
996
return self._parents_provider.get_parent_map([key])[key]
998
raise errors.RevisionNotPresent(next_key, self)
1000
if next_key in stop_keys:
1002
parents = get_parents(next_key)
1004
if len(parents) == 0:
1007
next_key = parents[0]
1009
def iter_topo_order(self, revisions):
1010
"""Iterate through the input revisions in topological order.
1012
This sorting only ensures that parents come before their children.
1013
An ancestor may sort after a descendant if the relationship is not
1014
visible in the supplied list of revisions.
1016
from bzrlib import tsort
1017
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1018
return sorter.iter_topo_order()
1020
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1021
"""Determine whether a revision is an ancestor of another.
1023
We answer this using heads() as heads() has the logic to perform the
1024
smallest number of parent lookups to determine the ancestral
1025
relationship between N revisions.
1027
return set([candidate_descendant]) == self.heads(
1028
[candidate_ancestor, candidate_descendant])
1030
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1031
"""Determine whether a revision is between two others.
1033
returns true if and only if:
1034
lower_bound_revid <= revid <= upper_bound_revid
1036
return ((upper_bound_revid is None or
1037
self.is_ancestor(revid, upper_bound_revid)) and
1038
(lower_bound_revid is None or
1039
self.is_ancestor(lower_bound_revid, revid)))
1041
def _search_for_extra_common(self, common, searchers):
1042
"""Make sure that unique nodes are genuinely unique.
1044
After _find_border_ancestors, all nodes marked "common" are indeed
1045
common. Some of the nodes considered unique are not, due to history
1046
shortcuts stopping the searches early.
1048
We know that we have searched enough when all common search tips are
1049
descended from all unique (uncommon) nodes because we know that a node
1050
cannot be an ancestor of its own ancestor.
1052
:param common: A set of common nodes
1053
:param searchers: The searchers returned from _find_border_ancestors
1056
# Basic algorithm...
1057
# A) The passed in searchers should all be on the same tips, thus
1058
# they should be considered the "common" searchers.
1059
# B) We find the difference between the searchers, these are the
1060
# "unique" nodes for each side.
1061
# C) We do a quick culling so that we only start searching from the
1062
# more interesting unique nodes. (A unique ancestor is more
1063
# interesting than any of its children.)
1064
# D) We start searching for ancestors common to all unique nodes.
1065
# E) We have the common searchers stop searching any ancestors of
1066
# nodes found by (D)
1067
# F) When there are no more common search tips, we stop
1069
# TODO: We need a way to remove unique_searchers when they overlap with
1070
# other unique searchers.
1071
if len(searchers) != 2:
1072
raise NotImplementedError(
1073
"Algorithm not yet implemented for > 2 searchers")
1074
common_searchers = searchers
1075
left_searcher = searchers[0]
1076
right_searcher = searchers[1]
1077
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1078
if not unique: # No unique nodes, nothing to do
1080
total_unique = len(unique)
1081
unique = self._remove_simple_descendants(unique,
1082
self.get_parent_map(unique))
1083
simple_unique = len(unique)
1085
unique_searchers = []
1086
for revision_id in unique:
1087
if revision_id in left_searcher.seen:
1088
parent_searcher = left_searcher
1090
parent_searcher = right_searcher
1091
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1092
if not revs_to_search: # XXX: This shouldn't be possible
1093
revs_to_search = [revision_id]
1094
searcher = self._make_breadth_first_searcher(revs_to_search)
1095
# We don't care about the starting nodes.
1097
unique_searchers.append(searcher)
1099
# possible todo: aggregate the common searchers into a single common
1100
# searcher, just make sure that we include the nodes into the .seen
1101
# properties of the original searchers
1103
ancestor_all_unique = None
1104
for searcher in unique_searchers:
1105
if ancestor_all_unique is None:
1106
ancestor_all_unique = set(searcher.seen)
1108
ancestor_all_unique = ancestor_all_unique.intersection(
1111
trace.mutter('Started %s unique searchers for %s unique revisions',
1112
simple_unique, total_unique)
1114
while True: # If we have no more nodes we have nothing to do
1115
newly_seen_common = set()
1116
for searcher in common_searchers:
1117
newly_seen_common.update(searcher.step())
1118
newly_seen_unique = set()
1119
for searcher in unique_searchers:
1120
newly_seen_unique.update(searcher.step())
1121
new_common_unique = set()
1122
for revision in newly_seen_unique:
1123
for searcher in unique_searchers:
1124
if revision not in searcher.seen:
1127
# This is a border because it is a first common that we see
1128
# after walking for a while.
1129
new_common_unique.add(revision)
1130
if newly_seen_common:
1131
# These are nodes descended from one of the 'common' searchers.
1132
# Make sure all searchers are on the same page
1133
for searcher in common_searchers:
1134
newly_seen_common.update(
1135
searcher.find_seen_ancestors(newly_seen_common))
1136
# We start searching the whole ancestry. It is a bit wasteful,
1137
# though. We really just want to mark all of these nodes as
1138
# 'seen' and then start just the tips. However, it requires a
1139
# get_parent_map() call to figure out the tips anyway, and all
1140
# redundant requests should be fairly fast.
1141
for searcher in common_searchers:
1142
searcher.start_searching(newly_seen_common)
1144
# If a 'common' node is an ancestor of all unique searchers, we
1145
# can stop searching it.
1146
stop_searching_common = ancestor_all_unique.intersection(
1148
if stop_searching_common:
1149
for searcher in common_searchers:
1150
searcher.stop_searching_any(stop_searching_common)
1151
if new_common_unique:
1152
# We found some ancestors that are common
1153
for searcher in unique_searchers:
1154
new_common_unique.update(
1155
searcher.find_seen_ancestors(new_common_unique))
1156
# Since these are common, we can grab another set of ancestors
1158
for searcher in common_searchers:
1159
new_common_unique.update(
1160
searcher.find_seen_ancestors(new_common_unique))
1162
# We can tell all of the unique searchers to start at these
1163
# nodes, and tell all of the common searchers to *stop*
1164
# searching these nodes
1165
for searcher in unique_searchers:
1166
searcher.start_searching(new_common_unique)
1167
for searcher in common_searchers:
1168
searcher.stop_searching_any(new_common_unique)
1169
ancestor_all_unique.update(new_common_unique)
1171
# Filter out searchers that don't actually search different
1172
# nodes. We already have the ancestry intersection for them
1173
next_unique_searchers = []
1174
unique_search_sets = set()
1175
for searcher in unique_searchers:
1176
will_search_set = frozenset(searcher._next_query)
1177
if will_search_set not in unique_search_sets:
1178
# This searcher is searching a unique set of nodes, let it
1179
unique_search_sets.add(will_search_set)
1180
next_unique_searchers.append(searcher)
1181
unique_searchers = next_unique_searchers
1182
for searcher in common_searchers:
1183
if searcher._next_query:
1186
# All common searcher have stopped searching
1189
def _remove_simple_descendants(self, revisions, parent_map):
1190
"""remove revisions which are children of other ones in the set
1192
This doesn't do any graph searching, it just checks the immediate
1193
parent_map to find if there are any children which can be removed.
1195
:param revisions: A set of revision_ids
1196
:return: A set of revision_ids with the children removed
1198
simple_ancestors = revisions.copy()
1199
# TODO: jam 20071214 we *could* restrict it to searching only the
1200
# parent_map of revisions already present in 'revisions', but
1201
# considering the general use case, I think this is actually
1204
# This is the same as the following loop. I don't know that it is any
1206
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1207
## if p_ids is not None and revisions.intersection(p_ids))
1208
## return simple_ancestors
1210
# Yet Another Way, invert the parent map (which can be cached)
1212
## for revision_id, parent_ids in parent_map.iteritems():
1213
## for p_id in parent_ids:
1214
## descendants.setdefault(p_id, []).append(revision_id)
1215
## for revision in revisions.intersection(descendants):
1216
## simple_ancestors.difference_update(descendants[revision])
1217
## return simple_ancestors
1218
for revision, parent_ids in parent_map.iteritems():
1219
if parent_ids is None:
1221
for parent_id in parent_ids:
1222
if parent_id in revisions:
1223
# This node has a parent present in the set, so we can
1225
simple_ancestors.discard(revision)
1227
return simple_ancestors
1230
class HeadsCache(object):
1231
"""A cache of results for graph heads calls."""
1233
def __init__(self, graph):
1237
def heads(self, keys):
1238
"""Return the heads of keys.
1240
This matches the API of Graph.heads(), specifically the return value is
1241
a set which can be mutated, and ordering of the input is not preserved
1244
:see also: Graph.heads.
1245
:param keys: The keys to calculate heads for.
1246
:return: A set containing the heads, which may be mutated without
1247
affecting future lookups.
1249
keys = frozenset(keys)
1251
return set(self._heads[keys])
1253
heads = self.graph.heads(keys)
1254
self._heads[keys] = heads
1258
class FrozenHeadsCache(object):
1259
"""Cache heads() calls, assuming the caller won't modify them."""
1261
def __init__(self, graph):
1265
def heads(self, keys):
1266
"""Return the heads of keys.
1268
Similar to Graph.heads(). The main difference is that the return value
1269
is a frozen set which cannot be mutated.
1271
:see also: Graph.heads.
1272
:param keys: The keys to calculate heads for.
1273
:return: A frozenset containing the heads.
1275
keys = frozenset(keys)
1277
return self._heads[keys]
1279
heads = frozenset(self.graph.heads(keys))
1280
self._heads[keys] = heads
1283
def cache(self, keys, heads):
1284
"""Store a known value."""
1285
self._heads[frozenset(keys)] = frozenset(heads)
1288
class _BreadthFirstSearcher(object):
1289
"""Parallel search breadth-first the ancestry of revisions.
1291
This class implements the iterator protocol, but additionally
1292
1. provides a set of seen ancestors, and
1293
2. allows some ancestries to be unsearched, via stop_searching_any
1296
def __init__(self, revisions, parents_provider):
1297
self._iterations = 0
1298
self._next_query = set(revisions)
1300
self._started_keys = set(self._next_query)
1301
self._stopped_keys = set()
1302
self._parents_provider = parents_provider
1303
self._returning = 'next_with_ghosts'
1304
self._current_present = set()
1305
self._current_ghosts = set()
1306
self._current_parents = {}
1309
if self._iterations:
1310
prefix = "searching"
1313
search = '%s=%r' % (prefix, list(self._next_query))
1314
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1315
' seen=%r)' % (self._iterations, search, list(self.seen)))
1317
def get_result(self):
1318
"""Get a SearchResult for the current state of this searcher.
1320
:return: A SearchResult for this search so far. The SearchResult is
1321
static - the search can be advanced and the search result will not
1322
be invalidated or altered.
1324
if self._returning == 'next':
1325
# We have to know the current nodes children to be able to list the
1326
# exclude keys for them. However, while we could have a second
1327
# look-ahead result buffer and shuffle things around, this method
1328
# is typically only called once per search - when memoising the
1329
# results of the search.
1330
found, ghosts, next, parents = self._do_query(self._next_query)
1331
# pretend we didn't query: perhaps we should tweak _do_query to be
1332
# entirely stateless?
1333
self.seen.difference_update(next)
1334
next_query = next.union(ghosts)
1336
next_query = self._next_query
1337
excludes = self._stopped_keys.union(next_query)
1338
included_keys = self.seen.difference(excludes)
1339
return SearchResult(self._started_keys, excludes, len(included_keys),
1345
except StopIteration:
1349
"""Return the next ancestors of this revision.
1351
Ancestors are returned in the order they are seen in a breadth-first
1352
traversal. No ancestor will be returned more than once. Ancestors are
1353
returned before their parentage is queried, so ghosts and missing
1354
revisions (including the start revisions) are included in the result.
1355
This can save a round trip in LCA style calculation by allowing
1356
convergence to be detected without reading the data for the revision
1357
the convergence occurs on.
1359
:return: A set of revision_ids.
1361
if self._returning != 'next':
1362
# switch to returning the query, not the results.
1363
self._returning = 'next'
1364
self._iterations += 1
1367
if len(self._next_query) == 0:
1368
raise StopIteration()
1369
# We have seen what we're querying at this point as we are returning
1370
# the query, not the results.
1371
self.seen.update(self._next_query)
1372
return self._next_query
1374
def next_with_ghosts(self):
1375
"""Return the next found ancestors, with ghosts split out.
1377
Ancestors are returned in the order they are seen in a breadth-first
1378
traversal. No ancestor will be returned more than once. Ancestors are
1379
returned only after asking for their parents, which allows us to detect
1380
which revisions are ghosts and which are not.
1382
:return: A tuple with (present ancestors, ghost ancestors) sets.
1384
if self._returning != 'next_with_ghosts':
1385
# switch to returning the results, not the current query.
1386
self._returning = 'next_with_ghosts'
1388
if len(self._next_query) == 0:
1389
raise StopIteration()
1391
return self._current_present, self._current_ghosts
1394
"""Advance the search.
1396
Updates self.seen, self._next_query, self._current_present,
1397
self._current_ghosts, self._current_parents and self._iterations.
1399
self._iterations += 1
1400
found, ghosts, next, parents = self._do_query(self._next_query)
1401
self._current_present = found
1402
self._current_ghosts = ghosts
1403
self._next_query = next
1404
self._current_parents = parents
1405
# ghosts are implicit stop points, otherwise the search cannot be
1406
# repeated when ghosts are filled.
1407
self._stopped_keys.update(ghosts)
1409
def _do_query(self, revisions):
1410
"""Query for revisions.
1412
Adds revisions to the seen set.
1414
:param revisions: Revisions to query.
1415
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1416
set(parents_of_found_revisions), dict(found_revisions:parents)).
1418
found_revisions = set()
1419
parents_of_found = set()
1420
# revisions may contain nodes that point to other nodes in revisions:
1421
# we want to filter them out.
1422
self.seen.update(revisions)
1423
parent_map = self._parents_provider.get_parent_map(revisions)
1424
found_revisions.update(parent_map)
1425
for rev_id, parents in parent_map.iteritems():
1428
new_found_parents = [p for p in parents if p not in self.seen]
1429
if new_found_parents:
1430
# Calling set.update() with an empty generator is actually
1432
parents_of_found.update(new_found_parents)
1433
ghost_revisions = revisions - found_revisions
1434
return found_revisions, ghost_revisions, parents_of_found, parent_map
1439
def find_seen_ancestors(self, revisions):
1440
"""Find ancestors of these revisions that have already been seen.
1442
This function generally makes the assumption that querying for the
1443
parents of a node that has already been queried is reasonably cheap.
1444
(eg, not a round trip to a remote host).
1446
# TODO: Often we might ask one searcher for its seen ancestors, and
1447
# then ask another searcher the same question. This can result in
1448
# searching the same revisions repeatedly if the two searchers
1449
# have a lot of overlap.
1450
all_seen = self.seen
1451
pending = set(revisions).intersection(all_seen)
1452
seen_ancestors = set(pending)
1454
if self._returning == 'next':
1455
# self.seen contains what nodes have been returned, not what nodes
1456
# have been queried. We don't want to probe for nodes that haven't
1457
# been searched yet.
1458
not_searched_yet = self._next_query
1460
not_searched_yet = ()
1461
pending.difference_update(not_searched_yet)
1462
get_parent_map = self._parents_provider.get_parent_map
1464
parent_map = get_parent_map(pending)
1466
# We don't care if it is a ghost, since it can't be seen if it is
1468
for parent_ids in parent_map.itervalues():
1469
all_parents.extend(parent_ids)
1470
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1471
seen_ancestors.update(next_pending)
1472
next_pending.difference_update(not_searched_yet)
1473
pending = next_pending
1475
return seen_ancestors
1477
def stop_searching_any(self, revisions):
1479
Remove any of the specified revisions from the search list.
1481
None of the specified revisions are required to be present in the
1484
It is okay to call stop_searching_any() for revisions which were seen
1485
in previous iterations. It is the callers responsibility to call
1486
find_seen_ancestors() to make sure that current search tips that are
1487
ancestors of those revisions are also stopped. All explicitly stopped
1488
revisions will be excluded from the search result's get_keys(), though.
1490
# TODO: does this help performance?
1493
revisions = frozenset(revisions)
1494
if self._returning == 'next':
1495
stopped = self._next_query.intersection(revisions)
1496
self._next_query = self._next_query.difference(revisions)
1498
stopped_present = self._current_present.intersection(revisions)
1499
stopped = stopped_present.union(
1500
self._current_ghosts.intersection(revisions))
1501
self._current_present.difference_update(stopped)
1502
self._current_ghosts.difference_update(stopped)
1503
# stopping 'x' should stop returning parents of 'x', but
1504
# not if 'y' always references those same parents
1505
stop_rev_references = {}
1506
for rev in stopped_present:
1507
for parent_id in self._current_parents[rev]:
1508
if parent_id not in stop_rev_references:
1509
stop_rev_references[parent_id] = 0
1510
stop_rev_references[parent_id] += 1
1511
# if only the stopped revisions reference it, the ref count will be
1513
for parents in self._current_parents.itervalues():
1514
for parent_id in parents:
1516
stop_rev_references[parent_id] -= 1
1519
stop_parents = set()
1520
for rev_id, refs in stop_rev_references.iteritems():
1522
stop_parents.add(rev_id)
1523
self._next_query.difference_update(stop_parents)
1524
self._stopped_keys.update(stopped)
1525
self._stopped_keys.update(revisions)
1528
def start_searching(self, revisions):
1529
"""Add revisions to the search.
1531
The parents of revisions will be returned from the next call to next()
1532
or next_with_ghosts(). If next_with_ghosts was the most recently used
1533
next* call then the return value is the result of looking up the
1534
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1536
revisions = frozenset(revisions)
1537
self._started_keys.update(revisions)
1538
new_revisions = revisions.difference(self.seen)
1539
if self._returning == 'next':
1540
self._next_query.update(new_revisions)
1541
self.seen.update(new_revisions)
1543
# perform a query on revisions
1544
revs, ghosts, query, parents = self._do_query(revisions)
1545
self._stopped_keys.update(ghosts)
1546
self._current_present.update(revs)
1547
self._current_ghosts.update(ghosts)
1548
self._next_query.update(query)
1549
self._current_parents.update(parents)
1553
class AbstractSearchResult(object):
1554
"""The result of a search, describing a set of keys.
1556
Search results are typically used as the 'fetch_spec' parameter when
1559
:seealso: AbstractSearch
1562
def get_recipe(self):
1563
"""Return a recipe that can be used to replay this search.
1565
The recipe allows reconstruction of the same results at a later date.
1567
:return: A tuple of `(search_kind_str, *details)`. The details vary by
1568
kind of search result.
1570
raise NotImplementedError(self.get_recipe)
1572
def get_network_struct(self):
1573
"""Return a tuple that can be transmitted via the HPSS protocol."""
1574
raise NotImplementedError(self.get_network_struct)
1577
"""Return the keys found in this search.
1579
:return: A set of keys.
1581
raise NotImplementedError(self.get_keys)
1584
"""Return false if the search lists 1 or more revisions."""
1585
raise NotImplementedError(self.is_empty)
1587
def refine(self, seen, referenced):
1588
"""Create a new search by refining this search.
1590
:param seen: Revisions that have been satisfied.
1591
:param referenced: Revision references observed while satisfying some
1593
:return: A search result.
1595
raise NotImplementedError(self.refine)
1598
class AbstractSearch(object):
1599
"""A search that can be executed, producing a search result.
1601
:seealso: AbstractSearchResult
1605
"""Construct a network-ready search result from this search description.
1607
This may take some time to search repositories, etc.
1609
:return: A search result (an object that implements
1610
AbstractSearchResult's API).
1612
raise NotImplementedError(self.execute)
1615
class SearchResult(AbstractSearchResult):
1616
"""The result of a breadth first search.
1618
A SearchResult provides the ability to reconstruct the search or access a
1619
set of the keys the search found.
1622
def __init__(self, start_keys, exclude_keys, key_count, keys):
1623
"""Create a SearchResult.
1625
:param start_keys: The keys the search started at.
1626
:param exclude_keys: The keys the search excludes.
1627
:param key_count: The total number of keys (from start to but not
1629
:param keys: The keys the search found. Note that in future we may get
1630
a SearchResult from a smart server, in which case the keys list is
1631
not necessarily immediately available.
1633
self._recipe = ('search', start_keys, exclude_keys, key_count)
1634
self._keys = frozenset(keys)
1637
kind, start_keys, exclude_keys, key_count = self._recipe
1638
if len(start_keys) > 5:
1639
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1641
start_keys_repr = repr(start_keys)
1642
if len(exclude_keys) > 5:
1643
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1645
exclude_keys_repr = repr(exclude_keys)
1646
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1647
kind, start_keys_repr, exclude_keys_repr, key_count)
1649
def get_recipe(self):
1650
"""Return a recipe that can be used to replay this search.
1652
The recipe allows reconstruction of the same results at a later date
1653
without knowing all the found keys. The essential elements are a list
1654
of keys to start and to stop at. In order to give reproducible
1655
results when ghosts are encountered by a search they are automatically
1656
added to the exclude list (or else ghost filling may alter the
1659
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1660
revision_count). To recreate the results of this search, create a
1661
breadth first searcher on the same graph starting at start_keys.
1662
Then call next() (or next_with_ghosts()) repeatedly, and on every
1663
result, call stop_searching_any on any keys from the exclude_keys
1664
set. The revision_count value acts as a trivial cross-check - the
1665
found revisions of the new search should have as many elements as
1666
revision_count. If it does not, then additional revisions have been
1667
ghosted since the search was executed the first time and the second
1672
def get_network_struct(self):
1673
start_keys = ' '.join(self._recipe[1])
1674
stop_keys = ' '.join(self._recipe[2])
1675
count = str(self._recipe[3])
1676
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1679
"""Return the keys found in this search.
1681
:return: A set of keys.
1686
"""Return false if the search lists 1 or more revisions."""
1687
return self._recipe[3] == 0
1689
def refine(self, seen, referenced):
1690
"""Create a new search by refining this search.
1692
:param seen: Revisions that have been satisfied.
1693
:param referenced: Revision references observed while satisfying some
1696
start = self._recipe[1]
1697
exclude = self._recipe[2]
1698
count = self._recipe[3]
1699
keys = self.get_keys()
1700
# New heads = referenced + old heads - seen things - exclude
1701
pending_refs = set(referenced)
1702
pending_refs.update(start)
1703
pending_refs.difference_update(seen)
1704
pending_refs.difference_update(exclude)
1705
# New exclude = old exclude + satisfied heads
1706
seen_heads = start.intersection(seen)
1707
exclude.update(seen_heads)
1708
# keys gets seen removed
1710
# length is reduced by len(seen)
1712
return SearchResult(pending_refs, exclude, count, keys)
1715
class PendingAncestryResult(AbstractSearchResult):
1716
"""A search result that will reconstruct the ancestry for some graph heads.
1718
Unlike SearchResult, this doesn't hold the complete search result in
1719
memory, it just holds a description of how to generate it.
1722
def __init__(self, heads, repo):
1725
:param heads: an iterable of graph heads.
1726
:param repo: a repository to use to generate the ancestry for the given
1729
self.heads = frozenset(heads)
1733
if len(self.heads) > 5:
1734
heads_repr = repr(list(self.heads)[:5])[:-1]
1735
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1737
heads_repr = repr(self.heads)
1738
return '<%s heads:%s repo:%r>' % (
1739
self.__class__.__name__, heads_repr, self.repo)
1741
def get_recipe(self):
1742
"""Return a recipe that can be used to replay this search.
1744
The recipe allows reconstruction of the same results at a later date.
1746
:seealso SearchResult.get_recipe:
1748
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1749
To recreate this result, create a PendingAncestryResult with the
1752
return ('proxy-search', self.heads, set(), -1)
1754
def get_network_struct(self):
1755
parts = ['ancestry-of']
1756
parts.extend(self.heads)
1760
"""See SearchResult.get_keys.
1762
Returns all the keys for the ancestry of the heads, excluding
1765
return self._get_keys(self.repo.get_graph())
1767
def _get_keys(self, graph):
1768
NULL_REVISION = revision.NULL_REVISION
1769
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1770
if key != NULL_REVISION and parents is not None]
1774
"""Return false if the search lists 1 or more revisions."""
1775
if revision.NULL_REVISION in self.heads:
1776
return len(self.heads) == 1
1778
return len(self.heads) == 0
1780
def refine(self, seen, referenced):
1781
"""Create a new search by refining this search.
1783
:param seen: Revisions that have been satisfied.
1784
:param referenced: Revision references observed while satisfying some
1787
referenced = self.heads.union(referenced)
1788
return PendingAncestryResult(referenced - seen, self.repo)
1791
class EmptySearchResult(AbstractSearchResult):
1792
"""An empty search result."""
1798
class EverythingResult(AbstractSearchResult):
1799
"""A search result that simply requests everything in the repository."""
1801
def __init__(self, repo):
1805
return '%s(%r)' % (self.__class__.__name__, self._repo)
1807
def get_recipe(self):
1808
raise NotImplementedError(self.get_recipe)
1810
def get_network_struct(self):
1811
return ('everything',)
1814
if 'evil' in debug.debug_flags:
1815
from bzrlib import remote
1816
if isinstance(self._repo, remote.RemoteRepository):
1817
# warn developers (not users) not to do this
1818
trace.mutter_callsite(
1819
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1820
return self._repo.all_revision_ids()
1823
# It's ok for this to wrongly return False: the worst that can happen
1824
# is that RemoteStreamSource will initiate a get_stream on an empty
1825
# repository. And almost all repositories are non-empty.
1828
def refine(self, seen, referenced):
1829
heads = set(self._repo.all_revision_ids())
1830
heads.difference_update(seen)
1831
heads.update(referenced)
1832
return PendingAncestryResult(heads, self._repo)
1835
class EverythingNotInOther(AbstractSearch):
1836
"""Find all revisions in that are in one repo but not the other."""
1838
def __init__(self, to_repo, from_repo, find_ghosts=False):
1839
self.to_repo = to_repo
1840
self.from_repo = from_repo
1841
self.find_ghosts = find_ghosts
1844
return self.to_repo.search_missing_revision_ids(
1845
self.from_repo, find_ghosts=self.find_ghosts)
1848
class NotInOtherForRevs(AbstractSearch):
1849
"""Find all revisions missing in one repo for a some specific heads."""
1851
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1852
find_ghosts=False, limit=None):
1855
:param required_ids: revision IDs of heads that must be found, or else
1856
the search will fail with NoSuchRevision. All revisions in their
1857
ancestry not already in the other repository will be included in
1859
:param if_present_ids: revision IDs of heads that may be absent in the
1860
source repository. If present, then their ancestry not already
1861
found in other will be included in the search result.
1862
:param limit: maximum number of revisions to fetch
1864
self.to_repo = to_repo
1865
self.from_repo = from_repo
1866
self.find_ghosts = find_ghosts
1867
self.required_ids = required_ids
1868
self.if_present_ids = if_present_ids
1872
if len(self.required_ids) > 5:
1873
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1875
reqd_revs_repr = repr(self.required_ids)
1876
if self.if_present_ids and len(self.if_present_ids) > 5:
1877
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1879
ifp_revs_repr = repr(self.if_present_ids)
1881
return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
1883
self.__class__.__name__, self.from_repo, self.to_repo,
1884
self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
1888
return self.to_repo.search_missing_revision_ids(
1889
self.from_repo, revision_ids=self.required_ids,
1890
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
1894
def collapse_linear_regions(parent_map):
1895
"""Collapse regions of the graph that are 'linear'.
1901
can be collapsed by removing B and getting::
1905
:param parent_map: A dictionary mapping children to their parents
1906
:return: Another dictionary with 'linear' chains collapsed
1908
# Note: this isn't a strictly minimal collapse. For example:
1916
# Will not have 'D' removed, even though 'E' could fit. Also:
1922
# A and C are both kept because they are edges of the graph. We *could* get
1923
# rid of A if we wanted.
1931
# Will not have any nodes removed, even though you do have an
1932
# 'uninteresting' linear D->B and E->C
1934
for child, parents in parent_map.iteritems():
1935
children.setdefault(child, [])
1937
children.setdefault(p, []).append(child)
1939
orig_children = dict(children)
1941
result = dict(parent_map)
1942
for node in parent_map:
1943
parents = result[node]
1944
if len(parents) == 1:
1945
parent_children = children[parents[0]]
1946
if len(parent_children) != 1:
1947
# This is not the only child
1949
node_children = children[node]
1950
if len(node_children) != 1:
1952
child_parents = result.get(node_children[0], None)
1953
if len(child_parents) != 1:
1954
# This is not its only parent
1956
# The child of this node only points at it, and the parent only has
1957
# this as a child. remove this node, and join the others together
1958
result[node_children[0]] = parents
1959
children[parents[0]] = node_children
1967
class GraphThunkIdsToKeys(object):
1968
"""Forwards calls about 'ids' to be about keys internally."""
1970
def __init__(self, graph):
1973
def topo_sort(self):
1974
return [r for (r,) in self._graph.topo_sort()]
1976
def heads(self, ids):
1977
"""See Graph.heads()"""
1978
as_keys = [(i,) for i in ids]
1979
head_keys = self._graph.heads(as_keys)
1980
return set([h[0] for h in head_keys])
1982
def merge_sort(self, tip_revision):
1983
nodes = self._graph.merge_sort((tip_revision,))
1985
node.key = node.key[0]
1988
def add_node(self, revision, parents):
1989
self._graph.add_node((revision,), [(p,) for p in parents])
1992
_counters = [0,0,0,0,0,0,0]
1994
from bzrlib._known_graph_pyx import KnownGraph
1995
except ImportError, e:
1996
osutils.failed_to_load_extension(e)
1997
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
