← 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-06-08 19:08:14 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: abentley@panoramicfeedback.com-20070608190814-a0dmj97o5osew1q8
Implement common-ancestor-based culling

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph_walker.py
112
112
 
113
113
        This will scale with the number of uncommon ancestors.
114
114
        """
 
115
        common_walker = _AncestryWalker([], self)
 
116
        common_ancestors = set()
115
117
        walkers = [_AncestryWalker([r], self) for r in revisions]
116
118
        active_walkers = walkers[:]
117
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
 
118
127
        while True:
119
128
            if len(active_walkers) == 0:
120
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
 
121
140
            newly_seen = set()
122
141
            new_active_walkers = []
123
142
            for walker in active_walkers:
129
148
                    new_active_walkers.append(walker)
130
149
            active_walkers = new_active_walkers
131
150
            for revision in newly_seen:
 
151
                if revision in common_ancestors:
 
152
                    for walker in walkers:
 
153
                        update_common(walker, revision)
 
154
                    continue
132
155
                for walker in walkers:
133
156
                    if revision not in walker.seen:
134
157
                        break
135
158
                else:
136
159
                    border_ancestors.add(revision)
137
160
                    for walker in walkers:
138
 
                        w_seen_ancestors = walker.find_seen_ancestors(
139
 
                            revision)
140
 
                        stopped = walker.stop_searching_any(w_seen_ancestors)
 
161
                        update_common(walker, revision)
141
162
 
142
163
    def _filter_candidate_lca(self, candidate_lca):
143
164
        """Remove candidates which are ancestors of other candidates.
276
297
 
277
298
    def start_searching(self, revisions):
278
299
        if self._search_revisions is None:
279
 
            self._start = revisions
 
300
            self._start = set(revisions)
280
301
        else:
281
302
            self._search_revisions.update(r for r in revisions if
282
303
                                          r not in self.seen)
 
304
        self.seen.update(revisions)