2019-12-23

React

35 分钟读完 (大约 5200 个字)

Virtual DOM 与 Diff 算法内容总结

之前我们借住 HcySunYang/vue-design 分了三部分分别介绍了 Virtual DOM 与 diff 算法相关内容，如下

本章是在之前的基础之上，将分散的代码汇总一下，做一下整体上的梳理，也算是一个小小的总结

使用 VNode 来描述真实 DOM

在第一部分当中，我们主要介绍了如何使用 VNode 来描述真实的 DOM，其主要分为五类，分别是 html/svg 元素、组件、纯文本、Fragment 以及 Portal，然后我们使用了 flags 来作为 VNode 的标识，使用位运算符来标记上面五类不同的元素

// flags.js
const VNodeFlags = {
  // html 标签
  ELEMENT_HTML: 1,
  // SVG 标签
  ELEMENT_SVG: 1 << 1,

  // 普通有状态组件
  COMPONENT_STATEFUL_NORMAL: 1 << 2,
  // 需要被keepAlive的有状态组件
  COMPONENT_STATEFUL_SHOULD_KEEP_ALIVE: 1 << 3,
  // 已经被keepAlive的有状态组件
  COMPONENT_STATEFUL_KEPT_ALIVE: 1 << 4,
  // 函数式组件
  COMPONENT_FUNCTIONAL: 1 << 5,

  // 纯文本
  TEXT: 1 << 6,
  // Fragment
  FRAGMENT: 1 << 7,
  // Portal
  PORTAL: 1 << 8
}

// html 和 svg 都是标签元素，可以用 ELEMENT 表示
VNodeFlags.ELEMENT = VNodeFlags.ELEMENT_HTML | VNodeFlags.ELEMENT_SVG

// 普通有状态组件、需要被 keepAlive 的有状态组件、已经被 keepAlice 的有状态组件都是有状态组件，统一用 COMPONENT_STATEFUL 表示
VNodeFlags.COMPONENT_STATEFUL =
  VNodeFlags.COMPONENT_STATEFUL_NORMAL |
  VNodeFlags.COMPONENT_STATEFUL_SHOULD_KEEP_ALIVE |
  VNodeFlags.COMPONENT_STATEFUL_KEPT_ALIVE
  
// 有状态组件 和 函数式组件都是组件，用 COMPONENT 表示
VNodeFlags.COMPONENT =
  VNodeFlags.COMPONENT_STATEFUL | VNodeFlags.COMPONENT_FUNCTIONAL

const ChildrenFlags = {
  // 未知的 children 类型
  UNKNOWN_CHILDREN: 0,
  // 没有 children
  NO_CHILDREN: 1,
  // children 是单个 VNode
  SINGLE_VNODE: 1 << 1,

  // children 是多个拥有 key 的 VNode
  KEYED_VNODES: 1 << 2,
  // children 是多个没有 key 的 VNode
  NONE_KEYED_VNODES: 1 << 3
}

ChildrenFlags.MULTIPLE_VNODES =
  ChildrenFlags.KEYED_VNODES | ChildrenFlags.NONE_KEYED_VNODES

export { VNodeFlags, ChildrenFlags }

辅助创建 VNode 的 h 函数

当我们拥有了 VNode 以后，接下来就需要一个辅助我们创建 VNode 的 h 函数，利用它来生成我们的 VNode 对象

// h.js
import { VNodeFlags, ChildrenFlags } from './flags'

export const Fragment = Symbol()
export const Portal = Symbol()

export function h(tag, data = null, children = null) {
  // 确定 flags
  let flags = null
  if (typeof tag === 'string') {
    flags = tag === 'svg' ? VNodeFlags.ELEMENT_SVG : VNodeFlags.ELEMENT_HTML
  } else if (tag === Fragment) {
    flags = VNodeFlags.FRAGMENT
  } else if (tag === Portal) {
    flags = VNodeFlags.PORTAL
    tag = data && data.target
  } else {
    // 兼容 Vue2 的对象式组件
    if (tag !== null && typeof tag === 'object') {
      flags = tag.functional
        ? VNodeFlags.COMPONENT_FUNCTIONAL // 函数式组件
        : VNodeFlags.COMPONENT_STATEFUL_NORMAL // 有状态组件
    } else if (typeof tag === 'function') {
      // Vue3 的类组件
      flags =
        tag.prototype && tag.prototype.render
          ? VNodeFlags.COMPONENT_STATEFUL_NORMAL // 有状态组件
          : VNodeFlags.COMPONENT_FUNCTIONAL // 函数式组件
    }
  }

  // 确定 childFlags
  let childFlags = null
  if (Array.isArray(children)) {
    const { length } = children
    if (length === 0) {
      // 没有 children
      childFlags = ChildrenFlags.NO_CHILDREN
    } else if (length === 1) {
      // 单个子节点
      childFlags = ChildrenFlags.SINGLE_VNODE
      children = children[0]
    } else {
      // 多个子节点，且子节点使用key
      childFlags = ChildrenFlags.KEYED_VNODES
      children = normalizeVNodes(children)
    }
  } else if (children == null) {
    // 没有子节点
    childFlags = ChildrenFlags.NO_CHILDREN
  } else if (children._isVNode) {
    // 单个子节点
    childFlags = ChildrenFlags.SINGLE_VNODE
  } else {
    // 其他情况都作为文本节点处理，即单个子节点，会调用 createTextVNode 创建纯文本类型的 VNode
    childFlags = ChildrenFlags.SINGLE_VNODE
    children = createTextVNode(children + '')
  }

  // 返回 VNode 对象
  return {
    _isVNode: true,
    flags,
    tag,
    data,
    key: data && data.key ? data.key : null,
    children,
    childFlags,
    el: null
  }
}

function normalizeVNodes(children) {
  const newChildren = []
  // 遍历 children
  for (let i = 0; i < children.length; i++) {
    const child = children[i]
    if (child.key == null) {
      // 如果原来的 VNode 没有key，则使用竖线(|)与该VNode在数组中的索引拼接而成的字符串作为key
      child.key = '|' + i
    }
    newChildren.push(child)
  }
  // 返回新的children，此时 children 的类型就是 ChildrenFlags.KEYED_VNODES
  return newChildren
}

export function createTextVNode(text) {
  return {
    _isVNode: true,
    // flags 是 VNodeFlags.TEXT
    flags: VNodeFlags.TEXT,
    tag: null,
    data: null,
    // 纯文本类型的 VNode，其 children 属性存储的是与之相符的文本内容
    children: text,
    // 文本节点没有子节点
    childFlags: ChildrenFlags.NO_CHILDREN
  }
}

渲染器

在我们在拥有了 VNode 对象以后，就可以利用渲染器来将其渲染到页面当中了，渲染器的工作流程分为两个阶段 mount 和 patch

如果旧的 VNode 存在，则会使用新的 VNode 与旧的 VNode 进行对比，试图以最小的资源开销完成 DOM 的更新，这个过程就叫 patch
如果旧的 VNode 不存在，则直接将新的 VNode 挂载成全新的 DOM，这个过程叫做 mount

同样的，挂载过程也需要分类来进行处理，一一对应着我们 VNode 对象当中的五大类，在挂载完成以后，我们就需要考虑对其的更新操作，所以这时候就需要用上 patch 函数，同样对应着对象当中的五大类

// render.js
import { VNodeFlags, ChildrenFlags } from './flags'
import { createTextVNode } from './h'

export default function render(vnode, container) {
  const prevVNode = container.vnode
  if (prevVNode == null) {
    if (vnode) {
      // 没有旧的 VNode，使用 `mount` 函数挂载全新的 VNode
      mount(vnode, container)
      // 将新的 VNode 添加到 container.vnode 属性下，这样下一次渲染时旧的 VNode 就存在了
      container.vnode = vnode
    }
  } else {
    if (vnode) {
      // 有旧的 VNode，则调用 `patch` 函数打补丁
      patch(prevVNode, vnode, container)
      // 更新 container.vnode
      container.vnode = vnode
    } else {
      // 有旧的 VNode 但是没有新的 VNode，这说明应该移除 DOM，在浏览器中可以使用 removeChild 函数。
      container.removeChild(prevVNode.el)
      container.vnode = null
    }
  }
}

function mount(vnode, container, isSVG, refNode) {
  const { flags } = vnode
  if (flags & VNodeFlags.ELEMENT) {
    // 挂载普通标签
    mountElement(vnode, container, isSVG, refNode)
  } else if (flags & VNodeFlags.COMPONENT) {
    // 挂载组件
    mountComponent(vnode, container, isSVG)
  } else if (flags & VNodeFlags.TEXT) {
    // 挂载纯文本
    mountText(vnode, container)
  } else if (flags & VNodeFlags.FRAGMENT) {
    // 挂载 Fragment
    mountFragment(vnode, container, isSVG)
  } else if (flags & VNodeFlags.PORTAL) {
    // 挂载 Portal
    mountPortal(vnode, container, isSVG)
  }
}

function mountElement(vnode, container, isSVG, refNode) {
  isSVG = isSVG || vnode.flags & VNodeFlags.ELEMENT_SVG
  const el = isSVG
    ? document.createElementNS('http://www.w3.org/2000/svg', vnode.tag)
    : document.createElement(vnode.tag)
  vnode.el = el
  const data = vnode.data
  if (data) {
    for (let key in data) {
      patchData(el, key, null, data[key])
    }
  }

  const childFlags = vnode.childFlags
  const children = vnode.children
  if (childFlags !== ChildrenFlags.NO_CHILDREN) {
    if (childFlags & ChildrenFlags.SINGLE_VNODE) {
      mount(children, el, isSVG)
    } else if (childFlags & ChildrenFlags.MULTIPLE_VNODES) {
      for (let i = 0; i < children.length; i++) {
        mount(children[i], el, isSVG)
      }
    }
  }

  refNode ? container.insertBefore(el, refNode) : container.appendChild(el)
}

function mountText(vnode, container) {
  const el = document.createTextNode(vnode.children)
  vnode.el = el
  container.appendChild(el)
}

function mountFragment(vnode, container, isSVG) {
  // 拿到 children 和 childFlags
  const { children, childFlags } = vnode
  switch (childFlags) {
    case ChildrenFlags.SINGLE_VNODE:
      // 如果是单个子节点，则直接调用 mount
      mount(children, container, isSVG)
      break
    case ChildrenFlags.NO_CHILDREN:
      // 如果没有子节点，等价于挂载空片段，会创建一个空的文本节点占位
      const placeholder = createTextVNode('')
      mountText(placeholder, container)
      break
    default:
      // 多个子节点，遍历挂载之
      for (let i = 0; i < children.length; i++) {
        mount(children[i], container, isSVG)
      }
  }
}

function mountPortal(vnode, container) {
  const { tag, children, childFlags } = vnode

  // 获取挂载点
  const target = typeof tag === 'string' ? document.querySelector(tag) : tag

  if (childFlags & ChildrenFlags.SINGLE_VNODE) {
    // 将 children 挂在到 target 上，而非 container
    mount(children, target)
  } else if (childFlags & ChildrenFlags.MULTIPLE_VNODES) {
    for (let i = 0; i < children.length; i++) {
      // 将 children 挂在到 target 上，而非 container
      mount(children[i], target)
    }
  }

  // 占位的空文本节点
  const placeholder = createTextVNode('')
  // 将该节点挂载到 container 中
  mountText(placeholder, container, null)
  // el 属性引用该节点
  vnode.el = placeholder.el
}

function mountComponent(vnode, container, isSVG) {
  if (vnode.flags & VNodeFlags.COMPONENT_STATEFUL) {
    mountStatefulComponent(vnode, container, isSVG)
  } else {
    mountFunctionalComponent(vnode, container, isSVG)
  }
}

function mountStatefulComponent(vnode, container, isSVG) {
  // 创建组件实例
  const instance = (vnode.children = new vnode.tag())
  // 初始化 props
  instance.$props = vnode.data

  instance._update = function () {
    if (instance._mounted) {
      // 更新
      // 1、拿到旧的 VNode
      const prevVNode = instance.$vnode
      // 2、重渲染新的 VNode
      const nextVNode = (instance.$vnode = instance.render())
      // 3、patch 更新
      patch(prevVNode, nextVNode, prevVNode.el.parentNode)
      // 4、更新 vnode.el 和 $el
      instance.$el = vnode.el = instance.$vnode.el
    } else {
      // 1、渲染VNode
      instance.$vnode = instance.render()
      // 2、挂载
      mount(instance.$vnode, container, isSVG)
      // 3、组件已挂载的标识
      instance._mounted = true
      // 4、el 属性值 和 组件实例的 $el 属性都引用组件的根DOM元素
      instance.$el = vnode.el = instance.$vnode.el
      // 5、调用 mounted 钩子
      instance.mounted && instance.mounted()
    }
  }

  instance._update()
}

function mountFunctionalComponent(vnode, container, isSVG) {
  vnode.handle = {
    prev: null,
    next: vnode,
    container,
    update: () => {
      if (vnode.handle.prev) {
        // 更新
        // prevVNode 是旧的组件VNode，nextVNode 是新的组件VNode
        const prevVNode = vnode.handle.prev
        const nextVNode = vnode.handle.next
        // prevTree 是组件产出的旧的 VNode
        const prevTree = prevVNode.children
        // nextTree 是组件产出的新的 VNode
        const props = nextVNode.data
        const nextTree = (nextVNode.children = nextVNode.tag(props))
        // 调用 patch 函数更新
        patch(prevTree, nextTree, vnode.handle.container)
      } else {
        // 获取 props
        const props = vnode.data
        // 获取 VNode
        const $vnode = (vnode.children = vnode.tag(props))
        // 挂载
        mount($vnode, container, isSVG)
        // el 元素引用该组件的根元素
        vnode.el = $vnode.el
      }
    }
  }

  // 立即调用 vnode.handle.update 完成初次挂载
  vnode.handle.update()
}

function patch(prevVNode, nextVNode, container) {
  const nextFlags = nextVNode.flags
  const prevFlags = prevVNode.flags

  if (prevFlags !== nextFlags) {
    replaceVNode(prevVNode, nextVNode, container)
  } else if (nextFlags & VNodeFlags.ELEMENT) {
    patchElement(prevVNode, nextVNode, container)
  } else if (nextFlags & VNodeFlags.COMPONENT) {
    patchComponent(prevVNode, nextVNode, container)
  } else if (nextFlags & VNodeFlags.TEXT) {
    patchText(prevVNode, nextVNode)
  } else if (nextFlags & VNodeFlags.FRAGMENT) {
    patchFragment(prevVNode, nextVNode, container)
  } else if (nextFlags & VNodeFlags.PORTAL) {
    patchPortal(prevVNode, nextVNode)
  }
}

function replaceVNode(prevVNode, nextVNode, container) {
  container.removeChild(prevVNode.el)
  if (prevVNode.flags & VNodeFlags.COMPONENT_STATEFUL_NORMAL) {
    const instance = prevVNode.children
    instance.unmounted && instance.unmounted()
  }
  mount(nextVNode, container)
}

function patchElement(prevVNode, nextVNode, container) {
  // 如果新旧 VNode 描述的是不同的标签，则调用 replaceVNode 函数使用新的 VNode 替换旧的 VNode
  if (prevVNode.tag !== nextVNode.tag) {
    replaceVNode(prevVNode, nextVNode, container)
    return
  }

  // 拿到 el 元素，注意这时要让 nextVNode.el 也引用该元素
  const el = (nextVNode.el = prevVNode.el)
  const prevData = prevVNode.data
  const nextData = nextVNode.data

  if (nextData) {
    for (let key in nextData) {
      const prevValue = prevData[key]
      const nextValue = nextData[key]
      patchData(el, key, prevValue, nextValue)
    }
  }
  if (prevData) {
    for (let key in prevData) {
      const prevValue = prevData[key]
      if (prevValue && !nextData.hasOwnProperty(key)) {
        patchData(el, key, prevValue, null)
      }
    }
  }

  // 调用 patchChildren 函数递归的更新子节点
  patchChildren(
    prevVNode.childFlags, // 旧的 VNode 子节点的类型
    nextVNode.childFlags, // 新的 VNode 子节点的类型
    prevVNode.children, // 旧的 VNode 子节点
    nextVNode.children, // 新的 VNode 子节点
    el // 当前标签元素，即这些子节点的父节点
  )
}

function patchChildren(
  prevChildFlags,
  nextChildFlags,
  prevChildren,
  nextChildren,
  container
) {
  switch (prevChildFlags) {
    // 旧的 children 是单个子节点，会执行该 case 语句块
    case ChildrenFlags.SINGLE_VNODE:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          // 新的 children 也是单个子节点时，会执行该 case 语句块
          patch(prevChildren, nextChildren, container)
          break
        case ChildrenFlags.NO_CHILDREN:
          // 新的 children 中没有子节点时，会执行该 case 语句块
          container.removeChild(prevChildren.el)
          break
        default:
          // 但新的 children 中有多个子节点时，会执行该 case 语句块
          container.removeChild(prevChildren.el)
          for (let i = 0; i < nextChildren.length; i++) {
            mount(nextChildren[i], container)
          }
          break
      }
      break
    // 旧的 children 中没有子节点时，会执行该 case 语句块
    case ChildrenFlags.NO_CHILDREN:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          // 新的 children 是单个子节点时，会执行该 case 语句块
          mount(nextChildren, container)
          break
        case ChildrenFlags.NO_CHILDREN:
          // 新的 children 中没有子节点时，会执行该 case 语句块
          break
        default:
          // 但新的 children 中有多个子节点时，会执行该 case 语句块
          for (let i = 0; i < nextChildren.length; i++) {
            mount(nextChildren[i], container)
          }
          break
      }
      break
    // 旧的 children 中有多个子节点时，会执行该 case 语句块
    default:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          for (let i = 0; i < prevChildren.length; i++) {
            container.removeChild(prevChildren[i].el)
          }
          mount(nextChildren, container)
          break
        case ChildrenFlags.NO_CHILDREN:
          for (let i = 0; i < prevChildren.length; i++) {
            container.removeChild(prevChildren[i].el)
          }
          break
        default:
          // 但新的 children 中有多个子节点时，会执行该 case 语句块
          let lastIndex = 0
          for (let i = 0; i < nextChildren.length; i++) {
            const nextVNode = nextChildren[i]
            let j = 0,
              find = false
            for (j; j < prevChildren.length; j++) {
              const prevVNode = prevChildren[j]
              if (nextVNode.key === prevVNode.key) {
                find = true
                patch(prevVNode, nextVNode, container)
                if (j < lastIndex) {
                  // 需要移动
                  const refNode = nextChildren[i - 1].el.nextSibling
                  container.insertBefore(prevVNode.el, refNode)
                  break
                } else {
                  // 更新 lastIndex
                  lastIndex = j
                }
              }
            }
            if (!find) {
              // 挂载新节点
              const refNode =
                i - 1 < 0
                  ? prevChildren[0].el
                  : nextChildren[i - 1].el.nextSibling
              mount(nextVNode, container, false, refNode)
            }
          }
          // 移除已经不存在的节点
          for (let i = 0; i < prevChildren.length; i++) {
            const prevVNode = prevChildren[i]
            const has = nextChildren.find(
              nextVNode => nextVNode.key === prevVNode.key
            )
            if (!has) {
              // 移除
              container.removeChild(prevVNode.el)
            }
          }
          break
      }
      break
  }
}

function patchText(prevVNode, nextVNode) {
  // 拿到文本节点 el，同时让 nextVNode.el 指向该文本节点
  const el = (nextVNode.el = prevVNode.el)
  // 只有当新旧文本内容不一致时才有必要更新
  if (nextVNode.children !== prevVNode.children) {
    el.nodeValue = nextVNode.children
  }
}

function patchFragment(prevVNode, nextVNode, container) {
  // 直接调用 patchChildren 函数更新 新旧片段的子节点即可
  patchChildren(
    prevVNode.childFlags, // 旧片段的子节点类型
    nextVNode.childFlags, // 新片段的子节点类型
    prevVNode.children, // 旧片段的子节点
    nextVNode.children, // 新片段的子节点
    container
  )

  switch (nextVNode.childFlags) {
    case ChildrenFlags.SINGLE_VNODE:
      nextVNode.el = nextVNode.children.el
      break
    case ChildrenFlags.NO_CHILDREN:
      nextVNode.el = prevVNode.el
      break
    default:
      nextVNode.el = nextVNode.children[0].el
  }
}

function patchPortal(prevVNode, nextVNode) {
  patchChildren(
    prevVNode.childFlags,
    nextVNode.childFlags,
    prevVNode.children,
    nextVNode.children,
    prevVNode.tag // 注意 container 是旧的 container
  )
  // 让 nextVNode.el 指向 prevVNode.el
  nextVNode.el = prevVNode.el

  // 如果新旧容器不同，才需要搬运
  if (nextVNode.tag !== prevVNode.tag) {
    // 获取新的容器元素，即挂载目标
    const container =
      typeof nextVNode.tag === 'string'
        ? document.querySelector(nextVNode.tag)
        : nextVNode.tag

    switch (nextVNode.childFlags) {
      case ChildrenFlags.SINGLE_VNODE:
        // 如果新的 Portal 是单个子节点，就把该节点搬运到新容器中
        container.appendChild(nextVNode.children.el)
        break
      case ChildrenFlags.NO_CHILDREN:
        // 新的 Portal 没有子节点，不需要搬运
        break
      default:
        // 如果新的 Portal 是多个子节点，遍历逐个将它们搬运到新容器中
        for (let i = 0; i < nextVNode.children.length; i++) {
          container.appendChild(nextVNode.children[i].el)
        }
        break
    }
  }
}

function patchComponent(prevVNode, nextVNode, container) {
  if (nextVNode.tag !== prevVNode.tag) {
    replaceVNode(prevVNode, nextVNode, container)
  } else if (nextVNode.flags & VNodeFlags.COMPONENT_STATEFUL_NORMAL) {
    // 获取组件实例
    const instance = (nextVNode.children = prevVNode.children)
    // 更新 props
    instance.$props = nextVNode.data
    // 更新组件
    instance._update()
  } else {
    // 更新函数式组件
    const handle = (nextVNode.handle = prevVNode.handle)
    handle.prev = prevVNode
    handle.next = nextVNode
    handle.container = container

    handle.update()
  }
}

function patchData(el, key, prevValue, nextValue) {
  const domPropsRE = /\W|^(?:value|checked|selected|muted)$/
  switch (key) {
    case 'style':
      for (let k in nextValue) {
        el.style[k] = nextValue[k]
      }
      for (let k in prevValue) {
        if (!nextValue.hasOwnProperty(k)) {
          el.style[k] = ''
        }
      }
      break
    case 'class':
      el.className = nextValue
      break
    default:
      if (key[0] === 'o' && key[1] === 'n') {
        // 事件
        // 移除旧事件
        if (prevValue) {
          el.removeEventListener(key.slice(2), prevValue)
        }
        // 添加新事件
        if (nextValue) {
          el.addEventListener(key.slice(2), nextValue)
        }
      } else if (domPropsRE.test(key)) {
        // 当做 DOM Prop 处理
        el[key] = nextValue
      } else {
        // 当做 Attr 处理
        el.setAttribute(key, nextValue)
      }
      break
  }
}

核心 Diff 算法

只有当新旧子节点的类型都是多个子节点时，核心 diff 算法才派得上用场，如下图所示

在 diff 算法一章，我们主要介绍了三种不同的算法，下面我们一个一个来进行回顾

这里需要注意，采用不同的算法只需要替换 patchChildren 函数当中的新旧 children 中都有多个子节点的情况下的分支判断即可

React 所采用 Diff 算法

React 当中所采用的方式是利用 key 来尽可能的复用 DOM 元素，然后在遍历当中使用『最大索引值』的概念来确定需要移动的元素，接着在内层循环当中采用标记变量的方式来确定是否需要挂载新的元素，最后在外层循环结束之后，再遍历一次旧的节点，如果在新节点当中找不到相对应的，则删除掉对应节点

function patchChildren(prevChildFlags, nextChildFlags, prevChildren, nextChildren, container) {
  switch (prevChildFlags) {

    // ... 省略（见上方）

    // 只有当新旧子节点的类型都是多个子节点时，核心 Diff 算法才派得上用场
    default:
      switch (nextChildFlags) {

        // ... 省略（见上方）

        /**
         *  react 所采用 diff 算法
         */
        default:
          let lastIndex = 0
          for (let i = 0; i < nextChildren.length; i++) {
            const nextVNode = nextChildren[i]
            let j = 0,
              find = false
            for (j; j < prevChildren.length; j++) {
              const prevVNode = prevChildren[j]
              if (nextVNode.key === prevVNode.key) {
                find = true
                patch(prevVNode, nextVNode, container)
                if (j < lastIndex) {
                  // 需要移动
                  const refNode = nextChildren[i - 1].el.nextSibling
                  container.insertBefore(prevVNode.el, refNode)
                  break
                } else {
                  // 更新 lastIndex
                  lastIndex = j
                }
              }
            }
            if (!find) {
              // 挂载新节点
              const refNode =
                i - 1 < 0
                  ? prevChildren[0].el
                  : nextChildren[i - 1].el.nextSibling
              mount(nextVNode, container, false, refNode)
            }
          }
          // 移除已经不存在的节点
          for (let i = 0; i < prevChildren.length; i++) {
            const prevVNode = prevChildren[i]
            const has = nextChildren.find(
              nextVNode => nextVNode.key === prevVNode.key
            )
            if (!has) {
              // 移除
              container.removeChild(prevVNode.el)
            }
          }
          break
      }
      break
  }
}

Vue2 所采用 Diff 算法

Vue2 所采用的是『双端比较』的算法，借鉴于开源项目 snabbdom，原理是使用四个变量分别存储新旧两个端点的位置索引，在结合四个位置索引所指向的 VNode，依次从两端开始进行比较，根据四次比较当中的各种情况进行不同的处理方式，对于经过四次比较依然没有找到可复用的节点的非理想情况，则采用再次遍历旧的节点的方式分情况进行处理

如果寻找到与第一个新节点当中拥有相同 key 值的元素，就会将其更新，并且将该节点置为 undefined，后续过程则会跳过这个状态
如果没有寻找到，这说明是一个全新的节点，挂载即可，为了避免遗漏，会在循环完毕之后再次进行判断，如果还存在没有被处理的全新节点，则一样会被挂载
同样的，在循环完毕后会进行判断有没有多余的元素，如果存在则说明有元素需要被移除

function patchChildren(prevChildFlags, nextChildFlags, prevChildren, nextChildren, container) {
  switch (prevChildFlags) {

    // ... 省略（见上方）

    // 只有当新旧子节点的类型都是多个子节点时，核心 Diff 算法才派得上用场
    default:
      switch (nextChildFlags) {

        // ... 省略（见上方）

        /**
         *  vue2 所采用 diff 算法
         */
        default:
          // 当新的 children 中有多个子节点时，会执行该 case 语句块
          let oldStartIdx = 0
          let oldEndIdx = prevChildren.length - 1
          let newStartIdx = 0
          let newEndIdx = nextChildren.length - 1
          let oldStartVNode = prevChildren[oldStartIdx]
          let oldEndVNode = prevChildren[oldEndIdx]
          let newStartVNode = nextChildren[newStartIdx]
          let newEndVNode = nextChildren[newEndIdx]
          while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if (!oldStartVNode) {
              oldStartVNode = prevChildren[++oldStartIdx]
            } else if (!oldEndVNode) {
              oldEndVNode = prevChildren[--oldEndIdx]
            } else if (oldStartVNode.key === newStartVNode.key) {
              patch(oldStartVNode, newStartVNode, container)
              oldStartVNode = prevChildren[++oldStartIdx]
              newStartVNode = nextChildren[++newStartIdx]
            } else if (oldEndVNode.key === newEndVNode.key) {
              patch(oldEndVNode, newEndVNode, container)
              oldEndVNode = prevChildren[--oldEndIdx]
              newEndVNode = nextChildren[--newEndIdx]
            } else if (oldStartVNode.key === newEndVNode.key) {
              patch(oldStartVNode, newEndVNode, container)
              container.insertBefore(
                oldStartVNode.el,
                oldEndVNode.el.nextSibling
              )
              oldStartVNode = prevChildren[++oldStartIdx]
              newEndVNode = nextChildren[--newEndIdx]
            } else if (oldEndVNode.key === newStartVNode.key) {
              patch(oldEndVNode, newStartVNode, container)
              container.insertBefore(oldEndVNode.el, oldStartVNode.el)
              oldEndVNode = prevChildren[--oldEndIdx]
              newStartVNode = nextChildren[++newStartIdx]
            } else {
              const idxInOld = prevChildren.findIndex(
                node => node.key === newStartVNode.key
              )
              if (idxInOld >= 0) {
                const vnodeToMove = prevChildren[idxInOld]
                patch(vnodeToMove, newStartVNode, container)
                prevChildren[idxInOld] = undefined
                container.insertBefore(vnodeToMove.el, oldStartVNode.el)
              } else {
                // 新节点
                mount(newStartVNode, container, false, oldStartVNode.el)
              }
              newStartVNode = nextChildren[++newStartIdx]
            }
          }
          if (oldEndIdx < oldStartIdx) {
            // 添加新节点
            for (let i = newStartIdx; i <= newEndIdx; i++) {
              mount(nextChildren[i], container, false, oldStartVNode.el)
            }
          } else if (newEndIdx < newStartIdx) {
            // 移除操作
            for (let i = oldStartIdx; i <= oldEndIdx; i++) {
              container.removeChild(prevChildren[i].el)
            }
          }
          break
      }
      break
  }
}

inferno 所采用 Diff 算法

也是在 Vue3 中将采用的一种算法，原理是在进行 diff 算法之前，先进行一次预处理，剔除掉相同的前置和后置元素，原理是建立一个索引，指向新旧子节点中的第一个节点，并逐步向后遍历，直到遇到两个拥有不同 key 值的节点为止，然后根据索引之间的关系来进行对应的单独处理

对于判断是否需要进行 DOM 移动，采用了构造一个数组来记录新子节点在经过预处理之后剩余未处理节点的数量
采用构建索引表（为了将时间复杂度由 O(n^2) 降为 O(n)）的方式对新旧子节点中具有相同 key 值的节点进行更新，来确定是否需要移动操作
最后利用最长递增子序列的方式来进行 DOM 的移动操作

function patchChildren(prevChildFlags, nextChildFlags, prevChildren, nextChildren, container) {
  switch (prevChildFlags) {

    // ... 省略（见上方）

    // 只有当新旧子节点的类型都是多个子节点时，核心 Diff 算法才派得上用场
    default:
      switch (nextChildFlags) {

        // ... 省略（见上方）

        /**
         *  inferno 所采用 diff 算法
         */
        default:
          // 更新相同的前缀节点
          let j = 0
          let prevVNode = prevChildren[j]
          let nextVNode = nextChildren[j]
          let prevEnd = prevChildren.length - 1
          let nextEnd = nextChildren.length - 1

          outer: {
            while (prevVNode.key === nextVNode.key) {
              patch(prevVNode, nextVNode, container)
              j++
              if (j > prevEnd || j > nextEnd) {
                break outer
              }
              prevVNode = prevChildren[j]
              nextVNode = nextChildren[j]
            }
            // 更新相同的后缀节点
            prevVNode = prevChildren[prevEnd]
            nextVNode = nextChildren[nextEnd]
            while (prevVNode.key === nextVNode.key) {
              patch(prevVNode, nextVNode, container)
              prevEnd--
              nextEnd--
              if (j > prevEnd || j > nextEnd) {
                break outer
              }
              prevVNode = prevChildren[prevEnd]
              nextVNode = nextChildren[nextEnd]
            }
          }

          if (j > prevEnd && j <= nextEnd) {
            // j -> nextEnd 之间的节点应该被添加
            const nextPos = nextEnd + 1
            const refNode =
              nextPos < nextChildren.length ? nextChildren[nextPos].el : null
            while (j <= nextEnd) {
              mount(nextChildren[j++], container, false, refNode)
            }
          } else if (j > nextEnd) {
            while (j <= prevEnd) {
              container.removeChild(prevChildren[j++].el)
            }
          } else {
            // 构造 source 数组
            const nextLeft = nextEnd - j + 1 // 新 children 中剩余未处理节点的数量
            const source = []
            for (let i = 0; i < nextLeft; i++) {
              source.push(-1)
            }

            const prevStart = j
            const nextStart = j
            let moved = false
            let pos = 0

            // 构建索引表
            const keyIndex = {}
            for (let i = nextStart; i <= nextEnd; i++) {
              keyIndex[nextChildren[i].key] = i
            }
            let patched = 0
            // 遍历旧 children 的剩余未处理节点
            for (let i = prevStart; i <= prevEnd; i++) {
              prevVNode = prevChildren[i]

              if (patched < nextLeft) {
                // 通过索引表快速找到新 children 中具有相同 key 的节点的位置
                const k = keyIndex[prevVNode.key]
                if (typeof k !== 'undefined') {
                  nextVNode = nextChildren[k]
                  // patch 更新
                  patch(prevVNode, nextVNode, container)
                  patched++
                  // 更新 source 数组
                  source[k - nextStart] = i
                  // 判断是否需要移动
                  if (k < pos) {
                    moved = true
                  } else {
                    pos = k
                  }
                } else {
                  // 没找到，说明旧节点在新 children 中已经不存在了，应该移除
                  container.removeChild(prevVNode.el)
                }
              } else {
                // 多余的节点，应该移除
                container.removeChild(prevVNode.el)
              }
            }

            if (moved) {
              const seq = lis(source)
              // j 指向最长递增子序列的最后一个值
              let j = seq.length - 1
              // 从后向前遍历新 children 中的剩余未处理节点
              for (let i = nextLeft - 1; i >= 0; i--) {
                if (source[i] === -1) {
                  // 作为全新的节点挂载

                  // 该节点在新 children 中的真实位置索引
                  const pos = i + nextStart
                  const nextVNode = nextChildren[pos]
                  // 该节点下一个节点的位置索引
                  const nextPos = pos + 1
                  // 挂载
                  mount(
                    nextVNode,
                    container,
                    false,
                    nextPos < nextChildren.length
                      ? nextChildren[nextPos].el
                      : null
                  )
                } else if (i !== seq[j]) {
                  // 说明该节点需要移动

                  // 该节点在新 children 中的真实位置索引
                  const pos = i + nextStart
                  const nextVNode = nextChildren[pos]
                  // 该节点下一个节点的位置索引
                  const nextPos = pos + 1
                  // 移动
                  container.insertBefore(
                    nextVNode.el,
                    nextPos < nextChildren.length
                      ? nextChildren[nextPos].el
                      : null
                  )
                } else {
                  // 当 i === seq[j] 时，说明该位置的节点不需要移动
                  // 并让 j 指向下一个位置
                  j--
                }
              }
            }

          }
          break
      }
      break
  }
}

# React