详解什么是虚拟DOM？以及diff算法

function diff(oldTree, newTree) {
  let index = 0;
  const patches = {};
  dfsWalk(oldTree, newTree, index, patches);
  return patches;
}
function dfsWalk(oldNode, newNode, index, patches) {
  const currentPatch = [];
  if (newNode === null) {
    // 节点被移除
  } else if (typeof oldNode === 'string' && typeof newNode === 'string') {
    // 更新文本节点
    if (oldNode !== newNode) {
      currentPatch.push({ type: 'TEXT', content: newNode });
    }
  } else if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) {
    // 更新相同节点
    const attrs = diffAttr(oldNode.props, newNode.props);
    if (Object.keys(attrs).length > 0) {
      currentPatch.push({ type: 'ATTR', attrs });
    }
    diffChildren(oldNode.children, newNode.children, index, patches, currentPatch);
  } else {
    // 节点完全不同，使用替换操作
    currentPatch.push({ type: 'REPLACE', node: newNode });
  }
  if (currentPatch.length > 0) {
    patches[index] = currentPatch;
  }
}
function diffChildren(oldChildren, newChildren, index, patches, currentPatch) {
  const diffs = listDiff(oldChildren, newChildren, 'key');
  newChildren = diffs.children;
  if (diffs.moves.length > 0) {
    currentPatch.push({ type: 'REORDER', moves: diffs.moves });
  }
  let lastChildIndex = index;
  oldChildren.forEach((child, i) => {
    const newChild = newChildren[i];
    lastChildIndex = (child && child.count) ? lastChildIndex + child.count + 1 : lastChildIndex + 1;
    dfsWalk(child, newChild, lastChildIndex, patches);
  });
}
function diffAttr(oldAttrs, newAttrs) {
  const attrs = {};
  for (const key in oldAttrs) {
    if (oldAttrs[key] !== newAttrs[key]) {
      attrs[key] = newAttrs[key];
    }
  }
  for (const key in newAttrs) {
    if (!oldAttrs.hasOwnProperty(key)) {
      attrs[key] = newAttrs[key];
    }
  }
  return attrs;
}
function listDiff(oldList, newList, key) {
  const oldMap = makeKeyIndexAndFree(oldList, key);
  const newMap = makeKeyIndexAndFree(newList, key);
  const newFree = newMap.free;
  const moves = [];
  const children = [];
  let i = 0;
  let item;
  let itemIndex;
  let freeIndex = 0;
  while (i < oldList.length) {
    item = oldList[i];
    itemIndex = oldMap.keyIndex[item[key]];
    if (itemIndex === undefined) {
      moves.push({ index: i, type: 0 });
    } else {
      children.push(newList[itemIndex]);
      newMap.keyIndex[item[key]] = undefined;
    }
    i++;
  }
  let simulateList = children.slice();
  i = 0;
  while (i < simulateList.length) {
    item = simulateList[i];
    itemIndex = newMap.keyIndex[item[key]];
    if (itemIndex !== undefined) {
      if (freeIndex === itemIndex) {
        freeIndex++;
      } else {
        children.splice(i, 0, newFree[itemIndex]);
        moves.push({ index: i, type: 1, item: newFree[itemIndex] });
        newFree[itemIndex] = undefined;
      }
    } else {
      moves.push({ index: i, type: 0 });
    }
    i++;
  }
  let lastFreeIndex = 0;
  for (const key in newFree) {
    if (newFree.hasOwnProperty(key)) {
      if (newFree[key] !== undefined) {
        children.push(newFree[key]);
        moves.push({ index: children.length - 1, type: 1, item: newFree[key] });
      }
    }
  }
  moves.sort((a, b) => a.index - b.index);
  return { children, moves };
}
function makeKeyIndexAndFree(list, key) {
  const keyIndex = {};
  const free = [];
  for (let i = 0, len = list.length; i < len; i++) {
    const item = list[i];
    if (item[key] !== undefined) {
      keyIndex[item[key]] = i;
    } else {
      free.push(item);
    }
  }
  return { keyIndex, free };
}