ReactのList Diff（リスト差分）

1. Tree Diff（木構造の差分）

木（ツリー）構造の diff は比較的複雑な問題です。まず簡単なシナリオを考えてみましょう：

    A           A'
   / \   ?    / | \
  B   C  ->  G  B   C
 / \  |         |   |
D   E F         D   E

diff(treeA, treeA') の結果は以下のようになるはずです：

1. G を B の前に挿入 (insert G before B)
2. E を F の位置に移動 (move E to F)
3. F を削除 (remove F)

treeA に対して上記の3つのステップを実行すれば treeA' が得られます。木の規模が小さい場合、一目で見分けることができますが、どうやって見分けたのかを振り返ってみましょう：

1. 上から下へと観察し、全く違うノードであればそれ以上探索しない
2. 現在の階層のノードを比較し、「追加（新しいものにはあり、古いものにはない）」と「削除（古いものにはあり、新しいものにはない）」を見つける
3. 下の階層の子ツリー構造が似ているかを見て、「移動（既存のノードの位置を変える）」かどうかを判断する

これをコンピュータに行わせる場合、「追加」と「削除」は見つけやすいですが、「移動」の判定はかなり複雑になります。まず、ツリーの類似度を数値化（例えば加重編集距離など）し、類似度がどの程度であれば「削除＋追加」よりも「移動」の方がコストが低い（操作手順が少ない）かを決定する必要があります。

P.S. Tree Diffアルゴリズムに興味がある場合は、Matching, diffing and merging XML を参考にしてください。古い記事（2008年）ですが、とても興味深いです。

2. Reactの仮定

Reactの内部で管理されている仮想DOMツリーも、どのように diff を行うかという問題に直面しています。DOMツリーが頻繁に更新される（頻繁なインタラクションがある）場合、複雑すぎる tree diff 手法はパフォーマンス上の問題を引き起こします。DOM操作のシナリオの特徴を考慮してみましょう：

• 部分的な小さな変更が多く、大規模な変更は少ない（パフォーマンスを考慮し、表示/非表示の切り替えで回避されることが多い）

• 階層をまたぐ移動は少なく、同じ階層内でのノード移動が多い（例えばテーブルのソートなど）

もし大規模な変更が多いのであれば、 diff はほとんど無意味であり、純粋なパフォーマンスの浪費になります。もし階層をまたぐ移動が多いのであれば、正確な move 判定が必須となり、アルゴリズムへの要求が非常に高くなります。DOM操作のシナリオは都合よくそこまで高い要求を必要としないため、Reactはいくつかの仮定を立てました：

1. 異なるタイプの2つの要素は、異なるツリーを生成する。

2. 開発者は key プロパティを使って、どの小要素が異なるレンダリング間で安定しているかをヒントとして提示できる。

つまり：

• 異なるタイプの要素は異なる子ツリーに対応すると仮定する（「下の階層の子ツリー構造が似ているか」を考慮しないため、「移動」の判定の難易度がなくなる）

• 変更前後の構造には一意の key が付与され、それを diff の基準とする。同じ key は同じ要素を表すと仮定する（比較コストの削減）

さらに、念のためReactは shouldComponentUpdate フックを提供し、 diff プロセスに人為的に介入して誤判定を避けることもできるようにしています。

3. 仮想DOMツリーのDiffとList Diff

ツリー構造を直接比較しようとすると、どこから手をつけていいか分かりません（人間の目は形状や構造の違いを簡単に比較できますが、コンピュータはこれが苦手です）。例えば：

Page
  Header
    div
      img
      p
  List
    Item1
      img
      p
      button
    Item2...

diff(Page, newPage) の結果を直接導き出すのは困難に思えます。そこで、問題の規模を縮小する方法を考えます。即効性のある良い方法は**再帰（再帰呼び出し）**です：

1. 各ノードが自分自身を更新する必要があるかチェックする
2. 必要であれば直接の子ノードをdiffし、 追加、削除、移動、変更 を見つける
3. 「変更」が必要なノードに対して再帰的に下へチェックを続け、葉ノードまで到達する

このようにして、ツリーの diff は list diff（リストの差分）に分解されます。実際に実装する必要があるのは list diff の部分だけであり、問題は非常に明確になりました。

4. List Diff（リスト差分）

2つの1次元整数配列を考えてみましょう：

var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];

どのように diff を使って 追加/削除/移動 を見つけるのでしょうか？

1. 古いリストを走査し、「削除」を見つける
2. 新しいリストを走査し、「追加」と「移動」を見つける

シンプルな実装案

まずはパフォーマンスや複雑さを考慮せず、最もシンプルで強引な list diff を実装してみます：

var diff = function(oldList, newList) {
    var changes = [];
    // 位置をシミュレートするためのミラー（コピー）
    var _oldList = oldList.slice();
    // 古いリストを走査し、削除を見つける
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
            _oldList.splice(i, 1);
        }
    });

    // 新しいリストを走査し、追加/移動を見つける
    newList.forEach(function(item, i) {
        var index = _oldList.indexOf(item);
        if (index === -1) {
            // 追加
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            _oldList.splice(i, 0, item);
        }
        else {
            // 移動
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                move(_oldList, step.from, step.to);
            }
        }
    });

    return changes;
};
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to, 0, item[0]);
    else
        list.splice(to - 1, 0, item[0]);
};

patch（適用）のシミュレーション：

var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};

実行して得られる操作手順：

source  1 2 3 7 4
target  1 4 5 3 7 6

remove 2
  1 3 7 4
move 4 to 3
  1 4 3 7
insert 5 before 3
  1 4 5 3 7
insert 6 before undefined
  1 4 5 3 7 6

位置をシミュレートするために _oldList ミラーを使用することで、「追加/削除/移動」による index への影響を計算する手間を省いていますが、余分なメモリ空間のオーバーヘッドがあります。この部分を取り除く方法を考えてみましょう。

空間消費の最適化

位置をシミュレートする操作をなくし、直接 index changes を計算します：

// 1. 位置をシミュレートする操作の代わりにindex changeの記録を使用する。先に新しいリストを走査し、次に古いリストを走査する
var diff = function(oldList, newList) {
    var changes = [];
    // changeがoldListのまだ比較していない要素のindexに与える影響を計算する。これは区間になる。
    // なぜなら、自分より前の要素をさらに前に移動させても、自分のindexには影響しないから。
    // move時、影響を受けるのは <=lastIndex のindexのみ。
    // <=index: delta で表現する。
    var maxLength = Math.max(oldList.length, newList.length);
    var oldIndexChanges = new Array(maxLength).fill(0);
    // 修正前のindex
    var _index;

    // 新しいリストを走査し、追加/移動を見つける
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 追加
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            // insertはoldListの後続のすべての要素のindexに影響を与える
            oldIndexChanges[maxLength - 1]++;
        }
        else {
            _index = index;
            // old indexの修正
            // indexから先頭に向かって数え、sum deltaを求める
            index += oldIndexChanges.reduce(function(acc, delta, idx) {
                if (idx >= index)
                    return acc + delta;
                else
                    return acc;
            });
            // 移動
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                if (index > i) {
                    // moveはoldListの <=from の要素に影響を与える
                    oldIndexChanges[_index]++;
                }
                else {
                    // fromがtoより小さくなることはあり得ない
                    // 前から順番にスキャンしており、[0, to-1]の位置は確定済みで、前から要素を取ることはないため
                    console.error('impossible');
                }
            }
        }
    });

    // 古いリストを走査し、削除を見つける
    // 総deltaを計算する
    // insertとmoveを経た後、削除される要素は必ず一番最後にあり、すべてのindex changeの影響を受ける
    var indexDelta = oldIndexChanges.reduce(function(acc, delta) {
        return acc + delta;
    });
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            // old indexの修正
            i += indexDelta;
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

// 2. patchのシミュレーション
var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};

実行して得られる操作手順：

source  1 2 3 7 4
target  1 4 5 3 7 6

move 4 to 2
  1 4 2 3 7
insert 5 before 2
  1 4 5 2 3 7
move 3 to 2
  1 4 5 3 2 7
move 7 to 2
  1 4 5 3 7 2
insert 6 before 2
  1 4 5 3 7 6 2
remove 2
  1 4 5 3 7 6

操作手順が2ステップ増えてしまいました。これは先に「移動」を行い、後から「削除」を行ったためです（後から「削除」を行えば、「追加・移動」を行う際に「削除」による index の変動を考慮しなくて済むため）。その中で、相対的に削除されるべき 2 に対して行われた2回の move は無意味です。これを回避する方法を考えなければなりませんが、ここでは深入りせず、直接Reactのオリジナル実装を見てみましょう。

5. React List Diff

我々のアプローチと似ており、先に新しいリストを走査し、次に古いリストを走査します：

var diff = function(oldList, newList) {
    var changes = [];
    // 過去にアクセスした元のchildrenリストの最大のindex
    var lastIndex = 0;
    // 前回配置したノード。追加/移動の基準に使用する
    var lastPlacedNode = null;

    // 新しいリストを走査し、追加/移動を見つける
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 追加
            changes.push({
                type: 'insert',
                item: item,
                afterNode: lastPlacedNode
            });
        }
        else {
            // lastIndexを利用して相対位置が変わっていない移動を除外する
            if (index < lastIndex) {
                // 移動
                var step = {
                    type: 'move',
                    item: item,
                    afterNode: lastPlacedNode
                };
                changes.push(step);
            }
            lastIndex = Math.max(index, lastIndex);
        }
        lastPlacedNode = item;
    });

    // 古いリストを走査し、削除を見つける
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

ここで非常に賢い最適化となっているのが lastIndex です。アクセスした元のリストの最も右側の要素の index を記録しておき、元の相対位置では要求を満たせなくなる（移動せざるを得なくなる）まで移動を行いません。これにより元の相対位置を最大限に活用し、不必要な移動を避けています。

patch のシミュレーション：

var showSteps = function(changes) {
    // 「移動」の際に以前の位置を調べるためにバックアップを残しておく
    var _oldList = oldList.slice();
    // DOM操作のシミュレーションにおいて、追加、移動、削除の対象となる古い要素の現在のindexを知る必要がある
    // 実際のDOMのpatchを行う際は、要素を見つければDOM APIはindexなしで追加、移動、削除ができるため不要
    var patchingIndex = -1;
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                insertAfter(oldList, change.item, patchingIndex);
                break;
            case 'remove':
                console.log('remove ' + _oldList[change.index]);
                patchingIndex = oldList.indexOf(_oldList[change.index]);
                oldList.splice(patchingIndex, 1);
                break;
            case 'move':
                console.log('move ' + change.item + ' to pos after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                move(oldList, oldList.indexOf(change.item), patchingIndex);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to + 1, 0, item[0]);
    else
        list.splice(to, 0, item[0]);
};
var insertAfter = function(list, item, index) {
    list.splice(index + 1, 0, item);
};

実行して得られる操作手順：

source  1 2 3 7 4
target  1 4 5 3 7 6

insert 5 after 4
  1 2 3 7 4 5
move 3 to pos after 5
  1 2 7 4 5 3
move 7 to pos after 3
  1 2 4 5 3 7
insert 6 after 7
  1 2 4 5 3 7 6
remove 2
  1 4 5 3 7 6

1 と 4 に遭遇したときは、元の相対順序が正しいため動かしません。 3 に遭遇したときに、移動させないと元の相対位置を維持できなくなるため、ここで初めて「移動」を行います。

この例を見る限り、Reactの実装は最も効率的というわけではありません。私たちが最初に書いたシンプルなバージョン（先に「削除」し、その後に「追加・移動」を行う）であれば、たった4ステップで完了します。

6. オンラインデモ

例に挙げたシナリオにおけるReactの実装および本文中の各 diff メソッド：http://www.ayqy.net/temp/react/demo/list-diff.html

ブラウザのコンソールを開き、「更新List」をクリックして diff の結果を確認してください。

P.S. Reactのバージョンは15.5.4です。

参考文献

• Reconciliation - React

• reactjs源码分析-下篇（更新机制实现原理）：非常に素晴らしいソースコード分析です