This is the sixth day of my participation in the August Text Challenge.More challenges in August

One, foreword

In the previous part, diff algorithm-out-of-order alignment mainly involves the following points:

  • The scheme of out-of-order comparison is introduced
  • The process analysis of out-of-order alignment is introduced
  • Realize the out-of-order comparison of the code logic

This article, diff algorithm stage combing

Second, initial rendering and view update process

  • The mountComponent method is called to mount the Vue at first rendering. Within the mountComponent method, a watcher is created.

  • When data is updated, the set method of Object.defineProperty is called. In the set method, dep.notify() is called to notify the collected Watcher to call update to render the update.

  • In the Update method of the Watcher class, queueWatcher is called to cache and de-redo the Watcher

  • The flushschedulerQueue method is called in the queueWatcher method to execute all watcher. runs and empty the queue

  • The run method of the Watcher class internally calls the Get method of the Watcher class: records the current Watcher and calls the getter

  • This. Getter is the view update method FN passed in when the Watcher class is instantiated, which is the updateComponent view rendering logic

  • Execute vm._render in updateComponent to regenerate the virtual node with the latest data and call Update to update the view

Third, the outer layer of diff algorithm is updated

In Vue, every time data changes, a diff comparison between old and new virtual nodes is performed instead of a full replacement of nodes:

  • For the first rendering, real nodes are generated from virtual nodes, replacing the original nodes
  • Update the rendering, generate new virtual nodes, and compare with the old virtual nodes, reuse the old nodes for rendering

The diff algorithm:

  • Also known as the same layer comparison algorithm;
  • Depth-first ergodic recursion;
  • Using the “head and tail pointer” processing;

By comparing the old and new virtual nodes, reuse the original nodes as much as possible to improve rendering performance.

The basis of node reusability:

  • If the label name and key are the same, it is judged as a reusable node.

The patch method is used to recursively update nodes. Oldvnode. nodeType nodeType is used to determine whether the node is a real node.

  • Non-real nodes, i.e. real DOM, perform initial rendering logic
  • If it is a real node, you need to compare the new and old virtual nodes

Comparison between old and new virtual nodes:

  • Replace oldvNode.el with a new real node createElm(vNode).

oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el);

  • When the node is the same, reuse the old node, update the text, style and other attributes;

Text processing:

  • The text node has no label name
  • The text node has no sons

Element handling:

  • Attributes of both old and new elements are overwritten with new values;
  • Delete the properties of the new one and the old one.

Style handling:

  • Old style object has, new style object does not have, delete redundant style object;
  • In the new style object, overwrites the old style object;

Fourth, comparison optimization of DIff algorithm

1. The situation of the new and old son nodes

  • Situation 1: The old one has a son, the new one doesn’t

    Processing method: directly delete redundant old DOM elements;

  • Situation 2: The old has no son, the new has a son

    Solution: Directly put the new child node into the corresponding old node.

  • Situation 3: Both parents have sons

    Treatment methods: DiFF comparison;

2. Diff comparison of new and old son nodes

  • The method of head and tail double Pointers is used to compare the new and old son nodes.

  • When both the old node and the new node have sons, the comparison is made between head, tail, head and tail.

  • Head head, tail tail, head tail, tail head are not hit, disorderly comparison;

Fifth, the out-of-order comparison of diff algorithm

  • Create a node key mapping and index mapping according to the old son set. Use the new child nodes to search the mapping in turn to see if there are reusable nodes.
  • If a reusable node exists, update the attributes of the reusable node and move it to the corresponding location. (The old position moved should be marked short)
  • There is no multiplexing node. Create a node and add it to the corresponding location.
  • Finally, delete the old nodes that cannot be reused.

Sixth, the end of diff algorithm

1. Problem analysis

So far, all the logic writing of diff algorithm has been completed, but the simulation of new and old nodes update;

The reason is that patch(vm.$el, vnode) is executed every update.

// src/lifecycle.js

export function lifeCycleMixin(Vue){
  Vue.prototype._update = function (vnode) {
    const vm = this;
    // Pass the current real element vm.$el, the virtual node vnode, and return the new real elementvm.$el = patch(vm.$el, vnode); }}Copy the code

When simulating diff updates with two virtual nodes, we have modified the Patch method to support both initial rendering and updated rendering:

// src/vdom/patch.js

/** * Insert the virtual node into the element after converting it into a real node@param {*} OldVnode Old virtual node *@param {*} Vnode New virtual node *@returns             New real element */
export function patch(oldVnode, vnode) {
  const isRealElement = oldVnode.nodeType;  // Real node: 1, virtual node: no such property
  if (isRealElement) {// Real node
    // 1, create a real node based on the virtual node
    const elm = createElm(vnode);
    // 2, replace the old node with the real node
    // Find the parent node of the element
    const parentNode = oldVnode.parentNode;
    // find the nextSibling of the old node (return null if nextSibling does not exist)
    const nextSibling = oldVnode.nextSibling;
    // insert the new node elm before the nextSibling of the old node el
    // Note: If nextSibling is null, insertBefore equals appendChild
    parentNode.insertBefore(elm, nextSibling);
    // Delete the old node el
    parentNode.removeChild(oldVnode);
    
    return elm;
  } else {
    // diff: comparison between old and new virtual nodes
    if(! isSameVnode(oldVnode, vnode)) {// If the node is not the same, replace the old node with the new one without considering reuse (abandon cross-layer reuse)
      return oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el);
    }

    // Reuse the same node (reuse the old), and then update the different places (attributes), note the special treatment of the text, the text is not the label name

    // Text processing: the text can be updated directly, because the text does not have Vue.component (' XXX ') in the component, which is the component's tag
    let el = vnode.el = oldVnode.el;  // Node multiplexing: assign old node EL to new node EL
    if(! oldVnode.tag) {// Text: no label name
      if(oldVnode.text ! == vnode.text) {// Update the text content: update the old content with the new content
        returnel.textContent = vnode.text; }}// Element processing: the same node, and the new and old nodes are not text
    updateProperties(vnode, oldVnode.data);

    // Compare son nodes
    let oldChildren = oldVnode.children || {};
    let newChildren = vnode.children || {};
    // Situation 1: The old has a son, the new has no son; Just kill the old DOM element
    if (oldChildren.length > 0 && newChildren.length == 0) {
      el.innerHTML = ' ';// Write violence directly empty; A better approach is to encapsulate the removeChildNodes method: remove all the children, because they may contain components
      // Situation 2: The old has no son, the new has a son; Just insert the new one
    } else if (oldChildren.length == 0 && newChildren.length > 0) {
      newChildren.forEach((child) = > {// Note that child is a virtual node and needs to become a real node
        let childElm = createElm(child); // Create a real node based on the new virtual node
        el.appendChild(childElm);// Put the generated real node into the DOM
      })
      // Situation 3: Both parents have sons
    } else {  // Recursive: updateChildren calls patch, patch, and updateChildren (the patch method is the entry)
      updateChildren(el, oldChildren, newChildren)
    }
    
    return el;// Returns the new node}}Copy the code

2. Normal use

Comment out all the code for simulating node updates and modify index.html

<! -- Diff algorithm -->
<body>
  <! -- Scenario: div tag reuse, update only the text name in span tag -->
  <div id="app">
    <span>{{name}}</span>
  </div>
  <script src="./vue.js"></script>
  <script>
    let vm = new Vue({
      el: "#app".data() {
        return { name: 'Brave'}}});setTimeout(() = > {
      vm.name = "BraveWang";
    }, 1000);
  </script>
</body>
Copy the code

2. Test the effect before modification

Test the effect of patch method before modification:

Test result: all the div tags are dried and created again.

$el = patch(vm.$el, vnode); , does not distinguish between initial render and updated render;

3. How to distinguish between initial rendering and updated rendering

How do I distinguish between initial render and updated render?

  • Save the current Vnode on vm.preVnode for the first rendering
  • For the second rendering, take vm.preVnode first, which has the value of updating the render
  • Initial render, executepatch(vm.$el, vnode)
  • Update render, executepatch(preVnode, vnode)

4. Code implementation

export function lifeCycleMixin(Vue){
  Vue.prototype._update = function (vnode) {
    const vm = this;
    // Take the previous preVnode
    let preVnode = vm.preVnode;
    // Save the current vNode before rendering
    vm.preVnode = vnode;
    PreVnode = preVnode; preVnode = preVnode; No value is initial render
    if(! preVnode){/ / at the beginning of rendering
      // Pass the current real element vm.$el, the virtual node vnode, and return the new real element
      vm.$el = patch(vm.$el, vnode);
    }else{// Update render: Diff comparison between old and new virtual nodesvm.$el = patch(preVnode, vnode); }}}Copy the code

5. Test the effect after modification:

Test the effect of modified patch method:

Test result: div tag is reused, only name in span is updated;

Seven, the end

In this paper, the periodic review of DIFF algorithm mainly involves the following points:

  • Initial rendering and view update process;
  • Diff algorithm outer layer update;
  • Comparison optimization of DIff algorithm;
  • Diff algorithm out-of-order alignment;
  • Initial render and update render judgment;

In the next part, the initialization process of components is introduced.

Update log

20210807: Add “Diff algorithm end” section; Update the “end” section; Update the title and abstract of the article;