use std::collections::BTreeSet;
use serde::{Deserialize, Serialize};
use crate::diagnostic::{Diagnostic, DiagnosticKind, Severity};
use crate::edge::{Edge, EdgeKey, EdgeSource};
use crate::graph::DataflowGraph;
use crate::ids::NodeId;
use crate::node::GraphNode;
use crate::typecheck;
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[non_exhaustive]
pub enum TopologyOp {
AddNode {
id: NodeId,
node: GraphNode,
},
RemoveNode {
id: NodeId,
},
ReplaceNode {
id: NodeId,
old: GraphNode,
new: GraphNode,
},
AddEdge {
key: EdgeKey,
edge: Edge,
},
RemoveEdge {
key: EdgeKey,
},
}
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum ApplyError {
#[error("AddNode: node `{id}` already exists")]
NodeAlreadyExists {
id: NodeId,
},
#[error("{op}: no node `{id}` exists in this graph")]
NodeNotFound {
op: &'static str,
id: NodeId,
},
#[error("ReplaceNode: node `{id}`'s current shape does not match this op's `old` field")]
StaleReplace {
id: NodeId,
},
#[error("RemoveEdge: no edge `{key}` exists in this graph")]
EdgeNotFound {
key: EdgeKey,
},
#[error("edge `{key}`'s consumer node no longer exists after applying these ops")]
DanglingConsumer {
key: EdgeKey,
},
#[error("edge `{key}` feeds input `{}`, which node `{}` does not declare", key.input, key.consumer)]
UndeclaredInput {
key: EdgeKey,
},
#[error("edge `{key}`'s producer node `{node}` does not exist after applying these ops")]
DanglingProducer {
key: EdgeKey,
node: NodeId,
},
#[error("edge `{key}`'s producer `{node}` does not declare output `{output}`")]
UndeclaredOutput {
key: EdgeKey,
node: NodeId,
output: crate::ids::PortName,
},
#[error("{count} edge(s) would newly violate strict type checking after applying these ops")]
TypeUnsafe {
count: usize,
mismatches: Vec<Diagnostic>,
},
}
#[must_use]
pub fn diff(old: &DataflowGraph, new: &DataflowGraph) -> Vec<TopologyOp> {
let mut ops = Vec::new();
for id in old.nodes.keys() {
if !new.nodes.contains_key(id) {
ops.push(TopologyOp::RemoveNode { id: id.clone() });
}
}
for (id, node) in &new.nodes {
match old.nodes.get(id) {
None => ops.push(TopologyOp::AddNode {
id: id.clone(),
node: node.clone(),
}),
Some(old_node) if old_node != node => ops.push(TopologyOp::ReplaceNode {
id: id.clone(),
old: old_node.clone(),
new: node.clone(),
}),
Some(_) => {}
}
}
for key in old.edges.keys() {
if !new.edges.contains_key(key) {
ops.push(TopologyOp::RemoveEdge { key: key.clone() });
}
}
for (key, edge) in &new.edges {
let changed = old.edges.get(key).is_none_or(|old_edge| old_edge != edge);
if changed {
ops.push(TopologyOp::AddEdge {
key: key.clone(),
edge: edge.clone(),
});
}
}
ops
}
pub fn apply(graph: &DataflowGraph, ops: &[TopologyOp]) -> Result<DataflowGraph, ApplyError> {
let mut nodes = graph.nodes.clone();
let mut edges = graph.edges.clone();
for op in ops {
if let TopologyOp::RemoveNode { id } = op
&& nodes.remove(id).is_none()
{
return Err(ApplyError::NodeNotFound {
op: "RemoveNode",
id: id.clone(),
});
}
}
for op in ops {
if let TopologyOp::AddNode { id, node } = op {
if nodes.contains_key(id) {
return Err(ApplyError::NodeAlreadyExists { id: id.clone() });
}
nodes.insert(id.clone(), node.clone());
}
}
for op in ops {
if let TopologyOp::ReplaceNode { id, old, new } = op {
match nodes.get(id) {
None => {
return Err(ApplyError::NodeNotFound {
op: "ReplaceNode",
id: id.clone(),
});
}
Some(current) if current != old => {
return Err(ApplyError::StaleReplace { id: id.clone() });
}
Some(_) => {}
}
nodes.insert(id.clone(), new.clone());
}
}
for op in ops {
if let TopologyOp::RemoveEdge { key } = op
&& edges.remove(key).is_none()
{
return Err(ApplyError::EdgeNotFound { key: key.clone() });
}
}
for op in ops {
if let TopologyOp::AddEdge { key, edge } = op {
edges.insert(key.clone(), edge.clone());
}
}
let candidate = DataflowGraph {
nodes,
edges,
strict_types: graph.strict_types,
type_rules: graph.type_rules.clone(),
};
check_referential_integrity(&candidate)?;
check_type_safety(graph, &candidate)?;
Ok(candidate)
}
fn check_referential_integrity(graph: &DataflowGraph) -> Result<(), ApplyError> {
for (key, edge) in &graph.edges {
let Some(consumer) = graph.nodes.get(&key.consumer) else {
return Err(ApplyError::DanglingConsumer { key: key.clone() });
};
if !consumer.inputs.contains_key(&key.input) {
return Err(ApplyError::UndeclaredInput { key: key.clone() });
}
if let EdgeSource::NodeOutput { node, output } = &edge.from {
let Some(producer) = graph.nodes.get(node) else {
return Err(ApplyError::DanglingProducer {
key: key.clone(),
node: node.clone(),
});
};
if !producer.outputs.contains_key(output) {
return Err(ApplyError::UndeclaredOutput {
key: key.clone(),
node: node.clone(),
output: output.clone(),
});
}
}
}
Ok(())
}
fn check_type_safety(base: &DataflowGraph, candidate: &DataflowGraph) -> Result<(), ApplyError> {
if !candidate.strict_types {
return Ok(());
}
let mismatched_before: BTreeSet<EdgeKey> = typecheck::check_types(
&base.nodes,
&base.edges,
&base.type_rules,
base.strict_types,
)
.into_iter()
.filter_map(|d| match d.kind {
DiagnosticKind::TypeMismatch { edge, .. } => Some(edge),
_ => None,
})
.collect();
let new_violations: Vec<Diagnostic> = typecheck::check_types(
&candidate.nodes,
&candidate.edges,
&candidate.type_rules,
candidate.strict_types,
)
.into_iter()
.filter(|d| {
d.severity == Severity::Error
&& matches!(&d.kind, DiagnosticKind::TypeMismatch { edge, .. } if !mismatched_before.contains(edge))
})
.collect();
if new_violations.is_empty() {
Ok(())
} else {
Err(ApplyError::TypeUnsafe {
count: new_violations.len(),
mismatches: new_violations,
})
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use std::collections::BTreeMap;
use astrs_manifest::{Input, Manifest, Node, Urn};
use super::*;
use crate::edge::QueueConfig;
use crate::ids::PortName;
use crate::node::{InputPort, OutputPort};
fn manifest_graph(yaml: &str) -> DataflowGraph {
let manifest = Manifest::from_yaml_str(yaml).unwrap();
DataflowGraph::from_manifest(&manifest).unwrap().0
}
fn one_node() -> DataflowGraph {
manifest_graph("nodes:\n - id: camera\n path: ./camera\n outputs: [frames]\n")
}
fn two_nodes_wired() -> DataflowGraph {
manifest_graph(
"nodes:\n - id: camera\n path: ./camera\n outputs: [frames]\n \
- id: detector\n path: ./detector\n inputs: { frames: camera/frames }\n",
)
}
#[test]
fn diff_of_identical_graphs_is_empty() {
let g = two_nodes_wired();
assert!(diff(&g, &g).is_empty());
}
#[test]
fn diff_detects_added_node_and_edge() {
let a = one_node();
let b = two_nodes_wired();
let ops = diff(&a, &b);
assert!(
ops.iter().any(
|op| matches!(op, TopologyOp::AddNode { id, .. } if id.as_str() == "detector")
)
);
assert!(
ops.iter()
.any(|op| matches!(op, TopologyOp::AddEdge { .. }))
);
}
#[test]
fn diff_detects_removed_node_and_edge() {
let a = two_nodes_wired();
let b = one_node();
let ops = diff(&a, &b);
assert!(
ops.iter()
.any(|op| matches!(op, TopologyOp::RemoveNode { id } if id.as_str() == "detector"))
);
assert!(
ops.iter()
.any(|op| matches!(op, TopologyOp::RemoveEdge { .. }))
);
}
#[test]
fn round_trip_add_node_and_edge() {
let a = one_node();
let b = two_nodes_wired();
let ops = diff(&a, &b);
let reconstructed = apply(&a, &ops).unwrap();
assert_eq!(reconstructed, b);
}
#[test]
fn round_trip_remove_node_and_edge() {
let a = two_nodes_wired();
let b = one_node();
let ops = diff(&a, &b);
let reconstructed = apply(&a, &ops).unwrap();
assert_eq!(reconstructed, b);
}
#[test]
fn round_trip_replace_node_shape() {
let a = two_nodes_wired();
let b = manifest_graph(
"nodes:\n - id: camera\n path: ./camera\n outputs: [frames, debug]\n \
- id: detector\n path: ./detector\n inputs: { frames: camera/frames }\n",
);
let ops = diff(&a, &b);
assert!(
ops.iter().any(
|op| matches!(op, TopologyOp::ReplaceNode { id, .. } if id.as_str() == "camera")
)
);
let reconstructed = apply(&a, &ops).unwrap();
assert_eq!(reconstructed, b);
}
#[test]
fn round_trip_rewire_edge_to_a_new_source() {
let a = manifest_graph(
"nodes:\n - id: camera\n path: ./camera\n outputs: [frames]\n \
- id: camera2\n path: ./camera2\n outputs: [frames]\n \
- id: detector\n path: ./detector\n inputs: { frames: camera/frames }\n",
);
let b = manifest_graph(
"nodes:\n - id: camera\n path: ./camera\n outputs: [frames]\n \
- id: camera2\n path: ./camera2\n outputs: [frames]\n \
- id: detector\n path: ./detector\n inputs: { frames: camera2/frames }\n",
);
let ops = diff(&a, &b);
assert_eq!(ops.len(), 1);
assert!(matches!(ops[0], TopologyOp::AddEdge { .. }));
let reconstructed = apply(&a, &ops).unwrap();
assert_eq!(reconstructed, b);
}
#[test]
fn diff_does_not_cover_strict_types_or_type_rules() {
let mut a = one_node();
a.strict_types = false;
let mut b = one_node();
b.strict_types = true;
assert!(diff(&a, &b).is_empty());
}
#[test]
fn add_node_rejects_an_id_that_already_exists() {
let g = one_node();
let ops = vec![TopologyOp::AddNode {
id: NodeId::new("camera"),
node: g.node(&NodeId::new("camera")).unwrap().clone(),
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::NodeAlreadyExists { .. }));
}
#[test]
fn remove_node_rejects_an_absent_id() {
let g = one_node();
let ops = vec![TopologyOp::RemoveNode {
id: NodeId::new("ghost"),
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::NodeNotFound { .. }));
}
#[test]
fn remove_edge_rejects_an_absent_key() {
let g = one_node();
let ops = vec![TopologyOp::RemoveEdge {
key: EdgeKey::new(NodeId::new("camera"), PortName::new("nope")),
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::EdgeNotFound { .. }));
}
#[test]
fn replace_node_rejects_a_stale_old_value() {
let g = two_nodes_wired();
let current = g.node(&NodeId::new("camera")).unwrap().clone();
let mut stale = current.clone();
stale.outputs.insert(
PortName::new("not-actually-there"),
OutputPort { type_urn: None },
);
let ops = vec![TopologyOp::ReplaceNode {
id: NodeId::new("camera"),
old: stale,
new: current,
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::StaleReplace { .. }));
}
#[test]
fn remove_node_without_removing_its_edge_is_rejected() {
let g = two_nodes_wired();
let ops = vec![TopologyOp::RemoveNode {
id: NodeId::new("camera"),
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::DanglingProducer { .. }));
}
#[test]
fn add_edge_to_an_undeclared_input_is_rejected() {
let g = one_node();
let ops = vec![TopologyOp::AddEdge {
key: EdgeKey::new(NodeId::new("camera"), PortName::new("not-declared")),
edge: Edge {
from: EdgeSource::Virtual("astrs/status".to_string()),
queue: QueueConfig::default(),
},
}];
let err = apply(&g, &ops).unwrap_err();
assert!(matches!(err, ApplyError::UndeclaredInput { .. }));
}
#[test]
fn add_edge_from_an_undeclared_output_is_rejected() {
let a = two_nodes_wired();
let ops = vec![TopologyOp::AddEdge {
key: EdgeKey::new(NodeId::new("detector"), PortName::new("frames")),
edge: Edge {
from: EdgeSource::NodeOutput {
node: NodeId::new("camera"),
output: PortName::new("not-an-output"),
},
queue: QueueConfig::default(),
},
}];
let err = apply(&a, &ops).unwrap_err();
assert!(matches!(err, ApplyError::UndeclaredOutput { .. }));
}
#[test]
fn strict_mode_rejects_a_newly_introduced_mismatch() {
let mut camera = Node::with_path("camera", "./camera");
camera.outputs = vec!["frames".to_string()];
camera
.output_types
.insert("frames".to_string(), Urn::new("std/core/v1/Float32"));
let mut detector = Node::with_path("detector", "./detector");
detector
.inputs
.insert("frames".to_string(), Input::from_source("camera/frames"));
detector
.input_types
.insert("frames".to_string(), Urn::new("std/core/v1/Float64"));
let manifest = Manifest {
nodes: vec![camera, detector],
strict_types: true,
..Manifest::default()
};
let (full, _) = DataflowGraph::from_manifest(&manifest).unwrap();
let mut base_nodes = BTreeMap::new();
base_nodes.insert(
NodeId::new("camera"),
full.node(&NodeId::new("camera")).unwrap().clone(),
);
let base = DataflowGraph {
nodes: base_nodes,
edges: BTreeMap::new(),
strict_types: true,
type_rules: Vec::new(),
};
let edge_key = EdgeKey::new(NodeId::new("detector"), PortName::new("frames"));
let ops = vec![
TopologyOp::AddNode {
id: NodeId::new("detector"),
node: full.node(&NodeId::new("detector")).unwrap().clone(),
},
TopologyOp::AddEdge {
key: edge_key.clone(),
edge: full.edge(&edge_key).unwrap().clone(),
},
];
let err = apply(&base, &ops).unwrap_err();
assert!(matches!(err, ApplyError::TypeUnsafe { count: 1, .. }));
}
#[test]
fn pre_existing_mismatch_is_not_re_flagged_by_an_unrelated_op() {
let mut camera = Node::with_path("camera", "./camera");
camera.outputs = vec!["frames".to_string(), "extra".to_string()];
camera
.output_types
.insert("frames".to_string(), Urn::new("std/core/v1/Float32"));
let mut detector = Node::with_path("detector", "./detector");
detector
.inputs
.insert("frames".to_string(), Input::from_source("camera/frames"));
detector
.input_types
.insert("frames".to_string(), Urn::new("std/core/v1/Float64"));
let manifest = Manifest {
nodes: vec![camera, detector],
strict_types: true,
..Manifest::default()
};
let (graph, _) = DataflowGraph::from_manifest(&manifest).unwrap();
let mut extra_node = graph.node(&NodeId::new("detector")).unwrap().clone();
extra_node
.inputs
.insert(PortName::new("extra"), InputPort { type_urn: None });
let ops = vec![
TopologyOp::ReplaceNode {
id: NodeId::new("detector"),
old: graph.node(&NodeId::new("detector")).unwrap().clone(),
new: extra_node,
},
TopologyOp::AddEdge {
key: EdgeKey::new(NodeId::new("detector"), PortName::new("extra")),
edge: Edge {
from: EdgeSource::NodeOutput {
node: NodeId::new("camera"),
output: PortName::new("extra"),
},
queue: QueueConfig::default(),
},
},
];
let result = apply(&graph, &ops).unwrap();
assert_eq!(result.node_count(), 2);
}
}