submilli_engine/
property_keys.rs

1//! Property-name domains shared by index signatures and template literal types.
2use crate::Type;
3use crate::type_size::{TypeLimits, TypeTooLarge};
4
5pub fn matches_name(domain: &Type, name: &str, limits: &TypeLimits) -> bool {
6    if !limits.spend_work(name.len() as u64) {
7        return false;
8    }
9    let Ok(units) = crate::literal_units::try_literal_units(name) else {
10        limits.record(TypeTooLarge::Allocation);
11        return false;
12    };
13    let result = matches_units(domain, &units, false, &mut |work| {
14        limits
15            .spend_work(work)
16            .then_some(())
17            .ok_or(TypeTooLarge::Work)
18    });
19    match result {
20        Ok(value) => value,
21        Err(MatchError::Work(error)) => {
22            limits.record(error);
23            false
24        }
25        Err(MatchError::Allocation) => {
26            limits.record(TypeTooLarge::Allocation);
27            false
28        }
29    }
30}
31
32pub fn canonical_number(name: &str) -> bool {
33    name.parse::<f64>()
34        .is_ok_and(|number| crate::runtime::number::format_number_js(number) == name)
35}
36
37#[derive(Debug)]
38pub enum MatchError<E> {
39    Work(E),
40    Allocation,
41}
42
43/// Every scan and candidate comparison is charged before it runs. Template
44/// matching uses TypeScript's first-delimiter split, including one UTF-16
45/// unit for an empty delimiter between adjacent substitutions.
46pub fn matches_units<E>(
47    domain: &Type,
48    units: &[u16],
49    substitution: bool,
50    charge: &mut impl FnMut(u64) -> Result<(), E>,
51) -> Result<bool, MatchError<E>> {
52    charge(1).map_err(MatchError::Work)?;
53    Ok(match domain.peel() {
54        Type::String => true,
55        Type::StringLiteral(value) => {
56            charge(value.len() as u64).map_err(MatchError::Work)?;
57            literal_units(value)?.as_slice() == units
58        }
59        Type::Number | Type::NumberLiteral(_) => {
60            charge(units.len() as u64).map_err(MatchError::Work)?;
61            let Some(text) = decode_units(units)? else {
62                return Ok(false);
63            };
64            match domain.peel() {
65                Type::NumberLiteral(value) => {
66                    crate::runtime::number::format_number_js(value.0) == text
67                }
68                _ if substitution => {
69                    !text.is_empty()
70                        && crate::runtime::number::string_to_number_js(&text).is_finite()
71                }
72                _ => canonical_number(&text),
73            }
74        }
75        Type::BigInt | Type::BigIntLiteral(_) if substitution => {
76            charge(units.len() as u64).map_err(MatchError::Work)?;
77            let Some(text) = decode_units(units)? else {
78                return Ok(false);
79            };
80            match domain.peel() {
81                Type::BigIntLiteral(value) => value == &text,
82                _ => bigint_text(&text),
83            }
84        }
85        Type::Boolean if substitution => {
86            units == [116, 114, 117, 101] || units == [102, 97, 108, 115, 101]
87        }
88        Type::BooleanLiteral(value) if substitution => {
89            value.to_string().encode_utf16().eq(units.iter().copied())
90        }
91        Type::Null if substitution => units == [110, 117, 108, 108],
92        Type::Undefined if substitution => units == [117, 110, 100, 101, 102, 105, 110, 101, 100],
93        Type::Union(members) => {
94            for member in members {
95                if matches_units(member, units, substitution, charge)? {
96                    return Ok(true);
97                }
98            }
99            false
100        }
101        Type::TemplateLiteral {
102            parts,
103            substitutions,
104        } => matches_template(parts, substitutions, units, charge)?,
105        _ => false,
106    })
107}
108
109fn matches_template<E>(
110    parts: &[String],
111    substitutions: &[Type],
112    units: &[u16],
113    charge: &mut impl FnMut(u64) -> Result<(), E>,
114) -> Result<bool, MatchError<E>> {
115    let Some(first) = parts.first() else {
116        return Ok(false);
117    };
118    if substitutions.is_empty() {
119        return matches_units(&Type::StringLiteral(first.clone()), units, false, charge);
120    }
121    let Some(last) = parts.last() else {
122        return Ok(false);
123    };
124    charge(first.len().saturating_add(last.len()) as u64).map_err(MatchError::Work)?;
125    let prefix = literal_units(first)?;
126    let suffix = literal_units(last)?;
127    if units.len() < prefix.len().saturating_add(suffix.len())
128        || !units.starts_with(&prefix)
129        || !units.ends_with(&suffix)
130    {
131        return Ok(false);
132    }
133    let remaining_end = units.len() - suffix.len();
134    let mut position = prefix.len();
135    for (index, hole) in substitutions.iter().enumerate() {
136        let last_hole = index.saturating_add(1) == substitutions.len();
137        let (end, delimiter_length) = if last_hole {
138            (remaining_end, 0)
139        } else {
140            let Some(delimiter) = parts.get(index.saturating_add(1)) else {
141                return Ok(false);
142            };
143            charge(delimiter.len() as u64).map_err(MatchError::Work)?;
144            let delimiter = literal_units(delimiter)?;
145            if delimiter.is_empty() {
146                if position >= remaining_end {
147                    return Ok(false);
148                }
149                (position + 1, 0)
150            } else {
151                let mut found = None;
152                for candidate in position..=remaining_end {
153                    charge(delimiter.len() as u64).map_err(MatchError::Work)?;
154                    if units
155                        .get(candidate..remaining_end)
156                        .is_some_and(|tail| tail.starts_with(&delimiter))
157                    {
158                        found = Some(candidate);
159                        break;
160                    }
161                }
162                let Some(end) = found else {
163                    return Ok(false);
164                };
165                (end, delimiter.len())
166            }
167        };
168        let Some(value) = units.get(position..end) else {
169            return Ok(false);
170        };
171        if !matches_units(hole, value, true, charge)? {
172            return Ok(false);
173        }
174        position = end.saturating_add(delimiter_length);
175    }
176    Ok(true)
177}
178
179fn literal_units<E>(text: &str) -> Result<Vec<u16>, MatchError<E>> {
180    crate::literal_units::try_literal_units(text).map_err(|_| MatchError::Allocation)
181}
182
183fn decode_units<E>(units: &[u16]) -> Result<Option<String>, MatchError<E>> {
184    let capacity = units.len().checked_mul(3).ok_or(MatchError::Allocation)?;
185    let mut text = String::new();
186    text.try_reserve(capacity)
187        .map_err(|_| MatchError::Allocation)?;
188    for scalar in char::decode_utf16(units.iter().copied()) {
189        let Ok(scalar) = scalar else {
190            return Ok(None);
191        };
192        text.push(scalar);
193    }
194    Ok(Some(text))
195}
196
197fn bigint_text(text: &str) -> bool {
198    let text = text.strip_prefix('-').unwrap_or(text);
199    let (digits, radix) =
200        if let Some(digits) = text.strip_prefix("0x").or_else(|| text.strip_prefix("0X")) {
201            (digits, 16)
202        } else if let Some(digits) = text.strip_prefix("0o").or_else(|| text.strip_prefix("0O")) {
203            (digits, 8)
204        } else if let Some(digits) = text.strip_prefix("0b").or_else(|| text.strip_prefix("0B")) {
205            (digits, 2)
206        } else {
207            (text, 10)
208        };
209    !digits.is_empty()
210        && (radix != 10 || digits.len() == 1 || !digits.starts_with('0'))
211        && digits
212            .chars()
213            .all(|digit| digit.is_ascii() && digit.is_digit(radix))
214}
215
216pub fn pattern(ty: &Type) -> Option<String> {
217    match ty.peel() {
218        Type::String => Some("[\\s\\S]*".into()),
219        Type::Number => Some(r"[+-]?(?:[0-9]+(?:\.[0-9]*)?|\.[0-9]+)(?:[eE][+-]?[0-9]+)?".into()),
220        Type::BigInt => Some(r"-?(?:[0-9]+|0[xX][0-9a-fA-F]+|0[oO][0-7]+|0[bB][01]+)".into()),
221        Type::BigIntLiteral(value) => Some(regex::escape(value)),
222        Type::Null => Some("null".into()),
223        Type::Undefined => Some("undefined".into()),
224        Type::StringLiteral(value) => Some(literal_pattern(value)),
225        Type::NumberLiteral(value) => Some(regex::escape(
226            &crate::runtime::number::format_number_js(value.0),
227        )),
228        Type::BooleanLiteral(value) => Some(value.to_string()),
229        Type::Boolean => Some("(?:true|false)".into()),
230        Type::Union(members) => Some(format!(
231            "(?:{})",
232            members
233                .iter()
234                .map(pattern)
235                .collect::<Option<Vec<_>>>()?
236                .join("|")
237        )),
238        Type::TemplateLiteral {
239            parts,
240            substitutions,
241        } => {
242            if parts.len() != substitutions.len().checked_add(1)? {
243                return None;
244            }
245            let mut result = String::new();
246            for (position, part) in parts.iter().enumerate() {
247                result.push_str(&literal_pattern(part));
248                if let Some(substitution) = substitutions.get(position) {
249                    if position + 1 < substitutions.len() && parts.get(position + 1)?.is_empty() {
250                        if !matches!(substitution.peel(), Type::String) {
251                            return None;
252                        }
253                        result.push_str("[\\s\\S]");
254                    } else {
255                        result.push_str(&pattern(substitution)?);
256                    }
257                }
258            }
259            Some(result)
260        }
261        _ => None,
262    }
263}
264
265fn literal_pattern(text: &str) -> String {
266    let mut result = String::new();
267    for unit in crate::literal_units::literal_units(text) {
268        result.push_str(&format!("\\u{unit:04x}"));
269    }
270    result
271}
272
273/// Runtime matching needs the domain, not source alias names. Keeping aliases
274/// here would consume the JSON decoder's nesting budget without adding meaning.
275pub fn runtime_domain(ty: &Type) -> Result<Type, TypeTooLarge> {
276    fn simplify(
277        ty: &Type,
278        depth: u32,
279        budget: &mut crate::type_size::TypeBudget<'_>,
280    ) -> Result<Type, TypeTooLarge> {
281        budget.charge(depth)?;
282        let simplified = crate::type_size::map_children(ty.peel(), |child| {
283            simplify(child, depth.saturating_add(1), budget)
284        })?;
285        let simplified = match simplified {
286            Type::Union(members) => Type::union(members),
287            other => other,
288        };
289        normalize_template(simplified, budget)
290    }
291    let limits = TypeLimits::default();
292    simplify(ty, 1, &mut limits.budget())
293}
294
295/// Collapse literal holes and distribute union holes before matching, as
296/// TypeScript does when constructing a template type. Expansion consumes the
297/// same budget as substitution, including the text copied into every branch.
298pub fn normalize_template(
299    ty: Type,
300    budget: &mut crate::type_size::TypeBudget<'_>,
301) -> Result<Type, TypeTooLarge> {
302    let Type::TemplateLiteral {
303        parts,
304        substitutions,
305    } = ty
306    else {
307        return Ok(ty);
308    };
309    if parts.len() != substitutions.len().saturating_add(1) {
310        return Err(TypeTooLarge::InvalidTemplate);
311    }
312    let first = parts.first().ok_or(TypeTooLarge::InvalidTemplate)?;
313    budget.charge_work(first.len() as u64)?;
314    let mut builders = vec![TemplateBuilder {
315        first: first.clone(),
316        holes: Vec::new(),
317    }];
318    for (hole, suffix) in substitutions.into_iter().zip(parts.into_iter().skip(1)) {
319        let alternatives = match hole.peel() {
320            Type::Union(members) => members.clone(),
321            Type::Boolean => vec![Type::BooleanLiteral(false), Type::BooleanLiteral(true)],
322            Type::Never => return Ok(Type::Never),
323            _ => vec![hole],
324        };
325        let mut expanded = Vec::new();
326        for builder in builders {
327            for alternative in &alternatives {
328                budget.charge(1)?;
329                budget.charge_work(
330                    (builder.first.len() as u64)
331                        .saturating_add(
332                            builder
333                                .holes
334                                .iter()
335                                .map(|hole| hole.suffix.len() as u64)
336                                .sum::<u64>(),
337                        )
338                        .saturating_add(suffix.len() as u64),
339                )?;
340                for hole in &builder.holes {
341                    budget.charge_copy(&hole.ty, 1)?;
342                }
343                budget.charge_copy(alternative, 1)?;
344                let mut next = builder.clone();
345                next.append(alternative, &suffix)?;
346                expanded.push(next);
347            }
348        }
349        builders = expanded;
350    }
351    Ok(Type::union(
352        builders.into_iter().map(TemplateBuilder::finish).collect(),
353    ))
354}
355
356#[derive(Clone)]
357struct TemplateBuilder {
358    first: String,
359    holes: Vec<TemplateHole>,
360}
361
362#[derive(Clone)]
363struct TemplateHole {
364    ty: Type,
365    suffix: String,
366}
367
368impl TemplateBuilder {
369    fn tail(&mut self) -> &mut String {
370        match self.holes.last_mut() {
371            Some(hole) => &mut hole.suffix,
372            None => &mut self.first,
373        }
374    }
375
376    fn append(&mut self, hole: &Type, suffix: &str) -> Result<(), TypeTooLarge> {
377        let literal = match hole.peel() {
378            Type::StringLiteral(text) | Type::BigIntLiteral(text) => Some(text.clone()),
379            Type::NumberLiteral(value) => Some(crate::runtime::number::format_number_js(value.0)),
380            Type::BooleanLiteral(value) => Some(value.to_string()),
381            Type::Null => Some("null".into()),
382            Type::Undefined => Some("undefined".into()),
383            _ => None,
384        };
385        if let Some(literal) = literal {
386            crate::literal_units::push_literal_text(self.tail(), &literal);
387            crate::literal_units::push_literal_text(self.tail(), suffix);
388        } else if let Type::TemplateLiteral {
389            parts,
390            substitutions,
391        } = hole.peel()
392        {
393            if parts.len() != substitutions.len().saturating_add(1) {
394                return Err(TypeTooLarge::InvalidTemplate);
395            }
396            let first = parts.first().ok_or(TypeTooLarge::InvalidTemplate)?;
397            crate::literal_units::push_literal_text(self.tail(), first);
398            self.holes
399                .extend(
400                    substitutions
401                        .iter()
402                        .zip(parts.iter().skip(1))
403                        .map(|(ty, suffix)| TemplateHole {
404                            ty: ty.clone(),
405                            suffix: suffix.clone(),
406                        }),
407                );
408            crate::literal_units::push_literal_text(self.tail(), suffix);
409        } else {
410            self.holes.push(TemplateHole {
411                ty: hole.clone(),
412                suffix: suffix.into(),
413            });
414        }
415        Ok(())
416    }
417
418    fn finish(self) -> Type {
419        if self.holes.is_empty() {
420            return Type::StringLiteral(self.first);
421        }
422        if self.first.is_empty()
423            && self
424                .holes
425                .iter()
426                .all(|hole| hole.suffix.is_empty() && matches!(hole.ty.peel(), Type::String))
427        {
428            return Type::String;
429        }
430        let (substitutions, suffixes): (Vec<_>, Vec<_>) = self
431            .holes
432            .into_iter()
433            .map(|hole| (hole.ty, hole.suffix))
434            .unzip();
435        let parts = std::iter::once(self.first).chain(suffixes).collect();
436        Type::TemplateLiteral {
437            parts,
438            substitutions,
439        }
440    }
441}
442
443#[cfg(test)]
444mod tests {
445    use super::*;
446
447    fn template(parts: &[&str], substitutions: Vec<Type>) -> Type {
448        Type::TemplateLiteral {
449            parts: parts.iter().map(ToString::to_string).collect(),
450            substitutions,
451        }
452    }
453
454    #[test]
455    fn numeric_names_use_canonical_javascript_spelling() {
456        for name in ["0", "1.5", "1e+21", "NaN", "Infinity", "-Infinity"] {
457            assert!(canonical_number(name), "{name}");
458        }
459        for name in ["-0", "01", "1e21", " 1", "0x10", ""] {
460            assert!(!canonical_number(name), "{name}");
461        }
462    }
463
464    #[test]
465    fn template_matching_uses_typescript_splits_and_numeric_syntax() {
466        let limits = TypeLimits::default();
467        let numeric = template(&["n_", ""], vec![Type::Number]);
468        for name in ["n_ ", "n_0x10", "n_-0", "n_1.5"] {
469            assert!(matches_name(&numeric, name, &limits), "{name}");
470        }
471        for name in ["n_", "n_NaN", "n_Infinity", "n_1e999"] {
472            assert!(!matches_name(&numeric, name, &limits), "{name}");
473        }
474        assert!(!matches_name(
475            &template(&["", "", ""], vec![Type::String, Type::Number]),
476            "xx42",
477            &limits
478        ));
479        assert!(!matches_name(
480            &template(&["", "_", ""], vec![Type::String, Type::Number]),
481            "a_b_2",
482            &limits
483        ));
484        let bigint = template(&["", ""], vec![Type::BigInt]);
485        assert!(matches_name(&bigint, "-0x10", &limits));
486        assert!(!matches_name(&bigint, "01", &limits));
487        assert!(!matches_name(&bigint, "+1", &limits));
488    }
489
490    #[test]
491    fn matching_preserves_lone_surrogates_and_stops_when_work_is_refused() {
492        let domain = template(&["id_", ""], vec![Type::String]);
493        let units = [105, 100, 95, 0xd800];
494        assert!(matches_units(&domain, &units, false, &mut |_| Ok::<_, ()>(())).unwrap());
495        assert!(matches!(
496            matches_units(&domain, &units, false, &mut |_| Err(())),
497            Err(MatchError::Work(()))
498        ));
499    }
500
501    #[test]
502    fn normalization_joins_literal_holes_and_checks_shape_and_work() {
503        let limits = TypeLimits::default();
504        let result = normalize_template(
505            template(
506                &["id_", "", ""],
507                vec![Type::StringLiteral("abc".into()), Type::Number],
508            ),
509            &mut limits.budget(),
510        )
511        .unwrap();
512        assert!(matches_name(&result, "id_abc12", &limits));
513        assert!(
514            normalize_template(
515                template(&["missing suffix"], vec![Type::Number]),
516                &mut limits.budget()
517            )
518            .is_err()
519        );
520        let exhausted = TypeLimits::with_work_allowance(0);
521        assert!(
522            normalize_template(
523                template(&["prefix", ""], vec![Type::String]),
524                &mut exhausted.budget()
525            )
526            .is_err()
527        );
528    }
529}
submilli_engine/property_keys.rs

submilli_engine/
property_keys.rs
