React diff算法

摘要：传统算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到，其中是树中节点的总数。对于同一层级的一组子节点，它们可以通过唯一进行区分。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。

https://zhuanlan.zhihu.com/p/...

React diff 会帮助我们计算出 Virtual DOM 中真正变化的部分，并只针对该部分进行实际 DOM 操作，而非重新渲染整个页面，从而保证了每次操作更新后页面的高效渲染，因此 Virtual DOM 与 diff 是保证 React 性能口碑的幕后推手。

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n3)，其中 n 是树中节点的总数。

Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。

拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。

对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

对树进行分层比较，两棵树只会对同一层次的节点进行比较。既然 DOM 节点跨层级的移动操作少到可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

由于 React 只会简单的考虑同层级节点的位置变换，而对于不同层级的节点，只有创建和删除操作。当出现节点跨层级移动时，并不会出现想象中的移动操作，而是以 A 为根节点的树被整个重新创建，这是一种影响 React 性能的操作，因此 React 官方建议不要进行 DOM 节点跨层级的操作。

React 是基于组件构建应用的，对于组件间的比较所采取的策略也是简洁高效。

如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。

如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点。

对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

如下图，当 component D 改变为 component G 时，即使这两个 component 结构相似，一旦 React 判断 D 和 G 是不同类型的组件，就不会比较二者的结构，而是直接删除 component D，重新创建 component G 以及其子节点。

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

INSERT_MARKUP，新的 component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。

MOVE_EXISTING，在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。

REMOVE_NODE，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，虽然只是小小的改动，性能上却发生了翻天覆地的变化！

先对新集合的节点进行循环遍历，for (name in nextChildren)，通过唯一 key 可以判断新老集合中是否存在相同的节点，if (prevChild === nextChild)，如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较，if (child._mountIndex < lastIndex)，则进行节点移动操作，否则不执行该操作。==这是一种顺序优化手段，lastIndex 一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置）==，如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作。

React 通过制定大胆的 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；

React 通过分层求异的策略，对 tree diff 进行算法优化；

React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；

React 通过设置唯一 key的策略，对 element diff 进行算法优化；

建议，在开发组件时，保持稳定的 DOM 结构会有助于性能的提升；

建议，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。

Level by Level

List

Components

Batching

Sub-tree Rendering

Selective Sub-tree Rendering

oldVdom不存在时，将newVdom生成的dom添加到父元素
newVdom不存在时，将newVdom对应index的真实dom删除
oldVdom, newVdom 的根节点不一致时，直接将oldVdom替换为newVdom
若上述都不满足，则说明两个vdom的根节点是一致的, 然后递归调用 diff & patch 方法

function h(type, props, ...children) {
    return {type, props, children};
}

function createElement(node) {
    if (typeof node === "string") {
        return document.createTextNode(node);
    }
    const $el = document.createElement(node.type);
    node.children
        .map(createElement)
        .forEach($el.appendChild.bind($el));
    return $el;
}

function changed(node1, node2) {
    return typeof node1 !== typeof node2 ||
        typeof node1 === "string" && node1 !== node2 ||
        node1.type !== node2.type
}

function updateElement($parent, newNode, oldNode, index = 0) {
    console.log(Array.from(arguments))
    // console.log(newNode)
    // console.log(newNode)

    if (!oldNode) {
        $parent.appendChild(
            createElement(newNode)
        );
    } else if (!newNode) {
        $parent.removeChild(
            $parent.childNodes[index]
        );
    } else if (changed(newNode, oldNode)) {
        console.log("if go changed")
        console.log(newNode, oldNode)
        $parent.replaceChild(
            createElement(newNode),
            $parent.childNodes[index]
        );
    } else if (newNode.type) {
        console.log("test if go last if")
        const newLength = newNode.children.length;
        const oldLength = oldNode.children.length;
        for (let i = 0; i < newLength || i < oldLength; i++) {
            updateElement(
                $parent.childNodes[index],
                newNode.children[i],
                oldNode.children[i],
                i
            );
        }
    }
}

// ---------------------------------------------------------------------

// let a = (
//     

//         
item 1
//         
item 2
//     
// );
//
// let b = (
//     

//         
item 1
//         
hello!
//     
// );

let a = h("ul", {}, h("li", {}, "item1"), h("li", {}, "item2"))
let b = h("ul", {}, h("li", {}, "item1"), h("li", {}, "hello!"))

const $root = document.getElementById("root");
const $reload = document.getElementById("reload");

updateElement($root, a);
$reload.addEventListener("click", () => {
    updateElement($root, b, a);
});



// 4. vdom diffs && patch
//index Virtual DOM对应处于真实DOM中的第几个子节点
function btsPatch(parentDomNode, oldVdom, newVdom, index=0) {
    if(!oldVdom) parentDomNode.appendChild(applyVDom(newVdom));
    if(!newVdom) { 
        if(parentDomNode.childNodes)
            parentDomNode.removeChild(parentDomNode.childNodes[index]);
    }
    if(typeof oldVdom != typeof newVdom ||
      (typeof oldVdom == "string" && oldVdom != newVdom) ||
      (typeof oldVdom == "object" && oldVdom.name != newVdom.name)
    ) {
        if(parentDomNode.childNodes && parentDomNode.childNodes[index])
            parentDomNode.removeChild(parentDomNode.childNodes[index]);
        parentDomNode.appendChild(applyVDom(newVdom));
    } else {
        if( typeof oldVdom == "object" ) {
            let count = Math.max(oldVdom.children.length, newVdom.children.length);
            if(count > 0) {
                for(let i=0; i < count; i++) {
                    btsPatch(parentDomNode.childNodes[index], oldVdom.children[i], newVdom.children[i], i);
                }
            }
        }
    }
    return // done bts or same string or no children
}