Skip to content

A lightweight WebAssembly runtime that is fast, secure, and standards-compliant

35.4 KB
Raw Blame
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:?}"),
    }
}