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:
122
new_found = parents_provider.get_parent_map(remaining)
123
found.update(new_found)
124
remaining.difference_update(new_found)
130
class CachingParentsProvider(object):
131
"""A parents provider which will cache the revision => parents as a dict.
133
This is useful for providers which have an expensive look up.
135
Either a ParentsProvider or a get_parent_map-like callback may be
136
supplied. If it provides extra un-asked-for parents, they will be cached,
137
but filtered out of get_parent_map.
139
The cache is enabled by default, but may be disabled and re-enabled.
141
def __init__(self, parent_provider=None, get_parent_map=None):
144
:param parent_provider: The ParentProvider to use. It or
145
get_parent_map must be supplied.
146
:param get_parent_map: The get_parent_map callback to use. It or
147
parent_provider must be supplied.
149
self._real_provider = parent_provider
150
if get_parent_map is None:
151
self._get_parent_map = self._real_provider.get_parent_map
153
self._get_parent_map = get_parent_map
155
self.enable_cache(True)
158
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
160
def enable_cache(self, cache_misses=True):
162
if self._cache is not None:
163
raise AssertionError('Cache enabled when already enabled.')
165
self._cache_misses = cache_misses
166
self.missing_keys = set()
168
def disable_cache(self):
169
"""Disable and clear the cache."""
171
self._cache_misses = None
172
self.missing_keys = set()
174
def get_cached_map(self):
175
"""Return any cached get_parent_map values."""
176
if self._cache is None:
178
return dict(self._cache)
180
def get_cached_parent_map(self, keys):
181
"""Return items from the cache.
183
This returns the same info as get_parent_map, but explicitly does not
184
invoke the supplied ParentsProvider to search for uncached values.
189
return dict([(key, cache[key]) for key in keys if key in cache])
191
def get_parent_map(self, keys):
192
"""See StackedParentsProvider.get_parent_map."""
195
cache = self._get_parent_map(keys)
197
needed_revisions = set(key for key in keys if key not in cache)
198
# Do not ask for negatively cached keys
199
needed_revisions.difference_update(self.missing_keys)
201
parent_map = self._get_parent_map(needed_revisions)
202
cache.update(parent_map)
203
if self._cache_misses:
204
for key in needed_revisions:
205
if key not in parent_map:
206
self.note_missing_key(key)
209
value = cache.get(key)
210
if value is not None:
214
def note_missing_key(self, key):
215
"""Note that key is a missing key."""
216
if self._cache_misses:
217
self.missing_keys.add(key)
220
class CallableToParentsProviderAdapter(object):
221
"""A parents provider that adapts any callable to the parents provider API.
223
i.e. it accepts calls to self.get_parent_map and relays them to the
224
callable it was constructed with.
227
def __init__(self, a_callable):
228
self.callable = a_callable
231
return "%s(%r)" % (self.__class__.__name__, self.callable)
233
def get_parent_map(self, keys):
234
return self.callable(keys)
238
"""Provide incremental access to revision graphs.
240
This is the generic implementation; it is intended to be subclassed to
241
specialize it for other repository types.
244
def __init__(self, parents_provider):
245
"""Construct a Graph that uses several graphs as its input
247
This should not normally be invoked directly, because there may be
248
specialized implementations for particular repository types. See
249
Repository.get_graph().
251
:param parents_provider: An object providing a get_parent_map call
252
conforming to the behavior of
253
StackedParentsProvider.get_parent_map.
255
if getattr(parents_provider, 'get_parents', None) is not None:
256
self.get_parents = parents_provider.get_parents
257
if getattr(parents_provider, 'get_parent_map', None) is not None:
258
self.get_parent_map = parents_provider.get_parent_map
259
self._parents_provider = parents_provider
262
return 'Graph(%r)' % self._parents_provider
264
def find_lca(self, *revisions):
265
"""Determine the lowest common ancestors of the provided revisions
267
A lowest common ancestor is a common ancestor none of whose
268
descendants are common ancestors. In graphs, unlike trees, there may
269
be multiple lowest common ancestors.
271
This algorithm has two phases. Phase 1 identifies border ancestors,
272
and phase 2 filters border ancestors to determine lowest common
275
In phase 1, border ancestors are identified, using a breadth-first
276
search starting at the bottom of the graph. Searches are stopped
277
whenever a node or one of its descendants is determined to be common
279
In phase 2, the border ancestors are filtered to find the least
280
common ancestors. This is done by searching the ancestries of each
283
Phase 2 is perfomed on the principle that a border ancestor that is
284
not an ancestor of any other border ancestor is a least common
287
Searches are stopped when they find a node that is determined to be a
288
common ancestor of all border ancestors, because this shows that it
289
cannot be a descendant of any border ancestor.
291
The scaling of this operation should be proportional to:
293
1. The number of uncommon ancestors
294
2. The number of border ancestors
295
3. The length of the shortest path between a border ancestor and an
296
ancestor of all border ancestors.
298
border_common, common, sides = self._find_border_ancestors(revisions)
299
# We may have common ancestors that can be reached from each other.
300
# - ask for the heads of them to filter it down to only ones that
301
# cannot be reached from each other - phase 2.
302
return self.heads(border_common)
304
def find_difference(self, left_revision, right_revision):
305
"""Determine the graph difference between two revisions"""
306
border, common, searchers = self._find_border_ancestors(
307
[left_revision, right_revision])
308
self._search_for_extra_common(common, searchers)
309
left = searchers[0].seen
310
right = searchers[1].seen
311
return (left.difference(right), right.difference(left))
313
def find_descendants(self, old_key, new_key):
314
"""Find descendants of old_key that are ancestors of new_key."""
315
child_map = self.get_child_map(self._find_descendant_ancestors(
317
graph = Graph(DictParentsProvider(child_map))
318
searcher = graph._make_breadth_first_searcher([old_key])
322
def _find_descendant_ancestors(self, old_key, new_key):
323
"""Find ancestors of new_key that may be descendants of old_key."""
324
stop = self._make_breadth_first_searcher([old_key])
325
descendants = self._make_breadth_first_searcher([new_key])
326
for revisions in descendants:
327
old_stop = stop.seen.intersection(revisions)
328
descendants.stop_searching_any(old_stop)
329
seen_stop = descendants.find_seen_ancestors(stop.step())
330
descendants.stop_searching_any(seen_stop)
331
return descendants.seen.difference(stop.seen)
333
def get_child_map(self, keys):
334
"""Get a mapping from parents to children of the specified keys.
336
This is simply the inversion of get_parent_map. Only supplied keys
337
will be discovered as children.
338
:return: a dict of key:child_list for keys.
340
parent_map = self._parents_provider.get_parent_map(keys)
342
for child, parents in sorted(viewitems(parent_map)):
343
for parent in parents:
344
parent_child.setdefault(parent, []).append(child)
347
def find_distance_to_null(self, target_revision_id, known_revision_ids):
348
"""Find the left-hand distance to the NULL_REVISION.
350
(This can also be considered the revno of a branch at
353
:param target_revision_id: A revision_id which we would like to know
355
:param known_revision_ids: [(revision_id, revno)] A list of known
356
revno, revision_id tuples. We'll use this to seed the search.
358
# Map from revision_ids to a known value for their revno
359
known_revnos = dict(known_revision_ids)
360
cur_tip = target_revision_id
362
NULL_REVISION = revision.NULL_REVISION
363
known_revnos[NULL_REVISION] = 0
365
searching_known_tips = list(known_revnos)
367
unknown_searched = {}
369
while cur_tip not in known_revnos:
370
unknown_searched[cur_tip] = num_steps
372
to_search = {cur_tip}
373
to_search.update(searching_known_tips)
374
parent_map = self.get_parent_map(to_search)
375
parents = parent_map.get(cur_tip, None)
376
if not parents: # An empty list or None is a ghost
377
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
381
for revision_id in searching_known_tips:
382
parents = parent_map.get(revision_id, None)
386
next_revno = known_revnos[revision_id] - 1
387
if next in unknown_searched:
388
# We have enough information to return a value right now
389
return next_revno + unknown_searched[next]
390
if next in known_revnos:
392
known_revnos[next] = next_revno
393
next_known_tips.append(next)
394
searching_known_tips = next_known_tips
396
# We reached a known revision, so just add in how many steps it took to
398
return known_revnos[cur_tip] + num_steps
400
def find_lefthand_distances(self, keys):
401
"""Find the distance to null for all the keys in keys.
403
:param keys: keys to lookup.
404
:return: A dict key->distance for all of keys.
406
# Optimisable by concurrent searching, but a random spread should get
407
# some sort of hit rate.
414
(key, self.find_distance_to_null(key, known_revnos)))
415
except errors.GhostRevisionsHaveNoRevno:
418
known_revnos.append((key, -1))
419
return dict(known_revnos)
421
def find_unique_ancestors(self, unique_revision, common_revisions):
422
"""Find the unique ancestors for a revision versus others.
424
This returns the ancestry of unique_revision, excluding all revisions
425
in the ancestry of common_revisions. If unique_revision is in the
426
ancestry, then the empty set will be returned.
428
:param unique_revision: The revision_id whose ancestry we are
430
(XXX: Would this API be better if we allowed multiple revisions on
431
to be searched here?)
432
:param common_revisions: Revision_ids of ancestries to exclude.
433
:return: A set of revisions in the ancestry of unique_revision
435
if unique_revision in common_revisions:
438
# Algorithm description
439
# 1) Walk backwards from the unique node and all common nodes.
440
# 2) When a node is seen by both sides, stop searching it in the unique
441
# walker, include it in the common walker.
442
# 3) Stop searching when there are no nodes left for the unique walker.
443
# At this point, you have a maximal set of unique nodes. Some of
444
# them may actually be common, and you haven't reached them yet.
445
# 4) Start new searchers for the unique nodes, seeded with the
446
# information you have so far.
447
# 5) Continue searching, stopping the common searches when the search
448
# tip is an ancestor of all unique nodes.
449
# 6) Aggregate together unique searchers when they are searching the
450
# same tips. When all unique searchers are searching the same node,
451
# stop move it to a single 'all_unique_searcher'.
452
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
453
# Most of the time this produces very little important information.
454
# So don't step it as quickly as the other searchers.
455
# 8) Search is done when all common searchers have completed.
457
unique_searcher, common_searcher = self._find_initial_unique_nodes(
458
[unique_revision], common_revisions)
460
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
464
(all_unique_searcher,
465
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
466
unique_searcher, common_searcher)
468
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
469
unique_tip_searchers, common_searcher)
470
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
471
if 'graph' in debug.debug_flags:
472
trace.mutter('Found %d truly unique nodes out of %d',
473
len(true_unique_nodes), len(unique_nodes))
474
return true_unique_nodes
476
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
477
"""Steps 1-3 of find_unique_ancestors.
479
Find the maximal set of unique nodes. Some of these might actually
480
still be common, but we are sure that there are no other unique nodes.
482
:return: (unique_searcher, common_searcher)
485
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
486
# we know that unique_revisions aren't in common_revisions, so skip
488
next(unique_searcher)
489
common_searcher = self._make_breadth_first_searcher(common_revisions)
491
# As long as we are still finding unique nodes, keep searching
492
while unique_searcher._next_query:
493
next_unique_nodes = set(unique_searcher.step())
494
next_common_nodes = set(common_searcher.step())
496
# Check if either searcher encounters new nodes seen by the other
498
unique_are_common_nodes = next_unique_nodes.intersection(
499
common_searcher.seen)
500
unique_are_common_nodes.update(
501
next_common_nodes.intersection(unique_searcher.seen))
502
if unique_are_common_nodes:
503
ancestors = unique_searcher.find_seen_ancestors(
504
unique_are_common_nodes)
505
# TODO: This is a bit overboard, we only really care about
506
# the ancestors of the tips because the rest we
507
# already know. This is *correct* but causes us to
508
# search too much ancestry.
509
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
510
unique_searcher.stop_searching_any(ancestors)
511
common_searcher.start_searching(ancestors)
513
return unique_searcher, common_searcher
515
def _make_unique_searchers(self, unique_nodes, unique_searcher,
517
"""Create a searcher for all the unique search tips (step 4).
519
As a side effect, the common_searcher will stop searching any nodes
520
that are ancestors of the unique searcher tips.
522
:return: (all_unique_searcher, unique_tip_searchers)
524
unique_tips = self._remove_simple_descendants(unique_nodes,
525
self.get_parent_map(unique_nodes))
527
if len(unique_tips) == 1:
528
unique_tip_searchers = []
529
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
531
unique_tip_searchers = []
532
for tip in unique_tips:
533
revs_to_search = unique_searcher.find_seen_ancestors([tip])
534
revs_to_search.update(
535
common_searcher.find_seen_ancestors(revs_to_search))
536
searcher = self._make_breadth_first_searcher(revs_to_search)
537
# We don't care about the starting nodes.
538
searcher._label = tip
540
unique_tip_searchers.append(searcher)
542
ancestor_all_unique = None
543
for searcher in unique_tip_searchers:
544
if ancestor_all_unique is None:
545
ancestor_all_unique = set(searcher.seen)
547
ancestor_all_unique = ancestor_all_unique.intersection(
549
# Collapse all the common nodes into a single searcher
550
all_unique_searcher = self._make_breadth_first_searcher(
552
if ancestor_all_unique:
553
# We've seen these nodes in all the searchers, so we'll just go to
555
all_unique_searcher.step()
557
# Stop any search tips that are already known as ancestors of the
559
stopped_common = common_searcher.stop_searching_any(
560
common_searcher.find_seen_ancestors(ancestor_all_unique))
563
for searcher in unique_tip_searchers:
564
total_stopped += len(searcher.stop_searching_any(
565
searcher.find_seen_ancestors(ancestor_all_unique)))
566
if 'graph' in debug.debug_flags:
567
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
568
' (%d stopped search tips, %d common ancestors'
569
' (%d stopped common)',
570
len(unique_nodes), len(unique_tip_searchers),
571
total_stopped, len(ancestor_all_unique),
573
return all_unique_searcher, unique_tip_searchers
575
def _step_unique_and_common_searchers(self, common_searcher,
576
unique_tip_searchers,
578
"""Step all the searchers"""
579
newly_seen_common = set(common_searcher.step())
580
newly_seen_unique = set()
581
for searcher in unique_tip_searchers:
582
next = set(searcher.step())
583
next.update(unique_searcher.find_seen_ancestors(next))
584
next.update(common_searcher.find_seen_ancestors(next))
585
for alt_searcher in unique_tip_searchers:
586
if alt_searcher is searcher:
588
next.update(alt_searcher.find_seen_ancestors(next))
589
searcher.start_searching(next)
590
newly_seen_unique.update(next)
591
return newly_seen_common, newly_seen_unique
593
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
595
newly_seen_unique, step_all_unique):
596
"""Find nodes that are common to all unique_tip_searchers.
598
If it is time, step the all_unique_searcher, and add its nodes to the
601
common_to_all_unique_nodes = newly_seen_unique.copy()
602
for searcher in unique_tip_searchers:
603
common_to_all_unique_nodes.intersection_update(searcher.seen)
604
common_to_all_unique_nodes.intersection_update(
605
all_unique_searcher.seen)
606
# Step all-unique less frequently than the other searchers.
607
# In the common case, we don't need to spider out far here, so
608
# avoid doing extra work.
610
tstart = time.clock()
611
nodes = all_unique_searcher.step()
612
common_to_all_unique_nodes.update(nodes)
613
if 'graph' in debug.debug_flags:
614
tdelta = time.clock() - tstart
615
trace.mutter('all_unique_searcher step() took %.3fs'
616
'for %d nodes (%d total), iteration: %s',
617
tdelta, len(nodes), len(all_unique_searcher.seen),
618
all_unique_searcher._iterations)
619
return common_to_all_unique_nodes
621
def _collapse_unique_searchers(self, unique_tip_searchers,
622
common_to_all_unique_nodes):
623
"""Combine searchers that are searching the same tips.
625
When two searchers are searching the same tips, we can stop one of the
626
searchers. We also know that the maximal set of common ancestors is the
627
intersection of the two original searchers.
629
:return: A list of searchers that are searching unique nodes.
631
# Filter out searchers that don't actually search different
632
# nodes. We already have the ancestry intersection for them
633
unique_search_tips = {}
634
for searcher in unique_tip_searchers:
635
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
636
will_search_set = frozenset(searcher._next_query)
637
if not will_search_set:
638
if 'graph' in debug.debug_flags:
639
trace.mutter('Unique searcher %s was stopped.'
640
' (%s iterations) %d nodes stopped',
642
searcher._iterations,
644
elif will_search_set not in unique_search_tips:
645
# This searcher is searching a unique set of nodes, let it
646
unique_search_tips[will_search_set] = [searcher]
648
unique_search_tips[will_search_set].append(searcher)
649
# TODO: it might be possible to collapse searchers faster when they
650
# only have *some* search tips in common.
651
next_unique_searchers = []
652
for searchers in viewvalues(unique_search_tips):
653
if len(searchers) == 1:
654
# Searching unique tips, go for it
655
next_unique_searchers.append(searchers[0])
657
# These searchers have started searching the same tips, we
658
# don't need them to cover the same ground. The
659
# intersection of their ancestry won't change, so create a
660
# new searcher, combining their histories.
661
next_searcher = searchers[0]
662
for searcher in searchers[1:]:
663
next_searcher.seen.intersection_update(searcher.seen)
664
if 'graph' in debug.debug_flags:
665
trace.mutter('Combining %d searchers into a single'
666
' searcher searching %d nodes with'
669
len(next_searcher._next_query),
670
len(next_searcher.seen))
671
next_unique_searchers.append(next_searcher)
672
return next_unique_searchers
674
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
675
unique_tip_searchers, common_searcher):
676
"""Steps 5-8 of find_unique_ancestors.
678
This function returns when common_searcher has stopped searching for
681
# We step the ancestor_all_unique searcher only every
682
# STEP_UNIQUE_SEARCHER_EVERY steps.
683
step_all_unique_counter = 0
684
# While we still have common nodes to search
685
while common_searcher._next_query:
687
newly_seen_unique) = self._step_unique_and_common_searchers(
688
common_searcher, unique_tip_searchers, unique_searcher)
689
# These nodes are common ancestors of all unique nodes
690
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
691
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
692
step_all_unique_counter==0)
693
step_all_unique_counter = ((step_all_unique_counter + 1)
694
% STEP_UNIQUE_SEARCHER_EVERY)
696
if newly_seen_common:
697
# If a 'common' node is an ancestor of all unique searchers, we
698
# can stop searching it.
699
common_searcher.stop_searching_any(
700
all_unique_searcher.seen.intersection(newly_seen_common))
701
if common_to_all_unique_nodes:
702
common_to_all_unique_nodes.update(
703
common_searcher.find_seen_ancestors(
704
common_to_all_unique_nodes))
705
# The all_unique searcher can start searching the common nodes
706
# but everyone else can stop.
707
# This is the sort of thing where we would like to not have it
708
# start_searching all of the nodes, but only mark all of them
709
# as seen, and have it search only the actual tips. Otherwise
710
# it is another get_parent_map() traversal for it to figure out
711
# what we already should know.
712
all_unique_searcher.start_searching(common_to_all_unique_nodes)
713
common_searcher.stop_searching_any(common_to_all_unique_nodes)
715
next_unique_searchers = self._collapse_unique_searchers(
716
unique_tip_searchers, common_to_all_unique_nodes)
717
if len(unique_tip_searchers) != len(next_unique_searchers):
718
if 'graph' in debug.debug_flags:
719
trace.mutter('Collapsed %d unique searchers => %d'
721
len(unique_tip_searchers),
722
len(next_unique_searchers),
723
all_unique_searcher._iterations)
724
unique_tip_searchers = next_unique_searchers
726
def get_parent_map(self, revisions):
727
"""Get a map of key:parent_list for revisions.
729
This implementation delegates to get_parents, for old parent_providers
730
that do not supply get_parent_map.
733
for rev, parents in self.get_parents(revisions):
734
if parents is not None:
735
result[rev] = parents
738
def _make_breadth_first_searcher(self, revisions):
739
return _BreadthFirstSearcher(revisions, self)
741
def _find_border_ancestors(self, revisions):
742
"""Find common ancestors with at least one uncommon descendant.
744
Border ancestors are identified using a breadth-first
745
search starting at the bottom of the graph. Searches are stopped
746
whenever a node or one of its descendants is determined to be common.
748
This will scale with the number of uncommon ancestors.
750
As well as the border ancestors, a set of seen common ancestors and a
751
list of sets of seen ancestors for each input revision is returned.
752
This allows calculation of graph difference from the results of this
755
if None in revisions:
756
raise errors.InvalidRevisionId(None, self)
757
common_ancestors = set()
758
searchers = [self._make_breadth_first_searcher([r])
760
active_searchers = searchers[:]
761
border_ancestors = set()
765
for searcher in searchers:
766
new_ancestors = searcher.step()
768
newly_seen.update(new_ancestors)
770
for revision in newly_seen:
771
if revision in common_ancestors:
772
# Not a border ancestor because it was seen as common
774
new_common.add(revision)
776
for searcher in searchers:
777
if revision not in searcher.seen:
780
# This is a border because it is a first common that we see
781
# after walking for a while.
782
border_ancestors.add(revision)
783
new_common.add(revision)
785
for searcher in searchers:
786
new_common.update(searcher.find_seen_ancestors(new_common))
787
for searcher in searchers:
788
searcher.start_searching(new_common)
789
common_ancestors.update(new_common)
791
# Figure out what the searchers will be searching next, and if
792
# there is only 1 set being searched, then we are done searching,
793
# since all searchers would have to be searching the same data,
794
# thus it *must* be in common.
795
unique_search_sets = set()
796
for searcher in searchers:
797
will_search_set = frozenset(searcher._next_query)
798
if will_search_set not in unique_search_sets:
799
# This searcher is searching a unique set of nodes, let it
800
unique_search_sets.add(will_search_set)
802
if len(unique_search_sets) == 1:
803
nodes = unique_search_sets.pop()
804
uncommon_nodes = nodes.difference(common_ancestors)
806
raise AssertionError("Somehow we ended up converging"
807
" without actually marking them as"
810
"\nuncommon_nodes: %s"
811
% (revisions, uncommon_nodes))
813
return border_ancestors, common_ancestors, searchers
815
def heads(self, keys):
816
"""Return the heads from amongst keys.
818
This is done by searching the ancestries of each key. Any key that is
819
reachable from another key is not returned; all the others are.
821
This operation scales with the relative depth between any two keys. If
822
any two keys are completely disconnected all ancestry of both sides
825
:param keys: An iterable of keys.
826
:return: A set of the heads. Note that as a set there is no ordering
827
information. Callers will need to filter their input to create
828
order if they need it.
830
candidate_heads = set(keys)
831
if revision.NULL_REVISION in candidate_heads:
832
# NULL_REVISION is only a head if it is the only entry
833
candidate_heads.remove(revision.NULL_REVISION)
834
if not candidate_heads:
835
return {revision.NULL_REVISION}
836
if len(candidate_heads) < 2:
837
return candidate_heads
838
searchers = dict((c, self._make_breadth_first_searcher([c]))
839
for c in candidate_heads)
840
active_searchers = dict(searchers)
841
# skip over the actual candidate for each searcher
842
for searcher in viewvalues(active_searchers):
844
# The common walker finds nodes that are common to two or more of the
845
# input keys, so that we don't access all history when a currently
846
# uncommon search point actually meets up with something behind a
847
# common search point. Common search points do not keep searches
848
# active; they just allow us to make searches inactive without
849
# accessing all history.
850
common_walker = self._make_breadth_first_searcher([])
851
while len(active_searchers) > 0:
856
except StopIteration:
857
# No common points being searched at this time.
859
for candidate in list(active_searchers):
861
searcher = active_searchers[candidate]
863
# rare case: we deleted candidate in a previous iteration
864
# through this for loop, because it was determined to be
865
# a descendant of another candidate.
868
ancestors.update(next(searcher))
869
except StopIteration:
870
del active_searchers[candidate]
872
# process found nodes
874
for ancestor in ancestors:
875
if ancestor in candidate_heads:
876
candidate_heads.remove(ancestor)
877
del searchers[ancestor]
878
if ancestor in active_searchers:
879
del active_searchers[ancestor]
880
# it may meet up with a known common node
881
if ancestor in common_walker.seen:
882
# some searcher has encountered our known common nodes:
884
ancestor_set = {ancestor}
885
for searcher in viewvalues(searchers):
886
searcher.stop_searching_any(ancestor_set)
888
# or it may have been just reached by all the searchers:
889
for searcher in viewvalues(searchers):
890
if ancestor not in searcher.seen:
893
# The final active searcher has just reached this node,
894
# making it be known as a descendant of all candidates,
895
# so we can stop searching it, and any seen ancestors
896
new_common.add(ancestor)
897
for searcher in viewvalues(searchers):
899
searcher.find_seen_ancestors([ancestor])
900
searcher.stop_searching_any(seen_ancestors)
901
common_walker.start_searching(new_common)
902
return candidate_heads
904
def find_merge_order(self, tip_revision_id, lca_revision_ids):
905
"""Find the order that each revision was merged into tip.
907
This basically just walks backwards with a stack, and walks left-first
908
until it finds a node to stop.
910
if len(lca_revision_ids) == 1:
911
return list(lca_revision_ids)
912
looking_for = set(lca_revision_ids)
913
# TODO: Is there a way we could do this "faster" by batching up the
914
# get_parent_map requests?
915
# TODO: Should we also be culling the ancestry search right away? We
916
# could add looking_for to the "stop" list, and walk their
917
# ancestry in batched mode. The flip side is it might mean we walk a
918
# lot of "stop" nodes, rather than only the minimum.
919
# Then again, without it we may trace back into ancestry we could have
921
stack = [tip_revision_id]
924
while stack and looking_for:
927
if next in looking_for:
929
looking_for.remove(next)
930
if len(looking_for) == 1:
931
found.append(looking_for.pop())
934
parent_ids = self.get_parent_map([next]).get(next, None)
935
if not parent_ids: # Ghost, nothing to search here
937
for parent_id in reversed(parent_ids):
938
# TODO: (performance) We see the parent at this point, but we
939
# wait to mark it until later to make sure we get left
940
# parents before right parents. However, instead of
941
# waiting until we have traversed enough parents, we
942
# could instead note that we've found it, and once all
943
# parents are in the stack, just reverse iterate the
945
if parent_id not in stop:
946
# this will need to be searched
947
stack.append(parent_id)
951
def find_lefthand_merger(self, merged_key, tip_key):
952
"""Find the first lefthand ancestor of tip_key that merged merged_key.
954
We do this by first finding the descendants of merged_key, then
955
walking through the lefthand ancestry of tip_key until we find a key
956
that doesn't descend from merged_key. Its child is the key that
959
:return: The first lefthand ancestor of tip_key to merge merged_key.
960
merged_key if it is a lefthand ancestor of tip_key.
961
None if no ancestor of tip_key merged merged_key.
963
descendants = self.find_descendants(merged_key, tip_key)
964
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
965
last_candidate = None
966
for candidate in candidate_iterator:
967
if candidate not in descendants:
968
return last_candidate
969
last_candidate = candidate
971
def find_unique_lca(self, left_revision, right_revision,
973
"""Find a unique LCA.
975
Find lowest common ancestors. If there is no unique common
976
ancestor, find the lowest common ancestors of those ancestors.
978
Iteration stops when a unique lowest common ancestor is found.
979
The graph origin is necessarily a unique lowest common ancestor.
981
Note that None is not an acceptable substitute for NULL_REVISION.
982
in the input for this method.
984
:param count_steps: If True, the return value will be a tuple of
985
(unique_lca, steps) where steps is the number of times that
986
find_lca was run. If False, only unique_lca is returned.
988
revisions = [left_revision, right_revision]
992
lca = self.find_lca(*revisions)
1000
raise errors.NoCommonAncestor(left_revision, right_revision)
1003
def iter_ancestry(self, revision_ids):
1004
"""Iterate the ancestry of this revision.
1006
:param revision_ids: Nodes to start the search
1007
:return: Yield tuples mapping a revision_id to its parents for the
1008
ancestry of revision_id.
1009
Ghosts will be returned with None as their parents, and nodes
1010
with no parents will have NULL_REVISION as their only parent. (As
1011
defined by get_parent_map.)
1012
There will also be a node for (NULL_REVISION, ())
1014
pending = set(revision_ids)
1017
processed.update(pending)
1018
next_map = self.get_parent_map(pending)
1019
next_pending = set()
1020
for item in viewitems(next_map):
1022
next_pending.update(p for p in item[1] if p not in processed)
1023
ghosts = pending.difference(next_map)
1024
for ghost in ghosts:
1026
pending = next_pending
1028
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1029
if stop_keys is None:
1031
next_key = start_key
1032
def get_parents(key):
1034
return self._parents_provider.get_parent_map([key])[key]
1036
raise errors.RevisionNotPresent(next_key, self)
1038
if next_key in stop_keys:
1040
parents = get_parents(next_key)
1042
if len(parents) == 0:
1045
next_key = parents[0]
1047
def iter_topo_order(self, revisions):
1048
"""Iterate through the input revisions in topological order.
1050
This sorting only ensures that parents come before their children.
1051
An ancestor may sort after a descendant if the relationship is not
1052
visible in the supplied list of revisions.
1054
from breezy import tsort
1055
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1056
return sorter.iter_topo_order()
1058
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1059
"""Determine whether a revision is an ancestor of another.
1061
We answer this using heads() as heads() has the logic to perform the
1062
smallest number of parent lookups to determine the ancestral
1063
relationship between N revisions.
1065
return {candidate_descendant} == self.heads(
1066
[candidate_ancestor, candidate_descendant])
1068
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1069
"""Determine whether a revision is between two others.
1071
returns true if and only if:
1072
lower_bound_revid <= revid <= upper_bound_revid
1074
return ((upper_bound_revid is None or
1075
self.is_ancestor(revid, upper_bound_revid)) and
1076
(lower_bound_revid is None or
1077
self.is_ancestor(lower_bound_revid, revid)))
1079
def _search_for_extra_common(self, common, searchers):
1080
"""Make sure that unique nodes are genuinely unique.
1082
After _find_border_ancestors, all nodes marked "common" are indeed
1083
common. Some of the nodes considered unique are not, due to history
1084
shortcuts stopping the searches early.
1086
We know that we have searched enough when all common search tips are
1087
descended from all unique (uncommon) nodes because we know that a node
1088
cannot be an ancestor of its own ancestor.
1090
:param common: A set of common nodes
1091
:param searchers: The searchers returned from _find_border_ancestors
1094
# Basic algorithm...
1095
# A) The passed in searchers should all be on the same tips, thus
1096
# they should be considered the "common" searchers.
1097
# B) We find the difference between the searchers, these are the
1098
# "unique" nodes for each side.
1099
# C) We do a quick culling so that we only start searching from the
1100
# more interesting unique nodes. (A unique ancestor is more
1101
# interesting than any of its children.)
1102
# D) We start searching for ancestors common to all unique nodes.
1103
# E) We have the common searchers stop searching any ancestors of
1104
# nodes found by (D)
1105
# F) When there are no more common search tips, we stop
1107
# TODO: We need a way to remove unique_searchers when they overlap with
1108
# other unique searchers.
1109
if len(searchers) != 2:
1110
raise NotImplementedError(
1111
"Algorithm not yet implemented for > 2 searchers")
1112
common_searchers = searchers
1113
left_searcher = searchers[0]
1114
right_searcher = searchers[1]
1115
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1116
if not unique: # No unique nodes, nothing to do
1118
total_unique = len(unique)
1119
unique = self._remove_simple_descendants(unique,
1120
self.get_parent_map(unique))
1121
simple_unique = len(unique)
1123
unique_searchers = []
1124
for revision_id in unique:
1125
if revision_id in left_searcher.seen:
1126
parent_searcher = left_searcher
1128
parent_searcher = right_searcher
1129
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1130
if not revs_to_search: # XXX: This shouldn't be possible
1131
revs_to_search = [revision_id]
1132
searcher = self._make_breadth_first_searcher(revs_to_search)
1133
# We don't care about the starting nodes.
1135
unique_searchers.append(searcher)
1137
# possible todo: aggregate the common searchers into a single common
1138
# searcher, just make sure that we include the nodes into the .seen
1139
# properties of the original searchers
1141
ancestor_all_unique = None
1142
for searcher in unique_searchers:
1143
if ancestor_all_unique is None:
1144
ancestor_all_unique = set(searcher.seen)
1146
ancestor_all_unique = ancestor_all_unique.intersection(
1149
trace.mutter('Started %s unique searchers for %s unique revisions',
1150
simple_unique, total_unique)
1152
while True: # If we have no more nodes we have nothing to do
1153
newly_seen_common = set()
1154
for searcher in common_searchers:
1155
newly_seen_common.update(searcher.step())
1156
newly_seen_unique = set()
1157
for searcher in unique_searchers:
1158
newly_seen_unique.update(searcher.step())
1159
new_common_unique = set()
1160
for revision in newly_seen_unique:
1161
for searcher in unique_searchers:
1162
if revision not in searcher.seen:
1165
# This is a border because it is a first common that we see
1166
# after walking for a while.
1167
new_common_unique.add(revision)
1168
if newly_seen_common:
1169
# These are nodes descended from one of the 'common' searchers.
1170
# Make sure all searchers are on the same page
1171
for searcher in common_searchers:
1172
newly_seen_common.update(
1173
searcher.find_seen_ancestors(newly_seen_common))
1174
# We start searching the whole ancestry. It is a bit wasteful,
1175
# though. We really just want to mark all of these nodes as
1176
# 'seen' and then start just the tips. However, it requires a
1177
# get_parent_map() call to figure out the tips anyway, and all
1178
# redundant requests should be fairly fast.
1179
for searcher in common_searchers:
1180
searcher.start_searching(newly_seen_common)
1182
# If a 'common' node is an ancestor of all unique searchers, we
1183
# can stop searching it.
1184
stop_searching_common = ancestor_all_unique.intersection(
1186
if stop_searching_common:
1187
for searcher in common_searchers:
1188
searcher.stop_searching_any(stop_searching_common)
1189
if new_common_unique:
1190
# We found some ancestors that are common
1191
for searcher in unique_searchers:
1192
new_common_unique.update(
1193
searcher.find_seen_ancestors(new_common_unique))
1194
# Since these are common, we can grab another set of ancestors
1196
for searcher in common_searchers:
1197
new_common_unique.update(
1198
searcher.find_seen_ancestors(new_common_unique))
1200
# We can tell all of the unique searchers to start at these
1201
# nodes, and tell all of the common searchers to *stop*
1202
# searching these nodes
1203
for searcher in unique_searchers:
1204
searcher.start_searching(new_common_unique)
1205
for searcher in common_searchers:
1206
searcher.stop_searching_any(new_common_unique)
1207
ancestor_all_unique.update(new_common_unique)
1209
# Filter out searchers that don't actually search different
1210
# nodes. We already have the ancestry intersection for them
1211
next_unique_searchers = []
1212
unique_search_sets = set()
1213
for searcher in unique_searchers:
1214
will_search_set = frozenset(searcher._next_query)
1215
if will_search_set not in unique_search_sets:
1216
# This searcher is searching a unique set of nodes, let it
1217
unique_search_sets.add(will_search_set)
1218
next_unique_searchers.append(searcher)
1219
unique_searchers = next_unique_searchers
1220
for searcher in common_searchers:
1221
if searcher._next_query:
1224
# All common searcher have stopped searching
1227
def _remove_simple_descendants(self, revisions, parent_map):
1228
"""remove revisions which are children of other ones in the set
1230
This doesn't do any graph searching, it just checks the immediate
1231
parent_map to find if there are any children which can be removed.
1233
:param revisions: A set of revision_ids
1234
:return: A set of revision_ids with the children removed
1236
simple_ancestors = revisions.copy()
1237
# TODO: jam 20071214 we *could* restrict it to searching only the
1238
# parent_map of revisions already present in 'revisions', but
1239
# considering the general use case, I think this is actually
1242
# This is the same as the following loop. I don't know that it is any
1244
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1245
## if p_ids is not None and revisions.intersection(p_ids))
1246
## return simple_ancestors
1248
# Yet Another Way, invert the parent map (which can be cached)
1250
## for revision_id, parent_ids in parent_map.iteritems():
1251
## for p_id in parent_ids:
1252
## descendants.setdefault(p_id, []).append(revision_id)
1253
## for revision in revisions.intersection(descendants):
1254
## simple_ancestors.difference_update(descendants[revision])
1255
## return simple_ancestors
1256
for revision, parent_ids in viewitems(parent_map):
1257
if parent_ids is None:
1259
for parent_id in parent_ids:
1260
if parent_id in revisions:
1261
# This node has a parent present in the set, so we can
1263
simple_ancestors.discard(revision)
1265
return simple_ancestors
1268
class HeadsCache(object):
1269
"""A cache of results for graph heads calls."""
1271
def __init__(self, graph):
1275
def heads(self, keys):
1276
"""Return the heads of keys.
1278
This matches the API of Graph.heads(), specifically the return value is
1279
a set which can be mutated, and ordering of the input is not preserved
1282
:see also: Graph.heads.
1283
:param keys: The keys to calculate heads for.
1284
:return: A set containing the heads, which may be mutated without
1285
affecting future lookups.
1287
keys = frozenset(keys)
1289
return set(self._heads[keys])
1291
heads = self.graph.heads(keys)
1292
self._heads[keys] = heads
1296
class FrozenHeadsCache(object):
1297
"""Cache heads() calls, assuming the caller won't modify them."""
1299
def __init__(self, graph):
1303
def heads(self, keys):
1304
"""Return the heads of keys.
1306
Similar to Graph.heads(). The main difference is that the return value
1307
is a frozen set which cannot be mutated.
1309
:see also: Graph.heads.
1310
:param keys: The keys to calculate heads for.
1311
:return: A frozenset containing the heads.
1313
keys = frozenset(keys)
1315
return self._heads[keys]
1317
heads = frozenset(self.graph.heads(keys))
1318
self._heads[keys] = heads
1321
def cache(self, keys, heads):
1322
"""Store a known value."""
1323
self._heads[frozenset(keys)] = frozenset(heads)
1326
class _BreadthFirstSearcher(object):
1327
"""Parallel search breadth-first the ancestry of revisions.
1329
This class implements the iterator protocol, but additionally
1330
1. provides a set of seen ancestors, and
1331
2. allows some ancestries to be unsearched, via stop_searching_any
1334
def __init__(self, revisions, parents_provider):
1335
self._iterations = 0
1336
self._next_query = set(revisions)
1338
self._started_keys = set(self._next_query)
1339
self._stopped_keys = set()
1340
self._parents_provider = parents_provider
1341
self._returning = 'next_with_ghosts'
1342
self._current_present = set()
1343
self._current_ghosts = set()
1344
self._current_parents = {}
1347
if self._iterations:
1348
prefix = "searching"
1351
search = '%s=%r' % (prefix, list(self._next_query))
1352
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1353
' seen=%r)' % (self._iterations, search, list(self.seen)))
1355
def get_state(self):
1356
"""Get the current state of this searcher.
1358
:return: Tuple with started keys, excludes and included keys
1360
if self._returning == 'next':
1361
# We have to know the current nodes children to be able to list the
1362
# exclude keys for them. However, while we could have a second
1363
# look-ahead result buffer and shuffle things around, this method
1364
# is typically only called once per search - when memoising the
1365
# results of the search.
1366
found, ghosts, next, parents = self._do_query(self._next_query)
1367
# pretend we didn't query: perhaps we should tweak _do_query to be
1368
# entirely stateless?
1369
self.seen.difference_update(next)
1370
next_query = next.union(ghosts)
1372
next_query = self._next_query
1373
excludes = self._stopped_keys.union(next_query)
1374
included_keys = self.seen.difference(excludes)
1375
return self._started_keys, excludes, included_keys
1380
except StopIteration:
1384
"""Return the next ancestors of this revision.
1386
Ancestors are returned in the order they are seen in a breadth-first
1387
traversal. No ancestor will be returned more than once. Ancestors are
1388
returned before their parentage is queried, so ghosts and missing
1389
revisions (including the start revisions) are included in the result.
1390
This can save a round trip in LCA style calculation by allowing
1391
convergence to be detected without reading the data for the revision
1392
the convergence occurs on.
1394
:return: A set of revision_ids.
1396
if self._returning != 'next':
1397
# switch to returning the query, not the results.
1398
self._returning = 'next'
1399
self._iterations += 1
1402
if len(self._next_query) == 0:
1403
raise StopIteration()
1404
# We have seen what we're querying at this point as we are returning
1405
# the query, not the results.
1406
self.seen.update(self._next_query)
1407
return self._next_query
1411
def next_with_ghosts(self):
1412
"""Return the next found ancestors, with ghosts split out.
1414
Ancestors are returned in the order they are seen in a breadth-first
1415
traversal. No ancestor will be returned more than once. Ancestors are
1416
returned only after asking for their parents, which allows us to detect
1417
which revisions are ghosts and which are not.
1419
:return: A tuple with (present ancestors, ghost ancestors) sets.
1421
if self._returning != 'next_with_ghosts':
1422
# switch to returning the results, not the current query.
1423
self._returning = 'next_with_ghosts'
1425
if len(self._next_query) == 0:
1426
raise StopIteration()
1428
return self._current_present, self._current_ghosts
1431
"""Advance the search.
1433
Updates self.seen, self._next_query, self._current_present,
1434
self._current_ghosts, self._current_parents and self._iterations.
1436
self._iterations += 1
1437
found, ghosts, next, parents = self._do_query(self._next_query)
1438
self._current_present = found
1439
self._current_ghosts = ghosts
1440
self._next_query = next
1441
self._current_parents = parents
1442
# ghosts are implicit stop points, otherwise the search cannot be
1443
# repeated when ghosts are filled.
1444
self._stopped_keys.update(ghosts)
1446
def _do_query(self, revisions):
1447
"""Query for revisions.
1449
Adds revisions to the seen set.
1451
:param revisions: Revisions to query.
1452
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1453
set(parents_of_found_revisions), dict(found_revisions:parents)).
1455
found_revisions = set()
1456
parents_of_found = set()
1457
# revisions may contain nodes that point to other nodes in revisions:
1458
# we want to filter them out.
1460
seen.update(revisions)
1461
parent_map = self._parents_provider.get_parent_map(revisions)
1462
found_revisions.update(parent_map)
1463
for rev_id, parents in viewitems(parent_map):
1466
new_found_parents = [p for p in parents if p not in seen]
1467
if new_found_parents:
1468
# Calling set.update() with an empty generator is actually
1470
parents_of_found.update(new_found_parents)
1471
ghost_revisions = revisions - found_revisions
1472
return found_revisions, ghost_revisions, parents_of_found, parent_map
1477
def find_seen_ancestors(self, revisions):
1478
"""Find ancestors of these revisions that have already been seen.
1480
This function generally makes the assumption that querying for the
1481
parents of a node that has already been queried is reasonably cheap.
1482
(eg, not a round trip to a remote host).
1484
# TODO: Often we might ask one searcher for its seen ancestors, and
1485
# then ask another searcher the same question. This can result in
1486
# searching the same revisions repeatedly if the two searchers
1487
# have a lot of overlap.
1488
all_seen = self.seen
1489
pending = set(revisions).intersection(all_seen)
1490
seen_ancestors = set(pending)
1492
if self._returning == 'next':
1493
# self.seen contains what nodes have been returned, not what nodes
1494
# have been queried. We don't want to probe for nodes that haven't
1495
# been searched yet.
1496
not_searched_yet = self._next_query
1498
not_searched_yet = ()
1499
pending.difference_update(not_searched_yet)
1500
get_parent_map = self._parents_provider.get_parent_map
1502
parent_map = get_parent_map(pending)
1504
# We don't care if it is a ghost, since it can't be seen if it is
1506
for parent_ids in viewvalues(parent_map):
1507
all_parents.extend(parent_ids)
1508
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1509
seen_ancestors.update(next_pending)
1510
next_pending.difference_update(not_searched_yet)
1511
pending = next_pending
1513
return seen_ancestors
1515
def stop_searching_any(self, revisions):
1517
Remove any of the specified revisions from the search list.
1519
None of the specified revisions are required to be present in the
1522
It is okay to call stop_searching_any() for revisions which were seen
1523
in previous iterations. It is the callers responsibility to call
1524
find_seen_ancestors() to make sure that current search tips that are
1525
ancestors of those revisions are also stopped. All explicitly stopped
1526
revisions will be excluded from the search result's get_keys(), though.
1528
# TODO: does this help performance?
1531
revisions = frozenset(revisions)
1532
if self._returning == 'next':
1533
stopped = self._next_query.intersection(revisions)
1534
self._next_query = self._next_query.difference(revisions)
1536
stopped_present = self._current_present.intersection(revisions)
1537
stopped = stopped_present.union(
1538
self._current_ghosts.intersection(revisions))
1539
self._current_present.difference_update(stopped)
1540
self._current_ghosts.difference_update(stopped)
1541
# stopping 'x' should stop returning parents of 'x', but
1542
# not if 'y' always references those same parents
1543
stop_rev_references = {}
1544
for rev in stopped_present:
1545
for parent_id in self._current_parents[rev]:
1546
if parent_id not in stop_rev_references:
1547
stop_rev_references[parent_id] = 0
1548
stop_rev_references[parent_id] += 1
1549
# if only the stopped revisions reference it, the ref count will be
1551
for parents in viewvalues(self._current_parents):
1552
for parent_id in parents:
1554
stop_rev_references[parent_id] -= 1
1557
stop_parents = set()
1558
for rev_id, refs in viewitems(stop_rev_references):
1560
stop_parents.add(rev_id)
1561
self._next_query.difference_update(stop_parents)
1562
self._stopped_keys.update(stopped)
1563
self._stopped_keys.update(revisions)
1566
def start_searching(self, revisions):
1567
"""Add revisions to the search.
1569
The parents of revisions will be returned from the next call to next()
1570
or next_with_ghosts(). If next_with_ghosts was the most recently used
1571
next* call then the return value is the result of looking up the
1572
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1574
revisions = frozenset(revisions)
1575
self._started_keys.update(revisions)
1576
new_revisions = revisions.difference(self.seen)
1577
if self._returning == 'next':
1578
self._next_query.update(new_revisions)
1579
self.seen.update(new_revisions)
1581
# perform a query on revisions
1582
revs, ghosts, query, parents = self._do_query(revisions)
1583
self._stopped_keys.update(ghosts)
1584
self._current_present.update(revs)
1585
self._current_ghosts.update(ghosts)
1586
self._next_query.update(query)
1587
self._current_parents.update(parents)
1591
def invert_parent_map(parent_map):
1592
"""Given a map from child => parents, create a map of parent=>children"""
1594
for child, parents in viewitems(parent_map):
1596
# Any given parent is likely to have only a small handful
1597
# of children, many will have only one. So we avoid mem overhead of
1598
# a list, in exchange for extra copying of tuples
1599
if p not in child_map:
1600
child_map[p] = (child,)
1602
child_map[p] = child_map[p] + (child,)
1606
def collapse_linear_regions(parent_map):
1607
"""Collapse regions of the graph that are 'linear'.
1613
can be collapsed by removing B and getting::
1617
:param parent_map: A dictionary mapping children to their parents
1618
:return: Another dictionary with 'linear' chains collapsed
1620
# Note: this isn't a strictly minimal collapse. For example:
1628
# Will not have 'D' removed, even though 'E' could fit. Also:
1634
# A and C are both kept because they are edges of the graph. We *could* get
1635
# rid of A if we wanted.
1643
# Will not have any nodes removed, even though you do have an
1644
# 'uninteresting' linear D->B and E->C
1646
for child, parents in viewitems(parent_map):
1647
children.setdefault(child, [])
1649
children.setdefault(p, []).append(child)
1651
orig_children = dict(children)
1653
result = dict(parent_map)
1654
for node in parent_map:
1655
parents = result[node]
1656
if len(parents) == 1:
1657
parent_children = children[parents[0]]
1658
if len(parent_children) != 1:
1659
# This is not the only child
1661
node_children = children[node]
1662
if len(node_children) != 1:
1664
child_parents = result.get(node_children[0], None)
1665
if len(child_parents) != 1:
1666
# This is not its only parent
1668
# The child of this node only points at it, and the parent only has
1669
# this as a child. remove this node, and join the others together
1670
result[node_children[0]] = parents
1671
children[parents[0]] = node_children
1679
class GraphThunkIdsToKeys(object):
1680
"""Forwards calls about 'ids' to be about keys internally."""
1682
def __init__(self, graph):
1685
def topo_sort(self):
1686
return [r for (r,) in self._graph.topo_sort()]
1688
def heads(self, ids):
1689
"""See Graph.heads()"""
1690
as_keys = [(i,) for i in ids]
1691
head_keys = self._graph.heads(as_keys)
1692
return {h[0] for h in head_keys}
1694
def merge_sort(self, tip_revision):
1695
nodes = self._graph.merge_sort((tip_revision,))
1697
node.key = node.key[0]
1700
def add_node(self, revision, parents):
1701
self._graph.add_node((revision,), [(p,) for p in parents])
1704
_counters = [0, 0, 0, 0, 0, 0, 0]
1706
from ._known_graph_pyx import KnownGraph
1707
except ImportError as e:
1708
osutils.failed_to_load_extension(e)
1709
from ._known_graph_py import KnownGraph
added
removed
breezy/graph.py
