Quadratic time in find_markers (many markers) and in parsing deeply nested lists

[dvejsada]

Found while adapting PactTrack to 0.3.0. PactTrack validates untrusted contract text of up to 10 MiB, so superlinear paths in the validator become request-time costs. There are two paths, both measured on 0.3.0 from PyPI with time.process_time().

1. find_markers: the rest of the fragment is re-scanned for every marker

In legaldown/validator/units.py find_markers, each marker match computes:

at_end = position and not HTML_COMMENT_RE.sub("", fragment[m.end():]).strip()

This copies the rest of the fragment and runs a regex substitution over it once per marker, so the cost is O(markers × fragment length). marker_matches also tests each match against every directive (any(d.start <= match.start() < d.end for d in lexed.directives ...)), which is O(markers × directives).

from functools import cache
from legaldown import lex, parse_document
from legaldown.validator.units import find_markers

for n in (5000, 10000, 20000):
    doc = parse_document("# S\n\n" + "a {when=x} " * n + "end\n")
    find_markers(doc, cache(lex))

markers	time
5,000	0.11 s
10,000	0.28 s
20,000	1.02 s

The time roughly quadruples each time the input doubles.

Suggested fix:

• Compute once per fragment the position from which only whitespace and comments remain. One backward pass over the comment-stripped view gives it. Then at_end becomes m.end() >= tail_start.
• For the directive test, a binary search over the sorted directive starts.

2. Parsing: nested lists are quadratic in depth

from legaldown import parse_document

for n in (100, 200, 400):
    parse_document("# S\n\n" + "".join("  " * i + "- a\n" for i in range(n)))

depth	time
100	0.10 s
200	0.43 s
400	1.85 s

PactTrack's editor also lays out a field with _layout several times per request, and 1,000 levels took about 48 s there. The cost looks like it comes from _scan_list re-scanning, and re-dedenting, each nested item's lines at every level. It may be worth either capping the nesting depth, as MAX_QUOTE_DEPTH does for quotes, or scanning each line once.

Neither of these is a correctness bug, and ordinary documents are far below these sizes. It is a denial-of-service surface for any service that validates uploaded text.