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