~bzr-pqm/bzr/bzr.dev

2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
1
# Copyright (C) 2007 Canonical Ltd
2
#
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.
7
#
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.
12
#
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
4183.7.1 by Sabin Iacob
update FSF mailing address
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
16
3377.4.5 by John Arbash Meinel
Several updates. A bit more debug logging, only step the all_unique searcher 1/10th of the time.
17
import time
18
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
19
from bzrlib import (
3377.3.33 by John Arbash Meinel
Add some logging with -Dgraph
20
    debug,
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
21
    errors,
3052.1.3 by John Arbash Meinel
deprecate revision.is_ancestor, update the callers and the tests.
22
    revision,
3099.3.3 by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map()
23
    symbol_versioning,
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
24
    trace,
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
25
    tsort,
26
    )
2490.2.1 by Aaron Bentley
Start work on GraphWalker
27
3377.4.9 by John Arbash Meinel
STEP every 5
28
STEP_UNIQUE_SEARCHER_EVERY = 5
3377.4.5 by John Arbash Meinel
Several updates. A bit more debug logging, only step the all_unique searcher 1/10th of the time.
29
2490.2.25 by Aaron Bentley
Update from review
30
# DIAGRAM of terminology
31
#       A
32
#       /\
33
#      B  C
34
#      |  |\
35
#      D  E F
36
#      |\/| |
37
#      |/\|/
38
#      G  H
39
#
40
# In this diagram, relative to G and H:
41
# A, B, C, D, E are common ancestors.
42
# C, D and E are border ancestors, because each has a non-common descendant.
43
# D and E are least common ancestors because none of their descendants are
44
# common ancestors.
45
# C is not a least common ancestor because its descendant, E, is a common
46
# ancestor.
47
#
48
# The find_unique_lca algorithm will pick A in two steps:
49
# 1. find_lca('G', 'H') => ['D', 'E']
50
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
51
52
2988.1.3 by Robert Collins
Add a new repositoy method _generate_text_key_index for use by reconcile/check.
53
class DictParentsProvider(object):
3172.1.2 by Robert Collins
Parent Providers should now implement ``get_parent_map`` returning a
54
    """A parents provider for Graph objects."""
2988.1.3 by Robert Collins
Add a new repositoy method _generate_text_key_index for use by reconcile/check.
55
56
    def __init__(self, ancestry):
57
        self.ancestry = ancestry
58
59
    def __repr__(self):
60
        return 'DictParentsProvider(%r)' % self.ancestry
61
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
62
    def get_parent_map(self, keys):
63
        """See _StackedParentsProvider.get_parent_map"""
64
        ancestry = self.ancestry
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
67
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
68
class _StackedParentsProvider(object):
69
70
    def __init__(self, parent_providers):
71
        self._parent_providers = parent_providers
72
2490.2.28 by Aaron Bentley
Fix handling of null revision
73
    def __repr__(self):
74
        return "_StackedParentsProvider(%r)" % self._parent_providers
75
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
76
    def get_parent_map(self, keys):
77
        """Get a mapping of keys => parents
78
79
        A dictionary is returned with an entry for each key present in this
80
        source. If this source doesn't have information about a key, it should
81
        not include an entry.
82
83
        [NULL_REVISION] is used as the parent of the first user-committed
84
        revision.  Its parent list is empty.
85
86
        :param keys: An iterable returning keys to check (eg revision_ids)
87
        :return: A dictionary mapping each key to its parents
88
        """
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
89
        found = {}
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
90
        remaining = set(keys)
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
91
        for parents_provider in self._parent_providers:
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
92
            new_found = parents_provider.get_parent_map(remaining)
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
93
            found.update(new_found)
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
94
            remaining.difference_update(new_found)
95
            if not remaining:
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
96
                break
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
97
        return found
98
99
100
class CachingParentsProvider(object):
3835.1.13 by Aaron Bentley
Update documentation
101
    """A parents provider which will cache the revision => parents as a dict.
102
103
    This is useful for providers which have an expensive look up.
104
105
    Either a ParentsProvider or a get_parent_map-like callback may be
106
    supplied.  If it provides extra un-asked-for parents, they will be cached,
107
    but filtered out of get_parent_map.
3835.1.16 by Aaron Bentley
Updates from review
108
109
    The cache is enabled by default, but may be disabled and re-enabled.
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
110
    """
3896.1.1 by Andrew Bennetts
Remove broken debugging cruft, and some unused imports.
111
    def __init__(self, parent_provider=None, get_parent_map=None):
3835.1.13 by Aaron Bentley
Update documentation
112
        """Constructor.
113
114
        :param parent_provider: The ParentProvider to use.  It or
115
            get_parent_map must be supplied.
116
        :param get_parent_map: The get_parent_map callback to use.  It or
117
            parent_provider must be supplied.
118
        """
3835.1.12 by Aaron Bentley
Unify CachingExtraParentsProvider and CachingParentsProvider.
119
        self._real_provider = parent_provider
120
        if get_parent_map is None:
121
            self._get_parent_map = self._real_provider.get_parent_map
122
        else:
123
            self._get_parent_map = get_parent_map
3835.1.16 by Aaron Bentley
Updates from review
124
        self._cache = {}
3835.1.15 by Aaron Bentley
Allow miss caching to be disabled.
125
        self._cache_misses = True
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
126
3835.1.12 by Aaron Bentley
Unify CachingExtraParentsProvider and CachingParentsProvider.
127
    def __repr__(self):
128
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
129
3835.1.15 by Aaron Bentley
Allow miss caching to be disabled.
130
    def enable_cache(self, cache_misses=True):
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
131
        """Enable cache."""
3835.1.19 by Aaron Bentley
Raise exception when caching is enabled twice.
132
        if self._cache is not None:
3835.1.20 by Aaron Bentley
Change custom error to an AssertionError.
133
            raise AssertionError('Cache enabled when already enabled.')
3835.1.16 by Aaron Bentley
Updates from review
134
        self._cache = {}
3835.1.15 by Aaron Bentley
Allow miss caching to be disabled.
135
        self._cache_misses = cache_misses
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
136
137
    def disable_cache(self):
3835.1.16 by Aaron Bentley
Updates from review
138
        """Disable and clear the cache."""
139
        self._cache = None
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
140
141
    def get_cached_map(self):
142
        """Return any cached get_parent_map values."""
3835.1.16 by Aaron Bentley
Updates from review
143
        if self._cache is None:
3835.1.12 by Aaron Bentley
Unify CachingExtraParentsProvider and CachingParentsProvider.
144
            return None
3835.1.16 by Aaron Bentley
Updates from review
145
        return dict((k, v) for k, v in self._cache.items()
3835.1.12 by Aaron Bentley
Unify CachingExtraParentsProvider and CachingParentsProvider.
146
                    if v is not None)
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
147
148
    def get_parent_map(self, keys):
3835.1.16 by Aaron Bentley
Updates from review
149
        """See _StackedParentsProvider.get_parent_map."""
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
150
        # Hack to build up the caching logic.
3835.1.16 by Aaron Bentley
Updates from review
151
        ancestry = self._cache
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
152
        if ancestry is None:
153
            # Caching is disabled.
154
            missing_revisions = set(keys)
155
            ancestry = {}
156
        else:
157
            missing_revisions = set(key for key in keys if key not in ancestry)
158
        if missing_revisions:
159
            parent_map = self._get_parent_map(missing_revisions)
160
            ancestry.update(parent_map)
3835.1.15 by Aaron Bentley
Allow miss caching to be disabled.
161
            if self._cache_misses:
3835.1.16 by Aaron Bentley
Updates from review
162
                # None is never a valid parents list, so it can be used to
163
                # record misses.
3835.1.15 by Aaron Bentley
Allow miss caching to be disabled.
164
                ancestry.update(dict((k, None) for k in missing_revisions
165
                                     if k not in parent_map))
3835.1.12 by Aaron Bentley
Unify CachingExtraParentsProvider and CachingParentsProvider.
166
        present_keys = [k for k in keys if ancestry.get(k) is not None]
3835.1.10 by Aaron Bentley
Move CachingExtraParentsProvider to Graph
167
        return dict((k, ancestry[k]) for k in present_keys)
168
169
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
170
class Graph(object):
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
171
    """Provide incremental access to revision graphs.
172
173
    This is the generic implementation; it is intended to be subclassed to
174
    specialize it for other repository types.
175
    """
2490.2.1 by Aaron Bentley
Start work on GraphWalker
176
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
177
    def __init__(self, parents_provider):
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
178
        """Construct a Graph that uses several graphs as its input
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
179
180
        This should not normally be invoked directly, because there may be
181
        specialized implementations for particular repository types.  See
3172.1.2 by Robert Collins
Parent Providers should now implement ``get_parent_map`` returning a
182
        Repository.get_graph().
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
183
3172.1.2 by Robert Collins
Parent Providers should now implement ``get_parent_map`` returning a
184
        :param parents_provider: An object providing a get_parent_map call
185
            conforming to the behavior of
186
            StackedParentsProvider.get_parent_map.
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
187
        """
3172.1.2 by Robert Collins
Parent Providers should now implement ``get_parent_map`` returning a
188
        if getattr(parents_provider, 'get_parents', None) is not None:
189
            self.get_parents = parents_provider.get_parents
190
        if getattr(parents_provider, 'get_parent_map', None) is not None:
191
            self.get_parent_map = parents_provider.get_parent_map
2490.2.29 by Aaron Bentley
Make parents provider private
192
        self._parents_provider = parents_provider
2490.2.28 by Aaron Bentley
Fix handling of null revision
193
194
    def __repr__(self):
2490.2.29 by Aaron Bentley
Make parents provider private
195
        return 'Graph(%r)' % self._parents_provider
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
196
197
    def find_lca(self, *revisions):
198
        """Determine the lowest common ancestors of the provided revisions
199
200
        A lowest common ancestor is a common ancestor none of whose
201
        descendants are common ancestors.  In graphs, unlike trees, there may
202
        be multiple lowest common ancestors.
2490.2.12 by Aaron Bentley
Improve documentation
203
204
        This algorithm has two phases.  Phase 1 identifies border ancestors,
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
205
        and phase 2 filters border ancestors to determine lowest common
206
        ancestors.
2490.2.12 by Aaron Bentley
Improve documentation
207
208
        In phase 1, border ancestors are identified, using a breadth-first
209
        search starting at the bottom of the graph.  Searches are stopped
210
        whenever a node or one of its descendants is determined to be common
211
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
212
        In phase 2, the border ancestors are filtered to find the least
2490.2.12 by Aaron Bentley
Improve documentation
213
        common ancestors.  This is done by searching the ancestries of each
214
        border ancestor.
215
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
216
        Phase 2 is perfomed on the principle that a border ancestor that is
217
        not an ancestor of any other border ancestor is a least common
218
        ancestor.
2490.2.12 by Aaron Bentley
Improve documentation
219
220
        Searches are stopped when they find a node that is determined to be a
221
        common ancestor of all border ancestors, because this shows that it
222
        cannot be a descendant of any border ancestor.
223
224
        The scaling of this operation should be proportional to
225
        1. The number of uncommon ancestors
226
        2. The number of border ancestors
227
        3. The length of the shortest path between a border ancestor and an
228
           ancestor of all border ancestors.
2490.2.3 by Aaron Bentley
Implement new merge base picker
229
        """
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
230
        border_common, common, sides = self._find_border_ancestors(revisions)
2776.3.1 by Robert Collins
* Deprecated method ``find_previous_heads`` on
231
        # We may have common ancestors that can be reached from each other.
232
        # - ask for the heads of them to filter it down to only ones that
233
        # cannot be reached from each other - phase 2.
234
        return self.heads(border_common)
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
235
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
236
    def find_difference(self, left_revision, right_revision):
2490.2.25 by Aaron Bentley
Update from review
237
        """Determine the graph difference between two revisions"""
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
238
        border, common, searchers = self._find_border_ancestors(
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
239
            [left_revision, right_revision])
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
240
        self._search_for_extra_common(common, searchers)
241
        left = searchers[0].seen
242
        right = searchers[1].seen
243
        return (left.difference(right), right.difference(left))
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
244
3445.1.4 by John Arbash Meinel
Change the function to be called 'find_distance_to_null'
245
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
246
        """Find the left-hand distance to the NULL_REVISION.
247
248
        (This can also be considered the revno of a branch at
249
        target_revision_id.)
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
250
251
        :param target_revision_id: A revision_id which we would like to know
252
            the revno for.
253
        :param known_revision_ids: [(revision_id, revno)] A list of known
254
            revno, revision_id tuples. We'll use this to seed the search.
255
        """
256
        # Map from revision_ids to a known value for their revno
257
        known_revnos = dict(known_revision_ids)
258
        cur_tip = target_revision_id
259
        num_steps = 0
260
        NULL_REVISION = revision.NULL_REVISION
3445.1.2 by John Arbash Meinel
Handle when a known revision is an ancestor.
261
        known_revnos[NULL_REVISION] = 0
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
262
3445.1.3 by John Arbash Meinel
Search from all of the known revisions.
263
        searching_known_tips = list(known_revnos.keys())
264
265
        unknown_searched = {}
266
3445.1.2 by John Arbash Meinel
Handle when a known revision is an ancestor.
267
        while cur_tip not in known_revnos:
3445.1.3 by John Arbash Meinel
Search from all of the known revisions.
268
            unknown_searched[cur_tip] = num_steps
269
            num_steps += 1
3445.1.2 by John Arbash Meinel
Handle when a known revision is an ancestor.
270
            to_search = set([cur_tip])
3445.1.3 by John Arbash Meinel
Search from all of the known revisions.
271
            to_search.update(searching_known_tips)
3445.1.2 by John Arbash Meinel
Handle when a known revision is an ancestor.
272
            parent_map = self.get_parent_map(to_search)
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
273
            parents = parent_map.get(cur_tip, None)
3445.1.8 by John Arbash Meinel
Clarity tweaks recommended by Ian
274
            if not parents: # An empty list or None is a ghost
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
275
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
276
                                                       cur_tip)
277
            cur_tip = parents[0]
3445.1.3 by John Arbash Meinel
Search from all of the known revisions.
278
            next_known_tips = []
279
            for revision_id in searching_known_tips:
280
                parents = parent_map.get(revision_id, None)
281
                if not parents:
282
                    continue
283
                next = parents[0]
284
                next_revno = known_revnos[revision_id] - 1
285
                if next in unknown_searched:
286
                    # We have enough information to return a value right now
287
                    return next_revno + unknown_searched[next]
288
                if next in known_revnos:
289
                    continue
290
                known_revnos[next] = next_revno
291
                next_known_tips.append(next)
292
            searching_known_tips = next_known_tips
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
293
3445.1.2 by John Arbash Meinel
Handle when a known revision is an ancestor.
294
        # We reached a known revision, so just add in how many steps it took to
295
        # get there.
296
        return known_revnos[cur_tip] + num_steps
3445.1.1 by John Arbash Meinel
Start working on a new Graph api to make finding revision numbers faster.
297
3377.3.21 by John Arbash Meinel
Simple brute-force implementation of find_unique_ancestors
298
    def find_unique_ancestors(self, unique_revision, common_revisions):
299
        """Find the unique ancestors for a revision versus others.
300
301
        This returns the ancestry of unique_revision, excluding all revisions
302
        in the ancestry of common_revisions. If unique_revision is in the
303
        ancestry, then the empty set will be returned.
304
305
        :param unique_revision: The revision_id whose ancestry we are
306
            interested in.
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
307
            XXX: Would this API be better if we allowed multiple revisions on
308
                 to be searched here?
3377.3.21 by John Arbash Meinel
Simple brute-force implementation of find_unique_ancestors
309
        :param common_revisions: Revision_ids of ancestries to exclude.
310
        :return: A set of revisions in the ancestry of unique_revision
311
        """
312
        if unique_revision in common_revisions:
313
            return set()
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
314
315
        # Algorithm description
316
        # 1) Walk backwards from the unique node and all common nodes.
317
        # 2) When a node is seen by both sides, stop searching it in the unique
318
        #    walker, include it in the common walker.
319
        # 3) Stop searching when there are no nodes left for the unique walker.
320
        #    At this point, you have a maximal set of unique nodes. Some of
321
        #    them may actually be common, and you haven't reached them yet.
322
        # 4) Start new searchers for the unique nodes, seeded with the
323
        #    information you have so far.
324
        # 5) Continue searching, stopping the common searches when the search
325
        #    tip is an ancestor of all unique nodes.
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
326
        # 6) Aggregate together unique searchers when they are searching the
327
        #    same tips. When all unique searchers are searching the same node,
328
        #    stop move it to a single 'all_unique_searcher'.
329
        # 7) The 'all_unique_searcher' represents the very 'tip' of searching.
330
        #    Most of the time this produces very little important information.
331
        #    So don't step it as quickly as the other searchers.
332
        # 8) Search is done when all common searchers have completed.
333
334
        unique_searcher, common_searcher = self._find_initial_unique_nodes(
335
            [unique_revision], common_revisions)
336
337
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
338
        if not unique_nodes:
339
            return unique_nodes
340
341
        (all_unique_searcher,
342
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
343
                                    unique_searcher, common_searcher)
344
345
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
346
                                  unique_tip_searchers, common_searcher)
347
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
3377.3.33 by John Arbash Meinel
Add some logging with -Dgraph
348
        if 'graph' in debug.debug_flags:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
349
            trace.mutter('Found %d truly unique nodes out of %d',
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
350
                         len(true_unique_nodes), len(unique_nodes))
351
        return true_unique_nodes
352
353
    def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
354
        """Steps 1-3 of find_unique_ancestors.
355
356
        Find the maximal set of unique nodes. Some of these might actually
357
        still be common, but we are sure that there are no other unique nodes.
358
359
        :return: (unique_searcher, common_searcher)
360
        """
361
362
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
363
        # we know that unique_revisions aren't in common_revisions, so skip
364
        # past them.
3377.3.27 by John Arbash Meinel
some simple updates
365
        unique_searcher.next()
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
366
        common_searcher = self._make_breadth_first_searcher(common_revisions)
367
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
368
        # As long as we are still finding unique nodes, keep searching
3377.3.27 by John Arbash Meinel
some simple updates
369
        while unique_searcher._next_query:
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
370
            next_unique_nodes = set(unique_searcher.step())
371
            next_common_nodes = set(common_searcher.step())
372
373
            # Check if either searcher encounters new nodes seen by the other
374
            # side.
375
            unique_are_common_nodes = next_unique_nodes.intersection(
376
                common_searcher.seen)
377
            unique_are_common_nodes.update(
378
                next_common_nodes.intersection(unique_searcher.seen))
379
            if unique_are_common_nodes:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
380
                ancestors = unique_searcher.find_seen_ancestors(
381
                                unique_are_common_nodes)
3377.4.5 by John Arbash Meinel
Several updates. A bit more debug logging, only step the all_unique searcher 1/10th of the time.
382
                # TODO: This is a bit overboard, we only really care about
383
                #       the ancestors of the tips because the rest we
384
                #       already know. This is *correct* but causes us to
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
385
                #       search too much ancestry.
3377.3.29 by John Arbash Meinel
Revert the _find_any_seen change.
386
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
387
                unique_searcher.stop_searching_any(ancestors)
388
                common_searcher.start_searching(ancestors)
389
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
390
        return unique_searcher, common_searcher
391
392
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
393
                               common_searcher):
394
        """Create a searcher for all the unique search tips (step 4).
395
396
        As a side effect, the common_searcher will stop searching any nodes
397
        that are ancestors of the unique searcher tips.
398
399
        :return: (all_unique_searcher, unique_tip_searchers)
400
        """
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
401
        unique_tips = self._remove_simple_descendants(unique_nodes,
402
                        self.get_parent_map(unique_nodes))
403
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
404
        if len(unique_tips) == 1:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
405
            unique_tip_searchers = []
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
406
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
407
        else:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
408
            unique_tip_searchers = []
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
409
            for tip in unique_tips:
410
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
411
                revs_to_search.update(
412
                    common_searcher.find_seen_ancestors(revs_to_search))
413
                searcher = self._make_breadth_first_searcher(revs_to_search)
414
                # We don't care about the starting nodes.
415
                searcher._label = tip
416
                searcher.step()
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
417
                unique_tip_searchers.append(searcher)
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
418
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
419
            ancestor_all_unique = None
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
420
            for searcher in unique_tip_searchers:
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
421
                if ancestor_all_unique is None:
422
                    ancestor_all_unique = set(searcher.seen)
423
                else:
424
                    ancestor_all_unique = ancestor_all_unique.intersection(
425
                                                searcher.seen)
3377.3.33 by John Arbash Meinel
Add some logging with -Dgraph
426
        # Collapse all the common nodes into a single searcher
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
427
        all_unique_searcher = self._make_breadth_first_searcher(
428
                                ancestor_all_unique)
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
429
        if ancestor_all_unique:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
430
            # We've seen these nodes in all the searchers, so we'll just go to
431
            # the next
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
432
            all_unique_searcher.step()
433
434
            # Stop any search tips that are already known as ancestors of the
435
            # unique nodes
436
            stopped_common = common_searcher.stop_searching_any(
437
                common_searcher.find_seen_ancestors(ancestor_all_unique))
438
439
            total_stopped = 0
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
440
            for searcher in unique_tip_searchers:
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
441
                total_stopped += len(searcher.stop_searching_any(
442
                    searcher.find_seen_ancestors(ancestor_all_unique)))
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
443
        if 'graph' in debug.debug_flags:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
444
            trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
445
                         ' (%d stopped search tips, %d common ancestors'
446
                         ' (%d stopped common)',
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
447
                         len(unique_nodes), len(unique_tip_searchers),
448
                         total_stopped, len(ancestor_all_unique),
449
                         len(stopped_common))
450
        return all_unique_searcher, unique_tip_searchers
451
452
    def _step_unique_and_common_searchers(self, common_searcher,
453
                                          unique_tip_searchers,
454
                                          unique_searcher):
3377.4.7 by John Arbash Meinel
Small documentation and code wrapping cleanup
455
        """Step all the searchers"""
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
456
        newly_seen_common = set(common_searcher.step())
457
        newly_seen_unique = set()
458
        for searcher in unique_tip_searchers:
459
            next = set(searcher.step())
460
            next.update(unique_searcher.find_seen_ancestors(next))
461
            next.update(common_searcher.find_seen_ancestors(next))
462
            for alt_searcher in unique_tip_searchers:
463
                if alt_searcher is searcher:
464
                    continue
465
                next.update(alt_searcher.find_seen_ancestors(next))
466
            searcher.start_searching(next)
467
            newly_seen_unique.update(next)
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
468
        return newly_seen_common, newly_seen_unique
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
469
470
    def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
471
                                         all_unique_searcher,
472
                                         newly_seen_unique, step_all_unique):
473
        """Find nodes that are common to all unique_tip_searchers.
474
475
        If it is time, step the all_unique_searcher, and add its nodes to the
476
        result.
477
        """
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
478
        common_to_all_unique_nodes = newly_seen_unique.copy()
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
479
        for searcher in unique_tip_searchers:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
480
            common_to_all_unique_nodes.intersection_update(searcher.seen)
481
        common_to_all_unique_nodes.intersection_update(
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
482
                                    all_unique_searcher.seen)
483
        # Step all-unique less frequently than the other searchers.
484
        # In the common case, we don't need to spider out far here, so
485
        # avoid doing extra work.
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
486
        if step_all_unique:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
487
            tstart = time.clock()
488
            nodes = all_unique_searcher.step()
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
489
            common_to_all_unique_nodes.update(nodes)
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
490
            if 'graph' in debug.debug_flags:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
491
                tdelta = time.clock() - tstart
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
492
                trace.mutter('all_unique_searcher step() took %.3fs'
493
                             'for %d nodes (%d total), iteration: %s',
494
                             tdelta, len(nodes), len(all_unique_searcher.seen),
495
                             all_unique_searcher._iterations)
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
496
        return common_to_all_unique_nodes
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
497
498
    def _collapse_unique_searchers(self, unique_tip_searchers,
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
499
                                   common_to_all_unique_nodes):
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
500
        """Combine searchers that are searching the same tips.
501
502
        When two searchers are searching the same tips, we can stop one of the
503
        searchers. We also know that the maximal set of common ancestors is the
504
        intersection of the two original searchers.
505
506
        :return: A list of searchers that are searching unique nodes.
507
        """
508
        # Filter out searchers that don't actually search different
509
        # nodes. We already have the ancestry intersection for them
510
        unique_search_tips = {}
511
        for searcher in unique_tip_searchers:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
512
            stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
513
            will_search_set = frozenset(searcher._next_query)
514
            if not will_search_set:
515
                if 'graph' in debug.debug_flags:
516
                    trace.mutter('Unique searcher %s was stopped.'
517
                                 ' (%s iterations) %d nodes stopped',
518
                                 searcher._label,
519
                                 searcher._iterations,
520
                                 len(stopped))
521
            elif will_search_set not in unique_search_tips:
522
                # This searcher is searching a unique set of nodes, let it
523
                unique_search_tips[will_search_set] = [searcher]
524
            else:
525
                unique_search_tips[will_search_set].append(searcher)
526
        # TODO: it might be possible to collapse searchers faster when they
527
        #       only have *some* search tips in common.
528
        next_unique_searchers = []
529
        for searchers in unique_search_tips.itervalues():
530
            if len(searchers) == 1:
531
                # Searching unique tips, go for it
532
                next_unique_searchers.append(searchers[0])
533
            else:
534
                # These searchers have started searching the same tips, we
535
                # don't need them to cover the same ground. The
536
                # intersection of their ancestry won't change, so create a
537
                # new searcher, combining their histories.
538
                next_searcher = searchers[0]
539
                for searcher in searchers[1:]:
540
                    next_searcher.seen.intersection_update(searcher.seen)
541
                if 'graph' in debug.debug_flags:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
542
                    trace.mutter('Combining %d searchers into a single'
543
                                 ' searcher searching %d nodes with'
544
                                 ' %d ancestry',
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
545
                                 len(searchers),
546
                                 len(next_searcher._next_query),
547
                                 len(next_searcher.seen))
548
                next_unique_searchers.append(next_searcher)
549
        return next_unique_searchers
550
551
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
552
                             unique_tip_searchers, common_searcher):
553
        """Steps 5-8 of find_unique_ancestors.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
554
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
555
        This function returns when common_searcher has stopped searching for
556
        more nodes.
557
        """
558
        # We step the ancestor_all_unique searcher only every
559
        # STEP_UNIQUE_SEARCHER_EVERY steps.
560
        step_all_unique_counter = 0
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
561
        # While we still have common nodes to search
562
        while common_searcher._next_query:
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
563
            (newly_seen_common,
564
             newly_seen_unique) = self._step_unique_and_common_searchers(
565
                common_searcher, unique_tip_searchers, unique_searcher)
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
566
            # These nodes are common ancestors of all unique nodes
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
567
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
568
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
569
                step_all_unique_counter==0)
570
            step_all_unique_counter = ((step_all_unique_counter + 1)
571
                                       % STEP_UNIQUE_SEARCHER_EVERY)
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
572
573
            if newly_seen_common:
574
                # If a 'common' node is an ancestor of all unique searchers, we
575
                # can stop searching it.
576
                common_searcher.stop_searching_any(
577
                    all_unique_searcher.seen.intersection(newly_seen_common))
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
578
            if common_to_all_unique_nodes:
579
                common_to_all_unique_nodes.update(
3377.4.7 by John Arbash Meinel
Small documentation and code wrapping cleanup
580
                    common_searcher.find_seen_ancestors(
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
581
                        common_to_all_unique_nodes))
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
582
                # The all_unique searcher can start searching the common nodes
583
                # but everyone else can stop.
3377.4.7 by John Arbash Meinel
Small documentation and code wrapping cleanup
584
                # This is the sort of thing where we would like to not have it
585
                # start_searching all of the nodes, but only mark all of them
586
                # as seen, and have it search only the actual tips. Otherwise
587
                # it is another get_parent_map() traversal for it to figure out
588
                # what we already should know.
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
589
                all_unique_searcher.start_searching(common_to_all_unique_nodes)
590
                common_searcher.stop_searching_any(common_to_all_unique_nodes)
3377.4.4 by John Arbash Meinel
Restore the previous code, but bring in a couple changes. Including an update to have lsprof show where the time is spent.
591
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
592
            next_unique_searchers = self._collapse_unique_searchers(
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
593
                unique_tip_searchers, common_to_all_unique_nodes)
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
594
            if len(unique_tip_searchers) != len(next_unique_searchers):
595
                if 'graph' in debug.debug_flags:
3377.4.8 by John Arbash Meinel
Final tweaks from Ian
596
                    trace.mutter('Collapsed %d unique searchers => %d'
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
597
                                 ' at %s iterations',
598
                                 len(unique_tip_searchers),
599
                                 len(next_unique_searchers),
600
                                 all_unique_searcher._iterations)
601
            unique_tip_searchers = next_unique_searchers
3377.3.21 by John Arbash Meinel
Simple brute-force implementation of find_unique_ancestors
602
3172.1.2 by Robert Collins
Parent Providers should now implement ``get_parent_map`` returning a
603
    def get_parent_map(self, revisions):
604
        """Get a map of key:parent_list for revisions.
605
606
        This implementation delegates to get_parents, for old parent_providers
607
        that do not supply get_parent_map.
608
        """
609
        result = {}
610
        for rev, parents in self.get_parents(revisions):
611
            if parents is not None:
612
                result[rev] = parents
613
        return result
614
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
615
    def _make_breadth_first_searcher(self, revisions):
616
        return _BreadthFirstSearcher(revisions, self)
617
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
618
    def _find_border_ancestors(self, revisions):
2490.2.12 by Aaron Bentley
Improve documentation
619
        """Find common ancestors with at least one uncommon descendant.
620
621
        Border ancestors are identified using a breadth-first
622
        search starting at the bottom of the graph.  Searches are stopped
623
        whenever a node or one of its descendants is determined to be common.
624
625
        This will scale with the number of uncommon ancestors.
2490.2.25 by Aaron Bentley
Update from review
626
627
        As well as the border ancestors, a set of seen common ancestors and a
628
        list of sets of seen ancestors for each input revision is returned.
629
        This allows calculation of graph difference from the results of this
630
        operation.
2490.2.12 by Aaron Bentley
Improve documentation
631
        """
2490.2.28 by Aaron Bentley
Fix handling of null revision
632
        if None in revisions:
633
            raise errors.InvalidRevisionId(None, self)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
634
        common_ancestors = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
635
        searchers = [self._make_breadth_first_searcher([r])
636
                     for r in revisions]
637
        active_searchers = searchers[:]
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
638
        border_ancestors = set()
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
639
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
640
        while True:
641
            newly_seen = set()
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
642
            for searcher in searchers:
643
                new_ancestors = searcher.step()
644
                if new_ancestors:
645
                    newly_seen.update(new_ancestors)
646
            new_common = set()
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
647
            for revision in newly_seen:
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
648
                if revision in common_ancestors:
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
649
                    # Not a border ancestor because it was seen as common
650
                    # already
651
                    new_common.add(revision)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
652
                    continue
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
653
                for searcher in searchers:
654
                    if revision not in searcher.seen:
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
655
                        break
656
                else:
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
657
                    # This is a border because it is a first common that we see
658
                    # after walking for a while.
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
659
                    border_ancestors.add(revision)
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
660
                    new_common.add(revision)
661
            if new_common:
662
                for searcher in searchers:
663
                    new_common.update(searcher.find_seen_ancestors(new_common))
664
                for searcher in searchers:
665
                    searcher.start_searching(new_common)
666
                common_ancestors.update(new_common)
667
668
            # Figure out what the searchers will be searching next, and if
669
            # there is only 1 set being searched, then we are done searching,
670
            # since all searchers would have to be searching the same data,
671
            # thus it *must* be in common.
672
            unique_search_sets = set()
673
            for searcher in searchers:
674
                will_search_set = frozenset(searcher._next_query)
675
                if will_search_set not in unique_search_sets:
676
                    # This searcher is searching a unique set of nodes, let it
677
                    unique_search_sets.add(will_search_set)
678
679
            if len(unique_search_sets) == 1:
680
                nodes = unique_search_sets.pop()
681
                uncommon_nodes = nodes.difference(common_ancestors)
3376.2.14 by Martin Pool
Remove recently-introduced assert statements
682
                if uncommon_nodes:
683
                    raise AssertionError("Somehow we ended up converging"
684
                                         " without actually marking them as"
685
                                         " in common."
686
                                         "\nStart_nodes: %s"
687
                                         "\nuncommon_nodes: %s"
688
                                         % (revisions, uncommon_nodes))
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
689
                break
690
        return border_ancestors, common_ancestors, searchers
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
691
2776.3.1 by Robert Collins
* Deprecated method ``find_previous_heads`` on
692
    def heads(self, keys):
693
        """Return the heads from amongst keys.
694
695
        This is done by searching the ancestries of each key.  Any key that is
696
        reachable from another key is not returned; all the others are.
697
698
        This operation scales with the relative depth between any two keys. If
699
        any two keys are completely disconnected all ancestry of both sides
700
        will be retrieved.
701
702
        :param keys: An iterable of keys.
2776.1.4 by Robert Collins
Trivial review feedback changes.
703
        :return: A set of the heads. Note that as a set there is no ordering
704
            information. Callers will need to filter their input to create
705
            order if they need it.
2490.2.12 by Aaron Bentley
Improve documentation
706
        """
2776.1.4 by Robert Collins
Trivial review feedback changes.
707
        candidate_heads = set(keys)
3052.5.5 by John Arbash Meinel
Special case Graph.heads() for NULL_REVISION rather than is_ancestor.
708
        if revision.NULL_REVISION in candidate_heads:
709
            # NULL_REVISION is only a head if it is the only entry
710
            candidate_heads.remove(revision.NULL_REVISION)
711
            if not candidate_heads:
712
                return set([revision.NULL_REVISION])
2850.2.1 by Robert Collins
(robertc) Special case the zero-or-no-heads case for Graph.heads(). (Robert Collins)
713
        if len(candidate_heads) < 2:
714
            return candidate_heads
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
715
        searchers = dict((c, self._make_breadth_first_searcher([c]))
2776.1.4 by Robert Collins
Trivial review feedback changes.
716
                          for c in candidate_heads)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
717
        active_searchers = dict(searchers)
718
        # skip over the actual candidate for each searcher
719
        for searcher in active_searchers.itervalues():
1551.15.81 by Aaron Bentley
Remove testing code
720
            searcher.next()
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
721
        # The common walker finds nodes that are common to two or more of the
722
        # input keys, so that we don't access all history when a currently
723
        # uncommon search point actually meets up with something behind a
724
        # common search point. Common search points do not keep searches
725
        # active; they just allow us to make searches inactive without
726
        # accessing all history.
727
        common_walker = self._make_breadth_first_searcher([])
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
728
        while len(active_searchers) > 0:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
729
            ancestors = set()
730
            # advance searches
731
            try:
732
                common_walker.next()
733
            except StopIteration:
2921.3.4 by Robert Collins
Review feedback.
734
                # No common points being searched at this time.
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
735
                pass
1551.15.78 by Aaron Bentley
Fix KeyError in filter_candidate_lca
736
            for candidate in active_searchers.keys():
737
                try:
738
                    searcher = active_searchers[candidate]
739
                except KeyError:
740
                    # rare case: we deleted candidate in a previous iteration
741
                    # through this for loop, because it was determined to be
742
                    # a descendant of another candidate.
743
                    continue
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
744
                try:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
745
                    ancestors.update(searcher.next())
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
746
                except StopIteration:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
747
                    del active_searchers[candidate]
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
748
                    continue
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
749
            # process found nodes
750
            new_common = set()
751
            for ancestor in ancestors:
752
                if ancestor in candidate_heads:
753
                    candidate_heads.remove(ancestor)
754
                    del searchers[ancestor]
755
                    if ancestor in active_searchers:
756
                        del active_searchers[ancestor]
757
                # it may meet up with a known common node
2921.3.4 by Robert Collins
Review feedback.
758
                if ancestor in common_walker.seen:
759
                    # some searcher has encountered our known common nodes:
760
                    # just stop it
761
                    ancestor_set = set([ancestor])
762
                    for searcher in searchers.itervalues():
763
                        searcher.stop_searching_any(ancestor_set)
764
                else:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
765
                    # or it may have been just reached by all the searchers:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
766
                    for searcher in searchers.itervalues():
767
                        if ancestor not in searcher.seen:
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
768
                            break
769
                    else:
2921.3.4 by Robert Collins
Review feedback.
770
                        # The final active searcher has just reached this node,
771
                        # making it be known as a descendant of all candidates,
772
                        # so we can stop searching it, and any seen ancestors
773
                        new_common.add(ancestor)
774
                        for searcher in searchers.itervalues():
775
                            seen_ancestors =\
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
776
                                searcher.find_seen_ancestors([ancestor])
2921.3.4 by Robert Collins
Review feedback.
777
                            searcher.stop_searching_any(seen_ancestors)
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
778
            common_walker.start_searching(new_common)
2776.1.4 by Robert Collins
Trivial review feedback changes.
779
        return candidate_heads
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
780
3514.2.8 by John Arbash Meinel
The insertion ordering into the weave has an impact on conflicts.
781
    def find_merge_order(self, tip_revision_id, lca_revision_ids):
782
        """Find the order that each revision was merged into tip.
783
784
        This basically just walks backwards with a stack, and walks left-first
785
        until it finds a node to stop.
786
        """
787
        if len(lca_revision_ids) == 1:
788
            return list(lca_revision_ids)
789
        looking_for = set(lca_revision_ids)
790
        # TODO: Is there a way we could do this "faster" by batching up the
791
        # get_parent_map requests?
792
        # TODO: Should we also be culling the ancestry search right away? We
793
        # could add looking_for to the "stop" list, and walk their
794
        # ancestry in batched mode. The flip side is it might mean we walk a
795
        # lot of "stop" nodes, rather than only the minimum.
796
        # Then again, without it we may trace back into ancestry we could have
797
        # stopped early.
798
        stack = [tip_revision_id]
799
        found = []
800
        stop = set()
801
        while stack and looking_for:
802
            next = stack.pop()
803
            stop.add(next)
804
            if next in looking_for:
805
                found.append(next)
806
                looking_for.remove(next)
807
                if len(looking_for) == 1:
808
                    found.append(looking_for.pop())
809
                    break
810
                continue
811
            parent_ids = self.get_parent_map([next]).get(next, None)
812
            if not parent_ids: # Ghost, nothing to search here
813
                continue
814
            for parent_id in reversed(parent_ids):
815
                # TODO: (performance) We see the parent at this point, but we
816
                #       wait to mark it until later to make sure we get left
817
                #       parents before right parents. However, instead of
818
                #       waiting until we have traversed enough parents, we
819
                #       could instead note that we've found it, and once all
820
                #       parents are in the stack, just reverse iterate the
821
                #       stack for them.
822
                if parent_id not in stop:
823
                    # this will need to be searched
824
                    stack.append(parent_id)
825
                stop.add(parent_id)
826
        return found
827
1551.19.10 by Aaron Bentley
Merge now warns when it encounters a criss-cross
828
    def find_unique_lca(self, left_revision, right_revision,
829
                        count_steps=False):
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
830
        """Find a unique LCA.
831
832
        Find lowest common ancestors.  If there is no unique  common
833
        ancestor, find the lowest common ancestors of those ancestors.
834
835
        Iteration stops when a unique lowest common ancestor is found.
836
        The graph origin is necessarily a unique lowest common ancestor.
2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
837
838
        Note that None is not an acceptable substitute for NULL_REVISION.
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
839
        in the input for this method.
1551.19.12 by Aaron Bentley
Add documentation for the count_steps parameter of Graph.find_unique_lca
840
841
        :param count_steps: If True, the return value will be a tuple of
842
            (unique_lca, steps) where steps is the number of times that
843
            find_lca was run.  If False, only unique_lca is returned.
2490.2.3 by Aaron Bentley
Implement new merge base picker
844
        """
845
        revisions = [left_revision, right_revision]
1551.19.10 by Aaron Bentley
Merge now warns when it encounters a criss-cross
846
        steps = 0
2490.2.3 by Aaron Bentley
Implement new merge base picker
847
        while True:
1551.19.10 by Aaron Bentley
Merge now warns when it encounters a criss-cross
848
            steps += 1
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
849
            lca = self.find_lca(*revisions)
850
            if len(lca) == 1:
1551.19.10 by Aaron Bentley
Merge now warns when it encounters a criss-cross
851
                result = lca.pop()
852
                if count_steps:
853
                    return result, steps
854
                else:
855
                    return result
2520.4.104 by Aaron Bentley
Avoid infinite loop when there is no unique lca
856
            if len(lca) == 0:
857
                raise errors.NoCommonAncestor(left_revision, right_revision)
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
858
            revisions = lca
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
859
3228.4.4 by John Arbash Meinel
Change iter_ancestry to take a group instead of a single node,
860
    def iter_ancestry(self, revision_ids):
3228.4.2 by John Arbash Meinel
Add a Graph.iter_ancestry()
861
        """Iterate the ancestry of this revision.
862
3228.4.4 by John Arbash Meinel
Change iter_ancestry to take a group instead of a single node,
863
        :param revision_ids: Nodes to start the search
3228.4.2 by John Arbash Meinel
Add a Graph.iter_ancestry()
864
        :return: Yield tuples mapping a revision_id to its parents for the
865
            ancestry of revision_id.
3228.4.10 by John Arbash Meinel
Respond to abentley's review comments.
866
            Ghosts will be returned with None as their parents, and nodes
3228.4.4 by John Arbash Meinel
Change iter_ancestry to take a group instead of a single node,
867
            with no parents will have NULL_REVISION as their only parent. (As
868
            defined by get_parent_map.)
3228.4.10 by John Arbash Meinel
Respond to abentley's review comments.
869
            There will also be a node for (NULL_REVISION, ())
3228.4.2 by John Arbash Meinel
Add a Graph.iter_ancestry()
870
        """
3228.4.4 by John Arbash Meinel
Change iter_ancestry to take a group instead of a single node,
871
        pending = set(revision_ids)
3228.4.2 by John Arbash Meinel
Add a Graph.iter_ancestry()
872
        processed = set()
873
        while pending:
874
            processed.update(pending)
875
            next_map = self.get_parent_map(pending)
876
            next_pending = set()
877
            for item in next_map.iteritems():
878
                yield item
879
                next_pending.update(p for p in item[1] if p not in processed)
880
            ghosts = pending.difference(next_map)
881
            for ghost in ghosts:
3228.4.10 by John Arbash Meinel
Respond to abentley's review comments.
882
                yield (ghost, None)
3228.4.2 by John Arbash Meinel
Add a Graph.iter_ancestry()
883
            pending = next_pending
884
2490.2.31 by Aaron Bentley
Fix iter_topo_order to permit un-included parents
885
    def iter_topo_order(self, revisions):
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
886
        """Iterate through the input revisions in topological order.
887
888
        This sorting only ensures that parents come before their children.
889
        An ancestor may sort after a descendant if the relationship is not
890
        visible in the supplied list of revisions.
891
        """
3099.3.3 by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map()
892
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
2490.2.34 by Aaron Bentley
Update NEWS and change implementation to return an iterator
893
        return sorter.iter_topo_order()
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
894
2653.2.1 by Aaron Bentley
Implement Graph.is_ancestor
895
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
2653.2.5 by Aaron Bentley
Update to clarify algorithm
896
        """Determine whether a revision is an ancestor of another.
897
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
898
        We answer this using heads() as heads() has the logic to perform the
3078.2.6 by Ian Clatworthy
fix efficiency of local commit detection as recommended by jameinel's review
899
        smallest number of parent lookups to determine the ancestral
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
900
        relationship between N revisions.
2653.2.5 by Aaron Bentley
Update to clarify algorithm
901
        """
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
902
        return set([candidate_descendant]) == self.heads(
903
            [candidate_ancestor, candidate_descendant])
2653.2.1 by Aaron Bentley
Implement Graph.is_ancestor
904
3921.3.5 by Marius Kruger
extract graph.is_between from builtins.cmd_tags.run, and test it
905
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
906
        """Determine whether a revision is between two others.
907
908
        returns true if and only if:
909
        lower_bound_revid <= revid <= upper_bound_revid
910
        """
911
        return ((upper_bound_revid is None or
912
                    self.is_ancestor(revid, upper_bound_revid)) and
913
               (lower_bound_revid is None or
914
                    self.is_ancestor(lower_bound_revid, revid)))
915
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
916
    def _search_for_extra_common(self, common, searchers):
917
        """Make sure that unique nodes are genuinely unique.
918
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
919
        After _find_border_ancestors, all nodes marked "common" are indeed
920
        common. Some of the nodes considered unique are not, due to history
921
        shortcuts stopping the searches early.
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
922
923
        We know that we have searched enough when all common search tips are
924
        descended from all unique (uncommon) nodes because we know that a node
925
        cannot be an ancestor of its own ancestor.
926
927
        :param common: A set of common nodes
928
        :param searchers: The searchers returned from _find_border_ancestors
929
        :return: None
930
        """
931
        # Basic algorithm...
932
        #   A) The passed in searchers should all be on the same tips, thus
933
        #      they should be considered the "common" searchers.
934
        #   B) We find the difference between the searchers, these are the
935
        #      "unique" nodes for each side.
936
        #   C) We do a quick culling so that we only start searching from the
937
        #      more interesting unique nodes. (A unique ancestor is more
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
938
        #      interesting than any of its children.)
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
939
        #   D) We start searching for ancestors common to all unique nodes.
940
        #   E) We have the common searchers stop searching any ancestors of
941
        #      nodes found by (D)
942
        #   F) When there are no more common search tips, we stop
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
943
944
        # TODO: We need a way to remove unique_searchers when they overlap with
945
        #       other unique searchers.
3376.2.14 by Martin Pool
Remove recently-introduced assert statements
946
        if len(searchers) != 2:
947
            raise NotImplementedError(
948
                "Algorithm not yet implemented for > 2 searchers")
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
949
        common_searchers = searchers
950
        left_searcher = searchers[0]
951
        right_searcher = searchers[1]
3377.3.15 by John Arbash Meinel
minor update
952
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
3377.3.17 by John Arbash Meinel
Keep track of the intersection of unique ancestry,
953
        if not unique: # No unique nodes, nothing to do
954
            return
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
955
        total_unique = len(unique)
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
956
        unique = self._remove_simple_descendants(unique,
957
                    self.get_parent_map(unique))
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
958
        simple_unique = len(unique)
3377.3.14 by John Arbash Meinel
Take another tack on _search_for_extra
959
960
        unique_searchers = []
961
        for revision_id in unique:
3377.3.15 by John Arbash Meinel
minor update
962
            if revision_id in left_searcher.seen:
3377.3.14 by John Arbash Meinel
Take another tack on _search_for_extra
963
                parent_searcher = left_searcher
964
            else:
965
                parent_searcher = right_searcher
966
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
967
            if not revs_to_search: # XXX: This shouldn't be possible
968
                revs_to_search = [revision_id]
3377.3.15 by John Arbash Meinel
minor update
969
            searcher = self._make_breadth_first_searcher(revs_to_search)
970
            # We don't care about the starting nodes.
971
            searcher.step()
972
            unique_searchers.append(searcher)
3377.3.14 by John Arbash Meinel
Take another tack on _search_for_extra
973
3377.3.16 by John Arbash Meinel
small cleanups
974
        # possible todo: aggregate the common searchers into a single common
975
        #   searcher, just make sure that we include the nodes into the .seen
976
        #   properties of the original searchers
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
977
3377.3.17 by John Arbash Meinel
Keep track of the intersection of unique ancestry,
978
        ancestor_all_unique = None
979
        for searcher in unique_searchers:
980
            if ancestor_all_unique is None:
981
                ancestor_all_unique = set(searcher.seen)
982
            else:
983
                ancestor_all_unique = ancestor_all_unique.intersection(
984
                                            searcher.seen)
985
3377.3.23 by John Arbash Meinel
Implement find_unique_ancestors using more explicit graph searching.
986
        trace.mutter('Started %s unique searchers for %s unique revisions',
987
                     simple_unique, total_unique)
3377.3.19 by John Arbash Meinel
Start culling unique searchers once they converge.
988
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
989
        while True: # If we have no more nodes we have nothing to do
990
            newly_seen_common = set()
991
            for searcher in common_searchers:
992
                newly_seen_common.update(searcher.step())
993
            newly_seen_unique = set()
994
            for searcher in unique_searchers:
995
                newly_seen_unique.update(searcher.step())
996
            new_common_unique = set()
997
            for revision in newly_seen_unique:
998
                for searcher in unique_searchers:
999
                    if revision not in searcher.seen:
1000
                        break
1001
                else:
1002
                    # This is a border because it is a first common that we see
1003
                    # after walking for a while.
1004
                    new_common_unique.add(revision)
1005
            if newly_seen_common:
1006
                # These are nodes descended from one of the 'common' searchers.
1007
                # Make sure all searchers are on the same page
1008
                for searcher in common_searchers:
3377.3.16 by John Arbash Meinel
small cleanups
1009
                    newly_seen_common.update(
1010
                        searcher.find_seen_ancestors(newly_seen_common))
3377.3.14 by John Arbash Meinel
Take another tack on _search_for_extra
1011
                # We start searching the whole ancestry. It is a bit wasteful,
1012
                # though. We really just want to mark all of these nodes as
1013
                # 'seen' and then start just the tips. However, it requires a
1014
                # get_parent_map() call to figure out the tips anyway, and all
1015
                # redundant requests should be fairly fast.
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1016
                for searcher in common_searchers:
1017
                    searcher.start_searching(newly_seen_common)
3377.3.13 by John Arbash Meinel
Change _search_for_extra_common slightly.
1018
3377.3.17 by John Arbash Meinel
Keep track of the intersection of unique ancestry,
1019
                # If a 'common' node is an ancestor of all unique searchers, we
3377.3.13 by John Arbash Meinel
Change _search_for_extra_common slightly.
1020
                # can stop searching it.
3377.3.17 by John Arbash Meinel
Keep track of the intersection of unique ancestry,
1021
                stop_searching_common = ancestor_all_unique.intersection(
1022
                                            newly_seen_common)
3377.3.13 by John Arbash Meinel
Change _search_for_extra_common slightly.
1023
                if stop_searching_common:
1024
                    for searcher in common_searchers:
1025
                        searcher.stop_searching_any(stop_searching_common)
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1026
            if new_common_unique:
3377.3.20 by John Arbash Meinel
comment cleanups.
1027
                # We found some ancestors that are common
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
1028
                for searcher in unique_searchers:
3377.3.16 by John Arbash Meinel
small cleanups
1029
                    new_common_unique.update(
1030
                        searcher.find_seen_ancestors(new_common_unique))
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1031
                # Since these are common, we can grab another set of ancestors
1032
                # that we have seen
1033
                for searcher in common_searchers:
3377.3.16 by John Arbash Meinel
small cleanups
1034
                    new_common_unique.update(
1035
                        searcher.find_seen_ancestors(new_common_unique))
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1036
1037
                # We can tell all of the unique searchers to start at these
1038
                # nodes, and tell all of the common searchers to *stop*
1039
                # searching these nodes
1040
                for searcher in unique_searchers:
1041
                    searcher.start_searching(new_common_unique)
1042
                for searcher in common_searchers:
1043
                    searcher.stop_searching_any(new_common_unique)
3377.3.17 by John Arbash Meinel
Keep track of the intersection of unique ancestry,
1044
                ancestor_all_unique.update(new_common_unique)
3377.3.19 by John Arbash Meinel
Start culling unique searchers once they converge.
1045
3377.3.20 by John Arbash Meinel
comment cleanups.
1046
                # Filter out searchers that don't actually search different
1047
                # nodes. We already have the ancestry intersection for them
3377.3.19 by John Arbash Meinel
Start culling unique searchers once they converge.
1048
                next_unique_searchers = []
1049
                unique_search_sets = set()
1050
                for searcher in unique_searchers:
1051
                    will_search_set = frozenset(searcher._next_query)
1052
                    if will_search_set not in unique_search_sets:
1053
                        # This searcher is searching a unique set of nodes, let it
1054
                        unique_search_sets.add(will_search_set)
1055
                        next_unique_searchers.append(searcher)
1056
                unique_searchers = next_unique_searchers
3377.3.2 by John Arbash Meinel
find_difference is fixed by updating _find_border_ancestors.... is that reasonable?
1057
            for searcher in common_searchers:
1058
                if searcher._next_query:
1059
                    break
1060
            else:
1061
                # All common searcher have stopped searching
3377.3.16 by John Arbash Meinel
small cleanups
1062
                return
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1063
1064
    def _remove_simple_descendants(self, revisions, parent_map):
1065
        """remove revisions which are children of other ones in the set
1066
1067
        This doesn't do any graph searching, it just checks the immediate
1068
        parent_map to find if there are any children which can be removed.
1069
1070
        :param revisions: A set of revision_ids
1071
        :return: A set of revision_ids with the children removed
1072
        """
1073
        simple_ancestors = revisions.copy()
1074
        # TODO: jam 20071214 we *could* restrict it to searching only the
1075
        #       parent_map of revisions already present in 'revisions', but
1076
        #       considering the general use case, I think this is actually
1077
        #       better.
1078
1079
        # This is the same as the following loop. I don't know that it is any
1080
        # faster.
1081
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1082
        ##     if p_ids is not None and revisions.intersection(p_ids))
1083
        ## return simple_ancestors
1084
1085
        # Yet Another Way, invert the parent map (which can be cached)
1086
        ## descendants = {}
1087
        ## for revision_id, parent_ids in parent_map.iteritems():
1088
        ##   for p_id in parent_ids:
1089
        ##       descendants.setdefault(p_id, []).append(revision_id)
1090
        ## for revision in revisions.intersection(descendants):
1091
        ##   simple_ancestors.difference_update(descendants[revision])
1092
        ## return simple_ancestors
1093
        for revision, parent_ids in parent_map.iteritems():
1094
            if parent_ids is None:
1095
                continue
1096
            for parent_id in parent_ids:
1097
                if parent_id in revisions:
1098
                    # This node has a parent present in the set, so we can
1099
                    # remove it
1100
                    simple_ancestors.discard(revision)
1101
                    break
1102
        return simple_ancestors
1103
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1104
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
1105
class HeadsCache(object):
1106
    """A cache of results for graph heads calls."""
1107
1108
    def __init__(self, graph):
1109
        self.graph = graph
1110
        self._heads = {}
1111
1112
    def heads(self, keys):
1113
        """Return the heads of keys.
1114
2911.4.3 by Robert Collins
Make the contract of HeadsCache.heads() more clear.
1115
        This matches the API of Graph.heads(), specifically the return value is
1116
        a set which can be mutated, and ordering of the input is not preserved
1117
        in the output.
1118
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
1119
        :see also: Graph.heads.
1120
        :param keys: The keys to calculate heads for.
1121
        :return: A set containing the heads, which may be mutated without
1122
            affecting future lookups.
1123
        """
2911.4.2 by Robert Collins
Make HeadsCache actually work.
1124
        keys = frozenset(keys)
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
1125
        try:
1126
            return set(self._heads[keys])
1127
        except KeyError:
1128
            heads = self.graph.heads(keys)
1129
            self._heads[keys] = heads
1130
            return set(heads)
1131
1132
3224.1.20 by John Arbash Meinel
Reduce the number of cache misses by caching known heads answers
1133
class FrozenHeadsCache(object):
1134
    """Cache heads() calls, assuming the caller won't modify them."""
1135
1136
    def __init__(self, graph):
1137
        self.graph = graph
1138
        self._heads = {}
1139
1140
    def heads(self, keys):
1141
        """Return the heads of keys.
1142
3224.1.24 by John Arbash Meinel
Fix up docstring since FrozenHeadsCache doesn't let you mutate the result.
1143
        Similar to Graph.heads(). The main difference is that the return value
1144
        is a frozen set which cannot be mutated.
3224.1.20 by John Arbash Meinel
Reduce the number of cache misses by caching known heads answers
1145
1146
        :see also: Graph.heads.
1147
        :param keys: The keys to calculate heads for.
3224.1.24 by John Arbash Meinel
Fix up docstring since FrozenHeadsCache doesn't let you mutate the result.
1148
        :return: A frozenset containing the heads.
3224.1.20 by John Arbash Meinel
Reduce the number of cache misses by caching known heads answers
1149
        """
1150
        keys = frozenset(keys)
1151
        try:
1152
            return self._heads[keys]
1153
        except KeyError:
1154
            heads = frozenset(self.graph.heads(keys))
1155
            self._heads[keys] = heads
1156
            return heads
1157
1158
    def cache(self, keys, heads):
1159
        """Store a known value."""
1160
        self._heads[frozenset(keys)] = frozenset(heads)
1161
1162
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
1163
class _BreadthFirstSearcher(object):
2921.3.4 by Robert Collins
Review feedback.
1164
    """Parallel search breadth-first the ancestry of revisions.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
1165
1166
    This class implements the iterator protocol, but additionally
1167
    1. provides a set of seen ancestors, and
1168
    2. allows some ancestries to be unsearched, via stop_searching_any
1169
    """
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1170
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
1171
    def __init__(self, revisions, parents_provider):
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1172
        self._iterations = 0
1173
        self._next_query = set(revisions)
1174
        self.seen = set()
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1175
        self._started_keys = set(self._next_query)
1176
        self._stopped_keys = set()
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
1177
        self._parents_provider = parents_provider
3177.3.3 by Robert Collins
Review feedback.
1178
        self._returning = 'next_with_ghosts'
3184.1.2 by Robert Collins
Add tests for starting and stopping searches in combination with get_recipe.
1179
        self._current_present = set()
1180
        self._current_ghosts = set()
1181
        self._current_parents = {}
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1182
1183
    def __repr__(self):
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1184
        if self._iterations:
1185
            prefix = "searching"
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
1186
        else:
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1187
            prefix = "starting"
1188
        search = '%s=%r' % (prefix, list(self._next_query))
1189
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1190
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1191
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1192
    def get_result(self):
1193
        """Get a SearchResult for the current state of this searcher.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1194
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1195
        :return: A SearchResult for this search so far. The SearchResult is
1196
            static - the search can be advanced and the search result will not
1197
            be invalidated or altered.
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1198
        """
1199
        if self._returning == 'next':
1200
            # We have to know the current nodes children to be able to list the
1201
            # exclude keys for them. However, while we could have a second
1202
            # look-ahead result buffer and shuffle things around, this method
1203
            # is typically only called once per search - when memoising the
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1204
            # results of the search.
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1205
            found, ghosts, next, parents = self._do_query(self._next_query)
1206
            # pretend we didn't query: perhaps we should tweak _do_query to be
1207
            # entirely stateless?
1208
            self.seen.difference_update(next)
3184.1.3 by Robert Collins
Automatically exclude ghosts.
1209
            next_query = next.union(ghosts)
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1210
        else:
1211
            next_query = self._next_query
3184.1.5 by Robert Collins
Record the number of found revisions for cross checking.
1212
        excludes = self._stopped_keys.union(next_query)
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1213
        included_keys = self.seen.difference(excludes)
1214
        return SearchResult(self._started_keys, excludes, len(included_keys),
1215
            included_keys)
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1216
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1217
    def step(self):
1218
        try:
1219
            return self.next()
1220
        except StopIteration:
1221
            return ()
1222
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1223
    def next(self):
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
1224
        """Return the next ancestors of this revision.
1225
2490.2.12 by Aaron Bentley
Improve documentation
1226
        Ancestors are returned in the order they are seen in a breadth-first
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1227
        traversal.  No ancestor will be returned more than once. Ancestors are
1228
        returned before their parentage is queried, so ghosts and missing
1229
        revisions (including the start revisions) are included in the result.
1230
        This can save a round trip in LCA style calculation by allowing
1231
        convergence to be detected without reading the data for the revision
1232
        the convergence occurs on.
1233
1234
        :return: A set of revision_ids.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
1235
        """
3177.3.3 by Robert Collins
Review feedback.
1236
        if self._returning != 'next':
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1237
            # switch to returning the query, not the results.
3177.3.3 by Robert Collins
Review feedback.
1238
            self._returning = 'next'
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1239
            self._iterations += 1
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1240
        else:
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1241
            self._advance()
1242
        if len(self._next_query) == 0:
1243
            raise StopIteration()
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1244
        # We have seen what we're querying at this point as we are returning
1245
        # the query, not the results.
1246
        self.seen.update(self._next_query)
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1247
        return self._next_query
1248
1249
    def next_with_ghosts(self):
1250
        """Return the next found ancestors, with ghosts split out.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1251
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1252
        Ancestors are returned in the order they are seen in a breadth-first
1253
        traversal.  No ancestor will be returned more than once. Ancestors are
3177.3.3 by Robert Collins
Review feedback.
1254
        returned only after asking for their parents, which allows us to detect
1255
        which revisions are ghosts and which are not.
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1256
1257
        :return: A tuple with (present ancestors, ghost ancestors) sets.
1258
        """
3177.3.3 by Robert Collins
Review feedback.
1259
        if self._returning != 'next_with_ghosts':
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1260
            # switch to returning the results, not the current query.
3177.3.3 by Robert Collins
Review feedback.
1261
            self._returning = 'next_with_ghosts'
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1262
            self._advance()
1263
        if len(self._next_query) == 0:
1264
            raise StopIteration()
1265
        self._advance()
1266
        return self._current_present, self._current_ghosts
1267
1268
    def _advance(self):
1269
        """Advance the search.
1270
1271
        Updates self.seen, self._next_query, self._current_present,
3177.3.3 by Robert Collins
Review feedback.
1272
        self._current_ghosts, self._current_parents and self._iterations.
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1273
        """
1274
        self._iterations += 1
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1275
        found, ghosts, next, parents = self._do_query(self._next_query)
1276
        self._current_present = found
1277
        self._current_ghosts = ghosts
1278
        self._next_query = next
1279
        self._current_parents = parents
3184.1.3 by Robert Collins
Automatically exclude ghosts.
1280
        # ghosts are implicit stop points, otherwise the search cannot be
1281
        # repeated when ghosts are filled.
1282
        self._stopped_keys.update(ghosts)
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1283
1284
    def _do_query(self, revisions):
1285
        """Query for revisions.
1286
3184.1.4 by Robert Collins
Correctly exclude ghosts when ghosts are started on an existing search.
1287
        Adds revisions to the seen set.
1288
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1289
        :param revisions: Revisions to query.
1290
        :return: A tuple: (set(found_revisions), set(ghost_revisions),
1291
           set(parents_of_found_revisions), dict(found_revisions:parents)).
1292
        """
3377.3.9 by John Arbash Meinel
Small tweaks to _do_query
1293
        found_revisions = set()
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1294
        parents_of_found = set()
3184.1.1 by Robert Collins
Add basic get_recipe to the graph breadth first searcher.
1295
        # revisions may contain nodes that point to other nodes in revisions:
1296
        # we want to filter them out.
1297
        self.seen.update(revisions)
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1298
        parent_map = self._parents_provider.get_parent_map(revisions)
3377.3.9 by John Arbash Meinel
Small tweaks to _do_query
1299
        found_revisions.update(parent_map)
3177.3.1 by Robert Collins
* New method ``next_with_ghosts`` on the Graph breadth-first-search objects
1300
        for rev_id, parents in parent_map.iteritems():
3517.4.2 by Martin Pool
Make simple-annotation and graph code more tolerant of knits with no graph
1301
            if parents is None:
1302
                continue
3377.3.9 by John Arbash Meinel
Small tweaks to _do_query
1303
            new_found_parents = [p for p in parents if p not in self.seen]
1304
            if new_found_parents:
1305
                # Calling set.update() with an empty generator is actually
1306
                # rather expensive.
1307
                parents_of_found.update(new_found_parents)
1308
        ghost_revisions = revisions - found_revisions
1309
        return found_revisions, ghost_revisions, parents_of_found, parent_map
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1310
2490.2.8 by Aaron Bentley
fix iteration stuff
1311
    def __iter__(self):
1312
        return self
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1313
3377.3.1 by John Arbash Meinel
Bring in some of the changes from graph_update and graph_optimization
1314
    def find_seen_ancestors(self, revisions):
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
1315
        """Find ancestors of these revisions that have already been seen.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1316
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
1317
        This function generally makes the assumption that querying for the
1318
        parents of a node that has already been queried is reasonably cheap.
1319
        (eg, not a round trip to a remote host).
1320
        """
1321
        # TODO: Often we might ask one searcher for its seen ancestors, and
1322
        #       then ask another searcher the same question. This can result in
1323
        #       searching the same revisions repeatedly if the two searchers
1324
        #       have a lot of overlap.
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
1325
        all_seen = self.seen
1326
        pending = set(revisions).intersection(all_seen)
1327
        seen_ancestors = set(pending)
1328
1329
        if self._returning == 'next':
1330
            # self.seen contains what nodes have been returned, not what nodes
1331
            # have been queried. We don't want to probe for nodes that haven't
1332
            # been searched yet.
1333
            not_searched_yet = self._next_query
1334
        else:
1335
            not_searched_yet = ()
3377.3.11 by John Arbash Meinel
Committing a debug thunk that was very helpful
1336
        pending.difference_update(not_searched_yet)
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
1337
        get_parent_map = self._parents_provider.get_parent_map
3377.3.12 by John Arbash Meinel
Remove the helpful but ugly thunk
1338
        while pending:
1339
            parent_map = get_parent_map(pending)
1340
            all_parents = []
1341
            # We don't care if it is a ghost, since it can't be seen if it is
1342
            # a ghost
1343
            for parent_ids in parent_map.itervalues():
1344
                all_parents.extend(parent_ids)
1345
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1346
            seen_ancestors.update(next_pending)
1347
            next_pending.difference_update(not_searched_yet)
1348
            pending = next_pending
3377.3.10 by John Arbash Meinel
Tweak _BreadthFirstSearcher.find_seen_ancestors()
1349
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
1350
        return seen_ancestors
1351
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
1352
    def stop_searching_any(self, revisions):
1353
        """
1354
        Remove any of the specified revisions from the search list.
1355
1356
        None of the specified revisions are required to be present in the
3808.1.4 by John Arbash Meinel
make _walk_to_common responsible for stopping ancestors
1357
        search list.
3808.1.1 by Andrew Bennetts
Possible fix for bug in new _walk_to_common_revisions.
1358
3808.1.4 by John Arbash Meinel
make _walk_to_common responsible for stopping ancestors
1359
        It is okay to call stop_searching_any() for revisions which were seen
1360
        in previous iterations. It is the callers responsibility to call
1361
        find_seen_ancestors() to make sure that current search tips that are
1362
        ancestors of those revisions are also stopped.  All explicitly stopped
1363
        revisions will be excluded from the search result's get_keys(), though.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
1364
        """
3377.4.6 by John Arbash Meinel
Lots of refactoring for find_unique_ancestors.
1365
        # TODO: does this help performance?
1366
        # if not revisions:
1367
        #     return set()
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1368
        revisions = frozenset(revisions)
3177.3.3 by Robert Collins
Review feedback.
1369
        if self._returning == 'next':
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1370
            stopped = self._next_query.intersection(revisions)
1371
            self._next_query = self._next_query.difference(revisions)
1372
        else:
3184.2.1 by Robert Collins
Handle stopping ghosts in searches properly.
1373
            stopped_present = self._current_present.intersection(revisions)
1374
            stopped = stopped_present.union(
1375
                self._current_ghosts.intersection(revisions))
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1376
            self._current_present.difference_update(stopped)
1377
            self._current_ghosts.difference_update(stopped)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1378
            # stopping 'x' should stop returning parents of 'x', but
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1379
            # not if 'y' always references those same parents
1380
            stop_rev_references = {}
3184.2.1 by Robert Collins
Handle stopping ghosts in searches properly.
1381
            for rev in stopped_present:
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1382
                for parent_id in self._current_parents[rev]:
1383
                    if parent_id not in stop_rev_references:
1384
                        stop_rev_references[parent_id] = 0
1385
                    stop_rev_references[parent_id] += 1
1386
            # if only the stopped revisions reference it, the ref count will be
1387
            # 0 after this loop
3177.3.3 by Robert Collins
Review feedback.
1388
            for parents in self._current_parents.itervalues():
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1389
                for parent_id in parents:
1390
                    try:
1391
                        stop_rev_references[parent_id] -= 1
1392
                    except KeyError:
1393
                        pass
1394
            stop_parents = set()
1395
            for rev_id, refs in stop_rev_references.iteritems():
1396
                if refs == 0:
1397
                    stop_parents.add(rev_id)
1398
            self._next_query.difference_update(stop_parents)
3184.1.2 by Robert Collins
Add tests for starting and stopping searches in combination with get_recipe.
1399
        self._stopped_keys.update(stopped)
4053.2.2 by Andrew Bennetts
Better fix, with test.
1400
        self._stopped_keys.update(revisions)
2490.2.25 by Aaron Bentley
Update from review
1401
        return stopped
2490.2.17 by Aaron Bentley
Add start_searching, tweak stop_searching_any
1402
1403
    def start_searching(self, revisions):
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1404
        """Add revisions to the search.
1405
1406
        The parents of revisions will be returned from the next call to next()
1407
        or next_with_ghosts(). If next_with_ghosts was the most recently used
1408
        next* call then the return value is the result of looking up the
1409
        ghost/not ghost status of revisions. (A tuple (present, ghosted)).
1410
        """
1411
        revisions = frozenset(revisions)
3184.1.2 by Robert Collins
Add tests for starting and stopping searches in combination with get_recipe.
1412
        self._started_keys.update(revisions)
3184.1.4 by Robert Collins
Correctly exclude ghosts when ghosts are started on an existing search.
1413
        new_revisions = revisions.difference(self.seen)
3177.3.3 by Robert Collins
Review feedback.
1414
        if self._returning == 'next':
3184.1.4 by Robert Collins
Correctly exclude ghosts when ghosts are started on an existing search.
1415
            self._next_query.update(new_revisions)
3377.3.30 by John Arbash Meinel
Can we avoid the extra _do_query in start_searching?
1416
            self.seen.update(new_revisions)
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1417
        else:
1418
            # perform a query on revisions
3377.3.30 by John Arbash Meinel
Can we avoid the extra _do_query in start_searching?
1419
            revs, ghosts, query, parents = self._do_query(revisions)
1420
            self._stopped_keys.update(ghosts)
3177.3.2 by Robert Collins
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
1421
            self._current_present.update(revs)
1422
            self._current_ghosts.update(ghosts)
1423
            self._next_query.update(query)
1424
            self._current_parents.update(parents)
1425
            return revs, ghosts
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1426
1427
1428
class SearchResult(object):
1429
    """The result of a breadth first search.
1430
1431
    A SearchResult provides the ability to reconstruct the search or access a
1432
    set of the keys the search found.
1433
    """
1434
1435
    def __init__(self, start_keys, exclude_keys, key_count, keys):
1436
        """Create a SearchResult.
1437
1438
        :param start_keys: The keys the search started at.
1439
        :param exclude_keys: The keys the search excludes.
1440
        :param key_count: The total number of keys (from start to but not
1441
            including exclude).
1442
        :param keys: The keys the search found. Note that in future we may get
1443
            a SearchResult from a smart server, in which case the keys list is
1444
            not necessarily immediately available.
1445
        """
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1446
        self._recipe = ('search', start_keys, exclude_keys, key_count)
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1447
        self._keys = frozenset(keys)
1448
1449
    def get_recipe(self):
1450
        """Return a recipe that can be used to replay this search.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1451
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1452
        The recipe allows reconstruction of the same results at a later date
1453
        without knowing all the found keys. The essential elements are a list
1454
        of keys to start and and to stop at. In order to give reproducible
1455
        results when ghosts are encountered by a search they are automatically
1456
        added to the exclude list (or else ghost filling may alter the
1457
        results).
1458
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1459
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
1460
            revision_count). To recreate the results of this search, create a
1461
            breadth first searcher on the same graph starting at start_keys.
1462
            Then call next() (or next_with_ghosts()) repeatedly, and on every
1463
            result, call stop_searching_any on any keys from the exclude_keys
1464
            set. The revision_count value acts as a trivial cross-check - the
1465
            found revisions of the new search should have as many elements as
3184.1.6 by Robert Collins
Create a SearchResult object which can be used as a replacement for sets.
1466
            revision_count. If it does not, then additional revisions have been
1467
            ghosted since the search was executed the first time and the second
1468
            time.
1469
        """
1470
        return self._recipe
1471
1472
    def get_keys(self):
1473
        """Return the keys found in this search.
1474
1475
        :return: A set of keys.
1476
        """
1477
        return self._keys
1478
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1479
    def is_empty(self):
1480
        """Return true if the search lists 1 or more revisions."""
1481
        return self._recipe[3] == 0
1482
1483
    def refine(self, seen, referenced):
1484
        """Create a new search by refining this search.
1485
1486
        :param seen: Revisions that have been satisfied.
1487
        :param referenced: Revision references observed while satisfying some
1488
            of this search.
1489
        """
1490
        start = self._recipe[1]
1491
        exclude = self._recipe[2]
1492
        count = self._recipe[3]
1493
        keys = self.get_keys()
1494
        # New heads = referenced + old heads - seen things - exclude
1495
        pending_refs = set(referenced)
1496
        pending_refs.update(start)
1497
        pending_refs.difference_update(seen)
1498
        pending_refs.difference_update(exclude)
1499
        # New exclude = old exclude + satisfied heads
1500
        seen_heads = start.intersection(seen)
1501
        exclude.update(seen_heads)
1502
        # keys gets seen removed
1503
        keys = keys - seen
1504
        # length is reduced by len(seen)
1505
        count -= len(seen)
1506
        return SearchResult(pending_refs, exclude, count, keys)
1507
3514.2.14 by John Arbash Meinel
Bring in the code to collapse linear portions of the graph.
1508
4070.9.14 by Andrew Bennetts
Tweaks requested by Robert's review.
1509
class PendingAncestryResult(object):
1510
    """A search result that will reconstruct the ancestry for some graph heads.
4086.1.4 by Andrew Bennetts
Fix whitespace nit.
1511
4070.9.14 by Andrew Bennetts
Tweaks requested by Robert's review.
1512
    Unlike SearchResult, this doesn't hold the complete search result in
1513
    memory, it just holds a description of how to generate it.
1514
    """
1515
1516
    def __init__(self, heads, repo):
1517
        """Constructor.
1518
1519
        :param heads: an iterable of graph heads.
1520
        :param repo: a repository to use to generate the ancestry for the given
1521
            heads.
1522
        """
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1523
        self.heads = frozenset(heads)
4070.9.2 by Andrew Bennetts
Rough prototype of allowing a SearchResult to be passed to fetch, and using that to improve network conversations.
1524
        self.repo = repo
1525
4070.9.5 by Andrew Bennetts
Better wire protocol: don't shoehorn MiniSearchResult serialisation into previous serialisation format.
1526
    def get_recipe(self):
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1527
        """Return a recipe that can be used to replay this search.
1528
1529
        The recipe allows reconstruction of the same results at a later date.
1530
1531
        :seealso SearchResult.get_recipe:
1532
1533
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
1534
            To recreate this result, create a PendingAncestryResult with the
1535
            start_keys_set.
1536
        """
1537
        return ('proxy-search', self.heads, set(), -1)
4070.9.5 by Andrew Bennetts
Better wire protocol: don't shoehorn MiniSearchResult serialisation into previous serialisation format.
1538
4070.9.2 by Andrew Bennetts
Rough prototype of allowing a SearchResult to be passed to fetch, and using that to improve network conversations.
1539
    def get_keys(self):
4098.1.1 by Andrew Bennetts
Fix a bug with how PendingAncestryResult.get_keys handles NULL_REVISION.
1540
        """See SearchResult.get_keys.
4098.1.2 by Andrew Bennetts
Fix 'trailing' whitespace (actually just a blank line in an indented docstring).
1541
4098.1.1 by Andrew Bennetts
Fix a bug with how PendingAncestryResult.get_keys handles NULL_REVISION.
1542
        Returns all the keys for the ancestry of the heads, excluding
1543
        NULL_REVISION.
1544
        """
1545
        return self._get_keys(self.repo.get_graph())
4098.1.3 by Andrew Bennetts
Fix 'trailing' whitespace (actually just a blank line between methods).
1546
4098.1.1 by Andrew Bennetts
Fix a bug with how PendingAncestryResult.get_keys handles NULL_REVISION.
1547
    def _get_keys(self, graph):
1548
        NULL_REVISION = revision.NULL_REVISION
1549
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1550
                if key != NULL_REVISION]
4070.9.2 by Andrew Bennetts
Rough prototype of allowing a SearchResult to be passed to fetch, and using that to improve network conversations.
1551
        return keys
1552
4152.1.2 by Robert Collins
Add streaming from a stacked branch when the sort order is compatible with doing so.
1553
    def is_empty(self):
1554
        """Return true if the search lists 1 or more revisions."""
1555
        if revision.NULL_REVISION in self.heads:
1556
            return len(self.heads) == 1
1557
        else:
1558
            return len(self.heads) == 0
1559
1560
    def refine(self, seen, referenced):
1561
        """Create a new search by refining this search.
1562
1563
        :param seen: Revisions that have been satisfied.
1564
        :param referenced: Revision references observed while satisfying some
1565
            of this search.
1566
        """
1567
        referenced = self.heads.union(referenced)
1568
        return PendingAncestryResult(referenced - seen, self.repo)
1569
4070.9.2 by Andrew Bennetts
Rough prototype of allowing a SearchResult to be passed to fetch, and using that to improve network conversations.
1570
3514.2.14 by John Arbash Meinel
Bring in the code to collapse linear portions of the graph.
1571
def collapse_linear_regions(parent_map):
1572
    """Collapse regions of the graph that are 'linear'.
1573
1574
    For example::
1575
1576
      A:[B], B:[C]
1577
1578
    can be collapsed by removing B and getting::
1579
1580
      A:[C]
1581
1582
    :param parent_map: A dictionary mapping children to their parents
1583
    :return: Another dictionary with 'linear' chains collapsed
1584
    """
1585
    # Note: this isn't a strictly minimal collapse. For example:
1586
    #   A
1587
    #  / \
1588
    # B   C
1589
    #  \ /
1590
    #   D
1591
    #   |
1592
    #   E
1593
    # Will not have 'D' removed, even though 'E' could fit. Also:
1594
    #   A
1595
    #   |    A
1596
    #   B => |
1597
    #   |    C
1598
    #   C
1599
    # A and C are both kept because they are edges of the graph. We *could* get
1600
    # rid of A if we wanted.
1601
    #   A
1602
    #  / \
1603
    # B   C
1604
    # |   |
1605
    # D   E
1606
    #  \ /
1607
    #   F
1608
    # Will not have any nodes removed, even though you do have an
1609
    # 'uninteresting' linear D->B and E->C
1610
    children = {}
1611
    for child, parents in parent_map.iteritems():
1612
        children.setdefault(child, [])
1613
        for p in parents:
1614
            children.setdefault(p, []).append(child)
1615
1616
    orig_children = dict(children)
1617
    removed = set()
1618
    result = dict(parent_map)
1619
    for node in parent_map:
1620
        parents = result[node]
1621
        if len(parents) == 1:
1622
            parent_children = children[parents[0]]
1623
            if len(parent_children) != 1:
1624
                # This is not the only child
1625
                continue
1626
            node_children = children[node]
1627
            if len(node_children) != 1:
1628
                continue
1629
            child_parents = result.get(node_children[0], None)
1630
            if len(child_parents) != 1:
1631
                # This is not its only parent
1632
                continue
1633
            # The child of this node only points at it, and the parent only has
1634
            # this as a child. remove this node, and join the others together
1635
            result[node_children[0]] = parents
1636
            children[parents[0]] = node_children
1637
            del result[node]
1638
            del children[node]
1639
            removed.add(node)
1640
1641
    return result