← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2009-04-04 01:45:09 UTC
  • mfrom: (3873.3.2 trivial)
  • mto: This revision was merged to the branch mainline in revision 4290.
  • Revision ID: jelmer@samba.org-20090404014509-qworcvw6gemoajoo
Merge in Martins' IPv6 literals patch.

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
 
1562
1460
 
1563
1461
        The recipe allows reconstruction of the same results at a later date
1564
1462
        without knowing all the found keys. The essential elements are a list
1565
 
        of keys to start and to stop at. In order to give reproducible
 
1463
        of keys to start and and to stop at. In order to give reproducible
1566
1464
        results when ghosts are encountered by a search they are automatically
1567
1465
        added to the exclude list (or else ghost filling may alter the
1568
1466
        results).
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