t4211: fix broken test when one -L range is subset of another

t4211 attempts to test multiple git-log -L ranges where one range is a
superset of the other, and falsely succeeds because its "expected"
output is incorrect.

Overlapping -L ranges handed to git-log are coalesced by
line-log.c:sort_and_merge_range_set() into a set of non-overlapping,
disjoint ranges. When one range is a subset of another,
sort_and_merge_range_set() should coalesce both ranges to the superset
range, but instead the coalesced range often is incorrectly truncated to
the end of the subset range. For example, ranges 2-8 and 3-4 are
coalesced incorrectly to 2-4.

One can observe this incorrect behavior with git-log -L using the test
repository created by t4211. The superset/subset ranges t4211 employs
are 4-$ and 8-12 (where $ represents end-of-file). The coalesced range
should be 4-$. Manually invoking git-log with the same ranges the test
employs, we see:

  % git log -L 4:a.c simple |
    awk '/^commit [0-9a-f]{40}/ { print substr($2,1,7) }'
  4659538
  100b61a
  39b6eb2
  a6eb826
  f04fb20
  de4c48a

  % git log -L 8,12:a.c simple | awk ...
  f04fb20
  de4c48a

  % git log -L 4:a.c -L 8,12:a.c simple | awk ...
  a6eb826
  f04fb20
  de4c48a

This last output is incorrect. 8-12 is a subset of 4-$, hence the output
of the coalesced range should be the same as the 4-$ output shown first.
In fact, the above incorrect output is the truncated bogus range 4-12:

  % git log -L 4,12:a.c simple | awk ...
  a6eb826
  f04fb20
  de4c48a

Fix the test to correctly fail in the presence of the
sort_and_merge_range_set() coalescing bug. Do so by changing the
"expected" output to the commits mentioned in the 4-$ output above.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
range_set: fix coalescing bug when range is a subset of another

When coalescing ranges, sort_and_merge_range_set() unconditionally
assumes that the end of a range being folded into a preceding range
should become the end of the coalesced range. This assumption, however,
is invalid when one range is a subset of another.  For example, given
ranges 1-5 and 2-3 added via range_set_append_unsafe(),
sort_and_merge_range_set() incorrectly coalesces them to range 1-3
rather than the correct union range 1-5. Fix this bug.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
range-set: fix sort_and_merge_range_set() corner case bug

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 <sunshine@sunshineco.com>
Acked-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t4211: demonstrate empty -L range crash

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Acked-by: Thomas Rast <trast@inf.ethz.ch>
Helped-by: SZEDER Gábor <szeder@ira.uka.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t4211: demonstrate crash when first -L encountered is empty range

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Acked-by: Thomas Rast <trast@inf.ethz.ch>
Helped-by: SZEDER Gábor <szeder@ira.uka.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
range-set: satisfy non-empty ranges invariant

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 <sunshine@sunshineco.com>
Acked-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
line-log: fix "log -LN" crash when N is last line of file

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 <sunshine@sunshineco.com>
Acked-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'es/line-log-further-fixes' into tr/line-log

* es/line-log-further-fixes:
  line-log: fix "log -LN" crash when N is last line of file
  range-set: satisfy non-empty ranges invariant
  t4211: demonstrate crash when first -L encountered is empty range
  t4211: demonstrate empty -L range crash
  range-set: fix sort_and_merge_range_set() corner case bug
  range_set: fix coalescing bug when range is a subset of another
  t4211: fix broken test when one -L range is subset of another