深入浅出WebAssembly(4) Validation

这系列主要是我对WASM研究的笔记，可能内容比较简略。总共包括：

深入浅出WebAssembly(1) Compilation
深入浅出WebAssembly(2) Basic Api
深入浅出WebAssembly(3) Instructions
深入浅出WebAssembly(4) Validation
深入浅出WebAssembly(5) Memory
深入浅出WebAssembly(6) Binary Format
深入浅出WebAssembly(7) Future
深入浅出WebAssembly(8) Wasm in Rust（TODO）

只有验证通过的模块才能初始化。验证是通过一个在模块ast和内容运行的类型系统(type system)来做的。

Contexts

contexts规定了类型运行的上下文：

\begin{array}{lll} C &::=& \{~ \begin{aligned} \begin{array}{lll} & \mathsf{types} & {\mathit{functype}}^\ast, \\ & {\mathsf{funcs}} & {\mathit{functype}}^\ast, \\ & {\mathsf{tables}} & {\mathit{tabletype}}^\ast, \\ & {\mathsf{mems}} & {\mathit{memtype}}^\ast, \\ & {\mathsf{globals}} & {\mathit{globaltype}}^\ast, \\ & {\mathsf{locals}} & {\mathit{valtype}}^\ast, \\ & {\mathsf{labels}} & {\mathit{resulttype}}^\ast, \\ & {\mathsf{return}} & {\mathit{resulttype}}^? \\ \end{array} \end{aligned} ~\} \end{array}

Locals，labels和return type只用在验证函数体内部语句的时候，在其他地方为空。label代表的是当前上下文的label stack用一系列resulttype表示，是当前context中唯一会随着语句顺序执行而变化的部分。
具体到实际context，一些空field将会被省略
$C, \mathsf{field} A^*$ 表示在同样的context C下，将 $A^*$ prepend到C的field中
我们可以使用 $C.\mathsf{labels}[i]$ 这样的索引语法来表示对应索引空间(index space)中的内容。而context扩展标记 $C,\mathsf{field} A$ 主要用来临时扩展相对索引空间，例如label indices。新的语句将在所有现有语句之前定义，占用索引为0的项并将之前的定义的其他项索引加一

Formal Notation

Conventions

$A:T$ 代表A拥有相应类型T $C \vdash A : T$ 代表在C这样的上下文中，A拥有相应的类型T

通常一个验证规则可以写成如下形式：

\frac{ \mathit{premise}_1 \qquad \mathit{premise}_2 \qquad \dots \qquad \mathit{premise}_n }{ \mathit{conclusion} }

一些规则可以没有前提，称为公理(axiom)，比如i32.add:

\frac{ }{ C \vdash \mathsf{i32}.\mathsf{add} : [\mathsf{i32}~\mathsf{i32}] \rightarrow[\mathsf{i32}] }

再比如local.get的规则可以写成：

\frac{ C.{\mathsf{locals}} = t }{ C \vdash {\mathsf{local.get}}~x : [] {\rightarrow} [t] }

再比如，前提本身也是一个判断：

\frac{ C,{\mathsf{label}}\,[t^?] \vdash {\mathit{instr}}^\ast : [] {\rightarrow} [t^?] }{ C \vdash {\mathsf{block}}~[t^?]~{\mathit{instr}}^\ast~{\mathsf{end}} : [] {\rightarrow} [t^?] }

Instructions

指令能够通过函数类型 $[t_1^\ast] {\rightarrow} [t_2^\ast]$ 来分类。函数类型描述了它怎么操作操作数虚拟机。参数用于push，返回用于pop。如指令 $\mathsf{i32}.\mathsf{add}$ 的类型是 $[\mathsf{i32}~\mathsf{i32}] \rightarrow [\mathsf{i32}]$ ，则表示它能够消耗两个 $\mathsf{i32}$ 参数，并且产生一个新的。

对于一些指令来说，类型规则并不是严格的类型约束，存在多态：

值多态value-polymorphic，其中一些值或者操作数是不限定的，比如所有的Parametric instructions都是（drop，select）
栈多态stack-polymorphic，对栈的状态是不限定的，比如所有控制指令，他们能提供无条件的流程控制。unreachable,br,br_table和return

例如对于select指令，下面两条语句都是合法的：

({\mathsf{i32}}.{\mathsf{const}}~1)({\mathsf{i32}}.{\mathsf{const}}~2)({\mathsf{i32}}.{\mathsf{const}}~3)~~{\mathsf{select}}{}

({\mathsf{f64}}.{\mathsf{const}}~1.0)({\mathsf{f64}}.{\mathsf{const}}~2.0)({\mathsf{i32}}.{\mathsf{const}}~3)~~{\mathsf{select}}{}

另外对于unreachable指令下的不可到达语句，也要进行类型检查。具体检查方式为：如果存在一个满足当前指令块的栈状态的话那么就合法，否则就不合法：

{\mathsf{unreachable}}~~{\mathsf{i32}}.{\mathsf{add}}

是合法的，因为当一个栈状态为 $[\mathsf{i32},\mathsf{i32}]$ 的时候，unreachable的语句能够顺利执行。

{\mathsf{unreachable}}({\mathsf{i64}}.{\mathsf{const}}~0){\mathsf{i32}}.{\mathsf{add}}

是不合法的，因为找不到一个栈能够让这个指令块正常执行。

常见指令的类型定义

Instructions — WebAssembly 1.0