Architecture

This page is for anyone who wants to know how Parsec is put together, whether to contribute or to judge whether it'll hold up. It follows a parse from the call to the finished tree, then covers the layout of a document, and says which file each piece lives in.

On this page: The files · From a string to a tree · The document's layout · Selectors · Serialization

The files

Everything is in one crate, crates/parsec, whose library is called parsec. Here's how the pieces fit together, with the file each one lives in:

flowchart TD
    bytes["Your bytes"] -->|"you decode them"| str["Text, as a str"]
    str --> pre["Preprocessing<br/>tokenizer.rs"]
    pre --> tok["Tokenizer<br/>tokenizer.rs"]
    tok -->|"one call per token"| tb["Tree builder<br/>tree.rs"]
    tb -.->|"switch text mode"| tok
    tb -->|"builds"| doc["Document arena<br/>dom.rs"]
    edit["Edits<br/>edit.rs"] -->|"change"| doc
    doc --> sel["Selectors<br/>css.rs"]
    doc --> ser["Serializer<br/>serialize.rs"]

Loading

Parsec doesn't decode bytes yet, so the first arrow is yours to draw: Parsing says how, and #5 is the plan to take it over.

File	Holds
src/lib.rs	The public re-exports, and named_reference, tag_number and is_html_element.
src/tokenizer.rs	The tokenizer (13.2.5 of the HTML Standard): 63 states, Sink, Tag, Attrs, Doctype, TextMode, preprocess.
src/tree.rs	The tree builder (13.2.6): 21 insertion modes, the stack of open elements, the list of active formatting elements, the adoption agency, foster parenting, foreign content, <select> and <selectedcontent>, plus parse, parse_with, parse_fragment, Options and ParseError.
src/dom.rs	Document and its storage, Kind, Ns, AttrNs, Quirks, MAX_INPUT, and every read-only method.
src/edit.rs	Every method that changes a document, and EditError.
src/serialize.rs	The fragment serialization algorithm (13.3) and text.
src/css.rs	The selector parser and matcher.
src/tags.rs	The 124 tag names the tree builder treats specially, as a u8 enum, with a hash table to look names up.
src/entities.rs	The 2,231 named character references, generated from the spec's entities.json by scripts/gen-entities.py, sorted for binary search.

From a string to a tree

Here's what parse_with(html, options) does, in tree.rs's run:

1. Size check. Over MAX_INPUT bytes, it returns ParseError::TooLarge before doing anything else.
2. A builder sized to the input. TreeBuilder::new makes an empty Document whose vectors are reserved in proportion to the input's length: about one node per 24 bytes, one attribute per 32, and a string buffer an eighth of the input. Most pages then parse without the vectors ever growing.
3. Preprocessing into the document. tokenizer::preprocess turns \r\n and \r into \n, and the result is stored in the document as a Box<str>. This is the document's copy of its source.
4. The one unsafe block. The tokenizer needs to read that source while the builder, which owns the document, is borrowed mutably as the tokenizer's sink. source() hands the tokenizer a reference to the boxed string that the borrow checker can't see is safe. It is safe because the box's contents never move or change while the parse runs, and the reference doesn't outlive run. Thread safety and memory safety has the reasoning in full.
5. Fragment setup, for parse_fragment: a context element, an <html> root on the stack, the insertion mode reset from the context, and the tokenizer's starting state picked from the context's name.
6. The deadline, if there's a budget.
7. Tokenizing. Tokenizer::run drives the whole parse. TreeBuilder implements Sink, so every token goes straight into tree construction as it's read; there's no token queue. When an insertion mode decides the tokenizer should switch to RCDATA, RAWTEXT, script data or PLAINTEXT (after <title>, <style>, <script>, <plaintext>), it returns that mode from start_tag. When the tokenizer meets <![CDATA[, it asks cdata_allowed, and the builder answers from the adjusted current node's namespace.
8. Finishing. A timeout drops the document and returns ParseError::Timeout. A fragment parse moves the <html> element's children up to the root and turns the root into a Fragment node. Then the document is returned.

Step 7 is where the two halves meet, and it's easier to see than to describe. Take <p>Hi<title>a<b></title>:

sequenceDiagram
    participant T as Tokenizer
    participant B as TreeBuilder, the Sink
    T->>B: start_tag(p)
    B-->>T: None, so keep reading markup
    T->>B: text(Hi), a slice of the input
    T->>B: start_tag(title)
    B-->>T: Some(Rcdata), so tags are text now
    T->>B: text(a), then the b tag as plain text
    T->>B: end_tag(title), which ends RCDATA
    T->>B: eof()

Loading

There's no queue in between: each call returns before the tokenizer reads another byte, so the builder's answer to start_tag decides how the very next character is read.

The tokenizer

The tokenizer has the whole input up front, so it doesn't need the spec's temporary buffer: where the spec buffers characters to decide later, it looks ahead. Runs of text are found with memchr, and text is passed to the sink as slices of the input whenever nothing in the run needed changing. A fast path reads plain tags (lowercase names, attribute values without references or NULs) in one pass, falling back to the state machine from the same place for anything else; a test in tokenizer.rs checks the two read 20,000 random tag-soup inputs the same way. Attribute names and values, and tag names, are slices of the input too when they're already lowercase and unchanged.

The tree builder

TreeBuilder::process is the spec's tree construction dispatcher: it sends each token to the HTML rules for the current insertion mode, or to the rules for foreign content. The insertion modes are methods named after the spec's (in_body, in_table_text, after_after_frameset...). There's no "in select" mode: Parsec follows the standard's current, relaxed <select> parsing, including <selectedcontent>, which gets a copy of the selected <option>'s children when that option is closed.

Some state is kept beyond what the spec describes, to keep common worst cases fast; Limits and hostile input explains each piece:

• open: Vec<Open>, the stack of open elements, each entry carrying its namespace and tag number so scope checks never touch the nodes;
• counts, how many HTML elements of each tag are open;
• on_stack, a flag per node for "is it open";
• active: Vec<NodeId>, the list of active formatting elements, with markers stored as NONE.

The adoption agency

The adoption agency algorithm repairs misnested formatting, turning <b>1<p>2</b>3</p> into <b>1</b><p><b>2</b>3</p>. It's TreeBuilder::adoption_agency in tree.rs, run for end tags of a, b, big, code, em, font, i, nobr, s, small, strike, strong, tt and u, and for <a> and <nobr> start tags that find one already open. It follows the spec's steps: up to 8 rounds of the outer loop; find the formatting element in the active list after the last marker; find the furthest block, the first special element above it on the stack; walk back down with the inner loop, cloning formatting elements that are still active and dropping them from the list after the third round; move the furthest block's children into a new clone of the formatting element; and fix the stack and the list, keeping the bookmark's place. When there's no formatting element to adopt, it returns true and the end tag is handled as "any other end tag".

A clone made here (or when formatting is reconstructed) shares its original's attribute list rather than copying it. That's why attribute edits always copy the list first; see Editing.

Foster parenting and the insertion point

TreeBuilder::place is the spec's "appropriate place for inserting a node". With foster parenting on and a table-related element as the target, it finds the last <table> or <template> on the stack and inserts before the table (or into the template, or into the element below the table if the table has no parent). A <template> target always means its contents node. Text that ends up beside an existing text node is appended to it rather than added as a new node.

Foreign content

SVG and MathML follow the spec's "rules for parsing tokens in foreign content" (TreeBuilder::foreign):

• Breaking out. A start tag from the spec's list (b, div, p, table, ul, font with color, face or size, and the rest), or an end tag </br> or </p>, pops elements until the current node is HTML, a MathML text integration point or an HTML integration point (break_out), then is reprocessed as HTML.
• Integration points. SVG foreignObject, desc and title are HTML integration points. MathML mi, mo, mn, ms and mtext are text integration points. A MathML annotation-xml is an HTML integration point when its encoding is text/html or application/xhtml+xml, in any case; the element records that when it's created, so the dispatcher can check it without rereading attributes.
• Names. SVG element names get their case back from a table of 37 (clipPath, foreignObject...), and SVG attribute names from a table of 58 (viewBox, gradientUnits...). Element names are fixed when the element is made. Attribute names are stored lowercase and their case is put back when they're read through attrs_written or serialized. The 11 namespaced attributes (xlink:href, xml:lang, xmlns:xlink...) get their AttrNs.
• Everything else. A self-closing start tag is popped at once; NUL characters become U+FFFD; and an end tag walks down the stack comparing names without ASCII case until it reaches an HTML element.

The document's layout

Document (dom.rs) is a few vectors:

Field	Holds
nodes: Vec<Node>	Every node. Each has parent, first_child, last_child, prev and next as u32 indexes (with u32::MAX for none) and its data: document, fragment, doctype, element, text, comment, processing instruction or CDATA.
src: Box<str>	The preprocessed input.
buf: String	Strings the parser had to make: decoded text and values, lowercased names.
extras: Vec<String>	Strings with an allocation each: everything an edit adds, and text the parser had to keep growing after something else was written to buf.
attrs: Vec<Attr>	Every attribute of every element. An element holds a range into it.
quirks, scripting	The mode, and whether the parse had scripting on (which the serializer needs for <noscript>).

An element stores its namespace, its tag number, its name (one of: the known tag's own name, an index into the SVG case table, or a string), its attribute range, its template contents node if it's a template, and the annotation-xml flag.

So a document is built with a handful of allocations rather than one per node, and dropping it frees a handful of blocks. Walking it is index arithmetic on a vector, which is friendly to the cache.

Spans into the source

Every string in a node is a Span { start: u32, end: u32 }, and two high bits say where it lives:

• bit 31 set: a range of src, the document's copy of the input;
• bit 30 set (and 31 clear): start is an index into extras;
• neither: a range of buf.

When the tree builder stores a string, it checks whether the string is a slice of src by comparing pointers. If it is (most text, most attribute values, most names on a typical page), the span points straight into the source and nothing is copied. That's also why offsets have to fit in 30 bits, and why MAX_INPUT is 2²⁹ bytes, leaving headroom for buf.

These spans are also the start of source positions: a text node that came straight from the input already knows its byte range. Exposing positions for every node and attribute is planned in #8.

Selectors

css.rs parses a selector into a SelectorList, a list of complex selectors. Each complex selector is stored right to left: the subject compound first, each with the combinator to the next one. Matching (Cx::complex) tests the subject, then follows combinators outward: up through parents for descendant and child, back through element siblings for + and ~. A :has() argument is a relative selector with an anchor compound at its left end; Cx::has searches the anchor's subtree, or its later siblings and their subtrees, for an element that matches with the anchor in place. Type selectors on HTML elements compare tag numbers when the name is a known tag, and strings otherwise.

Serialization

serialize.rs writes with an explicit stack of (node, is_end_tag) pairs instead of recursion, so the depth of the tree never touches the thread's stack. text and select walk without recursion too.

See also

• Limits and hostile input, for the extra state that keeps worst cases linear.
• Thread safety and memory safety, for the one unsafe block in full.
• Glossary, for the spec's terms used here.