что это?
Я полагаю, что все знакомы с концепцией виртуального DOM (Virtual DOM).От React до Vue виртуальный DOM обеспечивает кросс-платформенные возможности (React-Native и Weex) для обеих платформ. Поскольку многие люди знакомятся с виртуальным DOM в процессе изучения React, они предубеждены и думают, что виртуальный DOM и JSX неразделимы. На самом деле, виртуальный DOM и JSX совместимы, но JSX является лишь достаточным и ненужным условием для виртуального DOM.Vue может хорошо воспроизводить виртуальный DOM, даже если он использует шаблоны.В то же время многие люди используют JSX во Vue через babel.
Многие считают, что самым большим преимуществом виртуального DOM является алгоритм сравнения, который снижает потребление производительности JavaScript при работе с реальным DOM. Хотя этот виртуальный DOM дает одно преимущество, это еще не все. Самым большим преимуществом виртуального DOM является то, что он абстрагирует исходный процесс рендеринга и реализует кросс-платформенные возможности, а не только DOM браузеров и различные графические интерфейсы.
Вернемся к первоначальному вопросу, что такое виртуальный DOM, проще говоря, это обычный объект JavaScript, который содержитtag,props,childrenтри свойства.
<div id="app">
<p class="text">hello world!!!</p>
</div>
Приведенный выше HTML преобразуется в виртуальный DOM следующим образом:
{
tag: 'div',
props: {
id: 'app'
},
chidren: [
{
tag: 'p',
props: {
className: 'text'
},
chidren: [
'hello world!!!'
]
}
]
}
Этот объект мы часто называем виртуальным DOM.Поскольку DOM представляет собой древовидную структуру, ее можно легко представить с помощью объектов JavaScript. И встроенный DOM Поскольку поставщики браузеров должны реализовывать множество спецификаций (различные атрибуты HTML5, события DOM), даже создание пустого элемента div обходится дорого. Смысл повышения производительности виртуального DOM заключается в том, что при изменении DOM алгоритм сравнения сравнивает нативные объекты JavaScript, вычисляет DOM, который необходимо изменить, а затем работает только с измененным DOM вместо обновления всего представления.
Итак, как же нам преобразовать фрагмент HTML в виртуальный DOM?
Начнем с функции h
Обратите внимание на основные виртуальные библиотеки DOM (snabbdom,virtual-dom), обычно имеет функцию h, котораяReact.createElement, а в методе рендеринга в VuecreateElement, Кроме того, React преобразует jsx в форму рендеринга h-функции через babel, в то время как Vue использует vue-loader для преобразования шаблона в форму рендеринга h-функции (также можно использовать в vue через babel-plugin-transform-vue -jsx plugin jsx, суть все равно конвертируется в форму рендеринга функции h).
Сначала мы используем babel для преобразования фрагмента кода jsx в фрагмент кода js:
Установить зависимости Babel
npm i -D @babel/cli @babel/core @babel/plugin-transform-react-jsx
настроить .babelrc
{
"plugins": [
[
"@babel/plugin-transform-react-jsx",
{
"pragma": "h", // default pragma is React.createElement
}
]
]
}
транспиляция jsx
Создайте новый в каталогеmain.jsx
function getVDOM() {
return (
<div id="app">
<p className="text">hello world!!!</p>
</div>
)
}
Используйте следующую команду для перевода:
npx babel main.jsx --out-file main-compiled.js
Как видите, окончательный HTML-код будет переведен в визуализированную форму функции h. Функция h принимает три параметра, которые представляют имя тега, атрибут и дочерний узел элемента DOM, и, наконец, возвращает виртуальный объект DOM.
function h(tag, props, ...children) {
return {
tag,
props: props || {},
children: children.flat()
}
}
Визуализировать виртуальный DOM
Хотя виртуальный DOM можно отображать на нескольких платформах, вот как отображать виртуальный DOM в среде браузера.
function render(vdom) {
// 如果是字符串或者数字，创建一个文本节点
if (typeof vdom === 'string' || typeof vdom === 'number') {
return document.createTextNode(vdom)
}
const { tag, props, children } = vdom
// 创建真实DOM
const element = document.createElement(tag)
// 设置属性
setProps(element, props)
// 遍历子节点，并获取创建真实DOM，插入到当前节点
children
.map(render)
.forEach(element.appendChild.bind(element))
// 虚拟 DOM 中缓存真实 DOM 节点
vdom.dom = element
// 返回 DOM 节点
return element
}
function setProps (element, props) {
Object.entries(props).forEach(([key, value]) => {
setProp(element, key, value)
})
}
function setProp (element, key, vlaue) {
element.setAttribute(
// className使用class代替
key === 'className' ? 'class' : key,
vlaue
)
}
После преобразования виртуального DOM в реальный DOM его нужно только вставить в соответствующий корневой узел.
const vdom = <div>hello world!!!</div> // h('div', {}, 'hello world!!!')
const app = document.getElementById('app')
const ele = render(vdom)
app.appendChild(ele)
Конечно, в современных фреймворках обычно есть файл компонента, предназначенный для построения виртуального DOM Мы имитируем использование классов React для написания компонентов, а затем отображаем их на странице.
class Component {
vdom = null // 组件的虚拟DOM表示
$el = null // 虚拟DOM生成的真实节点
state = {
text: 'Initialize the Component'
}
render() {
const { text } = this.state
return (
<div>{ text }</div>
)
}
}
function createElement (app, component) {
const vdom = component.render()
component.vdom = vdom
component.$el = render(vdom) // 将虚拟 DOM 转换为真实 DOM
app.appendChild(component.$el)
}
const app = document.getElementById('app')
const component = new Component
createElement(app, component)
алгоритм сравнения
Алгоритм diff, как следует из названия, сравнивает изменения старого и нового VDOM, а затем обновляет измененные части в представлении. В соответствии с кодом, это функция сравнения, которая возвращает патчи (патчи).
const before = h('div', {}, 'before text')
const after = h('div', {}, 'after text')
const patches = diff(before, after)
Измените наш предыдущий компонент и добавьте метод setState для изменения внутреннего состояния компонента.
class Component {
vdom = null // 组件的虚拟DOM表示
$el = null // 虚拟DOM生成的真实节点
state = {
text: 'Initialize the Component'
}
// 手动修改组件state
setState(newState) {
this.state = {
...this.state,
...newState
}
const newVdom = this.render()
const patches = diff(this.vdom, newVdom)
patch(this.$el, patches)
}
changeText(text) {
this.setState({
text
})
}
render() {
const { text } = this.state
return (
<div>{ text }</div>
)
}
}
Когда мы вызываем setState, внутреннее состояние состояния изменяется, и повторный вызов метода рендеринга создаст новое виртуальное дерево DOM, чтобы мы могли использовать метод diff для вычисления измененных частей новой и старой виртуальной DOM, и, наконец, используйте метод patch, чтобы изменения отображались в представлении.
const app = document.getElementById('app')
const component = new Component
createElement(app, component)
// 将文本更改为数字，每秒 +1
let count = 0
setInterval(() => {
component.changeText(++count)
}, 1000);
Эволюция алгоритма сравнения
Самый классический пример алгоритма diff — это работа Мэтта Эша.virtual-dom,а такжеsnabbdom(интегрировано в vue 2.0).
Сначала появилась библиотека virtual-dom, которую сделали из любопытства, почему React такой быстрый. Его реализация очень академична, с поиском в глубину и деревом по порядку для эффективного сравнения. Он сильно отличается от алгоритма, который позже выпустил React.
Затем появился cito.js, который оказал большое влияние на все будущие алгоритмы виртуального DOM. Он использует алгоритм, который сравнивает оба конца одновременно, увеличивая скорость сравнения до нескольких уровней. За ним следует kivi.js, предлагающий две схемы оптимизации на основе cito.js, с использованием ключа для реализации отслеживания перемещений и применение алгоритма самой длинной самоинкрементной подпоследовательности на основе ключа (сложность алгоритма O(n ^ 2)). Но такой алгоритм сравнения слишком сложен, поэтому опоздавший snabbdom упрощает kivi.js, убирает алгоритм редактирования длины момента и расстояния и настраивает алгоритм сравнения на обоих концах. Есть небольшая потеря в скорости, но значительно улучшается читаемость. После этого знаменитый vue2.0 интегрировал всю библиотеку sanbbdom.
Цитата из статьи Ситу ЧжэнмэйОпыт разработки Qunar mini React
Давайте поговорим о конкретной реализации алгоритмов сравнения этих виртуальных DOM-библиотек:
1️⃣virtual-dom
Как новаторская работа над виртуальным DOM, виртуальный дом использует метод обхода дерева DOM в глубину.
Обход дерева DOM
Отражено в коде:
function diff (oldNode, newNode) {
const patches = []
walk(oldNode, newNode, patches, 0) // 进行深度优先遍历
return patches
}
function walk(oldNode, newNode, patches, index) {
if (newNode === oldNode) {
return
}
const patch = { type: 'update', vNode: newNode }
const oldChildren = oldNode.children
const newChildren = newNode.children
const oldLen = oldChildren.length
const newLen = newChildren.length
const len = oldLen > newLen ? oldLen : newLen
// 找到对应位置的子节点进行比对
for (let i = 0; i < len; i++) {
const oldChild = oldChildren[i]
const newChild = newChildren[i]
index++
// 相同节点进行比对
walk(oldChild, newChild, patches, index)
if (isArray(oldChild.children)) {
index += oldChild.children.length
}
}
if (patch) {
patches[index] = patch
}
}
Сравнение узлов VDOM
Приведенный выше код просто выполняет простой обход VDOM в глубину.Во время обхода также требуются некоторые сравнения каждого VDOM, которые делятся на следующие ситуации:
- Если старый узел не существует, вставьте новый узел; если новый узел не существует, удалите старый узел
- Если старый и новый узлы оба являются VNodes, а теги старого и нового узлов совпадают
- Сравните свойства старых и новых узлов
- Сравните различия между дочерними узлами старого и нового узлов, переупорядочите их по значению ключа и продолжайте обход узлов с тем же значением ключа.
- Если старый и новый узлы оба являются VText, определите, изменился ли текст двух
- В других случаях замените старый узел новым узлом напрямую.
import { isVNode, isVText, isArray } from '../utils/type'
function walk(oldNode, newNode, patches, index) {
if (newNode === oldNode) {
return
}
let patch = patches[index]
if (!oldNode) {
// 旧节点不存在，直接插入
patch = appendPatch(patch, {
type: PATCH.INSERT,
vNode: newNode,
})
} else if (!newNode) {
// 新节点不存在，删除旧节点
patch = appendPatch(patch, {
type: PATCH.REMOVE,
vNode: null,
})
} else if (isVNode(newNode)) {
if (isVNode(oldNode)) {
// 相同类型节点的 diff
if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {
// 新老节点属性的对比
const propsPatch = diffProps(newNode.props, oldNode.props)
if (propsPatch && propsPatch.length > 0) {
patch = appendPatch(patch, {
type: PATCH.PROPS,
patches: propsPatch,
})
}
// 新老节点子节点的对比
patch = diffChildren(oldNode, newNode, patches, patch, index)
}
} else {
// 新节点替换旧节点
patch = appendPatch(patch, {
type: PATCH.REPLACE,
vNode: newNode,
})
}
} else if (isVText(newNode)) {
if (!isVText(oldNode)) {
// 将旧节点替换成文本节点
patch = appendPatch(patch, {
type: PATCH.VTEXT,
vNode: newNode,
})
} else if (newNode.text !== oldNode.text) {
// 替换文本
patch = appendPatch(patch, {
type: PATCH.VTEXT,
vNode: newNode,
})
}
}
if (patch) {
// 将补丁放入对应位置
patches[index] = patch
}
}
// 一个节点可能有多个 patch
// 多个patch时，使用数组进行存储
function appendPatch(patch, apply) {
if (patch) {
if (isArray(patch)) {
patch.push(apply)
} else {
patch = [patch, apply]
}
return patch
} else {
return apply
}
}
сравнение свойств
function diffProps(newProps, oldProps) {
const patches = []
const props = Object.assign({}, newProps, oldProps)
Object.keys(props).forEach(key => {
const newVal = newProps[key]
const oldVal = oldProps[key]
if (!newVal) {
patches.push({
type: PATCH.REMOVE_PROP,
key,
value: oldVal,
})
}
if (oldVal === undefined || newVal !== oldVal) {
patches.push({
type: PATCH.SET_PROP,
key,
value: newVal,
})
}
})
return patches
}
Сравнение дочерних узлов
Можно сказать, что эта часть является частью с наибольшим количеством изменений в алгоритме сравнения, потому что в предыдущей части направление сравнения каждой библиотеки в основном такое же, и для сравнения подузлов каждый склад должен продолжать улучшить на основе прежнего.
Прежде всего, нужно понять, зачем нужно улучшать сравнение дочерних узлов. Если мы напрямую сравним дочерние узлы один за другим в соответствии с обходом в глубину, и порядок дочерних узлов изменится, это заставит алгоритм сравнения думать, что все дочерние узлы должны быть заменены, и повторно преобразовать виртуальный DOM всех дочерних узлов в настоящие DOM, эта операция очень дорогая.
Однако, если мы сможем найти позицию, соответствующую старому и новому виртуальному DOM, а затем переместить ее, мы сможем свести к минимуму работу DOM.
Virtual-dom пытался это сделать в самом начале, добавляя значение ключа к дочернему узлу и сравнивая значение ключа, чтобы определить, переместился ли дочерний узел. Режим сравнения движения дочерних узлов по значению ключа используется различными библиотеками, поэтому в основной библиотеке представления, если в дочернем узле отсутствует значение ключа, будет предупреждение.
В частности, как сравнивать, давайте сначала посмотрим на код:
function diffChildren(oldNode, newNode, patches, patch, index) {
const oldChildren = oldNode.children
// 新节点按旧节点的顺序重新排序
const sortedSet = sortChildren(oldChildren, newNode.children)
const newChildren = sortedSet.children
const oldLen = oldChildren.length
const newLen = newChildren.length
const len = oldLen > newLen ? oldLen : newLen
for (let i = 0; i < len; i++) {
var leftNode = oldChildren[i]
var rightNode = newChildren[i]
index++
if (!leftNode) {
if (rightNode) {
// 旧节点不存在，新节点存在，进行插入操作
patch = appendPatch(patch, {
type: PATCH.INSERT,
vNode: rightNode,
})
}
} else {
// 相同节点进行比对
walk(leftNode, rightNode, patches, index)
}
if (isVNode(leftNode) && isArray(leftNode.children)) {
index += leftNode.children.length
}
}
if (sortedSet.moves) {
// 最后进行重新排序
patch = appendPatch(patch, {
type: PATCH.ORDER,
moves: sortedSet.moves,
})
}
return patch
}
Здесь сначала необходимо переупорядочить новые дочерние узлы, сначала выполнить сравнение одного и того же узла и, наконец, переставить дочерние узлы в соответствии с новым порядком дочерних узлов.
Более сложной частью здесь является переупорядочивание дочерних узлов.
function sortChildren(oldChildren, newChildren) {
// 找出变化后的子节点中带 key 的 vdom (keys)，和不带 key 的 vdom (free)
const newChildIndex = keyIndex(newChildren)
const newKeys = newChildIndex.keys
const newFree = newChildIndex.free
// 所有子节点无 key 不进行对比
if (newFree.length === newChildren.length) {
return {
children: newChildren,
moves: null,
}
}
// 找出变化前的子节点中带 key 的 vdom (keys)，和不带 key 的 vdom (free)
const oldChildIndex = keyIndex(oldChildren)
const oldKeys = oldChildIndex.keys
const oldFree = oldChildIndex.free
// 所有子节点无 key 不进行对比
if (oldFree.length === oldChildren.length) {
return {
children: newChildren,
moves: null,
}
}
// O(MAX(N, M)) memory
const shuffle = []
const freeCount = newFree.length
let freeIndex = 0
let deletedItems = 0
// 遍历变化前的子节点，对比变化后子节点的 key 值
// 并按照对应顺序将变化后子节点的索引放入 shuffle 数组中
for (let i = 0; i < oldChildren.length; i++) {
const oldItem = oldChildren[i]
let itemIndex
if (oldItem.key) {
if (newKeys.hasOwnProperty(oldItem.key)) {
// 匹配到变化前节点中存在的 key
itemIndex = newKeys[oldItem.key]
shuffle.push(newChildren[itemIndex])
} else {
// 移除变化后节点不存在的 key 值
deletedItems++
shuffle.push(null)
}
} else {
if (freeIndex < freeCount) {
// 匹配变化前后的无 key 子节点
itemIndex = newFree[freeIndex++]
shuffle.push(newChildren[itemIndex])
} else {
// 如果变化后子节点中已经不存在无 key 项
// 变化前的无 key 项也是多余项，故删除
deletedItems++
shuffle.push(null)
}
}
}
const lastFreeIndex =
freeIndex >= newFree.length ? newChildren.length : newFree[freeIndex]
// 遍历变化后的子节点，将所有之前不存在的 key 对应的子节点放入 shuffle 数组中
for (let j = 0; j < newChildren.length; j++) {
const newItem = newChildren[j]
if (newItem.key) {
if (!oldKeys.hasOwnProperty(newItem.key)) {
// 添加所有新的 key 值对应的子节点
// 之后还会重新排序，我们会在适当的地方插入新增节点
shuffle.push(newItem)
}
} else if (j >= lastFreeIndex) {
// 添加剩余的无 key 子节点
shuffle.push(newItem)
}
}
const simulate = shuffle.slice()
const removes = []
const inserts = []
let simulateIndex = 0
let simulateItem
let wantedItem
for (let k = 0; k < newChildren.length; ) {
wantedItem = newChildren[k] // 期待元素: 表示变化后 k 的子节点
simulateItem = simulate[simulateIndex] // 模拟元素: 表示变化前 k 位置的子节点
// 删除在变化后不存在的子节点
while (simulateItem === null && simulate.length) {
removes.push(remove(simulate, simulateIndex, null))
simulateItem = simulate[simulateIndex]
}
if (!simulateItem || simulateItem.key !== wantedItem.key) {
// 期待元素的 key 值存在
if (wantedItem.key) {
if (simulateItem && simulateItem.key) {
// 如果一个带 key 的子元素没有在合适的位置，则进行移动
if (newKeys[simulateItem.key] !== k + 1) {
removes.push(remove(simulate, simulateIndex, simulateItem.key))
simulateItem = simulate[simulateIndex]
// if the remove didn't put the wanted item in place, we need to insert it
if (!simulateItem || simulateItem.key !== wantedItem.key) {
inserts.push({ key: wantedItem.key, to: k })
}
// items are matching, so skip ahead
else {
simulateIndex++
}
} else {
inserts.push({ key: wantedItem.key, to: k })
}
} else {
inserts.push({ key: wantedItem.key, to: k })
}
k++
}
// 该位置期待元素的 key 值不存在，且模拟元素存在 key 值
else if (simulateItem && simulateItem.key) {
// 变化前该位置的元素
removes.push(remove(simulate, simulateIndex, simulateItem.key))
}
} else {
// 如果期待元素和模拟元素 key 值相等，跳到下一个子节点比对
simulateIndex++
k++
}
}
// 移除所有的模拟元素
while (simulateIndex < simulate.length) {
simulateItem = simulate[simulateIndex]
removes.push(
remove(simulate, simulateIndex, simulateItem && simulateItem.key)
)
}
// 如果只有删除选项中有值
// 将操作直接交个 delete patch
if (removes.length === deletedItems && !inserts.length) {
return {
children: shuffle,
moves: null,
}
}
return {
children: shuffle,
moves: {
removes: removes,
inserts: inserts,
},
}
}
function keyIndex(children) {
const keys = {}
const free = []
const length = children.length
for (let i = 0; i < length; i++) {
const child = children[i]
if (child.key) {
keys[child.key] = i
} else {
free.push(i)
}
}
return {
keys: keys, // 子节点中所有存在的 key 对应的索引
free: free, // 子节点中不存在 key 值的索引
}
}
function remove(arr, index, key) {
arr.splice(index, 1) // 移除数组中指定元素
return {
from: index,
key: key,
}
}
Эта часть более сложная.Подробности см. в двух prs из virtual-dom.В двух prs обсуждается логика оптимизации для переупорядочивания подузлов diff.
обновить модель документа
После получения diff-результата VDOM необходимо обновить полученные патчи до вида.
function patch(rootNode, patches) {
if (!patches || patches.length === 0) return
// 取得对应 index 的真实 DOM
const nodes = domIndex(rootNode)
patches.forEach((patch, index) => {
patch && applyPatch(nodes[index], patch)
})
}
function domIndex(rootNode) {
const nodes = [rootNode]
const children = rootNode.childNodes
if (children.length) {
for (let child of children) {
if (child.nodeType === 1 || child.nodeType === 3) {
if (child.nodeType === 1) {
nodes.push(...domIndex(child))
} else if (child.nodeType === 3) {
nodes.push(child)
}
}
}
}
return nodes
}
Пройдите патчи, затем получите каждый реальный DOM и соответствующий ему патч, а затем обновите настоящий DOM:
function applyPatch(node, patchList) {
for (let patch of patchList) {
patchOp(node, patch)
}
}
function patchOp(node, patch) {
const { type, vNode } = patch
const parentNode = node.parentNode
let newNode = null
switch (type) {
case PATCH.INSERT:
// 插入新节点
break
case PATCH.REMOVE:
// 删除旧新节点
break
case PATCH.REPLACE:
// 替换节点
break
case PATCH.ORDER:
// 子节点重新排序
break
case PATCH.VTEXT:
// 替换文本节点
break
case PATCH.PROPS:
// 更新节点属性
break
default:
break
}
}
Каждый шаг операции здесь подробно раскрывать не буду, если интересно, можете посмотреть на моем гитхабеполный код.
2️⃣cito.js
Другие этапы cito аналогичны виртуальному дому.Самая большая разница заключается в сравнении дочерних узлов, и cito удаляет обновление патча.Во время процесса сравнения реальный DOM обновляется напрямую, что сохраняет хранилище патчей. В определенной степени это экономит память, и другие библиотеки VDOM позже в основном используют этот метод.
Давайте посмотрим, как оптимизирован cito при сравнении дочерних узлов?
На самом деле, как мы уже говорили ранее, основное изменение cito — это введение двустороннего сравнения, которое на несколько порядков увеличивает скорость алгоритма diff.
/**
* 子节点对比
* @param {Element} domNode 父节点的真实DOM
* @param {Array} oldChildren 旧的子节点
* @param {Array} children 新的子节点
*/
function updateChildren(domNode, oldChildren, children) {
const oldChildrenLength = oldChildren.length
const childrenLength = children.length
let oldEndIndex = oldChildrenLength - 1
let endIndex = childrenLength - 1
let oldStartIndex = 0
let startIndex = 0
let successful = true
let nextChild
// 两端对比算法
outer: while (
successful &&
oldStartIndex <= oldEndIndex &&
startIndex <= endIndex
) {
successful = false
let oldStartChild = oldChildren[oldStartIndex]
let startChild = children[startIndex]
while (oldStartChild.key === startChild.key) {
// 子节点对比
updateNode(oldStartChild, startChild, domNode)
oldStartIndex++
startIndex++
if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
break outer
}
oldStartChild = oldChildren[oldStartIndex]
startChild = children[startIndex]
successful = true
}
let oldEndChild = oldChildren[oldEndIndex]
let endChild = children[endIndex]
while (oldEndChild.key === endChild.key) {
// 子节点对比
updateNode(oldEndChild, endChild, domNode)
oldEndIndex--
endIndex--
if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
break outer
}
oldEndChild = oldChildren[oldEndIndex]
endChild = children[endIndex]
successful = true
}
while (oldStartChild.key === endChild.key) {
nextChild = endIndex + 1 < childrenLength ? children[endIndex + 1] : null
// 子节点对比
updateNode(oldStartChild, endChild, domNode)
// 移动子节点
moveChild(domNode, endChild, nextChild)
oldStartIndex++
endIndex--
if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
break outer
}
oldStartChild = oldChildren[oldStartIndex]
endChild = children[endIndex]
successful = true
}
while (oldEndChild.key === startChild.key) {
nextChild = oldStartIndex < oldChildrenLength ? oldChildren[oldStartIndex] : null
// 子节点对比
updateNode(oldEndChild, startChild, domNode)
// 移动子节点
moveChild(domNode, startChild, nextChild)
oldEndIndex--
startIndex++
if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
break outer
}
oldEndChild = oldChildren[oldEndIndex]
startChild = children[startIndex]
successful = true
}
}
}
Сравнение дочерних узлов:
function updateNode(oldNode, node, domParent) {
if (node === oldNode) {
return
}
const tag = node.tag
if (oldNode.tag !== tag) {
// 标签不一致，创建新节点
createNode(node, domParent, oldNode, true)
} else {
const oldChildren = oldNode.children
const children = node.children
const domNode = oldNode.dom
node.dom = domNode // 真实 DOM 挂在到 虚拟 DOM 上
// 子节点对比
if (children !== oldChildren) {
updateChildren(domNode, node, oldChildren, children)
}
const oldProps = oldNode.props
const props = node.props
// 属性对比
if (props !== oldProps) {
updateAttributes(domNode, props, oldProps)
}
}
}
Переместить дочерние узлы:
function moveChild(domNode, child, nextChild) {
const domRefChild = nextChild && nextChild.dom
let domChild = child.dom
if (domChild !== domRefChild) {
if (domRefChild) {
domNode.insertBefore(domChild, domRefChild)
} else {
domNode.appendChild(domChild)
}
}
}
3️⃣kivi.js
На основе cito алгоритм kivi diff вводит самую длинную растущую подпоследовательность и находит наименьшее количество операций DOM в подпоследовательности.
Алгоритмическое мышление
Переведено сkivi/lib/reconciler.ts
Этот алгоритм используется для нахождения минимального количества операций DOM и может быть разделен на следующие этапы:
1. Найдите общий узел в начале и в конце массива и переместите его с обоих концов.
Этот метод находит узел с одинаковым индексом в старом узле (A) и новом узле (B) путем сравнения значений ключа на обоих концах.
A: -> [a b c d e f g] <-
B: [a b f d c g]
Здесь мы можем пропустить первыйaиb, и отставаниеg.
A: -> [c d e f] <-
B: [f d c]
В этот момент будет предпринята попытка сравнить ребра, и если на противоположном ребре есть узел с таким же значением ключа, будет выполнена простая операция перемещения, иcУзел перемещается в
правый край, будетfУзел перемещается к левому краю.
A: -> [d e] <-
B: [d]
Теперь попытаюсь снова найти общие заголовки и трейлеры и найтиdУзел тот же, пропускаем.
A: -> [e] <-
B: [ ]
Затем проверьте, равна ли длина каждого списка 0, если старый список узлов имеет длину 0, оставшиеся узлы нового списка узлов будут вставлены, или если новый список узлов имеет длину 0, все элементы в старом списке узлов будут вставлены. быть удалены.
Этот простой алгоритм подходит для большинства практических случаев, таких как просто переворачивание списка.
Когда список не может найти решение с помощью этого алгоритма, используется следующий алгоритм, например:
A: -> [a b c d e f g] <-
B: [a c b h f e g]
пограничныйaиgУзлы одинаковые, пропускайте их.
A: -> [b c d e f] <-
B: [c b h f e]
Тогда вышеописанный алгоритм не работает и нужно переходить к следующему шагу.
2. Найдите узел, который нужно удалить или вставить, и нужно ли переместить узел.
Сначала мы создаем массивP, длина представляет собой длину списка новых дочерних узлов и присваивает -1 каждому элементу массива, что указывает, куда следует вставить новый дочерний узел. Позже мы назначим этому массиву позиции узлов в старых дочерних элементах.
A: [b c d e f]
B: [c b h f e]
P: [. . . . .] // . == -1
Затем мы создаем объектI, ключ которого представляет значение ключа нового дочернего узла, а значение — это позиция дочернего узла в оставшемся массиве узлов.
A: [b c d e f]
B: [c b h f e]
P: [. . . . .] // . == -1
I: {
c: 0,
b: 1,
h: 2,
f: 3,
e: 4,
}
last = 0
Мы начинаем обход оставшихся узлов старого списка дочерних узлов и проверяем, можем ли мыIУзел с таким же значением ключа находится в индексе объекта. Если узел не найден, удаляем его, в противном случае мы присваиваем узел массиву в старой позиции списка узлов.P.
A: [b c d e f]
^
B: [c b h f e]
P: [. 0 . . .] // . == -1
I: {
c: 0,
b: 1, <-
h: 2,
f: 3,
e: 4,
}
last = 1
когда мы массивыPПри назначении позиции узла мы сохраняем позицию предыдущего узла в новом списке дочерних узлов, если, когда позиция узла больше, чем позиция текущего узла, мыmovedустановить переменную вtrue.
A: [b c d e f]
^
B: [c b h f e]
P: [1 0 . . .] // . == -1
I: {
c: 0, <-
b: 1,
h: 2,
f: 3,
e: 4,
}
last = 1 // last > 0; moved = true
предыдущий узелbпозиция "1", текущий узелcположение «0», поэтомуmovedустановить переменную вtrue.
A: [b c d e f]
^
B: [c b h f e]
P: [1 0 . . .] // . == -1
I: {
c: 0,
b: 1,
h: 2,
f: 3,
e: 4,
}
moved = true
объектIне существует в индексеd, удалить узел
A: [b c d e f]
^
B: [c b h f e]
P: [1 0 . . 3] // . == -1
I: {
c: 0,
b: 1,
h: 2,
f: 3,
e: 4, <-
}
moved = true
для узлаeВыделенное место.
A: [b c d e f]
^
B: [c b h f e]
P: [1 0 . 4 3] // . == -1
I: {
c: 0,
b: 1,
h: 2,
f: 3, <-
e: 4,
}
moved = true
для узлаfВыделенное место.
В этот момент мы проверяемmovedНезависимо от того, включен ли флаг, или длина старого дочернего списка за вычетом количества удаленных узлов не равна длине нового дочернего списка. Если хоть одно из этих условий выполняется, переходим к следующему шагу.
3. ЕслиmovedTrue, найдите минимальное количество ходов и вставьте новый узел, если длина отправленного сообщения изменится.
еслиmovedправда, нам нужноPнашел в массивесамая длинная подпоследовательность с автоинкрементом, и переместите все узлы, не входящие в эту подпоследовательность.
A: [b c d e f]
B: [c b h f e]
P: [1 0 . 4 3] // . == -1
LIS: [1 4]
moved = true
Теперь нам нужно одновременно пройти новый список дочерних узлов и самую длинную самоувеличивающуюся подпоследовательность (далее LIS) из хвоста и проверить, равна ли текущая позиция значению LIS.
A: [b c d e f]
B: [c b h f e]
^ // new_pos == 4
P: [1 0 . 4 3] // . == -1
LIS: [1 4]
^ // new_pos == 4
moved = true
узелeсохранить текущее местоположение
A: [b c d e f]
B: [c b h f e]
^ // new_pos == 3
P: [1 0 . 4 3] // . == -1
LIS: [1 4]
^ // new_pos != 1
moved = true
мобильный узелf, перейти к следующему узлуeвпереди него.
A: [b c d e f]
B: [c b h f e]
^ // new_pos == 2
P: [1 0 . 4 3] // . == -1
^ // old_pos == -1
LIS: [1 4]
^
moved = true
узелhЕсли это -1 в массиве P, это означает вставку нового узлаh.
A: [b c d e f]
B: [c b h f e]
^ // new_pos == 1
P: [1 0 . 4 3] // . == -1
LIS: [1 4]
^ // new_pos == 1
moved = true
узелbсохранить текущее местоположение
A: [b c d e f]
B: [c b h f e]
^ // new_pos == 0
P: [1 0 . 4 3] // . == -1
LIS: [1 4]
^ // new_pos != undefined
moved = true
мобильный узелc, перейти к следующему узлуbвпереди него.
еслиmovedзаfalse, нам не нужно искать LIS, мы просто перебираем список новых дочерних элементов и проверяем, есть ли они в массивеPПозиция в , если она равна -1 , вставьте новый узел.
О киви
kivi — это авторская догадка по улучшению производительности виртуального DOM, она изначально отталкивается от производительности, поэтому код ее реализации может быть не элегантен, а его api тоже очень недружественный. Следующий snabbdom основан на kivi, что значительно улучшает читаемость кода.Многие статьи про виртуальный DOM также используют snabbdom в качестве примера.
Кроме того, автор kivi также создал еще один репозиторий с большим количеством исходного кода и API:ivi, вы можете узнать, если вы заинтересованы.
4️⃣snabbdom
Преимущество snabbdom в том, что значительно улучшается читабельность кода, а также вводится сравнение обоих концов, да и скорость диффа не медленная.
Мы можем просто посмотреть на основной код алгоритма сравнения snabbdom с обеих сторон:
/**
* 子节点对比
* @param {Element} parentElm 父节点的真实DOM
* @param {Array} oldCh 旧的子节点
* @param {Array} newCh 新的子节点
*/
function updateChildren(parentElm, oldCh, newCh) {
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
let oldKeyToIdx
let idxInOld
let elmToMove
let before
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 跳过两端不存在的旧节点
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
}
// 跳过两端不存在的新节点
else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
}
/*
** 进行两端对比，分为四种状况：
** 1. oldStart <=> newStart
** 2. oldEnd <=> newEnd
** 3. oldStart <=> newEnd
** 4. oldEnd <=> newStart
*/
else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
insertBefore(parentElm, oldStartVnode.dom, oldEndVnode.dom.nextSibling)
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// Vnode moved left
patchVnode(oldEndVnode, newStartVnode)
insertBefore(parentElm, oldEndVnode.dom, oldStartVnode.dom)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
// 上面四种情况都不存在，通过 key 值查找对应 VDOM 进行对比
else {
// 构造旧子节点的 map 表 (key => vdom)
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
idxInOld = oldKeyToIdx[newStartVnode.key]
// 如果新的子节点在旧子节点不存在，进行插入操作
if (idxInOld === undefined) {
insertBefore(parentElm, render(newStartVnode), oldStartVnode.dom)
newStartVnode = newCh[++newStartIdx]
}
// 如果新的子节点在旧子节点存在，进行对比
else {
elmToMove = oldCh[idxInOld]
if (elmToMove.sel !== newStartVnode.sel) {
// key 值相同，但是 tag 不同，重新生成节点并替换
insertBefore(parentElm, render(newStartVnode), oldStartVnode.dom)
} else {
patchVnode(elmToMove, newStartVnode)
oldCh[idxInOld] = undefined // 该位置已经对比，进行置空
insertBefore(parentElm, elmToMove.dom, oldStartVnode.dom)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
// 处理一些未处理到的节点
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].dom
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
} else {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
}
Что касается snabbdom, то в Интернете слишком много руководств по анализу его процесса сравнения.Будь то учебник по виртуальному DOM или анализ исходного кода Vue, здесь подробно описываться не будет. Но хорошо видно, что алгоритм diff в snabbdom имеет тень cito и kivi.
Суммировать
Нет никаких сомнений в том, что виртуальный DOM привносит во внешний интерфейс экстраординарное значение, и сегодня виртуальный DOM предлагает более свежие способы игры. НапримерomiОбъединение Virtual DOM с веб-компонентами иTaroиChameleonВозможность довести несколько концов унифицированы.
Кроме того, соответствующий код в тексте можно найти в моемgithubПроверьте, эта статья является скорее записью вашего собственного обучения, если у вас есть какие-либо неправильные взгляды, пожалуйста, поправьте меня.