Разрабатываем свой браузер с нуля. Часть первая: HTML22.11.2018 14:02

Всем привет!

Продолжаем цикл статей по разработке браузерного движка.

В данной статье я расскажу как создать самый быстрый HTML-парсер c DOM. Мы рассмотрим HTML спецификацию и чем она плоха относительно производительности и потребления ресурсов при разборе HTML.

С данной темой я докладывался на прошедшем HighLoad++. Конференцию не каждый может посетить, плюс в статье больше деталей.

Я предполагаю, что читатель обладает базовыми знаниями об HTML: теги, ноды, элементы, пространство имён.

Спецификация HTML

Прежде чем начать хоть как-то затрагивать реализацию HTML-парсера необходимо понять какой HTML спецификации верить.

Существует две HTML спецификации:

WHATWG
- Apple, Mozilla, Google, Microsoft
W3C
- Большой список компаний

Естественно, выбор пал на лидеров отрасли — WHATWG. Живой стандарт, большие компании у каждой из которых есть свой браузер/браузерный движок.

Процесс парсинга HTML

Процесс построения HTML дерева можно разделить на четыре части:

Декодер
Предварительная обработка
Токенизатор
Построение дерева

Рассмотрим каждую стадию по отдельности.

Декодер

Токенизатор принимает на вход юникод символы (code points). Соответственно, нам необходимо конвертировать текущий байтовый поток в юникод символы. Для этого необходимо воспользоваться спецификацией Encoding.

Если мы имеем HTML с неизвестной кодировкой (нет HTTP заголовка) то нам необходимо её определить до начала декодирования. Для этого мы воспользуемся алгоритмом encoding sniffing algorithm.

Если очень кратко то суть алгоритма сводится к тому, что мы ждем 500мс или первые 1024 байта из байтового потока и запускаем алгоритм prescan a byte stream to determine its encoding который пробует найти тег с атрибутами http-equiv, content или charset и пытается понять какую кодировку указал разработчик HTML.

В спецификации Encoding ороваривается нимнимальный набор поддерживаемых кодировок браузерным движком (всего 21): UTF-8, ISO-8859–2, ISO-8859–7, ISO-8859–8, windows-874, windows-1250, windows-1251, windows-1252, windows-1254, windows-1255, windows-1256, windows-1257, windows-1258, gb18030, Big5, ISO-2022-JP, Shift_JIS, EUC-KR, UTF-16BE, UTF-16LE и x-user-defined.

Предварительная обработка

После того как мы декодировали байты в юникод символы нам необходимо провести «зачистку». А именно, заменить все символы возврата каретки (\r) за которыми следует символ перевода строки (\n) на символ возврата каретки (\r). Затем, заменить все символы возврата каретки на символ перевода строки (\n).

Так описано в спецификации. То есть, \r\n => \r, \r => \n.

Но, на самом деле так никто не делает. Делают проще:
Если попался символ возврата каретки (\r) то смотрим есть ли символ перевода строки (\n). Если есть то меняем оба символа на символ перевода строки (\n), если нет то меняем только первый символ (\r) на перевод строки (\n).

На этом предварительная обработка данных завершена. Да, всего-то надо избавиться от символов возврата каретки, чтобы они не попадали в токенизатор. Токенизатор не ожидает и не знает, что делать с символом возврата каретки.

Ошибки парсинга

Чтобы в дальнейшем не возникало вопросов стоит сразу рассказать, что такое ошибка парсинга (parse error).

На самом деле ничего страшного. Звучит грозно, но по факту это лишь предупреждение о том, что мы ожидали одно, а имеем другое.
Ошибка парсинга не остановит процесс обработки данных или построение дерева. Это сообщение которое сигнализирует, что у нас не валидный HTML.

Ошибку парсига можно получить за суррогатные пары, \0, неверное расположение тега, неверный и ещё всякие.

К слову, некоторые ошибки парсинга ведут к последствиям. К примеру, если указать «плохой» то HTML дерево будет помечен как QUIRKS и изменится логика работы некоторых DOM функций.

Токенизатор

Как уже было сказано ранее, токенизатор принимает на вход юникод символы. Это конечный автомат (state machine) который имеет 80 состояний. В каждом состоянии условия для юникод символов. В зависимости от пришедшего символа токенизатор может:

Поменять своё состояние
Сформировать токен и поменять состояние
Ничего не делать, ждать следующий символ

Токенизатор создает токены шести видов: DOCTYPE, Start Tag, End Tag, Comment, Character, End-Of-File. Которые поступают в стадию построения дерева.

Примечательно, что токенизатор знает не о всех своих состояниях, а где о 40% (взял с потолка, для примера). «Зачем же остальные?» — спросите вы. Об остальных 60% знает стадия построения дерева.

Это сделано для того, чтобы правильно парсить такие теги как </code></strong>, <strong><code><style></code></strong>, <strong><code><script></code></strong>, <strong><code><title></code></strong> и так далее. То есть, обычно те теги в которых мы не ожидаем других тегов, а только закрытие себя.</p> <p>К примеру, тег <strong><code><title></code></strong> не может содержать в себе других тегов. Любые теги в <strong><code><title></code></strong> будут восприниматься как текст пока он не встретит закрывающий тег для себя <strong><code></title></code></strong>.</p> <p>Зачем так сделано? Ведь можно было просто указать токенизатору, что если встретим тег <strong><code><title></code></strong> то идем по «нужному нам пути». И это было бы верно если не namespaces! Да, пространство имён влияет на поведение стадии построения дерева, которая в свою очередь меняет поведение токенизатора.</p> <p>Для примера, рассмотрим поведение тега <strong><code><title></code></strong> в HTML и SVG пространстве имен: </p> <p><strong>HTML</strong></p> <pre> <code class="html"><title><span>Текст</span></title></code> </pre> <p>Результат построения дерева: </p> <pre> <code class="plaintext"><title> "<span>Текст</span>"</code> </pre> <p><strong>SVG</strong></p> <pre> <code class="html"><svg><title><span>Текст</span></title></svg></code> </pre> <p>Результат построения дерева: </p> <pre> <code class="plaintext"><svg> <title> <span> "Текст"</code> </pre> <p>Мы видим, что в первом случаи (HTML namespace) тег <strong><code><span></code></strong> является текстом, не был создан элемент <strong><code>span</code></strong>. Во втором случаи (SVG namespace) на основе тега <strong><code><span></code></strong> был создан элемент. То есть, в зависимости от простарнства имени теги ведут себя по-разному.</p> <p>Но, это ещё не всё. Тортиком на этом «празднике жизни» служит тот факт, что сам токенизатор должен знать в каком пространстве имен находится стадия построения дерева. И нужно это исключительно для того, чтобы правильно обработать <strong><code>CDATA</code></strong>.</p> <p>Рассмотрим два примера с <strong><code>CDATA</code></strong>, два пространства имён: </p> <p><strong>HTML</strong></p> <pre> <code class="html"><div><![CDATA[ Текст ]]</div></code> </pre> <p>Результат построения дерева: </p> <pre> <code class="plaintext"><div> </code> </pre> <p><strong>SVG</strong></p> <pre> <code class="html"><div><svg><![CDATA[ Текст ]]</svg></div></code> </pre> <p>Результат построения дерева: </p> <pre> <code class="plaintext"><div> <svg> " Текст "</code> </pre> <p>В первом случаи (HTML namespace) токенизатор воспринял <strong><code>CDATA</code></strong> за комментарий. Во втором случаи токенизатор разобрал структуру <strong><code>CDATA</code></strong> и получил данные из неё. В общем, правило такое: если встречаем <strong><code>CDATA</code></strong> не в HTML пространстве имён то парсим его, иначе считаем за комментарий.</p> <p>Вот такая получается жёсткая связь между токенизатором и построением дерева. Токенизатор должен знать в каком пространстве имен сейчас находится стадия построения дерева, а стадия построения дерева может менять состояния токенизатора.</p><p> <br /></p> <h3>Токены</h3> <p>Ниже будут рассмотрены все шесть видов токенов создаваемых токенизатором. Тут стоит отметить, что все токены имеют подготовленные данные, то есть уже обработанные и «готовые к употреблению». Это значит, что все именнованные символьные ссылки (named character references), вроде <strong><code>©</code></strong>, будут преобразованы в юникод символы.</p><p> <br /></p> <h3>DOCTYPE Token</h3> <p>Токен DOCTYPE имеет свою структуру не похожую на остальные теги. Токен содержит в себе: </p><p> <br /></p> <ol><li>Имя</li> <li>Public-идентификатор</li> <li>System-идентификатор</li> </ol> <p>В современном HTML единственный правильный/валидный DOCTYPE должен иметь следующий вид: </p> <pre> <code class="html"><!DOCTYPE html></code> </pre> <p>Все остальные <strong><code><!DOCTYPE></code></strong> будут считаться ошибкой парсинга.</p><p> <br /></p> <h3>Start Tag Token</h3> <p>Открывающий тег может содержать в себе: </p><p> <br /></p> <ol><li>Имя тега</li> <li>Атрибуты</li> <li>Флаги</li> </ol> <p>К примеру, </p> <pre> <code class="html"><div key="value" /></code> </pre> <p>Открывающий тег может содержать флаг <strong><code>self-closing</code></strong>. Данный флаг никак не влияет на закрытие тега, но может вызвать ошибку парсинга для не void элементов.</p><p> <br /></p> <h3>End Tag Token</h3> <p>Закрывающий тег. Обладает всеми свойствами токена открывающего тега, но имеет перед именем тега косую <strong><code>/</code></strong>.</p> <pre> <code class="html"></div key="value" /></code> </pre> <p>Закрывающий тег может содержать флаг <strong><code>self-closing</code></strong> который вызовет ошибку парсинга. Так же, ошибку парсинга вызовут атрибуты у закрывающего тега. Они будут правильно распарсены, но выброшены на стадии построения дерева.</p> <p>Токен комментария содержит в себе весь текст комментария. То есть, он полностью копируется из потока в токен.</p> <p>Пример, </p> <pre> <code class="html"></code> </pre><p> <br /></p> <h3>Character Token</h3> <p>Пожалуй самый интересный токен. Токен юникод символа. Может содержать в себе один (только один) символ.</p> <p>На каждый символ в HTML будет создаваться токен и отправляться в стадию построения дерева. Это очень накладно.<br />Давайте рассмотрим как это работает.</p> <p>Возьмет HTML данные: </p> <pre> <code class="html"><span>Слава императору! ®</span></code> </pre> <p>Как вы думаете сколько будет создано токенов для приведенного примера? Ответ: 22.</p> <p>Рассмотрим список создаваемых токенов: </p> <pre> <code class="plaintext">Start tag token: <span> Character token: С Character token: л Character token: а Character token: в Character token: а Character token: Character token: и Character token: м Character token: п Character token: е Character token: р Character token: а Character token: т Character token: о Character token: р Character token: у Character token: ! Character token: Character token: End tag token: </span> End-of-file token</code> </pre> <p>Не утешительно, правда? Но, конечно, многие создатели парсеров HTML по факту имеет только один токен в процессе обработки. Пуская его по кругу и затирая каждый раз новыми данными.</p> <p>Забежим вперед и ответим на вопрос: зачем так сделано? Почему не брать этот текст единым куском? Ответ кроется в стадии построения дерева.<br />Токенизатор бесполезен без стадии построения HTML дерева. Именно на стадии построения дерева происходит склейка текста с разными условиями.</p> <p>Условия, примерно, такие: </p><p> <br /></p> <ol><li>Если пришел символьный токен с <strong><code>U+0000</code></strong> (<strong><code>NULL</code></strong>) то вызываем ошибку парсинга и игнорируем токен.</li> <li>Если пришёл один из <strong><code>U+0009</code></strong> (<strong><code>CHARACTER TABULATION</code></strong>), <strong><code>U+000A</code></strong> (<strong><code>LINE FEED (LF)</code></strong>), <strong><code>U+000C</code></strong> (<strong><code>FORM FEED (FF)</code></strong>) или <strong><code>U+0020</code></strong> (<strong><code>SPACE</code></strong>) character токен тогда вызвать алгоритм восстановить активные элементы форматирования и вставить токен в дерево.</li> </ol> <p>Символьный токен добавляется в дерево по алгоритму: </p><p> <br /></p> <ol><li>Если текущая позиция вставки это не текстовая нода, тогда создать текстовую ноду, вставить её в дерево и добавить к ней данные из токена.</li> <li>Иначе добавить данные из токена к существующей текстовой ноде.</li> </ol> <p>Это поведение создает много проблем. Необходимость на каждый символ создавать токен и отправлять на анализ в стадию построения дерева. Мы не знаем размер текстовой ноды и нам приходится либо заранее выделить много памяти, либо делать реалоки. Всё это крайне накладно по памяти, либо по времени.</p><p> <br /></p> <h3>End-Of-File Token</h3> <p>Простой и понятный токен. Данные закончились — сообщим об этом стадии построения дерева.</p><p> <br /></p> <h3>Построение дерева</h3> <p>Построение дерева — это конечный автомат имеющий <strong><code>23</code></strong> состояния с множеством условий для токенов (тегов, текста). Стадия построения дерева самая большая, занимает значимую часть спецификации, а так же способна вызывать летаргический сон и раздражение.</p> <p>Всё устроено очень просто. На вход принимаются токены и в зависимости от токена переключается состояние построения дерева. На выходе мы имеем настоящий DOM.</p><p> <br /></p> <h2>Проблемы? </h2> <p>Давольно очевидными выглядят следующие проблемы: </p> <p><strong>Посимвольное копирование</strong></p> <p>На вход каждое состояние токенизатора принимает по одному символу которые он копирует/конвертирует в случаи необходимости: имена тегов, атрибуты, комментарии, символы.</p> <p>Это очень расточительно как по памяти так и по времени. Мы вынуждены заранее выделить неизвестное количество памяти под каждый атрибут, имя тега, комментарий и так далее. А это, соответственно, ведет к реалокам, а реалоки ведут к потерянному времени.</p> <p>А если представить, что HTML содержит 1000 тегов, а в каждом теге хотя бы по одному атрибуту, то мы получим адски медленную работу парсера.</p> <p><strong>Символьный токен</strong></p> <p>Второй проблемой является символьный токен. Получается, что мы создаем токен на каждый символ и отдаём его в построение дерева. Построение дерева не знает сколько у нас будет этих токенов и не может сразу выделить память под нужное количество символов. Соответственно, тут все те же реалоки + постоянные проверки на присутствие текстовой ноды в текущем состоянии дерева.</p> <p><strong>Монолитность системы</strong></p> <p>Большой проблемой является зависимость всего от всего. То есть, токенизатор зависит от состояния построения дерева, а построение дерева может управлять токенизатором. И всему виной пространство имен (namespaces).</p><p> <br /></p> <h2>Как будем решать проблемы? </h2> <p>Далее я опишу реализацию HTML парсера в своём проекте Lexbor, а так же решения всех озвученных проблем.</p><p> <br /></p> <h3>Предварительная обработка</h3> <p>Убираем предварительную обработку данных. Обучим токенизатор понимать возврат каретки (<strong><code>\r</code></strong>) как пробельный символ. Таким образом он будет прокинут в стадию построения дерева где мы с ним и разберёмся.</p><p> <br /></p> <h3>Токены</h3> <p>Легким движением руки мы унифицируем все токены. У нас будет один токен на всё. Вообще, во всём процессе парсинга будет только один токен.</p> <p>Наш унифицированный токен будет содержать следующие поля: </p><p> <br /></p> <ol><li>Tag ID</li> <li>Begin</li> <li>End</li> <li>Attributes</li> <li>Flags</li> </ol> <p><br /></p> <h4>Tag ID</h4> <p>Мы не будем работать с текстовым представлением имени тега. Переводим всё в цифры. Цифры легко сравнивать, с ними легче работать.</p> <p>Создаём статическую хеш-таблицу из всех известных тегов. Создаём перечисление (enum) из всех известных тегов. То есть, нам нужно жестко назначить каждому тегу идентификатор. Соответственно, в хеш-таблице ключом будет имя тега, а значением записать из перечисления.</p> <p>Для примера: </p> <pre> <code class="cpp">typedef enum { LXB_TAG__UNDEF = 0x0000, LXB_TAG__END_OF_FILE = 0x0001, LXB_TAG__TEXT = 0x0002, LXB_TAG__DOCUMENT = 0x0003, LXB_TAG__EM_COMMENT = 0x0004, LXB_TAG__EM_DOCTYPE = 0x0005, LXB_TAG_A = 0x0006, LXB_TAG_ABBR = 0x0007, LXB_TAG_ACRONYM = 0x0008, LXB_TAG_ADDRESS = 0x0009, LXB_TAG_ALTGLYPH = 0x000a, /* ... */ }</code> </pre> <p>Из примера видно, что мы создали теги для <strong>END-OF-FILE</strong> токена, для текста, документа. Всё это ради дальнейшего удобства. Приоткрывая занавес скажу, что в ноде (<strong><code>DOM Node Interface</code></strong>) у нас будет присутствовать <strong><code>Tag ID</code></strong>. Сделано это для того, чтобы не делать два сравнения: на тип ноды и на элемент. То есть, если нам нужен <strong><code>DIV</code></strong> элемент то мы делаем одну проверку в ноде: </p> <pre> <code class="cpp">if (node->tag_id == LXB_TAG_DIV) { /* Best code */ }</code> </pre> <p>Но, можно конечно сделать и так: </p> <pre> <code class="cpp">if (node->type == LXB_DOM_NODE_TYPE_ELEMENT && node->tag_id == LXB_TAG_DIV) { /* Oh, code */ }</code> </pre> <p>Два нижних подчёркивания в <strong><code>LXB_TAG__</code></strong> нужны для того, чтобы отделить общие теги от системных. Иначе говоря, пользователь может создать тег с именем <strong><code>text</code></strong> или <strong><code>end-of-file</code></strong> и если мы потом будем искать по имени тега то никаких ошибок не возникнет. Все системные теги начинаются с символа <strong><code>#</code></strong>.</p> <p>Но всё же, нода может хранить текстовое представление имени тега. Для 98.99999% нод этот параметр будет равен <strong><code>NULL</code></strong>. В некоторых пространствах имён нам необходимо прописать префикс или имя тега с фиксированным регистром. К примеру, <strong><code>baseProfile</code></strong> в SVG namespace.</p> <p>Логика работы простая. Если мы имеем тег с чётко оговоренным регистром то: </p><p> <br /></p> <ol><li>Добавляем его в общую базу тегов в нижнем регистре. Получаем идентификатор тега.</li> <li>К ноде добавляем идентификатор тега и оригинальное имя тега в текстовом представлении.</li> </ol> <p><strong>Пользовательские теги (custom elements)</strong></p> <p>Разработчик может создавать любые теги в HTML. Так-как мы имеем в статической хеш-таблице только те теги о которых знаем, а пользователь может создать любые то нам нужна динамическая хеш-таблица.</p> <p>Выглядит всё очень просто. Когда к нам прийдет тег мы посмотрим есть ли он в статической хеш-таблицы. Если тега нет то посмотрим в динамической, если и там нет то увеличиваем счётчик идентификаторов на один и добавляем тег в динамическую таблицу.</p> <p>Всё описанное происходит на стадии токенизатора. Внутри токенизатора и после все сравнения идут по <strong><code>Tag ID</code></strong> (за редким исключением).</p><p> <br /></p> <h4>Begin and End</h4> <p>Теперь в токенизаторе у нас не будет обработки данных. Мы ничего не будет копировать и конвертировать. Мы просто берём указатели на начало и конец данных.</p> <p>Вся обработка данных, таких как символьные ссылки, будет происходить на стадии построения дерева.<br />Таким образом мы будем знать размер данных для последующего выделения памяти.</p><p> <br /></p> <h4>Attributes</h4> <p>Тут всё так же просто. Мы ничего не копируем, а просто сохраняем указатели на начало/конец имени и значения атрибутов. Все преобразования происходят в момент построения дерева.</p><p> <br /></p> <h4>Flags</h4> <p>Так как мы унифицировали токены нам надо как-то сообщить построению дерева о типе токена. Для этого используется битмап поле Flags.</p> <p>Поле может содержать в себе следующие значения: </p> <pre> <code class="cpp">enum { LXB_HTML_TOKEN_TYPE_OPEN = 0x0000, LXB_HTML_TOKEN_TYPE_CLOSE = 0x0001, LXB_HTML_TOKEN_TYPE_CLOSE_SELF = 0x0002, LXB_HTML_TOKEN_TYPE_TEXT = 0x0004, LXB_HTML_TOKEN_TYPE_DATA = 0x0008, LXB_HTML_TOKEN_TYPE_RCDATA = 0x0010, LXB_HTML_TOKEN_TYPE_CDATA = 0x0020, LXB_HTML_TOKEN_TYPE_NULL = 0x0040, LXB_HTML_TOKEN_TYPE_FORCE_QUIRKS = 0x0080, LXB_HTML_TOKEN_TYPE_DONE = 0x0100 };</code> </pre> <p>Помимо типа токена, открывающий или закрывающий, есть значения для конвертера данных. Только токенизатор знает как правильно конвертировать данные. Соответственно, токенизатор помечает в токене как данные должны быть обработаны.</p><p> <br /></p> <h4>Character Token</h4> <p>Из ранее описанного можно сделать вывод, что символьный токен у нас исчез. Да, теперь у нас есть новый тип токена: <strong><code>LXB_HTML_TOKEN_TYPE_TEXT</code></strong>. Теперь мы создаём токен на весь текст между тегами помечая, как его в дальнейшем надо обработать.</p> <p>Из-за этого нам прийдется изменить условия в построении дерева. Нам нужно обучить его работать не с символьными токенами, а с текстовыми: конвертировать, удалять ненужные символы, пропускать пробелы и так далее.</p> <p>Но, здесь ничего сложного нет. В стадии построения дерева изменения будут минимальны. А вот токенизатор теперь у нас не соответствует спецификации от слова совсем. Но, он нам и не нужен, это нормально. Наша задача получить HTML/DOM дерево полностью соответствующее спецификации.</p><p> <br /></p> <h3>Стадии токенизатора</h3> <p>Чтобы обеспечить высокую скорость обработки данных в токенизаторе мы в каждую стадию добавим свой итератор. По спецификации у нас каждая стадия принимает по одному символу и в зависимости от пришедшего символа принимает решения. Но, правда в том, что это очень затратно.</p> <p>К примеру, чтобы перейти от стадии <strong><code>ATTRIBUTE_NAME</code></strong> к стадии <strong><code>ATTRIBUTE_VALUE</code></strong> нам нужно найти пробельный символ в имени атрибута, что будет свидетельствовать об его окончании. По спецификации мы должны скармливать по символу в стадию <strong><code>ATTRIBUTE_NAME</code></strong> пока не встретиться пробельный символ, и эта стадия не переключится на другую. Это очень затратно, обычно это реализуют через вызов функции на каждый символ или колбека вроде «tkz→next_code_point ()».</p> <p>Мы же добавляем в стадию <strong><code>ATTRIBUTE_NAME</code></strong> цикл и передадим входящий буфер целиком. В цикле ищем нужные нам символы для переключения и продолжаем работу на следующей стадии. Тут мы получим много выигрыша, даже оптимизации компилятора.</p> <p>Но! Самое страшное, что мы тем самым сломали поддержку чанков (chunks) из коробки. Благодаря посимвольной обработки в каждой стадии токенизатора у нас была поддержка чанков, а теперь мы это сломали.</p> <p>Как исправить? Как реализовать поддержку чанков?! Всё просто, вводим понятия входящих буферов (Incoming Buffer).</p><p> <br /></p> <h3>Incoming Buffer</h3> <p>Часто HTML парсят кусками (chunks). Например, если данные мы получаем по сети. Чтобы не простаивать в ожидании оставшихся данных мы можем отправить на обработку/парсинг уже полученные данные. Естественно, данные могут быть «порваны» в любом месте. К примеру, имеем два буфера: </p> <p><strong>Первый</strong></p> <pre> <code class="html"><div clas</code> </pre> <p><strong>Второй</strong></p> <pre> <code class="html">s="oh-no-oh-no"></code> </pre> <p>Так как мы ничего не копируем на стадии токенизации, а только берем указатели на начало и конец данных то у нас появляется проблема. Указатели на разные пользовательские буфера. А учитывая тот факт, что разработчики часто используют один и тот же буфер для данных то мы имеем дело с указателем на начало несуществующих данных.</p> <p>Чтобы решить озвученные проблемы нам необходимо понимать когда данные из пользовательского буфера больше не нужны.<br />Решение очень простое: </p><p> <br /></p> <ol><li>Если мы парсим кусками то каждый входящий кусок мы копируем во входящий буфер (Incoming Buffer).</li> <li>После парсинга текущего куска (ранее скопированного) мы смотрим, а не остался ли какой нибудь незавершенный токен? То есть, присутствуют ли указатели на текущий пользовательский буфер в последнем токене. Если указатели отсутствуют то освобождаем входящий буфер, если нет то оставляем его до тех пор пока он нужен. В 99% случаев входящий буфер уничтожится при поступлении следующего куска.</li> </ol> <p>Флагом «копировать входящий буфер» можно управлять. Для цельных данных копирование не происходит.</p> <p>Конечно, данную логику можно оптимизировать и усложнить. Можно не копировать предварительно весь буфер, а после обработки скопировать только нужные (оставшийся хвост) данные и поменять указатель в токене на наш новый буфер. Получится всё лучше и быстрее. Но, данная оптимизация, на текущий момент, является преждевременной. Текущая реализация работает быстро и не затратно по памяти.</p><p> <br /></p> <h3>Проблема: данные в токене</h3> <p>С проблемой парсинга кусков мы разобрались, можно выдохнуть. Но, при нашем подходе хранения указателей возникает другая проблема: в определенный момент возникает необходимость посмотреть на данные в токене. Мы этого сделать не можем. Если мы будем заглядывать в данные токена то нам придётся склеивать их (если они из разных кусков), а это дико затратно по времени. В спецификации есть пару моментов когда надо посмотреть чего мы там накопили в токене.</p> <p>Решается данная проблема просто: добавлением дополнительных стадий обработки в токенизатор. То есть, мы заранее знаем когда будут проверки и можем пойти по разному пути обработки данных в токенизаторе.</p><p> <br /></p> <h2>Стадия построения дерева</h2> <p>Тут изменения минимальны.</p> <p>У нас больше нет символьных токенов, но зато появились текстовые. Соответственно, нам необходимо обучить стадию построения дерева понимать новый токен.</p> <p>Вот как это выглядит: </p> <p><strong>По спецификации</strong></p> <pre> <code class="cpp">tree_build_in_body_character(token) { if (token.code_point == '\0') { /* Parse error, ignore token */ } else if (token.code_point == whitespaces) { /* Insert element */' } /* ... */ }</code> </pre> <p><strong>В Lexbor HTML</strong></p> <pre> <code class="cpp">tree_build_in_body_character(token) { lexbor_str_t str = {0}; lxb_html_parser_char_t pc = {0}; pc.drop_null = true; tree->status = lxb_html_token_parse_data(token, &pc, &str, tree->document->mem->text); if (token->type & LXB_HTML_TOKEN_TYPE_NULL) { /* Parse error */ } /* Insert element if not empty */ }</code> </pre> <p>Из примера видно, что мы убрали все условия на проверку символов и создали общую функцию для обработки текста. В функцию передается аргумент с параметрами о том как преобразовывать данные: </p> <pre> <code class="cpp">pc.replace_null /* Заменить все '\0' на заменяющий символ (REPLACEMENT CHARACTER (U+FFFD)) */ pc.drop_null /* Удалить все '\0' */ pc.is_attribute /* Если данные являются значением атрибута то парсить их надо "с умом" */ pc.state /* Стадия обработки. Можно указать с парсингом символьных ссылок или без. */</code> </pre> <p>В каждой стадии построения дерева есть свои условия для символьных токенов. Где-то надо выкидывать <strong><code>\0</code></strong>, а где-то заменять их на <strong><code>REPLACEMENT CHARACTER</code></strong>. Где-то надо конвертировать символьные ссылки, а где-то нет. И все эти параметры могу как угодно комбинироваться.</p> <p>Конечно же, на словах всё звучит просто. По факту необходимо быть предельно внимательным. К примеру, все пробельные символы до начала тега <strong><code><head></code></strong> должны быть выброшены. Возникает проблема, если к нам прийдет текстовый токен у которого в начале пробелы, а дальше текст:», а тут текст ». Мы должны отрезать пробелы в начале текста и посмотреть не осталось ли там чего, если данные ещё остались то под видом нового токена продолжить обработку.</p><p> <br /></p> <div><strong>Смешной тег <sarcasm></strong> <div> <p>В HTML спецификации (в разделе построения дерева) говорится о теге <strong><code>sarcasm</code></strong>. Я видел не раз как разработчики парсеров слепо включали обработку этого тега.</p> <pre> <code class="plaintext">An end tag whose tag name is "sarcasm" Take a deep breath, then act as described in the "any other end tag" entry below.</code> </pre> <p>Писатели спецификации шутят.</p> </div> </div><p> <br /></p> <h2>Итог</h2> <p>После всех перестановок и манипуляций мы имеем самый быстрый и полноценный HTML парсер с поддержкой DOM/HTML Interfaces который строит HTML/DOM дерево полностью соответствующее HTML спецификации.</p> <p>Если суммировать всё то, что мы изменили: </p><p> <br /></p> <ol><li>Убирали предварительную обработку (перенесли в токенизатор)</li> <li>Токенизатор<br /><ul><li>Добавили Incoming Buffer</li> <li>Унифицировали токены</li> <li>Вместо имён Tag ID</li> <li>Символьный токен: не один, а N+ символов</li> <li>Свой итератор в каждом состоянии</li> <li>Обработка токена в построении дерева</li> <li>Один токен на всё</li> </ul></li> <li>Построение дерева<br /><ul><li>Модифицируем условия для символьных токенов</li> </ul></li> </ol> <p>На i7 2012 года, на одном ядре, мы имеем среднюю скорость парсинга 235MB в секунду (Amazon-страницы).</p> <p>Конечно же, я знаю как увеличить этот показатель в 1.5/2 раза, то есть запас ещё есть. Но, мне необходимо двигаться дальше. Собственно, а дальше парсинг CSS и создание собственного грамара (Grammar, то есть, генерация эффективного кода для парсинга по Grammar). В отличии от парсинга HTML, парсинг CSS намного сложнее, там есть где «развернуться».</p><p> <br /></p> <h2>Исходники</h2> <p>Описанный подход парсинга и построения HTML дерева реализован в Lexbor HTML.</p><p> <br /></p> <h2>P.S.</h2> <p>Следующая статья будет о парсинге CSS и Grammar. Как обычно, статья будет на готовый код. Ждать где-то 6–8 месяцев.</p><p> <br /></p> <div><strong>Для тех, у кого есть время</strong> <div> <p>Не стесняйтесь помогать проекту. К примеру, если вы любите в свободное время писать документацию.<br />Не стесняйтесь поддерживать проект рублём (на другие валюты я тоже не обижусь). Об этом в личку.</p> </div> </div> <p>Спасибо за внимание! </p> <p class="copyrights"><span class="source">© <a target="_blank" rel="nofollow" href="https://habr.com/post/430736/?utm_campaign=430736">Habrahabr.ru</a></span></p> </div> <br>  <div style="padding-left: 20px;"> <script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-2514821055276660" crossorigin="anonymous"></script>  <ins class="adsbygoogle" style="display:block" data-ad-client="ca-pub-2514821055276660" data-ad-slot="1200562049" data-ad-format="auto"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script> </div>  <noindex> <div style="margin: 25px;" id="disqus_thread"></div> <script type="text/javascript"> var disqus_shortname = 'pcnewsru'; var disqus_identifier = '863717'; var disqus_title = 'Разрабатываем свой браузер с нуля. Часть первая: HTML'; var disqus_url = 'http://pcnews.ru/blogs/razrabatyvaem_svoj_brauzer_s_nula_cast_pervaa_html-863717.html'; (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script>   </noindex> </div> <br class="clearer"/> </div> <br class="clearer"/> <div id="footer-2nd"></div> <div id="footer"> <br/><br/> <ul class="horz-menu"> <li class="about"><a href="/info/about.html" title="О проекте">О проекте</a></li> <li class="additional-menu"><a href="/archive.html" title="Архив материалов">Архив</a> </li> <li class="additional-menu"><a href="/info/reklama.html" title="Реклама" class="menu-item"><strong>Реклама</strong></a> <a href="/info/partners.html" title="Партнёры" class="menu-item">Партнёры</a> <a href="/info/legal.html" title="Правовая информация" class="menu-item">Правовая информация</a> <a href="/info/contacts.html" title="Контакты" class="menu-item">Контакты</a> <a href="/feedback.html" title="Обратная связь" class="menu-item">Обратная связь</a></li> <li class="email"><a href="mailto:pcnews@pcnews.ru" title="Пишите нам на pcnews@pcnews.ru"><img src="/media/i/email.gif" alt="e-mail"/></a></li> <li style="visibility: hidden"> <noindex>  <script type="text/javascript"> var _tmr = window._tmr || (window._tmr = []); _tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()}); (function (d, w, id) { if (d.getElementById(id)) return; var ts = d.createElement("script"); ts.type = "text/javascript"; ts.async = true; ts.id = id; ts.src = (d.location.protocol == "https:" ? "https:" : "http:") + "//top-fwz1.mail.ru/js/code.js"; var f = function () { var s = d.getElementsByTagName("script")[0]; s.parentNode.insertBefore(ts, s); }; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "topmailru-code"); </script> <noscript> <div style="position:absolute;left:-10000px;"> <img src="//top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;" height="1" width="1" alt="Рейтинг@Mail.ru"/> </div> </noscript>  </noindex> </li> </ul> </div>    </div>  <div id="footer-adlinks"></div> <noindex> <script type="text/javascript"> document.write("<a rel='nofollow' href='//www.liveinternet.ru/click' "+ "target=_blank><img src='//counter.yadro.ru/hit?t45.6;r"+ escape(document.referrer)+((typeof(screen)=="undefined")?"": ";s"+screen.width+"*"+screen.height+"*"+(screen.colorDepth? screen.colorDepth:screen.pixelDepth))+";u"+escape(document.URL)+ ";"+Math.random()+ "' alt='' title='LiveInternet' "+ "border='0' width='1' height='1'><\/a>") </script>  <script type="text/javascript"> var _tmr = window._tmr || (window._tmr = []); _tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()}); (function (d, w, id) { if (d.getElementById(id)) return; var ts = d.createElement("script"); ts.type = "text/javascript"; ts.async = true; ts.id = id; ts.src = "https://top-fwz1.mail.ru/js/code.js"; var f = function () {var s = d.getElementsByTagName("script")[0]; s.parentNode.insertBefore(ts, s);}; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "topmailru-code"); </script><noscript><div> <img src="https://top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;position:absolute;left:-9999px;" alt="Top.Mail.Ru" /> </div></noscript>   <script type="text/javascript"> (function (d, w, c) { (w[c] = w[c] || []).push(function () { try { w.yaCounter23235610 = new Ya.Metrika({ id: 23235610, clickmap: true, trackLinks: true, accurateTrackBounce: true, webvisor: true, trackHash: true }); } catch (e) { } }); var n = d.getElementsByTagName("script")[0], s = d.createElement("script"), f = function () { n.parentNode.insertBefore(s, n); }; s.type = "text/javascript"; s.async = true; s.src = "https://mc.yandex.ru/metrika/watch.js"; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "yandex_metrika_callbacks"); </script> <noscript> <div><img src="https://mc.yandex.ru/watch/23235610" style="position:absolute; left:-9999px;" alt=""/> </div> </noscript>   <script type="text/javascript"> var sc_project=9446204; var sc_invisible=1; var sc_security="14d6509a"; </script> <script type="text/javascript" src="https://www.statcounter.com/counter/counter.js" async></script>  <script> (function (i, s, o, g, r, a, m) { i['GoogleAnalyticsObject'] = r; i[r] = i[r] || function () { (i[r].q = i[r].q || []).push(arguments) }, i[r].l = 1 * new Date(); a = s.createElement(o), m = s.getElementsByTagName(o)[0]; a.async = 1; a.src = g; m.parentNode.insertBefore(a, m) })(window, document, 'script', '//www.google-analytics.com/analytics.js', 'ga'); ga('create', 'UA-46280051-1', 'pcnews.ru'); ga('send', 'pageview'); </script> <script async="async" src="/assets/uptolike.js?pid=49295"></script> </noindex>   <script type="text/javascript" src="https://pcnews.ru/js/blockAdblock.js"></script> <script type="text/javascript" src="/assets/jquery.min.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.json.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.form.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.easing.1.2.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/effects.core.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/browser-sniff.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/scripts.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-utils.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-auth.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-fiximg.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-infobox.js"></script> </body> </html>