这篇文章上次修改于 268 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

         上一章我们首次将虚拟dom挂载到了页面上,这一章将讲讲Vnode的diff算法,采用的的同级比较,不会跨级,用到算法是深度优先遍历,具体看看图:

diff算法

和源码不同的是,我是自己调用patch方法进行下面的操作的,不是组件data状态发生改变而引起的diff,重点在算法上,这点就不纠结了。

首先,需要手动去触发patch方法

patch(oldVnode, newVnode);

实现patch方法

patch方法接收俩参数,老的节点(oldVNode)和新的节点(newVNode),当然,这两个节点是位置对应的。

patch时分两种情况:

  • 节点类型不一样,直接重建替换oldVNode
  • 节点类型一样

    • 判断类型是否为文本节点(类型都为undefined, 所以会判断类型相同)
    • 节点类型存在且相同, 只需要更新真实dom元素上的属性,和children

      • 先比较属性是否更新,调用updateDomProperties方法
      • 比较children节点(三种情况)

        • a、新的节点没有,老的节点有,直接删除老的
        • b、新的节点有,老节点的没有,直接添加新的
        • c、新的节点、老的节点均有儿子,需要调用updateChildrenNode比较(核心内容

代码实现:

function patch(oldVNode, newVNode) {
  // 1、节点类型不一样, 直接重建(替换节点)
  if(oldVNode.tag !== newVNode.tag) {
    return oldVNode.domElement.parentNode.replaceChild(createNewDomElement(newVNode), oldVNode.domElement);
  }
  // 2、判断是否为文本节点,直接更新
  if(typeof newVNode.text !== 'undefined') {
    return oldVNode.domElement.textContent = newVNode.text;
  }
  // 3、节点类型相同, 只需要更新真实dom(oldVNode.domElement)元素上的属性,和children Dom
  // 3.1、先比较属性
  let domElement = newVNode.domElement = oldVNode.domElement;
  updateDomProperties(newVNode, oldVNode.props);
  // 3.2、比较更新children节点
  let newChildren = newVNode.children;
  let oldChildren = oldVNode.children;
  let newCLen = newChildren.length;
  let oldCLen = oldChildren.length;
  if(newCLen > 0 && oldCLen > 0) { //(最复杂的情况)
    updateChildrenNode(domElement, newChildren, oldChildren);
  }else if(newCLen > 0) {
    for(let newChild in newChildren) {
      domElement.appendChild(createNewDomElement(newChild));
    }
  } else if(oldCLen > 0) {
    domElement.innerHTML = '';
  }
}

实现updateChildrenNode方法(核心)

1、首先定义oldChildrennewChildren的开始、结束节点和开始、结束索引

// 新、老的开始索引和开始节点
let oldStartIndex = 0, oldStartVNode = oldChildren[0];
let newStartIndex = 0, newStartVNode = newChildren[0];
// 新、老的结束索引和结束节点
let oldEndIndex = oldChildren.length - 1, oldEndVNode = oldChildren[oldEndIndex];
let newEndIndex = newChildren.length - 1, newEndVNode = newChildren[newEndIndex];

2、接着循环比较新、老节点所有儿子节点,若儿子还有儿子,就接着patch,这就是深度优先遍历,先从上到下,再从左到右。儿子的儿子先不管,原理都一样,我们就看当前新、老节点所有儿子节点,就是儿子节点的所有兄弟节点。跳出循环的条件是oldChildren或者newChildren的开始索引大于结束索引:

 while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    ......
 }

循环结束后,又分两种情况

  • 老的儿子队列处理完了,新的还没有, 则添加到老的儿子队列中,并创建新的儿子节点的real dom
  • 新的儿子队列处理完了,老的还没有, 则删除老的节点
// 循环结束。
 if (oldStartIndex >= oldEndIndex) { // 老的儿子队列处理完了,新的还没有, 则添加
   // 若 newEndIndex+1 的节点存在的话,说明该节点已经被更新为了真实dom(因为尾索引前移了),把其他的兄弟节点按顺序插到该节点前面就ok了
   // 若不存在,则说明最后节点和索引从定义开始就没改变过,值为null则插入到父节点下,兄弟节点的末尾
   let beforeDOMElement = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].domElement;
     for (let i = newStartIndex; i <= newEndIndex; i++) {
       parentElement.insertBefore(createNewDomElement(newChildren[i]), beforeDOMElement);
     }
 }


 if(newStartIndex >= newEndIndex) { //新的儿子队列处理完了,老的还没有, 则删除
   for (let i = oldStartIndex; i <= oldEndIndex; i++) {
     parentElement.removeChild(oldChildren[i].domElement);
   }
 }

节点比较分五种情况:

判断的调用的oldSameNewNode 是判断两节点的类型tagkey是否都相同,相同则执行if里的操作

下面说到的dom节点均为real dom节点

①、新、老儿子对列,头节点和头节点类型相同

  • patch新、老队列的开始节点
  • 两队列的开始、结束索引和节点,都后移一位

具体代码实现

if (oldSameNewNode(oldStartVNode, newStartVNode)) { // 新、老儿子对列,头节点和头节点比较
  patch(oldStartVNode, newStartVNode); // patch新老队列的开始节点
  oldStartVNode = oldChildren[++oldStartIndex];
  newStartVNode = newChildren[++newStartIndex];
}

②、新、老儿子对列,尾节点和尾节点类型相同

  • patch新、老队列的结束节点
  • 两队列的开始、结束索引和节点,都前移移一位

具体代码实现

if(oldSameNewNode(oldEndVNode, newEndVNode)){ // 新、老儿子对列,尾节点和尾节点比较
  patch(oldEndVNode, newEndVNode);
  oldEndVNode = oldChildren[--oldEndIndex];
  newEndVNode = newChildren[--newEndIndex];
}

③、新的儿子对列结束节点,与老的儿子对列开始节点类型相同,

  • patch老队列的开始节点、新的结束节点
  • 将更新后的dom节点,插到老的队列结束dom节点的后面
  • 老儿子队列的开始索引和开始节点后移一位,新儿子队列的开始索引和开始节点前移一位

具体代码实现

if(oldSameNewNode(oldStartVNode, newEndVNode)) { // 新的儿子对列尾节点,与老的儿子对列头节点比较
  patch(oldStartVNode, newEndVNode);
  parentElement.insertBefore(oldStartVNode.domElement,oldEndVNode.domElement.nextSibling);
  oldStartVNode = oldChildren[++oldStartIndex];
  newEndVNode = newChildren[--newEndIndex];
}

④、新的儿子对列开始节点,与老的儿子对列结束节点类型相同

  • patch老队列的结束节点、新的开始节点
  • 将更新后的dom节点,插到老的队列开始节点的前面
  • 老儿子队列的开始索引和开始节点前移一位,新儿子队列的开始索引和开始节点后移一位。

具体代码实现

if (oldSameNewNode(oldEndVNode, newStartVNode)) {// 新的儿子对列头节点,与老的儿子对列尾节点比较
  patch(oldEndVNode, newStartVNode);
  parentElement.insertBefore(oldEndVNode.domElement, oldStartVNode.domElement);
  oldEndVNode = oldChildren[--oldEndIndex];
  newStartVNode = newChildren[++newStartIndex];
}

⑤、该种毫无规律可言,若前四种优化选择项均不满足,就要key值来处理节点的比较,首先需要取得老的儿子队列每个节点的key存到一个对象里,键为key,键值为索引。然后新的儿子队列从开始索引的节点,用key在老队列key组成的对象检索该key是否存在。

  • key不存在,直接将该节点,插到老的儿子队列的开始节点的前面,并创建该Vnodereal dom
  • key存在,就要判断tag类型是否相同

    • tag类型不同,视为新节点,直接创建该Vnodereal dom,并插入到老的儿子队列的开始节点的前面
    • tag类型也相同,就要patch这俩相同节点,然后用结合key值(索引)找到该节点在oldChildren的索引位置,然后将该节点的dom,移动到老的队列开始节点的前面,最后将节点置为undefined.

新的儿子队列,开始索引和开始节点后移一位。

具体代码实现

else {
  // 判断新的Vnode的key是否存在老的Vnode的兄弟节点上
  let newVnodekeyInOld = oldKeyIndexMap[newStartVNode.key];
  if(newVnodekeyInOld == undefined) { // key不存在,直接将该Vnode更新为真实的dom
    parentElement.insertBefore(createNewDomElement(newStartVNode), oldStartVNode.domElement);
  } else { // key存在
    let needToMoveOldVnode = oldChildren[newVnodekeyInOld];
    if(needToMoveOldVnode.tag !== newStartVNode.tag){ // key同,类型不同,视为新节点,需插入
      parentElement.insertBefore(createNewDomElement(newStartVNode), oldStartVNode.domElement);
    } else { // key同,类型同,视为相同节点,先diff该节点和其儿子节点,在移动该节点,最后将该索引位置置为undefined
      patch(needToMoveOldVnode, newStartVNode);
      oldChildren[newVnodekeyInOld] = undefined;
      parentElement.insertBefore(needToMoveOldVnode.domElement, oldStartVNode.domElement);
    }
  }
  newStartVNode = newChildren[++newStartIndex];
}

注意:因老的节点dom,发生了移动,移动前的Vnode被置为了undefined,所以需在这五种判断前再加两层判断

if(!oldEndVNode) {
  oldEndVNode = oldChildren[--oldEndIndex];  // 该索引处节点被移动了,改为上一个索引节点
}else if(!oldStartVNode){
  oldStartVNode = oldChildren[++oldStartIndex]; // 该索引处节点被移动了,改为下一个索引节点
}

下面举个复杂的例子,熟悉一下整个过程

a、先前四种情况均不满足,则进行判断五,发现key也不存在,则将新E插到老A前,新的队列箭头后移(开始节点、索引后移)(1过程)

b、新B也满足判断五,则更新老B,并将老B插到老A之前,原老B置为undefined,新儿子队列箭头后移(2、3过程)

c、新A满足判断一,更新老A,两队列的开始索引和节点,都后移一位,此时新队列的开始箭头在新D,老队列的开始箭头在老B,而老Bundefined,开始箭头又移动到了老C上(4过程)

d、新D和b过程一样,更新D,插到老C之前,移动前老D Vnode置为undefined,新儿子队列箭头后移

e、新`F同a过程,将创建Freal dom,插到老C前,新队列箭头后移,while`循环结束(7)

f、删除老C

总结

一个简单的dom diff就实现了,可能讲的不太明白,可以看看vue源码的实现