200
202
def find_difference(self, left_revision, right_revision):
201
203
"""Determine the graph difference between two revisions"""
202
border, common, (left, right) = self._find_border_ancestors(
204
border, common, searchers = self._find_border_ancestors(
203
205
[left_revision, right_revision])
204
return (left.difference(right).difference(common),
205
right.difference(left).difference(common))
206
self._search_for_extra_common(common, searchers)
207
left = searchers[0].seen
208
right = searchers[1].seen
209
return (left.difference(right), right.difference(left))
211
def find_unique_ancestors(self, unique_revision, common_revisions):
212
"""Find the unique ancestors for a revision versus others.
214
This returns the ancestry of unique_revision, excluding all revisions
215
in the ancestry of common_revisions. If unique_revision is in the
216
ancestry, then the empty set will be returned.
218
:param unique_revision: The revision_id whose ancestry we are
220
XXX: Would this API be better if we allowed multiple revisions on
222
:param common_revisions: Revision_ids of ancestries to exclude.
223
:return: A set of revisions in the ancestry of unique_revision
225
if unique_revision in common_revisions:
228
# Algorithm description
229
# 1) Walk backwards from the unique node and all common nodes.
230
# 2) When a node is seen by both sides, stop searching it in the unique
231
# walker, include it in the common walker.
232
# 3) Stop searching when there are no nodes left for the unique walker.
233
# At this point, you have a maximal set of unique nodes. Some of
234
# them may actually be common, and you haven't reached them yet.
235
# 4) Start new searchers for the unique nodes, seeded with the
236
# information you have so far.
237
# 5) Continue searching, stopping the common searches when the search
238
# tip is an ancestor of all unique nodes.
239
# 6) Search is done when all common searchers have completed.
241
if 'graph' in debug.debug_flags:
242
_mutter = trace.mutter
244
def _mutter(*args, **kwargs):
247
unique_searcher = self._make_breadth_first_searcher([unique_revision])
248
# we know that unique_revision isn't in common_revisions
249
unique_searcher.next()
250
common_searcher = self._make_breadth_first_searcher(common_revisions)
252
while unique_searcher._next_query:
253
next_unique_nodes = set(unique_searcher.step())
254
next_common_nodes = set(common_searcher.step())
256
# Check if either searcher encounters new nodes seen by the other
258
unique_are_common_nodes = next_unique_nodes.intersection(
259
common_searcher.seen)
260
unique_are_common_nodes.update(
261
next_common_nodes.intersection(unique_searcher.seen))
262
if unique_are_common_nodes:
263
ancestors = unique_searcher.find_seen_ancestors(
264
unique_are_common_nodes)
265
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
266
unique_searcher.stop_searching_any(ancestors)
267
common_searcher.start_searching(ancestors)
269
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
272
unique_tips = self._remove_simple_descendants(unique_nodes,
273
self.get_parent_map(unique_nodes))
275
if len(unique_tips) == 1:
276
unique_searchers = []
277
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
279
unique_searchers = []
280
for tip in unique_tips:
281
revs_to_search = unique_searcher.find_seen_ancestors([tip])
282
searcher = self._make_breadth_first_searcher(revs_to_search)
283
# We don't care about the starting nodes.
284
searcher._label = tip
286
unique_searchers.append(searcher)
288
ancestor_all_unique = None
289
for searcher in unique_searchers:
290
if ancestor_all_unique is None:
291
ancestor_all_unique = set(searcher.seen)
293
ancestor_all_unique = ancestor_all_unique.intersection(
295
# Collapse all the common nodes into a single searcher
296
all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
297
if ancestor_all_unique:
298
all_unique_searcher.step()
300
# Stop any search tips that are already known as ancestors of the
302
common_searcher.stop_searching_any(
303
common_searcher.find_seen_ancestors(ancestor_all_unique))
306
for searcher in unique_searchers:
307
total_stopped += len(searcher.stop_searching_any(
308
searcher.find_seen_ancestors(ancestor_all_unique)))
309
_mutter('For %s unique nodes, created %s + 1 unique searchers'
310
' (%s stopped search tips, %s common ancestors)',
311
len(unique_nodes), len(unique_searchers), total_stopped,
312
len(ancestor_all_unique))
313
del ancestor_all_unique
315
# While we still have common nodes to search
316
while common_searcher._next_query:
317
newly_seen_common = set(common_searcher.step())
318
newly_seen_unique = set()
319
for searcher in unique_searchers:
320
newly_seen_unique.update(searcher.step())
321
# These nodes are common ancestors of all unique nodes
322
unique_are_common_nodes = newly_seen_unique.copy()
323
for searcher in unique_searchers:
324
unique_are_common_nodes = unique_are_common_nodes.intersection(
326
unique_are_common_nodes = unique_are_common_nodes.intersection(
327
all_unique_searcher.seen)
328
unique_are_common_nodes.update(all_unique_searcher.step())
329
if newly_seen_common:
330
# If a 'common' node is an ancestor of all unique searchers, we
331
# can stop searching it.
332
common_searcher.stop_searching_any(
333
all_unique_searcher.seen.intersection(newly_seen_common))
334
if unique_are_common_nodes:
335
# We have new common-to-all-unique-searchers nodes
336
for searcher in unique_searchers:
337
unique_are_common_nodes.update(
338
searcher.find_seen_ancestors(unique_are_common_nodes))
339
unique_are_common_nodes.update(
340
all_unique_searcher.find_seen_ancestors(unique_are_common_nodes))
341
# Since these are common, we can grab another set of ancestors
343
unique_are_common_nodes.update(
344
common_searcher.find_seen_ancestors(unique_are_common_nodes))
346
# The all_unique searcher can start searching the common nodes
347
# but everyone else can stop.
348
all_unique_searcher.start_searching(unique_are_common_nodes)
349
common_searcher.stop_searching_any(unique_are_common_nodes)
351
# Filter out searchers that don't actually search different
352
# nodes. We already have the ancestry intersection for them
353
next_unique_searchers = []
354
unique_search_sets = set()
355
for searcher in unique_searchers:
356
stopped = searcher.stop_searching_any(unique_are_common_nodes)
357
will_search_set = frozenset(searcher._next_query)
358
if not will_search_set:
359
_mutter('Unique searcher %s was stopped.'
360
' (%s iterations) %d nodes stopped',
362
searcher._iterations,
364
elif will_search_set not in unique_search_sets:
365
# This searcher is searching a unique set of nodes, let it
366
unique_search_sets.add(will_search_set)
367
next_unique_searchers.append(searcher)
369
_mutter('Unique searcher %s stopped for repeated'
370
' search of %s nodes',
371
searcher._label, len(will_search_set))
372
if len(unique_searchers) != len(next_unique_searchers):
373
_mutter('Collapsed %s unique searchers => %s'
375
len(unique_searchers), len(next_unique_searchers),
376
all_unique_searcher._iterations)
377
unique_searchers = next_unique_searchers
378
return unique_nodes.difference(common_searcher.seen)
207
380
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
381
def get_parents(self, revisions):
254
427
if None in revisions:
255
428
raise errors.InvalidRevisionId(None, self)
256
common_searcher = self._make_breadth_first_searcher([])
257
429
common_ancestors = set()
258
430
searchers = [self._make_breadth_first_searcher([r])
259
431
for r in revisions]
260
432
active_searchers = searchers[:]
261
433
border_ancestors = set()
262
def update_common(searcher, revisions):
263
w_seen_ancestors = searcher.find_seen_ancestors(
265
stopped = searcher.stop_searching_any(w_seen_ancestors)
266
common_ancestors.update(w_seen_ancestors)
267
common_searcher.start_searching(stopped)
270
if len(active_searchers) == 0:
271
return border_ancestors, common_ancestors, [s.seen for s in
274
new_common = common_searcher.next()
275
common_ancestors.update(new_common)
276
except StopIteration:
279
for searcher in active_searchers:
280
for revision in new_common.intersection(searcher.seen):
281
update_common(searcher, revision)
283
436
newly_seen = set()
284
new_active_searchers = []
285
for searcher in active_searchers:
287
newly_seen.update(searcher.next())
288
except StopIteration:
291
new_active_searchers.append(searcher)
292
active_searchers = new_active_searchers
437
for searcher in searchers:
438
new_ancestors = searcher.step()
440
newly_seen.update(new_ancestors)
293
442
for revision in newly_seen:
294
443
if revision in common_ancestors:
295
for searcher in searchers:
296
update_common(searcher, revision)
444
# Not a border ancestor because it was seen as common
446
new_common.add(revision)
298
448
for searcher in searchers:
299
449
if revision not in searcher.seen:
452
# This is a border because it is a first common that we see
453
# after walking for a while.
302
454
border_ancestors.add(revision)
303
for searcher in searchers:
304
update_common(searcher, revision)
455
new_common.add(revision)
457
for searcher in searchers:
458
new_common.update(searcher.find_seen_ancestors(new_common))
459
for searcher in searchers:
460
searcher.start_searching(new_common)
461
common_ancestors.update(new_common)
463
# Figure out what the searchers will be searching next, and if
464
# there is only 1 set being searched, then we are done searching,
465
# since all searchers would have to be searching the same data,
466
# thus it *must* be in common.
467
unique_search_sets = set()
468
for searcher in searchers:
469
will_search_set = frozenset(searcher._next_query)
470
if will_search_set not in unique_search_sets:
471
# This searcher is searching a unique set of nodes, let it
472
unique_search_sets.add(will_search_set)
474
if len(unique_search_sets) == 1:
475
nodes = unique_search_sets.pop()
476
uncommon_nodes = nodes.difference(common_ancestors)
478
raise AssertionError("Somehow we ended up converging"
479
" without actually marking them as"
482
"\nuncommon_nodes: %s"
483
% (revisions, uncommon_nodes))
485
return border_ancestors, common_ancestors, searchers
306
487
def heads(self, keys):
307
488
"""Return the heads from amongst keys.
469
650
return set([candidate_descendant]) == self.heads(
470
651
[candidate_ancestor, candidate_descendant])
653
def _search_for_extra_common(self, common, searchers):
654
"""Make sure that unique nodes are genuinely unique.
656
After _find_border_ancestors, all nodes marked "common" are indeed
657
common. Some of the nodes considered unique are not, due to history
658
shortcuts stopping the searches early.
660
We know that we have searched enough when all common search tips are
661
descended from all unique (uncommon) nodes because we know that a node
662
cannot be an ancestor of its own ancestor.
664
:param common: A set of common nodes
665
:param searchers: The searchers returned from _find_border_ancestors
669
# A) The passed in searchers should all be on the same tips, thus
670
# they should be considered the "common" searchers.
671
# B) We find the difference between the searchers, these are the
672
# "unique" nodes for each side.
673
# C) We do a quick culling so that we only start searching from the
674
# more interesting unique nodes. (A unique ancestor is more
675
# interesting than any of its children.)
676
# D) We start searching for ancestors common to all unique nodes.
677
# E) We have the common searchers stop searching any ancestors of
679
# F) When there are no more common search tips, we stop
681
# TODO: We need a way to remove unique_searchers when they overlap with
682
# other unique searchers.
683
if len(searchers) != 2:
684
raise NotImplementedError(
685
"Algorithm not yet implemented for > 2 searchers")
686
common_searchers = searchers
687
left_searcher = searchers[0]
688
right_searcher = searchers[1]
689
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
690
if not unique: # No unique nodes, nothing to do
692
total_unique = len(unique)
693
unique = self._remove_simple_descendants(unique,
694
self.get_parent_map(unique))
695
simple_unique = len(unique)
697
unique_searchers = []
698
for revision_id in unique:
699
if revision_id in left_searcher.seen:
700
parent_searcher = left_searcher
702
parent_searcher = right_searcher
703
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
704
if not revs_to_search: # XXX: This shouldn't be possible
705
revs_to_search = [revision_id]
706
searcher = self._make_breadth_first_searcher(revs_to_search)
707
# We don't care about the starting nodes.
709
unique_searchers.append(searcher)
711
# possible todo: aggregate the common searchers into a single common
712
# searcher, just make sure that we include the nodes into the .seen
713
# properties of the original searchers
715
ancestor_all_unique = None
716
for searcher in unique_searchers:
717
if ancestor_all_unique is None:
718
ancestor_all_unique = set(searcher.seen)
720
ancestor_all_unique = ancestor_all_unique.intersection(
723
trace.mutter('Started %s unique searchers for %s unique revisions',
724
simple_unique, total_unique)
726
while True: # If we have no more nodes we have nothing to do
727
newly_seen_common = set()
728
for searcher in common_searchers:
729
newly_seen_common.update(searcher.step())
730
newly_seen_unique = set()
731
for searcher in unique_searchers:
732
newly_seen_unique.update(searcher.step())
733
new_common_unique = set()
734
for revision in newly_seen_unique:
735
for searcher in unique_searchers:
736
if revision not in searcher.seen:
739
# This is a border because it is a first common that we see
740
# after walking for a while.
741
new_common_unique.add(revision)
742
if newly_seen_common:
743
# These are nodes descended from one of the 'common' searchers.
744
# Make sure all searchers are on the same page
745
for searcher in common_searchers:
746
newly_seen_common.update(
747
searcher.find_seen_ancestors(newly_seen_common))
748
# We start searching the whole ancestry. It is a bit wasteful,
749
# though. We really just want to mark all of these nodes as
750
# 'seen' and then start just the tips. However, it requires a
751
# get_parent_map() call to figure out the tips anyway, and all
752
# redundant requests should be fairly fast.
753
for searcher in common_searchers:
754
searcher.start_searching(newly_seen_common)
756
# If a 'common' node is an ancestor of all unique searchers, we
757
# can stop searching it.
758
stop_searching_common = ancestor_all_unique.intersection(
760
if stop_searching_common:
761
for searcher in common_searchers:
762
searcher.stop_searching_any(stop_searching_common)
763
if new_common_unique:
764
# We found some ancestors that are common
765
for searcher in unique_searchers:
766
new_common_unique.update(
767
searcher.find_seen_ancestors(new_common_unique))
768
# Since these are common, we can grab another set of ancestors
770
for searcher in common_searchers:
771
new_common_unique.update(
772
searcher.find_seen_ancestors(new_common_unique))
774
# We can tell all of the unique searchers to start at these
775
# nodes, and tell all of the common searchers to *stop*
776
# searching these nodes
777
for searcher in unique_searchers:
778
searcher.start_searching(new_common_unique)
779
for searcher in common_searchers:
780
searcher.stop_searching_any(new_common_unique)
781
ancestor_all_unique.update(new_common_unique)
783
# Filter out searchers that don't actually search different
784
# nodes. We already have the ancestry intersection for them
785
next_unique_searchers = []
786
unique_search_sets = set()
787
for searcher in unique_searchers:
788
will_search_set = frozenset(searcher._next_query)
789
if will_search_set not in unique_search_sets:
790
# This searcher is searching a unique set of nodes, let it
791
unique_search_sets.add(will_search_set)
792
next_unique_searchers.append(searcher)
793
unique_searchers = next_unique_searchers
794
for searcher in common_searchers:
795
if searcher._next_query:
798
# All common searcher have stopped searching
801
def _remove_simple_descendants(self, revisions, parent_map):
802
"""remove revisions which are children of other ones in the set
804
This doesn't do any graph searching, it just checks the immediate
805
parent_map to find if there are any children which can be removed.
807
:param revisions: A set of revision_ids
808
:return: A set of revision_ids with the children removed
810
simple_ancestors = revisions.copy()
811
# TODO: jam 20071214 we *could* restrict it to searching only the
812
# parent_map of revisions already present in 'revisions', but
813
# considering the general use case, I think this is actually
816
# This is the same as the following loop. I don't know that it is any
818
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
819
## if p_ids is not None and revisions.intersection(p_ids))
820
## return simple_ancestors
822
# Yet Another Way, invert the parent map (which can be cached)
824
## for revision_id, parent_ids in parent_map.iteritems():
825
## for p_id in parent_ids:
826
## descendants.setdefault(p_id, []).append(revision_id)
827
## for revision in revisions.intersection(descendants):
828
## simple_ancestors.difference_update(descendants[revision])
829
## return simple_ancestors
830
for revision, parent_ids in parent_map.iteritems():
831
if parent_ids is None:
833
for parent_id in parent_ids:
834
if parent_id in revisions:
835
# This node has a parent present in the set, so we can
837
simple_ancestors.discard(revision)
839
return simple_ancestors
473
842
class HeadsCache(object):
474
843
"""A cache of results for graph heads calls."""
652
1027
:return: A tuple: (set(found_revisions), set(ghost_revisions),
653
1028
set(parents_of_found_revisions), dict(found_revisions:parents)).
655
found_parents = set()
1030
found_revisions = set()
656
1031
parents_of_found = set()
657
1032
# revisions may contain nodes that point to other nodes in revisions:
658
1033
# we want to filter them out.
659
1034
self.seen.update(revisions)
660
1035
parent_map = self._parents_provider.get_parent_map(revisions)
1036
found_revisions.update(parent_map)
661
1037
for rev_id, parents in parent_map.iteritems():
662
found_parents.add(rev_id)
663
parents_of_found.update(p for p in parents if p not in self.seen)
664
ghost_parents = revisions - found_parents
665
return found_parents, ghost_parents, parents_of_found, parent_map
1038
new_found_parents = [p for p in parents if p not in self.seen]
1039
if new_found_parents:
1040
# Calling set.update() with an empty generator is actually
1042
parents_of_found.update(new_found_parents)
1043
ghost_revisions = revisions - found_revisions
1044
return found_revisions, ghost_revisions, parents_of_found, parent_map
667
1046
def __iter__(self):
670
def find_seen_ancestors(self, revision):
671
"""Find ancestors of this revision that have already been seen."""
672
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
673
seen_ancestors = set()
674
for ancestors in searcher:
675
for ancestor in ancestors:
676
if ancestor not in self.seen:
677
searcher.stop_searching_any([ancestor])
679
seen_ancestors.add(ancestor)
1049
def find_seen_ancestors(self, revisions):
1050
"""Find ancestors of these revisions that have already been seen."""
1051
all_seen = self.seen
1052
pending = set(revisions).intersection(all_seen)
1053
seen_ancestors = set(pending)
1055
if self._returning == 'next':
1056
# self.seen contains what nodes have been returned, not what nodes
1057
# have been queried. We don't want to probe for nodes that haven't
1058
# been searched yet.
1059
not_searched_yet = self._next_query
1061
not_searched_yet = ()
1062
pending.difference_update(not_searched_yet)
1063
get_parent_map = self._parents_provider.get_parent_map
1065
parent_map = get_parent_map(pending)
1067
# We don't care if it is a ghost, since it can't be seen if it is
1069
for parent_ids in parent_map.itervalues():
1070
all_parents.extend(parent_ids)
1071
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1072
seen_ancestors.update(next_pending)
1073
next_pending.difference_update(not_searched_yet)
1074
pending = next_pending
680
1076
return seen_ancestors
682
1078
def stop_searching_any(self, revisions):
added
removed
bzrlib/graph.py
