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):
138
self._cache_misses = cache_misses
140
self._requested_parents = set()
142
def disable_cache(self):
143
"""Disable and clear the cache."""
146
self._requested_parents = None
148
def get_cached_map(self):
149
"""Return any cached get_parent_map values."""
150
if self._cache is None:
152
return dict((k, v) for k, v in self._cache.items()
155
def get_parent_map(self, keys):
156
"""See _StackedParentsProvider.get_parent_map."""
157
# Hack to build up the caching logic.
158
ancestry = self._cache
160
# Caching is disabled.
161
missing_revisions = set(keys)
164
missing_revisions = set(key for key in keys if key not in ancestry)
165
if missing_revisions:
166
parent_map = self._get_parent_map(missing_revisions)
168
mutter('re-retrieved revisions: %d of %d',
169
len(set(ancestry).intersection(parent_map)),
171
ancestry.update(parent_map)
172
if self._cache_misses:
173
# None is never a valid parents list, so it can be used to
175
ancestry.update(dict((k, None) for k in missing_revisions
176
if k not in parent_map))
177
present_keys = [k for k in keys if ancestry.get(k) is not None]
179
if self._requested_parents is not None and len(ancestry) != 0:
180
self._requested_parents.update(present_keys)
181
mutter('Current hit rate: %d%%',
182
100.0 * len(self._requested_parents) / len(ancestry))
183
return dict((k, ancestry[k]) for k in present_keys)
187
"""Provide incremental access to revision graphs.
189
This is the generic implementation; it is intended to be subclassed to
190
specialize it for other repository types.
193
def __init__(self, parents_provider):
194
"""Construct a Graph that uses several graphs as its input
196
This should not normally be invoked directly, because there may be
197
specialized implementations for particular repository types. See
198
Repository.get_graph().
200
:param parents_provider: An object providing a get_parent_map call
201
conforming to the behavior of
202
StackedParentsProvider.get_parent_map.
204
if getattr(parents_provider, 'get_parents', None) is not None:
205
self.get_parents = parents_provider.get_parents
206
if getattr(parents_provider, 'get_parent_map', None) is not None:
207
self.get_parent_map = parents_provider.get_parent_map
208
self._parents_provider = parents_provider
211
return 'Graph(%r)' % self._parents_provider
213
def find_lca(self, *revisions):
214
"""Determine the lowest common ancestors of the provided revisions
216
A lowest common ancestor is a common ancestor none of whose
217
descendants are common ancestors. In graphs, unlike trees, there may
218
be multiple lowest common ancestors.
220
This algorithm has two phases. Phase 1 identifies border ancestors,
221
and phase 2 filters border ancestors to determine lowest common
224
In phase 1, border ancestors are identified, using a breadth-first
225
search starting at the bottom of the graph. Searches are stopped
226
whenever a node or one of its descendants is determined to be common
228
In phase 2, the border ancestors are filtered to find the least
229
common ancestors. This is done by searching the ancestries of each
232
Phase 2 is perfomed on the principle that a border ancestor that is
233
not an ancestor of any other border ancestor is a least common
236
Searches are stopped when they find a node that is determined to be a
237
common ancestor of all border ancestors, because this shows that it
238
cannot be a descendant of any border ancestor.
240
The scaling of this operation should be proportional to
241
1. The number of uncommon ancestors
242
2. The number of border ancestors
243
3. The length of the shortest path between a border ancestor and an
244
ancestor of all border ancestors.
246
border_common, common, sides = self._find_border_ancestors(revisions)
247
# We may have common ancestors that can be reached from each other.
248
# - ask for the heads of them to filter it down to only ones that
249
# cannot be reached from each other - phase 2.
250
return self.heads(border_common)
252
def find_difference(self, left_revision, right_revision):
253
"""Determine the graph difference between two revisions"""
254
border, common, searchers = self._find_border_ancestors(
255
[left_revision, right_revision])
256
self._search_for_extra_common(common, searchers)
257
left = searchers[0].seen
258
right = searchers[1].seen
259
return (left.difference(right), right.difference(left))
261
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
"""Find the left-hand distance to the NULL_REVISION.
264
(This can also be considered the revno of a branch at
267
:param target_revision_id: A revision_id which we would like to know
269
:param known_revision_ids: [(revision_id, revno)] A list of known
270
revno, revision_id tuples. We'll use this to seed the search.
272
# Map from revision_ids to a known value for their revno
273
known_revnos = dict(known_revision_ids)
274
cur_tip = target_revision_id
276
NULL_REVISION = revision.NULL_REVISION
277
known_revnos[NULL_REVISION] = 0
279
searching_known_tips = list(known_revnos.keys())
281
unknown_searched = {}
283
while cur_tip not in known_revnos:
284
unknown_searched[cur_tip] = num_steps
286
to_search = set([cur_tip])
287
to_search.update(searching_known_tips)
288
parent_map = self.get_parent_map(to_search)
289
parents = parent_map.get(cur_tip, None)
290
if not parents: # An empty list or None is a ghost
291
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
295
for revision_id in searching_known_tips:
296
parents = parent_map.get(revision_id, None)
300
next_revno = known_revnos[revision_id] - 1
301
if next in unknown_searched:
302
# We have enough information to return a value right now
303
return next_revno + unknown_searched[next]
304
if next in known_revnos:
306
known_revnos[next] = next_revno
307
next_known_tips.append(next)
308
searching_known_tips = next_known_tips
310
# We reached a known revision, so just add in how many steps it took to
312
return known_revnos[cur_tip] + num_steps
314
def find_unique_ancestors(self, unique_revision, common_revisions):
315
"""Find the unique ancestors for a revision versus others.
317
This returns the ancestry of unique_revision, excluding all revisions
318
in the ancestry of common_revisions. If unique_revision is in the
319
ancestry, then the empty set will be returned.
321
:param unique_revision: The revision_id whose ancestry we are
323
XXX: Would this API be better if we allowed multiple revisions on
325
:param common_revisions: Revision_ids of ancestries to exclude.
326
:return: A set of revisions in the ancestry of unique_revision
328
if unique_revision in common_revisions:
331
# Algorithm description
332
# 1) Walk backwards from the unique node and all common nodes.
333
# 2) When a node is seen by both sides, stop searching it in the unique
334
# walker, include it in the common walker.
335
# 3) Stop searching when there are no nodes left for the unique walker.
336
# At this point, you have a maximal set of unique nodes. Some of
337
# them may actually be common, and you haven't reached them yet.
338
# 4) Start new searchers for the unique nodes, seeded with the
339
# information you have so far.
340
# 5) Continue searching, stopping the common searches when the search
341
# tip is an ancestor of all unique nodes.
342
# 6) Aggregate together unique searchers when they are searching the
343
# same tips. When all unique searchers are searching the same node,
344
# stop move it to a single 'all_unique_searcher'.
345
# 7) The 'all_unique_searcher' represents the very 'tip' of searching.
346
# Most of the time this produces very little important information.
347
# So don't step it as quickly as the other searchers.
348
# 8) Search is done when all common searchers have completed.
350
unique_searcher, common_searcher = self._find_initial_unique_nodes(
351
[unique_revision], common_revisions)
353
unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
357
(all_unique_searcher,
358
unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
359
unique_searcher, common_searcher)
361
self._refine_unique_nodes(unique_searcher, all_unique_searcher,
362
unique_tip_searchers, common_searcher)
363
true_unique_nodes = unique_nodes.difference(common_searcher.seen)
364
if 'graph' in debug.debug_flags:
365
trace.mutter('Found %d truly unique nodes out of %d',
366
len(true_unique_nodes), len(unique_nodes))
367
return true_unique_nodes
369
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
370
"""Steps 1-3 of find_unique_ancestors.
372
Find the maximal set of unique nodes. Some of these might actually
373
still be common, but we are sure that there are no other unique nodes.
375
:return: (unique_searcher, common_searcher)
378
unique_searcher = self._make_breadth_first_searcher(unique_revisions)
379
# we know that unique_revisions aren't in common_revisions, so skip
381
unique_searcher.next()
382
common_searcher = self._make_breadth_first_searcher(common_revisions)
384
# As long as we are still finding unique nodes, keep searching
385
while unique_searcher._next_query:
386
next_unique_nodes = set(unique_searcher.step())
387
next_common_nodes = set(common_searcher.step())
389
# Check if either searcher encounters new nodes seen by the other
391
unique_are_common_nodes = next_unique_nodes.intersection(
392
common_searcher.seen)
393
unique_are_common_nodes.update(
394
next_common_nodes.intersection(unique_searcher.seen))
395
if unique_are_common_nodes:
396
ancestors = unique_searcher.find_seen_ancestors(
397
unique_are_common_nodes)
398
# TODO: This is a bit overboard, we only really care about
399
# the ancestors of the tips because the rest we
400
# already know. This is *correct* but causes us to
401
# search too much ancestry.
402
ancestors.update(common_searcher.find_seen_ancestors(ancestors))
403
unique_searcher.stop_searching_any(ancestors)
404
common_searcher.start_searching(ancestors)
406
return unique_searcher, common_searcher
408
def _make_unique_searchers(self, unique_nodes, unique_searcher,
410
"""Create a searcher for all the unique search tips (step 4).
412
As a side effect, the common_searcher will stop searching any nodes
413
that are ancestors of the unique searcher tips.
415
:return: (all_unique_searcher, unique_tip_searchers)
417
unique_tips = self._remove_simple_descendants(unique_nodes,
418
self.get_parent_map(unique_nodes))
420
if len(unique_tips) == 1:
421
unique_tip_searchers = []
422
ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
424
unique_tip_searchers = []
425
for tip in unique_tips:
426
revs_to_search = unique_searcher.find_seen_ancestors([tip])
427
revs_to_search.update(
428
common_searcher.find_seen_ancestors(revs_to_search))
429
searcher = self._make_breadth_first_searcher(revs_to_search)
430
# We don't care about the starting nodes.
431
searcher._label = tip
433
unique_tip_searchers.append(searcher)
435
ancestor_all_unique = None
436
for searcher in unique_tip_searchers:
437
if ancestor_all_unique is None:
438
ancestor_all_unique = set(searcher.seen)
440
ancestor_all_unique = ancestor_all_unique.intersection(
442
# Collapse all the common nodes into a single searcher
443
all_unique_searcher = self._make_breadth_first_searcher(
445
if ancestor_all_unique:
446
# We've seen these nodes in all the searchers, so we'll just go to
448
all_unique_searcher.step()
450
# Stop any search tips that are already known as ancestors of the
452
stopped_common = common_searcher.stop_searching_any(
453
common_searcher.find_seen_ancestors(ancestor_all_unique))
456
for searcher in unique_tip_searchers:
457
total_stopped += len(searcher.stop_searching_any(
458
searcher.find_seen_ancestors(ancestor_all_unique)))
459
if 'graph' in debug.debug_flags:
460
trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
461
' (%d stopped search tips, %d common ancestors'
462
' (%d stopped common)',
463
len(unique_nodes), len(unique_tip_searchers),
464
total_stopped, len(ancestor_all_unique),
466
return all_unique_searcher, unique_tip_searchers
468
def _step_unique_and_common_searchers(self, common_searcher,
469
unique_tip_searchers,
471
"""Step all the searchers"""
472
newly_seen_common = set(common_searcher.step())
473
newly_seen_unique = set()
474
for searcher in unique_tip_searchers:
475
next = set(searcher.step())
476
next.update(unique_searcher.find_seen_ancestors(next))
477
next.update(common_searcher.find_seen_ancestors(next))
478
for alt_searcher in unique_tip_searchers:
479
if alt_searcher is searcher:
481
next.update(alt_searcher.find_seen_ancestors(next))
482
searcher.start_searching(next)
483
newly_seen_unique.update(next)
484
return newly_seen_common, newly_seen_unique
486
def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
488
newly_seen_unique, step_all_unique):
489
"""Find nodes that are common to all unique_tip_searchers.
491
If it is time, step the all_unique_searcher, and add its nodes to the
494
common_to_all_unique_nodes = newly_seen_unique.copy()
495
for searcher in unique_tip_searchers:
496
common_to_all_unique_nodes.intersection_update(searcher.seen)
497
common_to_all_unique_nodes.intersection_update(
498
all_unique_searcher.seen)
499
# Step all-unique less frequently than the other searchers.
500
# In the common case, we don't need to spider out far here, so
501
# avoid doing extra work.
503
tstart = time.clock()
504
nodes = all_unique_searcher.step()
505
common_to_all_unique_nodes.update(nodes)
506
if 'graph' in debug.debug_flags:
507
tdelta = time.clock() - tstart
508
trace.mutter('all_unique_searcher step() took %.3fs'
509
'for %d nodes (%d total), iteration: %s',
510
tdelta, len(nodes), len(all_unique_searcher.seen),
511
all_unique_searcher._iterations)
512
return common_to_all_unique_nodes
514
def _collapse_unique_searchers(self, unique_tip_searchers,
515
common_to_all_unique_nodes):
516
"""Combine searchers that are searching the same tips.
518
When two searchers are searching the same tips, we can stop one of the
519
searchers. We also know that the maximal set of common ancestors is the
520
intersection of the two original searchers.
522
:return: A list of searchers that are searching unique nodes.
524
# Filter out searchers that don't actually search different
525
# nodes. We already have the ancestry intersection for them
526
unique_search_tips = {}
527
for searcher in unique_tip_searchers:
528
stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
529
will_search_set = frozenset(searcher._next_query)
530
if not will_search_set:
531
if 'graph' in debug.debug_flags:
532
trace.mutter('Unique searcher %s was stopped.'
533
' (%s iterations) %d nodes stopped',
535
searcher._iterations,
537
elif will_search_set not in unique_search_tips:
538
# This searcher is searching a unique set of nodes, let it
539
unique_search_tips[will_search_set] = [searcher]
541
unique_search_tips[will_search_set].append(searcher)
542
# TODO: it might be possible to collapse searchers faster when they
543
# only have *some* search tips in common.
544
next_unique_searchers = []
545
for searchers in unique_search_tips.itervalues():
546
if len(searchers) == 1:
547
# Searching unique tips, go for it
548
next_unique_searchers.append(searchers[0])
550
# These searchers have started searching the same tips, we
551
# don't need them to cover the same ground. The
552
# intersection of their ancestry won't change, so create a
553
# new searcher, combining their histories.
554
next_searcher = searchers[0]
555
for searcher in searchers[1:]:
556
next_searcher.seen.intersection_update(searcher.seen)
557
if 'graph' in debug.debug_flags:
558
trace.mutter('Combining %d searchers into a single'
559
' searcher searching %d nodes with'
562
len(next_searcher._next_query),
563
len(next_searcher.seen))
564
next_unique_searchers.append(next_searcher)
565
return next_unique_searchers
567
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
568
unique_tip_searchers, common_searcher):
569
"""Steps 5-8 of find_unique_ancestors.
571
This function returns when common_searcher has stopped searching for
574
# We step the ancestor_all_unique searcher only every
575
# STEP_UNIQUE_SEARCHER_EVERY steps.
576
step_all_unique_counter = 0
577
# While we still have common nodes to search
578
while common_searcher._next_query:
580
newly_seen_unique) = self._step_unique_and_common_searchers(
581
common_searcher, unique_tip_searchers, unique_searcher)
582
# These nodes are common ancestors of all unique nodes
583
common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
584
unique_tip_searchers, all_unique_searcher, newly_seen_unique,
585
step_all_unique_counter==0)
586
step_all_unique_counter = ((step_all_unique_counter + 1)
587
% STEP_UNIQUE_SEARCHER_EVERY)
589
if newly_seen_common:
590
# If a 'common' node is an ancestor of all unique searchers, we
591
# can stop searching it.
592
common_searcher.stop_searching_any(
593
all_unique_searcher.seen.intersection(newly_seen_common))
594
if common_to_all_unique_nodes:
595
common_to_all_unique_nodes.update(
596
common_searcher.find_seen_ancestors(
597
common_to_all_unique_nodes))
598
# The all_unique searcher can start searching the common nodes
599
# but everyone else can stop.
600
# This is the sort of thing where we would like to not have it
601
# start_searching all of the nodes, but only mark all of them
602
# as seen, and have it search only the actual tips. Otherwise
603
# it is another get_parent_map() traversal for it to figure out
604
# what we already should know.
605
all_unique_searcher.start_searching(common_to_all_unique_nodes)
606
common_searcher.stop_searching_any(common_to_all_unique_nodes)
608
next_unique_searchers = self._collapse_unique_searchers(
609
unique_tip_searchers, common_to_all_unique_nodes)
610
if len(unique_tip_searchers) != len(next_unique_searchers):
611
if 'graph' in debug.debug_flags:
612
trace.mutter('Collapsed %d unique searchers => %d'
614
len(unique_tip_searchers),
615
len(next_unique_searchers),
616
all_unique_searcher._iterations)
617
unique_tip_searchers = next_unique_searchers
619
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
620
def get_parents(self, revisions):
621
"""Find revision ids of the parents of a list of revisions
623
A list is returned of the same length as the input. Each entry
624
is a list of parent ids for the corresponding input revision.
626
[NULL_REVISION] is used as the parent of the first user-committed
627
revision. Its parent list is empty.
629
If the revision is not present (i.e. a ghost), None is used in place
630
of the list of parents.
632
Deprecated in bzr 1.2 - please see get_parent_map.
634
parents = self.get_parent_map(revisions)
635
return [parents.get(r, None) for r in revisions]
637
def get_parent_map(self, revisions):
638
"""Get a map of key:parent_list for revisions.
640
This implementation delegates to get_parents, for old parent_providers
641
that do not supply get_parent_map.
644
for rev, parents in self.get_parents(revisions):
645
if parents is not None:
646
result[rev] = parents
649
def _make_breadth_first_searcher(self, revisions):
650
return _BreadthFirstSearcher(revisions, self)
652
def _find_border_ancestors(self, revisions):
653
"""Find common ancestors with at least one uncommon descendant.
655
Border ancestors are identified using a breadth-first
656
search starting at the bottom of the graph. Searches are stopped
657
whenever a node or one of its descendants is determined to be common.
659
This will scale with the number of uncommon ancestors.
661
As well as the border ancestors, a set of seen common ancestors and a
662
list of sets of seen ancestors for each input revision is returned.
663
This allows calculation of graph difference from the results of this
666
if None in revisions:
667
raise errors.InvalidRevisionId(None, self)
668
common_ancestors = set()
669
searchers = [self._make_breadth_first_searcher([r])
671
active_searchers = searchers[:]
672
border_ancestors = set()
676
for searcher in searchers:
677
new_ancestors = searcher.step()
679
newly_seen.update(new_ancestors)
681
for revision in newly_seen:
682
if revision in common_ancestors:
683
# Not a border ancestor because it was seen as common
685
new_common.add(revision)
687
for searcher in searchers:
688
if revision not in searcher.seen:
691
# This is a border because it is a first common that we see
692
# after walking for a while.
693
border_ancestors.add(revision)
694
new_common.add(revision)
696
for searcher in searchers:
697
new_common.update(searcher.find_seen_ancestors(new_common))
698
for searcher in searchers:
699
searcher.start_searching(new_common)
700
common_ancestors.update(new_common)
702
# Figure out what the searchers will be searching next, and if
703
# there is only 1 set being searched, then we are done searching,
704
# since all searchers would have to be searching the same data,
705
# thus it *must* be in common.
706
unique_search_sets = set()
707
for searcher in searchers:
708
will_search_set = frozenset(searcher._next_query)
709
if will_search_set not in unique_search_sets:
710
# This searcher is searching a unique set of nodes, let it
711
unique_search_sets.add(will_search_set)
713
if len(unique_search_sets) == 1:
714
nodes = unique_search_sets.pop()
715
uncommon_nodes = nodes.difference(common_ancestors)
717
raise AssertionError("Somehow we ended up converging"
718
" without actually marking them as"
721
"\nuncommon_nodes: %s"
722
% (revisions, uncommon_nodes))
724
return border_ancestors, common_ancestors, searchers
726
def heads(self, keys):
727
"""Return the heads from amongst keys.
729
This is done by searching the ancestries of each key. Any key that is
730
reachable from another key is not returned; all the others are.
732
This operation scales with the relative depth between any two keys. If
733
any two keys are completely disconnected all ancestry of both sides
736
:param keys: An iterable of keys.
737
:return: A set of the heads. Note that as a set there is no ordering
738
information. Callers will need to filter their input to create
739
order if they need it.
741
candidate_heads = set(keys)
742
if revision.NULL_REVISION in candidate_heads:
743
# NULL_REVISION is only a head if it is the only entry
744
candidate_heads.remove(revision.NULL_REVISION)
745
if not candidate_heads:
746
return set([revision.NULL_REVISION])
747
if len(candidate_heads) < 2:
748
return candidate_heads
749
searchers = dict((c, self._make_breadth_first_searcher([c]))
750
for c in candidate_heads)
751
active_searchers = dict(searchers)
752
# skip over the actual candidate for each searcher
753
for searcher in active_searchers.itervalues():
755
# The common walker finds nodes that are common to two or more of the
756
# input keys, so that we don't access all history when a currently
757
# uncommon search point actually meets up with something behind a
758
# common search point. Common search points do not keep searches
759
# active; they just allow us to make searches inactive without
760
# accessing all history.
761
common_walker = self._make_breadth_first_searcher([])
762
while len(active_searchers) > 0:
767
except StopIteration:
768
# No common points being searched at this time.
770
for candidate in active_searchers.keys():
772
searcher = active_searchers[candidate]
774
# rare case: we deleted candidate in a previous iteration
775
# through this for loop, because it was determined to be
776
# a descendant of another candidate.
779
ancestors.update(searcher.next())
780
except StopIteration:
781
del active_searchers[candidate]
783
# process found nodes
785
for ancestor in ancestors:
786
if ancestor in candidate_heads:
787
candidate_heads.remove(ancestor)
788
del searchers[ancestor]
789
if ancestor in active_searchers:
790
del active_searchers[ancestor]
791
# it may meet up with a known common node
792
if ancestor in common_walker.seen:
793
# some searcher has encountered our known common nodes:
795
ancestor_set = set([ancestor])
796
for searcher in searchers.itervalues():
797
searcher.stop_searching_any(ancestor_set)
799
# or it may have been just reached by all the searchers:
800
for searcher in searchers.itervalues():
801
if ancestor not in searcher.seen:
804
# The final active searcher has just reached this node,
805
# making it be known as a descendant of all candidates,
806
# so we can stop searching it, and any seen ancestors
807
new_common.add(ancestor)
808
for searcher in searchers.itervalues():
810
searcher.find_seen_ancestors([ancestor])
811
searcher.stop_searching_any(seen_ancestors)
812
common_walker.start_searching(new_common)
813
return candidate_heads
815
def find_merge_order(self, tip_revision_id, lca_revision_ids):
816
"""Find the order that each revision was merged into tip.
818
This basically just walks backwards with a stack, and walks left-first
819
until it finds a node to stop.
821
if len(lca_revision_ids) == 1:
822
return list(lca_revision_ids)
823
looking_for = set(lca_revision_ids)
824
# TODO: Is there a way we could do this "faster" by batching up the
825
# get_parent_map requests?
826
# TODO: Should we also be culling the ancestry search right away? We
827
# could add looking_for to the "stop" list, and walk their
828
# ancestry in batched mode. The flip side is it might mean we walk a
829
# lot of "stop" nodes, rather than only the minimum.
830
# Then again, without it we may trace back into ancestry we could have
832
stack = [tip_revision_id]
835
while stack and looking_for:
838
if next in looking_for:
840
looking_for.remove(next)
841
if len(looking_for) == 1:
842
found.append(looking_for.pop())
845
parent_ids = self.get_parent_map([next]).get(next, None)
846
if not parent_ids: # Ghost, nothing to search here
848
for parent_id in reversed(parent_ids):
849
# TODO: (performance) We see the parent at this point, but we
850
# wait to mark it until later to make sure we get left
851
# parents before right parents. However, instead of
852
# waiting until we have traversed enough parents, we
853
# could instead note that we've found it, and once all
854
# parents are in the stack, just reverse iterate the
856
if parent_id not in stop:
857
# this will need to be searched
858
stack.append(parent_id)
862
def find_unique_lca(self, left_revision, right_revision,
864
"""Find a unique LCA.
866
Find lowest common ancestors. If there is no unique common
867
ancestor, find the lowest common ancestors of those ancestors.
869
Iteration stops when a unique lowest common ancestor is found.
870
The graph origin is necessarily a unique lowest common ancestor.
872
Note that None is not an acceptable substitute for NULL_REVISION.
873
in the input for this method.
875
:param count_steps: If True, the return value will be a tuple of
876
(unique_lca, steps) where steps is the number of times that
877
find_lca was run. If False, only unique_lca is returned.
879
revisions = [left_revision, right_revision]
883
lca = self.find_lca(*revisions)
891
raise errors.NoCommonAncestor(left_revision, right_revision)
894
def iter_ancestry(self, revision_ids):
895
"""Iterate the ancestry of this revision.
897
:param revision_ids: Nodes to start the search
898
:return: Yield tuples mapping a revision_id to its parents for the
899
ancestry of revision_id.
900
Ghosts will be returned with None as their parents, and nodes
901
with no parents will have NULL_REVISION as their only parent. (As
902
defined by get_parent_map.)
903
There will also be a node for (NULL_REVISION, ())
905
pending = set(revision_ids)
908
processed.update(pending)
909
next_map = self.get_parent_map(pending)
911
for item in next_map.iteritems():
913
next_pending.update(p for p in item[1] if p not in processed)
914
ghosts = pending.difference(next_map)
917
pending = next_pending
919
def iter_topo_order(self, revisions):
920
"""Iterate through the input revisions in topological order.
922
This sorting only ensures that parents come before their children.
923
An ancestor may sort after a descendant if the relationship is not
924
visible in the supplied list of revisions.
926
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
927
return sorter.iter_topo_order()
929
def is_ancestor(self, candidate_ancestor, candidate_descendant):
930
"""Determine whether a revision is an ancestor of another.
932
We answer this using heads() as heads() has the logic to perform the
933
smallest number of parent lookups to determine the ancestral
934
relationship between N revisions.
936
return set([candidate_descendant]) == self.heads(
937
[candidate_ancestor, candidate_descendant])
939
def _search_for_extra_common(self, common, searchers):
940
"""Make sure that unique nodes are genuinely unique.
942
After _find_border_ancestors, all nodes marked "common" are indeed
943
common. Some of the nodes considered unique are not, due to history
944
shortcuts stopping the searches early.
946
We know that we have searched enough when all common search tips are
947
descended from all unique (uncommon) nodes because we know that a node
948
cannot be an ancestor of its own ancestor.
950
:param common: A set of common nodes
951
:param searchers: The searchers returned from _find_border_ancestors
955
# A) The passed in searchers should all be on the same tips, thus
956
# they should be considered the "common" searchers.
957
# B) We find the difference between the searchers, these are the
958
# "unique" nodes for each side.
959
# C) We do a quick culling so that we only start searching from the
960
# more interesting unique nodes. (A unique ancestor is more
961
# interesting than any of its children.)
962
# D) We start searching for ancestors common to all unique nodes.
963
# E) We have the common searchers stop searching any ancestors of
965
# F) When there are no more common search tips, we stop
967
# TODO: We need a way to remove unique_searchers when they overlap with
968
# other unique searchers.
969
if len(searchers) != 2:
970
raise NotImplementedError(
971
"Algorithm not yet implemented for > 2 searchers")
972
common_searchers = searchers
973
left_searcher = searchers[0]
974
right_searcher = searchers[1]
975
unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
976
if not unique: # No unique nodes, nothing to do
978
total_unique = len(unique)
979
unique = self._remove_simple_descendants(unique,
980
self.get_parent_map(unique))
981
simple_unique = len(unique)
983
unique_searchers = []
984
for revision_id in unique:
985
if revision_id in left_searcher.seen:
986
parent_searcher = left_searcher
988
parent_searcher = right_searcher
989
revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
990
if not revs_to_search: # XXX: This shouldn't be possible
991
revs_to_search = [revision_id]
992
searcher = self._make_breadth_first_searcher(revs_to_search)
993
# We don't care about the starting nodes.
995
unique_searchers.append(searcher)
997
# possible todo: aggregate the common searchers into a single common
998
# searcher, just make sure that we include the nodes into the .seen
999
# properties of the original searchers
1001
ancestor_all_unique = None
1002
for searcher in unique_searchers:
1003
if ancestor_all_unique is None:
1004
ancestor_all_unique = set(searcher.seen)
1006
ancestor_all_unique = ancestor_all_unique.intersection(
1009
trace.mutter('Started %s unique searchers for %s unique revisions',
1010
simple_unique, total_unique)
1012
while True: # If we have no more nodes we have nothing to do
1013
newly_seen_common = set()
1014
for searcher in common_searchers:
1015
newly_seen_common.update(searcher.step())
1016
newly_seen_unique = set()
1017
for searcher in unique_searchers:
1018
newly_seen_unique.update(searcher.step())
1019
new_common_unique = set()
1020
for revision in newly_seen_unique:
1021
for searcher in unique_searchers:
1022
if revision not in searcher.seen:
1025
# This is a border because it is a first common that we see
1026
# after walking for a while.
1027
new_common_unique.add(revision)
1028
if newly_seen_common:
1029
# These are nodes descended from one of the 'common' searchers.
1030
# Make sure all searchers are on the same page
1031
for searcher in common_searchers:
1032
newly_seen_common.update(
1033
searcher.find_seen_ancestors(newly_seen_common))
1034
# We start searching the whole ancestry. It is a bit wasteful,
1035
# though. We really just want to mark all of these nodes as
1036
# 'seen' and then start just the tips. However, it requires a
1037
# get_parent_map() call to figure out the tips anyway, and all
1038
# redundant requests should be fairly fast.
1039
for searcher in common_searchers:
1040
searcher.start_searching(newly_seen_common)
1042
# If a 'common' node is an ancestor of all unique searchers, we
1043
# can stop searching it.
1044
stop_searching_common = ancestor_all_unique.intersection(
1046
if stop_searching_common:
1047
for searcher in common_searchers:
1048
searcher.stop_searching_any(stop_searching_common)
1049
if new_common_unique:
1050
# We found some ancestors that are common
1051
for searcher in unique_searchers:
1052
new_common_unique.update(
1053
searcher.find_seen_ancestors(new_common_unique))
1054
# Since these are common, we can grab another set of ancestors
1056
for searcher in common_searchers:
1057
new_common_unique.update(
1058
searcher.find_seen_ancestors(new_common_unique))
1060
# We can tell all of the unique searchers to start at these
1061
# nodes, and tell all of the common searchers to *stop*
1062
# searching these nodes
1063
for searcher in unique_searchers:
1064
searcher.start_searching(new_common_unique)
1065
for searcher in common_searchers:
1066
searcher.stop_searching_any(new_common_unique)
1067
ancestor_all_unique.update(new_common_unique)
1069
# Filter out searchers that don't actually search different
1070
# nodes. We already have the ancestry intersection for them
1071
next_unique_searchers = []
1072
unique_search_sets = set()
1073
for searcher in unique_searchers:
1074
will_search_set = frozenset(searcher._next_query)
1075
if will_search_set not in unique_search_sets:
1076
# This searcher is searching a unique set of nodes, let it
1077
unique_search_sets.add(will_search_set)
1078
next_unique_searchers.append(searcher)
1079
unique_searchers = next_unique_searchers
1080
for searcher in common_searchers:
1081
if searcher._next_query:
1084
# All common searcher have stopped searching
1087
def _remove_simple_descendants(self, revisions, parent_map):
1088
"""remove revisions which are children of other ones in the set
1090
This doesn't do any graph searching, it just checks the immediate
1091
parent_map to find if there are any children which can be removed.
1093
:param revisions: A set of revision_ids
1094
:return: A set of revision_ids with the children removed
1096
simple_ancestors = revisions.copy()
1097
# TODO: jam 20071214 we *could* restrict it to searching only the
1098
# parent_map of revisions already present in 'revisions', but
1099
# considering the general use case, I think this is actually
1102
# This is the same as the following loop. I don't know that it is any
1104
## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1105
## if p_ids is not None and revisions.intersection(p_ids))
1106
## return simple_ancestors
1108
# Yet Another Way, invert the parent map (which can be cached)
1110
## for revision_id, parent_ids in parent_map.iteritems():
1111
## for p_id in parent_ids:
1112
## descendants.setdefault(p_id, []).append(revision_id)
1113
## for revision in revisions.intersection(descendants):
1114
## simple_ancestors.difference_update(descendants[revision])
1115
## return simple_ancestors
1116
for revision, parent_ids in parent_map.iteritems():
1117
if parent_ids is None:
1119
for parent_id in parent_ids:
1120
if parent_id in revisions:
1121
# This node has a parent present in the set, so we can
1123
simple_ancestors.discard(revision)
1125
return simple_ancestors
1128
class HeadsCache(object):
1129
"""A cache of results for graph heads calls."""
1131
def __init__(self, graph):
1135
def heads(self, keys):
1136
"""Return the heads of keys.
1138
This matches the API of Graph.heads(), specifically the return value is
1139
a set which can be mutated, and ordering of the input is not preserved
1142
:see also: Graph.heads.
1143
:param keys: The keys to calculate heads for.
1144
:return: A set containing the heads, which may be mutated without
1145
affecting future lookups.
1147
keys = frozenset(keys)
1149
return set(self._heads[keys])
1151
heads = self.graph.heads(keys)
1152
self._heads[keys] = heads
1156
class FrozenHeadsCache(object):
1157
"""Cache heads() calls, assuming the caller won't modify them."""
1159
def __init__(self, graph):
1163
def heads(self, keys):
1164
"""Return the heads of keys.
1166
Similar to Graph.heads(). The main difference is that the return value
1167
is a frozen set which cannot be mutated.
1169
:see also: Graph.heads.
1170
:param keys: The keys to calculate heads for.
1171
:return: A frozenset containing the heads.
1173
keys = frozenset(keys)
1175
return self._heads[keys]
1177
heads = frozenset(self.graph.heads(keys))
1178
self._heads[keys] = heads
1181
def cache(self, keys, heads):
1182
"""Store a known value."""
1183
self._heads[frozenset(keys)] = frozenset(heads)
1186
class _BreadthFirstSearcher(object):
1187
"""Parallel search breadth-first the ancestry of revisions.
1189
This class implements the iterator protocol, but additionally
1190
1. provides a set of seen ancestors, and
1191
2. allows some ancestries to be unsearched, via stop_searching_any
1194
def __init__(self, revisions, parents_provider):
1195
self._iterations = 0
1196
self._next_query = set(revisions)
1198
self._started_keys = set(self._next_query)
1199
self._stopped_keys = set()
1200
self._parents_provider = parents_provider
1201
self._returning = 'next_with_ghosts'
1202
self._current_present = set()
1203
self._current_ghosts = set()
1204
self._current_parents = {}
1207
if self._iterations:
1208
prefix = "searching"
1211
search = '%s=%r' % (prefix, list(self._next_query))
1212
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1213
' seen=%r)' % (self._iterations, search, list(self.seen)))
1215
def get_result(self):
1216
"""Get a SearchResult for the current state of this searcher.
1218
:return: A SearchResult for this search so far. The SearchResult is
1219
static - the search can be advanced and the search result will not
1220
be invalidated or altered.
1222
if self._returning == 'next':
1223
# We have to know the current nodes children to be able to list the
1224
# exclude keys for them. However, while we could have a second
1225
# look-ahead result buffer and shuffle things around, this method
1226
# is typically only called once per search - when memoising the
1227
# results of the search.
1228
found, ghosts, next, parents = self._do_query(self._next_query)
1229
# pretend we didn't query: perhaps we should tweak _do_query to be
1230
# entirely stateless?
1231
self.seen.difference_update(next)
1232
next_query = next.union(ghosts)
1234
next_query = self._next_query
1235
excludes = self._stopped_keys.union(next_query)
1236
included_keys = self.seen.difference(excludes)
1237
return SearchResult(self._started_keys, excludes, len(included_keys),
1243
except StopIteration:
1247
"""Return the next ancestors of this revision.
1249
Ancestors are returned in the order they are seen in a breadth-first
1250
traversal. No ancestor will be returned more than once. Ancestors are
1251
returned before their parentage is queried, so ghosts and missing
1252
revisions (including the start revisions) are included in the result.
1253
This can save a round trip in LCA style calculation by allowing
1254
convergence to be detected without reading the data for the revision
1255
the convergence occurs on.
1257
:return: A set of revision_ids.
1259
if self._returning != 'next':
1260
# switch to returning the query, not the results.
1261
self._returning = 'next'
1262
self._iterations += 1
1265
if len(self._next_query) == 0:
1266
raise StopIteration()
1267
# We have seen what we're querying at this point as we are returning
1268
# the query, not the results.
1269
self.seen.update(self._next_query)
1270
return self._next_query
1272
def next_with_ghosts(self):
1273
"""Return the next found ancestors, with ghosts split out.
1275
Ancestors are returned in the order they are seen in a breadth-first
1276
traversal. No ancestor will be returned more than once. Ancestors are
1277
returned only after asking for their parents, which allows us to detect
1278
which revisions are ghosts and which are not.
1280
:return: A tuple with (present ancestors, ghost ancestors) sets.
1282
if self._returning != 'next_with_ghosts':
1283
# switch to returning the results, not the current query.
1284
self._returning = 'next_with_ghosts'
1286
if len(self._next_query) == 0:
1287
raise StopIteration()
1289
return self._current_present, self._current_ghosts
1292
"""Advance the search.
1294
Updates self.seen, self._next_query, self._current_present,
1295
self._current_ghosts, self._current_parents and self._iterations.
1297
self._iterations += 1
1298
found, ghosts, next, parents = self._do_query(self._next_query)
1299
self._current_present = found
1300
self._current_ghosts = ghosts
1301
self._next_query = next
1302
self._current_parents = parents
1303
# ghosts are implicit stop points, otherwise the search cannot be
1304
# repeated when ghosts are filled.
1305
self._stopped_keys.update(ghosts)
1307
def _do_query(self, revisions):
1308
"""Query for revisions.
1310
Adds revisions to the seen set.
1312
:param revisions: Revisions to query.
1313
:return: A tuple: (set(found_revisions), set(ghost_revisions),
1314
set(parents_of_found_revisions), dict(found_revisions:parents)).
1316
found_revisions = set()
1317
parents_of_found = set()
1318
# revisions may contain nodes that point to other nodes in revisions:
1319
# we want to filter them out.
1320
self.seen.update(revisions)
1321
parent_map = self._parents_provider.get_parent_map(revisions)
1322
found_revisions.update(parent_map)
1323
for rev_id, parents in parent_map.iteritems():
1326
new_found_parents = [p for p in parents if p not in self.seen]
1327
if new_found_parents:
1328
# Calling set.update() with an empty generator is actually
1330
parents_of_found.update(new_found_parents)
1331
ghost_revisions = revisions - found_revisions
1332
return found_revisions, ghost_revisions, parents_of_found, parent_map
1337
def find_seen_ancestors(self, revisions):
1338
"""Find ancestors of these revisions that have already been seen.
1340
This function generally makes the assumption that querying for the
1341
parents of a node that has already been queried is reasonably cheap.
1342
(eg, not a round trip to a remote host).
1344
# TODO: Often we might ask one searcher for its seen ancestors, and
1345
# then ask another searcher the same question. This can result in
1346
# searching the same revisions repeatedly if the two searchers
1347
# have a lot of overlap.
1348
all_seen = self.seen
1349
pending = set(revisions).intersection(all_seen)
1350
seen_ancestors = set(pending)
1352
if self._returning == 'next':
1353
# self.seen contains what nodes have been returned, not what nodes
1354
# have been queried. We don't want to probe for nodes that haven't
1355
# been searched yet.
1356
not_searched_yet = self._next_query
1358
not_searched_yet = ()
1359
pending.difference_update(not_searched_yet)
1360
get_parent_map = self._parents_provider.get_parent_map
1362
parent_map = get_parent_map(pending)
1364
# We don't care if it is a ghost, since it can't be seen if it is
1366
for parent_ids in parent_map.itervalues():
1367
all_parents.extend(parent_ids)
1368
next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1369
seen_ancestors.update(next_pending)
1370
next_pending.difference_update(not_searched_yet)
1371
pending = next_pending
1373
return seen_ancestors
1375
def stop_searching_any(self, revisions):
1377
Remove any of the specified revisions from the search list.
1379
None of the specified revisions are required to be present in the
1382
It is okay to call stop_searching_any() for revisions which were seen
1383
in previous iterations. It is the callers responsibility to call
1384
find_seen_ancestors() to make sure that current search tips that are
1385
ancestors of those revisions are also stopped. All explicitly stopped
1386
revisions will be excluded from the search result's get_keys(), though.
1388
# TODO: does this help performance?
1391
revisions = frozenset(revisions)
1392
if self._returning == 'next':
1393
stopped = self._next_query.intersection(revisions)
1394
self._next_query = self._next_query.difference(revisions)
1396
stopped_present = self._current_present.intersection(revisions)
1397
stopped = stopped_present.union(
1398
self._current_ghosts.intersection(revisions))
1399
self._current_present.difference_update(stopped)
1400
self._current_ghosts.difference_update(stopped)
1401
# stopping 'x' should stop returning parents of 'x', but
1402
# not if 'y' always references those same parents
1403
stop_rev_references = {}
1404
for rev in stopped_present:
1405
for parent_id in self._current_parents[rev]:
1406
if parent_id not in stop_rev_references:
1407
stop_rev_references[parent_id] = 0
1408
stop_rev_references[parent_id] += 1
1409
# if only the stopped revisions reference it, the ref count will be
1411
for parents in self._current_parents.itervalues():
1412
for parent_id in parents:
1414
stop_rev_references[parent_id] -= 1
1417
stop_parents = set()
1418
for rev_id, refs in stop_rev_references.iteritems():
1420
stop_parents.add(rev_id)
1421
self._next_query.difference_update(stop_parents)
1422
self._stopped_keys.update(stopped)
1423
self._stopped_keys.update(revisions - set([revision.NULL_REVISION]))
1426
def start_searching(self, revisions):
1427
"""Add revisions to the search.
1429
The parents of revisions will be returned from the next call to next()
1430
or next_with_ghosts(). If next_with_ghosts was the most recently used
1431
next* call then the return value is the result of looking up the
1432
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1434
revisions = frozenset(revisions)
1435
self._started_keys.update(revisions)
1436
new_revisions = revisions.difference(self.seen)
1437
if self._returning == 'next':
1438
self._next_query.update(new_revisions)
1439
self.seen.update(new_revisions)
1441
# perform a query on revisions
1442
revs, ghosts, query, parents = self._do_query(revisions)
1443
self._stopped_keys.update(ghosts)
1444
self._current_present.update(revs)
1445
self._current_ghosts.update(ghosts)
1446
self._next_query.update(query)
1447
self._current_parents.update(parents)
1451
class SearchResult(object):
1452
"""The result of a breadth first search.
1454
A SearchResult provides the ability to reconstruct the search or access a
1455
set of the keys the search found.
1458
def __init__(self, start_keys, exclude_keys, key_count, keys):
1459
"""Create a SearchResult.
1461
:param start_keys: The keys the search started at.
1462
:param exclude_keys: The keys the search excludes.
1463
:param key_count: The total number of keys (from start to but not
1465
:param keys: The keys the search found. Note that in future we may get
1466
a SearchResult from a smart server, in which case the keys list is
1467
not necessarily immediately available.
1469
self._recipe = (start_keys, exclude_keys, key_count)
1470
self._keys = frozenset(keys)
1472
def get_recipe(self):
1473
"""Return a recipe that can be used to replay this search.
1475
The recipe allows reconstruction of the same results at a later date
1476
without knowing all the found keys. The essential elements are a list
1477
of keys to start and and to stop at. In order to give reproducible
1478
results when ghosts are encountered by a search they are automatically
1479
added to the exclude list (or else ghost filling may alter the
1482
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1483
recreate the results of this search, create a breadth first
1484
searcher on the same graph starting at start_keys. Then call next()
1485
(or next_with_ghosts()) repeatedly, and on every result, call
1486
stop_searching_any on any keys from the exclude_keys set. The
1487
revision_count value acts as a trivial cross-check - the found
1488
revisions of the new search should have as many elements as
1489
revision_count. If it does not, then additional revisions have been
1490
ghosted since the search was executed the first time and the second
1496
"""Return the keys found in this search.
1498
:return: A set of keys.
1503
def collapse_linear_regions(parent_map):
1504
"""Collapse regions of the graph that are 'linear'.
1510
can be collapsed by removing B and getting::
1514
:param parent_map: A dictionary mapping children to their parents
1515
:return: Another dictionary with 'linear' chains collapsed
1517
# Note: this isn't a strictly minimal collapse. For example:
1525
# Will not have 'D' removed, even though 'E' could fit. Also:
1531
# A and C are both kept because they are edges of the graph. We *could* get
1532
# rid of A if we wanted.
1540
# Will not have any nodes removed, even though you do have an
1541
# 'uninteresting' linear D->B and E->C
1543
for child, parents in parent_map.iteritems():
1544
children.setdefault(child, [])
1546
children.setdefault(p, []).append(child)
1548
orig_children = dict(children)
1550
result = dict(parent_map)
1551
for node in parent_map:
1552
parents = result[node]
1553
if len(parents) == 1:
1554
parent_children = children[parents[0]]
1555
if len(parent_children) != 1:
1556
# This is not the only child
1558
node_children = children[node]
1559
if len(node_children) != 1:
1561
child_parents = result.get(node_children[0], None)
1562
if len(child_parents) != 1:
1563
# This is not its only parent
1565
# The child of this node only points at it, and the parent only has
1566
# this as a child. remove this node, and join the others together
1567
result[node_children[0]] = parents
1568
children[parents[0]] = node_children
added
removed
bzrlib/graph.py
