[MERGE] faster common ancestor

[Aaron Bentley]

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

Ah, here we are.

Robert Collins wrote:
> this common ancestor implementation is ~ the same as the 0.7 one, but it
> does not need to read each revision. for knits it will be faster as
> we'll only hit the index.
>  def revision_graph(revision, revision_source):
>      """Produce a graph of the ancestry of the specified revision.

Complaint already voiced; you've changed what revision_graph produces,
and this will break bzrtools, at least.

> +    # pick a root. If there are multiple roots
> +    # this could pick a random one.

We should always pick NULL_REVISION

> @@ -238,9 +208,10 @@
>  def combined_graph(revision_a, revision_b, revision_source):
>      """Produce a combined ancestry graph.
>      Return graph root, ancestors map, descendants map, set of common nodes"""
> -    root, ancestors, descendants = revision_graph(revision_a, revision_source)
> -    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
> -                                                        revision_source)
> +    root, ancestors, descendants = revision_graph(
> +        revision_a, revision_source)

This looks like unnecessary reformatting.

>              root, ancestors, descendants, common = \
> -                combined_graph(revision_a, revision_b, revision_source)
> +                combined_graph(revision_a,
> +                               revision_b,
> +                               revision_source)

Again, looks unnecessary.

> +    def get_revision_graph(self, revision_id):
> +        result = {}
> +        for source in self._revision_sources:
> +            try:
> +                result.update(source.get_revision_graph(revision_id))
> +            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
> +                pass
> +        if result:
> +            return result
> +        raise e

So here's another behavioural change, because the old revision_graph
would return a combination of the two; if revision_a had a ghost, it
would hit revision_b.  Here, if either repository is missing the tip
revision, all its data is ignored.  I am not certain whether this can
cause consistency problems, but it seems like it could.

> +        self.assertTrue(common_ancestor(revisions_2[6], revisions[5], sources),
> +                        (revisions[4], revisions_2[5]))

This test looks bogus, because it doesn't have a conditional in it.  You
could also use assertSubset.

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

iD8DBQFEDI9o0F+nu1YWqI0RApx6AJ9vTXTOKISYw+hlr3XRdf0zd9SVwgCdGUDK
w2zM+tZ6nbYsmCKYCFtpsmU=
=fwxB
-----END PGP SIGNATURE-----