【Vue2. X source code learning 】 29 – Diff algorithm – node comparison | August more text challenge

One, foreword

In the previous part, diFF algorithm problem analysis and patch method transformation mainly involve the following points:

• Initialization and update process analysis;
• Problem analysis and optimization ideas;
• Comparison simulation between old and new virtual nodes;
• Patch method modification;

Next, diff algorithm – node alignment

---

Second, diff algorithm

The modification of patch method was completed in the last article.

Next, write the diff algorithm for comparing old and new virtual nodes in view update.

Before that, let’s introduce the Diff algorithm:

1. A brief introduction of diFF algorithm

Diff algorithm is also called peer comparison algorithm;Copy the code

First, dom is a tree structure:

In daily development, the positions of B and A or D and A are rarely swapped, that is, the father and son nodes are rarely swapped

Moreover, cross-layer node comparison is very troublesome. Therefore, considering application scenarios and performance, DIff algorithm only compares nodes of the same layer.

2. Comparison method of DIff algorithm

The diff algorithm compares the old and new virtual nodes, “two trees”

Start from the root node of the tree, namely LV1 layer:

After the comparison of A, check whether node A has son nodes, namely B and C, and compare B first:

After B is compared, check whether NODE B has sons, namely, D and E, and compare NODE D first

D) no son after the comparison; Continue to compare E, the current layer processing is completed, return to the upper layer processing;

Continue to compare C, C has a son F, continue to compare F, finally all comparisons are completed, end;

Therefore, diff alignment is a recursive alignment of depth-first traversal;

Note: Recursive alignment is the performance bottleneck of VUE2. When the component tree is large, there will be performance problems.Copy the code

3. Node reuse of diff algorithm

How to determine the two nodes for reuse, generally speaking, the same label elements can be reused; However, if the tags are the same and the actual scenario does not want to reuse them, you can use the key attribute to mark them. If the key is different, two elements with the same tag name will not be reused.Copy the code

So, when writing the code, the reuse criteria for the same node are as follows:

1. The label name and key are the same node.
2. If the label name and key are not exactly the same, it is not the same node;

The isSameVnode method is used to determine whether the nodes are the same:

// src/vdom/index.js

/** * Check whether two virtual nodes are the same virtual node * Logic: label name and key are identical *@param {*} NewVnode New virtual node *@param {*} OldVnode Old virtual node *@returns * /
export function isSameVnode(newVnode, oldVnode){
  return (newVnode.tag === oldVnode.tag)&&(newVnode.key === oldVnode.key); 
}
Copy the code

If the labels and keys of the old and new virtual nodes are the same, that is, isSameVnode returns true, the attributes of the multiplexed node are only updated.

---

Third, virtual node comparison

1, not the same node

Create two virtual nodes to simulate view updates:

// Simulate initial rendering
let vm1 = new Vue({
    data() {
        return { name: 'Brave'}}})let render1 = compileToFunction('<div>{{name}}</div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);

// Simulate the new virtual node newVnode
let vm2 = new Vue({
    data() {
        return { name: 'BraveWang'}}})let render2 = compileToFunction('<p>{{name}}</p>');
let newVnode = render2.call(vm2);

// diff: compare old and new virtual nodes
setTimeout(() = > {
    patch(oldVnode, newVnode); 
}, 1000);
Copy the code

Since the old and new virtual nodes have different tag names (simulate the v-if and V-else case),

So it is not the same node, regardless of reuse (abandon cross-layer reuse), directly replace the old real node with a new one

In the patch method, new and old virtual nodes are printed:

How to replace nodes

Because the label name of the parent node is different, the node cannot be overused. You need to generate real nodes based on the new virtual node and replace the old nodeCopy the code

1. Create a real node with a new virtual node:

   createElm(vnode);

2. Replace the old node, if you get the old real node?

   When generating real nodes based on vNode, real nodes are mapped to virtual nodes through vnode.el. Therefore, the old real nodes can be obtained through oldvNode. el.

   Note: $el is the entire tree, not available here;

Conclusion:

• New real node: createElm(vnode);
• The old real node: oldvNode.el

export function patch(oldVnode, vnode) {
  const isRealElement = oldVnode.nodeType;
  if(isRealElement){// Real node
    const elm = createElm(vnode);
    const parentNode = oldVnode.parentNode;
    parentNode.insertBefore(elm, oldVnode.nextSibling); 
    parentNode.removeChild(oldVnode);
    return elm;
  }else{ // diff: comparison between old and new virtual nodes
    console.log(oldVnode, vnode)
    if(! isSameVnode(oldVnode, vnode)){// It is not the same node
      returnoldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el); }}}Copy the code

When subcomponents are included, each component has a Watcher and will be locally updated through diff, not the entire tree. Therefore, as long as components are properly split, there is generally no performance problemCopy the code

2 is the case of the same node

IsSameVnode returns true if the element’s tag name and key are the same.

At this point, you just need to update the properties (text, style, and so on)

2-1 Text processing

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

// Text processing: text can be updated directly, because text has no sons
Vue.component (' XXX '); XXX is the component's tag
let el = vnode.el = oldVnode.el;  // Node reuse: assign the old node EL to the new node EL
if(! oldVnode.tag){// Text: no label name
  if(oldVnode.text ! == vnode.text){// Content change: Update the text content
    return el.textContent = vnode.text;// Replace old content with new content
  } else{
    return; }}Copy the code

2-2 element processing

Elements are processed when the new and old nodes are not both text

You need to refactor the updateProperties method:

Before reconstruction: directly pass in the real element vnode.el and data attributes, replace, only with rendering function

// src/vdom/patch.js

export function createElm(vnode) {
  let{tag, data, children, text, vm} = vnode;
  if(typeof tag === 'string'){
    vnode.el = document.createElement(tag)
    updateProperties(vnode.el, data)
    children.forEach(child= > {
      vnode.el.appendChild(createElm(child))
    });
  } else {
    vnode.el = document.createTextNode(text)
  }
  return vnode.el;
}

function updateProperties(el, props = {} ) { 
  for(let key in props){
    el.setAttribute(key, props[key])
  }
}
Copy the code

The first parameter is the new virtual node and the second parameter is the old data, since the old and new data need to be diff comparedCopy the code

After refactoring: updateProperties method, with both rendering and update functions

// src/vdom/patch.js

export function createElm(vnode) {
  let{tag, data, children, text, vm} = vnode;
  if(typeof tag === 'string'){
    vnode.el = document.createElement(tag)
    updateProperties(vnode, data) // Modify...
    children.forEach(child= > {
      vnode.el.appendChild(createElm(child))
    });
  } else {
    vnode.el = document.createTextNode(text)
  }
  return vnode.el;
}

// for the first rendering, assign el to vnode as oldProps
// 2, update the logic, and compare the old props with the data in vNode
function updateProperties(vnode, oldProps = {} ) { 
  let el = vnode.el; // The actual node in the DOM (which was assigned when the old node was reused)
  let newProps = vnode.data || {};  // Get the new data
  // Comparison between old and new: comparison between two objects
  for(let key in newProps){ // Just cover the old one with the new one, but be careful: the old one is inside, and the new one may not be inside
    el.setAttribute(key, newProps[key])
  }
  // If the old one does not exist in the new one, it needs to be deleted
  for(let key in oldProps){
    if(! newProps[key]){ el.removeAttribute(key) } } }Copy the code

Test: the node element names are the same, but the attributes are different

// Call the updateProperties property update
updateProperties(vnode, oldVnode.data);
Copy the code

let vm1 = new Vue({
    data() {
        return { name: 'Brave'}}})let render1 = compileToFunction('<div id="a">{{name}}</div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);

let vm2 = new Vue({
    data() {
        return { name: 'BraveWang'}}})let render2 = compileToFunction('<div class="b">{{name}}</div>');
let newVnode = render2.call(vm2);
setTimeout(() = > {
    patch(oldVnode, newVnode); 
}, 1000);
Copy the code

Test results:

2-3 style treatment

In addition to the attributes that need to be updated, there are other special attributes that need to be updated, such as the style style

let vm1 = new Vue({
    data() {
        return { name: 'Brave'}}})let render1 = compileToFunction('<div style="color:blue">{{name}}</div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);

let vm2 = new Vue({
    data() {
        return { name: 'BraveWang'}}})let render2 = compileToFunction('<div style="color:red">{{name}}</div>');
let newVnode = render2.call(vm2);
setTimeout(() = > {
    patch(oldVnode, newVnode); 
}, 1000);
Copy the code

El.setattribute (key, newProps[key]) cannot be used to handle both old and new elements

Style is a string type and cannot be replaced directly. Style attributes need to be collected and then compared and updated

function updateProperties(vnode, oldProps = {} ) {
  let el = vnode.el;
  let newProps = vnode.data || {};

  let newStyly = newProps.style || {};  // New style object
  let oldStyly = oldProps.style || {};  // Old style object
  
  // The old style object has it, but the new style object does not
  for(let key in oldStyly){
    if(! newStyly[key]){ el.style[key] =' '}}// There is one in the new style object, overwriting the old style object
  for(let key in newProps){
    if(key == 'style') {// Handle style styles
      for(let key in newStyly){
          el.style[key] = newStyly[key]
      }
    }else{
      el.setAttribute(key, newProps[key])
    }
  }

  for(let key in oldProps){
    if(! newProps[key]){ el.removeAttribute(key) } } }Copy the code

Before the update:

After the update:

At this point, the outer div has been diff updated, but the inner name attribute has not been updated

Next, compare the son nodes

---

Four, the end

This paper introduces the DIff algorithm-node comparison, mainly involving the following points:

• Diff algorithm, comparison method and node reuse are introduced
• Diff algorithm of outer node is implemented
• How to replace and update different nodes
• How to reuse the same node update: text, element, style

Diff algorithm – Comparison optimization

---

Maintenance logs:

20210806: Adjust the layout of the article;