Skip to main content

relate_parser/
normalize.rs

1//! The statement normalizer (ADR-0503): one pass over the lexer's own
2//! token stream that derives a plan-cache template key, the rewritten
3//! statement text, and the extracted literal values — the enabler for
4//! template-keyed plan caching on workloads that emit literals instead of
5//! parameters.
6//!
7//! The three outputs of one walk, so they cannot drift:
8//!
9//! - **template** — the canonical key. Value-bearing literal tokens
10//!   (`Integer`, `Float`, `String`) become typed placeholders
11//!   `$__AUTO_INT_0__`/`$__AUTO_FLOAT_1__`/`$__AUTO_STR_2__` (the type is
12//!   part of the key, so `42` and `'42'` never share a template); a
13//!   bracket group of only such literals (recursively) collapses to one
14//!   `$__AUTO_LIST_n__` placeholder; identifiers render through the
15//!   canonical quoting policy ([`quote_identifier`]), parameters as
16//!   `$name`, and every other token — keywords included — as written.
17//!   Two statements share a template only if they parse identically.
18//!   Keyword case is deliberately NOT folded: the dialect keeps keyword
19//!   spellings as case-sensitive names (`(o:Order)`, `-[:ORDER]->`,
20//!   `n.match`, `{match: 1}`), and the token stream cannot prove a
21//!   keyword sits in a clause position rather than a name position — so
22//!   `match …` and `MATCH …` keep distinct templates (a miss, never a
23//!   wrong plan).
24//! - **rewritten** — the source with each normalized literal's byte span
25//!   replaced by its placeholder: a real Cypher statement whose literals
26//!   are parameters. Parsing it (with the extracted values bound as
27//!   `$__AUTO_*__` parameters, through the ordinary front-end entry) is
28//!   what a cache entry is built from, so any literal position whose
29//!   parameter form is ungrammatical fails that parse and the statement
30//!   simply stays uncached — an over-eager normalization costs a miss,
31//!   never a wrong plan.
32//! - **values** — the placeholder/value pairs in token order.
33//!
34//! Grammar guards skip normalization where a parameter is not grammatical
35//! or would change meaning (each costs only a cache miss): a `String`
36//! followed by `:` is a map-literal key; a `String` preceded by the
37//! contextual `FIELDTERMINATOR` identifier is a LOAD CSV field terminator;
38//! an `Integer`/`Float` preceded by `*` or `..` is a var-length quantifier
39//! bound; a `String` that is a function call's first argument feeds the
40//! front-end's constant folding (a temporal constructor's literal folds
41//! to a constant at lowering — a parameter there stays a per-row call).
42//! `CYPHER <version>` integers need no guard — the rewritten parse fails
43//! closed.
44//!
45//! Deliberately NOT done (the 2026-10-31 session's constraints, §7): no
46//! variable renaming (variable names are structural), no size threshold,
47//! no folding of non-clause keywords (`n.true` and `n.TRUE` are different
48//! property keys).
49
50use std::cell::Cell;
51
52use crate::lexer::{tokenize_with_options, ParseOptions};
53use crate::parser::{parse_int_literal, MAX_NESTING_DEPTH, MAX_QUERY_BYTES};
54use crate::token::{
55    is_field_terminator_word, line_starts_of, quote_identifier, token_start_byte, Token, TokenType,
56};
57
58/// The reserved prefix of every auto-parameter name. A statement whose
59/// token stream references a parameter with this prefix, or a caller whose
60/// parameter map carries a key with it, is [`NormalizeOutcome::NotCacheable`]
61/// — the caller can never collide with the engine's own names. An
62/// implementation detail of this module and the one helper below:
63/// `params_carry_reserved_prefix` is the public spelling of the policy.
64pub(crate) const AUTO_PARAM_PREFIX: &str = "__AUTO_";
65
66/// Whether a caller's parameter map carries any [`AUTO_PARAM_PREFIX`]-named
67/// key — the one spelling of the reserved-prefix collision policy, consulted
68/// at the one boundary that decides cache participation — the facade's
69/// `Connection::cache_lookup`, before the raw stage — where such a caller
70/// disables the cache for the statement entirely. Generic over the value
71/// type — the policy is about the names only.
72pub fn params_carry_reserved_prefix<V>(params: &std::collections::BTreeMap<String, V>) -> bool {
73    params
74        .keys()
75        .any(|name| name.starts_with(AUTO_PARAM_PREFIX))
76}
77
78/// One extracted literal value: the normalizer's own small vocabulary (the
79/// parser crate does not depend on the engine's value type). The facade
80/// converts these into parameter values at the one boundary where both
81/// exist.
82#[derive(Debug, Clone, PartialEq)]
83pub enum NormalizedValue {
84    Int(i64),
85    Float(f64),
86    Str(String),
87    List(Vec<NormalizedValue>),
88}
89
90/// What [`normalize_statement`] produced.
91#[derive(Debug, Clone, PartialEq)]
92pub enum NormalizeOutcome {
93    /// The template key, the rewritten statement, and the values, all of
94    /// one walk.
95    Normalized(Normalized),
96    /// The statement must not participate in the plan cache. Oversized
97    /// input, a lexer error token, an unparseable literal, a `$__AUTO_*`
98    /// name in the stream, or a list scan past its total step budget (an
99    /// adversarially nested payload — the parser's own guards are then
100    /// the statement's verdict). Never an error: the statement itself
101    /// parses and runs exactly as before.
102    NotCacheable,
103}
104
105/// The normalizer's outputs. See the [module documentation](self).
106#[derive(Debug, Clone, PartialEq)]
107pub struct Normalized {
108    /// The canonical template: two statements share it only if they parse
109    /// identically.
110    pub template: String,
111    /// The statement with normalized literals as `$__AUTO_*__`
112    /// parameters.
113    pub rewritten: String,
114    /// The `(placeholder, value)` pairs, in token order.
115    pub values: Vec<(String, NormalizedValue)>,
116    /// The original source spelling of each [`Self::values`] entry, in the
117    /// same order: the text the result column keeps (`RETURN 1` stays `1`).
118    pub spellings: Vec<String>,
119}
120
121/// Normalize `src` under the same [`ParseOptions`] the real parse would
122/// use (the preview gates change what the lexer produces, so the template
123/// must be derived from the identical token stream).
124pub fn normalize_statement(src: &str, options: ParseOptions) -> NormalizeOutcome {
125    // The same cap the parse enforces (ADR-0257), checked for the same
126    // reason: no adversarial amplification into unbounded token
127    // allocation. An oversized statement fails the parse anyway.
128    if src.len() > MAX_QUERY_BYTES {
129        return NormalizeOutcome::NotCacheable;
130    }
131    let tokens = tokenize_with_options(src, options);
132    let line_starts = line_starts_of(src);
133    let scan_budget = tokens.len() as u64 * 2 + SCAN_STEP_HEADROOM;
134    let mut pass = Pass {
135        src,
136        tokens: &tokens,
137        line_starts: &line_starts,
138        template: String::new(),
139        spans: Vec::new(),
140        values: Vec::new(),
141        spellings: Vec::new(),
142        next_index: 0,
143        call_argument: call_argument_context(&tokens),
144        scan_steps: Cell::new(0),
145        scan_budget,
146    };
147    match pass.run() {
148        Some(normalized) => NormalizeOutcome::Normalized(normalized),
149        None => NormalizeOutcome::NotCacheable,
150    }
151}
152
153/// The list scan's step-budget headroom over `2 × token count` — slack
154/// for the empty-group and single-element shapes whose scans touch a few
155/// tokens more than once.
156const SCAN_STEP_HEADROOM: u64 = 64;
157
158/// The one-pass state. `Option` returns are the not-cacheable bailouts,
159/// never errors: every guard's failure mode is a statement that stays
160/// uncached. The two lifetimes are the source's and the tokens' own
161/// (ADR-0505 borrowed them from it).
162struct Pass<'a, 't> {
163    src: &'a str,
164    tokens: &'t [Token<'a>],
165    line_starts: &'a [usize],
166    /// The template under construction: the rendered tokens joined with
167    /// single spaces.
168    template: String,
169    /// The rewritten text's replacements, in source order:
170    /// `(byte start, byte end, placeholder)` — the span runs from the
171    /// normalized token's (or group's) first byte to the next token's
172    /// first byte, so the inter-token whitespace rides out with the
173    /// literal.
174    spans: Vec<(usize, usize, String)>,
175    /// The extracted values in placeholder order.
176    values: Vec<(String, NormalizedValue)>,
177    /// Original source spellings, parallel to `values`.
178    spellings: Vec<String>,
179    /// The one counter every placeholder name derives from.
180    next_index: usize,
181    /// Whether each token sits inside a function call's argument list —
182    /// the innermost unmatched opener enclosing it is a `(` whose callee
183    /// identifier stands before it (a map or list nested in the argument
184    /// list is still argument territory). One linear precompute pass
185    /// (before the run loop), so the literal guards are a lookup, never a
186    /// per-literal rescan of the token prefix.
187    call_argument: Vec<bool>,
188    /// The list scan's consumed steps against `scan_budget` (see the
189    /// scan's doc) — a `Cell` so the scan stays `&self`, matching the
190    /// run loop's borrows.
191    scan_steps: Cell<u64>,
192    /// The total step budget: a healthy statement's scans visit each
193    /// token a bounded number of times, so `2 × tokens + headroom` is
194    /// never reached; the pathological re-descending shape trips it
195    /// early.
196    scan_budget: u64,
197}
198
199impl<'a, 't> Pass<'a, 't> {
200    /// Whether the list scan's step budget tripped — derived from the
201    /// counter and the budget, the same comparison the scan itself
202    /// declines on, never a stored copy of it: the whole statement
203    /// declines to not-cacheable (the parser's own guards are then its
204    /// verdict).
205    fn scan_exhausted(&self) -> bool {
206        self.scan_steps.get() > self.scan_budget
207    }
208
209    fn run(&mut self) -> Option<Normalized> {
210        let mut i = 0;
211        while i < self.tokens.len() {
212            if self.scan_exhausted() {
213                return None;
214            }
215            let tok = &self.tokens[i];
216            match tok.ty {
217                // A lexer error token fails the real parse; there is
218                // nothing to cache.
219                TokenType::Error => return None,
220                TokenType::Parameter => {
221                    if tok.literal.starts_with(AUTO_PARAM_PREFIX) {
222                        return None;
223                    }
224                    self.push_rendered(&format!("${}", tok.literal));
225                }
226                // A CIP-261 interpolated string embeds expressions, and an
227                // embedded parameter reference is invisible to the
228                // reserved-name check above — the payload is one token.
229                // The whole statement bails: an embedded `$__AUTO_*__`
230                // could otherwise collide with the rewritten text's own
231                // placeholders (found in review), and the payload's
232                // embedded literals are as unnormalizable as the
233                // interpolation itself.
234                TokenType::InterpString => return None,
235                TokenType::Identifier => {
236                    self.push_rendered(&quote_identifier(&tok.literal));
237                }
238                TokenType::Integer | TokenType::Float
239                    if !self.after_quantifier_bound(i) && !self.call_argument[i] =>
240                {
241                    let value = literal_value(tok)?;
242                    self.replace_token(i, value)?;
243                }
244                TokenType::String => {
245                    if self.is_map_key(i) || self.is_field_terminator(i) || self.call_argument[i] {
246                        // A guarded string (map key, LOAD CSV field
247                        // terminator, or a function-call argument) stays
248                        // in the template, quoted — the quotes keep it
249                        // from aliasing an identifier's render, and the
250                        // escaping keeps the render injective.
251                        self.push_rendered(&format!("'{}'", escape_single_quoted(&tok.literal)));
252                    } else {
253                        self.replace_token(i, literal_value(tok)?)?;
254                    }
255                }
256                TokenType::LeftBracket if !self.call_argument[i] => {
257                    if let Some((close, elements)) = self.scan_literal_group(i + 1) {
258                        // The whole bracket group is one parameter whose
259                        // value is the list (lists-as-one-param, the
260                        // `$__AUTO_INT_3__` positional-typed-key precedent).
261                        self.replace_group(i, close, NormalizedValue::List(elements))?;
262                        i = close;
263                    } else if self.scan_exhausted() {
264                        // The scan's step budget tripped: the statement
265                        // declines whole, not bracket by bracket.
266                        return None;
267                    } else {
268                        self.push_rendered(&tok.literal);
269                    }
270                }
271                // Every remaining token renders as written — keywords
272                // included. Case folding a keyword token is unsound at
273                // token level: the dialect keeps keyword spellings as
274                // case-sensitive NAMES (`(o:Order)` and `-[:ORDER]->`
275                // parse with the name as written, `n.match` and
276                // `{match: 1}` bind by spelling), and the token stream
277                // cannot prove a keyword sits in a clause position
278                // rather than a name position — so `match …` and
279                // `MATCH …` keep distinct templates, the safe direction.
280                _ => {
281                    self.push_rendered(&tok.literal);
282                }
283            }
284            i += 1;
285        }
286        Some(Normalized {
287            template: std::mem::take(&mut self.template),
288            rewritten: self.splice(),
289            values: std::mem::take(&mut self.values),
290            spellings: std::mem::take(&mut self.spellings),
291        })
292    }
293
294    /// Append one rendered token to the template, space-separated.
295    fn push_rendered(&mut self, text: &str) {
296        if !self.template.is_empty() {
297            self.template.push(' ');
298        }
299        self.template.push_str(text);
300    }
301
302    /// The byte offset of token `i`'s first byte.
303    fn start_byte(&self, i: usize) -> Option<usize> {
304        token_start_byte(&self.tokens[i], self.line_starts, self.src.len())
305    }
306
307    /// The byte offset the token after `i` starts at — the end of token
308    /// `i`'s replacement span (the inter-token whitespace rides out with
309    /// the literal); the source end for the final token.
310    fn end_byte(&self, i: usize) -> Option<usize> {
311        match self.tokens.get(i + 1) {
312            Some(next) => token_start_byte(next, self.line_starts, self.src.len()),
313            None => Some(self.src.len()),
314        }
315    }
316
317    /// Whether token `i` sits directly after `*` or `..`: the var-length
318    /// quantifier bounds (`[:TYPE*1..3]`), which take literal integers
319    /// only. The same shape after an arithmetic `*` (`2 * 3`) is a false
320    /// positive that costs a miss, never a wrong key.
321    fn after_quantifier_bound(&self, i: usize) -> bool {
322        i > 0 && matches!(self.tokens[i - 1].ty, TokenType::Star | TokenType::DotDot)
323    }
324
325    /// Whether token `i` is a `String` followed by `:` — a map-literal
326    /// key (`{'name': 1}`). Parameters are not map keys, and the key is
327    /// structural: it stays in the template.
328    fn is_map_key(&self, i: usize) -> bool {
329        self.tokens
330            .get(i + 1)
331            .is_some_and(|next| next.ty == TokenType::Colon)
332    }
333
334    /// Whether token `i` is the `String` after the contextual
335    /// `FIELDTERMINATOR` identifier of LOAD CSV, which requires a literal
336    /// there — decided through the crate's one spelling of that word.
337    fn is_field_terminator(&self, i: usize) -> bool {
338        i > 0
339            && self.tokens[i - 1].ty == TokenType::Identifier
340            && is_field_terminator_word(&self.tokens[i - 1].literal)
341    }
342
343    /// Replace token `i` with a fresh typed placeholder: the whole-group
344    /// emitter over a one-token span. `None` only when the token's byte
345    /// offset cannot derive — a real token stream from this source always
346    /// carries real positions.
347    fn replace_token(&mut self, i: usize, value: NormalizedValue) -> Option<()> {
348        self.replace_group(i, i, value)
349    }
350
351    /// Replace the token span `open..=close` (inclusive) with one
352    /// placeholder — the one emitter of the template text, the rewritten
353    /// span, and the value, from the one counter, so the three outputs
354    /// cannot drift. `None` only when a span endpoint's byte offset
355    /// cannot derive.
356    fn replace_group(&mut self, open: usize, close: usize, value: NormalizedValue) -> Option<()> {
357        let name = self.fresh_name(&value);
358        // One placeholder value feeds both outputs, so the template's
359        // rendering and the rewritten span are the same text by
360        // construction.
361        let placeholder = format!("${name}");
362        self.push_rendered(&placeholder);
363        let start = self.start_byte(open)?;
364        let end = self.end_byte(close)?;
365        self.spans.push((start, end, placeholder));
366        self.values.push((name, value));
367        self.spellings
368            .push(self.src[start..end].trim_end().to_string());
369        Some(())
370    }
371
372    fn fresh_name(&mut self, value: &NormalizedValue) -> String {
373        // The type tag derives from the value it names — the two cannot
374        // disagree.
375        let kind = match value {
376            NormalizedValue::Int(_) => "INT",
377            NormalizedValue::Float(_) => "FLOAT",
378            NormalizedValue::Str(_) => "STR",
379            NormalizedValue::List(_) => "LIST",
380        };
381        let name = format!("{AUTO_PARAM_PREFIX}{kind}_{}__", self.next_index);
382        self.next_index += 1;
383        name
384    }
385
386    /// Scan a bracket group's interior starting at `j` (just past the
387    /// `[`): `Some((index of the closing `]`, element values))` when every
388    /// element is a normalizable literal or such a group, comma-separated
389    /// (an empty group scans clean); `None` when anything else appears —
390    /// the caller then renders the `[` and lets the element tokens take
391    /// their own arms. The recursion is depth-capped at
392    /// [`MAX_NESTING_DEPTH`], the parser's own ADR-0257 limit: this scan
393    /// runs BEFORE the parse, so an adversarially nested payload must not
394    /// recurse past what the parser would reject anyway — a group past the
395    /// cap declines (no collapse), and the parse's depth guard is the
396    /// statement's verdict.
397    fn scan_literal_group(&self, j: usize) -> Option<(usize, Vec<NormalizedValue>)> {
398        self.scan_literal_group_at_depth(j, 0)
399    }
400
401    /// [`Pass::scan_literal_group`] with the recursion depth counted and
402    /// the total step budget charged: every visited token costs one step,
403    /// and a budget exhausted mid-scan flags the whole statement
404    /// not-cacheable — without it, a declined deep group re-descends from
405    /// the very next bracket (each restart at depth 0), turning an
406    /// adversarial payload into quadratic token visits.
407    fn scan_literal_group_at_depth(
408        &self,
409        mut j: usize,
410        depth: u32,
411    ) -> Option<(usize, Vec<NormalizedValue>)> {
412        if depth >= MAX_NESTING_DEPTH {
413            // Past the parser's depth cap the whole statement declines.
414            // A bare `None` would restart a depth-0 scan at the next `[`.
415            self.scan_steps.set(self.scan_budget.saturating_add(1));
416            return None;
417        }
418        let mut elements = Vec::new();
419        loop {
420            let steps = self.scan_steps.get() + 1;
421            self.scan_steps.set(steps);
422            if self.scan_exhausted() {
423                return None;
424            }
425            let tok = self.tokens.get(j)?;
426            let element = match tok.ty {
427                TokenType::LeftBracket => {
428                    let (close, inner) = self.scan_literal_group_at_depth(j + 1, depth + 1)?;
429                    j = close;
430                    NormalizedValue::List(inner)
431                }
432                TokenType::RightBracket if elements.is_empty() => return Some((j, elements)),
433                // `literal_value` is the scan's only token vocabulary: a
434                // non-literal is `None`, which declines the group.
435                _ => literal_value(tok)?,
436            };
437            elements.push(element);
438            j += 1;
439            match self.tokens.get(j)?.ty {
440                TokenType::Comma => j += 1,
441                TokenType::RightBracket => return Some((j, elements)),
442                _ => return None,
443            }
444        }
445    }
446
447    /// Build the rewritten statement: the source with every replacement
448    /// span spliced out for its placeholder. The span swallows the
449    /// inter-token whitespace with the literal, so a separator is put back
450    /// only when the next character would glue onto the placeholder
451    /// (`$__AUTO_INT_0__LIMIT` would lex as one name). An operator stays
452    /// where the source put it (`1+2`), which is what a projection's
453    /// column name round-trips from. The spans are in source order by
454    /// construction (the walk appends them in token order and
455    /// `replace_group` covers its whole interior).
456    fn splice(&self) -> String {
457        let mut out = String::with_capacity(self.src.len());
458        let mut cursor = 0;
459        for (start, end, placeholder) in &self.spans {
460            if *start > cursor {
461                out.push_str(&self.src[cursor..*start]);
462            }
463            out.push_str(placeholder);
464            // The span swallowed the original separator. Put one back only
465            // when the next character would otherwise glue to the
466            // placeholder (`$__AUTO_INT_0__LIMIT`). `1+2` keeps its `+`.
467            let glue = self.src[*end..]
468                .chars()
469                .next()
470                .is_some_and(|ch| ch == '$' || ch == '_' || ch.is_ascii_alphanumeric());
471            if glue {
472                out.push(' ');
473            }
474            cursor = *end;
475        }
476        out.push_str(&self.src[cursor..]);
477        out
478    }
479}
480
481/// The per-token function-call-argument context, in one linear pass: a
482/// token is argument territory when the innermost unmatched **paren**
483/// enclosing it is a call's (its callee identifier standing before it).
484/// A paren-only stack answers that in O(1) per token — brackets and
485/// braces are transparent (a map or list nested in an argument list is
486/// still argument territory, its literals feeding the same constant
487/// fold; one outside any call sees an empty or non-call paren stack) —
488/// and closers of a different kind never pop a paren, so the stack stays
489/// exact for parseable input. The precompute replaces a per-literal
490/// rescan of the token prefix (quadratic on the pre-parse lookup path,
491/// found in review) and itself never rescans the stack.
492fn call_argument_context(tokens: &[Token<'_>]) -> Vec<bool> {
493    #[derive(Clone, Copy, PartialEq)]
494    enum Paren {
495        Call,
496        Other,
497    }
498    let mut parens: Vec<Paren> = Vec::new();
499    let mut context = Vec::with_capacity(tokens.len());
500    for (i, tok) in tokens.iter().enumerate() {
501        context.push(parens.last() == Some(&Paren::Call));
502        match tok.ty {
503            TokenType::LeftParen => {
504                let is_call = i > 0 && tokens[i - 1].ty == TokenType::Identifier;
505                parens.push(if is_call { Paren::Call } else { Paren::Other });
506            }
507            TokenType::RightParen => {
508                parens.pop();
509            }
510            // Brackets and braces: transparent — no push, no pop, so a
511            // paren opened inside them still matches its own closer and
512            // the territory answer passes through unchanged.
513            _ => {}
514        }
515    }
516    context
517}
518
519/// The literal value one literal token carries — the one token-to-value
520/// mapping both the run loop's literal arms and the list scan read, with
521/// the same bail policy (`None`, nothing to cache) for anything that does
522/// not decode.
523fn literal_value(tok: &Token) -> Option<NormalizedValue> {
524    match tok.ty {
525        TokenType::Integer => Some(NormalizedValue::Int(parse_int_literal(&tok.literal).ok()?)),
526        TokenType::Float => Some(NormalizedValue::Float(parse_finite_float(&tok.literal)?)),
527        TokenType::String => Some(NormalizedValue::Str(tok.literal.to_string())),
528        _ => None,
529    }
530}
531
532/// Parse a float literal the way the parser's own expression arm does
533/// (CIP-52): a numeric literal that overflows to ±infinity is a
534/// compile-time error, so the statement never parses — `None`, nothing to
535/// cache.
536fn parse_finite_float(literal: &str) -> Option<f64> {
537    let value: f64 = literal.parse().ok()?;
538    value.is_finite().then_some(value)
539}
540
541/// Escape a skipped string's value for its single-quoted template render:
542/// backslash and quote doubled, everything else as-is. The render is
543/// injective on the value (a key string is data, not a spelling), which
544/// is all the template needs from it. The parser crate does not depend
545/// on `relate-core` (which spells this same two-character policy as
546/// its `escape_cypher_string`), so the policy is owned here, at this
547/// boundary, rather than imported.
548fn escape_single_quoted(value: &str) -> String {
549    let mut out = String::with_capacity(value.len());
550    for ch in value.chars() {
551        match ch {
552            '\\' | '\'' => {
553                out.push('\\');
554                out.push(ch);
555            }
556            _ => out.push(ch),
557        }
558    }
559    out
560}
561
562#[cfg(test)]
563#[path = "normalize_tests.rs"]
564mod tests;