前回はBackbone.jsの社内コードリーディング会でした。今回はVirtualDOMの軽量ライブラリとして少しずつ人気が出てきている気がするMithril.jsに関して行いますので、リーディング時のメモです。

Mithril
https://lhorie.github.io/mithril/

ソースコード(執筆時点v0.2.0 2015/07/18)
https://github.com/lhorie/mithril.js/blob/master/mithril.js

Virtual DOMの実装は約300行でそこが今回のソースコードリーディングのメインとなります。
今回はそのbuild()周りを見てきます。バージョンは現時点で最新のv0.2.0です。

ビール片手にリーディングしつつ、確認程度にメモを見ていただければ。


L1: undefined対策

でました。jqueryが導入して知られた方法ですね。関数にappという名前を付けているのは、あとでinternal test用に参照するためのもののようです.
(1156行目でwindowがない環境では空オブジェクトを渡しているということは、nodeやweb worker環境などでは動かない?)


L2: type check用の有名な(?)方法

Object.prototype.toStringによるtypeチェックを行っています。

なので、例えばこんなことやってると

Object.prototype.toString = function() { return 'hoge'; }

以下の呼び出しでhogeが返りますのでmithrilが動かなくなります。

({}).toString()

ObjectのtoStringを改変していないことがmithrilを使う前提ということですね。

参考

({}).toString() // -> "[object Object]"
({"prop": "hoge"}).toString() // -> "[object Object]"
(["hoge", "fuga"]).toString() // -> "hoge,fuga"
"hoge".toString() // -> "hoge"

// callを使ってthisをすり替えてやるとObject.prototype.toStringがthisが違うオブジェクトで呼ばれ出力される
({}).toString.call({"prop": "hoge"}) // -> "[object Object]"
({}).toString.call(["hoge", "fuga"]) // -> "[object Array]"
({}).toString.call("hoge") // -> "[object String]"

実はこれ結構有名な方法でunderscoreでも同じような実装でした。詳しく気になる方は以下の記事をご参照ください。


L35: m()
virtual domの登録の部分。文字列形式で受け取ったノード情報をregexでparseし、cellという以下のような形式のオブジェクトに変換していく。

例えば、以下のような文字列が右側のようなオブジェクトに変換されます。

m("div.classname#id[param=one][param2=two]") // -> {tag: "div", attrs: {id: "id", classname: "classname", param: "one", param2: "two"}, children: []}

mが階層化されているときは下から順番にcellが作られていきます。例えば、公式ドキュメントの例を見てみると、以下のように変換されます。

公式ドキュメントTODO Listサンプル
https://lhorie.github.io/mithril/getting-started.html#summary

m("html", [
    m("body", [
        m("input", {onchange: m.withAttr("value", todo.vm.description), value: todo.vm.description()}),
        m("button", {onclick: todo.vm.add}, "Add"),
        m("table", [
            todo.vm.list.map(function(task, index) {
                return m("tr", [
                    m("td", [
                        m("input[type=checkbox]", {onclick: m.withAttr("checked", task.done), checked: task.done()})
                    ]),
                    m("td", {style: {textDecoration: task.done() ? "line-through" : "none"}}, task.description()),
                ])
            })
        ])
    ])
])

/* ->
{
    tag: "html",
    attrs: {},
    children: [
        tag: "body"
        attrs: {}
        children: [
            {
                tag: "input",
                attrs: {
                    onchange: function(e){},
                    value: ""
                },
                children: []
            },
            {
                tag: "button",
                attrs: {
                    onclick: function(){}
                },
                children: ["Add"]
            },
            {
                tag: "table",
                attrs: [],
                children: []
            }
        ]
    ]
}
*/

後述のredraw()でm()が実行された後は上記のオブジェクトがdataという変数で次のbuild()に渡されます。


L36: arguments -> array変換

var args = [].slice.call(arguments);

Array likeなobjectであるargumentsをarrayにshallow copyして変換するコードかと思われます。あとでargs.sliceを使っているので、そのためのもののようです。


L74: build
Virtual DOMメイン実装
以下のようにコメントがあります。

the diff algorithm can be summarized as this:
1 – compare `data` and `cached`
2 – if they are different, copy `data` to `cached` and update the DOM based on what the difference is
3 – recursively apply this algorithm for every array and for the children of every virtual element

簡単に意訳すると

1. 今のvirtual domとcacheを比較する
2. 異なる場合は、異なる種類に応じて更新をする
3. 再帰的にchildrenを辿ってapplyする

mountやrequestなどからendFirstComputation -> endComputation -> redraw -> render -> buildの順に辿って、m()でtopの要素から変換したオブジェクトを再帰的に処理してきます。一応、後述しますが、例にあるようにtop要素がhtml要素で場合はfakeのinsertBeforeが作られていてappendChildになってたりします。

dataからchildrenへtreeを辿って再帰的に上記の各cellがdataというパラメーターとしてbuildが呼ばれていきます。

build()が再帰的に呼ばれるタイミングは意外とシンプルで以下の3箇所。
– dataがArrayの場合にdiffの処理が終わったあとに各要素に対してbuild()を呼ぶ
– dataがObjectで、その要素が新しい時にchildrenがあれば、childrenを渡してbuild()を呼ぶ -> DOM更新
– dataがObjectで、その要素がcacheにある場合はchildrenを渡してbuild()を呼ぶ -> DOM更新しない
終了条件はdataの配列が空だったりbutton要素の中のテキストなどの文字列が来る時で、returnされるものは各階層でのcachedのオブジェクトです。

top levelから始まるときは以下の引数がbuildに渡されます。

build(node, null, undefined, undefined, cell, cellCache[id], false, 0, null, undefined, configs)

引数それぞれparentElement, parentTag, parentCache, parentIndex, data, cached, shouldReattach, index, editable, namespace, configsに対応します。

もう少し詳しくそれぞれdataのtypeがArray, Object, Stringで分かれる処理を見ていきます。


dataがArrayであるとき (L118):

– L120: arrayが入れ子の場合はflattenする(後述)
– L130: cachedのattrsに’key’が存在する場合にdiffのアルゴリズムの説明
1) create a map of all existing keys, and mark all for deletion
2) add new keys to map and mark them for addition
3) if key exists in new list, change action from deletion to a move
4) for each key, handle its corresponding action as marked in previous steps

つまり、
1) cachedにあるattrsを全てDELETIONとしてマークする
2) 現在のdataのattrsは全てINSERTIONとしてマークする
3) 現在のdataのattrsが既存のものにもあった場合はDELETIONからMOVEに変更する
4) それぞれのkeyに対してマークされたアクションを実行する

ということです。

keysの使用例
https://lhorie.github.io/mithril/mithril.html#dealing-with-focus

m("ul", [
    items.map(function(item) {
        return m("li", {key: item.id}, [
            m("input")
        ]);
    })
]);

reactから来ている手法なんだと思いますが、リストなどの繰り返しのDOMに対してkeyをセットしておくとidentifierが明示されるのでより効率的に差分の更新が可能になるというものです。これによってリスト形式のDOMなどにshiftやspliceやsortのオペレーションを行った時にDOMの変更が最小限にする実装が可能になります。

実装をもう少し詳しく見ていきましょう。

L140: cachedにkeyが存在する場合はkey:actionのマップを生成します、その際にactionはDELETIONがセットされます
L155: まずattrsに’key’があるかをcheckした後に、arrayのサイズがcachedと比べて変わった場合、もしくは、一つでもkeyの値が変わった場合にdiffの処理に入ります
L169: 現在のdata (array)を一つずつ見て事前にcachedから作成しておいたkey:actionのマップを参照します。マップにまだ存在しなかった場合は、action INSERTIONとして登録します。マップに存在する場合はaction MOVEで上書きします。
L181: 出来上がったactionのmapからactionとindexでsortを行います。
L188: sortしたループの中でDELETIONが付いているものはDOMから削除を行います
L193: INSERTIONのものはinsertBeforeによってDOMに挿入されます
L200: MOVEのものは既に存在するDOMをinsetBeforeによって指定のindexに移動させます

ここまでがkeyによるdiffの実装でした。

dataがArrayである場合の処理はまだ少し続きます。
– L213: 各配列の要素を再帰処理としてbuildに渡していく
– L225: 一つでもintact(損傷がない完全な状態)ではないnodeがnodes内に存在する場合、各要素を処理したあとのnodes情報を現在のcahcedオブジェクトに更新する処理


dataがObjectであるとき (L241):

L265: 変更検知の部分

if (data.tag != cached.tag || dataAttrKeys.sort().join() != Object.keys(cached.attrs).sort().join() || data.attrs.id != cached.attrs.id || data.attrs.key != cached.attrs.key || (m.redraw.strategy() == "all" && (!cached.configContext || cached.configContext.retain !== true)) || (m.redraw.strategy() == "diff" && cached.configContext && cached.configContext.retain === false)) {

cacheしたタグやattrsが異なる場合や、configのretainがtrue以外でstrategy allの場合や、strategyがdiffでretainがfalseの時にはcacheのclearを呼んでいます。つまり条件にマッチすると、以前のnodeがDOMから削除されて、cached.nodes.lengthが0になるため、一からDOMを構築するプロセス(isNew)に入るようになります。

isNewの場合:
L283: document.createElementを使ってdata.tagからDOMを生成
L284: cacheオブジェクトを生成する時にattrsを生成したDOMにセット。childrenを再帰処理としてbuildへ 、そしてcacheオブジェクトには自身のDOMをnodesの配列に入れておく
L309: fakeもしくは実際のparentのinsertBeforeを呼んでDOMに挿入

isNewではない場合:
L314: cacheのchildrenを再帰処理としてbuildへ渡す
L315: 汚されていないというflagであるintactにtrue -> arrayでの処理内でbuildが呼ばれた時にintactをcheckして一つでも汚れていればnodesの更新を行う
L320: 親がrecreateされている場合は親DOMにinsertして終了


dataがStringであるとき (L335):

例えば、button要素の中のテキストを以下のようにm()で指定した場合はchildrenに文字列”Add”が要素として入ります。

m("button", {onclick: todo.vm.add}, "Add"),

その場合はdocument.createTextNode()などによりDOMを生成します。


これで、ざっくりとMithril Virtual DOMメインの実装であるbuild()の説明は終わりです。

基本的な流れは、m()で変換したdataをtopからツリーを辿ってcachedと比較しつつ、更新がある部分はDOMを生成しながら下がっていきます。末尾で変更が必要なものからDOMに挿入され、cachedを更新すると同時に上に上がりながら随時実際のDOMにinsertされていくという流れです。

意外と直感的で素直な実装のようです。

build()で重要なのはchildrenが渡された時のArrayに対する処理すると、それぞれの要素が渡された時のObjectに対する処理で大きく分岐している点だと思います。
Arrayに関してはkeyが存在する場合はdiffのアルゴリズムを適用し必要に応じてDOMを更新、Objectの時にはcachedと異なるかどうかを検知して必要に応じてDOMを更新、という処理が再帰的に行われます。
あと、cachedにはnodesというVirtual DOMによって表現されたものに対応した実際のDOMへのreferenceを持ち、それが常に最新と同期され、必要に応じて実際のDOMとして削除しているところもポイントです。


L120: flatten補足
上記に出てきflattenについて。

            //recursively flatten array
            for (var i = 0, len = data.length; i < len; i++) {
                if (type.call(data[i]) === ARRAY) {
                    data = data.concat.apply([], data);
                    i-- //check current index again and flatten until there are no more nested arrays at that index
                    len = data.length
                }
            }

一見何をしているかわからなかったですが、以下のコードを実行するとわかります。

[].concat([1, 2], [3, 4, 5], 6) // -> [1, 2, 3, 4, 5, 6]

ループの中で1要素のarrayを一度flattenしたあとに i– して len 現在のarrayの長さをセットしている理由は、展開後の要素の中にさらにarrayがある場合の対応。

つまり以下のケースは

[].concat([1, [2, 2.1, 2.3]], [3, 4, 5], 6) // -> [1, [2, 2.1, 2.3], 3, 4, 5, 6]

展開されてindexを今のところに戻して再実行されます。

どういうケースでchildrenの一つの要素がarrayになるのだろうか?と思ってみたら以下のようなarrayのmapをm()の子要素として指定したケースに、入れ子のarrayになるようです。

          m("table", [
                todo.vm.list.map(function(task, index) {
                    return m("tr", [
                        m("td", [
                            m("input[type=checkbox]", {onclick: m.withAttr("checked", task.done), checked: task.done()})
                        ]),
                        m("td", {style: {textDecoration: task.done() ? "line-through" : "none"}}, task.description()),
                    ])
                })
            ])

Virtual DOMメインの実装部分が終わったので、他は軽く流していきます。

L380: setAttributes
m()で受け取ったattrsを実際にDOMに適用するところです。基本的にはnode.setAttribute()をするのですが、それぞれのattrに対してちょっとした工夫がされています。
例えば、onxxxであったらbuildを行うためのautoredraw(後述)を呼ぶなど

L429: clear
buildで登録されたcached.nodesを実際にDOMから削除する

L440: unload
controllerのonunloadなどを呼ぶための後処理を行う(childrenがあれば再帰的に)

L477: autoredraw
onxxxで登録されたイベント時に自動的に呼び出されて、callbackを呼んだ後にendFirstComputationからredraw, renderを実行するためのもの。

L490: fake documentNode
m()でhtmlなどが指定された時にinsertBeforeなどDOM APIを擬似的に持ったラッパー

L505: render
メインのVirtual DOM diffアルゴリズムであるbuild()の前処理として条件によってfakeのinsertBeforeを用意したりDOMをクリアして、topレベルからbuild()を呼ぶ


ここら辺でだいたいMithril.js全体の半分で、build()周りのメインのVirtual DOMの実装がリーディングできたんじゃないかと思います。

次からprop, startComputation, route, deferred, requestのあたりを見ていきます!


Virtual DOMのコードを実際に読んでみて感想

VirtualDOMが一般的に速いと言われている理由がわかった気がしました。

理由は、実際のDOMの反映前にdiffを取って、変更部分だけに対してDOM変更適用に押さえられるから、ということだと思います。また、変更部分を検知するためのdiffはDOMを辿っているのではなく、実際はreferenceを辿っていているのも重要な点だと思います。

VirtualDOMライブラリの一つである今回のMithrilが速いと言われている理由は、詳しくは次回の記事で解説する予定ですが、今回解説したdiffのアルゴリズムが走るタイミングを極力減らす方針がとられているからだと思います。

ただ、やはり変更検知時に登録したノードのtopから全体のtreeを走査しているのは本当に効率的なのかな?と少し疑問に思いました。

それがまさにGoogleが最近出したIncremental DOMはその点を解消しているのかと思います。このような技術が出てくるのは、非常に自然な流れなんだなとコードを見ていて思いました。

では次回に続きます〜


Related Posts

JS

Facebook JavaScript SDKをrequireJSでロードする

Facebook Webアプリを作る際に便利なFacebook JavaScript SDKというものはご存知でしょうか。 これを使うと、クライアント側の認証やFBのAPIの呼び出しを簡単にJSで実現できます。 ただしSDKのロードは非同期に行われるため、コールバック等の扱いがやや複雑になります。特にrequireJSと組み合わせると、自作のモジュールの読み込みもasyncになるため、FB SDKのasyncのロードと整合性を合わせる必要があります。 今回はFB SDK+requireJSを使って、主にSDKロードからユーザーのログイン周りの処理の方法を紹介します。

JS

Polymer.importでWeb Componentsをlazy loadする

この記事はPolymer Advent Calendar 23日目の記事です。 前回の記事で紹介したvulcanize編では初期ロード時に必要なcomponentsを一つにまとめてしまおうというツールの紹介でした。 今回の記事は、同じくPolyermerのパフォーマンスアップのためのTips紹介ですが、少し話題は変わってWeb Componentsをlazy load(遅延ロード)する話です。

JS

Backbone.js 1.2.1コードリーディング徹底解体!その3

前回の”Backbone.js 1.2.1コードリーディング徹底解体!その2“の続きです!一応今回でbackbone 1.2.1のリーディングに関しては完結です!