{"thread":{"id":"22689","subject":"[RFC/PATCH 1/3] apply: Allow blank context lines to match beyond EOF","startedAt":"2010-02-17T07:03:04Z","lastAt":"2010-02-18T08:45:25Z","messageCount":3,"participants":["Björn Gustavsson","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"134839","messageId":"4B7B94A8.5000102@gmail.com","threadId":"22689","inReplyTo":null,"subject":"[RFC/PATCH 1/3] apply: Allow blank context lines to match beyond EOF","fromName":"Björn Gustavsson","fromEmail":"bgustavsson@gmail.com","sentAt":"2010-02-17T07:03:04Z","receivedAt":"2010-02-17T07:03:04Z","isPatch":true,"sender":{"key":"bgustavsson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/74840?v=4"},"body":"\"git apply --whitespace=fix\" will not always succeed when used\non a series of patches in the following circumstances:\n\n* One patch adds a blank line at the end of a file. (Since\n  --whitespace=fix is used, the blank line will *not* be added.)\n\n* The next patch adds non-blanks lines after the blank line\n  introduced in the first patch. That patch will not apply\n  because the blank line that is expected to be found at end\n  of the file is no longer there.\n\nFix this problem by allowing a blank context line at the beginning\nof a hunk to match if parts of it falls beyond end of the file\n(i.e. at least one context line must match an existing line in\nthe file).\n\nTODO: We should probably require that at least one *non-blank*\ncontext line should fall within the boundaries of the file.\n\nTODO: Since this commit touches an important code path in git,\nwe probably want to add more test cases.\n\nTODO: It could also be useful to handle files that shrink with\nblanks lines at the end.\n\nSigned-off-by: Björn Gustavsson <bgustavsson@gmail.com>\n---\n builtin-apply.c |  127 ++++++++++++++++++++++++++++++++++++++++++++++--------\n 1 files changed, 108 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin-apply.c b/builtin-apply.c\nindex 2a1004d..75c04f0 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -1854,18 +1854,55 @@ static int match_fragment(struct image *img,\n {\n \tint i;\n \tchar *fixed_buf, *buf, *orig, *target;\n+\tint limit;\n+\tint preimage_limit;\n \n-\tif (preimage->nr + try_lno > img->nr)\n+\t/*\n+\t * Should we remove blanks line at the end of the file?\n+\t *\n+\t * If yes, we will allow blank lines in the preimage to\n+\t * match non-existing lines beyond the last existing line\n+\t * in the file, provided that at least one line falls\n+\t * within the boundaries of the file.\n+\t */\n+\tif (match_end && ws_error_action == correct_ws_error &&\n+\t    ws_rule & WS_BLANK_AT_EOF &&\n+\t    try_lno < img->nr) {\n+\t\t/*\n+\t\t * This hunk must match the end of the file (img) or\n+\t\t * beyond. Set up limit and preimage_limit so that\n+\t\t * the early rejection tests that follow will\n+\t\t * allow the preimage to have lines that extend beyond\n+\t\t * the end of the file. The quick hash test will\n+\t\t * only compare the lines in the preimage that \n+\t\t * fall within the boundaries of img.\n+\t\t */\n+\t\tlimit = try_lno + preimage->nr;\n+\t\tpreimage_limit = img->nr - try_lno;\n+\t} else {\n+\t\t/*\n+\t\t * Not the last hunk or not removing blanks lined\n+\t\t * the end of the file.\n+\t\t *\n+\t\t * Set up the variables so that any hunk that\n+\t\t * fall beyound the end of the file will be\n+\t\t * quickly rejected.\n+\t\t */\n+\t\tlimit = img->nr;\n+\t\tpreimage_limit = preimage->nr;\n+\t}\n+\n+\tif (preimage->nr + try_lno > limit)\n \t\treturn 0;\n \n \tif (match_beginning && try_lno)\n \t\treturn 0;\n \n-\tif (match_end && preimage->nr + try_lno != img->nr)\n+\tif (match_end && preimage->nr + try_lno != limit)\n \t\treturn 0;\n \n \t/* Quick hash check */\n-\tfor (i = 0; i < preimage->nr; i++)\n+\tfor (i = 0; i < preimage_limit; i++)\n \t\tif (preimage->line[i].hash != img->line[try_lno + i].hash)\n \t\t\treturn 0;\n \n@@ -1875,12 +1912,17 @@ static int match_fragment(struct image *img,\n \t * otherwise try+fragsize must be still within the preimage,\n \t * and either case, the old piece should match the preimage\n \t * exactly.\n+\t *\n+\t * We can only have an exact match if the preimage does not\n+\t * extend beyond the end of the file.\n \t */\n-\tif ((match_end\n-\t     ? (try + preimage->len == img->len)\n-\t     : (try + preimage->len <= img->len)) &&\n-\t    !memcmp(img->buf + try, preimage->buf, preimage->len))\n-\t\treturn 1;\n+\tif (preimage_limit == preimage->nr) {\n+\t\tif ((match_end\n+\t\t     ? (try + preimage->len == img->len)\n+\t\t     : (try + preimage->len <= img->len)) &&\n+\t\t    !memcmp(img->buf + try, preimage->buf, preimage->len))\n+\t\t\treturn 1;\n+\t}\n \n \t/*\n \t * No exact match. If we are ignoring whitespace, run a line-by-line\n@@ -1932,12 +1974,16 @@ static int match_fragment(struct image *img,\n \t * it might with whitespace fuzz. We haven't been asked to\n \t * ignore whitespace, we were asked to correct whitespace\n \t * errors, so let's try matching after whitespace correction.\n+\t *\n+\t * The preimage may extend beyond the end of the file,\n+\t * but in this loop we will only handle the part of the\n+\t * preimage that falls within the file.\n \t */\n \tfixed_buf = xmalloc(preimage->len + 1);\n \tbuf = fixed_buf;\n \torig = preimage->buf;\n \ttarget = img->buf + try;\n-\tfor (i = 0; i < preimage->nr; i++) {\n+\tfor (i = 0; i < preimage_limit; i++) {\n \t\tsize_t fixlen; /* length after fixing the preimage */\n \t\tsize_t oldlen = preimage->line[i].len;\n \t\tsize_t tgtlen = img->line[try_lno + i].len;\n@@ -1977,6 +2023,29 @@ static int match_fragment(struct image *img,\n \t\ttarget += tgtlen;\n \t}\n \n+\n+\t/*\n+\t * Now handle the lines in the preimage that falls beyond the\n+\t * end of the file (if any). They will only match if they are\n+\t * empty or only contain whitespace (if WS_BLANK_AT_EOL is\n+\t * false).\n+\t */\n+\tfor ( ; i < preimage->nr; i++) {\n+\t\tsize_t fixlen; /* length after fixing the preimage */\n+\t\tsize_t oldlen = preimage->line[i].len;\n+\t\tint j;\n+\n+\t\t/* Try fixing the line in the preimage */\n+\t\tfixlen = ws_fix_copy(buf, orig, oldlen, ws_rule, NULL);\n+\n+\t\tfor (j = 0; j < fixlen; j++)\n+\t\t\tif (!isspace(buf[j]))\n+\t\t\t\tgoto unmatch_exit;\n+\n+\t\torig += oldlen;\n+\t\tbuf += fixlen;\n+\t}\n+\n \t/*\n \t * Yes, the preimage is based on an older version that still\n \t * has whitespace breakages unfixed, and fixing them makes the\n@@ -2002,11 +2071,17 @@ static int find_pos(struct image *img,\n \tunsigned long backwards, forwards, try;\n \tint backwards_lno, forwards_lno, try_lno;\n \n-\tif (preimage->nr > img->nr)\n-\t\treturn -1;\n+\t/*\n+\t * There used to be a quick reject here in case preimage\n+\t * had more lines than img. We must let match_fragment()\n+\t * handle that case because a hunk is now allowed to\n+\t * extend beyond the end of img when --whitespace=fix\n+\t * has been given (and core.whitespace.blanks-at-eof is\n+\t * enabled).\n+\t */\n \n \t/*\n-\t * If match_begining or match_end is specified, there is no\n+\t * If match_beginning or match_end is specified, there is no\n \t * point starting from a wrong line that will never match and\n \t * wander around and wait for a match at the specified end.\n \t */\n@@ -2091,12 +2166,26 @@ static void update_image(struct image *img,\n \tint i, nr;\n \tsize_t remove_count, insert_count, applied_at = 0;\n \tchar *result;\n+\tint preimage_limit;\n+\n+\t/*\n+\t * If we are removing blank lines at the end of img,\n+\t * the preimage may extend beyond the end.\n+\t * If that is the case, we must be careful only to\n+\t * remove the part of the preimage that falls within\n+\t * the boundaries of img. Initialize preimage_limit\n+\t * to the number of lines in the preimage that falls\n+\t * within the boundaries.\n+\t */\n+\tpreimage_limit = preimage->nr;\n+\tif (preimage_limit > img->nr - applied_pos)\n+\t\tpreimage_limit = img->nr - applied_pos;\n \n \tfor (i = 0; i < applied_pos; i++)\n \t\tapplied_at += img->line[i].len;\n \n \tremove_count = 0;\n-\tfor (i = 0; i < preimage->nr; i++)\n+\tfor (i = 0; i < preimage_limit; i++)\n \t\tremove_count += img->line[applied_pos + i].len;\n \tinsert_count = postimage->len;\n \n@@ -2113,8 +2202,8 @@ static void update_image(struct image *img,\n \tresult[img->len] = '\\0';\n \n \t/* Adjust the line table */\n-\tnr = img->nr + postimage->nr - preimage->nr;\n-\tif (preimage->nr < postimage->nr) {\n+\tnr = img->nr + postimage->nr - preimage_limit;\n+\tif (preimage_limit < postimage->nr) {\n \t\t/*\n \t\t * NOTE: this knows that we never call remove_first_line()\n \t\t * on anything other than pre/post image.\n@@ -2122,10 +2211,10 @@ static void update_image(struct image *img,\n \t\timg->line = xrealloc(img->line, nr * sizeof(*img->line));\n \t\timg->line_allocated = img->line;\n \t}\n-\tif (preimage->nr != postimage->nr)\n+\tif (preimage_limit != postimage->nr)\n \t\tmemmove(img->line + applied_pos + postimage->nr,\n-\t\t\timg->line + applied_pos + preimage->nr,\n-\t\t\t(img->nr - (applied_pos + preimage->nr)) *\n+\t\t\timg->line + applied_pos + preimage_limit,\n+\t\t\t(img->nr - (applied_pos + preimage_limit)) *\n \t\t\tsizeof(*img->line));\n \tmemcpy(img->line + applied_pos,\n \t       postimage->line,\n@@ -2321,7 +2410,7 @@ static int apply_one_fragment(struct image *img, struct fragment *frag,\n \n \tif (applied_pos >= 0) {\n \t\tif (new_blank_lines_at_end &&\n-\t\t    preimage.nr + applied_pos == img->nr &&\n+\t\t    preimage.nr + applied_pos >= img->nr &&\n \t\t    (ws_rule & WS_BLANK_AT_EOF) &&\n \t\t    ws_error_action != nowarn_ws_error) {\n \t\t\trecord_ws_error(WS_BLANK_AT_EOF, \"+\", 1, frag->linenr);\n-- \n1.7.0\n"},{"id":"134847","messageId":"7vbpfo5le0.fsf@alter.siamese.dyndns.org","threadId":"22689","inReplyTo":"4B7B94A8.5000102@gmail.com","subject":"Re: [RFC/PATCH 1/3] apply: Allow blank context lines to match beyond EOF","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-02-17T08:14:47Z","receivedAt":"2010-02-17T08:14:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Björn Gustavsson <bgustavsson@gmail.com> writes:\n\n> \"git apply --whitespace=fix\" will not always succeed when used\n> on a series of patches in the following circumstances:\n>\n> * One patch adds a blank line at the end of a file. (Since\n>   --whitespace=fix is used, the blank line will *not* be added.)\n>\n> * The next patch adds non-blanks lines after the blank line\n>   introduced in the first patch. That patch will not apply\n>   because the blank line that is expected to be found at end\n>   of the file is no longer there.\n>\n> Fix this problem by allowing a blank context line at the beginning\n> of a hunk to match if parts of it falls beyond end of the file\n> (i.e. at least one context line must match an existing line in\n> the file).\n>\n> TODO: We should probably require that at least one *non-blank*\n> context line should fall within the boundaries of the file.\n\nI think that is very sensible; I thought about this after I wrote the\nreview message in the previous round but failed to mention it.  Happy to\nsee that you are thinking along the same line.\n\n> @@ -2002,11 +2071,17 @@ static int find_pos(struct image *img,\n>  \tunsigned long backwards, forwards, try;\n>  \tint backwards_lno, forwards_lno, try_lno;\n>  \n> -\tif (preimage->nr > img->nr)\n> -\t\treturn -1;\n> +\t/*\n> +\t * There used to be a quick reject here in case preimage\n> +\t * had more lines than img. We must let match_fragment()\n> +\t * handle that case because a hunk is now allowed to\n> +\t * extend beyond the end of img when --whitespace=fix\n> +\t * has been given (and core.whitespace.blanks-at-eof is\n> +\t * enabled).\n> +\t */\n\nIs it worth to keep the quick-reject if we are not running under\nblank-at-eof mode?\n"},{"id":"134933","messageId":"6672d0161002180045q7a42ae49la7831dc0431d474a@mail.gmail.com","threadId":"22689","inReplyTo":"7vbpfo5le0.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] apply: Allow blank context lines to match beyond EOF","fromName":"Björn Gustavsson","fromEmail":"bgustavsson@gmail.com","sentAt":"2010-02-18T08:45:25Z","receivedAt":"2010-02-18T08:45:25Z","isPatch":true,"sender":{"key":"bgustavsson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/74840?v=4"},"body":"2010/2/17 Junio C Hamano <gitster@pobox.com>:\n\n>> @@ -2002,11 +2071,17 @@ static int find_pos(struct image *img,\n>>       unsigned long backwards, forwards, try;\n>>       int backwards_lno, forwards_lno, try_lno;\n>>\n>> -     if (preimage->nr > img->nr)\n>> -             return -1;\n>> +     /*\n>> +      * There used to be a quick reject here in case preimage\n>> +      * had more lines than img. We must let match_fragment()\n>> +      * handle that case because a hunk is now allowed to\n>> +      * extend beyond the end of img when --whitespace=fix\n>> +      * has been given (and core.whitespace.blanks-at-eof is\n>> +      * enabled).\n>> +      */\n>\n> Is it worth to keep the quick-reject if we are not running under\n> blank-at-eof mode?\n\nGood point.\n\nAs far as I can understand, the quick reject could only make\na difference if there is a huge preimage applied to a big file\nand it will only make \"git apply\" reject the patch faster.\n\nSo I created a text file containing one million lines. I deleted\nabout 60% of the lines and generated a diff.\n\nApplying that diff on the file where the lines had already\nbeen deleted (which would be the same as trying to\napply the patch twice on the original file), \"git apply\"\nwithout my branch (standard 1.7.0) needed 0.076s\nto reject the patch. With my branch (i.e. without the quick\nreject), \"git apply\" rejected the patch in 0.087s.\n\nSo unless there is some other real-world use case I haven't\nthought of, it does not seem worthwhile to keep\nthe quick rejection test for performance reasons.\n\nI think I'll factor out the removal of the quick reject\ninto a separate commit in my next revision of the patch\nseries, including information from this email in the\ncommit message.\n\nAnother thing is whether the rejection test is actually\nneeded for correctness reasons. As far I understand\nit, is is not not. There is one test that should be changed,\nthough, to make it clearer why it works. I intend to include\none of the following changes in my next revision of the patch\nseries.\n\nEither this one:\n\ndiff --git a/builtin-apply.c b/builtin-apply.c\nindex 75c04f0..d58c1ea 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -2090,7 +2090,11 @@ static int find_pos(struct image *img,\n        else if (match_end)\n                line = img->nr - preimage->nr;\n\n-       if (line > img->nr)\n+       /*\n+        * Because the comparison is unsigned, the following test\n+        * will also take care of a negative line number.\n+        */\n+       if ((size_t) line > img->nr)\n                line = img->nr;\n\n        try = 0;\n\nOr this one:\n\ndiff --git a/builtin-apply.c b/builtin-apply.c\nindex 75c04f0..8ca0e32 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -2090,7 +2090,9 @@ static int find_pos(struct image *img,\n        else if (match_end)\n                line = img->nr - preimage->nr;\n\n-       if (line > img->nr)\n+       if (line < 0)\n+               line = 0;\n+       else if (line > img->nr)\n                line = img->nr;\n\n        try = 0;\n\n-- \nBjörn Gustavsson, Erlang/OTP, Ericsson AB\n"}]}