diff options
| -rw-r--r-- | CHANGES.md | 1 | ||||
| -rw-r--r-- | docs/text.md | 63 | ||||
| -rw-r--r-- | src/environment.c | 2 | ||||
| -rw-r--r-- | src/stdlib/datatypes.h | 6 | ||||
| -rw-r--r-- | src/stdlib/text.c | 477 | ||||
| -rw-r--r-- | src/stdlib/text.h | 2 |
6 files changed, 385 insertions, 166 deletions
@@ -14,6 +14,7 @@ - Added Path.has_extension() - Added Table.with_fallback() - Added Int*.get_bit() and Byte.get_bit() +- Improved space efficiency of Text that contains non-ASCII codepoints - Fixed bugs: - Negative integers weren't converting to text properly. - Mutation of a collection during iteration was violating value semantics. diff --git a/docs/text.md b/docs/text.md index f716de36..bff6ee4e 100644 --- a/docs/text.md +++ b/docs/text.md @@ -2,29 +2,30 @@ `Text` is Tomo's datatype to represent text. The name `Text` is used instead of "string" because Tomo text represents immutable, normalized unicode data with -fast indexing that has an implementation that is efficient for concatenation. -These are _not_ C-style NUL-terminated character lists. GNU libunistring is -used for full Unicode functionality (grapheme cluster counts, capitalization, -etc.). +fast indexing that has a tree-based implementation that is efficient for +concatenation. These are _not_ C-style NUL-terminated character arrays. GNU +libunistring is used for full Unicode functionality (grapheme cluster counts, +capitalization, etc.). ## Implementation Internally, Tomo text's implementation is based on [Raku/MoarVM's strings](https://docs.raku.org/language/unicode) and [Boehm et al's -Cords](https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf). -Strings store their grapheme cluster count and either a compact list of 8-bit +Cords/Ropes](https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf). +Texts store their grapheme cluster count and either a compact list of 8-bit ASCII characters (for ASCII text), a list of 32-bit normal-form grapheme -cluster values (see below), or a (roughly) balanced binary tree concatenation -of two texts. The upside is that repeated concatenations are typically a +cluster values (see below), a compressed form of grapheme clusters with a +lookup table, or a (roughly) balanced binary tree representing a concatenation. +The upside of this approach is that repeated concatenations are typically a constant-time operation, which will occasionally require a small rebalancing -operation. Index-based text operations (like retrieving an arbitrary index or -slicing) are very fast: typically a constant-time operation for arbitrary -unicode text, but in the worst case scenario (text built from many -concatenations), `O(log(n))` time with very generous constant factors typically -amounting to only a handful of steps. Since concatenations use shared -substructures, they are very memory-efficient and can be used efficiently for -applications like implementing a text editor that stores a full edit history of -a large file's contents. +operation. Text is stored in a format that is highly memory-efficient and +index-based text operations (like retrieving an arbitrary index or slicing) are +very fast: typically a constant-time operation for arbitrary unicode text, but +in the worst case scenario (text built from many concatenations), `O(log(n))` +time with very generous constant factors typically amounting to only a handful +of steps. Since concatenations use shared substructures, they are very +memory-efficient and can be used efficiently for applications like implementing +a text editor that stores a full edit history of a large file's contents. ### Normal-Form Graphemes @@ -49,11 +50,37 @@ codepoints." Here are some examples: - `👩🏽🚀` is a single graphical cluster, but it's made up of several combining codepoints (`["WOMAN", "EMOJI MODIFIER FITZPATRICK TYPE-4", "ZERO WITDH JOINER", "ROCKET"]`). Since this can't be represented with a single - codepoint, we must create a synthetic codepoint for it. If this was the `n`th + codepoint, we must create a synthetic codepoint for it. If this was the 3rd synthetic codepoint that we've found, then we would represent it with the - number `-n`, which can be used to look it up in a lookup table. The lookup + number `-3`, which can be used to look it up in a lookup table. The lookup table holds the full sequence of codepoints used in the grapheme cluster. +### Text Compression + +One common property in natural language text is that most text is comprised of a +relatively small set of grapheme clusters that are frequently reused. To take +advantage of this property, Tomo's Text implementation scans along in new text +objects looking for spans of text that use 256 or fewer unique grapheme clusters +with many repetitions. If such a span is found, the text is stored using a small +translation table and one 8-bit unsigned integer per grapheme cluster in that +chunk (which is possible when there are 256 or fewer clusters in the text). This +means that, for the cost of a small array of 32-bit integers, we can store the +entire text using only one byte per grapheme cluster instead of a full 32-bit +integer. For example, a Greek-language text will typically use the Greek +alphabet, plus a few punctuation marks. Thus, if you have a text with a few +thousand Greek letters, we can efficiently store the text as a small lookup +table of around a hundred 32-bit integers and use one byte per "letter" in the +text. This representation is around 4x more efficient than using the UTF32 +representation to store each Unicode codepoint as a 32-bit integer, and it's +about 2x more efficient than using UTF8 to store each non-ASCII codepoint as a +multi-byte sequence. Different languages will have different efficiencies, but +in general, text will be stored significantly more efficiently than UTF32 and +somewhat more efficiently than UTF8. However, the big advantage of this approach +is that we get the ability to do constant-time random access of grapheme +clusters, while getting space efficiency that is almost always better than +variable-width UTF8 encoding (which does not support fast random access of any +kind). + ## Syntax Text has a flexible syntax designed to make it easy to hold values from diff --git a/src/environment.c b/src/environment.c index eb2d28be..0dbe015d 100644 --- a/src/environment.c +++ b/src/environment.c @@ -355,9 +355,11 @@ env_t *global_env(bool source_mapping) {"from_text", "Path$from_text", "func(text:Text -> Path)"}, {"has", "Text$has", "func(text:Text, target:Text -> Bool)"}, {"join", "Text$join", "func(glue:Text, pieces:[Text] -> Text)"}, + {"layout", "Text$layout", "func(text:Text -> Text)"}, {"left_pad", "Text$left_pad", "func(text:Text, count:Int, pad=' ', language='C' -> Text)"}, {"lines", "Text$lines", "func(text:Text -> [Text])"}, {"lower", "Text$lower", "func(text:Text, language='C' -> Text)"}, + {"memory_size", "Text$memory_size", "func(text:Text -> Int)"}, {"middle_pad", "Text$middle_pad", "func(text:Text, count:Int, pad=' ', language='C' -> Text)"}, {"quoted", "Text$quoted", "func(text:Text, color=no, quotation_mark='\"' -> Text)"}, {"repeat", "Text$repeat", "func(text:Text, count:Int -> Text)"}, diff --git a/src/stdlib/datatypes.h b/src/stdlib/datatypes.h index 135fb811..fce1ea74 100644 --- a/src/stdlib/datatypes.h +++ b/src/stdlib/datatypes.h @@ -74,7 +74,7 @@ typedef struct { void *fn, *userdata; } Closure_t; -enum text_type { TEXT_ASCII, TEXT_GRAPHEMES, TEXT_CONCAT }; +enum text_type { TEXT_ASCII, TEXT_GRAPHEMES, TEXT_CONCAT, TEXT_BLOB }; typedef struct Text_s { int64_t length:54; // Number of grapheme clusters @@ -92,6 +92,10 @@ typedef struct Text_s { struct { const struct Text_s *left, *right; }; + struct { + const int32_t *map; + const uint8_t *bytes; + } blob; }; } Text_t; diff --git a/src/stdlib/text.c b/src/stdlib/text.c index 0f3f9519..80c267ed 100644 --- a/src/stdlib/text.c +++ b/src/stdlib/text.c @@ -1,31 +1,58 @@ // This file defines type info and methods for the Text datatype, which uses // libunistr for Unicode support and implements a datastructure based on a // hybrid of Raku/MoarVM's space-efficient grapheme cluster representation of -// strings and Cords (Boehm et al), which have good runtime performance for -// text constructed by a series of many concatenations. -// +// strings, combined with a mostly-balanced tree datastructure based on Cords +// (Boehm et al), which have good runtime performance for text constructed by a +// series of many concatenations. In practice, this means Tomo's Text has an +// extremely compact memory footprint (typically as compact as UTF8 or +// up to 2x better for some languages), with extremely fast operations +// including concatenation, random indexing, and taking substrings. + // For more information on MoarVM's grapheme cluster strings, see: // https://docs.raku.org/language/unicode -// https://github.com/MoarVM/MoarVM/blob/main/docs/strings.asciidoc For more -// information on Cords, see the paper "Ropes: an Alternative to Strings" -// (Boehm, Atkinson, Plass 1995): +// https://github.com/MoarVM/MoarVM/blob/main/docs/strings.asciidoc +// For more information on Cords, see the paper "Ropes: an Alternative to +// Strings" (Boehm, Atkinson, Plass 1995): // https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf -// -// A note on grapheme clusters: In Unicode, codepoints can be represented using -// a 32-bit integer. Most codepoints correspond to the intuitive notion of a -// "letter", which is more formally known as a "grapheme cluster". A grapheme -// cluster is roughly speaking the amount of text that your cursor moves over -// when you press the arrow key once. However, some codepoints act as modifiers -// on other codepoints. For example, U+0301 (COMBINING ACUTE ACCENT) can modify -// a letter like "e" to form "é". During normalization, this frequently -// resolves down to a single unicode codepoint, in this case, "é" resolves to -// the single codepoint U+00E9 (LATIN SMALL LETTER E WITH ACUTE). However, in -// some cases, multiple codepoints make up a grapheme cluster but *don't* -// normalize to a single codepoint. For example, LATIN SMALL LETTER E (U+0065) -// + COMBINING VERTICAL LINE BELOW (U+0329) combine to form an unusual glyph -// that is not used frequently enough to warrant its own unique codepoint (this -// is basically what Zalgo text is). -// + +// Tomo's Text datatype represents Unicode text that is fully normalized using +// normalization form C (NFC). This means that all text created from source code +// or read in at runtime will respect normalization during comparison and other +// operations, and the original (potentially non-canonical) representation of +// text is not preserved. This also means that byte sequences that do not +// represent valid unicode text cannot be interpreted as the Text datatype. For +// example, a file with malformed UTF8 sequences cannot be read as Text. + +// A note on grapheme clusters: In Unicode, the fundamental unit is the +// "codepoint", which represents things like letters, symbols, emojis, +// combiners, and modifiers that alter other codepoints. However, most people +// have an intuitive notion of what a "letter" is that corresponds to the +// concept formally known as a grapheme cluster. A grapheme cluster is roughly +// speaking the amount of text that your cursor moves over when you press the +// left or right arrow key once. This often corresponds to a single codepoint, +// but some codepoints act as modifiers on other codepoints. For example, U+0301 +// (COMBINING ACUTE ACCENT) can modify a letter like "e" to form "é". During +// normalization, this frequently resolves down to a single unicode codepoint, +// in this case, "é" resolves to the single codepoint U+00E9 (LATIN SMALL LETTER +// E WITH ACUTE). However, in some cases, multiple codepoints make up a grapheme +// cluster but *don't* normalize to a single codepoint. For example, LATIN SMALL +// LETTER E (U+0065) + COMBINING VERTICAL LINE BELOW (U+0329) combine to form an +// unusual glyph that is not used frequently enough to warrant its own unique +// codepoint (this is basically what Zalgo text is). Emojis also use the ZERO +// WIDTH JOINER (U+200D) to add gender, skin tone, or other modifiers to emojis. +// Tomo takes an opinionated stance that grapheme clusters, not codepoints or +// bytes, are more useful to people when doing text operations like getting the +// "length" of a text or accessing the Nth "letter" of a text. If someone sends +// you a text with WOMAN (U+1F469) + ZERO WIDTH JOINER (U+200D) + ROCKET +// (U+1F680) followed by THUMBS UP (U+1F44D), it will render on your screen as +// two things: a female astronaut and a thumbs up, and this is how most people +// will think about the text. If you wish to operate on the raw codepoints that +// comprise the message, you are free to do so with the `.utf32_codepoints()` +// method and `Text.from_codepoints()`, but this is not the default behavior. +// The behavior for the given example is that `text.length == 2`, `text[1]` is +// the grapheme cluster representing a female astronaut emoji, and `text[2]` is +// the grapheme cluster representing the thumbs up emoji. + // There are a lot of benefits to storing unicode text with one grapheme // cluster per index in a densely packed list instead of storing the text as // variable-width UTF8-encoded bytes. It lets us have one canonical length for @@ -44,7 +71,7 @@ // things that would be nice if they had their own codepoint so things worked // out nicely because we're using them right now, and we'll give them a // negative number so it doesn't overlap with any real codepoints. -// + // Example 1: U+0048, U+00E9 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E // WITH ACUTE This would be stored as: (int32_t[]){0x48, 0xE9} Example 2: // U+0048, U+0065, U+0309 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E, @@ -52,6 +79,18 @@ // Where -2 is used as a lookup in a list that holds the actual unicode // codepoints: (ucs4_t[]){0x65, 0x0309} +// The text datastructure also uses a compact encoding (TEXT_BLOB) to store a +// per-chunk compressed form of the text when long stretches of text contain +// 256 or fewer unique grapheme clusters, which lets the text use a single byte +// for each grapheme cluster along with a lookup table. For typical text +// written in a variety of non-English natural languages (e.g. Spanish, Arabic, +// Japanese, Greek, German, Finnish, Basque), the in-memory representation +// takes up between 50-101% as much space as UTF8 encoding and between 24-39% +// as much space as UTF32 encoding, but with the advantage of extremely fast +// random access for indexing or slicing, unlike UTF8. In other words, this +// representation offers ASCII-like compactness and fast random access for +// non-English languages. + #include <assert.h> #include <ctype.h> #include <gc.h> @@ -68,6 +107,7 @@ #include <unistring/version.h> #include <uniwidth.h> +#include "bytes.h" #include "datatypes.h" #include "lists.h" #include "integers.h" @@ -102,7 +142,6 @@ static int32_t num_synthetic_graphemes = 0; #define SHORT_ASCII_LENGTH 64 #define SHORT_GRAPHEMES_LENGTH 16 -static Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize); static Text_t simple_concatenation(Text_t a, Text_t b); public Text_t EMPTY_TEXT = { @@ -142,6 +181,9 @@ static const TypeInfo_t GraphemeClusterInfo = { #endif public int32_t get_synthetic_grapheme(const ucs4_t *codepoints, int64_t utf32_len) { + if (utf32_len == 1) + return (int32_t)*codepoints; + ucs4_t length_prefixed[1+utf32_len]; length_prefixed[0] = (ucs4_t)utf32_len; for (int i = 0; i < utf32_len; i++) @@ -173,6 +215,7 @@ public int32_t get_synthetic_grapheme(const ucs4_t *codepoints, int64_t utf32_le uint8_t u8_buf[64]; size_t u8_len = sizeof(u8_buf)/sizeof(u8_buf[0]); uint8_t *u8 = u32_to_u8(codepoints, (size_t)utf32_len, u8_buf, &u8_len); + if (u8 == NULL) fail("Invalid graphemes encountered!"); // For performance reasons, use an arena allocator here to ensure that // synthetic graphemes store all of their information in a densely packed @@ -247,6 +290,26 @@ public int Text$print(FILE *stream, Text_t t) uint8_t buf[8]; size_t len = sizeof(buf); uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, buf, &len); + if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme); + written += (int)fwrite(u8, sizeof(char), len, stream); + if (u8 != buf) free(u8); + } else { + const uint8_t *u8 = GRAPHEME_UTF8(grapheme); + assert(u8); + written += (int)fwrite(u8, sizeof(uint8_t), strlen((char*)u8), stream); + } + } + return written; + } + case TEXT_BLOB: { + int written = 0; + for (int64_t i = 0; i < t.length; i++) { + int32_t grapheme = t.blob.map[t.blob.bytes[i]]; + if (grapheme >= 0) { + uint8_t buf[8]; + size_t len = sizeof(buf); + uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, buf, &len); + if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme); written += (int)fwrite(u8, sizeof(char), len, stream); if (u8 != buf) free(u8); } else { @@ -258,8 +321,9 @@ public int Text$print(FILE *stream, Text_t t) return written; } case TEXT_CONCAT: { - return (Text$print(stream, *t.left) - + Text$print(stream, *t.right)); + int written = Text$print(stream, *t.left); + written += Text$print(stream, *t.right); + return written; } default: return 0; } @@ -275,18 +339,24 @@ static const int64_t min_len_for_depth[MAX_TEXT_DEPTH] = { #define IS_BALANCED_TEXT(t) ((t).length >= min_len_for_depth[(t).depth]) -static void insert_balanced(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t to_insert) +static void insert_balanced_recursive(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t text) { + if (text.tag == TEXT_CONCAT && (!IS_BALANCED_TEXT(text) || text.depth >= MAX_TEXT_DEPTH)) { + insert_balanced_recursive(balanced_texts, *text.left); + insert_balanced_recursive(balanced_texts, *text.right); + return; + } + int i = 0; Text_t accumulator = EMPTY_TEXT; - for (; to_insert.length > min_len_for_depth[i + 1]; i++) { + for (; text.length > min_len_for_depth[i + 1]; i++) { if (balanced_texts[i].length) { accumulator = simple_concatenation(balanced_texts[i], accumulator); balanced_texts[i] = EMPTY_TEXT; } } - accumulator = simple_concatenation(accumulator, to_insert); + accumulator = simple_concatenation(accumulator, text); while (accumulator.length >= min_len_for_depth[i]) { if (balanced_texts[i].length) { @@ -299,16 +369,6 @@ static void insert_balanced(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t to_ins balanced_texts[i] = accumulator; } -static void insert_balanced_recursive(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t text) -{ - if (text.tag == TEXT_CONCAT && (!IS_BALANCED_TEXT(text) || text.depth >= MAX_TEXT_DEPTH)) { - insert_balanced_recursive(balanced_texts, *text.left); - insert_balanced_recursive(balanced_texts, *text.right); - } else { - insert_balanced(balanced_texts, text); - } -} - static Text_t rebalanced(Text_t a, Text_t b) { Text_t balanced_texts[MAX_TEXT_DEPTH]; @@ -384,15 +444,25 @@ static Text_t concat2_assuming_safe(Text_t a, Text_t b) if (a.tag == TEXT_GRAPHEMES) { memcpy(dest, a.graphemes, sizeof(int32_t[a.length])); dest += a.length; - } else { + } else if (a.tag == TEXT_ASCII) { for (int64_t i = 0; i < a.length; i++) *(dest++) = (int32_t)a.ascii[i]; + } else if (a.tag == TEXT_BLOB) { + for (int64_t i = 0; i < a.length; i++) + *(dest++) = a.blob.map[a.blob.bytes[i]]; + } else { + errx(1, "Unreachable"); } if (b.tag == TEXT_GRAPHEMES) { memcpy(dest, b.graphemes, sizeof(int32_t[b.length])); - } else { + } else if (b.tag == TEXT_ASCII) { for (int64_t i = 0; i < b.length; i++) *(dest++) = (int32_t)b.ascii[i]; + } else if (b.tag == TEXT_BLOB) { + for (int64_t i = 0; i < b.length; i++) + *(dest++) = b.blob.map[b.blob.bytes[i]]; + } else { + errx(1, "Unreachable"); } return ret; } @@ -455,7 +525,7 @@ static Text_t concat2(Text_t a, Text_t b) return concat2_assuming_safe(a, b); } - Text_t glue = text_from_u32(norm_buf, (int64_t)norm_length, false); + Text_t glue = Text$from_codepoints((List_t){.data=norm_buf, .length=(int64_t)norm_length, .stride=sizeof(int32_t)}); if (normalized != norm_buf) free(normalized); @@ -590,8 +660,8 @@ public Text_t Text$slice(Text_t text, Int_t first_int, Int_t last_int) last -= text.left->length; text = *text.right; } else { - return concat2(Text$slice(*text.left, I(first), I(text.length)), - Text$slice(*text.right, I(1), I(last-text.left->length))); + return concat2_assuming_safe(Text$slice(*text.left, I(first), I(text.length)), + Text$slice(*text.right, I(1), I(last-text.left->length))); } } @@ -610,6 +680,15 @@ public Text_t Text$slice(Text_t text, Int_t first_int, Int_t last_int) .graphemes=text.graphemes + (first-1), }; } + case TEXT_BLOB: { + Text_t ret = (Text_t){ + .tag=TEXT_BLOB, + .length=last - first + 1, + .blob.map=text.blob.map, + .blob.bytes=text.blob.bytes + (first-1), + }; + return ret; + } default: errx(1, "Invalid tag"); } return EMPTY_TEXT; @@ -648,90 +727,64 @@ public Text_t Text$reversed(Text_t text) ((int32_t*)ret.graphemes)[text.length-1-i] = text.graphemes[i]; return ret; } - case TEXT_CONCAT: { - return concat2(Text$reversed(*text.right), Text$reversed(*text.left)); - } - default: errx(1, "Invalid tag"); - } - return EMPTY_TEXT; -} - -public PUREFUNC Text_t Text$cluster(Text_t text, Int_t index_int) -{ - int64_t index = Int64$from_int(index_int, false); - if (index == 0) fail("Invalid index: 0"); - - if (index < 0) index = text.length + index + 1; - - if (index > text.length || index < 1) - fail("Invalid index: ", index_int, " is beyond the length of the text (length = ", (int64_t)text.length, ")"); - - while (text.tag == TEXT_CONCAT) { - if (index <= text.left->length) - text = *text.left; - else - text = *text.right; - } - - switch (text.tag) { - case TEXT_ASCII: { + case TEXT_BLOB: { struct Text_s ret = { - .tag=TEXT_ASCII, - .length=1, - .ascii=GC_MALLOC_ATOMIC(sizeof(char)), + .tag=TEXT_BLOB, + .length=text.length, + .blob.map=text.blob.map, }; - *(char*)&ret.ascii[0] = text.ascii[index-1]; + ret.blob.bytes = GC_MALLOC_ATOMIC(sizeof(uint8_t[ret.length])); + for (int64_t i = 0; i < text.length; i++) + ((uint8_t*)ret.blob.bytes)[text.length-1-i] = text.graphemes[i]; return ret; } - case TEXT_GRAPHEMES: { - struct Text_s ret = { - .tag=TEXT_GRAPHEMES, - .length=1, - .graphemes=GC_MALLOC_ATOMIC(sizeof(int32_t)), - }; - *(int32_t*)&ret.graphemes[0] = text.graphemes[index-1]; - return ret; + case TEXT_CONCAT: { + return concat2_assuming_safe(Text$reversed(*text.right), Text$reversed(*text.left)); } default: errx(1, "Invalid tag"); } return EMPTY_TEXT; } -Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize) +public PUREFUNC Text_t Text$cluster(Text_t text, Int_t index) { - // Normalization is apparently guaranteed to never exceed 3x in the input length - ucs4_t norm_buf[MIN(256, 3*num_codepoints)]; - if (normalize) { - size_t norm_length = sizeof(norm_buf)/sizeof(norm_buf[0]); - ucs4_t *normalized = u32_normalize(UNINORM_NFC, codepoints, (size_t)num_codepoints, norm_buf, &norm_length); - codepoints = normalized; - num_codepoints = (int64_t)norm_length; - } + return Text$slice(text, index, index); +} - // Intentionally overallocate here: allocate assuming each codepoint is a - // grapheme cluster. If that's not true, we'll have extra space at the end - // of the list, but the length will still be calculated correctly. - int32_t *graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[num_codepoints])); - struct Text_s ret = { - .tag=TEXT_GRAPHEMES, - .length=0, - .graphemes=graphemes, - }; - const ucs4_t *src = codepoints; - while (src < &codepoints[num_codepoints]) { - // TODO: use grapheme breaks instead of u32_grapheme_next()? - const ucs4_t *next = u32_grapheme_next(src, &codepoints[num_codepoints]); - if (next == &src[1]) { - graphemes[ret.length] = (int32_t)*src; - } else { - // Synthetic grapheme - graphemes[ret.length] = get_synthetic_grapheme(src, next-src); +static Text_t Text$from_components(List_t graphemes, Table_t unique_clusters) +{ + struct { + int32_t map[unique_clusters.entries.length]; + uint8_t bytes[graphemes.length]; + } *blob; + // If blob optimization will save at least 200 bytes: + if (unique_clusters.entries.length <= 256 && sizeof(*blob) + 200 < sizeof(int32_t[graphemes.length])) { + Text_t ret = { + .tag=TEXT_BLOB, + .length=graphemes.length, + .depth=0, + }; + blob = GC_MALLOC_ATOMIC(sizeof(*blob)); + for (int64_t i = 0; i < unique_clusters.entries.length; i++) { + struct { int32_t g; uint8_t b; } *entry = unique_clusters.entries.data + i*unique_clusters.entries.stride; + blob->map[entry->b] = entry->g; } - ++ret.length; - src = next; + for (int64_t i = 0; i < graphemes.length; i++) { + int32_t g = *(int32_t*)(graphemes.data + i*graphemes.stride); + uint8_t *byte = Table$get(unique_clusters, &g, Table$info(&Int32$info, &Byte$info)); + assert(byte); + blob->bytes[i] = *byte; + } + ret.blob.map = &blob->map[0]; + ret.blob.bytes = &blob->bytes[0]; + return ret; + } else { + return (Text_t){ + .tag=TEXT_GRAPHEMES, + .length=graphemes.length, + .graphemes=graphemes.data, + }; } - if (normalize && codepoints != norm_buf) free(codepoints); - return ret; } public OptionalText_t Text$from_strn(const char *str, size_t len) @@ -748,18 +801,37 @@ public OptionalText_t Text$from_strn(const char *str, size_t len) .length=ascii_span, .ascii=copy, }; - } else { - if (u8_check((uint8_t*)str, len) != NULL) - return NONE_TEXT; - - ucs4_t buf[128]; - size_t length = sizeof(buf)/sizeof(buf[0]); + } + if (u8_check((uint8_t*)str, len) != NULL) + return NONE_TEXT; - ucs4_t *codepoints = u8_to_u32((uint8_t*)str, (size_t)ascii_span + strlen(str + ascii_span), buf, &length); - Text_t ret = text_from_u32(codepoints, (int64_t)length, true); - if (codepoints != buf) free(codepoints); - return ret; + List_t graphemes = {}; + Table_t unique_clusters = {}; + const uint8_t *pos = (const uint8_t*)str; + const uint8_t *end = (const uint8_t*)&str[len]; + // Iterate over grapheme clusters + for (const uint8_t *next; (next=u8_grapheme_next(pos, end)); pos = next) { + uint32_t buf[256]; + size_t u32_len = sizeof(buf)/sizeof(buf[0]); + uint32_t *u32s = u8_to_u32(pos, (size_t)(next-pos), buf, &u32_len); + + uint32_t buf2[256]; + size_t u32_normlen = sizeof(buf2)/sizeof(buf2[0]); + uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, u32s, u32_len, buf2, &u32_normlen); + + int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen); + List$insert(&graphemes, &g, I(0), sizeof(int32_t)); + Table$get_or_setdefault(&unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length, Table$info(&Int32$info, &Byte$info)); + + if (u32s != buf) free(u32s); + if (u32s_normalized != buf2) free(u32s_normalized); + + if (unique_clusters.entries.length >= 256) { + return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters), Text$from_strn(next, (size_t)(end-next))); + } } + + return Text$from_components(graphemes, unique_clusters); } public OptionalText_t Text$from_str(const char *str) @@ -788,6 +860,7 @@ static void u8_buf_append(Text_t text, char **buf, int64_t *capacity, int64_t *i uint8_t u8_buf[64]; size_t u8_len = sizeof(u8_buf); uint8_t *u8 = u32_to_u8((ucs4_t*)&graphemes[g], 1, u8_buf, &u8_len); + if (u8 == NULL) fail("Invalid grapheme encountered: ", graphemes[g]); if (*i + (int64_t)u8_len > (int64_t)*capacity) { *capacity = *i + (int64_t)u8_len + 1; @@ -811,6 +884,37 @@ static void u8_buf_append(Text_t text, char **buf, int64_t *capacity, int64_t *i } break; } + case TEXT_BLOB: { + for (int64_t g = 0; g < text.length; g++) { + int32_t grapheme = text.blob.map[text.blob.bytes[g]]; + if (grapheme >= 0) { + uint8_t u8_buf[64]; + size_t u8_len = sizeof(u8_buf); + uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, u8_buf, &u8_len); + if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme); + + if (*i + (int64_t)u8_len > (int64_t)*capacity) { + *capacity = *i + (int64_t)u8_len + 1; + *buf = GC_REALLOC(*buf, (size_t)*capacity); + } + + memcpy(*buf + *i, u8, u8_len); + *i += (int64_t)u8_len; + if (u8 != u8_buf) free(u8); + } else { + const uint8_t *u8 = GRAPHEME_UTF8(grapheme); + size_t u8_len = u8_strlen(u8); + if (*i + (int64_t)u8_len > (int64_t)*capacity) { + *capacity = *i + (int64_t)u8_len + 1; + *buf = GC_REALLOC(*buf, (size_t)*capacity); + } + + memcpy(*buf + *i, u8, u8_len); + *i += (int64_t)u8_len; + } + } + break; + } case TEXT_CONCAT: { u8_buf_append(*text.left, buf, capacity, i); u8_buf_append(*text.right, buf, capacity, i); @@ -867,6 +971,15 @@ PUREFUNC public uint64_t Text$hash(const void *obj, const TypeInfo_t *info) int32_t last = text.length & 0x1 ? graphemes[text.length-1] : 0; // Odd number of graphemes return siphashfinish_last_part(&sh, (uint64_t)last); } + case TEXT_BLOB: { + for (int64_t i = 0; i + 1 < text.length; i += 2) { + tmp.chunks[0] = text.blob.map[text.blob.bytes[i]]; + tmp.chunks[1] = text.blob.map[text.blob.bytes[i+1]]; + siphashadd64bits(&sh, tmp.whole); + } + int32_t last = text.length & 0x1 ? text.blob.map[text.blob.bytes[text.length-1]] : 0; // Odd number of graphemes + return siphashfinish_last_part(&sh, (uint64_t)last); + } case TEXT_CONCAT: { TextIter_t state = NEW_TEXT_ITER_STATE(text); for (int64_t i = 0; i + 1 < text.length; i += 2) { @@ -928,6 +1041,7 @@ public int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index) switch (text.tag) { case TEXT_ASCII: return (int32_t)text.ascii[index - offset]; case TEXT_GRAPHEMES: return text.graphemes[index - offset]; + case TEXT_BLOB: return text.blob.map[text.blob.bytes[index - offset]]; default: errx(1, "Invalid text"); } return 0; @@ -1286,11 +1400,9 @@ public Text_t Text$upper(Text_t text, Text_t language) if (text.length == 0) return text; List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); - ucs4_t buf[128]; - size_t out_len = sizeof(buf)/sizeof(buf[0]); - ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len); - Text_t ret = text_from_u32(upper, (int64_t)out_len, false); - if (upper != buf) free(upper); + size_t out_len = 0; + ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len); + Text_t ret = Text$from_codepoints((List_t){.data=upper, .length=(int64_t)out_len, .stride=sizeof(int32_t)}); return ret; } @@ -1299,11 +1411,9 @@ public Text_t Text$lower(Text_t text, Text_t language) if (text.length == 0) return text; List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); - ucs4_t buf[128]; - size_t out_len = sizeof(buf)/sizeof(buf[0]); - ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len); - Text_t ret = text_from_u32(lower, (int64_t)out_len, false); - if (lower != buf) free(lower); + size_t out_len = 0; + ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len); + Text_t ret = Text$from_codepoints((List_t){.data=lower, .length=(int64_t)out_len, .stride=sizeof(int32_t)}); return ret; } @@ -1312,11 +1422,9 @@ public Text_t Text$title(Text_t text, Text_t language) if (text.length == 0) return text; List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); - ucs4_t buf[128]; - size_t out_len = sizeof(buf)/sizeof(buf[0]); - ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len); - Text_t ret = text_from_u32(title, (int64_t)out_len, false); - if (title != buf) free(title); + size_t out_len = 0; + ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len); + Text_t ret = Text$from_codepoints((List_t){.data=title, .length=(int64_t)out_len, .stride=sizeof(int32_t)}); return ret; } @@ -1332,12 +1440,20 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark) ret = concat2_assuming_safe(ret, quotation_mark); int32_t quote_char = Text$get_grapheme(quotation_mark, 0); -#define add_escaped(str) ({ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); \ +#define flush_unquoted() ({ \ + if (unquoted_span > 0) { \ + ret = concat2_assuming_safe(ret, Text$slice(text, I(i-unquoted_span+1), I(i))); \ + unquoted_span = 0; \ + } }) +#define add_escaped(str) ({ \ + flush_unquoted(); \ + if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); \ ret = concat2_assuming_safe(ret, Text("\\" str)); \ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m")); }) TextIter_t state = NEW_TEXT_ITER_STATE(text); - // TODO: optimize for spans of non-escaped text - for (int64_t i = 0; i < text.length; i++) { + int64_t unquoted_span = 0; + int64_t i = 0; + for (i = 0; i < text.length; i++) { int32_t g = Text$get_grapheme_fast(&state, i); switch (g) { case '\a': add_escaped("a"); break; @@ -1358,6 +1474,7 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark) } case '\x00' ... '\x06': case '\x0E' ... '\x1A': case '\x1C' ... '\x1F': case '\x7F' ... '\x7F': { + flush_unquoted(); if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); ret = concat2_assuming_safe(ret, Text("\\x")); char tmp[3] = { @@ -1372,15 +1489,21 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark) } default: { if (g == quote_char) { + flush_unquoted(); + if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); + ret = concat2_assuming_safe(ret, Text("\\")); ret = concat2_assuming_safe(ret, quotation_mark); + if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m")); } else { - ret = concat2_assuming_safe(ret, Text$slice(text, I(i+1), I(i+1))); + unquoted_span += 1; } break; } } } + flush_unquoted(); #undef add_escaped +#undef flush_unquoted ret = concat2_assuming_safe(ret, quotation_mark); if (colorize) @@ -1513,10 +1636,38 @@ public List_t Text$codepoint_names(Text_t text) public Text_t Text$from_codepoints(List_t codepoints) { - if (codepoints.stride != sizeof(int32_t)) - List$compact(&codepoints, sizeof(int32_t)); - - return text_from_u32(codepoints.data, codepoints.length, true); + if (codepoints.stride != sizeof(uint32_t)) + List$compact(&codepoints, sizeof(uint32_t)); + + List_t graphemes = {}; + Table_t unique_clusters = {}; + const uint32_t *pos = (const uint32_t*)codepoints.data; + const uint32_t *end = (const uint32_t*)&pos[codepoints.length]; + // Iterate over grapheme clusters + for (const uint32_t *next; (next=u32_grapheme_next(pos, end)); pos = next) { + // Buffer for normalized cluster: + uint32_t buf[256]; + size_t u32_normlen = sizeof(buf)/sizeof(buf[0]); + uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, pos, (size_t)(next-pos), buf, &u32_normlen); + + int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen); + List$insert(&graphemes, &g, I(0), sizeof(int32_t)); + Table$get_or_setdefault( + &unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length, + Table$info(&Int32$info, &Byte$info)); + + if (u32s_normalized != buf) free(u32s_normalized); + + if (unique_clusters.entries.length == 256) { + List_t remaining_codepoints = { + .length=(int64_t)(end-next), + .data=(void*)next, + .stride=sizeof(int32_t), + }; + return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters), Text$from_codepoints(remaining_codepoints)); + } + } + return Text$from_components(graphemes, unique_clusters); } public OptionalText_t Text$from_codepoint_names(List_t codepoint_names) @@ -1605,6 +1756,38 @@ PUREFUNC public bool Text$is_none(const void *t, const TypeInfo_t *info) return ((Text_t*)t)->length < 0; } +public Int_t Text$memory_size(Text_t text) +{ + switch (text.tag) { + case TEXT_ASCII: + return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(char[text.length])); + case TEXT_GRAPHEMES: + return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(int32_t[text.length])); + case TEXT_BLOB: + return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)((void*)text.blob.bytes - (void*)text.blob.map) + (int64_t)sizeof(uint8_t[text.length])); + case TEXT_CONCAT: + return Int$plus( + Int$from_int64((int64_t)sizeof(Text_t)), + Int$plus(Text$memory_size(*text.left), Text$memory_size(*text.right))); + default: errx(1, "Invalid text tag: ", text.tag); + } +} + +public Text_t Text$layout(Text_t text) +{ + switch (text.tag) { + case TEXT_ASCII: + return Texts(Text("ASCII("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")")); + case TEXT_GRAPHEMES: + return Texts(Text("Graphemes("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")")); + case TEXT_BLOB: + return Texts(Text("Blob("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")")); + case TEXT_CONCAT: + return Texts(Text("Concat("), Text$layout(*text.left), Text(", "), Text$layout(*text.right), Text(")")); + default: errx(1, "Invalid text tag: ", text.tag); + } +} + public void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *info) { (void)info; diff --git a/src/stdlib/text.h b/src/stdlib/text.h index 47ede6f1..fc336612 100644 --- a/src/stdlib/text.h +++ b/src/stdlib/text.h @@ -78,6 +78,8 @@ Text_t Text$right_pad(Text_t text, Int_t width, Text_t padding, Text_t language) Text_t Text$middle_pad(Text_t text, Int_t width, Text_t padding, Text_t language); int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index); uint32_t Text$get_main_grapheme_fast(TextIter_t *state, int64_t index); +Int_t Text$memory_size(Text_t text); +Text_t Text$layout(Text_t text); void Text$serialize(const void *obj, FILE *out, Table_t *, const TypeInfo_t *); void Text$deserialize(FILE *in, void *out, List_t *, const TypeInfo_t *); |