Geekly articles weekly

Entwickeln Sie Ihren Browser von Grund auf neu. Erster Teil: HTML


Hallo allerseits!


Wir setzen die Artikelserie zur Entwicklung der Browser-Engine fort.


In diesem Artikel werde ich Ihnen erklären, wie Sie den schnellsten HTML-Parser mit DOM erstellen. Wir werden uns die HTML-Spezifikation ansehen und herausfinden, warum sie hinsichtlich der Leistung und des Ressourcenverbrauchs beim Parsen von HTML schlecht ist.


Mit diesem Thema habe ich über das vergangene HighLoad ++ berichtet. Nicht jeder kann an der Konferenz teilnehmen, und der Artikel enthält weitere Details.


Ich gehe davon aus, dass der Leser Grundkenntnisse in HTML hat: Tags, Knoten, Elemente, Namespace.


HTML-Spezifikation


Bevor Sie sich mit der Implementierung des HTML-Parsers befassen, müssen Sie wissen, welche HTML-Spezifikationen Sie glauben müssen.


Es gibt zwei HTML-Spezifikationen:


  1. WAS
    • Apple, Mozilla, Google, Microsoft
  2. W3c
    • Große Liste von Unternehmen

Natürlich fiel die Wahl auf Branchenführer - WHATWG . Lebensstandard, große Unternehmen mit jeweils eigenem Browser / eigener Browser-Engine.


UPDATE: Leider öffnen sich die angegebenen Links zu den Spezifikationen nicht aus Russland. Anscheinend das "Echo des Krieges" mit Telegrammen.


HTML-Analyseprozess


Der Prozess zum Erstellen eines HTML-Baums kann in vier Teile unterteilt werden:


  1. Decoder
  2. Vorbehandlung
  3. Tokenizer
  4. Einen Baum bauen

Wir betrachten jede Stufe einzeln.


Decoder


Der Tokenizer akzeptiert Unicode-Zeichen (Codepunkte) als Eingabe. Dementsprechend müssen wir den aktuellen Bytestream in Unicode-Zeichen konvertieren. Verwenden Sie dazu die Codierungsspezifikation .


Wenn wir HTML mit einer unbekannten Codierung haben (kein HTTP-Header), müssen wir es bestimmen, bevor die Decodierung beginnt. Zu diesem Zweck verwenden wir den Codierungs-Sniffing-Algorithmus .


Wenn es nur sehr kurz ist, besteht die Essenz des Algorithmus darin, dass wir 500 oder die ersten 1024 vom Byte-Stream warten und den Prescan-Byte-Stream- Algorithmus ausführen, um seine Codierung zu bestimmen, die versucht, das <meta> mit den Attributen http-equiv , content oder charset und zu versuchen Verstehen Sie, welche Codierung der HTML-Entwickler angegeben hat.


Die Encoding legt den Mindestsatz unterstützter Codierungen durch die Browser-Engine fest (insgesamt 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 und X-User -definiert.


Vorbehandlung


Nachdem wir die Bytes in Unicode-Zeichen dekodiert haben, müssen wir "bereinigen". Ersetzen Sie nämlich alle Wagenrücklaufzeichen ( \r ) gefolgt von einem Zeilenvorschubzeichen ( \n ) durch ein Wagenrücklaufzeichen ( \r ). Ersetzen Sie dann alle Wagenrücklaufzeichen durch ein Zeilenumbruchzeichen ( \n ).


So beschrieben in der Spezifikation. Das heißt, \r\n => \r , \r => \n .


Tatsächlich tut es aber niemand. Machen Sie es einfacher:


Wenn Sie ein Wagenrücklaufzeichen ( \r ) erhalten, prüfen Sie, ob ein Zeilenvorschubzeichen ( \n ) vorhanden ist. Wenn dies der Fall ist, ändern wir beide Zeichen in das Zeilenvorschubzeichen ( \n ). Wenn nicht, ändern wir nur das erste Zeichen ( \r ) in das Zeilenvorschubzeichen ( \n ).


Damit ist die vorläufige Datenverarbeitung abgeschlossen. Ja, Sie müssen nur die Wagenrücklaufsymbole entfernen, damit sie nicht in den Tokenizer fallen. Der Tokenizer erwartet nicht und weiß nicht, was mit dem Wagenrücklaufsymbol zu tun ist.


Analysefehler


Damit es in Zukunft keine Fragen mehr gibt, sollten Sie sofort feststellen, was ein ( parse error ).


Nichts wirklich falsch. Es klingt bedrohlich, aber tatsächlich ist dies nur eine Warnung, dass wir einen erwartet haben, aber wir haben einen anderen.


Ein Analysefehler stoppt nicht die Datenverarbeitung oder die Baumbildung. Dies ist eine Nachricht, die signalisiert, dass wir kein gültiges HTML haben.


Parsig-Fehler können für Ersatzpaare, \0 , falsche Tag-Position, falsches <!DOCTYPE> und alle möglichen anderen Dinge erhalten werden.


Übrigens führen einige Analysefehler zu Konsequenzen. Wenn Sie beispielsweise "bad" <!DOCTYPE> angeben, wird der HTML-Baum als QUIRKS markiert und die Logik einiger DOM-Funktionen ändert sich.


Tokenizer


Wie bereits erwähnt, akzeptiert der Tokenizer Unicode-Zeichen als Eingabe. Dies ist eine Zustandsmaschine mit 80 Zuständen. In jedem Zustand Bedingungen für Unicode-Zeichen. Abhängig vom empfangenen Zeichen kann der Tokenizer:


  1. Ändern Sie Ihren Zustand
  2. Generieren Sie ein Token und ändern Sie den Status
  3. Tu nichts, warte auf den nächsten Charakter

Der Tokenizer erstellt sechs Arten von Token: DOCTYPE, Start-Tag, End-Tag, Kommentar, Zeichen, Dateiende. Welche betreten die Phase des Baumbaus.


Es ist bemerkenswert, dass der Tokenizer nicht über alle seine Zustände Bescheid weiß, aber wo ungefähr 40% (zum Beispiel von der Decke genommen). "Warum der Rest?" - Du fragst. Etwa die restlichen 60% kennen das Stadium des Baumbaus.


Dies geschieht, um Tags wie <textarea> , <style> , <script> , <title> usw. korrekt zu analysieren. Das heißt, normalerweise jene Tags, bei denen wir keine anderen Tags erwarten, sondern nur uns selbst schließen.


Beispielsweise kann das <title> keine anderen Tags enthalten. Alle Tags in <title> werden als Text wahrgenommen, bis sie auf ein schließendes Tag für sich selbst stoßen. </title> .


Warum wird das gemacht? Schließlich könnte man dem Tokenizer einfach sagen, dass wir, wenn wir das <title> treffen <title> den "Pfad gehen, den wir brauchen". Und das wäre wahr, wenn nicht Namespaces! Ja, der Namespace wirkt sich auf das Verhalten der Baumerstellungsphase aus, was wiederum das Verhalten des Tokenizers ändert.


Betrachten Sie als Beispiel das Verhalten des <title> in HTML- und SVG-Namespaces:


HTML


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

Das Ergebnis des Baumbaus:


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

Svg


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

Das Ergebnis des Baumbaus:


 <svg> <title> <span> ""

Wir sehen, dass im ersten Fall (HTML-Namespace) das <span> Text ist und das span Element nicht erstellt wurde. Im zweiten Fall (SVG-Namespace) wurde ein Element basierend auf dem <span> -Tag erstellt. Das heißt, je nach Namespace verhalten sich Tags unterschiedlich.


Aber das ist noch nicht alles. Der Kuchen bei dieser "Feier des Lebens" ist die Tatsache, dass der Tokenizer selbst wissen muss, in welchem ​​Namespace sich die Phase der Baumkonstruktion befindet. Und dies ist nur notwendig, um CDATA richtig zu handhaben.


Betrachten Sie zwei Beispiele mit CDATA , zwei Namespaces:


HTML


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

Das Ergebnis des Baumbaus:


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

Svg


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

Das Ergebnis des Baumbaus:


 <div> <svg> "  "

Im ersten Fall (HTML-Namespace) nahm der Tokenizer CDATA als Kommentar. Im zweiten Fall zerlegte der Tokenizer die CDATA Struktur und empfing Daten von ihr. Im Allgemeinen lautet die Regel: Wenn wir CDATA nicht im HTML-Namespace treffen, analysieren wir es, andernfalls betrachten wir es als Kommentar.


Dies ist die enge Verbindung zwischen dem Tokenizer und der Konstruktion des Baums. Der Tokenizer muss wissen, in welchem ​​Namespace sich die Phase der Baumkonstruktion gerade befindet, und die Phase der Baumkonstruktion kann den Status des Tokenizers ändern.


Token


Im Folgenden werden alle sechs Arten von Token betrachtet, die vom Tokenizer erstellt wurden. Es ist erwähnenswert, dass alle Token Daten vorbereitet haben, dh bereits verarbeitet und "gebrauchsfertig" sind. Dies bedeutet, dass alle benannten Zeichenreferenzen wie © in Unicode-Zeichen konvertiert werden.


DOCTYPE-Token


Das DOCTYPE-Token hat eine eigene Struktur, die anderen Tags nicht ähnlich ist. Das Token enthält:


  1. Vorname
  2. Öffentliche Kennung
  3. Systemkennung

In modernem HTML sollte der einzige gültige / gültige DOCTYPE folgendermaßen aussehen:


 <!DOCTYPE html>

Alle anderen <!DOCTYPE> werden als <!DOCTYPE> betrachtet.


Tag-Token starten


Das Eröffnungs-Tag kann enthalten:


  1. Tag-Name
  2. Attribute
  3. Flaggen

Z.B,


 <div key="value" />

Das öffnende Tag kann ein self-closing Flag enthalten. Dieses Flag wirkt sich nicht auf das Schließen des Tags aus, kann jedoch einen Analysefehler für nicht leere Elemente verursachen.


Tag-Token beenden


Tag schließen. Es hat alle Eigenschaften des Tokens des öffnenden Tags, aber einen Schrägstrich / vor dem Tag-Namen.


 </div key="value" />

Das schließende Tag kann ein self-closing Flag enthalten, das einen Analysefehler verursacht. Der Analysefehler wird auch durch die Attribute des schließenden Tags verursacht. Sie werden korrekt analysiert, aber im Stadium des Baumbaus weggeworfen.


Kommentar-Token


Das Kommentartoken enthält den gesamten Kommentartext. Das heißt, es wird vollständig vom Stream auf das Token kopiert.


Beispiel


 <!--  -->

Zeichen-Token


Vielleicht das interessanteste Zeichen. Unicode-Token-Symbol. Kann ein (nur ein) Zeichen enthalten.


Für jedes Zeichen in HTML wird ein Token erstellt und an die Phase der Baumkonstruktion gesendet. Das ist sehr teuer.
Mal sehen, wie es funktioniert.


Nehmen Sie die HTML-Daten:


 <span> ! &reg;</span>

Was denkst du, wie viele Token für dieses Beispiel erstellt werden? Antwort: 22.


Betrachten Sie die Liste der erstellten Token:


 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

Nicht tröstlich, oder? Aber natürlich haben viele Ersteller von HTML-Parsern während der Verarbeitung tatsächlich nur ein Token. Führen Sie es in einem Kreis aus und überschreiben Sie es jedes Mal mit neuen Daten.


Lassen Sie uns weitermachen und die Frage beantworten: Warum wird das getan? Warum nicht diesen Text in einem Stück aufnehmen? Die Antwort liegt in der Bauphase des Baumes.


Ein Tokenizer ist ohne die Phase der Erstellung eines HTML-Baums nutzlos. Während des Baus eines Baumes wird der Text unter verschiedenen Bedingungen zusammengeklebt.


Die Bedingungen sind ungefähr wie folgt:


  1. Wenn ein Zeichentoken mit U+0000 ( NULL ) eintrifft, verursachen wir einen Analysefehler und ignorieren das Token.
  2. Wenn eines der Zeichen-Token U+0009 ( CHARACTER TABULATION ), U+000A ( LINE FEED (LF) ), U+000C ( FORM FEED (FF) ) oder U+0020 ( SPACE ) gekommen ist, rufen Sie den Algorithmus auf, um die aktiven Formatierungselemente und wiederherzustellen Fügen Sie den Token in den Baum ein.

Das Symbol-Token wird dem Baum gemäß dem Algorithmus hinzugefügt:


  1. Wenn die aktuelle Einfügeposition kein Textknoten ist, erstellen Sie einen Textknoten, fügen Sie ihn in den Baum ein und fügen Sie Daten aus dem Token hinzu.
  2. Andernfalls fügen Sie Daten aus dem Token zu einem vorhandenen Textknoten hinzu.

Dieses Verhalten verursacht viele Probleme. Die Notwendigkeit, dass jedes Symbol ein Token erstellt und zur Analyse an die Phase der Erstellung eines Baums sendet. Wir kennen die Größe des Textknotens nicht und müssen entweder im Voraus viel Speicher zuweisen oder Realoks erstellen. All dies ist aus Speicher- oder Zeitgründen extrem teuer.


Token für das Dateiende


Einfaches und klares Zeichen. Die Daten sind vorbei - lassen Sie sich über diese Phase des Baumbaus informieren.


Einen Baum bauen


Tree Building ist eine Zustandsmaschine mit 23 Zuständen mit vielen Bedingungen für Token (Tags, Text). Das Stadium der Baumkonstruktion ist das größte, nimmt einen erheblichen Teil der Spezifikation ein und kann auch lethargischen Schlaf und Reizungen verursachen.


Alles ist sehr einfach angeordnet. Token werden am Eingang empfangen und abhängig vom Token wird der Status der Baumkonstruktion umgeschaltet. Am Ausgang haben wir ein echtes DOM.


Probleme?


Die folgenden Probleme scheinen ziemlich offensichtlich zu sein:


Zeichen für Zeichen kopieren


Jeder Tokenizer-Status erhält an der Eingabe ein Zeichen, das er bei Bedarf kopiert / konvertiert: Tag-Namen, Attribute, Kommentare, Symbole.


Dies ist sowohl im Gedächtnis als auch in der Zeit sehr verschwenderisch. Wir sind gezwungen, für jedes Attribut, jeden Tag-Namen, jeden Kommentar usw. eine unbekannte Speichermenge vorzuweisen. Und das führt dementsprechend zu Realoks und Realoks zu Zeitverlust.


Und wenn Sie sich vorstellen, dass HTML 1000 Tags enthält und jedes Tag mindestens ein Attribut hat, erhalten wir einen höllisch langsamen Parser.


Zeichen-Token


Das zweite Problem ist das Zeichen-Token. Es stellt sich heraus, dass wir für jedes Symbol ein Token erstellen und es zum Erstellen eines Baums geben. Das Erstellen eines Baums weiß nicht, wie viele dieser Token wir haben werden, und kann nicht sofort Speicher für die erforderliche Anzahl von Zeichen zuweisen. Dementsprechend prüft hier alle gleichen Realoks + Konstanten auf das Vorhandensein eines Textknotens im aktuellen Zustand des Baumes.


Monolithisches System


Das große Problem ist die Abhängigkeit von allem von allem. Das heißt, der Tokenizer hängt vom Status des Aufbaus des Baums ab, und die Konstruktion des Baums kann den Tokenizer steuern. Und alles ist schuld an den Namespaces.


Wie werden wir die Probleme lösen?


Als nächstes beschreibe ich die Implementierung des HTML-Parsers in meinem Lexbor- Projekt sowie die Lösung aller angesprochenen Probleme.


Vorbehandlung


Wir entfernen die vorläufige Datenverarbeitung. Wir werden den Tokenizer trainieren, um den Wagenrücklauf ( \r ) als Leerzeichen zu verstehen. So wird er in die Phase des Baumbaus geworfen, wo wir es herausfinden werden.


Token


Mit einem Handgriff vereinen wir alle Token. Wir werden für alles einen Token haben. Im Allgemeinen gibt es im gesamten Analyseprozess nur ein Token.


Unser einheitliches Token enthält die folgenden Felder:


  1. Tag-ID
  2. Beginnen Sie
  3. Ende
  4. Attribute
  5. Flaggen

Tag-ID


Wir werden nicht mit der Textdarstellung des Tag-Namens arbeiten. Wir übersetzen alles in Zahlen. Die Zahlen sind leicht zu vergleichen und leichter zu bearbeiten.


Wir erstellen eine statische Hash-Tabelle aus allen bekannten Tags. Wir erstellen eine Aufzählung aus allen bekannten Tags. Das heißt, wir müssen jedem Tag einen festen Bezeichner zuweisen. Dementsprechend ist in der Hash-Tabelle der Schlüssel der Name des Tags, und der Wert wird aus der Aufzählung geschrieben.


Beispielsweise:


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

Wie Sie dem Beispiel entnehmen können, haben wir Tags für das Token END-OF-FILE für Text für ein Dokument erstellt. All dies aus Gründen der weiteren Bequemlichkeit. Wenn ich den Vorhang öffne, sage ich, dass wir im Knoten ( DOM Node Interface Knotenschnittstelle) eine Tag ID . Dies geschieht, um keine zwei Vergleiche anzustellen: den Knotentyp und das Element. Das heißt, wenn wir ein DIV Element benötigen, führen wir eine Überprüfung im Knoten durch:


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

Aber natürlich können Sie dies tun:


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

Zwei Unterstriche in LXB_TAG__ sind erforderlich, um allgemeine Tags von System-Tags zu trennen. Mit anderen Worten, der Benutzer kann ein Tag mit dem Namenstext oder dem end-of-file Wenn wir dann nach dem Tag-Namen suchen, treten keine Fehler auf. Alle System-Tags beginnen mit einem # .


Ein Knoten kann jedoch eine Textdarstellung des Tag-Namens speichern. Für 98,99999% Knoten ist dieser Parameter NULL . In einigen Namespaces müssen wir ein Präfix oder einen Tag-Namen mit einem festen Register angeben. Beispiel: baseProfile im SVG-Namespace.


Die Logik der Arbeit ist einfach. Wenn wir ein Tag mit einem klar definierten Register haben, dann:


  1. Fügen Sie es der allgemeinen Basis von Tags in Kleinbuchstaben hinzu. Holen Sie sich die Tag-ID.
  2. Fügen Sie dem Knoten die Tag-ID und den ursprünglichen Tag-Namen in der Textdarstellung hinzu.

Benutzerdefinierte Tags


Ein Entwickler kann beliebige Tags in HTML erstellen. Da wir nur die Tags haben, die wir in einer statischen Hash-Tabelle kennen, und der Benutzer jede erstellen kann, benötigen wir eine dynamische Hash-Tabelle.


Alles sieht sehr einfach aus. Wenn das Tag zu uns kommt, werden wir sehen, ob es in der statischen Hash-Tabelle ist. Wenn es kein Tag gibt, schauen wir uns das dynamische an. Wenn es kein gibt, erhöhen wir den Bezeichnerzähler um eins und fügen das Tag der dynamischen Tabelle hinzu.


Alles, was beschrieben wird, geschieht in der Phase des Tokenizers. Im Tokenizer und nach allen Vergleichen nach Tag ID (mit seltenen Ausnahmen).


Anfang und Ende


Jetzt im Tokenizer haben wir keine Datenverarbeitung mehr. Wir werden nichts kopieren und konvertieren. Wir zeigen nur auf den Anfang und das Ende der Daten.


Alle Datenverarbeitungen, wie z. B. symbolische Verknüpfungen, finden in der Phase der Baumbildung statt.
Somit kennen wir die Größe der Daten für die nachfolgende Speicherzuweisung.


Attribute


Hier ist alles genauso einfach. Wir kopieren nichts, sondern speichern einfach Zeiger auf den Anfang / das Ende des Namens und der Attributwerte. Alle Transformationen erfolgen zum Zeitpunkt der Erstellung des Baums.


Flaggen


Da wir Token vereinheitlicht haben, müssen wir das Baumgebäude irgendwie über die Art des Tokens informieren. Verwenden Sie dazu das Bitmap-Feld Flags.


Das Feld kann folgende Werte enthalten:


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

Neben dem Typ des Tokens, der geöffnet oder geschlossen wird, gibt es Werte für den Datenkonverter. Nur der Tokenizer weiß, wie die Daten korrekt konvertiert werden. Dementsprechend markiert der Tokenizer im Token, wie die Daten verarbeitet werden sollen.


Zeichen-Token


Aus dem zuvor beschriebenen können wir schließen, dass das Symbol-Token von uns verschwunden ist. Ja, jetzt haben wir einen neuen Token-Typ: LXB_HTML_TOKEN_TYPE_TEXT . Jetzt erstellen wir ein Token für den gesamten Text zwischen den Tags und markieren, wie er in Zukunft verarbeitet werden soll.


Aus diesem Grund müssen wir die Bedingungen für die Konstruktion des Baumes ändern. Wir müssen ihn trainieren, nicht mit symbolischen Token, sondern mit Text-Token zu arbeiten: konvertieren, unnötige Zeichen löschen, Leerzeichen überspringen und so weiter.


Aber es gibt nichts Kompliziertes. In der Phase des Baumbaus sind die Änderungen minimal. Aber der Tokenizer stimmt jetzt überhaupt nicht mehr mit der Spezifikation des Wortes überein. Aber wir brauchen ihn nicht, es ist normal. Unsere Aufgabe ist es, einen HTML / DOM-Baum zu erhalten, der den Spezifikationen vollständig entspricht.


Tokenizer-Stufen


Um eine schnelle Datenverarbeitung im Tokenizer sicherzustellen, fügen wir jeder Stufe unseren Iterator hinzu. Gemäß der Spezifikation akzeptiert jede Stufe ein Symbol für uns und trifft je nach angekommenem Symbol Entscheidungen. Aber die Wahrheit ist, dass es sehr teuer ist.


Um beispielsweise von der Stufe ATTRIBUTE_VALUE Stufe ATTRIBUTE_NAME zu ATTRIBUTE_VALUE müssen Sie im Attributnamen einen Leerraum finden, der das Ende angibt. Gemäß der Spezifikation sollten wir der Stufe ATTRIBUTE_NAME nach Zeichen ATTRIBUTE_NAME bis ein Leerzeichen ATTRIBUTE_NAME und diese Stufe nicht zu einer anderen wechselt. Dies ist sehr teuer, normalerweise wird es durch einen Funktionsaufruf für jedes Zeichen oder einen Rückruf wie "tkz-> next_code_point ()" implementiert.


Wir fügen der Stufe ATTRIBUTE_NAME eine Schleife ATTRIBUTE_NAME und übergeben den gesamten eingehenden Puffer. In der Schleife suchen wir nach den Symbolen, die wir wechseln müssen, und arbeiten weiter an der nächsten Stufe. Hier bekommen wir viele Gewinne, sogar Compiler-Optimierungen.


Aber! Das Schlimmste ist, dass wir dadurch die Unterstützung von Brocken (Brocken) aus der Schachtel gerissen haben. Dank der zeichenweisen Verarbeitung in jeder Phase des Tokenizers hatten wir Unterstützung für Chunks, und jetzt haben wir sie gebrochen.


Wie kann ich das beheben? Wie implementiere ich Unterstützung für Chunks ?! Es ist ganz einfach, wir führen das Konzept der eingehenden Puffer (Incoming Buffer) ein.


Eingehender Puffer


Oft analysiert HTML in Blöcken. Zum Beispiel, wenn wir Daten über das Netzwerk empfangen. Um nicht untätig zu bleiben, während auf die verbleibenden Daten gewartet wird, können wir bereits empfangene Daten zur Verarbeitung / Analyse senden. Natürlich können Daten überall zerrissen werden. Zum Beispiel haben wir zwei Puffer:


Zuerst


 <div clas

Zweitens


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

Da wir in der Tokenisierungsphase nichts kopieren, sondern nur Zeiger auf den Anfang und das Ende der Daten nehmen, haben wir ein Problem. Zeiger auf verschiedene Benutzerpuffer. Angesichts der Tatsache, dass Entwickler häufig denselben Puffer für Daten verwenden, handelt es sich um einen Zeiger auf den Anfang nicht vorhandener Daten.


.
:


  1. (Incoming Buffer).
  2. ( ) , ? , . , . 99% .

" " . .


, . , ( ) . . , , , . .


:


, . , : . . ( ), . .


: . , .



.


, . , .


So sieht es aus:



 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>

Die HTML-Spezifikation (im Abschnitt zum Erstellen von Bäumen) befasst sich mit dem Tag sarcasm. Ich habe mehr als einmal gesehen, wie Parser-Entwickler die Verarbeitung dieses Tags blind eingeschaltet haben.


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

Spezifikationsschreiber scherzen.



HTML DOM/HTML Interfaces HTML/DOM HTML .


, :


  1. ( )

    • Incoming Buffer
    • Tag ID
    • ̆ : , N+
    • ̆
    • ̈


i7 2012 , , 235MB (Amazon-).


, 1.5/2 , . , . , CSS (Grammar, , Grammar). HTML, CSS , "".


Quellcode


HTML Lexbor HTML .


PS


CSS Grammar. , . - 6-8 .


,

Fühlen Sie sich frei, das Projekt zu helfen. Zum Beispiel, wenn Sie in Ihrer Freizeit Dokumentation schreiben möchten.
Fühlen Sie sich frei, das Projekt in Rubel zu unterstützen (ich werde auch nicht von anderen Währungen beleidigt sein). Darüber in PM.


Vielen Dank für Ihre Aufmerksamkeit!

Source: https://habr.com/ru/post/de430736/

More articles:


All Articles