Text Buffer Research

M0 — Buffer (@rawmark/buffer)

I don't have an exact goal with this document; I'm kind of just doing research and familiarizing myself with what a text buffer is and how it's going to fit into the application. Really, just getting my thoughts out there.

I started off looking into which data structure is the best for a text buffer but learned through research that I was looking at the problem wrong altogether, which makes sense because it started off as a pretty open-ended question. But we're locking in on what we're actually looking for. What isn't important is the data structure; what is important is the data, regardless of the data structure. The input/output remains the same, and that's something I think I overlooked. So, I don't need the fastest data structure out of the gate or the best data structure at the outset. I don't know what that looks like yet. It would be hard to optimize for that at this stage, if not impossible.

As far as researching which data structure, I'm going to default to flat string to get the ball rolling, and create a baseline for performance. This document will focus more on technical decisions around the SDK for the text buffer itself, like; what will the methods look like? I know there are underlying decisions as well that need to be made when designing a text buffer. That's what I'm still researching more about. And we'll use this document to answer those questions.

What is a text buffer? A text buffer is the data structure holding a documents text in memory. This data structure could be optimized so that inserting and deleting characters anywhere in the document stays fast, regardless of document size

Starting off with researching what text buffer data structure is most compatible for a markdown interface.

: Plain Array / String (baseline), Rope, Line Array / Array of Lines, Gap Buffer, and Piece Table as solutions.

Objectives

This is a large, but focused research effort with defined objectives.

• Be able to comprehend each text buffer data structure, document known pros/ cons with sources
• test correctness, invariants, API shape, and workload realism
• Publish the pros and cons found during benchmark testing (to a blog on this repo)
• Implement buffer data structure for rawmark
• Which algo is the best for the use-case? (Be able to explain pros/cons of each in conversation, and writing)

Reading Materials

• https://en.wikipedia.org/wiki/Piece_table
• https://en.wikipedia.org/wiki/Rope_%28data_structure%29
• https://learn.microsoft.com/en-us/dotnet/api/microsoft.visualstudio.text.itextbuffer?view=visualstudiosdk-2022
• https://zed.dev/blog/zed-decoded-rope-sumtree
• https://www.cs.unm.edu/~crowley/papers/sds/sds.html - Charles Crowley, "Data Structures for Text Sequences" (1998)
• https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
• https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf
• https://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table
• https://developer.mozilla.org/en-US/docs/Glossary/Buffer

Notes

• Note to self; these are called text buffer data structures or text sequence representations, not algorithms.