normalize.rs
raw
//! 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());
}
}