The DOM and DIff algorithms explored here are easy to understand and simplified versions.

What is the structure of the virtual DOM

For example, the following DOM node is its virtual node

<ul>
    <li>hello</li>
</ul>
Copy the code
{
    sel: 'div'.data: {},
    children: [{sel: 'li'.data: {},
            children: undefined.test: 'hello'.elm: undefined.// Is defined as the DOM of the current virtual node
            key: undefined}].test: undefined.elm: undefined.// Is defined as the DOM of the current virtual node
    key: undefined
}
Copy the code

Create a function that generates the virtual DOM

export default function vnode (sel, data, children, text, elm) {
  let key = data.key
  return {
    sel, data, children, text, elm, key
  }
}
Copy the code

Create an H function to create a virtual DOM node

import vnode from './vnode.js';
// Writing a low-spec version of the h function must take three arguments
// The first two parameters are fixed, and the third parameter is unfixed
// Three types' text '[] h()
export default function h (sel, data, c) {
  if (arguments.length < 3) {
    throw new Error('By contrast, h has to take three arguments.')}if (typeof c == 'string' || typeof c == 'number') {
    / / type a
    return vnode (sel, data, undefined, c ,undefined)}else if (Array.isArray(c)) {
    / / type ii
    let children = [];
    for (let i = 0; i< c.length; i++) {
      if(! (typeof c[i] == 'object' && c[i].hasOwnProperty('sel'))) {
        throw new Error('There is a non-h function in the array argument passed in')
        // do not call c[I]
        // Collect c[I]
        
      }else{
        children.push(c[i])
      }
    }
    // End of the loop Indicates that children are collected and returned to the virtual node
    return vnode(sel, data, children, undefined.undefined)}else if (typeof c == 'object' && c.hasOwnProperty('sel')) {
    / / type 3
    // The only child passed in is children
    let children = [c]
    return vnode(sel, data, children, undefined.undefined)}else {
    throw new Error('Sorry for the wrong parameter')}}Copy the code

After creating the virtual DOM node, you need to tree the virtual node. Here’s the process

Create a patch function to tree the virtual DOM nodes

import vnode from './vnode.js'
import createElement from './createElement.js'
import patchVnode from './patchVnode.js'
export default function (oldVnode, newVnode) {
  // Determine whether the first node is a DOM node or a virtual node
  if (oldVnode.sel == ' ' || oldVnode.sel == undefined) {
    // The DOM node passed in is wrapped as a virtual node
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
  }
  // Check whether oldVnode and newVnode are the same node
  
  if (oldVnode.sel == newVnode.sel && oldVnode.key == newVnode.key) {
    console.log('Same node')
    
    patchVnode(oldVnode, newVnode)
  }else {
    console.log('Not the same node, forcibly insert new node, delete old node')
    let cnode = createElement(newVnode)
    oldVnode.elm.parentNode.insertBefore(cnode, oldVnode.elm)

    // Delete the old node
    oldVnode.elm.parentNode.removeChild(oldVnode.elm)
  }
}
Copy the code

Here, a patchVnode function is created and the process is combed out

import vnode from './vnode.js'
import createElement from './createElement.js'
import updateChildren from './updateChildren.js'
export default function patchVnode (oldVnode, newVnode) {
  // Determine whether the old and new nodes are the same object
  if (newVnode == oldVnode) return ;
    // Check whether the new newVnode has a text
  if(newVnode.text ! =undefined && (newVnode.children == undefined || newVnode.children.length==0)) {
    // newVnode has a text attribute
    console.log('newVnode has text property ')
    if(newVnode.text ! = oldVnode.text) {// To determine that the new virtual node text is different from the old one, change the old innerText to the new text
      oldVnode.elm.innerText = newVnode.text
    }
  }else {
    // newVnode has the children attribute
    console.log('newVnode 有 children 属性')
    // Check whether oldVnode has children
    if(oldVnode.children ! =undefined && oldVnode.children.length > 0) {
      // The old virtual node has children and the new and old have the most complex
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      The old one has no children. The new one has children
      // Empty the old node
      oldVnode.elm.innerHTML = ' ';
      // Add a new node traverses the children of the new node
      for (let i=0; i< newVnode.children.length; i++) {
        let ch = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(ch)
      }
    }
  }
}
Copy the code

The createElement function used earlier is also attached

// Create vNode as DOM without inserting
export default function createElement (vnode) {
  let domNode = document.createElement(vnode.sel);
  // These are dumb versions that can only have child elements or text
  
  if(vnode.text ! = =' ' && (vnode.children == undefined || vnode.children.length == 0)) {
    / / text
    domNode.innerText = vnode.text;
    // Insert the parent of the tree pole node on the orphan node
    // pivot.parentNode.insertBefore(domNode, pivot)
    console.log("Did you get up the tree?")}else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // Call child node 1 recursively. When does recursion 2 end
    for (let i=0; i< vnode.children.length; i++ ){
      let ch = createElement(vnode.children[i])
      domNode.appendChild(ch)
    }
  }
  vnode.elm = domNode
  return vnode.elm
}
Copy the code

The most complicated thing is that both the old and new nodes have children, and that’s where the diff algorithm comes in

Let’s generalize the terms involved in the DIff algorithm

Now that we know the basic language of the algorithm let’s look at the idea of the diff algorithm

The specific code is as follows

import createElement from './createElement.js';
import patchVnode from './patchVnode.js'

export function checkSameVnode (a, b) {
  return a.sel==b.sel && a.key==b.key
}

export default function updateChildren (parentElm, oldCh, newCh) {
  console.log('I am updateChildren')
  console.log(oldCh, newCh)
  let oldStartIdx = 0; / / the old before
  let oldEndIdx = oldCh.length-1; / / after the old
  let newStartIdx = 0; / / new front
  let newEndIdx = newCh.length-1; / / new after

  let oldStartVnode = oldCh[0]; // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[0]; // New front node
  let newEndVnode = newCh[newEndIdx]; // New post-node

  let keyMap = null
   
  while (oldStartIdx<=oldEndIdx && newStartIdx<=newEndIdx) {
    // The four judgements should first filter out those marked with undefined
    if (oldStartVnode==null || oldCh[oldStartIdx]==undefined) {
      oldStartVnode = oldCh[++ oldStartIdx]
    } else if (oldEndVnode== null || oldCh[oldEndIdx]==undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newStartVnode==null || newCh[newStartIdx]==undefined) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newEndVnode ==null || newCh[newEndIdx] == undefined) {
      newEndVnode = newCh[--newEndIdx]
    }else
    if (checkSameVnode(newStartVnode, oldStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      newStartVnode = newCh[++ newStartIdx]
      oldStartVnode = oldCh[++ oldStartIdx]
    } else if (checkSameVnode(newEndVnode, oldEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[-- oldEndIdx]
      newEndVnode = newCh[-- newEndIdx]
    } else if (checkSameVnode(newEndVnode, oldStartVnode)) {
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      patchVnode(oldStartVnode, newEndVnode)
      newEndVnode= newCh[--newEndIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (checkSameVnode(newStartVnode, oldEndVnode)) {
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      patchVnode(oldEndVnode,newStartVnode)
      newStartVnode = newCh[++ newStartIdx]
      oldEndVnode = oldCh[-- oldEndIdx]
    }else {
      console.log('None of them')

      // Find the map of the key
      if(! keyMap) { keyMap = {}for(let i=oldStartIdx; i<=oldEndIdx; i++ ) {
          let key = oldCh[i].key;
          if (key) {
            keyMap[key] = i
          }
        }
        console.log(keyMap)
      }

      // Find the sequence number of the current newStartIdx mapping in keyMap
      const idxInOld = keyMap[newStartVnode.key]

      console.log(idxInOld)
      if (idxInOld==undefined) {
        // If idxInOld is undefined, it is a new entry
        // newStartVnode is not a node yet
        console.log('If idxInOld is undefined it's a brand new entry')
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
        

      } else {
        // If not, you need to move
        // Call patch to update the node and move it
        let elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove,newStartVnode)
        // Set this item to undefined to indicate that it has been processed
        oldCh[idxInOld] = undefined

        // Move to before oldStartVnode
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)

      }
      // The pointer moves
      newStartVnode = newCh[++ newStartIdx]
    }
  }
  // When the loop ends, check to see if there is anything left
  if (newStartIdx<= newEndIdx) {
    console.log('New has a few nodes left to process')
    InsertBefore = null; // insertBefore = null
    for (let i= newStartIdx; i<= newEndIdx; i++) {
      // The new node is a virtual node, and the DOM has not been created yet
      console.log('The new node is a virtual node, the DOM has not been created yet'+oldStartIdx)
      parentElm.insertBefore(createElement(newCh[i]) ,oldCh[oldStartIdx].elm)
    }
  } else if (oldStartIdx<=oldEndIdx) {
    console.log('Old still has a few nodes left')
    // Delete nodes between oldStart and oldEnd in batches
    for (let i = oldStartIdx; i<= oldEndIdx; i++) {
      if (oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm)
      }
      
    }
  }
}
Copy the code

My code structure is as follows

Entry file in index.js

import h from './my-snabbdom/h.js';
import patch from './my-snabbdom/patch.js'

const container = document.getElementById('container')
const btn = document.getElementById('btn')
var myNode = h ('ul',{}, [
  h ('li', {'key': 'a'}, 'a'),
  h ('li', {'key': 'b'}, 'b'),
  h ('li', {'key': 'c'}, 'c'),
  h ('li', {'key': 'd'}, 'd')])var myNode1 = h ('ul',{}, [
  h ('li', {'key': 'e'}, 'e'),
  h ('li', {'key': 'd'}, 'd'),
  h ('li', {'key': 'c'}, 'c'),
  h ('li', {'key': 'b'}, 'b'),
  h ('li', {'key': 'a'}, 'a'),
  
])

patch(container, myNode)


btn.onclick = function () {
  patch(myNode, myNode1)
}
Copy the code