/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: 2008-05-21 19:02:34 UTC
  • mto: This revision was merged to the branch mainline in revision 3460.
  • Revision ID: john@arbash-meinel.com-20080521190234-oijes1jniav97axe
Start working on a new Graph api to make finding revision numbers faster.

The current implementation traverses all ancestors. We'll do better by seeding the
information with known revisions.

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_revno(self, target_revision_id, known_revision_ids):
 
216
        """Determine the revno for target_revision_id.
 
217
 
 
218
        :param target_revision_id: A revision_id which we would like to know
 
219
            the revno for.
 
220
        :param known_revision_ids: [(revision_id, revno)] A list of known
 
221
            revno, revision_id tuples. We'll use this to seed the search.
 
222
        """
 
223
        # Map from revision_ids to a known value for their revno
 
224
        known_revnos = dict(known_revision_ids)
 
225
        cur_tip = target_revision_id
 
226
        num_steps = 0
 
227
        NULL_REVISION = revision.NULL_REVISION
 
228
 
 
229
        while cur_tip != NULL_REVISION:
 
230
            parent_map = self.get_parent_map([cur_tip])
 
231
            parents = parent_map.get(cur_tip, None)
 
232
            if not parents: # An empty list, or None is still a ghost
 
233
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
 
234
                                                       cur_tip)
 
235
            num_steps += 1
 
236
            cur_tip = parents[0]
 
237
 
 
238
        # We reached NULL_REVISION, so the total distance is num_steps + 1
 
239
        return num_steps
 
240
 
215
241
    def find_unique_ancestors(self, unique_revision, common_revisions):
216
242
        """Find the unique ancestors for a revision versus others.
217
243