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.

1 file changed, 48 insertions, 17 deletions

diff --git a/tests/extensions/test-about-render.lua b/tests/extensions/test-about-render.luaindex 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), "<div class='markdown'>")+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, "<h1 id='title'>Title</h1><p>Body</p>")
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), "<div class='markdown'>")
+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, "<h1 id='title'>Title</h1><p>Body</p>")