← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph_walker.py

  • Committer: Aaron Bentley
  • Date: 2007-05-30 15:18:12 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: abentley@panoramicfeedback.com-20070530151812-brau3xwf2568qqsb
Improve documentation

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph_walker.py
32
32
        specialized implementations for particular repository types.  See
33
33
        Repository.get_graph_walker()
34
34
 
35
 
        Note that the imput graphs *will* be altered to use NULL_REVISION as
 
35
        Note that the input graphs *will* be altered to use NULL_REVISION as
36
36
        their origin.
37
37
        """
38
38
        self._graph = graphs
79
79
 
80
80
        A distinct common ancestor is a common ancestor none of whose
81
81
        descendants are common ancestors.
 
82
 
 
83
        This algorithm has two phases.  Phase 1 identifies border ancestors,
 
84
        and phase 2 filters border ancestors to determine distinct ancestors.
 
85
 
 
86
        In phase 1, border ancestors are identified, using a breadth-first
 
87
        search starting at the bottom of the graph.  Searches are stopped
 
88
        whenever a node or one of its descendants is determined to be common
 
89
 
 
90
        In phase 2, the border ancestors are filtered to find the distinct
 
91
        common ancestors.  This is done by searching the ancestries of each
 
92
        border ancestor.
 
93
 
 
94
        Phase 2 is perfomed on the principle that a border ancestor that is not
 
95
        an ancestor of any other border ancestor is a distinct ancestor.
 
96
 
 
97
        Searches are stopped when they find a node that is determined to be a
 
98
        common ancestor of all border ancestors, because this shows that it
 
99
        cannot be a descendant of any border ancestor.
 
100
 
 
101
        The scaling of this operation should be proportional to
 
102
        1. The number of uncommon ancestors
 
103
        2. The number of border ancestors
 
104
        3. The length of the shortest path between a border ancestor and an
 
105
           ancestor of all border ancestors.
82
106
        """
83
107
        border_common = self._find_border_ancestors(revisions)
84
108
        return self._filter_candidate_dca(border_common)
85
109
 
86
110
    def _find_border_ancestors(self, revisions):
87
 
        """Find common ancestors with at least one uncommon descendant"""
 
111
        """Find common ancestors with at least one uncommon descendant.
 
112
 
 
113
        Border ancestors are identified using a breadth-first
 
114
        search starting at the bottom of the graph.  Searches are stopped
 
115
        whenever a node or one of its descendants is determined to be common.
 
116
 
 
117
        This will scale with the number of uncommon ancestors.
 
118
        """
88
119
        walkers = [_AncestryWalker(r, self) for r in revisions]
89
120
        active_walkers = walkers[:]
90
121
        maybe_distinct_common = set()
113
144
                        walker.stop_searching_any(w_seen_ancestors)
114
145
 
115
146
    def _filter_candidate_dca(self, candidate_dca):
116
 
        """Remove candidates which are ancestors of other candidates"""
 
147
        """Remove candidates which are ancestors of other candidates.
 
148
 
 
149
        This is done by searching the ancestries of each border ancestor.  It
 
150
        is perfomed on the principle that a border ancestor that is not an
 
151
        ancestor of any other border ancestor is a distinct ancestor.
 
152
 
 
153
        Searches are stopped when they find a node that is determined to be a
 
154
        common ancestor of all border ancestors, because this shows that it
 
155
        cannot be a descendant of any border ancestor.
 
156
 
 
157
        This will scale with the number of candidate ancestors and the length
 
158
        of the shortest path from a candidate to an ancestor common to all
 
159
        candidates.
 
160
        """
117
161
        walkers = dict((c, _AncestryWalker(c, self)) for c in candidate_dca)
118
162
        active_walkers = dict(walkers)
119
163
        # skip over the actual candidate for each walker
195
239
    def next(self):
196
240
        """Return the next ancestors of this revision.
197
241
 
198
 
        Ancestors are returned in the order they are seen.  No ancestor will
199
 
        be returned more than once.
 
242
        Ancestors are returned in the order they are seen in a breadth-first
 
243
        traversal.  No ancestor will be returned more than once.
200
244
        """
201
245
        if self._search_revisions is None:
202
246
            self._search_revisions = self._start
232
276
        Remove any of the specified revisions from the search list.
233
277
 
234
278
        None of the specified revisions are required to be present in the
235
 
        search list.
 
279
        search list.  In this case, the call is a no-op.
236
280
        """
237
281
        self._search_revisions = set(l for l in self._search_revisions
238
282
                                     if l not in revisions)