Разрабатываем свой браузер с нуля. Часть первая: HTML

qu3l02mug029as5w74y2zznn0yc.jpeg

Всем привет!

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

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

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

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


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

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

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


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

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


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

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


  1. Декодер
  2. Предварительная обработка
  3. Токенизатор
  4. Построение дерева

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


Декодер

Токенизатор принимает на вход юникод символы (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 состояний. В каждом состоянии условия для юникод символов. В зависимости от пришедшего символа токенизатор может:


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

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

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

Это сделано для того, чтобы правильно парсить такие теги как