gitk problems: can't unset "idinlist(...)"

gitk problems: can't unset "idinlist(...)"

[Linus Torvalds]

Ok, color me stumped, but gitk is unhappy.

Ingo and Thomas have just announced that they  have a unified x86 tree for 
both i386/x86-64, so I did

	gitk arch/i386 arch/x86_64

to look at what has happened recently in the kernel in that area.

I get the gitk history view, but no actual diffs, and I get an application 
error window saying

	can't unset "idinlist(57d1c91fa6d9146b309b7511f6432dea2a24858b)": no such element in array
	can't unset "idinlist(57d1c91fa6d9146b309b7511f6432dea2a24858b)": no such element in array
	    while executing
	"unset idinlist($id)"
	    (procedure "layouttail" line 11)
	    invoked from within
	"layouttail"
	    (procedure "layoutmore" line 35)
	    invoked from within
	"layoutmore $tlimit $allread"
	    (procedure "chewcommits" line 9)
	    invoked from within
	"chewcommits 1"
	    ("eval" body line 1)
	    invoked from within
	"eval $script"
	    (procedure "dorunq" line 9)
	    invoked from within
	"dorunq"
	    ("after" script)

which really doesn't tell me much.

It doesn't seem to happen without path limiting, and it also doesn't seem 
to happen for all paths (doing "gitk drivers/scsi" doesn't show it), but 
somehow that "arch/i386" part seems to bring it out.

I'm not seeing anything interesting or special about that named commit, or 
anything else that would make gitk unhappy. But it is.

Current kernel tree. Anybody else has any ideas? Somebody who knows 
tcl/tk, and gitk?

			Linus

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Fri, Jul 20, 2007 at 04:05:54PM -0700, Linus Torvalds wrote:

> 	can't unset "idinlist(57d1c91fa6d9146b309b7511f6432dea2a24858b)": no such element in array
> [...]
> I'm not seeing anything interesting or special about that named commit, or 
> anything else that would make gitk unhappy. But it is.

Interestingly, I repeatably get the exact same error but with a
different commit:

  7ed40918a386afc2e14a6d3da563ea6d13686c25

which looks like a totally uninteresting commit.

I would expect, given that our repositories are at presumably the same
state, that we would get the same error at the same spot, but we don't.
Which implies to me there is some randomness, except that I get the
_same_ commit every time (and presumably so do you).

My master (and all other branches) are at c2e6805.

-Peff

Re: gitk problems: can't unset "idinlist(...)"

[Linus Torvalds]

On Sat, 21 Jul 2007, Jeff King wrote:
> 
> Interestingly, I repeatably get the exact same error but with a
> different commit:
> 
>   7ed40918a386afc2e14a6d3da563ea6d13686c25
> 
> which looks like a totally uninteresting commit.

It seems to depend on the path limiter.

With "arch/i386", I get the 7ed409 one, with "arch/i386 arch/x86_64" I get 
a complaint about 57d1c91fa. In neither case do I see the reason.

But I think I found a clue. One thing special about that 57d1c91fa is that 
when you do

	git log --topo-order --parents --pretty=one arch/i386/ arch/x86_64/

and search for it, it first shows up as a parent for commit 9fdb62af92: 
and not just _one_ parent, but three! So it looks like the parent 
simplification is broken, and maybe gitk is unhappy for that reason.

The same is true of 7ed40918a38, btw, so yeah, I think that's it.

Junio, didn't we have some parent simplification patches recently?

			Linus

Re: gitk problems: can't unset "idinlist(...)"

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> It seems to depend on the path limiter.
>
> With "arch/i386", I get the 7ed409 one, with "arch/i386 arch/x86_64" I get 
> a complaint about 57d1c91fa. In neither case do I see the reason.
>
> But I think I found a clue. One thing special about that 57d1c91fa is that 
> when you do
>
> 	git log --topo-order --parents --pretty=one arch/i386/ arch/x86_64/
>
> and search for it, it first shows up as a parent for commit 9fdb62af92: 
> and not just _one_ parent, but three! So it looks like the parent 
> simplification is broken, and maybe gitk is unhappy for that reason.

Yeah, I think if you limit the range at the bottom
(e.g. v2.6.21..)  the problem disappears.

> The same is true of 7ed40918a38, btw, so yeah, I think that's it.
>
> Junio, didn't we have some parent simplification patches recently?

We had a patch to remove duplicated parent or something, I
think.

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Fri, Jul 20, 2007 at 10:53:10PM -0700, Linus Torvalds wrote:

> With "arch/i386", I get the 7ed409 one, with "arch/i386 arch/x86_64" I get 
> a complaint about 57d1c91fa. In neither case do I see the reason.

Oops, I thought you were using a different command line.

> 	git log --topo-order --parents --pretty=one arch/i386/ arch/x86_64/
> 
> and search for it, it first shows up as a parent for commit 9fdb62af92: 
> and not just _one_ parent, but three! So it looks like the parent 
> simplification is broken, and maybe gitk is unhappy for that reason.

OK, that should make it easier to find (note also that 9fdb62af92 is an
octopus, which might be related).

> Junio, didn't we have some parent simplification patches recently?

v1.5.2 works, so I am bisecting.

-Peff

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Sat, Jul 21, 2007 at 01:59:18AM -0400, Jeff King wrote:

> v1.5.2 works, so I am bisecting.

Hmm. The bad commit is 1ed84157. The commit message is a very suspicious
"Revert 88494423 (removal of duplicate parents in the output codepath)."

-Peff

Re: gitk problems: can't unset "idinlist(...)"

[Linus Torvalds]

On Fri, 20 Jul 2007, Linus Torvalds wrote:
> 
> Junio, didn't we have some parent simplification patches recently?

Yeah. Junio, I think your 11d6596709e04b8d2b429f230b2ed570d013f812 is 
buggy.

Here's a patch. Not very well tested, but it makes gitk happy and passes 
all the tests. And I really think Junio's code was very dubious (it did 
that "p = p->next" *every* time, and then did "pp = &p->next", so "pp" 
would end up jumping by multiple entries.

The new code only ever changes "pp" - either by moving p->next into it 
(delete the current entry) or by moving pp forward by one (keep the 
current entry).

That's much more logical, but somebody should double-check me anyway.

		Linus

---
Subject: Fix up duplicate parents removal

This removes duplicate parents properly, making gitk happy again.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 revision.c |   11 ++++++-----
 1 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/revision.c b/revision.c
index 28b5f2e..7036cf2 100644
--- a/revision.c
+++ b/revision.c
@@ -1323,16 +1323,17 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp
 
 static void remove_duplicate_parents(struct commit *commit)
 {
-	struct commit_list *p;
-	struct commit_list **pp = &commit->parents;
+	struct commit_list **pp, *p;
 
 	/* Examine existing parents while marking ones we have seen... */
-	for (p = commit->parents; p; p = p->next) {
+	pp = &commit->parents;
+	while ((p = *pp) != NULL) {
 		struct commit *parent = p->item;
-		if (parent->object.flags & TMP_MARK)
+		if (parent->object.flags & TMP_MARK) {
+			*pp = p->next;
 			continue;
+		}
 		parent->object.flags |= TMP_MARK;
-		*pp = p;
 		pp = &p->next;
 	}
 	/* ... and clear the temporary mark */

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Fri, Jul 20, 2007 at 11:11:19PM -0700, Linus Torvalds wrote:

> Here's a patch. Not very well tested, but it makes gitk happy and passes 
> all the tests. And I really think Junio's code was very dubious (it did 
> that "p = p->next" *every* time, and then did "pp = &p->next", so "pp" 
> would end up jumping by multiple entries.

I just independently came to the same conclusion. Your patch looks
correct to me (though there are some unrelated formatting changes which
made it a little harder to read).

Acked-by: Jeff King <peff@peff.net>

-Peff

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Sat, Jul 21, 2007 at 02:18:57AM -0400, Jeff King wrote:

> correct to me (though there are some unrelated formatting changes which
> made it a little harder to read).

By which I mean you can keep the 'for' loop, since in either case we are
always reading p->next (if we skip, then we set *pp to p->next anyway,
and if we don't, then pp becomes a pointer to p->next).

So this is a more readable patch which I believe is equivalent.

---
diff --git a/revision.c b/revision.c
index 28b5f2e..7def867 100644
--- a/revision.c
+++ b/revision.c
@@ -1329,10 +1329,11 @@ static void remove_duplicate_parents(struct commit *commit)
 	/* Examine existing parents while marking ones we have seen... */
 	for (p = commit->parents; p; p = p->next) {
 		struct commit *parent = p->item;
-		if (parent->object.flags & TMP_MARK)
+		if (parent->object.flags & TMP_MARK) {
+			*pp = p->next;
 			continue;
+		}
 		parent->object.flags |= TMP_MARK;
-		*pp = p;
 		pp = &p->next;
 	}
 	/* ... and clear the temporary mark */

Re: gitk problems: can't unset "idinlist(...)"

[Linus Torvalds]

On Sat, 21 Jul 2007, Jeff King wrote:
> 
> I just independently came to the same conclusion. Your patch looks
> correct to me (though there are some unrelated formatting changes which
> made it a little harder to read).

Yeah, I shouldn't have done that - I just ended up changing the "for()" to 
a "while()" (because we should *not* do the same thing at the end of the 
loop each time).  And as a part of that I changed the initialization to be 
at the head of the while-loop rather than in the variable declaration, 
because that's how I tend to mostly write while-loops.

But I probably should have tried to keep the patch minimal instead, so 
that it would show the changes better. Probably not a big deal.

		Linus

Re: gitk problems: can't unset "idinlist(...)"

[Linus Torvalds]

On Sat, 21 Jul 2007, Jeff King wrote:
> 
> By which I mean you can keep the 'for' loop, since in either case we are
> always reading p->next (if we skip, then we set *pp to p->next anyway,
> and if we don't, then pp becomes a pointer to p->next).
> 
> So this is a more readable patch which I believe is equivalent.

Fair enough, that also works.

Anyway, just because this is actually something I've noticed a lot of 
people do wrong, I actually do tend to think that when you traverse a 
singly-linked list and remove entries, you should *never* traverse the 
list itself, you should only ever traverse the "pointer to the pointer".

So the difference between your version and mine is that the

	while ((p = *pp) != NULL)

model really only has one single "iterator variable": "pp". Which makes it 
a lot easier to think about and avoid problems.

In contrast, your for-loop actually keeps track of *two* independent 
variables, the "tail pointer of the list we're building up" (pp) and the 
"head pointer of the old list we're traversing" (p).

Does it work? Yes. But I tend to prefer the "there's a single list" model, 
where you just remove entries as you traverse it through a single indirect 
pointer.

They're certainly equivalent, but slightly different mindsets. I at least 
personally find the "single pointer" less likely to have problems, because 
you can never get out of sync (which was basically exactly the problem 
that Junio's code had), because there is nothing to get out of sync _with_ 
when you just have a single main iterator variable.

			Linus

Re: gitk problems: can't unset "idinlist(...)"

[Jeff King]

On Fri, Jul 20, 2007 at 11:47:24PM -0700, Linus Torvalds wrote:

> So the difference between your version and mine is that the
> 
> 	while ((p = *pp) != NULL)

I actually like your version better (I like saving for loops for
honest-to-god, for-each-element-in-this-list iteration; munging the list
in the middle is something that you _should_ call attention to). I just
found your patch much harder to verify, because I had to make sure the
for/while change was equivalent. So you can blame Junio for writing it
wrong in the first place. :)

Junio, whatever you apply, please credit Linus; he beat me to the fix
and so my patch is completely cribbed from his. :)

-Peff

pointer to pointer (was: gitk problems: can't unset "idinlist(...)")

[David Kastrup]

[-- Attachment #1: Type: text/plain, Size: 1445 bytes --]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Anyway, just because this is actually something I've noticed a lot
> of people do wrong, I actually do tend to think that when you
> traverse a singly-linked list and remove entries, you should *never*
> traverse the list itself, you should only ever traverse the "pointer
> to the pointer".

When I have doubly-linked lists where there is only forward traversal
(the backlink being for convenient deletions without context), I make
the backlink a pointer to pointer.  This also means that one can
remove at the front of the list without needing to know the head
separately.

Anyway, here is some really, really ancient code of mine (file date is
of 1990 but it's older than that) which sorts linked lists stably
without extra storage and makes heavy use of pointer to pointer
traversal in both code and interface.  There is also a strictly
non-recursive variant with the same data flow (except for never making
a redundant assignment) and just one instead of two functions which
consistently beats good qsort implementations, but this old version is
quite more fun to read.

Basically, if head is the pointer to a sorted list of at least n
elements, mergesort(&head, n) will sort the first n elements and
return a pointer to that link which contains the tail of the list.  So
if you did not already 0-terminate your list, *mergesort(&head,n)=0;
will both sort and terminate your list.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Stable Mergesort on linked lists --]
[-- Type: text/x-csrc, Size: 1007 bytes --]

#include "mergesrt.h"
int (*mergecompare)(void *p1, void *p2);
int mergelink;
#define getlink(adr) (*(void**)((char*)(adr)+mergelink))

static void **merge(void **head1, void **tail1, void **tail2, unsigned n1, unsigned n2)
{
	register void *p1 = *head1, *p2 = *tail1;
	for(;;) {
		if ((*mergecompare)(p1, p2) <= 0) {
			p1 = *(head1 = &getlink(*head1 = p1));
			if (--n1 == 0)
				return *head1 = p2, tail2;
		} else {
			p2 = *(head1 = &getlink(*head1 = p2));
			if (--n2 == 0)
				return *tail1 = p2, *head1 = p1, tail1;
		}
	}
}


void **mergesort(void **head, unsigned n)
{
	switch (n) {
	case 0:
		return head;
	case 1:
		return &getlink(*head);
	case 2:
		{
			register void *p1, *p2;

			p2 = getlink(p1 = *head);
			if ((*mergecompare)(p1, p2) <= 0)
				return &getlink(p2);
			getlink(p1) = getlink(*head=p2);
			return &getlink(getlink(p2) = p1);
		}
	default:
		{
			unsigned m;
			void **h2;
			n -= m = n / 2;
			h2 = mergesort(head, n);
			return merge(head,h2,mergesort(h2,m),n,m);
		}
	}
}

[-- Attachment #3: Type: text/plain, Size: 52 bytes --]



-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: pointer to pointer

[David Kastrup]

David Kastrup <dak@gnu.org> writes:

    Content-Type: text/x-csrc
    Content-Disposition: attachment
    Content-Description: Stable Mergesort on linked lists

Sorry, this was supposed to be inline.  I apologize for the
inconvenience.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: gitk problems: can't unset "idinlist(...)"

[Paul Mackerras]

Linus Torvalds writes:

> Somebody who knows 
> tcl/tk, and gitk?

That sounds like me. :)  I see from the following messages that the
bug turned out to be elsewhere in git, but it looks like gitk should
be more robust and do something sensible rather than just throwing a
Tcl error.  I'll look at it.

Paul.