1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
28
STEP_UNIQUE_SEARCHER_EVERY = 5
30
# DIAGRAM of terminology
40
# In this diagram, relative to G and H:
41
# A, B, C, D, E are common ancestors.
42
# C, D and E are border ancestors, because each has a non-common descendant.
43
# D and E are least common ancestors because none of their descendants are
45
# C is not a least common ancestor because its descendant, E, is a common
48
# The find_unique_lca algorithm will pick A in two steps:
49
# 1. find_lca('G', 'H') => ['D', 'E']
50
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
53
class DictParentsProvider(object):
54
"""A parents provider for Graph objects."""
56
def __init__(self, ancestry):
57
self.ancestry = ancestry
60
return 'DictParentsProvider(%r)' % self.ancestry
62
def get_parent_map(self, keys):
63
"""See _StackedParentsProvider.get_parent_map"""
64
ancestry = self.ancestry
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
68
class _StackedParentsProvider(object):
70
def __init__(self, parent_providers):
71
self._parent_providers = parent_providers
74
return "_StackedParentsProvider(%r)" % self._parent_providers
76
def get_parent_map(self, keys):
77
"""Get a mapping of keys => parents
79
A dictionary is returned with an entry for each key present in this
80
source. If this source doesn't have information about a key, it should
83
[NULL_REVISION] is used as the parent of the first user-committed
84
revision. Its parent list is empty.
86
:param keys: An iterable returning keys to check (eg revision_ids)
87
:return: A dictionary mapping each key to its parents
91
for parents_provider in self._parent_providers:
92
new_found = parents_provider.get_parent_map(remaining)
93
found.update(new_found)
94
remaining.difference_update(new_found)
100
class CachingParentsProvider(object):
101
"""A parents provider which will cache the revision => parents as a dict.
103
This is useful for providers which have an expensive look up.
105
Either a ParentsProvider or a get_parent_map-like callback may be
106
supplied. If it provides extra un-asked-for parents, they will be cached,
107
but filtered out of get_parent_map.
109
The cache is enabled by default, but may be disabled and re-enabled.
111
def __init__(self, parent_provider=None, get_parent_map=None):
114
:param parent_provider: The ParentProvider to use. It or
115
get_parent_map must be supplied.
116
:param get_parent_map: The get_parent_map callback to use. It or
117
parent_provider must be supplied.
119
self._real_provider = parent_provider
120
if get_parent_map is None:
121
self._get_parent_map = self._real_provider.get_parent_map
123
self._get_parent_map = get_parent_map
125
self.enable_cache(True)
128
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
130
def enable_cache(self, cache_misses=True):
132
if self._cache is not None:
133
raise AssertionError('Cache enabled when already enabled.')
135
self._cache_misses = cache_misses
136
self.missing_keys = set()
138
def disable_cache(self):
139
"""Disable and clear the cache."""
141
self._cache_misses = None
142
self.missing_keys = set()
144
def get_cached_map(self):
145
"""Return any cached get_parent_map values."""
146
if self._cache is None:
148
return dict(self._cache)
150
def get_parent_map(self, keys):
151
"""See _StackedParentsProvider.get_parent_map."""
154
cache = self._get_parent_map(keys)
156
needed_revisions = set(key for key in keys if key not in cache)
157
# Do not ask for negatively cached keys
158
needed_revisions.difference_update(self.missing_keys)
160
parent_map = self._get_parent_map(needed_revisions)
161
cache.update(parent_map)
162
if self._cache_misses:
163
for key in needed_revisions:
164
if key not in parent_map:
165
self.note_missing_key(key)
168
value = cache.get(key)
169
if value is not None:
173
def note_missing_key(self, key):
174
"""Note that key is a missing key."""
175
if self._cache_misses:
176
self.missing_keys.add(key)
180
"""Provide incremental access to revision graphs.
182
This is the generic implementation; it is intended to be subclassed to
183
specialize it for other repository types.
186
def __init__(self, parents_provider):
187
"""Construct a Graph that uses several graphs as its input
189
This should not normally be invoked directly, because there may be
190
specialized implementations for particular repository types. See
191
Repository.get_graph().
193
:param parents_provider: An object providing a get_parent_map call
194
conforming to the behavior of
195
StackedParentsProvider.get_parent_map.
197
if getattr(parents_provider, 'get_parents', None) is not None:
198
self.get_parents = parents_provider.get_parents
199
if getattr(parents_provider, 'get_parent_map', None) is not None:
200
self.get_parent_map = parents_provider.get_parent_map
201
self._parents_provider = parents_provider
204
return 'Graph(%r)' % self._parents_provider
206
def find_lca(self, *revisions):
207
"""Determine the lowest common ancestors of the provided revisions
209
A lowest common ancestor is a common ancestor none of whose
210
descendants are common ancestors. In graphs, unlike trees, there may
211
be multiple lowest common ancestors.
213
This algorithm has two phases. Phase 1 identifies border ancestors,
214
and phase 2 filters border ancestors to determine lowest common
217
In phase 1, border ancestors are identified, using a breadth-first
218
search starting at the bottom of the graph. Searches are stopped
219
whenever a node or one of its descendants is determined to be common
221
In phase 2, the border ancestors are filtered to find the least
222
common ancestors. This is done by searching the ancestries of each
225
Phase 2 is perfomed on the principle that a border ancestor that is
226
not an ancestor of any other border ancestor is a least common
229
Searches are stopped when they find a node that is determined to be a
230
common ancestor of all border ancestors, because this shows that it
231
cannot be a descendant of any border ancestor.
233
The scaling of this operation should be proportional to
234
1. The number of uncommon ancestors
235
2. The number of border ancestors
236
3. The length of the shortest path between a border ancestor and an
237
ancestor of all border ancestors.
239
border_common, common, sides = self._find_border_ancestors(revisions)
240
# We may have common ancestors that can be reached from each other.
241
# - ask for the heads of them to filter it down to only ones that
242
# cannot be reached from each other - phase 2.
243
return self.heads(border_common)
245
def find_difference(self, left_revision, right_revision):
246
"""Determine the graph difference between two revisions"""
247
border, common, searchers = self._find_border_ancestors(
248
[left_revision, right_revision])
249
self._search_for_extra_common(common, searchers)
250
left = searchers[0].seen
251
right = searchers[1].seen
252
return (left.difference(right), right.difference(left))
254
def find_distance_to_null(self, target_revision_id, known_revision_ids):
255
"""Find the left-hand distance to the NULL_REVISION.
257
(This can also be considered the revno of a branch at
260
:param target_revision_id: A revision_id which we would like to know
262
:param known_revision_ids: [(revision_id, revno)] A list of known
263
revno, revision_id tuples. We'll use this to seed the search.
265
# Map from revision_ids to a known value for their revno
266
known_revnos = dict(known_revision_ids)
267
cur_tip = target_revision_id
269
NULL_REVISION = revision.NULL_REVISION
270
known_revnos[NULL_REVISION] = 0
272
searching_known_tips = list(known_revnos.keys())
274
unknown_searched = {}
276
while cur_tip not in known_revnos:
277
unknown_searched[cur_tip] = num_steps
279
to_search = set([cur_tip])
280
to_search.update(searching_known_tips)
281
parent_map = self.get_parent_map(to_search)
282
parents = parent_map.get(cur_tip, None)
283
if not parents: # An empty list or None is a ghost
284
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
288
for revision_id in searching_known_tips:
289
parents = parent_map.get(revision_id, None)
293
next_revno = known_revnos[revision_id] - 1
294
if next in unknown_searched:
295
# We have enough information to return a value right now
296
return next_revno + unknown_searched[next]
297
if next in known_revnos:
299
known_revnos[next] = next_revno
300
next_known_tips.append(next)
301
searching_known_tips = next_known_tips
303
# We reached a known revision, so just add in how many steps it took to
305
return known_revnos[cur_tip] + num_steps
307
def find_lefthand_distances(self, keys):
308
"""Find the distance to null for all the keys in keys.
310
:param keys: keys to lookup.
311
:return: A dict key->distance for all of keys.
313
# Optimisable by concurrent searching, but a random spread should get
314
# some sort of hit rate.
321
(key, self.find_distance_to_null(key, known_revnos)))
322
except errors.GhostRevisionsHaveNoRevno:
325
known_revnos.append((key, -1))
326
return dict(known_revnos)
328
def find_unique_ancestors(self, unique_revision, common_revisions):
329
"""Find the unique ancestors for a revision versus others.
331
This returns the ancestry of unique_revision, excluding all revisions
332
in the ancestry of common_revisions. If unique_revision is in the
333
ancestry, then the empty set will be returned.
335
:param unique_revision: The revision_id whose ancestry we are
337
XXX: Would this API be better if we allowed multiple revisions on
339
:param common_revisions: Revision_ids of ancestries to exclude.
340
:return: A set of revisions in the ancestry of unique_revision
342
if unique_revision in common_revisions:
345
# Algorithm description
346
# 1) Walk backwards from the unique node and all common nodes.
347
# 2) When a node is seen by both sides, stop searching it in the unique
348
# walker, include it in the common walker.
349
# 3) Stop searching when there are no nodes left for the unique walker.
350
# At this point, you have a maximal set of unique nodes. Some of
351
# them may actually be common, and you haven't reached them yet.
352
# 4) Start new searchers for the unique nodes, seeded with the
353
# information you have so far.
354
# 5) Continue searching, stopping the common searches when the search
355
# tip is an ancestor of all unique nodes.
356
# 6) Aggregate together unique searchers when they are searching the
357
# same tips. When all unique searchers are searching the same node,
358
# stop move it to a single 'all_unique_searcher'.
359
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
360
# Most of the time this produces very little important information.
361
# So don't step it as quickly as the other searchers.
362
# 8) Search is done when all common searchers have completed.
364
unique_searcher, common_searcher = self._find_initial_unique_nodes(
365
[unique_revision], common_revisions)
367
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
371
(all_unique_searcher,
372
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
373
unique_searcher, common_searcher)
375
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
376
unique_tip_searchers, common_searcher)
377
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
378
if 'graph' in debug.debug_flags:
379
trace.mutter('Found %d truly unique nodes out of %d',
380
len(true_unique_nodes), len(unique_nodes))
381
return true_unique_nodes
383
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
384
"""Steps 1-3 of find_unique_ancestors.
386
Find the maximal set of unique nodes. Some of these might actually
387
still be common, but we are sure that there are no other unique nodes.
389
:return: (unique_searcher, common_searcher)
392
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
393
# we know that unique_revisions aren't in common_revisions, so skip
395
unique_searcher.next()
396
common_searcher = self._make_breadth_first_searcher(common_revisions)
398
# As long as we are still finding unique nodes, keep searching
399
while unique_searcher._next_query:
400
next_unique_nodes = set(unique_searcher.step())
401
next_common_nodes = set(common_searcher.step())
403
# Check if either searcher encounters new nodes seen by the other
405
unique_are_common_nodes = next_unique_nodes.intersection(
406
common_searcher.seen)
407
unique_are_common_nodes.update(
408
next_common_nodes.intersection(unique_searcher.seen))
409
if unique_are_common_nodes:
410
ancestors = unique_searcher.find_seen_ancestors(
411
unique_are_common_nodes)
412
# TODO: This is a bit overboard, we only really care about
413
# the ancestors of the tips because the rest we
414
# already know. This is *correct* but causes us to
415
# search too much ancestry.
416
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
417
unique_searcher.stop_searching_any(ancestors)
418
common_searcher.start_searching(ancestors)
420
return unique_searcher, common_searcher
422
def _make_unique_searchers(self, unique_nodes, unique_searcher,
424
"""Create a searcher for all the unique search tips (step 4).
426
As a side effect, the common_searcher will stop searching any nodes
427
that are ancestors of the unique searcher tips.
429
:return: (all_unique_searcher, unique_tip_searchers)
431
unique_tips = self._remove_simple_descendants(unique_nodes,
432
self.get_parent_map(unique_nodes))
434
if len(unique_tips) == 1:
435
unique_tip_searchers = []
436
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
438
unique_tip_searchers = []
439
for tip in unique_tips:
440
revs_to_search = unique_searcher.find_seen_ancestors([tip])
441
revs_to_search.update(
442
common_searcher.find_seen_ancestors(revs_to_search))
443
searcher = self._make_breadth_first_searcher(revs_to_search)
444
# We don't care about the starting nodes.
445
searcher._label = tip
447
unique_tip_searchers.append(searcher)
449
ancestor_all_unique = None
450
for searcher in unique_tip_searchers:
451
if ancestor_all_unique is None:
452
ancestor_all_unique = set(searcher.seen)
454
ancestor_all_unique = ancestor_all_unique.intersection(
456
# Collapse all the common nodes into a single searcher
457
all_unique_searcher = self._make_breadth_first_searcher(
459
if ancestor_all_unique:
460
# We've seen these nodes in all the searchers, so we'll just go to
462
all_unique_searcher.step()
464
# Stop any search tips that are already known as ancestors of the
466
stopped_common = common_searcher.stop_searching_any(
467
common_searcher.find_seen_ancestors(ancestor_all_unique))
470
for searcher in unique_tip_searchers:
471
total_stopped += len(searcher.stop_searching_any(
472
searcher.find_seen_ancestors(ancestor_all_unique)))
473
if 'graph' in debug.debug_flags:
474
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
475
' (%d stopped search tips, %d common ancestors'
476
' (%d stopped common)',
477
len(unique_nodes), len(unique_tip_searchers),
478
total_stopped, len(ancestor_all_unique),
480
return all_unique_searcher, unique_tip_searchers
482
def _step_unique_and_common_searchers(self, common_searcher,
483
unique_tip_searchers,
485
"""Step all the searchers"""
486
newly_seen_common = set(common_searcher.step())
487
newly_seen_unique = set()
488
for searcher in unique_tip_searchers:
489
next = set(searcher.step())
490
next.update(unique_searcher.find_seen_ancestors(next))
491
next.update(common_searcher.find_seen_ancestors(next))
492
for alt_searcher in unique_tip_searchers:
493
if alt_searcher is searcher:
495
next.update(alt_searcher.find_seen_ancestors(next))
496
searcher.start_searching(next)
497
newly_seen_unique.update(next)
498
return newly_seen_common, newly_seen_unique
500
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
502
newly_seen_unique, step_all_unique):
503
"""Find nodes that are common to all unique_tip_searchers.
505
If it is time, step the all_unique_searcher, and add its nodes to the
508
common_to_all_unique_nodes = newly_seen_unique.copy()
509
for searcher in unique_tip_searchers:
510
common_to_all_unique_nodes.intersection_update(searcher.seen)
511
common_to_all_unique_nodes.intersection_update(
512
all_unique_searcher.seen)
513
# Step all-unique less frequently than the other searchers.
514
# In the common case, we don't need to spider out far here, so
515
# avoid doing extra work.
517
tstart = time.clock()
518
nodes = all_unique_searcher.step()
519
common_to_all_unique_nodes.update(nodes)
520
if 'graph' in debug.debug_flags:
521
tdelta = time.clock() - tstart
522
trace.mutter('all_unique_searcher step() took %.3fs'
523
'for %d nodes (%d total), iteration: %s',
524
tdelta, len(nodes), len(all_unique_searcher.seen),
525
all_unique_searcher._iterations)
526
return common_to_all_unique_nodes
528
def _collapse_unique_searchers(self, unique_tip_searchers,
529
common_to_all_unique_nodes):
530
"""Combine searchers that are searching the same tips.
532
When two searchers are searching the same tips, we can stop one of the
533
searchers. We also know that the maximal set of common ancestors is the
534
intersection of the two original searchers.
536
:return: A list of searchers that are searching unique nodes.
538
# Filter out searchers that don't actually search different
539
# nodes. We already have the ancestry intersection for them
540
unique_search_tips = {}
541
for searcher in unique_tip_searchers:
542
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
543
will_search_set = frozenset(searcher._next_query)
544
if not will_search_set:
545
if 'graph' in debug.debug_flags:
546
trace.mutter('Unique searcher %s was stopped.'
547
' (%s iterations) %d nodes stopped',
549
searcher._iterations,
551
elif will_search_set not in unique_search_tips:
552
# This searcher is searching a unique set of nodes, let it
553
unique_search_tips[will_search_set] = [searcher]
555
unique_search_tips[will_search_set].append(searcher)
556
# TODO: it might be possible to collapse searchers faster when they
557
# only have *some* search tips in common.
558
next_unique_searchers = []
559
for searchers in unique_search_tips.itervalues():
560
if len(searchers) == 1:
561
# Searching unique tips, go for it
562
next_unique_searchers.append(searchers[0])
564
# These searchers have started searching the same tips, we
565
# don't need them to cover the same ground. The
566
# intersection of their ancestry won't change, so create a
567
# new searcher, combining their histories.
568
next_searcher = searchers[0]
569
for searcher in searchers[1:]:
570
next_searcher.seen.intersection_update(searcher.seen)
571
if 'graph' in debug.debug_flags:
572
trace.mutter('Combining %d searchers into a single'
573
' searcher searching %d nodes with'
576
len(next_searcher._next_query),
577
len(next_searcher.seen))
578
next_unique_searchers.append(next_searcher)
579
return next_unique_searchers
581
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
582
unique_tip_searchers, common_searcher):
583
"""Steps 5-8 of find_unique_ancestors.
585
This function returns when common_searcher has stopped searching for
588
# We step the ancestor_all_unique searcher only every
589
# STEP_UNIQUE_SEARCHER_EVERY steps.
590
step_all_unique_counter = 0
591
# While we still have common nodes to search
592
while common_searcher._next_query:
594
newly_seen_unique) = self._step_unique_and_common_searchers(
595
common_searcher, unique_tip_searchers, unique_searcher)
596
# These nodes are common ancestors of all unique nodes
597
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
598
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
599
step_all_unique_counter==0)
600
step_all_unique_counter = ((step_all_unique_counter + 1)
601
% STEP_UNIQUE_SEARCHER_EVERY)
603
if newly_seen_common:
604
# If a 'common' node is an ancestor of all unique searchers, we
605
# can stop searching it.
606
common_searcher.stop_searching_any(
607
all_unique_searcher.seen.intersection(newly_seen_common))
608
if common_to_all_unique_nodes:
609
common_to_all_unique_nodes.update(
610
common_searcher.find_seen_ancestors(
611
common_to_all_unique_nodes))
612
# The all_unique searcher can start searching the common nodes
613
# but everyone else can stop.
614
# This is the sort of thing where we would like to not have it
615
# start_searching all of the nodes, but only mark all of them
616
# as seen, and have it search only the actual tips. Otherwise
617
# it is another get_parent_map() traversal for it to figure out
618
# what we already should know.
619
all_unique_searcher.start_searching(common_to_all_unique_nodes)
620
common_searcher.stop_searching_any(common_to_all_unique_nodes)
622
next_unique_searchers = self._collapse_unique_searchers(
623
unique_tip_searchers, common_to_all_unique_nodes)
624
if len(unique_tip_searchers) != len(next_unique_searchers):
625
if 'graph' in debug.debug_flags:
626
trace.mutter('Collapsed %d unique searchers => %d'
628
len(unique_tip_searchers),
629
len(next_unique_searchers),
630
all_unique_searcher._iterations)
631
unique_tip_searchers = next_unique_searchers
633
def get_parent_map(self, revisions):
634
"""Get a map of key:parent_list for revisions.
636
This implementation delegates to get_parents, for old parent_providers
637
that do not supply get_parent_map.
640
for rev, parents in self.get_parents(revisions):
641
if parents is not None:
642
result[rev] = parents
645
def _make_breadth_first_searcher(self, revisions):
646
return _BreadthFirstSearcher(revisions, self)
648
def _find_border_ancestors(self, revisions):
649
"""Find common ancestors with at least one uncommon descendant.
651
Border ancestors are identified using a breadth-first
652
search starting at the bottom of the graph. Searches are stopped
653
whenever a node or one of its descendants is determined to be common.
655
This will scale with the number of uncommon ancestors.
657
As well as the border ancestors, a set of seen common ancestors and a
658
list of sets of seen ancestors for each input revision is returned.
659
This allows calculation of graph difference from the results of this
662
if None in revisions:
663
raise errors.InvalidRevisionId(None, self)
664
common_ancestors = set()
665
searchers = [self._make_breadth_first_searcher([r])
667
active_searchers = searchers[:]
668
border_ancestors = set()
672
for searcher in searchers:
673
new_ancestors = searcher.step()
675
newly_seen.update(new_ancestors)
677
for revision in newly_seen:
678
if revision in common_ancestors:
679
# Not a border ancestor because it was seen as common
681
new_common.add(revision)
683
for searcher in searchers:
684
if revision not in searcher.seen:
687
# This is a border because it is a first common that we see
688
# after walking for a while.
689
border_ancestors.add(revision)
690
new_common.add(revision)
692
for searcher in searchers:
693
new_common.update(searcher.find_seen_ancestors(new_common))
694
for searcher in searchers:
695
searcher.start_searching(new_common)
696
common_ancestors.update(new_common)
698
# Figure out what the searchers will be searching next, and if
699
# there is only 1 set being searched, then we are done searching,
700
# since all searchers would have to be searching the same data,
701
# thus it *must* be in common.
702
unique_search_sets = set()
703
for searcher in searchers:
704
will_search_set = frozenset(searcher._next_query)
705
if will_search_set not in unique_search_sets:
706
# This searcher is searching a unique set of nodes, let it
707
unique_search_sets.add(will_search_set)
709
if len(unique_search_sets) == 1:
710
nodes = unique_search_sets.pop()
711
uncommon_nodes = nodes.difference(common_ancestors)
713
raise AssertionError("Somehow we ended up converging"
714
" without actually marking them as"
717
"\nuncommon_nodes: %s"
718
% (revisions, uncommon_nodes))
720
return border_ancestors, common_ancestors, searchers
722
def heads(self, keys):
723
"""Return the heads from amongst keys.
725
This is done by searching the ancestries of each key. Any key that is
726
reachable from another key is not returned; all the others are.
728
This operation scales with the relative depth between any two keys. If
729
any two keys are completely disconnected all ancestry of both sides
732
:param keys: An iterable of keys.
733
:return: A set of the heads. Note that as a set there is no ordering
734
information. Callers will need to filter their input to create
735
order if they need it.
737
candidate_heads = set(keys)
738
if revision.NULL_REVISION in candidate_heads:
739
# NULL_REVISION is only a head if it is the only entry
740
candidate_heads.remove(revision.NULL_REVISION)
741
if not candidate_heads:
742
return set([revision.NULL_REVISION])
743
if len(candidate_heads) < 2:
744
return candidate_heads
745
searchers = dict((c, self._make_breadth_first_searcher([c]))
746
for c in candidate_heads)
747
active_searchers = dict(searchers)
748
# skip over the actual candidate for each searcher
749
for searcher in active_searchers.itervalues():
751
# The common walker finds nodes that are common to two or more of the
752
# input keys, so that we don't access all history when a currently
753
# uncommon search point actually meets up with something behind a
754
# common search point. Common search points do not keep searches
755
# active; they just allow us to make searches inactive without
756
# accessing all history.
757
common_walker = self._make_breadth_first_searcher([])
758
while len(active_searchers) > 0:
763
except StopIteration:
764
# No common points being searched at this time.
766
for candidate in active_searchers.keys():
768
searcher = active_searchers[candidate]
770
# rare case: we deleted candidate in a previous iteration
771
# through this for loop, because it was determined to be
772
# a descendant of another candidate.
775
ancestors.update(searcher.next())
776
except StopIteration:
777
del active_searchers[candidate]
779
# process found nodes
781
for ancestor in ancestors:
782
if ancestor in candidate_heads:
783
candidate_heads.remove(ancestor)
784
del searchers[ancestor]
785
if ancestor in active_searchers:
786
del active_searchers[ancestor]
787
# it may meet up with a known common node
788
if ancestor in common_walker.seen:
789
# some searcher has encountered our known common nodes:
791
ancestor_set = set([ancestor])
792
for searcher in searchers.itervalues():
793
searcher.stop_searching_any(ancestor_set)
795
# or it may have been just reached by all the searchers:
796
for searcher in searchers.itervalues():
797
if ancestor not in searcher.seen:
800
# The final active searcher has just reached this node,
801
# making it be known as a descendant of all candidates,
802
# so we can stop searching it, and any seen ancestors
803
new_common.add(ancestor)
804
for searcher in searchers.itervalues():
806
searcher.find_seen_ancestors([ancestor])
807
searcher.stop_searching_any(seen_ancestors)
808
common_walker.start_searching(new_common)
809
return candidate_heads
811
def find_merge_order(self, tip_revision_id, lca_revision_ids):
812
"""Find the order that each revision was merged into tip.
814
This basically just walks backwards with a stack, and walks left-first
815
until it finds a node to stop.
817
if len(lca_revision_ids) == 1:
818
return list(lca_revision_ids)
819
looking_for = set(lca_revision_ids)
820
# TODO: Is there a way we could do this "faster" by batching up the
821
# get_parent_map requests?
822
# TODO: Should we also be culling the ancestry search right away? We
823
# could add looking_for to the "stop" list, and walk their
824
# ancestry in batched mode. The flip side is it might mean we walk a
825
# lot of "stop" nodes, rather than only the minimum.
826
# Then again, without it we may trace back into ancestry we could have
828
stack = [tip_revision_id]
831
while stack and looking_for:
834
if next in looking_for:
836
looking_for.remove(next)
837
if len(looking_for) == 1:
838
found.append(looking_for.pop())
841
parent_ids = self.get_parent_map([next]).get(next, None)
842
if not parent_ids: # Ghost, nothing to search here
844
for parent_id in reversed(parent_ids):
845
# TODO: (performance) We see the parent at this point, but we
846
# wait to mark it until later to make sure we get left
847
# parents before right parents. However, instead of
848
# waiting until we have traversed enough parents, we
849
# could instead note that we've found it, and once all
850
# parents are in the stack, just reverse iterate the
852
if parent_id not in stop:
853
# this will need to be searched
854
stack.append(parent_id)
858
def find_unique_lca(self, left_revision, right_revision,
860
"""Find a unique LCA.
862
Find lowest common ancestors. If there is no unique common
863
ancestor, find the lowest common ancestors of those ancestors.
865
Iteration stops when a unique lowest common ancestor is found.
866
The graph origin is necessarily a unique lowest common ancestor.
868
Note that None is not an acceptable substitute for NULL_REVISION.
869
in the input for this method.
871
:param count_steps: If True, the return value will be a tuple of
872
(unique_lca, steps) where steps is the number of times that
873
find_lca was run. If False, only unique_lca is returned.
875
revisions = [left_revision, right_revision]
879
lca = self.find_lca(*revisions)
887
raise errors.NoCommonAncestor(left_revision, right_revision)
890
def iter_ancestry(self, revision_ids):
891
"""Iterate the ancestry of this revision.
893
:param revision_ids: Nodes to start the search
894
:return: Yield tuples mapping a revision_id to its parents for the
895
ancestry of revision_id.
896
Ghosts will be returned with None as their parents, and nodes
897
with no parents will have NULL_REVISION as their only parent. (As
898
defined by get_parent_map.)
899
There will also be a node for (NULL_REVISION, ())
901
pending = set(revision_ids)
904
processed.update(pending)
905
next_map = self.get_parent_map(pending)
907
for item in next_map.iteritems():
909
next_pending.update(p for p in item[1] if p not in processed)
910
ghosts = pending.difference(next_map)
913
pending = next_pending
915
def iter_topo_order(self, revisions):
916
"""Iterate through the input revisions in topological order.
918
This sorting only ensures that parents come before their children.
919
An ancestor may sort after a descendant if the relationship is not
920
visible in the supplied list of revisions.
922
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
923
return sorter.iter_topo_order()
925
def is_ancestor(self, candidate_ancestor, candidate_descendant):
926
"""Determine whether a revision is an ancestor of another.
928
We answer this using heads() as heads() has the logic to perform the
929
smallest number of parent lookups to determine the ancestral
930
relationship between N revisions.
932
return set([candidate_descendant]) == self.heads(
933
[candidate_ancestor, candidate_descendant])
935
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
936
"""Determine whether a revision is between two others.
938
returns true if and only if:
939
lower_bound_revid <= revid <= upper_bound_revid
941
return ((upper_bound_revid is None or
942
self.is_ancestor(revid, upper_bound_revid)) and
943
(lower_bound_revid is None or
944
self.is_ancestor(lower_bound_revid, revid)))
946
def _search_for_extra_common(self, common, searchers):
947
"""Make sure that unique nodes are genuinely unique.
949
After _find_border_ancestors, all nodes marked "common" are indeed
950
common. Some of the nodes considered unique are not, due to history
951
shortcuts stopping the searches early.
953
We know that we have searched enough when all common search tips are
954
descended from all unique (uncommon) nodes because we know that a node
955
cannot be an ancestor of its own ancestor.
957
:param common: A set of common nodes
958
:param searchers: The searchers returned from _find_border_ancestors
962
# A) The passed in searchers should all be on the same tips, thus
963
# they should be considered the "common" searchers.
964
# B) We find the difference between the searchers, these are the
965
# "unique" nodes for each side.
966
# C) We do a quick culling so that we only start searching from the
967
# more interesting unique nodes. (A unique ancestor is more
968
# interesting than any of its children.)
969
# D) We start searching for ancestors common to all unique nodes.
970
# E) We have the common searchers stop searching any ancestors of
972
# F) When there are no more common search tips, we stop
974
# TODO: We need a way to remove unique_searchers when they overlap with
975
# other unique searchers.
976
if len(searchers) != 2:
977
raise NotImplementedError(
978
"Algorithm not yet implemented for > 2 searchers")
979
common_searchers = searchers
980
left_searcher = searchers[0]
981
right_searcher = searchers[1]
982
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
983
if not unique: # No unique nodes, nothing to do
985
total_unique = len(unique)
986
unique = self._remove_simple_descendants(unique,
987
self.get_parent_map(unique))
988
simple_unique = len(unique)
990
unique_searchers = []
991
for revision_id in unique:
992
if revision_id in left_searcher.seen:
993
parent_searcher = left_searcher
995
parent_searcher = right_searcher
996
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
997
if not revs_to_search: # XXX: This shouldn't be possible
998
revs_to_search = [revision_id]
999
searcher = self._make_breadth_first_searcher(revs_to_search)
1000
# We don't care about the starting nodes.
1002
unique_searchers.append(searcher)
1004
# possible todo: aggregate the common searchers into a single common
1005
# searcher, just make sure that we include the nodes into the .seen
1006
# properties of the original searchers
1008
ancestor_all_unique = None
1009
for searcher in unique_searchers:
1010
if ancestor_all_unique is None:
1011
ancestor_all_unique = set(searcher.seen)
1013
ancestor_all_unique = ancestor_all_unique.intersection(
1016
trace.mutter('Started %s unique searchers for %s unique revisions',
1017
simple_unique, total_unique)
1019
while True: # If we have no more nodes we have nothing to do
1020
newly_seen_common = set()
1021
for searcher in common_searchers:
1022
newly_seen_common.update(searcher.step())
1023
newly_seen_unique = set()
1024
for searcher in unique_searchers:
1025
newly_seen_unique.update(searcher.step())
1026
new_common_unique = set()
1027
for revision in newly_seen_unique:
1028
for searcher in unique_searchers:
1029
if revision not in searcher.seen:
1032
# This is a border because it is a first common that we see
1033
# after walking for a while.
1034
new_common_unique.add(revision)
1035
if newly_seen_common:
1036
# These are nodes descended from one of the 'common' searchers.
1037
# Make sure all searchers are on the same page
1038
for searcher in common_searchers:
1039
newly_seen_common.update(
1040
searcher.find_seen_ancestors(newly_seen_common))
1041
# We start searching the whole ancestry. It is a bit wasteful,
1042
# though. We really just want to mark all of these nodes as
1043
# 'seen' and then start just the tips. However, it requires a
1044
# get_parent_map() call to figure out the tips anyway, and all
1045
# redundant requests should be fairly fast.
1046
for searcher in common_searchers:
1047
searcher.start_searching(newly_seen_common)
1049
# If a 'common' node is an ancestor of all unique searchers, we
1050
# can stop searching it.
1051
stop_searching_common = ancestor_all_unique.intersection(
1053
if stop_searching_common:
1054
for searcher in common_searchers:
1055
searcher.stop_searching_any(stop_searching_common)
1056
if new_common_unique:
1057
# We found some ancestors that are common
1058
for searcher in unique_searchers:
1059
new_common_unique.update(
1060
searcher.find_seen_ancestors(new_common_unique))
1061
# Since these are common, we can grab another set of ancestors
1063
for searcher in common_searchers:
1064
new_common_unique.update(
1065
searcher.find_seen_ancestors(new_common_unique))
1067
# We can tell all of the unique searchers to start at these
1068
# nodes, and tell all of the common searchers to *stop*
1069
# searching these nodes
1070
for searcher in unique_searchers:
1071
searcher.start_searching(new_common_unique)
1072
for searcher in common_searchers:
1073
searcher.stop_searching_any(new_common_unique)
1074
ancestor_all_unique.update(new_common_unique)
1076
# Filter out searchers that don't actually search different
1077
# nodes. We already have the ancestry intersection for them
1078
next_unique_searchers = []
1079
unique_search_sets = set()
1080
for searcher in unique_searchers:
1081
will_search_set = frozenset(searcher._next_query)
1082
if will_search_set not in unique_search_sets:
1083
# This searcher is searching a unique set of nodes, let it
1084
unique_search_sets.add(will_search_set)
1085
next_unique_searchers.append(searcher)
1086
unique_searchers = next_unique_searchers
1087
for searcher in common_searchers:
1088
if searcher._next_query:
1091
# All common searcher have stopped searching
1094
def _remove_simple_descendants(self, revisions, parent_map):
1095
"""remove revisions which are children of other ones in the set
1097
This doesn't do any graph searching, it just checks the immediate
1098
parent_map to find if there are any children which can be removed.
1100
:param revisions: A set of revision_ids
1101
:return: A set of revision_ids with the children removed
1103
simple_ancestors = revisions.copy()
1104
# TODO: jam 20071214 we *could* restrict it to searching only the
1105
# parent_map of revisions already present in 'revisions', but
1106
# considering the general use case, I think this is actually
1109
# This is the same as the following loop. I don't know that it is any
1111
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1112
## if p_ids is not None and revisions.intersection(p_ids))
1113
## return simple_ancestors
1115
# Yet Another Way, invert the parent map (which can be cached)
1117
## for revision_id, parent_ids in parent_map.iteritems():
1118
## for p_id in parent_ids:
1119
## descendants.setdefault(p_id, []).append(revision_id)
1120
## for revision in revisions.intersection(descendants):
1121
## simple_ancestors.difference_update(descendants[revision])
1122
## return simple_ancestors
1123
for revision, parent_ids in parent_map.iteritems():
1124
if parent_ids is None:
1126
for parent_id in parent_ids:
1127
if parent_id in revisions:
1128
# This node has a parent present in the set, so we can
1130
simple_ancestors.discard(revision)
1132
return simple_ancestors
1135
class HeadsCache(object):
1136
"""A cache of results for graph heads calls."""
1138
def __init__(self, graph):
1142
def heads(self, keys):
1143
"""Return the heads of keys.
1145
This matches the API of Graph.heads(), specifically the return value is
1146
a set which can be mutated, and ordering of the input is not preserved
1149
:see also: Graph.heads.
1150
:param keys: The keys to calculate heads for.
1151
:return: A set containing the heads, which may be mutated without
1152
affecting future lookups.
1154
keys = frozenset(keys)
1156
return set(self._heads[keys])
1158
heads = self.graph.heads(keys)
1159
self._heads[keys] = heads
1163
class FrozenHeadsCache(object):
1164
"""Cache heads() calls, assuming the caller won't modify them."""
1166
def __init__(self, graph):
1170
def heads(self, keys):
1171
"""Return the heads of keys.
1173
Similar to Graph.heads(). The main difference is that the return value
1174
is a frozen set which cannot be mutated.
1176
:see also: Graph.heads.
1177
:param keys: The keys to calculate heads for.
1178
:return: A frozenset containing the heads.
1180
keys = frozenset(keys)
1182
return self._heads[keys]
1184
heads = frozenset(self.graph.heads(keys))
1185
self._heads[keys] = heads
1188
def cache(self, keys, heads):
1189
"""Store a known value."""
1190
self._heads[frozenset(keys)] = frozenset(heads)
1193
class _BreadthFirstSearcher(object):
1194
"""Parallel search breadth-first the ancestry of revisions.
1196
This class implements the iterator protocol, but additionally
1197
1. provides a set of seen ancestors, and
1198
2. allows some ancestries to be unsearched, via stop_searching_any
1201
def __init__(self, revisions, parents_provider):
1202
self._iterations = 0
1203
self._next_query = set(revisions)
1205
self._started_keys = set(self._next_query)
1206
self._stopped_keys = set()
1207
self._parents_provider = parents_provider
1208
self._returning = 'next_with_ghosts'
1209
self._current_present = set()
1210
self._current_ghosts = set()
1211
self._current_parents = {}
1214
if self._iterations:
1215
prefix = "searching"
1218
search = '%s=%r' % (prefix, list(self._next_query))
1219
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1220
' seen=%r)' % (self._iterations, search, list(self.seen)))
1222
def get_result(self):
1223
"""Get a SearchResult for the current state of this searcher.
1225
:return: A SearchResult for this search so far. The SearchResult is
1226
static - the search can be advanced and the search result will not
1227
be invalidated or altered.
1229
if self._returning == 'next':
1230
# We have to know the current nodes children to be able to list the
1231
# exclude keys for them. However, while we could have a second
1232
# look-ahead result buffer and shuffle things around, this method
1233
# is typically only called once per search - when memoising the
1234
# results of the search.
1235
found, ghosts, next, parents = self._do_query(self._next_query)
1236
# pretend we didn't query: perhaps we should tweak _do_query to be
1237
# entirely stateless?
1238
self.seen.difference_update(next)
1239
next_query = next.union(ghosts)
1241
next_query = self._next_query
1242
excludes = self._stopped_keys.union(next_query)
1243
included_keys = self.seen.difference(excludes)
1244
return SearchResult(self._started_keys, excludes, len(included_keys),
1250
except StopIteration:
1254
"""Return the next ancestors of this revision.
1256
Ancestors are returned in the order they are seen in a breadth-first
1257
traversal. No ancestor will be returned more than once. Ancestors are
1258
returned before their parentage is queried, so ghosts and missing
1259
revisions (including the start revisions) are included in the result.
1260
This can save a round trip in LCA style calculation by allowing
1261
convergence to be detected without reading the data for the revision
1262
the convergence occurs on.
1264
:return: A set of revision_ids.
1266
if self._returning != 'next':
1267
# switch to returning the query, not the results.
1268
self._returning = 'next'
1269
self._iterations += 1
1272
if len(self._next_query) == 0:
1273
raise StopIteration()
1274
# We have seen what we're querying at this point as we are returning
1275
# the query, not the results.
1276
self.seen.update(self._next_query)
1277
return self._next_query
1279
def next_with_ghosts(self):
1280
"""Return the next found ancestors, with ghosts split out.
1282
Ancestors are returned in the order they are seen in a breadth-first
1283
traversal. No ancestor will be returned more than once. Ancestors are
1284
returned only after asking for their parents, which allows us to detect
1285
which revisions are ghosts and which are not.
1287
:return: A tuple with (present ancestors, ghost ancestors) sets.
1289
if self._returning != 'next_with_ghosts':
1290
# switch to returning the results, not the current query.
1291
self._returning = 'next_with_ghosts'
1293
if len(self._next_query) == 0:
1294
raise StopIteration()
1296
return self._current_present, self._current_ghosts
1299
"""Advance the search.
1301
Updates self.seen, self._next_query, self._current_present,
1302
self._current_ghosts, self._current_parents and self._iterations.
1304
self._iterations += 1
1305
found, ghosts, next, parents = self._do_query(self._next_query)
1306
self._current_present = found
1307
self._current_ghosts = ghosts
1308
self._next_query = next
1309
self._current_parents = parents
1310
# ghosts are implicit stop points, otherwise the search cannot be
1311
# repeated when ghosts are filled.
1312
self._stopped_keys.update(ghosts)
1314
def _do_query(self, revisions):
1315
"""Query for revisions.
1317
Adds revisions to the seen set.
1319
:param revisions: Revisions to query.
1320
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1321
set(parents_of_found_revisions), dict(found_revisions:parents)).
1323
found_revisions = set()
1324
parents_of_found = set()
1325
# revisions may contain nodes that point to other nodes in revisions:
1326
# we want to filter them out.
1327
self.seen.update(revisions)
1328
parent_map = self._parents_provider.get_parent_map(revisions)
1329
found_revisions.update(parent_map)
1330
for rev_id, parents in parent_map.iteritems():
1333
new_found_parents = [p for p in parents if p not in self.seen]
1334
if new_found_parents:
1335
# Calling set.update() with an empty generator is actually
1337
parents_of_found.update(new_found_parents)
1338
ghost_revisions = revisions - found_revisions
1339
return found_revisions, ghost_revisions, parents_of_found, parent_map
1344
def find_seen_ancestors(self, revisions):
1345
"""Find ancestors of these revisions that have already been seen.
1347
This function generally makes the assumption that querying for the
1348
parents of a node that has already been queried is reasonably cheap.
1349
(eg, not a round trip to a remote host).
1351
# TODO: Often we might ask one searcher for its seen ancestors, and
1352
# then ask another searcher the same question. This can result in
1353
# searching the same revisions repeatedly if the two searchers
1354
# have a lot of overlap.
1355
all_seen = self.seen
1356
pending = set(revisions).intersection(all_seen)
1357
seen_ancestors = set(pending)
1359
if self._returning == 'next':
1360
# self.seen contains what nodes have been returned, not what nodes
1361
# have been queried. We don't want to probe for nodes that haven't
1362
# been searched yet.
1363
not_searched_yet = self._next_query
1365
not_searched_yet = ()
1366
pending.difference_update(not_searched_yet)
1367
get_parent_map = self._parents_provider.get_parent_map
1369
parent_map = get_parent_map(pending)
1371
# We don't care if it is a ghost, since it can't be seen if it is
1373
for parent_ids in parent_map.itervalues():
1374
all_parents.extend(parent_ids)
1375
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1376
seen_ancestors.update(next_pending)
1377
next_pending.difference_update(not_searched_yet)
1378
pending = next_pending
1380
return seen_ancestors
1382
def stop_searching_any(self, revisions):
1384
Remove any of the specified revisions from the search list.
1386
None of the specified revisions are required to be present in the
1389
It is okay to call stop_searching_any() for revisions which were seen
1390
in previous iterations. It is the callers responsibility to call
1391
find_seen_ancestors() to make sure that current search tips that are
1392
ancestors of those revisions are also stopped. All explicitly stopped
1393
revisions will be excluded from the search result's get_keys(), though.
1395
# TODO: does this help performance?
1398
revisions = frozenset(revisions)
1399
if self._returning == 'next':
1400
stopped = self._next_query.intersection(revisions)
1401
self._next_query = self._next_query.difference(revisions)
1403
stopped_present = self._current_present.intersection(revisions)
1404
stopped = stopped_present.union(
1405
self._current_ghosts.intersection(revisions))
1406
self._current_present.difference_update(stopped)
1407
self._current_ghosts.difference_update(stopped)
1408
# stopping 'x' should stop returning parents of 'x', but
1409
# not if 'y' always references those same parents
1410
stop_rev_references = {}
1411
for rev in stopped_present:
1412
for parent_id in self._current_parents[rev]:
1413
if parent_id not in stop_rev_references:
1414
stop_rev_references[parent_id] = 0
1415
stop_rev_references[parent_id] += 1
1416
# if only the stopped revisions reference it, the ref count will be
1418
for parents in self._current_parents.itervalues():
1419
for parent_id in parents:
1421
stop_rev_references[parent_id] -= 1
1424
stop_parents = set()
1425
for rev_id, refs in stop_rev_references.iteritems():
1427
stop_parents.add(rev_id)
1428
self._next_query.difference_update(stop_parents)
1429
self._stopped_keys.update(stopped)
1430
self._stopped_keys.update(revisions)
1433
def start_searching(self, revisions):
1434
"""Add revisions to the search.
1436
The parents of revisions will be returned from the next call to next()
1437
or next_with_ghosts(). If next_with_ghosts was the most recently used
1438
next* call then the return value is the result of looking up the
1439
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1441
revisions = frozenset(revisions)
1442
self._started_keys.update(revisions)
1443
new_revisions = revisions.difference(self.seen)
1444
if self._returning == 'next':
1445
self._next_query.update(new_revisions)
1446
self.seen.update(new_revisions)
1448
# perform a query on revisions
1449
revs, ghosts, query, parents = self._do_query(revisions)
1450
self._stopped_keys.update(ghosts)
1451
self._current_present.update(revs)
1452
self._current_ghosts.update(ghosts)
1453
self._next_query.update(query)
1454
self._current_parents.update(parents)
1458
class SearchResult(object):
1459
"""The result of a breadth first search.
1461
A SearchResult provides the ability to reconstruct the search or access a
1462
set of the keys the search found.
1465
def __init__(self, start_keys, exclude_keys, key_count, keys):
1466
"""Create a SearchResult.
1468
:param start_keys: The keys the search started at.
1469
:param exclude_keys: The keys the search excludes.
1470
:param key_count: The total number of keys (from start to but not
1472
:param keys: The keys the search found. Note that in future we may get
1473
a SearchResult from a smart server, in which case the keys list is
1474
not necessarily immediately available.
1476
self._recipe = ('search', start_keys, exclude_keys, key_count)
1477
self._keys = frozenset(keys)
1479
def get_recipe(self):
1480
"""Return a recipe that can be used to replay this search.
1482
The recipe allows reconstruction of the same results at a later date
1483
without knowing all the found keys. The essential elements are a list
1484
of keys to start and to stop at. In order to give reproducible
1485
results when ghosts are encountered by a search they are automatically
1486
added to the exclude list (or else ghost filling may alter the
1489
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1490
revision_count). To recreate the results of this search, create a
1491
breadth first searcher on the same graph starting at start_keys.
1492
Then call next() (or next_with_ghosts()) repeatedly, and on every
1493
result, call stop_searching_any on any keys from the exclude_keys
1494
set. The revision_count value acts as a trivial cross-check - the
1495
found revisions of the new search should have as many elements as
1496
revision_count. If it does not, then additional revisions have been
1497
ghosted since the search was executed the first time and the second
1503
"""Return the keys found in this search.
1505
:return: A set of keys.
1510
"""Return false if the search lists 1 or more revisions."""
1511
return self._recipe[3] == 0
1513
def refine(self, seen, referenced):
1514
"""Create a new search by refining this search.
1516
:param seen: Revisions that have been satisfied.
1517
:param referenced: Revision references observed while satisfying some
1520
start = self._recipe[1]
1521
exclude = self._recipe[2]
1522
count = self._recipe[3]
1523
keys = self.get_keys()
1524
# New heads = referenced + old heads - seen things - exclude
1525
pending_refs = set(referenced)
1526
pending_refs.update(start)
1527
pending_refs.difference_update(seen)
1528
pending_refs.difference_update(exclude)
1529
# New exclude = old exclude + satisfied heads
1530
seen_heads = start.intersection(seen)
1531
exclude.update(seen_heads)
1532
# keys gets seen removed
1534
# length is reduced by len(seen)
1536
return SearchResult(pending_refs, exclude, count, keys)
1539
class PendingAncestryResult(object):
1540
"""A search result that will reconstruct the ancestry for some graph heads.
1542
Unlike SearchResult, this doesn't hold the complete search result in
1543
memory, it just holds a description of how to generate it.
1546
def __init__(self, heads, repo):
1549
:param heads: an iterable of graph heads.
1550
:param repo: a repository to use to generate the ancestry for the given
1553
self.heads = frozenset(heads)
1556
def get_recipe(self):
1557
"""Return a recipe that can be used to replay this search.
1559
The recipe allows reconstruction of the same results at a later date.
1561
:seealso SearchResult.get_recipe:
1563
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1564
To recreate this result, create a PendingAncestryResult with the
1567
return ('proxy-search', self.heads, set(), -1)
1570
"""See SearchResult.get_keys.
1572
Returns all the keys for the ancestry of the heads, excluding
1575
return self._get_keys(self.repo.get_graph())
1577
def _get_keys(self, graph):
1578
NULL_REVISION = revision.NULL_REVISION
1579
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1580
if key != NULL_REVISION]
1584
"""Return false if the search lists 1 or more revisions."""
1585
if revision.NULL_REVISION in self.heads:
1586
return len(self.heads) == 1
1588
return len(self.heads) == 0
1590
def refine(self, seen, referenced):
1591
"""Create a new search by refining this search.
1593
:param seen: Revisions that have been satisfied.
1594
:param referenced: Revision references observed while satisfying some
1597
referenced = self.heads.union(referenced)
1598
return PendingAncestryResult(referenced - seen, self.repo)
1601
def collapse_linear_regions(parent_map):
1602
"""Collapse regions of the graph that are 'linear'.
1608
can be collapsed by removing B and getting::
1612
:param parent_map: A dictionary mapping children to their parents
1613
:return: Another dictionary with 'linear' chains collapsed
1615
# Note: this isn't a strictly minimal collapse. For example:
1623
# Will not have 'D' removed, even though 'E' could fit. Also:
1629
# A and C are both kept because they are edges of the graph. We *could* get
1630
# rid of A if we wanted.
1638
# Will not have any nodes removed, even though you do have an
1639
# 'uninteresting' linear D->B and E->C
1641
for child, parents in parent_map.iteritems():
1642
children.setdefault(child, [])
1644
children.setdefault(p, []).append(child)
1646
orig_children = dict(children)
1648
result = dict(parent_map)
1649
for node in parent_map:
1650
parents = result[node]
1651
if len(parents) == 1:
1652
parent_children = children[parents[0]]
1653
if len(parent_children) != 1:
1654
# This is not the only child
1656
node_children = children[node]
1657
if len(node_children) != 1:
1659
child_parents = result.get(node_children[0], None)
1660
if len(child_parents) != 1:
1661
# This is not its only parent
1663
# The child of this node only points at it, and the parent only has
1664
# this as a child. remove this node, and join the others together
1665
result[node_children[0]] = parents
1666
children[parents[0]] = node_children
added
removed
bzrlib/graph.py
