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.
145
def __init__(self, parent_provider=None, get_parent_map=None):
148
:param parent_provider: The ParentProvider to use. It or
149
get_parent_map must be supplied.
150
:param get_parent_map: The get_parent_map callback to use. It or
151
parent_provider must be supplied.
153
self._real_provider = parent_provider
154
if get_parent_map is None:
155
self._get_parent_map = self._real_provider.get_parent_map
157
self._get_parent_map = get_parent_map
159
self.enable_cache(True)
162
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
164
def enable_cache(self, cache_misses=True):
166
if self._cache is not None:
167
raise AssertionError('Cache enabled when already enabled.')
169
self._cache_misses = cache_misses
170
self.missing_keys = set()
172
def disable_cache(self):
173
"""Disable and clear the cache."""
175
self._cache_misses = None
176
self.missing_keys = set()
178
def get_cached_map(self):
179
"""Return any cached get_parent_map values."""
180
if self._cache is None:
182
return dict(self._cache)
184
def get_cached_parent_map(self, keys):
185
"""Return items from the cache.
187
This returns the same info as get_parent_map, but explicitly does not
188
invoke the supplied ParentsProvider to search for uncached values.
193
return dict([(key, cache[key]) for key in keys if key in cache])
195
def get_parent_map(self, keys):
196
"""See StackedParentsProvider.get_parent_map."""
199
cache = self._get_parent_map(keys)
201
needed_revisions = set(key for key in keys if key not in cache)
202
# Do not ask for negatively cached keys
203
needed_revisions.difference_update(self.missing_keys)
205
parent_map = self._get_parent_map(needed_revisions)
206
cache.update(parent_map)
207
if self._cache_misses:
208
for key in needed_revisions:
209
if key not in parent_map:
210
self.note_missing_key(key)
213
value = cache.get(key)
214
if value is not None:
218
def note_missing_key(self, key):
219
"""Note that key is a missing key."""
220
if self._cache_misses:
221
self.missing_keys.add(key)
224
class CallableToParentsProviderAdapter(object):
225
"""A parents provider that adapts any callable to the parents provider API.
227
i.e. it accepts calls to self.get_parent_map and relays them to the
228
callable it was constructed with.
231
def __init__(self, a_callable):
232
self.callable = a_callable
235
return "%s(%r)" % (self.__class__.__name__, self.callable)
237
def get_parent_map(self, keys):
238
return self.callable(keys)
242
"""Provide incremental access to revision graphs.
244
This is the generic implementation; it is intended to be subclassed to
245
specialize it for other repository types.
248
def __init__(self, parents_provider):
249
"""Construct a Graph that uses several graphs as its input
251
This should not normally be invoked directly, because there may be
252
specialized implementations for particular repository types. See
253
Repository.get_graph().
255
:param parents_provider: An object providing a get_parent_map call
256
conforming to the behavior of
257
StackedParentsProvider.get_parent_map.
259
if getattr(parents_provider, 'get_parents', None) is not None:
260
self.get_parents = parents_provider.get_parents
261
if getattr(parents_provider, 'get_parent_map', None) is not None:
262
self.get_parent_map = parents_provider.get_parent_map
263
self._parents_provider = parents_provider
266
return 'Graph(%r)' % self._parents_provider
268
def find_lca(self, *revisions):
269
"""Determine the lowest common ancestors of the provided revisions
271
A lowest common ancestor is a common ancestor none of whose
272
descendants are common ancestors. In graphs, unlike trees, there may
273
be multiple lowest common ancestors.
275
This algorithm has two phases. Phase 1 identifies border ancestors,
276
and phase 2 filters border ancestors to determine lowest common
279
In phase 1, border ancestors are identified, using a breadth-first
280
search starting at the bottom of the graph. Searches are stopped
281
whenever a node or one of its descendants is determined to be common
283
In phase 2, the border ancestors are filtered to find the least
284
common ancestors. This is done by searching the ancestries of each
287
Phase 2 is perfomed on the principle that a border ancestor that is
288
not an ancestor of any other border ancestor is a least common
291
Searches are stopped when they find a node that is determined to be a
292
common ancestor of all border ancestors, because this shows that it
293
cannot be a descendant of any border ancestor.
295
The scaling of this operation should be proportional to:
297
1. The number of uncommon ancestors
298
2. The number of border ancestors
299
3. The length of the shortest path between a border ancestor and an
300
ancestor of all border ancestors.
302
border_common, common, sides = self._find_border_ancestors(revisions)
303
# We may have common ancestors that can be reached from each other.
304
# - ask for the heads of them to filter it down to only ones that
305
# cannot be reached from each other - phase 2.
306
return self.heads(border_common)
308
def find_difference(self, left_revision, right_revision):
309
"""Determine the graph difference between two revisions"""
310
border, common, searchers = self._find_border_ancestors(
311
[left_revision, right_revision])
312
self._search_for_extra_common(common, searchers)
313
left = searchers[0].seen
314
right = searchers[1].seen
315
return (left.difference(right), right.difference(left))
317
def find_descendants(self, old_key, new_key):
318
"""Find descendants of old_key that are ancestors of new_key."""
319
child_map = self.get_child_map(self._find_descendant_ancestors(
321
graph = Graph(DictParentsProvider(child_map))
322
searcher = graph._make_breadth_first_searcher([old_key])
326
def _find_descendant_ancestors(self, old_key, new_key):
327
"""Find ancestors of new_key that may be descendants of old_key."""
328
stop = self._make_breadth_first_searcher([old_key])
329
descendants = self._make_breadth_first_searcher([new_key])
330
for revisions in descendants:
331
old_stop = stop.seen.intersection(revisions)
332
descendants.stop_searching_any(old_stop)
333
seen_stop = descendants.find_seen_ancestors(stop.step())
334
descendants.stop_searching_any(seen_stop)
335
return descendants.seen.difference(stop.seen)
337
def get_child_map(self, keys):
338
"""Get a mapping from parents to children of the specified keys.
340
This is simply the inversion of get_parent_map. Only supplied keys
341
will be discovered as children.
342
:return: a dict of key:child_list for keys.
344
parent_map = self._parents_provider.get_parent_map(keys)
346
for child, parents in sorted(viewitems(parent_map)):
347
for parent in parents:
348
parent_child.setdefault(parent, []).append(child)
351
def find_distance_to_null(self, target_revision_id, known_revision_ids):
352
"""Find the left-hand distance to the NULL_REVISION.
354
(This can also be considered the revno of a branch at
357
:param target_revision_id: A revision_id which we would like to know
359
:param known_revision_ids: [(revision_id, revno)] A list of known
360
revno, revision_id tuples. We'll use this to seed the search.
362
# Map from revision_ids to a known value for their revno
363
known_revnos = dict(known_revision_ids)
364
cur_tip = target_revision_id
366
NULL_REVISION = revision.NULL_REVISION
367
known_revnos[NULL_REVISION] = 0
369
searching_known_tips = list(known_revnos)
371
unknown_searched = {}
373
while cur_tip not in known_revnos:
374
unknown_searched[cur_tip] = num_steps
376
to_search = {cur_tip}
377
to_search.update(searching_known_tips)
378
parent_map = self.get_parent_map(to_search)
379
parents = parent_map.get(cur_tip, None)
380
if not parents: # An empty list or None is a ghost
381
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
385
for revision_id in searching_known_tips:
386
parents = parent_map.get(revision_id, None)
390
next_revno = known_revnos[revision_id] - 1
391
if next in unknown_searched:
392
# We have enough information to return a value right now
393
return next_revno + unknown_searched[next]
394
if next in known_revnos:
396
known_revnos[next] = next_revno
397
next_known_tips.append(next)
398
searching_known_tips = next_known_tips
400
# We reached a known revision, so just add in how many steps it took to
402
return known_revnos[cur_tip] + num_steps
404
def find_lefthand_distances(self, keys):
405
"""Find the distance to null for all the keys in keys.
407
:param keys: keys to lookup.
408
:return: A dict key->distance for all of keys.
410
# Optimisable by concurrent searching, but a random spread should get
411
# 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(
469
unique_nodes, 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.
513
common_searcher.find_seen_ancestors(ancestors))
514
unique_searcher.stop_searching_any(ancestors)
515
common_searcher.start_searching(ancestors)
517
return unique_searcher, common_searcher
519
def _make_unique_searchers(self, unique_nodes, unique_searcher,
521
"""Create a searcher for all the unique search tips (step 4).
523
As a side effect, the common_searcher will stop searching any nodes
524
that are ancestors of the unique searcher tips.
526
:return: (all_unique_searcher, unique_tip_searchers)
528
unique_tips = self._remove_simple_descendants(
529
unique_nodes, self.get_parent_map(unique_nodes))
531
if len(unique_tips) == 1:
532
unique_tip_searchers = []
533
ancestor_all_unique = unique_searcher.find_seen_ancestors(
536
unique_tip_searchers = []
537
for tip in unique_tips:
538
revs_to_search = unique_searcher.find_seen_ancestors([tip])
539
revs_to_search.update(
540
common_searcher.find_seen_ancestors(revs_to_search))
541
searcher = self._make_breadth_first_searcher(revs_to_search)
542
# We don't care about the starting nodes.
543
searcher._label = tip
545
unique_tip_searchers.append(searcher)
547
ancestor_all_unique = None
548
for searcher in unique_tip_searchers:
549
if ancestor_all_unique is None:
550
ancestor_all_unique = set(searcher.seen)
552
ancestor_all_unique = ancestor_all_unique.intersection(
554
# Collapse all the common nodes into a single searcher
555
all_unique_searcher = self._make_breadth_first_searcher(
557
if ancestor_all_unique:
558
# We've seen these nodes in all the searchers, so we'll just go to
560
all_unique_searcher.step()
562
# Stop any search tips that are already known as ancestors of the
564
stopped_common = common_searcher.stop_searching_any(
565
common_searcher.find_seen_ancestors(ancestor_all_unique))
568
for searcher in unique_tip_searchers:
569
total_stopped += len(searcher.stop_searching_any(
570
searcher.find_seen_ancestors(ancestor_all_unique)))
571
if 'graph' in debug.debug_flags:
572
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
573
' (%d stopped search tips, %d common ancestors'
574
' (%d stopped common)',
575
len(unique_nodes), len(unique_tip_searchers),
576
total_stopped, len(ancestor_all_unique),
578
return all_unique_searcher, unique_tip_searchers
580
def _step_unique_and_common_searchers(self, common_searcher,
581
unique_tip_searchers,
583
"""Step all the searchers"""
584
newly_seen_common = set(common_searcher.step())
585
newly_seen_unique = set()
586
for searcher in unique_tip_searchers:
587
next = set(searcher.step())
588
next.update(unique_searcher.find_seen_ancestors(next))
589
next.update(common_searcher.find_seen_ancestors(next))
590
for alt_searcher in unique_tip_searchers:
591
if alt_searcher is searcher:
593
next.update(alt_searcher.find_seen_ancestors(next))
594
searcher.start_searching(next)
595
newly_seen_unique.update(next)
596
return newly_seen_common, newly_seen_unique
598
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
600
newly_seen_unique, step_all_unique):
601
"""Find nodes that are common to all unique_tip_searchers.
603
If it is time, step the all_unique_searcher, and add its nodes to the
606
common_to_all_unique_nodes = newly_seen_unique.copy()
607
for searcher in unique_tip_searchers:
608
common_to_all_unique_nodes.intersection_update(searcher.seen)
609
common_to_all_unique_nodes.intersection_update(
610
all_unique_searcher.seen)
611
# Step all-unique less frequently than the other searchers.
612
# In the common case, we don't need to spider out far here, so
613
# avoid doing extra work.
615
tstart = osutils.perf_counter()
616
nodes = all_unique_searcher.step()
617
common_to_all_unique_nodes.update(nodes)
618
if 'graph' in debug.debug_flags:
619
tdelta = osutils.perf_counter() - tstart
620
trace.mutter('all_unique_searcher step() took %.3fs'
621
'for %d nodes (%d total), iteration: %s',
622
tdelta, len(nodes), len(all_unique_searcher.seen),
623
all_unique_searcher._iterations)
624
return common_to_all_unique_nodes
626
def _collapse_unique_searchers(self, unique_tip_searchers,
627
common_to_all_unique_nodes):
628
"""Combine searchers that are searching the same tips.
630
When two searchers are searching the same tips, we can stop one of the
631
searchers. We also know that the maximal set of common ancestors is the
632
intersection of the two original searchers.
634
:return: A list of searchers that are searching unique nodes.
636
# Filter out searchers that don't actually search different
637
# nodes. We already have the ancestry intersection for them
638
unique_search_tips = {}
639
for searcher in unique_tip_searchers:
640
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
641
will_search_set = frozenset(searcher._next_query)
642
if not will_search_set:
643
if 'graph' in debug.debug_flags:
644
trace.mutter('Unique searcher %s was stopped.'
645
' (%s iterations) %d nodes stopped',
647
searcher._iterations,
649
elif will_search_set not in unique_search_tips:
650
# This searcher is searching a unique set of nodes, let it
651
unique_search_tips[will_search_set] = [searcher]
653
unique_search_tips[will_search_set].append(searcher)
654
# TODO: it might be possible to collapse searchers faster when they
655
# only have *some* search tips in common.
656
next_unique_searchers = []
657
for searchers in viewvalues(unique_search_tips):
658
if len(searchers) == 1:
659
# Searching unique tips, go for it
660
next_unique_searchers.append(searchers[0])
662
# These searchers have started searching the same tips, we
663
# don't need them to cover the same ground. The
664
# intersection of their ancestry won't change, so create a
665
# new searcher, combining their histories.
666
next_searcher = searchers[0]
667
for searcher in searchers[1:]:
668
next_searcher.seen.intersection_update(searcher.seen)
669
if 'graph' in debug.debug_flags:
670
trace.mutter('Combining %d searchers into a single'
671
' searcher searching %d nodes with'
674
len(next_searcher._next_query),
675
len(next_searcher.seen))
676
next_unique_searchers.append(next_searcher)
677
return next_unique_searchers
679
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
680
unique_tip_searchers, common_searcher):
681
"""Steps 5-8 of find_unique_ancestors.
683
This function returns when common_searcher has stopped searching for
686
# We step the ancestor_all_unique searcher only every
687
# STEP_UNIQUE_SEARCHER_EVERY steps.
688
step_all_unique_counter = 0
689
# While we still have common nodes to search
690
while common_searcher._next_query:
692
newly_seen_unique) = self._step_unique_and_common_searchers(
693
common_searcher, unique_tip_searchers, unique_searcher)
694
# These nodes are common ancestors of all unique nodes
695
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
696
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
697
step_all_unique_counter == 0)
698
step_all_unique_counter = ((step_all_unique_counter + 1)
699
% STEP_UNIQUE_SEARCHER_EVERY)
701
if newly_seen_common:
702
# If a 'common' node is an ancestor of all unique searchers, we
703
# can stop searching it.
704
common_searcher.stop_searching_any(
705
all_unique_searcher.seen.intersection(newly_seen_common))
706
if common_to_all_unique_nodes:
707
common_to_all_unique_nodes.update(
708
common_searcher.find_seen_ancestors(
709
common_to_all_unique_nodes))
710
# The all_unique searcher can start searching the common nodes
711
# but everyone else can stop.
712
# This is the sort of thing where we would like to not have it
713
# start_searching all of the nodes, but only mark all of them
714
# as seen, and have it search only the actual tips. Otherwise
715
# it is another get_parent_map() traversal for it to figure out
716
# what we already should know.
717
all_unique_searcher.start_searching(common_to_all_unique_nodes)
718
common_searcher.stop_searching_any(common_to_all_unique_nodes)
720
next_unique_searchers = self._collapse_unique_searchers(
721
unique_tip_searchers, common_to_all_unique_nodes)
722
if len(unique_tip_searchers) != len(next_unique_searchers):
723
if 'graph' in debug.debug_flags:
724
trace.mutter('Collapsed %d unique searchers => %d'
726
len(unique_tip_searchers),
727
len(next_unique_searchers),
728
all_unique_searcher._iterations)
729
unique_tip_searchers = next_unique_searchers
731
def get_parent_map(self, revisions):
732
"""Get a map of key:parent_list for revisions.
734
This implementation delegates to get_parents, for old parent_providers
735
that do not supply get_parent_map.
738
for rev, parents in self.get_parents(revisions):
739
if parents is not None:
740
result[rev] = parents
743
def _make_breadth_first_searcher(self, revisions):
744
return _BreadthFirstSearcher(revisions, self)
746
def _find_border_ancestors(self, revisions):
747
"""Find common ancestors with at least one uncommon descendant.
749
Border ancestors are identified using a breadth-first
750
search starting at the bottom of the graph. Searches are stopped
751
whenever a node or one of its descendants is determined to be common.
753
This will scale with the number of uncommon ancestors.
755
As well as the border ancestors, a set of seen common ancestors and a
756
list of sets of seen ancestors for each input revision is returned.
757
This allows calculation of graph difference from the results of this
760
if None in revisions:
761
raise errors.InvalidRevisionId(None, self)
762
common_ancestors = set()
763
searchers = [self._make_breadth_first_searcher([r])
765
border_ancestors = set()
769
for searcher in searchers:
770
new_ancestors = searcher.step()
772
newly_seen.update(new_ancestors)
774
for revision in newly_seen:
775
if revision in common_ancestors:
776
# Not a border ancestor because it was seen as common
778
new_common.add(revision)
780
for searcher in searchers:
781
if revision not in searcher.seen:
784
# This is a border because it is a first common that we see
785
# after walking for a while.
786
border_ancestors.add(revision)
787
new_common.add(revision)
789
for searcher in searchers:
790
new_common.update(searcher.find_seen_ancestors(new_common))
791
for searcher in searchers:
792
searcher.start_searching(new_common)
793
common_ancestors.update(new_common)
795
# Figure out what the searchers will be searching next, and if
796
# there is only 1 set being searched, then we are done searching,
797
# since all searchers would have to be searching the same data,
798
# thus it *must* be in common.
799
unique_search_sets = set()
800
for searcher in searchers:
801
will_search_set = frozenset(searcher._next_query)
802
if will_search_set not in unique_search_sets:
803
# This searcher is searching a unique set of nodes, let it
804
unique_search_sets.add(will_search_set)
806
if len(unique_search_sets) == 1:
807
nodes = unique_search_sets.pop()
808
uncommon_nodes = nodes.difference(common_ancestors)
810
raise AssertionError("Somehow we ended up converging"
811
" without actually marking them as"
814
"\nuncommon_nodes: %s"
815
% (revisions, uncommon_nodes))
817
return border_ancestors, common_ancestors, searchers
819
def heads(self, keys):
820
"""Return the heads from amongst keys.
822
This is done by searching the ancestries of each key. Any key that is
823
reachable from another key is not returned; all the others are.
825
This operation scales with the relative depth between any two keys. If
826
any two keys are completely disconnected all ancestry of both sides
829
:param keys: An iterable of keys.
830
:return: A set of the heads. Note that as a set there is no ordering
831
information. Callers will need to filter their input to create
832
order if they need it.
834
candidate_heads = set(keys)
835
if revision.NULL_REVISION in candidate_heads:
836
# NULL_REVISION is only a head if it is the only entry
837
candidate_heads.remove(revision.NULL_REVISION)
838
if not candidate_heads:
839
return {revision.NULL_REVISION}
840
if len(candidate_heads) < 2:
841
return candidate_heads
842
searchers = dict((c, self._make_breadth_first_searcher([c]))
843
for c in candidate_heads)
844
active_searchers = dict(searchers)
845
# skip over the actual candidate for each searcher
846
for searcher in viewvalues(active_searchers):
848
# The common walker finds nodes that are common to two or more of the
849
# input keys, so that we don't access all history when a currently
850
# uncommon search point actually meets up with something behind a
851
# common search point. Common search points do not keep searches
852
# active; they just allow us to make searches inactive without
853
# accessing all history.
854
common_walker = self._make_breadth_first_searcher([])
855
while len(active_searchers) > 0:
860
except StopIteration:
861
# No common points being searched at this time.
863
for candidate in list(active_searchers):
865
searcher = active_searchers[candidate]
867
# rare case: we deleted candidate in a previous iteration
868
# through this for loop, because it was determined to be
869
# a descendant of another candidate.
872
ancestors.update(next(searcher))
873
except StopIteration:
874
del active_searchers[candidate]
876
# process found nodes
878
for ancestor in ancestors:
879
if ancestor in candidate_heads:
880
candidate_heads.remove(ancestor)
881
del searchers[ancestor]
882
if ancestor in active_searchers:
883
del active_searchers[ancestor]
884
# it may meet up with a known common node
885
if ancestor in common_walker.seen:
886
# some searcher has encountered our known common nodes:
888
ancestor_set = {ancestor}
889
for searcher in viewvalues(searchers):
890
searcher.stop_searching_any(ancestor_set)
892
# or it may have been just reached by all the searchers:
893
for searcher in viewvalues(searchers):
894
if ancestor not in searcher.seen:
897
# The final active searcher has just reached this node,
898
# making it be known as a descendant of all candidates,
899
# so we can stop searching it, and any seen ancestors
900
new_common.add(ancestor)
901
for searcher in viewvalues(searchers):
903
searcher.find_seen_ancestors([ancestor])
904
searcher.stop_searching_any(seen_ancestors)
905
common_walker.start_searching(new_common)
906
return candidate_heads
908
def find_merge_order(self, tip_revision_id, lca_revision_ids):
909
"""Find the order that each revision was merged into tip.
911
This basically just walks backwards with a stack, and walks left-first
912
until it finds a node to stop.
914
if len(lca_revision_ids) == 1:
915
return list(lca_revision_ids)
916
looking_for = set(lca_revision_ids)
917
# TODO: Is there a way we could do this "faster" by batching up the
918
# get_parent_map requests?
919
# TODO: Should we also be culling the ancestry search right away? We
920
# could add looking_for to the "stop" list, and walk their
921
# ancestry in batched mode. The flip side is it might mean we walk a
922
# lot of "stop" nodes, rather than only the minimum.
923
# Then again, without it we may trace back into ancestry we could have
925
stack = [tip_revision_id]
928
while stack and looking_for:
931
if next in looking_for:
933
looking_for.remove(next)
934
if len(looking_for) == 1:
935
found.append(looking_for.pop())
938
parent_ids = self.get_parent_map([next]).get(next, None)
939
if not parent_ids: # Ghost, nothing to search here
941
for parent_id in reversed(parent_ids):
942
# TODO: (performance) We see the parent at this point, but we
943
# wait to mark it until later to make sure we get left
944
# parents before right parents. However, instead of
945
# waiting until we have traversed enough parents, we
946
# could instead note that we've found it, and once all
947
# parents are in the stack, just reverse iterate the
949
if parent_id not in stop:
950
# this will need to be searched
951
stack.append(parent_id)
955
def find_lefthand_merger(self, merged_key, tip_key):
956
"""Find the first lefthand ancestor of tip_key that merged merged_key.
958
We do this by first finding the descendants of merged_key, then
959
walking through the lefthand ancestry of tip_key until we find a key
960
that doesn't descend from merged_key. Its child is the key that
963
:return: The first lefthand ancestor of tip_key to merge merged_key.
964
merged_key if it is a lefthand ancestor of tip_key.
965
None if no ancestor of tip_key merged merged_key.
967
descendants = self.find_descendants(merged_key, tip_key)
968
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
969
last_candidate = None
970
for candidate in candidate_iterator:
971
if candidate not in descendants:
972
return last_candidate
973
last_candidate = candidate
975
def find_unique_lca(self, left_revision, right_revision,
977
"""Find a unique LCA.
979
Find lowest common ancestors. If there is no unique common
980
ancestor, find the lowest common ancestors of those ancestors.
982
Iteration stops when a unique lowest common ancestor is found.
983
The graph origin is necessarily a unique lowest common ancestor.
985
Note that None is not an acceptable substitute for NULL_REVISION.
986
in the input for this method.
988
:param count_steps: If True, the return value will be a tuple of
989
(unique_lca, steps) where steps is the number of times that
990
find_lca was run. If False, only unique_lca is returned.
992
revisions = [left_revision, right_revision]
996
lca = self.find_lca(*revisions)
1000
return result, steps
1004
raise errors.NoCommonAncestor(left_revision, right_revision)
1007
def iter_ancestry(self, revision_ids):
1008
"""Iterate the ancestry of this revision.
1010
:param revision_ids: Nodes to start the search
1011
:return: Yield tuples mapping a revision_id to its parents for the
1012
ancestry of revision_id.
1013
Ghosts will be returned with None as their parents, and nodes
1014
with no parents will have NULL_REVISION as their only parent. (As
1015
defined by get_parent_map.)
1016
There will also be a node for (NULL_REVISION, ())
1018
pending = set(revision_ids)
1021
processed.update(pending)
1022
next_map = self.get_parent_map(pending)
1023
next_pending = set()
1024
for item in viewitems(next_map):
1026
next_pending.update(p for p in item[1] if p not in processed)
1027
ghosts = pending.difference(next_map)
1028
for ghost in ghosts:
1030
pending = next_pending
1032
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1033
if stop_keys is None:
1035
next_key = start_key
1037
def get_parents(key):
1039
return self._parents_provider.get_parent_map([key])[key]
1041
raise errors.RevisionNotPresent(next_key, self)
1043
if next_key in stop_keys:
1045
parents = get_parents(next_key)
1047
if len(parents) == 0:
1050
next_key = parents[0]
1052
def iter_topo_order(self, revisions):
1053
"""Iterate through the input revisions in topological order.
1055
This sorting only ensures that parents come before their children.
1056
An ancestor may sort after a descendant if the relationship is not
1057
visible in the supplied list of revisions.
1059
from breezy import tsort
1060
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1061
return sorter.iter_topo_order()
1063
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1064
"""Determine whether a revision is an ancestor of another.
1066
We answer this using heads() as heads() has the logic to perform the
1067
smallest number of parent lookups to determine the ancestral
1068
relationship between N revisions.
1070
return {candidate_descendant} == self.heads(
1071
[candidate_ancestor, candidate_descendant])
1073
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1074
"""Determine whether a revision is between two others.
1076
returns true if and only if:
1077
lower_bound_revid <= revid <= upper_bound_revid
1079
return ((upper_bound_revid is None or
1080
self.is_ancestor(revid, upper_bound_revid)) and
1081
(lower_bound_revid is None or
1082
self.is_ancestor(lower_bound_revid, revid)))
1084
def _search_for_extra_common(self, common, searchers):
1085
"""Make sure that unique nodes are genuinely unique.
1087
After _find_border_ancestors, all nodes marked "common" are indeed
1088
common. Some of the nodes considered unique are not, due to history
1089
shortcuts stopping the searches early.
1091
We know that we have searched enough when all common search tips are
1092
descended from all unique (uncommon) nodes because we know that a node
1093
cannot be an ancestor of its own ancestor.
1095
:param common: A set of common nodes
1096
:param searchers: The searchers returned from _find_border_ancestors
1099
# Basic algorithm...
1100
# A) The passed in searchers should all be on the same tips, thus
1101
# they should be considered the "common" searchers.
1102
# B) We find the difference between the searchers, these are the
1103
# "unique" nodes for each side.
1104
# C) We do a quick culling so that we only start searching from the
1105
# more interesting unique nodes. (A unique ancestor is more
1106
# interesting than any of its children.)
1107
# D) We start searching for ancestors common to all unique nodes.
1108
# E) We have the common searchers stop searching any ancestors of
1109
# nodes found by (D)
1110
# F) When there are no more common search tips, we stop
1112
# TODO: We need a way to remove unique_searchers when they overlap with
1113
# other unique searchers.
1114
if len(searchers) != 2:
1115
raise NotImplementedError(
1116
"Algorithm not yet implemented for > 2 searchers")
1117
common_searchers = searchers
1118
left_searcher = searchers[0]
1119
right_searcher = searchers[1]
1120
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1121
if not unique: # No unique nodes, nothing to do
1123
total_unique = len(unique)
1124
unique = self._remove_simple_descendants(unique,
1125
self.get_parent_map(unique))
1126
simple_unique = len(unique)
1128
unique_searchers = []
1129
for revision_id in unique:
1130
if revision_id in left_searcher.seen:
1131
parent_searcher = left_searcher
1133
parent_searcher = right_searcher
1134
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1135
if not revs_to_search: # XXX: This shouldn't be possible
1136
revs_to_search = [revision_id]
1137
searcher = self._make_breadth_first_searcher(revs_to_search)
1138
# We don't care about the starting nodes.
1140
unique_searchers.append(searcher)
1142
# possible todo: aggregate the common searchers into a single common
1143
# searcher, just make sure that we include the nodes into the .seen
1144
# properties of the original searchers
1146
ancestor_all_unique = None
1147
for searcher in unique_searchers:
1148
if ancestor_all_unique is None:
1149
ancestor_all_unique = set(searcher.seen)
1151
ancestor_all_unique = ancestor_all_unique.intersection(
1154
trace.mutter('Started %d unique searchers for %d unique revisions',
1155
simple_unique, total_unique)
1157
while True: # If we have no more nodes we have nothing to do
1158
newly_seen_common = set()
1159
for searcher in common_searchers:
1160
newly_seen_common.update(searcher.step())
1161
newly_seen_unique = set()
1162
for searcher in unique_searchers:
1163
newly_seen_unique.update(searcher.step())
1164
new_common_unique = set()
1165
for revision in newly_seen_unique:
1166
for searcher in unique_searchers:
1167
if revision not in searcher.seen:
1170
# This is a border because it is a first common that we see
1171
# after walking for a while.
1172
new_common_unique.add(revision)
1173
if newly_seen_common:
1174
# These are nodes descended from one of the 'common' searchers.
1175
# Make sure all searchers are on the same page
1176
for searcher in common_searchers:
1177
newly_seen_common.update(
1178
searcher.find_seen_ancestors(newly_seen_common))
1179
# We start searching the whole ancestry. It is a bit wasteful,
1180
# though. We really just want to mark all of these nodes as
1181
# 'seen' and then start just the tips. However, it requires a
1182
# get_parent_map() call to figure out the tips anyway, and all
1183
# redundant requests should be fairly fast.
1184
for searcher in common_searchers:
1185
searcher.start_searching(newly_seen_common)
1187
# If a 'common' node is an ancestor of all unique searchers, we
1188
# can stop searching it.
1189
stop_searching_common = ancestor_all_unique.intersection(
1191
if stop_searching_common:
1192
for searcher in common_searchers:
1193
searcher.stop_searching_any(stop_searching_common)
1194
if new_common_unique:
1195
# We found some ancestors that are common
1196
for searcher in unique_searchers:
1197
new_common_unique.update(
1198
searcher.find_seen_ancestors(new_common_unique))
1199
# Since these are common, we can grab another set of ancestors
1201
for searcher in common_searchers:
1202
new_common_unique.update(
1203
searcher.find_seen_ancestors(new_common_unique))
1205
# We can tell all of the unique searchers to start at these
1206
# nodes, and tell all of the common searchers to *stop*
1207
# searching these nodes
1208
for searcher in unique_searchers:
1209
searcher.start_searching(new_common_unique)
1210
for searcher in common_searchers:
1211
searcher.stop_searching_any(new_common_unique)
1212
ancestor_all_unique.update(new_common_unique)
1214
# Filter out searchers that don't actually search different
1215
# nodes. We already have the ancestry intersection for them
1216
next_unique_searchers = []
1217
unique_search_sets = set()
1218
for searcher in unique_searchers:
1219
will_search_set = frozenset(searcher._next_query)
1220
if will_search_set not in unique_search_sets:
1221
# This searcher is searching a unique set of nodes, let
1223
unique_search_sets.add(will_search_set)
1224
next_unique_searchers.append(searcher)
1225
unique_searchers = next_unique_searchers
1226
for searcher in common_searchers:
1227
if searcher._next_query:
1230
# All common searcher have stopped searching
1233
def _remove_simple_descendants(self, revisions, parent_map):
1234
"""remove revisions which are children of other ones in the set
1236
This doesn't do any graph searching, it just checks the immediate
1237
parent_map to find if there are any children which can be removed.
1239
:param revisions: A set of revision_ids
1240
:return: A set of revision_ids with the children removed
1242
simple_ancestors = revisions.copy()
1243
# TODO: jam 20071214 we *could* restrict it to searching only the
1244
# parent_map of revisions already present in 'revisions', but
1245
# considering the general use case, I think this is actually
1248
# This is the same as the following loop. I don't know that it is any
1250
# simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1251
# if p_ids is not None and revisions.intersection(p_ids))
1252
# return simple_ancestors
1254
# Yet Another Way, invert the parent map (which can be cached)
1256
# for revision_id, parent_ids in parent_map.iteritems():
1257
# for p_id in parent_ids:
1258
## descendants.setdefault(p_id, []).append(revision_id)
1259
# for revision in revisions.intersection(descendants):
1260
# simple_ancestors.difference_update(descendants[revision])
1261
# return simple_ancestors
1262
for revision, parent_ids in viewitems(parent_map):
1263
if parent_ids is None:
1265
for parent_id in parent_ids:
1266
if parent_id in revisions:
1267
# This node has a parent present in the set, so we can
1269
simple_ancestors.discard(revision)
1271
return simple_ancestors
1274
class HeadsCache(object):
1275
"""A cache of results for graph heads calls."""
1277
def __init__(self, graph):
1281
def heads(self, keys):
1282
"""Return the heads of keys.
1284
This matches the API of Graph.heads(), specifically the return value is
1285
a set which can be mutated, and ordering of the input is not preserved
1288
:see also: Graph.heads.
1289
:param keys: The keys to calculate heads for.
1290
:return: A set containing the heads, which may be mutated without
1291
affecting future lookups.
1293
keys = frozenset(keys)
1295
return set(self._heads[keys])
1297
heads = self.graph.heads(keys)
1298
self._heads[keys] = heads
1302
class FrozenHeadsCache(object):
1303
"""Cache heads() calls, assuming the caller won't modify them."""
1305
def __init__(self, graph):
1309
def heads(self, keys):
1310
"""Return the heads of keys.
1312
Similar to Graph.heads(). The main difference is that the return value
1313
is a frozen set which cannot be mutated.
1315
:see also: Graph.heads.
1316
:param keys: The keys to calculate heads for.
1317
:return: A frozenset containing the heads.
1319
keys = frozenset(keys)
1321
return self._heads[keys]
1323
heads = frozenset(self.graph.heads(keys))
1324
self._heads[keys] = heads
1327
def cache(self, keys, heads):
1328
"""Store a known value."""
1329
self._heads[frozenset(keys)] = frozenset(heads)
1332
class _BreadthFirstSearcher(object):
1333
"""Parallel search breadth-first the ancestry of revisions.
1335
This class implements the iterator protocol, but additionally
1336
1. provides a set of seen ancestors, and
1337
2. allows some ancestries to be unsearched, via stop_searching_any
1340
def __init__(self, revisions, parents_provider):
1341
self._iterations = 0
1342
self._next_query = set(revisions)
1344
self._started_keys = set(self._next_query)
1345
self._stopped_keys = set()
1346
self._parents_provider = parents_provider
1347
self._returning = 'next_with_ghosts'
1348
self._current_present = set()
1349
self._current_ghosts = set()
1350
self._current_parents = {}
1353
if self._iterations:
1354
prefix = "searching"
1357
search = '%s=%r' % (prefix, list(self._next_query))
1358
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1359
' seen=%r)' % (self._iterations, search, list(self.seen)))
1361
def get_state(self):
1362
"""Get the current state of this searcher.
1364
:return: Tuple with started keys, excludes and included keys
1366
if self._returning == 'next':
1367
# We have to know the current nodes children to be able to list the
1368
# exclude keys for them. However, while we could have a second
1369
# look-ahead result buffer and shuffle things around, this method
1370
# is typically only called once per search - when memoising the
1371
# results of the search.
1372
found, ghosts, next, parents = self._do_query(self._next_query)
1373
# pretend we didn't query: perhaps we should tweak _do_query to be
1374
# entirely stateless?
1375
self.seen.difference_update(next)
1376
next_query = next.union(ghosts)
1378
next_query = self._next_query
1379
excludes = self._stopped_keys.union(next_query)
1380
included_keys = self.seen.difference(excludes)
1381
return self._started_keys, excludes, included_keys
1386
except StopIteration:
1390
"""Return the next ancestors of this revision.
1392
Ancestors are returned in the order they are seen in a breadth-first
1393
traversal. No ancestor will be returned more than once. Ancestors are
1394
returned before their parentage is queried, so ghosts and missing
1395
revisions (including the start revisions) are included in the result.
1396
This can save a round trip in LCA style calculation by allowing
1397
convergence to be detected without reading the data for the revision
1398
the convergence occurs on.
1400
:return: A set of revision_ids.
1402
if self._returning != 'next':
1403
# switch to returning the query, not the results.
1404
self._returning = 'next'
1405
self._iterations += 1
1408
if len(self._next_query) == 0:
1409
raise StopIteration()
1410
# We have seen what we're querying at this point as we are returning
1411
# the query, not the results.
1412
self.seen.update(self._next_query)
1413
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 viewitems(parent_map):
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 viewvalues(parent_map):
1513
all_parents.extend(parent_ids)
1514
next_pending = all_seen.intersection(
1515
all_parents).difference(seen_ancestors)
1516
seen_ancestors.update(next_pending)
1517
next_pending.difference_update(not_searched_yet)
1518
pending = next_pending
1520
return seen_ancestors
1522
def stop_searching_any(self, revisions):
1524
Remove any of the specified revisions from the search list.
1526
None of the specified revisions are required to be present in the
1529
It is okay to call stop_searching_any() for revisions which were seen
1530
in previous iterations. It is the callers responsibility to call
1531
find_seen_ancestors() to make sure that current search tips that are
1532
ancestors of those revisions are also stopped. All explicitly stopped
1533
revisions will be excluded from the search result's get_keys(), though.
1535
# TODO: does this help performance?
1538
revisions = frozenset(revisions)
1539
if self._returning == 'next':
1540
stopped = self._next_query.intersection(revisions)
1541
self._next_query = self._next_query.difference(revisions)
1543
stopped_present = self._current_present.intersection(revisions)
1544
stopped = stopped_present.union(
1545
self._current_ghosts.intersection(revisions))
1546
self._current_present.difference_update(stopped)
1547
self._current_ghosts.difference_update(stopped)
1548
# stopping 'x' should stop returning parents of 'x', but
1549
# not if 'y' always references those same parents
1550
stop_rev_references = {}
1551
for rev in stopped_present:
1552
for parent_id in self._current_parents[rev]:
1553
if parent_id not in stop_rev_references:
1554
stop_rev_references[parent_id] = 0
1555
stop_rev_references[parent_id] += 1
1556
# if only the stopped revisions reference it, the ref count will be
1558
for parents in viewvalues(self._current_parents):
1559
for parent_id in parents:
1561
stop_rev_references[parent_id] -= 1
1564
stop_parents = set()
1565
for rev_id, refs in viewitems(stop_rev_references):
1567
stop_parents.add(rev_id)
1568
self._next_query.difference_update(stop_parents)
1569
self._stopped_keys.update(stopped)
1570
self._stopped_keys.update(revisions)
1573
def start_searching(self, revisions):
1574
"""Add revisions to the search.
1576
The parents of revisions will be returned from the next call to next()
1577
or next_with_ghosts(). If next_with_ghosts was the most recently used
1578
next* call then the return value is the result of looking up the
1579
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1581
revisions = frozenset(revisions)
1582
self._started_keys.update(revisions)
1583
new_revisions = revisions.difference(self.seen)
1584
if self._returning == 'next':
1585
self._next_query.update(new_revisions)
1586
self.seen.update(new_revisions)
1588
# perform a query on revisions
1589
revs, ghosts, query, parents = self._do_query(revisions)
1590
self._stopped_keys.update(ghosts)
1591
self._current_present.update(revs)
1592
self._current_ghosts.update(ghosts)
1593
self._next_query.update(query)
1594
self._current_parents.update(parents)
1598
def invert_parent_map(parent_map):
1599
"""Given a map from child => parents, create a map of parent=>children"""
1601
for child, parents in viewitems(parent_map):
1603
# Any given parent is likely to have only a small handful
1604
# of children, many will have only one. So we avoid mem overhead of
1605
# a list, in exchange for extra copying of tuples
1606
if p not in child_map:
1607
child_map[p] = (child,)
1609
child_map[p] = child_map[p] + (child,)
1613
def collapse_linear_regions(parent_map):
1614
"""Collapse regions of the graph that are 'linear'.
1620
can be collapsed by removing B and getting::
1624
:param parent_map: A dictionary mapping children to their parents
1625
:return: Another dictionary with 'linear' chains collapsed
1627
# Note: this isn't a strictly minimal collapse. For example:
1635
# Will not have 'D' removed, even though 'E' could fit. Also:
1641
# A and C are both kept because they are edges of the graph. We *could* get
1642
# rid of A if we wanted.
1650
# Will not have any nodes removed, even though you do have an
1651
# 'uninteresting' linear D->B and E->C
1653
for child, parents in viewitems(parent_map):
1654
children.setdefault(child, [])
1656
children.setdefault(p, []).append(child)
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 {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 ._known_graph_pyx import KnownGraph
1713
except ImportError as e:
1714
osutils.failed_to_load_extension(e)
1715
from ._known_graph_py import KnownGraph # noqa: F401
added
removed
breezy/graph.py
