function listDiff(oldList, newList, index, patches) {// 為了遍歷方便，先取出兩個 list 的所有 keyslet oldKeys = getKeys(oldList)let newKeys = getKeys(newList)let changes = []// 用于保存變更后的節點數據// 使用該數組保存有以下好處// 1.可以正確獲得被刪除節點索引// 2.交換節點位置只需要操作一遍 DOM// 3.用于 `diffChildren` 函數中的判斷，只需要遍歷// 兩個樹中都存在的節點，而對于新增或者刪除的節點來說，完全沒必要// 再去判斷一遍let list = []oldList &&oldList.forEach(item => {let key = item.keyif (isString(item)) {key = item}// 尋找新的 children 中是否含有當前節點// 沒有的話需要刪除let index = newKeys.indexOf(key)if (index === -1) {list.push(null)} else list.push(key)})// 遍歷變更后的數組let length = list.length// 因為刪除數組元素是會更改索引的// 所有從后往前刪可以保證索引不變for (let i = length - 1; i >= 0; i--) {// 判斷當前元素是否為空，為空表示需要刪除if (!list[i]) {list.splice(i, 1)changes.push({type: StateEnums.Remove,index: i})}}// 遍歷新的 list，判斷是否有節點新增或移動// 同時也對 `list` 做節點新增和移動節點的操作newList &&newList.forEach((item, i) => {let key = item.keyif (isString(item)) {key = item}// 尋找舊的 children 中是否含有當前節點let index = list.indexOf(key)// 沒找到代表新節點，需要插入if (index === -1  || key == null) {changes.push({type: StateEnums.Insert,node: item,index: i})list.splice(i, 0, key)} else {// 找到了，需要判斷是否需要移動if (index !== i) {changes.push({type: StateEnums.Move,from: index,to: i})move(list, index, i)}}})return { changes, list }
}function getKeys(list) {let keys = []let textlist &&list.forEach(item => {let keyif (isString(item)) {key = [item]} else if (item instanceof Element) {key = item.key}keys.push(key)})return keys
}

遍歷子元素打標識

對于這個函數來說，主要功能就兩個

1. 判斷兩個列表差異
2. 給節點打上標記

總體來說，該函數實現的功能很簡單

function diffChildren(oldChild, newChild, index, patches) {let { changes, list } = listDiff(oldChild, newChild, index, patches)if (changes.length) {if (patches[index]) {patches[index] = patches[index].concat(changes)} else {patches[index] = changes}}// 記錄上一個遍歷過的節點let last = nulloldChild &&oldChild.forEach((item, i) => {let child = item && item.childrenif (child) {index =last && last.children ? index + last.children.length + 1 : index + 1let keyIndex = list.indexOf(item.key)let node = newChild[keyIndex]// 只遍歷新舊中都存在的節點，其他新增或者刪除的沒必要遍歷if (node) {dfs(item, node, index, patches)}} else index += 1last = item})
}

let index = 0
export default function patch(node, patchs) {let changes = patchs[index]let childNodes = node && node.childNodes// 這里的深度遍歷和 diff 中是一樣的if (!childNodes) index += 1if (changes && changes.length && patchs[index]) {changeDom(node, changes)}let last = nullif (childNodes && childNodes.length) {childNodes.forEach((item, i) => {index =last && last.children ? index + last.children.length + 1 : index + 1patch(item, patchs)last = item})}
}function changeDom(node, changes, noChild) {changes &&changes.forEach(change => {let { type } = changeswitch (type) {case StateEnums.ChangeProps:let { props } = changeprops.forEach(item => {if (item.value) {node.setAttribute(item.prop, item.value)} else {node.removeAttribute(item.prop)}})breakcase StateEnums.Remove:node.childNodes[change.index].remove()breakcase StateEnums.Insert:let domif (isString(change.node)) {dom = document.createTextNode(change.node)} else if (change.node instanceof Element) {dom = change.node.create()}node.insertBefore(dom, node.childNodes[change.index])breakcase StateEnums.Replace:node.parentNode.replaceChild(change.node.create(), node)breakcase StateEnums.Move:let fromNode = node.childNodes[change.from]let toNode = node.childNodes[change.to]let cloneFromNode = fromNode.cloneNode(true)let cloenToNode = toNode.cloneNode(true)node.replaceChild(cloneFromNode, toNode)node.replaceChild(cloenToNode, fromNode)breakdefault:break}})
}

let test4 = new Element('div', { class: 'my-div' }, ['test4'])
let test5 = new Element('ul', { class: 'my-div' }, ['test5'])let test1 = new Element('div', { class: 'my-div' }, [test4])let test2 = new Element('div', { id: '11' }, [test5, test4])let root = test1.render()let pathchs = diff(test1, test2)
console.log(pathchs)setTimeout(() => {console.log('開始更新')patch(root, pathchs)console.log('結束更新')
}, 1000)