[PATCH 0/2] log -L overlapping ranges

[PATCH 0/2] log -L overlapping ranges

[Thomas Rast]

I noticed that it doesn't like getting multiple overlapping ranges
from the user.  This fixes it.


Thomas Rast (2):
  log -L: check range set invariants when we look it up
  log -L: fix overlapping input ranges

 line-log.c                          |  43 +++++++--
 t/t4211-line-log.sh                 |   6 ++
 t/t4211/expect.multiple             | 104 ++++++++++++++++++++
 t/t4211/expect.multiple-overlapping | 187 ++++++++++++++++++++++++++++++++++++
 t/t4211/expect.multiple-superset    |  59 ++++++++++++
 5 files changed, 392 insertions(+), 7 deletions(-)
 create mode 100644 t/t4211/expect.multiple
 create mode 100644 t/t4211/expect.multiple-overlapping
 create mode 100644 t/t4211/expect.multiple-superset

-- 
1.8.2.662.g6b31d33

[PATCH 1/2] log -L: check range set invariants when we look it up

[Thomas Rast]

lookup_line_range() is a good place to check that the range sets
satisfy the invariants: they have been computed and set in earlier
iterations, and we now start working with them.

Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
---
 line-log.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/line-log.c b/line-log.c
index 30edef4..5a12ceb 100644
--- a/line-log.c
+++ b/line-log.c
@@ -80,6 +80,25 @@ static int range_cmp(const void *_r, const void *_s)
 }
 
 /*
+ * Check that the ranges are non-empty, sorted and non-overlapping
+ */
+static void range_set_check_invariants(struct range_set *rs)
+{
+	int i;
+
+	if (!rs)
+		return;
+
+	if (rs->nr)
+		assert(rs->ranges[0].start < rs->ranges[0].end);
+
+	for (i = 1; i < rs->nr; i++) {
+		assert(rs->ranges[i-1].end < rs->ranges[i].start);
+		assert(rs->ranges[i].start < rs->ranges[i].end);
+	}
+}
+
+/*
  * Helper: In-place pass of sorting and merging the ranges in the
  * range set, to re-establish the invariants after another operation
  *
@@ -103,6 +122,8 @@ static void sort_and_merge_range_set(struct range_set *rs)
 	}
 	assert(o <= rs->nr);
 	rs->nr = o;
+
+	range_set_check_invariants(rs);
 }
 
 /*
@@ -687,8 +708,13 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,
 					       struct commit *commit)
 {
 	struct line_log_data *ret = NULL;
+	struct line_log_data *d;
 
 	ret = lookup_decoration(&revs->line_log_data, &commit->object);
+
+	for (d = ret; d; d = d->next)
+		range_set_check_invariants(&d->ranges);
+
 	return ret;
 }
 
-- 
1.8.2.662.g6b31d33

[PATCH 2/2] log -L: fix overlapping input ranges

[Thomas Rast]

The existing code was too defensive, and would trigger the assert in
range_set_append() if the user gave overlapping ranges.

The intent was always to define overlapping ranges as just the union
of all of them, as evidenced by the call to sort_and_merge_range_set().
(Which was already used, unlike what the comment said.)

Fix by splitting out the meat of range_set_append() to a new _unsafe()
function that lacks the paranoia.  sort_and_merge_range_set will fix
up the ranges, so we don't need the checks there.

Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
---
 line-log.c                          |  17 ++--
 t/t4211-line-log.sh                 |   6 ++
 t/t4211/expect.multiple             | 104 ++++++++++++++++++++
 t/t4211/expect.multiple-overlapping | 187 ++++++++++++++++++++++++++++++++++++
 t/t4211/expect.multiple-superset    |  59 ++++++++++++
 5 files changed, 366 insertions(+), 7 deletions(-)
 create mode 100644 t/t4211/expect.multiple
 create mode 100644 t/t4211/expect.multiple-overlapping
 create mode 100644 t/t4211/expect.multiple-superset

diff --git a/line-log.c b/line-log.c
index 5a12ceb..85c7c24 100644
--- a/line-log.c
+++ b/line-log.c
@@ -56,16 +56,21 @@ static void range_set_move(struct range_set *dst, struct range_set *src)
 }
 
 /* tack on a _new_ range _at the end_ */
-static void range_set_append(struct range_set *rs, long a, long b)
+static void range_set_append_unsafe(struct range_set *rs, long a, long b)
 {
 	assert(a <= b);
-	assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
 	range_set_grow(rs, 1);
 	rs->ranges[rs->nr].start = a;
 	rs->ranges[rs->nr].end = b;
 	rs->nr++;
 }
 
+static void range_set_append(struct range_set *rs, long a, long b)
+{
+	assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
+	range_set_append_unsafe(rs, a, b);
+}
+
 static int range_cmp(const void *_r, const void *_s)
 {
 	const struct range *r = _r;
@@ -99,10 +104,8 @@ static void range_set_check_invariants(struct range_set *rs)
 }
 
 /*
- * Helper: In-place pass of sorting and merging the ranges in the
- * range set, to re-establish the invariants after another operation
- *
- * NEEDSWORK currently not needed
+ * In-place pass of sorting and merging the ranges in the range set,
+ * to establish the invariants when we get the ranges from the user
  */
 static void sort_and_merge_range_set(struct range_set *rs)
 {
@@ -280,7 +283,7 @@ static void line_log_data_insert(struct line_log_data **list,
 	struct line_log_data *p = search_line_log_data(*list, spec->path, &ip);
 
 	if (p) {
-		range_set_append(&p->ranges, begin, end);
+		range_set_append_unsafe(&p->ranges, begin, end);
 		sort_and_merge_range_set(&p->ranges);
 		free_filespec(spec);
 		return;
diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 426a828..2341351 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh
@@ -39,6 +39,12 @@ canned_test "-L 24,+1:a.c simple" vanishes-early
 
 canned_test "-L '/long f/,/^}/:b.c' move-support" move-support-f
 
+canned_test "-L 4,12:a.c -L :main:a.c simple" multiple
+canned_test "-L 4,18:a.c -L :main:a.c simple" multiple-overlapping
+canned_test "-L :main:a.c -L 4,18:a.c simple" multiple-overlapping
+canned_test "-L 4:a.c -L 8,12:a.c simple" multiple-superset
+canned_test "-L 8,12:a.c -L 4:a.c simple" multiple-superset
+
 test_bad_opts "-L" "switch.*requires a value"
 test_bad_opts "-L b.c" "argument.*not of the form"
 test_bad_opts "-L 1:" "argument.*not of the form"
diff --git a/t/t4211/expect.multiple b/t/t4211/expect.multiple
new file mode 100644
index 0000000..76ad5b5
--- /dev/null
+++ b/t/t4211/expect.multiple
@@ -0,0 +1,104 @@
+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:48:43 2013 +0100
+
+    change back to complete line
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -18,5 +18,7 @@
+ int main ()
+ {
+ 	printf("%ld\n", f(15));
+ 	return 0;
+-}
+\ No newline at end of file
++}
++
++/* incomplete lines are bad! */
+
+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:48:10 2013 +0100
+
+    change to an incomplete line at end
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -18,5 +18,5 @@
+ int main ()
+ {
+ 	printf("%ld\n", f(15));
+ 	return 0;
+-}
++}
+\ No newline at end of file
+
+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:45:16 2013 +0100
+
+    touch both functions
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,9 +3,9 @@
+-int f(int x)
++long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+@@ -17,5 +17,5 @@
+ int main ()
+ {
+-	printf("%d\n", f(15));
++	printf("%ld\n", f(15));
+ 	return 0;
+ }
+
+commit f04fb20f2c77850996cba739709acc6faecc58f7
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:55 2013 +0100
+
+    change f()
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,8 +3,9 @@
+ int f(int x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
++	return s;
+ }
+
+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:48 2013 +0100
+
+    initial
+
+diff --git a/a.c b/a.c
+--- /dev/null
++++ b/a.c
+@@ -0,0 +3,8 @@
++int f(int x)
++{
++	int s = 0;
++	while (x) {
++		x >>= 1;
++		s++;
++	}
++}
diff --git a/t/t4211/expect.multiple-overlapping b/t/t4211/expect.multiple-overlapping
new file mode 100644
index 0000000..d930b6e
--- /dev/null
+++ b/t/t4211/expect.multiple-overlapping
@@ -0,0 +1,187 @@
+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:48:43 2013 +0100
+
+    change back to complete line
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -4,19 +4,21 @@
+ long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+ 
+ /*
+  * This is only an example!
+  */
+ 
+ int main ()
+ {
+ 	printf("%ld\n", f(15));
+ 	return 0;
+-}
+\ No newline at end of file
++}
++
++/* incomplete lines are bad! */
+
+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:48:10 2013 +0100
+
+    change to an incomplete line at end
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -4,19 +4,19 @@
+ long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+ 
+ /*
+  * This is only an example!
+  */
+ 
+ int main ()
+ {
+ 	printf("%ld\n", f(15));
+ 	return 0;
+-}
++}
+\ No newline at end of file
+
+commit 39b6eb2d5b706d3322184a169f666f25ed3fbd00
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:45:41 2013 +0100
+
+    touch comment
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,19 +3,19 @@
+ long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+ 
+ /*
+- * A comment.
++ * This is only an example!
+  */
+ 
+ int main ()
+ {
+ 	printf("%ld\n", f(15));
+ 	return 0;
+ }
+
+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:45:16 2013 +0100
+
+    touch both functions
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,19 +3,19 @@
+-int f(int x)
++long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+ 
+ /*
+  * A comment.
+  */
+ 
+ int main ()
+ {
+-	printf("%d\n", f(15));
++	printf("%ld\n", f(15));
+ 	return 0;
+ }
+
+commit f04fb20f2c77850996cba739709acc6faecc58f7
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:55 2013 +0100
+
+    change f()
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,18 +3,19 @@
+ int f(int x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
++	return s;
+ }
+ 
+ /*
+  * A comment.
+  */
+ 
+ int main ()
+ {
+ 	printf("%d\n", f(15));
+ 	return 0;
+ }
+
+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:48 2013 +0100
+
+    initial
+
+diff --git a/a.c b/a.c
+--- /dev/null
++++ b/a.c
+@@ -0,0 +3,18 @@
++int f(int x)
++{
++	int s = 0;
++	while (x) {
++		x >>= 1;
++		s++;
++	}
++}
++
++/*
++ * A comment.
++ */
++
++int main ()
++{
++	printf("%d\n", f(15));
++	return 0;
++}
diff --git a/t/t4211/expect.multiple-superset b/t/t4211/expect.multiple-superset
new file mode 100644
index 0000000..a1f5bc4
--- /dev/null
+++ b/t/t4211/expect.multiple-superset
@@ -0,0 +1,59 @@
+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:45:16 2013 +0100
+
+    touch both functions
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,9 +3,9 @@
+-int f(int x)
++long f(long x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
+ 	return s;
+ }
+
+commit f04fb20f2c77850996cba739709acc6faecc58f7
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:55 2013 +0100
+
+    change f()
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,8 +3,9 @@
+ int f(int x)
+ {
+ 	int s = 0;
+ 	while (x) {
+ 		x >>= 1;
+ 		s++;
+ 	}
++	return s;
+ }
+
+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a
+Author: Thomas Rast <trast@student.ethz.ch>
+Date:   Thu Feb 28 10:44:48 2013 +0100
+
+    initial
+
+diff --git a/a.c b/a.c
+--- /dev/null
++++ b/a.c
+@@ -0,0 +3,8 @@
++int f(int x)
++{
++	int s = 0;
++	while (x) {
++		x >>= 1;
++		s++;
++	}
++}
-- 
1.8.2.662.g6b31d33

Re: [PATCH 0/2] log -L overlapping ranges

[Junio C Hamano]

Thomas Rast <trast@inf.ethz.ch> writes:

> I noticed that it doesn't like getting multiple overlapping ranges
> from the user.  This fixes it.

Both look sensible.  Will queue on top of tr/line-log.

Thanks.