harn_parser/parser/
state.rs

1use crate::ast::*;
2use harn_lexer::{Span, Token, TokenKind};
3
4use super::error::ParserError;
5
6/// Deepest syntax nesting the parser descends into before refusing the source
7/// with a "nesting depth exceeded" error.
8pub const MAX_NESTING_DEPTH: usize = 64;
9
10/// Native stack a thread needs to parse any source the parser accepts.
11///
12/// The parser recurses once per nesting level, and an unoptimized build spends
13/// about 140 KiB of stack on each level of nested expressions. Rust's 2 MiB
14/// default thread stack is exhausted after about a dozen levels, long before
15/// [`MAX_NESTING_DEPTH`] refuses the source, and a stack overflow aborts the
16/// whole process rather than failing one parse. Any thread that runs the parser
17/// and was not created with at least this much stack must ask for it, as
18/// `harn_modules`' parallel module loader does.
19///
20/// The size follows the refusal, not the typical program: the parser must be
21/// able to reach [`MAX_NESTING_DEPTH`] and report it. `RUST_MIN_STACK` does
22/// not substitute: CI test lanes export it and no shipped binary does.
23pub const PARSE_STACK_SIZE: usize = 16 * 1024 * 1024;
24
25/// Recursive descent parser for Harn.
26pub struct Parser {
27    pub(super) tokens: Vec<Token>,
28    pub(super) pos: usize,
29    pub(super) errors: Vec<ParserError>,
30    nesting_depth: usize,
31}
32
33impl Parser {
34    pub(super) fn at_module_scope(&self) -> bool {
35        self.nesting_depth == 0
36    }
37
38    pub fn new(tokens: Vec<Token>) -> Self {
39        Self {
40            tokens,
41            pos: 0,
42            errors: Vec::new(),
43            nesting_depth: 0,
44        }
45    }
46
47    pub(super) fn check_token_nesting_limit(&self) -> Result<(), ParserError> {
48        let mut depth = 0usize;
49        for token in &self.tokens {
50            match token.kind {
51                TokenKind::LBrace | TokenKind::LBracket | TokenKind::LParen => {
52                    depth += 1;
53                    if depth > MAX_NESTING_DEPTH {
54                        return Err(ParserError::Unexpected {
55                            got: "source nesting depth exceeded".to_string(),
56                            expected: format!(
57                                "parser nesting depth within {MAX_NESTING_DEPTH} levels"
58                            ),
59                            span: token.span,
60                        });
61                    }
62                }
63                TokenKind::RBrace | TokenKind::RBracket | TokenKind::RParen => {
64                    depth = depth.saturating_sub(1);
65                }
66                _ => {}
67            }
68        }
69        Ok(())
70    }
71
72    pub(super) fn current_span(&self) -> Span {
73        self.tokens
74            .get(self.pos)
75            .map(|t| t.span)
76            .unwrap_or(Span::dummy())
77    }
78
79    pub(super) fn current_kind(&self) -> Option<&TokenKind> {
80        self.tokens.get(self.pos).map(|t| &t.kind)
81    }
82
83    pub(super) fn prev_span(&self) -> Span {
84        if self.pos > 0 {
85            self.tokens[self.pos - 1].span
86        } else {
87            Span::dummy()
88        }
89    }
90
91    /// Span of the most recently consumed *non-newline* token. Useful when
92    /// computing a node's end span after the parser has already consumed
93    /// trailing newlines (e.g. while looking ahead for an optional `else` /
94    /// `catch` / `finally` clause). Using `prev_span()` in that position
95    /// would report a newline token whose `end_line` is past the visual end
96    /// of the node, which downstream tools (notably the formatter) interpret
97    /// as belonging to the node.
98    pub(super) fn last_non_newline_span(&self) -> Span {
99        let mut i = self.pos;
100        while i > 0 {
101            i -= 1;
102            if self.tokens[i].kind != TokenKind::Newline {
103                return self.tokens[i].span;
104            }
105        }
106        Span::dummy()
107    }
108
109    /// Parse a complete .harn file. Reports multiple errors via recovery.
110    pub fn parse(&mut self) -> Result<Vec<SNode>, ParserError> {
111        self.check_token_nesting_limit()?;
112
113        let mut nodes = Vec::new();
114        self.skip_newlines();
115
116        while !self.is_at_end() {
117            // Recovery may leave us pointing at a stray `}` at top level; skip it.
118            if self.check(&TokenKind::RBrace) {
119                self.advance();
120                self.skip_newlines();
121                continue;
122            }
123
124            let result = if self.check(&TokenKind::Import) {
125                self.parse_import()
126            } else if self.check(&TokenKind::At) {
127                self.parse_attributed_decl()
128            } else if self.check(&TokenKind::Pipeline) {
129                self.parse_pipeline()
130            } else if self.check(&TokenKind::EvalPack) {
131                self.parse_eval_pack_decl(false)
132            } else {
133                self.parse_statement()
134            };
135
136            match result {
137                Ok(node) => {
138                    let end_line = node.span.end_line;
139                    nodes.push(node);
140                    let consumed_sep = self.consume_statement_separator();
141                    if !consumed_sep && !self.is_at_end() {
142                        self.require_statement_separator(end_line, "top-level item")?;
143                    }
144                }
145                Err(err) => {
146                    self.errors.push(err);
147                    self.synchronize();
148                }
149            }
150        }
151
152        if let Some(first) = self.errors.first() {
153            return Err(first.clone());
154        }
155        Ok(nodes)
156    }
157
158    /// Return all accumulated parser errors (after `parse()` returns).
159    pub fn all_errors(&self) -> &[ParserError] {
160        &self.errors
161    }
162
163    /// Check if the current token is one that starts a statement.
164    pub(super) fn is_statement_start(&self) -> bool {
165        matches!(
166            self.current_kind(),
167            Some(
168                TokenKind::Let
169                    | TokenKind::Const
170                    | TokenKind::Var
171                    | TokenKind::If
172                    | TokenKind::For
173                    | TokenKind::While
174                    | TokenKind::Match
175                    | TokenKind::Retry
176                    | TokenKind::Return
177                    | TokenKind::Throw
178                    | TokenKind::Fn
179                    | TokenKind::Pub
180                    | TokenKind::Try
181                    | TokenKind::Select
182                    | TokenKind::Pipeline
183                    | TokenKind::Import
184                    | TokenKind::Parallel
185                    | TokenKind::Enum
186                    | TokenKind::EvalPack
187                    | TokenKind::Struct
188                    | TokenKind::Interface
189                    | TokenKind::Emit
190                    | TokenKind::Guard
191                    | TokenKind::Require
192                    | TokenKind::Deadline
193                    | TokenKind::Yield
194                    | TokenKind::Mutex
195                    | TokenKind::Defer
196                    | TokenKind::Break
197                    | TokenKind::Continue
198                    | TokenKind::Tool
199                    | TokenKind::Skill
200                    | TokenKind::Impl
201            )
202        )
203    }
204
205    /// Advance past tokens until we reach a likely statement boundary.
206    pub(super) fn synchronize(&mut self) {
207        while !self.is_at_end() {
208            if self.check(&TokenKind::Semicolon) {
209                self.advance();
210                self.skip_newlines();
211                return;
212            }
213            if self.check(&TokenKind::Newline) {
214                self.advance();
215                if self.is_at_end() || self.is_statement_start() {
216                    return;
217                }
218                continue;
219            }
220            if self.check(&TokenKind::RBrace) {
221                return;
222            }
223            self.advance();
224        }
225    }
226
227    pub(super) fn is_at_end(&self) -> bool {
228        self.pos >= self.tokens.len()
229            || matches!(self.tokens.get(self.pos), Some(t) if t.kind == TokenKind::Eof)
230    }
231
232    pub(super) fn current(&self) -> Option<&Token> {
233        self.tokens.get(self.pos)
234    }
235
236    pub(super) fn peek_kind(&self) -> Option<&TokenKind> {
237        self.tokens.get(self.pos + 1).map(|t| &t.kind)
238    }
239
240    pub(super) fn peek_kind_at(&self, offset: usize) -> Option<&TokenKind> {
241        self.tokens.get(self.pos + offset).map(|t| &t.kind)
242    }
243
244    pub(super) fn check(&self, kind: &TokenKind) -> bool {
245        self.current()
246            .map(|t| std::mem::discriminant(&t.kind) == std::mem::discriminant(kind))
247            .unwrap_or(false)
248    }
249
250    /// Check for `kind`, skipping newlines first; used for binary operators
251    /// like `||` and `&&` that can span lines.
252    pub(super) fn check_skip_newlines(&mut self, kind: &TokenKind) -> bool {
253        let saved = self.pos;
254        self.skip_newlines();
255        if self.check(kind) {
256            true
257        } else {
258            self.pos = saved;
259            false
260        }
261    }
262
263    /// Check if current token is an identifier with the given name (without consuming it).
264    pub(super) fn check_identifier(&self, name: &str) -> bool {
265        matches!(self.current().map(|t| &t.kind), Some(TokenKind::Identifier(s)) if s == name)
266    }
267
268    /// `gen` is contextual so existing identifiers named `gen` keep working.
269    /// It starts a stream declaration only when followed by `fn`.
270    pub(super) fn check_contextual_gen_fn(&self) -> bool {
271        if !self.check_identifier("gen") {
272            return false;
273        }
274        matches!(
275            self.tokens.get(self.pos + 1).map(|t| &t.kind),
276            Some(TokenKind::Fn)
277        )
278    }
279
280    /// Block-introducing words remain contextual so identically named values,
281    /// dict keys, and properties keep working. They introduce a block only
282    /// when immediately followed by `{` at statement position.
283    pub(super) fn check_contextual_brace_block(&self, name: &str) -> bool {
284        if !self.check_identifier(name) {
285            return false;
286        }
287        matches!(
288            self.tokens.get(self.pos + 1).map(|t| &t.kind),
289            Some(TokenKind::LBrace)
290        )
291    }
292
293    pub(super) fn advance(&mut self) {
294        if self.pos < self.tokens.len() {
295            self.pos += 1;
296        }
297    }
298
299    pub(super) fn consume(
300        &mut self,
301        kind: &TokenKind,
302        expected: &str,
303    ) -> Result<Token, ParserError> {
304        self.skip_newlines();
305        let tok = self.current().ok_or_else(|| self.make_error(expected))?;
306        if std::mem::discriminant(&tok.kind) != std::mem::discriminant(kind) {
307            return Err(self.make_error(expected));
308        }
309        let tok = tok.clone();
310        self.advance();
311        Ok(tok)
312    }
313
314    pub(super) fn consume_identifier(&mut self, expected: &str) -> Result<String, ParserError> {
315        self.skip_newlines();
316        let tok = self.current().ok_or_else(|| self.make_error(expected))?;
317        if let TokenKind::Identifier(name) = &tok.kind {
318            let name = name.clone();
319            self.advance();
320            Ok(name)
321        } else {
322            // Distinguish reserved-keyword misuse (e.g. `for tool in list`) from
323            // a general unexpected token so the error is actionable.
324            let kw_name = harn_lexer::KEYWORDS
325                .iter()
326                .find(|&&kw| kw == tok.kind.to_string());
327            if let Some(kw) = kw_name {
328                Err(ParserError::Unexpected {
329                    got: format!("'{kw}' (reserved keyword)"),
330                    expected: expected.into(),
331                    span: tok.span,
332                })
333            } else {
334                Err(self.make_error(expected))
335            }
336        }
337    }
338
339    pub(super) fn consume_contextual_keyword(
340        &mut self,
341        name: &str,
342        expected: &str,
343    ) -> Result<Token, ParserError> {
344        self.skip_newlines();
345        let tok = self.current().ok_or_else(|| self.make_error(expected))?;
346        if matches!(&tok.kind, TokenKind::Identifier(id) if id == name) {
347            let tok = tok.clone();
348            self.advance();
349            Ok(tok)
350        } else {
351            Err(self.make_error(expected))
352        }
353    }
354
355    /// Like `consume_identifier`, but also accepts keywords as identifiers.
356    /// Used for property access (e.g., `obj.type`) and dict keys where
357    /// keywords are valid member names.
358    pub(super) fn consume_identifier_or_keyword(
359        &mut self,
360        expected: &str,
361    ) -> Result<String, ParserError> {
362        self.skip_newlines();
363        let tok = self.current().ok_or_else(|| self.make_error(expected))?;
364        if let TokenKind::Identifier(name) = &tok.kind {
365            let name = name.clone();
366            self.advance();
367            return Ok(name);
368        }
369        let name = match &tok.kind {
370            TokenKind::Pipeline => "pipeline",
371            TokenKind::Extends => "extends",
372            TokenKind::Override => "override",
373            TokenKind::Let => "let",
374            TokenKind::Const => "const",
375            TokenKind::Var => "var",
376            TokenKind::If => "if",
377            TokenKind::Else => "else",
378            TokenKind::For => "for",
379            TokenKind::In => "in",
380            TokenKind::Match => "match",
381            TokenKind::Retry => "retry",
382            TokenKind::Parallel => "parallel",
383            TokenKind::Return => "return",
384            TokenKind::Import => "import",
385            TokenKind::True => "true",
386            TokenKind::False => "false",
387            TokenKind::Nil => "nil",
388            TokenKind::Try => "try",
389            TokenKind::Catch => "catch",
390            TokenKind::Throw => "throw",
391            TokenKind::Finally => "finally",
392            TokenKind::Fn => "fn",
393            TokenKind::Spawn => "spawn",
394            TokenKind::While => "while",
395            TokenKind::TypeKw => "type",
396            TokenKind::Enum => "enum",
397            TokenKind::EvalPack => "eval_pack",
398            TokenKind::Struct => "struct",
399            TokenKind::Interface => "interface",
400            TokenKind::Emit => "emit",
401            TokenKind::Pub => "pub",
402            TokenKind::From => "from",
403            TokenKind::To => "to",
404            TokenKind::Tool => "tool",
405            TokenKind::Exclusive => "exclusive",
406            TokenKind::Guard => "guard",
407            TokenKind::Require => "require",
408            TokenKind::Deadline => "deadline",
409            TokenKind::Defer => "defer",
410            TokenKind::Yield => "yield",
411            TokenKind::Mutex => "mutex",
412            TokenKind::Break => "break",
413            TokenKind::Continue => "continue",
414            TokenKind::Select => "select",
415            TokenKind::Impl => "impl",
416            TokenKind::Skill => "skill",
417            _ => return Err(self.make_error(expected)),
418        };
419        let name = name.to_string();
420        self.advance();
421        Ok(name)
422    }
423
424    pub(super) fn skip_newlines(&mut self) {
425        while self.pos < self.tokens.len() && self.tokens[self.pos].kind == TokenKind::Newline {
426            self.pos += 1;
427        }
428    }
429
430    /// Consume an optional semicolon statement separator followed by any
431    /// number of newlines, or one-or-more newlines on their own.
432    ///
433    /// This is intentionally narrower than `skip_newlines()`: semicolons are
434    /// only legal between already-parsed list items, not in arbitrary parse
435    /// positions.
436    pub(super) fn consume_statement_separator(&mut self) -> bool {
437        let mut consumed = false;
438        if self.check(&TokenKind::Semicolon) {
439            self.advance();
440            consumed = true;
441        }
442        let start = self.pos;
443        self.skip_newlines();
444        consumed || self.pos != start
445    }
446
447    pub(super) fn require_statement_separator(
448        &self,
449        prev_end_line: usize,
450        expected_item: &str,
451    ) -> Result<(), ParserError> {
452        let Some(tok) = self.current() else {
453            return Ok(());
454        };
455        if tok.kind == TokenKind::Eof || tok.span.line != prev_end_line {
456            return Ok(());
457        }
458        Err(ParserError::Unexpected {
459            got: tok.kind.to_string(),
460            expected: format!("{expected_item} separator (`;` or newline)"),
461            span: tok.span,
462        })
463    }
464
465    pub(super) fn make_error(&self, expected: &str) -> ParserError {
466        if let Some(tok) = self.tokens.get(self.pos) {
467            if tok.kind == TokenKind::Eof {
468                return ParserError::UnexpectedEof {
469                    expected: expected.into(),
470                    span: tok.span,
471                };
472            }
473            ParserError::Unexpected {
474                got: tok.kind.to_string(),
475                expected: expected.into(),
476                span: tok.span,
477            }
478        } else {
479            ParserError::UnexpectedEof {
480                expected: expected.into(),
481                span: self.prev_span(),
482            }
483        }
484    }
485
486    pub(super) fn error(&self, expected: &str) -> ParserError {
487        self.make_error(expected)
488    }
489
490    pub(super) fn with_nesting<T>(
491        &mut self,
492        context: &'static str,
493        f: impl FnOnce(&mut Self) -> Result<T, ParserError>,
494    ) -> Result<T, ParserError> {
495        if self.nesting_depth >= MAX_NESTING_DEPTH {
496            return Err(ParserError::Unexpected {
497                got: format!("{context} nesting depth exceeded"),
498                expected: format!("parser nesting depth within {MAX_NESTING_DEPTH} levels"),
499                span: self.current_span(),
500            });
501        }
502        self.nesting_depth += 1;
503        let result = f(self);
504        self.nesting_depth = self.nesting_depth.saturating_sub(1);
505        result
506    }
507}
harn_parser/parser/state.rs

harn_parser/parser/
state.rs
