Author of songbao Write Code, one of the day, lab, etc. A bytedance engineer who loves to toss, is committed to the whole stack, and is working hard to grow, star Sea, the future can be expected.

One, foreword

Some students asked: Can you elaborate on the DIff algorithm?

To put it simply: Diff algorithm is a means of optimization. It compares the difference between the two modules before and after, and the process of repairing (updating) the difference is called patch, also known as patching.

For details, please read this article. If you have any questions, please contact songbao to write code.

The main problems solved in this paper are:

  • 1. Why the diff algorithm?
  • 2. Diff algorithm of virtual DOM
  • 3. Why the virtual DOM?
  • 4. Complexity and characteristics of DIFF algorithm?
  • 5. How are vue template files compiled and rendered?
  • 6. Is there a difference between diff in vue2. X and vue3
  • 7. Snabbdom algorithm, the source of DIFF algorithm
  • 8. What are the differences between DIFF algorithm and SNabbDOM algorithm?

Second, why talk about the diff algorithm?

Since the DIff algorithm is the core point of VUe2. X, vue3. X and React, understanding the DIFF algorithm is more helpful to understand the nature of each framework.

Speaking of “diff algorithms”, I have to say “virtual Dom” because the two are closely related.

Such as:

  • Vue’s responsivity principle?
  • How is the vue template file compiled?
  • Introduce the Virtual Dom algorithm?
  • Why use virtual DOM?
  • Diff algorithm complexity and the biggest characteristics?
  • How do nodes compare in the diff algorithm of vue2. X?

, etc.

Diff algorithm of virtual DOM

Let’s talk about virtual Dom first, which is to realize Dom through JS simulation. Then the difficulty is how to judge the difference between the old object and the new object.

Dom is a multi-fork tree structure. If you need to completely compare the differences between two trees, the algorithm’s time complexity O(n ^ 3) is difficult to accept, especially when N is very large. Therefore, the React team optimized the algorithm to achieve O(n) complexity to compare the differences.

The key to achieving O(n) complexity is to compare nodes only at the same level, not across layers, given that few DOM elements are moved across layers in real business.

The steps of virtual DOM difference algorithm are divided into two steps:

  • The object is first traversed from top to bottom and left to right, the depth of the tree, adding indexes to each node to facilitate the final rendering of the differences
  • Once the node has child elements, determine if the child elements are different

3.1 DIFF algorithm in VUE

In actual diff algorithm comparison, node comparison mainly includes five kinds of rules

  • 1. If both the old and new vNodes are static, have the same key (representing the same node), and the new VNode is clone or once (marked with the V-once attribute, rendering only once), Just replace ELM and componentInstance.

  • 2. If both the old and new nodes have children, diff is performed on the children and updateChildren is called, which is also the core of the diff.

  • 3. If the old node has no children and the new node has children, first empty the text content of the old node DOM, and then add children to the current DOM node.

  • 4. When the new node has no children and the old node has children, all children of the DOM node are removed.

  • 5, when the old and new nodes have no children, just text replacement

Partial source github.com/vuejs/vue/b… As follows:

function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
  if (oldVnode === vnode) {
    return;
  }

  if (isDef(vnode.elm) && isDef(ownerArray)) {
    // clone reused vnode
    vnode = ownerArray[index] = cloneVNode(vnode);
  }

  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;
  }
  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);
  }
  if (isUndef(vnode.text)) {
    // The child nodes are defined, and are not the same, use diff algorithm comparison
    if (isDef(oldCh) && isDef(ch)) {
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);// The new node has child elements. The old node does not have
    } else if (isDef(ch)) {
      if(process.env.NODE_ENV ! = ='production') {
        / / check the key
        checkDuplicateKeys(ch);
      }
      // Clear the text property of the old node
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ');
      // Add a new Vnode
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      // If the child of the old node has content, the new node does not. Then simply delete the content of the old section idea element
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
      / / as above. It's just a text node
    } else if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, ' ');
    }
    // If the text nodes are different, replace the node contents
  } 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); }}Copy the code

3.2 React Diff Algorithm

In the reconcileChildren function’s entries

workInProgress.child = reconcileChildFibers(
  workInProgress,
  current.child,
  nextChildren,
  renderLanes,
);
Copy the code
  • WorkInProgress: Passed in as the parent, the return of the first newly generated fiber is directed to it.
  • Current. Child: The old fiber node is compared with the newly generated ReactElement when the diff generates the new fiber node.
  • NextChildren: The newly generated ReactElement will use it as a standard to generate new Fiber nodes.
  • RenderLanes: This rendering priority will eventually be attached to the Lanes property of the new fiber.

The two principals of diFF are oldFiber (current-.child) and newChildren (nextChildren, new ReactElement), which are two different data structures.

Part of the source

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes,
) :Fiber | null {
  /* * returnFiber: parent of currentFirstChild * currentFirstChild: parent of WIP (Fiber) * newChildren: The component's render method renders new ReactElement nodes * lanes: priority-dependent * */
  // resultingFirstChild is the first fiber in the new Fiber list after diff.
  let resultingFirstChild: Fiber | null = null;
  // resultingFirstChild is the first fiber in the new linked list.
  // previousNewFiber is used to connect subsequent new fibers to the first fiber
  let previousNewFiber: Fiber | null = null;

  // oldFiber node, with which the new child node is compared
  let oldFiber = currentFirstChild;
  // Store the location of the fixed node
  let lastPlacedIndex = 0;
  // Stores the index of the new node traversed
  let newIdx = 0;
  // Record the next node of oldFiber traversed so far
  let nextOldFiber = null;

  // This loop processes node updates and interrupts traversal depending on whether the node is reusable
  for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
    // newChildren traversal is complete, oldFiber chain traversal is not complete, then need to interrupt traversal
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      // Use nextOldFiber to store the next node of oldFiber currently traversed
      nextOldFiber = oldFiber.sibling;
    }
    // Create a new node and check whether the key and tag are the same in updateSlot
    // oldFiber is reused only for DOM elements with the same key and tag
    // and return out, otherwise return null
    const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);

    // If newFiber is null, the key or tag is different. Therefore, nodes cannot be reused and traversal is interrupted
    if (newFiber === null) {
      if (oldFiber === null) {
        // If oldFiber is null, oldFiber is done
        // In the following scenario, D indicates the newly added node
        // Old a-b-C
        // new a-b-c-d oldFiber = nextOldFiber;
      }
      break;
    }
    if (shouldTrackSideEffects) {
      // shouldTrackSideEffects is true to indicate that this is the update process
      if (oldFiber && newFiber.alternate === null) {
        // newFiber. Alternate equals oldFiber. Alternate
        // oldFiber is the WIP node, and its alternate is the current node
        // oldFiber exists, and the updated new fiber node does not have the current node,
        After the update, there will be no current node displayed on the screen, but after the update, there will be WIP
        // The node will be called the current node, so you need to delete the existing WIP nodedeleteChild(returnFiber, oldFiber); }}// Record the position of the fixed node
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // Connect the new fiber to a one-way list with sibling Pointers
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    // Point the oldFiber node to the next one and move it in sync with newChildren's traversal
    oldFiber = nextOldFiber;
  }

  // Handle node deletion. After traversing the new child node, it indicates that the remaining oldFiber is useless and can be deleted.
  if (newIdx === newChildren.length) {
    // When newChildren completes traversal, delete the remaining nodes in oldFiber chain
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  // Process the new node. We're done iterating, we're doing everything that we can reuse, so that means the new ones are being inserted
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      // Create new Fiber nodes based on the newly generated ReactElement
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      // Record the position of the fixed node lastPlacedIndex
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // Connect the newly generated fiber node into a one-way list with sibling Pointers
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }
  // Put the remaining old children into a map of oldFiber nodes with key as the key
  // When a new oldFiber node is created based on the oldFiber node, the oldFiber node can be quickly identified by the key
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // The node moves
  for (; newIdx < newChildren.length; newIdx++) {
    // Create a new fiber based on the oldFiber node in the map
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );
    if(newFiber ! = =null) {
      if (shouldTrackSideEffects) {
        if(newFiber.alternate ! = =null) {
          // Since the remaining nodes in newChildren are likely to be the same as oldFiber, but in a different position,
          // However, it may be a new one.

          // If newFiber's alternate is not empty, newFiber is not new.
          OldFiber is already in use, so it needs to be
          // Delete oldFiber from map
          existingChildren.delete(newFiber.key === null? newIdx : newFiber.key); }}// Move nodes, the core of multi-node diff, where nodes really move
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // Connect the new fiber to a one-way list with sibling Pointers
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}if (shouldTrackSideEffects) {
    // Delete the remaining oldFiber
    existingChildren.forEach((child) = > deleteChild(returnFiber, child));
  }
  return resultingFirstChild;
}
Copy the code

Why use the virtual DOM?

In many cases, manual dom optimization is indeed more efficient than virtual DOM. For simple DOM structure, manual optimization has no problem, but when the page structure is very large and complex, manual optimization will take a lot of time, and the maintainability is not high, so it cannot guarantee that everyone has the ability to manually optimize. At this point, the virtual DOM solution came into being.

Virtual DOM is a solution to “the performance impact of too much dom manipulation.”

The Virtual DOM is often not optimal, but it is universal and strikes a balance between efficiency and maintainability.

** Virutal dom meaning: **

  • 1. Optimize DOM manipulation by providing a simple object instead of a complex DOM object
  • 2. Provide an intermediate layer, JS to write UI, ios and Android to render, just like reactNative.

V. Complexity and characteristics of diFF algorithm?

The diff of vue2. X is located in patch.js file. This algorithm is derived from SnabbDOM and its complexity is O(n). Understanding the diff process allows us to use the framework more effectively. The React diff is very much the same as the Vue diff.

Biggest feature: Comparisons are made only at the same level, not across levels.

<! Before -- -- -- ><div>              <! -- Level 1 -->
  <p>              <! -- Level 2 -->
    <b> aoy </b>   <! -- Level 3 -->
    <span>diff</Span>
  </p>
</div><! After -- -- -- ><div>             <! -- Level 1 -->
  <p>              <! -- Level 2 -->
    <b> aoy </b>   <! -- Level 3 -->
  </p>
  <span>diff</Span>
</div>
Copy the code

Compare before and after: It might be desirable to move directly after

, which is optimal.

But the actual diff operation is:

  • 1, remove<p>In the<span>;
  • Create a new one<span>Into the<p>Behind the. Because it’s new<span>At level 2, the old one at level 3, is a comparison of different levels.

How are vue template files compiled and rendered?

The DIff algorithm is also used in VUE, so it’s important to understand how vUE works. Through this question, we can have a good grasp of the diff algorithm in the whole compilation process, which link, what operation, and then use the DIff algorithm output?

Explanation:

1. Mount function

The mount function basically gets template and goes to compileToFunctions.

compileToFunction

The function compileToFunction mainly compiles template to the render function. First read cache, no cache to call compile method to get the render Function string form, through the new Function to generate the render Function.

// If there is a cache, just fetch it from the cache
const key = options && options.delimiters ? String(options.delimiters) + template : template;
if (cache[key]) {
  return cache[key];
}
const res = {};
const compiled = compile(template, options); // compile will be explained later
res.render = makeFunction(compiled.render); // Generate the render Function with new Function and cache it
const l = compiled.staticRenderFns.length;
res.staticRenderFns = new Array(l);
for (let i = 0; i < l; i++) {
  res.staticRenderFns[i] = makeFunction(compiled.staticRenderFns[i]);
}

/ /...

return (cache[key] = res); // Record to the cache
Copy the code

3. Compile the function

The compile function compiles the template to the string form of the render function. Let’s focus on render

After the Render method has been generated, it will go to mount for DOM updates. The core logic of this method is as follows:

// Triggers beforeMount Lifecycle hooks
callHook(vm, 'beforeMount');
// Key: Create a new Watcher and assign it to vm._watcher
vm._watcher = new Watcher(
  vm,
  function updateComponent() {
    vm._update(vm._render(), hydrating);
  },
  noop,
);
hydrating = false;
// manually mounted instance, call mounted on self
// mounted is called for render-created child components in its inserted hook
if (vm.$vnode == null) {
  vm._isMounted = true;
  callHook(vm, 'mounted');
}
return vm;
Copy the code

  • A New Watcher object is created. After the Watcher object is created,

  • The passed method vm._update(vm._render(), hydrating) is run. The main function of vm._render() is to run the render method previously generated by compiler and return a vNode object.

  • Vm.update () compares the new VDOM to the current VDOM and renders the difference to the actual DOM tree. (The implementation principle behind Watcher: the responsivity principle of VUe2. X)

Compile is the string form of a render function that compiles a template. The core code is as follows:

export function compile(template: string, options: CompilerOptions) :CompiledResult {
  const AST = parse(template.trim(), options); //1. parse
  optimize(AST, options); //2.optimize
  const code = generate(AST, options); //3.generate
  return {
    AST,
    render: code.render,
    staticRenderFns: code.staticRenderFns,
  };
}
Copy the code

Compile the function consists of three main steps:

  • The parse,
  • optimize
  • generate

Each output contains

  • AST string
  • StaticRenderFns object string
  • String of the render function.

Parse function: The main function is to parse the Template string into an AST (abstract syntax tree). The parse function converts the template structure (directives, attributes, and tags) into an ASTElement and generates an AST.

Optimize function (SRC/compiler/optomizer. Js) : the main function is to mark a static node. In the subsequent patch process, the old and new VNode tree structures are compared to optimize. Nodes marked as static are ignored in subsequent diff algorithms without detailed comparisons.

The generate function (SRC/compiler/codegen/index. Js) : main function according to the AST splicing generates render function string structure.

const code = AST ? genElement(AST) : '_c("div")';
staticRenderFns = prevStaticRenderFns;
onceCount = prevOnceCount;
return {
  render: `with(this){return ${code}} `.// wrap with(this)
  staticRenderFns: currentStaticRenderFns,
};
Copy the code

Which genElement function (SRC/compiler/codgen/index. Js) is generated according to the different methods of the attribute of the AST call string.

In a word:

That’s the three core steps of compile,

  • After compile we get the render Function as a string, followed by the new Function to get the actual render Function.

  • After the data changes, executes the watcher _update function (SRC/core/instance/lifecycle. Js), _update function performs the render function, output a new VNode tree structure data.

  • Then call the patch function to get the new VNode and compare it with the old VNode. Only the changed nodes will be updated to the new real DOM tree.

4. Patch function

Patch function is the diff function comparing old and new VNodes. It mainly aims to optimize DOM and minimize dom operation behavior through algorithm. Diff algorithm is derived from SNabbDOM and is the core of VDOM thought. The algorithm of SNabbDOM is optimized for the goal of DOM operation with fewer cross-level add and delete nodes. It will only be carried out at the same level without cross-level comparison.

To summarize

  • The compile function converts the template into an AST, optimizes the AST, and then converts the AST into the string form of the Render function.
  • Then the new Function is used to get the real render Function, and the render Function is associated with the data through Watcher.
  • When the data changes in reverse direction, the patch function is called, the render function is executed, the new VNode is generated, the old VNode is diff, and the DOM tree is finally updated.

Vue2. X, vue3. X, React diff.

In summary:

  • The core diff algorithm of VUe2. X adopts the algorithm of double-end comparison, starting from both ends of the old and new children at the same time, with the help of key reusable nodes.

  • Vue3. X borrows some other algorithms from Inferno (github.com/infernojs/i…) Solution: 1. Preprocessing the same pre – and post-elements; 2. Once we need to do a DOM move, the first thing we need to do is find the longest increasing subsequence of source.

In the creation of VNode to determine the type, and in the mount/patch process to determine the type of a VNode bit operation, on the basis of this optimization with Diff algorithm, the performance is improved.

You can take a look at the source of vue3. X: github.com/vuejs/vue/b…

  • React uses keys and tags to make trade-offs between nodes. Complex comparisons can be directly intercepted and reduced to simple operations such as node movement, addition and deletion.

A comparison of oldFiber to the new ReactElement node will generate new Fiber nodes marked with effectTags that will be connected to the workInProgress tree as new WIP nodes. The structure of the tree is thus determined bit by bit, and the new workInProgress nodes are basically finalized. After diff, the beginWork node of the workInProgress node is complete, and the completeWork stage is then entered.

Diff algorithm source SNabbDOM algorithm

Snabbdom algorithm: github.com/snabbdom/sn…

Positioning: A virtual DOM library focused on simplicity, modularity, power, and performance.

1. The SNabbDOM defines the Vnode type

The types of vNodes defined in snabbDOM (github.com/snabbdom/sn…)

export interface VNode { sel: string | undefined; / / the abbreviation of the selector data: VNodeData | undefined; / / the following VNodeData interface children: the content of the Array < VNode | string > | undefined; Elm: / / child Node Node | undefined; / / element, store the real HTMLElement text: string | undefined; / / if it is a text node, the stored text key: key | undefined; } export interface VNodeData {props? : Props; attrs? : Attrs; class? : Classes; style? : VNodeStyle; dataset? : Dataset; on? : On; attachData? : AttachData; hook? : Hooks; key? : Key; ns? : string; // for SVGs fn? : () => VNode; // for thunks args? : any[]; // for thunks is? : string; // for custom elements v1 [key: string]: any; // for any other 3rd party module }Copy the code

2, init function analysis

Init function address:

Github.com/snabbdom/sn…

The init() function takes an array of modules and an optional domApi object as arguments and returns a function, the patch() function.

The domApi object’s interface contains many methods for DOM manipulation.

3. Patch function analysis

Source:

Github.com/snabbdom/sn…

  • The init() function returns a patch() function
  • The patch() function takes two VNode objects as arguments and returns a new VNode.

4. H function analysis

Source:

Github.com/snabbdom/sn…

The h() function takes multiple arguments, including an sel argument that mounts the contents of the node to the container and returns a new VNode.

What are the differences between diff algorithm and SNabbDOM algorithm?

Vue2. X is not a complete SNabbDOM algorithm, but a vUE based scene for some modifications and optimization, mainly reflected in the judgment of key and diff.

1. In SNabbDOM, key and SEL are used to determine whether the node is the same. Then, in VUE, some judgments are added to determine whether the tag name is consistent, whether it is an annotation node, and whether it is an asynchronous node when the key is equal. Or whether the type is the same for input, etc.

Github.com/vuejs/vue/b…

/ * * *@param A is compared to node *@param B Compare nodes * Compare whether two nodes are the same * the following conditions are required: the key is the same, the tag is the same, whether they are annotation nodes, whether they have defined data, if it is input tag, then the type must be the same */
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)))
  );
}
Copy the code

2. Diff difference: patchVnode is a function to compare template changes, and diff may be used or directly updated.

Github.com/vuejs/vue/b…

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
  constcanMove = ! removeOnly;if(process.env.NODE_ENV ! = ="production") {
    checkDuplicateKeys(newCh);
  }

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(
        oldStartVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(
        oldEndVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      );
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(
        oldStartVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      );
      canMove &&
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        );
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(
        oldEndVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      canMove &&
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // New element
        createElm(
          newStartVnode,
          insertedVnodeQueue,
          parentElm,
          oldStartVnode.elm,
          false,
          newCh,
          newStartIdx
        );
      } else {
        // vnodeToMove The node to be moved
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(
            vnodeToMove,
            newStartVnode,
            insertedVnodeQueue,
            newCh,
            newStartIdx
          );
          oldCh[idxInOld] = undefined;
          canMove &&
            nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        } else {
          // same key but different element. treat as new element
          createElm(
            newStartVnode,
            insertedVnodeQueue,
            parentElm,
            oldStartVnode.elm,
            false, newCh, newStartIdx ); }}// vnodeToMove The node to be movednewStartVnode = newCh[++newStartIdx]; }}// The old node is complete, the new node is not complete
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm;
    addVnodes(
      parentElm,
      refElm,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
    );
    // New completed, old not completed
  } else if(newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx); }}Copy the code

Read more

  • AB experiment: BASIC principle of intelligent tuning MAB multi-arm slot machine

  • AB Experimental basis – proper noun

  • AB experimental basis – What is AB? What is the value of AB? Why the AB experiment?

  • (57) How to flatten an array?

  • Depth first traversal and breadth first traversal.

  • (55 题) To achieve a full array of arrays

  • 2020 “Songbao Write Code” personal year-end summary: the future can be expected

reference

  • Github.com/vuejs/vue/b…
  • Github.com/infernojs/i…
  • Github.com/vuejs/vue/b…
  • Github.com/snabbdom/sn…
  • Github.com/snabbdom/sn…
  • Github.com/snabbdom/sn…
  • Github.com/snabbdom/sn…
  • Github.com/snabbdom/sn…
  • Github.com/vuejs/vue/b…
  • Github.com/vuejs/vue/b…

Thank you for support

Songbao, the author of “Songbao Writes Code”, also used Saucxs to mix in the river’s lake, watermark-DOM package 700+ STAR, used to be in the ACM school team, did AB experiment in byte, served as the interviewer, set the school enrollment programming questions, love to struggle, committed to the full stack, like to challenge themselves. The public number has selected articles, advanced learning, a daily problem, laboratory, AB experiment, byte push and other modules, welcome to pay attention to and consult, and songbao write code together, flush!