/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

  • Committer: Aaron Bentley
  • Date: 2007-06-08 21:48:42 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: abentley@panoramicfeedback.com-20070608214842-t47flt7htr2xz0yh
Rename graph to deprecated_graph

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.deprecated_graph import (node_distances, select_farthest)
 
18
from bzrlib.revision import NULL_REVISION
 
19
 
 
20
 
 
21
class _StackedParentsProvider(object):
 
22
 
 
23
    def __init__(self, parent_providers):
 
24
        self._parent_providers = parent_providers
 
25
 
 
26
    def get_parents(self, revision_ids):
 
27
        """
 
28
        Find revision ids of the parents of a list of revisions
 
29
 
 
30
        A list is returned of the same length as the input.  Each entry
 
31
        is a list of parent ids for the corresponding input revision.
 
32
 
 
33
        [NULL_REVISION] is used as the parent of the first user-committed
 
34
        revision.  Its parent list is empty.
 
35
 
 
36
        If the revision is not present (i.e. a ghost), None is used in place
 
37
        of the list of parents.
 
38
        """
 
39
        found = {}
 
40
        for parents_provider in self._parent_providers:
 
41
            parent_list = parents_provider.get_parents(
 
42
                [r for r in revision_ids if r not in found])
 
43
            new_found = dict((k, v) for k, v in zip(revision_ids, parent_list)
 
44
                             if v is not None)
 
45
            found.update(new_found)
 
46
            if len(found) == len(revision_ids):
 
47
                break
 
48
        return [found.get(r) for r in revision_ids]
 
49
 
 
50
 
 
51
class GraphWalker(object):
 
52
    """Provide incremental access to revision graphs.
 
53
 
 
54
    This is the generic implementation; it is intended to be subclassed to
 
55
    specialize it for other repository types.
 
56
    """
 
57
 
 
58
    def __init__(self, parents_provider):
 
59
        """Construct a GraphWalker that uses several graphs as its input
 
60
 
 
61
        This should not normally be invoked directly, because there may be
 
62
        specialized implementations for particular repository types.  See
 
63
        Repository.get_graph()
 
64
 
 
65
        :param parents_func: a list of objects providing a get_parents call
 
66
            conforming to the behavior of GraphWalker.get_parents
 
67
        """
 
68
        self.get_parents = parents_provider.get_parents
 
69
 
 
70
    def find_lca(self, *revisions):
 
71
        """Determine the lowest common ancestors of the provided revisions
 
72
 
 
73
        A lowest common ancestor is a common ancestor none of whose
 
74
        descendants are common ancestors.  In graphs, unlike trees, there may
 
75
        be multiple lowest common ancestors.
 
76
 
 
77
        This algorithm has two phases.  Phase 1 identifies border ancestors,
 
78
        and phase 2 filters border ancestors to determine lowest common
 
79
        ancestors.
 
80
 
 
81
        In phase 1, border ancestors are identified, using a breadth-first
 
82
        search starting at the bottom of the graph.  Searches are stopped
 
83
        whenever a node or one of its descendants is determined to be common
 
84
 
 
85
        In phase 2, the border ancestors are filtered to find the least
 
86
        common ancestors.  This is done by searching the ancestries of each
 
87
        border ancestor.
 
88
 
 
89
        Phase 2 is perfomed on the principle that a border ancestor that is
 
90
        not an ancestor of any other border ancestor is a least common
 
91
        ancestor.
 
92
 
 
93
        Searches are stopped when they find a node that is determined to be a
 
94
        common ancestor of all border ancestors, because this shows that it
 
95
        cannot be a descendant of any border ancestor.
 
96
 
 
97
        The scaling of this operation should be proportional to
 
98
        1. The number of uncommon ancestors
 
99
        2. The number of border ancestors
 
100
        3. The length of the shortest path between a border ancestor and an
 
101
           ancestor of all border ancestors.
 
102
        """
 
103
        border_common = self._find_border_ancestors(revisions)
 
104
        return self._filter_candidate_lca(border_common)
 
105
 
 
106
    def _find_border_ancestors(self, revisions):
 
107
        """Find common ancestors with at least one uncommon descendant.
 
108
 
 
109
        Border ancestors are identified using a breadth-first
 
110
        search starting at the bottom of the graph.  Searches are stopped
 
111
        whenever a node or one of its descendants is determined to be common.
 
112
 
 
113
        This will scale with the number of uncommon ancestors.
 
114
        """
 
115
        common_walker = _AncestryWalker([], self)
 
116
        common_ancestors = set()
 
117
        walkers = [_AncestryWalker([r], self) for r in revisions]
 
118
        active_walkers = walkers[:]
 
119
        border_ancestors = set()
 
120
        def update_common(walker, revisions):
 
121
            w_seen_ancestors = walker.find_seen_ancestors(
 
122
                revision)
 
123
            stopped = walker.stop_searching_any(w_seen_ancestors)
 
124
            common_ancestors.update(w_seen_ancestors)
 
125
            common_walker.start_searching(stopped)
 
126
 
 
127
        while True:
 
128
            if len(active_walkers) == 0:
 
129
                return border_ancestors
 
130
            try:
 
131
                new_common = common_walker.next()
 
132
                common_ancestors.update(new_common)
 
133
            except StopIteration:
 
134
                pass
 
135
            else:
 
136
                for walker in active_walkers:
 
137
                    for revision in new_common.intersection(walker.seen):
 
138
                        update_common(walker, revision)
 
139
 
 
140
            newly_seen = set()
 
141
            new_active_walkers = []
 
142
            for walker in active_walkers:
 
143
                try:
 
144
                    newly_seen.update(walker.next())
 
145
                except StopIteration:
 
146
                    pass
 
147
                else:
 
148
                    new_active_walkers.append(walker)
 
149
            active_walkers = new_active_walkers
 
150
            for revision in newly_seen:
 
151
                if revision in common_ancestors:
 
152
                    for walker in walkers:
 
153
                        update_common(walker, revision)
 
154
                    continue
 
155
                for walker in walkers:
 
156
                    if revision not in walker.seen:
 
157
                        break
 
158
                else:
 
159
                    border_ancestors.add(revision)
 
160
                    for walker in walkers:
 
161
                        update_common(walker, revision)
 
162
 
 
163
    def _filter_candidate_lca(self, candidate_lca):
 
164
        """Remove candidates which are ancestors of other candidates.
 
165
 
 
166
        This is done by searching the ancestries of each border ancestor.  It
 
167
        is perfomed on the principle that a border ancestor that is not an
 
168
        ancestor of any other border ancestor is a lowest common ancestor.
 
169
 
 
170
        Searches are stopped when they find a node that is determined to be a
 
171
        common ancestor of all border ancestors, because this shows that it
 
172
        cannot be a descendant of any border ancestor.
 
173
 
 
174
        This will scale with the number of candidate ancestors and the length
 
175
        of the shortest path from a candidate to an ancestor common to all
 
176
        candidates.
 
177
        """
 
178
        walkers = dict((c, _AncestryWalker([c], self))
 
179
                       for c in candidate_lca)
 
180
        active_walkers = dict(walkers)
 
181
        # skip over the actual candidate for each walker
 
182
        for walker in active_walkers.itervalues():
 
183
            walker.next()
 
184
        while len(active_walkers) > 0:
 
185
            for candidate, walker in list(active_walkers.iteritems()):
 
186
                try:
 
187
                    ancestors = walker.next()
 
188
                except StopIteration:
 
189
                    del active_walkers[candidate]
 
190
                    continue
 
191
                for ancestor in ancestors:
 
192
                    if ancestor in candidate_lca:
 
193
                        candidate_lca.remove(ancestor)
 
194
                        del walkers[ancestor]
 
195
                        if ancestor in active_walkers:
 
196
                            del active_walkers[ancestor]
 
197
                    for walker in walkers.itervalues():
 
198
                        if ancestor not in walker.seen:
 
199
                            break
 
200
                    else:
 
201
                        # if this revision was seen by all walkers, then it
 
202
                        # is a descendant of all candidates, so we can stop
 
203
                        # searching it, and any seen ancestors
 
204
                        for walker in walkers.itervalues():
 
205
                            seen_ancestors =\
 
206
                                walker.find_seen_ancestors(ancestor)
 
207
                            walker.stop_searching_any(seen_ancestors)
 
208
        return candidate_lca
 
209
 
 
210
    def find_unique_lca(self, left_revision, right_revision):
 
211
        """Find a unique LCA.
 
212
 
 
213
        Find lowest common ancestors.  If there is no unique  common
 
214
        ancestor, find the lowest common ancestors of those ancestors.
 
215
 
 
216
        Iteration stops when a unique lowest common ancestor is found.
 
217
        The graph origin is necessarily a unique lowest common ancestor.
 
218
 
 
219
        Note that None is not an acceptable substitute for NULL_REVISION.
 
220
        in the input for this method.
 
221
        """
 
222
        revisions = [left_revision, right_revision]
 
223
        while True:
 
224
            lca = self.find_lca(*revisions)
 
225
            if len(lca) == 1:
 
226
                return lca.pop()
 
227
            revisions = lca
 
228
 
 
229
 
 
230
class _AncestryWalker(object):
 
231
    """Walk the ancestry of a single revision.
 
232
 
 
233
    This class implements the iterator protocol, but additionally
 
234
    1. provides a set of seen ancestors, and
 
235
    2. allows some ancestries to be unsearched, via stop_searching_any
 
236
    """
 
237
 
 
238
    def __init__(self, revisions, graph_walker):
 
239
        self._start = set(revisions)
 
240
        self._search_revisions = None
 
241
        self.seen = set(revisions)
 
242
        self._graph_walker = graph_walker
 
243
 
 
244
    def __repr__(self):
 
245
        return '_AncestryWalker(self._search_revisions=%r, self.seen=%r)' %\
 
246
            (self._search_revisions, self.seen)
 
247
 
 
248
    def next(self):
 
249
        """Return the next ancestors of this revision.
 
250
 
 
251
        Ancestors are returned in the order they are seen in a breadth-first
 
252
        traversal.  No ancestor will be returned more than once.
 
253
        """
 
254
        if self._search_revisions is None:
 
255
            self._search_revisions = self._start
 
256
        else:
 
257
            new_search_revisions = set()
 
258
            for parents in self._graph_walker.get_parents(
 
259
                self._search_revisions):
 
260
                if parents is None:
 
261
                    continue
 
262
                new_search_revisions.update(p for p in parents if
 
263
                                            p not in self.seen)
 
264
            self._search_revisions = new_search_revisions
 
265
        if len(self._search_revisions) == 0:
 
266
            raise StopIteration()
 
267
        self.seen.update(self._search_revisions)
 
268
        return self._search_revisions
 
269
 
 
270
    def __iter__(self):
 
271
        return self
 
272
 
 
273
    def find_seen_ancestors(self, revision):
 
274
        """Find ancstors of this revision that have already been seen."""
 
275
        walker = _AncestryWalker([revision], self._graph_walker)
 
276
        seen_ancestors = set()
 
277
        for ancestors in walker:
 
278
            for ancestor in ancestors:
 
279
                if ancestor not in self.seen:
 
280
                    walker.stop_searching_any([ancestor])
 
281
                else:
 
282
                    seen_ancestors.add(ancestor)
 
283
        return seen_ancestors
 
284
 
 
285
    def stop_searching_any(self, revisions):
 
286
        """
 
287
        Remove any of the specified revisions from the search list.
 
288
 
 
289
        None of the specified revisions are required to be present in the
 
290
        search list.  In this case, the call is a no-op.
 
291
        """
 
292
        stopped_searches = set(l for l in self._search_revisions
 
293
                               if l in revisions)
 
294
        self._search_revisions = set(l for l in self._search_revisions
 
295
                                     if l not in revisions)
 
296
        return stopped_searches
 
297
 
 
298
    def start_searching(self, revisions):
 
299
        if self._search_revisions is None:
 
300
            self._start = set(revisions)
 
301
        else:
 
302
            self._search_revisions.update(r for r in revisions if
 
303
                                          r not in self.seen)
 
304
        self.seen.update(revisions)