Trim avatar addresses in linear time

The trim pattern backtracked over a run of spaces inside an address,
which a commit can carry, and a log page runs the filter for every row.
Forty thousand spaces took two seconds per row.

3 files changed, 36 insertions, 2 deletions

diff --git a/custom/extensions/email-gravatar.lua b/custom/extensions/email-gravatar.luaindex 6eb5376..01db3f9 100644--- a/custom/extensions/email-gravatar.lua+++ b/custom/extensions/email-gravatar.lua@@ -58,6 +58,20 @@ local function hash_hex(input) 	return hex end +-- Lua patterns backtrack, so "^%s*(.-)%s*$" would cost the square of a long+-- run of spaces inside the address. Finding each end directly stays linear.+local function trim(text)+	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+ -- cgit can hand over the address still wrapped in angle brackets, and the -- service hashes the trimmed lowercase form, so an address that skipped this -- would hash to something the service has never heard of. A missing or empty@@ -70,7 +84,7 @@ local function normalize_email(email) 	if inner ~= nil then 		email = inner 	end-	email = (email:gsub("^%s*(.-)%s*$", "%1")):lower()+	email = trim(email):lower() 	if email == "" then 		return nil 	end
diff --git a/custom/extensions/email-gravatar.lua b/custom/extensions/email-gravatar.lua
index 6eb5376..01db3f9 100644
--- a/custom/extensions/email-gravatar.lua
+++ b/custom/extensions/email-gravatar.lua
@@ -58,6 +58,20 @@ local function hash_hex(input)
 	return hex
 end
 
+-- Lua patterns backtrack, so "^%s*(.-)%s*$" would cost the square of a long
+-- run of spaces inside the address. Finding each end directly stays linear.
+local function trim(text)
+	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
+
 -- cgit can hand over the address still wrapped in angle brackets, and the
 -- service hashes the trimmed lowercase form, so an address that skipped this
 -- would hash to something the service has never heard of. A missing or empty
@@ -70,7 +84,7 @@ local function normalize_email(email)
 	if inner ~= nil then
 		email = inner
 	end
-	email = (email:gsub("^%s*(.-)%s*$", "%1")):lower()
+	email = trim(email):lower()
 	if email == "" then
 		return nil
 	end
diff --git a/custom/extensions/email-libravatar.lua b/custom/extensions/email-libravatar.luaindex 9b3d595..1fb979d 100644--- a/custom/extensions/email-libravatar.lua+++ b/custom/extensions/email-libravatar.lua@@ -56,6 +56,20 @@ local function hash_hex(input) 	return hex end +-- Lua patterns backtrack, so "^%s*(.-)%s*$" would cost the square of a long+-- run of spaces inside the address. Finding each end directly stays linear.+local function trim(text)+	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+ -- cgit can hand over the address still wrapped in angle brackets, and the -- service hashes the trimmed lowercase form, so an address that skipped this -- would hash to something the service has never heard of. A missing or empty@@ -68,7 +82,7 @@ local function normalize_email(email) 	if inner ~= nil then 		email = inner 	end-	email = (email:gsub("^%s*(.-)%s*$", "%1")):lower()+	email = trim(email):lower() 	if email == "" then 		return nil 	end
diff --git a/custom/extensions/email-libravatar.lua b/custom/extensions/email-libravatar.lua
index 9b3d595..1fb979d 100644
--- a/custom/extensions/email-libravatar.lua
+++ b/custom/extensions/email-libravatar.lua
@@ -56,6 +56,20 @@ local function hash_hex(input)
 	return hex
 end
 
+-- Lua patterns backtrack, so "^%s*(.-)%s*$" would cost the square of a long
+-- run of spaces inside the address. Finding each end directly stays linear.
+local function trim(text)
+	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
+
 -- cgit can hand over the address still wrapped in angle brackets, and the
 -- service hashes the trimmed lowercase form, so an address that skipped this
 -- would hash to something the service has never heard of. A missing or empty
@@ -68,7 +82,7 @@ local function normalize_email(email)
 	if inner ~= nil then
 		email = inner
 	end
-	email = (email:gsub("^%s*(.-)%s*$", "%1")):lower()
+	email = trim(email):lower()
 	if email == "" then
 		return nil
 	end
diff --git a/tests/extensions/test-email-avatar.lua b/tests/extensions/test-email-avatar.luaindex 94fec7e..4960ec3 100644--- a/tests/extensions/test-email-avatar.lua+++ b/tests/extensions/test-email-avatar.lua@@ -68,6 +68,12 @@ h.equals("empty angle brackets draw no icon", out, "A U Thor") out = h.run({ "<author@example.com>", "commit" }, { "A U ", "Thor" }) h.contains("the name is buffered across writes", out, "> A U Thor") +-- 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)+ if mode == "real" then 	out = render("test@example.com", "x") 	h.equals("a known address hashes to its published md5", hash_of(out), "55502f40dc8b7c769880b10874abc9d0")
diff --git a/tests/extensions/test-email-avatar.lua b/tests/extensions/test-email-avatar.lua
index 94fec7e..4960ec3 100644
--- a/tests/extensions/test-email-avatar.lua
+++ b/tests/extensions/test-email-avatar.lua
@@ -68,6 +68,12 @@ h.equals("empty angle brackets draw no icon", out, "A U Thor")
 out = h.run({ "<author@example.com>", "commit" }, { "A U ", "Thor" })
 h.contains("the name is buffered across writes", out, "> A U Thor")
 
+-- 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)
+
 if mode == "real" then
 	out = render("test@example.com", "x")
 	h.equals("a known address hashes to its published md5", hash_of(out), "55502f40dc8b7c769880b10874abc9d0")