今回のスコープ
前回の予告通り、以下を実装します。
- breakとcontinue（JavaScriptはラベル指定breakができるがサポートしない）
- breakを踏まえたうえでのswitch文
またfor文で1つ目／2つ目／3つ目の式を省略した場合のテストをしていなかったのですが、特に2つ目は本文中でbreakしないと無限ループしてしまうので今ステップでテストすることにしました（なおステップ7段階の実装はもちろん省略に対応できていませんでした）
ステップ8段階のコードは以下にあります（push後に開発記書いててバグってる箇所に気づきました・・・）
https://github.com/junjis0203/joke/tree/step0008-fix1
break/continueのための仕組み
前回、「if/while/forはジャンプする量を事前に計算できるがbreakはできない1、ほかの仕組みを作る必要がある」と書きましたが、その仕組みを実装しました。仕組みは以下のようになります。
- breakやcontinueを行える制御構造の開始時に「breakされたらここに飛ぶ、continueされたらここに飛ぶ」という情報をスタックに積む。このスタックをbreakableStackと呼ぶ2
- breakやcontinueが起きたらbreakableStackから情報を取り出して指定された位置にジャンプする
- breakやcontinueされることなく本文（forなどのStatement部分）を終えたらbreakableStackを一つ下ろす
forはかなりややこしいのでwhileで説明します。ステップ7と比べてPUSH_BREAKABLEとPOP_BREAKABLEが追加されています。
case N.WHILE:
{
const exprInsns = [];
assembleNode(node.expr, exprInsns);
const stmtInsns = [];
assembleNode(node.stmt, stmtInsns);
const breakOffset = exprInsns.length + stmtInsns.length + 5; // to after POP_BREAKABLE
const continueOffset = 0;
makeInstruction(I.PUSH_BREAKABLE, {breakOffset, continueOffset});
embedInsns(exprInsns);
makeInstruction(I.UNI_OP, {operator: '!'});
makeInstruction(I.JUMP_IF, {offset: stmtInsns.length + 2});
embedInsns(stmtInsns);
makeInstruction(I.JUMP, {offset: -(exprInsns.length + stmtInsns.length + 2)});
makeInstruction(I.POP_BREAKABLE);
}
break;
PUSH_BREAKABLEの引数であるbreakOffsetとcontinueOffsetは名前の通り「breakされたときの飛び先」「continueされたときの飛び先」です。またoffsetという名前が示す通りこの時点では「PUSH_BREAKABLE命令がある位置からの相対位置」です。
VMではPUSH_BREAKABLEを見つけると絶対位置を計算したうえでbreakableStackにpushします3。continueOffsetで条件分岐しているのは「breakはできるけどcontinueはできない」ものがあるからですが詳しくはswitch文のところで説明します。
case I.PUSH_BREAKABLE:
{
// compute absolute address
let ptrBreak = context.ptr + insn.breakOffset;
let ptrContinue;
if (insn.continueOffset != undefined) {
ptrContinue = context.ptr + insn.continueOffset;
}
context.breakableStack.push({ptrBreak, ptrContinue});
}
break;
ともかくこれでbreakされたときにどこに飛べばいいのかわかるようになったので後はbreakableStackから取り出して絶対ジャンプをするだけです。
case I.BREAK:
{
const breakInfo = context.breakableStack.pop();
return {type: 'JUMP_ABS', ptr: breakInfo.ptrBreak};
}
for文の修正
for文は1つ目／2つ目／3つ目の式を省略することができますが、ステップ7段階では考慮していなかったので対応しました（結果、ステップ7に比べてアセンブル処理が長くなりました）。ステップ7に追試として入れようかなと思いましたが2つ目の式省略はbreakがないと無限ループになってしまうのでステップ8としてテストすることにしました。
まあその部分は淡々と長いだけなので今回の主題であるbreak/continue時の飛び先の計算の話をします。
let breakOffset = stmtInsns.length + 3; // to POP_SCOPE
let continueOffset = stmtInsns.length + 1; // to expr3
if (node.expr2) {
breakOffset += expr2Insns.length + 2;
continueOffset += expr2Insns.length + 2;
}
if (node.expr3) {
breakOffset += expr3Insns.length + 1;
}
makeInstruction(I.PUSH_BREAKABLE, {breakOffset, continueOffset});
前回の復習として、for文は以下のような命令列にアセンブルされます。breakされた場合は「6.の無条件ジャンプ」の一つ先へ、conitinueされた場合は「5.の更新処理命令列」に飛ぶ必要があります。それを計算しているのが上記のコードです。4
- forの1つ目（初期化）の命令列
- forの2つ目（条件）の命令列
- 条件を否定し、否定したものがtrueならループ末尾へ
- ループ本体の命令列
- forの3つ目（更新処理）の命令列
- forの2つ目の先頭への無条件ジャンプ
switch文の実装
以上でbreakが実装できたのでようやくswitch文です。
まずはいつも通り仕様を確認。
CaseClause :
case Expression : StatementList
なんとJavaScriptのcaseは「任意の式」が書けるようです！つまり以下のように書くこともできます！
switch (a) {
case b + c:
console.log('aはbとcを足したものに等しい');
break;
}
まあ「できる」と「意味がある」は別問題ですが。
JavaScriptではswitchに書かれた「式」とcaseに書かれているものは===で比較されるので書けてもおかしくはないですね。
アセンブル処理
ともかく構文解析を行い、アセンブル処理です。今までで最長。4
まず各部分のアセンブルを行います。
- switchの式をアセンブル
- 各caseについて式部分（Expression）を別命令配列にアセンブルしておく
- 同様に本文部分（StatementList）を別命令配列にアセンブルしておく
次に各部分の命令数を使って「条件にマッチした場合にどれだけジャンプすればいいか」のオフセットを計算します。
言葉だけでは絶対伝わらないので図解すると以下のようになります。ちなみに「case 1の本文」とかからジャンプがないのは間違いではありません。breakは「本文内のこと」なのでswitch自体に「本文実行したから末尾にジャンプ」という機能はありません。5
// calculate jump offset(any cool implementation?)
for (let i = 0; i < labelInfoList.length; i++) {
let insnsCount = 0;
if (!labelInfoList[i].default) {
for (let j = i + 1; j < labelInfoList.length; j++) {
if (!labelInfoList[j].default) {
insnsCount += labelInfoList[j].exprInsns.length + 3;
}
}
insnsCount += 1;
}
for (let j = 0; j < i; j++) {
insnsCount += labelInfoList[j].stmtsInsns.length;
if (!labelInfoList[j].default) {
insnsCount += 1;
}
}
labelInfoList[i].stmtsOffset = insnsCount + 1;
}
最後に「受験分岐を行う命令列」「どの条件にもマッチしなかった場合のデフォルト（または末尾）へのジャンプ」「条件分岐の飛び先の命令列」を埋め込んでいきます。最終的に先に図解したような命令列になります。
const labelInfoListWithoutDefault = labelInfoList.filter(c => !c.default);
const labelInfoForDefault = labelInfoList.find(c => c.default);
makeInstruction(I.PUSH_SCOPE);
makeInstruction(I.PUSH_BREAKABLE, {breakOffset});
for (const labelInfo of labelInfoListWithoutDefault) {
// dup switch.expr result for remain case
makeInstruction(I.DUP);
embedInsns(labelInfo.exprInsns);
makeInstruction(I.BIN_OP, {operator: '==='});
makeInstruction(I.JUMP_IF, {offset: labelInfo.stmtsOffset});
}
if (labelInfoForDefault) {
// jump to default label if no match
makeInstruction(I.JUMP, {offset: labelInfoForDefault.stmtsOffset});
} else {
// jump to switch end
let offset = labelInfoList.reduce((sum, curr) => sum + curr.stmtsInsns.length + 1, 0);
offset += 1;
makeInstruction(I.JUMP, {offset});
}
for (const labelInfo of labelInfoList) {
if (!labelInfo.default) {
// pop duplicated switch.expr result
makeInstruction(I.POP);
}
embedInsns(labelInfo.stmtsInsns);
}
makeInstruction(I.POP_BREAKABLE);
makeInstruction(I.POP_SCOPE);
// pop unused switch.expr result
if (!labelInfoForDefault) {
makeInstruction(I.POP);
}
テストでは以下のように「わざとbreak入れないで次のcase 3部分が実行（出力）されるか」を確認していますが、このほぼバグな動作を実現することがこれほど大変とは思いませんでした(笑)
switch (a) {
case 1:
console.log('Apple');
break;
case 2:
console.log('Banana');
// fallthrough(intendedly)
case 3:
console.log('Cherry');
break;
default:
console.log('Other');
break;
}
switch文でのcontinue
さて伏線しておいた「breakはできるけどcontinueはできない」ものの話です。具体的にはswitchがそれに該当します。以下のようなプログラムを考えてみましょう6。コメントにあるようにswitch文内に書かれているcontinueはswitch文に作用するのではなくfor文に作用する必要があります。
for (let i = 1; i <= 5; i++) {
switch (i) {
case 2:
console.log('foo');
continue; // goto next for
case 4:
console.log('bar');
break; // goto switch end
}
console.log(i);
}
これを実現するために、PUSH_BREAKABLEを再掲すると以下のようにcontinueOffsetは「設定されていたら計算する」ようにしてあります。switchに対応するPUSH_BREAKABLEではこのプロパティは設定されていません（つまりundefined）
case I.PUSH_BREAKABLE:
{
// compute absolute address
let ptrBreak = context.ptr + insn.breakOffset;
let ptrContinue;
if (insn.continueOffset != undefined) {
ptrContinue = context.ptr + insn.continueOffset;
}
context.breakableStack.push({ptrBreak, ptrContinue});
}
break;
先ほどは飛ばしたcontinue処理ではbrekableStackをたどってptrContinueが設定されているものを使います。なお無限ループになっていますが別途「ptrContinueのあるbreakInfoが積まれる」ことは確認しているので実際に無限ループすることはありません（はず）
case I.CONTINUE:
while (true) {
const breakInfo = context.breakableStack.pop();
if (breakInfo.ptrContinue) {
return {type: 'JUMP_ABS', ptr: breakInfo.ptrContinue};
}
}
言語機能以外の改造
breakが出てくると命令ポインタの動きが頭の中で追いきれなくなってくるのでデバッグ情報として命令ポインタも出すようにしました。
ここら辺、「どのinsnsListを実行しているのか7」のような情報もいるかなと思いますが未対応です。また、「構文解析結果やアセンブル結果は見たいけど実行はしなくていい」のようなdry runみたいな機能もいるかなと思っていますがいいオプション文字列を思いついていないため未対応です。
その他
最終目標のセルフホスティングについて、「何ができたらセルフホスティングできたと言えるか」を定義していなかったのでテストを追加しました。このテストが通ったらセルフホスティング完了とします。8
import JokeEngine from 'joke';
const program = `
function hello(callback) {
console.log("Hello");
callback();
}
hello(() => {
console.log("World");
});
`;
const joke = new JokeEngine();
joke.run('<program>', program);
あとがき
以上、今回はbreakとcontinueの仕組みをメインに説明してきました。これで制御構造はひとまず終わりです9。
次は配列かなと思っていますが、メソッドのことを考えると先にオブジェクトとprototypeを作るべきか？ということも検討中です。
-
ちなみにCRubyやCPythonはbreakに対して一旦ブロック末尾に対応するラベルに飛ぶようにしておき、後からラベルとbreakが書いてある位置の距離を計算してたはずです（末尾の位置はまだ決まってないのでbreakを見つけた時点では計算できない）。ラベル絶対使いたくないマンというわけではないですがJOKEではこの方法は採用しませんでした。 ↩
-
ちなみに仕様ではwhile/forなどのIterationStatementとswitch（SwitchStatement）はBreakableStatementとしてまとめられています。 ↩
-
このようにしているのは
PUSH_BREAKABLEを出力する時点では相対位置しかわからない（whileのstmtなどは別の命令列配列に書き込ませた後マージしている）ためですが書いててやはりラベル埋め込み後から計算法の方が楽かもとも思ってきました(笑) ↩ -
else ifについてはJavaScriptでは「else節の文」として再帰処理されるためシンプルです。 ↩
-
これにより無数のバグが生まれたのはまた別のお話。 ↩
-
意味があるかは別として。ふと思いついてしまったのでテストしました。 ↩
-
すでにコミットしているので、セルフホスティング完了まで延々とテストが失敗します(笑) ↩
-
例外処理はクラスを作るまでできない、クラスは実質式ですし、for-ofは配列と合わせて実装するつもりです。 ↩