Let’s Stop Ascribing Meaning to Code Points

https://manishearth.github.io/blog/2017/01/14/stop-ascribing-meaning-to-unicode-code-points/

by geofft • 10 years ago

132 55 10 years ago

manishearth.github.io

sanxiyn2• 10 years ago

The main time you want to be able to index by code point is if you’re implementing algorithms defined in the unicode spec that operate on unicode strings (casefolding, segmentation, NFD/NFC). Most if not all of these algorithms operate on whole strings, so implementing them as an iteration pass is usually necessary anyway, so you don’t lose anything if you can’t do arbitrary code point indexing.

Another algorithm for unicode strings which wants to index by code point is unicode regular expression matching. I heard that you do lose something here if you can't assume all code points encode to same length. Unlike other algorithms you mentioned which only iterate forward, depending on implementation regex needs to backtrack.

I once heard that complexity of implementing regex directly on UTF-8 is one reason why Python will not use UTF-8 internally.

Manishearth16• 10 years ago

Hm, interesting. You still don't need arbitrary indexing for that; just the ability to iterate backwards, but I can see how it would complicate things. I wonder if it could be implemented on utf8 without affecting performance much.

burntsushi's utf8-ranges library used by the Rust Regex lib probably makes this easier to deal with. I wonder how it performs in relation to the Python implementation (which I assume is in native code)

Animats3• 10 years ago

UTF-8 substrings can't find a misaligned match, because of the way UTF-8 is encoded. First bytes are unambiguous. I had to write "rfind" in Rust, and here it is:

    fn rfind(s: &[&str], key: &str) -> Option<usize> {
        (0 .. s.len()).rev().find(|&i| s[i] == key)    
    }

No need to explicitly worry about rune boundaries. This, like forward find, returns a byte index into a UTF-8 string. Explicit byte indices into UTF-8 strings are troublesome.

pjscott3• 10 years ago

Backtracking in a UTF-8 string is easy: when you need to remember a location, just record its byte offset. You have exactly the same issue in UTF-16, which is also variable-width and therefore not O(1)-indexable by code point. There are loads of regular expression engines which operate on both of these encodings, and I've never seen them go to any great pains to work around the lack of code point indexing.

sanxiyn2• 10 years ago

Yes, you have exactly the same issue in UTF-16, I never said otherwise.

Animats3• 10 years ago

If everything that can match in a regular expression is valid UTF-8, and everything the regular expression can generate is valid UTF-8, you can just run the regular expression on the byte string.

This requires that matches match UTF-8 substrings, only. That's easy for explicit strings, such as "abc". For more general forms, "." must match one rune, not one byte. But that's not hard.

Python's problem is that strings are random-access indexable by rune (in the Go sense). Python either needs a representation that's rune-indexable, or it needs to generate an index array for strings that need one. There's an argument for the second approach, because most loops don't need a random-access index. "for i in "abcdef: ... " does not, for example.

pjscott3• 10 years ago

It's also possible to chunk the index array: to store the byte-index of every 16th rune, say, and do a bit of cheap iteration afterward. I've had good success with this approach: it's fast, it's light on memory, and it preserves constant-time indexing by code point.

Manishearth16• 10 years ago

Python's problem is that strings are random-access indexable by rune

Yeah, one of my points in the blog post is that random-access rune (code point) indexing isn't very valuable. Python is stuck with it, but if anyone in the future needs to make a similar choice, I hope they don't use O(1) rune indexing as a reason unless they have a very specific use case where O(1) rune indexing actually matters.

(I, for one, am very happy with the "rune" terminology, "char" is way too overloaded. It took me a minute to understand why they did that in Go when I first picked it up, but when I realized the reason I found it brilliant)

hoytech2• 10 years ago

There are many considerations of course and I might not have fully grasped your point, but in reference to your last paragraph:

By default RE2 matches directly against the UTF-8 encoding, see this neat state diagram:

https://swtch.com/~rsc/regexp/regexp3.html#step3

In terms of backtracing engines, perl also stores strings internally as UTF-8 (on most platforms) and its regexp engine runs directly on them. It can also match "eXtended grapheme clusters" with \X.

burntsushi• 10 years ago

Another algorithm for unicode strings which wants to index by code point is unicode regular expression matching.

Why? This is certainly not a requirement for at least some levels of Unicode support.

I once heard that complexity of implementing regex directly on UTF-8 is one reason why Python will not use UTF-8 internally.

It's really not that bad. Both RE2 and Rust's regex engine operate on UTF-8 directly, and this is one of the reasons why these engines are fast. If your automaton is byte based, then you can do a lot of nice tricks in your DFA implementation. (In fact, it's a critical reason why ripgrep doesn't slow down when handling Unicode features, unlike GNU grep.)

For Rust at least, the trickier parts of generating the UTF-8 automaton are available for reuse in the utf8-ranges crate: https://docs.rs/utf8-ranges/1.0.0/utf8_ranges/ (Which is used in at least two regex implementations I've written.)

I'd say the complexity claim might be coming from some other component of the implementation, or something more related to how Python strings are generally represented, rather than it being a fundamental complexity of building a regex engine on UTF-8 directly.

chris_wot• 10 years ago

I'm not sure if this has changed, but LibreOffice has I herit d the most amazingly complicated and bizarre text layout system you can ever imagine.

std_throwaway• 10 years ago

How so?

scrollaway2• 10 years ago

Excellent post.

Now, Rust is a systems programming language and it just wouldn’t do to have expensive grapheme segmentation operations all over your string defaults. I’m very happy that the expensive O(n) operations are all only possible with explicit acknowledgement of the cost. So I do think that going the Swift route would be counterproductive for Rust.

I'm not sure I understand the logic here. How is Rust exempt but not, say, Python? Just because it's a systems language? I get why you wouldn't make it the default in Rust, but the logic applies to all languages, doesn't it?

Aside: I was talking about this with a friend just yesterday. Is there any language that separates the concept of a string and a user-facing string? Specifically for localization purposes, the way gettext works.

eg. I wish that in Python you could do this:

    err = "internal_error"
    msg = t"Internal error!"

error_msg would be easy to pick up for translation, rather than have to do some cludgy import as _ and _("Internal error!"). Hm, now that I'm writing this here, I guess it's still not a type you'd want to operate differently on than just plain unicode strings.

Manishearth16• 10 years ago

Just because it's a systems language? I get why you wouldn't make it the default in Rust, but the logic applies to all languages, doesn't it?

You deal with strings as bytes (opaque data) (edit2: didn't really mean bytes here. see child comments) more often than strings as text in systems programming, basically.

Also, you'll want to write stuff like fast parsers in Rust. For a parser you're usually doing ascii matching anyway.

Swift hides the actual encoding of the string from the user. That's not something we can do in Rust.

I get why you wouldn't make it the default in Rust

That's all I'm saying? I'm totally for having EGC operations there, I don't want them in the default operations. "it just wouldn’t do to have expensive grapheme segmentation operations all over your string defaults"

Basically, Rust tries to keep costs explicit, unlike languages like Python. This would be against that philosophy.

Edit: I'd also like to point out that indexing by code point or grapheme is a rare operation in Rust anyway.

xenadu02• 10 years ago

In Swift you have access to the utf8 and utf16 views. For a string constructed from UTF8 the utf8 view is a view onto the underlying storage more or less. That said the String API is getting some revisions in Swift 4 to make it both faster and easier to use without sacrificing correctness.

Swift supports unicode in source code so its parser is unicode aware. I'm not sure there is a good case for parsing in a non-unicode-aware way.

If you're working with strings as opaque data why are you even using a String type?

scrollaway2• 10 years ago

You deal with strings as bytes (opaque data) more often than strings as text in systems programming, basically.

Now you're really confusing me. Are you talking about simply byte strings vs. unicode strings? Most modern languages, including python, have that distinction. What am I missing?

hsivonen4• 10 years ago

In addition to the Rust design making more sense for systems programming than Swift's, what Rust puts on the language-level is forward-compatible with future Unicode versions. A future version of Unicode could define combining behavior for currently unassigned code points, which means that iterating by grapheme cluster will change as Swift becomes aware of new Unicode versions.

throwawayish5• 10 years ago

You deal with strings as bytes (opaque data) (edit2: didn't really mean bytes here. see child comments) more often than strings as text in systems programming, basically.

That's true in some sense [1] for unix-ish OSes, but doesn't hold on other operating systems.

[1] Even on unix-ish OSes it's pretty obvious that filenames are supposed to be encoded in something and aren't just uint8_t*. There's just no one telling you what that encoding is, so normally it's guessed (eg. $LANG). For filesystems that actually have a defined encoding (eg. NTFS\Win32, JFS, HFS+, APFS and the whole bunch of "non-unix OS FS") these are re-coded by the filesystem driver in the unix-ish OS. Eg. ntfs-3g transcodes filenames to UTF-8; cifs takes a "iocharset" option; and we of course have convmv(1).

The idea that "file names and generally everything in the OS is a bunch of bytes" is pretty much only shared by unix-ish systems.

captainmuon2• 10 years ago

Is there any language that separates the concept of a string and a user-facing string?

Not quite, but Nim has a concept of a tainted string, which comes from outside your (web) application and has to be escaped or explicitly casted into a regular string (the Python web framework Django has something similar). You could use the same mechanism of "distinct types" to create a user facing string vs an internal string if you want. I used this in a little Unicode related experiment to create a number-of-bytes and number-of-chars type, and made my strings take these as index, so I would never confuse them. Pretty neat language feature I thought.

hoytech2• 10 years ago

FYI: According to wikipedia: "Perl supported tainting from at least 1989 as the -T switch was included in Perl 3."

https://en.wikipedia.org/wiki/Taint_checking

omegaworks• 10 years ago

Ruby has separate strings and symbols. While you can express the same data in both forms, the syntax biases symbols toward simplicity.

1wd3• 10 years ago

In Python I've seen the convention "user facing string" vs. 'internal string'. It doesn't behave differently of course and there's no type checking, but it can be useful for showing intent.

throwawayish5• 10 years ago

error_msg would be easy to pick up for translation, rather than have to do some cludgy import as _ and _("Internal error!"). Hm, now that I'm writing this here, I guess it's still not a type you'd want to operate differently on than just plain unicode strings.

This is maybe ok for very simple cases, but doesn't work as soon as you need context (in Python this is either done by extra _ parameters or through special comments) or pluralization.

GolDDranks• 10 years ago

Excellent post, thank you!

By the way, I've sometimes heard that it was the popularity of emoji that finally made American and Western European coders learn about the particulars of unicode. Is this just a jokingly told anecdote, or did emoji really help?

Manishearth16• 10 years ago

I find it pretty accurate, but that's just anecdotal from how I've seen software I use change in that time period, and how I've seen attitudes of people online change.

I'm sure plenty of Western programmers were aware of this stuff, though. Just not enough.

klibertp• 10 years ago

Western European? I don't know - there are many languages in that part of the world which use some non-standard characters. Germany (not sure if it's still the case), France, Austria, Italy, Spain... Anyway, I always thought UNICODE ignorance is strictly an anglo-sphere thing - most of the rest of the world is very aware.

1wd3• 10 years ago

Western Europe uses more characters than ASCII like umlauts (äöü), accents (àèé), €¢, German ß and a few more, but large parts are still comfortably stuck in a codepage-style mindset thinking "ISO Latin-1 is good enough". (Also know as or confused with ISO/IEC 8859-1, CP-1252 or "Ansi".)

https://en.wikipedia.org/wiki/Code_page#ISO.2FIEC_8859-relat...

throwawayish5• 10 years ago

Central European languages can get more or less by with Latin-1, although even there many characters are already missing, iirc French, Czech, Dutch and Finnish. Special characters of many regional dialects are missing as well.

FWIW (more or less proper) Unicode support seems to be pretty much an implicit, hard requirement today for almost anything facing users.

Freak_NL3• 10 years ago

Emoji may have helped popularize support for Unicode characters outside of the Basic Multilingual Plane (The first 2¹⁶ code points in Unicode), because all but a few fall outside of it. Before emoji any code point outside of the BMP tended to have a niche audience. When I wrote my master's thesis in 2009, support for non-BMP characters was still sketchy (although XeLaTeX and PDF-viewer Evince could handle them neatly on the Linux desktop).

I doubt that emoji helped further popularize Unicode in Europe, because in my experience (anecdotal of course) developers were already well aware of the benefits of Unicode (and UTF-8 in particular for the web) before emoji got adopted from Japanese telephones and embraced en-masse. I suspect that in Europe the need for Unicode arose sooner. For Dutch for example; with the introduction of ISO-8859-15 in 1999 (subtly different from ISO-8859-1) you now often had two character encoding standards in mixed use for a single language, and when you had to render documents with names of people from various countries, things just got confusing (in the US diacritics tend to get dropped instead). UTF-8 offered a clean break from this.

It seems plausible that emoji may have helped Americans break the remnants of the ASCII barrier though.

Manishearth16• 10 years ago

(where "niche audience" includes speakers of the most spoken language in the world, but I assume you're talking about the West specifically)

makecheck• 10 years ago

Yep. On Apple platforms there is basically just ONE way to do this conveniently and correctly: an enumeration function on NSString that visits composed character sequences individually, as substrings. And, it was only added in OS 10.6, which shows how slow the evolution of correct Unicode processing can be.

And, there is still no completely reliable way to guess the cell/column width of a symbol just by looking at it, especially if your goal is to be consistent with any other interpreter of the string (like a text editor). Still heuristics at best for any case outside common tables like CJK.

slededit• 10 years ago

The flip side to this is you can render text several orders of a magnitude faster if its from the latin subset. A fast-path is extremely helpful if you have a lot of text on the screen.

Let’s Stop Ascribing Meaning to Code Points

Related Stories