Repository: pilosa/pilosa
Pull request #2023 (2019-06-25 16:35:38)

Add naive implementations of Roaring and fuzz test
## Overview

This PR adds a naive implementation of Roaring operations, where every Roaring Bitmap is represented as only `uint64` slices. Using this, we can then fuzz-test the naive implementation vs the actual Roaring implementations to check for correctness in the latter.

This actually revealed some bugs, as pointed out in #2015 and fixed in #2019.

This PR also modifies some tests to run conditional on the `roaringsentinel` build tag, instead of the `roaringparanoia` tag. In general, `roaringsentinel` is used for controlling unexpected/invalid behavior from users (e.g. calling `CountRange` with `start > end`), while `roaringparanoia` is used for controlling unexpected behavior that occur internally within the Roaring operations.

## 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).
- [ ] I have resolved any merge conflicts.
- [x] I have included tests that cover my changes.
- [x] All new and existing tests pass.
- [ ] Make sure PR title conforms to convention in CHANGELOG.md.
- [x] 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/fuzzer.go b/roaring/fuzzer.go
index cf3483b9..9312f786 100644
--- a/roaring/fuzzer.go
+++ b/roaring/fuzzer.go
@@ -16,6 +16,15 @@
 
 package roaring
 
+import (
+	"encoding/binary"
+	"fmt"
+	"io/ioutil"
+	"reflect"
+)
+
+// FuzzBitmapUnmarshalBinary fuzz tests the unmarshaling of binary
+// to both Pilosa and official roaring formats.
 func FuzzBitmapUnmarshalBinary(data []byte) int {
 	b := NewBitmap()
 	err := b.UnmarshalBinary(data)
@@ -24,3 +33,291 @@ func FuzzBitmapUnmarshalBinary(data []byte) int {
 	}
 	return 1
 }
+
+// FuzzRoaringOps fuzz tests different operations on roaring bitmaps,
+// comparing the results to a naive implementation of the operations
+// on uint64 slices.
+func FuzzRoaringOps(data []byte) int {
+	// number of uint64s not to include
+	const reserved = 4
+	// flipping is too inefficient for large values of end - start
+	// and will cause go-fuzz to hang if not controlled.
+	const maxFlips = 1000000
+
+	arr := bytesToUint64s(data)
+	if len(arr) <= reserved {
+		return 0
+	}
+
+	// start > end is possible. This will test correctness in unexpected conditions.
+	start, end, split, rand := arr[0], arr[1], int(arr[2]), arr[3]
+
+	// don't include start, end, split, rand in the slices
+	if split < reserved {
+		split = reserved
+	}
+	// ensure slice in bounds
+	if split > len(arr) {
+		split = len(arr)
+	}
+	// using removeSliceDuplicates guarantees that the slice inputs of the
+	// following functions do not have duplicates and are sorted, just as
+	// the Roaring Bitmap implementations are.
+	s1 := removeSliceDuplicates(arr[reserved:split])
+	s2 := removeSliceDuplicates(arr[split:])
+	if len(s1) == 0 {
+		s1 = nil
+	}
+	if len(s2) == 0 {
+		s2 = nil
+	}
+	bm1 := NewBitmap(arr[reserved:split]...)
+	bm2 := NewBitmap(arr[split:]...)
+
+	expected := s1
+	actual := bm1.Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("first slice:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expected = s2
+	actual = bm2.Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("second slice:\n expected: %v\n got: %v", expected, actual))
+	}
+	// Pure functions
+
+	expected = []uint64{maxInSlice(s1), maxInSlice(s2)}
+	actual = []uint64{bm1.Max(), bm2.Max()}
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("max values:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expected = intersectSlice(s1, s2)
+	actual = bm1.Intersect(bm2).Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("intersection:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expected = unionSlice(s1, s2)
+	actual = bm1.Union(bm2).Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("union:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expected = differenceSlice(s1, s2)
+	actual = bm1.Difference(bm2).Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("difference:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expected = xorSlice(s1, s2)
+	actual = bm1.Xor(bm2).Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("XOR:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	if (len(s1) > 0) != bm1.Any() {
+		panic(fmt.Sprintf("any:\n %v has %v values but got %v which has %v values", s1, len(s1), bm1.Slice(), bm1.Any()))
+	}
+	if (len(s2) > 0) != bm2.Any() {
+		panic(fmt.Sprintf("any:\n %v has %v values but got %v which has %v values", s2, len(s2), bm2.Slice(), bm2.Any()))
+	}
+
+	expected = []uint64{uint64(len(s1)), uint64(len(s2))}
+	actual = []uint64{bm1.Count(), bm2.Count()}
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("count:\n expected: %v\n got: %v", expected, actual))
+	}
+
+	expect := countRangeSlice(s1, start, end)
+	got := bm1.CountRange(start, end)
+	if expect != got {
+		panic(fmt.Sprintf("count range:\n count from %v to %v in slice %v and bitmap %v:\n expected %v got %v",
+			start, end, s1, bm1.Slice(), expect, got))
+	}
+	expect = countRangeSlice(s2, start, end)
+	got = bm2.CountRange(start, end)
+	if expect != got {
+		panic(fmt.Sprintf("count range:\n count from %v to %v in slice %v and bitmap %v:\n expected %v got %v",
+			start, end, s2, bm2.Slice(), expect, got))
+	}
+
+	expected = rangeSlice(s1, start, end)
+	actual = bm1.SliceRange(start, end)
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("slice range:\n from %v to %v in slice %v and bitmap %v:\n expected %v\n got %v",
+			start, end, s1, bm1.Slice(), expected, actual))
+	}
+	expected = rangeSlice(s2, start, end)
+	actual = bm2.SliceRange(start, end)
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("slice range:\n from %v to %v in slice %v and bitmap %v:\n expected %v\n got %v",
+			start, end, s2, bm2.Slice(), expected, actual))
+	}
+
+	expect = uint64(len(intersectSlice(s1, s2)))
+	got = bm1.IntersectionCount(bm2)
+	if expect != got {
+		panic(fmt.Sprintf("intersection count:\n expected %v got %v", expect, got))
+	}
+
+	_, found := containedInSlice(s1, rand)
+	if found != bm1.Contains(rand) {
+		panic(fmt.Sprintf("contains:\n %v contains %v: %v\n %v contains %v: %v", s1, rand, found,
+			bm1.Slice(), rand, bm1.Contains(rand)))
+	}
+	_, found = containedInSlice(s2, rand)
+	if found != bm2.Contains(rand) {
+		panic(fmt.Sprintf("contains:\n %v contains %v: %v\n %v contains %v: %v", s2, rand, found,
+			bm2.Slice(), rand, bm2.Contains(rand)))
+	}
+
+	if end-start < maxFlips {
+		expected = flipSlice(s1, start, end)
+		actual = bm1.Flip(start, end).Slice()
+		if !reflect.DeepEqual(expected, actual) {
+			panic(fmt.Sprintf("flip:\n from %v to %v in slice %v and bitmap %v\n expected %v\n got %v",
+				start, end, s1, bm1.Slice(), expected, actual))
+		}
+		expected = flipSlice(s2, start, end)
+		actual = bm2.Flip(start, end).Slice()
+		if !reflect.DeepEqual(expected, actual) {
+			panic(fmt.Sprintf("flip:\n from %v to %v in slice %v and bitmap %v\n expected %v\n got %v",
+				start, end, s2, bm2.Slice(), expected, actual))
+		}
+	}
+
+	expected = make([]uint64, 0)
+	actual = make([]uint64, 0)
+	forEachInSlice(s1, func(v uint64) { expected = append(expected, v) })
+	bm1.ForEach(func(v uint64) { actual = append(actual, v) })
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("for each:\n expected %v\n got %v", expected, actual))
+	}
+	expected = make([]uint64, 0)
+	actual = make([]uint64, 0)
+	forEachInSlice(s2, func(v uint64) { expected = append(expected, v) })
+	bm2.ForEach(func(v uint64) { actual = append(actual, v) })
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("for each:\n expected %v\n got %v", expected, actual))
+	}
+
+	expected = make([]uint64, 0)
+	actual = make([]uint64, 0)
+	forEachInRangeSlice(s1, start, end, func(v uint64) { expected = append(expected, v) })
+	bm1.ForEachRange(start, end, func(v uint64) { actual = append(actual, v) })
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("for each in range:\n expected %v\n got %v", expected, actual))
+	}
+	expected = make([]uint64, 0)
+	actual = make([]uint64, 0)
+	forEachInRangeSlice(s2, start, end, func(v uint64) { expected = append(expected, v) })
+	bm2.ForEachRange(start, end, func(v uint64) { actual = append(actual, v) })
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("for each in range:\n expected %v\n got %v", expected, actual))
+	}
+
+	// Impure functions
+	// The following tests operations that mutate bitmaps.
+
+	nbm1, nbm2 := bm1.Clone(), bm2.Clone()
+	expected = shiftSlice(s1, 1)
+	tempBM, _ := nbm1.Shift(1)
+	actual = tempBM.Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("shift:\n in slice %v and bitmap %v \n expected %v\n got %v",
+			s1, bm1.Slice(), expected, actual))
+	}
+	expected = shiftSlice(s2, 1)
+	tempBM, _ = nbm2.Shift(1)
+	actual = tempBM.Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("shift:\n in slice %v and bitmap %v \n expected %v\n got %v",
+			s2, bm2.Slice(), expected, actual))
+	}
+
+	// reuse start and end as random values
+	rand2 := start
+	rand3 := end
+
+	nbm1 = bm1.Clone()
+	expected, echanged := addNToSlice(s1, rand)
+	achanged := nbm1.DirectAddN(rand)
+	actual = nbm1.Slice()
+	if echanged != achanged || !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("directAddN:\n adding %v in slice %v and bitmap %v \n expected %v and %v changed \n got %v and %v changed",
+			rand, s1, bm1.Slice(), expected, echanged, actual, achanged))
+	}
+	nbm2 = bm2.Clone()
+	expected, echanged = addNToSlice(s2, rand2, rand3)
+	achanged = nbm2.DirectAddN(rand2, rand3)
+	actual = nbm2.Slice()
+	if echanged != achanged || !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("directAddN:\n adding %v and %v in slice %v and bitmap %v \n expected %v and %v changed \n got %v and %v changed",
+			rand2, rand3, s2, bm2.Slice(), expected, echanged, actual, achanged))
+	}
+
+	nbm1 = bm1.Clone()
+	expected, echanged = removeNFromSlice(s1, rand2, rand3)
+	achanged = nbm1.DirectRemoveN(rand2, rand3)
+	actual = nbm1.Slice()
+	if echanged != achanged || !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("directRemoveN\n removing %v and %v in slice %v and bitmap %v \n expected %v and %v changed \n got %v and %v changed",
+			rand2, rand3, s1, bm1.Slice(), expected, echanged, actual, achanged))
+	}
+	nbm2 = bm2.Clone()
+	expected, echanged = removeNFromSlice(s2, rand)
+	achanged = nbm2.DirectRemoveN(rand)
+	actual = nbm2.Slice()
+	if echanged != achanged || !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("directRemoveN:\n removing %v in slice %v and bitmap %v \n expected %v and %v changed \n got %v and %v changed",
+			rand, s2, bm2.Slice(), expected, echanged, actual, achanged))
+	}
+
+	nbm1, nbm2 = bm1.Clone(), bm2.Clone()
+	expected = unionSlice(s1, s2)
+	nbm1.UnionInPlace(nbm2)
+	actual = nbm1.Slice()
+	if !reflect.DeepEqual(expected, actual) {
+		panic(fmt.Sprintf("union in place:\n expected %v\n got %v", expected, actual))
+	}
+
+	return 1
+}
+
+func bytesToUint64s(data []byte) []uint64 {
+	const uint64Size = 8
+	size := len(data) / uint64Size
+
+	slice := make([]uint64, 0)
+	for i := 0; i < size; i++ {
+		offset := i * uint64Size
+		num := binary.LittleEndian.Uint64(data[offset : offset+uint64Size])
+		slice = append(slice, num)
+	}
+	return slice
+}
+
+// copy and paste the following to a main file to run.
+// path should be the absolute path to the corpus.
+// make sure filename is not already in the corpus.
+func addSliceToCorpus(slice []uint64, filename, path string) {
+	data := uint64sToBytes(slice)
+	err := ioutil.WriteFile(path+"/"+filename, data, 0777)
+	if err != nil {
+		fmt.Printf("could not write to file: %v\n", err)
+	}
+}
+
+func uint64sToBytes(slice []uint64) []byte {
+	const uint64Size = 8
+	size := len(slice) * uint64Size
+
+	data := make([]byte, size)
+	for i := 0; i < len(slice); i++ {
+		offset := i * uint64Size
+		binary.LittleEndian.PutUint64(data[offset:offset+uint64Size], slice[i])
+	}
+	return data
+}
diff --git a/roaring/naive.go b/roaring/naive.go
new file mode 100644
index 00000000..14b6cfe4
--- /dev/null
+++ b/roaring/naive.go
@@ -0,0 +1,321 @@
+// Copyright 2017 Pilosa Corp.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package roaring
+
+import (
+	"math"
+	"sort"
+)
+
+// The following functions reimplement Roaring Bitmap methods, but done naively on
+// uint64 slices. Most of these functions are inefficient, which is acceptable because
+// this is purely for testing consistency with Roaring internal operations. Thus, the
+// functions should be easily guaranteed to produce the correct results.
+
+func sortSlice(slice []uint64) {
+	sort.Slice(slice, func(i, j int) bool { return slice[i] < slice[j] })
+}
+
+// removeSliceDuplicates removes duplicate values
+// in the slice and sorts the output.
+func removeSliceDuplicates(slice []uint64) []uint64 {
+	// just throw slice into a map and
+	// get the values out again
+	hash := make(map[uint64]bool)
+	for _, val := range slice {
+		hash[val] = true
+	}
+	unique := make([]uint64, 0)
+	for key := range hash {
+		unique = append(unique, key)
+	}
+
+	if len(unique) == 0 {
+		return nil
+	}
+	sortSlice(unique)
+	return unique
+}
+
+// intersect intersects two []uint64s, removing any duplicates
+// and sorting the final output.
+func intersectSlice(s1, s2 []uint64) []uint64 {
+	// throw both slices in maps
+	hash1 := make(map[uint64]bool)
+	for _, val := range s1 {
+		hash1[val] = true
+	}
+	hash2 := make(map[uint64]bool)
+	for _, val := range s2 {
+		hash2[val] = true
+	}
+
+	intersection := make([]uint64, 0)
+
+	// look for keys from hash1 also in hash2
+	for key := range hash1 {
+		if _, found := hash2[key]; found {
+			intersection = append(intersection, key)
+		}
+	}
+
+	if len(intersection) == 0 {
+		return nil
+	}
+	sortSlice(intersection)
+	return intersection
+}
+
+// union unions two []uint64s and sorts the output.
+func unionSlice(s1, s2 []uint64) []uint64 {
+	// just dump both slices in a map
+	// and get the values out again
+	hash := make(map[uint64]bool)
+	for _, val := range s1 {
+		hash[val] = true
+	}
+	for _, val := range s2 {
+		hash[val] = true
+	}
+	union := make([]uint64, 0)
+
+	for key := range hash {
+		union = append(union, key)
+	}
+
+	if len(union) == 0 {
+		return nil
+	}
+	sortSlice(union)
+	return union
+}
+
+// maxSlice returns the max in the slice.
+func maxInSlice(slice []uint64) uint64 {
+	if len(slice) == 0 {
+		return 0
+	}
+
+	max := uint64(0)
+	for _, val := range slice {
+		if val > max {
+			max = val
+		}
+	}
+	return max
+}
+
+// differenceSlice returns a slice containing the values
+// present in the first slice but not in the second.
+func differenceSlice(s1, s2 []uint64) []uint64 {
+	// throw s2 in a map, check if each value
+	// in s1 is also in that map
+	hash := make(map[uint64]bool)
+	for _, val := range s2 {
+		hash[val] = true
+	}
+	diff := make([]uint64, 0)
+	for _, val := range s1 {
+		if _, found := hash[val]; !found {
+			diff = append(diff, val)
+		}
+	}
+	// make sure duplicates in s1 are not added
+	diff = removeSliceDuplicates(diff)
+	return diff
+}
+
+// xorSlice returns an array containing the values
+// present in exactly one of the two slices.
+func xorSlice(s1, s2 []uint64) []uint64 {
+	// throw both slices in maps
+	hash1 := make(map[uint64]bool)
+	for _, val := range s1 {
+		hash1[val] = true
+	}
+	hash2 := make(map[uint64]bool)
+	for _, val := range s2 {
+		hash2[val] = true
+	}
+
+	xor := make([]uint64, 0)
+	// add all values in hash1 not in hash2
+	for key := range hash1 {
+		if _, found := hash2[key]; !found {
+			xor = append(xor, key)
+		}
+	}
+	// add all values in hash2 not in hash1
+	for key := range hash2 {
+		if _, found := hash1[key]; !found {
+			xor = append(xor, key)
+		}
+	}
+
+	if len(xor) == 0 {
+		return nil
+	}
+	sortSlice(xor)
+	return xor
+}
+
+// shiftSlice adds n to each element and sorts the slice, but ignores any values that
+// will cause an overflow. This does not modify the original slice, unlike the Roaring implementation.
+func shiftSlice(slice []uint64, n int) []uint64 {
+	shifted := make([]uint64, 0)
+	for _, val := range slice {
+		if uint64(n) <= math.MaxUint64-val {
+			shifted = append(shifted, val+uint64(n))
+		}
+	}
+
+	if len(shifted) == 0 {
+		return nil
+	}
+	sortSlice(shifted)
+	return shifted
+}
+
+// forEachSlice executes fn for each element in the slice.
+func forEachInSlice(slice []uint64, fn func(uint64)) {
+	for _, val := range slice {
+		fn(val)
+	}
+}
+
+// forEachRangeSlice executes fn for each element in slice that is in [start, end).
+func forEachInRangeSlice(slice []uint64, start, end uint64, fn func(uint64)) {
+	for _, val := range slice {
+		if start <= val && val < end {
+			fn(val)
+		}
+	}
+}
+
+// containedInSlice returns the index of the first instance of v and true
+// if v is in slice and returns -1 and false otherwise.
+func containedInSlice(slice []uint64, v uint64) (int, bool) {
+	for idx := range slice {
+		if v == slice[idx] {
+			return idx, true
+		}
+	}
+	return -1, false
+}
+
+// addNToSlice adds the contents of a to slice and returns the new slice and
+// number of values successfully added. This somewhat mimics *Bitmap.DirectAddN
+// and but does not modify slice in place, so it returns that new slice instead.
+func addNToSlice(slice []uint64, a ...uint64) ([]uint64, int) {
+	newSlice := make([]uint64, len(slice))
+	copy(newSlice, slice)
+	changed := 0
+
+	for _, val := range a {
+		if _, found := containedInSlice(newSlice, val); !found {
+			newSlice = append(newSlice, val)
+			changed++
+		}
+	}
+
+	if len(newSlice) == 0 {
+		return nil, changed
+	}
+	sortSlice(newSlice)
+	return newSlice, changed
+}
+
+// removeNFromSlice removes the contents of a from slice and returns the new slice and
+// number of values successfully removed. This somewhat mimics *Bitmap.DirectRemoveN
+// and but does not modify slice in place, so it returns that new slice instead.
+func removeNFromSlice(slice []uint64, a ...uint64) ([]uint64, int) {
+	newSlice := make([]uint64, len(slice))
+	copy(newSlice, slice)
+	changed := 0
+
+	for _, val := range a {
+		if i, found := containedInSlice(newSlice, val); found {
+			newSlice = append(newSlice[:i], newSlice[i+1:]...)
+			changed++
+		}
+	}
+
+	if len(newSlice) == 0 {
+		return nil, changed
+	}
+	sortSlice(newSlice)
+	return newSlice, changed
+}
+
+// countRangeSlice returns the number of values in slice that are in [start, end).
+func countRangeSlice(slice []uint64, start, end uint64) uint64 {
+	count := uint64(0)
+	for _, val := range slice {
+		if start <= val && val < end {
+			count++
+		}
+	}
+	return count
+}
+
+// rangeSlice returns a sorted slice of integers between [start, end).
+func rangeSlice(slice []uint64, start, end uint64) []uint64 {
+	newSlice := make([]uint64, 0)
+	for _, val := range slice {
+		if start <= val && val < end {
+			newSlice = append(newSlice, val)
+		}
+	}
+
+	if len(newSlice) == 0 {
+		return nil
+	}
+	sortSlice(newSlice)
+	return newSlice
+}
+
+// flipSplice returns a slice containing all numbers in [start, end]
+// that are not in the original slice, as well as the numbers in the
+// original slice not in [start, end].
+func flipSlice(slice []uint64, start, end uint64) []uint64 {
+	if start > end {
+		sortSlice(slice)
+		return slice
+	}
+
+	flipped := make([]uint64, 0)
+	// add values in slice outside [start, end]
+	hash := make(map[uint64]bool)
+	for _, val := range slice {
+		hash[val] = true
+	}
+	for val := range hash {
+		if val < start || val > end {
+			flipped = append(flipped, val)
+		}
+	}
+
+	for i := start; i <= end; i++ {
+		if _, found := containedInSlice(slice, i); !found {
+			flipped = append(flipped, i)
+		}
+	}
+
+	if len(flipped) == 0 {
+		return nil
+	}
+	sortSlice(flipped)
+	return flipped
+}
diff --git a/roaring/roaring.go b/roaring/roaring.go
index d0c2f5f2..f55cbc4a 100644
--- a/roaring/roaring.go
+++ b/roaring/roaring.go
@@ -431,7 +431,7 @@ func (b *Bitmap) Size() int {
 
 // CountRange returns the number of bits set between [start, end).
 func (b *Bitmap) CountRange(start, end uint64) (n uint64) {
-	if roaringParanoia {
+	if roaringSentinel {
 		if start > end {
 			panic(fmt.Sprintf("counting in range but %v > %v", start, end))
 		}
@@ -494,7 +494,7 @@ func (b *Bitmap) Slice() []uint64 {
 
 // SliceRange returns a slice of integers between [start, end).
 func (b *Bitmap) SliceRange(start, end uint64) []uint64 {
-	if roaringParanoia {
+	if roaringSentinel {
 		if start > end {
 			panic(fmt.Sprintf("getting slice in range but %v > %v", start, end))
 		}
@@ -1271,7 +1271,7 @@ func (b *Bitmap) Check() error {
 
 // Flip performs a logical negate of the bits in the range [start,end].
 func (b *Bitmap) Flip(start, end uint64) *Bitmap {
-	if roaringParanoia {
+	if roaringSentinel {
 		if start > end {
 			panic(fmt.Sprintf("flipping in range but %v > %v", start, end))
 		}
diff --git a/roaring/roaring_nop_sentinel.go b/roaring/roaring_nop_sentinel.go
new file mode 100644
index 00000000..daa0b266
--- /dev/null
+++ b/roaring/roaring_nop_sentinel.go
@@ -0,0 +1,19 @@
+// Copyright 2017 Pilosa Corp.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build !roaringsentinel
+
+package roaring
+
+const roaringSentinel = false
diff --git a/roaring/roaring_sentinel.go b/roaring/roaring_sentinel.go
new file mode 100644
index 00000000..47cbf21f
--- /dev/null
+++ b/roaring/roaring_sentinel.go
@@ -0,0 +1,19 @@
+// Copyright 2017 Pilosa Corp.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build roaringsentinel
+
+package roaring
+
+const roaringSentinel = true


Test patch:
diff --git a/roaring/naive_test.go b/roaring/naive_test.go
new file mode 100644
index 00000000..154d0f8f
--- /dev/null
+++ b/roaring/naive_test.go
@@ -0,0 +1,459 @@
+// Copyright 2017 Pilosa Corp.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package roaring
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestSortSlice(t *testing.T) {
+	tests := []struct{ a, expected []uint64 }{
+		{
+			a:        []uint64{1, 3, 2, 8, 5, 21, 13},
+			expected: []uint64{1, 2, 3, 5, 8, 13, 21},
+		},
+	}
+
+	for _, test := range tests {
+		sortSlice(test.a)
+		if !reflect.DeepEqual(test.a, test.expected) {
+			t.Fatalf("unexpected sorting: %v", test.a)
+		}
+	}
+}
+
+func TestRemoveSliceDuplicates(t *testing.T) {
+	tests := []struct{ a, expected []uint64 }{
+		{
+			a:        []uint64{2, 3, 2, 1, 2, 5, 8, 5, 13, 3, 2, 5, 144},
+			expected: []uint64{1, 2, 3, 5, 8, 13, 144},
+		},
+		{
+			a:        []uint64{2, 3, 2, 1, 2, 5, 8, 5, 13, 3, 2, 5, 144, 21, 8, 3, 3, 5, 5, 1, 34, 21, 21},
+			expected: []uint64{1, 2, 3, 5, 8, 13, 21, 34, 144},
+		},
+	}
+
+	for _, test := range tests {
+		got := removeSliceDuplicates(test.a)
+		if !reflect.DeepEqual(got, test.expected) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestIntersectSlice(t *testing.T) {
+	tests := []struct{ a, b, expected []uint64 }{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{1, 5, 9},
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{1, 5, 9},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{1, 5, 9},
+			expected: []uint64{1, 5, 9},
+		},
+	}
+
+	for _, test := range tests {
+		got := intersectSlice(test.a, test.b)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestUnionSlice(t *testing.T) {
+	tests := []struct{ a, b, expected []uint64 }{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{1, 2, 4, 5, 9, 12, 13, 24},
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{1, 2, 4, 5, 9, 12, 13, 24},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{1, 5, 9},
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+		},
+	}
+
+	for _, test := range tests {
+		got := unionSlice(test.a, test.b)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestMaxInSlice(t *testing.T) {
+	a := []uint64{1, 4, 9, 5, 24, 13}
+	v := maxInSlice(a)
+	if uint64(24) != v {
+		t.Fatalf("expected %v, but got %v", uint64(24), v)
+	}
+
+	for i := uint64(1000); i <= uint64(100000); i++ {
+		a = append(a, i)
+		if v = maxInSlice(a); v != i {
+			t.Fatalf("expected %v, but got %v", i, v)
+		}
+	}
+}
+
+func TestDifferenceSlice(t *testing.T) {
+	tests := []struct{ a, b, expected []uint64 }{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{4, 13, 24},
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{2, 12},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64(nil),
+		},
+	}
+
+	for _, test := range tests {
+		got := differenceSlice(test.a, test.b)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestXorSlice(t *testing.T) {
+	tests := []struct{ a, b, expected []uint64 }{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{2, 4, 12, 13, 24},
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{2, 4, 12, 13, 24},
+		},
+		{
+			a:        []uint64{2, 4, 12, 13, 24},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{1, 2, 5, 9, 12},
+		},
+		{
+			a:        []uint64{2, 4, 12, 13, 24},
+			b:        []uint64{1, 2, 5, 9, 12},
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+		},
+	}
+
+	for _, test := range tests {
+		got := xorSlice(test.a, test.b)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestShiftSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		shift    int
+		expected []uint64
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			shift:    12,
+			expected: []uint64{13, 16, 17, 21, 25, 36},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			shift:    0,
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			shift:    1,
+			expected: []uint64{2, 5, 6, 10, 14, 25},
+		},
+	}
+
+	for _, test := range tests {
+		got := shiftSlice(test.a, test.shift)
+
+		if !reflect.DeepEqual(got, test.expected) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestForEachInSlice(t *testing.T) {
+	a := []uint64{1, 4, 9, 5, 24, 13}
+	c := make([]uint64, 0)
+
+	forEachInSlice(a, func(v uint64) {
+		c = append(c, v+1)
+	})
+	if !reflect.DeepEqual(c, []uint64{2, 5, 10, 6, 25, 14}) {
+		t.Fatalf("unexpected values: %v", c)
+	}
+}
+
+func TestForEachInRangeSlice(t *testing.T) {
+	a := []uint64{1, 4, 9, 5, 24, 13}
+	c := make([]uint64, 0)
+
+	forEachInRangeSlice(a, uint64(3), uint64(12), func(v uint64) {
+		c = append(c, v+1)
+	})
+	if !reflect.DeepEqual(c, []uint64{5, 10, 6}) {
+		t.Fatalf("unexpected values: %v", c)
+	}
+}
+
+func TestContainedInSlice(t *testing.T) {
+	tests := []struct {
+		a     []uint64
+		c     uint64
+		index int
+		found bool
+	}{
+		{
+			a:     []uint64{1, 4, 9, 5, 24, 13},
+			c:     uint64(4),
+			index: 1,
+			found: true,
+		},
+		{
+			a:     []uint64{1, 4, 9, 5, 24, 13},
+			c:     uint64(12),
+			index: -1,
+			found: false,
+		},
+	}
+
+	for _, test := range tests {
+		idx, found := containedInSlice(test.a, test.c)
+		if found != test.found {
+			t.Fatalf("expected value of found: %v, got %v", test.found, found)
+		}
+		if idx != test.index {
+			t.Fatalf("expected index %v, got %v", test.index, idx)
+		}
+	}
+}
+
+func TestAddNToSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		b        []uint64
+		expected []uint64
+		changed  int
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{1, 2, 4, 5, 9, 12, 13, 24},
+			changed:  2,
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{1, 2, 4, 5, 9, 12, 13, 24},
+			changed:  3,
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+			changed:  0,
+		},
+	}
+
+	for _, test := range tests {
+		got, changed := addNToSlice(test.a, test.b...)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected slices %v, got %v", test.expected, got)
+		}
+		if changed != test.changed {
+			t.Fatalf("expected changed %v, got %v", test.changed, changed)
+		}
+	}
+}
+
+func TestRemoveNFromSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		b        []uint64
+		expected []uint64
+		changed  int
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{2, 1, 9, 5, 12},
+			expected: []uint64{4, 13, 24},
+			changed:  3,
+		},
+		{
+			a:        []uint64{2, 1, 9, 5, 12},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64{2, 12},
+			changed:  3,
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			b:        []uint64{1, 4, 9, 5, 24, 13},
+			expected: []uint64(nil),
+			changed:  6,
+		},
+	}
+
+	for _, test := range tests {
+		got, changed := removeNFromSlice(test.a, test.b...)
+		if !reflect.DeepEqual(test.expected, got) {
+			t.Fatalf("expected slices %v, got %v", test.expected, got)
+		}
+		if changed != test.changed {
+			t.Fatalf("expected changed %v, got %v", test.changed, changed)
+		}
+	}
+}
+
+func TestCountRangeSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		start    uint64
+		end      uint64
+		expected uint64
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(3),
+			end:      uint64(12),
+			expected: uint64(3),
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(0),
+			end:      uint64(25),
+			expected: uint64(6),
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(12),
+			end:      uint64(4),
+			expected: uint64(0),
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(4),
+			end:      uint64(4),
+			expected: uint64(0),
+		},
+	}
+
+	for _, test := range tests {
+		got := countRangeSlice(test.a, test.start, test.end)
+		if got != test.expected {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestRangeSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		start    uint64
+		end      uint64
+		expected []uint64
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(3),
+			end:      uint64(12),
+			expected: []uint64{4, 5, 9},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(0),
+			end:      uint64(25),
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(5),
+			end:      uint64(5),
+			expected: []uint64(nil),
+		},
+	}
+
+	for _, test := range tests {
+		got := rangeSlice(test.a, test.start, test.end)
+		if !reflect.DeepEqual(got, test.expected) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}
+
+func TestFlipSlice(t *testing.T) {
+	tests := []struct {
+		a        []uint64
+		start    uint64
+		end      uint64
+		expected []uint64
+	}{
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(3),
+			end:      uint64(12),
+			expected: []uint64{1, 3, 6, 7, 8, 10, 11, 12, 13, 24},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(13),
+			end:      uint64(12),
+			expected: []uint64{1, 4, 5, 9, 13, 24},
+		},
+		{
+			a:        []uint64{1, 4, 9, 5, 24, 13},
+			start:    uint64(9),
+			end:      uint64(13),
+			expected: []uint64{1, 4, 5, 10, 11, 12, 24},
+		},
+	}
+
+	for _, test := range tests {
+		got := flipSlice(test.a, test.start, test.end)
+		if !reflect.DeepEqual(got, test.expected) {
+			t.Fatalf("expected %v, got %v", test.expected, got)
+		}
+	}
+}