One, virtual DOM implementation

The entire process of the virtual DOM:

  1. Create a data structure for the virtual DOM
  2. Generating the virtual DOM
  3. Mount the virtual DOM
  4. If the parent element does not have a virtual DOM, the mount method is called directly
  5. If the parent element has a virtual DOM and needs to be updated, the patch method is called to update it
  6. Update the types and props of the old and new VNodes in the patch method
  7. The next step is to update the children of the old and new VNodes
  8. If both children of the old VNode and children of the new VNode exist, nodeTree needs to be updated using the diff algorithm

1. Define the data structure of the virtual DOM

// h.js // VNode const createVNode = (type, props, key, $$) => {return {type, // div/CompoentA/" (text) Const createText = (text) => {return {type: '', props: {nodeValue: Text + ''}, $$: {flag: node_flag. text}} export const NODE_FLAG = {EL: 1, // Element text: 1 < < 1}Copy the code

2. Define object methods to generate the virtual DOM

// h.js // h('div', { className: 'padding20'}, 'hello world! ') export const h = (type, props, ... kids) => { props = props || {} let key = props.key || void 0 kids = normalize(props.children || kids) if (kids.length) props.children = kids.length === 1 ? kids[0] : kids const $$ = {} $$.el = null $$.flag = type === '' ? NODE_FLAG.TEXT : NODE_FLAG.EL return createVNode(type, props, key, $$)}Copy the code

Example:

import { h } from './h.js'
const vnode = h(  'ul',  {   
                  style: {      
                       width: '100px',   
                       height: '100px',    
                       backgroundColor: 'green'   
                  }  
                }, 
                [    
                    h('li', { key: 'li-a' }, 'this is li a'), 
                    h('li', { key: 'li-b' }, 'this is li b'), 
                    h('li', { key: 'li-c' }, 'this is li c'),   
                     h('li', { key: 'li-d' }, 'this is li d'), 
                ])
console.log(vnode)
Copy the code

3. Apply colours to a drawing

//render.js import { mount } from './mount.js' import { patch } from './patch.js' export const render = (vnode, Parent) => {let prev = parent._vnode // If (! Prev) {// Mount (vnode, parent) parent._vnode = vnode} else {if (vnode) {// Both old and new vnodeTree exist, Patch (prev, vnode, Parent) parent._vnode = vnode} else {// There is no new vnodeTree, remove parent.removechild (prev.$$.el)}}Copy the code

4. Mount operation Mount

// mount.js import { NODE_FLAG } from './h.js' import { patchProps } from './patch.js' export const mount = (vnode, parent, refNode) => { if (! Parent) throw new Error(' please pass in parent ') const $$= vnode.$$// for TEXT node if ($$. Flag & node_flag.text) {const el = Document.createtextnode (vnode.props. NodeValue) vnode.el = el // Render text node parent.appendChild(el)} else if ($$.flag & Node_flag.el) {const {type, props } = vnode const el = document.createElement(type) vnode.el = el const { children, ... Rest} = props if (object.keys (rest).length) {for (let key of object.keys (rest)) { // properties in patch props, such as class, // TMP/props (key, null, rest[key], el) } } if (children) { const __children = Array.isArray(children) ? children : [children] for (let child of __children) {// If chldren exist, mount(child, el) to their VNode corresponding element}} // render location refNode? parent.insertBefore(el, refNode) : parent.appendChild(el) }}Copy the code

5. PatchProps method

// patch.js export const patchProps = (key, prev, next, el) => { // style if (key === 'style') { // { style: { margin: '0px', padding: '10px' }} if (next) { for (let k in next) { el.style[k] = next[k] } } // { style: { padding: '0px', color: 'red' } } if (prev) { for (let k in prev) { if (! next.hasOwnProperty(k)) { el.style[k] = '' } } } } // class else if (key === 'className') { if (! el.classList.contains(next)) { el.classList.add(next) } } // events else if (key[0] === 'o' && key[1] === 'n') { prev &&  el.removeEventListener(key.slice(2).toLowerCase(), prev) next && el.addEventListener(key.slice(2).toLowerCase(), next) } else if (/\[A-Z]|^(? :value|checked|selected|muted)$/.test(key)) { el[key] = next } else { el.setAttribute && el.setAttribute(key, next) } }Copy the code

6. Patch method

// patch.js export const patch = (prev, next, parent) => { // type: 'div' -> type: 'p' // type not the same, remove old, mount new if (prev.type! == next-type) {parent.removechild (prev.el) mount(next, parent) return} {props: {children: prevChildren, props: {children: prevChildren,... prevProps } } = prev const { props: { children: nextChildren, ... NextProps}} = next // patchProps const el = (next.el = prev.el) // Patch Needs to update the props for (let key of Object.keys(nextProps)) { let prev = prevProps[key], let next = nextProps[key] patchProps(key, prev, next, El)} // patch props for (let key of object.keys (prevProps)) {if (! nextProps.hasOwnProperty(key)) patchProps(key, prevProps[key], null, el) } // patch children patchChildren(prevChildren, nextChildren, el)}Copy the code

7. PatchChildren method

// patch.js import { odiff } from './optimization-diff.js' const patchChildren = (prev, next, Parent) => {// diff => {// if there is no old node if (! prev) { if (! } else {next = array.isarray (next)? Next: [next] for (const c of next) {// Mount (c, parent)}}} // Children else if (prev &&! Array.isArray(prev)) { if (! next) parent.removeChild(prev.el) else if (next && ! Array.isArray(next)) { patch(prev, next, parent) } else { parent.removeChild(prev.el) for (const c of next) { mount(c, parent) } } } else odiff(prev, next, parent)}Copy the code

Diff algorithm

1. Diff algorithm for direct comparison

Process simulation

PrevMap {b:0, a: 1}; prevMap {b:0, a: 1}; prevMap {b:0, a: 1}; prevMap {b:0, a: 1}; [c, b, a]; [c, b, a]; [C, b, a]; [c, D, b, a] [C, D, a, b] [C, D, a, b] [c, d, a]

import { mount } from './mount.js'import { patch } from './patch.js' export const diff = (prev, next, parent) = >{ let prevMap = {} let nextMap = {} // old tree children for (let i = 0; i < prev.length; i++) { let { key = i + '' } = prev[i] prevMap[key] = i } console.log(prevMap, 'sss') let lastIndex = 0 for (let n = 0; n < next.length; n++) { let { key = n + '' } = next[n] let j = prevMap[key] let nextChild = next[n] nextMap[key] = n if (j == null) { let  refNode = n === 0 ? prev[0].el: next[n - 1].el.nextSibling mount(nextChild, parent, refNode) } else { patch(prev[j], nextChild, Parent) debugger if (j < lastIndex) {let refNode = next[n-1].el.sibling; parent.insertBefore(nextChild.el, refNode) } else { lastIndex = j } } } for (let i = 0; i < prev.length; i++) { let { key = '' + i } = prev[i] if (! nextMap.hasOwnProperty(key)) parent.removeChild(prev[i].el) } }Copy the code

2. Diff algorithm for the longest ascending subsequence

Longest ascending subsequence algorithm: in a sequence, find the longest and ascending subsequence

For example: find the longest ascending subsequence of 0, 8, 4, 12, 2, 10, 6, 4, 1, 9, 5, 13

1. Search from left to right: 0 8 12 13

2. Look for every other number from left to right: 0, 4, 12, 13

Of course there are other solutions

If [a, b, f, m, c] is updated to [C, a, d, b], the fastest is to move D to the first, a, B, C do not move (longest ascending subsequence algorithm)

import { mount } from "./mount.js"import { patch } from "./patch.js" export const odiff = (prevChildren, nextChildren, Parent) = >{// front pointer let j = 0 // back pointer let prevEnd = prevchildren. length-1 let nextEnd = nextchildren. length-1 let prevNode = prevChildren[j] let nextNode = nextChildren[j] outer: { while (prevNode.key === nextNode.key) { patch(prevNode, nextNode, parent) j++ if (j > prevEnd || j > nextEnd) break outer prevNode = prevChildren[j] nextNode = nextChildren[j] } prevNode  = prevChildren[prevEnd] nextNode = nextChildren[nextEnd] while (prevNode.key === nextNode.key) { patch(prevNode, nextNode, parent) prevEnd--nextEnd-- if (j > prevEnd || j > nextEnd) break outer prevNode = prevChildren[prevEnd] nextNode = nextChildren[nextEnd] } } if (j > prevEnd && j <= nextEnd) { let nextPos = nextEnd + 1 let refNode = nextPos >= nextChildren.length ? null: nextChildren[nextPos].el while (j <= nextEnd) { mount(nextChildren[j++], parent, refNode) } return } else if (j > nextEnd) { while (j <= prevEnd) { parent.removeChild(prevChildren[j++].el) } return } let nextStart = j, prevStart = j, nextLeft = nextEnd - j + 1, nextIndexMap = {}, source = new Array(nextLeft).fill( - 1), patched = 0, lastIndex = 0, move = false for (let i = nextStart; i <= nextEnd; i++) { let key = nextChildren[i].key || i nextIndexMap[key] = i } for (let i = prevStart; i <= prevEnd; i++) { let prevChild = prevChildren[i], prevKey = prevChild.key || i, nextIndex = nextIndexMap[prevKey] if (patched >= nextLeft || nextIndex === undefined) { parent.removeChild(prevChild.el)  continue } patched++let nextChild = nextChildren[nextIndex] patch(prevChild, nextChild, parent) source[nextIndex - nextStart] = i if (nextIndex < lastIndex) { move = true } else { lastIndex = nextIndex } } if  (move) { const seq = lis(source); let j = seq.length - 1; for (let i = nextLeft - 1; i >= 0; i--) { let pos = nextStart + i, nextPos = pos + 1, nextChild = nextChildren[pos], refNode = nextPos >= nextLeft ? null: nextChildren[nextPos].el if (source[i] === -1) { mount(nextChild, parent, refNode) } else if (i ! == seq[j]) { parent.insertBefore(nextChild.el, refNode) } else { j-- } } } else { // no move for (let i = nextLeft - 1; i >= 0; i--) { if (source[i] === -1) { let pos = nextStart + i, nextPos = pos + 1, nextChild = nextChildren[pos], refNode = nextPos >= nextLeft ? null: nextChildren[nextPos].el mount(nextChild, parent, refNode) } } } } function lis(arr) { let len = arr.length, result = [], dp = new Array(len).fill(1); for (let i = 0; i < len; i++) { result.push([i]) } for (let i = len - 1; i >= 0; i--) { let cur = arr[i], nextIndex = undefined if (cur === -1) continue for (let j = i + 1; j < len; j++) { let next = arr[j] if (cur < next) { let max = dp[j] + 1 if (max > dp[i]) { nextIndex = j dp[i] = max } } } if (nextIndex ! == undefined) result[i] = [...result[i], ...result[nextIndex]] } let index = dp.reduce((prev, cur, i, arr) = >cur > arr[prev] ? i: prev, dp.length - 1) return result[index] }Copy the code