search

sminez / ad

an adaptable text editor
https://crates.io/crates/ad-editor
MIT License
264 stars 10 forks source link

Investigate alternative backing data structures for buffers #6

Closed sminez closed 1 month ago

sminez commented 2 months ago

At first I used ropey for the underlying buffer data structure but I've since swapped that out for a simple gap buffer implementation instead. That works fine for current purposes but isn't ideal for things like multiple cursors which would make parts of the exec engine more efficient. When moving away from ropey I took a look at a variety of data structures and settled on a gap buffer as the simplest to implement that achieved what I needed from it. One of the other data structures I looked at was a piece table which is worth revisiting now that things are a little easier to abstract / rework over the underlying buffer data structure.

This paper is a good introduction to piece tables.

sminez commented 1 month ago

Another alternative is to use the block / disk approach used by sam and acme that is described here: http://doc.cat-v.org/plan_9/4th_edition/papers/sam/

The source for this in the go implementation of acme is found here: https://github.com/9fans/go/blob/main/cmd/acme/internal/disk/disk.go

sminez commented 1 month ago

Closing for now until there is a need for a different data structure. The gap buffer impl is very simple but easily meets the current requirements of the project.