~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
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
17
from bzrlib import (
18
    errors,
3052.1.3 by John Arbash Meinel
deprecate revision.is_ancestor, update the callers and the tests.
19
    revision,
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
20
    tsort,
21
    )
2490.2.21 by Aaron Bentley
Rename graph to deprecated_graph
22
from bzrlib.deprecated_graph import (node_distances, select_farthest)
2490.2.1 by Aaron Bentley
Start work on GraphWalker
23
2490.2.25 by Aaron Bentley
Update from review
24
# DIAGRAM of terminology
25
#       A
26
#       /\
27
#      B  C
28
#      |  |\
29
#      D  E F
30
#      |\/| |
31
#      |/\|/
32
#      G  H
33
#
34
# In this diagram, relative to G and H:
35
# A, B, C, D, E are common ancestors.
36
# C, D and E are border ancestors, because each has a non-common descendant.
37
# D and E are least common ancestors because none of their descendants are
38
# common ancestors.
39
# C is not a least common ancestor because its descendant, E, is a common
40
# ancestor.
41
#
42
# The find_unique_lca algorithm will pick A in two steps:
43
# 1. find_lca('G', 'H') => ['D', 'E']
44
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
45
46
2988.1.3 by Robert Collins
Add a new repositoy method _generate_text_key_index for use by reconcile/check.
47
class DictParentsProvider(object):
48
49
    def __init__(self, ancestry):
50
        self.ancestry = ancestry
51
52
    def __repr__(self):
53
        return 'DictParentsProvider(%r)' % self.ancestry
54
55
    def get_parents(self, revisions):
56
        return [self.ancestry.get(r, None) for r in revisions]
57
2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
58
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
59
class _StackedParentsProvider(object):
60
61
    def __init__(self, parent_providers):
62
        self._parent_providers = parent_providers
63
2490.2.28 by Aaron Bentley
Fix handling of null revision
64
    def __repr__(self):
65
        return "_StackedParentsProvider(%r)" % self._parent_providers
66
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
67
    def get_parents(self, revision_ids):
2490.2.25 by Aaron Bentley
Update from review
68
        """Find revision ids of the parents of a list of revisions
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
69
70
        A list is returned of the same length as the input.  Each entry
71
        is a list of parent ids for the corresponding input revision.
72
73
        [NULL_REVISION] is used as the parent of the first user-committed
74
        revision.  Its parent list is empty.
75
76
        If the revision is not present (i.e. a ghost), None is used in place
77
        of the list of parents.
78
        """
79
        found = {}
80
        for parents_provider in self._parent_providers:
2490.2.25 by Aaron Bentley
Update from review
81
            pending_revisions = [r for r in revision_ids if r not in found]
82
            parent_list = parents_provider.get_parents(pending_revisions)
83
            new_found = dict((k, v) for k, v in zip(pending_revisions,
84
                             parent_list) if v is not None)
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
85
            found.update(new_found)
86
            if len(found) == len(revision_ids):
87
                break
2490.2.25 by Aaron Bentley
Update from review
88
        return [found.get(r, None) for r in revision_ids]
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
89
90
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
91
class Graph(object):
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
92
    """Provide incremental access to revision graphs.
93
94
    This is the generic implementation; it is intended to be subclassed to
95
    specialize it for other repository types.
96
    """
2490.2.1 by Aaron Bentley
Start work on GraphWalker
97
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
98
    def __init__(self, parents_provider):
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
99
        """Construct a Graph that uses several graphs as its input
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
100
101
        This should not normally be invoked directly, because there may be
102
        specialized implementations for particular repository types.  See
2490.2.21 by Aaron Bentley
Rename graph to deprecated_graph
103
        Repository.get_graph()
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
104
2921.3.4 by Robert Collins
Review feedback.
105
        :param parents_provider: An object providing a get_parents call
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
106
            conforming to the behavior of StackedParentsProvider.get_parents
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
107
        """
108
        self.get_parents = parents_provider.get_parents
2490.2.29 by Aaron Bentley
Make parents provider private
109
        self._parents_provider = parents_provider
2490.2.28 by Aaron Bentley
Fix handling of null revision
110
111
    def __repr__(self):
2490.2.29 by Aaron Bentley
Make parents provider private
112
        return 'Graph(%r)' % self._parents_provider
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
113
114
    def find_lca(self, *revisions):
115
        """Determine the lowest common ancestors of the provided revisions
116
117
        A lowest common ancestor is a common ancestor none of whose
118
        descendants are common ancestors.  In graphs, unlike trees, there may
119
        be multiple lowest common ancestors.
2490.2.12 by Aaron Bentley
Improve documentation
120
121
        This algorithm has two phases.  Phase 1 identifies border ancestors,
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
122
        and phase 2 filters border ancestors to determine lowest common
123
        ancestors.
2490.2.12 by Aaron Bentley
Improve documentation
124
125
        In phase 1, border ancestors are identified, using a breadth-first
126
        search starting at the bottom of the graph.  Searches are stopped
127
        whenever a node or one of its descendants is determined to be common
128
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
129
        In phase 2, the border ancestors are filtered to find the least
2490.2.12 by Aaron Bentley
Improve documentation
130
        common ancestors.  This is done by searching the ancestries of each
131
        border ancestor.
132
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
133
        Phase 2 is perfomed on the principle that a border ancestor that is
134
        not an ancestor of any other border ancestor is a least common
135
        ancestor.
2490.2.12 by Aaron Bentley
Improve documentation
136
137
        Searches are stopped when they find a node that is determined to be a
138
        common ancestor of all border ancestors, because this shows that it
139
        cannot be a descendant of any border ancestor.
140
141
        The scaling of this operation should be proportional to
142
        1. The number of uncommon ancestors
143
        2. The number of border ancestors
144
        3. The length of the shortest path between a border ancestor and an
145
           ancestor of all border ancestors.
2490.2.3 by Aaron Bentley
Implement new merge base picker
146
        """
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
147
        border_common, common, sides = self._find_border_ancestors(revisions)
2776.3.1 by Robert Collins
* Deprecated method ``find_previous_heads`` on
148
        # We may have common ancestors that can be reached from each other.
149
        # - ask for the heads of them to filter it down to only ones that
150
        # cannot be reached from each other - phase 2.
151
        return self.heads(border_common)
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
152
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
153
    def find_difference(self, left_revision, right_revision):
2490.2.25 by Aaron Bentley
Update from review
154
        """Determine the graph difference between two revisions"""
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
155
        border, common, (left, right) = self._find_border_ancestors(
156
            [left_revision, right_revision])
157
        return (left.difference(right).difference(common),
158
                right.difference(left).difference(common))
159
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
160
    def _make_breadth_first_searcher(self, revisions):
161
        return _BreadthFirstSearcher(revisions, self)
162
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
163
    def _find_border_ancestors(self, revisions):
2490.2.12 by Aaron Bentley
Improve documentation
164
        """Find common ancestors with at least one uncommon descendant.
165
166
        Border ancestors are identified using a breadth-first
167
        search starting at the bottom of the graph.  Searches are stopped
168
        whenever a node or one of its descendants is determined to be common.
169
170
        This will scale with the number of uncommon ancestors.
2490.2.25 by Aaron Bentley
Update from review
171
172
        As well as the border ancestors, a set of seen common ancestors and a
173
        list of sets of seen ancestors for each input revision is returned.
174
        This allows calculation of graph difference from the results of this
175
        operation.
2490.2.12 by Aaron Bentley
Improve documentation
176
        """
2490.2.28 by Aaron Bentley
Fix handling of null revision
177
        if None in revisions:
178
            raise errors.InvalidRevisionId(None, self)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
179
        common_searcher = self._make_breadth_first_searcher([])
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
180
        common_ancestors = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
181
        searchers = [self._make_breadth_first_searcher([r])
182
                     for r in revisions]
183
        active_searchers = searchers[:]
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
184
        border_ancestors = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
185
        def update_common(searcher, revisions):
186
            w_seen_ancestors = searcher.find_seen_ancestors(
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
187
                revision)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
188
            stopped = searcher.stop_searching_any(w_seen_ancestors)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
189
            common_ancestors.update(w_seen_ancestors)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
190
            common_searcher.start_searching(stopped)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
191
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
192
        while True:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
193
            if len(active_searchers) == 0:
2490.2.23 by Aaron Bentley
Adapt find_borders to produce a graph difference
194
                return border_ancestors, common_ancestors, [s.seen for s in
195
                                                            searchers]
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
196
            try:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
197
                new_common = common_searcher.next()
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
198
                common_ancestors.update(new_common)
199
            except StopIteration:
200
                pass
201
            else:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
202
                for searcher in active_searchers:
203
                    for revision in new_common.intersection(searcher.seen):
204
                        update_common(searcher, revision)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
205
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
206
            newly_seen = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
207
            new_active_searchers = []
208
            for searcher in active_searchers:
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
209
                try:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
210
                    newly_seen.update(searcher.next())
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
211
                except StopIteration:
212
                    pass
213
                else:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
214
                    new_active_searchers.append(searcher)
215
            active_searchers = new_active_searchers
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
216
            for revision in newly_seen:
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
217
                if revision in common_ancestors:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
218
                    for searcher in searchers:
219
                        update_common(searcher, revision)
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
220
                    continue
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
221
                for searcher in searchers:
222
                    if revision not in searcher.seen:
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
223
                        break
224
                else:
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
225
                    border_ancestors.add(revision)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
226
                    for searcher in searchers:
227
                        update_common(searcher, revision)
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
228
2776.3.1 by Robert Collins
* Deprecated method ``find_previous_heads`` on
229
    def heads(self, keys):
230
        """Return the heads from amongst keys.
231
232
        This is done by searching the ancestries of each key.  Any key that is
233
        reachable from another key is not returned; all the others are.
234
235
        This operation scales with the relative depth between any two keys. If
236
        any two keys are completely disconnected all ancestry of both sides
237
        will be retrieved.
238
239
        :param keys: An iterable of keys.
2776.1.4 by Robert Collins
Trivial review feedback changes.
240
        :return: A set of the heads. Note that as a set there is no ordering
241
            information. Callers will need to filter their input to create
242
            order if they need it.
2490.2.12 by Aaron Bentley
Improve documentation
243
        """
2776.1.4 by Robert Collins
Trivial review feedback changes.
244
        candidate_heads = set(keys)
2850.2.1 by Robert Collins
(robertc) Special case the zero-or-no-heads case for Graph.heads(). (Robert Collins)
245
        if len(candidate_heads) < 2:
246
            return candidate_heads
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
247
        searchers = dict((c, self._make_breadth_first_searcher([c]))
2776.1.4 by Robert Collins
Trivial review feedback changes.
248
                          for c in candidate_heads)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
249
        active_searchers = dict(searchers)
250
        # skip over the actual candidate for each searcher
251
        for searcher in active_searchers.itervalues():
1551.15.81 by Aaron Bentley
Remove testing code
252
            searcher.next()
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
253
        # The common walker finds nodes that are common to two or more of the
254
        # input keys, so that we don't access all history when a currently
255
        # uncommon search point actually meets up with something behind a
256
        # common search point. Common search points do not keep searches
257
        # active; they just allow us to make searches inactive without
258
        # accessing all history.
259
        common_walker = self._make_breadth_first_searcher([])
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
260
        while len(active_searchers) > 0:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
261
            ancestors = set()
262
            # advance searches
263
            try:
264
                common_walker.next()
265
            except StopIteration:
2921.3.4 by Robert Collins
Review feedback.
266
                # 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
267
                pass
1551.15.78 by Aaron Bentley
Fix KeyError in filter_candidate_lca
268
            for candidate in active_searchers.keys():
269
                try:
270
                    searcher = active_searchers[candidate]
271
                except KeyError:
272
                    # rare case: we deleted candidate in a previous iteration
273
                    # through this for loop, because it was determined to be
274
                    # a descendant of another candidate.
275
                    continue
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
276
                try:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
277
                    ancestors.update(searcher.next())
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
278
                except StopIteration:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
279
                    del active_searchers[candidate]
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
280
                    continue
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
281
            # process found nodes
282
            new_common = set()
283
            for ancestor in ancestors:
284
                if ancestor in candidate_heads:
285
                    candidate_heads.remove(ancestor)
286
                    del searchers[ancestor]
287
                    if ancestor in active_searchers:
288
                        del active_searchers[ancestor]
289
                # it may meet up with a known common node
2921.3.4 by Robert Collins
Review feedback.
290
                if ancestor in common_walker.seen:
291
                    # some searcher has encountered our known common nodes:
292
                    # just stop it
293
                    ancestor_set = set([ancestor])
294
                    for searcher in searchers.itervalues():
295
                        searcher.stop_searching_any(ancestor_set)
296
                else:
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
297
                    # or it may have been just reached by all the searchers:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
298
                    for searcher in searchers.itervalues():
299
                        if ancestor not in searcher.seen:
2490.2.9 by Aaron Bentley
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors
300
                            break
301
                    else:
2921.3.4 by Robert Collins
Review feedback.
302
                        # The final active searcher has just reached this node,
303
                        # making it be known as a descendant of all candidates,
304
                        # so we can stop searching it, and any seen ancestors
305
                        new_common.add(ancestor)
306
                        for searcher in searchers.itervalues():
307
                            seen_ancestors =\
308
                                searcher.find_seen_ancestors(ancestor)
309
                            searcher.stop_searching_any(seen_ancestors)
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
310
            common_walker.start_searching(new_common)
2776.1.4 by Robert Collins
Trivial review feedback changes.
311
        return candidate_heads
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
312
313
    def find_unique_lca(self, left_revision, right_revision):
314
        """Find a unique LCA.
315
316
        Find lowest common ancestors.  If there is no unique  common
317
        ancestor, find the lowest common ancestors of those ancestors.
318
319
        Iteration stops when a unique lowest common ancestor is found.
320
        The graph origin is necessarily a unique lowest common ancestor.
2490.2.5 by Aaron Bentley
Use GraphWalker.unique_ancestor to determine merge base
321
322
        Note that None is not an acceptable substitute for NULL_REVISION.
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
323
        in the input for this method.
2490.2.3 by Aaron Bentley
Implement new merge base picker
324
        """
325
        revisions = [left_revision, right_revision]
326
        while True:
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
327
            lca = self.find_lca(*revisions)
328
            if len(lca) == 1:
329
                return lca.pop()
2520.4.104 by Aaron Bentley
Avoid infinite loop when there is no unique lca
330
            if len(lca) == 0:
331
                raise errors.NoCommonAncestor(left_revision, right_revision)
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
332
            revisions = lca
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
333
2490.2.31 by Aaron Bentley
Fix iter_topo_order to permit un-included parents
334
    def iter_topo_order(self, revisions):
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
335
        """Iterate through the input revisions in topological order.
336
337
        This sorting only ensures that parents come before their children.
338
        An ancestor may sort after a descendant if the relationship is not
339
        visible in the supplied list of revisions.
340
        """
2490.2.34 by Aaron Bentley
Update NEWS and change implementation to return an iterator
341
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
342
        return sorter.iter_topo_order()
2490.2.30 by Aaron Bentley
Add functionality for tsorting graphs
343
2653.2.1 by Aaron Bentley
Implement Graph.is_ancestor
344
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
2653.2.5 by Aaron Bentley
Update to clarify algorithm
345
        """Determine whether a revision is an ancestor of another.
346
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
347
        We answer this using heads() as heads() has the logic to perform the
348
        smallest number of parent looksup to determine the ancestral
349
        relationship between N revisions.
2653.2.5 by Aaron Bentley
Update to clarify algorithm
350
        """
3052.1.3 by John Arbash Meinel
deprecate revision.is_ancestor, update the callers and the tests.
351
        if revision.is_null(candidate_ancestor):
352
            return True
3052.1.4 by John Arbash Meinel
Special case when the candidate_descendant is also the NULL_REVISION
353
        if revision.is_null(candidate_descendant):
354
            # if candidate_descendant is NULL_REVISION, then only
355
            # candidate_ancestor == NULL_REVISION is an ancestor, but we've
356
            # already handled that case.
357
            return False
2921.3.1 by Robert Collins
* Graph ``heads()`` queries have been bugfixed to no longer access all
358
        return set([candidate_descendant]) == self.heads(
359
            [candidate_ancestor, candidate_descendant])
2653.2.1 by Aaron Bentley
Implement Graph.is_ancestor
360
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
361
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
362
class HeadsCache(object):
363
    """A cache of results for graph heads calls."""
364
365
    def __init__(self, graph):
366
        self.graph = graph
367
        self._heads = {}
368
369
    def heads(self, keys):
370
        """Return the heads of keys.
371
2911.4.3 by Robert Collins
Make the contract of HeadsCache.heads() more clear.
372
        This matches the API of Graph.heads(), specifically the return value is
373
        a set which can be mutated, and ordering of the input is not preserved
374
        in the output.
375
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
376
        :see also: Graph.heads.
377
        :param keys: The keys to calculate heads for.
378
        :return: A set containing the heads, which may be mutated without
379
            affecting future lookups.
380
        """
2911.4.2 by Robert Collins
Make HeadsCache actually work.
381
        keys = frozenset(keys)
2911.4.1 by Robert Collins
Factor out the Graph.heads() cache from _RevisionTextVersionCache for reuse, and use it in commit.
382
        try:
383
            return set(self._heads[keys])
384
        except KeyError:
385
            heads = self.graph.heads(keys)
386
            self._heads[keys] = heads
387
            return set(heads)
388
389
2592.3.223 by Robert Collins
Merge graph history-access bugfix.
390
class HeadsCache(object):
391
    """A cache of results for graph heads calls."""
392
393
    def __init__(self, graph):
394
        self.graph = graph
395
        self._heads = {}
396
397
    def heads(self, keys):
398
        """Return the heads of keys.
399
400
        :see also: Graph.heads.
401
        :param keys: The keys to calculate heads for.
402
        :return: A set containing the heads, which may be mutated without
403
            affecting future lookups.
404
        """
405
        keys = frozenset(keys)
406
        try:
407
            return set(self._heads[keys])
408
        except KeyError:
409
            heads = self.graph.heads(keys)
410
            self._heads[keys] = heads
411
            return set(heads)
412
413
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
414
class _BreadthFirstSearcher(object):
2921.3.4 by Robert Collins
Review feedback.
415
    """Parallel search breadth-first the ancestry of revisions.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
416
417
    This class implements the iterator protocol, but additionally
418
    1. provides a set of seen ancestors, and
419
    2. allows some ancestries to be unsearched, via stop_searching_any
420
    """
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
421
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
422
    def __init__(self, revisions, parents_provider):
2490.2.18 by Aaron Bentley
Change AncestryWalker to take a set of ancestors
423
        self._start = set(revisions)
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
424
        self._search_revisions = None
2490.2.18 by Aaron Bentley
Change AncestryWalker to take a set of ancestors
425
        self.seen = set(revisions)
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
426
        self._parents_provider = parents_provider 
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
427
428
    def __repr__(self):
2490.2.25 by Aaron Bentley
Update from review
429
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
430
                ' self.seen=%r)' % (self._search_revisions, self.seen))
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
431
432
    def next(self):
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
433
        """Return the next ancestors of this revision.
434
2490.2.12 by Aaron Bentley
Improve documentation
435
        Ancestors are returned in the order they are seen in a breadth-first
436
        traversal.  No ancestor will be returned more than once.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
437
        """
438
        if self._search_revisions is None:
439
            self._search_revisions = self._start
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
440
        else:
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
441
            new_search_revisions = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
442
            for parents in self._parents_provider.get_parents(
2490.2.13 by Aaron Bentley
Update distinct -> lowest, refactor, add ParentsProvider concept
443
                self._search_revisions):
444
                if parents is None:
445
                    continue
446
                new_search_revisions.update(p for p in parents if
447
                                            p not in self.seen)
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
448
            self._search_revisions = new_search_revisions
449
        if len(self._search_revisions) == 0:
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
450
            raise StopIteration()
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
451
        self.seen.update(self._search_revisions)
452
        return self._search_revisions
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
453
2490.2.8 by Aaron Bentley
fix iteration stuff
454
    def __iter__(self):
455
        return self
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
456
457
    def find_seen_ancestors(self, revision):
2490.2.25 by Aaron Bentley
Update from review
458
        """Find ancestors of this revision that have already been seen."""
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
459
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
460
        seen_ancestors = set()
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
461
        for ancestors in searcher:
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
462
            for ancestor in ancestors:
463
                if ancestor not in self.seen:
2490.2.22 by Aaron Bentley
Rename GraphWalker -> Graph, _AncestryWalker -> _BreadthFirstSearcher
464
                    searcher.stop_searching_any([ancestor])
2490.2.7 by Aaron Bentley
Start implementing mca that scales with number of uncommon ancestors
465
                else:
466
                    seen_ancestors.add(ancestor)
467
        return seen_ancestors
468
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
469
    def stop_searching_any(self, revisions):
470
        """
471
        Remove any of the specified revisions from the search list.
472
473
        None of the specified revisions are required to be present in the
2490.2.12 by Aaron Bentley
Improve documentation
474
        search list.  In this case, the call is a no-op.
2490.2.10 by Aaron Bentley
Clarify text, remove unused _get_ancestry method
475
        """
2490.2.25 by Aaron Bentley
Update from review
476
        stopped = self._search_revisions.intersection(revisions)
477
        self._search_revisions = self._search_revisions.difference(revisions)
478
        return stopped
2490.2.17 by Aaron Bentley
Add start_searching, tweak stop_searching_any
479
480
    def start_searching(self, revisions):
481
        if self._search_revisions is None:
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
482
            self._start = set(revisions)
2490.2.17 by Aaron Bentley
Add start_searching, tweak stop_searching_any
483
        else:
2490.2.25 by Aaron Bentley
Update from review
484
            self._search_revisions.update(revisions.difference(self.seen))
2490.2.19 by Aaron Bentley
Implement common-ancestor-based culling
485
        self.seen.update(revisions)