Re: Add merge-base
- From
Daniel Barkalow <barkalow@iabervon.org>
- Date
- Apr 17, 2005, 16:36 UTC
- Message-ID
- <Pine.LNX.4.21.0504171205190.30848-100000@iabervon.org>
- In-Reply-To
- <20050417160106.GI1487@pasky.ji.cz>
On Sun, 17 Apr 2005, Petr Baudis wrote:
Show 16 quoted lines
> Dear diary, on Sun, Apr 17, 2005 at 05:27:13PM CEST, I got a letter > where Daniel Barkalow <barkalow@iabervon.org> told me that... > > merge-base finds one of the best common ancestors of a pair of commits. In > > particular, it finds one of the ones which is fewest commits away from the > > further of the heads. > > What does it return when I have > > A -- C > \/ \ > /\ / > B -- D > > ? >:) > > I assume just either A or B, randomly?
Essentially, yes.
Show 6 quoted lines
> I think it would be best if it could list all the "first-class" matches > (both A and B in this case), each on a separate line; this way the > overlay tools could choose an algorithm to evaluate those further as > they see fit - e.g. sort them by time (you might aid that by listing the > commit time in front of them), then take the first n and try to diff > them all and take the one with least changes (as suggested by Linus).
It's actually kind of tricky to get all of the "best" ancestors without getting any useless ancestors; the "best" criterion is maintained in the current version by stopping as soon as possible.
I think that the real solution would be to have a merge program that interacts back and forth with the revision history processor, since I think that merges for which the choice of ancestor matters (for whether it gives a conflict) would benefit most directly and clearly from figuring out the histories of the conflicting changes, not choosing different ancestors.
If someone comes up with an algorithm that wants an alternative ancestor rather than more interactive stuff, I can work on getting a complete list.
Show 17 quoted lines
> > Index: merge-base.c
> > ===================================================================
> > --- /dev/null (tree:37a0b01b85c2999243674d48bfc71cdba0e5518e)
> > +++ d662b707e11391f6cfe597fd4d0bf9c41d34d01a/merge-base.c (mode:100644 sha1:0f85e7d9e9a896d1142a54170ddf1159f11f9cdd)
> > @@ -0,0 +1,108 @@
> > +#include <stdlib.h>
> > +#include "cache.h"
> > +#include "revision.h"
> > +
> > +struct revision *common_ancestor(struct revision *rev1, struct revision *rev2)
> > +{
> > + struct parent *parent;
> > +
> > + struct parent *rev1list = malloc(sizeof(struct parent));
> > + struct parent *rev2list = malloc(sizeof(struct parent));
>
> Did I overlook anything or you could have just a single revlist?I tried with just one, but I couldn't keep it straight in my head. rev1list holds the unmarked ancestors of rev1; rev2list holds the unmarked ancestors of rev2.
Show 22 quoted lines
> > + struct parent *posn, *temp;
> > +
> > + rev1list->parent = rev1;
> > + rev1list->next = NULL;
> > +
> > + rev2list->parent = rev2;
> > + rev2list->next = NULL;
> > +
> > + while (rev1list || rev2list) {
> > + posn = rev1list;
> > + rev1list = NULL;
> > + while (posn) {
> > + parse_commit_object(posn->parent);
> > + if (posn->parent->flags & 0x0001) {
> > + /*
> > + printf("1 already seen %s %x\n",
> > + sha1_to_hex(posn->parent->sha1),
> > + posn->parent->flags);
> > + */
> > + // do nothing
>
> Mostly for consistency, I'd prefer you to use /* */ comments in general.Sure.
> I think a terrified squeak at stderr in this situation (possibly > suggesting fsck-cache) might be appropriate.
No, this is normal; it indicates that tree 1 has a recent little merge:
orig --------------- tree 2
\
--- X -- Y -- Z -- tree 1
\ /
-- A --When we see X for A, we've already seen it for Y, but that's fine. I get this case when I merge with you after you merge twice with Linus since I last merged.
> > + } else if (posn->parent->flags & 0x0002) {
> > + // XXXX free lists
>
> Hmm, so, why not free the lists?Ah, details; mainly, I want to wait until revision.h is cleaner before fixing this sort of thing.
> Symmetrical notes apply to this half. Actually, they are too similar. > What about factoring them to a common function?
Sure.
Fixed version to follow.
-Daniel *This .sig left intentionally blank*