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

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jul 23, 2008, 19:33 UTC
Message-ID: <alpine.DEB.1.00.0807232014260.8986@racer>
In-Reply-To: <7vprp4ctkp.fsf@gitster.siamese.dyndns.org>

Hi,

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

Show 28 quoted lines

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

Show 8 quoted lines

> 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