侧边栏

VNode与递归diff

发布于 | 分类于 源码分析/diff算法

在工作中接触Vue、React大概有两三年了，最近一直在学习相关的技术原理，打算整理学习心得。本文深入研究虚拟DOMVNode相关的技术实现，了解前端框架的基础。

本文包含大量的示例代码，主要实现

  • createVNode，创建vnode
  • VNode2DOM，将vnode转换为DOM节点
  • VNode2HTML，将vnode转换为HTML字符串
  • diff算法，可分为递归实现（Vue）和循环实现（React Fiber），由于篇幅和结构的问题，本文主要实现递归diff，关于fiber相关实现，将在下一篇博客中进行

本系列文章列表如下

排在后面文章内会大量采用前面文章中的一些概念和代码实现，如createVNode、diffChildren、doPatch等方法，因此建议逐篇阅读，避免给读者造成困惑。本文相关示例代码均放在github上，如果发现问题，烦请指正。

vnode ​

我们知道vnode实际上就是一个用于描述UI的对象，包含一些基本属性，我们通过type描述需要渲染的标签，通过prpos描述样式、事件等属性，通过children描述子节点，最简单的实现如下所示

js
function createVNode(type, props = {}, children = []) {
    return {
        type,
        props,
        children
    }
}

如果要描述下面这个html结构的简单视图

html
<div>
    <h1>hello title</h1>
    <ul class="list-simple">
        <li>1</li>
        <li>2</li>
        <li>3</li>
    </ul>
</div>

使用createVNode，构建一颗vnode树，

js
let data = {
    title: 'hello vnode',
    list: [1, 2, 3]
}
createRoot(data)
function createRoot(data) {
    let listItem = data.list.map(item => {
        return createVNode('li', {
            onClick() {
                console.log(item)
            }
        }, [item])
    })
    let list = createVNode('ul', {
        class: 'list-simple',
    }, listItem)

    let title = createVNode('h1', {}, [data.title])
    let root = createVNode('div', {}, [title, list])
    return root
}

可以看见VNode树与DOM树是一一对应的，相比而言，vnode包含的属性要比一个真实DOM的属性少得多。在后面的实现中，我们会向VNode上添加一些额外的的属性。

此处需要注意，对于children而言，其元素的类型有两种：可以是一个VNode，也可以是原始字面量（视为文本节点）。为了统一处理文本节点和元素节点，我们可以在createVNode中对文本节点进行特殊处理

js
const TEXT_NODE = Symbol('__text_node')
// 暴露一个是否为文本节点的接口
function isTextNode(type) {
    return type === TEXT_NODE
}
function createVNode(type, props = {}, children = []) {
    let vnode = {
        type,
        props,
    }
    vnode.children = children.map((child, index) => {
        // 将无type的节点处理为文本节点，并将其值保存为nodeValue
        if (!child.type) {
            child = {
                type: TEXT_NODE,
                props: {
                    nodeValue: child
                },
                children: []
            }
        }
        return child
    })
    return vnode
}

这样每个VNode都可以包含了统一的属性。

通过VNode渲染视图 ​

当我们将整个UI通过VNode树描述之后，我们还需要将其渲染为真实的DOM节点，有两个实现思路

  • 直接将vnode映射为DOM节点，通过appendChild等方式渲染到页面上
  • 将vnode树解析成HTML字符串，结合innerHTML渲染到页面上

VNode2DOM ​

根据vnode.type，我们可以调用DOM接口实例化真实DOM，然后根据vnode.props设置相关DOM属性，最后根据vnode.children渲染子节点，这个过程最直观的方法是使用递归。

由于需要正确将子节点插入父节点中，因此需要提前构建父节点，方便起见此处使用先序遍历。

js
function VNode2DOM(root, parentDOM) {
    let { type, props, children } = root

    // 将当前vnode渲染为对应的DOM节点
    let dom
    if (isTextNode(type)) {
        dom = document.createTextNode(root.props.nodeValue)
    } else {
        dom = document.createElement(type)
        for (var key in props) {
            setAttribute(dom, key, props[key])
        }
    }
    // 将子节点也转换为dom节点
    Array.isArray(children) && children.forEach(child => {
        VNode2DOM(child, dom)
    })
    // 将当前节点插入节点
    if (parentDOM) {
        parentDOM.appendChild(dom)
    }
    root.$el = dom

    return dom
}

// 向dom元素增加属性
function setAttribute(el, prop, val) {
    // 处理事件
    let isEvent = prop.indexOf('on') === 0
    if (isEvent) {
        let eventName = prop.slice(2).toLowerCase()
        el.addEventListener(eventName, val)
    } else {
        el.setAttribute(prop, val)
    }
}

测试一下，可以看见页面渲染了真实的DOM节点，同时正确添加了props属性

js
let root = createRoot({
    title: 'hello vnode',
    list: [1, 2, 3]
})
let dom = VNode2DOM(root, null)
document.body.appendChild(dom)

VNode2HTML ​

除了渲染DOM节点，我们也可以直接拼接HTML字符串（甚至在某些场景下，如SSR，我们需要的反而仅仅是HTML字符串）。同样地，我们可以使用递归来实现。

由于构建一个vnode的html片段需要知道其全部子节点的html片段，因此此处使用后序遍历。

js
function VNode2HTML(root) {
    let { type, props, children } = root

    let sub = '' // 获取子节点渲染的html片段
    Array.isArray(children) && children.forEach(child => {
        sub += VNode2HTML(child)
    })

    let el = '' // 当前节点渲染的html片段
    if (type) {
        let attrs = ''
        for (var key in props) {
            attrs += getAttr(key, props[key])
        }
        el += `<${type}${attrs}>${sub}</${type}>` // 将子节点插入当前节点
    } else {
        el += root // 纯文本节点则直接返回
    }

    return el
    function getAttr(prop, val) {
        // 渲染HTML，假设我们不需要 事件 等props
        let isEvent = prop.indexOf('on') === 0
        return isEvent ? '' : ` ${prop}="${val}"`
    }
}

测试一下

js
let html = VNode2HTML(root)
console.log(html)
// 输出结果为
// <div><h1>hello vnode</h1><ul class="list-simple"><li>1</li><li>2</li><li>3</li></ul></div>
app2.innerHTML = html // 也可以渲染视图，尽管貌似少了注册事件等逻辑

可以看见，VNode2DOM和VNode2HTML都可以达到将VNode描述的UI渲染出来的目的。VNode2HTML主要用于服务端渲染的场景，而VNode2DOM可以在浏览器端直接通过DOM接口渲染，更加直观且灵活，本文主要研究浏览器环境中的VNode。关于SSR的相关知识，我会在后面的文章中继续实现（本次学习框架原理的一个主要目的就是更新博客的同构渲染）。

视图更新diff ​

当vnode发生变化时，我们可以通过重新渲染根节点来更新视图。但是，当vnode结构比较庞大时，我们就不得不考虑全部重新渲染所带来的性能问题。

由于我们在初始化的时候构建了全部的DOM节点，在vnode发生变化时的理想状态是：我们只更新发生了变化的那些vnode，其余未变化的vnode，我们没必要又重新构建一次。

因此现在问题转化为：如何找到那些发生了变化的vnode？解决这个问题的算法就被称为diff：从根节点开始，依次对比并更新新旧vnode树上的节点，并尽可能地复用DOM，避免额外开销。

diff算法 ​

为了性能和效率的均衡，diff算法遵循下面约定

  • 只对比同一层级的节点
  • 不同type的节点对应类型的DOM，需要完全更新当前节点及其子节点树
  • 相同type的节点则检测props是否变化，只更新发生了变化的属性，如果props未变化，则不进行任何更改

基于这些约定，对于vnode树中的某个节点而言，可能发生的变化有：删除、新增、更新节点属性，基于此我们来实现diff算法。整个diff算法分为两步，

  • 首先遍历vnode树，收集变化的节点，
  • 然后将收集的变化更新到视图上

diff

与前面的思路差不多，我们可以通过递归实现diff

js
// 定义节点可能发生的变化
const [REMOVE, REPLACE, INSERT, UPDATE] = [0, 1, 2, 3];

// 对比新旧节点，通过patches收集变化
function diff(oldNode, newNode, patches = []) {
    if (!newNode) {
        // 旧节点及其子节点都将移除
        patches.push({ type: REMOVE, oldNode })
    } else if (!oldNode) {
        // 当前节点与其子节点都将插入
        patches.push({ type: INSERT, newNode })
        diffChildren([], newNode.children, patches);
    } else if (oldNode.type !== newNode.type) {
        // 使用新节点替换旧节点
        patches.push({ type: REPLACE, oldNode, newNode })
        // 新节点的字节点都需要插入
        diffChildren([], newNode.children, patches);
    } else {
        // 如果存在有变化的属性，则使用新节点的属性更新旧节点
        let attrs = diffAttr(oldNode.props, newNode.props) // 发生变化的属性
        if (Object.keys(attrs).length > 0) {
            patches.push({ type: UPDATE, oldNode, newNode, attrs })
        }
        newNode.$el = oldNode.$el // 直接复用旧节点
        // 继续比较子节点
        diffChildren(oldNode.children, newNode.children, patches);
    }
    // 收集变化
    return patches
}

function diffAttr(oldAttrs, newAttrs) {
    let attrs = {};
    // 判断老的属性中和新的属性的关系
    for (let key in oldAttrs) {
        if (oldAttrs[key] !== newAttrs[key]) {
            attrs[key] = newAttrs[key]; // 有可能还是undefined
        }
    }
    for (let key in newAttrs) {
        // 老节点没有新节点的属性
        if (!oldAttrs.hasOwnProperty(key)) {
            attrs[key] = newAttrs[key];
        }
    }
    return attrs;
}
// 按顺序对比子节点，在后面我们会实现其他方式的新旧节点对比方式
function diffChildren(oldChildren, newChildren, patches) {
    let count = 0;
    // 比较新旧子树的节点
    if (oldChildren && oldChildren.length) {
        oldChildren.forEach((child, index) => {
            count++;
            diff(child, (newChildren && newChildren[index]) || null, patches);
        });
    }

    // 如果还有未比较的新节点，继续进行diff将其标记为INSERT
    if (newChildren && newChildren.length) {
        while (count < newChildren.length) {
            diff(null, newChildren[count++], patches);
        }
    }
}

使用方式大致如下，对比两个根节点

js
let root = createRoot({
    title: 'change title',
    list: [1,2,3]
})
let root2 = createRoot({
    title: 'hello vnode',
    list: [3, 2]
})

var patches = diff(root, root2)
console.log(patches) // 可以看见收集到的变化的节点

doPatch

在doPatch阶段，主要是将收集的变化更新到视图上

js
// 将变化更新到视图上
function doPatch(patches) {
    // 特定类型的变化，需要重新生成DOM节点，由于无法完全保证patches的顺序，因此在此步骤生成vnode.$el
    const beforeCommit = {
        [REPLACE](oldNode, newNode) {
            newNode.$el = createDOM(newNode)
        },
        [UPDATE](oldNode, newNode) {
            // 复用旧的DOM节点，只需要更新必要的属性即可
            newNode.$el = oldNode.$el
        },
        [INSERT](oldNode, newNode) {
            newNode.$el = createDOM(newNode)
        },
    };
    // 执行此步骤时所有vnode.$el都已准备就绪
    const commit = {
        [REMOVE](oldNode, newNode) {
            oldNode.$parent.$el.removeChild(oldNode.$el)
        },
        [REPLACE](oldNode, newNode) {
            let parent = oldNode.$parent.$el
            let old = oldNode.$el
            let el = newNode.$el

            // 新插入的节点上添加属性
            setAttributes(newNode, newNode.props)
            parent.insertBefore(el, old);
            parent.removeChild(old);
        },
        [UPDATE](oldNode, newNode) {
            // 只需要更更新diff阶段收集到的需要变化的属性
            setAttributes(newNode, newNode.attrs)
            // 将newNode移动到新的位置，问题在于前面的节点移动后，会影响后面节点的顺序
        },
        [INSERT](oldNode, newNode) {
            // 新插入的节点上添加属性
            setAttributes(newNode, newNode.props)
            insertDOM(newNode)
        },
    }
    // 首先对处理需要重新创建的DOM节点
    patches.forEach(patch => {
        const { type, oldNode, newNode } = patch
        let handler = beforeCommit[type];
        handler && handler(oldNode, newNode);
    })

    // 将每个变化更新到真实的视图上
    patches.forEach(patch => {
        const { type, oldNode, newNode } = patch
        let handler = commit[type];
        handler && handler(oldNode, newNode);
    })
}
// 创建节点
function createDOM(node) {
    let type = node.type
    return isTextNode(type) ?
        document.createTextNode(node.props.nodeValue) :
        document.createElement(type)
}
// 将节点插入父节点，如果节点存在父节点中，则调用insertBefore执行的是移动操作而不是复制操作，因此也可以用来进行MOVE操作
function insertDOM(newNode) {
    let parent = newNode.$parent.$el
    let children = parent.children

    let el = newNode.$el
    let after = children[newNode.index]

    after ? parent.insertBefore(el, after) : parent.appendChild(el)
}
// 设置DOM节点属性
function setAttributes(vnode, attrs) {
    if (isTextNode(vnode.type)) {
        vnode.$el.nodeValue = vnode.props.nodeValue
    } else {
        let el = vnode.$el
        attrs && Object.keys(attrs).forEach(key => {
            setAttribute(el, key, attrs[key])
        });
    }
}

可以看见在doPatch操作中，我们需要获取vnode的DOM实例和其父节点的引用，因此我们为vnode增加一个$el的属性，引用根据该vnode实例化的真实DOM节点，初始化时为null，在VNode2DOM时可以更新其值

js
function createVNode(type, props = {}, children = []) {
    let vnode = {
        // ...
        type,props
        $el: null
    }
    vnode.children = children.map(child => {
        child.$parent = vnode // 保存对父节点的引用
        return child
    })
    return vnode
}
function VNode2DOM(root, parentDOM) {
    // ...
    root.$el = dom // 在vnode的DOM实例化后更新vnode.$el
    return dom
}

这样在初始化视图后，后续更新时，我们会得到新的vnode树，先进行diff收集patches，然后将patches更新到页面上

js
let root = createRoot({
    title: 'change title',
    list: [1,2,3]
})
let dom = VNode2DOM(root) // 此时旧节点的$el已保持对于DOM实例的引用
document.body.appendChild(dom) // 初始化完成
// 数据发生变化，获取新的vnode树
let root2 = createRoot({
    title: 'hello vnode',
    list: [3, 2]
})

var patches = diff(root, root2) // 收集变化的节点
doPatches(patches) // 更新视图

代码优化：抛弃VNode2DOM，合并初始化和更新 ​

在上面的例子中，我们按照下面的流程实现应用

  • 首先使用createRoot(data)初始化根节点root，并调用VNode2DOM(root)将vnode渲染为DOM节点
  • 当data变化时，重新调用createRoot(data2)获取新的根节点root2，并通过diff(root, root2)获取新旧节点树中的变化patchs，最后通过doPatch(patchs)将变化更新在视图上

整个过程看起来比较简明，但可以发现VNode2DOM与doPatch中的初始化DOM节点的逻辑是重复的。换个思路，初始化的时候，可以看做是新旧点与一个为null的旧节点进行diff操作。

因此，我们现在可以直接跳过VNode2DOM，将初始化与diff的过程放在一起。

js
root = createRoot({
    title: 'hello vnode',
    list: [1, 2, 3]
})
let patches = diff(null, root)
root.$parent = {
    $el: app
}
doPatch(patches)

// 视图更新时与上面相同的例子相同
// let patches =diff(root, root2) 
// doPatch(patches)

就这样，我们只需要为根节点手动添加一个root.$parent.$el属性用于挂载，除此之外就不再需要VNode2DOM这个方法（尽管这个方法是了解vnode映射为真实DOM最简单直观的实现了）

diff算法优化：尽可能对比type相同的节点 ​

在上面的diff算法中，我们在对比新旧节点时，是通过相同的索引值在父元素中的进行对比的，当两个节点的类型不相同时，会标记为REPLACE，在patch时会移除旧节点，同时在原位置插入节点。

考虑下面问题，当子节点列表从[h1, ul]变成了[h1,p,ul]时，我们的算法会将新节点中的p标记为REPLACE，将ul标记为INSERT，这显然不能达到性能上的优化，最理想的状态是直接在第二个位置插入p标签即可。

这个问题可以转换为：在某些时刻，我们不能简单地通过默认的索引值来查找并对比新旧节点，反之，我们应该尽可能去对比子节点中vnode.type相同的节点。

（感谢我们将整个diff过程分成了diff和doPatch两个阶段，我们现在只需要修改diffChildren方法中的一些逻辑即可~）

以下面例子来说，

js
// 这里列举的abcde都是指不同的type
oldChildren = [a,b,c,d] 
newChildren = [b,e,d,c]
// 为了尽可能地复用旧节点，理想状态是复用b、d，删除a，在指定位置插入d之前插入e，将c移动到d之后，整个操作共计3步。

// 我们上面的具体例子中[h1, ul] -> [h1, p, ul]
// 理想状态应该是直接将p插入ul节点之前，只需要一步操作

因此我们重新实现一个diffChildren方法，并将之前的diffChildren方法重新命名为diffChildrenByIndex

js
// 尽可能地与相同type的节点进行比较
// 在这种逻辑下，会尽可能地按顺序复用子节点中类型相同的节点
// 整个算法的时间复杂度为O(n)，空间复杂度也为O(n)
// 注意在这种策略下不会再产生REPLACE类型的patch，而是直接将REPLACE拆分成了INSERT新节点和REMOVE旧节点的两个patch，对于doPatch阶段没有影响
function diffChildrenByType(oldChildren, newChildren, patches) {
    let map = {}
    oldChildren.forEach(child => {
        let { type } = child
        if (!map[type]) map[type] = []
        map[type].push(child)
    })
    for (let i = 0; i < newChildren.length; ++i) {
        let cur = newChildren[i]
        // 按顺序找到第一个类型相同的元素并复用，这种方式存在的问题是当两个类型相同的节点仅仅是调换位置，他们也会进行UPDATE
        // 针对这个问题，可以进一步判断，找到类型相同且props和children最接近的元素，从而避免上面的问题，但是这样做会增加时间复杂度
        // 因此，对于类型相同且顺序可能发生变化的节点，我们需要额外的手段来检测重复的节点，一种方法是使用语义化的标签，减少类型相同的标签，二是使用key
        if (map[cur.type] && map[cur.type].length) {
            let old = map[cur.type].shift()
            diff(old, cur, patches)
        } else {
            // 由于部分操作如INSERT依赖最终children的顺序，因此需要保证patches的顺序
            // 此处对于同一层级的节点而言，在前面的节点会先进入patches队列，因此会先插入
            diff(null, cur, patches)
        }
    }
    // 剩余未被使用的旧节点，将其移除
    Object.keys(map).forEach(type => {
        let arr = map[type]
        arr.forEach(old => {
            diff(old, null, patches)
        })
    })
}

测试一下

js
function diffChildren(oldChildren, newChildren, patches){
    // diffChildrenByIndex(oldChildren, newChildren, patches) // 根据索引值查找并diff节点
    diffChildrenByType(oldChildren, newChildren, patches) // 根据type查找并diff节点
}
// 变化[h1, ul] -> [h1, p, ul]

经过测试可以发现，在上面的例子中

  • diffChildrenByType会只会产生2个INSERT类型的patch(一个li节点和一个文本节点)，
  • diffChildrenByIndex1个REPLACE和8个INSERTpatch，（尽管这个测试用例有点极端，会重新构建整个ul子节点）。

使用key：避免原地复用元素节点 ​

在diffChildrenByType中我们提到了相同类型元素顺序调换会导致两个元素都进行UPDATE的问题，我们可以在创建节点时手动为节点添加一个唯一标识，从而保证在不同的顺序中也能快速找到该节点，按照行规我们将这个唯一标识命名为key。

接下来对craeteVNode和diffChildrenByType稍作修改，优先根据对比key相同的节点，然后再对比类型相同的节点

js
// 在diffChildrenByType的基础上增加了根据key查找旧节点的逻辑
// 根据type和key来进行判断，避免同类型元素顺序变化导致的不必要更新
function diffChildrenByKey(oldChildren, newChildren, patches) {
    newChildren = newChildren.slice() // 复制一份children，避免影响父节点的children属性
    // 找到新节点列表中带key的节点
    let keyMap = {}
    newChildren.forEach((child, index) => {
        let { key } = child
        // 只有携带key属性的会参与同key节点的比较
        if (key !== undefined) {
            if (keyMap[key]) {
                console.warn(`请保证${key}的唯一`, child)
            } else {
                keyMap[key] = {
                    vnode: child,
                    index
                }
            }
        }
    })

    // 在遍历旧列表时，先比较类型与key均相同的节点，如果新节点中不存在key相同的节点，才会将旧节点保存起来
    let typeMap = {}
    oldChildren.forEach(child => {
        let { type, key } = child
        // 先比较类型与key均相同的节点
        let { vnode, index } = (keyMap[key] || {})
        if (vnode && vnode.type === type) {
            newChildren[index] = null // 该节点已被比较，需要弹出
            // newChildren.splice(index, 1) // 该节点已被比较，需要弹出
            delete keyMap[key]
            diff(child, vnode, patches)
        } else {
            // 将剩余的节点保存起来，与剩余的新节点进行比较
            if (!typeMap[type]) typeMap[type] = []
            typeMap[type].push(child)
        }
    })

    // 剩下的节点处理与diffChildrenByType相同，此时key相同的节点已被比较
    for (let i = 0; i < newChildren.length; ++i) {
        let cur = newChildren[i]
        if (!cur) continue; // 已在在前面与此时key相同的节点进行比较
        // ... 找到一个类型相同的节点进行比较
    }
    // ... 剩余未被使用的旧节点，将其移除
}

同时增加一种MOVE的patch类型，在diff方法中，如果新旧节点在父节点中的位置不一致，则会提交一个patch，此外我们需要在vnode上增加一个index属性，用于记录新旧节点在父节点中的位置

js
function createVNode(type, props = {}, children = []) {
    vnode.key = props.key  // 增加key
    vnode.children = children.map((child, index) => {
        // ...
        child.index = index // 增加index, 记录在该节点的索引值
        return child
    })
}

const [REMOVE, REPLACE, INSERT, UPDATE, MOVE] = [0, 1, 2, 3, 5]; // 增加MOVE类型的patch
function diff(oldNode, newNode, patches = []) {
    // 新旧节点类型相同但索引值不一致，则表示节点复用，节点需要移动位置，进行MOVE
    if (oldNode.index !== newNode.index) {
        patches.push({ type: MOVE, oldNode, newNode })
    }
    return patches
}

最后，在doPatch阶段需要为MOVE类型的节点增加DOM更新处理方法

js
// 将节点插入父节点，如果节点存在父节点中，则调用insertBefore执行的是移动操作而不是复制操作，
// 因此也可以用来进行MOVE操作
function insertDOM(newNode) {
    let parent = newNode.$parent.$el
    let children = parent.children

    let el = newNode.$el
    let after = children[newNode.index]

    after ? parent.insertBefore(el, after) : parent.appendChild(el)
}
// 需要MOVE的元素按照新的索引值排序，保证排在前面的先进行移动位置的操作
patches
    .filter(patch => patch.type === MOVE)
    .sort((a, b) => a.index - b.index)
    .forEach(patch => {
        const { oldNode, newNode } = patch
        insertDOM(newNode)
    })

测试一下

js
function testKey() {
    let list1 = createList([1, 2, 3], true) // true 使用元素值作为key
    let patches = diff(null, list1)
    list1.$parent = {
        $el: app
    }
    doPatch(patches)
    btn.onclick = function () {
        let list2 = createList([4, 3, 2, 1], true)
        let patches = diff(list1, list2)
        console.log(patches)  // 查看收集的变化
        doPatch(patches)
    }
}

// 测试三种diff策略的影响
function diffChildren(oldChildren, newChildren, patches) {
    // diffChildrenByIndex(oldChildren, newChildren, patches)
    // diffChildrenByType(oldChildren, newChildren, patches)
    diffChildrenByKey(oldChildren, newChildren, patches)
}

同样进行上面的操作

  • diffChildrenByKey包含3个MOVE操作（1、2、3节点不会创建新的文本节点，而是移动li节点），两个INSERT操作（一个li节点和一个文本节点）
  • diffChildrenByType包含3个UPDATE操作（更新前三个文本节点），两个INSERT操作
  • diffChildrenByIndex，由于循环节点的类型一致，导致该方法的diff结果与diffChildrenByType相同

可以看见，增加key之后，会尽可能地复用元素节点并移动位置，而不是在原地复用元素节点并更新文本节点（移动位置在性能上并不见得优于原地更新文本节点），因此

使用key并不一定能带来性能上的提升，而是为了避免原地复用元素节点带来的影响。

小结 ​

本文从构造vnode节点开始，

  • 首先了解如何通过vnode描述一段HTML结构
  • 然后通过VNode2DOM和VNode2HTML了解了如何将vnode树渲染为真实的DOM节点
  • 接着考虑视图更新的情况，实现diff算法，主要实现diff（收集变化）和doPatch（将变化更新到页面上）两个方法，并合并了初始化和更新逻辑，移除了VNode2DOM
  • 然后优化同层新旧子节点之间的查找和对比，尽可能地复用type相同的DOM节点，并发现了顺序发生变化的同type节点存在的问题，
  • 最后引入了key进一步更新同层新旧子节点的查找和对比，对于key相同的节点，优先使用MOVE操作移动节点，避免原地复用元素节点

本文参考了Vue源码中的一些实现，但是Vue中使用多个游标进行diff的方式个人感觉不是很清楚明了，因此按照自己的理解实现了上面的几种diff策略

经过上面的步骤，大概能了解vnode与diff算法的一些核心思想。

由于上面的diff是递归实现的，很难被临时中断，在某个时刻又恢复至原来调用的地方，因此当vnode树过于复杂时，将长时间占用JavaScript执行线程，导致浏览器卡死。在下一篇文章中，将参考React中的 fiber，按循环实现diff。

感谢阅读，九月份经历了一次很失败的面试，感觉过去挺长一段时间，自己的学习态度和方法都出现了一些问题，总结起来就是：学而不思则罔，学习的时候，应该多思考才行。由于本人水平有限，文中出现的错误，烦请指正。

#Vue #React #diff

你要请我喝一杯奶茶？

版权声明：自由转载-非商用-保持署名和原文链接。

本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。