[PATCH] apply: fix delete-then-new patch fail with 3way

For one single patch FILE containing both deletion and creation
of the same file, applying with three way would fail, which should not.

When git-apply processes one single patch FILE, patches inside it
would be applied before write_out_results(), thus it may occur
that one file being deleted but it is still in the index when
applying a new patch, in this case, try_threeway() would find
an old file thus causing merge conflict.

To avoid this, git-apply should fall back to directly apply
when it turns out to be such cases.

Signed-off-by: Hongren (Zenithal) Zheng <i@zenithal.me>
---
 apply.c                   | 13 ++++++++++++-
 t/t4108-apply-threeway.sh | 20 ++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)

More notes below:

This patch is a bugfix hence it is based on branch `maint`.

This bug is caused by a behavior change since 2.32 where
git apply --3way would try 3-way first before directly apply.

Interestingly, if the deletion patch and the addition patch are in
two patch files, applying with three way would go on cleanly.

As indicated in commit msg, if these two patches are in different
patch files, write_out_results() would be called twice, unlike when
they are in the same file, write_out_results() would be called altogether
after all patches being applied.

One way to fix this is to check for this kind of conditions, which
is presented in this patch.

A side note though, this kind of checks and fixes already exist
as indicated by variable ok_if_exists in function check_patch().
See the comment around this variable for more info.

This kind of fixes is really dark magic.

Another way, which I do not adopt because it requires major refactor
but it is more clean and understandable, is to change the way
write_out_resultes() is called, namely instead of calling it
after all patches being applied in one patch FILE, after each patch
being applied, we write_out_result immediately thus deleting one file
would immediately delete the file from the index.

The man page of `patch` says: If the patch file contains more than
one patch, patch tries to apply each of them as if they came
from separate patch files. So I think this way is more standardized.

However, as also indicated by comments around variable
ok_if_exists in function check_patch(), consequtive patches in one
file have special meanings as endowed by diff.c::run_diff()

I do not know how to handle this, so I just send it as notes.

More comment: this problem or this kind of fix may be related to 
https://lore.kernel.org/git/YR1OszUm08BMAE1N@host1.jankratochvil.net/

diff --git a/apply.c b/apply.c
index 44bc31d6eb5b42d4077eff458246cde376cb6785..3fa96fcc781bdc27f66a35442f27972a0e84ea77 100644
--- a/apply.c
+++ b/apply.c

@@ -3558,8 +3558,19 @@ static int try_threeway(struct apply_state *state,
 	char *img;
 	struct image tmp_image;
 
-	/* No point falling back to 3-way merge in these cases */
+	/*
+	 * No point using 3-way merge in these cases
+	 *
+	 * For patch->is_new, if new_name does not exist in the index,
+	 * we can directly apply; if new_name exists,
+	 * according to ok_if_exists in check_patch(),
+	 * there are cases where new_name gets deleted in previous patches
+	 * BUT still exists in index, in this case, we can directly apply.
+	 */
 	if (patch->is_delete ||
+	      (patch->is_new &&
+	       (index_name_pos(state->repo->index, patch->new_name, strlen(patch->new_name)) < 0 ||
+		was_deleted(in_fn_table(state, patch->new_name)))) ||
 	    S_ISGITLINK(patch->old_mode) || S_ISGITLINK(patch->new_mode))
 		return -1;
 

diff --git a/t/t4108-apply-threeway.sh b/t/t4108-apply-threeway.sh
index 65147efdea9a00e30d156e6f4d5d72a3987f230d..14bbb393430ed57a236d25aa568a0fdc6d221a6d 100755
--- a/t/t4108-apply-threeway.sh
+++ b/t/t4108-apply-threeway.sh

@@ -230,4 +230,24 @@ test_expect_success 'apply with --3way --cached and conflicts' '
 	test_cmp expect.diff actual.diff
 '
 
+test_expect_success 'apply delete then new patch with 3way' '
+	git reset --hard main &&
+	test_write_lines 1 > delnew &&
+	git add delnew &&
+	git commit -m "delnew" &&
+	cat >delete-then-new.patch <<-\EOF &&
+	--- a/delnew
+	+++ /dev/null
+	@@ -1 +0,0 @@
+	-1
+	--- /dev/null
+	+++ b/delnew
+	@@ -0,0 +1 @@
+	+2
+	EOF
+
+	# Apply must succeed.
+	git apply --3way delete-then-new.patch
+'
+
 test_done

-- 
2.32.0

On Sun, Oct 03, 2021 at 07:25:29PM +0800, Hongren (Zenithal) Zheng wrote:

Is there any updates regarding this patch?

"Hongren (Zenithal) Zheng" [off-list ref] writes:

On Sun, Oct 03, 2021 at 07:25:29PM +0800, Hongren (Zenithal) Zheng wrote:

quoted

For one single patch FILE containing both deletion and creation
of the same file, applying with three way would fail, which should not.
 ...

Sigh.

Jerry, it seems that the earlier "let's be more aggressive to use
--3way, instead of using it as a fallback" is turning out to be more
and more trouble than we hoped.

One thing to notice about the patch used for this test is that ...

quoted

+test_expect_success 'apply delete then new patch with 3way' '
+	git reset --hard main &&
+	test_write_lines 1 > delnew &&
+	git add delnew &&
+	git commit -m "delnew" &&
+	cat >delete-then-new.patch <<-\EOF &&
+	--- a/delnew
+	+++ /dev/null
+	@@ -1 +0,0 @@
+	-1
+	--- /dev/null
+	+++ b/delnew
+	@@ -0,0 +1 @@
+	+2
+	EOF

... this is clearly not a patch that was generated by Git.  We do
not show two separate patches, to delete and then to create, the
same path to express a file modification, and that is true even when
we are showing a total-rewrite patch.

In addition, the above set of two patches lack the "index" header
that records the old and new blob object name, because it is not a
patch generated by Git.  Whether 3-way is attempted before or after
the normal application, because the object names there are a crucial
ingredient for the 3-way merge logic, there is no way for it to work
at all.

quoted

+	# Apply must succeed.
+	git apply --3way delete-then-new.patch

So, one simple and safe answer would be "Don't do it, --3way is only
about Git patches."  IOW, the command is failing as designed.

To extend and automate the solution would be to see, just before
attempting to do the 3-way, if the incoming patch is a Git generated
one, and do not even bother using the 3-way logic if it is not.

On Sat, Oct 16, 2021 at 11:08 PM Junio C Hamano [off-list ref] wrote:

"Hongren (Zenithal) Zheng" [off-list ref] writes:

quoted

On Sun, Oct 03, 2021 at 07:25:29PM +0800, Hongren (Zenithal) Zheng wrote:

quoted

For one single patch FILE containing both deletion and creation
of the same file, applying with three way would fail, which should not.
 ...

Sigh.

Jerry, it seems that the earlier "let's be more aggressive to use
--3way, instead of using it as a fallback" is turning out to be more
and more trouble than we hoped.

One thing to notice about the patch used for this test is that ...

quoted

quoted

+test_expect_success 'apply delete then new patch with 3way' '
+    git reset --hard main &&
+    test_write_lines 1 > delnew &&
+    git add delnew &&
+    git commit -m "delnew" &&
+    cat >delete-then-new.patch <<-\EOF &&
+    --- a/delnew
+    +++ /dev/null
+    @@ -1 +0,0 @@
+    -1
+    --- /dev/null
+    +++ b/delnew
+    @@ -0,0 +1 @@
+    +2
+    EOF

... this is clearly not a patch that was generated by Git.  We do
not show two separate patches, to delete and then to create, the
same path to express a file modification, and that is true even when
we are showing a total-rewrite patch.

In addition, the above set of two patches lack the "index" header
that records the old and new blob object name, because it is not a
patch generated by Git.  Whether 3-way is attempted before or after
the normal application, because the object names there are a crucial
ingredient for the 3-way merge logic, there is no way for it to work
at all.

quoted

quoted

+    # Apply must succeed.
+    git apply --3way delete-then-new.patch

So, one simple and safe answer would be "Don't do it, --3way is only
about Git patches."  IOW, the command is failing as designed.

Yeah I do wonder why one would specify "--3way" when the behavior that
they want is actually "direct application". Maybe the OP can elaborate on their
use case?

Part of my original assumption was that "--3way" users actually *want* 3way,
and thus the behavior change wouldn't be too controversial. Of course since
git has so many users, it shouldn't be that surprising that there are many use
patterns out there.

One possible fix-all solution would just be to back out the original change and
move the behavior into a new flag "--actually-3way" (name tbd) that will apply
this behavior and "--3way" would keep the old behavior. The downside here
would be proliferating more flags that would complicate the api and require
maintenance. And of course if users depended on the *new* behavior in the
meantime, then we'd be stuck.

Back to the patch at hand, it does seem like it would work, however I
notice that
if a modification patch were added to the end of the file such that it were
deleted -> add -> modify, that modify wouldn't benefit from actually
doing a 3way
since the file would not be in the index due to this short-cut. The
more general approach
of refactoring to write out results after each patch instead of at the
end *would* fix
both things. I guess this goes back to the larger issue of the
threeway implementation
not being well suited to non-git patches.

To extend and automate the solution would be to see, just before
attempting to do the 3-way, if the incoming patch is a Git generated
one, and do not even bother using the 3-way logic if it is not.

On Tue, Oct 19, 2021 at 11:56:11AM -0700, Jerry Zhang wrote:

On Sat, Oct 16, 2021 at 11:08 PM Junio C Hamano [off-list ref] wrote:

quoted

"Hongren (Zenithal) Zheng" [off-list ref] writes:

quoted

On Sun, Oct 03, 2021 at 07:25:29PM +0800, Hongren (Zenithal) Zheng wrote:

quoted

For one single patch FILE containing both deletion and creation
of the same file, applying with three way would fail, which should not.
 ...

Sigh.

Jerry, it seems that the earlier "let's be more aggressive to use
--3way, instead of using it as a fallback" is turning out to be more
and more trouble than we hoped.

One thing to notice about the patch used for this test is that ...

quoted

quoted

+test_expect_success 'apply delete then new patch with 3way' '
+    git reset --hard main &&
+    test_write_lines 1 > delnew &&
+    git add delnew &&
+    git commit -m "delnew" &&
+    cat >delete-then-new.patch <<-\EOF &&
+    --- a/delnew
+    +++ /dev/null
+    @@ -1 +0,0 @@
+    -1
+    --- /dev/null
+    +++ b/delnew
+    @@ -0,0 +1 @@
+    +2
+    EOF

... this is clearly not a patch that was generated by Git.  We do
not show two separate patches, to delete and then to create, the
same path to express a file modification, and that is true even when
we are showing a total-rewrite patch.

I'm aware of such process. This patch is generated by manually concatenating
two patches together.

Why should I concat patches, you may ask. Well, there are cases where
I have to distribute a patch series containing dozens of patches (like
packaging for a Linux distribution), instead of multiple files, one
file would be convenient. Also, since the patch series may be out-of-date as
the upstream repo progresses, git apply -3 would be better.

Despite the above example. Placing patches inside one file or not should
not affect the result of git apply -3

Refer to the man page of patch

From my first post:

quoted

quoted

quoted

The man page of `patch` says: If the patch file contains more than
one patch, patch tries to apply each of them as if they came
from separate patch files. So I think this way is more standardized.

quoted

In addition, the above set of two patches lack the "index" header
that records the old and new blob object name, because it is not a
patch generated by Git.  Whether 3-way is attempted before or after
the normal application, because the object names there are a crucial
ingredient for the 3-way merge logic, there is no way for it to work
at all.

It is my fault that for simplicity, I did not use a way to generate
patches with an "index" header in it. Below is the procedure to
reproduce this "bug" (I still call it "bug") even with index in it.

mkdir delete-then-new
pushd delete-then-new
git init
echo 1 > a
git add a
git commit -m "init"
git rm a
git commit -m "delete"
echo 2 > a
git add a
git commit -m "new"
git format-patch --full-index -o ../ HEAD~2
git checkout HEAD~2
cat ../0001-delete.patch ../0002-new.patch > ../delete-then-new.patch
git apply -3 ../delete-then-new.patch # it would fail

quoted

quoted

quoted

+    # Apply must succeed.
+    git apply --3way delete-then-new.patch

So, one simple and safe answer would be "Don't do it, --3way is only
about Git patches."  IOW, the command is failing as designed.

Yeah I do wonder why one would specify "--3way" when the behavior that
they want is actually "direct application". Maybe the OP can elaborate on their
use case?

I have mentioned the specific 3way usage in the above case.

Part of my original assumption was that "--3way" users actually *want* 3way,
and thus the behavior change wouldn't be too controversial. Of course since
git has so many users, it shouldn't be that surprising that there are many use
patterns out there.

I do want 3way, but there are cases where 3way would not work,
like when 3way patches and direct patches (e.g. delete/new, mode change)
are mixed together in one patch file.

I think we should enumerate all cases where threeway should be avoided
and we should fallback to directly applying. From my inspection of the
code, it seems that it is not sufficient now.

One possible fix-all solution would just be to back out the original change and
move the behavior into a new flag "--actually-3way" (name tbd) that will apply
this behavior and "--3way" would keep the old behavior. The downside here
would be proliferating more flags that would complicate the api and require
maintenance. And of course if users depended on the *new* behavior in the
meantime, then we'd be stuck.

Back to the patch at hand, it does seem like it would work, however I
notice that
if a modification patch were added to the end of the file such that it were
deleted -> add -> modify, that modify wouldn't benefit from actually
doing a 3way
since the file would not be in the index due to this short-cut. The
more general approach
of refactoring to write out results after each patch instead of at the
end *would* fix
both things. I guess this goes back to the larger issue of the
threeway implementation
not being well suited to non-git patches.

Yes, the problem comes from the short-cut, and I have mentioned that
we should write out results immediately instead of at the end.

From my first post:

quoted

quoted

quoted

Another way, which I do not adopt because it requires major refactor
but it is more clean and understandable, is to change the way
write_out_resultes() is called, namely instead of calling it
after all patches being applied in one patch FILE, after each patch
being applied, we write_out_result immediately thus deleting one file
would immediately delete the file from the index.

quoted

To extend and automate the solution would be to see, just before
attempting to do the 3-way, if the incoming patch is a Git generated
one, and do not even bother using the 3-way logic if it is not.

Concating two git-generated patches together would fool this mechanism, I
suppose. So the above "bug" still exists.

On Thu, Nov 4, 2021 at 4:16 AM Hongren (Zenithal) Zheng [off-list ref] wrote:

On Tue, Oct 19, 2021 at 11:56:11AM -0700, Jerry Zhang wrote:

quoted

On Sat, Oct 16, 2021 at 11:08 PM Junio C Hamano [off-list ref] wrote:

quoted

"Hongren (Zenithal) Zheng" [off-list ref] writes:

quoted

On Sun, Oct 03, 2021 at 07:25:29PM +0800, Hongren (Zenithal) Zheng wrote:

quoted

For one single patch FILE containing both deletion and creation
of the same file, applying with three way would fail, which should not.
 ...

Sigh.

Jerry, it seems that the earlier "let's be more aggressive to use
--3way, instead of using it as a fallback" is turning out to be more
and more trouble than we hoped.

One thing to notice about the patch used for this test is that ...

quoted

quoted

+test_expect_success 'apply delete then new patch with 3way' '
+    git reset --hard main &&
+    test_write_lines 1 > delnew &&
+    git add delnew &&
+    git commit -m "delnew" &&
+    cat >delete-then-new.patch <<-\EOF &&
+    --- a/delnew
+    +++ /dev/null
+    @@ -1 +0,0 @@
+    -1
+    --- /dev/null
+    +++ b/delnew
+    @@ -0,0 +1 @@
+    +2
+    EOF

... this is clearly not a patch that was generated by Git.  We do
not show two separate patches, to delete and then to create, the
same path to express a file modification, and that is true even when
we are showing a total-rewrite patch.

I'm aware of such process. This patch is generated by manually concatenating
two patches together.

Why should I concat patches, you may ask. Well, there are cases where
I have to distribute a patch series containing dozens of patches (like
packaging for a Linux distribution), instead of multiple files, one
file would be convenient. Also, since the patch series may be out-of-date as
the upstream repo progresses, git apply -3 would be better.

Despite the above example. Placing patches inside one file or not should
not affect the result of git apply -3

Refer to the man page of patch

From my first post:

quoted

quoted

quoted

quoted

The man page of `patch` says: If the patch file contains more than
one patch, patch tries to apply each of them as if they came
from separate patch files. So I think this way is more standardized.

quoted

quoted

In addition, the above set of two patches lack the "index" header
that records the old and new blob object name, because it is not a
patch generated by Git.  Whether 3-way is attempted before or after
the normal application, because the object names there are a crucial
ingredient for the 3-way merge logic, there is no way for it to work
at all.

It is my fault that for simplicity, I did not use a way to generate
patches with an "index" header in it. Below is the procedure to
reproduce this "bug" (I still call it "bug") even with index in it.

mkdir delete-then-new
pushd delete-then-new
git init
echo 1 > a
git add a
git commit -m "init"
git rm a
git commit -m "delete"
echo 2 > a
git add a
git commit -m "new"
git format-patch --full-index -o ../ HEAD~2
git checkout HEAD~2
cat ../0001-delete.patch ../0002-new.patch > ../delete-then-new.patch
git apply -3 ../delete-then-new.patch # it would fail

quoted

quoted

quoted

quoted

+    # Apply must succeed.
+    git apply --3way delete-then-new.patch

So, one simple and safe answer would be "Don't do it, --3way is only
about Git patches."  IOW, the command is failing as designed.

Yeah I do wonder why one would specify "--3way" when the behavior that
they want is actually "direct application". Maybe the OP can elaborate on their
use case?

I have mentioned the specific 3way usage in the above case.

quoted

Part of my original assumption was that "--3way" users actually *want* 3way,
and thus the behavior change wouldn't be too controversial. Of course since
git has so many users, it shouldn't be that surprising that there are many use
patterns out there.

I do want 3way, but there are cases where 3way would not work,
like when 3way patches and direct patches (e.g. delete/new, mode change)
are mixed together in one patch file.

I think we should enumerate all cases where threeway should be avoided
and we should fallback to directly applying. From my inspection of the
code, it seems that it is not sufficient now.

quoted

One possible fix-all solution would just be to back out the original change and
move the behavior into a new flag "--actually-3way" (name tbd) that will apply
this behavior and "--3way" would keep the old behavior. The downside here
would be proliferating more flags that would complicate the api and require
maintenance. And of course if users depended on the *new* behavior in the
meantime, then we'd be stuck.

Back to the patch at hand, it does seem like it would work, however I
notice that
if a modification patch were added to the end of the file such that it were
deleted -> add -> modify, that modify wouldn't benefit from actually
doing a 3way
since the file would not be in the index due to this short-cut. The
more general approach
of refactoring to write out results after each patch instead of at the
end *would* fix
both things. I guess this goes back to the larger issue of the
threeway implementation
not being well suited to non-git patches.

Yes, the problem comes from the short-cut, and I have mentioned that
we should write out results immediately instead of at the end.

From my first post:

quoted

quoted

quoted

quoted

Another way, which I do not adopt because it requires major refactor
but it is more clean and understandable, is to change the way
write_out_resultes() is called, namely instead of calling it
after all patches being applied in one patch FILE, after each patch
being applied, we write_out_result immediately thus deleting one file
would immediately delete the file from the index.

quoted

quoted

To extend and automate the solution would be to see, just before
attempting to do the 3-way, if the incoming patch is a Git generated
one, and do not even bother using the 3-way logic if it is not.

Concating two git-generated patches together would fool this mechanism, I
suppose. So the above "bug" still exists.

I was testing this issue and I found that one of my other patches,
"git-apply: silence errors for success cases", happens to fix your reported
issue a bit more generally / cleanly by avoiding 3way for all new patches
without an add conflict. Let me add you to that thread and ping for more
review.