手写diff算法

一、diff算法原理

最小量更新，key是这个节点的唯一标识，高度diff算法，在更改前后它们是同一个DOM节点。
只有同一个虚拟节点，才进行精细化比较，否则就是暴力删除旧的，插入新的。
问题：如何定义是同一个虚拟节点？
答：选择器相同，且key相同。
只进行同层比较，不会进行跨层比较。即使是同一片虚拟节点，但是跨层了，diff就是暴力删除旧的，然后插入新的。

• 旧节点的key要和新节点的key相同
• 旧节点的选择器要和新节点的选择器相同

3. 源码中创建子节点需要递归
   

二、手写diff，首次上DOM树patch(container,myVnodel)

（一）前置知识

1. Node.insertBefore()

2. Node.appendChild()

element.appendChild(aChild)

将一个节点附加到指定父节点的子节点列表的末尾处。
如果将被插入的节点已经存在于当前文档的文档树中，那么appendChild()只会将它从原先的位置移动到新的位置（不需要事先移除要移动的节点）。

3. Element.tagName
   返回当前元素的标签名

elementName = element.tagName

elementName是一个字符串，包含了element元素的标签名。
在HTML文档中，tagName会返回其大写形式。

4. Node.removeChild
   从DOM中删除一个子节点。返回删除的节点

let oldChild = node.removeChild(child)
// or
element.removeChild(child)

child是要移除的那个子节点。
node是child的父节点，
oldChild保存对删除的子节点的引用。oldChild === child

5. document.createElement

var element = document.createElement(tagName[, options])

tagName：指定要创建元素类型的字符串，创建元素时的nodeName使用tagName的值为初始化，该方法不允许使用限定名称（如：“html:a”），在html文档上调用createElement()方法创建元素之前会将tagName转化为小写，在Firefox、Opera和Chrome内核中，createElement(null)等同于createElement(“null”)
返回：新建的元素（Element）

（二）处理新旧节点不是同一个节点的情况

1. patch.js

import vnode from './vnode'
import createElement from './createElement'

export default function(oldVnode, newVnode) {
    // 判断传入的第一个参数是DOM节点还是 虚拟节点
    if (oldVnode.sel == '' || oldVnode.sel === undefined) {
        // 说明oldVnode是DOM节点，此时要包装成虚拟节点
        oldVnode = vnode(
            oldVnode.tagName.toLowerCase(), // sel
            {}, // data
            [], // children
            undefined, // text
            oldVnode // elm
        );
    }
    // 判断oldVnode和newVnode是不是同一个节点（key相同，并且选择器相同）
    if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
        console.log('是同一个节点，需要精细化比较');
    } else {
        console.log('不是同一个节点，暴力 插入新节点，删除旧节点');
        // 创建新虚拟节点 为DOM 节点
        // 要操作DOM ，所以都要转换为DOM节点
        let newVnodeElm = createElement(newVnode);
        let oldVnodeElm = oldVnode.elm;
        // 插入新节点到 旧节点之前
        if (newVnodeElm) {
            oldVnodeElm.parentNode.insertBefore(newVnodeElm, oldVnodeElm);
        }
        // 删除旧节点
        oldVnodeElm.parentNode.removeChild(oldVnodeElm);
    }
}

2. createElement.js

// 创建节点。将vnode虚拟节点创建为DOM节点
/**
 * 是孤儿节点，不进行插入操作
 * @param {object} vnode
 */
export default function createElement(vnode) {
    // 根据虚拟节点选择器属性  创建一个DOM节点，这个节点现在是孤儿节点
    let domNode = document.createElement(vnode.sel)
        // 判断是有子节点还是有文本
    if (vnode.text !== '' && (vnode.children === undefined || vnode.children.length === 0)) {
        // 说明没有子节点，内部是文本
        domNode.innerText = vnode.text;
    } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        // 说明内部是子节点，需要递归创建节点
        // 遍历数组
        for (let ch of vnode.children) {
            // 递归调用 创建出它的dom,一旦调用createElement 意味着创建出dom了。并且它的elm属性指向了创建出的dom,但是没有上树，是一个孤儿节点
            let chDOM = createElement(ch) // 得到 子节点 表示的 DOM节点，递归最后返回的一定是文本节点
            console.log(ch);
            // 文本节点 上domNode树
            domNode.appendChild(chDOM);
        }
    }
    // 补充虚拟节点的elm属性
    vnode.elm = domNode

    // 返回domNode DOM 对象
    return domNode;
}

3. index.js

// 测试 手写的diff 算法-------------------------------------
import h from './mysnabbdom/h'
import patch from './mysnabbdom/patch'
let container = document.getElememtById('container')
let btn = document.getElementById('btn')
const myVnode5 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
]);
// 上树
patch(container, myVnode5)
// 测试 手写的diff 算法-------------------------------------

结果：

（三）处理新旧节点是同一个节点的情况

大致思路：

1. 实现新旧节点text不同情况
   ① patch.js

// 判断oldVnode和newVnode是不是同一个节点（key相同，并且选择器相同）
if(oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
    console.log('是同一个节点，需要精细化比较');
    patchVNode(oldVnode, newVnode);
}

② patchVnode.js

import createElement from "./createElement";

// 精细化比较
export default function patchVnode(oldVnode, newVnode) {
    // 1.判断新旧vnode 是否是同一个对象
    if (oldVnode === newVnode) return;
    // 2.判断newVnode有没有text属性
    if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
        // newVnode 有text 属性
        // 2.1 判断newVnode 与 oldVnode的text属性是否相同
        if (newVnode.text !== oldVnode.text) {
            // 如果不同，那么直接让新text写入老elm中即可
            // 如果oldVnode中是children，也会立即消失
            oldVnode.elm.innerText = newVnode.text;
        }
    } else {
        // newVnode 没有text属性，有children属性
        // 2.2 判断oldVnode 有没有children 属性
        if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
            // oldVnode 有children 属性，最复杂的情况，新老节点都有children

        } else {
            // oldVnode 没有children属性，说明有text;newVnode有children属性
            oldVnode.elm.innerHTML = '';
            // 遍历新的vnode虚拟节点的子节点，创建DOM,上树。
            for (let ch of newVnode.children) {
                let chDOM = createElement(ch);
                oldVnode.elm.appendChild(chDOM);
            }
        }
    }
}

③ index.js

import h from "./my_snabbdom/h";
import patch from "./my_snabbdom/patch";

let container = document.getElementById("container");
let btn = document.getElementById("btn");

const myVnode1 = h("h1", {}, "你好");

// 上树
patch(container, myVnode1);

const myVnode2 = h("ul", {}, [
  h("li", {}, "A"),
  h("li", {}, "B"),
  h("li", {}, "C"),
  h("li", {}, "D"),
]);

btn.onclick = function () {
  patch(myVnode1, myVnode2);
}

结果：

（四）分析diff算法 更新子节点 操作（重点）

此种情况是一种最为复杂的情况。也就是上述思路图中的五角星的位置。

四种命中查找：
① 新前与旧前
② 新后与旧后
③ 新后与旧前（此种发生了：涉及移动节点，那么新前指向的节点，移动的旧后之后）
④ 新前与旧后（此种发生了：涉及移动节点，那么新前指向的节点，移动的旧前之前）
命中一种就不再进行命中判断了。
如果都没有命中，就需要用循环来寻找了。移动到oldStartIdx之前。

1. 循环四种命中查找

① 比较①新前newStart与旧前oldStart

如果命中①了，patch之后就移动头指针 newStart++，oldStart++。

if (checkSameVnode(oldStartVnode, newStartVnode)) {
    // 新前与旧前
    console.log(" ①1 新前与旧前 命中");
    // 精细化比较两个节点 oldStartVnode现在和newStartVnode一样了
    patchVnode(oldStartVnode, newStartVnode);
    // 移动指针，改变指针指向的节点，这表示这两个节点都处理（比较）完了
    oldStartVnode = oldCh[++oldStartIdx];
    newStartVnode = newCh[++newStartIdx];
}

如果没命中，就接着比较下一中情况。

② 比较②新后newEnd 与旧后oldEnd

如果命中②了，patch后就移动尾指针 newEnd–，oldEnd-- 。

if (checkSameVnode(oldEndVnode, newEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode);
    oldEndVnode = oldCh[--oldEndIdx];
    newEndVnode = newCh[--newEndIdx];
}

如果没命中，就接着比较下一种情况。

③ 比较③ 新后newEnd 与旧前 oldStart

如果命中③了，将 新后 newEnd 指向的节点移动到 旧后oldEnd 之后。

if (checkSameVnode(oldStartVnode, newEndVnode)) {
    // 新后与旧前
    console.log(" ③3 新后与旧前 命中");
    patchVnode(oldStartVnode, newEndVnode);
    // 当③新后与旧前命中的时候，此时要移动节点。移动 新后（旧前） 指向的这个节点到老节点的 旧后的后面
    // 移动节点：只要插入一个已经在DOM树上 的节点，就会被移动
    parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
    oldStartVnode = oldCh[++oldStartIdx];
    newEndVnode = newCh[--newEndIdx];
}

命中③复杂情况举例：倒序

如果没命中，就接着比较下一种情况。

④ 比较④新前newStart 与 旧后oldEnd

如果命中④了，将 新前newStart 指向的节点，移动到 旧前oldStart 之前。

if (checkSameVnode(oldEndVnode, newStartVnode)) {
    // 新前与旧后
    console.log(" ④4 新前与旧后 命中");
    patchVnode(oldEndVnode, newStartVnode);
    // 当④新前与旧后命中的时候，此时要移动节点。移动 新前（旧后） 指向的这个节点到老节点的 旧前的前面
    // 移动节点：只要插入一个已经在DOM树上的节点，就会被移动
    parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
    oldEndVnode = oldCh[--oldEndIdx];
    newStartVnode = newCh[++newStartIdx];
}

如果没命中，就表示四种情况都没有命中。

⑤ 四种都没命中， 遍历oldVnode中的key

找到了就移动位置，移动指针newStart++。

没找到的就是新节点，直接插入到所有未处理旧节点之前。

// 四种都没有匹配到，都没有命中
console.log("四种都没有命中");
// 寻找 keyMap 一个映射对象， 就不用每次都遍历old对象了
if (!keyMap) {
  keyMap = {};
  // 记录oldVnode中的节点出现的key
  // 从oldStartIdx开始到oldEndIdx结束，创建keyMap
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    const key = oldCh[i].key;
    if (key !== undefined) {
      keyMap[key] = i;
    }
  }
}
console.log(keyMap);
// 寻找当前项（newStartIdx）在keyMap中映射的序号
const idxInOld = keyMap[newStartVnode.key];
if (idxInOld === undefined) {
  // 如果 idxInOld 是 undefined 说明是全新的项，要插入
  // 被加入的项（就是newStartVnode这项)现不是真正的DOM节点
  parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
} else {
  // 说明不是全新的项，要移动
  const elmToMove = oldCh[idxInOld];
  patchVnode(elmToMove, newStartVnode);
  // 把这项设置为undefined，表示我已经处理完这项了
  oldCh[idxInOld] = undefined;
  // 移动，调用insertBefore也可以实现移动。
  parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
}

// newStartIdx++;
newStartVnode = newCh[++newStartIdx];

2. 循环结束

① 结束后，newVnode中若还有剩余

新节点中剩余的都插入 旧节点oldEnd后 或 oldStart之前。

② 结束后，oldVnode中若还有剩余节点

// 循环结束
if (newStartIdx <= newEndIdx) {
  // 说明newVndoe还有剩余节点没有处理，所以要添加这些节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    // insertBefore方法可以自动识别null，如果是null就会自动排到队尾，和appendChild一致
    parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
  }
} else if (oldStartIdx <= oldEndIdx) {
  // 说明oldVnode还有剩余节点没有处理，所以要删除这些节点
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    if (oldCh[i]) {
      parentElm.removeChild(oldCh[i].elm);
    }
  }
}

（五）手写diff更新子节点操作

1. patchVnode.js

// 2.2 判断 oldVnode 有没有 children 属性
if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
  // oldVnode有children属性 最复杂的情况，新老节点都有children
  updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
}

2. updateChildren.js

import createElement from "./createElement";
import patchVnode from "./patchVnode";
/**
 * 
 * @param {object} parentElm Dom节点
 * @param {Array} oldCh oldVnode的子节点数组
 * @param {Array} newCh newVnode的子节点数组
 */
export default function updateChildren(parentElm, oldCh, newCh) {
  console.log("updateChildren()");
  console.log(oldCh, newCh);

  // 四个指针
  // 旧前
  let oldStartIdx = 0;
  // 新前
  let newStartIdx = 0;
  // 旧后
  let oldEndIdx = oldCh.length - 1;
  // 新后
  let newEndIdx = newCh.length - 1;

  // 指针指向的四个节点
  // 旧前节点
  let oldStartVnode = oldCh[0];
  // 旧后节点
  let oldEndVnode = oldCh[oldEndIdx];
  // 新前节点
  let newStartVnode = newCh[0];
  // 新后节点
  let newEndVnode = newCh[newEndIdx];

  let keyMap = null;

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    console.log("**循环中**");
    // 首先应该不是判断四种命中，而是略过已经加了undefined标记的项
    if (oldStartVnode === null || oldCh[oldStartIdx] === undefined) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldEndVnode === null || oldCh[oldEndIdx] === undefined) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newStartVnode === null || newCh[newStartIdx] === undefined) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode === null || newCh[newEndIdx] === undefined) {
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
      // 新前与旧前
      console.log(" ①1 新前与旧前 命中");
      // 精细化比较两个节点 oldStartVnode现在和newStartVnode一样了
      patchVnode(oldStartVnode, newStartVnode);
      // 移动指针，改变指针指向的节点，这表示这两个节点都处理（比较）完了
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
      // 新后与旧后
      console.log(" ②2 新后与旧后 命中");
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
      // 新后与旧前
      console.log(" ③3 新后与旧前 命中");
      patchVnode(oldStartVnode, newEndVnode);
      // 当③新后与旧前命中的时候，此时要移动节点。移动 新后（旧前） 指向的这个节点到老节点的 旧后的后面
      // 移动节点：只要插入一个已经在DOM树上 的节点，就会被移动
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
      // 新前与旧后
      console.log(" ④4 新前与旧后 命中");
      patchVnode(oldEndVnode, newStartVnode);
      // 当④新前与旧后命中的时候，此时要移动节点。移动 新前（旧后） 指向的这个节点到老节点的 旧前的前面
      // 移动节点：只要插入一个已经在DOM树上的节点，就会被移动
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // 四种都没有匹配到，都没有命中
      console.log("四种都没有命中");
      // 寻找 keyMap 一个映射对象， 就不用每次都遍历old对象了
      if (!keyMap) {
        keyMap = {};
        // 记录oldVnode中的节点出现的key
        // 从oldStartIdx开始到oldEndIdx结束，创建keyMap
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key;
          if (key !== undefined) {
            keyMap[key] = i;
          }
        }
      }
      console.log(keyMap);
      // 寻找当前项（newStartIdx）在keyMap中映射的序号
      const idxInOld = keyMap[newStartVnode.key];
      if (idxInOld === undefined) {
        // 如果 idxInOld 是 undefined 说明是全新的项，要插入
        // 被加入的项（就是newStartVnode这项)现不是真正的DOM节点
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
      } else {
        // 说明不是全新的项，要移动
        const elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove, newStartVnode);
        // 把这项设置为undefined，表示我已经处理完这项了
        oldCh[idxInOld] = undefined;
        // 移动，调用insertBefore也可以实现移动。
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
      }

      // newStartIdx++;
      newStartVnode = newCh[++newStartIdx];
    }
  }
  // 循环结束
  if (newStartIdx <= newEndIdx) {
    // 说明newVndoe还有剩余节点没有处理，所以要添加这些节点
    // // 插入的标杆
    // const before =
    //   newCh[newEndIdx + 1] === null ? null : newCh[newEndIdx + 1].elm;
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // insertBefore方法可以自动识别null，如果是null就会自动排到队尾，和appendChild一致
      parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
    }
  } else if (oldStartIdx <= oldEndIdx) {
    // 说明oldVnode还有剩余节点没有处理，所以要删除这些节点
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if (oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm);
      }
    }
  }
}

// 判断是否是同一个节点
function checkSameVnode(a, b) {
  return a.sel === b.sel && a.key === b.key;
}

小结：