Piece Table in Go

In my ultimate yak shaving quest I started working on a shell. So far nothing new. I also added a file manager that is built into the shell or can be run standalone. Here is the thing I learned so far (beside how easy it is to mess up a terminal when putting it into "raw mode"): Having a single binary is pretty neat. I can scp to any server and have not just my shell with a few handy built in commands but also the file manager ready to go!

The other app I use most of the time when connected to a remote system is a text editor. (By now I think you can see where this is going.)

I am a long time (neo)vim user. And I am mostly happy except that I basically need a distribution to get neovim into a workable shape without having random plugin upgrades break my editor every other week. So for the fun of it, let’s assume that I would like to write one myself. Taking a critical look at my usual workflow actually shows I do not need a lot of features for my daily driver:

• edit text (duh) including undo and redo
• LSP integration
• syntax highlighting even for large files
• easy text navigation (does not need to be modal)
• fast text search, project wide
• a file explorer (might be optional)

Yeah, I know. This list is so basic, it celebrates Starbucks pumpkin spice latte. The file explorer mostly depends on how good the editor can react to files being moved around outside of the editor. I am not sure how easily solvable this is. But the rest ist very much not a big deal, I am feeling pretty comfortable with Bubbletea at this point. An LSP integration is fairly easy, I have built one for my coding agent. Syntax highlighting is implemented for the file manager preview, but might struggle with large files.

Piece Table

I am aware of two commonly used data structures for editors, piece tables and ropes. I have implemented ropes in the past. They are pretty neat for thread safe operations and concurrent editing, but this isn't something we will ever do in my little editor. Piece tables should be more memory efficient and in real world tests perform better. I am not sure if the difference will be too noticeable on systems I am using. But the promise of not having to balance trees (this is an editor after all, not a job interview at a startup cosplaying as FAANG), simple undo and redo and the option to mmap an external file instead of reading the whole file into memory seem pretty appealing.

The data structure itself is nothing too fancy.

type BufferType uint8

const (
        BufferOriginal BufferType = iota
        BufferAdd
)

type Piece struct {
        Buffer BufferType
        Start  int
        Length int
}

type PieceTable struct {
        original string
        add      strings.Builder
        pieces   []Piece
        length   int
}

We keep track if a piece of text in the piece table was from the original file or was added. Piece tables are append only, so we need to know where to get the piece of text from when building the whole representation of the original file and all edits on top.

func (pt *PieceTable) String() string {
        var sb strings.Builder
        sb.Grow(pt.length)
        addStr := pt.add.String()

        for _, p := range pt.pieces {
                if p.Buffer == BufferOriginal {
                        sb.WriteString(pt.original[p.Start : p.Start+p.Length])
                } else {
                        sb.WriteString(addStr[p.Start : p.Start+p.Length])
                }
        }

        return sb.String()
}

When we render the whole string all we have to do is iterate over all pieces and add the relevant substring with a pieces start and length to our strings.Builder. This should also give you an idea how to implement insert and delete methods.

func (pt *PieceTable) Insert(text string, offset int) {
        if len(text) == 0 {
                return
        }

        addStart := pt.add.Len()
        pt.add.WriteString(text)
        np := Piece{
                Buffer: BufferAdd,
                Start:  addStart,
                Length: len(text),
        }

        if len(pt.pieces) == 0 {
                pt.pieces = append(pt.pieces, np)
                pt.length += np.Length
                return
        }

        pID, pOffset := pt.findPosition(offset)

        if pID >= len(pt.pieces) {
                pt.pieces = append(pt.pieces, np)
        } else if pOffset == 0 { // insert before current piece
                pos := append([]Piece{np}, pt.pieces[pID:]...)
                pt.pieces = append(pt.pieces[:pID], pos...)
        } else { // split existing piece into two and insert in between
                cur := pt.pieces[pID]

                left := Piece{
                        Buffer: cur.Buffer,
                        Start:  cur.Start,
                        Length: pOffset,
                }

                right := Piece{
                        Buffer: cur.Buffer,
                        Start:  cur.Start + pOffset,
                        Length: cur.Length - pOffset,
                }

                nps := make([]Piece, 0, len(pt.pieces)+2)
                nps = append(nps, pt.pieces[:pID]...)
                nps = append(nps, left, np, right)
                nps = append(nps, pt.pieces[pID+1:]...)
                pt.pieces = nps
        }

        pt.length += np.Length
}

Inserting text comes down to adding it to the add StringBuilder and figuring out where to insert a new Piece to the pieces slice and keeping track of the start and offset.

func (pt *PieceTable) Delete(offset, length int) {
        if length <= 0 || offset < 0 || offset >= pt.length {
                return
        }

        sID, sOffset := pt.findPosition(offset)
        eID, eOffset := pt.findPosition(offset + length)

        nps := append([]Piece{}, pt.pieces[:sID]...)

        if sOffset > 0 {
                p := pt.pieces[sID]
                nps = append(nps, Piece{
                        Buffer: p.Buffer,
                        Start:  p.Start,
                        Length: sOffset,
                })
        }

        if eID < len(pt.pieces) {
                if eOffset > 0 {
                        p := pt.pieces[eID]
                        nps = append(nps, Piece{
                                Buffer: p.Buffer,
                                Start:  p.Start + eOffset,
                                Length: p.Length - eOffset,
                        })
                } else {
                        nps = append(nps, pt.pieces[eID:]...)
                }
        }

        pt.pieces = nps
        pt.length -= length
}

Deleting does not modify add - remember: append only - it simply gets the Piece in the correct state.

A test to replace some text shows how the pieces slice grows.

t.Run("replace", func(t *testing.T) {
        pt := newPieceTable("Hello World")
        pt.Insert(" cruel", 5)
        pt.Delete(5, 6)
        pt.Insert(" beautiful", 5)

        if pt.String() != "Hello beautiful World" {
                t.Error("Expected 'Hello beautiful World', got: ", pt.String())
        }

        t.Log(pt.pieces)
})

// output: [{0 0 5} {1 6 10} {0 5 6}]

This is basically all to it. We now have a simple way to manage text edits on a string with O(N) time complexity for indexing and search and O(1) for edits with only minimal overhead. Not too bad for what is a total of 160 lines of code.

As add and original will be reset whenever a file is saved I am not too worried about an ever growing strings.Builder. If I ever do a multi day edit session of a single file without saving things are likely pretty bad and you should send help. Running out of memory will be the least of my problems. I know some editors mix a tree a balanced tree in to get to O(leg N) time complexity, but I really do not fancy the additional work till I see it being necessary.

Progress

The side quests continue to pile up and are a very fun distraction. They might all be selected to cover a few things I either never had to deal with or did not touch in a very long time, so I really do not want to complain.

I am currently looking into Godot. It seems like a good enough alternative for what I am planning to do for Endirillia considering it is mostly rendering a single character in a little world. Having an open source engine and not dealing with Unity and its build pipeline are two pretty good arguments in its favor. I also do not intend to ever work professionally on a game, so there is no "side effect" for getting deeper into Unity.