44
49
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
48
class _StackedParentsProvider(object):
52
class DictParentsProvider(object):
53
"""A parents provider for Graph objects."""
55
def __init__(self, ancestry):
56
self.ancestry = ancestry
59
return 'DictParentsProvider(%r)' % self.ancestry
61
# Note: DictParentsProvider does not implement get_cached_parent_map
62
# Arguably, the data is clearly cached in memory. However, this class
63
# is mostly used for testing, and it keeps the tests clean to not
66
def get_parent_map(self, keys):
67
"""See StackedParentsProvider.get_parent_map"""
68
ancestry = self.ancestry
69
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
72
class StackedParentsProvider(object):
73
"""A parents provider which stacks (or unions) multiple providers.
75
The providers are queries in the order of the provided parent_providers.
50
78
def __init__(self, parent_providers):
51
79
self._parent_providers = parent_providers
53
81
def __repr__(self):
54
return "_StackedParentsProvider(%r)" % self._parent_providers
56
def get_parents(self, revision_ids):
57
"""Find revision ids of the parents of a list of revisions
59
A list is returned of the same length as the input. Each entry
60
is a list of parent ids for the corresponding input revision.
82
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
84
def get_parent_map(self, keys):
85
"""Get a mapping of keys => parents
87
A dictionary is returned with an entry for each key present in this
88
source. If this source doesn't have information about a key, it should
62
91
[NULL_REVISION] is used as the parent of the first user-committed
63
92
revision. Its parent list is empty.
65
If the revision is not present (i.e. a ghost), None is used in place
66
of the list of parents.
94
:param keys: An iterable returning keys to check (eg revision_ids)
95
:return: A dictionary mapping each key to its parents
69
for parents_provider in self._parent_providers:
70
pending_revisions = [r for r in revision_ids if r not in found]
71
parent_list = parents_provider.get_parents(pending_revisions)
72
new_found = dict((k, v) for k, v in zip(pending_revisions,
73
parent_list) if v is not None)
74
found.update(new_found)
75
if len(found) == len(revision_ids):
77
return [found.get(r, None) for r in revision_ids]
99
# This adds getattr() overhead to each get_parent_map call. However,
100
# this is StackedParentsProvider, which means we're dealing with I/O
101
# (either local indexes, or remote RPCs), so CPU overhead should be
103
for parents_provider in self._parent_providers:
104
get_cached = getattr(parents_provider, 'get_cached_parent_map',
106
if get_cached is None:
108
new_found = get_cached(remaining)
109
found.update(new_found)
110
remaining.difference_update(new_found)
115
for parents_provider in self._parent_providers:
116
new_found = parents_provider.get_parent_map(remaining)
117
found.update(new_found)
118
remaining.difference_update(new_found)
124
class CachingParentsProvider(object):
125
"""A parents provider which will cache the revision => parents as a dict.
127
This is useful for providers which have an expensive look up.
129
Either a ParentsProvider or a get_parent_map-like callback may be
130
supplied. If it provides extra un-asked-for parents, they will be cached,
131
but filtered out of get_parent_map.
133
The cache is enabled by default, but may be disabled and re-enabled.
135
def __init__(self, parent_provider=None, get_parent_map=None):
138
:param parent_provider: The ParentProvider to use. It or
139
get_parent_map must be supplied.
140
:param get_parent_map: The get_parent_map callback to use. It or
141
parent_provider must be supplied.
143
self._real_provider = parent_provider
144
if get_parent_map is None:
145
self._get_parent_map = self._real_provider.get_parent_map
147
self._get_parent_map = get_parent_map
149
self.enable_cache(True)
152
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
154
def enable_cache(self, cache_misses=True):
156
if self._cache is not None:
157
raise AssertionError('Cache enabled when already enabled.')
159
self._cache_misses = cache_misses
160
self.missing_keys = set()
162
def disable_cache(self):
163
"""Disable and clear the cache."""
165
self._cache_misses = None
166
self.missing_keys = set()
168
def get_cached_map(self):
169
"""Return any cached get_parent_map values."""
170
if self._cache is None:
172
return dict(self._cache)
174
def get_cached_parent_map(self, keys):
175
"""Return items from the cache.
177
This returns the same info as get_parent_map, but explicitly does not
178
invoke the supplied ParentsProvider to search for uncached values.
183
return dict([(key, cache[key]) for key in keys if key in cache])
185
def get_parent_map(self, keys):
186
"""See StackedParentsProvider.get_parent_map."""
189
cache = self._get_parent_map(keys)
191
needed_revisions = set(key for key in keys if key not in cache)
192
# Do not ask for negatively cached keys
193
needed_revisions.difference_update(self.missing_keys)
195
parent_map = self._get_parent_map(needed_revisions)
196
cache.update(parent_map)
197
if self._cache_misses:
198
for key in needed_revisions:
199
if key not in parent_map:
200
self.note_missing_key(key)
203
value = cache.get(key)
204
if value is not None:
208
def note_missing_key(self, key):
209
"""Note that key is a missing key."""
210
if self._cache_misses:
211
self.missing_keys.add(key)
214
class CallableToParentsProviderAdapter(object):
215
"""A parents provider that adapts any callable to the parents provider API.
217
i.e. it accepts calls to self.get_parent_map and relays them to the
218
callable it was constructed with.
221
def __init__(self, a_callable):
222
self.callable = a_callable
225
return "%s(%r)" % (self.__class__.__name__, self.callable)
227
def get_parent_map(self, keys):
228
return self.callable(keys)
80
231
class Graph(object):
127
282
common ancestor of all border ancestors, because this shows that it
128
283
cannot be a descendant of any border ancestor.
130
The scaling of this operation should be proportional to
285
The scaling of this operation should be proportional to:
131
287
1. The number of uncommon ancestors
132
288
2. The number of border ancestors
133
289
3. The length of the shortest path between a border ancestor and an
134
290
ancestor of all border ancestors.
136
292
border_common, common, sides = self._find_border_ancestors(revisions)
137
return self._filter_candidate_lca(border_common)
293
# We may have common ancestors that can be reached from each other.
294
# - ask for the heads of them to filter it down to only ones that
295
# cannot be reached from each other - phase 2.
296
return self.heads(border_common)
139
298
def find_difference(self, left_revision, right_revision):
140
299
"""Determine the graph difference between two revisions"""
141
border, common, (left, right) = self._find_border_ancestors(
300
border, common, searchers = self._find_border_ancestors(
142
301
[left_revision, right_revision])
143
return (left.difference(right).difference(common),
144
right.difference(left).difference(common))
302
self._search_for_extra_common(common, searchers)
303
left = searchers[0].seen
304
right = searchers[1].seen
305
return (left.difference(right), right.difference(left))
307
def find_descendants(self, old_key, new_key):
308
"""Find descendants of old_key that are ancestors of new_key."""
309
child_map = self.get_child_map(self._find_descendant_ancestors(
311
graph = Graph(DictParentsProvider(child_map))
312
searcher = graph._make_breadth_first_searcher([old_key])
316
def _find_descendant_ancestors(self, old_key, new_key):
317
"""Find ancestors of new_key that may be descendants of old_key."""
318
stop = self._make_breadth_first_searcher([old_key])
319
descendants = self._make_breadth_first_searcher([new_key])
320
for revisions in descendants:
321
old_stop = stop.seen.intersection(revisions)
322
descendants.stop_searching_any(old_stop)
323
seen_stop = descendants.find_seen_ancestors(stop.step())
324
descendants.stop_searching_any(seen_stop)
325
return descendants.seen.difference(stop.seen)
327
def get_child_map(self, keys):
328
"""Get a mapping from parents to children of the specified keys.
330
This is simply the inversion of get_parent_map. Only supplied keys
331
will be discovered as children.
332
:return: a dict of key:child_list for keys.
334
parent_map = self._parents_provider.get_parent_map(keys)
336
for child, parents in sorted(parent_map.items()):
337
for parent in parents:
338
parent_child.setdefault(parent, []).append(child)
341
def find_distance_to_null(self, target_revision_id, known_revision_ids):
342
"""Find the left-hand distance to the NULL_REVISION.
344
(This can also be considered the revno of a branch at
347
:param target_revision_id: A revision_id which we would like to know
349
:param known_revision_ids: [(revision_id, revno)] A list of known
350
revno, revision_id tuples. We'll use this to seed the search.
352
# Map from revision_ids to a known value for their revno
353
known_revnos = dict(known_revision_ids)
354
cur_tip = target_revision_id
356
NULL_REVISION = revision.NULL_REVISION
357
known_revnos[NULL_REVISION] = 0
359
searching_known_tips = list(known_revnos.keys())
361
unknown_searched = {}
363
while cur_tip not in known_revnos:
364
unknown_searched[cur_tip] = num_steps
366
to_search = set([cur_tip])
367
to_search.update(searching_known_tips)
368
parent_map = self.get_parent_map(to_search)
369
parents = parent_map.get(cur_tip, None)
370
if not parents: # An empty list or None is a ghost
371
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
375
for revision_id in searching_known_tips:
376
parents = parent_map.get(revision_id, None)
380
next_revno = known_revnos[revision_id] - 1
381
if next in unknown_searched:
382
# We have enough information to return a value right now
383
return next_revno + unknown_searched[next]
384
if next in known_revnos:
386
known_revnos[next] = next_revno
387
next_known_tips.append(next)
388
searching_known_tips = next_known_tips
390
# We reached a known revision, so just add in how many steps it took to
392
return known_revnos[cur_tip] + num_steps
394
def find_lefthand_distances(self, keys):
395
"""Find the distance to null for all the keys in keys.
397
:param keys: keys to lookup.
398
:return: A dict key->distance for all of keys.
400
# Optimisable by concurrent searching, but a random spread should get
401
# some sort of hit rate.
408
(key, self.find_distance_to_null(key, known_revnos)))
409
except errors.GhostRevisionsHaveNoRevno:
412
known_revnos.append((key, -1))
413
return dict(known_revnos)
415
def find_unique_ancestors(self, unique_revision, common_revisions):
416
"""Find the unique ancestors for a revision versus others.
418
This returns the ancestry of unique_revision, excluding all revisions
419
in the ancestry of common_revisions. If unique_revision is in the
420
ancestry, then the empty set will be returned.
422
:param unique_revision: The revision_id whose ancestry we are
424
(XXX: Would this API be better if we allowed multiple revisions on
425
to be searched here?)
426
:param common_revisions: Revision_ids of ancestries to exclude.
427
:return: A set of revisions in the ancestry of unique_revision
429
if unique_revision in common_revisions:
432
# Algorithm description
433
# 1) Walk backwards from the unique node and all common nodes.
434
# 2) When a node is seen by both sides, stop searching it in the unique
435
# walker, include it in the common walker.
436
# 3) Stop searching when there are no nodes left for the unique walker.
437
# At this point, you have a maximal set of unique nodes. Some of
438
# them may actually be common, and you haven't reached them yet.
439
# 4) Start new searchers for the unique nodes, seeded with the
440
# information you have so far.
441
# 5) Continue searching, stopping the common searches when the search
442
# tip is an ancestor of all unique nodes.
443
# 6) Aggregate together unique searchers when they are searching the
444
# same tips. When all unique searchers are searching the same node,
445
# stop move it to a single 'all_unique_searcher'.
446
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
447
# Most of the time this produces very little important information.
448
# So don't step it as quickly as the other searchers.
449
# 8) Search is done when all common searchers have completed.
451
unique_searcher, common_searcher = self._find_initial_unique_nodes(
452
[unique_revision], common_revisions)
454
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
458
(all_unique_searcher,
459
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
460
unique_searcher, common_searcher)
462
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
463
unique_tip_searchers, common_searcher)
464
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
465
if 'graph' in debug.debug_flags:
466
trace.mutter('Found %d truly unique nodes out of %d',
467
len(true_unique_nodes), len(unique_nodes))
468
return true_unique_nodes
470
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
471
"""Steps 1-3 of find_unique_ancestors.
473
Find the maximal set of unique nodes. Some of these might actually
474
still be common, but we are sure that there are no other unique nodes.
476
:return: (unique_searcher, common_searcher)
479
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
480
# we know that unique_revisions aren't in common_revisions, so skip
482
unique_searcher.next()
483
common_searcher = self._make_breadth_first_searcher(common_revisions)
485
# As long as we are still finding unique nodes, keep searching
486
while unique_searcher._next_query:
487
next_unique_nodes = set(unique_searcher.step())
488
next_common_nodes = set(common_searcher.step())
490
# Check if either searcher encounters new nodes seen by the other
492
unique_are_common_nodes = next_unique_nodes.intersection(
493
common_searcher.seen)
494
unique_are_common_nodes.update(
495
next_common_nodes.intersection(unique_searcher.seen))
496
if unique_are_common_nodes:
497
ancestors = unique_searcher.find_seen_ancestors(
498
unique_are_common_nodes)
499
# TODO: This is a bit overboard, we only really care about
500
# the ancestors of the tips because the rest we
501
# already know. This is *correct* but causes us to
502
# search too much ancestry.
503
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
504
unique_searcher.stop_searching_any(ancestors)
505
common_searcher.start_searching(ancestors)
507
return unique_searcher, common_searcher
509
def _make_unique_searchers(self, unique_nodes, unique_searcher,
511
"""Create a searcher for all the unique search tips (step 4).
513
As a side effect, the common_searcher will stop searching any nodes
514
that are ancestors of the unique searcher tips.
516
:return: (all_unique_searcher, unique_tip_searchers)
518
unique_tips = self._remove_simple_descendants(unique_nodes,
519
self.get_parent_map(unique_nodes))
521
if len(unique_tips) == 1:
522
unique_tip_searchers = []
523
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
525
unique_tip_searchers = []
526
for tip in unique_tips:
527
revs_to_search = unique_searcher.find_seen_ancestors([tip])
528
revs_to_search.update(
529
common_searcher.find_seen_ancestors(revs_to_search))
530
searcher = self._make_breadth_first_searcher(revs_to_search)
531
# We don't care about the starting nodes.
532
searcher._label = tip
534
unique_tip_searchers.append(searcher)
536
ancestor_all_unique = None
537
for searcher in unique_tip_searchers:
538
if ancestor_all_unique is None:
539
ancestor_all_unique = set(searcher.seen)
541
ancestor_all_unique = ancestor_all_unique.intersection(
543
# Collapse all the common nodes into a single searcher
544
all_unique_searcher = self._make_breadth_first_searcher(
546
if ancestor_all_unique:
547
# We've seen these nodes in all the searchers, so we'll just go to
549
all_unique_searcher.step()
551
# Stop any search tips that are already known as ancestors of the
553
stopped_common = common_searcher.stop_searching_any(
554
common_searcher.find_seen_ancestors(ancestor_all_unique))
557
for searcher in unique_tip_searchers:
558
total_stopped += len(searcher.stop_searching_any(
559
searcher.find_seen_ancestors(ancestor_all_unique)))
560
if 'graph' in debug.debug_flags:
561
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
562
' (%d stopped search tips, %d common ancestors'
563
' (%d stopped common)',
564
len(unique_nodes), len(unique_tip_searchers),
565
total_stopped, len(ancestor_all_unique),
567
return all_unique_searcher, unique_tip_searchers
569
def _step_unique_and_common_searchers(self, common_searcher,
570
unique_tip_searchers,
572
"""Step all the searchers"""
573
newly_seen_common = set(common_searcher.step())
574
newly_seen_unique = set()
575
for searcher in unique_tip_searchers:
576
next = set(searcher.step())
577
next.update(unique_searcher.find_seen_ancestors(next))
578
next.update(common_searcher.find_seen_ancestors(next))
579
for alt_searcher in unique_tip_searchers:
580
if alt_searcher is searcher:
582
next.update(alt_searcher.find_seen_ancestors(next))
583
searcher.start_searching(next)
584
newly_seen_unique.update(next)
585
return newly_seen_common, newly_seen_unique
587
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
589
newly_seen_unique, step_all_unique):
590
"""Find nodes that are common to all unique_tip_searchers.
592
If it is time, step the all_unique_searcher, and add its nodes to the
595
common_to_all_unique_nodes = newly_seen_unique.copy()
596
for searcher in unique_tip_searchers:
597
common_to_all_unique_nodes.intersection_update(searcher.seen)
598
common_to_all_unique_nodes.intersection_update(
599
all_unique_searcher.seen)
600
# Step all-unique less frequently than the other searchers.
601
# In the common case, we don't need to spider out far here, so
602
# avoid doing extra work.
604
tstart = time.clock()
605
nodes = all_unique_searcher.step()
606
common_to_all_unique_nodes.update(nodes)
607
if 'graph' in debug.debug_flags:
608
tdelta = time.clock() - tstart
609
trace.mutter('all_unique_searcher step() took %.3fs'
610
'for %d nodes (%d total), iteration: %s',
611
tdelta, len(nodes), len(all_unique_searcher.seen),
612
all_unique_searcher._iterations)
613
return common_to_all_unique_nodes
615
def _collapse_unique_searchers(self, unique_tip_searchers,
616
common_to_all_unique_nodes):
617
"""Combine searchers that are searching the same tips.
619
When two searchers are searching the same tips, we can stop one of the
620
searchers. We also know that the maximal set of common ancestors is the
621
intersection of the two original searchers.
623
:return: A list of searchers that are searching unique nodes.
625
# Filter out searchers that don't actually search different
626
# nodes. We already have the ancestry intersection for them
627
unique_search_tips = {}
628
for searcher in unique_tip_searchers:
629
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
630
will_search_set = frozenset(searcher._next_query)
631
if not will_search_set:
632
if 'graph' in debug.debug_flags:
633
trace.mutter('Unique searcher %s was stopped.'
634
' (%s iterations) %d nodes stopped',
636
searcher._iterations,
638
elif will_search_set not in unique_search_tips:
639
# This searcher is searching a unique set of nodes, let it
640
unique_search_tips[will_search_set] = [searcher]
642
unique_search_tips[will_search_set].append(searcher)
643
# TODO: it might be possible to collapse searchers faster when they
644
# only have *some* search tips in common.
645
next_unique_searchers = []
646
for searchers in unique_search_tips.itervalues():
647
if len(searchers) == 1:
648
# Searching unique tips, go for it
649
next_unique_searchers.append(searchers[0])
651
# These searchers have started searching the same tips, we
652
# don't need them to cover the same ground. The
653
# intersection of their ancestry won't change, so create a
654
# new searcher, combining their histories.
655
next_searcher = searchers[0]
656
for searcher in searchers[1:]:
657
next_searcher.seen.intersection_update(searcher.seen)
658
if 'graph' in debug.debug_flags:
659
trace.mutter('Combining %d searchers into a single'
660
' searcher searching %d nodes with'
663
len(next_searcher._next_query),
664
len(next_searcher.seen))
665
next_unique_searchers.append(next_searcher)
666
return next_unique_searchers
668
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
669
unique_tip_searchers, common_searcher):
670
"""Steps 5-8 of find_unique_ancestors.
672
This function returns when common_searcher has stopped searching for
675
# We step the ancestor_all_unique searcher only every
676
# STEP_UNIQUE_SEARCHER_EVERY steps.
677
step_all_unique_counter = 0
678
# While we still have common nodes to search
679
while common_searcher._next_query:
681
newly_seen_unique) = self._step_unique_and_common_searchers(
682
common_searcher, unique_tip_searchers, unique_searcher)
683
# These nodes are common ancestors of all unique nodes
684
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
685
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
686
step_all_unique_counter==0)
687
step_all_unique_counter = ((step_all_unique_counter + 1)
688
% STEP_UNIQUE_SEARCHER_EVERY)
690
if newly_seen_common:
691
# If a 'common' node is an ancestor of all unique searchers, we
692
# can stop searching it.
693
common_searcher.stop_searching_any(
694
all_unique_searcher.seen.intersection(newly_seen_common))
695
if common_to_all_unique_nodes:
696
common_to_all_unique_nodes.update(
697
common_searcher.find_seen_ancestors(
698
common_to_all_unique_nodes))
699
# The all_unique searcher can start searching the common nodes
700
# but everyone else can stop.
701
# This is the sort of thing where we would like to not have it
702
# start_searching all of the nodes, but only mark all of them
703
# as seen, and have it search only the actual tips. Otherwise
704
# it is another get_parent_map() traversal for it to figure out
705
# what we already should know.
706
all_unique_searcher.start_searching(common_to_all_unique_nodes)
707
common_searcher.stop_searching_any(common_to_all_unique_nodes)
709
next_unique_searchers = self._collapse_unique_searchers(
710
unique_tip_searchers, common_to_all_unique_nodes)
711
if len(unique_tip_searchers) != len(next_unique_searchers):
712
if 'graph' in debug.debug_flags:
713
trace.mutter('Collapsed %d unique searchers => %d'
715
len(unique_tip_searchers),
716
len(next_unique_searchers),
717
all_unique_searcher._iterations)
718
unique_tip_searchers = next_unique_searchers
720
def get_parent_map(self, revisions):
721
"""Get a map of key:parent_list for revisions.
723
This implementation delegates to get_parents, for old parent_providers
724
that do not supply get_parent_map.
727
for rev, parents in self.get_parents(revisions):
728
if parents is not None:
729
result[rev] = parents
146
732
def _make_breadth_first_searcher(self, revisions):
147
733
return _BreadthFirstSearcher(revisions, self)
163
749
if None in revisions:
164
750
raise errors.InvalidRevisionId(None, self)
165
common_searcher = self._make_breadth_first_searcher([])
166
751
common_ancestors = set()
167
752
searchers = [self._make_breadth_first_searcher([r])
168
753
for r in revisions]
169
754
active_searchers = searchers[:]
170
755
border_ancestors = set()
171
def update_common(searcher, revisions):
172
w_seen_ancestors = searcher.find_seen_ancestors(
174
stopped = searcher.stop_searching_any(w_seen_ancestors)
175
common_ancestors.update(w_seen_ancestors)
176
common_searcher.start_searching(stopped)
179
if len(active_searchers) == 0:
180
return border_ancestors, common_ancestors, [s.seen for s in
183
new_common = common_searcher.next()
184
common_ancestors.update(new_common)
185
except StopIteration:
188
for searcher in active_searchers:
189
for revision in new_common.intersection(searcher.seen):
190
update_common(searcher, revision)
192
758
newly_seen = set()
193
new_active_searchers = []
194
for searcher in active_searchers:
196
newly_seen.update(searcher.next())
197
except StopIteration:
200
new_active_searchers.append(searcher)
201
active_searchers = new_active_searchers
759
for searcher in searchers:
760
new_ancestors = searcher.step()
762
newly_seen.update(new_ancestors)
202
764
for revision in newly_seen:
203
765
if revision in common_ancestors:
204
for searcher in searchers:
205
update_common(searcher, revision)
766
# Not a border ancestor because it was seen as common
768
new_common.add(revision)
207
770
for searcher in searchers:
208
771
if revision not in searcher.seen:
774
# This is a border because it is a first common that we see
775
# after walking for a while.
211
776
border_ancestors.add(revision)
212
for searcher in searchers:
213
update_common(searcher, revision)
215
def _filter_candidate_lca(self, candidate_lca):
216
"""Remove candidates which are ancestors of other candidates.
218
This is done by searching the ancestries of each border ancestor. It
219
is perfomed on the principle that a border ancestor that is not an
220
ancestor of any other border ancestor is a lowest common ancestor.
222
Searches are stopped when they find a node that is determined to be a
223
common ancestor of all border ancestors, because this shows that it
224
cannot be a descendant of any border ancestor.
226
This will scale with the number of candidate ancestors and the length
227
of the shortest path from a candidate to an ancestor common to all
777
new_common.add(revision)
779
for searcher in searchers:
780
new_common.update(searcher.find_seen_ancestors(new_common))
781
for searcher in searchers:
782
searcher.start_searching(new_common)
783
common_ancestors.update(new_common)
785
# Figure out what the searchers will be searching next, and if
786
# there is only 1 set being searched, then we are done searching,
787
# since all searchers would have to be searching the same data,
788
# thus it *must* be in common.
789
unique_search_sets = set()
790
for searcher in searchers:
791
will_search_set = frozenset(searcher._next_query)
792
if will_search_set not in unique_search_sets:
793
# This searcher is searching a unique set of nodes, let it
794
unique_search_sets.add(will_search_set)
796
if len(unique_search_sets) == 1:
797
nodes = unique_search_sets.pop()
798
uncommon_nodes = nodes.difference(common_ancestors)
800
raise AssertionError("Somehow we ended up converging"
801
" without actually marking them as"
804
"\nuncommon_nodes: %s"
805
% (revisions, uncommon_nodes))
807
return border_ancestors, common_ancestors, searchers
809
def heads(self, keys):
810
"""Return the heads from amongst keys.
812
This is done by searching the ancestries of each key. Any key that is
813
reachable from another key is not returned; all the others are.
815
This operation scales with the relative depth between any two keys. If
816
any two keys are completely disconnected all ancestry of both sides
819
:param keys: An iterable of keys.
820
:return: A set of the heads. Note that as a set there is no ordering
821
information. Callers will need to filter their input to create
822
order if they need it.
824
candidate_heads = set(keys)
825
if revision.NULL_REVISION in candidate_heads:
826
# NULL_REVISION is only a head if it is the only entry
827
candidate_heads.remove(revision.NULL_REVISION)
828
if not candidate_heads:
829
return set([revision.NULL_REVISION])
830
if len(candidate_heads) < 2:
831
return candidate_heads
230
832
searchers = dict((c, self._make_breadth_first_searcher([c]))
231
for c in candidate_lca)
833
for c in candidate_heads)
232
834
active_searchers = dict(searchers)
233
835
# skip over the actual candidate for each searcher
234
836
for searcher in active_searchers.itervalues():
838
# The common walker finds nodes that are common to two or more of the
839
# input keys, so that we don't access all history when a currently
840
# uncommon search point actually meets up with something behind a
841
# common search point. Common search points do not keep searches
842
# active; they just allow us to make searches inactive without
843
# accessing all history.
844
common_walker = self._make_breadth_first_searcher([])
236
845
while len(active_searchers) > 0:
237
for candidate, searcher in list(active_searchers.iteritems()):
239
ancestors = searcher.next()
850
except StopIteration:
851
# No common points being searched at this time.
853
for candidate in active_searchers.keys():
855
searcher = active_searchers[candidate]
857
# rare case: we deleted candidate in a previous iteration
858
# through this for loop, because it was determined to be
859
# a descendant of another candidate.
862
ancestors.update(searcher.next())
240
863
except StopIteration:
241
864
del active_searchers[candidate]
243
for ancestor in ancestors:
244
if ancestor in candidate_lca:
245
candidate_lca.remove(ancestor)
246
del searchers[ancestor]
247
if ancestor in active_searchers:
248
del active_searchers[ancestor]
866
# process found nodes
868
for ancestor in ancestors:
869
if ancestor in candidate_heads:
870
candidate_heads.remove(ancestor)
871
del searchers[ancestor]
872
if ancestor in active_searchers:
873
del active_searchers[ancestor]
874
# it may meet up with a known common node
875
if ancestor in common_walker.seen:
876
# some searcher has encountered our known common nodes:
878
ancestor_set = set([ancestor])
879
for searcher in searchers.itervalues():
880
searcher.stop_searching_any(ancestor_set)
882
# or it may have been just reached by all the searchers:
249
883
for searcher in searchers.itervalues():
250
884
if ancestor not in searcher.seen:
253
# if this revision was seen by all searchers, then it
254
# is a descendant of all candidates, so we can stop
255
# searching it, and any seen ancestors
887
# The final active searcher has just reached this node,
888
# making it be known as a descendant of all candidates,
889
# so we can stop searching it, and any seen ancestors
890
new_common.add(ancestor)
256
891
for searcher in searchers.itervalues():
257
892
seen_ancestors =\
258
searcher.find_seen_ancestors(ancestor)
893
searcher.find_seen_ancestors([ancestor])
259
894
searcher.stop_searching_any(seen_ancestors)
262
def find_unique_lca(self, left_revision, right_revision):
895
common_walker.start_searching(new_common)
896
return candidate_heads
898
def find_merge_order(self, tip_revision_id, lca_revision_ids):
899
"""Find the order that each revision was merged into tip.
901
This basically just walks backwards with a stack, and walks left-first
902
until it finds a node to stop.
904
if len(lca_revision_ids) == 1:
905
return list(lca_revision_ids)
906
looking_for = set(lca_revision_ids)
907
# TODO: Is there a way we could do this "faster" by batching up the
908
# get_parent_map requests?
909
# TODO: Should we also be culling the ancestry search right away? We
910
# could add looking_for to the "stop" list, and walk their
911
# ancestry in batched mode. The flip side is it might mean we walk a
912
# lot of "stop" nodes, rather than only the minimum.
913
# Then again, without it we may trace back into ancestry we could have
915
stack = [tip_revision_id]
918
while stack and looking_for:
921
if next in looking_for:
923
looking_for.remove(next)
924
if len(looking_for) == 1:
925
found.append(looking_for.pop())
928
parent_ids = self.get_parent_map([next]).get(next, None)
929
if not parent_ids: # Ghost, nothing to search here
931
for parent_id in reversed(parent_ids):
932
# TODO: (performance) We see the parent at this point, but we
933
# wait to mark it until later to make sure we get left
934
# parents before right parents. However, instead of
935
# waiting until we have traversed enough parents, we
936
# could instead note that we've found it, and once all
937
# parents are in the stack, just reverse iterate the
939
if parent_id not in stop:
940
# this will need to be searched
941
stack.append(parent_id)
945
def find_lefthand_merger(self, merged_key, tip_key):
946
"""Find the first lefthand ancestor of tip_key that merged merged_key.
948
We do this by first finding the descendants of merged_key, then
949
walking through the lefthand ancestry of tip_key until we find a key
950
that doesn't descend from merged_key. Its child is the key that
953
:return: The first lefthand ancestor of tip_key to merge merged_key.
954
merged_key if it is a lefthand ancestor of tip_key.
955
None if no ancestor of tip_key merged merged_key.
957
descendants = self.find_descendants(merged_key, tip_key)
958
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
959
last_candidate = None
960
for candidate in candidate_iterator:
961
if candidate not in descendants:
962
return last_candidate
963
last_candidate = candidate
965
def find_unique_lca(self, left_revision, right_revision,
263
967
"""Find a unique LCA.
265
969
Find lowest common ancestors. If there is no unique common
285
1045
An ancestor may sort after a descendant if the relationship is not
286
1046
visible in the supplied list of revisions.
288
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
1048
from bzrlib import tsort
1049
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
289
1050
return sorter.iter_topo_order()
1052
def is_ancestor(self, candidate_ancestor, candidate_descendant):
1053
"""Determine whether a revision is an ancestor of another.
1055
We answer this using heads() as heads() has the logic to perform the
1056
smallest number of parent lookups to determine the ancestral
1057
relationship between N revisions.
1059
return set([candidate_descendant]) == self.heads(
1060
[candidate_ancestor, candidate_descendant])
1062
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1063
"""Determine whether a revision is between two others.
1065
returns true if and only if:
1066
lower_bound_revid <= revid <= upper_bound_revid
1068
return ((upper_bound_revid is None or
1069
self.is_ancestor(revid, upper_bound_revid)) and
1070
(lower_bound_revid is None or
1071
self.is_ancestor(lower_bound_revid, revid)))
1073
def _search_for_extra_common(self, common, searchers):
1074
"""Make sure that unique nodes are genuinely unique.
1076
After _find_border_ancestors, all nodes marked "common" are indeed
1077
common. Some of the nodes considered unique are not, due to history
1078
shortcuts stopping the searches early.
1080
We know that we have searched enough when all common search tips are
1081
descended from all unique (uncommon) nodes because we know that a node
1082
cannot be an ancestor of its own ancestor.
1084
:param common: A set of common nodes
1085
:param searchers: The searchers returned from _find_border_ancestors
1088
# Basic algorithm...
1089
# A) The passed in searchers should all be on the same tips, thus
1090
# they should be considered the "common" searchers.
1091
# B) We find the difference between the searchers, these are the
1092
# "unique" nodes for each side.
1093
# C) We do a quick culling so that we only start searching from the
1094
# more interesting unique nodes. (A unique ancestor is more
1095
# interesting than any of its children.)
1096
# D) We start searching for ancestors common to all unique nodes.
1097
# E) We have the common searchers stop searching any ancestors of
1098
# nodes found by (D)
1099
# F) When there are no more common search tips, we stop
1101
# TODO: We need a way to remove unique_searchers when they overlap with
1102
# other unique searchers.
1103
if len(searchers) != 2:
1104
raise NotImplementedError(
1105
"Algorithm not yet implemented for > 2 searchers")
1106
common_searchers = searchers
1107
left_searcher = searchers[0]
1108
right_searcher = searchers[1]
1109
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1110
if not unique: # No unique nodes, nothing to do
1112
total_unique = len(unique)
1113
unique = self._remove_simple_descendants(unique,
1114
self.get_parent_map(unique))
1115
simple_unique = len(unique)
1117
unique_searchers = []
1118
for revision_id in unique:
1119
if revision_id in left_searcher.seen:
1120
parent_searcher = left_searcher
1122
parent_searcher = right_searcher
1123
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1124
if not revs_to_search: # XXX: This shouldn't be possible
1125
revs_to_search = [revision_id]
1126
searcher = self._make_breadth_first_searcher(revs_to_search)
1127
# We don't care about the starting nodes.
1129
unique_searchers.append(searcher)
1131
# possible todo: aggregate the common searchers into a single common
1132
# searcher, just make sure that we include the nodes into the .seen
1133
# properties of the original searchers
1135
ancestor_all_unique = None
1136
for searcher in unique_searchers:
1137
if ancestor_all_unique is None:
1138
ancestor_all_unique = set(searcher.seen)
1140
ancestor_all_unique = ancestor_all_unique.intersection(
1143
trace.mutter('Started %s unique searchers for %s unique revisions',
1144
simple_unique, total_unique)
1146
while True: # If we have no more nodes we have nothing to do
1147
newly_seen_common = set()
1148
for searcher in common_searchers:
1149
newly_seen_common.update(searcher.step())
1150
newly_seen_unique = set()
1151
for searcher in unique_searchers:
1152
newly_seen_unique.update(searcher.step())
1153
new_common_unique = set()
1154
for revision in newly_seen_unique:
1155
for searcher in unique_searchers:
1156
if revision not in searcher.seen:
1159
# This is a border because it is a first common that we see
1160
# after walking for a while.
1161
new_common_unique.add(revision)
1162
if newly_seen_common:
1163
# These are nodes descended from one of the 'common' searchers.
1164
# Make sure all searchers are on the same page
1165
for searcher in common_searchers:
1166
newly_seen_common.update(
1167
searcher.find_seen_ancestors(newly_seen_common))
1168
# We start searching the whole ancestry. It is a bit wasteful,
1169
# though. We really just want to mark all of these nodes as
1170
# 'seen' and then start just the tips. However, it requires a
1171
# get_parent_map() call to figure out the tips anyway, and all
1172
# redundant requests should be fairly fast.
1173
for searcher in common_searchers:
1174
searcher.start_searching(newly_seen_common)
1176
# If a 'common' node is an ancestor of all unique searchers, we
1177
# can stop searching it.
1178
stop_searching_common = ancestor_all_unique.intersection(
1180
if stop_searching_common:
1181
for searcher in common_searchers:
1182
searcher.stop_searching_any(stop_searching_common)
1183
if new_common_unique:
1184
# We found some ancestors that are common
1185
for searcher in unique_searchers:
1186
new_common_unique.update(
1187
searcher.find_seen_ancestors(new_common_unique))
1188
# Since these are common, we can grab another set of ancestors
1190
for searcher in common_searchers:
1191
new_common_unique.update(
1192
searcher.find_seen_ancestors(new_common_unique))
1194
# We can tell all of the unique searchers to start at these
1195
# nodes, and tell all of the common searchers to *stop*
1196
# searching these nodes
1197
for searcher in unique_searchers:
1198
searcher.start_searching(new_common_unique)
1199
for searcher in common_searchers:
1200
searcher.stop_searching_any(new_common_unique)
1201
ancestor_all_unique.update(new_common_unique)
1203
# Filter out searchers that don't actually search different
1204
# nodes. We already have the ancestry intersection for them
1205
next_unique_searchers = []
1206
unique_search_sets = set()
1207
for searcher in unique_searchers:
1208
will_search_set = frozenset(searcher._next_query)
1209
if will_search_set not in unique_search_sets:
1210
# This searcher is searching a unique set of nodes, let it
1211
unique_search_sets.add(will_search_set)
1212
next_unique_searchers.append(searcher)
1213
unique_searchers = next_unique_searchers
1214
for searcher in common_searchers:
1215
if searcher._next_query:
1218
# All common searcher have stopped searching
1221
def _remove_simple_descendants(self, revisions, parent_map):
1222
"""remove revisions which are children of other ones in the set
1224
This doesn't do any graph searching, it just checks the immediate
1225
parent_map to find if there are any children which can be removed.
1227
:param revisions: A set of revision_ids
1228
:return: A set of revision_ids with the children removed
1230
simple_ancestors = revisions.copy()
1231
# TODO: jam 20071214 we *could* restrict it to searching only the
1232
# parent_map of revisions already present in 'revisions', but
1233
# considering the general use case, I think this is actually
1236
# This is the same as the following loop. I don't know that it is any
1238
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1239
## if p_ids is not None and revisions.intersection(p_ids))
1240
## return simple_ancestors
1242
# Yet Another Way, invert the parent map (which can be cached)
1244
## for revision_id, parent_ids in parent_map.iteritems():
1245
## for p_id in parent_ids:
1246
## descendants.setdefault(p_id, []).append(revision_id)
1247
## for revision in revisions.intersection(descendants):
1248
## simple_ancestors.difference_update(descendants[revision])
1249
## return simple_ancestors
1250
for revision, parent_ids in parent_map.iteritems():
1251
if parent_ids is None:
1253
for parent_id in parent_ids:
1254
if parent_id in revisions:
1255
# This node has a parent present in the set, so we can
1257
simple_ancestors.discard(revision)
1259
return simple_ancestors
1262
class HeadsCache(object):
1263
"""A cache of results for graph heads calls."""
1265
def __init__(self, graph):
1269
def heads(self, keys):
1270
"""Return the heads of keys.
1272
This matches the API of Graph.heads(), specifically the return value is
1273
a set which can be mutated, and ordering of the input is not preserved
1276
:see also: Graph.heads.
1277
:param keys: The keys to calculate heads for.
1278
:return: A set containing the heads, which may be mutated without
1279
affecting future lookups.
1281
keys = frozenset(keys)
1283
return set(self._heads[keys])
1285
heads = self.graph.heads(keys)
1286
self._heads[keys] = heads
1290
class FrozenHeadsCache(object):
1291
"""Cache heads() calls, assuming the caller won't modify them."""
1293
def __init__(self, graph):
1297
def heads(self, keys):
1298
"""Return the heads of keys.
1300
Similar to Graph.heads(). The main difference is that the return value
1301
is a frozen set which cannot be mutated.
1303
:see also: Graph.heads.
1304
:param keys: The keys to calculate heads for.
1305
:return: A frozenset containing the heads.
1307
keys = frozenset(keys)
1309
return self._heads[keys]
1311
heads = frozenset(self.graph.heads(keys))
1312
self._heads[keys] = heads
1315
def cache(self, keys, heads):
1316
"""Store a known value."""
1317
self._heads[frozenset(keys)] = frozenset(heads)
292
1320
class _BreadthFirstSearcher(object):
293
"""Parallel search the breadth-first the ancestry of revisions.
1321
"""Parallel search breadth-first the ancestry of revisions.
295
1323
This class implements the iterator protocol, but additionally
296
1324
1. provides a set of seen ancestors, and
300
1328
def __init__(self, revisions, parents_provider):
301
self._start = set(revisions)
302
self._search_revisions = None
303
self.seen = set(revisions)
304
self._parents_provider = parents_provider
1329
self._iterations = 0
1330
self._next_query = set(revisions)
1332
self._started_keys = set(self._next_query)
1333
self._stopped_keys = set()
1334
self._parents_provider = parents_provider
1335
self._returning = 'next_with_ghosts'
1336
self._current_present = set()
1337
self._current_ghosts = set()
1338
self._current_parents = {}
306
1340
def __repr__(self):
307
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
308
' self.seen=%r)' % (self._search_revisions, self.seen))
1341
if self._iterations:
1342
prefix = "searching"
1345
search = '%s=%r' % (prefix, list(self._next_query))
1346
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1347
' seen=%r)' % (self._iterations, search, list(self.seen)))
1349
def get_state(self):
1350
"""Get the current state of this searcher.
1352
:return: Tuple with started keys, excludes and included keys
1354
if self._returning == 'next':
1355
# We have to know the current nodes children to be able to list the
1356
# exclude keys for them. However, while we could have a second
1357
# look-ahead result buffer and shuffle things around, this method
1358
# is typically only called once per search - when memoising the
1359
# results of the search.
1360
found, ghosts, next, parents = self._do_query(self._next_query)
1361
# pretend we didn't query: perhaps we should tweak _do_query to be
1362
# entirely stateless?
1363
self.seen.difference_update(next)
1364
next_query = next.union(ghosts)
1366
next_query = self._next_query
1367
excludes = self._stopped_keys.union(next_query)
1368
included_keys = self.seen.difference(excludes)
1369
return self._started_keys, excludes, included_keys
1371
def _get_result(self):
1372
"""Get a SearchResult for the current state of this searcher.
1374
:return: A SearchResult for this search so far. The SearchResult is
1375
static - the search can be advanced and the search result will not
1376
be invalidated or altered.
1378
from bzrlib.vf_search import SearchResult
1379
(started_keys, excludes, included_keys) = self.get_state()
1380
return SearchResult(started_keys, excludes, len(included_keys),
1386
except StopIteration:
311
1390
"""Return the next ancestors of this revision.
313
1392
Ancestors are returned in the order they are seen in a breadth-first
314
traversal. No ancestor will be returned more than once.
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.
316
if self._search_revisions is None:
317
self._search_revisions = self._start
1402
if self._returning != 'next':
1403
# switch to returning the query, not the results.
1404
self._returning = 'next'
1405
self._iterations += 1
319
new_search_revisions = set()
320
for parents in self._parents_provider.get_parents(
321
self._search_revisions):
324
new_search_revisions.update(p for p in parents if
326
self._search_revisions = new_search_revisions
327
if len(self._search_revisions) == 0:
328
raise StopIteration()
329
self.seen.update(self._search_revisions)
330
return self._search_revisions
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
1415
def next_with_ghosts(self):
1416
"""Return the next found ancestors, with ghosts split out.
1418
Ancestors are returned in the order they are seen in a breadth-first
1419
traversal. No ancestor will be returned more than once. Ancestors are
1420
returned only after asking for their parents, which allows us to detect
1421
which revisions are ghosts and which are not.
1423
:return: A tuple with (present ancestors, ghost ancestors) sets.
1425
if self._returning != 'next_with_ghosts':
1426
# switch to returning the results, not the current query.
1427
self._returning = 'next_with_ghosts'
1429
if len(self._next_query) == 0:
1430
raise StopIteration()
1432
return self._current_present, self._current_ghosts
1435
"""Advance the search.
1437
Updates self.seen, self._next_query, self._current_present,
1438
self._current_ghosts, self._current_parents and self._iterations.
1440
self._iterations += 1
1441
found, ghosts, next, parents = self._do_query(self._next_query)
1442
self._current_present = found
1443
self._current_ghosts = ghosts
1444
self._next_query = next
1445
self._current_parents = parents
1446
# ghosts are implicit stop points, otherwise the search cannot be
1447
# repeated when ghosts are filled.
1448
self._stopped_keys.update(ghosts)
1450
def _do_query(self, revisions):
1451
"""Query for revisions.
1453
Adds revisions to the seen set.
1455
:param revisions: Revisions to query.
1456
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1457
set(parents_of_found_revisions), dict(found_revisions:parents)).
1459
found_revisions = set()
1460
parents_of_found = set()
1461
# revisions may contain nodes that point to other nodes in revisions:
1462
# we want to filter them out.
1464
seen.update(revisions)
1465
parent_map = self._parents_provider.get_parent_map(revisions)
1466
found_revisions.update(parent_map)
1467
for rev_id, parents in parent_map.iteritems():
1470
new_found_parents = [p for p in parents if p not in seen]
1471
if new_found_parents:
1472
# Calling set.update() with an empty generator is actually
1474
parents_of_found.update(new_found_parents)
1475
ghost_revisions = revisions - found_revisions
1476
return found_revisions, ghost_revisions, parents_of_found, parent_map
332
1478
def __iter__(self):
335
def find_seen_ancestors(self, revision):
336
"""Find ancestors of this revision that have already been seen."""
337
searcher = _BreadthFirstSearcher([revision], self._parents_provider)
338
seen_ancestors = set()
339
for ancestors in searcher:
340
for ancestor in ancestors:
341
if ancestor not in self.seen:
342
searcher.stop_searching_any([ancestor])
344
seen_ancestors.add(ancestor)
1481
def find_seen_ancestors(self, revisions):
1482
"""Find ancestors of these revisions that have already been seen.
1484
This function generally makes the assumption that querying for the
1485
parents of a node that has already been queried is reasonably cheap.
1486
(eg, not a round trip to a remote host).
1488
# TODO: Often we might ask one searcher for its seen ancestors, and
1489
# then ask another searcher the same question. This can result in
1490
# searching the same revisions repeatedly if the two searchers
1491
# have a lot of overlap.
1492
all_seen = self.seen
1493
pending = set(revisions).intersection(all_seen)
1494
seen_ancestors = set(pending)
1496
if self._returning == 'next':
1497
# self.seen contains what nodes have been returned, not what nodes
1498
# have been queried. We don't want to probe for nodes that haven't
1499
# been searched yet.
1500
not_searched_yet = self._next_query
1502
not_searched_yet = ()
1503
pending.difference_update(not_searched_yet)
1504
get_parent_map = self._parents_provider.get_parent_map
1506
parent_map = get_parent_map(pending)
1508
# We don't care if it is a ghost, since it can't be seen if it is
1510
for parent_ids in parent_map.itervalues():
1511
all_parents.extend(parent_ids)
1512
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1513
seen_ancestors.update(next_pending)
1514
next_pending.difference_update(not_searched_yet)
1515
pending = next_pending
345
1517
return seen_ancestors
347
1519
def stop_searching_any(self, revisions):
349
1521
Remove any of the specified revisions from the search list.
351
1523
None of the specified revisions are required to be present in the
352
search list. In this case, the call is a no-op.
1526
It is okay to call stop_searching_any() for revisions which were seen
1527
in previous iterations. It is the callers responsibility to call
1528
find_seen_ancestors() to make sure that current search tips that are
1529
ancestors of those revisions are also stopped. All explicitly stopped
1530
revisions will be excluded from the search result's get_keys(), though.
354
stopped = self._search_revisions.intersection(revisions)
355
self._search_revisions = self._search_revisions.difference(revisions)
1532
# TODO: does this help performance?
1535
revisions = frozenset(revisions)
1536
if self._returning == 'next':
1537
stopped = self._next_query.intersection(revisions)
1538
self._next_query = self._next_query.difference(revisions)
1540
stopped_present = self._current_present.intersection(revisions)
1541
stopped = stopped_present.union(
1542
self._current_ghosts.intersection(revisions))
1543
self._current_present.difference_update(stopped)
1544
self._current_ghosts.difference_update(stopped)
1545
# stopping 'x' should stop returning parents of 'x', but
1546
# not if 'y' always references those same parents
1547
stop_rev_references = {}
1548
for rev in stopped_present:
1549
for parent_id in self._current_parents[rev]:
1550
if parent_id not in stop_rev_references:
1551
stop_rev_references[parent_id] = 0
1552
stop_rev_references[parent_id] += 1
1553
# if only the stopped revisions reference it, the ref count will be
1555
for parents in self._current_parents.itervalues():
1556
for parent_id in parents:
1558
stop_rev_references[parent_id] -= 1
1561
stop_parents = set()
1562
for rev_id, refs in stop_rev_references.iteritems():
1564
stop_parents.add(rev_id)
1565
self._next_query.difference_update(stop_parents)
1566
self._stopped_keys.update(stopped)
1567
self._stopped_keys.update(revisions)
358
1570
def start_searching(self, revisions):
359
if self._search_revisions is None:
360
self._start = set(revisions)
1571
"""Add revisions to the search.
1573
The parents of revisions will be returned from the next call to next()
1574
or next_with_ghosts(). If next_with_ghosts was the most recently used
1575
next* call then the return value is the result of looking up the
1576
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1578
revisions = frozenset(revisions)
1579
self._started_keys.update(revisions)
1580
new_revisions = revisions.difference(self.seen)
1581
if self._returning == 'next':
1582
self._next_query.update(new_revisions)
1583
self.seen.update(new_revisions)
362
self._search_revisions.update(revisions.difference(self.seen))
363
self.seen.update(revisions)
1585
# perform a query on revisions
1586
revs, ghosts, query, parents = self._do_query(revisions)
1587
self._stopped_keys.update(ghosts)
1588
self._current_present.update(revs)
1589
self._current_ghosts.update(ghosts)
1590
self._next_query.update(query)
1591
self._current_parents.update(parents)
1595
def invert_parent_map(parent_map):
1596
"""Given a map from child => parents, create a map of parent=>children"""
1598
for child, parents in parent_map.iteritems():
1600
# Any given parent is likely to have only a small handful
1601
# of children, many will have only one. So we avoid mem overhead of
1602
# a list, in exchange for extra copying of tuples
1603
if p not in child_map:
1604
child_map[p] = (child,)
1606
child_map[p] = child_map[p] + (child,)
1610
def collapse_linear_regions(parent_map):
1611
"""Collapse regions of the graph that are 'linear'.
1617
can be collapsed by removing B and getting::
1621
:param parent_map: A dictionary mapping children to their parents
1622
:return: Another dictionary with 'linear' chains collapsed
1624
# Note: this isn't a strictly minimal collapse. For example:
1632
# Will not have 'D' removed, even though 'E' could fit. Also:
1638
# A and C are both kept because they are edges of the graph. We *could* get
1639
# rid of A if we wanted.
1647
# Will not have any nodes removed, even though you do have an
1648
# 'uninteresting' linear D->B and E->C
1650
for child, parents in parent_map.iteritems():
1651
children.setdefault(child, [])
1653
children.setdefault(p, []).append(child)
1655
orig_children = dict(children)
1657
result = dict(parent_map)
1658
for node in parent_map:
1659
parents = result[node]
1660
if len(parents) == 1:
1661
parent_children = children[parents[0]]
1662
if len(parent_children) != 1:
1663
# This is not the only child
1665
node_children = children[node]
1666
if len(node_children) != 1:
1668
child_parents = result.get(node_children[0], None)
1669
if len(child_parents) != 1:
1670
# This is not its only parent
1672
# The child of this node only points at it, and the parent only has
1673
# this as a child. remove this node, and join the others together
1674
result[node_children[0]] = parents
1675
children[parents[0]] = node_children
1683
class GraphThunkIdsToKeys(object):
1684
"""Forwards calls about 'ids' to be about keys internally."""
1686
def __init__(self, graph):
1689
def topo_sort(self):
1690
return [r for (r,) in self._graph.topo_sort()]
1692
def heads(self, ids):
1693
"""See Graph.heads()"""
1694
as_keys = [(i,) for i in ids]
1695
head_keys = self._graph.heads(as_keys)
1696
return set([h[0] for h in head_keys])
1698
def merge_sort(self, tip_revision):
1699
nodes = self._graph.merge_sort((tip_revision,))
1701
node.key = node.key[0]
1704
def add_node(self, revision, parents):
1705
self._graph.add_node((revision,), [(p,) for p in parents])
1708
_counters = [0,0,0,0,0,0,0]
1710
from bzrlib._known_graph_pyx import KnownGraph
1711
except ImportError, e:
1712
osutils.failed_to_load_extension(e)
1713
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
