← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2010-09-29 20:18:37 UTC
  • mfrom: (5450 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5452.
  • Revision ID: john@arbash-meinel.com-20100929201837-6d9jhvjokfe3ubvk
Merge bzr.dev 5450 to resolve NEWS and criss-cross merge.

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
 
261
295
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
296
        """Find the left-hand distance to the NULL_REVISION.
263
297
 
862
896
                stop.add(parent_id)
863
897
        return found
864
898
 
 
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
 
865
919
    def find_unique_lca(self, left_revision, right_revision,
866
920
                        count_steps=False):
867
921
        """Find a unique LCA.
919
973
                yield (ghost, None)
920
974
            pending = next_pending
921
975
 
 
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
 
922
995
    def iter_topo_order(self, revisions):
923
996
        """Iterate through the input revisions in topological order.
924
997