catalogue/comparison/sort_key

fn table() -> &'static Table {
    static TABLE: OnceLock<Table> = OnceLock::new();
    TABLE.get_or_init(build)
}

/// The bytes of a base64 text (the generated tables' encoding).
fn decode64(text: &str) -> Vec<u8> {
    let mut data = Vec::with_capacity(text.len() / 4 * 3);
    let (mut bits, mut count) = (0u32, 0);
    for byte in text.bytes() {
        let value = match byte {
            b'A'..=b'Z' => byte - b'A',
            b'a'..=b'z' => byte - b'a' + 26,
            b'0'..=b'9' => byte - b'0' + 52,
            b'+' => 62,
            b'/' => 63,
            _ => continue,
        };
        bits = (bits << 6) | u32::from(value);
        count += 6;
        if count >= 8 {
            count -= 8;
            data.push((bits >> count) as u8);
        }
    }
    data
}

fn byte(&mut self) -> u8 {
    let byte = self.data[self.at];
    self.at += 1;
    byte
}

fn varint(&mut self) -> u64 {
    let (mut value, mut shift) = (0u64, 0);
    loop {
        let byte = self.byte();
        value |= u64::from(byte & 0x7F) << shift;
        if byte & 0x80 == 0 {
            return value;
        }
        shift += 7;
    }
}

fn done(&self) -> bool {
    self.at >= self.data.len()
}

fn in_ranges(code: u16, ranges: &[(u16, u16)]) -> bool {
    ranges.iter().any(|&(a, b)| (a..=b).contains(&code))
}

fn build() -> Table {
    // The Unicode data.
    let mut roots: HashMap<u16, Root> = HashMap::new();
    let mut reader = Reader {
        data: decode64(UNITS),
        at: 0,
    };
    let mut code = 0u16;
    while !reader.done() {
        code += reader.varint() as u16;
        let flags = reader.byte();
        let count = reader.varint() as usize;
        let primaries: Vec<u64> = (0..count).map(|_| reader.varint()).collect();
        let secondaries: Vec<Vec<u32>> = (0..=count)
            .map(|_| {
                let n = reader.varint() as usize;
                (0..n).map(|_| reader.varint() as u32).collect()
            })
            .collect();
        roots.insert(
            code,
            Root {
                flags,
                primaries,
                secondaries,
            },
        );
    }
    // The measured exceptions.
    let mut exceptions: HashMap<u16, Exception> = HashMap::new();
    let mut reader = Reader {
        data: decode64(EXCEPTIONS),
        at: 0,
    };
    let mut code = 0u16;
    while !reader.done() {
        code += reader.varint() as u16;
        let exception = match reader.byte() {
            0 => Exception::Ignorable,
            1 => Exception::Refused,
            2 => Exception::Mark(reader.byte()),
            3 => Exception::Special([reader.byte(), reader.byte()]),
            5 => {
                let whole = reader.byte() == 1;
                let n = reader.varint() as usize;
                Exception::Expansion((0..n).map(|_| reader.varint() as u16).collect(), whole)
            }
            6 => Exception::Iteration(Iteration {
                vowel: reader.byte() == 1,
                diacritic: reader.byte(),
                iteration: reader.byte(),
                width: match reader.byte() {
                    0 => None,
                    _ => Some(reader.byte()),
                },
            }),
            _ => {
                let n = reader.varint() as usize;
                let primaries = (0..n).map(|_| reader.varint()).collect();
                let n = reader.varint() as usize;
                let diacritic = (0..n).map(|_| reader.byte()).collect();
                let n = reader.varint() as usize;
                let case = (0..n).map(|_| reader.byte()).collect();
                let kana = match reader.byte() {
                    0 => None,
                    _ => Some([reader.byte(), reader.byte(), reader.byte()]),
                };
                Exception::Weighted {
                    primaries,
                    diacritic,
                    case,
                    kana,
                }
            }
        };
        exceptions.insert(code, exception);
    }
    let placed: HashMap<u64, (u64, u8)> = PLACED.iter().map(|&(t, a, s)| (t, (a, s))).collect();
    let secondary: HashMap<u32, u8> = SECONDARY.iter().copied().collect();
    let special: HashMap<u16, [u8; 2]> = SPECIAL.iter().copied().collect();

    // A primary's ten key bytes and its length in Windows' keys.
    let slot = |token: u64| -> Slot {
        let (group, anchor, sub) = if token >= EXTRA_KIND {
            let (group, anchor, sub) = EXTRA[(token - EXTRA_KIND) as usize];
            (group, anchor, sub)
        } else {
            let at = GROUPS.partition_point(|&(start, _)| start <= token);
            let group = GROUPS[at.max(1) - 1].1;
            let (anchor, sub) = placed.get(&token).copied().unwrap_or((token, 0));
            (group, anchor, sub)
        };
        let mut bytes = [0u8; PRIMARY_BYTES];
        bytes[0] = group;
        bytes[1..9].copy_from_slice(&anchor.to_be_bytes());
        bytes[9] = sub;
        let length = match group {
            0xFD => 4,
            0xA9 => 3,
            _ => 2,
        };
        (bytes, length)
    };

    let mut table = Table {
        weights: Vec::with_capacity(0x10000),
        primary: Vec::new(),
        diacritic: Vec::new(),
        case: Vec::new(),
        expansions: Vec::new(),
        repeat: REPEAT.iter().map(|&(a, b, t)| (a, b, slot(t))).collect(),
        vowel: VOWEL.iter().map(|&(c, t)| (c, slot(t))).collect(),
        no_repeat: slot(NO_REPEAT),
    };
    let weighted = |table: &mut Table,
                    primaries: &[u64],
                    diacritic: &[u8],
                    case: &[u8],
                    kana: Option<[u8; 3]>|
     -> Weight {
        let primary = table.primary.len() as u32;
        let diacritic_at = table.diacritic.len() as u32;
        let case_at = table.case.len() as u32;
        let mut windows_length = 0u8;
        for &token in primaries {
            let (bytes, length) = slot(token);
            table.primary.extend_from_slice(&bytes);
            windows_length += length;
        }
        table.diacritic.extend_from_slice(diacritic);
        table.case.extend_from_slice(case);
        Weight::Weighted {
            primary,
            primaries: primaries.len() as u8,
            windows_length,
            diacritic: diacritic_at,
            diacritics: diacritic.len() as u8,
            case: case_at,
            cases: case.len() as u8,
            kana,
        }
    };
    for point in 0u32..=0xFFFF {
        let code = point as u16;
        let covered = code != 0 && (in_ranges(code, &COVERED) || special.contains_key(&code));
        let weight = if !covered {
            Weight::Refused
        } else if matches!(code, 0x1100 | 0x1161) {
            // Fn7's bare Giyeok/A native keys start C0/EC respectively.
            // Their remaining primary bytes and contextual runs stay unknown.
            Weight::FirstPrimaryGroup(if code == 0x1100 { 0xC0 } else { 0xEC })
        } else if let Some(exception) = exceptions.get(&code) {
            match exception {
                Exception::Ignorable => Weight::Ignorable,
                Exception::Refused => Weight::Refused,
                Exception::Mark(w) => Weight::Mark(*w),
                Exception::Special(w) => Weight::Special(*w),
                // An isolated form of marks compared as the marks (its decomposition without the
                // leading space): the walk's runs into it are not modelled.
                Exception::Expansion(_, false) => Weight::Refused,
                Exception::Expansion(units, whole) => {
                    let at = table.expansions.len() as u32;
                    table.expansions.extend_from_slice(units);
                    Weight::Expansion {
                        at,
                        len: units.len() as u8,
                        whole: *whole,
                    }
                }
                Exception::Iteration(rule) => Weight::Iteration(*rule),
                Exception::Weighted {
                    primaries,
                    diacritic,
                    case,
                    kana,
                } => weighted(&mut table, primaries, diacritic, case, *kana),
            }
        } else if (0xD800..=0xDFFF).contains(&code) {
            match SURROGATES
                .iter()
                .find(|&&(a, b, _)| (a..=b).contains(&code))
            {
                Some((_, _, Some((d, c)))) => {
                    weighted(&mut table, &[SURROGATE | point as u64], &[*d], &[*c], None)
                }
                Some((_, _, None)) => Weight::Ignorable,
                None => Weight::Refused,
            }
        } else if let Some(w) = special.get(&code) {
            Weight::Special(*w)
        } else if (0xAC00..=0xD7A3).contains(&code) {
            weighted(&mut table, &[HANGUL | point as u64], &[2], &[2], None)
        } else if let Some(base) = han_base(code) {
            if in_ranges(code, &NEW) {
                Weight::Ignorable
            } else {
                weighted(
                    &mut table,
                    &[HAN | (base << 32) | point as u64],
                    &[2],
                    &[2],
                    None,
                )
            }
        } else if let Some(root) = roots.get(&code) {
            derive(root, &secondary).map_or(Weight::Refused, |derived| match derived {
                Derived::Ignorable => Weight::Ignorable,
                Derived::Mark(w) => Weight::Mark(w),
                Derived::Weighted {
                    diacritic,
                    case,
                    kana,
                } => weighted(&mut table, &root.primaries, &diacritic, &case, kana),
            })
        } else {
            Weight::Refused
        };
        table.weights.push(weight);
    }
    table
}

/// The UCA's implicit weight base of a Han character (0 for the URO and the unified
/// compatibility ideographs, 1 for Extension A), each ordered by code point.
fn han_base(code: u16) -> Option<u64> {
    match code {
        0x4E00..=0x9FFF
        | 0xFA0E
        | 0xFA0F
        | 0xFA11
        | 0xFA13
        | 0xFA14
        | 0xFA1F
        | 0xFA21
        | 0xFA23
        | 0xFA24
        | 0xFA27..=0xFA29 => Some(0),
        0x3400..=0x4DBF => Some(1),
        _ => None,
    }
}

fn derive(root: &Root, secondary: &HashMap<u32, u8>) -> Option<Derived> {
    if root.flags & NEW_FLAG != 0 {
        return Some(Derived::Ignorable);
    }
    if root.primaries.is_empty() {
        return Some(match root.secondaries.as_slice() {
            [list] if list.len() == 1 => match secondary.get(&list[0]) {
                Some(&w) => Derived::Mark(w),
                None => Derived::Ignorable,
            },
            _ => Derived::Ignorable,
        });
    }
    if !root.secondaries[0].is_empty() {
        return None;
    }
    let mut diacritic = Vec::with_capacity(root.primaries.len());
    for list in &root.secondaries[1..] {
        let mut sum = 2u32;
        for s in list {
            sum += u32::from(*secondary.get(s)?);
        }
        diacritic.push((sum % 256) as u8);
    }
    let case = vec![if root.flags & WIDE != 0 { 3 } else { 2 }; root.primaries.len()];
    let kana = (root.flags & KANA != 0).then(|| {
        [
            if root.flags & SMALL != 0 { 0xC4 } else { 0xC6 },
            if root.flags & KATAKANA != 0 {
                0xC4
            } else {
                0xE4
            },
            if root.flags & NARROW != 0 { 0xC4 } else { 0xC5 },
        ]
    });
    Some(Derived::Weighted {
        diacritic,
        case,
        kana,
    })
}

/// Fn6's identical modern LV/LVT prefixes have default diacritic and case
/// entries, as fn7's native keys confirm, including after an identical ordinary
/// prefix. Their common weights cancel when
/// neither suffix can extend a Jamo sequence or repeat the preceding primary.
/// This gives no ordering between different Jamo prefixes or between a Jamo
/// sequence and a precomposed syllable.
pub(super) fn shared_jamo_tails<'a>(a: &'a [u16], b: &'a [u16]) -> Option<(usize, &'a [u16], &'a [u16])> {
    let prefix = a.iter().zip(b).take_while(|(x, y)| {
        x == y && ordinary_jamo_prefix(std::slice::from_ref(*x))
    }).count();
    let (a, b) = (&a[prefix..], &b[prefix..]);
    if a.len() < 2 || b.len() < 2 || a[..2] != b[..2]
        || !(0x1100..=0x1112).contains(&a[0]) || !(0x1161..=0x1175).contains(&a[1])
    {
        return None;
    }
    let at = if a.get(2) == b.get(2) && a.get(2).is_some_and(|c| (0x11A8..=0x11C2).contains(c)) {
        3
    } else {
        2
    };
    let (a, b) = (&a[at..], &b[at..]);
    (independent_jamo_suffix(a) && independent_jamo_suffix(b)).then_some((prefix, a, b))
}

/// Simple known entries neither join a Jamo run nor alter its boundary.
/// Keep marks, expansions, specials and ignorables outside this prefix rule.
fn ordinary_jamo_prefix(text: &[u16]) -> bool {
    text.iter().all(|&code| {
        // Paired surrogates can be variation selectors. Hangul syllables and
        // compatibility forms have unmeasured boundaries with conjoining Jamo.
        !matches!(code, 0x1100..=0x11FF | 0x3130..=0x318F | 0xA960..=0xA97F
            | 0xAC00..=0xDFFF | 0xFFA0..=0xFFDC)
            && matches!(table().weights[usize::from(code)],
                Weight::Weighted { primaries: 1, diacritics: 1, cases: 1, .. })
    })
}

/// These units cannot extend a Jamo run or repeat its preceding primary.
fn independent_jamo_suffix(text: &[u16]) -> bool {
    text.iter().all(|&code| matches!(
        table().weights[usize::from(code)],
        Weight::Ignorable | Weight::Mark(_) | Weight::Special(_) | Weight::Weighted { .. }
    ))
}

/// Fn7's three leading consonants start with the same primary pair as their
/// compatibility consonant, before the unmodelled Jamo bytes. This settles a
/// strict primary difference, not an equality with that compatibility form.
/// Native keys and CompareStringEx agree on the measured LV/LVT boundaries;
/// their disagreement for Giyeok versus its compatibility form stays refused.
fn jamo_leading_primary<'a>(table: &'a Table, text: &[u16], at: usize) -> Option<&'a [u8]> {
    let (compatibility, tail) = match text[at] {
        0x1100 => (0x3131, &text[at + 1..]),
        0x1101 => (0x3132, &text[at + 1..]),
        0x1102 => (0x3134, &text[at + 1..]),
        _ => return None,
    };
    if !ordinary_jamo_prefix(&text[..at]) {
        return None;
    }
    let tail = if tail.first() == Some(&0x1161) {
        let tail = &tail[1..];
        if text[at] == 0x1100 && tail.first() == Some(&0x11A8) { &tail[1..] } else { tail }
    } else if text[at] == 0x1100
        && matches!(tail, [0x00AD | 0x034F | 0x200B | 0x0301, 0x1161, ..])
    {
        &tail[2..]
    } else if text[at] == 0x1100 {
        tail
    } else {
        return None;
    };
    if !independent_jamo_suffix(tail) {
        return None;
    }
    match table.weights[compatibility] {
        Weight::Weighted { primary, primaries: 1, .. } => {
            Some(&table.primary[primary as usize..primary as usize + PRIMARY_BYTES])
        }
        _ => None,
    }
}

/// An order decided entirely before either unknown primary, or by a completed primary prefix.
/// No diacritic, case or special level can reverse a strict primary order.
pub(super) fn leading_order(
    left: &Result<Parts, Unfinished>,
    right: &Result<Parts, Unfinished>,
) -> Option<Ordering> {
    fn prefix(parts: &Result<Parts, Unfinished>) -> Option<(&[u8], bool, bool)> {
        match parts {
            Ok(parts) => Some((parts.primary.as_slice(), true, false)),
            Err(rest) => match rest.continuation {
                Continuation::More => Some((rest.primary.as_slice(), false, true)),
                Continuation::MayEnd => Some((rest.primary.as_slice(), false, false)),
                Continuation::Unknown => None,
            },
        }
    }
    let (a, a_complete, a_continues) = prefix(left)?;
    let (b, b_complete, b_continues) = prefix(right)?;
    let common = a.len().min(b.len());
    let earlier = a[..common].cmp(&b[..common]);
    if !earlier.is_eq() {
        return Some(earlier);
    }
    if a_complete && (a.len() < b.len() || (a.len() == b.len() && b_continues)) {
        Some(Ordering::Less)
    } else if b_complete && (b.len() < a.len() || (a.len() == b.len() && a_continues)) {
        Some(Ordering::Greater)
    } else {
        None
    }
}

fn separate_special(&mut self) {
    if let Self::Special(_, _, adjacent) = self {
        *adjacent = false;
    }
}

fn kana(&mut self, [small, kind, width]: [u8; 3], iteration: u8) {
    self.small.push(small);
    self.iteration.push(iteration);
    self.kind.push(kind);
    self.width.push(width);
}

/// Adds one code unit; `None` when it is refused.
fn unit(&mut self, table: &Table, code: u16, before: &mut Before) -> Option<()> {
    if matches!(table.weights[usize::from(code)], Weight::Ignorable | Weight::Mark(_)) {
        before.separate_special();
    }
    match table.weights[usize::from(code)] {
        Weight::Refused | Weight::FirstPrimaryGroup(_) => return None,
        Weight::Ignorable if self.expanding => {}
        Weight::Ignorable => self.steps.push(Step::Ignorable),
        Weight::Mark(added) => self.steps.push(Step::Mark(added)),
        Weight::Special([w0, w1]) => {
            self.steps.push(Step::Special(code));
            let position = 0xFFFF - (self.windows_length / 2) as u16;
            self.special.extend_from_slice(&position.to_be_bytes());
            self.special.extend_from_slice(&[w0, w1]);
            *before = Before::Special(code, [w0, w1], true);
        }
        Weight::Expansion { at, len, whole } => {
            let at = at as usize;
            let primaries = self.primary.len();
            // Marks run on into a decomposition after an entry, not after a mark, and an
            // ignorable unit in it does not end them (measured).
            debug_assert!(whole);
            self.steps.push(Step::Expansion);
            let expanding = std::mem::replace(&mut self.expanding, true);
            for &unit in &table.expansions[at..at + usize::from(len)] {
                self.unit(table, unit, before)?;
            }
            self.expanding = expanding;
            // An iteration mark after a unit that expands to several primaries takes FF FF.
            if self.primary.len() - primaries > PRIMARY_BYTES {
                *before = Before::Nothing;
            }
        }
        Weight::Iteration(rule) => {
            let ((bytes, length), kana) = match *before {
                Before::Nothing => (table.no_repeat, None),
                Before::Special(punctuation, [weight, _], adjacent) => {
                    // Fn7's native keys and Excel comparisons agree here: an
                    // iteration after these punctuation units has primary
                    // 06 followed by the punctuation's first special byte.
                    // This is before every ordinary primary group. Keep the
                    // position-dependent special itself in the final level.
                    if !adjacent || !matches!(code, 0x3005 | 0x309D | 0x30FC)
                        || !matches!(punctuation, 0x0027 | 0x002D | 0x2010 | 0x2212)
                    {
                        return None;
                    }
                    let mut bytes = [0; PRIMARY_BYTES];
                    bytes[0] = 0x06;
                    bytes[1] = weight;
                    ((bytes, 2), None)
                }
                Before::One(unit, own, kana) => {
                    let vowel = rule.vowel.then(|| table.vowel.get(&unit)).flatten();
                    let repeat = || {
                        let at = table.repeat.partition_point(|&(start, _, _)| start <= unit);
                        at.checked_sub(1)
                            .map(|at| table.repeat[at])
                            .filter(|&(_, end, _)| unit <= end)
                            .map(|(_, _, slot)| slot)
                    };
                    // A Han character's four-byte primary repeats as the separately measured
                    // REPEAT slot, not as its own primary. Fn1's three Han bases and their
                    // lookup/sort controls confirm this existing measurement.
                    (vowel.copied().or_else(repeat).unwrap_or(own), kana)
                }
            };
            self.primary.extend_from_slice(&bytes);
            self.windows_length += u32::from(length);
            // With nothing before it, the mark's own diacritic entry is not in the key.
            let diacritic = match *before {
                Before::Nothing => 2,
                _ => rule.diacritic,
            };
            self.steps.push(Step::Base(diacritic));
            self.case.push(2);
            if let Some([small, kind, width]) = kana {
                self.kana([small, kind, rule.width.unwrap_or(width)], rule.iteration);
            }
            before.separate_special();
        }
        Weight::Weighted {
            primary: start,
            primaries,
            windows_length: length,
            diacritic: diacritic_at,
            diacritics,
            case: case_at,
            cases,
            kana,
        } => {
            let start = start as usize;
            let bytes = &table.primary[start..start + usize::from(primaries) * PRIMARY_BYTES];
            self.primary.extend_from_slice(bytes);
            self.windows_length += u32::from(length);
            let (d, nd) = (diacritic_at as usize, usize::from(diacritics));
            if nd == 0 {
                self.steps.push(Step::Base(2));
            }
            self.steps
                .extend(table.diacritic[d..d + nd].iter().map(|&w| Step::Base(w)));
            let (c, nc) = (case_at as usize, usize::from(cases));
            self.case.extend_from_slice(&table.case[c..c + nc]);
            if let Some(weights) = kana {
                self.kana(weights, 3);
            }
            *before = if primaries == 1 {
                let mut slot = [0u8; PRIMARY_BYTES];
                slot.copy_from_slice(bytes);
                Before::One(code, (slot, length), kana)
            } else {
                Before::Nothing
            };
        }
    }
    Some(())
}

/// The collation weights of `text`, or the primary prefix before an unmodelled unit.
pub(super) fn parts(text: &[u16]) -> Result<Parts, Unfinished> {
    let table = table();
    let mut gathered = Gathered::default();
    let mut before = Before::Nothing;
    let mut starts: Vec<u32> = Vec::with_capacity(text.len() + 1);
    let mut at = 0;
    while at < text.len() {
        let code = text[at];
        starts.push(gathered.steps.len() as u32);
        if (0xD800..=0xDBFF).contains(&code)
            && let Some(&low) = text.get(at + 1)
            && (0xDC00..=0xDFFF).contains(&low)
        {
            let point = 0x10000 + ((u32::from(code) - 0xD800) << 10) + (u32::from(low) - 0xDC00);
            if (0xE0100..=0xE01EF).contains(&point) {
                gathered.steps.push(Step::Ignorable);
                before.separate_special();
                starts.push(gathered.steps.len() as u32);
                at += 2;
                continue;
            }
        }
        let primaries = gathered.primary.len();
        if gathered.unit(table, code, &mut before).is_none() {
            gathered.primary.truncate(primaries);
            if let Some(primary) = jamo_leading_primary(table, text, at) {
                gathered.primary.extend_from_slice(primary);
                return Err(Unfinished { primary: gathered.primary, continuation: Continuation::MayEnd });
            }
            // Fn7's exact bare reversed A/Giyeok pair keeps A's first EC byte.
            // No later byte, ordinary-prefix context or continuation is assigned.
            let bare_reversed_jamo = at == 0 && text == [0x1161, 0x1100];
            if ordinary_jamo_prefix(&text[..at])
                && (independent_jamo_suffix(&text[at + 1..]) || bare_reversed_jamo)
                && let Weight::FirstPrimaryGroup(group) = table.weights[usize::from(code)]
            {
                // A strict difference in this measured byte decides before any
                // unknown byte or later level. Keep the rest explicitly unfinished.
                gathered.primary.push(group);
                return Err(Unfinished { primary: gathered.primary, continuation: Continuation::More });
            }
            return Err(Unfinished {
                primary: gathered.primary,
                // An iteration failure after One would still add a primary. After a special
                // even a nonempty contribution has not been measured; leave it undecided.
                continuation: if matches!(table.weights[usize::from(code)], Weight::Iteration(_))
                    && matches!(before, Before::One(..))
                {
                    Continuation::More
                } else {
                    Continuation::Unknown
                },
            });
        }
        at += 1;
    }
    starts.push(gathered.steps.len() as u32);
    let trim = |list: &mut Vec<u8>, default: u8| {
        while list.last() == Some(&default) {
            list.pop();
        }
    };
    let Gathered {
        primary,
        steps,
        mut case,
        special,
        mut small,
        mut iteration,
        mut kind,
        mut width,
        ..
    } = gathered;
    trim(&mut case, 2);
    let mut rest = case;
    rest.push(1);
    if !small.is_empty() {
        trim(&mut small, 0xC6);
        trim(&mut iteration, 3);
        trim(&mut kind, 0xE4);
        trim(&mut width, 0xC5);
        rest.extend_from_slice(&small);
        rest.push(0xFF);
        rest.extend_from_slice(&iteration);
        rest.push(0x02);
        rest.extend_from_slice(&kind);
        rest.push(0xFF);
        rest.extend_from_slice(&width);
        rest.push(0xFF);
    }
    rest.push(1);
    rest.extend_from_slice(&special);
    Ok(Parts {
        primary,
        steps,
        rest,
        starts,
    })
}

/// The diacritic level of two texts whose primary weights are the same (see [`diacritics`]):
/// `CompareStringEx` first passes the code units the texts start with in common, passing an
/// ignorable unit on either side, and walks the rest.
pub(super) fn diacritic_order(a: &[u16], left: &Parts, b: &[u16], right: &Parts) -> Ordering {
    let ignorable = |parts: &Parts, at: usize| {
        let range = parts.starts[at] as usize..parts.starts[at + 1] as usize;
        parts.steps[range]
            .iter()
            .all(|step| matches!(step, Step::Ignorable | Step::Expansion))
    };
    let (mut i, mut j) = (0, 0);
    loop {
        while i < a.len() && ignorable(left, i) {
            i += 1;
        }
        while j < b.len() && ignorable(right, j) {
            j += 1;
        }
        if i < a.len() && j < b.len() && a[i] == b[j] {
            i += 1;
            j += 1;
        } else {
            break;
        }
    }
    diacritics(
        &left.steps[left.starts[i] as usize..],
        &right.steps[right.starts[j] as usize..],
    )
}

/// The diacritic level of what follows two texts' common start, as `CompareStringEx` walks it
/// (measured; Windows' sort keys hold a sum of marks per entry instead, and so order a few texts
/// otherwise). Both are walked in step, an ignorable unit passed on its own side. Two equal steps
/// pass. Two different entries, or two different marks, compare as sums: each with the marks that
/// follow it directly, added in a byte. A mark against a special passes the special once the walk
/// has passed a special (alone, or two different ones); otherwise, and against anything else, the
/// mark makes its text the greater. Two different specials pass every special and ignorable unit
/// that follows them on both sides; a special against anything else is passed on its own side. The first difference decides; when one side runs out, a mark left in the
/// other makes that one the greater.
fn diacritics(a: &[Step], b: &[Step]) -> Ordering {
    let passed = |steps: &[Step], mut at: usize| {
        while matches!(
            steps.get(at),
            Some(Step::Special(_) | Step::Ignorable | Step::Expansion)
        ) {
            at += 1;
        }
        at
    };
    // The sum of `first` and the marks from `at` on (passing an expansion's start after an
    // entry), and where they end.
    fn run(steps: &[Step], mut at: usize, first: u8, entry: bool) -> (u8, usize) {
        let mut sum = first;
        loop {
            match steps.get(at) {
                Some(Step::Mark(w)) => sum = sum.wrapping_add(*w),
                Some(Step::Expansion) if entry => {}
                _ => return (sum, at),
            }
            at += 1;
        }
    }
    let (mut i, mut j) = (0, 0);
    let mut result = Ordering::Equal;
    let mut decide = |order: Ordering| {
        if result.is_eq() {
            result = order;
        }
    };
    // Whether the walk has passed a special (alone, or two different ones).
    let mut special_passed = false;
    loop {
        while matches!(a.get(i), Some(Step::Ignorable | Step::Expansion)) {
            i += 1;
        }
        while matches!(b.get(j), Some(Step::Ignorable | Step::Expansion)) {
            j += 1;
        }
        let (Some(&x), Some(&y)) = (a.get(i), b.get(j)) else {
            break;
        };
        match (x, y) {
            _ if x == y => {
                i += 1;
                j += 1;
            }
            (Step::Mark(w), Step::Mark(v)) | (Step::Base(w), Step::Base(v)) => {
                let entry = matches!(x, Step::Base(_));
                let (left, next_i) = run(a, i + 1, w, entry);
                let (right, next_j) = run(b, j + 1, v, entry);
                decide(left.cmp(&right));
                i = next_i;
                j = next_j;
            }
            (Step::Mark(_), Step::Special(_)) if special_passed => j += 1,
            (Step::Special(_), Step::Mark(_)) if special_passed => i += 1,
            (Step::Mark(_), _) => {
                decide(Ordering::Greater);
                i += 1;
            }
            (_, Step::Mark(_)) => {
                decide(Ordering::Less);
                j += 1;
            }
            (Step::Special(_), Step::Special(_)) => {
                special_passed = true;
                i = passed(a, i);
                j = passed(b, j);
            }
            (Step::Special(_), _) => {
                special_passed = true;
                i += 1;
            }
            (_, Step::Special(_)) => {
                special_passed = true;
                j += 1;
            }
            _ => {
                i += 1;
                j += 1;
            }
        }
    }
    if a[i.min(a.len())..]
        .iter()
        .any(|s| matches!(s, Step::Mark(_)))
    {
        decide(Ordering::Greater);
    }
    if b[j.min(b.len())..]
        .iter()
        .any(|s| matches!(s, Step::Mark(_)))
    {
        decide(Ordering::Less);
    }
    result
}