implicit_predicates_gen/
graph.rs

1//! Expression graphs with shared subexpressions.
2
3use std::collections::BTreeMap;
4
5/// Index of a node in [`Graph::nodes`].
6pub type NodeId = usize;
7
8/// One node of an expression graph.
9#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
10pub enum Node {
11    /// A coordinate of a point parameter.
12    Coord {
13        /// Index of the parameter.
14        point: usize,
15        /// Coordinate: 0, 1 and 2 are x, y and z.
16        axis: u8,
17    },
18    /// An integer constant.
19    Int(i64),
20    /// Sum of two nodes.
21    Add(NodeId, NodeId),
22    /// Difference of two nodes.
23    Sub(NodeId, NodeId),
24    /// Product of two nodes.
25    Mul(NodeId, NodeId),
26}
27
28/// A polynomial expression as a graph in which equal subexpressions share a
29/// node.
30///
31/// Children come before their parents, every node is reachable from the root,
32/// and the root is the last node. Unary minus is represented as `0 - x`.
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub struct Graph {
35    /// The nodes, in dependency order.
36    pub nodes: Vec<Node>,
37    /// The node holding the value of the whole expression.
38    pub root: NodeId,
39}
40
41impl Graph {
42    /// An upper bound on the total degree of the polynomial, found in one
43    /// pass without expanding it: a coordinate has degree 1, a constant 0, a
44    /// sum the larger degree of its operands and a product their sum,
45    /// saturated at `u64::MAX`. Terms that cancel can make the true degree
46    /// lower.
47    pub(crate) fn degree_bound(&self) -> u64 {
48        let mut degrees: Vec<u64> = Vec::with_capacity(self.nodes.len());
49        for node in &self.nodes {
50            degrees.push(match *node {
51                Node::Coord { .. } => 1,
52                Node::Int(_) => 0,
53                Node::Add(x, y) | Node::Sub(x, y) => degrees[x].max(degrees[y]),
54                Node::Mul(x, y) => degrees[x].saturating_add(degrees[y]),
55            });
56        }
57        degrees[self.root]
58    }
59}
60
61/// Builds a graph, giving equal nodes the same id.
62#[derive(Default)]
63pub(crate) struct Builder {
64    nodes: Vec<Node>,
65    index: BTreeMap<Node, NodeId>,
66}
67
68impl Builder {
69    /// Returns the id of `node`, adding it if it is new.
70    pub(crate) fn intern(&mut self, node: Node) -> NodeId {
71        *self.index.entry(node).or_insert_with(|| {
72            self.nodes.push(node);
73            self.nodes.len() - 1
74        })
75    }
76
77    /// Returns the id of `0 - x`.
78    pub(crate) fn negate(&mut self, x: NodeId) -> NodeId {
79        let zero = self.intern(Node::Int(0));
80        self.intern(Node::Sub(zero, x))
81    }
82
83    /// Keeps only the nodes reachable from `root`, in their original order.
84    pub(crate) fn finish(self, root: NodeId) -> Graph {
85        let mut live = vec![false; self.nodes.len()];
86        live[root] = true;
87        for id in (0..self.nodes.len()).rev() {
88            if !live[id] {
89                continue;
90            }
91            if let Node::Add(x, y) | Node::Sub(x, y) | Node::Mul(x, y) = self.nodes[id] {
92                live[x] = true;
93                live[y] = true;
94            }
95        }
96        let mut new_id = vec![0; self.nodes.len()];
97        let mut nodes = Vec::new();
98        for (id, node) in self.nodes.iter().enumerate().filter(|&(id, _)| live[id]) {
99            new_id[id] = nodes.len();
100            nodes.push(match *node {
101                Node::Add(x, y) => Node::Add(new_id[x], new_id[y]),
102                Node::Sub(x, y) => Node::Sub(new_id[x], new_id[y]),
103                Node::Mul(x, y) => Node::Mul(new_id[x], new_id[y]),
104                leaf => leaf,
105            });
106        }
107        Graph {
108            root: nodes.len() - 1,
109            nodes,
110        }
111    }
112}
implicit_predicates_gen/graph.rs

implicit_predicates_gen/
graph.rs
