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


    Всем привет!


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


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


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


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


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


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


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


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

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


    UPDATE: К сожалению, приведенные ссылки на спецификации не открываются из России. Видимо, "эхо войны" с телеграмм.


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


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


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

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


    Декодер


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


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


    Если очень кратко то суть алгоритма сводится к тому, что мы ждем 500мс или первые 1024 байта из байтового потока и запускаем алгоритм prescan a byte stream to determine its encoding который пробует найти тег <meta> с атрибутами 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, неверное расположение тега, неверный <!DOCTYPE> и ещё всякие.


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


    Токенизатор


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


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

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


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


    Это сделано для того, чтобы правильно парсить такие теги как <textarea>, <style>, <script>, <title> и так далее. То есть, обычно те теги в которых мы не ожидаем других тегов, а только закрытие себя.


    К примеру, тег <title> не может содержать в себе других тегов. Любые теги в <title> будут восприниматься как текст пока он не встретит закрывающий тег для себя </title>.


    Зачем так сделано? Ведь можно было просто указать токенизатору, что если встретим тег <title> то идем по "нужному нам пути". И это было бы верно если не namespaces! Да, пространство имён влияет на поведение стадии построения дерева, которая в свою очередь меняет поведение токенизатора.


    Для примера, рассмотрим поведение тега <title> в HTML и SVG пространстве имен:


    HTML


    <title><span>Текст</span></title>

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


    <title>
        "<span>Текст</span>"

    SVG


    <svg><title><span>Текст</span></title></svg>

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


    <svg>
        <title>
            <span>
                "Текст"

    Мы видим, что в первом случаи (HTML namespace) тег <span> является текстом, не был создан элемент span. Во втором случае (SVG namespace) на основе тега <span> был создан элемент. То есть, в зависимости от пространства имени теги ведут себя по-разному.


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


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


    HTML


    <div><![CDATA[ Текст ]]></div>

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


    <div>
        <!--[CDATA[ Текст ]]-->

    SVG


    <div><svg><![CDATA[ Текст ]]></svg></div>

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


    <div>
        <svg>
            " Текст "

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


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


    Токены


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


    DOCTYPE Token


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


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

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


    <!DOCTYPE html>

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


    Start Tag Token


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


    1. Имя тега
    2. Атрибуты
    3. Флаги

    К примеру,


    <div key="value" />

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


    End Tag Token


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


    </div key="value" />

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


    Comment Token


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


    Пример,


    <!-- Комментарий -->

    Character Token


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


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


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


    <span>Слава императору! &reg;</span>

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


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


    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

    Не утешительно, правда? Но, конечно, многие создатели парсеров 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) как пробельный символ. Таким образом он будет прокинут в стадию построения дерева где мы с ним и разберёмся.


    Токены


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


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


    1. Tag ID
    2. Begin
    3. End
    4. Attributes
    5. Flags

    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). Например, если данные мы получаем по сети. Чтобы не простаивать в ожидании оставшихся данных мы можем отправить на обработку/парсинг уже полученные данные. Естественно, данные могут быть "порваны" в любом месте. К примеру, имеем два буфера:


    Первый


    <div clas

    Второй


    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 = {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 */
    }

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


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

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


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


    Смешной тег <sarcasm>

    В 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 месяцев.


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

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


    Спасибо за внимание!

    Поделиться публикацией

    Похожие публикации

    Комментарии 95
      +1
      Класс! Jscript движок на заметку — en.m.wikipedia.org/wiki/JerryScript
        0
        Спасибо, часто его советуют. Собственно, я начал сразу реализовывать DOM чтобы можно было уже сейчас начать прикручивать JS.

        Я смотрю, уже давно, в сторону V8. Но, проблемы с ним очевидны, меняется он исключительно под нужды хрома. На данный момент я не осилю свой JS движок, это фантастика. Как бы не кололось прийдётся взять чужое. Если денег найду то будет своё. Сейчас цель движок/расчёты/отрисовка.
          0
          У него потребление ресурсов очень маленькое, его развивает Самсунг… Вполне хороший движок.
          Удачи!
            0
            Интересно было бы поглядеть на сравнение производительности, хоть с тем же V8.
              +1

              Ресурсы да, но он очень медленный. Из-за того, что он позиционируется как встраиваемый и "лёгкий" он медленный. К тому же, он поддерживает только ECMA 5.1. В общем, хочется скорости и современности.

                0

                А SpiderMonkey?

                  0
                  У него лицензии MPL/GPL/LGPL. Не подойдёт.
                0
                Кстати, нет никакой информации о сборщике мусора, вполне может быть, что его и нет.
                UPD. Таки есть.
                jmem_pools_collect_empty(), jmem_run_free_unused_memory_callbacks()
                0
                меняется он исключительно под нужды хрома

                К сожалению, сейчас почти весь веб пишется «под нужды хрома». Думаю если возьмете V8 — ничего не потеряете.
              +1
              Если это продолжение цикла, то где же ссылка на предыдущие статьи?
                0

                Это вторая статья из цикла. Первую можно увидеть в моём аккаунте. Добавлю сегодня ссылку в статью.

                –1

                Не пробовали смотреть в сторону какого-нибудь другого языка вместо C? Например D в режиме BetterC. Бонусом должно быть ускорение времени компиляции проекта (к линковке, конечно, не относится).

                  0
                  Пробовал. Смотрел в сторону С++ и даже начинал писать на нём lexbor. Собственно, использовал его как Си с классами. От это идеи отказался, по своду причин.

                  Браузерный движок — это ОС, без преувеличений. Меня интересует скорость и ручное управление памятью. Плюс, обязательно встраиваемость в другие языки программирования. Не уверен, что D подходит для этого.
                    –6

                    C++ ооочень медленно компилируется, поэтому я даже не представляю как можно собирать проекты уровня Blink на домашней машине средней руки. D в режиме BetterC (это ключевой момент) как раз-таки очень хорошо должен вам подойти, просто гляньте на спеку: https://dlang.org/spec/betterc.html, там вообще нет рантайма кроме libc.


                    По сути это и есть C, только без заголовочных файлов (с модулями) и с разными очень удобными плюшками типа ranges, удобного foreach, array slices, RAII и т.д. Для ручного управления памятью никто не запрещает вызывать привычные malloc и free, либо подключить какие-то другие аллокаторы.


                    Сам D очень хорошо (полностью совместим) интерфейсится с C и чуть похуже с C++ (в основном из-за премудростей с интерфейсами и наследованием в классах), так что встраиваемость будет на отличном уровне.


                    Причина по которой я рекомендую именно D — в скорости компиляции оного референсным компилятором. Ни C, ни особенно C++, не смогут в такое просто из-за особенностей языка — наличие заголовочных файлов само по себе усложняет компиляцию.


                    Еще как вариант есть Rust, но у него со скоростью компиляции тоже вроде бы не все так хорошо (знатоки, поправьте, если что-то изменилось). Да и порог входа там тоже никто не отменял.

                      –3
                      Мне сложно что-то сказать. Что у него со скоростью работы? Насколько он эффективен? В Си не нужно городить отдельное АПИ, оно само собой получается, как для Си так и для С++. Компилятор Си есть для любой железки, хоть для микроволновки.

                      Си распространен настолько, что нет опасности, что его забросят или ключевые разработчики уйдут.
                      Си быстро компилируется. Да, если написать ядро линукса на плюсах то оно не соберётся никогда. По этому, я выбрал Си.
                        0
                        В принципе, про D это дельный совет, особенно если проект с нуля. Со скоростью работы у него всё номально, т.е. вполне сравнимо с C, эффективность это многопараметрическая штука. Скорость разработки: компиляция, модули. Синтаксис, (как многие говорят, и я тоже пришёл к такому выводу), наверное, лучшее что есть у С-подобных языков, просто кайф. (Не говоря про реальные фишки типа shared перенных, immutable типов, встроенных ассоциативных массивов, lazy аргументов, unittest'ов, pure функций, делегатов… )

                        Насчёт забросить, — да, вроде за 19 лет не забросили.
                        Что касается микроволновки, то это конечно перебор, но вот, например, для OpenBSD пока действительно нет компилятора D (ни DMD, ни GDC, ни LDC).

                        Причём здесь ядро Линукса, которое не соберётся на C++, и как из этого следует выбор C, я не совсем понял.
                          0

                          Скорость точно такая же как и в C/C++, так как бэкенды те же. Однако референсный компилятор оптимизирует хуже чем два других — LDC и GDC (с GCC бэкендом), а также не умеет в кросс-компиляцию, поэтому если нужны крутые оптимизации и микроволновки с чайниками, то собирать нужно через LDC, т.к. это компилятор на основе LLVM бэкенда (уже WASM даже работает). Но с ним и сама сборка будет медленнее, поэтому LDC в основном используют для продакшн билдов.
                          Вот вводная справка по компиляторам D: https://wiki.dlang.org/Compilers


                          Сам язык относительно недавно включили в состав GCC: https://www.opennet.ru/opennews/art.shtml?num=49546


                          Основатель и создатель языка — Уолтер Брайт: https://en.wikipedia.org/wiki/Walter_Bright
                          , он же создатель одного из самых первых полноценных компиляторов C++. С ним в паре работает Андрей Александреску — очень известный товарищ из мира C++. Также существует некоммерческая организация D Foundation, которая используется как раз для организации спонсорской помощи. С корпоративным уровнем у них там все достаточно серьезно, но все-таки сказывается отсутствие крупных спонсоров типа Google, Microsoft и т.д., но некоторые считают что это даже к лучшему.


                          Вот список организаций которые использовали или используют D: https://dlang.org/orgs-using-d.html


                          Самому языку на самом деле уже больше 10 лет, но у него сложная история. Популярным его не назовешь, но и умирать он точно не собирается (в виду наличия достаточно большой кодовой базы в некоторых крупных коммерческих проектах) и постепенно развивается, конечно не такими темпами как более попсовые Go и Rust.


                          Если надо собирать под какие-то специфические микроконтроллеры, то тут вы правы — лучше взять С, так как его компиляторы есть практически везде.


                          По эффективности же (для программиста) D превосходит оба языка из-за наличия в нем современных языковых средств, которые, кстати, C++ активно тащит в свои новые стандарты копируя их с D.


                          Тем не менее, в режиме BetterC у вас не будет замыканий, т.к. они требуют сборщика мусора, а также классов с их наследованием. Но т.к. у вас ручное управление памятью и в целом минимализм, то они вам и не нужны =D


                          Еще из недостатков можно отметить пока что слабую поддержку IDE, хотя она есть.


                          В общем рекомендую просто потратить пару дней и попробовать написать что-то что у вас уже написано на C, но только на подмножестве BetterC. Порог входа для вас будет нулевой (в виду практически полной совместимости с C), а приятных бонусов гораздо больше.


                          Можете пройти небольшой тур для ознакомления с общими принципами языка: https://tour.dlang.org/tour/ru/welcome/welcome-to-d


                          Одно могу точно сказать — попробовав D (даже в урезанном виде) потом будет очень больно слезать назад на C и C++.


                          Но если у вас есть какие-то специфические требования, то тут конечно лучше вам смотреть предметно самостоятельно, описать все в одном комментарии сложно. Может C в вашем случае действительно более подходящий выбор.

                            0
                            Спасибо вам за такой развёрнутый ответ!

                            Я посмотрю, для общего развития, на D. Но, данный проект (Lexbor) будет развиваться на Си.
                              +1

                              Да не за что! =)
                              D очень интересный язык с той точки зрения, что пытается исправить неудачные решения в C и C++ при этом не сдвигая целиком всю парадигму, как это делает, например, Rust.


                              Смотрю что Ваше предыдущее сообщение (да и мои тоже) уже успели заминусовать добрые посетители Хабра. Если что, то это не я. Обычно таким не занимаюсь =)


                              Всеми руками и ногами поддерживаю Ваше начинание! Сейчас в этой нише очень уж мало легковесных встраиваемых решений для рендеринга HTML. В приципе есть Sciter (его вроде уже упоминали), но он совсем не опен сорс и является платным для коммерческого использования.


                              Так что было бы здорово, если бы у Вас все получилось!

                          0
                          Почему вас настолько волнует скорость КОМПИЛЯЦИИ, а не выполнения? Так можно на каком-нибудь делфи писать начать с его однопроходным компилятором. Модульность проекта и инкрементальные сборки нивелируют неудобства связанные с ожиданием завершения сборки всего проекта.
                            0

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


                            Не совсем понимаю при чем здесь Delphi.

                              0

                              У компилятора Delphi относительно мало семантики и компиляция кода может происходить за один проход. Что собственно дает окололинейную скорость.
                              Опять же повторю — грамотная модульность проекта уменьшают количество юнитов для компиляции и облегчают тестирование этих самых модулей. Инкрементальная сборка при модульной же архитектуре позволят пересобирать не весь код, а только тот модуль который был непосредственно зацеплен. Так что время компиляции, особенно на том этапе, на котором находится автор статьи, не должно быть сколько-нибудь серьёзным препятствием для разработки.
                              Даже для такого жесткого компилятора как в Rust с его доказательным компилятором время компиляции не настолько большая проблема(теперь уже).

                      0
                      — del ---
                        +1
                        Любопытная статья. Автор проделал большую работу, за что заслуживает похвалы. Но
                        … что в первом случаи...

                        … благодаря обработки...

                        … есть пару моментов...

                        … к нам прийдет текстовый...

                        Может оттолкнуть многих (я, например, на каком-то подсознательном уровне не могу серьезно относиться к тексту, в котором неправильно склонены существительные). Попробуйте почистить статью от этого, так она станет намного лучше.
                          0
                          Я вас услышал.
                          0
                          Я от этой темы крайне далёк, но интересно, возможно ли это использовать для создания кросс-платформенной UI библиотеки? Некий такой аналог электрона, только без ненужных тяжелых штук. Плюс в том, что магией верстки владеет достаточно большое количество человек и интерфейсы себе можно заказать у первого попавшегося фрилансера.
                          А если возможно, то какие минусы? Они же должны быть, раз этого еще не сделали.
                            +1
                            Возможно. Но возможно в тот момент когда появиться CSS и Layout. Эта одна из целей — предоставить разработчикам весь функционал браузерного движка для создания нативных приложений. Что-то вроде Qt, но с другого боку.
                            Но, при этом, основная цель быстрый браузер.

                            Из минусов. За всё приходится платить. В основном памятью. Моя задача минимизировать это. Максимум скорости при минимальном потреблении ресурсов.

                            Ко мне обращался один из разработчиков UI для автомобилей. Мы обсуждали можно ли при минимальных затратах ресурсов использовать данный подход. Интерес к этому есть.

                            А не сделали это по простой причине — сложно. Не ради рекламы, но таких буйных как я мало. Посмотрите у кого есть свои браузерный движки. Даже у Яндекса его нет, они пользуют гугловский. Сложность колоссальная.
                              0
                              Понял, да, это будет безусловно круто. Если люди готовы использовать многожрущие скайпы и слаки на электроне ради единого UI, то ваша реализация явно в более выигрышной позиции окажется по части нативных приложений. Осталось дождаться, пока вы допишите, а кто-нибудь реализует для всего этого фреймворк.
                              Успехов вам, постараюсь поддержать проект чем смогу :)
                                0
                                Спасибо за поддержку!
                                  0

                                  На том же Qt можно единый UI писать. Вопрос лишь в удобстве, т.к. за этими фреймворками стоят разные языки программирования.

                                  0
                                  Ко мне обращался один из разработчиков UI для автомобилей.

                                  Не вижу тут пробоем с ресурсами. Например Mercedes Qt засунул.

                                    0
                                    По разговору, я понял, что любое удешевление компонентов экономит много денег. Ничего не могу сказать про Qt и Mercedes.
                                      0
                                      А в Qt при этом засунули CAN.
                                    +1
                                    А если возможно, то какие минусы? Они же должны быть, раз этого еще не сделали.

                                    Давно уже вроде сделали, насколько я помню интерфейс некоторых антивирусов написан на
                                    https://sciter.com/

                                      0
                                      Видел их сайт. Они, как я понимаю, делаю некую обрезанную версию движка для интерфейсов. Они платные, исходники можно получить по лицензии на год.

                                      У меня подход другой. Я создаю полноценный движок на Си с возможностью встраивать в любой язык программирования. Плюс, лицензия у меня очень свободная: Apache 2.0. То есть, использовать можно хоть где и хоть как.
                                        0
                                        «Они» это я лично, т.е. без ансамбля.

                                        История создания Sciter: sciter.com/10-years-road-to-sciter

                                        «обрезанную версию движка для интерфейсов»

                                        Не сказал бы что обрезанная ибо HTML5 и CSS3 (избранные модули) поддерживаются практически в полном объеме.

                                        Вот «полноценный движок на Си» сделать действительно крайне сложно. С это не тот язык на котором такие вещи удобно писать.

                                        И желание «встраивать в любой язык программирования» тоже вызывает вопросы.
                                        Сейчас Sciter встраиваем в C/C++, C#, Rust, Python и Go. и написан на C++. Embedding API тот, да, plain C ибо другой альтернативы нет.

                                        Но на самом деле встраивание в язык это дело десятое. Вот встраивание в существующие десктоп системы и графику это важно.

                                        Сейчас Sciter может работать на Windows (XP … 10) c Direct2D/DirectWrite (DirectX), Skia (OpenGL) и GDI+ (прости мя сирого, хоспидя). На Mac — CoreGraphics и OpenGL(Skia), Linux/GTK (cairo или Skia). На подходе Andorid (OpenGL) и iOS (CoreGraphics или OpenGL).

                                        Skia и Direct2D это C++ и только. Ибо Skia можно интегрировать только в исходниках а это С++. А Direct2D это IUnknown со товарищи, т.е. C++ опять же.

                                        Без Skia и Direct2D (т.е. hardware acceleration) делать rendering engine можно и не начинать. 4K мониторы это наше все теперь. А на них только H/W acceleration — других опций и нет.

                                          0
                                          Привет!

                                          Об удобстве написания речь не идёт. Хотя, тут на вкус и цвет все фломастеры разные. Главное, чтобы использовать удобно было. Си именно даёт «Embedding API» из коробки. Не нужно делать двойную работу, проектировать дополнительный апи. Так же, все структуры видны. Я совершенно не противник плюсов, они мне даже нравятся, но данный проект именно на Си.

                                          Желание встроиться в любой язык программирования у меня не вызывает вопросов. Тут, как раз, всё прозрачно. Я отлично понимаю (в NGINX сейчас тем и занимаюсь) как писать сишные расширения для Python, Node.js, Perl, PHP, Ruby и имею представление о Go.

                                          Ну, слушайте, я вообще ещё не говорил о рисовалке. Тут, как говориться, ежу понятно, что она должна быть «hardware acceleration». Не открывая гугл, Skia вроде хром и лиса пользуют, говорят очень быстрая.

                                          На данный момент стоит задача создания дерева отрисовки. Все расчеты, перерасчёты и так далее. При этом, делать всё это максимально быстро. Без рисования вообще. Но, сразу скажу, есть чёткое понимание как всё делать. Обсуждение бекенда рисовалки идёт постоянно. Приоткрывая занавес: у меня уже есть свой движок, всё что я выкладываю в публичный доступ это чистовик, черновик так и останется у меня.

                                          P.S.:
                                          Тысяча извинений. Из вашего сайта не понятно, что поддерживается, а что нет. Складывается впечатление, что как-то обрезано.

                                          При этом, наши дороги немного расходятся. Не знаю насколько выгодно продавать лицензии, но я делаю open source, а деньги извлекать буду другим методом. Да и речь тут даже не о деньгах.
                                            0
                                            «но данный проект именно на Си.»

                                            Не ясна модель встраивания в другие языки. Поэтому и вопросы.
                                            Если бы ты (можно без «вы»?) определил изначально периметр встраивания (API другими словами) то было бы наверное более понятно что оно такое будет.

                                            Скажем весь Sciter API это вот эта структура github.com/c-smile/sciter-sdk/blob/master/include/sciter-x-api.h — там реально 40 функций (DOM related).
                                            Это чистые C functions хотя написаны на C++. И то на чем они написаны вообще никого не волнует. И не должно. Далеко не все «структуры» вообще могут быть выставлены наружу. Это банально опасно. Только контролируемый периметр.

                                            «есть чёткое понимание как всё делать»

                                            У меня было это состояние лет так 14 назад. И более того был реальный опыт создания WYSIWYG редакторов что близко к HTML (и там и там DOM, parsing и всё такое). Реальность как всегда оказалась несколько далека от изначальной теории.

                                            Как я понимаю до слов harfbuzz (и вообще RTL), writing script itemizer and shaper, и прочая ты еще не добрался. (сужу по описанной структуре parser. Кому нужны эти «Character token» и что это вообще?)

                                            «я вообще ещё не говорил о рисовалке.» и "… дерева отрисовки. Все расчеты, перерасчёты и так далее."

                                            Ну да, теоретически ты можешь рассчитать положение примитивных прямоугольных блоков, но для glyph positioning придется учитывать такие вещи как ClearType и другие механизмы которые доступны на конкретных платформах и которые являются частью rendering механизма. Это суровая практика, сиречь необходимость. Без понятия архитектуры rendering с самого начала и как те glyphs оказываются в GPU памяти что-то практическое сделать невозможно.

                                            И еще, я ни в коем случае не хочу тут рисовать картину маслом «Умерщвление прекрасной гипотезы мерзким фактом». Можно написать HTML/CSS/script engine и одному, собственно sciter есть тому подтверждение. Но нужно изначально определить «а user кто?». Для чего это всё? Т.е. почему проект который сейчас использует WebKit или Sciter должен перейти на твой движок?

                                            Если это для того чтобы сделать что-то типа HTML-to-PDF утилиты, то это одно. Для UI же… С его анимациями и рисованием на 4K мониторе full screen и c 60 FPS это совсем другое — как минимум layout engine должен взаимодействовать с rendering engine чтобы получать вектора glyphs и прочая. DrawText примитивы уже не работают на таких потоках данных и скоростях.

                                            И еще по поводу языка. Sciter написан на «C c классами» по большому счету. Ибо это удобно — т.е. позволяет быстрее и что главное надежнее писать. (Sciter примерно 100 тыс LOC). Это всё важно для one-man-project. А Mozilla вообще пилит Rust для того чтобы писать Servo — ручное управление памятью для проектов такого масштаба даже для них оказалось суровой задачей.

                                            И по поводу Open Source. Не советую обольщаться на эту тему.
                                            Есть два типа проектов: небольшие утилиты и что-то типа Electron. Первые имеют смысл для Open Source. Вторые же… Ну вот реально никого не парит что там внутри — реально количество людей которые лезут в детали WebKit или Gecko исчисляется десятками на всём шарике. И вот собственно и вся аудитория для open-sourse-ности проектов такого уровня. Тем более в свете последних скандалов с NPM ( в Microsoft Visual Code пролезла закладка которая тырит Bitcoins ) народ оченно печально настроен.

                                            То что мы видим в OpenSource это верхушка айсберга. Реально же 90% софта это проекты по месту — внутренних IT отделов компаний. Да и те же китайцы. Любят они OpenSource. Но вот не знаю ни одного OS проекта финансируемого ими. Нет таких. Не потому что они такие-сякие, а потому что через их firewall такие платежи не сделать. Да и вообще поток статей типа FOSS is free as in toilet в последнее время оптимизма никак не внушает.

                                              0

                                              Весь комментарий основан на предположениях и доводах. Я понимаю, что тебе что-то было очень сложно сделать, отрывки этого я вижу в твоих комментариях. Ты пишешь очевидные вещи. Ещё раз, движок есть, пишется чистовик. По мере написания компонентов будут выходить статьи. И будут статьи о всё "сексе" с глифами, расчетами.


                                              Так же, я веслом не ударен, чтобы строить наивные предположения, что щас вот героически всех… Если посмотреть в мой профиль, то можно понять, что этим я занимаюсь больше 5 лет.


                                              Про open source. Я работаю в компании которая занимается этим самым опен-сорсом — NGINX. Я чётко представляют, что это такое. Иллюзий нет, вообще, нет и не было. Мой проект есть и будет под лицензией Apache 2.0.


                                              Чувак, как ты парсер то писал хтмл? Character token. Шучу :)


                                              Статья про быстрый парсинг. Остальное будет.


                                              И в завершении. Я реально рад, что есть такие проекты как ваш. Ваш проект придаёт уверенности и сил сделать свой движок. Некий буст.
                                              Я вполне рад пообщаться с вами вне хабра. Всё же, почти, одно дело делаем.

                                      0
                                      А если возможно, то какие минусы? Они же должны быть, раз этого еще не сделали.

                                      0

                                      Как только вышла GraalVM, первое что пришло на ум — на ее основе получился бы не плохой полиглот-браузер. Что если ее взять за основу?

                                        0
                                        Я не знаком с GraalVM.
                                        Смотря на их сайт, я не могу придумать как там привинтить браузер.
                                          0
                                          Через GraalVM можно привинтить ваши парсеры к джаве, а затем всё собрать в нативный бинарник под нужную ОС.
                                            0
                                            А в части интерпретации клиентского языка, который во всех браузерах по умолчанию js, дать возможность писать клиентский код на любом языке, который может интерпретировать сама GraalVM. Таким образом, пользователь сможет открывать как обычные сайты html/js, так и сайты с использованием других клиентских технологий.
                                              0
                                              Этого нет в стандарте, поэтому не будет пользоваться популярностью. К тому же wasm 2.0 пилят.

                                              Единственно, можно для PWA эту фичу сделать, но здесь нужен экономичный к ресурсам движок, иначе можно и на хроме делать с транспилерами.
                                        0

                                        Мне интересно что за компания, платит деньги за подобные "разработки"?

                                          +1
                                          Вы так говорите, будто это что-то плохое.
                                          Никто не оплачивает. Голый, прям обнаженный, энтузиазм и слабоумие!

                                          Если серьёзно. Делаю в свободное от работы время. Если найдется тот кто будет оплачивать подобные разработки — будет очень круто. Но пока вот так.
                                          +2
                                          Я конечно всё понимаю, но называть свой проект Lexbor… Дааа, это жестко
                                            0
                                            В чём проблема? В чём жёсткость?
                                              0
                                              Тоже не понимаю. Может созвучие какое-нибудь на анлийском не подходящее.
                                                0
                                                Состоит оно из двух слов
                                                1) lex — лексический (lexical). В линуксе даже программа такая есть, так и называется lex (лексический анализатор). Потому, что в браузерном движке много парсинга: html, css, font, url, js много всего.

                                                2) bor — думаю тут и так всё ясно. Транслит нашего слова бор. Лесной бор. В начале хотел назвать lextree. Но потом, подумав, выбрал lexbor.

                                                И уже потом, я осознал, что на GitHub у меня аккаунт lexborisov. То есть, начало от lexbor. В общем, сам Бог велел. Так и оставил.
                                          0
                                          Это конечно мои придирки, но как-то звучит не очень понятно «лексбор», lextree как раз более тематически. Раз уж это два сокращения (лексический и лесной бор), то логично было бы писать LexBor, ну и писать Lex(сокращение английского слова) + транслит русского, тоже самое, что 語彙бор. Ну и обычно выбирают простые и запоминающиеся имена своим проектам, которые будут легки на слуху у конечного пользователя. К примеру какое нибудь животное или название любого объекта, который будет ассоциироваться с вашим браузером.
                                            0
                                            Тут всем не угодишь. Lexbor — это браузерный движок. Браузер, если до него доползу, будет иметь другое название.

                                            При этом, вы сильно утрируете (доводите до абсурда), вы бы ещё, для примера, объединили арабскую вязь и иероглифы.
                                              0
                                              Строгих правил в наименовании нет. Возьмите хотя бы «Авито»
                                              thequestion.ru/questions/47962/pochemu-avito-nazyvaetsya-avito
                                              Вообще никакого смысла не было.
                                                0
                                                Ясный пень, что никто не заставляет давать имя по определённым правилам и с любым названием можно развиваться, как «Авито», который вы привели в пример. Разница лишь в том, что один продукт грубо говоря называется «Internet explorer» (отлично имя, запоминающееся и отображающее суть продукта, что скорее всего сыграет на раскрутке браузера) или «Снег»/«Камень»(вообще никак не соотносится с браузером, которое скорее «прячет» браузер от потенциального пользователя).
                                                Вообще хорошее имя и логотип довольно сильно сказываются на впечатлении пользователя. Хотя об этом рановато думать =)
                                                  0
                                                  А все зависит от того как пользователю эту информацию подать, я думаю .)

                                                  Давайте про ваши примеры:
                                                  Stein(Камень) — непробиваемый браузер
                                                  Schnee(Снег) — No hot bugs!

                                                  Да и логотип и название всегда можно поменять по мере необходимости.

                                                  PS. Кстати, The Rolling Stones — тоже не вижу никакой связи с музыкой, например.
                                              0
                                              Чтобы привлечь внимание нужно начинать с рендера. Парсерами внимание не привлечешь, вы только на них весь энтузиазм угрохаете, тем более на такую детальную проработку.
                                                +1
                                                Нельзя начать с рендеринга не имея адекватного HTML/CSS/Font парсера. Тут закладываются основы. Это в CSS можно какие-то части делать, а какие-то нет. Там много «вторичного».
                                                Энтузиазм не угрохается. Я занимаюсь этим не первый год.
                                                  –1
                                                  >Нельзя начать с рендеринга не имея адекватного HTML/CSS/Font парсера.
                                                  Можно.

                                                  >Тут закладываются основы.
                                                  Нет.

                                                  >Энтузиазм не угрохается. Я занимаюсь этим не первый год.
                                                  Ок. Просто визуальные вещи привлекают больше внимания. И если они есть в проекте, то лучше начинать с них.
                                                    +1
                                                    О Боги. Не буду спорить. Поверю вашему опыту в написании быстрых и эффективных браузерных движков.
                                                      0
                                                      Со своей стороны поверю вашему опыту «в написании быстрых и эффективных браузерных движков», на самом деле нет.
                                                        0
                                                        Просто для интереса, как вы себе представляете рендеринг не разобраного хтмл? Просто текст выводить?
                                                          0
                                                          Мы взяли [gumbo](https://github.com/google/gumbo-parser) и просто сделали рендер в той степени, в которой нам было нужно.
                                                            0
                                                            «Gumbo is an implementation of the HTML5 parsing algorithm» это буквально значит что у них есть парсер.
                                                              0
                                                              просто сделали рендер в той степени, в которой нам было нужно.

                                                              Какова эта степень этой простоты?


                                                              И CSS парсилку вы у кого-то взяли. Насколько быстро у вас всё это работает? Всё "органично" вписалось друг в друга? И работу со "сборкой мусора" вы написали. Он у вас динамически всё перерисовывает?


                                                              Речь идет о реализации быстрого браузерного движа. Если взять медленный и давно устаревший gumbo + прикрутить какой нибудь css парсер то речи о быстроте быть не может. Зачем писать рендеринг если вокруг все на соплях?

                                                                0
                                                                >Зачем писать рендеринг если вокруг все на соплях?
                                                                Затем, чтобы привлечь внимание к проекту. Еще раз — визуальные вещи привлекают больше внимания к проекту, чем какие-то непонятные парсеры. Или вам еще нужно разъяснять, почему важно внимание к проекту?

                                                                Когда привлечёте внимание, сделаете нормальные парсеры, хоть на ассемблере.
                                                                  0

                                                                  Внимание кого? Ответьте на этот вопрос.


                                                                  1. Разработчиков? Так если я сделаю все из говна и палок, при этом показывая как у меня что-то отрисовывается, люди использовать это не будут, это невозможно будет использовать. Потому как АПИ будет ломаться постоянно. Да и похвастаться чем? Скорость? Низким потреблением ресурсов? — нет, ничего этого не будет. Будут лишь какие-то огрызки, а потом чтобы привести эти огрызки в нормальный вид уйдёт ещё больше времени. Адаптировать чужое, часто, намного сложнее чем написать своё. Учитывая, что речь идёт именно о скорости.
                                                                  2. Инвесторов? Я разговаривал с ~5 инвесторами. Люди хотели вложить в проект деньги, в разработку. Речи о "покажи нам картинку и тогда мы поверим" не шло. Отказал всем по разным причинам. В основном из-за расхождения целей.

                                                                  Подход должен быть последовательный. Снизу вверх. Появляется новый модуль и его сразу же можно использовать. Использовать не только для браузерного движка, но и для других целей.

                                                                    –1
                                                                    >Внимание кого?
                                                                    Разработчиков, инвесторов и т.д.

                                                                    >Да и похвастаться чем?
                                                                    Не знаю, вы вот пока хвастаетесь быстрыми парсерами. Мне это не интересно, думаю другим разработчикам тоже. Этих парсеров валом, скорость там не самая важная вещь.

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

                                                                    Я бы, например, начал пробовать прикрутить ваш рендеринг к GraalVM и мне было бы неважно какой у вас там быстрый парсер. И из каких палок он сделан.

                                                                    >Я разговаривал с ~5 инвесторами.
                                                                    Могли бы разговаривать с большим количеством инвесторов, будь у вас хоть какой-то рабочий рендеринг.

                                                                    >Использовать не только для браузерного движка, но и для других целей.
                                                                    И многие используют ваш парсер?
                                                                      +1

                                                                      Я вас услышал.


                                                                      Если вам что-то не нужно, это не значит, что это не надо остальным.


                                                                      И многие используют ваш парсер?

                                                                      Много, даже деньги платят за биндинги и доработки. И благодарности, что вместо 20 серверов теперь используют 8. Смотрите на myhtml.

                                                                        0
                                                                        Для Java есть биндинги?
                                                                          0
                                                                          Нет. Я не видел. В Java свой мир. Там же, как мне сказали, всё должно быть на Java.
                                                                  0

                                                                  Для CSS katana. Из поддержки html ограничились тегами h1, h2, h3, h4, h5, h6, p, br, b, u, s, span, strong, img, a, pre, ul, ol, li, div, video, blockquote, i, em, sup, sub.
                                                                  В CSS ограничили до width, height, display, color, background, margin, padding, border, line-height, text-align, vertical-align, font-size, font-weight, text-decoration, cursor, word-wrap, list-style-type. Естественно выделение текста, событие клика по ссылке, ховер на ссылках. Сам посебе рендер не зависит от CSS/HTML парсера, он зависит от спецификаций как рендерить этот html.


                                                                  Зачем писать рендеринг если вокруг все на соплях?

                                                                  Почему на соплях? У нас не стоит цель написать свой браузер, мы хотим лишь иметь возможность в наших контролах использовать HTML. Это нормальное желание, когда люди пишут свой UI framework. В том же Qt не весь html поддерживается.

                                                                    0
                                                                    Сам посебе рендер не зависит от CSS/HTML парсера, он зависит от спецификаций как рендерить этот html.

                                                                    Зависит, ещё как зависит. Расчеты и отрисовка HTML это есть итоговый комплекс парсинга и преобразований. Даже поведение отрисовки меняется в зависимости от html и css. Как он может не зависеть? Вы можете начать писать Layout без html, css, font (парсинг, расчеты глифов)?


                                                                    То, что вы описали я могу сделать буквально сейчас используя свой Modest.

                                                                      0
                                                                      Как он может не зависеть?

                                                                      Позвольте поинтересоваться, как он может зависеть? С моей точки зрения в рендеринг должны просто скормиться готовые дерево элементов и стили, а откуда они взялись — распарсились или захардкодил кто-то или из какого-нибудь gumbo или результат манипуляции джаваскрипта с DOM (без innerHTML) — абсолютно неважно. (Я не претендую на богатый опыт «в написании быстрых и эффективных браузерных движков», так, интересующийся мимокрокодил)

                                                                0
                                                                >Просто для интереса, как вы себе представляете рендеринг не разобраного хтмл?
                                                                Делаете простейший парсер с отображением на ваши DOM структуры. Опять же DOM структуры для начала делаете простейшие, только самые важные поля и элементы. На этом делаете рендеринг. Привлекаете внимание. Допиливаете парсер и структуры до полной спецификации.
                                                                  0
                                                                  А сейчас как по вашему сделано? Сейчас реализован самый быстрый хтмл парсер из существующих с DOM. С основными DOM/HTML функциями в интерфейсам. При этом, интерфейсы используются все. Дальше, функции к всем существующим интерфейсам будут добавляться по мере надобности. Никто просто так не будет реализовывать все подряд функции DOM/HTML интерфейсов, это преждевременное занятие.

                                                                  В общем, я вас понял.
                                                                    –1
                                                                    По вашим сырцам в глубину не ходил. Но потратить год на парсеры это так себе затея. Простейший парсер с минимальными структурами можно месяца за два сделать. А вы, как я понял, уже год этим занимаетесь.

                                                                    Когда приступите к рендерингу, есть это в вашем роадмапе на ближайшее время?
                                                                      +1

                                                                      Ваше мнение очень важно для нас.
                                                                      Следите за обновлениями и всё узнаете.

                                                                        0
                                                                        Ок, но вы лучше на хабр пишите, а то за всем не уследишь )
                                                                      0
                                                                      Вот это вот парсер www.codeproject.com/Articles/14076/Fast-and-Compact-HTML-XML-Scanner-Tokenizer используется в моем Sciter (https://sciter.com). По тестам на то время это был самый быстрый вариант.

                                                                      Из отличительных черт — не аллоцирует память в процессе работы. В смысле вообще. Классический finite state automata — pull parser.
                                                        0
                                                        Решил попробовать реализовать одну идейку на данном парсере. Пошёл смотреть доки — их нет, ок. Пошёл смотреть примеры и тут я заметил, что названия тегов, атрибутов и их значений передаются в функцию с их размером. Серьёзно? =) Неужели нельзя было сделать подсчёт символ? Или такими способом достигается перформанс?
                                                          0

                                                          Разве нет? Или вот тут.


                                                          Документация не полная, и зачастую пишется "второпях", но она есть и соответствует действительности.


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

                                                          Абсолютно серьёзно. Данные у вас могут быть не зануленными.


                                                          Или такими способом достигается перформанс?

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

                                                            0
                                                            Документация, ок, просто увидел то, что issue открыли с просьбой запилить доки и оно до сих пор висит и в описании не нашёл. На счёт достижения безопасности таким образом, что-то сомнительно, только + 1 к способу прострелить себе ногу, коих в «C» и без того не мало
                                                              0

                                                              Вы сейчас серьёзно? Прострелить ногу от того, что явно передаёшь размер данных?
                                                              Скажите это ребятам из MS, там вообще запрещают пользовать memcpy, заставляют использовать memcpy_s (с передачей размера). Смотрите описание.


                                                              В сях, правильным поведением является передача размера входных данных. Вы всегда можете сделать strlen() и компилятор оптимизирует.

                                                                0
                                                                Хорошо, я в «сях» нуб, может так оно и есть, но ставить в пример ребят из MS =) Я понимаю, что они в любом случае выше меня на несколько голов, только у них что-то постоянно проблемы возникают, особенно с ОС.
                                                                  0

                                                                  Блин, ну проблемы возникают у всех. А когда твоим продуктом пользуются N то любой малейший косяк сразу виден. Студия у них просто прекрасная, вообще у них много хорошего, чего вы их обижаете?! :)

                                                            0
                                                            Тесты, наверно, можно посмотреть еще.
                                                              0

                                                              Там есть документация, она на сайте. Выше написал об этом.
                                                              В тестах можно посмотреть, но лучше в доку или в примеры.

                                                            0
                                                            токенизатор принимает на вход юникод символы


                                                            А зачем всё переводить в Unicode?

                                                            50% (условно) в HTML именно markup. Зачем эти 50% через конвертор-то гонять?

                                                            Как-то это не согласуется с заявленной целью «самый быстрый HTML-парсер c DOM.»

                                                              0

                                                              Чувствую, что как-то общение между нами не задалось.
                                                              Вы читали спецификацию HTML? Птиченька-намёкенька.
                                                              Давайте почитаем как разные кодировки устроены. У вас точно HTML?
                                                              Но, в статье описано, более того, в коде можно посмотреть как реализовано у меня. Ещё Modest посмотрите (проект остановлен). Там, кстати, можно увидеть попытку с глифами и расчётом, наивную попытку.


                                                              Как-то это не согласуется с заявленной целью «самый быстрый HTML-парсер c DOM.»

                                                              Вы сомневаетесь? А вы потестируйте со своим. Ваш код в студию!

                                                                0
                                                                Вы читали спецификацию HTML?


                                                                Более того, я (в том числе) её писал. Как Invited Expert @ W3C HTML5 WG и WHATWG.

                                                                Ты наверное не понял что я имею ввиду. Скажем у тебя есть HTML в кодировке UTF-8 на входе. Т.е. 50% твоего текста это ASCII. Зачем эти 50% вообще куда-то конвертировать?

                                                                Тебе нужно конвертировать содержимое text nodes. И некоторых атрибутов. И только. Зачем дурную работу делать?

                                                                А код я привел выше. Еще раз: www.codeproject.com/Articles/14076/Fast-and-Compact-HTML-XML-Scanner-Tokenizer

                                                                  0
                                                                  Я не совсем понимаю куда разговор наш ведёт. Вы хотите оспорить, что у меня самый быстрый хтмл парсер?

                                                                  У нас идеальный мир? У нас только utf-8 приходит? А если utf-16 на вход. Почитай спеки encoding. Ссылку же дал. Ну в самом деле-то.

                                                                  > 40 MB of XML per second
                                                                  Ясно, понятно.

                                                                  Я всегда хотел поучаствовать в написании хтмл спеки. Но, для меня это непостижимо, я тут «горшки обжигаю».

                                                                  > Тебе нужно конвертировать содержимое text nodes. И некоторых атрибутов. И только. Зачем дурную работу делать?

                                                                  Ещё раз перечитай статью и посмотри исходники.

                                                                  Жаль, что общение с превратилось в фарс.
                                                                0

                                                                myhtml тоже гляньте гласком. Прошлый проект.

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

                                                              Самое читаемое