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

From: Junio C Hamano <[email-masked]>
Date: Mon, 24 Mar 2014 14:18:10 -0700

Kirill Smelkov <[email-masked]> 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.

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

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

Sorry, but I cannot parse this.

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

> but will do in the future, when there will be several parents iterated
> simultaneously, and some pair of them would run to the end.
>
> Signed-off-by: Kirill Smelkov <[email-masked]>
> Signed-off-by: Junio C Hamano <[email-masked]>
> ---
>
> ( 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.

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

>  	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);