From 75fd15071ab9c6942a7a8760d718503c7646db8b Mon Sep 17 00:00:00 2001 From: Bryce Kwon Date: Sat, 7 Nov 2026 10:02:27 -1000 Subject: Time each hostile readme at two lengths One ten second budget covered several inputs, so a failure did not say which had regressed, and it allowed ten times the second a readme is held to while leaving a slow host little room. A linear render costs four times as much at four times the length and a quadratic one sixteen, whatever the host. The cap on unclosed brackets had no check at all, and the line of \h' escapes timed nothing that is bounded. --- tests/extensions/test-about-render.lua | 65 +++++++++++++++++++++++++--------- 1 file changed, 48 insertions(+), 17 deletions(-) (limited to 'tests/extensions') diff --git a/tests/extensions/test-about-render.lua b/tests/extensions/test-about-render.lua index 67c4ce0..98b84b8 100644 --- a/tests/extensions/test-about-render.lua +++ b/tests/extensions/test-about-render.lua @@ -264,23 +264,54 @@ h.contains("the innermost text still renders", out, "x") out = render("README.md", string.rep("*a", 200)) h.check("an emphasis bomb still renders something", #out > 0) --- Trimming a run of spaces must stay linear, or one hostile line holds a --- request for minutes. The lines below took minutes before, and the bound --- leaves room for a slow host, where they take a few seconds now. -local started = os.clock() -render("README.md", "# a" .. string.rep(" ", 3000) .. "b") -render("README.md", string.rep("# a\n", 50000)) -render("README.md", "| a | b |\n|---|---|\n| x" .. string.rep(" ", 40000) .. "y | z |") -h.check("a long run of spaces is trimmed quickly", os.clock() - started < 10) - --- The long forms of the man escapes scan for a closing bracket or quote, so --- they are bounded the same way, and a line of openers stays linear. -started = os.clock() -render("page.1", string.rep("\\[", 100000)) -render("page.1", string.rep("\\f[", 100000)) -render("page.1", string.rep("\\h'", 100000)) -render("page.1", string.rep("\\s[", 100000)) -h.check("a line of unclosed man escapes renders quickly", os.clock() - started < 10) +-- A hostile readme must cost about four times as much at four times the +-- length, as a linear pass does, where a quadratic one costs sixteen times +-- as much and holds a request for minutes near the size cap. Timing one +-- length against the other cancels out how fast the host is, and each +-- render repeats until it is long enough to time. +local function seconds(filename, text) + local runs, started, out = 0, os.clock(), nil + repeat + out = render(filename, text) + runs = runs + 1 + until os.clock() - started >= 0.02 + return (os.clock() - started) / runs, out +end + +local function stays_linear(name, filename, make, length) + local short = seconds(filename, make(length)) + local long, out = seconds(filename, make(4 * length)) + h.check(name, long < 10 * short, + string.format("%.4f s at length %d, then %.4f s at four times that", short, length, long)) + h.equals(name .. " and still renders as markup", out:sub(1, 22), "
") +end + +local function repeated(unit) + return function(count) + return string.rep(unit, count) + end +end + +-- Lua patterns backtrack, which is why trim finds each end directly. +stays_linear("a long run of spaces in a heading is trimmed in linear time", "README.md", + function(count) return "# a" .. string.rep(" ", count) .. "b" end, 10000) +stays_linear("a long run of spaces in a table cell is trimmed in linear time", "README.md", + function(count) return "| a | b |\n|---|---|\n| x" .. string.rep(" ", count) .. "y | z |" end, 10000) + +-- Every repeat of a heading counts up from the same anchor. +stays_linear("the anchors of a repeated heading are counted in linear time", "README.md", + repeated("# a\n"), 12500) + +-- Without the cap on the label and target scans, every unclosed bracket +-- scans to the end of its line. +stays_linear("a line of open brackets is scanned in linear time", "README.md", repeated("["), 10000) +stays_linear("a line of unclosed links is scanned in linear time", "README.md", repeated("[a](b"), 10000) + +-- The long forms of the man escapes scan for a closing bracket, bounded the +-- same way. +stays_linear("a line of unclosed character names renders in linear time", "page.1", repeated("\\["), 10000) +stays_linear("a line of unclosed font names renders in linear time", "page.1", repeated("\\f["), 10000) +stays_linear("a line of unclosed size escapes renders in linear time", "page.1", repeated("\\s["), 10000) out = render("README.md", "Title\n=====\n\nBody") h.contains("equals signs under a line make a heading", out, "

Title

Body

") -- cgit 2.12.1