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

std/src/unicode/normalize.nv
198 строк7 KB
Evgeniy Golovin
std(naming): collections/hashmap → hash_map — единственный нарушитель snake_case-правила модулей
06 авг 2026, 12:48
06 авг 2026, 12:480b0a260
// Plan 152.4.2 (D253): Unicode normalization — NFC / NFD / NFKC / NFKD (UAX #15).
//
// Opt-in module (`import std.unicode.{normalize_nfc, ...}`); NOT in the prelude,
// so the table cost is paid only by importers (criterion A6). Co-equal peer of
// `norm_data.nv` (generated tables) in the `std.unicode` folder-module — peers
// share declarations, so the `*_DATA` constants are visible here directly.
//
// Algorithm (UAX #15):
//   NFD  = canonical decomposition, then canonical ordering of combining marks.
//   NFC  = NFD, then canonical composition.
//   NFKD = compatibility decomposition, then canonical ordering.
//   NFKC = NFKD, then canonical composition.
// Hangul syllables are decomposed/composed algorithmically (not via tables).
//
// Tables (norm_data.nv) hold FULL decompositions already, so decomposition is a
// single table lookup per codepoint (no recursion needed at runtime).

module std.unicode

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

// ---- Hangul constants (UAX #15) ----
const SBASE = 0xAC00
const LBASE = 0x1100
const VBASE = 0x1161
const TBASE = 0x11A7
const LCOUNT = 19
const VCOUNT = 21
const TCOUNT = 28
const NCOUNT = 588    // VCOUNT * TCOUNT
const SCOUNT = 11172  // LCOUNT * NCOUNT

// ---- lazy-static tables (built once on first normalization call) ----
// hex / parse_cp_list / parse_cp_keyed_table / parse_cp_int_table /
// parse_comp_table / str_to_cps / cps_to_str live in the std.unicode peer
// cp_utils.nv (folder-module peers share declarations).
ro nfd_map HashMap[u32, str] = parse_cp_keyed_table(NFD_DATA)
ro nfkd_map HashMap[u32, str] = parse_cp_keyed_table(NFKD_DATA)
ro ccc_map HashMap[u32, int] = parse_cp_int_table(CCC_DATA)
ro comp_map HashMap[int, u32] = parse_comp_table(COMP_DATA)

fn ccc_of(cp u32) -> int {
    ccc_map.get(cp) ?? 0
}

fn decomp_lookup(cp u32, compat bool) -> Option[str] {
    if compat { nfkd_map.get(cp) } else { nfd_map.get(cp) }
}

fn is_hangul_syllable(cp u32) -> bool {
    ro c = cp as int  // Hangul grid math is index-arithmetic (int; D327 §bit-packing)
    c >= SBASE && c < SBASE + SCOUNT
}

// ---- decomposition ----
fn decompose(cps []u32, compat bool) -> []u32 {
    mut out []u32 = []u32.new(cap: cps.len() * 2)
    for cp in cps {
        if is_hangul_syllable(cp) {
            // Hangul algorithmic decomposition — grid/index arithmetic in `int`
            // (D327 §bit-packing); the resulting codepoints stored as `u32`.
            ro si = (cp as int) - SBASE
            out.push((LBASE + si / NCOUNT) as u32)
            out.push((VBASE + (si % NCOUNT) / TCOUNT) as u32)
            ro t = si % TCOUNT
            if t != 0 { out.push((TBASE + t) as u32) }
        } else {
            match decomp_lookup(cp, compat) {
                Some(seq) => { for d in parse_cp_list(seq) { out.push(d) } }
                None => { out.push(cp) }
            }
        }
    }
    out
}

// ---- canonical ordering (stable insertion sort by combining class) ----
// Starters (ccc == 0) act as barriers: a combining mark is never reordered past
// a starter, and equal-class marks keep their input order (stability).
fn canonical_order(arr []u32) -> []u32 {
    mut a []u32 = []u32.new(cap: arr.len())
    for x in arr { a.push(x) }
    ro n = a.len()
    for i in 1..n {
        ro cc = ccc_of(a[i])
        if cc != 0 {
            mut j = i
            while j > 0 && ccc_of(a[j - 1]) > cc {
                ro tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp
                j -= 1
            }
        }
    }
    a
}

// ---- canonical composition ----
// Primary composite of (a, b), or `None` if none (D327 §fallible — no `-1`
// sentinel). Hangul L+V and LV+T handled algorithmically; everything else via the
// inverted canonical-decomposition map. `a`/`b` stay `int`: the body is grid /
// bit-packing arithmetic (`(a<<21)|b` > 32 bits — D327 §bit-packing).
fn compose_pair(a int, b int) -> Option[u32] {
    if a >= LBASE && a < LBASE + LCOUNT && b >= VBASE && b < VBASE + VCOUNT {
        ro li = a - LBASE
        ro vi = b - VBASE
        Some((SBASE + (li * VCOUNT + vi) * TCOUNT) as u32)
    } else if a >= SBASE && a < SBASE + SCOUNT && ((a - SBASE) % TCOUNT) == 0
        && b > TBASE && b < TBASE + TCOUNT {
        Some((a + (b - TBASE)) as u32)
    } else {
        comp_map.get((a << 21) | b)
    }
}

// Canonical composition (UAX #15): walk the canonically-ordered sequence, folding
// each combining mark into the last starter when a primary composite exists and
// the mark is not blocked (no equal/greater class mark intervenes).
fn compose(cps []u32) -> []u32 {
    ro n = cps.len()
    mut out []u32 = []u32.new(cap: n)
    if n == 0 {
        out
    } else {
        out.push(cps[0])
        mut starter_pos = 0
        mut starter_ch = cps[0]
        mut last_ccc = ccc_of(cps[0])
        // A non-starter first char can never compose (no starter precedes it).
        if last_ccc != 0 { last_ccc = 256 }
        for i in 1..n {
            ro ch = cps[i]
            ro cc = ccc_of(ch)
            // compose_pair → Option[u32] (D327, no `-1` sentinel): Some(comp) AND
            // not blocked → fold into the starter; else emit `ch`.
            mut composed = false
            match compose_pair(starter_ch, ch) {
                Some(comp) => {
                    if last_ccc < cc || last_ccc == 0 {
                        out[starter_pos] = comp
                        starter_ch = comp
                        // last_ccc intentionally not updated: UAX#15 blocking rule —
                        // the composed char inherits the starter's CCC (0).
                        composed = true
                    }
                }
                None => {}
            }
            if !composed {
                if cc == 0 {
                    starter_pos = out.len()
                    starter_ch = ch
                }
                last_ccc = cc
                out.push(ch)
            }
        }
        out
    }
}

// ---- public API (D253: free-function form `normalize_nfc(s) -> str`) ----

/// Canonical decomposition + canonical ordering (NFD).
export fn normalize_nfd(s str) -> str {
    cps_to_str(canonical_order(decompose(str_to_cps(s), false)))
}

/// Compatibility decomposition + canonical ordering (NFKD).
export fn normalize_nfkd(s str) -> str {
    cps_to_str(canonical_order(decompose(str_to_cps(s), true)))
}

/// Canonical decomposition, ordering, then canonical composition (NFC).
export fn normalize_nfc(s str) -> str {
    cps_to_str(compose(canonical_order(decompose(str_to_cps(s), false))))
}

/// Compatibility decomposition, ordering, then canonical composition (NFKC).
export fn normalize_nfkc(s str) -> str {
    cps_to_str(compose(canonical_order(decompose(str_to_cps(s), true))))
}

// ---- str extension methods (Plan 91.18 Ф.5) ----

/// Canonical decomposition + ordering (NFD) as a str method.
export fn str @to_nfd() -> str => normalize_nfd(@)

/// Compatibility decomposition + ordering (NFKD) as a str method.
export fn str @to_nfkd() -> str => normalize_nfkd(@)

/// Canonical decomposition, ordering, then composition (NFC) as a str method.
export fn str @to_nfc() -> str => normalize_nfc(@)

/// Compatibility decomposition, ordering, then composition (NFKC) as a str method.
export fn str @to_nfkc() -> str => normalize_nfkc(@)