sim_lib_machine/
shuffle.rs

1use crate::{StackError, UnitStack, ValueWidthPolicy};
2
3/// Failure to construct or execute a logical stack shuffle.
4#[derive(Clone, Debug, PartialEq, Eq)]
5pub enum ShuffleError {
6    /// A logical value group has no units.
7    ZeroWidthGroup {
8        /// Index of the invalid group, counted from the bottom of the stack.
9        group: usize,
10    },
11    /// An output unit does not name a unit in the input layout.
12    UnknownUnit {
13        /// Invalid logical input-unit index.
14        unit: usize,
15    },
16    /// An output layout selects only part of a value group or changes its unit order.
17    SplitGroup {
18        /// Index of the offending group, counted from the bottom of the stack.
19        group: usize,
20    },
21    /// The live stack does not have the layout for which the plan was validated.
22    LayoutMismatch {
23        /// First expected group that was absent or had a different width.
24        group: usize,
25        /// Width recorded in the plan, or zero when the plan has no such group.
26        expected: usize,
27        /// Width found on the stack, or zero when the stack has no such group.
28        actual: usize,
29    },
30    /// The staged output cannot be represented by the operand stack.
31    Stack(StackError),
32}
33
34/// A validated permutation and duplication of whole logical value groups.
35///
36/// Input and output units are numbered from the bottom of the stack. The
37/// unit-level constructor makes decoded stack-machine instructions convenient
38/// to express while ensuring execution can never split a multi-unit value.
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub struct ShufflePlan {
41    input_widths: Vec<usize>,
42    output_groups: Vec<usize>,
43}
44
45impl ShufflePlan {
46    /// Validates a unit-level output layout against whole input value groups.
47    ///
48    /// A group may be omitted, moved, or repeated. Every occurrence must name
49    /// all of its units exactly once and in their original order.
50    pub fn new(
51        input_widths: impl IntoIterator<Item = usize>,
52        output_units: impl IntoIterator<Item = usize>,
53    ) -> Result<Self, ShuffleError> {
54        let input_widths: Vec<_> = input_widths.into_iter().collect();
55        let mut unit_to_group = Vec::new();
56        let mut starts = Vec::with_capacity(input_widths.len());
57        for (group, &width) in input_widths.iter().enumerate() {
58            if width == 0 {
59                return Err(ShuffleError::ZeroWidthGroup { group });
60            }
61            starts.push(unit_to_group.len());
62            unit_to_group.extend(std::iter::repeat_n(group, width));
63        }
64
65        let output_units: Vec<_> = output_units.into_iter().collect();
66        let mut output_groups = Vec::new();
67        let mut cursor = 0;
68        while cursor < output_units.len() {
69            let unit = output_units[cursor];
70            let Some(&group) = unit_to_group.get(unit) else {
71                return Err(ShuffleError::UnknownUnit { unit });
72            };
73            let start = starts[group];
74            let width = input_widths[group];
75            let end = cursor.saturating_add(width);
76            let whole_group = output_units
77                .get(cursor..end)
78                .is_some_and(|units| units.iter().copied().eq(start..start + width));
79            if !whole_group {
80                return Err(ShuffleError::SplitGroup { group });
81            }
82            output_groups.push(group);
83            cursor = end;
84        }
85
86        Ok(Self {
87            input_widths,
88            output_groups,
89        })
90    }
91
92    /// Applies the plan atomically, leaving `stack` untouched on every error.
93    pub fn execute<P>(&self, stack: &mut UnitStack<P>) -> Result<(), ShuffleError>
94    where
95        P: ValueWidthPolicy,
96        P::Value: Clone,
97    {
98        let common = self.input_widths.len().min(stack.values.len());
99        for group in 0..common {
100            let actual = P::width(&stack.values[group]);
101            let expected = self.input_widths[group];
102            if actual != expected {
103                return Err(ShuffleError::LayoutMismatch {
104                    group,
105                    expected,
106                    actual,
107                });
108            }
109        }
110        if self.input_widths.len() != stack.values.len() {
111            let group = common;
112            return Err(ShuffleError::LayoutMismatch {
113                group,
114                expected: self.input_widths.get(group).copied().unwrap_or(0),
115                actual: stack.values.get(group).map(P::width).unwrap_or(0),
116            });
117        }
118
119        let mut staged = UnitStack::<P>::new(stack.limit);
120        for &group in &self.output_groups {
121            staged
122                .push(stack.values[group].clone())
123                .map_err(ShuffleError::Stack)?;
124        }
125        *stack = staged;
126        Ok(())
127    }
128}
sim_lib_machine/shuffle.rs

sim_lib_machine/
shuffle.rs
