← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Andrew Bennetts
  • Date: 2010-09-23 07:40:07 UTC
  • mfrom: (5050.17.24 2.2)
  • mto: This revision was merged to the branch mainline in revision 5440.
  • Revision ID: andrew.bennetts@canonical.com-20100923074007-bqk101393z4npbw0
Merge lp:bzr/2.2.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
258
258
        right = searchers[1].seen
259
259
        return (left.difference(right), right.difference(left))
260
260
 
261
 
    def find_descendants(self, old_key, new_key):
262
 
        """Find descendants of old_key that are ancestors of new_key."""
263
 
        child_map = self.get_child_map(self._find_descendant_ancestors(
264
 
            old_key, new_key))
265
 
        graph = Graph(DictParentsProvider(child_map))
266
 
        searcher = graph._make_breadth_first_searcher([old_key])
267
 
        list(searcher)
268
 
        return searcher.seen
269
 
 
270
 
    def _find_descendant_ancestors(self, old_key, new_key):
271
 
        """Find ancestors of new_key that may be descendants of old_key."""
272
 
        stop = self._make_breadth_first_searcher([old_key])
273
 
        descendants = self._make_breadth_first_searcher([new_key])
274
 
        for revisions in descendants:
275
 
            old_stop = stop.seen.intersection(revisions)
276
 
            descendants.stop_searching_any(old_stop)
277
 
            seen_stop = descendants.find_seen_ancestors(stop.step())
278
 
            descendants.stop_searching_any(seen_stop)
279
 
        return descendants.seen.difference(stop.seen)
280
 
 
281
 
    def get_child_map(self, keys):
282
 
        """Get a mapping from parents to children of the specified keys.
283
 
 
284
 
        This is simply the inversion of get_parent_map.  Only supplied keys
285
 
        will be discovered as children.
286
 
        :return: a dict of key:child_list for keys.
287
 
        """
288
 
        parent_map = self._parents_provider.get_parent_map(keys)
289
 
        parent_child = {}
290
 
        for child, parents in sorted(parent_map.items()):
291
 
            for parent in parents:
292
 
                parent_child.setdefault(parent, []).append(child)
293
 
        return parent_child
294
 
 
295
261
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
296
262
        """Find the left-hand distance to the NULL_REVISION.
297
263
 
896
862
                stop.add(parent_id)
897
863
        return found
898
864
 
899
 
    def find_lefthand_merger(self, merged_key, tip_key):
900
 
        """Find the first lefthand ancestor of tip_key that merged merged_key.
901
 
 
902
 
        We do this by first finding the descendants of merged_key, then
903
 
        walking through the lefthand ancestry of tip_key until we find a key
904
 
        that doesn't descend from merged_key.  Its child is the key that
905
 
        merged merged_key.
906
 
 
907
 
        :return: The first lefthand ancestor of tip_key to merge merged_key.
908
 
            merged_key if it is a lefthand ancestor of tip_key.
909
 
            None if no ancestor of tip_key merged merged_key.
910
 
        """
911
 
        descendants = self.find_descendants(merged_key, tip_key)
912
 
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
913
 
        last_candidate = None
914
 
        for candidate in candidate_iterator:
915
 
            if candidate not in descendants:
916
 
                return last_candidate
917
 
            last_candidate = candidate
918
 
 
919
865
    def find_unique_lca(self, left_revision, right_revision,
920
866
                        count_steps=False):
921
867
        """Find a unique LCA.
973
919
                yield (ghost, None)
974
920
            pending = next_pending
975
921
 
976
 
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
977
 
        if stop_keys is None:
978
 
            stop_keys = ()
979
 
        next_key = start_key
980
 
        def get_parents(key):
981
 
            try:
982
 
                return self._parents_provider.get_parent_map([key])[key]
983
 
            except KeyError:
984
 
                raise errors.RevisionNotPresent(next_key, self)
985
 
        while True:
986
 
            if next_key in stop_keys:
987
 
                return
988
 
            parents = get_parents(next_key)
989
 
            yield next_key
990
 
            if len(parents) == 0:
991
 
                return
992
 
            else:
993
 
                next_key = parents[0]
994
 
 
995
922
    def iter_topo_order(self, revisions):
996
923
        """Iterate through the input revisions in topological order.
997
924