{"thread":{"id":"22846","subject":"[PATCH v3 2/5] apply: Remove the quick rejection test","startedAt":"2010-02-27T13:52:08Z","lastAt":"2010-02-27T13:52:08Z","messageCount":1,"participants":["Björn Gustavsson"],"isPatch":true,"patchVersion":3,"patchTotal":5},"messages":[{"id":"135834","messageId":"4B892388.6060502@gmail.com","threadId":"22846","inReplyTo":null,"subject":"[PATCH v3 2/5] apply: Remove the quick rejection test","fromName":"Björn Gustavsson","fromEmail":"bgustavsson@gmail.com","sentAt":"2010-02-27T13:52:08Z","receivedAt":"2010-02-27T13:52:08Z","isPatch":true,"sender":{"key":"bgustavsson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/74840?v=4"},"body":"In the next commit, we will make it possible for blank context\nlines to match beyond the end of the file. That means that a hunk\nwith a preimage that has more lines than present in the file may\nbe possible to successfully apply. Therefore, we must remove\nthe quick rejection test in find_pos().\n\nfind_pos() will already work correctly without the quick\nrejection test, but that might not be obvious. Therefore,\ncomment the test for handling out-of-range line numbers in\nfind_pos() and cast the \"line\" variable to the same (unsigned)\ntype as img->nr.\n\nWhat are performance implications of removing the quick\nrejection test?\n\nIt can only help \"git apply\" to reject a patch faster. For example,\nif I have a file with one million lines and a patch that removes\nslightly more than 50 percent of the lines and try to apply that\npatch twice, the second attempt will fail slightly faster\nwith the test than without (based on actual measurements).\n\nHowever, there is the pathological case of a patch with many\nmore context lines than the default three, and applying that patch\nusing \"git apply -C1\". Without the rejection test, the running\ntime will be roughly proportional to the number of context lines\ntimes the size of the file. That could be handled by writing\na more complicated rejection test (it would have to count the\nnumber of blanks at the end of the preimage), but I don't find\nthat worth doing until there is a real-world use case that\nwould benfit from it.\n\nIt would be possible to keep the quick rejection test if\n--whitespace=fix is not given, but I don't like that from\na testing point of view.\n\nSigned-off-by: Björn Gustavsson <bgustavsson@gmail.com>\n---\n builtin-apply.c           |   12 +++++++-----\n t/t4104-apply-boundary.sh |    9 +++++++++\n 2 files changed, 16 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin-apply.c b/builtin-apply.c\nindex fc6c708..9641a64 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -1997,11 +1997,8 @@ 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-\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@@ -2010,7 +2007,12 @@ static int find_pos(struct image *img,\n \telse if (match_end)\n \t\tline = img->nr - preimage->nr;\n \n-\tif (line > img->nr)\n+\t/*\n+\t * Because the comparison is unsigned, the following test\n+\t * will also take care of a negative line number that can\n+\t * result when match_end and preimage is larger than the target.\n+\t */\n+\tif ((size_t) line > img->nr)\n \t\tline = img->nr;\n \n \ttry = 0;\ndiff --git a/t/t4104-apply-boundary.sh b/t/t4104-apply-boundary.sh\nindex 0e3ce36..c617c2a 100755\n--- a/t/t4104-apply-boundary.sh\n+++ b/t/t4104-apply-boundary.sh\n@@ -134,4 +134,13 @@ test_expect_success 'two lines' '\n \n '\n \n+test_expect_success 'apply patch with 3 context lines matching at end' '\n+\t{ echo a; echo b; echo c; echo d; } >file &&\n+\tgit add file &&\n+\techo e >>file &&\n+\tgit diff >patch &&\n+\t>file &&\n+\ttest_must_fail git apply patch\n+'\n+\n test_done\n-- \n1.7.0\n"}]}