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
254
1. The number of uncommon ancestors
255
2. The number of border ancestors
256
3. The length of the shortest path between a border ancestor and an
257
ancestor of all border ancestors.
259
border_common, common, sides = self._find_border_ancestors(revisions)
260
# We may have common ancestors that can be reached from each other.
261
# - ask for the heads of them to filter it down to only ones that
262
# cannot be reached from each other - phase 2.
263
return self.heads(border_common)
265
def find_difference(self, left_revision, right_revision):
266
"""Determine the graph difference between two revisions"""
267
border, common, searchers = self._find_border_ancestors(
268
[left_revision, right_revision])
269
self._search_for_extra_common(common, searchers)
270
left = searchers[0].seen
271
right = searchers[1].seen
272
return (left.difference(right), right.difference(left))
274
def find_descendants(self, old_key, new_key):
275
"""Find descendants of old_key that are ancestors of new_key."""
276
child_map = self.get_child_map(self._find_descendant_ancestors(
278
graph = Graph(DictParentsProvider(child_map))
279
searcher = graph._make_breadth_first_searcher([old_key])
283
def _find_descendant_ancestors(self, old_key, new_key):
284
"""Find ancestors of new_key that may be descendants of old_key."""
285
stop = self._make_breadth_first_searcher([old_key])
286
descendants = self._make_breadth_first_searcher([new_key])
287
for revisions in descendants:
288
old_stop = stop.seen.intersection(revisions)
289
descendants.stop_searching_any(old_stop)
290
seen_stop = descendants.find_seen_ancestors(stop.step())
291
descendants.stop_searching_any(seen_stop)
292
return descendants.seen.difference(stop.seen)
294
def get_child_map(self, keys):
295
"""Get a mapping from parents to children of the specified keys.
297
This is simply the inversion of get_parent_map. Only supplied keys
298
will be discovered as children.
299
:return: a dict of key:child_list for keys.
301
parent_map = self._parents_provider.get_parent_map(keys)
303
for child, parents in sorted(parent_map.items()):
304
for parent in parents:
305
parent_child.setdefault(parent, []).append(child)
308
def find_distance_to_null(self, target_revision_id, known_revision_ids):
309
"""Find the left-hand distance to the NULL_REVISION.
311
(This can also be considered the revno of a branch at
314
:param target_revision_id: A revision_id which we would like to know
316
:param known_revision_ids: [(revision_id, revno)] A list of known
317
revno, revision_id tuples. We'll use this to seed the search.
319
# Map from revision_ids to a known value for their revno
320
known_revnos = dict(known_revision_ids)
321
cur_tip = target_revision_id
323
NULL_REVISION = revision.NULL_REVISION
324
known_revnos[NULL_REVISION] = 0
326
searching_known_tips = list(known_revnos.keys())
328
unknown_searched = {}
330
while cur_tip not in known_revnos:
331
unknown_searched[cur_tip] = num_steps
333
to_search = set([cur_tip])
334
to_search.update(searching_known_tips)
335
parent_map = self.get_parent_map(to_search)
336
parents = parent_map.get(cur_tip, None)
337
if not parents: # An empty list or None is a ghost
338
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
342
for revision_id in searching_known_tips:
343
parents = parent_map.get(revision_id, None)
347
next_revno = known_revnos[revision_id] - 1
348
if next in unknown_searched:
349
# We have enough information to return a value right now
350
return next_revno + unknown_searched[next]
351
if next in known_revnos:
353
known_revnos[next] = next_revno
354
next_known_tips.append(next)
355
searching_known_tips = next_known_tips
357
# We reached a known revision, so just add in how many steps it took to
359
return known_revnos[cur_tip] + num_steps
361
def find_lefthand_distances(self, keys):
362
"""Find the distance to null for all the keys in keys.
364
:param keys: keys to lookup.
365
:return: A dict key->distance for all of keys.
367
# Optimisable by concurrent searching, but a random spread should get
368
# some sort of hit rate.
375
(key, self.find_distance_to_null(key, known_revnos)))
376
except errors.GhostRevisionsHaveNoRevno:
379
known_revnos.append((key, -1))
380
return dict(known_revnos)
382
def find_unique_ancestors(self, unique_revision, common_revisions):
383
"""Find the unique ancestors for a revision versus others.
385
This returns the ancestry of unique_revision, excluding all revisions
386
in the ancestry of common_revisions. If unique_revision is in the
387
ancestry, then the empty set will be returned.
389
:param unique_revision: The revision_id whose ancestry we are
391
XXX: Would this API be better if we allowed multiple revisions on
393
:param common_revisions: Revision_ids of ancestries to exclude.
394
:return: A set of revisions in the ancestry of unique_revision
396
if unique_revision in common_revisions:
399
# Algorithm description
400
# 1) Walk backwards from the unique node and all common nodes.
401
# 2) When a node is seen by both sides, stop searching it in the unique
402
# walker, include it in the common walker.
403
# 3) Stop searching when there are no nodes left for the unique walker.
404
# At this point, you have a maximal set of unique nodes. Some of
405
# them may actually be common, and you haven't reached them yet.
406
# 4) Start new searchers for the unique nodes, seeded with the
407
# information you have so far.
408
# 5) Continue searching, stopping the common searches when the search
409
# tip is an ancestor of all unique nodes.
410
# 6) Aggregate together unique searchers when they are searching the
411
# same tips. When all unique searchers are searching the same node,
412
# stop move it to a single 'all_unique_searcher'.
413
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
414
# Most of the time this produces very little important information.
415
# So don't step it as quickly as the other searchers.
416
# 8) Search is done when all common searchers have completed.
418
unique_searcher, common_searcher = self._find_initial_unique_nodes(
419
[unique_revision], common_revisions)
421
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
425
(all_unique_searcher,
426
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
427
unique_searcher, common_searcher)
429
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
430
unique_tip_searchers, common_searcher)
431
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
432
if 'graph' in debug.debug_flags:
433
trace.mutter('Found %d truly unique nodes out of %d',
434
len(true_unique_nodes), len(unique_nodes))
435
return true_unique_nodes
437
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
438
"""Steps 1-3 of find_unique_ancestors.
440
Find the maximal set of unique nodes. Some of these might actually
441
still be common, but we are sure that there are no other unique nodes.
443
:return: (unique_searcher, common_searcher)
446
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
447
# we know that unique_revisions aren't in common_revisions, so skip
449
unique_searcher.next()
450
common_searcher = self._make_breadth_first_searcher(common_revisions)
452
# As long as we are still finding unique nodes, keep searching
453
while unique_searcher._next_query:
454
next_unique_nodes = set(unique_searcher.step())
455
next_common_nodes = set(common_searcher.step())
457
# Check if either searcher encounters new nodes seen by the other
459
unique_are_common_nodes = next_unique_nodes.intersection(
460
common_searcher.seen)
461
unique_are_common_nodes.update(
462
next_common_nodes.intersection(unique_searcher.seen))
463
if unique_are_common_nodes:
464
ancestors = unique_searcher.find_seen_ancestors(
465
unique_are_common_nodes)
466
# TODO: This is a bit overboard, we only really care about
467
# the ancestors of the tips because the rest we
468
# already know. This is *correct* but causes us to
469
# search too much ancestry.
470
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
471
unique_searcher.stop_searching_any(ancestors)
472
common_searcher.start_searching(ancestors)
474
return unique_searcher, common_searcher
476
def _make_unique_searchers(self, unique_nodes, unique_searcher,
478
"""Create a searcher for all the unique search tips (step 4).
480
As a side effect, the common_searcher will stop searching any nodes
481
that are ancestors of the unique searcher tips.
483
:return: (all_unique_searcher, unique_tip_searchers)
485
unique_tips = self._remove_simple_descendants(unique_nodes,
486
self.get_parent_map(unique_nodes))
488
if len(unique_tips) == 1:
489
unique_tip_searchers = []
490
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
492
unique_tip_searchers = []
493
for tip in unique_tips:
494
revs_to_search = unique_searcher.find_seen_ancestors([tip])
495
revs_to_search.update(
496
common_searcher.find_seen_ancestors(revs_to_search))
497
searcher = self._make_breadth_first_searcher(revs_to_search)
498
# We don't care about the starting nodes.
499
searcher._label = tip
501
unique_tip_searchers.append(searcher)
503
ancestor_all_unique = None
504
for searcher in unique_tip_searchers:
505
if ancestor_all_unique is None:
506
ancestor_all_unique = set(searcher.seen)
508
ancestor_all_unique = ancestor_all_unique.intersection(
510
# Collapse all the common nodes into a single searcher
511
all_unique_searcher = self._make_breadth_first_searcher(
513
if ancestor_all_unique:
514
# We've seen these nodes in all the searchers, so we'll just go to
516
all_unique_searcher.step()
518
# Stop any search tips that are already known as ancestors of the
520
stopped_common = common_searcher.stop_searching_any(
521
common_searcher.find_seen_ancestors(ancestor_all_unique))
524
for searcher in unique_tip_searchers:
525
total_stopped += len(searcher.stop_searching_any(
526
searcher.find_seen_ancestors(ancestor_all_unique)))
527
if 'graph' in debug.debug_flags:
528
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
529
' (%d stopped search tips, %d common ancestors'
530
' (%d stopped common)',
531
len(unique_nodes), len(unique_tip_searchers),
532
total_stopped, len(ancestor_all_unique),
534
return all_unique_searcher, unique_tip_searchers
536
def _step_unique_and_common_searchers(self, common_searcher,
537
unique_tip_searchers,
539
"""Step all the searchers"""
540
newly_seen_common = set(common_searcher.step())
541
newly_seen_unique = set()
542
for searcher in unique_tip_searchers:
543
next = set(searcher.step())
544
next.update(unique_searcher.find_seen_ancestors(next))
545
next.update(common_searcher.find_seen_ancestors(next))
546
for alt_searcher in unique_tip_searchers:
547
if alt_searcher is searcher:
549
next.update(alt_searcher.find_seen_ancestors(next))
550
searcher.start_searching(next)
551
newly_seen_unique.update(next)
552
return newly_seen_common, newly_seen_unique
554
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
556
newly_seen_unique, step_all_unique):
557
"""Find nodes that are common to all unique_tip_searchers.
559
If it is time, step the all_unique_searcher, and add its nodes to the
562
common_to_all_unique_nodes = newly_seen_unique.copy()
563
for searcher in unique_tip_searchers:
564
common_to_all_unique_nodes.intersection_update(searcher.seen)
565
common_to_all_unique_nodes.intersection_update(
566
all_unique_searcher.seen)
567
# Step all-unique less frequently than the other searchers.
568
# In the common case, we don't need to spider out far here, so
569
# avoid doing extra work.
571
tstart = time.clock()
572
nodes = all_unique_searcher.step()
573
common_to_all_unique_nodes.update(nodes)
574
if 'graph' in debug.debug_flags:
575
tdelta = time.clock() - tstart
576
trace.mutter('all_unique_searcher step() took %.3fs'
577
'for %d nodes (%d total), iteration: %s',
578
tdelta, len(nodes), len(all_unique_searcher.seen),
579
all_unique_searcher._iterations)
580
return common_to_all_unique_nodes
582
def _collapse_unique_searchers(self, unique_tip_searchers,
583
common_to_all_unique_nodes):
584
"""Combine searchers that are searching the same tips.
586
When two searchers are searching the same tips, we can stop one of the
587
searchers. We also know that the maximal set of common ancestors is the
588
intersection of the two original searchers.
590
:return: A list of searchers that are searching unique nodes.
592
# Filter out searchers that don't actually search different
593
# nodes. We already have the ancestry intersection for them
594
unique_search_tips = {}
595
for searcher in unique_tip_searchers:
596
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
597
will_search_set = frozenset(searcher._next_query)
598
if not will_search_set:
599
if 'graph' in debug.debug_flags:
600
trace.mutter('Unique searcher %s was stopped.'
601
' (%s iterations) %d nodes stopped',
603
searcher._iterations,
605
elif will_search_set not in unique_search_tips:
606
# This searcher is searching a unique set of nodes, let it
607
unique_search_tips[will_search_set] = [searcher]
609
unique_search_tips[will_search_set].append(searcher)
610
# TODO: it might be possible to collapse searchers faster when they
611
# only have *some* search tips in common.
612
next_unique_searchers = []
613
for searchers in unique_search_tips.itervalues():
614
if len(searchers) == 1:
615
# Searching unique tips, go for it
616
next_unique_searchers.append(searchers[0])
618
# These searchers have started searching the same tips, we
619
# don't need them to cover the same ground. The
620
# intersection of their ancestry won't change, so create a
621
# new searcher, combining their histories.
622
next_searcher = searchers[0]
623
for searcher in searchers[1:]:
624
next_searcher.seen.intersection_update(searcher.seen)
625
if 'graph' in debug.debug_flags:
626
trace.mutter('Combining %d searchers into a single'
627
' searcher searching %d nodes with'
630
len(next_searcher._next_query),
631
len(next_searcher.seen))
632
next_unique_searchers.append(next_searcher)
633
return next_unique_searchers
635
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
636
unique_tip_searchers, common_searcher):
637
"""Steps 5-8 of find_unique_ancestors.
639
This function returns when common_searcher has stopped searching for
642
# We step the ancestor_all_unique searcher only every
643
# STEP_UNIQUE_SEARCHER_EVERY steps.
644
step_all_unique_counter = 0
645
# While we still have common nodes to search
646
while common_searcher._next_query:
648
newly_seen_unique) = self._step_unique_and_common_searchers(
649
common_searcher, unique_tip_searchers, unique_searcher)
650
# These nodes are common ancestors of all unique nodes
651
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
652
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
653
step_all_unique_counter==0)
654
step_all_unique_counter = ((step_all_unique_counter + 1)
655
% STEP_UNIQUE_SEARCHER_EVERY)
657
if newly_seen_common:
658
# If a 'common' node is an ancestor of all unique searchers, we
659
# can stop searching it.
660
common_searcher.stop_searching_any(
661
all_unique_searcher.seen.intersection(newly_seen_common))
662
if common_to_all_unique_nodes:
663
common_to_all_unique_nodes.update(
664
common_searcher.find_seen_ancestors(
665
common_to_all_unique_nodes))
666
# The all_unique searcher can start searching the common nodes
667
# but everyone else can stop.
668
# This is the sort of thing where we would like to not have it
669
# start_searching all of the nodes, but only mark all of them
670
# as seen, and have it search only the actual tips. Otherwise
671
# it is another get_parent_map() traversal for it to figure out
672
# what we already should know.
673
all_unique_searcher.start_searching(common_to_all_unique_nodes)
674
common_searcher.stop_searching_any(common_to_all_unique_nodes)
676
next_unique_searchers = self._collapse_unique_searchers(
677
unique_tip_searchers, common_to_all_unique_nodes)
678
if len(unique_tip_searchers) != len(next_unique_searchers):
679
if 'graph' in debug.debug_flags:
680
trace.mutter('Collapsed %d unique searchers => %d'
682
len(unique_tip_searchers),
683
len(next_unique_searchers),
684
all_unique_searcher._iterations)
685
unique_tip_searchers = next_unique_searchers
687
def get_parent_map(self, revisions):
688
"""Get a map of key:parent_list for revisions.
690
This implementation delegates to get_parents, for old parent_providers
691
that do not supply get_parent_map.
694
for rev, parents in self.get_parents(revisions):
695
if parents is not None:
696
result[rev] = parents
699
def _make_breadth_first_searcher(self, revisions):
700
return _BreadthFirstSearcher(revisions, self)
702
def _find_border_ancestors(self, revisions):
703
"""Find common ancestors with at least one uncommon descendant.
705
Border ancestors are identified using a breadth-first
706
search starting at the bottom of the graph. Searches are stopped
707
whenever a node or one of its descendants is determined to be common.
709
This will scale with the number of uncommon ancestors.
711
As well as the border ancestors, a set of seen common ancestors and a
712
list of sets of seen ancestors for each input revision is returned.
713
This allows calculation of graph difference from the results of this
716
if None in revisions:
717
raise errors.InvalidRevisionId(None, self)
718
common_ancestors = set()
719
searchers = [self._make_breadth_first_searcher([r])
721
active_searchers = searchers[:]
722
border_ancestors = set()
726
for searcher in searchers:
727
new_ancestors = searcher.step()
729
newly_seen.update(new_ancestors)
731
for revision in newly_seen:
732
if revision in common_ancestors:
733
# Not a border ancestor because it was seen as common
735
new_common.add(revision)
737
for searcher in searchers:
738
if revision not in searcher.seen:
741
# This is a border because it is a first common that we see
742
# after walking for a while.
743
border_ancestors.add(revision)
744
new_common.add(revision)
746
for searcher in searchers:
747
new_common.update(searcher.find_seen_ancestors(new_common))
748
for searcher in searchers:
749
searcher.start_searching(new_common)
750
common_ancestors.update(new_common)
752
# Figure out what the searchers will be searching next, and if
753
# there is only 1 set being searched, then we are done searching,
754
# since all searchers would have to be searching the same data,
755
# thus it *must* be in common.
756
unique_search_sets = set()
757
for searcher in searchers:
758
will_search_set = frozenset(searcher._next_query)
759
if will_search_set not in unique_search_sets:
760
# This searcher is searching a unique set of nodes, let it
761
unique_search_sets.add(will_search_set)
763
if len(unique_search_sets) == 1:
764
nodes = unique_search_sets.pop()
765
uncommon_nodes = nodes.difference(common_ancestors)
767
raise AssertionError("Somehow we ended up converging"
768
" without actually marking them as"
771
"\nuncommon_nodes: %s"
772
% (revisions, uncommon_nodes))
774
return border_ancestors, common_ancestors, searchers
776
def heads(self, keys):
777
"""Return the heads from amongst keys.
779
This is done by searching the ancestries of each key. Any key that is
780
reachable from another key is not returned; all the others are.
782
This operation scales with the relative depth between any two keys. If
783
any two keys are completely disconnected all ancestry of both sides
786
:param keys: An iterable of keys.
787
:return: A set of the heads. Note that as a set there is no ordering
788
information. Callers will need to filter their input to create
789
order if they need it.
791
candidate_heads = set(keys)
792
if revision.NULL_REVISION in candidate_heads:
793
# NULL_REVISION is only a head if it is the only entry
794
candidate_heads.remove(revision.NULL_REVISION)
795
if not candidate_heads:
796
return set([revision.NULL_REVISION])
797
if len(candidate_heads) < 2:
798
return candidate_heads
799
searchers = dict((c, self._make_breadth_first_searcher([c]))
800
for c in candidate_heads)
801
active_searchers = dict(searchers)
802
# skip over the actual candidate for each searcher
803
for searcher in active_searchers.itervalues():
805
# The common walker finds nodes that are common to two or more of the
806
# input keys, so that we don't access all history when a currently
807
# uncommon search point actually meets up with something behind a
808
# common search point. Common search points do not keep searches
809
# active; they just allow us to make searches inactive without
810
# accessing all history.
811
common_walker = self._make_breadth_first_searcher([])
812
while len(active_searchers) > 0:
817
except StopIteration:
818
# No common points being searched at this time.
820
for candidate in active_searchers.keys():
822
searcher = active_searchers[candidate]
824
# rare case: we deleted candidate in a previous iteration
825
# through this for loop, because it was determined to be
826
# a descendant of another candidate.
829
ancestors.update(searcher.next())
830
except StopIteration:
831
del active_searchers[candidate]
833
# process found nodes
835
for ancestor in ancestors:
836
if ancestor in candidate_heads:
837
candidate_heads.remove(ancestor)
838
del searchers[ancestor]
839
if ancestor in active_searchers:
840
del active_searchers[ancestor]
841
# it may meet up with a known common node
842
if ancestor in common_walker.seen:
843
# some searcher has encountered our known common nodes:
845
ancestor_set = set([ancestor])
846
for searcher in searchers.itervalues():
847
searcher.stop_searching_any(ancestor_set)
849
# or it may have been just reached by all the searchers:
850
for searcher in searchers.itervalues():
851
if ancestor not in searcher.seen:
854
# The final active searcher has just reached this node,
855
# making it be known as a descendant of all candidates,
856
# so we can stop searching it, and any seen ancestors
857
new_common.add(ancestor)
858
for searcher in searchers.itervalues():
860
searcher.find_seen_ancestors([ancestor])
861
searcher.stop_searching_any(seen_ancestors)
862
common_walker.start_searching(new_common)
863
return candidate_heads
865
def find_merge_order(self, tip_revision_id, lca_revision_ids):
866
"""Find the order that each revision was merged into tip.
868
This basically just walks backwards with a stack, and walks left-first
869
until it finds a node to stop.
871
if len(lca_revision_ids) == 1:
872
return list(lca_revision_ids)
873
looking_for = set(lca_revision_ids)
874
# TODO: Is there a way we could do this "faster" by batching up the
875
# get_parent_map requests?
876
# TODO: Should we also be culling the ancestry search right away? We
877
# could add looking_for to the "stop" list, and walk their
878
# ancestry in batched mode. The flip side is it might mean we walk a
879
# lot of "stop" nodes, rather than only the minimum.
880
# Then again, without it we may trace back into ancestry we could have
882
stack = [tip_revision_id]
885
while stack and looking_for:
888
if next in looking_for:
890
looking_for.remove(next)
891
if len(looking_for) == 1:
892
found.append(looking_for.pop())
895
parent_ids = self.get_parent_map([next]).get(next, None)
896
if not parent_ids: # Ghost, nothing to search here
898
for parent_id in reversed(parent_ids):
899
# TODO: (performance) We see the parent at this point, but we
900
# wait to mark it until later to make sure we get left
901
# parents before right parents. However, instead of
902
# waiting until we have traversed enough parents, we
903
# could instead note that we've found it, and once all
904
# parents are in the stack, just reverse iterate the
906
if parent_id not in stop:
907
# this will need to be searched
908
stack.append(parent_id)
912
def find_lefthand_merger(self, merged_key, tip_key):
913
"""Find the first lefthand ancestor of tip_key that merged merged_key.
915
We do this by first finding the descendants of merged_key, then
916
walking through the lefthand ancestry of tip_key until we find a key
917
that doesn't descend from merged_key. Its child is the key that
920
:return: The first lefthand ancestor of tip_key to merge merged_key.
921
merged_key if it is a lefthand ancestor of tip_key.
922
None if no ancestor of tip_key merged merged_key.
924
descendants = self.find_descendants(merged_key, tip_key)
925
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
926
last_candidate = None
927
for candidate in candidate_iterator:
928
if candidate not in descendants:
929
return last_candidate
930
last_candidate = candidate
932
def find_unique_lca(self, left_revision, right_revision,
934
"""Find a unique LCA.
936
Find lowest common ancestors. If there is no unique common
937
ancestor, find the lowest common ancestors of those ancestors.
939
Iteration stops when a unique lowest common ancestor is found.
940
The graph origin is necessarily a unique lowest common ancestor.
942
Note that None is not an acceptable substitute for NULL_REVISION.
943
in the input for this method.
945
:param count_steps: If True, the return value will be a tuple of
946
(unique_lca, steps) where steps is the number of times that
947
find_lca was run. If False, only unique_lca is returned.
949
revisions = [left_revision, right_revision]
953
lca = self.find_lca(*revisions)
961
raise errors.NoCommonAncestor(left_revision, right_revision)
964
def iter_ancestry(self, revision_ids):
965
"""Iterate the ancestry of this revision.
967
:param revision_ids: Nodes to start the search
968
:return: Yield tuples mapping a revision_id to its parents for the
969
ancestry of revision_id.
970
Ghosts will be returned with None as their parents, and nodes
971
with no parents will have NULL_REVISION as their only parent. (As
972
defined by get_parent_map.)
973
There will also be a node for (NULL_REVISION, ())
975
pending = set(revision_ids)
978
processed.update(pending)
979
next_map = self.get_parent_map(pending)
981
for item in next_map.iteritems():
983
next_pending.update(p for p in item[1] if p not in processed)
984
ghosts = pending.difference(next_map)
987
pending = next_pending
989
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
990
if stop_keys is None:
993
def get_parents(key):
995
return self._parents_provider.get_parent_map([key])[key]
997
raise errors.RevisionNotPresent(next_key, self)
999
if next_key in stop_keys:
1001
parents = get_parents(next_key)
1003
if len(parents) == 0:
1006
next_key = parents[0]
1008
def iter_topo_order(self, revisions):
1009
"""Iterate through the input revisions in topological order.
1011
This sorting only ensures that parents come before their children.
1012
An ancestor may sort after a descendant if the relationship is not
1013
visible in the supplied list of revisions.
1015
from bzrlib import tsort
1016
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1017
return sorter.iter_topo_order()
1019
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1020
"""Determine whether a revision is an ancestor of another.
1022
We answer this using heads() as heads() has the logic to perform the
1023
smallest number of parent lookups to determine the ancestral
1024
relationship between N revisions.
1026
return set([candidate_descendant]) == self.heads(
1027
[candidate_ancestor, candidate_descendant])
1029
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1030
"""Determine whether a revision is between two others.
1032
returns true if and only if:
1033
lower_bound_revid <= revid <= upper_bound_revid
1035
return ((upper_bound_revid is None or
1036
self.is_ancestor(revid, upper_bound_revid)) and
1037
(lower_bound_revid is None or
1038
self.is_ancestor(lower_bound_revid, revid)))
1040
def _search_for_extra_common(self, common, searchers):
1041
"""Make sure that unique nodes are genuinely unique.
1043
After _find_border_ancestors, all nodes marked "common" are indeed
1044
common. Some of the nodes considered unique are not, due to history
1045
shortcuts stopping the searches early.
1047
We know that we have searched enough when all common search tips are
1048
descended from all unique (uncommon) nodes because we know that a node
1049
cannot be an ancestor of its own ancestor.
1051
:param common: A set of common nodes
1052
:param searchers: The searchers returned from _find_border_ancestors
1055
# Basic algorithm...
1056
# A) The passed in searchers should all be on the same tips, thus
1057
# they should be considered the "common" searchers.
1058
# B) We find the difference between the searchers, these are the
1059
# "unique" nodes for each side.
1060
# C) We do a quick culling so that we only start searching from the
1061
# more interesting unique nodes. (A unique ancestor is more
1062
# interesting than any of its children.)
1063
# D) We start searching for ancestors common to all unique nodes.
1064
# E) We have the common searchers stop searching any ancestors of
1065
# nodes found by (D)
1066
# F) When there are no more common search tips, we stop
1068
# TODO: We need a way to remove unique_searchers when they overlap with
1069
# other unique searchers.
1070
if len(searchers) != 2:
1071
raise NotImplementedError(
1072
"Algorithm not yet implemented for > 2 searchers")
1073
common_searchers = searchers
1074
left_searcher = searchers[0]
1075
right_searcher = searchers[1]
1076
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1077
if not unique: # No unique nodes, nothing to do
1079
total_unique = len(unique)
1080
unique = self._remove_simple_descendants(unique,
1081
self.get_parent_map(unique))
1082
simple_unique = len(unique)
1084
unique_searchers = []
1085
for revision_id in unique:
1086
if revision_id in left_searcher.seen:
1087
parent_searcher = left_searcher
1089
parent_searcher = right_searcher
1090
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1091
if not revs_to_search: # XXX: This shouldn't be possible
1092
revs_to_search = [revision_id]
1093
searcher = self._make_breadth_first_searcher(revs_to_search)
1094
# We don't care about the starting nodes.
1096
unique_searchers.append(searcher)
1098
# possible todo: aggregate the common searchers into a single common
1099
# searcher, just make sure that we include the nodes into the .seen
1100
# properties of the original searchers
1102
ancestor_all_unique = None
1103
for searcher in unique_searchers:
1104
if ancestor_all_unique is None:
1105
ancestor_all_unique = set(searcher.seen)
1107
ancestor_all_unique = ancestor_all_unique.intersection(
1110
trace.mutter('Started %s unique searchers for %s unique revisions',
1111
simple_unique, total_unique)
1113
while True: # If we have no more nodes we have nothing to do
1114
newly_seen_common = set()
1115
for searcher in common_searchers:
1116
newly_seen_common.update(searcher.step())
1117
newly_seen_unique = set()
1118
for searcher in unique_searchers:
1119
newly_seen_unique.update(searcher.step())
1120
new_common_unique = set()
1121
for revision in newly_seen_unique:
1122
for searcher in unique_searchers:
1123
if revision not in searcher.seen:
1126
# This is a border because it is a first common that we see
1127
# after walking for a while.
1128
new_common_unique.add(revision)
1129
if newly_seen_common:
1130
# These are nodes descended from one of the 'common' searchers.
1131
# Make sure all searchers are on the same page
1132
for searcher in common_searchers:
1133
newly_seen_common.update(
1134
searcher.find_seen_ancestors(newly_seen_common))
1135
# We start searching the whole ancestry. It is a bit wasteful,
1136
# though. We really just want to mark all of these nodes as
1137
# 'seen' and then start just the tips. However, it requires a
1138
# get_parent_map() call to figure out the tips anyway, and all
1139
# redundant requests should be fairly fast.
1140
for searcher in common_searchers:
1141
searcher.start_searching(newly_seen_common)
1143
# If a 'common' node is an ancestor of all unique searchers, we
1144
# can stop searching it.
1145
stop_searching_common = ancestor_all_unique.intersection(
1147
if stop_searching_common:
1148
for searcher in common_searchers:
1149
searcher.stop_searching_any(stop_searching_common)
1150
if new_common_unique:
1151
# We found some ancestors that are common
1152
for searcher in unique_searchers:
1153
new_common_unique.update(
1154
searcher.find_seen_ancestors(new_common_unique))
1155
# Since these are common, we can grab another set of ancestors
1157
for searcher in common_searchers:
1158
new_common_unique.update(
1159
searcher.find_seen_ancestors(new_common_unique))
1161
# We can tell all of the unique searchers to start at these
1162
# nodes, and tell all of the common searchers to *stop*
1163
# searching these nodes
1164
for searcher in unique_searchers:
1165
searcher.start_searching(new_common_unique)
1166
for searcher in common_searchers:
1167
searcher.stop_searching_any(new_common_unique)
1168
ancestor_all_unique.update(new_common_unique)
1170
# Filter out searchers that don't actually search different
1171
# nodes. We already have the ancestry intersection for them
1172
next_unique_searchers = []
1173
unique_search_sets = set()
1174
for searcher in unique_searchers:
1175
will_search_set = frozenset(searcher._next_query)
1176
if will_search_set not in unique_search_sets:
1177
# This searcher is searching a unique set of nodes, let it
1178
unique_search_sets.add(will_search_set)
1179
next_unique_searchers.append(searcher)
1180
unique_searchers = next_unique_searchers
1181
for searcher in common_searchers:
1182
if searcher._next_query:
1185
# All common searcher have stopped searching
1188
def _remove_simple_descendants(self, revisions, parent_map):
1189
"""remove revisions which are children of other ones in the set
1191
This doesn't do any graph searching, it just checks the immediate
1192
parent_map to find if there are any children which can be removed.
1194
:param revisions: A set of revision_ids
1195
:return: A set of revision_ids with the children removed
1197
simple_ancestors = revisions.copy()
1198
# TODO: jam 20071214 we *could* restrict it to searching only the
1199
# parent_map of revisions already present in 'revisions', but
1200
# considering the general use case, I think this is actually
1203
# This is the same as the following loop. I don't know that it is any
1205
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1206
## if p_ids is not None and revisions.intersection(p_ids))
1207
## return simple_ancestors
1209
# Yet Another Way, invert the parent map (which can be cached)
1211
## for revision_id, parent_ids in parent_map.iteritems():
1212
## for p_id in parent_ids:
1213
## descendants.setdefault(p_id, []).append(revision_id)
1214
## for revision in revisions.intersection(descendants):
1215
## simple_ancestors.difference_update(descendants[revision])
1216
## return simple_ancestors
1217
for revision, parent_ids in parent_map.iteritems():
1218
if parent_ids is None:
1220
for parent_id in parent_ids:
1221
if parent_id in revisions:
1222
# This node has a parent present in the set, so we can
1224
simple_ancestors.discard(revision)
1226
return simple_ancestors
1229
class HeadsCache(object):
1230
"""A cache of results for graph heads calls."""
1232
def __init__(self, graph):
1236
def heads(self, keys):
1237
"""Return the heads of keys.
1239
This matches the API of Graph.heads(), specifically the return value is
1240
a set which can be mutated, and ordering of the input is not preserved
1243
:see also: Graph.heads.
1244
:param keys: The keys to calculate heads for.
1245
:return: A set containing the heads, which may be mutated without
1246
affecting future lookups.
1248
keys = frozenset(keys)
1250
return set(self._heads[keys])
1252
heads = self.graph.heads(keys)
1253
self._heads[keys] = heads
1257
class FrozenHeadsCache(object):
1258
"""Cache heads() calls, assuming the caller won't modify them."""
1260
def __init__(self, graph):
1264
def heads(self, keys):
1265
"""Return the heads of keys.
1267
Similar to Graph.heads(). The main difference is that the return value
1268
is a frozen set which cannot be mutated.
1270
:see also: Graph.heads.
1271
:param keys: The keys to calculate heads for.
1272
:return: A frozenset containing the heads.
1274
keys = frozenset(keys)
1276
return self._heads[keys]
1278
heads = frozenset(self.graph.heads(keys))
1279
self._heads[keys] = heads
1282
def cache(self, keys, heads):
1283
"""Store a known value."""
1284
self._heads[frozenset(keys)] = frozenset(heads)
1287
class _BreadthFirstSearcher(object):
1288
"""Parallel search breadth-first the ancestry of revisions.
1290
This class implements the iterator protocol, but additionally
1291
1. provides a set of seen ancestors, and
1292
2. allows some ancestries to be unsearched, via stop_searching_any
1295
def __init__(self, revisions, parents_provider):
1296
self._iterations = 0
1297
self._next_query = set(revisions)
1299
self._started_keys = set(self._next_query)
1300
self._stopped_keys = set()
1301
self._parents_provider = parents_provider
1302
self._returning = 'next_with_ghosts'
1303
self._current_present = set()
1304
self._current_ghosts = set()
1305
self._current_parents = {}
1308
if self._iterations:
1309
prefix = "searching"
1312
search = '%s=%r' % (prefix, list(self._next_query))
1313
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1314
' seen=%r)' % (self._iterations, search, list(self.seen)))
1316
def get_result(self):
1317
"""Get a SearchResult for the current state of this searcher.
1319
:return: A SearchResult for this search so far. The SearchResult is
1320
static - the search can be advanced and the search result will not
1321
be invalidated or altered.
1323
if self._returning == 'next':
1324
# We have to know the current nodes children to be able to list the
1325
# exclude keys for them. However, while we could have a second
1326
# look-ahead result buffer and shuffle things around, this method
1327
# is typically only called once per search - when memoising the
1328
# results of the search.
1329
found, ghosts, next, parents = self._do_query(self._next_query)
1330
# pretend we didn't query: perhaps we should tweak _do_query to be
1331
# entirely stateless?
1332
self.seen.difference_update(next)
1333
next_query = next.union(ghosts)
1335
next_query = self._next_query
1336
excludes = self._stopped_keys.union(next_query)
1337
included_keys = self.seen.difference(excludes)
1338
return SearchResult(self._started_keys, excludes, len(included_keys),
1344
except StopIteration:
1348
"""Return the next ancestors of this revision.
1350
Ancestors are returned in the order they are seen in a breadth-first
1351
traversal. No ancestor will be returned more than once. Ancestors are
1352
returned before their parentage is queried, so ghosts and missing
1353
revisions (including the start revisions) are included in the result.
1354
This can save a round trip in LCA style calculation by allowing
1355
convergence to be detected without reading the data for the revision
1356
the convergence occurs on.
1358
:return: A set of revision_ids.
1360
if self._returning != 'next':
1361
# switch to returning the query, not the results.
1362
self._returning = 'next'
1363
self._iterations += 1
1366
if len(self._next_query) == 0:
1367
raise StopIteration()
1368
# We have seen what we're querying at this point as we are returning
1369
# the query, not the results.
1370
self.seen.update(self._next_query)
1371
return self._next_query
1373
def next_with_ghosts(self):
1374
"""Return the next found ancestors, with ghosts split out.
1376
Ancestors are returned in the order they are seen in a breadth-first
1377
traversal. No ancestor will be returned more than once. Ancestors are
1378
returned only after asking for their parents, which allows us to detect
1379
which revisions are ghosts and which are not.
1381
:return: A tuple with (present ancestors, ghost ancestors) sets.
1383
if self._returning != 'next_with_ghosts':
1384
# switch to returning the results, not the current query.
1385
self._returning = 'next_with_ghosts'
1387
if len(self._next_query) == 0:
1388
raise StopIteration()
1390
return self._current_present, self._current_ghosts
1393
"""Advance the search.
1395
Updates self.seen, self._next_query, self._current_present,
1396
self._current_ghosts, self._current_parents and self._iterations.
1398
self._iterations += 1
1399
found, ghosts, next, parents = self._do_query(self._next_query)
1400
self._current_present = found
1401
self._current_ghosts = ghosts
1402
self._next_query = next
1403
self._current_parents = parents
1404
# ghosts are implicit stop points, otherwise the search cannot be
1405
# repeated when ghosts are filled.
1406
self._stopped_keys.update(ghosts)
1408
def _do_query(self, revisions):
1409
"""Query for revisions.
1411
Adds revisions to the seen set.
1413
:param revisions: Revisions to query.
1414
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1415
set(parents_of_found_revisions), dict(found_revisions:parents)).
1417
found_revisions = set()
1418
parents_of_found = set()
1419
# revisions may contain nodes that point to other nodes in revisions:
1420
# we want to filter them out.
1421
self.seen.update(revisions)
1422
parent_map = self._parents_provider.get_parent_map(revisions)
1423
found_revisions.update(parent_map)
1424
for rev_id, parents in parent_map.iteritems():
1427
new_found_parents = [p for p in parents if p not in self.seen]
1428
if new_found_parents:
1429
# Calling set.update() with an empty generator is actually
1431
parents_of_found.update(new_found_parents)
1432
ghost_revisions = revisions - found_revisions
1433
return found_revisions, ghost_revisions, parents_of_found, parent_map
1438
def find_seen_ancestors(self, revisions):
1439
"""Find ancestors of these revisions that have already been seen.
1441
This function generally makes the assumption that querying for the
1442
parents of a node that has already been queried is reasonably cheap.
1443
(eg, not a round trip to a remote host).
1445
# TODO: Often we might ask one searcher for its seen ancestors, and
1446
# then ask another searcher the same question. This can result in
1447
# searching the same revisions repeatedly if the two searchers
1448
# have a lot of overlap.
1449
all_seen = self.seen
1450
pending = set(revisions).intersection(all_seen)
1451
seen_ancestors = set(pending)
1453
if self._returning == 'next':
1454
# self.seen contains what nodes have been returned, not what nodes
1455
# have been queried. We don't want to probe for nodes that haven't
1456
# been searched yet.
1457
not_searched_yet = self._next_query
1459
not_searched_yet = ()
1460
pending.difference_update(not_searched_yet)
1461
get_parent_map = self._parents_provider.get_parent_map
1463
parent_map = get_parent_map(pending)
1465
# We don't care if it is a ghost, since it can't be seen if it is
1467
for parent_ids in parent_map.itervalues():
1468
all_parents.extend(parent_ids)
1469
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1470
seen_ancestors.update(next_pending)
1471
next_pending.difference_update(not_searched_yet)
1472
pending = next_pending
1474
return seen_ancestors
1476
def stop_searching_any(self, revisions):
1478
Remove any of the specified revisions from the search list.
1480
None of the specified revisions are required to be present in the
1483
It is okay to call stop_searching_any() for revisions which were seen
1484
in previous iterations. It is the callers responsibility to call
1485
find_seen_ancestors() to make sure that current search tips that are
1486
ancestors of those revisions are also stopped. All explicitly stopped
1487
revisions will be excluded from the search result's get_keys(), though.
1489
# TODO: does this help performance?
1492
revisions = frozenset(revisions)
1493
if self._returning == 'next':
1494
stopped = self._next_query.intersection(revisions)
1495
self._next_query = self._next_query.difference(revisions)
1497
stopped_present = self._current_present.intersection(revisions)
1498
stopped = stopped_present.union(
1499
self._current_ghosts.intersection(revisions))
1500
self._current_present.difference_update(stopped)
1501
self._current_ghosts.difference_update(stopped)
1502
# stopping 'x' should stop returning parents of 'x', but
1503
# not if 'y' always references those same parents
1504
stop_rev_references = {}
1505
for rev in stopped_present:
1506
for parent_id in self._current_parents[rev]:
1507
if parent_id not in stop_rev_references:
1508
stop_rev_references[parent_id] = 0
1509
stop_rev_references[parent_id] += 1
1510
# if only the stopped revisions reference it, the ref count will be
1512
for parents in self._current_parents.itervalues():
1513
for parent_id in parents:
1515
stop_rev_references[parent_id] -= 1
1518
stop_parents = set()
1519
for rev_id, refs in stop_rev_references.iteritems():
1521
stop_parents.add(rev_id)
1522
self._next_query.difference_update(stop_parents)
1523
self._stopped_keys.update(stopped)
1524
self._stopped_keys.update(revisions)
1527
def start_searching(self, revisions):
1528
"""Add revisions to the search.
1530
The parents of revisions will be returned from the next call to next()
1531
or next_with_ghosts(). If next_with_ghosts was the most recently used
1532
next* call then the return value is the result of looking up the
1533
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1535
revisions = frozenset(revisions)
1536
self._started_keys.update(revisions)
1537
new_revisions = revisions.difference(self.seen)
1538
if self._returning == 'next':
1539
self._next_query.update(new_revisions)
1540
self.seen.update(new_revisions)
1542
# perform a query on revisions
1543
revs, ghosts, query, parents = self._do_query(revisions)
1544
self._stopped_keys.update(ghosts)
1545
self._current_present.update(revs)
1546
self._current_ghosts.update(ghosts)
1547
self._next_query.update(query)
1548
self._current_parents.update(parents)
1552
class AbstractSearchResult(object):
1553
"""The result of a search, describing a set of keys.
1555
Search results are typically used as the 'fetch_spec' parameter when
1558
:seealso: AbstractSearch
1561
def get_recipe(self):
1562
"""Return a recipe that can be used to replay this search.
1564
The recipe allows reconstruction of the same results at a later date.
1566
:return: A tuple of (search_kind_str, *details). The details vary by
1567
kind of search result.
1569
raise NotImplementedError(self.get_recipe)
1571
def get_network_struct(self):
1572
"""Return a tuple that can be transmitted via the HPSS protocol."""
1573
raise NotImplementedError(self.get_network_struct)
1576
"""Return the keys found in this search.
1578
:return: A set of keys.
1580
raise NotImplementedError(self.get_keys)
1583
"""Return false if the search lists 1 or more revisions."""
1584
raise NotImplementedError(self.is_empty)
1586
def refine(self, seen, referenced):
1587
"""Create a new search by refining this search.
1589
:param seen: Revisions that have been satisfied.
1590
:param referenced: Revision references observed while satisfying some
1592
:return: A search result.
1594
raise NotImplementedError(self.refine)
1597
class AbstractSearch(object):
1598
"""A search that can be executed, producing a search result.
1600
:seealso: AbstractSearchResult
1604
"""Construct a network-ready search result from this search description.
1606
This may take some time to search repositories, etc.
1608
:return: A search result (an object that implements
1609
AbstractSearchResult's API).
1611
raise NotImplementedError(self.execute)
1614
class SearchResult(AbstractSearchResult):
1615
"""The result of a breadth first search.
1617
A SearchResult provides the ability to reconstruct the search or access a
1618
set of the keys the search found.
1621
def __init__(self, start_keys, exclude_keys, key_count, keys):
1622
"""Create a SearchResult.
1624
:param start_keys: The keys the search started at.
1625
:param exclude_keys: The keys the search excludes.
1626
:param key_count: The total number of keys (from start to but not
1628
:param keys: The keys the search found. Note that in future we may get
1629
a SearchResult from a smart server, in which case the keys list is
1630
not necessarily immediately available.
1632
self._recipe = ('search', start_keys, exclude_keys, key_count)
1633
self._keys = frozenset(keys)
1636
kind, start_keys, exclude_keys, key_count = self._recipe
1637
if len(start_keys) > 5:
1638
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1640
start_keys_repr = repr(start_keys)
1641
if len(exclude_keys) > 5:
1642
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1644
exclude_keys_repr = repr(exclude_keys)
1645
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1646
kind, start_keys_repr, exclude_keys_repr, key_count)
1648
def get_recipe(self):
1649
"""Return a recipe that can be used to replay this search.
1651
The recipe allows reconstruction of the same results at a later date
1652
without knowing all the found keys. The essential elements are a list
1653
of keys to start and to stop at. In order to give reproducible
1654
results when ghosts are encountered by a search they are automatically
1655
added to the exclude list (or else ghost filling may alter the
1658
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1659
revision_count). To recreate the results of this search, create a
1660
breadth first searcher on the same graph starting at start_keys.
1661
Then call next() (or next_with_ghosts()) repeatedly, and on every
1662
result, call stop_searching_any on any keys from the exclude_keys
1663
set. The revision_count value acts as a trivial cross-check - the
1664
found revisions of the new search should have as many elements as
1665
revision_count. If it does not, then additional revisions have been
1666
ghosted since the search was executed the first time and the second
1671
def get_network_struct(self):
1672
start_keys = ' '.join(self._recipe[1])
1673
stop_keys = ' '.join(self._recipe[2])
1674
count = str(self._recipe[3])
1675
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1678
"""Return the keys found in this search.
1680
:return: A set of keys.
1685
"""Return false if the search lists 1 or more revisions."""
1686
return self._recipe[3] == 0
1688
def refine(self, seen, referenced):
1689
"""Create a new search by refining this search.
1691
:param seen: Revisions that have been satisfied.
1692
:param referenced: Revision references observed while satisfying some
1695
start = self._recipe[1]
1696
exclude = self._recipe[2]
1697
count = self._recipe[3]
1698
keys = self.get_keys()
1699
# New heads = referenced + old heads - seen things - exclude
1700
pending_refs = set(referenced)
1701
pending_refs.update(start)
1702
pending_refs.difference_update(seen)
1703
pending_refs.difference_update(exclude)
1704
# New exclude = old exclude + satisfied heads
1705
seen_heads = start.intersection(seen)
1706
exclude.update(seen_heads)
1707
# keys gets seen removed
1709
# length is reduced by len(seen)
1711
return SearchResult(pending_refs, exclude, count, keys)
1714
class PendingAncestryResult(AbstractSearchResult):
1715
"""A search result that will reconstruct the ancestry for some graph heads.
1717
Unlike SearchResult, this doesn't hold the complete search result in
1718
memory, it just holds a description of how to generate it.
1721
def __init__(self, heads, repo):
1724
:param heads: an iterable of graph heads.
1725
:param repo: a repository to use to generate the ancestry for the given
1728
self.heads = frozenset(heads)
1732
if len(self.heads) > 5:
1733
heads_repr = repr(list(self.heads)[:5])[:-1]
1734
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1736
heads_repr = repr(self.heads)
1737
return '<%s heads:%s repo:%r>' % (
1738
self.__class__.__name__, heads_repr, self.repo)
1740
def get_recipe(self):
1741
"""Return a recipe that can be used to replay this search.
1743
The recipe allows reconstruction of the same results at a later date.
1745
:seealso SearchResult.get_recipe:
1747
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1748
To recreate this result, create a PendingAncestryResult with the
1751
return ('proxy-search', self.heads, set(), -1)
1753
def get_network_struct(self):
1754
parts = ['ancestry-of']
1755
parts.extend(self.heads)
1759
"""See SearchResult.get_keys.
1761
Returns all the keys for the ancestry of the heads, excluding
1764
return self._get_keys(self.repo.get_graph())
1766
def _get_keys(self, graph):
1767
NULL_REVISION = revision.NULL_REVISION
1768
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1769
if key != NULL_REVISION and parents is not None]
1773
"""Return false if the search lists 1 or more revisions."""
1774
if revision.NULL_REVISION in self.heads:
1775
return len(self.heads) == 1
1777
return len(self.heads) == 0
1779
def refine(self, seen, referenced):
1780
"""Create a new search by refining this search.
1782
:param seen: Revisions that have been satisfied.
1783
:param referenced: Revision references observed while satisfying some
1786
referenced = self.heads.union(referenced)
1787
return PendingAncestryResult(referenced - seen, self.repo)
1790
class EmptySearchResult(AbstractSearchResult):
1791
"""An empty search result."""
1797
class EverythingResult(AbstractSearchResult):
1798
"""A search result that simply requests everything in the repository."""
1800
def __init__(self, repo):
1804
return '%s(%r)' % (self.__class__.__name__, self._repo)
1806
def get_recipe(self):
1807
raise NotImplementedError(self.get_recipe)
1809
def get_network_struct(self):
1810
return ('everything',)
1813
if 'evil' in debug.debug_flags:
1814
from bzrlib import remote
1815
if isinstance(self._repo, remote.RemoteRepository):
1816
# warn developers (not users) not to do this
1817
trace.mutter_callsite(
1818
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1819
return self._repo.all_revision_ids()
1822
# It's ok for this to wrongly return False: the worst that can happen
1823
# is that RemoteStreamSource will initiate a get_stream on an empty
1824
# repository. And almost all repositories are non-empty.
1827
def refine(self, seen, referenced):
1828
heads = set(self._repo.all_revision_ids())
1829
heads.difference_update(seen)
1830
heads.update(referenced)
1831
return PendingAncestryResult(heads, self._repo)
1834
class EverythingNotInOther(AbstractSearch):
1835
"""Find all revisions in that are in one repo but not the other."""
1837
def __init__(self, to_repo, from_repo, find_ghosts=False):
1838
self.to_repo = to_repo
1839
self.from_repo = from_repo
1840
self.find_ghosts = find_ghosts
1843
return self.to_repo.search_missing_revision_ids(
1844
self.from_repo, find_ghosts=self.find_ghosts)
1847
class NotInOtherForRevs(AbstractSearch):
1848
"""Find all revisions missing in one repo for a some specific heads."""
1850
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1854
:param required_ids: revision IDs of heads that must be found, or else
1855
the search will fail with NoSuchRevision. All revisions in their
1856
ancestry not already in the other repository will be included in
1858
:param if_present_ids: revision IDs of heads that may be absent in the
1859
source repository. If present, then their ancestry not already
1860
found in other will be included in the search result.
1862
self.to_repo = to_repo
1863
self.from_repo = from_repo
1864
self.find_ghosts = find_ghosts
1865
self.required_ids = required_ids
1866
self.if_present_ids = if_present_ids
1869
if len(self.required_ids) > 5:
1870
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1872
reqd_revs_repr = repr(self.required_ids)
1873
if self.if_present_ids and len(self.if_present_ids) > 5:
1874
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1876
ifp_revs_repr = repr(self.if_present_ids)
1878
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1879
self.__class__.__name__, self.from_repo, self.to_repo,
1880
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1883
return self.to_repo.search_missing_revision_ids(
1884
self.from_repo, revision_ids=self.required_ids,
1885
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1888
def collapse_linear_regions(parent_map):
1889
"""Collapse regions of the graph that are 'linear'.
1895
can be collapsed by removing B and getting::
1899
:param parent_map: A dictionary mapping children to their parents
1900
:return: Another dictionary with 'linear' chains collapsed
1902
# Note: this isn't a strictly minimal collapse. For example:
1910
# Will not have 'D' removed, even though 'E' could fit. Also:
1916
# A and C are both kept because they are edges of the graph. We *could* get
1917
# rid of A if we wanted.
1925
# Will not have any nodes removed, even though you do have an
1926
# 'uninteresting' linear D->B and E->C
1928
for child, parents in parent_map.iteritems():
1929
children.setdefault(child, [])
1931
children.setdefault(p, []).append(child)
1933
orig_children = dict(children)
1935
result = dict(parent_map)
1936
for node in parent_map:
1937
parents = result[node]
1938
if len(parents) == 1:
1939
parent_children = children[parents[0]]
1940
if len(parent_children) != 1:
1941
# This is not the only child
1943
node_children = children[node]
1944
if len(node_children) != 1:
1946
child_parents = result.get(node_children[0], None)
1947
if len(child_parents) != 1:
1948
# This is not its only parent
1950
# The child of this node only points at it, and the parent only has
1951
# this as a child. remove this node, and join the others together
1952
result[node_children[0]] = parents
1953
children[parents[0]] = node_children
1961
class GraphThunkIdsToKeys(object):
1962
"""Forwards calls about 'ids' to be about keys internally."""
1964
def __init__(self, graph):
1967
def topo_sort(self):
1968
return [r for (r,) in self._graph.topo_sort()]
1970
def heads(self, ids):
1971
"""See Graph.heads()"""
1972
as_keys = [(i,) for i in ids]
1973
head_keys = self._graph.heads(as_keys)
1974
return set([h[0] for h in head_keys])
1976
def merge_sort(self, tip_revision):
1977
return self._graph.merge_sort((tip_revision,))
1979
def add_node(self, revision, parents):
1980
self._graph.add_node((revision,), [(p,) for p in parents])
1983
_counters = [0,0,0,0,0,0,0]
1985
from bzrlib._known_graph_pyx import KnownGraph
1986
except ImportError, e:
1987
osutils.failed_to_load_extension(e)
1988
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
