multiple inserts of `nil` panics

[ingon]

Great library!

Saw the following panic in my usage:

package main

import (
	art "github.com/plar/go-adaptive-radix-tree"
)

func main() {
	tree := art.New()

	tree.Insert(art.Key("Hi, I'm Key"), "Nice to meet you, I'm Value")
	tree.Insert(art.Key(nil), "Meet you again")
	tree.Insert(art.Key(nil), "Meet you again") // panic
}

https://go.dev/play/p/G6tYWq0QzpJ

And the resulting trace:

panic: runtime error: slice bounds out of range [1:0]

goroutine 1 [running]:
github.com/plar/go-adaptive-radix-tree.(*tree).recursiveInsert(0xc00009ae60?, 0xc000106050, {0x0, 0x0, 0x0}, {0x46e6e0?, 0x496e98}, 0x1)
	/tmp/gopath331505154/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree.go:120 +0x5d7
github.com/plar/go-adaptive-radix-tree.(*tree).recursiveInsert(0xc00010a000?, 0xc00009af60, {0x0, 0x0, 0x0}, {0x46e6e0?, 0x496e98}, 0x0)
	/tmp/gopath331505154/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree.go:175 +0x293
github.com/plar/go-adaptive-radix-tree.(*tree).Insert(0xc00009af58, {0x0?, 0x404bd9?, 0x60?}, {0x46e6e0?, 0x496e98?})
	/tmp/gopath331505154/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree.go:15 +0x48
main.main()
	/tmp/sandbox249177140/prog.go:12 +0xc5

Looking to investigate further, the documentation hints that nil should be supported as a key.

[plar]

Thanks for your bug report.

the documentation hints that nil should be supported as a key.

Do you mean the following line?

Support for keys with null bytes, any byte array could be a key

in that case it is about C-strings (C-string is a sequence of chars terminated with a null character '\x00'). See example below.

package main

import (
	"fmt"
	art "github.com/plar/go-adaptive-radix-tree"
)

func main() {
	tree := art.New()
	tree.Insert(art.Key("key"), "value")
	k := art.Key("\x00")
	o1, u1 := tree.Insert(k, "v1")
	fmt.Println("insert =>", o1, u1)

	v1, f1 := tree.Search(k)
	fmt.Println("search =>", v1, f1)

	o2, u2 := tree.Insert(k, "v2")
	fmt.Println("insert2 =>", o2, u2)

	v2, f2 := tree.Search(k)
	fmt.Println("search2 =>", v2, f2)
}

https://go.dev/play/p/34_CyP2Zo47

Do you really think that nil should be supported as a valid key value?
I'm not sure if I want to support it but I couldn't find any counter arguments against it.
Let me sleep on it. I'll try to fix it in someway as soon as I have time.

Feel free to submit PR.

[plar]

This turned out to be a very easy fix. See v1.0.5 for updates.

[ingon]

Thanks for the fix, this is great!

By documentation, yeah I mean the bit about any byte array could be a key part, I understand that the 0-byte is different.

Do you really think that nil should be supported as a valid key value?

I was fine either way, it was just showing inconsistent behavior. In case art didn't support nils:

• It should be noted in docs/godoc
• Users of the library would have to take that into account
• The library should be fast-failing the first time you try, as oppose to work the first time and fail afterward.

In any case, it is great this turned out to be an easy fix. Thanks for taking the time to do it.