Skip to main content

neco_expr/
graph.rs

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}