{"thread":{"id":"49037","subject":"[PATCH 0/4] line-log: be more careful when adjusting multiple line ranges","startedAt":"2018-08-04T22:18:26Z","lastAt":"2018-08-07T22:01:03Z","messageCount":20,"participants":["Johannes Schindelin via GitGitGadget","Jonathan Nieder","Junio C Hamano","Andrei Rybak","Eric Sunshine","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"354505","messageId":"pull.15.git.gitgitgadget@gmail.com","threadId":"49037","inReplyTo":null,"subject":"[PATCH 0/4] line-log: be more careful when adjusting multiple line ranges","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-04T22:18:22Z","receivedAt":"2018-08-04T22:18:26Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"I am a heavy user of git log -L .... In fact, I use the feature where\nmultiple ranges can be specified extensively, via a not-exactly-trivial\nshell script function that takes the currently staged changes (or if none\nare staged, the current unstanged changes) and turns them into the\ncorresponding commit history:\n\nstaged_log () { #\n diff=\"$(git diff --cached -U1)\"\n test -n \"$diff\" ||\n diff=\"$(git diff -U1)\"\n test -n \"$diff\" ||\n die \"No changes\"\n eval \"git log $(echo \"$diff\" |\n sed -ne '/^--- a\\//{s/^-* a\\/\\(.*\\)/'\\''\\1'\\''/;x}' -e \\\n '/^@@ -/{s/^@@ -\\([^, ]*\\),\\([^ ]*\\).*/-L \\1,+\\2/;G;s/\\n/:/g;p}' |\n tr '\\n' ' ')\"\n}\n\nThis is an extremely useful way to look at the history, especially when\ntrying to fix up a commit deep in a long branch (or a thicket of branches).\n\nToday, however, this method failed me, by greeting me with an assertion.\nWhen I tried to paper over that assertion by joining line ranges that became\nadjacent (or overlapping), it still produced a segmentation fault when the\nline-log tried to print lines past the file contents.\n\nSo I had no choice but to fix this properly.\n\nI still wanted to keep the optimization where multiple line ranges are\njoined into a single one (I am convinced that this also affects the output,\nwhere previously multiple hunks would have been displayed, but I ran out of\ntime to investigate this). This is the 3rd patch. It is not purely an\noptimization, as the assertion would still trigger when line ranges could be\njoined.\n\nNow, I am fairly certain that the changes are correct, but given my track\nrecord with off-by-one bugs (and once even an off-by-two bug), I would\nreally appreciate some thorough review of this code, in particular the\nsecond one that is the actual bug fix. I am specifically interested in\nreviews from people who know line-log.c pretty well and can tell me whether\nthe src[i].end > target[j].end is correct, or whether it should actually\nhave been a >= (I tried to wrap my head around this, but I would feel more\ncomfortable if a domain expert would analyze this, whistling, and looking\nEric's way).\n\nCc: Eric Sunshine sunshine@sunshineco.com [sunshine@sunshineco.com]\n\nJohannes Schindelin (4):\n line-log: demonstrate a bug with nearly-overlapping ranges\n line-log: adjust start/end of ranges individually\n line-log: optimize ranges by joining them when possible\n line-log: convert an assertion to a full BUG() call\n\n line-log.c | 18 +++++++++++++++---\n t/t4211-line-log.sh | 17 +++++++++++++++++\n 2 files changed, 32 insertions(+), 3 deletions(-)\n\n\nbase-commit: 1d89318c48d233d52f1db230cf622935ac3c69fa\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-15%2Fdscho%2Fline-log-fix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-15/dscho/line-log-fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/15\n-- \ngitgitgadget\n"},{"id":"354506","messageId":"cab7bb36eb85dbe38ad95ee02b083f11f0820e24.1533421100.git.gitgitgadget@gmail.com","threadId":"49037","inReplyTo":"pull.15.git.gitgitgadget@gmail.com","subject":"[PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-04T22:18:23Z","receivedAt":"2018-08-04T22:18:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Johannes Schindelin \n\nCurrently, this test case throws an assertion:\n\n\tAssertion failed!\n\n\tProgram: git.exe\n\tFile: line-log.c, Line 71\n\nSigned-off-by: Johannes Schindelin \n---\n t/t4211-line-log.sh | 17 +++++++++++++++++\n 1 file changed, 17 insertions(+)\n\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 436b13ad2..61ff37430 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -115,4 +115,21 @@ test_expect_success 'range_set_union' '\n \tgit log $(for x in $(test_seq 200); do echo -L $((2*x)),+1:c.c; done)\n '\n \n+q_to_lf () {\n+\ttr Q '\\012'\n+}\n+\n+test_expect_failure 'close to overlapping ranges' '\n+\ttest_seq 5 >a1.c &&\n+\tgit add a1.c &&\n+\tgit commit -m \"5 lines\" a1.c &&\n+\tsed s/3/3QaQb/ tmp &&\n+\tmv tmp a1.c &&\n+\tgit commit -m \"2 more lines\" a1.c &&\n+\tsed s/4/cQ4/ tmp &&\n+\tmv tmp a1.c &&\n+\tgit commit -m \"1 more line\" a1.c &&\n+\tgit --no-pager log -L 1,3:a1.c -L 5,8:a1.c\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"354507","messageId":"7f92d92154143127734a638e41e064adce46a2e2.1533421100.git.gitgitgadget@gmail.com","threadId":"49037","inReplyTo":"pull.15.git.gitgitgadget@gmail.com","subject":"[PATCH 2/4] line-log: adjust start/end of ranges individually","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-04T22:18:25Z","receivedAt":"2018-08-04T22:18:29Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Johannes Schindelin \n\nWhen traversing commits and adjusting the ranges, things can get really\ntricky. For example, when the line range of interest encloses several\nhunks of a commit, the line range can actually shrink.\n\nCurrently, range_set_shift_diff() does not anticipate that scenario and\nblindly adjusts start and end by the same offset (\"shift\" the range).\n\nThis can lead to a couple of surprising issues, such as assertions in\nrange_set_append() (when the end of a given range is not adjusted\nproperly, it can point after the start of the next range) or even\nsegmentation faults (when t_end in the loop of dump_diff_hacky_one()\npoints outside the valid line range).\n\nLet's fix this by adjusting the start and the end offsets individually.\n\nSigned-off-by: Johannes Schindelin \n---\n line-log.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 72a5fed66..d8d09b5ee 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -427,7 +427,7 @@ static void range_set_shift_diff(struct range_set *out,\n \t\t\t\t struct diff_ranges *diff)\n {\n \tunsigned int i, j = 0;\n-\tlong offset = 0;\n+\tlong offset = 0, start_offset;\n \tstruct range *src = rs->ranges;\n \tstruct range *target = diff->target.ranges;\n \tstruct range *parent = diff->parent.ranges;\n@@ -438,7 +438,13 @@ static void range_set_shift_diff(struct range_set *out,\n \t\t\t\t- (target[j].end-target[j].start);\n \t\t\tj++;\n \t\t}\n-\t\trange_set_append(out, src[i].start+offset, src[i].end+offset);\n+\t\tstart_offset = offset;\n+\t\twhile (j < diff->target.nr && src[i].end > target[j].end) {\n+\t\t\toffset += (parent[j].end-parent[j].start)\n+\t\t\t\t- (target[j].end-target[j].start);\n+\t\t\tj++;\n+\t\t}\n+\t\trange_set_append(out, src[i].start+start_offset, src[i].end+offset);\n \t}\n }\n \n-- \ngitgitgadget\n\n"},{"id":"354508","messageId":"d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com","threadId":"49037","inReplyTo":"pull.15.git.gitgitgadget@gmail.com","subject":"[PATCH 3/4] line-log: optimize ranges by joining them when possible","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-04T22:18:26Z","receivedAt":"2018-08-04T22:18:30Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Johannes Schindelin \n\nTechnically, it is okay to have line ranges that touch (i.e. the end of\nthe first range ends just before the next range begins). However, it is\ninefficient, and when the user provides such touching ranges via\nmultiple `-L` options, we already join them.\n\nWhen we traverse the history, though, we never join ranges, even they\nbecome \"touchy-feely\" due to added lines (which are \"removed\" from\nline-log's point of view because it traverses the commit history into\nthe past).\n\nLet's optimize also this case.\n\nSigned-off-by: Johannes Schindelin \n---\n line-log.c | 4 ++++\n t/t4211-line-log.sh | 2 +-\n 2 files changed, 5 insertions(+), 1 deletion(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex d8d09b5ee..bc7ef69d6 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -68,6 +68,10 @@ void range_set_append_unsafe(struct range_set *rs, long a, long b)\n \n void range_set_append(struct range_set *rs, long a, long b)\n {\n+\tif (rs->nr > 0 && rs->ranges[rs->nr-1].end + 1 == a) {\n+\t\trs->ranges[rs->nr-1].end = b;\n+\t\treturn;\n+\t}\n \tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n \trange_set_append_unsafe(rs, a, b);\n }\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 61ff37430..ebaf5ea86 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -119,7 +119,7 @@ q_to_lf () {\n \ttr Q '\\012'\n }\n \n-test_expect_failure 'close to overlapping ranges' '\n+test_expect_success 'close to overlapping ranges' '\n \ttest_seq 5 >a1.c &&\n \tgit add a1.c &&\n \tgit commit -m \"5 lines\" a1.c &&\n-- \ngitgitgadget\n\n"},{"id":"354509","messageId":"faf35214f0f339b792a30a3bd013056217d9a2c1.1533421101.git.gitgitgadget@gmail.com","threadId":"49037","inReplyTo":"pull.15.git.gitgitgadget@gmail.com","subject":"[PATCH 4/4] line-log: convert an assertion to a full BUG() call","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-04T22:18:28Z","receivedAt":"2018-08-04T22:18:31Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Johannes Schindelin \n\nThe assertion in question really indicates a bug, when triggered, so we\nmight just as well use the sanctioned method to report it.\n\nSigned-off-by: Johannes Schindelin \n---\n line-log.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex bc7ef69d6..0e09df9db 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -72,7 +72,9 @@ void range_set_append(struct range_set *rs, long a, long b)\n \t\trs->ranges[rs->nr-1].end = b;\n \t\treturn;\n \t}\n-\tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n+\tif (rs->nr > 0 && rs->ranges[rs->nr-1].end > a)\n+\t\tBUG(\"append %ld-%ld, after %ld-%ld?!?\", a, b,\n+\t\t rs->ranges[rs->nr-1].start, rs->ranges[rs->nr-1].end);\n \trange_set_append_unsafe(rs, a, b);\n }\n \n-- \ngitgitgadget\n"},{"id":"354515","messageId":"20180805015908.GE258270@aiede.svl.corp.google.com","threadId":"49037","inReplyTo":"cab7bb36eb85dbe38ad95ee02b083f11f0820e24.1533421100.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-08-05T01:59:08Z","receivedAt":"2018-08-05T01:59:43Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nJohannes Schindelin wrote:\n\n> Currently, this test case throws an assertion:\n>\n> \tAssertion failed!\n>\n> \tProgram: git.exe\n> \tFile: line-log.c, Line 71\n>\n> Signed-off-by: Johannes Schindelin \n> ---\n> t/t4211-line-log.sh | 17 +++++++++++++++++\n> 1 file changed, 17 insertions(+)\n\nThanks for finding and demonstrating it. Can you say more about what\nis going on in the test case? Alternatively, could it be squashed in\nwith the patch that fixes it?\n\nThe below will be more nitpicky:\n\n[...]\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -115,4 +115,21 @@ test_expect_success 'range_set_union' '\n> \tgit log $(for x in $(test_seq 200); do echo -L $((2*x)),+1:c.c; done)\n> '\n> \n> +q_to_lf () {\n> +\ttr Q '\\012'\n> +}\n> +\n> +test_expect_failure 'close to overlapping ranges' '\n> +\ttest_seq 5 >a1.c &&\n> +\tgit add a1.c &&\n> +\tgit commit -m \"5 lines\" a1.c &&\n\nIt would be nice to use test_tick or test_commit for a more realistic\nhistory (with time marching forward).\n\n> +\tsed s/3/3QaQb/ tmp &&\n> +\tmv tmp a1.c &&\n> +\tgit commit -m \"2 more lines\" a1.c &&\n\nIt's probably just me, but the bit with Q makes it hard for me to\nfollow. Maybe there's a simpler way?\n\n\"sed -e '3aa' -e '3ab'\" works here, but I don't know how portable it\nis. I'd be more tempted to do\n\n\ttest_write_lines 1 2 3 4 5 >a1.c &&\n\t...\n\n\ttest_write_lines 1 2 3 a b 4 5 >a1.c &&\n\t...\n\n\ttest_write_lines 1 2 3 a b c 4 5 >a1.c &&\n\t...\n\nwhich is concise and has obvious behavior.\n\nThanks and hope that helps,\nJonathan\n"},{"id":"354532","messageId":"xmqq7el5s5qi.fsf@gitster-ct.c.googlers.com","threadId":"49037","inReplyTo":"d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/4] line-log: optimize ranges by joining them when possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-05T06:11:01Z","receivedAt":"2018-08-05T06:11:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Johannes Schindelin via GitGitGadget\" \nwrites:\n\n> From: Johannes Schindelin \n>\n> Technically, it is okay to have line ranges that touch (i.e. the end of\n> the first range ends just before the next range begins). However, it is\n> inefficient, and when the user provides such touching ranges via\n> multiple `-L` options, we already join them.\n>\n> When we traverse the history, though, we never join ranges, even they\n> become \"touchy-feely\" due to added lines (which are \"removed\" from\n> line-log's point of view because it traverses the commit history into\n> the past).\n\nI do not know if that would be an \"optimization\" (in the sense that\njoining would help performance) but I do agree that such a change\nmakes perfect sense from consistency's point of view. If two ranges\nthat were originally apart lose a gap in between them, it does not\nmake any sense to keep them separate. Good thinking.\n\n> diff --git a/line-log.c b/line-log.c\n> index d8d09b5ee..bc7ef69d6 100644\n> --- a/line-log.c\n> +++ b/line-log.c\n> @@ -68,6 +68,10 @@ void range_set_append_unsafe(struct range_set *rs, long a, long b)\n> \n> void range_set_append(struct range_set *rs, long a, long b)\n> {\n> +\tif (rs->nr > 0 && rs->ranges[rs->nr-1].end + 1 == a) {\n> +\t\trs->ranges[rs->nr-1].end = b;\n> +\t\treturn;\n> +\t}\n\nNice.\n\n> \tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n\n> \trange_set_append_unsafe(rs, a, b);\n> }\n> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\n> index 61ff37430..ebaf5ea86 100755\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -119,7 +119,7 @@ q_to_lf () {\n> \ttr Q '\\012'\n> }\n> \n> -test_expect_failure 'close to overlapping ranges' '\n> +test_expect_success 'close to overlapping ranges' '\n> \ttest_seq 5 >a1.c &&\n> \tgit add a1.c &&\n> \tgit commit -m \"5 lines\" a1.c &&\n"},{"id":"354540","messageId":"9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com","threadId":"49037","inReplyTo":"d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/4] line-log: optimize ranges by joining them when possible","fromName":"Andrei Rybak","fromEmail":"rybak.a.v@gmail.com","sentAt":"2018-08-05T08:45:45Z","receivedAt":"2018-08-05T08:45:51Z","isPatch":true,"sender":{"key":"rybak.a.v@gmail.com","avatar":"https://avatars.githubusercontent.com/u/624072?v=4"},"body":"On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:\n> \n> Now, I am fairly certain that the changes are correct, but given my track\n> record with off-by-one bugs (and once even an off-by-two bug), I would\n> really appreciate some thorough review of this code, in particular the\n> second one that is the actual bug fix. I am specifically interested in\n> reviews from people who know line-log.c pretty well and can tell me whether\n> the src[i].end > target[j].end is correct, or whether it should actually\n> have been a >= (I tried to wrap my head around this, but I would feel more\n> comfortable if a domain expert would analyze this, whistling, and looking\n> Eric's way).\n\nI don't know line-log.c at all, but here are my comments on the more\nabstract range and range_set changes:\n\nOn 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:\n> From: Johannes Schindelin \n> \n> Technically, it is okay to have line ranges that touch (i.e. the end of\n> the first range ends just before the next range begins). However, it is\n> inefficient, and when the user provides such touching ranges via\n> multiple `-L` options, we already join them.\n>\n> ...\n>\n> void range_set_append(struct range_set *rs, long a, long b)\n> {\n> +\tif (rs->nr > 0 && rs->ranges[rs->nr-1].end + 1 == a) {\n> +\t\trs->ranges[rs->nr-1].end = b;\n> +\t\treturn;\n> +\t}\n\nAs I understand it, this patch attempts to make range_set_append extend\nthe last range in the range set to include [a,b), if [a,b) \"touches\" the\nlast range in rs.\n\nDefinition of range from line-log.h reads:\n\n /* A range [start,end]. Lines are numbered starting at 0, and the\n * ranges include start but exclude end. */\n struct range {\n long start, end;\n };\n\nSo the optimization described in commit message should take care of\nfollowing case, with zero lines between last range in rs and [a,b):\n\n rs before : [---) ... [---)\n [a,b) : [---)\n rs after : [---) ... [-------)\n \nIt seems that the first condition in range_set_append should be:\n\n\tif (rs->nr > 0 && rs->ranges[rs->nr-1].end == a) {\n\t\t// extend the last range to include [a, b)\n\t}\n\nI think that the comments around struct range could be improved by\nswitching from using \"[]\", as in the comment from line-log.h quoted\nabove, and \"|---|\" as in various comments in line-log.c to \"left-closed,\nright-open\" interval notation like \"[start,end)\" and \"[---)\".\n\n> \tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n> \trange_set_append_unsafe(rs, a, b);\n> }\n\nWith these consideration in mind the assert should become\n\n\tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end < a);\n \nto cover cases starting from one line between last range in rs and [a,b)\n\n rs before : [---) ... [---)\n [a,b) : [---)\n rs after : [---) ... [---)[---)\n ^\n |\n\t\tthis line still not part of the range set.\n \n"},{"id":"354542","messageId":"CAPig+cRWcFVbA76_HT2iVD16bsUmbWdCgk_07rmiGneM5czdOQ@mail.gmail.com","threadId":"49037","inReplyTo":"7f92d92154143127734a638e41e064adce46a2e2.1533421100.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/4] line-log: adjust start/end of ranges individually","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-05T10:14:01Z","receivedAt":"2018-08-05T10:14:15Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Aug 4, 2018 at 6:18 PM Johannes Schindelin via GitGitGadget\n wrote:\n> When traversing commits and adjusting the ranges, things can get really\n> tricky. For example, when the line range of interest encloses several\n> hunks of a commit, the line range can actually shrink.\n>\n> Currently, range_set_shift_diff() does not anticipate that scenario and\n> blindly adjusts start and end by the same offset (\"shift\" the range).\n> [...]\n> Let's fix this by adjusting the start and the end offsets individually.\n>\n> Signed-off-by: Johannes Schindelin \n> ---\n> diff --git a/line-log.c b/line-log.c\n> @@ -438,7 +438,13 @@ static void range_set_shift_diff(struct range_set *out,\n> - (target[j].end-target[j].start);\n> j++;\n> }\n> - range_set_append(out, src[i].start+offset, src[i].end+offset);\n> + start_offset = offset;\n> + while (j < diff->target.nr && src[i].end > target[j].end) {\n> + offset += (parent[j].end-parent[j].start)\n> + - (target[j].end-target[j].start);\n> + j++;\n> + }\n> + range_set_append(out, src[i].start+start_offset, src[i].end+offset);\n\nI'm still trying to wrap my head around the original code, so I'm not\neven at the point of being able to say if this fix is correct. What\nhappens if the \"start_offset\" loop consumes all of 'j' before it even\ngets to the new loop? Why does the new loop use '>' whereas the\nexisting uses '>='?\n\nHaving said that, a much easier fix is to use\nrange_set_append_unsafe() here, and then at the bottom of the loop,\ninvoke 'sort_and_merge_range_set(out)' to restore range-set invariants\nand ensure that neighboring ranges are coalesced. Not only does that\nresolve the crash and other weird behavior, but it means you don't\nhave to add a special-case to range_set_append(), thus the fix becomes\nsimpler overall.\n\nAside from simplicity, I think the suggested use of\nrange_set_append_unsafe() and sort_and_merge_range_set() _is_ the\ncorrect fix anyhow because this code isn't taking care to ensure that\nthe range, after applying 'offset', doesn't abut or overlap with an\nearlier range, and sort_and_merge_range_set() is meant to be used\nexactly in cases like this when invariants may be broken.\n\nSo, while the suggested fix is simpler and \"better\" and fixes the\ncrash, that doesn't necessarily mean that the values computed here are\nactually correct. As noted, I'm still trying to grok the computation\nof these values, but that's a separate issue from the crash itself.\n"},{"id":"354543","messageId":"CAPig+cRoQB6Az=sYB_tjhOLewJyMzYAwqNxPh99a3aZFhzDcYg@mail.gmail.com","threadId":"49037","inReplyTo":"9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com","subject":"Re: [PATCH 3/4] line-log: optimize ranges by joining them when possible","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-05T10:31:02Z","receivedAt":"2018-08-05T10:31:15Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"> On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:\n> > Technically, it is okay to have line ranges that touch (i.e. the end of\n> > the first range ends just before the next range begins). However, it is\n> > inefficient, and when the user provides such touching ranges via\n> > multiple `-L` options, we already join them.\n> >\n> > void range_set_append(struct range_set *rs, long a, long b)\n> > {\n> > + if (rs->nr > 0 && rs->ranges[rs->nr-1].end + 1 == a) {\n> > + rs->ranges[rs->nr-1].end = b;\n> > + return;\n> > + }\n>\n> As I understand it, this patch attempts to make range_set_append extend\n> the last range in the range set to include [a,b), if [a,b) \"touches\" the\n> last range in rs.\n> It seems that the first condition in range_set_append should be:\n>\n> if (rs->nr > 0 && rs->ranges[rs->nr-1].end == a) {\n\nI agree that this patch has an off-by-1 bug. 'end' is not included in\nthe previous range, so it should not be adding 1 to end before\nchecking against 'a'.\n\n*However*, as mentioned in my review[1] of 2/4, the special-case added\nby this patch is unnecessary, so this patch should be scrapped.\n\n> With these consideration in mind the assert should become\n>\n> assert(rs->nr == 0 || rs->ranges[rs->nr-1].end < a);\n\nAgreed. The existing assertion() has an off-by-1 error.\nrange_set_append() is supposed to add a range _without_ breaking the\ninvariant that no two ranges can abut, and the assertion() was\nsupposed to protect against that. The existing \"<= a\" incorrectly\nallows the new range to abut an existing one, whereas the proposed \"<\na\" doesn't.\n\n(For adding abutting or overlapping ranges, range_set_append_unsafe()\nfollowed, at some point, by sort_and_merge_range_set() is the\nrecommended alternative to the more strict range_set_append().)\n\n[1]: https://public-inbox.org/git/CAPig+cRWcFVbA76_HT2iVD16bsUmbWdCgk_07rmiGneM5czdOQ@mail.gmail.com/\n"},{"id":"354544","messageId":"CAPig+cS-b973NzRvvcKyx6t5ChO_VDf=Bs8zoE-B_iPa3HWv5g@mail.gmail.com","threadId":"49037","inReplyTo":"pull.15.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/4] line-log: be more careful when adjusting multiple line ranges","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-05T10:39:13Z","receivedAt":"2018-08-05T10:39:26Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Aug 4, 2018 at 6:18 PM Johannes Schindelin via GitGitGadget\n wrote:\n> Now, I am fairly certain that the changes are correct, but given my track\n> record with off-by-one bugs (and once even an off-by-two bug), I would\n> really appreciate some thorough review of this code, in particular the\n> second one that is the actual bug fix. I am specifically interested in\n> reviews from people who know line-log.c pretty well and can tell me whether\n> the src[i].end > target[j].end is correct, or whether it should actually\n> have been a >= (I tried to wrap my head around this, but I would feel more\n> comfortable if a domain expert would analyze this, whistling, and looking\n> Eric's way).\n\nAlthough I fixed a number of bugs in basic range-set manipulation code\n(5 years ago), I have no experience with or knowledge of the code\nactually dealing with range-set manipulation in relation to diffs, so\nI'm not a domain expert by any means, and I'm _still_ trying to wrap\nmy head around that code.\n\nThat said, I left some comments on the individual patches suggesting a\nsimpler and more correct fix for the crash. (Despite that suggestion\nfor fixing the crash, I still can't say whether the actual\ncomputations performed by the existing code are correct, since I still\ndon't understand that aspect of it.)\n"},{"id":"354545","messageId":"CAPig+cRrC2mf1uuQ1C4Ue4OMZQbgcxXbJ9AXs0y6RSnUrcm7Dg@mail.gmail.com","threadId":"49037","inReplyTo":"faf35214f0f339b792a30a3bd013056217d9a2c1.1533421101.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/4] line-log: convert an assertion to a full BUG() call","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-05T10:42:44Z","receivedAt":"2018-08-05T10:42:57Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Aug 4, 2018 at 6:18 PM Johannes Schindelin via GitGitGadget\n wrote:\n> The assertion in question really indicates a bug, when triggered, so we\n> might just as well use the sanctioned method to report it.\n>\n> Signed-off-by: Johannes Schindelin \n> ---\n> diff --git a/line-log.c b/line-log.c\n> @@ -72,7 +72,9 @@ void range_set_append(struct range_set *rs, long a, long b)\n> - assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n> + if (rs->nr > 0 && rs->ranges[rs->nr-1].end > a)\n> + BUG(\"append %ld-%ld, after %ld-%ld?!?\", a, b,\n> + rs->ranges[rs->nr-1].start, rs->ranges[rs->nr-1].end);\n\nAlthough this appears to be a faithful translation of the assert() to\nBUG(), as mentioned by Andrei in his review of 3/4, the existing\nassert() seems to have an off-by-1 error, which means that the \"> a\"\nhere really ought to be \">= a\".\n\nGiven that this file is full of assert()'s, it doesn't necessarily\nmake sense to convert only this one, so perhaps the patch should be\ndropped (since I'm guessing you don't want to convert the rest of\nthem).\n"},{"id":"354546","messageId":"CAPig+cSon7opZ-pOZT-6O31upD5pRGhaz7-1xDuT6R5VrL54ng@mail.gmail.com","threadId":"49037","inReplyTo":"CAPig+cRWcFVbA76_HT2iVD16bsUmbWdCgk_07rmiGneM5czdOQ@mail.gmail.com","subject":"Re: [PATCH 2/4] line-log: adjust start/end of ranges individually","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-05T10:57:42Z","receivedAt":"2018-08-05T10:57:55Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sun, Aug 5, 2018 at 6:14 AM Eric Sunshine wrote:\n> Having said that, a much easier fix is to use\n> range_set_append_unsafe() here, and then at the bottom of the loop,\n> invoke 'sort_and_merge_range_set(out)' to restore range-set invariants\n\nBy \"bottom\", I meant \"outside\" or \"after\":\n\n ...and then invoke sort_and_merge_range_set()\n after the loop to restore range-set invariants.\n"},{"id":"354596","messageId":"nycvar.QRO.7.76.6.1808061216060.71@tvgsbejvaqbjf.bet","threadId":"49037","inReplyTo":"20180805015908.GE258270@aiede.svl.corp.google.com","subject":"Re: [PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-08-06T10:27:40Z","receivedAt":"2018-08-06T10:27:47Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jonathan,\n\nOn Sat, 4 Aug 2018, Jonathan Nieder wrote:\n\n> Johannes Schindelin wrote:\n> \n> > Currently, this test case throws an assertion:\n> >\n> > \tAssertion failed!\n> >\n> > \tProgram: git.exe\n> > \tFile: line-log.c, Line 71\n> >\n> > Signed-off-by: Johannes Schindelin \n> > ---\n> > t/t4211-line-log.sh | 17 +++++++++++++++++\n> > 1 file changed, 17 insertions(+)\n> \n> Thanks for finding and demonstrating it.\n\nYou're welcome.\n\n> Can you say more about what is going on in the test case?\n\nCertainly. I considered writing more into the commit message, but all my\nattempts were really repeating what the test case does, and were therefore\npoor commit message material.\n\nUnder certain circumstances, multiple ranges specified for the line-log\nwere adjusted incorrectly, leading to violation of assumptions as well as\nto segmentation faults. This test case demonstrates this.\n\n> Alternatively, could it be squashed in with the patch that fixes it?\n\nThere is this really awful trend on this mailing list to suggest\nconflating the demonstration of a bug with the bug fix.\n\nIt is really, really important to realize how valuable it is to have the\nregression test as an individual patch that can be used to verify that\nthere is a bug, to pinpoint where it was introduced, to test alternative\nfixes, to keep records separate, and I could go on and on and on. Please\ndo not ignore these very good reasons, and please refrain from\nrecommending such conflation in the future.\n\n> The below will be more nitpicky:\n> \n> [...]\n> > --- a/t/t4211-line-log.sh\n> > +++ b/t/t4211-line-log.sh\n> > @@ -115,4 +115,21 @@ test_expect_success 'range_set_union' '\n> > \tgit log $(for x in $(test_seq 200); do echo -L $((2*x)),+1:c.c; done)\n> > '\n> > \n> > +q_to_lf () {\n> > +\ttr Q '\\012'\n> > +}\n> > +\n> > +test_expect_failure 'close to overlapping ranges' '\n> > +\ttest_seq 5 >a1.c &&\n> > +\tgit add a1.c &&\n> > +\tgit commit -m \"5 lines\" a1.c &&\n> \n> It would be nice to use test_tick or test_commit for a more realistic\n> history (with time marching forward).\n\nAs far as this test is concerned, that realism is not necessary, and comes\nat the cost of readability.\n\n> > +\tsed s/3/3QaQb/ tmp &&\n> > +\tmv tmp a1.c &&\n> > +\tgit commit -m \"2 more lines\" a1.c &&\n> \n> It's probably just me, but the bit with Q makes it hard for me to\n> follow. Maybe there's a simpler way?\n\nMaybe. I did not find it, else I would have used it.\n\n> \"sed -e '3aa' -e '3ab'\" works here, but I don't know how portable it\n> is.\n\nMy experience with BSD sed and the `a` command made me highly suspicious,\nthat's why I did not go down that route.\n\nBesides, that `sed` invocation does not really look intuitive either.\n\n> I'd be more tempted to do\n> \n> \ttest_write_lines 1 2 3 4 5 >a1.c &&\n> \t...\n> \n> \ttest_write_lines 1 2 3 a b 4 5 >a1.c &&\n> \t...\n> \n> \ttest_write_lines 1 2 3 a b c 4 5 >a1.c &&\n> \t...\n> \n> which is concise and has obvious behavior.\n\nThat works for me!\n\nCiao,\nDscho\n"},{"id":"354598","messageId":"nycvar.QRO.7.76.6.1808061232120.71@tvgsbejvaqbjf.bet","threadId":"49037","inReplyTo":"CAPig+cRWcFVbA76_HT2iVD16bsUmbWdCgk_07rmiGneM5czdOQ@mail.gmail.com","subject":"Re: [PATCH 2/4] line-log: adjust start/end of ranges individually","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-08-06T12:52:06Z","receivedAt":"2018-08-06T12:52:14Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Eric,\n\nOn Sun, 5 Aug 2018, Eric Sunshine wrote:\n\n> On Sat, Aug 4, 2018 at 6:18 PM Johannes Schindelin via GitGitGadget\n> wrote:\n> > When traversing commits and adjusting the ranges, things can get really\n> > tricky. For example, when the line range of interest encloses several\n> > hunks of a commit, the line range can actually shrink.\n> >\n> > Currently, range_set_shift_diff() does not anticipate that scenario and\n> > blindly adjusts start and end by the same offset (\"shift\" the range).\n> > [...]\n> > Let's fix this by adjusting the start and the end offsets individually.\n> >\n> > Signed-off-by: Johannes Schindelin \n> > ---\n> > diff --git a/line-log.c b/line-log.c\n> > @@ -438,7 +438,13 @@ static void range_set_shift_diff(struct range_set *out,\n> > - (target[j].end-target[j].start);\n> > j++;\n> > }\n> > - range_set_append(out, src[i].start+offset, src[i].end+offset);\n> > + start_offset = offset;\n> > + while (j < diff->target.nr && src[i].end > target[j].end) {\n> > + offset += (parent[j].end-parent[j].start)\n> > + - (target[j].end-target[j].start);\n> > + j++;\n> > + }\n> > + range_set_append(out, src[i].start+start_offset, src[i].end+offset);\n> \n> I'm still trying to wrap my head around the original code, so I'm not\n> even at the point of being able to say if this fix is correct. What\n> happens if the \"start_offset\" loop consumes all of 'j' before it even\n> gets to the new loop?\n\nFirst of all, it is not really the `start_offset` loop, but more like the\n\"end_offset loop\": we are still adjusting `offset`, and that is what we\nuse to adjust the end of the current line range, while we take pains to\nkeep the offset that needs to be used for the start of said line range.\n\n> Why does the new loop use '>' whereas the existing uses '>='?\n\nAs a mathematician, I usually think of intervals as inclusive only on one\nend. So I intuitively use the non-inclusive comparison on the other end.\n\nIn this instance, the first loop tries to make sure that the offset to be\nused for the start offset has taken into account all of the relevant diff\nhunks (meaning: the diff hunks whose target lines start before src[i],\ni.e. the current line range to adjust).\n\nThe second loop, however, tries to make sure that the offset to adjust the\n*end* of the current line range.\n\nHence what I wrote.\n\nBut now that I think about it again, I am no longer sure that the first\nloop (the one I did not change) is sound, to begin with. Let's imagine a\nvery simple case, where we try to adjust a start line, say, 100, and the\ndiff has a hunk with header `@@ -90,20 +90,40 @@`. So the start line lies\nsomewhere around a quarter into the post-image.\n\nThe current line-log code adjusts this by a very crude method: since the\nline number lies between the post-image's start, it is adjusted by adding\nthe length of the pre-image and subtracting the length of the post image,\ni.e. 20 - 40. The result is that we pretend that it came from line number\n80, which is squarely outside the pre-image range.\n\nThat method of adjustment is appropriate for lines *outside* the\npost-image range, of course. If we had looked at line 140 (which is 10\nlines after the post-image), then it would be totally correct to say that\nit came from line 120.\n\nBut that method is pretty obviously broken for any line that lies *within*\na post-image.\n\nSo I think the entire loop is in dear need of adjustment.\n\nThe question is: how should it be adjusted? The safest way would be to\nadjust start and end of the line range differently, where start is pulled\nback to the pre-image's start (in the above example, 90), and end is\npushed up to the pre-image's end (in the above example, 110).\n\nOf course, this has a slightly unintuitive consequence: imagine that some\ncommit made a block of, say, 20 lines a conditional one. Like,\n\n\t/* Some comment */\n\tdo_something = 1;\n\t...\n\tprint_it();\n\t...\n\ncould have become\n\n\tif (!dry_run) {\n\t\t/* Some comment */\n\t\tdo_something = 1;\n\t\t...\n\t\tprint_it();\n\t\t...\n\t}\n\nIf you use my proposed method to adjust the line ranges to figure out the\nhistory of that `print_it()` line, this commit would blow up the line\nrange to the entire conditional block, which is probably not what you\nwanted.\n\nI don't really see a better way, though.\n\n> Having said that, a much easier fix is to use range_set_append_unsafe()\n> here, and then at the bottom of the loop, invoke\n> 'sort_and_merge_range_set(out)' to restore range-set invariants and\n> ensure that neighboring ranges are coalesced. Not only does that resolve\n> the crash and other weird behavior, but it means you don't have to add a\n> special-case to range_set_append(), thus the fix becomes simpler\n> overall.\n\nThat would only paper over the bug, as the line range is adjusted\nincorrectly. It really is.\n\nWhen looking at a line range, say, 90--110, and traversing a commit that\nadded 5 lines from line 100-105, then the end and the start of that line\nrange really need to be adjusted independently. In this example, the start\nwould not even budge, but the end would need to be adjusted to 105.\n\nThe current code would adjust neither because the start of the line range\nis outside of the post-image range.\n\nNo amount of restoring invariants can make up for that incorrect\nadjustment.\n\n> Aside from simplicity, I think the suggested use of\n> range_set_append_unsafe() and sort_and_merge_range_set() _is_ the\n> correct fix anyhow because this code isn't taking care to ensure that\n> the range, after applying 'offset', doesn't abut or overlap with an\n> earlier range, and sort_and_merge_range_set() is meant to be used\n> exactly in cases like this when invariants may be broken.\n> \n> So, while the suggested fix is simpler and \"better\" and fixes the\n> crash, that doesn't necessarily mean that the values computed here are\n> actually correct. As noted, I'm still trying to grok the computation\n> of these values, but that's a separate issue from the crash itself.\n\nI think sort_and_merge_range_set() is fine for \"Postelizing user input\"\n(Postel's law: be stringent in your output and lenient in your input,\nsomething we should also heed in general, not only in our code).\n\nBut I don't think our code should need it. If the line ranges need to\nresort to re-sorting (pun intended), that smells a lot like a bug.\n\nAnd the only way those ranges could be merged is when they start to touch\n(like in the test case I provided, when the lines 1, 2, 3 and the lines 4,\n5, become a single line range because a, b and then c, are removed from\nthe original 1, 2, 3, a, b, c, 4, 5). And my suggested fix makes that\nchange quite elegantly, while appending line ranges (which will work\ncorrectly if done in the correct order, which should always be the case\nbecause both our line ranges as well as the diff hunks are ordered).\n\nWhat do you think about my proposed change to adjust start and end?\n\nCiao,\nDscho\n"},{"id":"354600","messageId":"nycvar.QRO.7.76.6.1808061510260.71@tvgsbejvaqbjf.bet","threadId":"49037","inReplyTo":"CAPig+cRrC2mf1uuQ1C4Ue4OMZQbgcxXbJ9AXs0y6RSnUrcm7Dg@mail.gmail.com","subject":"Re: [PATCH 4/4] line-log: convert an assertion to a full BUG() call","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-08-06T13:14:53Z","receivedAt":"2018-08-06T13:15:02Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Eric,\n\nOn Sun, 5 Aug 2018, Eric Sunshine wrote:\n\n> On Sat, Aug 4, 2018 at 6:18 PM Johannes Schindelin via GitGitGadget\n> wrote:\n> > The assertion in question really indicates a bug, when triggered, so we\n> > might just as well use the sanctioned method to report it.\n> >\n> > Signed-off-by: Johannes Schindelin \n> > ---\n> > diff --git a/line-log.c b/line-log.c\n> > @@ -72,7 +72,9 @@ void range_set_append(struct range_set *rs, long a, long b)\n> > - assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n> > + if (rs->nr > 0 && rs->ranges[rs->nr-1].end > a)\n> > + BUG(\"append %ld-%ld, after %ld-%ld?!?\", a, b,\n> > + rs->ranges[rs->nr-1].start, rs->ranges[rs->nr-1].end);\n> \n> Although this appears to be a faithful translation of the assert() to\n> BUG(), as mentioned by Andrei in his review of 3/4, the existing\n> assert() seems to have an off-by-1 error, which means that the \"> a\"\n> here really ought to be \">= a\".\n\nI think Andrei's assessment is wrong. The code could not test for that\nearlier, as it did allow ranges to become \"abutting\" in the process, by\nfailing to merge them. So the invariant you talked about is more of an\ninvariant for the initial state.\n\nMy 3/4 would make that invariant heeded throughout the process.\n\nI am still keen on keeping the invariants straight *without* resorting to\ndirty tricks like calling sort_and_merge. Calling that function would just\nmake it easier for bugs to hide in this code.\n\n> Given that this file is full of assert()'s, it doesn't necessarily\n> make sense to convert only this one, so perhaps the patch should be\n> dropped (since I'm guessing you don't want to convert the rest of\n> them).\n\nSure, there are 18 of them, and you're right, I lack the time to convert\nthem.\n\nCiao,\nDscho\n"},{"id":"354613","messageId":"20180806144726.GB97564@aiede.svl.corp.google.com","threadId":"49037","inReplyTo":"nycvar.QRO.7.76.6.1808061216060.71@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-08-06T14:47:26Z","receivedAt":"2018-08-06T14:47:31Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Dscho,\n\nJohannes Schindelin wrote:\n> On Sat, 4 Aug 2018, Jonathan Nieder wrote:\n\n>> Alternatively, could it be squashed in with the patch that fixes it?\n>\n> There is this really awful trend on this mailing list to suggest\n> conflating the demonstration of a bug with the bug fix.\n>\n> It is really, really important to realize how valuable it is to have the\n> regression test as an individual patch that can be used to verify that\n> there is a bug, to pinpoint where it was introduced, to test alternative\n> fixes, to keep records separate, and I could go on and on and on. Please\n> do not ignore these very good reasons, and please refrain from\n> recommending such conflation in the future.\n\nIf you want to propose changing the project's style to always separate\ntests from the patch that fixes a bug, that's a discussion we can have,\nin a separate thread.\n\nToday, we do allow and encourage putting the test with the patch that\nfixes it, and that has real advantages:\n\n- the tests are easier to understand when found with \"git log\" because\n they are in context\n\n- as the patch evolves, it is easier to remember to update the test at\n the same time\n\n- newcomers imitating existing patches have a clear hint to write\n tests\n\n- the beginning of a patch series can be applied and merged down while\n the end is still under review, without either leaving out the tests\n or applying a test that doesn't pass and accomplishes little\n\nI've never found it difficult to use the test from a patch to verify\nthat there is a bug or pinpoint where it was introduced. Tests are\nseparate from the application code since they're in the t/ directory;\nthis is a very easy thing to do. That isn't to say that a patch that\nonly adds a (passing or expected-failure) test isn't valuable, even\nwithout a fix. It is valuable, precisely when it is self-explanatory.\n\nMore importantly, I am a bit surprised that instead of accepting the\nfeedback, you are basically calling a reviewer complicit, for pointing\nout a pretty normal possible improvement that follows the project's\nconventions.\n\nI'm beyond words.\n\nJonathan\n"},{"id":"354626","messageId":"20180806153305.GA105466@aiede.svl.corp.google.com","threadId":"49037","inReplyTo":"20180806144726.GB97564@aiede.svl.corp.google.com","subject":"Re: [PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-08-06T15:33:05Z","receivedAt":"2018-08-06T15:33:09Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Nieder wrote:\n> Johannes Schindelin wrote:\n\n>> It is really, really important to realize how valuable it is to have the\n>> regression test as an individual patch that can be used to verify that\n>> there is a bug, to pinpoint where it was introduced, to test alternative\n>> fixes, to keep records separate, and I could go on and on and on. Please\n>> do not ignore these very good reasons, and please refrain from\n>> recommending such conflation in the future.\n>\n> If you want to propose changing the project's style to always separate\n> tests from the patch that fixes a bug, that's a discussion we can have,\n> in a separate thread.\n\nBy the way, don't get me wrong: I am sympathetic to the motivation for\nsuch a change.\n\nI have worked on projects where tests were in a separate repository\nfrom the application. There are costs and benefits. To support the\nkind of use cases you're describing, the tests would include\nconditionals to allow running on old versions of the application (the\ntest expectations were based on the latest version, but setup code\nsometimes had to accomodate differences between versions). It worked\nokay and was probably worth it for that project, despite the added\nfriction. It's not clear it would be worth it for Git.\n\nJonathan\n"},{"id":"354718","messageId":"CAPig+cQU-mcUBJGHeZjKeta0_ve8WMr_KL1ToO9j-d=-hS1a=w@mail.gmail.com","threadId":"49037","inReplyTo":"nycvar.QRO.7.76.6.1808061510260.71@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 4/4] line-log: convert an assertion to a full BUG() call","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-07T09:09:57Z","receivedAt":"2018-08-07T09:10:10Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Mon, Aug 6, 2018 at 9:15 AM Johannes Schindelin\n wrote:\n> On Sun, 5 Aug 2018, Eric Sunshine wrote:\n> > Although this appears to be a faithful translation of the assert() to\n> > BUG(), as mentioned by Andrei in his review of 3/4, the existing\n> > assert() seems to have an off-by-1 error, which means that the \"> a\"\n> > here really ought to be \">= a\".\n>\n> I think Andrei's assessment is wrong. The code could not test for that\n> earlier, as it did allow ranges to become \"abutting\" in the process, by\n> failing to merge them. So the invariant you talked about is more of an\n> invariant for the initial state.\n\nI'm having trouble interpreting your response.\n\nMy understanding is that range_set_append() is intended to be strict\nby not allowing addition of a range which abuts an existing range\n(although, of course, the assert() checks only the last range, so it's\nnot full-proof). Assuming that to be correct, then the assertion\ncontains a one-off-error (according to my reasoning).\n\nI'm sensing from your reply that you seem to have a different idea\nabout range_set_append()'s intended use.\n\n> My 3/4 would make that invariant heeded throughout the process.\n>\n> I am still keen on keeping the invariants straight *without* resorting to\n> dirty tricks like calling sort_and_merge. Calling that function would just\n> make it easier for bugs to hide in this code.\n\nIndeed, avoiding the \"dirty trick\" would be ideal, although, I still\nhaven't wrapped my head around it enough to be able to say whether the\ncomputed offset, when applied to the range in question, could cause\nthat range to abut or overlap an existing range.\n\n(There are, of course, valid uses for range_set_append_unsafe() /\nsort_and_merge(), such as allowing -L options to overlap and be\nspecified in any order. Batch-adding them to the range-set via\nrange_set_append_unsafe() and letting sort_and_merge() sort them all\nout is plenty sensible.)\n"},{"id":"354775","messageId":"CAPig+cTBUCytuqMZAZshPNzJ28s_vhWNKawamt1=EtNZVcYJsg@mail.gmail.com","threadId":"49037","inReplyTo":"CAPig+cQU-mcUBJGHeZjKeta0_ve8WMr_KL1ToO9j-d=-hS1a=w@mail.gmail.com","subject":"Re: [PATCH 4/4] line-log: convert an assertion to a full BUG() call","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-08-07T22:00:47Z","receivedAt":"2018-08-07T22:01:03Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Aug 7, 2018 at 5:09 AM Eric Sunshine wrote:\n> On Mon, Aug 6, 2018 at 9:15 AM Johannes Schindelin\n> wrote:\n> > I think Andrei's assessment is wrong. The code could not test for that\n> > earlier, as it did allow ranges to become \"abutting\" in the process, by\n> > failing to merge them. So the invariant you talked about is more of an\n> > invariant for the initial state.\n>\n> My understanding is that range_set_append() is intended to be strict\n> by not allowing addition of a range which abuts an existing range\n> (although, of course, the assert() checks only the last range, so it's\n> not full-proof).\n\nIgnore my parenthetical comment. It is clearly wrong.\n\nLooking at this again, I see that there is some confusion. The comment\nin line-log.h says:\n\n /* New range must begin at or after end of last added range */\n void range_set_append(struct range_set *, long start, long end);\n\nHowever, that comment was added by me in c0babbe695 (range-set:\npublish API for re-use by git-blame -L, 2013-08-06) -- five years and\none day ago -- and it appears to be based upon a direct interpretation\nof the condition in the assert(), including its off-by-one error.\n\n*But*, one of the invariants of range-set is that the ranges must\n_not_ abut one another, so the \"at or after\" is wrong; it should say\ninstead something like \"after, and not touching, the end of the last\nadded range\".\n\nThat invariant about having a gap between ranges is enforced\ndeliberately by range_set_check_invariants(). It's also signaled\nimplicitly by the fact that no callers of range_set_append() ever\ninvoke sort_and_merge_range_set() after calling range_set_append().\n"}]}