124
95
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.
96
"""A parents provider which will cache the revision => parents in a dict.
98
This is useful for providers that have an expensive lookup.
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.
101
def __init__(self, parent_provider):
143
102
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)
103
# Theoretically we could use an LRUCache here
151
106
def __repr__(self):
152
107
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
109
def get_parent_map(self, keys):
186
"""See StackedParentsProvider.get_parent_map."""
110
"""See _StackedParentsProvider.get_parent_map"""
112
# If the _real_provider doesn't have a key, we cache a value of None,
113
# which we then later use to realize we cannot provide a value for that
187
116
cache = self._cache
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)
120
if value is not None:
121
parent_map[key] = value
126
new_parents = self._real_provider.get_parent_map(needed)
127
cache.update(new_parents)
128
parent_map.update(new_parents)
129
needed.difference_update(new_parents)
130
cache.update(dict.fromkeys(needed, None))
231
134
class Graph(object):
298
200
def find_difference(self, left_revision, right_revision):
299
201
"""Determine the graph difference between two revisions"""
300
border, common, searchers = self._find_border_ancestors(
202
border, common, (left, right) = self._find_border_ancestors(
301
203
[left_revision, right_revision])
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
204
return (left.difference(right).difference(common),
205
right.difference(left).difference(common))
207
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
def get_parents(self, revisions):
209
"""Find revision ids of the parents of a list of revisions
211
A list is returned of the same length as the input. Each entry
212
is a list of parent ids for the corresponding input revision.
214
[NULL_REVISION] is used as the parent of the first user-committed
215
revision. Its parent list is empty.
217
If the revision is not present (i.e. a ghost), None is used in place
218
of the list of parents.
220
Deprecated in bzr 1.2 - please see get_parent_map.
222
parents = self.get_parent_map(revisions)
223
return [parent.get(r, None) for r in revisions]
720
225
def get_parent_map(self, revisions):
721
226
"""Get a map of key:parent_list for revisions.
1059
469
return set([candidate_descendant]) == self.heads(
1060
470
[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
473
class HeadsCache(object):
1263
474
"""A cache of results for graph heads calls."""
1716
796
return self._keys
1719
"""Return false if the search lists 1 or more revisions."""
1720
return self._recipe[3] == 0
1722
def refine(self, seen, referenced):
1723
"""Create a new search by refining this search.
1725
:param seen: Revisions that have been satisfied.
1726
:param referenced: Revision references observed while satisfying some
1729
start = self._recipe[1]
1730
exclude = self._recipe[2]
1731
count = self._recipe[3]
1732
keys = self.get_keys()
1733
# New heads = referenced + old heads - seen things - exclude
1734
pending_refs = set(referenced)
1735
pending_refs.update(start)
1736
pending_refs.difference_update(seen)
1737
pending_refs.difference_update(exclude)
1738
# New exclude = old exclude + satisfied heads
1739
seen_heads = start.intersection(seen)
1740
exclude.update(seen_heads)
1741
# keys gets seen removed
1743
# length is reduced by len(seen)
1745
return SearchResult(pending_refs, exclude, count, keys)
1748
class PendingAncestryResult(AbstractSearchResult):
1749
"""A search result that will reconstruct the ancestry for some graph heads.
1751
Unlike SearchResult, this doesn't hold the complete search result in
1752
memory, it just holds a description of how to generate it.
1755
def __init__(self, heads, repo):
1758
:param heads: an iterable of graph heads.
1759
:param repo: a repository to use to generate the ancestry for the given
1762
self.heads = frozenset(heads)
1766
if len(self.heads) > 5:
1767
heads_repr = repr(list(self.heads)[:5])[:-1]
1768
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1770
heads_repr = repr(self.heads)
1771
return '<%s heads:%s repo:%r>' % (
1772
self.__class__.__name__, heads_repr, self.repo)
1774
def get_recipe(self):
1775
"""Return a recipe that can be used to replay this search.
1777
The recipe allows reconstruction of the same results at a later date.
1779
:seealso SearchResult.get_recipe:
1781
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1782
To recreate this result, create a PendingAncestryResult with the
1785
return ('proxy-search', self.heads, set(), -1)
1787
def get_network_struct(self):
1788
parts = ['ancestry-of']
1789
parts.extend(self.heads)
1793
"""See SearchResult.get_keys.
1795
Returns all the keys for the ancestry of the heads, excluding
1798
return self._get_keys(self.repo.get_graph())
1800
def _get_keys(self, graph):
1801
NULL_REVISION = revision.NULL_REVISION
1802
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1803
if key != NULL_REVISION and parents is not None]
1807
"""Return false if the search lists 1 or more revisions."""
1808
if revision.NULL_REVISION in self.heads:
1809
return len(self.heads) == 1
1811
return len(self.heads) == 0
1813
def refine(self, seen, referenced):
1814
"""Create a new search by refining this search.
1816
:param seen: Revisions that have been satisfied.
1817
:param referenced: Revision references observed while satisfying some
1820
referenced = self.heads.union(referenced)
1821
return PendingAncestryResult(referenced - seen, self.repo)
1824
class EmptySearchResult(AbstractSearchResult):
1825
"""An empty search result."""
1831
class EverythingResult(AbstractSearchResult):
1832
"""A search result that simply requests everything in the repository."""
1834
def __init__(self, repo):
1838
return '%s(%r)' % (self.__class__.__name__, self._repo)
1840
def get_recipe(self):
1841
raise NotImplementedError(self.get_recipe)
1843
def get_network_struct(self):
1844
return ('everything',)
1847
if 'evil' in debug.debug_flags:
1848
from bzrlib import remote
1849
if isinstance(self._repo, remote.RemoteRepository):
1850
# warn developers (not users) not to do this
1851
trace.mutter_callsite(
1852
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1853
return self._repo.all_revision_ids()
1856
# It's ok for this to wrongly return False: the worst that can happen
1857
# is that RemoteStreamSource will initiate a get_stream on an empty
1858
# repository. And almost all repositories are non-empty.
1861
def refine(self, seen, referenced):
1862
heads = set(self._repo.all_revision_ids())
1863
heads.difference_update(seen)
1864
heads.update(referenced)
1865
return PendingAncestryResult(heads, self._repo)
1868
class EverythingNotInOther(AbstractSearch):
1869
"""Find all revisions in that are in one repo but not the other."""
1871
def __init__(self, to_repo, from_repo, find_ghosts=False):
1872
self.to_repo = to_repo
1873
self.from_repo = from_repo
1874
self.find_ghosts = find_ghosts
1877
return self.to_repo.search_missing_revision_ids(
1878
self.from_repo, find_ghosts=self.find_ghosts)
1881
class NotInOtherForRevs(AbstractSearch):
1882
"""Find all revisions missing in one repo for a some specific heads."""
1884
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1885
find_ghosts=False, limit=None):
1888
:param required_ids: revision IDs of heads that must be found, or else
1889
the search will fail with NoSuchRevision. All revisions in their
1890
ancestry not already in the other repository will be included in
1892
:param if_present_ids: revision IDs of heads that may be absent in the
1893
source repository. If present, then their ancestry not already
1894
found in other will be included in the search result.
1895
:param limit: maximum number of revisions to fetch
1897
self.to_repo = to_repo
1898
self.from_repo = from_repo
1899
self.find_ghosts = find_ghosts
1900
self.required_ids = required_ids
1901
self.if_present_ids = if_present_ids
1905
if len(self.required_ids) > 5:
1906
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1908
reqd_revs_repr = repr(self.required_ids)
1909
if self.if_present_ids and len(self.if_present_ids) > 5:
1910
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1912
ifp_revs_repr = repr(self.if_present_ids)
1914
return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
1916
self.__class__.__name__, self.from_repo, self.to_repo,
1917
self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
1921
return self.to_repo.search_missing_revision_ids(
1922
self.from_repo, revision_ids=self.required_ids,
1923
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
1927
def invert_parent_map(parent_map):
1928
"""Given a map from child => parents, create a map of parent=>children"""
1930
for child, parents in parent_map.iteritems():
1932
# Any given parent is likely to have only a small handful
1933
# of children, many will have only one. So we avoid mem overhead of
1934
# a list, in exchange for extra copying of tuples
1935
if p not in child_map:
1936
child_map[p] = (child,)
1938
child_map[p] = child_map[p] + (child,)
1942
def _find_possible_heads(parent_map, tip_keys, depth):
1943
"""Walk backwards (towards children) through the parent_map.
1945
This finds 'heads' that will hopefully succinctly describe our search
1948
child_map = invert_parent_map(parent_map)
1950
current_roots = tip_keys
1951
walked = set(current_roots)
1952
while current_roots and depth > 0:
1955
children_update = children.update
1956
for p in current_roots:
1957
# Is it better to pre- or post- filter the children?
1959
children_update(child_map[p])
1962
# If we've seen a key before, we don't want to walk it again. Note that
1963
# 'children' stays relatively small while 'walked' grows large. So
1964
# don't use 'difference_update' here which has to walk all of 'walked'.
1965
# '.difference' is smart enough to walk only children and compare it to
1967
children = children.difference(walked)
1968
walked.update(children)
1969
current_roots = children
1971
# We walked to the end of depth, so these are the new tips.
1972
heads.update(current_roots)
1976
def _run_search(parent_map, heads, exclude_keys):
1977
"""Given a parent map, run a _BreadthFirstSearcher on it.
1979
Start at heads, walk until you hit exclude_keys. As a further improvement,
1980
watch for any heads that you encounter while walking, which means they were
1981
not heads of the search.
1983
This is mostly used to generate a succinct recipe for how to walk through
1986
:return: (_BreadthFirstSearcher, set(heads_encountered_by_walking))
1988
g = Graph(DictParentsProvider(parent_map))
1989
s = g._make_breadth_first_searcher(heads)
1993
next_revs = s.next()
1994
except StopIteration:
1996
for parents in s._current_parents.itervalues():
1997
f_heads = heads.intersection(parents)
1999
found_heads.update(f_heads)
2000
stop_keys = exclude_keys.intersection(next_revs)
2002
s.stop_searching_any(stop_keys)
2003
for parents in s._current_parents.itervalues():
2004
f_heads = heads.intersection(parents)
2006
found_heads.update(f_heads)
2007
return s, found_heads
2010
def limited_search_result_from_parent_map(parent_map, missing_keys, tip_keys,
2012
"""Transform a parent_map that is searching 'tip_keys' into an
2013
approximate SearchResult.
2015
We should be able to generate a SearchResult from a given set of starting
2016
keys, that covers a subset of parent_map that has the last step pointing at
2017
tip_keys. This is to handle the case that really-long-searches shouldn't be
2018
started from scratch on each get_parent_map request, but we *do* want to
2019
filter out some of the keys that we've already seen, so we don't get
2020
information that we already know about on every request.
2022
The server will validate the search (that starting at start_keys and
2023
stopping at stop_keys yields the exact key_count), so we have to be careful
2024
to give an exact recipe.
2027
1) Invert parent_map to get child_map (todo: have it cached and pass it
2029
2) Starting at tip_keys, walk towards children for 'depth' steps.
2030
3) At that point, we have the 'start' keys.
2031
4) Start walking parent_map from 'start' keys, counting how many keys
2032
are seen, and generating stop_keys for anything that would walk
2033
outside of the parent_map.
2035
:param parent_map: A map from {child_id: (parent_ids,)}
2036
:param missing_keys: parent_ids that we know are unavailable
2037
:param tip_keys: the revision_ids that we are searching
2038
:param depth: How far back to walk.
2041
# No search to send, because we haven't done any searching yet.
2043
heads = _find_possible_heads(parent_map, tip_keys, depth)
2044
s, found_heads = _run_search(parent_map, heads, set(tip_keys))
2045
_, start_keys, exclude_keys, key_count = s.get_result().get_recipe()
2047
# Anything in found_heads are redundant start_keys, we hit them while
2048
# walking, so we can exclude them from the start list.
2049
start_keys = set(start_keys).difference(found_heads)
2050
return start_keys, exclude_keys, key_count
2053
def search_result_from_parent_map(parent_map, missing_keys):
2054
"""Transform a parent_map into SearchResult information."""
2056
# parent_map is empty or None, simple search result
2058
# start_set is all the keys in the cache
2059
start_set = set(parent_map)
2060
# result set is all the references to keys in the cache
2061
result_parents = set()
2062
for parents in parent_map.itervalues():
2063
result_parents.update(parents)
2064
stop_keys = result_parents.difference(start_set)
2065
# We don't need to send ghosts back to the server as a position to
2067
stop_keys.difference_update(missing_keys)
2068
key_count = len(parent_map)
2069
if (revision.NULL_REVISION in result_parents
2070
and revision.NULL_REVISION in missing_keys):
2071
# If we pruned NULL_REVISION from the stop_keys because it's also
2072
# in our cache of "missing" keys we need to increment our key count
2073
# by 1, because the reconsitituted SearchResult on the server will
2074
# still consider NULL_REVISION to be an included key.
2076
included_keys = start_set.intersection(result_parents)
2077
start_set.difference_update(included_keys)
2078
return start_set, stop_keys, key_count
2081
def collapse_linear_regions(parent_map):
2082
"""Collapse regions of the graph that are 'linear'.
2088
can be collapsed by removing B and getting::
2092
:param parent_map: A dictionary mapping children to their parents
2093
:return: Another dictionary with 'linear' chains collapsed
2095
# Note: this isn't a strictly minimal collapse. For example:
2103
# Will not have 'D' removed, even though 'E' could fit. Also:
2109
# A and C are both kept because they are edges of the graph. We *could* get
2110
# rid of A if we wanted.
2118
# Will not have any nodes removed, even though you do have an
2119
# 'uninteresting' linear D->B and E->C
2121
for child, parents in parent_map.iteritems():
2122
children.setdefault(child, [])
2124
children.setdefault(p, []).append(child)
2126
orig_children = dict(children)
2128
result = dict(parent_map)
2129
for node in parent_map:
2130
parents = result[node]
2131
if len(parents) == 1:
2132
parent_children = children[parents[0]]
2133
if len(parent_children) != 1:
2134
# This is not the only child
2136
node_children = children[node]
2137
if len(node_children) != 1:
2139
child_parents = result.get(node_children[0], None)
2140
if len(child_parents) != 1:
2141
# This is not its only parent
2143
# The child of this node only points at it, and the parent only has
2144
# this as a child. remove this node, and join the others together
2145
result[node_children[0]] = parents
2146
children[parents[0]] = node_children
2154
class GraphThunkIdsToKeys(object):
2155
"""Forwards calls about 'ids' to be about keys internally."""
2157
def __init__(self, graph):
2160
def topo_sort(self):
2161
return [r for (r,) in self._graph.topo_sort()]
2163
def heads(self, ids):
2164
"""See Graph.heads()"""
2165
as_keys = [(i,) for i in ids]
2166
head_keys = self._graph.heads(as_keys)
2167
return set([h[0] for h in head_keys])
2169
def merge_sort(self, tip_revision):
2170
nodes = self._graph.merge_sort((tip_revision,))
2172
node.key = node.key[0]
2175
def add_node(self, revision, parents):
2176
self._graph.add_node((revision,), [(p,) for p in parents])
2179
_counters = [0,0,0,0,0,0,0]
2181
from bzrlib._known_graph_pyx import KnownGraph
2182
except ImportError, e:
2183
osutils.failed_to_load_extension(e)
2184
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
