This presentation details Ninefront's ongoing efforts to modernize its Unicode support, focusing on the implementation of advanced character property lookup functions and normalization algorithms. Jacob Moody outlines the historical context of UTF-8's origins in Plan 9 and the challenges posed by Unicode's evolution to 21-bit characters. The core of the work involves generating efficient, constant-time lookup tables from Unicode's standard data files, utilizing "compact arrays" (page table-like structures) to optimize operations like casing transformations. A significant portion of the talk addresses Unicode normalization (NFC and NFD), explaining the complexities of two-way character representations and the engineering solutions employed, including specialized hash tables and exception handling for decomposition and recomposition mappings. The presenter also covers the development of a streaming normalization interface designed for bounded memory, rigorous testing against Unicode's extensive test suite, and the integration of these features into Ninefront's text processing utilities. Future work will address critical GUI limitations and user interaction with decomposed Unicode.
Summary:
0:00 Historical Context & UTF-8 Origins: Jacob Moody introduces himself, working on Ninefront, and describes himself as a "growing Unicode nerd." He recounts how Unicode V1 (1991) led to Plan 9's early 16-bit Unicode support. Ken Thompson designed UTF-8 in response to a request for a file-system-safe UTF, with Rob Pike implementing it in under a week. Plan 9's quick adoption served as an argument for UTF-8's standardization.
0:32 Unicode Evolution to 21-bit Characters: Unicode later extended to 21-bit characters from V2 onwards, a significant shift from the initial 16-bit ambition. Ninefront was reportedly the first to implement support for these 21-bit code points, and work to integrate this throughout Ninefront's software (e.g., Unicode in Yak identifiers) is ongoing.
0:50 Addressing Outdated rune Functions: Plan 9's libc included rune variants of ctype.h functions (like toUpperRune, isLowerRune). However, in Ninefront, these functions were never updated to handle characters beyond the 16-bit Basic Multilingual Plane (BMP), leading to missing functionality for extended Unicode.
0:56 Solution: Code Generation & Compact Arrays: The previous implementation used a large static array with binary search, which becomes inefficient as Unicode grows. The solution involves code generation from Unicode's annually published UnicodeData.txt files to create efficient lookup tables.
0:07:09 Optimizing Lookups with Compact Arrays: To avoid the performance degradation of binary search, a "compact array" data structure (similar to page tables) was adopted. This involves splitting code point indices into chunks, overlapping identical chunks, and using multi-layered indexing. This optimization yields constant-time lookups with moderate memory footprint (e.g., ~10KB for casing tables, ~25KB for combined isRune tables).
0:13:55 Normalization Explained: Unicode normalization is crucial because some characters can be represented in multiple ways (e.g., precomposed characters vs. a base character + combining diacritics). This creates comparison issues for computers. Normalization converts text consistently into either NFD (decomposed) or NFC (composed) forms.
0:17:16 Normalization Data Tables & Engineering Challenges: Implementing normalization requires specific data tables for decomposition/recomposition mappings, combining character classes (for sorting), and "quick check" values. While combining character class and quick check tables are relatively straightforward using compact arrays (~10KB each), decomposition and recomposition tables posed more engineering challenges due to multiple output runes and the need for efficient lookups across the BMP and beyond.
0:19:53 Specialized Tables for Decomposition/Recomposition: For decomposition, BMP outputs are packed into a single 32-bit integer, and non-BMP outputs (a small number) are handled via an offset into a separate flat array. For recomposition, a hash table is used for BMP inputs due to the size of compact arrays, while non-BMP inputs are linearly searched in a small exception list. Overall, these normalization tables add about 50KB to the program size.
0:27:00 Streaming Normalization Algorithm: The standard's abstract normalization algorithm implies multiple passes, which is unsuitable for streaming text processing with bounded memory. A custom chunking method was developed to process text in fixed memory blocks, handling both base rune + conjoiner contexts and more complex cases like Korean Hangul (using the quick check value for boundary detection).
0:31:33 Handling Edge Cases and Interface: Edge cases like an unlimited number of conjoiners are handled by introducing a COMBINING GRAPHEME JOINER (U+034F) to break long sequences into 30-conjoiner chunks, allowing for bounded memory sorting. The library exposes a streaming API (norm_init, norm_pull) for flexibility and also provides fixed-size input interfaces.
0:36:50 Extensive Testing & Current Usage: The implementation was rigorously tested against tens of thousands of Unicode standard-published test cases, which proved invaluable for identifying and fixing issues. These new features are now supported in Ninefront's TCS (Text Conversion System) for normalization of pipe and file inputs and are also vendored by the streetlist project.
0:38:25 Additional "Freebie" Algorithms: The new data tables also enabled the easy implementation of grapheme break and word break algorithms (dictating logical character and word boundaries, respectively), requiring only about 60-70 lines of code.
0:39:30 Future Work: Key future challenges include updating graphical user interfaces (Acme, SAM, RIO) and the font system, which currently assume one code point equals one character, to properly handle decomposed Unicode. Resolving ambiguities in user interaction (e.g., backspace behavior for decomposed characters) and integrating Unicode-aware regex (\w, \b, \s) are also areas for future development.