From: Junio C Hamano <gitster@pobox.com>
To: Kirill Smelkov <kirr@navytux.spb.ru>
Cc: kirr@mns.spb.ru, git@vger.kernel.org
Subject: Re: [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well
Date: Mon, 07 Apr 2014 11:07:47 -0700 [thread overview]
Message-ID: <xmqqmwfxm2rw.fsf@gitster.dls.corp.google.com> (raw)
In-Reply-To: <20140406214626.GA3843@mini.zxlink> (Kirill Smelkov's message of "Mon, 7 Apr 2014 01:46:26 +0400")
Kirill Smelkov <kirr@navytux.spb.ru> writes:
>> > + 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.
>
> Yes, correct (modulo we *will* go to skip label if any one of the
> parent's entry sorts after some other parent). By definition of combined
> diff we show a path only if it shows in every diff D(T,Pi), and if
>
> 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀ pi=p[imin] pi↓
>
> some pj sorts after p[imin] that would mean that Pj does not have
> p[imin] and since t > p[imin] (which means T does not have p[imin]
> either) diff D(T,Pj) does not have p[imin]. And because of that we know
> the whole combined-diff will not have p[imin] as, by definition,
> combined diff is sets intersection and one of the sets does not have
> that path.
>
> ( In usual words p[imin] is not changed between Pj..T - it was
> e.g. removed in Pj~, so merging parents to T does not bring any new
> information wrt path p[imin] and that is why we do not want to show
> p[imin] in combined-diff output - no new change about that path )
>
> So nothing to append to the output, and update minimum tree entries,
> preparing for the next step.
That's all in line with the current and traditional definition of
combined diff.
This is a tangent that is outside the scope of this current topic,
but I wonder if you found it disturbing that we treat the result 't'
that has a path and the result 't' that does not have a path with
respect to a parent that does not have the path in a somewhat
assymmetric way.
With a merge M between commits A and B, where they all have the same
path with different contents, we obviously show that path in the
combined diff format. A merge N that records exactly the same tree
as M that merges the same commits A and B plus another commit C that
does not have that path still shows the combined diff, with one
extra column to express "everything in the result N has been added
with respect to C which did not have the path at all".
However, a merge O between the same commits A and B, where A and B
have a path and O loses it, shows the path in the combined format.
A merge P among the same A, B and an extra parent C that does not
have that path ceases to show it (this is the assymmetry).
It is a natural extension of "Do not show the path when the result
matches one of the parent" rule, and in this case the result P takes
contents, "the path does not exist", from one parent "C", so it is
internally consistent, and I originally designed it that way on
purpose, but somehow it feels a bit strange.
next prev parent reply other threads:[~2014-04-07 18:07 UTC|newest]
Thread overview: 64+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-02-24 16:21 [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup Kirill Smelkov
2014-02-24 16:21 ` [PATCH 01/19] combine-diff: move show_log_first logic/action out of paths scanning Kirill Smelkov
2014-02-24 16:21 ` [PATCH 02/19] combine-diff: move changed-paths scanning logic into its own function Kirill Smelkov
2014-02-24 16:21 ` [PATCH 03/19] tree-diff: no need to manually verify that there is no mode change for a path Kirill Smelkov
2014-02-24 16:21 ` [PATCH 04/19] tree-diff: no need to pass match to skip_uninteresting() Kirill Smelkov
2014-02-24 16:21 ` [PATCH 05/19] tree-diff: show_tree() is not needed Kirill Smelkov
2014-02-24 16:21 ` [PATCH 06/19] tree-diff: consolidate code for emitting diffs and recursion in one place Kirill Smelkov
2014-02-24 16:21 ` [PATCH 07/19] tree-diff: don't assume compare_tree_entry() returns -1,0,1 Kirill Smelkov
2014-02-24 16:21 ` [PATCH 08/19] tree-diff: move all action-taking code out of compare_tree_entry() Kirill Smelkov
2014-02-24 16:21 ` [PATCH 09/19] tree-diff: rename compare_tree_entry -> tree_entry_pathcmp Kirill Smelkov
2014-02-24 16:21 ` [PATCH 10/19] tree-diff: show_path prototype is not needed anymore Kirill Smelkov
2014-02-24 16:21 ` [PATCH 11/19] tree-diff: simplify tree_entry_pathcmp Kirill Smelkov
2014-03-24 21:25 ` Junio C Hamano
2014-03-25 9:23 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH 12/19] tree-diff: remove special-case diff-emitting code for empty-tree cases Kirill Smelkov
2014-03-24 21:18 ` Junio C Hamano
2014-03-25 9:20 ` Kirill Smelkov
2014-03-25 17:45 ` Junio C Hamano
2014-03-26 18:32 ` Kirill Smelkov
2014-03-25 22:07 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH 13/19] tree-diff: diff_tree() should now be static Kirill Smelkov
2014-02-24 16:21 ` [PATCH v2 14/19] tree-diff: rework diff_tree interface to be sha1 based Kirill Smelkov
2014-03-24 21:36 ` Junio C Hamano
2014-03-25 9:22 ` Kirill Smelkov
2014-03-25 17:46 ` Junio C Hamano
2014-03-26 19:52 ` Kirill Smelkov
2014-03-26 21:34 ` Junio C Hamano
2014-03-27 14:24 ` Kirill Smelkov
2014-03-27 18:48 ` Junio C Hamano
2014-03-27 19:43 ` Kirill Smelkov
2014-03-28 6:52 ` Johannes Sixt
2014-03-28 17:06 ` Junio C Hamano
2014-03-28 17:46 ` Johannes Sixt
2014-03-28 18:36 ` Junio C Hamano
2014-03-28 19:08 ` Johannes Sixt
2014-03-28 19:27 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH 15/19] tree-diff: no need to call "full" diff_tree_sha1 from show_path() Kirill Smelkov
2014-03-27 14:21 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH v2 16/19] tree-diff: reuse base str(buf) memory on sub-tree recursion Kirill Smelkov
2014-03-24 21:43 ` Junio C Hamano
2014-03-25 9:23 ` Kirill Smelkov
2014-03-27 14:22 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH 17/19] Portable alloca for Git Kirill Smelkov
2014-02-28 10:58 ` Thomas Schwinge
2014-02-28 13:44 ` Erik Faye-Lund
2014-02-28 13:50 ` Erik Faye-Lund
2014-02-28 17:00 ` Kirill Smelkov
2014-02-28 17:19 ` Erik Faye-Lund
2014-03-05 9:31 ` Kirill Smelkov
2014-03-24 21:47 ` Junio C Hamano
2014-03-27 14:22 ` Kirill Smelkov
2014-04-09 12:48 ` Kirill Smelkov
2014-04-09 13:01 ` Erik Faye-Lund
2014-04-10 17:30 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well Kirill Smelkov
2014-03-27 14:23 ` Kirill Smelkov
2014-04-04 18:42 ` Junio C Hamano
2014-04-06 21:46 ` Kirill Smelkov
2014-04-07 17:29 ` Junio C Hamano
2014-04-07 20:26 ` Kirill Smelkov
2014-04-07 18:07 ` Junio C Hamano [this message]
2014-02-24 16:21 ` [PATCH 19/19] combine-diff: speed it up, by using multiparent diff tree-walker directly Kirill Smelkov
2014-02-24 23:43 ` [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup Duy Nguyen
2014-02-25 10:38 ` Kirill Smelkov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqmwfxm2rw.fsf@gitster.dls.corp.google.com \
--to=gitster@pobox.com \
--cc=git@vger.kernel.org \
--cc=kirr@mns.spb.ru \
--cc=kirr@navytux.spb.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).