squonk_ast/ast/
match_recognize.rs

1// SPDX-License-Identifier: MIT
2// Copyright (c) 2026 Moderately AI Inc.
3
4//! Row pattern recognition — the `<source> MATCH_RECOGNIZE (…)` table factor
5//! (SQL:2016 `<row pattern recognition clause>`; Snowflake / Oracle).
6//!
7//! `MATCH_RECOGNIZE` runs a regular expression over the *rows* of a partition, in a
8//! defined order, and projects a row (or one row per match) from the matched runs.
9//! It is modelled as a table-factor suffix ([`TableFactor::MatchRecognize`]) — the
10//! `PIVOT`/`UNPIVOT` precedent — carrying one [`MatchRecognize`] operator core:
11//!
12//! ```text
13//! <source> MATCH_RECOGNIZE (
14//!     [ PARTITION BY <expr>, … ]
15//!     [ ORDER BY <sort>, … ]
16//!     [ MEASURES <expr> AS <name>, … ]
17//!     [ ONE ROW PER MATCH | ALL ROWS PER MATCH [ SHOW EMPTY MATCHES
18//!                                              | OMIT EMPTY MATCHES
19//!                                              | WITH UNMATCHED ROWS ] ]
20//!     [ AFTER MATCH SKIP { PAST LAST ROW | TO NEXT ROW
21//!                        | TO FIRST <sym> | TO LAST <sym> } ]
22//!     PATTERN ( <row pattern> )
23//!     [ SUBSET <name> = ( <sym>, … ), … ]
24//!     [ DEFINE <sym> AS <condition>, … ]
25//! )
26//! ```
27//!
28//! # Parity with, and deviations from, sqlparser-rs
29//!
30//! The shape follows sqlparser-rs's `MatchRecognize` family (`Measure`,
31//! `RowsPerMatch`, `EmptyMatchesMode`, `AfterMatchSkip`, `SymbolDefinition`,
32//! `MatchRecognizePattern`, `RepetitionQuantifier`), reshaped per ADR-0011 where
33//! their model is lossy:
34//!
35//! - **Anchors are inlined into [`MatchRecognizePattern`].** sqlparser-rs nests them
36//!   in a separate `MatchRecognizeSymbol { Named, Start, End }` reached through
37//!   `Pattern::Symbol`/`Exclude`/`Permute`; we hoist [`Start`](MatchRecognizePattern::Start)
38//!   and [`End`](MatchRecognizePattern::End) to sibling pattern variants so the tree
39//!   is one recursive enum, not two.
40//! - **[`Exclude`](MatchRecognizePattern::Exclude) and
41//!   [`Permute`](MatchRecognizePattern::Permute) carry full sub-patterns**, not the
42//!   bare symbols sqlparser-rs restricts them to — the SQL:2016 grammar allows a
43//!   pattern inside `{- … -}` and each `PERMUTE(…)` argument, so the symbol-only
44//!   shape is lossy.
45//! - **[`Concat`](MatchRecognizePattern::Concat) is added** as an explicit
46//!   sequence node (sqlparser-rs has it too), and a single-element sequence/branch is
47//!   flattened to its inner pattern so `PATTERN (A)` is a bare
48//!   [`Symbol`](MatchRecognizePattern::Symbol), never a one-element `Concat`.
49//! - **`SUBSET` is modelled** ([`SubsetDefinition`]) — the Oracle union-variable
50//!   clause sqlparser-rs omits entirely.
51//! - We keep sqlparser-rs's [`RepetitionQuantifier`] arms verbatim (no *reluctant*
52//!   `?` suffix): the reluctant marker needs a `?` token that the eager
53//!   context-free tokenizer (ADR-0005) cannot produce in pattern position (it is the
54//!   anonymous placeholder / a stray byte), so there is nothing to round-trip.
55//!
56//! Both operators are gated on
57//! [`TableFactorSyntax::match_recognize`](crate::dialect::TableFactorSyntax) (Snowflake
58//! and Lenient). See the parser's `match_recognize` module for the lexer-reachability
59//! notes on the `$` anchor and `?` quantifier.
60
61use super::{Expr, Extension, Ident, NoExt, OrderByExpr, TableFactor};
62use crate::vocab::Meta;
63use thin_vec::ThinVec;
64
65/// The `MATCH_RECOGNIZE (…)` operator core — the row-pattern-recognition clause
66/// applied to a [`source`](Self::source) relation, hosted by
67/// [`TableFactor::MatchRecognize`](crate::ast::TableFactor) (which owns the trailing
68/// `AS <alias>`).
69///
70/// `source` is boxed to break the `TableFactor` → `MatchRecognize` → `TableFactor`
71/// type cycle (the [`Pivot`](crate::ast::Pivot) precedent), and the whole core is
72/// boxed again inside the table-factor variant to keep that hot enum lean (ADR-0007).
73/// Every clause but [`pattern`](Self::pattern) is optional; the field order matches
74/// the fixed clause order the grammar requires.
75#[derive(Clone, Debug, PartialEq, Eq, Hash)]
76#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
77#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
78pub struct MatchRecognize<X: Extension = NoExt> {
79    /// Input source for this syntax.
80    pub source: Box<TableFactor<X>>,
81    /// `PARTITION BY <expr>, …` — the partitions matched independently; empty when
82    /// absent (the whole input is one partition).
83    pub partition_by: ThinVec<Expr<X>>,
84    /// `ORDER BY <sort>, …` — the row order the pattern matches against; empty when
85    /// absent.
86    pub order_by: ThinVec<OrderByExpr<X>>,
87    /// `MEASURES <expr> AS <name>, …` — the columns computed from a match; empty when
88    /// absent.
89    pub measures: ThinVec<Measure<X>>,
90    /// `ONE ROW PER MATCH` / `ALL ROWS PER MATCH [ … ]`; `None` leaves the engine
91    /// default (`ONE ROW PER MATCH`) unwritten.
92    pub rows_per_match: Option<RowsPerMatch>,
93    /// `AFTER MATCH SKIP …` — where matching resumes after a match; `None` leaves the
94    /// default (`AFTER MATCH SKIP PAST LAST ROW`) unwritten.
95    pub after_match_skip: Option<AfterMatchSkip>,
96    /// `PATTERN ( <row pattern> )` — the row-pattern regular expression. Mandatory.
97    pub pattern: MatchRecognizePattern,
98    /// `SUBSET <name> = ( <sym>, … ), …` — union pattern variables (Oracle); empty
99    /// when absent.
100    pub subsets: ThinVec<SubsetDefinition>,
101    /// `DEFINE <sym> AS <condition>, …` — the boolean conditions defining each
102    /// pattern variable; empty when absent (an undefined variable matches every row).
103    pub define: ThinVec<SymbolDefinition<X>>,
104    /// Source location and node identity.
105    pub meta: Meta,
106}
107
108/// One `MEASURES` item: `<expr> AS <name>` — an expression computed over a match,
109/// projected under an output name.
110#[derive(Clone, Debug, PartialEq, Eq, Hash)]
111#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
112#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
113pub struct Measure<X: Extension = NoExt> {
114    /// Expression evaluated by this syntax.
115    pub expr: Expr<X>,
116    /// Alias assigned by this syntax.
117    pub alias: Ident,
118    /// Source location and node identity.
119    pub meta: Meta,
120}
121
122/// The `ONE ROW PER MATCH` / `ALL ROWS PER MATCH` output cardinality.
123///
124/// A tag enum (no spanned children) — [`AllRows`](Self::AllRows) carries the optional
125/// empty-match mode that only the `ALL ROWS` form admits.
126#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
127#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
128#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
129pub enum RowsPerMatch {
130    /// `ONE ROW PER MATCH` — one summary row per match.
131    OneRow,
132    /// `ALL ROWS PER MATCH [ SHOW EMPTY MATCHES | OMIT EMPTY MATCHES
133    /// | WITH UNMATCHED ROWS ]` — one row per matched (and optionally unmatched) input
134    /// row.
135    AllRows(Option<EmptyMatchesMode>),
136}
137
138/// The `ALL ROWS PER MATCH` empty/unmatched-row treatment.
139#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
140#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
141#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
142pub enum EmptyMatchesMode {
143    /// `SHOW EMPTY MATCHES`.
144    Show,
145    /// `OMIT EMPTY MATCHES`.
146    Omit,
147    /// `WITH UNMATCHED ROWS`.
148    WithUnmatched,
149}
150
151/// The `AFTER MATCH SKIP …` clause — where the matcher resumes after a match.
152///
153/// A spanned node (every variant carries `meta`) because the
154/// [`ToFirst`](Self::ToFirst)/[`ToLast`](Self::ToLast) forms name a pattern variable.
155#[derive(Clone, Debug, PartialEq, Eq, Hash)]
156#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
157#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
158pub enum AfterMatchSkip {
159    /// `AFTER MATCH SKIP PAST LAST ROW` (the engine default).
160    PastLastRow {
161        /// Source location and node identity.
162        meta: Meta,
163    },
164    /// `AFTER MATCH SKIP TO NEXT ROW`.
165    ToNextRow {
166        /// Source location and node identity.
167        meta: Meta,
168    },
169    /// `AFTER MATCH SKIP TO FIRST <sym>`.
170    ToFirst {
171        /// Pattern symbol referenced by this syntax.
172        symbol: Ident,
173        /// Source location and node identity.
174        meta: Meta,
175    },
176    /// `AFTER MATCH SKIP TO LAST <sym>`.
177    ToLast {
178        /// Pattern symbol referenced by this syntax.
179        symbol: Ident,
180        /// Source location and node identity.
181        meta: Meta,
182    },
183}
184
185/// One `SUBSET` union-variable definition: `<name> = ( <member>, … )` — a pattern
186/// variable standing for the union of the listed variables' rows (Oracle).
187#[derive(Clone, Debug, PartialEq, Eq, Hash)]
188#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
189#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
190pub struct SubsetDefinition {
191    /// Name referenced by this syntax.
192    pub name: Ident,
193    /// members in source order.
194    pub members: ThinVec<Ident>,
195    /// Source location and node identity.
196    pub meta: Meta,
197}
198
199/// One `DEFINE` clause: `<sym> AS <condition>` — the boolean condition a row must
200/// satisfy to be classified as the pattern variable `symbol`.
201#[derive(Clone, Debug, PartialEq, Eq, Hash)]
202#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
203#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
204pub struct SymbolDefinition<X: Extension = NoExt> {
205    /// Interned source spelling.
206    pub symbol: Ident,
207    /// The boolean condition a row must satisfy to be classified as this variable.
208    pub definition: Expr<X>,
209    /// Source location and node identity.
210    pub meta: Meta,
211}
212
213/// The row-pattern regular expression inside `PATTERN ( … )` — a recursive grammar of
214/// pattern variables, anchors, grouping, alternation, concatenation, exclusion,
215/// permutation, and quantifiers.
216///
217/// Non-generic in the extension parameter: a pattern references only variable names
218/// ([`Ident`]) and structural operators, never an [`Expr`]. Every variant carries
219/// `meta`, so the whole tree is addressable (ADR-0002); the recursion is bounded by
220/// the parser's shared depth guard.
221#[derive(Clone, Debug, PartialEq, Eq, Hash)]
222#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
223#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
224pub enum MatchRecognizePattern {
225    /// A pattern variable reference (`A`, `STRT`).
226    Symbol {
227        /// Pattern symbol referenced by this syntax.
228        symbol: Ident,
229        /// Source location and node identity.
230        meta: Meta,
231    },
232    /// The partition-start anchor `^`.
233    Start {
234        /// Source location and node identity.
235        meta: Meta,
236    },
237    /// The partition-end anchor `$`.
238    End {
239        /// Source location and node identity.
240        meta: Meta,
241    },
242    /// A concatenation (sequence) `a b c` — matched in order.
243    Concat {
244        /// patterns in source order.
245        patterns: ThinVec<MatchRecognizePattern>,
246        /// Source location and node identity.
247        meta: Meta,
248    },
249    /// An alternation `a | b | c` — matched as the first branch that succeeds.
250    Alternation {
251        /// patterns in source order.
252        patterns: ThinVec<MatchRecognizePattern>,
253        /// Source location and node identity.
254        meta: Meta,
255    },
256    /// A parenthesized group `( … )`.
257    Group {
258        /// The grouped sub-pattern.
259        pattern: Box<MatchRecognizePattern>,
260        /// Source location and node identity.
261        meta: Meta,
262    },
263    /// An exclusion `{- … -}` — matched but omitted from `ALL ROWS PER MATCH` output.
264    Exclude {
265        /// The excluded sub-pattern.
266        pattern: Box<MatchRecognizePattern>,
267        /// Source location and node identity.
268        meta: Meta,
269    },
270    /// `PERMUTE ( p1, p2, … )` — matches the arguments in any order.
271    Permute {
272        /// patterns in source order.
273        patterns: ThinVec<MatchRecognizePattern>,
274        /// Source location and node identity.
275        meta: Meta,
276    },
277    /// A quantified pattern `p*`, `p+`, `p{2,3}` — repeat `pattern` per `quantifier`.
278    Repetition {
279        /// The repeated sub-pattern.
280        pattern: Box<MatchRecognizePattern>,
281        /// The repetition count or range (`*`/`+`/`?`/`{m,n}`); see [`RepetitionQuantifier`].
282        quantifier: RepetitionQuantifier,
283        /// Source location and node identity.
284        meta: Meta,
285    },
286}
287
288/// A row-pattern quantifier — the repetition count applied to a pattern factor.
289///
290/// A tag enum (its bounds are plain `u32`s, no spanned children). Mirrors
291/// sqlparser-rs verbatim. The `AtMostOne` (`?`) form has no lexer-reachable parser
292/// path — see the module docs — but is retained for parity and lossless rendering.
293#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
294#[cfg_attr(feature = "serde-serialize", derive(serde::Serialize))]
295#[cfg_attr(feature = "serde-deserialize", derive(serde::Deserialize))]
296pub enum RepetitionQuantifier {
297    /// `*` — zero or more.
298    ZeroOrMore,
299    /// `+` — one or more.
300    OneOrMore,
301    /// `?` — zero or one.
302    AtMostOne,
303    /// `{n}` — exactly `n`.
304    Exactly(u32),
305    /// `{n,}` — at least `n`.
306    AtLeast(u32),
307    /// `{,m}` — at most `m`.
308    AtMost(u32),
309    /// `{n,m}` — between `n` and `m` (inclusive).
310    Range(u32, u32),
311}
squonk_ast/ast/match_recognize.rs

squonk_ast/ast/
match_recognize.rs
