vuejs 设计与实现 - 双端diff算法

这篇具有很好参考价值的文章主要介绍了vuejs 设计与实现 - 双端diff算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

我们介绍了简单 Diff 算法的实现原理。简单 Diff 算法利用虚拟节点的 key 属性,尽可能地复用 DOM元素,并通过移动 DOM的方式来完成更新,从而减少不断地创建和销毁 DOM 元素带来的性能开销。但是,简单 Diff 算法仍然存在很多缺陷,这些缺陷可以通过本章将要介绍的双端 Diff 算法解决。

1.双端比较的原理

双端 Diff 算法是一种同时对新旧两组子节点的两个端点进行比较的算法。因此,我们需要四个索引值,分别指向新旧两组子节点的端点.如下图:

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

双端比较的方式:

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
在双端比较中,每一轮比较都分为四个步骤,如图 10-5 中的连线所示。
比较的过程如下描述:
第一步: 比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的第一个子节点 p-4,看看它们是否相同。由于两者的key 值不同,因此不相同,不可复用,于是什么都不做。

第二步:比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的最后一个子节点 p-3,看看它们是否相同。由于两者的 key 值不同,因此不相同,不可复用,于是什么都不做。

第三步:比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的最后一个子节点 p-3,看看它们是否相同。由于两者的 key 值不同,因此不相同,不可复用,于是什么都不做。

第四步:比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的第一个子节点 p-4。由于它们的 key 值相同,因此可以进行 DOM 复用。
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

 function patchChildren(n1, n2, container) {
   patchKeyedChildren(n1, n2, container)
}

function patchKeyedChildren(n1, n2, container){
   const oldChildren = n1.children 
   const newChildren = n2.children

   // 四个索引值
   let oldStartIdx = 0
   let oldEndIdx = oldChildren.length - 1

   let newStartIdx = 0
   let newEndIdx = newChildren.length - 1

   // 四个索引指向的 vnode 节点
   let oldStartVNode = oldChildren[oldStartIdx]
   let oldEndVNode = oldChildren[oldEndIdx]

   let newStartVNode = newChildren[newStartIdx]
   let newEndVNode = newChildren[newEndIdx]


   if (oldStartVNode.key === newStartVNode.key) {
        // 步骤一:oldStartVNode 和 newStartVNode 比较

    } else if (oldEndVNode.key === newEndVNode.key) {
        // 步骤二:oldEndVNode 和 newEndVNode 比较
     
    } else if(oldStartVNode.key === newEndVNode.key) {
        // 步骤三:oldStartVNode 和 newEndVNode 比较
       


    } else if (oldEndVNode.key === newStartVNode.key) {
        // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
        // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
        // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。


        // 第四步:oldEndVNode 和 newStartVNode 比较
        // 仍然需要调用 patch 函数进行打补丁
        patch(oldEndVNode, newStartVNode, container)

        // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
        insert(oldEndVNode.el, container, oldStartVNode.el)
        
        // 移动 DOM 完成后,更新索引值,指向下一个位置
        oldEndVNode = oldChildren[--oldEndIdx]
        newStartVNode = newChildren[++newStartIdx]
    }


}

第一轮 DOM 移动操作完成 态状的点节后,新旧两组子节点以及真实 DOM 节点的状态如下:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

此时,真实 DOM 节点顺序为 p-4、p-1、p-2、p-3,这与新的 一组子节点顺序不一致。这是因为diff算法还没结束,还需要进行下一轮更新。因此,我们需要将更新逻辑封装到一个 while 循环中,

function patchChildren(n1, n2, container) {
            patchKeyedChildren(n1, n2, container)
        }

        function patchKeyedChildren(n1, n2, container){
            const oldChildren = n1.children 
            const newChildren = n2.children

            // 四个索引值
            let oldStartIdx = 0
            let oldEndIdx = oldChildren.length - 1

            let newStartIdx = 0
            let newEndIdx = newChildren.length - 1

            // 四个索引指向的 vnode 节点
            let oldStartVNode = oldChildren[oldStartIdx]
            let oldEndVNode = oldChildren[oldEndIdx]

            let newStartVNode = newChildren[newStartIdx]
            let newEndVNode = newChildren[newEndIdx]

 +           while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                 
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
                   

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }
 +           }


        }

由于在每一轮更新完成之后,紧接着都会更新四个索引中与当前更新轮次相关联的索引,所以整个 while 循环执行的条件是:头部索引值要小于等于尾部索引值。

在第一轮更新结束后循环条件仍然成立,因此需要进行下一轮的比较:

第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-2,看看它们是否相同。由于两者的 key 值不
同,不可复用,所以什么都不做。

这里,我们使用了新的名词: 。它指的是头部索引oldStartIdx 和 newStartIdx 所指向的节点。

第二步:比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3,两者的 key 值相同,可以复用。另外,由于两者都处于尾部,因此不需要对真实 DOM 进行移动操作,只需要打补丁即可:

">
function patchChildren(n1, n2, container) {
            patchKeyedChildren(n1, n2, container)
        }

        function patchKeyedChildren(n1, n2, container){
            const oldChildren = n1.children 
            const newChildren = n2.children

            // 四个索引值
            let oldStartIdx = 0
            let oldEndIdx = oldChildren.length - 1

            let newStartIdx = 0
            let newEndIdx = newChildren.length - 1

            // 四个索引指向的 vnode 节点
            let oldStartVNode = oldChildren[oldStartIdx]
            let oldEndVNode = oldChildren[oldEndIdx]

            let newStartVNode = newChildren[newStartIdx]
            let newEndVNode = newChildren[newEndIdx]

            while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
      +              patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
       +             oldEndVNode = oldChildren[--oldEndIdx]
       +             newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }
            }


        }

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
真实 DOM 的顺序相比上一轮没有变化,因为在这一轮的比较中没有对 DOM 节点进行移动,只是对 p-3 节点打补丁。接下来,我们再根据图 上图所示的状态执行下一轮的比较:

第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-2,看看它们是否相同。由于两者的 key 值不
同,不可复用,因此什么都不做。

第二步:比较旧的一组子节点中的尾部节点 p-2 与新的一组子节点中的尾部节点 p-1,看看它们是否相同,由于两者的 key 值不
同,不可复用,因此什么都不做。

第三步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-1。两者的 key 值相同,可以复用。

在第三步的比较中,我们找到了相同的节点,这说明: p-1原本是头部节点,但是在新的顺序中,它变成了尾部节点。因此,我们需要将节点p-1对应的真实 DOM 移动到旧的一组子节点的尾部节点 p-2 所对应的真实 DOM 后面,同时还需要更新相应的索引到下一个位置,如图 下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

function patchChildren(n1, n2, container) {
            patchKeyedChildren(n1, n2, container)
        }

        function patchKeyedChildren(n1, n2, container){
            const oldChildren = n1.children 
            const newChildren = n2.children

            // 四个索引值
            let oldStartIdx = 0
            let oldEndIdx = oldChildren.length - 1

            let newStartIdx = 0
            let newEndIdx = newChildren.length - 1

            // 四个索引指向的 vnode 节点
            let oldStartVNode = oldChildren[oldStartIdx]
            let oldEndVNode = oldChildren[oldEndIdx]

            let newStartVNode = newChildren[newStartIdx]
            let newEndVNode = newChildren[newEndIdx]

            while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
                    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
                   
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                    patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
       +             patch(oldStartVNode, newEndVNode, container)
       +             insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

       +             oldStartVNode = oldChildren[++oldStartIdx]
       +             newEndVNode = newChildren[--newEndIdx]

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }
            }


        }

下一轮循环:
第一步:比较旧的一组子节点中的头部节点 p-2 与新的一组 子节点中的头部节点 p-2。发现两者 key 值相同,可以复用。但 两者在新旧两组子节点中都是头部节点,因此不需要移动,只需 要调用 patch 函数进行打补丁即可。

function patchChildren(n1, n2, container) {
            patchKeyedChildren(n1, n2, container)
        }

        function patchKeyedChildren(n1, n2, container){
            const oldChildren = n1.children 
            const newChildren = n2.children

            // 四个索引值
            let oldStartIdx = 0
            let oldEndIdx = oldChildren.length - 1

            let newStartIdx = 0
            let newEndIdx = newChildren.length - 1

            // 四个索引指向的 vnode 节点
            let oldStartVNode = oldChildren[oldStartIdx]
            let oldEndVNode = oldChildren[oldEndIdx]

            let newStartVNode = newChildren[newStartIdx]
            let newEndVNode = newChildren[newEndIdx]

            while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
                    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
   +                 patch(oldStartVNode, newStartVNode, container)
                    // 更新相关索引,指向下一个位置
   +                 oldStartVNode = oldChildren[++oldStartIdx]
   +                 newStartVNode = newChildren[++newStartIdx]
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                    patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
                    patch(oldStartVNode, newEndVNode, container)
                    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

                    oldStartVNode = oldChildren[++oldStartIdx]
                    newEndVNode = newChildren[--newEndIdx]

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }
            }


        }

在这一轮更新之后,新旧两组子节点与真实 DOM 节点的状态如图下图 10-10 所示。

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

双端比较的优势

优势:减少移动操作。

案例分析:如下图的新旧两组子节点:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

简单diff:移动两次
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

双端diff:移动一次

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

非理想状态的处理方式

第一轮都无法命中

  • 旧的一组子节点:p-1、p-2、p-3、p-4。
  • 新的一组子节点:p-2、p-4、p-1、p-3。

当我们尝试按照双端 Diff 算法的思路进行第一轮比较时,会发现无法命中四个步骤中的任何一步。这个时候怎么办呢?这时,我们只能通过增加额外的处理步骤来处理这种非理想情况。既然两个头部和两个尾部的四个节点中都没有可复用的节点,那么我们就尝试看看非头部、非尾部的节点能否复用。具体做法是,拿新的一组子节点中的头部节点去旧的一组子节点中寻找:如下面的代码:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
                    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
                    patch(oldStartVNode, newStartVNode, container)
                    // 更新相关索引,指向下一个位置
                    oldStartVNode = oldChildren[++oldStartIdx]
                    newStartVNode = newChildren[++newStartIdx]
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                    patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
                    patch(oldStartVNode, newEndVNode, container)
                    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

                    oldStartVNode = oldChildren[++oldStartIdx]
                    newEndVNode = newChildren[--newEndIdx]

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                } else {
+					// 处理非理想情况

                    // 在旧的一 组子节点中,找到与新的一组子节点的头部节点具有相同 key 值的节点
                    // 遍历旧的一组子节点,试图寻找与 newStartVNode 拥有相同 key 值的节点
                    // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
 +                   const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)
				}
            }

如下图在旧子节点中寻找可复用节点:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

function patchChildren(n1, n2, container) {
            patchKeyedChildren(n1, n2, container)
        }

        function patchKeyedChildren(n1, n2, container){
            const oldChildren = n1.children 
            const newChildren = n2.children

            // 四个索引值
            let oldStartIdx = 0
            let oldEndIdx = oldChildren.length - 1

            let newStartIdx = 0
            let newEndIdx = newChildren.length - 1

            // 四个索引指向的 vnode 节点
            let oldStartVNode = oldChildren[oldStartIdx]
            let oldEndVNode = oldChildren[oldEndIdx]

            let newStartVNode = newChildren[newStartIdx]
            let newEndVNode = newChildren[newEndIdx]

            while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

                if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
                    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
                    patch(oldStartVNode, newStartVNode, container)
                    // 更新相关索引,指向下一个位置
                    oldStartVNode = oldChildren[++oldStartIdx]
                    newStartVNode = newChildren[++newStartIdx]
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                    patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
                    patch(oldStartVNode, newEndVNode, container)
                    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

                    oldStartVNode = oldChildren[++oldStartIdx]
                    newEndVNode = newChildren[--newEndIdx]

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }  else {
                    // 处理非理想情况

                    // 在旧的一 组子节点中,找到与新的一组子节点的头部节点具有相同 key 值的节点
                    // 遍历旧的一组子节点,试图寻找与 newStartVNode 拥有相同 key 值的节点
                    // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
                    const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)

                    // idxInOld 大于 0,说明找到了可复用的节点,并且需要将其对应的真实DOM 移动到头部
 +                   if(idxInOld > 0) {
 +                       // idxInOld 位置对应的 vnode 就是需要移动的节点
                        const vnodeToMove = oldChildren[idxInOld]
                        
                        // 不要忘记除移动操作外还应该打补丁
 +                       patch(vnodeToMove, newStartVNode, container)

                        // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前,因此使用后者作为锚点
+                        insert(vnodeToMove.el, container, oldStartVNode.el)

                        // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处,因此将其设置为 undefined
 +                       oldChildren[idxInOld] = undefined
                        
                        // 最后更新 newStartIdx 到下一个位置
 +                       newStartVNode = newChildren[++newStartIdx]
                    }
                }
            }


        }

在上面这段代码中,首先判断 idxInOld 是否大于 0。如果条件 成立,则说明找到了可复用的节点,然后将该节点对应的真实 DOM 移 动到头部。为此,我们先要获取需要移动的节点,这里的 oldChildren[idxInOld] 所指向的节点就是需要移动的节点。在移 动节点之前,不要忘记调用 patch 函数进行打补丁。接着,调用 insert 函数,并以现在的头部节点对应的真实 DOM 节点 oldStartVNode.el 作为锚点参数来完成节点的移动操作。当节点移 动完成后,还有两步工作需要做:

    1. 由于处于 idxInOld 处的节点已经处理过了(对应的真实 DOM 移到了别处),因此我们应该将 oldChildren[idxInOld] 设 置为undefined。
    1. 新的一组子节点中的头部节点已经处理完毕,因此将 newStartIdx 前进到下一个位置。

经过上述两个步骤的操作后,新旧两组子节点以及真实 DOM 节点 的状态如图 下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
此时,真实 DOM 的顺序为:p-2、p-1、p-3、p-4。接着,双端 Diff 算法会继续进行。如下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4,两者 key 值不同,不可复用。
第二步:比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的尾部节点 p-3,两者 key 值不同,不可复用。
第三步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-3,两者 key 值不同,不可复用。
第四步:比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的头部节点 p-4,两者的 key 值相同,可以复用。

在这一轮比较的第四步中,我们找到了可复用的节点。因此,按照双端 Diff 算法的逻辑移动真实 DOM,即把节点 p-4 对应的真实DOM 移动到旧的一组子节点中头部节点 p-1 所对应的真实 DOM 前面,如图 下图 所示:

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

此时,真实 DOM 节点的顺序是:p-2、p-4、p-1、p-3。接着,开始下一轮的比较:
第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1,两者的 key 值相同,可以复用。

在这一轮比较中,第一步就找到了可复用的节点。由于两者都处于头部,所以不需要对真实 DOM 进行移动,只需要打补丁即可。在这一步操作过后,新旧两组子节点与真实 DOM 节点的状态如图 下图 所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

此时,真实 DOM 节点的顺序是:p-2、p-4、p-1、p-3。接着,进行下一轮的比较。需要注意的一点是,此时旧的一组子节点的
头部节点是 undefined。这说明该节点已经被处理过了,因此不需要再处理它了,直接跳过即可。为此,我们需要补充这部分逻辑的代码,具体实现如下:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

	// 增加两个判断分支,如果头尾部节点为 undefined,则说明该节点已经被处理过了,直接跳到下一个位置
   + if (!oldStartVNode) {
   +     oldStartVNode = oldChildren[++oldStartIdx]
   + } else if (!oldEndVNode) {
   + 	 oldEndVNode = oldChildren[--oldEndIdx]
   + }else if (oldStartVNode.key === newStartVNode.key) {
        // 步骤一:oldStartVNode 和 newStartVNode 比较
        // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
        patch(oldStartVNode, newStartVNode, container)
        // 更新相关索引,指向下一个位置
        oldStartVNode = oldChildren[++oldStartIdx]
        newStartVNode = newChildren[++newStartIdx]

    } else if (oldEndVNode.key === newEndVNode.key) {
        // 步骤二:oldEndVNode 和 newEndVNode 比较
        // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
        patch(oldEndVNode, newEndVNode, container)

        // 更新索引和头尾部节点变量
        oldEndVNode = oldChildren[--oldEndIdx]
        newEndVNode = newChildren[--newEndIdx]

    } else if(oldStartVNode.key === newEndVNode.key) {
        // 步骤三:oldStartVNode 和 newEndVNode 比较
        patch(oldStartVNode, newEndVNode, container)
        insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

        oldStartVNode = oldChildren[++oldStartIdx]
        newEndVNode = newChildren[--newEndIdx]


    } else if (oldEndVNode.key === newStartVNode.key) {
        // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
        // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
        // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。


        // 第四步:oldEndVNode 和 newStartVNode 比较
        // 仍然需要调用 patch 函数进行打补丁
        patch(oldEndVNode, newStartVNode, container)

        // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
        insert(oldEndVNode.el, container, oldStartVNode.el)
        
        // 移动 DOM 完成后,更新索引值,指向下一个位置
        oldEndVNode = oldChildren[--oldEndIdx]
        newStartVNode = newChildren[++newStartIdx]
    }  else {
        // 处理非理想情况

        // 在旧的一 组子节点中,找到与新的一组子节点的头部节点具有相同 key 值的节点
        // 遍历旧的一组子节点,试图寻找与 newStartVNode 拥有相同 key 值的节点
        // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
        const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)

        // idxInOld 大于 0,说明找到了可复用的节点,并且需要将其对应的真实DOM 移动到头部
        if(idxInOld > 0) {
            // idxInOld 位置对应的 vnode 就是需要移动的节点
            const vnodeToMove = oldChildren[idxInOld]
            
            // 不要忘记除移动操作外还应该打补丁
            patch(vnodeToMove, newStartVNode, container)

            // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前,因此使用后者作为锚点
            insert(vnodeToMove.el, container, oldStartVNode.el)

            // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处,因此将其设置为 undefined
            oldChildren[idxInOld] = undefined
            
            // 最后更新 newStartIdx 到下一个位置
            newStartVNode = newChildren[++newStartIdx]
        }
    }
}

观察上面的代码,在循环开始时,我们优先判断头部节点和尾部节点是否存在。如果不存在,则说明它们已经被处理过了,直接跳到下一个位置即可。在这一轮比较过后,新旧两组子节点与真实 DOM 节点的状态如图 下图 所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

现在,四个步骤又重合了,接着进行最后一轮的比较:
第一步:比较旧的一组子节点中的头部节点 p-3 与新的一组子节点中的头部节点 p-3,两者的 key 值相同,可以复用。在第一步中找到了可复用的节点。由于两者都是头部节点,因此不需要进行 DOM 移动操作,直接打补丁即可。在这一轮比较过后,最终状态如图 下图 所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
这时,满足循环停止的条件,于是更新完成。最终,真实 DOM 节点的顺序与新的一组子节点的顺序一致,都是:p-2、p-4、p-1、p-3。

添加新元素

添加新元素的时机:1.四个步骤的比较中都找不到可复用的节点 。 2.尝试拿新的一组子节点中的头部节点 p-4 去旧的一组子节点中寻找具有相同 key 值的节点,但在旧的一组子节点中根本就没有 p-4 节点。这说明节点 p-4 是一个新增节点。

案例1如下:

  • 旧的一组子节点:p-1、p-2、p-3。
  • 新的一组子节点:p-4、p-1、p-3、p-2。
    vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

代码如下:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
                if (!oldStartVNode) {
                    oldStartVNode = oldChildren[++oldStartIdx]
                } else if (oldStartVNode.key === newStartVNode.key) {
                    // 步骤一:oldStartVNode 和 newStartVNode 比较
                    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
                    patch(oldStartVNode, newStartVNode, container)
                    // 更新相关索引,指向下一个位置
                    oldStartVNode = oldChildren[++oldStartIdx]
                    newStartVNode = newChildren[++newStartIdx]
    
                } else if (oldEndVNode.key === newEndVNode.key) {
                    // 步骤二:oldEndVNode 和 newEndVNode 比较
                    // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                    patch(oldEndVNode, newEndVNode, container)

                    // 更新索引和头尾部节点变量
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newEndVNode = newChildren[--newEndIdx]
    
                } else if(oldStartVNode.key === newEndVNode.key) {
                    // 步骤三:oldStartVNode 和 newEndVNode 比较
                    patch(oldStartVNode, newEndVNode, container)
                    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

                    oldStartVNode = oldChildren[++oldStartIdx]
                    newEndVNode = newChildren[--newEndIdx]

    
                } else if (oldEndVNode.key === newStartVNode.key) {
                    // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                    // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                    // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。
    
    
                    // 第四步:oldEndVNode 和 newStartVNode 比较
                    // 仍然需要调用 patch 函数进行打补丁
                    patch(oldEndVNode, newStartVNode, container)
    
                    // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                    insert(oldEndVNode.el, container, oldStartVNode.el)
                    
                    // 移动 DOM 完成后,更新索引值,指向下一个位置
                    oldEndVNode = oldChildren[--oldEndIdx]
                    newStartVNode = newChildren[++newStartIdx]
                }  else {
                    // 处理非理想情况

                    // 在旧的一 组子节点中,找到与新的一组子节点的头部节点具有相同 key 值的节点
                    // 遍历旧的一组子节点,试图寻找与 newStartVNode 拥有相同 key 值的节点
                    // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
                    const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)

                    // idxInOld 大于 0,说明找到了可复用的节点,并且需要将其对应的真实DOM 移动到头部
                    if(idxInOld > 0) {
                        // idxInOld 位置对应的 vnode 就是需要移动的节点
                        const vnodeToMove = oldChildren[idxInOld]
                        
                        // 不要忘记除移动操作外还应该打补丁
                        patch(vnodeToMove, newStartVNode, container)

                        // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前,因此使用后者作为锚点
                        insert(vnodeToMove.el, container, oldStartVNode.el)

                        // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处,因此将其设置为 undefined
                        oldChildren[idxInOld] = undefined
                        
                        // 最后更新 newStartIdx 到下一个位置
                        newStartVNode = newChildren[++newStartIdx]
                    } else {

+          				// 新增节点
+           			// 将 newStartVNode 作为新节点挂载到头部,使用当前头部节点oldStartVNode.el 作为锚点
+           			patch(null, newStartVNode, container, oldStartVNode.el)
                    }
                }
            }

当条件idxInOld > 0不成立时,说明 newStartVNode 节点是全新的节点。又由于 newStartVNode 节点 是头部节点,因此我们应该将其作为新的头部节点进行挂载。所以, 在调用 patch 函数挂载节点时,我们使用 oldStartVNode.el 作为 锚点。在这一步操作完成之后,新旧两组子节点以及真实 DOM 节点的 状态如下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

案例2

  • 旧的一组子节点:p-1、p-2、p-3。
  • 新的一组子节点:p-4、p-1、p-2、p-3。
    第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4,两者的 key 值不同,不可以复用。
    第二步:比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3,两者的 key 值相同,可以复用。
    在第二步中找到了可复用的节点,因此进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如图下图 所示:
    vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
    接着进行下一轮的比较:
    第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4,两者的 key 值不同,不可以复用。
    第二步:比较旧的一组子节点中的尾部节点 p-2 与新的一组子节点中的尾部节点 p-2,两者的 key 值相同,可以复用。
    我们又在第二步找到了可复用的节点,于是再次进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如图 下图 所示:

vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
接着,进行下一轮的更新:
第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4,两者的 key 值不同,不可以复用。
第二步:比较旧的一组子节点中的尾部节点 p-1 与新的一组子节点中的尾部节点 p-1,两者的 key 值相同,可以复用。

还是在第二步找到了可复用的节点,再次进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如图 下图 所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

当这一轮更新完毕后,由于变量 oldStartIdx 的值大于oldEndIdx 的值,满足更新停止的条件,因此更新停止。但通过观察可知,节点 p-4 在整个更新过程中被遗漏了,没有得到任何处理,这说明我们的算法是有缺陷的。为了弥补这个缺陷,我们需要添加额外的处理代码:

 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
  // 省略部分代码
 }
 // 循环结束后检查索引值的情况,
+  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
+ 	// 如果满足条件,则说明有新的节点遗留,需要挂载它们
+ for (let i = newStartIdx; i <= newEndIdx; i++) {
+      patch(null, newChildren[i], container, oldStartVNode.el)


 +  }
 }

我们在 while 循环结束后增加了一个 if 条件语句,检查四个索引值的情况。根据图上图可知,如果条件oldEndIdx <oldStartIdx && newStartIdx <= newEndIdx成立,说明新的一组子节点中有遗留的节点需要作为新节点挂载。哪些节点是新节点呢?索引值位于 newStartIdx 和 newEndIdx 这个区间内的节点都是新节点。``于是我们开启一个 for 循环来遍历这个区间内的节点并逐一挂载。挂载时的锚点仍然使用当前的头部节点oldStartVNode.el,这样就完成了对新增元素的处理。

移除不存在的元素

案例如下:

  • 旧的一组子节点:p-1、p-2、p-3。
  • 新的一组子节点:p-1、p-3。
    vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript

可以看到,在新的一组子节点中 p-2 节点已经不存在了。为了搞清楚应该如何处理节点被移除的情况,我们还是按照双端 Diff 算法的思路执行更新。
第一步:比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1,两者的 key 值相同,可以复用。
在第一步的比较中找到了可复用的节点,于是执行更新。在这一轮比较过后,新旧两组子节点以及真实 DOM 节点的状态如图下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
接着,执行下一轮更新:
第一步:比较旧的一组子节点中的头部节点 p-2 与新的一组子节点中的头部节点 p-3,两者的 key 值不同,不可以复用。
第二步:比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3,两者的 key 值相同,可以复用。

在第二步中找到了可复用的节点,于是进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如图 下图所示:
vuejs 设计与实现 - 双端diff算法,vue.js,算法,javascript
此时变量 newStartIdx 的值大于变量 newEndIdx 的值,满足更新停止的条件,于是更新结束。但观察图 10-34 可知,旧的一组子节点中存在未被处理的节点,应该将其移除。因此,我们需要增加额外的代码来处理它,如下所示:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
  // 省略部分代码
 }
 // 循环结束后检查索引值的情况,
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
 	// 如果满足条件,则说明有新的节点遗留,需要挂载它们
 for (let i = newStartIdx; i <= newEndIdx; i++) {
      patch(null, newChildren[i], container, oldStartVNode.el)


   }
+ } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
+ 	 for (let i = oldStartIdx; i <= oldEndIdx; i++) {
+		unmount(oldChildren[i])
+	}
 }

与处理新增节点类似,我们在 while 循环结束后又增加了一个else…if 分支,用于卸载已经不存在的节点。由图 上图 可知,索引值位于 oldStartIdx 和 oldEndIdx 这个区间内的节点都应该被卸载,于是我们开启一个 for 循环将它们逐一卸载。

完整代码:文章来源地址https://www.toymoban.com/news/detail-638486.html

const renderer = createRenderer({
            createElement(tag) {
                // console.log(`创建元素 ${tag}`)
                return document.createElement(tag)
            },
            setElementText(el, text) {
                // console.log(`设置${JSON.stringify(el)}的文本内容:${text}`)
                el.textContent = text
            },
            insert(el, parent, anchor = null) {
                // console.log(`将${JSON.stringify(el)}添加到:${JSON.stringify(parent)}`)
                parent.insertBefore(el, anchor)
            },

            // 处理vnode.props
            patchProps(el, key, prevValue, nextValue) {
                // 匹配以 on 开头的属性,视其为事件
                if (/^on/.test(key)) {
                    console.log('key', key)
                    // 根据属性名称得到对应的事件名称,例如 onClick ---> click
                    const name = key.slice(2).toLowerCase()
                    // 移除上一次绑定的事件处理函数
                    prevValue && el.removeEventListener(name, prevValue)
                    el.addEventListener(name, nextValue)
                } else if (key === 'class') {
                    el.className = nextValue || ''
                } else if (key in el) {
                    const type = typeof el[key]
                    if (type === 'boolean' && nextValue === '') {
                        el[key] = true
                    } else {
                        el[key] = nextValue
                    }
                } else {
                    el.setAttribute(key, nextValue)
                }
            },

            createText(text) {
                return document.createTextNode(text)
            },
            setText(el, text) {
                el.nodeValue = text
            }
        })

        function createRenderer(options) {
            const { createElement, setElementText, insert, patchProps, createText, setText } = options

            // 渲染元素
            function render(vnode, container) {
                if (vnode) {
                    patch(container._vnode, vnode, container)
                } else {
                    if (container._vnode) {
                        unmount(container._vnode)
                        // container.innerHTML = ''
                    }
                }

                container._vnode = vnode
            }
            // 更新
            function patch(n1, n2, container) {
                if (n1 && n1.type !== n2.type) {
                    unmount(n1)
                    n1 = null
                }
                // 代码运行到这里,证明 n1 和 n2 所描述的内容相同
                const { type } = n2
                // 如果 n2.type 的值是字符串类型,则它描述的是普通标签元素
                if (typeof type === 'string') {
                    if (!n1) {
                        mountElement(n2, container)
                    } else {
                        // 更新子节点
                        patchElement(n1, n2)
                    }
                } else if (typeof type === 'object') {
                    // 组件
                } else if (typeof type === Text) {
                    if (!n1) {
                        const el = n2.el = createText(n2.children)
                        insert(el, container)
                    } else {
                        const el = n2.el = n1.el
                        if (n2.children !== n1.children) {
                            setText(el, n2.children)
                        }
                    }
                } else if (typeof type === Fragment) {
                    // 如果旧 vnode 不存在,则只需要将 Fragment 的 children 逐个挂载
                    if (!n1) {
                        n2.children.forEach(c => patch(null, c, container))
                    } else {
                        // 如果旧 vnode 存在,则只需要更新 Fragment 的 children 即可
+                        patchChildren(n1, n2, container)
                    }
                }
            }

            // 挂载元素
            function mountElement(vnode, container) {
                // 让 vnode.el 引用真实 DOM 元素, 卸载的时候用
                const el = vnode.el = createElement(vnode.type)

                // 处理children
                if (typeof vnode.children === 'string') {
                    setElementText(el, vnode.children)
                } else if (Array.isArray(vnode.children)) {
                    vnode.children.forEach(child => {
                        patch(null, child, el)
                    });
                }

                // 处理pprops
                if (vnode.props) {
                    for (const key in vnode.props) {
                        // 调用 patchProps 函数即可
                        patchProps(el, key, null, vnode.props[key])
                    }
                }


                insert(el, container)
            }

            // 更新子节点步骤:
            // 第一步:更新 props
            // 第二步:更新 children
            function patchElement(n1, n2) {
                const el = n2.el = n1.el
                const oldProps = n1.props
                const newProps = n2.props


                // 第一步:更新 props
                for (const key in newProps) {
                    if (newProps[key] !== oldProps[key]) {
                        patchProps(el, key, oldProps[ke], newProps[key])
                    }
                }

                // 第二步:更新 children
                patchChildren(n1, n2, el)
            }
            // 更新 children
+            function patchChildren(n1, n2, container) {
                if (typeof n2.children === 'string') {
                    // 1.旧子节点是一组子节点,先逐个卸载
                    // 2.旧子节点是字符串,直接使用setElementText设置即可
                    // 3.旧子节点无,直接使用setElementText设置即可
                    if (Array.isArray(n1.children)) {
                        n1.children.forEach((c) => unmount(c))
                    }
                    setElementText(container, n2.children)

                } else if (Array.isArray(n2.children)) {
                    // 1.旧子节点是一组子节点,进行patch操作
                    // 2.旧子节点是字符串,直接使用setElementText设置即可
                    // 3.旧子节点无,直接使用setElementText设置即可
                    if (Array.isArray(n1.children)) {
                        
                        // 双端diff
                        patchKeyedChildren(n1, n2)

                    } else {
                        setElementText(container, '')
                        n2.children.forEach((c) => patch(null, c, container))
                    }

                } else {
                    // 代码运行到这里,说明新子节点不存在
                    // 1.旧子节点是一组子节点,只需逐个卸载即可
                    // 2.旧子节点是文本节点,清空内容即可

                    if (Array.isArray(n1.children)) {
                        n2.children.forEach((c) => unmount(c))
                    } else if (typeof n1.children === 'string') {
                        setElementText(container, '')
                    }

                }
            }

            // 卸载
            function unmount(vnode) {
                console.log(vnode)
                const parent = vnode.el.parentNode
                parent && parent.removeChild(vnode.el)
            }


+            function patchKeyedChildren(n1, n2, container) {
                const oldChildren = n1.children
                const newChildren = n2.children

                let oldStartIdx = 0
                let oldEndIdx = n1.children.length - 1
                let newStartIdx = 0
                let newEndIdx = n2.children.length - 1

                let oldStartVNode = oldChildren[oldStartIdx]
                let oldEndVNode = oldChildren[oldEndIdx]
                let newStartVNode = newChildren[newStartIdx]
                let newEndVNode = newChildren[newEndIdx]

                while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
                    if (!oldStartVNode) {
                        oldStartVNode = oldChildren[++oldStartIdx]
                    } else if (oldStartVNode.key === newStartVNode.key) {
                        // 步骤一:oldStartVNode 和 newStartVNode 比较
                        // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
                        patch(oldStartVNode, newStartVNode, container)
                        // 更新相关索引,指向下一个位置
                        oldStartVNode = oldChildren[++oldStartIdx]
                        newStartVNode = newChildren[++newStartIdx]

                    } else if (oldEndVNode.key === newEndVNode.key) {
                        // 步骤二:oldEndVNode 和 newEndVNode 比较
                        // 节点在新的顺序中仍然处于尾部,不需要移动,但仍需打补丁
                        patch(oldEndVNode, newEndVNode, container)

                        // 更新索引和头尾部节点变量
                        oldEndVNode = oldChildren[--oldEndIdx]
                        newEndVNode = newChildren[--newEndIdx]

                    } else if (oldStartVNode.key === newEndVNode.key) {
                        // 步骤三:oldStartVNode 和 newEndVNode 比较
                        patch(oldStartVNode, newEndVNode, container)
                        insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

                        oldStartVNode = oldChildren[++oldStartIdx]
                        newEndVNode = newChildren[--newEndIdx]


                    } else if (oldEndVNode.key === newStartVNode.key) {
                        // 我们找到了具有相同 key 值的节点。这说明,原来处于尾部的节点在新的顺序中应该处于头部。
                        // 于是,我们只需要以头部元素oldStartVNode.el 作为锚点,将尾部元素 oldEndVNode.el 移动到锚点前面即可。
                        // 但需要注意的是,在进行 DOM 的移动操作之前,仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。


                        // 第四步:oldEndVNode 和 newStartVNode 比较
                        // 仍然需要调用 patch 函数进行打补丁
                        patch(oldEndVNode, newStartVNode, container)

                        // 移动dom操作  oldEndVNode.el 移动到 oldStartVNode.el 前面
                        insert(oldEndVNode.el, container, oldStartVNode.el)

                        // 移动 DOM 完成后,更新索引值,指向下一个位置
                        oldEndVNode = oldChildren[--oldEndIdx]
                        newStartVNode = newChildren[++newStartIdx]
                    } else {
                        // 处理非理想情况

                        // 在旧的一 组子节点中,找到与新的一组子节点的头部节点具有相同 key 值的节点
                        // 遍历旧的一组子节点,试图寻找与 newStartVNode 拥有相同 key 值的节点
                        // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
                        const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)

                        // idxInOld 大于 0,说明找到了可复用的节点,并且需要将其对应的真实DOM 移动到头部
                        if (idxInOld > 0) {
                            // idxInOld 位置对应的 vnode 就是需要移动的节点
                            const vnodeToMove = oldChildren[idxInOld]

                            // 不要忘记除移动操作外还应该打补丁
                            patch(vnodeToMove, newStartVNode, container)

                            // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前,因此使用后者作为锚点
                            insert(vnodeToMove.el, container, oldStartVNode.el)

                            // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处,因此将其设置为 undefined
                            oldChildren[idxInOld] = undefined

                            // 最后更新 newStartIdx 到下一个位置
                            newStartVNode = newChildren[++newStartIdx]
                        } else {

                            // 新增节点
                            // 将 newStartVNode 作为新节点挂载到头部,使用当前头部节点oldStartVNode.el 作为锚点
                            patch(null, newStartVNode, container, oldStartVNode.el)
                        }
                    }
                }


                // 循环结束后检查索引值的情况,
                // 新增元素
                if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
                    for (let i = newStartIdx; i < newEndIdx; i++) {
                        patch(null, newChildren[i], container, oldStartVNode.el)
                    }
                } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
                    // 移除元素
                    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                        unmount(oldChildren[i])
                    }
                }


            }
            return {
                render
            }
        }

        // 测试
        const Text = Symbol()
        const vnode = {
            type: 'div',
            // children: 'hello'
            props: {
                id: 'red',
                onClick: () => {
                    alert('clicked')
                }
            },
            children: [
                {
                    type: 'p',
                    children: 'hello',
                    props: {
                        class: 'ddd'
                    }
                },
                {
                    type: 'Text',
                    children: '我是文本内容'
                },
                {
                    type: 'Fragment',
                    children: [
                        { type: 'li', children: '1', text: '1' },
                        { type: 'li', children: '2', text: '2' }
                    ]
                }
            ]
        }
        console.log(vnode)

        renderer.render(vnode, document.getElementById('app'))

到了这里,关于vuejs 设计与实现 - 双端diff算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • vuejs 设计与实现 - 渲染器的设计

    本节,我们暂时将渲染器限定在 DOM 平台。既然渲染器用来渲染真实 DOM 元素,那么严格来说,下面的函数就是一个合格的渲染器: 使用渲染器: 如果页面中存在 id 为 app 的 DOM 元素,那么上面的代码就会将 插入到该 DOM 元素内。 当然,我们不仅可以渲染静态的字符串,还可以

    2024年02月13日
    浏览(35)
  • JavaScript实现手写签名,可触屏手写,支持移动端与PC端双端保存

    1.HTML模板 2.获取DOM元素和定义变量 3.创建两个canvas元素,并设置它们的宽度和高度 4.绑定触摸事件:touchstart, touchmove, touchend和click 5.实现触摸事件回调函数:startDrawing, draw和stopDrawing 6.实现绘制线段的函数:drawLine 7.实现清除签名的函数:clearSignature 8.实现保存签名的函数:

    2024年01月16日
    浏览(49)
  • 【vue】diff 算法详解

    diff算法是一种通过 同层的树节点 进行比较的高效算法         diff算法的目的就是找出新旧不同虚拟DOM之间的差异,使最小化的更新视图,所以 diff 算法本质上就是比较两个js对象的差异 特点         1. 比较只会在同层级进行,不会跨层级比较         2. 在diff比较的构成

    2024年02月02日
    浏览(33)
  • vue的diff算法原理

    vue基于虚拟DOM做更新,diff的核心就是比较两个虚拟节点的差异。 vue的diff算法是 平级比较 ,不考虑跨级比较的情况。内部采用 深度递归 + 双指针 的方式进行比较 先比较是否是相同节点 key tag (标识,标签名) 相同节点比较属性,并复用老节点(将老的虚拟dom复用给新的虚拟

    2023年04月25日
    浏览(32)
  • vuejs 设计与实现 - 渲染器 - 挂载与更新

    渲染器的核心功能:挂载与更新 1.2挂载子节点 (vnode.children) vnode.children可以是字符串类型的,也可以是数组类型的,如下: 可以看到,vnode.children 是一个数组,它的每一个元素都是一个独立的虚拟节点对象。这样就形成了树型结构,即虚拟DOM 树。 为了完成子节点的渲染,我们

    2024年02月13日
    浏览(34)
  • 【源码系列#06】Vue3 Diff算法

    专栏分享:vue2源码专栏,vue3源码专栏,vue router源码专栏,玩具项目专栏,硬核💪推荐🙌 欢迎各位ITer关注点赞收藏 🌸🌸🌸 Vue2 Diff算法可以参考此篇文章 【Vue2.x源码系列08】Diff算法原理 两个不同虚拟节点不需要进行比较,直接移除老节点,将新的虚拟节点渲染成真实D

    2024年01月17日
    浏览(40)
  • vue和react的diff算法源码

    Vue.js 的 Diff 算法主要基于 Snabbdom,以下是 Vue.js 中虚拟 DOM Diff 算法的简化版伪代码,以便说明其基本思想: 这里主要关注 patchVnode 函数,它是 Diff 算法的核心。Vue.js 的 Diff 算法采用了一种双端比较的策略,具体步骤如下: 1.同层级比较: 首先比较新旧节点的同层级,通过

    2024年03月15日
    浏览(52)
  • vue diff 前后缀+最长递增子序列算法

    如上图所示,新旧 children 拥有相同的前缀节点和后缀节点 对于前缀节点,我们可以建立一个索引,指向新旧 children 中的第一个节点,并逐步向后遍历,直到遇到两个拥有不同 key 值的节点为止 对于相同的后缀节点,由于新旧 children 中节点的数量可能不同,所以我们需要两个

    2024年02月13日
    浏览(36)
  • vue diff算法与虚拟dom知识整理(6) 感受diff算法 (不要神话虚拟dom更不要做完美主义)

    我们还是打开之前的案例 然后 将src下的index.js代码修改如下 首先 我们写入节点的方法叫 patch 我们来查一下这个单纯的意思 其实 他不是一个暴力装卸的方法 而是 修补的一个概念 因为 我们需要一个触发事件的工具 所以 我们在www文件夹下的index.html中加一个id为btn的按钮 参考

    2024年02月04日
    浏览(33)
  • vue2和vue3之间diff算法的差异

    1.Virtual DOM的优化 Vue 2 中的 diff 算法针对整个 Virtual DOM 树进行了完整的比较,导致在大型应用中可能存在性能问题。 Vue 3 中通过静态分析和标记,将组件标记为静态、动态或稳定,从而避免不必要的 Virtual DOM 比较,提高了渲染性能。 2.动态指令的优化 Vue 2 中动态指令的 di

    2024年02月04日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包