Hola a todos!
Continuamos la serie de artículos sobre el desarrollo del motor del navegador.
En este artículo explicaré cómo crear el analizador HTML más rápido con DOM. Analizaremos la especificación HTML y por qué es malo con respecto al rendimiento y al consumo de recursos al analizar HTML.
Con este tema, informé sobre el pasado HighLoad ++. No todos pueden asistir a la conferencia, además el artículo tiene más detalles.
Supongo que el lector tiene conocimientos básicos de HTML: etiquetas, nodos, elementos, espacio de nombres.
Especificación HTML
Antes de comenzar a tocar la implementación del analizador HTML, debe comprender qué especificaciones HTML debe creer.
Hay dos especificaciones HTML:
- WHATWG
- Apple, Mozilla, Google, Microsoft
- W3c
Naturalmente, la elección recayó en los líderes de la industria: WHATWG . Nivel de vida, grandes empresas, cada una con su propio navegador / motor de búsqueda.
ACTUALIZACIÓN: Desafortunadamente, los enlaces dados a las especificaciones no se abren desde Rusia. Aparentemente, el "eco de la guerra" con telegramas.
Proceso de análisis HTML
El proceso de construcción de un árbol HTML se puede dividir en cuatro partes:
- Decodificador
- Pretratamiento
- Tokenizer
- Construir un árbol
Consideramos cada etapa por separado.
Decodificador
El tokenizer acepta caracteres Unicode (puntos de código) como entrada. Por consiguiente, necesitamos convertir la secuencia de bytes actual a caracteres Unicode. Para hacer esto, use la especificación de codificación .
Si tenemos HTML con una codificación desconocida (sin encabezado HTTP), entonces debemos determinarlo antes de que comience la decodificación. Para hacer esto, utilizaremos el algoritmo de codificación sniffing .
Si es muy breve, la esencia del algoritmo es que esperamos 500 o los primeros 1024 del flujo de bytes y ejecutamos el algoritmo de preescaneo de flujo de bytes para determinar su codificación que intenta encontrar la <meta> con los atributos http-equiv , content o charset e intenta entienda qué codificación indicó el desarrollador HTML.
La especificación de Encoding estipula el conjunto mínimo de codificaciones admitidas por el motor del navegador (21 en 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 y x-user -definido.
Pretratamiento
Después de decodificar los bytes en caracteres Unicode, necesitamos "limpiar". Es decir, reemplace todos los caracteres de retorno de carro ( \r ) seguidos de un carácter de avance de línea ( \n ) con un carácter de retorno de carro ( \r ). Luego, reemplace todos los caracteres de retorno de carro con un carácter de nueva línea ( \n ).
Así se describe en la especificación. Es decir, \r\n => \r , \r => \n .
Pero, de hecho, nadie lo hace. Hazlo más fácil:
Si obtiene un carácter de retorno de carro ( \r ), observe si hay un carácter de avance de línea ( \n ). Si lo hay, entonces cambiamos ambos caracteres al carácter de avance de línea ( \n ), si no, cambiamos solo el primer carácter ( \r ) al avance de línea ( \n ).
Esto completa el procesamiento preliminar de datos. Sí, solo necesita deshacerse de los símbolos de retorno de carro para que no caigan en el tokenizador. El tokenizador no espera y no sabe qué hacer con el símbolo de retorno de carro.
Analizando errores
Para que en el futuro no haya preguntas, debe saber de inmediato qué es un parse error ).
Nada realmente mal. Suena amenazante, pero en realidad esto es solo una advertencia de que estábamos esperando uno, pero tenemos otro.
Un error de análisis no detendrá el procesamiento de datos o la construcción de árboles. Este es un mensaje que indica que no tenemos HTML válido.
Se puede obtener un error de Parsig para pares sustitutos, \0 , ubicación de etiqueta incorrecta, <!DOCTYPE> incorrecto y todo tipo de otras cosas.
Por cierto, algunos errores de análisis conducen a consecuencias. Por ejemplo, si especifica "bad" <!DOCTYPE> , el árbol HTML se marcará como QUIRKS y la lógica de algunas funciones DOM cambiará.
Tokenizer
Como se mencionó anteriormente, el tokenizer acepta caracteres Unicode como entrada. Esta es una máquina de estados que tiene 80 estados. En cada estado, condiciones para los caracteres Unicode. Dependiendo del personaje recibido, el tokenizer puede:
- Cambia tu estado
- Genera un token y cambia de estado
- No hagas nada, espera al próximo personaje
El tokenizer crea seis tipos de tokens: DOCTYPE, Start Tag, End Tag, Comment, Character, End-Of-File. Que entran en la etapa de construir un árbol.
Es de destacar que el tokenizer no conoce todos sus estados, pero donde aproximadamente el 40% (tomado del techo, por ejemplo). "¿Por qué el resto?" - usted pregunta Alrededor del 60% restante conoce la etapa de construcción de un árbol.
Esto se hace para analizar correctamente etiquetas como <textarea> , <style> , <script> , <title> y así sucesivamente. Es decir, generalmente aquellas etiquetas en las que no esperamos otras etiquetas, sino solo cerrarnos.
Por ejemplo, la <title> no puede contener otras etiquetas. Cualquier etiqueta en <title> se percibirá como texto hasta que encuentre una etiqueta de cierre para sí misma </title> .
¿Por qué se hace esto? Después de todo, podrías decirle al tokenizador que si nos encontramos con la <title> seguiremos el "camino que necesitamos". ¡Y eso sería cierto si no son espacios de nombres! Sí, el espacio de nombres afecta el comportamiento de la etapa de construcción del árbol, que a su vez cambia el comportamiento del tokenizer.
Como ejemplo, considere el comportamiento de la <title> en los espacios de nombres HTML y SVG:
HTML
<title><span></span></title>
El resultado de construir un árbol:
<title> "<span></span>"
Svg
<svg><title><span></span></title></svg>
El resultado de construir un árbol:
<svg> <title> <span> ""
Vemos que en el primer caso (espacio de nombres HTML) la <span> es texto, el elemento span no se creó. En el segundo caso (espacio de nombres SVG), se creó un elemento basado en la etiqueta <span> . Es decir, dependiendo del espacio de nombres, las etiquetas se comportan de manera diferente.
Pero eso no es todo. El pastel de esta "celebración de la vida" es el hecho de que el tokenizador debe saber en qué espacio de nombres se encuentra la etapa de construcción del árbol. Y esto es necesario únicamente para manejar adecuadamente CDATA .
Considere dos ejemplos con CDATA , dos espacios de nombres:
HTML
<div><![CDATA[ ]]></div>
El resultado de construir un árbol:
<div> <!--[CDATA[ ]]-->
Svg
<div><svg><![CDATA[ ]]></svg></div>
El resultado de construir un árbol:
<div> <svg> " "
En el primer caso (espacio de nombres HTML), el tokenizer tomó CDATA para hacer comentarios. En el segundo caso, el tokenizer desmontó la estructura CDATA y recibió datos de ella. En general, la regla es la siguiente: si nos encontramos con CDATA no en el espacio de nombres HTML, lo analizamos, de lo contrario lo consideramos como un comentario.
Esta es la estrecha conexión entre el tokenizador y la construcción del árbol. El tokenizador debe saber en qué espacio de nombres se encuentra actualmente la etapa de construcción del árbol, y la etapa de construcción del árbol puede cambiar el estado del tokenizador.
Fichas
A continuación, consideraremos los seis tipos de tokens creados por el tokenizador. Vale la pena señalar que todos los tokens tienen datos preparados, es decir, ya procesados y "listos para usar". Esto significa que todas las referencias de caracteres con nombre, como © , se convertirán en caracteres unicode.
Token DOCTYPE
El token DOCTYPE tiene su propia estructura, no similar a otras etiquetas. El token contiene:
- Nombre
- Identificador público
- Identificador del sistema
En HTML moderno, el único DOCTYPE válido / válido debería tener este aspecto:
<!DOCTYPE html>
Todos los demás <!DOCTYPE> se considerarán un error de análisis.
Iniciar etiqueta token
La etiqueta de apertura puede contener:
- Nombre de etiqueta
- Atributos
- Banderas
Por ejemplo,
<div key="value" />
La etiqueta de apertura puede contener una bandera de self-closing . Este indicador no afecta el cierre de la etiqueta, pero puede causar un error de análisis para elementos no nulos .
Token de etiqueta final
Etiqueta de cierre Tiene todas las propiedades del token de la etiqueta de apertura, pero tiene una barra diagonal / delante del nombre de la etiqueta.
</div key="value" />
La etiqueta de cierre puede contener un indicador de self-closing que provocará un error de análisis. Además, el error de análisis será causado por los atributos de la etiqueta de cierre. Se analizarán correctamente, pero se arrojarán en la etapa de construcción del árbol.
El token de comentario contiene todo el texto del comentario. Es decir, se copia completamente de la transmisión al token.
Ejemplo
Ficha de personaje
Quizás la ficha más interesante. Símbolo de token Unicode. Puede contener un (solo un) carácter.
Se creará un token para cada carácter en HTML y se enviará a la etapa de construcción del árbol. Esto es muy costoso.
Veamos como funciona.
Toma los datos HTML:
<span> ! ®</span>
¿Qué piensas cuántos tokens se crearán para este ejemplo? Respuesta: 22.
Considere la lista de tokens creados:
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
No es reconfortante, ¿verdad? Pero, por supuesto, muchos creadores de analizadores HTML de hecho solo tienen un token durante el procesamiento. Ejecutarlo en un círculo y sobrescribirlo con nuevos datos cada vez.
Avancemos y respondamos la pregunta: ¿por qué se hace esto? ¿Por qué no tomar este texto en una sola pieza? La respuesta está en la fase de construcción del árbol.
Un tokenizer es inútil sin la etapa de construir un árbol HTML. Es en la etapa de construcción de un árbol que el texto se pega con diferentes condiciones.
Las condiciones son aproximadamente las siguientes:
- Si llega un token de personaje con
U+0000 ( NULL ), entonces causamos un error de análisis e ignoramos el token. - Si uno de los
CHARACTER TABULATION U+0009 ( CHARACTER TABULATION ), U+000A ( LINE FEED (LF) ), U+000C ( FORM FEED (FF) ) o U+0020 ( SPACE ) llegó, llame al algoritmo para restaurar los elementos de formato activos y inserte la ficha en el árbol.
El token de símbolo se agrega al árbol de acuerdo con el algoritmo:
- Si la posición de inserción actual no es un nodo de texto, cree un nodo de texto, insértelo en el árbol y agréguele datos del token.
- De lo contrario, agregue datos del token a un nodo de texto existente.
Este comportamiento crea muchos problemas. La necesidad de que cada símbolo cree un token y lo envíe para su análisis a la etapa de construcción de un árbol. No conocemos el tamaño del nodo de texto y tenemos que asignar una gran cantidad de memoria por adelantado o hacer enlaces. Todo esto es extremadamente costoso de memoria o tiempo.
Token de fin de archivo
Token simple y claro. Los datos han terminado. Permítanos informarle sobre esta etapa de la construcción de árboles.
Construir un árbol
Tree building es una máquina 23 estados con 23 estados con muchas condiciones para tokens (etiquetas, texto). La etapa de construcción de un árbol es la más grande, ocupa una parte significativa de la especificación y también es capaz de causar irritación y sueño letárgico.
Todo está organizado de manera muy simple. Los tokens se reciben en la entrada y, dependiendo del token, se cambia el estado de la construcción del árbol. En la salida, tenemos un DOM real.
Problemas?
Los siguientes problemas parecen bastante obvios:
Copia caracter por caracter
Cada estado del tokenizador recibe un carácter en la entrada, que copia / convierte cuando sea necesario: nombres de etiquetas, atributos, comentarios, símbolos.
Esto es muy derrochador tanto en la memoria como en el tiempo. Nos vemos obligados a preasignar una cantidad desconocida de memoria para cada atributo, nombre de etiqueta, comentario, etc. Y esto, en consecuencia, conduce a reinos, y los reinos conducen a tiempo perdido.
Y si imagina que HTML contiene 1000 etiquetas, y cada etiqueta tiene al menos un atributo, entonces obtenemos un analizador infernalmente lento.
Ficha de personaje
El segundo problema es el token de personaje. Resulta que creamos una ficha para cada símbolo y le damos para construir un árbol. Construir un árbol no sabe cuántos de estos tokens tendremos y no podemos asignar inmediatamente memoria para la cantidad requerida de caracteres. En consecuencia, aquí todos los mismos realoks + constantes verifican la presencia de un nodo de texto en el estado actual del árbol.
Sistema monolítico
El gran problema es la dependencia de todo en todo. Es decir, el tokenizer depende del estado de construcción del árbol, y la construcción del árbol puede controlar el tokenizer. Y todo tiene la culpa del espacio de nombres (espacios de nombres).
¿Cómo resolveremos los problemas?
A continuación, describiré la implementación del analizador HTML en mi proyecto Lexbor , así como la solución a todos los problemas expresados.
Pretratamiento
Eliminamos el procesamiento preliminar de datos. Entrenaremos el tokenizador para comprender el retorno de carro ( \r ) como un carácter de espacio. Por lo tanto, lo arrojarán a la etapa de construcción de un árbol donde lo resolveremos.
Fichas
Con un movimiento de muñeca unificamos todas las fichas. Tendremos una ficha para todo. En general, solo habrá un token en todo el proceso de análisis.
Nuestro token unificado contendrá los siguientes campos:
- ID de etiqueta
- Comenzar
- Fin
- Atributos
- Banderas
ID de etiqueta
No trabajaremos con la representación textual del nombre de la etiqueta. Traducimos todo a números. Los números son fáciles de comparar, más fáciles de trabajar.
Creamos una tabla hash estática a partir de todas las etiquetas conocidas. Creamos enumeración a partir de todas las etiquetas conocidas. Es decir, debemos asignar rígidamente un identificador a cada etiqueta. En consecuencia, en la tabla hash, la clave es el nombre de la etiqueta y el valor se escribe desde la enumeración.
Por un ejemplo:
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 puede ver en el ejemplo, creamos etiquetas para el token END-OF-FILE , para texto, para un documento. Todo esto en aras de una mayor comodidad. Al abrir el telón, diré que en el nodo ( DOM Node Interface ) tendremos una Tag ID . Esto se hace para no hacer dos comparaciones: en el tipo de nodo y en el elemento. Es decir, si necesitamos un elemento DIV , entonces hacemos una comprobación en el nodo:
if (node->tag_id == LXB_TAG_DIV) { }
Pero, por supuesto, puedes hacer esto:
if (node->type == LXB_DOM_NODE_TYPE_ELEMENT && node->tag_id == LXB_TAG_DIV) { }
Se necesitan dos guiones bajos en LXB_TAG__ para separar las etiquetas comunes de las del sistema. En otras palabras, el usuario puede crear una etiqueta con el text del nombre o el end-of-file y si luego buscamos por nombre de etiqueta, no se producirán errores. Todas las etiquetas del sistema comienzan con un # .
Pero aún así, un nodo puede almacenar una representación textual del nombre de la etiqueta. Para 98.99999% de nodos, este parámetro será NULL . En algunos espacios de nombres, necesitamos especificar un prefijo o nombre de etiqueta con un registro fijo. Por ejemplo, baseProfile en el espacio de nombres SVG.
La lógica del trabajo es simple. Si tenemos una etiqueta con un registro claramente definido, entonces:
- Agréguelo a la base general de etiquetas en minúsculas. Obtenga la identificación de la etiqueta.
- Agregue el identificador de etiqueta y el nombre de etiqueta original en la representación de texto al nodo.
Etiquetas personalizadas
Un desarrollador puede crear cualquier etiqueta en HTML. Como solo tenemos las etiquetas que conocemos en una tabla hash estática y el usuario puede crearlas, necesitamos una tabla hash dinámica.
Todo se ve muy simple. Cuando nos llegue la etiqueta, veremos si está en la tabla hash estática. Si no hay etiqueta, veamos la dinámica, si no la hay, aumente el contador del identificador en uno y agregue la etiqueta a la tabla dinámica.
Todo lo descrito ocurre en la etapa del tokenizer. Dentro del tokenizer y después de todas las comparaciones, vaya por Tag ID (con raras excepciones).
Comienzo y fin
Ahora en el tokenizer no tendremos procesamiento de datos. No copiaremos ni convertiremos nada. Simplemente llevamos punteros al principio y al final de los datos.
Todo el procesamiento de datos, como los enlaces simbólicos, se llevará a cabo en la etapa de construcción del árbol.
Por lo tanto, sabremos el tamaño de los datos para la asignación posterior de memoria.
Atributos
Aquí todo es igual de simple. No copiamos nada, simplemente guardamos punteros al principio / al final del nombre y los valores de los atributos. Todas las transformaciones ocurren en el momento en que se construye el árbol.
Banderas
Dado que tenemos tokens unificados, debemos informar de alguna manera al edificio del árbol sobre el tipo de token. Para hacer esto, use el campo de mapa de bits de Banderas.
El campo puede contener los siguientes 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 };
Además del tipo de token que se abre o cierra, hay valores para el convertidor de datos. Solo el tokenizer sabe cómo convertir correctamente los datos. En consecuencia, el tokenizer marca en el token cómo se deben procesar los datos.
Ficha de personaje
De lo descrito anteriormente, podemos concluir que el token del símbolo ha desaparecido de nosotros. Sí, ahora tenemos un nuevo tipo de token: LXB_HTML_TOKEN_TYPE_TEXT . Ahora creamos un token para todo el texto entre las etiquetas, marcando cómo se debe procesar en el futuro.
Debido a esto, tendremos que cambiar las condiciones en la construcción del árbol. Necesitamos entrenarlo para trabajar no con tokens simbólicos, sino con tokens de texto: convertir, eliminar caracteres innecesarios, omitir espacios, etc.
Pero, no hay nada complicado. En la etapa de construcción de un árbol, los cambios serán mínimos. Pero el tokenizer ahora no coincide con la especificación de la palabra en absoluto. Pero no lo necesitamos, es normal. Nuestra tarea es obtener un árbol HTML / DOM que cumpla totalmente con las especificaciones.
Etapas Tokenizer
Para garantizar el procesamiento de datos a alta velocidad en el tokenizer, agregaremos nuestro iterador a cada etapa. Según la especificación, cada etapa acepta un símbolo para nosotros y, dependiendo del símbolo que ha llegado, toma decisiones. Pero, la verdad es que es muy caro.
Por ejemplo, para pasar de la etapa ATTRIBUTE_NAME a la etapa ATTRIBUTE_VALUE necesitamos encontrar un espacio en blanco en el nombre del atributo, que indicará su finalización. De acuerdo con la especificación, debemos alimentar por carácter a la etapa ATTRIBUTE_NAME hasta que se ATTRIBUTE_NAME un carácter de espacio en blanco, y esta etapa no cambie a otra. Esto es muy costoso, generalmente se implementa a través de una llamada de función para cada carácter o devolución de llamada como "tkz-> next_code_point ()".
Agregamos un bucle a la etapa ATTRIBUTE_NAME y pasamos todo el búfer entrante. En el ciclo, buscamos los símbolos que necesitamos cambiar y continuamos trabajando en la siguiente etapa. Aquí obtenemos muchas ganancias, incluso optimizaciones del compilador.
Pero! Lo peor es que rompimos el soporte de trozos (trozos) fuera de la caja. Gracias al procesamiento de caracteres por símbolo en cada etapa del tokenizer, teníamos soporte para fragmentos, y ahora lo hemos roto.
¿Cómo arreglarlo? ¿Cómo implementar soporte para trozos? Es simple, presentamos el concepto de buffers entrantes (Buffer entrante).
Tampón entrante
A menudo, el HTML se analiza en fragmentos. Por ejemplo, si recibimos datos a través de la red. Para no permanecer inactivo mientras espera los datos restantes, podemos enviar los datos ya recibidos para su procesamiento / análisis. Naturalmente, los datos se pueden dividir en cualquier lugar. Por ejemplo, tenemos dos buffers:
Primero
<div clas
Segundo
s="oh-no-oh-no">
Dado que no copiamos nada en la etapa de tokenización, sino que solo llevamos punteros al principio y al final de los datos, tenemos un problema. Punteros a diferentes buffers de usuario. Y dado que los desarrolladores a menudo usan el mismo búfer para los datos, estamos tratando con un puntero al comienzo de datos inexistentes.
.
:
- (Incoming Buffer).
- ( ) , ? , . , . 99% .
" " . .
, . , ( ) . . , , , . .
:
, . , : . . ( ), . .
: . , .
.
, . , .
:
tree_build_in_body_character(token) { if (token.code_point == '\0') { } else if (token.code_point == whitespaces) { ' } /* ... */ }
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) { } }
, . :
pc.replace_null pc.drop_null 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 .
, :
- ( )
- Incoming Buffer
- Tag ID
- ̆ : , N+
- ̆
- ̈
i7 2012 , , 235MB (Amazon-).
, 1.5/2 , . , . , CSS (Grammar, , Grammar). HTML, CSS , "".
Código fuente
HTML Lexbor HTML .
PS
CSS Grammar. , . - 6-8 .
Gracias por su atencion!