Недавно я смотрел на некоторые низкоуровневые знания. Поэтому я хочу сделать серию, чтобы попытаться рассказать об этих более сложных и важных моментах знания. Обучение похоже на большую гору: только взобравшись на гору самостоятельно, вы сможете увидеть разные пейзажи и получить более глубокие переживания. Сегодня мы поговорим о более важных алгоритмах vue virtual (Virtual) DOM и diff в Vue.
Виртуальный (виртуальный) DOM
Виртуальный DOM на самом деле представляет собой дерево, основанное на объектах JavaScript (узлах VNode), с использованием атрибутов объекта для описания узлов, что эквивалентно добавлению кеша между js и реальным DOM, с использованием алгоритма dom diff, чтобы избежать ненужных операций с DOM, таким образом улучшить производительность. Конечно, алгоритм иногда не является оптимальным решением, потому что он должен быть совместим со многими ситуациями, которые могут возникнуть на практике, такими как перемещение двух узлов по дереву dom, которое будет обсуждаться позже.
В предыдущих статьях легче понять управление состоянием данных vue в сочетании с Virtual DOM. В vue состояние элемента обычно изменяется, а подписчик компилирует и отображает в соответствии с изменением состояния. Базовая реализация может просто понимать как три шага. :
1. Используйте структуру объекта JavaScript, чтобы выразить структуру дерева dom, а затем используйте это дерево, чтобы построить настоящее дерево dom и вставить его на страницу браузера.
2. Когда состояние изменяется, то есть наше состояние изменяется, Vue реконструирует дерево объектов дерева, а затем использует вновь построенное дерево для сравнения со старым деревом (сравнивается только тот же слой), записывает разницу между два дерева.
3. Повторно примените разницу, записанную в шаге 2, к настоящему дереву DOM, построенному на шаге 1, и представление обновится.
Пример: есть список ul>li, который записан в шаблоне как:
Vue сначала скомпилирует шаблон, который включает в себя три процесса: синтаксический анализ, оптимизация и генерация.
parse будет использовать обычные и другие методы для анализа инструкций, классов, стилей и других данных в шаблоне шаблона для формирования AST, поэтому наш ul> li может быть проанализирован следующим образом
Процесс оптимизации на самом деле только для оптимизации алгоритма diff в следующем тексте.Если этот процесс не добавить, то нужно сравнивать узлы каждого слоя, и даже неизменяемую часть приходится делать заново, что также нарушает исходный суть виртуального DOM, в результате чего несогласованные необходимые ресурсы рассчитываются и тратятся впустую. Поэтому в процессе компиляции Vue будет активно отмечать статические статические узлы, Лично под этим понимаются некоторые узлы на странице, неизменные или не затронутые состоянием. Например, наш узел ul, как бы ни менялся li, ul никогда не изменится, поэтому в процессе компиляции каждый ul можно пометить меткой. Когда последующее обновление обновляет интерфейс представления, процесс исправления видит эту метку и пропускает эти статические узлы напрямую.
Наконец, преобразуйте AST в строку функции рендеринга с помощью generate, и результатом будет строка рендеринга и строка staticRenderFns. Вы можете показаться запутанным. Прежде всего, вы должны почти знать первые два шага. Когда вы получаете AST, внутри Vue есть генератор кода, называемый element ASTs. Как и в названии, функция generate получает проанализированный объект AST. Дерево AST, создание разных методов для внутренних вызовов для разных узлов AST, затем объединение исполняемых строк JavaScript, ожидание последующих вызовов. Это может закончиться так:
Весь код процесса, сгенерированный Virtual DOM, можно упростить следующим образом: заинтересованные студенты могут перейти к соответствующему исходному коду Vue, исходный код находится в src/compiler/index.js.
Исходный алгоритм diff на самом деле «непригоден», потому что временная сложность составляет O (n ^ 3). Предположим, что дерево dom имеет 1000 узлов, первый проход должен пройти по дереву1, второй проход — по дереву2, а последний проход — отсортировать и объединить в новое дерево. Таким образом, эти 1000 узлов должны вычислить 1000^3 = 100 миллионов раз, что является очень большим вычислением, и этот алгоритм в основном бесполезен.
Позже дизайнеры придумали несколько методов для изменения временной сложности с O(n^3) на O(n), так как же эти разработчики реализовали это? В этом преимущество алгоритма diff, а также некоторое знание, которое мы обычно понимаем:
1. Сравнивайте только один уровень, а не межуровневое сравнение
2. Если теги не совпадают, удалите и перестройте напрямую, и больше не сравнивайте по глубине.
3. Если тег и ключ совпадают, они считаются одним и тем же узлом и не сравниваются по глубине.
Это простой диф. При сравнении узлов дерева одного и того же слоя вместо поиска и обхода дерева слой за слоем временная сложность составляет всего O (n).
Как упоминалось ранее в Virtual DOM, когда состояние изменяется, Vue реконструирует дерево объектов дерева, а затем сравнивает вновь построенное дерево со старым деревом. Этот процесс называется исправлением. «Различия» получаются в результате сравнения, и эти «различия» окончательно обновляются в представлении. Процесс исправления также является основным алгоритмом vue и react, который трудно понять. Давайте сначала посмотрим на несколько простых графиков, чтобы понять, как diff сравнивает разницу между старыми и новыми виртуальными узлами.
Сценарий 1. Обновление удаления перемещения
Движущаяся сцена должна быть самой основной в diff. для достижения этого эффекта. Мы можем переместить b в конец того же слоя или переместить c в начало B, а затем переместить D в начало B. Конечно, это результат сравнения ключей. Если ключа нет, то сравниваться будут только друг с другом по очереди, причем b ==> c, c==> d, d ==> b. Затем в третьем слое, поскольку вновь созданный c не имеет e и f, он создаст новые e и f. Чтобы повторно использовать e и f, после установки ключа соответствующий узел будет искаться в объекте oldKeyToIdx, сгенерированном ключом. Пусть алгоритм знает не удалять узлы, а перемещать узлы, что является ролью ключей и ключей. То же самое верно для вставки новых узлов в массив.
Сценарий 2: Удалить новый
Мы могли бы ожидать, что переместим C сразу за B, что является оптимальной операцией. Но фактическая операция diff состоит в том, чтобы удалить c и создать c и вставить его ниже b, что является результатом сравнения на одном уровне. Если его можно оптимизировать вручную, когда это необходимо, например, рендеринг дочерних компонентов перехватывается для оптимизации в жизненном цикле shouldComponentUpdate реакции.
В простом понимании реальной работы алгоритма diff. Для того, чтобы все лучше поняли, потому что это произведение еще сложнее. Далее мы проанализируем, как алгоритм diff выполняет обход в глубину в виде псевдокода и записывает различия.
Алгоритм сравнения VDOM Vue заимствован изsnabbdom, можно было бы также начать с примера snabbdom
В Vue новое и старое деревья сначала просматриваются в глубину, так что каждый узел будет иметь уникальную метку. При обходе каждый раз при обходе узла узел будет сравниваться с новым деревом, и если есть разница, то она будет записываться в объект.
/* 创建diff函数，接受新旧量两棵参数 */
function diff (oldTree, newTree) {
var index = 0 //当前节点的标志
var patches = {} //用来记录每个节点差异的对象
dfsWalk(oldTree, newTree, index, patches) // 对两棵树进行深度优先遍历
return patches //返回不同的记录
}
function dfsWalk (oldNode, newNode, index, patches) {
var currentPatch = [] // 定义一个数组将对比oldNode和newNode的不同，记录下来
if (newNode === null) {
// 当执行重新排序时，真正的DOM节点将被删除，因此不需要在这里进行调整
} else if (_.isString(oldNode) && _.isString(newNode)) {
// 判断oldNode、newNode是否是字符串对象或者字符串值
if (newNode !== oldNode) {
//节点不同直接放入到数组中
currentPatch.push({ type: patch.TEXT, content: newNode })
}
} else if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) {
// 节点是相同的，diff区分旧节点的props和子节点
// diff处理props
var propsPatches = diffProps(oldNode, newNode)
if (propsPatches) {
currentPatch.push({ type: patch.PROPS, props: propsPatches })
}
// diff处理子节点，如果有‘ignore’这个标志的。diff就忽视这个子节点
if (!isIgnoreChildren(newNode)) {
diffChildren(
oldNode.children,
newNode.children,
index,
patches,
currentPatch
)
}
} else {
// 节点不相同，用新节点直接替换旧节点
currentPatch.push({ type: patch.REPLACE, node: newNode })
}
}
function isIgnoreChildren (node) {
return (node.props && node.props.hasOwnProperty('ignore'))
}
/* 处理子节点diffChildren函数 */
function diffChildren (oldChildren, newChildren, index, patches, currentPatch) {
var diffs = listDiff(oldChildren, newChildren, 'key')
newChildren = diffs.children
if (diffs.moves.length) {
var reorderPatch = { type: patch.REORDER, moves: diffs.moves }
currentPatch.push(reorderPatch)
}
var leftNode = null
var currentNodeIndex = index
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i]
currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1
dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点
leftNode = child
})
}
/* 处理子节点的props diffProps函数 */
function diffProps (oldNode, newNode) {
var count = 0
var oldProps = oldNode.props
var newProps = newNode.props
var key, value
var propsPatches = {}
// Find out different properties
for (key in oldProps) {
value = oldProps[key]
if (newProps[key] !== value) {
count++
propsPatches[key] = newProps[key]
}
}
// Find out new property
for (key in newProps) {
value = newProps[key]
if (!oldProps.hasOwnProperty(key)) {
count++
propsPatches[key] = newProps[key]
}
}
// If properties all are identical
if (count === 0) {
return null
}
return propsPatches
}
// 暴露diff函数
module.exports = diff