std/src/unicode/collate.nv - main - nv-lang/nova

std/src/unicode/collate.nv
443 строки17 KB
Evgeniy Golovin
std(naming): collections/hashmap → hash_map — единственный нарушитель snake_case-правила модулей
06 авг 2026, 12:48
06 авг 2026, 12:480b0a260
// Plan 152.5b (D254): Unicode collation — UCA / DUCET (UTS #10).
//
// Opt-in `std.unicode` peer (NOT prelude — `str` NEVER collates silently; the
// default `str` Ord is byte-lexicographic, D254). Co-equal with `collate_data.nv`
// (generated DUCET tables) in the `std.unicode` folder-module, so the `*_DATA`
// constants are visible here directly. Reuses peer helpers from normalize.nv
// (hex / str_to_cps / cps_to_str / parse_cp_list / normalize_nfd) and the table
// parsers below.
//
// Algorithm (UTS #10, Default Unicode Collation Element Table):
//   1. Normalize the input to NFD (canonical decomposition + ordering).
//   2. Map the normalized codepoints to collation elements: greedy longest-match
//      against the DUCET (contractions first, then single cps); codepoints with
//      no table entry (CJK ideographs, siniform blocks, unassigned) get
//      algorithmic IMPLICIT weights (UTS #10 §10.1).
//   3. Build the multi-level sort key under the **Shifted** variable-weighting
//      variant (§4): variable CEs are demoted to level 4; the key is
//      L1.. 0 L2.. 0 L3.. 0 L4.. concatenated.
//   4. compare(a, b) = lexicographic compare of the two sort keys.
//
// SCOPE (honest): this implements the **DUCET (default, non-tailored) collation**
// with the **Shifted** variable-weighting variant — matching the official
// CollationTest_SHIFTED.txt conformance oracle. Locale tailoring (CLDR) is NOT
// implemented (see `[M-152-collation-tailoring]`); for tailored ordering use a
// future locale Collator. This is the same scope as Rust's `unicode-collation`
// DUCET mode / ICU root collator without tailoring.

module std.unicode

import std.collections.hash_map.{HashMap}
import std.collections.vec.{Vec}

// ── DUCET table parsing (lazy-static, built once on first touch) ──
// parse_cp_keyed_table / hex live in cp_utils.nv peer; parse_flat in ranges.nv peer.
// SINGLE_DATA and CONTRACTION_DATA both use the "cp:value;.." shape -> parse_cp_keyed_table.
// IMPLICIT_DATA uses the nested ';'-of-',' flat shape -> parse_flat.
ro collate_single_map HashMap[u32, str] = parse_cp_keyed_table(SINGLE_DATA)
ro collate_contraction_map HashMap[u32, str] = parse_cp_keyed_table(CONTRACTION_DATA)
ro implicit_flat []u32 = parse_flat(IMPLICIT_DATA)

// ── collation-element parsing ──
// One CE is encoded "[*]P.S.T". We unpack it into 4 ints appended to `acc`:
//   [variable(0/1), primary, secondary, tertiary]
// so the whole CE stream is a flat []int of quadruples (avoids a struct/tuple
// HashMap value — see [M-hashmap-tuple-key-mono]).
// D246-амендмент ([M-ro-launder-via-mut-binding], Ф.2 миграция, 2026-07-23):
// `ce` — `mut` (in-out по D326-ревизии §Р3) — NOT `.clone()`: `str` не несёт
// `@clone()` в этой кодовой базе (её буфер `ptr *u8` уже always-ro-pointee
// по конструкции — нет способа записать в него ВООБЩЕ, так что in-out здесь
// абсолютно безвреден, cascade на caller (`push_ce_list`) — просто `for mut
// ce`, без реальной семантической разницы).
fn push_one_ce(mut acc []u32, mut ce str) -> int {
    mut variable u32 = 0
    mut body = ce
    match ce.strip_prefix("*") {
        Some(rest) => {
            variable = 1
            body = rest
        }
        None => {}
    }
    ro parts = body.split(".").collect()
    if parts.len() == 3 {
        match hex(parts[0]) {
            Some(p) => match hex(parts[1]) {
                Some(s) => match hex(parts[2]) {
                    Some(t) => {
                        acc.push(variable)
                        acc.push(p)
                        acc.push(s)
                        acc.push(t)
                    }
                    None => {}
                }
                None => {}
            }
            None => {}
        }
    }
    0
}

// Parse a "ce|ce|.." CE list into flat quadruples appended to `acc`.
// D246-амендмент ([M-ro-launder-via-mut-binding], Ф.2 миграция, 2026-07-23):
// `for mut ce` — `push_one_ce`'s `ce` param стал `mut` (in-out), см. его doc.
fn push_ce_list(mut acc []u32, ces str) {
    for mut ce in ces.split("|") { push_one_ce(acc, ce) }
}

// Implicit weights (UTS #10 §10.1) for a codepoint with no DUCET entry. Appends
// TWO collation elements (4 ints each) to `acc`:
//   CE1 = [0, AAAA, 0x20, 0x02]   CE2 = [0, BBBB, 0, 0]
// kind 0 (Han/default): AAAA = base + (cp >> 15), BBBB = (cp & 0x7fff) | 0x8000.
// kind 1 (siniform):    AAAA = base,              BBBB = (cp - lo) | 0x8000.
// Codepoints in no implicit range fall back to base 0xFBC0, kind 0.
fn push_implicit(mut acc []u32, cp u32) {
    // The range test compares `cp` against the `u32` table bounds (kept `u32`); the
    // weight arithmetic below is bit-packing / grid math → `int` (D327 §bit-packing).
    ro c = cp as int
    mut base = 0xFBC0
    mut kind = 0
    mut lo = 0
    ro count = implicit_flat.len() / 4
    mut i = 0
    mut found = false
    while i < count && !found {
        ro rlo = implicit_flat[i * 4]
        ro rhi = implicit_flat[i * 4 + 1]
        if cp >= rlo && cp <= rhi {
            base = implicit_flat[i * 4 + 2]
            kind = implicit_flat[i * 4 + 3]
            lo = rlo
            found = true
        }
        i += 1
    }
    mut aaaa = 0
    mut bbbb = 0
    if kind == 1 {
        aaaa = base
        bbbb = (c - lo) | 0x8000
    } else {
        aaaa = base + (c >> 15)
        bbbb = (c & 0x7FFF) | 0x8000
    }
    acc.push(0)
    acc.push(aaaa as u32)
    acc.push(0x20)
    acc.push(0x02)
    acc.push(0)
    acc.push(bbbb as u32)
    acc.push(0)
    acc.push(0)
}

// ── contraction lookup helpers (variants keyed by first cp; "rest=ces#..") ──

fn cp_seq_eq(a []u32, b []u32) -> bool {
    if a.len() != b.len() {
        false
    } else {
        mut ok = true
        mut i = 0
        while i < a.len() {
            if a[i] != b[i] { ok = false }
            i += 1
        }
        ok
    }
}

// `pre` is a strict prefix of `full`?
fn cp_seq_is_prefix(pre []u32, full []u32) -> bool {
    if pre.len() >= full.len() {
        false
    } else {
        mut ok = true
        mut i = 0
        while i < pre.len() {
            if pre[i] != full[i] { ok = false }
            i += 1
        }
        ok
    }
}

// Exact contraction match: does `first` have a variant whose tail == `tail`?
// Returns its CE string. (No early break — iterate all variants, keep last hit.)
fn contraction_lookup(first u32, tail []u32) -> Option[str] {
    mut found Option[str] = None
    match collate_contraction_map.get(first) {
        Some(variants) => {
            for variant in variants.split("#") {
                match variant.split_once("=") {
                    Some((rest, ces)) => {
                        if cp_seq_eq(parse_cp_list(rest), tail) { found = Some(ces) }
                    }
                    None => {}
                }
            }
        }
        None => {}
    }
    found
}

// Is `tail` a strict prefix of some longer variant tail of `first`? (keep extending)
fn contraction_has_longer(first u32, tail []u32) -> bool {
    match collate_contraction_map.get(first) {
        Some(variants) => {
            mut yes = false
            for variant in variants.split("#") {
                match variant.split_once("=") {
                    Some((rest, _ces)) => {
                        if cp_seq_is_prefix(tail, parse_cp_list(rest)) { yes = true }
                    }
                    None => {}
                }
            }
            yes
        }
        None => false
    }
}

fn cp_seq_push(src []u32, x u32) -> []u32 {
    mut out []u32 = []u32.new(cap: src.len() + 1)
    for v in src { out.push(v) }
    out.push(x)
    out
}

// Same as cp_seq_push but for `[]int` index lists. A separate function is
// REQUIRED: passing a `[]int` to `cp_seq_push` (which takes `[]u32`)
// reinterprets 64-bit ints as 32-bit words → garbage indices (the `(hi<<32)|lo`
// out-of-bounds that bit the s21 discontiguous path). Keep the element types exact.
fn idx_seq_push(src []int, x int) -> []int {
    mut out []int = []int.new(cap: src.len() + 1)
    for v in src { out.push(v) }
    out.push(x)
    out
}

// UCA S2.1: longest contraction match at `i` with **discontiguous** extension —
// a contraction continuation may match across an interposed non-starter whose
// combining class is strictly lower (the interposed mark is collated separately).
// `used` marks already-consumed indices (read-only here). Returns the chosen CE
// string (None ⇒ caller emits implicit weights) + the list of consumed indices
// (always includes `i`).
fn s21_match(cps []u32, used []int, i int) -> (Option[str], []int) {
    ro n = cps.len()
    ro first = cps[i]
    mut best_ces = collate_single_map.get(first)   // longest exact so far = `first` alone
    mut best_consumed []int = []int.new(cap: 4)
    best_consumed.push(i)
    match collate_contraction_map.get(first) {
        Some(_) => {
            mut cur_tail []u32 = []u32.new(cap: 4)                     // matched tail cps (after first)
            mut cur_consumed []int = []int.new(cap: 4)                 // their indices (in order)
            mut prev_ccc = 0
            mut j = i + 1
            mut going = true
            while going && j < n {
                if used[j] == 1 {
                    j += 1
                } else {
                    ro cj = cps[j]
                    ro ccj = ccc_of(cj)
                    ro eligible = if ccj == 0 { prev_ccc == 0 } else { ccj > prev_ccc }
                    if eligible {
                        ro trial = cp_seq_push(cur_tail, cj)
                        match contraction_lookup(first, trial) {
                            Some(ces) => {
                                cur_tail = trial
                                cur_consumed = idx_seq_push(cur_consumed, j)
                                best_ces = Some(ces)
                                best_consumed = with_base(i, cur_consumed)
                                prev_ccc = 0
                                j += 1
                            }
                            None => {
                                if contraction_has_longer(first, trial) {
                                    cur_tail = trial
                                    cur_consumed = idx_seq_push(cur_consumed, j)
                                    prev_ccc = 0
                                    j += 1
                                } else if ccj == 0 {
                                    going = false
                                } else {
                                    prev_ccc = ccj
                                    j += 1
                                }
                            }
                        }
                    } else if ccj == 0 {
                        going = false
                    } else {
                        prev_ccc = ccj
                        j += 1
                    }
                }
            }
        }
        None => {}
    }
    (best_ces, best_consumed)
}

// [i] ++ consumed (the discontiguously-matched tail indices).
fn with_base(i int, consumed []int) -> []int {
    mut out []int = []int.new(cap: consumed.len() + 1)
    out.push(i)
    for x in consumed { out.push(x) }
    out
}

// Map the NFD-normalized codepoints of `s` to the flat collation-element stream
// (quadruples [variable, primary, secondary, tertiary]). Applies UCA S2.1.
fn collation_elements(s str) -> []u32 {
    ro cps = str_to_cps(normalize_nfd(s))
    ro n = cps.len()
    mut used []int = []int.new(cap: n)
    for z in 0..n {
        used.push(0)
    }
    mut acc []u32 = []u32.new(cap: n * 8)
    mut i = 0
    while i < n {
        if used[i] == 1 {
            i += 1
        } else {
            ro (ces, consumed) = s21_match(cps, used, i)
            for idx in consumed { used[idx] = 1 }
            match ces {
                Some(cs) => { push_ce_list(acc, cs) }
                None => { push_implicit(acc, cps[i]) }
            }
            i += 1
        }
    }
    acc
}

// ── sort-key construction (Shifted variable weighting, UTS #10 §4) ──
//
// L4 (quaternary) rule for Shifted:
//   - variable CE:                        L1=L2=L3=0, L4 = original L1
//   - ignorable (L1==0) after a variable: L1=L2=L3=L4=0  (fully removed)
//   - completely ignorable (all zero) not after variable: removed (no L4)
//   - ignorable (L1==0, but L2/L3 != 0) not after variable: L4 = 0xFFFF
//   - normal non-variable (L1 != 0):      L4 = 0xFFFF
// A non-ignorable (L1 != 0) CE clears the "after variable" state.
//
// Sort key = [ all L1>0 primaries ] 0 [ all L2>0 secondaries ] 0
//            [ all L3>0 tertiaries ] 0 [ all L4 quaternaries ].
// (Zero weights are skipped at each level; the 0 separators keep levels apart so
// a shorter run at level N always sorts before a longer one — standard UCA.)
const L4_MAX u32 = 0xFFFF

/// Build the UCA sort key for `s` as a `[]u32` of 16-bit weights (Shifted variant).
/// `compare`/`eq` byte-compare these keys. Caching a precomputed key for repeated
/// comparisons (e.g. sorting) avoids re-normalizing per comparison.
export fn collate_sort_key(s str) -> []u32 {
    ro ce = collation_elements(s)
    ro m = ce.len() / 4
    mut prim []u32 = []u32.new(cap: m + 1)
    mut sec []u32 = []u32.new(cap: m + 1)
    mut tert []u32 = []u32.new(cap: m + 1)
    mut quat []u32 = []u32.new(cap: m + 1)
    mut after_variable = false
    for j in 0..m {
        ro variable = ce[j * 4]
        ro p = ce[j * 4 + 1]
        ro s2 = ce[j * 4 + 2]
        ro t = ce[j * 4 + 3]
        if variable == 1 {
            // Demote: contributes only L4 = original primary.
            if p != 0 { quat.push(p) }
            after_variable = true
        } else if p == 0 {
            // Ignorable at the primary level.
            if after_variable {
                // Removed entirely (no weight at any level).
            } else if s2 != 0 || t != 0 {
                // Keep secondary/tertiary; L4 = FFFF.
                if s2 != 0 { sec.push(s2) }
                if t != 0 { tert.push(t) }
                quat.push(L4_MAX)
            }
            // completely-ignorable (all zero) not after variable: drop silently.
        } else {
            // Normal non-variable, non-ignorable element.
            prim.push(p)
            if s2 != 0 { sec.push(s2) }
            if t != 0 { tert.push(t) }
            quat.push(L4_MAX)
            after_variable = false
        }
    }
    mut key []u32 = []u32.new(cap: prim.len() + sec.len() + tert.len() + quat.len() + 4)
    for w in prim { key.push(w) }
    key.push(0)
    for w in sec { key.push(w) }
    key.push(0)
    for w in tert { key.push(w) }
    key.push(0)
    for w in quat { key.push(w) }
    key
}

// Lexicographic compare of two weight keys: -1 / 0 / +1 (D183 int convention).
fn compare_keys(a []u32, b []u32) -> int {
    ro na = a.len()
    ro nb = b.len()
    ro n = na.min(nb)
    mut i = 0
    mut result = 0
    while i < n && result == 0 {
        if a[i] < b[i] {
            result = -1
        } else if a[i] > b[i] {
            result = 1
        }
        i += 1
    }
    if result == 0 {
        if na < nb { result = -1 } else if na > nb { result = 1 }
    }
    result
}

/// Collate two strings under DUCET (Shifted variant). Returns -1 / 0 / +1,
/// matching `str @compare`. Analogous to JS `localeCompare`
/// (root locale) / Java `Collator` (no tailoring). NOTE: this is opt-in — `str`'s
/// default `<`/`compare` stays byte-lexicographic.
export fn collate_compare(a str, b str) -> int {
    compare_keys(collate_sort_key(a), collate_sort_key(b))
}

/// True iff `a` and `b` collate equal under DUCET (Shifted). Equal collation does
/// NOT imply byte equality (case/accent/punctuation may be folded into levels).
export fn collate_eq(a str, b str) -> bool {
    collate_compare(a, b) == 0
}

// ── Collator (DUCET namespace) ──
//
// A bodyless namespace that exposes the DUCET collator as static methods, mirroring
// `java.text.Collator` / `Intl.Collator`. DUCET is stateless (no tailoring), so the
// collator carries no fields — `order`/`key`/`same` delegate to the free functions.
// A future tailored Collator ([M-152-collation-tailoring]) carrying locale data would
// become a value-record with a `Collator.with_locale(...)` constructor; the static
// DUCET entry points stay as-is. Mirrors `type RawMem` namespace convention.
export type Collator

/// DUCET (non-tailored) collation. Method names are `order`/`key`/`same`
/// (not the `@compare`/`@equal` protocol names) — collation is opt-in and must not
/// be mistaken for `str`'s default byte Ord.
export fn Collator.order(a str, b str) -> int => collate_compare(a, b)

export fn Collator.key(s str) -> []u32 => collate_sort_key(s)

export fn Collator.same(a str, b str) -> bool => collate_eq(a, b)