« back to all changes in this revision
Viewing changes to bzrlib/graph.py
- browse files at revision 3407
- compare with another revision
- compare with revision 1711.2.122
- download diff
- download tarball
- view history from revision 3407
- Committer: Canonical.com Patch Queue Manager
- Date: 2008-05-05 23:15:58 UTC
- mfrom: (3377.3.45 submitted)
- Revision ID: pqm@pqm.ubuntu.com-20080505231558-7w3zaehbvtcjk7jv
(jam) Make Graph.find_differences() correct,
and create a Graph.find_unique_ancestors function.
and create a Graph.find_unique_ancestors function.
added
removed
bzrlib/graph.py
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
16
17
17
from bzrlib import (
18
debug,
18
19
errors,
19
20
revision,
20
21
symbol_versioning,
22
trace,
21
23
tsort,
22
24
)
23
25
from bzrlib.deprecated_graph import (node_distances, select_farthest)
199
201
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))
210
211
def find_unique_ancestors(self, unique_revision, common_revisions):
212
"""Find the unique ancestors for a revision versus others.
213
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.
217
218
:param unique_revision: The revision_id whose ancestry we are
219
interested in.
220
XXX: Would this API be better if we allowed multiple revisions on
221
to be searched here?
222
:param common_revisions: Revision_ids of ancestries to exclude.
223
:return: A set of revisions in the ancestry of unique_revision
224
"""
225
if unique_revision in common_revisions:
226
return set()
227
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.
240
241
if 'graph' in debug.debug_flags:
242
_mutter = trace.mutter
243
else:
244
def _mutter(*args, **kwargs):
245
pass
246
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)
251
252
while unique_searcher._next_query:
253
next_unique_nodes = set(unique_searcher.step())
254
next_common_nodes = set(common_searcher.step())
255
256
# Check if either searcher encounters new nodes seen by the other
257
# side.
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)
268
269
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
270
if not unique_nodes:
271
return unique_nodes
272
unique_tips = self._remove_simple_descendants(unique_nodes,
273
self.get_parent_map(unique_nodes))
274
275
if len(unique_tips) == 1:
276
unique_searchers = []
277
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
278
else:
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
285
searcher.step()
286
unique_searchers.append(searcher)
287
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)
292
else:
293
ancestor_all_unique = ancestor_all_unique.intersection(
294
searcher.seen)
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()
299
300
# Stop any search tips that are already known as ancestors of the
301
# unique nodes
302
common_searcher.stop_searching_any(
303
common_searcher.find_seen_ancestors(ancestor_all_unique))
304
305
total_stopped = 0
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
314
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(
325
searcher.seen)
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
342
# that we have seen
343
unique_are_common_nodes.update(
344
common_searcher.find_seen_ancestors(unique_are_common_nodes))
345
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)
350
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',
361
searcher._label,
362
searcher._iterations,
363
len(stopped))
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)
368
else:
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'
374
' at %s iterations',
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)
206
379
207
380
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
381
def get_parents(self, revisions):
220
393
Deprecated in bzr 1.2 - please see get_parent_map.
221
394
"""
222
395
parents = self.get_parent_map(revisions)
223
return [parent.get(r, None) for r in revisions]
396
return [parents.get(r, None) for r in revisions]
224
397
225
398
def get_parent_map(self, revisions):
226
399
"""Get a map of key:parent_list for revisions.
253
426
"""
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(
264
revision)
265
stopped = searcher.stop_searching_any(w_seen_ancestors)
266
common_ancestors.update(w_seen_ancestors)
267
common_searcher.start_searching(stopped)
268
434
269
435
while True:
270
if len(active_searchers) == 0:
271
return border_ancestors, common_ancestors, [s.seen for s in
272
searchers]
273
try:
274
new_common = common_searcher.next()
275
common_ancestors.update(new_common)
276
except StopIteration:
277
pass
278
else:
279
for searcher in active_searchers:
280
for revision in new_common.intersection(searcher.seen):
281
update_common(searcher, revision)
282
283
436
newly_seen = set()
284
new_active_searchers = []
285
for searcher in active_searchers:
286
try:
287
newly_seen.update(searcher.next())
288
except StopIteration:
289
pass
290
else:
291
new_active_searchers.append(searcher)
292
active_searchers = new_active_searchers
437
for searcher in searchers:
438
new_ancestors = searcher.step()
439
if new_ancestors:
440
newly_seen.update(new_ancestors)
441
new_common = set()
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
445
# already
446
new_common.add(revision)
297
447
continue
298
448
for searcher in searchers:
299
449
if revision not in searcher.seen:
300
450
break
301
451
else:
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)
456
if new_common:
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)
462
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)
473
474
if len(unique_search_sets) == 1:
475
nodes = unique_search_sets.pop()
476
uncommon_nodes = nodes.difference(common_ancestors)
477
assert not uncommon_nodes, ("Somehow we ended up converging"
478
" without actually marking them as"
479
" in common."
480
"\nStart_nodes: %s"
481
"\nuncommon_nodes: %s"
482
% (revisions, uncommon_nodes))
483
break
484
return border_ancestors, common_ancestors, searchers
305
485
306
486
def heads(self, keys):
307
487
"""Return the heads from amongst keys.
387
567
new_common.add(ancestor)
388
568
for searcher in searchers.itervalues():
389
569
seen_ancestors =\
390
searcher.find_seen_ancestors(ancestor)
570
searcher.find_seen_ancestors([ancestor])
391
571
searcher.stop_searching_any(seen_ancestors)
392
572
common_walker.start_searching(new_common)
393
573
return candidate_heads
469
649
return set([candidate_descendant]) == self.heads(
470
650
[candidate_ancestor, candidate_descendant])
471
651
652
def _search_for_extra_common(self, common, searchers):
653
"""Make sure that unique nodes are genuinely unique.
654
655
After _find_border_ancestors, all nodes marked "common" are indeed
656
common. Some of the nodes considered unique are not, due to history
657
shortcuts stopping the searches early.
658
659
We know that we have searched enough when all common search tips are
660
descended from all unique (uncommon) nodes because we know that a node
661
cannot be an ancestor of its own ancestor.
662
663
:param common: A set of common nodes
664
:param searchers: The searchers returned from _find_border_ancestors
665
:return: None
666
"""
667
# Basic algorithm...
668
# A) The passed in searchers should all be on the same tips, thus
669
# they should be considered the "common" searchers.
670
# B) We find the difference between the searchers, these are the
671
# "unique" nodes for each side.
672
# C) We do a quick culling so that we only start searching from the
673
# more interesting unique nodes. (A unique ancestor is more
674
# interesting than any of its children.)
675
# D) We start searching for ancestors common to all unique nodes.
676
# E) We have the common searchers stop searching any ancestors of
677
# nodes found by (D)
678
# F) When there are no more common search tips, we stop
679
680
# TODO: We need a way to remove unique_searchers when they overlap with
681
# other unique searchers.
682
assert len(searchers) == 2, (
683
"Algorithm not yet implemented for > 2 searchers")
684
common_searchers = searchers
685
left_searcher = searchers[0]
686
right_searcher = searchers[1]
687
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
688
if not unique: # No unique nodes, nothing to do
689
return
690
total_unique = len(unique)
691
unique = self._remove_simple_descendants(unique,
692
self.get_parent_map(unique))
693
simple_unique = len(unique)
694
695
unique_searchers = []
696
for revision_id in unique:
697
if revision_id in left_searcher.seen:
698
parent_searcher = left_searcher
699
else:
700
parent_searcher = right_searcher
701
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
702
if not revs_to_search: # XXX: This shouldn't be possible
703
revs_to_search = [revision_id]
704
searcher = self._make_breadth_first_searcher(revs_to_search)
705
# We don't care about the starting nodes.
706
searcher.step()
707
unique_searchers.append(searcher)
708
709
# possible todo: aggregate the common searchers into a single common
710
# searcher, just make sure that we include the nodes into the .seen
711
# properties of the original searchers
712
713
ancestor_all_unique = None
714
for searcher in unique_searchers:
715
if ancestor_all_unique is None:
716
ancestor_all_unique = set(searcher.seen)
717
else:
718
ancestor_all_unique = ancestor_all_unique.intersection(
719
searcher.seen)
720
721
trace.mutter('Started %s unique searchers for %s unique revisions',
722
simple_unique, total_unique)
723
724
while True: # If we have no more nodes we have nothing to do
725
newly_seen_common = set()
726
for searcher in common_searchers:
727
newly_seen_common.update(searcher.step())
728
newly_seen_unique = set()
729
for searcher in unique_searchers:
730
newly_seen_unique.update(searcher.step())
731
new_common_unique = set()
732
for revision in newly_seen_unique:
733
for searcher in unique_searchers:
734
if revision not in searcher.seen:
735
break
736
else:
737
# This is a border because it is a first common that we see
738
# after walking for a while.
739
new_common_unique.add(revision)
740
if newly_seen_common:
741
# These are nodes descended from one of the 'common' searchers.
742
# Make sure all searchers are on the same page
743
for searcher in common_searchers:
744
newly_seen_common.update(
745
searcher.find_seen_ancestors(newly_seen_common))
746
# We start searching the whole ancestry. It is a bit wasteful,
747
# though. We really just want to mark all of these nodes as
748
# 'seen' and then start just the tips. However, it requires a
749
# get_parent_map() call to figure out the tips anyway, and all
750
# redundant requests should be fairly fast.
751
for searcher in common_searchers:
752
searcher.start_searching(newly_seen_common)
753
754
# If a 'common' node is an ancestor of all unique searchers, we
755
# can stop searching it.
756
stop_searching_common = ancestor_all_unique.intersection(
757
newly_seen_common)
758
if stop_searching_common:
759
for searcher in common_searchers:
760
searcher.stop_searching_any(stop_searching_common)
761
if new_common_unique:
762
# We found some ancestors that are common
763
for searcher in unique_searchers:
764
new_common_unique.update(
765
searcher.find_seen_ancestors(new_common_unique))
766
# Since these are common, we can grab another set of ancestors
767
# that we have seen
768
for searcher in common_searchers:
769
new_common_unique.update(
770
searcher.find_seen_ancestors(new_common_unique))
771
772
# We can tell all of the unique searchers to start at these
773
# nodes, and tell all of the common searchers to *stop*
774
# searching these nodes
775
for searcher in unique_searchers:
776
searcher.start_searching(new_common_unique)
777
for searcher in common_searchers:
778
searcher.stop_searching_any(new_common_unique)
779
ancestor_all_unique.update(new_common_unique)
780
781
# Filter out searchers that don't actually search different
782
# nodes. We already have the ancestry intersection for them
783
next_unique_searchers = []
784
unique_search_sets = set()
785
for searcher in unique_searchers:
786
will_search_set = frozenset(searcher._next_query)
787
if will_search_set not in unique_search_sets:
788
# This searcher is searching a unique set of nodes, let it
789
unique_search_sets.add(will_search_set)
790
next_unique_searchers.append(searcher)
791
unique_searchers = next_unique_searchers
792
for searcher in common_searchers:
793
if searcher._next_query:
794
break
795
else:
796
# All common searcher have stopped searching
797
return
798
799
def _remove_simple_descendants(self, revisions, parent_map):
800
"""remove revisions which are children of other ones in the set
801
802
This doesn't do any graph searching, it just checks the immediate
803
parent_map to find if there are any children which can be removed.
804
805
:param revisions: A set of revision_ids
806
:return: A set of revision_ids with the children removed
807
"""
808
simple_ancestors = revisions.copy()
809
# TODO: jam 20071214 we *could* restrict it to searching only the
810
# parent_map of revisions already present in 'revisions', but
811
# considering the general use case, I think this is actually
812
# better.
813
814
# This is the same as the following loop. I don't know that it is any
815
# faster.
816
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
817
## if p_ids is not None and revisions.intersection(p_ids))
818
## return simple_ancestors
819
820
# Yet Another Way, invert the parent map (which can be cached)
821
## descendants = {}
822
## for revision_id, parent_ids in parent_map.iteritems():
823
## for p_id in parent_ids:
824
## descendants.setdefault(p_id, []).append(revision_id)
825
## for revision in revisions.intersection(descendants):
826
## simple_ancestors.difference_update(descendants[revision])
827
## return simple_ancestors
828
for revision, parent_ids in parent_map.iteritems():
829
if parent_ids is None:
830
continue
831
for parent_id in parent_ids:
832
if parent_id in revisions:
833
# This node has a parent present in the set, so we can
834
# remove it
835
simple_ancestors.discard(revision)
836
break
837
return simple_ancestors
838
472
839
473
840
class HeadsCache(object):
474
841
"""A cache of results for graph heads calls."""
582
949
return SearchResult(self._started_keys, excludes, len(included_keys),
583
950
included_keys)
584
951
952
def step(self):
953
try:
954
return self.next()
955
except StopIteration:
956
return ()
957
585
958
def next(self):
586
959
"""Return the next ancestors of this revision.
587
960
652
1025
:return: A tuple: (set(found_revisions), set(ghost_revisions),
653
1026
set(parents_of_found_revisions), dict(found_revisions:parents)).
654
1027
"""
655
found_parents = set()
1028
found_revisions = set()
656
1029
parents_of_found = set()
657
1030
# revisions may contain nodes that point to other nodes in revisions:
658
1031
# we want to filter them out.
659
1032
self.seen.update(revisions)
660
1033
parent_map = self._parents_provider.get_parent_map(revisions)
1034
found_revisions.update(parent_map)
661
1035
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
1036
new_found_parents = [p for p in parents if p not in self.seen]
1037
if new_found_parents:
1038
# Calling set.update() with an empty generator is actually
1039
# rather expensive.
1040
parents_of_found.update(new_found_parents)
1041
ghost_revisions = revisions - found_revisions
1042
return found_revisions, ghost_revisions, parents_of_found, parent_map
666
1043
667
1044
def __iter__(self):
668
1045
return self
669
1046
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])
678
else:
679
seen_ancestors.add(ancestor)
1047
def find_seen_ancestors(self, revisions):
1048
"""Find ancestors of these revisions that have already been seen."""
1049
all_seen = self.seen
1050
pending = set(revisions).intersection(all_seen)
1051
seen_ancestors = set(pending)
1052
1053
if self._returning == 'next':
1054
# self.seen contains what nodes have been returned, not what nodes
1055
# have been queried. We don't want to probe for nodes that haven't
1056
# been searched yet.
1057
not_searched_yet = self._next_query
1058
else:
1059
not_searched_yet = ()
1060
pending.difference_update(not_searched_yet)
1061
get_parent_map = self._parents_provider.get_parent_map
1062
while pending:
1063
parent_map = get_parent_map(pending)
1064
all_parents = []
1065
# We don't care if it is a ghost, since it can't be seen if it is
1066
# a ghost
1067
for parent_ids in parent_map.itervalues():
1068
all_parents.extend(parent_ids)
1069
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1070
seen_ancestors.update(next_pending)
1071
next_pending.difference_update(not_searched_yet)
1072
pending = next_pending
1073
680
1074
return seen_ancestors
681
1075
682
1076
def stop_searching_any(self, revisions):
731
1125
revisions = frozenset(revisions)
732
1126
self._started_keys.update(revisions)
733
1127
new_revisions = revisions.difference(self.seen)
734
revs, ghosts, query, parents = self._do_query(revisions)
735
self._stopped_keys.update(ghosts)
736
1128
if self._returning == 'next':
737
1129
self._next_query.update(new_revisions)
1130
self.seen.update(new_revisions)
738
1131
else:
739
1132
# perform a query on revisions
1133
revs, ghosts, query, parents = self._do_query(revisions)
1134
self._stopped_keys.update(ghosts)
740
1135
self._current_present.update(revs)
741
1136
self._current_ghosts.update(ghosts)
742
1137
self._next_query.update(query)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1