React List Diff | 黯羽轻扬

一.Tree Diff

树的diff是个相对复杂的问题，先考虑一个简单场景：

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

diff(treeA, treeA')结果应该是：

1.insert G before B
2.move   E to     F
3.remove F

对treeA做以上3步，就能得到treeA'，树的规模较小时，一眼就能看出来，回想下是怎么做到的：

1.自顶向下观察，完全不一样就不用找了
2.对比当前层节点，找出 增（新的有旧的没有）、删（旧的有新的没有）
3.向下看子树结构是否相似，判断是不是 移（把原有节点移动位置）

如果要计算机来做的话，增和删好找，移的判定就比较复杂了，首先要把树的相似程度量化（比如加权编辑距离），并确定相似度为多少时，移比删+增划算（操作步骤更少）

P.S.对Tree Diff算法感兴趣的话，可以参考Matching, diffing and merging XML，文章比较老（08年），但挺有意思

二.React假设

React内部维护的虚拟DOM树也面临如何diff的问题，DOM树频繁更新（频繁交互的话），过于复杂的tree diff方案会带来性能困扰，考虑DOM操作场景的特点：

局部小改动多，大片的改动少（性能考虑，用显示隐藏来规避）
跨层级的移动少，同层节点移动多（比如表格排序）

如果大片改动多的话，diff基本上是没有意义的，纯粹的性能损耗。如果跨层级移动多的话，精确的move判定就很必要，对算法要求就很高。DOM操作场景恰好不需要太高要求，据此提出了几点假设：

1.Two elements of different types will produce different trees.

2.The developer can hint at which child elements may be stable across different renders with a key prop.

也就是说：

假设不同类型的元素对应不同子树（不考虑“向下看子树结构是否相似”，移的判断就没难度了）
前后结构都会带有唯一的key，作为diff依据，假定同key表示同元素（降低比较成本）

另外，保险起见，React还提供了shouldComponentUpdate钩子，允许人工干预diff过程，避免误判

三.虚拟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部分，问题变得很明朗了

四.List Diff

考虑两个一维整数数组：

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做的两步move没有意义，要想办法规避掉，这里不再展开，直接看React的原版实现

五.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，记录摸过的源list最右元素的index，直到原相对位置无法满足需要了（不移不行了），才做移，这样来最大限度地利用原相对位置，避免不必要的移动

模拟patch：

var showSteps = function(changes) {
    // 留一份，针对 移 用来查以前的位置
    var _oldList = oldList.slice();
    // 针对 增 移 和 删，模拟DOM操作需要知道patching中，旧元素的当前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步就能完成

六.在线Demo

示例场景下的React实现及文中各例diff方法：http://www.ayqy.net/temp/react/demo/list-diff.html

打开浏览器Console，点“更新List”，看diff结果

P.S.React版本为15.5.4

参考资料

Reconciliation – React
reactjs源码分析-下篇（更新机制实现原理）：非常漂亮的源码分析

《React List Diff》上有2条评论

john 2017-08-08 19:22

下面优化的 list diff算法有问题，比如对于 oldList = [1,3,7,8] newList = [8,3,7,1]通过你下面优化后的算法得到的move不正确

回复 ↓
1. ayqy 文章作者2017-08-19 21:38
  感谢指出错误，文中的list diff优化以及react list diff都存在错误，已经修正
  
  list diff优化不能只简单的先做增移，后做删，增和移会影响old list index，后续的index比较结果就错了，改用oldIndexChanges区间记录对old list index的影响
  
  react list diff判断move多了一个index不等的条件，保持相对位置不动的话，index比较已经失去了意义，应该去掉（当时没明白react的move判断为什么不比较index，没有深入去想），见react源码：
```
moveChild: function (child, afterNode, toIndex, lastIndex) {
  // If the index of `child` is less than `lastIndex`, then it needs to
  // be moved. Otherwise, we do not need to move it because a child will be
  // inserted or moved before `child`.
  if (child._mountIndex < lastIndex) {
    return makeMove(child, afterNode, toIndex);
  }
}
```
  回复 ↓

一.Tree Diff

二.React假设

三.虚拟DOM树 Diff与List Diff

四.List Diff

简单方案

优化空间消耗

五.React List Diff

六.在线Demo

参考资料

《React List Diff》上有2条评论

发表评论 取消回复

发表评论取消回复