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}