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

From: Junio C Hamano <[email-masked]>
Date: Wed, 23 Jul 2008 12:02:30 -0700

Johannes Schindelin <[email-masked]> 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.