1
# Copyright (C) 2007-2011 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
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
# Note: DictParentsProvider does not implement get_cached_parent_map
64
# Arguably, the data is clearly cached in memory. However, this class
65
# is mostly used for testing, and it keeps the tests clean to not
68
def get_parent_map(self, keys):
69
"""See StackedParentsProvider.get_parent_map"""
70
ancestry = self.ancestry
71
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
74
class StackedParentsProvider(object):
75
"""A parents provider which stacks (or unions) multiple providers.
77
The providers are queries in the order of the provided parent_providers.
80
def __init__(self, parent_providers):
81
self._parent_providers = parent_providers
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
86
def get_parent_map(self, keys):
87
"""Get a mapping of keys => parents
89
A dictionary is returned with an entry for each key present in this
90
source. If this source doesn't have information about a key, it should
93
[NULL_REVISION] is used as the parent of the first user-committed
94
revision. Its parent list is empty.
96
:param keys: An iterable returning keys to check (eg revision_ids)
97
:return: A dictionary mapping each key to its parents
100
remaining = set(keys)
101
# This adds getattr() overhead to each get_parent_map call. However,
102
# this is StackedParentsProvider, which means we're dealing with I/O
103
# (either local indexes, or remote RPCs), so CPU overhead should be
105
for parents_provider in self._parent_providers:
106
get_cached = getattr(parents_provider, 'get_cached_parent_map',
108
if get_cached is None:
110
new_found = get_cached(remaining)
111
found.update(new_found)
112
remaining.difference_update(new_found)
117
for parents_provider in self._parent_providers:
118
new_found = parents_provider.get_parent_map(remaining)
119
found.update(new_found)
120
remaining.difference_update(new_found)
126
class CachingParentsProvider(object):
127
"""A parents provider which will cache the revision => parents as a dict.
129
This is useful for providers which have an expensive look up.
131
Either a ParentsProvider or a get_parent_map-like callback may be
132
supplied. If it provides extra un-asked-for parents, they will be cached,
133
but filtered out of get_parent_map.
135
The cache is enabled by default, but may be disabled and re-enabled.
137
def __init__(self, parent_provider=None, get_parent_map=None):
140
:param parent_provider: The ParentProvider to use. It or
141
get_parent_map must be supplied.
142
:param get_parent_map: The get_parent_map callback to use. It or
143
parent_provider must be supplied.
145
self._real_provider = parent_provider
146
if get_parent_map is None:
147
self._get_parent_map = self._real_provider.get_parent_map
149
self._get_parent_map = get_parent_map
151
self.enable_cache(True)
154
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
156
def enable_cache(self, cache_misses=True):
158
if self._cache is not None:
159
raise AssertionError('Cache enabled when already enabled.')
161
self._cache_misses = cache_misses
162
self.missing_keys = set()
164
def disable_cache(self):
165
"""Disable and clear the cache."""
167
self._cache_misses = None
168
self.missing_keys = set()
170
def get_cached_map(self):
171
"""Return any cached get_parent_map values."""
172
if self._cache is None:
174
return dict(self._cache)
176
def get_cached_parent_map(self, keys):
177
"""Return items from the cache.
179
This returns the same info as get_parent_map, but explicitly does not
180
invoke the supplied ParentsProvider to search for uncached values.
185
return dict([(key, cache[key]) for key in keys if key in cache])
187
def get_parent_map(self, keys):
188
"""See StackedParentsProvider.get_parent_map."""
191
cache = self._get_parent_map(keys)
193
needed_revisions = set(key for key in keys if key not in cache)
194
# Do not ask for negatively cached keys
195
needed_revisions.difference_update(self.missing_keys)
197
parent_map = self._get_parent_map(needed_revisions)
198
cache.update(parent_map)
199
if self._cache_misses:
200
for key in needed_revisions:
201
if key not in parent_map:
202
self.note_missing_key(key)
205
value = cache.get(key)
206
if value is not None:
210
def note_missing_key(self, key):
211
"""Note that key is a missing key."""
212
if self._cache_misses:
213
self.missing_keys.add(key)
216
class CallableToParentsProviderAdapter(object):
217
"""A parents provider that adapts any callable to the parents provider API.
219
i.e. it accepts calls to self.get_parent_map and relays them to the
220
callable it was constructed with.
223
def __init__(self, a_callable):
224
self.callable = a_callable
227
return "%s(%r)" % (self.__class__.__name__, self.callable)
229
def get_parent_map(self, keys):
230
return self.callable(keys)
234
"""Provide incremental access to revision graphs.
236
This is the generic implementation; it is intended to be subclassed to
237
specialize it for other repository types.
240
def __init__(self, parents_provider):
241
"""Construct a Graph that uses several graphs as its input
243
This should not normally be invoked directly, because there may be
244
specialized implementations for particular repository types. See
245
Repository.get_graph().
247
:param parents_provider: An object providing a get_parent_map call
248
conforming to the behavior of
249
StackedParentsProvider.get_parent_map.
251
if getattr(parents_provider, 'get_parents', None) is not None:
252
self.get_parents = parents_provider.get_parents
253
if getattr(parents_provider, 'get_parent_map', None) is not None:
254
self.get_parent_map = parents_provider.get_parent_map
255
self._parents_provider = parents_provider
258
return 'Graph(%r)' % self._parents_provider
260
def find_lca(self, *revisions):
261
"""Determine the lowest common ancestors of the provided revisions
263
A lowest common ancestor is a common ancestor none of whose
264
descendants are common ancestors. In graphs, unlike trees, there may
265
be multiple lowest common ancestors.
267
This algorithm has two phases. Phase 1 identifies border ancestors,
268
and phase 2 filters border ancestors to determine lowest common
271
In phase 1, border ancestors are identified, using a breadth-first
272
search starting at the bottom of the graph. Searches are stopped
273
whenever a node or one of its descendants is determined to be common
275
In phase 2, the border ancestors are filtered to find the least
276
common ancestors. This is done by searching the ancestries of each
279
Phase 2 is perfomed on the principle that a border ancestor that is
280
not an ancestor of any other border ancestor is a least common
283
Searches are stopped when they find a node that is determined to be a
284
common ancestor of all border ancestors, because this shows that it
285
cannot be a descendant of any border ancestor.
287
The scaling of this operation should be proportional to:
289
1. The number of uncommon ancestors
290
2. The number of border ancestors
291
3. The length of the shortest path between a border ancestor and an
292
ancestor of all border ancestors.
294
border_common, common, sides = self._find_border_ancestors(revisions)
295
# We may have common ancestors that can be reached from each other.
296
# - ask for the heads of them to filter it down to only ones that
297
# cannot be reached from each other - phase 2.
298
return self.heads(border_common)
300
def find_difference(self, left_revision, right_revision):
301
"""Determine the graph difference between two revisions"""
302
border, common, searchers = self._find_border_ancestors(
303
[left_revision, right_revision])
304
self._search_for_extra_common(common, searchers)
305
left = searchers[0].seen
306
right = searchers[1].seen
307
return (left.difference(right), right.difference(left))
309
def find_descendants(self, old_key, new_key):
310
"""Find descendants of old_key that are ancestors of new_key."""
311
child_map = self.get_child_map(self._find_descendant_ancestors(
313
graph = Graph(DictParentsProvider(child_map))
314
searcher = graph._make_breadth_first_searcher([old_key])
318
def _find_descendant_ancestors(self, old_key, new_key):
319
"""Find ancestors of new_key that may be descendants of old_key."""
320
stop = self._make_breadth_first_searcher([old_key])
321
descendants = self._make_breadth_first_searcher([new_key])
322
for revisions in descendants:
323
old_stop = stop.seen.intersection(revisions)
324
descendants.stop_searching_any(old_stop)
325
seen_stop = descendants.find_seen_ancestors(stop.step())
326
descendants.stop_searching_any(seen_stop)
327
return descendants.seen.difference(stop.seen)
329
def get_child_map(self, keys):
330
"""Get a mapping from parents to children of the specified keys.
332
This is simply the inversion of get_parent_map. Only supplied keys
333
will be discovered as children.
334
:return: a dict of key:child_list for keys.
336
parent_map = self._parents_provider.get_parent_map(keys)
338
for child, parents in sorted(parent_map.items()):
339
for parent in parents:
340
parent_child.setdefault(parent, []).append(child)
343
def find_distance_to_null(self, target_revision_id, known_revision_ids):
344
"""Find the left-hand distance to the NULL_REVISION.
346
(This can also be considered the revno of a branch at
349
:param target_revision_id: A revision_id which we would like to know
351
:param known_revision_ids: [(revision_id, revno)] A list of known
352
revno, revision_id tuples. We'll use this to seed the search.
354
# Map from revision_ids to a known value for their revno
355
known_revnos = dict(known_revision_ids)
356
cur_tip = target_revision_id
358
NULL_REVISION = revision.NULL_REVISION
359
known_revnos[NULL_REVISION] = 0
361
searching_known_tips = list(known_revnos.keys())
363
unknown_searched = {}
365
while cur_tip not in known_revnos:
366
unknown_searched[cur_tip] = num_steps
368
to_search = set([cur_tip])
369
to_search.update(searching_known_tips)
370
parent_map = self.get_parent_map(to_search)
371
parents = parent_map.get(cur_tip, None)
372
if not parents: # An empty list or None is a ghost
373
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
377
for revision_id in searching_known_tips:
378
parents = parent_map.get(revision_id, None)
382
next_revno = known_revnos[revision_id] - 1
383
if next in unknown_searched:
384
# We have enough information to return a value right now
385
return next_revno + unknown_searched[next]
386
if next in known_revnos:
388
known_revnos[next] = next_revno
389
next_known_tips.append(next)
390
searching_known_tips = next_known_tips
392
# We reached a known revision, so just add in how many steps it took to
394
return known_revnos[cur_tip] + num_steps
396
def find_lefthand_distances(self, keys):
397
"""Find the distance to null for all the keys in keys.
399
:param keys: keys to lookup.
400
:return: A dict key->distance for all of keys.
402
# Optimisable by concurrent searching, but a random spread should get
403
# some sort of hit rate.
410
(key, self.find_distance_to_null(key, known_revnos)))
411
except errors.GhostRevisionsHaveNoRevno:
414
known_revnos.append((key, -1))
415
return dict(known_revnos)
417
def find_unique_ancestors(self, unique_revision, common_revisions):
418
"""Find the unique ancestors for a revision versus others.
420
This returns the ancestry of unique_revision, excluding all revisions
421
in the ancestry of common_revisions. If unique_revision is in the
422
ancestry, then the empty set will be returned.
424
:param unique_revision: The revision_id whose ancestry we are
426
(XXX: Would this API be better if we allowed multiple revisions on
427
to be searched here?)
428
:param common_revisions: Revision_ids of ancestries to exclude.
429
:return: A set of revisions in the ancestry of unique_revision
431
if unique_revision in common_revisions:
434
# Algorithm description
435
# 1) Walk backwards from the unique node and all common nodes.
436
# 2) When a node is seen by both sides, stop searching it in the unique
437
# walker, include it in the common walker.
438
# 3) Stop searching when there are no nodes left for the unique walker.
439
# At this point, you have a maximal set of unique nodes. Some of
440
# them may actually be common, and you haven't reached them yet.
441
# 4) Start new searchers for the unique nodes, seeded with the
442
# information you have so far.
443
# 5) Continue searching, stopping the common searches when the search
444
# tip is an ancestor of all unique nodes.
445
# 6) Aggregate together unique searchers when they are searching the
446
# same tips. When all unique searchers are searching the same node,
447
# stop move it to a single 'all_unique_searcher'.
448
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
449
# Most of the time this produces very little important information.
450
# So don't step it as quickly as the other searchers.
451
# 8) Search is done when all common searchers have completed.
453
unique_searcher, common_searcher = self._find_initial_unique_nodes(
454
[unique_revision], common_revisions)
456
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
460
(all_unique_searcher,
461
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
462
unique_searcher, common_searcher)
464
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
465
unique_tip_searchers, common_searcher)
466
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
467
if 'graph' in debug.debug_flags:
468
trace.mutter('Found %d truly unique nodes out of %d',
469
len(true_unique_nodes), len(unique_nodes))
470
return true_unique_nodes
472
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
473
"""Steps 1-3 of find_unique_ancestors.
475
Find the maximal set of unique nodes. Some of these might actually
476
still be common, but we are sure that there are no other unique nodes.
478
:return: (unique_searcher, common_searcher)
481
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
482
# we know that unique_revisions aren't in common_revisions, so skip
484
unique_searcher.next()
485
common_searcher = self._make_breadth_first_searcher(common_revisions)
487
# As long as we are still finding unique nodes, keep searching
488
while unique_searcher._next_query:
489
next_unique_nodes = set(unique_searcher.step())
490
next_common_nodes = set(common_searcher.step())
492
# Check if either searcher encounters new nodes seen by the other
494
unique_are_common_nodes = next_unique_nodes.intersection(
495
common_searcher.seen)
496
unique_are_common_nodes.update(
497
next_common_nodes.intersection(unique_searcher.seen))
498
if unique_are_common_nodes:
499
ancestors = unique_searcher.find_seen_ancestors(
500
unique_are_common_nodes)
501
# TODO: This is a bit overboard, we only really care about
502
# the ancestors of the tips because the rest we
503
# already know. This is *correct* but causes us to
504
# search too much ancestry.
505
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
506
unique_searcher.stop_searching_any(ancestors)
507
common_searcher.start_searching(ancestors)
509
return unique_searcher, common_searcher
511
def _make_unique_searchers(self, unique_nodes, unique_searcher,
513
"""Create a searcher for all the unique search tips (step 4).
515
As a side effect, the common_searcher will stop searching any nodes
516
that are ancestors of the unique searcher tips.
518
:return: (all_unique_searcher, unique_tip_searchers)
520
unique_tips = self._remove_simple_descendants(unique_nodes,
521
self.get_parent_map(unique_nodes))
523
if len(unique_tips) == 1:
524
unique_tip_searchers = []
525
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
527
unique_tip_searchers = []
528
for tip in unique_tips:
529
revs_to_search = unique_searcher.find_seen_ancestors([tip])
530
revs_to_search.update(
531
common_searcher.find_seen_ancestors(revs_to_search))
532
searcher = self._make_breadth_first_searcher(revs_to_search)
533
# We don't care about the starting nodes.
534
searcher._label = tip
536
unique_tip_searchers.append(searcher)
538
ancestor_all_unique = None
539
for searcher in unique_tip_searchers:
540
if ancestor_all_unique is None:
541
ancestor_all_unique = set(searcher.seen)
543
ancestor_all_unique = ancestor_all_unique.intersection(
545
# Collapse all the common nodes into a single searcher
546
all_unique_searcher = self._make_breadth_first_searcher(
548
if ancestor_all_unique:
549
# We've seen these nodes in all the searchers, so we'll just go to
551
all_unique_searcher.step()
553
# Stop any search tips that are already known as ancestors of the
555
stopped_common = common_searcher.stop_searching_any(
556
common_searcher.find_seen_ancestors(ancestor_all_unique))
559
for searcher in unique_tip_searchers:
560
total_stopped += len(searcher.stop_searching_any(
561
searcher.find_seen_ancestors(ancestor_all_unique)))
562
if 'graph' in debug.debug_flags:
563
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
564
' (%d stopped search tips, %d common ancestors'
565
' (%d stopped common)',
566
len(unique_nodes), len(unique_tip_searchers),
567
total_stopped, len(ancestor_all_unique),
569
return all_unique_searcher, unique_tip_searchers
571
def _step_unique_and_common_searchers(self, common_searcher,
572
unique_tip_searchers,
574
"""Step all the searchers"""
575
newly_seen_common = set(common_searcher.step())
576
newly_seen_unique = set()
577
for searcher in unique_tip_searchers:
578
next = set(searcher.step())
579
next.update(unique_searcher.find_seen_ancestors(next))
580
next.update(common_searcher.find_seen_ancestors(next))
581
for alt_searcher in unique_tip_searchers:
582
if alt_searcher is searcher:
584
next.update(alt_searcher.find_seen_ancestors(next))
585
searcher.start_searching(next)
586
newly_seen_unique.update(next)
587
return newly_seen_common, newly_seen_unique
589
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
591
newly_seen_unique, step_all_unique):
592
"""Find nodes that are common to all unique_tip_searchers.
594
If it is time, step the all_unique_searcher, and add its nodes to the
597
common_to_all_unique_nodes = newly_seen_unique.copy()
598
for searcher in unique_tip_searchers:
599
common_to_all_unique_nodes.intersection_update(searcher.seen)
600
common_to_all_unique_nodes.intersection_update(
601
all_unique_searcher.seen)
602
# Step all-unique less frequently than the other searchers.
603
# In the common case, we don't need to spider out far here, so
604
# avoid doing extra work.
606
tstart = time.clock()
607
nodes = all_unique_searcher.step()
608
common_to_all_unique_nodes.update(nodes)
609
if 'graph' in debug.debug_flags:
610
tdelta = time.clock() - tstart
611
trace.mutter('all_unique_searcher step() took %.3fs'
612
'for %d nodes (%d total), iteration: %s',
613
tdelta, len(nodes), len(all_unique_searcher.seen),
614
all_unique_searcher._iterations)
615
return common_to_all_unique_nodes
617
def _collapse_unique_searchers(self, unique_tip_searchers,
618
common_to_all_unique_nodes):
619
"""Combine searchers that are searching the same tips.
621
When two searchers are searching the same tips, we can stop one of the
622
searchers. We also know that the maximal set of common ancestors is the
623
intersection of the two original searchers.
625
:return: A list of searchers that are searching unique nodes.
627
# Filter out searchers that don't actually search different
628
# nodes. We already have the ancestry intersection for them
629
unique_search_tips = {}
630
for searcher in unique_tip_searchers:
631
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
632
will_search_set = frozenset(searcher._next_query)
633
if not will_search_set:
634
if 'graph' in debug.debug_flags:
635
trace.mutter('Unique searcher %s was stopped.'
636
' (%s iterations) %d nodes stopped',
638
searcher._iterations,
640
elif will_search_set not in unique_search_tips:
641
# This searcher is searching a unique set of nodes, let it
642
unique_search_tips[will_search_set] = [searcher]
644
unique_search_tips[will_search_set].append(searcher)
645
# TODO: it might be possible to collapse searchers faster when they
646
# only have *some* search tips in common.
647
next_unique_searchers = []
648
for searchers in unique_search_tips.itervalues():
649
if len(searchers) == 1:
650
# Searching unique tips, go for it
651
next_unique_searchers.append(searchers[0])
653
# These searchers have started searching the same tips, we
654
# don't need them to cover the same ground. The
655
# intersection of their ancestry won't change, so create a
656
# new searcher, combining their histories.
657
next_searcher = searchers[0]
658
for searcher in searchers[1:]:
659
next_searcher.seen.intersection_update(searcher.seen)
660
if 'graph' in debug.debug_flags:
661
trace.mutter('Combining %d searchers into a single'
662
' searcher searching %d nodes with'
665
len(next_searcher._next_query),
666
len(next_searcher.seen))
667
next_unique_searchers.append(next_searcher)
668
return next_unique_searchers
670
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
671
unique_tip_searchers, common_searcher):
672
"""Steps 5-8 of find_unique_ancestors.
674
This function returns when common_searcher has stopped searching for
677
# We step the ancestor_all_unique searcher only every
678
# STEP_UNIQUE_SEARCHER_EVERY steps.
679
step_all_unique_counter = 0
680
# While we still have common nodes to search
681
while common_searcher._next_query:
683
newly_seen_unique) = self._step_unique_and_common_searchers(
684
common_searcher, unique_tip_searchers, unique_searcher)
685
# These nodes are common ancestors of all unique nodes
686
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
687
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
688
step_all_unique_counter==0)
689
step_all_unique_counter = ((step_all_unique_counter + 1)
690
% STEP_UNIQUE_SEARCHER_EVERY)
692
if newly_seen_common:
693
# If a 'common' node is an ancestor of all unique searchers, we
694
# can stop searching it.
695
common_searcher.stop_searching_any(
696
all_unique_searcher.seen.intersection(newly_seen_common))
697
if common_to_all_unique_nodes:
698
common_to_all_unique_nodes.update(
699
common_searcher.find_seen_ancestors(
700
common_to_all_unique_nodes))
701
# The all_unique searcher can start searching the common nodes
702
# but everyone else can stop.
703
# This is the sort of thing where we would like to not have it
704
# start_searching all of the nodes, but only mark all of them
705
# as seen, and have it search only the actual tips. Otherwise
706
# it is another get_parent_map() traversal for it to figure out
707
# what we already should know.
708
all_unique_searcher.start_searching(common_to_all_unique_nodes)
709
common_searcher.stop_searching_any(common_to_all_unique_nodes)
711
next_unique_searchers = self._collapse_unique_searchers(
712
unique_tip_searchers, common_to_all_unique_nodes)
713
if len(unique_tip_searchers) != len(next_unique_searchers):
714
if 'graph' in debug.debug_flags:
715
trace.mutter('Collapsed %d unique searchers => %d'
717
len(unique_tip_searchers),
718
len(next_unique_searchers),
719
all_unique_searcher._iterations)
720
unique_tip_searchers = next_unique_searchers
722
def get_parent_map(self, revisions):
723
"""Get a map of key:parent_list for revisions.
725
This implementation delegates to get_parents, for old parent_providers
726
that do not supply get_parent_map.
729
for rev, parents in self.get_parents(revisions):
730
if parents is not None:
731
result[rev] = parents
734
def _make_breadth_first_searcher(self, revisions):
735
return _BreadthFirstSearcher(revisions, self)
737
def _find_border_ancestors(self, revisions):
738
"""Find common ancestors with at least one uncommon descendant.
740
Border ancestors are identified using a breadth-first
741
search starting at the bottom of the graph. Searches are stopped
742
whenever a node or one of its descendants is determined to be common.
744
This will scale with the number of uncommon ancestors.
746
As well as the border ancestors, a set of seen common ancestors and a
747
list of sets of seen ancestors for each input revision is returned.
748
This allows calculation of graph difference from the results of this
751
if None in revisions:
752
raise errors.InvalidRevisionId(None, self)
753
common_ancestors = set()
754
searchers = [self._make_breadth_first_searcher([r])
756
active_searchers = searchers[:]
757
border_ancestors = set()
761
for searcher in searchers:
762
new_ancestors = searcher.step()
764
newly_seen.update(new_ancestors)
766
for revision in newly_seen:
767
if revision in common_ancestors:
768
# Not a border ancestor because it was seen as common
770
new_common.add(revision)
772
for searcher in searchers:
773
if revision not in searcher.seen:
776
# This is a border because it is a first common that we see
777
# after walking for a while.
778
border_ancestors.add(revision)
779
new_common.add(revision)
781
for searcher in searchers:
782
new_common.update(searcher.find_seen_ancestors(new_common))
783
for searcher in searchers:
784
searcher.start_searching(new_common)
785
common_ancestors.update(new_common)
787
# Figure out what the searchers will be searching next, and if
788
# there is only 1 set being searched, then we are done searching,
789
# since all searchers would have to be searching the same data,
790
# thus it *must* be in common.
791
unique_search_sets = set()
792
for searcher in searchers:
793
will_search_set = frozenset(searcher._next_query)
794
if will_search_set not in unique_search_sets:
795
# This searcher is searching a unique set of nodes, let it
796
unique_search_sets.add(will_search_set)
798
if len(unique_search_sets) == 1:
799
nodes = unique_search_sets.pop()
800
uncommon_nodes = nodes.difference(common_ancestors)
802
raise AssertionError("Somehow we ended up converging"
803
" without actually marking them as"
806
"\nuncommon_nodes: %s"
807
% (revisions, uncommon_nodes))
809
return border_ancestors, common_ancestors, searchers
811
def heads(self, keys):
812
"""Return the heads from amongst keys.
814
This is done by searching the ancestries of each key. Any key that is
815
reachable from another key is not returned; all the others are.
817
This operation scales with the relative depth between any two keys. If
818
any two keys are completely disconnected all ancestry of both sides
821
:param keys: An iterable of keys.
822
:return: A set of the heads. Note that as a set there is no ordering
823
information. Callers will need to filter their input to create
824
order if they need it.
826
candidate_heads = set(keys)
827
if revision.NULL_REVISION in candidate_heads:
828
# NULL_REVISION is only a head if it is the only entry
829
candidate_heads.remove(revision.NULL_REVISION)
830
if not candidate_heads:
831
return set([revision.NULL_REVISION])
832
if len(candidate_heads) < 2:
833
return candidate_heads
834
searchers = dict((c, self._make_breadth_first_searcher([c]))
835
for c in candidate_heads)
836
active_searchers = dict(searchers)
837
# skip over the actual candidate for each searcher
838
for searcher in active_searchers.itervalues():
840
# The common walker finds nodes that are common to two or more of the
841
# input keys, so that we don't access all history when a currently
842
# uncommon search point actually meets up with something behind a
843
# common search point. Common search points do not keep searches
844
# active; they just allow us to make searches inactive without
845
# accessing all history.
846
common_walker = self._make_breadth_first_searcher([])
847
while len(active_searchers) > 0:
852
except StopIteration:
853
# No common points being searched at this time.
855
for candidate in active_searchers.keys():
857
searcher = active_searchers[candidate]
859
# rare case: we deleted candidate in a previous iteration
860
# through this for loop, because it was determined to be
861
# a descendant of another candidate.
864
ancestors.update(searcher.next())
865
except StopIteration:
866
del active_searchers[candidate]
868
# process found nodes
870
for ancestor in ancestors:
871
if ancestor in candidate_heads:
872
candidate_heads.remove(ancestor)
873
del searchers[ancestor]
874
if ancestor in active_searchers:
875
del active_searchers[ancestor]
876
# it may meet up with a known common node
877
if ancestor in common_walker.seen:
878
# some searcher has encountered our known common nodes:
880
ancestor_set = set([ancestor])
881
for searcher in searchers.itervalues():
882
searcher.stop_searching_any(ancestor_set)
884
# or it may have been just reached by all the searchers:
885
for searcher in searchers.itervalues():
886
if ancestor not in searcher.seen:
889
# The final active searcher has just reached this node,
890
# making it be known as a descendant of all candidates,
891
# so we can stop searching it, and any seen ancestors
892
new_common.add(ancestor)
893
for searcher in searchers.itervalues():
895
searcher.find_seen_ancestors([ancestor])
896
searcher.stop_searching_any(seen_ancestors)
897
common_walker.start_searching(new_common)
898
return candidate_heads
900
def find_merge_order(self, tip_revision_id, lca_revision_ids):
901
"""Find the order that each revision was merged into tip.
903
This basically just walks backwards with a stack, and walks left-first
904
until it finds a node to stop.
906
if len(lca_revision_ids) == 1:
907
return list(lca_revision_ids)
908
looking_for = set(lca_revision_ids)
909
# TODO: Is there a way we could do this "faster" by batching up the
910
# get_parent_map requests?
911
# TODO: Should we also be culling the ancestry search right away? We
912
# could add looking_for to the "stop" list, and walk their
913
# ancestry in batched mode. The flip side is it might mean we walk a
914
# lot of "stop" nodes, rather than only the minimum.
915
# Then again, without it we may trace back into ancestry we could have
917
stack = [tip_revision_id]
920
while stack and looking_for:
923
if next in looking_for:
925
looking_for.remove(next)
926
if len(looking_for) == 1:
927
found.append(looking_for.pop())
930
parent_ids = self.get_parent_map([next]).get(next, None)
931
if not parent_ids: # Ghost, nothing to search here
933
for parent_id in reversed(parent_ids):
934
# TODO: (performance) We see the parent at this point, but we
935
# wait to mark it until later to make sure we get left
936
# parents before right parents. However, instead of
937
# waiting until we have traversed enough parents, we
938
# could instead note that we've found it, and once all
939
# parents are in the stack, just reverse iterate the
941
if parent_id not in stop:
942
# this will need to be searched
943
stack.append(parent_id)
947
def find_lefthand_merger(self, merged_key, tip_key):
948
"""Find the first lefthand ancestor of tip_key that merged merged_key.
950
We do this by first finding the descendants of merged_key, then
951
walking through the lefthand ancestry of tip_key until we find a key
952
that doesn't descend from merged_key. Its child is the key that
955
:return: The first lefthand ancestor of tip_key to merge merged_key.
956
merged_key if it is a lefthand ancestor of tip_key.
957
None if no ancestor of tip_key merged merged_key.
959
descendants = self.find_descendants(merged_key, tip_key)
960
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
961
last_candidate = None
962
for candidate in candidate_iterator:
963
if candidate not in descendants:
964
return last_candidate
965
last_candidate = candidate
967
def find_unique_lca(self, left_revision, right_revision,
969
"""Find a unique LCA.
971
Find lowest common ancestors. If there is no unique common
972
ancestor, find the lowest common ancestors of those ancestors.
974
Iteration stops when a unique lowest common ancestor is found.
975
The graph origin is necessarily a unique lowest common ancestor.
977
Note that None is not an acceptable substitute for NULL_REVISION.
978
in the input for this method.
980
:param count_steps: If True, the return value will be a tuple of
981
(unique_lca, steps) where steps is the number of times that
982
find_lca was run. If False, only unique_lca is returned.
984
revisions = [left_revision, right_revision]
988
lca = self.find_lca(*revisions)
996
raise errors.NoCommonAncestor(left_revision, right_revision)
999
def iter_ancestry(self, revision_ids):
1000
"""Iterate the ancestry of this revision.
1002
:param revision_ids: Nodes to start the search
1003
:return: Yield tuples mapping a revision_id to its parents for the
1004
ancestry of revision_id.
1005
Ghosts will be returned with None as their parents, and nodes
1006
with no parents will have NULL_REVISION as their only parent. (As
1007
defined by get_parent_map.)
1008
There will also be a node for (NULL_REVISION, ())
1010
pending = set(revision_ids)
1013
processed.update(pending)
1014
next_map = self.get_parent_map(pending)
1015
next_pending = set()
1016
for item in next_map.iteritems():
1018
next_pending.update(p for p in item[1] if p not in processed)
1019
ghosts = pending.difference(next_map)
1020
for ghost in ghosts:
1022
pending = next_pending
1024
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1025
if stop_keys is None:
1027
next_key = start_key
1028
def get_parents(key):
1030
return self._parents_provider.get_parent_map([key])[key]
1032
raise errors.RevisionNotPresent(next_key, self)
1034
if next_key in stop_keys:
1036
parents = get_parents(next_key)
1038
if len(parents) == 0:
1041
next_key = parents[0]
1043
def iter_topo_order(self, revisions):
1044
"""Iterate through the input revisions in topological order.
1046
This sorting only ensures that parents come before their children.
1047
An ancestor may sort after a descendant if the relationship is not
1048
visible in the supplied list of revisions.
1050
from bzrlib import tsort
1051
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1052
return sorter.iter_topo_order()
1054
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1055
"""Determine whether a revision is an ancestor of another.
1057
We answer this using heads() as heads() has the logic to perform the
1058
smallest number of parent lookups to determine the ancestral
1059
relationship between N revisions.
1061
return set([candidate_descendant]) == self.heads(
1062
[candidate_ancestor, candidate_descendant])
1064
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1065
"""Determine whether a revision is between two others.
1067
returns true if and only if:
1068
lower_bound_revid <= revid <= upper_bound_revid
1070
return ((upper_bound_revid is None or
1071
self.is_ancestor(revid, upper_bound_revid)) and
1072
(lower_bound_revid is None or
1073
self.is_ancestor(lower_bound_revid, revid)))
1075
def _search_for_extra_common(self, common, searchers):
1076
"""Make sure that unique nodes are genuinely unique.
1078
After _find_border_ancestors, all nodes marked "common" are indeed
1079
common. Some of the nodes considered unique are not, due to history
1080
shortcuts stopping the searches early.
1082
We know that we have searched enough when all common search tips are
1083
descended from all unique (uncommon) nodes because we know that a node
1084
cannot be an ancestor of its own ancestor.
1086
:param common: A set of common nodes
1087
:param searchers: The searchers returned from _find_border_ancestors
1090
# Basic algorithm...
1091
# A) The passed in searchers should all be on the same tips, thus
1092
# they should be considered the "common" searchers.
1093
# B) We find the difference between the searchers, these are the
1094
# "unique" nodes for each side.
1095
# C) We do a quick culling so that we only start searching from the
1096
# more interesting unique nodes. (A unique ancestor is more
1097
# interesting than any of its children.)
1098
# D) We start searching for ancestors common to all unique nodes.
1099
# E) We have the common searchers stop searching any ancestors of
1100
# nodes found by (D)
1101
# F) When there are no more common search tips, we stop
1103
# TODO: We need a way to remove unique_searchers when they overlap with
1104
# other unique searchers.
1105
if len(searchers) != 2:
1106
raise NotImplementedError(
1107
"Algorithm not yet implemented for > 2 searchers")
1108
common_searchers = searchers
1109
left_searcher = searchers[0]
1110
right_searcher = searchers[1]
1111
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1112
if not unique: # No unique nodes, nothing to do
1114
total_unique = len(unique)
1115
unique = self._remove_simple_descendants(unique,
1116
self.get_parent_map(unique))
1117
simple_unique = len(unique)
1119
unique_searchers = []
1120
for revision_id in unique:
1121
if revision_id in left_searcher.seen:
1122
parent_searcher = left_searcher
1124
parent_searcher = right_searcher
1125
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1126
if not revs_to_search: # XXX: This shouldn't be possible
1127
revs_to_search = [revision_id]
1128
searcher = self._make_breadth_first_searcher(revs_to_search)
1129
# We don't care about the starting nodes.
1131
unique_searchers.append(searcher)
1133
# possible todo: aggregate the common searchers into a single common
1134
# searcher, just make sure that we include the nodes into the .seen
1135
# properties of the original searchers
1137
ancestor_all_unique = None
1138
for searcher in unique_searchers:
1139
if ancestor_all_unique is None:
1140
ancestor_all_unique = set(searcher.seen)
1142
ancestor_all_unique = ancestor_all_unique.intersection(
1145
trace.mutter('Started %s unique searchers for %s unique revisions',
1146
simple_unique, total_unique)
1148
while True: # If we have no more nodes we have nothing to do
1149
newly_seen_common = set()
1150
for searcher in common_searchers:
1151
newly_seen_common.update(searcher.step())
1152
newly_seen_unique = set()
1153
for searcher in unique_searchers:
1154
newly_seen_unique.update(searcher.step())
1155
new_common_unique = set()
1156
for revision in newly_seen_unique:
1157
for searcher in unique_searchers:
1158
if revision not in searcher.seen:
1161
# This is a border because it is a first common that we see
1162
# after walking for a while.
1163
new_common_unique.add(revision)
1164
if newly_seen_common:
1165
# These are nodes descended from one of the 'common' searchers.
1166
# Make sure all searchers are on the same page
1167
for searcher in common_searchers:
1168
newly_seen_common.update(
1169
searcher.find_seen_ancestors(newly_seen_common))
1170
# We start searching the whole ancestry. It is a bit wasteful,
1171
# though. We really just want to mark all of these nodes as
1172
# 'seen' and then start just the tips. However, it requires a
1173
# get_parent_map() call to figure out the tips anyway, and all
1174
# redundant requests should be fairly fast.
1175
for searcher in common_searchers:
1176
searcher.start_searching(newly_seen_common)
1178
# If a 'common' node is an ancestor of all unique searchers, we
1179
# can stop searching it.
1180
stop_searching_common = ancestor_all_unique.intersection(
1182
if stop_searching_common:
1183
for searcher in common_searchers:
1184
searcher.stop_searching_any(stop_searching_common)
1185
if new_common_unique:
1186
# We found some ancestors that are common
1187
for searcher in unique_searchers:
1188
new_common_unique.update(
1189
searcher.find_seen_ancestors(new_common_unique))
1190
# Since these are common, we can grab another set of ancestors
1192
for searcher in common_searchers:
1193
new_common_unique.update(
1194
searcher.find_seen_ancestors(new_common_unique))
1196
# We can tell all of the unique searchers to start at these
1197
# nodes, and tell all of the common searchers to *stop*
1198
# searching these nodes
1199
for searcher in unique_searchers:
1200
searcher.start_searching(new_common_unique)
1201
for searcher in common_searchers:
1202
searcher.stop_searching_any(new_common_unique)
1203
ancestor_all_unique.update(new_common_unique)
1205
# Filter out searchers that don't actually search different
1206
# nodes. We already have the ancestry intersection for them
1207
next_unique_searchers = []
1208
unique_search_sets = set()
1209
for searcher in unique_searchers:
1210
will_search_set = frozenset(searcher._next_query)
1211
if will_search_set not in unique_search_sets:
1212
# This searcher is searching a unique set of nodes, let it
1213
unique_search_sets.add(will_search_set)
1214
next_unique_searchers.append(searcher)
1215
unique_searchers = next_unique_searchers
1216
for searcher in common_searchers:
1217
if searcher._next_query:
1220
# All common searcher have stopped searching
1223
def _remove_simple_descendants(self, revisions, parent_map):
1224
"""remove revisions which are children of other ones in the set
1226
This doesn't do any graph searching, it just checks the immediate
1227
parent_map to find if there are any children which can be removed.
1229
:param revisions: A set of revision_ids
1230
:return: A set of revision_ids with the children removed
1232
simple_ancestors = revisions.copy()
1233
# TODO: jam 20071214 we *could* restrict it to searching only the
1234
# parent_map of revisions already present in 'revisions', but
1235
# considering the general use case, I think this is actually
1238
# This is the same as the following loop. I don't know that it is any
1240
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1241
## if p_ids is not None and revisions.intersection(p_ids))
1242
## return simple_ancestors
1244
# Yet Another Way, invert the parent map (which can be cached)
1246
## for revision_id, parent_ids in parent_map.iteritems():
1247
## for p_id in parent_ids:
1248
## descendants.setdefault(p_id, []).append(revision_id)
1249
## for revision in revisions.intersection(descendants):
1250
## simple_ancestors.difference_update(descendants[revision])
1251
## return simple_ancestors
1252
for revision, parent_ids in parent_map.iteritems():
1253
if parent_ids is None:
1255
for parent_id in parent_ids:
1256
if parent_id in revisions:
1257
# This node has a parent present in the set, so we can
1259
simple_ancestors.discard(revision)
1261
return simple_ancestors
1264
class HeadsCache(object):
1265
"""A cache of results for graph heads calls."""
1267
def __init__(self, graph):
1271
def heads(self, keys):
1272
"""Return the heads of keys.
1274
This matches the API of Graph.heads(), specifically the return value is
1275
a set which can be mutated, and ordering of the input is not preserved
1278
:see also: Graph.heads.
1279
:param keys: The keys to calculate heads for.
1280
:return: A set containing the heads, which may be mutated without
1281
affecting future lookups.
1283
keys = frozenset(keys)
1285
return set(self._heads[keys])
1287
heads = self.graph.heads(keys)
1288
self._heads[keys] = heads
1292
class FrozenHeadsCache(object):
1293
"""Cache heads() calls, assuming the caller won't modify them."""
1295
def __init__(self, graph):
1299
def heads(self, keys):
1300
"""Return the heads of keys.
1302
Similar to Graph.heads(). The main difference is that the return value
1303
is a frozen set which cannot be mutated.
1305
:see also: Graph.heads.
1306
:param keys: The keys to calculate heads for.
1307
:return: A frozenset containing the heads.
1309
keys = frozenset(keys)
1311
return self._heads[keys]
1313
heads = frozenset(self.graph.heads(keys))
1314
self._heads[keys] = heads
1317
def cache(self, keys, heads):
1318
"""Store a known value."""
1319
self._heads[frozenset(keys)] = frozenset(heads)
1322
class _BreadthFirstSearcher(object):
1323
"""Parallel search breadth-first the ancestry of revisions.
1325
This class implements the iterator protocol, but additionally
1326
1. provides a set of seen ancestors, and
1327
2. allows some ancestries to be unsearched, via stop_searching_any
1330
def __init__(self, revisions, parents_provider):
1331
self._iterations = 0
1332
self._next_query = set(revisions)
1334
self._started_keys = set(self._next_query)
1335
self._stopped_keys = set()
1336
self._parents_provider = parents_provider
1337
self._returning = 'next_with_ghosts'
1338
self._current_present = set()
1339
self._current_ghosts = set()
1340
self._current_parents = {}
1343
if self._iterations:
1344
prefix = "searching"
1347
search = '%s=%r' % (prefix, list(self._next_query))
1348
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1349
' seen=%r)' % (self._iterations, search, list(self.seen)))
1351
def get_state(self):
1352
"""Get the current state of this searcher.
1354
:return: Tuple with started keys, excludes and included keys
1356
if self._returning == 'next':
1357
# We have to know the current nodes children to be able to list the
1358
# exclude keys for them. However, while we could have a second
1359
# look-ahead result buffer and shuffle things around, this method
1360
# is typically only called once per search - when memoising the
1361
# results of the search.
1362
found, ghosts, next, parents = self._do_query(self._next_query)
1363
# pretend we didn't query: perhaps we should tweak _do_query to be
1364
# entirely stateless?
1365
self.seen.difference_update(next)
1366
next_query = next.union(ghosts)
1368
next_query = self._next_query
1369
excludes = self._stopped_keys.union(next_query)
1370
included_keys = self.seen.difference(excludes)
1371
return self._started_keys, excludes, included_keys
1373
def _get_result(self):
1374
"""Get a SearchResult for the current state of this searcher.
1376
:return: A SearchResult for this search so far. The SearchResult is
1377
static - the search can be advanced and the search result will not
1378
be invalidated or altered.
1380
from bzrlib.vf_search import SearchResult
1381
(started_keys, excludes, included_keys) = self.get_state()
1382
return SearchResult(started_keys, excludes, len(included_keys),
1388
except StopIteration:
1392
"""Return the next ancestors of this revision.
1394
Ancestors are returned in the order they are seen in a breadth-first
1395
traversal. No ancestor will be returned more than once. Ancestors are
1396
returned before their parentage is queried, so ghosts and missing
1397
revisions (including the start revisions) are included in the result.
1398
This can save a round trip in LCA style calculation by allowing
1399
convergence to be detected without reading the data for the revision
1400
the convergence occurs on.
1402
:return: A set of revision_ids.
1404
if self._returning != 'next':
1405
# switch to returning the query, not the results.
1406
self._returning = 'next'
1407
self._iterations += 1
1410
if len(self._next_query) == 0:
1411
raise StopIteration()
1412
# We have seen what we're querying at this point as we are returning
1413
# the query, not the results.
1414
self.seen.update(self._next_query)
1415
return self._next_query
1417
def next_with_ghosts(self):
1418
"""Return the next found ancestors, with ghosts split out.
1420
Ancestors are returned in the order they are seen in a breadth-first
1421
traversal. No ancestor will be returned more than once. Ancestors are
1422
returned only after asking for their parents, which allows us to detect
1423
which revisions are ghosts and which are not.
1425
:return: A tuple with (present ancestors, ghost ancestors) sets.
1427
if self._returning != 'next_with_ghosts':
1428
# switch to returning the results, not the current query.
1429
self._returning = 'next_with_ghosts'
1431
if len(self._next_query) == 0:
1432
raise StopIteration()
1434
return self._current_present, self._current_ghosts
1437
"""Advance the search.
1439
Updates self.seen, self._next_query, self._current_present,
1440
self._current_ghosts, self._current_parents and self._iterations.
1442
self._iterations += 1
1443
found, ghosts, next, parents = self._do_query(self._next_query)
1444
self._current_present = found
1445
self._current_ghosts = ghosts
1446
self._next_query = next
1447
self._current_parents = parents
1448
# ghosts are implicit stop points, otherwise the search cannot be
1449
# repeated when ghosts are filled.
1450
self._stopped_keys.update(ghosts)
1452
def _do_query(self, revisions):
1453
"""Query for revisions.
1455
Adds revisions to the seen set.
1457
:param revisions: Revisions to query.
1458
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1459
set(parents_of_found_revisions), dict(found_revisions:parents)).
1461
found_revisions = set()
1462
parents_of_found = set()
1463
# revisions may contain nodes that point to other nodes in revisions:
1464
# we want to filter them out.
1466
seen.update(revisions)
1467
parent_map = self._parents_provider.get_parent_map(revisions)
1468
found_revisions.update(parent_map)
1469
for rev_id, parents in parent_map.iteritems():
1472
new_found_parents = [p for p in parents if p not in seen]
1473
if new_found_parents:
1474
# Calling set.update() with an empty generator is actually
1476
parents_of_found.update(new_found_parents)
1477
ghost_revisions = revisions - found_revisions
1478
return found_revisions, ghost_revisions, parents_of_found, parent_map
1483
def find_seen_ancestors(self, revisions):
1484
"""Find ancestors of these revisions that have already been seen.
1486
This function generally makes the assumption that querying for the
1487
parents of a node that has already been queried is reasonably cheap.
1488
(eg, not a round trip to a remote host).
1490
# TODO: Often we might ask one searcher for its seen ancestors, and
1491
# then ask another searcher the same question. This can result in
1492
# searching the same revisions repeatedly if the two searchers
1493
# have a lot of overlap.
1494
all_seen = self.seen
1495
pending = set(revisions).intersection(all_seen)
1496
seen_ancestors = set(pending)
1498
if self._returning == 'next':
1499
# self.seen contains what nodes have been returned, not what nodes
1500
# have been queried. We don't want to probe for nodes that haven't
1501
# been searched yet.
1502
not_searched_yet = self._next_query
1504
not_searched_yet = ()
1505
pending.difference_update(not_searched_yet)
1506
get_parent_map = self._parents_provider.get_parent_map
1508
parent_map = get_parent_map(pending)
1510
# We don't care if it is a ghost, since it can't be seen if it is
1512
for parent_ids in parent_map.itervalues():
1513
all_parents.extend(parent_ids)
1514
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1515
seen_ancestors.update(next_pending)
1516
next_pending.difference_update(not_searched_yet)
1517
pending = next_pending
1519
return seen_ancestors
1521
def stop_searching_any(self, revisions):
1523
Remove any of the specified revisions from the search list.
1525
None of the specified revisions are required to be present in the
1528
It is okay to call stop_searching_any() for revisions which were seen
1529
in previous iterations. It is the callers responsibility to call
1530
find_seen_ancestors() to make sure that current search tips that are
1531
ancestors of those revisions are also stopped. All explicitly stopped
1532
revisions will be excluded from the search result's get_keys(), though.
1534
# TODO: does this help performance?
1537
revisions = frozenset(revisions)
1538
if self._returning == 'next':
1539
stopped = self._next_query.intersection(revisions)
1540
self._next_query = self._next_query.difference(revisions)
1542
stopped_present = self._current_present.intersection(revisions)
1543
stopped = stopped_present.union(
1544
self._current_ghosts.intersection(revisions))
1545
self._current_present.difference_update(stopped)
1546
self._current_ghosts.difference_update(stopped)
1547
# stopping 'x' should stop returning parents of 'x', but
1548
# not if 'y' always references those same parents
1549
stop_rev_references = {}
1550
for rev in stopped_present:
1551
for parent_id in self._current_parents[rev]:
1552
if parent_id not in stop_rev_references:
1553
stop_rev_references[parent_id] = 0
1554
stop_rev_references[parent_id] += 1
1555
# if only the stopped revisions reference it, the ref count will be
1557
for parents in self._current_parents.itervalues():
1558
for parent_id in parents:
1560
stop_rev_references[parent_id] -= 1
1563
stop_parents = set()
1564
for rev_id, refs in stop_rev_references.iteritems():
1566
stop_parents.add(rev_id)
1567
self._next_query.difference_update(stop_parents)
1568
self._stopped_keys.update(stopped)
1569
self._stopped_keys.update(revisions)
1572
def start_searching(self, revisions):
1573
"""Add revisions to the search.
1575
The parents of revisions will be returned from the next call to next()
1576
or next_with_ghosts(). If next_with_ghosts was the most recently used
1577
next* call then the return value is the result of looking up the
1578
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1580
revisions = frozenset(revisions)
1581
self._started_keys.update(revisions)
1582
new_revisions = revisions.difference(self.seen)
1583
if self._returning == 'next':
1584
self._next_query.update(new_revisions)
1585
self.seen.update(new_revisions)
1587
# perform a query on revisions
1588
revs, ghosts, query, parents = self._do_query(revisions)
1589
self._stopped_keys.update(ghosts)
1590
self._current_present.update(revs)
1591
self._current_ghosts.update(ghosts)
1592
self._next_query.update(query)
1593
self._current_parents.update(parents)
1597
def invert_parent_map(parent_map):
1598
"""Given a map from child => parents, create a map of parent=>children"""
1600
for child, parents in parent_map.iteritems():
1602
# Any given parent is likely to have only a small handful
1603
# of children, many will have only one. So we avoid mem overhead of
1604
# a list, in exchange for extra copying of tuples
1605
if p not in child_map:
1606
child_map[p] = (child,)
1608
child_map[p] = child_map[p] + (child,)
1612
def collapse_linear_regions(parent_map):
1613
"""Collapse regions of the graph that are 'linear'.
1619
can be collapsed by removing B and getting::
1623
:param parent_map: A dictionary mapping children to their parents
1624
:return: Another dictionary with 'linear' chains collapsed
1626
# Note: this isn't a strictly minimal collapse. For example:
1634
# Will not have 'D' removed, even though 'E' could fit. Also:
1640
# A and C are both kept because they are edges of the graph. We *could* get
1641
# rid of A if we wanted.
1649
# Will not have any nodes removed, even though you do have an
1650
# 'uninteresting' linear D->B and E->C
1652
for child, parents in parent_map.iteritems():
1653
children.setdefault(child, [])
1655
children.setdefault(p, []).append(child)
1657
orig_children = dict(children)
1659
result = dict(parent_map)
1660
for node in parent_map:
1661
parents = result[node]
1662
if len(parents) == 1:
1663
parent_children = children[parents[0]]
1664
if len(parent_children) != 1:
1665
# This is not the only child
1667
node_children = children[node]
1668
if len(node_children) != 1:
1670
child_parents = result.get(node_children[0], None)
1671
if len(child_parents) != 1:
1672
# This is not its only parent
1674
# The child of this node only points at it, and the parent only has
1675
# this as a child. remove this node, and join the others together
1676
result[node_children[0]] = parents
1677
children[parents[0]] = node_children
1685
class GraphThunkIdsToKeys(object):
1686
"""Forwards calls about 'ids' to be about keys internally."""
1688
def __init__(self, graph):
1691
def topo_sort(self):
1692
return [r for (r,) in self._graph.topo_sort()]
1694
def heads(self, ids):
1695
"""See Graph.heads()"""
1696
as_keys = [(i,) for i in ids]
1697
head_keys = self._graph.heads(as_keys)
1698
return set([h[0] for h in head_keys])
1700
def merge_sort(self, tip_revision):
1701
nodes = self._graph.merge_sort((tip_revision,))
1703
node.key = node.key[0]
1706
def add_node(self, revision, parents):
1707
self._graph.add_node((revision,), [(p,) for p in parents])
1710
_counters = [0,0,0,0,0,0,0]
1712
from bzrlib._known_graph_pyx import KnownGraph
1713
except ImportError, e:
1714
osutils.failed_to_load_extension(e)
1715
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
