Что такое браузер html

Но, это ещё не всё. Тортиком на этом «празднике жизни» служит тот факт, что сам токенизатор должен знать в каком пространстве имен находится стадия построения дерева. И нужно это исключительно для того, чтобы правильно обработать CDATA .

Рассмотрим два примера с CDATA , два пространства имён:

HTML

Результат построения дерева:

SVG

Результат построения дерева:

  " Текст "

В первом случаи (HTML namespace) токенизатор воспринял CDATA за комментарий. Во втором случае токенизатор разобрал структуру CDATA и получил данные из неё. В общем, правило такое: если встречаем CDATA не в HTML пространстве имён то парсим его, иначе считаем за комментарий.

Вот такая получается жёсткая связь между токенизатором и построением дерева. Токенизатор должен знать в каком пространстве имен сейчас находится стадия построения дерева, а стадия построения дерева может менять состояния токенизатора.

Токены

Ниже будут рассмотрены все шесть видов токенов создаваемых токенизатором. Тут стоит отметить, что все токены имеют подготовленные данные, то есть уже обработанные и «готовые к употреблению». Это значит, что все именнованные символьные ссылки (named character references), вроде &copy , будут преобразованы в юникод символы.

DOCTYPE Token

Токен DOCTYPE имеет свою структуру не похожую на остальные теги. Токен содержит в себе:

1. Имя
2. Public-идентификатор
3. System-идентификатор

В современном HTML единственный правильный/валидный DOCTYPE должен иметь следующий вид:

Все остальные будут считаться ошибкой парсинга.

Start Tag Token

Открывающий тег может содержать в себе:

Открывающий тег может содержать флаг self-closing . Данный флаг никак не влияет на закрытие тега, но может вызвать ошибку парсинга для не void элементов.

End Tag Token

Закрывающий тег. Обладает всеми свойствами токена открывающего тега, но имеет перед именем тега косую / .

Закрывающий тег может содержать флаг self-closing который вызовет ошибку парсинга. Так же, ошибку парсинга вызовут атрибуты у закрывающего тега. Они будут правильно распарсены, но выброшены на стадии построения дерева.

Comment Token

Токен комментария содержит в себе весь текст комментария. То есть, он полностью копируется из потока в токен.

Character Token

Пожалуй самый интересный токен. Токен юникод символа. Может содержать в себе один (только один) символ.

На каждый символ в HTML будет создаваться токен и отправляться в стадию построения дерева. Это очень накладно.
Давайте рассмотрим как это работает.

Возьмём HTML данные:

Слава императору! ®

Как вы думаете сколько будет создано токенов для приведенного примера? Ответ: 22.

Рассмотрим список создаваемых токенов:

Start tag 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: Character token: End tag token: End-of-file token

Не утешительно, правда? Но, конечно, многие создатели парсеров HTML по факту имеет только один токен в процессе обработки. Пуская его по кругу и затирая каждый раз новыми данными.

Забежим вперед и ответим на вопрос: зачем так сделано? Почему не брать этот текст единым куском? Ответ кроется в стадии построения дерева.

Токенизатор бесполезен без стадии построения HTML дерева. Именно на стадии построения дерева происходит склейка текста с разными условиями.

Условия, примерно, такие:

1. Если пришел символьный токен с U+0000 ( NULL ) то вызываем ошибку парсинга и игнорируем токен.
2. Если пришёл один из U+0009 ( CHARACTER TABULATION ), U+000A ( LINE FEED (LF) ), U+000C ( FORM FEED (FF) ) или U+0020 ( SPACE ) character токен тогда вызвать алгоритм восстановить активные элементы форматирования и вставить токен в дерево.

Символьный токен добавляется в дерево по алгоритму:

1. Если текущая позиция вставки это не текстовая нода, тогда создать текстовую ноду, вставить её в дерево и добавить к ней данные из токена.
2. Иначе добавить данные из токена к существующей текстовой ноде.

Это поведение создает много проблем. Необходимость на каждый символ создавать токен и отправлять на анализ в стадию построения дерева. Мы не знаем размер текстовой ноды и нам приходится либо заранее выделить много памяти, либо делать реалоки. Всё это крайне накладно по памяти, либо по времени.

End-Of-File Token

Простой и понятный токен. Данные закончились — сообщим об этом стадии построения дерева.

Построение дерева

Построение дерева — это конечный автомат имеющий 23 состояния с множеством условий для токенов (тегов, текста). Стадия построения дерева самая большая, занимает значимую часть спецификации, а так же способна вызывать летаргический сон и раздражение.

Всё устроено очень просто. На вход принимаются токены и в зависимости от токена переключается состояние построения дерева. На выходе мы имеем настоящий DOM.

Проблемы?

Давольно очевидными выглядят следующие проблемы:

Посимвольное копирование

На вход каждое состояние токенизатора принимает по одному символу которые он копирует/конвертирует в случаи необходимости: имена тегов, атрибуты, комментарии, символы.

Это очень расточительно как по памяти так и по времени. Мы вынуждены заранее выделить неизвестное количество памяти под каждый атрибут, имя тега, комментарий и так далее. А это, соответственно, ведет к реалокам, а реалоки ведут к потерянному времени.

А если представить, что HTML содержит 1000 тегов, а в каждом теге хотя бы по одному атрибуту, то мы получим адски медленную работу парсера.

Символьный токен

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

Монолитность системы

Большой проблемой является зависимость всего от всего. То есть, токенизатор зависит от состояния построения дерева, а построение дерева может управлять токенизатором. И всему виной пространство имен (namespaces).

Как будем решать проблемы?

Далее я опишу реализацию HTML парсера в своём проекте Lexbor, а так же решения всех озвученных проблем.

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

Убираем предварительную обработку данных. Обучим токенизатор понимать возврат каретки ( \r ) как пробельный символ. Таким образом он будет прокинут в стадию построения дерева где мы с ним и разберёмся.

Токены

Легким движением руки мы унифицируем все токены. У нас будет один токен на всё. Вообще, во всём процессе парсинга будет только один токен.

Наш унифицированный токен будет содержать следующие поля:

Tag ID

Мы не будем работать с текстовым представлением имени тега. Переводим всё в цифры. Цифры легко сравнивать, с ними легче работать.

Создаём статическую хеш-таблицу из всех известных тегов. Создаём перечисление (enum) из всех известных тегов. То есть, нам нужно жестко назначить каждому тегу идентификатор. Соответственно, в хеш-таблице ключом будет имя тега, а значением записать из перечисления.

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, /* . */ >

Из примера видно, что мы создали теги для END-OF-FILE токена, для текста, документа. Всё это ради дальнейшего удобства. Приоткрывая занавес скажу, что в ноде ( DOM Node Interface ) у нас будет присутствовать Tag ID . Сделано это для того, чтобы не делать два сравнения: на тип ноды и на элемент. То есть, если нам нужен DIV элемент то мы делаем одну проверку в ноде:

if (node->tag_id == LXB_TAG_DIV) < /* Best code */ >

Но, можно конечно сделать и так:

if (node->type == LXB_DOM_NODE_TYPE_ELEMENT && node->tag_id == LXB_TAG_DIV) < /* Oh, code */ >

Два нижних подчёркивания в LXB_TAG__ нужны для того, чтобы отделить общие теги от системных. Иначе говоря, пользователь может создать тег с именем text или end-of-file и если мы потом будем искать по имени тега то никаких ошибок не возникнет. Все системные теги начинаются с символа # .

Но всё же, нода может хранить текстовое представление имени тега. Для 98.99999% нод этот параметр будет равен NULL . В некоторых пространствах имён нам необходимо прописать префикс или имя тега с фиксированным регистром. К примеру, baseProfile в SVG namespace.

Логика работы простая. Если мы имеем тег с чётко оговоренным регистром то:

1. Добавляем его в общую базу тегов в нижнем регистре. Получаем идентификатор тега.
2. К ноде добавляем идентификатор тега и оригинальное имя тега в текстовом представлении.

Пользовательские теги (custom elements)

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

Выглядит всё очень просто. Когда к нам прийдет тег мы посмотрим есть ли он в статической хеш-таблицы. Если тега нет то посмотрим в динамической, если и там нет то увеличиваем счётчик идентификаторов на один и добавляем тег в динамическую таблицу.

Всё описанное происходит на стадии токенизатора. Внутри токенизатора и после все сравнения идут по Tag ID (за редким исключением).

Begin and End

Теперь в токенизаторе у нас не будет обработки данных. Мы ничего не будет копировать и конвертировать. Мы просто берём указатели на начало и конец данных.

Вся обработка данных, таких как символьные ссылки, будет происходить на стадии построения дерева.
Таким образом мы будем знать размер данных для последующего выделения памяти.

Attributes

Тут всё так же просто. Мы ничего не копируем, а просто сохраняем указатели на начало/конец имени и значения атрибутов. Все преобразования происходят в момент построения дерева.

Flags

Так как мы унифицировали токены нам надо как-то сообщить построению дерева о типе токена. Для этого используется битмап поле Flags.

Поле может содержать в себе следующие значения:

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 >;

Помимо типа токена, открывающий или закрывающий, есть значения для конвертера данных. Только токенизатор знает как правильно конвертировать данные. Соответственно, токенизатор помечает в токене как данные должны быть обработаны.

Character Token

Из ранее описанного можно сделать вывод, что символьный токен у нас исчез. Да, теперь у нас есть новый тип токена: LXB_HTML_TOKEN_TYPE_TEXT . Теперь мы создаём токен на весь текст между тегами помечая, как его в дальнейшем надо обработать.

Из-за этого нам прийдется изменить условия в построении дерева. Нам нужно обучить его работать не с символьными токенами, а с текстовыми: конвертировать, удалять ненужные символы, пропускать пробелы и так далее.

Но, здесь ничего сложного нет. В стадии построения дерева изменения будут минимальны. А вот токенизатор теперь у нас не соответствует спецификации от слова совсем. Но, он нам и не нужен, это нормально. Наша задача получить HTML/DOM дерево полностью соответствующее спецификации.

Стадии токенизатора

Чтобы обеспечить высокую скорость обработки данных в токенизаторе мы в каждую стадию добавим свой итератор. По спецификации у нас каждая стадия принимает по одному символу и в зависимости от пришедшего символа принимает решения. Но, правда в том, что это очень затратно.

К примеру, чтобы перейти от стадии ATTRIBUTE_NAME к стадии ATTRIBUTE_VALUE нам нужно найти пробельный символ в имени атрибута, что будет свидетельствовать об его окончании. По спецификации мы должны скармливать по символу в стадию ATTRIBUTE_NAME пока не встретиться пробельный символ, и эта стадия не переключится на другую. Это очень затратно, обычно это реализуют через вызов функции на каждый символ или колбека вроде «tkz->next_code_point()».

Мы же добавляем в стадию ATTRIBUTE_NAME цикл и передадим входящий буфер целиком. В цикле ищем нужные нам символы для переключения и продолжаем работу на следующей стадии. Тут мы получим много выигрыша, даже оптимизации компилятора.

Но! Самое страшное, что мы тем самым сломали поддержку чанков (chunks) из коробки. Благодаря посимвольной обработки в каждой стадии токенизатора у нас была поддержка чанков, а теперь мы это сломали.

Как исправить? Как реализовать поддержку чанков?! Всё просто, вводим понятия входящих буферов (Incoming Buffer).

Incoming Buffer

Часто HTML парсят кусками (chunks). Например, если данные мы получаем по сети. Чтобы не простаивать в ожидании оставшихся данных мы можем отправить на обработку/парсинг уже полученные данные. Естественно, данные могут быть «порваны» в любом месте. К примеру, имеем два буфера:

Первый

Второй

s="oh-no-oh-no">

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

Чтобы решить озвученные проблемы нам необходимо понимать когда данные из пользовательского буфера больше не нужны.
Решение очень простое:

1. Если мы парсим кусками то каждый входящий кусок мы копируем во входящий буфер (Incoming Buffer).
2. После парсинга текущего куска (ранее скопированного) мы смотрим, а не остался ли какой нибудь незавершенный токен? То есть, присутствуют ли указатели на текущий пользовательский буфер в последнем токене. Если указатели отсутствуют то освобождаем входящий буфер, если нет то оставляем его до тех пор пока он нужен. В 99% случаев входящий буфер уничтожится при поступлении следующего куска.

Флагом «копировать входящий буфер» можно управлять. Для цельных данных копирование не происходит.

Конечно, данную логику можно оптимизировать и усложнить. Можно не копировать предварительно весь буфер, а после обработки скопировать только нужные (оставшийся хвост) данные и поменять указатель в токене на наш новый буфер. Получится всё лучше и быстрее. Но, данная оптимизация, на текущий момент, является преждевременной. Текущая реализация работает быстро и не затратно по памяти.

Проблема: данные в токене

С проблемой парсинга кусков мы разобрались, можно выдохнуть. Но, при нашем подходе хранения указателей возникает другая проблема: в определенный момент возникает необходимость посмотреть на данные в токене. Мы этого сделать не можем. Если мы будем заглядывать в данные токена то нам придётся склеивать их (если они из разных кусков), а это дико затратно по времени. В спецификации есть пару моментов когда надо посмотреть чего мы там накопили в токене.

Решается данная проблема просто: добавлением дополнительных стадий обработки в токенизатор. То есть, мы заранее знаем когда будут проверки и можем пойти по разному пути обработки данных в токенизаторе.

Стадия построения дерева

Тут изменения минимальны.

У нас больше нет символьных токенов, но зато появились текстовые. Соответственно, нам необходимо обучить стадию построения дерева понимать новый токен.

Вот как это выглядит:

По спецификации

tree_build_in_body_character(token) < if (token.code_point == '\0') < /* Parse error, ignore token */ >else if (token.code_point == whitespaces) < /* Insert element */' >/* . */ >

В Lexbor HTML

tree_build_in_body_character(token) < lexbor_str_t str = ; lxb_html_parser_char_t pc = ; 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 */ >

Из примера видно, что мы убрали все условия на проверку символов и создали общую функцию для обработки текста. В функцию передается аргумент с параметрами о том как преобразовывать данные:

pc.replace_null /* Заменить все '\0' на заменяющий символ (REPLACEMENT CHARACTER (U+FFFD)) */ pc.drop_null /* Удалить все '\0' */ pc.is_attribute /* Если данные являются значением атрибута то парсить их надо "с умом" */ pc.state /* Стадия обработки. Можно указать с парсингом символьных ссылок или без. */

В каждой стадии построения дерева есть свои условия для символьных токенов. Где-то надо выкидывать \0 , а где-то заменять их на REPLACEMENT CHARACTER . Где-то надо конвертировать символьные ссылки, а где-то нет. И все эти параметры могу как угодно комбинироваться.

Конечно же, на словах всё звучит просто. По факту необходимо быть предельно внимательным. К примеру, все пробельные символы до начала тега должны быть выброшены. Возникает проблема, если к нам прийдет текстовый токен у которого в начале пробелы, а дальше текст: » а тут текст «. Мы должны отрезать пробелы в начале текста и посмотреть не осталось ли там чего, если данные ещё остались то под видом нового токена продолжить обработку.

Смешной тег

В HTML спецификации (в разделе построения дерева) говорится о теге sarcasm . Я видел не раз как разработчики парсеров слепо включали обработку этого тега.

An end tag whose tag name is "sarcasm" Take a deep breath, then act as described in the "any other end tag" entry below.

Писатели спецификации шутят.

Итог

После всех перестановок и манипуляций мы имеем самый быстрый и полноценный HTML парсер с поддержкой DOM/HTML Interfaces который строит HTML/DOM дерево полностью соответствующее HTML спецификации.

Если суммировать всё то, что мы изменили:

1. Убирали предварительную обработку (перенесли в токенизатор)
2. Токенизатор
   • Добавили Incoming Buffer
   • Унифицировали токены
   • Вместо имён Tag ID
   • Символьный токен: не один, а N+ символов
   • Свой итератор в каждом состоянии
   • Обработка токена в построении дерева
   • Один токен на всё
3. Построение дерева
   • Модифицируем условия для символьных токенов

На i7 2012 года, на одном ядре, мы имеем среднюю скорость парсинга 235MB в секунду (Amazon-страницы).

Конечно же, я знаю как увеличить этот показатель в 1.5/2 раза, то есть запас ещё есть. Но, мне необходимо двигаться дальше. Собственно, а дальше парсинг CSS и создание собственного грамара (Grammar, то есть, генерация эффективного кода для парсинга по Grammar). В отличии от парсинга HTML, парсинг CSS намного сложнее, там есть где «развернуться».

Исходники

Описанный подход парсинга и построения HTML дерева реализован в Lexbor HTML.

P.S.

Следующая статья будет о парсинге CSS и Grammar. Как обычно, статья будет на готовый код. Ждать где-то 6-8 месяцев.

Для тех, у кого есть время

Не стесняйтесь помогать проекту. К примеру, если вы любите в свободное время писать документацию.
Не стесняйтесь поддерживать проект рублём (на другие валюты я тоже не обижусь). Об этом в личку.