jellyflow_core/core/
imports.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use super::{Graph, GraphId};
4
5/// Reserved metadata for a graph import.
6///
7/// The presence of an entry declares a dependency from the importing graph onto the imported
8/// graph. Additional metadata (aliasing, pinning, namespaces) can be added later without changing
9/// the key contract.
10#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize)]
11pub struct GraphImport {
12    /// Optional import alias for UI and authoring ergonomics.
13    #[serde(default, skip_serializing_if = "Option::is_none")]
14    pub alias: Option<String>,
15}
16
17#[derive(Debug, Clone, thiserror::Error, PartialEq, Eq)]
18pub enum GraphImportError {
19    #[error("import references missing graph: from={from} to={to}")]
20    MissingGraph { from: GraphId, to: GraphId },
21
22    #[error("import cycle detected")]
23    Cycle { cycle: Vec<GraphId> },
24}
25
26#[derive(Debug, Clone)]
27pub struct GraphImportClosure {
28    /// All reachable imports (excluding the root graph id).
29    pub reachable: BTreeSet<GraphId>,
30    /// Deterministic DFS postorder (dependencies first), excluding the root graph id.
31    pub order: Vec<GraphId>,
32}
33
34impl GraphImportClosure {
35    pub fn contains(&self, graph: GraphId) -> bool {
36        self.reachable.contains(&graph)
37    }
38}
39
40/// Resolves the transitive import closure for a graph id with deterministic semantics.
41///
42/// Determinism contract:
43/// - imports are traversed in `BTreeMap` key order (`GraphId` total order),
44/// - the resulting `order` is DFS postorder (dependencies appear before dependents).
45pub fn resolve_import_closure<'a>(
46    root_graph: &'a Graph,
47    resolver: impl FnMut(GraphId) -> Option<&'a Graph>,
48) -> Result<GraphImportClosure, GraphImportError> {
49    ImportClosureResolver::new(root_graph, resolver).finish()
50}
51
52#[derive(Debug, Clone, Copy, PartialEq, Eq)]
53enum ImportVisitMark {
54    Temporary,
55    Permanent,
56}
57
58struct ImportClosureResolver<'a, R>
59where
60    R: FnMut(GraphId) -> Option<&'a Graph>,
61{
62    root: GraphId,
63    root_graph: &'a Graph,
64    resolver: R,
65    marks: BTreeMap<GraphId, ImportVisitMark>,
66    stack: Vec<GraphId>,
67    closure: GraphImportClosure,
68}
69
70impl<'a, R> ImportClosureResolver<'a, R>
71where
72    R: FnMut(GraphId) -> Option<&'a Graph>,
73{
74    fn new(root_graph: &'a Graph, resolver: R) -> Self {
75        Self {
76            root: root_graph.graph_id,
77            root_graph,
78            resolver,
79            marks: BTreeMap::new(),
80            stack: Vec::new(),
81            closure: GraphImportClosure {
82                reachable: BTreeSet::new(),
83                order: Vec::new(),
84            },
85        }
86    }
87
88    fn finish(mut self) -> Result<GraphImportClosure, GraphImportError> {
89        self.visit(self.root, self.root)?;
90        Ok(self.closure)
91    }
92
93    fn visit(&mut self, node: GraphId, from: GraphId) -> Result<(), GraphImportError> {
94        match self.marks.get(&node).copied() {
95            Some(ImportVisitMark::Permanent) => return Ok(()),
96            Some(ImportVisitMark::Temporary) => return Err(self.cycle_error(node)),
97            None => {}
98        }
99
100        self.marks.insert(node, ImportVisitMark::Temporary);
101        self.stack.push(node);
102
103        for dep in self.dependencies(node, from)? {
104            self.closure.reachable.insert(dep);
105            self.visit(dep, node)?;
106        }
107
108        self.stack.pop();
109        self.marks.insert(node, ImportVisitMark::Permanent);
110
111        if node != self.root {
112            self.closure.order.push(node);
113        }
114
115        Ok(())
116    }
117
118    fn dependencies(
119        &mut self,
120        node: GraphId,
121        from: GraphId,
122    ) -> Result<Vec<GraphId>, GraphImportError> {
123        let imports = if node == self.root {
124            &self.root_graph.imports
125        } else {
126            let Some(graph) = (self.resolver)(node) else {
127                return Err(GraphImportError::MissingGraph { from, to: node });
128            };
129            &graph.imports
130        };
131
132        Ok(imports.keys().copied().collect())
133    }
134
135    fn cycle_error(&self, node: GraphId) -> GraphImportError {
136        if let Some(pos) = self.stack.iter().position(|id| *id == node) {
137            let mut cycle = self.stack[pos..].to_vec();
138            cycle.push(node);
139            return GraphImportError::Cycle { cycle };
140        }
141
142        GraphImportError::Cycle {
143            cycle: vec![node, node],
144        }
145    }
146}
jellyflow_core/core/imports.rs

jellyflow_core/core/
imports.rs
