substrait-explain 0.9.0

# Substrait Text Format Grammar

This document describes the grammar for the human-readable Substrait text format used by `substrait-explain`. This format allows you to write Substrait query plans in a concise, readable text format that can be parsed back into full Substrait protobuf plans.

## Overview

The Substrait text format consists of three sections:

1. **Version Section** (optional) - Declares the Substrait version of the plan
2. **Extensions Section** (optional) - Defines URNs and function/type extensions
3. **Plan Section** - Contains the actual query plan with relations

## Design Principles

This section describes the syntax and semantics principles of the text-format
DSL. For the repository-level design philosophy, compatibility expectations, and
format change guidance, see [`DESIGN.md`](DESIGN.md).

The grammar is designed around several concrete choices that make it practical and consistent:

### 1. Single-Line, Structured Relations

All relations follow the same structure: `Name[arguments => columns]`

- **Name**: The relation type (Read, Filter, Project, etc.)
- **Arguments**: Relation-specific: input expressions, field references, or function calls
  - Arguments follow a regular pattern (tuple, input expression, etc.) or combination, and should map directly to Substrait proto fields. Uses tuples for compound arguments, with literals, expressions, and enums for values.
- **Arrow**: `=>` separates arguments from output columns
- **Columns**: Output column names and types

Every relation fits on one line with indentation showing hierarchy. This uniform pattern makes it easy to parse any relation, understand input/output structure, and add new relation types.

### 2. SQL-Like References, Literals, and Enums

- Field references: `$0`, `$1`, etc.
- Types are shown inline with literals and column names: `42:i64`, `'hello':string`
- Nullability is explicit: `string?` for nullable, `string` for non-nullable

This prevents ambiguity and makes plans self-documenting while being familiar to SQL developers.

### 3. Extension Support and Structured Syntax

- Extensions section defines URNs and function/type mappings.
- Function calls can include anchors: `add#10@1($0, $1)`.
- Clear structural boundaries: `[]` for relations, `<>` for types, `()` for functions.
- Maintains full Substrait compatibility while keeping the text format readable and parseable.

### 4. Hierarchical Organization

- Section headers (`===`) separate major components.
- 2-space indentation shows query plan hierarchy.
- Consistent formatting across all document elements.

The format maps directly to Substrait protobuf messages, with relations, expressions, types, and extensions corresponding to their respective protobuf structures.

## Grammar Notation

This document uses **PEG (Parsing Expression Grammar)** notation:

- **`"text"`** - Literal text
- **`element?`** - Optional element
- **`element*`** - Zero or more repetitions
- **`element+`** - One or more repetitions
- **`element1 / element2`** - Choice (try element1 first)
  - _Implementation Note: Pest uses `|` instead of `/`_
- **`element1 element2`** - Sequence
  - _Implementation Note: Pest uses `~` for explicit concatenation_

## Basic Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  ## 10 @  1: add
  ## 11 @  1: multiply

=== Plan
Root[result]
  Project[$0, $1, add($0, $1):i64]
    Read[orders => quantity:i32?, price:i64]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

## Document Structure

A Substrait text format document consists of two main sections with specific formatting rules.

### Sections

The document uses `===` headers to separate major sections:

- **`=== Version`** - Declares the plan's Substrait version (optional)
- **`=== Extensions`** - Defines URNs and function/type mappings (optional)
- **`=== Plan`** - Contains the actual query plan (required)

When present, the sections appear in this order, mirroring the field order of
the Substrait `Plan` protobuf.

#### Version format

```text
=== Version major.minor.patch
  producer: producer string
  git_hash: git hash
```

The header carries the version number as `major.minor.patch` (three
non-negative integers). The indented `producer:` and `git_hash:` lines are
optional and may appear in either order beneath the header.

The `=== Version` section as a whole is optional; a document with no version
section is valid and denotes a plan without a declared version.

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Version 0.55.0
  producer: my-optimizer
=== Plan
Root[result]
  Read[orders => quantity:i32?]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# let version = plan.version.unwrap();
# assert_eq!(version.minor_number, 55);
# assert_eq!(version.producer, "my-optimizer");
```

#### Extension format

```text
=== Extensions
URNs:
  @  urn_anchor: urn
  …
Functions:
  ##  anchor @  urn_anchor: name
  …
Types:
  ##  anchor @  urn_anchor: name
  …
Type Variations:
  ##  anchor @  urn_anchor: name
  …
```

Where `anchor` and `urn_anchor` are integers, `urn` is a text URN, and function, type, and type variation names are identifiers or quoted text.

### Plan Hierarchy and Indentation

Relations use indentation to show the query plan hierarchy:

- **Root level**: No indentation (typically `Root` relation)
- **Child relations**: Indented with 2 spaces per level
- **Each relation**: On its own line with format `Name[arguments => columns]`

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  ## 10 @  1: gt

=== Plan
Root[result]                   // Level 0 (no indentation)
  Project[$0, $1]              // Level 1 (2 spaces)
    Filter[gt($0, 10):boolean => $0]   // Level 2 (4 spaces)
      Read[data => a:i64]      // Level 3 (6 spaces)
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

## Basic Terminals

### Character Classes

- **`letter`**` := [a-zA-Z]` - Alphabetic characters
- **`digit`**` := [0-9]` - Numeric digits

### `name` and `identifier`

- **`name`**` := identifier / quoted_name`
  - Used for column names, function names, etc. It can be unquoted if it's a valid identifier, or using "double quotes" if special characters are required (much like SQL)
  - Examples: `function_name`, `"quoted name"`
- **`identifier`**` := letter (letter / digit / "_")*`
  - Used for columns, function names, etc. that are proper identifiers.
  - Examples: `table_name`, `my_function`, `col1`
- **`quoted_name`**` := '"' ("\\" . / !'"' .)* '"'`
  - Used for columns, function names, etc. that are not valid as identifiers, and thus need quoting.
  - Examples: `"function name"`, `"table.name"`, `"table\.name"`, `"function \"with some\nescapes\""`

### `enum`

Enum fields in arguments are represented as &-prefixed variants (e.g., `&AscNullsFirst`), matching the Substrait proto definition. This applies to all enum fields in relation arguments.

#### Syntax

`enum := "&" identifier`

#### Examples

- `&AscNullsFirst`, `&AscNullsLast`, `&DescNullsFirst`, `&DescNullsLast` - sort directions

### Scalar values

These are basic terminals used in [expressions](#expression-literals)
and [arguments](#arguments).

- **`integer`**` := "-"? digit+`
  - Examples: `42`, `-10`, `0`
- **`float`**` := "-"? digit+ "." digit+`
  - Examples: `3.14`, `-2.5`, `1.0`
- **`boolean`**` := "true" / "false"`
  - Examples: `true`, `false`
- **`string`**` := "'" ("\\" . / !"'" .)* "'"`
  - Examples: `'hello'`, `'table name'`, `'C:\path\to\file'`, `'line1\nline2'`, `'quote\'s here'`
- **`null`**` := "null"`
  - Examples: `null:i64?`, `null:string?`, `null:date?`
  - A type annotation is required for `null`
- **`typed_literal`**` := string ":" type`
  - String literals with type annotations for non-primitive types
  - Examples: `'2023-01-01':date`, `'2023-12-25T14:30:45.123':timestamp`, `'2023-01-01T12:00:00.123456789':precisiontimestamp<9>`, `'14:30:45.123456':precisiontime<6>`, `'5d 3s':interval_day<0>`

All basic literal types (`integer`, `float`, `boolean`, and `string`) are supported, plus `date`, `time`, `timestamp`, `precisiontime`, `precisiontimestamp`, `precisiontimestamptz`, `interval_day`, and typed null literals. Other Substrait literal types (e.g., `interval_year`, `decimal`, `uuid`) are not yet implemented. The deprecated `timestamp_tz` literal is also not yet implemented; use `precisiontimestamptz<6>` instead.

#### `interval_day` Typed Literals

`interval_day` string literals represent Substrait `IntervalDayToSecond` values.
The string holds up to three duration terms:

```text
interval_day_literal := (duration_days (" " duration_seconds)? (" " duration_subseconds)?)
                      / (duration_seconds (" " duration_subseconds)?)
                      / duration_subseconds
duration_days        := "-"? digit+ "d"
duration_seconds     := "-"? digit+ "s"
duration_subseconds  := "-"? digit+ subsecond_unit
subsecond_unit       := "ms" / "us" / "ns" / "ps"
```

Each term is optional, but at least one is required, and terms appear in
descending order: days, then seconds, then sub-seconds. Terms are separated by
exactly one space, with no leading or trailing whitespace. Each term carries its
own optional sign, matching the separate Substrait fields for days, seconds, and
sub-seconds.

Sub-second precision comes from the type ascription, not the string, so an
`interval_day` literal always names its precision: `interval_day<precision>`.
A literal's precision must be one of 0 (seconds), 3 (milliseconds), 6
(microseconds), 9 (nanoseconds), or 12 (picoseconds) - the precisions that have
a unit to write a value in. Unlike `precisiontimestamp` and `precisiontime`
literals, `interval_day` accepts 12: sub-seconds are stored as a plain integer
count rather than going through `chrono`.

A sub-second term's unit must agree with the ascribed precision - `ms` is
precision 3, `us` is 6, `ns` is 9, and `ps` is 12 - so there is only one place a
value's precision can come from.

Examples:

- `'5d':interval_day<0>`
- `'4d 5s':interval_day<6>`
- `'123456789ns':interval_day<9>`
- `'5d 3s 100ms':interval_day<3>`
- `'-5d 3s':interval_day<0>`
- `'5d':interval_day?<6>` (nullable)

Only non-zero components are written on output, since precision travels in the
type suffix: an interval of 5 days at nanosecond precision is `'5d':interval_day<9>`,
not `'5d 0ns':interval_day<9>`. An all-zero interval is written `'0s'`.

## Types

The type syntax in this grammar follows the [standard Substrait type definition syntax](https://substrait.io/types/type_parsing/), with extensions to support anchors and URN references for user-defined types.

### Type Syntax Overview

All types follow this general pattern:

```text
type := ("u!")? identifier anchor? urn_anchor? nullability? parameters?
```

Where:

- **`identifier`** - The type name (case-insensitive, lowercase preferred), e.g. `geo_point` or `my_type`. `u!my_type` syntax is accepted, but not recommended; the `u!` will be dropped - e.g. both `u!json` and `json` refer to the same extension.
- **`anchor`**` := "#" integer` - Extension anchor (e.g., `#10`)
- **`urn_anchor`**` := "@" integer` - URN anchor (e.g., `@1`)
- **`nullability`**` := "?"` - Optional nullability indicator (defaults to non-nullable)
- **`parameters`**` := "<" (param ("," param)*)? ">"` - Optional type parameters
- **`param`**` := type / integer / name` - Type parameter (type, integer, or name)

### Simple Types

Simple types are the basic Substrait types with optional nullability.

#### Syntax

`simple_type_name nullability?`

#### Simple Type Names

From [official Substrait grammar](https://raw.githubusercontent.com/substrait-io/substrait/refs/heads/main/grammar/SubstraitType.g4), `simple_type_name` can be any of these literal strings:

- `boolean`, `i8`, `i16`, `i32`, `i64`
- `fp32`, `fp64`
- `string`, `binary`
- `timestamp`, `timestamp_tz`, `date`, `time`
- `interval_year`, `uuid`

`interval_day` is not in this list: it is parameterized by sub-second precision,
so it is written as a compound type (see below).

#### Nullability

- `?` - nullable
- `⁉` - unspecified nullability (not generally valid)
- (nothing) - non-nullable

##### Examples:

```rust
# use substrait_explain::Parser;

let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1, $2, $3]
    Read[data => int_field:i64, string_field:string?, created_at:timestamp?, user_id:uuid]
"#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Compound Types

Compound types follow the same syntax as standard Substrait parameterized types.

#### Precision Time And Timestamp Types

Precision time and timestamp types put the nullability marker before the precision parameter.

#### Syntax

```text
precision_time_type         := "precisiontime" nullability? "<" integer ">"
precision_timestamp_type    := "precisiontimestamp" nullability? "<" integer ">"
precision_timestamp_tz_type := "precisiontimestamptz" nullability? "<" integer ">"
```

The precision parameter follows the Substrait unit convention: `0` means
seconds, `3` milliseconds, `6` microseconds, `9` nanoseconds, and `12`
picoseconds. Two different subsets apply:

- _Types_ accept the full Substrait range, any precision from `0` through `12`.
- _Literals_ accept only `0`, `3`, `6`, and `9`.

The literal restriction is a limitation of this implementation, not of
Substrait, which supports every precision from 0 to 12.

Literals stop at `9` because chrono (the underlying date/time library) has no
sub-nanosecond resolution, so precision-12 literals cannot be parsed.
Textifying a precision-12 value from a protobuf plan is still supported: the
_value_ is truncated to nanosecond resolution and a truncation diagnostic is
emitted, but the declared _type_ is preserved as `<12>` (truncating the value
does not silently rewrite its type).

#### Examples

```text
precisiontime<6>
precisiontime?<6>
precisiontimestamp<9>
precisiontimestamp?<9>
precisiontimestamptz<3>
precisiontimestamptz?<3>
```

`interval_day` takes an integer sub-second precision from 0 to 12, e.g.
`interval_day<9>`, `interval_day?<0>`. The parameter is required, as it is for
every other parameterized type. Writing an `interval_day` *literal* additionally
requires a precision that has a unit to write values in; see
[`interval_day` Typed Literals](#interval_day-typed-literals).

#### Examples

// TODO: This example uses `map` type, which is not yet implemented in the parser.

```text
use substrait_explain::Parser;

let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1, $2]
    Read[data => list_field:list<i64>, map_field:map<string, i64>, struct_field:struct<i64, string?>]
"#;

let plan = Parser::parse(plan_text).unwrap();
assert_eq!(plan.relations.len(), 1);
```

### User-Defined Types

User-defined types extend the standard Substrait UDT syntax to support anchors and URN references.

#### Syntax

`("u!")? identifier anchor? urn_anchor? nullability? parameters?`

#### Key differences from standard Substrait

- Adds optional `anchor` and `urn_anchor` for extension references
- The `u!` prefix is accepted in type declarations but normalized at storage time, so `u!json` and `json` in a declaration refer to the same type. It is an error to use `u!` on function or type-variation declarations.
- In plan references both `u!json` and `json` are accepted and resolve to the same anchor. The canonical output always uses the bare name.

#### Examples

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://example.com/types
  @  2: https://example.com/functions
Types:
  ##  8 @  1: point
  ##  9 @  1: custom_type
Functions:
  ## 10 @  2: add

=== Plan
Root[result]
  Project[$0, $1, $2]
    Read[data => point_field:point#8@1?<i8>, custom_field:custom_type#9, prefixed_field:u!custom_type]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

## Expressions

#### Syntax

`expression := function_call / reference / expression_literal / cast_expression / if_then`

### Examples

```text
add($3, 10):i64              // Simple function call with required output type
add#10@2($3, 10):i64         // Function call with anchors and output type
```

### Expression Literals

An `expression_literal` represents a Substrait `Literal` expression and
therefore always has a type. The text format may infer the conventional type
for a non-null scalar when its type ascription is omitted:

```text
expression_literal := (float / integer / boolean / string) (":" type)?
                    / "null" ":" type
```

- An unannotated `integer` has type `i64`; an annotation can select another
  integer type, as in `5:i16`.
- An unannotated `float` has type `fp64`; an annotation can select another
  floating-point type.
- A `boolean` may only have boolean type.
- An unannotated `string` has type `string`. String values may be annotated as
  other supported literal types, such as `'2023-01-01':date`.
- A `null` literal requires an explicit type, such as `null:i64?`,
  `null:string?`, or `null:date?`.

#### Examples

```text
null:i64?
null:string?
null:date?
'2023-01-01':date
'2023-12-25T14:30:45.123':timestamp
'2023-01-01T12:00:00.123456789':precisiontimestamp<9>
'14:30:45.123456':precisiontime<6>
```

The supported non-primitive literal types are `date`, `time`, `timestamp`,
`precisiontime`, `precisiontimestamp`, and `precisiontimestamptz`. Other
Substrait literal types, including `interval_year`, `decimal`, and `uuid`, are
not yet implemented. The deprecated `timestamp_tz` literal is also not
implemented; use `precisiontimestamptz<6>` instead.

### Field References

Currently, only references to fields in the Relations' input are supported.

#### Syntax

`reference := "$" integer`

#### Examples

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1, $42]
    Read[data => field0:i64, field1:string, field42:boolean]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Function Calls

#### Syntax

`function_call := function_signature anchor? urn_anchor? "(" (expression ("," expression)*)? ")" ":" type`

where `function_signature` is the function base name with an optional colon-delimited type-signature suffix:

```text
function_signature := identifier (":" argument_signature?)?
argument_signature := short_arg_type ("_" short_arg_type)*
short_arg_type     := "u!" short_arg_name | short_arg_name
short_arg_name     := ASCII_ALPHA ASCII_ALPHANUMERIC*
```

Examples of function signatures: `add`, `equal:any_any`, `count:` (empty signature), `json_extract_path:u!json_str`, `bar:u!arg_u!arg`.

#### Components

- `function_signature` - function name with optional signature suffix (see above)
- `anchor` - optional anchor (e.g., `#10`)
- `urn_anchor` - optional URN anchor (e.g., `@1`)
- `expression` - as above
- `type` - required output type

#### Function Name Resolution

Within the plan, a function name has three parts: a `base` name (e.g. `abs`), a type signature (prefixed with a colon, e.g. `:i64`), and anchor (prefixed with `#`, e.g. `#4`).

Both type signature and anchor are separably optional if the reference is unambiguous; either or both may be required to make the reference unambiguous. A function name (base, signature if present, and anchor if present) must map to exactly one function named in the `Extensions` section.

Where unambiguous, signature and anchor may both be left off, used separately, or together for completeness (`abs:i64#4($0):fp64`).

#### Examples

```text
// Simple: resolves if there is exactly one function named `add`
add($0, $1):i64
// Signature: resolves only if exactly one function named `add` is registered,
// with type signature `:i64_i64`
add:i64_i64($0, $1):i64
// Anchor: resolves if anchor 1 exists with base name `add`
add#1($0, $1):i64
// Anchor + full name: resolves if anchor 1 exists with name `add` and
// type signature `i64_i64`
add:i64_i64#1($0, $1):i64
// Simple: resolves if there is exactly one function named `count`
count():i64
// Signature: resolves if "count:" is registered exactly once with
// type signature "" (zero arguments)
count:():i64
```

### Cast Expressions

A cast converts an expression to a target type. Its optional failure behavior
controls what happens when the value cannot be converted.

#### Syntax

```text
cast_expression := "(" expression ")" "::" cast_failure_behavior? type
cast_failure_behavior := "?" / "!"
```

Where:

- no failure prefix leaves the behavior unspecified
- `?` returns null when the cast fails
- `!` raises an error when the cast fails

#### Examples

```text
(78:i32)::i16
($0)::?i16
($0)::!i16
```

### Aggregate Measures

Aggregate measures are used in the output of Aggregate relations to compute aggregates. An aggregate measure is written as a plain `function_call` (see [Function Calls section](#function-calls)) in the output position of an Aggregate relation - the syntax is identical, e.g. `sum($2):i64`, `count($1):i64`, `avg($3):fp64`.

This syntax only captures a measure's `function_reference`, `arguments`, and `output_type`. The Substrait `Measure` message also carries a `filter` (a per-measure filter expression, separate from the aggregate function) and the `AggregateFunction` itself has `invocation` (e.g. `DISTINCT`), `phase`, and `sorts` (for ordered aggregates), which are currently unsupported. Parsing always produces `invocation: UNSPECIFIED`, `phase: UNSPECIFIED`, no `sorts`, and no `filter`, regardless of what the original plan contained.

### IfThen

An IfThen expression is a conditional function or logical operator that evaluates to a boolean.

#### Syntax

`if_then := "if_then(" (if_clause ",")+ "_ ->" expression ")"`

`if_clause := expression "->" expression`

#### Examples

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[status]
  Fetch[limit=10, offset=0 => ]
    Project[if_then(true -> $0, false -> $1, _ -> $2)]
      Read[events.logs => status:string?]
#  "#;
#
#  let plan = Parser::parse(plan_text).unwrap();
#  assert_eq!(plan.relations.len(), 1);
```

## Relations

Relations represent the operations in a query plan. Each relation is displayed on a single line with indentation showing the hierarchy.

### General Relation Grammar

All relations follow this general pattern:

#### Syntax

```text
relation := name "[" (relation_arguments ("=>" columns)?)? "]"
relation_arguments := (arguments ("," named_arguments)?) / named_arguments
columns := name ("," name)* / reference_list
```

Where:

- **`name`**: The type of operation (`Read`, `Filter`, `Project`, etc.)
- **`relation_arguments`**: Positional arguments, named arguments, or both (optional)
- **`arguments`**: Positional expressions, field references, enums, tuples, or parameter literals
- **`named_arguments`**: Named arguments, following any positional arguments
- **`=>`**: Separator before an optional output clause
- **`columns`**: Output column names and types, or field references for pass-through
- **`reference_list := reference ("," reference)*`**: comma-separated list of field references

#### Example

```text
RelationName[arguments, named_arguments => columns]
```

#### Special cases

- **Root relation**: Only specifies output column names, no arguments or `=>` separator

The arguments allowed and format of output columns varies by relation type.

#### Emit

Every relation this crate parses carries an explicit `RelCommon.emit_kind`:
`Direct` when the columns pass through unchanged, `Emit` when the text gives a
remap. `emit_kind` is a protobuf `oneof`, so leaving it unset has no default a
consumer can rely on — it would have to infer `Direct`.

### Arguments

Arguments in relations can be parameter literals, expressions, enums, or tuples thereof.

#### Syntax

```text
arguments := argument ("," argument)*
named_arguments := name "=" argument ("," name "=" argument)*
argument := enum / reference / parameter_literal / expression / tuple
parameter_literal := float / integer / boolean / string / null
tuple := "(" ")"                                        // 0-tuple
       / "(" argument "," ")"                           // 1-tuple (trailing comma required)
       / "(" argument ("," argument)+ ","? ")"          // 2+-tuple (trailing comma optional)
```

A `parameter_literal` supplies a scalar value directly to a relation parameter
and never has a type ascription. An `expression_literal` is part of an
expression and therefore has a Substrait type. The relation-specific grammar
determines which interpretation applies.

Tuples follow the Python/Rust trailing-comma convention to disambiguate from parenthesised expressions: `(x)` is a parenthesised expression, not a tuple. A trailing comma is required to form a 1-element tuple: `(x,)`. For 2+ elements the trailing comma is optional: `(x, y)` and `(x, y,)` are equivalent.

#### Examples

- Simple arguments: `$0`, `42`, `'hello'`, `&AscNullsFirst`
- 0-tuple: `()`
- 1-tuple: `(&HASH,)` — trailing comma required
- 2+-tuple: `($0, &AscNullsFirst)`, `(&HASH, &RANGE,)`
- Named arguments: `limit=10`, `offset=5`

### Root Relation

#### Syntax

`"Root" "[" (name ("," name)*)? "]"`

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[c, d]           // root with output columns c and d
  Project[$0, $1]
    Read[data => a:i64, b:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Read Relation

#### Syntax

```text
read_relation := "Read" "[" table_name output "]"
output := implicit_output / direct_output
implicit_output := "=>" named_column_list
direct_output := "+>" named_column_list ("|>" reference_list)?
```

#### Components

- `table_name := name ("." name)*` - table name, optionally qualified with schema/database
- `named_column := name ":" type` - column name with type annotation
- `named_column_list := (named_column ("," named_column)*)?` - the list of columns and their types to be read from the table `table_name`.
  - `=>` is used to mean implicit column ordering; for `Read`, this translates to `Direct` column ordering.
  - `+>` with no `|>` also means `Direct`, and is accepted as an equivalent spelling of `=>`. The canonical form is `=>`.
  - When used with `+> … |>`, the `named_column`s are in the expected order of the table, and the emit order is a Remap specified by `reference_list`.

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1]
    Read[schema.table => a:i64, b:string?]
Root[result2]
  Project[$0, $1]
    Read[orders => quantity:i32?, price:i64]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 2);
```
`+>` with no `|>` is accepted as an equivalent of `=>`, and prints back as `=>`:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[a, b]
  Read[my_table +> a:i64, b:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

Use `+> ... |>` to specify an Emit / output ordering different from the table's base schema:
only some fields should flow downstream:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[b, a]
  Read[my_table +> a:i64, b:string, c:i64 |> $1, $0]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### VirtualTable Read Relation

A VirtualTable read embeds inline data directly in the plan, similar to SQL's `VALUES` clause. Instead of referencing a catalog table, the data rows are specified as part of the relation.

The `Read:Virtual` relation uses the same `ReadRel` protobuf message with `ReadType::VirtualTable`, where each row is a `nested::Struct` containing expressions.

#### Syntax

`"Read:Virtual" "[" virtual_read_rows ("," "filter" "=" expression)? "=>" named_column_list "]"`

Where `virtual_read_rows := virtual_row ("," virtual_row)* / "_"`, and
`virtual_row := "(" (expression ("," expression)*)? ")"` — a parenthesized
tuple of expressions forming one row. Rows may be empty (`()`) for zero-column
tables. For an empty virtual table, write `_` in place of the entire row list,
e.g. `Read:Virtual[_ => id:i64]` for zero rows.

#### Components

- `virtual_row` - parenthesized tuple of expressions, one per row; `()` for zero-column rows
- `expression` - any expression (literal, field reference, function call)
- `filter` - optional `ReadRel.filter` expression, with field references over the virtual table output schema
- `named_column_list` - output column names with type annotations

#### Examples

Inline form with two rows:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[id, name]
  Read:Virtual[(1, 'alice'), (2, 'bob') => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

Empty virtual table (no rows):

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[id, name]
  Read:Virtual[_ => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

Inline form with a `ReadRel.filter`:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
Functions:
  ## 10 @  1: gt

=== Plan
Root[id, name]
  Read:Virtual[(1, 'alice'), (2, 'bob'), filter=gt($0, 1:i64):boolean => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

#### Multi-line form

For readability, a `Read:Virtual` with many rows may be written across several
lines. Each continuation line is indented one level deeper than the relation and
prefixed with a `- ` marker. Continuations are allowed after the opening `[`,
after each row or filter separator (`,`), and before `=>`:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
Functions:
  ## 10 @  1: gt

=== Plan
Root[id, name]
  Read:Virtual[
    - (1, 'alice'),
    - (2, 'bob'),
    - filter=gt($0, 1:i64):boolean
    - => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

The multi-line form is purely a layout convenience: it parses to exactly the
same plan as the inline form above. The standard output may use inline or multi-line form depending on the length of the `VirtualTable`.

### `ExtensionTable` Read Relation

An `ExtensionTable` read uses `ReadRel` with `ReadType::ExtensionTable`. The relation header carries the read output schema, while a required `+ Ext:` addendum carries the custom table detail payload.

#### Syntax

```text
extension_table_read_relation := "Read:Extension" "[" named_column_list "]"
extension_table_detail        := "+" "Ext" ":" name "[" (empty / extension_args)? "]"
```

The `+ Ext:` line is indented one level deeper than the `Read:Extension` line. It is required, and addendum lines must appear before any child relations. Canonical formatting writes `+ Ext:` first, followed by `+ Enh:` and `+ Opt:` lines when present.

#### Components

- `named_column_list` - output column names with type annotations, stored in `ReadRel.base_schema`
- `name` - the extension name registered with `ExtensionRegistry`
- `extension_args` - positional and/or named arguments encoded into the `ExtensionTable.detail: Any`

#### Example

```rust
# use substrait_explain::extensions::examples;
# use substrait_explain::format_with_registry;
# use substrait_explain::Parser;
#
# let registry = examples::registry();
# let parser = Parser::new().with_extension_registry(registry.clone());
#
# let plan_text = r#"
=== Plan
Root[id, payload]
  Read:Extension[id:i64, payload:string]
    + Ext:BlobStoreRead['path/to/file', limit=100, include_archived=true]
# "#;
#
# let plan = parser.parse_plan(plan_text).unwrap();
# let (formatted, errors) = format_with_registry(&plan, &Default::default(), &registry);
# assert!(errors.is_empty());
# assert_eq!(formatted.trim(), plan_text.trim());
```

Relation-level advanced extensions can still be attached to the same read relation:

```rust
# use substrait_explain::extensions::examples;
# use substrait_explain::format_with_registry;
# use substrait_explain::Parser;
#
# let registry = examples::registry();
# let parser = Parser::new().with_extension_registry(registry.clone());
#
# let plan_text = r#"
=== Plan
Root[id]
  Read:Extension[id:i64]
    + Ext:BlobStoreRead['path/to/file']
    + Enh:PartitionHint[&HASH, count=8]
    + Opt:PlanHint[hint='parallel']
# "#;
#
# let plan = parser.parse_plan(plan_text).unwrap();
# let (formatted, errors) = format_with_registry(&plan, &Default::default(), &registry);
# assert!(errors.is_empty());
# assert_eq!(formatted.trim(), plan_text.trim());
```

### Filter Relation

#### Syntax

`"Filter" "[" expression "=>" reference_list "]"`

#### Components

- `expression` - boolean expression for filtering
- `reference_list` - field references to pass through

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  ## 10 @  1: gt

=== Plan
Root[result]
  Filter[gt($2, 100):boolean => $0, $1, $2]
    Project[$0, $1, $2]
      Read[data => a:i64, b:string, c:i32]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Project Relation

#### Syntax

`"Project" "[" (expression ("," expression)*)? "]"`

#### Components

- `expression` - field reference, function call, or literal (see Expressions section)

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[result]
  Project[$1, 42]                    // project field 1 and literal 42
    Read[data => a:i64, b:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Aggregate Relation

#### Syntax

`"Aggregate" "[" grouping_sets "=>" aggregate_output "]"`

#### Components

- `grouping_sets := grouping_set_list / expression_list` - can be a list of grouping sets (each parenthesized), or a single unparenthesized list for the common, single-set case
- `grouping_set_list := grouping_set ("," grouping_set)*`
- `grouping_set := "(" expression_list ")" / "_"` - a grouping set can be (1) a list of expressions, or (2) `_`, the standard we use for empty lists
- `aggregate_output := expression ("," expression)*` - comma-separated list of output items
- Each output item is either an aggregate function call (which becomes a new measure), or an expression that must match one of the `grouping_sets` expressions by value - since an Aggregate relation's output schema is always exactly `grouping_expressions + measures`. See [Aggregate Measures section](#aggregate-measures)

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_aggregate.yaml
Functions:
  ## 10 @  1: sum
  ## 11 @  1: count

=== Plan
Root[result]
  Aggregate[($0), ($0, $1) => $0, $1, sum($2):i64, count($2):i64]           // Group by field 0, and ($0, $1)
    Read[orders => category:string, region:string?,  amount:i64]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Sort Relation

The Sort relation specifies sort expressions and directions for ordering the input:

Sort[($0, &AscNullsFirst), (lower($1):string, &DescNullsLast) => $0, $1]

#### Syntax

```text
sort_relation := "Sort" "[" sort_fields "=>" reference_list "]"
sort_fields := sort_field ("," sort_field)*
sort_field := "(" expression "," sort_direction ")"
sort_direction := "&AscNullsFirst" / "&AscNullsLast" / "&DescNullsFirst" / "&DescNullsLast"
```

#### Components

- Each sort field is a tuple: `(expression, sort_direction)`
- Sort directions follow the general `enum` syntax and specify null handling
- `reference_list` - comma-separated list of field references to pass through

### Fetch Relation

A Fetch relation limits or offsets rows from its input.

#### Syntax

```text
fetch_relation := "Fetch" "[" fetch_args "=>" reference_list "]"
fetch_args := fetch_arg ("," fetch_arg)* / "_"
fetch_arg := ("limit" / "offset") "=" (integer / expression)
```

#### Components

- `limit` - maximum number of rows to return
- `offset` - number of rows to skip
- `_` - no limit or offset
- `reference_list` - fields to pass through, optionally reordered

`limit` and `offset` may appear in either order, but no more than once each. A
bare integer is a parameter literal and must be non-negative; other values are
expressions.

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[id, name]
  Fetch[limit=10, offset=5 => $0, $1]
    Read[records => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Join Relation

#### Syntax

```text
"Join" "[" join_type "," expression ("," "post_filter" "=" expression)? "=>" reference_list "]"
```

#### Components

- `join_type` - Join type enum with `&` prefix (e.g., `&Inner`, `&Left`, `&Right`, `&Outer`)
- `expression` - Join condition (boolean expression relating left and right inputs), with field references over input order
- `post_filter` - Optional post-join filter expression, applied after join matching, with field references over direct output order
- `reference_list` - comma-separated list of field references for output columns, with field references over direct output order

#### Field Reference Mapping

For join conditions, field references map to the combined schema of left and
right inputs:

- `$0`, `$1`, ... refer to left input fields
- `$n`, `$n+1`, ... refer to right input fields (where n = number of left fields)

For `post_filter` and `reference_list`, field references map to the join's
direct output order:

- inner, left, right, and outer joins output left fields followed by right fields
- left semi, left anti, and left single joins output left fields only
- right semi, right anti, and right single joins output right fields only, renumbered from `$0`
- left mark and right mark joins output the retained side's fields followed by the mark column

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
Functions:
  ## 10 @  1: eq

=== Plan
Root[user_orders]
  Join[&Inner, eq($0, $2):boolean => $0, $1, $3]
    Read[users => id:i64, name:string]        // Fields $0, $1
    Read[orders => user_id:i64, amount:i32]   // Fields $2, $3
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Set Relation

#### Syntax

`"Set" "[" set_op "=>" reference_list "]"`

#### Components

- `set_op` - Set operation enum with `&` prefix, using Substrait's protobuf `SetOp`
  variant names directly
- `reference_list` - Comma-separated list of field references for output columns

A `Set` relation combines two or more inputs (written as indented children,
like any other multi-input relation), which must all share the same output
schema. Field references map to that common schema:

- `$0`, `$1`, ... refer to fields of the shared input schema

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[id, name]
  Set[&UnionAll => $0, $1]
    Read[active_users => id:i64, name:string]
    Read[archived_users => id:i64, name:string]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Cross Relation

#### Syntax

`"Cross" "[" reference_list "]"`

#### Components

- `reference_list` - Comma-separated list of field references for output columns

A `Cross` relation is the Cartesian product of its two inputs (written as
indented children). It takes no arguments, so the bracket body is just the
output columns. The output concatenates the left and right inputs, so field
references map to the combined schema:

- `$0`, `$1`, ... refer to left input fields
- `$n`, `$n+1`, ... refer to right input fields (where n = number of left fields)

#### Example

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Plan
Root[id, name, order_id, amount]
  Cross[$0, $1, $2, $3]
    Read[users => id:i64, name:string]
    Read[orders => order_id:i64, amount:i32]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```

### Extension Relations

Extension relations allow custom relation types with user-defined protobuf payloads. They enable integration with custom data sources, optimizations, or specialized operations beyond standard Substrait relations.

#### Types

There are three extension relation types, based on their input cardinality:

- **`ExtensionLeaf`** - No child relations (e.g., custom data sources)
- **`ExtensionSingle`** - Exactly one child relation (e.g., custom transformations)
- **`ExtensionMulti`** - Zero or more child relations (e.g., custom joins)

#### Syntax

```text
extension_relation := extension_type ":" name "[" (empty / extension_args)? ("=>" extension_columns)? "]"
extension_type := "ExtensionLeaf" / "ExtensionSingle" / "ExtensionMulti"
extension_args := (positional_args ("," named_args)?) / named_args
positional_args := extension_arg ("," extension_arg)*
extension_arg := enum / reference / parameter_literal / expression / tuple
named_args := named_arg ("," named_arg)*
named_arg := name "=" extension_arg
extension_columns := (extension_column ("," extension_column)*)?
extension_column := named_column / reference / expression
```

Note: the parser also accepts the `=>` section being omitted entirely (e.g. `ExtensionLeaf:Foo[_]`), treating it as zero output columns. The canonical form always includes `=>`.

#### Components

- **`extension_type`** - One of `ExtensionLeaf`, `ExtensionSingle`, or `ExtensionMulti`
- **`name`** - The extension name (registered with `ExtensionRegistry`)
- **`empty`** (`_`) - Explicitly marks an extension with no arguments
- **`extension_args`** - Positional arguments (enums, references, parameter literals, expressions, or tuples) and/or named arguments (`key=value` pairs); both are optional
- **`extension_columns`** - Output column definitions: named columns (`name:type`), field references (`$0`), or expressions

A `parameter_literal` is a direct scalar parameter. Values such as
`2`, `2.4`, `true`, `'path'`, and `null` therefore render without type
ascriptions, even in verbose output.

A registered extension may interpret a non-null parameter literal as an
expression, in which case it has the default non-nullable type described under
[Expression Literals](#expression-literals). An explicitly ascribed literal such
as `2:i16`, `'2024-01-01':date`, or `null:i64?` is an expression. Field
references, function calls, and casts are also expression values.

#### Examples

```text
=== Plan
Root[result]
  ExtensionSingle:CustomFilter[threshold=100 => $0, $1]
    ExtensionLeaf:ParquetScan[path='data/users.parquet', batch_size=1024 => id:i64, name:string]
```

Extension with positional arguments and no output columns:

```text
ExtensionSingle:VectorNormalize[$0, $1, method='l2' => ]
```

Extension with no arguments:

```text
ExtensionLeaf:EmptySource[_ => ]
```

#### Custom Extension Types

To use custom relation types with protobuf `detail` payloads, register them with an `ExtensionRegistry`. See the API documentation for details on implementing the `Explainable` trait.

## Advanced Extensions

Advanced extensions allow attaching enhancement and optimization metadata to any standard relation via the Substrait `AdvancedExtension` protobuf field.

### Overview

Each relation can carry:

- **At most one** enhancement (`+ Enh:`) — extra semantic metadata attached to a relation
- **Zero or more** optimizations (`+ Opt:`) — hints for the query planner

### Syntax

```text
addendum      := "+" addendum_type ":" name "[" (empty | extension_args)? "]"
addendum_type := "Enh" | "Opt" | "Ext"
```

Where:

- **`addendum_type`** — `Enh` for an enhancement, `Opt` for an optimization, or `Ext` for an `ExtensionTable` detail on `Read:Extension`
- **`name`** — the registered type name (e.g. `PartitionHint`)
- **`extension_args`** — positional and/or named arguments; use `_` for empty

Addendum lines are **indented one level deeper** than the relation they annotate, just like child relations. They MUST appear **before** any child relations. `+ Enh:` and `+ Opt:` lines attach advanced extensions to standard relations. `+ Ext:` lines are only valid under `Read:Extension`; extension relations (`ExtensionLeaf`, `ExtensionSingle`, and `ExtensionMulti`) do not support addenda.

### Argument Syntax

Enhancement and Optimization arguments follow the same rules as extension-relation arguments,
including `parameter_literal` for scalar parameters without type ascriptions.

### Example: Enhancement on a Read Relation

```rust
# use substrait_explain::extensions::examples;
# use substrait_explain::format_with_registry;
# use substrait_explain::Parser;
#
# let registry = examples::registry();
# let parser = Parser::new().with_extension_registry(registry.clone());
#
# let plan_text = r#"
=== Plan
Root[result]
  Read[data => col:i64]
    + Enh:PartitionHint[&HASH, count=8]
# "#;
#
# let plan = parser.parse_plan(plan_text).unwrap();
# let (formatted, errors) = format_with_registry(&plan, &Default::default(), &registry);
# assert!(errors.is_empty());
# assert_eq!(formatted.trim(), plan_text.trim());
```

### Example: Enhancement and Multiple Optimizations

```rust
# use substrait_explain::extensions::examples;
# use substrait_explain::format_with_registry;
# use substrait_explain::Parser;
#
# let registry = examples::registry();
# let parser = Parser::new().with_extension_registry(registry.clone());
#
# let plan_text = r#"
=== Plan
Root[result]
  Read[data => col:i64]
    + Enh:PartitionHint[&HASH, count=4]
    + Opt:PlanHint[hint='use_index']
    + Opt:PlanHint[hint='parallel']
# "#;
#
# let plan = parser.parse_plan(plan_text).unwrap();
# let (formatted, errors) = format_with_registry(&plan, &Default::default(), &registry);
# assert!(errors.is_empty());
# assert_eq!(formatted.trim(), plan_text.trim());
```

### Custom Extension Types

To parse or textify advanced extensions with custom protobuf payloads, register them with an `ExtensionRegistry`:

- **Enhancements**: `registry.register_enhancement::<MyEnhancement>()`
- **Optimizations**: `registry.register_optimization::<MyOptimization>()`

Both require implementing the `Explainable` trait, which provides `from_args` / `to_args` for text-format conversion, and `prost::Message + prost::Name` for protobuf serialization.

#### Parse failure behaviour

If a `+ Enh:` or `+ Opt:` name is **not registered** in the registry at parse time, the parser returns a hard error.

If the registry does not know the type URL at **textify** time (e.g. when formatting a plan received from an external source), the line is still emitted with a failure token and a `FormatError` is collected — the rest of the plan is unaffected.

For example, if a plan contains an enhancement whose type URL is not registered, the textified output replaces the name and arguments with `!{extension}`:

```text
=== Plan
Root[result]
  Read[my.table => col:i64]
    + Enh[!{extension}]
```

The collected `FormatError` carries the full detail:

```rust
# use substrait_explain::extensions::ExtensionError;
# use substrait_explain::FormatError;
# let error =
FormatError::Extension(ExtensionError::NotFound {
    name: "type.googleapis.com/acme.PartitionHint".to_string(),
})
# ;
# assert_eq!(
#     format!("{error}"),
#     "Extension error: Extension 'type.googleapis.com/acme.PartitionHint' not found in registry"
# );
```

The `Read` line and everything else in the plan are textified normally; only the unrecognized enhancement line degrades to the failure token.

## Complete Example

A complete query that joins users and orders tables, calculates total order value, filters for high-value orders, and groups by user to show total revenue per customer:

```rust
# use substrait_explain::Parser;
#
# let plan_text = r#"
=== Extensions
URNs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
  @  2: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
  @  3: https://github.com/substrait-io/substrait/blob/main/extensions/functions_aggregate.yaml
Functions:
  ## 10 @  1: eq
  ## 11 @  1: gt
  ## 12 @  2: multiply
  ## 13 @  3: sum

=== Plan
Root[customer_revenue]
  Aggregate[$0, $1 => $0, $1, sum($3):i64]
    Filter[gt($3, 100):boolean => $0, $1, $2, $3]
      Project[$0, $1, $2, multiply($4, $5):i64]
        Join[&Inner, eq($0, $3):boolean => $0, $1, $2, $3, $4, $5]
          Read[users => id:i64, name:string, region:string]
          Read[orders => user_id:i64, quantity:i32, price:i64]
# "#;
#
# let plan = Parser::parse(plan_text).unwrap();
# assert_eq!(plan.relations.len(), 1);
```