专栏目录请点击

简介

1. 把属性结构按照层级进行分解，只比较同级元素
2. 他包括虚拟dom的对比，以及对比之后更新真实dom

过程

1. diff算法中充满了递归，整个递归的过程patch ==> patchVnode ==> updateChildren==> patchVnode==> updateChildren —>patchVnode的递归循环
2. 其中key是为了标识两个节点是不是同一个虚拟节点
   • 是的话就要判断子节点是不是同一节点
   • 不是的话继续比较
3. 如果不加key的话，如果两个不同节点的标签名恰好相同，那么就会被判定为同一个节点
   • 对比中发现子节点不一样，那么就会凭空增加很多真实的DOM操作，增加回流和重绘

源码

patch

// patch.js
​
import vnode from "./vnode"
import patchDetails from "./patchVnode"
import createEle from "./createEle"
​
/**
 * @description 用来对比两个虚拟dom的根节点，并根据对比结果操作真实Dom
 * @param {*} oldVnode 
 * @param {*} newVnode 
 */
export function patch(oldVnode, newVnode) {
  // 1.判断oldVnode是否为虚拟节点，不是的话转化为虚拟节点
  if(!oldVnode.sel) {
    // 转化为虚拟节点
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
  }
​
  // 2.判断oldVnode和newVnode是否为同一个节点
  if(oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
    console.log('是同一个节点')
    // 比较子节点
    patchDetails(oldVnode, newVnode)
  }else {
    console.log('不是同一个节点')
    // 插入newVnode 
    const newNode = createEle(newVnode) // 插入之前需要先将newVnode转化为dom
    oldVnode.elm.parentNode.insertBefore(newNode, oldVnode.elm) // 插入操作
    // 删除oldVnode
    oldVnode.elm.parentNode.removeChild(oldVnode.elm)
  }
}
​
// createEle.js
​
/**
 * @description 根据传入的虚拟Dom生成真实Dom
 * @param {*} vnode 
 * @returns real node
 */
export default function createEle (vnode) {
  const realNode = document.createElement(vnode.sel)
​
  // 子节点转换
  if(vnode.text && (vnode.children == undefined || (vnode.children && vnode.children.length == 0)) ) {
    // 子节点只含有文本
    realNode.innerText = vnode.text  
  }else if(Array.isArray(vnode.children) && vnode.children.length > 0) {
    // 子节点为其他虚拟节点 递归添加node
    for(let i = 0; i < vnode.children.length; i++) {
      const childNode = createEle(vnode.children[i])
      realNode.appendChild(childNode)
    }
  }
​
  // 补充vnode的elm属性
  vnode.elm = realNode
​
  return vnode.elm
}

patchVnode

• 用来比较两个虚拟节点的子节点并更新其子节点对应的真实Dom节点

// patchVnode.js
​
import updateChildren from "./updateChildren"
import createEle from "./createEle"
​
/**
 * @description 比较两个虚拟节点的子节点（children or text） 并更新其子节点对应的真实dom节点
 * @param {*} oldVnode 
 * @param {*} newVnode 
 * @returns 
 */
export function patchDetails(oldVnode, newVnode) {
  // 判断oldVnode和newVnode是否为同一个对象, 是的话直接不用比了
  if(oldVnode == newVnode) return 
​
  // 默认newVnode和oldVnode只有text和children其中之一，真实的源码这里的情况会更多一些，不过大同小异。
​
  if(hasText(newVnode)) {
    // newVnode有text但没有children
​
    /**
     *  newVnode.text !== oldVnode.text 直接囊括了两种情况
     *  1.oldVnode有text无children 但是text和newVnode的text内容不同
     *  2.oldVnode无text有children 此时oldVnode.text为undefined 
     *  两种情况都可以通过innerText属性直接完成dom更新 
     *  情况1直接更新text 情况2相当于去掉了children后加了新的text
     */
    if(newVnode.text !== oldVnode.text) {
      oldVnode.elm.innerText = newVnode.text
    }
​
  }else if(hasChildren(newVnode)) {
    // newVnode有children但是没有text
    
    if(hasText(oldVnode)) {
      // oldVnode有text但是没有children
      
      oldVnode.elm.innerText = '' // 删除oldVnode的text
      // 添加newVnode的children
      for(let i = 0; i < newVnode.children.length; i++) {
        oldVnode.elm.appendChild(createEle(newVnode.children[i]))
      }
​
    }else if(hasChildren(oldVnode)) {
      // oldVnode有children但是没有text
​
      // 对比两个节点的children 并更新对应的真实dom节点
      updateChildren(oldVnode.children, newVnode.children, oldVnode.elm)
    }
  }
}
​
// 有children没有text
function hasChildren(node) {
  return !node.text && (node.children && node.children.length > 0)
} 
​
// 有text没有children
function hasText(node) {
  return node.text && (node.children == undefined || (node.children && node.children.length == 0))
} 

updateChildren

这个方法是diff算法的核心，当patchVnode的参数oldVnode和newVnode都有children的时候就会调用到此方法

过程

1. 在对比过程中会引入四个指针
   1. 指向oldVnode子节点列表第一个节点和最后一个节点的两个指针(简称旧前和旧后)
   2. 指向newVnode子节点列表第一个节点和最后一个节点的两个指针(简称新前和新后)
2. 每一次对比按照一下顺序进行
   1. 旧前与新前对比
   2. 旧后与新后对比
   3. 旧前与新后对比
   4. 旧后与新前对比
3. 命中
   1. 对比中两个指针对应的虚拟dom相同，那么就是命中了
   2. 命中后，不会在查找，而是移动指针
   3. 但是也有可能操作真实的DOM，比如第三点和第四点
   4. 命中后会开始新的查找
4. 终止条件
   1. 旧前指针移动到旧后指针的后面
   2. 或者新前指针移动到新后指针的后面
   3. 这个时候我们可以理解为算法对比结束，但是结束后可能存在没有处理完的情景
5. 没有处理完的情景
   1. 如果旧子节点先处理完了，新子节点有剩余，说明有要新增的节点。将根据最终新前和新后之间的虚拟节点执行插入操作
   2. 如果新子节点先处理完了，旧子节点有剩余，说明有要删除的节点。将根据最终旧前和旧后之间的虚拟节点执行删除操作

例子

假设我们在DOM中插入了一个b的li节点，那么在diff算法中他是如何进行比较的呢

1. 同级比对。我们知道在diff算法中只对于同级的节点进行对比
   
2. 那么，上面的DOM结构，在算法中会进行如下的对比。
3. 首先旧前a会与新前b进行比较，没有比对成功
4. 那么旧前a会与新后a进行比较，发现比对成功，这个时候会做如下操作
5. 做如下几个操作
   1. 真实dom结构变动，将a节点移到与newVnode相同的位置
   2. 旧前指针往后移动一个(移动到新的节点，因为当前所指的节点已经匹配成功)
   3. 新后指针往前移动一个(移动到新的节点，因为当前所指的节点已经匹配成功)
6. 再次进行比对旧前b与新前b进行比对.，发现比对成功，那么做如下几个操作
   1. 真实dom结构变动。真实dom中的b与新节点b对齐
   2. 然后进行指针的移动
7. 然后再次进行比对，再次进行上面的四个对比中的旧前与新前进行比对，发现比对成功，再次进行移动到如下位置
8. 这个时候旧前已经跑到了旧后的后面，那么比对结束。
9. 这个时候我们会发现旧节点处理完毕，但是新的节点还有剩余，这个时候我们会看新前和新后指针指向的虚拟节点，他们之间的虚拟节点就是新插入的节点
10. 这个时候把 虚拟节点直接放入真是dom中就可以了
11. 上面大概就是虚拟dom的diff算法的一个简单的效果成，我们可以看下面的源码，看具体的过程

// updateChildren.js
​
import patchDetails from "./patchVnode"
import createEle from "./createEle";
​
/**
 * @description 对比子节点列表并更新真实Dom
 * @param {*} oldCh 旧虚拟Dom子节点列表 
 * @param {*} newCh 新虚拟Dom子节点列表 
 * @param {*} parent 新旧虚拟节点对应的真实Dom
 * @returns 
 */
​
export default function updateChildren(oldCh, newCh, parent) {
  // 定义四个指针 旧前 旧后 新前 新后 （四个指针两两一对，每一对前后指针所指向的节点以及其之间的节点为未处理的子节点）
  let oldStartIndex = 0;
  let oldEndIndex = oldCh.length - 1;
  let newStartIndex = 0;
  let newEndIndex = newCh.length - 1;
​
  // 四个指针对应的节点
  let oldStartNode = oldCh[oldStartIndex];
  let oldEndNode = oldCh[oldEndIndex];
  let newStartNode = newCh[newStartIndex];
  let newEndNode = newCh[newEndIndex];
​
  // oldCh中每个子节点 key 与 index的哈希表 用于四种对比规则都不匹配的情况下在oldCh中寻找节点
  const keyMap = new Map();
​
  /**
   * 开始遍历两个children数组进行细节对比
   * 对比规则：旧前-新前 旧后-新后 旧前-新后 旧后-新前
   * 对比之后指针进行移动
   * 直到指针不满足以下条件 意味着有一对前后指针之间再无未处理的子节点 则停止对比 直接操作DOM
   */
​
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // 这四种情况是为了让指针在移动的过程中跳过空节点
    if (oldStartNode == undefined) {
      oldStartNode = oldCh[++oldStartIndex];
    } else if (oldEndNode == undefined) {
      oldEndNode = oldCh[--oldEndIndex];
    } else if (newStartNode == undefined) {
      newStartNode = newCh[++newStartIndex];
    } else if (newEndNode == undefined) {
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newStartNode)) {
      console.log("method1");
      // 旧前-新前是同一个虚拟节点
​
      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldStartNode, newStartNode);
      // 指针移动
      oldStartNode = oldCh[++oldStartIndex];
      newStartNode = newCh[++newStartIndex];
    } else if (isSame(oldEndNode, newEndNode)) {
      console.log("method2");
      // 旧后-新后是同一个虚拟节点
​
      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldEndNode, newEndNode);
      // 指针移动
      oldEndNode = oldCh[--oldEndIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newEndNode)) {
      console.log("method3");
      // 旧前-新后是同一个虚拟节点
​
      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldStartNode, newEndNode);
​
      /**
       *  这一步多一个移动(真实)节点的操作
       *  需要把当前指针所指向的子节点 移动到 oldEndIndex所对应真实节点之后（也就是未处理真实节点的尾部）
       *  注意：这一步是在操作真实节点
       */
      parent.insertBefore(oldStartNode.elm, oldEndNode.elm.nextSibling);
​
      // 指针移动
      oldStartNode = oldCh[++oldStartIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldEndNode, newStartNode)) {
      console.log("method4");
      // 旧后-新前 是同一个虚拟节点
​
      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldEndNode, newStartNode);
      /**
       *  这一步多一个移动(真实)节点的操作
       *  与method3不同在移动位置
       *  需要把当前指针所指向的子节点 移动到 oldStartIndex所对应真实节点之前（也就是未处理真实节点的顶部）
       *  注意：这一步是在操作真实节点
       */
      parent.insertBefore(oldEndNode.elm, oldCh[oldStartIndex].elm);
​
      // 指针移动
      oldEndNode = oldCh[--oldEndIndex];
      newStartNode = newCh[++newStartIndex];
    } else {
      console.log("does not match");
      // 四种规则都不匹配
​
      // 生成keyMap
      if (keyMap.size == 0) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
          if (oldCh[i].key) keyMap.set(oldCh[i].key, i);
        }
      }
​
      // 在oldCh中搜索当前newStartIndex所指向的节点
      if (keyMap.has(newStartNode.key)) {
        // 搜索到了
​
        // 先获取oldCh中该虚拟节点
        const oldMoveNode = oldCh[keyMap.get(newStartNode.key)];
        // 两个子节点再对比他们的子节点并更新dom （递归切入点）
        patchDetails(oldMoveNode, newStartNode);
​
        // 移动这个节点（移动的是真实节点）
        parent.insertBefore(oldMoveNode.elm, oldStartNode.elm);
​
        // 该虚拟节点设置为undefined（还记得最开始的四个条件吗，因为这里会将子节点制空，所以加了那四个条件）
        oldCh[keyMap.get(newStartNode.key)] = undefined;
          
      } else {
        // 没搜索到 直接插入
        parent.insertBefore(createEle(newStartNode), oldStartNode.elm);
      }
​
      // 指针移动
      newStartNode = newCh[++newStartIndex];
    }
  }
​
  /**
   * 插入和删除节点
   * while结束后 有一对前后指针之间仍然有未处理的子节点，那么就会进行插入或者删除操作
   * oldCh的双指针中有未处理的子节点，进行删除操作
   * newCh的双指针中有未处理的子节点，进行插入操作
   */
  if (oldStartIndex <= oldEndIndex) {
    // 删除
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
      // 加判断是因为oldCh[i]有可能为undefined
      if(oldCh[i]) parent.removeChild(oldCh[i].elm);
    }
  } else if (newStartIndex <= newEndIndex) {
    /**
     * 插入
     * 这里需要注意的点是从哪里插入，也就是appendChild的第二个参数
     * 应该从oldStartIndex对应的位置插入
     */
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      // oldCh[oldStartIndex]存在是从头部插入
      parent.insertBefore(createEle(newCh[i]), oldCh[oldStartIndex] ? oldCh[oldStartIndex].elm : undefined);
    }
  }
}
​
// 判断两个虚拟节点是否为同一个虚拟节点
function isSame(a, b) {
  return a.sel == b.sel && a.key == b.key;
}