//! Unicode Normalization Form C for secrets.
//!
//! The iterators in `unicode_normalization` keep internal buffers that move to
//! the heap for long runs of combining marks and are freed without being
//! wiped, and slice sorting allocates scratch space. This module implements
//! the UAX #15 normalization algorithm itself, using only that crate's
//! character data tables, so that every buffer holding the text is one it
//! controls: each is sized up front so it never reallocates, and is zeroized
//! when dropped.

use unicode_normalization::char::{canonical_combining_class, compose, decompose_canonical};
use zeroize::Zeroizing;

/// The largest number of code points any single character's full canonical
/// decomposition can produce.
const MAX_CANONICAL_DECOMPOSITION: usize = 4;

/// Returns the NFC normalization of `text`, leaving no unwiped copies of it in
/// memory.
pub(crate) fn nfc(text: &str) -> Zeroizing<String> {
    let mut chars = Zeroizing::new(Vec::with_capacity(
        text.chars()
            .count()
            .saturating_mul(MAX_CANONICAL_DECOMPOSITION),
    ));

    decompose(text, &mut chars);
    canonical_order(&mut chars);
    let len = canonical_compose(&mut chars);
    chars.truncate(len);

    let mut normalized = Zeroizing::new(String::with_capacity(
        chars.iter().map(|c| c.len_utf8()).sum(),
    ));
    normalized.extend(chars.iter());
    normalized
}

/// Appends the full canonical decomposition of `text` to `out`, which must
/// have room for `MAX_CANONICAL_DECOMPOSITION` code points per character.
fn decompose(text: &str, out: &mut Vec<char>) {
    for c in text.chars() {
        decompose_canonical(c, |d| {
            debug_assert!(out.len() < out.capacity(), "decomposition buffer overflow");
            out.push(d);
        });
    }
}

/// Applies the Canonical Ordering Algorithm in place: within each run of
/// non-starters, characters are stably sorted by canonical combining class.
///
/// This is an insertion sort, which neither allocates nor reorders characters
/// of equal class. Runs of combining marks are short in real text.
fn canonical_order(chars: &mut [char]) {
    for i in 1..chars.len() {
        let class = canonical_combining_class(chars[i]);
        if class == 0 {
            continue;
        }

        let mut j = i;
        while j > 0 {
            let previous = canonical_combining_class(chars[j - 1]);
            if previous <= class {
                break;
            }
            chars.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// Applies the Canonical Composition Algorithm in place to canonically
/// decomposed, canonically ordered text, returning the composed length.
///
/// A character combines with the most recent starter unless it is blocked: that
/// is, unless some character left uncomposed between them has a combining class
/// of zero or at least that of the character.
fn canonical_compose(chars: &mut [char]) -> usize {
    let mut written = 0;
    let mut starter: Option<usize> = None;
    let mut last_class: Option<u8> = None;

    for read in 0..chars.len() {
        let c = chars[read];
        let class = canonical_combining_class(c);

        if let Some(s) = starter {
            let blocked = last_class.is_some_and(|last| last >= class);

            if !blocked && let Some(composed) = compose(chars[s], c) {
                chars[s] = composed;
                continue;
            }

            if class == 0 {
                starter = Some(written);
                last_class = None;
            } else {
                last_class = Some(class);
            }
        } else if class == 0 {
            starter = Some(written);
        }

        chars[written] = c;
        written += 1;
    }

    written
}

#[cfg(test)]
mod tests {
    use unicode_normalization::UnicodeNormalization as _;

    use super::*;

    #[test]
    fn max_canonical_decomposition_bounds_every_character() {
        let longest = (0..=char::MAX as u32)
            .filter_map(char::from_u32)
            .map(|c| {
                let mut n = 0;
                decompose_canonical(c, |_| n += 1);
                n
            })
            .max()
            .unwrap();

        assert_eq!(longest, MAX_CANONICAL_DECOMPOSITION);
    }

    fn assert_matches_reference(text: &str) {
        let reference: String = text.nfc().collect();
        assert_eq!(*nfc(text), reference, "NFC mismatch for {text:?}");
    }

    #[test]
    fn matches_reference_on_known_cases() {
        for text in [
            "",
            "password",
            "caf\u{e9}",
            "cafe\u{301}",
            // Combining marks out of canonical order (230 before 220).
            "a\u{301}\u{316}",
            // Blocked and unblocked combinations.
            "a\u{323}\u{302}",
            "a\u{302}\u{323}",
            "\u{1ec7}",
            "e\u{302}\u{323}",
            // Leading non-starters with no starter to combine with.
            "\u{301}\u{301}a",
            // Singleton decompositions and composition exclusions.
            "\u{212b}",
            "\u{2126}",
            "\u{344}",
            "\u{f900}",
            // Hangul: precomposed, LV + T, and conjoining jamo.
            "\u{d55c}\u{ae00}",
            "\u{ac00}\u{11a8}",
            "\u{1100}\u{1161}\u{11a8}",
            "\u{1100}\u{1161}\u{1100}",
            // Long runs of combining marks, which overflow inline buffers.
            "Z\u{300}\u{301}\u{302}\u{303}\u{304}\u{305}\u{306}\u{307}\u{308}\u{309}\u{316}\u{317}\u{318}",
            "\u{1f600} emoji and \u{4e2d}\u{6587}",
        ] {
            assert_matches_reference(text);
        }
    }

    #[test]
    fn matches_reference_on_generated_text() {
        // Starters, precomposed letters, combining marks of assorted classes,
        // Hangul jamo and syllables, singletons, and exclusions.
        const POOL: &[char] = &[
            'a', 'e', 'o', 'A', 'Z', '\u{e9}', '\u{1ec7}', '\u{212b}', '\u{344}', '\u{f900}',
            '\u{300}', '\u{301}', '\u{302}', '\u{308}', '\u{316}', '\u{323}', '\u{327}', '\u{334}',
            '\u{345}', '\u{5b0}', '\u{93c}', '\u{94d}', '\u{1100}', '\u{1161}', '\u{11a8}',
            '\u{ac00}', '\u{d55c}', '\u{3099}', '\u{304b}', ' ',
        ];

        // A fixed-seed xorshift generator keeps the test deterministic.
        let mut state: u64 = 0x2545_f491_4f6c_dd1d;
        let mut next = move || {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            state
        };

        for _ in 0..20_000 {
            let len = (next() % 12) as usize;
            let text: String = (0..len)
                .map(|_| POOL[(next() % POOL.len() as u64) as usize])
                .collect();
            assert_matches_reference(&text);
        }
    }

    #[test]
    fn buffers_are_never_reallocated() {
        let text = format!("Z{}", "\u{301}\u{316}\u{344}".repeat(200));
        let mut chars = Vec::with_capacity(text.chars().count() * MAX_CANONICAL_DECOMPOSITION);
        let allocation = chars.as_ptr();

        decompose(&text, &mut chars);
        canonical_order(&mut chars);
        let len = canonical_compose(&mut chars);

        assert_eq!(chars.as_ptr(), allocation);
        assert!(len <= chars.len());
    }
}