Basic reference types for Wasm

Wasm Reference Types

# Reference Types for WebAssembly

## Introduction

Use cases:

* Easier and more efficient interop with host
* Manipulation of tables inside Wasm
* Tyoed function pointers
* Setting the stage for other proposals like exception handling
* A smoother transition path to GC

Design:

* Identify separate levels of feature support that could be turned into incremental proposals
* Goal: get the most important parts soon


## Level 0: Add `anyref` value type

Motivation: Allow host references to be represented directly by type `anyref`,
without having to go through tables, allocating slots, and maintaining index bijections at the boundaries.

Changes:

* Add `anyref` as a fifth value type (valtype = numtype | reftype)
* Add `null` instruction and (default) value
* Any non-primitive value from the host can be passed as `anyref` to Wasm function

That's all!

Notes:

- Does not imply GC by itself, only if host refs are GCed pointers!
- Reference types are opaque.
- No way to create a non-null `anyref` value inside Wasm.
- No way to consume an `anyref` value inside Wasm.
- No way to put `anyref` into a table.
- No subtyping between `anyfunc` and `anyref`.


## Level 1: Allow `anyref` as an element type

Motivation: Allow representing data structures containing references
by repurposng tables as a general memory for opaque data types;
allow manipulating function tables from within Wasm.

Changes:

* Add `anyref` element type and `anyfunc` value type (unify elemtype and reftype)
* Allow multiple tables
* Add `(table.get $t)` and `(table.set $t)` instructions

Notes:

- `call_indirect` takes table index immediate.
- `call_indirect` requires element type < `anyfunc`.
- Element segment has table index immediate.
- Still no subtyping between `anyfunc` and `anyref` element types.

Question:

- Should we rename `get/set_global` to ` global.get/set`?


## Level 2: Function references

Motivation: Allow function pointers to be expressed directly without going through table and dynamic type check;
enable functions to be passed to other modules easily.

Changes:

* Add `(ref $t)` as reference (i.e., value type and element) type
* Add `(ref.func $f)` and `(call_ref)` instructions
* Introduce subtyping `ref <functype>` < `anyfunc` < `anyref`

Notes:

- Function references cannot be null.

Question:

* General function have no reasonable default, do we need scoped variables like `let`?
* Should there be a down cast instruction?
* Should there be depth subtyping for function types?
* Should we rename `call_indirect` to `call_table`?


## Level 3: Type import/export

Motivation: Allow the host (or Wasm modules) to distinguish different reference types.

Changes:

* Add `(type)` external type, enables types to be imported and exported
* Add `WebAssembly.Type` class to JS API, creates new opaque data types
* Subtyping `ref <abstype>` < `anyref`

Notes:

- Type `(ref $t)` can now denote an abstract type or a function reference
- Imported types have index starting from 0.
- May need to impose constraints on order of imports, to stratify section dependencies.

Questions:

* Should subsumption be implicit of require an explicit upcast?
* Do we need a nullable `(ref opt $t)` type to allow use with locals etc.?
* Should we add `(new)` definitional type to enable Wasm modules to define new types, too?
* Should we add a `(cast $t)` instruction for down casts?
* Should JS API allow specifying subtyping between new types?


## Level 4+: Possible future additions

* Introduce reference types pointing to tables, memories, or globals (first-class tables, memories, globals)
* Allow all value types as element types (unify elemtype with valtype)
* GC extension


## Detailed Changes

Multiple Tables:

* more than one table allowed (already representable in binary format)
* element section has table index (already reserved in binary format)
* call_indirect has table index (already reserved in binary format)

Reference Types:

* `numtype ::= i32 | i64 | f32 | f64`
* `valtype ::= numtype | reftype`
* `reftype ::= anyref | anyfunc | ref <typeidx>`
* `elemtype ::= reftype`
* subtying: `ref $t < anyref`, `ref <functype>` < `anyfunc` < `anyref`
* subsumption: `e : t` iff `e : t'` and `t' < t`
* `call_indirect` requires element type < `anyfunc`

Type Import/Export:

* `externtype ::= ... | type`
* reserve byte in binary format to allow refinements later
* new type import section? (before type)
* new type export section? (before export)
* `deftype ::= ... | new`
* `new WebAssembly.Type(name)` creates new unique type

Instructions for Manipulating Tables:

* `table.init $src $dst : [i32 i32 i32] -> []`
* `table.copy $src $dst : [i32 i32 i32] -> []`
* `table.clear $dst : [i32 i32] -> []`
* `table.grow $dst : [i32] -> [i32]`
* `table.size $dst : [] -> [i32]`
* `table.get $dst : [i32] -> [t]`
* `table.set $dst : [i32 t] -> []`
* `(call_indirect $t $dst)` reduces to `(table.get $dst) (cast (ref $t)) (call_ref (ref $t))`

Instructions for Function References:

* `ref.func $f : [] -> (ref $t)  iff $f : $t`
* `call_ref : [ts1 (ref $t)] -> [ts2]  iff $t = [ts1] -> [ts2]`

Instructions for Casting:

* `cast t : [t'] -> [t]`  iff `t` < `t'`


## Pssobile Future Changes

References to all external types:

* `deftype := ... | globaltype | tabletype | memtype`

Instructions for global references:

* `ref.global $g : [] -> (ref $t)  iff $g : $t`
* `get_global_ref : [(ref $t)] -> [t]  iff $t = mut t`
* `set_global_ref : [t (ref $t)] -> []  iff $t = var t`

Instructions for table references:

* `ref.table $x : [] -> (ref $t)  iff $x : $t`
* ...

Instructions for memory references:

* `ref.mem $m : [] -> (ref $t)  iff $m : $t`
* ...