The Challenge of Strings
Strings are one of those things we take for granted in most languages. It’s not until you’re working in a language like C that you really come to appreciate how much complexity they hide. It wasn’t until I was working on Conjure that I really came to understand the challenge they pose.
Let’s start with the fact that strings often exist directly in a language’s grammar as a string literal1. At this stage, we almost view "my string" as a simple value like 42. But they’re not simple. Even at this stage, we’ve secretely allocated a block of read-only data "my string" has become a pointer to that .rodata’s address.
For strings created at runtime, we typically need to perform a heap allocation2 and they’re usually variably sized, unless you pin them to a fixed array like char[64]. We also want to compare them constantly, whether that’s a plain == or as the cases in a switch. Then there are substrings, which are often just a naked view into another string’s memory. And all of that is before you even get to formats like ASCII versus UTF-8.
#Trying to make strings safer
One of the approaches I explored involved storing a tag on the string that drives its runtime behavior based on how it was obtained. Let’s start with its simplest form:
typedef struct {
u8 tag : 2; /// Runtime tag defining the strings behavior.
u64 len : 62; /// Length of the string.
u8 *data; /// Pointer to the data the string represents.
} cjrString;
String Immutability
It’s worth noting that a
stringin Conjure is immutable. This makes a number of memory semantics significantly simpler, especially when borrowing or techniques like reference-counting are involved.
At the very start of the string is a 2-bit tag. This is the critical piece, because it identifies the rules the string plays by.
In Conjure, free() is a compiler-intrinsic that can directly accept strings. When a string is handed to free(), it calls the runtime function cjrString_free(), which starts by switching on the tag field. The tag can be in one of the following states:
| Value | Description |
|---|---|
0 | It’s a string literal whose pointer lives in .rodata |
1 | Standard heap allocated string created from a helper like string.new() or string.from() |
2 | Borrowed string whose pointer lives in another string’s memory, like from string.slice() |
3 | Potentially reserved for “small string optimization” |
In my opinion, this solves a number of potential bugs when you’re manually managing memory. You can safely free() any string and never accidentally free one you don’t own.
The tag is also cheap. A string is only 16 bytes on a 64-bit system. And if I do eventually implement automatic reference counting just for strings, the tag stays useful for avoiding operations that would otherwise require me to interrogate the string by first following its pointer.
Small string optimization could push this further. With a union employed efficiently, all the space outside the 2-bit tag becomes possible string storage, giving you up to 14 bytes of small string before you ever touch the heap.
#Another little big detail
Conjure’s string is still NUL-terminated for easy C-interop with const char*, at least when the tag is 0 or 1. The same cannot be said if the tag is 2 (borrowed) or 3 (sso).
This is why the runtime has the cjrString_toC() wrapper function to handle the different types of strings and obtain a valid C-compatible const char* pointer. Borrowed strings often won’t end at the same NUL-terminator the source string does, since a substring can sit in the middle of another string entirely.
#Closing thoughts
I’ve gone back and forth on this for a while, but for Conjure I’d love for the user to fully treat string as a value type. Something that’s managed for you, rather than a pointer type you’re in charge of managing yourself. How this will happen is still a problem I’m actively trying to solve.