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}