← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-03-24 05:12:24 UTC
  • mfrom: (4189.1.1 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20090324051224-rneg6bkbzjyd85rl
(mbp) merge update to FSF address

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
128
121
            self._get_parent_map = self._real_provider.get_parent_map
129
122
        else:
130
123
            self._get_parent_map = get_parent_map
131
 
        self._cache = None
132
 
        self.enable_cache(True)
 
124
        self._cache = {}
 
125
        self._cache_misses = True
133
126
 
134
127
    def __repr__(self):
135
128
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
140
133
            raise AssertionError('Cache enabled when already enabled.')
141
134
        self._cache = {}
142
135
        self._cache_misses = cache_misses
143
 
        self.missing_keys = set()
144
136
 
145
137
    def disable_cache(self):
146
138
        """Disable and clear the cache."""
147
139
        self._cache = None
148
 
        self._cache_misses = None
149
 
        self.missing_keys = set()
150
140
 
151
141
    def get_cached_map(self):
152
142
        """Return any cached get_parent_map values."""
153
143
        if self._cache is None:
154
144
            return None
155
 
        return dict(self._cache)
 
145
        return dict((k, v) for k, v in self._cache.items()
 
146
                    if v is not None)
156
147
 
157
148
    def get_parent_map(self, keys):
158
 
        """See StackedParentsProvider.get_parent_map."""
159
 
        cache = self._cache
160
 
        if cache is None:
161
 
            cache = self._get_parent_map(keys)
 
149
        """See _StackedParentsProvider.get_parent_map."""
 
150
        # Hack to build up the caching logic.
 
151
        ancestry = self._cache
 
152
        if ancestry is None:
 
153
            # Caching is disabled.
 
154
            missing_revisions = set(keys)
 
155
            ancestry = {}
162
156
        else:
163
 
            needed_revisions = set(key for key in keys if key not in cache)
164
 
            # Do not ask for negatively cached keys
165
 
            needed_revisions.difference_update(self.missing_keys)
166
 
            if needed_revisions:
167
 
                parent_map = self._get_parent_map(needed_revisions)
168
 
                cache.update(parent_map)
169
 
                if self._cache_misses:
170
 
                    for key in needed_revisions:
171
 
                        if key not in parent_map:
172
 
                            self.note_missing_key(key)
173
 
        result = {}
174
 
        for key in keys:
175
 
            value = cache.get(key)
176
 
            if value is not None:
177
 
                result[key] = value
178
 
        return result
179
 
 
180
 
    def note_missing_key(self, key):
181
 
        """Note that key is a missing key."""
182
 
        if self._cache_misses:
183
 
            self.missing_keys.add(key)
 
157
            missing_revisions = set(key for key in keys if key not in ancestry)
 
158
        if missing_revisions:
 
159
            parent_map = self._get_parent_map(missing_revisions)
 
160
            ancestry.update(parent_map)
 
161
            if self._cache_misses:
 
162
                # None is never a valid parents list, so it can be used to
 
163
                # record misses.
 
164
                ancestry.update(dict((k, None) for k in missing_revisions
 
165
                                     if k not in parent_map))
 
166
        present_keys = [k for k in keys if ancestry.get(k) is not None]
 
167
        return dict((k, ancestry[k]) for k in present_keys)
184
168
 
185
169
 
186
170
class Graph(object):
311
295
        # get there.
312
296
        return known_revnos[cur_tip] + num_steps
313
297
 
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
 
 
335
298
    def find_unique_ancestors(self, unique_revision, common_revisions):
336
299
        """Find the unique ancestors for a revision versus others.
337
300
 
926
889
        An ancestor may sort after a descendant if the relationship is not
927
890
        visible in the supplied list of revisions.
928
891
        """
929
 
        from bzrlib import tsort
930
892
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
893
        return sorter.iter_topo_order()
932
894
 
1489
1451
 
1490
1452
        The recipe allows reconstruction of the same results at a later date
1491
1453
        without knowing all the found keys. The essential elements are a list
1492
 
        of keys to start and to stop at. In order to give reproducible
 
1454
        of keys to start and and to stop at. In order to give reproducible
1493
1455
        results when ghosts are encountered by a search they are automatically
1494
1456
        added to the exclude list (or else ghost filling may alter the
1495
1457
        results).
1515
1477
        return self._keys
1516
1478
 
1517
1479
    def is_empty(self):
1518
 
        """Return false if the search lists 1 or more revisions."""
 
1480
        """Return true if the search lists 1 or more revisions."""
1519
1481
        return self._recipe[3] == 0
1520
1482
 
1521
1483
    def refine(self, seen, referenced):
1585
1547
    def _get_keys(self, graph):
1586
1548
        NULL_REVISION = revision.NULL_REVISION
1587
1549
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1588
 
                if key != NULL_REVISION and parents is not None]
 
1550
                if key != NULL_REVISION]
1589
1551
        return keys
1590
1552
 
1591
1553
    def is_empty(self):
1592
 
        """Return false if the search lists 1 or more revisions."""
 
1554
        """Return true if the search lists 1 or more revisions."""
1593
1555
        if revision.NULL_REVISION in self.heads:
1594
1556
            return len(self.heads) == 1
1595
1557
        else:
1677
1639
            removed.add(node)
1678
1640
 
1679
1641
    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