miniVue3的简单实现-虚拟dom对比

1.虚拟dom对比的时机

• 1.在渲染过程中会执行processElement 处理元素节点， 内部调用updateElement对前后dom节点进行比对（此情况是变动前虚拟dom和变动后虚拟dom节点都存在的情况）， updateElement 函数内部就是进行虚拟dom对比的全过程

• 2.先进行dom根节点处理，执行processElement函数处理dom 根节点对比有两种情况

  1. 变化前的虚拟dom节点n1和变化后的虚拟dom节点n2通过isSameVnode判断，结果不相等，那么就需要重新根据改变后的虚拟dom节点n2重新构建元素节点，和初始化渲染流程的元素挂载过程一致

    2. n1和n2相等，n2复用n1的dom节点，通过patchProps更新根节点的props属性， 
        然后调用patchChildren进行子元素对比

• 3.代码实现

  // 处理元素节点
  const processElement = (n1, n2, container, ancher) => {
    // 根据n1是否为null 判断是挂载元素节点，还是更新元素节点
    if (n1 == null) {
        mountElement(n2, container, ancher);
    } else {
        //变更前后虚拟dom都不为null
        updateElement(n1, n2, container);
    }
  }
  
  // 更新节点，首先从根节点开始
const updateElement = (n1, n2, container) => {
    // 1. n1，n2 是不是同一个节点
    // 通过hostRemove删除节点 并将n1节点重置为null，
    const el = n2.el = n1.el;
    if (n1 && !isSameVnode(n1, n2)) {
        // hostRemove就是获取到父节点调用removeChild删除当前节点
        hostRemove(el);
        n1 = null;
    }
    // 因为n1重置为null后，patch第一位参数传null就会走和第一次渲染挂载dom的流程一致
    if (n1 == null) {
        patch(null, n2, container)
    } else {
        // 元素一样， 先更新属性
        patchProps(n1, n2, el);
        // 然后对比子元素
        patchChildren(n1, n2, el);
    }
}

 // 对比元素属性
const patchProps = (n1, n2, el) => {
    // 新对象的属性
    const prevProps = n1.props || {};
    // 旧对象的属性
    const nextProps = n2.props || {};

    // prevProps和nextProps不相等， 进行属性更新
    if (prevProps !== nextProps) {
        // 如果在新属性中存在， 需要设置属性
        for (let key in nextProps) {
            if (prevProps[key] !== nextProps[key]) {
                // 更新新属性
                hostPatchProps(el, key, prevProps[key], nextProps[key]);
            }
        }
        // 旧属性在新属性中不存在删除掉
        for (let key in prevProps) {
            if (!(key in nextProps)) {
                // 删除旧属性
                hostPatchProps(el, key, prevProps[key], null);
            }
        }
    }
}

export function hostPatchProps (el, key, oldVal = null, newVal = null) {
    switch (key) {
        case "class":
            // 属性是class
            patchClass(el, newVal)
            break;
        case "style":
            // 属性是style
            patchStyle(el, oldVal, newVal);
            break;
        default:
            // 普通dom属性
            patchAttr(el, key, newVal);
            break;
    }
}

function patchClass (el, val) {
    if (val == null) {
        // 当为null时就是没有class
        val = "";
    }
    // 设置最新的class值
    el.className = val;
}

function patchStyle (el, oldVal, newVal) {
    // 以最新的style为元素设置属性
    for (let key in newVal) {
        el.style[key] = newVal[key];
    }
    // 属性在新的style里不存在，在老的style中存在，以最新的为主， 
    就需要删除老的原来存在于复用的元素上的style属性
    for (let key in oldVal) {
        if (!(key in newVal)) {
            el.style[key] = "";
        }
    }
}
function patchAttr (el, key, val) {
    if (!val) {
        // val不存在值时就是删除属性
        el.removeAttribute(key);
    } else {
        // val存在值就是设置当前属性， 不管原有属性是否存在，直接设置替换即可
        el.setAttribute(key, val);
    }
}

2. 执行patchChildren进行子元素dom对比的流程

1. 首先获取变更前后的虚拟dom节点n1和n2的子元素c1和c2，并获取n1和n2的shapFlag为prveShapFlag和nextShapFlag，用以判断子节点的类型

2.虚拟dom子节点的类型分为两种， 文本类型和数组类型

1. 如果新的虚拟dom子节点是文本类型那么子节点就是文本节点，不管旧的虚拟dom节点的子节点
是文本类型还是数组类型，dom元素都直接用textContent把子节点设置成文本节点

2. 如果新的虚拟dom的子节点是数组类型，需要区分两种情况
    1. 旧的虚拟dom的子节点类型也是数组类型，需要调用patchKeyChildren进行详细子节点对比差异，
    就好比vue2中的dom对比流程一样
    2.旧的虚拟dom节点类型为文本类型，只需要将元素中原有的文本节点删除，然后循环新的虚拟dom子
    节点，通过path将子节点进行挂载到dom上即可

3.代码实现

// 对比子元素
const patchChildren = (n1, n2, container) => {
    const c1 = n1.children;
    const c2 = n2.children;
    const prveShapFlag = n1.shapFlag;
    const nextShapFlag = n2.shapFlag;
    // 子元素的类型分为数组和字符串类型， 所以， 这有四种情况
    // 1.c2 为字符串， c1为字符串
    // 2.c2为字符串， c1 为数组
    // 3. c2 为数组， c1为字符串
    // 4. c2为数组， c1为数组

    if (nextShapFlag & shapFlags.TEXT_CHILD) {
        // 如果c2是字符串， 不管c1是字符串还是数组， 直接用 textContent设置新值即可
        // 所以不用区分情况， 只是需要判别c1和c2都为字符串时 相等就不用更改
        if (c1 !== c2) {
            hostSetElementText(container, c2);
        }
    } else if (nextShapFlag & shapFlags.ARRAY_CHILD) {

        if (prveShapFlag & shapFlags.ARRAY_CHILD) {
            // c2 是数组 c1是数组， 最复杂的dom对比
            patchKeyChildren(c1, c2, container)
        }
        if (prveShapFlag & shapFlags.TEXT_CHILD) {
            // c1 是字符串， 先将字符串删除， 再循环挂在新元素
            hostSetElementText(container, "");
            for (let i = 0; i < c2.length; i++) {
                // 将每个新子元素挂载
                patch(null, c2[i], container);
            }
        }
    }
}

3. patchKeyChildren进行新旧虚拟dom的子元素都为多个的复杂情况

1. 首先新虚拟dom子节点的长度为l2和新旧虚拟dom子节点的个数e1和e2

   const patchKeyChildren = (c1, c2, container) => {
        //记录从0位置开始已经对比过相同元素的个数
        let i = 0;
        // l2用来判断参照物ancher， 当nextIndex大于l2时ancher为null
        const l2 = c2.length;
        // 旧的子节点个数
        let e1 = c1.length - 1;
        // 新的子节点个数
        let e2 = l2 - 1;
   }

2. 首先从子节点c1和c2的位置0开始进行循环对比，循环条件为i小于c1和c2的子节点个数， 如果从头部开始对比，子节点相同就i++记录相同的节点个数并获取c1和c2的下一个子节点，再次进行对比，直到从头部对比开始出现子节点不相等时终止

const patchKeyChildren = (c1, c2, container) => {
    //.....前代码省略
    /* 
      1.从前往后进行对比 , 循环条件 i始终比e1和e2小
      可能情况 
      prev [a, b, c] next [a, b, c, d] 相当于向后添加元素
      只要前面的元素相同就将i后移
      i e1 e2的结果
      1.1 i = 3; e1=2; e2 = 3
    */
    while (i <= e1 && i <= e2) {
        // 同一个节点， 将i指针向后移动， 当节点不同时跳出循环
        const n1 = c1[i];
        const n2 = c2[i];
        if (isSameVnode(n1, n2)) {
            // 节点相同但属性不一定相同， 需要更新,并且进行递归
            patch(n1, n2, container);
        } else {
            break;
        }
        i++;
    }
}

3. 头部不相同后，从尾部开始对比，尾部对比如果相同e1--、e2--。前后虚拟dom不同或i大于e1或e2后结束尾部对比

    const patchKeyChildren = (c1, c2, container) => {
        //.....前代码省略
        while (i <= e1 && i <= e2) {
            // 同一个节点， 将e1, e2指针向前移动， 当节点不同时跳出循环
            const n1 = c1[e1];
            const n2 = c2[e2];
            if (isSameVnode(n1, n2)) {
                // 节点相同但属性不一定相同， 需要更新,并且进行递归
                patch(n1, n2, container);
            } else {
                break;
            }
            e1--;
            e2--
        }
    }

4. 当2、3两个步骤前后对比都结束后，可能出现下面情况
   1. i>e1 说明e1的虚拟dom节点已经全部遍历完成，如果在i>e1的条件下 i>e2, 说明e2的虚拟dom节点也全部遍历完成，e1和e2都经过2、3步骤遍历完成说明变更前后的虚拟dom节点完全相同无变更， 所以不需要进行处理

        2. i>e1条件下， i<=e2说明, e1遍历完成，e2还剩余元素，说明变化后新的虚拟dom新增了元素，
    新增的元素需要新建dom插入到现在的位置
    

        3. i>e2， 新的虚拟dom节点遍历完成，i<=e1,说明 老的虚拟dom节点未遍历完成，有剩余元素， 
        是不需要的节点，需要删除
        

        4. i<e1&&i<e2 说明新老虚拟dom都未遍历完成， 都有剩余元素，就需要对剩余的元素每一项
        进行对比差异，此情况为最复杂的dom对比
        

代码实现

 const patchKeyChildren = (c1, c2, container) => {
        //.....前代码省略
        if (i > e1) {
            // 老的虚拟dom遍历完成，新的虚拟dom有剩余元素，说明有新增, 
            循环剩余元素数量，直接挂载新元素即可
            while (i <= e2) {
                // 获取当前需要插入元素的下一个元素dom，用insertBefore插入，
                // 超出e2元素长度ancher改为null insertBefore效果相当于appendchild
                let nextPos = e2 + 1;
                const ancher = nextPos < l2 ? c2[nextPos].el : null;
                patch(null, c2[i], container, ancher);
                i++;
            }
        } else if (i > e2) {
            // 新的虚拟dom遍历完成，老的虚拟dom有剩余元素，剩余的元素都不需要，需要删除旧节点
            while (i <= e1) {
                // hostRemove就是调用removeChild进行节点删除
                hostRemove(c1[i].el);
                i++;
            }
        } else {
            // 此处为情况4最复杂的dom对比
        }
    }

4. 新老虚拟dom元素都未完全遍历完成，有剩余元素的对比情况

此对比情况 1.首先要建立新虚拟dom的key和index的映射表
          2.循环遍历老的虚拟dom节点，更新和删除节点，并找出需要移动的节点
          3.最后新增新的dom节点并用最小递增子序列处理需要移动元素到正确位置

此对比情况 整体代码

 const patchKeyChildren = (c1, c2, container) => {
        //.....前代码省略
        if (i > e1) {

        } else if (i > e2) {

        } else {
            // 此处为情况4最复杂的dom对比
            // 中间元素不明情况
            let s1 = i;
            let s2 = i;
            // 建立新节点key和index的映射表， 用于查找元素
            const keytoNewIndexMap = new Map();
            for (i = s2; i <= e2; i++) {
                const key = c2[i].key;
                keytoNewIndexMap.set(key, i);
            }
            let j;
            // 已经被比较的dom个数
            let patched = 0;
            // 将要被比对的元素个数
            let toBePatched = e2 - s2 + 1;
            let moved = false;  // 用来判断是否有移动操作
            let maxNewIndexSoFar = 0; // 
            const newIndexToOldIndex = new Array(toBePatched).fill(0);
            // 循环旧的虚拟dom查找当前的旧节点的key值的对应新节点index
            // 如果旧节点不存在key值，就通过newIndexToOldIndex对ing的oldIndex
            // 是否为0判断, 如果为0 说明还未找到, 再通过判断tag是否相等,找一个标签相等的
            // 判定为同一项
            let newIndex;
            // 处理老的虚拟dom，更新和删除元素操作，并找出需要移动的元素
            for (i = s1; i <= e1; i++) {
                const prevChild = c1[i];
                // 这里需要处理旧元素剩的多余节点，patched大于等于toBePatched元素时， 
                说明旧子节点已经有剩余不需要的了
                //不需要就卸载掉
                if (patched >= toBePatched) {
                    hostRemove(prevChild.el);
                }
                if (prevChild.key != null) {
                    // 旧的节点有key值， 直接去建立的映射表里找元素现在新的序列位置
                    newIndex = keytoNewIndexMap.get(prevChild.key);
                } else {
                    // 如果旧节点没有key值，看newIndexToOldIndex对应位置的值是否为0，为0
                    // 就是未找到对象元素， 然后再判断tag是否相等
                    for (j = s2; j < toBePatched; j++) {
                        if (newIndexToOldIndex[j] == 0 && 
                        isSameVnode(prevChild, c2[j + s2])) {
                            newIndex = j;
                            break;
                        }
                    }
                }
                if (newIndex == undefined) {
                    // 在新元素中找不到对应的index，说明元素已经不存在了， 要卸载
                    hostRemove(prevChild.el)
                } else {
                    // 0是一个特殊标识，所以需要i+1
                    newIndexToOldIndex[newIndex - s2] = i + 1;

                    // 找到就把当前序列存起来
                    if (maxNewIndexSoFar >= newIndex) {
                        // 如果当maxNewIndexSoFar大于newIndex就说明有元素移位了
                        // 因为maxNewIndexSoFar一直是存储找到旧节点在新节点中的newIndex，
                        // 旧节点一直是递增的， 如果未移动位置， 新节点也应该是递增的
                        moved = true;
                    } else {
                        maxNewIndexSoFar = newIndex;
                    }

                    // newIndex有值说明当前元素需要更新操作，如果需要移动位置，最后再做处理
                    patch(prevChild, c2[newIndex], container);
                    // 记录对比过的元素
                    patched++
                }
            }
            // 下面就要用最长递增子序列来判断最少的元素位移
            const increasingNewIndexSequence =
            moved ? getSequence(newIndexToOldIndex) : [];
            j = increasingNewIndexSequence.length;
            // 倒叙循环要对比的元素
            // 获取到最后一个对比元素之后那个元素序列作为dom操作的参照物

            for (i = toBePatched - 1; i >= 0; i--) {
                // 等于0是新增元素，只要找到参照物插入即可
                const nextIndex = s2 + i;
                const nextChild = c2[nextIndex];
                const ancher = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;
                if (newIndexToOldIndex[i] == 0) {
                    patch(null, c2[s2 + i], container, ancher)
                } else if (moved) {
                    // 如果不是新增， 不用移动， 直接结束了
                    if (j < 0 || i !== increasingNewIndexSequence[j]) {
                        //j为最长递增子序列的数组长度， 当j<0时，当前i肯定需要移动 
                        有需要的移动元素， i不在最长递增子序列中需要移动
                        hostInsert(nextChild.el, container, ancher)
                    } else {
                        // 其他情况不需要移动节点， 只需将j--即可j--指向最长递增子序列前一项
                        j--;
                    }
                }
            }
        }
    }

分步代码及步骤拆解

1. 首先记录新老虚拟dom开始位置i，分别为s1，s2， 然后创一个map映射表，记录每个新虚拟dom节点key和index的关系

2.用patched记录已经被比较的元素，toBePatched记录将要被比较的元素，moved记录当前需要对比的元素中是否有元素被移动位置了，maxNewIndexSoFar记录当前已经对比过的最大index，maxNewIndexSoFar会用于判断元素是否被移动过，newIndexToOldIndex用于记录新老虚拟dom节点的index对用关系

    let s1 = i;
    let s2 = i;
    // 建立新节点key和index的映射表， 用于查找元素
    const keytoNewIndexMap = new Map();
    for (i = s2; i <= e2; i++) {
        const key = c2[i].key;
        keytoNewIndexMap.set(key, i);
    }
    let j;
    // 已经被比较的dom个数
    let patched = 0;
    // 将要被比对的元素个数
    let toBePatched = e2 - s2 + 1;
    let moved = false;  // 用来判断是否有移动操作
    let maxNewIndexSoFar = 0; // 
    const newIndexToOldIndex = new Array(toBePatched).fill(0);

3.循环老的虚拟dom的剩余元素，找到需要删除和更新的元素

1.循环dom， 处理边界， 如果比较过的数量patched大于等于需要被比较的数量toBePatched，
老的虚拟dom剩下的元素已经都不需要，直接删除掉

    for (i = s1; i <= e1; i++) {
        const prevChild = c1[i];
        // 这里需要处理旧元素剩的多余节点，patched大于等于toBePatched元素时， 
        // 说明旧子节点已经有剩余不需要的了,不需要就卸载掉
        if (patched >= toBePatched) {
            // 直接删除元素
            hostRemove(prevChild.el);
        }
        //........
    }

    2.找出老的dom节点对应在新的虚拟dom节点中的位置index（老的节点在新的虚拟dom中找到后，
    说明是同一个元素，可以复用，但最终要以新虚拟dom的index作为元素所处的最终位置）
    
    分为存在key值和无key值得情况： 
    
    存在key直接通过创建的keytoNewIndexMap获取老节点对应的新节点index即可
    （此index为节点最终的位置）。
    
    不存在key值，如果newIndexToOldIndex中当前位置j的值为0，并且用isSameVnode判断标签名相等，
    就直接判定当前新虚拟dom的元素c2[j + s2]和老的虚拟节点prevChild 是前后相同的元素，
    记录prevChild的index，复用当前结点

    if (prevChild.key != null) {
        // 旧的节点有key值， 直接去建立的映射表里找元素现在新的序列位置
        newIndex = keytoNewIndexMap.get(prevChild.key);
    } else {
        // 如果旧节点没有key值，看newIndexToOldIndex对应位置的值是否为0，为0
        // 就是未找到对象元素， 然后再判断tag是否相等
        for (j = s2; j < toBePatched; j++) {
            if (newIndexToOldIndex[j] == 0 && isSameVnode(prevChild, c2[j + s2])) {
                newIndex = j;
                break;
            }
        }
    }

4. 根据上一步记录的查找的newIndex来进行判断， 如果newIndex不存在，说明老的虚拟dom在新的虚拟dom中不存在，直接将老节点prevChild的元素删除掉即可。如果newIndex存在，说明老的虚拟dom节点可以被复用，直接通过patch方法更新元素的属性即可，这里不处理元素的位置移动，下一步最长递增子序列过程处理

    if (newIndex == undefined) {
        // 在新元素中找不到对应的index，说明元素已经不存在了， 要卸载
        hostRemove(prevChild.el)
    } else {
        // newIndexToOldIndex 记录新节点和老节点对应的位置，为
        //最长递增子序列做判断的依据，0是一个特殊标识，所以需要i+1
        newIndexToOldIndex[newIndex - s2] = i + 1;

        // 找到就把当前序列存起来
        if (maxNewIndexSoFar >= newIndex) {
            // 如果当maxNewIndexSoFar大于newIndex就说明有元素移位了
            // 因为maxNewIndexSoFar一直是存储找到旧节点在新节点中的newIndex，
            // 旧节点一直是递增的， 如果未移动位置， 新节点也应该是递增的
            moved = true;
        } else {
            //记录最后一次的index
            maxNewIndexSoFar = newIndex;
        }

        // newIndex有值说明当前元素需要更新操作，如果需要移动位置，最后再做处理
        patch(prevChild, c2[newIndex], container);
        // 记录对比过的元素数量
        patched++
    }

5. 新增和移动元素的过程，会是一个倒叙对比的过程，因为需要获取到对比元素的下一个dom节点作为插入文档中的参照物

   1. 首先根据moved来判断是否需要移动元素，如果需要移动元素就执行getSequence（getSequence直接搬运的源码）获取最长递增子序列，然后倒叙遍历新虚拟dom需要被对比的节点
   2. 获取未对比节点的最后一个节点的序列nextIndex，并获取最后一个虚拟节点nextChild，获取插入节点的标志参照ancher（未超出c2的长度下一个元素节点就是c2[nextIndex + 1].el，超出c2长度，ancher=null）
   3. 如果newIndexToOldIndex[i] == 0说明当前新的虚拟dom节点是一个新增的元素，直接用patch创建元素挂载即可
   4. 如果newIndexToOldIndex[i] ！== 0并且moved=true 说明 当前节点是复用的元素，而且需要移动位置

  // 下面就要用最长递增子序列来判断最少的元素位移
    const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndex) : [];
    j = increasingNewIndexSequence.length;
    // 倒叙循环要对比的元素
    // 获取到最后一个对比元素之后那个元素序列作为dom操作的参照物

    for (i = toBePatched - 1; i >= 0; i--) {
        // 等于0是新增元素，只要找到参照物插入即可
        const nextIndex = s2 + i;
        const nextChild = c2[nextIndex];
        const ancher = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;
        if (newIndexToOldIndex[i] == 0) {
            patch(null, c2[s2 + i], container, ancher)
        } else if (moved) {
            // 如果不是新增， 不用移动， 直接结束了
            // i和increasingNewIndexSequence[j]中位置不相等就需要移动
            if (j < 0 || i !== increasingNewIndexSequence[j]) {
                //j为最长递增子序列的数组长度， 当j<0时，当前i肯定需要移动 有需要的移动元素，
                i不在最长递增子序列中需要移动
                hostInsert(nextChild.el, container, ancher)
            } else {
                // 其他情况不需要移动节点， 只需将j--即可j--指向最长递增子序列前一项
                j--;
            }
        }
    }

git地址

链接：github.com/liyanjunCod…

miniVue3为vue3的简单实现代码