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

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 5, 2018, 06:11 UTC
Message-ID: <xmqq7el5s5qi.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <d5d9db3c1124d29e26864596a8c36f0dc4de8a7e.1533421100.git.gitgitgadget@gmail.com>

"Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 11 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.
>
> When we traverse the history, though, we never join ranges, even they
> become "touchy-feely" due to added lines (which are "removed" from
> line-log's point of view because it traverses the commit history into
> the past).

I do not know if that would be an "optimization" (in the sense that joining would help performance) but I do agree that such a change makes perfect sense from consistency's point of view. If two ranges that were originally apart lose a gap in between them, it does not make any sense to keep them separate. Good thinking.

Show 12 quoted lines

> diff --git a/line-log.c b/line-log.c
> index d8d09b5ee..bc7ef69d6 100644
> --- a/line-log.c
> +++ b/line-log.c
> @@ -68,6 +68,10 @@ void range_set_append_unsafe(struct range_set *rs, long a, long b)
>  
>  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;
> +	}

Nice.

>  	assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);

Show 15 quoted lines

>  	range_set_append_unsafe(rs, a, b);
>  }
> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
> index 61ff37430..ebaf5ea86 100755
> --- a/t/t4211-line-log.sh
> +++ b/t/t4211-line-log.sh
> @@ -119,7 +119,7 @@ q_to_lf () {
>  	tr Q '\012'
>  }
>  
> -test_expect_failure 'close to overlapping ranges' '
> +test_expect_success 'close to overlapping ranges' '
>  	test_seq 5 >a1.c &&
>  	git add a1.c &&
>  	git commit -m "5 lines" a1.c &&