chewxy/skiprope

package skiprope is a rope-like data structure built on top of skiplists

SkipRope

package skiprope is an implementation of the rope data structure. It's not strictly a rope as per se. It's not built on top of a binary tree like most rope data structures are.

Instead it's built on top of a skip list. This makes it more akin to a piece table than a true rope.

This library is quite complete as it is (it has all the functions and I need for my projects). However, any addition, corrections etc are welcome. Please see CONTRIBUTING.md for more information on how to contribute.

Installing

This package is go-gettable: go get -u github.com/chewxy/skiprope.

This package is versioned with SemVer 2.0, and does not have any external dependencies except for testing (of which the fantastic assert package is used).

Usage

r := skiprope.New()
if err := r.Insert(0, "Hello World! Hello, 世界"); err != nil {
	// handle error
}
if err  := r.Insert(5, "there "); err != nil {
	// handle error
}
fmt.Println(r.String()) // "Hello there World! Hello, 世界"

FAQ

How do I keep track of row, col information?

The best way is to use a linebuffer data structure in conjunction with the Rope:

type Foo struct{
	*skiprope.Rope
	linebuf []int
}

The linebuf is essentially a list of offsets to a newline character. The main reason why I didn't add a linebuf slice into the *Rope data structure is because while it's a common thing to do, for a couple of my projects I didn't need it. The nature of Go's composable data structure and programs make it quite easy to add these things. A pro-tip is to extend the Insert, InsertRunes and EraseAt methods.

I do not think it to be wise to add it to the core data structure.

When is *Rope going to implement io.Writer and io.Reader?

The main reason why I didn't do it was mostly because I didn't need it. However, I've been asked about this before. I personally don't have the bandwidth to do it.

Please send a pull request :)

Benchmarks

There is a benchmark mini-program that is not required for the running, but here are the results:

go test -run=^$ -bench=. -benchmem -cpuprofile=test.prof
BenchmarkNaiveRandomInsert-8   	   50000	     37774 ns/op	      15 B/op	       0 allocs/op
BenchmarkRopeRandomInsert-8    	 3000000	       407 ns/op	      27 B/op	       0 allocs/op
BenchmarkERopeRandomInsert-8   	 1000000	      2143 ns/op	    1161 B/op	      25 allocs/op
PASS

Fuzz testing

Guard against crashing for certain inputs by running fuzz tests. First, build the instrumented binaries for the tests and then run them.

$ go-fuzz-build github.com/chewxy/skiprope
$ go-fuzz -bin=skiprope-fuzz.zip -workdir=workdir

History, Development and Acknowledgements

This package started its life as a textbook binary-tree data structure for another personal project of mine. Over time, I decided to add more and more optimizations to it. The original design had a split at every new-line character.

I started by moving more and more things off the heap, and onto the stack. As I wondered how to incorporate a search structure using a skiplist, I stumbled onto a well developed library for C, librope.

It had everything I had wanted: a rope-like structure, using skiplists to find nodes, minimal allocations on heap, and a solution to my problem wrt keeping the skiplists off heap. The solution turned out to be to be the skiplist data structure, without a pointer. So I ended up adapting most of Joseph Gentle's algorithm. So this library owes most of its work to Joseph Gentle.

Hours before releasing this library, I had a consult by Egon Elbre, who gave good advice on whether just sticking with []rune was a good idea. He managed to convince me that it isn't, so the first pull request was made to update this library to deal with []byte instead. As a result, memory use went down 40B/op at the cost of an increase of about 30 ns/op. The number can be further shaved down with better optimizations.

skiprope's Issues

String() crashes with an incomplete (?) ending byte

Discovered adding fuzz tests with #8

Reproducing test:

func TestIncompleteLast(t *testing.T) {
    a := "00000000000000000000" +
        "00000000000000000000" +
        "00000000000000000000" +
        "000\xcb"

    r := New()
    if err := r.Insert(0, a); err != nil {
        t.Fatal(err)
    }

    assert.Equal(t, a, r.String())
}

--- FAIL: TestIncompleteLast (0.00s)
panic: runtime error: slice bounds out of range [recovered]
        panic: runtime error: slice bounds out of range

goroutine 11 [running]:
testing.tRunner.func1(0xc420102690)
        /home/codegoalie/workspace/sources/go/src/testing/testing.go:711 +0x2d2
panic(0x6f86c0, 0x94c330)
        /home/codegoalie/workspace/sources/go/src/runtime/panic.go:491 +0x283
github.com/codegoalie/skiprope.(*Rope).SubstrBytes(0xc420104900, 0x0, 0x40, 0x0, 0xc420299600, 0x40)
        /home/codegoalie/workspace/go/src/github.com/codegoalie/skiprope/rope.go:107 +0x3b0
github.com/codegoalie/skiprope.(*Rope).Substr(0xc420104900, 0x0, 0x40, 0x4e5b01, 0xc420104900)
        /home/codegoalie/workspace/go/src/github.com/codegoalie/skiprope/rope.go:121 +0x3f
github.com/codegoalie/skiprope.(*Rope).String(0xc420104900, 0x0, 0x75c744)
        /home/codegoalie/workspace/go/src/github.com/codegoalie/skiprope/rope.go:186 +0x3d
github.com/codegoalie/skiprope.TestIncompleteLast(0xc420102690)
        /home/codegoalie/workspace/go/src/github.com/codegoalie/skiprope/rope_test.go:212 +0x17d
testing.tRunner(0xc420102690, 0x764360)
        /home/codegoalie/workspace/sources/go/src/testing/testing.go:746 +0xd0
created by testing.(*T).Run
        /home/codegoalie/workspace/sources/go/src/testing/testing.go:789 +0x2de
exit status 2
FAIL    github.com/codegoalie/skiprope  0.011s

Suggestion for tracking lines does not work

On the subject of "How do I keep track of row, col information?", the README suggests:

The best way is to use a linebuffer data structure in conjunction with the Rope:

type Foo struct{
	*skiprope.Rope
	linebuf []int
}

The linebuf is essentially a list of offsets to a newline character.

This doesn't work. More precisely, it technically works, but doing this negates the advantages of using a rope in the first place. The reason is that maintaining the linebuf array when the rope is modified is an O(n) operation in the average case, where n is the number of lines. Under standard assumptions (bounded line length), this makes inserting into and deleting from the rope an O(n) operation in the length of the text – and we are back to zero. At this point, the "rope" is just a very complicated string.

Rope implementations designed for line-based editing store line count information directly in the binary tree's nodes, in addition to the fragment length. This allows for line operations with a complexity of O(log(n)). Of course, instead of a line array as suggested, one could use a binary tree to externally track lines, but that would entail mirroring the rope's internal structure outside of it, which is extremely ugly.

It appears, then, that the correct answer to the question "How do I keep track of row, col information?" is currently "Use a different package", which is rather unfortunate because all other rope implementations written in Go that I am aware of suffer from the same shortcoming (unlike e.g. ropey, which gets this right).

Go-Fuzz this library

Implementation left to whoever who's interested in picking this up

Move to use `[]byte`

Per @egonelbre's advice:

1. Create two loops: one for byte handling, one for rune handling - once the continuation bit has been detected, fallback onto rune handling loop

Add `io.WriterTo` methods

There should be THREE io.WriterTo methods:

• WriteTo(w io.Writer) (n int64, err error)
• WriteToSubstr(w io.Writer, pointA, pointB int) error

The latter is essentially SubstrBytes but writing it to a io.Writer

Add `io.Reader` methods

Add `io.Writer` method