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
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}