servo/html5ever

High-performance browser-grade HTML5 parser

html5ever

API Documentation

html5ever is an HTML parser developed as part of the Servo project.

It can parse and serialize HTML according to the WHATWG specs (aka "HTML5"). However, there are some differences in the actual behavior currently, most of which are documented in the bug tracker. html5ever passes all tokenizer tests from html5lib-tests, with most tree builder tests outside of the unimplemented features. The goal is to pass all html5lib tests, while also providing all hooks needed by a production web browser, e.g. document.write.

Note that the HTML syntax is very similar to XML. For correct parsing of XHTML, use an XML parser (That said, many XHTML documents in the wild are serialized in an HTML-compatible form).

html5ever is written in Rust, therefore it avoids the notorious security problems that come along with using C. Being built with Rust also makes the library come with the high-grade performance you would expect from an HTML parser written in C. html5ever is basically a C HTML parser, but without needing a garbage collector or other heavy runtime processes.

Getting started in Rust

Add html5ever as a dependency in your Cargo.toml file:

[dependencies]
html5ever = "0.26"

You should also take a look at examples/html2html.rs, examples/print-rcdom.rs, and the API documentation.

Getting started in other languages

Bindings for Python and other languages are much desired.

Working on html5ever

To fetch the test suite, you need to run

git submodule update --init

Run cargo doc in the repository root to build local documentation under target/doc/.

Details

html5ever uses callbacks to manipulate the DOM, therefore it does not provide any DOM tree representation.

html5ever exclusively uses UTF-8 to represent strings. In the future it will support other document encodings (and UCS-2 document.write) by converting input.

The code is cross-referenced with the WHATWG syntax spec, and eventually we will have a way to present code and spec side-by-side.

html5ever builds against the official stable releases of Rust, though some optimizations are only supported on nightly releases.

html5ever's Issues

Revisit tokenizer microoptimizations

For example, there's an old branch to use SSE 4.2 string instructions in tokenization, which realized a speedup of about 10% and could probably be pushed much further.

Did not compile with latest rustc

➜ parser git:(master) ✗ cargo build
Compiling html5ever v0.0.0 (https://github.com/kmcallister/html5ever#974b5ac1)
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:41:1: 43:2 error: the parameter type Handle may not live long enough; consider adding an explicit lifetime bound Handle:'a...
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:41 pub struct ActiveFormattingIter<'a, Handle> {
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:42 iter: Rev<Enumerate<slice::Items<'a, FormatEntry>>>,
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:43 }
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:41:1: 43:2 note: ...so that the reference type core::slice::Items<'a,tree_builder::types::FormatEntry<Handle>> does not outlive the data it points at
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:41 pub struct ActiveFormattingIter<'a, Handle> {
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:42 iter: Rev<Enumerate<slice::Items<'a, FormatEntry>>>,
/Users/mac/.cargo/git/checkouts/html5ever-122db04116ffdbdc/master/src/tree_builder/actions.rs:43 }
error: aborting due to previous error
Could not compile html5ever.

➜ parser git:(master) ✗ rustc -v
rustc 0.12.0-nightly (9a2286d3a 2014-10-03 07:33:26 +0000)

Add serializer tests

Write C bindings for the tree builder

Switch to Cargo

Integrate with html-parsers-benchmark

https://github.com/seriyps/html-parsers-benchmark

I believe @Ygg01 made some progress on this.

We can add Hubbub and Gecko's C++ parser as well.

Implement parsing for <isindex>

If we really have to. It's an obscure feature, deprecated as hell, and really messy.

Accept raw bytes

Reads from the network will not necessarily align with UTF-8 codepoint boundaries.

Switch to Criterion.rs for benchmarking

Especially if bheisler/criterion.rs#23 is implemented.

C API

We should have a C API. Then any language can call into a high-performance, memory-safe HTML parser.

Implement the "XML5" syntax

A parser for well-formed XML 1.0 is a very different beast from a HTML parser. But there's this XML5 spec that is quite similar to HTML parsing and could re-use a lot of the machinery, if not the actual parse rules. Servo could potentially use this for all XML parts of the Web platform. See servo/servo#3319.

Implement character encoding detection / conversion

See the HTML spec and the WHATWG Encoding spec. This also entails noticing <meta charset=...> and <meta http-equiv="Content-Type"> as we parse.

Document the C API

There are lots of details such as pointer ownership and character encoding.

Docs aren't updating

Do fewer linear searches of element stacks

e.g. the open elements or active formatting elements. We search these when looking for elements in various scopes, and #77 adds more.

We could track open elements with a bitvector for each scope. Checking if one of a set of elements is open in a particular scope would be a simple bitmask test. We can choose bit patterns to match the static atom indices as well.

We should find an abstraction that makes it hard to screw up the book-keeping.

html5ever uses #![no_std] but depends on phf which links std

It's not clear how big of an issue this is, but html5ever itself is still ultimately linking against std due to rust-phf's use of std.

Implement parsing of <template>

It has a bunch of special parsing rules :/

Finish implementing, and test, the fragment cases in parsing

Right now there is code in tests/tree_builder.rs to ignore the fragment-case tests.

High-priority / blocking Rust issues

None at present!

Implement the rest of misnested tag recovery

Adoption agency algorithm, foster parenting, reconstruct formatting, etc.

Speculative parsing and tokenization

Similar to servo/servo#1009

The first step is speculative parsing concurrent with scripts, similar to what Gecko does.

Rust issue tracking

rust-lang/rust#15609: Autoderef chooses deref() when deref_mut() is needed for ref mut pattern
rust-lang/rust#16617: Syntactic context discarded when quoting a macro invocation
rust-lang/rust#18043: Bencher::iter should support per-iteration setup

Add stability attributes throughout the library

Handle qualified tag and attribute names in serialization

Replace int/uint with isize/usize or explicit sizes

Implement tokenization of CDATA sections

These can only appear in MathML and SVG (see #8, #9)

Add the C API to the automated test suite

Right now we build but do not test it.

Implement parsing for MathML

Switch back to std imports and drop #![no_std]

After rust-lang/rust#19654 lands, there's no reason to avoid std in libraries used from C.

Use iterators for tokenizer lookahead

Provide hooks Servo needs to implement the document lifecycle

This covers things like <script async>, <script defer>, DOMContentLoaded and onload, session history and its interaction with document.open and document.write. See servo/servo#1879.

Related to #6 (document.write).

Support document.write

See servo/servo#3704.

The argument to document.write is a sequence of UCS-2 code units and we need a way to interface this with the UTF-8 parser. My plan is:

(Edit: Largely superseded by this proposal)

• Convert to UTF-8 as soon as possible.
• Convert invalid surrogate sequences to U+FFFD 'REPLACEMENT CHARACTER'. This is a deviation from the spec, but nobody has objected strongly in the course of various discussions. There was even talk of amending the spec to allow this behavior, since it's currently written under the assumption that all parsers use UCS-2 natively.
• If a document.write input ends with a leading surrogate, we can't convert it yet, so save this single u16 in the BufferQueue alongside the UTF-8 buffers.
• If a document.write input starts with a trailing surrogate, and there's a saved leading surrogate in the BufferQueue, then replace both with the appropriate Unicode character as UTF-8.
• If the parser receives any other input and there's a saved leading surrogate, drop the saved surrogate and prepend U+FFFD to the input. (This means that a script split an invalid surrogate sequence across multiple document.write calls, or wrote a lone leading surrogate and then finished.)

Implement all the details of handling </script>

See also #7.

Make Namespace a newtype around Atom

After discussion with @SimonSapin we concluded that there's no reason for a custom enum. An HTML parser can only output a fixed set of namespaces, but XHTML parsing and DOM manipulation can produce arbitrary namespaces, so Servo must represent namespaces as interned strings anyway.

I think we still want Namespace to be a separate type, not a synonym, so that it's harder to mix up namespaces and other atoms. (Does that mean we should also have e.g. TagName and AttrName newtypes?)

HTML test case reducer

An automated test case reducer in the style of C-Reduce would be a useful demo/application for this library.

Use Cargo for tests, examples, benchmarks

build errors with html5ever as cargo crate

rustc 0.13.0-nightly (6f4c11be3 2014-12-05 20:23:10 +0000)
cargo 0.0.1-pre-nightly (da789a6 2014-11-30 08:14:16 +0000)

Steps to Reproduce

cargo new project --bin
cd project

Add html5ever to Cargo.toml

[dependencies.html5ever]
git = "https://github.com/servo/html5ever"

Add html5ever to main.rs

#![feature(phase)]

extern crate html5ever;
use html5ever::sink::common::{Document, Doctype, Text, Comment, Element};

Attempt build

cargo build
    Updating registry `https://github.com/rust-lang/crates.io-index`
   Compiling html5ever_macros v0.0.0 (https://github.com/servo/html5ever#e7f74b65)
   Compiling time v0.1.0
   Compiling string_cache_macros v0.0.0 (https://github.com/servo/string-cache#40f25a17)
/Users/ozten/.cargo/git/checkouts/html5ever-1ab8707684fb3258/master/macros/src/named_entities.rs:37:9: 37:21 error: unresolved enum variant, struct or const `Object`
/Users/ozten/.cargo/git/checkouts/html5ever-1ab8707684fb3258/master/macros/src/named_entities.rs:37         json::Object(m) => m,
                                                                                                            ^~~~~~~~~~~~
error: aborting due to previous error
   Compiling phf v0.2.0
/Users/ozten/.cargo/git/checkouts/string-cache-628f0438d3df3ef7/master/macros/src/atom/mod.rs:18:25: 18:30 error: unresolved import `std::slice::Found`. There is no `Found` in `std::slice`
/Users/ozten/.cargo/git/checkouts/string-cache-628f0438d3df3ef7/master/macros/src/atom/mod.rs:18 use std::slice::{Items, Found, NotFound};
                                                                                                                         ^~~~~
/Users/ozten/.cargo/git/checkouts/string-cache-628f0438d3df3ef7/master/macros/src/atom/mod.rs:18:32: 18:40 error: unresolved import `std::slice::NotFound`. There is no `NotFound` in `std::slice`
/Users/ozten/.cargo/git/checkouts/string-cache-628f0438d3df3ef7/master/macros/src/atom/mod.rs:18 use std::slice::{Items, Found, NotFound};
                                                                                                                                ^~~~~~~~
error: aborting due to 2 previous errors
Build failed, waiting for other jobs to finish...
Could not compile `html5ever_macros`.

To learn more, run the command again with --verbose.

I'm new to using cargo, so maybe I'm doing something wrong. The README states that this project tracks nightly Rust. Thanks for your help!

Add a method to get a Node's index in its parent's children in RcDom

A private function to calculate it already exists here, and I need access to this info to get the next/previous sibling of a Node for a project I'm working on.

I'll be happy to submit a pull request if you could tell me where is the best place to add this.

Display code next to spec

Many parts of the parser code closely match sections of the HTML5 syntax spec. We should include machine-readable comments describing this correspondence, and then generate a HTML document with syntax-highlighted Rust code next to spec excerpts.

Use associated items to clean up the API

The std lib uses them now, so it's about time.

Use string-cache for interning

Use string-cache for interning, and port our interning macros to it.

Fix scripts/bench-branches.py

It uses the removed libtest --save-metrics feature. See 22a97c2 and rust-lang/rust#19145.

Provide hooks for application cache selection

A browser runs the application cache selection algorithm when the parser sees <html manifest=...>.

Build on Rust stable branch

Not for 1.0 necessarily, but at some point in 1.x.

The biggest obstacle is syntax extensions. I have no clever ideas there except running rustc-nightly --pretty expanded and shipping that as the 1.x "source".

We should catalog all of the other obstacles here.

Servo itself will be on nightlies for a looooong time.

Provide source spans for tokens and DOM nodes

We can use something like libsyntax's Span and Spanned types to track positions in the input stream.

The tokenizer will remember its current position and the position at certain events, e.g. start tag, start attribute name. The tree builder will call a tree sink method (with an empty default) to annotate the DOM with span information.

Then we can write a command-line HTML validator with the same output UI as rustc :)

Note that eventually it will be possible for a single document's nodes to come from multiple text sources, e.g. with document.write.

Benchmark the C API

Quantify the overhead of the extra indirection, the virtual calls, etc.

Consider small vector optimization for CharacterTokens

The tokenizer often emits one character at a time.

Publish binaries (or LLVM IR?) for the library

So it can be used from C without a local Rust compiler, especially in the interim period before rustc 1.0 makes it into popular OS distributions.

Implement parsing for SVG

Implement a parent-ownership DOM

This would be another built-in TreeSink, suitable for simple static parsing tasks, and potentially faster than RcDom.

During parsing, the TreeSink operates on

type TentativeNodePtr = *mut UnsafeCell<TentativeNode>;

struct TentativeNode {
    node: NodeEnum,
    parent: TentativeNodePtr,
    children: Vec<TentativeNodePtr>,
    // plus kind opt-out markers?
}

The TentativeNodes are allocated and owned by the TreeSink itself. They all live as long as the TreeSink does, so reference counting is not necessary.

The get_result method consumes the TreeSink and transmutes the root node to

pub struct Node {
    pub node: NodeEnum,
    _parent_not_accessible: uint,
    pub children: Vec<Box<Node>>,
}

thus transferring ownership of each node to its parent, without actually doing anything at runtime. get_result then walks the tree once and destroys any TentativeNodes that didn't make it into the final tree.

We should statically assert that the respective layouts of TentativeNode and Node are really compatible.