Desenvolva seu navegador a partir do zero. Parte Um: HTML

Olá pessoal!

Continuamos a série de artigos sobre o desenvolvimento do mecanismo do navegador.

Neste artigo, mostrarei como criar o analisador HTML mais rápido com o DOM. Veremos a especificação HTML e por que ela é ruim em relação ao desempenho e consumo de recursos ao analisar o HTML.

Com este tópico, relatei o HighLoad ++ passado. Nem todos podem participar da conferência, além do artigo ter mais detalhes.

Suponho que o leitor tenha conhecimento básico de HTML: tags, nós, elementos, espaço para nome.

Especificação HTML

Antes de começar a tocar na implementação do analisador HTML, você precisa entender em que especificações HTML acreditar.

Existem duas especificações HTML:

1. WHATWG
   
   • Apple, Mozilla, Google, Microsoft
2. W3c
   
   • Grande lista de empresas

Naturalmente, a escolha recaiu sobre os líderes do setor - WHATWG . Padrão de vida, grandes empresas, cada uma com seu próprio navegador / mecanismo de navegador.

ATUALIZAÇÃO: Infelizmente, os links fornecidos para as especificações não abrem da Rússia. Aparentemente, o "eco da guerra" com os telegramas.

Processo de análise de HTML

O processo de construção de uma árvore HTML pode ser dividido em quatro partes:

1. Decodificador
2. Pré-tratamento
3. Tokenizer
4. Construindo uma árvore

Consideramos cada estágio separadamente.

Decodificador

O tokenizer aceita caracteres Unicode (pontos de código) como entrada. Portanto, precisamos converter o fluxo de bytes atual em caracteres Unicode. Para fazer isso, use a especificação Encoding .

Se tivermos HTML com uma codificação desconhecida (sem cabeçalho HTTP), precisaremos determiná-lo antes do início da decodificação. Para fazer isso, usaremos o algoritmo de detecção de codificação .

Se muito brevemente, a essência do algoritmo é que esperamos 500 ou os primeiros 1024 do fluxo de bytes e executamos o algoritmo de pré-digitalização de um fluxo de bytes para determinar sua codificação que tenta encontrar a <meta> com os atributos http-equiv , content ou charset e tenta entender o que a codificação indicada pelo desenvolvedor HTML.

A especificação de Encoding estipula o conjunto mínimo de codificações suportadas pelo mecanismo do navegador (21 no total): 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 e x-usuário -definido.

Pré-tratamento

Depois de decodificar os bytes em caracteres Unicode, precisamos "limpar". Substitua todos os caracteres de retorno de carro ( \r ) seguidos por um caractere de avanço de linha ( \n ) por um caractere de retorno de carro ( \r ). Em seguida, substitua todos os caracteres de retorno de carro por um caractere de nova linha ( \n ).

Assim descrito na especificação. Ou seja, \r\n => \r , \r => \n .

Mas, de fato, ninguém faz. Facilite:

Se você obtiver um caractere de retorno de carro ( \r ), verifique se há um caractere de avanço de linha ( \n ). Se houver, alteramos os dois caracteres para o caractere de avanço de linha ( \n ); caso contrário, alteramos apenas o primeiro caractere ( \r ) para o avanço de linha ( \n ).

Isso completa o processamento preliminar de dados. Sim, você só precisa se livrar dos símbolos de retorno de carro para que eles não caiam no tokenizador. O tokenizador não espera e não sabe o que fazer com o símbolo de retorno de carro.

Erros de análise

Para que no futuro não haja perguntas, você deve informar imediatamente o que é um ( parse error ).

Nada realmente errado. Parece ameaçador, mas na verdade isso é apenas um aviso de que estávamos esperando um, mas temos outro.

Um erro de análise não interrompe o processamento de dados ou a construção de árvores. Esta é uma mensagem que indica que não temos HTML válido.

O erro de análise pode ser obtido para pares substitutos, \0 , local incorreto da marca, <!DOCTYPE> incorreto e todo tipo de outras coisas.

A propósito, alguns erros de análise levam a consequências. Por exemplo, se você especificar "bad" <!DOCTYPE> , a árvore HTML será marcada como QUIRKS e a lógica de algumas funções do DOM será alterada.

Tokenizer

Como mencionado anteriormente, o tokenizer aceita caracteres Unicode como entrada. Esta é uma máquina de estado que possui 80 estados. Em cada estado, condições para caracteres Unicode. Dependendo do caractere recebido, o tokenizador pode:

1. Mude seu estado
2. Gere um token e mude de estado
3. Não faça nada, aguarde o próximo personagem

O tokenizer cria seis tipos de tokens: DOCTYPE, Tag inicial, Tag final, Comentário, Caractere, Fim do arquivo. Que entram no estágio de construção de uma árvore.

Vale ressaltar que o tokenizer não conhece todos os seus estados, mas onde cerca de 40% (retirado do teto, por exemplo). "Por que o resto?" - você pergunta. Cerca dos 60% restantes conhecem o estágio de construção de uma árvore.

Isso é feito para analisar corretamente tags como <textarea> , <style> , <script> , <title> e assim por diante. Ou seja, geralmente aquelas tags nas quais não esperamos outras, mas apenas fechando a nós mesmos.

Por exemplo, a <title> não pode conter outras tags. Qualquer tag em <title> será percebida como texto até encontrar uma tag de fechamento </title> .

Por que isso é feito? Afinal, você pode simplesmente dizer ao tokenizer que, se encontrarmos a <title> seguiremos o "caminho que precisamos". E isso seria verdade se não os namespaces! Sim, o espaço para nome afeta o comportamento do estágio de construção da árvore, que por sua vez altera o comportamento do tokenizador.

Como exemplo, considere o comportamento da <title> nos espaços para nome HTML e SVG:

HTML

 <title><span></span></title> 

O resultado da construção de uma árvore:

 <title> "<span></span>" 

Svg

 <svg><title><span></span></title></svg> 

O resultado da construção de uma árvore:

 <svg> <title> <span> "" 

Vimos que, no primeiro caso (espaço de nome HTML), a <span> é texto, o elemento span não foi criado. No segundo caso (espaço de nome SVG), um elemento foi criado com base na tag <span> . Ou seja, dependendo do espaço para nome, as tags se comportam de maneira diferente.

Mas isso não é tudo. O bolo desta "celebração da vida" é o fato de que o próprio tokenizador deve saber em que espaço de nome está localizado o estágio de construção da árvore. E isso é necessário apenas para lidar adequadamente com o CDATA .

Considere dois exemplos com CDATA , dois espaços para nome:

HTML

 <div><![CDATA[  ]]></div> 

O resultado da construção de uma árvore:

 <div> <!--[CDATA[  ]]--> 

Svg

 <div><svg><![CDATA[  ]]></svg></div> 

O resultado da construção de uma árvore:

 <div> <svg> "  " 

No primeiro caso (espaço para nome HTML), o tokenizer levou o CDATA para comentar. No segundo caso, o tokenizer desmontou a estrutura CDATA e recebeu dados dela. Em geral, a regra é a seguinte: se encontrarmos CDATA não está no espaço de nomes HTML, analisamos-o, caso contrário, o consideraremos como um comentário.

Essa é a conexão estreita entre o tokenizer e a construção da árvore. O tokenizer deve saber em qual espaço de nomes está localizado o estágio de construção da árvore e o estágio de construção da árvore pode alterar o estado do tokenizador.

Tokens

Abaixo, consideraremos todos os seis tipos de tokens criados pelo tokenizer. Vale ressaltar que todos os tokens prepararam dados, isto é, já foram processados ​​e “prontos para uso”. Isso significa que todas as referências de caracteres nomeadas, como © , serão convertidas em caracteres unicode.

DOCTYPE Token

O token DOCTYPE possui sua própria estrutura não semelhante a outras tags. O token contém:

1. Primeiro nome
2. Identificador público
3. Identificador do sistema

No HTML moderno, o único DOCTYPE válido / válido deve ficar assim:

 <!DOCTYPE html> 

Todos os outros <!DOCTYPE> serão considerados um erro de análise.

Iniciar token de tag

A tag de abertura pode conter:

1. Nome da tag
2. Atributos
3. Bandeiras

Por exemplo,

 <div key="value" /> 

A tag de abertura pode conter um sinalizador de self-closing . Esse sinalizador não afeta o fechamento da tag, mas pode causar um erro de análise para elementos não nulos .

Finalizar token da tag

Tag de fechamento. Ele possui todas as propriedades do token da tag de abertura, mas possui uma barra / na frente do nome da tag.

 </div key="value" /> 

A tag de fechamento pode conter um sinalizador de self-closing que causará um erro de análise. Além disso, o erro de análise será causado pelos atributos da marca de fechamento. Eles serão analisados ​​corretamente, mas jogados fora na fase de construção das árvores.

Token de comentário

O token de comentário contém todo o texto do comentário. Ou seja, é completamente copiado do fluxo para o token.

Exemplo

 <!--  --> 

Token de personagem

Talvez o token mais interessante. Símbolo de token Unicode. Pode conter um (apenas um) caractere.

Um token será criado para cada caractere em HTML e enviado ao estágio de construção da árvore. Isso é muito caro.
Vamos ver como isso funciona.

Pegue os dados HTML:

 <span> ! &reg;</span> 

O que você acha quantos tokens serão criados para este exemplo? Resposta: 22.

Considere a lista de tokens criados:

 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 

Não é reconfortante, certo? Mas, é claro, muitos criadores de analisadores de HTML de fato têm apenas um token durante o processamento. Executando-o em um círculo e substituindo-o por novos dados a cada vez.

Vamos seguir em frente e responder à pergunta: por que isso é feito? Por que não levar esse texto em uma única peça? A resposta está na fase de construção da árvore.

Um tokenizador é inútil sem o estágio de construção de uma árvore HTML. É na fase de construção de uma árvore que o texto é colado com diferentes condições.

As condições são aproximadamente as seguintes:

1. Se um token de caractere com U+0000 ( NULL ) chegar, causamos um erro de análise e ignoramos o token.
2. Se um dos CHARACTER TABULATION U+0009 ( CHARACTER TABULATION ), U+000A ( LINE FEED (LF) ), U+000C ( FORM FEED (FF) ) ou U+0020 ( SPACE ) vier, chame o algoritmo para restaurar os elementos de formatação ativos e insira o token na árvore.

O token de símbolo é adicionado à árvore de acordo com o algoritmo:

1. Se a posição de inserção atual não for um nó de texto, crie um nó de texto, insira-o na árvore e adicione dados do token a ele.
2. Caso contrário, adicione dados do token a um nó de texto existente.

Esse comportamento cria muitos problemas. A necessidade de cada símbolo criar um token e enviar para análise ao estágio de construção de uma árvore. Não sabemos o tamanho do nó de texto e temos que alocar muita memória antecipadamente ou fazer realoks. Tudo isso é extremamente caro de memória ou tempo.

Token de fim de arquivo

Token simples e claro. Os dados acabaram - vamos informá-lo sobre esta etapa da construção das árvores.

Construindo uma árvore

A construção de árvores é uma máquina 23 estados com 23 estados com muitas condições para tokens (tags, texto). O estágio de construção de uma árvore é o maior, ocupa uma parte significativa da especificação e também é capaz de causar irritação e sono letárgico.

Tudo é organizado de maneira muito simples. Os tokens são recebidos na entrada e, dependendo do token, o estado da construção da árvore é alternado. Na saída, temos um DOM real.

Problemas?

Os seguintes problemas parecem bastante óbvios:

Cópia por caractere

Cada estado do tokenizer recebe um caractere na entrada, que copia / converte quando necessário: nomes de tags, atributos, comentários, símbolos.

Isso é muito inútil, tanto na memória quanto no tempo. Somos forçados a pré-alocar uma quantidade desconhecida de memória para cada atributo, nome da tag, comentário e assim por diante. E isso, consequentemente, leva a realoks, e realoks levam a tempo perdido.

E se você imagina que o HTML contém 1000 tags e cada tag possui pelo menos um atributo, obtemos um analisador infernalmente lento.

Token de personagem

O segundo problema é o token de caractere. Acontece que criamos um token para cada símbolo e damos para construir uma árvore. Construir uma árvore não sabe quantos desses tokens teremos e não podemos alocar memória imediatamente para o número necessário de caracteres. Assim, aqui todos os mesmos realoks + constantes verificam a presença de um nó de texto no estado atual da árvore.

Sistema monolítico

O grande problema é a dependência de tudo em tudo. Ou seja, o tokenizer depende do estado de construção da árvore, e a construção da árvore pode controlar o tokenizer. E tudo é o culpado pelo namespace (namespaces).

Como vamos resolver os problemas?

A seguir, descreverei a implementação do analisador de HTML no meu projeto Lexbor , bem como a solução para todos os problemas expressos.

Pré-tratamento

Removemos o processamento preliminar de dados. Treinaremos o tokenizador para entender o retorno de carro ( \r ) como um caractere de espaço. Assim, ele será jogado no estágio de construção de uma árvore onde descobriremos isso.

Tokens

Com um movimento do pulso, unificamos todos os tokens. Teremos um token para tudo. Em geral, haverá apenas um token em todo o processo de análise.

Nosso token unificado conterá os seguintes campos:

1. ID da tag
2. Iniciar
3. Fim
4. Atributos
5. Bandeiras

ID da tag

Não trabalharemos com a representação textual do nome da tag. Nós traduzimos tudo em números. Os números são fáceis de comparar, mais fáceis de trabalhar.

Criamos uma tabela de hash estática de todas as tags conhecidas. Criamos enum a partir de todas as tags conhecidas. Ou seja, precisamos atribuir rigidamente um identificador para cada tag. Assim, na tabela de hash, a chave é o nome da marca e o valor é gravado na enumeração.

Por exemplo:

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

Como você pode ver no exemplo, criamos tags para o token END-OF-FILE , para texto, para um documento. Tudo isso para maior conveniência. Abrindo a cortina, direi que no nó ( DOM Node Interface ) teremos um Tag ID . Isso é feito para não fazer duas comparações: no tipo de nó e no elemento. Ou seja, se precisarmos de um elemento DIV , faremos uma verificação no nó:

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

Mas, é claro, você pode fazer isso:

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

São necessários dois sublinhados em LXB_TAG__ para separar tags comuns das tags do sistema. Em outras palavras, o usuário pode criar uma tag com o nome text ou no end-of-file e end-of-file se procurarmos pelo nome da tag, nenhum erro ocorrerá. Todas as tags do sistema começam com um # .

Ainda assim, um nó pode armazenar uma representação textual do nome da marca. Para 98.99999% de nós, esse parâmetro será NULL . Em alguns espaços para nome, precisamos especificar um prefixo ou nome de marca com um registro fixo. Por exemplo, baseProfile no espaço de nome SVG.

A lógica do trabalho é simples. Se tivermos uma tag com um registro claramente definido, então:

1. Adicione-o à base geral de tags em minúsculas. Obtenha o ID da tag.
2. Adicione o identificador de marca e o nome da marca original na representação de texto ao nó.

Tags personalizadas

Um desenvolvedor pode criar qualquer tag em HTML. Como temos apenas as tags que conhecemos em uma tabela hash estática e o usuário pode criar uma, precisamos de uma tabela hash dinâmica.

Tudo parece muito simples. Quando a tag chegar, veremos se está na tabela de hash estática. Se não houver uma tag, vejamos a dinâmica, se não houver, aumentamos o contador do identificador em um e adicionamos a tag à tabela dinâmica.

Tudo descrito acontece no estágio do tokenizer. Dentro do tokenizer e depois de todas as comparações, vá pelo Tag ID (com raras exceções).

Início e fim

Agora, no tokenizer, não teremos processamento de dados. Não copiaremos e converteremos nada. Apenas indicamos o início e o fim dos dados.

Todo o processamento de dados, como links simbólicos, ocorrerá no estágio de construção da árvore.
Assim, saberemos o tamanho dos dados para a alocação subsequente de memória.

Atributos

Tudo é tão simples aqui. Nós não copiamos nada, mas simplesmente salvamos os ponteiros no início / fim dos valores de nome e atributo. Todas as transformações ocorrem no momento em que a árvore é construída.

Bandeiras

Como temos tokens unificados, precisamos informar a construção de árvores sobre o tipo de token. Para fazer isso, use o campo de bitmap Flags.

O campo pode conter os seguintes valores:

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

Além do tipo de token que abre ou fecha, há valores para o conversor de dados. Somente o tokenizador sabe como converter os dados corretamente. Assim, o tokenizador marca no token como os dados devem ser processados.

Token de personagem

Do descrito anteriormente, pode-se concluir que o token de símbolo desapareceu de nós. Sim, agora temos um novo tipo de token: LXB_HTML_TOKEN_TYPE_TEXT . Agora, criamos um token para o texto inteiro entre as tags, marcando como ele deve ser processado no futuro.

Por isso, teremos que alterar as condições na construção da árvore. Precisamos treiná-lo para trabalhar não com tokens simbólicos, mas com tokens de texto: converter, excluir caracteres desnecessários, pular espaços e assim por diante.

Mas, não há nada complicado. Na fase de construção de uma árvore, as alterações serão mínimas. Mas o tokenizador agora não corresponde à especificação da palavra. Mas não precisamos dele, é normal. Nossa tarefa é obter uma árvore HTML / DOM que esteja em total conformidade com as especificações.

Etapas do tokenizador

Para garantir o processamento de dados em alta velocidade no tokenizer, adicionaremos nosso iterador a cada estágio. De acordo com a especificação, cada estágio aceita um símbolo para nós e, dependendo do símbolo que chegou, toma decisões. Mas, a verdade é que é muito caro.

Por exemplo, para passar do estágio ATTRIBUTE_NAME para o estágio ATTRIBUTE_VALUE precisamos encontrar um espaço em branco no nome do atributo, o que indicará seu fim. De acordo com a especificação, devemos alimentar por caractere o estágio ATTRIBUTE_NAME até que ATTRIBUTE_NAME um caractere de espaço em branco, e esse estágio não muda para outro. Isso é muito caro, geralmente é implementado através de uma chamada de função para cada caractere ou retorno de chamada como "tkz-> next_code_point ()".

Adicionamos um loop ao estágio ATTRIBUTE_NAME e passamos todo o buffer de entrada. No loop, procuramos os símbolos que precisamos alternar e continuamos a trabalhar no próximo estágio. Aqui temos muitos ganhos, até otimizações de compilador.

Mas! O pior é que, dessa forma, quebramos o suporte de pedaços (pedaços) da caixa. Graças ao processamento de caractere por símbolo em cada estágio do tokenizer, tínhamos suporte para pedaços e agora o quebramos.

Como consertar isso? Como implementar o suporte para pedaços ?! É simples, apresentamos o conceito de buffers de entrada (buffer de entrada).

Buffer de entrada

Frequentemente, o HTML analisa em pedaços. Por exemplo, se recebermos dados pela rede. Para não ficar ocioso enquanto aguarda os dados restantes, podemos enviar dados já recebidos para processamento / análise. Naturalmente, os dados podem ser extraídos em qualquer lugar. Por exemplo, temos dois buffers:

Primeiro

 <div clas 

Segundo

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

Como não copiamos nada no estágio de tokenização, mas apenas levamos ponteiros para o início e o fim dos dados, temos um problema. Ponteiros para diferentes buffers de usuário. E, como os desenvolvedores costumam usar o mesmo buffer para dados, estamos lidando com um ponteiro para o início de dados inexistentes.

.
:

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> . , , : " ". , .

 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 , "".

Código fonte

HTML Lexbor HTML .

PS

CSS Grammar. , . - 6-8 .

Obrigado pela atenção!