Limits and hostile input

If you parse pages you didn't write, some of them will be built to hurt you, and some will hurt you by accident. This page covers the two limits Parsec gives you, which inputs it handles in linear time and why, and where it doesn't yet.

On this page: The problem · The two limits · Inputs that stay linear · Why those stay linear · Where it isn't linear yet · Fuzzing

The problem

The HTML Standard's tree builder does real work per tag. Asking whether a <p> is "in button scope" means walking the stack of open elements; the adoption agency algorithm, which repairs misnested formatting like <b><i></b></i>, walks the list of active formatting elements and the stack; reconstructing formatting after a block can clone a whole list of elements. Each of those is cheap on a normal page and costs time proportional to depth or list length on a page made of nothing but nesting. Multiply that by the number of tags and you get a parser whose time grows with the square of the input.

Here's the arithmetic. Say a page is $n$ nested tags, and the $k$-th tag costs a walk down a stack $k$ elements deep. The whole parse then costs

$$1 + 2 + \cdots + n = \frac{n(n+1)}{2},$$

which is quadratic: double $n$ and the time goes up four times. If each tag costs a constant $c$ instead, however deep the stack, the parse costs $cn$, and doubling the page only doubles the time. The rest of this page is about keeping Parsec on the $cn$ side.

Lexbor shows what that looks like. In lexbor#340, <b>×n <i>×n x</b>×n takes 29 seconds at n = 4,000 (82 KB), and at n = 10,000 (208 KB) it ran a 32 GB machine out of memory after about ten minutes; 40,000 nested <div>s (200 KB) take 1.7 seconds, from an unbounded walk in lxb_html_tree_element_in_scope(). The same thread notes that Gumbo caps nesting at 400 and that Chromium caps it too. Lexbor has no limit option of any kind.

The two limits

A time budget

parse_with takes an Options::budget. When it runs out, you get ParseError::Timeout { budget, parsed } and no document. Parsing has the details: the clock is checked every 4,096 steps of the tokenizer, so the limit is approximate, and the partial tree is thrown away.

Tip

If you crawl, set one.

Pick it from what a page is worth to you, not from what parsing usually takes; a normal page finishes far inside any budget you'd choose, so the budget only ever fires on the pages you'd want to drop anyway.

use parsec::{Options, ParseError, parse_with};
use std::time::Duration;

fn parse_untrusted(html: &str) -> Option<parsec::Document> {
    let options = Options {
        budget: Some(Duration::from_secs(1)),
        ..Options::default()
    };
    match parse_with(html, options) {
        Ok(doc) => Some(doc),
        Err(ParseError::Timeout { parsed, .. }) => {
            eprintln!("dropped a page after {parsed} bytes");
            None
        }
        Err(ParseError::TooLarge { len }) => {
            eprintln!("dropped a {len}-byte page");
            None
        }
    }
}

fn main() {
    assert!(parse_untrusted("<p>hello").is_some());
}

parse and parse_fragment have no budget. There's no budgeted fragment parse yet.

A size cap

MAX_INPUT is 536,870,912 bytes (512 MiB). Over that, parse_with returns ParseError::TooLarge and parse and parse_fragment panic. It exists because strings are stored as 32-bit offsets with flag bits on top (Architecture), not as a memory policy. If you want a smaller cap, check html.len() yourself before parsing.

There's no memory limit and no depth limit. Memory grows with the input: the document reserves space in proportion to the input's length up front (about one node per 24 bytes, plus buffers), then grows as needed. A depth limit that behaves as Chromium's does, adding elements past the limit as siblings instead of children, is planned in #10.

Inputs that stay linear

crates/parsec/examples/hostile.rs builds eight inputs designed to be slow and times each one.

The eight hostile inputs, with their sizes

Name	Input	Size
unclosed divs	<div> × 80,000	390 KB
unclosed tables	<table> × 40,000	273 KB
nested inline	<span> × 80,000	468 KB
formatting then paragraphs	300 distinct <b class=cN> tags, then <p>x × 3,000	15 KB
distinct formatting per p	<p><b><i><u><s><em><strong><tt><code><big><small><strike> × 5,000	278 KB
misnested a	<a><p><a>x</p> × 20,000	273 KB
adoption	<b><div><b><div> × 10,000	156 KB
table foster	<table> then x<td>y × 50,000	292 KB

Run it with:

cargo run --release --example hostile

It prints each input's size, the time and the node count. Doubling or quadrupling any of these doubles or quadruples the time, give or take noise: the cost is linear in the input.

Why those stay linear

The spec's algorithms are the same in every parser; what differs is how much each step costs. Parsec's tree builder (crates/parsec/src/tree.rs) keeps a little extra state so that the common worst cases are constant-time per tag:

• Counts of open elements by tag. The builder keeps, for each of its 124 known tags, how many HTML elements of that tag are open. "Is there a <p> in button scope?" is answered at once when no <p> is open at all, however deep the stack, which is what makes 80,000 unclosed <div>s cheap. (counts, and in_scope.)
• A flag per node for "on the stack of open elements". Reconstructing active formatting elements and the adoption agency both ask whether an element is still open. That's one lookup instead of a walk down the stack. (on_stack, and open_contains.)
• The spec's own bounds, kept. The adoption agency's outer loop runs at most 8 times and its inner loop drops formatting elements after the third, as the spec says, and the "Noah's Ark" clause keeps at most three identical formatting elements after the last marker. These are what stop <b> repeated thousands of times from rebuilding thousands of elements at every paragraph.
• Text that doesn't get copied again and again. When text is added to a text node whose string isn't at the end of the parse buffer, the string moves to an allocation of its own once, rather than being copied to the end on every append. Without that, <body x> repeated between runs of text made memory grow with the square of the input; there's a test for it in tree.rs's hostile module. (Document::append_text in dom.rs.)

And outside the tree builder:

• No recursion where depth comes from the page. Serialization, text and select walk the tree with their own stack or with the tree's links, so a tree tens of thousands of levels deep doesn't overflow a thread's stack. A test serializes 20,000 nested <div>s on a 256 KB stack.
• A nesting limit on selectors. Selector parsing and matching do recurse, so functional pseudo-classes nest at most 32 deep (see Selectors).

Where it isn't linear yet

Not every input is. Some patterns still make the tree builder walk the stack of open elements, or an element's ancestors, for every tag, as the spec describes those steps: certain kinds of end tags under very deep nesting are the main ones. On those, time grows with depth multiplied by the number of tags, as it does in Lexbor and in any parser that follows the algorithm step by step without a depth limit.

Two things protect you today: the time budget, which turns a slow page into an error, and the size cap. The depth limit in #10 is the planned fix, and new inputs that turn out slow go into hostile.rs with the fix that makes them linear.

Caution

Found an input that's slow? Please report it privately, as SECURITY.md describes, rather than in a public issue.

Fuzzing

A fuzz target (crates/parsec/fuzz/fuzz_targets/parse.rs) parses arbitrary bytes, lossily decoded, as a document and as a fragment in one of 13 contexts, with scripting on or off, and checks that every node is reached from the root exactly once and that every child's parent link agrees. CI runs it nightly for five minutes on inputs of up to 4,096 bytes. Contributing shows how to run it yourself.

See also

• Parsing, for parse_with and its options.
• Architecture, for where the extra state lives.
• Thread safety and memory safety, for the panics you can cause.