use crate::budget::Budget;
use crate::error::{LoadError, LoadErrorKind};
use crate::path::RelPath;
mod recursion;
use recursion::Recursion;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Delimiter {
Paren,
Bracket,
Brace,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Token<'a> {
Open(Delimiter),
CloseBrace,
CloseOther,
Ident(&'a str),
Bang,
Minus,
Star,
Amp,
AmpAmp,
Pipe,
PipePipe,
Lt,
Gt,
Semi,
Comma,
FatArrow,
Colon,
PathSep,
Hash,
Operator,
Lifetime,
Literal,
Float,
Other,
}
#[derive(Debug, Default, Clone, Copy)]
struct Level {
angles: usize,
else_ifs: usize,
after_brace: bool,
pending_else: bool,
}
struct Counters {
levels: Vec<Level>,
prefix_run: usize,
closure_chain: usize,
closure_pending_end: bool,
closure_head_depth: Option<usize>,
}
#[derive(Debug, Clone, Copy)]
struct Exceeded {
budget: Budget,
line: usize,
}
impl Counters {
fn new() -> Self {
Self {
levels: vec![Level::default()],
prefix_run: 0,
closure_chain: 0,
closure_pending_end: false,
closure_head_depth: None,
}
}
fn top(&mut self) -> &mut Level {
let last = self.levels.len() - 1;
&mut self.levels[last]
}
fn depth(&self) -> usize {
self.levels.len() - 1
}
fn feed(&mut self, token: Token<'_>, line: usize) -> Result<(), Exceeded> {
self.else_if(token, line)?;
self.prefix(token, line)?;
self.closure(token, line)?;
self.angle_and_delimiter(token, line)
}
fn else_if(&mut self, token: Token<'_>, line: usize) -> Result<(), Exceeded> {
if token == Token::CloseBrace {
return Ok(());
}
let continues = token == Token::Ident("else") && self.top().after_brace;
let level = self.top();
let starts_statement = matches!(token, Token::Ident(word) if word != "else");
if (level.after_brace && starts_statement) || token == Token::Semi {
level.else_ifs = 0;
}
level.after_brace = false;
if level.pending_else {
level.pending_else = false;
if token == Token::Ident("if") {
level.else_ifs += 1;
if level.else_ifs > Budget::ElseIf.limit() {
return Err(Exceeded {
budget: Budget::ElseIf,
line,
});
}
} else {
level.else_ifs = 0;
}
}
if continues {
level.pending_else = true;
}
Ok(())
}
fn prefix(&mut self, token: Token<'_>, line: usize) -> Result<(), Exceeded> {
if matches!(
token,
Token::Bang | Token::Minus | Token::Star | Token::Amp | Token::AmpAmp
) {
self.prefix_run += 1;
if self.prefix_run > Budget::PrefixOperators.limit() {
return Err(Exceeded {
budget: Budget::PrefixOperators,
line,
});
}
} else if token != Token::Lifetime {
self.prefix_run = 0;
}
Ok(())
}
fn closure(&mut self, token: Token<'_>, line: usize) -> Result<(), Exceeded> {
let depth = self.depth();
if let Some(head_depth) = self.closure_head_depth {
if depth < head_depth {
self.closure_head_depth = None;
self.closure_pending_end = false;
self.closure_chain = 0;
} else if token == Token::Pipe && depth == head_depth {
self.closure_head_depth = None;
self.closure_pending_end = true;
return Ok(());
} else {
return Ok(());
}
}
match token {
Token::PipePipe | Token::Pipe => {
self.closure_chain = if self.closure_pending_end {
self.closure_chain + 1
} else {
1
};
if self.closure_chain > Budget::ClosureBars.limit() {
return Err(Exceeded {
budget: Budget::ClosureBars,
line,
});
}
if token == Token::Pipe {
self.closure_head_depth = Some(depth);
self.closure_pending_end = false;
} else {
self.closure_pending_end = true;
}
}
Token::Ident("move") if self.closure_pending_end => {}
_ => {
self.closure_pending_end = false;
self.closure_chain = 0;
}
}
Ok(())
}
fn angle_and_delimiter(&mut self, token: Token<'_>, line: usize) -> Result<(), Exceeded> {
match token {
Token::Open(_) => {
self.levels.push(Level::default());
if self.depth() > Budget::Delimiters.limit() {
return Err(Exceeded {
budget: Budget::Delimiters,
line,
});
}
}
Token::CloseBrace | Token::CloseOther => {
if self.levels.len() > 1 {
self.levels.pop();
if token == Token::CloseBrace {
let parent = self.top();
parent.after_brace = true;
parent.angles = 0;
}
}
}
Token::Lt => {
let level = self.top();
level.angles += 1;
if level.angles > Budget::Angles.limit() {
return Err(Exceeded {
budget: Budget::Angles,
line,
});
}
}
Token::Gt => {
let level = self.top();
level.angles = level.angles.saturating_sub(1);
}
Token::Semi | Token::AmpAmp | Token::PipePipe => self.top().angles = 0,
_ => {}
}
Ok(())
}
}
fn is_ident_start(byte: u8) -> bool {
byte == b'_' || byte.is_ascii_alphabetic() || byte >= 0x80
}
fn is_whitespace(ch: char) -> bool {
ch.is_whitespace() || matches!(ch, '\u{200e}' | '\u{200f}')
}
fn is_ident_continue(ch: char) -> bool {
ch == '_' || ch.is_ascii_alphanumeric() || (!ch.is_ascii() && !is_whitespace(ch))
}
struct Cursor<'a> {
text: &'a str,
bytes: &'a [u8],
at: usize,
line: usize,
}
impl<'a> Cursor<'a> {
fn new(text: &'a str) -> Self {
Self {
text,
bytes: text.as_bytes(),
at: 0,
line: 1,
}
}
fn peek(&self, ahead: usize) -> Option<u8> {
self.bytes.get(self.at + ahead).copied()
}
fn bump(&mut self) {
if self.peek(0) == Some(b'\n') {
self.line += 1;
}
self.at += 1;
}
fn bump_by(&mut self, count: usize) {
for _ in 0..count {
self.bump();
}
}
fn whitespace_width(&self) -> Option<usize> {
self.text[self.at..]
.chars()
.next()
.filter(|ch| is_whitespace(*ch))
.map(char::len_utf8)
}
fn skip_header_trivia(&mut self) {
while let Some(byte) = self.peek(0) {
if byte == b'/' && self.peek(1) == Some(b'/') && self.doc_comment_tokens() == 0 {
self.skip_line_comment();
} else if byte == b'/' && self.peek(1) == Some(b'*') && self.doc_comment_tokens() == 0 {
self.skip_block_comment();
} else {
let Some(width) = self.whitespace_width() else {
break;
};
self.bump_by(width);
}
}
}
fn doc_comment_tokens(&self) -> usize {
match (self.peek(1), self.peek(2), self.peek(3)) {
(Some(b'/'), Some(b'/'), next) if next != Some(b'/') => 6,
(Some(b'*'), Some(b'*'), next) if next != Some(b'*') && next != Some(b'/') => 6,
(Some(b'/' | b'*'), Some(b'!'), _) => 7,
_ => 0,
}
}
fn skip_line_comment(&mut self) {
while self.peek(0).is_some_and(|byte| byte != b'\n') {
self.bump();
}
}
fn skip_block_comment(&mut self) {
self.bump_by(2);
let mut depth = 1_usize;
while depth > 0 && self.peek(0).is_some() {
if self.peek(0) == Some(b'/') && self.peek(1) == Some(b'*') {
depth += 1;
self.bump_by(2);
} else if self.peek(0) == Some(b'*') && self.peek(1) == Some(b'/') {
depth -= 1;
self.bump_by(2);
} else {
self.bump();
}
}
}
fn skip_quoted(&mut self, quote: u8) {
while let Some(byte) = self.peek(0) {
self.bump();
if byte == b'\\' {
if self.peek(0).is_some() {
self.bump();
}
} else if byte == quote {
return;
}
}
}
fn skip_raw_string(&mut self, hashes: usize) {
self.bump_by(hashes + 1);
while let Some(byte) = self.peek(0) {
self.bump();
if byte == b'"' {
let closing = (0..hashes).all(|offset| self.peek(offset) == Some(b'#'));
if closing {
self.bump_by(hashes);
return;
}
}
}
}
fn hashes_at(&self, ahead: usize) -> usize {
let mut count = 0;
while self.peek(ahead + count) == Some(b'#') {
count += 1;
}
count
}
fn skip_quote_or_lifetime(&mut self) -> bool {
self.bump();
match self.peek(0) {
Some(b'\\') => {
self.skip_quoted(b'\'');
false
}
Some(first) => {
let width = match first {
0xF0.. => 4,
0xE0.. => 3,
0xC0.. => 2,
_ => 1,
};
if self.peek(width) == Some(b'\'') {
self.bump_by(width + 1);
false
} else {
self.ident();
true
}
}
None => false,
}
}
fn ident(&mut self) -> &'a str {
let start = self.at;
let width = self.text[start..]
.chars()
.take_while(|ch| is_ident_continue(*ch))
.map(char::len_utf8)
.sum();
self.bump_by(width);
&self.text[start..self.at]
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Scan {
pub(crate) tokens: usize,
pub(crate) recursion: usize,
}
pub(crate) fn shebang(text: &str) -> Option<std::ops::Range<usize>> {
let start = if text.starts_with('\u{feff}') {
'\u{feff}'.len_utf8()
} else {
0
};
if !text[start..].starts_with("#!") {
return None;
}
let mut cursor = Cursor::new(text);
cursor.at = start + 2;
cursor.skip_header_trivia();
if cursor.peek(0) == Some(b'[') {
return None;
}
let end = text[start..].find('\n').map_or(text.len(), |at| start + at);
Some(start..end)
}
pub(crate) fn prescan_file(
file: &RelPath,
text: &str,
max_tokens: usize,
) -> Result<Scan, LoadError> {
let at = shebang(text).map_or_else(
|| {
if text.starts_with('\u{feff}') {
'\u{feff}'.len_utf8()
} else {
0
}
},
|range| range.end,
);
prescan_from(file, text, max_tokens, at)
}
pub(crate) fn prescan(file: &RelPath, text: &str, max_tokens: usize) -> Result<Scan, LoadError> {
prescan_from(file, text, max_tokens, 0)
}
fn prescan_from(
file: &RelPath,
text: &str,
max_tokens: usize,
at: usize,
) -> Result<Scan, LoadError> {
let mut cursor = Cursor::new(text);
cursor.at = at;
let mut counters = Counters::new();
let mut recursion = Recursion::new();
let mut tokens = 0_usize;
let over = |budget: Budget, limit: usize, line: usize| {
LoadError::new(file, Some(line), LoadErrorKind::Budget { budget, limit })
};
let mut count = |added: usize, line: usize| {
tokens += added;
if tokens > max_tokens {
Err(over(Budget::FileTokens, max_tokens, line))
} else {
Ok(())
}
};
while let Some(byte) = cursor.peek(0) {
if !byte.is_ascii()
&& let Some(width) = cursor.whitespace_width()
{
cursor.bump_by(width);
continue;
}
let line = cursor.line;
let start = cursor.at;
let token = match byte {
b if b.is_ascii_whitespace() => {
cursor.bump();
continue;
}
b'/' => match cursor.peek(1) {
Some(b'/') => {
count(cursor.doc_comment_tokens(), line)?;
cursor.skip_line_comment();
continue;
}
Some(b'*') => {
count(cursor.doc_comment_tokens(), line)?;
cursor.skip_block_comment();
continue;
}
_ => {
cursor.bump();
Token::Operator
}
},
b'"' => {
cursor.bump();
cursor.skip_quoted(b'"');
Token::Literal
}
b'\'' => {
if cursor.skip_quote_or_lifetime() {
Token::Lifetime
} else {
Token::Literal
}
}
b if is_ident_start(b) => word(&mut cursor),
b'0'..=b'9' => {
if number(&mut cursor) {
Token::Float
} else {
Token::Literal
}
}
b'(' | b'[' | b'{' => {
cursor.bump();
Token::Open(match byte {
b'(' => Delimiter::Paren,
b'[' => Delimiter::Bracket,
_ => Delimiter::Brace,
})
}
b'}' => {
cursor.bump();
Token::CloseBrace
}
b')' | b']' => {
cursor.bump();
Token::CloseOther
}
_ => punctuation(&mut cursor, byte),
};
let added = lexed_tokens(token, &text.as_bytes()[start..cursor.at]);
count(added, line)?;
counters
.feed(token, line)
.map_err(|exceeded| over(exceeded.budget, exceeded.budget.limit(), exceeded.line))?;
if recursion.feed(token, cursor.at - start) > Budget::Recursion.limit() {
return Err(over(Budget::Recursion, Budget::Recursion.limit(), line));
}
}
Ok(Scan {
tokens,
recursion: recursion.peak(),
})
}
fn lexed_tokens(token: Token<'_>, lexed: &[u8]) -> usize {
match token {
Token::Lifetime => 2,
Token::Bang
| Token::Minus
| Token::Star
| Token::Amp
| Token::AmpAmp
| Token::Pipe
| Token::PipePipe
| Token::Lt
| Token::Gt
| Token::Semi
| Token::Comma
| Token::FatArrow
| Token::Colon
| Token::PathSep
| Token::Hash
| Token::Operator
| Token::Other => lexed.len(),
Token::Open(_)
| Token::CloseBrace
| Token::CloseOther
| Token::Ident(_)
| Token::Literal
| Token::Float => 1,
}
}
fn punctuation<'a>(cursor: &mut Cursor<'_>, byte: u8) -> Token<'a> {
let next = cursor.peek(1);
let (token, width) = match (byte, next) {
(b'&', Some(b'&')) => (Token::AmpAmp, 2),
(b'|', Some(b'|')) => (Token::PipePipe, 2),
(b'=', Some(b'>')) => (Token::FatArrow, 2),
(b':', Some(b':')) => (Token::PathSep, 2),
(b'.', Some(b'.')) => (
Token::Operator,
if matches!(cursor.peek(2), Some(b'=' | b'.')) {
3
} else {
2
},
),
(b'&' | b'*' | b'-' | b'!' | b'|' | b'<', Some(b'=')) | (b'-', Some(b'>')) => {
(Token::Operator, 2)
}
(b'&', _) => (Token::Amp, 1),
(b'|', _) => (Token::Pipe, 1),
(b'!', _) => (Token::Bang, 1),
(b'-', _) => (Token::Minus, 1),
(b'*', _) => (Token::Star, 1),
(b'<', _) => (Token::Lt, 1),
(b'>', _) => (Token::Gt, 1),
(b';', _) => (Token::Semi, 1),
(b',', _) => (Token::Comma, 1),
(b':', _) => (Token::Colon, 1),
(b'#', _) => (Token::Hash, 1),
(b'+' | b'/' | b'%' | b'^' | b'=' | b'?' | b'@' | b'.', _) => (Token::Operator, 1),
_ => (Token::Other, 1),
};
cursor.bump_by(width);
token
}
fn word<'a>(cursor: &mut Cursor<'a>) -> Token<'a> {
let start = cursor.at;
let word = cursor.ident();
match (word, cursor.peek(0)) {
("b" | "c", Some(b'"')) => {
cursor.bump();
cursor.skip_quoted(b'"');
Token::Literal
}
("b", Some(b'\'')) => {
cursor.bump();
cursor.skip_quoted(b'\'');
Token::Literal
}
("r" | "br" | "cr", Some(b'"' | b'#')) => {
let hashes = cursor.hashes_at(0);
if cursor.peek(hashes) == Some(b'"') {
cursor.skip_raw_string(hashes);
Token::Literal
} else if word == "r" && hashes == 1 {
cursor.bump();
Token::Ident(cursor.ident())
} else {
Token::Ident(&cursor.text[start..cursor.at])
}
}
_ => Token::Ident(word),
}
}
fn number(cursor: &mut Cursor<'_>) -> bool {
let mut dotted = false;
while let Some(ch) = cursor.text[cursor.at..].chars().next() {
if ch == '.' {
if dotted || !cursor.peek(1).is_some_and(|byte| byte.is_ascii_digit()) {
break;
}
dotted = true;
} else if !is_ident_continue(ch) {
break;
}
cursor.bump_by(ch.len_utf8());
}
dotted
}