← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Ian Clatworthy
  • Date: 2007-12-17 01:45:32 UTC
  • mto: (3119.1.1 ianc-integration)
  • mto: This revision was merged to the branch mainline in revision 3120.
  • Revision ID: ian.clatworthy@internode.on.net-20071217014532-dmbv2mm72nzq0ai6
follow-up tweaks to bzr.dev integration

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
17
17
from bzrlib import (
18
18
    errors,
19
19
    revision,
20
 
    symbol_versioning,
21
20
    tsort,
22
21
    )
23
22
from bzrlib.deprecated_graph import (node_distances, select_farthest)
53
52
    def __repr__(self):
54
53
        return 'DictParentsProvider(%r)' % self.ancestry
55
54
 
56
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
57
55
    def get_parents(self, revisions):
58
56
        return [self.ancestry.get(r, None) for r in revisions]
59
57
 
60
 
    def get_parent_map(self, keys):
61
 
        """See _StackedParentsProvider.get_parent_map"""
62
 
        ancestry = self.ancestry
63
 
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
64
 
 
65
58
 
66
59
class _StackedParentsProvider(object):
67
60
 
71
64
    def __repr__(self):
72
65
        return "_StackedParentsProvider(%r)" % self._parent_providers
73
66
 
74
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
75
67
    def get_parents(self, revision_ids):
76
68
        """Find revision ids of the parents of a list of revisions
77
69
 
84
76
        If the revision is not present (i.e. a ghost), None is used in place
85
77
        of the list of parents.
86
78
        """
87
 
        found = self.get_parent_map(revision_ids)
88
 
        return [found.get(r, None) for r in revision_ids]
89
 
 
90
 
    def get_parent_map(self, keys):
91
 
        """Get a mapping of keys => parents
92
 
 
93
 
        A dictionary is returned with an entry for each key present in this
94
 
        source. If this source doesn't have information about a key, it should
95
 
        not include an entry.
96
 
 
97
 
        [NULL_REVISION] is used as the parent of the first user-committed
98
 
        revision.  Its parent list is empty.
99
 
 
100
 
        :param keys: An iterable returning keys to check (eg revision_ids)
101
 
        :return: A dictionary mapping each key to its parents
102
 
        """
103
79
        found = {}
104
 
        remaining = set(keys)
105
80
        for parents_provider in self._parent_providers:
106
 
            new_found = parents_provider.get_parent_map(remaining)
 
81
            pending_revisions = [r for r in revision_ids if r not in found]
 
82
            parent_list = parents_provider.get_parents(pending_revisions)
 
83
            new_found = dict((k, v) for k, v in zip(pending_revisions,
 
84
                             parent_list) if v is not None)
107
85
            found.update(new_found)
108
 
            remaining.difference_update(new_found)
109
 
            if not remaining:
 
86
            if len(found) == len(revision_ids):
110
87
                break
111
 
        return found
112
 
 
113
 
 
114
 
class CachingParentsProvider(object):
115
 
    """A parents provider which will cache the revision => parents in a dict.
116
 
 
117
 
    This is useful for providers that have an expensive lookup.
118
 
    """
119
 
 
120
 
    def __init__(self, parent_provider):
121
 
        self._real_provider = parent_provider
122
 
        # Theoretically we could use an LRUCache here
123
 
        self._cache = {}
124
 
 
125
 
    def __repr__(self):
126
 
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
127
 
 
128
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
129
 
    def get_parents(self, revision_ids):
130
 
        """See _StackedParentsProvider.get_parents"""
131
 
        found = self.get_parent_map(revision_ids)
132
88
        return [found.get(r, None) for r in revision_ids]
133
89
 
134
 
    def get_parent_map(self, keys):
135
 
        """See _StackedParentsProvider.get_parent_map"""
136
 
        needed = set()
137
 
        # If the _real_provider doesn't have a key, we cache a value of None,
138
 
        # which we then later use to realize we cannot provide a value for that
139
 
        # key.
140
 
        parent_map = {}
141
 
        cache = self._cache
142
 
        for key in keys:
143
 
            if key in cache:
144
 
                value = cache[key]
145
 
                if value is not None:
146
 
                    parent_map[key] = value
147
 
            else:
148
 
                needed.add(key)
149
 
 
150
 
        if needed:
151
 
            new_parents = self._real_provider.get_parent_map(needed)
152
 
            cache.update(new_parents)
153
 
            parent_map.update(new_parents)
154
 
            needed.difference_update(new_parents)
155
 
            cache.update(dict.fromkeys(needed, None))
156
 
        return parent_map
157
 
 
158
90
 
159
91
class Graph(object):
160
92
    """Provide incremental access to revision graphs.
174
106
            conforming to the behavior of StackedParentsProvider.get_parents
175
107
        """
176
108
        self.get_parents = parents_provider.get_parents
177
 
        self.get_parent_map = parents_provider.get_parent_map
178
109
        self._parents_provider = parents_provider
179
110
 
180
111
    def __repr__(self):
423
354
        An ancestor may sort after a descendant if the relationship is not
424
355
        visible in the supplied list of revisions.
425
356
        """
426
 
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
 
357
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
427
358
        return sorter.iter_topo_order()
428
359
 
429
360
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
501
432
        self._start = set(revisions)
502
433
        self._search_revisions = None
503
434
        self.seen = set(revisions)
504
 
        self._parents_provider = parents_provider
 
435
        self._parents_provider = parents_provider 
505
436
 
506
437
    def __repr__(self):
507
 
        if self._search_revisions is not None:
508
 
            search = 'searching=%r' % (list(self._search_revisions),)
509
 
        else:
510
 
            search = 'starting=%r' % (list(self._start),)
511
 
        return ('_BreadthFirstSearcher(%s,'
512
 
                ' seen=%r)' % (search, list(self.seen)))
 
438
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
 
439
                ' self.seen=%r)' % (self._search_revisions, self.seen))
513
440
 
514
441
    def next(self):
515
442
        """Return the next ancestors of this revision.
521
448
            self._search_revisions = self._start
522
449
        else:
523
450
            new_search_revisions = set()
524
 
            parent_map = self._parents_provider.get_parent_map(
525
 
                            self._search_revisions)
526
 
            for parents in parent_map.itervalues():
 
451
            for parents in self._parents_provider.get_parents(
 
452
                self._search_revisions):
 
453
                if parents is None:
 
454
                    continue
527
455
                new_search_revisions.update(p for p in parents if
528
456
                                            p not in self.seen)
529
457
            self._search_revisions = new_search_revisions