Struct Graph 

pub struct Graph {

    pub nodes: Arena<NodeId, Node>,
    pub values: Arena<ValueId, Value>,
    pub inputs: Vec<ValueId>,
    pub outputs: Vec<ValueId>,
    pub initializers: HashMap<ValueId, WeightRef>,
    pub symbol_constraints: HashMap<SymbolId, SymbolConstraints>,
    pub symbol_unifications: Vec<(SymbolId, SymbolId)>,
    pub symbol_derivations: Vec<(SymbolId, SymbolId)>,
    pub symbol_opaque: Vec<SymbolId>,
    pub inference_symbol_floor: Option<u32>,
    pub opset_imports: HashMap<String, u64>,
    pub subgraphs: HashMap<(NodeId, String), Graph>,
    pub model_functions: HashMap<ModelFunctionKey, ModelFunction>,
    pub ambiguous_model_functions: HashSet<ModelFunctionKey>,
    /* private fields */
}

A computation graph in SSA form.

Nodes and values live in Arenas keyed by NodeId / ValueId. The mutation API keeps producer/consumer edges consistent, so optimization passes can rewrite the graph and then Graph::validate it.

Fields

nodes: Arena<NodeId, Node>

values: Arena<ValueId, Value>

inputs: Vec<ValueId>

Graph inputs, in order. These have no producer.

outputs: Vec<ValueId>

Graph outputs, in order.

initializers: HashMap<ValueId, WeightRef>

Constant initializer weights, keyed by the value they populate.

symbol_constraints: HashMap<SymbolId, SymbolConstraints>

Constraints on symbolic dimensions.

symbol_unifications: Vec<(SymbolId, SymbolId)>

Symbol pairs that shape inference unified while broadcasting two distinct symbolic dimensions onto a single representative (the (loser, winner) substitution in onnx-runtime-shape-inference’s InferenceContext::broadcast_dim).

This is the authoritative, complete-by-construction record of every symbol equivalence inference introduced — elementwise broadcast, MatMul batch dims, Einsum ellipsis, Concat non-concat axes, Expand, and any future handler — because all of them funnel through the single broadcast_dim chokepoint that appends here. It is populated by [crate::shape]-driven inference (infer_graph) and left empty otherwise; it never affects an inferred dimension. Consumers that must reason about a symbol’s full equivalence class (e.g. the CUDA-graph capture-eligibility classifier, which closes its growing-symbol set over these pairs) read it instead of re-deriving a partial copy of inference’s unification per op.

symbol_derivations: Vec<(SymbolId, SymbolId)>

Directed symbol provenance edges (derived, source) recorded when shape inference interns a derived dimension expression (e.g. seq_kv * 8 from Reshape([-1]) or Flatten) to a fresh SymbolId (onnx-runtime-shape-inference’s SymbolInterner::lower): the derived symbol depends on each source symbol its expression was built from.

Together with symbol_unifications this is the complete-by-construction symbol-lineage record: every path by which an inference-minted symbol acquires a dependency on a graph symbol funnels through either the broadcast_dim chokepoint (unification) or the lower chokepoint (derivation). Consumers that must reason about a symbol’s full dependency set — e.g. the CUDA-graph capture-eligibility classifier, which closes its growing/pinned set over these edges — read it instead of re-deriving inference’s lineage per op. It never affects an inferred dim.

symbol_opaque: Vec<SymbolId>

Symbols shape inference minted for a genuinely unknowable extent — an arithmetic overflow degrade or a nonsensical negative extent — from which no source symbol could be recovered (SymbolInterner::lower). A conservative consumer (the capture classifier) treats these as disqualifying (eager), never as constant/pinned.

inference_symbol_floor: Option<u32>

The floor id at/above which every symbol was minted by shape inference (an anonymous/derived/data-dependent symbol); ids below it are graph-declared roots (batch, seq, KV length, heads, …). Set by infer_graph; None before inference runs. The fail-safe capture classifier uses it to distinguish a provably-rooted symbol from an inference-minted (potentially-unknown) one.

opset_imports: HashMap<String, u64>

Imported opsets: domain → version.

subgraphs: HashMap<(NodeId, String), Graph>

Subgraph bodies for control-flow ops, keyed by (node, attr_name).

model_functions: HashMap<ModelFunctionKey, ModelFunction>

Unique model-local functions keyed by normalized (domain, op_type).

Phase-1 heterogeneous legalization intentionally fails closed on overload ambiguity, so overload is not represented here; ambiguous keys are tracked separately in Self::ambiguous_model_functions. TODO(hetero-function-phase2): replace this with an overload-aware FunctionLibrary/IR function identity instead of the bounded unique-name catalog used by the Phase-1 correctness fix.

ambiguous_model_functions: HashSet<ModelFunctionKey>

Model-local function names that are ambiguous without overload metadata.

Implementations

impl Graph

Upper bound on a plausible opset version.

ONNX is at 24 and gains roughly one per release, so anything past this is not a version but a corrupted or misinterpreted value. Bounding it here means every consumer agrees on which versions are usable, rather than each discovering its own limit when converting to a narrower integer.

pub fn new() -> Self

An empty graph.

pub fn effective_opset(&self, node: &Node) -> Option<u64>

The opset version governing node, or None if neither the node nor this graph names one.

One owner for this decision, because three callers previously made it separately and could disagree about the same node: shape inference, native dispatch, and the plugin ABI, which converted to a narrower integer and so rejected versions the others accepted.

A node-local Node::version wins when it is a usable version. Values that cannot be one — negative, zero, or beyond what any opset could plausibly reach — are ignored rather than trusted, since a node claiming them describes IR that is already wrong and the graph’s own import is the better answer.

pub fn node(&self, id: NodeId) -> &Node

Borrow a node. Panics if id is not live; use Graph::try_node for a checked lookup.

pub fn node_mut(&mut self, id: NodeId) -> &mut Node

Mutably borrow a node. Panics if id is not live.

pub fn try_node(&self, id: NodeId) -> Option<&Node>

Checked node lookup.

pub fn value(&self, id: ValueId) -> &Value

Borrow a value. Panics if id is not live; use Graph::try_value for a checked lookup.

pub fn value_mut(&mut self, id: ValueId) -> &mut Value

Mutably borrow a value. Panics if id is not live.

pub fn try_value(&self, id: ValueId) -> Option<&Value>

Checked value lookup.

pub fn uses(&self, value: ValueId) -> Vec<(NodeId, u32)>

Consuming input slots sorted by (NodeId, input_index).

pub fn consumers(&self, value: ValueId) -> Vec<NodeId>

Distinct consumer nodes sorted by ascending NodeId.

pub fn num_uses(&self, value: ValueId) -> usize

Number of consuming input slots.

pub fn has_uses(&self, value: ValueId) -> bool

Whether at least one node input slot consumes value.

pub fn num_nodes(&self) -> usize

Number of live nodes.

pub fn num_values(&self) -> usize

Number of live values.

pub fn value_type_is_known(&self, id: ValueId) -> bool

Whether a value’s element type came from explicit source type information.

pub fn value_shape_is_known(&self, id: ValueId) -> bool

Whether a value’s rank and dimensions came from explicit source shape information.

pub fn mark_value_type_unknown(&mut self, id: ValueId)

Mark a value’s placeholder element type as unknown.

pub fn mark_value_type_known(&mut self, id: ValueId)

Mark a value’s element type as known.

pub fn mark_value_shape_unknown(&mut self, id: ValueId)

Mark a value’s placeholder shape as unknown.

pub fn mark_value_shape_known(&mut self, id: ValueId)

Mark a value’s shape as known (e.g. after seeding a control-flow subgraph’s formal input from the owning node’s operand shape).

pub fn create_symbol(&mut self, name: Option<String>) -> SymbolId

Allocate a fresh symbolic dimension with an optional name (no dedup).

pub fn intern_symbol(&mut self, name: &str) -> SymbolId

Intern a symbolic dimension by protobuf dim-param name: repeated names resolve to the same SymbolId (graph-construction invariant §3.5.4).

pub fn create_value(&mut self, dtype: DataType, shape: Shape) -> ValueId

Create a new anonymous value with a contiguous default layout.

pub fn create_named_value( &mut self, name: impl Into<String>, dtype: DataType, shape: Shape, ) -> ValueId

Create a new named value.

pub fn add_input(&mut self, value: ValueId)

Register value as a graph input.

pub fn add_output(&mut self, value: ValueId)

Register value as a graph output.

pub fn insert_output(&mut self, index: usize, value: ValueId)

Insert value into the ordered graph outputs.

pub fn remove_input(&mut self, index: usize) -> ValueId

Remove one ordered graph input.

pub fn remove_output(&mut self, index: usize) -> ValueId

Remove one ordered graph output.

pub fn set_inputs(&mut self, inputs: Vec<ValueId>)

Replace the complete ordered graph-input list.

pub fn set_outputs(&mut self, outputs: Vec<ValueId>)

Replace the complete ordered graph-output list.

pub fn set_initializer(&mut self, value: ValueId, weight: WeightRef)

Attach initializer weights to value.

pub fn predecessors(&self, node: NodeId) -> Vec<NodeId>

Direct predecessors: nodes that produce this node’s inputs.

pub fn successors(&self, node: NodeId) -> Vec<NodeId>

Direct successors: nodes that consume this node’s outputs.

pub fn nodes_between( &self, inputs: &[ValueId], outputs: &[ValueId], ) -> Vec<NodeId>

All nodes that lie on a path between inputs and outputs.

Walks backwards from outputs via producer edges, stopping at any value in inputs. Used to extract subgraphs for EP capability claims (§3.4).

pub fn topological_order(&self) -> Result<Vec<NodeId>, GraphError>

Topological order of nodes via Kahn’s algorithm.

Ties are broken by ascending NodeId for deterministic output. Returns GraphError::CycleDetected if the graph has a cycle.

pub fn normalize_domains(&mut self)

Canonicalize the default ONNX operator domain to "" throughout this graph (nodes, opset-import keys) and recursively in every subgraph.

After this pass the graph satisfies the post-load invariant: the default domain is always the empty string; "ai.onnx" never appears. The loader establishes this at proto-materialization time; this method lets programmatic graph builders reach the same canonical form before session construction. See crate::normalize_domain.

pub fn insert_node(&mut self, node: Node) -> NodeId

Insert a node, wiring its producer/consumer edges. The node’s id field is overwritten with the freshly allocated NodeId.

pub fn remove_node(&mut self, id: NodeId)

Remove a node, disconnecting its edges. Output values left with no consumers (and not graph I/O or initializers) are deleted.

pub fn remove_nodes(&mut self, ids: &[NodeId])

Remove nodes in slice order.

Each input edge is removed directly by (NodeId, input_index), so this remains linear in the number of removed edges even for a high-fanout shared value.

pub fn replace_node_groups( &mut self, groups: Vec<(Vec<NodeId>, Node)>, graph_outputs: &HashSet<ValueId>, ) -> Vec<NodeId>

Replace disjoint node groups with one node each while updating shared producer/consumer metadata in a batch.

Each group is semantically equivalent to calling Graph::remove_node for its IDs in slice order and then Graph::insert_node for the replacement. In particular, replacement IDs and orphan-value collection match that sequential operation. graph_outputs is retained for API compatibility and checked against the per-value membership invariant in debug builds.

pub fn replace_node(&mut self, old: NodeId, new: Node) -> NodeId

Replace node old in place with new, preserving the NodeId.

The old node’s edges are disconnected and the new node’s edges are connected. Values that were outputs of old but not of new are left in place (producer cleared); the caller may prune them.

pub fn insert_on_edge(&mut self, value: ValueId, new_node: Node) -> NodeId

Splice new_node onto the edge feeding out of value: producer(value) → [new_node] → consumers(value).

new_node’s single input becomes value, and it produces a fresh value that replaces value in all of value’s original consumers.

pub fn replace_input( &mut self, node: NodeId, input_index: usize, new_value: Option<ValueId>, ) -> Option<ValueId>

Replace one node input and update both values’ consumer sets.

This is constant-time on average for edge metadata. None disconnects the slot and is used by node removal.

pub fn replace_all_uses(&mut self, old_value: ValueId, new_value: ValueId)

Replace every use of old_value with new_value in consumer nodes and in the graph output list, moving consumer edges accordingly.

pub fn validate(&self) -> Result<(), Vec<GraphError>>

Verify structural invariants (§3.3). Returns every defect found.

pub fn gc_value_if_orphan(&mut self, value: ValueId)

Delete value if it has no producer, no consumers, and is not part of the graph’s I/O or initializers.

Clears the value’s entries in the unknown-type/shape sets so a later arena slot reuse does not inherit stale “unknown” flags.

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Graph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Graph

fn default() -> Graph

Returns the “default value” for a type.