Re: [PATCH 12/19] tree-diff: remove special-case diff-emitting code for empty-tree cases

From: Kirill Smelkov <kirr@navytux.spb.ru>
Date: Mar 25, 2014, 09:20 UTC
Message-ID: <20140325092040.GA3777@mini.zxlink>
In-Reply-To: <xmqqior3pa7h.fsf@gitster.dls.corp.google.com>

On Mon, Mar 24, 2014 at 02:18:10PM -0700, Junio C Hamano wrote:

Show 7 quoted lines

> Kirill Smelkov <kirr@mns.spb.ru> writes:
> 
> > via teaching tree_entry_pathcmp() how to compare empty tree descriptors:
> 
> Drop this line, as you explain the "pretend empty compares bigger
> than anything else" idea later anyway?  This early part of the
> proposed log message made me hiccup while reading it.

Hmm, I was trying to show the big picture first and only then details...

Show 26 quoted lines

> > While walking trees, we iterate their entries from lowest to highest in
> > sort order, so empty tree means all entries were already went over.
> >
> > If we artificially assign +infinity value to such tree "entry", it will
> > go after all usual entries, and through the usual driver loop we will be
> > taking the same actions, which were hand-coded for special cases, i.e.
> >
> >     t1 empty, t2 non-empty
> >         pathcmp(+∞, t2) -> +1
> >         show_path(/*t1=*/NULL, t2);     /* = t1 > t2 case in main loop */
> >
> >     t1 non-empty, t2-empty
> >         pathcmp(t1, +∞) -> -1
> >         show_path(t1, /*t2=*/NULL);     /* = t1 < t2 case in main loop */
> 
> Sounds good.  I would have phrased a bit differently, though:
> 
>     When we have T1 and T2, we return a sign that tells the caller
>     to indicate the "earlier" one to be emitted, and by returning
>     the sign that causes the non-empty side to be emitted, we will
>     automatically cause the entries from the remaining side to be
>     emitted, without attempting to touch the empty side at all.  We
>     can teach tree_entry_pathcmp() to pretend that an empty tree has
>     an element that sorts after anything else to achieve this.
> 
> without saying "infinity".

Doesn't your description, especially "an element that sorts after anything else" match what "infinity" is pretty exactly? :)

I agree it could read more clearly to those new to the concept, but we are basically talking about the same thing and once someone is familiar with infinity and its friends the second description imho is less obvious.

Let's maybe as a compromise add your text as "In other words <textual description ...>" ?

This way, it will hopefully be good both ways...

> > Right now we never go to when compared tree descriptors are infinity,...
> 
> Sorry, but I cannot parse this.

Sorry, I've omitted one word here. It should read

    "Right now we never go to when compared tree descriptors are _both_ infinity,..."

i.e. right now we never call tree_entry_pathcmp with both t1 and t2 being empty.

Show 8 quoted lines

> > as
> > this condition is checked in the loop beginning as finishing criteria,
> 
> What condition and which loop?  The loop that immediately surrounds
> the callsite of tree_entry_pathcmp() is the infinite "for (;;) {" loop,
> and after it prepares t1 and t2 by skipping paths outside pathspec,
> we check if both are empty (i.e. we ran out).  Is that the condition
> you are referring to?

Yes exactly. Modulo diff_can_quit_early() logic, we break from loop in diff_tree (the loop in which special-case diff-tree emitting code was) when both trees were scanned to the end, i.e.

        if (!t1->size && !t2->size)
                break;

in other words when both t1 and t2 are "+∞".

Because of that, at this stage we will never go into tree_entry_pathcmp with (+∞,+∞) arguments, which could mean (!t1->size && !t2->size) case could be unnecessary in tree_entry_pathcmp and should not be coded at all...

> > but will do in the future, when there will be several parents iterated
> > simultaneously, and some pair of them would run to the end.

... I was trying to say this case will probably be needed later, and that it is better to have it for generality.

I hope this should be more clear once that prologue with "both" included is not confusing.

Show 22 quoted lines

> > Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
> > Signed-off-by: Junio C Hamano <gitster@pobox.com>
> > ---
> >
> > ( re-posting without change )
> >
> >  tree-diff.c | 21 +++++++++------------
> >  1 file changed, 9 insertions(+), 12 deletions(-)
> >
> > diff --git a/tree-diff.c b/tree-diff.c
> > index cf96ad7..2fd6d0e 100644
> > --- a/tree-diff.c
> > +++ b/tree-diff.c
> > @@ -12,12 +12,19 @@
> >   *
> >   * NOTE files and directories *always* compare differently, even when having
> >   *      the same name - thanks to base_name_compare().
> > + *
> > + * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty.
> 
> The basic idea is very sane.  It is a nice (and obvious---once you
> are told about the trick) and clean restructuring of the code.

Thanks. I was surprised it is seen as a trick, as infinity is very handy and common concept in many areas and in sorting too.

Show 14 quoted lines

> 
> >   */
> >  static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
> >  {
> >  	struct name_entry *e1, *e2;
> >  	int cmp;
> >  
> > +	if (!t1->size)
> > +		return t2->size ? +1 /* +∞ > c */  : 0 /* +∞ = +∞ */;
> > +	else if (!t2->size)
> > +		return -1;	/* c < +∞ */
> 
> Where do these "c" come from?  I somehow feel that these comments
> are making it harder to understand what is going on.

"c" means some finite "c"onstant here. When I was studying at school and at the university, it was common to denote constants via this letter - i.e. in algebra and operators they often show scalar multiplication as

    c·A     (or α·A)

etc. I understand it could maybe be confusing (but it came to me as surprise), so would the following be maybe better:

        if (!t1->size)
        	return t2->size ? +1 /* +∞ > const */  : 0 /* +∞ = +∞ */;
        else if (!t2->size)
        	return -1;	/* const < +∞ */

Thanks, Kirill

Show 23 quoted lines

> >  	e1 = &t1->entry;
> >  	e2 = &t2->entry;
> >  	cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
> > @@ -151,18 +158,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
> >  			skip_uninteresting(t1, &base, opt);
> >  			skip_uninteresting(t2, &base, opt);
> >  		}
> > -		if (!t1->size) {
> > -			if (!t2->size)
> > -				break;
> > -			show_path(&base, opt, /*t1=*/NULL, t2);
> > -			update_tree_entry(t2);
> > -			continue;
> > -		}
> > -		if (!t2->size) {
> > -			show_path(&base, opt, t1, /*t2=*/NULL);
> > -			update_tree_entry(t1);
> > -			continue;
> > -		}
> > +		if (!t1->size && !t2->size)
> > +			break;
> >  
> >  		cmp = tree_entry_pathcmp(t1, t2);