← 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-26 17:24:21 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: aaron.bentley@utoronto.ca-20070526172421-16cyxl6ttbmsdfco
Start implementing mca that scales with number of uncommon ancestors

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph_walker.py
68
68
        descendants are common ancestors.  (This is not quite the standard
69
69
        graph theory definition)
70
70
        """
71
 
        common = set(self._get_ancestry(revisions[0]))
72
 
        for revision in revisions[1:]:
73
 
            common.intersection_update(self._get_ancestry(revision))
74
 
        common.add(NULL_REVISION)
75
 
        mca = set()
76
 
        for ancestor in common:
77
 
            if len([d for d in self._descendants[0].get(ancestor, []) if d in
78
 
                    common]) == 0:
79
 
                mca.add(ancestor)
80
 
        return mca
 
71
        walkers = [_AncestryWalker(r, self) for r in revisions]
 
72
        active_walkers = walkers[:]
 
73
        maybe_minimal_common = set()
 
74
        seen_ancestors = set()
 
75
        while True:
 
76
            if len(active_walkers) == 0:
 
77
                maybe_minimal_common.difference_update(seen_ancestors)
 
78
                return maybe_minimal_common
 
79
            newly_seen = set()
 
80
            new_active_walkers = []
 
81
            for walker in active_walkers:
 
82
                try:
 
83
                    newly_seen.update(walker.next())
 
84
                except StopIteration:
 
85
                    pass
 
86
                else:
 
87
                    new_active_walkers.append(walker)
 
88
            active_walkers = new_active_walkers
 
89
            for revision in newly_seen:
 
90
                for walker in walkers:
 
91
                    if revision not in walker.seen:
 
92
                        break
 
93
                else:
 
94
                    maybe_minimal_common.add(revision)
 
95
                    for walker in walkers:
 
96
                        w_seen_ancestors = walker.find_seen_ancestors(revision)
 
97
                        walker.stop_tracing_any(w_seen_ancestors)
 
98
                        w_seen_ancestors.discard(revision)
 
99
                        seen_ancestors.update(w_seen_ancestors)
81
100
 
82
101
    def unique_common(self, left_revision, right_revision):
83
102
        """Find a unique minimal common ancestor.
97
116
                return minimal.pop()
98
117
            revisions = minimal
99
118
 
 
119
    def get_parents(self, revision):
 
120
        for ancestors in self._ancestors:
 
121
            try:
 
122
                return ancestors[revision]
 
123
            except KeyError:
 
124
                pass
 
125
        else:
 
126
            raise KeyError
 
127
 
100
128
    def _get_ancestry(self, revision):
101
129
        if revision == NULL_REVISION:
102
130
            ancestry = []
112
140
                raise KeyError(revision)
113
141
        ancestry.append(NULL_REVISION)
114
142
        return ancestry
 
143
 
 
144
 
 
145
class _AncestryWalker(object):
 
146
    """Walk the ancestry of a single revision"""
 
147
 
 
148
    def __init__(self, revision, graph_walker):
 
149
        self._start = set([revision])
 
150
        self._lines = None
 
151
        self.seen = set()
 
152
        self._graph_walker = graph_walker
 
153
 
 
154
    def __repr__(self):
 
155
        return '_AncestryWalker(self._lines=%r, self.seen=%r)' %\
 
156
            (self._lines, self.seen)
 
157
 
 
158
    def next(self):
 
159
        """Return the next parents of this revision"""
 
160
        if self._lines is None:
 
161
            self._lines = self._start
 
162
        else:
 
163
            new_lines = set()
 
164
            for revision in self._lines:
 
165
                new_lines.update(p for p in
 
166
                                 self._graph_walker.get_parents(revision) if p
 
167
                                 not in self.seen)
 
168
            self._lines = new_lines
 
169
        if len(self._lines) == 0:
 
170
            raise StopIteration()
 
171
        self.seen.update(self._lines)
 
172
        return self._lines
 
173
 
 
174
    def make_iterator(self):
 
175
        while True:
 
176
            yield self.next()
 
177
 
 
178
    def find_seen_ancestors(self, revision):
 
179
        """Find ancstors of this revision that have already been seen."""
 
180
        walker = _AncestryWalker(revision, self._graph_walker)
 
181
        seen_ancestors = set()
 
182
        for ancestors in walker.make_iterator():
 
183
            for ancestor in ancestors:
 
184
                if ancestor not in self.seen:
 
185
                    walker.stop_tracing_any([ancestor])
 
186
                else:
 
187
                    seen_ancestors.add(ancestor)
 
188
        return seen_ancestors
 
189
 
 
190
    def stop_tracing_any(self, revisions):
 
191
        self._lines = set(l for l in self._lines if l not in revisions)