Vue2的diff算法

export function diff(oldCh, newCh) {
    let oldStartIndex = 0;
    let newStartIndex = 0;
    let oldEndIndex = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIndex];
    let newEndIndex = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIndex];

    let oldKeyToIndex;
    let i = 1;
    // https://github.com/vuejs/vue/tree/main/src/core/vdom/patch.ts
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // console.log('循环', newStartIndex, oldStartIndex, newEndIndex, oldEndIndex)
        // console.log('循环体', JSON.parse(JSON.stringify(newCh)), JSON.parse(JSON.stringify(oldCh)))
        // 这一段就是说，从start开始每当一个新节点C复用了旧节点并移动旧节点到C的位置，
        // C旧节点
        if (oldStartVnode === undefined) {
            console.log('第一种')
            oldStartVnode = oldCh[++oldStartIndex] // Vnode has been moved left
        } else if (oldEndVnode === undefined) {
            console.log('第二种')
            oldEndVnode = oldCh[--oldEndIndex]
        }

        else if (sameVNode(oldStartVnode, newStartVnode)) {
            console.log('第三种')
            patchVNode(oldStartVnode, newStartVnode)
            oldStartVnode = oldCh[++oldStartIndex];
            newStartVnode = newCh[++newStartIndex];
        } else if (sameVNode(oldEndVnode, newEndVnode)) {
            console.log('第四种')
            patchVNode(oldEndVnode, newEndVnode)
            oldEndVnode = oldCh[--oldEndIndex];
            newEndVnode = newCh[--newEndIndex];
        } else if (sameVNode(oldStartVnode, newEndVnode)) {
            console.log('第五种')
            patchVNode(oldStartVnode, newEndVnode);
            insertBefore(oldStartVnode, nextSibling(oldEndVnode)) // 移动节点，JS的dom操作方法insertBefore也会是移动的
            oldStartVnode = oldCh[++oldStartIndex];
            newEndVnode = newCh[--newEndIndex];
        } else if (sameVNode(oldEndVnode, newStartVnode)) {
            console.log('第六种')
            patchVNode(oldEndVnode, newStartVnode);
            insertBefore(oldEndVnode, oldStartVnode);
            oldEndVnode = oldCh[--oldEndIndex]
            newStartVnode = newCh[++newStartIndex];
        } else {
            console.log('第七种')
            // 只遍历剩余新节点，oldStartIndex 和 oldEndIndex 保持不变
            // 看当前新节点 是否 和旧节点其中一个一样
            if (oldKeyToIndex === undefined) {
                oldKeyToIndex = createKeyToOldIdx(oldCh, oldStartIndex, oldEndIndex);
            }

            let indexInOld;
            if (newStartVnode.key) {
                indexInOld = oldKeyToIndex.get(newStartVnode.key);
            } else {
                indexInOld = findIndexInOld(newStartVnode);

            }

            if (indexInOld === undefined) {
                // 创建新节点并插入到oldStartVnode前面，
                createElm(newStartVnode, oldStartVnode);
            } else {
                let vnodeToMove = oldCh[indexInOld];

                if (sameVNode(vnodeToMove, newStartVnode)) {
                    patchVNode(vnodeToMove, newStartVnode);
                    oldCh[indexInOld] = undefined;
                    insertBefore(vnodeToMove, oldStartVnode);
                } else {
                    createElm(newStartVnode, oldStartVnode)
                }
            }

            newStartVnode = newCh[++newStartIndex]
        }
    }

    if (oldStartIndex > oldEndIndex) {
        const anchor = newCh[newEndIndex + 1] === undefined ? null : newCh[newEndIndex].el

        addVnodes(anchor, newCh, newStartIndex, newEndIndex)
    } else if (newStartIndex > newEndIndex){
        removeVnodes(oldCh, oldStartIndex, oldEndIndex);
    }
}


function createKeyToOldIdx(oldCh, oldStartIndex, oldEndIndex) {
    const oldKeyToIndex = new Map();
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
        oldKeyToIndex.set(oldCh[i].key, i);
    }
    return oldKeyToIndex;
}

function findIndexInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
        if (oldCh[i].key === newStartVnode.key) {
            return i;
        }
    }
}


function sameVNode(oldNode, newNode) {
    // 判断VNode是否相等，如果节点类型、组件标识、key相同，就认为是相同的
    // 这里我简化了只比较key，
    // 如果认为是相同就调用patch进一步比较和更新，比如比较属性、事件监听器、子节点比较、组件的状态和props触发组件更新
    if (oldNode.key === newNode.key)
        return true
    else {
        return false
    }
}


function patchVNode(oldNode, newNode, anchor) {
    // 进一步比较和更新，比如比较属性、事件监听器、子节点比较、组件的状态和props触发组件更新
    // 还有更新或替换 dom

    if (oldNode === null) {
        insertBefore(newNode, anchor)
        return;
    }
    if (oldNode.key === newNode.key) {
        replaceChild(newNode, oldNode)
    }
}

function createElm(newStartVnode, anchor) {
    // 实际上是createElement，再insertBefore 或者 appendChild
    // insertBefore 实际插入也只需要一个节点本身，而不是一个索引
    insertBefore(newStartVnode, anchor)
}


function addVnodes(anchor, newCh, startIndex, endIndex) {
    for (let i = endIndex; i >= startIndex; i--) {
        insertBefore(newCh[i], i = endIndex ? anchor : newCh[i+1])
    }
}

function removeVnodes(oldCh, startIndex, endIndex) {
    for (let i = endIndex; i >= startIndex; i--) {
        removeChild(oldCh[i]);
    }
}

// insertBefore(node, child) 将一个节点插入到指定父节点的子列表中的参考节点之前
// 我是为了模拟JS原生方法
// 如果node已经挂载在页面上，insertBefore(node, child)的行为是移动 node 到新的位置，而不是复制它。
function insertBefore(node, anchor) {
    if (anchor === 'tail') {
        appendChild(node)
    } else {
        const oldIndex = globalHtml.findLastIndex(b => b.key === node.key);
        if (oldIndex > -1) {
            globalHtml.splice(oldIndex, 1);
        }
        const index = globalHtml.findLastIndex(b => b.key === anchor.key);
        globalHtml.splice(index, 0, node);
    }
}


// appendChild 将一个节点添加到指定父节点的子列表末尾
function appendChild (node) {
    globalHtml.push(node);
}

// replaceChild 替换父节点的子节点
function replaceChild(newNode, oldNode) {
    const index = globalHtml.findIndex(b => b.key === oldNode.key);
    globalHtml[index].el = newNode.el;
    globalHtml[index].status = '被更新了属性';
}

function nextSibling(node) {
    // 也是为了模拟，实际只需要element.nextElementSibling就能取到element的同级next节点
    const find = globalHtml.findIndex(b => b.key === node.key);
    return globalHtml[find + 1];
}

function removeChild(node) {
    // 这里为了模拟所以需要findIndex，真实dom节点的删除，只需要removeChild(childNode)
    // 不需要index，只需要节点本身
    const index = globalHtml.findIndex(b => b.key === node.key);
    globalHtml.splice(index, 1);
}


export function init(page) {
    globalHtml = page;
}


let oldCh = [
    {key: 1, el: 'a', type: 'old'},
    {key: 2, el: 'b', type: 'old'},
    {key: 3, el: 'c', type: 'old'},
    {key: 4, el: 'd', type: 'old'},
    {key: 5, el: 'e', type: 'old'},
    {key: 6, el: 'f', type: 'old'},
]
let newCh = [
    {key: 3, el: 'c', type: 'new'},
    {key: 4, el: 'd', type: 'new'},
    {key: 2, el: 'b', type: 'new'},
    {key: 1, el: 'a', type: 'new'},
    {key: 6, el: 'f', type: 'new'},
    {key: 7, el: 'g', type: 'new'},
]

let globalHtml = [...oldCh]

init(globalHtml)
diff(oldCh, newCh);
console.log(globalHtml);