relate_parser/parser/mod.rs
1use crate::ast::*;
2use crate::error::{ParseError, ParseResult};
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.
8pub(crate) use literals::parse_int_literal;
9use literals::{IntLiteralError, IntLiteralSite};
10
11/// `parse_constraint_for_target_ext`'s result: the `FOR <pattern>` target of
12/// a `CREATE CONSTRAINT`.
13struct ConstraintForTarget {
14 entity_type: SchemaEntityType,
15 /// The flat label/relationship-type list (empty for a label-less
16 /// target).
17 labels: Vec<SmallName>,
18 /// The FOR pattern's own variable, `""` when it has none (the shape
19 /// `CreateConstraintClause::variable` stores).
20 variable: SmallName,
21 /// A relationship pattern's source endpoint alias (CIP-177); `None`
22 /// for a node target or an alias-less endpoint.
23 source_alias: Option<SmallName>,
24 /// A relationship pattern's target endpoint alias, like `source_alias`.
25 target_alias: Option<SmallName>,
26}
27
28/// `parse_graph_type_constraint_verb`'s return shape: the constraint kind,
29/// the parsed `<value type>` for a `PropertyType` kind, and the `OPTIONS`
30/// tail.
31struct GraphTypeConstraintVerbSpec {
32 kind: GraphTypeConstraintVerb,
33 /// The `<value type>` of a `PropertyType` kind, `None` otherwise.
34 property_type: Option<TypeExpr>,
35 options: OptionsForm,
36}
37
38/// ADR-0257: maximum size of a Cypher query text accepted by [`parse`], in
39/// bytes (4 MiB). Enforced *before lexing* so that adversarial inputs cannot
40/// amplify into unbounded token allocations (LABS-81: 8 MiB of commas used to
41/// become >=520 MB of tokens). Every query path -- the Rust API, the C ABI,
42/// the CLI, the TCK, and Bolt -- funnels through the parser's entry points,
43/// each of which constructs through `Parser::new`, the one site the cap is
44/// enforced, so this single check covers them all.
45pub const MAX_QUERY_BYTES: usize = 4 * 1024 * 1024; // 4 MiB = 4 194 304
46
47/// ADR-0257: maximum nesting depth accepted while parsing. Enforced on
48/// expression nesting (every nested expression -- parenthesized constructs,
49/// list/map literals, function-call arguments, subqueries, ... -- descends
50/// through [`Parser::parse_expression`]; `NOT` chains recurse through
51/// [`Parser::parse_not`]) and on statement nesting (subquery bodies).
52/// Recursive-descent parsing beyond this depth risks a stack-overflow abort,
53/// which -- when the engine is embedded via the C ABI -- kills the host
54/// process instead of surfacing a recoverable error (LABS-69). The front-end
55/// lowering boundary enforces the same limit on its own walkers.
56pub const MAX_NESTING_DEPTH: u32 = 500;
57
58/// ADR-0116 ยง2: the [`ParseError::detail`] tag on a parse failure for a
59/// recognized-but-unsupported database administration command (everything
60/// outside CE's supported set on Relate's fixed namespaces). The
61/// error's `message` carries the verbatim statement text (without a leading
62/// `CYPHER n` preamble), so `relate-front` can raise CE's
63/// `UnsupportedAdministrationCommand` (51N27) echoing it. The tag name
64/// matches `ErrorKind::UnsupportedAdministrationCommand` in
65/// `relate-error`, so even an unmapped parse error keeps the right TCK
66/// kind/class.
67pub const UNSUPPORTED_ADMINISTRATION_DETAIL: &str = "UnsupportedAdministrationCommand";
68
69/// The [`ParseError::detail`] tag naming the undefined-variable condition
70/// (Neo4j 42N62): every parser site that rejects an unbound name carries it,
71/// so `EngineError::kind()` surfaces `UndefinedVariable` instead of the
72/// generic `UnexpectedSyntax` fallback. The tag name matches
73/// `ErrorKind::UndefinedVariable` in `relate-error`.
74pub const UNDEFINED_VARIABLE_DETAIL: &str = "UndefinedVariable";
75
76/// Parse a Cypher query string into a Statement AST.
77pub fn parse(input: &str) -> ParseResult<Statement> {
78 parse_with_options(input, crate::lexer::ParseOptions::default())
79}
80
81/// Parse a Cypher query string into a Statement AST under
82/// parse-affecting preview opt-ins ([`crate::lexer::ParseOptions`]: the
83/// ADR-0371 gate set the caller's store resolved from
84/// `RELATE_PREVIEW`, threaded here by `relate-front`'s preview
85/// admission). [`crate::lexer::ParseOptions::default`] is the dialect
86/// floor: every option widens acceptance of a form the floor rejects,
87/// never narrows it, so the ungated [`parse`] is exactly
88/// `parse_with_options` with all options off. The ADR-0257 size cap rides
89/// the constructor (`Parser::new`'s first statement), the parser's one
90/// tokenizing site -- not this entry point.
91pub fn parse_with_options(
92 input: &str,
93 options: crate::lexer::ParseOptions,
94) -> ParseResult<Statement> {
95 let mut parser = Parser::new(input, "query text", options)?;
96 parser.parse()
97}
98
99/// Parse a bare value expression under explicit parse-affecting preview
100/// opt-ins ([`crate::lexer::ParseOptions`]). Used for CIP-261 interpolation
101/// embeds: the `{...}` body of an interpolated string literal is a full
102/// expression, sub-parsed by [`parse_interp_body`] with the options of the
103/// parse that lexed the enclosing statement, so an embed observes the
104/// caller's dialect gates instead of silently re-parsing under the floor.
105/// `pub(crate)`: its only callers are in this crate (the public floor
106/// wrapper [`parse_expression_str`] and the embed sub-parse); it is
107/// promoted to `pub` -- with a root re-export beside
108/// [`parse`]/[`parse_with_options`] -- when a second crate needs gated
109/// expression parsing. The ADR-0257 size cap rides the constructor
110/// (`Parser::new`'s first statement), the parser's one tokenizing site --
111/// not this entry point.
112pub(crate) fn parse_expression_str_with_options(
113 input: &str,
114 options: crate::lexer::ParseOptions,
115) -> ParseResult<Expr> {
116 let mut parser = Parser::new(input, "expression text", options)?;
117 let expr = parser.parse_expression()?;
118 if parser.peek().ty != TokenType::EOF {
119 return Err(parser
120 .error_at_token(parser.peek(), "unexpected trailing input in expression")
121 .with_detail("UnexpectedSyntax"));
122 }
123 Ok(expr)
124}
125
126/// Parse a bare value expression on the dialect floor
127/// ([`crate::lexer::ParseOptions::default`]) -- the public wrapper for
128/// callers with no preview gates to thread; gated callers (and the
129/// interpolation-embed sub-parse) use `parse_expression_str_with_options`.
130pub fn parse_expression_str(input: &str) -> ParseResult<Expr> {
131 parse_expression_str_with_options(input, crate::lexer::ParseOptions::default())
132}
133
134// TODO(CIP-261): an interpolated literal is scanned three times -- once by
135// the lexer (`Lexer::read_interpolation`), once here to split text from
136// `{...}` embeds, and once more when each embed is re-tokenized by
137// `parse_expression_str_with_options`. Having the lexer emit real tokens for
138// the body (an
139// open/expression/close triple) would collapse this to a single scan; that
140// reshape of the token stream is deferred, not done in this change.
141/// Split a CIP-261 interpolation body (the [`TokenType::InterpString`]
142/// payload) into text and expression parts. `\{`/`\}` are escaped literal
143/// braces; a top-level `{` starts an expression segment that runs to its
144/// matching `}` (nesting, inner strings and backtick-quoted identifiers
145/// respected), sub-parsed with [`parse_expression_str_with_options`] under
146/// the caller's [`crate::lexer::ParseOptions`], so an embed inherits the
147/// dialect gates of the parse that lexed the enclosing statement.
148///
149/// The lexer leaves every escape unresolved in the payload, so literal-text
150/// escapes are decoded here -- after the two-byte lookahead that tells `\\`
151/// (an escaped backslash) apart from `\{` (an escaped literal brace).
152fn parse_interp_body(
153 body: &str,
154 options: crate::lexer::ParseOptions,
155) -> Result<Vec<crate::ast::InterpPart>, String> {
156 use crate::ast::InterpPart;
157
158 let chars: Vec<char> = body.chars().collect();
159 let mut parts: Vec<InterpPart> = Vec::new();
160 let mut text = String::new();
161 let mut i = 0;
162 while i < chars.len() {
163 let c = chars[i];
164 if c == '\\' && i + 1 < chars.len() {
165 i += push_interp_escape(&mut text, &chars, i)?;
166 continue;
167 }
168 if c != '{' {
169 text.push(c);
170 i += 1;
171 continue;
172 }
173 // Expression segment: find the matching close brace.
174 let mut depth = 1usize;
175 let mut inner_quote: Option<char> = None;
176 let mut in_backtick = false;
177 let mut j = i + 1;
178 while j < chars.len() {
179 let d = chars[j];
180 if let Some(q) = inner_quote {
181 if d == '\\' {
182 j += 2;
183 continue;
184 }
185 if d == q {
186 inner_quote = None;
187 }
188 } else if in_backtick {
189 // Inside `...` everything -- braces and quotes included -- is
190 // an inert identifier name.
191 if d == '`' {
192 in_backtick = false;
193 }
194 } else {
195 match d {
196 '\\' => j += 1,
197 '`' => in_backtick = true,
198 '{' | '[' | '(' => depth += 1,
199 '}' | ']' | ')' => {
200 // A closer with nothing open -- e.g. the `)` in
201 // `{)}` -- is malformed. Guard the decrement so
202 // `depth` can never underflow on hostile input.
203 if depth == 0 {
204 break;
205 }
206 depth -= 1;
207 // Only the outer `}` reaching depth 0 ends it.
208 if d == '}' && depth == 0 {
209 break;
210 }
211 }
212 '\'' | '"' => inner_quote = Some(d),
213 _ => {}
214 }
215 }
216 j += 1;
217 }
218 if depth != 0 {
219 return Err("unterminated { expression } in interpolated string".into());
220 }
221 let expr_src: String = chars[i + 1..j].iter().collect();
222 let expr = parse_expression_str_with_options(&expr_src, options)
223 .map_err(|e| format!("invalid expression in interpolated string: {e}"))?;
224 if !text.is_empty() {
225 parts.push(InterpPart::Text(std::mem::take(&mut text)));
226 }
227 parts.push(InterpPart::Interp(Box::new(expr)));
228 i = j + 1;
229 }
230 if !text.is_empty() {
231 parts.push(InterpPart::Text(text));
232 }
233 Ok(parts)
234}
235
236/// Decode one escape in a CIP-261 literal-text segment, appending the decoded
237/// text to `text` and returning how many chars were consumed (`chars[i]` is
238/// the `\`). The lexer leaves escapes unresolved so a later scanner cannot
239/// confuse a resolved `\\` with the start of `\{`; this is where they resolve
240/// again. `\{`/`\}` become the literal brace, known escapes decode, and an
241/// unknown escape keeps its two-character form.
242fn push_interp_escape(text: &mut String, chars: &[char], i: usize) -> Result<usize, String> {
243 let next = chars[i + 1]; // caller guarantees `i + 1 < chars.len()`
244 match next {
245 '\\' => {
246 text.push('\\');
247 Ok(2)
248 }
249 '{' => {
250 text.push('{');
251 Ok(2)
252 }
253 '}' => {
254 text.push('}');
255 Ok(2)
256 }
257 'n' => {
258 text.push('\n');
259 Ok(2)
260 }
261 't' => {
262 text.push('\t');
263 Ok(2)
264 }
265 '\'' => {
266 text.push('\'');
267 Ok(2)
268 }
269 '"' => {
270 text.push('"');
271 Ok(2)
272 }
273 'u' => {
274 if i + 6 > chars.len() {
275 return Err("invalid unicode escape sequence".into());
276 }
277 let hex: String = chars[i + 2..i + 6].iter().collect();
278 match u32::from_str_radix(&hex, 16) {
279 Ok(cp) => {
280 // A UTF-16 surrogate pair escape (`๐`) is one
281 // supplementary code point, same as in a plain string
282 // literal (see the lexer's `surrogate_pair_codepoint`).
283 if let Some(pair) = interp_surrogate_pair(cp, chars, i) {
284 text.push(pair.0);
285 return Ok(pair.1);
286 }
287 if let Some(ch) = char::from_u32(cp) {
288 text.push(ch);
289 }
290 Ok(6)
291 }
292 Err(_) => Err(format!("invalid unicode escape sequence: \\u{hex}")),
293 }
294 }
295 other => {
296 text.push('\\');
297 text.push(other);
298 Ok(2)
299 }
300 }
301}
302
303/// Decode a high-surrogate escape at `chars[i..]` (the `\`) together with an
304/// immediately following low-surrogate escape, returning the combined
305/// supplementary code point and the 12 chars the pair occupies.
306fn interp_surrogate_pair(cp: u32, chars: &[char], i: usize) -> Option<(char, usize)> {
307 if !(0xD800..=0xDBFF).contains(&cp) || i + 12 > chars.len() {
308 return None;
309 }
310 if chars[i + 6] != '\\' || chars[i + 7] != 'u' {
311 return None;
312 }
313 let hex: String = chars[i + 8..i + 12].iter().collect();
314 let lo = u32::from_str_radix(&hex, 16).ok()?;
315 if !(0xDC00..=0xDFFF).contains(&lo) {
316 return None;
317 }
318 char::from_u32(0x10000 + ((cp - 0xD800) << 10) + (lo - 0xDC00)).map(|ch| (ch, 12))
319}
320
321/// Parse a bare `<graph type specification body>` -- the `{ ... }` grammar
322/// shared by `CREATE GRAPH TYPE`/`ALTER CURRENT GRAPH TYPE`, without the
323/// surrounding statement (`canonical` is wrapped in braces here, so callers
324/// pass the CIP-180 canonical form's comma-joined contents, no braces of
325/// their own). Used by `relate-executor`'s `Graph` to reconstruct a
326/// persisted `current_graph_type` model from the snapshot manifest on load
327/// -- see `Graph::restore_graph_type_spec`. The ADR-0257 size cap rides the
328/// constructor (`Parser::new`'s first statement) and checks the wrapped
329/// string -- the exact text this entry point lexes.
330pub fn parse_graph_type_body(canonical: &str) -> ParseResult<GraphTypeBody> {
331 let wrapped = format!("{{{canonical}}}");
332 let mut parser = Parser::new(
333 &wrapped,
334 "graph type body",
335 crate::lexer::ParseOptions::default(),
336 )?;
337 let (open, body) = parser.parse_graph_type_spec_body()?;
338 parser.reject_bare_constraint_drops(&open, &body)?;
339 Ok(body)
340}
341
342/// CIP-150: the parsed statement preamble (`Parser::parse_preamble`) --
343/// `EXPLAIN`/`PROFILE` flags plus the effective `CYPHER <version>`, if any
344/// was given. Distinct option `key=value` pairs are validated for
345/// recognized keys, constrained value vocabularies
346/// ([`CYPHER_OPTION_VALUES`]), and internal consistency while parsing, but
347/// their values aren't retained past that check -- Relate has no
348/// runtime concept of `runtime=`/`planner=` etc. to act on, so only the
349/// fact that they parsed and didn't conflict matters.
350struct Preamble {
351 version: Option<u32>,
352 explain: bool,
353 profile: bool,
354}
355
356/// CIP-150: the pre-parser option keys Relate recognizes after a
357/// `CYPHER [<version>]` clause (besides the version itself). These mirror
358/// Neo4j's own pre-parser option vocabulary; Relate validates that a
359/// key is recognized and internally consistent but -- since it implements
360/// only one query-execution engine/runtime -- doesn't act on any of their
361/// values.
362const CYPHER_OPTION_KEYS: &[&str] = &[
363 "planner",
364 "runtime",
365 "updatestrategy",
366 "expressionengine",
367 "replan",
368 "connectcomponentsplanner",
369 "debug",
370 "operatorengine",
371];
372
373/// CIP-150 / Neo4j 2026.10: the pre-parser option keys whose *values*
374/// carry a constrained vocabulary, with each key's valid values -- the
375/// value-side twin of [`CYPHER_OPTION_KEYS`]' 22N07 key check. The one
376/// key with a vocabulary today is `runtime`, mirroring the three runtimes
377/// of Neo4j's current line (slotted, pipelined, parallel; the CIP-150
378/// corpus's accepted `runtime=slotted` examples pin the Cypher-5 side of
379/// that set). Relate implements a single engine, so every listed
380/// value is accepted-and-ignored; any other value fails with an authored
381/// 22N10 error naming the valid set.
382const CYPHER_OPTION_VALUES: &[(&str, &[&str])] =
383 &[("runtime", &["slotted", "pipelined", "parallel"])];
384
385/// The recursive-descent parser over a borrowed token stream. `'a` is the
386/// input query text's lifetime: the [`Token`] literals and [`Self::source`]
387/// borrow it (ADR-0505), and the parser โ built and dropped inside the
388/// parse entry points โ never outlives it. The AST it produces stays
389/// `'static` (owned strings).
390struct Parser<'a> {
391 source: &'a str,
392 tokens: Vec<Token<'a>>,
393 pos: usize,
394 /// Byte offset of the first byte of each 1-based source line
395 /// (`line_starts[0] == 0` is line 1's start). Precomputed once per parse
396 /// so `token_byte_offset` is O(1) instead of rescanning the whole source
397 /// per projection item. The lexer counts columns in *bytes* (see
398 /// `Lexer::advance`), so a token's byte offset is exactly
399 /// `line_starts[line - 1] + col - 1` โ this also fixes the old
400 /// char-counted scan, which mismatched the lexer's byte-counted columns
401 /// (and returned `None`) as soon as any non-ASCII char preceded the
402 /// token.
403 line_starts: Vec<usize>,
404 /// The clause-level pattern side-effect flags (label/quantifier mixing
405 /// state); see [`PatternSideEffectFlags`]. One field so a speculative
406 /// parse can snapshot/restore it by plain assignment.
407 side_effects: PatternSideEffectFlags,
408 /// Nesting depth of `parse_when_query` branch/ELSE bodies currently
409 /// being parsed -- 0 outside any such body. While positive, a bare
410 /// (non-brace) body's own clause loop (`parse_statement`) must stop at
411 /// a following `WHEN` too, not just `ELSE`/EOF/etc, so control returns
412 /// to `parse_when_query`'s own loop to see the next branch (CIP-213
413 /// `next_conditional_interactions.feature` PE3.1: `WHEN a THEN RETURN
414 /// x WHEN b THEN RETURN y ELSE RETURN z`, no braces anywhere). Scoped
415 /// to *this* mechanism only -- a bare `WHEN` appearing after an
416 /// ordinary clause outside any WHEN-body context (e.g. `MATCH (n)
417 /// WHEN ...`) must remain a hard parse error (CIP-135
418 /// syntax_placement.feature [8]/[9]), so this must stay zero there.
419 in_when_branch_body: u32,
420 /// Nesting depth of `parse_statement` calls -- 0 outside any statement,
421 /// 1 while parsing the outermost statement, 2+ while parsing a nested
422 /// `EXISTS {}`/`COUNT {}`/`CALL {}` subquery's own statement body. Used
423 /// to scope the label-expression mixing flags to one top-level
424 /// statement; see `parse_statement`'s doc comment. Also capped at
425 /// [`MAX_NESTING_DEPTH`] (ADR-0257) so deeply nested subquery bodies
426 /// cannot overflow the stack via pure statement recursion.
427 statement_depth: u32,
428 /// Current statement-block nesting depth (ADR-0257): incremented on
429 /// entering `parse_statement_block`, decremented on exit. Every
430 /// statement-nesting cycle funnels through `parse_statement_block` --
431 /// CALL/EXISTS/COUNT/COLLECT subquery bodies, brace-enclosed nested
432 /// procedure specifications (`{ { ... } }`), and WHEN/ELSE bodies
433 /// (`WHEN ... THEN { WHEN ... }`) -- including the cycles that bypass
434 /// `parse_statement`, `parse_clause`, and `parse_expression` and so
435 /// never engage any other counter (LABS-69: ~3000 nested braces used
436 /// to SIGABRT on an 8 MiB release stack). Unlike `statement_depth`,
437 /// this counter is *not* consulted for label-mixing scoping, so a
438 /// top-level `{ ... }` body incrementing it cannot flip
439 /// `is_outer_clause`. Capped at [`MAX_NESTING_DEPTH`].
440 block_depth: u32,
441 /// Current expression nesting depth (ADR-0257): incremented on entering
442 /// `parse_expression` and on each recursive `parse_not` step, decremented
443 /// on exit. Every nested expression -- parenthesized constructs, list
444 /// literals, map literals, function-call arguments, CASE operands,
445 /// comprehension bodies, subquery WHERE/RETURN expressions -- descends
446 /// through `parse_expression`, so this one counter bounds all expression
447 /// recursion. Also counts recursion cycles that bypass
448 /// `parse_expression` but are expression-shaped: unary `-`/`!` chains,
449 /// nested label/subpath parens, and nested `LIST<...>`/`ANY<...>`
450 /// value-type brackets (see `parse_value_type`). Capped at
451 /// [`MAX_NESTING_DEPTH`] (LABS-69).
452 expr_depth: u32,
453 /// Current clause nesting depth (ADR-0257): incremented on entering
454 /// `parse_clause`, decremented on exit. Both callers of `parse_clause`
455 /// (`parse_statement`'s body loop and `parse_foreach`'s body loop) are
456 /// loops, so the counter returns to baseline after every clause and
457 /// only grows with *true* clause nesting. That nesting exists: nested
458 /// FOREACH bodies recurse `parse_clause` -> `parse_clause_inner` ->
459 /// `parse_foreach` -> `parse_clause`, bypassing `parse_statement`, so
460 /// the `statement_depth` cap never engages on that cycle (LABS-69).
461 /// Capped at [`MAX_NESTING_DEPTH`].
462 clause_depth: u32,
463 /// True while parsing the `WHERE`-part expression of a list/pattern
464 /// comprehension. There, a bare `|` is genuinely ambiguous: it could
465 /// continue a label-expression disjunction (`x:A|B`) or be the
466 /// comprehension's own map-expression separator (`WHERE x:A | expr]`).
467 /// `parse_label_or` consults this flag to check, before committing to
468 /// the disjunction reading, whether doing so would strand a
469 /// well-formed label chain in front of tokens that can't follow one
470 /// (e.g. `.` for property access) -- see `label_or_pipe_is_ambiguous`,
471 /// which answers the question with a pure token-level scan.
472 comprehension_where_ambiguous_pipe: bool,
473 /// Whether the comprehension being parsed *requires* a map expression
474 /// after its `|` separator (a pattern comprehension always does, a list
475 /// comprehension need not). A `]` right after the scanned label chain
476 /// then proves that `|` was the separator, not a label disjunction --
477 /// see `label_or_pipe_is_ambiguous`.
478 comprehension_where_map_required: bool,
479 /// Depth of `EXISTS { โฆ }` bodies currently being parsed. An unbounded
480 /// quantified path pattern under REPEATABLE ELEMENTS is safe inside an
481 /// existence probe (the probe stops at the first row) and is accepted
482 /// there, while a top-level match still rejects it (42N53).
483 exists_subquery_depth: u32,
484 /// Memo of `pattern_comprehension_follows_equals` verdicts, keyed by
485 /// the token position of the `=` the probe starts at. The parse is
486 /// deterministic and the probe restores the token position and every
487 /// side-effect flag before returning, so the verdict depends only on
488 /// that position -- and a `true` verdict is always re-parsed for real
489 /// by the caller, which re-enforces the nesting-depth caps. Without
490 /// the memo, each level of a nested `[v = (n {p: ...}) | ...]` shape
491 /// probes *and* re-parses the whole nested term, giving 2^k parse
492 /// cost (LABS-183: ~0.7 s release at k=20, doubling per level); with
493 /// it each position is probed once and the shape is O(k^2) overall.
494 pattern_comprehension_probe_memo: std::collections::HashMap<usize, bool>,
495 /// Memo of `scan_label_primary_extent`'s group-case extents, keyed by
496 /// the opener's absolute token index and the scan's nesting depth. The
497 /// scan is a pure function of `self.tokens` (fixed for the parse) and
498 /// that depth -- `dynamic_label_quantifier_at(pos - self.pos)` reads
499 /// `tokens[self.pos + (pos - self.pos)]` == `tokens[pos]`, so `self.pos`
500 /// cancels out, and scan positions always stay at or past `self.pos` --
501 /// so a cached entry always equals a fresh scan. Without it each level
502 /// of a nested wide label disjunction re-walks its whole child subtree
503 /// (O(width * depth^2), ~31 s on a slow Windows debug runner); with it
504 /// every group extent is computed once (O(tokens)).
505 label_group_extent_memo: std::collections::HashMap<(usize, u32), Option<usize>>,
506 /// The parse-affecting preview opt-ins for this parse (see
507 /// [`crate::lexer::ParseOptions`]). Set once by `Parser::new` from the
508 /// entry point's options; never mutated mid-parse, so nested and
509 /// speculative parses all observe one dialect.
510 options: crate::lexer::ParseOptions,
511 /// Which label-mixing accumulator the clause being parsed feeds (see
512 /// [`LabelMixTarget`]). Saved and restored around each clause so a
513 /// nested subquery body's clauses choose their own side.
514 label_mix_target: LabelMixTarget,
515}
516
517/// The clause-level side-effect flags a pattern parse can set. Kept as one
518/// `Copy` field on `Parser` (`Parser::side_effects`) so a speculative
519/// `parse_pattern_path` probe snapshots and restores them by plain
520/// assignment (see `pattern_comprehension_follows_equals`), and the
521/// clause-start reset is a single `Default::default()` (plus the two
522/// quantifier flags' per-clause reset for nested clauses).
523#[derive(Default, Clone, Copy)]
524struct PatternSideEffectFlags {
525 /// The label-mixing forms seen in the clause currently being parsed.
526 /// `parse_insert` reads this for its own clause-local rejection (a
527 /// `:A:B` chain is never allowed in INSERT); it is reset at the start of
528 /// every clause, nested or not.
529 clause_labels: LabelMixFlags,
530 /// The label-mixing forms seen by the read clauses accumulated in the
531 /// current scope. Neo4j keeps the read side (MATCH/WITH/RETURN label
532 /// predicates) and the write side (CREATE/INSERT; MERGE counts as both)
533 /// apart: inside one `CALL { โฆ }` body `MATCH (n:A:B)` followed by
534 /// `CREATE (m IS B)` is legal, while two MATCHes (or a MERGE and a
535 /// CREATE) mixing the forms are not. See `PatternSideEffectFlags::read_labels`.
536 read_labels: LabelMixFlags,
537 /// The write side of the split described on [`Self::read_labels`].
538 write_labels: LabelMixFlags,
539 /// True if the ONE label/type expression currently being parsed saw a
540 /// colon-conjunction (`:A:B`), and
541 /// [`Self::label_expr_saw_gql_symbol`] the GQL symbol case. Reset at
542 /// the entry of `parse_label_expr_body`; `mixed-label-syntax` admits
543 /// mixing across separate label expressions of one clause, but Neo4j
544 /// keeps it illegal *within* one expression
545 /// (GpmSyntaxMixingAllowedAcceptance "Mixing : conjunction with
546 /// GPM-only label/type expression operators": `(n:A|B:C)`).
547 label_expr_saw_legacy_conjunction: bool,
548 /// See [`Self::label_expr_saw_legacy_conjunction`].
549 label_expr_saw_gql_symbol: bool,
550 /// True if a parenthesized label-expression group (`(A:B)`, `(A&B)`,
551 /// ...) was parsed anywhere in the clause currently being parsed.
552 /// CIP-114: CREATE/MERGE/MATCH allow this grouping, but INSERT does
553 /// not -- `parse_insert` checks this flag after parsing its pattern,
554 /// same reset/scoping as [`Self::clause_labels`].
555 label_saw_paren_group: bool,
556 /// True if a legacy bracket-syntax variable-length quantifier
557 /// (`[*min..max]`, including a bare `[*]`) was parsed anywhere in the
558 /// clause currently being parsed. Neo4j rejects mixing this pre-GPM
559 /// quantifier syntax with a GPM postfix/QPP quantifier (`->+`, `->*`,
560 /// `->{m,n}`, `((...)...){m,n}`) *within the same clause* -- but not
561 /// across separate clauses/statements (CIP-40 quantifier-mixing.feature
562 /// scenario 9 vs scenario 10), checked in `parse_clause`.
563 quantifier_saw_legacy_bracket: bool,
564 /// True if a GPM postfix or QPP quantifier was parsed anywhere in the
565 /// clause currently being parsed. See `quantifier_saw_legacy_bracket`.
566 quantifier_saw_gpm_form: bool,
567 /// Quantifier forms seen inside pattern comprehensions of the clause
568 /// currently being parsed (accumulated across all of its
569 /// comprehensions). A comprehension's inner pattern is its own pattern
570 /// context: its quantifier forms never combine with the clause's own
571 /// (a legacy `[:R*1..2]` inside a comprehension nested in a quantified
572 /// path pattern's WHERE is legal, Neo4j
573 /// QuantifiedPathPatternAcceptance "Pattern comprehension containing a
574 /// variable-length relationship inside a QPP is allowed"), but two
575 /// comprehensions in the same clause still combine with each other
576 /// (CIP-40 label-expression-mixing.feature scenario 13,
577 /// quantifier-mixing.feature scenario 10) -- so these are separate
578 /// accumulators, checked separately from the clause-level pair in
579 /// `parse_clause_at_current_depth`.
580 quantifier_comprehension_saw_legacy_bracket: bool,
581 /// See `quantifier_comprehension_saw_legacy_bracket`.
582 quantifier_comprehension_saw_gpm_form: bool,
583}
584
585/// The three label-expression forms whose mixing Neo4j rejects within one
586/// clause (CIP-14/CIP-40).
587#[derive(Default, Clone, Copy)]
588struct LabelMixFlags {
589 /// A legacy multi-label colon-conjunction (`:A:B`).
590 legacy_conjunction: bool,
591 /// A GQL label-expression symbol (`&`, `!`, `%`, a grouping paren, or
592 /// `|` on a node).
593 gql_symbol: bool,
594 /// A pattern-position `IS` label/type introducer (`(n IS A)`,
595 /// `-[IS R]->`), even without any GQL symbol beside it.
596 is_introducer: bool,
597}
598
599impl LabelMixFlags {
600 /// The rejection this set of forms triggers, if any. The GQL-symbol rule
601 /// is reported before the `IS` rule, matching the reference engine's
602 /// 42I10-before-42I29 precedence.
603 fn mixing(&self) -> Option<&'static str> {
604 if self.legacy_conjunction && self.gql_symbol {
605 return Some(
606 "InvalidLabelExpression: mixing label expression symbols (|, &, !, and %) with colon (:) between labels is not allowed",
607 );
608 }
609 if self.legacy_conjunction && self.is_introducer {
610 return Some(
611 "MixedIsAndColonConjunction: cannot mix the IS introducer with colon-conjunction within the same clause",
612 );
613 }
614 None
615 }
616}
617
618/// Which accumulator(s) the label forms of the clause being parsed feed.
619/// Neo4j keeps read clauses and write clauses apart when combining the forms
620/// across the clauses of one subquery scope; MERGE is both, and a label
621/// specification written by SET/REMOVE never joins either side.
622#[derive(Clone, Copy, Default, PartialEq, Eq)]
623enum LabelMixTarget {
624 #[default]
625 None,
626 Read,
627 Write,
628 Both,
629}
630
631/// A single postfix accessor (`.prop` or CIP-131's `[<expr>]`) parsed after
632/// a SET/REMOVE target's base expression by `Parser::parse_property_target_accessors`.
633enum PropertyTargetAccessor {
634 Static(SmallName),
635 Dynamic(Expr),
636}
637
638/// Generates the `enter_*_depth` / `exit_*_depth` / `with_*_depth` triple
639/// for one depth-guard counter field (ADR-0257, LABS-69). The four
640/// families (`expr_depth`, `clause_depth`, `statement_depth`,
641/// `block_depth`) share one mechanically identical shape; generating them
642/// from a single definition keeps the balanced-enter/exit property true by
643/// construction: `enter` leaves the counter unchanged on error, `exit` is
644/// a saturating decrement, and `with` captures `f`'s result (including
645/// error propagation), decrements, and only then returns, so no `?` can
646/// ever sit between enter and exit. The limit check and error message are
647/// byte-identical across families.
648macro_rules! depth_guard_family {
649 (
650 field = $field:ident,
651 enter = $enter:ident,
652 exit = $exit:ident,
653 with = $with:ident,
654 enter_doc = $enter_doc:expr,
655 exit_doc = $exit_doc:expr,
656 with_doc = $with_doc:expr $(,)?
657 ) => {
658 #[doc = $enter_doc]
659 fn $enter(&mut self) -> ParseResult<()> {
660 if self.$field >= MAX_NESTING_DEPTH {
661 return Err(self.error(format!(
662 "maximum nesting depth of {MAX_NESTING_DEPTH} exceeded"
663 )));
664 }
665 self.$field += 1;
666 Ok(())
667 }
668
669 #[doc = $exit_doc]
670 fn $exit(&mut self) {
671 self.$field = self.$field.saturating_sub(1);
672 }
673
674 #[doc = $with_doc]
675 fn $with<T>(&mut self, f: impl FnOnce(&mut Self) -> ParseResult<T>) -> ParseResult<T> {
676 self.$enter()?;
677 let result = f(self);
678 self.$exit();
679 result
680 }
681 };
682}
683
684/// The running base of [`Parser::parse_postfix`]'s postfix chain, making
685/// the namespace-call accumulation invariant structural instead of
686/// comment-held.
687///
688/// While a dot-chain the memoized `scan_dot_chain_for_call` classified as
689/// ending in `(` is being accumulated, the base is [`PostfixBase::NsPath`]
690/// โ a bare namespace-path string with *no* `Expr` โ so no postfix arm can
691/// observe or rebuild a stale intermediate expression (materializing one
692/// per segment cost ฮ(nยฒ) in string clones, a parse-time DoS on maximal
693/// inputs). Everywhere else the base is [`PostfixBase::Built`].
694enum PostfixBase {
695 /// A materialized expression, plus its namespace path while it is a
696 /// plain dotted path (a `Variable`, or a property chain over one) โ
697 /// maintained incrementally so a long `a.b.c...` chain costs amortized
698 /// O(1) per segment instead of re-walking and re-`format!`ing the
699 /// whole chain per dot. `None` once any non-path postfix form
700 /// (subscript, map projection, function call) has been applied.
701 Built(Expr, Option<String>),
702 /// A call-bound dot-chain accumulated as a bare path string. Entered
703 /// only under the scan's ends-in-`(` verdict, so mid-chain the token
704 /// after each `.ident` is always `.` or `(`, and the chain's
705 /// terminating `(` arm โ which builds the `FunctionCall` name from
706 /// this path โ is the only way out.
707 NsPath(String),
708}
709
710impl<'a> Parser<'a> {
711 /// Builds a parser over `source` under one explicit dialect: the
712 /// constructor tokenizes the source itself via
713 /// [`tokenize_with_options`], so the token stream and the
714 /// [`crate::lexer::ParseOptions`] that lexed it are one fact, never two
715 /// independently supplied arguments that could disagree. Every entry
716 /// point (`parse_with_options`, `parse_expression_str_with_options`,
717 /// `parse_graph_type_body`) passes its options here -- the ungated floor
718 /// entry points pass [`crate::lexer::ParseOptions::default`] explicitly,
719 /// and `parse_with_options` forwards the caller's preview gates -- so a
720 /// `Parser` can never exist half-configured.
721 ///
722 /// The constructor is the parser's only tokenizing site, so the
723 /// ADR-0257 admission cap ([`MAX_QUERY_BYTES`]) is structural here, not
724 /// a convention each entry point must remember to enforce: the first
725 /// statement checks `source.len()` *before* lexing, so adversarial
726 /// input cannot amplify into unbounded token allocations (LABS-81: 8
727 /// MiB of commas used to become over 520 MB of tokens). `subject` only
728 /// labels the input kind in the over-cap error message.
729 fn new(
730 source: &'a str,
731 subject: &str,
732 options: crate::lexer::ParseOptions,
733 ) -> Result<Self, ParseError> {
734 if source.len() > MAX_QUERY_BYTES {
735 return Err(ParseError::new(
736 format!(
737 "{subject} of {} bytes exceeds the maximum query size of {MAX_QUERY_BYTES} bytes",
738 source.len()
739 ),
740 1,
741 1,
742 ));
743 }
744 let tokens = tokenize_with_options(source, options);
745 Ok(Parser {
746 source,
747 line_starts: crate::token::line_starts_of(source),
748 tokens,
749 pos: 0,
750 side_effects: PatternSideEffectFlags::default(),
751 label_mix_target: LabelMixTarget::None,
752 in_when_branch_body: 0,
753 statement_depth: 0,
754 block_depth: 0,
755 expr_depth: 0,
756 clause_depth: 0,
757 comprehension_where_ambiguous_pipe: false,
758 comprehension_where_map_required: false,
759 exists_subquery_depth: 0,
760 pattern_comprehension_probe_memo: std::collections::HashMap::new(),
761 label_group_extent_memo: std::collections::HashMap::new(),
762 options,
763 })
764 }
765
766 // ---- Token access ----
767
768 /// The synthetic past-the-end EOF sentinel โ the one spelling of the
769 /// token every out-of-range probe returns. `Token<'static>` covariantly
770 /// subtypes to any `Token<'a>`, so one shared empty-literal instance
771 /// serves every parse.
772 fn eof_token() -> &'static Token<'static> {
773 static EOF: std::sync::OnceLock<Token<'static>> = std::sync::OnceLock::new();
774 EOF.get_or_init(|| Token::new(TokenType::EOF, "", 0, 0))
775 }
776
777 fn peek(&self) -> &Token<'a> {
778 self.peek_at(0)
779 }
780
781 fn peek_type(&self) -> TokenType {
782 self.peek().ty
783 }
784
785 /// Looks ahead `offset` tokens past the current position (0 == `peek`)
786 /// without consuming anything.
787 fn peek_at(&self, offset: usize) -> &Token<'a> {
788 let idx = self.pos + offset;
789 if idx >= self.tokens.len() {
790 Self::eof_token()
791 } else {
792 &self.tokens[idx]
793 }
794 }
795
796 /// True if the current token is a case-insensitive identifier matching
797 /// `word` โ the generic probe for the many contextual keywords that are
798 /// not reserved words in the lexer: type grammar words (`VALUE`,
799 /// `PROPERTY`, `MAP`) and schema/administration words (`DEFAULT`,
800 /// `KEY`, ...).
801 pub(super) fn peek_is_ident(&self, word: &str) -> bool {
802 self.peek_at_is_ident(0, word)
803 }
804
805 /// Like `peek_is_ident`, but `offset` tokens ahead (0 == `peek_is_ident`).
806 pub(super) fn peek_at_is_ident(&self, offset: usize, word: &str) -> bool {
807 Self::token_is_ident(self.peek_at(offset), word)
808 }
809
810 /// True if `tok` is a case-insensitive identifier matching `word` โ the
811 /// token-level core of [`Self::peek_at_is_ident`], for call sites that
812 /// already hold the token.
813 pub(super) fn token_is_ident(tok: &Token, word: &str) -> bool {
814 tok.ty == TokenType::Identifier && tok.literal.eq_ignore_ascii_case(word)
815 }
816
817 /// True when the cursor is on the `ALL` set-quantifier spelling
818 /// (`count(ALL x)`, `collect(ALL x)`, `RETURN ALL`, `GROUP BY ALL`),
819 /// false for the `all(x IN list WHERE predicate)` list-predicate
820 /// function: `ALL` immediately followed by `(` is always the function,
821 /// the same priority the RETURN/WITH/GROUP-BY modifier readers apply.
822 /// The one spelling of that rule, shared by every set-quantifier site so
823 /// a nested `all(...)` inside an argument list cannot be swallowed as
824 /// the aggregate's quantifier.
825 pub(super) fn all_is_set_quantifier(&self) -> bool {
826 self.peek_type() == TokenType::ALL && self.peek_at(1).ty != TokenType::LeftParen
827 }
828
829 /// Consume and return the current token. The value is cloned out of the
830 /// stream because `backup`/`restore_pos` re-read tokens from
831 /// `self.tokens` after they have been consumed; with ADR-0505's borrowed
832 /// literals that clone is a pointer copy, not a heap allocation (only
833 /// the rare owned literal โ an escaped string, a formatted error โ pays
834 /// a String clone here).
835 fn next_token(&mut self) -> Token<'a> {
836 if self.pos >= self.tokens.len() {
837 Self::eof_token().clone()
838 } else {
839 let tok = self.tokens[self.pos].clone();
840 self.pos += 1;
841 tok
842 }
843 }
844
845 fn backup(&mut self) {
846 if self.pos > 0 {
847 self.pos -= 1;
848 }
849 }
850
851 fn save_pos(&self) -> usize {
852 self.pos
853 }
854
855 fn restore_pos(&mut self, pos: usize) {
856 self.pos = pos;
857 }
858
859 /// Extract a namespace string from an expression.
860 /// Returns Some("name") for Variable("name"), or Some("a.b") for nested property accesses
861 /// on variables that look like namespace paths.
862 fn extract_namespace(expr: &Expr) -> Option<String> {
863 match expr {
864 Expr::Variable(name) => Some(name.with_str(str::to_owned)),
865 Expr::Property(prop) => {
866 Self::extract_namespace(&prop.expr).map(|ns| format!("{}.{}", ns, prop.property))
867 }
868 _ => None,
869 }
870 }
871
872 fn expect(&mut self, ty: TokenType) -> ParseResult<Token<'a>> {
873 let tok = self.next_token();
874 if tok.ty != ty {
875 return Err(self.error_at_token(
876 &tok,
877 format!("expected {:?}, got {:?} ({:?})", ty, tok.literal, tok.ty),
878 ));
879 }
880 Ok(tok)
881 }
882
883 /// Like [`Parser::expect`] but tags the raised error with a specific
884 /// openCypher-TCK error *detail* name. Used at grammar positions
885 /// where a mismatch has a more precise classification than the generic
886 /// `UnexpectedSyntax` โ e.g. the closing `]` of a relationship pattern
887 /// (`InvalidRelationshipPattern`).
888 fn expect_detail(&mut self, ty: TokenType, detail: &'static str) -> ParseResult<Token<'a>> {
889 let tok = self.next_token();
890 if tok.ty != ty {
891 return Err(self
892 .error_at_token(
893 &tok,
894 format!("expected {:?}, got {:?} ({:?})", ty, tok.literal, tok.ty),
895 )
896 .with_detail(detail));
897 }
898 Ok(tok)
899 }
900
901 fn error(&self, msg: impl Into<String>) -> ParseError {
902 let tok = self.peek();
903 self.error_at_token(tok, msg)
904 }
905
906 fn error_at_token(&self, tok: &Token, msg: impl Into<String>) -> ParseError {
907 let err = ParseError::new(msg, tok.line, tok.col).with_source(self.source);
908 // A lexer error token (malformed number/unicode literal) carries the
909 // specific openCypher-TCK error *detail* it should surface โ propagate
910 // it so the raised parse error reports e.g. `InvalidNumberLiteral`
911 // instead of the generic `UnexpectedSyntax`. Non-error
912 // tokens carry no detail, so this is a no-op for the common case.
913 match tok.detail {
914 Some(detail) => err.with_detail(detail),
915 None => err,
916 }
917 }
918
919 /// A violated parser-internal invariant (e.g. the `parse_postfix`
920 /// namespace-call state machine reaching a state the memoized scan's
921 /// verdict rules out). The query engine's contract is typed errors,
922 /// never panics, so even a "cannot happen" state surfaces as a typed
923 /// parse error whose message marks it as an internal bug rather than a
924 /// user-syntax problem.
925 fn internal_error(&self, msg: impl Into<String>) -> ParseError {
926 self.error(format!("internal parser error: {}", msg.into()))
927 }
928
929 // ---- Top level ----
930
931 depth_guard_family! {
932 field = expr_depth,
933 enter = enter_expr_depth,
934 exit = exit_expr_depth,
935 with = with_expr_depth,
936 enter_doc = "ADR-0257: enter one level of expression nesting. \
937 Returns a typed error naming the limit once [`MAX_NESTING_DEPTH`] \
938 levels are already active, instead of recursing until the process \
939 aborts (LABS-69). On error the counter is left unchanged, so a \
940 speculative re-parse at a shallower position is not poisoned.",
941 exit_doc = "Pairs with [`Parser::enter_expr_depth`]; must run on \
942 every exit path (including error propagation) so \
943 backtracking/speculative parses keep the counter balanced.",
944 with_doc = "Runs `f` one expression-nesting level deep: the only \
945 sanctioned way to guard a recursive expression-shaped parse with \
946 `expr_depth`. The enter/exit pair is balanced by construction -- \
947 `f`'s result (including error propagation) is captured, the \
948 counter is decremented, and only then is the result returned, so \
949 no `?` can ever sit between enter and exit.",
950 }
951
952 depth_guard_family! {
953 field = clause_depth,
954 enter = enter_clause_depth,
955 exit = exit_clause_depth,
956 with = with_clause_depth,
957 enter_doc = "ADR-0257: enter one level of clause nesting. Returns a \
958 typed error naming the limit once [`MAX_NESTING_DEPTH`] levels \
959 are already active, instead of recursing until the process aborts \
960 (LABS-69: nested FOREACH bodies recurse through `parse_clause` \
961 without passing through `parse_statement`). On error the counter \
962 is left unchanged, so a speculative re-parse at a shallower \
963 position is not poisoned.",
964 exit_doc = "Pairs with [`Parser::enter_clause_depth`]; must run on \
965 every exit path (including error propagation) so sequential \
966 clauses in one statement/FOREACH body do not accumulate.",
967 with_doc = "[`Parser::with_expr_depth`] for `clause_depth`.",
968 }
969
970 depth_guard_family! {
971 field = statement_depth,
972 enter = enter_statement_depth,
973 exit = exit_statement_depth,
974 with = with_statement_depth,
975 enter_doc = "ADR-0257: enter one level of statement nesting. Returns \
976 a typed error naming the limit once [`MAX_NESTING_DEPTH`] levels \
977 are already active, instead of recursing until the process aborts \
978 (LABS-69). On error the counter is left unchanged, so a \
979 speculative re-parse at a shallower position is not poisoned.",
980 exit_doc = "Pairs with [`Parser::enter_statement_depth`]; must run on \
981 every exit path (including error propagation) so \
982 backtracking/speculative parses keep the counter balanced.",
983 with_doc = "[`Parser::with_expr_depth`] for `statement_depth`.",
984 }
985
986 depth_guard_family! {
987 field = block_depth,
988 enter = enter_block_depth,
989 exit = exit_block_depth,
990 with = with_block_depth,
991 enter_doc = "ADR-0257: enter one level of statement-block nesting. \
992 Returns a typed error naming the limit once \
993 [`MAX_NESTING_DEPTH`] levels are already active, instead of \
994 recursing until the process aborts (LABS-69: braced single \
995 queries and WHEN/ELSE bodies recurse through \
996 `parse_statement_block` without passing through \
997 `parse_statement`, `parse_clause`, or `parse_expression`). On \
998 error the counter is left unchanged, so a speculative re-parse \
999 at a shallower position is not poisoned.",
1000 exit_doc = "Pairs with [`Parser::enter_block_depth`]; must run on \
1001 every exit path (including error propagation) so sequential NEXT \
1002 stages in one block and backtracking/speculative parses keep the \
1003 counter balanced.",
1004 with_doc = "[`Parser::with_expr_depth`] for `block_depth`.",
1005 }
1006
1007 /// Parses an `Integer` token as a `u32` bound (relationship hop count,
1008 /// path quantifier bound, number of paths/groups) via the checked
1009 /// [`parse_int_literal`] path. Literals that don't fit are a typed parse
1010 /// error naming the bound -- never a silent clamp (LABS-81:
1011 /// `[*99999999999..2]` used to parse as `min_hops = 1`).
1012 fn parse_u32_bound(&self, tok: &Token, what: &str) -> ParseResult<u32> {
1013 // Both failures render through the one integer-literal error path,
1014 // naming the bound.
1015 let site = IntLiteralSite::Bounded {
1016 what,
1017 max: u64::from(u32::MAX),
1018 };
1019 let value = parse_int_literal(&tok.literal)
1020 .map_err(|error| self.int_literal_error(tok, error, site))?;
1021 u32::try_from(value)
1022 .map_err(|_| self.int_literal_error(tok, IntLiteralError::Overflow, site))
1023 }
1024
1025 fn parse(&mut self) -> ParseResult<Statement> {
1026 let preamble = self.parse_preamble()?;
1027
1028 let mut stmt = self.parse_statement_block()?;
1029 stmt.explain = preamble.explain;
1030 stmt.profile = preamble.profile;
1031 stmt.cypher_version = preamble.version;
1032
1033 if self.peek_type() == TokenType::Semicolon {
1034 self.next_token();
1035 }
1036 // Any token left unconsumed here means `parse_regular_query`
1037 // returned without absorbing the rest of the input -- e.g. a bare
1038 // CIP-135 `<when query>` cannot be UNIONed (syntax_placement.feature
1039 // scenarios 16/17), and two brace-enclosed `<single query>`s
1040 // juxtaposed with no `UNION`/`NEXT` connector between them
1041 // (scenario 12/13) leave the second `{...}` sitting here. Every
1042 // other clause-loop path already consumes all the way to EOF on
1043 // its own (`parse_statement`'s loop keeps calling `parse_clause`
1044 // until it hits one of EOF/`;`/`UNION`/`}`, and any clause-shaped
1045 // leftover token already produces its own "unexpected token" error
1046 // there), so this is specifically the top-level backstop for the
1047 // brace-form `SingleQuery`/`<when query>` productions, which don't
1048 // loop.
1049 if self.peek_type() != TokenType::EOF {
1050 return Err(self.error(format!("unexpected token {:?}", self.peek().literal)));
1051 }
1052
1053 Ok(stmt)
1054 }
1055
1056 /// CIP-150: consumes the optional statement preamble at the very start
1057 /// of the query -- any interleaving of `EXPLAIN`/`PROFILE` (each at
1058 /// most once, mutually exclusive) with zero or more `CYPHER [<version>]
1059 /// [<key>=<value>]...` clauses. `CYPHER` is a non-reserved word --
1060 /// recognized by spelling on a plain `Identifier` token, like `SHOW`/
1061 /// `USE` elsewhere -- checked only here, once, at the true start of
1062 /// input, so it never shadows a variable named `cypher` appearing
1063 /// anywhere else in a query.
1064 ///
1065 /// Grammar (per the CIP): `<preamble> ::= <preamble option>...`,
1066 /// `<preamble option> ::= EXPLAIN | PROFILE | <cypher options>`,
1067 /// `<cypher options> ::= CYPHER [<cypher version>] <cypher option>...`.
1068 /// A fresh `CYPHER` keyword is required to open each options clause --
1069 /// once one ends (at the first token that isn't a recognized
1070 /// `<key>=<value>` pair), only another `CYPHER`/`EXPLAIN`/`PROFILE`
1071 /// token can continue the preamble; anything else (including a bare
1072 /// `key=value` with no preceding fresh `CYPHER`) falls through to
1073 /// ordinary statement parsing and is a generic syntax error there --
1074 /// this is what makes `CYPHER 5 EXPLAIN runtime=slotted RETURN 1`
1075 /// (doc example E1) a hard error: `EXPLAIN` ends the `CYPHER` clause,
1076 /// and `runtime=slotted` isn't a valid statement start.
1077 ///
1078 /// Two different `<cypher version>` values for the same statement (or
1079 /// two different values for the same non-version option key) are
1080 /// rejected as a conflicting pre-parser combination; the same value
1081 /// repeated is fine. An out-of-range or non-integer version number, or
1082 /// an unrecognized option key, is also rejected. Relate recognizes
1083 /// exactly the two versions Neo4j 2026.05 ships (`5`, `25`); either is
1084 /// accepted and recorded on the returned `Statement` for the engine to
1085 /// act on (see `Statement::cypher_version`) -- Relate otherwise
1086 /// implements a single dialect (the modern, GQL-aligned grammar this
1087 /// whole parser targets), so the two versions differ only where the
1088 /// engine explicitly checks `cypher_version` (the gates in
1089 /// `relate-front`'s `validate::dialect`, wired into lowering).
1090 fn parse_preamble(&mut self) -> ParseResult<Preamble> {
1091 let mut version: Option<u32> = None;
1092 let mut options: std::collections::HashMap<String, String> =
1093 std::collections::HashMap::new();
1094 let mut explain = false;
1095 let mut profile = false;
1096
1097 loop {
1098 match self.peek_type() {
1099 TokenType::EXPLAIN if !explain && !profile => {
1100 self.next_token();
1101 explain = true;
1102 }
1103 TokenType::PROFILE if !explain && !profile => {
1104 self.next_token();
1105 profile = true;
1106 }
1107 TokenType::Identifier if self.peek().literal.eq_ignore_ascii_case("cypher") => {
1108 self.next_token(); // consume CYPHER
1109
1110 // Optional `<cypher version> ::= <digit>...` -- only
1111 // attempted when the next token could plausibly be one
1112 // (an integer or decimal digit sequence); anything else
1113 // (an option key, EXPLAIN, EOF, ...) means no version
1114 // was given at all, per the grammar's `[<cypher
1115 // version>]`.
1116 if matches!(self.peek_type(), TokenType::Integer | TokenType::Float) {
1117 let tok = self.next_token();
1118 if tok.ty != TokenType::Integer
1119 || (tok.literal != "5" && tok.literal != "25")
1120 {
1121 return Err(self.error_at_token(
1122 &tok,
1123 format!(
1124 "SyntaxError: 22N10 invalid pre-parser option value: {:?} is not a valid cypher version",
1125 tok.literal
1126 ),
1127 ));
1128 }
1129 let v: u32 = tok.literal.parse().unwrap();
1130 match version {
1131 Some(existing) if existing != v => {
1132 return Err(self.error_at_token(
1133 &tok,
1134 "SyntaxError: 22N09 conflicting pre-parser combination: multiple values for 'cypher version'",
1135 ));
1136 }
1137 _ => version = Some(v),
1138 }
1139 }
1140
1141 // Zero or more `<cypher option key> = <cypher option
1142 // value>` pairs, each `<key>` a plain identifier
1143 // directly followed by `=`.
1144 while self.peek_type() == TokenType::Identifier
1145 && self.peek_at(1).ty == TokenType::Equals
1146 {
1147 let key_tok = self.next_token();
1148 self.next_token(); // consume =
1149 let value_tok = self.next_token();
1150 let key_lower = key_tok.literal.to_ascii_lowercase();
1151 if !CYPHER_OPTION_KEYS.contains(&key_lower.as_str()) {
1152 return Err(self.error_at_token(
1153 &key_tok,
1154 format!(
1155 "SyntaxError: 22N07 invalid pre-parser option key: {:?}",
1156 key_tok.literal
1157 ),
1158 ));
1159 }
1160 // Keys with a constrained value vocabulary
1161 // (`CYPHER_OPTION_VALUES`) validate their value
1162 // the same way -- an authored 22N10 error naming
1163 // the valid set, the value-side twin of the 22N07
1164 // key error above.
1165 if let Some((_, values)) = CYPHER_OPTION_VALUES
1166 .iter()
1167 .find(|(key, _)| *key == key_lower)
1168 {
1169 if !values.contains(&value_tok.literal.to_ascii_lowercase().as_str()) {
1170 return Err(self.error_at_token(
1171 &value_tok,
1172 format!(
1173 "SyntaxError: 22N10 invalid pre-parser option value: {:?} is not a valid {} value (valid values: {})",
1174 value_tok.literal,
1175 key_tok.literal,
1176 values.join(", ")
1177 ),
1178 ));
1179 }
1180 }
1181 match options.get(&key_lower) {
1182 Some(existing) if existing != &value_tok.literal => {
1183 return Err(self.error_at_token(
1184 &value_tok,
1185 format!(
1186 "SyntaxError: 22N09 conflicting pre-parser combination: multiple values for {:?}",
1187 key_tok.literal
1188 ),
1189 ));
1190 }
1191 _ => {
1192 options.insert(key_lower, value_tok.literal.into_owned());
1193 }
1194 }
1195 }
1196 }
1197 _ => break,
1198 }
1199 }
1200
1201 Ok(Preamble {
1202 version,
1203 explain,
1204 profile,
1205 })
1206 }
1207
1208 /// `<RegularQuery> ::= <SingleQuery> (UNION [ALL] <SingleQuery>)*` -- a
1209 /// single query optionally chained to further queries via UNION/UNION
1210 /// ALL. This is the top-level query grammar minus EXPLAIN/PROFILE (which
1211 /// only apply once, at the very start of a top-level query), so it is
1212 /// also the grammar every subquery body uses: `COUNT { ... }`,
1213 /// `EXISTS { ... }`, `COLLECT { ... }`, and `CALL { ... }` all embed a
1214 /// `<RegularQuery>` and must therefore accept a UNION chain between their
1215 /// braces, not just a single statement.
1216 ///
1217 /// CIP-146: each `<SingleQuery>` is now parsed via `parse_single_query`,
1218 /// which additionally accepts the brace-enclosed
1219 /// `[ USE <graph-expr> ] '{' <RegularQuery> '}'` form. Per the CIP's
1220 /// Semantics Step 3 (Unwrap), a brace-enclosed arm is transparent
1221 /// (Case 1) when it is the *sole* `SingleQuery` here (no `UNION`
1222 /// follows) -- its clauses/union chain are simply used as this
1223 /// `RegularQuery` directly, which is exactly what `parse_single_query`
1224 /// already returns. But once a `UNION` token *does* follow, every arm
1225 /// (including this first one) is now a `SingleQuery`-only/UNION-argument
1226 /// context (Case 2): an arm whose own brace body was itself composite
1227 /// (nested UNION) needs the `CALL (*) { BODY } RETURN *` / `... FINISH`
1228 /// rewrap (Case 2.2) via `maybe_wrap_composite_union_arm` so the outer
1229 /// union's dedup boundary lands exactly where the braces put it (see
1230 /// union-braces.feature scenario 7); a linear arm needs no rewrap since
1231 /// splicing it in directly is already observably identical.
1232 fn parse_regular_query(&mut self) -> ParseResult<Statement> {
1233 // CIP-135: `<regular query> ::= <union query> | <when query> |
1234 // <single query>` -- a `<when query>` (bare `WHEN ... THEN {...}
1235 // [WHEN ...]* [ELSE {...}]`) is a distinct top-level alternative,
1236 // not composable with UNION and not a `<single query>` (so it
1237 // can't appear as a UNION arm) unless explicitly wrapped in
1238 // top-level braces (`{ WHEN ... }`, which *is* a `<single query>`
1239 // per CIP-146 since its content is a full `<regular query>`).
1240 // Only checked here, at the very start of a `<regular query>` --
1241 // never inside `parse_clause_inner`, so a `WHEN` appearing after
1242 // an earlier clause in the same statement (e.g. `MATCH (n) WHEN
1243 // ...`) still falls through to that dispatch's catch-all
1244 // "unexpected token" error.
1245 if self.peek_type() == TokenType::WHEN {
1246 return self.parse_when_query();
1247 }
1248 let mut stmt = self.parse_single_query()?;
1249
1250 if self.peek_type() != TokenType::UNION {
1251 return Ok(stmt);
1252 }
1253 stmt = Self::maybe_wrap_composite_union_arm(stmt);
1254
1255 // UNION / UNION ALL / UNION DISTINCT (CIP-154: `DISTINCT` is an
1256 // optional synonym for plain UNION's set semantics -- mutually
1257 // exclusive with `ALL`, and represented identically to plain UNION
1258 // as `all: false`; mixing `UNION` with `UNION ALL` in one chain is
1259 // accepted, as in Neo4j).
1260 while self.peek_type() == TokenType::UNION {
1261 self.next_token();
1262 let all = if self.peek_type() == TokenType::ALL {
1263 self.next_token();
1264 true
1265 } else {
1266 if self.peek_type() == TokenType::DISTINCT {
1267 self.next_token();
1268 }
1269 false
1270 };
1271 let next_stmt = self.parse_single_query()?;
1272 let next_stmt = Self::maybe_wrap_composite_union_arm(next_stmt);
1273 // Attach to end of union chain
1274 let mut current = &mut stmt;
1275 while current.union.is_some() {
1276 current = &mut current.union.as_mut().unwrap().statement;
1277 }
1278 current.union = Some(Box::new(UnionPart {
1279 all,
1280 statement: next_stmt,
1281 }));
1282 }
1283
1284 Ok(stmt)
1285 }
1286
1287 /// True if the current token is the CIP-213 `NEXT` contextual keyword --
1288 /// a non-reserved word (per the CIP's own grammar), recognized by
1289 /// spelling on a plain `Identifier` token, the same technique already
1290 /// used for `SHOW`/`USE`/`LET`/`FILTER`/`FINISH`. Only ever checked at
1291 /// clause-list-loop boundaries (`parse_statement`'s stop condition) and
1292 /// at the top of `parse_statement_block`'s own loop -- never inside
1293 /// `parse_clause_inner` -- so `next` remains usable as an ordinary
1294 /// variable/label name everywhere else (e.g. `MATCH (next) RETURN
1295 /// next`).
1296 fn at_next_keyword(&self) -> bool {
1297 self.peek_type() == TokenType::Identifier
1298 && self.peek().literal.eq_ignore_ascii_case("next")
1299 }
1300
1301 /// CIP-213 `<statement block> ::= <statement> [<next statement>...]`,
1302 /// `<next statement> ::= NEXT <statement>`. Wraps `parse_regular_query`
1303 /// (a `<statement>`: a possibly-UNION'd `<composite statement>`, or a
1304 /// bare `<conditional statement>` i.e. a `<when query>`) with a
1305 /// trailing loop over `NEXT <statement>` stages, threading each stage
1306 /// onto the previous one's `.next` field. This is the production every
1307 /// "full regular query" call site now uses in place of a raw
1308 /// `parse_regular_query` call, so NEXT is parseable everywhere a
1309 /// `<RegularQuery>` embeds (top level, brace-enclosed nested procedure
1310 /// specifications, CALL subquery bodies, and EXISTS/COUNT/COLLECT
1311 /// subquery-expression bodies) -- matching every context the CIP's own
1312 /// examples chain NEXT through.
1313 ///
1314 /// ADR-0257: this is the single choke point through which EVERY
1315 /// statement-nesting cycle funnels -- CALL/EXISTS/COUNT/COLLECT
1316 /// subquery bodies, brace-enclosed nested procedure specifications
1317 /// (`parse_braced_single_query`), and WHEN/ELSE bodies
1318 /// (`parse_when_query` via `parse_single_query`). The braced/WHEN
1319 /// cycles recurse `parse_single_query` -> `parse_braced_single_query`
1320 /// -> here without passing through `parse_statement`, `parse_clause`,
1321 /// or `parse_expression`, so none of the other depth counters engages
1322 /// on them (LABS-69: ~3000 nested braces on a ~6 KB input used to
1323 /// SIGABRT on an 8 MiB release stack). Guarding here with the
1324 /// dedicated `block_depth` counter -- deliberately *not*
1325 /// `statement_depth`, which doubles as the `is_outer_clause`
1326 /// label-mixing signal and must not be inflated by a top-level
1327 /// `{ ... }` body -- bounds every cycle at the same one-increment-per-
1328 /// nesting-level rate.
1329 fn parse_statement_block(&mut self) -> ParseResult<Statement> {
1330 self.with_block_depth(Self::parse_statement_block_at_current_depth)
1331 }
1332
1333 fn parse_statement_block_at_current_depth(&mut self) -> ParseResult<Statement> {
1334 if self.at_next_keyword() {
1335 return Err(
1336 self.error("InvalidNextStatement: NEXT must follow a statement, not begin one")
1337 );
1338 }
1339 // Every "full regular query" embedding context (CALL/EXISTS/COUNT/
1340 // COLLECT bodies, brace-enclosed nested procedure specifications)
1341 // starts a *fresh* scope for `in_when_branch_body` -- that flag
1342 // only exists to let a bare (non-brace) WHEN/THEN body's own
1343 // clause loop stop at a sibling `WHEN`, and must not leak into an
1344 // unrelated nested body parsed while it happens to be set (e.g. a
1345 // `CALL { ... }` subquery embedded inside a bare THEN body, whose
1346 // own bare `MATCH (n) WHEN ...` must still be a hard error per
1347 // CIP-135, not silently treated as a statement-block boundary).
1348 let saved_in_when_branch_body = std::mem::take(&mut self.in_when_branch_body);
1349 // CIP-231: the optional `<definition block>` heads every
1350 // `<procedure specification>` -- top level and every braced nested
1351 // body (this is the one choke point all of them funnel through, so
1352 // definitions parse in exactly the grammar's positions and nowhere
1353 // else). Parsed before the statement proper; the resolver in the
1354 // front end rewrites definitions and their call sites away before
1355 // lowering.
1356 let definitions = self.parse_local_definitions()?;
1357 let result = self.parse_statement_block_inner();
1358 self.in_when_branch_body = saved_in_when_branch_body;
1359 let mut result = result?;
1360 // `extend`, not assign: a block that starts with its own DEFINE
1361 // statements can still parse into a braced inner body carrying
1362 // definitions of its own (`DEFINE ... { DEFINE ... ... }`); the
1363 // outer block's own (possibly empty) definitions come first in
1364 // declaration order, the inner body's after them.
1365 result.definitions.splice(0..0, definitions);
1366 Ok(result)
1367 }
1368
1369 fn parse_statement_block_inner(&mut self) -> ParseResult<Statement> {
1370 let mut stmt = self.parse_regular_query()?;
1371 // `stmt` may already carry its own `.next` chain -- e.g. a
1372 // brace-enclosed nested procedure specification
1373 // (`parse_braced_single_query`) whose own content is itself a
1374 // multi-stage NEXT chain (CIP-213 PE8.1). Find the *true* current
1375 // tail before appending anything more, so an outer NEXT here
1376 // extends that chain instead of clobbering it.
1377 let mut tail = &mut stmt;
1378 while tail.next.is_some() {
1379 tail = tail.next.as_mut().unwrap();
1380 }
1381 while self.at_next_keyword() {
1382 self.next_token(); // consume NEXT
1383 if self.at_next_keyword() {
1384 return Err(self.error(
1385 "InvalidNextStatement: NEXT cannot be immediately followed by another NEXT",
1386 ));
1387 }
1388 if matches!(
1389 self.peek_type(),
1390 TokenType::EOF | TokenType::Semicolon | TokenType::RightBrace | TokenType::UNION
1391 ) {
1392 return Err(
1393 self.error("InvalidNextStatement: NEXT must be followed by a statement")
1394 );
1395 }
1396 let next_stmt = self.parse_regular_query()?;
1397 tail.next = Some(Box::new(next_stmt));
1398 tail = tail.next.as_mut().unwrap();
1399 }
1400 Ok(stmt)
1401 }
1402
1403 /// CIP-146 Semantics Step 3, Case 2.2: rewrites a composite (nested-union)
1404 /// UNION argument `arm` -- which can only arise from a brace-enclosed
1405 /// body whose own content was itself a UNION chain -- into
1406 /// `CALL (*) { arm } RETURN *` (arm ends in a tabular RETURN) or
1407 /// `CALL (*) { arm } FINISH` (arm's result is omitted, e.g. every leaf
1408 /// arm is CREATE-only). A linear `arm` (`.union.is_none()`) is returned
1409 /// unchanged, since splicing it directly into the outer chain is already
1410 /// observably identical to wrapping it.
1411 ///
1412 /// CIP-213: also fires when `arm.next.is_some()` -- a brace-enclosed
1413 /// body whose own content is a NEXT chain (PE4.5/PE4.6). Without this,
1414 /// attaching a sibling UNION arm directly onto `arm` would leave `arm`
1415 /// carrying *both* `.union` (the sibling arm) and `.next` (arm's own
1416 /// internal continuation) on the same node, and `Engine::
1417 /// execute_statement_seeded` -- which always resolves `.union` before
1418 /// `.next` -- would then wrongly feed the *whole merged* union row set
1419 /// (both arms' rows) into `arm`'s own internal NEXT stage instead of
1420 /// just its own branch's rows. Wrapping `arm` (chain and all) inside an
1421 /// opaque `CALL (*) { ... }` first makes it a single self-contained,
1422 /// `.next`-free node before any sibling UNION arm is ever attached to
1423 /// it, so the two concepts never collide.
1424 fn maybe_wrap_composite_union_arm(arm: Statement) -> Statement {
1425 if arm.union.is_none() && arm.next.is_none() {
1426 return arm;
1427 }
1428 let mut tail = &arm;
1429 while let Some(next_stmt) = &tail.next {
1430 tail = next_stmt;
1431 }
1432 let tabular = tail.clauses.iter().any(|c| matches!(c, Clause::Return(_)));
1433 let trailer = if tabular {
1434 Clause::Return(ReturnClause {
1435 group_by: None,
1436 distinct: false,
1437 items: vec![ReturnItem {
1438 expr: Expr::Star,
1439 alias: None,
1440 all: true,
1441 source_text: None,
1442 }],
1443 order_by: Vec::new(),
1444 skip: None,
1445 limit: None,
1446 })
1447 } else {
1448 Clause::Finish
1449 };
1450 Statement {
1451 clauses: vec![
1452 Clause::CallSubquery(CallSubqueryClause {
1453 statement: arm,
1454 scope: CallScope::Wildcard,
1455 optional: false,
1456 in_transactions: None,
1457 }),
1458 trailer,
1459 ],
1460 union: None,
1461 explain: false,
1462 profile: false,
1463 next: None,
1464 cypher_version: None,
1465 brace_wrapped: false,
1466 definitions: Vec::new(),
1467 }
1468 }
1469
1470 /// `<SingleQuery> ::= <Statement> | [ USE <graph-expr> ] '{' <RegularQuery> '}'`
1471 /// (CIP-146). The plain form is unchanged pre-CIP-146 behavior
1472 /// (delegated to `parse_statement`); the brace form is new. Used
1473 /// everywhere a `SingleQuery` is expected: the first arm of a
1474 /// `RegularQuery`, every subsequent UNION/UNION ALL argument, and (since
1475 /// `CALL`/`CALL (...)` bodies are themselves a `RegularQuery`) the top
1476 /// level of a CALL subquery body -- exactly the "known to process one
1477 /// row" contexts the CIP restricts this syntax to. Deliberately *not*
1478 /// wired into `parse_clause_inner`, so brace syntax stays rejected mid-
1479 /// query (e.g. after WITH) and as a LOAD CSV argument body.
1480 fn parse_single_query(&mut self) -> ParseResult<Statement> {
1481 if self.peek_type() == TokenType::LeftBrace {
1482 return self.parse_braced_single_query(None);
1483 }
1484 if self.peek_type() == TokenType::Identifier
1485 && self.peek().literal.eq_ignore_ascii_case("use")
1486 {
1487 // Could be the new `USE <graph-expr> { ... }` brace-prefixed
1488 // SingleQuery, or an ordinary leading `USE` clause of a plain
1489 // statement (pre-CIP-146, e.g. `USE db RETURN 1`) -- parse the
1490 // USE clause (it already knows how to parse a graph expression)
1491 // and check what follows before committing.
1492 let save = self.save_pos();
1493 let use_clause = self.parse_use()?;
1494 if self.peek_type() == TokenType::LeftBrace {
1495 return self.parse_braced_single_query(Some(use_clause.graph_expr));
1496 }
1497 self.restore_pos(save);
1498 }
1499 self.parse_statement()
1500 }
1501
1502 /// Parses the body of a CIP-146 `[ USE <graph-expr> ] '{' <RegularQuery> '}'`
1503 /// SingleQuery; `use_prefix` is the already-parsed USE graph expression
1504 /// (if any) -- the leading `{` is the current token. Empty braces are a
1505 /// syntax error (grammar requires at least one SingleQuery inside).
1506 /// Nested braces (Semantics Step 1, Simplify) collapse for free via
1507 /// plain recursion into `parse_regular_query`, which itself dispatches
1508 /// back through `parse_single_query` for its own arms. A USE prefix is
1509 /// pushed (Semantics Step 2, Normalize) as the first clause of every arm
1510 /// of the resulting body -- linear body: just the one statement;
1511 /// composite body: every arm of its union chain.
1512 fn parse_braced_single_query(&mut self, use_prefix: Option<Expr>) -> ParseResult<Statement> {
1513 let brace_tok = self.next_token(); // consume {
1514 if self.peek_type() == TokenType::RightBrace {
1515 return Err(self.error_at_token(
1516 &brace_tok,
1517 "InvalidInput: empty braces `{ }` are not a valid query body",
1518 ));
1519 }
1520 let mut inner = self.parse_statement_block()?;
1521 self.expect(TokenType::RightBrace)?;
1522 inner.brace_wrapped = true;
1523
1524 if let Some(graph_expr) = use_prefix {
1525 let mut cur = &mut inner;
1526 loop {
1527 cur.clauses.insert(
1528 0,
1529 Clause::Use(UseClause {
1530 graph_expr: graph_expr.clone(),
1531 }),
1532 );
1533 if cur.union.is_some() {
1534 cur = &mut cur.union.as_mut().unwrap().statement;
1535 } else {
1536 break;
1537 }
1538 }
1539 }
1540
1541 Ok(inner)
1542 }
1543
1544 /// CIP-135: `<when query> ::= <when>, {<when>}, [<else>]`, where
1545 /// `<when> ::= "WHEN", <predicate>, "THEN", <single-query>` and
1546 /// `<else> ::= "ELSE", <single-query>`. Called from `parse_regular_query`
1547 /// once it has confirmed the current token is `WHEN`. Each branch body
1548 /// (and the optional ELSE body) is parsed via `parse_single_query`, so
1549 /// it may be a top-level-brace `{ ... }` body (the only form every
1550 /// scenario in this CIP's eval suite actually uses) or a bare
1551 /// single-/multi-part query per the grammar. Result is wrapped as the
1552 /// sole clause of a fresh `Statement` -- a `<when query>` never mixes
1553 /// with other clauses and (being a `<regular query>`-level alternative,
1554 /// not a `<single query>`) is deliberately not connected to a following
1555 /// `UNION` here; callers that need brace+UNION composition already get
1556 /// it for free via `parse_braced_single_query`'s recursive call into
1557 /// this same function.
1558 fn parse_when_query(&mut self) -> ParseResult<Statement> {
1559 let mut branches = Vec::new();
1560 loop {
1561 self.expect(TokenType::WHEN)?;
1562 let predicate = self.parse_expression()?;
1563 self.expect(TokenType::THEN)?;
1564 let body = self.parse_when_branch_body()?;
1565 branches.push(WhenBranch { predicate, body });
1566 if self.peek_type() != TokenType::WHEN {
1567 break;
1568 }
1569 }
1570 let else_body = if self.peek_type() == TokenType::ELSE {
1571 self.next_token();
1572 Some(self.parse_when_branch_body()?)
1573 } else {
1574 None
1575 };
1576 Ok(Statement {
1577 clauses: vec![Clause::Conditional(ConditionalClause {
1578 branches,
1579 else_body,
1580 })],
1581 ..Statement::default()
1582 })
1583 }
1584
1585 /// Parses one WHEN or ELSE branch body with `in_when_branch_body`
1586 /// raised, restoring it before any error propagates (same balanced
1587 /// shape as the `with_*_depth` helpers).
1588 fn parse_when_branch_body(&mut self) -> ParseResult<Statement> {
1589 self.in_when_branch_body += 1;
1590 let body = self.parse_single_query();
1591 self.in_when_branch_body -= 1;
1592 body
1593 }
1594
1595 fn parse_statement(&mut self) -> ParseResult<Statement> {
1596 // ADR-0257: pure statement recursion (`CALL { CALL { ... } }`,
1597 // `EXISTS { EXISTS { ... } }`) must hit the same hard nesting cap as
1598 // expression recursion instead of overflowing the stack (LABS-69).
1599 // Routed through the balanced helper so an error mid-body cannot
1600 // leave `statement_depth` inflated for a speculative re-parse.
1601 //
1602 // This counter does NOT engage on every statement-nesting cycle:
1603 // `parse_braced_single_query` and `parse_when_query` bodies recurse
1604 // `parse_single_query` -> `parse_braced_single_query` ->
1605 // `parse_statement_block` -> ... without passing through
1606 // `parse_statement` (or `parse_clause`/`parse_expression`). Those
1607 // cycles are now guarded by `block_depth` at `parse_statement_block`
1608 // -- the choke point every statement-nesting cycle funnels through.
1609 // The hard cap here is kept anyway, belt-and-braces: on any stack,
1610 // every active `parse_statement` frame sits inside a distinct
1611 // enclosing `parse_statement_block` frame (its only caller,
1612 // `parse_single_query`, is reached only via `parse_regular_query` /
1613 // `parse_when_query`, both of which run inside a block), so
1614 // `block_depth >= statement_depth` always holds and `block_depth`
1615 // provably trips at the same-or-earlier nesting depth on every
1616 // cycle this cap catches -- but keeping it costs nothing and
1617 // protects against a future caller path that bypasses
1618 // `parse_statement_block`. The counter itself is load-bearing
1619 // regardless of the cap: it is the `is_outer_clause` label-mixing
1620 // scoping signal (see `parse_clause`).
1621 self.with_statement_depth(Self::parse_statement_at_current_depth)
1622 }
1623
1624 fn parse_statement_at_current_depth(&mut self) -> ParseResult<Statement> {
1625 let mut stmt = Statement {
1626 clauses: Vec::new(),
1627 ..Statement::default()
1628 };
1629
1630 // See `parse_clause`'s doc comment for how label-expression mixing
1631 // is scoped relative to this statement-nesting depth.
1632 loop {
1633 match self.peek_type() {
1634 TokenType::EOF
1635 | TokenType::Semicolon
1636 | TokenType::UNION
1637 | TokenType::RightBrace
1638 // CIP-135: a bare (non-brace) WHEN/THEN body -- e.g.
1639 // `WHEN a = 1 THEN RETURN 2 AS a ELSE RETURN 3 AS a` --
1640 // must stop before the following `ELSE`, the same way a
1641 // brace already stops it, rather than trying to parse
1642 // `ELSE` as the start of a new clause. `WHEN` is
1643 // deliberately *not* added here (see `parse_regular_query`'s
1644 // doc comment): a bare `WHEN` appearing after an ordinary
1645 // clause must remain a hard parse error, not silently
1646 // become a new statement-block boundary.
1647 | TokenType::ELSE => {
1648 if self.peek_type() == TokenType::Semicolon {
1649 self.next_token();
1650 }
1651 break;
1652 }
1653 TokenType::WHEN if self.in_when_branch_body > 0 => break,
1654 // CIP-213: `NEXT` is a statement-block boundary, not a
1655 // clause -- stop the clause loop here so the enclosing
1656 // `parse_statement_block` can consume it. No real clause
1657 // ever starts with the bare word "next", so this can never
1658 // misfire mid-clause (see `at_next_keyword`'s doc comment).
1659 _ if self.at_next_keyword() => break,
1660 _ => {
1661 let clause = self.parse_clause()?;
1662 stmt.clauses.push(clause);
1663 }
1664 }
1665 }
1666
1667 self.check_label_set_mixing(&stmt.clauses)?;
1668 // CIP-123/CIP-242/CIP-253: composed SHOW/TERMINATE clauses (multiple
1669 // SHOW/TERMINATE commands chained together, or a single SHOW/
1670 // TERMINATE composed with other Cypher clauses) are now genuinely
1671 // supported -- each acts as a nested-loop cross join against the
1672 // rows produced so far, exactly like `SHOW FUNCTIONS`/`SHOW
1673 // PROCEDURES` already did before this feature landed (see
1674 // `crate::clause::show`). The structural rules that govern
1675 // composition (mandatory non-star YIELD, mandatory trailing RETURN,
1676 // no re-declaring an in-scope variable) are checked at the semantic
1677 // (post-parse) validation stage instead of here, in
1678 // `relate_front::validate::validate_show_composability` --
1679 // this parser only builds the AST.
1680
1681 Ok(stmt)
1682 }
1683
1684 /// CIP-126 Examples 5/6: within a single SET clause (or a single REMOVE
1685 /// clause), `IS` and a colon-conjunction (`:A:B`, i.e. more than one
1686 /// label in one item) cannot both be used across that one clause's
1687 /// label-set items -- single-label items of either syntax may freely
1688 /// coexist. Checked independently per clause (CIP-126
1689 /// `05-invalid-mixing.feature` never combines items across two
1690 /// different clauses; CIP-40 `dml-label-set-mixing.feature` scenario 14
1691 /// is `@neo4j-verified` legal for exactly that cross-clause shape: a
1692 /// SET clause using `IS` and a *separate* REMOVE clause using colon
1693 /// conjunction, both in the same statement).
1694 fn check_label_set_mixing(&self, clauses: &[Clause]) -> ParseResult<()> {
1695 for clause in clauses {
1696 let items: Vec<(bool, usize)> = match clause {
1697 Clause::Set(sc) => sc
1698 .items
1699 .iter()
1700 .filter(|i| !i.labels.is_empty())
1701 .map(|i| (i.is_keyword, i.labels.len()))
1702 .collect(),
1703 Clause::Remove(rc) => rc
1704 .items
1705 .iter()
1706 .filter(|i| !i.labels.is_empty())
1707 .map(|i| (i.is_keyword, i.labels.len()))
1708 .collect(),
1709 _ => continue,
1710 };
1711 let mut saw_is = false;
1712 let mut saw_colon_conjunction = false;
1713 for (is_keyword, len) in items {
1714 if is_keyword {
1715 saw_is = true;
1716 } else if len > 1 {
1717 saw_colon_conjunction = true;
1718 }
1719 }
1720 if saw_is && saw_colon_conjunction {
1721 return Err(self.error(
1722 "MixedIsAndColonConjunction: cannot mix IS and colon-conjunction across SET/REMOVE label items in the same clause",
1723 ));
1724 }
1725 }
1726 Ok(())
1727 }
1728}
1729
1730mod case;
1731mod clauses;
1732mod definitions;
1733mod expressions;
1734mod labels;
1735mod literals;
1736mod names;
1737mod patterns;
1738
1739pub use patterns::selector_is_selective;
1740mod schema;
1741mod search;
1742mod show;
1743mod types;
1744
1745#[cfg(test)]
1746mod tests;
1747
1748/// True if any element of a quantified path pattern's operand is itself
1749/// quantified -- directly (`PatternElement::Quantified`) or via a
1750/// variable-length/quantified relationship (`RelPattern` with hop bounds,
1751/// whether legacy `*min..max` or the CIP-28 postfix form) -- which CIP-28
1752/// Rule 4 forbids (no nested quantification).
1753fn contains_quantification(elements: &[PatternElement]) -> bool {
1754 elements.iter().any(|e| match e {
1755 PatternElement::Quantified(_) => true,
1756 PatternElement::Relationship(rp) => rp.is_variable_length(),
1757 PatternElement::Node(_) => false,
1758 })
1759}
1760
1761/// True if `elements` contains a *GPM-syntax* quantification -- a
1762/// quantified path pattern (`((...))+`) or a CIP-28 Form-5 postfix-quantified
1763/// relationship (`-->+`, `-[]->{1,5}`) -- but *not* the legacy bracket
1764/// variable-length form (`-[*1..5]->`), which remains legal inside
1765/// `shortestPath(...)`/`allShortestPaths(...)` (CIP-40 path-selector-mixing
1766/// scenario 7). Used to reject `QuantifiedPathPatternInShortestPath`
1767/// (scenario 6).
1768fn contains_gpm_quantification(elements: &[PatternElement]) -> bool {
1769 elements.iter().any(|e| match e {
1770 PatternElement::Quantified(_) => true,
1771 PatternElement::Relationship(rp) => rp.quantified,
1772 PatternElement::Node(_) => false,
1773 })
1774}
1775
1776fn comparison_op(ty: TokenType) -> Option<&'static str> {
1777 match ty {
1778 TokenType::Equals => Some(EQUALS),
1779 TokenType::NotEquals => Some("<>"),
1780 TokenType::LessThan => Some("<"),
1781 TokenType::GreaterThan => Some(">"),
1782 TokenType::LessEqual => Some("<="),
1783 TokenType::GreaterEqual => Some(">="),
1784 TokenType::RegexMatch => Some("=~"),
1785 _ => None,
1786 }
1787}
1788
1789/// The AST's one spelling table for operator text (ADR-0505 ยง2): the `op`
1790/// fields of `BinaryExpr`, `UnaryExpr` and `StringMatchExpr` are
1791/// `&'static str` drawn from these constants, so every producer consults
1792/// the table and no spelling is re-spelled at a build site. The comparison
1793/// family's spellings live in the `comparison_op` token-to-spelling table
1794/// above โ its own one table, consumed by every comparison build site โ
1795/// with one exception: the equality spelling is a named constant below,
1796/// because simple-CASE's plain-value default (`parse_when_operand_element`)
1797/// builds the same comparison without a token to read the table from.
1798const EQUALS: &str = "=";
1799const OR: &str = "OR";
1800const XOR: &str = "XOR";
1801const AND: &str = "AND";
1802const NOT: &str = "NOT";
1803/// `+`, shared by the unary and binary producers.
1804const PLUS: &str = "+";
1805/// `-`, shared by the unary and binary producers.
1806const MINUS: &str = "-";
1807const CONCAT: &str = "||";
1808const MUL: &str = "*";
1809const DIV: &str = "/";
1810const MOD: &str = "%";
1811const POW: &str = "^";
1812const STARTS_WITH: &str = "STARTS WITH";
1813const ENDS_WITH: &str = "ENDS WITH";
1814const CONTAINS: &str = "CONTAINS";
1815
1816// Test-only probe for the CIP-272 map-comprehension lookahead: counts the
1817// speculative full parses entered for a `{` in expression position. A brace
1818// with no top-level `|` must never reach that parse (the exponential
1819// parse-time regression), so the regression test asserts on this count rather
1820// than on wall-clock time. Thread-local: the test harness runs every test on
1821// its own thread.
1822#[cfg(test)]
1823std::thread_local! {
1824 static SPECULATIVE_COMPREHENSION_PARSES: std::cell::Cell<usize> =
1825 const { std::cell::Cell::new(0) };
1826}