AdventCalendar
reactjs
deku

segmentio/dekuのコード読んで自分でも仮想DOMのdiffアルゴリズムを書いてみた

More than 3 years have passed since last update.

VirtualDOM Advent Calendar 2014 - Qiitaの6日目です。

前回、チラッと紹介したdeku、どんなもんかそこまで詳しく知らなかったのでコード読んでみた。

segmentio/deku


Dekuの特徴


  • APIはほぼReactと一緒


    • render/renderToString/setState/shouldUpdate



  • 小さい


    • 手元でビルドしたのが23kb(Reactが90kb)

    • 公式が9kb謳ってるのは、昔の名残かな…?gzipかもしれないけど

    • diff即生DOM操作なんでヘッドレスで動くような構造ではない



  • duo.jsに依存して書かれてる


    • まあsegment.io製だし



デクだけにシンプル。小さいのが特徴。

アルゴリズムとしての本質はここみればわかる deku/diff.js at master · segmentio/deku


dekuを参考に自分で仮想DOMアルゴリズム書いてみた

dekuで雰囲気掴んだので自分でも書いてみた。

やること


  • keyとchildrenだけなelementノード同士を比較する

  • JSONとJSONを比較して、JSONにpatchする

patch先がJSONなんで有り難みがないけど、勉強用にはこれでよい。

本当はtextノードとかcomponentノードがあるけど、めんどいんでパス。後述するdiffの比較パターンが増えるだけで、そんなに難しくはない。


書いてみる

さっくりcoffeeで書く。

まずこういうデータを用意する。


treeA =
key: 'foo'
children: [
{key: 'baa', children: []}
{key: 'baz', children: []}
]
props: {a: 1}

treeB =
key: 'foo'
props: {a: 1, b: 2}
children: [
{
key: 'fuba'
children: []
} # diff
{
key: 'bar'
children: []
}
{
key: 'baz'
children: [
{
key: 'xxx'
children: []
} # diff
{
key: 'xxx'
children: []
} # diff
]
}
]

treeC =
key: 'foo'
props: {a: 3}
children: [
{key: 'bar', children: []}
{key: 'fuba', children: []}
]

コード全体(あとで関数ごとに解説する)

_ = require 'lodash'

diffChildren = (prev, next, parent, path) ->
node = parent[path]
len = Math.max prev.children.length, next.children.length
i = -1
while ++i < len
left = prev.children[i]
right = next.children[i]
if left? and right?
diff left, right, node.children, i
else if right? # added
node.children[i] = _.cloneDeep right
else if left? # removed
node.children.splice i, 1
len--
i--

diffAttrs = (prev, next, node) ->
node.props ?= {}
next.props ?= {}
prev.props ?= {}
for key, next_val of next.props
if next_val isnt prev.props[key]
node.props[key] = next_val
for key of prev.props when key not in _.keys(next.props)
delete node.props[key]

diff = (prev, next, parent, path) ->
node = parent[path]
if prev.key is next.key
diffAttrs prev, next, parent[path]
else
parent[path] = _.cloneDeep next
diffChildren prev, next, parent, path

解説


diff

diff = (prev, next, parent, path) ->

node = parent[path]
if prev.key is next.key
diffAttrs prev, next, parent[path]
else
parent[path] = _.cloneDeep next
diffChildren prev, next, parent, path


  • キーを比較して、同じならAttributesの比較。違うなら自分自身を全書き換え

  • その後childrenの比較をする

JSというかポインタがない言語特有の辛い点として、ポインタを扱えないので自分自身の木を書き換えようとしたら親と自分自身のキーを渡す必要があり、この辛い点が (prev, next, parent, path) -> の第三、第四引数に表れてる。


diffAttrs

diffAttrs = (prev, next, node) ->

node.props ?= {}
next.props ?= {}
prev.props ?= {}
for key, next_val of next.props
if next_val isnt prev.props[key]
node.props[key] = next_val
for key of prev.props when key not in _.keys(next.props)
delete node.props[key]


  • 2つのノードのpropsオブジェクトを比較して、キーの値が更新されていればnodeのキーを更新

  • 消えてるキーは削除

ここは簡単


diffChildren

diffChildren = (prev, next, parent, path) ->

node = parent[path]
len = Math.max prev.children.length, next.children.length
i = -1
while ++i < len
left = prev.children[i]
right = next.children[i]
if left? and right?
diff left, right, node.children, i
else if right? # added
node.children[i] = _.cloneDeep right
else if left? # removed
node.children.splice i, 1
len--
i--


  • ループする回数(len)を長い方に合わせる

  • 前(left)が存在して次(right)が存在しない場合はそのインデックスをrightに書き換え

  • 前(left)が存在せず次(right)が存在する場合はそのインデックスを削除。カーソル(i) とループ回数(len)を一個ずつ減らす

  • どちらもノードが存在する場合はdiffに渡す(結果として再帰)

(簡単なコードに見えるけど再帰沼に引っかかって2時間ぐらいかかってます…)


使い方

というわけで使う

pp = require 'prettyjson'

# debug用dump
p = ->
if arguments.length is 1
console.log pp.render arguments[0]
else if arguments.length is 2
console.log arguments[0] + ':\n' + pp.render arguments[1]

parent = node: _.cloneDeep treeA
diff treeA, treeB, parent, 'node' # A -> B
p parent.node
console.log '--------'
diff parent.node, treeC, parent, 'node' # B -> C
p parent.node

ポインタ使えないのでこういうふうにparent.node, 'node' が俺だぜって渡すことになる。その結果、parent.nodeに副作用がおきる。

たぶん外部に提供するときはファサード作ると思う。

key:      foo

children:
-
key: fuba
children:
(empty array)
-
key: bar
children:
(empty array)
-
key: baz
children:
-
key: xxx
children:
(empty array)
-
key: xxx
children:
(empty array)
props:
a: 1
b: 2
--------
key: foo
children:
-
key: bar
children:
(empty array)
-
key: fuba
children:
(empty array)
props:
a: 3

こういう感じになる

ちゃんとテストしてなくて目視チェックだけど許して


わかったこと


  • プロパティ比較の関数と子孫の比較の関数で再帰すれば良い

  • というかこの2つさえあればよい。エントリはポイントはプロパティ比較

  • 今のままだとArrayの判定がナイーブすぎて子が一個ずれたりすると全部走ってしまう


    • とはいえ賢く書こうとすると一気に辛くなる



  • (このコードからは有り難みがわからないが)とにかく前後の状態だけを触って、結果を木にあてる。ここの「翻訳」(今回はjson->json)を任意の構造体に対応させさえすれば、木構造なら何にでも仮想DOMの考え方が適用できる

  • 賢いの書こうとすると、すぐオーダーの問題になるのでセンシティブな感じ

学びがあった。