Rewrite the `table_ops` fuzzer to hammer on all GC/reference types things

# GC Fuzzing

This is a sketch of a series of milestones, roughly estimated to be about one PR each, for GC fuzzing. We don't need to do exactly these milestones in exactly this order. It is okay if, in the process of implementing them, we find reason to do milestone X before Y and decide to swap their order. It is okay if one milestone becomes three PRs, or two milestones become one PR. This is just a sketch to provide some light structure. Also, these milestones represent a lot of work, and while the goal is certainly to get everything here finished during your internship, if it turns out that this is more work that can be completed in that amount of time, that is okay.

### Incremental Milestones

* [X] Port the `table_ops` fuzzer from `arbitrary` to `mutatis`

* Replacing `arbitrary`-based generator with a `mutatis`-based fuzzer
* Oracle should be able to (largely) remain unmodified
* Avoid adding new features or changing existing functionality as much as possible
* Start handling the scenario where:
* We originally have a valid series of fuzzer ops A,
* then a random mutation inserts, removes, or changes an op in A to produce fuzzer ops A',
* but A' is now no longer a valid sequence of fuzzer ops (for example, an initial op whose result was the input for a subsequent op was removed, for example).
* Now we have to figure out how to handle invalid test cases:
* Do we throw it away and continue to the next one?
* Do we "patch up" the test case in a post-processing pass that fixes it up such that it becomes valid?
* I'm thinking we probably want to do a fix-up pass to avoid wasting cycles on test cases we won't execute, ultimately hurting our overall fuzzing throughput, but I'm not 100% sure that is the right choice, and I am all ears for counter arguments and alternative ideas.
* As far as `mutatis`-related prior art goes, the allocator fuzzer handled this stuff in the oracle: it simply avoided performing the fuzzer's allocation operations when they did not make sense (i.e. it ignores the "deallocate pointer with id X" operation if there isn't currently a live allocation with id X): https://github.com/fitzgen/deallocate-zeroed/blob/52c2b9b7305dd1a947b3342128fcf0d03143223e/crates/fuzzing/src/lib.rs#L656
* We want to always generate valid Wasm, otherwise we can't even execute the subset of ops that are valid, so I think we will need to do the equivalent filtering/fixing up in the generator rather than in the oracle.
* This fix-up pass could be its own pass, mutating the fuzzer ops AST structure directly, before we generate a Wasm binary from that AST structure. Or, alternatively, it could be integrated into Wasm-binary-from-AST generation step.
* Goal: Become familiar with `mutatis` and move the fuzzer towards our north star vision for it

* [x] Add support for empty `(rec ...)` groups containing zero or more empty `struct` types.

* Add generation support for these `(rec ...)` groups with zero or more empty `struct` types
* Add a fuzzer op that allocates a random one of our `struct` types. We should avoid emitting this op when we have not defined any `struct` types.
* Add a function import that takes a `structref` argument to our Wasm binary skeleton
* Add a fuzzer op that calls that new function
* Add a function import for each defined `struct` type that takes a reference of that type of struct specifically
* Add a fuzzer op that calls these new typed functions
* Add support for generating locals, globals, and tables that contain `structref`s and concretely typed `struct` references
* Add new or extend existing fuzzer ops for accessing locals/globals/tables of `structref`s and concretely typed `struct` references
* Define a mutation that adds an empty `struct` type to an existing `(rec ...)` group
* Define a mutation that removes a `struct` type from an existing `(rec ...)` group
* Define a mutation that moves a `struct` type within an existing `(rec ...)` group
* Define a mutation that moves a `struct` type from an existing `(rec ...)` group to another
* Define a mutation that duplicates a `(rec ...)` group
* Define a mutation that removes a whole `(rec ...)` group
* Define a mutation that merges two `(rec ...)` groups
* Define a mutation that splits a `(rec ...)` group in two, if possible
* Will need to migrate the abstract representation of the value stack from a couner of how many `externref`s are on the stack to an actual stack of types
* Note: there is a whole lot here, even just exercising empty `struct` definitions, so it may make sense to split this up into a few PRs
* Goal: start exercising type canonicalization, lay down initial infrastructure for `(rec ...)` groups and `struct` types.

* [x] Add support for exercising subtyping relationships

* Add support for on `struct` type to be a subtype of another `struct` type
* Subtypes must be defined after their supertypes, so this will require we do some validation/filtering/fixups in the face of mutations that reorder types. (This restriction prevents cyclic subtyping where A subtypes B and B subtypes A.)
* Want to think hard about how we represent types, rec groups, and type references in the AST at this point and how we are architecting the program. These choices are going to have a big impact on everything we do from here on out.
* Do we just have a list of rec groups that directly reflect the order we will put them into the Wasm binary?
* Do we create arbitrary type graphs and then do a topological sort on them to ensure they are valid? If we do this approach, what happens in the future when we find a cycle that is not within the same rec group? Or do we not even have rec groups here, just types, and then generate rec groups as part of the projection out from the graph?
* Do we reference types by id and ignore references when there is not type associated with that id?
* Or do we simply reference types by their type index, as in Wasm? And then ignore invalid references?
* Goal: Continue to fill out type system features that we exercise, figure out the architecture we want for dealing with references between types.

* [x] Add support for casting and testing references

* Add a fuzzer op for casts that should always succeed (from a subtype to a supertype). This should become a `ref.cast` instruction in the Wasm binary.
* Add a fuzzer op for fallible downcasts. This should not trap and kill the whole program if the downcast fails. In the fullness of time, we will want to generate blocks that do things with the downcasted value that are only executed if the downcast succeeds, something like this:

```
block (param ...)
;; Break out of this block if we fail to cast the reference on top of the
;; stack to its subtype.
ref.br_on_cast_fail ...

;; Do stuff with the subtype reference...
end

;; Control joins again here and the program continues.
```

And we will want to exercise both the `br_on_cast_fail` and `br_on_cast` instructions, which will require slightly different shapes of blocks.

Initially, we can simply downcast to a nullable subtype reference, where we get null if the downcast fails:

```
block (param (ref null $my_super)) (result (ref null $my_sub))
local.tee $my_temp
;; Test if the downcast will succeed.
ref.test ...
if (result (ref null $my_sub))
;; The downcast will succeed, do a downcast-or-trap operation which we
;; know will not trap.
local.get $my_temp
ref.cast ...
else
;; The downcast would fail, so just create a null reference instead.
ref.null ...
end
end
```
* Goal: Exercise subtyping checks and casting logic.

* [x] Add support for POD and `externref` fields in `struct`s

* Add generation and mutation support for `i8`/`i16`/`i32`/`i64`/`f32`/`f64`/`v128`/`externref` struct fields. Reference fields will be trickier and can be added in another milestone.
* Add fuzzer ops for `struct.get` and `struct.set`
* Maybe: Add fuzzer ops for creating POD constants? Or should we just create zero constants on demand when necessary in the AST-to-Wasm-binary generation step? We aren't trying to exercise arithmetic in this fuzzer, that is well exercised by other fuzzers already, so the only interesting case for POD data is really when it comes from another `struct`'s field. Other than that interesting case, we just need a *some* value in order to allocate a struct containing these values.
* Add mutators to add, remove, and modify a field in a defined `struct` type
* Goal: start exercising accessing, reading from, and writing to GC objects

* [x] Add support for concretely-typed references as `struct` fields

* Extend the items from the previous milestone to full type references between different defined `struct` types
* Also add support for abstract `structref` types
* Non-nullable type references will be tricky: if we have a cycle of non-nullable references, then those types are not currently inhabitable.
* Can detect and correct this in our fix-up pass, perhaps
* Okay to punt on this in a first PR, but we definitely would want to start handling them in a closely following PR. This is an important corner of the spec, and we perform optimizations based on non-nullability in the compiler, and one that none of our other fuzzers are exercising this right now (wasm-smith does not support non-nullable references yet).
* This phase is when we will really start seeing the impact of our architecture choices around how to represent types and references between them in the AST.
* Goal: start exercising references between GC objects and constructing interesting type- and heap-graphs, exercise non-nullable references

* [x] Add support for `i31ref`s and `eqref`s

* Support for `eqref` fields/locals/globals/tables
* Support for `i31ref` fields/locals/globals/tables
* Define new fuzzer ops for upcasting concrete and abstract `struct` refs and `i31ref`s to abstract `eqref`s
* Define new fuzzer ops for `i31.get_s` and `i31.get_u`
* Add host function imports that take `i31ref`s and `eqref`s from Wasm
* Maybe: make the `i31ref`-taking host functions also take the results of `i31.get_s` and `i31.get_u` and assert that the host's version of those operations matches the inline Wasm versions
* Goal: continue filling out coverage for the Wasm GC type system, exercise `i31ref`s

* [x] Add support for defining `array` types

* Extend everything we have done so far to `array` types
* Should be relatively easy at this point, since we already laid down all the infrastructure
* Will want to take care that we don't generate out-of-bounds array accesses very often (we do want to exercise the out-of-bounds paths, but we don't want 99% of test cases failing to actually run most of the generated program because of traps)
* Goal: complete our coverage of the Wasm GC type system, exercise array accesses and their bounds checks

* [ ] Enumerate Wasm GC instructions and ensure that the fuzzer exercises each of them

* There are a number of misc instructions that we still won't exercise at this point in time, things like `array.copy` and `array.new_elem`
* We should go through each of them and add support for exercising those instructions, if we don't already
* Goal: complete our coverage of the Wasm GC execution semantics

### Additional Ideas and Misc. Items

* [x] Rename the fuzz target to `gc_ops` or something, it has already grown / will continue to grow way past just exercising `table.{get,set}` and etc...

* [x] Add GC-after-N-allocations and OOM-after-N-allocations counters to our runtime, generate values for those counters in our test case generator, and then configure them based on those values in our oracle

* I remember that SpiderMonkey's fuzzing has something similar with its OOM after N allocations and then their JS helper that sets that to 0, runs a closure, then 1, runs the closer, etc... It was incredibly effective at finding improperly-handled OOM bugs.
* Would exercise the we-need-to-GC-before-satisfying-the-current-allocation path in our raw GC allocation libcalls
* Will probably want to gate these counters' compilation on `#[cfg(fuzzing)]`
* Will need to have a plan to avoid timeouts in the face of frequent GCs because of small counter values. Might need to make GCs consume fuel. Or might just make the counter not auto-reset and instead go to "infinity" after it triggers once. Or something.

* [ ] Generalize the host functions that create and take GC refs to arbitrary numbers of params and results

* Right now, they always take 3 arguments or return 3 arguments
* They should take an arbitrary number of arguments and/or return an arbitrary number of arguments, controlled by the fuzzer/mutator

* [ ] Investigate moving from a operand stack paradigm to a "places" paradigm

* That is, instead of each GC op saying "here are my operand types that I pop from the stack, and result types that I push onto the stack" we instead have them say "here is where I get operands from (and their types) and here is where I put results (and their types)".

Something like this:

```rust
enum SimplePlace {
/// The `i`th local.
Local(u32),
/// The `i`th global.
Global(u32),
/// The `i`th table's `j`th element.
Table(u32, u32),
}

enum Place {
Simple(SimplePlace),
/// The `i`th field of the struct at the given simple place.
StructField(SimplePlace, u32),
/// The `i`th element of the array at the given simple place.
ArrayElement(SimplePlace, u32),
}

impl GcOp {
pub(crate) fn operands(&self) -> &[(Type, Place)] {
// ...
}
pub(crate) fn results(&self) -> &[(Type, Place)] {
// ...
}
}
```

And we would fixup a GC op's places rather than fixing up the stack. And encoding each GC op would always be stack-neutral (not pop any incoming stack operands, not push any outgoing stack operands)

* This is probably easier to `fixup` than the stack stuff, while still reusing as many existing operands as possible (never have to insert `drop`s)
* This probably gets us more-interesting DFGs and liveness
* Hopefully would ultimately lead to more-interesting heap graphs as well

* [ ] Use partial evaluation to emit expected-value assertions

* Do some abstract interpretation (possibly during `fixup`) to partially evaluate our GC ops (but not optimize the emitted Wasm code based on the results, just track it)
* Add a new `GcOp::Assert` instruction, that does something like this at encoding time:
```rust
for (place, abstract_value) in partial_eval_results_at_current_program_point {
if let Some(concrete_value) = abstract_value.as_concrete() {
// []
place.emit_get();
// [t]
concrete_value.emit();
// [t t]
emit_call_assert_equal();
// []
}
}
```
* The goal is to find heap corruption where values are overwritten or incorrect.

* [ ] Generate arbitrary numbers of `{eqref,i31ref,structref,arrayref,(ref null? $idx), ...}` locals, globals, and tables (clamped to within reasonable ranges). Right now we always generate just a single local, global, and table of each of those types. This would allow for more interesting data-flow graphs and interactions with alias analysis.

--------------

+cc @khagankhan