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

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 23, 2008, 19:02 UTC
Message-ID: <7vprp4ctkp.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.DEB.1.00.0807230150480.8986@racer>

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

Show 18 quoted lines

> @@ -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.