Subject: Re: [PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another

From: Thomas Rast <[email-masked]>
Date: Tue, 9 Jul 2013 11:31:49 +0200

Eric Sunshine <[email-masked]> writes:

> When coalescing ranges, sort_and_merge_range_set() unconditionally
> assumes that the end of a range being folded into a preceding range
> should become the end of the coalesced range. This assumption, however,
> is invalid when one range is a subset of another.  For example, given
> ranges 1-5 and 2-3 added via range_set_append_unsafe(),
> sort_and_merge_range_set() incorrectly coalesces them to range 1-3
> rather than the correct union range 1-5. Fix this bug.
>
> Signed-off-by: Eric Sunshine <[email-masked]>
> ---
>  line-log.c          | 3 ++-
>  t/t4211-line-log.sh | 4 ++--
>  2 files changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/line-log.c b/line-log.c
> index 4bbb09b..8cc29a0 100644
> --- a/line-log.c
> +++ b/line-log.c
> @@ -116,7 +116,8 @@ static void sort_and_merge_range_set(struct range_set *rs)
>  
>  	for (i = 1; i < rs->nr; i++) {
>  		if (rs->ranges[i].start <= rs->ranges[o-1].end) {
> -			rs->ranges[o-1].end = rs->ranges[i].end;
> +			if (rs->ranges[o-1].end < rs->ranges[i].end)
> +				rs->ranges[o-1].end = rs->ranges[i].end;

Ouch.  Thanks for finding and fixing this.

Acked-by: Thomas Rast <[email-masked]>

-- 
Thomas Rast
trast@{inf,student}.ethz.ch