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

[Aaron Bentley]

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

John A Meinel wrote:
> Isn't it true that, any time you get this pattern:
> http://aaronbentley.com/pastegraph.cgi?n=140
> 
> Where we both merge a common revision, then LCA+DOM will pick the
> ultimate parent (A).
> When you probably want it to pick (J).

Yes.  And worse, a la http://aaronbentley.com/pastegraph.cgi?n=136

> I don't know if it is quite as obvious what to do when the ancestries
> are longer. But what if we had a shortcut for *immediate* ancestors.

Could you expand on this?

> Or maybe we introduce the concept of 'last merged' revisions. So even if
> you have this:
> 
> http://aaronbentley.com/pastegraph.cgi?n=141
> 
> You still have a 'last merged' revisions of B+J for the left side, and
> J+D for the right side.

> So it wouldn't have to be a dominator if it is present in the
> 'last-merged' revisions of both sides.

Hmm.  Interesting.

> Now, doing this:
> http://aaronbentley.com/pastegraph.cgi?n=143
> 
> Would mean that we stop picking 'J' and revert back to the only
> dominator "A".
> But that seems reasonable considering the topology.

I don't understand why that would be reasonable.

Where I'm getting to is thinking that our current algorithm is better
than LCA+DOM, except in its handling of criss-cross.  So maybe the best
course is to:

1. update it to skip criss-cross merge bases
2. work on caching strategies so that it doesn't take so long.  With
proper caching, it should be a very cheap operation.

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

iD8DBQFD+fZZ0F+nu1YWqI0RAnC6AJ4mlbd/EzUVrjWOTlaTKTkrdtKKiACdFQGd
NZzreGlk779PQA8VfaxHVjk=
=6xXm
-----END PGP SIGNATURE-----