Soundness

The type system of WebAssembly is sound, implying both type safety and memory safety with respect to the WebAssembly semantics. For example:

  • All types declared and derived during validation are respected at run time; e.g., every local or global variable will only contain type-correct values, every instruction will only be applied to operands of the expected type, and every function invocation always evaluates to a result of the right type (if it does not trap, throw an exception, or diverge).

  • No memory location will be read or written except those explicitly defined by the program, i.e., as a local, a global, an element in a table, or a location within a linear memory.

  • There is no undefined behavior, i.e., the execution rules cover all possible cases that can occur in a valid program, and the rules are mutually consistent.

Soundness also is instrumental in ensuring additional properties, most notably, encapsulation of function and module scopes: no locals can be accessed outside their own function and no module components can be accessed outside their own module unless they are explicitly exported or imported.

The typing rules defining WebAssembly validation only cover the static components of a WebAssembly program. In order to state and prove soundness precisely, the typing rules must be extended to the dynamic components of the abstract runtime, that is, the store, configurations, and administrative instructions. [1]

Results

Results can be classified by result types as follows.

Results \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\)

  • For each value \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}_i\) in \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\):

    • The value \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}_i\) is valid with some value type \(t_i\).

  • Let \(t^\ast\) be the concatenation of all \(t_i\).

  • Then the result is valid with result type \([t^\ast]\).

\[\frac{ (S \href{../appendix/properties.html#valid-val}{\vdash} \href{../exec/runtime.html#syntax-val}{\mathit{val}} : t)^\ast }{ S \href{../appendix/properties.html#valid-result}{\vdash} \href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast : [t^\ast] }\]

Results \(\href{../exec/runtime.html#syntax-trap}{\mathsf{trap}}\)

\[\frac{ }{ S \href{../appendix/properties.html#valid-result}{\vdash} \href{../exec/runtime.html#syntax-trap}{\mathsf{trap}} : [t^\ast] }\]

Todo

Add validation for exception results.

Store Validity

The following typing rules specify when a runtime store \(S\) is valid. A valid store must consist of function, table, memory, tag, global, and module instances that are themselves valid, relative to \(S\).

To that end, each kind of instance is classified by a respective function, table, memory, tag, or global type. Module instances are classified by module contexts, which are regular contexts repurposed as module types describing the index spaces defined by a module.

Store \(S\)

  • Each function instance \(\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{funcs}}\) must be valid with some function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}_i\).

  • Each table instance \(\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tables}}\) must be valid with some table type \(\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}_i\).

  • Each memory instance \(\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{mems}}\) must be valid with some memory type \(\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}_i\).

  • Each tag instance \(\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tags}}\) must be valid with some tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}_i\).

  • Each global instance \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{globals}}\) must be valid with some global type \(\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}_i\).

  • Each element instance \(\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}}\) must be valid with some reference type \(\href{../syntax/types.html#syntax-reftype}{\mathit{reftype}}_i\).

  • Each data instance \(\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}_i\) in \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}}\) must be valid.

  • Then the store is valid.

\[\begin{split}~\\[-1ex] \frac{ \begin{array}{@{}c@{}} (S \href{../appendix/properties.html#valid-funcinst}{\vdash} \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}} : \href{../syntax/types.html#syntax-functype}{\mathit{functype}})^\ast \qquad (S \href{../appendix/properties.html#valid-tableinst}{\vdash} \href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}} : \href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}})^\ast \\ (S \href{../appendix/properties.html#valid-meminst}{\vdash} \href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}} : \href{../syntax/types.html#syntax-memtype}{\mathit{memtype}})^\ast \qquad (S \href{../appendix/properties.html#valid-taginst}{\vdash} \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}} : \href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}})^\ast \\ (S \href{../appendix/properties.html#valid-globalinst}{\vdash} \href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}} : \href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}})^\ast \\ (S \href{../appendix/properties.html#valid-eleminst}{\vdash} \href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}} : \href{../syntax/types.html#syntax-reftype}{\mathit{reftype}})^\ast \qquad (S \href{../appendix/properties.html#valid-datainst}{\vdash} \href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}} \mathrel{\mbox{ok}})^\ast \\ S = \{ \href{../exec/runtime.html#syntax-store}{\mathsf{funcs}}~\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}^\ast, \href{../exec/runtime.html#syntax-store}{\mathsf{tables}}~\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}^\ast, \href{../exec/runtime.html#syntax-store}{\mathsf{mems}}~\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}^\ast, \href{../exec/runtime.html#syntax-store}{\mathsf{tags}}~\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}^\ast, \\ \href{../exec/runtime.html#syntax-store}{\mathsf{globals}}~\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}^\ast, \href{../exec/runtime.html#syntax-store}{\mathsf{elems}}~\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}^\ast, \href{../exec/runtime.html#syntax-store}{\mathsf{datas}}~\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}^\ast \} \end{array} }{ \href{../appendix/properties.html#valid-store}{\vdash} S \mathrel{\mbox{ok}} }\end{split}\]

Function Instances \(\{\href{../exec/runtime.html#syntax-funcinst}{\mathsf{type}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}, \href{../exec/runtime.html#syntax-funcinst}{\mathsf{module}}~\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}, \href{../exec/runtime.html#syntax-funcinst}{\mathsf{code}}~\href{../syntax/modules.html#syntax-func}{\mathit{func}}\}\)

  • The function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\) must be valid.

  • The module instance \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}\) must be valid with some context \(C\).

  • Under context \(C\), the function \(\href{../syntax/modules.html#syntax-func}{\mathit{func}}\) must be valid with function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\).

  • Then the function instance is valid with function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\).

\[\frac{ \href{../valid/types.html#valid-functype}{\vdash} \href{../syntax/types.html#syntax-functype}{\mathit{functype}} \mathrel{\mbox{ok}} \qquad S \href{../appendix/properties.html#valid-moduleinst}{\vdash} \href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}} : C \qquad C \href{../valid/modules.html#valid-func}{\vdash} \href{../syntax/modules.html#syntax-func}{\mathit{func}} : \href{../syntax/types.html#syntax-functype}{\mathit{functype}} }{ S \href{../appendix/properties.html#valid-funcinst}{\vdash} \{\href{../exec/runtime.html#syntax-funcinst}{\mathsf{type}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}, \href{../exec/runtime.html#syntax-funcinst}{\mathsf{module}}~\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}, \href{../exec/runtime.html#syntax-funcinst}{\mathsf{code}}~\href{../syntax/modules.html#syntax-func}{\mathit{func}}\} : \href{../syntax/types.html#syntax-functype}{\mathit{functype}} }\]

Host Function Instances \(\{\href{../exec/runtime.html#syntax-funcinst}{\mathsf{type}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}, \href{../exec/runtime.html#syntax-funcinst}{\mathsf{hostcode}}~\mathit{hf}\}\)

  • The function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\) must be valid.

  • Let \([t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast]\) be the function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\).

  • For every valid store \(S_1\) extending \(S\) and every sequence \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\) of values whose types coincide with \(t_1^\ast\):

    • Executing \(\mathit{hf}\) in store \(S_1\) with arguments \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\) has a non-empty set of possible outcomes.

    • For every element \(R\) of this set:

      • Either \(R\) must be \(\bot\) (i.e., divergence).

      • Or \(R\) consists of a valid store \(S_2\) extending \(S_1\) and a result \(\href{../exec/runtime.html#syntax-result}{\mathit{result}}\) whose type coincides with \([t_2^\ast]\).

  • Then the function instance is valid with function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\).

\[\begin{split}\frac{ \begin{array}[b]{@{}l@{}} \href{../valid/types.html#valid-functype}{\vdash} [t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] \mathrel{\mbox{ok}} \\ \end{array} \quad \begin{array}[b]{@{}l@{}} \forall S_1, \href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast,~ {\href{../appendix/properties.html#valid-store}{\vdash} S_1 \mathrel{\mbox{ok}}} \wedge {\href{../appendix/properties.html#extend-store}{\vdash} S \href{../appendix/properties.html#extend}{\preceq} S_1} \wedge {S_1 \href{../appendix/properties.html#valid-result}{\vdash} \href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast : [t_1^\ast]} \Longrightarrow {} \\ \qquad \mathit{hf}(S_1; \href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast) \supset \emptyset \wedge {} \\ \qquad \forall R \in \mathit{hf}(S_1; \href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast),~ R = \bot \vee {} \\ \qquad\qquad \exists S_2, \href{../exec/runtime.html#syntax-result}{\mathit{result}},~ {\href{../appendix/properties.html#valid-store}{\vdash} S_2 \mathrel{\mbox{ok}}} \wedge {\href{../appendix/properties.html#extend-store}{\vdash} S_1 \href{../appendix/properties.html#extend}{\preceq} S_2} \wedge {S_2 \href{../appendix/properties.html#valid-result}{\vdash} \href{../exec/runtime.html#syntax-result}{\mathit{result}} : [t_2^\ast]} \wedge R = (S_2; \href{../exec/runtime.html#syntax-result}{\mathit{result}}) \end{array} }{ S \href{../appendix/properties.html#valid-funcinst}{\vdash} \{\href{../exec/runtime.html#syntax-funcinst}{\mathsf{type}}~[t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast], \href{../exec/runtime.html#syntax-funcinst}{\mathsf{hostcode}}~\mathit{hf}\} : [t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] }\end{split}\]

Note

This rule states that, if appropriate pre-conditions about store and arguments are satisfied, then executing the host function must satisfy appropriate post-conditions about store and results. The post-conditions match the ones in the execution rule for invoking host functions.

Any store under which the function is invoked is assumed to be an extension of the current store. That way, the function itself is able to make sufficient assumptions about future stores.

Table Instances \(\{ \href{../exec/runtime.html#syntax-tableinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t), \href{../exec/runtime.html#syntax-tableinst}{\mathsf{elem}}~\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^\ast \}\)

  • The table type \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t\) must be valid.

  • The length of \(\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^\ast\) must equal \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}.\href{../syntax/types.html#syntax-limits}{\mathsf{min}}\).

  • For each reference \(\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}_i\) in the table’s elements \(\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^n\):

  • Then the table instance is valid with table type \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t\).

\[\frac{ \href{../valid/types.html#valid-tabletype}{\vdash} \href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t \mathrel{\mbox{ok}} \qquad n = \href{../syntax/types.html#syntax-limits}{\mathit{limits}}.\href{../syntax/types.html#syntax-limits}{\mathsf{min}} \qquad (S \vdash \href{../exec/runtime.html#syntax-ref}{\mathit{ref}} : t)^n }{ S \href{../appendix/properties.html#valid-tableinst}{\vdash} \{ \href{../exec/runtime.html#syntax-tableinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t), \href{../exec/runtime.html#syntax-tableinst}{\mathsf{elem}}~\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^n \} : \href{../syntax/types.html#syntax-limits}{\mathit{limits}}~t }\]

Memory Instances \(\{ \href{../exec/runtime.html#syntax-meminst}{\mathsf{type}}~\href{../syntax/types.html#syntax-limits}{\mathit{limits}}, \href{../exec/runtime.html#syntax-meminst}{\mathsf{data}}~b^\ast \}\)

  • The memory type \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}\) must be valid.

  • The length of \(b^\ast\) must equal \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}.\href{../syntax/types.html#syntax-limits}{\mathsf{min}}\) multiplied by the page size \(64\,\mathrm{Ki}\).

  • Then the memory instance is valid with memory type \(\href{../syntax/types.html#syntax-limits}{\mathit{limits}}\).

\[\frac{ \href{../valid/types.html#valid-memtype}{\vdash} \href{../syntax/types.html#syntax-limits}{\mathit{limits}} \mathrel{\mbox{ok}} \qquad n = \href{../syntax/types.html#syntax-limits}{\mathit{limits}}.\href{../syntax/types.html#syntax-limits}{\mathsf{min}} \cdot 64\,\mathrm{Ki} }{ S \href{../appendix/properties.html#valid-meminst}{\vdash} \{ \href{../exec/runtime.html#syntax-meminst}{\mathsf{type}}~\href{../syntax/types.html#syntax-limits}{\mathit{limits}}, \href{../exec/runtime.html#syntax-meminst}{\mathsf{data}}~b^n \} : \href{../syntax/types.html#syntax-limits}{\mathit{limits}} }\]

Tag Instances \(\{ \href{../exec/runtime.html#syntax-taginst}{\mathsf{type}}~\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}} \}\)

  • The tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}\) must be valid.

  • Then the tag instance is valid with tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}\).

\[\frac{ \href{../valid/types.html#valid-tagtype}{\vdash} \href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}} \mathrel{\mbox{ok}} }{ S \href{../appendix/properties.html#valid-taginst}{\vdash} \{ \href{../exec/runtime.html#syntax-taginst}{\mathsf{type}}~\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}} \} : \href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}} }\]

Global Instances \(\{ \href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t), \href{../exec/runtime.html#syntax-globalinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}} \}\)

  • The global type \(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t\) must be valid.

  • The value \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}\) must be valid with value type \(t\).

  • Then the global instance is valid with global type \(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t\).

\[\frac{ \href{../valid/types.html#valid-globaltype}{\vdash} \href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t \mathrel{\mbox{ok}} \qquad S \href{../appendix/properties.html#valid-val}{\vdash} \href{../exec/runtime.html#syntax-val}{\mathit{val}} : t }{ S \href{../appendix/properties.html#valid-globalinst}{\vdash} \{ \href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t), \href{../exec/runtime.html#syntax-globalinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}} \} : \href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t }\]

Element Instances \(\{ \href{../exec/runtime.html#syntax-eleminst}{\mathsf{elem}}~\mathit{fa}^\ast \}\)

  • For each reference \(\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}_i\) in the elements \(\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^n\):

  • Then the element instance is valid with reference type \(t\).

\[\frac{ (S \vdash \href{../exec/runtime.html#syntax-ref}{\mathit{ref}} : t)^\ast }{ S \href{../appendix/properties.html#valid-eleminst}{\vdash} \{ \href{../exec/runtime.html#syntax-eleminst}{\mathsf{type}}~t, \href{../exec/runtime.html#syntax-eleminst}{\mathsf{elem}}~\href{../exec/runtime.html#syntax-ref}{\mathit{ref}}^\ast \} \mathrel{\mbox{ok}} }\]

Data Instances \(\{ \href{../exec/runtime.html#syntax-datainst}{\mathsf{data}}~b^\ast \}\)

  • The data instance is valid.

\[\frac{ }{ S \href{../appendix/properties.html#valid-datainst}{\vdash} \{ \href{../exec/runtime.html#syntax-datainst}{\mathsf{data}}~b^\ast \} \mathrel{\mbox{ok}} }\]

Export Instances \(\{ \href{../exec/runtime.html#syntax-exportinst}{\mathsf{name}}~\href{../syntax/values.html#syntax-name}{\mathit{name}}, \href{../exec/runtime.html#syntax-exportinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-externval}{\mathit{externval}} \}\)

  • The external value \(\href{../exec/runtime.html#syntax-externval}{\mathit{externval}}\) must be valid with some external type \(\href{../syntax/types.html#syntax-externtype}{\mathit{externtype}}\).

  • Then the export instance is valid.

\[\frac{ S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathit{externval}} : \href{../syntax/types.html#syntax-externtype}{\mathit{externtype}} }{ S \href{../appendix/properties.html#valid-exportinst}{\vdash} \{ \href{../exec/runtime.html#syntax-exportinst}{\mathsf{name}}~\href{../syntax/values.html#syntax-name}{\mathit{name}}, \href{../exec/runtime.html#syntax-exportinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-externval}{\mathit{externval}} \} \mathrel{\mbox{ok}} }\]

Module Instances \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}\)

  • Each function type \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{types}}\) must be valid.

  • For each function address \(\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{funcaddrs}}\), the external value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}_i\) must be valid with some external type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{func}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}'_i\).

  • For each table address \(\href{../exec/runtime.html#syntax-tableaddr}{\mathit{tableaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{tableaddrs}}\), the external value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{table}}~\href{../exec/runtime.html#syntax-tableaddr}{\mathit{tableaddr}}_i\) must be valid with some external type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{table}}~\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}_i\).

  • For each memory address \(\href{../exec/runtime.html#syntax-memaddr}{\mathit{memaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{memaddrs}}\), the external value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{mem}}~\href{../exec/runtime.html#syntax-memaddr}{\mathit{memaddr}}_i\) must be valid with some external type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{mem}}~\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}_i\).

  • For each tag address \(\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{tagaddrs}}\), the external value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}_i\) must be valid with some external type \(\href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}_i\).

  • For each global address \(\href{../exec/runtime.html#syntax-globaladdr}{\mathit{globaladdr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{globaladdrs}}\), the external value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{global}}~\href{../exec/runtime.html#syntax-globaladdr}{\mathit{globaladdr}}_i\) must be valid with some external type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{global}}~\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}_i\).

  • For each element address \(\href{../exec/runtime.html#syntax-elemaddr}{\mathit{elemaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{elemaddrs}}\), the element instance \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}}[\href{../exec/runtime.html#syntax-elemaddr}{\mathit{elemaddr}}_i]\) must be valid with some reference type \(\href{../syntax/types.html#syntax-reftype}{\mathit{reftype}}_i\).

  • For each data address \(\href{../exec/runtime.html#syntax-dataaddr}{\mathit{dataaddr}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{dataaddrs}}\), the data instance \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}}[\href{../exec/runtime.html#syntax-dataaddr}{\mathit{dataaddr}}_i]\) must be valid.

  • Each export instance \(\href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{exports}}\) must be valid.

  • For each export instance \(\href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}}_i\) in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{exports}}\), the name \(\href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}}_i.\href{../exec/runtime.html#syntax-exportinst}{\mathsf{name}}\) must be different from any other name occurring in \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{exports}}\).

  • Let \({\href{../syntax/types.html#syntax-functype}{\mathit{functype}}'}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-functype}{\mathit{functype}}'_i\) in order.

  • Let \(\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}_i\) in order.

  • Let \(\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}_i\) in order.

  • Let \(\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}_i\) in order.

  • Let \(\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}_i\) in order.

  • Let \(\href{../syntax/types.html#syntax-reftype}{\mathit{reftype}}^\ast\) be the concatenation of all \(\href{../syntax/types.html#syntax-reftype}{\mathit{reftype}}_i\) in order.

  • Let \(n\) be the length of \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}.\href{../exec/runtime.html#syntax-moduleinst}{\mathsf{dataaddrs}}\).

  • Then the module instance is valid with context | \(\{\href{../valid/conventions.html#context}{\mathsf{types}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}^\ast, \href{../valid/conventions.html#context}{\mathsf{funcs}}~{\href{../syntax/types.html#syntax-functype}{\mathit{functype}}'}^\ast, \href{../valid/conventions.html#context}{\mathsf{tables}}~\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}^\ast, \href{../valid/conventions.html#context}{\mathsf{mems}}~\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}^\ast, \href{../valid/conventions.html#context}{\mathsf{tags}}~\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}}^\ast, \href{../valid/conventions.html#context}{\mathsf{globals}}~\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}^\ast\}\).

\[\begin{split}~\\[-1ex] \frac{ \begin{array}{@{}c@{}} (\href{../valid/types.html#valid-functype}{\vdash} \href{../syntax/types.html#syntax-functype}{\mathit{functype}} \mathrel{\mbox{ok}})^\ast \\ (S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{func}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}')^\ast \qquad (S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{table}}~\href{../exec/runtime.html#syntax-tableaddr}{\mathit{tableaddr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{table}}~\href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}})^\ast \\ (S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{mem}}~\href{../exec/runtime.html#syntax-memaddr}{\mathit{memaddr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{mem}}~\href{../syntax/types.html#syntax-memtype}{\mathit{memtype}})^\ast \qquad (S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}} : \href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~\href{../syntax/types.html#syntax-tagtype}{\mathit{tagtype}})^\ast \\ (S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{global}}~\href{../exec/runtime.html#syntax-globaladdr}{\mathit{globaladdr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{global}}~\href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}})^\ast \\ (S \href{../appendix/properties.html#valid-eleminst}{\vdash} S.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}}[\href{../exec/runtime.html#syntax-elemaddr}{\mathit{elemaddr}}] : \href{../syntax/types.html#syntax-reftype}{\mathit{reftype}})^\ast \qquad (S \href{../appendix/properties.html#valid-datainst}{\vdash} S.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}}[\href{../exec/runtime.html#syntax-dataaddr}{\mathit{dataaddr}}] \mathrel{\mbox{ok}})^n \\ (S \href{../appendix/properties.html#valid-exportinst}{\vdash} \href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}} \mathrel{\mbox{ok}})^\ast \qquad (\href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}}.\href{../exec/runtime.html#syntax-exportinst}{\mathsf{name}})^\ast ~\mbox{disjoint} \end{array} }{ S \href{../appendix/properties.html#valid-moduleinst}{\vdash} \{ \begin{array}[t]{@{}l@{~}l@{}} \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{types}} & \href{../syntax/types.html#syntax-functype}{\mathit{functype}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{funcaddrs}} & \href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{tableaddrs}} & \href{../exec/runtime.html#syntax-tableaddr}{\mathit{tableaddr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{memaddrs}} & \href{../exec/runtime.html#syntax-memaddr}{\mathit{memaddr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{tagaddrs}} & \href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{globaladdrs}} & \href{../exec/runtime.html#syntax-globaladdr}{\mathit{globaladdr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{elemaddrs}} & \href{../exec/runtime.html#syntax-elemaddr}{\mathit{elemaddr}}^\ast, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{dataaddrs}} & \href{../exec/runtime.html#syntax-dataaddr}{\mathit{dataaddr}}^n, \\ \href{../exec/runtime.html#syntax-moduleinst}{\mathsf{exports}} & \href{../exec/runtime.html#syntax-exportinst}{\mathit{exportinst}}^\ast ~\} : \{ \begin{array}[t]{@{}l@{~}l@{}} \href{../valid/conventions.html#context}{\mathsf{types}} & \href{../syntax/types.html#syntax-functype}{\mathit{functype}}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{funcs}} & {\href{../syntax/types.html#syntax-functype}{\mathit{functype}}'}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{tables}} & \href{../syntax/types.html#syntax-tabletype}{\mathit{tabletype}}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{mems}} & \href{../syntax/types.html#syntax-memtype}{\mathit{memtype}}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{globals}} & \href{../syntax/types.html#syntax-globaltype}{\mathit{globaltype}}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{elems}} & \href{../syntax/types.html#syntax-reftype}{\mathit{reftype}}^\ast, \\ \href{../valid/conventions.html#context}{\mathsf{datas}} & {\mathrel{\mbox{ok}}}^n ~\} \end{array} \end{array} }\end{split}\]

Configuration Validity

To relate the WebAssembly type system to its execution semantics, the typing rules for instructions must be extended to configurations \(S;T\), which relates the store to execution threads.

Configurations and threads are classified by their result type. In addition to the store \(S\), threads are typed under a return type \(\href{../syntax/types.html#syntax-resulttype}{\mathit{resulttype}}^?\), which controls whether and with which type a \(\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{return}}\) instruction is allowed. This type is absent (\(\epsilon\)) except for instruction sequences inside an administrative \(\href{../exec/runtime.html#syntax-frame}{\mathsf{frame}}\) instruction.

Finally, frames are classified with frame contexts, which extend the module contexts of a frame’s associated module instance with the locals that the frame contains.

Configurations \(S;T\)

\[\frac{ \href{../appendix/properties.html#valid-store}{\vdash} S \mathrel{\mbox{ok}} \qquad S; \epsilon \href{../appendix/properties.html#valid-thread}{\vdash} T : [t^\ast] }{ \href{../appendix/properties.html#valid-config}{\vdash} S; T : [t^\ast] }\]

Threads \(F;\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\)

  • Let \(\href{../syntax/types.html#syntax-resulttype}{\mathit{resulttype}}^?\) be the current allowed return type.

  • The frame \(F\) must be valid with a context \(C\).

  • Let \(C'\) be the same context as \(C\), but with \(\href{../valid/conventions.html#context}{\mathsf{return}}\) set to \(\href{../syntax/types.html#syntax-resulttype}{\mathit{resulttype}}^?\).

  • Under context \(C'\), the instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\) must be valid with some type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^\ast]\).

  • Then the thread is valid with the result type \([t^\ast]\).

\[\frac{ S \href{../appendix/properties.html#valid-frame}{\vdash} F : C \qquad S; C,\href{../valid/conventions.html#context}{\mathsf{return}}~\href{../syntax/types.html#syntax-resulttype}{\mathit{resulttype}}^? \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^\ast] }{ S; \href{../syntax/types.html#syntax-resulttype}{\mathit{resulttype}}^? \href{../appendix/properties.html#valid-thread}{\vdash} F; \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [t^\ast] }\]

Frames \(\{\href{../exec/runtime.html#syntax-frame}{\mathsf{locals}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast, \href{../exec/runtime.html#syntax-frame}{\mathsf{module}}~\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}\}\)

  • The module instance \(\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}\) must be valid with some module context \(C\).

  • Each value \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}_i\) in \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\) must be valid with some value type \(t_i\).

  • Let \(t^\ast\) be the concatenation of all \(t_i\) in order.

  • Let \(C'\) be the same context as \(C\), but with the value types \(t^\ast\) prepended to the \(\href{../valid/conventions.html#context}{\mathsf{locals}}\) vector.

  • Then the frame is valid with frame context \(C'\).

\[\frac{ S \href{../appendix/properties.html#valid-moduleinst}{\vdash} \href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}} : C \qquad (S \href{../appendix/properties.html#valid-val}{\vdash} \href{../exec/runtime.html#syntax-val}{\mathit{val}} : t)^\ast }{ S \href{../appendix/properties.html#valid-frame}{\vdash} \{\href{../exec/runtime.html#syntax-frame}{\mathsf{locals}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast, \href{../exec/runtime.html#syntax-frame}{\mathsf{module}}~\href{../exec/runtime.html#syntax-moduleinst}{\mathit{moduleinst}}\} : (C, \href{../valid/conventions.html#context}{\mathsf{locals}}~t^\ast) }\]

Administrative Instructions

Typing rules for administrative instructions are specified as follows. In addition to the context \(C\), typing of these instructions is defined under a given store \(S\). To that end, all previous typing judgements \(C \vdash \mathit{prop}\) are generalized to include the store, as in \(S; C \vdash \mathit{prop}\), by implicitly adding \(S\) to all rules – \(S\) is never modified by the pre-existing rules, but it is accessed in the extra rules for administrative instructions given below.

\(\href{../exec/runtime.html#syntax-trap}{\mathsf{trap}}\)

  • The instruction is valid with type \([t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast]\), for any sequences of value types \(t_1^\ast\) and \(t_2^\ast\).

\[\frac{ }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-trap}{\mathsf{trap}} : [t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] }\]

\(\href{../exec/runtime.html#syntax-ref.extern}{\mathsf{ref{.}extern}}~\href{../exec/runtime.html#syntax-externaddr}{\mathit{externaddr}}\)

  • The instruction is valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [\href{../syntax/types.html#syntax-reftype}{\mathsf{externref}}]\).

\[\frac{ }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-ref.extern}{\mathsf{ref{.}extern}}~\href{../exec/runtime.html#syntax-externaddr}{\mathit{externaddr}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [\href{../syntax/types.html#syntax-reftype}{\mathsf{externref}}] }\]

\(\href{../exec/runtime.html#syntax-ref}{\mathsf{ref}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}\)

  • The external function value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}\) must be valid with external function type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{func}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}}\).

  • Then the instruction is valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [\href{../syntax/types.html#syntax-reftype}{\mathsf{funcref}}]\).

\[\frac{ S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{func}}~\href{../syntax/types.html#syntax-functype}{\mathit{functype}} }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-ref}{\mathsf{ref}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [\href{../syntax/types.html#syntax-reftype}{\mathsf{funcref}}] }\]

\(\href{../exec/runtime.html#syntax-throwadm}{\mathsf{throw}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}\)

  • The external tag value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}\) must be valid with external tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t^\ast]\href{../syntax/types.html#syntax-functype}{\rightarrow}[]\).

  • Then the instruction is valid with type \([t_1^\ast t^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast]\) for any sequences of value types \(t_1^\ast\) and \(t_2^\ast\).

\[\frac{ S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}} : \href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t^\ast]\href{../syntax/types.html#syntax-functype}{\rightarrow}[] }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-throwadm}{\mathsf{throw}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}} : [t_1^\ast t^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] }\]

\(\href{../exec/runtime.html#syntax-handleradm}{\mathsf{handler}}_n\{(\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}^?~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1^\ast)^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_2^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}}\)

  • Let \(C'\) be the same context as \(C\), but with the label type \([t_2^\ast]\) prepended to the \(\href{../valid/conventions.html#context}{\mathsf{labels}}\) vector.

  • Under context \(C'\), the instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_2^\ast\) must be valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n]\).

  • Let \(C''\) be the same context as \(C\), but with the label type \((\href{../valid/conventions.html#context}{\mathsf{catch}}~[t_2^n])\) prepended to the \(\href{../valid/conventions.html#context}{\mathsf{labels}}\) vector.

  • Under context \(C''\), for every \(\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}^?\) and associated instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1^\ast\):

    • If \(\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}^? = \epsilon\), then \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1^\ast\) must be valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n]\).

    • Else:

      • The external tag value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}\) must be valid with some external tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} []\).

      • The instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1^\ast\) must be valid with type \([t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n]\).

  • Then the compound instruction is valid under context \(C'\) with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n]\).

\[\begin{split}\frac{ \begin{array}{@{}c@{}} ((S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}} : \href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t_1^\ast]\href{../syntax/types.html#syntax-functype}{\rightarrow}[])^? \\ ~~S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,(\href{../valid/conventions.html#context}{\mathsf{catch}}~[t_2^n]) \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1^\ast : [(t_1^\ast)^?] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n])^\ast \\ S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t_2^n] \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_2^\ast : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n] \\ \end{array} }{ S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t_2^n] \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-handleradm}{\mathsf{handler}}_n\{(\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}^?~{\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_1}^\ast)^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_2^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^n] }\end{split}\]

\(\href{../exec/runtime.html#syntax-handleradm}{\mathsf{handler}}_n\{l\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}}\)

  • The label \(C.\href{../valid/conventions.html#context}{\mathsf{labels}}[l]\) must be defined in the context.

  • Let \(C'\) be the same context as \(C\), but with the label \([t^\ast]\) prepended to the \(\href{../valid/conventions.html#context}{\mathsf{labels}}\) vector.

  • Under context \(C'\), the instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\) must be valid with type \([]\href{../syntax/types.html#syntax-functype}{\rightarrow}[t^n]\).

  • Then the compound instruction is valid under context \(C'\) with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n]\).

\[\frac{ S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t^n] \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n] \qquad C.\href{../valid/conventions.html#context}{\mathsf{labels}}[l] = \href{../valid/conventions.html#context}{\mathsf{catch}}^?~[t_0^\ast] }{ S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t^n] \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-handleradm}{\mathsf{handler}}_n\{l\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n] }\]

\(\href{../exec/runtime.html#syntax-caughtadm}{\mathsf{caught}}_n\{\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}}\)

  • The external tag value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}\) must be valid with some external tag type \(\href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t_0^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} []\).

  • The values \(\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\) must be of type \([t_0^\ast]\).

  • The label \(C.\href{../valid/conventions.html#context}{\mathsf{labels}}[0]\) must be defined in the context.

  • Let \((\href{../valid/conventions.html#context}{\mathsf{catch}}^?~[t^n])\) be the label type \(C.\href{../valid/conventions.html#context}{\mathsf{labels}}[0]\).

  • The \(\href{../valid/conventions.html#context}{\mathsf{catch}}\) must not be present in the label type \(C.\href{../valid/conventions.html#context}{\mathsf{labels}}[0]\).

  • Let \(C''\) be the same context as \(C\), but with the label type \((\href{../valid/conventions.html#context}{\mathsf{catch}}~[t^n])\) replacing the first element of the \(\href{../valid/conventions.html#context}{\mathsf{labels}}\) vector.

  • Under context \(C''\), the instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\) must be valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n]\).

  • Then the compound instruction is valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n]\).

\[\frac{ S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{tag}}~\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}} : \href{../syntax/types.html#syntax-tagtype}{\mathsf{tag}}~[t_0^\ast]\href{../syntax/types.html#syntax-functype}{\rightarrow}[] \qquad (val : t_0)^\ast \qquad S; C',\href{../valid/conventions.html#context}{\mathsf{labels}}\,(\href{../valid/conventions.html#context}{\mathsf{catch}}~[t^n]) \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n] }{ S; C',\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t^n] \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-caughtadm}{\mathsf{caught}}_n\{\href{../exec/runtime.html#syntax-tagaddr}{\mathit{tagaddr}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n] }\]

\(\href{../exec/runtime.html#syntax-invoke}{\mathsf{invoke}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}\)

  • The external function value \(\href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}}\) must be valid with external function type \(\href{../syntax/types.html#syntax-externtype}{\mathsf{func}} ([t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast])\).

  • Then the instruction is valid with type \([t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast]\).

\[\frac{ S \href{../exec/modules.html#valid-externval}{\vdash} \href{../exec/runtime.html#syntax-externval}{\mathsf{func}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}} : \href{../syntax/types.html#syntax-externtype}{\mathsf{func}}~[t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-invoke}{\mathsf{invoke}}~\href{../exec/runtime.html#syntax-funcaddr}{\mathit{funcaddr}} : [t_1^\ast] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^\ast] }\]

\(\href{../exec/runtime.html#syntax-label}{\mathsf{label}}_n\{\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_0^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}}\)

  • The instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_0^\ast\) must be valid with some type \([t_1^n] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*]\).

  • Let \(C'\) be the same context as \(C\), but with the label type \([t_1^n]\) prepended to the \(\href{../valid/conventions.html#context}{\mathsf{labels}}\) vector.

  • Under context \(C'\), the instruction sequence \(\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\) must be valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*]\).

  • Then the compound instruction is valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*]\).

\[\frac{ S; C \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_0^\ast : [t_1^n] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*] \qquad S; C,\href{../valid/conventions.html#context}{\mathsf{labels}}\,[t_1^n] \href{../valid/instructions.html#valid-instr-seq}{\vdash} \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*] }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-label}{\mathsf{label}}_n\{\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}_0^\ast\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t_2^*] }\]

\(\href{../exec/runtime.html#syntax-frame}{\mathsf{frame}}_n\{F\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}}\)

  • Under the return type \([t^n]\), the thread \(F; \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast\) must be valid with result type \([t^n]\).

  • Then the compound instruction is valid with type \([] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n]\).

\[\frac{ S; [t^n] \href{../valid/instructions.html#valid-instr-seq}{\vdash} F; \href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast : [t^n] }{ S; C \href{../appendix/properties.html#valid-instr-admin}{\vdash} \href{../exec/runtime.html#syntax-frame}{\mathsf{frame}}_n\{F\}~\href{../syntax/instructions.html#syntax-instr}{\mathit{instr}}^\ast~\href{../syntax/instructions.html#syntax-instr-control}{\mathsf{end}} : [] \href{../syntax/types.html#syntax-functype}{\rightarrow} [t^n] }\]

Store Extension

Programs can mutate the store and its contained instances. Any such modification must respect certain invariants, such as not removing allocated instances or changing immutable definitions. While these invariants are inherent to the execution semantics of WebAssembly instructions and modules, host functions do not automatically adhere to them. Consequently, the required invariants must be stated as explicit constraints on the invocation of host functions. Soundness only holds when the embedder ensures these constraints.

The necessary constraints are codified by the notion of store extension: a store state \(S'\) extends state \(S\), written \(S \href{../appendix/properties.html#extend}{\preceq} S'\), when the following rules hold.

Note

Extension does not imply that the new store is valid, which is defined separately above.

Store \(S\)

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{funcs}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tables}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{mems}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tags}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{globals}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}}\) must not shrink.

  • The length of \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}}\) must not shrink.

  • For each function instance \(\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{funcs}}\), the new function instance must be an extension of the old.

  • For each table instance \(\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tables}}\), the new table instance must be an extension of the old.

  • For each memory instance \(\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{mems}}\), the new memory instance must be an extension of the old.

  • For each tag instance \(\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{tags}}\), the new tag instance must be an extension of the old.

  • For each global instance \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{globals}}\), the new global instance must be an extension of the old.

  • For each element instance \(\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}}\), the new global instance must be an extension of the old.

  • For each data instance \(\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}_i\) in the original \(S.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}}\), the new global instance must be an extension of the old.

\[\begin{split}\frac{ \begin{array}{@{}ccc@{}} S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{funcs}} = \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{funcs}} = {\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}'_1}^\ast~\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}_2^\ast & (\href{../appendix/properties.html#extend-funcinst}{\vdash} \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{tables}} = \href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{tables}} = {\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}'_1}^\ast~\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}_2^\ast & (\href{../appendix/properties.html#extend-tableinst}{\vdash} \href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{mems}} = \href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{mems}} = {\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}'_1}^\ast~\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}_2^\ast & (\href{../appendix/properties.html#extend-meminst}{\vdash} \href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{tags}} = \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{tags}} = {\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}'_1}^\ast~\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}_2^\ast & (\href{../appendix/properties.html#extend-taginst}{\vdash} \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{globals}} = \href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{globals}} = {\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}'_1}^\ast~\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}_2^\ast & (\href{../appendix/properties.html#extend-globalinst}{\vdash} \href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}} = \href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{elems}} = {\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}'_1}^\ast~\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}_2^\ast & (\href{../appendix/properties.html#extend-eleminst}{\vdash} \href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}'_1)^\ast \\ S_1.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}} = \href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}_1^\ast & S_2.\href{../exec/runtime.html#syntax-store}{\mathsf{datas}} = {\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}'_1}^\ast~\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}_2^\ast & (\href{../appendix/properties.html#extend-datainst}{\vdash} \href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}_1 \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}'_1)^\ast \\ \end{array} }{ \href{../appendix/properties.html#extend-store}{\vdash} S_1 \href{../appendix/properties.html#extend}{\preceq} S_2 }\end{split}\]

Function Instance \(\href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}}\)

  • A function instance must remain unchanged.

\[\frac{ }{ \href{../appendix/properties.html#extend-funcinst}{\vdash} \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}} \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-funcinst}{\mathit{funcinst}} }\]

Table Instance \(\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}\)

  • The table type \(\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}.\href{../exec/runtime.html#syntax-tableinst}{\mathsf{type}}\) must remain unchanged.

  • The length of \(\href{../exec/runtime.html#syntax-tableinst}{\mathit{tableinst}}.\href{../exec/runtime.html#syntax-tableinst}{\mathsf{elem}}\) must not shrink.

\[\frac{ n_1 \leq n_2 }{ \href{../appendix/properties.html#extend-tableinst}{\vdash} \{\href{../exec/runtime.html#syntax-tableinst}{\mathsf{type}}~\mathit{tt}, \href{../exec/runtime.html#syntax-tableinst}{\mathsf{elem}}~(\mathit{fa}_1^?)^{n_1}\} \href{../appendix/properties.html#extend}{\preceq} \{\href{../exec/runtime.html#syntax-tableinst}{\mathsf{type}}~\mathit{tt}, \href{../exec/runtime.html#syntax-tableinst}{\mathsf{elem}}~(\mathit{fa}_2^?)^{n_2}\} }\]

Memory Instance \(\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}\)

  • The memory type \(\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}.\href{../exec/runtime.html#syntax-meminst}{\mathsf{type}}\) must remain unchanged.

  • The length of \(\href{../exec/runtime.html#syntax-meminst}{\mathit{meminst}}.\href{../exec/runtime.html#syntax-meminst}{\mathsf{data}}\) must not shrink.

\[\frac{ n_1 \leq n_2 }{ \href{../appendix/properties.html#extend-meminst}{\vdash} \{\href{../exec/runtime.html#syntax-meminst}{\mathsf{type}}~\mathit{mt}, \href{../exec/runtime.html#syntax-meminst}{\mathsf{data}}~b_1^{n_1}\} \href{../appendix/properties.html#extend}{\preceq} \{\href{../exec/runtime.html#syntax-meminst}{\mathsf{type}}~\mathit{mt}, \href{../exec/runtime.html#syntax-meminst}{\mathsf{data}}~b_2^{n_2}\} }\]

Tag Instance \(\href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}}\)

  • A tag instance must remain unchanged.

\[\frac{ }{ \href{../appendix/properties.html#extend-taginst}{\vdash} \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}} \href{../appendix/properties.html#extend}{\preceq} \href{../exec/runtime.html#syntax-taginst}{\mathit{taginst}} }\]

Global Instance \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}\)

  • The global type \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}.\href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}\) must remain unchanged.

  • Let \(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t\) be the structure of \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}.\href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}\).

  • If \(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}\) is \(\href{../syntax/types.html#syntax-mut}{\mathsf{const}}\), then the value \(\href{../exec/runtime.html#syntax-globalinst}{\mathit{globalinst}}.\href{../exec/runtime.html#syntax-globalinst}{\mathsf{value}}\) must remain unchanged.

\[\frac{ \href{../syntax/types.html#syntax-mut}{\mathit{mut}} = \href{../syntax/types.html#syntax-mut}{\mathsf{var}} \vee \href{../exec/runtime.html#syntax-val}{\mathit{val}}_1 = \href{../exec/runtime.html#syntax-val}{\mathit{val}}_2 }{ \href{../appendix/properties.html#extend-globalinst}{\vdash} \{\href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t), \href{../exec/runtime.html#syntax-globalinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}_1\} \href{../appendix/properties.html#extend}{\preceq} \{\href{../exec/runtime.html#syntax-globalinst}{\mathsf{type}}~(\href{../syntax/types.html#syntax-mut}{\mathit{mut}}~t), \href{../exec/runtime.html#syntax-globalinst}{\mathsf{value}}~\href{../exec/runtime.html#syntax-val}{\mathit{val}}_2\} }\]

Element Instance \(\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}\)

  • The vector \(\href{../exec/runtime.html#syntax-eleminst}{\mathit{eleminst}}.\href{../exec/runtime.html#syntax-eleminst}{\mathsf{elem}}\) must either remain unchanged or shrink to length \(0\).

\[\frac{ \mathit{fa}_1^\ast = \mathit{fa}_2^\ast \vee \mathit{fa}_2^\ast = \epsilon }{ \href{../appendix/properties.html#extend-eleminst}{\vdash} \{\href{../exec/runtime.html#syntax-eleminst}{\mathsf{elem}}~\mathit{fa}_1^\ast\} \href{../appendix/properties.html#extend}{\preceq} \{\href{../exec/runtime.html#syntax-eleminst}{\mathsf{elem}}~\mathit{fa}_2^\ast\} }\]

Data Instance \(\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}\)

  • The vector \(\href{../exec/runtime.html#syntax-datainst}{\mathit{datainst}}.\href{../exec/runtime.html#syntax-datainst}{\mathsf{data}}\) must either remain unchanged or shrink to length \(0\).

\[\frac{ b_1^\ast = b_2^\ast \vee b_2^\ast = \epsilon }{ \href{../appendix/properties.html#extend-datainst}{\vdash} \{\href{../exec/runtime.html#syntax-datainst}{\mathsf{data}}~b_1^\ast\} \href{../appendix/properties.html#extend}{\preceq} \{\href{../exec/runtime.html#syntax-datainst}{\mathsf{data}}~b_2^\ast\} }\]

Theorems

Given the definition of valid configurations, the standard soundness theorems hold. [2] [3]

Theorem (Preservation). If a configuration \(S;T\) is valid with result type \([t^\ast]\) (i.e., \(\href{../appendix/properties.html#valid-config}{\vdash} S;T : [t^\ast]\)), and steps to \(S';T'\) (i.e., \(S;T \href{../exec/conventions.html#formal-notation}{\hookrightarrow} S';T'\)), then \(S';T'\) is a valid configuration with the same result type (i.e., \(\href{../appendix/properties.html#valid-config}{\vdash} S';T' : [t^\ast]\)). Furthermore, \(S'\) is an extension of \(S\) (i.e., \(\href{../appendix/properties.html#extend-store}{\vdash} S \href{../appendix/properties.html#extend}{\preceq} S'\)).

A terminal thread is one whose sequence of instructions is a result. A terminal configuration is a configuration whose thread is terminal.

Theorem (Progress). If a configuration \(S;T\) is valid (i.e., \(\href{../appendix/properties.html#valid-config}{\vdash} S;T : [t^\ast]\) for some result type \([t^\ast]\)), then either it is terminal, or it can step to some configuration \(S';T'\) (i.e., \(S;T \href{../exec/conventions.html#formal-notation}{\hookrightarrow} S';T'\)).

From Preservation and Progress the soundness of the WebAssembly type system follows directly.

Corollary (Soundness). If a configuration \(S;T\) is valid (i.e., \(\href{../appendix/properties.html#valid-config}{\vdash} S;T : [t^\ast]\) for some result type \([t^\ast]\)), then it either diverges or takes a finite number of steps to reach a terminal configuration \(S';T'\) (i.e., \(S;T \href{../exec/conventions.html#formal-notation}{\hookrightarrow}^\ast S';T'\)) that is valid with the same result type (i.e., \(\href{../appendix/properties.html#valid-config}{\vdash} S';T' : [t^\ast]\)) and where \(S'\) is an extension of \(S\) (i.e., \(\href{../appendix/properties.html#extend-store}{\vdash} S \href{../appendix/properties.html#extend}{\preceq} S'\)).

In other words, every thread in a valid configuration either runs forever, traps, throws an exception, or terminates with a result that has the expected type. Consequently, given a valid store, no computation defined by instantiation or invocation of a valid module can “crash” or otherwise (mis)behave in ways not covered by the execution semantics given in this specification.