patchbuiltin-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 <michal.kiedrowicz@gmail.com>

> diff --git a/builtin-apply.c b/builtin-apply.c
> index 1926cd8..6f6bf85 100644
> --- a/builtin-apply.c
> +++ b/builtin-apply.c
> @@ -2271,6 +2271,16 @@ static struct patch *in_fn_table(const char *name)
>  	return NULL;
>  }
>  
> +static int to_be_deleted(struct patch *patch)
> +{
> +	return patch == (struct patch *) -2;
> +}
> +
> +static int was_deleted(struct patch *patch)
> +{
> +	return patch == (struct patch *) -1;
> +}

> @@ -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
> +	 */
> +	while (patch) {
> +		if ((patch->new_name == NULL) || (patch->is_rename)) {
> +			struct string_list_item *item =
> +				string_list_insert(patch->old_name, &fn_table);
> +			item->util = (struct patch *) -2;
> +		}
> +		patch = patch->next;
> +	}
> +}

> @@ -2410,6 +2438,8 @@ static int check_preimage(struct patch *patch, struct cache_entry **ce, struct s
>  			return error("%s: %s", old_name, strerror(errno));
>  	}
>  
> +	if(to_be_deleted(tpatch)) tpatch = NULL;
> +

> 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?

> Junio C Hamano <gitster@pobox.com> wrote:
> ...
>> 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?
>
> 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. 

>  
> >
> > 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.

> Michał Kiedrowicz <michal.kiedrowicz@gmail.com> writes:
> 
>> ... 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.
> 
> 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).
> 

>> 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).
>>
>
> 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.

> Michał Kiedrowicz <michal.kiedrowicz@gmail.com> writes:
>   
>> ... 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.  
> 
> 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.

> 
> 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.
> 
> 

> Junio C Hamano <gitster@pobox.com> wrote:
>
>> Michał Kiedrowicz <michal.kiedrowicz@gmail.com> writes:
>>   
>>> ... 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.  
>> 
>> 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.
>
>>
>> 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.
>
> 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 :).
>
>> 
>> 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.
>
>> 
>> 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);
>
> 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.