Привет.

У многих frontend-разработчиков бытует мнение, что технология VDOM, которая, в частности, используется в React.js, работает как черный ящик. Так же на просторах npm есть куча библиотек, реализующих эту технологию, однако вот как по мне — так в них черт ногу сломит. Сама тема VDOM-а меня заинтересовала некоторое время назад и я начал экспериментировать наощупь, сам. В конечном итоге все кончилось тем, что я сделал свою реализацию VDOM-а и встроил в свой фрейморк для датагридов (о нём я как-нибудь напишу). Это оказалось не просто, а очень просто и в этой статье я детально объясню что к чему, зачем и почему. И как оно работает тоже расскажу. Ныряйте под кат и мы предадимся интересному опыту.

Disclamer

Я не фронтенд-разработчик. Не бейте меня тапками.
Так же, не стоит писать "возьми готовый фреймворк, дубина". Я знаю о том, что есть готовые фреймворки, но мне нужна собственная реализация по ряду сугубо технических причин.

Зачем оно надо

TL;DR: Пример из этой статьи на jsfiddle, исходники

На хабре где-то уже была статья про VDOM, но объяснение сути дела в ней мне не нравится. Поэтому давайте я на пальцах раскидаю. Итак, положим у вас есть веб-страничка, ага? В ней отрисован некий HTML-элемент (вероятно, довольно большой). Чтобы немного добавить контекста — скажу что этот элемент отрисован посредством натягивания шаблона на вью-модель. Ну все пользовались фреймворками, которые делают подобное, ведь так? Handlebars там, lodash-шаблоны, AngularJS в какой-то мере… И вот короче представьте что модель, на которую натягивается шаблон — поменялась. И вам надо отрисовать эти изменения внутри HTML-элемента. Возникает вопрос — а как это сделать и при этом не попасть впросак? Тут, как водится, есть несколько вариантов.

innerHTML

Можно прогнать модель данных через шаблонизатор, получить HTML и просто сделать element.innerHTML = ourHtmlString;. Дешево и сердито, но для некоторых задач вполне прокатывает. Что же здесь ужасного, спросите вы?

А я вам отвечу: этот вариант плох прежде всего потому, что все дочерние элементы, расположенные внутри element будут беспощадно убиты браузером и заменены новыми. Следовательно? Да, следовательно вы потеряете все подписки на события (в рамках вашего элемента, конечно же), которые у вас были. Вам придется переподписывать вновь созданные элементы заново. Тут я, честно признаюсь, не в курсе как работает сборка мусора в разных js-движках, но допускаю что если ранее в своем коде вы сохранили какие-то из дочерних элементов, например, в переменные, то эти элементы будут убраны из дерева, но не уничтожены. Привет, утечка памяти, мы по тебе скучали. Ну это если предположить что браузер использует для DOM-элементов reference counting, например. Кто знает подробности — отпишите в комментариях пожалуйста.

Окромя этого — сей вариант дюже медленный, особливо когда дочерних элементов много. То есть браузер честно сотрет все, что было отрисовано внутри элемента, пересчитает и перерисует заново. Вот представьте — нарисована у вас карточка пользователя Гриши, в которой 100 разных полей. А у вас в данных изменилась только дата рождения. И что теперь — "Все фигня, Гриша, давай по-новой" ради одного несчастного куска текста? Убьем Гришу целиком, посчитаем и нарисуем заново? А вы знаете, что перерисовка интерфейса в браузере — это вообще-то долго? И если Гриша состоит из 150 элементов — то еще куда ни шло. А вот если из тысячи (вскрытие показывает у Гриши обилие мелких деталей) — то на отдельных машинах перерисовка может достигать нескольких секунд, что дюже снижает отзывчивость интерфейса.

Ну и самое печальное: через innerHTML отрисовываются не все элементы. Как пример — в IE8 невозможно установить innerHTML у элемента tbody. В Google Chrome через innerHTML плохо рендерятся заголовки таблиц (th). Все, что вы туда вставите через innerHTML — будет урезано до обычного текста по неведомой мне причине. Пруфлинка не будет — информация из собственного опыта. Вероятно сейчас это уже починили, но осадочек остался.

Таким образом innerHTML — как быстрый и грязный хак. Ненадежен в общем случае, имеет кучу сайд-эффектов, да и вообще — мы тут не в 9 классе школы чтобы так писать. Из плюсов — реализуется на коленке.

Парсер HTML

Откровенно говоря, этот вариант решает только последнюю и самую печальную проблему innerHTML — крайнюю привередливость в создаваемых элементах. Но упомянуть его определенно стоит, во многом потому что он нам понадобится для реализации VDOM.

Как оно работает? Да просто работает. Парсит HTML и вызывает document.createElement для каждого узла с последующей установкой атрибутов. Потом делаете element.innerHTML = '' и проходитесь по полученным элементам, вызывая appendChild/insertBefore.

Ну… Во-первых, мы не решили проблему с убиением элементов. Во-вторых, с парсерингом HTML всё не так гладко в этом мире.

Парсить HTML — это примерно как парсить XML-документ и в парсерах для клиентской стороны чаще всего употребляется в пищу поточный парсер. Дада, это примерно как StAX в Java. Доказано, что употребление поточного парсера XML полезно для здоровья. Почему? Да потому что работает быстро и пишется легко. Не стоит использовать для этой задачи классический древесный парсер как для XML. Оно тут просто не нужно.

Все в мире HTML-парсеров хорошо, кроме одного: нету их, бедняжек, встроенных в браузеры. В MDN упоминается DOMParser, однако он все еще экспериментален и, видимо, отдаст вам на выходе дерево. Ну вот только обходить деревья и вызывать document.createElement нам на стороне клиента-то и не хватало, ага. Словом, странный он. Давайте не будем его трогать. Есть htmlparser2 — вон лежит в npm. Событийный поточный парсер, но я сам его не пользовал, ибо как идеология моего фреймворка не позволяет мне использовать сторонние зависимости. И вот есть статья и пример кода Джона Резига (пожалуйста, воспринимайте его в отрыве от jQuery), где он объяснет всё на пальцах и дает код простенького парсера. Мне он не нравится тем, что работает на регулярных выражениях. Вижу сие зело трудозатраным. Однако, вполне работоспособным. Долгое время у меня (каюсь) использовался как раз код из этой статьи, переработанный под TypeScript. Однако потом я заменил его на поточный парсер на простенькой state-машине (коим я с вами сегодня и поделюсь), дабы минимизировать сравнения строк и сделать поддержку создания виртуальных элементов (что в пример Джона запиливать было несколько неудобно).

VDOM собственной персоной

И вот мы наконец подошли к самому хитрому подходу, который решает проблемы как с производительностью, так и с привередливостью innerHTML к элементам. А именно — используя парсер HTML мы можем, внезапно, распарсить наш HTML, но вызывать для каждого элемента не document.createElement, а просто создание какого-либо объекта, который будет хранить имя тега и атрибуты. Этот самый объект и будет называться виртуальным DOM-узлом, а их совокупность — виртуальным DOM-деревом, или VDOM. Здесь стоит отметить, что создать тысячу объектов в JS через var a = {}; — это быстро. Очень быстро. А вот создать тысячу реальных DOM-узлов — это медленно. Из этого обстоятельства, собсно, и проистекает прирост производительности.

Окей, создали. И что же мы будем с этим добром делать? Снимать штаны и бегать Штаны можно не снимать, а вот бегать придется: мы будем сравнивать структуру нашего VDOM-дерева с тем, что уже отрисовано, составлять из этого некое подобие diff-патча (что надо доабвить, что убрать, куда докинуть атрибутов, где поменять контент) и накатывать его на существующее DOM-дерево. Вот прям так же, как это происходит в вашем любимом git во время мерджей. Благо, задача построения diff-а в программировании довольно известная — гуглится, внезапно, по словам нахождение наибольшей общей подпоследовательности. Решается она динамическим программированием. Алгоритм имеет квадратичную сложность. В хороших ВУЗах решение этой задачи изучают на первых курсах, но здесь я его тезисно опишу и подскажу как адаптировать его под деревья.

UPD: в комментариях меня уже закидали помидорами на предмет того, что LCS для данной задачи неоптимален — необходимо использовать LIS, но я не могу переписать статью и код так быстро. Так что просто держите в голове, что ту часть, которая занимается высчитыванием diff-а можно оптимизировать гораздо "плотнее".

В итоге, VDOM-подход не убивает те элементы дерева, которые не изменились и не создаёт лишних элементов, что знатно экономит память и сохраняет подписки на события (если элементы не уничтожаются), одновременно заставляя ваш CPU больше заниматься сравнениями, нежели созданием HTML-элементов. А это даёт знатный прирост производительности, когда из 1000 элементов на экране изменился только один.

Приступим

Мы напишем небольшое приложение, которое будет состоять из textarea слева, в которой вы будете вбивать и/или изменять свой HTML, а в окошке справа — видеть результат работы. Никаких дополнительных библиотек — только TypeScript и браузер. Будем, что называется, творить магию из воздуха.

Вы знаете, сначала я хотел добавить в эту статью много кода с построчным разбором оного, но памятуя свои предыдущие статьи, не решился это делать. Непосредственно код снижает читаемость и нагоняет тоску. Так что, с вашего позволения, я просто буду давать ссылки на Github и объясню как и что работает. Наш VDOM будет состоять из трёх главных компонент — парсера HTML, непосредственно компаратора и калькулятора батчей, а так же app.ts, который соберёт это всё добро вместе и заставит работать.

Парсер

Тут надо сделать оговорочку. Как я понимаю, React.js работает без парсера HTML в виду того, что его шаблоны (jsx/tsx) уже собираются в соответствующие вызовы создания нод. Это хороший ход, улучшающий быстродействие, но вы знаете… создавать свой язык шаблонизации и писать для него компилятор не входило в мои планы, когда я писал эту статью. Так что мы будем парсить голый HTML руками. Такая реализация гарантирует нам возможность встраивать нашу поделку куда угодно, ну и позволит избежать чисто педагогических курьёзов, если вы понимаете о чём я :) Итак, поехали.

Стек

JavaScript не содержит эффективных инструментов для работы со стеками, а таковой нам понадобится. Поэтому делаем простенький стек. Без комментариев.

Конструктор нод

Как вы знаете, с точки зрения JavaScript, HTML-документ состоит из нод. Некоторые из которых вполне себе являются HTML-элементами, такими как HTMLInputElement (тег input), HTMLDivElement (тег div). А некоторые — нет (текст, комментарий). Все доступные типы нод перечислены вот здесь, в MDN. Мы же начнем с простого — объявим интерфейс т.н. "конструктора нод". Чтобы не вхардкоживать в наш парсер HTML-я вызовы document.createElement и использовать один и тот же парсер что для DOM, что для VDOM. В моей реализации он выглядит вот так. Как видим, мы ограничиваемся тремя типами нод — HTML-элемент, текст (контент) и комментарий. Интерфейс крайне прост и предусматривает возможность создания всех трех типов нод, а для HTML-элемента ещё и установку аттрибутов. Чтобы далеко не отходить от кассы, тут же реализуем его для реальных HTML-нод. Это очень просто. Справится даже ребёнок.

Тут же мы продумаем как мы будем хранить VDOM-ноды. Что нам важно знать о ноде, помимо её типа? В случае с HTML-элементом — тег да атрибуты. В случае с комментарием и текстом — контент. Плюс ко всему прочему нам так же важен список дочерних нод. Отлично. Описываем интерфейс и enum для типов, после чего реализуем сам конструктор: вот так.

Парсер HTML

Парсер — это у нас будет такая штука, у которой есть ограниченной число состояний. Она неспеша идёт по переданному ей HTML, символ за символом и в зависимости от текущего символа меняет своё состояние. При переходе из состояния в состояние парсер будет дёргать методы конструктора нод, выполняя соответствующие действия.

Например: читает парсер символы, никого не трогает. Оп — встретил <, запоминает где его увидел, меняет состояние на "слушаем внимательно, сейчас будет HTML-тег". Читает дальше. Оп — встречает пробельный символ, и такой: ага! вот оно и имя тега. Вспоминает где встретил <, выгрызает текст оттуда до текущей позиции — вот вам и имя тега. Стало быть, надо дернуть нод-конструктор и вызвать у него create, передав имя тега. Дальше парсер пропускает все пробельные символы и если видит >, то переходит в изначальное состояние. А если видит букву алфавита — так же ловит имя атрибута, =, значение атрибута в кавычках, дергает нод-конструктор… Ну и так далее, пока не дойдет до конца.

Созданные теги мы будем хранить в стеке. Каждый раз, когда мы доходим до открывающего тега — кладём его в стек. При создании элемента через конструктор, указываем текущую макушку стека как родительский элемент. Тривиально. Уверен, все хоть раз, да делали нечто подобное, когда писали калькулятор на первых курсах университета.

Все состояния, а так же действия при переходах мы сложим в state-машину, которая технически представляет из себя огромный Dictionary, чёртов C# в голове hash-объект вида "состояние" -> "описание действий". Описание действий в нашем случае состоит из трёх частей:

• функция, которая выполнится на входе в состояние;
• функция, которая выполнится на выходе из состояния;
• функция, которая будет вызываться для каждого следующего считанного символа;

Я объединил эти три функции в штуку, которую назвал IStateInfo. Там же я описал все возможные состояния парсера. Сделал сам парсер, снабдив его несколькими полезными тестер-функциями (это когда мы смотрим какой у нас символ текущий, что было n символов назад, складываются ли следующие за текущим m символов в такое-то слово, ну и иже с ними). Особливо выделяется функция fix(): когда мы меняем состояние парсера — она запоминает позицию текущего символа с той мыслью, чтобы сдвинувшись на несколько символов далее, мы могли выгрызть кусок текста между запомненной позицией и текущим положением. Выгрызание куска текста от запомненной позиции до текущей производится функцией cut(). Обычно, после вызова cut() — state-машина подает парсеру сигнал — вроде "о, смотри, открывающий тег поймали, вот его имя". Почему так сложно? Ну… я — человек экономный. Сделал парсер, который не создает лишних строк без необходимости.

Ну и, собственно, дальше я просто перечислил все возможные состояния парсера и все возможные действия — что называется, запрограммировал state-машину. Там есть много нюансов, связанных с кавычками вокруг атрибутов, самозакрывающимися тегами, символами - и : в именах атрибутов. Разрешите мне опустить здесь детальное разжевывание каждого из этих кейсов — всё есть в коде, при желании вы сами это увидите.

Ещё одна особенность: теги style и script парсер вырезает и складывает отдельно, дабы пользователь парсера сам решил казнить их или помиловать что с ними дальше делать. Можно, например, сделать eval у скриптов. А вот что делать со стилями — вопрос неясный даже для меня. Единственное, что не учтено в моей реализации — это хитрая возможная структура этих тегов. Скажем, если в script-е у вас встречается текст в духе return '</script>';, то парсер по ошибке распознает оный как закрытие тега script, что неприятно, однако легко чинится , просто мне лень.

Высчитываем разницу

Итак, на текущем этапе мы имеем годный HTML-парсер, которому можно передать кусок HTML-я и распарсить его в реальные DOM-элементы, или же в VDOM-элементы. Это просто прекрасно.
Теперь представьте, что у нас уже отрисован на экране какой-то HTML, мы хотим его незначительно поменять. Берём его, вносим коррективы, скармливаем парсеру с VDOM-конструктором. Получаем список VDOM-нод. Теперь нам надобно высчитать разницу между HTML-ем, который отрисован на экране и тем, что нам напарсил наш парсер. По сути дела надо взять parent-нод, внутри которого отрисован наш HTML, взять массив всех его детей и сравнить его с аналогичным массивом виртуальных детей, который нам создал HTML-парсер. И когда я говорю "сравнить" — я имею в виду не просто ответить на вопрос "совпадают или нет", но и сгенерировать т.н. "update batch" — список какие элементы куда надо добавить, а какие откуда удалить чтобы из старого куска дерева получить новое. После чего, полученная пачка изменений просто накатывается на уже отрисованный HTML, не уничтожая уже отрисованное и неизменённое, но умно меняя только затронутые ноды. Называется эта операция VDOM update. Вот как-то так. Но, обо всём по порядку.

Кэш сравнений

Для начала надо научиться сравнивать HTML-ноды и VDOM-ноды. Делается это относительно просто:

1. Сравниваем типы. Если не совпадает — ноды разные
2. Если обе ноды текстовые или комментарии — сравниваем контент. Совпадает? Одинаковые. Не совпадает? Разные.
3. Сравниваем количество атрибутов. Не совпадает? Разные.
4. Содержательно сравниваем наличие атрибутов и их значения. Что-то не совпало? Ну вы поняли.
5. Проделываем шаги 1-4 для каждой ноды-потомка.
6. Если вы это читаете, значит ноды всё-таки совпадают.

Как можно заметить, каждый раз с нуля сравнивать ноды — это трудозатратно. Во многом из-за рекурсии на 5 шаге. Поэтому я сделал кэш-компаратор, который живет в рамках одного update-а и хранит результаты сравнений нод друг с другом. Таким образом, если тот факт, что два нода — разные уже когда-то был установлен, то он не устанавливается заново, а берется из кэша. Много однотипного кода.

LCS

Это сокращение от "Longest Common Subsequence". Этот класс по сути представляет собой матрицу для решения LCS-задачи методом динамического программирования. Мы ему даём на вход два массива — один из реальных нод, другой — из виртуальных, так же скармливаем кэш сравнений, про который я рассказал выше. Дальше, вызываем produceModifyBatch и получаем массив batch entries (описаны в самом низу), который по сути говорит что надо сделать с такой-то по счету нодой — обновить, удалить, или вставить другую (и какую именно) ноду ПЕРЕД ней.

Первым делом после вызова produceModifyBatch, LCS урезает одинаковые элементы с начала и с конца массивов (функция doSkips). Далее на оставшихся данных стоится матрица динамического программирования — точно так, как объясняется вот в этом видео. Затем оную обходят, определяя какие ноды надо удалить, а какие — добавить (тоже описано в видео). Обратите внимание, что на этом этапе мы не получаем список нод, которые надо обновить. Результат содержит только удаления-добавления, но! Но удаление-добавление ноды в одно и то же место (или добавление-удаление) — это и есть обновление. Операция normalizeBatch как раз и делает, что схлопывает рядом стоящее добавление-удаление в одну операцию — обновление, переформатируя первичный массив batch entry-ев. Полученный результат, наконец, можно вернуть счастливому пользователю.

LCS — и есть самое сложное в VDOM-е, из-за чего многим он кажется страшной магией. Как видите, сам алгоритм, что называется, tricky, но вполне себе понимаемый. Сложность его, кстати, квадратичная, но бояться нечего. Если изменений относительно мало и они где-то в середине пачки элементов — большинство отсекается на стадии doSkips и в результате матрица динамического программирования нечасто превышает по размерам 3x3. Конечно же, если ваши пользователи не перерисовывают 10 тысяч кнопочек, стоящих друг под другом. На практике такие случаи происходят редко. Так что имеет смысл не строить LCS-матрицу, если у вас 2 или 1 элемент, а обработать результат "руками". Гораздо чаще в реальной жизни встречается большая вложенность элементов, если на то пошло. Но, однако, недостаточная чтобы сорвать стек вызовов в JS (у нас дальше будет рекурсивная обработка). Вот так и живём. Не знаю, возможно тот же React.js пошел ещё дальше в оптимизации этого процесса — я его исходники не читал. Кто знает — отпишитесь. Все мои задачи же вписываются в означенные ограничения с огромным запасом.

Материализатор и DOM Differ

Наконец, пишем метод update, который заменяет потомков выбранного нами parent-элемента, через LCS-сравнение, на полученный от HTML-парсера массив виртуальных нод. Тут нам, очевидно, понадобится материализатор нод — штукенция, которая превращает виртуальную ноду в реальную. Без комментариев.

И создать кэш сравнений заранее! И животноводство!

Сам update: берем потомков parent-а, берем массив VDOM-нод. Создаем LCS, получаем update batch. Меланхолично проходим по нему, собираем всех, кого надо добавить в один массив, всех, кого надо удалить — в другой. Всех, кого надо обновить — сначала обновляем список аттрибутов несложной функцией updateAttributes, а потом рекурсивно применяем тот же самый метод update, который мы в настоящий момент и описываем (предварительно, достав массив потомков из VDOM-ноды-донора). В итоге: всех, кого надо добавить — прогоняем через материализатор, делаем parent.insertBefore. Всех, кого надо удалить — делаем parent.removeChild. Упражнение закончено. Код вот тут.

Для дебага я ещё добавил функцию diff, которая выводит в консоль содержимое update batch-а. Однако, на практике её вывод несколько сложен для понимания.

Все вместе

Создаем простенький HTML-документ с бутстраповскими стилями, создаем app.ts, из которого и задействуем нашу прекрасную наработку для демонстрации.

Итоги

Вы прочли статью о том, как устроен VDOM. Надеюсь, после такого экскурса, у вас появится больше понимания зачем оно надо и как оно устроено, исчезнет страх перед неизвестным и вы будете немного больше ориентироваться в происходящем внутри модных JS-фреймворков. Кому-то, возможно, понравится компактный HTML-парсер — забирайте, я не возражаю.

Всем спасибо за прочтение, комментарии приветствуются.