You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
urllib.robotparser.RobotFileParser.parse() is quadratic in repeated identical "User-agent:" lines #162282
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²).
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.
Activity