axiolid_model/
graph.rs

1//! Immutable geometry DAG and append-only builder.
2
3use core::fmt;
4
5use crate::{id::GraphId, BuiltInNode, GeometryNode, NodeId};
6
7/// Invalid graph construction.
8#[non_exhaustive]
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub enum GraphError {
11    /// A node handle belongs to a different graph builder.
12    ForeignReference { reference: NodeId },
13    /// A node referenced itself or a later/not-yet-inserted node.
14    NonPriorReference { node: NodeId, reference: NodeId },
15    /// A reference resolves locally but points to the wrong node family.
16    InvalidReferenceType {
17        /// Existing node whose family is invalid for this edge.
18        reference: NodeId,
19        /// Human-readable family accepted by the edge.
20        expected: &'static str,
21        /// Human-readable family of the referenced node.
22        actual: &'static str,
23    },
24    /// A requested root does not exist.
25    UnknownRoot { root: NodeId, node_count: usize },
26    /// A master representation names a side the relation does not have.
27    ContradictoryMaster {
28        /// What the contradiction is, in the caller's terms.
29        detail: &'static str,
30    },
31}
32
33impl fmt::Display for GraphError {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            Self::ForeignReference { reference } => {
37                write!(f, "{reference} belongs to another geometry graph")
38            }
39            Self::NonPriorReference { node, reference } => {
40                write!(f, "{node} references non-prior {reference}")
41            }
42            Self::InvalidReferenceType {
43                reference,
44                expected,
45                actual,
46            } => write!(f, "{reference} has node type {actual}; expected {expected}"),
47            Self::ContradictoryMaster { detail } => {
48                write!(f, "contradictory surface-curve master: {detail}")
49            }
50            Self::UnknownRoot { root, node_count } => {
51                write!(f, "root {root} exceeds graph size {node_count}")
52            }
53        }
54    }
55}
56
57impl std::error::Error for GraphError {}
58
59/// Immutable acyclic geometry graph with one or more roots.
60#[derive(Debug, Clone, PartialEq)]
61pub struct GeometryGraph {
62    owner: GraphId,
63    nodes: Vec<GeometryNode>,
64    roots: Vec<NodeId>,
65}
66
67impl Default for GeometryGraph {
68    fn default() -> Self {
69        Self {
70            owner: GraphId::fresh(),
71            nodes: Vec::new(),
72            roots: Vec::new(),
73        }
74    }
75}
76
77impl GeometryGraph {
78    /// Number of nodes.
79    pub fn len(&self) -> usize {
80        self.nodes.len()
81    }
82
83    /// Whether the graph has no nodes.
84    pub fn is_empty(&self) -> bool {
85        self.nodes.is_empty()
86    }
87
88    /// Read a node by typed handle. A handle owned by another graph returns `None`.
89    pub fn get(&self, id: NodeId) -> Option<&GeometryNode> {
90        if !id.belongs_to(self.owner) {
91            return None;
92        }
93        self.nodes.get(id.index())
94    }
95
96    /// Output roots in caller-specified order.
97    pub fn roots(&self) -> &[NodeId] {
98        &self.roots
99    }
100
101    /// All nodes in stable topological insertion order.
102    pub fn iter(&self) -> impl ExactSizeIterator<Item = (NodeId, &GeometryNode)> {
103        self.nodes
104            .iter()
105            .enumerate()
106            .map(|(index, node)| (NodeId::from_index(self.owner, index), node))
107    }
108}
109
110/// Append-only builder that makes cycles and dangling references unrepresentable.
111#[derive(Debug)]
112pub struct GeometryGraphBuilder {
113    owner: Option<GraphId>,
114    nodes: Vec<GeometryNode>,
115}
116
117impl Default for GeometryGraphBuilder {
118    fn default() -> Self {
119        Self::new()
120    }
121}
122
123impl GeometryGraphBuilder {
124    /// Create an empty builder.
125    pub const fn new() -> Self {
126        Self {
127            owner: None,
128            nodes: Vec::new(),
129        }
130    }
131
132    /// Insert a node. Every reference must be to an earlier node.
133    pub fn push(&mut self, node: GeometryNode) -> Result<NodeId, GraphError> {
134        let owner = *self.owner.get_or_insert_with(GraphId::fresh);
135        let id = NodeId::from_index(owner, self.nodes.len());
136        let references = node.references();
137        if let Some(&reference) = references
138            .iter()
139            .find(|reference| !reference.belongs_to(owner))
140        {
141            return Err(GraphError::ForeignReference { reference });
142        }
143        if let Some(&reference) = references
144            .iter()
145            .find(|reference| reference.index() >= id.index())
146        {
147            return Err(GraphError::NonPriorReference {
148                node: id,
149                reference,
150            });
151        }
152        crate::validation::validate_reference_types(&node, &self.nodes)?;
153        self.nodes.push(node);
154        Ok(id)
155    }
156
157    /// Insert one canonical representation without spelling its enum variant.
158    ///
159    /// The accepted set is deliberately sealed; adapters must translate custom
160    /// values into a built-in neutral representation before graph construction.
161    pub fn push_value<T>(&mut self, value: T) -> Result<NodeId, GraphError>
162    where
163        T: BuiltInNode,
164    {
165        self.push(value.into())
166    }
167
168    /// Freeze the graph after validating roots.
169    pub fn finish(self, roots: Vec<NodeId>) -> Result<GeometryGraph, GraphError> {
170        let owner = self.owner.unwrap_or_else(GraphId::fresh);
171        if let Some(&reference) = roots.iter().find(|root| !root.belongs_to(owner)) {
172            return Err(GraphError::ForeignReference { reference });
173        }
174        if let Some(&root) = roots.iter().find(|root| root.index() >= self.nodes.len()) {
175            return Err(GraphError::UnknownRoot {
176                root,
177                node_count: self.nodes.len(),
178            });
179        }
180        Ok(GeometryGraph {
181            owner,
182            nodes: self.nodes,
183            roots,
184        })
185    }
186}
187
188#[cfg(test)]
189mod tests {
190    use axiolid_core::Vec3;
191
192    use super::*;
193    use crate::Instance;
194
195    const EMPTY_BUILDER: GeometryGraphBuilder = GeometryGraphBuilder::new();
196
197    #[test]
198    fn const_constructor_remains_source_compatible() {
199        assert!(EMPTY_BUILDER.finish(Vec::new()).unwrap().is_empty());
200    }
201
202    #[test]
203    fn insertion_order_is_topological_order() {
204        let mut builder = GeometryGraphBuilder::new();
205        let source = builder.push(GeometryNode::Point3(Vec3::ZERO)).unwrap();
206        let instance = builder
207            .push(GeometryNode::Instance(Instance {
208                source,
209                transform: axiolid_core::Transform3::IDENTITY,
210            }))
211            .unwrap();
212        let graph = builder.finish(vec![instance]).unwrap();
213        assert_eq!(graph.len(), 2);
214        assert_eq!(graph.roots(), &[instance]);
215    }
216
217    #[test]
218    fn sealed_built_in_values_have_an_ergonomic_builder_path() {
219        let mut builder = GeometryGraphBuilder::new();
220        let sphere = builder
221            .push_value(axiolid_primitive::Primitive::Sphere { radius: 1.0 })
222            .unwrap();
223        let graph = builder.finish(vec![sphere]).unwrap();
224        assert!(matches!(
225            graph.get(sphere),
226            Some(GeometryNode::Primitive(
227                axiolid_primitive::Primitive::Sphere { radius: 1.0 }
228            ))
229        ));
230    }
231
232    #[test]
233    fn handles_from_another_builder_cannot_alias_local_nodes() {
234        let mut foreign_builder = GeometryGraphBuilder::new();
235        let foreign = foreign_builder
236            .push(GeometryNode::Point3(Vec3::ZERO))
237            .unwrap();
238
239        let mut builder = GeometryGraphBuilder::new();
240        let local = builder.push(GeometryNode::Point3(Vec3::ZERO)).unwrap();
241        let error = builder
242            .push(GeometryNode::Instance(Instance {
243                source: foreign,
244                transform: axiolid_core::Transform3::IDENTITY,
245            }))
246            .unwrap_err();
247        assert!(matches!(
248            error,
249            GraphError::ForeignReference { reference } if reference == foreign
250        ));
251        let error = builder.finish(vec![foreign]).unwrap_err();
252        assert!(matches!(
253            error,
254            GraphError::ForeignReference { reference } if reference == foreign
255        ));
256
257        let graph = foreign_builder.finish(vec![foreign]).unwrap();
258        assert!(graph.get(local).is_none());
259    }
260
261    #[test]
262    fn semantic_reference_types_are_validated_before_insertion() {
263        let mut builder = GeometryGraphBuilder::new();
264        let point = builder.push(GeometryNode::Point3(Vec3::ZERO)).unwrap();
265        let error = builder
266            .push(GeometryNode::SolidOperation(
267                crate::SolidOperation::Extrusion {
268                    profile: point,
269                    direction: Vec3::Z,
270                    depth: 1.0,
271                },
272            ))
273            .unwrap_err();
274        assert!(matches!(
275            error,
276            GraphError::InvalidReferenceType {
277                reference,
278                expected: "profile",
279                actual: "point3",
280            } if reference == point
281        ));
282    }
283
284    #[test]
285    fn instance_nodes_preserve_their_source_reference_family() {
286        let mut builder = GeometryGraphBuilder::new();
287        let point = builder.push(GeometryNode::Point3(Vec3::ZERO)).unwrap();
288        let instance = builder
289            .push(GeometryNode::Instance(Instance {
290                source: point,
291                transform: axiolid_core::Transform3::IDENTITY,
292            }))
293            .unwrap();
294
295        let error = builder
296            .push(GeometryNode::SolidOperation(
297                crate::SolidOperation::Boolean {
298                    left: instance,
299                    right: instance,
300                    operator: axiolid_core::BooleanOperator::Union,
301                },
302            ))
303            .unwrap_err();
304        let GraphError::InvalidReferenceType {
305            reference,
306            expected,
307            actual,
308        } = error
309        else {
310            panic!("unexpected graph error: {error:?}");
311        };
312        assert_eq!(reference, instance);
313        assert_eq!(expected, "solid");
314        assert_eq!(actual, "instance");
315
316        let solid = builder
317            .push(GeometryNode::Primitive(
318                axiolid_primitive::Primitive::Sphere { radius: 1.0 },
319            ))
320            .unwrap();
321        let solid_instance = builder
322            .push(GeometryNode::Instance(Instance {
323                source: solid,
324                transform: axiolid_core::Transform3::IDENTITY,
325            }))
326            .unwrap();
327        assert!(builder
328            .push(GeometryNode::SolidOperation(
329                crate::SolidOperation::Boolean {
330                    left: solid_instance,
331                    right: solid_instance,
332                    operator: axiolid_core::BooleanOperator::Union,
333                },
334            ))
335            .is_ok());
336    }
337
338    #[test]
339    fn surface_curve_requires_a_three_dimensional_basis() {
340        let mut builder = GeometryGraphBuilder::new();
341        let curve_2d = builder
342            .push(GeometryNode::Curve2(axiolid_curve::Curve2::Line(
343                axiolid_curve::Line2 {
344                    origin: axiolid_core::Vec2::ZERO,
345                    direction: axiolid_core::Vec2::X,
346                },
347            )))
348            .unwrap();
349        let plane = builder
350            .push(GeometryNode::Surface(axiolid_surface::Surface::Plane(
351                axiolid_surface::Plane {
352                    frame: axiolid_core::Frame3 {
353                        origin: Vec3::ZERO,
354                        x: Vec3::X,
355                        y: Vec3::Y,
356                        z: Vec3::Z,
357                    },
358                },
359            )))
360            .unwrap();
361        let error = builder
362            .push(GeometryNode::CurveRelation(
363                crate::CurveRelation::SurfaceCurve {
364                    curve_3d: curve_2d,
365                    sides: crate::SurfaceSides::one(plane, curve_2d),
366                    master: crate::MasterRepresentation::Curve3d,
367                },
368            ))
369            .unwrap_err();
370        assert!(matches!(
371            error,
372            GraphError::InvalidReferenceType {
373                reference,
374                expected: "curve3",
375                actual: "curve2",
376            } if reference == curve_2d
377        ));
378
379        let curve_3d = builder
380            .push(GeometryNode::Curve3(axiolid_curve::Curve3::Line(
381                axiolid_curve::Line3 {
382                    origin: Vec3::ZERO,
383                    direction: Vec3::X,
384                },
385            )))
386            .unwrap();
387        let trimmed_3d = builder
388            .push(GeometryNode::CurveRelation(crate::CurveRelation::Trimmed {
389                basis: curve_3d,
390                start: Vec::new(),
391                end: Vec::new(),
392                sense_agreement: true,
393                preference: crate::TrimmingPreference::Unspecified,
394            }))
395            .unwrap();
396        assert!(builder
397            .push(GeometryNode::CurveRelation(
398                crate::CurveRelation::SurfaceCurve {
399                    curve_3d: trimmed_3d,
400                    sides: crate::SurfaceSides::one(plane, curve_2d),
401                    master: crate::MasterRepresentation::Curve3d,
402                },
403            ))
404            .is_ok());
405    }
406
407    #[test]
408    fn parameter_curve_requires_a_two_dimensional_reference() {
409        let mut builder = GeometryGraphBuilder::new();
410        let surface = builder
411            .push(GeometryNode::Surface(axiolid_surface::Surface::Plane(
412                axiolid_surface::Plane {
413                    frame: axiolid_core::Frame3 {
414                        origin: Vec3::ZERO,
415                        x: Vec3::X,
416                        y: Vec3::Y,
417                        z: Vec3::Z,
418                    },
419                },
420            )))
421            .unwrap();
422        let curve_3d = builder
423            .push(GeometryNode::Curve3(axiolid_curve::Curve3::Line(
424                axiolid_curve::Line3 {
425                    origin: Vec3::ZERO,
426                    direction: Vec3::X,
427                },
428            )))
429            .unwrap();
430        let error = builder
431            .push(GeometryNode::CurveRelation(
432                crate::CurveRelation::ParameterCurve {
433                    basis_surface: surface,
434                    reference_curve: curve_3d,
435                },
436            ))
437            .unwrap_err();
438        assert!(matches!(
439            error,
440            GraphError::InvalidReferenceType {
441                reference,
442                expected: "curve2",
443                actual: "curve3",
444            } if reference == curve_3d
445        ));
446    }
447}
axiolid_model/graph.rs

axiolid_model/
graph.rs
