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
33
STEP_UNIQUE_SEARCHER_EVERY = 5
35
# DIAGRAM of terminology
45
# In this diagram, relative to G and H:
46
# A, B, C, D, E are common ancestors.
47
# C, D and E are border ancestors, because each has a non-common descendant.
48
# D and E are least common ancestors because none of their descendants are
50
# C is not a least common ancestor because its descendant, E, is a common
53
# The find_unique_lca algorithm will pick A in two steps:
54
# 1. find_lca('G', 'H') => ['D', 'E']
55
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
58
class DictParentsProvider(object):
59
"""A parents provider for Graph objects."""
61
def __init__(self, ancestry):
62
self.ancestry = ancestry
65
return 'DictParentsProvider(%r)' % self.ancestry
67
# Note: DictParentsProvider does not implement get_cached_parent_map
68
# Arguably, the data is clearly cached in memory. However, this class
69
# is mostly used for testing, and it keeps the tests clean to not
72
def get_parent_map(self, keys):
73
"""See StackedParentsProvider.get_parent_map"""
74
ancestry = self.ancestry
75
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
78
class StackedParentsProvider(object):
79
"""A parents provider which stacks (or unions) multiple providers.
81
The providers are queries in the order of the provided parent_providers.
84
def __init__(self, parent_providers):
85
self._parent_providers = parent_providers
88
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
90
def get_parent_map(self, keys):
91
"""Get a mapping of keys => parents
93
A dictionary is returned with an entry for each key present in this
94
source. If this source doesn't have information about a key, it should
97
[NULL_REVISION] is used as the parent of the first user-committed
98
revision. Its parent list is empty.
100
:param keys: An iterable returning keys to check (eg revision_ids)
101
:return: A dictionary mapping each key to its parents
104
remaining = set(keys)
105
# This adds getattr() overhead to each get_parent_map call. However,
106
# this is StackedParentsProvider, which means we're dealing with I/O
107
# (either local indexes, or remote RPCs), so CPU overhead should be
109
for parents_provider in self._parent_providers:
110
get_cached = getattr(parents_provider, 'get_cached_parent_map',
112
if get_cached is None:
114
new_found = get_cached(remaining)
115
found.update(new_found)
116
remaining.difference_update(new_found)
121
for parents_provider in self._parent_providers:
123
new_found = parents_provider.get_parent_map(remaining)
124
except errors.UnsupportedOperation:
126
found.update(new_found)
127
remaining.difference_update(new_found)
133
class CachingParentsProvider(object):
134
"""A parents provider which will cache the revision => parents as a dict.
136
This is useful for providers which have an expensive look up.
138
Either a ParentsProvider or a get_parent_map-like callback may be
139
supplied. If it provides extra un-asked-for parents, they will be cached,
140
but filtered out of get_parent_map.
142
The cache is enabled by default, but may be disabled and re-enabled.
144
def __init__(self, parent_provider=None, get_parent_map=None):
147
:param parent_provider: The ParentProvider to use. It or
148
get_parent_map must be supplied.
149
:param get_parent_map: The get_parent_map callback to use. It or
150
parent_provider must be supplied.
152
self._real_provider = parent_provider
153
if get_parent_map is None:
154
self._get_parent_map = self._real_provider.get_parent_map
156
self._get_parent_map = get_parent_map
158
self.enable_cache(True)
161
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
163
def enable_cache(self, cache_misses=True):
165
if self._cache is not None:
166
raise AssertionError('Cache enabled when already enabled.')
168
self._cache_misses = cache_misses
169
self.missing_keys = set()
171
def disable_cache(self):
172
"""Disable and clear the cache."""
174
self._cache_misses = None
175
self.missing_keys = set()
177
def get_cached_map(self):
178
"""Return any cached get_parent_map values."""
179
if self._cache is None:
181
return dict(self._cache)
183
def get_cached_parent_map(self, keys):
184
"""Return items from the cache.
186
This returns the same info as get_parent_map, but explicitly does not
187
invoke the supplied ParentsProvider to search for uncached values.
192
return dict([(key, cache[key]) for key in keys if key in cache])
194
def get_parent_map(self, keys):
195
"""See StackedParentsProvider.get_parent_map."""
198
cache = self._get_parent_map(keys)
200
needed_revisions = set(key for key in keys if key not in cache)
201
# Do not ask for negatively cached keys
202
needed_revisions.difference_update(self.missing_keys)
204
parent_map = self._get_parent_map(needed_revisions)
205
cache.update(parent_map)
206
if self._cache_misses:
207
for key in needed_revisions:
208
if key not in parent_map:
209
self.note_missing_key(key)
212
value = cache.get(key)
213
if value is not None:
217
def note_missing_key(self, key):
218
"""Note that key is a missing key."""
219
if self._cache_misses:
220
self.missing_keys.add(key)
223
class CallableToParentsProviderAdapter(object):
224
"""A parents provider that adapts any callable to the parents provider API.
226
i.e. it accepts calls to self.get_parent_map and relays them to the
227
callable it was constructed with.
230
def __init__(self, a_callable):
231
self.callable = a_callable
234
return "%s(%r)" % (self.__class__.__name__, self.callable)
236
def get_parent_map(self, keys):
237
return self.callable(keys)
241
"""Provide incremental access to revision graphs.
243
This is the generic implementation; it is intended to be subclassed to
244
specialize it for other repository types.
247
def __init__(self, parents_provider):
248
"""Construct a Graph that uses several graphs as its input
250
This should not normally be invoked directly, because there may be
251
specialized implementations for particular repository types. See
252
Repository.get_graph().
254
:param parents_provider: An object providing a get_parent_map call
255
conforming to the behavior of
256
StackedParentsProvider.get_parent_map.
258
if getattr(parents_provider, 'get_parents', None) is not None:
259
self.get_parents = parents_provider.get_parents
260
if getattr(parents_provider, 'get_parent_map', None) is not None:
261
self.get_parent_map = parents_provider.get_parent_map
262
self._parents_provider = parents_provider
265
return 'Graph(%r)' % self._parents_provider
267
def find_lca(self, *revisions):
268
"""Determine the lowest common ancestors of the provided revisions
270
A lowest common ancestor is a common ancestor none of whose
271
descendants are common ancestors. In graphs, unlike trees, there may
272
be multiple lowest common ancestors.
274
This algorithm has two phases. Phase 1 identifies border ancestors,
275
and phase 2 filters border ancestors to determine lowest common
278
In phase 1, border ancestors are identified, using a breadth-first
279
search starting at the bottom of the graph. Searches are stopped
280
whenever a node or one of its descendants is determined to be common
282
In phase 2, the border ancestors are filtered to find the least
283
common ancestors. This is done by searching the ancestries of each
286
Phase 2 is perfomed on the principle that a border ancestor that is
287
not an ancestor of any other border ancestor is a least common
290
Searches are stopped when they find a node that is determined to be a
291
common ancestor of all border ancestors, because this shows that it
292
cannot be a descendant of any border ancestor.
294
The scaling of this operation should be proportional to:
296
1. The number of uncommon ancestors
297
2. The number of border ancestors
298
3. The length of the shortest path between a border ancestor and an
299
ancestor of all border ancestors.
301
border_common, common, sides = self._find_border_ancestors(revisions)
302
# We may have common ancestors that can be reached from each other.
303
# - ask for the heads of them to filter it down to only ones that
304
# cannot be reached from each other - phase 2.
305
return self.heads(border_common)
307
def find_difference(self, left_revision, right_revision):
308
"""Determine the graph difference between two revisions"""
309
border, common, searchers = self._find_border_ancestors(
310
[left_revision, right_revision])
311
self._search_for_extra_common(common, searchers)
312
left = searchers[0].seen
313
right = searchers[1].seen
314
return (left.difference(right), right.difference(left))
316
def find_descendants(self, old_key, new_key):
317
"""Find descendants of old_key that are ancestors of new_key."""
318
child_map = self.get_child_map(self._find_descendant_ancestors(
320
graph = Graph(DictParentsProvider(child_map))
321
searcher = graph._make_breadth_first_searcher([old_key])
325
def _find_descendant_ancestors(self, old_key, new_key):
326
"""Find ancestors of new_key that may be descendants of old_key."""
327
stop = self._make_breadth_first_searcher([old_key])
328
descendants = self._make_breadth_first_searcher([new_key])
329
for revisions in descendants:
330
old_stop = stop.seen.intersection(revisions)
331
descendants.stop_searching_any(old_stop)
332
seen_stop = descendants.find_seen_ancestors(stop.step())
333
descendants.stop_searching_any(seen_stop)
334
return descendants.seen.difference(stop.seen)
336
def get_child_map(self, keys):
337
"""Get a mapping from parents to children of the specified keys.
339
This is simply the inversion of get_parent_map. Only supplied keys
340
will be discovered as children.
341
:return: a dict of key:child_list for keys.
343
parent_map = self._parents_provider.get_parent_map(keys)
345
for child, parents in sorted(viewitems(parent_map)):
346
for parent in parents:
347
parent_child.setdefault(parent, []).append(child)
350
def find_distance_to_null(self, target_revision_id, known_revision_ids):
351
"""Find the left-hand distance to the NULL_REVISION.
353
(This can also be considered the revno of a branch at
356
:param target_revision_id: A revision_id which we would like to know
358
:param known_revision_ids: [(revision_id, revno)] A list of known
359
revno, revision_id tuples. We'll use this to seed the search.
361
# Map from revision_ids to a known value for their revno
362
known_revnos = dict(known_revision_ids)
363
cur_tip = target_revision_id
365
NULL_REVISION = revision.NULL_REVISION
366
known_revnos[NULL_REVISION] = 0
368
searching_known_tips = list(known_revnos)
370
unknown_searched = {}
372
while cur_tip not in known_revnos:
373
unknown_searched[cur_tip] = num_steps
375
to_search = {cur_tip}
376
to_search.update(searching_known_tips)
377
parent_map = self.get_parent_map(to_search)
378
parents = parent_map.get(cur_tip, None)
379
if not parents: # An empty list or None is a ghost
380
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
384
for revision_id in searching_known_tips:
385
parents = parent_map.get(revision_id, None)
389
next_revno = known_revnos[revision_id] - 1
390
if next in unknown_searched:
391
# We have enough information to return a value right now
392
return next_revno + unknown_searched[next]
393
if next in known_revnos:
395
known_revnos[next] = next_revno
396
next_known_tips.append(next)
397
searching_known_tips = next_known_tips
399
# We reached a known revision, so just add in how many steps it took to
401
return known_revnos[cur_tip] + num_steps
403
def find_lefthand_distances(self, keys):
404
"""Find the distance to null for all the keys in keys.
406
:param keys: keys to lookup.
407
:return: A dict key->distance for all of keys.
409
# Optimisable by concurrent searching, but a random spread should get
410
# some sort of hit rate.
417
(key, self.find_distance_to_null(key, known_revnos)))
418
except errors.GhostRevisionsHaveNoRevno:
421
known_revnos.append((key, -1))
422
return dict(known_revnos)
424
def find_unique_ancestors(self, unique_revision, common_revisions):
425
"""Find the unique ancestors for a revision versus others.
427
This returns the ancestry of unique_revision, excluding all revisions
428
in the ancestry of common_revisions. If unique_revision is in the
429
ancestry, then the empty set will be returned.
431
:param unique_revision: The revision_id whose ancestry we are
433
(XXX: Would this API be better if we allowed multiple revisions on
434
to be searched here?)
435
:param common_revisions: Revision_ids of ancestries to exclude.
436
:return: A set of revisions in the ancestry of unique_revision
438
if unique_revision in common_revisions:
441
# Algorithm description
442
# 1) Walk backwards from the unique node and all common nodes.
443
# 2) When a node is seen by both sides, stop searching it in the unique
444
# walker, include it in the common walker.
445
# 3) Stop searching when there are no nodes left for the unique walker.
446
# At this point, you have a maximal set of unique nodes. Some of
447
# them may actually be common, and you haven't reached them yet.
448
# 4) Start new searchers for the unique nodes, seeded with the
449
# information you have so far.
450
# 5) Continue searching, stopping the common searches when the search
451
# tip is an ancestor of all unique nodes.
452
# 6) Aggregate together unique searchers when they are searching the
453
# same tips. When all unique searchers are searching the same node,
454
# stop move it to a single 'all_unique_searcher'.
455
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
456
# Most of the time this produces very little important information.
457
# So don't step it as quickly as the other searchers.
458
# 8) Search is done when all common searchers have completed.
460
unique_searcher, common_searcher = self._find_initial_unique_nodes(
461
[unique_revision], common_revisions)
463
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
467
(all_unique_searcher,
468
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
469
unique_searcher, common_searcher)
471
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
472
unique_tip_searchers, common_searcher)
473
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
474
if 'graph' in debug.debug_flags:
475
trace.mutter('Found %d truly unique nodes out of %d',
476
len(true_unique_nodes), len(unique_nodes))
477
return true_unique_nodes
479
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
480
"""Steps 1-3 of find_unique_ancestors.
482
Find the maximal set of unique nodes. Some of these might actually
483
still be common, but we are sure that there are no other unique nodes.
485
:return: (unique_searcher, common_searcher)
488
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
489
# we know that unique_revisions aren't in common_revisions, so skip
491
next(unique_searcher)
492
common_searcher = self._make_breadth_first_searcher(common_revisions)
494
# As long as we are still finding unique nodes, keep searching
495
while unique_searcher._next_query:
496
next_unique_nodes = set(unique_searcher.step())
497
next_common_nodes = set(common_searcher.step())
499
# Check if either searcher encounters new nodes seen by the other
501
unique_are_common_nodes = next_unique_nodes.intersection(
502
common_searcher.seen)
503
unique_are_common_nodes.update(
504
next_common_nodes.intersection(unique_searcher.seen))
505
if unique_are_common_nodes:
506
ancestors = unique_searcher.find_seen_ancestors(
507
unique_are_common_nodes)
508
# TODO: This is a bit overboard, we only really care about
509
# the ancestors of the tips because the rest we
510
# already know. This is *correct* but causes us to
511
# search too much ancestry.
512
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
513
unique_searcher.stop_searching_any(ancestors)
514
common_searcher.start_searching(ancestors)
516
return unique_searcher, common_searcher
518
def _make_unique_searchers(self, unique_nodes, unique_searcher,
520
"""Create a searcher for all the unique search tips (step 4).
522
As a side effect, the common_searcher will stop searching any nodes
523
that are ancestors of the unique searcher tips.
525
:return: (all_unique_searcher, unique_tip_searchers)
527
unique_tips = self._remove_simple_descendants(unique_nodes,
528
self.get_parent_map(unique_nodes))
530
if len(unique_tips) == 1:
531
unique_tip_searchers = []
532
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
534
unique_tip_searchers = []
535
for tip in unique_tips:
536
revs_to_search = unique_searcher.find_seen_ancestors([tip])
537
revs_to_search.update(
538
common_searcher.find_seen_ancestors(revs_to_search))
539
searcher = self._make_breadth_first_searcher(revs_to_search)
540
# We don't care about the starting nodes.
541
searcher._label = tip
543
unique_tip_searchers.append(searcher)
545
ancestor_all_unique = None
546
for searcher in unique_tip_searchers:
547
if ancestor_all_unique is None:
548
ancestor_all_unique = set(searcher.seen)
550
ancestor_all_unique = ancestor_all_unique.intersection(
552
# Collapse all the common nodes into a single searcher
553
all_unique_searcher = self._make_breadth_first_searcher(
555
if ancestor_all_unique:
556
# We've seen these nodes in all the searchers, so we'll just go to
558
all_unique_searcher.step()
560
# Stop any search tips that are already known as ancestors of the
562
stopped_common = common_searcher.stop_searching_any(
563
common_searcher.find_seen_ancestors(ancestor_all_unique))
566
for searcher in unique_tip_searchers:
567
total_stopped += len(searcher.stop_searching_any(
568
searcher.find_seen_ancestors(ancestor_all_unique)))
569
if 'graph' in debug.debug_flags:
570
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
571
' (%d stopped search tips, %d common ancestors'
572
' (%d stopped common)',
573
len(unique_nodes), len(unique_tip_searchers),
574
total_stopped, len(ancestor_all_unique),
576
return all_unique_searcher, unique_tip_searchers
578
def _step_unique_and_common_searchers(self, common_searcher,
579
unique_tip_searchers,
581
"""Step all the searchers"""
582
newly_seen_common = set(common_searcher.step())
583
newly_seen_unique = set()
584
for searcher in unique_tip_searchers:
585
next = set(searcher.step())
586
next.update(unique_searcher.find_seen_ancestors(next))
587
next.update(common_searcher.find_seen_ancestors(next))
588
for alt_searcher in unique_tip_searchers:
589
if alt_searcher is searcher:
591
next.update(alt_searcher.find_seen_ancestors(next))
592
searcher.start_searching(next)
593
newly_seen_unique.update(next)
594
return newly_seen_common, newly_seen_unique
596
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
598
newly_seen_unique, step_all_unique):
599
"""Find nodes that are common to all unique_tip_searchers.
601
If it is time, step the all_unique_searcher, and add its nodes to the
604
common_to_all_unique_nodes = newly_seen_unique.copy()
605
for searcher in unique_tip_searchers:
606
common_to_all_unique_nodes.intersection_update(searcher.seen)
607
common_to_all_unique_nodes.intersection_update(
608
all_unique_searcher.seen)
609
# Step all-unique less frequently than the other searchers.
610
# In the common case, we don't need to spider out far here, so
611
# avoid doing extra work.
613
tstart = time.clock()
614
nodes = all_unique_searcher.step()
615
common_to_all_unique_nodes.update(nodes)
616
if 'graph' in debug.debug_flags:
617
tdelta = time.clock() - tstart
618
trace.mutter('all_unique_searcher step() took %.3fs'
619
'for %d nodes (%d total), iteration: %s',
620
tdelta, len(nodes), len(all_unique_searcher.seen),
621
all_unique_searcher._iterations)
622
return common_to_all_unique_nodes
624
def _collapse_unique_searchers(self, unique_tip_searchers,
625
common_to_all_unique_nodes):
626
"""Combine searchers that are searching the same tips.
628
When two searchers are searching the same tips, we can stop one of the
629
searchers. We also know that the maximal set of common ancestors is the
630
intersection of the two original searchers.
632
:return: A list of searchers that are searching unique nodes.
634
# Filter out searchers that don't actually search different
635
# nodes. We already have the ancestry intersection for them
636
unique_search_tips = {}
637
for searcher in unique_tip_searchers:
638
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
639
will_search_set = frozenset(searcher._next_query)
640
if not will_search_set:
641
if 'graph' in debug.debug_flags:
642
trace.mutter('Unique searcher %s was stopped.'
643
' (%s iterations) %d nodes stopped',
645
searcher._iterations,
647
elif will_search_set not in unique_search_tips:
648
# This searcher is searching a unique set of nodes, let it
649
unique_search_tips[will_search_set] = [searcher]
651
unique_search_tips[will_search_set].append(searcher)
652
# TODO: it might be possible to collapse searchers faster when they
653
# only have *some* search tips in common.
654
next_unique_searchers = []
655
for searchers in viewvalues(unique_search_tips):
656
if len(searchers) == 1:
657
# Searching unique tips, go for it
658
next_unique_searchers.append(searchers[0])
660
# These searchers have started searching the same tips, we
661
# don't need them to cover the same ground. The
662
# intersection of their ancestry won't change, so create a
663
# new searcher, combining their histories.
664
next_searcher = searchers[0]
665
for searcher in searchers[1:]:
666
next_searcher.seen.intersection_update(searcher.seen)
667
if 'graph' in debug.debug_flags:
668
trace.mutter('Combining %d searchers into a single'
669
' searcher searching %d nodes with'
672
len(next_searcher._next_query),
673
len(next_searcher.seen))
674
next_unique_searchers.append(next_searcher)
675
return next_unique_searchers
677
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
678
unique_tip_searchers, common_searcher):
679
"""Steps 5-8 of find_unique_ancestors.
681
This function returns when common_searcher has stopped searching for
684
# We step the ancestor_all_unique searcher only every
685
# STEP_UNIQUE_SEARCHER_EVERY steps.
686
step_all_unique_counter = 0
687
# While we still have common nodes to search
688
while common_searcher._next_query:
690
newly_seen_unique) = self._step_unique_and_common_searchers(
691
common_searcher, unique_tip_searchers, unique_searcher)
692
# These nodes are common ancestors of all unique nodes
693
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
694
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
695
step_all_unique_counter==0)
696
step_all_unique_counter = ((step_all_unique_counter + 1)
697
% STEP_UNIQUE_SEARCHER_EVERY)
699
if newly_seen_common:
700
# If a 'common' node is an ancestor of all unique searchers, we
701
# can stop searching it.
702
common_searcher.stop_searching_any(
703
all_unique_searcher.seen.intersection(newly_seen_common))
704
if common_to_all_unique_nodes:
705
common_to_all_unique_nodes.update(
706
common_searcher.find_seen_ancestors(
707
common_to_all_unique_nodes))
708
# The all_unique searcher can start searching the common nodes
709
# but everyone else can stop.
710
# This is the sort of thing where we would like to not have it
711
# start_searching all of the nodes, but only mark all of them
712
# as seen, and have it search only the actual tips. Otherwise
713
# it is another get_parent_map() traversal for it to figure out
714
# what we already should know.
715
all_unique_searcher.start_searching(common_to_all_unique_nodes)
716
common_searcher.stop_searching_any(common_to_all_unique_nodes)
718
next_unique_searchers = self._collapse_unique_searchers(
719
unique_tip_searchers, common_to_all_unique_nodes)
720
if len(unique_tip_searchers) != len(next_unique_searchers):
721
if 'graph' in debug.debug_flags:
722
trace.mutter('Collapsed %d unique searchers => %d'
724
len(unique_tip_searchers),
725
len(next_unique_searchers),
726
all_unique_searcher._iterations)
727
unique_tip_searchers = next_unique_searchers
729
def get_parent_map(self, revisions):
730
"""Get a map of key:parent_list for revisions.
732
This implementation delegates to get_parents, for old parent_providers
733
that do not supply get_parent_map.
736
for rev, parents in self.get_parents(revisions):
737
if parents is not None:
738
result[rev] = parents
741
def _make_breadth_first_searcher(self, revisions):
742
return _BreadthFirstSearcher(revisions, self)
744
def _find_border_ancestors(self, revisions):
745
"""Find common ancestors with at least one uncommon descendant.
747
Border ancestors are identified using a breadth-first
748
search starting at the bottom of the graph. Searches are stopped
749
whenever a node or one of its descendants is determined to be common.
751
This will scale with the number of uncommon ancestors.
753
As well as the border ancestors, a set of seen common ancestors and a
754
list of sets of seen ancestors for each input revision is returned.
755
This allows calculation of graph difference from the results of this
758
if None in revisions:
759
raise errors.InvalidRevisionId(None, self)
760
common_ancestors = set()
761
searchers = [self._make_breadth_first_searcher([r])
763
active_searchers = searchers[:]
764
border_ancestors = set()
768
for searcher in searchers:
769
new_ancestors = searcher.step()
771
newly_seen.update(new_ancestors)
773
for revision in newly_seen:
774
if revision in common_ancestors:
775
# Not a border ancestor because it was seen as common
777
new_common.add(revision)
779
for searcher in searchers:
780
if revision not in searcher.seen:
783
# This is a border because it is a first common that we see
784
# after walking for a while.
785
border_ancestors.add(revision)
786
new_common.add(revision)
788
for searcher in searchers:
789
new_common.update(searcher.find_seen_ancestors(new_common))
790
for searcher in searchers:
791
searcher.start_searching(new_common)
792
common_ancestors.update(new_common)
794
# Figure out what the searchers will be searching next, and if
795
# there is only 1 set being searched, then we are done searching,
796
# since all searchers would have to be searching the same data,
797
# thus it *must* be in common.
798
unique_search_sets = set()
799
for searcher in searchers:
800
will_search_set = frozenset(searcher._next_query)
801
if will_search_set not in unique_search_sets:
802
# This searcher is searching a unique set of nodes, let it
803
unique_search_sets.add(will_search_set)
805
if len(unique_search_sets) == 1:
806
nodes = unique_search_sets.pop()
807
uncommon_nodes = nodes.difference(common_ancestors)
809
raise AssertionError("Somehow we ended up converging"
810
" without actually marking them as"
813
"\nuncommon_nodes: %s"
814
% (revisions, uncommon_nodes))
816
return border_ancestors, common_ancestors, searchers
818
def heads(self, keys):
819
"""Return the heads from amongst keys.
821
This is done by searching the ancestries of each key. Any key that is
822
reachable from another key is not returned; all the others are.
824
This operation scales with the relative depth between any two keys. If
825
any two keys are completely disconnected all ancestry of both sides
828
:param keys: An iterable of keys.
829
:return: A set of the heads. Note that as a set there is no ordering
830
information. Callers will need to filter their input to create
831
order if they need it.
833
candidate_heads = set(keys)
834
if revision.NULL_REVISION in candidate_heads:
835
# NULL_REVISION is only a head if it is the only entry
836
candidate_heads.remove(revision.NULL_REVISION)
837
if not candidate_heads:
838
return {revision.NULL_REVISION}
839
if len(candidate_heads) < 2:
840
return candidate_heads
841
searchers = dict((c, self._make_breadth_first_searcher([c]))
842
for c in candidate_heads)
843
active_searchers = dict(searchers)
844
# skip over the actual candidate for each searcher
845
for searcher in viewvalues(active_searchers):
847
# The common walker finds nodes that are common to two or more of the
848
# input keys, so that we don't access all history when a currently
849
# uncommon search point actually meets up with something behind a
850
# common search point. Common search points do not keep searches
851
# active; they just allow us to make searches inactive without
852
# accessing all history.
853
common_walker = self._make_breadth_first_searcher([])
854
while len(active_searchers) > 0:
859
except StopIteration:
860
# No common points being searched at this time.
862
for candidate in list(active_searchers):
864
searcher = active_searchers[candidate]
866
# rare case: we deleted candidate in a previous iteration
867
# through this for loop, because it was determined to be
868
# a descendant of another candidate.
871
ancestors.update(next(searcher))
872
except StopIteration:
873
del active_searchers[candidate]
875
# process found nodes
877
for ancestor in ancestors:
878
if ancestor in candidate_heads:
879
candidate_heads.remove(ancestor)
880
del searchers[ancestor]
881
if ancestor in active_searchers:
882
del active_searchers[ancestor]
883
# it may meet up with a known common node
884
if ancestor in common_walker.seen:
885
# some searcher has encountered our known common nodes:
887
ancestor_set = {ancestor}
888
for searcher in viewvalues(searchers):
889
searcher.stop_searching_any(ancestor_set)
891
# or it may have been just reached by all the searchers:
892
for searcher in viewvalues(searchers):
893
if ancestor not in searcher.seen:
896
# The final active searcher has just reached this node,
897
# making it be known as a descendant of all candidates,
898
# so we can stop searching it, and any seen ancestors
899
new_common.add(ancestor)
900
for searcher in viewvalues(searchers):
902
searcher.find_seen_ancestors([ancestor])
903
searcher.stop_searching_any(seen_ancestors)
904
common_walker.start_searching(new_common)
905
return candidate_heads
907
def find_merge_order(self, tip_revision_id, lca_revision_ids):
908
"""Find the order that each revision was merged into tip.
910
This basically just walks backwards with a stack, and walks left-first
911
until it finds a node to stop.
913
if len(lca_revision_ids) == 1:
914
return list(lca_revision_ids)
915
looking_for = set(lca_revision_ids)
916
# TODO: Is there a way we could do this "faster" by batching up the
917
# get_parent_map requests?
918
# TODO: Should we also be culling the ancestry search right away? We
919
# could add looking_for to the "stop" list, and walk their
920
# ancestry in batched mode. The flip side is it might mean we walk a
921
# lot of "stop" nodes, rather than only the minimum.
922
# Then again, without it we may trace back into ancestry we could have
924
stack = [tip_revision_id]
927
while stack and looking_for:
930
if next in looking_for:
932
looking_for.remove(next)
933
if len(looking_for) == 1:
934
found.append(looking_for.pop())
937
parent_ids = self.get_parent_map([next]).get(next, None)
938
if not parent_ids: # Ghost, nothing to search here
940
for parent_id in reversed(parent_ids):
941
# TODO: (performance) We see the parent at this point, but we
942
# wait to mark it until later to make sure we get left
943
# parents before right parents. However, instead of
944
# waiting until we have traversed enough parents, we
945
# could instead note that we've found it, and once all
946
# parents are in the stack, just reverse iterate the
948
if parent_id not in stop:
949
# this will need to be searched
950
stack.append(parent_id)
954
def find_lefthand_merger(self, merged_key, tip_key):
955
"""Find the first lefthand ancestor of tip_key that merged merged_key.
957
We do this by first finding the descendants of merged_key, then
958
walking through the lefthand ancestry of tip_key until we find a key
959
that doesn't descend from merged_key. Its child is the key that
962
:return: The first lefthand ancestor of tip_key to merge merged_key.
963
merged_key if it is a lefthand ancestor of tip_key.
964
None if no ancestor of tip_key merged merged_key.
966
descendants = self.find_descendants(merged_key, tip_key)
967
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
968
last_candidate = None
969
for candidate in candidate_iterator:
970
if candidate not in descendants:
971
return last_candidate
972
last_candidate = candidate
974
def find_unique_lca(self, left_revision, right_revision,
976
"""Find a unique LCA.
978
Find lowest common ancestors. If there is no unique common
979
ancestor, find the lowest common ancestors of those ancestors.
981
Iteration stops when a unique lowest common ancestor is found.
982
The graph origin is necessarily a unique lowest common ancestor.
984
Note that None is not an acceptable substitute for NULL_REVISION.
985
in the input for this method.
987
:param count_steps: If True, the return value will be a tuple of
988
(unique_lca, steps) where steps is the number of times that
989
find_lca was run. If False, only unique_lca is returned.
991
revisions = [left_revision, right_revision]
995
lca = self.find_lca(*revisions)
1003
raise errors.NoCommonAncestor(left_revision, right_revision)
1006
def iter_ancestry(self, revision_ids):
1007
"""Iterate the ancestry of this revision.
1009
:param revision_ids: Nodes to start the search
1010
:return: Yield tuples mapping a revision_id to its parents for the
1011
ancestry of revision_id.
1012
Ghosts will be returned with None as their parents, and nodes
1013
with no parents will have NULL_REVISION as their only parent. (As
1014
defined by get_parent_map.)
1015
There will also be a node for (NULL_REVISION, ())
1017
pending = set(revision_ids)
1020
processed.update(pending)
1021
next_map = self.get_parent_map(pending)
1022
next_pending = set()
1023
for item in viewitems(next_map):
1025
next_pending.update(p for p in item[1] if p not in processed)
1026
ghosts = pending.difference(next_map)
1027
for ghost in ghosts:
1029
pending = next_pending
1031
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1032
if stop_keys is None:
1034
next_key = start_key
1035
def get_parents(key):
1037
return self._parents_provider.get_parent_map([key])[key]
1039
raise errors.RevisionNotPresent(next_key, self)
1041
if next_key in stop_keys:
1043
parents = get_parents(next_key)
1045
if len(parents) == 0:
1048
next_key = parents[0]
1050
def iter_topo_order(self, revisions):
1051
"""Iterate through the input revisions in topological order.
1053
This sorting only ensures that parents come before their children.
1054
An ancestor may sort after a descendant if the relationship is not
1055
visible in the supplied list of revisions.
1057
from breezy import tsort
1058
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1059
return sorter.iter_topo_order()
1061
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1062
"""Determine whether a revision is an ancestor of another.
1064
We answer this using heads() as heads() has the logic to perform the
1065
smallest number of parent lookups to determine the ancestral
1066
relationship between N revisions.
1068
return {candidate_descendant} == self.heads(
1069
[candidate_ancestor, candidate_descendant])
1071
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1072
"""Determine whether a revision is between two others.
1074
returns true if and only if:
1075
lower_bound_revid <= revid <= upper_bound_revid
1077
return ((upper_bound_revid is None or
1078
self.is_ancestor(revid, upper_bound_revid)) and
1079
(lower_bound_revid is None or
1080
self.is_ancestor(lower_bound_revid, revid)))
1082
def _search_for_extra_common(self, common, searchers):
1083
"""Make sure that unique nodes are genuinely unique.
1085
After _find_border_ancestors, all nodes marked "common" are indeed
1086
common. Some of the nodes considered unique are not, due to history
1087
shortcuts stopping the searches early.
1089
We know that we have searched enough when all common search tips are
1090
descended from all unique (uncommon) nodes because we know that a node
1091
cannot be an ancestor of its own ancestor.
1093
:param common: A set of common nodes
1094
:param searchers: The searchers returned from _find_border_ancestors
1097
# Basic algorithm...
1098
# A) The passed in searchers should all be on the same tips, thus
1099
# they should be considered the "common" searchers.
1100
# B) We find the difference between the searchers, these are the
1101
# "unique" nodes for each side.
1102
# C) We do a quick culling so that we only start searching from the
1103
# more interesting unique nodes. (A unique ancestor is more
1104
# interesting than any of its children.)
1105
# D) We start searching for ancestors common to all unique nodes.
1106
# E) We have the common searchers stop searching any ancestors of
1107
# nodes found by (D)
1108
# F) When there are no more common search tips, we stop
1110
# TODO: We need a way to remove unique_searchers when they overlap with
1111
# other unique searchers.
1112
if len(searchers) != 2:
1113
raise NotImplementedError(
1114
"Algorithm not yet implemented for > 2 searchers")
1115
common_searchers = searchers
1116
left_searcher = searchers[0]
1117
right_searcher = searchers[1]
1118
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1119
if not unique: # No unique nodes, nothing to do
1121
total_unique = len(unique)
1122
unique = self._remove_simple_descendants(unique,
1123
self.get_parent_map(unique))
1124
simple_unique = len(unique)
1126
unique_searchers = []
1127
for revision_id in unique:
1128
if revision_id in left_searcher.seen:
1129
parent_searcher = left_searcher
1131
parent_searcher = right_searcher
1132
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1133
if not revs_to_search: # XXX: This shouldn't be possible
1134
revs_to_search = [revision_id]
1135
searcher = self._make_breadth_first_searcher(revs_to_search)
1136
# We don't care about the starting nodes.
1138
unique_searchers.append(searcher)
1140
# possible todo: aggregate the common searchers into a single common
1141
# searcher, just make sure that we include the nodes into the .seen
1142
# properties of the original searchers
1144
ancestor_all_unique = None
1145
for searcher in unique_searchers:
1146
if ancestor_all_unique is None:
1147
ancestor_all_unique = set(searcher.seen)
1149
ancestor_all_unique = ancestor_all_unique.intersection(
1152
trace.mutter('Started %s unique searchers for %s unique revisions',
1153
simple_unique, total_unique)
1155
while True: # If we have no more nodes we have nothing to do
1156
newly_seen_common = set()
1157
for searcher in common_searchers:
1158
newly_seen_common.update(searcher.step())
1159
newly_seen_unique = set()
1160
for searcher in unique_searchers:
1161
newly_seen_unique.update(searcher.step())
1162
new_common_unique = set()
1163
for revision in newly_seen_unique:
1164
for searcher in unique_searchers:
1165
if revision not in searcher.seen:
1168
# This is a border because it is a first common that we see
1169
# after walking for a while.
1170
new_common_unique.add(revision)
1171
if newly_seen_common:
1172
# These are nodes descended from one of the 'common' searchers.
1173
# Make sure all searchers are on the same page
1174
for searcher in common_searchers:
1175
newly_seen_common.update(
1176
searcher.find_seen_ancestors(newly_seen_common))
1177
# We start searching the whole ancestry. It is a bit wasteful,
1178
# though. We really just want to mark all of these nodes as
1179
# 'seen' and then start just the tips. However, it requires a
1180
# get_parent_map() call to figure out the tips anyway, and all
1181
# redundant requests should be fairly fast.
1182
for searcher in common_searchers:
1183
searcher.start_searching(newly_seen_common)
1185
# If a 'common' node is an ancestor of all unique searchers, we
1186
# can stop searching it.
1187
stop_searching_common = ancestor_all_unique.intersection(
1189
if stop_searching_common:
1190
for searcher in common_searchers:
1191
searcher.stop_searching_any(stop_searching_common)
1192
if new_common_unique:
1193
# We found some ancestors that are common
1194
for searcher in unique_searchers:
1195
new_common_unique.update(
1196
searcher.find_seen_ancestors(new_common_unique))
1197
# Since these are common, we can grab another set of ancestors
1199
for searcher in common_searchers:
1200
new_common_unique.update(
1201
searcher.find_seen_ancestors(new_common_unique))
1203
# We can tell all of the unique searchers to start at these
1204
# nodes, and tell all of the common searchers to *stop*
1205
# searching these nodes
1206
for searcher in unique_searchers:
1207
searcher.start_searching(new_common_unique)
1208
for searcher in common_searchers:
1209
searcher.stop_searching_any(new_common_unique)
1210
ancestor_all_unique.update(new_common_unique)
1212
# Filter out searchers that don't actually search different
1213
# nodes. We already have the ancestry intersection for them
1214
next_unique_searchers = []
1215
unique_search_sets = set()
1216
for searcher in unique_searchers:
1217
will_search_set = frozenset(searcher._next_query)
1218
if will_search_set not in unique_search_sets:
1219
# This searcher is searching a unique set of nodes, let it
1220
unique_search_sets.add(will_search_set)
1221
next_unique_searchers.append(searcher)
1222
unique_searchers = next_unique_searchers
1223
for searcher in common_searchers:
1224
if searcher._next_query:
1227
# All common searcher have stopped searching
1230
def _remove_simple_descendants(self, revisions, parent_map):
1231
"""remove revisions which are children of other ones in the set
1233
This doesn't do any graph searching, it just checks the immediate
1234
parent_map to find if there are any children which can be removed.
1236
:param revisions: A set of revision_ids
1237
:return: A set of revision_ids with the children removed
1239
simple_ancestors = revisions.copy()
1240
# TODO: jam 20071214 we *could* restrict it to searching only the
1241
# parent_map of revisions already present in 'revisions', but
1242
# considering the general use case, I think this is actually
1245
# This is the same as the following loop. I don't know that it is any
1247
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1248
## if p_ids is not None and revisions.intersection(p_ids))
1249
## return simple_ancestors
1251
# Yet Another Way, invert the parent map (which can be cached)
1253
## for revision_id, parent_ids in parent_map.iteritems():
1254
## for p_id in parent_ids:
1255
## descendants.setdefault(p_id, []).append(revision_id)
1256
## for revision in revisions.intersection(descendants):
1257
## simple_ancestors.difference_update(descendants[revision])
1258
## return simple_ancestors
1259
for revision, parent_ids in viewitems(parent_map):
1260
if parent_ids is None:
1262
for parent_id in parent_ids:
1263
if parent_id in revisions:
1264
# This node has a parent present in the set, so we can
1266
simple_ancestors.discard(revision)
1268
return simple_ancestors
1271
class HeadsCache(object):
1272
"""A cache of results for graph heads calls."""
1274
def __init__(self, graph):
1278
def heads(self, keys):
1279
"""Return the heads of keys.
1281
This matches the API of Graph.heads(), specifically the return value is
1282
a set which can be mutated, and ordering of the input is not preserved
1285
:see also: Graph.heads.
1286
:param keys: The keys to calculate heads for.
1287
:return: A set containing the heads, which may be mutated without
1288
affecting future lookups.
1290
keys = frozenset(keys)
1292
return set(self._heads[keys])
1294
heads = self.graph.heads(keys)
1295
self._heads[keys] = heads
1299
class FrozenHeadsCache(object):
1300
"""Cache heads() calls, assuming the caller won't modify them."""
1302
def __init__(self, graph):
1306
def heads(self, keys):
1307
"""Return the heads of keys.
1309
Similar to Graph.heads(). The main difference is that the return value
1310
is a frozen set which cannot be mutated.
1312
:see also: Graph.heads.
1313
:param keys: The keys to calculate heads for.
1314
:return: A frozenset containing the heads.
1316
keys = frozenset(keys)
1318
return self._heads[keys]
1320
heads = frozenset(self.graph.heads(keys))
1321
self._heads[keys] = heads
1324
def cache(self, keys, heads):
1325
"""Store a known value."""
1326
self._heads[frozenset(keys)] = frozenset(heads)
1329
class _BreadthFirstSearcher(object):
1330
"""Parallel search breadth-first the ancestry of revisions.
1332
This class implements the iterator protocol, but additionally
1333
1. provides a set of seen ancestors, and
1334
2. allows some ancestries to be unsearched, via stop_searching_any
1337
def __init__(self, revisions, parents_provider):
1338
self._iterations = 0
1339
self._next_query = set(revisions)
1341
self._started_keys = set(self._next_query)
1342
self._stopped_keys = set()
1343
self._parents_provider = parents_provider
1344
self._returning = 'next_with_ghosts'
1345
self._current_present = set()
1346
self._current_ghosts = set()
1347
self._current_parents = {}
1350
if self._iterations:
1351
prefix = "searching"
1354
search = '%s=%r' % (prefix, list(self._next_query))
1355
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1356
' seen=%r)' % (self._iterations, search, list(self.seen)))
1358
def get_state(self):
1359
"""Get the current state of this searcher.
1361
:return: Tuple with started keys, excludes and included keys
1363
if self._returning == 'next':
1364
# We have to know the current nodes children to be able to list the
1365
# exclude keys for them. However, while we could have a second
1366
# look-ahead result buffer and shuffle things around, this method
1367
# is typically only called once per search - when memoising the
1368
# results of the search.
1369
found, ghosts, next, parents = self._do_query(self._next_query)
1370
# pretend we didn't query: perhaps we should tweak _do_query to be
1371
# entirely stateless?
1372
self.seen.difference_update(next)
1373
next_query = next.union(ghosts)
1375
next_query = self._next_query
1376
excludes = self._stopped_keys.union(next_query)
1377
included_keys = self.seen.difference(excludes)
1378
return self._started_keys, excludes, included_keys
1383
except StopIteration:
1387
"""Return the next ancestors of this revision.
1389
Ancestors are returned in the order they are seen in a breadth-first
1390
traversal. No ancestor will be returned more than once. Ancestors are
1391
returned before their parentage is queried, so ghosts and missing
1392
revisions (including the start revisions) are included in the result.
1393
This can save a round trip in LCA style calculation by allowing
1394
convergence to be detected without reading the data for the revision
1395
the convergence occurs on.
1397
:return: A set of revision_ids.
1399
if self._returning != 'next':
1400
# switch to returning the query, not the results.
1401
self._returning = 'next'
1402
self._iterations += 1
1405
if len(self._next_query) == 0:
1406
raise StopIteration()
1407
# We have seen what we're querying at this point as we are returning
1408
# the query, not the results.
1409
self.seen.update(self._next_query)
1410
return self._next_query
1414
def next_with_ghosts(self):
1415
"""Return the next found ancestors, with ghosts split out.
1417
Ancestors are returned in the order they are seen in a breadth-first
1418
traversal. No ancestor will be returned more than once. Ancestors are
1419
returned only after asking for their parents, which allows us to detect
1420
which revisions are ghosts and which are not.
1422
:return: A tuple with (present ancestors, ghost ancestors) sets.
1424
if self._returning != 'next_with_ghosts':
1425
# switch to returning the results, not the current query.
1426
self._returning = 'next_with_ghosts'
1428
if len(self._next_query) == 0:
1429
raise StopIteration()
1431
return self._current_present, self._current_ghosts
1434
"""Advance the search.
1436
Updates self.seen, self._next_query, self._current_present,
1437
self._current_ghosts, self._current_parents and self._iterations.
1439
self._iterations += 1
1440
found, ghosts, next, parents = self._do_query(self._next_query)
1441
self._current_present = found
1442
self._current_ghosts = ghosts
1443
self._next_query = next
1444
self._current_parents = parents
1445
# ghosts are implicit stop points, otherwise the search cannot be
1446
# repeated when ghosts are filled.
1447
self._stopped_keys.update(ghosts)
1449
def _do_query(self, revisions):
1450
"""Query for revisions.
1452
Adds revisions to the seen set.
1454
:param revisions: Revisions to query.
1455
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1456
set(parents_of_found_revisions), dict(found_revisions:parents)).
1458
found_revisions = set()
1459
parents_of_found = set()
1460
# revisions may contain nodes that point to other nodes in revisions:
1461
# we want to filter them out.
1463
seen.update(revisions)
1464
parent_map = self._parents_provider.get_parent_map(revisions)
1465
found_revisions.update(parent_map)
1466
for rev_id, parents in viewitems(parent_map):
1469
new_found_parents = [p for p in parents if p not in seen]
1470
if new_found_parents:
1471
# Calling set.update() with an empty generator is actually
1473
parents_of_found.update(new_found_parents)
1474
ghost_revisions = revisions - found_revisions
1475
return found_revisions, ghost_revisions, parents_of_found, parent_map
1480
def find_seen_ancestors(self, revisions):
1481
"""Find ancestors of these revisions that have already been seen.
1483
This function generally makes the assumption that querying for the
1484
parents of a node that has already been queried is reasonably cheap.
1485
(eg, not a round trip to a remote host).
1487
# TODO: Often we might ask one searcher for its seen ancestors, and
1488
# then ask another searcher the same question. This can result in
1489
# searching the same revisions repeatedly if the two searchers
1490
# have a lot of overlap.
1491
all_seen = self.seen
1492
pending = set(revisions).intersection(all_seen)
1493
seen_ancestors = set(pending)
1495
if self._returning == 'next':
1496
# self.seen contains what nodes have been returned, not what nodes
1497
# have been queried. We don't want to probe for nodes that haven't
1498
# been searched yet.
1499
not_searched_yet = self._next_query
1501
not_searched_yet = ()
1502
pending.difference_update(not_searched_yet)
1503
get_parent_map = self._parents_provider.get_parent_map
1505
parent_map = get_parent_map(pending)
1507
# We don't care if it is a ghost, since it can't be seen if it is
1509
for parent_ids in viewvalues(parent_map):
1510
all_parents.extend(parent_ids)
1511
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1512
seen_ancestors.update(next_pending)
1513
next_pending.difference_update(not_searched_yet)
1514
pending = next_pending
1516
return seen_ancestors
1518
def stop_searching_any(self, revisions):
1520
Remove any of the specified revisions from the search list.
1522
None of the specified revisions are required to be present in the
1525
It is okay to call stop_searching_any() for revisions which were seen
1526
in previous iterations. It is the callers responsibility to call
1527
find_seen_ancestors() to make sure that current search tips that are
1528
ancestors of those revisions are also stopped. All explicitly stopped
1529
revisions will be excluded from the search result's get_keys(), though.
1531
# TODO: does this help performance?
1534
revisions = frozenset(revisions)
1535
if self._returning == 'next':
1536
stopped = self._next_query.intersection(revisions)
1537
self._next_query = self._next_query.difference(revisions)
1539
stopped_present = self._current_present.intersection(revisions)
1540
stopped = stopped_present.union(
1541
self._current_ghosts.intersection(revisions))
1542
self._current_present.difference_update(stopped)
1543
self._current_ghosts.difference_update(stopped)
1544
# stopping 'x' should stop returning parents of 'x', but
1545
# not if 'y' always references those same parents
1546
stop_rev_references = {}
1547
for rev in stopped_present:
1548
for parent_id in self._current_parents[rev]:
1549
if parent_id not in stop_rev_references:
1550
stop_rev_references[parent_id] = 0
1551
stop_rev_references[parent_id] += 1
1552
# if only the stopped revisions reference it, the ref count will be
1554
for parents in viewvalues(self._current_parents):
1555
for parent_id in parents:
1557
stop_rev_references[parent_id] -= 1
1560
stop_parents = set()
1561
for rev_id, refs in viewitems(stop_rev_references):
1563
stop_parents.add(rev_id)
1564
self._next_query.difference_update(stop_parents)
1565
self._stopped_keys.update(stopped)
1566
self._stopped_keys.update(revisions)
1569
def start_searching(self, revisions):
1570
"""Add revisions to the search.
1572
The parents of revisions will be returned from the next call to next()
1573
or next_with_ghosts(). If next_with_ghosts was the most recently used
1574
next* call then the return value is the result of looking up the
1575
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1577
revisions = frozenset(revisions)
1578
self._started_keys.update(revisions)
1579
new_revisions = revisions.difference(self.seen)
1580
if self._returning == 'next':
1581
self._next_query.update(new_revisions)
1582
self.seen.update(new_revisions)
1584
# perform a query on revisions
1585
revs, ghosts, query, parents = self._do_query(revisions)
1586
self._stopped_keys.update(ghosts)
1587
self._current_present.update(revs)
1588
self._current_ghosts.update(ghosts)
1589
self._next_query.update(query)
1590
self._current_parents.update(parents)
1594
def invert_parent_map(parent_map):
1595
"""Given a map from child => parents, create a map of parent=>children"""
1597
for child, parents in viewitems(parent_map):
1599
# Any given parent is likely to have only a small handful
1600
# of children, many will have only one. So we avoid mem overhead of
1601
# a list, in exchange for extra copying of tuples
1602
if p not in child_map:
1603
child_map[p] = (child,)
1605
child_map[p] = child_map[p] + (child,)
1609
def collapse_linear_regions(parent_map):
1610
"""Collapse regions of the graph that are 'linear'.
1616
can be collapsed by removing B and getting::
1620
:param parent_map: A dictionary mapping children to their parents
1621
:return: Another dictionary with 'linear' chains collapsed
1623
# Note: this isn't a strictly minimal collapse. For example:
1631
# Will not have 'D' removed, even though 'E' could fit. Also:
1637
# A and C are both kept because they are edges of the graph. We *could* get
1638
# rid of A if we wanted.
1646
# Will not have any nodes removed, even though you do have an
1647
# 'uninteresting' linear D->B and E->C
1649
for child, parents in viewitems(parent_map):
1650
children.setdefault(child, [])
1652
children.setdefault(p, []).append(child)
1654
orig_children = dict(children)
1656
result = dict(parent_map)
1657
for node in parent_map:
1658
parents = result[node]
1659
if len(parents) == 1:
1660
parent_children = children[parents[0]]
1661
if len(parent_children) != 1:
1662
# This is not the only child
1664
node_children = children[node]
1665
if len(node_children) != 1:
1667
child_parents = result.get(node_children[0], None)
1668
if len(child_parents) != 1:
1669
# This is not its only parent
1671
# The child of this node only points at it, and the parent only has
1672
# this as a child. remove this node, and join the others together
1673
result[node_children[0]] = parents
1674
children[parents[0]] = node_children
1682
class GraphThunkIdsToKeys(object):
1683
"""Forwards calls about 'ids' to be about keys internally."""
1685
def __init__(self, graph):
1688
def topo_sort(self):
1689
return [r for (r,) in self._graph.topo_sort()]
1691
def heads(self, ids):
1692
"""See Graph.heads()"""
1693
as_keys = [(i,) for i in ids]
1694
head_keys = self._graph.heads(as_keys)
1695
return {h[0] for h in head_keys}
1697
def merge_sort(self, tip_revision):
1698
nodes = self._graph.merge_sort((tip_revision,))
1700
node.key = node.key[0]
1703
def add_node(self, revision, parents):
1704
self._graph.add_node((revision,), [(p,) for p in parents])
1707
_counters = [0, 0, 0, 0, 0, 0, 0]
1709
from ._known_graph_pyx import KnownGraph
1710
except ImportError as e:
1711
osutils.failed_to_load_extension(e)
1712
from ._known_graph_py import KnownGraph
added
removed
breezy/graph.py
