Orchestrator — CapDAG documentation

Machine notation parsing, DAG construction, and cap resolution.

Overview

The orchestrator turns a machine into something that runs. Its input is machine notation (Machine notation) or a planner Strand; its output is one MachinePlan per strand, which execute_plan runs.

flowchart LR
    MN["Machine notation"] --> RES["Resolve<br/>(machine module)"]
    ST["Planner strand"] --> RES
    RES --> BUILD["MachinePlanBuilder"]
    BUILD --> MP["MachinePlan<br/>(one per strand)"]
    MP --> EX["execute_plan"]

There is one path. Notation is resolved into a Machine (cap lookup, binding of sources to args, taken outputs, cardinality, cycle check, inlining of included machines), and MachinePlanBuilder emits a plan for each strand and the shape of the run (Planner): Cap nodes and a CapOutput node for every other output a step gives, InputSlot and Output nodes at the boundary, ForEach, Item and Collect where cardinality calls for a map or a gather, Arg edges for every binding that is not the main input.

ResolvedNotation is the front end a host uses: it resolves notation once, says what the machine takes and gives by the names the notation wrote, and builds the plan of a strand for a run. A run says, by input name, what it binds (RunInputs): which inputs are sequences, and the type of what it binds where that is more specific than the input’s declared type (a file of one kind given to an input that takes several). The plan follows the given types: a step whose output is its input unchanged produces the run’s type. A type that does not conform to the input’s, or a name that is no input, is refused. A machine that includes others is resolved against the host’s MachineSource.

A strand’s plan for a run is a StrandPlan: the strand, the plan, and the name the notation writes for each node that holds a value. It is what a run is. Each resolution mints new step tokens, so a host that was shown a plan, and keyed argument values by its steps’ tokens, runs that plan: it hands it back, and the plan is checked against the one the notation resolves to now for the same run (StrandPlan::check_is_a_resolution_of). Steps are paired by their written names (every step that holds a value has one), maps by their node, and a step that holds no value by everything else it is; with the pairs, the handed-back plan’s tokens are renamed and the two must be equal field for field, or the check says where they differ. The pairing serves the check alone — the plan that runs keeps its own tokens.

Source: capdag-rs/src/orchestrator/machine_plan.rs (ResolvedNotation, RunInputs, StrandPlan, build_plans_from_notation), capdag-rs/src/planner/plan_builder.rs.

Scopes and segments

A plan has one scope per place a step can run: the machine itself, and the body of each ForEach. execute_plan runs a scope by running its units: chains of steps, and the maps directly inside it. A chain is handed to the EngineRuntime as a segment: a ResolvedGraph holding only those steps (Execution).

ResolvedGraph

A ResolvedGraph is steps with the cap definitions they run, wired by the nodes they read and produce:

pub struct ResolvedGraph {
    pub nodes: HashMap<String, String>,   // node name → the media URN it holds
    pub steps: Vec<ResolvedStep>,          // cap invocations, in no particular order
    pub graph_name: Option<String>,
}

A node no step of the graph produces is an input of the graph: its value is supplied when the graph is run.

Source: capdag-rs/src/orchestrator/types.rs.

ResolvedStep

One step is one invocation of a cap:

pub struct ResolvedStep {
    pub token_id: StepToken,       // the step's identity, carried from the machine
    pub node: String,              // where its MAIN output is stored
    pub cap_urn: String,
    pub cap: Cap,                  // the full cap definition
    pub inputs: Vec<StepInput>,    // the streams it is sent
    pub outputs: Vec<StepOutput>,  // its other outputs that something takes
    pub out_media: String,         // the media URN of the main output
    pub policy: StepPolicy,        // what it does when it fails
}

pub struct StepInput {
    pub stream_urn: String,        // `in=` for the main input, the arg's URN for any other
    pub source: StepSource,
}

pub enum StepSource {
    Node(String),                  // one node's value, as it is
    Gather(Vec<String>),           // several nodes' values, in order, as one sequence
}

pub struct StepOutput {
    pub output_media_urn: String,  // the output's URN in the definition
    pub node: String,              // where its value is stored
}

A cartridge tells its inputs apart by stream_urn. A gathered member that holds one value contributes one item and one that holds a sequence contributes its items; a gather with no members is an empty sequence. A response stream for a declared output that no StepOutput takes is audited, consumed and dropped. Each step carries its Cap, so nothing is resolved again during execution. Values an arg is given from the run’s argument ledger, and constants, are not inputs here: they are sent with the request.

Source: types.rs.

Plan converter

steps_to_resolved_graph(plan, step_ids, registry) converts a chosen set of a plan’s Cap nodes into a ResolvedGraph; plan_to_resolved_graph(plan, registry) converts every step of a plan that has no map.

Plan node type	Graph element
Cap	A step. Its `Direct` in-edge is its main input and each `Arg` in-edge another input stream.
CapOutput	A `StepOutput` of the step it belongs to: the node holding that output.
Collect	A `Gather` source, its members in binding order.
InputSlot, Item, and any node produced outside the chosen steps	A node the graph reads and does not produce.
Output	Nothing: `execute_plan` reads the node it names when the run ends.
ForEach	Not converted. `plan_to_resolved_graph` refuses a plan that holds one; `execute_plan` runs the map itself and converts its body’s steps.

Source: capdag-rs/src/orchestrator/plan_converter.rs.

Validation

A machine is validated where it is resolved (Machine::from_string, per strand): unknown caps and names, the binding of sources to args and the conformance of every bound source to the type its arg accepts, taken outputs, step policy, cycle detection by Kahn’s algorithm, and the consistency of every node’s media URN across the wirings that touch it, and everything a machine in step position is held to. Each failure is one of the errors listed in Machine notation.

Nothing downstream re-validates. The plan builder and the converter check only the invariants of their own input (MachinePlan::validate, and the converter’s own checks on the steps it is given), and report a violation as InvalidGraph: by then it is a defect, not a user error.

Error types

pub enum ParseOrchestrationError {
    MachineSyntaxParseFailed(String),      // the notation did not parse or resolve
    CapNotFound { cap_urn: String },        // cap URN not in the registry
    NotADag { cycle_nodes: Vec<String> },   // the steps form a cycle
    InvalidGraph { message: String },        // the plan cannot be run as asked
}

All errors are descriptive and include the node names or URNs involved. There are no catch-all variants.

Source: types.rs.

Other implementations

The resolver exists in the Go, Python and JavaScript libraries, which parse and resolve the same notation to the same bindings. The plan builder and execute_plan exist in the Rust library only: it is what the capdag CLI and the engine run.