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("e_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;