Re: [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Apr 4, 2014, 18:42 UTC
- Message-ID
- <xmqqppkxos0w.fsf@gitster.dls.corp.google.com>
- In-Reply-To
- <20140327142354.GD17333@mini.zxlink>
Kirill Smelkov <kirr@navytux.spb.ru> writes:
> +extern > +struct combine_diff_path *diff_tree_paths(
These two on the same line, please.
Show 14 quoted lines
> + 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.
Show 23 quoted lines
> +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.
Show 5 quoted lines
> +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.
Show 83 quoted lines
> +/*
> + * 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.
Show 20 quoted lines
> + /* 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.
Show 21 quoted lines
> + /* 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.
Show 8 quoted lines
> }
>
> - /* 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"?
Show 12 quoted lines
> + 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.
Show 34 quoted lines
> +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.