# HG changeset patch
# User Matthew Wild <mwild1@gmail.com>
# Date 1536704876 -3600
# Node ID 561f0af6c9dc497d4a82d75257057bac0904bb45
# Parent  091212cef52aa06fd828ad534173b03330335053
serve/: Import dependencies required for serve mode from Prosody 329a670ae975

diff -r 091212cef52a -r 561f0af6c9dc serve/net/http/codes.lua
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/serve/net/http/codes.lua	Tue Sep 11 23:27:56 2018 +0100
@@ -0,0 +1,86 @@
+
+local response_codes = {
+	-- Source: http://www.iana.org/assignments/http-status-codes
+
+	[100] = "Continue"; -- RFC7231, Section 6.2.1
+	[101] = "Switching Protocols"; -- RFC7231, Section 6.2.2
+	[102] = "Processing";
+	[103] = "Early Hints";
+	-- [104-199] = "Unassigned";
+
+	[200] = "OK"; -- RFC7231, Section 6.3.1
+	[201] = "Created"; -- RFC7231, Section 6.3.2
+	[202] = "Accepted"; -- RFC7231, Section 6.3.3
+	[203] = "Non-Authoritative Information"; -- RFC7231, Section 6.3.4
+	[204] = "No Content"; -- RFC7231, Section 6.3.5
+	[205] = "Reset Content"; -- RFC7231, Section 6.3.6
+	[206] = "Partial Content"; -- RFC7233, Section 4.1
+	[207] = "Multi-Status";
+	[208] = "Already Reported";
+	-- [209-225] = "Unassigned";
+	[226] = "IM Used";
+	-- [227-299] = "Unassigned";
+
+	[300] = "Multiple Choices"; -- RFC7231, Section 6.4.1
+	[301] = "Moved Permanently"; -- RFC7231, Section 6.4.2
+	[302] = "Found"; -- RFC7231, Section 6.4.3
+	[303] = "See Other"; -- RFC7231, Section 6.4.4
+	[304] = "Not Modified"; -- RFC7232, Section 4.1
+	[305] = "Use Proxy"; -- RFC7231, Section 6.4.5
+	-- [306] = "(Unused)"; -- RFC7231, Section 6.4.6
+	[307] = "Temporary Redirect"; -- RFC7231, Section 6.4.7
+	[308] = "Permanent Redirect";
+	-- [309-399] = "Unassigned";
+
+	[400] = "Bad Request"; -- RFC7231, Section 6.5.1
+	[401] = "Unauthorized"; -- RFC7235, Section 3.1
+	[402] = "Payment Required"; -- RFC7231, Section 6.5.2
+	[403] = "Forbidden"; -- RFC7231, Section 6.5.3
+	[404] = "Not Found"; -- RFC7231, Section 6.5.4
+	[405] = "Method Not Allowed"; -- RFC7231, Section 6.5.5
+	[406] = "Not Acceptable"; -- RFC7231, Section 6.5.6
+	[407] = "Proxy Authentication Required"; -- RFC7235, Section 3.2
+	[408] = "Request Timeout"; -- RFC7231, Section 6.5.7
+	[409] = "Conflict"; -- RFC7231, Section 6.5.8
+	[410] = "Gone"; -- RFC7231, Section 6.5.9
+	[411] = "Length Required"; -- RFC7231, Section 6.5.10
+	[412] = "Precondition Failed"; -- RFC7232, Section 4.2
+	[413] = "Payload Too Large"; -- RFC7231, Section 6.5.11
+	[414] = "URI Too Long"; -- RFC7231, Section 6.5.12
+	[415] = "Unsupported Media Type"; -- RFC7231, Section 6.5.13
+	[416] = "Range Not Satisfiable"; -- RFC7233, Section 4.4
+	[417] = "Expectation Failed"; -- RFC7231, Section 6.5.14
+	[418] = "I'm a teapot"; -- RFC2324, Section 2.3.2
+	-- [419-420] = "Unassigned";
+	[421] = "Misdirected Request"; -- RFC7540, Section 9.1.2
+	[422] = "Unprocessable Entity";
+	[423] = "Locked";
+	[424] = "Failed Dependency";
+	[425] = "Too Early";
+	[426] = "Upgrade Required"; -- RFC7231, Section 6.5.15
+	-- [427] = "Unassigned";
+	[428] = "Precondition Required";
+	[429] = "Too Many Requests";
+	-- [430] = "Unassigned";
+	[431] = "Request Header Fields Too Large";
+	-- [432-450] = "Unassigned";
+	[451] = "Unavailable For Legal Reasons";
+	-- [452-499] = "Unassigned";
+
+	[500] = "Internal Server Error"; -- RFC7231, Section 6.6.1
+	[501] = "Not Implemented"; -- RFC7231, Section 6.6.2
+	[502] = "Bad Gateway"; -- RFC7231, Section 6.6.3
+	[503] = "Service Unavailable"; -- RFC7231, Section 6.6.4
+	[504] = "Gateway Timeout"; -- RFC7231, Section 6.6.5
+	[505] = "HTTP Version Not Supported"; -- RFC7231, Section 6.6.6
+	[506] = "Variant Also Negotiates";
+	[507] = "Insufficient Storage";
+	[508] = "Loop Detected";
+	-- [509] = "Unassigned";
+	[510] = "Not Extended";
+	[511] = "Network Authentication Required";
+	-- [512-599] = "Unassigned";
+};
+
+for k,v in pairs(response_codes) do response_codes[k] = k.." "..v; end
+return setmetatable(response_codes, { __index = function(_, k) return k.." Unassigned"; end })
diff -r 091212cef52a -r 561f0af6c9dc serve/net/http/parser.lua
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/serve/net/http/parser.lua	Tue Sep 11 23:27:56 2018 +0100
@@ -0,0 +1,187 @@
+local tonumber = tonumber;
+local assert = assert;
+local t_insert, t_concat = table.insert, table.concat;
+local url_parse = require "socket.url".parse;
+local urldecode = require "util.http".urldecode;
+
+local function preprocess_path(path)
+	path = urldecode((path:gsub("//+", "/")));
+	if path:sub(1,1) ~= "/" then
+		path = "/"..path;
+	end
+	local level = 0;
+	for component in path:gmatch("([^/]+)/") do
+		if component == ".." then
+			level = level - 1;
+		elseif component ~= "." then
+			level = level + 1;
+		end
+		if level < 0 then
+			return nil;
+		end
+	end
+	return path;
+end
+
+local httpstream = {};
+
+function httpstream.new(success_cb, error_cb, parser_type, options_cb)
+	local client = true;
+	if not parser_type or parser_type == "server" then client = false; else assert(parser_type == "client", "Invalid parser type"); end
+	local buf, buflen, buftable = {}, 0, true;
+	local bodylimit = tonumber(options_cb and options_cb().body_size_limit) or 10*1024*1024;
+	local buflimit = tonumber(options_cb and options_cb().buffer_size_limit) or bodylimit * 2;
+	local chunked, chunk_size, chunk_start;
+	local state = nil;
+	local packet;
+	local len;
+	local have_body;
+	local error;
+	return {
+		feed = function(_, data)
+			if error then return nil, "parse has failed"; end
+			if not data then -- EOF
+				if buftable then buf, buftable = t_concat(buf), false; end
+				if state and client and not len then -- reading client body until EOF
+					packet.body = buf;
+					success_cb(packet);
+				elseif buf ~= "" then -- unexpected EOF
+					error = true; return error_cb("unexpected-eof");
+				end
+				return;
+			end
+			if buftable then
+				t_insert(buf, data);
+			else
+				buf = { buf, data };
+				buftable = true;
+			end
+			buflen = buflen + #data;
+			if buflen > buflimit then error = true; return error_cb("max-buffer-size-exceeded"); end
+			while buflen > 0 do
+				if state == nil then -- read request
+					if buftable then buf, buftable = t_concat(buf), false; end
+					local index = buf:find("\r\n\r\n", nil, true);
+					if not index then return; end -- not enough data
+					local method, path, httpversion, status_code, reason_phrase;
+					local first_line;
+					local headers = {};
+					for line in buf:sub(1,index+1):gmatch("([^\r\n]+)\r\n") do -- parse request
+						if first_line then
+							local key, val = line:match("^([^%s:]+): *(.*)$");
+							if not key then error = true; return error_cb("invalid-header-line"); end -- TODO handle multi-line and invalid headers
+							key = key:lower();
+							headers[key] = headers[key] and headers[key]..","..val or val;
+						else
+							first_line = line;
+							if client then
+								httpversion, status_code, reason_phrase = line:match("^HTTP/(1%.[01]) (%d%d%d) (.*)$");
+								status_code = tonumber(status_code);
+								if not status_code then error = true; return error_cb("invalid-status-line"); end
+								have_body = not
+									 ( (options_cb and options_cb().method == "HEAD")
+									or (status_code == 204 or status_code == 304 or status_code == 301)
+									or (status_code >= 100 and status_code < 200) );
+							else
+								method, path, httpversion = line:match("^(%w+) (%S+) HTTP/(1%.[01])$");
+								if not method then error = true; return error_cb("invalid-status-line"); end
+							end
+						end
+					end
+					if not first_line then error = true; return error_cb("invalid-status-line"); end
+					chunked = have_body and headers["transfer-encoding"] == "chunked";
+					len = tonumber(headers["content-length"]); -- TODO check for invalid len
+					if len and len > bodylimit then error = true; return error_cb("content-length-limit-exceeded"); end
+					if client then
+						-- FIXME handle '100 Continue' response (by skipping it)
+						if not have_body then len = 0; end
+						packet = {
+							code = status_code;
+							httpversion = httpversion;
+							headers = headers;
+							body = have_body and "" or nil;
+							-- COMPAT the properties below are deprecated
+							responseversion = httpversion;
+							responseheaders = headers;
+						};
+					else
+						local parsed_url;
+						if path:byte() == 47 then -- starts with /
+							local _path, _query = path:match("([^?]*).?(.*)");
+							if _query == "" then _query = nil; end
+							parsed_url = { path = _path, query = _query };
+						else
+							parsed_url = url_parse(path);
+							if not(parsed_url and parsed_url.path) then error = true; return error_cb("invalid-url"); end
+						end
+						path = preprocess_path(parsed_url.path);
+						headers.host = parsed_url.host or headers.host;
+
+						len = len or 0;
+						packet = {
+							method = method;
+							url = parsed_url;
+							path = path;
+							httpversion = httpversion;
+							headers = headers;
+							body = nil;
+						};
+					end
+					buf = buf:sub(index + 4);
+					buflen = #buf;
+					state = true;
+				end
+				if state then -- read body
+					if client then
+						if chunked then
+							if chunk_start and buflen - chunk_start - 2 < chunk_size then
+								return;
+							end -- not enough data
+							if buftable then buf, buftable = t_concat(buf), false; end
+							if not buf:find("\r\n", nil, true) then
+								return;
+							end -- not enough data
+							if not chunk_size then
+								chunk_size, chunk_start = buf:match("^(%x+)[^\r\n]*\r\n()");
+								chunk_size = chunk_size and tonumber(chunk_size, 16);
+								if not chunk_size then error = true; return error_cb("invalid-chunk-size"); end
+							end
+							if chunk_size == 0 and buf:find("\r\n\r\n", chunk_start-2, true) then
+								state, chunk_size = nil, nil;
+								buf = buf:gsub("^.-\r\n\r\n", ""); -- This ensure extensions and trailers are stripped
+								success_cb(packet);
+							elseif buflen - chunk_start - 2 >= chunk_size then -- we have a chunk
+								packet.body = packet.body..buf:sub(chunk_start, chunk_start + (chunk_size-1));
+								buf = buf:sub(chunk_start + chunk_size + 2);
+								buflen = buflen - (chunk_start + chunk_size + 2 - 1);
+								chunk_size, chunk_start = nil, nil;
+							else -- Partial chunk remaining
+								break;
+							end
+						elseif len and buflen >= len then
+							if buftable then buf, buftable = t_concat(buf), false; end
+							if packet.code == 101 then
+								packet.body, buf, buflen, buftable = buf, {}, 0, true;
+							else
+								packet.body, buf = buf:sub(1, len), buf:sub(len + 1);
+								buflen = #buf;
+							end
+							state = nil; success_cb(packet);
+						else
+							break;
+						end
+					elseif buflen >= len then
+						if buftable then buf, buftable = t_concat(buf), false; end
+						packet.body, buf = buf:sub(1, len), buf:sub(len + 1);
+						buflen = #buf;
+						state = nil; success_cb(packet);
+					else
+						break;
+					end
+				end
+			end
+		end;
+	};
+end
+
+return httpstream;
diff -r 091212cef52a -r 561f0af6c9dc serve/net/http/server.lua
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/serve/net/http/server.lua	Tue Sep 11 23:27:56 2018 +0100
@@ -0,0 +1,366 @@
+
+local t_insert, t_remove, t_concat = table.insert, table.remove, table.concat;
+local parser_new = require "net.http.parser".new;
+local events = require "util.events".new();
+local addserver = require "net.server".addserver;
+local log = require "util.logger".init("http.server");
+local os_date = os.date;
+local pairs = pairs;
+local s_upper = string.upper;
+local setmetatable = setmetatable;
+local xpcall = xpcall;
+local traceback = debug.traceback;
+local tostring = tostring;
+local cache = require "util.cache";
+local codes = require "net.http.codes";
+local blocksize = 2^16;
+
+local _M = {};
+
+local sessions = {};
+local incomplete = {};
+local listener = {};
+local hosts = {};
+local default_host;
+local options = {};
+
+local function is_wildcard_event(event)
+	return event:sub(-2, -1) == "/*";
+end
+local function is_wildcard_match(wildcard_event, event)
+	return wildcard_event:sub(1, -2) == event:sub(1, #wildcard_event-1);
+end
+
+local _handlers = events._handlers;
+local recent_wildcard_events = cache.new(10000, function (key, value) -- luacheck: ignore 212/value
+	rawset(_handlers, key, nil);
+end);
+
+local event_map = events._event_map;
+setmetatable(events._handlers, {
+	-- Called when firing an event that doesn't exist (but may match a wildcard handler)
+	__index = function (handlers, curr_event)
+		if is_wildcard_event(curr_event) then return; end -- Wildcard events cannot be fired
+		-- Find all handlers that could match this event, sort them
+		-- and then put the array into handlers[curr_event] (and return it)
+		local matching_handlers_set = {};
+		local handlers_array = {};
+		for event, handlers_set in pairs(event_map) do
+			if event == curr_event or
+			is_wildcard_event(event) and is_wildcard_match(event, curr_event) then
+				for handler, priority in pairs(handlers_set) do
+					matching_handlers_set[handler] = { (select(2, event:gsub("/", "%1"))), is_wildcard_event(event) and 0 or 1, priority };
+					table.insert(handlers_array, handler);
+				end
+			end
+		end
+		if #handlers_array > 0 then
+			table.sort(handlers_array, function(b, a)
+				local a_score, b_score = matching_handlers_set[a], matching_handlers_set[b];
+				for i = 1, #a_score do
+					if a_score[i] ~= b_score[i] then -- If equal, compare next score value
+						return a_score[i] < b_score[i];
+					end
+				end
+				return false;
+			end);
+		else
+			handlers_array = false;
+		end
+		rawset(handlers, curr_event, handlers_array);
+		if not event_map[curr_event] then -- Only wildcard handlers match, if any
+			recent_wildcard_events:set(curr_event, true);
+		end
+		return handlers_array;
+	end;
+	__newindex = function (handlers, curr_event, handlers_array)
+		if handlers_array == nil
+		and is_wildcard_event(curr_event) then
+			-- Invalidate the indexes of all matching events
+			for event in pairs(handlers) do
+				if is_wildcard_match(curr_event, event) then
+					handlers[event] = nil;
+				end
+			end
+		end
+		rawset(handlers, curr_event, handlers_array);
+	end;
+});
+
+local handle_request;
+local _1, _2, _3;
+local function _handle_request() return handle_request(_1, _2, _3); end
+
+local last_err;
+local function _traceback_handler(err) last_err = err; log("error", "Traceback[httpserver]: %s", traceback(tostring(err), 2)); end
+events.add_handler("http-error", function (error)
+	return "Error processing request: "..codes[error.code]..". Check your error log for more information.";
+end, -1);
+
+function listener.onconnect(conn)
+	local secure = conn:ssl() and true or nil;
+	local pending = {};
+	local waiting = false;
+	local function process_next()
+		if waiting then return; end -- log("debug", "can't process_next, waiting");
+		waiting = true;
+		while sessions[conn] and #pending > 0 do
+			local request = t_remove(pending);
+			--log("debug", "process_next: %s", request.path);
+			--handle_request(conn, request, process_next);
+			_1, _2, _3 = conn, request, process_next;
+			if not xpcall(_handle_request, _traceback_handler) then
+				conn:write("HTTP/1.0 500 Internal Server Error\r\n\r\n"..events.fire_event("http-error", { code = 500, private_message = last_err }));
+				conn:close();
+			end
+		end
+		--log("debug", "ready for more");
+		waiting = false;
+	end
+	local function success_cb(request)
+		--log("debug", "success_cb: %s", request.path);
+		if waiting then
+			log("error", "http connection handler is not reentrant: %s", request.path);
+			assert(false, "http connection handler is not reentrant");
+		end
+		request.secure = secure;
+		t_insert(pending, request);
+		process_next();
+	end
+	local function error_cb(err)
+		log("debug", "error_cb: %s", err or "<nil>");
+		-- FIXME don't close immediately, wait until we process current stuff
+		-- FIXME if err, send off a bad-request response
+		sessions[conn] = nil;
+		conn:close();
+	end
+	local function options_cb()
+		return options;
+	end
+	sessions[conn] = parser_new(success_cb, error_cb, "server", options_cb);
+end
+
+function listener.ondisconnect(conn)
+	local open_response = conn._http_open_response;
+	if open_response and open_response.on_destroy then
+		open_response.finished = true;
+		open_response:on_destroy();
+	end
+	incomplete[conn] = nil;
+	sessions[conn] = nil;
+end
+
+function listener.ondetach(conn)
+	sessions[conn] = nil;
+	incomplete[conn] = nil;
+end
+
+function listener.onincoming(conn, data)
+	sessions[conn]:feed(data);
+end
+
+function listener.ondrain(conn)
+	local response = incomplete[conn];
+	if response and response._send_more then
+		response._send_more();
+	end
+end
+
+local headerfix = setmetatable({}, {
+	__index = function(t, k)
+		local v = "\r\n"..k:gsub("_", "-"):gsub("%f[%w].", s_upper)..": ";
+		t[k] = v;
+		return v;
+	end
+});
+
+function _M.hijack_response(response, listener) -- luacheck: ignore
+	error("TODO");
+end
+function handle_request(conn, request, finish_cb)
+	--log("debug", "handler: %s", request.path);
+	local headers = {};
+	for k,v in pairs(request.headers) do headers[k:gsub("-", "_")] = v; end
+	request.headers = headers;
+	request.conn = conn;
+
+	local date_header = os_date('!%a, %d %b %Y %H:%M:%S GMT'); -- FIXME use
+	local conn_header = request.headers.connection;
+	conn_header = conn_header and ","..conn_header:gsub("[ \t]", ""):lower().."," or ""
+	local httpversion = request.httpversion
+	local persistent = conn_header:find(",keep-alive,", 1, true)
+		or (httpversion == "1.1" and not conn_header:find(",close,", 1, true));
+
+	local response_conn_header;
+	if persistent then
+		response_conn_header = "Keep-Alive";
+	else
+		response_conn_header = httpversion == "1.1" and "close" or nil
+	end
+
+	local response = {
+		request = request;
+		status_code = 200;
+		headers = { date = date_header, connection = response_conn_header };
+		persistent = persistent;
+		conn = conn;
+		send = _M.send_response;
+		send_file = _M.send_file;
+		done = _M.finish_response;
+		finish_cb = finish_cb;
+	};
+	conn._http_open_response = response;
+
+	local host = (request.headers.host or ""):match("[^:]+");
+
+	-- Some sanity checking
+	local err_code, err;
+	if not request.path then
+		err_code, err = 400, "Invalid path";
+	elseif not hosts[host] then
+		if hosts[default_host] then
+			host = default_host;
+		elseif host then
+			err_code, err = 404, "Unknown host: "..host;
+		else
+			err_code, err = 400, "Missing or invalid 'Host' header";
+		end
+	end
+
+	if err then
+		response.status_code = err_code;
+		response:send(events.fire_event("http-error", { code = err_code, message = err, response = response }));
+		return;
+	end
+
+	local event = request.method.." "..host..request.path:match("[^?]*");
+	local payload = { request = request, response = response };
+	log("debug", "Firing event: %s", event);
+	local result = events.fire_event(event, payload);
+	if result ~= nil then
+		if result ~= true then
+			local body;
+			local result_type = type(result);
+			if result_type == "number" then
+				response.status_code = result;
+				if result >= 400 then
+					payload.code = result;
+					body = events.fire_event("http-error", payload);
+				end
+			elseif result_type == "string" then
+				body = result;
+			elseif result_type == "table" then
+				for k, v in pairs(result) do
+					if k ~= "headers" then
+						response[k] = v;
+					else
+						for header_name, header_value in pairs(v) do
+							response.headers[header_name] = header_value;
+						end
+					end
+				end
+			end
+			response:send(body);
+		end
+		return;
+	end
+
+	-- if handler not called, return 404
+	response.status_code = 404;
+	payload.code = 404;
+	response:send(events.fire_event("http-error", payload));
+end
+local function prepare_header(response)
+	local status_line = "HTTP/"..response.request.httpversion.." "..(response.status or codes[response.status_code]);
+	local headers = response.headers;
+	local output = { status_line };
+	for k,v in pairs(headers) do
+		t_insert(output, headerfix[k]..v);
+	end
+	t_insert(output, "\r\n\r\n");
+	return output;
+end
+_M.prepare_header = prepare_header;
+function _M.send_response(response, body)
+	if response.finished then return; end
+	body = body or response.body or "";
+	response.headers.content_length = #body;
+	local output = prepare_header(response);
+	t_insert(output, body);
+	response.conn:write(t_concat(output));
+	response:done();
+end
+function _M.send_file(response, f)
+	if response.finished then return; end
+	local chunked = not response.headers.content_length;
+	if chunked then response.headers.transfer_encoding = "chunked"; end
+	incomplete[response.conn] = response;
+	response._send_more = function ()
+		if response.finished then
+			incomplete[response.conn] = nil;
+			return;
+		end
+		local chunk = f:read(blocksize);
+		if chunk then
+			if chunked then
+				chunk = ("%x\r\n%s\r\n"):format(#chunk, chunk);
+			end
+			-- io.write("."); io.flush();
+			response.conn:write(chunk);
+		else
+			if chunked then
+				response.conn:write("0\r\n\r\n");
+			end
+			-- io.write("\n");
+			if f.close then f:close(); end
+			incomplete[response.conn] = nil;
+			return response:done();
+		end
+	end
+	response.conn:write(t_concat(prepare_header(response)));
+	return true;
+end
+function _M.finish_response(response)
+	if response.finished then return; end
+	response.finished = true;
+	response.conn._http_open_response = nil;
+	if response.on_destroy then
+		response:on_destroy();
+		response.on_destroy = nil;
+	end
+	if response.persistent then
+		response:finish_cb();
+	else
+		response.conn:close();
+	end
+end
+function _M.add_handler(event, handler, priority)
+	events.add_handler(event, handler, priority);
+end
+function _M.remove_handler(event, handler)
+	events.remove_handler(event, handler);
+end
+
+function _M.listen_on(port, interface, ssl)
+	return addserver(interface or "*", port, listener, "*a", ssl);
+end
+function _M.add_host(host)
+	hosts[host] = true;
+end
+function _M.remove_host(host)
+	hosts[host] = nil;
+end
+function _M.set_default_host(host)
+	default_host = host;
+end
+function _M.fire_event(event, ...)
+	return events.fire_event(event, ...);
+end
+function _M.set_option(name, value)
+	options[name] = value;
+end
+
+_M.listener = listener;
+_M.codes = codes;
+_M._events = events;
+return _M;
diff -r 091212cef52a -r 561f0af6c9dc serve/util/cache.lua
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/serve/util/cache.lua	Tue Sep 11 23:27:56 2018 +0100
@@ -0,0 +1,178 @@
+
+local function _remove(list, m)
+	if m.prev then
+		m.prev.next = m.next;
+	end
+	if m.next then
+		m.next.prev = m.prev;
+	end
+	if list._tail == m then
+		list._tail = m.prev;
+	end
+	if list._head == m then
+		list._head = m.next;
+	end
+	list._count = list._count - 1;
+end
+
+local function _insert(list, m)
+	if list._head then
+		list._head.prev = m;
+	end
+	m.prev, m.next = nil, list._head;
+	list._head = m;
+	if not list._tail then
+		list._tail = m;
+	end
+	list._count = list._count + 1;
+end
+
+local cache_methods = {};
+local cache_mt = { __index = cache_methods };
+
+function cache_methods:set(k, v)
+	local m = self._data[k];
+	if m then
+		-- Key already exists
+		if v ~= nil then
+			-- Bump to head of list
+			_remove(self, m);
+			_insert(self, m);
+			m.value = v;
+		else
+			-- Remove from list
+			_remove(self, m);
+			self._data[k] = nil;
+		end
+		return true;
+	end
+	-- New key
+	if v == nil then
+		return true;
+	end
+	-- Check whether we need to remove oldest k/v
+	if self._count == self.size then
+		local tail = self._tail;
+		local on_evict, evicted_key, evicted_value = self._on_evict, tail.key, tail.value;
+		if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
+			-- Cache is full, and we're not allowed to evict
+			return false;
+		end
+		_remove(self, tail);
+		self._data[evicted_key] = nil;
+	end
+
+	m = { key = k, value = v, prev = nil, next = nil };
+	self._data[k] = m;
+	_insert(self, m);
+	return true;
+end
+
+function cache_methods:get(k)
+	local m = self._data[k];
+	if m then
+		return m.value;
+	end
+	return nil;
+end
+
+function cache_methods:items()
+	local m = self._head;
+	return function ()
+		if not m then
+			return;
+		end
+		local k, v = m.key, m.value;
+		m = m.next;
+		return k, v;
+	end
+end
+
+function cache_methods:values()
+	local m = self._head;
+	return function ()
+		if not m then
+			return;
+		end
+		local v = m.value;
+		m = m.next;
+		return v;
+	end
+end
+
+function cache_methods:count()
+	return self._count;
+end
+
+function cache_methods:head()
+	local head = self._head;
+	if not head then return nil, nil; end
+	return head.key, head.value;
+end
+
+function cache_methods:tail()
+	local tail = self._tail;
+	if not tail then return nil, nil; end
+	return tail.key, tail.value;
+end
+
+function cache_methods:resize(new_size)
+	new_size = assert(tonumber(new_size), "cache size must be a number");
+	new_size = math.floor(new_size);
+	assert(new_size > 0, "cache size must be greater than zero");
+	local on_evict = self._on_evict;
+	while self._count > new_size do
+		local tail = self._tail;
+		local evicted_key, evicted_value = tail.key, tail.value;
+		if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
+			-- Cache is full, and we're not allowed to evict
+			return false;
+		end
+		_remove(self, tail);
+		self._data[evicted_key] = nil;
+	end
+	self.size = new_size;
+	return true;
+end
+
+function cache_methods:table()
+	--luacheck: ignore 212/t
+	if not self.proxy_table then
+		self.proxy_table = setmetatable({}, {
+			__index = function (t, k)
+				return self:get(k);
+			end;
+			__newindex = function (t, k, v)
+				if not self:set(k, v) then
+					error("failed to insert key into cache - full");
+				end
+			end;
+			__pairs = function (t)
+				return self:items();
+			end;
+			__len = function (t)
+				return self:count();
+			end;
+		});
+	end
+	return self.proxy_table;
+end
+
+function cache_methods:clear()
+	self._data = {};
+	self._count = 0;
+	self._head = nil;
+	self._tail = nil;
+end
+
+local function new(size, on_evict)
+	size = assert(tonumber(size), "cache size must be a number");
+	size = math.floor(size);
+	assert(size > 0, "cache size must be greater than zero");
+	local data = {};
+	return setmetatable({ _data = data, _count = 0, size = size, _head = nil, _tail = nil, _on_evict = on_evict }, cache_mt);
+end
+
+return {
+	new = new;
+}