[PATCH 0/5] range-set and line-log bug fixes

While implementing multiple -L support for git-blame, I encountered
several bugs in range-set and line-log resulting in crashes. This
series fixes those bugs.

Eric Sunshine (5):
  range-set: fix sort_and_merge_range_set() corner case bug
  t4211: demonstrate empty -L range crash
  range-set: satisfy non-empty ranges invariant
  t4211: demonstrate crash when first -L encountered is empty range
  line-log: fix "log -LN" crash when N is last line of file

 line-log.c          |  9 ++++++---
 t/t4211-line-log.sh | 13 +++++++++++++
 2 files changed, 19 insertions(+), 3 deletions(-)

-- 
1.8.3.4.1120.gc240c48

When handed an empty range_set (range_set.nr == 0),
sort_and_merge_range_set() incorrectly sets range_set.nr to 1 at exit.
Subsequent range_set functions then access the bogus range at element
zero and crash or throw an assertion failure. Fix this bug.

Signed-off-by: Eric Sunshine <redacted>
---

This bug could have been fixed with a simple conditional rather than
changing the for() loop to start at 0. I did it this way, however,
because the next fix (range-set: satisfy non-empty ranges invariant)
also needs the for() loop starting at 0. Thus, by changing the for()
loop here, the subsequent fix becomes much more obvious and easy to
read.

 line-log.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/line-log.c b/line-log.c
index 8cc29a0..5234879 100644
--- a/line-log.c
+++ b/line-log.c

@@ -110,12 +110,12 @@ static void range_set_check_invariants(struct range_set *rs)
 static void sort_and_merge_range_set(struct range_set *rs)
 {
 	int i;
-	int o = 1; /* output cursor */
+	int o = 0; /* output cursor */
 
 	qsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);
 
-	for (i = 1; i < rs->nr; i++) {
-		if (rs->ranges[i].start <= rs->ranges[o-1].end) {
+	for (i = 0; i < rs->nr; i++) {
+		if (o > 0 && rs->ranges[i].start <= rs->ranges[o-1].end) {
 			if (rs->ranges[o-1].end < rs->ranges[i].end)
 				rs->ranges[o-1].end = rs->ranges[i].end;
 		} else {

-- 
1.8.3.4.1120.gc240c48

Signed-off-by: Eric Sunshine <redacted>
---
 t/t4211-line-log.sh | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 7776f93..1db1edd 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh

@@ -64,4 +64,12 @@ test_bad_opts "-L 1,1000:b.c" "has only.*lines"
 test_bad_opts "-L :b.c" "argument.*not of the form"
 test_bad_opts "-L :foo:b.c" "no match"
 
+# There is a separate bug when an empty -L range is the first -L encountered,
+# thus to demonstrate this particular bug, the empty -L range must follow a
+# non-empty -L range.
+test_expect_failure '-L {empty-range} (any -L)' '
+	n=$(expr $(cat b.c | wc -l) + 1) &&
+	git log -L1,1:b.c -L$n:b.c
+'
+
 test_done

-- 
1.8.3.4.1120.gc240c48

Signed-off-by: Eric Sunshine <redacted>
---
 t/t4211-line-log.sh | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 12814c0..7616365 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh

@@ -72,4 +72,9 @@ test_expect_success '-L {empty-range} (any -L)' '
 	git log -L1,1:b.c -L$n:b.c
 '
 
+test_expect_failure '-L {empty-range} (first -L)' '
+	n=$(expr $(cat b.c | wc -l) + 1) &&
+	git log -L$n:b.c
+'
+
 test_done

-- 
1.8.3.4.1120.gc240c48

range-set invariants are: ranges must be (1) non-empty, (2) disjoint,
(3) sorted in ascending order.

During processing, various range-set utility functions break the
invariants (for instance, by adding empty ranges), with the
expectation that a finalizing sort_and_merge_range_set() will restore
sanity.

sort_and_merge_range_set(), however, neglects to fold out empty
ranges, thus it fails to satisfy the non-empty constraint. Subsequent
range-set functions crash or throw an assertion failure upon
encountering such an anomaly. Rectify the situation by having
sort_and_merge_range_set() fold out empty ranges.

Signed-off-by: Eric Sunshine <redacted>
---
 line-log.c          | 2 ++
 t/t4211-line-log.sh | 2 +-
 2 files changed, 3 insertions(+), 1 deletion(-)

diff --git a/line-log.c b/line-log.c
index 5234879..6f94d56 100644
--- a/line-log.c
+++ b/line-log.c

@@ -115,6 +115,8 @@ static void sort_and_merge_range_set(struct range_set *rs)
 	qsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);
 
 	for (i = 0; i < rs->nr; i++) {
+		if (rs->ranges[i].start == rs->ranges[i].end)
+			continue;
 		if (o > 0 && rs->ranges[i].start <= rs->ranges[o-1].end) {
 			if (rs->ranges[o-1].end < rs->ranges[i].end)
 				rs->ranges[o-1].end = rs->ranges[i].end;

diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 1db1edd..12814c0 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh

@@ -67,7 +67,7 @@ test_bad_opts "-L :foo:b.c" "no match"
 # There is a separate bug when an empty -L range is the first -L encountered,
 # thus to demonstrate this particular bug, the empty -L range must follow a
 # non-empty -L range.
-test_expect_failure '-L {empty-range} (any -L)' '
+test_expect_success '-L {empty-range} (any -L)' '
 	n=$(expr $(cat b.c | wc -l) + 1) &&
 	git log -L1,1:b.c -L$n:b.c
 '

-- 
1.8.3.4.1120.gc240c48

range-set invariants are: ranges must be (1) non-empty, (2) disjoint,
(3) sorted in ascending order.

line_log_data_insert() breaks the non-empty invariant under the
following conditions: the incoming range is empty and the pathname
attached to the range has not yet been encountered. In this case,
line_log_data_insert() assigns the empty range to a new line_log_data
record without taking any action to ensure that the empty range is
eventually folded out.  Subsequent range-set functions crash or throw an
assertion failure upon encountering such an anomaly.  Fix this bug.

Signed-off-by: Eric Sunshine <redacted>
---
 line-log.c          | 1 +
 t/t4211-line-log.sh | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/line-log.c b/line-log.c
index 6f94d56..c2d01dc 100644
--- a/line-log.c
+++ b/line-log.c

@@ -299,6 +299,7 @@ static void line_log_data_insert(struct line_log_data **list,
 	p = xcalloc(1, sizeof(struct line_log_data));
 	p->path = path;
 	range_set_append(&p->ranges, begin, end);
+	sort_and_merge_range_set(&p->ranges);
 	if (ip) {
 		p->next = ip->next;
 		ip->next = p;

diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 7616365..94267d7 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh

@@ -72,7 +72,7 @@ test_expect_success '-L {empty-range} (any -L)' '
 	git log -L1,1:b.c -L$n:b.c
 '
 
-test_expect_failure '-L {empty-range} (first -L)' '
+test_expect_success '-L {empty-range} (first -L)' '
 	n=$(expr $(cat b.c | wc -l) + 1) &&
 	git log -L$n:b.c
 '

-- 
1.8.3.4.1120.gc240c48

On Tue, Jul 23, 2013 at 10:28:05AM -0400, Eric Sunshine wrote:

You could avoid the 'cat' here and patch in 4/5 by doing $(wc -l <b.c).

(Side question: the test suite is full with similar constructs, i.e.
redirecting file contents to stdin, but why not just use wc -l b.c,
i.e. let wc open the file?)

On Tue, Jul 23, 2013 at 10:28 AM, Eric Sunshine [off-list ref] wrote:

While implementing multiple -L support for git-blame, I encountered
several bugs in range-set and line-log resulting in crashes. This
series fixes those bugs.

Eric Sunshine (5):
  range-set: fix sort_and_merge_range_set() corner case bug
  t4211: demonstrate empty -L range crash
  range-set: satisfy non-empty ranges invariant
  t4211: demonstrate crash when first -L encountered is empty range
  line-log: fix "log -LN" crash when N is last line of file

I've run into a bit of a conundrum relating to the tests added by this
series, for which I could use some input.

The tests in this series identify real bugs in dealing with empty
ranges, which the subsequent patches fix. The test are possible
because one can specify an empty range via blame/log -L, however, I
now realize that the ability for -L to create empty ranges was never
intended or part of the design, but is in fact itself a bug. An
example manifestation of this bug, given a 5-line file:

  % git blame -L5 foo  # OK, blames line 5
  % git blame -L6 foo  # accepted, no error, no output, huh?
  % git blame -L7 foo  # error: "fatal: file foo has only 5 lines"

I believe that it is correct to fix this bug (and already have a fix
locally). The example -L6 should error out just like -L7 rather than
creating an empty range.

Fixing this bug closes the empty-range-creation loophole which is used
by the t4211 tests added in this series and, unfortunately, there is
no other way to create an empty range, hence no way to keep these
tests operational. What to do?

* Should we drop these new t4211 tests which guard against real potential bugs?

* Should we add custom C code to the test suite to make the
empty-range testing possible?

* Should we introduce another (undocumented) loophole just for the
sake of the tests?

For the last point, I was considering -Lfoo,+0. It is currently
undocumented and its behavior undefined. In fact, -Lfoo,+0 and
-Lfoo,-0 presently are interpreted as -Lfoo,+2 (definitely undefined
behavior). It would be possible to make -Lfoo,+0 mean empty-range and
keep it undocumented, which would create the loophole these tests
require.

I personally dislike this idea for several reasons: (1) we should be
closing loopholes rather than creating them intentionally; (2)
generally, an empty range has no useful meaning in conjunction with
-L; (3) if not an empty range, then -Lfoo,+0 conveys nothing and
should be reported as an error.

The only possible minor advantage I can see to interpreting -Lfoo,+0
as an empty range is that it could provide an anchor for relative
-L/RE/ searches once blame accepts multiple -L options. For example,
"blame -L42,+0 -L/^struct/,/^}/ foo.c" would blame the first struct
starting at line 42, without also showing blame for line 42. I don't
really consider this a good argument in favor of -Lfoo,+0 representing
an empty range, and it's a very poor substitute for Michael Haggerty's
more expressive proposal [1].

[1]: http://thread.gmane.org/gmane.comp.version-control.git/229755/focus=230967

On Thu, Jul 25, 2013 at 4:03 AM, Eric Sunshine [off-list ref] wrote:

I don't
really consider this a good argument in favor of -Lfoo,+0 representing
an empty range, and it's a very poor substitute for Michael Haggerty's
more expressive proposal [1].

[1]: http://thread.gmane.org/gmane.comp.version-control.git/229755/focus=230967

And here's the correct link to Michael's proposal:

http://thread.gmane.org/gmane.comp.version-control.git/229755/focus=229995

Am 7/25/2013 10:03, schrieb Eric Sunshine:

The tests in this series identify real bugs in dealing with empty
ranges, which the subsequent patches fix. The test are possible
because one can specify an empty range via blame/log -L, however, I
now realize that the ability for -L to create empty ranges was never
intended or part of the design, but is in fact itself a bug.

...

* Should we drop these new t4211 tests which guard against real potential bugs?

* Should we add custom C code to the test suite to make the
empty-range testing possible?

* Should we introduce another (undocumented) loophole just for the
sake of the tests?

IIUC, the tests you added are protecting the *implementation* of range-set
functions. For tests of the implementation, we usually write test-foo
programs that call the functions directly.

Tests invoking git should test the observable behavior. Therefore, if
calling a git utility with "-Lfoo,+0" should be an error, then the test
suite should mark such a call with test_must_fail. I guess this rules out
the loophole approach.

-- Hannes

On Thu, Jul 25, 2013 at 5:12 AM, Johannes Sixt [off-list ref] wrote:

Am 7/25/2013 10:03, schrieb Eric Sunshine:

quoted

The tests in this series identify real bugs in dealing with empty
ranges, which the subsequent patches fix. The test are possible
because one can specify an empty range via blame/log -L, however, I
now realize that the ability for -L to create empty ranges was never
intended or part of the design, but is in fact itself a bug.

...

quoted

* Should we drop these new t4211 tests which guard against real potential bugs?

* Should we add custom C code to the test suite to make the
empty-range testing possible?

* Should we introduce another (undocumented) loophole just for the
sake of the tests?

IIUC, the tests you added are protecting the *implementation* of range-set
functions. For tests of the implementation, we usually write test-foo
programs that call the functions directly.

You understand correctly. The added t4211 tests check range-set and
line-log functionality.

range-set is an implementation detail of git-log's -L and is entirely
private (static to the implementation file), so there's no API to test
via a test-foo program. It is sufficiently generic that its API could
(some day) be published, thus allowing a test-foo program, however,
doing so would involve writing documentation and covering its entire
API with tests: a large enough task in itself, and quite orthogonal to
fixing the log/blame -L loophole.

line-log is partially public, however, the code in which the bug was
discovered is private (static) and likely always will be since it is
not generic. Moreover, once the -L loophole is closed, there will be
no way to trigger the case under consideration via its public API, so
again there is no opportunity for a test-foo program.

Thus, the question remains: What to do with these two tests once the
-L loophole is closed? Remove them?

Tests invoking git should test the observable behavior. Therefore, if
calling a git utility with "-Lfoo,+0" should be an error, then the test
suite should mark such a call with test_must_fail. I guess this rules out
the loophole approach.

Indeed, nicely stated.