Luigit
repositories / smith

smith

There are many coding harnesses - but this one is fast

owned by admin

smith-harness/src/response_sanitizer.rs

Raw
//! Bounded pre-guest response sanitization (`SMH-SPEC-SPEC0001`, Authentication).
//!
//! Request-owned borrowed credentials never enter guest state or diagnostics.
//! Matching recognizes raw bytes and single-level JSON scalar spellings without
//! enumerating combinations. Only a bounded classification window survives a call.
//!
//! For a large dictionary, a JSON token at each byte offset has one successor
//! (or none), including offsets inside another escape. A reverse automaton over
//! that DAG finds the longest complete credential at every start in one pass.
//! Persistent transition maps bound a lookup by alphabet depth, not prefix length.
//! Starts with a full worst-case spelling of lookahead cannot be partial matches.
//! Retaining lookahead plus one credential-sized processing block amortizes the
//! overlapping passes: lookahead <= 6 * block, so steady work is <= 7 passes/byte.
//! No spelling expansion, response-sized state, or input-dependent work rejection.
//! An incremental earliest-start frontier reuses matched prefixes across chunks.
//! Failed lookahead switches to blocks instead of restarting at overlapping offsets.
//! Complete long echoes and public packets can progress before EOF.

mod automaton;
mod frontier;

use automaton::Automaton;
use frontier::PrefixProgress;

const CREDENTIAL_COUNT_MAX: usize = 32;
const CREDENTIAL_BYTES_MAX: usize = 4096;
const CREDENTIAL_TOTAL_BYTES_MAX: usize = 32 * 1024;
const CARRY_BYTES_MAX: usize = CREDENTIAL_BYTES_MAX * 6;
const REPLACEMENT_BYTES_MAX: usize = 32;
const JSON_SCALAR_BYTES_MAX: usize = 12;
#[cfg(test)]
const REPLACEMENT: &[u8] = b"<redacted>";

pub struct ResponseSanitizer<'a> {
    credentials: &'a [String],
    replacement: &'static [u8],
    carry: Vec<u8>,
    dictionary: Option<Box<Dictionary>>,
}

// Small credentials retain eager classification with a fixed comparison bound.
// Large credentials use reverse dynamic programming over bounded blocks.
const EAGER_BYTES_MAX: usize = 64;

struct Dictionary {
    raw: Automaton,
    json: Option<Automaton>,
    lookahead: usize,
    block_bytes: usize,
    next_scan: usize,
    progress: Vec<PrefixProgress>,
    matched_length: u16,
    inspected_bytes: u16,
    stage: MatchingStage,
}

#[derive(Clone, Copy)]
enum MatchingStage {
    Eager,
    Frontier,
    Block,
}

#[cfg(all(not(test), target_arch = "x86_64"))]
const _: () = assert!(
    std::mem::size_of::<Dictionary>() == 168,
    "production request dictionary must remain 168 bytes"
);

#[cfg(test)]
impl Dictionary {
    fn comparisons(&self) -> u64 {
        self.raw.comparisons() + self.json.as_ref().map_or(0, Automaton::comparisons)
    }
}

#[derive(Clone, Copy)]
enum Spelling {
    Different,
    Prefix,
    Complete(usize),
}

impl<'a> ResponseSanitizer<'a> {
    pub(super) fn validate(credentials: &[String]) -> Result<(), &'static str> {
        if credentials.len() > CREDENTIAL_COUNT_MAX
            || credentials
                .iter()
                .any(|credential| credential.is_empty() || credential.len() > CREDENTIAL_BYTES_MAX)
            || credentials.iter().map(String::len).sum::<usize>() > CREDENTIAL_TOTAL_BYTES_MAX
        {
            return Err("response sanitizer credential bounds exceeded");
        }
        Ok(())
    }

    pub(super) fn new(
        credentials: &'a [String],
        replacement: &'static [u8],
    ) -> Result<Self, &'static str> {
        Self::validate(credentials)?;
        if replacement.is_empty() || replacement.len() > REPLACEMENT_BYTES_MAX {
            return Err("response sanitizer replacement bound exceeded");
        }
        let dictionary = credentials
            .iter()
            .any(|value| value.len() > EAGER_BYTES_MAX)
            .then(|| {
                let lookahead = credentials
                    .iter()
                    .map(|value| {
                        value
                            .chars()
                            .map(|scalar| scalar.len_utf16() * 6)
                            .sum::<usize>()
                    })
                    .max()
                    .unwrap_or_default();
                Box::new(Dictionary {
                    raw: Automaton::new(
                        credentials
                            .iter()
                            .map(|value| value.bytes().rev().map(u32::from).collect())
                            .collect(),
                    ),
                    // ASCII byte and scalar patterns are identical; borrow
                    // the raw table for both traversals instead of duplicating it.
                    json: (!credentials.iter().all(|value| value.is_ascii())).then(|| {
                        Automaton::new(
                            credentials
                                .iter()
                                .map(|value| value.chars().rev().map(u32::from).collect())
                                .collect(),
                        )
                    }),
                    lookahead,
                    block_bytes: credentials
                        .iter()
                        .map(String::len)
                        .max()
                        .unwrap_or_default(),
                    next_scan: lookahead,
                    progress: Vec::new(),
                    matched_length: 0,
                    inspected_bytes: 0,
                    stage: MatchingStage::Eager,
                })
            });
        let carry = dictionary.as_ref().map_or_else(Vec::new, |dictionary| {
            Vec::with_capacity(dictionary.lookahead + dictionary.block_bytes)
        });
        Ok(Self {
            credentials,
            replacement,
            carry,
            dictionary,
        })
    }

    pub(super) fn push(&mut self, mut bytes: &[u8]) -> Result<Vec<u8>, &'static str> {
        if self.credentials.is_empty() {
            return Ok(bytes.to_vec());
        }
        let mut output = Vec::new();
        while !bytes.is_empty() {
            let bound = self
                .dictionary
                .as_ref()
                .map_or(CARRY_BYTES_MAX, |dictionary| {
                    dictionary.lookahead + dictionary.block_bytes
                });
            // Probe bounded prefixes even when transport delivers a large
            // packet; unrelated public bytes must not wait for block lookahead.
            let limit = if self.dictionary.is_some() && self.carry.len() < EAGER_BYTES_MAX {
                EAGER_BYTES_MAX
            } else {
                bound
            };
            let count = bytes.len().min(limit - self.carry.len());
            if count == 0 {
                self.carry.clear();
                return Err("response sanitizer carry bound exceeded");
            }
            self.carry.extend_from_slice(&bytes[..count]);
            bytes = &bytes[count..];
            if self.dictionary.is_some() {
                self.classify_dictionary(&mut output);
            } else {
                self.classify(&mut output, false, CARRY_BYTES_MAX);
            }
        }
        Ok(output)
    }

    // Invoke only on normal completion. Dropping on every other exit discards
    // carry, including a potentially sensitive prefix at disconnect.
    pub(super) fn finish(&mut self) -> Vec<u8> {
        let mut output = Vec::new();
        if self.dictionary.is_some() {
            self.classify_block(&mut output, true);
        } else {
            self.classify(&mut output, true, CARRY_BYTES_MAX);
        }
        output
    }

    fn classify_dictionary(&mut self, output: &mut Vec<u8>) {
        loop {
            let Some(dictionary) = &self.dictionary else {
                return;
            };
            match dictionary.stage {
                MatchingStage::Eager => {
                    let before = self.carry.len();
                    self.classify(output, false, EAGER_BYTES_MAX);
                    if self.carry.is_empty() {
                        return;
                    }
                    if self.carry.len() != before {
                        continue;
                    }
                    if self.carry.len() < EAGER_BYTES_MAX {
                        return;
                    }
                    let Some(dictionary) = &mut self.dictionary else {
                        return;
                    };
                    dictionary.progress.clear();
                    dictionary
                        .progress
                        .resize(self.credentials.len(), PrefixProgress::default());
                    dictionary.matched_length = 0;
                    dictionary.inspected_bytes = 0;
                    dictionary.stage = MatchingStage::Frontier;
                }
                MatchingStage::Frontier => {
                    let Some(dictionary) = &mut self.dictionary else {
                        return;
                    };
                    if dictionary.advance_start(&self.carry, self.credentials) {
                        return;
                    }
                    let matched = usize::from(dictionary.matched_length);
                    let inspected = usize::from(dictionary.inspected_bytes);
                    if matched != 0 {
                        output.extend_from_slice(self.replacement);
                        self.carry.drain(..matched);
                    }
                    dictionary.progress.clear();
                    // A failed scalar may inspect at most twelve bytes beyond
                    // a completion. Larger unpaid lookahead must use blocks,
                    // otherwise short overlapping matches restart long scans.
                    dictionary.stage = if matched != 0
                        && (self.carry.len() <= EAGER_BYTES_MAX
                            || matched + JSON_SCALAR_BYTES_MAX >= inspected)
                    {
                        MatchingStage::Eager
                    } else {
                        MatchingStage::Block
                    };
                }
                MatchingStage::Block => {
                    if self.carry.len() < dictionary.next_scan {
                        return;
                    }
                    self.classify_block(output, false);
                }
            }
        }
    }

    fn classify_block(&mut self, output: &mut Vec<u8>, finished: bool) {
        let Some(dictionary) = &mut self.dictionary else {
            return;
        };
        let length = self.carry.len();
        if length == 0 {
            dictionary.progress.clear();
            dictionary.stage = MatchingStage::Eager;
            return;
        }
        let json = dictionary.json.as_ref().unwrap_or(&dictionary.raw);
        let mut ends = vec![0_u32; length];
        let mut states = vec![0_u32; length + 1];
        let mut raw_lengths = vec![0_u16; length];
        let mut raw_state = 0;
        for offset in (0..length).rev() {
            raw_state = dictionary
                .raw
                .advance(raw_state, u32::from(self.carry[offset]));
            raw_lengths[offset] = self::length(dictionary.raw.longest(raw_state));
            if let Some((scalar, count)) = json_token(&self.carry[offset..]) {
                let end = offset + count;
                ends[offset] = automaton::index(end);
                states[offset] = json.advance(states[end], u32::from(scalar));
            }
        }
        let safe = if finished {
            length
        } else {
            length + 1 - dictionary.lookahead
        };
        let mut offset = 0;
        while offset < safe {
            let mut end = offset;
            for _ in 0..json.longest(states[offset]) {
                end = ends[end] as usize;
            }
            let matched = usize::from(raw_lengths[offset]).max(end - offset);
            if matched == 0 {
                output.push(self.carry[offset]);
                offset += 1;
            } else {
                output.extend_from_slice(self.replacement);
                offset += matched;
            }
        }
        self.carry.drain(..offset);
        dictionary.next_scan = dictionary
            .lookahead
            .max(self.carry.len() + dictionary.block_bytes);
        dictionary.progress.clear();
        dictionary.stage = if finished || self.carry.len() <= EAGER_BYTES_MAX {
            MatchingStage::Eager
        } else {
            MatchingStage::Block
        };
    }

    fn classify(&mut self, output: &mut Vec<u8>, finished: bool, byte_limit: usize) {
        let mut offset = 0;
        let length = self.carry.len().min(byte_limit);
        while offset < length {
            let bytes = &self.carry[offset..length];
            let mut matched = 0;
            let mut pending = false;
            for credential in self.credentials {
                for spelling in [
                    raw_spelling(bytes, credential.as_bytes()),
                    json_spelling(bytes, credential),
                ] {
                    match spelling {
                        Spelling::Complete(length) => matched = matched.max(length),
                        Spelling::Prefix => pending = true,
                        Spelling::Different => {}
                    }
                }
            }
            if pending && !finished {
                break;
            }
            if matched == 0 {
                output.push(bytes[0]);
                offset += 1;
            } else {
                output.extend_from_slice(self.replacement);
                offset += matched;
            }
        }
        self.carry.drain(..offset);
    }
}

#[expect(
    clippy::cast_possible_truncation,
    reason = "credential validation bounds every accepted pattern length to 4096"
)]
fn length(value: usize) -> u16 {
    assert!(
        value <= CREDENTIAL_BYTES_MAX,
        "accepted dictionary length must fit its credential bound"
    );
    value as u16
}

#[expect(
    clippy::cast_possible_truncation,
    reason = "classification windows are bounded to 28672 bytes"
)]
fn spelling_offset(value: usize) -> u16 {
    assert!(
        value <= CARRY_BYTES_MAX + CREDENTIAL_BYTES_MAX,
        "spelling offset must fit the bounded classification window"
    );
    value as u16
}

fn json_token(bytes: &[u8]) -> Option<(char, usize)> {
    let first = *bytes.first()?;
    if first != b'\\' {
        if first == b'"' || first < 0x20 {
            return None;
        }
        let length = match first {
            0..=0x7f => 1,
            0xc2..=0xdf => 2,
            0xe0..=0xef => 3,
            0xf0..=0xf4 => 4,
            _ => return None,
        };
        return Some((
            std::str::from_utf8(bytes.get(..length)?)
                .ok()?
                .chars()
                .next()?,
            length,
        ));
    }
    let short = match *bytes.get(1)? {
        b'"' => '"',
        b'\\' => '\\',
        b'/' => '/',
        b'b' => '\u{8}',
        b'f' => '\u{c}',
        b'n' => '\n',
        b'r' => '\r',
        b't' => '\t',
        b'u' => {
            let unit = unicode_unit(bytes)?;
            if (0xd800..=0xdbff).contains(&unit) {
                let low = unicode_unit(bytes.get(6..)?)?;
                if !(0xdc00..=0xdfff).contains(&low) {
                    return None;
                }
                let scalar = 0x10000 + ((unit - 0xd800) << 10) + low - 0xdc00;
                return Some((char::from_u32(scalar)?, 12));
            }
            return Some((char::from_u32(unit)?, 6));
        }
        _ => return None,
    };
    Some((short, 2))
}

fn unicode_unit(bytes: &[u8]) -> Option<u32> {
    if bytes.get(..2)? != b"\\u" {
        return None;
    }
    bytes.get(2..6)?.iter().try_fold(0, |unit, digit| {
        Some((unit << 4) | char::from(*digit).to_digit(16)?)
    })
}

#[cfg(test)]
thread_local! {
    static COMPARISONS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
}

fn raw_spelling(bytes: &[u8], spelling: &[u8]) -> Spelling {
    #[cfg(test)]
    let starts_with = |bytes: &[u8], prefix: &[u8]| {
        bytes.len() >= prefix.len()
            && bytes.iter().zip(prefix).all(|(actual, expected)| {
                COMPARISONS.with(|count| count.set(count.get() + 1));
                actual == expected
            })
    };
    #[cfg(not(test))]
    let starts_with = <[u8]>::starts_with;
    if starts_with(bytes, spelling) {
        Spelling::Complete(spelling.len())
    } else if starts_with(spelling, bytes) {
        Spelling::Prefix
    } else {
        Spelling::Different
    }
}

fn json_spelling(bytes: &[u8], credential: &str) -> Spelling {
    let mut offset = 0;
    for scalar in credential.chars() {
        match scalar_spelling(&bytes[offset..], scalar) {
            Spelling::Complete(length) => offset += length,
            other => return other,
        }
    }
    Spelling::Complete(offset)
}

fn scalar_spelling(bytes: &[u8], scalar: char) -> Spelling {
    if bytes.first() == Some(&b'\\') {
        escaped_scalar(bytes, scalar)
    } else if scalar == '"' || scalar == '\\' || scalar <= '\u{1f}' {
        if bytes.is_empty() {
            Spelling::Prefix
        } else {
            Spelling::Different
        }
    } else {
        raw_spelling(bytes, scalar.encode_utf8(&mut [0; 4]).as_bytes())
    }
}

fn escaped_scalar(bytes: &[u8], scalar: char) -> Spelling {
    let short = match scalar {
        '"' => Some(b'"'),
        '\\' => Some(b'\\'),
        '/' => Some(b'/'),
        '\u{8}' => Some(b'b'),
        '\u{c}' => Some(b'f'),
        '\n' => Some(b'n'),
        '\r' => Some(b'r'),
        '\t' => Some(b't'),
        _ => None,
    };
    if let Some(short) = short {
        match raw_spelling(bytes, &[b'\\', short]) {
            Spelling::Different => {}
            other => return other,
        }
    }
    let mut spelling = [0; JSON_SCALAR_BYTES_MAX];
    let mut length = 0;
    for unit in scalar.encode_utf16(&mut [0; 2]) {
        spelling[length..length + 2].copy_from_slice(b"\\u");
        for (index, shift) in [12, 8, 4, 0].into_iter().enumerate() {
            spelling[length + 2 + index] = b"0123456789abcdef"[usize::from((*unit >> shift) & 15)];
        }
        length += 6;
    }
    // Only hex digits are case-insensitive; JSON's escape introducer is not.
    for (index, expected) in spelling[..length].iter().enumerate() {
        let Some(actual) = bytes.get(index) else {
            return Spelling::Prefix;
        };
        #[cfg(test)]
        COMPARISONS.with(|count| count.set(count.get() + 1));
        if (index % 6 < 2 && actual != expected)
            || (index % 6 >= 2 && actual.to_ascii_lowercase() != *expected)
        {
            return Spelling::Different;
        }
    }
    Spelling::Complete(length)
}

#[cfg(test)]
mod tests {
    //! SMH-SPEC-SPEC0001: chunking, preservation, carry, and request memory bounds.
    use super::*;

    fn sanitize(credentials: &[String], chunks: &[&[u8]], complete: bool) -> Vec<u8> {
        let mut sanitizer = ResponseSanitizer::new(credentials, REPLACEMENT).unwrap();
        let mut output = Vec::new();
        for chunk in chunks {
            output.extend_from_slice(&sanitizer.push(chunk).unwrap());
            let bound = sanitizer
                .dictionary
                .as_ref()
                .map_or(CARRY_BYTES_MAX, |dictionary| {
                    dictionary.lookahead + dictionary.block_bytes
                });
            assert!(sanitizer.carry.len() <= bound);
        }
        if complete {
            output.extend_from_slice(&sanitizer.finish());
        }
        output
    }

    #[test]
    fn bytewise_near_match_work_is_linear() {
        for (count, length) in [(32, 1024), (8, 4096)] {
            let credentials: Vec<String> = (0..count)
                .map(|index| format!("{}{:02}", "a".repeat(length - 2), index))
                .collect();
            ResponseSanitizer::validate(&credentials).unwrap();
            for (encoded, repetitions) in [(false, 1), (true, 1), (false, 8), (true, 8)] {
                let wire = if encoded {
                    b"\\u0061".repeat(length * repetitions)
                } else {
                    vec![b'a'; length * repetitions]
                };
                COMPARISONS.with(|count| count.set(0));
                let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
                let mut output = Vec::new();
                for byte in &wire {
                    output.extend(sanitizer.push(std::slice::from_ref(byte)).unwrap());
                }
                output.extend(sanitizer.finish());
                assert_eq!(output, wire);
                let dictionary = sanitizer.dictionary.as_ref().unwrap();
                let comparisons = COMPARISONS.with(std::cell::Cell::get) + dictionary.comparisons();
                eprintln!(
                    "fixed {count}x{length}, encoded={encoded}, repetitions={repetitions}: {comparisons} comparisons/transition steps, {} input bytes",
                    wire.len()
                );
                assert!(
                    comparisons <= wire.len() as u64 * 256 + 65536,
                    "long-prefix work restarted: {comparisons}"
                );
            }
        }
    }

    #[test]
    fn ascii_dictionary_shares_raw_and_json_block_traversals() {
        let credentials = ["a".repeat(CREDENTIAL_BYTES_MAX), "x".repeat(65)];
        let sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
        assert!(sanitizer.dictionary.as_ref().unwrap().json.is_none());
        for spelling in [
            credentials[0].as_bytes().to_vec(),
            b"\\u0061".repeat(CREDENTIAL_BYTES_MAX),
        ] {
            let mut wire = vec![b'x'; 64];
            wire.push(b'!');
            let mut expected = wire.clone();
            wire.extend_from_slice(&spelling);
            wire.extend_from_slice(b":after");
            expected.extend_from_slice(REPLACEMENT);
            expected.extend_from_slice(b":after");
            for chunk_bytes in [1, 64, 4096, wire.len()] {
                assert_eq!(
                    sanitize(
                        &credentials,
                        &wire.chunks(chunk_bytes).collect::<Vec<_>>(),
                        true
                    ),
                    expected
                );
            }
        }
    }

    #[test]
    fn complete_large_raw_and_json_echoes_progress_before_finish() {
        let credential = "a".repeat(CREDENTIAL_BYTES_MAX);
        let credentials = [credential.clone()];
        for wire in [
            credential.into_bytes(),
            b"\\u0061".repeat(CREDENTIAL_BYTES_MAX),
        ] {
            let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
            let mut output = Vec::new();
            for byte in &wire {
                output.extend(sanitizer.push(std::slice::from_ref(byte)).unwrap());
            }
            assert_eq!(output, REPLACEMENT);
            assert!(sanitizer.finish().is_empty());
        }
    }

    #[test]
    fn short_matches_cannot_restart_failed_long_overlaps() {
        let credentials = [
            "a".into(),
            format!("{}00", "a".repeat(CREDENTIAL_BYTES_MAX - 2)),
        ];
        let wire = vec![b'a'; CREDENTIAL_BYTES_MAX * 2];
        COMPARISONS.with(|count| count.set(0));
        let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
        let mut output = sanitizer.push(&wire).unwrap();
        output.extend(sanitizer.finish());
        let dictionary = sanitizer.dictionary.as_ref().unwrap();
        let comparisons = COMPARISONS.with(std::cell::Cell::get) + dictionary.comparisons();
        assert_eq!(output, REPLACEMENT.repeat(wire.len()));
        assert!(
            comparisons <= wire.len() as u64 * 256 + 65536,
            "overlapping short completions restarted long scans: {comparisons}"
        );
    }

    #[test]
    fn large_dictionary_matches_raw_mixed_unicode_and_surrogate_spellings_at_every_split() {
        let prefix = "a".repeat(65);
        let tail = "a\"\\é😀/\u{7f}\u{85}\0z";
        let credentials = [format!("{prefix}{tail}"), prefix.clone()];
        for spelling in [
            format!("{prefix}{tail}"),
            format!(
                "{prefix}{}{}{}",
                r#"a\"\\\u00E9\ud83D\uDE00\/"#, "\u{7f}\u{85}", r#"\u0000z"#
            ),
            format!(
                "{}{}",
                "\\u0061".repeat(65),
                r#"\u0061\u0022\u005cé😀/\u007F\u0085\u0000\u007a"#
            ),
        ] {
            for force_block in [false, true] {
                let mut safe = b"safe:".to_vec();
                if force_block {
                    // A failed first frontier forces the later rich match through block DP.
                    safe.extend_from_slice(&[b'a'; 64]);
                    safe.push(b'!');
                }
                let mut wire = safe.clone();
                wire.extend_from_slice(spelling.as_bytes());
                let after = b":after".repeat(100);
                wire.extend_from_slice(&after);
                wire.push(0xff);
                let mut expected = safe;
                expected.extend_from_slice(REPLACEMENT);
                expected.extend_from_slice(&after);
                expected.push(0xff);
                for split in 0..=wire.len() {
                    assert_eq!(
                        sanitize(&credentials, &[&wire[..split], &wire[split..]], true),
                        expected
                    );
                }
                assert_eq!(
                    sanitize(&credentials, &wire.chunks(1).collect::<Vec<_>>(), true),
                    expected
                );
            }
        }
    }

    #[test]
    fn large_dictionary_does_not_delay_unrelated_public_packets() {
        let credentials = ["a".repeat(CREDENTIAL_BYTES_MAX)];
        let wire = b"public.".repeat(128);
        let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
        assert_eq!(sanitizer.push(&wire).unwrap(), wire);
        assert!(sanitizer.finish().is_empty());
    }

    #[test]
    fn large_dictionary_abort_discards_prefix_and_completion_preserves_truncated_escape() {
        let credentials = ["a".repeat(CREDENTIAL_BYTES_MAX)];
        let mut prefix = b"\\u0061".repeat(CREDENTIAL_BYTES_MAX - 1);
        prefix.extend_from_slice(b"\\u00");
        for chunk_bytes in [1, 7, 64, 4096, prefix.len()] {
            let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
            assert_eq!(sanitizer.push(b"safe:").unwrap(), b"safe:");
            for chunk in prefix.chunks(chunk_bytes) {
                assert!(sanitizer.push(chunk).unwrap().is_empty());
            }
            assert_eq!(sanitizer.finish(), prefix);
            assert!(sanitizer.finish().is_empty());
            assert_eq!(
                sanitize(&credentials, &[b"safe:", &prefix], false),
                b"safe:"
            );
        }
    }

    #[test]
    fn large_dictionary_preserves_escape_interior_matches_and_greedy_partition_law() {
        let credentials = vec![
            "x".repeat(65),
            "u0061b".into(),
            "31".into(),
            "1x".into(),
            "a\"\\é😀/z".into(),
            "abc".into(),
            "abcdef".into(),
        ];
        let mut wire = vec![b'x'; 64];
        wire.push(b'!');
        wire.extend_from_slice(
            &b"\\u0061\\u0062|3\\u0031x|abcdef|a\\\"\\\\\\u00E9\\ud83D\\uDE00\\/z|\xff\\uD800?"
                .repeat(12),
        );
        let mut reference = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
        reference.dictionary = None;
        let mut expected = reference.push(&wire).unwrap();
        expected.extend(reference.finish());
        for chunk_bytes in 1..=wire.len() {
            assert_eq!(
                sanitize(
                    &credentials,
                    &wire.chunks(chunk_bytes).collect::<Vec<_>>(),
                    true
                ),
                expected
            );
        }
    }

    #[test]
    fn every_partition_preserves_binary_unrelated_bytes_and_supported_spellings() {
        let credentials = ["a\"\\é😀/z".to_string()];
        for spelling in [
            "a\"\\é😀/z",
            r#"a\"\\\u00E9\ud83D\uDE00\/z"#,
            r#"\u0061\u0022\u005cé😀/\u007a"#,
        ] {
            let mut wire = b"\xff\0before:".to_vec();
            wire.extend_from_slice(spelling.as_bytes());
            wire.extend_from_slice(b":after\0\xfe");
            let expected = b"\xff\0before:<redacted>:after\0\xfe";
            // Exhaustive two-boundary partitions include empty, bytewise UTF-8,
            // short-escape, Unicode-escape and surrogate-pair fragments.
            for first in 0..=wire.len() {
                for second in first..=wire.len() {
                    assert_eq!(
                        sanitize(
                            &credentials,
                            &[&wire[..first], &wire[first..second], &wire[second..]],
                            true
                        ),
                        expected
                    );
                }
            }
            let chunks: Vec<_> = wire.chunks(1).collect();
            assert_eq!(sanitize(&credentials, &chunks, true), expected);
        }
    }

    #[test]
    fn json_literal_del_and_c1_controls_remain_valid_in_mixed_spellings() {
        let credentials = ["a\u{7f}\u{85}z".into()];
        let wire = "\\u0061\u{7f}\u{85}\\u007a".as_bytes();
        for split in 0..=wire.len() {
            assert_eq!(
                sanitize(&credentials, &[&wire[..split], &wire[split..]], true),
                REPLACEMENT
            );
        }
    }

    #[test]
    fn arbitrary_binary_bytes_without_matches_are_preserved_under_chunking() {
        let credentials = ["not-present".to_string()];
        let bytes: Vec<u8> = (0..=255).collect();
        for size in 1..=bytes.len() {
            assert_eq!(
                sanitize(&credentials, &bytes.chunks(size).collect::<Vec<_>>(), true),
                bytes
            );
        }
    }

    #[test]
    fn failed_streams_discard_unresolved_suffix_but_completion_classifies_it() {
        let credentials = ["credential".to_string()];
        for prefix in [
            b"cred".as_slice(),
            br"\u0063\u0072\u0065\u0064",
            br"\u0063\u00",
        ] {
            let chunks = [b"safe:".as_slice(), prefix];
            assert_eq!(sanitize(&credentials, &chunks, false), b"safe:");
            let mut expected = b"safe:".to_vec();
            expected.extend_from_slice(prefix);
            assert_eq!(sanitize(&credentials, &chunks, true), expected);
        }
    }

    #[test]
    fn longest_match_and_overlapping_prefixes_are_chunk_independent() {
        let credentials = ["abc".into(), "abcdef".into(), "bc".into(), "\\".into()];
        for split in 0..=12 {
            let wire = br"abcdef abc\\";
            assert_eq!(
                sanitize(&credentials, &[&wire[..split], &wire[split..]], true),
                b"<redacted> <redacted><redacted>"
            );
        }
    }

    #[test]
    fn bounds_are_finite_and_diagnostics_do_not_contain_inputs() {
        for credentials in [
            vec!["private".into(); CREDENTIAL_COUNT_MAX + 1],
            vec!["x".repeat(CREDENTIAL_BYTES_MAX + 1)],
            vec!["x".repeat(CREDENTIAL_BYTES_MAX); 9],
            vec![String::new()],
        ] {
            let error = ResponseSanitizer::new(&credentials, REPLACEMENT)
                .err()
                .unwrap();
            assert_eq!(error, "response sanitizer credential bounds exceeded");
        }
        let credentials = ["a".repeat(CREDENTIAL_BYTES_MAX)];
        let encoded = "\\u0061".repeat(CREDENTIAL_BYTES_MAX);
        let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
        assert!(
            sanitizer
                .push(&encoded.as_bytes()[..encoded.len() - 1])
                .unwrap()
                .is_empty()
        );
        assert_eq!(sanitizer.carry.len(), CARRY_BYTES_MAX - 1);
        assert_eq!(sanitizer.push(b"1").unwrap(), REPLACEMENT);
        assert!(sanitizer.finish().is_empty());
    }

    fn empty_dictionary_allocates_only_returned_bytes() {
        let (output, cost) = smith_alloc::measure(smith_alloc::Scope::KernelCall, || {
            let mut sanitizer = ResponseSanitizer::new(&[], REPLACEMENT).unwrap();
            let output = sanitizer.push(b"public!").unwrap();
            assert!(sanitizer.finish().is_empty());
            output
        });
        assert_eq!(output, b"public!");
        assert_eq!(cost.allocations, 1);
        assert_eq!(cost.bytes, 7);
    }

    #[cfg(target_arch = "x86_64")]
    fn large_dictionary_layout_and_allocation_cost_are_exact() {
        assert_eq!(std::mem::size_of::<Dictionary>(), 184);
        assert_eq!(std::mem::size_of::<MatchingStage>(), 1);
        let credentials: Vec<String> = (0..8)
            .map(|index| format!("{}{:02}", "a".repeat(4094), index))
            .collect();
        let (mut sanitizer, construction) =
            smith_alloc::measure(smith_alloc::Scope::KernelCall, || {
                ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap()
            });
        let wire = vec![b'a'; 4096];
        let (output, streaming) = smith_alloc::measure(smith_alloc::Scope::KernelCall, || {
            let mut output = sanitizer.push(&wire).unwrap();
            output.extend(sanitizer.finish());
            output
        });
        assert_eq!(output, wire);
        assert_eq!(construction.allocations, 33);
        assert_eq!(construction.bytes, 3_092_912);
        assert_eq!(construction.peak, 2_654_428);
        assert_eq!(streaming.allocations, 15);
        assert_eq!(streaming.bytes, 53_308);
        assert_eq!(streaming.peak, 45_124);
    }

    #[test]
    fn request_layout_and_allocation_cost_are_exact() {
        empty_dictionary_allocates_only_returned_bytes();
        #[cfg(target_arch = "x86_64")]
        large_dictionary_layout_and_allocation_cost_are_exact();
        #[cfg(target_arch = "x86_64")]
        assert_eq!(std::mem::size_of::<ResponseSanitizer<'_>>(), 64);
        let credentials = ["credential".into()];
        let (output, cost) = smith_alloc::measure(smith_alloc::Scope::KernelCall, || {
            let mut sanitizer = ResponseSanitizer::new(&credentials, REPLACEMENT).unwrap();
            let output = sanitizer.push(b"public!").unwrap();
            assert!(sanitizer.finish().is_empty());
            output
        });
        assert_eq!(output, b"public!");
        assert_eq!(cost.allocations, 2);
        assert_eq!(cost.bytes, 16);
    }
}