1
# Copyright (C) 2007, 2008, 2009 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
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
29
STEP_UNIQUE_SEARCHER_EVERY = 5
31
# DIAGRAM of terminology
41
# In this diagram, relative to G and H:
42
# A, B, C, D, E are common ancestors.
43
# C, D and E are border ancestors, because each has a non-common descendant.
44
# D and E are least common ancestors because none of their descendants are
46
# C is not a least common ancestor because its descendant, E, is a common
49
# The find_unique_lca algorithm will pick A in two steps:
50
# 1. find_lca('G', 'H') => ['D', 'E']
51
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
54
class DictParentsProvider(object):
55
"""A parents provider for Graph objects."""
57
def __init__(self, ancestry):
58
self.ancestry = ancestry
61
return 'DictParentsProvider(%r)' % self.ancestry
63
def get_parent_map(self, keys):
64
"""See StackedParentsProvider.get_parent_map"""
65
ancestry = self.ancestry
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
68
@deprecated_function(deprecated_in((1, 16, 0)))
69
def _StackedParentsProvider(*args, **kwargs):
70
return StackedParentsProvider(*args, **kwargs)
72
class StackedParentsProvider(object):
73
"""A parents provider which stacks (or unions) multiple providers.
75
The providers are queries in the order of the provided parent_providers.
78
def __init__(self, parent_providers):
79
self._parent_providers = parent_providers
82
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
84
def get_parent_map(self, keys):
85
"""Get a mapping of keys => parents
87
A dictionary is returned with an entry for each key present in this
88
source. If this source doesn't have information about a key, it should
91
[NULL_REVISION] is used as the parent of the first user-committed
92
revision. Its parent list is empty.
94
:param keys: An iterable returning keys to check (eg revision_ids)
95
:return: A dictionary mapping each key to its parents
99
for parents_provider in self._parent_providers:
100
new_found = parents_provider.get_parent_map(remaining)
101
found.update(new_found)
102
remaining.difference_update(new_found)
108
class CachingParentsProvider(object):
109
"""A parents provider which will cache the revision => parents as a dict.
111
This is useful for providers which have an expensive look up.
113
Either a ParentsProvider or a get_parent_map-like callback may be
114
supplied. If it provides extra un-asked-for parents, they will be cached,
115
but filtered out of get_parent_map.
117
The cache is enabled by default, but may be disabled and re-enabled.
119
def __init__(self, parent_provider=None, get_parent_map=None):
122
:param parent_provider: The ParentProvider to use. It or
123
get_parent_map must be supplied.
124
:param get_parent_map: The get_parent_map callback to use. It or
125
parent_provider must be supplied.
127
self._real_provider = parent_provider
128
if get_parent_map is None:
129
self._get_parent_map = self._real_provider.get_parent_map
131
self._get_parent_map = get_parent_map
133
self.enable_cache(True)
136
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
138
def enable_cache(self, cache_misses=True):
140
if self._cache is not None:
141
raise AssertionError('Cache enabled when already enabled.')
143
self._cache_misses = cache_misses
144
self.missing_keys = set()
146
def disable_cache(self):
147
"""Disable and clear the cache."""
149
self._cache_misses = None
150
self.missing_keys = set()
152
def get_cached_map(self):
153
"""Return any cached get_parent_map values."""
154
if self._cache is None:
156
return dict(self._cache)
158
def get_parent_map(self, keys):
159
"""See StackedParentsProvider.get_parent_map."""
162
cache = self._get_parent_map(keys)
164
needed_revisions = set(key for key in keys if key not in cache)
165
# Do not ask for negatively cached keys
166
needed_revisions.difference_update(self.missing_keys)
168
parent_map = self._get_parent_map(needed_revisions)
169
cache.update(parent_map)
170
if self._cache_misses:
171
for key in needed_revisions:
172
if key not in parent_map:
173
self.note_missing_key(key)
176
value = cache.get(key)
177
if value is not None:
181
def note_missing_key(self, key):
182
"""Note that key is a missing key."""
183
if self._cache_misses:
184
self.missing_keys.add(key)
188
"""Provide incremental access to revision graphs.
190
This is the generic implementation; it is intended to be subclassed to
191
specialize it for other repository types.
194
def __init__(self, parents_provider):
195
"""Construct a Graph that uses several graphs as its input
197
This should not normally be invoked directly, because there may be
198
specialized implementations for particular repository types. See
199
Repository.get_graph().
201
:param parents_provider: An object providing a get_parent_map call
202
conforming to the behavior of
203
StackedParentsProvider.get_parent_map.
205
if getattr(parents_provider, 'get_parents', None) is not None:
206
self.get_parents = parents_provider.get_parents
207
if getattr(parents_provider, 'get_parent_map', None) is not None:
208
self.get_parent_map = parents_provider.get_parent_map
209
self._parents_provider = parents_provider
212
return 'Graph(%r)' % self._parents_provider
214
def find_lca(self, *revisions):
215
"""Determine the lowest common ancestors of the provided revisions
217
A lowest common ancestor is a common ancestor none of whose
218
descendants are common ancestors. In graphs, unlike trees, there may
219
be multiple lowest common ancestors.
221
This algorithm has two phases. Phase 1 identifies border ancestors,
222
and phase 2 filters border ancestors to determine lowest common
225
In phase 1, border ancestors are identified, using a breadth-first
226
search starting at the bottom of the graph. Searches are stopped
227
whenever a node or one of its descendants is determined to be common
229
In phase 2, the border ancestors are filtered to find the least
230
common ancestors. This is done by searching the ancestries of each
233
Phase 2 is perfomed on the principle that a border ancestor that is
234
not an ancestor of any other border ancestor is a least common
237
Searches are stopped when they find a node that is determined to be a
238
common ancestor of all border ancestors, because this shows that it
239
cannot be a descendant of any border ancestor.
241
The scaling of this operation should be proportional to
242
1. The number of uncommon ancestors
243
2. The number of border ancestors
244
3. The length of the shortest path between a border ancestor and an
245
ancestor of all border ancestors.
247
border_common, common, sides = self._find_border_ancestors(revisions)
248
# We may have common ancestors that can be reached from each other.
249
# - ask for the heads of them to filter it down to only ones that
250
# cannot be reached from each other - phase 2.
251
return self.heads(border_common)
253
def find_difference(self, left_revision, right_revision):
254
"""Determine the graph difference between two revisions"""
255
border, common, searchers = self._find_border_ancestors(
256
[left_revision, right_revision])
257
self._search_for_extra_common(common, searchers)
258
left = searchers[0].seen
259
right = searchers[1].seen
260
return (left.difference(right), right.difference(left))
262
def find_distance_to_null(self, target_revision_id, known_revision_ids):
263
"""Find the left-hand distance to the NULL_REVISION.
265
(This can also be considered the revno of a branch at
268
:param target_revision_id: A revision_id which we would like to know
270
:param known_revision_ids: [(revision_id, revno)] A list of known
271
revno, revision_id tuples. We'll use this to seed the search.
273
# Map from revision_ids to a known value for their revno
274
known_revnos = dict(known_revision_ids)
275
cur_tip = target_revision_id
277
NULL_REVISION = revision.NULL_REVISION
278
known_revnos[NULL_REVISION] = 0
280
searching_known_tips = list(known_revnos.keys())
282
unknown_searched = {}
284
while cur_tip not in known_revnos:
285
unknown_searched[cur_tip] = num_steps
287
to_search = set([cur_tip])
288
to_search.update(searching_known_tips)
289
parent_map = self.get_parent_map(to_search)
290
parents = parent_map.get(cur_tip, None)
291
if not parents: # An empty list or None is a ghost
292
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
296
for revision_id in searching_known_tips:
297
parents = parent_map.get(revision_id, None)
301
next_revno = known_revnos[revision_id] - 1
302
if next in unknown_searched:
303
# We have enough information to return a value right now
304
return next_revno + unknown_searched[next]
305
if next in known_revnos:
307
known_revnos[next] = next_revno
308
next_known_tips.append(next)
309
searching_known_tips = next_known_tips
311
# We reached a known revision, so just add in how many steps it took to
313
return known_revnos[cur_tip] + num_steps
315
def find_unique_ancestors(self, unique_revision, common_revisions):
316
"""Find the unique ancestors for a revision versus others.
318
This returns the ancestry of unique_revision, excluding all revisions
319
in the ancestry of common_revisions. If unique_revision is in the
320
ancestry, then the empty set will be returned.
322
:param unique_revision: The revision_id whose ancestry we are
324
XXX: Would this API be better if we allowed multiple revisions on
326
:param common_revisions: Revision_ids of ancestries to exclude.
327
:return: A set of revisions in the ancestry of unique_revision
329
if unique_revision in common_revisions:
332
# Algorithm description
333
# 1) Walk backwards from the unique node and all common nodes.
334
# 2) When a node is seen by both sides, stop searching it in the unique
335
# walker, include it in the common walker.
336
# 3) Stop searching when there are no nodes left for the unique walker.
337
# At this point, you have a maximal set of unique nodes. Some of
338
# them may actually be common, and you haven't reached them yet.
339
# 4) Start new searchers for the unique nodes, seeded with the
340
# information you have so far.
341
# 5) Continue searching, stopping the common searches when the search
342
# tip is an ancestor of all unique nodes.
343
# 6) Aggregate together unique searchers when they are searching the
344
# same tips. When all unique searchers are searching the same node,
345
# stop move it to a single 'all_unique_searcher'.
346
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
347
# Most of the time this produces very little important information.
348
# So don't step it as quickly as the other searchers.
349
# 8) Search is done when all common searchers have completed.
351
unique_searcher, common_searcher = self._find_initial_unique_nodes(
352
[unique_revision], common_revisions)
354
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
358
(all_unique_searcher,
359
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
360
unique_searcher, common_searcher)
362
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
363
unique_tip_searchers, common_searcher)
364
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
365
if 'graph' in debug.debug_flags:
366
trace.mutter('Found %d truly unique nodes out of %d',
367
len(true_unique_nodes), len(unique_nodes))
368
return true_unique_nodes
370
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
371
"""Steps 1-3 of find_unique_ancestors.
373
Find the maximal set of unique nodes. Some of these might actually
374
still be common, but we are sure that there are no other unique nodes.
376
:return: (unique_searcher, common_searcher)
379
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
380
# we know that unique_revisions aren't in common_revisions, so skip
382
unique_searcher.next()
383
common_searcher = self._make_breadth_first_searcher(common_revisions)
385
# As long as we are still finding unique nodes, keep searching
386
while unique_searcher._next_query:
387
next_unique_nodes = set(unique_searcher.step())
388
next_common_nodes = set(common_searcher.step())
390
# Check if either searcher encounters new nodes seen by the other
392
unique_are_common_nodes = next_unique_nodes.intersection(
393
common_searcher.seen)
394
unique_are_common_nodes.update(
395
next_common_nodes.intersection(unique_searcher.seen))
396
if unique_are_common_nodes:
397
ancestors = unique_searcher.find_seen_ancestors(
398
unique_are_common_nodes)
399
# TODO: This is a bit overboard, we only really care about
400
# the ancestors of the tips because the rest we
401
# already know. This is *correct* but causes us to
402
# search too much ancestry.
403
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
404
unique_searcher.stop_searching_any(ancestors)
405
common_searcher.start_searching(ancestors)
407
return unique_searcher, common_searcher
409
def _make_unique_searchers(self, unique_nodes, unique_searcher,
411
"""Create a searcher for all the unique search tips (step 4).
413
As a side effect, the common_searcher will stop searching any nodes
414
that are ancestors of the unique searcher tips.
416
:return: (all_unique_searcher, unique_tip_searchers)
418
unique_tips = self._remove_simple_descendants(unique_nodes,
419
self.get_parent_map(unique_nodes))
421
if len(unique_tips) == 1:
422
unique_tip_searchers = []
423
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
425
unique_tip_searchers = []
426
for tip in unique_tips:
427
revs_to_search = unique_searcher.find_seen_ancestors([tip])
428
revs_to_search.update(
429
common_searcher.find_seen_ancestors(revs_to_search))
430
searcher = self._make_breadth_first_searcher(revs_to_search)
431
# We don't care about the starting nodes.
432
searcher._label = tip
434
unique_tip_searchers.append(searcher)
436
ancestor_all_unique = None
437
for searcher in unique_tip_searchers:
438
if ancestor_all_unique is None:
439
ancestor_all_unique = set(searcher.seen)
441
ancestor_all_unique = ancestor_all_unique.intersection(
443
# Collapse all the common nodes into a single searcher
444
all_unique_searcher = self._make_breadth_first_searcher(
446
if ancestor_all_unique:
447
# We've seen these nodes in all the searchers, so we'll just go to
449
all_unique_searcher.step()
451
# Stop any search tips that are already known as ancestors of the
453
stopped_common = common_searcher.stop_searching_any(
454
common_searcher.find_seen_ancestors(ancestor_all_unique))
457
for searcher in unique_tip_searchers:
458
total_stopped += len(searcher.stop_searching_any(
459
searcher.find_seen_ancestors(ancestor_all_unique)))
460
if 'graph' in debug.debug_flags:
461
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
462
' (%d stopped search tips, %d common ancestors'
463
' (%d stopped common)',
464
len(unique_nodes), len(unique_tip_searchers),
465
total_stopped, len(ancestor_all_unique),
467
return all_unique_searcher, unique_tip_searchers
469
def _step_unique_and_common_searchers(self, common_searcher,
470
unique_tip_searchers,
472
"""Step all the searchers"""
473
newly_seen_common = set(common_searcher.step())
474
newly_seen_unique = set()
475
for searcher in unique_tip_searchers:
476
next = set(searcher.step())
477
next.update(unique_searcher.find_seen_ancestors(next))
478
next.update(common_searcher.find_seen_ancestors(next))
479
for alt_searcher in unique_tip_searchers:
480
if alt_searcher is searcher:
482
next.update(alt_searcher.find_seen_ancestors(next))
483
searcher.start_searching(next)
484
newly_seen_unique.update(next)
485
return newly_seen_common, newly_seen_unique
487
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
489
newly_seen_unique, step_all_unique):
490
"""Find nodes that are common to all unique_tip_searchers.
492
If it is time, step the all_unique_searcher, and add its nodes to the
495
common_to_all_unique_nodes = newly_seen_unique.copy()
496
for searcher in unique_tip_searchers:
497
common_to_all_unique_nodes.intersection_update(searcher.seen)
498
common_to_all_unique_nodes.intersection_update(
499
all_unique_searcher.seen)
500
# Step all-unique less frequently than the other searchers.
501
# In the common case, we don't need to spider out far here, so
502
# avoid doing extra work.
504
tstart = time.clock()
505
nodes = all_unique_searcher.step()
506
common_to_all_unique_nodes.update(nodes)
507
if 'graph' in debug.debug_flags:
508
tdelta = time.clock() - tstart
509
trace.mutter('all_unique_searcher step() took %.3fs'
510
'for %d nodes (%d total), iteration: %s',
511
tdelta, len(nodes), len(all_unique_searcher.seen),
512
all_unique_searcher._iterations)
513
return common_to_all_unique_nodes
515
def _collapse_unique_searchers(self, unique_tip_searchers,
516
common_to_all_unique_nodes):
517
"""Combine searchers that are searching the same tips.
519
When two searchers are searching the same tips, we can stop one of the
520
searchers. We also know that the maximal set of common ancestors is the
521
intersection of the two original searchers.
523
:return: A list of searchers that are searching unique nodes.
525
# Filter out searchers that don't actually search different
526
# nodes. We already have the ancestry intersection for them
527
unique_search_tips = {}
528
for searcher in unique_tip_searchers:
529
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
530
will_search_set = frozenset(searcher._next_query)
531
if not will_search_set:
532
if 'graph' in debug.debug_flags:
533
trace.mutter('Unique searcher %s was stopped.'
534
' (%s iterations) %d nodes stopped',
536
searcher._iterations,
538
elif will_search_set not in unique_search_tips:
539
# This searcher is searching a unique set of nodes, let it
540
unique_search_tips[will_search_set] = [searcher]
542
unique_search_tips[will_search_set].append(searcher)
543
# TODO: it might be possible to collapse searchers faster when they
544
# only have *some* search tips in common.
545
next_unique_searchers = []
546
for searchers in unique_search_tips.itervalues():
547
if len(searchers) == 1:
548
# Searching unique tips, go for it
549
next_unique_searchers.append(searchers[0])
551
# These searchers have started searching the same tips, we
552
# don't need them to cover the same ground. The
553
# intersection of their ancestry won't change, so create a
554
# new searcher, combining their histories.
555
next_searcher = searchers[0]
556
for searcher in searchers[1:]:
557
next_searcher.seen.intersection_update(searcher.seen)
558
if 'graph' in debug.debug_flags:
559
trace.mutter('Combining %d searchers into a single'
560
' searcher searching %d nodes with'
563
len(next_searcher._next_query),
564
len(next_searcher.seen))
565
next_unique_searchers.append(next_searcher)
566
return next_unique_searchers
568
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
569
unique_tip_searchers, common_searcher):
570
"""Steps 5-8 of find_unique_ancestors.
572
This function returns when common_searcher has stopped searching for
575
# We step the ancestor_all_unique searcher only every
576
# STEP_UNIQUE_SEARCHER_EVERY steps.
577
step_all_unique_counter = 0
578
# While we still have common nodes to search
579
while common_searcher._next_query:
581
newly_seen_unique) = self._step_unique_and_common_searchers(
582
common_searcher, unique_tip_searchers, unique_searcher)
583
# These nodes are common ancestors of all unique nodes
584
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
585
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
586
step_all_unique_counter==0)
587
step_all_unique_counter = ((step_all_unique_counter + 1)
588
% STEP_UNIQUE_SEARCHER_EVERY)
590
if newly_seen_common:
591
# If a 'common' node is an ancestor of all unique searchers, we
592
# can stop searching it.
593
common_searcher.stop_searching_any(
594
all_unique_searcher.seen.intersection(newly_seen_common))
595
if common_to_all_unique_nodes:
596
common_to_all_unique_nodes.update(
597
common_searcher.find_seen_ancestors(
598
common_to_all_unique_nodes))
599
# The all_unique searcher can start searching the common nodes
600
# but everyone else can stop.
601
# This is the sort of thing where we would like to not have it
602
# start_searching all of the nodes, but only mark all of them
603
# as seen, and have it search only the actual tips. Otherwise
604
# it is another get_parent_map() traversal for it to figure out
605
# what we already should know.
606
all_unique_searcher.start_searching(common_to_all_unique_nodes)
607
common_searcher.stop_searching_any(common_to_all_unique_nodes)
609
next_unique_searchers = self._collapse_unique_searchers(
610
unique_tip_searchers, common_to_all_unique_nodes)
611
if len(unique_tip_searchers) != len(next_unique_searchers):
612
if 'graph' in debug.debug_flags:
613
trace.mutter('Collapsed %d unique searchers => %d'
615
len(unique_tip_searchers),
616
len(next_unique_searchers),
617
all_unique_searcher._iterations)
618
unique_tip_searchers = next_unique_searchers
620
def get_parent_map(self, revisions):
621
"""Get a map of key:parent_list for revisions.
623
This implementation delegates to get_parents, for old parent_providers
624
that do not supply get_parent_map.
627
for rev, parents in self.get_parents(revisions):
628
if parents is not None:
629
result[rev] = parents
632
def _make_breadth_first_searcher(self, revisions):
633
return _BreadthFirstSearcher(revisions, self)
635
def _find_border_ancestors(self, revisions):
636
"""Find common ancestors with at least one uncommon descendant.
638
Border ancestors are identified using a breadth-first
639
search starting at the bottom of the graph. Searches are stopped
640
whenever a node or one of its descendants is determined to be common.
642
This will scale with the number of uncommon ancestors.
644
As well as the border ancestors, a set of seen common ancestors and a
645
list of sets of seen ancestors for each input revision is returned.
646
This allows calculation of graph difference from the results of this
649
if None in revisions:
650
raise errors.InvalidRevisionId(None, self)
651
common_ancestors = set()
652
searchers = [self._make_breadth_first_searcher([r])
654
active_searchers = searchers[:]
655
border_ancestors = set()
659
for searcher in searchers:
660
new_ancestors = searcher.step()
662
newly_seen.update(new_ancestors)
664
for revision in newly_seen:
665
if revision in common_ancestors:
666
# Not a border ancestor because it was seen as common
668
new_common.add(revision)
670
for searcher in searchers:
671
if revision not in searcher.seen:
674
# This is a border because it is a first common that we see
675
# after walking for a while.
676
border_ancestors.add(revision)
677
new_common.add(revision)
679
for searcher in searchers:
680
new_common.update(searcher.find_seen_ancestors(new_common))
681
for searcher in searchers:
682
searcher.start_searching(new_common)
683
common_ancestors.update(new_common)
685
# Figure out what the searchers will be searching next, and if
686
# there is only 1 set being searched, then we are done searching,
687
# since all searchers would have to be searching the same data,
688
# thus it *must* be in common.
689
unique_search_sets = set()
690
for searcher in searchers:
691
will_search_set = frozenset(searcher._next_query)
692
if will_search_set not in unique_search_sets:
693
# This searcher is searching a unique set of nodes, let it
694
unique_search_sets.add(will_search_set)
696
if len(unique_search_sets) == 1:
697
nodes = unique_search_sets.pop()
698
uncommon_nodes = nodes.difference(common_ancestors)
700
raise AssertionError("Somehow we ended up converging"
701
" without actually marking them as"
704
"\nuncommon_nodes: %s"
705
% (revisions, uncommon_nodes))
707
return border_ancestors, common_ancestors, searchers
709
def heads(self, keys):
710
"""Return the heads from amongst keys.
712
This is done by searching the ancestries of each key. Any key that is
713
reachable from another key is not returned; all the others are.
715
This operation scales with the relative depth between any two keys. If
716
any two keys are completely disconnected all ancestry of both sides
719
:param keys: An iterable of keys.
720
:return: A set of the heads. Note that as a set there is no ordering
721
information. Callers will need to filter their input to create
722
order if they need it.
724
candidate_heads = set(keys)
725
if revision.NULL_REVISION in candidate_heads:
726
# NULL_REVISION is only a head if it is the only entry
727
candidate_heads.remove(revision.NULL_REVISION)
728
if not candidate_heads:
729
return set([revision.NULL_REVISION])
730
if len(candidate_heads) < 2:
731
return candidate_heads
732
searchers = dict((c, self._make_breadth_first_searcher([c]))
733
for c in candidate_heads)
734
active_searchers = dict(searchers)
735
# skip over the actual candidate for each searcher
736
for searcher in active_searchers.itervalues():
738
# The common walker finds nodes that are common to two or more of the
739
# input keys, so that we don't access all history when a currently
740
# uncommon search point actually meets up with something behind a
741
# common search point. Common search points do not keep searches
742
# active; they just allow us to make searches inactive without
743
# accessing all history.
744
common_walker = self._make_breadth_first_searcher([])
745
while len(active_searchers) > 0:
750
except StopIteration:
751
# No common points being searched at this time.
753
for candidate in active_searchers.keys():
755
searcher = active_searchers[candidate]
757
# rare case: we deleted candidate in a previous iteration
758
# through this for loop, because it was determined to be
759
# a descendant of another candidate.
762
ancestors.update(searcher.next())
763
except StopIteration:
764
del active_searchers[candidate]
766
# process found nodes
768
for ancestor in ancestors:
769
if ancestor in candidate_heads:
770
candidate_heads.remove(ancestor)
771
del searchers[ancestor]
772
if ancestor in active_searchers:
773
del active_searchers[ancestor]
774
# it may meet up with a known common node
775
if ancestor in common_walker.seen:
776
# some searcher has encountered our known common nodes:
778
ancestor_set = set([ancestor])
779
for searcher in searchers.itervalues():
780
searcher.stop_searching_any(ancestor_set)
782
# or it may have been just reached by all the searchers:
783
for searcher in searchers.itervalues():
784
if ancestor not in searcher.seen:
787
# The final active searcher has just reached this node,
788
# making it be known as a descendant of all candidates,
789
# so we can stop searching it, and any seen ancestors
790
new_common.add(ancestor)
791
for searcher in searchers.itervalues():
793
searcher.find_seen_ancestors([ancestor])
794
searcher.stop_searching_any(seen_ancestors)
795
common_walker.start_searching(new_common)
796
return candidate_heads
798
def find_merge_order(self, tip_revision_id, lca_revision_ids):
799
"""Find the order that each revision was merged into tip.
801
This basically just walks backwards with a stack, and walks left-first
802
until it finds a node to stop.
804
if len(lca_revision_ids) == 1:
805
return list(lca_revision_ids)
806
looking_for = set(lca_revision_ids)
807
# TODO: Is there a way we could do this "faster" by batching up the
808
# get_parent_map requests?
809
# TODO: Should we also be culling the ancestry search right away? We
810
# could add looking_for to the "stop" list, and walk their
811
# ancestry in batched mode. The flip side is it might mean we walk a
812
# lot of "stop" nodes, rather than only the minimum.
813
# Then again, without it we may trace back into ancestry we could have
815
stack = [tip_revision_id]
818
while stack and looking_for:
821
if next in looking_for:
823
looking_for.remove(next)
824
if len(looking_for) == 1:
825
found.append(looking_for.pop())
828
parent_ids = self.get_parent_map([next]).get(next, None)
829
if not parent_ids: # Ghost, nothing to search here
831
for parent_id in reversed(parent_ids):
832
# TODO: (performance) We see the parent at this point, but we
833
# wait to mark it until later to make sure we get left
834
# parents before right parents. However, instead of
835
# waiting until we have traversed enough parents, we
836
# could instead note that we've found it, and once all
837
# parents are in the stack, just reverse iterate the
839
if parent_id not in stop:
840
# this will need to be searched
841
stack.append(parent_id)
845
def find_unique_lca(self, left_revision, right_revision,
847
"""Find a unique LCA.
849
Find lowest common ancestors. If there is no unique common
850
ancestor, find the lowest common ancestors of those ancestors.
852
Iteration stops when a unique lowest common ancestor is found.
853
The graph origin is necessarily a unique lowest common ancestor.
855
Note that None is not an acceptable substitute for NULL_REVISION.
856
in the input for this method.
858
:param count_steps: If True, the return value will be a tuple of
859
(unique_lca, steps) where steps is the number of times that
860
find_lca was run. If False, only unique_lca is returned.
862
revisions = [left_revision, right_revision]
866
lca = self.find_lca(*revisions)
874
raise errors.NoCommonAncestor(left_revision, right_revision)
877
def iter_ancestry(self, revision_ids):
878
"""Iterate the ancestry of this revision.
880
:param revision_ids: Nodes to start the search
881
:return: Yield tuples mapping a revision_id to its parents for the
882
ancestry of revision_id.
883
Ghosts will be returned with None as their parents, and nodes
884
with no parents will have NULL_REVISION as their only parent. (As
885
defined by get_parent_map.)
886
There will also be a node for (NULL_REVISION, ())
888
pending = set(revision_ids)
891
processed.update(pending)
892
next_map = self.get_parent_map(pending)
894
for item in next_map.iteritems():
896
next_pending.update(p for p in item[1] if p not in processed)
897
ghosts = pending.difference(next_map)
900
pending = next_pending
902
def iter_topo_order(self, revisions):
903
"""Iterate through the input revisions in topological order.
905
This sorting only ensures that parents come before their children.
906
An ancestor may sort after a descendant if the relationship is not
907
visible in the supplied list of revisions.
909
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
910
return sorter.iter_topo_order()
912
def is_ancestor(self, candidate_ancestor, candidate_descendant):
913
"""Determine whether a revision is an ancestor of another.
915
We answer this using heads() as heads() has the logic to perform the
916
smallest number of parent lookups to determine the ancestral
917
relationship between N revisions.
919
return set([candidate_descendant]) == self.heads(
920
[candidate_ancestor, candidate_descendant])
922
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
923
"""Determine whether a revision is between two others.
925
returns true if and only if:
926
lower_bound_revid <= revid <= upper_bound_revid
928
return ((upper_bound_revid is None or
929
self.is_ancestor(revid, upper_bound_revid)) and
930
(lower_bound_revid is None or
931
self.is_ancestor(lower_bound_revid, revid)))
933
def _search_for_extra_common(self, common, searchers):
934
"""Make sure that unique nodes are genuinely unique.
936
After _find_border_ancestors, all nodes marked "common" are indeed
937
common. Some of the nodes considered unique are not, due to history
938
shortcuts stopping the searches early.
940
We know that we have searched enough when all common search tips are
941
descended from all unique (uncommon) nodes because we know that a node
942
cannot be an ancestor of its own ancestor.
944
:param common: A set of common nodes
945
:param searchers: The searchers returned from _find_border_ancestors
949
# A) The passed in searchers should all be on the same tips, thus
950
# they should be considered the "common" searchers.
951
# B) We find the difference between the searchers, these are the
952
# "unique" nodes for each side.
953
# C) We do a quick culling so that we only start searching from the
954
# more interesting unique nodes. (A unique ancestor is more
955
# interesting than any of its children.)
956
# D) We start searching for ancestors common to all unique nodes.
957
# E) We have the common searchers stop searching any ancestors of
959
# F) When there are no more common search tips, we stop
961
# TODO: We need a way to remove unique_searchers when they overlap with
962
# other unique searchers.
963
if len(searchers) != 2:
964
raise NotImplementedError(
965
"Algorithm not yet implemented for > 2 searchers")
966
common_searchers = searchers
967
left_searcher = searchers[0]
968
right_searcher = searchers[1]
969
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
970
if not unique: # No unique nodes, nothing to do
972
total_unique = len(unique)
973
unique = self._remove_simple_descendants(unique,
974
self.get_parent_map(unique))
975
simple_unique = len(unique)
977
unique_searchers = []
978
for revision_id in unique:
979
if revision_id in left_searcher.seen:
980
parent_searcher = left_searcher
982
parent_searcher = right_searcher
983
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
984
if not revs_to_search: # XXX: This shouldn't be possible
985
revs_to_search = [revision_id]
986
searcher = self._make_breadth_first_searcher(revs_to_search)
987
# We don't care about the starting nodes.
989
unique_searchers.append(searcher)
991
# possible todo: aggregate the common searchers into a single common
992
# searcher, just make sure that we include the nodes into the .seen
993
# properties of the original searchers
995
ancestor_all_unique = None
996
for searcher in unique_searchers:
997
if ancestor_all_unique is None:
998
ancestor_all_unique = set(searcher.seen)
1000
ancestor_all_unique = ancestor_all_unique.intersection(
1003
trace.mutter('Started %s unique searchers for %s unique revisions',
1004
simple_unique, total_unique)
1006
while True: # If we have no more nodes we have nothing to do
1007
newly_seen_common = set()
1008
for searcher in common_searchers:
1009
newly_seen_common.update(searcher.step())
1010
newly_seen_unique = set()
1011
for searcher in unique_searchers:
1012
newly_seen_unique.update(searcher.step())
1013
new_common_unique = set()
1014
for revision in newly_seen_unique:
1015
for searcher in unique_searchers:
1016
if revision not in searcher.seen:
1019
# This is a border because it is a first common that we see
1020
# after walking for a while.
1021
new_common_unique.add(revision)
1022
if newly_seen_common:
1023
# These are nodes descended from one of the 'common' searchers.
1024
# Make sure all searchers are on the same page
1025
for searcher in common_searchers:
1026
newly_seen_common.update(
1027
searcher.find_seen_ancestors(newly_seen_common))
1028
# We start searching the whole ancestry. It is a bit wasteful,
1029
# though. We really just want to mark all of these nodes as
1030
# 'seen' and then start just the tips. However, it requires a
1031
# get_parent_map() call to figure out the tips anyway, and all
1032
# redundant requests should be fairly fast.
1033
for searcher in common_searchers:
1034
searcher.start_searching(newly_seen_common)
1036
# If a 'common' node is an ancestor of all unique searchers, we
1037
# can stop searching it.
1038
stop_searching_common = ancestor_all_unique.intersection(
1040
if stop_searching_common:
1041
for searcher in common_searchers:
1042
searcher.stop_searching_any(stop_searching_common)
1043
if new_common_unique:
1044
# We found some ancestors that are common
1045
for searcher in unique_searchers:
1046
new_common_unique.update(
1047
searcher.find_seen_ancestors(new_common_unique))
1048
# Since these are common, we can grab another set of ancestors
1050
for searcher in common_searchers:
1051
new_common_unique.update(
1052
searcher.find_seen_ancestors(new_common_unique))
1054
# We can tell all of the unique searchers to start at these
1055
# nodes, and tell all of the common searchers to *stop*
1056
# searching these nodes
1057
for searcher in unique_searchers:
1058
searcher.start_searching(new_common_unique)
1059
for searcher in common_searchers:
1060
searcher.stop_searching_any(new_common_unique)
1061
ancestor_all_unique.update(new_common_unique)
1063
# Filter out searchers that don't actually search different
1064
# nodes. We already have the ancestry intersection for them
1065
next_unique_searchers = []
1066
unique_search_sets = set()
1067
for searcher in unique_searchers:
1068
will_search_set = frozenset(searcher._next_query)
1069
if will_search_set not in unique_search_sets:
1070
# This searcher is searching a unique set of nodes, let it
1071
unique_search_sets.add(will_search_set)
1072
next_unique_searchers.append(searcher)
1073
unique_searchers = next_unique_searchers
1074
for searcher in common_searchers:
1075
if searcher._next_query:
1078
# All common searcher have stopped searching
1081
def _remove_simple_descendants(self, revisions, parent_map):
1082
"""remove revisions which are children of other ones in the set
1084
This doesn't do any graph searching, it just checks the immediate
1085
parent_map to find if there are any children which can be removed.
1087
:param revisions: A set of revision_ids
1088
:return: A set of revision_ids with the children removed
1090
simple_ancestors = revisions.copy()
1091
# TODO: jam 20071214 we *could* restrict it to searching only the
1092
# parent_map of revisions already present in 'revisions', but
1093
# considering the general use case, I think this is actually
1096
# This is the same as the following loop. I don't know that it is any
1098
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1099
## if p_ids is not None and revisions.intersection(p_ids))
1100
## return simple_ancestors
1102
# Yet Another Way, invert the parent map (which can be cached)
1104
## for revision_id, parent_ids in parent_map.iteritems():
1105
## for p_id in parent_ids:
1106
## descendants.setdefault(p_id, []).append(revision_id)
1107
## for revision in revisions.intersection(descendants):
1108
## simple_ancestors.difference_update(descendants[revision])
1109
## return simple_ancestors
1110
for revision, parent_ids in parent_map.iteritems():
1111
if parent_ids is None:
1113
for parent_id in parent_ids:
1114
if parent_id in revisions:
1115
# This node has a parent present in the set, so we can
1117
simple_ancestors.discard(revision)
1119
return simple_ancestors
1122
class HeadsCache(object):
1123
"""A cache of results for graph heads calls."""
1125
def __init__(self, graph):
1129
def heads(self, keys):
1130
"""Return the heads of keys.
1132
This matches the API of Graph.heads(), specifically the return value is
1133
a set which can be mutated, and ordering of the input is not preserved
1136
:see also: Graph.heads.
1137
:param keys: The keys to calculate heads for.
1138
:return: A set containing the heads, which may be mutated without
1139
affecting future lookups.
1141
keys = frozenset(keys)
1143
return set(self._heads[keys])
1145
heads = self.graph.heads(keys)
1146
self._heads[keys] = heads
1150
class FrozenHeadsCache(object):
1151
"""Cache heads() calls, assuming the caller won't modify them."""
1153
def __init__(self, graph):
1157
def heads(self, keys):
1158
"""Return the heads of keys.
1160
Similar to Graph.heads(). The main difference is that the return value
1161
is a frozen set which cannot be mutated.
1163
:see also: Graph.heads.
1164
:param keys: The keys to calculate heads for.
1165
:return: A frozenset containing the heads.
1167
keys = frozenset(keys)
1169
return self._heads[keys]
1171
heads = frozenset(self.graph.heads(keys))
1172
self._heads[keys] = heads
1175
def cache(self, keys, heads):
1176
"""Store a known value."""
1177
self._heads[frozenset(keys)] = frozenset(heads)
1180
class _BreadthFirstSearcher(object):
1181
"""Parallel search breadth-first the ancestry of revisions.
1183
This class implements the iterator protocol, but additionally
1184
1. provides a set of seen ancestors, and
1185
2. allows some ancestries to be unsearched, via stop_searching_any
1188
def __init__(self, revisions, parents_provider):
1189
self._iterations = 0
1190
self._next_query = set(revisions)
1192
self._started_keys = set(self._next_query)
1193
self._stopped_keys = set()
1194
self._parents_provider = parents_provider
1195
self._returning = 'next_with_ghosts'
1196
self._current_present = set()
1197
self._current_ghosts = set()
1198
self._current_parents = {}
1201
if self._iterations:
1202
prefix = "searching"
1205
search = '%s=%r' % (prefix, list(self._next_query))
1206
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1207
' seen=%r)' % (self._iterations, search, list(self.seen)))
1209
def get_result(self):
1210
"""Get a SearchResult for the current state of this searcher.
1212
:return: A SearchResult for this search so far. The SearchResult is
1213
static - the search can be advanced and the search result will not
1214
be invalidated or altered.
1216
if self._returning == 'next':
1217
# We have to know the current nodes children to be able to list the
1218
# exclude keys for them. However, while we could have a second
1219
# look-ahead result buffer and shuffle things around, this method
1220
# is typically only called once per search - when memoising the
1221
# results of the search.
1222
found, ghosts, next, parents = self._do_query(self._next_query)
1223
# pretend we didn't query: perhaps we should tweak _do_query to be
1224
# entirely stateless?
1225
self.seen.difference_update(next)
1226
next_query = next.union(ghosts)
1228
next_query = self._next_query
1229
excludes = self._stopped_keys.union(next_query)
1230
included_keys = self.seen.difference(excludes)
1231
return SearchResult(self._started_keys, excludes, len(included_keys),
1237
except StopIteration:
1241
"""Return the next ancestors of this revision.
1243
Ancestors are returned in the order they are seen in a breadth-first
1244
traversal. No ancestor will be returned more than once. Ancestors are
1245
returned before their parentage is queried, so ghosts and missing
1246
revisions (including the start revisions) are included in the result.
1247
This can save a round trip in LCA style calculation by allowing
1248
convergence to be detected without reading the data for the revision
1249
the convergence occurs on.
1251
:return: A set of revision_ids.
1253
if self._returning != 'next':
1254
# switch to returning the query, not the results.
1255
self._returning = 'next'
1256
self._iterations += 1
1259
if len(self._next_query) == 0:
1260
raise StopIteration()
1261
# We have seen what we're querying at this point as we are returning
1262
# the query, not the results.
1263
self.seen.update(self._next_query)
1264
return self._next_query
1266
def next_with_ghosts(self):
1267
"""Return the next found ancestors, with ghosts split out.
1269
Ancestors are returned in the order they are seen in a breadth-first
1270
traversal. No ancestor will be returned more than once. Ancestors are
1271
returned only after asking for their parents, which allows us to detect
1272
which revisions are ghosts and which are not.
1274
:return: A tuple with (present ancestors, ghost ancestors) sets.
1276
if self._returning != 'next_with_ghosts':
1277
# switch to returning the results, not the current query.
1278
self._returning = 'next_with_ghosts'
1280
if len(self._next_query) == 0:
1281
raise StopIteration()
1283
return self._current_present, self._current_ghosts
1286
"""Advance the search.
1288
Updates self.seen, self._next_query, self._current_present,
1289
self._current_ghosts, self._current_parents and self._iterations.
1291
self._iterations += 1
1292
found, ghosts, next, parents = self._do_query(self._next_query)
1293
self._current_present = found
1294
self._current_ghosts = ghosts
1295
self._next_query = next
1296
self._current_parents = parents
1297
# ghosts are implicit stop points, otherwise the search cannot be
1298
# repeated when ghosts are filled.
1299
self._stopped_keys.update(ghosts)
1301
def _do_query(self, revisions):
1302
"""Query for revisions.
1304
Adds revisions to the seen set.
1306
:param revisions: Revisions to query.
1307
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1308
set(parents_of_found_revisions), dict(found_revisions:parents)).
1310
found_revisions = set()
1311
parents_of_found = set()
1312
# revisions may contain nodes that point to other nodes in revisions:
1313
# we want to filter them out.
1314
self.seen.update(revisions)
1315
parent_map = self._parents_provider.get_parent_map(revisions)
1316
found_revisions.update(parent_map)
1317
for rev_id, parents in parent_map.iteritems():
1320
new_found_parents = [p for p in parents if p not in self.seen]
1321
if new_found_parents:
1322
# Calling set.update() with an empty generator is actually
1324
parents_of_found.update(new_found_parents)
1325
ghost_revisions = revisions - found_revisions
1326
return found_revisions, ghost_revisions, parents_of_found, parent_map
1331
def find_seen_ancestors(self, revisions):
1332
"""Find ancestors of these revisions that have already been seen.
1334
This function generally makes the assumption that querying for the
1335
parents of a node that has already been queried is reasonably cheap.
1336
(eg, not a round trip to a remote host).
1338
# TODO: Often we might ask one searcher for its seen ancestors, and
1339
# then ask another searcher the same question. This can result in
1340
# searching the same revisions repeatedly if the two searchers
1341
# have a lot of overlap.
1342
all_seen = self.seen
1343
pending = set(revisions).intersection(all_seen)
1344
seen_ancestors = set(pending)
1346
if self._returning == 'next':
1347
# self.seen contains what nodes have been returned, not what nodes
1348
# have been queried. We don't want to probe for nodes that haven't
1349
# been searched yet.
1350
not_searched_yet = self._next_query
1352
not_searched_yet = ()
1353
pending.difference_update(not_searched_yet)
1354
get_parent_map = self._parents_provider.get_parent_map
1356
parent_map = get_parent_map(pending)
1358
# We don't care if it is a ghost, since it can't be seen if it is
1360
for parent_ids in parent_map.itervalues():
1361
all_parents.extend(parent_ids)
1362
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1363
seen_ancestors.update(next_pending)
1364
next_pending.difference_update(not_searched_yet)
1365
pending = next_pending
1367
return seen_ancestors
1369
def stop_searching_any(self, revisions):
1371
Remove any of the specified revisions from the search list.
1373
None of the specified revisions are required to be present in the
1376
It is okay to call stop_searching_any() for revisions which were seen
1377
in previous iterations. It is the callers responsibility to call
1378
find_seen_ancestors() to make sure that current search tips that are
1379
ancestors of those revisions are also stopped. All explicitly stopped
1380
revisions will be excluded from the search result's get_keys(), though.
1382
# TODO: does this help performance?
1385
revisions = frozenset(revisions)
1386
if self._returning == 'next':
1387
stopped = self._next_query.intersection(revisions)
1388
self._next_query = self._next_query.difference(revisions)
1390
stopped_present = self._current_present.intersection(revisions)
1391
stopped = stopped_present.union(
1392
self._current_ghosts.intersection(revisions))
1393
self._current_present.difference_update(stopped)
1394
self._current_ghosts.difference_update(stopped)
1395
# stopping 'x' should stop returning parents of 'x', but
1396
# not if 'y' always references those same parents
1397
stop_rev_references = {}
1398
for rev in stopped_present:
1399
for parent_id in self._current_parents[rev]:
1400
if parent_id not in stop_rev_references:
1401
stop_rev_references[parent_id] = 0
1402
stop_rev_references[parent_id] += 1
1403
# if only the stopped revisions reference it, the ref count will be
1405
for parents in self._current_parents.itervalues():
1406
for parent_id in parents:
1408
stop_rev_references[parent_id] -= 1
1411
stop_parents = set()
1412
for rev_id, refs in stop_rev_references.iteritems():
1414
stop_parents.add(rev_id)
1415
self._next_query.difference_update(stop_parents)
1416
self._stopped_keys.update(stopped)
1417
self._stopped_keys.update(revisions)
1420
def start_searching(self, revisions):
1421
"""Add revisions to the search.
1423
The parents of revisions will be returned from the next call to next()
1424
or next_with_ghosts(). If next_with_ghosts was the most recently used
1425
next* call then the return value is the result of looking up the
1426
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1428
revisions = frozenset(revisions)
1429
self._started_keys.update(revisions)
1430
new_revisions = revisions.difference(self.seen)
1431
if self._returning == 'next':
1432
self._next_query.update(new_revisions)
1433
self.seen.update(new_revisions)
1435
# perform a query on revisions
1436
revs, ghosts, query, parents = self._do_query(revisions)
1437
self._stopped_keys.update(ghosts)
1438
self._current_present.update(revs)
1439
self._current_ghosts.update(ghosts)
1440
self._next_query.update(query)
1441
self._current_parents.update(parents)
1445
class SearchResult(object):
1446
"""The result of a breadth first search.
1448
A SearchResult provides the ability to reconstruct the search or access a
1449
set of the keys the search found.
1452
def __init__(self, start_keys, exclude_keys, key_count, keys):
1453
"""Create a SearchResult.
1455
:param start_keys: The keys the search started at.
1456
:param exclude_keys: The keys the search excludes.
1457
:param key_count: The total number of keys (from start to but not
1459
:param keys: The keys the search found. Note that in future we may get
1460
a SearchResult from a smart server, in which case the keys list is
1461
not necessarily immediately available.
1463
self._recipe = ('search', start_keys, exclude_keys, key_count)
1464
self._keys = frozenset(keys)
1466
def get_recipe(self):
1467
"""Return a recipe that can be used to replay this search.
1469
The recipe allows reconstruction of the same results at a later date
1470
without knowing all the found keys. The essential elements are a list
1471
of keys to start and to stop at. In order to give reproducible
1472
results when ghosts are encountered by a search they are automatically
1473
added to the exclude list (or else ghost filling may alter the
1476
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1477
revision_count). To recreate the results of this search, create a
1478
breadth first searcher on the same graph starting at start_keys.
1479
Then call next() (or next_with_ghosts()) repeatedly, and on every
1480
result, call stop_searching_any on any keys from the exclude_keys
1481
set. The revision_count value acts as a trivial cross-check - the
1482
found revisions of the new search should have as many elements as
1483
revision_count. If it does not, then additional revisions have been
1484
ghosted since the search was executed the first time and the second
1490
"""Return the keys found in this search.
1492
:return: A set of keys.
1497
"""Return false if the search lists 1 or more revisions."""
1498
return self._recipe[3] == 0
1500
def refine(self, seen, referenced):
1501
"""Create a new search by refining this search.
1503
:param seen: Revisions that have been satisfied.
1504
:param referenced: Revision references observed while satisfying some
1507
start = self._recipe[1]
1508
exclude = self._recipe[2]
1509
count = self._recipe[3]
1510
keys = self.get_keys()
1511
# New heads = referenced + old heads - seen things - exclude
1512
pending_refs = set(referenced)
1513
pending_refs.update(start)
1514
pending_refs.difference_update(seen)
1515
pending_refs.difference_update(exclude)
1516
# New exclude = old exclude + satisfied heads
1517
seen_heads = start.intersection(seen)
1518
exclude.update(seen_heads)
1519
# keys gets seen removed
1521
# length is reduced by len(seen)
1523
return SearchResult(pending_refs, exclude, count, keys)
1526
class PendingAncestryResult(object):
1527
"""A search result that will reconstruct the ancestry for some graph heads.
1529
Unlike SearchResult, this doesn't hold the complete search result in
1530
memory, it just holds a description of how to generate it.
1533
def __init__(self, heads, repo):
1536
:param heads: an iterable of graph heads.
1537
:param repo: a repository to use to generate the ancestry for the given
1540
self.heads = frozenset(heads)
1543
def get_recipe(self):
1544
"""Return a recipe that can be used to replay this search.
1546
The recipe allows reconstruction of the same results at a later date.
1548
:seealso SearchResult.get_recipe:
1550
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1551
To recreate this result, create a PendingAncestryResult with the
1554
return ('proxy-search', self.heads, set(), -1)
1557
"""See SearchResult.get_keys.
1559
Returns all the keys for the ancestry of the heads, excluding
1562
return self._get_keys(self.repo.get_graph())
1564
def _get_keys(self, graph):
1565
NULL_REVISION = revision.NULL_REVISION
1566
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1567
if key != NULL_REVISION and parents is not None]
1571
"""Return false if the search lists 1 or more revisions."""
1572
if revision.NULL_REVISION in self.heads:
1573
return len(self.heads) == 1
1575
return len(self.heads) == 0
1577
def refine(self, seen, referenced):
1578
"""Create a new search by refining this search.
1580
:param seen: Revisions that have been satisfied.
1581
:param referenced: Revision references observed while satisfying some
1584
referenced = self.heads.union(referenced)
1585
return PendingAncestryResult(referenced - seen, self.repo)
1588
def collapse_linear_regions(parent_map):
1589
"""Collapse regions of the graph that are 'linear'.
1595
can be collapsed by removing B and getting::
1599
:param parent_map: A dictionary mapping children to their parents
1600
:return: Another dictionary with 'linear' chains collapsed
1602
# Note: this isn't a strictly minimal collapse. For example:
1610
# Will not have 'D' removed, even though 'E' could fit. Also:
1616
# A and C are both kept because they are edges of the graph. We *could* get
1617
# rid of A if we wanted.
1625
# Will not have any nodes removed, even though you do have an
1626
# 'uninteresting' linear D->B and E->C
1628
for child, parents in parent_map.iteritems():
1629
children.setdefault(child, [])
1631
children.setdefault(p, []).append(child)
1633
orig_children = dict(children)
1635
result = dict(parent_map)
1636
for node in parent_map:
1637
parents = result[node]
1638
if len(parents) == 1:
1639
parent_children = children[parents[0]]
1640
if len(parent_children) != 1:
1641
# This is not the only child
1643
node_children = children[node]
1644
if len(node_children) != 1:
1646
child_parents = result.get(node_children[0], None)
1647
if len(child_parents) != 1:
1648
# This is not its only parent
1650
# The child of this node only points at it, and the parent only has
1651
# this as a child. remove this node, and join the others together
1652
result[node_children[0]] = parents
1653
children[parents[0]] = node_children
1661
_counters = [0,0,0,0,0,0,0]
1663
from bzrlib._known_graph_pyx import KnownGraph
1664
except ImportError, e:
1665
osutils.failed_to_load_extension(e)
1666
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
