206
142
def find_difference(self, left_revision, right_revision):
207
143
"""Determine the graph difference between two revisions"""
208
border, common, searchers = self._find_border_ancestors(
144
border, common, (left, right) = self._find_border_ancestors(
209
145
[left_revision, right_revision])
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
573
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
574
def get_parents(self, revisions):
575
"""Find revision ids of the parents of a list of revisions
577
A list is returned of the same length as the input. Each entry
578
is a list of parent ids for the corresponding input revision.
580
[NULL_REVISION] is used as the parent of the first user-committed
581
revision. Its parent list is empty.
583
If the revision is not present (i.e. a ghost), None is used in place
584
of the list of parents.
586
Deprecated in bzr 1.2 - please see get_parent_map.
588
parents = self.get_parent_map(revisions)
589
return [parents.get(r, None) for r in revisions]
591
def get_parent_map(self, revisions):
592
"""Get a map of key:parent_list for revisions.
594
This implementation delegates to get_parents, for old parent_providers
595
that do not supply get_parent_map.
598
for rev, parents in self.get_parents(revisions):
599
if parents is not None:
600
result[rev] = parents
146
return (left.difference(right).difference(common),
147
right.difference(left).difference(common))
603
149
def _make_breadth_first_searcher(self, revisions):
604
150
return _BreadthFirstSearcher(revisions, self)
620
166
if None in revisions:
621
167
raise errors.InvalidRevisionId(None, self)
168
common_searcher = self._make_breadth_first_searcher([])
622
169
common_ancestors = set()
623
170
searchers = [self._make_breadth_first_searcher([r])
624
171
for r in revisions]
625
172
active_searchers = searchers[:]
626
173
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)
629
195
newly_seen = set()
630
for searcher in searchers:
631
new_ancestors = searcher.step()
633
newly_seen.update(new_ancestors)
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
635
205
for revision in newly_seen:
636
206
if revision in common_ancestors:
637
# Not a border ancestor because it was seen as common
639
new_common.add(revision)
207
for searcher in searchers:
208
update_common(searcher, revision)
641
210
for searcher in searchers:
642
211
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.
647
214
border_ancestors.add(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
215
for searcher in searchers:
216
update_common(searcher, revision)
680
218
def heads(self, keys):
681
219
"""Return the heads from amongst keys.
730
249
# a descendant of another candidate.
733
ancestors.update(searcher.next())
252
ancestors = searcher.next()
734
253
except StopIteration:
735
254
del active_searchers[candidate]
737
# process found nodes
739
for ancestor in ancestors:
740
if ancestor in candidate_heads:
741
candidate_heads.remove(ancestor)
742
del searchers[ancestor]
743
if ancestor in active_searchers:
744
del active_searchers[ancestor]
745
# it may meet up with a known common node
746
if ancestor in common_walker.seen:
747
# some searcher has encountered our known common nodes:
749
ancestor_set = set([ancestor])
750
for searcher in searchers.itervalues():
751
searcher.stop_searching_any(ancestor_set)
753
# or it may have been just reached by all the searchers:
256
for ancestor in ancestors:
257
if ancestor in candidate_heads:
258
candidate_heads.remove(ancestor)
259
del searchers[ancestor]
260
if ancestor in active_searchers:
261
del active_searchers[ancestor]
754
262
for searcher in searchers.itervalues():
755
263
if ancestor not in searcher.seen:
758
# The final active searcher has just reached this node,
759
# making it be known as a descendant of all candidates,
760
# so we can stop searching it, and any seen ancestors
761
new_common.add(ancestor)
266
# if this revision was seen by all searchers, then it
267
# is a descendant of all candidates, so we can stop
268
# searching it, and any seen ancestors
762
269
for searcher in searchers.itervalues():
763
270
seen_ancestors =\
764
searcher.find_seen_ancestors([ancestor])
271
searcher.find_seen_ancestors(ancestor)
765
272
searcher.stop_searching_any(seen_ancestors)
766
common_walker.start_searching(new_common)
767
273
return candidate_heads
769
def find_merge_order(self, tip_revision_id, lca_revision_ids):
770
"""Find the order that each revision was merged into tip.
772
This basically just walks backwards with a stack, and walks left-first
773
until it finds a node to stop.
775
if len(lca_revision_ids) == 1:
776
return list(lca_revision_ids)
777
looking_for = set(lca_revision_ids)
778
# TODO: Is there a way we could do this "faster" by batching up the
779
# get_parent_map requests?
780
# TODO: Should we also be culling the ancestry search right away? We
781
# could add looking_for to the "stop" list, and walk their
782
# ancestry in batched mode. The flip side is it might mean we walk a
783
# lot of "stop" nodes, rather than only the minimum.
784
# Then again, without it we may trace back into ancestry we could have
786
stack = [tip_revision_id]
789
while stack and looking_for:
792
if next in looking_for:
794
looking_for.remove(next)
795
if len(looking_for) == 1:
796
found.append(looking_for.pop())
799
parent_ids = self.get_parent_map([next]).get(next, None)
800
if not parent_ids: # Ghost, nothing to search here
802
for parent_id in reversed(parent_ids):
803
# TODO: (performance) We see the parent at this point, but we
804
# wait to mark it until later to make sure we get left
805
# parents before right parents. However, instead of
806
# waiting until we have traversed enough parents, we
807
# could instead note that we've found it, and once all
808
# parents are in the stack, just reverse iterate the
810
if parent_id not in stop:
811
# this will need to be searched
812
stack.append(parent_id)
816
def find_unique_lca(self, left_revision, right_revision,
275
def find_unique_lca(self, left_revision, right_revision):
818
276
"""Find a unique LCA.
820
278
Find lowest common ancestors. If there is no unique common
877
300
An ancestor may sort after a descendant if the relationship is not
878
301
visible in the supplied list of revisions.
880
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
303
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
881
304
return sorter.iter_topo_order()
883
306
def is_ancestor(self, candidate_ancestor, candidate_descendant):
884
307
"""Determine whether a revision is an ancestor of another.
886
We answer this using heads() as heads() has the logic to perform the
887
smallest number of parent lookups to determine the ancestral
888
relationship between N revisions.
890
return set([candidate_descendant]) == self.heads(
891
[candidate_ancestor, candidate_descendant])
893
def _search_for_extra_common(self, common, searchers):
894
"""Make sure that unique nodes are genuinely unique.
896
After _find_border_ancestors, all nodes marked "common" are indeed
897
common. Some of the nodes considered unique are not, due to history
898
shortcuts stopping the searches early.
900
We know that we have searched enough when all common search tips are
901
descended from all unique (uncommon) nodes because we know that a node
902
cannot be an ancestor of its own ancestor.
904
:param common: A set of common nodes
905
:param searchers: The searchers returned from _find_border_ancestors
909
# A) The passed in searchers should all be on the same tips, thus
910
# they should be considered the "common" searchers.
911
# B) We find the difference between the searchers, these are the
912
# "unique" nodes for each side.
913
# C) We do a quick culling so that we only start searching from the
914
# more interesting unique nodes. (A unique ancestor is more
915
# interesting than any of its children.)
916
# D) We start searching for ancestors common to all unique nodes.
917
# E) We have the common searchers stop searching any ancestors of
919
# F) When there are no more common search tips, we stop
921
# TODO: We need a way to remove unique_searchers when they overlap with
922
# other unique searchers.
923
if len(searchers) != 2:
924
raise NotImplementedError(
925
"Algorithm not yet implemented for > 2 searchers")
926
common_searchers = searchers
927
left_searcher = searchers[0]
928
right_searcher = searchers[1]
929
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
930
if not unique: # No unique nodes, nothing to do
932
total_unique = len(unique)
933
unique = self._remove_simple_descendants(unique,
934
self.get_parent_map(unique))
935
simple_unique = len(unique)
937
unique_searchers = []
938
for revision_id in unique:
939
if revision_id in left_searcher.seen:
940
parent_searcher = left_searcher
942
parent_searcher = right_searcher
943
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
944
if not revs_to_search: # XXX: This shouldn't be possible
945
revs_to_search = [revision_id]
946
searcher = self._make_breadth_first_searcher(revs_to_search)
947
# We don't care about the starting nodes.
949
unique_searchers.append(searcher)
951
# possible todo: aggregate the common searchers into a single common
952
# searcher, just make sure that we include the nodes into the .seen
953
# properties of the original searchers
955
ancestor_all_unique = None
956
for searcher in unique_searchers:
957
if ancestor_all_unique is None:
958
ancestor_all_unique = set(searcher.seen)
960
ancestor_all_unique = ancestor_all_unique.intersection(
963
trace.mutter('Started %s unique searchers for %s unique revisions',
964
simple_unique, total_unique)
966
while True: # If we have no more nodes we have nothing to do
967
newly_seen_common = set()
968
for searcher in common_searchers:
969
newly_seen_common.update(searcher.step())
970
newly_seen_unique = set()
971
for searcher in unique_searchers:
972
newly_seen_unique.update(searcher.step())
973
new_common_unique = set()
974
for revision in newly_seen_unique:
975
for searcher in unique_searchers:
976
if revision not in searcher.seen:
979
# This is a border because it is a first common that we see
980
# after walking for a while.
981
new_common_unique.add(revision)
982
if newly_seen_common:
983
# These are nodes descended from one of the 'common' searchers.
984
# Make sure all searchers are on the same page
985
for searcher in common_searchers:
986
newly_seen_common.update(
987
searcher.find_seen_ancestors(newly_seen_common))
988
# We start searching the whole ancestry. It is a bit wasteful,
989
# though. We really just want to mark all of these nodes as
990
# 'seen' and then start just the tips. However, it requires a
991
# get_parent_map() call to figure out the tips anyway, and all
992
# redundant requests should be fairly fast.
993
for searcher in common_searchers:
994
searcher.start_searching(newly_seen_common)
996
# If a 'common' node is an ancestor of all unique searchers, we
997
# can stop searching it.
998
stop_searching_common = ancestor_all_unique.intersection(
1000
if stop_searching_common:
1001
for searcher in common_searchers:
1002
searcher.stop_searching_any(stop_searching_common)
1003
if new_common_unique:
1004
# We found some ancestors that are common
1005
for searcher in unique_searchers:
1006
new_common_unique.update(
1007
searcher.find_seen_ancestors(new_common_unique))
1008
# Since these are common, we can grab another set of ancestors
1010
for searcher in common_searchers:
1011
new_common_unique.update(
1012
searcher.find_seen_ancestors(new_common_unique))
1014
# We can tell all of the unique searchers to start at these
1015
# nodes, and tell all of the common searchers to *stop*
1016
# searching these nodes
1017
for searcher in unique_searchers:
1018
searcher.start_searching(new_common_unique)
1019
for searcher in common_searchers:
1020
searcher.stop_searching_any(new_common_unique)
1021
ancestor_all_unique.update(new_common_unique)
1023
# Filter out searchers that don't actually search different
1024
# nodes. We already have the ancestry intersection for them
1025
next_unique_searchers = []
1026
unique_search_sets = set()
1027
for searcher in unique_searchers:
1028
will_search_set = frozenset(searcher._next_query)
1029
if will_search_set not in unique_search_sets:
1030
# This searcher is searching a unique set of nodes, let it
1031
unique_search_sets.add(will_search_set)
1032
next_unique_searchers.append(searcher)
1033
unique_searchers = next_unique_searchers
1034
for searcher in common_searchers:
1035
if searcher._next_query:
1038
# All common searcher have stopped searching
1041
def _remove_simple_descendants(self, revisions, parent_map):
1042
"""remove revisions which are children of other ones in the set
1044
This doesn't do any graph searching, it just checks the immediate
1045
parent_map to find if there are any children which can be removed.
1047
:param revisions: A set of revision_ids
1048
:return: A set of revision_ids with the children removed
1050
simple_ancestors = revisions.copy()
1051
# TODO: jam 20071214 we *could* restrict it to searching only the
1052
# parent_map of revisions already present in 'revisions', but
1053
# considering the general use case, I think this is actually
1056
# This is the same as the following loop. I don't know that it is any
1058
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1059
## if p_ids is not None and revisions.intersection(p_ids))
1060
## return simple_ancestors
1062
# Yet Another Way, invert the parent map (which can be cached)
1064
## for revision_id, parent_ids in parent_map.iteritems():
1065
## for p_id in parent_ids:
1066
## descendants.setdefault(p_id, []).append(revision_id)
1067
## for revision in revisions.intersection(descendants):
1068
## simple_ancestors.difference_update(descendants[revision])
1069
## return simple_ancestors
1070
for revision, parent_ids in parent_map.iteritems():
1071
if parent_ids is None:
1073
for parent_id in parent_ids:
1074
if parent_id in revisions:
1075
# This node has a parent present in the set, so we can
1077
simple_ancestors.discard(revision)
1079
return simple_ancestors
309
There are two possible outcomes: True and False, but there are three
310
possible relationships:
312
a) candidate_ancestor is an ancestor of candidate_descendant
313
b) candidate_ancestor is an descendant of candidate_descendant
314
c) candidate_ancestor is an sibling of candidate_descendant
316
To check for a, we walk from candidate_descendant, looking for
319
To check for b, we walk from candidate_ancestor, looking for
320
candidate_descendant.
322
To make a and b more efficient, we can stop any searches that hit
325
If we exhaust our searches, but neither a or b is true, then c is true.
327
In order to find c efficiently, we must avoid searching from
328
candidate_descendant or candidate_ancestor into common ancestors. But
329
if we don't search common ancestors at all, we won't know if we hit
330
common ancestors. So we have a walker for common ancestors. Note that
331
its searches are not required to terminate in order to determine c to
334
ancestor_walker = self._make_breadth_first_searcher(
335
[candidate_ancestor])
336
descendant_walker = self._make_breadth_first_searcher(
337
[candidate_descendant])
338
common_walker = self._make_breadth_first_searcher([])
339
active_ancestor = True
340
active_descendant = True
341
while (active_ancestor or active_descendant):
343
if active_descendant:
345
nodes = descendant_walker.next()
346
except StopIteration:
347
active_descendant = False
349
if candidate_ancestor in nodes:
351
new_common.update(nodes.intersection(ancestor_walker.seen))
354
nodes = ancestor_walker.next()
355
except StopIteration:
356
active_ancestor = False
358
if candidate_descendant in nodes:
360
new_common.update(nodes.intersection(
361
descendant_walker.seen))
363
new_common.update(common_walker.next())
364
except StopIteration:
366
for walker in (ancestor_walker, descendant_walker):
367
for node in new_common:
368
c_ancestors = walker.find_seen_ancestors(node)
369
walker.stop_searching_any(c_ancestors)
370
common_walker.start_searching(new_common)
1082
374
class HeadsCache(object):
1148
410
def __init__(self, revisions, parents_provider):
1149
self._iterations = 0
1150
self._next_query = set(revisions)
1152
self._started_keys = set(self._next_query)
1153
self._stopped_keys = set()
1154
self._parents_provider = parents_provider
1155
self._returning = 'next_with_ghosts'
1156
self._current_present = set()
1157
self._current_ghosts = set()
1158
self._current_parents = {}
411
self._start = set(revisions)
412
self._search_revisions = None
413
self.seen = set(revisions)
414
self._parents_provider = parents_provider
1160
416
def __repr__(self):
1161
if self._iterations:
1162
prefix = "searching"
1165
search = '%s=%r' % (prefix, list(self._next_query))
1166
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1167
' seen=%r)' % (self._iterations, search, list(self.seen)))
1169
def get_result(self):
1170
"""Get a SearchResult for the current state of this searcher.
1172
:return: A SearchResult for this search so far. The SearchResult is
1173
static - the search can be advanced and the search result will not
1174
be invalidated or altered.
1176
if self._returning == 'next':
1177
# We have to know the current nodes children to be able to list the
1178
# exclude keys for them. However, while we could have a second
1179
# look-ahead result buffer and shuffle things around, this method
1180
# is typically only called once per search - when memoising the
1181
# results of the search.
1182
found, ghosts, next, parents = self._do_query(self._next_query)
1183
# pretend we didn't query: perhaps we should tweak _do_query to be
1184
# entirely stateless?
1185
self.seen.difference_update(next)
1186
next_query = next.union(ghosts)
1188
next_query = self._next_query
1189
excludes = self._stopped_keys.union(next_query)
1190
included_keys = self.seen.difference(excludes)
1191
return SearchResult(self._started_keys, excludes, len(included_keys),
1197
except StopIteration:
417
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
418
' self.seen=%r)' % (self._search_revisions, self.seen))
1201
421
"""Return the next ancestors of this revision.
1203
423
Ancestors are returned in the order they are seen in a breadth-first
1204
traversal. No ancestor will be returned more than once. Ancestors are
1205
returned before their parentage is queried, so ghosts and missing
1206
revisions (including the start revisions) are included in the result.
1207
This can save a round trip in LCA style calculation by allowing
1208
convergence to be detected without reading the data for the revision
1209
the convergence occurs on.
1211
:return: A set of revision_ids.
424
traversal. No ancestor will be returned more than once.
1213
if self._returning != 'next':
1214
# switch to returning the query, not the results.
1215
self._returning = 'next'
1216
self._iterations += 1
426
if self._search_revisions is None:
427
self._search_revisions = self._start
1219
if len(self._next_query) == 0:
1220
raise StopIteration()
1221
# We have seen what we're querying at this point as we are returning
1222
# the query, not the results.
1223
self.seen.update(self._next_query)
1224
return self._next_query
1226
def next_with_ghosts(self):
1227
"""Return the next found ancestors, with ghosts split out.
1229
Ancestors are returned in the order they are seen in a breadth-first
1230
traversal. No ancestor will be returned more than once. Ancestors are
1231
returned only after asking for their parents, which allows us to detect
1232
which revisions are ghosts and which are not.
1234
:return: A tuple with (present ancestors, ghost ancestors) sets.
1236
if self._returning != 'next_with_ghosts':
1237
# switch to returning the results, not the current query.
1238
self._returning = 'next_with_ghosts'
1240
if len(self._next_query) == 0:
1241
raise StopIteration()
1243
return self._current_present, self._current_ghosts
1246
"""Advance the search.
1248
Updates self.seen, self._next_query, self._current_present,
1249
self._current_ghosts, self._current_parents and self._iterations.
1251
self._iterations += 1
1252
found, ghosts, next, parents = self._do_query(self._next_query)
1253
self._current_present = found
1254
self._current_ghosts = ghosts
1255
self._next_query = next
1256
self._current_parents = parents
1257
# ghosts are implicit stop points, otherwise the search cannot be
1258
# repeated when ghosts are filled.
1259
self._stopped_keys.update(ghosts)
1261
def _do_query(self, revisions):
1262
"""Query for revisions.
1264
Adds revisions to the seen set.
1266
:param revisions: Revisions to query.
1267
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1268
set(parents_of_found_revisions), dict(found_revisions:parents)).
1270
found_revisions = set()
1271
parents_of_found = set()
1272
# revisions may contain nodes that point to other nodes in revisions:
1273
# we want to filter them out.
1274
self.seen.update(revisions)
1275
parent_map = self._parents_provider.get_parent_map(revisions)
1276
found_revisions.update(parent_map)
1277
for rev_id, parents in parent_map.iteritems():
1280
new_found_parents = [p for p in parents if p not in self.seen]
1281
if new_found_parents:
1282
# Calling set.update() with an empty generator is actually
1284
parents_of_found.update(new_found_parents)
1285
ghost_revisions = revisions - found_revisions
1286
return found_revisions, ghost_revisions, parents_of_found, parent_map
429
new_search_revisions = set()
430
for parents in self._parents_provider.get_parents(
431
self._search_revisions):
434
new_search_revisions.update(p for p in parents if
436
self._search_revisions = new_search_revisions
437
if len(self._search_revisions) == 0:
438
raise StopIteration()
439
self.seen.update(self._search_revisions)
440
return self._search_revisions
1288
442
def __iter__(self):
1291
def find_seen_ancestors(self, revisions):
1292
"""Find ancestors of these revisions that have already been seen.
1294
This function generally makes the assumption that querying for the
1295
parents of a node that has already been queried is reasonably cheap.
1296
(eg, not a round trip to a remote host).
1298
# TODO: Often we might ask one searcher for its seen ancestors, and
1299
# then ask another searcher the same question. This can result in
1300
# searching the same revisions repeatedly if the two searchers
1301
# have a lot of overlap.
1302
all_seen = self.seen
1303
pending = set(revisions).intersection(all_seen)
1304
seen_ancestors = set(pending)
1306
if self._returning == 'next':
1307
# self.seen contains what nodes have been returned, not what nodes
1308
# have been queried. We don't want to probe for nodes that haven't
1309
# been searched yet.
1310
not_searched_yet = self._next_query
1312
not_searched_yet = ()
1313
pending.difference_update(not_searched_yet)
1314
get_parent_map = self._parents_provider.get_parent_map
1316
parent_map = get_parent_map(pending)
1318
# We don't care if it is a ghost, since it can't be seen if it is
1320
for parent_ids in parent_map.itervalues():
1321
all_parents.extend(parent_ids)
1322
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1323
seen_ancestors.update(next_pending)
1324
next_pending.difference_update(not_searched_yet)
1325
pending = next_pending
445
def find_seen_ancestors(self, revision):
446
"""Find ancestors of this revision that have already been seen."""
447
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
448
seen_ancestors = set()
449
for ancestors in searcher:
450
for ancestor in ancestors:
451
if ancestor not in self.seen:
452
searcher.stop_searching_any([ancestor])
454
seen_ancestors.add(ancestor)
1327
455
return seen_ancestors
1329
457
def stop_searching_any(self, revisions):
1333
461
None of the specified revisions are required to be present in the
1334
462
search list. In this case, the call is a no-op.
1336
# TODO: does this help performance?
1339
revisions = frozenset(revisions)
1340
if self._returning == 'next':
1341
stopped = self._next_query.intersection(revisions)
1342
self._next_query = self._next_query.difference(revisions)
1344
stopped_present = self._current_present.intersection(revisions)
1345
stopped = stopped_present.union(
1346
self._current_ghosts.intersection(revisions))
1347
self._current_present.difference_update(stopped)
1348
self._current_ghosts.difference_update(stopped)
1349
# stopping 'x' should stop returning parents of 'x', but
1350
# not if 'y' always references those same parents
1351
stop_rev_references = {}
1352
for rev in stopped_present:
1353
for parent_id in self._current_parents[rev]:
1354
if parent_id not in stop_rev_references:
1355
stop_rev_references[parent_id] = 0
1356
stop_rev_references[parent_id] += 1
1357
# if only the stopped revisions reference it, the ref count will be
1359
for parents in self._current_parents.itervalues():
1360
for parent_id in parents:
1362
stop_rev_references[parent_id] -= 1
1365
stop_parents = set()
1366
for rev_id, refs in stop_rev_references.iteritems():
1368
stop_parents.add(rev_id)
1369
self._next_query.difference_update(stop_parents)
1370
self._stopped_keys.update(stopped)
464
stopped = self._search_revisions.intersection(revisions)
465
self._search_revisions = self._search_revisions.difference(revisions)
1373
468
def start_searching(self, revisions):
1374
"""Add revisions to the search.
1376
The parents of revisions will be returned from the next call to next()
1377
or next_with_ghosts(). If next_with_ghosts was the most recently used
1378
next* call then the return value is the result of looking up the
1379
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1381
revisions = frozenset(revisions)
1382
self._started_keys.update(revisions)
1383
new_revisions = revisions.difference(self.seen)
1384
if self._returning == 'next':
1385
self._next_query.update(new_revisions)
1386
self.seen.update(new_revisions)
469
if self._search_revisions is None:
470
self._start = set(revisions)
1388
# perform a query on revisions
1389
revs, ghosts, query, parents = self._do_query(revisions)
1390
self._stopped_keys.update(ghosts)
1391
self._current_present.update(revs)
1392
self._current_ghosts.update(ghosts)
1393
self._next_query.update(query)
1394
self._current_parents.update(parents)
1398
class SearchResult(object):
1399
"""The result of a breadth first search.
1401
A SearchResult provides the ability to reconstruct the search or access a
1402
set of the keys the search found.
1405
def __init__(self, start_keys, exclude_keys, key_count, keys):
1406
"""Create a SearchResult.
1408
:param start_keys: The keys the search started at.
1409
:param exclude_keys: The keys the search excludes.
1410
:param key_count: The total number of keys (from start to but not
1412
:param keys: The keys the search found. Note that in future we may get
1413
a SearchResult from a smart server, in which case the keys list is
1414
not necessarily immediately available.
1416
self._recipe = (start_keys, exclude_keys, key_count)
1417
self._keys = frozenset(keys)
1419
def get_recipe(self):
1420
"""Return a recipe that can be used to replay this search.
1422
The recipe allows reconstruction of the same results at a later date
1423
without knowing all the found keys. The essential elements are a list
1424
of keys to start and and to stop at. In order to give reproducible
1425
results when ghosts are encountered by a search they are automatically
1426
added to the exclude list (or else ghost filling may alter the
1429
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1430
recreate the results of this search, create a breadth first
1431
searcher on the same graph starting at start_keys. Then call next()
1432
(or next_with_ghosts()) repeatedly, and on every result, call
1433
stop_searching_any on any keys from the exclude_keys set. The
1434
revision_count value acts as a trivial cross-check - the found
1435
revisions of the new search should have as many elements as
1436
revision_count. If it does not, then additional revisions have been
1437
ghosted since the search was executed the first time and the second
1443
"""Return the keys found in this search.
1445
:return: A set of keys.
1450
def collapse_linear_regions(parent_map):
1451
"""Collapse regions of the graph that are 'linear'.
1457
can be collapsed by removing B and getting::
1461
:param parent_map: A dictionary mapping children to their parents
1462
:return: Another dictionary with 'linear' chains collapsed
1464
# Note: this isn't a strictly minimal collapse. For example:
1472
# Will not have 'D' removed, even though 'E' could fit. Also:
1478
# A and C are both kept because they are edges of the graph. We *could* get
1479
# rid of A if we wanted.
1487
# Will not have any nodes removed, even though you do have an
1488
# 'uninteresting' linear D->B and E->C
1490
for child, parents in parent_map.iteritems():
1491
children.setdefault(child, [])
1493
children.setdefault(p, []).append(child)
1495
orig_children = dict(children)
1497
result = dict(parent_map)
1498
for node in parent_map:
1499
parents = result[node]
1500
if len(parents) == 1:
1501
parent_children = children[parents[0]]
1502
if len(parent_children) != 1:
1503
# This is not the only child
1505
node_children = children[node]
1506
if len(node_children) != 1:
1508
child_parents = result.get(node_children[0], None)
1509
if len(child_parents) != 1:
1510
# This is not its only parent
1512
# The child of this node only points at it, and the parent only has
1513
# this as a child. remove this node, and join the others together
1514
result[node_children[0]] = parents
1515
children[parents[0]] = node_children
472
self._search_revisions.update(revisions.difference(self.seen))
473
self.seen.update(revisions)
added
removed
bzrlib/graph.py
