Does the combo of subtyping and unreachable code require actual type inference?

[fitzgen]

Consider the following example. I've annotated it with the operand stack in between each opcode twice:

1. Once with the appendix's algorithm.
2. A second time with wasm-smith's "actual" stack.

The difference is that the appendix algorithm truncates the stack after unreachable code, letting subsequent pops materialize their expected types, while wasm-smith maintains the "actual" stack going into the unreachable code.

AFAICT, the formal typing rules don't actually mandate the appendix's operand stack truncation. There has never been divergence between the two approaches until now, with the introduction of subtyping.

In the following example, the br 0 makes the subsequent code unreachable. The appendix will additionally truncate the stack. Next, the br_on_null is typed [anyref anyref] -> [anyref (ref any)] due to the type of its label. With wasm-smith's actual stack, this type checks fine because structref <: anyref combined with the rules for subtyping between instructions. For the appendix algorithm, we have an empty stack in unreachable code, so when the br_on_null wants to pop the anyref that the label demands, it does, and then when it pushes it back onto the stack, it pushes an anyref. Not a structref. This is the source of the divergence between the two approaches. Finally, the br_on_cast_fail observes the "actual" structref, triggering a type mismatch: expected structref, found anyref error in the appendix algorithm.

(module
  (func (param anyref) (result anyref)
    ;; 0x1b: appendix: []
    ;;         actual: []
    ref.null struct
    ;; 0x1d: appendix: [structref]
    ;;         actual: [structref]
    local.get 0
    ;; 0x1f: appendix: [structref anyref]
    ;;         actual: [structref anyref]
    br 0
    ;; 0x21: appendix: []
    ;;         actual: [structref]
    local.get 0
    ;; 0x23: appendix: [anyref]
    ;;         actual: [structref anyref]
    br_on_null 0
    ;; 0x25: appendix: [anyref (ref any)]
    ;;         actual: [structref (ref any)]
    drop
    ;; 0x26: appendix: [anyref]
    ;;         actual: [structref]
    br_on_cast_fail 0  structref structref
  )
)

The reference interpreter, and wasmparser, report the type mismatch error and consider the example invalid. But despite that, it isn't clear to me that it really is invalid.

Firefox and wasm-smith consider the example valid.

If this example is valid, then it seems like popping from an empty operand stack in unreachable code would have to, in this case, produce a value that is constrained to be some subtype of anyref but not necessarily exactly anyref and then the subsequent br_on_cast_fail would add a second constraint that the value is additionally a subtype of structref, and then implementations would need to solve these constraints to determine validity. But that kind of constraint solving and "real" type inference is something that we intentionally avoid requiring in Wasm validation. So if this example is currently valid, it seems like we want to do something to avoid the need for this kind of constraint solving.

Concrete Questions

1. the actual formal typing rules don't mandate the appendix's operand stack truncation

   Is this statement true or false?

2. Is the example valid or invalid?

Thanks for your time!

[tlively]

Is there an instruction missing at the beginning of the example? Where does the structref come from?

[fitzgen]

Is there an instruction missing at the beginning of the example? Where does the structref come from?

Whoops, I left out a ref.null struct, adding it now.

Edit: fixed!

[tlively]

I don't think this really gets to the crux of the issue, but I'm curious about how keeping the stack like you describe can ever work. For example, this is perfectly valid:

block
 f32.const 1.0
 f32.const 2.0
 br 0
 i32.add
 drop
end

Wouldn't keeping the stack around produce an error about the i32.add having f32 operands?

[fitzgen]

Wouldn't keeping the stack around produce an error about the i32.add having f32 operands?

I guess the difference is that wasm-smith is generating valid Wasm modules, not validating arbitrary Wasm modules. Given your example, it does seem like truncation is necessary for a validator.

So I guess the question is: is truncation necessary for generators? I think this is equivalent to asking whether we can add an unreachable anywhere in a valid function body and still end up with a valid function body.

[rossberg]

First of all, the fact that the example is rejected has nothing to do with unreachable code or "stack truncation". The following sequence is invalid regardless of what's before it:

(local.get 0)
(br_on_null 0)
(drop)
(br_on_cast_fail 0 structref structref)

The reason is that after the br_on_null the two topmost values on the stack are two anyrefs (assuming both local 0 and label 0 have type anyref, as in your example). Because the typing rule is:

• br_on_null $𝑙 : [𝑡* (ref null ℎ𝑡)] → [𝑡* (ref ℎ𝑡)]
  • if $𝑙 : [𝑡*]

Note how the stack result is determined (and fixed) by the type of $𝑙. (A more permissive rule would be possible, but would be more complicated yet only rarely more useful in practice. Edit: well, possible except for the loss of principal types.)

As for truncating the stack, that is "mandated" by the spec in so far as the declarative type of br allows consuming an arbitrary number of virtual values from the stack:

• br $𝑙 : [𝑡₁* 𝑡*] → [𝑡₂*]
  • if $𝑙 : [𝑡*]

There are infinitely many ways to instantiate the 𝑡₁* and 𝑡₂* in this rule, but an algorithm always needs to make the most general choice, otherwise it wouldn't be complete. And the most general algorithmic solution is to pop everything currently the stack because after that the algorithm can successfully pop any type it wants, especially bottom, which is at least as permissive as anything that could have been on the stack before.

A simple example demonstrating this would be

(func
  (i32.const 0)
  (br 0)
  (ref.is_null)
  (drop)
)

An algorithm that does not "truncate" the stack would incorrectly reject this.

As an aside, the algorithm from the Appendix does not just truncate the stack, it replaces it with the polymorphic stack. So a more faithful way to annotate the example above e.g. would be

;; []
(i32.const 0)
;; [i32]
(br 0)
;; [...]
(ref.is_null)
;; [... i32]
(drop)
;; [...]

where "..." denotes the polymorphic bottom of the stack, from which arbitrary types can be drawn.

An alternative is to annotate the actual instruction types:

(i32.const 0)  ;; [] → [i32]
(br 0)         ;; [i32] → [bot]
(ref.is_null)  ;; [bot] → [i32]
(drop)         ;; [i32] → []

Here, the output of each type must match up with the input of the next. For br, 𝑡₁* was instantiated with i32 and 𝑡₂* with bot. Any reference type would also work instead of bot, but that would require guessing ahead.

So, to summarise the answers to your questions:

1. Yes and no: there would be other ways to formulate an algorithm (e.g., with search and backtracking), but for simple forward checking like with the Appendix' algorithm, you have to truncate.

2. The example is invalid, but for unrelated reasons.

And to the question in the issue's subject: no, forward checking is enough. The principal types property of the Wasm type system (esp the "Closed Principal Forward Types" theorem) ensures that.

Finally, Firefox and wasm-smith seem to have bugs in their validators, but from your example alone it is unclear whether they are related to stack polymorphism.

[fitzgen]

Thanks for the explanation, and pointing out the root issue with the br_on_null.

In wasmparser we were doing

push_operands(pop_operands(label_types))

instead of

pop_operands(label_types)
push_operands(label_types)

in some places where we shouldn't have. That caused us to consider the following valid:

(module
  (func (param anyref) (result anyref)
    ref.null struct
    local.get 0
    br_on_null 0
    drop
    br_on_cast_fail 0  structref structref
  )
)

but then adding an unreachable just after the ref.null struct would make us consider it invalid and it seemed wrong to me that inserting an unreachable anywhere would ever make a Wasm invalid.

Glad that things have been cleared up!

FWIW, Firefox seems to have a similar bug. Filed https://bugzilla.mozilla.org/show_bug.cgi?id=1879096 for them.

Thanks again!

[rossberg]

Can I motivate you to add a test for this to the Wasm test suite? :)

[fitzgen]

Writing one already :)

[fitzgen]

#518