1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27
from bzrlib.deprecated_graph import (node_distances, select_farthest)
29
STEP_UNIQUE_SEARCHER_EVERY = 5
31
# DIAGRAM of terminology
41
# In this diagram, relative to G and H:
42
# A, B, C, D, E are common ancestors.
43
# C, D and E are border ancestors, because each has a non-common descendant.
44
# D and E are least common ancestors because none of their descendants are
46
# C is not a least common ancestor because its descendant, E, is a common
49
# The find_unique_lca algorithm will pick A in two steps:
50
# 1. find_lca('G', 'H') => ['D', 'E']
51
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
54
class DictParentsProvider(object):
55
"""A parents provider for Graph objects."""
57
def __init__(self, ancestry):
58
self.ancestry = ancestry
61
return 'DictParentsProvider(%r)' % self.ancestry
63
def get_parent_map(self, keys):
64
"""See _StackedParentsProvider.get_parent_map"""
65
ancestry = self.ancestry
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
class _StackedParentsProvider(object):
71
def __init__(self, parent_providers):
72
self._parent_providers = parent_providers
75
return "_StackedParentsProvider(%r)" % self._parent_providers
77
def get_parent_map(self, keys):
78
"""Get a mapping of keys => parents
80
A dictionary is returned with an entry for each key present in this
81
source. If this source doesn't have information about a key, it should
84
[NULL_REVISION] is used as the parent of the first user-committed
85
revision. Its parent list is empty.
87
:param keys: An iterable returning keys to check (eg revision_ids)
88
:return: A dictionary mapping each key to its parents
92
for parents_provider in self._parent_providers:
93
new_found = parents_provider.get_parent_map(remaining)
94
found.update(new_found)
95
remaining.difference_update(new_found)
101
class CachingParentsProvider(object):
102
"""A parents provider which will cache the revision => parents in a dict.
104
This is useful for providers that have an expensive lookup.
107
def __init__(self, parent_provider):
108
self._real_provider = parent_provider
109
# Theoretically we could use an LRUCache here
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
115
def get_parent_map(self, keys):
116
"""See _StackedParentsProvider.get_parent_map"""
118
# If the _real_provider doesn't have a key, we cache a value of None,
119
# which we then later use to realize we cannot provide a value for that
126
if value is not None:
127
parent_map[key] = value
132
new_parents = self._real_provider.get_parent_map(needed)
133
cache.update(new_parents)
134
parent_map.update(new_parents)
135
needed.difference_update(new_parents)
136
cache.update(dict.fromkeys(needed, None))
141
"""Provide incremental access to revision graphs.
143
This is the generic implementation; it is intended to be subclassed to
144
specialize it for other repository types.
147
def __init__(self, parents_provider):
148
"""Construct a Graph that uses several graphs as its input
150
This should not normally be invoked directly, because there may be
151
specialized implementations for particular repository types. See
152
Repository.get_graph().
154
:param parents_provider: An object providing a get_parent_map call
155
conforming to the behavior of
156
StackedParentsProvider.get_parent_map.
158
if getattr(parents_provider, 'get_parents', None) is not None:
159
self.get_parents = parents_provider.get_parents
160
if getattr(parents_provider, 'get_parent_map', None) is not None:
161
self.get_parent_map = parents_provider.get_parent_map
162
self._parents_provider = parents_provider
165
return 'Graph(%r)' % self._parents_provider
167
def find_lca(self, *revisions):
168
"""Determine the lowest common ancestors of the provided revisions
170
A lowest common ancestor is a common ancestor none of whose
171
descendants are common ancestors. In graphs, unlike trees, there may
172
be multiple lowest common ancestors.
174
This algorithm has two phases. Phase 1 identifies border ancestors,
175
and phase 2 filters border ancestors to determine lowest common
178
In phase 1, border ancestors are identified, using a breadth-first
179
search starting at the bottom of the graph. Searches are stopped
180
whenever a node or one of its descendants is determined to be common
182
In phase 2, the border ancestors are filtered to find the least
183
common ancestors. This is done by searching the ancestries of each
186
Phase 2 is perfomed on the principle that a border ancestor that is
187
not an ancestor of any other border ancestor is a least common
190
Searches are stopped when they find a node that is determined to be a
191
common ancestor of all border ancestors, because this shows that it
192
cannot be a descendant of any border ancestor.
194
The scaling of this operation should be proportional to
195
1. The number of uncommon ancestors
196
2. The number of border ancestors
197
3. The length of the shortest path between a border ancestor and an
198
ancestor of all border ancestors.
200
border_common, common, sides = self._find_border_ancestors(revisions)
201
# We may have common ancestors that can be reached from each other.
202
# - ask for the heads of them to filter it down to only ones that
203
# cannot be reached from each other - phase 2.
204
return self.heads(border_common)
206
def find_difference(self, left_revision, right_revision):
207
"""Determine the graph difference between two revisions"""
208
border, common, searchers = self._find_border_ancestors(
209
[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
603
def _make_breadth_first_searcher(self, revisions):
604
return _BreadthFirstSearcher(revisions, self)
606
def _find_border_ancestors(self, revisions):
607
"""Find common ancestors with at least one uncommon descendant.
609
Border ancestors are identified using a breadth-first
610
search starting at the bottom of the graph. Searches are stopped
611
whenever a node or one of its descendants is determined to be common.
613
This will scale with the number of uncommon ancestors.
615
As well as the border ancestors, a set of seen common ancestors and a
616
list of sets of seen ancestors for each input revision is returned.
617
This allows calculation of graph difference from the results of this
620
if None in revisions:
621
raise errors.InvalidRevisionId(None, self)
622
common_ancestors = set()
623
searchers = [self._make_breadth_first_searcher([r])
625
active_searchers = searchers[:]
626
border_ancestors = set()
630
for searcher in searchers:
631
new_ancestors = searcher.step()
633
newly_seen.update(new_ancestors)
635
for revision in newly_seen:
636
if revision in common_ancestors:
637
# Not a border ancestor because it was seen as common
639
new_common.add(revision)
641
for searcher in searchers:
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.
647
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
680
def heads(self, keys):
681
"""Return the heads from amongst keys.
683
This is done by searching the ancestries of each key. Any key that is
684
reachable from another key is not returned; all the others are.
686
This operation scales with the relative depth between any two keys. If
687
any two keys are completely disconnected all ancestry of both sides
690
:param keys: An iterable of keys.
691
:return: A set of the heads. Note that as a set there is no ordering
692
information. Callers will need to filter their input to create
693
order if they need it.
695
candidate_heads = set(keys)
696
if revision.NULL_REVISION in candidate_heads:
697
# NULL_REVISION is only a head if it is the only entry
698
candidate_heads.remove(revision.NULL_REVISION)
699
if not candidate_heads:
700
return set([revision.NULL_REVISION])
701
if len(candidate_heads) < 2:
702
return candidate_heads
703
searchers = dict((c, self._make_breadth_first_searcher([c]))
704
for c in candidate_heads)
705
active_searchers = dict(searchers)
706
# skip over the actual candidate for each searcher
707
for searcher in active_searchers.itervalues():
709
# The common walker finds nodes that are common to two or more of the
710
# input keys, so that we don't access all history when a currently
711
# uncommon search point actually meets up with something behind a
712
# common search point. Common search points do not keep searches
713
# active; they just allow us to make searches inactive without
714
# accessing all history.
715
common_walker = self._make_breadth_first_searcher([])
716
while len(active_searchers) > 0:
721
except StopIteration:
722
# No common points being searched at this time.
724
for candidate in active_searchers.keys():
726
searcher = active_searchers[candidate]
728
# rare case: we deleted candidate in a previous iteration
729
# through this for loop, because it was determined to be
730
# a descendant of another candidate.
733
ancestors.update(searcher.next())
734
except StopIteration:
735
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:
754
for searcher in searchers.itervalues():
755
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)
762
for searcher in searchers.itervalues():
764
searcher.find_seen_ancestors([ancestor])
765
searcher.stop_searching_any(seen_ancestors)
766
common_walker.start_searching(new_common)
767
return candidate_heads
769
def find_unique_lca(self, left_revision, right_revision,
771
"""Find a unique LCA.
773
Find lowest common ancestors. If there is no unique common
774
ancestor, find the lowest common ancestors of those ancestors.
776
Iteration stops when a unique lowest common ancestor is found.
777
The graph origin is necessarily a unique lowest common ancestor.
779
Note that None is not an acceptable substitute for NULL_REVISION.
780
in the input for this method.
782
:param count_steps: If True, the return value will be a tuple of
783
(unique_lca, steps) where steps is the number of times that
784
find_lca was run. If False, only unique_lca is returned.
786
revisions = [left_revision, right_revision]
790
lca = self.find_lca(*revisions)
798
raise errors.NoCommonAncestor(left_revision, right_revision)
801
def iter_ancestry(self, revision_ids):
802
"""Iterate the ancestry of this revision.
804
:param revision_ids: Nodes to start the search
805
:return: Yield tuples mapping a revision_id to its parents for the
806
ancestry of revision_id.
807
Ghosts will be returned with None as their parents, and nodes
808
with no parents will have NULL_REVISION as their only parent. (As
809
defined by get_parent_map.)
810
There will also be a node for (NULL_REVISION, ())
812
pending = set(revision_ids)
815
processed.update(pending)
816
next_map = self.get_parent_map(pending)
818
for item in next_map.iteritems():
820
next_pending.update(p for p in item[1] if p not in processed)
821
ghosts = pending.difference(next_map)
824
pending = next_pending
826
def iter_topo_order(self, revisions):
827
"""Iterate through the input revisions in topological order.
829
This sorting only ensures that parents come before their children.
830
An ancestor may sort after a descendant if the relationship is not
831
visible in the supplied list of revisions.
833
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
834
return sorter.iter_topo_order()
836
def is_ancestor(self, candidate_ancestor, candidate_descendant):
837
"""Determine whether a revision is an ancestor of another.
839
We answer this using heads() as heads() has the logic to perform the
840
smallest number of parent lookups to determine the ancestral
841
relationship between N revisions.
843
return set([candidate_descendant]) == self.heads(
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
1035
class HeadsCache(object):
1036
"""A cache of results for graph heads calls."""
1038
def __init__(self, graph):
1042
def heads(self, keys):
1043
"""Return the heads of keys.
1045
This matches the API of Graph.heads(), specifically the return value is
1046
a set which can be mutated, and ordering of the input is not preserved
1049
:see also: Graph.heads.
1050
:param keys: The keys to calculate heads for.
1051
:return: A set containing the heads, which may be mutated without
1052
affecting future lookups.
1054
keys = frozenset(keys)
1056
return set(self._heads[keys])
1058
heads = self.graph.heads(keys)
1059
self._heads[keys] = heads
1063
class FrozenHeadsCache(object):
1064
"""Cache heads() calls, assuming the caller won't modify them."""
1066
def __init__(self, graph):
1070
def heads(self, keys):
1071
"""Return the heads of keys.
1073
Similar to Graph.heads(). The main difference is that the return value
1074
is a frozen set which cannot be mutated.
1076
:see also: Graph.heads.
1077
:param keys: The keys to calculate heads for.
1078
:return: A frozenset containing the heads.
1080
keys = frozenset(keys)
1082
return self._heads[keys]
1084
heads = frozenset(self.graph.heads(keys))
1085
self._heads[keys] = heads
1088
def cache(self, keys, heads):
1089
"""Store a known value."""
1090
self._heads[frozenset(keys)] = frozenset(heads)
1093
class _BreadthFirstSearcher(object):
1094
"""Parallel search breadth-first the ancestry of revisions.
1096
This class implements the iterator protocol, but additionally
1097
1. provides a set of seen ancestors, and
1098
2. allows some ancestries to be unsearched, via stop_searching_any
1101
def __init__(self, revisions, parents_provider):
1102
self._iterations = 0
1103
self._next_query = set(revisions)
1105
self._started_keys = set(self._next_query)
1106
self._stopped_keys = set()
1107
self._parents_provider = parents_provider
1108
self._returning = 'next_with_ghosts'
1109
self._current_present = set()
1110
self._current_ghosts = set()
1111
self._current_parents = {}
1114
if self._iterations:
1115
prefix = "searching"
1118
search = '%s=%r' % (prefix, list(self._next_query))
1119
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1120
' seen=%r)' % (self._iterations, search, list(self.seen)))
1122
def get_result(self):
1123
"""Get a SearchResult for the current state of this searcher.
1125
:return: A SearchResult for this search so far. The SearchResult is
1126
static - the search can be advanced and the search result will not
1127
be invalidated or altered.
1129
if self._returning == 'next':
1130
# We have to know the current nodes children to be able to list the
1131
# exclude keys for them. However, while we could have a second
1132
# look-ahead result buffer and shuffle things around, this method
1133
# is typically only called once per search - when memoising the
1134
# results of the search.
1135
found, ghosts, next, parents = self._do_query(self._next_query)
1136
# pretend we didn't query: perhaps we should tweak _do_query to be
1137
# entirely stateless?
1138
self.seen.difference_update(next)
1139
next_query = next.union(ghosts)
1141
next_query = self._next_query
1142
excludes = self._stopped_keys.union(next_query)
1143
included_keys = self.seen.difference(excludes)
1144
return SearchResult(self._started_keys, excludes, len(included_keys),
1150
except StopIteration:
1154
"""Return the next ancestors of this revision.
1156
Ancestors are returned in the order they are seen in a breadth-first
1157
traversal. No ancestor will be returned more than once. Ancestors are
1158
returned before their parentage is queried, so ghosts and missing
1159
revisions (including the start revisions) are included in the result.
1160
This can save a round trip in LCA style calculation by allowing
1161
convergence to be detected without reading the data for the revision
1162
the convergence occurs on.
1164
:return: A set of revision_ids.
1166
if self._returning != 'next':
1167
# switch to returning the query, not the results.
1168
self._returning = 'next'
1169
self._iterations += 1
1172
if len(self._next_query) == 0:
1173
raise StopIteration()
1174
# We have seen what we're querying at this point as we are returning
1175
# the query, not the results.
1176
self.seen.update(self._next_query)
1177
return self._next_query
1179
def next_with_ghosts(self):
1180
"""Return the next found ancestors, with ghosts split out.
1182
Ancestors are returned in the order they are seen in a breadth-first
1183
traversal. No ancestor will be returned more than once. Ancestors are
1184
returned only after asking for their parents, which allows us to detect
1185
which revisions are ghosts and which are not.
1187
:return: A tuple with (present ancestors, ghost ancestors) sets.
1189
if self._returning != 'next_with_ghosts':
1190
# switch to returning the results, not the current query.
1191
self._returning = 'next_with_ghosts'
1193
if len(self._next_query) == 0:
1194
raise StopIteration()
1196
return self._current_present, self._current_ghosts
1199
"""Advance the search.
1201
Updates self.seen, self._next_query, self._current_present,
1202
self._current_ghosts, self._current_parents and self._iterations.
1204
self._iterations += 1
1205
found, ghosts, next, parents = self._do_query(self._next_query)
1206
self._current_present = found
1207
self._current_ghosts = ghosts
1208
self._next_query = next
1209
self._current_parents = parents
1210
# ghosts are implicit stop points, otherwise the search cannot be
1211
# repeated when ghosts are filled.
1212
self._stopped_keys.update(ghosts)
1214
def _do_query(self, revisions):
1215
"""Query for revisions.
1217
Adds revisions to the seen set.
1219
:param revisions: Revisions to query.
1220
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1221
set(parents_of_found_revisions), dict(found_revisions:parents)).
1223
found_revisions = set()
1224
parents_of_found = set()
1225
# revisions may contain nodes that point to other nodes in revisions:
1226
# we want to filter them out.
1227
self.seen.update(revisions)
1228
parent_map = self._parents_provider.get_parent_map(revisions)
1229
found_revisions.update(parent_map)
1230
for rev_id, parents in parent_map.iteritems():
1231
new_found_parents = [p for p in parents if p not in self.seen]
1232
if new_found_parents:
1233
# Calling set.update() with an empty generator is actually
1235
parents_of_found.update(new_found_parents)
1236
ghost_revisions = revisions - found_revisions
1237
return found_revisions, ghost_revisions, parents_of_found, parent_map
1242
def find_seen_ancestors(self, revisions):
1243
"""Find ancestors of these revisions that have already been seen.
1245
This function generally makes the assumption that querying for the
1246
parents of a node that has already been queried is reasonably cheap.
1247
(eg, not a round trip to a remote host).
1249
# TODO: Often we might ask one searcher for its seen ancestors, and
1250
# then ask another searcher the same question. This can result in
1251
# searching the same revisions repeatedly if the two searchers
1252
# have a lot of overlap.
1253
all_seen = self.seen
1254
pending = set(revisions).intersection(all_seen)
1255
seen_ancestors = set(pending)
1257
if self._returning == 'next':
1258
# self.seen contains what nodes have been returned, not what nodes
1259
# have been queried. We don't want to probe for nodes that haven't
1260
# been searched yet.
1261
not_searched_yet = self._next_query
1263
not_searched_yet = ()
1264
pending.difference_update(not_searched_yet)
1265
get_parent_map = self._parents_provider.get_parent_map
1267
parent_map = get_parent_map(pending)
1269
# We don't care if it is a ghost, since it can't be seen if it is
1271
for parent_ids in parent_map.itervalues():
1272
all_parents.extend(parent_ids)
1273
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1274
seen_ancestors.update(next_pending)
1275
next_pending.difference_update(not_searched_yet)
1276
pending = next_pending
1278
return seen_ancestors
1280
def stop_searching_any(self, revisions):
1282
Remove any of the specified revisions from the search list.
1284
None of the specified revisions are required to be present in the
1285
search list. In this case, the call is a no-op.
1287
# TODO: does this help performance?
1290
revisions = frozenset(revisions)
1291
if self._returning == 'next':
1292
stopped = self._next_query.intersection(revisions)
1293
self._next_query = self._next_query.difference(revisions)
1295
stopped_present = self._current_present.intersection(revisions)
1296
stopped = stopped_present.union(
1297
self._current_ghosts.intersection(revisions))
1298
self._current_present.difference_update(stopped)
1299
self._current_ghosts.difference_update(stopped)
1300
# stopping 'x' should stop returning parents of 'x', but
1301
# not if 'y' always references those same parents
1302
stop_rev_references = {}
1303
for rev in stopped_present:
1304
for parent_id in self._current_parents[rev]:
1305
if parent_id not in stop_rev_references:
1306
stop_rev_references[parent_id] = 0
1307
stop_rev_references[parent_id] += 1
1308
# if only the stopped revisions reference it, the ref count will be
1310
for parents in self._current_parents.itervalues():
1311
for parent_id in parents:
1313
stop_rev_references[parent_id] -= 1
1316
stop_parents = set()
1317
for rev_id, refs in stop_rev_references.iteritems():
1319
stop_parents.add(rev_id)
1320
self._next_query.difference_update(stop_parents)
1321
self._stopped_keys.update(stopped)
1324
def start_searching(self, revisions):
1325
"""Add revisions to the search.
1327
The parents of revisions will be returned from the next call to next()
1328
or next_with_ghosts(). If next_with_ghosts was the most recently used
1329
next* call then the return value is the result of looking up the
1330
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1332
revisions = frozenset(revisions)
1333
self._started_keys.update(revisions)
1334
new_revisions = revisions.difference(self.seen)
1335
if self._returning == 'next':
1336
self._next_query.update(new_revisions)
1337
self.seen.update(new_revisions)
1339
# perform a query on revisions
1340
revs, ghosts, query, parents = self._do_query(revisions)
1341
self._stopped_keys.update(ghosts)
1342
self._current_present.update(revs)
1343
self._current_ghosts.update(ghosts)
1344
self._next_query.update(query)
1345
self._current_parents.update(parents)
1349
class SearchResult(object):
1350
"""The result of a breadth first search.
1352
A SearchResult provides the ability to reconstruct the search or access a
1353
set of the keys the search found.
1356
def __init__(self, start_keys, exclude_keys, key_count, keys):
1357
"""Create a SearchResult.
1359
:param start_keys: The keys the search started at.
1360
:param exclude_keys: The keys the search excludes.
1361
:param key_count: The total number of keys (from start to but not
1363
:param keys: The keys the search found. Note that in future we may get
1364
a SearchResult from a smart server, in which case the keys list is
1365
not necessarily immediately available.
1367
self._recipe = (start_keys, exclude_keys, key_count)
1368
self._keys = frozenset(keys)
1370
def get_recipe(self):
1371
"""Return a recipe that can be used to replay this search.
1373
The recipe allows reconstruction of the same results at a later date
1374
without knowing all the found keys. The essential elements are a list
1375
of keys to start and and to stop at. In order to give reproducible
1376
results when ghosts are encountered by a search they are automatically
1377
added to the exclude list (or else ghost filling may alter the
1380
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1381
recreate the results of this search, create a breadth first
1382
searcher on the same graph starting at start_keys. Then call next()
1383
(or next_with_ghosts()) repeatedly, and on every result, call
1384
stop_searching_any on any keys from the exclude_keys set. The
1385
revision_count value acts as a trivial cross-check - the found
1386
revisions of the new search should have as many elements as
1387
revision_count. If it does not, then additional revisions have been
1388
ghosted since the search was executed the first time and the second
1394
"""Return the keys found in this search.
1396
:return: A set of keys.
added
removed
bzrlib/graph.py
