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

[Eric Sunshine <sunshine@sunshineco.com>]

> On 2018-08-05 00:18, Johannes Schindelin via GitGitGadget wrote:
> > 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.
> It seems that the first condition in range_set_append should be:
>
>         if (rs->nr > 0 && rs->ranges[rs->nr-1].end == a) {

I agree that this patch has an off-by-1 bug. 'end' is not included in
the previous range, so it should not be adding 1 to end before
checking against 'a'.

*However*, as mentioned in my review[1] of 2/4, the special-case added
by this patch is unnecessary, so this patch should be scrapped.

> With these consideration in mind the assert should become
>
>         assert(rs->nr == 0 || rs->ranges[rs->nr-1].end < a);

Agreed. The existing assertion() has an off-by-1 error.
range_set_append() is supposed to add a range _without_ breaking the
invariant that no two ranges can abut, and the assertion() was
supposed to protect against that. The existing "<= a" incorrectly
allows the new range to abut an existing one, whereas the proposed "<
a" doesn't.

(For adding abutting or overlapping ranges, range_set_append_unsafe()
followed, at some point, by sort_and_merge_range_set() is the
recommended alternative to the more strict range_set_append().)

[1]: https://public-inbox.org/git/CAPig+cRWcFVbA76_HT2iVD16bsUmbWdCgk_07rmiGneM5czdOQ@mail.gmail.com/