5 files changed, 59 insertions, 26 deletions
diff --git a/tests/extensions/harness.lua b/tests/extensions/harness.lua
index 5084ab4..188d90f 100644
--- a/tests/extensions/harness.lua
+++ b/tests/extensions/harness.lua
@@ -301,6 +301,39 @@ function harness.excludes(name, haystack, needle)
 	end
 end
 
+-- Checks that a text four times as long costs about four times as much to
+-- run, as a linear pass does, where a quadratic one costs sixteen times as
+-- much. Timing one length against the other cancels out how fast the host
+-- is. Each timing repeats the run for at least 50 ms, and the two lengths
+-- take turns, keeping the fastest timing of each. A busy host can charge
+-- the process for time its CPU was taken away, which slows a timing but
+-- never speeds one up. A ratio under six is plainly linear and ends the
+-- turns, so only one near the bound takes all five before it can fail.
+-- Returns what the longer run gave back.
+function harness.stays_linear(name, run, make, length)
+	local texts = { make(length), make(4 * length) }
+	local fastest = { math.huge, math.huge }
+	local out
+	for _ = 1, 5 do
+		for i = 1, 2 do
+			local runs, started = 0, os.clock()
+			repeat
+				out = run(texts[i])
+				runs = runs + 1
+			until os.clock() - started >= 0.05
+			fastest[i] = math.min(fastest[i], (os.clock() - started) / runs)
+		end
+		if fastest[2] < 6 * fastest[1] then
+			break
+		end
+	end
+	local short, long = fastest[1], fastest[2]
+	harness.check(name, long < 10 * short,
+		string.format("%.4f s at length %d, then %.4f s at four times that",
+			short, length, long))
+	return out
+end
+
 -- A run that made no check proves nothing, so it fails as well.
 function harness.finish()
 	if failures > 0 then
diff --git a/tests/extensions/test-about-render.lua b/tests/extensions/test-about-render.lua
index a08de66..cdba28a 100644
--- a/tests/extensions/test-about-render.lua
+++ b/tests/extensions/test-about-render.lua
@@ -266,25 +266,12 @@ out = render("README.md", "**__*_x_*__**")
 h.contains("every kind of emphasis nests in the others", out,
 	"<p><strong><strong><em><em>x</em></em></strong></strong></p>")
 
--- 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
-
+-- A hostile readme that renders in more than linear time holds a request
+-- for minutes near the size cap.
 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))
+	local out = h.stays_linear(name, function(text)
+		return render(filename, text)
+	end, make, length)
 	h.equals(name .. " and still renders as markup", out:sub(1, 22), "<div class='markdown'>")
 end
 
diff --git a/tests/extensions/test-email-avatar.lua b/tests/extensions/test-email-avatar.lua
index 5929634..c9a9ec0 100644
--- a/tests/extensions/test-email-avatar.lua
+++ b/tests/extensions/test-email-avatar.lua
@@ -101,14 +101,14 @@ h.contains("a name keeps the escaping cgit gave it", out, "> A &amp; B")
 h.excludes("and is not escaped again", out, "&amp;amp;")
 
 -- A commit can carry any bytes in its address, and a log page runs the
--- filter once per row, so the trim has to stay linear in a run of spaces.
-local started = os.clock()
-render("<a" .. string.rep(" ", 40000) .. "b>", "x")
-h.check("a long run of inner spaces is trimmed quickly", os.clock() - started < 0.5)
-
-started = os.clock()
-render(string.rep("<", 40000), "x")
-h.check("a long run of open brackets is unwrapped quickly", os.clock() - started < 0.5)
+-- filter once per row, so trimming and unwrapping have to stay linear.
+local function address_only(text)
+	return (render(text, "x"))
+end
+h.stays_linear("a long run of inner spaces is trimmed in linear time", address_only,
+	function(count) return "<a" .. string.rep(" ", count) .. "b>" end, 10000)
+h.stays_linear("an address of open brackets is scanned in linear time", address_only,
+	function(count) return string.rep("<", count) end, 10000)
 
 h.check("text around the brackets is dropped",
 	hash_of(render("x <author@example.com> y", "x")) == plain)
diff --git a/tests/extensions/test-link-commits.lua b/tests/extensions/test-link-commits.lua
index fa3a040..dca16d4 100644
--- a/tests/extensions/test-link-commits.lua
+++ b/tests/extensions/test-link-commits.lua
@@ -126,4 +126,11 @@ h.equals("the shipped examples link what they describe", out,
 	"<a href='https://gitlab.example.com/my/repo/-/merge_requests/42'>!42</a> and " ..
 	"<a href='https://www.rfc-editor.org/rfc/rfc9110'>RFC 9110</a>")
 
+-- A message near cgit's size limit with a match every few bytes still has
+-- to come out in linear time.
+h.load_with(script, { { "-- { pattern = \"#(%d+)\"", "{ pattern = \"#(%d+)\"" } })
+h.stays_linear("a long message full of matches is linked in linear time", function(text)
+	return (render(text))
+end, function(count) return string.rep("deadbeef #1 ", count) end, 10000)
+
 h.finish()
diff --git a/tests/extensions/test-link-trailers.lua b/tests/extensions/test-link-trailers.lua
index c4dfdf5..7912d3e 100644
--- a/tests/extensions/test-link-trailers.lua
+++ b/tests/extensions/test-link-trailers.lua
@@ -106,4 +106,10 @@ out = render("CVE", "CVE-2024-12345")
 h.equals("the shipped CVE example links to its record", out,
 	"<a href='https://www.cve.org/CVERecord?id=CVE-2024-12345'>CVE-2024-12345</a>")
 
+-- A long value of url starts is checked against the url pattern once, from
+-- its start, so it costs no more than its length.
+h.stays_linear("a long value is checked in linear time", function(text)
+	return (render("Link", text))
+end, function(count) return string.rep("http://", count) .. " " end, 10000)
+
 h.finish()
-rw-r--r--	tests/extensions/harness.lua	33
-rw-r--r--	tests/extensions/test-about-render.lua	23
-rw-r--r--	tests/extensions/test-email-avatar.lua	16
-rw-r--r--	tests/extensions/test-link-commits.lua	7
-rw-r--r--	tests/extensions/test-link-trailers.lua	6