builtin-apply: keep information about files to be deleted

Example correct diff generated by `diff -M -B' might look like this:

diff --git a/file1 b/file2
similarity index 100%
rename from file1
rename to file2
diff --git a/file2 b/file1
similarity index 100%
rename from file2
rename to file1

Information about removing file2' comes after information about creation of new file2' (renamed from `file1'). Existing implementation isn't able to apply such patch, because it has to know in advance which files will be removed.

This patch populates fn_table with information about removal of files before calling check_patch() for each patch to be applied.

Signed-off-by Michał Kiedrowicz <[email protected]>

builtin-apply.c +0 -0

index 1926cd8..6f6bf85 100644
@@ -2271,6 +2271,16 @@ static struct patch *in_fn_table(const char *name)
 	return NULL;
 }

builtin-apply.c +4 -0

@@ -2295,6 +2305,24 @@ static void add_to_fn_table(struct patch *patch)
...
+static void prepare_fn_table(struct patch *patch)
+{
+	/*
+	 * store information about incoming file deletion

This PATH_TO_BE_DELETED logic should be Ok for the normal case, but it seems a bit fragile. In a sequence of patches, if you have even one patch that makes the path disappear, you initialize it as PATH_TO_BE_DELETED, and special case the "creation should not clobber existing path" rule to allow it to be present in the tree.

That may make this sequence work, I presume, with your change:

patch #1 renames frotz.c to hello.c
patch #2 renames hello.c to frotz.c

because of patch #2, hello.c is marked as PATH_TO_BE_DELETED initially and then when patch #1 is handled, frotz.c is allowed to replace it.

But if you have further patches that do the following (the "file table" mechanism was added to handle concatenated patches that affect the same path more than once), I thing PATH_TO_BE_DELETED logic would break down:

patch #3 renames alpha.c to hello.c
patch #4 renames hello.c to alpha.c

When patch #3 is handled, the PATH_TO_BE_DELETED mark is long gone from hello.c, and we will see the same failure you addressed in your patch, won't we?

The prepare_fn_table() may be a good place to diagnose such a situation and warn or error out if the user feeds such an input we cannot handle sanely.

Style;

	if (to_be_deleted(tpatch))
        	tpatch = NULL;

Other than that, I think it is a sensible approach.

Junio C Hamano <[email protected]> wrote:
...

Quoted 8 lines

But if you have further patches that do the following (the "file table" mechanism was added to handle concatenated patches that affect the same path more than once), I thing PATH_TO_BE_DELETED logic would break down:

patch #3 renames alpha.c to hello.c
patch #4 renames hello.c to alpha.c

Quoted 3 lines

When patch #3 is handled, the PATH_TO_BE_DELETED mark is long gone from hello.c, and we will see the same failure you addressed in your patch, won't we?

As far as I understand the code, diffs are applied independently (for every file apply_patch() is called) and for every apply_patch() call fn_table is cleared. So situation you described in only possible in a *single* diff and I don't think it is possible to happen.

Quoted 7 lines

As far as I understand the code, diffs are applied independently (for every file apply_patch() is called) and for every apply_patch() call fn_table is cleared. So situation you described in only possible in a *single* diff and I don't think it is possible to happen.

Yes, one invocation of "git format-patch -1" will not produce such a situation.

A single diff file that is concatenation of two "git format-patch -1" output (or just a plain-old "diff -ru" output from outside git, perhaps managed in quilt) was what introduced fn_table mechanism. Apparently people use "git apply" to apply such a patch.

... However, there are some cases when these two
rules may cause problems:

patch #1: rename A to B
patch #2: rename C to A
patch #3: modify A

Should patch #3 modify B (which was A) or A (which was C)?

patch #1: rename A to B
patch #2: rename B to A
patch #3: modify A
patch #4: modify B

Which files should be patched by #3 and #4?

In my opinion both #3 and #4 should fail (or both should succeed) -- with my patch only #3 will work and #4 will be rejected, because in #2 B was marked as deleted.

Quoted 14 lines · Michał Kiedrowicz

... However, there are some cases when these two
rules may cause problems:

patch #1: rename A to B
patch #2: rename C to A
patch #3: modify A

Should patch #3 modify B (which was A) or A (which was C)?

patch #1: rename A to B
patch #2: rename B to A
patch #3: modify A
patch #4: modify B

Quoted 5 lines

Which files should be patched by #3 and #4?

In my opinion both #3 and #4 should fail (or both should succeed) -- with my patch only #3 will work and #4 will be rejected, because in #2 B was marked as deleted.

Both of the examples above cannot be emitted as a single commit by format-patch; the user is feeding a combined patch. Perhaps renames in each example sequence were came from one git commit but modifications are from separate commit or handcrafted "follow-up" patch.

There are two stances we can take:

(1) The user knows what he is doing.

In the first example, if he wanted the change in #3 to end up in
B, he would have arranged the patches in a different order, namely, 3 1 2, but he didn't. We should modify A (that came from C).

(2) In situations like these when it is unusual and there is no
clear and unambiguous answer, the rule has always been "fail and ask the user to clean up", because silently doing a wrong thing in an unusual situation that happens only once in a while is far worse than
interrupting the user and forcing a manual intervention.

In the first example, there is no clear answer. Perhaps all
three patches were independent patches (the first two obviously came from git because only we can do renames, but they may have been separate commits), and the user may have reordered them (or just picked a random order because he was linearizing a history with a merge).

The second one is even iffier. If we _know_ that originally patch #1 and #2 came from the same commit, then they represent swapping between A and B, but if they came from different git commits, and if the user picked patches in a random order, it may mean something completely different.

I am somewhat tempted to say that we should fail all of them, including the original "single patch swapping files" brought up by Linus.

BUT

Can we make use simple rule to detect problematic cases?

- An input to git-apply can contain more than one patch that affects
a path; however

- you cannot create a path that still exists, except for a path
that _will_ be renamed away or removed (your patch fixes this by adding this "except for..." part to loosen the existing rule);

- you cannot modify a path in a separate patch if it is involved
in an either side of a rename (this will catch the ambiguity of patch #3 in your first example and #3 and #4 in your second example);

- In addition:

- the same path cannot be renamed from more than once (this will
catch concatenation of two git generated patches);

With such a change, I think we can keep the safety of "when there are more than one plausible outcomes, the tool shouldn't silently decide, nor make progress that the user later needs to undo and redo", while allowing a sane use of rename patches generated out of a git commit.

Quoted 22 lines · Junio C Hamano

Quoted 14 lines · Michał Kiedrowicz

... However, there are some cases when these two
rules may cause problems:

patch #1: rename A to B
patch #2: rename C to A
patch #3: modify A

Should patch #3 modify B (which was A) or A (which was C)?

patch #1: rename A to B
patch #2: rename B to A
patch #3: modify A
patch #4: modify B

Quoted 5 lines

Which files should be patched by #3 and #4?

In my opinion both #3 and #4 should fail (or both should succeed) -- with my patch only #3 will work and #4 will be rejected, because in #2 B was marked as deleted.

Quoted 5 lines

Both of the examples above cannot be emitted as a single commit by format-patch; the user is feeding a combined patch. Perhaps renames in each example sequence were came from one git commit but modifications are from separate commit or handcrafted "follow-up" patch.

Yes, that's true. In "normal" case, renames and modifications should be handled properly and (generally) aren't subject of this discussion.

Quoted 22 lines

There are two stances we can take:

(1) The user knows what he is doing.

In the first example, if he wanted the change in #3 to end up in
B, he would have arranged the patches in a different order, namely, 3 1 2, but he didn't. We should modify A (that came from C).

(2) In situations like these when it is unusual and there is no
clear and unambiguous answer, the rule has always been "fail and ask the user to clean up", because silently doing a wrong thing in an unusual situation that happens only once in a while is far worse than
interrupting the user and forcing a manual intervention.

In the first example, there is no clear answer. Perhaps all
three patches were independent patches (the first two obviously came from git because only we can do renames, but they may have been separate commits), and the user may have reordered them (or just picked a random order because he was linearizing a history with a merge).

Quoted 5 lines

The second one is even iffier. If we _know_ that originally patch #1 and #2 came from the same commit, then they represent swapping between A and B, but if they came from different git commits, and if the user picked patches in a random order, it may mean something completely different.

The problem here is that there are at least two patches which touch the same file(s) and it is impossible to say which patches should be handled atomically. However, there is no easy way to specify renames as a single patch. A diff containing swapping of three files looks like this:

diff --git a/file2 b/file1
similarity index 100%
rename from file2
rename to file1
diff --git a/file3 b/file2
similarity index 100%
rename from file3
rename to file2
diff --git a/file1 b/file3
similarity index 100%
rename from file1
rename to file3

BTW: it applies correctly :).

Quoted 4 lines

I am somewhat tempted to say that we should fail all of them, including the original "single patch swapping files" brought up by Linus.

I may agree that difficult scenarios should be rejected, but I will also say that git-apply should always accept git-diff output.

Quoted 8 lines

BUT

Can we make use simple rule to detect problematic cases?

- An input to git-apply can contain more than one patch that affects
a path; however

Quoted 7 lines

- you cannot create a path that still exists, except for a path
that _will_ be renamed away or removed (your patch fixes this by adding this "except for..." part to loosen the existing rule);

- you cannot modify a path in a separate patch if it is involved
in an either side of a rename (this will catch the ambiguity of patch #3 in your first example and #3 and #4 in your second example);

What should happen in following situation:

patch #1: modify A
patch #2: rename A to B

#2 should fail? Now it creates new B which is a copy of A before applying any patches and modifies A according to #1.

Do you mean that patches which break above rules should be skipped when "--reject" is set, as other failures? Or that whole git-apply should fail regardless of "--reject"?

Quoted 14 lines · Michał Kiedrowicz

... However, there are some cases when these two
rules may cause problems:

patch #1: rename A to B
patch #2: rename C to A
patch #3: modify A

Should patch #3 modify B (which was A) or A (which was C)?

patch #1: rename A to B
patch #2: rename B to A
patch #3: modify A
patch #4: modify B

Quoted 5 lines

Which files should be patched by #3 and #4?

In my opinion both #3 and #4 should fail (or both should succeed) -- with my patch only #3 will work and #4 will be rejected, because in #2 B was marked as deleted.

Both of the examples above cannot be emitted as a single commit by format-patch; the user is feeding a combined patch. Perhaps renames in each example sequence were came from one git commit but modifications are from separate commit or handcrafted "follow-up" patch.

There are two stances we can take:

(1) The user knows what he is doing.

In the first example, if he wanted the change in #3 to end up in B, he would have arranged the patches in a different order, namely, 3 1 2, but he didn't. We should modify A (that came from C).

Quoted 4 lines

There are two stances we can take:

(1) The user knows what he is doing.

Quoted 4 lines

In the first example, if he wanted the change in #3 to end up in B, he would have arranged the patches in a different order, namely, 3 1 2, but he didn't. We should modify A (that came from C).

This gets my vote. Standard "diff -u" patches have always had to be numbered properly if they have even the slightest chance of interfering with each other, so developers are already used to it.