642d5a256791
lex.rs
//! A small, forgiving JavaScript tokenizer.
//!
//! It never fails: unterminated strings, comments and templates just end at the end of input. It
//! serves two jobs: estimating how deeply a source nests before we hand it to the real parser
//! (whose recursion is unbounded), and extracting facts when parsing is refused or fails.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokKind {
Ident,
Str,
/// One chunk of a template literal (between backticks / `${` / `}`).
Template,
Number,
Punct,
Regex,
Comment,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Token<'a> {
pub kind: TokKind,
/// Raw source text of the token (quotes included for strings).
pub text: &'a str,
pub offset: usize,
/// A `/…/` after `yield`, where the same text is a regex in a generator and division in
/// sloppy code; the nesting estimate counts the brackets inside it, since they may be code.
pub ambiguous_regex: bool,
}
const PUNCTS: &[&str] = &[
">>>=", "...", "===", "!==", "**=", "<<=", ">>=", ">>>", "&&=", "||=", "??=", "=>", "==", "!=", "<=", ">=", "&&", "||", "??", "?.", "++", "--", "+=", "-=",
"*=", "/=", "%=", "&=", "|=", "^=", "**", "<<", ">>",
];
/// Words after which `/` starts a regex. `yield` is handled separately: in a generator it starts
/// a regex, but in sloppy code it is an identifier and `/` divides, so a regex there is read only
/// when one closes on the line and its brackets are counted too.
const REGEX_AFTER_KEYWORDS: &[&str] = &["return", "typeof", "instanceof", "in", "of", "new", "delete", "void", "throw", "case", "do", "else", "await"];
/// Words after which `++`/`--` starts an expression instead of updating a value. Missing one
/// would under-count, so this list errs towards treating a word as expression-starting.
const EXPRESSION_KEYWORDS: &[&str] = &[
"return",
"throw",
"typeof",
"void",
"delete",
"await",
"new",
"in",
"instanceof",
"of",
"yield",
"case",
"do",
"else",
"if",
"for",
"while",
"with",
"var",
"let",
"const",
"class",
"extends",
"function",
"default",
"import",
"export",
];
fn is_ident_start(b: u8) -> bool {
b.is_ascii_alphabetic() || b == b'_' || b == b'$' || b == b'\\' || b >= 0x80
}
fn is_ident_part(b: u8) -> bool {
is_ident_start(b) || b.is_ascii_digit()
}
/// Byte length of the JavaScript whitespace character at `offset` that isn't plain ASCII
/// whitespace (the vertical tab, no-break space, byte-order mark and the other space separators),
/// or 0.
fn other_space_len(src: &str, offset: usize) -> usize {
match src.as_bytes().get(offset) {
Some(0x0b) => 1,
Some(&c) if c >= 0x80 => src
.get(offset..)
.and_then(|rest| rest.chars().next())
.filter(|c| matches!(c, '\u{a0}' | '\u{1680}' | '\u{2000}'..='\u{200a}' | '\u{202f}' | '\u{205f}' | '\u{3000}' | '\u{feff}'))
.map_or(0, char::len_utf8),
_ => 0,
}
}
fn line_terminator_len(src: &str, offset: usize) -> usize {
match src.as_bytes().get(offset) {
Some(b'\n' | b'\r') => 1,
Some(0xe2) if src.get(offset..).is_some_and(|rest| rest.starts_with('\u{2028}') || rest.starts_with('\u{2029}')) => 3,
_ => 0,
}
}
/// The same for a byte slice: LF, CR, U+2028 or U+2029 at `i`; 0 when there is none.
fn line_terminator_bytes(bytes: &[u8], i: usize) -> usize {
match bytes.get(i) {
Some(b'\n' | b'\r') => 1,
Some(0xe2) if bytes.get(i + 1) == Some(&0x80) && matches!(bytes.get(i + 2), Some(0xa8 | 0xa9)) => 3,
_ => 0,
}
}
/// Tokenize `src`, stopping after `max_tokens` (the flag says whether it stopped early).
pub fn tokenize(src: &str, max_tokens: usize) -> (Vec<Token<'_>>, bool) {
let mut out = Vec::new();
let truncated = scan(src, max_tokens, |t| out.push(t));
(out, truncated)
}
/// What a scan found besides the tokens.
#[derive(Debug, Clone, Copy, Default)]
pub(crate) struct Scanned {
/// `max_tokens` stopped the scan.
pub truncated: bool,
/// The shared `yield /…/` lookahead budget ran out before a line ended, so whether those
/// slashes are regexes or division is unknown; admission fails closed.
pub lookahead_exhausted: bool,
/// A `yield /…/` read as a regex hides division token boundaries: a quote or backtick inside
/// it, or a following `/`, `++` or `--`; admission fails closed.
pub ambiguous_boundaries: bool,
}
/// Stream tokens to `emit` without storing them. Returns true when `max_tokens` stopped it.
pub fn scan<'a>(src: &'a str, max_tokens: usize, emit: impl FnMut(Token<'a>)) -> bool {
scan_checked(src, max_tokens, emit).truncated
}
pub(crate) fn scan_checked<'a>(src: &'a str, max_tokens: usize, mut emit: impl FnMut(Token<'a>)) -> Scanned {
let b = src.as_bytes();
let mut lookahead_exhausted = false;
let mut ambiguous_boundaries = false;
// Set after a `yield /…/` read as a regex: the division reading ends in a `/` token instead,
// so the next `/`, `++` or `--` would be classified differently.
let mut after_ambiguous_regex = false;
let mut count = 0usize;
let mut i = 0usize;
// true = this brace opened a template substitution `${`.
let mut braces: Vec<bool> = Vec::new();
let slice = |a: usize, z: usize| src.get(a..z).unwrap_or("");
let mut last_sig: Option<(TokKind, &str)> = None;
// Whether the last token was a name after `.`/`?.`: `x.of /` divides, it does not start a regex.
let mut last_member = false;
// Bytes left for `yield /…/` lookahead across this source; keeps hostile input linear.
let mut lookahead_left = b.len();
while i < b.len() {
let c = b.get(i).copied().unwrap_or(0);
if c.is_ascii_whitespace() {
i += 1;
continue;
}
let line_end = line_terminator_len(src, i);
if line_end != 0 {
i += line_end;
continue;
}
let space = other_space_len(src, i);
if space != 0 {
i += space;
continue;
}
if count >= max_tokens {
return Scanned { truncated: true, lookahead_exhausted, ambiguous_boundaries };
}
count += 1;
let start = i;
let next = b.get(i + 1).copied().unwrap_or(0);
// Comments.
if c == b'/' && next == b'/' {
while i < b.len() && line_terminator_len(src, i) == 0 {
i += 1;
}
emit(Token { kind: TokKind::Comment, text: slice(start, i), offset: start, ambiguous_regex: false });
continue;
}
if c == b'/' && next == b'*' {
i += 2;
while i < b.len() && !(b.get(i) == Some(&b'*') && b.get(i + 1) == Some(&b'/')) {
i += 1;
}
i = (i + 2).min(b.len());
emit(Token { kind: TokKind::Comment, text: slice(start, i), offset: start, ambiguous_regex: false });
continue;
}
if after_ambiguous_regex {
// Comments above keep the flag: the next real token decides. The flag is replaced by
// this token's own state at the end of the iteration.
let diverges = (c == b'/' && next != b'/' && next != b'*') || ((c == b'+' || c == b'-') && next == c);
ambiguous_boundaries |= diverges;
}
let tok_kind;
let mut ambiguous_regex = false;
let slash = if c == b'/' { regex_start(last_sig, last_member) } else { RegexStart::No };
let ambiguous_close = if slash == RegexStart::Ambiguous {
match regex_closes(b, i + 1, &mut lookahead_left) {
RegexCloses::Closes => true,
RegexCloses::No => false,
RegexCloses::Exhausted => {
lookahead_exhausted = true;
false
}
}
} else {
false
};
if c == b'"' || c == b'\'' {
i += 1;
while let Some(&d) = b.get(i) {
i += 1;
if d == b'\\' {
i += if b.get(i) == Some(&b'\r') && b.get(i + 1) == Some(&b'\n') { 2 } else { 1 };
} else if d == c || d == b'\n' {
break;
}
}
i = i.min(b.len());
tok_kind = TokKind::Str;
} else if c == b'`' || (c == b'}' && braces.last() == Some(&true)) {
if c == b'}' {
braces.pop();
}
i += 1;
loop {
match b.get(i) {
None => break,
Some(b'\\') => i += 2,
Some(b'`') => {
i += 1;
break;
}
Some(b'$') if b.get(i + 1) == Some(&b'{') => {
i += 2;
braces.push(true);
break;
}
Some(_) => i += 1,
}
}
i = i.min(b.len());
tok_kind = TokKind::Template;
} else if is_ident_start(c) {
while b.get(i).is_some_and(|&d| is_ident_part(d) && (d < 0x80 || (line_terminator_len(src, i) == 0 && other_space_len(src, i) == 0))) {
i += 1;
}
tok_kind = TokKind::Ident;
} else if c.is_ascii_digit() || (c == b'.' && next.is_ascii_digit()) {
let radix = c == b'0' && matches!(next, b'x' | b'X' | b'b' | b'B' | b'o' | b'O');
while let Some(&d) = b.get(i) {
let exp_sign =
!radix && matches!(d, b'+' | b'-') && matches!(b.get(i.wrapping_sub(1)), Some(b'e' | b'E')) && b.get(i + 1).is_some_and(u8::is_ascii_digit);
if d.is_ascii_alphanumeric() || d == b'.' || d == b'_' || exp_sign {
i += 1;
} else {
break;
}
}
tok_kind = TokKind::Number;
} else if slash != RegexStart::No && (slash == RegexStart::Yes || ambiguous_close) {
ambiguous_regex = slash == RegexStart::Ambiguous;
i += 1;
let mut in_class = false;
while let Some(&d) = b.get(i) {
let term = line_terminator_bytes(b, i);
if term != 0 {
i += term;
break;
}
i += 1;
match d {
b'\\' => {
if line_terminator_bytes(b, i) != 0 {
break;
}
i += 1;
}
b'[' => in_class = true,
b']' => in_class = false,
b'/' if !in_class => {
// In sloppy code this closing `/` divides, and a `*` or `/` right after it
// opens a comment the regex reading passes.
if ambiguous_regex && matches!(b.get(i), Some(b'*' | b'/')) {
ambiguous_boundaries = true;
}
break;
}
_ => {}
}
}
while b.get(i).is_some_and(|&d| d.is_ascii_alphabetic()) {
i += 1;
}
i = i.min(b.len());
tok_kind = TokKind::Regex;
} else {
let rest = b.get(i..).unwrap_or_default();
let len = PUNCTS.iter().find(|p| rest.starts_with(p.as_bytes())).map_or(1, |p| p.len());
// Never split a multi-byte character.
let mut z = i + len;
while z < b.len() && !src.is_char_boundary(z) {
z += 1;
}
if c == b'{' {
braces.push(false);
} else if c == b'}' {
braces.pop();
}
i = z;
tok_kind = TokKind::Punct;
}
let text = slice(start, i);
last_member = tok_kind == TokKind::Ident && matches!(last_sig, Some((TokKind::Punct, "." | "?.")));
last_sig = Some((tok_kind, text));
emit(Token { kind: tok_kind, text, offset: start, ambiguous_regex });
if ambiguous_regex {
// In sloppy code a quote here starts a string whose end the regex reading may pass, and
// an unbalanced bracket leaves the two readings with different bracket scopes.
if text.bytes().any(|b| matches!(b, b'\'' | b'"' | b'`')) || !brackets_balance(text) {
ambiguous_boundaries = true;
}
}
after_ambiguous_regex = ambiguous_regex;
}
Scanned { truncated: false, lookahead_exhausted, ambiguous_boundaries }
}
/// Whether a `/` starts a regex, divides, or is the ambiguous `yield /…`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum RegexStart {
No,
Yes,
Ambiguous,
}
fn regex_start(prev: Option<(TokKind, &str)>, after_member: bool) -> RegexStart {
if after_member {
// `x.of /`, `x.in /`: a property name is a value, so `/` divides.
return RegexStart::No;
}
match prev {
None => RegexStart::Yes,
Some((TokKind::Punct, ")" | "]" | "}" | "++" | "--")) => RegexStart::No,
Some((TokKind::Punct, _)) => RegexStart::Yes,
// `yield /re/` in a generator, or `yield / 2` in sloppy code: read a regex only when one
// closes on the line, and count its brackets too, as they may be code rather than a class.
Some((TokKind::Ident, "yield")) => RegexStart::Ambiguous,
Some((TokKind::Ident, w)) if REGEX_AFTER_KEYWORDS.contains(&w) => RegexStart::Yes,
Some(_) => RegexStart::No,
}
}
/// What a `yield /…/` lookahead found.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum RegexCloses {
/// A closing `/` on the same line.
Closes,
/// A line ended first: the slash divides.
No,
/// The shared lookahead budget ran out before the line did: unknown, so admission fails closed.
Exhausted,
}
/// Whether a `/`, starting at `from`, closes a regex on the same line. Escapes and `[…]` classes
/// are respected, as in the scanner above, and every JavaScript line terminator ends the search
/// (even after a backslash). `budget` is the bytes this scan may still look at across the whole
/// source, which keeps repeated lookahead on hostile `yield /[…` input linear.
fn regex_closes(bytes: &[u8], mut i: usize, budget: &mut usize) -> RegexCloses {
let mut in_class = false;
while let Some(&d) = bytes.get(i) {
if line_terminator_bytes(bytes, i) != 0 {
return RegexCloses::No;
}
if *budget == 0 {
return RegexCloses::Exhausted;
}
*budget -= 1;
i += 1;
match d {
b'\\' => {
if line_terminator_bytes(bytes, i) != 0 {
return RegexCloses::No;
}
i += 1;
}
b'[' => in_class = true,
b']' => in_class = false,
b'/' if !in_class => return RegexCloses::Closes,
_ => {}
}
}
RegexCloses::No
}
/// How much nesting the text of an ambiguous `yield /…/` may hold if it is sloppy-code division:
/// its brackets and every `!`, `+`, `-`, `~`, `*`, `%`, `?`, `&`, `|` or `^`, which chain one node
/// each. Counting a real regex's characters too over-estimates, which only sends the source to the
/// lexer fallback.
fn ambiguous_depth(text: &str) -> usize {
text.bytes().filter(|b| matches!(b, b'(' | b'[' | b'{' | b'!' | b'+' | b'-' | b'~' | b'*' | b'%' | b'?' | b'&' | b'|' | b'^')).count()
}
/// Whether the brackets in `text` balance. An ambiguous token whose division reading leaves a
/// bracket open, or closes one it never opened, no longer shares the scanner's bracket scopes.
fn brackets_balance(text: &str) -> bool {
let mut depth = 0usize;
for b in text.bytes() {
match b {
b'(' | b'[' | b'{' => depth += 1,
b')' | b']' | b'}' => match depth.checked_sub(1) {
Some(d) => depth = d,
None => return false,
},
_ => {}
}
}
depth == 0
}
/// Decode the value of a string token (quotes stripped, common escapes resolved).
pub fn string_value(raw: &str) -> String {
let inner = raw.get(1..).unwrap_or("");
let inner = match raw.chars().next() {
Some(q) if inner.ends_with(q) => inner.get(..inner.len().saturating_sub(1)).unwrap_or(inner),
_ => inner,
};
unescape(inner)
}
/// Resolve JavaScript escape sequences (lenient: unknown escapes keep the character).
pub fn unescape(s: &str) -> String {
let mut out = String::with_capacity(s.len());
let mut it = s.chars().peekable();
while let Some(c) = it.next() {
if c != '\\' {
out.push(c);
continue;
}
match it.next() {
Some('n') => out.push('\n'),
Some('t') => out.push('\t'),
Some('r') => out.push('\r'),
Some('b') => out.push('\u{8}'),
Some('f') => out.push('\u{c}'),
Some('v') => out.push('\u{b}'),
Some(c @ '0'..='7') => {
let mut code = c as u32 - '0' as u32;
let extra = if c <= '3' { 2 } else { 1 };
for _ in 0..extra {
let Some(d @ '0'..='7') = it.peek().copied() else { break };
it.next();
code = code * 8 + d as u32 - '0' as u32;
}
out.push(char::from_u32(code).unwrap_or('\u{FFFD}'));
}
Some('x') => {
let h: String = it.by_ref().take(2).collect();
if let Some(ch) = u32::from_str_radix(&h, 16).ok().and_then(char::from_u32) {
out.push(ch);
}
}
Some('u') => {
let code = if it.peek() == Some(&'{') {
it.next();
// Accumulate without allocating: any number of leading zeroes is valid.
let mut value = Some(0u32);
let mut digits = false;
let mut closed = false;
for c in it.by_ref() {
if c == '}' {
closed = true;
break;
}
digits = true;
value = value.and_then(|v| v.checked_mul(16)?.checked_add(c.to_digit(16)?));
}
if digits && closed { value } else { None }
} else {
let hex: String = it.by_ref().take(4).collect();
u32::from_str_radix(&hex, 16).ok()
};
let Some(mut code) = code else { continue };
if (0xD800..0xDC00).contains(&code) {
let mut ahead = it.clone();
if ahead.next() == Some('\\') && ahead.next() == Some('u') {
let lo: String = ahead.by_ref().take(4).collect();
if let Some(lo) = u32::from_str_radix(&lo, 16).ok().filter(|l| lo.len() == 4 && (0xDC00..0xE000).contains(l)) {
code = 0x10000 + ((code - 0xD800) << 10) + (lo - 0xDC00);
it = ahead;
}
}
}
out.push(char::from_u32(code).unwrap_or('\u{FFFD}'));
}
Some('\n' | '\u{2028}' | '\u{2029}') => {}
Some('\r') => {
if it.peek() == Some(&'\n') {
it.next();
}
}
Some(other) => out.push(other),
None => {}
}
}
out
}
/// An upper-bound style estimate of how deep the syntax tree for `tokens` will nest.
///
/// Brackets add a level; operators that nest expressions (member access, binary and assignment
/// operators, conditionals, arrows, unary prefixes) and nesting statement keywords add a level
/// until the next `,` or `;` at the same bracket depth. So do a call, index or template that
/// follows another (`f()()`, `a[0][1]`, a chain of tagged templates) and a label that follows
/// another (`a: b: c;`): each wraps what came before in one more node, though its brackets close.
/// A bracket that the expression goes on after (`((f)()).a`, `f(g(x)())()`, `(a + b) + c`) keeps
/// what was counted inside it, since what follows wraps all of it; of siblings such as
/// `(a) && (b)` only the deepest counts.
/// Comments and whitespace (non-ASCII spaces included) are skipped. Over-estimates are fine: they
/// only send a file to the lexer fallback.
pub fn nesting_estimate(tokens: &[Token<'_>]) -> usize {
let mut n = Nesting::default();
for t in tokens {
n.feed(t);
}
n.max
}
/// What the last tokens were, as far as chains and labels need to know.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Recent {
/// `)`, `]` or the end of a template: a `(`, `[` or template right after it continues a chain.
PostfixEnd,
/// A label's colon (or any colon): a name and a colon after it make another label.
Colon,
/// A name that follows a colon.
NameAfterColon,
Other,
}
/// Does `t`, right after a closing bracket, carry on the expression the bracket ended?
fn continues_after_close(t: &Token<'_>) -> bool {
match t.kind {
TokKind::Punct => !matches!(t.text, "," | ";" | "{" | ":"),
TokKind::Template => true,
TokKind::Ident => matches!(t.text, "in" | "instanceof"),
_ => false,
}
}
/// Streaming state for [`nesting_estimate`].
#[derive(Debug)]
pub struct Nesting {
/// What each open bracket has counted so far, one per level.
stack: Vec<usize>,
/// The `else` links counted at each level: a block's links end with its `}`.
chains: Vec<usize>,
/// Whether the last token ended a statement at that level (`;` or `}`).
ended: Vec<bool>,
/// The expression depth at every level together.
sum: usize,
/// The `else` links at every level together. Kept apart from the expression level, which a
/// comma clears: `if (a) b, c; else …` still nests one level per link.
chain_total: usize,
pub max: usize,
recent: Recent,
/// What a bracket that just closed had counted, for the expression it may go on in.
carry: usize,
/// Whether the last token can end an expression, so `++`/`--` after it is postfix.
prev_value: bool,
/// Whether the last token was `++`/`--`; a following one is prefix, never postfix.
prev_update: bool,
/// Whether the last token was `extends`, so a `class` after it is a nested heritage.
prev_extends: bool,
}
impl Default for Nesting {
fn default() -> Self {
Nesting {
stack: vec![0],
chains: vec![0],
ended: vec![false],
sum: 0,
chain_total: 0,
max: 0,
recent: Recent::Other,
carry: 0,
prev_value: false,
prev_update: false,
prev_extends: false,
}
}
}
impl Nesting {
/// Take one token into the estimate.
pub fn feed(&mut self, t: &Token<'_>) {
if t.kind == TokKind::Comment {
return;
}
let Nesting { stack, chains, ended, sum, chain_total, max, recent, carry, prev_value, prev_update, prev_extends } = self;
// `if (a); else if (a); else …`: each link ends with `;`, but the next link nests inside
// it. Count the links at their own level, apart from the expression level (which a comma
// clears), so a `;` inside a block does not reset the chain that block is the consequent
// of. Any other token after a statement end closes that level's chain.
let level = stack.len().saturating_sub(1);
if let Some(flag) = ended.get_mut(level)
&& std::mem::take(flag)
&& let Some(links) = chains.get_mut(level)
{
if t.kind == TokKind::Ident && t.text == "else" {
*links += 1;
*chain_total += 1;
} else {
*chain_total = chain_total.saturating_sub(*links);
*links = 0;
}
}
if t.ambiguous_regex {
let inner = ambiguous_depth(t.text);
// The division reading's depth is part of this expression, so later nesting adds to
// it; the comma, `;` and closing-bracket handling above clear it like any other depth.
if let Some(n) = stack.last_mut() {
*n = n.saturating_add(inner);
}
*sum = sum.saturating_add(inner);
}
// `((f)())()`, `f(g(x)())()`, `(a + b) + c`: what follows a closed bracket wraps the
// expression it ended, so that expression's depth goes on counting at this level. Siblings
// (`(a) && (b)`) don't add up: the deepest one counts.
let carried = std::mem::take(carry);
if continues_after_close(t)
&& let Some(n) = stack.last_mut()
&& carried > *n
{
*sum += carried - *n;
*n = carried;
}
// `f()(`, `a[0][`, a template after a template: another node around the chain so far.
let chained = *recent == Recent::PostfixEnd
&& match t.kind {
TokKind::Punct => matches!(t.text, "(" | "["),
TokKind::Template => t.text.starts_with('`'),
_ => false,
};
// `a: b:`: a label after a label. `default` is a case clause, not a label.
let labelled = *recent == Recent::NameAfterColon && t.kind == TokKind::Punct && t.text == ":";
*recent = match t.kind {
TokKind::Punct if matches!(t.text, ")" | "]") => Recent::PostfixEnd,
TokKind::Template if t.text.len() > 1 && t.text.ends_with('`') => Recent::PostfixEnd,
TokKind::Punct if t.text == ":" => Recent::Colon,
TokKind::Ident if *recent == Recent::Colon && t.text != "default" => Recent::NameAfterColon,
_ => Recent::Other,
};
if (chained || labelled)
&& let Some(n) = stack.last_mut()
{
*n += 1;
*sum += 1;
}
let closes = match t.kind {
TokKind::Punct => matches!(t.text, ")" | "]" | "}"),
TokKind::Template => t.text.starts_with('}'),
_ => false,
};
let opens = match t.kind {
TokKind::Punct => matches!(t.text, "(" | "[" | "{"),
TokKind::Template => t.text.ends_with("${"),
_ => false,
};
if closes
&& stack.len() > 1
&& let Some(n) = stack.pop()
{
*sum = sum.saturating_sub(n + 1);
*carry = n;
if let Some(links) = chains.pop() {
*chain_total = chain_total.saturating_sub(links);
}
ended.pop();
if t.kind == TokKind::Punct
&& t.text == "}"
&& let Some(flag) = ended.last_mut()
{
*flag = true;
}
}
if opens {
stack.push(0);
chains.push(0);
ended.push(false);
*sum += 1;
}
if !opens && !closes {
let nests = match t.kind {
TokKind::Punct => !matches!(t.text, "," | ";" | ":") && !(matches!(t.text, "++" | "--") && *prev_value && !*prev_update),
// `class extends class extends …`: each class after `extends` nests a heritage.
// `extends` itself would accumulate across separate declarations, which don't nest.
TokKind::Ident if t.text == "class" => *prev_extends,
TokKind::Ident => matches!(
t.text,
"typeof" | "void" | "delete" | "await" | "new" | "if" | "else" | "for" | "while" | "do" | "with" | "in" | "instanceof" | "yield"
),
_ => false,
};
if let Some(n) = stack.last_mut() {
if matches!((t.kind, t.text), (TokKind::Punct, "," | ";")) {
*sum = sum.saturating_sub(*n);
*n = 0;
if t.text == ";"
&& let Some(flag) = ended.last_mut()
{
*flag = true;
}
} else if nests {
*n += 1;
*sum += 1;
}
}
}
*max = (*max).max(sum.saturating_add(*chain_total));
// What the next token sees: `a++` is postfix, `++a` and `++++a` are prefix.
*prev_value = match t.kind {
TokKind::Number | TokKind::Str | TokKind::Regex => true,
TokKind::Ident => !EXPRESSION_KEYWORDS.contains(&t.text),
TokKind::Punct => matches!(t.text, ")" | "]" | "++" | "--"),
TokKind::Template => t.text.len() > 1 && t.text.ends_with('`'),
TokKind::Comment => false,
};
*prev_update = t.kind == TokKind::Punct && matches!(t.text, "++" | "--");
*prev_extends = t.kind == TokKind::Ident && t.text == "extends";
}
}
#[cfg(test)]
mod tests {
use super::*;
fn kinds(s: &str) -> Vec<(TokKind, String)> {
tokenize(s, 1000).0.into_iter().map(|t| (t.kind, t.text.to_string())).collect()
}
#[test]
fn operators_before_non_ascii_identifier() {
for (src, op) in [("a===日本", "==="), ("a>>日本", ">>"), ("a=>é", "=>"), ("a!==😀", "!==")] {
let t: Vec<&str> = tokenize(src, 100).0.into_iter().map(|t| t.text).collect();
assert_eq!(t.len(), 3, "{src}: {t:?}");
assert_eq!(t[1], op, "{src}");
}
}
#[test]
fn whitespace_does_not_count_against_limit() {
let (t, truncated) = tokenize("a b c d", 4);
assert_eq!(t.len(), 4);
assert!(!truncated);
let (t, truncated) = tokenize("a b c d", 3);
assert_eq!(t.len(), 3);
assert!(truncated);
}
#[test]
fn exponent_sign() {
let texts = |s: &str| tokenize(s, 100).0.into_iter().map(|t| t.text.to_string()).collect::<Vec<_>>();
assert_eq!(texts("x = 1e+5 + 2.5E-3;"), ["x", "=", "1e+5", "+", "2.5E-3", ";"]);
assert_eq!(texts("0x1e+5"), ["0x1e", "+", "5"]);
}
#[test]
fn crlf_line_continuation_stays_in_string() {
let k = kinds("x = 'a\\\r\nb';");
assert!(k.contains(&(TokKind::Str, "'a\\\r\nb'".into())), "{k:?}");
assert!(k.contains(&(TokKind::Punct, ";".into())), "{k:?}");
}
#[test]
fn unescape_crlf_line_continuation() {
assert_eq!(unescape("a\\\r\nb"), "ab");
assert_eq!(unescape("a\\\rb"), "ab");
assert_eq!(unescape("a\\\nb"), "ab");
}
#[test]
fn unescape_backspace_formfeed_vtab() {
assert_eq!(unescape(r"a\fb\vc\bd"), "a\u{c}b\u{b}c\u{8}d");
assert_eq!(string_value(r#""\b\f\v""#), "\u{8}\u{c}\u{b}");
}
#[test]
fn unescape_combines_surrogate_pairs() {
assert_eq!(unescape("\\uD83D\\uDE00"), "😀");
assert_eq!(unescape("a\\uD83D\\u0041"), "a\u{FFFD}A");
assert_eq!(unescape("\\uDE00x"), "\u{FFFD}x");
assert_eq!(unescape("\\u{1F600}"), "😀");
}
#[test]
fn tokenizes_strings_templates_regex() {
let k = kinds(r#"a = "x\"y" + `t${b}u` / 2; r = /a\/b[/]c/g"#);
assert!(k.contains(&(TokKind::Str, r#""x\"y""#.into())));
assert!(k.contains(&(TokKind::Template, "`t${".into())));
assert!(k.contains(&(TokKind::Template, "}u`".into())));
assert!(k.contains(&(TokKind::Regex, "/a\\/b[/]c/g".into())));
assert!(k.contains(&(TokKind::Punct, "/".into())));
assert_eq!(string_value(r#""aA\x42\n""#), "aAB\n");
}
#[test]
fn nesting_grows_with_depth() {
let shallow = nesting_estimate(&tokenize("a(b, c); d[e];", 100).0);
let deep_src = format!("{}1{}", "(".repeat(300), ")".repeat(300));
let deep = nesting_estimate(&tokenize(&deep_src, 10_000).0);
let chain = nesting_estimate(&tokenize(&"a+".repeat(500), 10_000).0);
let nots = nesting_estimate(&tokenize(&format!("{}x", "!".repeat(400)), 10_000).0);
assert!(shallow < 5, "{shallow}");
assert!(deep >= 300 && chain >= 500 && nots >= 400, "{deep} {chain} {nots}");
}
#[test]
fn nesting_counts_else_if_extends_prefix_update_and_hidden_brackets() {
let deep = |src: String| nesting_estimate(&tokenize(&src, 100_000).0);
let n = 5_000;
let else_if = format!("if(a);{}", "else if(a);".repeat(n));
assert!(deep(else_if) > n, "else-if chain");
let extends = format!("x = class{};", " extends class".repeat(n) + " {}");
assert!(deep(extends) > n, "class extends chain");
let separate = "class A extends B {}".repeat(n);
assert!(deep(separate) < 16, "separate extended classes do not add up");
let prefix = format!("x = {}a;", "++".repeat(n));
assert!(deep(prefix) > n, "prefix ++ run");
let hidden = format!("x = a++ /{} / 1;", "[".repeat(n) + &"]".repeat(n));
assert!(deep(hidden) > n, "brackets after an update operator");
let commas = "if(a)b,c;else ".repeat(n) + "if(a)b,c;";
assert!(deep(commas) > n, "else-if chain with comma expressions");
let alternating = "if(a){b;}else if(a)c;else ".repeat(n) + "if(a){d;}";
assert!(deep(alternating) > n, "block and unbraced consequents");
let yield_regex = format!("x = yield /{} /;", "[".repeat(n) + &"]".repeat(n));
assert!(deep(yield_regex) > n, "brackets in a regex after yield");
let yield_nots = format!("x = yield /{}a / 1;", "!".repeat(n));
assert!(deep(yield_nots) > n, "prefix operators in an ambiguous regex after yield");
let adds = format!("x = yield /{}a / 1;", "a+".repeat(n));
assert!(deep(adds) > n, "addition chain in an ambiguous regex after yield");
let separated = format!("x = yield /{}a / 1;", "!a".repeat(n));
assert!(deep(separated) > n, "separated prefix operators in an ambiguous regex after yield");
let cond = format!("x = yield /{}a / 1;", "a?b:".repeat(n));
assert!(deep(cond) > n, "conditional chain in an ambiguous regex after yield");
for op in ["&", "|", "^"] {
let bitwise = format!("x = yield /{}a / 1;", format!("a{op}").repeat(n));
assert!(deep(bitwise) > n, "bitwise {op} chain in an ambiguous regex after yield");
}
}
#[test]
fn ambiguous_regex_lookahead_stops_at_its_budget() {
let bytes = b"/[[[[[[";
let mut budget = 4;
assert_eq!(regex_closes(bytes, 1, &mut budget), RegexCloses::Exhausted);
assert_eq!(budget, 0);
}
#[test]
fn ambiguous_regex_stops_at_every_line_terminator() {
for term in ["\n", "\r", "\u{2028}", "\u{2029}"] {
let src = format!("yield / 2;{term} x = {}a; /re/;", "!".repeat(6_000));
let toks = tokenize(&src, 100_000).0;
let nots = toks.iter().filter(|t| t.kind == TokKind::Punct && t.text == "!").count();
assert_eq!(nots, 6_000, "line terminator {term:?}");
assert!(nesting_estimate(&toks) >= 6_000, "line terminator {term:?}");
}
// A backslash before the line end does not let the lookahead continue either.
let escaped = format!("yield / 2;\\\n x = {}a; /re/;", "!".repeat(6_000));
let toks = tokenize(&escaped, 100_000).0;
assert_eq!(toks.iter().filter(|t| t.kind == TokKind::Punct && t.text == "!").count(), 6_000);
assert!(nesting_estimate(&toks) >= 6_000);
}
#[test]
fn division_follows_updates_and_members_but_yield_can_start_a_regex() {
for src in ["a++ / b[0] / c", "x.of / b[0] / c", "x?.of / b[0] / c"] {
let kinds: Vec<TokKind> = tokenize(src, 100).0.into_iter().map(|t| t.kind).collect();
assert!(!kinds.contains(&TokKind::Regex), "{src}: {kinds:?}");
}
// `yield /a[0]/g` is a regex in a generator: recognized as one, flagged ambiguous, and
// the code after its closing delimiter is still tokenized.
let toks = tokenize("yield /a[0]/g; f(x);", 100).0;
let regex = toks.iter().find(|t| t.kind == TokKind::Regex).expect("a regex after yield");
assert_eq!(regex.text, "/a[0]/g");
assert!(regex.ambiguous_regex);
let texts: Vec<&str> = toks.iter().map(|t| t.text).collect();
assert!(texts.contains(&";") && texts.contains(&"f") && texts.contains(&"("), "{texts:?}");
// `yield* /re/` too, and `return /re/` as before.
assert!(tokenize("yield* /re/g", 100).0.iter().any(|t| t.kind == TokKind::Regex));
assert!(tokenize("return /a[0]/g", 100).0.iter().any(|t| t.kind == TokKind::Regex));
// A compact generator regex stays a shallow regex, not a refused source.
let boundary = tokenize("yield /a+b/;", 100).0;
assert!(boundary.iter().any(|t| t.kind == TokKind::Regex));
assert!(nesting_estimate(&boundary) < 16);
// `yield / 2` with no closing `/` on the line is sloppy-code division: no regex is made,
// and the brackets after it stay visible to the nesting estimate.
let division = tokenize("yield / 2; g(h(k(i)));", 100).0;
assert!(!division.iter().any(|t| t.kind == TokKind::Regex), "{division:?}");
assert!(nesting_estimate(&division) >= 3);
}
#[test]
fn never_panics_on_junk() {
for s in ["\"", "`${", "/*", "'\\", "}}}}", "`${`${`${", "/[", "é/é/", "\u{1F600}=`\u{1F600}${é}`", "a/**/b//"] {
let (t, _) = tokenize(s, 100);
let _ = nesting_estimate(&t);
for tok in t {
let _ = string_value(tok.text);
}
}
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.