Skip to main content

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.min_hops.is_some() || rp.max_hops.is_some(),
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}