← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Merge from bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
134
134
           ancestor of all border ancestors.
135
135
        """
136
136
        border_common, common, sides = self._find_border_ancestors(revisions)
137
 
        return self._filter_candidate_lca(border_common)
 
137
        # We may have common ancestors that can be reached from each other.
 
138
        # - ask for the heads of them to filter it down to only ones that
 
139
        # cannot be reached from each other - phase 2.
 
140
        return self.heads(border_common)
138
141
 
139
142
    def find_difference(self, left_revision, right_revision):
140
143
        """Determine the graph difference between two revisions"""
212
215
                    for searcher in searchers:
213
216
                        update_common(searcher, revision)
214
217
 
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.
 
218
    def heads(self, keys):
 
219
        """Return the heads from amongst keys.
 
220
 
 
221
        This is done by searching the ancestries of each key.  Any key that is
 
222
        reachable from another key is not returned; all the others are.
 
223
 
 
224
        This operation scales with the relative depth between any two keys. If
 
225
        any two keys are completely disconnected all ancestry of both sides
 
226
        will be retrieved.
 
227
 
 
228
        :param keys: An iterable of keys.
 
229
        :return: A set of the heads. Note that as a set there is no ordering
 
230
            information. Callers will need to filter their input to create
 
231
            order if they need it.
229
232
        """
 
233
        candidate_heads = set(keys)
 
234
        if len(candidate_heads) < 2:
 
235
            return candidate_heads
230
236
        searchers = dict((c, self._make_breadth_first_searcher([c]))
231
 
                          for c in candidate_lca)
 
237
                          for c in candidate_heads)
232
238
        active_searchers = dict(searchers)
233
239
        # skip over the actual candidate for each searcher
234
240
        for searcher in active_searchers.itervalues():
248
254
                    del active_searchers[candidate]
249
255
                    continue
250
256
                for ancestor in ancestors:
251
 
                    if ancestor in candidate_lca:
252
 
                        candidate_lca.remove(ancestor)
 
257
                    if ancestor in candidate_heads:
 
258
                        candidate_heads.remove(ancestor)
253
259
                        del searchers[ancestor]
254
260
                        if ancestor in active_searchers:
255
261
                            del active_searchers[ancestor]
264
270
                            seen_ancestors =\
265
271
                                searcher.find_seen_ancestors(ancestor)
266
272
                            searcher.stop_searching_any(seen_ancestors)
267
 
        return candidate_lca
 
273
        return candidate_heads
268
274
 
269
275
    def find_unique_lca(self, left_revision, right_revision):
270
276
        """Find a unique LCA.