← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

* Deprecated method ``find_previous_heads`` on
  ``bzrlib.inventory.InventoryEntry``. This has been superceded by the use
  of ``parent_candidates`` and a separate heads check via the repository
  API. (Robert Collins)

* New public method ``heads`` on the ``bzrlib.graph.Graph`` class. This is
  a simple rename of a previously internal method which implements the same
  semantics as heads(). (Robert Collins, John A Meinel)

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.
229
230
        """
 
231
        candidate_lca = set(keys)
230
232
        searchers = dict((c, self._make_breadth_first_searcher([c]))
231
233
                          for c in candidate_lca)
232
234
        active_searchers = dict(searchers)