1692063 - Expand subtyping algorithm to work with recursive types

Status: RESOLVED FIXED

(Core :: JavaScript: WebAssembly, task, P3)

Description

[Ryan Hunt [:rhunt] (on leave until early May)]

The current struct subtyping algorithm (and array subtyping algorithm to be added soon), is shallow and not compatible with the current MVP.

Comment 1

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1692063 - Add complete subtyping and equivalence algorithm. r?lth

This commit implements the complete subtyping and equivalence algorithm
used for struct and array types. The algorithm is an implementation of
gfp^t [1] for the subtyping rules presented in the MVP. An simple
python implementation is given at the end of V8 MVP doc [2].

Two challenges were given for integrating this with our validation code.

• Subtyping checks require allocating in a cache, which may OOM. Code was
  modified to handle this appropriately and abstracted across validation.
• The type assumption cache is not thread-safe and cannot exist in the
  type context. Code was modified to store this in appropriate locations
  and thread it through validation.

[1] Pierce, Benjamin C. Types and Programming Languages. definition 21.6.4
[2] https://docs.google.com/document/d/1yAWU3dbs8kUa_wcnnirDxUu9nEBsNfq0Xo90OWx6yuo/edit#heading=h.9dwoku9340md

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/bd8121e747b5
Add complete subtyping and equivalence algorithm. r=lth

Comment 3

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/bd8121e747b5