How to use the Diff algorithm in Vue 2.5

This article will analyze the Virtual Dom used in Vue 2.5.3 version. updataChildren is the core of the Diff algorithm, so this article conducts a graphic analysis of updataChildren. Let me share with you the Diff algorithm of Vue 2.5 through this article. Friends who need it can refer to it

DOM is "inherently slow", so all major front-end frameworks provide ways to optimize DOM operations. In Angular It is dirty value checking. React first proposed Virtual Dom, and Vue2.0 also added Virtual Dom, which is similar to React.

This article will analyze the Virtual Dom used in Vue 2.5.3 version.

updataChildren is the core of the Diff algorithm, so this article conducts a graphic analysis of updataChildren.

1.VNode object

A VNode instance contains the following attributes. This part of the code is in src/core/vdom/vnode.js Inside

export default class VNode {
 tag: string | void;
 data: VNodeData | void;
 children: ?Array<VNode>;
 text: string | void;
 elm: Node | void;
 ns: string | void;
 context: Component | void; // rendered in this component&#39;s scope
 key: string | number | void;
 componentOptions: VNodeComponentOptions | void;
 componentInstance: Component | void; // component instance
 parent: VNode | void; // component placeholder node

 // strictly internal
 raw: boolean; // contains raw HTML? (server only)
 isStatic: boolean; // hoisted static node
 isRootInsert: boolean; // necessary for enter transition check
 isComment: boolean; // empty comment placeholder?
 isCloned: boolean; // is a cloned node?
 isOnce: boolean; // is a v-once node?
 asyncFactory: Function | void; // async component factory function
 asyncMeta: Object | void;
 isAsyncPlaceholder: boolean;
 ssrContext: Object | void;
 functionalContext: Component | void; // real context vm for functional nodes
 functionalOptions: ?ComponentOptions; // for SSR caching
 functionalScopeId: ?string; // functioanl scope id support

• tag: The tag name of the current node

• data: The data object of the current node. For specific fields, please refer to vue source code types The definition of VNodeData in /vnode.d.ts

• children: array type, containing the child nodes of the current node

• text: current The text of the node. Generally, text nodes or comment nodes will have this attribute

• elm: the real dom node corresponding to the current virtual node

• ns : Node namespace

• context: Compilation scope

• functionalContext: Functional component scope

• key: The key attribute of the node is used as the identifier of the node, which is beneficial to the optimization of the patch.

• componentOptions: The option information used when creating a component instance

• child: the component instance corresponding to the current node

• parent: the placeholder node of the component

• raw: raw html

• isStatic: The identifier of the static node

• isRootInsert: Whether to insert as the root node, is

• isComment: Whether the current node is a comment node

• isCloned: Whether the current node is a clone node

• isOnce: Whether the current node has v- once directive

2. Classification of VNode

VNode can be understood as a base class of VueVirtual Dom, through VNode The VNnode instances generated by the constructor can be of the following categories:

• EmptyVNode: Annotation node without content

• TextVNode: Text node

• ElementVNode: Ordinary element node

• ComponentVNode: Component node

• CloneVNode: Clone node, which can be the above Any type of node, the only difference is that the isCloned attribute is true

3.Create-Element source code analysis

This part of the code is in src/core/vdom/create-element.js. I just paste the code and add my comments

export function createElement (
 context: Component,
 tag: any,
 data: any,
 children: any,
 normalizationType: any,
 alwaysNormalize: boolean
): VNode {
 // 兼容不传data的情况
 if (Array.isArray(data) || isPrimitive(data)) {
 normalizationType = children
 children = data
 data = undefined
 }
 // 如果alwaysNormalize是true
 // 那么normalizationType应该设置为常量ALWAYS_NORMALIZE的值
 if (isTrue(alwaysNormalize)) {
 normalizationType = ALWAYS_NORMALIZE
 }
 // 调用_createElement创建虚拟节点
 return _createElement(context, tag, data, children, normalizationType)
}

export function _createElement (
 context: Component,
 tag?: string | Class<Component> | Function | Object,
 data?: VNodeData,
 children?: any,
 normalizationType?: number
): VNode {

 /**
 * 如果存在data.__ob__，说明data是被Observer观察的数据
 * 不能用作虚拟节点的data
 * 需要抛出警告，并返回一个空节点
 *
 * 被监控的data不能被用作vnode渲染的数据的原因是：
 * data在vnode渲染过程中可能会被改变，这样会触发监控，导致不符合预期的操作
 */
 if (isDef(data) && isDef((data: any).__ob__)) {
 process.env.NODE_ENV !== &#39;production&#39; && warn(
  `Avoid using observed data object as vnode data: ${JSON.stringify(data)}\n` +
  &#39;Always create fresh vnode data objects in each render!&#39;,
  context
 )
 return createEmptyVNode()
 }
 // object syntax in v-bind
 if (isDef(data) && isDef(data.is)) {
 tag = data.is
 }
 if (!tag) {
 // 当组件的is属性被设置为一个falsy的值
 // Vue将不会知道要把这个组件渲染成什么
 // 所以渲染一个空节点
 // in case of component :is set to falsy value
 return createEmptyVNode()
 }
 // key为非原始值警告
 // warn against non-primitive key
 if (process.env.NODE_ENV !== &#39;production&#39; &&
 isDef(data) && isDef(data.key) && !isPrimitive(data.key)
 ) {
 warn(
  &#39;Avoid using non-primitive value as key, &#39; +
  &#39;use string/number value instead.&#39;,
  context
 )
 }
 // 作用域插槽
 // support single function children as default scoped slot
 if (Array.isArray(children) &&
 typeof children[0] === &#39;function&#39;
 ) {
 data = data || {}
 data.scopedSlots = { default: children[0] }
 children.length = 0
 }
 // 根据normalizationType的值，选择不同的处理方法
 if (normalizationType === ALWAYS_NORMALIZE) {
 children = normalizeChildren(children)
 } else if (normalizationType === SIMPLE_NORMALIZE) {
 children = simpleNormalizeChildren(children)
 }
 let vnode, ns
 // 如果标签名是字符串类型
 if (typeof tag === &#39;string&#39;) {
 let Ctor
 // 获取标签的命名空间
 ns = (context.$vnode && context.$vnode.ns) || config.getTagNamespace(tag)
 // 如果是保留标签
 if (config.isReservedTag(tag)) {
  // platform built-in elements
  // 就创建这样一个vnode
  vnode = new VNode(
  config.parsePlatformTagName(tag), data, children,
  undefined, undefined, context
  )
  // 如果不是保留字标签，尝试从vm的components上查找是否有这个标签的定义
 } else if (isDef(Ctor = resolveAsset(context.$options, &#39;components&#39;, tag))) {
  // component
  // 如果找到，就创建虚拟组件节点
  vnode = createComponent(Ctor, data, context, children, tag)
 } else {
  // unknown or unlisted namespaced elements
  // check at runtime because it may get assigned a namespace when its
  // parent normalizes children
  // 兜底方案，创建一个正常的vnode
  vnode = new VNode(
  tag, data, children,
  undefined, undefined, context
  )
 }
 } else {
 // 当tag不是字符串的时候，我们认为tag是组件的构造类
 // 所以直接创建
 // direct component options / constructor
 vnode = createComponent(tag, data, context, children)
 }
 if (isDef(vnode)) {
 // 应用命名空间
 if (ns) applyNS(vnode, ns)
 return vnode
 } else {
 // 返回一个空节点
 return createEmptyVNode()
 }
}
function applyNS (vnode, ns, force) {
 vnode.ns = ns
 if (vnode.tag === &#39;foreignObject&#39;) {
 // use default namespace inside foreignObject
 ns = undefined
 force = true
 }
 if (isDef(vnode.children)) {
 for (let i = 0, l = vnode.children.length; i < l; i++) {
  const child = vnode.children[i]
  if (isDef(child.tag) && (isUndef(child.ns) || isTrue(force))) {
  applyNS(child, ns, force)
  }
 }
 }
}

4. Patch principle

The patch function is defined in src/core/vdom/patch.js. The patch logic is relatively simple, so no code is required.

The patch function receives 6 parameters:

• oldVnode: old virtual node or old real dom node

• vnode: new virtual node

• hydrating: Whether to mix it with real dom

• removeOnly: special flag, used for

• parentElm: parent node

• refElm: The new node will be inserted before refElm

The logic of patch is:

if vnode does not exist but oldVnode exists, indicating that the intention is to destroy the old node, then call invokeDestroyHook(oldVnode) to destroy it

If oldVnode does not exist but vnode exists, indicating that the intention is to create a new node, then call createElm to create a new node

else When vnode and oldVnode both exist

If oldVnode and vnode are the same node, call patchVnode to patch

When vnode and oldVnode When they are not the same node, if oldVnode is a real dom node or hydrating is set to true, you need to use the hydrate function to map the virtual dom and the real dom, then set oldVnode to the corresponding virtual dom, find the parent node of oldVnode.elm, according to vnode creates a real dom node and inserts it into the parent node at the position of oldVnode.elm

The logic of patchVnode is:

1. If oldVnode is completely consistent with vnode, Then you don’t need to do anything

2. If oldVnode and vnode are both static nodes and have the same key, and when vnode is a clone node or a node controlled by the v-once command, you only need to change oldVnode. Both elm and oldVnode.child are copied to vnode, and no other operations are required

3. Otherwise, if vnode is not a text node or comment node

• If oldVnode and vnode has child nodes, and the child nodes of the two parties are not completely consistent, execute updateChildren

• If only oldVnode has child nodes, then delete these nodes

• If only vnode has child nodes, then create these child nodes

• If neither oldVnode nor vnode has child nodes, but oldVnode is a text node or comment node, Just set the text of vnode.elm to the empty string

4.如果vnode是文本节点或注释节点，但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以

代码如下：

 function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
 // 如果新旧节点一致，什么都不做
 if (oldVnode === vnode) {
  return
 }
 // 让vnode.el引用到现在的真实dom，当el修改时，vnode.el会同步变化
 const elm = vnode.elm = oldVnode.elm
 // 异步占位符
 if (isTrue(oldVnode.isAsyncPlaceholder)) {
  if (isDef(vnode.asyncFactory.resolved)) {
  hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
  } else {
  vnode.isAsyncPlaceholder = true
  }
  return
 }
 // reuse element for static trees.
 // note we only do this if the vnode is cloned -
 // if the new node is not cloned it means the render functions have been
 // reset by the hot-reload-api and we need to do a proper re-render.
 // 如果新旧都是静态节点，并且具有相同的key
 // 当vnode是克隆节点或是v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上
 // 也不用再有其他操作
 if (isTrue(vnode.isStatic) &&
  isTrue(oldVnode.isStatic) &&
  vnode.key === oldVnode.key &&
  (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
 ) {
  vnode.componentInstance = oldVnode.componentInstance
  return
 }
 let i
 const data = vnode.data
 if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
  i(oldVnode, vnode)
 }
 const oldCh = oldVnode.children
 const ch = vnode.children
 if (isDef(data) && isPatchable(vnode)) {
  for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
  if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
 }
 // 如果vnode不是文本节点或者注释节点
 if (isUndef(vnode.text)) {
  // 并且都有子节点
  if (isDef(oldCh) && isDef(ch)) {
  // 并且子节点不完全一致，则调用updateChildren
  if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  // 如果只有新的vnode有子节点
  } else if (isDef(ch)) {
  if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
  // elm已经引用了老的dom节点，在老的dom节点上添加子节点
  addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  // 如果新vnode没有子节点，而vnode有子节点，直接删除老的oldCh
  } else if (isDef(oldCh)) {
  removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  // 如果老节点是文本节点
  } else if (isDef(oldVnode.text)) {
  nodeOps.setTextContent(elm, &#39;&#39;)
  }
  // 如果新vnode和老vnode是文本节点或注释节点
  // 但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以
 } else if (oldVnode.text !== vnode.text) {
  nodeOps.setTextContent(elm, vnode.text)
 }
 if (isDef(data)) {
  if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
 }
 }

5.updataChildren原理

updateChildren的逻辑是：

分别获取oldVnode和vnode的firstChild、lastChild，赋值给oldStartVnode、oldEndVnode、newStartVnode、newEndVnode

如果oldStartVnode和newStartVnode是同一节点，调用patchVnode进行patch，然后将oldStartVnode和newStartVnode都设置为下一个子节点，

如果oldEndVnode和newEndVnode是同一节点，调用patchVnode进行patch，然后将oldEndVnode和newEndVnode都设置为上一个子节点，重复上述流程

如果oldStartVnode和newEndVnode是同一节点，调用patchVnode进行patch，如果removeOnly是false，那么可以把oldStartVnode.elm移动到oldEndVnode.elm之后，然后把oldStartVnode设置为下一个节点，newEndVnode设置为上一个节点，重复上述流程

如果newStartVnode和oldEndVnode是同一节点，调用patchVnode进行patch，如果removeOnly是false，那么可以把oldEndVnode.elm移动到oldStartVnode.elm之前，然后把newStartVnode设置为下一个节点，oldEndVnode设置为上一个节点，重复上述流程

如果以上都不匹配，就尝试在oldChildren中寻找跟newStartVnode具有相同key的节点，如果找不到相同key的节点，说明newStartVnode是一个新节点，就创建一个，然后把newStartVnode设置为下一个节点

如果上一步找到了跟newStartVnode相同key的节点，那么通过其他属性的比较来判断这2个节点是否是同一个节点，如果是，就调用patchVnode进行patch，如果removeOnly是false，就把newStartVnode.elm插入到oldStartVnode.elm之前，把newStartVnode设置为下一个节点，重复上述流程

如果在oldChildren中没有寻找到newStartVnode的同一节点，那就创建一个新节点，把newStartVnode设置为下一个节点，重复上述流程

如果oldStartVnode跟oldEndVnode重合了，并且newStartVnode跟newEndVnode也重合了，这个循环就结束了

具体代码如下：

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
 let oldStartIdx = 0 // 旧头索引
 let newStartIdx = 0 // 新头索引
 let oldEndIdx = oldCh.length - 1 // 旧尾索引
 let newEndIdx = newCh.length - 1 // 新尾索引
 let oldStartVnode = oldCh[0] // oldVnode的第一个child
 let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一个child
 let newStartVnode = newCh[0] // newVnode的第一个child
 let newEndVnode = newCh[newEndIdx] // newVnode的最后一个child
 let oldKeyToIdx, idxInOld, vnodeToMove, refElm
 // removeOnly is a special flag used only by <transition-group>
 // to ensure removed elements stay in correct relative positions
 // during leaving transitions
 const canMove = !removeOnly
 // 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，证明diff完了，循环结束
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 如果oldVnode的第一个child不存在
  if (isUndef(oldStartVnode)) {
  // oldStart索引右移
  oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  // 如果oldVnode的最后一个child不存在
  } else if (isUndef(oldEndVnode)) {
  // oldEnd索引左移
  oldEndVnode = oldCh[--oldEndIdx]
  // oldStartVnode和newStartVnode是同一个节点
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  // patch oldStartVnode和newStartVnode， 索引左移，继续循环
  patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
  // oldEndVnode和newEndVnode是同一个节点
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  // patch oldEndVnode和newEndVnode，索引右移，继续循环
  patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
  // oldStartVnode和newEndVnode是同一个节点
  } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
  // patch oldStartVnode和newEndVnode
  patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
  // 如果removeOnly是false，则将oldStartVnode.eml移动到oldEndVnode.elm之后
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  // oldStart索引右移，newEnd索引左移
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
  // 如果oldEndVnode和newStartVnode是同一个节点
  } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
  // patch oldEndVnode和newStartVnode
  patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
  // 如果removeOnly是false，则将oldEndVnode.elm移动到oldStartVnode.elm之前
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  // oldEnd索引左移，newStart索引右移
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
  // 如果都不匹配
  } else {
  if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  // 尝试在oldChildren中寻找和newStartVnode的具有相同的key的Vnode
  idxInOld = isDef(newStartVnode.key)
   ? oldKeyToIdx[newStartVnode.key]
   : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
  // 如果未找到，说明newStartVnode是一个新的节点
  if (isUndef(idxInOld)) { // New element
   // 创建一个新Vnode
   createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
  // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
  } else {
   vnodeToMove = oldCh[idxInOld]
   /* istanbul ignore if */
   if (process.env.NODE_ENV !== &#39;production&#39; && !vnodeToMove) {
   warn(
    &#39;It seems there are duplicate keys that is causing an update error. &#39; +
    &#39;Make sure each v-for item has a unique key.&#39;
   )
   }
   // 比较两个具有相同的key的新节点是否是同一个节点
   //不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。
   if (sameVnode(vnodeToMove, newStartVnode)) {
   // patch vnodeToMove和newStartVnode
   patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
   // 清除
   oldCh[idxInOld] = undefined
   // 如果removeOnly是false，则将找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm
   // 移动到oldStartVnode.elm之前
   canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
   // 如果key相同，但是节点不相同，则创建一个新的节点
   } else {
   // same key but different element. treat as new element
   createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
   }
  }
  // 右移
  newStartVnode = newCh[++newStartIdx]
  }
 }

6.具体的Diff分析

不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。

diff的遍历过程中，只要是对dom进行的操作都调用api.insertBefore，api.insertBefore只是原生insertBefore的简单封装。

比较分为两种，一种是有vnode.key的，一种是没有的。但这两种比较对真实dom的操作是一致的。

对于与sameVnode(oldStartVnode, newStartVnode)和sameVnode(oldEndVnode,newEndVnode)为true的情况，不需要对dom进行移动。

总结遍历过程，有3种dom操作：上述图中都有

1.当oldStartVnode，newEndVnode值得比较，说明oldStartVnode.el跑到oldEndVnode.el的后边了。

2.当oldEndVnode，newStartVnode值得比较，oldEndVnode.el跑到了oldStartVnode.el的前边，准确的说应该是oldEndVnode.el需要移动到oldStartVnode.el的前边”。

3.newCh中的节点oldCh里没有， 将新节点插入到oldStartVnode.el的前边

在结束时，分为两种情况：

1.oldStartIdx > oldEndIdx，可以认为oldCh先遍历完。当然也有可能newCh此时也正好完成了遍历，统一都归为此类。此时newStartIdx和newEndIdx之间的vnode是新增的，调用addVnodes，把他们全部插进before的后边，before很多时候是为null的。addVnodes调用的是insertBefore操作dom节点，我们看看insertBefore的文档：parentElement.insertBefore(newElement, referenceElement)

如果referenceElement为null则newElement将被插入到子节点的末尾。如果newElement已经在DOM树中，newElement首先会从DOM树中移除。所以before为null，newElement将被插入到子节点的末尾。

2.newStartIdx > newEndIdx, it can be considered that newCh is traversed first. At this time, the vnode between oldStartIdx and oldEndIdx no longer exists in the new child node. Call removeVnodes to delete them from the dom.

The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.

Related articles:

Chrome Firefox comes with debugging tools (detailed tutorial)

About how Vue.js implements infinite scrolling loading

How to implement table filtering using Angular

How to implement a calculator using JavaScript

The above is the detailed content of How to use the Diff algorithm in Vue 2.5. For more information, please follow other related articles on the PHP Chinese website!