Re: [PATCH v2 1/4] t4059: test 'diff --cc' with a change from only few parents

Max Kirillov [off-list ref] writes:

If `git diff --cc` is used with 2 or more parents, then it shows
all hunks which have changed compared to at least 2 parents.
Which is reasonable, because those places are likely places for
conflicts, and it should be displayed how they were resolved.

OK.

But, preliminary path filtering passes a path only it was changed
compared to each parent.

That is true, but I am a bit confused by the above, especially the
word "But" that begins the sentence.  Are you talking about this
comment that describes what the caller wants to do?

    /* find set of paths that every parent touches */
    static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,
            const struct sha1_array *parents, struct diff_options *opt)

When the result of a merge exactly matches one (or more) of the
parent of the merge, we do not want to show it in the combined
format, so intersect_paths() does want to find paths that are
different from all parents.  Isn't that a good thing?

So, if a hunk which has not changed compared to some of parents is
shown if there are more changed hunks in the file, but not shown
if it is the only change.

This looks inconsistent and for some scenarios it is desirable to show
such changes.

Hmm, that may be true.  So help me see if I understand your goal by
checking if I rephrased you correctly below:

 - We want to show a combined hunk when the number of parent
   variants for the hunk is more than 2 (i.e. interesting octopus)
   or the result does not match any of the parents (i.e. conflict
   resolution of a pairwise merge).  We want to drop a hunk whose
   result came from only one set of parent and the other parents had
   the same original that is different from the result.

 - The current code filters out a path that matches one of the
   parents very early.  This is OK for a two-way merge.  If the
   result matches one of the parent's, then any hunk we might
   produce by not pre-filtering would have the result that came from
   one parent (i.e. the one identical to the result) and there is
   only one other parent, which cannot make it an interesting
   octopus by definition.

   But an octopus may merge three variants and pick the result from
   one of the parents as a whole.  With the pre-filtering, no hunk
   from such a path is shown, even when the other two variants in
   "discarded" parents are not identical.

The original to refer to are two commits bf1c32bd (combine-diff:
update --cc "uninteresting hunks" logic., 2006-02-02) and fd4b1d21
(combine-diff: add safety check to --cc., 2006-02-02).

Especially, we need to pay close attention to the discussion that
germinated the current behaviour:

  http://thread.gmane.org/gmane.comp.version-control.git/15486/focus=15519

I recall that the "diff --cc" before that change was not discarding
uninteresting merges sufficiently and the two commits were a
deliberate attempt to reject what your series wants to show as
uninteresting hunks.  

Two suggestions.

 - This is primarily for 2/4, but can we make it more clear in the
   code that we do this "include more" change only on Octopus
   merges?  This change should not make any difference for two-way
   merges and I'd prefer to avoid extra processing of finding
   matching hunks and combining, only to discard the result.

 - Can you run "diff --cc" with and without your patches to the
   "merge from hell" commit mentioned in the original thread and see
   if we show more hunks with your patches, and make sure what are
   shown additionally looked really "interesting"?

Thanks.

On Sat, Apr 11, 2015 at 2:07 PM, Junio C Hamano [off-list ref] wrote:

Especially, we need to pay close attention to the discussion that
germinated the current behaviour:

  http://thread.gmane.org/gmane.comp.version-control.git/15486/focus=15519

I recall that the "diff --cc" before that change was not discarding
uninteresting merges sufficiently and the two commits were a
deliberate attempt to reject what your series wants to show as
uninteresting hunks.

Two suggestions.

 - This is primarily for 2/4, but can we make it more clear in the

Eh, sorry, I obviously meant 3/4. And let me half-retract this suggestion
and put it on hold; the code-flow has become sufficiently different that
special-casing two-way merge may not be worth it after all.

   code that we do this "include more" change only on Octopus
   merges?  This change should not make any difference for two-way
   merges and I'd prefer to avoid extra processing of finding
   matching hunks and combining, only to discard the result.

 - Can you run "diff --cc" with and without your patches to the
   "merge from hell" commit mentioned in the original thread and see
   if we show more hunks with your patches, and make sure what are
   shown additionally looked really "interesting"?

This one still stands. We'd be interested to see what difference this
makes in the real world project history.

Thanks.

On Sat, Apr 11, 2015 at 02:07:25PM -0700, Junio C Hamano wrote:

Max Kirillov [off-list ref] writes:

quoted

If `git diff --cc` is used with 2 or more parents, then it shows
all hunks which have changed compared to at least 2 parents.
Which is reasonable, because those places are likely places for
conflicts, and it should be displayed how they were resolved.

OK.

quoted

But, preliminary path filtering passes a path only it was changed
compared to each parent.

That is true, but I am a bit confused by the above, especially the
word "But" that begins the sentence.  Are you talking about this
comment that describes what the caller wants to do?

    /* find set of paths that every parent touches */
    static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,
            const struct sha1_array *parents, struct diff_options *opt)

When the result of a merge exactly matches one (or more) of the
parent of the merge, we do not want to show it in the combined
format, so intersect_paths() does want to find paths that are
different from all parents.  Isn't that a good thing?

If it is a good thing, then probably for file which has not
been filtered out it is also a good thing, then diff --cc
should have been hiding hunks which fully preserve one of
the parent.

quoted

So, if a hunk which has not changed compared to some of parents is
shown if there are more changed hunks in the file, but not shown
if it is the only change.

This looks inconsistent and for some scenarios it is desirable to show
such changes.

Hmm, that may be true.  So help me see if I understand your goal by
checking if I rephrased you correctly below:

 - We want to show a combined hunk when the number of parent
   variants for the hunk is more than 2 (i.e. interesting octopus)
   or the result does not match any of the parents (i.e. conflict
   resolution of a pairwise merge).  We want to drop a hunk whose
   result came from only one set of parent and the other parents had
   the same original that is different from the result.

 - The current code filters out a path that matches one of the
   parents very early.  This is OK for a two-way merge.  If the
   result matches one of the parent's, then any hunk we might
   produce by not pre-filtering would have the result that came from
   one parent (i.e. the one identical to the result) and there is
   only one other parent, which cannot make it an interesting
   octopus by definition.

   But an octopus may merge three variants and pick the result from
   one of the parents as a whole.  With the pre-filtering, no hunk
   from such a path is shown, even when the other two variants in
   "discarded" parents are not identical.

Yes, I meant that.

The original to refer to are two commits bf1c32bd (combine-diff:
update --cc "uninteresting hunks" logic., 2006-02-02) and fd4b1d21
(combine-diff: add safety check to --cc., 2006-02-02).

Especially, we need to pay close attention to the discussion that
germinated the current behaviour:

  http://thread.gmane.org/gmane.comp.version-control.git/15486/focus=15519

I recall that the "diff --cc" before that change was not discarding
uninteresting merges sufficiently and the two commits were a
deliberate attempt to reject what your series wants to show as
uninteresting hunks.  

Two suggestions.

 - This is primarily for 2/4, but can we make it more clear in the
   code that we do this "include more" change only on Octopus
   merges?  This change should not make any difference for two-way
   merges and I'd prefer to avoid extra processing of finding
   matching hunks and combining, only to discard the result.

 - Can you run "diff --cc" with and without your patches to the
   "merge from hell" commit mentioned in the original thread and see
   if we show more hunks with your patches, and make sure what are
   shown additionally looked really "interesting"?

The diffs:
older version (without my patch):
https://gist.githubusercontent.com/max630/70080d38e8e9951b58a4/raw/diffcc_old.txt
newer version:
https://gist.githubusercontent.com/max630/70080d38e8e9951b58a4/raw/diffcc_new.txt

The outcome is quite different, yes.

First, I can see that file removal/deletion are passed
without filtering, even if file was only added/deleted
compared to some parents and not changed compared to any, so
it's in some way "2 versions" diff which should not be
shown. This I think is something should be fixed in addition
to this series.

Other than that, all other changes look "interesting",
meaning they contain more than 2 versions. Sometimes it's not
easy to spot because a long hunk is almost inherited from
one parent with all others being the same, and only in
couple of lines there when they differ. But I always find
some difference.

It was also quite slow, 11 seconds compared to some 0.4.
But for 2-way merges speed did not change.



My exact case was that there was a change in one branch
which was overwritten during merge conflict resolution by
fully acepting the other branch - in a 2-parent merge. I
started looking for a way to visualize such cases. They
are not visible in usual diff, because they look same as
accepting change compared to the unchange branch. To
recognize them you should consider the mergebase. I googled
to your suggestion in [1], and prepared a trivial testcase
for such a merge - in contained a base commit, change in
both branches and children which fully repeat one of the
branches. But then I discovered that such merge is not shown
in "diff --cc" because of the path filtering. So here am I.

Actually I think this is the very true rule which I would
like to be used: if there is a parent which is changed
compared to the merge base and child commit differs from
that parent. Because this is where there had been a valuable
change, and it disappeared. Linus in [2] wrote that those
change was fixing the same problem and it's good that they
are not shown, by it my case there were fixing different
problems, they just happened to be in the same place, and
after merge the bug reappeared.

[1] http://thread.gmane.org/gmane.comp.version-control.git/191553/focus=191557
[2] http://thread.gmane.org/gmane.comp.version-control.git/15486/focus=15519

* for `diff --cc` 2 cases:
  * the path must be changed since at least 2 parents, which
    should have the path different. In other words, the child and its
    parents must contain at least 3 different versions of file.
    Non-existing in the commit path counts as one version.
  * All parents are the same, but child commit differs from them.
* for `diff -c`: the path must be changed since at least 1 parent.

Signed-off-by: Max Kirillov <redacted>
---
This what could be done to hide the added and removed files.
It also makes it work faster - diff --cc on the evil merge runs now 2.5 seconds
instead of 11 (or 0.4 without the series).

This also fails t4057, but I really don't see the logic of `diff -c`
othwerwise. It should show all changes, with trivial merges also, and it
is shown by long files in my t4059. But it uses same path filtering as
`diff --cc`, which is even more restrictive.
 combine-diff.c | 91 ++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 66 insertions(+), 25 deletions(-)

diff --git a/combine-diff.c b/combine-diff.c
index 2285c7c..f44032a 100644
--- a/combine-diff.c
+++ b/combine-diff.c

@@ -50,20 +50,49 @@ static void insert_path(struct combine_diff_path **pos, const char* path, int n,
 	*pos = p;
 }
 
-static int changed_parents(struct combine_diff_path *p, int n)
+static int path_not_interesting(struct combine_diff_path *p, int n,
+				struct diff_filespec *new_parent)
 {
 	int parent_idx;
-	int result = 0;
+	struct object_id first_parent;
+	int found_first = 0;
+	int found_same_parent = 0;
 
 	for (parent_idx = 0; parent_idx < n; parent_idx++) {
-		if (p->parent[parent_idx].status != ' ')
-			result++;
+		if (p->parent[parent_idx].status != ' ') {
+			if (found_first) {
+				if (hashcmp(p->parent[parent_idx].oid.hash, first_parent.hash)) {
+					/* found second different unique parent - non-trivial merge */
+					return 0;
+				}
+			} else {
+				found_first = 1;
+				hashcpy(first_parent.hash,
+					p->parent[parent_idx].oid.hash);
+			}
+		} else {
+			/* the new commit repeats some of parents */
+			found_same_parent = 1;
+		}
 	}
 
-	return result;
+	if (new_parent) {
+		if (hashcmp(p->oid.hash, new_parent->sha1)) {
+			if (!found_same_parent || hashcmp(first_parent.hash, new_parent->sha1)) {
+				return 0;
+			} else {
+				return 1;
+			}
+		} else {
+			found_same_parent = 1;
+		}
+	}
+
+	return found_same_parent;
 }
 
-static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
+static struct combine_diff_path *intersect_paths(
+	struct combine_diff_path *curr, int n, int num_parent, int dense)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;
 	struct combine_diff_path *p, **tail = &curr;

@@ -81,35 +110,46 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 
 		if (cmp < 0) {
 			/* p->path not in q->queue[] */
-			if (num_parent > 2 && 2 - changed_parents(p, n) <= num_parent - n - 1) {
-				/* still can get 2 changed parents */
+			if (dense &&
+			    n == num_parent - 1 &&
+			    path_not_interesting(p, n, NULL)) {
+				/* only 1 unique different parent
+				   not interesting change */
+				*tail = p->next;
+				free(p);
+			} else {
+				/* already has or still can get 2 changed parents */
 				hashcpy(p->parent[n].oid.hash, p->oid.hash);
 				p->parent[n].mode = p->mode;
 				p->parent[n].status = ' ';
 				tail = &p->next;
-			} else {
-				*tail = p->next;
-				free(p);
 			}
 			continue;
-		}
-
-		if (cmp > 0) {
+		} else if (cmp > 0) {
 			/* q->queue[i] not in p->path */
-			if (1 <= num_parent - n - 1) {
-				insert_path(tail, q->queue[i]->two->path, n, num_parent, q->queue[i]);
+			if (!dense || n < num_parent - 1) {
+				insert_path(tail, q->queue[i]->two->path,
+					    n, num_parent, q->queue[i]);
 				tail = &(*tail)->next;
 			}
 			i++;
 			continue;
-		}
+		} else {
+			if (dense &&
+			    n == num_parent - 1 &&
+			    path_not_interesting(p, n, q->queue[i]->one)) {
+				*tail = p->next;
+				free(p);
+			} else {
+				hashcpy(p->parent[n].oid.hash, q->queue[i]->one->sha1);
+				p->parent[n].mode = q->queue[i]->one->mode;
+				p->parent[n].status = q->queue[i]->status;
 
-		hashcpy(p->parent[n].oid.hash, q->queue[i]->one->sha1);
-		p->parent[n].mode = q->queue[i]->one->mode;
-		p->parent[n].status = q->queue[i]->status;
+				tail = &p->next;
+			}
+			i++;
+		}
 
-		tail = &p->next;
-		i++;
 	}
 	return curr;
 }

@@ -1341,7 +1381,8 @@ static const char *path_path(void *obj)
 
 /* find set of paths that every parent touches */
 static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,
-	const struct sha1_array *parents, struct diff_options *opt)
+	const struct sha1_array *parents, struct diff_options *opt,
+	int dense)
 {
 	struct combine_diff_path *paths = NULL;
 	int i, num_parent = parents->nr;

@@ -1367,7 +1408,7 @@ static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,
 			opt->output_format = DIFF_FORMAT_NO_OUTPUT;
 		diff_tree_sha1(parents->sha1[i], sha1, "", opt);
 		diffcore_std(opt);
-		paths = intersect_paths(paths, i, num_parent);
+		paths = intersect_paths(paths, i, num_parent, dense);
 
 		/* if showing diff, show it in requested order */
 		if (opt->output_format != DIFF_FORMAT_NO_OUTPUT &&

@@ -1477,7 +1518,7 @@ void diff_tree_combined(const unsigned char *sha1,
 		 * diff(sha1,parent_i) for all i to do the job, specifically
 		 * for parent0.
 		 */
-		paths = find_paths_generic(sha1, parents, &diffopts);
+		paths = find_paths_generic(sha1, parents, &diffopts, dense);
 	}
 	else {
 		int stat_opt;

-- 
2.3.4.2801.g3d0809b