v0.4.0
Text · Lesson 14.5

String builder

Source
Build text a piece at a time in one growing buffer with StringBuilder, then hand it over as a String with TakeString.

A String has no way to add to its text — it can be cleared or replaced whole, but never appended to. Building text a piece at a time out of Strings alone would mean making a new String at every step and copying everything built so far into it — the longer the text, the more each step costs. StringBuilder is the tool for that job. It keeps one growing buffer, appends into it, and asks the allocator for a larger one only when the room runs out. When the text is finished, it hands the buffer over as a String.

Length and capacity

A builder tracks two numbers: Length, the text so far, and Capacity, the room for it. A new builder has allocated nothing yet; its buffer appears with the first append.

var builder = StringBuilder(allocator);

Join appends the colours one at a time and reports both numbers after each:

func Join(builder: &var StringBuilder, words: char8[..][..]) {
    for i in 0..words.length {
        if i > 0 {
            let separator = if i == words.length - 1 { " and " } else { ", " };
            builder.Append(separator);
        }
        builder.Append(words[i]);
        PrintLine("added {}: {} bytes, room for {}", words[i], builder.Length(),
            builder.Capacity());
    }
}
After addingLengthCapacityWhat happened
red316the first buffer is allocated
orange1116fits; only the new bytes copied
yellow1932out of room: the buffer doubles
green2632fits
blue3564doubles again

The room doubles each time it runs out, so most appends copy just the bytes being added, and the rare move to a bigger buffer gets rarer as the text grows.

The builder is passed as &var StringBuilder — a mutable reference — so Join grows the caller's builder rather than a copy of it.

Which appends can throw

Appending text cannot fail. The text was checked when it was made, and a builder that cannot grow ends the program, as every allocation in a String does — so Join needs no throws and no try at all. Appending a single character is different: a char32 may hold a value that is no character at all, so AppendScalar declares throws TextError, and its call is marked with try, which passes the error on to Main.

MethodAppendsThrows?
Append(text)a char8[..] or a StringViewno
AppendScalar(c)one character, any char32, encoded as UTF-8TextError, for a non-character
AppendAscii(byte)one ASCII char8TextError, for a non-ASCII byte
builder.Append(" ");
try builder.AppendScalar('✓');

The check mark is one character but three UTF-8 bytes, which is why the finished text is 39 bytes, not 37.

Taking the text out

View looks at the text so far without taking it — a string view of the builder's buffer. TakeString hands the buffer itself to a String, without copying a byte, and leaves the builder empty, ready to build something else:

PrintLine("view    {}", builder.View());

let sentence = builder.TakeString();
PrintLine("string  {}", sentence.View());
PrintLine("builder now holds {} bytes", builder.Length());
flowchart LR
    b["`StringBuilder`<br/>buffer: 39 bytes"] -- "`View()`<br/>borrow, no copy" --> v["`StringView`"]
    b -- "`TakeString()`<br/>hand over the buffer;<br/>builder left empty" --> s["`String`<br/>owns the 39 bytes"]
    b -- "`ToString()`<br/>copy the bytes" --> c["`String`<br/>a copy; builder keeps its text"]
MethodReturnsCopies?Builder afterwards
View()StringViewnounchanged
TakeString()Stringnoempty
ToString()Stringyesunchanged

None of the three throws. TakeString allocates nothing; ToString allocates the copy, and like every allocation in a String ends the program if memory runs out.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

Src/Main.rux
// A `String` cannot grow: it can be cleared or replaced whole, but never appended to, so building
// text a piece at a time out of Strings alone would copy everything built so far at every step.
// `StringBuilder` is the tool for that job. It keeps one growing buffer, appends into it, and asks
// the allocator for a larger one only when the room runs out. `Length` is the text so far and
// `Capacity` the room for it. The room doubles each time it runs out, so most appends copy just
// the bytes being added, and the rare move to a bigger buffer gets rarer as the text grows.
//
// Appending text cannot fail: text was checked when it was made, and a builder that cannot grow
// ends the program, as every allocation in a String does. Appending a single character can, since
// a `char32` may hold a value that is no character at all, so `AppendScalar` declares
// `throws TextError`. When the text is finished, `TakeString` hands the buffer over as a String
// without copying it.
import Allocator::SystemAllocator;
import Io::PrintLine;
import Text::{ StringBuilder, TextError };

// Joins words into a list a person would write: "a, b and c". The builder is borrowed `&var`,
// so the caller's builder is the one that grows. Watch the room: 16, then 32, then 64.
func Join(builder: &var StringBuilder, words: char8[..][..]) {
    for i in 0..words.length {
        if i > 0 {
            let separator = if i == words.length - 1 { " and " } else { ", " };
            builder.Append(separator);
        }
        builder.Append(words[i]);
        PrintLine("added {}: {} bytes, room for {}", words[i], builder.Length(),
            builder.Capacity());
    }
}

func Main() throws TextError {
    let allocator = SystemAllocator();

    // A new builder has allocated nothing yet. Its buffer appears with the first append.
    var builder = StringBuilder(allocator);
    let colours: char8[..][5] = ["red", "orange", "yellow", "green", "blue"];
    Join(builder, colours);

    // Single characters go in with `AppendScalar`, which encodes any character as UTF-8 and
    // refuses a value that is not one.
    builder.Append(" ");
    try builder.AppendScalar('✓');

    // `View` looks at the text so far without taking it.
    PrintLine("view    {}", builder.View());

    // `TakeString` hands the buffer itself to a String. The builder is left empty, ready to
    // build something else.
    let sentence = builder.TakeString();
    PrintLine("string  {}", sentence.View());
    PrintLine("builder now holds {} bytes", builder.Length());
}

Besides Io, its Rux.toml lists Allocator and Text under [Dependencies].

Run it

cd Examples/Text/StringBuilder
rux run
added red: 3 bytes, room for 16
added orange: 11 bytes, room for 16
added yellow: 19 bytes, room for 32
added green: 26 bytes, room for 32
added blue: 35 bytes, room for 64
view    red, orange, yellow, green and blue ✓
string  red, orange, yellow, green and blue ✓
builder now holds 0 bytes

Common mistakes

Try it yourself

  1. Replace TakeString with ToString() and see what the last line prints now.
  2. Make the builder with StringBuilder::WithCapacity(allocator, 64) instead. How do the room for numbers change?
  3. Write Repeat(builder: &var StringBuilder, text: char8[..], count: int) and use it to build a line of 40 dashes. Does it need throws?
  4. After TakeString, build a second sentence in the same builder.

Learn more