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

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の考え方が適用できる
• 賢いの書こうとすると、すぐオーダーの問題になるのでセンシティブな感じ

学びがあった。