autoperm/
solve.rs

1use crate::parse::StackEffectDiagram;
2use petgraph::prelude::*;
3
4/// Represents an instruction within the computation model
5#[derive(Debug, PartialEq, Eq, Clone, Hash)]
6pub enum Instruction {
7    /// Clear / Zero the cell at a given index
8    Clear {
9        /// The index of the cell to clear
10        cell: isize,
11    },
12    /// Delete the data in a cell and copy it to a list of other cells
13    Mov {
14        /// The index of the cell to Mov
15        cell: isize,
16        /// The list of cells to copy the data to.
17        ///
18        /// Note: This list will never contain `cell`
19        to: Vec<isize>,
20    },
21    /// Start the program with the assumption that the top of the stack is at a given index
22    Start {
23        /// The index of the top of the stack
24        cell: isize,
25    },
26    /// Change the top of the stack to a given index
27    Top {
28        /// The index of the new top of the stack
29        cell: isize,
30    },
31}
32
33/// Given a [`StackEffectDiagram`](crate::parse::StackEffectDiagram) generate a list of instructions
34/// to apply that diagram.
35///
36/// # Examples
37///
38/// ```
39/// use autoperm::{solve, Instruction, StackEffectDiagram};
40///
41/// // a b -- b a
42/// let diagram = StackEffectDiagram {
43///     inputs: 2,
44///     mapping: vec![1, 0],
45/// };
46///
47/// let instructions = solve(&diagram);
48///
49/// assert_eq!(instructions, vec![
50///     Instruction::Start { cell: 1},
51///     Instruction::Mov { cell: 1, to: vec![2] },
52///     Instruction::Mov { cell: 0, to: vec![1] },
53///     Instruction::Mov { cell: 2, to: vec![0] },
54///     Instruction::Top { cell: 1 },
55/// ]);
56/// ```
57pub fn solve(diagram: &StackEffectDiagram) -> Vec<Instruction> {
58    let mapping = &diagram.mapping;
59    let inputs = diagram.inputs;
60
61    // The index of the temporary variable. Place it above the highest item
62    let temp = std::cmp::max(inputs, mapping.len()) as isize;
63
64    let edges: Vec<_> = mapping.iter().enumerate().map(|(i, j)| (*j, i)).collect();
65
66    let mut digraph: DiGraph<(), (), usize> = DiGraph::from_edges(edges);
67
68    // if the number of outputs is less than the number of inputs those nodes need to be cleared
69    if mapping.len() < inputs {
70        (mapping.len()..inputs).for_each(|_| {
71            digraph.add_node(());
72        })
73    }
74
75    // Reversing the ouput of tarjan's strongly connected components creates the program
76    let tarjan = petgraph::algo::tarjan_scc(&digraph);
77    println!("{:?}", tarjan);
78
79    let mut instructions = vec![Instruction::Start { cell: inputs as isize - 1 }];
80
81    for component in tarjan {
82        if component.len() == 1 {
83            // get the neighbors as a usize
84            let neighbors = get_neighbors(&digraph, component[0]);
85            let index = component[0].index() as isize;
86
87            if neighbors.is_empty() {
88                if index < inputs as isize {
89                    instructions.push(Instruction::Clear { cell: index });
90                }
91            } else if neighbors.contains(&index) {
92                if neighbors.len() > 1 {
93                    instructions.push(Instruction::Mov { cell: index, to: vec![temp] });
94                    instructions.push(Instruction::Mov { cell: temp,  to: neighbors });
95                }
96            } else {
97                instructions.push(Instruction::Mov{ cell: index, to: neighbors});
98            }
99        } else {
100            let mut iter = component.into_iter();
101
102            let last_index = iter.next().unwrap();
103            let last_neighbors = get_neighbors(&digraph, last_index);
104
105            instructions.push(Instruction::Mov{ cell: last_index.index() as isize, to: vec![temp]} );
106
107            for node in iter {
108                let neighbors = get_neighbors(&digraph, node);
109                instructions.push(Instruction::Mov{ cell: node.index() as isize, to: neighbors });
110            }
111
112            instructions.push(Instruction::Mov{ cell: temp, to: last_neighbors});
113        }
114    }
115
116    instructions.push(Instruction::Top { cell: mapping.len() as isize - 1 });
117
118    instructions
119}
120
121fn get_neighbors<N, E, Ty, Ix>(graph: &Graph<N, E, Ty, Ix>, index: NodeIndex<Ix>) -> Vec<isize>
122where
123    Ty: petgraph::EdgeType,
124    Ix: petgraph::adj::IndexType,
125{
126    graph.neighbors(index).map(|i| i.index() as isize).collect()
127}
autoperm/solve.rs

autoperm/
solve.rs
