From 47a509cfd36dfac4013f4ee76891165727eb47a1 Mon Sep 17 00:00:00 2001
From: Bryce Kwon <bryce@brycekwon.com>
Date: Fri, 16 Oct 2026 06:37:01 -1000
Subject: Trim readme lines in linear time

The heading pattern backtracked over a run of spaces in cubic time and
the cell trim in quadratic time, so one crafted line in a readme could
hold a request for half an hour, well inside the size cap. The heading
rule now also keeps a sharp that ends a word, as in "# C#".
---
 custom/extensions/about-render.lua     | 28 ++++++++++++++++++++++++++--
 tests/extensions/test-about-render.lua | 10 ++++++++++
 2 files changed, 36 insertions(+), 2 deletions(-)

diff --git a/custom/extensions/about-render.lua b/custom/extensions/about-render.lua
index c833c00..ecb2abe 100644
--- a/custom/extensions/about-render.lua
+++ b/custom/extensions/about-render.lua
@@ -33,8 +33,32 @@ local max_depth = 24
 local filename, chunks = "", {}
 
 
+-- Lua patterns backtrack, so "%s+$" costs the square of a run of spaces in
+-- the middle of a line. Finding each end directly stays linear.
 local function trim(text)
-	return (text:gsub("^%s+", ""):gsub("%s+$", ""))
+	local first = text:find("%S")
+	if first == nil then
+		return ""
+	end
+	local last = #text
+	while text:find("^%s", last) do
+		last = last - 1
+	end
+	return text:sub(first, last)
+end
+
+-- A heading may close with a run of hashes, which only counts as markup when
+-- a space comes before it, so "# C#" keeps its sharp.
+local function heading_text(title)
+	title = trim(title)
+	local last = #title
+	while last > 0 and title:sub(last, last) == "#" do
+		last = last - 1
+	end
+	if last == 0 or title:find("^%s", last) then
+		return trim(title:sub(1, last))
+	end
+	return title
 end
 
 -- Normalise CRLF and CR to newlines, then split. A trailing newline yields
@@ -332,7 +356,7 @@ if has_lpeg then
 				blocks[#blocks + 1] = {
 					kind = "heading",
 					level = #hashes,
-					kids = parse_inline((title:gsub("%s*#*%s*$", ""))),
+					kids = parse_inline(heading_text(title)),
 				}
 				i = i + 1
 			elseif break_line:match(line) then
diff --git a/tests/extensions/test-about-render.lua b/tests/extensions/test-about-render.lua
index 338949a..b0379b7 100644
--- a/tests/extensions/test-about-render.lua
+++ b/tests/extensions/test-about-render.lua
@@ -73,6 +73,9 @@ h.contains("a heading renders inside the wrapper", out, "<div class='markdown'><
 out = render("README.md", "## Sub ##")
 h.contains("trailing hashes are stripped from a heading", out, "<h2>Sub</h2>")
 
+out = render("README.md", "# C#")
+h.contains("a hash ending a word stays in the heading", out, "<h1>C#</h1>")
+
 out = render("README.MD", "# Upper")
 h.contains("the extension matches whatever its case", out, "<h1>Upper</h1>")
 
@@ -160,6 +163,13 @@ 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. Both lines below took seconds before.
+local started = os.clock()
+render("README.md", "# a" .. string.rep(" ", 3000) .. "b")
+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 < 1)
+
 out = render("README.md", "| a | b |\n| --- | --- |\n| 1 | 2 |")
 h.contains("a pipe table renders its head", out, "<thead><tr><th>a</th><th>b</th></tr></thead>")
 h.contains("a pipe table renders its body", out, "<tbody><tr><td>1</td><td>2</td></tr></tbody>")
-- 
cgit