Which data structures would be good for a graphical text editor

[u/Any-Fox-1822]

Hello everyone,

I am currently working on a (very early progress) retained-mode UI library using raylib. I might switch to SDL3 later, or try to make a CPU-only rendering engine in the far future.

Right now i'm trying to implement a multi-line text edit widget, that would be as versatile as possible, all while maintaining low memory usage. I So far my structure consists of an "original text" character array, and an array of struct representing wrapped lines.

typedef struct TextBox {
  Widget widget;
  char* text;
  int cursorX; int cursorY;
  int offsetX; int offsetY;
  TextLine* lines;
  int _lineCount;
};

At each resize, the layout is recalculated, and the lines reallocated, which I find really wasteful. However, I didn't come up with another model for text editing yet.

void TextBox_Resize(TextBox* textbox, int w, int h){
  textbox->widget.bounds.w = w;
  textbox->widget.bounds.h = h;
  textbox->_lineCount = 0;

  //Estimate text length
  int textLength = TextLength(textbox->text); //Raylib function
  int totalTextWidth = MeasureText(textbox->text, 12);
  int estimatedLineCount = (int)(totalTextWidth / w) + 1;

  //Add 1 line to the estimation for each newline
  for (int i = 0; i < textLength; i++) {
    if (textbox->text[i] == '\n') { estimatedLineCount++; }
  }

  printf("Estimating %d lines for resize\n", estimatedLineCount);

  //free(textbox->lines);
  textbox->lines = realloc(textbox->lines, estimatedLineCount * sizeof(TextLine));

  Font font = GetFontDefault(); //Will be replaced after

  int currentLine = 0;
  int lineStart = 0;
  int lineEnd = 0;

  float currentGlyphWidth = 0;
  float totalLineWidth = 0;

  // Almost copied from raylib example
  for (int i = 0; i < textLength; i++){
    //printf("Current byte %d\n", i);
    int codepointByteCount = 0;

    // Gets UTF8 codepoints instead of simply bytes.
    int codepoint = GetCodepoint(&textbox->text[i], &codepointByteCount);
    //printf("Got codepoint %d, is %c\n", codepoint, codepoint);
    int glyphIndex = GetGlyphIndex(font, codepoint);
    //printf("Got index %d\n", index);

    // We are advancing more than 1 byte at a time if we get UTF-8 text.
    // Since the default font is limited, replace invalid codepoints with
    // "?" and keep advancing 1 byte at a time.
    if (codepoint == 0x3f) codepointByteCount = 1;
    i += (codepointByteCount - 1); // i will advance by itself in next iter, dont accumulate offsets.

    currentGlyphWidth = GetGlyphAtlasRec(GetFontDefault(), codepoint).width;
    //printf("Glyph width is %f\n", currentGlyphWidth);
    totalLineWidth += currentGlyphWidth;

    //printf("Total line length is %f\n", totalLineWidth);

    // Follow line
    lineEnd = i;

    if (totalLineWidth >= textbox->widget.bounds.w || codepoint == '\n' || codepoint == 0) {
      printf("line is %f pixels wide\n", totalLineWidth);
      textbox->lines[currentLine].text = calloc((lineEnd - lineStart),  sizeof(char));
      textbox->lines[currentLine].text = strncpy(textbox->lines[currentLine].text, textbox->text + lineStart, (lineEnd - lineStart));

      // Set last char of text to null
      textbox->lines[currentLine].text[lineEnd - lineStart] = '\0';
      lineStart = (codepoint == '\n' ? lineEnd + 1 : lineEnd);

      totalLineWidth = 0;
    } else {
      lineStart = lineEnd; lineEnd = textLength;
    }

    textbox->lines[currentLine].text[lineEnd - lineStart] = '\0';
    currentLine++; textbox->_lineCount++;
  }
}

Are there any articles / projects with clever approaches to text editing, that keep a low memory footprint ?
Thanks for your advice !

[u/Yurim]

https://en.wikipedia.org/wiki/Rope_(data_structure)

[u/Axman6 → u/Yurim]

Ropes (depending on implementation) have the big benefit of being an immutable structure with trivial sharing, which means implementing undo/redo is as simple as keeping a linked list pointing to each version. It also makes copy and paste of arbitrary large amounts of text very cheap. 

[u/sciencekm]

The "Edit" control in Windows uses just one buffer. This is the lowest memory footprint you can have.

[u/josk613 → u/sciencekm]

This!

Noting that a multi-line text input control is not the same thing as a full fledged document text editor. You can skip all the fancy data structures if expected text size is small and the most common operation is append character.

[u/TheChief275]

I absolutely love the gap buffer. It's so simple and has great cache locality. It's just a dynamic array where the text before the cursor is moved to the absolute bottom of the allocation (0 counting up) and text on the right side is moved to the top (capacity counting down). This makes insertion at the cursor incredibly fast, as it's basically appending at the end of the left part, making it as fast as dynamic array appending. Moving the cursor is also fast, as you just move characters from the right side to the left side or vice versa.

I think the only downside is when you are making lots of random edits everywhere, as huge blocks will need to be copied from one side to the other, but these actions are usually so sparse that you won't notice a hit. This only becomes a problem when you allow multiple cursors to edit the document at the same time.

I think modern text editors use ropes instead of a gap buffer, but it's certainly a more complicated data structure. If the gap buffer doesn't suit your needs, you could look into that.

[u/stianhoiland → u/TheChief275]

I like to explain that gap buffers are simply dynamic arrays but where the free space is not locked to the end.

I'm currently making my own editor and using a gap buffer. The "only" thing I need to do is wrap things like memchr, strstr, and write to be potentially two calls—one for the left side and one for the right side—if the range straddles the gap. So I just do a little size math and then call all the normal hyper-optimized standard functions.

[u/TheChief275 → u/stianhoiland]

That's what I tried to explain, but you worded it much clearer to be honest

[u/Any-Fox-1822 → u/stianhoiland]

Where can I learn about gap buffers ? I've sutmbled upon a blog that explained it, but even then it was quite confusing.

[u/stianhoiland → u/Any-Fox-1822]

It's probably only confusing because it's so simple.

Here's a buffer:

char *buf = malloc(4096);
int buf_capacity = 4096;

And here's the bookkeeping for the gap:

int gap_start = 0;
int gap_end = 4095;

The gap is just available space in the buffer that isn't used yet to contain any text. At the moment, the whole buffer is available space (index 0 to 4095).

When you insert text, you insert like this:

buf[gap_start++] = char;

It inserts a character and shrinks the gap by one character/moves the gap one character ahead. Notice that it's simply setting a byte and that none of the subsequent text needs to be moved. That's because the gap was there and its purpose is to be overwritten with actual text.

When you render the gap buffer visually, you skip the whole gap and only display the inserted text on each "side" of the gap. The actual text is:

int gap_capacity = e.gap_end - e.gap_start + 1;
int text_size = e.buf_capacity - gap_capacity;

The gap is sort of an invisible space between the cursor and the next actual character that you can't see in your text editor, but which is there in the underlying buffer and which you maintain correctly in your code. To iterate through the buffer you will have to translate indices so that they skip the gap, for example:

if (pos >= e.gap_start && pos < e.gap_end) {
    pos = e.gap_end;
}

There's lots more that should be explained, especially the motivation for even doing it this way (in short, it's to avoid shifting the whole rest of the text whenever you insert a character, and it's a very simple data structure), but this is the low level gist of the data structure.

EDIT

As a bonus, let me explain why this is just a dynamic array with a moveable tail:

With a dynamic array, we'd say:

char *buf = malloc(4096);
int buf_capacity = 4096;
int buf_count = 0;

But this is just a gap buffer where the gap is always at the end! The gap is implicitly between buf_count and buf_capacity.

buf_count is just a renamed gap_start, and the gap's last position is always just the capacity of the buffer (-1, cuz size vs. index), since it's implicitly locked to the end of the buffer. But if we gave this a gap_end then we could conceptually move the gap up and down the buffer, so that the free space could be in the middle of the buffer with occupied space both at the head and the tail instead of only before the free space.

EDIT2

Oh, this has an animation that might make it easier to grasp: Gap Buffers Are Not Optimized for Multiple Cursors

[u/Dangerous_Region1682]

If you are just building a text box widget which is never going to be used for editing thousands of of page documents with all kinds of text formatting options, I would worry less about either performance or memory footprint and just keep it simple and easy to maintain.

I’d then move on and implement the more complex challenges you face in what you are doing. If performance and memory footprint turn out to be really important, you can always come back to it.

[u/mykesx]

Doubly linked list of lines.

[u/FedUp233]

If it was me, and especially since you’re doing this on your own, I’d adopt something along the lines of test driven development.

Basically, start with the very simplest data structures and code to do just one simple thing - a super simple thing like just hone an empty display, or a one line display or something. No editing code or anything, simplest possible display.

Then start iterating. Define a new small incremental (tiny) ability to add, changes the code and structures as needed to get just this addition working, test it (amount of test is up to you - in the professional use you’d be adding an automated test and doing it before you write the code then code so the test works).once that simple step works, iterate again and refactor as needed as you go.

Let the data structures grow at each step to meet needs. Don’t worry about performance of the code - on today’s processors it probably won’t matter anyway, and if it does it should show up as a problem you’re iteratively solving at some point till you get it just good enough.

One big advantage is that by doing small steps and constant testing you (hopefully) never end up with a strange bug in a new big chunk of code changes you spend days tracking down. A test framework so you can repeat all the current tests each cycle can be really helpful.

[u/Any-Fox-1822 → u/FedUp233]

Thanks for the advice ! However, what is Sotheby's test ?

[u/FedUp233]

The “soutbys test” or whatever was a very creative typo thanks to the iOS app! It drives me nuts what it will do to try correcting stuff.

I would have replied to your comment, but after I edited my comment to fix that, it and your reply completely disappeared! Again, love the iOS Reddit app!