200
206
def find_difference(self, left_revision, right_revision):
201
207
"""Determine the graph difference between two revisions"""
202
border, common, (left, right) = self._find_border_ancestors(
208
border, common, searchers = self._find_border_ancestors(
203
209
[left_revision, right_revision])
204
return (left.difference(right).difference(common),
205
right.difference(left).difference(common))
210
self._search_for_extra_common(common, searchers)
211
left = searchers[0].seen
212
right = searchers[1].seen
213
return (left.difference(right), right.difference(left))
215
def find_distance_to_null(self, target_revision_id, known_revision_ids):
216
"""Find the left-hand distance to the NULL_REVISION.
218
(This can also be considered the revno of a branch at
221
:param target_revision_id: A revision_id which we would like to know
223
:param known_revision_ids: [(revision_id, revno)] A list of known
224
revno, revision_id tuples. We'll use this to seed the search.
226
# Map from revision_ids to a known value for their revno
227
known_revnos = dict(known_revision_ids)
228
cur_tip = target_revision_id
230
NULL_REVISION = revision.NULL_REVISION
231
known_revnos[NULL_REVISION] = 0
233
searching_known_tips = list(known_revnos.keys())
235
unknown_searched = {}
237
while cur_tip not in known_revnos:
238
unknown_searched[cur_tip] = num_steps
240
to_search = set([cur_tip])
241
to_search.update(searching_known_tips)
242
parent_map = self.get_parent_map(to_search)
243
parents = parent_map.get(cur_tip, None)
244
if not parents: # An empty list or None is a ghost
245
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
249
for revision_id in searching_known_tips:
250
parents = parent_map.get(revision_id, None)
254
next_revno = known_revnos[revision_id] - 1
255
if next in unknown_searched:
256
# We have enough information to return a value right now
257
return next_revno + unknown_searched[next]
258
if next in known_revnos:
260
known_revnos[next] = next_revno
261
next_known_tips.append(next)
262
searching_known_tips = next_known_tips
264
# We reached a known revision, so just add in how many steps it took to
266
return known_revnos[cur_tip] + num_steps
268
def find_unique_ancestors(self, unique_revision, common_revisions):
269
"""Find the unique ancestors for a revision versus others.
271
This returns the ancestry of unique_revision, excluding all revisions
272
in the ancestry of common_revisions. If unique_revision is in the
273
ancestry, then the empty set will be returned.
275
:param unique_revision: The revision_id whose ancestry we are
277
XXX: Would this API be better if we allowed multiple revisions on
279
:param common_revisions: Revision_ids of ancestries to exclude.
280
:return: A set of revisions in the ancestry of unique_revision
282
if unique_revision in common_revisions:
285
# Algorithm description
286
# 1) Walk backwards from the unique node and all common nodes.
287
# 2) When a node is seen by both sides, stop searching it in the unique
288
# walker, include it in the common walker.
289
# 3) Stop searching when there are no nodes left for the unique walker.
290
# At this point, you have a maximal set of unique nodes. Some of
291
# them may actually be common, and you haven't reached them yet.
292
# 4) Start new searchers for the unique nodes, seeded with the
293
# information you have so far.
294
# 5) Continue searching, stopping the common searches when the search
295
# tip is an ancestor of all unique nodes.
296
# 6) Aggregate together unique searchers when they are searching the
297
# same tips. When all unique searchers are searching the same node,
298
# stop move it to a single 'all_unique_searcher'.
299
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
300
# Most of the time this produces very little important information.
301
# So don't step it as quickly as the other searchers.
302
# 8) Search is done when all common searchers have completed.
304
unique_searcher, common_searcher = self._find_initial_unique_nodes(
305
[unique_revision], common_revisions)
307
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
311
(all_unique_searcher,
312
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
313
unique_searcher, common_searcher)
315
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
316
unique_tip_searchers, common_searcher)
317
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
318
if 'graph' in debug.debug_flags:
319
trace.mutter('Found %d truly unique nodes out of %d',
320
len(true_unique_nodes), len(unique_nodes))
321
return true_unique_nodes
323
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
324
"""Steps 1-3 of find_unique_ancestors.
326
Find the maximal set of unique nodes. Some of these might actually
327
still be common, but we are sure that there are no other unique nodes.
329
:return: (unique_searcher, common_searcher)
332
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
333
# we know that unique_revisions aren't in common_revisions, so skip
335
unique_searcher.next()
336
common_searcher = self._make_breadth_first_searcher(common_revisions)
338
# As long as we are still finding unique nodes, keep searching
339
while unique_searcher._next_query:
340
next_unique_nodes = set(unique_searcher.step())
341
next_common_nodes = set(common_searcher.step())
343
# Check if either searcher encounters new nodes seen by the other
345
unique_are_common_nodes = next_unique_nodes.intersection(
346
common_searcher.seen)
347
unique_are_common_nodes.update(
348
next_common_nodes.intersection(unique_searcher.seen))
349
if unique_are_common_nodes:
350
ancestors = unique_searcher.find_seen_ancestors(
351
unique_are_common_nodes)
352
# TODO: This is a bit overboard, we only really care about
353
# the ancestors of the tips because the rest we
354
# already know. This is *correct* but causes us to
355
# search too much ancestry.
356
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
357
unique_searcher.stop_searching_any(ancestors)
358
common_searcher.start_searching(ancestors)
360
return unique_searcher, common_searcher
362
def _make_unique_searchers(self, unique_nodes, unique_searcher,
364
"""Create a searcher for all the unique search tips (step 4).
366
As a side effect, the common_searcher will stop searching any nodes
367
that are ancestors of the unique searcher tips.
369
:return: (all_unique_searcher, unique_tip_searchers)
371
unique_tips = self._remove_simple_descendants(unique_nodes,
372
self.get_parent_map(unique_nodes))
374
if len(unique_tips) == 1:
375
unique_tip_searchers = []
376
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
378
unique_tip_searchers = []
379
for tip in unique_tips:
380
revs_to_search = unique_searcher.find_seen_ancestors([tip])
381
revs_to_search.update(
382
common_searcher.find_seen_ancestors(revs_to_search))
383
searcher = self._make_breadth_first_searcher(revs_to_search)
384
# We don't care about the starting nodes.
385
searcher._label = tip
387
unique_tip_searchers.append(searcher)
389
ancestor_all_unique = None
390
for searcher in unique_tip_searchers:
391
if ancestor_all_unique is None:
392
ancestor_all_unique = set(searcher.seen)
394
ancestor_all_unique = ancestor_all_unique.intersection(
396
# Collapse all the common nodes into a single searcher
397
all_unique_searcher = self._make_breadth_first_searcher(
399
if ancestor_all_unique:
400
# We've seen these nodes in all the searchers, so we'll just go to
402
all_unique_searcher.step()
404
# Stop any search tips that are already known as ancestors of the
406
stopped_common = common_searcher.stop_searching_any(
407
common_searcher.find_seen_ancestors(ancestor_all_unique))
410
for searcher in unique_tip_searchers:
411
total_stopped += len(searcher.stop_searching_any(
412
searcher.find_seen_ancestors(ancestor_all_unique)))
413
if 'graph' in debug.debug_flags:
414
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
415
' (%d stopped search tips, %d common ancestors'
416
' (%d stopped common)',
417
len(unique_nodes), len(unique_tip_searchers),
418
total_stopped, len(ancestor_all_unique),
420
return all_unique_searcher, unique_tip_searchers
422
def _step_unique_and_common_searchers(self, common_searcher,
423
unique_tip_searchers,
425
"""Step all the searchers"""
426
newly_seen_common = set(common_searcher.step())
427
newly_seen_unique = set()
428
for searcher in unique_tip_searchers:
429
next = set(searcher.step())
430
next.update(unique_searcher.find_seen_ancestors(next))
431
next.update(common_searcher.find_seen_ancestors(next))
432
for alt_searcher in unique_tip_searchers:
433
if alt_searcher is searcher:
435
next.update(alt_searcher.find_seen_ancestors(next))
436
searcher.start_searching(next)
437
newly_seen_unique.update(next)
438
return newly_seen_common, newly_seen_unique
440
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
442
newly_seen_unique, step_all_unique):
443
"""Find nodes that are common to all unique_tip_searchers.
445
If it is time, step the all_unique_searcher, and add its nodes to the
448
common_to_all_unique_nodes = newly_seen_unique.copy()
449
for searcher in unique_tip_searchers:
450
common_to_all_unique_nodes.intersection_update(searcher.seen)
451
common_to_all_unique_nodes.intersection_update(
452
all_unique_searcher.seen)
453
# Step all-unique less frequently than the other searchers.
454
# In the common case, we don't need to spider out far here, so
455
# avoid doing extra work.
457
tstart = time.clock()
458
nodes = all_unique_searcher.step()
459
common_to_all_unique_nodes.update(nodes)
460
if 'graph' in debug.debug_flags:
461
tdelta = time.clock() - tstart
462
trace.mutter('all_unique_searcher step() took %.3fs'
463
'for %d nodes (%d total), iteration: %s',
464
tdelta, len(nodes), len(all_unique_searcher.seen),
465
all_unique_searcher._iterations)
466
return common_to_all_unique_nodes
468
def _collapse_unique_searchers(self, unique_tip_searchers,
469
common_to_all_unique_nodes):
470
"""Combine searchers that are searching the same tips.
472
When two searchers are searching the same tips, we can stop one of the
473
searchers. We also know that the maximal set of common ancestors is the
474
intersection of the two original searchers.
476
:return: A list of searchers that are searching unique nodes.
478
# Filter out searchers that don't actually search different
479
# nodes. We already have the ancestry intersection for them
480
unique_search_tips = {}
481
for searcher in unique_tip_searchers:
482
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
483
will_search_set = frozenset(searcher._next_query)
484
if not will_search_set:
485
if 'graph' in debug.debug_flags:
486
trace.mutter('Unique searcher %s was stopped.'
487
' (%s iterations) %d nodes stopped',
489
searcher._iterations,
491
elif will_search_set not in unique_search_tips:
492
# This searcher is searching a unique set of nodes, let it
493
unique_search_tips[will_search_set] = [searcher]
495
unique_search_tips[will_search_set].append(searcher)
496
# TODO: it might be possible to collapse searchers faster when they
497
# only have *some* search tips in common.
498
next_unique_searchers = []
499
for searchers in unique_search_tips.itervalues():
500
if len(searchers) == 1:
501
# Searching unique tips, go for it
502
next_unique_searchers.append(searchers[0])
504
# These searchers have started searching the same tips, we
505
# don't need them to cover the same ground. The
506
# intersection of their ancestry won't change, so create a
507
# new searcher, combining their histories.
508
next_searcher = searchers[0]
509
for searcher in searchers[1:]:
510
next_searcher.seen.intersection_update(searcher.seen)
511
if 'graph' in debug.debug_flags:
512
trace.mutter('Combining %d searchers into a single'
513
' searcher searching %d nodes with'
516
len(next_searcher._next_query),
517
len(next_searcher.seen))
518
next_unique_searchers.append(next_searcher)
519
return next_unique_searchers
521
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
522
unique_tip_searchers, common_searcher):
523
"""Steps 5-8 of find_unique_ancestors.
525
This function returns when common_searcher has stopped searching for
528
# We step the ancestor_all_unique searcher only every
529
# STEP_UNIQUE_SEARCHER_EVERY steps.
530
step_all_unique_counter = 0
531
# While we still have common nodes to search
532
while common_searcher._next_query:
534
newly_seen_unique) = self._step_unique_and_common_searchers(
535
common_searcher, unique_tip_searchers, unique_searcher)
536
# These nodes are common ancestors of all unique nodes
537
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
538
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
539
step_all_unique_counter==0)
540
step_all_unique_counter = ((step_all_unique_counter + 1)
541
% STEP_UNIQUE_SEARCHER_EVERY)
543
if newly_seen_common:
544
# If a 'common' node is an ancestor of all unique searchers, we
545
# can stop searching it.
546
common_searcher.stop_searching_any(
547
all_unique_searcher.seen.intersection(newly_seen_common))
548
if common_to_all_unique_nodes:
549
common_to_all_unique_nodes.update(
550
common_searcher.find_seen_ancestors(
551
common_to_all_unique_nodes))
552
# The all_unique searcher can start searching the common nodes
553
# but everyone else can stop.
554
# This is the sort of thing where we would like to not have it
555
# start_searching all of the nodes, but only mark all of them
556
# as seen, and have it search only the actual tips. Otherwise
557
# it is another get_parent_map() traversal for it to figure out
558
# what we already should know.
559
all_unique_searcher.start_searching(common_to_all_unique_nodes)
560
common_searcher.stop_searching_any(common_to_all_unique_nodes)
562
next_unique_searchers = self._collapse_unique_searchers(
563
unique_tip_searchers, common_to_all_unique_nodes)
564
if len(unique_tip_searchers) != len(next_unique_searchers):
565
if 'graph' in debug.debug_flags:
566
trace.mutter('Collapsed %d unique searchers => %d'
568
len(unique_tip_searchers),
569
len(next_unique_searchers),
570
all_unique_searcher._iterations)
571
unique_tip_searchers = next_unique_searchers
207
573
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
574
def get_parents(self, revisions):
254
620
if None in revisions:
255
621
raise errors.InvalidRevisionId(None, self)
256
common_searcher = self._make_breadth_first_searcher([])
257
622
common_ancestors = set()
258
623
searchers = [self._make_breadth_first_searcher([r])
259
624
for r in revisions]
260
625
active_searchers = searchers[:]
261
626
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
629
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
630
for searcher in searchers:
631
new_ancestors = searcher.step()
633
newly_seen.update(new_ancestors)
293
635
for revision in newly_seen:
294
636
if revision in common_ancestors:
295
for searcher in searchers:
296
update_common(searcher, revision)
637
# Not a border ancestor because it was seen as common
639
new_common.add(revision)
298
641
for searcher in searchers:
299
642
if revision not in searcher.seen:
645
# This is a border because it is a first common that we see
646
# after walking for a while.
302
647
border_ancestors.add(revision)
303
for searcher in searchers:
304
update_common(searcher, revision)
648
new_common.add(revision)
650
for searcher in searchers:
651
new_common.update(searcher.find_seen_ancestors(new_common))
652
for searcher in searchers:
653
searcher.start_searching(new_common)
654
common_ancestors.update(new_common)
656
# Figure out what the searchers will be searching next, and if
657
# there is only 1 set being searched, then we are done searching,
658
# since all searchers would have to be searching the same data,
659
# thus it *must* be in common.
660
unique_search_sets = set()
661
for searcher in searchers:
662
will_search_set = frozenset(searcher._next_query)
663
if will_search_set not in unique_search_sets:
664
# This searcher is searching a unique set of nodes, let it
665
unique_search_sets.add(will_search_set)
667
if len(unique_search_sets) == 1:
668
nodes = unique_search_sets.pop()
669
uncommon_nodes = nodes.difference(common_ancestors)
671
raise AssertionError("Somehow we ended up converging"
672
" without actually marking them as"
675
"\nuncommon_nodes: %s"
676
% (revisions, uncommon_nodes))
678
return border_ancestors, common_ancestors, searchers
306
680
def heads(self, keys):
307
681
"""Return the heads from amongst keys.
444
843
return set([candidate_descendant]) == self.heads(
445
844
[candidate_ancestor, candidate_descendant])
846
def _search_for_extra_common(self, common, searchers):
847
"""Make sure that unique nodes are genuinely unique.
849
After _find_border_ancestors, all nodes marked "common" are indeed
850
common. Some of the nodes considered unique are not, due to history
851
shortcuts stopping the searches early.
853
We know that we have searched enough when all common search tips are
854
descended from all unique (uncommon) nodes because we know that a node
855
cannot be an ancestor of its own ancestor.
857
:param common: A set of common nodes
858
:param searchers: The searchers returned from _find_border_ancestors
862
# A) The passed in searchers should all be on the same tips, thus
863
# they should be considered the "common" searchers.
864
# B) We find the difference between the searchers, these are the
865
# "unique" nodes for each side.
866
# C) We do a quick culling so that we only start searching from the
867
# more interesting unique nodes. (A unique ancestor is more
868
# interesting than any of its children.)
869
# D) We start searching for ancestors common to all unique nodes.
870
# E) We have the common searchers stop searching any ancestors of
872
# F) When there are no more common search tips, we stop
874
# TODO: We need a way to remove unique_searchers when they overlap with
875
# other unique searchers.
876
if len(searchers) != 2:
877
raise NotImplementedError(
878
"Algorithm not yet implemented for > 2 searchers")
879
common_searchers = searchers
880
left_searcher = searchers[0]
881
right_searcher = searchers[1]
882
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
883
if not unique: # No unique nodes, nothing to do
885
total_unique = len(unique)
886
unique = self._remove_simple_descendants(unique,
887
self.get_parent_map(unique))
888
simple_unique = len(unique)
890
unique_searchers = []
891
for revision_id in unique:
892
if revision_id in left_searcher.seen:
893
parent_searcher = left_searcher
895
parent_searcher = right_searcher
896
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
897
if not revs_to_search: # XXX: This shouldn't be possible
898
revs_to_search = [revision_id]
899
searcher = self._make_breadth_first_searcher(revs_to_search)
900
# We don't care about the starting nodes.
902
unique_searchers.append(searcher)
904
# possible todo: aggregate the common searchers into a single common
905
# searcher, just make sure that we include the nodes into the .seen
906
# properties of the original searchers
908
ancestor_all_unique = None
909
for searcher in unique_searchers:
910
if ancestor_all_unique is None:
911
ancestor_all_unique = set(searcher.seen)
913
ancestor_all_unique = ancestor_all_unique.intersection(
916
trace.mutter('Started %s unique searchers for %s unique revisions',
917
simple_unique, total_unique)
919
while True: # If we have no more nodes we have nothing to do
920
newly_seen_common = set()
921
for searcher in common_searchers:
922
newly_seen_common.update(searcher.step())
923
newly_seen_unique = set()
924
for searcher in unique_searchers:
925
newly_seen_unique.update(searcher.step())
926
new_common_unique = set()
927
for revision in newly_seen_unique:
928
for searcher in unique_searchers:
929
if revision not in searcher.seen:
932
# This is a border because it is a first common that we see
933
# after walking for a while.
934
new_common_unique.add(revision)
935
if newly_seen_common:
936
# These are nodes descended from one of the 'common' searchers.
937
# Make sure all searchers are on the same page
938
for searcher in common_searchers:
939
newly_seen_common.update(
940
searcher.find_seen_ancestors(newly_seen_common))
941
# We start searching the whole ancestry. It is a bit wasteful,
942
# though. We really just want to mark all of these nodes as
943
# 'seen' and then start just the tips. However, it requires a
944
# get_parent_map() call to figure out the tips anyway, and all
945
# redundant requests should be fairly fast.
946
for searcher in common_searchers:
947
searcher.start_searching(newly_seen_common)
949
# If a 'common' node is an ancestor of all unique searchers, we
950
# can stop searching it.
951
stop_searching_common = ancestor_all_unique.intersection(
953
if stop_searching_common:
954
for searcher in common_searchers:
955
searcher.stop_searching_any(stop_searching_common)
956
if new_common_unique:
957
# We found some ancestors that are common
958
for searcher in unique_searchers:
959
new_common_unique.update(
960
searcher.find_seen_ancestors(new_common_unique))
961
# Since these are common, we can grab another set of ancestors
963
for searcher in common_searchers:
964
new_common_unique.update(
965
searcher.find_seen_ancestors(new_common_unique))
967
# We can tell all of the unique searchers to start at these
968
# nodes, and tell all of the common searchers to *stop*
969
# searching these nodes
970
for searcher in unique_searchers:
971
searcher.start_searching(new_common_unique)
972
for searcher in common_searchers:
973
searcher.stop_searching_any(new_common_unique)
974
ancestor_all_unique.update(new_common_unique)
976
# Filter out searchers that don't actually search different
977
# nodes. We already have the ancestry intersection for them
978
next_unique_searchers = []
979
unique_search_sets = set()
980
for searcher in unique_searchers:
981
will_search_set = frozenset(searcher._next_query)
982
if will_search_set not in unique_search_sets:
983
# This searcher is searching a unique set of nodes, let it
984
unique_search_sets.add(will_search_set)
985
next_unique_searchers.append(searcher)
986
unique_searchers = next_unique_searchers
987
for searcher in common_searchers:
988
if searcher._next_query:
991
# All common searcher have stopped searching
994
def _remove_simple_descendants(self, revisions, parent_map):
995
"""remove revisions which are children of other ones in the set
997
This doesn't do any graph searching, it just checks the immediate
998
parent_map to find if there are any children which can be removed.
1000
:param revisions: A set of revision_ids
1001
:return: A set of revision_ids with the children removed
1003
simple_ancestors = revisions.copy()
1004
# TODO: jam 20071214 we *could* restrict it to searching only the
1005
# parent_map of revisions already present in 'revisions', but
1006
# considering the general use case, I think this is actually
1009
# This is the same as the following loop. I don't know that it is any
1011
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1012
## if p_ids is not None and revisions.intersection(p_ids))
1013
## return simple_ancestors
1015
# Yet Another Way, invert the parent map (which can be cached)
1017
## for revision_id, parent_ids in parent_map.iteritems():
1018
## for p_id in parent_ids:
1019
## descendants.setdefault(p_id, []).append(revision_id)
1020
## for revision in revisions.intersection(descendants):
1021
## simple_ancestors.difference_update(descendants[revision])
1022
## return simple_ancestors
1023
for revision, parent_ids in parent_map.iteritems():
1024
if parent_ids is None:
1026
for parent_id in parent_ids:
1027
if parent_id in revisions:
1028
# This node has a parent present in the set, so we can
1030
simple_ancestors.discard(revision)
1032
return simple_ancestors
448
1035
class HeadsCache(object):
449
1036
"""A cache of results for graph heads calls."""
added
removed
bzrlib/graph.py
