← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007 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
 
    symbol_versioning,
24
24
    trace,
25
 
    tsort,
26
25
    )
 
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
 
 
68
 
class _StackedParentsProvider(object):
69
 
 
 
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
    
70
77
    def __init__(self, parent_providers):
71
78
        self._parent_providers = parent_providers
72
79
 
73
80
    def __repr__(self):
74
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
81
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
82
 
76
83
    def get_parent_map(self, keys):
77
84
        """Get a mapping of keys => parents
148
155
        return dict(self._cache)
149
156
 
150
157
    def get_parent_map(self, keys):
151
 
        """See _StackedParentsProvider.get_parent_map."""
 
158
        """See StackedParentsProvider.get_parent_map."""
152
159
        cache = self._cache
153
160
        if cache is None:
154
161
            cache = self._get_parent_map(keys)
304
311
        # get there.
305
312
        return known_revnos[cur_tip] + num_steps
306
313
 
 
314
    def find_lefthand_distances(self, keys):
 
315
        """Find the distance to null for all the keys in keys.
 
316
 
 
317
        :param keys: keys to lookup.
 
318
        :return: A dict key->distance for all of keys.
 
319
        """
 
320
        # Optimisable by concurrent searching, but a random spread should get
 
321
        # some sort of hit rate.
 
322
        result = {}
 
323
        known_revnos = []
 
324
        ghosts = []
 
325
        for key in keys:
 
326
            try:
 
327
                known_revnos.append(
 
328
                    (key, self.find_distance_to_null(key, known_revnos)))
 
329
            except errors.GhostRevisionsHaveNoRevno:
 
330
                ghosts.append(key)
 
331
        for key in ghosts:
 
332
            known_revnos.append((key, -1))
 
333
        return dict(known_revnos)
 
334
 
307
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
308
336
        """Find the unique ancestors for a revision versus others.
309
337
 
898
926
        An ancestor may sort after a descendant if the relationship is not
899
927
        visible in the supplied list of revisions.
900
928
        """
 
929
        from bzrlib import tsort
901
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
902
931
        return sorter.iter_topo_order()
903
932
 
1556
1585
    def _get_keys(self, graph):
1557
1586
        NULL_REVISION = revision.NULL_REVISION
1558
1587
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1559
 
                if key != NULL_REVISION]
 
1588
                if key != NULL_REVISION and parents is not None]
1560
1589
        return keys
1561
1590
 
1562
1591
    def is_empty(self):
1648
1677
            removed.add(node)
1649
1678
 
1650
1679
    return result
 
1680
 
 
1681
 
 
1682
class GraphThunkIdsToKeys(object):
 
1683
    """Forwards calls about 'ids' to be about keys internally."""
 
1684
 
 
1685
    def __init__(self, graph):
 
1686
        self._graph = graph
 
1687
 
 
1688
    def topo_sort(self):
 
1689
        return [r for (r,) in self._graph.topo_sort()]
 
1690
 
 
1691
    def heads(self, ids):
 
1692
        """See Graph.heads()"""
 
1693
        as_keys = [(i,) for i in ids]
 
1694
        head_keys = self._graph.heads(as_keys)
 
1695
        return set([h[0] for h in head_keys])
 
1696
 
 
1697
    def merge_sort(self, tip_revision):
 
1698
        return self._graph.merge_sort((tip_revision,))
 
1699
 
 
1700
 
 
1701
_counters = [0,0,0,0,0,0,0]
 
1702
try:
 
1703
    from bzrlib._known_graph_pyx import KnownGraph
 
1704
except ImportError, e:
 
1705
    osutils.failed_to_load_extension(e)
 
1706
    from bzrlib._known_graph_py import KnownGraph