[PATCH] merge-ort: fix bug with renormalization and rename/delete conflicts

[PATCH] merge-ort: fix bug with renormalization and rename/delete conflicts

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Ever since commit a492d5331c ("merge-ort: ensure we consult df_conflict
and path_conflicts", 2021-06-30), when renormalization is active AND a
file is involved in a rename/delete conflict BUT the file is unmodified
(either before or after renormalization), merge-ort was running into an
assertion failure.  Prior to that commit (or if assertions were compiled
out), merge-ort would mis-merge instead, ignoring the rename/delete
conflict and just deleting the file.

Remove the assertions, fix the code appropriately, leave some good
comments in the code, and add a testcase for this situation.

Reported-by: Ralf Thielow <ralf.thielow@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
    merge-ort: fix bug with renormalization and rename/delete conflicts
    
    Original report:
    https://lore.kernel.org/git/CAN0XMOK8iHZnbtYw7CPAQGJcmuVSDxQoFNFEwiaa41V89F1rzA@mail.gmail.com/
    
    Built in v2.34.1, but rebases onto and/or merges cleanly with newer
    versions.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1174%2Fnewren%2Fmerge-ort-rename-delete-renormalization-bug-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1174/newren/merge-ort-rename-delete-renormalization-bug-v1
Pull-Request: https://github.com/git/git/pull/1174

 merge-ort.c                | 19 ++++++++++++++++---
 t/t6418-merge-text-auto.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 3 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 0342f104836..c3197970219 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3841,9 +3841,22 @@ static void process_entry(struct merge_options *opt,
 		if (opt->renormalize &&
 		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
 				   path)) {
-			ci->merged.is_null = 1;
-			ci->merged.clean = 1;
-			assert(!ci->df_conflict && !ci->path_conflict);
+			if (!ci->path_conflict) {
+				/*
+				 * Blob unchanged after renormalization, so
+				 * there's no modify/delete conflict after all;
+				 * we can just remove the file.
+				 */
+				ci->merged.is_null = 1;
+				ci->merged.clean = 1;
+				 /*
+				  * file goes away => even if there was a
+				  * directory/file conflict there isn't one now.
+				  */
+				ci->df_conflict = 0;
+			} else {
+				/* rename/delete, so conflict remains */
+			}
 		} else if (ci->path_conflict &&
 			   oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
 			/*
diff --git a/t/t6418-merge-text-auto.sh b/t/t6418-merge-text-auto.sh
index 1e0296dd172..41288a60ceb 100755
--- a/t/t6418-merge-text-auto.sh
+++ b/t/t6418-merge-text-auto.sh
@@ -204,4 +204,30 @@ test_expect_success 'Test delete/normalize conflict' '
 	test_path_is_missing file
 '
 
+test_expect_success 'rename/delete vs. renormalization' '
+	git init subrepo &&
+	(
+		cd subrepo &&
+		echo foo >oldfile &&
+		git add oldfile &&
+		git commit -m original &&
+
+		git branch rename &&
+		git branch nuke &&
+
+		git checkout rename &&
+		git mv oldfile newfile &&
+		git commit -m renamed &&
+
+		git checkout nuke &&
+		git rm oldfile &&
+		git commit -m deleted &&
+
+		git checkout rename^0 &&
+		test_must_fail git -c merge.renormalize=true merge nuke >out &&
+
+		grep "rename/delete" out
+	)
+'
+
 test_done

base-commit: e9d7761bb94f20acc98824275e317fa82436c25d
-- 
gitgitgadget

Re: [PATCH] merge-ort: fix bug with renormalization and rename/delete conflicts

[Derrick Stolee]

On 12/27/2021 7:20 PM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> Ever since commit a492d5331c ("merge-ort: ensure we consult df_conflict
> and path_conflicts", 2021-06-30), when renormalization is active AND a
> file is involved in a rename/delete conflict BUT the file is unmodified
> (either before or after renormalization), merge-ort was running into an
> assertion failure. 

This "the file is unmodified" is critical, as when I looked at the test,
it seemed too simple. I asked myself, "Why does renormalization matter
here?" Turns out it is just an artifact of the carefully organized cases.

>  		if (opt->renormalize &&
>  		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
>  				   path)) {
> -			ci->merged.is_null = 1;
> -			ci->merged.clean = 1;
> -			assert(!ci->df_conflict && !ci->path_conflict);
> +			if (!ci->path_conflict) {
> +				/*
> +				 * Blob unchanged after renormalization, so
> +				 * there's no modify/delete conflict after all;
> +				 * we can just remove the file.
> +				 */
> +				ci->merged.is_null = 1;
> +				ci->merged.clean = 1;
> +				 /*
> +				  * file goes away => even if there was a
> +				  * directory/file conflict there isn't one now.
> +				  */
> +				ci->df_conflict = 0;
> +			} else {
> +				/* rename/delete, so conflict remains */
> +			}

This breakdown of the cases is informative, and I like how self-contained
the change is.

> +test_expect_success 'rename/delete vs. renormalization' '
> +	git init subrepo &&
> +	(
> +		cd subrepo &&
> +		echo foo >oldfile &&
> +		git add oldfile &&
> +		git commit -m original &&
> +
> +		git branch rename &&
> +		git branch nuke &&
> +
> +		git checkout rename &&
> +		git mv oldfile newfile &&
> +		git commit -m renamed &&
> +
> +		git checkout nuke &&
> +		git rm oldfile &&
> +		git commit -m deleted &&
> +
> +		git checkout rename^0 &&
> +		test_must_fail git -c merge.renormalize=true merge nuke >out &&
> +
> +		grep "rename/delete" out
> +	)
> +'
> +
>  test_done

I tested this on the latest 'master' and saw the following:

  git: merge-ort.c:3846: process_entry: Assertion `!ci->df_conflict && !ci->path_conflict' failed

so it indeed hits this case.

This patch looks good to me. Thanks!

Reviewed-by: Derrick Stolee <dstolee@microsoft.com>

[PATCH v2] merge-ort: fix bug with renormalization and rename/delete conflicts

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Ever since commit a492d5331c ("merge-ort: ensure we consult df_conflict
and path_conflicts", 2021-06-30), when renormalization is active AND a
file is involved in a rename/delete conflict BUT the file is unmodified
(either before or after renormalization), merge-ort was running into an
assertion failure.  Prior to that commit (or if assertions were compiled
out), merge-ort would mis-merge instead, ignoring the rename/delete
conflict and just deleting the file.

Remove the assertions, fix the code appropriately, leave some good
comments in the code, and add a testcase for this situation.

Reported-by: Ralf Thielow <ralf.thielow@gmail.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
    merge-ort: fix bug with renormalization and rename/delete conflicts
    
    Original report:
    https://lore.kernel.org/git/CAN0XMOK8iHZnbtYw7CPAQGJcmuVSDxQoFNFEwiaa41V89F1rzA@mail.gmail.com/
    
    Built in v2.34.1, but rebases onto and/or merges cleanly with newer
    versions.
    
    Changes since v1:
    
     * Added Stolee's Reviewed-by

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1174%2Fnewren%2Fmerge-ort-rename-delete-renormalization-bug-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1174/newren/merge-ort-rename-delete-renormalization-bug-v2
Pull-Request: https://github.com/git/git/pull/1174

Range-diff vs v1:

 1:  5841f3d901d ! 1:  72876b9c106 merge-ort: fix bug with renormalization and rename/delete conflicts
     @@ Commit message
          comments in the code, and add a testcase for this situation.
      
          Reported-by: Ralf Thielow <ralf.thielow@gmail.com>
     +    Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## merge-ort.c ##


 merge-ort.c                | 19 ++++++++++++++++---
 t/t6418-merge-text-auto.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 3 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 0342f104836..c3197970219 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3841,9 +3841,22 @@ static void process_entry(struct merge_options *opt,
 		if (opt->renormalize &&
 		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
 				   path)) {
-			ci->merged.is_null = 1;
-			ci->merged.clean = 1;
-			assert(!ci->df_conflict && !ci->path_conflict);
+			if (!ci->path_conflict) {
+				/*
+				 * Blob unchanged after renormalization, so
+				 * there's no modify/delete conflict after all;
+				 * we can just remove the file.
+				 */
+				ci->merged.is_null = 1;
+				ci->merged.clean = 1;
+				 /*
+				  * file goes away => even if there was a
+				  * directory/file conflict there isn't one now.
+				  */
+				ci->df_conflict = 0;
+			} else {
+				/* rename/delete, so conflict remains */
+			}
 		} else if (ci->path_conflict &&
 			   oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
 			/*
diff --git a/t/t6418-merge-text-auto.sh b/t/t6418-merge-text-auto.sh
index 1e0296dd172..41288a60ceb 100755
--- a/t/t6418-merge-text-auto.sh
+++ b/t/t6418-merge-text-auto.sh
@@ -204,4 +204,30 @@ test_expect_success 'Test delete/normalize conflict' '
 	test_path_is_missing file
 '
 
+test_expect_success 'rename/delete vs. renormalization' '
+	git init subrepo &&
+	(
+		cd subrepo &&
+		echo foo >oldfile &&
+		git add oldfile &&
+		git commit -m original &&
+
+		git branch rename &&
+		git branch nuke &&
+
+		git checkout rename &&
+		git mv oldfile newfile &&
+		git commit -m renamed &&
+
+		git checkout nuke &&
+		git rm oldfile &&
+		git commit -m deleted &&
+
+		git checkout rename^0 &&
+		test_must_fail git -c merge.renormalize=true merge nuke >out &&
+
+		grep "rename/delete" out
+	)
+'
+
 test_done

base-commit: e9d7761bb94f20acc98824275e317fa82436c25d
-- 
gitgitgadget

Re: [PATCH] merge-ort: fix bug with renormalization and rename/delete conflicts

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> This breakdown of the cases is informative, and I like how self-contained
> the change is.
>  ....
>
> This patch looks good to me. Thanks!
>
> Reviewed-by: Derrick Stolee <dstolee@microsoft.com>

Thanks, both.

A related tangent, but I was looking at the data structure involved
and noticed that the casting between structure types "merged_info"
and "conflict_info" looked a bit ugly.  It might be worth cleaning
them up into 

 (A) a union with two struct, with "clean" member in the union to
     switch between the two structures; or

 (B) a single structure that looks like "conflict_info" but inlines
     members of "merged_info" into it.

The latter may be cleaner and simpler, and the unified data type
would be the "merge info", which may be representing cleanly merged
path, or conflicted path, and would justify conditional use of some
members based on the value of the .clean member.

Re: [PATCH] merge-ort: fix bug with renormalization and rename/delete conflicts

[Elijah Newren]

On Thu, Dec 30, 2021 at 2:56 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> Derrick Stolee <stolee@gmail.com> writes:
>
> > This breakdown of the cases is informative, and I like how self-contained
> > the change is.
> >  ....
> >
> > This patch looks good to me. Thanks!
> >
> > Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
>
> Thanks, both.
>
> A related tangent, but I was looking at the data structure involved
> and noticed that the casting between structure types "merged_info"
> and "conflict_info" looked a bit ugly.

Yes, that's true.

> It might be worth cleaning them up into
>
>  (A) a union with two struct, with "clean" member in the union to
>      switch between the two structures; or
>
>  (B) a single structure that looks like "conflict_info" but inlines
>      members of "merged_info" into it.
>
> The latter may be cleaner and simpler, and the unified data type
> would be the "merge info", which may be representing cleanly merged
> path, or conflicted path, and would justify conditional use of some
> members based on the value of the .clean member.

These are heavily used data structures.  Note that:
  sizeof(struct conflict_info) = 216
  sizeof(struct merged_info) = 64
In particular, we have to allocate one or the other of these for every
path (both file and directory) involved in the merge.  Since the
former is 3.375 times bigger than the latter, and the vast majority of
paths involved in a merge usually do not conflict (think of files only
changed on one side), using just one combined struct would require
more than 3x the amount of memory.  So I'd rather avoid (B).

(A) may work, but I'd still have to allocate merged_info instead of
the union type to avoid the memory increase.  And since we have an
amount of memory allocated that is smaller than the union, when
accessing it via the union, Stolee would probably still want all the
same casting safeguards (as a safety check to avoid out-of-bounds
accesses) that I think you're complaining about.