2013年5月29日

harmony:spread

ES6 で追加される仕様 spread を実装するオハナシ。

http://wiki.ecmascript.org/doku.php?id=harmony:spread

「...」というオペレータで、配列を引数や配列の一部としてその場に展開できるという機能で、配列については既に Firefox16 で実装済。

js> [1, 2, ...[3, 4, 5]]
[1, 2, 3, 4, 5]

でも上のページの Sematics とはやや実装が違って、イテレータを使う事になってる。

しかし引数の方は未実装で、エラーになる。

js> print (1, 2, ...[3, 4, 5])
typein:3: SyntaxError: syntax error:
typein:3: print (1, 2, ...[3, 4, 5])

typein:3: .............^

で、これが欲しくなったのです。

きっかけは UnMHT で以下のような形のリストの変換をしようとした時の事。

[ [ [A, B, C], [M, N] ], [ [D, E, F, G], [O, P, Q], ... ] ]
↓
[ [ [A, B, C], [D, E, F, G], ... ], [ [M, N], [O, P, Q], ...] ]
↓
[ [A, B, C, D, E, F, G, ...], [M, N, O, P, Q, ...] ]

unzip して concat って感じなんだけど、JavaScript の Array の concat って複数の配列をまとめて連結する場合、それぞれ引数として渡さないといけない。

[].concat ([A, B, C], [D, E, F], [G, H, I])

手元に配列の配列があった場合には Array.prototype.concat.apply を使わないといけない。

Array.prototype.concat.apply ([], xs)

これを、

[].concat (...xs)

こう書きたい。

で、いつ頃実装されるのかなー、と Bugzilla の Bug 762363 を見てみたら、バグ登録以降進捗ナシ! (実はあるのかもしれないけど...)
なんでかしら、と思って Firefox のソースを覗いて弄り初めたワケです。

...

で、弄ったものがこちらになります。

js> [].concat (...[[1, 2, 3], [4, 5, 6], [7, 8, 9]]);
[1, 2, 3, 4, 5, 6, 7, 8, 9]
js> ((...x) => x) (1, 2, ...[3, 4, 5])
[1, 2, 3, 4, 5]

動いているかのように見える。
確かに動いているには動いているんだけど、ウソをついてる部分があるので完成とは言い難い。

元々、関数呼び出し (JSOP_CALL) は、

THIS.FUNC (ARG1, ARG2, ARG3)
↓
{FUNC}               // 関数本体に相当するバイトコード列
{THIS}               // this に相当するバイトコード列
JSOP_NOTEARG
{ARG1}               // 第 1 引数に相当するバイトコード列
JSOP_NOTEARG
{ARG2}               // 第 2 引数に相当するバイトコード列
JSOP_NOTEARG
{ARG3}               // 第 3 引数に相当するバイトコード列
JSOP_NOTEARG
JSOP_CALL(argc=3)

みたいなバイトコードで動いてる。

1. FUNC、THIS、ARG1、ARG2、ARG3 で、それぞれ引数をスタックに乗っける
-- ここから JSOP_CALL -- 2. スタックのうち引数の範囲を CallArgs から参照させる
3. 関数の中身を実行する
4. return の部分で FUNC があった場所に返り値を放り込む
5. スタックポインタを返り値の所まで戻す

で、5 の部分でいくつ戻すかっていうのが、

スタックの消費数 - スタックの生成数
= (argc + THIS 1 個 + FUNC 1 個) - (返り値 1 個)
= argc + 1

[js/public/CallArgs.h]
class MOZ_STACK_CLASS CallReceiver
{
...
    Value *spAfterCall() const {
        setUsedRval();
        return argv_ - 1;
    }
...
};

(argv_ は スタックのトップから argc だけ下なので、さらに 1 を引けば良い)

で、その数は実行より前に判明している事が前提になってるみたいなコードがある (このコードはスタックの消費数 = argc + 2)。

[js/src/jsopcode.cpp]
unsigned
js::StackUses(JSScript *script, jsbytecode *pc)
{
...
    switch (op) {
...
      default:
        /* stack: fun, this, [argc arguments] */
        JS_ASSERT(op == JSOP_NEW || op == JSOP_CALL || op == JSOP_EVAL ||
                  op == JSOP_FUNCALL || op == JSOP_FUNAPPLY);
        return 2 + GET_ARGC(pc);
    }
}

スタックの消費数は 2 + GET_ARGC(pc) って事になってて、JSOP_CALL みたいなのは 3 バイトのオペコードで、後ろ 2 バイトに argc を持っている。 (GET_ARGC はオペコードの後ろ 2 バイトの整数を取得する)

static bool
EmitCallOrNew(JSContext *cx, BytecodeEmitter *bce, ParseNode *pn)
{
...
    uint32_t argc = pn->pn_count - 1;
...
    if (Emit3(cx, bce, pn->getOp(), ARGC_HI(argc), ARGC_LO(argc)) < 0)
        return false;
...
}

spread を使うなら、実行してみないと argc が分からないので、バイトコード生成時に argc を与えるなんて事はできない。

ここが解決できてない所で、今はとりあえず可変 (-1 = 65535) という argc を例外扱いして、どうしても正数が必要な場合はウソ (適当に 3 = 引数は 1 個) を返している。
で、引数が 1 個じゃなければ 3 なんてのはウソなんでクラッシュするかと思ったけど別にクラッシュはしなかった...。
一体何のためにこの数が使われてるか更に解析する必要アリ。

[js/src/jsopcode.cpp]
unsigned
js::StackUses(JSScript *script, jsbytecode *pc)
{
...
    switch (op) {
...
      default:
        /* stack: fun, this, [argc arguments] */
        JS_ASSERT(op == JSOP_NEW || op == JSOP_CALL || op == JSOP_EVAL ||
                  op == JSOP_FUNCALL || op == JSOP_FUNAPPLY);
        if (GET_ARGC(pc) == 65535) {
            return 3;
        }
        return 2 + GET_ARGC(pc);
    }
}

で、バイトコード自体はどんな感じになったかというと

THIS.FUNC (ARG1, ARG2, ...ARG3)
↓
{FUNC}               // 関数本体に相当するバイトコード列
{THIS}               // this に相当するバイトコード列
JSOP_NOTEARG
JSOP_ZERO
{ARG1}               // 第 1 引数に相当するバイトコード列
JSOP_NOTEARG
SWAP
JSOP_ONE
JSOP_ADD
{ARG2}               // 第 2 引数に相当するバイトコード列
JSOP_NOTEARG
SWAP
JSOP_ONE
JSOP_ADD
{ARG3}               // 第 3 引数に相当するバイトコード列
JSOP_SPREADARG       // 勝手に新規追加したオペコード
JSOP_CALL(argc=-1)

まず、JSOP_CALL の argc が -1 の場合、argc をスタックのトップに乗っけた状態で JSOP_CALL を呼ぶ、という約束にする。

引数を乗せる前にまず JSOP_ZERO で 0 をスタックに乗っけておく。
引数を乗せたら上下を入れ替えてから 1 を足す、という事を繰り返す事でスタックには引数が順番に乗った上で、さらに現時点での argc が乗る。
さて spread はどうするかっていうと、引数 ARG3 を乗っけて、JSOP_SPREADARG を実行する。
JSOP_SPREADARG は、対象の引数 (ARG3) と argc をスタックからポップして、引数を展開した結果を順番にスタックに乗っけて、さらに展開した数だけ増やした argc をスタックに乗っける。
JSOP_NOTEARG については JSOP_SPREADARG の中で対応。といっても、何もしないオペコードなので JSOP_SPREADARG の中でも何もしない (IonMonkey の方では使ってるらしい)。

さて、JSOP_CALL の本体はどうなってるかというと、バイトコードから argc を取り出して CallArgs を生成する。

[js/src/jsinterp.cpp]
BEGIN_CASE(JSOP_NEW)
BEGIN_CASE(JSOP_CALL)
BEGIN_CASE(JSOP_FUNCALL)
{
...
    JS_ASSERT(regs.stackDepth() >= 2 + GET_ARGC(regs.pc));
    CallArgs args = CallArgsFromSp(GET_ARGC(regs.pc), regs.sp);
...
}

ここで、argc をバイトコードからじゃなくてスタックから取り出すようにすれば動く。

[js/src/jsinterp.cpp]
BEGIN_CASE(JSOP_NEW)
BEGIN_CASE(JSOP_CALL)
BEGIN_CASE(JSOP_FUNCALL)
{
...
    CallArgs args;
    if (GET_ARGC(regs.pc) == 65535) {
        JS_ASSERT(regs.stackDepth() >= 3);
        int32_t argc = regs.sp[-1].toInt32();
        regs.sp --;
        JS_ASSERT(regs.stackDepth() >= 2 + argc);
        args = CallArgsFromSp(argc, regs.sp);
    }
    else {
        JS_ASSERT(regs.stackDepth() >= 2 + GET_ARGC(regs.pc));
        args = CallArgsFromSp(GET_ARGC(regs.pc), regs.sp);
    }
...
}

という事でとりあえず動きはする状態にはなったんだけど、ヘンなものを渡すとクラッシュする。

js> ((...x) => x) (10, 20, ...{});
Assertion failure: index >= size_t(pcstack.depth()), at ***/mozilla-central/js/src/jsopcode.cpp:1489

あと、argc = -1 ってのがどうしてもダメそうなら、
spread がある場合、引数を全部配列に放り込んで 1 引数扱いにして apply を呼ぶようにするとか、
CallArgs を修正して引数をスタック以外に置けるようにするとか、
そんな感じになるかもしれない。

とりあえずもうしばらく弄ってみようと思う。

0 件のコメント:

コメントを投稿