Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

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

Open
  • Is something wrong?
#788 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
45/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Active
Tech stack
rust
Domain
web-dev

Research direction

Start in tree_builder/mod.rs, especially TreeBuilder::in_scope, and locate TreeBuilderOpts. Reproduce the nested-element benchmark to establish the scaling problem, then evaluate the proposed max_tree_depth behavior and compatibility choice. Done means deeply nested input is bounded as described while the parser still produces a valid document.

Written by the indexing model from the issue text.

Description

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.

Dominant language
Rust
Stars
2.6k
Forks
291
Avg merge
8h 21m
Merged PRs (30d)
3

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from servo/html5ever

All issues in servo/html5ever

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.