[MERGE] Repository.get_revision_graph improvements

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Arbash Meinel wrote:
> 2) Introduce Graph.iter_ancestry() which returns similar information.

bb:resubmit

I would be more comfortable with iter_ancestry if there was a
distinction made between revisions with no parents and ghost revisions.
 The obvious idea would be for ghosts to have None as their parent list.

It can be useful to detect ghost revisions, and your use case,
get_revision_graph, already does this.  I think using None would help
clarify this, while avoiding special-casing NULL_REVISION.

Another use case for ghosts would be looking for ghost revisions in a
different repository, i.e. stacking.


> === modified file 'bzrlib/graph.py'
> --- bzrlib/graph.py	2008-02-03 22:55:08 +0000
> +++ bzrlib/graph.py	2008-02-25 22:41:36 +0000
> @@ -424,6 +424,37 @@
>                  raise errors.NoCommonAncestor(left_revision, right_revision)
>              revisions = lca
>  
> +    def iter_ancestry(self, revision_ids):
> +        """Iterate the ancestry of this revision.
> +
> +        The specific order is undefined, but children should be returned before
> +        parents.

^^^ I don't think this is necessarily true; what about history shortcuts?

> === modified file 'bzrlib/repofmt/pack_repo.py'
> --- bzrlib/repofmt/pack_repo.py	2008-02-19 03:58:32 +0000
> +++ bzrlib/repofmt/pack_repo.py	2008-02-26 00:03:15 +0000
> @@ -1926,6 +1926,53 @@
>              found_parents[key[0]] = parents
>          return found_parents
>  
> +    @needs_read_lock
> +    def get_revision_graph(self, revision_id=None):
> +        """Return a dictionary containing the revision graph.
> +
> +        :param revision_id: The revision_id to get a graph from. If None, then
> +        the entire revision graph is returned. This is a deprecated mode of
> +        operation and will be removed in the future.
> +        :return: a dictionary of revision_id->revision_parents_list.
> +        """
> +        if 'evil' in debug.debug_flags:
> +            mutter_callsite(3,
> +                "get_revision_graph scales with size of history.")
> +        # special case NULL_REVISION
> +        if revision_id == _mod_revision.NULL_REVISION:
> +            return {}
> +        a_weave = self._get_revision_vf()

Urgh, why are you calling this a weave?

And since you're going to use a Graph in a minute, why not just use
Graph.get_parents_map to find out if the revision is present?  At least
you have a chance of caching that way.

> +        if revision_id is None:
> +            return a_weave.get_graph()
> +        if revision_id not in a_weave:
> +            raise errors.NoSuchRevision(self, revision_id)

^^^ Since it is expensive to determine whether revision_id is in the
"weave", it's probably worth avoiding the test here.  You can get this
from the iter_ancestry output (if there are no results, revision_id was
not present in this weave/graph.

> +        else:
> +            g = self.get_graph()
> +            ancestry = {}
> +            children = {}
> +            ghosts = set()
> +            NULL_REVISION = _mod_revision.NULL_REVISION
> +            for rev_id, parent_ids in g.iter_ancestry([revision_id]):
> +                if len(parent_ids) == 0: # Ghost
> +                    if rev_id not in children:
> +                        continue
> +                    ghosts.add(rev_id)
> +                    for child in children[rev_id]:
> +                        old_anc = ancestry[child]
> +                        ancestry[child] = tuple(p for p in old_anc
> +                                                   if p != rev_id)
> +                    continue
> +                if len(parent_ids) == 1 and parent_ids[0] == NULL_REVISION:
> +                    parent_ids = () # No parents

^^^ Do you need special handling of NULL_REVISION here?  It looks like
the ghost handling would do it.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFH0Pbl0F+nu1YWqI0RAtqZAKCCiZvFUSgQPFi+lWxq/VG2B3qNlgCfXUO/
87uP7WxSmhQetLtcjaFUlgg=
=47l1
-----END PGP SIGNATURE-----