Skip to content

LordOS — a free, fast and secure GNU/Linux distribution based on Debian, with its own desktop environment: display server and Wayland compositor in C, a React UI engine on QuickJS, and private native apps.

14.8 KB
Raw Blame
/* bidi.c — Unicode bidirectional algorithm (UAX #9, Unicode 15.1 revision), complete:
 * explicit embeddings and overrides (LRE/RLE/LRO/RLO/PDF), isolates (LRI/RLI/FSI/PDI),
 * isolating run sequences, rules W1–W7, bracket pairs (N0), N1–N2, I1–I2 and,
 * per line, L1–L2. Verified with BidiCharacterTest.txt (server/tests/bidi_test.c).
 *
 * The tables come from unicode.c (tools/gen-unicode.mjs). No fribidi or ICU. */
#include "bidi.h"

#include <stdlib.h>
#include <string.h>

#include "unicode.h"

#define MAX_DEPTH 125
#define MAX_BRACKETS 63

int bidi_class(uint32_t cp) { return uc_bidi(cp); }
uint32_t bidi_mirror(uint32_t cp) { return uc_mirror(cp); }

/* Pair of a bracket normalized by canonical equivalence (U+2329 = U+3008). */
static uint32_t canon(uint32_t cp) { return cp == 0x2329 ? 0x3008 : cp == 0x232A ? 0x3009 : cp; }
static uint32_t bracket(uint32_t cp, int *open) { uint32_t b = uc_bracket(cp, open); return b ? canon(b) : 0; }

static int is_isolate_init(int t) { return t == BIDI_LRI || t == BIDI_RLI || t == BIDI_FSI; }
static int is_removed(int t) {
    return t == BIDI_LRE || t == BIDI_RLE || t == BIDI_LRO || t == BIDI_RLO || t == BIDI_PDF || t == BIDI_BN;
}
static int is_ni(int t) {
    return t == BIDI_B || t == BIDI_S || t == BIDI_WS || t == BIDI_ON || is_isolate_init(t) || t == BIDI_PDI;
}
/* Strong direction for N0/N1: L, or R (EN and AN count as R); -1 if neutral. */
static int strong_dir(int t) {
    if (t == BIDI_L) return BIDI_L;
    if (t == BIDI_R || t == BIDI_AL || t == BIDI_EN || t == BIDI_AN) return BIDI_R;
    return -1;
}

/* P2/P3 over [start, end), skipping what lies between an isolate and its PDI. */
static int first_strong(const uint8_t *t, const int *match, int start, int end) {
    for (int i = start; i < end; i++) {
        if (t[i] == BIDI_L) return 0;
        if (t[i] == BIDI_R || t[i] == BIDI_AL) return 1;
        if (t[i] == BIDI_B) break;
        if (is_isolate_init(t[i])) {
            if (match[i] < 0) break;
            i = match[i];
        }
    }
    return -1;
}

/* BD9: PDI that closes each isolate (-1 if none). */
static void match_isolates(const uint8_t *t, int n, int *match, int *stack) {
    int sp = 0;
    for (int i = 0; i < n; i++) {
        match[i] = -1;
        if (is_isolate_init(t[i])) stack[sp++] = i;
        else if (t[i] == BIDI_PDI && sp > 0) match[stack[--sp]] = i;
        else if (t[i] == BIDI_B) sp = 0;
    }
}

int bidi_direction(const uint32_t *cp, int n) {
    int depth = 0;
    for (int i = 0; i < n; i++) {
        int t = bidi_class(cp[i]);
        if (is_isolate_init(t)) depth++;
        else if (t == BIDI_PDI) { if (depth > 0) depth--; }
        else if (t == BIDI_B) break;
        else if (!depth && t == BIDI_L) return 0;
        else if (!depth && (t == BIDI_R || t == BIDI_AL)) return 1;
    }
    return -1;
}

typedef struct {
    const uint32_t *cp;
    const uint8_t *orig;        /* original classes */
    uint8_t *t;                 /* classes that keep changing */
    uint8_t *levels;
    const uint8_t *elev;        /* embedding levels (X1–X8), before I1/I2 */
    int n, para;
} Para;

/* Resolves an isolating run sequence (W1–I2). idx: its characters in order. */
static void resolve_sequence(Para *p, const int *idx, int m, uint8_t *t, uint8_t *pre) {
    int level = p->elev[idx[0]];
    /* sos / eos */
    int before = p->para;
    for (int i = idx[0] - 1; i >= 0; i--) if (!is_removed(p->orig[i])) { before = p->elev[i]; break; }
    int after = p->para, last = idx[m - 1];
    if (!is_isolate_init(p->orig[last]))
        for (int i = last + 1; i < p->n; i++) if (!is_removed(p->orig[i])) { after = p->elev[i]; break; }
    int sos = ((before > level ? before : level) & 1) ? BIDI_R : BIDI_L;
    int eos = ((after > level ? after : level) & 1) ? BIDI_R : BIDI_L;

    for (int k = 0; k < m; k++) pre[k] = t[k] = p->t[idx[k]];

    /* W1: NSM takes the class of the previous one (ON after an isolate or PDI). */
    for (int k = 0; k < m; k++)
        if (t[k] == BIDI_NSM) t[k] = k == 0 ? (uint8_t)sos : is_isolate_init(t[k - 1]) || t[k - 1] == BIDI_PDI ? BIDI_ON : t[k - 1];
    /* W2: EN after AL → AN.  W3: AL → R. */
    int last_strong = sos;
    for (int k = 0; k < m; k++) {
        if (t[k] == BIDI_L || t[k] == BIDI_R || t[k] == BIDI_AL) last_strong = t[k];
        else if (t[k] == BIDI_EN && last_strong == BIDI_AL) t[k] = BIDI_AN;
    }
    for (int k = 0; k < m; k++) if (t[k] == BIDI_AL) t[k] = BIDI_R;
    /* W4: an ES between ENs, a CS between ENs or between ANs. */
    for (int k = 1; k + 1 < m; k++) {
        if (t[k] == BIDI_ES && t[k - 1] == BIDI_EN && t[k + 1] == BIDI_EN) t[k] = BIDI_EN;
        else if (t[k] == BIDI_CS && t[k - 1] == BIDI_EN && t[k + 1] == BIDI_EN) t[k] = BIDI_EN;
        else if (t[k] == BIDI_CS && t[k - 1] == BIDI_AN && t[k + 1] == BIDI_AN) t[k] = BIDI_AN;
    }
    /* W5: ET next to EN → EN. */
    for (int k = 0; k < m; k++) {
        if (t[k] != BIDI_ET) continue;
        int e = k;
        while (e < m && t[e] == BIDI_ET) e++;
        if ((k > 0 && t[k - 1] == BIDI_EN) || (e < m && t[e] == BIDI_EN))
            for (int j = k; j < e; j++) t[j] = BIDI_EN;
        k = e - 1;
    }
    /* W6: the remaining separators → ON.  W7: EN after L → L. */
    for (int k = 0; k < m; k++) if (t[k] == BIDI_ES || t[k] == BIDI_ET || t[k] == BIDI_CS) t[k] = BIDI_ON;
    last_strong = sos;
    for (int k = 0; k < m; k++) {
        if (t[k] == BIDI_L || t[k] == BIDI_R) last_strong = t[k];
        else if (t[k] == BIDI_EN && last_strong == BIDI_L) t[k] = BIDI_L;
    }

    /* N0: bracket pairs (BD16). */
    int e_dir = (level & 1) ? BIDI_R : BIDI_L;
    int stack_pos[MAX_BRACKETS];
    uint32_t stack_cp[MAX_BRACKETS];
    int sp = 0, npairs = 0, cap = 0;
    int *pairs = NULL;              /* [open, close] per pair */
    for (int k = 0; k < m; k++) {
        if (t[k] != BIDI_ON) continue;
        int open;
        uint32_t other = bracket(p->cp[idx[k]], &open);
        if (!other) continue;
        if (open) {
            if (sp == MAX_BRACKETS) { npairs = 0; break; }
            stack_pos[sp] = k;
            stack_cp[sp++] = other;
        } else {
            uint32_t me = canon(p->cp[idx[k]]);
            for (int s = sp - 1; s >= 0; s--) {
                if (stack_cp[s] != me) continue;
                if (npairs == cap) {
                    cap = cap ? cap * 2 : 16;
                    int *np = realloc(pairs, sizeof(int) * 2 * (size_t)cap);
                    if (!np) { npairs = 0; sp = 0; break; }
                    pairs = np;
                }
                pairs[2 * npairs] = stack_pos[s];
                pairs[2 * npairs + 1] = k;
                npairs++;
                sp = s;
                break;
            }
        }
    }
    /* sort by opening position (insertion: there are usually few) */
    for (int a = 1; a < npairs; a++) {
        int o = pairs[2 * a], c = pairs[2 * a + 1], b = a - 1;
        while (b >= 0 && pairs[2 * b] > o) { pairs[2 * b + 2] = pairs[2 * b]; pairs[2 * b + 3] = pairs[2 * b + 1]; b--; }
        pairs[2 * b + 2] = o;
        pairs[2 * b + 3] = c;
    }
    for (int a = 0; a < npairs; a++) {
        int o = pairs[2 * a], c = pairs[2 * a + 1];
        int found_e = 0, found_opp = 0;
        for (int k = o + 1; k < c; k++) {
            int d = strong_dir(t[k]);
            if (d == e_dir) { found_e = 1; break; }
            if (d >= 0) found_opp = 1;
        }
        int set = -1;
        if (found_e) set = e_dir;
        else if (found_opp) {
            int ctx = sos;
            for (int k = o - 1; k >= 0; k--) { int d = strong_dir(t[k]); if (d >= 0) { ctx = d; break; } }
            set = ctx != e_dir ? ctx : e_dir;
        }
        if (set < 0) continue;
        t[o] = t[c] = (uint8_t)set;
        for (int k = o + 1; k < m && pre[k] == BIDI_NSM; k++) t[k] = (uint8_t)set;
        for (int k = c + 1; k < m && pre[k] == BIDI_NSM; k++) t[k] = (uint8_t)set;
    }
    free(pairs);

    /* N1/N2: neutrals between two equal strong ones take that direction; otherwise, the level's. */
    for (int k = 0; k < m; k++) {
        if (!is_ni(t[k])) continue;
        int e = k;
        while (e < m && is_ni(t[e])) e++;
        int lead = k == 0 ? sos : strong_dir(t[k - 1]);
        int trail = e == m ? eos : strong_dir(t[e]);
        int d = lead == trail && lead >= 0 ? lead : e_dir;
        for (int j = k; j < e; j++) t[j] = (uint8_t)d;
        k = e - 1;
    }

    /* I1/I2 */
    for (int k = 0; k < m; k++) {
        int lv = level;
        if (!(lv & 1)) { if (t[k] == BIDI_R) lv += 1; else if (t[k] == BIDI_AN || t[k] == BIDI_EN) lv += 2; }
        else if (t[k] == BIDI_L || t[k] == BIDI_EN || t[k] == BIDI_AN) lv += 1;
        p->levels[idx[k]] = (uint8_t)lv;
    }
}

int bidi_levels(const uint32_t *cp, int n, int para, uint8_t *levels, uint8_t *removed) {
    if (n <= 0) return para > 0 ? 1 : 0;
    /* a single block: classes ×3, matches, stack, sequence indices, runs */
    size_t ints = (size_t)n * 5;
    uint8_t *bytes = malloc((size_t)n * 5);
    int *mem = malloc(sizeof(int) * ints);
    if (!bytes || !mem) {
        free(bytes); free(mem);
        int lv = para > 0 ? 1 : 0;
        memset(levels, lv, (size_t)n);
        if (removed) memset(removed, 0, (size_t)n);
        return lv;
    }
    uint8_t *orig = bytes, *t = bytes + n, *seq_t = bytes + 2 * n, *seq_pre = bytes + 3 * n, *elev = bytes + 4 * n;
    int *match = mem, *stack = mem + n, *idx = mem + 2 * n, *run_start = mem + 3 * n, *run_of = mem + 4 * n;

    for (int i = 0; i < n; i++) orig[i] = t[i] = (uint8_t)bidi_class(cp[i]);
    match_isolates(orig, n, match, stack);
    if (para < 0) para = first_strong(orig, match, 0, n) == 1 ? 1 : 0;

    /* X1–X8: stack of explicit levels */
    struct { uint8_t level, override, isolate; } st[MAX_DEPTH + 2];
    int sp = 0, ovf_iso = 0, ovf_emb = 0, valid_iso = 0;
    st[sp].level = (uint8_t)para; st[sp].override = 0; st[sp].isolate = 0; sp++;
    for (int i = 0; i < n; i++) {
        int c = orig[i];
        int top = st[sp - 1].level;
        switch (c) {
        case BIDI_RLE: case BIDI_LRE: case BIDI_RLO: case BIDI_LRO: {
            int nl = (c == BIDI_RLE || c == BIDI_RLO) ? (top + 1) | 1 : (top + 2) & ~1;
            levels[i] = (uint8_t)top;
            if (nl <= MAX_DEPTH && !ovf_iso && !ovf_emb) {
                st[sp].level = (uint8_t)nl;
                st[sp].override = c == BIDI_LRO ? 1 : c == BIDI_RLO ? 2 : 0;   /* 1 → L, 2 → R */
                st[sp].isolate = 0;
                sp++;
            } else if (!ovf_iso) ovf_emb++;
            break;
        }
        case BIDI_RLI: case BIDI_LRI: case BIDI_FSI: {
            levels[i] = (uint8_t)top;
            if (st[sp - 1].override) t[i] = st[sp - 1].override == 1 ? BIDI_L : BIDI_R;
            int rtl = c == BIDI_RLI || (c == BIDI_FSI && first_strong(orig, match, i + 1, match[i] >= 0 ? match[i] : n) == 1);
            int nl = rtl ? (top + 1) | 1 : (top + 2) & ~1;
            if (nl <= MAX_DEPTH && !ovf_iso && !ovf_emb) {
                valid_iso++;
                st[sp].level = (uint8_t)nl; st[sp].override = 0; st[sp].isolate = 1;
                sp++;
            } else ovf_iso++;
            break;
        }
        case BIDI_PDI:
            if (ovf_iso > 0) ovf_iso--;
            else if (valid_iso > 0) {
                ovf_emb = 0;
                while (!st[sp - 1].isolate) sp--;
                sp--;
                valid_iso--;
            }
            levels[i] = st[sp - 1].level;
            if (st[sp - 1].override) t[i] = st[sp - 1].override == 1 ? BIDI_L : BIDI_R;
            break;
        case BIDI_PDF:
            if (ovf_iso > 0) {}
            else if (ovf_emb > 0) ovf_emb--;
            else if (!st[sp - 1].isolate && sp >= 2) sp--;
            levels[i] = (uint8_t)top;
            break;
        case BIDI_B:
            levels[i] = (uint8_t)para;
            break;
        case BIDI_BN:
            levels[i] = (uint8_t)top;
            break;
        default:
            levels[i] = (uint8_t)top;
            if (st[sp - 1].override) t[i] = st[sp - 1].override == 1 ? BIDI_L : BIDI_R;
            break;
        }
    }

    /* X9/X10: level runs (without the removed characters) and isolating sequences */
    int nruns = 0, prev = -1;
    for (int i = 0; i < n; i++) {
        run_of[i] = -1;
        if (is_removed(orig[i])) continue;
        if (prev < 0 || levels[i] != levels[prev]) run_start[nruns++] = i;
        run_of[i] = nruns - 1;
        prev = i;
    }
    memcpy(elev, levels, (size_t)n);
    Para p = { cp, orig, t, levels, elev, n, para };
    for (int r = 0; r < nruns; r++) {
        int first = run_start[r];
        /* the ones that start with a PDI closing an isolate continue another sequence */
        if (orig[first] == BIDI_PDI) {
            int matched = 0;
            for (int j = first - 1; j >= 0 && !matched; j--) if (match[j] == first) matched = 1;
            if (matched) continue;
        }
        int m = 0, run = r;
        for (;;) {
            int lastc = -1;
            for (int i = run_start[run]; i < n; i++) {
                if (run_of[i] < 0) continue;
                if (run_of[i] != run) break;
                idx[m++] = i;
                lastc = i;
            }
            if (lastc < 0 || !is_isolate_init(orig[lastc]) || match[lastc] < 0) break;
            int next = run_of[match[lastc]];
            if (next < 0) break;
            run = next;
        }
        if (m) resolve_sequence(&p, idx, m, seq_t, seq_pre);
    }

    /* the removed ones take the level of the previous one (for drawing and shaping) */
    for (int i = 0; i < n; i++) {
        int rm = is_removed(orig[i]);
        if (removed) removed[i] = (uint8_t)rm;
        if (rm) levels[i] = i > 0 ? levels[i - 1] : (uint8_t)para;
    }
    free(bytes);
    free(mem);
    return para;
}

void bidi_line(const uint32_t *cp, uint8_t *levels, int start, int end, int para, int *order) {
    /* L1: separators, and spaces/isolates before them or at the end, at the paragraph level */
    int trailing = 1;
    for (int i = end - 1; i >= start; i--) {
        int c = bidi_class(cp[i]);
        if (c == BIDI_S || c == BIDI_B) { levels[i] = (uint8_t)para; trailing = 1; continue; }
        if (trailing && (c == BIDI_WS || is_isolate_init(c) || c == BIDI_PDI || is_removed(c))) { levels[i] = (uint8_t)para; continue; }
        trailing = 0;
    }
    /* L2: reverse from the highest level down to the lowest odd one */
    int n = end - start, hi = 0, lo_odd = 255;
    for (int k = 0; k < n; k++) {
        order[k] = start + k;
        int lv = levels[start + k];
        if (lv > hi) hi = lv;
        if ((lv & 1) && lv < lo_odd) lo_odd = lv;
    }
    for (int lv = hi; lv >= lo_odd && lv > 0; lv--) {
        for (int k = 0; k < n; k++) {
            if (levels[order[k]] < lv) continue;
            int e = k;
            while (e < n && levels[order[e]] >= lv) e++;
            for (int a = k, b = e - 1; a < b; a++, b--) { int tmp = order[a]; order[a] = order[b]; order[b] = tmp; }
            k = e;
        }
    }
}