oxide_regexp/unicode/
mod.rs

1//! Checksum-pinned Unicode 17 primitives used by the JavaScript lexer, the
2//! regular-expression compiler and the String intrinsics.
3//!
4//! QuickJS stores binary Unicode properties as alternating run lengths with a
5//! sparse 32-byte-block index. Keeping that representation avoids silently
6//! inheriting the Rust toolchain or host ICU Unicode version while preserving
7//! the pinned engine's exact table boundaries.
8
9mod ident_tables {
10    include!("generated/unicode/unicode_ident_tables.rs");
11}
12
13/// QuickJS reserves 30 bits for a string's UTF-16 code-unit length; case
14/// conversion and normalization never produce a longer result.
15pub const MAX_STRING_LEN: usize = (1 << 30) - 1;
16
17/// Why case conversion or normalization produced no string.
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub enum StringError {
20    /// The result would exceed the caller's length limit.
21    TooLong,
22    /// A buffer reservation failed.
23    OutOfMemory,
24}
25
26/// A produced string in its narrowest storage, as QuickJS's `StringBuffer`
27/// leaves it: Latin-1 bytes until a wider code unit arrives, then UTF-16.
28#[derive(Clone, Debug, Eq, PartialEq)]
29pub enum CodeUnitBuf {
30    Latin1(Vec<u8>),
31    Utf16(Vec<u16>),
32}
33
34impl CodeUnitBuf {
35    /// The UTF-16 code units, widening Latin-1 storage.
36    #[must_use]
37    pub fn to_utf16(&self) -> Vec<u16> {
38        match self {
39            Self::Latin1(units) => units.iter().copied().map(u16::from).collect(),
40            Self::Utf16(units) => units.clone(),
41        }
42    }
43}
44
45/// String input as UTF-16 code units: `[u16]`, or `[u8]` holding Latin-1
46/// code units (each byte is one code unit below U+0100).
47pub trait CodeUnits {
48    /// The number of UTF-16 code units.
49    fn unit_len(&self) -> usize;
50    /// The code unit at `index`, or `None` past the end.
51    fn unit_at(&self, index: usize) -> Option<u16>;
52    /// Whether every code unit is below U+0100.
53    fn all_latin1(&self) -> bool;
54}
55
56impl CodeUnits for [u16] {
57    #[inline]
58    fn unit_len(&self) -> usize {
59        self.len()
60    }
61
62    #[inline]
63    fn unit_at(&self, index: usize) -> Option<u16> {
64        self.get(index).copied()
65    }
66
67    fn all_latin1(&self) -> bool {
68        self.iter().all(|unit| *unit < 0x100)
69    }
70}
71
72impl CodeUnits for [u8] {
73    #[inline]
74    fn unit_len(&self) -> usize {
75        self.len()
76    }
77
78    #[inline]
79    fn unit_at(&self, index: usize) -> Option<u16> {
80        self.get(index).copied().map(u16::from)
81    }
82
83    fn all_latin1(&self) -> bool {
84        true
85    }
86}
87
88const INDEX_BLOCK_LEN: usize = 32;
89const CODE_MASK: u32 = (1 << 21) - 1;
90
91#[must_use]
92pub fn is_id_start(code_point: u32) -> bool {
93    is_in_table(
94        code_point,
95        &ident_tables::ID_START_TABLE,
96        &ident_tables::ID_START_INDEX,
97    )
98}
99
100#[must_use]
101pub fn is_id_continue(code_point: u32) -> bool {
102    is_id_start(code_point)
103        || is_in_table(
104            code_point,
105            &ident_tables::ID_CONTINUE_TABLE,
106            &ident_tables::ID_CONTINUE_INDEX,
107        )
108}
109
110fn is_in_table(code_point: u32, table: &[u8], index: &[u8]) -> bool {
111    let Some((mut code, mut position)) = index_position(code_point, index) else {
112        return false;
113    };
114    let mut included = false;
115    loop {
116        let byte = table[position];
117        position += 1;
118        if byte < 0x40 {
119            code += u32::from(byte >> 3) + 1;
120            if code_point < code {
121                return included;
122            }
123            included = !included;
124            code += u32::from(byte & 7) + 1;
125        } else if byte >= 0x80 {
126            code += u32::from(byte - 0x80) + 1;
127        } else if byte < 0x60 {
128            code += (u32::from(byte - 0x40) << 8) | u32::from(table[position]);
129            code += 1;
130            position += 1;
131        } else {
132            code += (u32::from(byte - 0x60) << 16)
133                | (u32::from(table[position]) << 8)
134                | u32::from(table[position + 1]);
135            code += 1;
136            position += 2;
137        }
138        if code_point < code {
139            return included;
140        }
141        included = !included;
142    }
143}
144
145fn index_position(code_point: u32, index: &[u8]) -> Option<(u32, usize)> {
146    debug_assert!(!index.is_empty() && index.len().is_multiple_of(3));
147    let entry_count = index.len() / 3;
148    let first = read_u24(index, 0);
149    let first_code = first & CODE_MASK;
150    if code_point < first_code {
151        return Some((0, 0));
152    }
153
154    let last = read_u24(index, entry_count - 1);
155    if code_point >= last & CODE_MASK {
156        return None;
157    }
158
159    let mut lower = 0;
160    let mut upper = entry_count - 1;
161    while upper - lower > 1 {
162        let middle = (upper + lower) / 2;
163        if code_point < read_u24(index, middle) & CODE_MASK {
164            upper = middle;
165        } else {
166            lower = middle;
167        }
168    }
169    let entry = read_u24(index, lower);
170    let code = entry & CODE_MASK;
171    let position = (lower + 1) * INDEX_BLOCK_LEN + (entry >> 21) as usize;
172    Some((code, position))
173}
174
175fn read_u24(index: &[u8], entry: usize) -> u32 {
176    let offset = entry * 3;
177    u32::from(index[offset])
178        | (u32::from(index[offset + 1]) << 8)
179        | (u32::from(index[offset + 2]) << 16)
180}
181
182#[cfg(test)]
183mod tests {
184    use super::{is_id_continue, is_id_start};
185
186    /// FNV-1a step over one little-endian `u32`, shared by the table
187    /// fingerprint tests that compare against pinned QuickJS C output.
188    pub(super) fn hash_u32(mut hash: u64, value: u32) -> u64 {
189        for byte in value.to_le_bytes() {
190            hash ^= u64::from(byte);
191            hash = hash.wrapping_mul(1_099_511_628_211);
192        }
193        hash
194    }
195
196    #[test]
197    fn unicode_17_identifier_tables_have_pinned_counts_and_boundaries() {
198        let mut start_count = 0;
199        let mut continue_count = 0;
200        for code_point in 0..=0x10_ffff {
201            let start = is_id_start(code_point);
202            let continuation = is_id_continue(code_point);
203            assert!(!start || continuation, "U+{code_point:04X}");
204            start_count += usize::from(start);
205            continue_count += usize::from(continuation);
206        }
207        assert_eq!(start_count, 145_916);
208        assert_eq!(continue_count, 149_240);
209
210        for code_point in [0x03c0, 0x10400, 0x33479] {
211            assert!(is_id_start(code_point), "U+{code_point:04X}");
212        }
213        for code_point in [0x0024, 0x0030, 0x0300, 0x1f600, 0x3347a] {
214            assert!(!is_id_start(code_point), "U+{code_point:04X}");
215        }
216        for code_point in [0x0030, 0x005f, 0x0300, 0x200c, 0x200d] {
217            assert!(is_id_continue(code_point), "U+{code_point:04X}");
218        }
219    }
220}
221
222pub mod case;
223pub mod normalize;
224pub mod property;
oxide_regexp/unicode/mod.rs

oxide_regexp/unicode/
mod.rs
