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

Tokenizer: duplicate-attribute check is O(n²) in a tag's attribute count

Open
  • Is something wrong?
#796 0 comments 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
42/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
rust
Domain
performance, web-dev

Research direction

Start in html5ever/src/tokenizer/mod.rs at Tokenizer::finish_attribute, where current_tag_attrs is scanned linearly for each new attribute. Keep that scan for small tags and switch to a set of LocalNames once the count crosses a small bound, clearing the set when the tag is emitted. Preserve which attribute wins, the duplicate-attribute parse error, and current_tag_had_duplicate_attributes. Use the tokenizer-only repro in the issue as a timing check; add or extend tokenizer tests for duplicate names on large tags.

Written by the indexing model from the issue text.

Description

The tokenizer's duplicate-attribute check scans every attribute already on the tag for each new one (Tokenizer::finish_attribute, html5ever/src/tokenizer/mod.rs on main, and the same in 0.38/0.39):

let dup = {
    self.current_tag_attrs
        .borrow()
        .iter()
        .any(|a| a.name.local == name)
};

So a start tag with n attributes costs O(n²) in the tokenizer alone. One tag with tens of thousands of attributes is enough to keep a parser thread busy for tens of seconds.

Repro (tokenizer only, sink counts attributes and does nothing else; html5ever 0.38.0, release build, Apple M-series):

use html5ever::tendril::StrTendril;
use html5ever::tokenizer::{BufferQueue, Token, TokenSink, TokenSinkResult, Tokenizer, TokenizerOpts};
use std::{cell::Cell, time::Instant};

struct Count(Cell<usize>);
impl TokenSink for Count {
    type Handle = ();
    fn process_token(&self, t: Token, _line: u64) -> TokenSinkResult<()> {
        if let Token::TagToken(tag) = t { self.0.set(self.0.get() + tag.attrs.len()); }
        TokenSinkResult::Continue
    }
}

fn main() {
    for n in [10_000usize, 20_000, 40_000, 80_000] {
        let mut s = String::from("<div");
        for i in 0..n { s.push_str(&format!(" a{i}=x")); }
        s.push_str("></div>");
        let tok = Tokenizer::new(Count(Cell::new(0)), TokenizerOpts::default());
        let q = BufferQueue::default();
        q.push_back(StrTendril::from(s.as_str()));
        let t0 = Instant::now();
        let _ = tok.feed(&q);
        tok.end();
        println!("{n} attrs: {:?}", t0.elapsed());
    }
}
attributes 10,000 20,000 40,000 80,000
time 0.38 s 0.95 s 7.3 s 38.1 s

For comparison, Chrome 154 parses a 100,000-attribute <div> via innerHTML in about 60 ms.

Spec: HTML §13.2.5.33 (attribute name state) only requires that, on leaving the attribute name state, an attribute whose name matches one already on the token is a duplicate-attribute parse error and is dropped. It says nothing about how the match is found.

How Blink does it: AtomicHTMLToken deduplicates with a HashSet<AtomicString> once a tag has at least 10 attributes, and with a linear scan below that, where the scan is cheaper (third_party/blink/renderer/core/html/parser/atomic_html_token.h, kMinimumNumAttributesToDedupWithHash, InitializeAttributes<DedupWithHash>). The comment there names this exact case: "to avoid DDoS opportunities or similar with O(n²) behavior by setting lots of attributes."

Possible fix: keep the linear scan for small tags, and once the tag's attribute count crosses a small bound, check membership against a set of the tag's LocalNames (atoms hash cheaply). Clear the set when the tag is emitted. Behaviour (which attribute wins, the parse error, current_tag_had_duplicate_attributes) stays the same.

I'm happy to send a PR if this direction is acceptable.

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.