More merge base discussion [was: monotone's LCA+DOM algo for selecting a merge base]

[John A Meinel]

Aaron Bentley wrote:
> John A Meinel wrote:
>>> Aaron Bentley wrote:
>>> As I understand it, the current algorithm uses the revision which is
>>> farthest from 'null:' which is inside the ancestry of both sides. Is
>>> that correct?
> 
> Correct.
>>> If it is, then a reasonable cache would be to just annotate each
>>> revision with its maximum distance from 'null:'. This is fixed property
>>> that only changes if ghosts are fleshed out. Which means that a cache is
>>> perfect for it.
> 
> Exactly.
> 

Sounds reasonable to me. It seems perfectly suited for something like
the 'stat-cache'. Which would just have "revision-id\0distance" one per
line.

I don't know what the delimiter should be, especially since I don't know
what our future revision-id spec is going to be. '\0' is a safe bet that
we won't ever allow it, but I don't know about any other character.

> 
>>> What we haven't fully investigated, is that it preferentially picks
>>> long-cuts.
> ...
>>> We avoided LCA, because A->C->J cause A to look much closer than it
>>> really should be. (A shortcut). The problem I was running into was that
>>> it was picking A because the "C" path went through Robert's integration
>>> branch, whereas I had just merged the other branch.
> 
> As soon as someone merges Robert, they get his distance-from-null: +1,
> unless they're already farther than him.  I think I have noticed one
> case where it chose Robert due to this long-cut behaviour.
> 
> I guess one option would be to give up on using mutually-merged bases,
> and require that the base be on the revision-history of one of the
> branches.  Most of the time, that won't be too bad.
> 
> But yes, I've seen this happen too.
> 
> Aaron

I think what actually happened is that I merged you, and resolved all
the conflicts. And then when I merged you again, it picked Robert as a
base, and I had to resolve *your* conflicts again, not integration
conflicts.
That actually makes the most sense, because if it picks Robert as a
base, it basically rolls up all of your changes, and applies them to my
tree. While if it picks you as a base, it would roll up all of Robert's
changes. But I probably didn't have to resolve conflicts between Robert
and myself, I had to resolve changes between you and myself. And then I
had to resolve them again. I'm 90% sure that is what happened.

John
=:->

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060220/16d700e7/attachment.pgp