Skip to content

urllib.robotparser.RobotFileParser.parse() is quadratic in repeated identical "User-agent:" lines #162282

Description

@VadimToptunov

urllib.robotparser.RobotFileParser.parse() scales as O(N²) in the number of identical User-agent: lines inside a single group. When a robots.txt has N User-agent: lines with no intervening Allow: or Disallow:, the parser accumulates one Entry whose useragents list ends up with N duplicates. _add_entry then walks that list and from the second iteration on calls merge_entries(self.groups[agent], entry); merge_entries is itself O(N) because it rebuilds useragents from the other entry's set. The product is O(N²).

Reproducer:

import time
from urllib.robotparser import RobotFileParser

for n in (10_000, 20_000):
    body = ("User-agent: evil\n" * n) + "Disallow: /\n"
    rp = RobotFileParser()
    t0 = time.perf_counter()
    rp.parse(body.splitlines())
    print(n, round(time.perf_counter() - t0, 2))

On Python 3.14.6 / M-series arm64:

  • 10 000 lines → 2.65 s
  • 20 000 lines → 10.48 s
  • the ratio dt / n² is constant at ~27 ns, confirming pure quadratic

A minimal fix is to deduplicate inside _add_entry so a given agent is registered at most once per call. For every input shape except "same agent repeated within one entry" the change is a no-op; for that shape it removes the redundant self-merges that caused the quadratic.

Will post a PR.

Linked PRs

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions