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