26
$\begingroup$

Languages developed over the last fifteen years or so have been within the era where Unicode is ubiquitous, and so could design their core string types accordingly. There are a lot of new issues that Unicode brings up, and I'm interested in how they've been traded off in different designs. I've listed some of the dimensions of those design choices below the line.

I'm looking for instances of different real-world general-purpose languages released from around 2008 onwards addressing Unicode in their strings. Languages that I know released fitting in that group and made relevant design choices include Rust, Swift, Go, Raku, and Python 3, but there are surely others too. What did these languages decide to do with their string type(s), and if applicable how has that been received by programmers?

References to design documentation, rationale, or notable reception are welcome.


Unicode raises a number of questions and design choices that the preceding history of languages leaning on predominantly byte or 16-bit strings in platform-dependent encodings didn't. For example:

  • Encoding: Are strings stored in UTF-8, UTF-16, UTF-32, a combination, or something else? Is that made visible to the user?
  • Characters: What is the atomic unit of a string, if anything? It may be a byte, a code unit, a code point, a grapheme cluster, or something else.
  • Indexing: Possibly related, what are the semantics and ergonomics of indexing into a string ("give me character 5", or from 5 on), if there is any? Iteration may also be relevant.
  • Normalisation: Are strings automatically normalised internally into some canonical form?
  • Equality: When are two strings considered equal? Encoding or normalisation of the value may matter here, or may be abstracted away.
  • Ordering: When does one string precede another for comparison or sorting operations?

Any given language might deliberately deal with only some of these. A variety of different reasonable designs are available for each, with tradeoffs for different combinations. I'm interested in what design choices were made and what the implications and reception of those choices by users of the language were, if that's notable.

I'm thinking about the run-time string values here, so language syntax for strings is relevant only as far as it's directly supporting the semantics (for example, syntactic support for different forms of indexing or specifying different encodings on a string literal).

$\endgroup$
1
  • 2
    $\begingroup$ I can't help but say this to prospective language designers as a grumpy user of programming languages: if your core string type is UTF-8 (which is fine) you better give your users good tools in your standard library to manipulate common things (like file paths) that may not be valid UTF-8. Lookin at you golang/node.js. $\endgroup$ Oct 25, 2023 at 16:23

6 Answers 6

22
$\begingroup$

Swift

Swift strings are complicated. At the time of writing, the implementation of Swift.String is split across more than 30 files in the standard library, and that's not counting things that need to be handled in the compiler (like string literals) or Objective-C (like NSString).

In Swift, the stack-/register-allocated storage of a String is 16 bytes. It's a tagged union of one of a few things:

  • An NSString, which is an abstract class from Objective-C. Usually this stores immutable UTF-16, but it can use a number of other encodings such as ASCII or UTF-32. This member of the union only exists on Apple's platforms, since Objective-C interop is not supported on Windows or Linux.
  • If the string is no more than 15 bytes in UTF-8 with no null terminator, the first n bytes are its UTF-8 representation, the next 15 - n bytes are all zeroes, and the low nibble of the last byte is the string's length (source).
  • A pointer to a copy-on-write, resizable, null-terminated UTF-8 buffer (docs and source). Sometimes, there's a "breadcrumbs" pointer after the null terminator, but more on that later.
  • If the optimizer can prove the string does not grow arbitrarily large or escape the current stack frame, it uses an owned stack buffer rather than a CoW heap buffer (forum post).
  • A pointer to an "immortal" UTF-8 buffer that the Swift runtime can't modify even to resize, i.e. a string literal (source).

But, we're here to talk Unicode, so let's talk Unicode.

Character

A Character in Swift is an extended grapheme cluster (docs). This can be more than one Unicode codepoint, but it always looks like a single character. Examples of multi-codepoint characters include \r\n (yes, I know) and ('e' + U+0301). If you want a single Unicode codepoint, that type is Unicode.Scalar, which is just a wrapper around UInt32 (source).

In terms of storage, a Character is stored exactly the same way as a String! (source)

@frozen
public struct Character: Sendable {
  @usableFromInline
  internal var _str: String

  @inlinable @inline(__always)
  internal init(unchecked str: String) {
    self._str = str
    _invariantCheck()
  }
}

count

In Swift 3, String.count gave a very specific error message (example):

'count' is unavailable: there is no universally good answer, see the documentation comment for discussion

However, starting in Swift 4, it is available. .count is an O(n) operation that counts the number of extended grapheme clusters in the string (docs). This is consistent with the fact that String implements Sequence<Character> -- String.count is the number of Characters in the String.

String Views

Swift offers a number of views on a string that don't allocate new storage:

  • String.unicodeScalars is a Sequence<Unicode.Scalar> rather than a Sequence<Character>, but otherwise operates in much the same way as the original String (docs). General-purpose string algorithms are intentionally not available for this type.
  • String.utf16 is a Sequence<UInt16> (docs). If the string is stored in another format, this converts one value at a time as you iterate over it (source).
  • String.utf8 is a Sequence<UInt8> (docs). It offers fast access to the raw bytes for a String that's already in UTF-8, and converts an NSString one value at a time as needed (source).

Breadcrumbs

In order to speed up repeated accesses to utf16, UTF-8 strings may put a breadcrumbs pointer after the null terminator (source). The breadcrumbs are a list of the UTF-8 offsets of every 64th UTF-16 code unit (source). A string stores whether it has breadcrumbs in an unused bit in its capacity field (source).

Indexing

Swift Strings aren't indexable by an integer, the way an Array is. Instead, there's a specific type String.Index that's used to avoid the O(n) index access UTF-8 would normally impose. To summarize, it's the following 64-bit bitfield (listed in order from MSb to LSb; source):

  • a 48-bit number ("position" or "encoded offset") that is the raw offset in the underlying buffer;
  • a 2-bit number ("transcoded offset") that's the location within the Unicode scalar, when applicable (e.g. if it points to the third byte of a 4-byte UTF-8 character);
  • ten bits that are purely private and not even used by the ABI (the "resilient slice") -- at the time of writing, only six of them are used, and it stores the distance to the next grapheme cluster, if known; and
  • four single-bit flags, for which '1' is true and '0' is either false or unknown:
    • the underlying buffer is UTF-16,
    • the underlying buffer is UTF-8,
    • the index points to a boundary between Characters (_isCharacterAligned), and
    • the index points to a boundary between Unicode scalars (_isScalarAligned).

Before Swift 5.7, the resilient slice was thirteen bits, and included what is now the first three of the four flags.

This layout reduces the overhead of advancing the index forwards by spreading out when the UTF-8 is interpreted. The resilient slice also allows some room for the implementation to improve while still being ABI-stable.

String Literals

A literal like "a" could be any of the following types:

  • String, obviously.
  • Substring, less obviously (docs). A Substring is just a slice of a String, but it isn't an unowned slice: it keeps the original String alive (docs). This allows Substrings to be expressed with string literals.
  • NSString (docs).
  • Character, if it's only one grapheme cluster (docs).
  • Unicode.Scalar, if it's only one Unicode codepoint (docs). This is converted to UTF-32 so that it's always four bytes.
  • StaticString, which is either a pointer to some constant UTF-8 data in the binary, or in some rare cases, a single character in UTF-32 (docs). This is generally used for things you want to know at compile-time, like the file name passed to assert(_:_:line:file:).

Equality and Normalization

String equality is elementwise equality of its Characters*. Character equality is not bytewise equality. Character equality uses the canonical normalized form, but Characters are not automatically normalized (example):

import Foundation

func printRawBytes(_ c: Character) {
  let ints = unsafeBitCast(c, to: (UInt64, UInt64).self)
  print(String(format: "0x%.16llX%.16llX", ints.0.bigEndian, ints.1.bigEndian))
}

let precomposed: Character = "é"
printRawBytes(precomposed) // 0xC3A900000000000000000000000000A2

let combining: Character = "é"
printRawBytes(combining) // 0x65CC81000000000000000000000000A3

print(precomposed == combining) // true

Strings that use an external buffer set a bit in the class header when they are known to already be NFC normalized (source). This can speed up certain operations: for example, two strings that use the same encoding and are both normalized can be compared bytewise.

*While this is semantically true, that's not how the Swift stdlib actually implements it. Instead, Character equality delegates to String equality, and String equality is its own mess.

Ordering

String equality is relatively straightforward: do the strings represent the same text? However, Strings can also be compared for order: str1 < str2 is legal. While it's generally preferred to use methods like localizedStandardCompare for user-facing text, for some cases it's better to be locale-independent.

For NFC normalized UTF-8 text, it just uses memcmp. Other formats are converted to that and compared one Character at a time. The use of memcmp here sounds strange at first, but remember that this is for providing a consistent ordering across versions and locales, not for alphabetizing user-facing text.

Performance Issues

As was recently pointed out on the Swift forums, there is no limit to how large a Character can be. Consider the following:

let problematic = "a" + String(repeating: "\u{0301}", count: 20_000_000) + "x"
// `problematic` is 20,000,002 Unicode scalars, but only 2 grapheme clusters!

func thisWillTakeAWhile() -> Character {
  problematic.first!
}

Because a Character is an owned (often unique) String, never a Substring, that has to copy the 20,000,001-scalar grapheme cluster into a new string. This forms pathological cases for a lot of functions that assume materializing a Character takes negligible time, such as haystack.contains(needle). That function, at the very least, compares the first character of needle to each character in haystack until it finds a match. When retrieving the first character of needle takes a noticeable amount of time, even obviously (to us) false ones like "Hello, World!".contains(problematic) take several seconds to execute (example, though I'm seeing around 1.3 seconds, rather than the 10 seconds reported in the forum post).

$\endgroup$
12
$\begingroup$

Rust

The default string types (&)str and String are both UTF-8, ignoring native encoding. There are various other types and conversion methods to convert between native rust strings and other encodings, such as UTF-32 (the widestring stdlib crate) and native strings (OsString)

The "atomic unit" of a string is defined to be a char, representing a single UTF-8 codepoint - a Unicode scalar value.

You cannot directly index a string without converting it to a byte-like Rust-level representation and therefore losing the invariant that the string is correct UTF. You can, however, access the codepoint n (which is of course a O(n) operation).

As far as I am aware, everything else just uses the UTF-8 byte values in terms of ordering, encoding, and equality.

Also as far as I know, this approach has been pretty well received in the linux community, as UTF-8 is prevalent there. I cannot speak for the Windows community.

$\endgroup$
5
  • 3
    $\begingroup$ When you say "standard for UTF-8 in terms of ordering, encoding, and equality", you mean it just uses byte ordering and equality (like a C string)? $\endgroup$
    – Michael Homer
    Jun 13, 2023 at 5:08
  • 1
    $\begingroup$ @MichaelHomer Yes, as confirmed by the source code here: doc.rust-lang.org/src/alloc/string.rs.html#362 $\endgroup$
    – blueberry
    Jun 13, 2023 at 5:14
  • 5
    $\begingroup$ A few issues in this answer... First a codepoint is independent from an encoding, hence UTF-8 codepoint has no meaning. Second you can definitely index a string in Rust, though you do have to be aware that shall indexes fall on non codepoint boundaries, a panic will ensue. Thirdly, it may be important to point out that Rust aims for a minimal standard library, so that relegating more Unicode functionality to 3rd-party crates is not shocking to Rust users... though it may be to newcomers. $\endgroup$ Jul 3, 2023 at 13:39
  • $\begingroup$ this is fairly similar to what Julia does with strings $\endgroup$ Jul 5, 2023 at 4:26
  • 1
    $\begingroup$ Note that UTF-8 byte order is the same as Unicode code point order. This is not the case for UTF-16, due to the "surrogate" code units not being at the end of the 16-bit code space. $\endgroup$
    – dan04
    Jul 7, 2023 at 16:58
8
$\begingroup$

Python 3

Conceptually, strings are immutable sequences of code points.

Indexing strings results in a string containing a single code point. Characters not exposed as a separate type.

Equality is based on equality of code points, and ordering is based on the value of the code points. Normalisation is not done implicitly.

The representation in memory is more of an implementation detail, but in order to keep indexing as fast as expected by users, strings in CPython are represented as arrays of code points, either using 1 byte (Latin-1), 2 bytes (UCS-2, aka UTF-16 not containing surrogate pairs) or 4 bytes (UTF-32), using the smallest representation that fits all code points in the string. This is not exposed to Python users.

Compare and contrast bytes, Python 3's immutable byte sequence:

Indexing bytes gives an int.

Equality is based on byte values, and ordering is based on the value of the bytes. Normalisation is not relevant to byte sequences.

$\endgroup$
3
  • $\begingroup$ What about Ordering? $\endgroup$
    – Pablo H
    Jul 3, 2023 at 15:45
  • $\begingroup$ I'm sorry, what is your question exactly? $\endgroup$
    – Jasmijn
    Jul 3, 2023 at 16:26
  • $\begingroup$ Sorry, I failed to read the last sentence of your answer! :-( $\endgroup$
    – Pablo H
    Jul 3, 2023 at 17:10
4
$\begingroup$

This does not address 2008 onwards (which seems a pretty arbitrary date) but provides some background instead.

Treat it as a (mostly) library issue

A monad string is just an array of bytes interpreted as UTF-8 what's the problem?

A fair few languages treat it as a library issue.

Users thinking about Unicode know:

  • UTF-8 is a variable length encoding
  • The difference between indexing a byte and a character

So they expect operations to distinguish:

  • arrays of bytes
  • arrays of characters/code points (i.e. strings of text)

And provide different sets of operations for each and conversions from one to the other.

Getting this right can be hard but you can farm it out. Rather it is easy to miss a corner case and introduce bugs which is unfortunate in a core library.

A string is of course a core type but starting with the faulty assumption that most users are using Western scripts it is sufficient to:

Use UTF-8 everywhere

  • Source files are encoded as UTF-8

    • so you can write comments natively
    • possibly use non-western letters as variable names
  • The core string type is an array of bytes ideally with a length rather than null terminated

    • So you can embed nulls.
    • So inserting a null does cannot be used as an attack vector to truncate strings

So:

  • C having null-terminated strings gets this wrong.
  • C++ follows C, so std::string originally got this wrong too (and zero-terminated strings are still needed in places).
  • D from 2001 gets this right - as do most other newer languages

Leave it to a (possibly third party) library

For example:

  • ICU - International Components for Unicode.

  • Users of the Qt library will use QString.

    QString is an array of UTF-16 so there are potential issues with code points above 0xFFFF which require 2 QChar's to represent - see Retrieve Unicode code points > U+FFFF from QChar.

    This is a good example of how subtle bugs remain even in implementations we might hope are Unicode safe.

But sometimes it's an OS issue...

The Windows API is quite fond of UTF-16

Because Windows is popular, this leads to abominations like std::wstring becoming standard library elements in some languages. It's an abomination because:

  • It should not be necessary to make your code generic over more than one string representation.
  • Because 2 bytes will be more than enough for everyone (oops - no it won't).

See also UTF-8, UTF-16, and UTF-32.

Maturity brings wisdom

With enough maturity a good Unicode library should become a de-facto or blessed standard or a core library.

Putting it into a clever type system and getting it right early on would be great though so I look forward to reading the other answers.

$\endgroup$
9
  • $\begingroup$ Yeah, it's a shame that crippled implementations of std::wstring are out there. I get used to assuming that wchar_t can hold any code point - thankfully I don't have to target Windows platforms! $\endgroup$ Aug 16, 2023 at 14:50
  • $\begingroup$ Many aspects of Unicode should be OS issues, save for the lack of a useful specification for a set of primitives an OS should support. Changes to the Unicode standard should not require rebuilding programs that might be affected thereby, but should instead be accommodated via OS update which would then have the appropriate effect on applications that use the OS functions. Unfortunately, there is at present no way to avoid baking changeable aspects of the Unicode standard into the application layer. $\endgroup$
    – supercat
    Oct 18, 2023 at 19:55
  • $\begingroup$ If your interpretation is UTF-8 in-memory then you give up on random-access character indexing. $\endgroup$ Oct 19, 2023 at 17:02
  • 1
    $\begingroup$ @KarlKnechtel: Outside of the specific task of converting strings between UTF-8, UTF-16, and UTF-32, there aren't many situations where code-point boundaries are significant, so I'm not sure why the inability to retrieve the Nth code point given a string and N would be a problem. $\endgroup$
    – supercat
    Oct 24, 2023 at 15:12
  • 1
    $\begingroup$ @KarlKnechtel They do, but why? Even fully understanding all Unicode complexities, i18n, blah, blah? What are the use cases? (I can think 2, where perhaps some other data type may be better: file system paths or web URIs, and strings of symbols such as DNA, number/license plates, product codes (e.g. EAN), etc.) $\endgroup$
    – Pablo H
    Oct 26, 2023 at 15:32
1
$\begingroup$

Nim

All strings are UTF-8 strings by convention, but it is not enforced.

Strings are char arrays, where char is a single byte. Indexing into a string is safe in the sense that Nim will not panic upon getting a char > 127 representing a fraction of a codepoint, but it will just treat it as a byte. Strings are conventionally treated as no more than a char array. There is a commonly used special openarray[T] type that abstracts over lists (seq[T]), arrays of various sizes, and strings.

There is a separate std/unicode module in the standard library that provides a (four-byte) Rune type representing a Unicode character, various associated functions, and a .runes() iterator.

Strings are both length-prefixed and null-terminated. Nim also has the cstring type for compatibility with C, which behaves the same as the string type, but lacks a length field and is instead only null-terminated. string is implicitly convertible to cstring. It doesn't do anything terribly different wrt. Unicode.

$\endgroup$
-1
$\begingroup$

Languages developed over the last fifteen years or so have been within the era where Unicode is ubiquitous, and so could design their core string types accordingly.

There is a lot of history, and because of that, there is a lot of backward compatibility that may need to be made avaliable in new languages. The considerations below focus in this extra requisite.

This answer is not specific to a previous language, but considerations for a possible future language that tries to avoid a lot of pitfalls in string design. It's heavly inspired in Swift design, as mentioned in other answer, and provides some design alternatives (naming, sequential/proximal indexing, opaque positions and SSO)

Encoding

Encoding: Are strings stored in UTF-8, UTF-16, UTF-32, a combination, or something else?

Make the internal encoding a pure implementation detail. It's the only way to ensure you can change it, globally or on a per case basis. Python's experience in changing strings between versions 2 and 3 showed how disastrous exposing any internal encoding can cause afterwards.

Views

Is that made visible to the user?

Expose the popular encoding via non allocating views.

Say:

str s = "...";
foreach (a in s.Utf8)  {} // a is u8
foreach (b in s.Utf16) {} // b is u16
foreach (c in s.Utf32) {} // c is u32
foreach (d in s.CChar) {} // machine dependent sized type

These views should be implemented like like C#'s structs or non-malloc()ed C's structs. That is, objects allocated in directly stack frames.

Character

Characters: What is the atomic unit of a string, if anything? It may be a byte, a code unit, a code point, a grapheme cluster, or something else.

Offer all, explicitly, and avoid all confusion.

str s = "...";
foreach (a in s.Bytes)     {} // a is u8
foreach (b in s.Runes)     {} // b is u32
foreach (c in s.Graphemes) {} // c is str

Rune is a common name for code points. But if it is the same as .Utf32 view, it may be omitted.

Indexing

Indexing: Possibly related, what are the semantics and ergonomics of indexing into a string ("give me character 5", or from 5 on), if there is any? Iteration may also be relevant.

There is no indexing or counting on string objects, only in views.

That is, the indexing by .Bytes accesses the underlying byte sequence, no transformation is applied. Indexing by .Utf8 is $O(1)$ complexity in strings stored as UTF-8 strings, and $O(n)$ complexity for strings in other encoding, and so on.

With this, it is obvious that some users will want to make certain strings in certain encoding sometimes, to obtain the $O(1)$ complexity. So the string type will then gain some methods as:

// Create new arrays in these specific encoding
// or return the same string, if already internally
// on requested encoding

str s = "...";
var a = s.ToUtf8();
var b = s.ToUtf16();
var c = s.ToUtf32();

And in cases the performance really matters, and can be traded for memory:

var d = s.Utf8.ToArray();
var e = s.Utf16.ToArray();
var f = s.Utf32.ToArray();

Sequential indexing

The most accessed method on Java's string is charAt(). That is no mistake. Every XML or JSON parser over there will use charAt() or make around it.

There is something to consider here. Parsers in general will use charAt() in every code unit. These accesses are not arbitrary or random, as one charAt() call almost always is performed in an index very next to a previous charAt() call.

That is, indexing is almost always sequential or proximal.

The $O(n)$ complexity on UTF-8 indexing occurs on a random access basis and no memorization. But if one specific string object "remembers" the last byte to code unit mapping, it can then use another algorithm to navigate around the byte stream, instead of starting every time from beginning.

So a new string object may reserve space for this memorization, or, even better, make this sequential/proximal indexing very visible.

str s = "...";

var walker = s.Utf16.Walker;

var p = walker.Prev; // Previous code unit or zero
var t = walker.Code; // Actual code unit or zero
var n = walker.Next; // Actual code unit or zero

if ( walker.HasNext ) {};
if ( walker.HasPrev ) {};
if ( walker.HasCode ) {};

walker.Advance();
walker.Advance(n);
walker.Rewind();
walker.Rewind(n);

Indexing and Moore's law

It's important to take a hint of history of C's fgetpos()/fsetpos(), and make all positioning on string to use WalkerPosition/fpos_t/nint/u0, instead of built-in integers.

Built-in integers can be used in indexing and advancing/rewind as usual, but absolute positioning should be opaque, as fpos_t.

Normalisation

Normalisation: Are strings automatically normalised internally into some canonical form?

As above, system configurable and explicit invoked methods and views.

var b = File.ReadAllBytes(filename);
var r = new str(b);

var s = r.Normalize(); // System default, configurable

var nfd = s.NormalizeFormD();
var nfc = s.NormalizeFormC();
var nfkd = s.NormalizeFormD();
var nfkc = s.NormalizeFormC();

Equality: When are two strings considered equal? Encoding or normalisation of the value may matter here, or may be abstracted away.

As strings may have may have different encoding and freely convertible between these encoding, without changing their meanings, then:

  • Strings with same encoding compare equals if are byte identical (fast path);

  • Strings with different encoding compare equals if they have the same code points. That is, in general:

def Equals( this? , other: str ) :bool
    if ( this == null && other == null )
        return true;
    if ( this == null && other != null )
        return false;
    if ( this != null && other == null )
        return false;
    var s1 = this.Utf32.Walker;
    var s2 = other.Uft32.Walker;
    for ( ; s1.HasNext , s2.HasNext ; s1.Advance(), s2.Advance() )
        if ( s1.Code != s2.Code )
            return false;
    if ( s1.SamePosition(s2) )
        return true;
    return false;

Ordering

Ordering: When does one string precede another for comparison or sorting operations?

As with Normalization, make configurable if the string uses a "binary fast" collation, to compare code points directly, uses a specific collation, or tries to detect and select a collation from systems configuration.

Also, is sometimes necessary to compare string with different collations, so a explicit API is in order:

var cmp = new String.Collation(code);
cmp.Compare(str1, str2);

Small string optimization

I'm interested in what design choices were made and what the implications and reception of those choices by users of the language were, if that's notable.

There is a notable, somewhat recent development. Small string optimization (SSO) is an implementation that boosts performance of systems dramatically.

Designing your strings API to make it possible to implement SSO is important.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .