Diff options
| author | Bryce Kwon <bryce@brycekwon.com> | |
|---|---|---|
| committer | Bryce Kwon <bryce@brycekwon.com> | |
| commit | ||
| parent | ||
| tree | ||
| download | ||
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#".
| -rw-r--r-- | custom/extensions/about-render.lua | 28 | |
| -rw-r--r-- | 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>") |