Re: [Monotone-devel] Re: Bug in monotone lca

[Nathaniel Smith]

On Fri, May 20, 2005 at 09:48:06AM +0200, Wim Oudshoorn wrote:
> Nathaniel Smith <address@hidden> writes:
> > It doesn't make much of a difference for anything
> > that monotone uses its LCA algorithm for, though; in fact, "nearest
> > common ancestor" is probably better.  (We just use LCA when we want a
> > nearby common ancestor, that we can use to generate a path from one
> > node to another, for instance.)
> >
> > This is why, though, if someone wanted to make
> > unique-lca-or-else-lca+dom into the merge ancestor selection
> > algorithm as a temporary stopgap measure, they would have to actually
> > do some work, since for merging you really do need to use the "minimal
> > common ancestor" variant.
> 
> Yes indeed.  But a looked at the code a little and although 
> the lca code I more or less undestand, I can't figure
> out what lcad is doing.
> 
> Is there some precise specification of what it is supposed to do?

It is supposed to find the unique node A such that:
  - A is a common ancestor
  - A is comparable to all ancestors of one side
  - no descendents of A have the above two properties
This is always unique, and so long as the graph is single rooted,
always defined.

> P.S.:  As a stopgap measure, I still think my proposal of a week
> ago is better :-)

Indeed, it looked quite interesting and plausible; I've been meaning
to respond, but it takes some effort to wrap my head back around what
sort of properties are needed and figure out whether I really believe
your suggestion handles all the bad cases...

>  However that also requires real implementation
> work :-(.

Perhaps less than you might think; some things are already written.
(For instance, there's already a function that finds the heads of an
arbitrary revision set, which I seem to recall being one of the
primitives you want...)

>   I might want to try to refresh my C++ knowledge,
> however monotone takes over 2hrs to compile on my fast computer :-(.
> I dread how long it will take to compile on my server 
> which is really slow.

'./configure CFLAGS="-O0 -ggdb3" CXXFLAGS="-O0 -ggdb3"' makes a huge
difference :-).  (Actually just the -O0 part, but when you're
developing, it's sorta handy to always have debugging info there
without having to recompile for it.)

(ccache is also very, very helpful.)

-- Nathaniel

-- 
"On arrival in my ward I was immediately served with lunch. `This is
what you ordered yesterday.' I pointed out that I had just arrived,
only to be told: `This is what your bed ordered.'"
  -- Letter to the Editor, The Times, September 2000