Crate rsaeb 

Byte-oriented interpreter for A=B ordered rewrite programs.

This page is the canonical API guide. The README is the package entry point and language overview, while the project wiki is a short use-case navigation layer. This page focuses on exact public Rust surfaces and the typed boundaries a host program should use.

rsaeb is a no_std + alloc library crate. It parses compact A=B source into an immutable program::Program, validates host bytes as input::RuntimeInput, admits that input into a one-run input::RunSeed, and executes only after limits::ExecutionLimits are attached. The interpreter core does not read files, use process arguments, access environment variables, write stdout/stderr, or perform lossy byte-to-text display conversion.

The public API is intentionally arranged as boundary types rather than root re-exports. A host should move data through the domains in this order: source bytes become a parsed program, raw input bytes become validated runtime input, validated input becomes an admitted run seed, and only then can execution or tracing start. That ordering keeps parse errors, input validation errors, run-admission errors, runtime failures, and trace-sink failures separate in both type signatures and diagnostics.

API map

Use these public entry points according to the boundary being crossed:

• source::ProgramSource::from_bytes and source::ProgramSource::from_text explicitly label host bytes or strings as A=B source before parsing.
• program::Program::parse validates source syntax under limits::ParseLimits and returns a reusable program::Program.
• input::RuntimeInputSource::from_bytes labels host input bytes, and input::RuntimeInput::validate validates and owns them in the runtime input byte domain until execution consumes the value.
• limits::RuntimeInputLimits bounds raw input validation, input::RunSeed admits validated input under limits::ExecutionLimits, and limits::TraceSnapshotByteLimit bounds trace snapshot materialization.
• program::Program::run runs to completion while borrowing the parsed program, program::Program::start_run returns a borrowed typestate execution, program::Program::start_rule_attempt_run returns a borrowed rule-line attempt typestate execution, and the into_* variants return explicit owned typestate executions.
• program::Program::run_with_borrowed_trace observes borrowed trace events without per-event allocation; program::Program::run_with_trace_snapshots materializes bounded owned trace events.
• inspect exposes borrowed structured rule views, and error exposes structured parse, input, runtime, and trace errors.

Typed boundaries

Program source and runtime input are different byte domains. Program payload bytes are printable executable syntax bytes accepted by the parser. Runtime input accepts any ASCII byte, including whitespace, control bytes, and bytes that are reserved syntax in program source. Construct both explicitly before execution so parsing, input validation, and runtime failures remain distinguishable in the type system.

input::RunSeed is the admission witness for one run. It consumes a validated input::RuntimeInput together with limits::ExecutionLimits, checks the initial runtime-state budget, and prevents a later execution API from receiving raw bytes or detached budget values. execution::RuleAttemptSeed extends that admission witness with a limits::RuleAttemptLimit when a host needs rule-line attempt stepping.

Basic execution

Parse source::ProgramSource, validate input::RuntimeInput, then admit an input::RunSeed before running:

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

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());
}

Parse program::Program once when the same rules should be reused. The parser assigns private slots to (once) rules, and each runtime invocation owns only those per-run slot states rather than mutating the parsed program:

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, RunOutcome};
use rsaeb::source::ProgramSource;

let program = Program::parse(ProgramSource::from_text("(once)a=b\na=c"), DEFAULT_PARSE_LIMITS)?;
let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
let execution_limits = ExecutionLimits::new(
    StepLimit::new(10_000),
    DEFAULT_MAX_STATE_LEN,
    DEFAULT_MAX_RETURN_LEN,
);

let first_input = RuntimeInput::validate(RuntimeInputSource::from_bytes(b"aa"), input_limits)?;
let second_input = RuntimeInput::validate(RuntimeInputSource::from_bytes(b"aa"), input_limits)?;

let first = program.run(RunSeed::admit(first_input, execution_limits)?)?;
let second = program.run(RunSeed::admit(second_input, execution_limits)?)?;

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

Stepwise execution

Use program::Program::start_run when a host wants to wait after each applied rule while keeping the parsed program reusable:

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

let program = Program::parse(ProgramSource::from_text("a=b\nb=c"), DEFAULT_PARSE_LIMITS)?;
let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
let execution_limits = ExecutionLimits::new(
    StepLimit::new(10),
    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 execution = program.start_run(seed)?;

let execution = match execution.step() {
    BorrowedStepTransition::Applied(applied) => {
        if applied.rule().position().number().get() != 1 {
            return Err("unexpected first applied rule".into());
        }
        if applied.state().materialize()?.as_slice() != b"b" {
            return Err("unexpected first applied state".into());
        }
        applied.into_session()
    }
    BorrowedStepTransition::Stable(_) | BorrowedStepTransition::Returned(_) | BorrowedStepTransition::Failed(_) => {
        return Err("expected first applied step".into());
    }
};

let execution = match execution.step() {
    BorrowedStepTransition::Applied(applied) => {
        if applied.rule().position().number().get() != 2 {
            return Err("unexpected second applied rule".into());
        }
        if applied.state().materialize()?.as_slice() != b"c" {
            return Err("unexpected second applied state".into());
        }
        applied.into_session()
    }
    BorrowedStepTransition::Stable(_) | BorrowedStepTransition::Returned(_) | BorrowedStepTransition::Failed(_) => {
        return Err("expected second applied step".into());
    }
};

match execution.step() {
    BorrowedStepTransition::Stable(stable) => {
        if stable.steps().get() != 2 {
            return Err("unexpected stable step count".into());
        }
        if stable.state().materialize()?.as_slice() != b"c" {
            return Err("unexpected stable state".into());
        }
    }
    BorrowedStepTransition::Applied(_) | BorrowedStepTransition::Returned(_) | BorrowedStepTransition::Failed(_) => {
        return Err("expected stable completion".into());
    }
}

A execution::BorrowedStepTransition::Failed value is terminal. It exposes the uncommitted state for diagnostics, then lets callers discard the failed run into its error::RunError; it does not expose a retryable session. execution::OwnedStepTransition::Failed carries the same error and uncommitted-state diagnostics for owned sessions, and it can split into the runtime error plus the parsed program when ownership matters. Failed transitions are terminal; recovering the program never recovers a retryable session. Borrowed applied and returned transitions carry inspect::RuleView witnesses; owned transitions retain execution::OwnedRuleWitness values so rule metadata remains available after ownership moves. Owned non-terminal applied and missed transitions also expose into_parts methods so callers can keep the owned witness and the continuation session together.

Use program::Program::start_rule_attempt_run when the host needs to observe every executable rule line, including lines that do not apply to the current runtime state:

use rsaeb::execution::{BorrowedRuleAttemptTransition, RuleAttemptSeed, RuleMissReason};
use rsaeb::limits::{
    DEFAULT_MAX_INPUT_LEN, DEFAULT_PARSE_LIMITS, DEFAULT_MAX_RETURN_LEN, DEFAULT_MAX_STATE_LEN,
    RuleAttemptLimit, StepLimit,
};
use rsaeb::input::{RuntimeInput, RuntimeInputSource};
use rsaeb::input::RunSeed;
use rsaeb::limits::{ExecutionLimits, RuntimeInputLimits};
use rsaeb::program::Program;
use rsaeb::source::ProgramSource;

let program = Program::parse(ProgramSource::from_text("z=x\na=b"), DEFAULT_PARSE_LIMITS)?;
let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
let execution_limits = ExecutionLimits::new(
    StepLimit::new(10),
    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 attempt_seed = RuleAttemptSeed::new(seed, RuleAttemptLimit::new(10));
let execution = program.start_rule_attempt_run(attempt_seed)?;

let execution = match execution.step() {
    BorrowedRuleAttemptTransition::Missed(missed) => {
        if missed.miss().reason() != RuleMissReason::StateMismatch {
            return Err("unexpected miss reason".into());
        }
        if missed.miss().rule().position().number().get() != 1 {
            return Err("unexpected missed rule".into());
        }
        missed.into_session()
    }
    BorrowedRuleAttemptTransition::Applied(_)
    | BorrowedRuleAttemptTransition::Stable(_)
    | BorrowedRuleAttemptTransition::Returned(_)
    | BorrowedRuleAttemptTransition::Failed(_) => return Err("expected first rule to miss".into()),
};

match execution.step() {
    BorrowedRuleAttemptTransition::Applied(applied) => {
        if applied.step().get() != 1 || applied.rule().position().number().get() != 2 {
            return Err("unexpected applied rule attempt".into());
        }
    }
    BorrowedRuleAttemptTransition::Missed(_)
    | BorrowedRuleAttemptTransition::Stable(_)
    | BorrowedRuleAttemptTransition::Returned(_)
    | BorrowedRuleAttemptTransition::Failed(_) => return Err("expected second rule to apply".into()),
}

Limits

limits::RuntimeInputLimits carries input-byte validation policy. limits::ExecutionLimits carries initial runtime-state admission, the step budget, and byte budgets for rewrite states and (return) outputs. execution::RuleAttemptSeed binds one run seed to the limits::RuleAttemptLimit for the separate rule-line attempt mode. Trace snapshot materialization uses an explicit limits::TraceSnapshotByteLimit. Step limits are reserved before rewrite or return-output materialization when another matching rule would apply after the configured number of completed steps:

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

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::Finish(RunFinishError::Step(RunStepError::StepLimit(error))))
        if error.completed_steps().get() == 0
) {
    return Err("unexpected step-limit error".into());
}

Rule inspection

Parsed rules are exposed as borrowed structured views, not as stored source strings:

use rsaeb::limits::DEFAULT_PARSE_LIMITS;
use rsaeb::inspect::{RuleAction, RuleAnchor, RuleRepeat};
use rsaeb::program::Program;
use rsaeb::source::ProgramSource;

let program = Program::parse(ProgramSource::from_text("( once ) ( start ) a = ( end ) b # comment"), DEFAULT_PARSE_LIMITS)?;
let rule = program.rules().next().ok_or("missing parsed rule")?;

if rule.repeat() != RuleRepeat::Once {
    return Err("unexpected repeat".into());
}
if rule.anchor() != RuleAnchor::Start {
    return Err("unexpected anchor".into());
}
if rule.lhs().materialize()?.as_slice() != b"a" {
    return Err("unexpected left side".into());
}
match rule.action() {
    RuleAction::MoveEnd(payload) => {
        if payload.materialize()?.as_slice() != b"b" {
            return Err("unexpected moved payload".into());
        }
    }
    RuleAction::Replace(_) | RuleAction::MoveStart(_) | RuleAction::Return(_) => {
        return Err("expected move-end action".into());
    }
}
if rule.canonical_source()?.as_slice() != b"(once)(start)a=(end)b" {
    return Err("unexpected canonical source".into());
}

Tracing

Borrowed trace events allocate no snapshots. Snapshot tracing is layered on top when a caller needs owned event bytes:

use core::convert::Infallible;
use rsaeb::limits::{
    DEFAULT_MAX_INPUT_LEN, DEFAULT_PARSE_LIMITS, DEFAULT_MAX_RETURN_LEN, DEFAULT_MAX_STATE_LEN, StepLimit,
};
use rsaeb::trace::BorrowedTraceEvent;
use rsaeb::input::{RuntimeInput, RuntimeInputSource};
use rsaeb::input::RunSeed;
use rsaeb::limits::{ExecutionLimits, RuntimeInputLimits};
use rsaeb::program::Program;
use rsaeb::source::ProgramSource;

let program = Program::parse(ProgramSource::from_text("a=b\nb=(return)ok"), DEFAULT_PARSE_LIMITS)?;
let mut byte_counts = Vec::new();
let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
let execution_limits = ExecutionLimits::new(
    StepLimit::new(10),
    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)?;

program.run_with_borrowed_trace(
    seed,
    |event| {
        byte_counts.push(event.byte_count().get());
        if let BorrowedTraceEvent::Step { rule, .. } = event {
            let _line = rule.line_number();
        }
        Ok::<(), Infallible>(())
    },
)?;

if byte_counts != [1, 1, 2] {
    return Err("unexpected trace byte counts".into());
}

Snapshot tracing materializes owned event bytes under an explicit snapshot byte budget, which lets the caller retain events after each callback returns:

use rsaeb::limits::{
    DEFAULT_MAX_INPUT_LEN, DEFAULT_PARSE_LIMITS, DEFAULT_MAX_RETURN_LEN, DEFAULT_MAX_STATE_LEN,
    DEFAULT_MAX_TRACE_SNAPSHOT_LEN, StepLimit,
};
use rsaeb::trace::{TraceSnapshotEffect, TraceSnapshotEvent};
use rsaeb::input::{RuntimeInput, RuntimeInputSource};
use rsaeb::input::RunSeed;
use rsaeb::limits::{ExecutionLimits, RuntimeInputLimits};
use rsaeb::program::Program;
use rsaeb::source::ProgramSource;

let program = Program::parse(ProgramSource::from_text("a=b\nb=(return)ok"), DEFAULT_PARSE_LIMITS)?;
let input_limits = RuntimeInputLimits::new(DEFAULT_MAX_INPUT_LEN);
let execution_limits = ExecutionLimits::new(
    StepLimit::new(10),
    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 mut states = Vec::new();
let mut returns = Vec::new();

program.run_with_trace_snapshots(seed, DEFAULT_MAX_TRACE_SNAPSHOT_LEN, |event| {
    match event {
        TraceSnapshotEvent::Initial { state } => states.push(state.into_raw_bytes()),
        TraceSnapshotEvent::Step {
            effect: TraceSnapshotEffect::Continue { state },
            ..
        } => states.push(state.into_raw_bytes()),
        TraceSnapshotEvent::Step {
            effect: TraceSnapshotEffect::Return { output },
            ..
        } => returns.push(output.into_raw_bytes()),
    }
    Ok::<(), core::convert::Infallible>(())
})?;

if states != [b"a".to_vec(), b"b".to_vec()] {
    return Err("unexpected trace states".into());
}
if returns != [b"ok".to_vec()] {
    return Err("unexpected trace returns".into());
}

Error model

Source parsing, runtime input validation, runtime execution, trace snapshot materialization, and user trace-sink failures are reported with structured error types such as error::ParseError, error::RuntimeInputError, error::RunError, error::AllocationError, error::TraceSnapshotError, error::TraceSnapshotRunError, and error::TracedRunError. Allocation reservation failures include a typed error::RequestedCapacity instead of only a formatted string. Representation failures are distinct from allocation failures, and runtime contradictions that public construction paths cannot express are eliminated by typed witnesses instead of becoming hidden panics or display-only errors.

use rsaeb::error::RuntimeInputError;
use rsaeb::limits::{RuntimeInputByteLimit, RuntimeInputLimits};
use rsaeb::input::{RuntimeInput, RuntimeInputSource};

fn validate_host_input(bytes: &[u8]) -> Result<RuntimeInput, RuntimeInputError> {
    let limits = RuntimeInputLimits::new(RuntimeInputByteLimit::new(4));
    RuntimeInput::validate(RuntimeInputSource::from_bytes(bytes), limits)
}

let Err(error) = validate_host_input(&[0xff]) else {
    return Err("expected non-ASCII input to fail".into());
};

if !matches!(
    error,
    RuntimeInputError::NonAscii { column, byte }
        if column.get() == 1 && byte.get() == 0xff
) {
    return Err("unexpected input error".into());
}

Modules

error

Structured error types for parsing, input validation, running, and tracing.

execution

Public stepwise run typestates.

input

Runtime-input boundary types.

inspect

Borrowed inspection views for parsed rules and payloads.

limits

Runtime budgets and public byte-count value types.

program

Parsed program and run-to-completion result types.

source

Program-source boundary and source-position value types.

trace

Borrowed and snapshot trace event types.