rsaeb

rsaeb is a Rust 2024 no_std + alloc, byte-oriented interpreter for A=B ordered rewrite programs.

A=B: https://store.steampowered.com/app/1720850/AB/

Unofficial Project Notice

This project is an unofficial, independently developed interpreter library. It is not affiliated with, endorsed by, or maintained by Artless Games or the original A=B author.

A=B's compact lhs=rhs ordered rewrite system is an unusually elegant programming-puzzle idea. This crate exists because that design is worth studying, testing, and reimplementing. If this interpreter interests you, please support the original game.

Quick Start

Parse source into an immutable Program, validate runtime input, and run with explicit limits:

use rsaeb::limits::{
    DEFAULT_MAX_INPUT_LEN, DEFAULT_PARSE_LIMITS, DEFAULT_MAX_RETURN_LEN, DEFAULT_MAX_STATE_LEN,
    DEFAULT_MAX_STEPS, ExecutionLimits, RuntimeInputLimits,
};
use rsaeb::input::{RunSeed, RuntimeInput, RuntimeInputSource};
use rsaeb::program::{Program, RunOutcome};
use rsaeb::source::ProgramSource;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let program = Program::parse(ProgramSource::from_text("a=b"), DEFAULT_PARSE_LIMITS)?;
    let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
    let execution_limits = ExecutionLimits::new(
        DEFAULT_MAX_STEPS,
        DEFAULT_MAX_STATE_LEN,
        DEFAULT_MAX_RETURN_LEN,
    );
    let input = RuntimeInput::validate(RuntimeInputSource::from_bytes(b"a"), input_limits)?;
    let seed = RunSeed::admit(input, execution_limits)?;
    let result = program.run(seed)?;

    if !matches!(
        result.outcome(),
        RunOutcome::Stable(output) if output.as_slice() == b"b"
    ) {
        return Err("unexpected stable output".into());
    }

    Ok(())
}

Construct ProgramSource explicitly with ProgramSource::from_text or ProgramSource::from_bytes; there is no implicit source conversion at the API boundary. Use from_bytes when source comments may contain non-UTF-8 bytes. Reuse parsed programs freely: a Program is immutable, and (once) consumption is local to each execution.

Execution APIs

The primary execution path is:

1. Construct ProgramSource with from_text or from_bytes.
2. Parse it with Program::parse.
3. Label host bytes with RuntimeInputSource::from_bytes and validate them with RuntimeInput::validate.
4. Admit RuntimeInput with RunSeed::admit, then execute with Program::run, Program::start_run, or Program::into_run.

The crate intentionally contains no filesystem, process, stdout/stderr, argument parsing, environment access, or lossy display boundary. Hosts should perform I/O outside the interpreter and pass already-loaded bytes to ProgramSource and RuntimeInput.

Stepwise Execution

Use Program::start_run when a host needs control after each applied rule while keeping the parsed program reusable. Use Program::into_run only when the session itself must own the parsed program, such as when moving it across a 'static task boundary. Program::run remains the borrowed run-to-completion path.

The public typestate API lives under rsaeb::execution: borrowed RunSession<'program> advances through StepTransition, while OwnedRunSession advances through OwnedStepTransition. Applied, stable, returned, and failed states represent post-step states. (return) is terminal, not an ordinary continuation step. Running, applied, and stable executions expose borrowed RuntimeStateView values for observation. A failed borrowed step returns StepTransition::Failed, so a host can inspect the uncommitted state and then discard the failed run into its runtime error. An owned failed step returns OwnedStepTransition::Failed; it exposes the same diagnostics and can also split the runtime error from the uncommitted owned session when the host needs to recover the parsed program.

The docs.rs crate page contains a complete doctested stepwise example.

Resource Limits

ParseLimits is the parser contract. It bounds source bytes, executable code-line bytes, parsed payload bytes, and executable rule count before the parser accepts host-provided source into the program domain.

RuntimeInputLimits is the raw input validation contract. RunSeed::admit is the boundary that ties one validated input to one ExecutionLimits value. ExecutionLimits is the run admission and execution contract: it validates initial runtime-state size during admission, then carries the step, rewrite-state, and return-output budgets through the run. Step count alone is not enough for a rewrite system because a short run can still expand state aggressively.

use rsaeb::error::{LimitError, RunError};
use rsaeb::limits::{
    DEFAULT_MAX_INPUT_LEN, DEFAULT_PARSE_LIMITS, DEFAULT_MAX_RETURN_LEN, DEFAULT_MAX_STATE_LEN,
    ExecutionLimits, RuntimeInputLimits, StepLimit,
};
use rsaeb::input::{RunSeed, RuntimeInput, RuntimeInputSource};
use rsaeb::program::Program;
use rsaeb::source::ProgramSource;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
    let execution_limits = ExecutionLimits::new(
        StepLimit::new(0),
        DEFAULT_MAX_STATE_LEN,
        DEFAULT_MAX_RETURN_LEN,
    );
    let input = RuntimeInput::validate(RuntimeInputSource::from_bytes(b"a"), input_limits)?;
    let seed = RunSeed::admit(input, execution_limits)?;
    let result = Program::parse(ProgramSource::from_text("a=b"), DEFAULT_PARSE_LIMITS)?.run(seed);

    if !matches!(
        result,
        Err(RunError::Limit(LimitError::Step { completed_steps, .. }))
            if completed_steps.get() == 0
    ) {
        return Err("unexpected step-limit error".into());
    }

    Ok(())
}

Execution may succeed exactly at the step limit. The step limit becomes an error only when another rule would still apply after the configured number of completed steps.

Runtime input validation is bounded by RuntimeInputLimits; initial state admission is bounded by ExecutionLimits before the interpreter creates an execution session. Trace snapshot materialization has its own TraceSnapshotByteLimit because tracing is outside runtime execution.

Tracing

Tracing has two layers:

• Borrowed tracing does not materialize owned event snapshots. Events borrow runtime state or return payload bytes only for the callback invocation.
• Snapshot tracing materializes owned event bytes under TraceSnapshotByteLimit.

Borrowed trace sinks use run_with_borrowed_trace, which separates runtime errors from trace-sink errors with TracedRunError. Snapshot tracing adds one more failure domain through TraceSnapshotRunError: runtime execution, snapshot materialization, and sink failures are distinct variants.

Parsed rule views inside trace events borrow from the parsed Program, so retained trace events cannot outlive that program.

A=B Language Reference

A program source is a byte sequence containing one rewrite rule per non-empty code line:

lhs=rhs

Each line is parsed in this order:

1. # starts a comment. Everything from # to the end of the line is ignored.
2. Non-ASCII bytes are rejected in the remaining code part.
3. ASCII whitespace in the code part is removed completely.
4. Remaining non-whitespace code bytes must be printable ASCII.
5. Empty compact code is ignored.
6. Non-empty compact code must contain exactly one =.
7. The left side and right side are parsed as compact rule syntax.

Examples:

a=b# this is parsed as a=b
#a=b  this whole line is a comment
a b = b b  # this is parsed as ab=bb

Comments may contain arbitrary non-ASCII or non-UTF-8 bytes when source is provided with ProgramSource::from_bytes. Executable code outside comments must be ASCII. ASCII control bytes are invalid in executable code except for ASCII whitespace that is removed during compaction.

Parse error columns are one-based byte positions in the original source line before whitespace compaction. Diagnostics point at the user's source text, not at the internal compacted representation.

Reserved Characters

The following characters are reserved in program code:

= # ( )

Their meanings are fixed:

• = separates the left side from the right side.
• # starts a comment.
• ( and ) are only allowed as part of supported modifier/action tokens.

A second = in compact code is a parse error:

a=b=c

A second = inside a comment is ignored:

a=b#=c

Reserved syntax where payload data is expected is always a parse error:

a=b(
a=b)
a=b()
a=()
a=b(start)
a=(once)b
a(once)=b

Because whitespace is removed from program code, spaces cannot be represented as rule data. Because =, #, (, and ) are reserved, program payloads also refuse them as rule data.

Runtime input is different. Input bytes are runtime data, not program code. Input must be ASCII, but it may contain whitespace, ASCII control bytes, and reserved characters. Ordinary rewrite actions cannot match, create, or delete those bytes directly.

program: a=b
input:   a=()#c
output:  b=()#c

Rules cannot match across preserved runtime-only bytes:

program: ab=bb
input:   a bc
output:  a bc

(return) stops execution and replaces the final output with its return payload, so runtime-only input bytes are not preserved after a matching return rule:

program: a=(return)x
input:   a=()#c
output:  x

Left-Side Modifiers

The left side may start with one repeat modifier and one anchor modifier:

• (once): the rule may be used at most once per runtime execution.
• (start): the rule only matches at the start of the current state.
• (end): the rule only matches at the end of the current state.

Supported modifier order is (once) first, then an optional anchor. Duplicated or unsupported left-side modifier order is a parse error.

Examples:

a=b
(once)a=b
(start)a=b
(end)a=b
(once)(start)a=b

Because code whitespace is ignored, this is also valid and equivalent to (once)(start)a=b:

( once ) ( start ) a = b

Right-Side Actions

The right side selects the action for a matching rule:

• text: replace the matched left side with text.
• (start)text: remove the match and insert text at the start of the state.
• (end)text: remove the match and append text to the end of the state.
• (return)text: stop execution immediately and output text, discarding the current runtime state.

The action payload is still program data, so it cannot contain whitespace, reserved characters, non-ASCII bytes, or ASCII control bytes. (return) can therefore output only program-representable bytes, even if the discarded runtime state contained spaces or reserved characters from the original input.

Examples:

a=b
x=(start)y
x=(end)y
x=(return)y

Empty Sides

The left side and right side may be empty.

An empty right side deletes the matched left side:

a=

An empty left side matches an empty byte sequence. For unanchored rules and (start) rules, it matches at the start of the current state:

(once)=x

With input ab, this inserts x at the start and produces xab.

For (end) rules, an empty left side matches at the end of the current state:

(once)(end)=x

With input ab, this inserts x at the end and produces abx.

An unanchored empty-left rule without (once), (return), or some later rule that makes execution stop can rewrite forever until the step limit is reached. That is legal syntax; execution remains governed by ExecutionLimits.

Ordered Execution

Execution is ordered and single-step.

On each step, the runtime scans rules from top to bottom and applies the first rule that matches the current state. For an unanchored non-empty left side, the leftmost match in the current state is used. After one rewrite step, scanning restarts from the first rule.

Example:

program:
aa=x
a=y

input:
aaaa

output:
xx

The first rule is preferred over the second rule, and each application rewrites the leftmost matching aa.

Byte-Domain Boundary

Program source and runtime input are deliberately different byte domains:

• Program code is compact printable ASCII syntax.
• ASCII whitespace in program code is ignored before parsing.
• # starts a comment for the rest of the source line.
• Comments may contain non-ASCII or non-UTF-8 bytes.
• Executable code outside comments must be ASCII.
• Program payloads cannot contain whitespace, =, #, (, ), non-ASCII bytes, or ASCII control bytes.
• Runtime input is ASCII data and may contain spaces, ASCII control bytes, and reserved syntax bytes.
• Normal rewrites preserve runtime-only bytes that program code cannot construct or match.
• (return) stops execution and replaces the whole output with its return payload.

Internally, parser and runtime phases stay separate instead of passing raw byte buffers through every stage:

raw line bytes
  -> RawSourceLine
  -> CodeLine                # comment removed, executable code ASCII validated
  -> CompactCodeLine         # whitespace removed, SourceColumn retained
  -> NonEmptyCompactCodeLine # empty compact lines cannot enter rule parsing
  -> RuleSyntaxLine          # exactly one '=' has been proven
  -> LeftSyntax / RightSyntax
  -> ProgramByte             # bytes that program code may construct and match

runtime input bytes
  -> AsciiByte         # runtime input domain validation
  -> RuntimeByte       # private ProgramConstructible(ProgramByte) or Opaque(NonProgramAsciiByte)
  -> RunSession / OwnedRunSession
                       # consumes RuntimeInput and owns mutable execution state

Program payloads are stored as ProgramByte, not raw u8. Runtime state is stored as RuntimeByte: payload-compatible input and rule output become editable program bytes, while whitespace, control bytes, and reserved syntax bytes from input become opaque ASCII bytes. Ordinary rules match only editable bytes. Opaque input bytes are preserved by surrounding rewrites but cannot be directly matched, created, or deleted by program payloads.

Runtime input and runtime state stay in the typed byte domain during execution. Public observation crosses an explicit materialization boundary: RuntimeStateView materializes to RuntimeStateSnapshot, stable run results use RuntimeStateSnapshot, (return) outputs use ReturnOutput, parsed payload inspection materializes to PayloadBytes, and snapshot tracing materializes owned event bytes under TraceSnapshotByteLimit. During execution, the active state and the rewrite scratch buffer are distinct typed buffers, and the runtime swaps them only after a successful continuation step. (once) rules carry private slots assigned during parsing; only a committed application can consume that slot.

no_std + alloc Boundary

The library crate is #![no_std] and uses alloc only at owned-buffer boundaries such as parsed rules, runtime input validation, per-run (once) state, run results, canonical rule source, explicit view materialization, and trace snapshots. It requires an allocator, but not std.

Allocation is explicit and fallible. Parser/runtime paths reserve explicitly and report AllocationError instead of relying on accidental Vec growth. Runtime expansion is budgeted through ExecutionLimits; the runtime checks size limits before allocating oversized states or return outputs. Trace snapshot materialization is budgeted separately through TraceSnapshotByteLimit. Internal parser/runtime witnesses are borrowed slices or typed indexes; they do not allocate just to strengthen invariants.

Owned public values that contain byte buffers intentionally do not implement Clone; copying bytes is an explicit materialization step, not a hidden infallible API. Parser payload validation is reported before payload storage allocation, so invalid source bytes are not hidden behind allocation failures.

A downstream std application can use the library normally. A downstream no_std application must provide an allocator before calling APIs that allocate.

Error Model

The library error model is intentionally split. Parse errors, runtime input errors, runtime execution errors, allocation errors, configured limit errors, and trace materialization errors have separate structured types under rsaeb::error.

Allocation failures preserve the allocation boundary as AllocationContext. Reservation failures also report a typed RequestedCapacity, so hosts can distinguish failures while validating input, materializing state views, building canonical rule source, producing final output, or retaining trace snapshots without parsing display strings.

Representation failures such as unrepresentable parser positions are separate from allocation failure and are reported as ParseErrorKind::Representation. Parser or runtime witness contradictions that should be unreachable through ordinary public inputs are reported as InternalInvariant variants instead of panicking or being folded into allocation errors.

State length arithmetic overflow is separate from allocation failure and is reported as RunError::StateSize. Configured byte budgets and step budgets are reported as RunError::Limit(LimitError::...). Trace snapshot byte limits are reported through TraceSnapshotError, not RunError::Limit, because snapshot materialization is outside runtime execution.

Filesystem failures are not part of the library error model. External I/O must be handled before bytes enter ProgramSource::from_bytes, ProgramSource::from_text, or RuntimeInputSource::from_bytes.

Public API Overview

The generated rustdoc is the complete API reference. Public types live under their domain modules; the crate root intentionally does not provide duplicate type import paths.

• rsaeb::source: ProgramSource and source-position value types used by parser diagnostics
• rsaeb::input: RuntimeInputSource, RuntimeInput, and RunSeed
• rsaeb::program: Program, RunResult, RunOutcome, RuntimeStateSnapshot, ReturnOutput, and ReturnOutputView
• rsaeb::limits: ParseLimits, SourceByteLimit, CodeLineByteLimit, PayloadByteLimit, RuleLimit, StepLimit, RuntimeInputByteLimit, RuntimeStateByteLimit, ReturnByteLimit, TraceSnapshotByteLimit, RuntimeInputLimits, ExecutionLimits, parser/runtime byte-count value types, StepCount, and default budget constants
• rsaeb::execution: borrowed stepwise run typestates (RunSession, StepTransition, AppliedStep, StableRun, ReturnedRun, FailedRun) and explicit owned typestates (OwnedRunSession, OwnedStepTransition, OwnedAppliedStep, OwnedStableRun, OwnedReturnedRun, OwnedFailedRun)
• rsaeb::inspect: RuleView, RuleActionView, PayloadView, PayloadBytes, CanonicalRuleSource, rule position/count types, OnceRuleCount, RuleRepeat, and RuleAnchor
• rsaeb::trace: TraceEvent, TraceEffect, borrowed trace aliases, snapshot trace aliases, and RuntimeStateView
• rsaeb::error: parse, input, runtime, allocation, limit, and trace error types, including rejected-byte diagnostic value types and RequestedCapacity

Development Checks

Run the public documentation and package checks before publishing changes:

rustup target add thumbv7em-none-eabihf
cargo fmt --check
cargo check --lib --all-features --target thumbv7em-none-eabihf
cargo clippy --all-targets --all-features -- -D warnings
cargo test --all-targets --all-features
cargo test --doc --all-features
latest_rlib="$(find target/debug/deps -maxdepth 1 -name 'librsaeb-*.rlib' -printf '%T@ %p\n' | sort -nr | awk 'NR == 1 { print $2 }')"
rustdoc --edition=2024 --test README.md -L dependency=target/debug/deps --extern "rsaeb=${latest_rlib}"
RUSTDOCFLAGS="-D warnings" cargo doc --all-features --no-deps
cargo package --list
cargo package