Repository: pilosa/pilosa
Pull request #2100 (2020-03-13 10:02:54)

Fix offset-by-1 in CountRange with continuous bits interval
When the interval is a proper superset of the range with start equal to
interval start, the range must be considered a superset or it will be
completly ignored (since it neither a subset nor it overlaps)

## Overview

CountRange(start, end) may return 0 even if the bitmap contains bits in the range start and end.

See added unittest, especially:

```
bm3 := roaring.NewFileBitmap(1, 2, 3, 4)
bm3.Optimize() // convert to runs
if n := bm3.CountRange(1, 3); n != 2 {
	t.Fatalf("unexpected n: %d", n)
}
```

## Pull request checklist

- [x] I have read the [contributing guide](https://github.com/pilosa/pilosa/blob/master/CONTRIBUTING.md).
- [x] I have agreed to the [Contributor License Agreement](https://cla-assistant.io/pilosa/pilosa).
- [ ] I have updated the [documentation](https://github.com/pilosa/pilosa/tree/master/docs).
- [x] I have resolved any merge conflicts.
- [x] I have included tests that cover my changes.
- [x] All new and existing tests pass.
- [x] Make sure PR title conforms to convention in CHANGELOG.md.
- [ ] Add appropriate changelog label to PR (if applicable).

## Code review checklist
This is the checklist that the reviewer will follow while reviewing your pull request. You do not need to do anything with this checklist, but be aware of what the reviewer will be looking for.

- [ ] Ensure that any changes to external docs have been included in this pull request.
- [ ] If the changes require that minor/major versions need to be updated, tag the PR appropriately.
- [ ] Ensure the new code is [properly commented](https://github.com/golang/go/wiki/CodeReviewComments#doc-comments) and follows [Idiomatic Go](https://dmitri.shuralyov.com/idiomatic-go).
- [ ] Check that tests have been written and that they cover the new functionality.
- [ ] Run tests and ensure they pass.
- [ ] Build and run the code, performing any applicable integration testing.
- [ ] Make sure PR title conforms to convention in CHANGELOG.md.
- [ ] Make sure PR is tagged with appropriate changelog label.



Patch:
diff --git a/roaring/roaring.go b/roaring/roaring.go
index 86ee64fc..ac49ee2f 100644
--- a/roaring/roaring.go
+++ b/roaring/roaring.go
@@ -2033,18 +2033,18 @@ func (c *Container) runCountRange(start, end int32) (n int32) {
 			break
 		}
 		// iv is superset of range
-		if int32(iv.start) < start && int32(iv.last) > end {
+		if int32(iv.start) <= start && int32(iv.last) >= end {
 			return end - start
 		}
 		// iv is subset of range
-		if int32(iv.start) >= start && int32(iv.last) < end {
+		if int32(iv.start) >= start && int32(iv.last) <= end {
 			n += iv.runlen()
 		}
-		// iv overlaps beginning of range
+		// iv overlaps beginning of range without being a subset
 		if int32(iv.start) < start && int32(iv.last) < end {
 			n += int32(iv.last) - start + 1
 		}
-		// iv overlaps end of range
+		// iv overlaps end of range without being a subset
 		if int32(iv.start) > start && int32(iv.last) >= end {
 			n += end - int32(iv.start)
 		}


Test patch:
diff --git a/roaring/roaring_internal_test.go b/roaring/roaring_internal_test.go
index 0ecd7302..27fbe8f2 100644
--- a/roaring/roaring_internal_test.go
+++ b/roaring/roaring_internal_test.go
@@ -147,6 +147,16 @@ func TestRunCountRange(t *testing.T) {
 	c.add(10)
 	c.add(11)
 
+	cnt = c.runCountRange(4, 8)
+	if cnt != 3 {
+		t.Fatalf("should get 3 from range overlaps front of interval, but got: %v", cnt)
+	}
+
+	cnt = c.runCountRange(5, 8)
+	if cnt != 3 {
+		t.Fatalf("should get 3 from range within interval, but got: %v", cnt)
+	}
+
 	cnt = c.runCountRange(6, 8)
 	if cnt != 2 {
 		t.Fatalf("should get 2 from range within interval, but got: %v", cnt)
@@ -162,6 +172,31 @@ func TestRunCountRange(t *testing.T) {
 		t.Fatalf("should get 3 from range overlaps back of interval, but got: %v", cnt)
 	}
 
+	cnt = c.runCountRange(8, 10)
+	if cnt != 2 {
+		t.Fatalf("should get 2 from range within interval, but got: %v", cnt)
+	}
+
+	cnt = c.runCountRange(8, 11)
+	if cnt != 3 {
+		t.Fatalf("should get 3 from range within interval, but got: %v", cnt)
+	}
+
+	cnt = c.runCountRange(8, 12)
+	if cnt != 4 {
+		t.Fatalf("should get 4 from range overlaps back of interval, but got: %v", cnt)
+	}
+
+	cnt = c.runCountRange(5, 12)
+	if cnt != 7 {
+		t.Fatalf("should get 7 from interval within range, but got: %v", cnt)
+	}
+
+	cnt = c.runCountRange(5, 11)
+	if cnt != 6 {
+		t.Fatalf("should get 6 from interval equal to range, but got: %v", cnt)
+	}
+
 	c.add(17)
 	c.add(19)
 	c.add(18)
diff --git a/roaring/roaring_test.go b/roaring/roaring_test.go
index 836fd8de..fbe95273 100644
--- a/roaring/roaring_test.go
+++ b/roaring/roaring_test.go
@@ -457,6 +457,12 @@ func TestBitmap_RunCountRange(t *testing.T) {
 	if n := bm2.CountRange(3, 2); n != 0 {
 		t.Fatalf("unexpected n: %d", n)
 	}
+
+	bm3 := roaring.NewFileBitmap(1, 2, 3, 4)
+	bm3.Optimize() // convert to runs
+	if n := bm3.CountRange(1, 3); n != 2 {
+		t.Fatalf("unexpected n: %d", n)
+	}
 }
 
 func TestBitmap_Intersection(t *testing.T) {