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

From: Eric Sunshine <sunshine@sunshineco.com>
Date: Aug 5, 2018, 10:31 UTC
Message-ID: <CAPig+cRoQB6Az=sYB_tjhOLewJyMzYAwqNxPh99a3aZFhzDcYg@mail.gmail.com>
In-Reply-To: <9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com>

Show 19 quoted lines

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