1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27
from bzrlib.deprecated_graph import (node_distances, select_farthest)
29
STEP_UNIQUE_SEARCHER_EVERY = 5
31
# DIAGRAM of terminology
41
# In this diagram, relative to G and H:
42
# A, B, C, D, E are common ancestors.
43
# C, D and E are border ancestors, because each has a non-common descendant.
44
# D and E are least common ancestors because none of their descendants are
46
# C is not a least common ancestor because its descendant, E, is a common
49
# The find_unique_lca algorithm will pick A in two steps:
50
# 1. find_lca('G', 'H') => ['D', 'E']
51
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
54
class DictParentsProvider(object):
55
"""A parents provider for Graph objects."""
57
def __init__(self, ancestry):
58
self.ancestry = ancestry
61
return 'DictParentsProvider(%r)' % self.ancestry
63
def get_parent_map(self, keys):
64
"""See _StackedParentsProvider.get_parent_map"""
65
ancestry = self.ancestry
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
class _StackedParentsProvider(object):
71
def __init__(self, parent_providers):
72
self._parent_providers = parent_providers
75
return "_StackedParentsProvider(%r)" % self._parent_providers
77
def get_parent_map(self, keys):
78
"""Get a mapping of keys => parents
80
A dictionary is returned with an entry for each key present in this
81
source. If this source doesn't have information about a key, it should
84
[NULL_REVISION] is used as the parent of the first user-committed
85
revision. Its parent list is empty.
87
:param keys: An iterable returning keys to check (eg revision_ids)
88
:return: A dictionary mapping each key to its parents
92
for parents_provider in self._parent_providers:
93
new_found = parents_provider.get_parent_map(remaining)
94
found.update(new_found)
95
remaining.difference_update(new_found)
101
class CachingParentsProvider(object):
102
"""A parents provider which will cache the revision => parents as a dict.
104
This is useful for providers which have an expensive look up.
106
Either a ParentsProvider or a get_parent_map-like callback may be
107
supplied. If it provides extra un-asked-for parents, they will be cached,
108
but filtered out of get_parent_map.
110
The cache is enabled by default, but may be disabled and re-enabled.
112
def __init__(self, parent_provider=None, get_parent_map=None, debug=False):
115
:param parent_provider: The ParentProvider to use. It or
116
get_parent_map must be supplied.
117
:param get_parent_map: The get_parent_map callback to use. It or
118
parent_provider must be supplied.
119
:param debug: If true, mutter debugging messages.
121
self._real_provider = parent_provider
122
if get_parent_map is None:
123
self._get_parent_map = self._real_provider.get_parent_map
125
self._get_parent_map = get_parent_map
127
self._cache_misses = True
130
self._requested_parents = None
133
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
135
def enable_cache(self, cache_misses=True):
137
if self._cache is not None:
138
raise AssertionError('Cache enabled when already enabled.')
140
self._cache_misses = cache_misses
142
self._requested_parents = set()
144
def disable_cache(self):
145
"""Disable and clear the cache."""
148
self._requested_parents = None
150
def get_cached_map(self):
151
"""Return any cached get_parent_map values."""
152
if self._cache is None:
154
return dict((k, v) for k, v in self._cache.items()
157
def get_parent_map(self, keys):
158
"""See _StackedParentsProvider.get_parent_map."""
159
# Hack to build up the caching logic.
160
ancestry = self._cache
162
# Caching is disabled.
163
missing_revisions = set(keys)
166
missing_revisions = set(key for key in keys if key not in ancestry)
167
if missing_revisions:
168
parent_map = self._get_parent_map(missing_revisions)
170
mutter('re-retrieved revisions: %d of %d',
171
len(set(ancestry).intersection(parent_map)),
173
ancestry.update(parent_map)
174
if self._cache_misses:
175
# None is never a valid parents list, so it can be used to
177
ancestry.update(dict((k, None) for k in missing_revisions
178
if k not in parent_map))
179
present_keys = [k for k in keys if ancestry.get(k) is not None]
181
if self._requested_parents is not None and len(ancestry) != 0:
182
self._requested_parents.update(present_keys)
183
mutter('Current hit rate: %d%%',
184
100.0 * len(self._requested_parents) / len(ancestry))
185
return dict((k, ancestry[k]) for k in present_keys)
189
"""Provide incremental access to revision graphs.
191
This is the generic implementation; it is intended to be subclassed to
192
specialize it for other repository types.
195
def __init__(self, parents_provider):
196
"""Construct a Graph that uses several graphs as its input
198
This should not normally be invoked directly, because there may be
199
specialized implementations for particular repository types. See
200
Repository.get_graph().
202
:param parents_provider: An object providing a get_parent_map call
203
conforming to the behavior of
204
StackedParentsProvider.get_parent_map.
206
if getattr(parents_provider, 'get_parents', None) is not None:
207
self.get_parents = parents_provider.get_parents
208
if getattr(parents_provider, 'get_parent_map', None) is not None:
209
self.get_parent_map = parents_provider.get_parent_map
210
self._parents_provider = parents_provider
213
return 'Graph(%r)' % self._parents_provider
215
def find_lca(self, *revisions):
216
"""Determine the lowest common ancestors of the provided revisions
218
A lowest common ancestor is a common ancestor none of whose
219
descendants are common ancestors. In graphs, unlike trees, there may
220
be multiple lowest common ancestors.
222
This algorithm has two phases. Phase 1 identifies border ancestors,
223
and phase 2 filters border ancestors to determine lowest common
226
In phase 1, border ancestors are identified, using a breadth-first
227
search starting at the bottom of the graph. Searches are stopped
228
whenever a node or one of its descendants is determined to be common
230
In phase 2, the border ancestors are filtered to find the least
231
common ancestors. This is done by searching the ancestries of each
234
Phase 2 is perfomed on the principle that a border ancestor that is
235
not an ancestor of any other border ancestor is a least common
238
Searches are stopped when they find a node that is determined to be a
239
common ancestor of all border ancestors, because this shows that it
240
cannot be a descendant of any border ancestor.
242
The scaling of this operation should be proportional to
243
1. The number of uncommon ancestors
244
2. The number of border ancestors
245
3. The length of the shortest path between a border ancestor and an
246
ancestor of all border ancestors.
248
border_common, common, sides = self._find_border_ancestors(revisions)
249
# We may have common ancestors that can be reached from each other.
250
# - ask for the heads of them to filter it down to only ones that
251
# cannot be reached from each other - phase 2.
252
return self.heads(border_common)
254
def find_difference(self, left_revision, right_revision):
255
"""Determine the graph difference between two revisions"""
256
border, common, searchers = self._find_border_ancestors(
257
[left_revision, right_revision])
258
self._search_for_extra_common(common, searchers)
259
left = searchers[0].seen
260
right = searchers[1].seen
261
return (left.difference(right), right.difference(left))
263
def find_distance_to_null(self, target_revision_id, known_revision_ids):
264
"""Find the left-hand distance to the NULL_REVISION.
266
(This can also be considered the revno of a branch at
269
:param target_revision_id: A revision_id which we would like to know
271
:param known_revision_ids: [(revision_id, revno)] A list of known
272
revno, revision_id tuples. We'll use this to seed the search.
274
# Map from revision_ids to a known value for their revno
275
known_revnos = dict(known_revision_ids)
276
cur_tip = target_revision_id
278
NULL_REVISION = revision.NULL_REVISION
279
known_revnos[NULL_REVISION] = 0
281
searching_known_tips = list(known_revnos.keys())
283
unknown_searched = {}
285
while cur_tip not in known_revnos:
286
unknown_searched[cur_tip] = num_steps
288
to_search = set([cur_tip])
289
to_search.update(searching_known_tips)
290
parent_map = self.get_parent_map(to_search)
291
parents = parent_map.get(cur_tip, None)
292
if not parents: # An empty list or None is a ghost
293
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
297
for revision_id in searching_known_tips:
298
parents = parent_map.get(revision_id, None)
302
next_revno = known_revnos[revision_id] - 1
303
if next in unknown_searched:
304
# We have enough information to return a value right now
305
return next_revno + unknown_searched[next]
306
if next in known_revnos:
308
known_revnos[next] = next_revno
309
next_known_tips.append(next)
310
searching_known_tips = next_known_tips
312
# We reached a known revision, so just add in how many steps it took to
314
return known_revnos[cur_tip] + num_steps
316
def find_unique_ancestors(self, unique_revision, common_revisions):
317
"""Find the unique ancestors for a revision versus others.
319
This returns the ancestry of unique_revision, excluding all revisions
320
in the ancestry of common_revisions. If unique_revision is in the
321
ancestry, then the empty set will be returned.
323
:param unique_revision: The revision_id whose ancestry we are
325
XXX: Would this API be better if we allowed multiple revisions on
327
:param common_revisions: Revision_ids of ancestries to exclude.
328
:return: A set of revisions in the ancestry of unique_revision
330
if unique_revision in common_revisions:
333
# Algorithm description
334
# 1) Walk backwards from the unique node and all common nodes.
335
# 2) When a node is seen by both sides, stop searching it in the unique
336
# walker, include it in the common walker.
337
# 3) Stop searching when there are no nodes left for the unique walker.
338
# At this point, you have a maximal set of unique nodes. Some of
339
# them may actually be common, and you haven't reached them yet.
340
# 4) Start new searchers for the unique nodes, seeded with the
341
# information you have so far.
342
# 5) Continue searching, stopping the common searches when the search
343
# tip is an ancestor of all unique nodes.
344
# 6) Aggregate together unique searchers when they are searching the
345
# same tips. When all unique searchers are searching the same node,
346
# stop move it to a single 'all_unique_searcher'.
347
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
348
# Most of the time this produces very little important information.
349
# So don't step it as quickly as the other searchers.
350
# 8) Search is done when all common searchers have completed.
352
unique_searcher, common_searcher = self._find_initial_unique_nodes(
353
[unique_revision], common_revisions)
355
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
359
(all_unique_searcher,
360
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
361
unique_searcher, common_searcher)
363
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
364
unique_tip_searchers, common_searcher)
365
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
366
if 'graph' in debug.debug_flags:
367
trace.mutter('Found %d truly unique nodes out of %d',
368
len(true_unique_nodes), len(unique_nodes))
369
return true_unique_nodes
371
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
372
"""Steps 1-3 of find_unique_ancestors.
374
Find the maximal set of unique nodes. Some of these might actually
375
still be common, but we are sure that there are no other unique nodes.
377
:return: (unique_searcher, common_searcher)
380
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
381
# we know that unique_revisions aren't in common_revisions, so skip
383
unique_searcher.next()
384
common_searcher = self._make_breadth_first_searcher(common_revisions)
386
# As long as we are still finding unique nodes, keep searching
387
while unique_searcher._next_query:
388
next_unique_nodes = set(unique_searcher.step())
389
next_common_nodes = set(common_searcher.step())
391
# Check if either searcher encounters new nodes seen by the other
393
unique_are_common_nodes = next_unique_nodes.intersection(
394
common_searcher.seen)
395
unique_are_common_nodes.update(
396
next_common_nodes.intersection(unique_searcher.seen))
397
if unique_are_common_nodes:
398
ancestors = unique_searcher.find_seen_ancestors(
399
unique_are_common_nodes)
400
# TODO: This is a bit overboard, we only really care about
401
# the ancestors of the tips because the rest we
402
# already know. This is *correct* but causes us to
403
# search too much ancestry.
404
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
405
unique_searcher.stop_searching_any(ancestors)
406
common_searcher.start_searching(ancestors)
408
return unique_searcher, common_searcher
410
def _make_unique_searchers(self, unique_nodes, unique_searcher,
412
"""Create a searcher for all the unique search tips (step 4).
414
As a side effect, the common_searcher will stop searching any nodes
415
that are ancestors of the unique searcher tips.
417
:return: (all_unique_searcher, unique_tip_searchers)
419
unique_tips = self._remove_simple_descendants(unique_nodes,
420
self.get_parent_map(unique_nodes))
422
if len(unique_tips) == 1:
423
unique_tip_searchers = []
424
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
426
unique_tip_searchers = []
427
for tip in unique_tips:
428
revs_to_search = unique_searcher.find_seen_ancestors([tip])
429
revs_to_search.update(
430
common_searcher.find_seen_ancestors(revs_to_search))
431
searcher = self._make_breadth_first_searcher(revs_to_search)
432
# We don't care about the starting nodes.
433
searcher._label = tip
435
unique_tip_searchers.append(searcher)
437
ancestor_all_unique = None
438
for searcher in unique_tip_searchers:
439
if ancestor_all_unique is None:
440
ancestor_all_unique = set(searcher.seen)
442
ancestor_all_unique = ancestor_all_unique.intersection(
444
# Collapse all the common nodes into a single searcher
445
all_unique_searcher = self._make_breadth_first_searcher(
447
if ancestor_all_unique:
448
# We've seen these nodes in all the searchers, so we'll just go to
450
all_unique_searcher.step()
452
# Stop any search tips that are already known as ancestors of the
454
stopped_common = common_searcher.stop_searching_any(
455
common_searcher.find_seen_ancestors(ancestor_all_unique))
458
for searcher in unique_tip_searchers:
459
total_stopped += len(searcher.stop_searching_any(
460
searcher.find_seen_ancestors(ancestor_all_unique)))
461
if 'graph' in debug.debug_flags:
462
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
463
' (%d stopped search tips, %d common ancestors'
464
' (%d stopped common)',
465
len(unique_nodes), len(unique_tip_searchers),
466
total_stopped, len(ancestor_all_unique),
468
return all_unique_searcher, unique_tip_searchers
470
def _step_unique_and_common_searchers(self, common_searcher,
471
unique_tip_searchers,
473
"""Step all the searchers"""
474
newly_seen_common = set(common_searcher.step())
475
newly_seen_unique = set()
476
for searcher in unique_tip_searchers:
477
next = set(searcher.step())
478
next.update(unique_searcher.find_seen_ancestors(next))
479
next.update(common_searcher.find_seen_ancestors(next))
480
for alt_searcher in unique_tip_searchers:
481
if alt_searcher is searcher:
483
next.update(alt_searcher.find_seen_ancestors(next))
484
searcher.start_searching(next)
485
newly_seen_unique.update(next)
486
return newly_seen_common, newly_seen_unique
488
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
490
newly_seen_unique, step_all_unique):
491
"""Find nodes that are common to all unique_tip_searchers.
493
If it is time, step the all_unique_searcher, and add its nodes to the
496
common_to_all_unique_nodes = newly_seen_unique.copy()
497
for searcher in unique_tip_searchers:
498
common_to_all_unique_nodes.intersection_update(searcher.seen)
499
common_to_all_unique_nodes.intersection_update(
500
all_unique_searcher.seen)
501
# Step all-unique less frequently than the other searchers.
502
# In the common case, we don't need to spider out far here, so
503
# avoid doing extra work.
505
tstart = time.clock()
506
nodes = all_unique_searcher.step()
507
common_to_all_unique_nodes.update(nodes)
508
if 'graph' in debug.debug_flags:
509
tdelta = time.clock() - tstart
510
trace.mutter('all_unique_searcher step() took %.3fs'
511
'for %d nodes (%d total), iteration: %s',
512
tdelta, len(nodes), len(all_unique_searcher.seen),
513
all_unique_searcher._iterations)
514
return common_to_all_unique_nodes
516
def _collapse_unique_searchers(self, unique_tip_searchers,
517
common_to_all_unique_nodes):
518
"""Combine searchers that are searching the same tips.
520
When two searchers are searching the same tips, we can stop one of the
521
searchers. We also know that the maximal set of common ancestors is the
522
intersection of the two original searchers.
524
:return: A list of searchers that are searching unique nodes.
526
# Filter out searchers that don't actually search different
527
# nodes. We already have the ancestry intersection for them
528
unique_search_tips = {}
529
for searcher in unique_tip_searchers:
530
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
531
will_search_set = frozenset(searcher._next_query)
532
if not will_search_set:
533
if 'graph' in debug.debug_flags:
534
trace.mutter('Unique searcher %s was stopped.'
535
' (%s iterations) %d nodes stopped',
537
searcher._iterations,
539
elif will_search_set not in unique_search_tips:
540
# This searcher is searching a unique set of nodes, let it
541
unique_search_tips[will_search_set] = [searcher]
543
unique_search_tips[will_search_set].append(searcher)
544
# TODO: it might be possible to collapse searchers faster when they
545
# only have *some* search tips in common.
546
next_unique_searchers = []
547
for searchers in unique_search_tips.itervalues():
548
if len(searchers) == 1:
549
# Searching unique tips, go for it
550
next_unique_searchers.append(searchers[0])
552
# These searchers have started searching the same tips, we
553
# don't need them to cover the same ground. The
554
# intersection of their ancestry won't change, so create a
555
# new searcher, combining their histories.
556
next_searcher = searchers[0]
557
for searcher in searchers[1:]:
558
next_searcher.seen.intersection_update(searcher.seen)
559
if 'graph' in debug.debug_flags:
560
trace.mutter('Combining %d searchers into a single'
561
' searcher searching %d nodes with'
564
len(next_searcher._next_query),
565
len(next_searcher.seen))
566
next_unique_searchers.append(next_searcher)
567
return next_unique_searchers
569
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
570
unique_tip_searchers, common_searcher):
571
"""Steps 5-8 of find_unique_ancestors.
573
This function returns when common_searcher has stopped searching for
576
# We step the ancestor_all_unique searcher only every
577
# STEP_UNIQUE_SEARCHER_EVERY steps.
578
step_all_unique_counter = 0
579
# While we still have common nodes to search
580
while common_searcher._next_query:
582
newly_seen_unique) = self._step_unique_and_common_searchers(
583
common_searcher, unique_tip_searchers, unique_searcher)
584
# These nodes are common ancestors of all unique nodes
585
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
586
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
587
step_all_unique_counter==0)
588
step_all_unique_counter = ((step_all_unique_counter + 1)
589
% STEP_UNIQUE_SEARCHER_EVERY)
591
if newly_seen_common:
592
# If a 'common' node is an ancestor of all unique searchers, we
593
# can stop searching it.
594
common_searcher.stop_searching_any(
595
all_unique_searcher.seen.intersection(newly_seen_common))
596
if common_to_all_unique_nodes:
597
common_to_all_unique_nodes.update(
598
common_searcher.find_seen_ancestors(
599
common_to_all_unique_nodes))
600
# The all_unique searcher can start searching the common nodes
601
# but everyone else can stop.
602
# This is the sort of thing where we would like to not have it
603
# start_searching all of the nodes, but only mark all of them
604
# as seen, and have it search only the actual tips. Otherwise
605
# it is another get_parent_map() traversal for it to figure out
606
# what we already should know.
607
all_unique_searcher.start_searching(common_to_all_unique_nodes)
608
common_searcher.stop_searching_any(common_to_all_unique_nodes)
610
next_unique_searchers = self._collapse_unique_searchers(
611
unique_tip_searchers, common_to_all_unique_nodes)
612
if len(unique_tip_searchers) != len(next_unique_searchers):
613
if 'graph' in debug.debug_flags:
614
trace.mutter('Collapsed %d unique searchers => %d'
616
len(unique_tip_searchers),
617
len(next_unique_searchers),
618
all_unique_searcher._iterations)
619
unique_tip_searchers = next_unique_searchers
621
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
622
def get_parents(self, revisions):
623
"""Find revision ids of the parents of a list of revisions
625
A list is returned of the same length as the input. Each entry
626
is a list of parent ids for the corresponding input revision.
628
[NULL_REVISION] is used as the parent of the first user-committed
629
revision. Its parent list is empty.
631
If the revision is not present (i.e. a ghost), None is used in place
632
of the list of parents.
634
Deprecated in bzr 1.2 - please see get_parent_map.
636
parents = self.get_parent_map(revisions)
637
return [parents.get(r, None) for r in revisions]
639
def get_parent_map(self, revisions):
640
"""Get a map of key:parent_list for revisions.
642
This implementation delegates to get_parents, for old parent_providers
643
that do not supply get_parent_map.
646
for rev, parents in self.get_parents(revisions):
647
if parents is not None:
648
result[rev] = parents
651
def _make_breadth_first_searcher(self, revisions):
652
return _BreadthFirstSearcher(revisions, self)
654
def _find_border_ancestors(self, revisions):
655
"""Find common ancestors with at least one uncommon descendant.
657
Border ancestors are identified using a breadth-first
658
search starting at the bottom of the graph. Searches are stopped
659
whenever a node or one of its descendants is determined to be common.
661
This will scale with the number of uncommon ancestors.
663
As well as the border ancestors, a set of seen common ancestors and a
664
list of sets of seen ancestors for each input revision is returned.
665
This allows calculation of graph difference from the results of this
668
if None in revisions:
669
raise errors.InvalidRevisionId(None, self)
670
common_ancestors = set()
671
searchers = [self._make_breadth_first_searcher([r])
673
active_searchers = searchers[:]
674
border_ancestors = set()
678
for searcher in searchers:
679
new_ancestors = searcher.step()
681
newly_seen.update(new_ancestors)
683
for revision in newly_seen:
684
if revision in common_ancestors:
685
# Not a border ancestor because it was seen as common
687
new_common.add(revision)
689
for searcher in searchers:
690
if revision not in searcher.seen:
693
# This is a border because it is a first common that we see
694
# after walking for a while.
695
border_ancestors.add(revision)
696
new_common.add(revision)
698
for searcher in searchers:
699
new_common.update(searcher.find_seen_ancestors(new_common))
700
for searcher in searchers:
701
searcher.start_searching(new_common)
702
common_ancestors.update(new_common)
704
# Figure out what the searchers will be searching next, and if
705
# there is only 1 set being searched, then we are done searching,
706
# since all searchers would have to be searching the same data,
707
# thus it *must* be in common.
708
unique_search_sets = set()
709
for searcher in searchers:
710
will_search_set = frozenset(searcher._next_query)
711
if will_search_set not in unique_search_sets:
712
# This searcher is searching a unique set of nodes, let it
713
unique_search_sets.add(will_search_set)
715
if len(unique_search_sets) == 1:
716
nodes = unique_search_sets.pop()
717
uncommon_nodes = nodes.difference(common_ancestors)
719
raise AssertionError("Somehow we ended up converging"
720
" without actually marking them as"
723
"\nuncommon_nodes: %s"
724
% (revisions, uncommon_nodes))
726
return border_ancestors, common_ancestors, searchers
728
def heads(self, keys):
729
"""Return the heads from amongst keys.
731
This is done by searching the ancestries of each key. Any key that is
732
reachable from another key is not returned; all the others are.
734
This operation scales with the relative depth between any two keys. If
735
any two keys are completely disconnected all ancestry of both sides
738
:param keys: An iterable of keys.
739
:return: A set of the heads. Note that as a set there is no ordering
740
information. Callers will need to filter their input to create
741
order if they need it.
743
candidate_heads = set(keys)
744
if revision.NULL_REVISION in candidate_heads:
745
# NULL_REVISION is only a head if it is the only entry
746
candidate_heads.remove(revision.NULL_REVISION)
747
if not candidate_heads:
748
return set([revision.NULL_REVISION])
749
if len(candidate_heads) < 2:
750
return candidate_heads
751
searchers = dict((c, self._make_breadth_first_searcher([c]))
752
for c in candidate_heads)
753
active_searchers = dict(searchers)
754
# skip over the actual candidate for each searcher
755
for searcher in active_searchers.itervalues():
757
# The common walker finds nodes that are common to two or more of the
758
# input keys, so that we don't access all history when a currently
759
# uncommon search point actually meets up with something behind a
760
# common search point. Common search points do not keep searches
761
# active; they just allow us to make searches inactive without
762
# accessing all history.
763
common_walker = self._make_breadth_first_searcher([])
764
while len(active_searchers) > 0:
769
except StopIteration:
770
# No common points being searched at this time.
772
for candidate in active_searchers.keys():
774
searcher = active_searchers[candidate]
776
# rare case: we deleted candidate in a previous iteration
777
# through this for loop, because it was determined to be
778
# a descendant of another candidate.
781
ancestors.update(searcher.next())
782
except StopIteration:
783
del active_searchers[candidate]
785
# process found nodes
787
for ancestor in ancestors:
788
if ancestor in candidate_heads:
789
candidate_heads.remove(ancestor)
790
del searchers[ancestor]
791
if ancestor in active_searchers:
792
del active_searchers[ancestor]
793
# it may meet up with a known common node
794
if ancestor in common_walker.seen:
795
# some searcher has encountered our known common nodes:
797
ancestor_set = set([ancestor])
798
for searcher in searchers.itervalues():
799
searcher.stop_searching_any(ancestor_set)
801
# or it may have been just reached by all the searchers:
802
for searcher in searchers.itervalues():
803
if ancestor not in searcher.seen:
806
# The final active searcher has just reached this node,
807
# making it be known as a descendant of all candidates,
808
# so we can stop searching it, and any seen ancestors
809
new_common.add(ancestor)
810
for searcher in searchers.itervalues():
812
searcher.find_seen_ancestors([ancestor])
813
searcher.stop_searching_any(seen_ancestors)
814
common_walker.start_searching(new_common)
815
return candidate_heads
817
def find_merge_order(self, tip_revision_id, lca_revision_ids):
818
"""Find the order that each revision was merged into tip.
820
This basically just walks backwards with a stack, and walks left-first
821
until it finds a node to stop.
823
if len(lca_revision_ids) == 1:
824
return list(lca_revision_ids)
825
looking_for = set(lca_revision_ids)
826
# TODO: Is there a way we could do this "faster" by batching up the
827
# get_parent_map requests?
828
# TODO: Should we also be culling the ancestry search right away? We
829
# could add looking_for to the "stop" list, and walk their
830
# ancestry in batched mode. The flip side is it might mean we walk a
831
# lot of "stop" nodes, rather than only the minimum.
832
# Then again, without it we may trace back into ancestry we could have
834
stack = [tip_revision_id]
837
while stack and looking_for:
840
if next in looking_for:
842
looking_for.remove(next)
843
if len(looking_for) == 1:
844
found.append(looking_for.pop())
847
parent_ids = self.get_parent_map([next]).get(next, None)
848
if not parent_ids: # Ghost, nothing to search here
850
for parent_id in reversed(parent_ids):
851
# TODO: (performance) We see the parent at this point, but we
852
# wait to mark it until later to make sure we get left
853
# parents before right parents. However, instead of
854
# waiting until we have traversed enough parents, we
855
# could instead note that we've found it, and once all
856
# parents are in the stack, just reverse iterate the
858
if parent_id not in stop:
859
# this will need to be searched
860
stack.append(parent_id)
864
def find_unique_lca(self, left_revision, right_revision,
866
"""Find a unique LCA.
868
Find lowest common ancestors. If there is no unique common
869
ancestor, find the lowest common ancestors of those ancestors.
871
Iteration stops when a unique lowest common ancestor is found.
872
The graph origin is necessarily a unique lowest common ancestor.
874
Note that None is not an acceptable substitute for NULL_REVISION.
875
in the input for this method.
877
:param count_steps: If True, the return value will be a tuple of
878
(unique_lca, steps) where steps is the number of times that
879
find_lca was run. If False, only unique_lca is returned.
881
revisions = [left_revision, right_revision]
885
lca = self.find_lca(*revisions)
893
raise errors.NoCommonAncestor(left_revision, right_revision)
896
def iter_ancestry(self, revision_ids):
897
"""Iterate the ancestry of this revision.
899
:param revision_ids: Nodes to start the search
900
:return: Yield tuples mapping a revision_id to its parents for the
901
ancestry of revision_id.
902
Ghosts will be returned with None as their parents, and nodes
903
with no parents will have NULL_REVISION as their only parent. (As
904
defined by get_parent_map.)
905
There will also be a node for (NULL_REVISION, ())
907
pending = set(revision_ids)
910
processed.update(pending)
911
next_map = self.get_parent_map(pending)
913
for item in next_map.iteritems():
915
next_pending.update(p for p in item[1] if p not in processed)
916
ghosts = pending.difference(next_map)
919
pending = next_pending
921
def iter_topo_order(self, revisions):
922
"""Iterate through the input revisions in topological order.
924
This sorting only ensures that parents come before their children.
925
An ancestor may sort after a descendant if the relationship is not
926
visible in the supplied list of revisions.
928
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
929
return sorter.iter_topo_order()
931
def is_ancestor(self, candidate_ancestor, candidate_descendant):
932
"""Determine whether a revision is an ancestor of another.
934
We answer this using heads() as heads() has the logic to perform the
935
smallest number of parent lookups to determine the ancestral
936
relationship between N revisions.
938
return set([candidate_descendant]) == self.heads(
939
[candidate_ancestor, candidate_descendant])
941
def _search_for_extra_common(self, common, searchers):
942
"""Make sure that unique nodes are genuinely unique.
944
After _find_border_ancestors, all nodes marked "common" are indeed
945
common. Some of the nodes considered unique are not, due to history
946
shortcuts stopping the searches early.
948
We know that we have searched enough when all common search tips are
949
descended from all unique (uncommon) nodes because we know that a node
950
cannot be an ancestor of its own ancestor.
952
:param common: A set of common nodes
953
:param searchers: The searchers returned from _find_border_ancestors
957
# A) The passed in searchers should all be on the same tips, thus
958
# they should be considered the "common" searchers.
959
# B) We find the difference between the searchers, these are the
960
# "unique" nodes for each side.
961
# C) We do a quick culling so that we only start searching from the
962
# more interesting unique nodes. (A unique ancestor is more
963
# interesting than any of its children.)
964
# D) We start searching for ancestors common to all unique nodes.
965
# E) We have the common searchers stop searching any ancestors of
967
# F) When there are no more common search tips, we stop
969
# TODO: We need a way to remove unique_searchers when they overlap with
970
# other unique searchers.
971
if len(searchers) != 2:
972
raise NotImplementedError(
973
"Algorithm not yet implemented for > 2 searchers")
974
common_searchers = searchers
975
left_searcher = searchers[0]
976
right_searcher = searchers[1]
977
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
978
if not unique: # No unique nodes, nothing to do
980
total_unique = len(unique)
981
unique = self._remove_simple_descendants(unique,
982
self.get_parent_map(unique))
983
simple_unique = len(unique)
985
unique_searchers = []
986
for revision_id in unique:
987
if revision_id in left_searcher.seen:
988
parent_searcher = left_searcher
990
parent_searcher = right_searcher
991
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
992
if not revs_to_search: # XXX: This shouldn't be possible
993
revs_to_search = [revision_id]
994
searcher = self._make_breadth_first_searcher(revs_to_search)
995
# We don't care about the starting nodes.
997
unique_searchers.append(searcher)
999
# possible todo: aggregate the common searchers into a single common
1000
# searcher, just make sure that we include the nodes into the .seen
1001
# properties of the original searchers
1003
ancestor_all_unique = None
1004
for searcher in unique_searchers:
1005
if ancestor_all_unique is None:
1006
ancestor_all_unique = set(searcher.seen)
1008
ancestor_all_unique = ancestor_all_unique.intersection(
1011
trace.mutter('Started %s unique searchers for %s unique revisions',
1012
simple_unique, total_unique)
1014
while True: # If we have no more nodes we have nothing to do
1015
newly_seen_common = set()
1016
for searcher in common_searchers:
1017
newly_seen_common.update(searcher.step())
1018
newly_seen_unique = set()
1019
for searcher in unique_searchers:
1020
newly_seen_unique.update(searcher.step())
1021
new_common_unique = set()
1022
for revision in newly_seen_unique:
1023
for searcher in unique_searchers:
1024
if revision not in searcher.seen:
1027
# This is a border because it is a first common that we see
1028
# after walking for a while.
1029
new_common_unique.add(revision)
1030
if newly_seen_common:
1031
# These are nodes descended from one of the 'common' searchers.
1032
# Make sure all searchers are on the same page
1033
for searcher in common_searchers:
1034
newly_seen_common.update(
1035
searcher.find_seen_ancestors(newly_seen_common))
1036
# We start searching the whole ancestry. It is a bit wasteful,
1037
# though. We really just want to mark all of these nodes as
1038
# 'seen' and then start just the tips. However, it requires a
1039
# get_parent_map() call to figure out the tips anyway, and all
1040
# redundant requests should be fairly fast.
1041
for searcher in common_searchers:
1042
searcher.start_searching(newly_seen_common)
1044
# If a 'common' node is an ancestor of all unique searchers, we
1045
# can stop searching it.
1046
stop_searching_common = ancestor_all_unique.intersection(
1048
if stop_searching_common:
1049
for searcher in common_searchers:
1050
searcher.stop_searching_any(stop_searching_common)
1051
if new_common_unique:
1052
# We found some ancestors that are common
1053
for searcher in unique_searchers:
1054
new_common_unique.update(
1055
searcher.find_seen_ancestors(new_common_unique))
1056
# Since these are common, we can grab another set of ancestors
1058
for searcher in common_searchers:
1059
new_common_unique.update(
1060
searcher.find_seen_ancestors(new_common_unique))
1062
# We can tell all of the unique searchers to start at these
1063
# nodes, and tell all of the common searchers to *stop*
1064
# searching these nodes
1065
for searcher in unique_searchers:
1066
searcher.start_searching(new_common_unique)
1067
for searcher in common_searchers:
1068
searcher.stop_searching_any(new_common_unique)
1069
ancestor_all_unique.update(new_common_unique)
1071
# Filter out searchers that don't actually search different
1072
# nodes. We already have the ancestry intersection for them
1073
next_unique_searchers = []
1074
unique_search_sets = set()
1075
for searcher in unique_searchers:
1076
will_search_set = frozenset(searcher._next_query)
1077
if will_search_set not in unique_search_sets:
1078
# This searcher is searching a unique set of nodes, let it
1079
unique_search_sets.add(will_search_set)
1080
next_unique_searchers.append(searcher)
1081
unique_searchers = next_unique_searchers
1082
for searcher in common_searchers:
1083
if searcher._next_query:
1086
# All common searcher have stopped searching
1089
def _remove_simple_descendants(self, revisions, parent_map):
1090
"""remove revisions which are children of other ones in the set
1092
This doesn't do any graph searching, it just checks the immediate
1093
parent_map to find if there are any children which can be removed.
1095
:param revisions: A set of revision_ids
1096
:return: A set of revision_ids with the children removed
1098
simple_ancestors = revisions.copy()
1099
# TODO: jam 20071214 we *could* restrict it to searching only the
1100
# parent_map of revisions already present in 'revisions', but
1101
# considering the general use case, I think this is actually
1104
# This is the same as the following loop. I don't know that it is any
1106
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1107
## if p_ids is not None and revisions.intersection(p_ids))
1108
## return simple_ancestors
1110
# Yet Another Way, invert the parent map (which can be cached)
1112
## for revision_id, parent_ids in parent_map.iteritems():
1113
## for p_id in parent_ids:
1114
## descendants.setdefault(p_id, []).append(revision_id)
1115
## for revision in revisions.intersection(descendants):
1116
## simple_ancestors.difference_update(descendants[revision])
1117
## return simple_ancestors
1118
for revision, parent_ids in parent_map.iteritems():
1119
if parent_ids is None:
1121
for parent_id in parent_ids:
1122
if parent_id in revisions:
1123
# This node has a parent present in the set, so we can
1125
simple_ancestors.discard(revision)
1127
return simple_ancestors
1130
class HeadsCache(object):
1131
"""A cache of results for graph heads calls."""
1133
def __init__(self, graph):
1137
def heads(self, keys):
1138
"""Return the heads of keys.
1140
This matches the API of Graph.heads(), specifically the return value is
1141
a set which can be mutated, and ordering of the input is not preserved
1144
:see also: Graph.heads.
1145
:param keys: The keys to calculate heads for.
1146
:return: A set containing the heads, which may be mutated without
1147
affecting future lookups.
1149
keys = frozenset(keys)
1151
return set(self._heads[keys])
1153
heads = self.graph.heads(keys)
1154
self._heads[keys] = heads
1158
class FrozenHeadsCache(object):
1159
"""Cache heads() calls, assuming the caller won't modify them."""
1161
def __init__(self, graph):
1165
def heads(self, keys):
1166
"""Return the heads of keys.
1168
Similar to Graph.heads(). The main difference is that the return value
1169
is a frozen set which cannot be mutated.
1171
:see also: Graph.heads.
1172
:param keys: The keys to calculate heads for.
1173
:return: A frozenset containing the heads.
1175
keys = frozenset(keys)
1177
return self._heads[keys]
1179
heads = frozenset(self.graph.heads(keys))
1180
self._heads[keys] = heads
1183
def cache(self, keys, heads):
1184
"""Store a known value."""
1185
self._heads[frozenset(keys)] = frozenset(heads)
1188
class _BreadthFirstSearcher(object):
1189
"""Parallel search breadth-first the ancestry of revisions.
1191
This class implements the iterator protocol, but additionally
1192
1. provides a set of seen ancestors, and
1193
2. allows some ancestries to be unsearched, via stop_searching_any
1196
def __init__(self, revisions, parents_provider):
1197
self._iterations = 0
1198
self._next_query = set(revisions)
1200
self._started_keys = set(self._next_query)
1201
self._stopped_keys = set()
1202
self._parents_provider = parents_provider
1203
self._returning = 'next_with_ghosts'
1204
self._current_present = set()
1205
self._current_ghosts = set()
1206
self._current_parents = {}
1209
if self._iterations:
1210
prefix = "searching"
1213
search = '%s=%r' % (prefix, list(self._next_query))
1214
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1215
' seen=%r)' % (self._iterations, search, list(self.seen)))
1217
def get_result(self):
1218
"""Get a SearchResult for the current state of this searcher.
1220
:return: A SearchResult for this search so far. The SearchResult is
1221
static - the search can be advanced and the search result will not
1222
be invalidated or altered.
1224
if self._returning == 'next':
1225
# We have to know the current nodes children to be able to list the
1226
# exclude keys for them. However, while we could have a second
1227
# look-ahead result buffer and shuffle things around, this method
1228
# is typically only called once per search - when memoising the
1229
# results of the search.
1230
found, ghosts, next, parents = self._do_query(self._next_query)
1231
# pretend we didn't query: perhaps we should tweak _do_query to be
1232
# entirely stateless?
1233
self.seen.difference_update(next)
1234
next_query = next.union(ghosts)
1236
next_query = self._next_query
1237
excludes = self._stopped_keys.union(next_query)
1238
included_keys = self.seen.difference(excludes)
1239
return SearchResult(self._started_keys, excludes, len(included_keys),
1245
except StopIteration:
1249
"""Return the next ancestors of this revision.
1251
Ancestors are returned in the order they are seen in a breadth-first
1252
traversal. No ancestor will be returned more than once. Ancestors are
1253
returned before their parentage is queried, so ghosts and missing
1254
revisions (including the start revisions) are included in the result.
1255
This can save a round trip in LCA style calculation by allowing
1256
convergence to be detected without reading the data for the revision
1257
the convergence occurs on.
1259
:return: A set of revision_ids.
1261
if self._returning != 'next':
1262
# switch to returning the query, not the results.
1263
self._returning = 'next'
1264
self._iterations += 1
1267
if len(self._next_query) == 0:
1268
raise StopIteration()
1269
# We have seen what we're querying at this point as we are returning
1270
# the query, not the results.
1271
self.seen.update(self._next_query)
1272
return self._next_query
1274
def next_with_ghosts(self):
1275
"""Return the next found ancestors, with ghosts split out.
1277
Ancestors are returned in the order they are seen in a breadth-first
1278
traversal. No ancestor will be returned more than once. Ancestors are
1279
returned only after asking for their parents, which allows us to detect
1280
which revisions are ghosts and which are not.
1282
:return: A tuple with (present ancestors, ghost ancestors) sets.
1284
if self._returning != 'next_with_ghosts':
1285
# switch to returning the results, not the current query.
1286
self._returning = 'next_with_ghosts'
1288
if len(self._next_query) == 0:
1289
raise StopIteration()
1291
return self._current_present, self._current_ghosts
1294
"""Advance the search.
1296
Updates self.seen, self._next_query, self._current_present,
1297
self._current_ghosts, self._current_parents and self._iterations.
1299
self._iterations += 1
1300
found, ghosts, next, parents = self._do_query(self._next_query)
1301
self._current_present = found
1302
self._current_ghosts = ghosts
1303
self._next_query = next
1304
self._current_parents = parents
1305
# ghosts are implicit stop points, otherwise the search cannot be
1306
# repeated when ghosts are filled.
1307
self._stopped_keys.update(ghosts)
1309
def _do_query(self, revisions):
1310
"""Query for revisions.
1312
Adds revisions to the seen set.
1314
:param revisions: Revisions to query.
1315
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1316
set(parents_of_found_revisions), dict(found_revisions:parents)).
1318
found_revisions = set()
1319
parents_of_found = set()
1320
# revisions may contain nodes that point to other nodes in revisions:
1321
# we want to filter them out.
1322
self.seen.update(revisions)
1323
parent_map = self._parents_provider.get_parent_map(revisions)
1324
found_revisions.update(parent_map)
1325
for rev_id, parents in parent_map.iteritems():
1328
new_found_parents = [p for p in parents if p not in self.seen]
1329
if new_found_parents:
1330
# Calling set.update() with an empty generator is actually
1332
parents_of_found.update(new_found_parents)
1333
ghost_revisions = revisions - found_revisions
1334
return found_revisions, ghost_revisions, parents_of_found, parent_map
1339
def find_seen_ancestors(self, revisions):
1340
"""Find ancestors of these revisions that have already been seen.
1342
This function generally makes the assumption that querying for the
1343
parents of a node that has already been queried is reasonably cheap.
1344
(eg, not a round trip to a remote host).
1346
# TODO: Often we might ask one searcher for its seen ancestors, and
1347
# then ask another searcher the same question. This can result in
1348
# searching the same revisions repeatedly if the two searchers
1349
# have a lot of overlap.
1350
all_seen = self.seen
1351
pending = set(revisions).intersection(all_seen)
1352
seen_ancestors = set(pending)
1354
if self._returning == 'next':
1355
# self.seen contains what nodes have been returned, not what nodes
1356
# have been queried. We don't want to probe for nodes that haven't
1357
# been searched yet.
1358
not_searched_yet = self._next_query
1360
not_searched_yet = ()
1361
pending.difference_update(not_searched_yet)
1362
get_parent_map = self._parents_provider.get_parent_map
1364
parent_map = get_parent_map(pending)
1366
# We don't care if it is a ghost, since it can't be seen if it is
1368
for parent_ids in parent_map.itervalues():
1369
all_parents.extend(parent_ids)
1370
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1371
seen_ancestors.update(next_pending)
1372
next_pending.difference_update(not_searched_yet)
1373
pending = next_pending
1375
return seen_ancestors
1377
def stop_searching_any(self, revisions):
1379
Remove any of the specified revisions from the search list.
1381
None of the specified revisions are required to be present in the
1384
It is okay to call stop_searching_any() for revisions which were seen
1385
in previous iterations. It is the callers responsibility to call
1386
find_seen_ancestors() to make sure that current search tips that are
1387
ancestors of those revisions are also stopped. All explicitly stopped
1388
revisions will be excluded from the search result's get_keys(), though.
1390
# TODO: does this help performance?
1393
revisions = frozenset(revisions)
1394
if self._returning == 'next':
1395
stopped = self._next_query.intersection(revisions)
1396
self._next_query = self._next_query.difference(revisions)
1398
stopped_present = self._current_present.intersection(revisions)
1399
stopped = stopped_present.union(
1400
self._current_ghosts.intersection(revisions))
1401
self._current_present.difference_update(stopped)
1402
self._current_ghosts.difference_update(stopped)
1403
# stopping 'x' should stop returning parents of 'x', but
1404
# not if 'y' always references those same parents
1405
stop_rev_references = {}
1406
for rev in stopped_present:
1407
for parent_id in self._current_parents[rev]:
1408
if parent_id not in stop_rev_references:
1409
stop_rev_references[parent_id] = 0
1410
stop_rev_references[parent_id] += 1
1411
# if only the stopped revisions reference it, the ref count will be
1413
for parents in self._current_parents.itervalues():
1414
for parent_id in parents:
1416
stop_rev_references[parent_id] -= 1
1419
stop_parents = set()
1420
for rev_id, refs in stop_rev_references.iteritems():
1422
stop_parents.add(rev_id)
1423
self._next_query.difference_update(stop_parents)
1424
self._stopped_keys.update(stopped)
1425
self._stopped_keys.update(revisions - set([revision.NULL_REVISION]))
1428
def start_searching(self, revisions):
1429
"""Add revisions to the search.
1431
The parents of revisions will be returned from the next call to next()
1432
or next_with_ghosts(). If next_with_ghosts was the most recently used
1433
next* call then the return value is the result of looking up the
1434
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1436
revisions = frozenset(revisions)
1437
self._started_keys.update(revisions)
1438
new_revisions = revisions.difference(self.seen)
1439
if self._returning == 'next':
1440
self._next_query.update(new_revisions)
1441
self.seen.update(new_revisions)
1443
# perform a query on revisions
1444
revs, ghosts, query, parents = self._do_query(revisions)
1445
self._stopped_keys.update(ghosts)
1446
self._current_present.update(revs)
1447
self._current_ghosts.update(ghosts)
1448
self._next_query.update(query)
1449
self._current_parents.update(parents)
1453
class SearchResult(object):
1454
"""The result of a breadth first search.
1456
A SearchResult provides the ability to reconstruct the search or access a
1457
set of the keys the search found.
1460
def __init__(self, start_keys, exclude_keys, key_count, keys):
1461
"""Create a SearchResult.
1463
:param start_keys: The keys the search started at.
1464
:param exclude_keys: The keys the search excludes.
1465
:param key_count: The total number of keys (from start to but not
1467
:param keys: The keys the search found. Note that in future we may get
1468
a SearchResult from a smart server, in which case the keys list is
1469
not necessarily immediately available.
1471
self._recipe = (start_keys, exclude_keys, key_count)
1472
self._keys = frozenset(keys)
1474
def get_recipe(self):
1475
"""Return a recipe that can be used to replay this search.
1477
The recipe allows reconstruction of the same results at a later date
1478
without knowing all the found keys. The essential elements are a list
1479
of keys to start and and to stop at. In order to give reproducible
1480
results when ghosts are encountered by a search they are automatically
1481
added to the exclude list (or else ghost filling may alter the
1484
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1485
recreate the results of this search, create a breadth first
1486
searcher on the same graph starting at start_keys. Then call next()
1487
(or next_with_ghosts()) repeatedly, and on every result, call
1488
stop_searching_any on any keys from the exclude_keys set. The
1489
revision_count value acts as a trivial cross-check - the found
1490
revisions of the new search should have as many elements as
1491
revision_count. If it does not, then additional revisions have been
1492
ghosted since the search was executed the first time and the second
1498
"""Return the keys found in this search.
1500
:return: A set of keys.
1505
def collapse_linear_regions(parent_map):
1506
"""Collapse regions of the graph that are 'linear'.
1512
can be collapsed by removing B and getting::
1516
:param parent_map: A dictionary mapping children to their parents
1517
:return: Another dictionary with 'linear' chains collapsed
1519
# Note: this isn't a strictly minimal collapse. For example:
1527
# Will not have 'D' removed, even though 'E' could fit. Also:
1533
# A and C are both kept because they are edges of the graph. We *could* get
1534
# rid of A if we wanted.
1542
# Will not have any nodes removed, even though you do have an
1543
# 'uninteresting' linear D->B and E->C
1545
for child, parents in parent_map.iteritems():
1546
children.setdefault(child, [])
1548
children.setdefault(p, []).append(child)
1550
orig_children = dict(children)
1552
result = dict(parent_map)
1553
for node in parent_map:
1554
parents = result[node]
1555
if len(parents) == 1:
1556
parent_children = children[parents[0]]
1557
if len(parent_children) != 1:
1558
# This is not the only child
1560
node_children = children[node]
1561
if len(node_children) != 1:
1563
child_parents = result.get(node_children[0], None)
1564
if len(child_parents) != 1:
1565
# This is not its only parent
1567
# The child of this node only points at it, and the parent only has
1568
# this as a child. remove this node, and join the others together
1569
result[node_children[0]] = parents
1570
children[parents[0]] = node_children
added
removed
bzrlib/graph.py
