← 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:56:18 UTC
  • mto: This revision was merged to the branch mainline in revision 5452.
  • Revision ID: john@arbash-meinel.com-20100929205618-qlldxw4ykwt5511n
Move the new NEWS entry to the appropriate section.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
19
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
 
22
    osutils,
22
23
    revision,
23
24
    trace,
24
 
    tsort,
25
25
    )
26
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
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
 
311
345
        # get there.
312
346
        return known_revnos[cur_tip] + num_steps
313
347
 
 
348
    def find_lefthand_distances(self, keys):
 
349
        """Find the distance to null for all the keys in keys.
 
350
 
 
351
        :param keys: keys to lookup.
 
352
        :return: A dict key->distance for all of keys.
 
353
        """
 
354
        # Optimisable by concurrent searching, but a random spread should get
 
355
        # some sort of hit rate.
 
356
        result = {}
 
357
        known_revnos = []
 
358
        ghosts = []
 
359
        for key in keys:
 
360
            try:
 
361
                known_revnos.append(
 
362
                    (key, self.find_distance_to_null(key, known_revnos)))
 
363
            except errors.GhostRevisionsHaveNoRevno:
 
364
                ghosts.append(key)
 
365
        for key in ghosts:
 
366
            known_revnos.append((key, -1))
 
367
        return dict(known_revnos)
 
368
 
314
369
    def find_unique_ancestors(self, unique_revision, common_revisions):
315
370
        """Find the unique ancestors for a revision versus others.
316
371
 
841
896
                stop.add(parent_id)
842
897
        return found
843
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
 
844
919
    def find_unique_lca(self, left_revision, right_revision,
845
920
                        count_steps=False):
846
921
        """Find a unique LCA.
898
973
                yield (ghost, None)
899
974
            pending = next_pending
900
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
 
901
995
    def iter_topo_order(self, revisions):
902
996
        """Iterate through the input revisions in topological order.
903
997
 
905
999
        An ancestor may sort after a descendant if the relationship is not
906
1000
        visible in the supplied list of revisions.
907
1001
        """
 
1002
        from bzrlib import tsort
908
1003
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
909
1004
        return sorter.iter_topo_order()
910
1005
 
1657
1752
    return result
1658
1753
 
1659
1754
 
 
1755
class GraphThunkIdsToKeys(object):
 
1756
    """Forwards calls about 'ids' to be about keys internally."""
 
1757
 
 
1758
    def __init__(self, graph):
 
1759
        self._graph = graph
 
1760
 
 
1761
    def topo_sort(self):
 
1762
        return [r for (r,) in self._graph.topo_sort()]
 
1763
 
 
1764
    def heads(self, ids):
 
1765
        """See Graph.heads()"""
 
1766
        as_keys = [(i,) for i in ids]
 
1767
        head_keys = self._graph.heads(as_keys)
 
1768
        return set([h[0] for h in head_keys])
 
1769
 
 
1770
    def merge_sort(self, tip_revision):
 
1771
        return self._graph.merge_sort((tip_revision,))
 
1772
 
 
1773
 
1660
1774
_counters = [0,0,0,0,0,0,0]
1661
1775
try:
1662
1776
    from bzrlib._known_graph_pyx import KnownGraph
1663
 
except ImportError:
 
1777
except ImportError, e:
 
1778
    osutils.failed_to_load_extension(e)
1664
1779
    from bzrlib._known_graph_py import KnownGraph