Re: [PATCH 3/4] line-log: optimize ranges by joining them when possible

From: Andrei Rybak <rybak.a.v@gmail.com>
Date: Aug 5, 2018, 08:45 UTC
Message-ID: <9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com>
In-Reply-To: <d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com>

On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:

Show 10 quoted lines

> 
> 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:

Show 15 quoted lines

> From: Johannes Schindelin <johannes.schindelin@gmx.de>
> 
> 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.