Panic in Delete

[achille-roussel]

I've ran into a case where the delete code path appears to panic within the llrb package:

panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x100bc7b40]

goroutine 7 [running]:
testing.tRunner.func1.2({0x100d5dd60, 0x100f44d30})
	/usr/local/go/src/testing/testing.go:1209 +0x258
testing.tRunner.func1(0x1400008d040)
	/usr/local/go/src/testing/testing.go:1212 +0x284
panic({0x100d5dd60, 0x100f44d30})
	/usr/local/go/src/runtime/panic.go:1038 +0x21c
github.com/petar/GoLLRB/llrb.flip(...)
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:417
github.com/petar/GoLLRB/llrb.moveRedRight(0x1400016fa40)
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:434 +0x30
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400016fa40, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:361 +0x25c
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400017eea0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018a0c0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018bda0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001567f0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:328 +0x40

It seems that moveRedRight requires both the left and right children to exist https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L432, but here only the right child is tested https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L359-L362?

[resam72]

i get the same issue
here is a sample code that shows this

in this code i'm trying to implement a kind of MFU cache

i'm using the KCounter where the KCounter.value is the frequency of the KCounter.key

the tree holds only N keys with the highest frequency , when there is no more room left the key with the minimal frequency will be dropped

const maxCacheSize = 3

type KCounter struct {
	key   string
	value int
}

func (t KCounter) Less(than llrb.Item) bool {
	counter := than.(KCounter)
	if t.key < counter.key {
		return true
	}
	return t.value < counter.value
}

func Test_A(t *testing.T) {

	put := func(t *llrb.LLRB, itemByKey map[string]KCounter, kc KCounter) bool {

		item, ok := itemByKey[kc.key]
		if ok {
			//update the value by re-inserting it
			t.Delete(item)
			t.ReplaceOrInsert(kc)
			itemByKey[kc.key] = kc
			return true
		}
		if t.Len() >= maxCacheSize {
			smallestItem := t.Min().(KCounter)
			if kc.value < smallestItem.value {
				//dont add group that have values that are smaller than the smallest elem in tree
				return false
			}
			t.DeleteMin()
		}
		t.ReplaceOrInsert(kc)
		itemByKey[kc.key] = kc
		return true

	}

	itemByKey := make(map[string]KCounter)
	tree := llrb.New()

	for i := 0; i < 100000; i++ {
		put(tree, itemByKey, KCounter{strconv.Itoa(i % 20), i % 10})
	}

}

this result in

panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x102c393dc]

goroutine 35 [running]:
testing.tRunner.func1.2({0x102f08580, 0x10323fb40})
	/opt/homebrew/opt/go/libexec/src/testing/testing.go:1545 +0x1c4
testing.tRunner.func1()
	/opt/homebrew/opt/go/libexec/src/testing/testing.go:1548 +0x360
panic({0x102f08580?, 0x10323fb40?})
	/opt/homebrew/opt/go/libexec/src/runtime/panic.go:914 +0x218
github.com/petar/GoLLRB/llrb.flip(...)
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:417
github.com/petar/GoLLRB/llrb.moveRedRight(0x140000e6b18?)
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:434 +0x2c
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000991e8?, 0x1400009c510, {0x102f80818, 0x14000099d40})
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:361 +0x2a4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000e6c18?, 0x1400009c510, {0x102f80818, 0x14000099d40})
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x14000099d40?, 0x1400009c780, {0x102f80818, 0x14000099d40})
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000e6d01?, 0x1400009c780, {0x102f80818, 0x14000099d40})
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001ebdc8, {0x102f80818?, 0x14000099d40?})
	/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:328 +0x38
xdr.panw/ipl/internal/dml/cronus/throttler.Test_frequentKeyCounterTracker1.func1(0x140001ebdc8, 0x103177850?, {{0x102e1242d, 0x1}, 0x8})
	/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:325 +0xa0
xdr.panw/ipl/internal/dml/cronus/throttler.Test_frequentKeyCounterTracker1(0x1?)
	/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:348 +0xe0
testing.tRunner(0x1400008a820, 0x102f7d1f0)
	/opt/homebrew/opt/go/libexec/src/testing/testing.go:1595 +0xe8
created by testing.(*T).Run in goroutine 1
	/opt/homebrew/opt/go/libexec/src/testing/testing.go:1648 +0x33c


Process finished with the exit code 1