# IchorRuntime v0.2.0 - Table of Contents

> The small runtime support library Ichor-generated parsers call into: capture dispatch, error formatting, compiled Tokenizer/Parser combinators, and the LR/GLR runtime -- plus standalone Pratt precedence parsing, generic term recursion, and unification/backtracking search. Ichor itself is dev-only.

## Pages

- [IchorRuntime](readme.md)
- [Cheatsheet](cheatsheet.md)
- [Changelog](changelog.md)
- [LICENSE](license.md)

## Modules

- Capture Dispatch
  - [Ichor.Actions](Ichor.Actions.md): How a parsed Aether AST turns into an actual result -- a sandboxed
program's final value, a config's map/struct, a query's result set, or
transpiled output. One mechanism, used differently per grammar: a
grammar's Actions module only implements the rules/tokens it needs
custom behavior for (`@optional_callbacks`); everything else falls back
to the defaults below.
  - [Ichor.Capture](Ichor.Capture.md): Every capture an action receives bundles the raw parsed structure with
a callable to evaluate it: `node` is always available, unevaluated --
what `quote` returns directly. `eval` is what an action calls when it
actually wants a child's value, with an explicit context it controls.
Never evaluated automatically -- that's the whole point: a special
form like `if` or `quote` decides *whether* and *when* to call `eval`
at all, which is exactly what lets an untaken `if` branch, or `quote`'s
own argument, go unevaluated (and unbound-symbol/nonterminating errors
inside them stay latent) instead of always eagerly running.
  - [Ichor.CustomLexeme](Ichor.CustomLexeme.md): The behaviour a `Grammar.IR.CustomLexeme` `@native("Module",
"function", ...)` node (at *token* position) dispatches to -- the
escape hatch for lexical constructs a fixed maximal-munch tokenizer
can't express: a heredoc's dynamic terminator, a string literal with
embedded interpolated expressions, a `\catcode`-style mid-scan
reconfiguration.
  - [Ichor.CustomRule](Ichor.CustomRule.md): The behaviour a `Grammar.IR.Custom` `@native("Module", "function", ...)`
node dispatches to -- the escape hatch for grammar constructs no static
PEG grammar can express: a Prolog-style mutable operator-precedence
table, C's typedef-vs-expression ambiguity, and similar "what matches
here depends on something read earlier" problems.
  - [Ichor.Node](Ichor.Node.md): The default-fallback shape `Ichor.Actions` builds for a matched rule
that has more than one meaningful capture (a rule with exactly one
capture passes that capture's own value straight through instead):
`rule` names the matched rule, `captures` maps each capture name to its
already-evaluated value (or a list of values, for a name captured more
than once -- e.g. inside a `*`), and `span` locates the whole match
back in the original input.

- Errors
  - [Ichor.Error](Ichor.Error.md): One error struct, reused across every stage -- Lexer, Parser, analysis
pass, and `Ichor.Actions` -- so errors look the same regardless of
origin.

- Lexing/Parsing Support
  - [Grammar.Lexer](Grammar.Lexer.md): The Lexer stage of Aether's Reader/Tokenizer/Lexer/Parser split: walks
a Tokenizer's raw token stream left-to-right, applying every
`@keywords`/`@refine` rule an `Aether.Grammar`'s `refiners` map
declares, before the Parser ever runs.
  - [Grammar.Native.Runtime.Parser](Grammar.Native.Runtime.Parser.md): Rule-level helpers shared by every `Grammar.Native.RuleCompiler`-generated
function -- the Parser stage of Aether's Reader/Tokenizer/Lexer/Parser
split. Mirrors `Grammar.VM.TokenInterpreter`'s own semantics exactly
(same backtracking discipline, same no-progress guard on `Star`), just
expressed as plain function composition instead of a bytecode
interpreter loop -- `Grammar.VM.Compiler`'s moduledoc describes the
same combinators this module implements.
  - [Grammar.Native.Runtime.Tokenizer](Grammar.Native.Runtime.Tokenizer.md): Char-level helpers shared by every `Grammar.Native.CharCompiler`-generated
function, plus the maximal-munch driver `Grammar.Native.generate/2`'s own
`lex_candidates/2` feeds into -- the Tokenizer stage of Aether's
Reader/Tokenizer/Lexer/Parser split. No captures, no `ref_stack` --
tokens can never contain a `Capture` or `Indent`, so a token body is
just text in, `{matched text, rest}` out.

  - [Grammar.Source](Grammar.Source.md): The very first, Reader-adjacent stage in front of the Tokenizer:
confirms `input` is valid UTF-8 before any char-level matcher --
built on Elixir binary pattern matching against `::utf8` codepoints --
ever touches it. Malformed input left unchecked doesn't fail cleanly:
it crashes a compiled matcher with a `MatchError` partway through
tokenizing, deep inside either backend, instead of surfacing as an
ordinary `Ichor.Error`.
  - [Grammar.VM.Token](Grammar.VM.Token.md): One lexed token from `Grammar.VM.Tokenizer` -- the target grammar's own
tokens (e.g. a calculator's `NUMBER`, `"+"`), not to be confused with
`Aether.Token` (Ichor's front-end lexing `.aether` source itself).

- LR/GLR Runtime
  - [Grammar.GLR.GSS](Grammar.GLR.GSS.md): The graph-structured stack itself: nodes keyed by `{state,
stream_position}` (deduplicated -- two derivations that reach the same
state at the same position share one node, the actual efficiency win
over independent parallel stacks), edges labeled with whatever that
edge's own transition produced (a shifted `%Grammar.VM.Token{}`, or a
reduced nonterminal's own already-built raw-captures list) plus the
provenance accumulated along it so far.
  - [Grammar.GLR.Runtime](Grammar.GLR.Runtime.md): The GSS-driving shift-reduce/fork loop itself, shared by the
interpreted `Grammar.GLR` (which wraps a `Grammar.LRTable`'s plain
action/goto maps into closures) and `Grammar.Native.GLR` (which
passes compiled per-state functions instead) -- extracted so both
reuse the exact same, already-proven algorithm. The graph-structured
stack itself (node merging, multi-path reduce enumeration --
`Grammar.GLR.GSS`) is inherently a runtime, input-driven data
structure that can't compile away no matter which engine calls into
it; only *how a caller looks up actions/goto for a state* varies.

  - [Grammar.LR.Stack](Grammar.LR.Stack.md): The linear LR stack's shift/reduce mechanics -- shared by the
interpreted `Grammar.LR` and `Grammar.Native.LR`'s per-state
generated code, since a stack push/pop is exactly the same operation
regardless of whether the state driving it came from a `Map.get` or a
compiled `case`.
  - [Grammar.LRTable](Grammar.LRTable.md): The SLR(1) action/goto table shape itself, plus the two lookups every
LR-family engine needs at match time -- interpreted (`Grammar.LR`,
`Grammar.GLR.Runtime`) or compiled (generated `Grammar.Native.LR`/
`.GLR` code) alike.
  - [Grammar.LRTable.Captures](Grammar.LRTable.Captures.md): Builds the raw-capture list `Ichor.Actions` expects (`{:token,...}`/
`{:rule,...}`/`{:text,...}`, see `Ichor.Capture.raw_captures/0`) from
one reduced production's own RHS entries -- shared by `Grammar.LR` (a
single linear stack) and `Grammar.GLR` (a graph-structured one): both
reduce the same kind of production, against the same kind of token
stream, needing the exact same per-position classification (see
`Grammar.LRTable.Production`'s own moduledoc for what each capture
kind means), so this logic has exactly one place to live rather than
two copies drifting apart.
  - [Grammar.LRTable.Production](Grammar.LRTable.Production.md): One flat CFG production, `lhs -> rhs`, produced by `Grammar.LRTable.Desugar`
from a grammar's PEG-shaped IR (`Seq`/`Choice`/`Star`/`Plus`/`Opt`/`Rep`
each desugar to one or more of these; `Choice` in particular maps
directly onto "more than one production for the same `lhs`" -- the
natural CFG shape ordered PEG choice already resembles, minus the
ordering).

- Backtrack
  - [Ichor.Backtrack](Ichor.Backtrack.md): The behaviour a lazy backtracking search engine implements --
`Ichor.Backtrack.Tree` (Stream-backed, correctness-first) is the only
one today; a future WAM-grade engine would implement the same
contract, letting whatever's built on top (a Prolog-style
SLD-resolution loop, say) swap engines without changing.
  - [Ichor.Backtrack.Bindings](Ichor.Backtrack.Bindings.md): A substitution: which logic variables are bound to which terms so
far, opaque outside this module. `unify/4` is the whole unification
algorithm -- standard, recursive, structural unification with no
occurs-check (matches ISO Prolog's own default: `X = f(X)` succeeds,
building a cyclic term, rather than failing or looping to detect the
cycle -- occurs-check is opt-in in real Prolog too, via `unify_with_occurs_check/2`,
never the default).
  - [Ichor.Backtrack.Term](Ichor.Backtrack.Term.md): The behaviour a caller's own term representation implements so
`Ichor.Backtrack.Bindings` can unify it -- passed explicitly to every
`Bindings` function (`resolve/3`, `unify/4`), the same "module passed
as a plain argument, never looked up dynamically" convention
`Ichor.Actions.evaluate/5` already uses for an actions module.
  - [Ichor.Backtrack.Tree](Ichor.Backtrack.Tree.md): The correctness-first `Ichor.Backtrack` engine: a solution is a plain
thunk, `(-> :empty | {:solution, value, rest})` -- a manually-unfolded
lazy list (a "search tree," hence the name), not backed by any
process/agent or Elixir `Stream` machinery. Each combinator forces
exactly one step of whatever it's combining, which is what makes
`once/1` genuinely stop exploring rather than compute everything and
discard all but the first result, and what makes an infinite Prolog
recursion still yield its first solutions instead of hanging forever
building a list.

- Toolkit
  - [Ichor.Toolkit.Pratt](Ichor.Toolkit.Pratt.md): Precedence-climbing (Pratt) expression parsing over a runtime-mutable
operator table -- extracted from a pattern already hand-rolled once,
`OpExprTest.Operators.climb/6` (`test/support/opexpr_operators.ex`),
the worked example proving `Grammar.IR.Custom`/`@native(...)` rule-
position dispatch works at all. That fixture only ever needed infix
chains; this generalizes to prefix and postfix too, since those are
exactly what Track 1's own motivating scenarios need (Prolog's
`op/3` supports `fy`/`fx` prefix and `xf`/`yf` postfix operators
alongside infix ones, Haskell fixity declarations are infix-only but
mixfix notation is not).
  - [Ichor.Toolkit.Result](Ichor.Toolkit.Result.md): The generic "walk a collection, threading an accumulator through a
fallible step, stopping at the first failure" primitive -- extracted
from a pattern independently hand-rolled at least ten times across
Ichor's own compiler internals before this existed: `build_ruleset/1`
(duplicated near-verbatim across `Ichor.EBNF.ISO.Actions`,
`Ichor.EBNF.W3C.Actions`, `Ichor.BNF.Actions`, `Ichor.ABNF.Actions`, and
`Ichor.PEG.Actions`), `Ichor.Backtrack.Bindings`' own `unify_compound/5`
inner reduce over zipped compound-term arguments (whose failure
sentinel is a bare `:fail`, not `{:error, _}`), `Aether.Eval`'s own
`process_defs/2`, and -- byte-for-byte identical to each other --
`Ichor.Actions`' own `eval_one/2` list-of-captures branch, and
`Aether.Eval`'s own `convert_list/3` and `convert_seq_terms/3`.
  - [Ichor.Toolkit.TermWalk](Ichor.Toolkit.TermWalk.md): Generic recursion over any `Ichor.Backtrack.Term` implementation --
extracted from a pattern independently duplicated inside
`Ichor.Toolkit.TypeScheme` itself: `resolve_deep/3` and the private
`substitute/3` shared the identical "apply a transform, then (if the
result is compound) deconstruct, recurse into every argument with the
same transform, and reconstruct" recursive skeleton, differing only in
what the transform itself does at each step (chase a variable's
binding one level, or substitute a specific variable for a fresh one);
`free_vars/3` is the same recursive shape again, but folding into an
accumulator instead of rebuilding a term.