intl 0.5.1

//! Unicode Collation Algorithm (UTS #10) — DUCET root collation.
//!
//! Compares strings in the Unicode default collation order. Requires the
//! `alloc` feature (collation buffers the whole string while generating
//! collation elements and sort keys).
//!
//! ```
//! # #[cfg(feature = "alloc")] {
//! use intl::unicode::collate::{compare, AlternateHandling};
//! use core::cmp::Ordering;
//!
//! // Accented letters sort just after their base letter, not by code point.
//! assert_eq!(compare("a", "z"), Ordering::Less);
//! assert_eq!(compare("café", "cafz"), Ordering::Less);
//! # }
//! ```

use super::generated::collation as tables;
use super::normalize::{canonical_combining_class as ccc, nfd};
use alloc::string::{String, ToString};
use alloc::vec::Vec;
use core::cmp::Ordering;

// ---- Collation element (packed u64) accessors ----

#[inline]
fn primary(ce: u64) -> u16 {
    ((ce >> 32) & 0xFFFF) as u16
}
#[inline]
fn secondary(ce: u64) -> u16 {
    ((ce >> 16) & 0xFFFF) as u16
}
#[inline]
fn tertiary(ce: u64) -> u16 {
    (ce & 0xFFFF) as u16
}
#[inline]
fn is_variable(ce: u64) -> bool {
    (ce >> 48) & 1 != 0
}
#[inline]
fn pack(p: u32, s: u32, t: u32) -> u64 {
    (p as u64) << 32 | (s as u64) << 16 | t as u64
}

// Tailoring sub-weight: a second primary component for tailored letters, stored
// in the otherwise-unused high bits of the CE (bits 49–63, above the variable
// bit). It lets the tailored sort key emit a `(base, sub)` pair per element, so
// arbitrarily many letters can be inserted immediately after a reset anchor
// (`&z < a < b < c < …`) without exhausting the DUCET inter-letter gap. Plain
// DUCET CEs have `sub == 0`.
#[inline]
fn sub_weight(ce: u64) -> u16 {
    ((ce >> 49) & 0x7FFF) as u16
}
#[inline]
fn pack_tailored(base: u32, sub: u32, s: u32, t: u32) -> u64 {
    ((sub as u64) << 49) | (base as u64) << 32 | (s as u64) << 16 | t as u64
}

// Tailoring sub-weight regions (see `build_tailored_sort_key`). A plain DUCET
// letter emits the *midpoint* sub-weight `SUB_MID` in the sort key, so a tailored
// letter can be placed either just **after** its reset anchor (sub `SUB_MID + k`,
// the `&z < å` case) or just **before** it (sub `SUB_BEFORE + k < SUB_MID`, the
// CLDR `&[before 1] X < å` reset-before). `k` is the running primary offset, so
// any number of letters fit on either side of one anchor.
const SUB_MID: u16 = 0x4000;
const SUB_BEFORE: u16 = 0x2000;

// ---- Chinese (zh) pinyin Han-weight table (feature `collation-zh`). ----
//
// The distilled CLDR pinyin order: `Han codepoint -> u16 pinyin rank`. Blob
// layout (little-endian): `[u32 count]`, then `count` sorted `u32` codepoints,
// then `count` `u16` ranks (parallel). Generated by codegen (`emit_collation_zh`)
// from the vendored `zh.xml`. See `Tailoring::for_locale`.
#[cfg(feature = "collation-zh")]
const ZH_PINYIN: &[u8] = include_bytes!("collation_zh.bin");

// Alternate zh Han-weight tables, selected via `zh-u-co-stroke` / `zh-u-co-zhuyin`
// (feature `collation-zh`). Same blob format as [`ZH_PINYIN`]: URO + Compatibility
// Han → dense `stroke` / `zhuyin` rank; Extensions share the radical-stroke
// fallback ([`ZH_PINYIN_RS`]). See [`Tailoring::for_locale`].
#[cfg(feature = "collation-zh")]
const ZH_STROKE: &[u8] = include_bytes!("collation_zh_stroke.bin");
#[cfg(feature = "collation-zh")]
const ZH_ZHUYIN: &[u8] = include_bytes!("collation_zh_zhuyin.bin");

// Chinese (zh) radical-stroke fallback table (feature `collation-zh`).
//
// For Han ideographs with NO pinyin rank (the CJK Extensions, plus rare
// reading-less URO chars), `Intl.Collator('zh')` (ICU/V8) orders by Unihan
// radical-stroke — radical number, then residual strokes, then code point —
// placing them after all pinyin chars but before Latin. This is the distilled
// `kRSUnicode` order from `Unihan_kRSUnicode.txt`, now covering the whole URO too
// (so `zh-u-co-unihan` can order every Han by radical-stroke). Blob layout
// (little-endian): `[u32 count]`, then `count` sorted `u32` codepoints, then
// `count` `u16` packed keys, each `radical << 8 | (residual + 16) << 1 |
// is_simplified`. Generated by codegen (`emit_collation_zh_rs`). See [`zh_rs_key`]
// and [`Tailoring::sort_key`].
#[cfg(feature = "collation-zh")]
const ZH_PINYIN_RS: &[u8] = include_bytes!("collation_zh_rs.bin");

// The second ordering primary of a radical-stroke Han (its first is the pinyin
// rank's slot). It sits above every pinyin rank (max ≈ 20924) and below the DUCET
// implicit Han primary (≥ 0xFB40), so the three Han groups sort in the ICU/V8
// order: pinyin < radical-stroke < (reading-less, DUCET) < Latin.
#[cfg(feature = "collation-zh")]
const ZH_RS_MARKER: u32 = 0x8000;

// The fixed primary *base* for a Han ideograph under zh pinyin collation. It sits
// in the DUCET primary gap between the digits (`'9'` = 0x21EF) and the Latin
// letters (`'a'` = 0x23EC), so `[reorder Hani]` is reproduced: digits < Han <
// Latin < other scripts. The pinyin rank rides the tailoring sub-weight, so all
// ~44k Han are ordered within this one base with no gap exhaustion.
#[cfg(feature = "collation-zh")]
const ZH_HAN_BASE: u32 = 0x21F0;

/// The primary rank of Han ideograph `cp` in a ranked zh Han-weight `table`
/// (pinyin / stroke / zhuyin), or `None` if `cp` is not listed (then the
/// radical-stroke order is the fallback). Binary-searches the table's codepoint
/// array (layout per [`ZH_PINYIN`]); no alloc.
#[cfg(feature = "collation-zh")]
fn zh_ranked(table: &[u8], cp: u32) -> Option<u16> {
    let count = u32::from_le_bytes([table[0], table[1], table[2], table[3]]) as usize;
    let cps = 4; // codepoint array starts here
    let ranks = cps + count * 4; // rank array starts after the codepoints
    let (mut lo, mut hi) = (0usize, count);
    while lo < hi {
        let mid = (lo + hi) / 2;
        let o = cps + mid * 4;
        let v = u32::from_le_bytes([table[o], table[o + 1], table[o + 2], table[o + 3]]);
        match v.cmp(&cp) {
            Ordering::Less => lo = mid + 1,
            Ordering::Greater => hi = mid,
            Ordering::Equal => {
                let r = ranks + mid * 2;
                return Some(u16::from_le_bytes([table[r], table[r + 1]]));
            }
        }
    }
    None
}

/// The packed radical-stroke key of Han ideograph `cp` (see [`ZH_PINYIN_RS`]), or
/// `None` if `cp` is absent (then the DUCET implicit order is the final fallback).
/// Binary-searches the codepoint array; no alloc.
#[cfg(feature = "collation-zh")]
fn zh_rs_key(cp: u32) -> Option<u16> {
    let count = u32::from_le_bytes([
        ZH_PINYIN_RS[0],
        ZH_PINYIN_RS[1],
        ZH_PINYIN_RS[2],
        ZH_PINYIN_RS[3],
    ]) as usize;
    let cps = 4; // codepoint array starts here
    let keys = cps + count * 4; // packed-key array starts after the codepoints
    let (mut lo, mut hi) = (0usize, count);
    while lo < hi {
        let mid = (lo + hi) / 2;
        let o = cps + mid * 4;
        let v = u32::from_le_bytes([
            ZH_PINYIN_RS[o],
            ZH_PINYIN_RS[o + 1],
            ZH_PINYIN_RS[o + 2],
            ZH_PINYIN_RS[o + 3],
        ]);
        match v.cmp(&cp) {
            Ordering::Less => lo = mid + 1,
            Ordering::Greater => hi = mid,
            Ordering::Equal => {
                let r = keys + mid * 2;
                return Some(u16::from_le_bytes([ZH_PINYIN_RS[r], ZH_PINYIN_RS[r + 1]]));
            }
        }
    }
    None
}

/// How variable collation elements (spaces, punctuation, symbols) are handled.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AlternateHandling {
    /// Variable elements keep their primary weight (punctuation is significant).
    NonIgnorable,
    /// Variable elements are moved to a quaternary level (punctuation is ignored
    /// at the primary level). This is the CLDR/ICU default.
    Shifted,
}

// `@implicitweights` ranges from allkeys.txt: (first, last, base, origin).
// `origin` is the start of the *first* range declaring `base`, so ranges that
// share a base (e.g. Tangut + Tangut Supplement) get a continuous BBBB offset.
const IMPLICIT_RANGES: &[(u32, u32, u32, u32)] = &[
    (0x17000, 0x187FF, 0xFB00, 0x17000),
    (0x18800, 0x18AFF, 0xFB01, 0x18800),
    (0x18D00, 0x18D7F, 0xFB00, 0x17000),
    (0x18D80, 0x18DFF, 0xFB01, 0x18800),
    (0x1B170, 0x1B2FF, 0xFB02, 0x1B170),
    (0x18B00, 0x18CFF, 0xFB03, 0x18B00),
];

/// Append the two derived (implicit) collation elements for `cp`.
fn push_implicit(cp: u32, out: &mut Vec<u64>) {
    let (aaaa, bbbb) = implicit_primaries(cp);
    out.push(pack(aaaa, 0x0020, 0x0002));
    out.push(pack(bbbb, 0x0000, 0x0000));
}

fn implicit_primaries(cp: u32) -> (u32, u32) {
    for &(first, last, base, origin) in IMPLICIT_RANGES {
        if cp >= first && cp <= last {
            return (base, (cp - origin) | 0x8000);
        }
    }
    let base = if tables::unified_ideograph(cp) {
        if (0x4E00..=0x9FFF).contains(&cp) || (0xF900..=0xFAFF).contains(&cp) {
            0xFB40
        } else {
            0xFB80
        }
    } else {
        0xFBC0
    };
    (base + (cp >> 15), (cp & 0x7FFF) | 0x8000)
}

/// Look up the collation elements for the contraction `first` + `suffix`.
fn lookup_contraction(first: u32, suffix: &[char]) -> Option<&'static [u64]> {
    for (suf, ces) in tables::contractions(first)? {
        if *suf == suffix {
            return Some(ces);
        }
    }
    None
}

/// Produce the collation element array for an NFD codepoint buffer (UCA S2.1).
fn collation_elements(cv: Vec<char>) -> Vec<u64> {
    let mut cea = Vec::new();
    each_collation_element(&cv, |ces, opt, _start| {
        match ces {
            Some(ces) => cea.extend_from_slice(ces),
            None => push_implicit(opt, &mut cea),
        }
        Walk::Continue
    });
    cea
}

/// Like [`collation_elements`], but also returns, for each emitted element, the
/// index into `cv` of the starter that produced it. [`find`] uses this to map a
/// primary in the stream back to the source character offset.
fn collation_elements_tagged(cv: Vec<char>) -> (Vec<u64>, Vec<usize>) {
    let mut cea = Vec::new();
    let mut src = Vec::new();
    each_collation_element(&cv, |ces, opt, start| {
        match ces {
            Some(ces) => {
                for &ce in ces {
                    cea.push(ce);
                    src.push(start);
                }
            }
            None => {
                let before = cea.len();
                push_implicit(opt, &mut cea);
                for _ in before..cea.len() {
                    src.push(start);
                }
            }
        }
        Walk::Continue
    });
    (cea, src)
}

/// Core of [`collation_elements`]: walk the NFD buffer `cv` (UCA S2.1) and, for
/// each collation step, invoke `emit(Some(ces), 0, start)` with the matched
/// element slice, or `emit(None, s0, start)` when no mapping exists (caller
/// derives the implicit weights for code point `s0`). `start` is the index in
/// `cv` of the starter that began the step.
///
/// The closure returns a [`Walk`] verdict: [`Walk::Continue`] to keep going or
/// [`Walk::Stop`] to end the walk immediately after this step (used by
/// [`window_decision`] to bound the scan once enough primaries are seen — a
/// trailing run of zero-primary code points is then never visited).
///
/// Discontiguous matching (S2.1.1–S2.1.3) consumes unblocked non-starters that
/// lie *after* the contiguous match. The previous implementation removed each
/// consumed char from `cv` with `Vec::remove` — an O(n) shift inside the loop,
/// quadratic on long combining-mark runs. Here consumed positions are marked in
/// a `consumed` bitmask instead (no shifting), and the discontiguous lookahead
/// is capped at the longest registered contraction suffix for the starter, so a
/// run of marks that forms no contraction is not rescanned repeatedly.
fn each_collation_element<F: FnMut(Option<&'static [u64]>, u32, usize) -> Walk>(
    cv: &[char],
    mut emit: F,
) {
    let mut consumed = alloc::vec![false; cv.len()];
    let mut suffix: Vec<char> = Vec::new(); // reused buffer (no per-step clone)
    let mut i = 0;
    while i < cv.len() {
        if consumed[i] {
            i += 1;
            continue;
        }
        let s0 = cv[i] as u32;
        let mut end = i + 1;
        let mut matched: Option<&'static [u64]> = tables::ce_singles(s0);
        suffix.clear();

        // The longest registered contraction suffix for `s0` bounds how far the
        // discontiguous scan can usefully look ahead.
        let mut max_suf = 0usize;

        // Longest contiguous contraction (entries are sorted longest-first).
        if let Some(entries) = tables::contractions(s0) {
            for (suf, ces) in entries {
                if suf.len() > max_suf {
                    max_suf = suf.len();
                }
                let stop = i + 1 + suf.len();
                if stop <= cv.len() && cv[i + 1..stop] == **suf {
                    matched = Some(ces);
                    suffix.clear();
                    suffix.extend_from_slice(suf);
                    end = stop;
                    break;
                }
            }
        }

        // Discontiguous extension: pull in unblocked non-starters (S2.1.1–S2.1.3).
        // Each successful pass appends one consumable non-starter to `suffix`; we
        // cap the suffix length by `max_suf` (the longest registered contraction)
        // so a long mark run that can't form a longer contraction stops at once
        // instead of being rescanned.
        if max_suf > suffix.len() {
            loop {
                let mut last_ccc = 0u8;
                let mut j = end;
                let mut hit: Option<usize> = None;
                while j < cv.len() {
                    if consumed[j] {
                        j += 1;
                        continue;
                    }
                    let cc = ccc(cv[j]);
                    if cc == 0 {
                        break; // starter: stop
                    }
                    if last_ccc < cc {
                        suffix.push(cv[j]);
                        if let Some(ces) = lookup_contraction(s0, &suffix) {
                            matched = Some(ces);
                            hit = Some(j); // keep the pushed char in `suffix`
                            break;
                        }
                        suffix.pop();
                        last_ccc = cc;
                    } else {
                        break; // blocked non-starter: stop
                    }
                    j += 1;
                }
                match hit {
                    Some(j) => {
                        consumed[j] = true;
                        if suffix.len() >= max_suf {
                            break; // no longer contraction possible
                        }
                    }
                    None => break,
                }
            }
        }

        let verdict = match matched {
            Some(ces) => emit(Some(ces), 0, i),
            None => emit(None, s0, i),
        };
        if verdict == Walk::Stop {
            return;
        }
        i = end;
    }
}

/// Whether [`each_collation_element`] should keep walking after a step.
#[derive(PartialEq, Eq, Clone, Copy)]
enum Walk {
    Continue,
    Stop,
}

/// Emit synthetic collation elements for an ASCII-digit run so that numeric
/// values sort by magnitude (`"file2" < "file10"`). Encoding: a fixed marker
/// primary (placing numbers where digits sort), then the significant-digit count
/// (so shorter numbers sort first), then one primary per significant digit.
fn emit_number(digits: &[char], cea: &mut Vec<u64>) {
    // The marker = the DUCET primary of '0', so numbers keep the digit position.
    let marker = primary(collation_elements(alloc::vec!['0'])[0]) as u32;
    // Significant digits (drop leading zeros, but keep a single zero for "0").
    let first_sig = digits
        .iter()
        .position(|&c| c != '0')
        .unwrap_or(digits.len() - 1);
    let sig = &digits[first_sig..];
    cea.push(pack(marker, 0, 0));
    cea.push(pack(sig.len() as u32 + 1, 0, 0));
    for &d in sig {
        cea.push(pack((d as u32 - '0' as u32) + 1, 0, 0));
    }
}

/// Collation element array with numeric ordering: ASCII-digit runs become a
/// single magnitude-ordered element, the rest uses the normal UCA algorithm.
fn collation_elements_numeric(cv: Vec<char>) -> Vec<u64> {
    let mut cea = Vec::new();
    let mut i = 0;
    while i < cv.len() {
        if cv[i].is_ascii_digit() {
            let start = i;
            while i < cv.len() && cv[i].is_ascii_digit() {
                i += 1;
            }
            emit_number(&cv[start..i], &mut cea);
        } else {
            let start = i;
            while i < cv.len() && !cv[i].is_ascii_digit() {
                i += 1;
            }
            cea.extend(collation_elements(cv[start..i].to_vec()));
        }
    }
    cea
}

/// The non-ignorable primary weights of `s` (root DUCET) — the sequence used
/// for primary-strength (case- and accent-insensitive) matching.
fn primaries(s: &str) -> Vec<u16> {
    collation_elements(nfd(s.chars()).collect())
        .into_iter()
        .map(primary)
        .filter(|&p| p != 0)
        .collect()
}

/// Find the first substring of `text` that matches `pattern` at **primary
/// strength** — i.e. case- and accent-insensitively (`"CAFÉ"` matches `"cafe"`)
/// — and return its byte range, or `None`. Uses root (DUCET) collation. An empty
/// pattern matches at `0..0`. This is the collation analog of `str::find`.
///
/// ```
/// # #[cfg(feature = "alloc")] {
/// use intl::unicode::collate::find;
/// assert_eq!(find("Hello, CAFÉ!", "cafe"), Some(7..12));
/// assert_eq!(find("a naïve approach", "naive"), Some(2..8));
/// assert_eq!(find("abc", "xyz"), None);
/// # }
/// ```
#[must_use]
pub fn find(text: &str, pattern: &str) -> Option<core::ops::Range<usize>> {
    let pat = primaries(pattern);
    if pat.is_empty() {
        return Some(0..0);
    }
    let need = pat.len();

    // --- Build the full-text primary stream once, with source byte spans. ---
    //
    // NFD-expand the whole text. `start_of[k]` / `end_of[k]` are the byte offsets
    // in `text` of the start and end of the ORIGINAL char that produced NFD char
    // `k` (NFD never crosses an original-char boundary; an original char may
    // expand to several NFD chars, all sharing its byte span).
    let mut nfd_buf: Vec<char> = Vec::new();
    let mut start_of: Vec<usize> = Vec::new();
    let mut end_of: Vec<usize> = Vec::new();
    for (b, c) in text.char_indices() {
        for d in nfd(core::iter::once(c)) {
            nfd_buf.push(d);
            start_of.push(b);
            end_of.push(b + c.len_utf8());
        }
    }

    let (cea, src) = collation_elements_tagged(nfd_buf);
    // For each non-zero primary, the original byte span of the source char.
    // `prim_start` is non-decreasing. `group_starts` holds the byte offset of
    // every collation-element group's starter (distinct `src` values), i.e. the
    // starts at which the isolated and full-text views agree.
    let mut prim: Vec<u16> = Vec::new();
    let mut prim_start: Vec<usize> = Vec::new();
    let mut prim_end: Vec<usize> = Vec::new();
    let mut group_starts: alloc::collections::BTreeSet<usize> = alloc::collections::BTreeSet::new();
    for (idx, &ce) in cea.iter().enumerate() {
        group_starts.insert(start_of[src[idx]]);
        let p = primary(ce);
        if p != 0 {
            prim.push(p);
            prim_start.push(start_of[src[idx]]);
            prim_end.push(end_of[src[idx]]);
        }
    }

    // --- Scan every char-boundary start in order (leftmost wins). ---
    //
    // The original tested every char-boundary start `a`: it took the smallest
    // window `text[a..b]` whose isolated primaries reach `need`, then returned it
    // iff those primaries equal `pat`. Scanning starts ascending yields the
    // leftmost match, and a leading-ignorable (zero-primary) start is preferred
    // over the later non-ignorable one — both reproduced below.
    //
    // For a start `a` that begins a collation-element group, the isolated view of
    // `text[a..]` equals the full-text view from that group on, so the decision
    // window is just the next `need` primaries in the precomputed stream — found
    // in O(need) via the cursor `k`, with no re-collation. This fast path covers
    // essentially every start (including long combining-mark runs, whose marks
    // are their own zero-primary groups), and is what removes the quadratic cost.
    //
    // A start that falls *inside* a group (a char folded into a contiguous
    // contraction such as `l·`, or a discontiguously-consumed mark) can, in
    // isolation, regain a leading primary the full-text stream doesn't show. Such
    // starts are rare and confined to contraction-length windows; for them we fall
    // back to the exact original decision (`window_decision`), bounded to the few
    // chars needed to reach `need` primaries.
    let mut k = 0usize; // cursor into the primary stream; advances with `a`
    for (a, _) in text.char_indices() {
        while k < prim_start.len() && prim_start[k] < a {
            k += 1;
        }
        if group_starts.contains(&a) {
            // Aligned: isolated == full-text view from here.
            if k + need <= prim.len() && prim[k..k + need] == pat[..] {
                let b = prim_end[k + need - 1];
                if primaries(&text[a..b]) == pat {
                    return Some(a..b);
                }
            }
        } else if let Some((win, b)) = window_decision(&text[a..], need) {
            // Unaligned (mid-contraction) start: exact isolated decision.
            if win == pat {
                return Some(a..a + b);
            }
        }
    }
    None
}

/// The exact decision window the original [`find`] inner loop produces for an
/// unaligned start: the isolated primaries of the shortest prefix of `s` that
/// reaches `need` primaries, and that prefix's byte length. `None` if `s` has
/// fewer than `need` primaries in total.
///
/// Reference semantics (preserved byte-for-byte):
/// ```ignore
/// for b in char_boundaries(s).skip(1).chain([s.len()]) {
///     let pr = primaries(&s[..b]);
///     if pr.len() >= need { return Some((pr, b)); }
/// }
/// None
/// ```
/// That loop is O(W²) when the text after the start is a long run of zero-primary
/// code points (combining marks / ignorables): `need` is never reached, so it
/// re-collates an O(b) prefix at every one of the W boundaries to the end of the
/// string — the algorithmic-complexity DoS.
///
/// The fix bounds the scan to the prefix that actually decides the result. A
/// trailing run of zero-primary code points can never add a primary, so it can
/// never change which boundary first reaches `need`; we therefore stream-collate
/// `s` once, stopping as soon as `need` non-zero primaries are produced, to find
/// an upper bound `cut` on the answer boundary (the byte where the collation
/// group *after* the `need`-th-primary group starts, or `s.len()`). The reference
/// loop is then replayed verbatim but only over `s[..=cut]` — identical results,
/// but the zero-primary tail past `cut` is never collated. `cut` is bounded by
/// the position of the `need`-th primary-bearing character, independent of the
/// tail length, so the whole call is linear in that bounded prefix.
///
/// To keep each call's *setup* (NFD expansion + the per-walk `consumed` bitmask
/// inside [`each_collation_element`]) bounded by the deciding prefix rather than
/// by `s.len()`, the cut search ([`find_cut`]) runs over a growing **prefix** of
/// `s`, doubling its length until the prefix produces `need` primaries or `s` is
/// exhausted. Without this, [`find`] is again quadratic: it calls
/// `window_decision` at every unaligned (mid-contraction) start, and each call
/// expanded/allocated over the whole O(n) remaining suffix before the early
/// `Walk::Stop` could fire — so `m` such starts over O(n) suffixes cost O(n·m).
fn window_decision(s: &str, need: usize) -> Option<(Vec<u16>, usize)> {
    debug_assert!(need > 0);

    let cut = find_cut(s, need)?; // fewer than `need` primaries in all of `s`

    // Replay the reference loop verbatim, bounded to `s[..=cut]`. The first char
    // boundary `b <= cut` whose truncated primaries reach `need` is the answer; we
    // know one exists by `cut` because the full collation reaches `need` there.
    for (b, _) in s[..cut]
        .char_indices()
        .skip(1)
        .chain(core::iter::once((cut, '\0')))
    {
        let pr = primaries(&s[..b]);
        if pr.len() >= need {
            return Some((pr, b));
        }
    }
    None
}

/// Upper bound on the answer boundary for [`window_decision`]: the byte offset of
/// the collation group that *follows* the one producing the `need`-th non-zero
/// primary of `s` (or `s.len()` if that group is the last). `None` if all of `s`
/// has fewer than `need` primaries.
///
/// The search is bounded to a growing prefix `s[..end]`, doubled until it reaches
/// `need` primaries or covers all of `s`. NFD expansion and the per-walk bitmask
/// in [`each_collation_element`] only ever touch this bounded prefix, so a long
/// zero-primary (combining-mark / ignorable) tail past the deciding prefix is
/// never expanded — the per-start cost that keeps [`find`]/[`contains`] linear.
/// The doubling sums geometrically, so total work stays O(deciding prefix).
fn find_cut(s: &str, need: usize) -> Option<usize> {
    // Start with a prefix generous enough to clear most short patterns in one
    // pass, then double. `cap` is a *byte* length, snapped up to a char boundary.
    let mut cap = need.saturating_mul(8).max(16);
    loop {
        let mut end = cap.min(s.len());
        while end < s.len() && !s.is_char_boundary(end) {
            end += 1;
        }
        let prefix = &s[..end];

        // NFD-expand only this prefix, mapping each NFD char back to the byte
        // offset in `s` of the original char that produced it (NFD never crosses
        // an original-char boundary).
        let mut nfd_buf: Vec<char> = Vec::new();
        let mut byte_of: Vec<usize> = Vec::new();
        for (b, c) in prefix.char_indices() {
            for d in nfd(core::iter::once(c)) {
                nfd_buf.push(d);
                byte_of.push(b);
            }
        }

        // Stream the collation over the prefix, counting non-zero primaries. Stop
        // on the collation group that *follows* the one producing the `need`-th
        // primary, recording its starter byte offset as the cut.
        let mut produced = 0usize;
        let mut reached = false; // set once `need` primaries are produced
        let mut cut: Option<usize> = None;
        each_collation_element(&nfd_buf, |ces, opt, start| {
            if reached {
                // The group after the one that reached `need`: its start is the
                // smallest possible boundary past the deciding prefix.
                cut = Some(byte_of[start]);
                return Walk::Stop;
            }
            let nonzero = match ces {
                Some(ces) => ces.iter().any(|&ce| primary(ce) != 0),
                // A derived (implicit) code point always carries a non-zero primary.
                None => implicit_primaries(opt).0 != 0,
            };
            if nonzero {
                produced += 1;
                if produced >= need {
                    reached = true;
                }
            }
            Walk::Continue
        });

        if reached {
            // A later group started within the prefix → its start is the cut.
            if let Some(cut) = cut {
                return Some(cut);
            }
            // The deciding group was the prefix's last. If the prefix is all of
            // `s`, the cut is the whole string. Otherwise the following group lies
            // just past `end`; grow so it (and any discontiguous tail it absorbs)
            // is actually walked rather than cut off by truncation — truncation
            // must not invent or hide the following-group boundary.
            if end == s.len() {
                return Some(s.len());
            }
        } else if end == s.len() {
            return None; // fewer than `need` primaries in all of `s`
        }

        cap = cap.saturating_mul(2);
    }
}

/// `true` if `text` contains `pattern` at primary strength (see [`find`]).
#[must_use]
pub fn contains(text: &str, pattern: &str) -> bool {
    find(text, pattern).is_some()
}

/// The first primary collation weight of `s` under `tail`, as a `(base, sub)`
/// pair packed into a `u32` (the pair-encoded primary), or `0` if `s` starts
/// with an ignorable/variable element — the value used to place a string in an
/// index bucket. Both the tailored and root (identity) tailorings emit the pair,
/// so a tailored letter (`å` → `(z, sub)`) is distinguished from its anchor.
fn first_primary(tail: &Tailoring, s: &str) -> u32 {
    let key = tail.sort_key(s);
    let base = key.first().copied().unwrap_or(0) as u32;
    if base == 0 {
        return 0;
    }
    let sub = key.get(1).copied().unwrap_or(0) as u32;
    (base << 16) | sub
}

/// The alphabetic-index bucket **labels** for `lang` — the headings under which
/// strings are grouped, in collation order: `A`–`Z` plus the locale's extra
/// letters (Swedish `Å Ä Ö`, Czech `Ch`, …). Latin-script locales only; an
/// unknown or non-Latin locale yields just `A`–`Z`.
///
/// ```
/// # #[cfg(feature = "alloc")] {
/// use intl::unicode::collate::index_labels;
/// assert_eq!(index_labels("sv").last().map(String::as_str), Some("Ö"));
/// assert_eq!(index_labels("en").len(), 26);
/// # }
/// ```
#[must_use]
pub fn index_labels(lang: &str) -> Vec<alloc::string::String> {
    use alloc::string::ToString;
    let extra: &[&str] = match lang.split(['-', '_']).next().unwrap_or(lang) {
        "sv" | "fi" => &["Å", "Ä", "Ö"],
        "da" | "nb" | "nn" | "no" => &["Æ", "Ø", "Å"],
        "is" => &["Þ", "Æ", "Ö"],
        "es" | "gl" => &["Ñ"],
        "et" => &["Š", "Ž", "Õ", "Ä", "Ö", "Ü"],
        "cs" | "sk" => &["Č", "Ch", "Ř", "Š", "Ž"],
        "pl" => &["Ą", "Ć", "Ę", "Ł", "Ń", "Ó", "Ś", "Ź", "Ż"],
        "hu" => &["Cs", "Dz", "Dzs", "Gy", "Ly", "Ny", "Sz", "Ty", "Zs"],
        "tr" | "az" => &["Ç", "Ğ", "Ö", "Ş", "Ü"],
        "ro" => &["Ă", "Â", "Î", "Ș", "Ț"],
        "sq" => &[
            "Ç", "Dh", "Ë", "Gj", "Ll", "Nj", "Rr", "Sh", "Th", "Xh", "Zh",
        ],
        "cy" => &["Ch", "Dd", "Ff", "Ng", "Ll", "Ph", "Rh", "Th"],
        _ => &[],
    };
    let tail = Tailoring::for_locale(lang).unwrap_or_else(Tailoring::identity);
    let mut labels: Vec<alloc::string::String> = ('A'..='Z')
        .map(|c| c.to_string())
        .chain(extra.iter().map(|s| s.to_string()))
        .collect();
    // Order the labels by collation, so an inserted letter lands in its real
    // place (Spanish `Ñ` after `N`, Swedish `Å Ä Ö` after `Z`).
    labels.sort_by_key(|l| first_primary(&tail, l));
    labels
}

/// The alphabetic-index bucket that `s` sorts into for `lang` (the ICU
/// `AlphabeticIndex` operation): one of [`index_labels`], or `"#"` for a string
/// that sorts before `A` (digits, symbols) or past the last label (other
/// scripts). A diacritic letter that sorts *between* two labels (like `á`) is
/// grouped under the earlier one (`A`), matching ICU.
///
/// ```
/// # #[cfg(feature = "alloc")] {
/// use intl::unicode::collate::index_bucket;
/// assert_eq!(index_bucket("en", "Apple"), "A");
/// assert_eq!(index_bucket("en", "Ångström"), "A"); // root: å ≈ a
/// assert_eq!(index_bucket("sv", "Ångström"), "Å"); // Swedish: å is its own letter
/// assert_eq!(index_bucket("en", "123"), "#");
/// # }
/// ```
#[must_use]
pub fn index_bucket(lang: &str, s: &str) -> alloc::string::String {
    use alloc::string::ToString;
    let tail = Tailoring::for_locale(lang).unwrap_or_else(Tailoring::identity);
    let sp = first_primary(&tail, s);
    if sp == 0 {
        return "#".to_string(); // sorts before A (variable/ignorable lead)
    }
    let labels = index_labels(lang);
    let mut chosen: Option<usize> = None;
    for (i, label) in labels.iter().enumerate() {
        if first_primary(&tail, label) <= sp {
            chosen = Some(i);
        } else {
            break;
        }
    }
    match chosen {
        // Past the last label and not equal to it → a later script: overflow.
        Some(i) if i == labels.len() - 1 && first_primary(&tail, &labels[i]) < sp => {
            "#".to_string()
        }
        Some(i) => labels[i].clone(),
        None => "#".to_string(),
    }
}

/// Collation strength — the most significant weight level that is compared.
/// Lower strengths ignore finer distinctions: [`Primary`](Strength::Primary)
/// ignores accents and case, [`Secondary`](Strength::Secondary) ignores case
/// (but not accents), [`Tertiary`](Strength::Tertiary) (the default) compares
/// everything.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Strength {
    /// Level 1 only: base letters (`a` = `A` = `á`).
    Primary,
    /// Levels 1–2: accents matter, case does not (`a` = `A`, `á` ≠ `a`).
    Secondary,
    /// Levels 1–3 (default): accents and case both matter.
    Tertiary,
    /// Levels 1–4: also distinguishes shifted variable elements.
    Quaternary,
}

/// Build the sort key (a sequence of 16-bit weights) for a collation element
/// array under the given variable handling, truncated at `strength`.
fn build_sort_key(cea: &[u64], alternate: AlternateHandling, strength: Strength) -> Vec<u16> {
    let mut key = Vec::new();
    match alternate {
        AlternateHandling::NonIgnorable => {
            for &ce in cea {
                let p = primary(ce);
                if p != 0 {
                    key.push(p);
                }
            }
            if strength == Strength::Primary {
                return key;
            }
            key.push(0);
            for &ce in cea {
                let s = secondary(ce);
                if s != 0 {
                    key.push(s);
                }
            }
            if strength == Strength::Secondary {
                return key;
            }
            key.push(0);
            for &ce in cea {
                let t = tertiary(ce);
                if t != 0 {
                    key.push(t);
                }
            }
        }
        AlternateHandling::Shifted => {
            // Transform each element, tracking whether we follow a shifted
            // variable; collect (p, s, t, quaternary).
            let mut rows: Vec<(u16, u16, u16, u16)> = Vec::with_capacity(cea.len());
            let mut after_variable = false;
            for &ce in cea {
                let (p, s, t) = (primary(ce), secondary(ce), tertiary(ce));
                if is_variable(ce) && p != 0 {
                    rows.push((0, 0, 0, p)); // shifted to the quaternary level
                    after_variable = true;
                } else if p == 0 && s == 0 && t == 0 {
                    rows.push((0, 0, 0, 0)); // completely ignorable: transparent
                } else if p == 0 {
                    // Primary-ignorable (combining mark): fully shifted if it
                    // trails a variable, otherwise significant with L4 = FFFF.
                    if after_variable {
                        rows.push((0, 0, 0, 0));
                    } else {
                        rows.push((0, s, t, 0xFFFF));
                    }
                } else {
                    rows.push((p, s, t, 0xFFFF));
                    after_variable = false;
                }
            }
            for &(p, ..) in &rows {
                if p != 0 {
                    key.push(p);
                }
            }
            if strength == Strength::Primary {
                return key;
            }
            key.push(0);
            for &(_, s, ..) in &rows {
                if s != 0 {
                    key.push(s);
                }
            }
            if strength == Strength::Secondary {
                return key;
            }
            key.push(0);
            for &(_, _, t, _) in &rows {
                if t != 0 {
                    key.push(t);
                }
            }
            if strength == Strength::Tertiary {
                return key;
            }
            key.push(0);
            for &(.., q) in &rows {
                if q != 0 {
                    key.push(q);
                }
            }
        }
    }
    key
}

/// A configured collator.
#[derive(Debug, Clone, Copy)]
pub struct Collator {
    alternate: AlternateHandling,
    strength: Strength,
    numeric: bool,
}

impl Default for Collator {
    fn default() -> Self {
        Collator {
            alternate: AlternateHandling::Shifted,
            strength: Strength::Tertiary,
            numeric: false,
        }
    }
}

impl Collator {
    /// A collator with the given variable handling (and tertiary strength).
    #[must_use]
    pub fn new(alternate: AlternateHandling) -> Self {
        Collator {
            alternate,
            strength: Strength::Tertiary,
            numeric: false,
        }
    }

    /// Set the comparison [`Strength`] (e.g. [`Strength::Primary`] for
    /// accent- and case-insensitive comparison).
    #[must_use]
    pub fn with_strength(mut self, strength: Strength) -> Self {
        self.strength = strength;
        self
    }

    /// Enable **numeric** ordering (CLDR `kn`): runs of ASCII digits compare by
    /// numeric value, so `"item2"` sorts before `"item10"`.
    #[must_use]
    pub fn with_numeric(mut self, numeric: bool) -> Self {
        self.numeric = numeric;
        self
    }

    /// The DUCET sort key for `s`: comparing two sort keys lexicographically
    /// yields the same order as [`compare`](Self::compare).
    #[must_use]
    pub fn sort_key(&self, s: &str) -> Vec<u16> {
        let cv: Vec<char> = nfd(s.chars()).collect();
        let cea = if self.numeric {
            collation_elements_numeric(cv)
        } else {
            collation_elements(cv)
        };
        build_sort_key(&cea, self.alternate, self.strength)
    }

    /// Compare two strings in DUCET collation order.
    #[must_use]
    pub fn compare(&self, a: &str, b: &str) -> Ordering {
        self.sort_key(a).cmp(&self.sort_key(b))
    }
}

/// Compare two strings in DUCET collation order using the default collator
/// (variable elements [shifted](AlternateHandling::Shifted)).
#[must_use]
pub fn compare(a: &str, b: &str) -> Ordering {
    Collator::default().compare(a, b)
}

/// The DUCET sort key for `s` using the default collator.
#[must_use]
pub fn sort_key(s: &str) -> Vec<u16> {
    Collator::default().sort_key(s)
}

/// A **locale-tailored** collator: the DUCET order with per-locale primary
/// reordering applied (CLDR tailoring rules). Built from a rule string such as
/// `"&z < å < ä < ö"` (Swedish), which places `å`/`ä`/`ö` immediately after `z`.
///
/// Supported relations: `<`/`<<`/`<<<` (primary/secondary/tertiary), `=`
/// (identical), their `*` range forms, plus `[before]` reset-before and
/// `[import]` (see [`parse`](Self::parse) for the full grammar). Each tailored
/// letter is given a primary weight just above (or below, for `[before]`) its
/// reset anchor; upper-case forms are added automatically. Characters not
/// mentioned keep their DUCET order.
///
/// **Capacity:** tailored letters share their anchor's DUCET primary as a *base*
/// and are ordered by a second *sub-weight* component (the sort key emits a
/// `(base, sub)` pair per element), so a single reset can be followed by an
/// effectively unbounded number of consecutive primary (`<`) reorderings —
/// `&a < x₁ < x₂ < … < x₅₀` sorts correctly, between the anchor and the next
/// base letter, with no gap-exhaustion. This pair encoding is used only by the
/// tailored sort key; the root [`compare`]/[`sort_key`] path is unchanged.
///
/// ```
/// # #[cfg(feature = "alloc")] {
/// use intl::unicode::collate::Tailoring;
/// use core::cmp::Ordering;
/// let sv = Tailoring::parse("&z < å < ä < ö").unwrap();
/// // In Swedish, å/ä/ö sort *after* z, not near a/o.
/// assert_eq!(sv.compare("z", "å"), Ordering::Less);
/// assert_eq!(sv.compare("ä", "ö"), Ordering::Less);
/// assert_eq!(sv.compare("z", "ö"), Ordering::Less);
/// # }
/// ```
pub struct Tailoring {
    /// Tailored NFD sequences → collation-element sequence, sorted longest-first.
    entries: Vec<(Vec<char>, Vec<u64>)>,
    /// Script `[reorder …]` mapping (CLDR reorder codes → primary-rank remap), or
    /// `None` when the rule has no `[reorder]` of script groups. Applied by
    /// [`sort_key`](Self::sort_key) so whole scripts move (e.g. `[reorder Cyrl]`
    /// sorts Cyrillic before Latin for `ru`/`bg`/`sr`), preserving within-script
    /// order. See [`Reorder`].
    reorder: Option<Reorder>,
    /// zh collation: when `Some`, Han ideographs are weighted by their rank in
    /// this ranked Han-weight table ([`zh_ranked`]) — pinyin ([`ZH_PINYIN`]),
    /// stroke ([`ZH_STROKE`]) or zhuyin ([`ZH_ZHUYIN`]) — with the radical-stroke
    /// fallback for the rest, instead of the DUCET implicit weight. `None` for
    /// every non-zh tailoring. Set by [`Tailoring::zh`] (feature `collation-zh`).
    #[cfg(feature = "collation-zh")]
    han: Option<&'static [u8]>,
    /// zh `unihan` collation (`zh-u-co-unihan`): when `true`, *every* Han
    /// ideograph is ordered by Unihan radical-stroke ([`zh_rs_key`]) — the ranked
    /// (`han`) table is bypassed entirely, so readings never influence the order.
    /// Set by [`Tailoring::zh_unihan`] (feature `collation-zh`).
    #[cfg(feature = "collation-zh")]
    han_unihan: bool,
}

impl Tailoring {
    /// A built-in tailoring for a locale, or `None` if none is bundled. Two
    /// sources are consulted, in order: the **official CLDR collation rules**
    /// (generated into a committed table for the bulk of the coverage — including
    /// the Japanese kana collation and Croatian/Bosnian), then a small set of
    /// hand-written rules for locales kept out of that table (e.g. the Nordic
    /// `&z < å < ä < ö`, or `[before]`-based rules the data-consistency gate's
    /// simple tokenizer can't validate: Icelandic, Turkish, Estonian, Kazakh).
    ///
    /// A self-consistency gate (`tests/collation_data_consistency`) excludes from
    /// the generated table any locale whose rule the parser would mis-order
    /// (decomposing-letter anchors, chained multi-char expansions), so this never
    /// returns a tailoring that sorts against its own rule — it falls back to a
    /// hand-written rule or to root DUCET instead.
    ///
    /// ```
    /// # #[cfg(feature = "alloc")] {
    /// use intl::unicode::collate::Tailoring;
    /// use core::cmp::Ordering;
    /// let sv = Tailoring::for_locale("sv").unwrap();
    /// assert_eq!(sv.compare("z", "å"), Ordering::Less);
    /// let es = Tailoring::for_locale("es").unwrap(); // from CLDR data
    /// assert_eq!(es.compare("n", "ñ"), Ordering::Less);
    /// # }
    /// ```
    #[must_use]
    pub fn for_locale(lang: &str) -> Option<Tailoring> {
        // Normalize, then try the official CLDR rule table — first the full tag
        // (`ff-adlm`), then the primary subtag (`es`) — before the hand-written
        // fallbacks. A plain `[..2]` truncation would alias "fil" to "fi".
        let full = lang.replace('_', "-").to_ascii_lowercase();
        let primary = full.split('-').next().unwrap_or(&full);
        // Chinese defaults to pinyin collation (feature `collation-zh`); the
        // `-u-co-stroke` / `-u-co-zhuyin` BCP-47 collation keywords select the
        // stroke / zhuyin variants. Handled before the CLDR rule table since zh's
        // Han order is a per-codepoint weight table, not a runtime rule string.
        #[cfg(feature = "collation-zh")]
        if primary == "zh" {
            // `zh-u-co-unihan` orders every Han by radical-stroke (readings
            // ignored) — a distinct code path, not a ranked Han-weight table.
            if full.find("-u-co-").map(|i| &full[i + 6..]) == Some("unihan") {
                return Some(Tailoring::zh_unihan());
            }
            let table = match full.find("-u-co-").map(|i| &full[i + 6..]) {
                Some("stroke") => ZH_STROKE,
                Some("zhuyin") => ZH_ZHUYIN,
                // `pinyin`, `standard`, an unknown/unsupported keyword, or none →
                // the default pinyin table.
                _ => ZH_PINYIN,
            };
            return Some(Tailoring::zh(table));
        }
        for key in [full.as_str(), primary] {
            if let Some(rule) = crate::cldr::collation_rule(key)
                && let Some(t) = Tailoring::parse(rule)
            {
                return Some(t);
            }
        }
        // Korean (`ko`) is now bundled from CLDR (`[reorder Hang Hani]` + the
        // hanja-by-reading table), resolved by the loop above; no hand fallback.
        // Hangul and reading-bearing hanja match V8 exactly; the only residual is
        // hanja with no CLDR Korean reading, which fall to DUCET (code-point) order
        // rather than V8's radical-stroke (the radical-stroke table is gated behind
        // `collation-zh`, out of the default `collation` build).
        let lc = primary;
        let rules = match lc {
            "sv" | "fi" => "&z < å < ä < ö",               // Swedish, Finnish
            "da" | "nb" | "nn" | "no" => "&z < æ < ø < å", // Danish, Norwegian
            // Icelandic (CLDR): accented vowels reset *before* the next base letter
            // (so ý sorts just before z's neighbor, þ after z, then æ ä ö ø å).
            "is" => {
                "&[before 1]b<á<<<Á &d<<đ<<<Đ<ð<<<Ð &[before 1]f<é<<<É &[before 1]j<í<<<Í \
                 &[before 1]p<ó<<<Ó &[before 1]v<ú<<<Ú &[before 1]z<ý<<<Ý \
                 &[before 1]ǀ<æ<<<Æ<<ä<<<Ä<ö<<<Ö<<ø<<<Ø<å<<<Å"
            }
            // Estonian (CLDR): š/z/ž reset before T (so they sort after s), and
            // õ/ä/ö/ü reset before X (so they sort after w) — not all after s.
            "et" => "&[before 1]T<š<<<Š<z<<<Z<ž<<<Ž &[before 1]X<õ<<<Õ<ä<<<Ä<ö<<<Ö<ü<<<Ü",
            "de" => "&ae = ä &oe = ö &ue = ü &ss = ß", // German phonebook (expansions)
            "pl" => "&a < ą &c < ć &e < ę &l < ł &n < ń &o < ó &s < ś &z < ź < ż", // Polish
            "cs" | "sk" => "&c < č &h < ch &r < ř &s < š &z < ž", // Czech/Slovak (ch digraph)
            // Turkish (CLDR): dotless ı resets *before* i (ı sorts between h and i).
            "tr" => "&C<ç<<<Ç &G<ğ<<<Ğ &[before 1]i<ı<<<I &i<<<İ &O<ö<<<Ö &S<ş<<<Ş &U<ü<<<Ü",
            "az" => "&c < ç &g < ğ &h < ı &i < i̇ &o < ö &s < ş &u < ü", // Azerbaijani
            "lv" => "&c < č &g < ģ &i < ī &k < ķ &l < ļ &n < ņ &s < š &z < ž", // Latvian
            "lt" => "&c < č &s < š &z < ž",                             // Lithuanian
            // Serbo-Croatian Latin digraphs (bs imports this via `[import hr]`).
            // `sr` (default Cyrillic) is bundled from CLDR as `[reorder Cyrl]`
            // instead, so only `hr` (Latin) uses this hand rule.
            "hr" => "&c < č < ć &d < dž < đ &l < lj &n < nj &s < š &z < ž",
            // Kazakh (CLDR): Cyrillic ё/ү after their bases, і reset before ь.
            "kk" => "&Е<ё<<<Ё &Ұ<ү<<<Ү &[before 1]ь<і<<<І",
            "es" => "&n < ñ", // Spanish (ñ after n)
            // Hungarian digraphs (dzs/dz longest-match first via the engine sort),
            // plus gemination: a doubled digraph like `ccs`/`ggy`/`ddzs` collates
            // as the digraph doubled (`cs`+`cs`) via `/`-expansion, one tertiary
            // step above it (CLDR `&cs<<<ccs/cs`). Verified against V8.
            "hu" => {
                "&c < cs &d < dz < dzs &g < gy &l < ly &n < ny &s < sz &t < ty &z < zs \
                 &O < ö <<< Ö << ő <<< Ő &U < ü <<< Ü << ű <<< Ű \
                 &cs <<< ccs / cs &dz <<< ddz / dz &dzs <<< ddzs / dzs &gy <<< ggy / gy \
                 &ly <<< lly / ly &ny <<< nny / ny &sz <<< ssz / sz &ty <<< tty / ty \
                 &zs <<< zzs / zs"
            }
            "ro" => "&a < ă < â &i < î &s < ș &t < ț", // Romanian
            "sq" => {
                "&c < ç &d < dh &e < ë &g < gj &l < ll &n < nj &r < rr &s < sh &t < th &x < xh &z < zh"
            } // Albanian
            "uk" => "&г < ґ &е < є &и < і < ї",        // Ukrainian (Cyrillic)
            "vi" => "&a < ă < â &d < đ &e < ê &o < ô < ơ &u < ư", // Vietnamese (base letters)
            // Welsh digraphs (ch/dd/ff/ng/ll/ph/rh/th), each after its base letter.
            "cy" => "&c < ch &d < dd &f < ff &g < ng &l < ll &p < ph &r < rh &t < th",
            "fil" | "tl" => "&n < ñ < ng", // Filipino/Tagalog (ng digraph)
            "fo" => "&a < á &d < ð &i < í &o < ó &u < ú &y < ý &z < æ < ø", // Faroese
            "kl" => "&z < æ < ø < å",      // Greenlandic (Danish-style)
            "gl" => "&n < ñ",              // Galician (ñ after n)
            "ga" => "&a < á &e < é &i < í &o < ó &u < ú", // Irish (long-vowel accents)
            "ha" => "&b < ɓ &d < ɗ &k < ƙ &s < sh &t < ts &y < ƴ", // Hausa (hooked letters)
            _ => return None,
        };
        Tailoring::parse(rules)
    }

    /// Parse a CLDR-style tailoring rule string. Supported syntax:
    ///
    /// * relations `<` (primary), `<<` (secondary), `<<<` (tertiary), `=`
    ///   (identity), and their **star / range** forms `<*`, `<<*`, `<<<*`, `=*`
    ///   (each character of the target run is related to the previous one);
    /// * **expansions** when the reset anchor is a multi-character string
    ///   (`"&ae = ä"` makes `ä` collate as `"ae"`);
    /// * `[before 1|2|3] <anchor>` — reset *before* the anchor, so the following
    ///   letters sort immediately below it (`&[before 1] i < ı` puts `ı` between
    ///   `h` and `i`);
    /// * `[import <locale>]` — splice in another bundled locale's parsed rules;
    /// * `[reorder <code> …]` — script reordering: whole scripts move as blocks
    ///   (e.g. `[reorder Cyrl]` sorts Cyrillic before Latin), preserving
    ///   within-script order. Special low groups
    ///   (`space`/`punct`/`digit`/…) are parsed but kept in their default front
    ///   position (reordering *among* them is not modeled);
    /// * `\uXXXX` / `\UXXXXXXXX` escapes and `'…'` / `''` quoting of literals;
    /// * option resets that carry no ordering — `[normalization …]`,
    ///   `[caseFirst …]`, `[suppressContractions …]`, `[optimize …]` — are
    ///   ignored, and `#…` line comments are stripped.
    ///
    /// Returns `None` if a reset anchor or target is malformed or no orderings
    /// were produced.
    #[must_use]
    pub fn parse(rules: &str) -> Option<Tailoring> {
        let mut entries: Vec<(Vec<char>, Vec<u64>)> = Vec::new();
        let mut reorder_codes: Vec<ReorderCode> = Vec::new();
        Self::parse_into(rules, &mut entries, &mut reorder_codes, 0)?;
        let reorder = Reorder::build(&reorder_codes);
        // A rule with *only* a `[reorder …]` (no `<`/`=` orderings) — as `ru`/`bg`/
        // `sr` — is a valid tailoring: its reorder mapping is the whole content.
        if entries.is_empty() && reorder.is_none() {
            return None;
        }
        // Longest sequences first so contractions win during matching.
        entries.sort_by_key(|e| core::cmp::Reverse(e.0.len()));
        Some(Tailoring {
            entries,
            reorder,
            #[cfg(feature = "collation-zh")]
            han: None,
            #[cfg(feature = "collation-zh")]
            han_unihan: false,
        })
    }

    /// Parse `rules` into `entries` (orderings) and `reorder_codes` (any
    /// `[reorder …]` group list). `depth` bounds `[import]` recursion.
    fn parse_into(
        rules: &str,
        entries: &mut Vec<(Vec<char>, Vec<u64>)>,
        reorder_codes: &mut Vec<ReorderCode>,
        depth: u32,
    ) -> Option<()> {
        if depth > 8 {
            return Some(()); // import cycle / runaway guard
        }
        let toks = lex(rules)?;
        let mut anchor: Vec<char> = Vec::new();
        let mut anchor_primary = 0u32;
        // The anchor's full DUCET collation-element sequence. Used when the anchor
        // has two or more non-ignorable primaries (a Hangul syllable in Korean's
        // hanja-by-reading rule), where the single first-primary sub-weight cannot
        // place the tailored target at the anchor's real sort position.
        let mut anchor_ces: Vec<u64> = Vec::new();
        // If the reset anchor is itself a previously-tailored letter (e.g. the
        // Hungarian digraph `cs`), its full synthetic CE — carrying the tailoring
        // sub-weight, secondary and tertiary that a plain DUCET primary lacks. A
        // following `<<`/`<<<` variant then bumps from *that* CE, so `ccs` lands
        // just after the tailored `cs` rather than after root `c`.
        let mut anchor_ce: Option<u64> = None;
        let mut before = false; // current reset was `[before …]`
        // Running offsets within each level relative to the reset anchor.
        let (mut p_off, mut s_off, mut t_off) = (0u32, 0u32, 0u32);
        let mut i = 0;
        while i < toks.len() {
            match &toks[i] {
                Tok::Amp => {
                    i += 1;
                    // `[before N]` places the following letters just below the
                    // anchor. We model reset-before at the primary level (the only
                    // level any bundled rule uses); a `[before 2|3]` is treated the
                    // same, i.e. just below the anchor's primary.
                    before = false;
                    if let Some(Tok::Before(lvl)) = toks.get(i) {
                        before = *lvl >= 1;
                        i += 1;
                    }
                    let mut a = Vec::new();
                    while let Some(Tok::Lit(c)) = toks.get(i) {
                        a.push(*c);
                        i += 1;
                    }
                    anchor = a;
                    // NFD the anchor before deriving its CEs — the runtime NFDs
                    // input first, so a precomposed anchor (notably a Hangul
                    // syllable, which UCA weights via its decomposed jamo, not a
                    // single mapping) must be decomposed here to match.
                    let anchor_nfd: Vec<char> = nfd(anchor.iter().copied()).collect();
                    anchor_ces = collation_elements(anchor_nfd.clone());
                    anchor_primary = primary(*anchor_ces.first()?) as u32;
                    // Reset onto a tailored letter → adopt its synthetic CE.
                    anchor_ce = entries.iter().find_map(|(seq, ces)| {
                        (seq == &anchor_nfd && ces.len() == 1).then_some(ces[0])
                    });
                    (p_off, s_off, t_off) = (0, 0, 0);
                }
                Tok::Rel(level) => {
                    let level = *level;
                    i += 1;
                    let star = matches!(toks.get(i), Some(Tok::Star));
                    if star {
                        i += 1;
                    }
                    let mut target = Vec::new();
                    while let Some(Tok::Lit(c)) = toks.get(i) {
                        target.push(*c);
                        i += 1;
                    }
                    // Optional `/expansion` (Hungarian gemination `ccs/cs`).
                    let mut expansion: Vec<char> = Vec::new();
                    if matches!(toks.get(i), Some(Tok::Slash)) {
                        i += 1;
                        while let Some(Tok::Lit(c)) = toks.get(i) {
                            expansion.push(*c);
                            i += 1;
                        }
                    }
                    if target.is_empty() || anchor_primary == 0 {
                        return None;
                    }
                    // `<*abc` (and friends) is shorthand for `<a<b<c`: apply the
                    // relation to each character in turn. Otherwise the whole run
                    // is one contraction/expansion target.
                    let groups: Vec<Vec<char>> = if star {
                        target.iter().map(|&c| alloc::vec![c]).collect()
                    } else {
                        alloc::vec![target]
                    };
                    let n_groups = groups.len();
                    for (gi, g) in groups.into_iter().enumerate() {
                        // A star run's expansion (if any) attaches only to its last
                        // character; a plain (non-star) target is a single group.
                        let exp = if gi + 1 == n_groups {
                            expansion.as_slice()
                        } else {
                            &[]
                        };
                        Self::apply_relation(
                            entries,
                            level,
                            &g,
                            &anchor,
                            anchor_primary,
                            anchor_ce,
                            &anchor_ces,
                            before,
                            exp,
                            &mut p_off,
                            &mut s_off,
                            &mut t_off,
                        );
                    }
                }
                Tok::Import(loc) => {
                    // Splice in another bundled locale's rules — from its CLDR rule
                    // string if bundled, else from its hand-written fallback (so
                    // `[import hr]` resolves even though hr has no rule table entry).
                    // Unresolvable imports (e.g. the private `*-u-co-*` kana/unihan
                    // tables) are skipped rather than failing the whole parse.
                    if let Some(rule) = import_rule(loc) {
                        Self::parse_into(rule, entries, reorder_codes, depth + 1)?;
                    } else if depth < 8
                        && let Some(t) = import_tailoring(loc)
                    {
                        entries.extend(t.entries);
                    }
                    i += 1;
                    // The import may leave the anchor context in any state; require
                    // an explicit `&` reset before the next relation.
                    anchor_primary = 0;
                }
                Tok::Reorder(codes) => {
                    for c in codes {
                        if let Some(rc) = ReorderCode::parse(c) {
                            reorder_codes.push(rc);
                        }
                    }
                    i += 1;
                }
                // Stray tokens (a `[before]`/`Star` not following its operator, an
                // ignored option bracket, or a leftover literal) carry no ordering.
                _ => i += 1,
            }
        }
        Some(())
    }

    /// Apply one non-reset relation to `target` under the current anchor.
    /// `expansion`, if non-empty, is appended to `target`'s collation elements
    /// (the CLDR `Y/Z` form). `anchor_ce` is the tailored anchor's synthetic CE
    /// when the reset landed on a previously-tailored letter (see `parse_into`).
    #[allow(clippy::too_many_arguments)]
    fn apply_relation(
        entries: &mut Vec<(Vec<char>, Vec<u64>)>,
        level: u8,
        target: &[char],
        anchor: &[char],
        anchor_primary: u32,
        anchor_ce: Option<u64>,
        anchor_ces: &[u64],
        before: bool,
        expansion: &[char],
        p_off: &mut u32,
        s_off: &mut u32,
        t_off: &mut u32,
    ) {
        if level == 0 {
            // `=` identity / expansion: target collates as the anchor.
            Self::push_expansion(entries, target, anchor);
            return;
        }
        match level {
            1 => (*p_off, *s_off, *t_off) = (*p_off + 1, 0, 0),
            2 => (*s_off, *t_off) = (*s_off + 1, 0),
            _ => *t_off += 1,
        }
        // Resolve the expansion (if any) to collation elements, matching already-
        // tailored letters first (so `/cs` uses the Hungarian digraph's CE, not
        // root `c`+`s`), then root DUCET for the remainder.
        let exp_ces = Self::resolve_expansion(entries, expansion);
        // Multi-primary anchor (a Hangul syllable in Korean's hanja-by-reading
        // rule): the target must carry the anchor's *full* primary sequence so it
        // sorts at the anchor's real position (`&가<<伽` puts 伽 right after the
        // whole syllable 가, before 각), which the single first-primary sub-weight
        // below cannot express. Only fires for a plain (non-tailored) anchor with
        // two or more non-ignorable primaries and a secondary/tertiary relation —
        // no single-letter Latin/Cyrillic rule qualifies, so their order is
        // unchanged.
        if anchor_ce.is_none()
            && level >= 2
            && anchor_ces.iter().filter(|&&ce| primary(ce) != 0).count() >= 2
        {
            Self::push_anchor_expansion(
                entries, target, anchor_ces, level, *s_off, *t_off, &exp_ces,
            );
            return;
        }
        // A secondary/tertiary variant of a *tailored* anchor copies that anchor's
        // full CE (primary base, sub-weight, secondary) and bumps only the level's
        // weight — otherwise the plain-DUCET path (base primary + sub-weight).
        if let (Some(ce), true) = (anchor_ce, level >= 2) {
            Self::push_variant(entries, target, ce, *s_off, *t_off, &exp_ces);
            return;
        }
        // Tailored letters share the anchor's DUCET primary as their base and are
        // ordered by a sub-weight: `SUB_MID + p_off` places them just *after* the
        // anchor, `SUB_BEFORE + p_off` just *before* it (a `[before]` reset).
        let region = if before { SUB_BEFORE } else { SUB_MID };
        let sub = region as u32 + *p_off;
        Self::push_letter(
            entries,
            target,
            anchor_primary,
            sub,
            *s_off,
            *t_off,
            &exp_ces,
        );
    }

    /// Collation elements of `seq`, resolving the longest already-tailored entry
    /// at each position first (so a Hungarian `/cs` expansion picks up the `cs`
    /// digraph's synthetic CE), then falling back to root DUCET for the rest.
    fn resolve_expansion(entries: &[(Vec<char>, Vec<u64>)], seq: &[char]) -> Vec<u64> {
        let nfd_seq: Vec<char> = nfd(seq.iter().copied()).collect();
        let mut out = Vec::new();
        let mut i = 0;
        while i < nfd_seq.len() {
            // Longest tailored entry that is a prefix at `i` (entries aren't sorted
            // during the parse, so scan for the max length explicitly).
            let mut best: Option<&Vec<u64>> = None;
            let mut best_len = 0;
            for (s, ces) in entries {
                if !s.is_empty()
                    && s.len() > best_len
                    && nfd_seq[i..].len() >= s.len()
                    && nfd_seq[i..i + s.len()] == s[..]
                {
                    best = Some(ces);
                    best_len = s.len();
                }
            }
            if let Some(ces) = best {
                out.extend_from_slice(ces);
                i += best_len;
            } else {
                out.extend(collation_elements(alloc::vec![nfd_seq[i]]));
                i += 1;
            }
        }
        out
    }

    /// Case variants of a tailored `target`: the lower form (tertiary `0x02`),
    /// the all-upper form (`0x08`), and — for a multi-char target — the
    /// title-case form (`0x08`), so `ch`/`CH`/`Ch` all match.
    fn case_variants(target: &[char]) -> Vec<(Vec<char>, u32)> {
        let upper_all: Vec<char> = target.iter().map(|&c| upper(c)).collect();
        let mut v = alloc::vec![(target.to_vec(), 0x0002u32), (upper_all, 0x0008u32)];
        if target.len() > 1 {
            let mut title = target.to_vec();
            title[0] = upper(target[0]);
            v.push((title, 0x0008));
        }
        v
    }

    /// Map `target` (in each case form) to a single synthetic collation element
    /// at primary `p`, secondary/tertiary bumped by `s_off`/`t_off`, optionally
    /// followed by `exp_ces` (a `/expansion`).
    fn push_letter(
        entries: &mut Vec<(Vec<char>, Vec<u64>)>,
        target: &[char],
        base: u32,
        sub: u32,
        s_off: u32,
        t_off: u32,
        exp_ces: &[u64],
    ) {
        for (form, case_t) in Self::case_variants(target) {
            let all_upper = form.iter().all(|c| !c.is_lowercase());
            let seq: Vec<char> = nfd(form.into_iter()).collect();
            if !seq.is_empty() {
                let mut ces = alloc::vec![pack_tailored(base, sub, 0x0020 + s_off, case_t + t_off)];
                ces.extend(Self::cased_expansion(exp_ces, all_upper));
                entries.push((seq, ces));
            }
        }
    }

    /// Map `target` (in each case form) to a **tertiary/secondary variant** of an
    /// existing tailored anchor CE: the anchor's primary base, sub-weight and
    /// secondary are kept, and only the bumped level differs — so `ccs` sorts as
    /// the geminated `cs` (`<<<`), just above plain `cs`. `exp_ces` (the `/cs`
    /// expansion) is appended.
    fn push_variant(
        entries: &mut Vec<(Vec<char>, Vec<u64>)>,
        target: &[char],
        anchor_ce: u64,
        s_off: u32,
        t_off: u32,
        exp_ces: &[u64],
    ) {
        let base = primary(anchor_ce) as u32;
        let sub = sub_weight(anchor_ce) as u32;
        let sec = secondary(anchor_ce) as u32 + s_off;
        for (form, case_t) in Self::case_variants(target) {
            let all_upper = form.iter().all(|c| !c.is_lowercase());
            let seq: Vec<char> = nfd(form.into_iter()).collect();
            if !seq.is_empty() {
                let mut ces = alloc::vec![pack_tailored(base, sub, sec, case_t + t_off)];
                ces.extend(Self::cased_expansion(exp_ces, all_upper));
                entries.push((seq, ces));
            }
        }
    }

    /// Map a `target` (e.g. a Korean hanja) to an **expansion of a multi-primary
    /// anchor** (its reading Hangul syllable): the anchor's full DUCET collation
    /// elements, followed by a primary-ignorable *distinguisher* CE that bumps the
    /// secondary (`<<`) or tertiary (`<<<`) weight by the running offset. The
    /// target thus shares the anchor's primaries (equal at primary strength, like
    /// V8/ICU) yet sorts just after it, and successive targets under one anchor
    /// order by their increasing offset. `exp_ces` (a `/expansion`, unused by the
    /// Korean rule) is appended. No case variants — hanja and Hangul are uncased.
    fn push_anchor_expansion(
        entries: &mut Vec<(Vec<char>, Vec<u64>)>,
        target: &[char],
        anchor_ces: &[u64],
        level: u8,
        s_off: u32,
        t_off: u32,
        exp_ces: &[u64],
    ) {
        let seq: Vec<char> = nfd(target.iter().copied()).collect();
        if seq.is_empty() {
            return;
        }
        let mut ces = anchor_ces.to_vec();
        // Primary-ignorable distinguisher: a secondary bump for `<<`, a tertiary
        // bump for `<<<` (each offset is ≥ 1 here, so the target never collides
        // with the bare anchor).
        let dist = if level == 2 {
            pack(0, 0x0020 + s_off, 0x0002)
        } else {
            pack(0, 0x0020, 0x0002 + t_off)
        };
        ces.push(dist);
        ces.extend_from_slice(exp_ces);
        entries.push((seq, ces));
    }

    /// The expansion CEs for a given case form. Root-derived expansion CEs are
    /// lower-case; for an all-upper target form (`CCS`), raise their tertiary case
    /// weight so `CCS`'s trailing `CS` is upper-cased too. Synthetic (tailored)
    /// expansion CEs keep whatever case they were tailored with.
    fn cased_expansion(exp_ces: &[u64], all_upper: bool) -> Vec<u64> {
        if !all_upper {
            return exp_ces.to_vec();
        }
        exp_ces
            .iter()
            .map(|&ce| {
                // Raise a lower-case tertiary (0x02) to the upper form (0x08),
                // leaving already-cased or ignorable tertiaries untouched.
                if tertiary(ce) == 0x0002 {
                    (ce & !0xFFFF) | 0x0008
                } else {
                    ce
                }
            })
            .collect()
    }

    /// Map `target` (lower and upper forms) to the full collation-element
    /// sequence of the `anchor` string — an expansion (`ä` → CEs of `"ae"`).
    fn push_expansion(entries: &mut Vec<(Vec<char>, Vec<u64>)>, target: &[char], anchor: &[char]) {
        let forms = [
            (target.to_vec(), anchor.to_vec()),
            (
                target.iter().map(|&c| upper(c)).collect::<Vec<_>>(),
                anchor.iter().map(|&c| upper(c)).collect::<Vec<_>>(),
            ),
        ];
        for (t_form, a_form) in forms {
            let seq: Vec<char> = nfd(t_form.into_iter()).collect();
            let ces = collation_elements(nfd(a_form.into_iter()).collect());
            if !seq.is_empty() && !ces.is_empty() {
                entries.push((seq, ces));
            }
        }
    }

    fn match_at(&self, rest: &[char]) -> Option<(usize, &[u64])> {
        for (seq, ces) in &self.entries {
            if rest.len() >= seq.len() && rest[..seq.len()] == seq[..] {
                return Some((seq.len(), ces));
            }
        }
        None
    }

    /// The tailored sort key for `s`.
    #[must_use]
    pub fn sort_key(&self, s: &str) -> Vec<u16> {
        let cv: Vec<char> = nfd(s.chars()).collect();
        let mut cea = Vec::new();
        let mut buf: Vec<char> = Vec::new();
        let mut i = 0;
        while i < cv.len() {
            // zh collation: a Han ideograph with a rank in the active table
            // (pinyin / stroke / zhuyin) is weighted by that rank instead of its
            // DUCET implicit weight. Tailoring entries (tone vowels) are matched
            // first; non-Han and unlisted ideographs fall through to the buffered
            // DUCET path.
            #[cfg(feature = "collation-zh")]
            if let Some(table) = self.han
                && self.match_at(&cv[i..]).is_none()
            {
                let cp = cv[i] as u32;
                // Every Han ideograph is placed in the reordered Han band — a
                // fixed marker base `ZH_HAN_BASE`, between the DUCET digit and
                // Latin weights (`[reorder Hani]`: digits < Han < Latin) — followed
                // by an ordering key that rides a *second primary* (16 bits, vs the
                // tailoring sub-weight's 15 — too narrow for ranks up to ~44k):
                //   • a listed ideograph → its rank in the active table (ICU/V8);
                //   • an unlisted ideograph with a Unihan radical-stroke key →
                //     the `ZH_RS_MARKER` band (above every pinyin rank, below the
                //     DUCET implicit weight), then radical, residual strokes and
                //     code point as successive ordering primaries — true ICU/V8
                //     radical-stroke order for the Extensions;
                //   • an unlisted ideograph with no radical-stroke key → its DUCET
                //     implicit weights, whose `AAAA` (≈0xFB40) exceeds the marker,
                //     so it sorts after the radical-stroke chars yet before Latin.
                // Non-Han falls through to the buffered root (DUCET) path.
                //
                // In `unihan` mode the ranked (pinyin/stroke/zhuyin) lookup is
                // skipped entirely, so every Han takes the radical-stroke branch
                // (or the DUCET implicit tail for the rare RS-less ideograph).
                let ranked = if self.han_unihan {
                    None
                } else {
                    zh_ranked(table, cp)
                };
                if let Some(rank) = ranked {
                    if !buf.is_empty() {
                        cea.extend(collation_elements(core::mem::take(&mut buf)));
                    }
                    cea.push(pack(ZH_HAN_BASE, 0x0020, 0x0002));
                    cea.push(pack(rank as u32, 0x0000, 0x0000));
                    i += 1;
                    continue;
                } else if let Some(packed) = zh_rs_key(cp) {
                    if !buf.is_empty() {
                        cea.extend(collation_elements(core::mem::take(&mut buf)));
                    }
                    // Unpack `radical << 8 | (residual+16) << 1 | simplified`: the
                    // radical is one ordering primary, the residual+simplified low
                    // byte the next (residual dominates, the simplified-variant bit
                    // breaks a residual tie). Both are non-zero.
                    let radical_key = (packed >> 8) as u32;
                    let resid = (packed & 0xFF) as u32;
                    cea.push(pack(ZH_HAN_BASE, 0x0020, 0x0002));
                    cea.push(pack(ZH_RS_MARKER, 0x0000, 0x0000));
                    cea.push(pack(radical_key, 0x0000, 0x0000));
                    cea.push(pack(resid, 0x0000, 0x0000));
                    // Final tie-break for chars sharing (radical, residual): the
                    // DUCET *implicit* primaries, whose `AAAA` puts the URO block
                    // (0xFB40) before the Extension blocks (0xFB80) — matching V8,
                    // which groups URO ahead of Ext-A/B at equal radical-stroke
                    // (raw code point would wrongly float Ext-A, at U+34xx, first).
                    // `BBBB` carries the code point within a block.
                    let (aaaa, bbbb) = implicit_primaries(cp);
                    cea.push(pack(aaaa, 0x0000, 0x0000));
                    cea.push(pack(bbbb, 0x0000, 0x0000));
                    i += 1;
                    continue;
                } else if tables::unified_ideograph(cp) {
                    if !buf.is_empty() {
                        cea.extend(collation_elements(core::mem::take(&mut buf)));
                    }
                    let (aaaa, bbbb) = implicit_primaries(cp);
                    cea.push(pack(ZH_HAN_BASE, 0x0020, 0x0002));
                    cea.push(pack(aaaa, 0x0000, 0x0000));
                    cea.push(pack(bbbb, 0x0000, 0x0000));
                    i += 1;
                    continue;
                }
            }
            if let Some((len, ces)) = self.match_at(&cv[i..]) {
                if !buf.is_empty() {
                    cea.extend(collation_elements(core::mem::take(&mut buf)));
                }
                cea.extend_from_slice(ces);
                i += len;
            } else {
                buf.push(cv[i]);
                i += 1;
            }
        }
        if !buf.is_empty() {
            cea.extend(collation_elements(buf));
        }
        build_tailored_sort_key(&cea, self.reorder.as_ref())
    }

    /// Compare two strings in this tailored order.
    #[must_use]
    pub fn compare(&self, a: &str, b: &str) -> Ordering {
        self.sort_key(a).cmp(&self.sort_key(b))
    }

    /// An empty tailoring (DUCET root order), whose [`sort_key`](Self::sort_key)
    /// uses the same pair-encoded primary level as any other tailoring — so the
    /// alphabetic index can treat root and tailored locales uniformly.
    #[must_use]
    pub fn identity() -> Tailoring {
        Tailoring {
            entries: Vec::new(),
            reorder: None,
            #[cfg(feature = "collation-zh")]
            han: None,
            #[cfg(feature = "collation-zh")]
            han_unihan: false,
        }
    }

    /// The Chinese (`zh`) collator for a ranked Han-weight `table` — pinyin
    /// ([`ZH_PINYIN`], the default `Intl.Collator('zh')` order), stroke
    /// ([`ZH_STROKE`], `zh-u-co-stroke`), or zhuyin ([`ZH_ZHUYIN`],
    /// `zh-u-co-zhuyin`). Han ideographs are weighted by their rank in `table`,
    /// placed — per `[reorder Hani]` — after digits and before Latin and other
    /// scripts; ideographs absent from `table` fall to Unihan radical-stroke
    /// order; non-Han uses the root (DUCET) order.
    ///
    /// The tone-marked romanization vowels (`ā á ǎ à` …) are ordered as secondary
    /// variants of their base vowel (CLDR `private-pinyin`), so romanized pinyin
    /// also sorts sensibly.
    ///
    /// Private — reached via [`Tailoring::for_locale`]`("zh")` so no public API is
    /// added by the `collation-zh` feature.
    #[cfg(feature = "collation-zh")]
    fn zh(table: &'static [u8]) -> Tailoring {
        // CLDR zh `private-pinyin`: tone-marked vowels as secondary/tertiary of
        // their base (affects romanized-pinyin Latin text only, never Han).
        const TONES: &str = "\
            &[before 2]a<<ā<<<Ā<<á<<<Á<<ǎ<<<Ǎ<<à<<<À \
            &[before 2]e<<ē<<<Ē<<é<<<É<<ě<<<Ě<<è<<<È \
            &[before 2]i<<ī<<<Ī<<í<<<Í<<ǐ<<<Ǐ<<ì<<<Ì \
            &[before 2]o<<ō<<<Ō<<ó<<<Ó<<ǒ<<<Ǒ<<ò<<<Ò \
            &[before 2]u<<ū<<<Ū<<ú<<<Ú<<ǔ<<<Ǔ<<ù<<<Ù \
            &U<<ǖ<<<Ǖ<<ǘ<<<Ǘ<<ǚ<<<Ǚ<<ǜ<<<Ǜ<<ü<<<Ü";
        let mut t = Tailoring::parse(TONES).unwrap_or_else(Tailoring::identity);
        t.han = Some(table);
        t
    }

    /// The Chinese `unihan` collator (`zh-u-co-unihan`): every Han ideograph is
    /// ordered purely by Unihan **radical-stroke** (radical number, then residual
    /// strokes, then code point) — the pinyin/stroke/zhuyin readings are ignored.
    /// Placed, per `[reorder Hani]`, after digits and before Latin; non-Han uses
    /// the root (DUCET) order. The tone-marked romanization vowels are still
    /// tailored (harmless for the Han-only `unihan` order, consistent with `zh`).
    ///
    /// Private — reached via [`Tailoring::for_locale`]`("zh-u-co-unihan")`.
    #[cfg(feature = "collation-zh")]
    fn zh_unihan() -> Tailoring {
        // `han` must be `Some` so the Han path in `sort_key` fires; the table
        // itself is never consulted in `unihan` mode (the ranked lookup is
        // skipped), so any zh table serves as the gate.
        let mut t = Tailoring::zh(ZH_PINYIN);
        t.han_unihan = true;
        t
    }
}

/// Build a tailored sort key (UCA `Shifted`, tertiary strength) whose **primary
/// level emits a `(base, sub)` pair per element** — `sub` is the tailoring
/// sub-weight (0 for plain DUCET letters). This places a tailored letter
/// immediately after its anchor and after every word that merely *starts* with
/// the anchor, with no bound on how many letters share one anchor.
fn build_tailored_sort_key(cea: &[u64], reorder: Option<&Reorder>) -> Vec<u16> {
    let mut rows: Vec<(u16, u16, u16, u16, u16)> = Vec::with_capacity(cea.len());
    let mut after_variable = false;
    for &ce in cea {
        let (p, sub, s, t) = (primary(ce), sub_weight(ce), secondary(ce), tertiary(ce));
        if is_variable(ce) && p != 0 {
            rows.push((0, 0, 0, 0, p)); // shifted to the quaternary level
            after_variable = true;
        } else if p == 0 && s == 0 && t == 0 {
            rows.push((0, 0, 0, 0, 0)); // completely ignorable
        } else if p == 0 {
            if after_variable {
                rows.push((0, 0, 0, 0, 0));
            } else {
                rows.push((0, 0, s, t, 0xFFFF));
            }
        } else {
            rows.push((p, sub, s, t, 0xFFFF));
            after_variable = false;
        }
    }
    let mut key = Vec::new();
    for &(p, sub, ..) in &rows {
        if p != 0 {
            // `[reorder …]`: prepend the primary's reorder-group rank so whole
            // scripts move as a block (listed groups first, then others in DUCET
            // order) while the original primary still orders *within* a group.
            if let Some(r) = reorder {
                key.push(r.rank(p));
            }
            key.push(p);
            // A plain DUCET letter (`sub == 0`) sits at the midpoint, so tailored
            // letters can be inserted just below (`[before]`) or above it.
            key.push(if sub == 0 { SUB_MID } else { sub });
        }
    }
    key.push(0);
    for &(_, _, s, ..) in &rows {
        if s != 0 {
            key.push(s);
        }
    }
    key.push(0);
    for &(_, _, _, t, _) in &rows {
        if t != 0 {
            key.push(t);
        }
    }
    key.push(0);
    for &(.., q) in &rows {
        if q != 0 {
            key.push(q);
        }
    }
    key
}

/// A parsed CLDR `[reorder …]` group code.
enum ReorderCode {
    /// A script group (`Cyrl` → [`Script::Cyrillic`]).
    Script(super::script::Script),
    /// The `others`/`Zzzz` placeholder — where unlisted groups sort.
    Others,
    /// A special low group (`space`/`punct`/`symbol`/`currency`/`digit`). These
    /// live below every script; we keep them in their default (front) position
    /// and do not model reordering *among* them (a documented approximation —
    /// no bundled locale needs it). Parsed so such codes don't defeat the rule.
    Special,
}

impl ReorderCode {
    fn parse(tag: &str) -> Option<ReorderCode> {
        match tag.to_ascii_lowercase().as_str() {
            "space" | "punct" | "symbol" | "currency" | "digit" => Some(ReorderCode::Special),
            "others" | "zzzz" => Some(ReorderCode::Others),
            _ => script_from_tag(tag).map(ReorderCode::Script),
        }
    }
}

/// Map an ISO 15924 script tag (`Cyrl`, `Latn`, …) to a [`Script`]. Covers the
/// tags that appear in CLDR collation `[reorder]` rules; others return `None`.
fn script_from_tag(tag: &str) -> Option<super::script::Script> {
    use super::script::Script::*;
    // Normalize to `Titlecase` (`cyrl`/`CYRL` → `Cyrl`).
    let mut norm = String::new();
    for (i, c) in tag.chars().enumerate() {
        if i == 0 {
            norm.push(c.to_ascii_uppercase());
        } else {
            norm.push(c.to_ascii_lowercase());
        }
    }
    Some(match norm.as_str() {
        "Cyrl" => Cyrillic,
        "Latn" => Latin,
        "Grek" => Greek,
        "Arab" => Arabic,
        "Hani" => Han,
        "Hebr" => Hebrew,
        "Armn" => Armenian,
        "Geor" => Georgian,
        "Ethi" => Ethiopic,
        "Cher" => Cherokee,
        "Deva" => Devanagari,
        "Beng" => Bengali,
        "Guru" => Gurmukhi,
        "Gujr" => Gujarati,
        "Orya" => Oriya,
        "Taml" => Tamil,
        "Telu" => Telugu,
        "Knda" => Kannada,
        "Mlym" => Malayalam,
        "Sinh" => Sinhala,
        "Tibt" => Tibetan,
        "Thai" => Thai,
        "Laoo" => Lao,
        "Khmr" => Khmer,
        "Mymr" => Myanmar,
        "Hang" => Hangul,
        "Bopo" => Bopomofo,
        "Kana" => Katakana,
        "Mong" => Mongolian,
        _ => return None,
    })
}

/// The first non-zero DUCET primary weight of code point `cp`, or `0` if it has
/// none (fully ignorable). Used to derive a script's primary range from the
/// DUCET at [`Reorder::build`] time. Avoids allocating for the common
/// single-mapping case; decomposing/implicit code points take the full path.
fn char_primary(cp: u32) -> u16 {
    if let Some(ces) = tables::ce_singles(cp) {
        for &ce in ces {
            let p = primary(ce);
            if p != 0 {
                return p;
            }
        }
        return 0;
    }
    let Some(c) = char::from_u32(cp) else {
        return 0;
    };
    for ce in collation_elements(nfd(core::iter::once(c)).collect()) {
        let p = primary(ce);
        if p != 0 {
            return p;
        }
    }
    0
}

/// A script `[reorder …]` mapping, resolved to primary-weight ranges. Reordering
/// moves whole scripts by remapping the **primary rank** in the sort key: each
/// primary is classified into a reorder group and the group's rank is emitted
/// before the primary, so groups sort by rank and characters within a group keep
/// their DUCET primary order.
///
/// Groups and ranks: rank `0` is the low region — every space/punctuation/
/// symbol/currency/digit primary, i.e. everything below the first script letter
/// (`script_start`). It always sorts first (matching ICU/V8: digits and
/// punctuation precede the reordered scripts). Each **listed** script group gets
/// a rank `≥ 1` in list order; every unlisted script (and the implicit CJK
/// range) gets `others_rank`, sorting after the listed ones in DUCET order.
struct Reorder {
    /// The lowest primary of any script letter (DUCET primary of `'a'`).
    /// Primaries below this are the low region (rank 0).
    script_start: u16,
    /// `(lo, hi, rank)` per listed script, from the DUCET; ranges are disjoint.
    groups: Vec<(u16, u16, u16)>,
    /// Rank for scripts not explicitly listed (the `others` slot).
    others_rank: u16,
}

impl Reorder {
    /// Build the mapping from parsed reorder codes, deriving each listed script's
    /// primary range from the DUCET. Returns `None` if no script group is listed
    /// (a `[reorder]` of only special groups / `others` is treated as a no-op).
    fn build(codes: &[ReorderCode]) -> Option<Reorder> {
        // Assign ranks: listed scripts take slots 1,2,…; `others` reserves the
        // slot where unlisted groups sort; special groups take no script slot.
        let mut scripts: Vec<(super::script::Script, u16)> = Vec::new();
        let mut idx = 1u16;
        let mut others_rank: Option<u16> = None;
        for c in codes {
            match c {
                ReorderCode::Script(s) => {
                    scripts.push((*s, idx));
                    idx += 1;
                }
                ReorderCode::Others => {
                    if others_rank.is_none() {
                        others_rank = Some(idx);
                        idx += 1;
                    }
                }
                ReorderCode::Special => {}
            }
        }
        if scripts.is_empty() {
            return None;
        }
        let others_rank = others_rank.unwrap_or(idx);
        let script_start = char_primary('a' as u32);

        // Derive each listed script's primary range by scanning the BMP: for each
        // code point of a listed script, fold its (letter) primary into that
        // group's [lo, hi]. Only primaries ≥ `script_start` count, so a script's
        // own low-region punctuation (e.g. the Arabic comma) is excluded and the
        // range stays a clean letter band. Supplementary-plane scripts are not
        // scanned (none of the reorder-only locales need them).
        let mut groups: Vec<(u16, u16, u16)> =
            scripts.iter().map(|&(_, r)| (u16::MAX, 0u16, r)).collect();
        for cp in 0u32..0x1_0000 {
            let sc = super::script::script_u32(cp);
            let Some(pos) = scripts.iter().position(|&(s, _)| s == sc) else {
                continue;
            };
            let pr = char_primary(cp);
            if pr < script_start {
                continue;
            }
            let g = &mut groups[pos];
            if pr < g.0 {
                g.0 = pr;
            }
            if pr > g.1 {
                g.1 = pr;
            }
        }
        // Drop groups whose script had no letter in the scanned range.
        groups.retain(|&(lo, hi, _)| lo <= hi);
        if groups.is_empty() {
            return None;
        }
        Some(Reorder {
            script_start,
            groups,
            others_rank,
        })
    }

    /// The reorder-group rank of primary weight `p` (see [`Reorder`]).
    fn rank(&self, p: u16) -> u16 {
        if p < self.script_start {
            return 0;
        }
        for &(lo, hi, r) in &self.groups {
            if p >= lo && p <= hi {
                return r;
            }
        }
        self.others_rank
    }
}

/// The upper-case form of `c` (first char of its full mapping), or `c` itself.
fn upper(c: char) -> char {
    super::case::to_uppercase(c).next().unwrap_or(c)
}

/// A lexical token of a CLDR tailoring rule (see [`Tailoring::parse`]).
enum Tok {
    /// `&` — reset.
    Amp,
    /// A relation: `0` = `=` (identity), `1` = `<`, `2` = `<<`, `3` = `<<<`.
    Rel(u8),
    /// The `*` immediately following a relation (`<*`, `<<*`, `=*`): the target
    /// run is a character list, each related to the previous.
    Star,
    /// The `/` after a relation target introduces an **expansion** string
    /// (`Y/Z` — `Y` collates as its own weight followed by the weights of `Z`).
    Slash,
    /// A literal character (letter, or a quoted/escaped operator character).
    Lit(char),
    /// `[before N]` preceding a reset anchor.
    Before(u8),
    /// `[import <locale>]`.
    Import(String),
    /// `[reorder <code> <code> …]` — the whitespace-split group codes (script
    /// tags like `Cyrl`, or special groups `space`/`punct`/`digit`/`others`).
    Reorder(Vec<String>),
}

/// Read `n` hex digits from `chars[start..]` into a code point.
fn parse_hex(chars: &[char], start: usize, n: usize) -> Option<u32> {
    if start + n > chars.len() {
        return None;
    }
    let s: String = chars[start..start + n].iter().collect();
    u32::from_str_radix(&s, 16).ok()
}

/// Tokenize a CLDR tailoring rule string: strips `#` comments and whitespace,
/// resolves `\uXXXX`/`\UXXXXXXXX` escapes and `'…'`/`''` quoting, recognizes the
/// relation operators and their `*` range form, and classifies `[…]` brackets
/// into `[before N]`, `[import …]`, or ignored options.
fn lex(rules: &str) -> Option<Vec<Tok>> {
    let chars: Vec<char> = rules.chars().collect();
    let mut out = Vec::new();
    let mut i = 0;
    while i < chars.len() {
        let c = chars[i];
        match c {
            '#' => {
                while i < chars.len() && chars[i] != '\n' {
                    i += 1;
                }
            }
            _ if c.is_whitespace() => i += 1,
            // Expansion: `&A <<< Y/Z` makes `Y` collate as its relation to `A`
            // followed by an expansion of `Z` (Hungarian gemination: `ccs` = the
            // doubled `cs`). Emitted as a token so the walker can read `Z`.
            '/' => {
                out.push(Tok::Slash);
                i += 1;
            }
            // Prefix context (`x|y`) carries ordering we don't model; treat as a
            // separator so neither side merges into a neighbor.
            '|' => i += 1,
            '\'' => {
                i += 1;
                if i < chars.len() && chars[i] == '\'' {
                    out.push(Tok::Lit('\'')); // `''` = a literal apostrophe
                    i += 1;
                } else {
                    while i < chars.len() && chars[i] != '\'' {
                        out.push(Tok::Lit(chars[i]));
                        i += 1;
                    }
                    if i < chars.len() {
                        i += 1; // closing quote
                    }
                }
            }
            '\\' => {
                i += 1;
                let Some(&e) = chars.get(i) else { break };
                match e {
                    'u' => {
                        out.push(Tok::Lit(char::from_u32(parse_hex(&chars, i + 1, 4)?)?));
                        i += 5;
                    }
                    'U' => {
                        out.push(Tok::Lit(char::from_u32(parse_hex(&chars, i + 1, 8)?)?));
                        i += 9;
                    }
                    other => {
                        out.push(Tok::Lit(other)); // `\-`, `\!`, … → literal
                        i += 1;
                    }
                }
            }
            '[' => {
                // Read a bracketed option, honoring nested `[…]` (e.g. the range
                // list in `[optimize [가-…]]`).
                let start = i + 1;
                let mut depth = 1;
                i += 1;
                while i < chars.len() && depth > 0 {
                    match chars[i] {
                        '[' => depth += 1,
                        ']' => depth -= 1,
                        _ => {}
                    }
                    if depth > 0 {
                        i += 1;
                    }
                }
                let content: String = chars[start..i].iter().collect();
                if i < chars.len() {
                    i += 1; // closing `]`
                }
                let content = content.trim();
                if let Some(rest) = content.strip_prefix("before") {
                    let lvl = rest
                        .trim()
                        .chars()
                        .next()
                        .and_then(|d| d.to_digit(10))
                        .unwrap_or(1) as u8;
                    out.push(Tok::Before(lvl.clamp(1, 3)));
                } else if let Some(rest) = content.strip_prefix("import") {
                    out.push(Tok::Import(rest.trim().to_string()));
                } else if let Some(rest) = content.strip_prefix("reorder") {
                    let codes: Vec<String> =
                        rest.split_whitespace().map(ToString::to_string).collect();
                    if !codes.is_empty() {
                        out.push(Tok::Reorder(codes));
                    }
                }
                // Else an ordering-free option (normalization / caseFirst /
                // suppressContractions / optimize / …): ignored.
            }
            '&' => {
                out.push(Tok::Amp);
                i += 1;
            }
            '=' => {
                out.push(Tok::Rel(0));
                i += 1;
                if i < chars.len() && chars[i] == '*' {
                    out.push(Tok::Star);
                    i += 1;
                }
            }
            '<' => {
                let mut n = 0u8;
                while i < chars.len() && chars[i] == '<' {
                    n = n.saturating_add(1);
                    i += 1;
                }
                out.push(Tok::Rel(n.min(3)));
                if i < chars.len() && chars[i] == '*' {
                    out.push(Tok::Star);
                    i += 1;
                }
            }
            other => {
                out.push(Tok::Lit(other));
                i += 1;
            }
        }
    }
    Some(out)
}

/// Resolve an `[import <locale>]` target to a bundled rule string. Accepts a bare
/// locale (`es`) or a BCP-47 collation tag (`da-u-co-standard`); only the
/// `standard` collation is bundled, so private/other `-u-co-*` types (e.g. the
/// Japanese `ja-u-co-private-kana`) resolve to `None` and are skipped.
fn import_rule(loc: &str) -> Option<&'static str> {
    let full = loc.replace('_', "-").to_ascii_lowercase();
    if let Some(idx) = full.find("-u-co-") {
        if &full[idx + 6..] != "standard" {
            return None;
        }
        return crate::cldr::collation_rule(&full[..idx]);
    }
    crate::cldr::collation_rule(&full)
}

/// Resolve an `[import <locale>]` target that has no bundled rule string to its
/// hand-written fallback tailoring (e.g. `hr`). Strips a `-u-co-standard` suffix.
fn import_tailoring(loc: &str) -> Option<Tailoring> {
    let full = loc.replace('_', "-").to_ascii_lowercase();
    let base = match full.find("-u-co-") {
        Some(idx) if &full[idx + 6..] == "standard" => full[..idx].to_string(),
        Some(_) => return None,
        None => full,
    };
    Tailoring::for_locale(&base)
}

#[cfg(test)]
mod dos_fix_tests {
    use super::*;
    use alloc::string::String;

    /// Reference implementation of `find`: the original O(n^2) algorithm, kept
    /// here verbatim so the fast `find` can be checked against it for byte-for-
    /// byte identical results.
    fn find_reference(text: &str, pattern: &str) -> Option<core::ops::Range<usize>> {
        let pat = primaries(pattern);
        if pat.is_empty() {
            return Some(0..0);
        }
        let bounds: Vec<usize> = text
            .char_indices()
            .map(|(i, _)| i)
            .chain(core::iter::once(text.len()))
            .collect();
        for a in 0..bounds.len() - 1 {
            for b in a + 1..bounds.len() {
                let pr = primaries(&text[bounds[a]..bounds[b]]);
                if pr.len() < pat.len() {
                    continue;
                }
                if pr == pat {
                    return Some(bounds[a]..bounds[b]);
                }
                break;
            }
        }
        None
    }

    /// Reference (pre-fix) collation-element generator, using `Vec::remove`, to
    /// confirm the bitmask rewrite is byte-identical.
    fn collation_elements_reference(mut cv: Vec<char>) -> Vec<u64> {
        let mut cea = Vec::new();
        let mut i = 0;
        while i < cv.len() {
            let s0 = cv[i] as u32;
            let mut end = i + 1;
            let mut matched: Option<&'static [u64]> = tables::ce_singles(s0);
            let mut suffix: Vec<char> = Vec::new();
            if let Some(entries) = tables::contractions(s0) {
                for (suf, ces) in entries {
                    let stop = i + 1 + suf.len();
                    if stop <= cv.len() && cv[i + 1..stop] == **suf {
                        matched = Some(ces);
                        suffix = suf.to_vec();
                        end = stop;
                        break;
                    }
                }
            }
            loop {
                let mut last_ccc = 0u8;
                let mut j = end;
                let mut hit = None;
                while j < cv.len() {
                    let cc = ccc(cv[j]);
                    if cc == 0 {
                        break;
                    }
                    if last_ccc < cc {
                        let mut trial = suffix.clone();
                        trial.push(cv[j]);
                        if let Some(ces) = lookup_contraction(s0, &trial) {
                            hit = Some((j, ces, trial));
                            break;
                        }
                        last_ccc = cc;
                    } else {
                        break;
                    }
                    j += 1;
                }
                match hit {
                    Some((j, ces, trial)) => {
                        matched = Some(ces);
                        suffix = trial;
                        cv.remove(j);
                    }
                    None => break,
                }
            }
            match matched {
                Some(ces) => cea.extend_from_slice(ces),
                None => push_implicit(s0, &mut cea),
            }
            i = end;
        }
        cea
    }

    // Tiny deterministic PRNG (xorshift) — no external deps.
    struct Rng(u64);
    impl Rng {
        fn next(&mut self) -> u64 {
            let mut x = self.0;
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            self.0 = x;
            x
        }
        fn pick<'a, T>(&mut self, xs: &'a [T]) -> &'a T {
            &xs[(self.next() as usize) % xs.len()]
        }
    }

    /// Characters chosen to exercise contractions (`l·`, `ch`), discontiguous
    /// non-starters (combining marks of varying ccc), expansions, CJK (implicit
    /// weights), digits, and ASCII.
    const ALPHABET: &[char] = &[
        'a', 'b', 'c', 'e', 'h', 'l', 'z', 'A', 'C', 'H', 'L', 'ñ', 'Ñ', 'å', 'Ç', 'ç', '·',
        '\u{0301}', '\u{0300}', '\u{0327}', '\u{0323}', '\u{0308}', 'é', 'É', '0', '1', '2', '中',
        ' ', '!', '\u{00C6}', '\u{0153}',
    ];

    fn random_string(rng: &mut Rng, len: usize) -> String {
        (0..len).map(|_| *rng.pick(ALPHABET)).collect()
    }

    #[test]
    fn find_matches_reference_fuzz() {
        let mut rng = Rng(0x9E3779B97F4A7C15);
        for _ in 0..4000 {
            let tlen = (rng.next() as usize) % 14;
            let plen = 1 + (rng.next() as usize) % 4;
            let text = random_string(&mut rng, tlen);
            let pat = random_string(&mut rng, plen);
            assert_eq!(
                find(&text, &pat),
                find_reference(&text, &pat),
                "find mismatch: text={text:?} pat={pat:?}"
            );
        }
        // A few hand-picked structural cases.
        for (t, p) in [
            ("l·a", "la"),
            ("L·", "l"),
            ("e\u{0301}", "e"),
            ("\u{0301}e", "e"),
            ("  café", "cafe"),
            ("ñ", "n"),
            ("中文", "中"),
            ("aaa", "aa"),
            ("", "x"),
            ("x", ""),
        ] {
            assert_eq!(
                find(t, p),
                find_reference(t, p),
                "case text={t:?} pat={p:?}"
            );
        }
    }

    #[test]
    fn collation_elements_matches_reference_fuzz() {
        let mut rng = Rng(0xD1B54A32D192ED03);
        for _ in 0..4000 {
            let len = (rng.next() as usize) % 16;
            let s = random_string(&mut rng, len);
            let cv: Vec<char> = nfd(s.chars()).collect();
            assert_eq!(
                collation_elements(cv.clone()),
                collation_elements_reference(cv),
                "CE mismatch: s={s:?}"
            );
        }
    }

    #[test]
    fn perf_smoke_large_nonmatching_find() {
        // Previously O(n^2): a few hundred KB of non-matching text. Must finish
        // quickly (this test would hang for seconds before the fix).
        let text: String = "a".repeat(300_000);
        assert_eq!(find(&text, "qzx"), None);
        assert_eq!(find(&text, "aaa"), Some(0..3));
    }

    #[test]
    fn perf_smoke_long_combining_run() {
        // Previously O(n^2) in `collation_elements` via `Vec::remove`: a long run
        // of combining marks after a starter.
        let mut s = String::from("e");
        for _ in 0..200_000 {
            s.push('\u{0301}');
        }
        let key = sort_key(&s);
        assert!(!key.is_empty());
        // `find` over the same pathological input must also stay fast.
        assert_eq!(find(&s, "z"), None);
    }

    #[test]
    fn perf_smoke_unaligned_start_zero_primary_tail() {
        // The `window_decision` quadratic: `l·` forms the Catalan middle-dot
        // contraction, making `·` an *unaligned* (mid-contraction) start, and the
        // long acute-accent run after it is a zero-primary tail. Before the fix,
        // the unaligned start re-collated growing prefixes to the end of the
        // string — O(n^2): ~29s at 128 KB. After the fix it is linear; this test
        // simply completing quickly proves termination/linearity.
        let big: String = {
            let mut s = String::from("l\u{00B7}");
            for _ in 0..50_000 {
                s.push('\u{0301}');
            }
            s
        };
        // Tiny reference input with the same structure (no long tail).
        let small = "l\u{00B7}\u{0301}";
        // "zz" is not present at primary strength → both must be `None`, and the
        // big input must agree with the small one (and with the O(n^2) reference).
        assert_eq!(find(&big, "zz"), None);
        assert_eq!(find(small, "zz"), find_reference(small, "zz"));
        assert_eq!(find(&big, "zz"), find_reference(small, "zz"));
        // Sanity: a pattern that *is* present is still found in the big input.
        assert_eq!(find(&big, "l"), Some(0..1));
    }

    #[test]
    fn perf_smoke_repeated_contraction_nonmatching() {
        // The remaining `find`/`contains` quadratic: a *repeated* contraction.
        // Every `·` of the Catalan `l·` middle-dot contraction is an unaligned
        // (mid-contraction) start, so `find` falls back to `window_decision` at
        // each one. Before this fix each fallback NFD-expanded the whole O(n)
        // remaining suffix and allocated a `consumed` bitmask of that length
        // *before* the early `Walk::Stop` could bound the walk — so `m` such
        // starts over O(n) suffixes were O(n·m) ≈ O(n^2). Measured release:
        // 60 KB → 11 s, 120 KB → 62 s. After the fix each fallback's setup is
        // bounded to the deciding prefix (proportional to `need`), so this large
        // input completes near-instantly; the test would hang under the old code.
        let n = 50_000;
        let big: String = "l\u{00B7}".repeat(n); // ~150 KB
        // "zz" never matches at primary strength → full scan over every start.
        assert_eq!(find(&big, "zz"), None);
        assert!(!contains(&big, "zz"));
        // Correctness against the O(n^2) reference on a small same-structure input.
        let small = "l\u{00B7}l\u{00B7}l\u{00B7}";
        assert_eq!(find(small, "zz"), find_reference(small, "zz"));
        assert_eq!(find(&big, "zz"), find_reference(small, "zz"));
        // A present pattern is still found at the expected (leftmost) offset.
        assert_eq!(find(&big, "l"), Some(0..1));
        assert!(contains(&big, "l"));
    }
}