← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2008-06-06 16:40:46 UTC
  • mfrom: (3482 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3483.
  • Revision ID: aaron@aaronbentley.com-20080606164046-ghbxplxuhtpcb9iz
Merge with bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
212
212
        right = searchers[1].seen
213
213
        return (left.difference(right), right.difference(left))
214
214
 
 
215
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
 
216
        """Find the left-hand distance to the NULL_REVISION.
 
217
 
 
218
        (This can also be considered the revno of a branch at
 
219
        target_revision_id.)
 
220
 
 
221
        :param target_revision_id: A revision_id which we would like to know
 
222
            the revno for.
 
223
        :param known_revision_ids: [(revision_id, revno)] A list of known
 
224
            revno, revision_id tuples. We'll use this to seed the search.
 
225
        """
 
226
        # Map from revision_ids to a known value for their revno
 
227
        known_revnos = dict(known_revision_ids)
 
228
        cur_tip = target_revision_id
 
229
        num_steps = 0
 
230
        NULL_REVISION = revision.NULL_REVISION
 
231
        known_revnos[NULL_REVISION] = 0
 
232
 
 
233
        searching_known_tips = list(known_revnos.keys())
 
234
 
 
235
        unknown_searched = {}
 
236
 
 
237
        while cur_tip not in known_revnos:
 
238
            unknown_searched[cur_tip] = num_steps
 
239
            num_steps += 1
 
240
            to_search = set([cur_tip])
 
241
            to_search.update(searching_known_tips)
 
242
            parent_map = self.get_parent_map(to_search)
 
243
            parents = parent_map.get(cur_tip, None)
 
244
            if not parents: # An empty list or None is a ghost
 
245
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
 
246
                                                       cur_tip)
 
247
            cur_tip = parents[0]
 
248
            next_known_tips = []
 
249
            for revision_id in searching_known_tips:
 
250
                parents = parent_map.get(revision_id, None)
 
251
                if not parents:
 
252
                    continue
 
253
                next = parents[0]
 
254
                next_revno = known_revnos[revision_id] - 1
 
255
                if next in unknown_searched:
 
256
                    # We have enough information to return a value right now
 
257
                    return next_revno + unknown_searched[next]
 
258
                if next in known_revnos:
 
259
                    continue
 
260
                known_revnos[next] = next_revno
 
261
                next_known_tips.append(next)
 
262
            searching_known_tips = next_known_tips
 
263
 
 
264
        # We reached a known revision, so just add in how many steps it took to
 
265
        # get there.
 
266
        return known_revnos[cur_tip] + num_steps
 
267
 
215
268
    def find_unique_ancestors(self, unique_revision, common_revisions):
216
269
        """Find the unique ancestors for a revision versus others.
217
270