// Explicit whitespace, used below.
// Pest allows implicit whitespace with WHITESPACE; we don't do that here.
whitespace = _{ " " }
// Shorthand for optional whitespace between tokens
sp = _{ whitespace* }
// Basic Terminals
identifier = @{ ASCII_ALPHA ~ (ASCII_ALPHANUMERIC | "_")* }
integer = @{ "-"? ~ ASCII_DIGIT+ }
float = @{ "-"? ~ ASCII_DIGIT+ ~ "." ~ ASCII_DIGIT+ }
boolean = @{ "true" | "false" }
// Basic string literals, does not handle escape sequences for simplicity here.
// String literals are for literal values
string_literal = @{
"\'" ~ // opening quote
(("\\" ~ ANY) // Escape sequence
| (!"\'" ~ ANY) // Any character except the closing quote
)* // middle
~ "\'" // closing quote
}
// Quoted names are for function names or other identifiers that need to be quoted
quoted_name = @{
"\"" ~ // opening quote
(("\\" ~ ANY) // Escape sequence
| (!"\"" ~ ANY) // Any character except the closing quote
)* // middle
~ "\"" // closing quote
}
// A name of a function or table can either be an unquoted identifier or a quoted string
name = { identifier | quoted_name }
// A compound name is a Substrait function compound name: base identifier followed by an optional
// colon-delimited signature (e.g. "equal:any_any", "regexp_match_substring:str_str_i64").
// The rule is atomic so no whitespace is allowed around the colon, making it unambiguous
// with the output-type annotation which always follows the closing parenthesis.
compound_name = @{ identifier ~ (":" ~ identifier)? }
// Expression Components
// Field reference
reference = { "$" ~ integer }
// Literal
literal = { (float | integer | boolean | string_literal) ~ (":" ~ sp ~ type)? }
// -- Components for types and functions
anchor = { "#" ~ sp ~ integer }
urn_anchor = { "@" ~ sp ~ integer }
parameter = { type | integer | name }
// An arbitrary parameter list for use with type expressions or function calls.
// Example: <T, V>
//
// Note that if a type can have no parameters, there should be no parameter list.
// A type that can take parameters but has an empty parameter list should be
// written with the empty parameter list.
//
// As examples: 'i64' and 'struct<>' are valid, but 'i64<>' and 'struct' are not.
parameters = { "<" ~ (parameter ~ ("," ~ sp ~ parameter)*)? ~ ">" }
// Nullability - ? for nullable, nothing for non-nullable. And for unspecified, ⁉.
nullability = { ("?" | "⁉")? }
// -- Type Expressions --
// See <https://substrait.io/types/type_classes/>. These must be lowercase.
simple_type_name = {
"boolean"
| "i8"
| "i16"
| "i32"
| "i64"
| "u8"
| "u16"
| "u32"
| "u64"
| "fp32"
| "fp64"
| "string"
| "binary"
| "timestamp_tz"
| "timestamp"
| "date"
| "time"
| "interval_year"
| "uuid"
}
// A simple native type expression, composed of a name and optional nullability.
// Examples: i64, bool?, string
simple_type = { simple_type_name ~ nullability }
// -- Compound Types --
//
// Note that the names here are case-insensitive. In the docs, they are shown as
// upper-case, but I prefer them lowercase...
// A list type expression, composed of a list keyword and a type.
// Example: list<i64>
list_type = { ^"list" ~ nullability ~ "<" ~ type ~ ">" }
// A map type expression, composed of a map keyword and a key type and a value type.
// Example: map<i64, string>
map_type = { ^"map" ~ nullability ~ "<" ~ type ~ "," ~ sp ~ type ~ ">" }
struct_type = { ^"struct" ~ nullability ~ parameters }
// A compound type expression, composed of a name, optional parameters, and optional nullability.
// Example: LIST?<fp64?>, MAP<i64, string>
// TODO: precisiontime types, interval_day
compound_type = { list_type | map_type | struct_type }
// A user-defined type expression.
//
// Example: point#8@2?<i8>
//
// - The `u!` prefix is optional.
// - The anchor is optional if the name is unique in the extensions; otherwise,
// required.
// - The URN anchor is optional. Note that this is different from type
// expressions in the YAML, where these do not exist.
// - If the type is nullable, the nullability is required.
// - The parameters are required if they exist for this type.
user_defined_type = {
"u!"? ~ name ~ anchor? ~ urn_anchor? ~ nullability ~ parameters?
}
// A type expression is a simple type, a compound type, or a user-defined type.
type = { simple_type | compound_type | user_defined_type }
// -- Function Calls --
argument_list = { "(" ~ (expression ~ (sp ~ "," ~ sp ~ expression)*)? ~ ")" }
// Scalar function call:
// - Compound function name (base name or base:signature, e.g. "equal" or "equal:any_any")
// - Optional Anchor, e.g. #1
// - Optional URN Anchor, e.g. @1
// - Arguments `()` are required, e.g. (1, 2, 3)
// - Optional output type annotation after closing paren, e.g. :i64
// (unambiguous because compound_name is atomic and ends before the opening paren)
function_call = {
compound_name ~ sp ~ anchor? ~ sp ~ urn_anchor? ~ sp ~ argument_list ~ (":" ~ sp ~ type)?
}
if_clause = {
expression ~ sp ~ "->" ~ sp ~ expression
}
// For the form: if_then(true || false -> true, _ -> false)
if_then = {
"if_then(" ~ sp ~ (if_clause ~ sp ~ "," ~ sp)+ ~ sp ~ "_" ~ sp ~ "->" ~ sp ~ expression ~ ")"
}
// Enum value, e.g. &Inner, &CORE, &AscNullsFirst
enum_value = @{ "&" ~ identifier }
// Cast failure behavior: ? for RETURN_NULL, ! for THROW_EXCEPTION, absent for UNSPECIFIED
cast_failure_behavior = { "?" | "!" }
// Cast expression: wraps an expression in parens and appends ::target_type
// Optional failure behavior prefix before the type:
// (78:i32)::i16 UNSPECIFIED (default)
// (78:i32)::?i16 RETURN_NULL
// (78:i32)::!i16 THROW_EXCEPTION
cast_expression = { "(" ~ sp ~ expression ~ sp ~ ")" ~ sp ~ "::" ~ sp ~ cast_failure_behavior? ~ sp ~ type }
// Top-level Expression Rule
// Order matters for PEGs: Since an identifer can be a function call, we put that first.
// cast_expression must come before literal/function_call since it starts with "("
expression = { if_then | cast_expression | function_call | reference | literal }
// == Extensions ==
// These rules are for parsing extension declarations, by line.
// -- URN Extension Declaration --
// Format: @anchor: urn_value
// Example: @1: /my/urn1
// `urn_anchor` is defined above as "@" ~ integer.
// `sp` is defined above as whitespace*.
// A URN value can be a sequence of non-whitespace characters
urn = @{ (!whitespace ~ ANY)+ }
extension_urn_declaration = { urn_anchor ~ ":" ~ sp ~ urn }
// -- Simple Extension Declaration (Function, Type, TypeVariation) --
// Format: #anchor@urn_ref: name_or_compound_name
// Examples: #10@1: my_func #1@2: equal:any_any
// `anchor` is defined above as "#" ~ integer.
// `urn_anchor` is defined above as "@" ~ integer.
// `compound_name` accepts both plain names and compound names with signatures.
simple_extension = { anchor ~ sp ~ urn_anchor ~ sp ~ ":" ~ sp ~ compound_name }
// == Relations ==
// These rules are for parsing relations - well, for parsing one relation on one line.
// A relation is in the form:
// NAME[parameters => columns]
//
// Parameters are optional, and are a comma-separated list of expressions.
// Columns are required, and are a comma-separated list of named columns.
//
// Example:
//
// name "[" (arguments "=>")? columns "]"
// where:
// - arguments are a comma-separated list of table names or expressions
table_name = { (name ~ ("." ~ name)*) }
named_column = { name ~ ":" ~ type }
named_column_list = { (named_column ~ ("," ~ sp ~ named_column)*)? }
planNode = {
// virtual_read_relation must precede read_relation: both start with "Read",
// and PEG tries alternatives in order — the longer "Read:Virtual" prefix
// must be attempted first.
virtual_read_relation
| read_relation
| filter_relation
| project_relation
| aggregate_relation
| sort_relation
| fetch_relation
| join_relation
| extension_relation
| adv_extension
}
// At the top level, we can have a RelRoot, or a regular relation; both are valid.
top_level_relation = {
root_relation
| planNode
}
root_relation = { "Root" ~ "[" ~ root_name_list ~ "]" }
root_name_list = { (name ~ (sp ~ "," ~ sp ~ name)*)? }
read_relation = { "Read" ~ "[" ~ table_name ~ sp ~ "=>" ~ sp ~ named_column_list ~ "]" }
// VirtualTable read: Read:Virtual[rows => columns] or Read:Virtual[_ => columns]
// Rows are parenthesized tuples; _ means empty (no rows).
virtual_read_relation = { "Read:Virtual" ~ "[" ~ virtual_read_args ~ sp ~ "=>" ~ sp ~ named_column_list ~ "]" }
virtual_read_args = { virtual_row_list | empty }
virtual_row_list = { virtual_row ~ (sp ~ "," ~ sp ~ virtual_row)* }
virtual_row = { "(" ~ sp ~ expression_list? ~ sp ~ ")" }
filter_relation = { "Filter" ~ "[" ~ expression ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
reference_list = { (reference ~ (sp ~ "," ~ sp ~ reference)*)? }
project_relation = { "Project" ~ "[" ~ project_argument_list ~ "]" }
project_argument_list = { (project_argument ~ (sp ~ "," ~ sp ~ project_argument)*)? }
project_argument = { reference | expression }
// Aggregate relation: groups by specified fields and applies aggregate functions
// Format: Aggregate[group_by_fields => output_items]
// Examples:
// Aggregate[$0 => $0, sum($1), count($1)] # common case, 1 group, grouping on field 0, output is measure expressions and expressions used in group by
// Aggregate[$0, $1 => $0, $1, sum($2), count($2)] # common case, 1 group, grouping on fields 0 and 1, output sum, count and group by expressions
// Aggregate[($0, $1), ($1) => $0, $1, sum($2)] # multiple grouping sets. group by fields 0,1, and field 1, output are fields 0 and 1 and sum on field 2
// Aggregate[_ => sum($0), count($1)] # No grouping (global aggregates)
aggregate_relation = { "Aggregate" ~ "[" ~ aggregate_group_by ~ sp ~ "=>" ~ sp ~ aggregate_output ~ "]" }
aggregate_group_by = { grouping_set_list | expression_list }
grouping_set_list = { grouping_set ~ sp ~ ("," ~ sp ~ grouping_set)* }
grouping_set = { ("(" ~ sp ~ expression_list ~ sp ~ ")") | empty }
expression_list = { expression ~ sp ~ ("," ~ sp ~ expression)* }
aggregate_output = { (aggregate_output_item ~ (sp ~ "," ~ sp ~ aggregate_output_item)*)? }
aggregate_output_item = { reference | aggregate_measure }
// TODO: Add support for filter, invocation, etc.
aggregate_measure = { function_call }
// Empty grouping symbol
empty = { "_" }
// SortRel: Sort[($0, &AscNullsFirst), ($2, &DescNullsLast) => ...]
sort_relation = { "Sort" ~ "[" ~ sort_field_list ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
sort_field_list = { (sort_field ~ (sp ~ "," ~ sp ~ sort_field)*)? }
sort_field = { "(" ~ sp ~ reference ~ sp ~ "," ~ sp ~ sort_direction ~ sp ~ ")" }
sort_direction = { "&AscNullsFirst" | "&AscNullsLast" | "&DescNullsFirst" | "&DescNullsLast" }
// FetchRel: Fetch[limit=..., offset=... => ...] (named arguments only, any order, or _ for empty)
fetch_arg_name = { "limit" | "offset" }
fetch_value = { integer | expression }
fetch_named_arg = { fetch_arg_name ~ sp ~ "=" ~ sp ~ fetch_value }
fetch_named_arg_list = { fetch_named_arg ~ (sp ~ "," ~ sp ~ fetch_named_arg)* }
fetch_args = _{ fetch_named_arg_list | empty }
fetch_relation = { "Fetch" ~ "[" ~ fetch_args ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
// JoinRel: Join[&Inner, eq($0, $2) => $0, $1, $2, $3]
// Note: Longer prefixes must come before shorter ones (e.g., "&LeftSemi" before "&Left")
// so that the parser doesn't match "&Left" when it should match "&LeftSemi"
join_type = { "&Inner" | "&LeftSemi" | "&LeftAnti" | "&LeftSingle" | "&LeftMark" | "&Left" | "&RightSemi" | "&RightAnti" | "&RightSingle" | "&RightMark" | "&Right" | "&Outer" }
join_relation = { "Join" ~ "[" ~ join_type ~ sp ~ "," ~ sp ~ expression ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
// Extension relations for custom operators not covered by standard Substrait
// Format: ExtensionType:ExtensionName[arguments, named_arguments => columns]
// Follows the general relation grammar pattern exactly
// Examples:
// - ExtensionLeaf:ParquetScan[path='data/*.parquet', schema='auto' => col1:i32, col2:string]
// - ExtensionSingle:VectorNormalize[method='l2', dimensions=128 => $0, $1]
// - ExtensionMulti:FuzzyJoin[algorithm='lsh', threshold=0.8 => $0, $1, $2, $3]
extension_relation = { extension_name ~ "[" ~ sp ~ arguments ~ (sp ~ "=>" ~ sp ~ extension_columns)? ~ "]" }
// Extension name format: ExtensionType:CustomExtensionName
extension_name = { extension_type ~ ":" ~ name }
extension_type = { "ExtensionLeaf" | "ExtensionSingle" | "ExtensionMulti" }
arguments = { (empty | (extension_arguments ~ (sp ~ "," ~ sp ~ extension_named_arguments)?) | extension_named_arguments)? }
// Positional arguments (expressions, literals, references, enums, tuples)
extension_arguments = { extension_argument ~ (sp ~ "," ~ sp ~ extension_argument)* }
// Tuples follow the Python/Rust trailing-comma convention to disambiguate from parenthesised
// expressions.
tuple = {
// empty tuple (0-tuple)
"(" ~ sp ~ ")"
// Single element (1-tuple) - uses trailing comma to distinguish from expression
| "(" ~ sp ~ extension_argument ~ sp ~ "," ~ sp ~ ")"
// Multi-element tuple. Trailing comma optional.
| "(" ~ sp ~ extension_argument
~ (sp ~ "," ~ sp ~ extension_argument)+
~ (sp ~ ",")? ~ sp ~ ")"
}
extension_argument = { enum_value | reference | literal | expression | tuple }
// Named arguments (name=value pairs)
extension_named_arguments = { extension_named_argument ~ (sp ~ "," ~ sp ~ extension_named_argument)* }
extension_named_argument = { name ~ sp ~ "=" ~ sp ~ extension_argument }
// Output columns - can mix named columns, references, and expressions
extension_columns = { (extension_column ~ (sp ~ "," ~ sp ~ extension_column)*)? }
extension_column = { named_column | reference | expression }
// Advanced extensions: enhancements and optimizations attached to relations
// Format: + Enh:Name[args] or + Opt:Name[args]
// Examples:
// - + Enh:PartitionHint[&HASH, count=8]
// - + Opt:SomeOptimization[threshold=100, mode='fast']
adv_extension = { "+" ~ sp ~ adv_ext_type ~ ":" ~ name ~ "[" ~ arguments ~ "]" }
adv_ext_type = { "Enh" | "Opt" }