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#".

2 files changed, 36 insertions, 2 deletions

diff --git a/custom/extensions/about-render.lua b/custom/extensions/about-render.luaindex 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/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.luaindex 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>")
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>")