Re: [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well

[Junio C Hamano <gitster@pobox.com>]

Kirill Smelkov <kirr@navytux.spb.ru> writes:

> +extern
> +struct combine_diff_path *diff_tree_paths(

These two on the same line, please.

> +	struct combine_diff_path *p, const unsigned char *sha1,
> +	const unsigned char **parent_sha1, int nparent,
> +	struct strbuf *base, struct diff_options *opt);
>  extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,
>  			  const char *base, struct diff_options *opt);
> ...
> +/*
> + * convert path -> opt->diff_*() callbacks
> + *
> + * emits diff to first parent only, and tells diff tree-walker that we are done
> + * with p and it can be freed.
> + */
> +static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
>  {

Very straight-forward; good.

> +static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
> +	int nparent, const struct strbuf *base, const char *path, int pathlen,
> +	unsigned mode, const unsigned char *sha1)
> +{
> +	struct combine_diff_path *p;
> +	int len = base->len + pathlen;
> +	int alloclen = combine_diff_path_size(nparent, len);
> +
> +	/* if last->next is !NULL - it is a pre-allocated memory, we can reuse */
> +	p = last->next;
> +	if (p && (alloclen > (intptr_t)p->next)) {
> +		free(p);
> +		p = NULL;
> +	}
> +
> +	if (!p) {
> +		p = xmalloc(alloclen);
> +
> +		/*
> +		 * until we go to it next round, .next holds how many bytes we
> +		 * allocated (for faster realloc - we don't need copying old data).
> +		 */
> +		p->next = (struct combine_diff_path *)(intptr_t)alloclen;

This reuse of the .next field is somewhat yucky, but it is very
localized inside a function that has a single callsite to this
function, so let's let it pass.

> +static struct combine_diff_path *emit_path(struct combine_diff_path *p,
> +	struct strbuf *base, struct diff_options *opt, int nparent,
> +	struct tree_desc *t, struct tree_desc *tp,
> +	int imin)
>  {

Again, fairly straight-forward and good.

> +/*
> + * generate paths for combined diff D(sha1,parents_sha1[])
> + ...
> +static struct combine_diff_path *ll_diff_tree_paths(
> +	struct combine_diff_path *p, const unsigned char *sha1,
> +	const unsigned char **parents_sha1, int nparent,
> +	struct strbuf *base, struct diff_options *opt)
> +{
> +	struct tree_desc t, *tp;
> +	void *ttree, **tptree;
> +	int i;
> +
> +	tp     = xalloca(nparent * sizeof(tp[0]));
> +	tptree = xalloca(nparent * sizeof(tptree[0]));
> +
> +	/*
> +	 * load parents first, as they are probably already cached.
> +	 *
> +	 * ( log_tree_diff() parses commit->parent before calling here via
> +	 *   diff_tree_sha1(parent, commit) )
> +	 */
> +	for (i = 0; i < nparent; ++i)
> +		tptree[i] = fill_tree_descriptor(&tp[i], parents_sha1[i]);
> +	ttree = fill_tree_descriptor(&t, sha1);
>  
>  	/* Enable recursion indefinitely */
>  	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
>  
>  	for (;;) {
> -		int cmp;
> +		int imin, cmp;
>  
>  		if (diff_can_quit_early(opt))
>  			break;
> +
>  		if (opt->pathspec.nr) {
> -			skip_uninteresting(&t1, base, opt);
> -			skip_uninteresting(&t2, base, opt);
> +			skip_uninteresting(&t, base, opt);
> +			for (i = 0; i < nparent; i++)
> +				skip_uninteresting(&tp[i], base, opt);
>  		}
> -		if (!t1.size && !t2.size)
> -			break;
>  
> -		cmp = tree_entry_pathcmp(&t1, &t2);
> +		/* comparing is finished when all trees are done */
> +		if (!t.size) {
> +			int done = 1;
> +			for (i = 0; i < nparent; ++i)
> +				if (tp[i].size) {
> +					done = 0;
> +					break;
> +				}
> +			if (done)
> +				break;
> +		}
> +
> +		/*
> +		 * lookup imin = argmin(x1...xn),
> +		 * mark entries whether they =tp[imin] along the way
> +		 */
> +		imin = 0;
> +		tp[0].entry.mode &= ~S_IFXMIN_NEQ;
> +
> +		for (i = 1; i < nparent; ++i) {
> +			cmp = tree_entry_pathcmp(&tp[i], &tp[imin]);
> +			if (cmp < 0) {
> +				imin = i;
> +				tp[i].entry.mode &= ~S_IFXMIN_NEQ;
> +			}
> +			else if (cmp == 0) {
> +				tp[i].entry.mode &= ~S_IFXMIN_NEQ;
> +			}
> +			else {
> +				tp[i].entry.mode |= S_IFXMIN_NEQ;
> +			}
> +		}
> +
> +		/* fixup markings for entries before imin */
> +		for (i = 0; i < imin; ++i)
> +			tp[i].entry.mode |= S_IFXMIN_NEQ;	/* x[i] > x[imin] */
> +

These two loop made my reading hiccup for a while.  With these you
are scanning the tp[] array 1.5 times (and doing the bitwise
assignment to entry.mode 1.5 * nparent times), but I suspect it may
have been a lot easier to read if the first loop only identified the
imin, and the second loop only did the entry.mode for _all_ nparents.

> +		/* compare a vs x[imin] */
> +		cmp = tree_entry_pathcmp(&t, &tp[imin]);
> +
> +		/* a = xi */
> +		if (cmp == 0) {
> +			/* are either xk > xi or diff(a,xk) != ø ? */
> +			if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {
> +				for (i = 0; i < nparent; ++i) {
> +					/* x[i] > x[imin] */
> +					if (tp[i].entry.mode & S_IFXMIN_NEQ)
> +						continue;
> +
> +					/* diff(a,xk) != ø */
> +					if (hashcmp(t.entry.sha1, tp[i].entry.sha1) ||
> +					    (t.entry.mode != tp[i].entry.mode))
> +						continue;
> +
> +					goto skip_emit_t_tp;
> +				}
> +			}

Please bear with me.  The notation scares me as I am not good at math.

In short, the above loop is about:

    We are looking at path in 't' and some parents have the same
    path.  If any of these parents have that path with the contents
    identical to 't', then do not emit this path.

which makes sense to me, but these notation also made my reading
hiccup, especially because it is hard to guess what "xk" refers to
(e.g. "any k where 0 <= k < nparent && i != k"? "all such k"?).  I
still haven't figured out what you meant to say with "xk", but I
think I got what the code wants to do.

How does the "the (virtual) path from a tree that has ran out of
entries sorts later than anything else" comparison rule influence
the picture?  A parent that has ran out would have _NEQ bit set and
would not count as having the same contents as the path from 't'.
If 't' has ran out, the only way t and tp[imin] could compare equal
is when tp[imin] has also ran out, but that can happen only when all
the parents are done with, so we would have broken out of the loop
even before we try to figure out imin.  So there is no funnies
there, which is good.

> +			/* D += {δ(a,xk) if xk=xi;  "+a" if xk > xi} */
> +			p = emit_path(p, base, opt, nparent,
> +					&t, tp, imin);
> +
> +		skip_emit_t_tp:
> +			/* a↓,  ∀ xk=ximin  xk↓ */
> +			update_tree_entry(&t);
> +			update_tp_entries(tp, nparent);
>  		}
>  
> -		/* t1 < t2 */
> +		/* a < xi */
>  		else if (cmp < 0) {
> -			show_path(base, opt, &t1, /*t2=*/NULL);
> -			update_tree_entry(&t1);
> +			/* D += "+a" */
> +			p = emit_path(p, base, opt, nparent,
> +					&t, /*tp=*/NULL, -1);
> +
> +			/* a↓ */
> +			update_tree_entry(&t);

This is straight-forward.  No parent has path 't' has, so only the
entry from 't' is given, and we deal with the next entry in 't'
without touching any of the parents in the next iteration.  Good.

>  		}
>  
> -		/* t1 > t2 */
> +		/* a > xi */
>  		else {
> -			show_path(base, opt, /*t1=*/NULL, &t2);
> -			update_tree_entry(&t2);
> +			/* ∀j xj=ximin -> D += "-xi" */

Did you mean "-xj"?

> +			if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {
> +				for (i = 0; i < nparent; ++i)
> +					if (tp[i].entry.mode & S_IFXMIN_NEQ)
> +						goto skip_emit_tp;
> +			}
> +
> +			p = emit_path(p, base, opt, nparent,
> +					/*t=*/NULL, tp, imin);
> +
> +		skip_emit_tp:
> +			/* ∀ xk=ximin  xk↓ */
> +			update_tp_entries(tp, nparent);

There are parents whose path sort earlier than what is in 't'
(i.e. they were lost in the result---we would want to show
removal).  What makes us jump to the skip label?

    We are looking at path in 't', and some parents have paths that
    sort earlier than that path.  We will not go to skip label if
    any one of the parent's entry sorts after some other parent (or
    the parent in question has ran out its entries), which means we
    show the entry from the parents only when all the parents have
    that same path, which is missing from 't'.

I am not sure if I am reading this correctly, though.

For the two-way diff, the above degenerates to "show all parent
entries that come before the first entry in 't'", which is correct.
For the combined diff, the current intersect_paths() makes sure that
each path appears in all the pair-wise diff between t and tp[],
which again means that the above logic match the current behaviour.


> +struct combine_diff_path *diff_tree_paths(
> +	struct combine_diff_path *p, const unsigned char *sha1,
> +	const unsigned char **parents_sha1, int nparent,
> +	struct strbuf *base, struct diff_options *opt)
> +{
> +	p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
> +
> +	/*
> +	 * free pre-allocated last element, if any
> +	 * (see path_appendnew() for details about why)
> +	 */
> +	if (p->next) {
> +		free(p->next);
> +		p->next = NULL;
> +	}
> +
> +	return p;
>  }
>  
>  /*
> @@ -308,6 +664,27 @@ static void try_to_follow_renames(const unsigned char *old, const unsigned char
>  	q->nr = 1;
>  }
>  
> +static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
> +			     struct strbuf *base, struct diff_options *opt)
> +{
> +	struct combine_diff_path phead, *p;
> +	const unsigned char *parents_sha1[1] = {old};
> +	pathchange_fn_t pathchange_old = opt->pathchange;
> +
> +	phead.next = NULL;
> +	opt->pathchange = emit_diff_first_parent_only;
> +	diff_tree_paths(&phead, new, parents_sha1, 1, base, opt);

Hmph.  I would have expected

	const unsigned char **parents_sha1 = &old;

or even

	diff_tree_paths(&phead, new, &old, 1, base, opt);

here.


Thanks.