wasmtime_fuzzing/generators/gc_ops/
stack.rs

1//! The abstract operand stack `GcOps::fixup` tracks to make an op sequence valid.
2
3use crate::generators::gc_ops::ops::GcOp;
4use crate::generators::gc_ops::types::{TypeId, Types};
5
6/// Tracks the required operand type on the abstract value stack.
7#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
8pub enum StackType {
9    /// `externref`.
10    ExternRef,
11    /// `eqref`.
12    Eq,
13    /// `i31ref`.
14    I31,
15    /// `(ref $*)`, optionally with a concrete type index.
16    Struct(Option<u32>),
17    /// `(ref array)` or `(ref $t)`, optionally with a concrete type index.
18    Array(Option<u32>),
19}
20
21/// Whether the dense type index `sub` is the same as, or a subtype of, `sup`.
22fn is_subtype_dense(sub: u32, sup: u32, types: &Types, encoding_order: &[TypeId]) -> bool {
23    let sub = encoding_order.get(usize::try_from(sub).unwrap());
24    let sup = encoding_order.get(usize::try_from(sup).unwrap());
25    match (sub, sup) {
26        (Some(&sub), Some(&sup)) => types.is_subtype(sub, sup),
27        _ => false,
28    }
29}
30
31/// Whether `top` can serve as an operand of type `req`, including by subtyping.
32fn satisfies(req: StackType, top: StackType, types: &Types, encoding_order: &[TypeId]) -> bool {
33    use StackType::{Array, Eq, ExternRef, I31, Struct};
34    match (req, top) {
35        (ExternRef, ExternRef) | (I31, I31) => true,
36        // struct, array and i31 are all subtypes of eq.
37        (Eq, Eq | Struct(_) | Array(_) | I31) => true,
38        (Struct(None), Struct(_)) | (Array(None), Array(_)) => true,
39        (Struct(Some(want)), Struct(Some(have))) | (Array(Some(want)), Array(Some(have))) => {
40            is_subtype_dense(have, want, types, encoding_order)
41        }
42        _ => false,
43    }
44}
45
46/// The op that produces a value of type `req` from nothing, a null or a fresh
47/// object for a concrete type. Abstract nulls also cover the case of no types at all.
48fn synthesize(req: StackType, num_types: u32) -> GcOp {
49    match req {
50        StackType::ExternRef => GcOp::NullExtern,
51        StackType::Eq => GcOp::NullEq,
52        StackType::I31 => GcOp::RefI31 { value: 0 },
53        StackType::Struct(None) => GcOp::NullStruct,
54        StackType::Array(None) => GcOp::NullArray,
55        StackType::Struct(Some(t)) => {
56            debug_assert_ne!(num_types, 0, "typed struct requirement with no types");
57            GcOp::StructNew {
58                type_index: StackType::clamp(t, num_types),
59            }
60        }
61        StackType::Array(Some(t)) => {
62            debug_assert_ne!(num_types, 0, "typed array requirement with no types");
63            GcOp::ArrayNewDefault {
64                type_index: StackType::clamp(t, num_types),
65            }
66        }
67    }
68}
69
70impl StackType {
71    /// Ensure the top of `stack` satisfies `req`, emitting a fixup op if it does
72    /// not, then pop it. `None` (a `Drop` operand) takes anything.
73    pub fn fixup_operand(
74        req: Option<StackType>,
75        stack: &mut Vec<StackType>,
76        out: &mut Vec<GcOp>,
77        num_types: u32,
78        types: &Types,
79        encoding_order: &[TypeId],
80    ) {
81        let mut result_types = Vec::new();
82        match req {
83            None => {
84                if stack.is_empty() {
85                    Self::emit(GcOp::NullExtern, stack, out, num_types, &mut result_types);
86                }
87            }
88            Some(req) => {
89                let ok = stack
90                    .last()
91                    .is_some_and(|&top| satisfies(req, top, types, encoding_order));
92                if !ok {
93                    let op = synthesize(req, num_types);
94                    Self::emit(op, stack, out, num_types, &mut result_types);
95                }
96            }
97        }
98        let popped = stack.pop();
99        log::trace!("[StackType::fixup_operand] req={req:?} popped={popped:?} stack={stack:?}");
100    }
101
102    /// Emit an opcode and update the stack.
103    pub(crate) fn emit(
104        op: GcOp,
105        stack: &mut Vec<Self>,
106        out: &mut Vec<GcOp>,
107        num_types: u32,
108        result_types: &mut Vec<Self>,
109    ) {
110        log::trace!(
111            "[StackType::emit] op={op:?} stack_len_before={} num_types={num_types}",
112            stack.len()
113        );
114        out.push(op);
115        result_types.clear();
116        op.result_types(result_types);
117        for ty in result_types {
118            let clamped_ty = match ty {
119                Self::Struct(Some(t)) => Self::Struct(Some(Self::clamp(*t, num_types))),
120                Self::Array(Some(t)) => Self::Array(Some(Self::clamp(*t, num_types))),
121                other => *other,
122            };
123            log::trace!("[StackType::emit] push result {clamped_ty:?}");
124            stack.push(clamped_ty);
125        }
126        log::trace!("[StackType::emit] leave stack={stack:?}");
127    }
128
129    /// Fixup for cast ops: ensures the sub/super type relationship actually
130    /// holds. Always repairs the op rather than dropping it.
131    ///
132    /// For upcast the operand (sub) is on the stack, so we keep sub fixed
133    /// and adjust super. For downcast the operand (super) is on the stack,
134    /// so we keep super fixed and adjust sub.
135    pub fn fixup_cast(op: GcOp, types: &Types, encoding_order: &[TypeId]) -> GcOp {
136        match op {
137            GcOp::RefCastUpward {
138                sub_type_index,
139                super_type_index,
140            } => {
141                // Operand is sub (on the stack) — keep it, fix super.
142                let super_type_index = Self::find_supertype_of(
143                    sub_type_index,
144                    super_type_index,
145                    types,
146                    encoding_order,
147                );
148                GcOp::RefCastUpward {
149                    sub_type_index,
150                    super_type_index,
151                }
152            }
153            GcOp::RefCastDownward {
154                sub_type_index,
155                super_type_index,
156            } => {
157                // Operand is super (on the stack) — keep it, fix sub.
158                let sub_type_index =
159                    Self::find_subtype_of(super_type_index, sub_type_index, types, encoding_order);
160                GcOp::RefCastDownward {
161                    sub_type_index,
162                    super_type_index,
163                }
164            }
165            // Array casts use the same index repair (subtyping is kind-agnostic).
166            GcOp::ArrayRefCastUpward {
167                sub_type_index,
168                super_type_index,
169            } => {
170                let super_type_index = Self::find_supertype_of(
171                    sub_type_index,
172                    super_type_index,
173                    types,
174                    encoding_order,
175                );
176                GcOp::ArrayRefCastUpward {
177                    sub_type_index,
178                    super_type_index,
179                }
180            }
181            GcOp::ArrayRefCastDownward {
182                sub_type_index,
183                super_type_index,
184            } => {
185                let sub_type_index =
186                    Self::find_subtype_of(super_type_index, sub_type_index, types, encoding_order);
187                GcOp::ArrayRefCastDownward {
188                    sub_type_index,
189                    super_type_index,
190                }
191            }
192            other => other,
193        }
194    }
195
196    /// Given a sub type on the stack, find a valid super_type_index such
197    /// that sub <: super. Keeps sub fixed. Falls back to self-cast.
198    fn find_supertype_of(
199        sub_type_index: u32,
200        super_type_index: u32,
201        types: &Types,
202        encoding_order: &[TypeId],
203    ) -> u32 {
204        if let (Some(&sub_tid), Some(&super_tid)) = (
205            encoding_order.get(usize::try_from(sub_type_index).unwrap()),
206            encoding_order.get(usize::try_from(super_type_index).unwrap()),
207        ) {
208            // Already valid.
209            if types.is_subtype(sub_tid, super_tid) {
210                return super_type_index;
211            }
212            // Try sub's direct supertype.
213            if let Some(actual_super) = types.type_defs.get(&sub_tid).and_then(|d| d.supertype) {
214                if let Some(idx) = encoding_order.iter().position(|&t| t == actual_super) {
215                    return u32::try_from(idx).unwrap();
216                }
217            }
218        }
219        // Self-cast.
220        sub_type_index
221    }
222
223    /// Given a super type on the stack, find a valid sub_type_index such
224    /// that sub <: super. Keeps super fixed. Falls back to self-cast.
225    fn find_subtype_of(
226        super_type_index: u32,
227        sub_type_index: u32,
228        types: &Types,
229        encoding_order: &[TypeId],
230    ) -> u32 {
231        if let (Some(&sub_tid), Some(&super_tid)) = (
232            encoding_order.get(usize::try_from(sub_type_index).unwrap()),
233            encoding_order.get(usize::try_from(super_type_index).unwrap()),
234        ) {
235            // Already valid.
236            if types.is_subtype(sub_tid, super_tid) {
237                return sub_type_index;
238            }
239            // Try to find any direct subtype of super.
240            for (idx, tid) in encoding_order.iter().enumerate() {
241                if let Some(def) = types.type_defs.get(tid) {
242                    if def.supertype == Some(super_tid) {
243                        return u32::try_from(idx).unwrap();
244                    }
245                }
246            }
247        }
248        // Self-cast.
249        super_type_index
250    }
251
252    /// Clamp a type index to the number of types.
253    fn clamp(t: u32, n: u32) -> u32 {
254        if n == 0 { 0 } else { t % n }
255    }
256}
wasmtime_fuzzing/generators/gc_ops/stack.rs

wasmtime_fuzzing/generators/gc_ops/
stack.rs
