50
44
# 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)
67
@deprecated_function(deprecated_in((1, 16, 0)))
68
def _StackedParentsProvider(*args, **kwargs):
69
return StackedParentsProvider(*args, **kwargs)
71
class StackedParentsProvider(object):
72
"""A parents provider which stacks (or unions) multiple providers.
74
The providers are queries in the order of the provided parent_providers.
48
class _StackedParentsProvider(object):
77
50
def __init__(self, parent_providers):
78
51
self._parent_providers = parent_providers
80
53
def __repr__(self):
81
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
83
def get_parent_map(self, keys):
84
"""Get a mapping of keys => parents
86
A dictionary is returned with an entry for each key present in this
87
source. If this source doesn't have information about a key, it should
54
return "_StackedParentsProvider(%r)" % self._parent_providers
56
def get_parents(self, revision_ids):
57
"""Find revision ids of the parents of a list of revisions
59
A list is returned of the same length as the input. Each entry
60
is a list of parent ids for the corresponding input revision.
90
62
[NULL_REVISION] is used as the parent of the first user-committed
91
63
revision. Its parent list is empty.
93
:param keys: An iterable returning keys to check (eg revision_ids)
94
:return: A dictionary mapping each key to its parents
65
If the revision is not present (i.e. a ghost), None is used in place
66
of the list of parents.
98
69
for parents_provider in self._parent_providers:
99
new_found = parents_provider.get_parent_map(remaining)
70
pending_revisions = [r for r in revision_ids if r not in found]
71
parent_list = parents_provider.get_parents(pending_revisions)
72
new_found = dict((k, v) for k, v in zip(pending_revisions,
73
parent_list) if v is not None)
100
74
found.update(new_found)
101
remaining.difference_update(new_found)
75
if len(found) == len(revision_ids):
107
class CachingParentsProvider(object):
108
"""A parents provider which will cache the revision => parents as a dict.
110
This is useful for providers which have an expensive look up.
112
Either a ParentsProvider or a get_parent_map-like callback may be
113
supplied. If it provides extra un-asked-for parents, they will be cached,
114
but filtered out of get_parent_map.
116
The cache is enabled by default, but may be disabled and re-enabled.
118
def __init__(self, parent_provider=None, get_parent_map=None):
121
:param parent_provider: The ParentProvider to use. It or
122
get_parent_map must be supplied.
123
:param get_parent_map: The get_parent_map callback to use. It or
124
parent_provider must be supplied.
126
self._real_provider = parent_provider
127
if get_parent_map is None:
128
self._get_parent_map = self._real_provider.get_parent_map
130
self._get_parent_map = get_parent_map
132
self.enable_cache(True)
135
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
137
def enable_cache(self, cache_misses=True):
139
if self._cache is not None:
140
raise AssertionError('Cache enabled when already enabled.')
142
self._cache_misses = cache_misses
143
self.missing_keys = set()
145
def disable_cache(self):
146
"""Disable and clear the cache."""
148
self._cache_misses = None
149
self.missing_keys = set()
151
def get_cached_map(self):
152
"""Return any cached get_parent_map values."""
153
if self._cache is None:
155
return dict(self._cache)
157
def get_parent_map(self, keys):
158
"""See StackedParentsProvider.get_parent_map."""
161
cache = self._get_parent_map(keys)
163
needed_revisions = set(key for key in keys if key not in cache)
164
# Do not ask for negatively cached keys
165
needed_revisions.difference_update(self.missing_keys)
167
parent_map = self._get_parent_map(needed_revisions)
168
cache.update(parent_map)
169
if self._cache_misses:
170
for key in needed_revisions:
171
if key not in parent_map:
172
self.note_missing_key(key)
175
value = cache.get(key)
176
if value is not None:
180
def note_missing_key(self, key):
181
"""Note that key is a missing key."""
182
if self._cache_misses:
183
self.missing_keys.add(key)
77
return [found.get(r, None) for r in revision_ids]
186
80
class Graph(object):
244
134
ancestor of all border ancestors.
246
136
border_common, common, sides = self._find_border_ancestors(revisions)
247
# We may have common ancestors that can be reached from each other.
248
# - ask for the heads of them to filter it down to only ones that
249
# cannot be reached from each other - phase 2.
250
return self.heads(border_common)
137
return self._filter_candidate_lca(border_common)
252
139
def find_difference(self, left_revision, right_revision):
253
140
"""Determine the graph difference between two revisions"""
254
border, common, searchers = self._find_border_ancestors(
141
border, common, (left, right) = self._find_border_ancestors(
255
142
[left_revision, right_revision])
256
self._search_for_extra_common(common, searchers)
257
left = searchers[0].seen
258
right = searchers[1].seen
259
return (left.difference(right), right.difference(left))
261
def find_descendants(self, old_key, new_key):
262
"""Find descendants of old_key that are ancestors of new_key."""
263
child_map = self.get_child_map(self._find_descendant_ancestors(
265
graph = Graph(DictParentsProvider(child_map))
266
searcher = graph._make_breadth_first_searcher([old_key])
270
def _find_descendant_ancestors(self, old_key, new_key):
271
"""Find ancestors of new_key that may be descendants of old_key."""
272
stop = self._make_breadth_first_searcher([old_key])
273
descendants = self._make_breadth_first_searcher([new_key])
274
for revisions in descendants:
275
old_stop = stop.seen.intersection(revisions)
276
descendants.stop_searching_any(old_stop)
277
seen_stop = descendants.find_seen_ancestors(stop.step())
278
descendants.stop_searching_any(seen_stop)
279
return descendants.seen.difference(stop.seen)
281
def get_child_map(self, keys):
282
"""Get a mapping from parents to children of the specified keys.
284
This is simply the inversion of get_parent_map. Only supplied keys
285
will be discovered as children.
286
:return: a dict of key:child_list for keys.
288
parent_map = self._parents_provider.get_parent_map(keys)
290
for child, parents in sorted(parent_map.items()):
291
for parent in parents:
292
parent_child.setdefault(parent, []).append(child)
295
def find_distance_to_null(self, target_revision_id, known_revision_ids):
296
"""Find the left-hand distance to the NULL_REVISION.
298
(This can also be considered the revno of a branch at
301
:param target_revision_id: A revision_id which we would like to know
303
:param known_revision_ids: [(revision_id, revno)] A list of known
304
revno, revision_id tuples. We'll use this to seed the search.
306
# Map from revision_ids to a known value for their revno
307
known_revnos = dict(known_revision_ids)
308
cur_tip = target_revision_id
310
NULL_REVISION = revision.NULL_REVISION
311
known_revnos[NULL_REVISION] = 0
313
searching_known_tips = list(known_revnos.keys())
315
unknown_searched = {}
317
while cur_tip not in known_revnos:
318
unknown_searched[cur_tip] = num_steps
320
to_search = set([cur_tip])
321
to_search.update(searching_known_tips)
322
parent_map = self.get_parent_map(to_search)
323
parents = parent_map.get(cur_tip, None)
324
if not parents: # An empty list or None is a ghost
325
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
329
for revision_id in searching_known_tips:
330
parents = parent_map.get(revision_id, None)
334
next_revno = known_revnos[revision_id] - 1
335
if next in unknown_searched:
336
# We have enough information to return a value right now
337
return next_revno + unknown_searched[next]
338
if next in known_revnos:
340
known_revnos[next] = next_revno
341
next_known_tips.append(next)
342
searching_known_tips = next_known_tips
344
# We reached a known revision, so just add in how many steps it took to
346
return known_revnos[cur_tip] + num_steps
348
def find_lefthand_distances(self, keys):
349
"""Find the distance to null for all the keys in keys.
351
:param keys: keys to lookup.
352
:return: A dict key->distance for all of keys.
354
# Optimisable by concurrent searching, but a random spread should get
355
# some sort of hit rate.
362
(key, self.find_distance_to_null(key, known_revnos)))
363
except errors.GhostRevisionsHaveNoRevno:
366
known_revnos.append((key, -1))
367
return dict(known_revnos)
369
def find_unique_ancestors(self, unique_revision, common_revisions):
370
"""Find the unique ancestors for a revision versus others.
372
This returns the ancestry of unique_revision, excluding all revisions
373
in the ancestry of common_revisions. If unique_revision is in the
374
ancestry, then the empty set will be returned.
376
:param unique_revision: The revision_id whose ancestry we are
378
XXX: Would this API be better if we allowed multiple revisions on
380
:param common_revisions: Revision_ids of ancestries to exclude.
381
:return: A set of revisions in the ancestry of unique_revision
383
if unique_revision in common_revisions:
386
# Algorithm description
387
# 1) Walk backwards from the unique node and all common nodes.
388
# 2) When a node is seen by both sides, stop searching it in the unique
389
# walker, include it in the common walker.
390
# 3) Stop searching when there are no nodes left for the unique walker.
391
# At this point, you have a maximal set of unique nodes. Some of
392
# them may actually be common, and you haven't reached them yet.
393
# 4) Start new searchers for the unique nodes, seeded with the
394
# information you have so far.
395
# 5) Continue searching, stopping the common searches when the search
396
# tip is an ancestor of all unique nodes.
397
# 6) Aggregate together unique searchers when they are searching the
398
# same tips. When all unique searchers are searching the same node,
399
# stop move it to a single 'all_unique_searcher'.
400
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
401
# Most of the time this produces very little important information.
402
# So don't step it as quickly as the other searchers.
403
# 8) Search is done when all common searchers have completed.
405
unique_searcher, common_searcher = self._find_initial_unique_nodes(
406
[unique_revision], common_revisions)
408
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
412
(all_unique_searcher,
413
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
414
unique_searcher, common_searcher)
416
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
417
unique_tip_searchers, common_searcher)
418
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
419
if 'graph' in debug.debug_flags:
420
trace.mutter('Found %d truly unique nodes out of %d',
421
len(true_unique_nodes), len(unique_nodes))
422
return true_unique_nodes
424
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
425
"""Steps 1-3 of find_unique_ancestors.
427
Find the maximal set of unique nodes. Some of these might actually
428
still be common, but we are sure that there are no other unique nodes.
430
:return: (unique_searcher, common_searcher)
433
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
434
# we know that unique_revisions aren't in common_revisions, so skip
436
unique_searcher.next()
437
common_searcher = self._make_breadth_first_searcher(common_revisions)
439
# As long as we are still finding unique nodes, keep searching
440
while unique_searcher._next_query:
441
next_unique_nodes = set(unique_searcher.step())
442
next_common_nodes = set(common_searcher.step())
444
# Check if either searcher encounters new nodes seen by the other
446
unique_are_common_nodes = next_unique_nodes.intersection(
447
common_searcher.seen)
448
unique_are_common_nodes.update(
449
next_common_nodes.intersection(unique_searcher.seen))
450
if unique_are_common_nodes:
451
ancestors = unique_searcher.find_seen_ancestors(
452
unique_are_common_nodes)
453
# TODO: This is a bit overboard, we only really care about
454
# the ancestors of the tips because the rest we
455
# already know. This is *correct* but causes us to
456
# search too much ancestry.
457
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
458
unique_searcher.stop_searching_any(ancestors)
459
common_searcher.start_searching(ancestors)
461
return unique_searcher, common_searcher
463
def _make_unique_searchers(self, unique_nodes, unique_searcher,
465
"""Create a searcher for all the unique search tips (step 4).
467
As a side effect, the common_searcher will stop searching any nodes
468
that are ancestors of the unique searcher tips.
470
:return: (all_unique_searcher, unique_tip_searchers)
472
unique_tips = self._remove_simple_descendants(unique_nodes,
473
self.get_parent_map(unique_nodes))
475
if len(unique_tips) == 1:
476
unique_tip_searchers = []
477
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
479
unique_tip_searchers = []
480
for tip in unique_tips:
481
revs_to_search = unique_searcher.find_seen_ancestors([tip])
482
revs_to_search.update(
483
common_searcher.find_seen_ancestors(revs_to_search))
484
searcher = self._make_breadth_first_searcher(revs_to_search)
485
# We don't care about the starting nodes.
486
searcher._label = tip
488
unique_tip_searchers.append(searcher)
490
ancestor_all_unique = None
491
for searcher in unique_tip_searchers:
492
if ancestor_all_unique is None:
493
ancestor_all_unique = set(searcher.seen)
495
ancestor_all_unique = ancestor_all_unique.intersection(
497
# Collapse all the common nodes into a single searcher
498
all_unique_searcher = self._make_breadth_first_searcher(
500
if ancestor_all_unique:
501
# We've seen these nodes in all the searchers, so we'll just go to
503
all_unique_searcher.step()
505
# Stop any search tips that are already known as ancestors of the
507
stopped_common = common_searcher.stop_searching_any(
508
common_searcher.find_seen_ancestors(ancestor_all_unique))
511
for searcher in unique_tip_searchers:
512
total_stopped += len(searcher.stop_searching_any(
513
searcher.find_seen_ancestors(ancestor_all_unique)))
514
if 'graph' in debug.debug_flags:
515
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
516
' (%d stopped search tips, %d common ancestors'
517
' (%d stopped common)',
518
len(unique_nodes), len(unique_tip_searchers),
519
total_stopped, len(ancestor_all_unique),
521
return all_unique_searcher, unique_tip_searchers
523
def _step_unique_and_common_searchers(self, common_searcher,
524
unique_tip_searchers,
526
"""Step all the searchers"""
527
newly_seen_common = set(common_searcher.step())
528
newly_seen_unique = set()
529
for searcher in unique_tip_searchers:
530
next = set(searcher.step())
531
next.update(unique_searcher.find_seen_ancestors(next))
532
next.update(common_searcher.find_seen_ancestors(next))
533
for alt_searcher in unique_tip_searchers:
534
if alt_searcher is searcher:
536
next.update(alt_searcher.find_seen_ancestors(next))
537
searcher.start_searching(next)
538
newly_seen_unique.update(next)
539
return newly_seen_common, newly_seen_unique
541
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
543
newly_seen_unique, step_all_unique):
544
"""Find nodes that are common to all unique_tip_searchers.
546
If it is time, step the all_unique_searcher, and add its nodes to the
549
common_to_all_unique_nodes = newly_seen_unique.copy()
550
for searcher in unique_tip_searchers:
551
common_to_all_unique_nodes.intersection_update(searcher.seen)
552
common_to_all_unique_nodes.intersection_update(
553
all_unique_searcher.seen)
554
# Step all-unique less frequently than the other searchers.
555
# In the common case, we don't need to spider out far here, so
556
# avoid doing extra work.
558
tstart = time.clock()
559
nodes = all_unique_searcher.step()
560
common_to_all_unique_nodes.update(nodes)
561
if 'graph' in debug.debug_flags:
562
tdelta = time.clock() - tstart
563
trace.mutter('all_unique_searcher step() took %.3fs'
564
'for %d nodes (%d total), iteration: %s',
565
tdelta, len(nodes), len(all_unique_searcher.seen),
566
all_unique_searcher._iterations)
567
return common_to_all_unique_nodes
569
def _collapse_unique_searchers(self, unique_tip_searchers,
570
common_to_all_unique_nodes):
571
"""Combine searchers that are searching the same tips.
573
When two searchers are searching the same tips, we can stop one of the
574
searchers. We also know that the maximal set of common ancestors is the
575
intersection of the two original searchers.
577
:return: A list of searchers that are searching unique nodes.
579
# Filter out searchers that don't actually search different
580
# nodes. We already have the ancestry intersection for them
581
unique_search_tips = {}
582
for searcher in unique_tip_searchers:
583
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
584
will_search_set = frozenset(searcher._next_query)
585
if not will_search_set:
586
if 'graph' in debug.debug_flags:
587
trace.mutter('Unique searcher %s was stopped.'
588
' (%s iterations) %d nodes stopped',
590
searcher._iterations,
592
elif will_search_set not in unique_search_tips:
593
# This searcher is searching a unique set of nodes, let it
594
unique_search_tips[will_search_set] = [searcher]
596
unique_search_tips[will_search_set].append(searcher)
597
# TODO: it might be possible to collapse searchers faster when they
598
# only have *some* search tips in common.
599
next_unique_searchers = []
600
for searchers in unique_search_tips.itervalues():
601
if len(searchers) == 1:
602
# Searching unique tips, go for it
603
next_unique_searchers.append(searchers[0])
605
# These searchers have started searching the same tips, we
606
# don't need them to cover the same ground. The
607
# intersection of their ancestry won't change, so create a
608
# new searcher, combining their histories.
609
next_searcher = searchers[0]
610
for searcher in searchers[1:]:
611
next_searcher.seen.intersection_update(searcher.seen)
612
if 'graph' in debug.debug_flags:
613
trace.mutter('Combining %d searchers into a single'
614
' searcher searching %d nodes with'
617
len(next_searcher._next_query),
618
len(next_searcher.seen))
619
next_unique_searchers.append(next_searcher)
620
return next_unique_searchers
622
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
623
unique_tip_searchers, common_searcher):
624
"""Steps 5-8 of find_unique_ancestors.
626
This function returns when common_searcher has stopped searching for
629
# We step the ancestor_all_unique searcher only every
630
# STEP_UNIQUE_SEARCHER_EVERY steps.
631
step_all_unique_counter = 0
632
# While we still have common nodes to search
633
while common_searcher._next_query:
635
newly_seen_unique) = self._step_unique_and_common_searchers(
636
common_searcher, unique_tip_searchers, unique_searcher)
637
# These nodes are common ancestors of all unique nodes
638
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
639
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
640
step_all_unique_counter==0)
641
step_all_unique_counter = ((step_all_unique_counter + 1)
642
% STEP_UNIQUE_SEARCHER_EVERY)
644
if newly_seen_common:
645
# If a 'common' node is an ancestor of all unique searchers, we
646
# can stop searching it.
647
common_searcher.stop_searching_any(
648
all_unique_searcher.seen.intersection(newly_seen_common))
649
if common_to_all_unique_nodes:
650
common_to_all_unique_nodes.update(
651
common_searcher.find_seen_ancestors(
652
common_to_all_unique_nodes))
653
# The all_unique searcher can start searching the common nodes
654
# but everyone else can stop.
655
# This is the sort of thing where we would like to not have it
656
# start_searching all of the nodes, but only mark all of them
657
# as seen, and have it search only the actual tips. Otherwise
658
# it is another get_parent_map() traversal for it to figure out
659
# what we already should know.
660
all_unique_searcher.start_searching(common_to_all_unique_nodes)
661
common_searcher.stop_searching_any(common_to_all_unique_nodes)
663
next_unique_searchers = self._collapse_unique_searchers(
664
unique_tip_searchers, common_to_all_unique_nodes)
665
if len(unique_tip_searchers) != len(next_unique_searchers):
666
if 'graph' in debug.debug_flags:
667
trace.mutter('Collapsed %d unique searchers => %d'
669
len(unique_tip_searchers),
670
len(next_unique_searchers),
671
all_unique_searcher._iterations)
672
unique_tip_searchers = next_unique_searchers
674
def get_parent_map(self, revisions):
675
"""Get a map of key:parent_list for revisions.
677
This implementation delegates to get_parents, for old parent_providers
678
that do not supply get_parent_map.
681
for rev, parents in self.get_parents(revisions):
682
if parents is not None:
683
result[rev] = parents
143
return (left.difference(right).difference(common),
144
right.difference(left).difference(common))
686
146
def _make_breadth_first_searcher(self, revisions):
687
147
return _BreadthFirstSearcher(revisions, self)
703
163
if None in revisions:
704
164
raise errors.InvalidRevisionId(None, self)
165
common_searcher = self._make_breadth_first_searcher([])
705
166
common_ancestors = set()
706
167
searchers = [self._make_breadth_first_searcher([r])
707
168
for r in revisions]
708
169
active_searchers = searchers[:]
709
170
border_ancestors = set()
171
def update_common(searcher, revisions):
172
w_seen_ancestors = searcher.find_seen_ancestors(
174
stopped = searcher.stop_searching_any(w_seen_ancestors)
175
common_ancestors.update(w_seen_ancestors)
176
common_searcher.start_searching(stopped)
179
if len(active_searchers) == 0:
180
return border_ancestors, common_ancestors, [s.seen for s in
183
new_common = common_searcher.next()
184
common_ancestors.update(new_common)
185
except StopIteration:
188
for searcher in active_searchers:
189
for revision in new_common.intersection(searcher.seen):
190
update_common(searcher, revision)
712
192
newly_seen = set()
713
for searcher in searchers:
714
new_ancestors = searcher.step()
716
newly_seen.update(new_ancestors)
193
new_active_searchers = []
194
for searcher in active_searchers:
196
newly_seen.update(searcher.next())
197
except StopIteration:
200
new_active_searchers.append(searcher)
201
active_searchers = new_active_searchers
718
202
for revision in newly_seen:
719
203
if revision in common_ancestors:
720
# Not a border ancestor because it was seen as common
722
new_common.add(revision)
204
for searcher in searchers:
205
update_common(searcher, revision)
724
207
for searcher in searchers:
725
208
if revision not in searcher.seen:
728
# This is a border because it is a first common that we see
729
# after walking for a while.
730
211
border_ancestors.add(revision)
731
new_common.add(revision)
733
for searcher in searchers:
734
new_common.update(searcher.find_seen_ancestors(new_common))
735
for searcher in searchers:
736
searcher.start_searching(new_common)
737
common_ancestors.update(new_common)
739
# Figure out what the searchers will be searching next, and if
740
# there is only 1 set being searched, then we are done searching,
741
# since all searchers would have to be searching the same data,
742
# thus it *must* be in common.
743
unique_search_sets = set()
744
for searcher in searchers:
745
will_search_set = frozenset(searcher._next_query)
746
if will_search_set not in unique_search_sets:
747
# This searcher is searching a unique set of nodes, let it
748
unique_search_sets.add(will_search_set)
750
if len(unique_search_sets) == 1:
751
nodes = unique_search_sets.pop()
752
uncommon_nodes = nodes.difference(common_ancestors)
754
raise AssertionError("Somehow we ended up converging"
755
" without actually marking them as"
758
"\nuncommon_nodes: %s"
759
% (revisions, uncommon_nodes))
761
return border_ancestors, common_ancestors, searchers
763
def heads(self, keys):
764
"""Return the heads from amongst keys.
766
This is done by searching the ancestries of each key. Any key that is
767
reachable from another key is not returned; all the others are.
769
This operation scales with the relative depth between any two keys. If
770
any two keys are completely disconnected all ancestry of both sides
773
:param keys: An iterable of keys.
774
:return: A set of the heads. Note that as a set there is no ordering
775
information. Callers will need to filter their input to create
776
order if they need it.
212
for searcher in searchers:
213
update_common(searcher, revision)
215
def _filter_candidate_lca(self, candidate_lca):
216
"""Remove candidates which are ancestors of other candidates.
218
This is done by searching the ancestries of each border ancestor. It
219
is perfomed on the principle that a border ancestor that is not an
220
ancestor of any other border ancestor is a lowest common ancestor.
222
Searches are stopped when they find a node that is determined to be a
223
common ancestor of all border ancestors, because this shows that it
224
cannot be a descendant of any border ancestor.
226
This will scale with the number of candidate ancestors and the length
227
of the shortest path from a candidate to an ancestor common to all
778
candidate_heads = set(keys)
779
if revision.NULL_REVISION in candidate_heads:
780
# NULL_REVISION is only a head if it is the only entry
781
candidate_heads.remove(revision.NULL_REVISION)
782
if not candidate_heads:
783
return set([revision.NULL_REVISION])
784
if len(candidate_heads) < 2:
785
return candidate_heads
786
230
searchers = dict((c, self._make_breadth_first_searcher([c]))
787
for c in candidate_heads)
231
for c in candidate_lca)
788
232
active_searchers = dict(searchers)
789
233
# skip over the actual candidate for each searcher
790
234
for searcher in active_searchers.itervalues():
792
# The common walker finds nodes that are common to two or more of the
793
# input keys, so that we don't access all history when a currently
794
# uncommon search point actually meets up with something behind a
795
# common search point. Common search points do not keep searches
796
# active; they just allow us to make searches inactive without
797
# accessing all history.
798
common_walker = self._make_breadth_first_searcher([])
799
236
while len(active_searchers) > 0:
804
except StopIteration:
805
# No common points being searched at this time.
807
237
for candidate in active_searchers.keys():
809
239
searcher = active_searchers[candidate]
813
243
# a descendant of another candidate.
816
ancestors.update(searcher.next())
246
ancestors = searcher.next()
817
247
except StopIteration:
818
248
del active_searchers[candidate]
820
# process found nodes
822
for ancestor in ancestors:
823
if ancestor in candidate_heads:
824
candidate_heads.remove(ancestor)
825
del searchers[ancestor]
826
if ancestor in active_searchers:
827
del active_searchers[ancestor]
828
# it may meet up with a known common node
829
if ancestor in common_walker.seen:
830
# some searcher has encountered our known common nodes:
832
ancestor_set = set([ancestor])
833
for searcher in searchers.itervalues():
834
searcher.stop_searching_any(ancestor_set)
836
# or it may have been just reached by all the searchers:
250
for ancestor in ancestors:
251
if ancestor in candidate_lca:
252
candidate_lca.remove(ancestor)
253
del searchers[ancestor]
254
if ancestor in active_searchers:
255
del active_searchers[ancestor]
837
256
for searcher in searchers.itervalues():
838
257
if ancestor not in searcher.seen:
841
# The final active searcher has just reached this node,
842
# making it be known as a descendant of all candidates,
843
# so we can stop searching it, and any seen ancestors
844
new_common.add(ancestor)
260
# if this revision was seen by all searchers, then it
261
# is a descendant of all candidates, so we can stop
262
# searching it, and any seen ancestors
845
263
for searcher in searchers.itervalues():
846
264
seen_ancestors =\
847
searcher.find_seen_ancestors([ancestor])
265
searcher.find_seen_ancestors(ancestor)
848
266
searcher.stop_searching_any(seen_ancestors)
849
common_walker.start_searching(new_common)
850
return candidate_heads
852
def find_merge_order(self, tip_revision_id, lca_revision_ids):
853
"""Find the order that each revision was merged into tip.
855
This basically just walks backwards with a stack, and walks left-first
856
until it finds a node to stop.
858
if len(lca_revision_ids) == 1:
859
return list(lca_revision_ids)
860
looking_for = set(lca_revision_ids)
861
# TODO: Is there a way we could do this "faster" by batching up the
862
# get_parent_map requests?
863
# TODO: Should we also be culling the ancestry search right away? We
864
# could add looking_for to the "stop" list, and walk their
865
# ancestry in batched mode. The flip side is it might mean we walk a
866
# lot of "stop" nodes, rather than only the minimum.
867
# Then again, without it we may trace back into ancestry we could have
869
stack = [tip_revision_id]
872
while stack and looking_for:
875
if next in looking_for:
877
looking_for.remove(next)
878
if len(looking_for) == 1:
879
found.append(looking_for.pop())
882
parent_ids = self.get_parent_map([next]).get(next, None)
883
if not parent_ids: # Ghost, nothing to search here
885
for parent_id in reversed(parent_ids):
886
# TODO: (performance) We see the parent at this point, but we
887
# wait to mark it until later to make sure we get left
888
# parents before right parents. However, instead of
889
# waiting until we have traversed enough parents, we
890
# could instead note that we've found it, and once all
891
# parents are in the stack, just reverse iterate the
893
if parent_id not in stop:
894
# this will need to be searched
895
stack.append(parent_id)
899
def find_lefthand_merger(self, merged_key, tip_key):
900
"""Find the first lefthand ancestor of tip_key that merged merged_key.
902
We do this by first finding the descendants of merged_key, then
903
walking through the lefthand ancestry of tip_key until we find a key
904
that doesn't descend from merged_key. Its child is the key that
907
:return: The first lefthand ancestor of tip_key to merge merged_key.
908
merged_key if it is a lefthand ancestor of tip_key.
909
None if no ancestor of tip_key merged merged_key.
911
descendants = self.find_descendants(merged_key, tip_key)
912
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
913
last_candidate = None
914
for candidate in candidate_iterator:
915
if candidate not in descendants:
916
return last_candidate
917
last_candidate = candidate
919
def find_unique_lca(self, left_revision, right_revision,
269
def find_unique_lca(self, left_revision, right_revision):
921
270
"""Find a unique LCA.
923
272
Find lowest common ancestors. If there is no unique common
999
294
An ancestor may sort after a descendant if the relationship is not
1000
295
visible in the supplied list of revisions.
1002
from bzrlib import tsort
1003
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
297
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
1004
298
return sorter.iter_topo_order()
1006
300
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1007
301
"""Determine whether a revision is an ancestor of another.
1009
We answer this using heads() as heads() has the logic to perform the
1010
smallest number of parent lookups to determine the ancestral
1011
relationship between N revisions.
1013
return set([candidate_descendant]) == self.heads(
1014
[candidate_ancestor, candidate_descendant])
1016
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1017
"""Determine whether a revision is between two others.
1019
returns true if and only if:
1020
lower_bound_revid <= revid <= upper_bound_revid
1022
return ((upper_bound_revid is None or
1023
self.is_ancestor(revid, upper_bound_revid)) and
1024
(lower_bound_revid is None or
1025
self.is_ancestor(lower_bound_revid, revid)))
1027
def _search_for_extra_common(self, common, searchers):
1028
"""Make sure that unique nodes are genuinely unique.
1030
After _find_border_ancestors, all nodes marked "common" are indeed
1031
common. Some of the nodes considered unique are not, due to history
1032
shortcuts stopping the searches early.
1034
We know that we have searched enough when all common search tips are
1035
descended from all unique (uncommon) nodes because we know that a node
1036
cannot be an ancestor of its own ancestor.
1038
:param common: A set of common nodes
1039
:param searchers: The searchers returned from _find_border_ancestors
1042
# Basic algorithm...
1043
# A) The passed in searchers should all be on the same tips, thus
1044
# they should be considered the "common" searchers.
1045
# B) We find the difference between the searchers, these are the
1046
# "unique" nodes for each side.
1047
# C) We do a quick culling so that we only start searching from the
1048
# more interesting unique nodes. (A unique ancestor is more
1049
# interesting than any of its children.)
1050
# D) We start searching for ancestors common to all unique nodes.
1051
# E) We have the common searchers stop searching any ancestors of
1052
# nodes found by (D)
1053
# F) When there are no more common search tips, we stop
1055
# TODO: We need a way to remove unique_searchers when they overlap with
1056
# other unique searchers.
1057
if len(searchers) != 2:
1058
raise NotImplementedError(
1059
"Algorithm not yet implemented for > 2 searchers")
1060
common_searchers = searchers
1061
left_searcher = searchers[0]
1062
right_searcher = searchers[1]
1063
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1064
if not unique: # No unique nodes, nothing to do
1066
total_unique = len(unique)
1067
unique = self._remove_simple_descendants(unique,
1068
self.get_parent_map(unique))
1069
simple_unique = len(unique)
1071
unique_searchers = []
1072
for revision_id in unique:
1073
if revision_id in left_searcher.seen:
1074
parent_searcher = left_searcher
1076
parent_searcher = right_searcher
1077
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1078
if not revs_to_search: # XXX: This shouldn't be possible
1079
revs_to_search = [revision_id]
1080
searcher = self._make_breadth_first_searcher(revs_to_search)
1081
# We don't care about the starting nodes.
1083
unique_searchers.append(searcher)
1085
# possible todo: aggregate the common searchers into a single common
1086
# searcher, just make sure that we include the nodes into the .seen
1087
# properties of the original searchers
1089
ancestor_all_unique = None
1090
for searcher in unique_searchers:
1091
if ancestor_all_unique is None:
1092
ancestor_all_unique = set(searcher.seen)
1094
ancestor_all_unique = ancestor_all_unique.intersection(
1097
trace.mutter('Started %s unique searchers for %s unique revisions',
1098
simple_unique, total_unique)
1100
while True: # If we have no more nodes we have nothing to do
1101
newly_seen_common = set()
1102
for searcher in common_searchers:
1103
newly_seen_common.update(searcher.step())
1104
newly_seen_unique = set()
1105
for searcher in unique_searchers:
1106
newly_seen_unique.update(searcher.step())
1107
new_common_unique = set()
1108
for revision in newly_seen_unique:
1109
for searcher in unique_searchers:
1110
if revision not in searcher.seen:
1113
# This is a border because it is a first common that we see
1114
# after walking for a while.
1115
new_common_unique.add(revision)
1116
if newly_seen_common:
1117
# These are nodes descended from one of the 'common' searchers.
1118
# Make sure all searchers are on the same page
1119
for searcher in common_searchers:
1120
newly_seen_common.update(
1121
searcher.find_seen_ancestors(newly_seen_common))
1122
# We start searching the whole ancestry. It is a bit wasteful,
1123
# though. We really just want to mark all of these nodes as
1124
# 'seen' and then start just the tips. However, it requires a
1125
# get_parent_map() call to figure out the tips anyway, and all
1126
# redundant requests should be fairly fast.
1127
for searcher in common_searchers:
1128
searcher.start_searching(newly_seen_common)
1130
# If a 'common' node is an ancestor of all unique searchers, we
1131
# can stop searching it.
1132
stop_searching_common = ancestor_all_unique.intersection(
1134
if stop_searching_common:
1135
for searcher in common_searchers:
1136
searcher.stop_searching_any(stop_searching_common)
1137
if new_common_unique:
1138
# We found some ancestors that are common
1139
for searcher in unique_searchers:
1140
new_common_unique.update(
1141
searcher.find_seen_ancestors(new_common_unique))
1142
# Since these are common, we can grab another set of ancestors
1144
for searcher in common_searchers:
1145
new_common_unique.update(
1146
searcher.find_seen_ancestors(new_common_unique))
1148
# We can tell all of the unique searchers to start at these
1149
# nodes, and tell all of the common searchers to *stop*
1150
# searching these nodes
1151
for searcher in unique_searchers:
1152
searcher.start_searching(new_common_unique)
1153
for searcher in common_searchers:
1154
searcher.stop_searching_any(new_common_unique)
1155
ancestor_all_unique.update(new_common_unique)
1157
# Filter out searchers that don't actually search different
1158
# nodes. We already have the ancestry intersection for them
1159
next_unique_searchers = []
1160
unique_search_sets = set()
1161
for searcher in unique_searchers:
1162
will_search_set = frozenset(searcher._next_query)
1163
if will_search_set not in unique_search_sets:
1164
# This searcher is searching a unique set of nodes, let it
1165
unique_search_sets.add(will_search_set)
1166
next_unique_searchers.append(searcher)
1167
unique_searchers = next_unique_searchers
1168
for searcher in common_searchers:
1169
if searcher._next_query:
1172
# All common searcher have stopped searching
1175
def _remove_simple_descendants(self, revisions, parent_map):
1176
"""remove revisions which are children of other ones in the set
1178
This doesn't do any graph searching, it just checks the immediate
1179
parent_map to find if there are any children which can be removed.
1181
:param revisions: A set of revision_ids
1182
:return: A set of revision_ids with the children removed
1184
simple_ancestors = revisions.copy()
1185
# TODO: jam 20071214 we *could* restrict it to searching only the
1186
# parent_map of revisions already present in 'revisions', but
1187
# considering the general use case, I think this is actually
1190
# This is the same as the following loop. I don't know that it is any
1192
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1193
## if p_ids is not None and revisions.intersection(p_ids))
1194
## return simple_ancestors
1196
# Yet Another Way, invert the parent map (which can be cached)
1198
## for revision_id, parent_ids in parent_map.iteritems():
1199
## for p_id in parent_ids:
1200
## descendants.setdefault(p_id, []).append(revision_id)
1201
## for revision in revisions.intersection(descendants):
1202
## simple_ancestors.difference_update(descendants[revision])
1203
## return simple_ancestors
1204
for revision, parent_ids in parent_map.iteritems():
1205
if parent_ids is None:
1207
for parent_id in parent_ids:
1208
if parent_id in revisions:
1209
# This node has a parent present in the set, so we can
1211
simple_ancestors.discard(revision)
1213
return simple_ancestors
1216
class HeadsCache(object):
1217
"""A cache of results for graph heads calls."""
1219
def __init__(self, graph):
1223
def heads(self, keys):
1224
"""Return the heads of keys.
1226
This matches the API of Graph.heads(), specifically the return value is
1227
a set which can be mutated, and ordering of the input is not preserved
1230
:see also: Graph.heads.
1231
:param keys: The keys to calculate heads for.
1232
:return: A set containing the heads, which may be mutated without
1233
affecting future lookups.
1235
keys = frozenset(keys)
1237
return set(self._heads[keys])
1239
heads = self.graph.heads(keys)
1240
self._heads[keys] = heads
1244
class FrozenHeadsCache(object):
1245
"""Cache heads() calls, assuming the caller won't modify them."""
1247
def __init__(self, graph):
1251
def heads(self, keys):
1252
"""Return the heads of keys.
1254
Similar to Graph.heads(). The main difference is that the return value
1255
is a frozen set which cannot be mutated.
1257
:see also: Graph.heads.
1258
:param keys: The keys to calculate heads for.
1259
:return: A frozenset containing the heads.
1261
keys = frozenset(keys)
1263
return self._heads[keys]
1265
heads = frozenset(self.graph.heads(keys))
1266
self._heads[keys] = heads
1269
def cache(self, keys, heads):
1270
"""Store a known value."""
1271
self._heads[frozenset(keys)] = frozenset(heads)
303
There are two possible outcomes: True and False, but there are three
304
possible relationships:
306
a) candidate_ancestor is an ancestor of candidate_descendant
307
b) candidate_ancestor is an descendant of candidate_descendant
308
c) candidate_ancestor is an sibling of candidate_descendant
310
To check for a, we walk from candidate_descendant, looking for
313
To check for b, we walk from candidate_ancestor, looking for
314
candidate_descendant.
316
To make a and b more efficient, we can stop any searches that hit
319
If we exhaust our searches, but neither a or b is true, then c is true.
321
In order to find c efficiently, we must avoid searching from
322
candidate_descendant or candidate_ancestor into common ancestors. But
323
if we don't search common ancestors at all, we won't know if we hit
324
common ancestors. So we have a walker for common ancestors. Note that
325
its searches are not required to terminate in order to determine c to
328
ancestor_walker = self._make_breadth_first_searcher(
329
[candidate_ancestor])
330
descendant_walker = self._make_breadth_first_searcher(
331
[candidate_descendant])
332
common_walker = self._make_breadth_first_searcher([])
333
active_ancestor = True
334
active_descendant = True
335
while (active_ancestor or active_descendant):
337
if active_descendant:
339
nodes = descendant_walker.next()
340
except StopIteration:
341
active_descendant = False
343
if candidate_ancestor in nodes:
345
new_common.update(nodes.intersection(ancestor_walker.seen))
348
nodes = ancestor_walker.next()
349
except StopIteration:
350
active_ancestor = False
352
if candidate_descendant in nodes:
354
new_common.update(nodes.intersection(
355
descendant_walker.seen))
357
new_common.update(common_walker.next())
358
except StopIteration:
360
for walker in (ancestor_walker, descendant_walker):
361
for node in new_common:
362
c_ancestors = walker.find_seen_ancestors(node)
363
walker.stop_searching_any(c_ancestors)
364
common_walker.start_searching(new_common)
1274
368
class _BreadthFirstSearcher(object):
1275
"""Parallel search breadth-first the ancestry of revisions.
369
"""Parallel search the breadth-first the ancestry of revisions.
1277
371
This class implements the iterator protocol, but additionally
1278
372
1. provides a set of seen ancestors, and
1282
376
def __init__(self, revisions, parents_provider):
1283
self._iterations = 0
1284
self._next_query = set(revisions)
1286
self._started_keys = set(self._next_query)
1287
self._stopped_keys = set()
1288
self._parents_provider = parents_provider
1289
self._returning = 'next_with_ghosts'
1290
self._current_present = set()
1291
self._current_ghosts = set()
1292
self._current_parents = {}
377
self._start = set(revisions)
378
self._search_revisions = None
379
self.seen = set(revisions)
380
self._parents_provider = parents_provider
1294
382
def __repr__(self):
1295
if self._iterations:
1296
prefix = "searching"
1299
search = '%s=%r' % (prefix, list(self._next_query))
1300
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1301
' seen=%r)' % (self._iterations, search, list(self.seen)))
1303
def get_result(self):
1304
"""Get a SearchResult for the current state of this searcher.
1306
:return: A SearchResult for this search so far. The SearchResult is
1307
static - the search can be advanced and the search result will not
1308
be invalidated or altered.
1310
if self._returning == 'next':
1311
# We have to know the current nodes children to be able to list the
1312
# exclude keys for them. However, while we could have a second
1313
# look-ahead result buffer and shuffle things around, this method
1314
# is typically only called once per search - when memoising the
1315
# results of the search.
1316
found, ghosts, next, parents = self._do_query(self._next_query)
1317
# pretend we didn't query: perhaps we should tweak _do_query to be
1318
# entirely stateless?
1319
self.seen.difference_update(next)
1320
next_query = next.union(ghosts)
1322
next_query = self._next_query
1323
excludes = self._stopped_keys.union(next_query)
1324
included_keys = self.seen.difference(excludes)
1325
return SearchResult(self._started_keys, excludes, len(included_keys),
1331
except StopIteration:
383
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
384
' self.seen=%r)' % (self._search_revisions, self.seen))
1335
387
"""Return the next ancestors of this revision.
1337
389
Ancestors are returned in the order they are seen in a breadth-first
1338
traversal. No ancestor will be returned more than once. Ancestors are
1339
returned before their parentage is queried, so ghosts and missing
1340
revisions (including the start revisions) are included in the result.
1341
This can save a round trip in LCA style calculation by allowing
1342
convergence to be detected without reading the data for the revision
1343
the convergence occurs on.
1345
:return: A set of revision_ids.
390
traversal. No ancestor will be returned more than once.
1347
if self._returning != 'next':
1348
# switch to returning the query, not the results.
1349
self._returning = 'next'
1350
self._iterations += 1
392
if self._search_revisions is None:
393
self._search_revisions = self._start
1353
if len(self._next_query) == 0:
1354
raise StopIteration()
1355
# We have seen what we're querying at this point as we are returning
1356
# the query, not the results.
1357
self.seen.update(self._next_query)
1358
return self._next_query
1360
def next_with_ghosts(self):
1361
"""Return the next found ancestors, with ghosts split out.
1363
Ancestors are returned in the order they are seen in a breadth-first
1364
traversal. No ancestor will be returned more than once. Ancestors are
1365
returned only after asking for their parents, which allows us to detect
1366
which revisions are ghosts and which are not.
1368
:return: A tuple with (present ancestors, ghost ancestors) sets.
1370
if self._returning != 'next_with_ghosts':
1371
# switch to returning the results, not the current query.
1372
self._returning = 'next_with_ghosts'
1374
if len(self._next_query) == 0:
1375
raise StopIteration()
1377
return self._current_present, self._current_ghosts
1380
"""Advance the search.
1382
Updates self.seen, self._next_query, self._current_present,
1383
self._current_ghosts, self._current_parents and self._iterations.
1385
self._iterations += 1
1386
found, ghosts, next, parents = self._do_query(self._next_query)
1387
self._current_present = found
1388
self._current_ghosts = ghosts
1389
self._next_query = next
1390
self._current_parents = parents
1391
# ghosts are implicit stop points, otherwise the search cannot be
1392
# repeated when ghosts are filled.
1393
self._stopped_keys.update(ghosts)
1395
def _do_query(self, revisions):
1396
"""Query for revisions.
1398
Adds revisions to the seen set.
1400
:param revisions: Revisions to query.
1401
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1402
set(parents_of_found_revisions), dict(found_revisions:parents)).
1404
found_revisions = set()
1405
parents_of_found = set()
1406
# revisions may contain nodes that point to other nodes in revisions:
1407
# we want to filter them out.
1408
self.seen.update(revisions)
1409
parent_map = self._parents_provider.get_parent_map(revisions)
1410
found_revisions.update(parent_map)
1411
for rev_id, parents in parent_map.iteritems():
1414
new_found_parents = [p for p in parents if p not in self.seen]
1415
if new_found_parents:
1416
# Calling set.update() with an empty generator is actually
1418
parents_of_found.update(new_found_parents)
1419
ghost_revisions = revisions - found_revisions
1420
return found_revisions, ghost_revisions, parents_of_found, parent_map
395
new_search_revisions = set()
396
for parents in self._parents_provider.get_parents(
397
self._search_revisions):
400
new_search_revisions.update(p for p in parents if
402
self._search_revisions = new_search_revisions
403
if len(self._search_revisions) == 0:
404
raise StopIteration()
405
self.seen.update(self._search_revisions)
406
return self._search_revisions
1422
408
def __iter__(self):
1425
def find_seen_ancestors(self, revisions):
1426
"""Find ancestors of these revisions that have already been seen.
1428
This function generally makes the assumption that querying for the
1429
parents of a node that has already been queried is reasonably cheap.
1430
(eg, not a round trip to a remote host).
1432
# TODO: Often we might ask one searcher for its seen ancestors, and
1433
# then ask another searcher the same question. This can result in
1434
# searching the same revisions repeatedly if the two searchers
1435
# have a lot of overlap.
1436
all_seen = self.seen
1437
pending = set(revisions).intersection(all_seen)
1438
seen_ancestors = set(pending)
1440
if self._returning == 'next':
1441
# self.seen contains what nodes have been returned, not what nodes
1442
# have been queried. We don't want to probe for nodes that haven't
1443
# been searched yet.
1444
not_searched_yet = self._next_query
1446
not_searched_yet = ()
1447
pending.difference_update(not_searched_yet)
1448
get_parent_map = self._parents_provider.get_parent_map
1450
parent_map = get_parent_map(pending)
1452
# We don't care if it is a ghost, since it can't be seen if it is
1454
for parent_ids in parent_map.itervalues():
1455
all_parents.extend(parent_ids)
1456
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1457
seen_ancestors.update(next_pending)
1458
next_pending.difference_update(not_searched_yet)
1459
pending = next_pending
411
def find_seen_ancestors(self, revision):
412
"""Find ancestors of this revision that have already been seen."""
413
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
414
seen_ancestors = set()
415
for ancestors in searcher:
416
for ancestor in ancestors:
417
if ancestor not in self.seen:
418
searcher.stop_searching_any([ancestor])
420
seen_ancestors.add(ancestor)
1461
421
return seen_ancestors
1463
423
def stop_searching_any(self, revisions):
1465
425
Remove any of the specified revisions from the search list.
1467
427
None of the specified revisions are required to be present in the
1470
It is okay to call stop_searching_any() for revisions which were seen
1471
in previous iterations. It is the callers responsibility to call
1472
find_seen_ancestors() to make sure that current search tips that are
1473
ancestors of those revisions are also stopped. All explicitly stopped
1474
revisions will be excluded from the search result's get_keys(), though.
428
search list. In this case, the call is a no-op.
1476
# TODO: does this help performance?
1479
revisions = frozenset(revisions)
1480
if self._returning == 'next':
1481
stopped = self._next_query.intersection(revisions)
1482
self._next_query = self._next_query.difference(revisions)
1484
stopped_present = self._current_present.intersection(revisions)
1485
stopped = stopped_present.union(
1486
self._current_ghosts.intersection(revisions))
1487
self._current_present.difference_update(stopped)
1488
self._current_ghosts.difference_update(stopped)
1489
# stopping 'x' should stop returning parents of 'x', but
1490
# not if 'y' always references those same parents
1491
stop_rev_references = {}
1492
for rev in stopped_present:
1493
for parent_id in self._current_parents[rev]:
1494
if parent_id not in stop_rev_references:
1495
stop_rev_references[parent_id] = 0
1496
stop_rev_references[parent_id] += 1
1497
# if only the stopped revisions reference it, the ref count will be
1499
for parents in self._current_parents.itervalues():
1500
for parent_id in parents:
1502
stop_rev_references[parent_id] -= 1
1505
stop_parents = set()
1506
for rev_id, refs in stop_rev_references.iteritems():
1508
stop_parents.add(rev_id)
1509
self._next_query.difference_update(stop_parents)
1510
self._stopped_keys.update(stopped)
1511
self._stopped_keys.update(revisions)
430
stopped = self._search_revisions.intersection(revisions)
431
self._search_revisions = self._search_revisions.difference(revisions)
1514
434
def start_searching(self, revisions):
1515
"""Add revisions to the search.
1517
The parents of revisions will be returned from the next call to next()
1518
or next_with_ghosts(). If next_with_ghosts was the most recently used
1519
next* call then the return value is the result of looking up the
1520
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1522
revisions = frozenset(revisions)
1523
self._started_keys.update(revisions)
1524
new_revisions = revisions.difference(self.seen)
1525
if self._returning == 'next':
1526
self._next_query.update(new_revisions)
1527
self.seen.update(new_revisions)
1529
# perform a query on revisions
1530
revs, ghosts, query, parents = self._do_query(revisions)
1531
self._stopped_keys.update(ghosts)
1532
self._current_present.update(revs)
1533
self._current_ghosts.update(ghosts)
1534
self._next_query.update(query)
1535
self._current_parents.update(parents)
1539
class SearchResult(object):
1540
"""The result of a breadth first search.
1542
A SearchResult provides the ability to reconstruct the search or access a
1543
set of the keys the search found.
1546
def __init__(self, start_keys, exclude_keys, key_count, keys):
1547
"""Create a SearchResult.
1549
:param start_keys: The keys the search started at.
1550
:param exclude_keys: The keys the search excludes.
1551
:param key_count: The total number of keys (from start to but not
1553
:param keys: The keys the search found. Note that in future we may get
1554
a SearchResult from a smart server, in which case the keys list is
1555
not necessarily immediately available.
1557
self._recipe = ('search', start_keys, exclude_keys, key_count)
1558
self._keys = frozenset(keys)
1560
def get_recipe(self):
1561
"""Return a recipe that can be used to replay this search.
1563
The recipe allows reconstruction of the same results at a later date
1564
without knowing all the found keys. The essential elements are a list
1565
of keys to start and to stop at. In order to give reproducible
1566
results when ghosts are encountered by a search they are automatically
1567
added to the exclude list (or else ghost filling may alter the
1570
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1571
revision_count). To recreate the results of this search, create a
1572
breadth first searcher on the same graph starting at start_keys.
1573
Then call next() (or next_with_ghosts()) repeatedly, and on every
1574
result, call stop_searching_any on any keys from the exclude_keys
1575
set. The revision_count value acts as a trivial cross-check - the
1576
found revisions of the new search should have as many elements as
1577
revision_count. If it does not, then additional revisions have been
1578
ghosted since the search was executed the first time and the second
1584
"""Return the keys found in this search.
1586
:return: A set of keys.
1591
"""Return false if the search lists 1 or more revisions."""
1592
return self._recipe[3] == 0
1594
def refine(self, seen, referenced):
1595
"""Create a new search by refining this search.
1597
:param seen: Revisions that have been satisfied.
1598
:param referenced: Revision references observed while satisfying some
1601
start = self._recipe[1]
1602
exclude = self._recipe[2]
1603
count = self._recipe[3]
1604
keys = self.get_keys()
1605
# New heads = referenced + old heads - seen things - exclude
1606
pending_refs = set(referenced)
1607
pending_refs.update(start)
1608
pending_refs.difference_update(seen)
1609
pending_refs.difference_update(exclude)
1610
# New exclude = old exclude + satisfied heads
1611
seen_heads = start.intersection(seen)
1612
exclude.update(seen_heads)
1613
# keys gets seen removed
1615
# length is reduced by len(seen)
1617
return SearchResult(pending_refs, exclude, count, keys)
1620
class PendingAncestryResult(object):
1621
"""A search result that will reconstruct the ancestry for some graph heads.
1623
Unlike SearchResult, this doesn't hold the complete search result in
1624
memory, it just holds a description of how to generate it.
1627
def __init__(self, heads, repo):
1630
:param heads: an iterable of graph heads.
1631
:param repo: a repository to use to generate the ancestry for the given
1634
self.heads = frozenset(heads)
1637
def get_recipe(self):
1638
"""Return a recipe that can be used to replay this search.
1640
The recipe allows reconstruction of the same results at a later date.
1642
:seealso SearchResult.get_recipe:
1644
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1645
To recreate this result, create a PendingAncestryResult with the
1648
return ('proxy-search', self.heads, set(), -1)
1651
"""See SearchResult.get_keys.
1653
Returns all the keys for the ancestry of the heads, excluding
1656
return self._get_keys(self.repo.get_graph())
1658
def _get_keys(self, graph):
1659
NULL_REVISION = revision.NULL_REVISION
1660
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1661
if key != NULL_REVISION and parents is not None]
1665
"""Return false if the search lists 1 or more revisions."""
1666
if revision.NULL_REVISION in self.heads:
1667
return len(self.heads) == 1
1669
return len(self.heads) == 0
1671
def refine(self, seen, referenced):
1672
"""Create a new search by refining this search.
1674
:param seen: Revisions that have been satisfied.
1675
:param referenced: Revision references observed while satisfying some
1678
referenced = self.heads.union(referenced)
1679
return PendingAncestryResult(referenced - seen, self.repo)
1682
def collapse_linear_regions(parent_map):
1683
"""Collapse regions of the graph that are 'linear'.
1689
can be collapsed by removing B and getting::
1693
:param parent_map: A dictionary mapping children to their parents
1694
:return: Another dictionary with 'linear' chains collapsed
1696
# Note: this isn't a strictly minimal collapse. For example:
1704
# Will not have 'D' removed, even though 'E' could fit. Also:
1710
# A and C are both kept because they are edges of the graph. We *could* get
1711
# rid of A if we wanted.
1719
# Will not have any nodes removed, even though you do have an
1720
# 'uninteresting' linear D->B and E->C
1722
for child, parents in parent_map.iteritems():
1723
children.setdefault(child, [])
1725
children.setdefault(p, []).append(child)
1727
orig_children = dict(children)
1729
result = dict(parent_map)
1730
for node in parent_map:
1731
parents = result[node]
1732
if len(parents) == 1:
1733
parent_children = children[parents[0]]
1734
if len(parent_children) != 1:
1735
# This is not the only child
1737
node_children = children[node]
1738
if len(node_children) != 1:
1740
child_parents = result.get(node_children[0], None)
1741
if len(child_parents) != 1:
1742
# This is not its only parent
1744
# The child of this node only points at it, and the parent only has
1745
# this as a child. remove this node, and join the others together
1746
result[node_children[0]] = parents
1747
children[parents[0]] = node_children
1755
class GraphThunkIdsToKeys(object):
1756
"""Forwards calls about 'ids' to be about keys internally."""
1758
def __init__(self, graph):
1761
def topo_sort(self):
1762
return [r for (r,) in self._graph.topo_sort()]
1764
def heads(self, ids):
1765
"""See Graph.heads()"""
1766
as_keys = [(i,) for i in ids]
1767
head_keys = self._graph.heads(as_keys)
1768
return set([h[0] for h in head_keys])
1770
def merge_sort(self, tip_revision):
1771
return self._graph.merge_sort((tip_revision,))
1774
_counters = [0,0,0,0,0,0,0]
1776
from bzrlib._known_graph_pyx import KnownGraph
1777
except ImportError, e:
1778
osutils.failed_to_load_extension(e)
1779
from bzrlib._known_graph_py import KnownGraph
435
if self._search_revisions is None:
436
self._start = set(revisions)
438
self._search_revisions.update(revisions.difference(self.seen))
439
self.seen.update(revisions)
added
removed
bzrlib/graph.py
