/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-06-18 20:02:18 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: abentley@panoramicfeedback.com-20070618200218-pviwju0zlq1xgfq3
Update from review

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
17
17
from bzrlib.deprecated_graph import (node_distances, select_farthest)
18
18
from bzrlib.revision import NULL_REVISION
19
19
 
 
20
# DIAGRAM of terminology
 
21
#       A
 
22
#       /\
 
23
#      B  C
 
24
#      |  |\
 
25
#      D  E F
 
26
#      |\/| |
 
27
#      |/\|/
 
28
#      G  H
 
29
#
 
30
# In this diagram, relative to G and H:
 
31
# A, B, C, D, E are common ancestors.
 
32
# C, D and E are border ancestors, because each has a non-common descendant.
 
33
# D and E are least common ancestors because none of their descendants are
 
34
# common ancestors.
 
35
# C is not a least common ancestor because its descendant, E, is a common
 
36
# ancestor.
 
37
#
 
38
# The find_unique_lca algorithm will pick A in two steps:
 
39
# 1. find_lca('G', 'H') => ['D', 'E']
 
40
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
 
41
 
 
42
 
20
43
 
21
44
class _StackedParentsProvider(object):
22
45
 
24
47
        self._parent_providers = parent_providers
25
48
 
26
49
    def get_parents(self, revision_ids):
27
 
        """
28
 
        Find revision ids of the parents of a list of revisions
 
50
        """Find revision ids of the parents of a list of revisions
29
51
 
30
52
        A list is returned of the same length as the input.  Each entry
31
53
        is a list of parent ids for the corresponding input revision.
38
60
        """
39
61
        found = {}
40
62
        for parents_provider in self._parent_providers:
41
 
            parent_list = parents_provider.get_parents(
42
 
                [r for r in revision_ids if r not in found])
43
 
            new_found = dict((k, v) for k, v in zip(revision_ids, parent_list)
44
 
                             if v is not None)
 
63
            pending_revisions = [r for r in revision_ids if r not in found]
 
64
            parent_list = parents_provider.get_parents(pending_revisions)
 
65
            new_found = dict((k, v) for k, v in zip(pending_revisions,
 
66
                             parent_list) if v is not None)
45
67
            found.update(new_found)
46
68
            if len(found) == len(revision_ids):
47
69
                break
48
 
        return [found.get(r) for r in revision_ids]
 
70
        return [found.get(r, None) for r in revision_ids]
49
71
 
50
72
 
51
73
class Graph(object):
104
126
        return self._filter_candidate_lca(border_common)
105
127
 
106
128
    def find_difference(self, left_revision, right_revision):
 
129
        """Determine the graph difference between two revisions"""
107
130
        border, common, (left, right) = self._find_border_ancestors(
108
131
            [left_revision, right_revision])
109
132
        return (left.difference(right).difference(common),
120
143
        whenever a node or one of its descendants is determined to be common.
121
144
 
122
145
        This will scale with the number of uncommon ancestors.
 
146
 
 
147
        As well as the border ancestors, a set of seen common ancestors and a
 
148
        list of sets of seen ancestors for each input revision is returned.
 
149
        This allows calculation of graph difference from the results of this
 
150
        operation.
123
151
        """
124
152
        common_searcher = self._make_breadth_first_searcher([])
125
153
        common_ancestors = set()
253
281
        self._parents_provider = parents_provider 
254
282
 
255
283
    def __repr__(self):
256
 
        return '_BreadthFirstSearcher(self._search_revisions=%r,' \
257
 
            ' self.seen=%r)' % (self._search_revisions, self.seen)
 
284
        return ('_BreadthFirstSearcher(self._search_revisions=%r,'
 
285
                ' self.seen=%r)' % (self._search_revisions, self.seen))
258
286
 
259
287
    def next(self):
260
288
        """Return the next ancestors of this revision.
282
310
        return self
283
311
 
284
312
    def find_seen_ancestors(self, revision):
285
 
        """Find ancstors of this revision that have already been seen."""
 
313
        """Find ancestors of this revision that have already been seen."""
286
314
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
287
315
        seen_ancestors = set()
288
316
        for ancestors in searcher:
300
328
        None of the specified revisions are required to be present in the
301
329
        search list.  In this case, the call is a no-op.
302
330
        """
303
 
        stopped_searches = set(l for l in self._search_revisions
304
 
                               if l in revisions)
305
 
        self._search_revisions = set(l for l in self._search_revisions
306
 
                                     if l not in revisions)
307
 
        return stopped_searches
 
331
        stopped = self._search_revisions.intersection(revisions)
 
332
        self._search_revisions = self._search_revisions.difference(revisions)
 
333
        return stopped
308
334
 
309
335
    def start_searching(self, revisions):
310
336
        if self._search_revisions is None:
311
337
            self._start = set(revisions)
312
338
        else:
313
 
            self._search_revisions.update(r for r in revisions if
314
 
                                          r not in self.seen)
 
339
            self._search_revisions.update(revisions.difference(self.seen))
315
340
        self.seen.update(revisions)