Planner

Path finding, plan construction, and execution for multi-step transformations.

Overview

The planner module discovers transformation paths automatically. Given a source media type and a target media type, it finds a sequence of caps that transforms the data without the user specifying the intermediate steps.

This is different from the orchestrator (see Orchestrator), which takes an explicit DAG description. The planner builds the DAG by searching the capability graph.

Source: capdag-rs/src/planner/.

LiveCapFab

graph LR
    PDF["media:document;ext=pdf"] -->|extract_metadata| REC["media:record"]
    PDF -->|generate_thumbnail| IMG["media:ext=png;image"]
    PDF -->|extract_text| TXT["media:enc=utf-8"]
    TXT -->|generate_embeddings| EMB["media:embedding"]
    TXT -->|summarize| TXT2["media:enc=utf-8"]
    IMG -->|describe_image| TXT

The LiveCapFab is a directed graph where nodes are media URNs and edges are capabilities. When a cap is registered with input URN A and output URN B, the graph gains an edge A → B labeled with that cap. Every other output the cap declares is reachable too: an output whose media URN is C adds an edge A → C, labeled with the cap and that output. The main output’s runtime type follows the cap URN’s effect (see Cap URN structure); any other output gives its own type. An output that carries the cap’s input unchanged (a router’s) has no type of its own, so it adds no edge.

Path finding traverses this graph to discover multi-step transformation chains: if there is a cap A → B and a cap B → C, then the input type A can reach the output type C via a two-step chain.

Source: capdag-rs/src/planner/live_cap_fab.rs.

Reachable targets

get_reachable_targets() returns all media types reachable from a given source via one or more cap invocations. It performs a breadth-first traversal of the graph starting from the source node and collecting all reachable nodes.

This is used by the UI to show what transformations are available for a given input file (“you can extract metadata, generate a thumbnail, create embeddings, …”), without enumerating every possible path.

Each result is a ReachableTargetInfo containing the target media URN and the machine needed to reach it.

Path finding

find_paths_to_exact_target() returns one or more Strand objects connecting a specific source to a specific target. Each strand is a concrete path through the capability graph.

When multiple paths exist (e.g., PDF → text via extraction, or PDF → image → text via OCR), all valid paths are returned. The caller chooses which to execute based on preference or context.

Source: live_cap_fab.rs.

Strand

A Strand is an ordered list of StrandSteps representing a path through the capability graph:

[source] --cap_1--> [intermediate_1] --cap_2--> [intermediate_2] --cap_3--> [target]

StrandStep

Each step has a token_id, its stable identity, minted when the step is created; the media types at its boundaries, from_spec and to_spec; and a step_type:

• Cap: the cap_urn to invoke, its title and specificity, whether its input and the output it takes are sequences (input_is_sequence, output_is_sequence), inputs (each argument it is fed and that input’s producer: the strand’s input or another step, by token), and output_urn: the other output the step takes, by its media URN, or none for the main output.
• ForEach: a sequence becomes its items; the media type does not change.
• Collect: items become a sequence; the media type does not change.

The first step’s from_spec is the source; the last step’s to_spec is the target. A strand that takes another output becomes a machine whose step takes that output by its name in the cap’s definition (-> (rest=n)); a strand that takes an output its cap does not declare as another output is refused (UnknownStrandOutput).

Source: live_cap_fab.rs, machine/resolve.rs.

Cardinality analysis

The cardinality module determines the shape of data flowing through the plan:

InputCardinality: Is the data a single item or a list?

• Single: One value (e.g., media:document;ext=pdf, one PDF document).
• Sequence: Multiple values (e.g., media:document;ext=pdf;list, a list of PDF documents). The list marker tag in the media URN signals this.

InputStructure: Is the data opaque or structured?

• Opaque: Raw bytes with no internal structure (e.g., media:binary).
• Record: A structured record with named fields (e.g., media:record). The record marker tag signals this.

MediaShape: Combines cardinality and structure into a single classification.

ShapeCompatibility: Determines whether two shapes are compatible for connection. A Single source can feed a Single consumer. A Sequence source can feed a ForEach node that processes items individually.

Source: capdag-rs/src/planner/cardinality.rs.

Argument binding

The argument binding system records, for each argument of a cap invocation, where its value comes from:

ArgumentBindings is the collection for one invocation, keyed by argument media URN. ResolvedArgument is the final value: bytes ready to be sent, with the ArgumentSource they came from.

Source: capdag-rs/src/planner/argument_binding.rs.

MachinePlan

A MachinePlan is a DAG of MachineNodes connected by MachinePlanEdges. It is the planner’s output format: a fully specified execution plan.

Source: capdag-rs/src/planner/plan.rs.

Node types

pub enum ExecutionNodeType {
    Cap { token_id, cap_urn, arg_bindings, preferred_cap, policy },  // a step: one invocation of a cap
    CapOutput { cap_node, output_media_urn, output_name, carries_input },  // one output of a step other than its main one
    ForEach { token_id, sources, body },   // a map: its body runs once per item of its sources, zipped
    Item { foreach, source, media_urn },   // what one run of a map's body is given of one source
    Collect { input_nodes, output_media_urn },  // a gather: several values, in order, as one sequence
    InputSlot { slot_name, expected_media_urn, cardinality },  // something the run supplies
    Output { output_name, source_node },   // something the run gives
}

• A Cap node is a step, and stands for its main output: what reads the main output wires from the step’s node. It carries the step’s policy (retry, on_error) and its argument bindings, constants among them.
• Every other output of a step that something takes is a CapOutput node; its value in a run is stored under that node. carries_input marks an output that carries the step’s input, type unchanged.
• A ForEach lists the sequences it zips (sources, each with the Item node the body is given its item as) and its body: every node that runs once per item. A map opened inside a body is a member of that body; its own body is its own.
• A Collect is a gather into one sequence arg. A member holding one value contributes one item, a member holding a sequence its items, an absent member none. One value bound to a sequence arg is a gather of one.
• InputSlot and Output are the plan’s boundary. A machine that starts from a source has no InputSlot; one that ends in a sink has no Output.

ForEach, Item and Collect realize what the notation leaves to cardinality (Machine notation): none is authored.

Edge types

pub enum EdgeType {
    Direct,                // Into a step: its main input. Into any other node: what that node is of
    Arg { arg_urn },       // Into one non-main argument of a step, delivered under that URN
    Iteration,             // From a map to one of its item nodes
    Collection,            // From a gathered node into its gather
}

An edge says what is delivered, not how often. A node inside a map, read from outside it, is the sequence of its values over the runs, in item order; read from inside the same run, it is that run’s value. The executor reads which from where the two nodes are. Which output of a step an edge leaves is the node it leaves from: the step’s own node for the main output, a CapOutput node for any other. A value that is to be taken apart is taken apart by a cap; there are no field-extracting edges.

MachinePlan::validate holds a plan to this shape: a map iterates at least one sequence, every item is an item of its own map and a member of its body, no node is in two bodies, a CapOutput names a step, and every gather and output names a node of the plan.

MachinePlanBuilder

flowchart LR
    S["MachineStrand<br/>(resolved steps)"] --> PB["MachinePlanBuilder"]
    SH["Run inputs<br/>(how many values, of what type)"] --> PB
    PB --> IS["InputSlot nodes"]
    PB --> CAP["Cap, CapOutput nodes"]
    PB --> MAP["ForEach, Item, Collect"]
    PB --> OUT["Output nodes"]
    IS --> MP["MachinePlan"]
    CAP --> MP
    MAP --> MP
    OUT --> MP

The plan builder converts one resolved strand of a Machine, and what the run binds to each of its inputs (AnchorInput: one value or a sequence, and the type of what is bound), into a MachinePlan.

build_plan_from_machine_strand_for_run() is the entry point (build_plan_from_machine_strand() binds every input alike, to its declared type):

1. Create an InputSlot for each input anchor of the strand, holding the type the run binds to it. Every input must be bound, and the bound type must conform to the input’s declared type.
2. Decide where every step runs: the iteration rule of Machine notation, applied to the strand with the run’s shape. It is the same rule the resolver applies to the notation alone, so a machine maps in a run exactly where its notation says it would.
3. Create a ForEach for each map, with an Item node per source, and list in its body every node that runs once per item.
4. Create a Cap node for each step and a CapOutput node for each other output it gives. Wire each binding: the item where the step is inside the map that iterates its source and the arg takes one value, the node itself otherwise; a Collect where several nodes, or one value, feed a sequence arg. A constant becomes a Literal binding and is wired from nothing.
5. Create an Output for each output anchor.

A planned path (a Strand from the capfab) becomes a plan the same way: it is resolved into a MachineStrand first.

Source: capdag-rs/src/planner/plan_builder.rs, capdag-rs/src/machine/iteration.rs.

Slot resolution priority

flowchart TD
    Q{"slot_values<br/>[token_id:slot_name]?"} -->|Found| V1["Use explicit<br/>per-step value"]
    Q -->|Not found| Q2{"cap_settings<br/>[cap_urn][slot_name]?"}
    Q2 -->|Found| V2["Use per-cap<br/>setting"]
    Q2 -->|Not found| Q3{"default_value<br/>in cap definition?"}
    Q3 -->|Found| V3["Use default"]
    Q3 -->|Not found| V4["No value<br/>(argument omitted)"]

An argument the machine binds, to another node or to a constant, is not a slot: its value is the machine’s, and a slot_values entry or a mid-run update addressed to it is refused, naming the step and the argument. For an argument the machine leaves unbound, the builder resolves its value in three steps:

1. slot_values["{token_id}:{slot_name}"]: Explicit per-step values, addressed by the step’s StepToken (the StrandStep::token_id the planner minted, which is also the plan’s cap-node id). A token comes from the plan or it does not exist: it is never derived from a position, because a strand is a DAG: parallel branches merging downstream have no ordinal, and two identical caps on separate branches differ only by token.
2. cap_settings[cap_urn][slot_name]: Per-cap settings. These apply to every instance of a cap, regardless of which step it appears in.
3. default_value from the cap definition: the fallback.

This priority order lets users override specific steps while still having sensible defaults.

Source: plan_builder.rs.

What a run of a plan is asked for

MachinePlanBuilder::analyze_plan_arguments() reads a plan and says, for every step (addressed by its token) and every argument of its cap, where the argument’s value comes from:

The last two are the step’s slots: the arguments a run may give a value to. A run can go without the user when no slot is required and without a default. The analysis reads the same wires and bindings the plan builder made, so an argument a constant or a named source binds is never asked for. Mirrors carry the result types; plans are built, and analyzed, by the reference only.

Source: plan_builder.rs.

Running a plan

A plan is run by execute_plan (Execution). There is no other executor: the planner produces plans and does not run them.

cap_step_count

A planned path’s cap_step_count counts its Cap steps only: cardinality transitions are not steps a user sees, so candidates are ranked and displayed by it.

Source: capdag-rs/src/planner/live_cap_fab.rs.

Live feeds need no planner support

A live-feed source (13.2 §Reference media) requires nothing from the planner. The consuming arg’s is_sequence declaration makes every wiring decision: a sequence-consuming cap (concat) links directly to the sequence producer and receives the stream whole; over an unbounded feed this is a valid deferred-emission plan, since stopping the run delivers END and the fold emits (a concat over a microphone is “the whole recording, when stopped”); an item-consuming cap (a per-frame filter) is mapped, exactly as for any bounded sequence. Emission timing is op policy, not type structure, and there is no plan-time “unbounded” restriction, and unboundedness does not appear in the plan: a plan is a plan whether its source is a file or a microphone.

Boundedness is instead an executor concern, decided from the cap definitions’ streaming declarations (15.2 §Streaming contracts): a hop from a producer that may emit without a length promise into a consumer that does not consume without one is a chain boundary: the producer runs to completion, its output is spooled, and the consumer is fed the bounded whole after END. The plan never changes for it; only how the chain is executed does. Memory for completion-requiring ops over long feeds is an operational concern of the op (buffer, spill, window), surfaced through ordinary memory-pressure machinery, never a planner error.