/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: John Arbash Meinel
  • Date: 2007-12-20 12:34:06 UTC
  • mfrom: (3133 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3134.
  • Revision ID: john@arbash-meinel.com-20071220123406-4ijq232s46ecsutz
[merge] bzr.dev 3133

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
16
16
 
17
17
from bzrlib import (
18
18
    errors,
 
19
    revision,
 
20
    symbol_versioning,
19
21
    tsort,
20
22
    )
21
23
from bzrlib.deprecated_graph import (node_distances, select_farthest)
22
 
from bzrlib.revision import NULL_REVISION
23
24
 
24
25
# DIAGRAM of terminology
25
26
#       A
44
45
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
45
46
 
46
47
 
 
48
class DictParentsProvider(object):
 
49
 
 
50
    def __init__(self, ancestry):
 
51
        self.ancestry = ancestry
 
52
 
 
53
    def __repr__(self):
 
54
        return 'DictParentsProvider(%r)' % self.ancestry
 
55
 
 
56
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
 
57
    def get_parents(self, revisions):
 
58
        return [self.ancestry.get(r, None) for r in revisions]
 
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
 
47
65
 
48
66
class _StackedParentsProvider(object):
49
67
 
53
71
    def __repr__(self):
54
72
        return "_StackedParentsProvider(%r)" % self._parent_providers
55
73
 
 
74
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
56
75
    def get_parents(self, revision_ids):
57
76
        """Find revision ids of the parents of a list of revisions
58
77
 
65
84
        If the revision is not present (i.e. a ghost), None is used in place
66
85
        of the list of parents.
67
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
        """
68
103
        found = {}
 
104
        remaining = set(keys)
69
105
        for parents_provider in self._parent_providers:
70
 
            pending_revisions = [r for r in revision_ids if r not in found]
71
 
            parent_list = parents_provider.get_parents(pending_revisions)
72
 
            new_found = dict((k, v) for k, v in zip(pending_revisions,
73
 
                             parent_list) if v is not None)
 
106
            new_found = parents_provider.get_parent_map(remaining)
74
107
            found.update(new_found)
75
 
            if len(found) == len(revision_ids):
 
108
            remaining.difference_update(new_found)
 
109
            if not remaining:
76
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)
77
132
        return [found.get(r, None) for r in revision_ids]
78
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
 
79
158
 
80
159
class Graph(object):
81
160
    """Provide incremental access to revision graphs.
95
174
            conforming to the behavior of StackedParentsProvider.get_parents
96
175
        """
97
176
        self.get_parents = parents_provider.get_parents
 
177
        self.get_parent_map = parents_provider.get_parent_map
98
178
        self._parents_provider = parents_provider
99
179
 
100
180
    def __repr__(self):
231
311
            order if they need it.
232
312
        """
233
313
        candidate_heads = set(keys)
 
314
        if revision.NULL_REVISION in candidate_heads:
 
315
            # NULL_REVISION is only a head if it is the only entry
 
316
            candidate_heads.remove(revision.NULL_REVISION)
 
317
            if not candidate_heads:
 
318
                return set([revision.NULL_REVISION])
234
319
        if len(candidate_heads) < 2:
235
320
            return candidate_heads
236
321
        searchers = dict((c, self._make_breadth_first_searcher([c]))
299
384
            common_walker.start_searching(new_common)
300
385
        return candidate_heads
301
386
 
302
 
    def find_unique_lca(self, left_revision, right_revision):
 
387
    def find_unique_lca(self, left_revision, right_revision,
 
388
                        count_steps=False):
303
389
        """Find a unique LCA.
304
390
 
305
391
        Find lowest common ancestors.  If there is no unique  common
310
396
 
311
397
        Note that None is not an acceptable substitute for NULL_REVISION.
312
398
        in the input for this method.
 
399
 
 
400
        :param count_steps: If True, the return value will be a tuple of
 
401
            (unique_lca, steps) where steps is the number of times that
 
402
            find_lca was run.  If False, only unique_lca is returned.
313
403
        """
314
404
        revisions = [left_revision, right_revision]
 
405
        steps = 0
315
406
        while True:
 
407
            steps += 1
316
408
            lca = self.find_lca(*revisions)
317
409
            if len(lca) == 1:
318
 
                return lca.pop()
 
410
                result = lca.pop()
 
411
                if count_steps:
 
412
                    return result, steps
 
413
                else:
 
414
                    return result
319
415
            if len(lca) == 0:
320
416
                raise errors.NoCommonAncestor(left_revision, right_revision)
321
417
            revisions = lca
327
423
        An ancestor may sort after a descendant if the relationship is not
328
424
        visible in the supplied list of revisions.
329
425
        """
330
 
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
 
426
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
331
427
        return sorter.iter_topo_order()
332
428
 
333
429
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
334
430
        """Determine whether a revision is an ancestor of another.
335
431
 
336
432
        We answer this using heads() as heads() has the logic to perform the
337
 
        smallest number of parent looksup to determine the ancestral
 
433
        smallest number of parent lookups to determine the ancestral
338
434
        relationship between N revisions.
339
435
        """
340
436
        return set([candidate_descendant]) == self.heads(
405
501
        self._start = set(revisions)
406
502
        self._search_revisions = None
407
503
        self.seen = set(revisions)
408
 
        self._parents_provider = parents_provider 
 
504
        self._parents_provider = parents_provider
409
505
 
410
506
    def __repr__(self):
411
 
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
412
 
                ' 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)))
413
513
 
414
514
    def next(self):
415
515
        """Return the next ancestors of this revision.
421
521
            self._search_revisions = self._start
422
522
        else:
423
523
            new_search_revisions = set()
424
 
            for parents in self._parents_provider.get_parents(
425
 
                self._search_revisions):
426
 
                if parents is None:
427
 
                    continue
 
524
            parent_map = self._parents_provider.get_parent_map(
 
525
                            self._search_revisions)
 
526
            for parents in parent_map.itervalues():
428
527
                new_search_revisions.update(p for p in parents if
429
528
                                            p not in self.seen)
430
529
            self._search_revisions = new_search_revisions