torg_core/
eval.rs

1//! Circuit evaluator for TØR-G graphs.
2//!
3//! Provides high-performance evaluation of boolean circuits using
4//! direct array indexing instead of hash maps.
5
6use std::collections::HashMap;
7
8use crate::error::EvalError;
9use crate::graph::Graph;
10use crate::token::Source;
11
12/// Evaluate a TØR-G graph with given input values (HashMap API).
13///
14/// This is a convenience wrapper around [`evaluate_into`] for callers
15/// that prefer HashMap-based input/output.
16///
17/// # Arguments
18///
19/// * `graph` - The graph to evaluate
20/// * `inputs` - Map from input IDs to their boolean values
21///
22/// # Returns
23///
24/// Map from output IDs to their computed boolean values.
25///
26/// # Errors
27///
28/// Returns an error if a required input is missing.
29pub fn evaluate(
30    graph: &Graph,
31    inputs: &HashMap<u16, bool>,
32) -> Result<HashMap<u16, bool>, EvalError> {
33    // Verify all declared inputs have values
34    for &id in &graph.inputs {
35        if !inputs.contains_key(&id) {
36            return Err(EvalError::MissingInput(id));
37        }
38    }
39
40    // Convert to slice-based format
41    let max_input_id = graph.inputs.iter().copied().max().unwrap_or(0) as usize;
42    let mut input_values = vec![false; max_input_id + 1];
43    for &id in &graph.inputs {
44        input_values[id as usize] = inputs[&id];
45    }
46
47    // Evaluate using fast path
48    let output_values = evaluate_graph(graph, &input_values);
49
50    // Convert output to HashMap
51    let mut result = HashMap::with_capacity(graph.outputs.len());
52    for (i, &id) in graph.outputs.iter().enumerate() {
53        result.insert(id, output_values[i]);
54    }
55
56    Ok(result)
57}
58
59/// Evaluate a graph and return output values as a Vec.
60///
61/// This is the fastest evaluation path. Input values are provided as a slice
62/// indexed by input ID. Returns output values in the same order as `graph.outputs`.
63///
64/// # Arguments
65///
66/// * `graph` - The graph to evaluate
67/// * `inputs` - Slice of boolean values indexed by input ID. Must be large enough
68///   to contain all input IDs (i.e., `inputs.len() > max_input_id`).
69///
70/// # Returns
71///
72/// Vec of output values in the same order as `graph.outputs`.
73///
74/// # Panics
75///
76/// Panics if `inputs` is too small to contain all input IDs.
77#[inline]
78pub fn evaluate_graph(graph: &Graph, inputs: &[bool]) -> Vec<bool> {
79    let mut outputs = vec![false; graph.outputs.len()];
80    evaluate_into(graph, inputs, &mut outputs);
81    outputs
82}
83
84/// Evaluate a graph into a pre-allocated output buffer.
85///
86/// This is the zero-allocation evaluation path for hot loops.
87///
88/// # Arguments
89///
90/// * `graph` - The graph to evaluate
91/// * `inputs` - Slice of boolean values indexed by input ID
92/// * `outputs` - Pre-allocated output buffer (must have length >= graph.outputs.len())
93///
94/// # Panics
95///
96/// Panics if `inputs` or `outputs` are too small.
97#[inline]
98pub fn evaluate_into(graph: &Graph, inputs: &[bool], outputs: &mut [bool]) {
99    // Fast path: empty graph
100    if graph.nodes.is_empty() {
101        // Outputs are just input references
102        for (i, &id) in graph.outputs.iter().enumerate() {
103            outputs[i] = inputs[id as usize];
104        }
105        return;
106    }
107
108    // Compute max ID to size the values array
109    let max_node_id = graph.nodes.iter().map(|n| n.id).max().unwrap_or(0);
110    let max_input_id = graph.inputs.iter().copied().max().unwrap_or(0);
111    let max_id = max_node_id.max(max_input_id) as usize;
112
113    // Pre-allocate values array (indexed by ID)
114    let mut values = vec![false; max_id + 1];
115
116    // Load input values
117    for &id in &graph.inputs {
118        values[id as usize] = inputs[id as usize];
119    }
120
121    // Evaluate nodes in topological order
122    for node in &graph.nodes {
123        let left = resolve_source_fast(&node.left, &values);
124        let right = resolve_source_fast(&node.right, &values);
125        values[node.id as usize] = node.op.eval(left, right);
126    }
127
128    // Write outputs
129    for (i, &id) in graph.outputs.iter().enumerate() {
130        outputs[i] = values[id as usize];
131    }
132}
133
134/// Resolve a source operand using direct array indexing.
135#[inline(always)]
136fn resolve_source_fast(source: &Source, values: &[bool]) -> bool {
137    match source {
138        Source::True => true,
139        Source::False => false,
140        Source::Id(id) => values[*id as usize],
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use crate::graph::Node;
148    use crate::token::BoolOp;
149
150    #[test]
151    fn test_simple_or() {
152        let graph = Graph {
153            inputs: vec![0, 1],
154            nodes: vec![Node::new(2, BoolOp::Or, Source::Id(0), Source::Id(1))],
155            outputs: vec![2],
156        };
157
158        // false OR false = false
159        let result = evaluate(&graph, &[(0, false), (1, false)].into()).unwrap();
160        assert!(!result[&2]);
161
162        // false OR true = true
163        let result = evaluate(&graph, &[(0, false), (1, true)].into()).unwrap();
164        assert!(result[&2]);
165
166        // true OR false = true
167        let result = evaluate(&graph, &[(0, true), (1, false)].into()).unwrap();
168        assert!(result[&2]);
169
170        // true OR true = true
171        let result = evaluate(&graph, &[(0, true), (1, true)].into()).unwrap();
172        assert!(result[&2]);
173    }
174
175    #[test]
176    fn test_constants() {
177        let graph = Graph {
178            inputs: vec![],
179            nodes: vec![Node::new(0, BoolOp::Or, Source::True, Source::False)],
180            outputs: vec![0],
181        };
182
183        let result = evaluate(&graph, &HashMap::new()).unwrap();
184        assert!(result[&0]); // true OR false = true
185    }
186
187    #[test]
188    fn test_chain_evaluation() {
189        // node(2) = input(0) XOR input(1)
190        // node(3) = node(2) OR True
191        let graph = Graph {
192            inputs: vec![0, 1],
193            nodes: vec![
194                Node::new(2, BoolOp::Xor, Source::Id(0), Source::Id(1)),
195                Node::new(3, BoolOp::Or, Source::Id(2), Source::True),
196            ],
197            outputs: vec![3],
198        };
199
200        // 0 XOR 0 = 0, 0 OR true = true
201        let result = evaluate(&graph, &[(0, false), (1, false)].into()).unwrap();
202        assert!(result[&3]);
203    }
204
205    #[test]
206    fn test_missing_input() {
207        let graph = Graph {
208            inputs: vec![0, 1],
209            nodes: vec![Node::new(2, BoolOp::Or, Source::Id(0), Source::Id(1))],
210            outputs: vec![2],
211        };
212
213        // Missing input 1
214        let result = evaluate(&graph, &[(0, false)].into());
215        assert_eq!(result, Err(EvalError::MissingInput(1)));
216    }
217
218    #[test]
219    fn test_nor_operation() {
220        let graph = Graph {
221            inputs: vec![0, 1],
222            nodes: vec![Node::new(2, BoolOp::Nor, Source::Id(0), Source::Id(1))],
223            outputs: vec![2],
224        };
225
226        // false NOR false = true
227        let result = evaluate(&graph, &[(0, false), (1, false)].into()).unwrap();
228        assert!(result[&2]);
229
230        // Any true = false
231        let result = evaluate(&graph, &[(0, true), (1, false)].into()).unwrap();
232        assert!(!result[&2]);
233    }
234
235    #[test]
236    fn test_evaluate_graph_fast() {
237        let graph = Graph {
238            inputs: vec![0, 1],
239            nodes: vec![Node::new(2, BoolOp::Or, Source::Id(0), Source::Id(1))],
240            outputs: vec![2],
241        };
242
243        // Use slice-based API
244        let inputs = [false, true]; // id 0 = false, id 1 = true
245        let outputs = evaluate_graph(&graph, &inputs);
246        assert_eq!(outputs, vec![true]); // false OR true = true
247    }
248
249    #[test]
250    fn test_evaluate_into_zero_alloc() {
251        let graph = Graph {
252            inputs: vec![0, 1],
253            nodes: vec![
254                Node::new(2, BoolOp::Or, Source::Id(0), Source::Id(1)),
255                Node::new(3, BoolOp::Xor, Source::Id(0), Source::Id(1)),
256            ],
257            outputs: vec![2, 3],
258        };
259
260        let inputs = [true, false];
261        let mut outputs = [false, false];
262        evaluate_into(&graph, &inputs, &mut outputs);
263
264        assert_eq!(outputs[0], true); // true OR false = true
265        assert_eq!(outputs[1], true); // true XOR false = true
266    }
267}
torg_core/eval.rs

torg_core/
eval.rs
