← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph_walker.py

  • Committer: Aaron Bentley
  • Date: 2007-05-30 01:17:03 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: aaron.bentley@utoronto.ca-20070530011703-tgvzbyonqsol27e5
Clarify text, remove unused _get_ancestry method

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph_walker.py
19
19
 
20
20
 
21
21
class GraphWalker(object):
22
 
    """Provide incremental access to revision graphs"""
 
22
    """Provide incremental access to revision graphs.
 
23
 
 
24
    This is the generic implementation; it is intended to be subclassed to
 
25
    specialize it for other repository types.
 
26
    """
23
27
 
24
28
    def __init__(self, graphs):
 
29
        """Construct a GraphWalker that uses several graphs as its input
 
30
 
 
31
        This should not normally be invoked directly, because there may be
 
32
        specialized implementations for particular repository types.  See
 
33
        Repository.get_graph_walker()
 
34
 
 
35
        Note that the imput graphs *will* be altered to use NULL_REVISION as
 
36
        their origin.
 
37
        """
25
38
        self._graph = graphs
26
39
        self._ancestors = []
27
40
        self._descendants = []
68
81
        descendants are common ancestors.  (This is not quite the standard
69
82
        graph theory definition)
70
83
        """
71
 
        candidate_mca = self._find_candidate_mca(revisions)
72
 
        return self._filter_candidate_mca(candidate_mca)
 
84
        border_common = self._find_border_ancestors(revisions)
 
85
        return self._filter_candidate_mca(border_common)
73
86
 
74
 
    def _find_candidate_mca(self, revisions):
 
87
    def _find_border_ancestors(self, revisions):
 
88
        """Find common ancestors with at least one uncommon descendant"""
75
89
        walkers = [_AncestryWalker(r, self) for r in revisions]
76
90
        active_walkers = walkers[:]
77
91
        maybe_minimal_common = set()
97
111
                    maybe_minimal_common.add(revision)
98
112
                    for walker in walkers:
99
113
                        w_seen_ancestors = walker.find_seen_ancestors(revision)
100
 
                        walker.stop_tracing_any(w_seen_ancestors)
 
114
                        walker.stop_searching_any(w_seen_ancestors)
101
115
 
102
116
    def _filter_candidate_mca(self, candidate_mca):
103
117
        """Remove candidates which are ancestors of other candidates"""
125
139
                    else:
126
140
                        # if this revision was seen by all walkers, then it
127
141
                        # is a descendant of all candidates, so we can stop
128
 
                        # tracing it, and any seen ancestors
 
142
                        # searching it, and any seen ancestors
129
143
                        for walker in walkers.itervalues():
130
144
                            seen_ancestors =\
131
145
                                walker.find_seen_ancestors(ancestor)
132
 
                            walker.stop_tracing_any(seen_ancestors)
 
146
                            walker.stop_searching_any(seen_ancestors)
133
147
        return candidate_mca
134
148
 
135
149
    def unique_common(self, left_revision, right_revision):
151
165
            revisions = minimal
152
166
 
153
167
    def get_parents(self, revision):
 
168
        """Determine the parents of a revision"""
154
169
        for ancestors in self._ancestors:
155
170
            try:
156
171
                return ancestors[revision]
159
174
        else:
160
175
            raise KeyError
161
176
 
162
 
    def _get_ancestry(self, revision):
163
 
        if revision == NULL_REVISION:
164
 
            ancestry = []
165
 
        else:
166
 
            for graph in self._graph:
167
 
                try:
168
 
                    ancestry = graph.get_ancestry(revision)
169
 
                except KeyError:
170
 
                    pass
171
 
                else:
172
 
                    break
173
 
            else:
174
 
                raise KeyError(revision)
175
 
        ancestry.append(NULL_REVISION)
176
 
        return ancestry
177
 
 
178
177
 
179
178
class _AncestryWalker(object):
180
 
    """Walk the ancestry of a single revision"""
 
179
    """Walk the ancestry of a single revision.
 
180
 
 
181
    This class implements the iterator protocol, but additionally
 
182
    1. provides a set of seen ancestors, and
 
183
    2. allows some ancestries to be unsearched, via stop_searching_any
 
184
    """
181
185
 
182
186
    def __init__(self, revision, graph_walker):
183
187
        self._start = set([revision])
184
 
        self._lines = None
 
188
        self._search_revisions = None
185
189
        self.seen = set()
186
190
        self._graph_walker = graph_walker
187
191
 
188
192
    def __repr__(self):
189
 
        return '_AncestryWalker(self._lines=%r, self.seen=%r)' %\
190
 
            (self._lines, self.seen)
 
193
        return '_AncestryWalker(self._search_revisions=%r, self.seen=%r)' %\
 
194
            (self._search_revisions, self.seen)
191
195
 
192
196
    def next(self):
193
 
        """Return the next parents of this revision"""
194
 
        if self._lines is None:
195
 
            self._lines = self._start
 
197
        """Return the next ancestors of this revision.
 
198
 
 
199
        Ancestors are returned in the order they are seen.  No ancestor will
 
200
        be returned more than once.
 
201
        """
 
202
        if self._search_revisions is None:
 
203
            self._search_revisions = self._start
196
204
        else:
197
 
            new_lines = set()
198
 
            for revision in self._lines:
199
 
                new_lines.update(p for p in
 
205
            new_search_revisions = set()
 
206
            for revision in self._search_revisions:
 
207
                new_search_revisions.update(p for p in
200
208
                                 self._graph_walker.get_parents(revision) if p
201
209
                                 not in self.seen)
202
 
            self._lines = new_lines
203
 
        if len(self._lines) == 0:
 
210
            self._search_revisions = new_search_revisions
 
211
        if len(self._search_revisions) == 0:
204
212
            raise StopIteration()
205
 
        self.seen.update(self._lines)
206
 
        return self._lines
 
213
        self.seen.update(self._search_revisions)
 
214
        return self._search_revisions
207
215
 
208
216
    def __iter__(self):
209
217
        return self
215
223
        for ancestors in walker:
216
224
            for ancestor in ancestors:
217
225
                if ancestor not in self.seen:
218
 
                    walker.stop_tracing_any([ancestor])
 
226
                    walker.stop_searching_any([ancestor])
219
227
                else:
220
228
                    seen_ancestors.add(ancestor)
221
229
        return seen_ancestors
222
230
 
223
 
    def stop_tracing_any(self, revisions):
224
 
        self._lines = set(l for l in self._lines if l not in revisions)
 
231
    def stop_searching_any(self, revisions):
 
232
        """
 
233
        Remove any of the specified revisions from the search list.
 
234
 
 
235
        None of the specified revisions are required to be present in the
 
236
        search list.
 
237
        """
 
238
        self._search_revisions = set(l for l in self._search_revisions
 
239
                                     if l not in revisions)