[MERGE] faster common ancestor

[Robert Collins]

On Mon, 2006-03-06 at 14:37 -0500, Aaron Bentley wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Ah, here we are.
...
> Complaint already voiced; you've changed what revision_graph produces,
> and this will break bzrtools, at least.

I will reinstate revision_graph having ghosts asap when our other thread
completes.

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

So if we have explicit knowledge about other unavailable revisions, and
no revisions have no parents, where should we put 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.

I touched the code several times while fiddling with different
approaches.

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

Same reason.

> > +    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.

I think you are saying that 'if one repository has a ghost in the other,
and the other is missing the which which references it, the
multiplerevisionsources adapter should ensure that the returned graph
contains both revisions' ?

> > +        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.

Doh!. Nice catch. I'll fix that up with the ghost aware api I'm doing.

Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060307/5cd7aec4/attachment.pgp