Adopt substrait-packaging's published grammar (substrait-antlr) for type derivations; gap analysis vs. the validator's bespoke grammar

[nielspardon]

Summary

The validator maintains its own ANTLR grammar for the simple-extension type-derivation DSL
(rs/src/parse/extensions/simple/derivations/SubstraitType.g4,
~612 lines), with the generated lexer/parser committed alongside it. Meanwhile,
substrait-io/substrait-packaging now generates and
publishes the spec's grammar as the substrait-antlr crate (from the canonical
substrait/grammar/SubstraitType.g4, ~83 lines), and other libraries already parse extension YAMLs with it.

This issue records a gap analysis comparing the two grammars, so we can decide what (if anything) needs to
land upstream, and then rewrite the validator to consume substrait-antlr instead of carrying a bespoke,
divergent grammar.

Background

While piloting a migration of the validator onto the published substrait-packaging crates
(substrait-prost, substrait-extensions, substrait-antlr), the ANTLR swap failed to compile: the two
grammars are not different versions of the same grammar — they are different grammars for overlapping
languages.

• Validator grammar: a pattern matcher + evaluator. Every type expression does double duty — it both
  matches a function call's actual argument types (capturing bindings like P1/S1 as a side effect) and
  evaluates to a derived output type. Hand-rolled precedence cascade
  (patternOr → patternAnd → … → patternMisc), program/statement/pattern entry rules, ~50 parse-context
  types.
• Upstream grammar (substrait-antlr): a one-directional type-expression / derivation grammar. Left-
  recursive expr with labeled alternatives (#BinaryExpr/#IfExpr/#Ternary), scalarType/
  parameterizedType/typeDef, startRule/typeStatement, 4 parse-context types.

Crucially, most of the validator's matching machinery is resolved during semantic analysis, not parsing,
so it can be layered on top of the upstream parse tree just as well as its own.

Feature delta

Constructs the validator grammar has that upstream lacks — and their real-world usage

Usage was checked across the bundled standard extensions (rs/src/resources/extensions/*.yaml) and the entire
test corpus (tests/).

Validator-only construct	Syntax	Used in stdlib?	Used anywhere in tests?
Type variation suffix	i32[bigoffset]	No	No
Explicit non-nullable / nullable-if	T!, T??pred	No	No
Integer range patterns	1..5, ..5, 5..	No	No
Enum-set patterns	{ASC, DESC}	No	No
Inconsistent / variadic binding	?x	No	No
Typed meta-wildcards	metaint, typename, …	No (only in the validator's internal AST proto)	No
Assertion statements	assert x matches y, ; separators	No	No
Namespaced type refs	a.b.type	No	No

Current spec syntax upstream supports but the validator's (stale) grammar does NOT

Construct	In stdlib 0.87.0?	Validator grammar?
Function types func<any1 -> any2>	Yes (higher-order fns)	No — grammar has no ->/Arrow token
User-defined sigil u!geometry	Yes (geometry extension)	No — ! is only the boolean-NOT / non-nullable operator, not an identifier char

So the bespoke grammar carries a large amount of surface that is unused in practice, while simultaneously
missing syntax the standard extensions already use. The committed parser is also stale relative to the
validator's own pinned substrait submodule (0.87.0) — i.e. this can't be fixed by a version bump; the
grammars genuinely diverged in design.

Is anything actually missing from upstream?

For the realistic goal — parse and evaluate what extension YAMLs actually contain — upstream's grammar is
already sufficient. It covers every type expression and derivation program in the standard extensions: simple

• parameterized types, ? nullability, named numeric parameters, any/anyN, u! user-defined,
  func<… -> …>, multi-line x = expr … FinalType derivations, arithmetic, comparisons, boolean ops,
  min/max/function calls, if/then/else, and the ternary.

The constructs upstream would need to add only matter if we want to preserve the validator's full matching
expressiveness. These are also candidates for "is this still in the spec?" and should be resolved as spec /
substrait-packaging questions before the rewrite:

1. Type variation suffix [...] — the most defensible gap, since type variations are a real Substrait
   concept. Are derivations ever expected to constrain/derive variations?
2. Richer nullability (!, ??predicate) beyond the simple ?.
3. Assertion statements (assert … matches …, ; separators) — lets a derivation express constraints
   like assert a + b == 10.
4. Integer ranges, enum-set patterns, inconsistent/variadic bindings ?x, typed meta-wildcards — niche,
   quite possibly vestigial.

Proposed direction

1. Resolve the four upstream-gap items above with the spec / substrait-packaging (decide which are
   intended parts of the derivation language vs. vestigial). This determines whether the rewrite is a straight
   port or needs a couple of grammar additions upstream first.
2. Rewrite the validator's derivation handling to consume substrait-antlr: delete the committed
   grammar + generated lexer/parser, depend on the published crate, and move the validator's value-add
   (binding capture, matching, derivation evaluation) into a semantic-analysis layer over the upstream
   expr/typeDef parse tree. This deletes a divergent, stale grammar and fixes the func<-> / u! gaps
   for free.

This issue is the record we can return to; the rewrite will proceed in a follow-up PR.

[nielspardon]

Filed the operator-precedence gap upstream as substrait-io/substrait#1106 — the spec's SubstraitType.g4 puts all binary operators in a single left-recursive alternative, so they share one precedence level (e.g. 1 + 2 * 3 - 4 / 5 evaluates to 1, not 7). Surfaced while re-targeting the validator's derivation analyzer onto the substrait-antlr grammar.