[MERGE] LCA Merge resolution for tree-shape

[Martin Pool]

I think we should really get this merged and released, because it
unblocks some difficult merges for mysql.  In fact I'd like to do this
into a 1.7.1rc1.

> It seems to me like a form that iterated LCAs might be ideal.  Then you
> could do:
>
> iterator = graph.search_lcas()
> values = iterator.next()
> if len(values) == 1:
>  criss_cross = False
>  lcas = []
> else:
>  criss_cross = True
>  lcas = values
>  for values in iterator:
>    pass
> (base,) = values
>
>> Re-traversing the graph is unfortunate, but not terrible. And I'd like
>> to postpone rewriting find_unique_lca on top of the rest of this.
>
> You always have the option of rewriting find_unique_lca as a separate
> patch that we merge *first*.

Some kind of stateful object that walks back through them seems to
make sense, but we could also do that in a later patch.

>> I'm attaching a version which responds to most of your requests. The
>> remaining ones are:
>>
>> 1) Modifying Graph.find_unique_lca. I feel like this is outside the
>> scope of this patch. It certainly isn't trivial to fix.
>>
>> 2) Merger.revision_trees(). I *can* implement this, though there is only
>> one caller.
>>
>> 3) Filtering in MultiWalker. We could, but I don't think it would be a
>> net win, and this code is already written. If you feel strongly, I can
>> do so.
>>
>> 4) Changing _entries_lca to return everything where THIS != OTHER. The
>> point of what I wrote is to only return entries where OTHER != "base"
>> (where base is also made up of lcas as appropriate.)
>
> 1, 2, and 4 are the only substantial concerns I had, so not addressing
> them gets you another
>
> bb:resubmit
>
>> I appreciate you reviewing this. I know it gets hairy, there are some
>> outlandish edge-cases that happen to exist in the real world. I don't
>> feel like I've really over engineered it, but I'm willing to discuss it
>> a bit more.
>
> I don't think you've over-engineered it.  I think you've made
> adjustments to the model without adjusting the code to match, making the
> codebase messier.

John said he's going to talk to Aaron about the remaining points and
work out whether to modify them, do them now, or do them after merging
this patch.

-- 
Martin <http://launchpad.net/~mbp/>