~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Martin Pool
  • Date: 2005-05-03 08:00:27 UTC
  • Revision ID: mbp@sourcefrog.net-20050503080027-908edb5b39982198
doc

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 in active_searchers.keys():
238
 
                try:
239
 
                    searcher = active_searchers[candidate]
240
 
                except KeyError:
241
 
                    # rare case: we deleted candidate in a previous iteration
242
 
                    # through this for loop, because it was determined to be
243
 
                    # a descendant of another candidate.
244
 
                    continue
245
 
                try:
246
 
                    ancestors = searcher.next()
247
 
                except StopIteration:
248
 
                    del active_searchers[candidate]
249
 
                    continue
250
 
                for ancestor in ancestors:
251
 
                    if ancestor in candidate_lca:
252
 
                        candidate_lca.remove(ancestor)
253
 
                        del searchers[ancestor]
254
 
                        if ancestor in active_searchers:
255
 
                            del active_searchers[ancestor]
256
 
                    for searcher in searchers.itervalues():
257
 
                        if ancestor not in searcher.seen:
258
 
                            break
259
 
                    else:
260
 
                        # if this revision was seen by all searchers, then it
261
 
                        # is a descendant of all candidates, so we can stop
262
 
                        # searching it, and any seen ancestors
263
 
                        for searcher in searchers.itervalues():
264
 
                            seen_ancestors =\
265
 
                                searcher.find_seen_ancestors(ancestor)
266
 
                            searcher.stop_searching_any(seen_ancestors)
267
 
        return candidate_lca
268
 
 
269
 
    def find_unique_lca(self, left_revision, right_revision):
270
 
        """Find a unique LCA.
271
 
 
272
 
        Find lowest common ancestors.  If there is no unique  common
273
 
        ancestor, find the lowest common ancestors of those ancestors.
274
 
 
275
 
        Iteration stops when a unique lowest common ancestor is found.
276
 
        The graph origin is necessarily a unique lowest common ancestor.
277
 
 
278
 
        Note that None is not an acceptable substitute for NULL_REVISION.
279
 
        in the input for this method.
280
 
        """
281
 
        revisions = [left_revision, right_revision]
282
 
        while True:
283
 
            lca = self.find_lca(*revisions)
284
 
            if len(lca) == 1:
285
 
                return lca.pop()
286
 
            if len(lca) == 0:
287
 
                raise errors.NoCommonAncestor(left_revision, right_revision)
288
 
            revisions = lca
289
 
 
290
 
    def iter_topo_order(self, revisions):
291
 
        """Iterate through the input revisions in topological order.
292
 
 
293
 
        This sorting only ensures that parents come before their children.
294
 
        An ancestor may sort after a descendant if the relationship is not
295
 
        visible in the supplied list of revisions.
296
 
        """
297
 
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
298
 
        return sorter.iter_topo_order()
299
 
 
300
 
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
301
 
        """Determine whether a revision is an ancestor of another.
302
 
 
303
 
        There are two possible outcomes: True and False, but there are three
304
 
        possible relationships:
305
 
 
306
 
        a) candidate_ancestor is an ancestor of candidate_descendant
307
 
        b) candidate_ancestor is an descendant of candidate_descendant
308
 
        c) candidate_ancestor is an sibling of candidate_descendant
309
 
 
310
 
        To check for a, we walk from candidate_descendant, looking for
311
 
        candidate_ancestor.
312
 
 
313
 
        To check for b, we walk from candidate_ancestor, looking for
314
 
        candidate_descendant.
315
 
 
316
 
        To make a and b more efficient, we can stop any searches that hit
317
 
        common ancestors.
318
 
 
319
 
        If we exhaust our searches, but neither a or b is true, then c is true.
320
 
 
321
 
        In order to find c efficiently, we must avoid searching from
322
 
        candidate_descendant or candidate_ancestor into common ancestors.  But
323
 
        if we don't search common ancestors at all, we won't know if we hit
324
 
        common ancestors.  So we have a walker for common ancestors.  Note that
325
 
        its searches are not required to terminate in order to determine c to
326
 
        be true.
327
 
        """
328
 
        ancestor_walker = self._make_breadth_first_searcher(
329
 
            [candidate_ancestor])
330
 
        descendant_walker = self._make_breadth_first_searcher(
331
 
            [candidate_descendant])
332
 
        common_walker = self._make_breadth_first_searcher([])
333
 
        active_ancestor = True
334
 
        active_descendant = True
335
 
        while (active_ancestor or active_descendant):
336
 
            new_common = set()
337
 
            if active_descendant:
338
 
                try:
339
 
                    nodes = descendant_walker.next()
340
 
                except StopIteration:
341
 
                    active_descendant = False
342
 
                else:
343
 
                    if candidate_ancestor in nodes:
344
 
                        return True
345
 
                    new_common.update(nodes.intersection(ancestor_walker.seen))
346
 
            if active_ancestor:
347
 
                try:
348
 
                    nodes = ancestor_walker.next()
349
 
                except StopIteration:
350
 
                    active_ancestor = False
351
 
                else:
352
 
                    if candidate_descendant in nodes:
353
 
                        return False
354
 
                    new_common.update(nodes.intersection(
355
 
                        descendant_walker.seen))
356
 
            try:
357
 
                new_common.update(common_walker.next())
358
 
            except StopIteration:
359
 
                pass
360
 
            for walker in (ancestor_walker, descendant_walker):
361
 
                for node in new_common:
362
 
                    c_ancestors = walker.find_seen_ancestors(node)
363
 
                    walker.stop_searching_any(c_ancestors)
364
 
                common_walker.start_searching(new_common)
365
 
        return False
366
 
 
367
 
 
368
 
class _BreadthFirstSearcher(object):
369
 
    """Parallel search the breadth-first the ancestry of revisions.
370
 
 
371
 
    This class implements the iterator protocol, but additionally
372
 
    1. provides a set of seen ancestors, and
373
 
    2. allows some ancestries to be unsearched, via stop_searching_any
374
 
    """
375
 
 
376
 
    def __init__(self, revisions, parents_provider):
377
 
        self._start = set(revisions)
378
 
        self._search_revisions = None
379
 
        self.seen = set(revisions)
380
 
        self._parents_provider = parents_provider 
381
 
 
382
 
    def __repr__(self):
383
 
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
384
 
                ' self.seen=%r)' % (self._search_revisions, self.seen))
385
 
 
386
 
    def next(self):
387
 
        """Return the next ancestors of this revision.
388
 
 
389
 
        Ancestors are returned in the order they are seen in a breadth-first
390
 
        traversal.  No ancestor will be returned more than once.
391
 
        """
392
 
        if self._search_revisions is None:
393
 
            self._search_revisions = self._start
394
 
        else:
395
 
            new_search_revisions = set()
396
 
            for parents in self._parents_provider.get_parents(
397
 
                self._search_revisions):
398
 
                if parents is None:
399
 
                    continue
400
 
                new_search_revisions.update(p for p in parents if
401
 
                                            p not in self.seen)
402
 
            self._search_revisions = new_search_revisions
403
 
        if len(self._search_revisions) == 0:
404
 
            raise StopIteration()
405
 
        self.seen.update(self._search_revisions)
406
 
        return self._search_revisions
407
 
 
408
 
    def __iter__(self):
409
 
        return self
410
 
 
411
 
    def find_seen_ancestors(self, revision):
412
 
        """Find ancestors of this revision that have already been seen."""
413
 
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
414
 
        seen_ancestors = set()
415
 
        for ancestors in searcher:
416
 
            for ancestor in ancestors:
417
 
                if ancestor not in self.seen:
418
 
                    searcher.stop_searching_any([ancestor])
419
 
                else:
420
 
                    seen_ancestors.add(ancestor)
421
 
        return seen_ancestors
422
 
 
423
 
    def stop_searching_any(self, revisions):
424
 
        """
425
 
        Remove any of the specified revisions from the search list.
426
 
 
427
 
        None of the specified revisions are required to be present in the
428
 
        search list.  In this case, the call is a no-op.
429
 
        """
430
 
        stopped = self._search_revisions.intersection(revisions)
431
 
        self._search_revisions = self._search_revisions.difference(revisions)
432
 
        return stopped
433
 
 
434
 
    def start_searching(self, revisions):
435
 
        if self._search_revisions is None:
436
 
            self._start = set(revisions)
437
 
        else:
438
 
            self._search_revisions.update(revisions.difference(self.seen))
439
 
        self.seen.update(revisions)