Re: [BUG] git-am silently applying patches incorrectly

Junio C Hamano [off-list ref] writes:

Looking at it closer, however, I noticed that the false hit (i.e. "two
blocks closed, a blank line, return 0 and the end of function") in this
particular case only appears because we applied the previous hunk.  In the
version of the file in 0ce3017b, there is only one such place and there
should be no ambiguity in the patch application.

The problem we are seeing is caused only because we look at the result of
application of the previous hunks in the patch and incrementally try to
apply the remaining hunks.  So clearly "git apply" can and should be fixed
for this case by teaching find_pos() not to report a match on a line that
was touched by application of the previous hunk.

And here is a quick and dirty fix to do something like that.  It assumes
that the hunks for a single file being patched are already sorted in the
ascending order (which should be the case), and may regress cases where we
used to find a match even when the version you are patching has moved
functions around in the file by failing to notice a match.  And it does
get the same result as your GNU patch test.

-- >8 --
Subject: [PATCH] apply: do not look behind beyond what we already patched

When looking for a place to apply a hunk, we used to check lines that
match the preimage of it, starting from the line that the patch wants to
apply the hunk at, with increasing offsets in both ways until we find a
match.

Colin Guthrie found an interesting case where this misapplied a patch that
wanted to touch a preimage that consists of "two block closed '<indent>}<LF>',
a blank line, '<indent>return 0;<LF>', the function closed '}<LF>'".  The
target version of the file originally had only one such location, but the hunk
immediately before that created another such preimage, and find_pos() happily
reported that the preimage matched what the hunk wanted to modify.  Oops.

By recording where the last hunk is applied, and limiting the search done
by find_pos() to the rest of the file, we can reduce such an accident.
Ideally, we should not simply limit the upward search like this patch
does, but skip the regions that were touched by previous hunks, but this
approach was much simpler ;-)

I also considered to teach apply_one_fragment() to take the offset we have
found while applying the previous hunk into account when looking for a
match with find_pos(), but dismissed that approach, because it would
sometimes work better but sometimes worse, depending on the difference
between the version the patch was created against and the version the
patch is being applied.

Signed-off-by: Junio C Hamano <redacted>
---
 builtin/apply.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/builtin/apply.c b/builtin/apply.c
index 14951da..30857c6 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c

@@ -211,6 +211,7 @@ struct line {
  */
 struct image {
 	char *buf;
+	size_t last_match;
 	size_t len;
 	size_t nr;
 	size_t alloc;

@@ -2323,11 +2324,11 @@ static int find_pos(struct image *img,
 			return try_lno;
 
 	again:
-		if (backwards_lno == 0 && forwards_lno == img->nr)
+		if (backwards_lno <= img->last_match && forwards_lno == img->nr)
 			break;
 
 		if (i & 1) {
-			if (backwards_lno == 0) {
+			if (backwards_lno <= img->last_match) {
 				i++;
 				goto again;
 			}

@@ -2648,6 +2649,7 @@ static int apply_one_fragment(struct image *img, struct fragment *frag,
 				" to apply fragment at %d\n",
 				leading, trailing, applied_pos+1);
 		update_image(img, applied_pos, &preimage, &postimage);
+		img->last_match = applied_pos;
 	} else {
 		if (apply_verbosely)
 			error("while searching for:\n%.*s",

On Fri, Mar 4, 2011 at 11:05 AM, Junio C Hamano [off-list ref] wrote:

And here is a quick and dirty fix to do something like that.  It assumes
that the hunks for a single file being patched are already sorted in the
ascending order (which should be the case), and may regress cases where we
used to find a match even when the version you are patching has moved
functions around in the file by failing to notice a match.  And it does
get the same result as your GNU patch test.

Ack. Looks correct. In fact, shouldn't we make that "last_match" be
the _end_ of the last place we applied the patch at, rather than the
beginning?

IOW, maybe something like "img->last_match = applied_pos +
postimage.nr;" or whatever.

I dunno.

                     Linus

On Fri, 2011-03-04 at 11:05 -0800, Junio C Hamano wrote:

Junio C Hamano [off-list ref] writes:

quoted

Looking at it closer, however, I noticed that the false hit (i.e. "two
blocks closed, a blank line, return 0 and the end of function") in this
particular case only appears because we applied the previous hunk.  In the
version of the file in 0ce3017b, there is only one such place and there
should be no ambiguity in the patch application.

The problem we are seeing is caused only because we look at the result of
application of the previous hunks in the patch and incrementally try to
apply the remaining hunks.  So clearly "git apply" can and should be fixed
for this case by teaching find_pos() not to report a match on a line that
was touched by application of the previous hunk.

And here is a quick and dirty fix to do something like that.  It assumes
that the hunks for a single file being patched are already sorted in the
ascending order (which should be the case), and may regress cases where we
used to find a match even when the version you are patching has moved
functions around in the file by failing to notice a match.  And it does
get the same result as your GNU patch test.

It checks out here applied against master. I don't know how I got it to
work the first time without this patch--but I'm pretty sure I don't want
to know at this point.

-- 
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59