Vue.js 虚拟DOM和diff算法

发表于 2022-10-23 更新于 2025-05-02 分类于编程

虚拟DOM和diff算法是什么?

虚拟DOM是用JavaScript对象描述DOM的层次结构，DOM中的一切属性都在虚拟DOM中有对应的属性。

diff算法发生在虚拟DOM上，将新旧虚拟DOM进行精细化比较，找到新旧虚拟DOM中的不同，计算出如何最小量更新，并将更新结果反映到真实DOM上。

真实DOM：

1
2
3

<div class="box">
    <h3>Hello World</h3>
</div>

虚拟DOM：

{
    "sel": "div",
    "data": {
        "class": { "box": true }
    },
    "children": [
        {
            "sel": "h3",
            "data": {},
            "text": "Hello World"
        }
    ]
}

如果通过虚拟DOM来实现下面DOM变化：

那就需要将新旧的虚拟DOM进行diff算法：

snabbdom

snabbdom是虚拟DOM的鼻祖，Vue中的虚拟DOM就借鉴了snabbdom的思想。先来学习一下snabbdom的使用方法并配置snabbdom的开发环境。

配置开发环境

安装snabbdom：

1	$ npm install snabbdom -S

安装webpack：

1	$ npm install webpack webpack-cli webpack-dev-server

webpack.config.js：

module.exports = {
    mode: "development",
    entry: './src/index.js',
    output: {
        publicPath: "/virtual/",
        filename: 'bundle.js'
    },
    devServer: {
        port: 8080,
        static: "www"
    }
};

然后新建src/index.js、www/index.html，并在index.html中引入virtual/bundle.js，中再运行npm run dev运行webpack-dev-server，即可将项目运行起来了。

h函数

在index.js中，我们从snabbdom包中引入init、h两个函数和数据模块，其中h函数用来创建虚拟节点，patch函数用于将虚拟节点上树：

import {
    init,
    propsModule,
    h,
} from "snabbdom";

然后通过h函数创建虚拟节点：

1	const vnode = h("div", { props: { id: "container" } }, "Hello World");

再创建patch函数，再init函数中包含数据模块：

1
2
3

const patch = init([
    propsModule,
]);

通过DOM获取div，并将虚拟节点上树：

1 2	const container = document.getElementById("container"); patch(container, vnode);

保存并刷新，可以看到创建的div已经被渲染出来了：

我们把刚刚创建的虚拟节点在控制台中打印出来：

{
    "sel": "div",
    "data": {
        "props": {
            "id": "container1"
        }
    },
    "text": "Hello World",
    "key": undefined,
    "elm": div#container1,
    "children": undefined,
}

可以看到虚拟节点一共有6个属性：sel是选择器，selector的缩写；data就是节点的class、id之类的数据；text就是节点的文本内容；ele表示在真实DOM上的节点；children表示节点的子节点；key是undefined，是每一个虚拟节点的唯一标识。

h函数可以嵌套使用

const vnode = h("ul", [
    h("li", "1"),
    h("li", "2"),
    h("li", "3")
]);

h函数中嵌套h函数，并把被嵌套的h函数放到一个数组中，这样用于代表子节点。渲染的效果：

h函数原理

h函数用于生成虚拟节点，前面讲到虚拟节点是一个有6个属性的对象，所以h函数的功能十分简单，我们写一个低配版的h函数，它接受三个参数：第一个参数是虚拟节点的标签名；第二个是虚拟节点的数据；第三个是节点的内容或者子节点。我们先创建一个vnode函数，用于创建虚拟节点，十分简单：

// vnode.js
export default function vnode(sel, data, children, text, elm) {
    const key = data === undefined ? undefined : data.key;
    return { sel, data, children, text, elm, key };
}

然后我们创建h函数，h函数通过调用vnode函数生成虚拟节点，在h函数中，需要对传入的参数进行判断：

// h.js

import vnode from "./vnode";

export default function h(sel, data, c) {
    let children = [];
    let text;

    if (arguments.length != 3) {
        throw new Error('h() expects 3 arguments.');
    }
    if (typeof c === 'string' || typeof c === 'number') {
        text = c;
    } else if (Array.isArray(c)) {
        for (let i = 0; i < c.length; i++) {
            if ((typeof c[i] == "object" && c[i].hasOwnProperty("sel"))) {
                children.push(c[i]);
            } else {
                throw new Error('All elements in array must be a vnode.');
            }
        }
    } else if ((typeof c == "object" && c.hasOwnProperty("sel"))) {
        children = [c];
    } else {
        throw new Error('h() expects a string, number, array or vnode as the third argument.')
    }
    return vnode(sel, data, children.length ? children : undefined, text, undefined);
}

在index.js中引入我们自己编写的h函数，测试一下：

import h from "./myVirtualDom/h";

const vnode = h("ul", {}, [
    h("li", {}, "1"),
    h("li", {}, "2"),
    h("li", {}, "3")
]);

console.log(vnode);

结果打印出来，可以看到虚拟节点已经创建成功了。

diff算法

diff算法在虚拟DOM上起作用，用于比较新旧的虚拟DOM，进行最小量更新。

现在有下面两个虚拟节点：

const vnode1 = h("ul", [
    h("li", "1"),
    h("li", "2"),
    h("li", "3")
]);

const vnode2 = h("ul", [
    h("li", "1"),
    h("li", "2"),
    h("li", "3"),
    h("li", "4")
]);

然后在真实DOM上添加一个div和一个按钮，并且在index.js中获取它

1 2	const container = document.getElementById("container"); const btn = document.getElementById("btn");

然后将vnode1上树：

1	patch(container, vnode1);

接着给按钮绑定一个点击事件，点击后将vnode2节点也上树：

1
2
3

btn.onclick = () => {
    patch(vnode1, vnode2);
};

现在页面上已经渲染出了vnode1节点了，然后我们打开开发者工具，改变vnode1中其中一个子元素的内容：

这时点击按钮，将vnode2节点上树：

可以发现不仅第四个li被上树了，而且第一个被而修改的li的内容也没有被修改，说明patch在修改DOM时并没有将原来一整个ul给删掉，而是直接把新的li直接给上树。这就是diff算法的效果，计算出页面的最小量更新。不过diff算法只会进行同层比较，如果节点不同层，即使是相同内容的节点，也会被删掉重新上树。

patch函数

patch函数用于使虚拟节点上树，同时也是diff的入口，patch函数接受两个参数：

旧节点
新节点

diff函数先要判断旧节点是不是一个虚拟节点，如果不是那就把旧节点转化成虚拟节点，然后判断新旧节点是不是同一个节点，如果是那就进行最小量更新，如果不是就直接暴力的删除替换：

根据上面的逻辑，我们可以写出下面的代码：

import vnode from "./vnode";
import createElement from "./createElement";

export default function patch(oldVnode, newVnode) {
    // 先判断oldVnode是不是真实的DOM节点
    if (oldVnode.sel === "" || oldVnode.sel === undefined) {
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
    }

    // 判断oldVnode和newVnode是不是同一个节点
    if (oldVnode.sel == newVnode.sel && oldVnode.key == newVnode.key) {

    }
    // 如果不是,旧直接插入/替换
    else {
        // 获取旧节点
        let elm = oldVnode.elm;
        // 获取旧节点的父节点
        let parent = elm.parentNode;
        // 创建新节点
        let newVnodeElm = createElement(newVnode);
        // 插入新节点
        if (parent && newVnodeElm) {
            parent.insertBefore(newVnodeElm, elm);
        }
        // 删除旧节点
        oldVnode.elm.parentNode.removeChild(oldVnode.elm);
    }
}

其中的createElement函数：

export default function createElement(vnode) {
    var element = document.createElement(vnode.sel);
    // 当vnode的值是字符串,并且没有子节点的时候,直接创建文本节点
    if (vnode.text != "" && (vnode.children == undefined || vnode.children.length == 0)) {
        element.innerText = vnode.text;
    }
    // 当vnode有子节点的时候,递归创建子节点
    else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        let children = vnode.children;
        for (let i = 0; i < children.length; i++) {
            let child = children[i];
            let childElement = createElement(child);
            element.appendChild(childElement);
        }
    }
    vnode.elm = element;
    return element;
}

上面的代码已经完成了新旧节点不是同一个节点的情况了，我们可以测试一下：

import h from './myVirtualDom/h';
import patch from './myVirtualDom/patch';

const container = document.getElementById("container");
const btn = document.getElementById("btn");

const vnode1 = h("p", {}, "Hello World");

const vnode2 = h("ul", {}, [
    h("li", {}, "1"),
    h("li", {}, "2"),

]);


patch(container, vnode1);
btn.onclick = function () {
    patch(vnode1, vnode2);
}

可以看到已经可以成功删除替换节点了：

接下来要处理新旧节点是同一个节点的情况。

新旧节点是同一个节点时

当新旧节点是同一个节点时，又会分出很多种情况，首先要判断新旧节点是不是在内存里的同一个对象，如果是那就什么都不做；如果不是就要再判断新节点有没有text，如果有那还要判断新旧节点的text是否相同，如果相同就什么都不做，如果不同就把旧节点的text替换成新节点的text；如果新节点没有text属性，这就意味着新节点有children属性，那就再判断旧节点有没有children，如果旧节点没有children，那就清空旧节点的text，并把新节点的children添加到新节点上，如果旧节点有children，那就要进行精细化比较了，流程图如下：

我们先不管新旧节点都有children的情况，即精细化比较，先把除了精细化比较外的情况根据上面的逻辑写出来：

import vnode from "./vnode";
import createElement from "./createElement";

export default function patch(oldVnode, newVnode) {
    // 先判断oldVnode是不是真实的DOM节点
    if (oldVnode.sel == "" || oldVnode.sel == undefined) {
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
    }

    // 判断oldVnode和newVnode是不是同一个节点
    if (oldVnode.sel == newVnode.sel && oldVnode.key == newVnode.key) {
        // 判断新旧节点是不是内存里的同一个对象
        if (oldVnode === newVnode) {
            return
        }
        // 判断新节点有没有text属性,如果没有就代表新节点有children
        if (newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length == 0)) {
            // 判断新旧节点的text属性是不是一样,如果一样就不用更新了
            if (newVnode.text != oldVnode.text) {
                oldVnode.elm.innerText = newVnode.text;
            } else {
                return;
            }
        } 
        // 如果新节点有children属性
        else {
            // 判断旧节点有没有children属性,如果有就要进行diff算法
            if (oldVnode.children != undefined && oldVnode.children.length > 0) {

            } 
            // 如果没有就直接清空旧节点的文本内容,然后添加新节点的children
            else {
                oldVnode.elm.innerHTML = "";
                for (let i = 0; i < newVnode.children.length; i++) {
                    dom = createElement(newVnode.children[i]);
                    oldVnode.elm.appendChild(dom);
                }
            }
        }
    }

    // 如果不是,旧直接插入/替换
    else {
        // 获取旧节点
        let elm = oldVnode.elm;
        // 获取旧节点的父节点
        let parent = elm.parentNode;
        // 创建新节点
        let newVnodeElm = createElement(newVnode);
        // 插入新节点
        if (parent && newVnodeElm) {
            parent.insertBefore(newVnodeElm, elm);
        }
        // 删除旧节点
        parent.removeChild(oldVnode.elm);
    }
}

现在已经可以实现处理除了节点是同一个节点且节点都有children的情况了：

import h from './myVirtualDom/h';
import patch from './myVirtualDom/patch';

const container = document.getElementById("container");
const btn = document.getElementById("btn");

const vnode1 = h("ul", {}, [
    h("li", {}, "hello"),
    h("li", {}, "world"),
    h("li", {}, "!!!")
]);

const vnode2 = h("ul", {}, "hello world");


patch(container, vnode1);
btn.onclick = function () {
    patch(vnode1, vnode2);
}

效果：

接下来要实现的是当新旧节点都有children的情况。

diff算法的子节点更新策略

diff算法有四种命中查找节点的策略：

新前与旧前
新后与旧后
新后与旧前（此种情况发生了，需要移动节点，那么新后指向的节点，移动到旧后之后）
新前与旧后（此种情况发生了，需要移动节点，那么新前指向的节点，移动到旧前之前）

每当命中一种策略就不再进行命中判断了，如果所有策略都没有命中，就需要用循环来查找。

1.新前与旧前

如果命中新前与旧前，表示新前与旧前两个节点没有增加没有删除，只是更新，在patchVnode后，把旧前和新前后移一位，然后进行下一个比较。

// 1.新前与旧前
if (sameVnode(newStartVnode, oldStartVnode)) {
    patchVnode(oldStartVnode, newStartVnode);
    oldStartVnode = oldCh[++oldStartIdx];
    newStartVnode = newCh[++newStartIdx];
}

2.新后与旧后

命中新后与旧后，patchVnode后，新后与旧后都要前移一位。

// 2.新后与旧后
else if (sameVnode(newEndVnode, oldEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode);
    oldEndVnode = oldCh[--oldEndIdx];
    newEndVnode = newCh[--newEndIdx];
}

3.新后与旧前

命中新后与旧前，patchVnode后，移动节点，新后指向的节点，移动到旧后之后，新后前移一位，旧前后移一位。

// 3.新后和旧前
else if (sameVnode(newEndVnode, oldStartVnode)) {
    patchVnode(oldStartVnode, newEndVnode);
    parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
    newEndVnode = newCh[--newEndIdx];
    oldStartVnode = oldCh[++oldStartIdx];
}

4.新前与旧后

命中新前与旧后，patchVnode后，新前指向的节点移动到旧前之前，然后新前后移一位，旧后前移一位。

// 4.新前与旧后
else if (sameVnode(newStartVnode, oldEndVnode)) {
    patchVnode(oldEndVnode, newStartVnode);
    parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
    newStartVnode = newCh[++newStartIdx];
    oldEndVnode = oldCh[--oldEndIdx];
}

四种情况都不符合

如果四种条件都不符合，那就在旧节点中循环查找新前节点，如果旧节点中找到了新前节点，那么就把新前节点移动到旧前节点之前，然后把旧节点中找到的节点设置为undefined，然后新前后移一位。

循环结束

循环结束后，还要判断删除/增加节点的情况。

如果新前小于新后，说明新前到新后之间的节点还没有被处理，所以要把这些元素上树。

// 循环结束
// 新前<=新后,说明新节点还有节点未处理,就把新前到新后的节点上树
if (newStartIdx <= newEndIdx) {
    // 如果是在旧节点前面加节点的话,旧后会超过旧前,旧前这时会指向oldCh[0]
    // 如果是在旧节点后面加节点,旧前就会超过旧后,指向一个空的,所以before是null,所以会在末尾加上
    const before = oldCh[oldStartIdx] == null ? null : oldCh[oldStartIdx].elm
    for (let i = newStartIdx; i <= newEndIdx; i++) {
        parentElm.insertBefore(createElement(newCh[i]), before);
    }
}

如果旧前小于旧后，说明有节点要删除

// 旧节点还有节点未处理,就说明有节点要删除
else if (oldStartIdx <= oldEndIdx) {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
        if (oldCh[i] != undefined) {
            parentElm.removeChild(oldCh[i].elm);
        }
    }
}

到这里，diff算法就已经完成了。

import createElement from "./createElement";
import patchVnode from "./patchVnode";

// 判断是不是同一个节点
function sameVnode(a, b) {
    return a.sel == b.sel && a.key == b.key
}

export default function updateChildren(parentElm, oldCh, newCh) {
    // 旧前
    let oldStartIdx = 0;
    // 旧后
    let oldEndIdx = oldCh.length - 1;
    // 新前
    let newStartIdx = 0;
    // 新后
    let newEndIdx = newCh.length - 1;
    // 对应指针的节点
    let oldStartVnode = oldCh[oldStartIdx];
    let oldEndVnode = oldCh[oldEndIdx];
    let newStartVnode = newCh[newStartIdx];
    let newEndVnode = newCh[newEndIdx];

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 首先要略过已经被定义成undefined的项
        if (oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
            oldStartVnode = oldCh[++oldStartIdx];
        } else if (oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
            oldEndVnode = oldCh[--oldEndIdx];
        } else if (newStartVnode == null || newCh[newStartIdx] == undefined) {
            newStartVnode = newCh[++newStartIdx];
        } else if (newEndVnode == null || newCh[newEndIdx] == undefined) {
            newEndVnode = newCh[--newEndIdx];
        }
        // 然后再进行四种命中的判断
        // 1.新前与旧前
        else if (sameVnode(newStartVnode, oldStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        // 2.新后与旧后
        else if (sameVnode(newEndVnode, oldEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        // 3.新后和旧前
        else if (sameVnode(newEndVnode, oldStartVnode)) {
            patchVnode(oldStartVnode, newEndVnode);
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
            newEndVnode = newCh[--newEndIdx];
            oldStartVnode = oldCh[++oldStartIdx];
        }
        // 4.新前与旧后
        else if (sameVnode(newStartVnode, oldEndVnode)) {
            patchVnode(oldEndVnode, newStartVnode);
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
            newStartVnode = newCh[++newStartIdx];
            oldEndVnode = oldCh[--oldEndIdx];
        }
        // 四种都不命中
        else {
            // keyMap是一个映射对象,节点的key是键,节点在oldCh的索引是值
            if (!keyMap) {
                var keyMap = {};
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    var key = oldCh[i].key;
                    if (key != undefined) {
                        keyMap[key] = i;
                    }
                }
            }

            // 找到当前新前节点的key在keyMap中的值
            var idxOnOld = keyMap[newStartVnode.key];

            // 如果是undefined,说明新前是一个全新的节点
            if (idxOnOld == undefined) {
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
            }
            // 如果不是的话,那么就把新前节点移动到旧前节点之前，然后把旧节点中找到的节点设置为undefined，然后新前后移一位
            else {
                var elementToMove = oldCh[idxOnOld];
                patchVnode(elementToMove, newStartVnode);
                parentElm.insertBefore(elementToMove.elm, oldStartVnode.elm);
                oldCh[idxOnOld] = undefined;
            }
            newStartVnode = newCh[++newStartIdx]
        }
    }

    // 循环结束
    // 新前<=新后,说明新节点还有节点未处理,就把新前到新后的节点上树
    if (newStartIdx <= newEndIdx) {
        // 如果是在旧节点前面加节点的话,旧后会超过旧前,旧前这时会指向oldCh[0]
        // 如果是在旧节点后面加节点,旧前就会超过旧后,指向一个空的,所以before是null,所以会在末尾加上
        const before = oldCh[oldStartIdx] == null ? null : oldCh[oldStartIdx].elm

        for (let i = newStartIdx; i <= newEndIdx; i++) {
            parentElm.insertBefore(createElement(newCh[i]), before);
        }
    }
    // 旧节点还有节点未处理,就说明有节点要删除
    else if (oldStartIdx <= oldEndIdx) {
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCh[i] != undefined) {
                parentElm.removeChild(oldCh[i].elm);
            }
        }
    }
}

代码

createElement.js

export default function createElement(vnode) {
    var element = document.createElement(vnode.sel);
    // 当vnode的值是字符串,并且没有子节点的时候,直接创建文本节点
    if (vnode.text != "" && (vnode.children == undefined || vnode.children.length == 0)) {
        element.innerText = vnode.text;
    }
    // 当vnode有子节点的时候,递归创建子节点
    else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        let children = vnode.children;
        for (let i = 0; i < children.length; i++) {
            let child = children[i];
            let childElement = createElement(child);
            element.appendChild(childElement);
        }
    }
    vnode.elm = element;
    return element;
}

h.js

import vnode from "./vnode";

export default function h(sel, data, c) {
    let children = [];
    let text;

    if (arguments.length != 3) {
        throw new Error('h() expects 3 arguments.');
    }
    if (typeof c === 'string' || typeof c === 'number') {
        text = c;
    } else if (Array.isArray(c)) {
        for (let i = 0; i < c.length; i++) {
            if ((typeof c[i] == "object" && c[i].hasOwnProperty("sel"))) {
                children.push(c[i]);
            } else {
                throw new Error('All elements in array must be a vnode.');
            }
        }
    } else if ((typeof c == "object" && c.hasOwnProperty("sel"))) {
        children = [c];
    } else {
        throw new Error('h() expects a string, number, array or vnode as the third argument.')
    }
    return vnode(sel, data, children.length ? children : undefined, text, undefined);
}

patch.js

import vnode from "./vnode";
import createElement from "./createElement";
import patchVnode from "./patchVnode";

export default function patch(oldVnode, newVnode) {
    // 先判断oldVnode是不是真实的DOM节点
    if (oldVnode.sel == "" || oldVnode.sel == undefined) {
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
    }

    // 判断oldVnode和newVnode是不是同一个节点
    if (oldVnode.sel == newVnode.sel && oldVnode.key == newVnode.key) {
        // 判断新旧节点是不是内存里的同一个对象
        patchVnode(oldVnode, newVnode);
    }

    // 如果不是,旧直接插入/替换
    else {
        // 获取旧节点
        let elm = oldVnode.elm;
        // 获取旧节点的父节点
        let parent = elm.parentNode;
        // 创建新节点
        let newVnodeElm = createElement(newVnode);
        // 插入新节点
        if (parent && newVnodeElm) {
            parent.insertBefore(newVnodeElm, elm);
        }
        // 删除旧节点
        parent.removeChild(oldVnode.elm);
    }
}

patchVnode.js

import updateChildren from "./updateChildren";
import createElement from "./createElement";

export default function patchVnode(oldVnode, newVnode) {
    if (oldVnode === newVnode) {
        return
    }
    // 判断新节点有没有text属性,如果没有就代表新节点有children
    if (newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length == 0)) {
        // 判断新旧节点的text属性是不是一样,如果一样就不用更新了
        if (newVnode.text != oldVnode.text) {
            oldVnode.elm.innerText = newVnode.text;
        } else {
            return;
        }
    }
    // 如果新节点有children属性
    else {
        // 判断旧节点有没有children属性,如果都有就要进行diff算法
        if (oldVnode.children != undefined && oldVnode.children.length > 0) {
            updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
        }
        // 如果没有就直接清空旧节点的文本内容,然后添加新节点的children
        else {
            oldVnode.elm.innerHTML = "";
            for (let i = 0; i < newVnode.children.length; i++) {
                var dom = createElement(newVnode.children[i]);
                oldVnode.elm.appendChild(dom);
            }
        }
    }
    oldVnode.children = newVnode.children;
}

updateChildren.js

import createElement from "./createElement";
import patchVnode from "./patchVnode";

// 判断是不是同一个节点
function sameVnode(a, b) {
    return a.sel == b.sel && a.key == b.key
}

export default function updateChildren(parentElm, oldCh, newCh) {
    // 旧前
    let oldStartIdx = 0;
    // 旧后
    let oldEndIdx = oldCh.length - 1;
    // 新前
    let newStartIdx = 0;
    // 新后
    let newEndIdx = newCh.length - 1;
    // 对应指针的节点
    let oldStartVnode = oldCh[oldStartIdx];
    let oldEndVnode = oldCh[oldEndIdx];
    let newStartVnode = newCh[newStartIdx];
    let newEndVnode = newCh[newEndIdx];

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 首先要略过已经被定义成undefined的项
        if (oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
            oldStartVnode = oldCh[++oldStartIdx];
        } else if (oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
            oldEndVnode = oldCh[--oldEndIdx];
        } else if (newStartVnode == null || newCh[newStartIdx] == undefined) {
            newStartVnode = newCh[++newStartIdx];
        } else if (newEndVnode == null || newCh[newEndIdx] == undefined) {
            newEndVnode = newCh[--newEndIdx];
        }
        // 然后再进行四种命中的判断
        // 1.新前与旧前
        else if (sameVnode(newStartVnode, oldStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        // 2.新后与旧后
        else if (sameVnode(newEndVnode, oldEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        // 3.新后和旧前
        else if (sameVnode(newEndVnode, oldStartVnode)) {
            patchVnode(oldStartVnode, newEndVnode);
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
            newEndVnode = newCh[--newEndIdx];
            oldStartVnode = oldCh[++oldStartIdx];
        }
        // 4.新前与旧后
        else if (sameVnode(newStartVnode, oldEndVnode)) {
            patchVnode(oldEndVnode, newStartVnode);
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
            newStartVnode = newCh[++newStartIdx];
            oldEndVnode = oldCh[--oldEndIdx];
        }
        // 四种都不命中
        else {
            // keyMap是一个映射对象,节点的key是键,节点在oldCh的索引是值
            if (!keyMap) {
                var keyMap = {};
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    var key = oldCh[i].key;
                    if (key != undefined) {
                        keyMap[key] = i;
                    }
                }
            }

            // 找到当前新前节点的key在keyMap中的值
            var idxOnOld = keyMap[newStartVnode.key];

            // 如果是undefined,说明新前是一个全新的节点
            if (idxOnOld == undefined) {
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
            }
            // 如果不是的话,那么就把新前节点移动到旧前节点之前，然后把旧节点中找到的节点设置为undefined，然后新前后移一位
            else {
                var elementToMove = oldCh[idxOnOld];
                patchVnode(elementToMove, newStartVnode);
                parentElm.insertBefore(elementToMove.elm, oldStartVnode.elm);
                oldCh[idxOnOld] = undefined;
            }
            newStartVnode = newCh[++newStartIdx]
        }
    }

    // 循环结束
    // 新前<=新后,说明新节点还有节点未处理,就把新前到新后的节点上树
    if (newStartIdx <= newEndIdx) {
        // 如果是在旧节点前面加节点的话,旧后会超过旧前,旧前这时会指向oldCh[0]
        // 如果是在旧节点后面加节点,旧前就会超过旧后,指向一个空的,所以before是null,所以会在末尾加上
        const before = oldCh[oldStartIdx] == null ? null : oldCh[oldStartIdx].elm

        for (let i = newStartIdx; i <= newEndIdx; i++) {
            parentElm.insertBefore(createElement(newCh[i]), before);
        }
    }
    // 旧节点还有节点未处理,就说明有节点要删除
    else if (oldStartIdx <= oldEndIdx) {
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCh[i] != undefined) {
                parentElm.removeChild(oldCh[i].elm);
            }
        }
    }
}

vnode.js

export default function vnode(sel, data, children, text, elm) {
    const key = data === undefined ? undefined : data.key;
    return { sel, data, children, text, elm, key };
}