git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Andrei Rybak <rybak.a.v@gmail.com>
To: Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com>,
	git@vger.kernel.org
Cc: Thomas Rast <tr@thomasrast.ch>,
	Junio C Hamano <gitster@pobox.com>,
	Johannes Schindelin <johannes.schindelin@gmx.de>
Subject: Re: [PATCH 3/4] line-log: optimize ranges by joining them when possible
Date: Sun, 5 Aug 2018 10:45:45 +0200	[thread overview]
Message-ID: <9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com> (raw)
In-Reply-To: <d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com>

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@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.
  

  parent reply	other threads:[~2018-08-05  8:45 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-04 22:18 [PATCH 0/4] line-log: be more careful when adjusting multiple line ranges Johannes Schindelin via GitGitGadget
2018-08-04 22:18 ` [PATCH 1/4] line-log: demonstrate a bug with nearly-overlapping ranges Johannes Schindelin via GitGitGadget
2018-08-05  1:59   ` Jonathan Nieder
2018-08-06 10:27     ` Johannes Schindelin
2018-08-06 14:47       ` Jonathan Nieder
2018-08-06 15:33         ` Jonathan Nieder
2018-08-04 22:18 ` [PATCH 2/4] line-log: adjust start/end of ranges individually Johannes Schindelin via GitGitGadget
2018-08-05 10:14   ` Eric Sunshine
2018-08-05 10:57     ` Eric Sunshine
2018-08-06 12:52     ` Johannes Schindelin
2018-08-04 22:18 ` [PATCH 3/4] line-log: optimize ranges by joining them when possible Johannes Schindelin via GitGitGadget
2018-08-05  6:11   ` Junio C Hamano
2018-08-05  8:45   ` Andrei Rybak [this message]
2018-08-05 10:31     ` Eric Sunshine
2018-08-04 22:18 ` [PATCH 4/4] line-log: convert an assertion to a full BUG() call Johannes Schindelin via GitGitGadget
2018-08-05 10:42   ` Eric Sunshine
2018-08-06 13:14     ` Johannes Schindelin
2018-08-07  9:09       ` Eric Sunshine
2018-08-07 22:00         ` Eric Sunshine
2018-08-05 10:39 ` [PATCH 0/4] line-log: be more careful when adjusting multiple line ranges Eric Sunshine

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com \
    --to=rybak.a.v@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=gitster@pobox.com \
    --cc=johannes.schindelin@gmx.de \
    --cc=tr@thomasrast.ch \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).