From 8ba0615b0fe832a15eb695ccd661674b6946995c Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 28 Sep 2026 11:41:43 +0100 Subject: Resolve bidirectional text as UAX #9 does, passing all of Unicode's bidi tests --- text/bidi.c | 351 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 351 insertions(+) create mode 100644 text/bidi.c (limited to 'text/bidi.c') diff --git a/text/bidi.c b/text/bidi.c new file mode 100644 index 0000000..d2f95c9 --- /dev/null +++ b/text/bidi.c @@ -0,0 +1,351 @@ +/* The Unicode Bidirectional Algorithm (UAX #9, Unicode 15.1), for one + * paragraph laid out as one line: text/text.h. Rules are named as in the + * annex; the tests are Unicode's own (BidiTest.txt, BidiCharacterTest.txt). */ +#include "text.h" +#include +#include + +enum { MAX_DEPTH = 125, BRACKETS = 63 }; +typedef VegaBidiClass Class; + +static bool initiator(Class c) { return c == VEGA_BIDI_LRI || c == VEGA_BIDI_RLI || c == VEGA_BIDI_FSI; } +static bool removed(Class c) { + return c == VEGA_BIDI_RLE || c == VEGA_BIDI_LRE || c == VEGA_BIDI_RLO || c == VEGA_BIDI_LRO || c == VEGA_BIDI_PDF || + c == VEGA_BIDI_BN; +} +/* Neutral or isolate formatting character (NI). */ +static bool neutral(Class c) { + return c == VEGA_BIDI_B || c == VEGA_BIDI_S || c == VEGA_BIDI_WS || c == VEGA_BIDI_ON || initiator(c) || + c == VEGA_BIDI_PDI; +} +/* A strong direction for N0 and N1: L, or R for R, AL, EN and AN; else -1. */ +static int strong(Class c) { + if (c == VEGA_BIDI_L) return VEGA_BIDI_L; + if (c == VEGA_BIDI_R || c == VEGA_BIDI_AL || c == VEGA_BIDI_EN || c == VEGA_BIDI_AN) return VEGA_BIDI_R; + return -1; +} + +/* P2-P3 over [from, to): 1 when the first strong character (skipping + * isolates to their matching PDI) is R or AL, 0 when it is L, -1 when there + * is none. */ +static int first_strong(const Class *t, const size_t *match, size_t from, size_t to) { + for (size_t i = from; i < to; ++i) { + if (t[i] == VEGA_BIDI_L) return 0; + if (t[i] == VEGA_BIDI_R || t[i] == VEGA_BIDI_AL) return 1; + if (initiator(t[i])) { + if (match[i] >= to) return -1; + i = match[i]; + } + } + return -1; +} + +/* U+2329 and U+232A are canonically U+3008 and U+3009 (BD16). */ +static uint32_t canonical(uint32_t code) { return code == 0x2329 ? 0x3008 : code == 0x232A ? 0x3009 : code; } + +typedef struct { size_t open, close; } Pair; /* positions in a sequence of an opening bracket and its closing one */ + +typedef struct { + const Class *original; + Class *t; + uint8_t *levels; + const uint32_t *codes; + size_t *seq; /* the isolating run sequence's characters */ + size_t count; + uint8_t level; + Class sos, eos; + Pair *pairs; /* room for count / 2 + 1 */ +} Sequence; + +static int by_opening(const void *a, const void *b) { + const Pair *x = a, *y = b; + return (x->open > y->open) - (x->open < y->open); +} + +static Class before(const Sequence *s, size_t k) { return k ? s->t[s->seq[k - 1]] : s->sos; } + +static void weak_types(Sequence *s) { + Class *t = s->t; + size_t *seq = s->seq, m = s->count; + for (size_t k = 0; k < m; ++k) /* W1 */ + if (t[seq[k]] == VEGA_BIDI_NSM) { + Class previous = before(s, k); + t[seq[k]] = initiator(previous) || previous == VEGA_BIDI_PDI ? VEGA_BIDI_ON : previous; + } + Class last = s->sos; /* W2, W3 */ + for (size_t k = 0; k < m; ++k) { + Class c = t[seq[k]]; + if (c == VEGA_BIDI_L || c == VEGA_BIDI_R || c == VEGA_BIDI_AL) last = c; + else if (c == VEGA_BIDI_EN && last == VEGA_BIDI_AL) t[seq[k]] = VEGA_BIDI_AN; + } + for (size_t k = 0; k < m; ++k) + if (t[seq[k]] == VEGA_BIDI_AL) t[seq[k]] = VEGA_BIDI_R; + for (size_t k = 1; k + 1 < m; ++k) { /* W4 */ + Class c = t[seq[k]], p = t[seq[k - 1]], n = t[seq[k + 1]]; + if (c == VEGA_BIDI_ES && p == VEGA_BIDI_EN && n == VEGA_BIDI_EN) t[seq[k]] = VEGA_BIDI_EN; + else if (c == VEGA_BIDI_CS && p == n && (p == VEGA_BIDI_EN || p == VEGA_BIDI_AN)) t[seq[k]] = p; + } + for (size_t k = 0; k < m;) { /* W5 */ + if (t[seq[k]] != VEGA_BIDI_ET) { ++k; continue; } + size_t end = k; + while (end < m && t[seq[end]] == VEGA_BIDI_ET) ++end; + bool number = (k && t[seq[k - 1]] == VEGA_BIDI_EN) || (end < m && t[seq[end]] == VEGA_BIDI_EN); + for (; k < end; ++k) + if (number) t[seq[k]] = VEGA_BIDI_EN; + } + for (size_t k = 0; k < m; ++k) { /* W6 */ + Class c = t[seq[k]]; + if (c == VEGA_BIDI_ES || c == VEGA_BIDI_ET || c == VEGA_BIDI_CS) t[seq[k]] = VEGA_BIDI_ON; + } + last = s->sos; /* W7 */ + for (size_t k = 0; k < m; ++k) { + Class c = t[seq[k]]; + if (c == VEGA_BIDI_L || c == VEGA_BIDI_R) last = c; + else if (c == VEGA_BIDI_EN && last == VEGA_BIDI_L) t[seq[k]] = VEGA_BIDI_L; + } +} + +/* N0: paired brackets take the direction of what they enclose. */ +static void brackets(Sequence *s) { + if (!s->codes) return; + Class *t = s->t; + size_t *seq = s->seq, m = s->count; + Pair *pairs = s->pairs; + size_t found = 0; + struct { uint32_t pair; size_t at; } open[BRACKETS]; + size_t depth = 0; + for (size_t k = 0; k < m; ++k) { + uint32_t pair, code = s->codes[seq[k]]; + int kind = t[seq[k]] == VEGA_BIDI_ON ? vega_bracket(code, &pair) : 0; + if (kind == 1) { + if (depth == BRACKETS) break; /* BD16: no more pairs in this sequence */ + open[depth].pair = canonical(pair); + open[depth++].at = k; + } else if (kind == 2) { + for (size_t d = depth; d-- > 0;) + if (open[d].pair == canonical(code)) { + pairs[found].open = open[d].at, pairs[found++].close = k; + depth = d; + break; + } + } + } + qsort(pairs, found, sizeof(*pairs), by_opening); /* in the order of the opening brackets */ + Class embedding = s->level & 1 ? VEGA_BIDI_R : VEGA_BIDI_L, opposite = embedding == VEGA_BIDI_L ? VEGA_BIDI_R : VEGA_BIDI_L; + for (size_t p = 0; p < found; ++p) { + size_t open_at = pairs[p].open, close_at = pairs[p].close; + bool same = false, other = false; + for (size_t k = open_at + 1; k < close_at; ++k) { + int d = strong(t[seq[k]]); + if (d == (int)embedding) same = true; + else if (d >= 0) other = true; + } + Class resolved; + if (same) resolved = embedding; + else if (other) { + Class context = s->sos; + for (size_t k = open_at; k-- > 0;) + if (strong(t[seq[k]]) >= 0) { context = (Class)strong(t[seq[k]]); break; } + resolved = context == opposite ? opposite : embedding; + } else + continue; + size_t ends[2] = {open_at, close_at}; + for (unsigned e = 0; e < 2; ++e) { + t[seq[ends[e]]] = resolved; + /* Marks that followed the bracket (made ON by W1) follow it. */ + for (size_t k = ends[e] + 1; k < m && s->original[seq[k]] == VEGA_BIDI_NSM; ++k) t[seq[k]] = resolved; + } + } +} + +static void neutral_types(Sequence *s) { + Class *t = s->t; + size_t *seq = s->seq, m = s->count; + Class embedding = s->level & 1 ? VEGA_BIDI_R : VEGA_BIDI_L; + for (size_t k = 0; k < m;) { /* N1, N2 */ + if (!neutral(t[seq[k]])) { ++k; continue; } + size_t end = k; + while (end < m && neutral(t[seq[end]])) ++end; + int left = k ? strong(t[seq[k - 1]]) : (int)s->sos, right = end < m ? strong(t[seq[end]]) : (int)s->eos; + Class resolved = left >= 0 && left == right ? (Class)left : embedding; + for (; k < end; ++k) t[seq[k]] = resolved; + } + for (size_t k = 0; k < m; ++k) { /* I1, I2 */ + Class c = t[seq[k]]; + uint8_t *level = &s->levels[seq[k]]; + if (!(*level & 1)) *level += c == VEGA_BIDI_R ? 1 : c == VEGA_BIDI_AN || c == VEGA_BIDI_EN ? 2 : 0; + else *level += c == VEGA_BIDI_L || c == VEGA_BIDI_EN || c == VEGA_BIDI_AN ? 1 : 0; + } +} + +int vega_bidi_levels(const VegaBidiClass *classes, const uint32_t *codes, size_t count, int direction, uint8_t *levels) { + if (!count) return direction == VEGA_BIDI_RTL ? 1 : 0; + size_t *match = malloc(count * sizeof(*match)), *runs = malloc((count + 1) * sizeof(*runs)), + *run_of = malloc(count * sizeof(*run_of)), *seq = malloc(count * sizeof(*seq)); + Class *t = malloc(count * sizeof(*t)); + bool *matched_pdi = calloc(count, sizeof(*matched_pdi)); + Pair *pairs = malloc((count / 2 + 1) * sizeof(*pairs)); + uint8_t *embedding = malloc(count); + int paragraph = -1; + if (!match || !runs || !run_of || !seq || !t || !matched_pdi || !pairs || !embedding) goto done; + memcpy(t, classes, count * sizeof(*t)); + /* BD9: each isolate initiator's matching PDI (count: none). */ + { + size_t depth = 0; + for (size_t i = 0; i < count; ++i) { + match[i] = count; + if (initiator(t[i])) runs[depth++] = i; /* runs as a stack here */ + else if (t[i] == VEGA_BIDI_PDI && depth) { + match[runs[--depth]] = i; + matched_pdi[i] = true; + } + } + } + /* P2, P3 */ + paragraph = direction == VEGA_BIDI_RTL ? 1 : direction == VEGA_BIDI_LTR ? 0 : first_strong(t, match, 0, count) == 1; + /* X1-X8: explicit levels and directions. */ + struct { uint8_t level; Class override; bool isolate; } stack[MAX_DEPTH + 2]; + size_t depth = 0; + unsigned overflow_isolates = 0, overflow_embeddings = 0, valid_isolates = 0; + stack[depth].level = (uint8_t)paragraph, stack[depth].override = VEGA_BIDI_ON, stack[depth++].isolate = false; + for (size_t i = 0; i < count; ++i) { + Class c = classes[i]; + uint8_t level = stack[depth - 1].level; + switch (c) { + case VEGA_BIDI_RLE: case VEGA_BIDI_LRE: case VEGA_BIDI_RLO: case VEGA_BIDI_LRO: { + bool rtl = c == VEGA_BIDI_RLE || c == VEGA_BIDI_RLO; + uint8_t next = rtl ? (uint8_t)((level + 1) | 1) : (uint8_t)((level + 2) & ~1); + levels[i] = level; + if (next <= MAX_DEPTH && !overflow_isolates && !overflow_embeddings) { + stack[depth].level = next; + stack[depth].override = c == VEGA_BIDI_RLO ? VEGA_BIDI_R : c == VEGA_BIDI_LRO ? VEGA_BIDI_L : VEGA_BIDI_ON; + stack[depth++].isolate = false; + } else if (!overflow_isolates) + ++overflow_embeddings; + break; + } + case VEGA_BIDI_RLI: case VEGA_BIDI_LRI: case VEGA_BIDI_FSI: { + levels[i] = level; + if (stack[depth - 1].override != VEGA_BIDI_ON) t[i] = stack[depth - 1].override; + bool rtl = c == VEGA_BIDI_RLI || (c == VEGA_BIDI_FSI && first_strong(classes, match, i + 1, match[i]) == 1); + uint8_t next = rtl ? (uint8_t)((level + 1) | 1) : (uint8_t)((level + 2) & ~1); + if (next <= MAX_DEPTH && !overflow_isolates && !overflow_embeddings) { + ++valid_isolates; + stack[depth].level = next, stack[depth].override = VEGA_BIDI_ON, stack[depth++].isolate = true; + } else + ++overflow_isolates; + break; + } + case VEGA_BIDI_PDI: + if (overflow_isolates) --overflow_isolates; + else if (valid_isolates) { + overflow_embeddings = 0; + while (!stack[depth - 1].isolate) --depth; + --depth; + --valid_isolates; + } + levels[i] = stack[depth - 1].level; + if (stack[depth - 1].override != VEGA_BIDI_ON) t[i] = stack[depth - 1].override; + break; + case VEGA_BIDI_PDF: + levels[i] = level; + if (overflow_isolates) break; + if (overflow_embeddings) --overflow_embeddings; + else if (!stack[depth - 1].isolate && depth >= 2) --depth; + break; + case VEGA_BIDI_B: levels[i] = (uint8_t)paragraph; break; /* X8 */ + case VEGA_BIDI_BN: levels[i] = level; break; + default: + levels[i] = level; + if (stack[depth - 1].override != VEGA_BIDI_ON) t[i] = stack[depth - 1].override; + } + } + /* X9, X10: level runs of the characters that stay, and the isolating run + * sequences they make (a run ending in an isolate initiator continues + * with the run its matching PDI begins), by the explicit levels (the + * sequences' own resolution changes levels). */ + memcpy(embedding, levels, count); + size_t run_count = 0; + for (size_t i = 0; i < count; ++i) { + if (removed(classes[i])) continue; + bool starts = true; + for (size_t j = i; j-- > 0;) + if (!removed(classes[j])) { starts = embedding[j] != embedding[i]; break; } + if (starts) runs[run_count++] = i; + run_of[i] = run_count - 1; + } + for (size_t r = 0; r < run_count; ++r) { + size_t first = runs[r]; + if (classes[first] == VEGA_BIDI_PDI && matched_pdi[first]) continue; /* it continues another sequence */ + Sequence s = {classes, t, levels, codes, seq, 0, embedding[first], VEGA_BIDI_L, VEGA_BIDI_L, pairs}; + for (size_t run = r;;) { + size_t last = runs[run]; + for (size_t i = runs[run]; i < count && (removed(classes[i]) || run_of[i] == run); ++i) + if (!removed(classes[i])) seq[s.count++] = last = i; + if (!initiator(classes[last]) || match[last] >= count) break; + run = run_of[match[last]]; + } + size_t head = seq[0], tail = seq[s.count - 1]; + int previous = paragraph, next = paragraph; + for (size_t j = head; j-- > 0;) + if (!removed(classes[j])) { previous = embedding[j]; break; } + if (!initiator(classes[tail])) + for (size_t j = tail + 1; j < count; ++j) + if (!removed(classes[j])) { next = embedding[j]; break; } + s.sos = ((s.level > previous ? s.level : previous) & 1) ? VEGA_BIDI_R : VEGA_BIDI_L; + s.eos = ((s.level > next ? s.level : next) & 1) ? VEGA_BIDI_R : VEGA_BIDI_L; + weak_types(&s); + brackets(&s); + neutral_types(&s); + } + /* L1: separators, and whitespace and isolate controls before them or at + * the end of the line, go back to the paragraph's level. */ + for (size_t i = count, trailing = 1; i-- > 0;) { + Class c = classes[i]; + if (c == VEGA_BIDI_S || c == VEGA_BIDI_B) { + levels[i] = (uint8_t)paragraph; + trailing = 1; + } else if (c == VEGA_BIDI_WS || initiator(c) || c == VEGA_BIDI_PDI || removed(c)) { + if (trailing) levels[i] = (uint8_t)paragraph; + } else + trailing = 0; + } + for (size_t i = 0; i < count; ++i) + if (removed(classes[i])) levels[i] = VEGA_BIDI_REMOVED; +done: + free(match); + free(runs); + free(run_of); + free(seq); + free(t); + free(matched_pdi); + free(pairs); + free(embedding); + return paragraph; +} + +size_t vega_bidi_order(const uint8_t *levels, size_t count, uint32_t *order) { + size_t n = 0; + uint8_t highest = 0, lowest_odd = 0xff; + for (size_t i = 0; i < count; ++i) { + if (levels[i] == VEGA_BIDI_REMOVED) continue; + order[n++] = (uint32_t)i; + if (levels[i] > highest) highest = levels[i]; + if ((levels[i] & 1) && levels[i] < lowest_odd) lowest_odd = levels[i]; + } + /* L2: from the highest level down to the lowest odd one, reverse every + * run of characters at that level or higher. */ + for (int level = highest; level >= lowest_odd && lowest_odd != 0xff; --level) + for (size_t k = 0; k < n;) { + if (levels[order[k]] < level) { ++k; continue; } + size_t end = k; + while (end < n && levels[order[end]] >= level) ++end; + for (size_t a = k, b = end - 1; a < b; ++a, --b) { + uint32_t swap = order[a]; + order[a] = order[b]; + order[b] = swap; + } + k = end; + } + return n; +} -- cgit v1.2.3