git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / Atom feed
* [PATCH] range_set: fix coalescing bug when range is a subset of another
@ 2013-07-07 13:02 Eric Sunshine
  0 siblings, 0 replies; only message in thread
From: Eric Sunshine @ 2013-07-07 13:02 UTC (permalink / raw)
  To: git; +Cc: Eric Sunshine

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 <sunshine@sunshineco.com>
---

Presumably, this problem does not happen in practice, so it's not clear
if the patch should be applied.  I discovered it when teaching git-blame
to accept multiple -L options, one iteration of which (after making the
range_set API public) employed sort_and_merge_range_set() to sort and
coalesce input -L ranges added via range_set_append_unsafe().

It might make sense to apply this patch in order to future-proof
sort_and_merge_range_set() in case the range_set API ever becomes
public.


 line-log.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

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;
 		} else {
 			rs->ranges[o].start = rs->ranges[i].start;
 			rs->ranges[o].end = rs->ranges[i].end;
-- 
1.8.3.2

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2013-07-07 13:03 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-07-07 13:02 [PATCH] range_set: fix coalescing bug when range is a subset of another Eric Sunshine

git@vger.kernel.org list mirror (unofficial, one of many)

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 git git/ https://public-inbox.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.io/gmane.comp.version-control.git
 note: .onion URLs require Tor: https://www.torproject.org/

code repositories for the project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git