#78 highlight: O(n²) per-char suffix allocation makes builds take minutes
What
src/highlight.rs:252 rebuilds the rest of the line for every character:
let rest: String = chars[i..].iter().collect();
That is O(n²) allocation/copy per line, and highlight_lines runs for every text file up to MAX_HIGHLIGHT_BYTES = 512 KiB.
Reproduced
Repo with one 64 KB single-line JS file ('var x=1;' * 8000):
hu13 build /tmp/hlprobe -o /tmp/hlout
real 0m27.5s
Quadratic scaling means a 512 KiB minified file can take ~30 minutes; several such files stall a build.
Impact
Build-time DoS / unacceptable builds on ordinary minified assets. MAX_HIGHLIGHT_BYTES does not protect because the cost is per line.
Fix
- Scan on byte/char indices of
&str(or oneVec<char>per line) without building suffixStrings. - Consider capping a single line (e.g. 8 KiB) to plain text; keep whole-file cap.
- Add a timing/scaling unit test with a 64 KB single-line fixture (coarse bound, not wall-clock tight).
Comments (0)
No comments yet.