A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
use crate::generators::gc_ops::{
limits::GcOpsLimits,
ops::{GcOp, GcOps, OP_NAMES},
stack::StackType,
types::{ArrayType, CompositeType, FieldType, RecGroupId, StructField, TypeId, Types},
};
use mutatis;
use mutatis::mutators as m;
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};
use std::collections::BTreeSet;
use wasmparser;
use wasmprinter;
/// Flattened encoding order for use in tests.
fn encoding_order(types: &Types) -> Vec<TypeId> {
let type_to_group = types.type_to_group_map();
let mut grouped = Vec::new();
types.encoding_order_grouped(&mut grouped, &type_to_group);
grouped
.into_iter()
.flat_map(|(_, members)| members)
.collect()
}
/// Returns true iff `sub_index` is the same as or a subtype of `sup_index`.
///
/// The `encoding_order` slice maps dense indices (0, 1, 2, …) to
/// [`TypeId`]s in the same order they appear in the encoded Wasm binary.
fn is_subtype_index(
types: &Types,
sub_index: u32,
sup_index: u32,
encoding_order: &[TypeId],
) -> bool {
if sub_index == sup_index {
return true;
}
let sub = match encoding_order
.get(usize::try_from(sub_index).unwrap())
.copied()
{
Some(t) => t,
None => return false,
};
let sup = match encoding_order
.get(usize::try_from(sup_index).unwrap())
.copied()
{
Some(t) => t,
None => return false,
};
types.is_subtype(sub, sup)
}
/// Creates empty GcOps
fn empty_test_ops() -> GcOps {
let mut t = GcOps {
limits: GcOpsLimits {
num_params: 5,
num_globals: 5,
table_size: 5,
max_rec_groups: 5,
max_types: 5,
max_fields: 10,
array_length: 5,
},
ops: vec![],
types: Types::new(),
};
for i in 0..t.limits.max_rec_groups {
t.types.insert_rec_group(RecGroupId(i));
}
t
}
/// Creates GcOps with all default opcodes
fn test_ops(num_params: u32, num_globals: u32, table_size: u32) -> GcOps {
let mut t = GcOps {
limits: GcOpsLimits {
num_params,
num_globals,
table_size,
max_rec_groups: 7,
max_types: 10,
max_fields: 10,
array_length: 5,
},
ops: vec![
GcOp::NullExtern,
GcOp::Drop,
GcOp::Gc,
GcOp::LocalSet { local_index: 0 },
GcOp::LocalGet { local_index: 0 },
GcOp::GlobalSet { global_index: 0 },
GcOp::GlobalGet { global_index: 0 },
GcOp::StructNew { type_index: 0 },
],
types: Types::new(),
};
for i in 0..t.limits.max_rec_groups {
t.types.insert_rec_group(RecGroupId(i));
}
let mut rng = StdRng::seed_from_u64(0xC0FFEE);
if t.limits.max_rec_groups > 0 {
for i in 0..t.limits.max_types {
let gid = RecGroupId(rng.random_range(0..t.limits.max_rec_groups));
let is_final = false;
let supertype = None;
t.types
.insert_struct(TypeId(i), gid, is_final, supertype, Vec::new());
}
}
t
}
/// Check that a `GcOps` emits a valid Wasm binary, describing the failure if
/// not.
fn check_valid_wasm(ops: &GcOps) -> Result<(), String> {
let mut ops = ops.clone();
let wasm = ops.to_wasm_binary();
let feats = wasmparser::WasmFeatures::default()
| wasmparser::WasmFeatures::REFERENCE_TYPES
| wasmparser::WasmFeatures::GC
| wasmparser::WasmFeatures::GC_TYPES;
let mut validator = wasmparser::Validator::new_with_features(feats);
validator.validate_all(&wasm).map(|_| ()).map_err(|e| {
let wat =
wasmprinter::print_bytes(&wasm).unwrap_or_else(|e| format!("<disasm failed: {e}>"));
format!(
"Emitted Wasm binary is not valid!\n\n\
=== Validation Error ===\n\n\
{e}\n\n\
=== GcOps ===\n\n\
{ops:#?}\n\n\
=== Wat ===\n\n\
{wat}"
)
})
}
/// Validate that a GcOps produces a valid Wasm binary.
fn assert_valid_wasm(ops: &GcOps) {
if let Err(e) = check_valid_wasm(ops) {
panic!("{e}");
}
}
#[test]
fn always_produces_valid_wasm() {
let _ = env_logger::try_init();
mutatis::check::Check::new()
.iters(2048)
.shrink_iters(1024)
.seed(0xC0FFEE)
.run_with(
m::default::<GcOps>(),
[test_ops(5, 5, 5), empty_test_ops(), cast_test_ops(vec![])],
check_valid_wasm,
)
.unwrap();
}
/// Every limit must stay inside its declared range under mutation.
#[test]
fn limits_stay_in_range() -> mutatis::Result<()> {
use crate::generators::gc_ops::limits::{
ARRAY_LENGTH_RANGE, MAX_FIELDS_RANGE, MAX_REC_GROUPS_RANGE, MAX_TYPES_RANGE,
NUM_GLOBALS_RANGE, NUM_PARAMS_RANGE, TABLE_SIZE_RANGE,
};
let _ = env_logger::try_init();
let mut ops = test_ops(5, 5, 5);
ops.limits.fixup_limits();
let mut session = mutatis::Session::new().seed(0xC0FFEE);
for _ in 0..2048 {
session.mutate(&mut ops)?;
let l = &ops.limits;
assert!(NUM_PARAMS_RANGE.contains(&l.num_params), "{l:?}");
assert!(NUM_GLOBALS_RANGE.contains(&l.num_globals), "{l:?}");
assert!(TABLE_SIZE_RANGE.contains(&l.table_size), "{l:?}");
assert!(MAX_REC_GROUPS_RANGE.contains(&l.max_rec_groups), "{l:?}");
assert!(MAX_TYPES_RANGE.contains(&l.max_types), "{l:?}");
assert!(MAX_FIELDS_RANGE.contains(&l.max_fields), "{l:?}");
assert!(ARRAY_LENGTH_RANGE.contains(&l.array_length), "{l:?}");
}
Ok(())
}
#[test]
fn struct_new_removed_when_no_types() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut ops = test_ops(0, 0, 0);
ops.limits.max_types = 0;
ops.ops = vec![GcOp::StructNew { type_index: 42 }];
ops.fixup(&mut Vec::new());
assert!(
ops.ops
.iter()
.all(|op| !matches!(op, GcOp::StructNew { .. })),
"StructNew should be removed when there are no types"
);
Ok(())
}
#[test]
fn local_ops_removed_when_no_params() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut ops = test_ops(0, 0, 0);
ops.limits.num_params = 0;
ops.ops = vec![
GcOp::LocalGet { local_index: 42 },
GcOp::LocalSet { local_index: 99 },
];
ops.fixup(&mut Vec::new());
assert!(
ops.ops
.iter()
.all(|op| !matches!(op, GcOp::LocalGet { .. } | GcOp::LocalSet { .. })),
"LocalGet/LocalSet should be removed when there are no params"
);
Ok(())
}
#[test]
fn global_ops_removed_when_no_globals() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut ops = test_ops(0, 0, 0);
ops.limits.num_globals = 0;
ops.ops = vec![
GcOp::GlobalGet { global_index: 42 },
GcOp::GlobalSet { global_index: 99 },
];
ops.fixup(&mut Vec::new());
assert!(
ops.ops
.iter()
.all(|op| !matches!(op, GcOp::GlobalGet { .. } | GcOp::GlobalSet { .. })),
"GlobalGet/GlobalSet should be removed when there are no globals"
);
Ok(())
}
#[test]
fn every_op_generated() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut unseen_ops: std::collections::HashSet<_> = OP_NAMES.iter().copied().collect();
let mut res = empty_test_ops();
let mut session = mutatis::Session::new().seed(0xC0FFEE);
'outer: for _ in 0..=32768 {
session.mutate(&mut res)?;
for op in &res.ops {
unseen_ops.remove(op.name());
if unseen_ops.is_empty() {
break 'outer;
}
}
}
assert!(unseen_ops.is_empty(), "Failed to generate {unseen_ops:?}");
Ok(())
}
#[test]
fn i31_and_eq_upcast_ops_validate() -> mutatis::Result<()> {
let _ = env_logger::try_init();
// Exercise every new i31/eqref op end-to-end through encoding + validation.
let mut ops = test_ops(5, 5, 5);
ops.ops = vec![
// Create i31 values and route them through locals/globals/tables.
GcOp::RefI31 { value: 0x4000_0001 },
GcOp::I31LocalSet,
GcOp::I31LocalGet,
GcOp::I31GlobalSet,
GcOp::I31GlobalGet,
GcOp::I31TableSet { elem_index: 0 },
GcOp::I31TableGet { elem_index: 0 },
// Inline i31.get_s / i31.get_u (null-guarded).
GcOp::I31GetS,
GcOp::RefI31 { value: 7 },
GcOp::I31GetU,
// Null i31, then differential host check.
GcOp::NullI31,
GcOp::TakeI31Call,
GcOp::RefI31 { value: 0x7fff_ffff },
GcOp::TakeI31Call,
// Upcast i31 -> eqref and hand it to the eqref-taking host function.
GcOp::RefI31 { value: 1 },
GcOp::I31RefAsEq,
GcOp::TakeEqCall,
// Upcast abstract and concrete struct refs -> eqref.
GcOp::NullStruct,
GcOp::StructRefAsEq,
GcOp::TakeEqCall,
GcOp::StructNew { type_index: 0 },
GcOp::TypedStructRefAsEq { type_index: 0 },
GcOp::TakeEqCall,
];
assert_valid_wasm(&ops);
Ok(())
}
#[test]
fn emits_rec_groups_and_validates() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut ops = test_ops(5, 5, 5);
assert_valid_wasm(&ops);
let wasm = ops.to_wasm_binary();
let wat = wasmprinter::print_bytes(&wasm).expect("to WAT");
let recs = wat.matches("(rec").count();
let structs = wat.matches("(struct)").count();
assert_eq!(
recs,
ops.types.rec_groups.len(),
"one (rec) block per rec group"
);
assert_eq!(
structs,
ops.types.type_defs.len(),
"one (struct) per struct type in type_defs"
);
Ok(())
}
#[test]
fn fixup_check_types_and_indexes() -> mutatis::Result<()> {
let _ = env_logger::try_init();
let mut ops = test_ops(5, 5, 5);
// These `GcOp`s do not have their operands satisfied, and their results are
// not the operands of the next op, so `fixup` will need to deal with
// that. Additionally, their immediates are out-of-bounds of their
// respective index spaces, which `fixup` will also need to address.
ops.ops = vec![
GcOp::TakeTypedStructCall {
type_index: ops.limits.max_types + 7,
},
GcOp::GlobalSet {
global_index: ops.limits.num_globals * 2,
},
GcOp::StructNew {
type_index: ops.limits.max_types + 9,
},
GcOp::LocalSet {
local_index: ops.limits.num_params * 5,
},
];
// Call `fixup` to insert missing types, rewrite the immediates such that
// they are within their bounds, insert missing operands, and drop unused
// results.
ops.fixup(&mut Vec::new());
// Check that we got the expected `GcOp` sequence after `fixup`:
assert_eq!(
ops.ops,
[
// Inserted by `fixup` to satisfy `TakeTypedStructCall`'s operands.
GcOp::StructNew { type_index: 7 },
// The `type_index` is now valid.
GcOp::TakeTypedStructCall { type_index: 7 },
// Inserted by `fixup` to satisfy `GlobalSet`'s operands.
GcOp::NullExtern,
// The `global_index` is now valid.
GcOp::GlobalSet { global_index: 0 },
// The `type_index` is now valid.
GcOp::StructNew { type_index: 9 },
// Inserted by `fixup` to satisfy `LocalSet`'s operands.
GcOp::NullExtern,
// The `local_index` is now valid.
GcOp::LocalSet { local_index: 0 },
// Inserted by `fixup` to make sure the operand stack is empty at
// the end of the block.
GcOp::Drop,
]
);
// Verify that we generate a valid Wasm binary after calling `fixup`.
assert_valid_wasm(&ops);
Ok(())
}
#[test]
fn sort_types_by_supertype_orders_supertype_before_subtype_across_rec_groups() {
let mut types = Types::new();
let ga = RecGroupId(0);
let gb = RecGroupId(1);
let gc = RecGroupId(2);
let gd = RecGroupId(3);
types.insert_rec_group(ga);
types.insert_rec_group(gb);
types.insert_rec_group(gc);
types.insert_rec_group(gd);
let a = TypeId(0);
let b = TypeId(1);
let c = TypeId(2);
let d = TypeId(3);
// Cross-rec-group chain: C <: A <: B <: D.
types.insert_struct(a, ga, false, Some(b), Vec::new()); // A <: B
types.insert_struct(b, gb, false, Some(d), Vec::new()); // B <: D
types.insert_struct(c, gc, false, Some(a), Vec::new()); // C <: A
types.insert_struct(d, gd, false, None, Vec::new()); // D
let mut sorted = Vec::new();
types.sort_types_topo(&mut sorted);
// Rec-group boundaries do not change topological ordering by supertype.
assert_eq!(
sorted,
[TypeId(3), TypeId(1), TypeId(0), TypeId(2)],
"topo order: supertype before subtype across rec groups"
);
}
#[test]
fn fixup_preserves_subtyping_within_same_rec_group() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g = RecGroupId(0);
types.insert_rec_group(g);
let super_ty = TypeId(0);
let sub_ty = TypeId(1);
// Both types are in the same rec group.
// The second subtypes the first.
types.insert_struct(super_ty, g, false, None, Vec::new());
types.insert_struct(sub_ty, g, false, Some(super_ty), Vec::new());
let limits = GcOpsLimits {
num_params: 0,
num_globals: 0,
table_size: 0,
max_rec_groups: 10,
max_types: 10,
max_fields: 10,
array_length: 5,
};
types.fixup_types(&limits, &mut Vec::new());
assert_eq!(types.rec_group_of(super_ty), Some(g));
assert_eq!(types.rec_group_of(sub_ty), Some(g));
assert_eq!(
types.type_defs.get(&sub_ty).unwrap().supertype,
Some(super_ty)
);
}
#[test]
fn fixup_breaks_one_edge_in_multi_rec_group_type_cycle() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g_a = RecGroupId(0);
let g_bc = RecGroupId(1);
let g_d = RecGroupId(2);
types.insert_rec_group(g_a);
types.insert_rec_group(g_bc);
types.insert_rec_group(g_d);
let a = TypeId(0);
let b = TypeId(1);
let c = TypeId(2);
let d = TypeId(3);
// Rec(a)
types.insert_struct(a, g_a, false, Some(d), Vec::new());
// Rec(b, c)
types.insert_struct(b, g_bc, false, None, Vec::new());
types.insert_struct(c, g_bc, false, Some(a), Vec::new());
// Rec(d)
types.insert_struct(d, g_d, false, Some(c), Vec::new());
let limits = GcOpsLimits {
num_params: 0,
num_globals: 0,
table_size: 0,
max_rec_groups: 10,
max_types: 10,
max_fields: 10,
array_length: 5,
};
types.fixup_types(&limits, &mut Vec::new());
let a_super = types.type_defs.get(&a).unwrap().supertype;
let c_super = types.type_defs.get(&c).unwrap().supertype;
let d_super = types.type_defs.get(&d).unwrap().supertype;
let cleared = [a_super, c_super, d_super]
.into_iter()
.filter(|st| st.is_none())
.count();
assert!(
cleared == 1,
"fixup should clear exactly one edge to break the cycle"
);
}
#[test]
fn sort_rec_groups_topo_orders_dependencies_first() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g0 = RecGroupId(0);
let g1 = RecGroupId(1);
let g2 = RecGroupId(2);
let g3 = RecGroupId(3);
types.insert_rec_group(g0);
types.insert_rec_group(g1);
types.insert_rec_group(g2);
types.insert_rec_group(g3);
let a = TypeId(0);
let b = TypeId(1);
let c = TypeId(2);
let d = TypeId(3);
let e = TypeId(4);
let f = TypeId(5);
types.insert_struct(a, g0, false, Some(b), Vec::new()); // g0 -> g1
types.insert_struct(b, g1, false, Some(c), Vec::new()); // g1 -> g2
types.insert_struct(c, g2, false, Some(d), Vec::new()); // g2 ->g3
types.insert_struct(d, g3, false, None, Vec::new());
types.insert_struct(e, g0, false, None, Vec::new());
types.insert_struct(f, g2, false, None, Vec::new());
let type_to_group = types.type_to_group_map();
let mut sorted = Vec::new();
types.sort_rec_groups_topo(&mut sorted, &type_to_group);
// g3 has no deps, g2 depends on g3, g1 on g2, g0 on g1.
assert_eq!(
sorted,
[RecGroupId(3), RecGroupId(2), RecGroupId(1), RecGroupId(0)],
"topo order: depended-on groups before dependent groups"
);
}
#[test]
fn merge_rec_group_cycles() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g0 = RecGroupId(0);
let g1 = RecGroupId(1);
let g2 = RecGroupId(2);
let g3 = RecGroupId(3);
types.insert_rec_group(g0);
types.insert_rec_group(g1);
types.insert_rec_group(g2);
types.insert_rec_group(g3);
let a0 = TypeId(0);
let a1 = TypeId(1);
let b0 = TypeId(2);
let b1 = TypeId(3);
let c0 = TypeId(4);
let c1 = TypeId(5);
let c2 = TypeId(6);
let d0 = TypeId(7);
let d1 = TypeId(8);
// Before: t
//
// ----------------------------------
// | outer cycle │
// v │
// +----+ +----+ +----+ │
// | g0 |------>| g1 |------>| g2 |---
// +----+ +----+ +----+
// ^ │
// │ inner │
// │ cycle v
// │ +----+
// -----------| g3 |
// +----+
//
// All four groups are mutually reachable (g0->g1->g2->g0 and
// g1->g2->g3->g1), so they form a single strongly-connected component.
//
// After: the whole SCC is merged into one rec group, with every supertype
// edge preserved (nothing is dropped).
//
// +-------------------------+
// | g0 ∪ g1 ∪ g2 ∪ g3 |
// +-------------------------+
types.insert_struct(a0, g0, false, Some(b0), Vec::new()); // g0 -> g1
types.insert_struct(a1, g0, false, None, Vec::new());
types.insert_struct(b0, g1, false, None, Vec::new());
types.insert_struct(b1, g1, false, Some(c0), Vec::new()); // g1 -> g2
types.insert_struct(c0, g2, false, None, Vec::new());
types.insert_struct(c1, g2, false, Some(a1), Vec::new()); // g2 -> g0 (outer back edge)
types.insert_struct(c2, g2, false, Some(d0), Vec::new()); // g2 -> g3
types.insert_struct(d0, g3, false, None, Vec::new());
types.insert_struct(d1, g3, false, Some(b0), Vec::new()); // g3 -> g1 (inner back edge)
// Type graph is acyclic — breaking supertype cycles changes nothing.
types.break_supertype_cycles();
assert_eq!(types.type_defs.get(&a0).unwrap().supertype, Some(b0));
assert_eq!(types.type_defs.get(&b1).unwrap().supertype, Some(c0));
assert_eq!(types.type_defs.get(&c1).unwrap().supertype, Some(a1));
assert_eq!(types.type_defs.get(&c2).unwrap().supertype, Some(d0));
assert_eq!(types.type_defs.get(&d1).unwrap().supertype, Some(b0));
assert_eq!(types.rec_groups.len(), 4);
let type_to_group = types.type_to_group_map();
types.merge_rec_group_cycles(&type_to_group);
// The whole cycle collapses into a single rec group...
assert_eq!(types.rec_groups.len(), 1);
// ...which contains every type from all four original groups.
let merged: BTreeSet<TypeId> = types.rec_groups.values().flatten().copied().collect();
let expected: BTreeSet<TypeId> = [a0, a1, b0, b1, c0, c1, c2, d0, d1].into_iter().collect();
assert_eq!(merged, expected);
// Merging drops no edges: every supertype relationship is preserved.
assert_eq!(types.type_defs.get(&a0).unwrap().supertype, Some(b0));
assert_eq!(types.type_defs.get(&b1).unwrap().supertype, Some(c0));
assert_eq!(types.type_defs.get(&c1).unwrap().supertype, Some(a1));
assert_eq!(types.type_defs.get(&c2).unwrap().supertype, Some(d0));
assert_eq!(types.type_defs.get(&d1).unwrap().supertype, Some(b0));
// With a single group there are no cross-group ordering constraints left.
let type_to_group = types.type_to_group_map();
let mut topo = Vec::new();
types.sort_rec_groups_topo(&mut topo, &type_to_group);
assert_eq!(topo.len(), 1);
}
#[test]
fn is_subtype_index_accepts_chain() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g0 = RecGroupId(0);
let g1 = RecGroupId(1);
let g2 = RecGroupId(2);
let g3 = RecGroupId(3);
types.insert_rec_group(g0);
types.insert_rec_group(g1);
types.insert_rec_group(g2);
types.insert_rec_group(g3);
// Build chain: 1 <- 2 <- 3
//
// TypeId(1): g0
// TypeId(2): subtype of 1
// TypeId(3): g2
// TypeId(4): g3
//
// Since type_defs is a BTreeMap, the dense index order used by
// is_subtype_index is:
//
// 0 -> TypeId(1)
// 1 -> TypeId(2)
// 2 -> TypeId(3)
types.insert_struct(TypeId(1), g0, false, None, Vec::new());
types.insert_struct(TypeId(2), g1, false, Some(TypeId(1)), Vec::new());
types.insert_struct(TypeId(3), g2, false, Some(TypeId(2)), Vec::new());
types.insert_struct(TypeId(4), g3, false, Some(TypeId(3)), Vec::new());
let order = encoding_order(&types);
// self
assert!(is_subtype_index(&types, 0, 0, &order)); // 1 <: 1
assert!(is_subtype_index(&types, 1, 1, &order)); // 2 <: 2
assert!(is_subtype_index(&types, 2, 2, &order)); // 3 <: 3
// requested checks
assert!(is_subtype_index(&types, 1, 0, &order)); // 2 <: 1
assert!(is_subtype_index(&types, 2, 0, &order)); // 3 <: 1
assert!(is_subtype_index(&types, 2, 1, &order)); // 3 <: 2
// reverse directions must fail
assert!(!is_subtype_index(&types, 0, 1, &order)); // 1 </: 2
assert!(!is_subtype_index(&types, 0, 2, &order)); // 1 </: 3
assert!(!is_subtype_index(&types, 1, 2, &order)); // 2 </: 3
}
/// Encoding order can differ from BTreeMap key order when a higher-numbered
/// TypeId lives in a group that must be emitted *before* a lower-numbered
/// TypeId's group (because of cross-group supertype dependencies).
///
/// With plain BTreeMap key order the dense indices would be:
/// 0 -> TypeId(1) 1 -> TypeId(10)
///
/// But the correct encoding order (group topo sort) is:
/// 0 -> TypeId(10) 1 -> TypeId(1)
///
/// A naive key-order approach would conclude "index 0 (TypeId(1)) <: index 1
/// (TypeId(10))" is false (they're unrelated), while the real encoding order
/// says "index 1 (TypeId(1)) <: index 0 (TypeId(10))" is true.
#[test]
fn is_subtype_index_encoding_order_differs_from_key_order() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g0 = RecGroupId(0);
let g1 = RecGroupId(1);
types.insert_rec_group(g0);
types.insert_rec_group(g1);
// TypeId(10) in g0: the supertype (no parent).
// TypeId(1) in g1: subtype of TypeId(10).
//
// BTreeMap key order: [TypeId(1), TypeId(10)] -> dense 0=TypeId(1), 1=TypeId(10)
// Encoding order: [TypeId(10), TypeId(1)] -> dense 0=TypeId(10), 1=TypeId(1)
// (g0 must come before g1 because g1's type has a supertype in g0)
types.insert_struct(TypeId(10), g0, false, None, Vec::new());
types.insert_struct(TypeId(1), g1, false, Some(TypeId(10)), Vec::new());
let order = encoding_order(&types);
// Verify that encoding order is indeed reversed from key order.
assert_eq!(order, vec![TypeId(10), TypeId(1)]);
// index 1 (TypeId(1)) is a subtype of index 0 (TypeId(10))
assert!(is_subtype_index(&types, 1, 0, &order));
// index 0 (TypeId(10)) is NOT a subtype of index 1 (TypeId(1))
assert!(!is_subtype_index(&types, 0, 1, &order));
// Also verify the direct TypeId-based method works.
assert!(types.is_subtype(TypeId(1), TypeId(10)));
assert!(!types.is_subtype(TypeId(10), TypeId(1)));
}
#[test]
fn stacktype_fixup_accepts_subtype_for_supertype_requirement() {
let _ = env_logger::try_init();
let mut types = Types::new();
let g = RecGroupId(0);
types.insert_rec_group(g);
// Same chain: 1 <- 2 <- 3
//
// Dense indices:
// 0 -> TypeId(1)
// 1 -> TypeId(2)
// 2 -> TypeId(3)
types.insert_struct(TypeId(1), g, false, None, Vec::new());
types.insert_struct(TypeId(2), g, false, Some(TypeId(1)), Vec::new());
types.insert_struct(TypeId(3), g, false, Some(TypeId(2)), Vec::new());
let num_types = u32::try_from(types.type_defs.len()).unwrap();
let order = encoding_order(&types);
// Case 1: stack has subtype 3, op requires supertype 2.
let mut stack = vec![StackType::Struct(Some(2))];
let mut out = vec![];
StackType::fixup_operand(
Some(StackType::Struct(Some(1))),
&mut stack,
&mut out,
num_types,
&types,
&order,
);
// Accepted as-is:
// - no fixup ops inserted
// - operand consumed from stack
assert!(
out.is_empty(),
"subtype 3 should satisfy required supertype 2"
);
assert!(stack.is_empty(), "accepted operand should be popped");
// Case 2: stack has subtype 3, op requires supertype 1.
let mut stack = vec![StackType::Struct(Some(2))];
let mut out = vec![];
StackType::fixup_operand(
Some(StackType::Struct(Some(0))),
&mut stack,
&mut out,
num_types,
&types,
&order,
);
// Accepted as-is:
assert!(
out.is_empty(),
"subtype 3 should satisfy required supertype 1"
);
assert!(stack.is_empty(), "accepted operand should be popped");
// Case 3: stack has type 1, op requires subtype 2.
let mut stack = vec![StackType::Struct(Some(0))];
let mut out = vec![];
StackType::fixup_operand(
Some(StackType::Struct(Some(1))),
&mut stack,
&mut out,
num_types,
&types,
&order,
);
// Not accepted. Fixup should synthesize the requested concrete type.
assert_eq!(out, vec![GcOp::StructNew { type_index: 1 }]);
assert_eq!(stack, vec![StackType::Struct(Some(0))]);
}
/// Helper: creates GcOps with a 3-type chain: TypeId(1) <- TypeId(2) <- TypeId(3).
///
/// Dense encoding indices:
/// 0 -> TypeId(1) (root, no supertype)
/// 1 -> TypeId(2) (supertype = TypeId(1))
/// 2 -> TypeId(3) (supertype = TypeId(2))
fn cast_test_ops(ops: Vec<GcOp>) -> GcOps {
let mut t = GcOps {
limits: GcOpsLimits {
num_params: 0,
num_globals: 0,
table_size: 0,
max_rec_groups: 5,
max_types: 10,
max_fields: 10,
array_length: 5,
},
ops,
types: Types::new(),
};
let g = RecGroupId(0);
t.types.insert_rec_group(g);
t.types.insert_struct(TypeId(1), g, false, None, Vec::new());
t.types
.insert_struct(TypeId(2), g, false, Some(TypeId(1)), Vec::new());
t.types
.insert_struct(TypeId(3), g, false, Some(TypeId(2)), Vec::new());
t
}
/// Helper: creates GcOps with two unrelated types (flat hierarchy, no supertypes).
///
/// Dense encoding indices:
/// 0 -> TypeId(1) (no supertype)
/// 1 -> TypeId(2) (no supertype)
fn flat_cast_test_ops(ops: Vec<GcOp>) -> GcOps {
let mut t = GcOps {
limits: GcOpsLimits {
num_params: 0,
num_globals: 0,
table_size: 0,
max_rec_groups: 5,
max_types: 10,
max_fields: 10,
array_length: 5,
},
ops,
types: Types::new(),
};
let g = RecGroupId(0);
t.types.insert_rec_group(g);
t.types.insert_struct(TypeId(1), g, false, None, Vec::new());
t.types.insert_struct(TypeId(2), g, false, None, Vec::new());
t
}
// ---- RefCastUpward tests ----
/// Case 1: valid pair (sub <: super) — kept as-is.
#[test]
fn upcast_valid_pair() {
let _ = env_logger::try_init();
// index 2 (TypeId(3)) <: index 0 (TypeId(1)) via chain 3 <: 2 <: 1
let mut ops = cast_test_ops(vec![GcOp::RefCastUpward {
sub_type_index: 2,
super_type_index: 0,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastUpward {
sub_type_index: 2,
super_type_index: 0,
}
)),
"valid upcast pair should be preserved: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 2: wrong pair — repaired to sub's direct supertype.
#[test]
fn upcast_wrong_pair_repaired_via_supertype() {
let _ = env_logger::try_init();
// index 1 (TypeId(2)) is NOT a subtype of index 2 (TypeId(3)).
// TypeId(2)'s supertype is TypeId(1) at index 0.
// Should repair to { sub: 1, super: 0 }.
let mut ops = cast_test_ops(vec![GcOp::RefCastUpward {
sub_type_index: 1,
super_type_index: 2,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastUpward {
sub_type_index: 1,
super_type_index: 0,
}
)),
"upcast should be repaired to sub's direct supertype: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 3: sub has no supertype — falls back to self-cast.
#[test]
fn upcast_no_supertype_self_cast() {
let _ = env_logger::try_init();
// index 0 (TypeId(1)) has no supertype, so no valid super can be found.
// Falls back to self-cast { sub: 0, super: 0 }.
let mut ops = cast_test_ops(vec![GcOp::RefCastUpward {
sub_type_index: 0,
super_type_index: 2,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastUpward {
sub_type_index: 0,
super_type_index: 0,
}
)),
"upcast with no supertype should become self-cast: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 4: flat hierarchy (no supertypes at all) — self-cast.
#[test]
fn upcast_flat_hierarchy_self_cast() {
let _ = env_logger::try_init();
let mut ops = flat_cast_test_ops(vec![GcOp::RefCastUpward {
sub_type_index: 0,
super_type_index: 1,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastUpward {
sub_type_index,
super_type_index,
} if sub_type_index == super_type_index
)),
"upcast in flat hierarchy should become self-cast: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
// ---- RefCastDownward tests ----
/// Case 1: valid pair — kept as-is.
#[test]
fn downcast_valid_pair() {
let _ = env_logger::try_init();
// index 2 (TypeId(3)) <: index 0 (TypeId(1)) — valid.
let mut ops = cast_test_ops(vec![GcOp::RefCastDownward {
sub_type_index: 2,
super_type_index: 0,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastDownward {
sub_type_index: 2,
super_type_index: 0,
}
)),
"valid downcast pair should be preserved: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 2: wrong pair — super (operand) is kept, sub (result) is
/// repaired by finding a direct subtype of the super.
#[test]
fn downcast_wrong_pair_repaired_finds_subtype() {
let _ = env_logger::try_init();
// sub=0 (TypeId(1)) is NOT a subtype of super=1 (TypeId(2)).
// super stays at 1 (it's the stack operand).
// Scan finds TypeId(3) at index 2 as a direct subtype of TypeId(2).
// Repaired to { sub: 2, super: 1 }.
let mut ops = cast_test_ops(vec![GcOp::RefCastDownward {
sub_type_index: 0,
super_type_index: 1,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastDownward {
sub_type_index: 2,
super_type_index: 1,
}
)),
"downcast should keep super and find a valid sub: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 3: super has no subtypes — falls back to self-cast keeping
/// the super (operand) fixed.
#[test]
fn downcast_no_subtype_self_cast() {
let _ = env_logger::try_init();
// super=2 (TypeId(3)) is the leaf — no type has it as a supertype.
// Self-cast: { sub: 2, super: 2 }.
let mut ops = cast_test_ops(vec![GcOp::RefCastDownward {
sub_type_index: 1,
super_type_index: 2,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastDownward {
sub_type_index: 2,
super_type_index: 2,
}
)),
"downcast with no subtypes should self-cast keeping super: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// Case 4: flat hierarchy — self-cast.
#[test]
fn downcast_flat_hierarchy_self_cast() {
let _ = env_logger::try_init();
let mut ops = flat_cast_test_ops(vec![GcOp::RefCastDownward {
sub_type_index: 0,
super_type_index: 1,
}]);
ops.fixup(&mut Vec::new());
assert!(
ops.ops.iter().any(|op| matches!(
op,
GcOp::RefCastDownward {
sub_type_index,
super_type_index,
} if sub_type_index == super_type_index
)),
"downcast in flat hierarchy should become self-cast: {:#?}",
ops.ops
);
assert_valid_wasm(&ops);
}
/// `Types::fixup` must re-point dangling type references at live types rather
/// than erasing them, because a mutated type id is essentially never live and
/// erasing would leave the fuzzer with no concrete references and no subtyping.
#[test]
fn fixup_repoints_dangling_references() {
let limits = GcOpsLimits::default();
let gid = RecGroupId(0);
let mut types = Types::new();
types.insert_rec_group(gid);
// A final struct and an array: neither is a legal supertype for a
// non-final struct, so resolution must not pick either of them.
types.insert_struct(TypeId(10), gid, true, None, Vec::new());
types.insert_type(
TypeId(20),
gid,
false,
None,
CompositeType::Array(ArrayType {
element: StructField {
field_type: FieldType::I32,
mutable: false,
},
}),
);
// The one legal supertype.
types.insert_struct(TypeId(30), gid, false, None, Vec::new());
// The type under test: a dangling supertype and a dangling field
// reference, both pointing at ids that do not exist.
types.insert_struct(
TypeId(40),
gid,
false,
Some(TypeId(0xdead_beef)),
vec![StructField {
field_type: FieldType::Ref {
nullable: true,
type_id: TypeId(0xfeed_face),
},
mutable: false,
}],
);
types.fixup_types(&limits, &mut Vec::new());
let def = types.type_defs.get(&TypeId(40)).unwrap();
assert_eq!(
def.supertype,
Some(TypeId(30)),
"a dangling supertype must resolve to the one non-final struct, \
not to the final struct, the array, or `None`"
);
let field = &def.composite_type.fields()[0];
match field.field_type {
FieldType::Ref { type_id, .. } => assert!(
types.type_defs.contains_key(&type_id),
"a dangling reference must resolve to a live type, got {type_id:?}"
),
ref other => panic!("dangling reference was erased instead of re-pointed: {other:?}"),
}
}