44
50
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
48
class _StackedParentsProvider(object):
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.
50
77
def __init__(self, parent_providers):
51
78
self._parent_providers = parent_providers
53
80
def __repr__(self):
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.
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
62
90
[NULL_REVISION] is used as the parent of the first user-committed
63
91
revision. Its parent list is empty.
65
If the revision is not present (i.e. a ghost), None is used in place
66
of the list of parents.
93
:param keys: An iterable returning keys to check (eg revision_ids)
94
:return: A dictionary mapping each key to its parents
69
98
for parents_provider in self._parent_providers:
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)
99
new_found = parents_provider.get_parent_map(remaining)
74
100
found.update(new_found)
75
if len(found) == len(revision_ids):
101
remaining.difference_update(new_found)
77
return [found.get(r, None) for r in 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)
80
186
class Graph(object):
142
252
def find_difference(self, left_revision, right_revision):
143
253
"""Determine the graph difference between two revisions"""
144
border, common, (left, right) = self._find_border_ancestors(
254
border, common, searchers = self._find_border_ancestors(
145
255
[left_revision, right_revision])
146
return (left.difference(right).difference(common),
147
right.difference(left).difference(common))
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_distance_to_null(self, target_revision_id, known_revision_ids):
262
"""Find the left-hand distance to the NULL_REVISION.
264
(This can also be considered the revno of a branch at
267
:param target_revision_id: A revision_id which we would like to know
269
:param known_revision_ids: [(revision_id, revno)] A list of known
270
revno, revision_id tuples. We'll use this to seed the search.
272
# Map from revision_ids to a known value for their revno
273
known_revnos = dict(known_revision_ids)
274
cur_tip = target_revision_id
276
NULL_REVISION = revision.NULL_REVISION
277
known_revnos[NULL_REVISION] = 0
279
searching_known_tips = list(known_revnos.keys())
281
unknown_searched = {}
283
while cur_tip not in known_revnos:
284
unknown_searched[cur_tip] = num_steps
286
to_search = set([cur_tip])
287
to_search.update(searching_known_tips)
288
parent_map = self.get_parent_map(to_search)
289
parents = parent_map.get(cur_tip, None)
290
if not parents: # An empty list or None is a ghost
291
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
295
for revision_id in searching_known_tips:
296
parents = parent_map.get(revision_id, None)
300
next_revno = known_revnos[revision_id] - 1
301
if next in unknown_searched:
302
# We have enough information to return a value right now
303
return next_revno + unknown_searched[next]
304
if next in known_revnos:
306
known_revnos[next] = next_revno
307
next_known_tips.append(next)
308
searching_known_tips = next_known_tips
310
# We reached a known revision, so just add in how many steps it took to
312
return known_revnos[cur_tip] + num_steps
314
def find_lefthand_distances(self, keys):
315
"""Find the distance to null for all the keys in keys.
317
:param keys: keys to lookup.
318
:return: A dict key->distance for all of keys.
320
# Optimisable by concurrent searching, but a random spread should get
321
# some sort of hit rate.
328
(key, self.find_distance_to_null(key, known_revnos)))
329
except errors.GhostRevisionsHaveNoRevno:
332
known_revnos.append((key, -1))
333
return dict(known_revnos)
335
def find_unique_ancestors(self, unique_revision, common_revisions):
336
"""Find the unique ancestors for a revision versus others.
338
This returns the ancestry of unique_revision, excluding all revisions
339
in the ancestry of common_revisions. If unique_revision is in the
340
ancestry, then the empty set will be returned.
342
:param unique_revision: The revision_id whose ancestry we are
344
XXX: Would this API be better if we allowed multiple revisions on
346
:param common_revisions: Revision_ids of ancestries to exclude.
347
:return: A set of revisions in the ancestry of unique_revision
349
if unique_revision in common_revisions:
352
# Algorithm description
353
# 1) Walk backwards from the unique node and all common nodes.
354
# 2) When a node is seen by both sides, stop searching it in the unique
355
# walker, include it in the common walker.
356
# 3) Stop searching when there are no nodes left for the unique walker.
357
# At this point, you have a maximal set of unique nodes. Some of
358
# them may actually be common, and you haven't reached them yet.
359
# 4) Start new searchers for the unique nodes, seeded with the
360
# information you have so far.
361
# 5) Continue searching, stopping the common searches when the search
362
# tip is an ancestor of all unique nodes.
363
# 6) Aggregate together unique searchers when they are searching the
364
# same tips. When all unique searchers are searching the same node,
365
# stop move it to a single 'all_unique_searcher'.
366
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
367
# Most of the time this produces very little important information.
368
# So don't step it as quickly as the other searchers.
369
# 8) Search is done when all common searchers have completed.
371
unique_searcher, common_searcher = self._find_initial_unique_nodes(
372
[unique_revision], common_revisions)
374
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
378
(all_unique_searcher,
379
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
380
unique_searcher, common_searcher)
382
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
383
unique_tip_searchers, common_searcher)
384
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
385
if 'graph' in debug.debug_flags:
386
trace.mutter('Found %d truly unique nodes out of %d',
387
len(true_unique_nodes), len(unique_nodes))
388
return true_unique_nodes
390
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
391
"""Steps 1-3 of find_unique_ancestors.
393
Find the maximal set of unique nodes. Some of these might actually
394
still be common, but we are sure that there are no other unique nodes.
396
:return: (unique_searcher, common_searcher)
399
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
400
# we know that unique_revisions aren't in common_revisions, so skip
402
unique_searcher.next()
403
common_searcher = self._make_breadth_first_searcher(common_revisions)
405
# As long as we are still finding unique nodes, keep searching
406
while unique_searcher._next_query:
407
next_unique_nodes = set(unique_searcher.step())
408
next_common_nodes = set(common_searcher.step())
410
# Check if either searcher encounters new nodes seen by the other
412
unique_are_common_nodes = next_unique_nodes.intersection(
413
common_searcher.seen)
414
unique_are_common_nodes.update(
415
next_common_nodes.intersection(unique_searcher.seen))
416
if unique_are_common_nodes:
417
ancestors = unique_searcher.find_seen_ancestors(
418
unique_are_common_nodes)
419
# TODO: This is a bit overboard, we only really care about
420
# the ancestors of the tips because the rest we
421
# already know. This is *correct* but causes us to
422
# search too much ancestry.
423
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
424
unique_searcher.stop_searching_any(ancestors)
425
common_searcher.start_searching(ancestors)
427
return unique_searcher, common_searcher
429
def _make_unique_searchers(self, unique_nodes, unique_searcher,
431
"""Create a searcher for all the unique search tips (step 4).
433
As a side effect, the common_searcher will stop searching any nodes
434
that are ancestors of the unique searcher tips.
436
:return: (all_unique_searcher, unique_tip_searchers)
438
unique_tips = self._remove_simple_descendants(unique_nodes,
439
self.get_parent_map(unique_nodes))
441
if len(unique_tips) == 1:
442
unique_tip_searchers = []
443
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
445
unique_tip_searchers = []
446
for tip in unique_tips:
447
revs_to_search = unique_searcher.find_seen_ancestors([tip])
448
revs_to_search.update(
449
common_searcher.find_seen_ancestors(revs_to_search))
450
searcher = self._make_breadth_first_searcher(revs_to_search)
451
# We don't care about the starting nodes.
452
searcher._label = tip
454
unique_tip_searchers.append(searcher)
456
ancestor_all_unique = None
457
for searcher in unique_tip_searchers:
458
if ancestor_all_unique is None:
459
ancestor_all_unique = set(searcher.seen)
461
ancestor_all_unique = ancestor_all_unique.intersection(
463
# Collapse all the common nodes into a single searcher
464
all_unique_searcher = self._make_breadth_first_searcher(
466
if ancestor_all_unique:
467
# We've seen these nodes in all the searchers, so we'll just go to
469
all_unique_searcher.step()
471
# Stop any search tips that are already known as ancestors of the
473
stopped_common = common_searcher.stop_searching_any(
474
common_searcher.find_seen_ancestors(ancestor_all_unique))
477
for searcher in unique_tip_searchers:
478
total_stopped += len(searcher.stop_searching_any(
479
searcher.find_seen_ancestors(ancestor_all_unique)))
480
if 'graph' in debug.debug_flags:
481
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
482
' (%d stopped search tips, %d common ancestors'
483
' (%d stopped common)',
484
len(unique_nodes), len(unique_tip_searchers),
485
total_stopped, len(ancestor_all_unique),
487
return all_unique_searcher, unique_tip_searchers
489
def _step_unique_and_common_searchers(self, common_searcher,
490
unique_tip_searchers,
492
"""Step all the searchers"""
493
newly_seen_common = set(common_searcher.step())
494
newly_seen_unique = set()
495
for searcher in unique_tip_searchers:
496
next = set(searcher.step())
497
next.update(unique_searcher.find_seen_ancestors(next))
498
next.update(common_searcher.find_seen_ancestors(next))
499
for alt_searcher in unique_tip_searchers:
500
if alt_searcher is searcher:
502
next.update(alt_searcher.find_seen_ancestors(next))
503
searcher.start_searching(next)
504
newly_seen_unique.update(next)
505
return newly_seen_common, newly_seen_unique
507
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
509
newly_seen_unique, step_all_unique):
510
"""Find nodes that are common to all unique_tip_searchers.
512
If it is time, step the all_unique_searcher, and add its nodes to the
515
common_to_all_unique_nodes = newly_seen_unique.copy()
516
for searcher in unique_tip_searchers:
517
common_to_all_unique_nodes.intersection_update(searcher.seen)
518
common_to_all_unique_nodes.intersection_update(
519
all_unique_searcher.seen)
520
# Step all-unique less frequently than the other searchers.
521
# In the common case, we don't need to spider out far here, so
522
# avoid doing extra work.
524
tstart = time.clock()
525
nodes = all_unique_searcher.step()
526
common_to_all_unique_nodes.update(nodes)
527
if 'graph' in debug.debug_flags:
528
tdelta = time.clock() - tstart
529
trace.mutter('all_unique_searcher step() took %.3fs'
530
'for %d nodes (%d total), iteration: %s',
531
tdelta, len(nodes), len(all_unique_searcher.seen),
532
all_unique_searcher._iterations)
533
return common_to_all_unique_nodes
535
def _collapse_unique_searchers(self, unique_tip_searchers,
536
common_to_all_unique_nodes):
537
"""Combine searchers that are searching the same tips.
539
When two searchers are searching the same tips, we can stop one of the
540
searchers. We also know that the maximal set of common ancestors is the
541
intersection of the two original searchers.
543
:return: A list of searchers that are searching unique nodes.
545
# Filter out searchers that don't actually search different
546
# nodes. We already have the ancestry intersection for them
547
unique_search_tips = {}
548
for searcher in unique_tip_searchers:
549
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
550
will_search_set = frozenset(searcher._next_query)
551
if not will_search_set:
552
if 'graph' in debug.debug_flags:
553
trace.mutter('Unique searcher %s was stopped.'
554
' (%s iterations) %d nodes stopped',
556
searcher._iterations,
558
elif will_search_set not in unique_search_tips:
559
# This searcher is searching a unique set of nodes, let it
560
unique_search_tips[will_search_set] = [searcher]
562
unique_search_tips[will_search_set].append(searcher)
563
# TODO: it might be possible to collapse searchers faster when they
564
# only have *some* search tips in common.
565
next_unique_searchers = []
566
for searchers in unique_search_tips.itervalues():
567
if len(searchers) == 1:
568
# Searching unique tips, go for it
569
next_unique_searchers.append(searchers[0])
571
# These searchers have started searching the same tips, we
572
# don't need them to cover the same ground. The
573
# intersection of their ancestry won't change, so create a
574
# new searcher, combining their histories.
575
next_searcher = searchers[0]
576
for searcher in searchers[1:]:
577
next_searcher.seen.intersection_update(searcher.seen)
578
if 'graph' in debug.debug_flags:
579
trace.mutter('Combining %d searchers into a single'
580
' searcher searching %d nodes with'
583
len(next_searcher._next_query),
584
len(next_searcher.seen))
585
next_unique_searchers.append(next_searcher)
586
return next_unique_searchers
588
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
589
unique_tip_searchers, common_searcher):
590
"""Steps 5-8 of find_unique_ancestors.
592
This function returns when common_searcher has stopped searching for
595
# We step the ancestor_all_unique searcher only every
596
# STEP_UNIQUE_SEARCHER_EVERY steps.
597
step_all_unique_counter = 0
598
# While we still have common nodes to search
599
while common_searcher._next_query:
601
newly_seen_unique) = self._step_unique_and_common_searchers(
602
common_searcher, unique_tip_searchers, unique_searcher)
603
# These nodes are common ancestors of all unique nodes
604
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
605
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
606
step_all_unique_counter==0)
607
step_all_unique_counter = ((step_all_unique_counter + 1)
608
% STEP_UNIQUE_SEARCHER_EVERY)
610
if newly_seen_common:
611
# If a 'common' node is an ancestor of all unique searchers, we
612
# can stop searching it.
613
common_searcher.stop_searching_any(
614
all_unique_searcher.seen.intersection(newly_seen_common))
615
if common_to_all_unique_nodes:
616
common_to_all_unique_nodes.update(
617
common_searcher.find_seen_ancestors(
618
common_to_all_unique_nodes))
619
# The all_unique searcher can start searching the common nodes
620
# but everyone else can stop.
621
# This is the sort of thing where we would like to not have it
622
# start_searching all of the nodes, but only mark all of them
623
# as seen, and have it search only the actual tips. Otherwise
624
# it is another get_parent_map() traversal for it to figure out
625
# what we already should know.
626
all_unique_searcher.start_searching(common_to_all_unique_nodes)
627
common_searcher.stop_searching_any(common_to_all_unique_nodes)
629
next_unique_searchers = self._collapse_unique_searchers(
630
unique_tip_searchers, common_to_all_unique_nodes)
631
if len(unique_tip_searchers) != len(next_unique_searchers):
632
if 'graph' in debug.debug_flags:
633
trace.mutter('Collapsed %d unique searchers => %d'
635
len(unique_tip_searchers),
636
len(next_unique_searchers),
637
all_unique_searcher._iterations)
638
unique_tip_searchers = next_unique_searchers
640
def get_parent_map(self, revisions):
641
"""Get a map of key:parent_list for revisions.
643
This implementation delegates to get_parents, for old parent_providers
644
that do not supply get_parent_map.
647
for rev, parents in self.get_parents(revisions):
648
if parents is not None:
649
result[rev] = parents
149
652
def _make_breadth_first_searcher(self, revisions):
150
653
return _BreadthFirstSearcher(revisions, self)
166
669
if None in revisions:
167
670
raise errors.InvalidRevisionId(None, self)
168
common_searcher = self._make_breadth_first_searcher([])
169
671
common_ancestors = set()
170
672
searchers = [self._make_breadth_first_searcher([r])
171
673
for r in revisions]
172
674
active_searchers = searchers[:]
173
675
border_ancestors = set()
174
def update_common(searcher, revisions):
175
w_seen_ancestors = searcher.find_seen_ancestors(
177
stopped = searcher.stop_searching_any(w_seen_ancestors)
178
common_ancestors.update(w_seen_ancestors)
179
common_searcher.start_searching(stopped)
182
if len(active_searchers) == 0:
183
return border_ancestors, common_ancestors, [s.seen for s in
186
new_common = common_searcher.next()
187
common_ancestors.update(new_common)
188
except StopIteration:
191
for searcher in active_searchers:
192
for revision in new_common.intersection(searcher.seen):
193
update_common(searcher, revision)
195
678
newly_seen = set()
196
new_active_searchers = []
197
for searcher in active_searchers:
199
newly_seen.update(searcher.next())
200
except StopIteration:
203
new_active_searchers.append(searcher)
204
active_searchers = new_active_searchers
679
for searcher in searchers:
680
new_ancestors = searcher.step()
682
newly_seen.update(new_ancestors)
205
684
for revision in newly_seen:
206
685
if revision in common_ancestors:
207
for searcher in searchers:
208
update_common(searcher, revision)
686
# Not a border ancestor because it was seen as common
688
new_common.add(revision)
210
690
for searcher in searchers:
211
691
if revision not in searcher.seen:
694
# This is a border because it is a first common that we see
695
# after walking for a while.
214
696
border_ancestors.add(revision)
215
for searcher in searchers:
216
update_common(searcher, revision)
697
new_common.add(revision)
699
for searcher in searchers:
700
new_common.update(searcher.find_seen_ancestors(new_common))
701
for searcher in searchers:
702
searcher.start_searching(new_common)
703
common_ancestors.update(new_common)
705
# Figure out what the searchers will be searching next, and if
706
# there is only 1 set being searched, then we are done searching,
707
# since all searchers would have to be searching the same data,
708
# thus it *must* be in common.
709
unique_search_sets = set()
710
for searcher in searchers:
711
will_search_set = frozenset(searcher._next_query)
712
if will_search_set not in unique_search_sets:
713
# This searcher is searching a unique set of nodes, let it
714
unique_search_sets.add(will_search_set)
716
if len(unique_search_sets) == 1:
717
nodes = unique_search_sets.pop()
718
uncommon_nodes = nodes.difference(common_ancestors)
720
raise AssertionError("Somehow we ended up converging"
721
" without actually marking them as"
724
"\nuncommon_nodes: %s"
725
% (revisions, uncommon_nodes))
727
return border_ancestors, common_ancestors, searchers
218
729
def heads(self, keys):
219
730
"""Return the heads from amongst keys.
327
926
An ancestor may sort after a descendant if the relationship is not
328
927
visible in the supplied list of revisions.
330
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
929
from bzrlib import tsort
930
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
331
931
return sorter.iter_topo_order()
333
933
def is_ancestor(self, candidate_ancestor, candidate_descendant):
334
934
"""Determine whether a revision is an ancestor of another.
336
936
We answer this using heads() as heads() has the logic to perform the
337
smallest number of parent looksup to determine the ancestral
937
smallest number of parent lookups to determine the ancestral
338
938
relationship between N revisions.
340
940
return set([candidate_descendant]) == self.heads(
341
941
[candidate_ancestor, candidate_descendant])
943
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
944
"""Determine whether a revision is between two others.
946
returns true if and only if:
947
lower_bound_revid <= revid <= upper_bound_revid
949
return ((upper_bound_revid is None or
950
self.is_ancestor(revid, upper_bound_revid)) and
951
(lower_bound_revid is None or
952
self.is_ancestor(lower_bound_revid, revid)))
954
def _search_for_extra_common(self, common, searchers):
955
"""Make sure that unique nodes are genuinely unique.
957
After _find_border_ancestors, all nodes marked "common" are indeed
958
common. Some of the nodes considered unique are not, due to history
959
shortcuts stopping the searches early.
961
We know that we have searched enough when all common search tips are
962
descended from all unique (uncommon) nodes because we know that a node
963
cannot be an ancestor of its own ancestor.
965
:param common: A set of common nodes
966
:param searchers: The searchers returned from _find_border_ancestors
970
# A) The passed in searchers should all be on the same tips, thus
971
# they should be considered the "common" searchers.
972
# B) We find the difference between the searchers, these are the
973
# "unique" nodes for each side.
974
# C) We do a quick culling so that we only start searching from the
975
# more interesting unique nodes. (A unique ancestor is more
976
# interesting than any of its children.)
977
# D) We start searching for ancestors common to all unique nodes.
978
# E) We have the common searchers stop searching any ancestors of
980
# F) When there are no more common search tips, we stop
982
# TODO: We need a way to remove unique_searchers when they overlap with
983
# other unique searchers.
984
if len(searchers) != 2:
985
raise NotImplementedError(
986
"Algorithm not yet implemented for > 2 searchers")
987
common_searchers = searchers
988
left_searcher = searchers[0]
989
right_searcher = searchers[1]
990
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
991
if not unique: # No unique nodes, nothing to do
993
total_unique = len(unique)
994
unique = self._remove_simple_descendants(unique,
995
self.get_parent_map(unique))
996
simple_unique = len(unique)
998
unique_searchers = []
999
for revision_id in unique:
1000
if revision_id in left_searcher.seen:
1001
parent_searcher = left_searcher
1003
parent_searcher = right_searcher
1004
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1005
if not revs_to_search: # XXX: This shouldn't be possible
1006
revs_to_search = [revision_id]
1007
searcher = self._make_breadth_first_searcher(revs_to_search)
1008
# We don't care about the starting nodes.
1010
unique_searchers.append(searcher)
1012
# possible todo: aggregate the common searchers into a single common
1013
# searcher, just make sure that we include the nodes into the .seen
1014
# properties of the original searchers
1016
ancestor_all_unique = None
1017
for searcher in unique_searchers:
1018
if ancestor_all_unique is None:
1019
ancestor_all_unique = set(searcher.seen)
1021
ancestor_all_unique = ancestor_all_unique.intersection(
1024
trace.mutter('Started %s unique searchers for %s unique revisions',
1025
simple_unique, total_unique)
1027
while True: # If we have no more nodes we have nothing to do
1028
newly_seen_common = set()
1029
for searcher in common_searchers:
1030
newly_seen_common.update(searcher.step())
1031
newly_seen_unique = set()
1032
for searcher in unique_searchers:
1033
newly_seen_unique.update(searcher.step())
1034
new_common_unique = set()
1035
for revision in newly_seen_unique:
1036
for searcher in unique_searchers:
1037
if revision not in searcher.seen:
1040
# This is a border because it is a first common that we see
1041
# after walking for a while.
1042
new_common_unique.add(revision)
1043
if newly_seen_common:
1044
# These are nodes descended from one of the 'common' searchers.
1045
# Make sure all searchers are on the same page
1046
for searcher in common_searchers:
1047
newly_seen_common.update(
1048
searcher.find_seen_ancestors(newly_seen_common))
1049
# We start searching the whole ancestry. It is a bit wasteful,
1050
# though. We really just want to mark all of these nodes as
1051
# 'seen' and then start just the tips. However, it requires a
1052
# get_parent_map() call to figure out the tips anyway, and all
1053
# redundant requests should be fairly fast.
1054
for searcher in common_searchers:
1055
searcher.start_searching(newly_seen_common)
1057
# If a 'common' node is an ancestor of all unique searchers, we
1058
# can stop searching it.
1059
stop_searching_common = ancestor_all_unique.intersection(
1061
if stop_searching_common:
1062
for searcher in common_searchers:
1063
searcher.stop_searching_any(stop_searching_common)
1064
if new_common_unique:
1065
# We found some ancestors that are common
1066
for searcher in unique_searchers:
1067
new_common_unique.update(
1068
searcher.find_seen_ancestors(new_common_unique))
1069
# Since these are common, we can grab another set of ancestors
1071
for searcher in common_searchers:
1072
new_common_unique.update(
1073
searcher.find_seen_ancestors(new_common_unique))
1075
# We can tell all of the unique searchers to start at these
1076
# nodes, and tell all of the common searchers to *stop*
1077
# searching these nodes
1078
for searcher in unique_searchers:
1079
searcher.start_searching(new_common_unique)
1080
for searcher in common_searchers:
1081
searcher.stop_searching_any(new_common_unique)
1082
ancestor_all_unique.update(new_common_unique)
1084
# Filter out searchers that don't actually search different
1085
# nodes. We already have the ancestry intersection for them
1086
next_unique_searchers = []
1087
unique_search_sets = set()
1088
for searcher in unique_searchers:
1089
will_search_set = frozenset(searcher._next_query)
1090
if will_search_set not in unique_search_sets:
1091
# This searcher is searching a unique set of nodes, let it
1092
unique_search_sets.add(will_search_set)
1093
next_unique_searchers.append(searcher)
1094
unique_searchers = next_unique_searchers
1095
for searcher in common_searchers:
1096
if searcher._next_query:
1099
# All common searcher have stopped searching
1102
def _remove_simple_descendants(self, revisions, parent_map):
1103
"""remove revisions which are children of other ones in the set
1105
This doesn't do any graph searching, it just checks the immediate
1106
parent_map to find if there are any children which can be removed.
1108
:param revisions: A set of revision_ids
1109
:return: A set of revision_ids with the children removed
1111
simple_ancestors = revisions.copy()
1112
# TODO: jam 20071214 we *could* restrict it to searching only the
1113
# parent_map of revisions already present in 'revisions', but
1114
# considering the general use case, I think this is actually
1117
# This is the same as the following loop. I don't know that it is any
1119
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1120
## if p_ids is not None and revisions.intersection(p_ids))
1121
## return simple_ancestors
1123
# Yet Another Way, invert the parent map (which can be cached)
1125
## for revision_id, parent_ids in parent_map.iteritems():
1126
## for p_id in parent_ids:
1127
## descendants.setdefault(p_id, []).append(revision_id)
1128
## for revision in revisions.intersection(descendants):
1129
## simple_ancestors.difference_update(descendants[revision])
1130
## return simple_ancestors
1131
for revision, parent_ids in parent_map.iteritems():
1132
if parent_ids is None:
1134
for parent_id in parent_ids:
1135
if parent_id in revisions:
1136
# This node has a parent present in the set, so we can
1138
simple_ancestors.discard(revision)
1140
return simple_ancestors
344
1143
class HeadsCache(object):
345
1144
"""A cache of results for graph heads calls."""
404
1209
def __init__(self, revisions, parents_provider):
405
self._start = set(revisions)
406
self._search_revisions = None
407
self.seen = set(revisions)
408
self._parents_provider = parents_provider
1210
self._iterations = 0
1211
self._next_query = set(revisions)
1213
self._started_keys = set(self._next_query)
1214
self._stopped_keys = set()
1215
self._parents_provider = parents_provider
1216
self._returning = 'next_with_ghosts'
1217
self._current_present = set()
1218
self._current_ghosts = set()
1219
self._current_parents = {}
410
1221
def __repr__(self):
411
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
412
' self.seen=%r)' % (self._search_revisions, self.seen))
1222
if self._iterations:
1223
prefix = "searching"
1226
search = '%s=%r' % (prefix, list(self._next_query))
1227
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1228
' seen=%r)' % (self._iterations, search, list(self.seen)))
1230
def get_result(self):
1231
"""Get a SearchResult for the current state of this searcher.
1233
:return: A SearchResult for this search so far. The SearchResult is
1234
static - the search can be advanced and the search result will not
1235
be invalidated or altered.
1237
if self._returning == 'next':
1238
# We have to know the current nodes children to be able to list the
1239
# exclude keys for them. However, while we could have a second
1240
# look-ahead result buffer and shuffle things around, this method
1241
# is typically only called once per search - when memoising the
1242
# results of the search.
1243
found, ghosts, next, parents = self._do_query(self._next_query)
1244
# pretend we didn't query: perhaps we should tweak _do_query to be
1245
# entirely stateless?
1246
self.seen.difference_update(next)
1247
next_query = next.union(ghosts)
1249
next_query = self._next_query
1250
excludes = self._stopped_keys.union(next_query)
1251
included_keys = self.seen.difference(excludes)
1252
return SearchResult(self._started_keys, excludes, len(included_keys),
1258
except StopIteration:
415
1262
"""Return the next ancestors of this revision.
417
1264
Ancestors are returned in the order they are seen in a breadth-first
418
traversal. No ancestor will be returned more than once.
1265
traversal. No ancestor will be returned more than once. Ancestors are
1266
returned before their parentage is queried, so ghosts and missing
1267
revisions (including the start revisions) are included in the result.
1268
This can save a round trip in LCA style calculation by allowing
1269
convergence to be detected without reading the data for the revision
1270
the convergence occurs on.
1272
:return: A set of revision_ids.
420
if self._search_revisions is None:
421
self._search_revisions = self._start
1274
if self._returning != 'next':
1275
# switch to returning the query, not the results.
1276
self._returning = 'next'
1277
self._iterations += 1
423
new_search_revisions = set()
424
for parents in self._parents_provider.get_parents(
425
self._search_revisions):
428
new_search_revisions.update(p for p in parents if
430
self._search_revisions = new_search_revisions
431
if len(self._search_revisions) == 0:
432
raise StopIteration()
433
self.seen.update(self._search_revisions)
434
return self._search_revisions
1280
if len(self._next_query) == 0:
1281
raise StopIteration()
1282
# We have seen what we're querying at this point as we are returning
1283
# the query, not the results.
1284
self.seen.update(self._next_query)
1285
return self._next_query
1287
def next_with_ghosts(self):
1288
"""Return the next found ancestors, with ghosts split out.
1290
Ancestors are returned in the order they are seen in a breadth-first
1291
traversal. No ancestor will be returned more than once. Ancestors are
1292
returned only after asking for their parents, which allows us to detect
1293
which revisions are ghosts and which are not.
1295
:return: A tuple with (present ancestors, ghost ancestors) sets.
1297
if self._returning != 'next_with_ghosts':
1298
# switch to returning the results, not the current query.
1299
self._returning = 'next_with_ghosts'
1301
if len(self._next_query) == 0:
1302
raise StopIteration()
1304
return self._current_present, self._current_ghosts
1307
"""Advance the search.
1309
Updates self.seen, self._next_query, self._current_present,
1310
self._current_ghosts, self._current_parents and self._iterations.
1312
self._iterations += 1
1313
found, ghosts, next, parents = self._do_query(self._next_query)
1314
self._current_present = found
1315
self._current_ghosts = ghosts
1316
self._next_query = next
1317
self._current_parents = parents
1318
# ghosts are implicit stop points, otherwise the search cannot be
1319
# repeated when ghosts are filled.
1320
self._stopped_keys.update(ghosts)
1322
def _do_query(self, revisions):
1323
"""Query for revisions.
1325
Adds revisions to the seen set.
1327
:param revisions: Revisions to query.
1328
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1329
set(parents_of_found_revisions), dict(found_revisions:parents)).
1331
found_revisions = set()
1332
parents_of_found = set()
1333
# revisions may contain nodes that point to other nodes in revisions:
1334
# we want to filter them out.
1335
self.seen.update(revisions)
1336
parent_map = self._parents_provider.get_parent_map(revisions)
1337
found_revisions.update(parent_map)
1338
for rev_id, parents in parent_map.iteritems():
1341
new_found_parents = [p for p in parents if p not in self.seen]
1342
if new_found_parents:
1343
# Calling set.update() with an empty generator is actually
1345
parents_of_found.update(new_found_parents)
1346
ghost_revisions = revisions - found_revisions
1347
return found_revisions, ghost_revisions, parents_of_found, parent_map
436
1349
def __iter__(self):
439
def find_seen_ancestors(self, revision):
440
"""Find ancestors of this revision that have already been seen."""
441
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
442
seen_ancestors = set()
443
for ancestors in searcher:
444
for ancestor in ancestors:
445
if ancestor not in self.seen:
446
searcher.stop_searching_any([ancestor])
448
seen_ancestors.add(ancestor)
1352
def find_seen_ancestors(self, revisions):
1353
"""Find ancestors of these revisions that have already been seen.
1355
This function generally makes the assumption that querying for the
1356
parents of a node that has already been queried is reasonably cheap.
1357
(eg, not a round trip to a remote host).
1359
# TODO: Often we might ask one searcher for its seen ancestors, and
1360
# then ask another searcher the same question. This can result in
1361
# searching the same revisions repeatedly if the two searchers
1362
# have a lot of overlap.
1363
all_seen = self.seen
1364
pending = set(revisions).intersection(all_seen)
1365
seen_ancestors = set(pending)
1367
if self._returning == 'next':
1368
# self.seen contains what nodes have been returned, not what nodes
1369
# have been queried. We don't want to probe for nodes that haven't
1370
# been searched yet.
1371
not_searched_yet = self._next_query
1373
not_searched_yet = ()
1374
pending.difference_update(not_searched_yet)
1375
get_parent_map = self._parents_provider.get_parent_map
1377
parent_map = get_parent_map(pending)
1379
# We don't care if it is a ghost, since it can't be seen if it is
1381
for parent_ids in parent_map.itervalues():
1382
all_parents.extend(parent_ids)
1383
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1384
seen_ancestors.update(next_pending)
1385
next_pending.difference_update(not_searched_yet)
1386
pending = next_pending
449
1388
return seen_ancestors
451
1390
def stop_searching_any(self, revisions):
453
1392
Remove any of the specified revisions from the search list.
455
1394
None of the specified revisions are required to be present in the
456
search list. In this case, the call is a no-op.
1397
It is okay to call stop_searching_any() for revisions which were seen
1398
in previous iterations. It is the callers responsibility to call
1399
find_seen_ancestors() to make sure that current search tips that are
1400
ancestors of those revisions are also stopped. All explicitly stopped
1401
revisions will be excluded from the search result's get_keys(), though.
458
stopped = self._search_revisions.intersection(revisions)
459
self._search_revisions = self._search_revisions.difference(revisions)
1403
# TODO: does this help performance?
1406
revisions = frozenset(revisions)
1407
if self._returning == 'next':
1408
stopped = self._next_query.intersection(revisions)
1409
self._next_query = self._next_query.difference(revisions)
1411
stopped_present = self._current_present.intersection(revisions)
1412
stopped = stopped_present.union(
1413
self._current_ghosts.intersection(revisions))
1414
self._current_present.difference_update(stopped)
1415
self._current_ghosts.difference_update(stopped)
1416
# stopping 'x' should stop returning parents of 'x', but
1417
# not if 'y' always references those same parents
1418
stop_rev_references = {}
1419
for rev in stopped_present:
1420
for parent_id in self._current_parents[rev]:
1421
if parent_id not in stop_rev_references:
1422
stop_rev_references[parent_id] = 0
1423
stop_rev_references[parent_id] += 1
1424
# if only the stopped revisions reference it, the ref count will be
1426
for parents in self._current_parents.itervalues():
1427
for parent_id in parents:
1429
stop_rev_references[parent_id] -= 1
1432
stop_parents = set()
1433
for rev_id, refs in stop_rev_references.iteritems():
1435
stop_parents.add(rev_id)
1436
self._next_query.difference_update(stop_parents)
1437
self._stopped_keys.update(stopped)
1438
self._stopped_keys.update(revisions)
462
1441
def start_searching(self, revisions):
463
if self._search_revisions is None:
464
self._start = set(revisions)
466
self._search_revisions.update(revisions.difference(self.seen))
467
self.seen.update(revisions)
1442
"""Add revisions to the search.
1444
The parents of revisions will be returned from the next call to next()
1445
or next_with_ghosts(). If next_with_ghosts was the most recently used
1446
next* call then the return value is the result of looking up the
1447
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1449
revisions = frozenset(revisions)
1450
self._started_keys.update(revisions)
1451
new_revisions = revisions.difference(self.seen)
1452
if self._returning == 'next':
1453
self._next_query.update(new_revisions)
1454
self.seen.update(new_revisions)
1456
# perform a query on revisions
1457
revs, ghosts, query, parents = self._do_query(revisions)
1458
self._stopped_keys.update(ghosts)
1459
self._current_present.update(revs)
1460
self._current_ghosts.update(ghosts)
1461
self._next_query.update(query)
1462
self._current_parents.update(parents)
1466
class SearchResult(object):
1467
"""The result of a breadth first search.
1469
A SearchResult provides the ability to reconstruct the search or access a
1470
set of the keys the search found.
1473
def __init__(self, start_keys, exclude_keys, key_count, keys):
1474
"""Create a SearchResult.
1476
:param start_keys: The keys the search started at.
1477
:param exclude_keys: The keys the search excludes.
1478
:param key_count: The total number of keys (from start to but not
1480
:param keys: The keys the search found. Note that in future we may get
1481
a SearchResult from a smart server, in which case the keys list is
1482
not necessarily immediately available.
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
self._keys = frozenset(keys)
1487
def get_recipe(self):
1488
"""Return a recipe that can be used to replay this search.
1490
The recipe allows reconstruction of the same results at a later date
1491
without knowing all the found keys. The essential elements are a list
1492
of keys to start and to stop at. In order to give reproducible
1493
results when ghosts are encountered by a search they are automatically
1494
added to the exclude list (or else ghost filling may alter the
1497
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1498
revision_count). To recreate the results of this search, create a
1499
breadth first searcher on the same graph starting at start_keys.
1500
Then call next() (or next_with_ghosts()) repeatedly, and on every
1501
result, call stop_searching_any on any keys from the exclude_keys
1502
set. The revision_count value acts as a trivial cross-check - the
1503
found revisions of the new search should have as many elements as
1504
revision_count. If it does not, then additional revisions have been
1505
ghosted since the search was executed the first time and the second
1511
"""Return the keys found in this search.
1513
:return: A set of keys.
1518
"""Return false if the search lists 1 or more revisions."""
1519
return self._recipe[3] == 0
1521
def refine(self, seen, referenced):
1522
"""Create a new search by refining this search.
1524
:param seen: Revisions that have been satisfied.
1525
:param referenced: Revision references observed while satisfying some
1528
start = self._recipe[1]
1529
exclude = self._recipe[2]
1530
count = self._recipe[3]
1531
keys = self.get_keys()
1532
# New heads = referenced + old heads - seen things - exclude
1533
pending_refs = set(referenced)
1534
pending_refs.update(start)
1535
pending_refs.difference_update(seen)
1536
pending_refs.difference_update(exclude)
1537
# New exclude = old exclude + satisfied heads
1538
seen_heads = start.intersection(seen)
1539
exclude.update(seen_heads)
1540
# keys gets seen removed
1542
# length is reduced by len(seen)
1544
return SearchResult(pending_refs, exclude, count, keys)
1547
class PendingAncestryResult(object):
1548
"""A search result that will reconstruct the ancestry for some graph heads.
1550
Unlike SearchResult, this doesn't hold the complete search result in
1551
memory, it just holds a description of how to generate it.
1554
def __init__(self, heads, repo):
1557
:param heads: an iterable of graph heads.
1558
:param repo: a repository to use to generate the ancestry for the given
1561
self.heads = frozenset(heads)
1564
def get_recipe(self):
1565
"""Return a recipe that can be used to replay this search.
1567
The recipe allows reconstruction of the same results at a later date.
1569
:seealso SearchResult.get_recipe:
1571
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1572
To recreate this result, create a PendingAncestryResult with the
1575
return ('proxy-search', self.heads, set(), -1)
1578
"""See SearchResult.get_keys.
1580
Returns all the keys for the ancestry of the heads, excluding
1583
return self._get_keys(self.repo.get_graph())
1585
def _get_keys(self, graph):
1586
NULL_REVISION = revision.NULL_REVISION
1587
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1588
if key != NULL_REVISION and parents is not None]
1592
"""Return false if the search lists 1 or more revisions."""
1593
if revision.NULL_REVISION in self.heads:
1594
return len(self.heads) == 1
1596
return len(self.heads) == 0
1598
def refine(self, seen, referenced):
1599
"""Create a new search by refining this search.
1601
:param seen: Revisions that have been satisfied.
1602
:param referenced: Revision references observed while satisfying some
1605
referenced = self.heads.union(referenced)
1606
return PendingAncestryResult(referenced - seen, self.repo)
1609
def collapse_linear_regions(parent_map):
1610
"""Collapse regions of the graph that are 'linear'.
1616
can be collapsed by removing B and getting::
1620
:param parent_map: A dictionary mapping children to their parents
1621
:return: Another dictionary with 'linear' chains collapsed
1623
# Note: this isn't a strictly minimal collapse. For example:
1631
# Will not have 'D' removed, even though 'E' could fit. Also:
1637
# A and C are both kept because they are edges of the graph. We *could* get
1638
# rid of A if we wanted.
1646
# Will not have any nodes removed, even though you do have an
1647
# 'uninteresting' linear D->B and E->C
1649
for child, parents in parent_map.iteritems():
1650
children.setdefault(child, [])
1652
children.setdefault(p, []).append(child)
1654
orig_children = dict(children)
1656
result = dict(parent_map)
1657
for node in parent_map:
1658
parents = result[node]
1659
if len(parents) == 1:
1660
parent_children = children[parents[0]]
1661
if len(parent_children) != 1:
1662
# This is not the only child
1664
node_children = children[node]
1665
if len(node_children) != 1:
1667
child_parents = result.get(node_children[0], None)
1668
if len(child_parents) != 1:
1669
# This is not its only parent
1671
# The child of this node only points at it, and the parent only has
1672
# this as a child. remove this node, and join the others together
1673
result[node_children[0]] = parents
1674
children[parents[0]] = node_children
1682
class GraphThunkIdsToKeys(object):
1683
"""Forwards calls about 'ids' to be about keys internally."""
1685
def __init__(self, graph):
1688
def heads(self, ids):
1689
"""See Graph.heads()"""
1690
as_keys = [(i,) for i in ids]
1691
head_keys = self._graph.heads(as_keys)
1692
return set([h[0] for h in head_keys])
1695
_counters = [0,0,0,0,0,0,0]
1697
from bzrlib._known_graph_pyx import KnownGraph
1698
except ImportError, e:
1699
osutils.failed_to_load_extension(e)
1700
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
