Tree builder is O(n²) in nesting depth with no depth cap: 512 KB of <ul><li> takes 94 s

[mnaza]

Summary

Parsing time grows quadratically with element nesting depth, and nothing caps the depth. For input a parser might receive from the network, a few hundred KB of nested <div> or <ul><li> is seconds to minutes of CPU. Browsers bound this: Chromium/WebKit stop nesting at 512 (kMaximumHTMLParserDOMTreeDepth / maximumHTMLParserDOMTreeDepth) and attach deeper elements to the nearest allowed ancestor.

Reproduction

html5ever = "=0.39.0", markup5ever_rcdom = "0.39.0+unofficial", cargo run --release:

use html5ever::tendril::TendrilSink;
use html5ever::{parse_document, ParseOpts};
use markup5ever_rcdom::RcDom;
use std::time::Instant;

fn parse(html: &str) {
    let _ = parse_document(RcDom::default(), ParseOpts::default())
        .from_utf8()
        .read_from(&mut html.as_bytes())
        .unwrap();
}

fn main() {
    let shapes: [(&str, fn(usize) -> String); 3] = [
        ("<div>", |n| format!("{}x{}", "<div>".repeat(n), "</div>".repeat(n))),
        ("<ul><li>", |n| format!("{}x", "<ul><li>".repeat(n))),
        ("<b>", |n| format!("{}x", "<b>".repeat(n))),
    ];
    for (name, mk) in shapes {
        for n in [4_000usize, 16_000, 64_000] {
            let html = mk(n);
            let t = Instant::now();
            parse(&html);
            println!("{name:<9} n={n:>6}  bytes={:>7}  {:>10.3?}", html.len(), t.elapsed());
        }
    }
}

Output (release build, x86_64 Linux):

<div>     n=  4000  bytes=  44001    68.720ms
<div>     n= 16000  bytes= 176001   959.590ms
<div>     n= 64000  bytes= 704001     15.552s
<ul><li>  n=  4000  bytes=  32001   160.128ms
<ul><li>  n= 16000  bytes= 128001      2.746s
<ul><li>  n= 64000  bytes= 512001     93.746s
<b>       n=  4000  bytes=  12001     1.429ms
<b>       n= 16000  bytes=  48001     6.034ms
<b>       n= 64000  bytes= 192001    24.330ms

×4 per doubling for <div> and <li>; the same byte counts laid out wide (<div>x</div> × n) parse in single-digit milliseconds. <b> stays linear because the formatting-element path does not scan the stack.

Where the time goes

This is the spec algorithm, implemented as written: a <div> start tag runs "if the stack of open elements has a p element in button scope, close a p element" (TreeBuilder::in_scope, tree_builder/mod.rs), which walks the stack from the top until a scope boundary — with thousands of open <div>s and no boundary, that is the whole stack, for every tag. <li> runs the "loop: if node is an li … otherwise if node is in the special category and not address/div/p, break" walk, same shape. So each tag is O(depth) and the document is O(n²). A tokenizer-only pass over the same input is linear.

Suggestion

A max_tree_depth in TreeBuilderOpts with Chromium's behaviour (when the stack of open elements is at the limit, insert the new element under the nearest ancestor within the limit instead of the current node — the document still parses, the tree is just flattened past the limit), defaulting to something like 512 or left unlimited for compatibility. That bounds the per-tag scans and the DOM depth (which also protects recursive consumers of the tree).

Context: found while hardening a web-fetch tool (dondai44423/donsetch#276); we now pre-scan for nesting and refuse documents past 4096 before handing them to html5ever, but the parser is where the bound belongs.