Skip to content

Bound DETAILS_TAG's Opener Scan So an Unclosed Opener Costs Linear Time #2386

Closed

Description

@ptr727

Found by a local-strict-review pass while working #2384 on feature/auto-2384. It predates that branch, whose opener text is unchanged from develop.

DETAILS_TAG's opener alternative in scripts/pr_review.py, <details(?:[ \t\n\f\r][^>]*|/)?>, has an unbounded [^>]* that crosses lines. For each <details with no > after it, the scan runs to the end of the text, so a body made of such lines costs quadratic time in every reader that pairs tags (details_spans, mask_narrative, and through them marker_blocks and unrecognized_in).

A constructed body of "<details x\n" * n measured about 0.06s at 11k characters, 0.26s at 22k, 1.05s at 44k, and 2.3s at 66k per reader call. GitHub caps a body at 65536 characters, and status runs several readers per body.

Done looks like: the opener is bounded so the scan is linear, for example by stopping its tail at < or at a blank line, with a timing test or a bounded-input test built from constructed text, and the existing tag tests still passing.

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

    bugSomething isn't workingscriptA defect in hub tooling

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions