Skip to main content

rusty_agent_runtime/
graph.rs

1//! Graph definition, plus structural validation when you call
2//! [`GraphBuilder::compile`].
3//!
4//! The public graph API is deliberately a thin builder ([`GraphBuilder`]);
5//! `compile()` freezes the graph into an immutable, cheaply-clonable
6//! [`Graph`] with `Arc`-wrapped internals and validates structure **before
7//! any node (or LLM call) ever runs**:
8//!
9//! - an entry point must be set and must reference a known node;
10//! - every edge endpoint must reference a known node;
11//! - at least one node must be registered;
12//! - node names must not collide with the reserved [`END`] sentinel;
13//! - edges must be unambiguous: no duplicate `from → to` edges, at most one
14//!   conditional edge per source node, and no source node mixing static and
15//!   conditional edges.
16//!
17//! Edge types:
18//!
19//! - **Normal edges** ([`GraphBuilder::add_edge`]): `from → to`. Multiple
20//!   outgoing normal edges from one node activate **all** destinations in
21//!   parallel in the next super-step.
22//! - **Conditional edges** ([`GraphBuilder::add_conditional_edges`]): an
23//!   async routing function reads the post-barrier state and returns a
24//!   [`Route`] — one node, dynamic fan-out via [`Send`], or the end of the
25//!   run.
26
27use std::collections::{HashMap, HashSet};
28use std::fmt;
29use std::future::Future;
30use std::pin::Pin;
31use std::sync::Arc;
32
33use serde::{Deserialize, Serialize};
34use serde_json::Value;
35
36use crate::error::{Result, RustyError};
37use crate::node::Node;
38use crate::state::State;
39
40/// Reserved node name for the terminal route. Not a real node: routers
41/// signal termination with [`Route::End`] instead of naming a node.
42/// [`GraphBuilder::compile`] rejects registering a node under this name (or
43/// any `__`-prefixed name) so the sentinel namespace can never collide with
44/// user nodes.
45pub const END: &str = "__end__";
46
47/// The routing decision of a conditional edge.
48#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
49#[serde(rename_all = "snake_case")]
50pub enum Route {
51    /// Activate exactly one node next.
52    Node(String),
53    /// Dynamic fan-out (LangGraph `Send` API): activate one node invocation
54    /// per item, each with its own scoped input state. The canonical
55    /// map-reduce pattern: items are generated at runtime, each mapped
56    /// through a node, results fan back in through multi-write reducers.
57    Send(Vec<Send>),
58    /// Terminate the run.
59    End,
60}
61
62/// A single dynamic fan-out instruction: run `node` once with `state` as
63/// its scoped input state.
64///
65/// Semantics for the executor: the scoped state is merged into the shared
66/// state before the node runs (so the node sees its item), and the node's
67/// updates merge back through the normal channel reducers — fan-in requires
68/// multi-write reducers on the destination channels.
69#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
70pub struct Send {
71    /// Target node name (must resolve to a known node at execution time).
72    pub node: String,
73    /// Scoped input state for this invocation (partial update applied to the
74    /// shared state snapshot before the node runs).
75    pub state: Value,
76}
77
78impl Send {
79    /// Convenience constructor.
80    pub fn new(node: impl Into<String>, state: Value) -> Self {
81        Self {
82            node: node.into(),
83            state,
84        }
85    }
86}
87
88/// Async routing function for a conditional edge: reads the post-barrier
89/// state and decides where the run goes next.
90///
91/// Produced by [`GraphBuilder::add_conditional_edges`] from any
92/// `Fn(State) -> impl Future<Output = Result<Route>>`.
93// NOTE: `Send` below refers to std's marker trait; the local `Send` struct
94// shadows it in this module, hence the fully-qualified path.
95pub type ConditionalRouter = Arc<
96    dyn Fn(State) -> Pin<Box<dyn Future<Output = Result<Route>> + std::marker::Send>>
97        + std::marker::Send
98        + Sync,
99>;
100
101/// One edge in the graph.
102#[derive(Clone)]
103pub enum Edge {
104    /// Static edge: after `from` completes, activate `to` in the next
105    /// super-step. Multiple `Direct` edges from the same node activate all
106    /// targets in parallel.
107    Direct { from: String, to: String },
108    /// Dynamic edge: after `from` completes, evaluate `router` against the
109    /// post-barrier state to decide the next activation.
110    Conditional {
111        from: String,
112        router: ConditionalRouter,
113    },
114}
115
116impl Edge {
117    /// The source node of this edge.
118    pub fn from(&self) -> &str {
119        match self {
120            Edge::Direct { from, .. } | Edge::Conditional { from, .. } => from,
121        }
122    }
123}
124
125impl fmt::Debug for Edge {
126    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127        match self {
128            Edge::Direct { from, to } => write!(f, "Edge::Direct({from} -> {to})"),
129            Edge::Conditional { from, .. } => write!(f, "Edge::Conditional({from} -> ?)"),
130        }
131    }
132}
133
134/// Internal, immutable graph topology. Wrapped in `Arc` by [`Graph`].
135struct GraphInner {
136    nodes: HashMap<String, Arc<dyn Node>>,
137    edges: Vec<Edge>,
138    entry_point: String,
139}
140
141/// A compiled, immutable, thread-safe graph. Cheap to clone (Arc internals).
142///
143/// Obtain via [`GraphBuilder::compile`]. The executor drives a `Graph`;
144/// graphs are frozen so topology can never drift mid-run.
145pub struct Graph {
146    inner: Arc<GraphInner>,
147}
148
149impl Clone for Graph {
150    fn clone(&self) -> Self {
151        Self {
152            inner: Arc::clone(&self.inner),
153        }
154    }
155}
156
157impl fmt::Debug for Graph {
158    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
159        f.debug_struct("Graph")
160            .field("nodes", &self.inner.nodes.keys().collect::<Vec<_>>())
161            .field("edges", &self.inner.edges)
162            .field("entry_point", &self.inner.entry_point)
163            .finish()
164    }
165}
166
167impl Graph {
168    /// The entry-point node name.
169    pub fn entry_point(&self) -> &str {
170        &self.inner.entry_point
171    }
172
173    /// Look up a node by name.
174    pub fn node(&self, name: &str) -> Option<Arc<dyn Node>> {
175        self.inner.nodes.get(name).cloned()
176    }
177
178    /// `true` if a node with this name is registered.
179    pub fn has_node(&self, name: &str) -> bool {
180        self.inner.nodes.contains_key(name)
181    }
182
183    /// All registered node names.
184    pub fn node_names(&self) -> impl Iterator<Item = &str> {
185        self.inner.nodes.keys().map(String::as_str)
186    }
187
188    /// All edges originating at `from` (static and conditional).
189    pub fn outgoing_edges(&self, from: &str) -> Vec<&Edge> {
190        self.inner
191            .edges
192            .iter()
193            .filter(|e| e.from() == from)
194            .collect()
195    }
196
197    /// All edges in the graph.
198    pub fn edges(&self) -> &[Edge] {
199        &self.inner.edges
200    }
201
202    /// Number of registered nodes.
203    pub fn node_count(&self) -> usize {
204        self.inner.nodes.len()
205    }
206
207    /// SHA-256 content hash of the graph's topology: the sorted node names
208    /// and the sorted edge descriptors (`from>to` for static edges,
209    /// `from>?` for conditional routers).
210    ///
211    /// Stamped into [`crate::record::CheckpointHeader::graph_hash`] so replay
212    /// can detect that a checkpoint and the graph about to resume it
213    /// disagree structurally. It is deliberately a *topology* hash: node
214    /// bodies are opaque closures/trait objects, so semantic changes inside
215    /// a node cannot be detected here — that is what the application-level
216    /// `graph_version` (set via `RunConfig::with_graph_version`) is for.
217    pub fn topology_hash(&self) -> String {
218        let mut lines: Vec<String> =
219            Vec::with_capacity(self.inner.nodes.len() + self.inner.edges.len());
220        lines.extend(self.inner.nodes.keys().map(|name| format!("node:{name}")));
221        lines.extend(self.inner.edges.iter().map(|edge| match edge {
222            Edge::Direct { from, to } => format!("edge:{from}>{to}"),
223            Edge::Conditional { from, .. } => format!("edge:{from}>?"),
224        }));
225        lines.push(format!("entry:{}", self.inner.entry_point));
226        lines.sort_unstable();
227        crate::record::sha256_hex(lines.join("\n").as_bytes())
228    }
229}
230
231/// Builder for a [`Graph`]. Register nodes and edges, set the entry point,
232/// then [`GraphBuilder::compile`] to validate and freeze.
233#[derive(Default)]
234pub struct GraphBuilder {
235    nodes: HashMap<String, Arc<dyn Node>>,
236    edges: Vec<Edge>,
237    entry_point: Option<String>,
238}
239
240impl GraphBuilder {
241    /// An empty builder.
242    pub fn new() -> Self {
243        Self::default()
244    }
245
246    /// Register a node under `name`.
247    ///
248    /// Accepts any [`Node`] impl — including async closures
249    /// (`Fn(NodeContext) -> impl Future<Output = Result<NodeOutput>>`) via
250    /// the blanket impl. Re-registering the same name replaces the node.
251    pub fn add_node<N>(&mut self, name: impl Into<String>, node: N) -> &mut Self
252    where
253        N: Node + 'static,
254    {
255        self.nodes.insert(name.into(), Arc::new(node));
256        self
257    }
258
259    /// Add a static edge `from → to`. Multiple outgoing static edges from
260    /// the same node activate all destinations in parallel in the next
261    /// super-step.
262    ///
263    /// [`GraphBuilder::compile`] rejects a node that has both static and
264    /// conditional edges — ambiguous routing fails when you call `compile()`,
265    /// not as a runtime surprise. Dynamic routing via `Command::goto` from a node
266    /// that also has static edges remains a runtime rule: both paths
267    /// execute.
268    pub fn add_edge(&mut self, from: impl Into<String>, to: impl Into<String>) -> &mut Self {
269        self.edges.push(Edge::Direct {
270            from: from.into(),
271            to: to.into(),
272        });
273        self
274    }
275
276    /// Add a conditional edge: after `from` completes, run `router` against
277    /// the post-barrier state and follow the returned [`Route`].
278    ///
279    /// ```
280    /// use rusty_agent_runtime::graph::{GraphBuilder, Route};
281    ///
282    /// let mut builder = GraphBuilder::new();
283    /// builder.add_conditional_edges("agent", |state| async move {
284    ///     let needs_tools = state.get("messages")
285    ///         .and_then(|m| m.as_array())
286    ///         .and_then(|a| a.last())
287    ///         .map(|m| m.get("tool_calls").is_some())
288    ///         .unwrap_or(false);
289    ///     Ok(if needs_tools { Route::Node("tools".into()) } else { Route::End })
290    /// });
291    /// ```
292    pub fn add_conditional_edges<F, Fut>(&mut self, from: impl Into<String>, router: F) -> &mut Self
293    where
294        F: Fn(State) -> Fut + std::marker::Send + Sync + 'static,
295        Fut: Future<Output = Result<Route>> + std::marker::Send + 'static,
296    {
297        let router: ConditionalRouter = Arc::new(move |state| Box::pin(router(state)));
298        self.edges.push(Edge::Conditional {
299            from: from.into(),
300            router,
301        });
302        self
303    }
304
305    /// Set the entry-point node (the LangGraph `START` edge).
306    pub fn set_entry_point(&mut self, name: impl Into<String>) -> &mut Self {
307        self.entry_point = Some(name.into());
308        self
309    }
310
311    /// Validate and freeze the graph.
312    ///
313    /// Validation (all failures are [`RustyError::Graph`]):
314    ///
315    /// - at least one node is registered;
316    /// - the entry point is set and references a known node;
317    /// - every edge endpoint (`from`, and `to` for static edges) references
318    ///   a known node;
319    /// - no node is registered under a reserved name ([`END`] or any
320    ///   `__`-prefixed name);
321    /// - no duplicate static `from → to` edge (a duplicate would activate
322    ///   the target twice in one super-step, which surfaces as a spurious
323    ///   double-write failure on single-write channels);
324    /// - at most one conditional edge per source node;
325    /// - no source node mixes static and conditional edges.
326    ///
327    /// Conditional router targets and [`Send`] node names are validated at
328    /// execution time (they are data-dependent by design).
329    pub fn compile(self) -> Result<Graph> {
330        if self.nodes.is_empty() {
331            return Err(RustyError::Graph(
332                "cannot compile an empty graph: register at least one node".into(),
333            ));
334        }
335
336        for name in self.nodes.keys() {
337            if name == END || name.starts_with("__") {
338                return Err(RustyError::Graph(format!(
339                    "node name `{name}` is reserved (`{END}` and `__`-prefixed names \
340                     form the engine's sentinel namespace)"
341                )));
342            }
343        }
344
345        let entry_point = self.entry_point.ok_or_else(|| {
346            RustyError::Graph("no entry point set: call set_entry_point()".into())
347        })?;
348        if !self.nodes.contains_key(&entry_point) {
349            return Err(RustyError::Graph(format!(
350                "entry point `{entry_point}` does not reference a known node"
351            )));
352        }
353
354        let mut direct_edges: HashSet<(&str, &str)> = HashSet::new();
355        let mut direct_sources: HashSet<&str> = HashSet::new();
356        let mut conditional_sources: HashSet<&str> = HashSet::new();
357
358        for edge in &self.edges {
359            let from = edge.from();
360            if !self.nodes.contains_key(from) {
361                return Err(RustyError::Graph(format!(
362                    "edge source `{from}` does not reference a known node"
363                )));
364            }
365            match edge {
366                Edge::Direct { to, .. } => {
367                    if !self.nodes.contains_key(to) {
368                        return Err(RustyError::Graph(format!(
369                            "edge target `{to}` (from `{from}`) does not reference a known node"
370                        )));
371                    }
372                    if !direct_edges.insert((from, to.as_str())) {
373                        return Err(RustyError::Graph(format!(
374                            "duplicate edge `{from} -> {to}`: the target would be \
375                             activated twice in one super-step"
376                        )));
377                    }
378                    direct_sources.insert(from);
379                }
380                Edge::Conditional { .. } => {
381                    if !conditional_sources.insert(from) {
382                        return Err(RustyError::Graph(format!(
383                            "node `{from}` has multiple conditional edges; only one \
384                             router per source node is allowed"
385                        )));
386                    }
387                }
388            }
389        }
390
391        if let Some(from) = direct_sources.intersection(&conditional_sources).next() {
392            return Err(RustyError::Graph(format!(
393                "node `{from}` has both static and conditional edges; routing would \
394                 be ambiguous — use one kind per source node"
395            )));
396        }
397
398        Ok(Graph {
399            inner: Arc::new(GraphInner {
400                nodes: self.nodes,
401                edges: self.edges,
402                entry_point,
403            }),
404        })
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use super::*;
411    use crate::node::NodeOutput;
412    use serde_json::json;
413
414    async fn ok_node(_ctx: crate::node::NodeContext) -> Result<NodeOutput> {
415        Ok(NodeOutput::empty())
416    }
417
418    #[test]
419    fn compile_rejects_empty_graph() {
420        let err = GraphBuilder::new().compile().unwrap_err();
421        assert!(matches!(err, RustyError::Graph(_)));
422    }
423
424    #[test]
425    fn compile_rejects_missing_entry_point() {
426        let mut b = GraphBuilder::new();
427        b.add_node("a", ok_node);
428        let err = b.compile().unwrap_err();
429        assert!(matches!(err, RustyError::Graph(_)));
430    }
431
432    #[test]
433    fn compile_rejects_unknown_entry_point() {
434        let mut b = GraphBuilder::new();
435        b.add_node("a", ok_node);
436        b.set_entry_point("nope");
437        assert!(b.compile().is_err());
438    }
439
440    #[test]
441    fn compile_rejects_dangling_edges() {
442        let mut b = GraphBuilder::new();
443        b.add_node("a", ok_node);
444        b.set_entry_point("a");
445        b.add_edge("a", "ghost");
446        assert!(b.compile().is_err());
447
448        let mut b = GraphBuilder::new();
449        b.add_node("a", ok_node);
450        b.set_entry_point("a");
451        b.add_conditional_edges("ghost", |_s| async { Ok(Route::End) });
452        assert!(b.compile().is_err());
453    }
454
455    #[tokio::test]
456    async fn compile_accepts_valid_graph() {
457        let mut b = GraphBuilder::new();
458        b.add_node("agent", ok_node);
459        b.add_node("tools", ok_node);
460        b.set_entry_point("agent");
461        b.add_edge("tools", "agent");
462        b.add_conditional_edges("agent", |state| async move {
463            Ok(if state.contains("done") {
464                Route::End
465            } else {
466                Route::Node("tools".into())
467            })
468        });
469        let graph = b.compile().unwrap();
470        assert_eq!(graph.entry_point(), "agent");
471        assert_eq!(graph.node_count(), 2);
472        assert!(graph.has_node("tools"));
473        assert_eq!(graph.outgoing_edges("agent").len(), 1);
474        assert_eq!(graph.outgoing_edges("tools").len(), 1);
475
476        // Clones share the same frozen internals.
477        let g2 = graph.clone();
478        assert!(g2.node("agent").is_some());
479
480        // Router is callable.
481        let edges = graph.outgoing_edges("agent");
482        let route = match edges[0] {
483            Edge::Conditional { router, .. } => {
484                router(State::from_value(json!({"done": true})).unwrap()).await
485            }
486            _ => panic!("expected conditional edge"),
487        };
488        assert_eq!(route.unwrap(), Route::End);
489    }
490
491    #[test]
492    fn compile_rejects_duplicate_direct_edges() {
493        let mut b = GraphBuilder::new();
494        b.add_node("a", ok_node);
495        b.add_node("b", ok_node);
496        b.set_entry_point("a");
497        b.add_edge("a", "b");
498        b.add_edge("a", "b");
499        let err = b.compile().unwrap_err();
500        assert!(matches!(err, RustyError::Graph(_)));
501    }
502
503    #[test]
504    fn compile_rejects_duplicate_conditional_edges() {
505        let mut b = GraphBuilder::new();
506        b.add_node("a", ok_node);
507        b.set_entry_point("a");
508        b.add_conditional_edges("a", |_s| async { Ok(Route::End) });
509        b.add_conditional_edges("a", |_s| async { Ok(Route::End) });
510        let err = b.compile().unwrap_err();
511        assert!(matches!(err, RustyError::Graph(_)));
512    }
513
514    #[test]
515    fn compile_rejects_mixed_static_and_conditional_edges() {
516        let mut b = GraphBuilder::new();
517        b.add_node("a", ok_node);
518        b.add_node("b", ok_node);
519        b.set_entry_point("a");
520        b.add_edge("a", "b");
521        b.add_conditional_edges("a", |_s| async { Ok(Route::End) });
522        let err = b.compile().unwrap_err();
523        assert!(matches!(err, RustyError::Graph(_)));
524    }
525
526    #[test]
527    fn compile_rejects_reserved_node_names() {
528        for name in [END, "__internal"] {
529            let mut b = GraphBuilder::new();
530            b.add_node(name, ok_node);
531            b.set_entry_point(name);
532            let err = b.compile().unwrap_err();
533            assert!(matches!(err, RustyError::Graph(_)), "name: {name}");
534        }
535    }
536}