1use alloc::vec::Vec;
2
3use crate::storage::{reserve_entries, StorageResource};
4use crate::{ExprId, ExprNode, GraphError};
5
6#[derive(Debug, Eq, PartialEq)]
7pub struct ExprGraph {
8 nodes: Vec<ExprNode>,
9}
10
11impl ExprGraph {
12 pub fn new() -> Self {
13 Self { nodes: Vec::new() }
14 }
15
16 pub fn len(&self) -> usize {
17 self.nodes.len()
18 }
19
20 pub fn is_empty(&self) -> bool {
21 self.nodes.is_empty()
22 }
23
24 pub fn get(&self, id: ExprId) -> Option<&ExprNode> {
25 usize::try_from(id.get())
26 .ok()
27 .and_then(|index| self.nodes.get(index))
28 }
29
30 pub fn push(&mut self, node: ExprNode) -> Result<ExprId, GraphError> {
31 let next = next_expr_id(self.nodes.len())?;
32 validate_children(&node, next)?;
33 let required = self
34 .nodes
35 .len()
36 .checked_add(1)
37 .ok_or(GraphError::IdExhausted)?;
38 reserve_entries(&mut self.nodes, required, StorageResource::GraphNodes)
39 .map_err(GraphError::Storage)?;
40 self.nodes.push(node);
41 Ok(next)
42 }
43
44 pub fn try_clone(&self) -> Result<Self, GraphError> {
45 let mut nodes = Vec::new();
46 reserve_entries(&mut nodes, self.nodes.len(), StorageResource::GraphNodes)
47 .map_err(GraphError::Storage)?;
48 for node in &self.nodes {
49 nodes.push(node.try_clone().map_err(graph_node_error)?);
50 }
51 Ok(Self { nodes })
52 }
53}
54
55impl Default for ExprGraph {
56 fn default() -> Self {
57 Self::new()
58 }
59}
60
61fn graph_node_error(error: crate::EvalError) -> GraphError {
62 GraphError::Node(graph_node_payload(error))
63}
64
65fn graph_node_payload(error: crate::EvalError) -> crate::EvalError {
66 error
67}
68
69fn next_expr_id(length: usize) -> Result<ExprId, GraphError> {
70 u32::try_from(length)
71 .map(ExprId::new)
72 .map_err(|_| GraphError::IdExhausted)
73}
74
75fn validate_child(child: ExprId, next: ExprId) -> Result<(), GraphError> {
76 if child < next {
77 Ok(())
78 } else {
79 Err(GraphError::InvalidChildId { child, next })
80 }
81}
82
83fn validate_children(node: &ExprNode, next: ExprId) -> Result<(), GraphError> {
84 match node {
85 ExprNode::Atom(_) => Ok(()),
86 ExprNode::Neg(child) => validate_child(*child, next),
87 ExprNode::Add(left, right)
88 | ExprNode::Sub(left, right)
89 | ExprNode::Mul(left, right)
90 | ExprNode::Div(left, right) => {
91 validate_child(*left, next)?;
92 validate_child(*right, next)
93 }
94 ExprNode::Pow { base, .. } => validate_child(*base, next),
95 }
96}
97
98#[cfg(test)]
99mod tests {
100 use neco_bigint::{BigInt, BigintError, ReducedRational};
101
102 use super::next_expr_id;
103 use crate::value::{with_clone_failure, CloneContact};
104 use crate::{AtomId, EvalError, ExprGraph, ExprId, ExprNode, GraphError};
105
106 #[test]
107 fn next_id_rejects_values_above_u32() {
108 if usize::BITS > u32::BITS {
109 assert_eq!(
110 next_expr_id((u32::MAX as usize) + 1),
111 Err(GraphError::IdExhausted)
112 );
113 }
114 }
115
116 #[test]
117 fn graph_accepts_only_existing_children() {
118 let mut graph = ExprGraph::new();
119 let atom = graph.push(ExprNode::Atom(AtomId::new(4))).unwrap();
120 assert_eq!(atom, ExprId::new(0));
121
122 let add = graph
123 .push(ExprNode::Add(ExprId::new(0), ExprId::new(0)))
124 .unwrap();
125 assert_eq!(add, ExprId::new(1));
126 assert_eq!(graph.len(), 2);
127
128 assert_eq!(
129 graph.push(ExprNode::Neg(ExprId::new(2))),
130 Err(GraphError::InvalidChildId {
131 child: ExprId::new(2),
132 next: ExprId::new(2),
133 })
134 );
135 assert_eq!(graph.len(), 2);
136
137 assert_eq!(
138 graph.push(ExprNode::Mul(ExprId::new(0), ExprId::new(3))),
139 Err(GraphError::InvalidChildId {
140 child: ExprId::new(3),
141 next: ExprId::new(2),
142 })
143 );
144 assert_eq!(graph.len(), 2);
145 }
146
147 #[test]
148 fn graph_clone_preserves_node_order() {
149 let mut graph = ExprGraph::new();
150 graph.push(ExprNode::Atom(AtomId::new(7))).unwrap();
151 graph.push(ExprNode::Neg(ExprId::new(0))).unwrap();
152
153 assert_eq!(graph.try_clone().unwrap(), graph);
154 }
155
156 #[test]
157 fn exponent_clone_failure_keeps_the_bigint_payload() {
158 let node = ExprNode::Pow {
159 base: ExprId::new(0),
160 exponent: ReducedRational::from_bigint(BigInt::one().unwrap()).unwrap(),
161 };
162 assert_eq!(
163 with_clone_failure(CloneContact::Exponent, || node.try_clone()),
164 Err(EvalError::Bigint(BigintError::AllocationFailure {
165 requested_limbs: 17,
166 }))
167 );
168 }
169
170 #[test]
171 fn graph_clone_wraps_node_failure_and_preserves_its_payload() {
172 let mut graph = ExprGraph::new();
173 let atom = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
174 graph
175 .push(ExprNode::Pow {
176 base: atom,
177 exponent: ReducedRational::from_bigint(BigInt::one().unwrap()).unwrap(),
178 })
179 .unwrap();
180 assert_eq!(
181 with_clone_failure(CloneContact::Exponent, || graph.try_clone()),
182 Err(GraphError::Node(EvalError::Bigint(
183 BigintError::AllocationFailure {
184 requested_limbs: 17,
185 }
186 )))
187 );
188 assert_eq!(graph.len(), 2);
189 }
190}