{"thread":{"id":"33396","subject":"Re: [PATCH 0/2] log -L overlapping ranges","startedAt":"2013-04-05T14:34:46Z","lastAt":"2013-04-05T17:39:45Z","messageCount":4,"participants":["Junio C Hamano","Thomas Rast"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"213295","messageId":"cover.1365172322.git.trast@inf.ethz.ch","threadId":"33396","inReplyTo":null,"subject":"[PATCH 0/2] log -L overlapping ranges","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-05T14:34:46Z","receivedAt":"2013-04-05T14:34:46Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"I noticed that it doesn't like getting multiple overlapping ranges\nfrom the user. This fixes it.\n\n\nThomas Rast (2):\n log -L: check range set invariants when we look it up\n log -L: fix overlapping input ranges\n\n line-log.c | 43 +++++++--\n t/t4211-line-log.sh | 6 ++\n t/t4211/expect.multiple | 104 ++++++++++++++++++++\n t/t4211/expect.multiple-overlapping | 187 ++++++++++++++++++++++++++++++++++++\n t/t4211/expect.multiple-superset | 59 ++++++++++++\n 5 files changed, 392 insertions(+), 7 deletions(-)\n create mode 100644 t/t4211/expect.multiple\n create mode 100644 t/t4211/expect.multiple-overlapping\n create mode 100644 t/t4211/expect.multiple-superset\n\n-- \n1.8.2.662.g6b31d33\n"},{"id":"213285","messageId":"1604fca2ca876cfed7f26b914a31607269c2d5de.1365172322.git.trast@inf.ethz.ch","threadId":"33396","inReplyTo":"cover.1365172322.git.trast@inf.ethz.ch","subject":"[PATCH 1/2] log -L: check range set invariants when we look it up","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-05T14:34:47Z","receivedAt":"2013-04-05T14:34:47Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"lookup_line_range() is a good place to check that the range sets\nsatisfy the invariants: they have been computed and set in earlier\niterations, and we now start working with them.\n\nSigned-off-by: Thomas Rast \n---\n line-log.c | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/line-log.c b/line-log.c\nindex 30edef4..5a12ceb 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -80,6 +80,25 @@ static int range_cmp(const void *_r, const void *_s)\n }\n \n /*\n+ * Check that the ranges are non-empty, sorted and non-overlapping\n+ */\n+static void range_set_check_invariants(struct range_set *rs)\n+{\n+\tint i;\n+\n+\tif (!rs)\n+\t\treturn;\n+\n+\tif (rs->nr)\n+\t\tassert(rs->ranges[0].start < rs->ranges[0].end);\n+\n+\tfor (i = 1; i < rs->nr; i++) {\n+\t\tassert(rs->ranges[i-1].end < rs->ranges[i].start);\n+\t\tassert(rs->ranges[i].start < rs->ranges[i].end);\n+\t}\n+}\n+\n+/*\n * Helper: In-place pass of sorting and merging the ranges in the\n * range set, to re-establish the invariants after another operation\n *\n@@ -103,6 +122,8 @@ static void sort_and_merge_range_set(struct range_set *rs)\n \t}\n \tassert(o <= rs->nr);\n \trs->nr = o;\n+\n+\trange_set_check_invariants(rs);\n }\n \n /*\n@@ -687,8 +708,13 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,\n \t\t\t\t\t struct commit *commit)\n {\n \tstruct line_log_data *ret = NULL;\n+\tstruct line_log_data *d;\n \n \tret = lookup_decoration(&revs->line_log_data, &commit->object);\n+\n+\tfor (d = ret; d; d = d->next)\n+\t\trange_set_check_invariants(&d->ranges);\n+\n \treturn ret;\n }\n \n-- \n1.8.2.662.g6b31d33\n"},{"id":"213297","messageId":"c6e42a44fe0b21504bf504986b6a988f08c00646.1365172322.git.trast@inf.ethz.ch","threadId":"33396","inReplyTo":"cover.1365172322.git.trast@inf.ethz.ch","subject":"[PATCH 2/2] log -L: fix overlapping input ranges","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-05T14:34:48Z","receivedAt":"2013-04-05T14:34:48Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The existing code was too defensive, and would trigger the assert in\nrange_set_append() if the user gave overlapping ranges.\n\nThe intent was always to define overlapping ranges as just the union\nof all of them, as evidenced by the call to sort_and_merge_range_set().\n(Which was already used, unlike what the comment said.)\n\nFix by splitting out the meat of range_set_append() to a new _unsafe()\nfunction that lacks the paranoia. sort_and_merge_range_set will fix\nup the ranges, so we don't need the checks there.\n\nSigned-off-by: Thomas Rast \n---\n line-log.c | 17 ++--\n t/t4211-line-log.sh | 6 ++\n t/t4211/expect.multiple | 104 ++++++++++++++++++++\n t/t4211/expect.multiple-overlapping | 187 ++++++++++++++++++++++++++++++++++++\n t/t4211/expect.multiple-superset | 59 ++++++++++++\n 5 files changed, 366 insertions(+), 7 deletions(-)\n create mode 100644 t/t4211/expect.multiple\n create mode 100644 t/t4211/expect.multiple-overlapping\n create mode 100644 t/t4211/expect.multiple-superset\n\ndiff --git a/line-log.c b/line-log.c\nindex 5a12ceb..85c7c24 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -56,16 +56,21 @@ static void range_set_move(struct range_set *dst, struct range_set *src)\n }\n \n /* tack on a _new_ range _at the end_ */\n-static void range_set_append(struct range_set *rs, long a, long b)\n+static void range_set_append_unsafe(struct range_set *rs, long a, long b)\n {\n \tassert(a <= b);\n-\tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n \trange_set_grow(rs, 1);\n \trs->ranges[rs->nr].start = a;\n \trs->ranges[rs->nr].end = b;\n \trs->nr++;\n }\n \n+static void range_set_append(struct range_set *rs, long a, long b)\n+{\n+\tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n+\trange_set_append_unsafe(rs, a, b);\n+}\n+\n static int range_cmp(const void *_r, const void *_s)\n {\n \tconst struct range *r = _r;\n@@ -99,10 +104,8 @@ static void range_set_check_invariants(struct range_set *rs)\n }\n \n /*\n- * Helper: In-place pass of sorting and merging the ranges in the\n- * range set, to re-establish the invariants after another operation\n- *\n- * NEEDSWORK currently not needed\n+ * In-place pass of sorting and merging the ranges in the range set,\n+ * to establish the invariants when we get the ranges from the user\n */\n static void sort_and_merge_range_set(struct range_set *rs)\n {\n@@ -280,7 +283,7 @@ static void line_log_data_insert(struct line_log_data **list,\n \tstruct line_log_data *p = search_line_log_data(*list, spec->path, &ip);\n \n \tif (p) {\n-\t\trange_set_append(&p->ranges, begin, end);\n+\t\trange_set_append_unsafe(&p->ranges, begin, end);\n \t\tsort_and_merge_range_set(&p->ranges);\n \t\tfree_filespec(spec);\n \t\treturn;\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 426a828..2341351 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -39,6 +39,12 @@ canned_test \"-L 24,+1:a.c simple\" vanishes-early\n \n canned_test \"-L '/long f/,/^}/:b.c' move-support\" move-support-f\n \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+\n test_bad_opts \"-L\" \"switch.*requires a value\"\n test_bad_opts \"-L b.c\" \"argument.*not of the form\"\n test_bad_opts \"-L 1:\" \"argument.*not of the form\"\ndiff --git a/t/t4211/expect.multiple b/t/t4211/expect.multiple\nnew file mode 100644\nindex 0000000..76ad5b5\n--- /dev/null\n+++ b/t/t4211/expect.multiple\n@@ -0,0 +1,104 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \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+@@ -18,5 +18,7 @@\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 \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+@@ -18,5 +18,5 @@\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 a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,9 +3,9 @@\n+-int f(int x)\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+@@ -17,5 +17,5 @@\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 \n+Date: Thu Feb 28 10:44:55 2013 +0100\n+\n+ change f()\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,8 +3,9 @@\n+ int f(int x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n++\treturn s;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +3,8 @@\n++int f(int x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\n++\t\ts++;\n++\t}\n++}\ndiff --git a/t/t4211/expect.multiple-overlapping b/t/t4211/expect.multiple-overlapping\nnew file mode 100644\nindex 0000000..d930b6e\n--- /dev/null\n+++ b/t/t4211/expect.multiple-overlapping\n@@ -0,0 +1,187 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \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 \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 \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 \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,19 +3,19 @@\n+-int f(int x)\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+ */\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 \n+Date: Thu Feb 28 10:44:55 2013 +0100\n+\n+ change f()\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,18 +3,19 @@\n+ int f(int 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+ */\n+ \n+ int main ()\n+ {\n+ \tprintf(\"%d\\n\", f(15));\n+ \treturn 0;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +3,18 @@\n++int f(int x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\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++}\ndiff --git a/t/t4211/expect.multiple-superset b/t/t4211/expect.multiple-superset\nnew file mode 100644\nindex 0000000..a1f5bc4\n--- /dev/null\n+++ b/t/t4211/expect.multiple-superset\n@@ -0,0 +1,59 @@\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,9 +3,9 @@\n+-int f(int x)\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+commit f04fb20f2c77850996cba739709acc6faecc58f7\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:55 2013 +0100\n+\n+ change f()\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,8 +3,9 @@\n+ int f(int x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n++\treturn s;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +3,8 @@\n++int f(int x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\n++\t\ts++;\n++\t}\n++}\n-- \n1.8.2.662.g6b31d33\n"},{"id":"213281","messageId":"7vzjxcc1we.fsf@alter.siamese.dyndns.org","threadId":"33396","inReplyTo":"cover.1365172322.git.trast@inf.ethz.ch","subject":"Re: [PATCH 0/2] log -L overlapping ranges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-05T17:39:45Z","receivedAt":"2013-04-05T17:39:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> I noticed that it doesn't like getting multiple overlapping ranges\n> from the user. This fixes it.\n\nBoth look sensible. Will queue on top of tr/line-log.\n\nThanks.\n"}]}