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._cache_misses = 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
137
def disable_cache(self):
138
"""Disable and clear the cache."""
141
def get_cached_map(self):
142
"""Return any cached get_parent_map values."""
143
if self._cache is None:
145
return dict((k, v) for k, v in self._cache.items()
148
def get_parent_map(self, keys):
149
"""See _StackedParentsProvider.get_parent_map."""
150
# Hack to build up the caching logic.
151
ancestry = self._cache
153
# Caching is disabled.
154
missing_revisions = set(keys)
157
missing_revisions = set(key for key in keys if key not in ancestry)
158
if missing_revisions:
159
parent_map = self._get_parent_map(missing_revisions)
160
ancestry.update(parent_map)
161
if self._cache_misses:
162
# None is never a valid parents list, so it can be used to
164
ancestry.update(dict((k, None) for k in missing_revisions
165
if k not in parent_map))
166
present_keys = [k for k in keys if ancestry.get(k) is not None]
167
return dict((k, ancestry[k]) for k in present_keys)
171
"""Provide incremental access to revision graphs.
173
This is the generic implementation; it is intended to be subclassed to
174
specialize it for other repository types.
177
def __init__(self, parents_provider):
178
"""Construct a Graph that uses several graphs as its input
180
This should not normally be invoked directly, because there may be
181
specialized implementations for particular repository types. See
182
Repository.get_graph().
184
:param parents_provider: An object providing a get_parent_map call
185
conforming to the behavior of
186
StackedParentsProvider.get_parent_map.
188
if getattr(parents_provider, 'get_parents', None) is not None:
189
self.get_parents = parents_provider.get_parents
190
if getattr(parents_provider, 'get_parent_map', None) is not None:
191
self.get_parent_map = parents_provider.get_parent_map
192
self._parents_provider = parents_provider
195
return 'Graph(%r)' % self._parents_provider
197
def find_lca(self, *revisions):
198
"""Determine the lowest common ancestors of the provided revisions
200
A lowest common ancestor is a common ancestor none of whose
201
descendants are common ancestors. In graphs, unlike trees, there may
202
be multiple lowest common ancestors.
204
This algorithm has two phases. Phase 1 identifies border ancestors,
205
and phase 2 filters border ancestors to determine lowest common
208
In phase 1, border ancestors are identified, using a breadth-first
209
search starting at the bottom of the graph. Searches are stopped
210
whenever a node or one of its descendants is determined to be common
212
In phase 2, the border ancestors are filtered to find the least
213
common ancestors. This is done by searching the ancestries of each
216
Phase 2 is perfomed on the principle that a border ancestor that is
217
not an ancestor of any other border ancestor is a least common
220
Searches are stopped when they find a node that is determined to be a
221
common ancestor of all border ancestors, because this shows that it
222
cannot be a descendant of any border ancestor.
224
The scaling of this operation should be proportional to
225
1. The number of uncommon ancestors
226
2. The number of border ancestors
227
3. The length of the shortest path between a border ancestor and an
228
ancestor of all border ancestors.
230
border_common, common, sides = self._find_border_ancestors(revisions)
231
# We may have common ancestors that can be reached from each other.
232
# - ask for the heads of them to filter it down to only ones that
233
# cannot be reached from each other - phase 2.
234
return self.heads(border_common)
236
def find_difference(self, left_revision, right_revision):
237
"""Determine the graph difference between two revisions"""
238
border, common, searchers = self._find_border_ancestors(
239
[left_revision, right_revision])
240
self._search_for_extra_common(common, searchers)
241
left = searchers[0].seen
242
right = searchers[1].seen
243
return (left.difference(right), right.difference(left))
245
def find_distance_to_null(self, target_revision_id, known_revision_ids):
246
"""Find the left-hand distance to the NULL_REVISION.
248
(This can also be considered the revno of a branch at
251
:param target_revision_id: A revision_id which we would like to know
253
:param known_revision_ids: [(revision_id, revno)] A list of known
254
revno, revision_id tuples. We'll use this to seed the search.
256
# Map from revision_ids to a known value for their revno
257
known_revnos = dict(known_revision_ids)
258
cur_tip = target_revision_id
260
NULL_REVISION = revision.NULL_REVISION
261
known_revnos[NULL_REVISION] = 0
263
searching_known_tips = list(known_revnos.keys())
265
unknown_searched = {}
267
while cur_tip not in known_revnos:
268
unknown_searched[cur_tip] = num_steps
270
to_search = set([cur_tip])
271
to_search.update(searching_known_tips)
272
parent_map = self.get_parent_map(to_search)
273
parents = parent_map.get(cur_tip, None)
274
if not parents: # An empty list or None is a ghost
275
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
279
for revision_id in searching_known_tips:
280
parents = parent_map.get(revision_id, None)
284
next_revno = known_revnos[revision_id] - 1
285
if next in unknown_searched:
286
# We have enough information to return a value right now
287
return next_revno + unknown_searched[next]
288
if next in known_revnos:
290
known_revnos[next] = next_revno
291
next_known_tips.append(next)
292
searching_known_tips = next_known_tips
294
# We reached a known revision, so just add in how many steps it took to
296
return known_revnos[cur_tip] + num_steps
298
def find_unique_ancestors(self, unique_revision, common_revisions):
299
"""Find the unique ancestors for a revision versus others.
301
This returns the ancestry of unique_revision, excluding all revisions
302
in the ancestry of common_revisions. If unique_revision is in the
303
ancestry, then the empty set will be returned.
305
:param unique_revision: The revision_id whose ancestry we are
307
XXX: Would this API be better if we allowed multiple revisions on
309
:param common_revisions: Revision_ids of ancestries to exclude.
310
:return: A set of revisions in the ancestry of unique_revision
312
if unique_revision in common_revisions:
315
# Algorithm description
316
# 1) Walk backwards from the unique node and all common nodes.
317
# 2) When a node is seen by both sides, stop searching it in the unique
318
# walker, include it in the common walker.
319
# 3) Stop searching when there are no nodes left for the unique walker.
320
# At this point, you have a maximal set of unique nodes. Some of
321
# them may actually be common, and you haven't reached them yet.
322
# 4) Start new searchers for the unique nodes, seeded with the
323
# information you have so far.
324
# 5) Continue searching, stopping the common searches when the search
325
# tip is an ancestor of all unique nodes.
326
# 6) Aggregate together unique searchers when they are searching the
327
# same tips. When all unique searchers are searching the same node,
328
# stop move it to a single 'all_unique_searcher'.
329
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
330
# Most of the time this produces very little important information.
331
# So don't step it as quickly as the other searchers.
332
# 8) Search is done when all common searchers have completed.
334
unique_searcher, common_searcher = self._find_initial_unique_nodes(
335
[unique_revision], common_revisions)
337
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
341
(all_unique_searcher,
342
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
343
unique_searcher, common_searcher)
345
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
346
unique_tip_searchers, common_searcher)
347
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
348
if 'graph' in debug.debug_flags:
349
trace.mutter('Found %d truly unique nodes out of %d',
350
len(true_unique_nodes), len(unique_nodes))
351
return true_unique_nodes
353
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
354
"""Steps 1-3 of find_unique_ancestors.
356
Find the maximal set of unique nodes. Some of these might actually
357
still be common, but we are sure that there are no other unique nodes.
359
:return: (unique_searcher, common_searcher)
362
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
363
# we know that unique_revisions aren't in common_revisions, so skip
365
unique_searcher.next()
366
common_searcher = self._make_breadth_first_searcher(common_revisions)
368
# As long as we are still finding unique nodes, keep searching
369
while unique_searcher._next_query:
370
next_unique_nodes = set(unique_searcher.step())
371
next_common_nodes = set(common_searcher.step())
373
# Check if either searcher encounters new nodes seen by the other
375
unique_are_common_nodes = next_unique_nodes.intersection(
376
common_searcher.seen)
377
unique_are_common_nodes.update(
378
next_common_nodes.intersection(unique_searcher.seen))
379
if unique_are_common_nodes:
380
ancestors = unique_searcher.find_seen_ancestors(
381
unique_are_common_nodes)
382
# TODO: This is a bit overboard, we only really care about
383
# the ancestors of the tips because the rest we
384
# already know. This is *correct* but causes us to
385
# search too much ancestry.
386
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
387
unique_searcher.stop_searching_any(ancestors)
388
common_searcher.start_searching(ancestors)
390
return unique_searcher, common_searcher
392
def _make_unique_searchers(self, unique_nodes, unique_searcher,
394
"""Create a searcher for all the unique search tips (step 4).
396
As a side effect, the common_searcher will stop searching any nodes
397
that are ancestors of the unique searcher tips.
399
:return: (all_unique_searcher, unique_tip_searchers)
401
unique_tips = self._remove_simple_descendants(unique_nodes,
402
self.get_parent_map(unique_nodes))
404
if len(unique_tips) == 1:
405
unique_tip_searchers = []
406
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
408
unique_tip_searchers = []
409
for tip in unique_tips:
410
revs_to_search = unique_searcher.find_seen_ancestors([tip])
411
revs_to_search.update(
412
common_searcher.find_seen_ancestors(revs_to_search))
413
searcher = self._make_breadth_first_searcher(revs_to_search)
414
# We don't care about the starting nodes.
415
searcher._label = tip
417
unique_tip_searchers.append(searcher)
419
ancestor_all_unique = None
420
for searcher in unique_tip_searchers:
421
if ancestor_all_unique is None:
422
ancestor_all_unique = set(searcher.seen)
424
ancestor_all_unique = ancestor_all_unique.intersection(
426
# Collapse all the common nodes into a single searcher
427
all_unique_searcher = self._make_breadth_first_searcher(
429
if ancestor_all_unique:
430
# We've seen these nodes in all the searchers, so we'll just go to
432
all_unique_searcher.step()
434
# Stop any search tips that are already known as ancestors of the
436
stopped_common = common_searcher.stop_searching_any(
437
common_searcher.find_seen_ancestors(ancestor_all_unique))
440
for searcher in unique_tip_searchers:
441
total_stopped += len(searcher.stop_searching_any(
442
searcher.find_seen_ancestors(ancestor_all_unique)))
443
if 'graph' in debug.debug_flags:
444
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
445
' (%d stopped search tips, %d common ancestors'
446
' (%d stopped common)',
447
len(unique_nodes), len(unique_tip_searchers),
448
total_stopped, len(ancestor_all_unique),
450
return all_unique_searcher, unique_tip_searchers
452
def _step_unique_and_common_searchers(self, common_searcher,
453
unique_tip_searchers,
455
"""Step all the searchers"""
456
newly_seen_common = set(common_searcher.step())
457
newly_seen_unique = set()
458
for searcher in unique_tip_searchers:
459
next = set(searcher.step())
460
next.update(unique_searcher.find_seen_ancestors(next))
461
next.update(common_searcher.find_seen_ancestors(next))
462
for alt_searcher in unique_tip_searchers:
463
if alt_searcher is searcher:
465
next.update(alt_searcher.find_seen_ancestors(next))
466
searcher.start_searching(next)
467
newly_seen_unique.update(next)
468
return newly_seen_common, newly_seen_unique
470
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
472
newly_seen_unique, step_all_unique):
473
"""Find nodes that are common to all unique_tip_searchers.
475
If it is time, step the all_unique_searcher, and add its nodes to the
478
common_to_all_unique_nodes = newly_seen_unique.copy()
479
for searcher in unique_tip_searchers:
480
common_to_all_unique_nodes.intersection_update(searcher.seen)
481
common_to_all_unique_nodes.intersection_update(
482
all_unique_searcher.seen)
483
# Step all-unique less frequently than the other searchers.
484
# In the common case, we don't need to spider out far here, so
485
# avoid doing extra work.
487
tstart = time.clock()
488
nodes = all_unique_searcher.step()
489
common_to_all_unique_nodes.update(nodes)
490
if 'graph' in debug.debug_flags:
491
tdelta = time.clock() - tstart
492
trace.mutter('all_unique_searcher step() took %.3fs'
493
'for %d nodes (%d total), iteration: %s',
494
tdelta, len(nodes), len(all_unique_searcher.seen),
495
all_unique_searcher._iterations)
496
return common_to_all_unique_nodes
498
def _collapse_unique_searchers(self, unique_tip_searchers,
499
common_to_all_unique_nodes):
500
"""Combine searchers that are searching the same tips.
502
When two searchers are searching the same tips, we can stop one of the
503
searchers. We also know that the maximal set of common ancestors is the
504
intersection of the two original searchers.
506
:return: A list of searchers that are searching unique nodes.
508
# Filter out searchers that don't actually search different
509
# nodes. We already have the ancestry intersection for them
510
unique_search_tips = {}
511
for searcher in unique_tip_searchers:
512
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
513
will_search_set = frozenset(searcher._next_query)
514
if not will_search_set:
515
if 'graph' in debug.debug_flags:
516
trace.mutter('Unique searcher %s was stopped.'
517
' (%s iterations) %d nodes stopped',
519
searcher._iterations,
521
elif will_search_set not in unique_search_tips:
522
# This searcher is searching a unique set of nodes, let it
523
unique_search_tips[will_search_set] = [searcher]
525
unique_search_tips[will_search_set].append(searcher)
526
# TODO: it might be possible to collapse searchers faster when they
527
# only have *some* search tips in common.
528
next_unique_searchers = []
529
for searchers in unique_search_tips.itervalues():
530
if len(searchers) == 1:
531
# Searching unique tips, go for it
532
next_unique_searchers.append(searchers[0])
534
# These searchers have started searching the same tips, we
535
# don't need them to cover the same ground. The
536
# intersection of their ancestry won't change, so create a
537
# new searcher, combining their histories.
538
next_searcher = searchers[0]
539
for searcher in searchers[1:]:
540
next_searcher.seen.intersection_update(searcher.seen)
541
if 'graph' in debug.debug_flags:
542
trace.mutter('Combining %d searchers into a single'
543
' searcher searching %d nodes with'
546
len(next_searcher._next_query),
547
len(next_searcher.seen))
548
next_unique_searchers.append(next_searcher)
549
return next_unique_searchers
551
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
552
unique_tip_searchers, common_searcher):
553
"""Steps 5-8 of find_unique_ancestors.
555
This function returns when common_searcher has stopped searching for
558
# We step the ancestor_all_unique searcher only every
559
# STEP_UNIQUE_SEARCHER_EVERY steps.
560
step_all_unique_counter = 0
561
# While we still have common nodes to search
562
while common_searcher._next_query:
564
newly_seen_unique) = self._step_unique_and_common_searchers(
565
common_searcher, unique_tip_searchers, unique_searcher)
566
# These nodes are common ancestors of all unique nodes
567
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
568
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
569
step_all_unique_counter==0)
570
step_all_unique_counter = ((step_all_unique_counter + 1)
571
% STEP_UNIQUE_SEARCHER_EVERY)
573
if newly_seen_common:
574
# If a 'common' node is an ancestor of all unique searchers, we
575
# can stop searching it.
576
common_searcher.stop_searching_any(
577
all_unique_searcher.seen.intersection(newly_seen_common))
578
if common_to_all_unique_nodes:
579
common_to_all_unique_nodes.update(
580
common_searcher.find_seen_ancestors(
581
common_to_all_unique_nodes))
582
# The all_unique searcher can start searching the common nodes
583
# but everyone else can stop.
584
# This is the sort of thing where we would like to not have it
585
# start_searching all of the nodes, but only mark all of them
586
# as seen, and have it search only the actual tips. Otherwise
587
# it is another get_parent_map() traversal for it to figure out
588
# what we already should know.
589
all_unique_searcher.start_searching(common_to_all_unique_nodes)
590
common_searcher.stop_searching_any(common_to_all_unique_nodes)
592
next_unique_searchers = self._collapse_unique_searchers(
593
unique_tip_searchers, common_to_all_unique_nodes)
594
if len(unique_tip_searchers) != len(next_unique_searchers):
595
if 'graph' in debug.debug_flags:
596
trace.mutter('Collapsed %d unique searchers => %d'
598
len(unique_tip_searchers),
599
len(next_unique_searchers),
600
all_unique_searcher._iterations)
601
unique_tip_searchers = next_unique_searchers
603
def get_parent_map(self, revisions):
604
"""Get a map of key:parent_list for revisions.
606
This implementation delegates to get_parents, for old parent_providers
607
that do not supply get_parent_map.
610
for rev, parents in self.get_parents(revisions):
611
if parents is not None:
612
result[rev] = parents
615
def _make_breadth_first_searcher(self, revisions):
616
return _BreadthFirstSearcher(revisions, self)
618
def _find_border_ancestors(self, revisions):
619
"""Find common ancestors with at least one uncommon descendant.
621
Border ancestors are identified using a breadth-first
622
search starting at the bottom of the graph. Searches are stopped
623
whenever a node or one of its descendants is determined to be common.
625
This will scale with the number of uncommon ancestors.
627
As well as the border ancestors, a set of seen common ancestors and a
628
list of sets of seen ancestors for each input revision is returned.
629
This allows calculation of graph difference from the results of this
632
if None in revisions:
633
raise errors.InvalidRevisionId(None, self)
634
common_ancestors = set()
635
searchers = [self._make_breadth_first_searcher([r])
637
active_searchers = searchers[:]
638
border_ancestors = set()
642
for searcher in searchers:
643
new_ancestors = searcher.step()
645
newly_seen.update(new_ancestors)
647
for revision in newly_seen:
648
if revision in common_ancestors:
649
# Not a border ancestor because it was seen as common
651
new_common.add(revision)
653
for searcher in searchers:
654
if revision not in searcher.seen:
657
# This is a border because it is a first common that we see
658
# after walking for a while.
659
border_ancestors.add(revision)
660
new_common.add(revision)
662
for searcher in searchers:
663
new_common.update(searcher.find_seen_ancestors(new_common))
664
for searcher in searchers:
665
searcher.start_searching(new_common)
666
common_ancestors.update(new_common)
668
# Figure out what the searchers will be searching next, and if
669
# there is only 1 set being searched, then we are done searching,
670
# since all searchers would have to be searching the same data,
671
# thus it *must* be in common.
672
unique_search_sets = set()
673
for searcher in searchers:
674
will_search_set = frozenset(searcher._next_query)
675
if will_search_set not in unique_search_sets:
676
# This searcher is searching a unique set of nodes, let it
677
unique_search_sets.add(will_search_set)
679
if len(unique_search_sets) == 1:
680
nodes = unique_search_sets.pop()
681
uncommon_nodes = nodes.difference(common_ancestors)
683
raise AssertionError("Somehow we ended up converging"
684
" without actually marking them as"
687
"\nuncommon_nodes: %s"
688
% (revisions, uncommon_nodes))
690
return border_ancestors, common_ancestors, searchers
692
def heads(self, keys):
693
"""Return the heads from amongst keys.
695
This is done by searching the ancestries of each key. Any key that is
696
reachable from another key is not returned; all the others are.
698
This operation scales with the relative depth between any two keys. If
699
any two keys are completely disconnected all ancestry of both sides
702
:param keys: An iterable of keys.
703
:return: A set of the heads. Note that as a set there is no ordering
704
information. Callers will need to filter their input to create
705
order if they need it.
707
candidate_heads = set(keys)
708
if revision.NULL_REVISION in candidate_heads:
709
# NULL_REVISION is only a head if it is the only entry
710
candidate_heads.remove(revision.NULL_REVISION)
711
if not candidate_heads:
712
return set([revision.NULL_REVISION])
713
if len(candidate_heads) < 2:
714
return candidate_heads
715
searchers = dict((c, self._make_breadth_first_searcher([c]))
716
for c in candidate_heads)
717
active_searchers = dict(searchers)
718
# skip over the actual candidate for each searcher
719
for searcher in active_searchers.itervalues():
721
# The common walker finds nodes that are common to two or more of the
722
# input keys, so that we don't access all history when a currently
723
# uncommon search point actually meets up with something behind a
724
# common search point. Common search points do not keep searches
725
# active; they just allow us to make searches inactive without
726
# accessing all history.
727
common_walker = self._make_breadth_first_searcher([])
728
while len(active_searchers) > 0:
733
except StopIteration:
734
# No common points being searched at this time.
736
for candidate in active_searchers.keys():
738
searcher = active_searchers[candidate]
740
# rare case: we deleted candidate in a previous iteration
741
# through this for loop, because it was determined to be
742
# a descendant of another candidate.
745
ancestors.update(searcher.next())
746
except StopIteration:
747
del active_searchers[candidate]
749
# process found nodes
751
for ancestor in ancestors:
752
if ancestor in candidate_heads:
753
candidate_heads.remove(ancestor)
754
del searchers[ancestor]
755
if ancestor in active_searchers:
756
del active_searchers[ancestor]
757
# it may meet up with a known common node
758
if ancestor in common_walker.seen:
759
# some searcher has encountered our known common nodes:
761
ancestor_set = set([ancestor])
762
for searcher in searchers.itervalues():
763
searcher.stop_searching_any(ancestor_set)
765
# or it may have been just reached by all the searchers:
766
for searcher in searchers.itervalues():
767
if ancestor not in searcher.seen:
770
# The final active searcher has just reached this node,
771
# making it be known as a descendant of all candidates,
772
# so we can stop searching it, and any seen ancestors
773
new_common.add(ancestor)
774
for searcher in searchers.itervalues():
776
searcher.find_seen_ancestors([ancestor])
777
searcher.stop_searching_any(seen_ancestors)
778
common_walker.start_searching(new_common)
779
return candidate_heads
781
def find_merge_order(self, tip_revision_id, lca_revision_ids):
782
"""Find the order that each revision was merged into tip.
784
This basically just walks backwards with a stack, and walks left-first
785
until it finds a node to stop.
787
if len(lca_revision_ids) == 1:
788
return list(lca_revision_ids)
789
looking_for = set(lca_revision_ids)
790
# TODO: Is there a way we could do this "faster" by batching up the
791
# get_parent_map requests?
792
# TODO: Should we also be culling the ancestry search right away? We
793
# could add looking_for to the "stop" list, and walk their
794
# ancestry in batched mode. The flip side is it might mean we walk a
795
# lot of "stop" nodes, rather than only the minimum.
796
# Then again, without it we may trace back into ancestry we could have
798
stack = [tip_revision_id]
801
while stack and looking_for:
804
if next in looking_for:
806
looking_for.remove(next)
807
if len(looking_for) == 1:
808
found.append(looking_for.pop())
811
parent_ids = self.get_parent_map([next]).get(next, None)
812
if not parent_ids: # Ghost, nothing to search here
814
for parent_id in reversed(parent_ids):
815
# TODO: (performance) We see the parent at this point, but we
816
# wait to mark it until later to make sure we get left
817
# parents before right parents. However, instead of
818
# waiting until we have traversed enough parents, we
819
# could instead note that we've found it, and once all
820
# parents are in the stack, just reverse iterate the
822
if parent_id not in stop:
823
# this will need to be searched
824
stack.append(parent_id)
828
def find_unique_lca(self, left_revision, right_revision,
830
"""Find a unique LCA.
832
Find lowest common ancestors. If there is no unique common
833
ancestor, find the lowest common ancestors of those ancestors.
835
Iteration stops when a unique lowest common ancestor is found.
836
The graph origin is necessarily a unique lowest common ancestor.
838
Note that None is not an acceptable substitute for NULL_REVISION.
839
in the input for this method.
841
:param count_steps: If True, the return value will be a tuple of
842
(unique_lca, steps) where steps is the number of times that
843
find_lca was run. If False, only unique_lca is returned.
845
revisions = [left_revision, right_revision]
849
lca = self.find_lca(*revisions)
857
raise errors.NoCommonAncestor(left_revision, right_revision)
860
def iter_ancestry(self, revision_ids):
861
"""Iterate the ancestry of this revision.
863
:param revision_ids: Nodes to start the search
864
:return: Yield tuples mapping a revision_id to its parents for the
865
ancestry of revision_id.
866
Ghosts will be returned with None as their parents, and nodes
867
with no parents will have NULL_REVISION as their only parent. (As
868
defined by get_parent_map.)
869
There will also be a node for (NULL_REVISION, ())
871
pending = set(revision_ids)
874
processed.update(pending)
875
next_map = self.get_parent_map(pending)
877
for item in next_map.iteritems():
879
next_pending.update(p for p in item[1] if p not in processed)
880
ghosts = pending.difference(next_map)
883
pending = next_pending
885
def iter_topo_order(self, revisions):
886
"""Iterate through the input revisions in topological order.
888
This sorting only ensures that parents come before their children.
889
An ancestor may sort after a descendant if the relationship is not
890
visible in the supplied list of revisions.
892
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
893
return sorter.iter_topo_order()
895
def is_ancestor(self, candidate_ancestor, candidate_descendant):
896
"""Determine whether a revision is an ancestor of another.
898
We answer this using heads() as heads() has the logic to perform the
899
smallest number of parent lookups to determine the ancestral
900
relationship between N revisions.
902
return set([candidate_descendant]) == self.heads(
903
[candidate_ancestor, candidate_descendant])
905
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
906
"""Determine whether a revision is between two others.
908
returns true if and only if:
909
lower_bound_revid <= revid <= upper_bound_revid
911
return ((upper_bound_revid is None or
912
self.is_ancestor(revid, upper_bound_revid)) and
913
(lower_bound_revid is None or
914
self.is_ancestor(lower_bound_revid, revid)))
916
def _search_for_extra_common(self, common, searchers):
917
"""Make sure that unique nodes are genuinely unique.
919
After _find_border_ancestors, all nodes marked "common" are indeed
920
common. Some of the nodes considered unique are not, due to history
921
shortcuts stopping the searches early.
923
We know that we have searched enough when all common search tips are
924
descended from all unique (uncommon) nodes because we know that a node
925
cannot be an ancestor of its own ancestor.
927
:param common: A set of common nodes
928
:param searchers: The searchers returned from _find_border_ancestors
932
# A) The passed in searchers should all be on the same tips, thus
933
# they should be considered the "common" searchers.
934
# B) We find the difference between the searchers, these are the
935
# "unique" nodes for each side.
936
# C) We do a quick culling so that we only start searching from the
937
# more interesting unique nodes. (A unique ancestor is more
938
# interesting than any of its children.)
939
# D) We start searching for ancestors common to all unique nodes.
940
# E) We have the common searchers stop searching any ancestors of
942
# F) When there are no more common search tips, we stop
944
# TODO: We need a way to remove unique_searchers when they overlap with
945
# other unique searchers.
946
if len(searchers) != 2:
947
raise NotImplementedError(
948
"Algorithm not yet implemented for > 2 searchers")
949
common_searchers = searchers
950
left_searcher = searchers[0]
951
right_searcher = searchers[1]
952
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
953
if not unique: # No unique nodes, nothing to do
955
total_unique = len(unique)
956
unique = self._remove_simple_descendants(unique,
957
self.get_parent_map(unique))
958
simple_unique = len(unique)
960
unique_searchers = []
961
for revision_id in unique:
962
if revision_id in left_searcher.seen:
963
parent_searcher = left_searcher
965
parent_searcher = right_searcher
966
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
967
if not revs_to_search: # XXX: This shouldn't be possible
968
revs_to_search = [revision_id]
969
searcher = self._make_breadth_first_searcher(revs_to_search)
970
# We don't care about the starting nodes.
972
unique_searchers.append(searcher)
974
# possible todo: aggregate the common searchers into a single common
975
# searcher, just make sure that we include the nodes into the .seen
976
# properties of the original searchers
978
ancestor_all_unique = None
979
for searcher in unique_searchers:
980
if ancestor_all_unique is None:
981
ancestor_all_unique = set(searcher.seen)
983
ancestor_all_unique = ancestor_all_unique.intersection(
986
trace.mutter('Started %s unique searchers for %s unique revisions',
987
simple_unique, total_unique)
989
while True: # If we have no more nodes we have nothing to do
990
newly_seen_common = set()
991
for searcher in common_searchers:
992
newly_seen_common.update(searcher.step())
993
newly_seen_unique = set()
994
for searcher in unique_searchers:
995
newly_seen_unique.update(searcher.step())
996
new_common_unique = set()
997
for revision in newly_seen_unique:
998
for searcher in unique_searchers:
999
if revision not in searcher.seen:
1002
# This is a border because it is a first common that we see
1003
# after walking for a while.
1004
new_common_unique.add(revision)
1005
if newly_seen_common:
1006
# These are nodes descended from one of the 'common' searchers.
1007
# Make sure all searchers are on the same page
1008
for searcher in common_searchers:
1009
newly_seen_common.update(
1010
searcher.find_seen_ancestors(newly_seen_common))
1011
# We start searching the whole ancestry. It is a bit wasteful,
1012
# though. We really just want to mark all of these nodes as
1013
# 'seen' and then start just the tips. However, it requires a
1014
# get_parent_map() call to figure out the tips anyway, and all
1015
# redundant requests should be fairly fast.
1016
for searcher in common_searchers:
1017
searcher.start_searching(newly_seen_common)
1019
# If a 'common' node is an ancestor of all unique searchers, we
1020
# can stop searching it.
1021
stop_searching_common = ancestor_all_unique.intersection(
1023
if stop_searching_common:
1024
for searcher in common_searchers:
1025
searcher.stop_searching_any(stop_searching_common)
1026
if new_common_unique:
1027
# We found some ancestors that are common
1028
for searcher in unique_searchers:
1029
new_common_unique.update(
1030
searcher.find_seen_ancestors(new_common_unique))
1031
# Since these are common, we can grab another set of ancestors
1033
for searcher in common_searchers:
1034
new_common_unique.update(
1035
searcher.find_seen_ancestors(new_common_unique))
1037
# We can tell all of the unique searchers to start at these
1038
# nodes, and tell all of the common searchers to *stop*
1039
# searching these nodes
1040
for searcher in unique_searchers:
1041
searcher.start_searching(new_common_unique)
1042
for searcher in common_searchers:
1043
searcher.stop_searching_any(new_common_unique)
1044
ancestor_all_unique.update(new_common_unique)
1046
# Filter out searchers that don't actually search different
1047
# nodes. We already have the ancestry intersection for them
1048
next_unique_searchers = []
1049
unique_search_sets = set()
1050
for searcher in unique_searchers:
1051
will_search_set = frozenset(searcher._next_query)
1052
if will_search_set not in unique_search_sets:
1053
# This searcher is searching a unique set of nodes, let it
1054
unique_search_sets.add(will_search_set)
1055
next_unique_searchers.append(searcher)
1056
unique_searchers = next_unique_searchers
1057
for searcher in common_searchers:
1058
if searcher._next_query:
1061
# All common searcher have stopped searching
1064
def _remove_simple_descendants(self, revisions, parent_map):
1065
"""remove revisions which are children of other ones in the set
1067
This doesn't do any graph searching, it just checks the immediate
1068
parent_map to find if there are any children which can be removed.
1070
:param revisions: A set of revision_ids
1071
:return: A set of revision_ids with the children removed
1073
simple_ancestors = revisions.copy()
1074
# TODO: jam 20071214 we *could* restrict it to searching only the
1075
# parent_map of revisions already present in 'revisions', but
1076
# considering the general use case, I think this is actually
1079
# This is the same as the following loop. I don't know that it is any
1081
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1082
## if p_ids is not None and revisions.intersection(p_ids))
1083
## return simple_ancestors
1085
# Yet Another Way, invert the parent map (which can be cached)
1087
## for revision_id, parent_ids in parent_map.iteritems():
1088
## for p_id in parent_ids:
1089
## descendants.setdefault(p_id, []).append(revision_id)
1090
## for revision in revisions.intersection(descendants):
1091
## simple_ancestors.difference_update(descendants[revision])
1092
## return simple_ancestors
1093
for revision, parent_ids in parent_map.iteritems():
1094
if parent_ids is None:
1096
for parent_id in parent_ids:
1097
if parent_id in revisions:
1098
# This node has a parent present in the set, so we can
1100
simple_ancestors.discard(revision)
1102
return simple_ancestors
1105
class HeadsCache(object):
1106
"""A cache of results for graph heads calls."""
1108
def __init__(self, graph):
1112
def heads(self, keys):
1113
"""Return the heads of keys.
1115
This matches the API of Graph.heads(), specifically the return value is
1116
a set which can be mutated, and ordering of the input is not preserved
1119
:see also: Graph.heads.
1120
:param keys: The keys to calculate heads for.
1121
:return: A set containing the heads, which may be mutated without
1122
affecting future lookups.
1124
keys = frozenset(keys)
1126
return set(self._heads[keys])
1128
heads = self.graph.heads(keys)
1129
self._heads[keys] = heads
1133
class FrozenHeadsCache(object):
1134
"""Cache heads() calls, assuming the caller won't modify them."""
1136
def __init__(self, graph):
1140
def heads(self, keys):
1141
"""Return the heads of keys.
1143
Similar to Graph.heads(). The main difference is that the return value
1144
is a frozen set which cannot be mutated.
1146
:see also: Graph.heads.
1147
:param keys: The keys to calculate heads for.
1148
:return: A frozenset containing the heads.
1150
keys = frozenset(keys)
1152
return self._heads[keys]
1154
heads = frozenset(self.graph.heads(keys))
1155
self._heads[keys] = heads
1158
def cache(self, keys, heads):
1159
"""Store a known value."""
1160
self._heads[frozenset(keys)] = frozenset(heads)
1163
class _BreadthFirstSearcher(object):
1164
"""Parallel search breadth-first the ancestry of revisions.
1166
This class implements the iterator protocol, but additionally
1167
1. provides a set of seen ancestors, and
1168
2. allows some ancestries to be unsearched, via stop_searching_any
1171
def __init__(self, revisions, parents_provider):
1172
self._iterations = 0
1173
self._next_query = set(revisions)
1175
self._started_keys = set(self._next_query)
1176
self._stopped_keys = set()
1177
self._parents_provider = parents_provider
1178
self._returning = 'next_with_ghosts'
1179
self._current_present = set()
1180
self._current_ghosts = set()
1181
self._current_parents = {}
1184
if self._iterations:
1185
prefix = "searching"
1188
search = '%s=%r' % (prefix, list(self._next_query))
1189
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1190
' seen=%r)' % (self._iterations, search, list(self.seen)))
1192
def get_result(self):
1193
"""Get a SearchResult for the current state of this searcher.
1195
:return: A SearchResult for this search so far. The SearchResult is
1196
static - the search can be advanced and the search result will not
1197
be invalidated or altered.
1199
if self._returning == 'next':
1200
# We have to know the current nodes children to be able to list the
1201
# exclude keys for them. However, while we could have a second
1202
# look-ahead result buffer and shuffle things around, this method
1203
# is typically only called once per search - when memoising the
1204
# results of the search.
1205
found, ghosts, next, parents = self._do_query(self._next_query)
1206
# pretend we didn't query: perhaps we should tweak _do_query to be
1207
# entirely stateless?
1208
self.seen.difference_update(next)
1209
next_query = next.union(ghosts)
1211
next_query = self._next_query
1212
excludes = self._stopped_keys.union(next_query)
1213
included_keys = self.seen.difference(excludes)
1214
return SearchResult(self._started_keys, excludes, len(included_keys),
1220
except StopIteration:
1224
"""Return the next ancestors of this revision.
1226
Ancestors are returned in the order they are seen in a breadth-first
1227
traversal. No ancestor will be returned more than once. Ancestors are
1228
returned before their parentage is queried, so ghosts and missing
1229
revisions (including the start revisions) are included in the result.
1230
This can save a round trip in LCA style calculation by allowing
1231
convergence to be detected without reading the data for the revision
1232
the convergence occurs on.
1234
:return: A set of revision_ids.
1236
if self._returning != 'next':
1237
# switch to returning the query, not the results.
1238
self._returning = 'next'
1239
self._iterations += 1
1242
if len(self._next_query) == 0:
1243
raise StopIteration()
1244
# We have seen what we're querying at this point as we are returning
1245
# the query, not the results.
1246
self.seen.update(self._next_query)
1247
return self._next_query
1249
def next_with_ghosts(self):
1250
"""Return the next found ancestors, with ghosts split out.
1252
Ancestors are returned in the order they are seen in a breadth-first
1253
traversal. No ancestor will be returned more than once. Ancestors are
1254
returned only after asking for their parents, which allows us to detect
1255
which revisions are ghosts and which are not.
1257
:return: A tuple with (present ancestors, ghost ancestors) sets.
1259
if self._returning != 'next_with_ghosts':
1260
# switch to returning the results, not the current query.
1261
self._returning = 'next_with_ghosts'
1263
if len(self._next_query) == 0:
1264
raise StopIteration()
1266
return self._current_present, self._current_ghosts
1269
"""Advance the search.
1271
Updates self.seen, self._next_query, self._current_present,
1272
self._current_ghosts, self._current_parents and self._iterations.
1274
self._iterations += 1
1275
found, ghosts, next, parents = self._do_query(self._next_query)
1276
self._current_present = found
1277
self._current_ghosts = ghosts
1278
self._next_query = next
1279
self._current_parents = parents
1280
# ghosts are implicit stop points, otherwise the search cannot be
1281
# repeated when ghosts are filled.
1282
self._stopped_keys.update(ghosts)
1284
def _do_query(self, revisions):
1285
"""Query for revisions.
1287
Adds revisions to the seen set.
1289
:param revisions: Revisions to query.
1290
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1291
set(parents_of_found_revisions), dict(found_revisions:parents)).
1293
found_revisions = set()
1294
parents_of_found = set()
1295
# revisions may contain nodes that point to other nodes in revisions:
1296
# we want to filter them out.
1297
self.seen.update(revisions)
1298
parent_map = self._parents_provider.get_parent_map(revisions)
1299
found_revisions.update(parent_map)
1300
for rev_id, parents in parent_map.iteritems():
1303
new_found_parents = [p for p in parents if p not in self.seen]
1304
if new_found_parents:
1305
# Calling set.update() with an empty generator is actually
1307
parents_of_found.update(new_found_parents)
1308
ghost_revisions = revisions - found_revisions
1309
return found_revisions, ghost_revisions, parents_of_found, parent_map
1314
def find_seen_ancestors(self, revisions):
1315
"""Find ancestors of these revisions that have already been seen.
1317
This function generally makes the assumption that querying for the
1318
parents of a node that has already been queried is reasonably cheap.
1319
(eg, not a round trip to a remote host).
1321
# TODO: Often we might ask one searcher for its seen ancestors, and
1322
# then ask another searcher the same question. This can result in
1323
# searching the same revisions repeatedly if the two searchers
1324
# have a lot of overlap.
1325
all_seen = self.seen
1326
pending = set(revisions).intersection(all_seen)
1327
seen_ancestors = set(pending)
1329
if self._returning == 'next':
1330
# self.seen contains what nodes have been returned, not what nodes
1331
# have been queried. We don't want to probe for nodes that haven't
1332
# been searched yet.
1333
not_searched_yet = self._next_query
1335
not_searched_yet = ()
1336
pending.difference_update(not_searched_yet)
1337
get_parent_map = self._parents_provider.get_parent_map
1339
parent_map = get_parent_map(pending)
1341
# We don't care if it is a ghost, since it can't be seen if it is
1343
for parent_ids in parent_map.itervalues():
1344
all_parents.extend(parent_ids)
1345
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1346
seen_ancestors.update(next_pending)
1347
next_pending.difference_update(not_searched_yet)
1348
pending = next_pending
1350
return seen_ancestors
1352
def stop_searching_any(self, revisions):
1354
Remove any of the specified revisions from the search list.
1356
None of the specified revisions are required to be present in the
1359
It is okay to call stop_searching_any() for revisions which were seen
1360
in previous iterations. It is the callers responsibility to call
1361
find_seen_ancestors() to make sure that current search tips that are
1362
ancestors of those revisions are also stopped. All explicitly stopped
1363
revisions will be excluded from the search result's get_keys(), though.
1365
# TODO: does this help performance?
1368
revisions = frozenset(revisions)
1369
if self._returning == 'next':
1370
stopped = self._next_query.intersection(revisions)
1371
self._next_query = self._next_query.difference(revisions)
1373
stopped_present = self._current_present.intersection(revisions)
1374
stopped = stopped_present.union(
1375
self._current_ghosts.intersection(revisions))
1376
self._current_present.difference_update(stopped)
1377
self._current_ghosts.difference_update(stopped)
1378
# stopping 'x' should stop returning parents of 'x', but
1379
# not if 'y' always references those same parents
1380
stop_rev_references = {}
1381
for rev in stopped_present:
1382
for parent_id in self._current_parents[rev]:
1383
if parent_id not in stop_rev_references:
1384
stop_rev_references[parent_id] = 0
1385
stop_rev_references[parent_id] += 1
1386
# if only the stopped revisions reference it, the ref count will be
1388
for parents in self._current_parents.itervalues():
1389
for parent_id in parents:
1391
stop_rev_references[parent_id] -= 1
1394
stop_parents = set()
1395
for rev_id, refs in stop_rev_references.iteritems():
1397
stop_parents.add(rev_id)
1398
self._next_query.difference_update(stop_parents)
1399
self._stopped_keys.update(stopped)
1400
self._stopped_keys.update(revisions)
1403
def start_searching(self, revisions):
1404
"""Add revisions to the search.
1406
The parents of revisions will be returned from the next call to next()
1407
or next_with_ghosts(). If next_with_ghosts was the most recently used
1408
next* call then the return value is the result of looking up the
1409
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1411
revisions = frozenset(revisions)
1412
self._started_keys.update(revisions)
1413
new_revisions = revisions.difference(self.seen)
1414
if self._returning == 'next':
1415
self._next_query.update(new_revisions)
1416
self.seen.update(new_revisions)
1418
# perform a query on revisions
1419
revs, ghosts, query, parents = self._do_query(revisions)
1420
self._stopped_keys.update(ghosts)
1421
self._current_present.update(revs)
1422
self._current_ghosts.update(ghosts)
1423
self._next_query.update(query)
1424
self._current_parents.update(parents)
1428
class SearchResult(object):
1429
"""The result of a breadth first search.
1431
A SearchResult provides the ability to reconstruct the search or access a
1432
set of the keys the search found.
1435
def __init__(self, start_keys, exclude_keys, key_count, keys):
1436
"""Create a SearchResult.
1438
:param start_keys: The keys the search started at.
1439
:param exclude_keys: The keys the search excludes.
1440
:param key_count: The total number of keys (from start to but not
1442
:param keys: The keys the search found. Note that in future we may get
1443
a SearchResult from a smart server, in which case the keys list is
1444
not necessarily immediately available.
1446
self._recipe = ('search', start_keys, exclude_keys, key_count)
1447
self._keys = frozenset(keys)
1449
def get_recipe(self):
1450
"""Return a recipe that can be used to replay this search.
1452
The recipe allows reconstruction of the same results at a later date
1453
without knowing all the found keys. The essential elements are a list
1454
of keys to start and and to stop at. In order to give reproducible
1455
results when ghosts are encountered by a search they are automatically
1456
added to the exclude list (or else ghost filling may alter the
1459
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1460
revision_count). To recreate the results of this search, create a
1461
breadth first searcher on the same graph starting at start_keys.
1462
Then call next() (or next_with_ghosts()) repeatedly, and on every
1463
result, call stop_searching_any on any keys from the exclude_keys
1464
set. The revision_count value acts as a trivial cross-check - the
1465
found revisions of the new search should have as many elements as
1466
revision_count. If it does not, then additional revisions have been
1467
ghosted since the search was executed the first time and the second
1473
"""Return the keys found in this search.
1475
:return: A set of keys.
1480
"""Return true if the search lists 1 or more revisions."""
1481
return self._recipe[3] == 0
1483
def refine(self, seen, referenced):
1484
"""Create a new search by refining this search.
1486
:param seen: Revisions that have been satisfied.
1487
:param referenced: Revision references observed while satisfying some
1490
start = self._recipe[1]
1491
exclude = self._recipe[2]
1492
count = self._recipe[3]
1493
keys = self.get_keys()
1494
# New heads = referenced + old heads - seen things - exclude
1495
pending_refs = set(referenced)
1496
pending_refs.update(start)
1497
pending_refs.difference_update(seen)
1498
pending_refs.difference_update(exclude)
1499
# New exclude = old exclude + satisfied heads
1500
seen_heads = start.intersection(seen)
1501
exclude.update(seen_heads)
1502
# keys gets seen removed
1504
# length is reduced by len(seen)
1506
return SearchResult(pending_refs, exclude, count, keys)
1509
class PendingAncestryResult(object):
1510
"""A search result that will reconstruct the ancestry for some graph heads.
1512
Unlike SearchResult, this doesn't hold the complete search result in
1513
memory, it just holds a description of how to generate it.
1516
def __init__(self, heads, repo):
1519
:param heads: an iterable of graph heads.
1520
:param repo: a repository to use to generate the ancestry for the given
1523
self.heads = frozenset(heads)
1526
def get_recipe(self):
1527
"""Return a recipe that can be used to replay this search.
1529
The recipe allows reconstruction of the same results at a later date.
1531
:seealso SearchResult.get_recipe:
1533
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1534
To recreate this result, create a PendingAncestryResult with the
1537
return ('proxy-search', self.heads, set(), -1)
1540
"""See SearchResult.get_keys.
1542
Returns all the keys for the ancestry of the heads, excluding
1545
return self._get_keys(self.repo.get_graph())
1547
def _get_keys(self, graph):
1548
NULL_REVISION = revision.NULL_REVISION
1549
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1550
if key != NULL_REVISION]
1554
"""Return true if the search lists 1 or more revisions."""
1555
if revision.NULL_REVISION in self.heads:
1556
return len(self.heads) == 1
1558
return len(self.heads) == 0
1560
def refine(self, seen, referenced):
1561
"""Create a new search by refining this search.
1563
:param seen: Revisions that have been satisfied.
1564
:param referenced: Revision references observed while satisfying some
1567
referenced = self.heads.union(referenced)
1568
return PendingAncestryResult(referenced - seen, self.repo)
1571
def collapse_linear_regions(parent_map):
1572
"""Collapse regions of the graph that are 'linear'.
1578
can be collapsed by removing B and getting::
1582
:param parent_map: A dictionary mapping children to their parents
1583
:return: Another dictionary with 'linear' chains collapsed
1585
# Note: this isn't a strictly minimal collapse. For example:
1593
# Will not have 'D' removed, even though 'E' could fit. Also:
1599
# A and C are both kept because they are edges of the graph. We *could* get
1600
# rid of A if we wanted.
1608
# Will not have any nodes removed, even though you do have an
1609
# 'uninteresting' linear D->B and E->C
1611
for child, parents in parent_map.iteritems():
1612
children.setdefault(child, [])
1614
children.setdefault(p, []).append(child)
1616
orig_children = dict(children)
1618
result = dict(parent_map)
1619
for node in parent_map:
1620
parents = result[node]
1621
if len(parents) == 1:
1622
parent_children = children[parents[0]]
1623
if len(parent_children) != 1:
1624
# This is not the only child
1626
node_children = children[node]
1627
if len(node_children) != 1:
1629
child_parents = result.get(node_children[0], None)
1630
if len(child_parents) != 1:
1631
# This is not its only parent
1633
# The child of this node only points at it, and the parent only has
1634
# this as a child. remove this node, and join the others together
1635
result[node_children[0]] = parents
1636
children[parents[0]] = node_children
added
removed
bzrlib/graph.py
