← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2009-04-30 14:04:38 UTC
  • mto: This revision was merged to the branch mainline in revision 4316.
  • Revision ID: aaron@aaronbentley.com-20090430140438-hpw2h918x4mpnpaw
Update from review

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 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,
23
22
    revision,
 
23
    symbol_versioning,
24
24
    trace,
 
25
    tsort,
25
26
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
28
28
STEP_UNIQUE_SEARCHER_EVERY = 5
29
29
 
60
60
        return 'DictParentsProvider(%r)' % self.ancestry
61
61
 
62
62
    def get_parent_map(self, keys):
63
 
        """See StackedParentsProvider.get_parent_map"""
 
63
        """See _StackedParentsProvider.get_parent_map"""
64
64
        ancestry = self.ancestry
65
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
66
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
 
 
71
 
class StackedParentsProvider(object):
72
 
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
74
 
    The providers are queries in the order of the provided parent_providers.
75
 
    """
76
 
    
 
67
 
 
68
class _StackedParentsProvider(object):
 
69
 
77
70
    def __init__(self, parent_providers):
78
71
        self._parent_providers = parent_providers
79
72
 
80
73
    def __repr__(self):
81
 
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
 
74
        return "_StackedParentsProvider(%r)" % self._parent_providers
82
75
 
83
76
    def get_parent_map(self, keys):
84
77
        """Get a mapping of keys => parents
155
148
        return dict(self._cache)
156
149
 
157
150
    def get_parent_map(self, keys):
158
 
        """See StackedParentsProvider.get_parent_map."""
 
151
        """See _StackedParentsProvider.get_parent_map."""
159
152
        cache = self._cache
160
153
        if cache is None:
161
154
            cache = self._get_parent_map(keys)
258
251
        right = searchers[1].seen
259
252
        return (left.difference(right), right.difference(left))
260
253
 
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
254
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
296
255
        """Find the left-hand distance to the NULL_REVISION.
297
256
 
345
304
        # get there.
346
305
        return known_revnos[cur_tip] + num_steps
347
306
 
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
 
 
369
307
    def find_unique_ancestors(self, unique_revision, common_revisions):
370
308
        """Find the unique ancestors for a revision versus others.
371
309
 
896
834
                stop.add(parent_id)
897
835
        return found
898
836
 
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
837
    def find_unique_lca(self, left_revision, right_revision,
920
838
                        count_steps=False):
921
839
        """Find a unique LCA.
973
891
                yield (ghost, None)
974
892
            pending = next_pending
975
893
 
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
894
    def iter_topo_order(self, revisions):
996
895
        """Iterate through the input revisions in topological order.
997
896
 
999
898
        An ancestor may sort after a descendant if the relationship is not
1000
899
        visible in the supplied list of revisions.
1001
900
        """
1002
 
        from bzrlib import tsort
1003
901
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1004
902
        return sorter.iter_topo_order()
1005
903
 
1658
1556
    def _get_keys(self, graph):
1659
1557
        NULL_REVISION = revision.NULL_REVISION
1660
1558
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1661
 
                if key != NULL_REVISION and parents is not None]
 
1559
                if key != NULL_REVISION]
1662
1560
        return keys
1663
1561
 
1664
1562
    def is_empty(self):
1750
1648
            removed.add(node)
1751
1649
 
1752
1650
    return result
1753
 
 
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
 
 
1774
 
_counters = [0,0,0,0,0,0,0]
1775
 
try:
1776
 
    from bzrlib._known_graph_pyx import KnownGraph
1777
 
except ImportError, e:
1778
 
    osutils.failed_to_load_extension(e)
1779
 
    from bzrlib._known_graph_py import KnownGraph