526互联

Vue源码学习(十六):diff算法(三)暴力比对

发布时间 2023-11-10 19:56:48作者: 养肥胖虎

好家伙，这是diff的最后一节了

 

0.暴力比对的使用场景 

没有可复用的节点：当新旧虚拟 DOM 的结构完全不同，或者某个节点不能被复用时，需要通过暴力比对来创建新的节点，并在真实 DOM 上进行相应的插入操作。

0.1.例子一：

// 创建vnode
let vm1 = new Vue({
  data: {
    name: '张三'
  }
})
let render1 = compileToFunction(`<ul>
    <li style="background:red" key="c">c</li>
     <li style="background:pink" key="b">b</li>
     <li style="background:blue" key="a">a</li>
    </ul>`)
let vnode1 = render1.call(vm1)
document.body.appendChild(createELm(vnode1))

//数据更新
let vm2 = new Vue({
  data: {
    name: '李四'
  }
})
let render2 = compileToFunction(`<ul>
     <li style="background:red" key="f">f</li>
     <li style="background:pink" key="g">g</li>
     <li style="background:blue" key="e">e</li>
    </ul>`)
let vnode2 = render2.call(vm2)

setTimeout(() => {
  patch(vnode1, vnode2)
}, 2000)

 

0.2.例子二：

let vm1 = new Vue({
  data: {
    name: '张三'
  }
})
let render1 = compileToFunction(`<ul>
    <li style="background:red" key="c">c</li>
     <li style="background:pink" key="b">b</li>
     <li style="background:blue" key="a">a</li>
    </ul>`)
let vnode1 = render1.call(vm1)
document.body.appendChild(createELm(vnode1))

//数据更新
let vm2 = new Vue({
  data: {
    name: '李四'
  }
})
let render2 = compileToFunction(`<ul>
     <li style="background:red" key="f">f</li>
     <li style="background:pink" key="g">g</li>
     <li style="background:pink" key="b">b</li>
     <li style="background:blue" key="e">e</li>

    </ul>`)
let vnode2 = render2.call(vm2)

setTimeout(() => {
  patch(vnode1, vnode2)
}, 2000)

 

 

依旧是这个例子，但我们分开两种情况讨论

情况一：render1和render2中没有相同的key值

情况二：render1和render2中只有一个节点的key值是相同的

以上两种情况上一张的方法

Vue源码学习(十五):diff算法(二)交叉比对(双指针)

无法处理

于是我们使用暴力比对

 

 

1.分析

来看逻辑图：

1.1.情况一：

例子：c b a 与 f g e 比对

1.1.1比对新旧vnode中的首个节点

不匹配，将新vnode中的元素添加到旧vnode首个元素前

 

 

1.1.2.新vnode指针++

添加逻辑同上，依旧是添加到添加到旧vnode首个元素前

 

1.1.3.新vnode指针++

添加逻辑同上，依旧是添加到添加到旧vnode首个元素前

 

1.1.4.匹配完成，删除旧vnode

 

1.2.情况二：

例子： c b a 与 f g b e比对

前两步一致

但，到相同的元素b时有些许的不同

此处我们会引入一个旧vnode的关系映射表

 

1.2.2.新vnode节点中的每一个子节点都将与这个映射表进行匹配,寻找相同的元素

 

 1.2.3.继续

 

 

 

将旧vnode中的"相同节点"打上一个"删去标记"

后续步骤同情况一

 

2.代码实现

2.1.建立映射表

    function makeIndexBykey(child){
        let map = {}
            child.forEach((item,index)=>{
                if(item.key){
                    map[item.key] =index
                }
            })
        return map
    }
    //创建映射表
    let map =makeIndexBykey(oldChildren)

在暴力比对（也称为全量更新）期间，旧 vnode 映射表的作用是存储旧 vnode 子元素的键值对（key-value pairs）。

这个映射表的目的是在新旧 vnode 的比对中，可以通过键（key）快速查找旧 vnode 中对应的索引位置。

在给定的代码中，makeIndexBykey 函数接收一个 child 数组作为输入参数，遍历每个 child 元素，并且如果该元素存在 key 属性，

则将其在 child 数组中的索引值存储到 map 对象中，以 item.key 作为键，index 作为值。

这样做的目的是为了在后续的比对过程中，可以通过 key 值快速找到旧 vnode 中对应的索引值。

通过查找 map 对象，可以在遇到新的 vnode 元素时，快速判断是否存在对应的 key 值，并且获取旧 vnode 中的索引值。

这对于减少比对时间和优化更新性能非常有帮助，尤其在大型应用程序或具有复杂数据结构的页面中。

 

2.2.暴力比对算法

console.log(5)
            //1 创建 旧元素映射表
            //2 从旧的中寻找新的中有的元素
            let moveIndex = map[newStartVnode.key]
            //没有相应key值的元素
            if(moveIndex == undefined){
                parent.insertBefore(createELm(newStartVnode),oldStartVnode.el)
            }//有
            else{
                let moveVnode = oldChildren[moveIndex] //获取到有的元素
                oldChildren[moveIndex]=null
                //a b f c 和 d f e 
                parent.insertBefore(moveVnode.el,oldStartVnode.el)

                patch(moveVnode,newEndVnode)
            }
            newStartVnode = newChildren[++newStartIndex]

--1--如果旧 vnode 中不存在相同键（key）的元素，即 moveIndex 为 undefined，则说明这是一个新元素，需要将新元素插入到旧 vnode 开始位置元素之前。

这里调用 createELm(newStartVnode) 创建新元素的 DOM 节点，并通过 parent.insertBefore 方法将其插入到旧 vnode 开始位置元素之前。

--2--如果旧 vnode 中存在相同键（key）的元素，则说明这是一个相同元素(一个需要移动的元素,事实上,代码的逻辑为,将在旧vnode中该"相同元素"移动)

通过 let moveVnode = oldChildren[moveIndex] 将该元素赋值给 moveVnode。然后将 oldChildren[moveIndex] 设为 null，标记该元素已经被处理。

然后，通过 parent.insertBefore(moveVnode.el, oldStartVnode.el)，将该元素的 DOM 节点插入到旧 vnode 开始位置元素之前。

 

2.3.删除旧vnode中节点

//将老的多余的元素删去
    if (oldStartIndex <= oldEndIndex) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            //注意null
            let child = oldChildren[i]
            if(child !=null ){
                parent.removeChild(child.el) //删除元素
            }
        }
    }

 

3.patch.js完整代码

export function patch(oldVnode, Vnode) {
    //原则  将虚拟节点转换成真实的节点
    console.log(oldVnode, Vnode)
    // console.log(oldVnode.nodeType)
    // console.log(Vnode.nodeType)
    //第一次渲染 oldVnode 是一个真实的DOM
    //判断ldVnode.nodeType是否为一,意思就是判断oldVnode是否为属性节点
    if (oldVnode.nodeType === 1) {
        console.log(oldVnode, Vnode) //注意oldVnode 需要在加载 mount 添加上去  vm.$el= el

        let el = createELm(Vnode) // 产生一个新的DOM
        let parentElm = oldVnode.parentNode //获取老元素（app） 父亲 ，body
        //   console.log(oldVnode)
        //  console.log(parentElm)

        parentElm.insertBefore(el, oldVnode.nextSibling) //当前真实的元素插入到app 的后面
        parentElm.removeChild(oldVnode) //删除老节点
        //重新赋值
        return el
    } else { //  diff
        // console.log(oldVnode.nodeType)
        // console.log(oldVnode, Vnode)
        //1 元素不是一样 
        if (oldVnode.tag !== Vnode.tag) {
            //旧的元素 直接替换为新的元素
            return oldVnode.el.parentNode.replaceChild(createELm(Vnode), oldVnode.el)
        }
        //2 标签一样 text  属性 <div>1</div>  <div>2</div>  tag:undefined
        if (!oldVnode.tag) {
            if (oldVnode.text !== Vnode.text) {
                return oldVnode.el.textContent = Vnode.text
            }
        }
        //2.1属性 (标签一样)  <div id='a'>1</div>  <div style>2</div>
        //在updataRpors方法中处理
        //方法 1直接复制
        let el = Vnode.el = oldVnode.el
        updataRpors(Vnode, oldVnode.data)
        //diff子元素 <div>1</div>  <div></div>
        console.log(oldVnode,Vnode)
        let oldChildren = oldVnode.children || []
        let newChildren = Vnode.children || []
        if (oldChildren.length > 0 && newChildren.length > 0) { //老的有儿子 新有儿子
            //创建方法
            
            updataChild(oldChildren, newChildren, el)
        } else if (oldChildren.length > 0 && newChildren.length <= 0) { //老的元素 有儿子 新的没有儿子
            el.innerHTML = ''
        } else if (newChildren.length > 0 && oldChildren.length <= 0) { //老没有儿子  新的有儿子
            for (let i = 0; i < newChildren.length; i++) {
                let child = newChildren[i]
                //添加到真实DOM
                el.appendChild(createELm(child))
            }
        }

    }
}

function updataChild(oldChildren, newChildren, parent) {
    //diff算法 做了很多优化 例子<div>11</div> 更新为 <div>22</div> 
    //dom中操作元素 常用的 思想 尾部添加 头部添加 倒叙和正序的方式
    //双指针 遍历
    console.log(oldChildren, newChildren)
    let oldStartIndex = 0 //老的开头索引
    let oldStartVnode = oldChildren[oldStartIndex];
    let oldEndIndex = oldChildren.length - 1
    let oldEndVnode = oldChildren[oldEndIndex]

    let newStartIndex = 0 //新的开头索引
    let newStartVnode = newChildren[newStartIndex];
    let newEndIndex = newChildren.length - 1
    let newEndVnode = newChildren[newEndIndex]
    // console.log(oldEndIndex,newEndIndex)
    // console.log(oldEndVnode,newEndVnode)

    function makeIndexBykey(child){
        let map = {}
            child.forEach((item,index)=>{
                if(item.key){
                    map[item.key] =index
                }
            })
        return map
    }
    //创建映射表
    let map =makeIndexBykey(oldChildren)

    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        //比对子元素
        console.log(666)
        if (isSomeVnode(oldStartVnode, newStartVnode)) {
            //递归
            //1 从头部开始
            console.log(1)
            patch(oldStartVnode, newStartVnode);
            //移动指针
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
            console.log(oldStartVnode,newStartVnode)
        }//2 从尾部开始
        else if(isSomeVnode(oldEndVnode, newEndVnode)){
            //
            console.log(2)
            patch(oldEndVnode, newEndVnode);
            oldEndVnode = oldChildren[--oldEndIndex]
            newEndVnode = newChildren[--newEndIndex]
        }//3 交叉比对 从头
        else if(isSomeVnode(oldStartVnode,newEndVnode)){
            console.log(3)
            patch(oldStartVnode, newEndVnode);
            oldStartVnode =oldChildren[++oldStartIndex]
            newEndVnode = newChildren[--newEndIndex];
        }//4 交叉比对 从尾
        else if(isSomeVnode(oldEndVnode,newStartVnode)){
            console.log(4)
            patch(oldEndVnode, newStartVnode);
            oldEndVnode =oldChildren[--oldStartIndex]
            newStartVnode = newChildren[++newStartIndex];
        }//5 暴力比对 儿子之间没有任何关系
        else{
            console.log(5)
            //1 创建 旧元素映射表
            //2 从旧的中寻找新的中有的元素
            let moveIndex = map[newStartVnode.key]
            //没有相应key值的元素
            if(moveIndex == undefined){
                parent.insertBefore(createELm(newStartVnode),oldStartVnode.el)
            }//有
            else{
                let moveVnode = oldChildren[moveIndex] //获取到有的元素
                oldChildren[moveIndex]=null
                //a b f c 和 d f e 
                parent.insertBefore(moveVnode.el,oldStartVnode.el)

                patch(moveVnode,newEndVnode)
            }
            newStartVnode = newChildren[++newStartIndex]
        }
    }
    //判断完毕,添加多余的子儿子  a b c  新的 a b c d
    console.log(newEndIndex)
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            parent.appendChild(createELm(newChildren[i]))
        }
    }
    //将老的多余的元素删去
    if (oldStartIndex <= oldEndIndex) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            //注意null
            let child = oldChildren[i]
            if(child !=null ){
                parent.removeChild(child.el) //删除元素
            }
        }
    }
    
}
function isSomeVnode(oldContext, newContext) {
    // return true
    return (oldContext.tag == newContext.tag) && (oldContext.key === newContext.key);
}  



//添加属性
function updataRpors(vnode, oldProps = {}) { //第一次
    let newProps = vnode.data || {} //获取当前新节点 的属性
    let el = vnode.el //获取当前真实节点 {}
    //1老的有属性，新没有属性
    for (let key in oldProps) {
        if (!newProps[key]) {
            //删除属性
            el.removeAttribute[key] //
        }
    }
    //2演示 老的 style={color:red}  新的 style="{background:red}"
    let newStyle = newProps.style || {} //获取新的样式
    let oldStyle = oldProps.style || {} //老的
    for (let key in oldStyle) {
        if (!newStyle[key]) {
            el.style = ''
        }
    }
    //新的
    for (let key in newProps) {
        if (key === "style") {
            for (let styleName in newProps.style) {
                el.style[styleName] = newProps.style[styleName]
            }
        } else if (key === 'class') {
            el.className = newProps.class
        } else {
            el.setAttribute(key, newProps[key])
        }
    }
}
//vnode 变成真实的Dom
export function createELm(vnode) {
    let {
        tag,
        children,
        key,
        data,
        text
    } = vnode
    //注意
    if (typeof tag === 'string') { //创建元素 放到 vnode.el上
        vnode.el = document.createElement(tag) //创建元素 
        updataRpors(vnode)
        //有儿子
        children.forEach(child => {
            // 递归 儿子 将儿子渲染后的结果放到 父亲中
            vnode.el.appendChild(createELm(child))
        })
    } else { //文本
        vnode.el = document.createTextNode(text)
    }
    return vnode.el //新的dom
}