[PATCH 1/2] Add test to show that show-branch misses out the 8th column

[PATCH 1/2] Add test to show that show-branch misses out the 8th column

[Johannes Schindelin]

Noticed by Pasky.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 t/t3202-show-branch-octopus.sh |   59 ++++++++++++++++++++++++++++++++++++++++
 1 files changed, 59 insertions(+), 0 deletions(-)
 create mode 100755 t/t3202-show-branch-octopus.sh

diff --git a/t/t3202-show-branch-octopus.sh b/t/t3202-show-branch-octopus.sh
new file mode 100755
index 0000000..8d50c23
--- /dev/null
+++ b/t/t3202-show-branch-octopus.sh
@@ -0,0 +1,59 @@
+#!/bin/sh
+
+test_description='test show-branch with more than 8 heads'
+
+. ./test-lib.sh
+
+numbers="1 2 3 4 5 6 7 8 9 10"
+
+test_expect_success 'setup' '
+
+	> file &&
+	git add file &&
+	test_tick &&
+	git commit -m initial &&
+
+	for i in $numbers
+	do
+		git checkout -b branch$i master &&
+		> file$i &&
+		git add file$i &&
+		test_tick &&
+		git commit -m branch$i || break
+	done
+
+'
+
+cat > expect << EOF
+! [branch1] branch1
+ ! [branch2] branch2
+  ! [branch3] branch3
+   ! [branch4] branch4
+    ! [branch5] branch5
+     ! [branch6] branch6
+      ! [branch7] branch7
+       ! [branch8] branch8
+        ! [branch9] branch9
+         * [branch10] branch10
+----------
+         * [branch10] branch10
+        +  [branch9] branch9
+       +   [branch8] branch8
+      +    [branch7] branch7
+     +     [branch6] branch6
+    +      [branch5] branch5
+   +       [branch4] branch4
+  +        [branch3] branch3
+ +         [branch2] branch2
++          [branch1] branch1
++++++++++* [branch10^] initial
+EOF
+
+test_expect_failure 'show-branch with more than 8 branches' '
+
+	git show-branch $(for i in $numbers; do echo branch$i; done) > out &&
+	test_cmp expect out
+
+'
+
+test_done
-- 
1.6.0.rc0.22.gf2096d.dirty

[PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Johannes Schindelin]

We used to set the TOPOSORT flag of commits during the topological
sorting, but we can just as well use the member "indegree" for it:
indegree is now incremented by 1 in the cases where the commit used
to have the TOPOSORT flag.

This is the same behavior as before, since indegree could not be
non-zero when TOPOSORT was unset.

Incidentally, this fixes the bug in show-branch where the 8th column
was not shown: show-branch sorts the commits in topological order,
assuming that all the commit flags are available for show-branch's
private matters.

But this was not true: TOPOSORT was identical to the flag corresponding
to the 8th ref.  So the flags for the 8th column were unset by the
topological sorting.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	This is another late-night patch done by yours-truly.  However,
	I tried extra hard to make sure that every occurrence of
	indegree was properly changed, and I am pretty certain that
	the reasoning with the unset TOPOSORT is correct.

	But please check (I know, not necessary to ask for extra review
	for my patches,	but nevertheless).

 commit.c                       |   13 ++++++-------
 revision.h                     |    3 +--
 t/t3202-show-branch-octopus.sh |    2 +-
 3 files changed, 8 insertions(+), 10 deletions(-)

diff --git a/commit.c b/commit.c
index 5148ec5..9dacfb8 100644
--- a/commit.c
+++ b/commit.c
@@ -436,8 +436,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	/* Mark them and clear the indegree */
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
-		commit->object.flags |= TOPOSORT;
-		commit->indegree = 0;
+		commit->indegree = 1;
 	}
 
 	/* update the indegree */
@@ -446,7 +445,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		while (parents) {
 			struct commit *parent = parents->item;
 
-			if (parent->object.flags & TOPOSORT)
+			if (parent->indegree)
 				parent->indegree++;
 			parents = parents->next;
 		}
@@ -464,7 +463,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
 
-		if (!commit->indegree)
+		if (commit->indegree == 1)
 			insert = &commit_list_insert(commit, insert)->next;
 	}
 
@@ -486,7 +485,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent=parents->item;
 
-			if (!(parent->object.flags & TOPOSORT))
+			if (!parent->indegree)
 				continue;
 
 			/*
@@ -494,7 +493,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * when all their children have been emitted thereby
 			 * guaranteeing topological order.
 			 */
-			if (!--parent->indegree) {
+			if (--parent->indegree == 1) {
+				parent->indegree = 0;
 				if (!lifo)
 					insert_by_date(parent, &work);
 				else
@@ -505,7 +505,6 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		 * work_item is a commit all of whose children
 		 * have already been emitted. we can emit it now.
 		 */
-		commit->object.flags &= ~TOPOSORT;
 		*pptr = work_item;
 		pptr = &work_item->next;
 	}
diff --git a/revision.h b/revision.h
index fa68c65..f64e8ce 100644
--- a/revision.h
+++ b/revision.h
@@ -12,8 +12,7 @@
 #define CHILD_SHOWN	(1u<<6)
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
 #define SYMMETRIC_LEFT	(1u<<8)
-#define TOPOSORT	(1u<<9)	/* In the active toposort list.. */
-#define ALL_REV_FLAGS	((1u<<10)-1)
+#define ALL_REV_FLAGS	((1u<<9)-1)
 
 struct rev_info;
 struct log_info;
diff --git a/t/t3202-show-branch-octopus.sh b/t/t3202-show-branch-octopus.sh
index 8d50c23..7fe4a6e 100755
--- a/t/t3202-show-branch-octopus.sh
+++ b/t/t3202-show-branch-octopus.sh
@@ -49,7 +49,7 @@ cat > expect << EOF
 +++++++++* [branch10^] initial
 EOF
 
-test_expect_failure 'show-branch with more than 8 branches' '
+test_expect_success 'show-branch with more than 8 branches' '
 
 	git show-branch $(for i in $numbers; do echo branch$i; done) > out &&
 	test_cmp expect out
-- 
1.6.0.rc0.22.gf2096d.dirty

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> This is the same behavior as before, since indegree could not be
> non-zero when TOPOSORT was unset.
>
> Incidentally, this fixes the bug in show-branch where the 8th column
> was not shown: show-branch sorts the commits in topological order,
> assuming that all the commit flags are available for show-branch's
> private matters.

Do people still actively use show-branch as a G/CUI, especially after that
"log --graph" thing was introduced?

If that is the case, it might also make sense to stop using the object
flags but allocate necessary number of bits (not restricted to 25 or so)
pointed at by commit->util field to remove its limitation.

Hint, hint...

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Jon Loeliger]

Junio C Hamano wrote:
> 
> Do people still actively use show-branch as a G/CUI, especially after that
> "log --graph" thing was introduced?

At the risk of sounding Old School, yes.

While the "log --graph" thing is Really Slick, it has
grumbly-factors, IMO.  First, I have to set up an alias
all the time, as "git log --graph --pretty=oneline" is
grumpy typing.  Second, I always have to widen my screen
to accommodate reasonable looking output or colrm it.
(Having it self-colrm to window-width would be nice.)
(Sure, --abbrev-commit too, but see "First," above. :-))
Finally, I frequently like seeing a self-limited history
when all the branches reach their common ancestor.

HTH,
jdl

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Petr Baudis]

On Tue, Jul 22, 2008 at 06:01:30PM -0700, Junio C Hamano wrote:
> Do people still actively use show-branch as a G/CUI, especially after that
> "log --graph" thing was introduced?

To me, show-branch is just more convenient to use; I can see more easily
which patches are with which branches, which is useful especially for my
new sick-twisted use of feature branches for individual patches, thus
having a lot of interdependencies.

> If that is the case, it might also make sense to stop using the object
> flags but allocate necessary number of bits (not restricted to 25 or so)
> pointed at by commit->util field to remove its limitation.
> 
> Hint, hint...

Maybe I will hit it soon... ;-)

-- 
				Petr "Pasky" Baudis
As in certain cults it is possible to kill a process if you know
its true name.  -- Ken Thompson and Dennis M. Ritchie

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Junio C Hamano]

Petr Baudis <pasky@suse.cz> writes:

> On Tue, Jul 22, 2008 at 06:01:30PM -0700, Junio C Hamano wrote:
>> Do people still actively use show-branch as a G/CUI, especially after that
>> "log --graph" thing was introduced?
>
> To me, show-branch is just more convenient to use; I can see more easily
> which patches are with which branches, which is useful especially for my
> new sick-twisted use of feature branches for individual patches, thus
> having a lot of interdependencies.

Heh, I still recall hearing from many people that its output is hard to
decipher and UI is unintuitive.  What changed their mind, I have to
wonder...

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> @@ -494,7 +493,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
>  			 * when all their children have been emitted thereby
>  			 * guaranteeing topological order.
>  			 */
> -			if (!--parent->indegree) {
> +			if (--parent->indegree == 1) {
> +				parent->indegree = 0;
>  				if (!lifo)
>  					insert_by_date(parent, &work);
>  				else
> @@ -505,7 +505,6 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
>  		 * work_item is a commit all of whose children
>  		 * have already been emitted. we can emit it now.
>  		 */
> -		commit->object.flags &= ~TOPOSORT;
>  		*pptr = work_item;
>  		pptr = &work_item->next;
>  	}

These two hunks look suspicious.

The "tips" used to enter that while() loop with zero indegree, its parents
examined and then entered the final list pointed by pptr with the toposort
scratch variables removed and indegree set to zero.  Now with the new +1
based code, they enter the while() loop with 1 indegree, and enter the
final list with indegree set to 1.

A parent that has only one child that is "tip" is discovered in the
while() loop, its indegree decremented (so it goes down to zero in the
original code and 1 in yours) and enters work queue to be processed.  It
used to have the toposort scratch variable removed in the second hunk
above, but that is done in the first hunk in your version.

So after this patch, indegree will be all zero for non-tip commits but
will be one for tip commits.  Is this intended?

I'd suggest dropping the "parent->indegree = 0" assignment and turn the
second hunk into "commit->indgree = 0" assignment.

Re: [PATCH 2/2] sort_in_topological_order(): avoid setting a commit flag

[Johannes Schindelin]

Hi,

On Wed, 23 Jul 2008, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > @@ -494,7 +493,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
> >  			 * when all their children have been emitted thereby
> >  			 * guaranteeing topological order.
> >  			 */
> > -			if (!--parent->indegree) {
> > +			if (--parent->indegree == 1) {
> > +				parent->indegree = 0;
> >  				if (!lifo)
> >  					insert_by_date(parent, &work);
> >  				else
> > @@ -505,7 +505,6 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
> >  		 * work_item is a commit all of whose children
> >  		 * have already been emitted. we can emit it now.
> >  		 */
> > -		commit->object.flags &= ~TOPOSORT;
> >  		*pptr = work_item;
> >  		pptr = &work_item->next;
> >  	}
> 
> These two hunks look suspicious.
> 
> The "tips" used to enter that while() loop with zero indegree, its 
> parents examined and then entered the final list pointed by pptr with 
> the toposort scratch variables removed and indegree set to zero.  Now 
> with the new +1 based code, they enter the while() loop with 1 indegree, 
> and enter the final list with indegree set to 1.

Almost correct.  The way I did it the if() is entered with indegree == 
1, but is set indegree to 0 right away.

I did it this way because of these two lines before the if():

                        if (!parent->indegree)
                                continue;

These are the replacement for the previous

			if (!(parent->object.flags & TOPOSORT))
                                continue;

Now, if indegree was not set to 0, that if () would not trigger, but in 
the next one (the first hunk you quoted), indegree was decremented and 
failed the test == 1.

However, that is correct only by pure chance; I certainly missed that.  
The correct fix according to my thinking would be to set the indegree to 0 
when the tips are inserted, too.

> A parent that has only one child that is "tip" is discovered in the 
> while() loop, its indegree decremented (so it goes down to zero in the 
> original code and 1 in yours) and enters work queue to be processed.  
> It used to have the toposort scratch variable removed in the second hunk 
> above, but that is done in the first hunk in your version.
> 
> So after this patch, indegree will be all zero for non-tip commits but
> will be one for tip commits.  Is this intended?

No.

> I'd suggest dropping the "parent->indegree = 0" assignment and turn the
> second hunk into "commit->indgree = 0" assignment.

Yeah, that is much simpler.

Thanks,
Dscho