← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-03-15 21:00:35 UTC
  • mfrom: (3228.4.15 revision_graph)
  • Revision ID: pqm@pqm.ubuntu.com-20080315210035-5qwda8bre2nwsra3
(jam) Update PackRepo.get_revision_graph() to efficiently handle
        ghosts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
424
424
                raise errors.NoCommonAncestor(left_revision, right_revision)
425
425
            revisions = lca
426
426
 
 
427
    def iter_ancestry(self, revision_ids):
 
428
        """Iterate the ancestry of this revision.
 
429
 
 
430
        :param revision_ids: Nodes to start the search
 
431
        :return: Yield tuples mapping a revision_id to its parents for the
 
432
            ancestry of revision_id.
 
433
            Ghosts will be returned with None as their parents, and nodes
 
434
            with no parents will have NULL_REVISION as their only parent. (As
 
435
            defined by get_parent_map.)
 
436
            There will also be a node for (NULL_REVISION, ())
 
437
        """
 
438
        pending = set(revision_ids)
 
439
        processed = set()
 
440
        while pending:
 
441
            processed.update(pending)
 
442
            next_map = self.get_parent_map(pending)
 
443
            next_pending = set()
 
444
            for item in next_map.iteritems():
 
445
                yield item
 
446
                next_pending.update(p for p in item[1] if p not in processed)
 
447
            ghosts = pending.difference(next_map)
 
448
            for ghost in ghosts:
 
449
                yield (ghost, None)
 
450
            pending = next_pending
 
451
 
427
452
    def iter_topo_order(self, revisions):
428
453
        """Iterate through the input revisions in topological order.
429
454