/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Add source index to the index iteration API to allow mapping back to the origin of retrieved data.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
 
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
 
 
17
from bzrlib import (
 
18
    errors,
 
19
    tsort,
 
20
    )
 
21
from bzrlib.deprecated_graph import (node_distances, select_farthest)
 
22
from bzrlib.revision import NULL_REVISION
 
23
 
 
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
 
 
47
 
 
48
class _StackedParentsProvider(object):
 
49
 
 
50
    def __init__(self, parent_providers):
 
51
        self._parent_providers = parent_providers
 
52
 
 
53
    def __repr__(self):
 
54
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
55
 
 
56
    def get_parents(self, revision_ids):
 
57
        """Find revision ids of the parents of a list of revisions
 
58
 
 
59
        A list is returned of the same length as the input.  Each entry
 
60
        is a list of parent ids for the corresponding input revision.
 
61
 
 
62
        [NULL_REVISION] is used as the parent of the first user-committed
 
63
        revision.  Its parent list is empty.
 
64
 
 
65
        If the revision is not present (i.e. a ghost), None is used in place
 
66
        of the list of parents.
 
67
        """
 
68
        found = {}
 
69
        for parents_provider in self._parent_providers:
 
70
            pending_revisions = [r for r in revision_ids if r not in found]
 
71
            parent_list = parents_provider.get_parents(pending_revisions)
 
72
            new_found = dict((k, v) for k, v in zip(pending_revisions,
 
73
                             parent_list) if v is not None)
 
74
            found.update(new_found)
 
75
            if len(found) == len(revision_ids):
 
76
                break
 
77
        return [found.get(r, None) for r in revision_ids]
 
78
 
 
79
 
 
80
class Graph(object):
 
81
    """Provide incremental access to revision graphs.
 
82
 
 
83
    This is the generic implementation; it is intended to be subclassed to
 
84
    specialize it for other repository types.
 
85
    """
 
86
 
 
87
    def __init__(self, parents_provider):
 
88
        """Construct a Graph that uses several graphs as its input
 
89
 
 
90
        This should not normally be invoked directly, because there may be
 
91
        specialized implementations for particular repository types.  See
 
92
        Repository.get_graph()
 
93
 
 
94
        :param parents_func: an object providing a get_parents call
 
95
            conforming to the behavior of StackedParentsProvider.get_parents
 
96
        """
 
97
        self.get_parents = parents_provider.get_parents
 
98
        self._parents_provider = parents_provider
 
99
 
 
100
    def __repr__(self):
 
101
        return 'Graph(%r)' % self._parents_provider
 
102
 
 
103
    def find_lca(self, *revisions):
 
104
        """Determine the lowest common ancestors of the provided revisions
 
105
 
 
106
        A lowest common ancestor is a common ancestor none of whose
 
107
        descendants are common ancestors.  In graphs, unlike trees, there may
 
108
        be multiple lowest common ancestors.
 
109
 
 
110
        This algorithm has two phases.  Phase 1 identifies border ancestors,
 
111
        and phase 2 filters border ancestors to determine lowest common
 
112
        ancestors.
 
113
 
 
114
        In phase 1, border ancestors are identified, using a breadth-first
 
115
        search starting at the bottom of the graph.  Searches are stopped
 
116
        whenever a node or one of its descendants is determined to be common
 
117
 
 
118
        In phase 2, the border ancestors are filtered to find the least
 
119
        common ancestors.  This is done by searching the ancestries of each
 
120
        border ancestor.
 
121
 
 
122
        Phase 2 is perfomed on the principle that a border ancestor that is
 
123
        not an ancestor of any other border ancestor is a least common
 
124
        ancestor.
 
125
 
 
126
        Searches are stopped when they find a node that is determined to be a
 
127
        common ancestor of all border ancestors, because this shows that it
 
128
        cannot be a descendant of any border ancestor.
 
129
 
 
130
        The scaling of this operation should be proportional to
 
131
        1. The number of uncommon ancestors
 
132
        2. The number of border ancestors
 
133
        3. The length of the shortest path between a border ancestor and an
 
134
           ancestor of all border ancestors.
 
135
        """
 
136
        border_common, common, sides = self._find_border_ancestors(revisions)
 
137
        return self._filter_candidate_lca(border_common)
 
138
 
 
139
    def find_difference(self, left_revision, right_revision):
 
140
        """Determine the graph difference between two revisions"""
 
141
        border, common, (left, right) = self._find_border_ancestors(
 
142
            [left_revision, right_revision])
 
143
        return (left.difference(right).difference(common),
 
144
                right.difference(left).difference(common))
 
145
 
 
146
    def _make_breadth_first_searcher(self, revisions):
 
147
        return _BreadthFirstSearcher(revisions, self)
 
148
 
 
149
    def _find_border_ancestors(self, revisions):
 
150
        """Find common ancestors with at least one uncommon descendant.
 
151
 
 
152
        Border ancestors are identified using a breadth-first
 
153
        search starting at the bottom of the graph.  Searches are stopped
 
154
        whenever a node or one of its descendants is determined to be common.
 
155
 
 
156
        This will scale with the number of uncommon ancestors.
 
157
 
 
158
        As well as the border ancestors, a set of seen common ancestors and a
 
159
        list of sets of seen ancestors for each input revision is returned.
 
160
        This allows calculation of graph difference from the results of this
 
161
        operation.
 
162
        """
 
163
        if None in revisions:
 
164
            raise errors.InvalidRevisionId(None, self)
 
165
        common_searcher = self._make_breadth_first_searcher([])
 
166
        common_ancestors = set()
 
167
        searchers = [self._make_breadth_first_searcher([r])
 
168
                     for r in revisions]
 
169
        active_searchers = searchers[:]
 
170
        border_ancestors = set()
 
171
        def update_common(searcher, revisions):
 
172
            w_seen_ancestors = searcher.find_seen_ancestors(
 
173
                revision)
 
174
            stopped = searcher.stop_searching_any(w_seen_ancestors)
 
175
            common_ancestors.update(w_seen_ancestors)
 
176
            common_searcher.start_searching(stopped)
 
177
 
 
178
        while True:
 
179
            if len(active_searchers) == 0:
 
180
                return border_ancestors, common_ancestors, [s.seen for s in
 
181
                                                            searchers]
 
182
            try:
 
183
                new_common = common_searcher.next()
 
184
                common_ancestors.update(new_common)
 
185
            except StopIteration:
 
186
                pass
 
187
            else:
 
188
                for searcher in active_searchers:
 
189
                    for revision in new_common.intersection(searcher.seen):
 
190
                        update_common(searcher, revision)
 
191
 
 
192
            newly_seen = set()
 
193
            new_active_searchers = []
 
194
            for searcher in active_searchers:
 
195
                try:
 
196
                    newly_seen.update(searcher.next())
 
197
                except StopIteration:
 
198
                    pass
 
199
                else:
 
200
                    new_active_searchers.append(searcher)
 
201
            active_searchers = new_active_searchers
 
202
            for revision in newly_seen:
 
203
                if revision in common_ancestors:
 
204
                    for searcher in searchers:
 
205
                        update_common(searcher, revision)
 
206
                    continue
 
207
                for searcher in searchers:
 
208
                    if revision not in searcher.seen:
 
209
                        break
 
210
                else:
 
211
                    border_ancestors.add(revision)
 
212
                    for searcher in searchers:
 
213
                        update_common(searcher, revision)
 
214
 
 
215
    def _filter_candidate_lca(self, candidate_lca):
 
216
        """Remove candidates which are ancestors of other candidates.
 
217
 
 
218
        This is done by searching the ancestries of each border ancestor.  It
 
219
        is perfomed on the principle that a border ancestor that is not an
 
220
        ancestor of any other border ancestor is a lowest common ancestor.
 
221
 
 
222
        Searches are stopped when they find a node that is determined to be a
 
223
        common ancestor of all border ancestors, because this shows that it
 
224
        cannot be a descendant of any border ancestor.
 
225
 
 
226
        This will scale with the number of candidate ancestors and the length
 
227
        of the shortest path from a candidate to an ancestor common to all
 
228
        candidates.
 
229
        """
 
230
        searchers = dict((c, self._make_breadth_first_searcher([c]))
 
231
                          for c in candidate_lca)
 
232
        active_searchers = dict(searchers)
 
233
        # skip over the actual candidate for each searcher
 
234
        for searcher in active_searchers.itervalues():
 
235
            searcher.next()
 
236
        while len(active_searchers) > 0:
 
237
            for candidate, searcher in list(active_searchers.iteritems()):
 
238
                try:
 
239
                    ancestors = searcher.next()
 
240
                except StopIteration:
 
241
                    del active_searchers[candidate]
 
242
                    continue
 
243
                for ancestor in ancestors:
 
244
                    if ancestor in candidate_lca:
 
245
                        candidate_lca.remove(ancestor)
 
246
                        del searchers[ancestor]
 
247
                        if ancestor in active_searchers:
 
248
                            del active_searchers[ancestor]
 
249
                    for searcher in searchers.itervalues():
 
250
                        if ancestor not in searcher.seen:
 
251
                            break
 
252
                    else:
 
253
                        # if this revision was seen by all searchers, then it
 
254
                        # is a descendant of all candidates, so we can stop
 
255
                        # searching it, and any seen ancestors
 
256
                        for searcher in searchers.itervalues():
 
257
                            seen_ancestors =\
 
258
                                searcher.find_seen_ancestors(ancestor)
 
259
                            searcher.stop_searching_any(seen_ancestors)
 
260
        return candidate_lca
 
261
 
 
262
    def find_unique_lca(self, left_revision, right_revision):
 
263
        """Find a unique LCA.
 
264
 
 
265
        Find lowest common ancestors.  If there is no unique  common
 
266
        ancestor, find the lowest common ancestors of those ancestors.
 
267
 
 
268
        Iteration stops when a unique lowest common ancestor is found.
 
269
        The graph origin is necessarily a unique lowest common ancestor.
 
270
 
 
271
        Note that None is not an acceptable substitute for NULL_REVISION.
 
272
        in the input for this method.
 
273
        """
 
274
        revisions = [left_revision, right_revision]
 
275
        while True:
 
276
            lca = self.find_lca(*revisions)
 
277
            if len(lca) == 1:
 
278
                return lca.pop()
 
279
            if len(lca) == 0:
 
280
                raise errors.NoCommonAncestor(left_revision, right_revision)
 
281
            revisions = lca
 
282
 
 
283
    def iter_topo_order(self, revisions):
 
284
        """Iterate through the input revisions in topological order.
 
285
 
 
286
        This sorting only ensures that parents come before their children.
 
287
        An ancestor may sort after a descendant if the relationship is not
 
288
        visible in the supplied list of revisions.
 
289
        """
 
290
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
 
291
        return sorter.iter_topo_order()
 
292
 
 
293
 
 
294
class _BreadthFirstSearcher(object):
 
295
    """Parallel search the breadth-first the ancestry of revisions.
 
296
 
 
297
    This class implements the iterator protocol, but additionally
 
298
    1. provides a set of seen ancestors, and
 
299
    2. allows some ancestries to be unsearched, via stop_searching_any
 
300
    """
 
301
 
 
302
    def __init__(self, revisions, parents_provider):
 
303
        self._start = set(revisions)
 
304
        self._search_revisions = None
 
305
        self.seen = set(revisions)
 
306
        self._parents_provider = parents_provider 
 
307
 
 
308
    def __repr__(self):
 
309
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
 
310
                ' self.seen=%r)' % (self._search_revisions, self.seen))
 
311
 
 
312
    def next(self):
 
313
        """Return the next ancestors of this revision.
 
314
 
 
315
        Ancestors are returned in the order they are seen in a breadth-first
 
316
        traversal.  No ancestor will be returned more than once.
 
317
        """
 
318
        if self._search_revisions is None:
 
319
            self._search_revisions = self._start
 
320
        else:
 
321
            new_search_revisions = set()
 
322
            for parents in self._parents_provider.get_parents(
 
323
                self._search_revisions):
 
324
                if parents is None:
 
325
                    continue
 
326
                new_search_revisions.update(p for p in parents if
 
327
                                            p not in self.seen)
 
328
            self._search_revisions = new_search_revisions
 
329
        if len(self._search_revisions) == 0:
 
330
            raise StopIteration()
 
331
        self.seen.update(self._search_revisions)
 
332
        return self._search_revisions
 
333
 
 
334
    def __iter__(self):
 
335
        return self
 
336
 
 
337
    def find_seen_ancestors(self, revision):
 
338
        """Find ancestors of this revision that have already been seen."""
 
339
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
 
340
        seen_ancestors = set()
 
341
        for ancestors in searcher:
 
342
            for ancestor in ancestors:
 
343
                if ancestor not in self.seen:
 
344
                    searcher.stop_searching_any([ancestor])
 
345
                else:
 
346
                    seen_ancestors.add(ancestor)
 
347
        return seen_ancestors
 
348
 
 
349
    def stop_searching_any(self, revisions):
 
350
        """
 
351
        Remove any of the specified revisions from the search list.
 
352
 
 
353
        None of the specified revisions are required to be present in the
 
354
        search list.  In this case, the call is a no-op.
 
355
        """
 
356
        stopped = self._search_revisions.intersection(revisions)
 
357
        self._search_revisions = self._search_revisions.difference(revisions)
 
358
        return stopped
 
359
 
 
360
    def start_searching(self, revisions):
 
361
        if self._search_revisions is None:
 
362
            self._start = set(revisions)
 
363
        else:
 
364
            self._search_revisions.update(revisions.difference(self.seen))
 
365
        self.seen.update(revisions)