[MERGE] more common-ancestor performance improvements.

[Aaron Bentley]

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

Robert Collins wrote:
> This sounds great. I think we should start a index mapping terms we use
> - e.g. border common ancestor - to their definition (which might be on
> wikipedia, or inside the code base). We don't always use the formal
> definition of a term, or there can be multiple definitions and we should
> make it clear which one we have chosen.

To avoid misusing existing terminology, I have googled "border common
ancestor".  It doesn't appear to be a known graph theory term.  I have
also chosen "distinct common ancestor" as a replacement for "minimal
common ancestor".  Again, it is not a known graph theory term.

Anyone who knows the actual terms for these things, please let me know.
The information I've found on graph theory tends to be either way below
my level, or way above it.

> In the patch itself..
> 
> +    def _find_candidate_mca(self, revisions):
> +        walkers = [_AncestryWalker(r, self) for r in revisions]
> 
> I think that functions like this really benefit from a docstring which
> provides a simple overview of the function.

I've renamed this to find_border_ancestors, and given it a docstring.

> Something like that would make it a lot easier for folk looking at the
> code - both for review and for eventual usage.
> 
> 
> +        self._lines = None
> 
> I'm guessing this variable name is cribbed from somewhere else

Yes, it's used by several functions in bzrlib.graph.

> - its
> very opaque. What is a line in this context? Perhaps '_revisions' ?

It meant "line of ancestry/descent".  I've changed it to
_search_revisions, as we discussed.

Here is an updated merge directive and patch, to clarify the behavior.
I've also removed GraphWalker._get_ancestry, which was unused.

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

iD8DBQFGXZem0F+nu1YWqI0RAvqGAJ43vu2eXnlBIqaaFYRUnpuGBp428wCfVbJE
QxDd+RGvLF9Xd2oXjdS+t3M=
=H+mW
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-walker4.patch
Type: text/x-patch
Size: 121079 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070530/c2e0dae1/attachment-0002.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-walker4b.patch
Type: text/x-patch
Size: 15734 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070530/c2e0dae1/attachment-0003.bin