/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2007-12-19 06:04:19 UTC
  • mfrom: (3127 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3128.
  • Revision ID: aaron.bentley@utoronto.ca-20071219060419-afwva4q14cjlzfta
Merge with bzr.dev

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,
20
21
    tsort,
21
22
    )
22
23
from bzrlib.deprecated_graph import (node_distances, select_farthest)
52
53
    def __repr__(self):
53
54
        return 'DictParentsProvider(%r)' % self.ancestry
54
55
 
 
56
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
55
57
    def get_parents(self, revisions):
56
58
        return [self.ancestry.get(r, None) for r in revisions]
57
59
 
 
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
 
58
65
 
59
66
class _StackedParentsProvider(object):
60
67
 
64
71
    def __repr__(self):
65
72
        return "_StackedParentsProvider(%r)" % self._parent_providers
66
73
 
 
74
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
67
75
    def get_parents(self, revision_ids):
68
76
        """Find revision ids of the parents of a list of revisions
69
77
 
76
84
        If the revision is not present (i.e. a ghost), None is used in place
77
85
        of the list of parents.
78
86
        """
 
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
        """
79
103
        found = {}
 
104
        remaining = set(keys)
80
105
        for parents_provider in self._parent_providers:
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)
 
106
            new_found = parents_provider.get_parent_map(remaining)
85
107
            found.update(new_found)
86
 
            if len(found) == len(revision_ids):
 
108
            remaining.difference_update(new_found)
 
109
            if not remaining:
87
110
                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)
88
132
        return [found.get(r, None) for r in revision_ids]
89
133
 
 
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
 
90
158
 
91
159
class Graph(object):
92
160
    """Provide incremental access to revision graphs.
106
174
            conforming to the behavior of StackedParentsProvider.get_parents
107
175
        """
108
176
        self.get_parents = parents_provider.get_parents
 
177
        self.get_parent_map = parents_provider.get_parent_map
109
178
        self._parents_provider = parents_provider
110
179
 
111
180
    def __repr__(self):
354
423
        An ancestor may sort after a descendant if the relationship is not
355
424
        visible in the supplied list of revisions.
356
425
        """
357
 
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
 
426
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
358
427
        return sorter.iter_topo_order()
359
428
 
360
429
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
432
501
        self._start = set(revisions)
433
502
        self._search_revisions = None
434
503
        self.seen = set(revisions)
435
 
        self._parents_provider = parents_provider 
 
504
        self._parents_provider = parents_provider
436
505
 
437
506
    def __repr__(self):
438
 
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
439
 
                ' self.seen=%r)' % (self._search_revisions, self.seen))
 
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)))
440
513
 
441
514
    def next(self):
442
515
        """Return the next ancestors of this revision.
448
521
            self._search_revisions = self._start
449
522
        else:
450
523
            new_search_revisions = set()
451
 
            for parents in self._parents_provider.get_parents(
452
 
                self._search_revisions):
453
 
                if parents is None:
454
 
                    continue
 
524
            parent_map = self._parents_provider.get_parent_map(
 
525
                            self._search_revisions)
 
526
            for parents in parent_map.itervalues():
455
527
                new_search_revisions.update(p for p in parents if
456
528
                                            p not in self.seen)
457
529
            self._search_revisions = new_search_revisions