手写一个diff算法（完整版）

vNode方法

创建vNode.js文件，返回一个包装成虚拟节点的方法

export default function vnode(sel, data, children, text, elm) {
    const key = data && data.key;
    return { sel, data, children, text, elm, key };
}

h方法

实现一个低配版本的h函数，调用的形态为以下的三种之一：
1.h('div', {}, 'text')
2.h('div', {}, [])
3.h('div', {}, h())

import vnode from "./vNode";
export default function h(sel, data, c) {
    // 检查入参熟练
    if (arguments.length !== 3) {
        throw new Error('请传入三个参数')
    }
    // 检查c参数类型 是text，h('div', {}, 'text')
    if (typeof c == 'string' || typeof c == 'number' ) {
        return vnode(sel,data,undefined,c,undefined)
    // 检查c参数类型 是h数组，h('div', {}, [])
    }else if(Array.isArray(c)) {
        let children = []
        for (let i = 0; i < c.length; i++) {
            if (!(typeof c[i] == 'object' )) {
                throw new Error('传入的数组函数不是一个h对象')
            }
            children.push(c[i])
        }
        return vnode(sel,data,children,undefined,undefined) 
    // 检查c参数类型 是h对象，h('div', {}, h())
    }else if(typeof c == 'object' && c.hasOwnProperty('sel')) {
        let children = c
        return vnode(sel,data,children,undefined,undefined)
    }else{
        throw new Error('传入的第三个参数类型错误')
    }
}

createElement方法

真正的创建节点，把传入的虚拟节点vnode创建为真实dom

export default function createElement(vnode) {
    let domNode = document.createElement(vnode.sel)
    // 虚拟节点有text属性 没有子元素
    if (vnode.text!=='' && vnode.children === undefined) {
        domNode.innerText = vnode.text
    }
     // 虚拟节点有children属性 有子元素 需要递归
    else if (Array.isArray(vnode.children) && vnode.children.length >0 ){
        const list = vnode.children
        // 它内部有子节点，需要递归append上树
        for (let i = 0; i < list.length; i++) {
            // 创建出字节点dom 递归调用createElement
            let chDom = createElement(list[i])
            // 上树
            domNode.appendChild(chDom)
        }
    }
    vnode.elm = domNode
    // eml是纯dom对象，return出去
    return vnode.elm
}

patch方法

核心，实现虚拟节点的真实上树

import vnode from "./vNode";
import createElement from "./createElement";
import patchVnode from "./patchVnode";

// 书写上树节点
export default function patch(oldVnode, newVnode){
    // 判断传入的第一个参数，是否是虚拟节点
    if ((oldVnode&&oldVnode.sel == '') || (oldVnode&&oldVnode.sel == undefined) ) {
        //是真实节点 包装成虚拟节点后返回
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], oldVnode.elm, oldVnode)
    }
    // 判断新旧阶段是否为同一个节点
    if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
        patchVnode(oldVnode, newVnode)

    }else{
        // 进行暴力删除旧节点，插入新节点
        let newElm = createElement(newVnode)
        if (oldVnode.elm.parentNode && newElm) {
            oldVnode.elm.parentNode.insertBefore(newElm, oldVnode.elm)
        } 
        oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
}

patchVnode方法

patch函数调用过程中，当判断新旧阶段是否为同一个节点时，即key和选择器一致时，可以判断是同一个节点，进行精细化比较

import updateChildren from "./updateChildren"
export default function(oldVnode, newVnode){
        // key和选择器一致时，可以判断是同一个节点，进行精细化比较
        // 1,判断新旧节点是否完全相同 什么都不用做
        if (oldVnode === newVnode) return

        // 2,判断新节点有没有text属性
        if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length===0)) {
            // console.log('有text属性', oldVnode, newVnode)
            // text不相同 直接修改text
            if (newVnode.text !== oldVnode.text) {
                // oldElm.innerText = newVnode.text
                oldVnode.elm.innerText = newVnode.text
            }
        // 3,判断新节点有没有children属性
        }else{ 
            //先判断旧节点有没有children
            if (oldVnode.children !== undefined && oldVnode.children.length>0) {
                // diff算法实现 最复杂的算法部分
                updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
            }else{
                // console.log('旧节点没有text属性 没有children',oldVnode, newVnode)
                //没有，清空老的节点文字，追加children数组
                oldVnode.elm.innerText = ''
                for (let i = 0; i < newVnode.children.length; i++) {
                    let dom = createElement(newVnode.children[i])
                    oldVnode.elm.appendChild(dom)
                }
            }
        }
}

updateChildren

diff算法的核心，也是最复杂的算法部分，当新旧节点都有children时，如何实现最小量的更新策略。即旧节点没有text属性, 有children，这时会进入diff算法实现。

import patchVnode from "./patchVnode"
import createElement from "./createElement"

// 检查是否是同一节点
function checkSameVnode(a, b) {
    return a.sel === b.sel && a.key === b.key
}

export default function (parentElm, oldCn, newCn) {

    // 定义指针 新前、新后，旧前、旧后
    let newStartIdx = 0
    let newEndIdx = newCn.length - 1
    let oldStartIdx = 0
    let oldEndIdx = oldCn.length - 1

    // 定义新旧节点
    let newStartVnode = newCn[0]
    let newEndVnode = newCn[newEndIdx]
    let oldStartVnode = oldCn[0]
    let oldEndVnode = oldCn[oldEndIdx]

    // 寻找keymap
    let keyMap = null

    // 开始循环语句 四种命中查找：
    //     新前与旧前
    //     新后与旧后
    //     新后与旧前
    //     新前与旧后
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 先略过加了undefined标记的那项
        if (oldStartVnode == null || oldCn[oldStartIdx] == undefined) {
            oldStartVnode = oldCn[++oldStartIdx]
        } else if (oldEndVnode == null || oldCn[oldEndIdx] == undefined) {
            oldEndVnode = oldCn[--oldEndIdx]
        } else if (newStartVnode == null || newCn[newStartIdx] == undefined) {
            newStartVnode = newCn[++newStartIdx]
        } else if (newEndVnode == null || newCn[newEndIdx] == undefined) {
            newEndVnode = newCn[--newEndIdx]
        }
        // 判断 新旧 前面的节点是否相同
        else if (checkSameVnode(newStartVnode, oldStartVnode)) {
            console.log('1) 新前与旧前');
            patchVnode(oldStartVnode, newStartVnode)
            oldStartVnode = oldCn[++oldStartIdx]
            newStartVnode = newCn[++newStartIdx]

        } else if (checkSameVnode(newEndVnode, oldEndVnode)) {
            console.log('2) 新后与旧后');
            patchVnode(oldEndVnode, newEndVnode)
            oldEndVnode = oldCn[--oldEndIdx]
            newEndVnode = newCn[--newEndIdx]

        } else if (checkSameVnode(newEndVnode, oldStartVnode)) {
            console.log('3) 新后与旧前');
            // 先移动 后++
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
            patchVnode(oldStartVnode, newEndVnode)
            oldStartVnode = oldCn[++oldStartIdx]
            newEndVnode = newCn[--newEndIdx]

        } else if (checkSameVnode(newStartVnode, oldEndVnode)) {
            console.log('4) 新前与旧后');
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
            patchVnode(oldEndVnode, newStartVnode)
            oldEndVnode = oldCn[--oldEndIdx]
            newStartVnode = newCn[++newStartIdx]

        } else {
            console.log('四种查找都都没有命中的时候');
            // 寻找 key 的 map
            // 这个map很好理解呀,把old节点的存入对象中,然后看看new中节点的key是否可以在对象中找到
            if (!keyMap) {
                keyMap = {}
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    const key = oldCn[i].key
                    if (key !== undefined) {
                        keyMap[key] = i
                    }
                }
            }

            const idxInOld = keyMap[newStartVnode.key]
            if (idxInOld == undefined) {
                // 是undefined，表示是全新的项，目前是虚拟节点不是真正的dom节点
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
            } else {
                // 不是undefined，不是全新的项，需要移动, 而不是删除后的新增
                const elmToMove = oldCn[idxInOld]
                patchVnode(elmToMove, newStartVnode)
                oldCn[idxInOld] = undefined
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
            }

            // 指针下移，只移动新的头
            newStartVnode = newCn[++newStartIdx]
        }
    }

    // 查找循环结束后，有没有剩余的节点
    if (newStartIdx <= newEndIdx) {
        console.log('新的节点上 有剩余的节点，需要新增')
        const before = newCn[newEndIdx + 1] == null ? null : newCn[newEndIdx + 1].elm
        for (let i = newStartIdx; i <= newEndIdx; i++) {
            parentElm.insertBefore(createElement(newCn[i]), before)
        }
    } else if (oldStartIdx <= oldEndIdx) {
        console.log('旧的节点上 有剩余的节点，需要批量移除')
        // 批量删除oldStartIdx 与 oldEndIdx之间剩余的项
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCn[i]) {
                parentElm.removeChild(oldCn[i].elm)
            }
        }
    }
}

一些测试用例

// 先引入h函数与patch方法
import h from "./my-snabbdom/h";
import patch from "./my-snabbdom/patch";
// 获取真实dom节点，创建虚拟新旧节点
const container = window.document.getElementById('box')
const myNode_old = h('h2', {}, [
  h('span', {}, 'span11111  '),
  h('span', {}, 'span22222'),
])
const myNode_new = h('h2', {}, 'rita开始学源码')
// 上树
patch(container, myNode_old)
patch(myNode_old, myNode_new )