vue3简单diff算法

使用过vue的同学应该都知道，vue通过虚拟dom（vnode）来尽可能得减少dom操作，优化渲染性能，其中diff算法就是负责计算出待更新dom的位置和可复用性。我们今天来实现一个简单的diff算法。

简单的节点更新

假设有以下新旧节点

// 旧节点
const oldChilren = [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' },
]
// 新节点
const newChilren = [
    { type: 'p', children: '3' },
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
]

简单的更新算法

不考虑复用性，我们可以使用以下方法更新节点

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        const oldLen = oldChilren.length
        const newLen = newChildren.length
        const commonLength = Math.min(oldLen, newLen)
        // 依次更新公共节点
        for (let i = 0; i < commonLength; i++) {
            patch(oldChilren[i], newChildren[i])
        }
        if (oldLen > newLen) {
            // 旧节点的数量大于新节点的数量，卸载旧节点
            for (let i = commonLength; i < oldLen; i++) {
                unmount(oldChilren)
            }
        } else if (newLen > oldLen) {
            // 旧节点的数量小于新节点的数量，新增新节点
            for (let i = commonLength; i < oldLen; i++) {
                patch(null, newChildren[i], container)
            }
        }
    }
}

主要的思路就是取公共节点进行更新，然后对于旧节点的数量大于新节点的数量，进行卸载旧节点的操作；对于旧节点的数量小于新节点的数量，进行新增新节点的操作。

其中patch函数的定义如下：

/**
 * 更新新旧节点
 * @param n1 旧vnode节点
 * @param n2 新vnode节点
 * @param container 父容器，用来挂载操作
 */
function patch(n1,n2,container){
    ...
}

主要作用有：

在n1存在的情况下，将n1节点替换为n2节点
在n1不存在的情况下，挂载n2节点到container下

这种方式，虽然新旧节点能够正常更新，但这种不管三七二十一批量替换的方式并不是我们想要的，下面我们来找出可复用的节点。

节点更新优化

考虑到更新性能，我们可以复用节点

复用节点的更新

需要复用节点，首先我们需要给每个节点增加一个key属性，来标识他的身份。

demo数据更新如下：

// 旧节点
const oldChilren = [
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
    { type: 'p', children: '3', key: 3 },
]
// 新节点
const newChilren = [
    { type: 'p', children: '3', key: 3 },
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
]

代码实现如下：

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        for (let i = 0; i < newChilren.length; i++) {
            const newNode = newChildren[i]
            for (let j = 0; j < oldChilren.length; j++) {
                const oldNode = oldChilren[i]
                // 找到key值相同的vnode
                if (oldNode.key === newNode.key) {
                    patch(oldNode, newNode, container)
                    break
                }
            }
        }
    } else {

    }
}

我们试着在旧节点中找到新节点对应的位置，通过两层循环一一比较key的值，我们就能找到可复用的节点，接下来我们需要知道哪些节点需要移动。
通过观察j我们会发现找到复用节点时的索引为2,0,1，而如果他的索引顺序为0,1,2，即和旧节点的顺序一致的话就不需要移动。所以只有当当前索引比最大存储的索引小的时候，我们才需要移动该节点。

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        // 最大存储的索引
        let lastIndex = 0
        for (let i = 0; i < newChilren.length; i++) {
            const newNode = newChildren[i]
            for (let j = 0; j < oldChilren.length; j++) {
                const oldNode = oldChilren[i]
                // 找到key值相同的vnode
                if (oldNode.key === newNode.key) {
                    patch(oldNode, newNode, container)
                    if (j < lastIndex) {
                        // 旧节点索引小于最大索引则移动dom
                    } else {
                        // 旧节点索引不小于最大索引则更新最大索引，不需要移动dom
                        lastIndex = j
                    }
                    break
                }
            }
        }
    } else {

    }
}

代码主要的运行流程如下：

在旧节点中寻找第一个新节点的位置，发现为2，大于lastIndex，无需移动，将lastIndex赋值为2
在旧节点中寻找第二个新节点的位置，发现为0，小于lastIndex，需要移动节点
在旧节点中寻找第三个新节点的位置，发现为1，小于lastIndex，需要移动节点

找到了需要移动的旧节点后，我们只需要把它移动到正确的位置即可，不难看出这个位置就是新节点所在的位置是是所在新节点的前一个元素的后面。

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        let lastIndex = 0
        for (let i = 0; i < newChilren.length; i++) {
            const newNode = newChildren[i]
            for (let j = 0; j < oldChilren.length; j++) {
                const oldNode = oldChilren[i]
                if (oldNode.key === newNode.key) {
                    patch(oldNode, newNode, container)
                    if (j < lastIndex) {
                        // 移动到新节点的上个元素的后面
                        const preNode = newChildren[i - 1]
                        // 如果不存在前一个节点说明是第一个节点不需要移动
                        if (preNode) {
                            const anchor = preNode.el.nextSibling
                            // 将newNode移动到anchor前面
                            insert(newNode, container, anchor)
                        }

                    } else {
                        lastIndex = j
                    }
                    break
                }
            }
        }
    } else {

    }
}
/** 插入节点 */
function insert(el, parent, anchor) {
    parent.inserBefore(el, anchor)
}

代码主要的运行流程如下：

在旧节点中寻找第一个新节点的位置，发现为2，大于lastIndex，无需移动，将lastIndex赋值为2
在旧节点中寻找第二个新节点的位置，发现为0，小于lastIndex，需要移动节点，位置是所在新节点的前一个元素的后面
在旧节点中寻找第三个新节点的位置，发现为1，小于lastIndex，需要移动节点，位置是所在新节点的前一个元素的后面

新增节点

光复用老节点还不够，当新节点数据变为

const newChilren = [
    { type: 'p', children: '3', key: 3 },
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '4', key: 4 },
    { type: 'p', children: '2', key: 2 },
]

这时候执行patchChildren函数后会发现key=4的节点没有被添加进去。接下来我们这么做：

1.找到新节点

2.挂载新节点到新的位置

代码实现如下

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        let lastIndex = 0
        for (let i = 0; i < newChilren.length; i++) {
            const newNode = newChildren[i]
            // 新增find标识，表示在旧节点中是否存在可复用的节点
            let find = false
            for (let j = 0; j < oldChilren.length; j++) {
                const oldNode = oldChilren[i]
                if (oldNode.key === newNode.key) {
                    // 找到则置为true
                    find = true
                    patch(oldNode, newNode, container)
                    if (j < lastIndex) {
                        const preNode = newChildren[i - 1]
                        if (preNode) {
                            const anchor = preNode.el.nextSibling
                            insert(newNode, container, anchor)
                        }

                    } else {
                        lastIndex = j
                    }
                    break
                }
            }
        // 如果代码运行到这里find为false则表示为新节点
        if(!find){
            const preNode = newChildren[i - 1]
            let anchor = null
            if(preNode){
                // 锚点元素为前一元素的后一个节点
                anchor = preNode.el.nextSibling
            }else{
                // 没有前一个节点说明新节点是第一个节点，所以锚点元素设置为第一个元素
                anchor = container.firstChild
            }
            // 挂载新节点
            patch(null, newNode, container, anchor)
        }

    } else {

    }
}

移除不存在的旧节点

当新节点数据变为时，我们就需要移除key=2的旧节点

const newChilren = [
    { type: 'p', children: '3', key: 3 },
    { type: 'p', children: '1', key: 1 },
]

代码实现如下:

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {

    } else if (Array.isArray(n2.children)) {
        const oldChilren = n1.children
        const newChildren = n2.children
        let lastIndex = 0
        for (let i = 0; i < newChilren.length; i++) {
            // 省略部分代码
        }
        // 遍历一遍旧节点
        for(let i = 0; i < oldChilren.length; i++){
            const oldNode = oldChilren[i]
            // 未找到的节点进行移除
            if(!newChilren.find(vnode=>vnode.key === oldNode.key)){
                // 调用 unmount将其卸载
                unmount(oldNode)
            }
        }
    } else {

    }
}

总结

至此，我们讨论了diff算法的作用，并通过key来试图最大化程度得复用DOM元素，避免过多得对DOM元素进行销毁和重建。

我们讨论了简单diff算法是如何找到需要移动的元素的：拿新的一组节点中的节点去旧节点中寻找可复用的节点，如果找到了则记录该位置的索引，我们把这个位置称为最大索引，在整个更新过程中如果一个节点的索引小于最大索引，则说明该节点对应的真实DOM元素需要移动。

最后我们介绍了如何新增和删除虚拟节点。

vue3简单diff算法 ​

简单的节点更新 ​

简单的更新算法 ​

节点更新优化 ​

复用节点的更新 ​

新增节点 ​

移除不存在的旧节点 ​

总结 ​