{"thread":{"id":"34386","subject":"[PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another","startedAt":"2013-07-09T05:55:03Z","lastAt":"2013-07-09T09:31:49Z","messageCount":4,"participants":["Eric Sunshine","Thomas Rast"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"222886","messageId":"1373349305-63917-1-git-send-email-sunshine@sunshineco.com","threadId":"34386","inReplyTo":null,"subject":"[PATCH v2 0/2] fix broken range_set tests and coalescing","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-07-09T05:55:03Z","receivedAt":"2013-07-09T05:55:03Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"This is a re-roll of a patch [1] which fixes the\nline-log.c:sort_and_merge_range_set() coalescing bug.  This re-roll\ninserts a new patch before the lone patch from v1.\n\npatch 1/2: Fix broken tests in t4211 which should have detected the\n    sort_and_merge_range_set() bug but didn't due to incorrect\n    \"expected\" state. Mark the tests as expect-failure.\n\npatch 2/2: Fix the sort_and_merge_range_set() coalesce bug. Same as v1\n    but also flips the tests to expect-success.\n\n[1]: http://article.gmane.org/gmane.comp.version-control.git/229774\n\nEric Sunshine (2):\n  t4211: fix broken test when one -L range is subset of another\n  range_set: fix coalescing bug when range is a subset of another\n\n line-log.c                       |   3 +-\n t/t4211/expect.multiple-superset | 134 ++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 133 insertions(+), 4 deletions(-)\n\n-- \n1.8.3.2\n"},{"id":"222885","messageId":"1373349305-63917-2-git-send-email-sunshine@sunshineco.com","threadId":"34386","inReplyTo":"1373349305-63917-1-git-send-email-sunshine@sunshineco.com","subject":"[PATCH v2 1/2] t4211: fix broken test when one -L range is subset of another","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-07-09T05:55:04Z","receivedAt":"2013-07-09T05:55:04Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"t4211 attempts to test multiple git-log -L ranges where one range is a\nsuperset of the other, and falsely succeeds because its \"expected\"\noutput is incorrect.\n\nOverlapping -L ranges handed to git-log are coalesced by\nline-log.c:sort_and_merge_range_set() into a set of non-overlapping,\ndisjoint ranges. When one range is a subset of another,\nsort_and_merge_range_set() should coalesce both ranges to the superset\nrange, but instead the coalesced range often is incorrectly truncated to\nthe end of the subset range. For example, ranges 2-8 and 3-4 are\ncoalesced incorrectly to 2-4.\n\nOne can observe this incorrect behavior with git-log -L using the test\nrepository created by t4211. The superset/subset ranges t4211 employs\nare 4-$ and 8-12 (where $ represents end-of-file). The coalesced range\nshould be 4-$. Manually invoking git-log with the same ranges the test\nemploys, we see:\n\n  % git log -L 4:a.c simple |\n    awk '/^commit [0-9a-f]{40}/ { print substr($2,1,7) }'\n  4659538\n  100b61a\n  39b6eb2\n  a6eb826\n  f04fb20\n  de4c48a\n\n  % git log -L 8,12:a.c simple | awk ...\n  f04fb20\n  de4c48a\n\n  % git log -L 4:a.c -L 8,12:a.c simple | awk ...\n  a6eb826\n  f04fb20\n  de4c48a\n\nThis last output is incorrect. 8-12 is a subset of 4-$, hence the output\nof the coalesced range should be the same as the 4-$ output shown first.\nIn fact, the above incorrect output is the truncated bogus range 4-12:\n\n  % git log -L 4,12:a.c simple | awk ...\n  a6eb826\n  f04fb20\n  de4c48a\n\nFix the test to correctly fail in the presence of the\nsort_and_merge_range_set() coalescing bug. Do so by changing the\n\"expected\" output to the commits mentioned in the 4-$ output above.\n\nSigned-off-by: Eric Sunshine <sunshine@sunshineco.com>\n---\n t/t4211-line-log.sh              |   4 +-\n t/t4211/expect.multiple-superset | 134 ++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 133 insertions(+), 5 deletions(-)\n\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 7776f93..549df9e 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -50,8 +50,8 @@ canned_test \"-M -L ':f:b.c' parallel-change\" parallel-change-f-to-main\n canned_test \"-L 4,12:a.c -L :main:a.c simple\" multiple\n canned_test \"-L 4,18:a.c -L :main:a.c simple\" multiple-overlapping\n canned_test \"-L :main:a.c -L 4,18:a.c simple\" multiple-overlapping\n-canned_test \"-L 4:a.c -L 8,12:a.c simple\" multiple-superset\n-canned_test \"-L 8,12:a.c -L 4:a.c simple\" multiple-superset\n+canned_test_failure \"-L 4:a.c -L 8,12:a.c simple\" multiple-superset\n+canned_test_failure \"-L 8,12:a.c -L 4:a.c simple\" multiple-superset\n \n test_bad_opts \"-L\" \"switch.*requires a value\"\n test_bad_opts \"-L b.c\" \"argument.*not of the form\"\ndiff --git a/t/t4211/expect.multiple-superset b/t/t4211/expect.multiple-superset\nindex a1f5bc4..d930b6e 100644\n--- a/t/t4211/expect.multiple-superset\n+++ b/t/t4211/expect.multiple-superset\n@@ -1,3 +1,100 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast <trast@student.ethz.ch>\n+Date:   Thu Feb 28 10:48:43 2013 +0100\n+\n+    change back to complete line\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -4,19 +4,21 @@\n+ long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+ \n+ /*\n+  * This is only an example!\n+  */\n+ \n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n+\\ No newline at end of file\n++}\n++\n++/* incomplete lines are bad! */\n+\n+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c\n+Author: Thomas Rast <trast@student.ethz.ch>\n+Date:   Thu Feb 28 10:48:10 2013 +0100\n+\n+    change to an incomplete line at end\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -4,19 +4,19 @@\n+ long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+ \n+ /*\n+  * This is only an example!\n+  */\n+ \n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n++}\n+\\ No newline at end of file\n+\n+commit 39b6eb2d5b706d3322184a169f666f25ed3fbd00\n+Author: Thomas Rast <trast@student.ethz.ch>\n+Date:   Thu Feb 28 10:45:41 2013 +0100\n+\n+    touch comment\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,19 +3,19 @@\n+ long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+ \n+ /*\n+- * A comment.\n++ * This is only an example!\n+  */\n+ \n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+ }\n+\n commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n Author: Thomas Rast <trast@student.ethz.ch>\n Date:   Thu Feb 28 10:45:16 2013 +0100\n@@ -7,7 +104,7 @@ Date:   Thu Feb 28 10:45:16 2013 +0100\n diff --git a/a.c b/a.c\n --- a/a.c\n +++ b/a.c\n-@@ -3,9 +3,9 @@\n+@@ -3,19 +3,19 @@\n -int f(int x)\n +long f(long x)\n  {\n@@ -18,6 +115,17 @@ diff --git a/a.c b/a.c\n  \t}\n  \treturn s;\n  }\n+ \n+ /*\n+  * A comment.\n+  */\n+ \n+ int main ()\n+ {\n+-\tprintf(\"%d\\n\", f(15));\n++\tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+ }\n \n commit f04fb20f2c77850996cba739709acc6faecc58f7\n Author: Thomas Rast <trast@student.ethz.ch>\n@@ -28,7 +136,7 @@ Date:   Thu Feb 28 10:44:55 2013 +0100\n diff --git a/a.c b/a.c\n --- a/a.c\n +++ b/a.c\n-@@ -3,8 +3,9 @@\n+@@ -3,18 +3,19 @@\n  int f(int x)\n  {\n  \tint s = 0;\n@@ -38,6 +146,16 @@ diff --git a/a.c b/a.c\n  \t}\n +\treturn s;\n  }\n+ \n+ /*\n+  * A comment.\n+  */\n+ \n+ int main ()\n+ {\n+ \tprintf(\"%d\\n\", f(15));\n+ \treturn 0;\n+ }\n \n commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n Author: Thomas Rast <trast@student.ethz.ch>\n@@ -48,7 +166,7 @@ Date:   Thu Feb 28 10:44:48 2013 +0100\n diff --git a/a.c b/a.c\n --- /dev/null\n +++ b/a.c\n-@@ -0,0 +3,8 @@\n+@@ -0,0 +3,18 @@\n +int f(int x)\n +{\n +\tint s = 0;\n@@ -57,3 +175,13 @@ diff --git a/a.c b/a.c\n +\t\ts++;\n +\t}\n +}\n++\n++/*\n++ * A comment.\n++ */\n++\n++int main ()\n++{\n++\tprintf(\"%d\\n\", f(15));\n++\treturn 0;\n++}\n-- \n1.8.3.2\n"},{"id":"222884","messageId":"1373349305-63917-3-git-send-email-sunshine@sunshineco.com","threadId":"34386","inReplyTo":"1373349305-63917-1-git-send-email-sunshine@sunshineco.com","subject":"[PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-07-09T05:55:05Z","receivedAt":"2013-07-09T05:55:05Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"When coalescing ranges, sort_and_merge_range_set() unconditionally\nassumes that the end of a range being folded into a preceding range\nshould become the end of the coalesced range. This assumption, however,\nis invalid when one range is a subset of another.  For example, given\nranges 1-5 and 2-3 added via range_set_append_unsafe(),\nsort_and_merge_range_set() incorrectly coalesces them to range 1-3\nrather than the correct union range 1-5. Fix this bug.\n\nSigned-off-by: Eric Sunshine <sunshine@sunshineco.com>\n---\n line-log.c          | 3 ++-\n t/t4211-line-log.sh | 4 ++--\n 2 files changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 4bbb09b..8cc29a0 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -116,7 +116,8 @@ static void sort_and_merge_range_set(struct range_set *rs)\n \n \tfor (i = 1; i < rs->nr; i++) {\n \t\tif (rs->ranges[i].start <= rs->ranges[o-1].end) {\n-\t\t\trs->ranges[o-1].end = rs->ranges[i].end;\n+\t\t\tif (rs->ranges[o-1].end < rs->ranges[i].end)\n+\t\t\t\trs->ranges[o-1].end = rs->ranges[i].end;\n \t\t} else {\n \t\t\trs->ranges[o].start = rs->ranges[i].start;\n \t\t\trs->ranges[o].end = rs->ranges[i].end;\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 549df9e..7776f93 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -50,8 +50,8 @@ canned_test \"-M -L ':f:b.c' parallel-change\" parallel-change-f-to-main\n canned_test \"-L 4,12:a.c -L :main:a.c simple\" multiple\n canned_test \"-L 4,18:a.c -L :main:a.c simple\" multiple-overlapping\n canned_test \"-L :main:a.c -L 4,18:a.c simple\" multiple-overlapping\n-canned_test_failure \"-L 4:a.c -L 8,12:a.c simple\" multiple-superset\n-canned_test_failure \"-L 8,12:a.c -L 4:a.c simple\" multiple-superset\n+canned_test \"-L 4:a.c -L 8,12:a.c simple\" multiple-superset\n+canned_test \"-L 8,12:a.c -L 4:a.c simple\" multiple-superset\n \n test_bad_opts \"-L\" \"switch.*requires a value\"\n test_bad_opts \"-L b.c\" \"argument.*not of the form\"\n-- \n1.8.3.2\n"},{"id":"222893","messageId":"8738rogjui.fsf@linux-k42r.v.cablecom.net","threadId":"34386","inReplyTo":"1373349305-63917-3-git-send-email-sunshine@sunshineco.com","subject":"Re: [PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-07-09T09:31:49Z","receivedAt":"2013-07-09T09:31:49Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Eric Sunshine <sunshine@sunshineco.com> writes:\n\n> When coalescing ranges, sort_and_merge_range_set() unconditionally\n> assumes that the end of a range being folded into a preceding range\n> should become the end of the coalesced range. This assumption, however,\n> is invalid when one range is a subset of another.  For example, given\n> ranges 1-5 and 2-3 added via range_set_append_unsafe(),\n> sort_and_merge_range_set() incorrectly coalesces them to range 1-3\n> rather than the correct union range 1-5. Fix this bug.\n>\n> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>\n> ---\n>  line-log.c          | 3 ++-\n>  t/t4211-line-log.sh | 4 ++--\n>  2 files changed, 4 insertions(+), 3 deletions(-)\n>\n> diff --git a/line-log.c b/line-log.c\n> index 4bbb09b..8cc29a0 100644\n> --- a/line-log.c\n> +++ b/line-log.c\n> @@ -116,7 +116,8 @@ static void sort_and_merge_range_set(struct range_set *rs)\n>  \n>  \tfor (i = 1; i < rs->nr; i++) {\n>  \t\tif (rs->ranges[i].start <= rs->ranges[o-1].end) {\n> -\t\t\trs->ranges[o-1].end = rs->ranges[i].end;\n> +\t\t\tif (rs->ranges[o-1].end < rs->ranges[i].end)\n> +\t\t\t\trs->ranges[o-1].end = rs->ranges[i].end;\n\nOuch.  Thanks for finding and fixing this.\n\nAcked-by: Thomas Rast <trast@inf.ethz.ch>\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}