Diff算法

VUE 中的 Diff 实现

Diff 算法比较只会进行同层进行,不会进行跨层比较

相同节点判断

function sameVnode (a, b) {
  return (
    a.key === b.key &&  // key值
    a.tag === b.tag &&  // 标签名
    a.isComment === b.isComment &&  // 是否为注释节点
    // 是否都定义了data，data包含一些具体信息，例如onclick , style
    isDef(a.data) === isDef(b.data) &&  
    sameInputType(a, b) // 当标签是<input>的时候，type必须相同
  )
}

首先比较newVnode 和oldVnode 的sel 属性(VDOM的构建描述’dev’, ’ul.className’, ’li#idName’ 等),如果节点不同说明Vnode被完全改变了,直接替换为newVnode 因为Diff算法为同层比较,所以不需要进行children的比较

节点合并

function patchVnode(oldVnode, newVnode){
  const el = newVnode.el = oldVnode.el //合并引用
  let i, oldCh = oldVnode.children, ch = newVnode.children
  if (oldVnode === newVnode) return //如果严格一致直接返回
  if (oldVnode.text !== null && newVnode.text !== null && oldVnode.text !== newVnode.text) { // 文本节点处理
    api.setTextContent(el, newVnode.text)
  }else{
    updateEle(el, newVnode, oldVnode) //更新节点
    if (oldCh && ch && oldCh !== ch) {
          updateChildren(el, oldCh, ch)
    }else if (ch){
          createEle(newVnode) 
    }else if (oldCh){
          api.removeChildren(el)
    }
  }
}

找到对应的真实dom，称为el
判断newVnode和oldVnode是否指向同一个对象，如果是，那么直接return
如果他们都有文本节点并且不相等，那么将el的文本节点设置为newVnode的文本节点。
如果oldVnode有子节点而newVnode没有，则删除el的子节点
如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el
如果两者都有子节点，则执行updateChildren函数比较子节点

子节点比较

有子节点 —>无子节点无子节点 —>有子节点子节点—>文本节点文本节点—>子节点这几种情况都比较简单,关键点在于有子节点—>有子节点这种情况的比较为了方便理解可以虚拟成两个数组进行比较

function sameVnode (a, b) {//节点相同判断
  return (
    a.key === b.key &&  // key值
    a.tag === b.tag &&  // 标签名
    a.isComment === b.isComment &&  // 是否为注释节点
    // 是否都定义了data，data包含一些具体信息，例如onclick , style
    isDef(a.data) === isDef(b.data) &&  
    sameInputType(a, b) // 当标签是<input>的时候，type必须相同
  )
}

function patchVnode(oldVnode, newVnode){
  const el = newVnode.el = oldVnode.el //合并引用
  let i, oldCh = oldVnode.children, ch = newVnode.children
  if (oldVnode === newVnode) return //如果严格一致直接返回
  if (oldVnode.text !== null && newVnode.text !== null && oldVnode.text !== newVnode.text) { // 文本节点处理
    api.setTextContent(el, newVnode.text)
  }else{
    updateEle(el, newVnode, oldVnode) //更新节点
    if (oldCh && ch && oldCh !== ch) {
          updateChildren(el, oldCh, ch)
    }else if (ch){
          createEle(newVnode) 
    }else if (oldCh){
          api.removeChildren(el)
    }
  }
}

function updateChildren(el,newChidlren,OldChidlren){ //挂载父节点

  let oldStartIdx = 0;//老节点的数组开始索引
  let oldEndIdx = OldChidlren.length - 1;  //老节点的数组结束索引
  let newStartIdx = 0;//新节点的数组开始索引
  let newEndIdx = newChidlren.length - 1; //新节点的数组结束索引
  
  let oldStartVnode = OldChidlren[0] //老的开始节点
  let oldEndVnode = OldChidlren[oldEndIdx]//老的结束节点
  let newStartVnode = newChidlren[0]//新的开始节点
  let newEndVnode = newChidlren[newEndIdx] //新的结束节点

  while(oldStartIdx<=oldEndIdx && newStartIdx<=newEndIdx){//结束条件,两组数据都处理完
    if (oldStartVnode == null) {   // 处理空节点
        oldStartVnode = OldChidlren[++oldStartIdx] 
    }else if (oldEndVnode == null) {
        oldEndVnode = OldChidlren[--oldEndIdx]
    }else if (newStartVnode == null) {
        newStartVnode = newChidlren[++newStartIdx]
    }else if (newEndVnode == null) {
        newEndVnode = newChidlren[--newEndIdx] 
        //所有操作其实都是在老列表上进行,整个列表会被分割为已经操作过的节点和未操作的节点两部分
        //操作过的节点组成最后结果列表,未操作过的列表继续作为旧列表进行匹配操作
    }else if(sameVnode(newStartVnode,oldStartVnode )){//头头相等
      patchVnode(newStartVnode,oldStartVnode) //直接合并,处理下一个
      oldStartVnode = OldChidlren[++oldStartIdx]
      newStartVnode = newChidlren[++newStartIdx]
    }else if(sameVnode(newEndVnode,oldEndVnode )){ //尾尾相等
      patchVnode(newEndVnode,oldEndVnode) //直接合并,处理上一个
      oldStartVnode = OldChidlren[--oldEndIdx]
      newStartVnode = newChidlren[--newEndIdx]
    }else if(sameVnode(oldStartVnode, newEndVnode)){ //老头等于新尾
      
      patchVnode(oldStartVnode, newEndVnode)
      api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el)) //则把老头移到最后 这里的头尾都是虚拟头尾,参照双指针区间,不一定是实际列表尾
      oldStartVnode = OldChidlren[++oldStartIdx] //处理下一个老头
      newEndVnode = newChidlren[--newEndIdx]//处理下一个新尾
    }else if(sameVnode(oldEndVnode, newStartVnode)){ //老尾等于新头
      patchVnode(oldEndVnode, newStartVnode)//则吧老尾移到最头

      api.insertBefore(parentElm, oldEndVnode.el,oldStartVnode.el) 
      oldEndVnode = OldChidlren[--oldEndIdx] //处理上一个老尾
      newStartVnode = newChidlren[++newStartIdx]//处理下一个新头
    }else {//进行key值判断
      if (oldKeyToIdx === undefined){
        oldKeyToIdx = createKeyToOldIdx(OldChidlren, oldStartIdx, oldEndIdx) // 创建旧列表哈希表
      }
      idxInOld = oldKeyToIdx[newStartVnode.key] //在旧表中查询是否存在对应的节点
      if(!idxInOld){//不存在符合项
        api.insertBefore(parentElm,createEle(newStartVnode).el,oldStartVnode.el) //把新列表的头节点插入旧表最前面
        newStartVnode = newChidlren[++newStartIdx]//继续处理下一个
      }else{
        elmToMove = oldChidlren[idxInOld]//获取对应的节点
        if (elmToMove.sel !== newStartVnode.sel) {//如果为不为同一个DOM 
          api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)//创建一个插入到头 这里是处理一些key值一样,但实际上还是不一样的节点
        }else{
          patchVnode(elmToMove, newStartVnode)//合并节点
          oldChidlren[idxInOld] = null//旧表对应位置置空
          api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)//把对应节点插入到旧表最头
        }
        newStartVnode = newChidlren[++newStartIdx]//继续处理下一个

      }
      if (oldStartIdx > oldEndIdx) {//旧表全处理完
          before = newChidlren[newEndIdx + 1] == null ? null : newChidlren[newEndIdx + 1].el
          addVnodes(parentElm, before, newChidlren, newStartIdx, newEndIdx)//把新表剩余的剩余元素都插入到旧表后
      }else if (newStartIdx > newEndIdx) {//新表处理完
          removeVnodes(parentElm, oldChidlren, oldStartIdx, oldEndIdx)//把旧表剩余的元素都删除
      }
    }
  }  
}

所有操作其实都是在老列表上进行,整个列表会被分割为已经操作过的节点和未操作的节点两部分
操作过的节点组成最后结果列表,未操作过的列表继续作为旧列表进行匹配操作
之后语境里的头尾都是根据双指针标识出来的待处理段的头尾
判断相等后的两项代表已处理完,指针要移动相应的进行移动,头处理则开始指针后移,尾处理则结束指针前移
判断相等也要执行patchVnode操作合并
头头相等,合并后插入旧表头,指针都后移
尾尾相等,合并后插入旧表尾,指针都前移
老头等于新尾,则把老头移到最后
老尾等于新头,则吧老尾移到最头
头尾都没有相等则以新头进行哈希表比较
没有哈希表要以旧列表key值构建
查到不到则直接新头插入旧表最前,然后新表开始指针后移
查到了,也要进行一下全等判断,确定相等后,把对应的节点移到旧表最开始,并且相应位置节点赋值为undefined.然后新表开始指针后移
为啥要再次进行全等判断呢,因为key值命中一次后,哈希表不会更新,key可能再次命中,而节点已经被移走,还有些key值重复等特殊情况
结束条件
oldS > oldE表示oldChidlren先遍历完，那么就将多余的vCh根据index添加到dom中去
S > E表示newChidlren先遍历完，那么就在真实dom中将区间为[oldS, oldE]的多余节点删掉

上一页LocalStorage存取对象下一页虚拟dom

最后更新于2年前