trellis_core/
graph.rs

1use crate::{
2    AuditState, DependencyList, DerivedNode, GraphError, GraphResult, InputNode, NodeHandle,
3    NodeId, NodeKind, NodeMeta, OutputKey, OutputMeta, Revision, ScopeId, ScopeMeta, Transaction,
4    TransactionId, TransactionOptions,
5    collection::{CollectionSpec, StoredCollection, StoredDiff},
6    derive::DerivedSpec,
7    input::{StoredInput, value_type},
8    output::OutputSpec,
9    resource::{ResourceKey, ResourcePlanner},
10};
11use std::collections::{BTreeMap, BTreeSet};
12
13/// Trellis graph skeleton with transactional input mutation.
14pub struct Graph<C = (), O = ()> {
15    pub(crate) next_node_id: u64,
16    pub(crate) next_scope_id: u64,
17    pub(crate) next_output_key: u64,
18    pub(crate) next_transaction_id: TransactionId,
19    pub(crate) revision: Revision,
20    pub(crate) nodes: BTreeMap<NodeId, NodeMeta>,
21    pub(crate) scopes: BTreeMap<ScopeId, ScopeMeta>,
22    pub(crate) input_values: BTreeMap<NodeId, Box<dyn StoredInput>>,
23    pub(crate) derived_specs: BTreeMap<NodeId, DerivedSpec<C, O>>,
24    pub(crate) derived_values: BTreeMap<NodeId, Box<dyn StoredInput>>,
25    pub(crate) collection_specs: BTreeMap<NodeId, CollectionSpec<C, O>>,
26    pub(crate) collection_values: BTreeMap<NodeId, Box<dyn StoredCollection>>,
27    pub(crate) previous_collection_values: BTreeMap<NodeId, Box<dyn StoredCollection>>,
28    pub(crate) collection_diffs: BTreeMap<NodeId, Box<dyn StoredDiff>>,
29    pub(crate) resource_planners: Vec<ResourcePlanner<C, O>>,
30    pub(crate) resource_owners: BTreeMap<ResourceKey, BTreeSet<ScopeId>>,
31    pub(crate) output_specs: BTreeMap<OutputKey, OutputSpec<C, O>>,
32    pub(crate) output_values: BTreeMap<OutputKey, O>,
33    pub(crate) outputs: BTreeMap<OutputKey, OutputMeta>,
34    pub(crate) audit: AuditState,
35    pub(crate) transaction_open: bool,
36}
37
38impl<C, O> Graph<C, O> {
39    /// Creates an empty graph.
40    pub fn new_with_command_type() -> Self {
41        Self {
42            next_node_id: 1,
43            next_scope_id: 1,
44            next_output_key: 1,
45            next_transaction_id: TransactionId::default(),
46            revision: Revision::default(),
47            nodes: BTreeMap::new(),
48            scopes: BTreeMap::new(),
49            input_values: BTreeMap::new(),
50            derived_specs: BTreeMap::new(),
51            derived_values: BTreeMap::new(),
52            collection_specs: BTreeMap::new(),
53            collection_values: BTreeMap::new(),
54            previous_collection_values: BTreeMap::new(),
55            collection_diffs: BTreeMap::new(),
56            resource_planners: Vec::new(),
57            resource_owners: BTreeMap::new(),
58            output_specs: BTreeMap::new(),
59            output_values: BTreeMap::new(),
60            outputs: BTreeMap::new(),
61            audit: AuditState::default(),
62            transaction_open: false,
63        }
64    }
65
66    /// Returns the graph revision.
67    pub fn revision(&self) -> Revision {
68        self.revision
69    }
70
71    /// Begins an input transaction with default options.
72    pub fn begin_transaction(&mut self) -> GraphResult<Transaction<'_, C, O>>
73    where
74        O: Clone + PartialEq,
75    {
76        self.begin_transaction_with_options(TransactionOptions::default())
77    }
78
79    /// Begins an input transaction with explicit options.
80    pub fn begin_transaction_with_options(
81        &mut self,
82        options: TransactionOptions,
83    ) -> GraphResult<Transaction<'_, C, O>>
84    where
85        O: Clone + PartialEq,
86    {
87        if self.transaction_open {
88            return Err(GraphError::NestedTransaction);
89        }
90
91        self.transaction_open = true;
92        let id = self.allocate_transaction_id();
93        Ok(Transaction::new(self, id, options))
94    }
95
96    pub(crate) fn create_scope_with_parent_direct(
97        &mut self,
98        id: ScopeId,
99        debug_name: impl Into<String>,
100        parent: Option<ScopeId>,
101    ) -> GraphResult<ScopeId> {
102        if let Some(parent) = parent {
103            let parent_meta = self.require_scope(parent)?;
104            if parent_meta.is_closed() {
105                return Err(GraphError::ScopeAlreadyClosed(parent));
106            }
107        }
108
109        self.scopes
110            .insert(id, ScopeMeta::new(id, debug_name, parent));
111        Ok(id)
112    }
113
114    pub(crate) fn input_direct<T>(
115        &mut self,
116        id: NodeId,
117        debug_name: impl Into<String>,
118    ) -> GraphResult<InputNode<T>>
119    where
120        T: Clone + PartialEq + 'static,
121    {
122        let meta = NodeMeta::new(
123            id,
124            NodeKind::Input,
125            debug_name,
126            DependencyList::empty(),
127            self.revision,
128            Some(value_type::<T>()),
129        );
130        self.nodes.insert(id, meta);
131        Ok(InputNode::new(id))
132    }
133
134    pub(crate) fn derived_direct<T>(
135        &mut self,
136        id: NodeId,
137        debug_name: impl Into<String>,
138        dependencies: DependencyList,
139        derive: impl for<'ctx> Fn(&crate::DeriveContext<'ctx, C, O>) -> Result<T, crate::DeriveError>
140        + 'static,
141    ) -> GraphResult<DerivedNode<T>>
142    where
143        T: Clone + PartialEq + 'static,
144    {
145        self.validate_dependencies(id, &dependencies)?;
146        self.reject_collection_dependencies(&dependencies)?;
147        let meta = NodeMeta::new(
148            id,
149            NodeKind::Derived,
150            debug_name,
151            dependencies,
152            self.revision,
153            Some(value_type::<T>()),
154        );
155        self.nodes.insert(id, meta);
156        self.derived_specs
157            .insert(id, DerivedSpec::<C, O>::new(derive));
158        Ok(DerivedNode::new(id))
159    }
160
161    pub(crate) fn attach_node_to_scope_direct(
162        &mut self,
163        node_id: NodeId,
164        scope: ScopeId,
165    ) -> GraphResult<()> {
166        let scope_meta = self.require_scope(scope)?;
167        if scope_meta.is_closed() {
168            return Err(GraphError::ScopeAlreadyClosed(scope));
169        }
170
171        let node_meta = self
172            .nodes
173            .get_mut(&node_id)
174            .ok_or(GraphError::UnknownNode(node_id))?;
175
176        if node_meta.owning_scope().is_some() {
177            return Err(GraphError::NodeAlreadyAttached(node_id));
178        }
179
180        node_meta.attach_scope(scope);
181        Ok(())
182    }
183
184    /// Returns metadata for a node.
185    pub fn node_meta<H: NodeHandle>(&self, node: H) -> Option<&NodeMeta> {
186        self.nodes.get(&node.id())
187    }
188
189    /// Returns metadata for a node id.
190    pub fn node_meta_by_id(&self, id: NodeId) -> Option<&NodeMeta> {
191        self.nodes.get(&id)
192    }
193
194    /// Returns metadata for a scope.
195    pub fn scope_meta(&self, id: ScopeId) -> Option<&ScopeMeta> {
196        self.scopes.get(&id)
197    }
198
199    /// Returns metadata for a materialized output.
200    pub fn output_meta(&self, key: OutputKey) -> Option<&OutputMeta> {
201        self.outputs.get(&key)
202    }
203
204    /// Returns declared dependencies for a node.
205    pub fn dependencies<H: NodeHandle>(&self, node: H) -> Option<&DependencyList> {
206        self.node_meta(node).map(NodeMeta::dependencies)
207    }
208
209    /// Returns all node metadata in stable id order.
210    pub fn nodes(&self) -> impl Iterator<Item = &NodeMeta> {
211        self.nodes.values()
212    }
213
214    /// Returns all scope metadata in stable id order.
215    pub fn scopes(&self) -> impl Iterator<Item = &ScopeMeta> {
216        self.scopes.values()
217    }
218
219    pub(crate) fn allocate_node_id(&mut self) -> NodeId {
220        let id = NodeId::from_index(self.next_node_id);
221        self.next_node_id += 1;
222        id
223    }
224
225    pub(crate) fn allocate_scope_id(&mut self) -> ScopeId {
226        let id = ScopeId::from_index(self.next_scope_id);
227        self.next_scope_id += 1;
228        id
229    }
230
231    pub(crate) fn allocate_output_key(&mut self) -> OutputKey {
232        let key = OutputKey::from_index(self.next_output_key);
233        self.next_output_key += 1;
234        key
235    }
236
237    fn allocate_transaction_id(&mut self) -> TransactionId {
238        self.next_transaction_id = self.next_transaction_id.next();
239        self.next_transaction_id
240    }
241
242    pub(crate) fn require_scope(&self, id: ScopeId) -> GraphResult<&ScopeMeta> {
243        self.scopes.get(&id).ok_or(GraphError::UnknownScope(id))
244    }
245
246    pub(crate) fn validate_dependencies(
247        &self,
248        node_id: NodeId,
249        dependencies: &DependencyList,
250    ) -> GraphResult<()> {
251        for dependency in dependencies.as_slice() {
252            if *dependency == node_id {
253                return Err(GraphError::SelfDependency(node_id));
254            }
255            if !self.nodes.contains_key(dependency) {
256                return Err(GraphError::UnknownNode(*dependency));
257            }
258            if self.depends_on(*dependency, node_id) {
259                return Err(GraphError::CycleDetected(node_id));
260            }
261        }
262        Ok(())
263    }
264
265    pub(crate) fn validate_output_dependencies(
266        &self,
267        dependencies: &DependencyList,
268    ) -> GraphResult<()> {
269        for dependency in dependencies.as_slice() {
270            if !self.nodes.contains_key(dependency) {
271                return Err(GraphError::UnknownNode(*dependency));
272            }
273        }
274        Ok(())
275    }
276
277    fn reject_collection_dependencies(&self, dependencies: &DependencyList) -> GraphResult<()> {
278        for dependency in dependencies.as_slice() {
279            if self
280                .nodes
281                .get(dependency)
282                .is_some_and(|meta| meta.kind() == NodeKind::Collection)
283            {
284                return Err(GraphError::CollectionDependencyNotAllowed(*dependency));
285            }
286        }
287        Ok(())
288    }
289
290    fn depends_on(&self, start: NodeId, target: NodeId) -> bool {
291        let Some(meta) = self.nodes.get(&start) else {
292            return false;
293        };
294        meta.dependencies()
295            .as_slice()
296            .iter()
297            .any(|dependency| *dependency == target || self.depends_on(*dependency, target))
298    }
299}
trellis_core/graph.rs

trellis_core/
graph.rs
