はじめに
RustでWebAssemblyインタプリタを作ったのでその実装の話や、wasmの仕様についての記事です。
HListを使ったジェネリックプログラミングの話や、最後の方には「自作言語 on 自作wasmインタプリタ on 自作wasmインタプリタ」みたいな話も出てきます。
分かりにくい所や間違っている所は指摘してくださると助かります。
リポジトリ
作った成果物のリポジトリです。まだpublishはしていませんがクレートになっています。
cargoのexample実行に対応しているのでそれを見ればだいたい分かると思います。
今回はadc-2019-12-22というタグがついたコミットのソースを元に解説していきます。
https://github.com/kgtkr/wasm-rs/tree/adc-2019-12-22
仕様書
この記事では仕様書を読みながら順番に実装を解説していきます。
いくつかの章に分かれていますが、実装に深く関わるのは以下です。
- Structure
- Validation
- Execution
- Binary Format
- Text Format
今回はこのうちValidationとText Formatを除く部分を実装しました。
Validationは読み込んだモジュールの静的検証についての仕様が書かれています。静的検証は型チェックみたいなものです。今回は間に合わなかったので実装しませんでした。つまり入力されるwasmコードは常に正しいものとして扱います。
Text Formatはwatというwasmのテキストフォーマットについての仕様が書かれています。watとはwasmの命令と1対1対応の命令を持っているテキストフォーマットの言語です。wasmはバイナリフォーマットなので人間が読み書きするのは難しいですが、watであれば比較的読み書きしやすいです。wasmを機械語とするならwatはアセンブリ言語みたいなものです。この記事で出てくるwasmのサンプルコードは基本的にwatのコードです。これを実装することでwasmとwatの相互変換ができるようになりますが、今回はwasmバイナリを読み込んで実行できればいいので実装しませんでした。
wasmインタプリタの実装には直接関係ありませんが、バイナリフォーマットのデコードだけでなくエンコード処理も実装しています。これは元々wasmに出力する自作言語をRustで作ろうと思いバイナリの出力コードを書いていたらインタプリタを作りたくなったから作ったという経緯が理由だったりします。
上記のwasm仕様書はwasmのcore仕様の物です。他にもJSのWebAssembly APIについての仕様などがありますが今回は関係ないので無視します。
Structure
wasmモジュールの構造についての仕様が書かれています。ここを読んでRustのデータ構造に落とし込んでいきます。
例えばvaltypeは以下のように定義されています。
valtype ::= i32 | i64 | f32 | f64
これをRustのデータ構造にすると以下のようになります。
pub enum ValType {
I32,
I64,
F32,
F64,
}
このように順番に定義していって最終的には以下のようなwasmモジュールを表す構造体が定義出来れば完成です。
pub struct Module {
pub types: Vec<FuncType>,
pub funcs: Vec<Func>,
pub tables: Vec<Table>,
pub mems: Vec<Mem>,
pub globals: Vec<Global>,
pub elem: Vec<Elem>,
pub data: Vec<Data>,
pub start: Option<Start>,
pub imports: Vec<Import>,
pub exports: Vec<Export>,
}
Binary Format
Executionは長くなるので先にこっちの解説をします。この章はwasmのバイナリフォーマットについての仕様が書かれています。これを読み実装することで先ほど定義したデータ構造とバイナリデータの相互変換ができるようになります。今回はパーサーコンビネーターライブラリにnomを使いました。Rustには他にもcombineというパーサーコンビネーターライブラリがあります。combineは使ったことがありましたが、nomは使ったことがなかったからという理由でnomを採用しただけで深い理由はありません。昔のnomはマクロをかなり多用したライブラリでしたがマクロを使わずに書けるようになっており使いやすかったです。他にもバイト列と数値型のデコード/エンコードなどを行うのにbyteorderを、leb128という整数の可変長フォーマットのデコード/エンコードを行うのにleb128というライブラリを使っています。
DecoderとEncoderの定義
まずバイト列からデコードできるデータ型を表すトレイトとしてDecoderトレイトを定義します
use nom::{sequence::tuple, IResult};
pub trait Decoder
where
Self: std::marker::Sized,
{
fn decode(input: &[u8]) -> IResult<&[u8], Self>;
fn decode_to_end(input: &[u8]) -> Result<Self, nom::Err<(&[u8], nom::error::ErrorKind)>> {
let (_, (x, _)) = tuple((Self::decode, eof()))(input)?;
Ok(x)
}
}
decode関数はバイト列を受け取って、未処理のバイト列と結果を返します。デコードは失敗する可能性があるのでnomのIResultを使っています。
decode_to_end関数はバイト列を受けとって結果を返します。eofは空の入力を受け取ったら成功し、そうでなければ失敗する独自コンビネーターです。
次にバイト列にエンコードできるデータ型を表すトレイトとしてEncoderトレイトを定義します。
pub trait Encoder {
fn encode(&self, bytes: &mut Vec<u8>);
fn encode_to_vec(&self) -> Vec<u8> {
let mut bytes = Vec::new();
self.encode(&mut bytes);
bytes
}
}
encode関数は可変のバイト列を受け取ってエンコード結果をそこに書き込んでいきます。encode_to_vecはエンコードしてバイト列を返します。
この2つのトレイトを先ほどStructureを見ながら定義したデータ構造に実装していくことでデコードとエンコードを行います。例えばvaltypeの仕様は以下のようになっています。
valtype ::= 0x7F => i32
| 0x7E => i64
| 0x7D => f32
| 0x7C => f64
これにDecoderとEncoderを実装すると以下のようになります。tokenは指定されたトークンを読む独自コンビネーターです。
impl Decoder for ValType {
fn decode(input: &[u8]) -> IResult<&[u8], ValType> {
alt((
map(parser::token(0x7f), |_| ValType::I32),
map(parser::token(0x7e), |_| ValType::I64),
map(parser::token(0x7d), |_| ValType::F32),
map(parser::token(0x7c), |_| ValType::F64),
))(input)
}
}
impl Encoder for ValType {
fn encode(&self, bytes: &mut Vec<u8>) {
bytes.push(match self {
ValType::I32 => 0x7f,
ValType::I64 => 0x7e,
ValType::F32 => 0x7d,
ValType::F64 => 0x7c,
});
}
}
leb128のデコード、エンコード
wasmではバイナリ容量を節約するためにleb128という可変長の整数エンコード形式を使っています。このエンコード形式は小さな数値であれば1バイトにエンコードでき、また任意の大きな数値を扱うことができます。ただしwasmでは大きさの上限が仕様で決まっています。また符号付きと符号なしがありますが両方使われています。
例えばu32に対する実装は以下のようになっています。
impl Decoder for u32 {
fn decode(input: &[u8]) -> IResult<&[u8], u32> {
parser::io_read(|rb| {
leb128::read::unsigned(rb)
.ok()
.and_then(|x| u32::try_from(x).ok())
})(input)
}
}
impl Encoder for u32 {
fn encode(&self, bytes: &mut Vec<u8>) {
leb128::write::unsigned(bytes, *self as u64).unwrap();
}
}
io_readはio::Readerを受け取ってデコードするライブラリの関数をnomのコンビネーターに変換する独自コンビネーターです(ソース)。ここではleb128というライブラリを使うことで簡単に実装しています。
Sectionについて
バイナリ仕様にはSectionというものが出てきます。SectionはType Section、Import Sectionなどがあり、さっき定義したModule構造体の各フィールドと大体対応しています。ただしfuncsフィールドは関数のシグネチャのみのFunction Sectionと、関数の本体であるCode Sectionに分かれています。これはシグネチャだけを先に定義することでバイト列のストリームを受け取ってデコードしたり、検証したりするためです。また、メタデータとして自由に使えるCustom Sectionというものもあります。
各セクションはセクションID,本体のバイト数,本体のようにエンコードされます。
モジュールのデコード/エンコード
各セクションのデコーダー/エンコーダーや、セクションのコンビネーターをいい感じに定義して最終的に以下のようにデコーダーとエンコーダーをModuleに実装します。
impl Decoder for Module {
fn decode(input: &[u8]) -> IResult<&[u8], Module> {
map(
tuple((
tuple((
parser::token(0x00),
parser::token(0x61),
parser::token(0x73),
parser::token(0x6d),
parser::token(0x01),
parser::token(0x00),
parser::token(0x00),
parser::token(0x00),
)),
tuple((p_costoms, p_section(Byte(1), Vec::<FuncType>::decode))),
tuple((p_costoms, p_section(Byte(2), Vec::<Import>::decode))),
tuple((p_costoms, p_section(Byte(3), Vec::<TypeIdx>::decode))),
tuple((p_costoms, p_section(Byte(4), Vec::<Table>::decode))),
tuple((p_costoms, p_section(Byte(5), Vec::<Mem>::decode))),
tuple((p_costoms, p_section(Byte(6), Vec::<Global>::decode))),
tuple((p_costoms, p_section(Byte(7), Vec::<Export>::decode))),
tuple((p_costoms, p_section(Byte(8), Start::decode))),
tuple((p_costoms, p_section(Byte(9), Vec::<Elem>::decode))),
tuple((p_costoms, p_section(Byte(10), super::values::p_vec(p_code)))),
tuple((p_costoms, p_section(Byte(11), Vec::<Data>::decode))),
p_costoms,
)),
|(
_,
(_, types),
(_, imports),
(_, funcs),
(_, tables),
(_, mems),
(_, globals),
(_, exports),
(_, start),
(_, elem),
(_, code),
(_, data),
_,
)| Module {
types: types.unwrap_or_else(Vec::new),
funcs: funcs
.unwrap_or_else(Vec::new)
.into_iter()
.zip(code.unwrap_or_else(Vec::new))
.map(|(type_, (locals, body))| Func {
type_,
locals,
body,
})
.collect::<Vec<_>>(),
imports: imports.unwrap_or_else(Vec::new),
tables: tables.unwrap_or_else(Vec::new),
mems: mems.unwrap_or_else(Vec::new),
globals: globals.unwrap_or_else(Vec::new),
exports: exports.unwrap_or_else(Vec::new),
start,
elem: elem.unwrap_or_else(Vec::new),
data: data.unwrap_or_else(Vec::new),
},
)(input)
}
}
impl Encoder for Module {
fn encode(&self, bytes: &mut Vec<u8>) {
bytes.push(0x00);
bytes.push(0x61);
bytes.push(0x73);
bytes.push(0x6d);
bytes.push(0x01);
bytes.push(0x00);
bytes.push(0x00);
bytes.push(0x00);
encode_section(Byte(1), &self.types, bytes);
encode_section(Byte(2), &self.imports, bytes);
encode_section(
Byte(3),
self.funcs.iter().map(|x| &x.type_).collect::<Vec<_>>(),
bytes,
);
encode_section(Byte(4), &self.tables, bytes);
encode_section(Byte(5), &self.mems, bytes);
encode_section(Byte(6), &self.globals, bytes);
encode_section(Byte(7), &self.exports, bytes);
encode_section(Byte(8), &self.start, bytes);
encode_section(Byte(9), &self.elem, bytes);
encode_section(
Byte(10),
self.funcs.iter().map(|x| Code(x)).collect::<Vec<_>>(),
bytes,
);
encode_section(Byte(11), &self.data, bytes);
}
}
p_costomsは任意個のカスタムセクションをパースするパーサー(ソース)、p_sectionはセクションIDと本体のデコーダーを受け取ってセクションのパーサーを作るコンビネーター(ソース)です。セクションは省略することができるのでそこらへんの処理もいい感じにしています。encode_sectionはセクションをエンコードする関数で、セクションが空ならセクションごと省略してしまうみたいな処理が中に入っています(ソース)。このような「空であれば省略」といった処理を抽象化するのに空かの判定や、空でない値を取り出す機能を持つZeroという名前のトレイトを定義していて、Option<T>とVec<T>に実装しています。(ソース)
バイナリを読んでみよう
せっかくなのでwasmの簡単なバイナリを読んでみましょう。例にするwatは以下です。
(module
(func $add (param $a i32) (param $b i32) (result i32)
get_local $a
get_local $b
i32.add
)
(export "add" (func $add))
)
2つのi32値を受け取って足した値を返す関数を定義して"add"という名前でexportしているだけの簡単なモジュールです。
wasmには変数名がないのでwatの変数名は数値のインデックス値に変換されたり、関数を宣言すると自動でtypeが宣言されたりします。上記のwatにそのような変換を手動でしてなるべくwasmに近づけたwatが以下です。
(module
(type (func (param i32) (param i32) (result i32)))
(func (type 0)
get_local 0
get_local 1
i32.add
)
(export "add" (func 0))
)
この上記2つのwatは同等で、wasmに変換すると同じwasmを出力します。このwatをwasmに変換して16進数で表現したものが以下です。
0000000 00 61 73 6d 01 00 00 00 01 07 01 60 02 7f 7f 01
0000010 7f 03 02 01 00 07 07 01 03 61 64 64 00 00 0a 09
0000020 01 07 00 20 00 20 01 6a 0b
意味ごとに区切ってインデントと解説を入れたのが以下です。
00 61 73 6d // "\0asm"という文字列。これは固定
01 00 00 00 // wasmのバージョンは1。リトルエンディアン
/* Type Section */
01 // Section IDは1(Type Section)
07 // セクション本体のサイズは7。ここより下は本体
01 // typeの宣言数は1
60 // 関数の型であることを表す。バージョン1では関数の型しかないので固定
02 // 引数の数を表す。引数は2つ
7f // i32型を表す
7f // i32
01 // 返り値の数を表す。バージョン1では0か1
7f // i32
/* Function Section */
03 // Section IDは3
02 // セクション本体のサイズは2
01 // 関数の宣言数
00 // 関数の型は0番目に定義されたtype
/* Export Section */
07 // Section IDは7
07 //セクション本体のサイズは7
01 // exportの数
03 // export名のバイト数
61 64 64 // addという文字列
00 // 関数のexportであることを表す
00 // 0番目に定義された関数をexportする
/* Code Section */
0a // Section IDは10
09 // セクション本体のサイズは9
01 // 関数本体の宣言数(Function Sectionの関数の宣言数と一致する)
07 // 関数本体のサイズ
00 // ローカル変数の宣言数。今回は0
20 00 // get_local 0
20 01 // get_local 1
6a // i32.add
0b // end
proptestを使った自動テスト
proptestを使った自動テストについてです。proptestは以下のように書く事でランダムにデータが与えられ、それに対する性質を書くことで楽にテストを書くことができるツールです。
proptest!(|(x: T)| {
// xが満たすべき性質(満たさなければpanic)
});
今回はASTをランダムで自動生成→ASTをエンコードしてバイナリに変換→バイナリをデコードして元のASTに戻るかという検証に使いました。再利用したいのでidentity_encode_decodeというヘルパー関数を定義します。Arbitraryトレイトはランダムに値を自動生成できる型が実装するトレイトです。
pub fn identity_encode_decode<T: Arbitrary + Encoder + Decoder + PartialEq>() {
proptest!(|(x: T)| {
assert_eq!(Decoder::decode_end(&x.encode_to_vec()), Ok(x));
});
}
今回も例としてvaltypeを使います。
まずテスト対象のValTypeに#[cfg_attr(test, derive(Arbitrary))]をつけてArbitraryトレイトを自動導出します。(cfg_attrによってテスト時のみ自動導出しています)。
次にテスト関数に以下の一行を追記します。
identity_encode_decode::<ValType>();
これだけで「任意のValTypeに対してエンコード→デコードすると元に戻るか」ということを確認することが出来てとても楽です。
ただし問題もあり再帰構造を含むとArbitraryトレイトの自動導出ができません。自分でArbitraryトレイトの実装をするのは大変なので今回は再帰構造を含まないデータ型のみでproptestを使った自動テストを行いました。
Execution
wasmのランタイム構造、実行仕様などについて書かれています。実装にはnum、frunk、generic-array、typenumを使っています。numは数値に関するトレイトなどが定義されているライブラリです。frunkはGenericプログラミングをするためのライブラリでHListなどが定義されています。generic-arrayは長さを型パラメーターで渡せる固定長配列を提供しているライブラリで、typenumはgeneric-arrayが依存している型レベル整数のライブラリです。
Genericプログラミングについて
実装にfrunkというライブラリのGenericとHListを使っています(CoproductやLabelledGenericもありますが今回は使いません)。
HListは再帰的な構造を持つタプルのようなものです。例えば(A, B, C, D)をHListにするとHCons<A, HCons<B, HCons<C, HCons<D, HNill>>>>となります。そしてGenericはReprという関連型を持つトレイトで、HListやCoproductと相互変換できるデータ型を表します。Reprは変換先の型を表します。これの何が嬉しいかというとGenericトレイトさえマクロなどで自動導出してしまえばマクロを使わずに一般的にデータ型に様々なトレイトを実装することができるようになります。例えば、impl PartialEq for HNil、impl<H: PartialEq, T: PartialEq + HList> PartialEq for HCons<H, T>を実装してしまえば全てのフィールドがPartialEqを実装している任意の構造体でPartialEqが使えるようになります。再帰的な構造になっているので()、(A,)、(A, B)、(A, B, C)、(A, B, C, D)…の全てに実装するみたいな事をする必要はありません。とても便利ですね。
ランタイム構造の定義
スタックの値の定義
valはi32/i64/f32/f64のいずれかであると書かれているので以下のように定義します。
pub enum Val {
I32(i32),
I64(i64),
F32(f32),
F64(f64),
}
Valの関連関数に、val_typeというValを受け取ってValTypeを返す関数、unwrap_i32のようなValを受け取ってi32を返す関数(Val::I32(x)でなければパニック)も定義します。
そして次にいくつかのトレイトを定義します。
まずPrimitiveValです。
pub trait PrimitiveVal: Sized {
fn try_from_val(val: Val) -> Option<Self>;
fn wrap_val(self) -> Val;
fn type_() -> ValType;
}
i32型などに実装するトレイトでスタックに入っているプリミティブ型であることを表します。
次にInterpretPrimitiveです。これはPrimitiveValから解釈可能な型に実装するトレイトで、PrimitiveValを実装している型に加えて、bool、u32、u64に実装しています。
pub trait InterpretPrimitive {
type Primitive: PrimitiveVal;
fn to_primitive(self) -> Self::Primitive;
fn reinterpret(primitive: Self::Primitive) -> Self;
}
最後にInterpretValで、Valから解釈可能な型に実装します。InterpretPrimitiveを実装している型に加えてVal自身も実装しています。
pub trait InterpretVal: Sized {
fn try_interpret_val(val: Val) -> Option<Self>;
fn to_val(self) -> Val;
}
各インスタンスとアドレスの定義
メモリやテーブルのインスタンスやアドレスを定義します。FooInstとFooAddrを定義していき、FooAddrはRc<RefCell<FooInst>>のnewtypeになります。外部に公開するのはFooAddrだけで、所有権の競合でパニックにならないように気をつけてインターフェイスを作っていきます。
例えばメモリであれば以下のような構造体になります。
struct MemInst {
max: Option<usize>,
data: Vec<u8>,
}
pub struct MemAddr(Rc<RefCell<MemInst>>);
funcinstの実装は色々工夫しているので詳細に解説します。仕様書を読むとfuncinstはwasmの関数とホスト関数があります。そしてwasmの関数はmoduleinstを持っています。しかしmoduleinstはfuncaddrを持っており循環参照になってしまいます。循環参照になるとRcではメモリリークしてしまうのでfuncinstが持つmoduleinstはWeakで包んでいます。
pub(super) enum FuncInst {
RuntimeFunc {
type_: FuncType,
code: Func,
module: Weak<ModuleInst>,
},
HostFunc {
type_: FuncType,
host_code: Rc<dyn Fn(Vec<Val>) -> Result<Option<Val>, WasmError>>,
},
}
Weakを使うとFuncAddrよりModuleInstが長く生存していることを利用する側が保証する必要がありますが、今回はこれで妥協しました。もう少しいい方法があれば改善したいです。
次にホスト関数のFuncAddrを簡単に作るための工夫です。例えばi32を出力する関数は何もしないと以下のように書く必要があります。
FuncAddr(Rc::new(RefCell::new(FuncInst::HostFunc {
type_: FuncType(vec![ValType::I32], vec![]),
host_code: Rc::new(|params| {
match ¶ms[..] {
[Val::I32(x)] => {
println("{}", x);
Ok(None)
},
_ => panic!()
}
})
})))
これが以下のように書けたら便利ですね。
FuncAddr::alloc_host(|(x,): (i32,)| {
println("{}", x);
Ok(())
})
これにfrunkを使います。
まずValTypeableというトレイトを定義します。これはある型をVec<ValType>に変換する機能を持ったトレイトです。write_valtypeを実装するようになっているのは計算量を抑えるためでStateモナドみたいな物です。
pub trait ValTypeable {
fn write_valtype(types: &mut Vec<ValType>);
fn to_valtype() -> Vec<ValType> {
let mut types = Vec::new();
Self::write_valtype(&mut types);
types
}
}
これを各型に実装していきます。まずInterpretPrimitiveを実装している型であればその型の解釈元のプリミティブ型になります。例えばi32::to_valtype() == vec![ValType::I32]です。
impl<T: InterpretPrimitive> ValTypeable for T {
fn write_valtype(types: &mut Vec<ValType>) {
types.push(T::Primitive::type_());
}
}
次にHNil、つまり()のようなものに実装します。これはvec![]を返します。
impl ValTypeable for HNil {
fn write_valtype(_: &mut Vec<ValType>) {}
}
最後にHCons<H, T>に実装します。これは順番に呼び出すだけです。
impl<H: ValTypeable, T: HList + ValTypeable> ValTypeable for HCons<H, T> {
fn write_valtype(types: &mut Vec<ValType>) {
H::write_valtype(types);
T::write_valtype(types);
}
}
これによって各要素がInterpretPrimitiveを実装しているHList全てで使えるようになりました。タプルはGenericを実装しているので、例えば(i32, i64, bool)::Repr::to_valtype() == vec![ValType::I32, ValType::I64, ValType::I32]です。(T::ReprはHListやCoproductに変換した時の結果型)
同じような感じである型の値をOption<Val>に変換するToOptionValと、Vec<Val>からある型の値に変換するFromVecValを定義します。
ToOptionValは返り値をOption<Val>に変換するのに、FromVecValは引数のVec<Val>から変換するのに使います。
pub trait ToOptionVal {
fn to_option_val(self) -> Option<Val>;
}
pub trait FromVecVal: Sized {
fn from_vec_val_pop_tail(vals: &mut Vec<Val>) -> Self;
fn from_vec_val(mut vals: Vec<Val>) -> Self {
let res = Self::from_vec_val_pop_tail(&mut vals);
assert_eq!(vals.len(), 0);
res
}
}
現在のwasmは複数の返り値をサポートしていないので、ToOptionValはHCons<T, H>ではなくHCons<T, HNil>に実装しています。(これによって()や(x,)を返すことはできるが、(x, y)を返すとコンパイルエラーになる)。from_vec_valは解釈に失敗したらパニックになります。これは検証済みのwasmモジュールでは解釈に失敗することはないからという理由です。
これらを使ってalloc_hostを実装すると以下のようになります。
pub fn alloc_host<P: Generic, R: Generic>(
f: impl Fn(P) -> Result<R, WasmError> + 'static,
) -> FuncAddr
where
P::Repr: ValTypeable + FromVecVal,
R::Repr: ValTypeable + ToOptionVal,
{
let type_ = FuncType(P::Repr::to_valtype(), R::Repr::to_valtype());
FuncAddr(Rc::new(RefCell::new(FuncInst::HostFunc {
type_,
host_code: Rc::new(move |params| {
let p = P::Repr::from_vec_val(params);
let r = into_generic(f(from_generic(p))?);
Ok(r.to_option_val())
}),
})))
}
Genericを実装した引数の型Pと返り値の型Rを受け取って(これらは普通タプル型になる)、Generic::ReprのValTypeable制約によって関数の型を生成し、FromVecValやToOptionVal制約によって引数と返り値を解釈したり変換したりしています。
他の各インスタンスやアドレスの定義は詳しく解説しないので知りたい方はソースを読んでください。
そしてこれらのインスタンスを組み合わせたModuleInstは以下のようになっています。
pub struct ModuleInst {
pub types: Vec<FuncType>,
pub funcs: Vec<FuncAddr>,
pub table: Option<TableAddr>,
pub mem: Option<MemAddr>,
pub globals: Vec<GlobalAddr>,
pub exports: Vec<ExportInst>,
}
スタックの値の定義
仕様書を読むとスタックにはValの他に関数の呼び出しラベルとフレームが含まれることが分かります。ラベルは制御構文に入ると積まれる値です。
まずLabelとFrameを定義します。
pub struct Label {
pub instrs: Vec<Instr>,
pub n: usize,
}
pub struct Frame {
pub module: Weak<ModuleInst>,
pub locals: Vec<Val>,
pub n: usize,
}
nは結果の値の数です。現在のwasmでは0か1になります。Labelのinstrsは継続です。ラベルの継続については前書いたWebAssemblyのbr命令についてという記事を読んでください。簡単に言うとbrした時にラベルの本体を抜けて実行される命令です。
ValとFrameとLabelは任意の順序で積まれる可能性があると書いてありますが、実際はある程度順序が決まっているので最低限計算量を抑えることとなるべく単純な実装にするために今回は以下のようなネストしたスタックを使いました。
pub struct LabelStack {
pub label: Label,
// 後ろから実行
pub instrs: Vec<AdminInstr>,
pub stack: Vec<Val>,
}
pub struct FrameStack {
pub frame: Frame,
// not empty
// stack[0]の継続は空
pub stack: Vec<LabelStack>,
}
pub struct Stack {
// not empty
pub stack: Vec<FrameStack>,
}
ルートのスタックであるStackはFrameを持つFrameStackのスタックを持っています。そしてFrameStackはLabelを持つLabelStackのスタックを持っています。LabelスタックはValのスタックと未処理の命令列であるAdminInstrのスタックを持っています。
AdminInstrというのは仕様書のAdministrative Instructionsに手を加えた物です。Instrにいくつかの命令を追加しています。
pub enum AdminInstr {
Instr(Instr),
Invoke(FuncAddr),
Label(Label, Vec<Instr>),
Br(LabelIdx),
Return,
}
スタックを簡単に扱う
スタックから簡単に値をpopしたりpushしたりするためのトレイトと便利関数を見てみましょう。
まずStackValuesトレイトです。
pub trait StackValues: Sized {
fn pop_stack(stack: &mut Vec<Val>) -> Option<Self>;
fn push_stack(self, stack: &mut Vec<Val>);
}
これはスタックにpushとpopできる値を表します。これを各要素がInterpretValを実装しているHListに実装することで一般的に使えるようにしています。
impl<T: InterpretVal> StackValues for T {
fn pop_stack(stack: &mut Vec<Val>) -> Option<Self> {
let val = stack.pop()?;
T::try_interpret_val(val)
}
fn push_stack(self, stack: &mut Vec<Val>) {
stack.push(self.to_val());
}
}
impl StackValues for HNil {
fn pop_stack(_: &mut Vec<Val>) -> Option<Self> {
Some(HNil)
}
fn push_stack(self, _: &mut Vec<Val>) {}
}
impl<H: StackValues, T: HList + StackValues> StackValues for HCons<H, T> {
fn pop_stack(stack: &mut Vec<Val>) -> Option<Self> {
let tail = T::pop_stack(stack)?;
let head = H::pop_stack(stack)?;
Some(tail.prepend(head))
}
fn push_stack(self, stack: &mut Vec<Val>) {
self.head.push_stack(stack);
self.tail.push_stack(stack);
}
}
HCons<H, T>のpop_stackはtail→headの順でpopしていることに注意してください。これは(a, b)をスタックにpushするとa→bの順でスタックに積まれ、スタックの上にbが来るのでpopはbからになることから分かると思います。
次にLabelStackの関連関数にStackValuesトレイトを活用した便利関数を定義していきます。
まずpop_valuesとpush_valuesです。これは型引数に(i32, i32)などのGenericを実装していて、Generic::ReprがStackValuesを実装している型の値を受け取ってpushしたりpopしたりする関数です。
fn pop_values<T>(&mut self) -> T
where
T: Generic,
T::Repr: StackValues,
{
from_generic(T::Repr::pop_stack(&mut self.stack).unwrap())
}
fn push_values<T>(&mut self, x: T)
where
T: Generic,
T::Repr: StackValues,
{
into_generic(x).push_stack(&mut self.stack)
}
次にFnOnce((i32,i32)) -> Result<(i64,), WasmError>などのコールバックを受け取ってスタックから値をpopして関数を呼び出し結果をpushするrunと、runの結果がResultでない(=失敗しない)版のrun_ok関数です。
fn run<I, O>(&mut self, f: impl FnOnce(I) -> Result<O, WasmError>) -> Result<(), WasmError>
where
I: Generic,
I::Repr: StackValues,
O: Generic,
O::Repr: StackValues,
{
let input = self.pop_values::<I>();
let output = f(input)?;
self.push_values(output);
Ok(())
}
fn run_ok<I, O>(&mut self, f: impl FnOnce(I) -> O) -> ()
where
I: Generic,
I::Repr: StackValues,
O: Generic,
O::Repr: StackValues,
{
self.run(|i| Ok(f(i))).unwrap();
}
最後にこれらをラップした関数を定義していきます。数値命令はconst、unop、binop、testop、reop、cvtopというグループに分けることができるのでこれらに特化した関数です。以下のようになります。
fn run_const<T: InterpretVal>(&mut self, f: impl FnOnce() -> T) {
self.run_ok(|(): ()| -> (T,) { (f(),) })
}
fn run_unop<T: InterpretVal>(
&mut self,
f: impl FnOnce(T) -> Result<T, WasmError>,
) -> Result<(), WasmError> {
self.run(|(x,): (T,)| -> Result<(T,), _> { Ok((f(x)?,)) })
}
fn run_binop<T: InterpretVal>(
&mut self,
f: impl FnOnce(T, T) -> Result<T, WasmError>,
) -> Result<(), WasmError> {
self.run(|(a, b): (T, T)| -> Result<(T,), _> { Ok((f(a, b)?,)) })
}
fn run_testop<T: InterpretVal>(&mut self, f: impl FnOnce(T) -> bool) {
self.run_ok(|(x,): (T,)| -> (bool,) { (f(x),) })
}
fn run_reop<T: InterpretVal>(&mut self, f: impl FnOnce(T, T) -> bool) {
self.run_ok(|(x, y): (T, T)| -> (bool,) { (f(x, y),) })
}
fn run_cvtop<T: InterpretVal, R: InterpretVal>(
&mut self,
f: impl FnOnce(T) -> Result<R, WasmError>,
) -> Result<(), WasmError> {
self.run(|(x,): (T,)| -> Result<(R,), _> { Ok((f(x)?,)) })
}
失敗するかもしれない命令グループと必ず成功する命令グループがあるのでrunとrun_okを使い分けています。
バイト列に変換できる値
バイト列との相互変換はメモリ命令や再解釈命令でよく出てくるのでトレイトを定義します。
pub trait Byteable: Sized {
type N: ArrayLength<u8>;
fn to_bytes(self) -> GenericArray<u8, Self::N>;
fn from_bytes(bytes: &GenericArray<u8, Self::N>) -> Self;
}
Nは型レベル整数で、GenericArrayは固定長配列です。これを{i/u}{8/16/32/64}と、f32、f64に実装しています。
命令の実行
Stack、LabelStack、FrameStackはそれぞれ命令を1ステップ実行するstep関数を持っています。
// LabelStack
fn step(&mut self, frame: &mut Frame) -> Result<Option<FrameLevelInstr>, WasmError> {
Ok(match self.instrs.pop() {
Some(instr) => match instr {
AdminInstr::Instr(instr) => {
match instr {
// 各命令の処理(800行程度)
}
None
}
AdminInstr::Invoke(x) => Some(FrameLevelInstr::Invoke(x)),
AdminInstr::Label(l, is) => Some(FrameLevelInstr::Label(l, is)),
AdminInstr::Br(l) => Some(FrameLevelInstr::Br(l)),
AdminInstr::Return => Some(FrameLevelInstr::Return),
},
None => Some(FrameLevelInstr::LabelEnd),
})
}
// FrameStack
pub fn step(&mut self) -> Result<Option<ModuleLevelInstr>, WasmError> {
let cur_lavel = self.stack.last_mut().unwrap();
Ok(if let Some(instr) = cur_lavel.step(&mut self.frame)? {
match instr {
// 各命令の処理(60行程度)
}
} else {
None
})
}
// Stack
pub fn step(&mut self) -> Result<(), WasmError> {
let cur_frame = self.stack.last_mut().unwrap();
if let Some(instr) = cur_frame.step()? {
let cur_label = cur_frame.stack.last_mut().unwrap();
match instr {
// 各命令の処理(70行程度)
}
}
Ok(())
}
ソースを見れば分かるように、Stackのstepを呼び出すとFrameStackのstepが呼び出され、FrameStackのstepを呼び出すとLabelStackのstepが呼び出されます。そしてほとんどの命令はLabelStackで処理されます。しかしLabelStackでは処理出来ない命令があります。例えば制御構造に入る命令や、関数を呼び出す命令です。
制御構造に入るにはLabelStackのスタックに値を積む必要がありますが、Labelを一つしか持たないLabelStackでは処理出来ません。関数呼び出しはFrameStackのスタックに値を積む必要がありますがこれもできません。このような処理に対応するためにLabelStackのstepはOption<FrameLevelInstr>を、FrameStackのstepはOption<ModuleLevelInstr>を返すようになっています(ただしtrapにも対応する必要があるのでResultで包んでいます)。
FrameLevelInstrはLabelStackでは処理出来ない命令、ModuleLevelInstrはFrameStackでは処理出来ない命令で以下のようになっています。
pub enum FrameLevelInstr {
Label(Label, Vec<Instr>),
Br(LabelIdx),
LabelEnd,
Invoke(FuncAddr),
Return,
}
pub enum ModuleLevelInstr {
Invoke(FuncAddr),
Return,
}
そして、これらをstepの返り値で受け取った時は親が処理するようになっています(もし親も処理できなければ更に親に返します)。
これが命令の実行方法です。
ここから命令の処理を実際にいくつか解説していきます。しかし全て解説するのは無理なので詳しく知りたい方はソースを読んでください。
まずは単純なi32.const命令です。
// LabelStack::step
Instr::I32Const(x) => {
self.run_const(|| -> i32 { x });
}
これはi32.const xのxの値が結果になります。
次にi32.addです。
// LabelStack::step
Instr::I32Add => {
self.run_binop(|x: i32, y: i32| -> Result<i32, _> {
Ok(x.overflowing_add(y).0)
})?;
}
+ではなくoverflowing_addを使っているのはオーバーフロー時の処理も決められており、その処理とoverflowing_addが一致していたからです。
ローカル変数関連の命令を見てみましょう。例えばget_localです。
// LabelStack::step
Instr::LocalGet(idx) => {
self.run_ok(|(): ()| -> (Val,) { (frame.locals[idx.to_idx()],) });
}
引数で受け取った現在のFrameのローカル変数の値を取得しています。to_idxはインデックスを表すnewtypeからusizeに変換する関数です。
グローバル変数に関する命令は以下のようになっています。
// LabelStack::step
Instr::GlobalSet(idx) => {
let instance = frame.module.upgrade().unwrap();
self.run_ok(|(x,): (Val,)| -> () {
instance.globals[idx.to_idx()].set(x).unwrap();
()
});
}
これは現在のフレームから現在のモジュールインスタンスを取得して(モジュールインスタンスはWeakで持っているのでupgradeしている)、グローバル変数を書き換えています。
次にメモリ命令としてf32.storeを見てみましょう。
// LabelStack::step
Instr::F32Store(m) => {
let instance = frame.module.upgrade().unwrap();
self.run(|(ptr, x): (i32, f32)| -> Result<(), _> {
instance.mem.as_ref().unwrap().write::<f32>(&m, ptr, x)?;
Ok(())
})?;
}
MemAddrにwriteというByteableを実装している型をメモリに書き込めるwrite関数を定義しているのでそれを使っています。
制御命令も見てみましょう。例えばifです。仕様は大体以下のようになっています。
(i32.const c) if [t^n] instr1 else instr2 end → label_n {} instr1 end (if c ≠ 0)
(i32.const c) if [t^n] instr1 else instr2 end → label_n {} instr2 end (if c = 0)
つまり、スタックの一番上の値が0でなければthen節を、0ならelse節を実行するという意味です。この時labelが作られますが継続は空になります。t^nやlabel_nのnは結果の値の数で現在のwasmでは0か1になります。これを実装するとこうなります。
// LabelStack::step
Instr::If(rt, is1, is2) => {
let (x,) = self.pop_values::<(bool,)>();
self.instrs.push(AdminInstr::Label(
Label {
instrs: vec![],
n: rt.0.iter().count(),
},
if x { is1 } else { is2 },
));
}
boolはStackValuesを実装していて0でないかでi32を変換してくれるのでここでは0でないかを判定する必要はありません。rtはOption<ValType>のnewtype(ResultType)です。これが評価されると命令スタックのIfがLabel命令に変わります(self.instrs.pushしているので命令が積まれる)。
ではこのLabel命令の評価を見てみましょう。まずLabelStack::stepの評価です。
// LabelStack::step
AdminInstr::Label(l, is) => Some(FrameLevelInstr::Label(l, is)),
ここでは何もせずにただ返り値として返しています。これはLabelを一つしか持たないLabelStackではこれ以上できることがないからです。そこでこれを受け取った親のFrameStackがどう処理するかを見てみましょう。
// FrameStack::step
FrameLevelInstr::Label(label, instrs) => {
self.stack.push(LabelStack {
label,
instrs: instrs.into_iter().map(AdminInstr::Instr).rev().collect(),
stack: vec![],
});
None
}
受け取ったラベルと次に実行するべき命令をLabelStackのスタックにpushしています。LabelStackのinstrsはAdminInstrのスタックですが、FrameLevelInstr::LabelのinstrsはInstrの命令列なのでAdminInstr::Instrで包んで反転するという処理が入っています。Label命令はFrameStackで完結するので親であるStackにはNoneを返しています。
StackのReturn命令の処理も見てみましょう。仕様は以下のようになっています。
frame_n{F} B^k[val^n return] end → val^n
nは返り値の数で、B^k[val^n return]で最後のlabelを表しています。その最後のlabelの最後のスタックの値val^nを取り出せばいいわけです。ただネストしたスタックを採用しているので実装はかなり変わります。
// Stack::next
ModuleLevelInstr::Return => {
let ret = cur_label.stack.pop();
if self.stack.pop().unwrap().frame.n != 0 {
self.stack
.last_mut()
.unwrap()
.stack
.last_mut()
.unwrap()
.stack
.push(ret.unwrap());
}
}
現在のラベルのスタックの一番上の値をpopしてretに一時的に格納しておきます(返り値が複数になることはないので0個または1個であるOption<Val>になっています)。
そして現在のFrameStackのスタックの一番上の値をpopしてそのframeの結果の数nを調べてそれが0でなければ、返り先のframeの最後のlabelのスタックにさっき格納しておいたretをpushしています。
関数の呼び出し
wasm関数を外部から呼び出す時の処理は以下のようになります。これはFuncAddrの関連関数です。
仕様書のInvocationに仕様があります。
pub fn call(&self, params: Vec<Val>) -> Result<Option<Val>, WasmError> {
let mut stack = Stack {
stack: vec![FrameStack {
frame: Frame {
locals: Vec::new(),
module: Weak::new(),
n: 0,
},
stack: vec![LabelStack {
label: Label {
instrs: vec![],
n: 0,
},
instrs: vec![AdminInstr::Invoke(self.clone())],
stack: params,
}],
}],
};
loop {
stack.step()?;
if stack.stack.len() == 1
&& stack.stack.first().unwrap().stack.len() == 1
&& stack
.stack
.first()
.unwrap()
.stack
.first()
.unwrap()
.instrs
.is_empty()
{
break;
}
}
Ok(stack.stack.pop().unwrap().stack.pop().unwrap().stack.pop())
}
これは引数でパラメーターparamsを受け取って、ダミーラベルを持つダミーフレームを作っています。ダミーラベルには実行対象のFuncAddrが設定されたInvoke命令と、paramsをスタックに載せています。
そして、ダミーフレームが値に評価されるまでstepを呼び続けて値に評価されたら結果を返しています。
インスタンス化
実際に処理を実行するにはModuleとimportする値を受け取って、ModuleInstを作らなければいけません。その処理の解説です。
まずimportする値は以下のようになっています。
pub type ExternalModule = HashMap<String, ExternalVal>;
pub type ImportObjects = HashMap<String, ExternalModule>;
#[derive(Debug, Clone)]
pub enum ExternalVal {
Func(FuncAddr),
Table(TableAddr),
Mem(MemAddr),
Global(GlobalAddr),
}
ExternalValはimportやexportできる値で、それのMapがExternalModule、さらにそれのMapがImportObjectsです。
ModuleInst::newが実際の処理です。
この関数のシグネチャは以下のようになっています。結果がResultであることから分かるようにインスタンス化は失敗することがあります。例えばimportする値が存在しなかったり、start関数でtrapした場合などです。
pub fn new(module: &Module, imports_objects: ImportObjects) -> Result<Rc<ModuleInst>, WasmError>;
まずtypes以外は空のモジュールを作ります。
let mut result = ModuleInst {
types: module.types.clone(),
funcs: Vec::new(),
table: None,
mem: None,
globals: Vec::new(),
exports: Vec::new(),
};
次にモジュールのimport宣言と、importされた値を使って実際にimportしていきます。この時その名前を持つ値が存在するか、値の種類が正しいかだけでなく値の型チェックをする必要があります。
for import in &module.imports {
let val = imports_objects
.get(&import.module.0)
.and_then(|module| module.get(&import.name.0))
.cloned()
.ok_or_else(|| WasmError::LinkError)?;
match &import.desc {
ImportDesc::Func(idx) => {
result.funcs.push(
val.as_func()
.filter(|func| func.type_().is_match(result.types.get_idx(*idx)))
.ok_or_else(|| WasmError::LinkError)?,
);
}
// 省略
}
}
各インスタンスはtype_関数を持っており、各Typeはis_match関数を持っているのでこれでチェックすることが出来ます。
a.is_match(b)はaがbのサブタイプかを判定しています。インスタンスの型を調べる仕様は仕様書のExternal Typingを、型のサブタイプはImport Matchingに書いてあります。
次にモジュールの各値をインスタンス化していきます。ただ、funcsのインスタンス化だけ特殊で、一旦ダミーの値を置いています。
for _ in &module.funcs {
result.funcs.push(FuncAddr::alloc_dummy());
}
if let Some(table) = module.tables.iter().next() {
let _ = result.table.replace(TableAddr::alloc(&table.type_));
}
// 省略
これはModuleInstとFuncInstは循環参照しており、この段階では渡すことが出来ないからです。ダミーの値を置いているのはこれをしないと以下のexportする値を作れないといった理由があります。
for export in &module.exports {
result.exports.push(ExportInst {
name: export.name.0.clone(),
value: match export.desc {
ExportDesc::Func(idx) => ExternalVal::Func(result.funcs.get_idx(idx).clone()),
ExportDesc::Global(idx) => {
ExternalVal::Global(result.globals.get_idx(idx).clone())
}
ExportDesc::Mem(_idx) => ExternalVal::Mem(result.mem.as_ref().unwrap().clone()),
ExportDesc::Table(_idx) => {
ExternalVal::Table(result.table.as_ref().unwrap().clone())
}
},
});
}
ダミーの値はインスタンス化の最後のほうで実際の値に置き換えられます。
まず、ModuleInstをRcで包んで、関数をインスタンス化しています。
そしてstart関数が存在すればそれが実行され結果が返されます。
let result = Rc::new(result);
for (i, func) in module.funcs.iter().enumerate() {
let idx = i + module
.imports
.iter()
.map(|x| {
if let ImportDesc::Func(_) = x.desc {
1
} else {
0
}
})
.sum::<usize>();
result.funcs[idx].replace_dummy(func.clone(), Rc::downgrade(&result));
}
if let Some(start) = &module.start {
result.funcs.get_idx(start.func).call(vec![])?;
}
Ok(result)
その他のインスタンス化処理や、dataやelemによるmemやtableの初期化は特に特殊な事をしていないので解説は省略します。
公式のテストケース
公式がwast形式のテストケースを用意してくれています。
wastというのはwatの拡張形式で「この関数をこの順番で呼び出せばこの結果が返ってくる」といったassertや、複数モジュールを定義してそのモジュール間の連携とテストを書いたりすることができます。
wastはwabtのwast2jsonというコマンドで複数のwasmと、テストケースのjsonに変換して使うことが出来ます。
masterのwabtはwast2jsonの出力するwasmファイルが壊れるバグがあるのでタグがついている一番最新のバージョンを使いましょう。
そしてwastのテストケースも#1104で、assert_return_canonical_nanとassert_return_arithmetic_nanが消されてnan:canonicalとnan:canonicalというリテラルのようなものが入ったのですが、まだwabtが対応しておらず、wasm2jsonを実行するとエラーになるのでこのPRがマージされる前のものを使う必要があります(wabt以外の変換ツールを使えばいけるはずですが試してません)
テストの実装はここです。
https://github.com/kgtkr/wasm-rs/blob/adc-2019-12-22/tests/spec.rs
assert_malformed(モジュールのパースに失敗)はテキストフォーマットの実装ができていないので、assert_invalid(検証に失敗)は検証フェーズの実装ができてないので、assert_exhaustion(リソースを使い果たした)はスタックオーバーフローなどの実装ができていないので、assert_return_canonical_nan(結果がcanonical_nanである)とassert_return_arithmetic_nan(結果がarithmetic_nanである)はさっきのPRで消されてしまうのでテストをスキップしていますがそれ以外は全て通りました。
出力したjsonをいい感じにパースして書いてあるとおりに実行すればテストできるのでかなり楽です。気をつける事があるとすればjsonのvalueはi32/i64/f32/f64に関係なく全て符号なし整数の文字列なのでそれをパースして、リトルエンディアンでバイト列に変換して、バイト列から対象の型に変換する必要があるくらいです。
md5を計算するRustコードを自作インタプリタ上で動かす
md5を計算するRustコードをwasmにコンパイルして自作インタプリタ上で動かしてみました。
wasmにコンパイルするRustコードは以下です。
use std::ffi::{c_void, CString};
use std::mem::forget;
#[no_mangle]
pub extern "C" fn md5(input: *mut i8) -> *const i8 {
let s = CString::new(format!(
"{:x}",
md5::compute(unsafe { CString::from_raw(input) }.into_bytes())
))
.unwrap();
let p = s.as_ptr();
forget(s);
p
}
#[no_mangle]
pub fn alloc(size: usize) -> *mut c_void {
let mut buf = Vec::with_capacity(size);
let p = buf.as_mut_ptr();
forget(buf);
p
}
fn main() {}
Rustからwasmに公開する関数は整数やポインタ型でしかやり取りできないので、これを使う側はallocで文字列をCStringに変換したバイト列の長さ分メモリを確保→確保したメモリをバイト列で埋める→md5に確保したメモリのポインタを渡す→結果がポインタで返ってくるのでポインタをCStringに変換するという処理を行う必要があります。
これをする処理が以下です。md5-bin.wasmが上記のコンパイル結果です。
use maplit::hashmap;
use std::ffi::CString;
use wasm_rs::binary::decode_module;
use wasm_rs::exec::{ModuleInst, Val};
fn main() {
let module = decode_module(
&std::fs::read("md5-bin/target/wasm32-unknown-unknown/release/md5-bin.wasm").unwrap(),
)
.unwrap();
let instance = ModuleInst::new(&module, hashmap! {}).unwrap();
let input_bytes = CString::new("abc").unwrap().into_bytes();
let input_ptr = instance
.export("alloc")
.unwrap_func()
.call(vec![Val::I32(input_bytes.len() as i32)])
.unwrap()
.unwrap()
.unwrap_i32();
instance
.export("memory")
.unwrap_mem()
.write_buffer(input_ptr, &input_bytes[..]);
let output_ptr = instance
.export("md5")
.unwrap_func()
.call(vec![Val::I32(input_ptr as i32)])
.unwrap()
.unwrap()
.unwrap_i32() as usize;
let mem = instance.export("memory").unwrap_mem();
println!(
"{}",
CString::new(
mem.into_iter()
.skip(output_ptr)
.take_while(|x| *x != 0)
.collect::<Vec<_>>(),
)
.unwrap()
.into_string()
.unwrap()
);
}
これを実行すると以下のように表示され、"abc"のmd5を計算できていることが分かります。
900150983cd24fb0d6963f7d28e17f72
自作言語を自作インタプリタで動かす
一年前にHaskellでwasmにコンパイルする自作言語を作ったので(WebAssemblyにコンパイルする言語を実装する
)、それを実行してみたところ上手く動かすことができました。
以下は配列を10個用意して、インデックスの値で初期化、各要素をインクリメント、二倍、デクリメントして出力する自作言語のコードです。
extern fun "memory" "malloc" malloc(x: i32): i32
extern fun "io" "print" print(x: i32)
fun main() = {
let n = 10;
let arr = [i32; n];
for(let i = 0; i < n; i = i + 1) {
arr[i] = i;
};
map(inc, n, arr);
map(double, n, arr);
map(dec, n, arr);
forEach(print, n, arr);
}
fun double(x: i32): i32 = x * 2
fun inc(x: i32): i32 = x + 1
fun dec(x: i32): i32 = x - 1
fun map(f: (i32) => i32, n:i32, arr: [i32]) = {
for(let i = 0; i< n; i = i + 1) {
arr[i] = f(arr[i]);
};
}
fun forEach(f: (i32) =>, n: i32, arr: [i32]) = {
for(let i = 0; i < n; i = i + 1) {
f(arr[i]);
};
}
cl8w-ex.wasmは自作言語のコンパイル結果、memory.wasmは自作言語の実行に必要なランタイムとなっています。
モジュールのインスタンス化には各モジュールがimportしている値を用意し渡す必要があります。
use wasm_rs::binary::decode_module;
use wasm_rs::exec::{ModuleInst, ExternalVal, FuncAddr, MemAddr};
use maplit::hashmap;
fn main(){
let memory = ExternalVal::Mem(MemAddr::new(10, None));
let print = ExternalVal::Func(FuncAddr::alloc_host(|(x,): (i32,)| {
println!("{}", x);
Ok(())
}));
let memory_module =
decode_module(&std::fs::read("cl8w-wasm/memory.wasm").unwrap()).unwrap();
let memory_instance = ModuleInst::new(
&memory_module,
hashmap! {
"resource".to_string() => hashmap!{
"memory".to_string() => memory.clone()
}
},
)
.unwrap();
let main_module =
decode_module(&std::fs::read("cl8w-wasm/cl8w-ex.wasm").unwrap()).unwrap();
let main_instance = ModuleInst::new(
&main_module,
hashmap! {
"resource".to_string() => hashmap!{
"memory".to_string() => memory.clone()
},
"memory".to_string() => memory_instance.exports(),
"io".to_string() => hashmap!{
"print".to_string() => print.clone()
}
},
)
.unwrap();
main_instance
.export("main")
.unwrap_func()
.call(vec![])
.unwrap();
}
これを実行するとこのように表示されます。
1
3
5
7
9
11
13
15
17
19
自作インタプリタ上で自作インタプリタを動かす
Rustはwasmにコンパイルすることができるので自作インタプリタ上で自作言語を動かすコードをwasmにコンパイルし、それを自作インタプリタで動かしてみました。つまり自作言語(wasm) on 自作インタプリタ(wasm) on 自作インタプリタ(ホストマシン)です。
自作言語のコードはさっきと同じです。
wasmにコンパイルするRustコードは以下です。さっきとほぼ同じですが、printをexternしていたり、run関数をexternしているところが違います。
use maplit::hashmap;
use wasm_rs::binary::decode_module;
use wasm_rs::exec::{ExternalVal, FuncAddr, MemAddr, ModuleInst};
fn main() {}
extern "C" {
fn print(x: i32) -> ();
}
#[no_mangle]
pub extern "C" fn run() {
let memory = ExternalVal::Mem(MemAddr::new(10, None));
let print = ExternalVal::Func(FuncAddr::alloc_host(|(x,): (i32,)| {
unsafe {
print(x);
}
Ok(())
}));
let memory_module = decode_module(include_bytes!("../../cl8w-wasm/memory.wasm")).unwrap();
let memory_instance = ModuleInst::new(
&memory_module,
hashmap!(
"resource".to_string() => hashmap!(
"memory".to_string() => memory.clone()
)
),
)
.unwrap();
let main_module = decode_module(include_bytes!("../../cl8w-wasm/cl8w-ex.wasm")).unwrap();
let main_instance = ModuleInst::new(
&main_module,
hashmap!(
"resource".to_string() => hashmap!(
"memory".to_string() => memory.clone()
),
"memory".to_string() => memory_instance.exports(),
"io".to_string() => hashmap!(
"print".to_string() => print.clone()
)
),
)
.unwrap();
main_instance
.export("main")
.unwrap_func()
.call(vec![])
.unwrap();
}
上記Rustコードをwasmにコンパイルして動かすコードは以下のようになります。cl8w-on-wasm-bin.wasmは上記Rustコードのコンパイル結果です。
use maplit::hashmap;
use wasm_rs::binary::decode_module;
use wasm_rs::exec::{ExternalVal, FuncAddr, ModuleInst};
fn main() {
let print = ExternalVal::Func(FuncAddr::alloc_host(|(x,): (i32,)| {
println!("{}", x);
Ok(())
}));
let module = decode_module(
&std::fs::read(
"cl8w-on-wasm-bin/target/wasm32-unknown-unknown/release/cl8w-on-wasm-bin.wasm",
)
.unwrap(),
)
.unwrap();
let instance = ModuleInst::new(
&module,
hashmap! {
"env".to_string() => hashmap!{
"print".to_string() => print
}
},
)
.unwrap();
instance.export("run").unwrap_func().call(vec![]).unwrap();
}
これを実行すると以下のようになります。
手元環境(MBP2018 2.5GHz i7)でtimeコマンドを使って実行時間の計測もしてみました。どちらのRustコードもreleaseビルドです。
1
3
5
7
9
11
13
15
17
19
real 1m48.488s
user 1m41.136s
sys 0m1.177s
遅すぎますね。遅いwasmインタプリタの上で遅いwasmインタプリタを動かしてその上で遅い自作言語(どちらかというと自作メモリアロケーターが遅い)を動かしているのでめちゃくちゃ遅いのは当然です。パフォーマンス無視で実装したとはいえ流石に遅すぎるので改善したいです。
ちなみにcl8w-on-wasm-bin.wasmをnode.js上で実行すると実行時間は以下のようになりました。かなり差ありますね。
real 0m0.376s
user 0m0.869s
sys 0m0.080s
これからやりたいこと
まずは検証フェーズと、watのパーサーを作って全ての公式テストケースを通るようにしたいです。
ModuleInstにWeakを使いまくってるのも綺麗じゃないのでそれも改善したいと思っています。