Skip to main content

relate_parser/parser/
mod.rs

1use crate::ast::*;
2use crate::error::{ParseError, ParseResult, SUPPORTED_CYPHER_VERSION};
3use crate::lexer::tokenize_with_options;
4use crate::token::{is_clause_boundary, is_contextual_clause_keyword, Token, TokenType};
5use relate_names::SmallName;
6// `pub(crate)` beyond the parser module for the statement normalizer
7// (ADR-0503), which extracts the same values the parser would bind.
8use interp::parse_interp_body;
9use is_predicate::{IsLabelPolicy, Suffix};
10pub(crate) use literals::parse_int_literal;
11use literals::{IntLiteralError, IntLiteralSite};
12
13/// `parse_constraint_for_target_ext`'s result: the `FOR <pattern>` target of
14/// a `CREATE CONSTRAINT`.
15struct ConstraintForTarget {
16    entity_type: SchemaEntityType,
17    /// The flat label/relationship-type list (empty for a label-less
18    /// target).
19    labels: Vec<SmallName>,
20    /// The FOR pattern's own variable, `""` when it has none (the shape
21    /// `CreateConstraintClause::variable` stores).
22    variable: SmallName,
23    /// A relationship pattern's source endpoint alias (CIP-177); `None`
24    /// for a node target or an alias-less endpoint.
25    source_alias: Option<SmallName>,
26    /// A relationship pattern's target endpoint alias, like `source_alias`.
27    target_alias: Option<SmallName>,
28}
29
30/// `parse_graph_type_constraint_verb`'s return shape: the constraint kind,
31/// the parsed `<value type>` for a `PropertyType` kind, and the `OPTIONS`
32/// tail.
33struct GraphTypeConstraintVerbSpec {
34    kind: GraphTypeConstraintVerb,
35    /// The `<value type>` of a `PropertyType` kind, `None` otherwise.
36    property_type: Option<TypeExpr>,
37    options: OptionsForm,
38}
39
40/// ADR-0257: maximum size of a Cypher query text accepted by [`parse`], in
41/// bytes (4 MiB). Enforced *before lexing* so that adversarial inputs cannot
42/// amplify into unbounded token allocations (LABS-81: 8 MiB of commas used to
43/// become >=520 MB of tokens). Every query path -- the Rust API, the C ABI,
44/// the CLI, the TCK, and Bolt -- funnels through the parser's entry points,
45/// each of which constructs through `Parser::new`, the one site the cap is
46/// enforced, so this single check covers them all.
47pub const MAX_QUERY_BYTES: usize = 4 * 1024 * 1024; // 4 MiB = 4 194 304
48
49/// ADR-0257: maximum nesting depth accepted while parsing. Enforced on
50/// expression nesting (every nested expression -- parenthesized constructs,
51/// list/map literals, function-call arguments, subqueries, ... -- descends
52/// through [`Parser::parse_expression`]; `NOT` chains recurse through
53/// [`Parser::parse_not`]) and on statement nesting (subquery bodies).
54/// Recursive-descent parsing beyond this depth risks a stack-overflow abort,
55/// which -- when the engine is embedded via the C ABI -- kills the host
56/// process instead of surfacing a recoverable error (LABS-69). The front-end
57/// lowering boundary enforces the same limit on its own walkers.
58pub const MAX_NESTING_DEPTH: u32 = 500;
59
60/// ADR-0116 §2: the [`ParseError::detail`] tag on a parse failure for a
61/// recognized-but-unsupported database administration command (everything
62/// outside CE's supported set on Relate's fixed namespaces). The
63/// error's `message` carries the verbatim statement text (without a leading
64/// `CYPHER n` preamble), so `relate-front` can raise CE's
65/// `UnsupportedAdministrationCommand` (51N27) echoing it. The tag name
66/// matches `ErrorKind::UnsupportedAdministrationCommand` in
67/// `relate-error`, so even an unmapped parse error keeps the right TCK
68/// kind/class.
69pub const UNSUPPORTED_ADMINISTRATION_DETAIL: &str = "UnsupportedAdministrationCommand";
70
71/// The [`ParseError::detail`] tag naming the undefined-variable condition
72/// (Neo4j 42N62): every parser site that rejects an unbound name carries it,
73/// so `EngineError::kind()` surfaces `UndefinedVariable` instead of the
74/// generic `UnexpectedSyntax` fallback. The tag name matches
75/// `ErrorKind::UndefinedVariable` in `relate-error`.
76pub const UNDEFINED_VARIABLE_DETAIL: &str = "UndefinedVariable";
77
78/// Parse a Cypher query string into a Statement AST.
79pub fn parse(input: &str) -> ParseResult<Statement> {
80    parse_with_options(input, crate::lexer::ParseOptions::default())
81}
82
83/// Parse a Cypher query string into a Statement AST under
84/// parse-affecting preview opt-ins ([`crate::lexer::ParseOptions`]: the
85/// ADR-0371 gate set the caller's store resolved from
86/// `RELATE_PREVIEW`, threaded here by `relate-front`'s preview
87/// admission). [`crate::lexer::ParseOptions::default`] is the dialect
88/// floor: every option widens acceptance of a form the floor rejects,
89/// never narrows it, so the ungated [`parse`] is exactly
90/// `parse_with_options` with all options off. The ADR-0257 size cap rides
91/// the constructor (`Parser::new`'s first statement), the parser's one
92/// tokenizing site -- not this entry point.
93pub fn parse_with_options(
94    input: &str,
95    options: crate::lexer::ParseOptions,
96) -> ParseResult<Statement> {
97    let mut parser = Parser::new(input, "query text", options)?;
98    parser.parse()
99}
100
101/// Parse a bare value expression under explicit parse-affecting preview
102/// opt-ins ([`crate::lexer::ParseOptions`]). Used for CIP-261 interpolation
103/// embeds: the `{...}` body of an interpolated string literal is a full
104/// expression, sub-parsed by [`parse_interp_body`] with the options of the
105/// parse that lexed the enclosing statement, so an embed observes the
106/// caller's dialect gates instead of silently re-parsing under the floor.
107/// `pub(crate)`: its only callers are in this crate (the public floor
108/// wrapper [`parse_expression_str`] and the embed sub-parse); it is
109/// promoted to `pub` -- with a root re-export beside
110/// [`parse`]/[`parse_with_options`] -- when a second crate needs gated
111/// expression parsing. The ADR-0257 size cap rides the constructor
112/// (`Parser::new`'s first statement), the parser's one tokenizing site --
113/// not this entry point.
114pub(crate) fn parse_expression_str_with_options(
115    input: &str,
116    options: crate::lexer::ParseOptions,
117) -> ParseResult<Expr> {
118    let mut parser = Parser::new(input, "expression text", options)?;
119    let expr = parser.parse_expression()?;
120    if parser.peek().ty != TokenType::EOF {
121        return Err(parser
122            .error_at_token(parser.peek(), "unexpected trailing input in expression")
123            .with_detail("UnexpectedSyntax"));
124    }
125    Ok(expr)
126}
127
128/// Parse a bare value expression on the dialect floor
129/// ([`crate::lexer::ParseOptions::default`]) -- the public wrapper for
130/// callers with no preview gates to thread; gated callers (and the
131/// interpolation-embed sub-parse) use `parse_expression_str_with_options`.
132pub fn parse_expression_str(input: &str) -> ParseResult<Expr> {
133    parse_expression_str_with_options(input, crate::lexer::ParseOptions::default())
134}
135
136/// Parse a bare `<graph type specification body>` -- the `{ ... }` grammar
137/// shared by `CREATE GRAPH TYPE`/`ALTER CURRENT GRAPH TYPE`, without the
138/// surrounding statement (`canonical` is wrapped in braces here, so callers
139/// pass the CIP-180 canonical form's comma-joined contents, no braces of
140/// their own). Used by `relate-executor`'s `Graph` to reconstruct a
141/// persisted `current_graph_type` model from the snapshot manifest on load
142/// -- see `Graph::restore_graph_type_spec`. The ADR-0257 size cap rides the
143/// constructor (`Parser::new`'s first statement) and checks the wrapped
144/// string -- the exact text this entry point lexes.
145pub fn parse_graph_type_body(canonical: &str) -> ParseResult<GraphTypeBody> {
146    let wrapped = format!("{{{canonical}}}");
147    let mut parser = Parser::new(
148        &wrapped,
149        "graph type body",
150        crate::lexer::ParseOptions::default(),
151    )?;
152    let (open, body) = parser.parse_graph_type_spec_body()?;
153    parser.reject_bare_constraint_drops(&open, &body)?;
154    Ok(body)
155}
156
157/// CIP-150: the pre-parser option keys Relate recognizes after a
158/// `CYPHER [<version>]` clause (besides the version itself). These mirror
159/// Neo4j's own pre-parser option vocabulary; Relate validates that a
160/// key is recognized and internally consistent but -- since it implements
161/// only one query-execution engine/runtime -- doesn't act on any of their
162/// values.
163const CYPHER_OPTION_KEYS: &[&str] = &[
164    "planner",
165    "runtime",
166    "updatestrategy",
167    "expressionengine",
168    "replan",
169    "connectcomponentsplanner",
170    "debug",
171    "operatorengine",
172];
173
174/// CIP-150 / Neo4j 2026.10: the pre-parser option keys whose *values*
175/// carry a constrained vocabulary, with each key's valid values -- the
176/// value-side twin of [`CYPHER_OPTION_KEYS`]' 22N07 key check. The one
177/// key with a vocabulary today is `runtime`, mirroring the three runtimes
178/// of Neo4j's current line (slotted, pipelined, parallel; the CIP-150
179/// corpus's accepted `runtime=slotted` examples pin the Cypher-5 side of
180/// that set). Relate implements a single engine, so every listed
181/// value is accepted-and-ignored; any other value fails with an authored
182/// 22N10 error naming the valid set.
183const CYPHER_OPTION_VALUES: &[(&str, &[&str])] =
184    &[("runtime", &["slotted", "pipelined", "parallel"])];
185
186/// The recursive-descent parser over a borrowed token stream. `'a` is the
187/// input query text's lifetime: the [`Token`] literals and [`Self::source`]
188/// borrow it (ADR-0505), and the parser — built and dropped inside the
189/// parse entry points — never outlives it. The AST it produces stays
190/// `'static` (owned strings).
191struct Parser<'a> {
192    source: &'a str,
193    tokens: Vec<Token<'a>>,
194    pos: usize,
195    /// Byte offset of the first byte of each 1-based source line
196    /// (`line_starts[0] == 0` is line 1's start). Precomputed once per parse
197    /// so `token_byte_offset` is O(1) instead of rescanning the whole source
198    /// per projection item. The lexer counts columns in *bytes* (see
199    /// `Lexer::advance`), so a token's byte offset is exactly
200    /// `line_starts[line - 1] + col - 1` — this also fixes the old
201    /// char-counted scan, which mismatched the lexer's byte-counted columns
202    /// (and returned `None`) as soon as any non-ASCII char preceded the
203    /// token.
204    line_starts: Vec<usize>,
205    /// The clause-level pattern side-effect flags (label/quantifier mixing
206    /// state); see [`PatternSideEffectFlags`]. One field so a speculative
207    /// parse can snapshot/restore it by plain assignment.
208    side_effects: PatternSideEffectFlags,
209    /// Nesting depth of `parse_when_query` branch/ELSE bodies currently
210    /// being parsed -- 0 outside any such body. While positive, a bare
211    /// (non-brace) body's own clause loop (`parse_statement`) must stop at
212    /// a following `WHEN` too, not just `ELSE`/EOF/etc, so control returns
213    /// to `parse_when_query`'s own loop to see the next branch (CIP-213
214    /// `next_conditional_interactions.feature`: `WHEN a THEN RETURN
215    /// x WHEN b THEN RETURN y ELSE RETURN z`, no braces anywhere). Scoped
216    /// to *this* mechanism only -- a bare `WHEN` appearing after an
217    /// ordinary clause outside any WHEN-body context (e.g. `MATCH (n)
218    /// WHEN ...`) must remain a hard parse error (CIP-135
219    /// syntax_placement.feature [8]/[9]), so this must stay zero there.
220    in_when_branch_body: u32,
221    /// Nesting depth of `parse_statement` calls -- 0 outside any statement,
222    /// 1 while parsing the outermost statement, 2+ while parsing a nested
223    /// `EXISTS {}`/`COUNT {}`/`CALL {}` subquery's own statement body. Used
224    /// to scope the label-expression mixing flags to one top-level
225    /// statement; see `parse_statement`'s doc comment. Also capped at
226    /// [`MAX_NESTING_DEPTH`] (ADR-0257) so deeply nested subquery bodies
227    /// cannot overflow the stack via pure statement recursion.
228    statement_depth: u32,
229    /// Current statement-block nesting depth (ADR-0257): incremented on
230    /// entering `parse_statement_block`, decremented on exit. Every
231    /// statement-nesting cycle funnels through `parse_statement_block` --
232    /// CALL/EXISTS/COUNT/COLLECT subquery bodies, brace-enclosed nested
233    /// procedure specifications (`{ { ... } }`), and WHEN/ELSE bodies
234    /// (`WHEN ... THEN { WHEN ... }`) -- including the cycles that bypass
235    /// `parse_statement`, `parse_clause`, and `parse_expression` and so
236    /// never engage any other counter (LABS-69: ~3000 nested braces used
237    /// to SIGABRT on an 8 MiB release stack). Unlike `statement_depth`,
238    /// this counter is *not* consulted for label-mixing scoping, so a
239    /// top-level `{ ... }` body incrementing it cannot flip
240    /// `is_outer_clause`. Capped at [`MAX_NESTING_DEPTH`].
241    block_depth: u32,
242    /// Current expression nesting depth (ADR-0257): incremented on entering
243    /// `parse_expression` and on each recursive `parse_not` step, decremented
244    /// on exit. Every nested expression -- parenthesized constructs, list
245    /// literals, map literals, function-call arguments, CASE operands,
246    /// comprehension bodies, subquery WHERE/RETURN expressions -- descends
247    /// through `parse_expression`, so this one counter bounds all expression
248    /// recursion. Also counts recursion cycles that bypass
249    /// `parse_expression` but are expression-shaped: unary `-`/`!` chains,
250    /// nested label/subpath parens, and nested `LIST<...>`/`ANY<...>`
251    /// value-type brackets (see `parse_value_type`). Capped at
252    /// [`MAX_NESTING_DEPTH`] (LABS-69).
253    expr_depth: u32,
254    /// Current clause nesting depth (ADR-0257): incremented on entering
255    /// `parse_clause`, decremented on exit. Both callers of `parse_clause`
256    /// (`parse_statement`'s body loop and `parse_foreach`'s body loop) are
257    /// loops, so the counter returns to baseline after every clause and
258    /// only grows with *true* clause nesting. That nesting exists: nested
259    /// FOREACH bodies recurse `parse_clause` -> `parse_clause_inner` ->
260    /// `parse_foreach` -> `parse_clause`, bypassing `parse_statement`, so
261    /// the `statement_depth` cap never engages on that cycle (LABS-69).
262    /// Capped at [`MAX_NESTING_DEPTH`].
263    clause_depth: u32,
264    /// True while parsing the `WHERE`-part expression of a list/pattern
265    /// comprehension. There, a bare `|` is genuinely ambiguous: it could
266    /// continue a label-expression disjunction (`x:A|B`) or be the
267    /// comprehension's own map-expression separator (`WHERE x:A | expr]`).
268    /// `parse_label_or` consults this flag to check, before committing to
269    /// the disjunction reading, whether doing so would strand a
270    /// well-formed label chain in front of tokens that can't follow one
271    /// (e.g. `.` for property access) -- see `label_or_pipe_is_ambiguous`,
272    /// which answers the question with a pure token-level scan.
273    comprehension_where_ambiguous_pipe: bool,
274    /// Whether the comprehension being parsed *requires* a map expression
275    /// after its `|` separator (a pattern comprehension always does, a list
276    /// comprehension need not). A `]` right after the scanned label chain
277    /// then proves that `|` was the separator, not a label disjunction --
278    /// see `label_or_pipe_is_ambiguous`.
279    comprehension_where_map_required: bool,
280    /// Depth of `EXISTS { … }` bodies currently being parsed. An unbounded
281    /// quantified path pattern under REPEATABLE ELEMENTS is safe inside an
282    /// existence probe (the probe stops at the first row) and is accepted
283    /// there, while a top-level match still rejects it (42N53).
284    exists_subquery_depth: u32,
285    /// Memo of `pattern_comprehension_follows_equals` verdicts, keyed by
286    /// the token position of the `=` the probe starts at. The parse is
287    /// deterministic and the probe restores the token position and every
288    /// side-effect flag before returning, so the verdict depends only on
289    /// that position -- and a `true` verdict is always re-parsed for real
290    /// by the caller, which re-enforces the nesting-depth caps. Without
291    /// the memo, each level of a nested `[v = (n {p: ...}) | ...]` shape
292    /// probes *and* re-parses the whole nested term, giving 2^k parse
293    /// cost (LABS-183: ~0.7 s release at k=20, doubling per level); with
294    /// it each position is probed once and the shape is O(k^2) overall.
295    pattern_comprehension_probe_memo: std::collections::HashMap<usize, bool>,
296    /// Memo of `scan_label_primary_extent`'s group-case extents, keyed by
297    /// the opener's absolute token index and the scan's nesting depth. The
298    /// scan is a pure function of `self.tokens` (fixed for the parse) and
299    /// that depth -- `dynamic_label_quantifier_at(pos - self.pos)` reads
300    /// `tokens[self.pos + (pos - self.pos)]` == `tokens[pos]`, so `self.pos`
301    /// cancels out, and scan positions always stay at or past `self.pos` --
302    /// so a cached entry always equals a fresh scan. Without it each level
303    /// of a nested wide label disjunction re-walks its whole child subtree
304    /// (O(width * depth^2), ~31 s on a slow Windows debug runner); with it
305    /// every group extent is computed once (O(tokens)).
306    label_group_extent_memo: std::collections::HashMap<(usize, u32), Option<usize>>,
307    /// The parse-affecting preview opt-ins for this parse (see
308    /// [`crate::lexer::ParseOptions`]). Set once by `Parser::new` from the
309    /// entry point's options; never mutated mid-parse, so nested and
310    /// speculative parses all observe one dialect.
311    options: crate::lexer::ParseOptions,
312    /// Which label-mixing accumulator the clause being parsed feeds (see
313    /// [`LabelMixTarget`]). Saved and restored around each clause so a
314    /// nested subquery body's clauses choose their own side.
315    label_mix_target: LabelMixTarget,
316}
317
318/// The clause-level side-effect flags a pattern parse can set. Kept as one
319/// `Copy` field on `Parser` (`Parser::side_effects`) so a speculative
320/// `parse_pattern_path` probe snapshots and restores them by plain
321/// assignment (see `pattern_comprehension_follows_equals`), and the
322/// clause-start reset is a single `Default::default()` (plus the two
323/// quantifier flags' per-clause reset for nested clauses).
324#[derive(Default, Clone, Copy)]
325struct PatternSideEffectFlags {
326    /// The label-mixing forms seen in the clause currently being parsed.
327    /// `parse_insert` reads this for its own clause-local rejection (a
328    /// `:A:B` chain is never allowed in INSERT); it is reset at the start of
329    /// every clause, nested or not.
330    clause_labels: LabelMixFlags,
331    /// The label-mixing forms seen by the read clauses accumulated in the
332    /// current scope. Neo4j keeps the read side (MATCH/WITH/RETURN label
333    /// predicates) and the write side (CREATE/INSERT; MERGE counts as both)
334    /// apart: inside one `CALL { … }` body `MATCH (n:A:B)` followed by
335    /// `CREATE (m IS B)` is legal, while two MATCHes (or a MERGE and a
336    /// CREATE) mixing the forms are not. See `PatternSideEffectFlags::read_labels`.
337    read_labels: LabelMixFlags,
338    /// The write side of the split described on [`Self::read_labels`].
339    write_labels: LabelMixFlags,
340    /// The forms the ONE label/type expression currently being parsed has
341    /// seen (`legacy_conjunction` and `gql_symbol` only). Reset at the
342    /// entry of `parse_label_expr_body`; `mixed-label-syntax` admits
343    /// mixing across separate label expressions of one clause, but Neo4j
344    /// keeps it illegal *within* one expression
345    /// (GpmSyntaxMixingAllowedAcceptance "Mixing : conjunction with
346    /// GPM-only label/type expression operators": `(n:A|B:C)`).
347    expression_labels: LabelMixFlags,
348    /// True if a parenthesized label-expression group (`(A:B)`, `(A&B)`,
349    /// ...) was parsed anywhere in the clause currently being parsed.
350    /// CIP-114: CREATE/MERGE/MATCH allow this grouping, but INSERT does
351    /// not -- `parse_insert` checks this flag after parsing its pattern,
352    /// same reset/scoping as [`Self::clause_labels`].
353    label_saw_paren_group: bool,
354    /// The quantifier forms seen anywhere in the clause currently being
355    /// parsed. Neo4j rejects mixing the pre-GPM bracket quantifier
356    /// (`[*min..max]`, including a bare `[*]`) with a GPM postfix/QPP
357    /// quantifier (`->+`, `->*`, `->{m,n}`, `((...)...){m,n}`) *within the
358    /// same clause* -- but not across separate clauses/statements (CIP-40
359    /// quantifier-mixing.feature scenario 9 vs scenario 10), checked in
360    /// `check_quantifier_mixing`.
361    quantifiers: QuantifierForms,
362    /// Quantifier forms seen inside pattern comprehensions of the clause
363    /// currently being parsed (accumulated across all of its
364    /// comprehensions). A comprehension's inner pattern is its own pattern
365    /// context: its quantifier forms never combine with the clause's own
366    /// (a legacy `[:R*1..2]` inside a comprehension nested in a quantified
367    /// path pattern's WHERE is legal, Neo4j
368    /// QuantifiedPathPatternAcceptance "Pattern comprehension containing a
369    /// variable-length relationship inside a QPP is allowed"), but two
370    /// comprehensions in the same clause still combine with each other
371    /// (CIP-40 label-expression-mixing.feature scenario 13,
372    /// quantifier-mixing.feature scenario 10) -- so these are a separate
373    /// accumulator, checked separately from [`Self::quantifiers`].
374    comprehension_quantifiers: QuantifierForms,
375}
376
377/// The two quantifier syntaxes whose mixing Neo4j rejects within one clause.
378#[derive(Default, Clone, Copy)]
379struct QuantifierForms {
380    /// A legacy bracket-syntax variable-length quantifier (`[*min..max]`).
381    legacy_bracket: bool,
382    /// A GPM postfix or QPP quantifier.
383    gpm_form: bool,
384}
385
386impl QuantifierForms {
387    fn mixed(self) -> bool {
388        self.legacy_bracket && self.gpm_form
389    }
390
391    /// Folds another accumulator's forms into this one.
392    fn absorb(&mut self, other: Self) {
393        self.legacy_bracket |= other.legacy_bracket;
394        self.gpm_form |= other.gpm_form;
395    }
396}
397
398/// The three label-expression forms whose mixing Neo4j rejects within one
399/// clause (CIP-14/CIP-40).
400#[derive(Default, Clone, Copy)]
401struct LabelMixFlags {
402    /// A legacy multi-label colon-conjunction (`:A:B`).
403    legacy_conjunction: bool,
404    /// A GQL label-expression symbol (`&`, `!`, `%`, a grouping paren, or
405    /// `|` on a node).
406    gql_symbol: bool,
407    /// A pattern-position `IS` label/type introducer (`(n IS A)`,
408    /// `-[IS R]->`), even without any GQL symbol beside it.
409    is_introducer: bool,
410}
411
412impl LabelMixFlags {
413    /// The within-one-expression rule (used on the `expression_labels`
414    /// accumulator): colon-conjunction beside a GQL symbol.
415    fn within_expression_mixing(&self) -> bool {
416        self.legacy_conjunction && self.gql_symbol
417    }
418
419    /// The rejection this set of forms triggers, if any. The GQL-symbol rule
420    /// is reported before the `IS` rule, matching the reference engine's
421    /// 42I10-before-42I29 precedence.
422    fn mixing(&self) -> Option<&'static str> {
423        if self.legacy_conjunction && self.gql_symbol {
424            return Some(
425                "InvalidLabelExpression: mixing label expression symbols (|, &, !, and %) with colon (:) between labels is not allowed",
426            );
427        }
428        if self.legacy_conjunction && self.is_introducer {
429            return Some(
430                "MixedIsAndColonConjunction: cannot mix the IS introducer with colon-conjunction within the same clause",
431            );
432        }
433        None
434    }
435}
436
437/// Which accumulator(s) the label forms of the clause being parsed feed.
438/// Neo4j keeps read clauses and write clauses apart when combining the forms
439/// across the clauses of one subquery scope; MERGE is both, and a label
440/// specification written by SET/REMOVE never joins either side.
441#[derive(Clone, Copy, Default, PartialEq, Eq)]
442enum LabelMixTarget {
443    #[default]
444    None,
445    Read,
446    Write,
447    Both,
448}
449
450/// A single postfix accessor (`.prop` or CIP-131's `[<expr>]`) parsed after
451/// a SET/REMOVE target's base expression by `Parser::parse_property_target_accessors`.
452enum PropertyTargetAccessor {
453    Static(SmallName),
454    Dynamic(Expr),
455}
456
457/// Generates the `enter_*_depth` / `exit_*_depth` / `with_*_depth` triple
458/// for one depth-guard counter field (ADR-0257, LABS-69). The four
459/// families (`expr_depth`, `clause_depth`, `statement_depth`,
460/// `block_depth`) share one mechanically identical shape; generating them
461/// from a single definition keeps the balanced-enter/exit property true by
462/// construction: `enter` leaves the counter unchanged on error, `exit` is
463/// a saturating decrement, and `with` captures `f`'s result (including
464/// error propagation), decrements, and only then returns, so no `?` can
465/// ever sit between enter and exit. The limit check and error message are
466/// byte-identical across families.
467macro_rules! depth_guard_family {
468    (
469        field = $field:ident,
470        enter = $enter:ident,
471        exit = $exit:ident,
472        with = $with:ident,
473        enter_doc = $enter_doc:expr,
474        exit_doc = $exit_doc:expr,
475        with_doc = $with_doc:expr $(,)?
476    ) => {
477        #[doc = $enter_doc]
478        fn $enter(&mut self) -> ParseResult<()> {
479            if self.$field >= MAX_NESTING_DEPTH {
480                return Err(self.error(format!(
481                    "maximum nesting depth of {MAX_NESTING_DEPTH} exceeded"
482                )));
483            }
484            self.$field += 1;
485            Ok(())
486        }
487
488        #[doc = $exit_doc]
489        fn $exit(&mut self) {
490            self.$field = self.$field.saturating_sub(1);
491        }
492
493        #[doc = $with_doc]
494        fn $with<T>(&mut self, f: impl FnOnce(&mut Self) -> ParseResult<T>) -> ParseResult<T> {
495            self.$enter()?;
496            let result = f(self);
497            self.$exit();
498            result
499        }
500    };
501}
502
503/// The running base of [`Parser::parse_postfix`]'s postfix chain, making
504/// the namespace-call accumulation invariant structural instead of
505/// comment-held.
506///
507/// While a dot-chain the memoized `scan_dot_chain_for_call` classified as
508/// ending in `(` is being accumulated, the base is [`PostfixBase::NsPath`]
509/// — a bare namespace-path string with *no* `Expr` — so no postfix arm can
510/// observe or rebuild a stale intermediate expression (materializing one
511/// per segment cost Θ(n²) in string clones, a parse-time DoS on maximal
512/// inputs). Everywhere else the base is [`PostfixBase::Built`].
513enum PostfixBase {
514    /// A materialized expression, plus its namespace path while it is a
515    /// plain dotted path (a `Variable`, or a property chain over one) —
516    /// maintained incrementally so a long `a.b.c...` chain costs amortized
517    /// O(1) per segment instead of re-walking and re-`format!`ing the
518    /// whole chain per dot. `None` once any non-path postfix form
519    /// (subscript, map projection, function call) has been applied.
520    Built(Expr, Option<String>),
521    /// A call-bound dot-chain accumulated as a bare path string. Entered
522    /// only under the scan's ends-in-`(` verdict, so mid-chain the token
523    /// after each `.ident` is always `.` or `(`, and the chain's
524    /// terminating `(` arm — which builds the `FunctionCall` name from
525    /// this path — is the only way out.
526    NsPath(String),
527}
528
529impl<'a> Parser<'a> {
530    /// Builds a parser over `source` under one explicit dialect: the
531    /// constructor tokenizes the source itself via
532    /// [`tokenize_with_options`], so the token stream and the
533    /// [`crate::lexer::ParseOptions`] that lexed it are one fact, never two
534    /// independently supplied arguments that could disagree. Every entry
535    /// point (`parse_with_options`, `parse_expression_str_with_options`,
536    /// `parse_graph_type_body`) passes its options here -- the ungated floor
537    /// entry points pass [`crate::lexer::ParseOptions::default`] explicitly,
538    /// and `parse_with_options` forwards the caller's preview gates -- so a
539    /// `Parser` can never exist half-configured.
540    ///
541    /// The constructor is the parser's only tokenizing site, so the
542    /// ADR-0257 admission cap ([`MAX_QUERY_BYTES`]) is structural here, not
543    /// a convention each entry point must remember to enforce: the first
544    /// statement checks `source.len()` *before* lexing, so adversarial
545    /// input cannot amplify into unbounded token allocations (LABS-81: 8
546    /// MiB of commas used to become over 520 MB of tokens). `subject` only
547    /// labels the input kind in the over-cap error message.
548    fn new(
549        source: &'a str,
550        subject: &str,
551        options: crate::lexer::ParseOptions,
552    ) -> Result<Self, ParseError> {
553        if source.len() > MAX_QUERY_BYTES {
554            return Err(ParseError::new(
555                format!(
556                    "{subject} of {} bytes exceeds the maximum query size of {MAX_QUERY_BYTES} bytes",
557                    source.len()
558                ),
559                1,
560                1,
561            ));
562        }
563        let tokens = tokenize_with_options(source, options);
564        Ok(Parser {
565            source,
566            line_starts: crate::token::line_starts_of(source),
567            tokens,
568            pos: 0,
569            side_effects: PatternSideEffectFlags::default(),
570            label_mix_target: LabelMixTarget::None,
571            in_when_branch_body: 0,
572            statement_depth: 0,
573            block_depth: 0,
574            expr_depth: 0,
575            clause_depth: 0,
576            comprehension_where_ambiguous_pipe: false,
577            comprehension_where_map_required: false,
578            exists_subquery_depth: 0,
579            pattern_comprehension_probe_memo: std::collections::HashMap::new(),
580            label_group_extent_memo: std::collections::HashMap::new(),
581            options,
582        })
583    }
584
585    // ---- Token access ----
586
587    /// The synthetic past-the-end EOF sentinel — the one spelling of the
588    /// token every out-of-range probe returns. `Token<'static>` covariantly
589    /// subtypes to any `Token<'a>`, so one shared empty-literal instance
590    /// serves every parse.
591    fn eof_token() -> &'static Token<'static> {
592        static EOF: std::sync::OnceLock<Token<'static>> = std::sync::OnceLock::new();
593        EOF.get_or_init(|| Token::new(TokenType::EOF, "", 0, 0))
594    }
595
596    fn peek(&self) -> &Token<'a> {
597        self.peek_at(0)
598    }
599
600    fn peek_type(&self) -> TokenType {
601        self.peek().ty
602    }
603
604    /// Looks ahead `offset` tokens past the current position (0 == `peek`)
605    /// without consuming anything.
606    fn peek_at(&self, offset: usize) -> &Token<'a> {
607        let idx = self.pos + offset;
608        if idx >= self.tokens.len() {
609            Self::eof_token()
610        } else {
611            &self.tokens[idx]
612        }
613    }
614
615    /// True if the current token is a case-insensitive identifier matching
616    /// `word` — the generic probe for the many contextual keywords that are
617    /// not reserved words in the lexer: type grammar words (`VALUE`,
618    /// `PROPERTY`, `MAP`) and schema/administration words (`DEFAULT`,
619    /// `KEY`, ...).
620    pub(super) fn peek_is_ident(&self, word: &str) -> bool {
621        self.peek_at_is_ident(0, word)
622    }
623
624    /// Like `peek_is_ident`, but `offset` tokens ahead (0 == `peek_is_ident`).
625    pub(super) fn peek_at_is_ident(&self, offset: usize, word: &str) -> bool {
626        Self::token_is_ident(self.peek_at(offset), word)
627    }
628
629    /// True if `tok` is a case-insensitive identifier matching `word` — the
630    /// token-level core of [`Self::peek_at_is_ident`], for call sites that
631    /// already hold the token.
632    pub(super) fn token_is_ident(tok: &Token, word: &str) -> bool {
633        tok.ty == TokenType::Identifier && tok.literal.eq_ignore_ascii_case(word)
634    }
635
636    /// True when the cursor is on the `ALL` set-quantifier spelling
637    /// (`count(ALL x)`, `collect(ALL x)`, `RETURN ALL`, `GROUP BY ALL`),
638    /// false for the `all(x IN list WHERE predicate)` list-predicate
639    /// function: `ALL` immediately followed by `(` is always the function,
640    /// the same priority the RETURN/WITH/GROUP-BY modifier readers apply.
641    /// The one spelling of that rule, shared by every set-quantifier site so
642    /// a nested `all(...)` inside an argument list cannot be swallowed as
643    /// the aggregate's quantifier.
644    pub(super) fn all_is_set_quantifier(&self) -> bool {
645        self.peek_type() == TokenType::ALL && self.peek_at(1).ty != TokenType::LeftParen
646    }
647
648    /// Consume and return the current token. The value is cloned out of the
649    /// stream because `backup`/`restore_pos` re-read tokens from
650    /// `self.tokens` after they have been consumed; with ADR-0505's borrowed
651    /// literals that clone is a pointer copy, not a heap allocation (only
652    /// the rare owned literal — an escaped string, a formatted error — pays
653    /// a String clone here).
654    fn next_token(&mut self) -> Token<'a> {
655        if self.pos >= self.tokens.len() {
656            Self::eof_token().clone()
657        } else {
658            let tok = self.tokens[self.pos].clone();
659            self.pos += 1;
660            tok
661        }
662    }
663
664    fn backup(&mut self) {
665        if self.pos > 0 {
666            self.pos -= 1;
667        }
668    }
669
670    fn save_pos(&self) -> usize {
671        self.pos
672    }
673
674    fn restore_pos(&mut self, pos: usize) {
675        self.pos = pos;
676    }
677
678    /// Extract a namespace string from an expression.
679    /// Returns Some("name") for Variable("name"), or Some("a.b") for nested property accesses
680    /// on variables that look like namespace paths.
681    fn extract_namespace(expr: &Expr) -> Option<String> {
682        match expr {
683            Expr::Variable(name) => Some(name.with_str(str::to_owned)),
684            Expr::Property(prop) => {
685                Self::extract_namespace(&prop.expr).map(|ns| format!("{}.{}", ns, prop.property))
686            }
687            _ => None,
688        }
689    }
690
691    fn expect(&mut self, ty: TokenType) -> ParseResult<Token<'a>> {
692        let tok = self.next_token();
693        if tok.ty != ty {
694            return Err(self.expected_token_error(ty, &tok));
695        }
696        Ok(tok)
697    }
698
699    /// The `expected <ty>, got <tok>` error at `tok`, shared by every
700    /// single-token expectation.
701    fn expected_token_error(&self, ty: TokenType, tok: &Token) -> ParseError {
702        self.error_at_token(
703            tok,
704            format!("expected {:?}, got {:?} ({:?})", ty, tok.literal, tok.ty),
705        )
706    }
707
708    /// Like [`Parser::expect`] but tags the raised error with a specific
709    /// openCypher-TCK error *detail* name. Used at grammar positions
710    /// where a mismatch has a more precise classification than the generic
711    /// `UnexpectedSyntax` — e.g. the closing `]` of a relationship pattern
712    /// (`InvalidRelationshipPattern`).
713    fn expect_detail(&mut self, ty: TokenType, detail: &'static str) -> ParseResult<Token<'a>> {
714        let tok = self.next_token();
715        if tok.ty != ty {
716            return Err(self.expected_token_error(ty, &tok).with_detail(detail));
717        }
718        Ok(tok)
719    }
720
721    fn error(&self, msg: impl Into<String>) -> ParseError {
722        let tok = self.peek();
723        self.error_at_token(tok, msg)
724    }
725
726    fn error_at_token(&self, tok: &Token, msg: impl Into<String>) -> ParseError {
727        let err = ParseError::new(msg, tok.line, tok.col).with_source(self.source);
728        // A lexer error token (malformed number/unicode literal) carries the
729        // specific openCypher-TCK error *detail* it should surface — propagate
730        // it so the raised parse error reports e.g. `InvalidNumberLiteral`
731        // instead of the generic `UnexpectedSyntax`. Non-error
732        // tokens carry no detail, so this is a no-op for the common case.
733        match tok.detail {
734            Some(detail) => err.with_detail(detail),
735            None => err,
736        }
737    }
738
739    /// A violated parser-internal invariant (e.g. the `parse_postfix`
740    /// namespace-call state machine reaching a state the memoized scan's
741    /// verdict rules out). The query engine's contract is typed errors,
742    /// never panics, so even a "cannot happen" state surfaces as a typed
743    /// parse error whose message marks it as an internal bug rather than a
744    /// user-syntax problem.
745    fn internal_error(&self, msg: impl Into<String>) -> ParseError {
746        self.error(format!("internal parser error: {}", msg.into()))
747    }
748
749    // ---- Top level ----
750
751    depth_guard_family! {
752        field = expr_depth,
753        enter = enter_expr_depth,
754        exit = exit_expr_depth,
755        with = with_expr_depth,
756        enter_doc = "ADR-0257: enter one level of expression nesting. \
757            Returns a typed error naming the limit once [`MAX_NESTING_DEPTH`] \
758            levels are already active, instead of recursing until the process \
759            aborts (LABS-69). On error the counter is left unchanged, so a \
760            speculative re-parse at a shallower position is not poisoned.",
761        exit_doc = "Pairs with [`Parser::enter_expr_depth`]; must run on \
762            every exit path (including error propagation) so \
763            backtracking/speculative parses keep the counter balanced.",
764        with_doc = "Runs `f` one expression-nesting level deep: the only \
765            sanctioned way to guard a recursive expression-shaped parse with \
766            `expr_depth`. The enter/exit pair is balanced by construction -- \
767            `f`'s result (including error propagation) is captured, the \
768            counter is decremented, and only then is the result returned, so \
769            no `?` can ever sit between enter and exit.",
770    }
771
772    depth_guard_family! {
773        field = clause_depth,
774        enter = enter_clause_depth,
775        exit = exit_clause_depth,
776        with = with_clause_depth,
777        enter_doc = "ADR-0257: enter one level of clause nesting. Returns a \
778            typed error naming the limit once [`MAX_NESTING_DEPTH`] levels \
779            are already active, instead of recursing until the process aborts \
780            (LABS-69: nested FOREACH bodies recurse through `parse_clause` \
781            without passing through `parse_statement`). On error the counter \
782            is left unchanged, so a speculative re-parse at a shallower \
783            position is not poisoned.",
784        exit_doc = "Pairs with [`Parser::enter_clause_depth`]; must run on \
785            every exit path (including error propagation) so sequential \
786            clauses in one statement/FOREACH body do not accumulate.",
787        with_doc = "[`Parser::with_expr_depth`] for `clause_depth`.",
788    }
789
790    depth_guard_family! {
791        field = statement_depth,
792        enter = enter_statement_depth,
793        exit = exit_statement_depth,
794        with = with_statement_depth,
795        enter_doc = "ADR-0257: enter one level of statement nesting. Returns \
796            a typed error naming the limit once [`MAX_NESTING_DEPTH`] levels \
797            are already active, instead of recursing until the process aborts \
798            (LABS-69). On error the counter is left unchanged, so a \
799            speculative re-parse at a shallower position is not poisoned.",
800        exit_doc = "Pairs with [`Parser::enter_statement_depth`]; must run on \
801            every exit path (including error propagation) so \
802            backtracking/speculative parses keep the counter balanced.",
803        with_doc = "[`Parser::with_expr_depth`] for `statement_depth`.",
804    }
805
806    depth_guard_family! {
807        field = block_depth,
808        enter = enter_block_depth,
809        exit = exit_block_depth,
810        with = with_block_depth,
811        enter_doc = "ADR-0257: enter one level of statement-block nesting. \
812            Returns a typed error naming the limit once \
813            [`MAX_NESTING_DEPTH`] levels are already active, instead of \
814            recursing until the process aborts (LABS-69: braced single \
815            queries and WHEN/ELSE bodies recurse through \
816            `parse_statement_block` without passing through \
817            `parse_statement`, `parse_clause`, or `parse_expression`). On \
818            error the counter is left unchanged, so a speculative re-parse \
819            at a shallower position is not poisoned.",
820        exit_doc = "Pairs with [`Parser::enter_block_depth`]; must run on \
821            every exit path (including error propagation) so sequential NEXT \
822            stages in one block and backtracking/speculative parses keep the \
823            counter balanced.",
824        with_doc = "[`Parser::with_expr_depth`] for `block_depth`.",
825    }
826
827    /// Parses an `Integer` token as a `u32` bound (relationship hop count,
828    /// path quantifier bound, number of paths/groups) via the checked
829    /// [`parse_int_literal`] path. Literals that don't fit are a typed parse
830    /// error naming the bound -- never a silent clamp (LABS-81:
831    /// `[*99999999999..2]` used to parse as `min_hops = 1`).
832    fn parse_u32_bound(&self, tok: &Token, what: &str) -> ParseResult<u32> {
833        // Both failures render through the one integer-literal error path,
834        // naming the bound.
835        let site = IntLiteralSite::Bounded {
836            what,
837            max: u64::from(u32::MAX),
838        };
839        let value = parse_int_literal(&tok.literal)
840            .map_err(|error| self.int_literal_error(tok, error, site))?;
841        u32::try_from(value)
842            .map_err(|_| self.int_literal_error(tok, IntLiteralError::Overflow, site))
843    }
844}
845
846mod case;
847mod clauses;
848mod definitions;
849mod expressions;
850mod interp;
851mod is_predicate;
852mod labels;
853mod literals;
854mod names;
855mod patterns;
856
857pub use patterns::selector_is_selective;
858mod schema;
859mod search;
860mod show;
861mod statement;
862mod types;
863
864#[cfg(test)]
865mod tests;
866
867/// True if any element of a quantified path pattern's operand is itself
868/// quantified -- directly (`PatternElement::Quantified`) or via a
869/// variable-length/quantified relationship (`RelPattern` with hop bounds,
870/// whether legacy `*min..max` or the CIP-28 postfix form) -- which CIP-28
871/// forbids (no nested quantification).
872fn contains_quantification(elements: &[PatternElement]) -> bool {
873    elements.iter().any(|e| match e {
874        PatternElement::Quantified(_) => true,
875        PatternElement::Relationship(rp) => rp.is_variable_length(),
876        PatternElement::Node(_) => false,
877    })
878}
879
880/// True if `elements` contains a *GPM-syntax* quantification -- a
881/// quantified path pattern (`((...))+`) or a CIP-28 Form-5 postfix-quantified
882/// relationship (`-->+`, `-[]->{1,5}`) -- but *not* the legacy bracket
883/// variable-length form (`-[*1..5]->`), which remains legal inside
884/// `shortestPath(...)`/`allShortestPaths(...)` (CIP-40 path-selector-mixing
885/// scenario 7). Used to reject `QuantifiedPathPatternInShortestPath`
886/// (scenario 6).
887fn contains_gpm_quantification(elements: &[PatternElement]) -> bool {
888    elements.iter().any(|e| match e {
889        PatternElement::Quantified(_) => true,
890        PatternElement::Relationship(rp) => rp.quantified,
891        PatternElement::Node(_) => false,
892    })
893}
894
895fn comparison_op(ty: TokenType) -> Option<&'static str> {
896    match ty {
897        TokenType::Equals => Some(EQUALS),
898        TokenType::NotEquals => Some("<>"),
899        TokenType::LessThan => Some("<"),
900        TokenType::GreaterThan => Some(">"),
901        TokenType::LessEqual => Some("<="),
902        TokenType::GreaterEqual => Some(">="),
903        TokenType::RegexMatch => Some("=~"),
904        _ => None,
905    }
906}
907
908/// The AST's one spelling table for operator text (ADR-0505 §2): the `op`
909/// fields of `BinaryExpr`, `UnaryExpr` and `StringMatchExpr` are
910/// `&'static str` drawn from these constants, so every producer consults
911/// the table and no spelling is re-spelled at a build site. The comparison
912/// family's spellings live in the `comparison_op` token-to-spelling table
913/// above — its own one table, consumed by every comparison build site —
914/// with one exception: the equality spelling is a named constant below,
915/// because simple-CASE's plain-value default (`parse_when_operand_element`)
916/// builds the same comparison without a token to read the table from.
917const EQUALS: &str = "=";
918const OR: &str = "OR";
919const XOR: &str = "XOR";
920const AND: &str = "AND";
921const NOT: &str = "NOT";
922/// `+`, shared by the unary and binary producers.
923const PLUS: &str = "+";
924/// `-`, shared by the unary and binary producers.
925const MINUS: &str = "-";
926const CONCAT: &str = "||";
927const MUL: &str = "*";
928const DIV: &str = "/";
929const MOD: &str = "%";
930const POW: &str = "^";
931const STARTS_WITH: &str = "STARTS WITH";
932const ENDS_WITH: &str = "ENDS WITH";
933const CONTAINS: &str = "CONTAINS";
934
935// Test-only probe for the CIP-272 map-comprehension lookahead: counts the
936// speculative full parses entered for a `{` in expression position. A brace
937// with no top-level `|` must never reach that parse (the exponential
938// parse-time regression), so the regression test asserts on this count rather
939// than on wall-clock time. Thread-local: the test harness runs every test on
940// its own thread.
941#[cfg(test)]
942std::thread_local! {
943    static SPECULATIVE_COMPREHENSION_PARSES: std::cell::Cell<usize> =
944        const { std::cell::Cell::new(0) };
945}