// 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" }
null = @{ "null" }
// 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 }
// Short argument type name in a function signature.
// Underscores are intentionally excluded: "_" is the argument separator in argument_signature,
// so a type name like "json_str" cannot be written as a single arg — it would parse as
// two arguments "json" and "str". All Substrait-defined arg type codes are alphanumeric-only.
// Examples: "i64", "str", "any", "json"
short_arg_name = @{ ASCII_ALPHA ~ ASCII_ALPHANUMERIC* }
// A single argument type in a function signature: plain or u!-prefixed.
// Examples: "i64", "u!json"
short_arg_type = @{ "u!" ~ short_arg_name | short_arg_name }
// The type-signature suffix of a function signature: underscore-separated argument types.
// Examples: "any_any", "i64_i64", "u!json_str"
argument_signature = @{ short_arg_type ~ ("_" ~ short_arg_type)* }
// A Substrait function signature: function base name with an optional colon-delimited type-signature suffix.
// Examples: "add", "equal:any_any", "count:", "json_extract_path:u!json_str"
function_signature = @{ identifier ~ (":" ~ argument_signature?)? }
// Expression Components
// Field reference
reference = { "$" ~ integer }
// Literal
literal = { (float | integer | boolean | string_literal | null) ~ (":" ~ 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 }
// Precision timestamp types take an integer precision parameter.
// Example: precisiontimestamp<9>, precisiontimestamptz?<6>
precision_timestamp_tz_type = { ^"precisiontimestamptz" ~ nullability ~ "<" ~ integer ~ ">" }
precision_timestamp_type = { ^"precisiontimestamp" ~ nullability ~ "<" ~ integer ~ ">" }
precision_time_type = { ^"precisiontime" ~ nullability ~ "<" ~ integer ~ ">" }
// A compound type expression, composed of a name, optional parameters, and optional nullability.
// Example: LIST?<fp64?>, MAP<i64, string>
// TODO: interval_day
compound_type = { list_type | map_type | struct_type | precision_timestamp_tz_type | precision_timestamp_type | precision_time_type }
// A user-defined type expression. The u! prefix is optional and ignored for lookup purposes;
// both "json" and "u!json" resolve to the same extension.
// Examples: "point#8@2?<i8>", "json?", "u!json?", "geo_point#5@1", "u!geo_point#5@1"
// Anchor is required when the name is ambiguous across URNs; URN anchor is optional.
// TODO: Do we need to support quoted names / special characters in type/function names?
user_defined_type = {
"u!"? ~ identifier ~ 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)
// - Required output type annotation after closing paren, e.g. :i64
// (unambiguous because function_signature is atomic and ends before the opening paren)
function_call = {
function_signature ~ 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 identifier 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: simple_extension_name
// Examples: #10@1: my_func #1@2: equal:any_any #5@1: json #11@1: u!point
// `anchor` is defined above as "#" ~ integer.
// `urn_anchor` is defined above as "@" ~ integer.
simple_extension_name = @{ "u!"? ~ identifier ~ (":" ~ argument_signature?)? }
simple_extension = { anchor ~ sp ~ urn_anchor ~ sp ~ ":" ~ sp ~ simple_extension_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)*)? }
// -- Output clauses --
// `=>` declares the final visible output columns without preserving a RelCommon.emit distinction.
// `+>` declares the direct output domain. Without `|>`, it is an explicit
// `|>` the trailing reference list is preserved as an explicit Emit over that direct output domain.
output = { implicit_output | direct_output }
implicit_output = { "=>" ~ sp ~ named_column_list }
direct_output = { "+>" ~ sp ~ named_column_list ~ emit_suffix }
emit_suffix = { (sp ~ "|>" ~ sp ~ reference_list)? }
planNode = {
// Specialized read relations must precede read_relation: all start with
// "Read", and PEG tries alternatives in order — the longer prefixes
// must be attempted first.
extension_read_relation
| virtual_read_relation
| read_relation
| filter_relation
| project_relation
| aggregate_relation
| sort_relation
| fetch_relation
| join_relation
| set_relation
| cross_relation
| extension_relation
| addendum
}
// 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 ~ output ~ "]" }
// ExtensionTable read: Read:Extension[columns], with detail in a required + Ext addendum.
extension_read_relation = { "Read:Extension" ~ "[" ~ named_column_list ~ "]" }
// -- Multi-line relation layout --
// A relation may be written across several lines, with each continuation line
// indented and prefixed by a `- ` marker at defined points in the relation grammar.
//
// TODO: reuse these for other bracketed relations (Project, Aggregate, ...).
// A continuation line transition: newline, followed by spaces and "- "
relation_line_cont = _{ sp ~ NEWLINE ~ sp ~ "- " ~ sp }
// Continuation allowed after relation opening ("["), between arguments (after ","),
// or before the columns (before "=>")
relation_open = _{ "[" ~ relation_line_cont? }
relation_comma = _{ sp ~ "," ~ (relation_line_cont | sp) }
relation_arrow = _{ (relation_line_cont | sp) ~ "=>" ~ sp }
// VirtualTable read: Read:Virtual[rows => columns] or Read:Virtual[_, filter=... => columns]
// Rows are parenthesized tuples; _ means empty (no rows). May also be written
// across multiple lines using the relation layout rules above:
// Read:Virtual[
// - (1, 'alice'),
// - (2, 'bob')
// - => id:i64, name:string]
// The trailing `relation_end` forces the rule to consume the whole (possibly
// multi-line) input, so a stray continuation line after `]` is a parse error
// rather than silently dropped. It is silent so the `EOI` token does not show
// up among the relation's child pairs.
virtual_read_relation = { "Read:Virtual" ~ relation_open ~ virtual_read_rows ~ (relation_comma ~ virtual_read_filter)? ~ relation_arrow ~ named_column_list ~ "]" ~ relation_end }
relation_end = _{ sp ~ EOI }
virtual_read_rows = { virtual_row_list | empty }
virtual_read_filter = { "filter" ~ sp ~ "=" ~ sp ~ expression }
virtual_row_list = { virtual_row ~ (relation_comma ~ 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)* }
// TODO: Add support for filter invocation, etc.
aggregate_output = { (expression ~ (sp ~ "," ~ sp ~ expression)*)? }
// 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), post_filter=gt($3, 0) => $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_post_join_filter = { "post_filter" ~ sp ~ "=" ~ sp ~ expression }
join_relation = { "Join" ~ "[" ~ join_type ~ sp ~ "," ~ sp ~ expression ~ (sp ~ "," ~ sp ~ join_post_join_filter)? ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
// SetRel: Set[&UnionAll => $0, $1, $2]
// Note: Longer prefixes must come before shorter ones (e.g., "&IntersectionMultisetAll"
// before "&IntersectionMultiset") so that the parser doesn't stop at the shorter match.
set_op = { "&IntersectionMultisetAll" | "&IntersectionMultiset" | "&IntersectionPrimary" | "&MinusPrimaryAll" | "&MinusPrimary" | "&MinusMultiset" | "&UnionAll" | "&UnionDistinct" }
set_relation = { "Set" ~ "[" ~ set_op ~ sp ~ "=>" ~ sp ~ reference_list ~ "]" }
// CrossRel: Cross[$0, $1, $2, $3] (Cartesian product of left and right; no args)
cross_relation = { "Cross" ~ "[" ~ 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)* }
// Untyped scalar extension literals render independently of expression literal
// verbosity. Typed literals (for example, 2:i16 or '2024-01-01':date) fall
// through to expression parsing so their Substrait type information is
// preserved.
untyped_literal = { (float | integer | boolean | string_literal) ~ !(":") }
// 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 | untyped_literal | reference | 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 }
// Relation addenda: metadata/detail lines attached to a relation.
// Format: + Enh:Name[args], + Opt:Name[args], or + Ext:Name[args]
// Examples:
// - + Enh:PartitionHint[&HASH, count=8]
// - + Opt:SomeOptimization[threshold=100, mode='fast']
// - + Ext:BlobStoreRead['path/to/file']
addendum = { "+" ~ sp ~ addendum_type ~ ":" ~ name ~ "[" ~ arguments ~ "]" }
addendum_type = { "Enh" | "Opt" | "Ext" }