关于javascript:Diff算法

Diff

• diff 比照的就是 vnode
• 同时因为 dom 很少跨级挪动，所以比照只在同层级中进行
• vue 和 react 的 diff 算法大体是一样的

VNode

• vue 的 vnode 如下

{el:  div  // 对实在的节点的援用，本例中就是 document.querySelector('#id.classA')
    tagName: 'DIV',   // 节点的标签
    sel: 'div#v.classA'  // 节点的选择器
    data: null,       // 一个存储节点属性的对象，对应节点的 el[prop]属性，例如 onclick , style
    children: [], // 存储子节点的数组，每个子节点也是 vnode 构造
    text: null,    // 如果是文本节点，对应文本节点的 textContent，否则为 null
}

• react 的 vnode 如下

{
    type: 'div',
    props: {className: 'myDiv',},
    chidren: [{ type: 'p', props: { value:'1'} },
        {type: 'div', props: { value:'2'} },
        {type: 'span', props: { value:'3'} }
    ]
}

Vue

• vue 的 diff 是边比拟边更新的过程
• 更改数据时，触发试图更新，会生成一棵新的 vdom 树
• 比照同级的 vnode，仅当 vue 认为两个 vnode 值得比拟时，才会持续比照其子节点，如果认为不值得比拟，会间接删除旧节点，插入新节点

function patch (oldVnode, vnode) {if (sameVnode(oldVnode, vnode)) {patchVnode(oldVnode, vnode)
    } else {
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode)
        if (parentEle !== null) {api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
            api.removeChild(parentEle, oldVnode.el)
            oldVnode = null
        }
    }
    return vnode
}

function sameVnode(oldVnode, vnode){
  // 两节点 key 值雷同，并且 sel 属性值雷同，即认为两节点属同一类型，可进行下一步比拟
    return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}

• 针对同类型的节点，进行 patch 操作，并比拟他的子节点

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el  // 让 vnode.el 援用到当初的实在 dom，当 el 批改时，vnode.el 会同步变动。let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return  // 新旧节点援用统一，认为没有变动
    // 文本节点的比拟
    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {api.setTextContent(el, vnode.text)
    }else {updateEle(el, vnode, oldVnode)
        // 对于领有子节点 (两者的子节点不同) 的两个节点，调用 updateChildren
        if (oldCh && ch && oldCh !== ch) {updateChildren(el, oldCh, ch)
        } else if (ch){  // 只有新节点有子节点，增加新的子节点
            createEle(vnode) //create el's children dom
        } else if (oldCh){  // 只有旧节点内存在子节点，执行删除子节点操作
            api.removeChildren(el)
        }
    }
}

• 针对单方都领有子节点的状况，通过 updateChildren 来解决更新

updateChildren (parentElm, oldCh, newCh) {
    let oldStartIdx = 0, newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVnode == null) {   // 对于 vnode.key 的比拟，会把 oldVnode = null
                oldStartVnode = oldCh[++oldStartIdx] 
            } else if (oldEndVnode == null) {oldEndVnode = oldCh[--oldEndIdx]
            } else if (newStartVnode == null) {newStartVnode = newCh[++newStartIdx]
            } else if (newEndVnode == null) {newEndVnode = newCh[--newEndIdx]
            } else if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            } else if (sameVnode(oldStartVnode, newEndVnode)) {patchVnode(oldStartVnode, newEndVnode)
                api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
            } else if (sameVnode(oldEndVnode, newStartVnode)) {patchVnode(oldEndVnode, newStartVnode)
                api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            } else {
               // 应用 key 时的比拟
                if (oldKeyToIdx === undefined) {oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有 key 生成 index 表
                }
                idxInOld = oldKeyToIdx[newStartVnode.key]
                if (!idxInOld) {api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    newStartVnode = newCh[++newStartIdx]
                }
                else {elmToMove = oldCh[idxInOld]
                    if (elmToMove.sel !== newStartVnode.sel) {api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    }else {patchVnode(elmToMove, newStartVnode)
                        oldCh[idxInOld] = null
                        api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                    }
                    newStartVnode = newCh[++newStartIdx]
                }
            }
        }
        if (oldStartIdx > oldEndIdx) {before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        } else if (newStartIdx > newEndIdx) {removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
}

• 详情下，就是别离新建 4 个指针，指向新旧节点的头尾，而后通过两两比对，看是否是同一个类型的节点
• 而后分状况，如果新旧头节点是同一个类型节点，间接调用 patchVnode 即可，同理新旧尾节点是同一个类型节点，也是 patchVnode 解决
• 但如果判断新头和旧尾是同一个类型节点，除了要 patchVnode 解决外，还须要将尾部节点移到头部
• 同理，如果新尾和旧头是同一个类型节点，patchVnode 解决后，将头节点移到尾部
• 如果四种比拟都没有击中，这时判断新头的节点是否在仍未被比照的旧节点中，如果在，patchVnode 解决，并在 dom 中将旧节点移到新头的地位，本来旧节点对应的 Vnode 置空，这样下次判断就会被跳过，而如果新节点不在旧节点列表里，则间接新建节点插入即可
• 最初，当头指针和尾指针相遇并错过后，判断以后四个指针的地位，如果旧的头尾指针两头还有节点，那这些节点都是多余的，须要被移除，如果新的头尾指针两头还有节点，那这些节点都是新增的，须要被插入

React

• react 的 diff 是先比拟，后更新的流程，比照阶段会先记录下差别

function diff (oldTree, newTree) {
  // 以后节点的标记，当前每遍历到一个节点，加 1
  var index = 0
  var patches = {} // 用来记录每个节点差别的对象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 对两棵树进行深度优先遍历
function dfsWalk (oldNode, newNode, index, patches) {
  // 比照 oldNode 和 newNode 的不同，记录下来，省略了代码...
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

• 先比照以后节点，记录差别，而后比照子节点
• 子节点的比照间接从左节点开始，判断其是否在旧节点列表中，如果不在，则记录新建，如果在，则标记挪动
• 最初依据差别对立更新 dom

区别

• vue 的 diff 是边比拟边更新的，react 则是先记录差别，再对立更新
• vue 认为两个节点元素是同一个元素是依据 key 以及 sel 来判断的，如果元素类型雷同，但 classname 不统一的话也会认为是不同的元素，而 react 是依据元素类型以及 key 来判断的，所以会认为是同一个元素类型，间接在这下面进行属性增减
• diff 策略也不一样，vue 是新旧头尾四个节点比照，react 则是从左到右进行比照
• 另外 react16 提出了 fiber 这个概念，diff 是基于 fiber 树进行的，且能够被打断，让浏览器能解决更高优先级的工作，而 vue 的 diff 和 patch 是不能被打断的

key 的作用

• vue 和 react 的 key 作用是一样的，就是通知引擎以后比照的两个节点是否是同一个节点
• vue 没有 key 的时候，两个都是 undefined，则 vue 会认为其是雷同节点，而就地复用这个元素，但很可能这是个 input 元素，你曾经在外面输出了某些信息，而更新时不会挪动这些信息导致最终后果可能不是你所冀望的，所以须要指明 key 来避免元素的复用
• react 则会默认赋值给 key，所以子元素中，新旧节点的地位可能产生了挪动，但因为 react 默认 index 作为 key，还是会认为雷同地位上的元素是同一个元素，而在其根底上批改属性，导致产生和 vue 一样的问题