On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:
>
> Now, I am fairly certain that the changes are correct, but given my track
> record with off-by-one bugs (and once even an off-by-two bug), I would
> really appreciate some thorough review of this code, in particular the
> second one that is the actual bug fix. I am specifically interested in
> reviews from people who know line-log.c pretty well and can tell me whether
> the src[i].end > target[j].end is correct, or whether it should actually
> have been a >= (I tried to wrap my head around this, but I would feel more
> comfortable if a domain expert would analyze this, whistling, and looking
> Eric's way).
I don't know line-log.c at all, but here are my comments on the more
abstract range and range_set changes:
On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:
> From: Johannes Schindelin <johannes.schindelin@xxxxxx>
>
> Technically, it is okay to have line ranges that touch (i.e. the end of
> the first range ends just before the next range begins). However, it is
> inefficient, and when the user provides such touching ranges via
> multiple `-L` options, we already join them.
>
> ...
>
> void range_set_append(struct range_set *rs, long a, long b)
> {
> + if (rs->nr > 0 && rs->ranges[rs->nr-1].end + 1 == a) {
> + rs->ranges[rs->nr-1].end = b;
> + return;
> + }
As I understand it, this patch attempts to make range_set_append extend
the last range in the range set to include [a,b), if [a,b) "touches" the
last range in rs.
Definition of range from line-log.h reads:
/* A range [start,end]. Lines are numbered starting at 0, and the
* ranges include start but exclude end. */
struct range {
long start, end;
};
So the optimization described in commit message should take care of
following case, with zero lines between last range in rs and [a,b):
rs before : [---) ... [---)
[a,b) : [---)
rs after : [---) ... [-------)
It seems that the first condition in range_set_append should be:
if (rs->nr > 0 && rs->ranges[rs->nr-1].end == a) {
// extend the last range to include [a, b)
}
I think that the comments around struct range could be improved by
switching from using "[]", as in the comment from line-log.h quoted
above, and "|---|" as in various comments in line-log.c to "left-closed,
right-open" interval notation like "[start,end)" and "[---)".
> assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
> range_set_append_unsafe(rs, a, b);
> }
With these consideration in mind the assert should become
assert(rs->nr == 0 || rs->ranges[rs->nr-1].end < a);
to cover cases starting from one line between last range in rs and [a,b)
rs before : [---) ... [---)
[a,b) : [---)
rs after : [---) ... [---)[---)
^
|
this line still not part of the range set.
