Fix interesting git-rev-list corner case

Fix interesting git-rev-list corner case

[Linus Torvalds]

This corner-case was triggered by a kernel commit that was not in date
order, due to a misconfigured time zone that made the commit appear three
hours older than it was.

That caused git-rev-list to traverse the commit tree in a non-obvious
order, and made it parse several of the _parents_ of the misplaced commit
before it actually parsed the commit itself. That's fine, but it meant 
that the grandparents of the commit didn't get marked uninteresting, 
because they had been reached through an "interesting" branch.

The reason was that "mark_parents_uninteresting()" (which is supposed to 
mark all existing parents as being uninteresting - duh) didn't actually 
traverse more than one level down the parent chain.

NORMALLY this is fine, since with the date-based traversal order,
grandparents won't ever even have been looked at before their parents (so
traversing the chain down isn't needed, because the next time around when 
we pick out the parent we'll mark _its_ parents uninteresting), but since 
we'd gotten out of order, we'd already seen the parent and thus never got 
around to mark the grandparents.

Anyway, the fix is simple. Just traverse parent chains recursively.  
Normally the chain won't even exist (since the parent hasn't been parsed
yet), so this is not actually going to trigger except in this strange 
corner-case.

Add a comment to the simple one-liner, since this was a bit subtle, and I 
had to really think things through to understand how it could happen.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -228,6 +228,17 @@ static void mark_parents_uninteresting(s
 		commit->object.flags |= UNINTERESTING;
 
 		/*
+		 * Normally we haven't parsed the parent
+		 * yet, so we won't have a parent of a parent
+		 * here. However, it may turn out that we've
+		 * reached this commit some other way (where it
+		 * wasn't uninteresting), in which case we need
+		 * to mark its parents recursively too..
+		 */
+		if (commit->parents)
+			mark_parents_uninteresting(commit);
+
+		/*
 		 * A missing commit is ok iff its parent is marked 
 		 * uninteresting.
 		 *

Re: Fix interesting git-rev-list corner case

[Ryan Anderson]

On Fri, Jul 29, 2005 at 03:50:30PM -0700, Linus Torvalds wrote:
> 
> This corner-case was triggered by a kernel commit that was not in date
> order, due to a misconfigured time zone that made the commit appear three
> hours older than it was.

Maybe it'd make sense to have the commits refuse to add a commit when it
would be younger than one of it's parents?

I suppose that only really fixes one direction of the other problem,
though.

-- 

Ryan Anderson
  sometimes Pug Majere

Re: Fix interesting git-rev-list corner case

[A Large Angry SCM]

Ryan Anderson wrote:
> Maybe it'd make sense to have the commits refuse to add a commit when it
> would be younger than one of it's parents?

Better not to trust timestamps in distributed federations since you 
can't guarantee any kind of accuracy across administrative boundaries.

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Fri, 29 Jul 2005, Ryan Anderson wrote:
> 
> Maybe it'd make sense to have the commits refuse to add a commit when it
> would be younger than one of it's parents?

No, the git-rev-list thing really was a bug, it was just that I hadn't 
thought things through when I wrote it, and the "normal" case (ie the ones 
I had tested) just happened to work because it's a common one.

In other words - I had taken a shortcut without thinking it through.

The date really isn't important - the algorithm I had works fine even if 
dates are totally screwed up, it just had a stupid bug.

And trying to make the date more important than it is will just inevitably 
lead to _worse_ problems down the road. 

So the date is a good heuristic (we have to traverse the commits in _some_
order, and the date order just happens to be one that ends up giving the
minimum number of commits "usually"), but any time we _depend_ on dates
one way or the other that would be a good.

		Linus

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Fri, 29 Jul 2005, Linus Torvalds wrote:
> 
>		, but any time we _depend_ on dates
> one way or the other that would be a good.

"_not_ be a good _thing_". I don't know what strange brain-glitch I had
there.

I had kind of hoped my kids would be all grown up before their dad started 
losing his marbles. Oh, well..

			Linus

Re: Fix interesting git-rev-list corner case

[Peter Osterlund]

Linus Torvalds <torvalds@osdl.org> writes:

> This corner-case was triggered by a kernel commit that was not in date
> order, due to a misconfigured time zone that made the commit appear three
> hours older than it was.

I have problems pulling linux kernel changes from
33ac02aa4cef417871e128ab4a6565e751e5f3b2 to
b0825488a642cadcf39709961dde61440cb0731c into my local tree. At first
I thought your patch would fix it, but it doesn't:

r3000:~/git$ cat linux/.git/HEAD
b0825488a642cadcf39709961dde61440cb0731c
r3000:~/git$ git-clone-script -l linux linux.test
defaulting to local storage area
0 blocks
r3000:~/git$ cd linux.test/
r3000:~/git/linux.test$ echo 33ac02aa4cef417871e128ab4a6565e751e5f3b2 >.git/HEAD
r3000:~/git/linux.test$ git-pull-script ../linux
Packing 291 objects
Unpacking 291 objects
 100% (291/291) done
Trying to merge b0825488a642cadcf39709961dde61440cb0731c into 33ac02aa4cef417871e128ab4a6565e751e5f3b2
Simple merge failed, trying Automatic merge
Removing arch/mips/vr41xx/common/giu.c
Auto-merging arch/s390/kernel/head.S.
Auto-merging arch/s390/kernel/head64.S.
Auto-merging arch/um/os-Linux/elf_aux.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/um/os-Linux/elf_aux.c.
Auto-merging arch/x86_64/kernel/smp.c.
Auto-merging arch/x86_64/kernel/smpboot.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/x86_64/kernel/smpboot.c.
Auto-merging drivers/i2c/busses/i2c-mpc.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/i2c/busses/i2c-mpc.c.
Removing drivers/ide/cris/ide-v10.c
Removing drivers/media/dvb/frontends/lgdt3302.c
Removing drivers/media/dvb/frontends/lgdt3302.h
Removing drivers/media/dvb/frontends/lgdt3302_priv.h
Removing drivers/serial/bast_sio.c
Auto-merging drivers/usb/input/hid-input.c.
Auto-merging drivers/video/fbmem.c.
Auto-merging include/asm-i386/bitops.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/asm-i386/bitops.h.
Auto-merging include/asm-x86_64/smp.h.
Auto-merging kernel/sys.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in kernel/sys.c.
Removing net/ipv4/utils.c
Removing sound/pcmcia/vx/vx_entry.c
Removing sound/pcmcia/vx/vxp440.c
fatal: merge program failed
Automatic merge failed, fix up by hand

-- 
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Sat, 30 Jul 2005, Peter Osterlund wrote:
> 
> I have problems pulling linux kernel changes from
> 33ac02aa4cef417871e128ab4a6565e751e5f3b2 to
> b0825488a642cadcf39709961dde61440cb0731c into my local tree. At first
> I thought your patch would fix it, but it doesn't:

No, this is a merge conflict failure, and you simply have conflicts in the
tree. git did everything right, it just couldn't do an automatic merge.

> ERROR: Merge conflict in arch/um/os-Linux/elf_aux.c.
> ERROR: Merge conflict in arch/x86_64/kernel/smpboot.c.
> ERROR: Merge conflict in drivers/i2c/busses/i2c-mpc.c.
> ERROR: Merge conflict in include/asm-i386/bitops.h.
> ERROR: Merge conflict in kernel/sys.c.

We don't have any nice graphical tools to show these to you like BitKeeper 
had, although it shouldn't be fundamentally hard.

What you need to do is basically edit all those five files, and look for 
the conflicts (they are just like normal CVS conflicts:

	<<<<<<<
		orig-branch
		conflict-contents
	=======
		pulled-branch
		conflict-contents
	>>>>>>>>

and then you edit them to your liking until you have no more conflicts, 
and then you have to commit your manual resolve with

	git commit --all

which will commit the merge _and_ your manual conflict resolution.

This is something where a nice wrapper layer could do a lot better. I know 
there are graphical three-way merge programs available.

But core git is no worse (and in fact a _lot_ better) than CVS in this 
regard, so I feel that the git merge, while obviously not perfect or even 
very smart, is "sufficient" for what git is (ie it's up to porcelain to do 
anything better).

			Linus

Re: Fix interesting git-rev-list corner case

[Peter Osterlund]

Linus Torvalds <torvalds@osdl.org> writes:

> On Sat, 30 Jul 2005, Peter Osterlund wrote:
> > 
> > I have problems pulling linux kernel changes from
> > 33ac02aa4cef417871e128ab4a6565e751e5f3b2 to
> > b0825488a642cadcf39709961dde61440cb0731c into my local tree. At first
> > I thought your patch would fix it, but it doesn't:
> 
> No, this is a merge conflict failure, and you simply have conflicts in the
> tree. git did everything right, it just couldn't do an automatic merge.

OK, but note that I didn't do any editing of any local files myself.
Both commit ids are from your public linux kernel git tree. What I did
was equivalent to:

1. rsync from rsync.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/
2. waited a day or so.
3. git-pull-script from the same kernel.org repository.

Is it expected that you end up with merge conflicts in this case? If
that's the case, is there a better way to pull changes that doesn't
involve having to resolve conflicts in files you didn't even know
existed?

I think it should be possible to just fast forward to the new HEAD in
this situation.

-- 
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Sat, 30 Jul 2005, Peter Osterlund wrote:
> 
> OK, but note that I didn't do any editing of any local files myself.
> Both commit ids are from your public linux kernel git tree. What I did
> was equivalent to:
> 
> 1. rsync from rsync.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/
> 2. waited a day or so.
> 3. git-pull-script from the same kernel.org repository.
> 
> Is it expected that you end up with merge conflicts in this case?

Nope. Something went wrong.

> I think it should be possible to just fast forward to the new HEAD in
> this situation.

Indeed.

Can you send me your HEAD and MERGE_HEAD (don't do the merge).

Sounds like maybe "git-merge-base" is confused, and thinks HEAD is not
reachable from FETCH_HEAD. It could have a similar bug git-rev-list had.

			Linus

Re: Fix interesting git-rev-list corner case

[Peter Osterlund]

On Sat, 30 Jul 2005, Linus Torvalds wrote:

> On Sat, 30 Jul 2005, Peter Osterlund wrote:
> >
> > OK, but note that I didn't do any editing of any local files myself.
> > Both commit ids are from your public linux kernel git tree. What I did
> > was equivalent to:
> >
> > 1. rsync from rsync.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/
> > 2. waited a day or so.
> > 3. git-pull-script from the same kernel.org repository.
> >
> > Is it expected that you end up with merge conflicts in this case?
>
> Nope. Something went wrong.
>
> > I think it should be possible to just fast forward to the new HEAD in
> > this situation.
>
> Indeed.
>
> Can you send me your HEAD and MERGE_HEAD (don't do the merge).

HEAD      : 33ac02aa4cef417871e128ab4a6565e751e5f3b2
MERGE_HEAD: b0825488a642cadcf39709961dde61440cb0731c

-- 
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Sat, 30 Jul 2005, Peter Osterlund wrote:
> >
> > Can you send me your HEAD and MERGE_HEAD (don't do the merge).
> 
> HEAD      : 33ac02aa4cef417871e128ab4a6565e751e5f3b2
> MERGE_HEAD: b0825488a642cadcf39709961dde61440cb0731c

Bingo.

Yup, it's git-merge-base, and it is confused by the same thing that 
confused git-rev-list.

Thanks, I'll fix it.

		Linus

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Sat, 30 Jul 2005, Linus Torvalds wrote:
> 
> Yup, it's git-merge-base, and it is confused by the same thing that 
> confused git-rev-list.
> 
> Thanks, I'll fix it.

Hmm.. Here's a tentative fix. I'm not really happy with it, and maybe
somebody else can come up with a better one. I think this one ends up
being quite a bit more expensive than the old one (it will look up _all_
common parents that have a child that isn't common, and then select the
newest one of the bunch), but I haven't really thought it through very
much.

I bet there is a smarter way to do this, but this _should_ fix the problem
Peter sees. Peter?

		Linus
---
diff --git a/merge-base.c b/merge-base.c
--- a/merge-base.c
+++ b/merge-base.c
@@ -2,54 +2,50 @@
 #include "cache.h"
 #include "commit.h"
 
-static struct commit *process_list(struct commit_list **list_p, int this_mark,
-				   int other_mark)
-{
-	struct commit *item = (*list_p)->item;
-
-	if (item->object.flags & other_mark) {
-		return item;
-	} else {
-		pop_most_recent_commit(list_p, this_mark);
-	}
-	return NULL;
-}
-
 static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
 {
-	struct commit_list *rev1list = NULL;
-	struct commit_list *rev2list = NULL;
+	struct commit_list *list = NULL;
+	struct commit_list *result = NULL;
 
-	commit_list_insert(rev1, &rev1list);
-	rev1->object.flags |= 0x1;
-	commit_list_insert(rev2, &rev2list);
-	rev2->object.flags |= 0x2;
+	if (rev1 == rev2)
+		return rev1;
 
 	parse_commit(rev1);
 	parse_commit(rev2);
 
-	while (rev1list || rev2list) {
-		struct commit *ret;
-		if (!rev1list) {
-			// process 2
-			ret = process_list(&rev2list, 0x2, 0x1);
-		} else if (!rev2list) {
-			// process 1
-			ret = process_list(&rev1list, 0x1, 0x2);
-		} else if (rev1list->item->date < rev2list->item->date) {
-			// process 2
-			ret = process_list(&rev2list, 0x2, 0x1);
-		} else {
-			// process 1
-			ret = process_list(&rev1list, 0x1, 0x2);
+	rev1->object.flags |= 1;
+	rev2->object.flags |= 2;
+	insert_by_date(rev1, &list);
+	insert_by_date(rev2, &list);
+
+	while (list) {
+		struct commit *commit = list->item;
+		struct commit_list *tmp = list, *parents;
+		int flags = commit->object.flags & 3;
+
+		list = list->next;
+		free(tmp);
+		switch (flags) {
+		case 3:
+			insert_by_date(commit, &result);
+			continue;
+		case 0:
+			die("git-merge-base: commit without either parent?");
 		}
-		if (ret) {
-			free_commit_list(rev1list);
-			free_commit_list(rev2list);
-			return ret;
+		parents = commit->parents;
+		while (parents) {
+			struct commit *p = parents->item;
+			parents = parents->next;
+			if ((p->object.flags & flags) == flags)
+				continue;
+			parse_commit(p);
+			p->object.flags |= flags;
+			insert_by_date(p, &list);
 		}
 	}
-	return NULL;
+	if (!result)
+		return NULL;
+	return result->item;
 }
 
 int main(int argc, char **argv)
@@ -64,6 +60,8 @@ int main(int argc, char **argv)
 	}
 	rev1 = lookup_commit_reference(rev1key);
 	rev2 = lookup_commit_reference(rev2key);
+	if (!rev1 || !rev2)
+		return 1;
 	ret = common_ancestor(rev1, rev2);
 	if (!ret)
 		return 1;

Re: Fix interesting git-rev-list corner case

[Peter Osterlund]

Linus Torvalds <torvalds@osdl.org> writes:

> On Sat, 30 Jul 2005, Linus Torvalds wrote:
> > 
> > Yup, it's git-merge-base, and it is confused by the same thing that 
> > confused git-rev-list.
> > 
> > Thanks, I'll fix it.
> 
> Hmm.. Here's a tentative fix. I'm not really happy with it, and maybe
> somebody else can come up with a better one. I think this one ends up
> being quite a bit more expensive than the old one (it will look up _all_
> common parents that have a child that isn't common, and then select the
> newest one of the bunch), but I haven't really thought it through very
> much.
> 
> I bet there is a smarter way to do this, but this _should_ fix the problem
> Peter sees. Peter?

Yes, it does fix the problem. Thanks.

-- 
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340

Re: Fix interesting git-rev-list corner case

[Linus Torvalds]

On Sat, 31 Jul 2005, Peter Osterlund wrote:
>
> > I bet there is a smarter way to do this, but this _should_ fix the problem
> > Peter sees. Peter?
> 
> Yes, it does fix the problem. Thanks.

Ok, Junio, can you apply the git-merge-base patch? It's not perfect, but
it's clearly better than what's there right now.

Add a "Signed-off-by: Linus Torvalds <torvalds@osdl.org>" and edit the 
description a bit, perhaps.

		Linus

Re: Fix interesting git-rev-list corner case

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Sat, 31 Jul 2005, Peter Osterlund wrote:
>>
>> > I bet there is a smarter way to do this, but this _should_ fix the problem
>> > Peter sees. Peter?
>> 
>> Yes, it does fix the problem. Thanks.
>
> Ok, Junio, can you apply the git-merge-base patch? It's not perfect, but
> it's clearly better than what's there right now.
>
> Add a "Signed-off-by: Linus Torvalds <torvalds@osdl.org>" and edit the 
> description a bit, perhaps.

OK.  It's already sitting at the top of the "pu" branch, so I'll
just advance "master" with your sign off added.