Module:User:Theknightwho/parser

This module lacks a documentation subpage. You may create it.

Useful links: root page • root page’s subpages • links • transclusions • testcases • user page • user talk page • userspace

This is a private module sandbox of Theknightwho, for their own experimentation. Items in this module may be added and removed at Theknightwho's discretion; do not rely on this module's stability.

---

local loaded = package.loaded
local loader = package.loaders[2]

local function sentinel()
end

function require(modname)
	assert(
		type(modname) == "string",
		("bad argument #1 to 'require' (string expected, got %s)"):format(type(modname))
	)
	local p = loaded[modname]
	if p then -- is it there?
		if p == sentinel then
			error(("loop or previous error loading module '%s'"):format(modname))
		end
		return p -- package is already loaded
	end
	local init = loader(modname)
	assert(
		init,
		("module '%s' not found"):format(modname)
	)
	loaded[modname] = sentinel
	local actual_arg = _G.arg
	_G.arg = {modname}
	local res = init(modname)
	if res then
		loaded[modname] = res
	end
	_G.arg = actual_arg
	if loaded[modname] == sentinel then
		loaded[modname] = true
	end
	return loaded[modname]
end

mw.loadData = require

setmetatable(loaded, {
	__mode = "v"
})

local Parser = {}
Parser.__index = Parser

------------------------------------------------------------------------------------
--
-- Submodules
--
------------------------------------------------------------------------------------

local Tokenizer = require("Module:User:Theknightwho/parser/tokenizer")

------------------------------------------------------------------------------------
--
-- Cache
--
------------------------------------------------------------------------------------

local cached_nodes = {}
local called_nodes = {}
local content_lang = mw.getContentLanguage()
local current_title = mw.title.getCurrentTitle()
local parsed_nodes = {}
local template_calls = {}
local template_trees = {}
local titles = {}

------------------------------------------------------------------------------------
--
-- Utility functions
--
------------------------------------------------------------------------------------

local ulen = mw.ustring.len

local function capturing_split(str, pattern)
	local ret, start = {}, 1
	pattern = "(.-)(" .. pattern .. ")()"
	repeat
		if start > #str then
			return ret
		end
		local m1, m2, new_start = str:match(pattern, start)
		if not m1 then
			table.insert(ret, str:sub(start))
			return ret
		end
		if m1 ~= "" then
			table.insert(ret, m1)
		end
		start = new_start
		table.insert(ret, m2)
	until false
end

local function text_split(str, pattern)
	local ret, start = {}, 1
	pattern = "(.-)" .. pattern .. "()"
	repeat
		local m1, new_start = str:match(pattern, start)
		if not m1 then
			table.insert(ret, str:sub(start))
			return ret
		end
		table.insert(ret, m1)
		start = new_start
	until false
end

local function comma_value(n)
	local k
	n = tostring(n)
	repeat
		n, k = n:gsub("^(-?%d+)(%d%d%d)", '%1,%2')
	until k == 0
	return n
end

local function frame_arg_key(key)
	-- Parameter keys which are non-decimal integers with no leading zeros between -2^53 and 2^53 that are unsigned when positive (and not -0) are converted to numbers by PHP.
	if key == "0" or key:find("^-?[1-9]%d*$") then
		local num_key = tonumber(key)
		if (
			num_key >= -9007199254740992 and
			num_key <= 9007199254740992 and
			-- Treated as equal to +/-9007199254740992 due to floating-point rounding errors.
			key ~= "9007199254740993" and
			key ~= "-9007199254740993"
		) then
			key = num_key
		end
	end
	return key
end

local function len_event(t)
	if #t == 0 then
		local mt = getmetatable(t)
		if mt and mt.__len then
			return mt.__len()
		end
	end
	return #t
end

-- Standard PHP character escape.
local function php_escaped(text)
	return (text:gsub("[\"&'<>]", {
		["\""] = "&quot;", ["&"] = "&amp;", ["'"] = "&#039;",
		["<"] = "&lt;", [">"] = "&gt;",
	}))
end

-- Almost identical to mw.text.nowiki, but with minor changes to match the PHP equivalent: ";" always escapes, and colons in certain protocols only escape after regex \b.
local function php_wfEscapeWikiText(text)
	return (text
		:gsub("[\"&'<=>%[%]{|};]", {
			["\""] = "&#34;", ["&"] = "&#38;", ["'"] = "&#39;",
			["<"] = "&#60;", ["="] = "&#61;", [">"] = "&#62;",
			["["] = "&#91;", ["]"] = "&#93;", ["{"] = "&#123;",
			["|"] = "&#124;", ["}"] = "&#125;", [";"] = "&#59;"
		})
		:gsub("%f[^%z\r\n][#*: \n\r\t]", {
			["#"] = "&#35;", ["*"] = "&#42;", [":"] = "&#58;",
			[" "] = "&#32;", ["\n"] = "&#10;", ["\r"] = "&#13;",
			["\t"] = "&#9;"
		})
		:gsub("(%f[^%z\r\n])%-(%-%-%-)", "%1&#45;%2")
		:gsub("__", "_&#95;")
		:gsub("://", "&#58;//")
		:gsub("([IP]?[MRS][BFI][CDN])([\t\n\f\r ])", function(m1, m2)
			if m1 == "ISBN" or m1 == "RFC" or m1 == "PMID" then
				return m1 .. m2:gsub(".", {
					["\t"] = "&#9;", ["\n"] = "&#10;", ["\f"] = "&#12;",
					["\r"] = "&#13;", [" "] = "&#32;"
				})
			end
		end)
		:gsub("[%w_]+:", {
			["bitcoin:"] = "bitcoin&#58;", ["geo:"] = "geo&#58;", ["magnet:"] = "magnet&#58;",
			["mailto:"] = "mailto&#58;", ["matrix:"] = "matrix&#58;", ["news:"] = "news&#58;",
			["sip:"] = "sip&#58;", ["sips:"] = "sips&#58;", ["sms:"] = "sms&#58;",
			["tel:"] = "tel&#58;", ["urn:"] = "urn&#58;", ["xmpp:"] = "xmpp&#58;"
		}))
end

local function reverse_table(t)
	local new_t = {}
	local new_t_i = 1
	for i = #t, 1, -1 do
		new_t[new_t_i] = t[i]
		new_t_i = new_t_i + 1
	end
	return new_t
end

local function shallowcopy(t)
	local ret = {}
	for k, v in pairs(t) do
		ret[k] = v
	end
	return ret
end

local function tonumber_loose(text)
	if type(text) == "string" then
		local text_lower = text:lower()
		if not (
			text_lower == "inf" or
			text_lower == "-inf" or
			text_lower == "nan" or
			text_lower == "-nan"
		) then
			text = tonumber(text) or text
		end
	end
	return text
end

local function tonumber_strict(text)
	if type(text) == "string" then
		local num_text = text:match("^[+%-]?%d+%.?%d*")
		text = tonumber(num_text) or text
	end
	return text
end

------------------------------------------------------------------------------------
--
-- Errors
--
------------------------------------------------------------------------------------

local errors = {}
for _, k in ipairs{"BadRoute", "DisallowedModifier", "MissedCloseToken", "Unresolved"} do
	errors[k] = {}
end

------------------------------------------------------------------------------------
--
-- Frame
--
------------------------------------------------------------------------------------

local Frame = mw.getCurrentFrame()
local actual_parent = Frame:getParent()

local function eq(a, b)
	return rawequal(a, b) or rawequal(b, Frame)
end

setmetatable(Frame, {__eq = eq})

local function newCallbackParserValue(callback)
	local value, cache = {}

	function value:expand()
		if not cache then
			cache = callback()
		end
		return cache
	end

	return value
end

function Frame:getArgument(opt)
	local name = type(opt) == "table" and opt.name or opt
	return newCallbackParserValue(
		function ()
			return self.args[name]
		end
	)
end

function Frame:getParent()
	return nil
end

Frame.really_preprocess = Frame.preprocess

function Frame:preprocess(opt)
	return Parser:parse(opt)
end

function Frame:newParserValue(opt)
	local text = type(opt) == "table" and opt.text or opt
	return newCallbackParserValue(
		function ()
			return self:preprocess(text)
		end
	)
end

function Frame:newTemplateParserValue(opt)
	assert(
		type(opt) == "table",
		"frame:newTemplateParserValue: the first parameter must be a table"
	)
	assert(
		opt.title,
		"frame:newTemplateParserValue: a title is required"
	)
	return newCallbackParserValue(
		function ()
			return self:expandTemplate(opt)
		end
	)
end

function Frame:argumentPairs()
	return pairs(self.args)
end

function Frame:newChild(opt)
	assert(
		type(opt) == "table",
		"frame:newChild: the first parameter must be a table"
	)
	local title = opt.title and tostring(opt.title) or self:getTitle()
	assert(
		not opt.args or type(opt.args) == "table",
		"frame:newChild: args must be a table"
	)
	local args = opt.args or {}
	local parent = opt.parent ~= false and self
	local child = setmetatable({}, {
		__index = Frame,
		__eq = eq
	})
	
	function child:getParent()
		return parent
	end
	
	function child:getTitle()
		return title
	end
	
	child.args = args
	
	return child
end

local parent_frame, child_frame
if actual_frame then
	parent_frame = Frame:newChild{title = actual_parent:getTitle(), args = actual_parent.args, parent = false}
	child_frame = parent_frame:newChild{title = Frame:getTitle(), args = Frame.args}
else
	child_frame = Frame:newChild{title = Frame:getTitle(), args = Frame.args, parent = false}
end

function mw.getCurrentFrame()
	return child_frame
end

------------------------------------------------------------------------------------
--
-- Tags
--
------------------------------------------------------------------------------------

local tags = {}
for _, k in ipairs{"categorytree", "ce", "chem", "gallery", "graph", "hiero", "imagemap", "inputbox", "math", "nowiki", "pre", "score", "section", "source", "syntaxhighlight", "templatedata", "timeline"} do
	tags[k] = true
end

local tag_captures = {}
for tag in pairs(tags) do
	tag = tag:gsub(".", function(m)
		return "[" .. m:upper() .. m .. "]"
	end)
	table.insert(tag_captures, "(<" .. tag .. ".->)")
	table.insert(tag_captures, "(<" .. "/" .. tag .. "%s->)")
end
for _, tag in ipairs{"includeonly", "noinclude", "onlyinclude"} do
	tag = tag:gsub(".", function(m)
		return "[" .. m:upper() .. m .. "]"
	end)
	table.insert(tag_captures, "(<" .. tag .. ".->)")
	table.insert(tag_captures, "(<" .. "/" .. tag .. ".->)")
end
table.insert(tag_captures, "(<!%-%-)")
table.insert(tag_captures, "(%-%->)")

local iferror_tags = {}
for _, k in ipairs{"div", "p", "span", "strong"} do
	iferror_tags[k] = true
end

------------------------------------------------------------------------------------
--
-- Nodes
--
------------------------------------------------------------------------------------

local Wikitext = {}
Wikitext.__index = Wikitext

function Wikitext:new(t, type)
	local node = select(2, xpcall(
		function()
			return setmetatable(t, self)
		end,
		function()
			return setmetatable({t}, self)
		end
	))
	cached_nodes[node] = type
	return node
end

function Wikitext:unresolved_handler(func)
	return function(err)
		if err == errors.Unresolved then
			return func()
		else
			if self.title then
				-- TODO: implement template traceback
				error("Error parsing " .. current_title .. ": " .. debug.traceback(err), 2)
			else
				error(debug.traceback(err), 2)
			end
		end
	end
end

function Wikitext:resolve()
	for k in ipairs(self) do
		self[k] = self:get_child(self[k], true)
	end
	return select(2, xpcall(
		function()
			return table.concat(self)
		end,
		function()
			return self
		end
	))
end

function Wikitext:try_resolve()
	self = select(2, xpcall(
		function()
			return self:resolve()
		end,
		self:unresolved_handler(function()
			return self
		end)
	))
	return self
end

function Wikitext:get_child(node, no_trim)
	if called_nodes[node] then
		return called_nodes[node]
	end
	if type(node) == "table" then
		node = node:try_resolve()
	end
	if type(node) == "string" and not no_trim then
		local node_old = node
		node = node:match("^[\9-\11\13\32]*(.-)[\9-\11\13\32]*$")
		called_nodes[node_old] = node
		called_nodes[node] = node
	end
	return node
end

function Wikitext:unresolved()
	error(errors.Unresolved)
end

function Wikitext:get_arg()
	return nil
end

function Wikitext:prepare_frames()
	return nil
end

function Wikitext:get_instance(cached_node, name, args)
	if type(cached_node) ~= "table" then
		return cached_node
	end
	
	local node = {}
	
	if cached_nodes[cached_node] then
		function node:try_resolve()
			if not parsed_nodes[cached_node] then
				cached_node = self:get_child(cached_node)
				parsed_nodes[cached_node] = true
			end
			if type(cached_node) == "string" then
				return cached_node
			end
			self = select(2, xpcall(
				function()
					return self:resolve()
				end,
				self:unresolved_handler(function()
					return self
				end)
			))
			return self
		end
		
		function node:get_arg(arg)
			return args and args[arg]
		end
		
		if cached_nodes[cached_node] == "Template" then
			function node:prepare_frames(mod)
				local parent_args = args and {}
				for k, v in pairs(args) do
					local k_new = frame_arg_key(k)
					parent_args[k_new] = args[k]
				end
				parent_frame = Frame:newChild{title = name, args = parent_args, parent = false}
				for k in pairs(self.params) do
					self.params[k] = self:get_child(self.params[k])
				end
				local child_args = self.params and shallowcopy(self.params)
				child_frame = parent_frame:newChild{title = mod, args = child_args}
				return true
			end
		end
	end
	
	return setmetatable(node, {
		__index = function(t, k)
			if type(rawget(cached_node, k)) == "table" then
				t[k] = self:get_instance(cached_node[k], name, args)
				return t[k]
			end
			return cached_node[k]
		end,
		__ipairs = function(t)
			return function(t, i)
				i = i + 1
				local v = t[i]
				if v then
					return i, v
				end
			end, t, 0
		end,
		__pairs = function(t)
			local done, mt = {}
			return function(t, k)
				if not mt then
					k = next(t, k)
					local v = k and t[k]
					if v then
						done[k] = true
						return k, v
					end
					mt = true
					k = next(cached_node)
				end
				while k and done[k] do
					k = next(cached_node, k)
				end
				local v = k and t[k]
				if v then
					done[k] = true
					return k, v
				end
			end, t
		end,
		__len = function()
			return #cached_node
		end
	})
end

local Argument = Wikitext:new{}
Argument.__index = Argument

function Argument:resolve()
	self[1] = self:get_child(self[1])
	if type(self[1]) == "table" or cached_nodes[self] then
		self:unresolved()
	elseif self:get_arg(self[1]) then
		return self:get_arg(self[1])
	end
	self[2] = self:get_child(self[2])
	if type(self[2]) == "table" then
		self:unresolved()
	else
		return self[2] or "{{{" .. self[1] .. "}}}"
	end
end

local Template = Wikitext:new{}
Template.__index = Template

function Template:parser_function_error(mw_page, ...)
	local msg = mw.title.new("MediaWiki:" .. mw_page):getContent()
	for i, arg in ipairs{...} do
		msg = msg:gsub("$" .. i, arg)
	end
	return Parser:parse("<strong class=\"error\">" .. php_escaped(msg) .. "</strong>")
end

local expr = {}
for v, k in ipairs{"NEGATIVE", "POSITIVE", "PLUS", "MINUS", "TIMES", "DIVIDE", "MOD", "OPEN", "CLOSE", "AND", "OR", "NOT", "EQUALITY", "LESS", "GREATER", "LESSEQ", "GREATEREQ", "NOTEQ", "ROUND", "EXPONENT", "SINE", "COSINE", "TANGENS", "ARCSINE", "ARCCOS", "ARCTAN", "EXP", "LN", "ABS", "FLOOR", "TRUNC", "CEIL", "POW", "PI", "FMOD", "SQRT"} do
	expr[k] = v
end

local expr_white_class = {}
for _, k in ipairs{" ", "\t", "\r", "\n"} do
	expr_white_class[k] = true
end

local expr_number_class = {}
for _, k in ipairs{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "."} do
	expr_number_class[k] = true
end

local expr_alpha_class = {}
for _, k in ipairs{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"} do
	expr_alpha_class[k] = true
end

local expr_precedence = {
	[expr.NEGATIVE] = 10, [expr.POSITIVE] = 10, [expr.EXPONENT] = 10,
	[expr.SINE] = 9, [expr.COSINE] = 9, [expr.TANGENS] = 9,
	[expr.ARCSINE] = 9, [expr.ARCCOS] = 9, [expr.ARCTAN] = 9,
	[expr.EXP] = 9, [expr.LN] = 9, [expr.ABS] = 9,
	[expr.FLOOR] = 9, [expr.TRUNC] = 9, [expr.CEIL] = 9,
	[expr.NOT] = 9, [expr.SQRT] = 9, [expr.POW] = 8,
	[expr.TIMES] = 7, [expr.DIVIDE] = 7, [expr.MOD] = 7,
	[expr.FMOD] = 7, [expr.PLUS] = 6, [expr.MINUS] = 6,
	[expr.ROUND] = 5, [expr.EQUALITY] = 4, [expr.LESS] = 4,
	[expr.GREATER] = 4, [expr.LESSEQ] = 4, [expr.GREATEREQ] = 4,
	[expr.NOTEQ] = 4, [expr.AND] = 3, [expr.OR] = 2,
	[expr.PI] = 0, [expr.OPEN] = -1, [expr.CLOSE] = -1,
}

local expr_names = {
	[expr.NEGATIVE] = "-", [expr.POSITIVE] = "+", [expr.NOT] = "not",
	[expr.TIMES] = "*", [expr.DIVIDE] = "/", [expr.MOD] = "mod",
	[expr.FMOD] = "fmod", [expr.PLUS] = "+", [expr.MINUS] = "-",
	[expr.ROUND] = "round", [expr.EQUALITY] = "=", [expr.LESS] = "<",
	[expr.GREATER] = ">", [expr.LESSEQ] = "<=", [expr.GREATEREQ] = ">=",
	[expr.NOTEQ] = "<>", [expr.AND] = "and", [expr.OR] = "or",
	[expr.EXPONENT] = "e", [expr.SINE] = "sin", [expr.COSINE] = "cos",
	[expr.TANGENS] = "tan", [expr.ARCSINE] = "asin", [expr.ARCCOS] = "acos",
	[expr.ARCTAN] = "atan", [expr.LN] = "ln", [expr.EXP] = "exp",
	[expr.ABS] = "abs", [expr.FLOOR] = "floor", [expr.TRUNC] = "trunc",
	[expr.CEIL] = "ceil", [expr.POW] = "^", [expr.PI] = "pi", [expr.SQRT] = "sqrt",
}

local expr_signs = {
	["<="] = expr.LESSEQ, [">="] = expr.GREATEREQ, ["<>"] = expr.NOTEQ,
	["!="] = expr.NOTEQ, ["*"] = expr.TIMES, ["/"] = expr.DIVIDE,
	["^"] = expr.POW, ["="] = expr.EQUALITY, ["<"] = expr.LESS,
	[">"] = expr.GREATER
}

local expr_stack_min = {
	[expr.NEGATIVE] = 1, [expr.POSITIVE] = 1, [expr.TIMES] = 2,
	[expr.DIVIDE] = 2, [expr.MOD] = 2, [expr.FMOD] = 2,
	[expr.PLUS] = 2, [expr.MINUS] = 2, [expr.AND] = 2,
	[expr.OR] = 2, [expr.EQUALITY] = 2, [expr.NOT] = 1,
	[expr.ROUND] = 2, [expr.LESS] = 2, [expr.GREATER] = 2,
	[expr.LESSEQ] = 2, [expr.GREATEREQ] = 2, [expr.NOTEQ] = 2,
	[expr.EXPONENT] = 2, [expr.SINE] = 1, [expr.COSINE] = 1,
	[expr.TANGENS] = 1, [expr.ARCSINE] = 1, [expr.ARCCOS] = 1,
	[expr.ARCTAN] = 1, [expr.EXP] = 1, [expr.LN] = 1,
	[expr.ABS] = 1, [expr.FLOOR] = 1, [expr.TRUNC] = 1,
	[expr.CEIL] = 1, [expr.POW] = 2, [expr.SQRT] = 1
}

local expr_unary = {}
for _, k in ipairs{"NOT", "SINE", "COSINE", "TANGENS", "ARCSINE", "ARCCOS", "ARCTAN", "EXP", "LN", "ABS", "FLOOR", "TRUNC", "CEIL", "SQRT"} do
	expr_unary[expr[k]] = true
end

local expr_words = {
	["mod"] = expr.MOD, ["fmod"] = expr.FMOD, ["and"] = expr.AND,
	["or"] = expr.OR, ["not"] = expr.NOT, ["round"] = expr.ROUND,
	["div"] = expr.DIVIDE, ["e"] = expr.EXPONENT, ["sin"] = expr.SINE,
	["cos"] = expr.COSINE, ["tan"] = expr.TANGENS, ["asin"] = expr.ARCSINE,
	["acos"] = expr.ARCCOS, ["atan"] = expr.ARCTAN, ["exp"] = expr.EXP,
	["ln"] = expr.LN, ["abs"] = expr.ABS, ["trunc"] = expr.TRUNC,
	["floor"] = expr.FLOOR, ["ceil"] = expr.CEIL, ["pi"] = expr.PI,
	["sqrt"] = expr.SQRT
}

local expr_operations = {
	[expr.NEGATIVE] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, arg * -1)
	end,
	
	[expr.POSITIVE] = function(op, stack)
	end,
	
	[expr.TIMES] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left * right)
	end,
	
	[expr.DIVIDE] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		if right == 0 then
			self:parser_function_error("pfunc_expr_division_by_zero")
		end
		table.insert(stack, left / right)
	end,
	
	[expr.MOD] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		if right == 0 then
			self:parser_function_error("pfunc_expr_division_by_zero")
		end
		table.insert(stack, left % right)
	end,
	
	[expr.FMOD] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		if right == 0 then
			self:parser_function_error("pfunc_expr_division_by_zero")
		end
		table.insert(stack, math.fmod(left, right))
	end,
	
	[expr.PLUS] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left + right)
	end,
	
	[expr.MINUS] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left - right)
	end,
	
	[expr.AND] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left and right and 1 or 0)
	end,
	
	[expr.OR] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, (left or right) and 1 or 0)
	end,
	
	[expr.EQUALITY] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left == right and 1 or 0)
	end,
	
	[expr.NOT] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, (not arg) and 1 or 0)
	end,
	
	[expr.ROUND] = function(op, stack)
		local mult = 10^(table.remove(stack) or 0)
		local value = table.remove(stack)
		table.insert(stack, math.floor(value * mult + 0.5) / mult)
	end,
	
	[expr.LESS] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left < right and 1 or 0)
	end,
	
	[expr.GREATER] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left > right and 1 or 0)
	end,
	
	[expr.LESSEQ] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left <= right and 1 or 0)
	end,
	
	[expr.GREATEREQ] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left >= right and 1 or 0)
	end,
	
	[expr.NOTEQ] = function(op, stack)
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, left ~= right and 1 or 0)
	end,
	
	[expr.EXPONENT] = function(op, stack) -- TODO
		local right = table.remove(stack)
		local left = table.remove(stack)
	end,
	
	[expr.SINE] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.sin(arg))
	end,
	
	[expr.COSINE] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.cos(arg))
	end,
	
	[expr.TANGENS] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.tan(arg))
	end,
	
	[expr.ARCSINE] = function(op, stack)
		local arg = table.remove(stack)
		if arg < -1 or arg > 1 then
			self:parser_function_error("pfunc_expr_invalid_argument")
		end
		table.insert(stack, math.asin(arg))
	end,
	
	[expr.ARCCOS] = function(op, stack)
		local arg = table.remove(stack)
		if arg < -1 or arg > 1 then
			self:parser_function_error("pfunc_expr_invalid_argument")
		end
		table.insert(stack, math.acos(arg))
	end,
	
	[expr.ARCTAN] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.atan(arg))
	end,
	
	[expr.EXP] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.exp(arg))
	end,
	
	[expr.LN] = function(op, stack)
		local arg = table.remove(stack)
		if arg <= 0 then
			self:parser_function_error("pfunc_expr_invalid_argument_ln")
		end
		table.insert(stack, math.log(arg))
	end,
	
	[expr.ABS] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.abs(arg))
	end,
	
	[expr.FLOOR] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.floor(arg))
	end,
	
	[expr.TRUNC] = function(op, stack) -- TODO
		local arg = table.remove(stack)
	end,
	
	[expr.CEIL] = function(op, stack)
		local arg = table.remove(stack)
		table.insert(stack, math.ceil(arg))
	end,
	
	[expr.POW] = function(op, stack) -- TODO
		local right = table.remove(stack)
		local left = table.remove(stack)
		table.insert(stack, math.pow(left, right))
	end,
	
	[expr.SQRT] = function(op, stack)
		local arg = table.remove(stack)
		local ret = math.sqrt(arg)
		--if ret == tonumber("NaN") then -- TODO
			self:parser_function_error("pfunc_expr_not_a_number")
		--end
		table.insert(stack, ret)
	end
}

-- Implements #EXPR and #IFEXPR.
function Template:expression(str)
	local operands, operators = {}, {}
	for k, v in pairs{
		["&lt;"] = "<", ["&gt;"] = ">", ["&minus;"] = "-", ["−"] = "-"
	} do
		str = str:gsub(k, v)
	end
	local p, fin, expecting, name, op = 1, str:len(), "expression"
	while p <= fin do
		repeat
			if #operands > 100 or #operators > 100 then
				return self:parser_function_error("pfunc_expr_stack_exhausted")
			end
			local char = str:sub(p, p)
			local char2 = str:sub(p + 1, p + 2)
			if expr_white_class[char] then
				while expr_white_class[char] do
					p = p + 1
					char = str:sub(p, p)
				end
				break
			elseif expr_number_class[char] then
				if expecting ~= "expression" then
					return self:parser_function_error("pfunc_expr_unexpected_number")
				end
				local len = 0
				while expr_number_class[char] do
					len = len + 1
					p = p + 1
					char = str:sub(p, p)
				end
				table.insert(operands, tonumber_loose(str:sub(p - len, p - 1)))
				expecting = "operator"
				break
			elseif expr_alpha_class[char] then
				local remaining = str:sub(p)
				local word = remaining:match("^%a*")
				if not word then
					return self:parser_function_error("pfunc_expr_preg_match_failure")
				end
				word = word:lower()
				p = p + word:len()
				if not expr_words[word] then
					return self:parser_function_error("pfunc_expr_unrecognised_word", word)
				end
				op = expr_words[word]
				if op == expr.EXPONENT or op == expr.PI then
					if expecting ~= "expression" then
						break
					end
					local v = op == expr.EXPONENT and math.exp(1) or math.pi
					table.insert(operands, v)
					expecting = "operator"
					break
				elseif expr_unary[word] then
					if expecting ~= "expression" then
						return self:parser_function_error("pfunc_expr_unexpected_operator", word)
					end
					tabe.insert(operators, op)
					break
				end
				name = word
			elseif expr_signs[char2] then
				name = char2
				op = expr_signs[char2]
				p = p + 2
			elseif char == "+" then
				p = p + 1
				if expecting == "expression" then
					table.insert(operators, expr.POSITIVE)
					break
				end
				op = expr.PLUS
			elseif char == "-" then
				p = p + 1
				if expecting == "expression" then
					table.insert(operators, expr.NEGATIVE)
					break
				end
				op = expr.MINUS
			elseif char == "(" then
				if expecting == "operator" then
					return self:parser_function_error("pfunc_expr_unexpected_operator", "(")
				end
				table.insert(operators, expr.OPEN)
				p = p + 1
				break
			elseif char == ")" then
				local last_op = operators[#operators]
				repeat
					local last_op = table.remove(operators)
				until last_op == expr.OPEN or not last_op
				if not last_op then
					return self:parser_function_error("pfunc_expr_unexpected_closing_bracket")
				end
				expecting = "operator"
				p = p + 1
				break
			elseif expr_signs[char] then
				name = char
				op = expr_signs[char]
				p = p + 1
			else
				--local utf_expr = 
			end
			if execting == "expression" then
				return self:parser_function_error("pfunc_expr_unexpected_operator", name)
			end
			local last_op = operators[#operators]
			while last_op and expr_precedence[op] <= expr_precedence[last_op] do
				if #operands < expr_stack_min[last_op] then
					self:parser_function_error("pfunc_expr_missing_operand", expr_names[last_op])
				end
				expr_operations[last_op](last_op, operands)
				table.remove(operators)
				last_op = operators[#operators]
			end
			table.insert(operators, op)
			expecting = "expression"
		until true
	end
	while #operators > 0 and op == table.remove(operators) do
		if op == expr.OPEN then
			return self:parser_function_error("pfunc_expr_unclosed_bracket", name)
		elseif expr_operations[op] then
			expr_operations[op](op, operands)
		else
			self:parser_function_error("pfunc_expr_unknown_error")
		end
	end
	return table.concat(operands, "<br />\n")
end

-- Implements PADLEFT and PADRIGHT.
function Template:pad(left, str, len, pad_str)
	len = len and tonumber_strict(len)
	if (
		not len or
		pad_str == "" or
		type(len) ~= "number"
		or len < 1
	) then
		return str, ""
	elseif not pad_str then
		pad_str = "0"
	end
	local param3_len = ulen(pad_str)
	local ret_len = math.min(len, 500) - ulen(str)
	if ret_len <= 0 then
		return str, ""
	end
	local reps = math.floor(ret_len / param3_len)
	local rem = ret_len % param3_len
	if left then
		return pad_str:rep(reps) .. pad_str:sub(1, rem) .. str
	end
	return str .. pad_str:rep(reps) .. pad_str:sub(1, rem)
end

local case_insensitive = {}
case_insensitive.__index = function(t, k)
	local k_upper = k:upper()
	if type(k) == "string" and case_insensitive[k_upper] then
		return rawget(t, k_upper)
	end
end
for _, k in ipairs{"#BABEL", "#CATEGORYTREE", "#DATEFORMAT", "#EXPR", "#FORMATDATE", "#IF", "#IFEQ", "#IFERROR", "#IFEXIST", "#IFEXPR", "#INVOKE", "#LANGUAGE", "#LQTPAGELIMIT", "#LST", "#LSTH", "#LSTX", "#PROPERTY", "#REL2ABS", "#SECTION", "#SECTION-H", "#SECTION-X", "#SPECIAL", "#SPECIALE", "#STATEMENTS", "#SWITCH", "#TAG", "#TARGET", "#TIME", "#TIMEL", "#TITLEPARTS", "#USELIQUIDTHREADS", "ANCHORENCODE", "ARTICLEPATH", "BIDI", "CANONICALURL", "CANONICALURLE", "FILEPATH", "FORMATNUM", "FULLURL", "FULLURLE", "GENDER", "GRAMMAR", "INT", "LC", "LCFIRST", "LOCALURL", "LOCALURLE", "MSG", "MSGNW", "NOEXTERNALLANGLINKS", "NS", "NSE", "PADLEFT", "PADRIGHT", "PAGEID", "PLURAL", "RAW", "SAFESUBST", "SCRIPTPATH", "SERVER", "SERVERNAME", "STYLEPATH", "SUBST", "UC", "UCFIRST", "URLENCODE"} do
	case_insensitive[k] = true
end

Template.parser_functions = {
	["#BABEL"] = function(self)
		self:load_array_params()
		return Frame:callParserFunction(
			"#BABEL",
			self.params
		)
	end,
	
	["#CATEGORYTREE"] = function(self) -- TODO
	end,
	
	["#EXPR"] = function(self)
		self:load_array_params(1)
		return self:expression(self.params[1])
	end,

	["#FORMATDATE"] = function(self) -- TODO
		-- self:load_array_params(2) ?
	end,
	
	["#IF"] = function(self)
		self:load_array_params(3, 1)
		local n = self.params[1] ~= "" and 2 or 3
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["#IFEQ"] = function(self)
		self:load_array_params(4, 2)
		for i = 1, 2 do
			self.params[i] = tonumber_loose(self.params[i])
		end
		local n = self.params[1] == self.params[2] and 3 or 4
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["#IFERROR"] = function(self)
		self:load_array_params(3, 1)
		local n = 3
		for tag in self.params[1]:gmatch("<([adginoprstv]+)[\9-\11\13\32][^>]-%f[^\9-\11\13\32]class=\"[^\">]-%f[^\9-\11\13\32\"]error%f[\9-\11\13\32\"][^\">]-\"") do
			if iferror_tags[tag] then
				n = 2
				break
			end
		end
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return (
			self.params[n] or
			n == 2 and "" or
			n == 3 and self.params[1]
		)
	end,
	
	["#IFEXIST"] = function(self)
		self:load_array_params(3, 1)
		local title = mw.title.new(self.params[1])
		local n = title and title.exists and 2 or 3
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["#IFEXPR"] = function(self)
		self:load_array_params(3, 1)
		local t = Frame:callParserFunction(
			"#IFEXPR",
			self.params[1],
			"2", "3"
		)
		local n = t == "2" and 2 or t == "3" and 3
		if not n then
			return t
		end
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["#INVOKE"] = function(self)
		if self[2] then
			self.params = self.params or {}
			local params, added, offset, unresolved = self[2], {}, 0
			if not params[1][4] then
				self[3] = params[1][2]
				offset = offset + 1
				params[1][4] = true
			end
			if not params[2] then
				error("Module error: You must specify a function to call.")
			end
			if not params[2][4] then
				if params[2][3] then
					self[4] = Wikitext:new({params[2][1], "=", params[2][2]}, cached_nodes[self] and "Wikitext")
				else
					self[4] = params[2][2]
					offset = offset + 1
				end
				params[2][4] = true
			end
			for i = 3, len_event(params) do
				repeat
					if not params[i][4] then
						if params[i][3] then
							params[i][1] = self:get_child(params[i][1])
							if type(params[i][1]) == "table" then
								unresolved = true
								break
							end
							params[i][1] = frame_arg_key(params[i][1])
						else
							params[i][1] = params[i][1] - offset
						end
						params[i][4] = true
					end
					if not added[params[i][1]] then
						self.params[params[i][1]] = params[i][2]
						added[params[i][1]] = true
					end
				until true
			end
			if unresolved then
				self:unresolved()
			end
			self[2] = nil
		end
		self[3] = self:get_child(self[3])
		self[4] = self:get_child(self[4])
		if type(self[3]) == "table" or type(self[4]) == "table" then
			self:unresolved()
		end
		local mod = "Module:" .. self[3]
		if not self:prepare_frames(mod) then
			self:unresolved()
		end
		if not require(mod)[self[4]] then error(mw.dumpObject(self)) end
		return tostring(require(mod)[self[4]](child_frame))
	end,
	
	["#LANGUAGE"] = function(self) -- TODO
		-- self:load_array_params(2) ?
	end,
	
	["#LQTPAGELIMIT"] = function(self) -- TODO
	end,
	
	["#LST"] = function(self) -- TODO
	end,
	
	["#LSTH"] = function(self) -- TODO
	end,
	
	["#LSTX"] = function(self) -- TODO
	end,
	
	["#PROPERTY"] = function(self) -- TODO
	end,
	
	["#REL2ABS"] = function(self)
		self:load_array_params(2)
		local from = self.params[2]
		if from == "" then
			from = current_title.prefixedText
		end
		local to = self.params[1]
			:reverse()
			:gsub("^[ /]*", "")
			:reverse()
		if to == "" or to == "." then
			return from
		end
		if self.params[1]:find("^%.?%.?/?$") then
			from = ""
		end
		local full_path = from .. "/" .. to
		local exploded, i = text_split(full_path, "/"), 1
		repeat
			if exploded[i] == "" or exploded[i] == "." then
				table.remove(exploded, i)
			elseif exploded[i] == ".." then
				if i == 1 then
					return self:parser_function_error("pfunc_rel2abs_invalid_depth", full_path)
				end
				table.remove(exploded, i)
				table.remove(exploded, i - 1)
				i = i - 1
			else
				i = i + 1
			end
		until not exploded[i]
		return table.concat(exploded, "/")
	end,
	
	["#SPECIAL"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"#SPECIAL",
			self.params
		)
	end,
	
	["#SPECIALE"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"#SPECIALE",
			self.params
		)
	end,
	
	["#STATEMENTS"] = function(self) -- TODO
	end,
	
	["#SWITCH"] = function(self)
		-- `added` keeps track of whether a key has already been added to self.params in the current run. If present, the new value is ignored. We can't do this by simply checking whether it's already been added to self.params or not, because key X might be a variable during caching (so needs to be evaluated each call), while key Y might be static. In situations where X == Y, Y should be ignored. However, because it's static, it will already be present in the cached template's self.params table, so checking self.params after evaluating X in a template call would result in X's value being discarded.
		-- `add_keys` stores any shortcut keys (e.g. a and b in a|b|c=d).
		-- The parameter `false` stores the default value, given by #default (case insensitive). These can also act as keys (e.g. if #dEfault and #defaulT are given, #defaulT (the second) would give the actual default value as it's the last instance, but an exact input of #dEfault simply treats the first as an ordinary key and matches it. This default is overridden if any values without keys are given at the end.
		if self[2] then
			self.params = self.params or {}
			local params, added, add_keys, unresolved = self[2], {}, {}
			self.params[1] = params[1][2]
			for i = 2, len_event(params) do
				repeat
					if params[i][3] then
						if not params[i][4] then
							params[i][1] = self:get_child(params[i][1])
							if type(params[i][1]) == "table" then
								unresolved = true
								add_keys = {}
								break
							end
							params[i][4] = true
						end
						if not added[params[i][1]] then
							self.params[params[i][1]] = params[i][2]
							added[params[i][1]] = true
						end
						for _, k in ipairs(add_keys) do
							params[k][2] = self:get_child(params[k][2])
							if type(params[k][2]) == "table" then
								unresolved = true
								break
							end
							if not added[params[k][2]] then
								self.params[params[k][2]] = params[i][2]
								added[params[k][2]] = true
							end
						end
						add_keys = {}
						if params[i][5] == nil then
							params[i][5] = params[i][1]:lower() == "#defaultsort"
						end
						if params[i][5] then
							self.params[false] = params[i][2]
						end
					else
						table.insert(add_keys, i)
					end
				until true
			end
			-- Default value is always the final parameter if it doesn't have an equals sign.
			if len_event(add_keys) > 0 then
				local k = add_keys[len_event(add_keys)]
				self.params[false] = params[k][2]
			end
			if unresolved then
				self:unresolved()
			end
			self[2] = nil
		end
		self.params[1] = self:get_child(self.params[1])
		if type(self.params[1]) == "table" then
			self:unresolved()
		end
		local n = self.params[self.params[1]] and self.params[1] or false
		self.params[n] = self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["#TAG"] = function(self) -- TODO
	end,
	
	["#TARGET"] = function(self) -- TODO
	end,
	
	["#TIME"] = function(self) -- TODO
	end,
	
	["#TIMEL"] = function(self) -- TODO
	end,
	
	["#TITLEPARTS"] = function(self)
		self:load_array_params(3)
		return Frame:callParserFunction(
			"#TITLEPARTS",
			self.params
		)
	end,
	
	["#USELIQUIDTHREADS"] = function(self) -- TODO
	end,
	
	["ANCHORENCODE"] = function(self)
		self:load_array_params(1)
		return mw.uri.anchorEncode(self.params[1])
	end,
	
	["BASEPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.baseText and php_wfEscapeWikiText(title.baseText) or ""
	end,
	
	["BASEPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.baseText and php_wfEscapeWikiText(mw.uri.encode(title.baseText, "WIKI")) or ""
	end,
	
	["BIDI"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"BIDI",
			self.params
		)
	end,
	
	["CANONICALURL"] = function(self)
		self:load_array_params(2)
		return tostring(mw.uri.canonicalUrl(
			self.params[1],
			self.params[2]
		))
	end,
	
	["CANONICALURLE"] = function(self)
		self:load_array_params(2)
		return mw.uri.encode(tostring(mw.uri.canonicalUrl(
			self.params[1],
			self.params[2]
		)), "WIKI")
	end,
	
	["CASCADINGSOURCES"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.cascadingProtection and type(title.cascadingProtection.sources) == "table" and table.concat(title.cascadingProtection.sources, "|") or ""
	end,
	
	["DEFAULTSORT"] = function(self)
		self:load_array_params(2)
		return Frame:callParserFunction(
			"DEFAULTSORT",
			self.params
		)
	end,
	
	["DISPLAYTITLE"] = function(self)
		self:load_array_params(2)
		return Frame:callParserFunction(
			"DISPLAYTITLE",
			self.params
		)
	end,
	
	["FILEPATH"] = function(self)
		self:load_array_params(3)
		return Frame:callParserFunction(
			"FILEPATH",
			self.params
		)
	end,
	
	["FORMATNUM"] = function(self)
		self:load_array_params(2)
		return content_lang:formatNum(
			self.params[1],
			self.params[2]
		)
	end,
	
	["FULLPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.prefixedText and php_wfEscapeWikiText(title.prefixedText) or ""
	end,
	
	["FULLPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.prefixedText and php_wfEscapeWikiText(mw.uri.encode(title.prefixedText, "WIKI")) or ""
	end,
	
	["FULLURL"] = function(self)
		self:load_array_params(2)
		return tostring(mw.uri.fullUrl(
			self.params[1],
			self.params[2]
		))
	end,
	
	["FULLURLE"] = function(self)
		self:load_array_params(2)
		return mw.uri.encode(tostring(mw.uri.fullUrl(
			self.params[1],
			self.params[2]
		)), "WIKI")
	end,
	
	["GENDER"] = function(self)
		self:load_array_params(4, 1)
		local t = Frame:callParserFunction(
			"GENDER",
			self.params[1],
			"2", "3", "4"
		)
		local n = (
			t == "3" and self.params[3] and 3 or
			t == "4" and self.params[4] and 4 or
			2
		)
		self.params[n] = self.params[n] and self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["GRAMMAR"] = function(self)
		self:load_array_params(2)
		return content_lang:grammar(
			self.params[1],
			self.params[2]
		)
	end,
	
	["INT"] = function(self) -- TODO
	end,
	
	["LC"] = function(self)
		self:load_array_params(1)
		return content_lang:lc(self.params[1])
	end,
	
	["LCFIRST"] = function(self)
		self:load_array_params(1)
		return content_lang:lcfirst(self.params[1])
	end,
	
	["LOCALURL"] = function(self)
		self:load_array_params(2)
		return tostring(mw.uri.localUrl(
			self.params[1],
			self.params[2]
		))
	end,
	
	["LOCALURLE"] = function(self)
		self:load_array_params(2)
		return mw.uri.encode(tostring(mw.uri.localUrl(
			self.params[1],
			self.params[2]
		)), "WIKI")
	end,
	
	["NAMESPACE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.nsText and php_wfEscapeWikiText(title.nsText) or ""
	end,
	
	["NAMESPACEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.nsText and php_wfEscapeWikiText(mw.uri.encode(title.nsText, "WIKI")) or ""
	end,
	
	["NAMESPACENUMBER"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.namespace and tostring(title.namespace) or ""
	end,
	
	["NOEXTERNALLANGLINKS"] = function(self) -- TODO
	end,
	
	["NS"] = function(self)
		self:load_array_params(1)
		local ns = tonumber(self.params[1])
		return mw.site.namespaces[ns] and mw.site.namespaces[ns].name or ""
	end,
	
	["NSE"] = function(self)
		self:load_array_params(1)
		local ns = tonumber(self.params[1])
		return mw.site.namespaces[ns] and mw.uri.encode(mw.site.namespaces[ns].name, "WIKI") or ""
	end,
	
	["NUMBERINGROUP"] = function(self)
		self:load_array_params(2)
		local num = mw.site.stats.usersInGroup(self.params[1])
		return self.params[2] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFACTIVEUSERS"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.activeUsers
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFADMINS"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.admins
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFARTICLES"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.articles
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFEDITS"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.edits
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFFILES"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.files
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFPAGES"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.pages
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["NUMBEROFUSERS"] = function(self)
		self:load_array_params(1)
		local num = mw.site.stats.users
		return self.params[1] == "R" and num or comma_value(num)
	end,
	
	["PADLEFT"] = function(self)
		self:load_array_params(3)
		return self:pad(true, unpack(self.params))
	end,
	
	["PADRIGHT"] = function(self)
		self:load_array_params(3)
		return self:pad(false, unpack(self.params))
	end,
	
	["PAGEID"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.id and tostring(title.id) or ""
	end,
	
	["PAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.text and php_wfEscapeWikiText(title.text) or ""
	end,
	
	["PAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.text and php_wfEscapeWikiText(mw.uri.encode(title.text, "WIKI")) or ""
	end,
	
	["PAGESINCATEGORY"] = function(self)
		self:load_array_params(3)
		if self.params[2] then
			self.params[2] = self.params[2]:lower()
			if not (
				self.params[2] == "all" or
				self.params[2] == "subcats" or
				self.params[2] == "files" or
				self.params[2] == "pages"
			) then
				self.params[2] = nil
			end
		end
		local num = mw.site.stats.pagesInCategory(self.params[1], self.params[2])
		return self.params[3] == "R" and num or comma_value(num)
	end,
	
	["PAGESIZE"] = function(self) -- TODO
		-- self:load_array_params(2) ?
	end,
	
	["PLURAL"] = function(self)
		if self[2] then
			self.params = self.params or {}
			local params, added, unresolved = self[2], {}
			self.params[1] = params[1][2]
			for i = 2, len_event(params) do
				repeat
					if params[i][3] then
						if not params[i][4] then
							params[i][1] = self:get_child(params[i][1])
							if type(params[i][1]) == "table" then
								unresolved = true
								break
							end
							params[i][4] = true
						end
						if not added[params[i][1]] then
							self.params[params[i][1]] = params[i][2]
							added[params[i][1]] = true
						end
					else
						if params[i][1] == 2 then
							self.params[false] = params[i][2]
						elseif params[i][1] == 3 then
							self.params[true] = params[i][2]
						end
					end
				until true
			end
			if unresolved then
				self:unresolved()
			end
			self[2] = nil
		end
		self.params[1] = self:get_child(self.params[1])
		if type(self.params[1]) == "table" then
			self:unresolved()
		end
		local v = tostring(tonumber_strict(self.params[1]))
		local n = (
			self.params[v] and v or
			self[true] and v ~= "1" and v ~= "-1" and true or
			false
		)
		self.params[n] = self:get_child(self.params[n])
		return self.params[n] or ""
	end,
	
	["PROTECTIONEXPIRY"] = function(self)
		self:load_array_params(2)
		return Frame:callParserFunction(
			"PROTECTIONEXPIRY",
			self.params
		)
	end,
	
	["PROTECTIONLEVEL"] = function(self) -- TODO
		self:load_array_params(2)
		return Frame:callParserFunction(
			"PROTECTIONLEVEL",
			self.params
		)
	end,
	
	["REVISIONDAY"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONDAY",
			self.params
		)
	end,
	
	["REVISIONDAY2"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONDAY2",
			self.params
		)
	end,
	
	["REVISIONID"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONID",
			self.params
		)
	end,
	
	["REVISIONMONTH"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONMONTH",
			self.params
		)
	end,
	
	["REVISIONMONTH1"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONMONTH1",
			self.params
		)
	end,
	
	["REVISIONTIMESTAMP"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONTIMESTAMP",
			self.params
		)
	end,
	
	["REVISIONUSER"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONUSER",
			self.params
		)
	end,
	
	["REVISIONYEAR"] = function(self)
		self:load_array_params(1)
		return Frame:callParserFunction(
			"REVISIONYEAR",
			self.params
		)
	end,
	
	["ROOTPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.rootText and php_wfEscapeWikiText(title.rootText) or ""
	end,
	
	["ROOTPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.rootText and php_wfEscapeWikiText(mw.uri.encode(title.rootText, "WIKI")) or ""
	end,
	
	["SUBJECTPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subjectPageTitle and title.subjectPageTitle.fullText and php_wfEscapeWikiText(title.subjectPageTitle.fullText) or ""
	end,
	
	["SUBJECTPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subjectPageTitle and title.subjectPageTitle.fullText and php_wfEscapeWikiText(mw.uri.encode(title.subjectPageTitle.fullText, "WIKI")) or ""
	end,
	
	["SUBJECTSPACE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subjectNsText and php_wfEscapeWikiText(title.subjectNsText) or ""
	end,
	
	["SUBJECTSPACEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subjectNsText and php_wfEscapeWikiText(mw.uri.encode(title.subjectNsText, "WIKI")) or ""
	end,
	
	["SUBPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subpageText and php_wfEscapeWikiText(title.subpageText) or ""
	end,
	
	["SUBPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.subpageText and php_wfEscapeWikiText(mw.uri.encode(title.subpageText, "WIKI")) or ""
	end,
	
	["TALKPAGENAME"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.talkPageTitle and title.talkPageTitle.fullText and php_wfEscapeWikiText(title.talkPageTitle.fullText) or ""
	end,
	
	["TALKPAGENAMEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.talkPageTitle and title.talkPageTitle.fullText and php_wfEscapeWikiText(mw.uri.encode(title.talkPageTitle.fullText, "WIKI")) or ""
	end,
	
	["TALKSPACE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.namespace and mw.site.namespaces[title.namespace] and mw.site.namespaces[title.namespace].talk and mw.site.namespaces[title.namespace].talk.canonicalName or ""
	end,
	
	["TALKSPACEE"] = function(self)
		self:load_array_params(1)
		local title = mw.title.new(self.params[1])
		return title and title.namespace and mw.site.namespaces[title.namespace] and mw.site.namespaces[title.namespace].talk and mw.site.namespaces[title.namespace].talk.canonicalName and mw.uri.encode(mw.site.namespaces[title.namespace].talk.canonicalName, "WIKI") or ""
	end,
	
	["UC"] = function(self)
		self:load_array_params(1)
		return content_lang:uc(self.params[1])
	end,
	
	["UCFIRST"] = function(self)
		self:load_array_params(1)
		return content_lang:ucfirst(self.params[1])
	end,
	
	["URLENCODE"] = function(self)
		self:load_array_params(2)
		return mw.uri.encode(
			self.params[1],
			self.params[2]
		)
	end
}

for k, v in pairs{
	["#DATEFORMAT"] = "#FORMATDATE",
	["#SECTION"] = "#LST",
	["#SECTION-H"] = "#LSTH",
	["#SECTION-X"] = "#LSTX",
	["DEFAULTCATEGORYSORT"] = "DEFAULTSORT",
	["DEFAULTSORTKEY"] = "DEFAULTSORT",
	["NUMINGROUP"] = "NUMBERINGROUP",
	["PAGESINCAT"] = "PAGESINCATEGORY",
	["ARTICLEPAGENAME"] = "SUBJECTPAGENAME",
	["ARTICLEPAGENAMEE"] = "SUBJECTPAGENAMEE",
	["ARTICLESPACE"] = "SUBJECTSPACE",
	["ARTICLESPACEE"] = "SUBJECTSPACEE"
} do
	Template.parser_functions[k] = Template.parser_functions[v]
end

setmetatable(Template.parser_functions, case_insensitive)

Template.parser_variables = {
	["!"] = "|",
	["="] = "="
}

local parser_variables = {
	["ARTICLEPAGENAME"] = "SUBJECTPAGENAME",
	
	["ARTICLEPAGENAMEE"] = "SUBJECTPAGENAMEE",
	
	["ARTICLEPATH"] = function()
		return mw.title.new("$1"):localUrl()
	end,
	
	["ARTICLESPACE"] = "SUBJECTSPACE",
	
	["ARTICLESPACEE"] = "SUBJECTSPACEE",
	
	["BASEPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.baseText)
	end,
	
	["BASEPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.baseText, "WIKI"))
	end,
	
	["CASCADINGSOURCES"] = function()
		return table.concat(current_title.cascadingProtection.sources, "|")
	end,
	
	["CONTENTLANG"] = "CONTENTLANGUAGE",
	
	["CONTENTLANGUAGE"] = function()
		return content_lang:getCode()
	end,
	
	["CURRENTDAY"] = function()
		return ("%d"):format(os.date("!%d"))
	end,
	
	["CURRENTDAY2"] = function()
		return os.date("!%d")
	end,
	
	["CURRENTDAYNAME"] = function()
		return os.date("!%A")
	end,
	
	["CURRENTDOW"] = function()
		return os.date("!%w")
	end,
	
	["CURRENTHOUR"] = function()
		return os.date("!%H")
	end,
	
	["CURRENTMONTH"] = function()
		return os.date("!%m")
	end,
	
	["CURRENTMONTH1"] = function()
		return ("%d"):format(os.date("!%m"))
	end,
	
	["CURRENTMONTH2"] = "CURRENTMONTH",
	
	["CURRENTMONTHABBREV"] = function()
		return os.date("!%b")
	end,
	
	["CURRENTMONTHNAME"] = function()
		return os.date("!%B")
	end,
	
	["CURRENTMONTHNAMEGEN"] = "CURRENTMONTHNAME",
	
	["CURRENTTIME"] = function()
		return os.date("!%R")
	end,
	
	["CURRENTTIMESTAMP"] = function()
		return os.date("!%Y%m%d%H%M%S")
	end,
	
	["CURRENTVERSION"] = function()
		return mw.site.currentVersion
	end,
	
	["CURRENTWEEK"] = function()
		return ("%02d"):format(
			(os.date("!%U%w"):gsub("(..)(.)", function(m1, m2)
				return m2 == "0" and (m1 - 1) or m1
			end) - 1) % 52 + 1
		)
	end,
	
	["CURRENTYEAR"] = function()
		return os.date("!%Y")
	end,
	
	["DIRECTIONMARK"] = function()
		return content_lang:getDirMark()
	end,
	
	["DIRMARK"] = "DIRECTIONMARK",
	
	["FULLPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.prefixedText)
	end,
	
	["FULLPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.prefixedText, "WIKI"))
	end,
	
	["LOCALDAY"] = function()
		return ("%d"):format(os.date("%d"))
	end,
	
	["LOCALDAY2"] = function()
		return os.date("%d")
	end,
	
	["LOCALDAYNAME"] = function()
		return os.date("%A")
	end,
	
	["LOCALDOW"] = function()
		return os.date("%w")
	end,
	
	["LOCALHOUR"] = function()
		return os.date("%H")
	end,
	
	["LOCALMONTH"] = function()
		return os.date("%m")
	end,
	
	["LOCALMONTH1"] = function()
		return ("%d"):format(os.date("%m"))
	end,
	
	["LOCALMONTH2"] = "LOCALMONTH",
	
	["LOCALMONTHABBREV"] = function()
		return os.date("%b")
	end,
	
	["LOCALMONTHNAME"] = function()
		return os.date("%B")
	end,
	
	["LOCALMONTHNAMEGEN"] = "LOCALMONTHNAME",
	
	["LOCALTIME"] = function()
		return os.date("%R")
	end,
	
	["LOCALTIMESTAMP"] = function()
		return os.date("%Y%m%d%H%M%S")
	end,
	
	["LOCALWEEK"] = function()
		return ("%02d"):format(
			(os.date("%U%w"):gsub("(..)(.)", function(m1, m2)
				return m2 == "0" and (m1 - 1) or m1
			end) - 1) % 52 + 1
		)
	end,
	
	["LOCALYEAR"] = function()
		return os.date("%Y")
	end,
	
	["NAMESPACE"] = function()
		return current_title.nsText
	end,
	
	["NAMESPACEE"] = function()
		return mw.uri.encode(current_title.nsText, "WIKI")
	end,
	
	["NAMESPACENUMBER"] = function()
		return tostring(current_title.namespace)
	end,
	
	["NOEXTERNALLANGLINKS"] = function()
		return Frame:callParserFunction(
			"NOEXTERNALLANGLINKS",
			"*"
		)
	end,
	
	["NUMBEROFACTIVEUSERS"] = function()
		return comma_value(mw.site.stats.activeUsers)
	end,
	
	["NUMBEROFADMINS"] = function()
		return comma_value(mw.site.stats.admins)
	end,
	
	["NUMBEROFARTICLES"] = function()
		return comma_value(mw.site.stats.articles)
	end,
	
	["NUMBEROFEDITS"] = function()
		return comma_value(mw.site.stats.edits)
	end,
	
	["NUMBEROFFILES"] = function()
		return comma_value(mw.site.stats.files)
	end,
	
	["NUMBEROFPAGES"] = function()
		return comma_value(mw.site.stats.pages)
	end,
	
	["NUMBEROFUSERS"] = function()
		return comma_value(mw.site.stats.users)
	end,
	
	["PAGEID"] = function()
		return tostring(current_title.id)
	end,
	
	["PAGELANGUAGE"] = function()
		return Frame:really_preprocess("{{PAGELANGUAGE}}")
	end,
	
	["PAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.text)
	end,
	
	["PAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.text, "WIKI"))
	end,
	
	["REVISIONDAY"] = function()
		return Frame:callParserFunction(
			"REVISIONDAY",
			current_title.fullText
		)
	end,
	
	["REVISIONDAY2"] = function()
		return Frame:callParserFunction(
			"REVISIONDAY2",
			current_title.fullText
		)
	end,
	
	["REVISIONID"] = function()
		return Frame:callParserFunction(
			"REVISIONID",
			current_title.fullText
		)
	end,
	
	["REVISIONMONTH"] = function()
		return Frame:callParserFunction(
			"REVISIONMONTH",
			current_title.fullText
		)
	end,
	
	["REVISIONMONTH1"] = function()
		return Frame:callParserFunction(
			"REVISIONMONTH1",
			current_title.fullText
		)
	end,
	
	["REVISIONSIZE"] = function()
		return Frame:really_preprocess("{{REVISIONSIZE}}")
	end,
	
	["REVISIONTIMESTAMP"] = function()
		return Frame:callParserFunction(
			"REVISIONTIMESTAMP",
			current_title.fullText
		)
	end,
	
	["REVISIONUSER"] = function()
		return Frame:callParserFunction(
			"REVISIONUSER",
			current_title.fullText
		)
	end,
	
	["REVISIONYEAR"] = function()
		return Frame:callParserFunction(
			"REVISIONYEAR",
			current_title.fullText
		)
	end,
	
	["ROOTPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.rootText)
	end,
	
	["ROOTPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.rootText, "WIKI"))
	end,
	
	["SCRIPTPATH"] = function()
		return mw.site.scriptPath
	end,
	
	["SERVER"] = function()
		return mw.site.server
	end,
	
	["SERVERNAME"] = function()
		return Frame:really_preprocess("{{SERVERNAME}}")
	end,
	
	["SITENAME"] = function()
		return mw.site.siteName
	end,
	
	["STYLEPATH"] = function()
		return mw.site.stylePath
	end,
	
	["SUBJECTPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.subjectPageTitle.fullText)
	end,
	
	["SUBJECTPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.subjectPageTitle.fullText, "WIKI"))
	end,
	
	["SUBJECTSPACE"] = function()
		return current_title.subjectNsText
	end,
	
	["SUBJECTSPACEE"] = function()
		return mw.uri.encode(current_title.subjectNsText, "WIKI")
	end,
	
	["SUBPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.subpageText)
	end,
	
	["SUBPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.subpageText, "WIKI"))
	end,
	
	["TALKPAGENAME"] = function()
		return php_wfEscapeWikiText(current_title.talkPageTitle.fullText)
	end,
	
	["TALKPAGENAMEE"] = function()
		return php_wfEscapeWikiText(mw.uri.encode(current_title.talkPageTitle.fullText, "WIKI"))
	end,
	
	["TALKSPACE"] = function()
		return mw.site.namespaces[current_title.namespace].talk.canonicalName
	end,
	
	["TALKSPACEE"] = function()
		return mw.uri.encode(mw.site.namespaces[current_title.namespace].talk.canonicalName, "WIKI")
	end
}

parser_variables.__index = function(t, k)
	local k_upper = k:upper()
	if type(k) == "string" and case_insensitive[k_upper] then
		k = k_upper
	end
	if type(parser_variables[k]) == "string" then
		k = parser_variables[k]
	end
	if parser_variables[k] then
		t[k] = parser_variables[k]()
		parser_variables[k] = nil
	end
	return rawget(t, k)
end

setmetatable(Template.parser_variables, parser_variables)

Template.transclusion_modifiers = {
	["MSG"] = function(self)
		if self.modifiers_context < 2 then
			-- ...
			self.modifiers_context = 2
		end
		error(errors.DisallowedModifier)
	end,
	
	["MSGNW"] = function(self)
		if self.modifiers_context < 2 then
			-- ...
			self.modifiers_context = 2
		end
		error(errors.DisallowedModifier)
	end,
	
	["RAW"] = function(self)
		if self.modifiers_context < 3 then
			-- ...
			self.modifiers_context = 3
		end
		error(errors.DisallowedModifier)
	end,
	
	["SAFESUBST"] = function(self)
		if self.modifiers_context < 1 then
			self.modifiers_context = 1
			return
		end
		error(errors.DisallowedModifier)
	end,
	
	["SUBST"] = function(self)
		if self.modifiers_context < 1 then
			self:fail()
		end
		error(errors.DisallowedModifier)
	end
}

setmetatable(Template.transclusion_modifiers, case_insensitive)

function Template:remove_param(pos, abs)
	local params, param = self[2]
	if type(pos) ~= "number" then
		for i, p in ipairs(params) do
			if p[1] == pos then
				return table.remove(params, i)
			end
		end
	elseif abs then
		param = table.remove(self[2], pos)
		if param and not param[3] then
			for i = pos, len_event(params) do
				if not params[i][3] then
					params[i][1] = params[i][1] - 1
				end
			end
		end
		return param
	end
	local removed, show_key
	for i, p in ipairs(params) do
		if removed and not (show_key or p[3]) then
			p[1] = p[1] - 1
		elseif p[1] == pos then
			param = table.remove(params, i)
			removed, show_key = true, param[3]
		end
	end
	return param
end

function Template:load_table_params()
	if not self[2] then
		return
	end
	self.params = self.params or {}
	local params, unresolved = self[2]
	for i, param in ipairs(params) do
		repeat
			if not param[4] then
				if param[3] then
					param[1] = self:get_child(param[1])
				end
				param[2] = self:get_child(param[2])
				if (
					type(param[1]) == "table" or
					type(param[2]) == "table"
				) then
					unresolved = true
					break
				end
				param[4] = true
			end
			self.params[param[1]] = param[2]
		until true
	end
	if unresolved then
		self:unresolved()
	end
	self[2] = nil
end

function Template:load_array_params(max, eval)
	if not self[2] then
		return
	end
	self.params = self.params or {}
	local params, unresolved = self[2]
	for i, param in ipairs(params) do
		repeat
			if not (
				param[4] or
				(max and i > max)
			) then
				if param[3] then
					param = {i, Wikitext:new({param[1], "=", param[2]}, cached_nodes[self] and "Wikitext")}
				end
				if not (eval and i > eval) then
					param[2] = self:get_child(param[2])
					if type(param[2]) == "table" then
						unresolved = true
						break
					end
				end
				param[4] = true
			end
			self.params[i] = param[2]
		until true
	end
	if unresolved then
		self:unresolved()
	end
	self[2] = nil
end

function Template:resolve()
	self[1] = self:get_child(self[1])
	if type(self[1]) == "table" then
		self:unresolved()
	end
	if template_calls[self[1]] then
		return template_calls[self[1]](self)
	end
	self.modifiers_context = 0
	local name = text_split(self[1], ":")
	for i, snippet in ipairs(name) do
		repeat
			if pcall(self.transclusion_modifiers[snippet], self) then
				break
			elseif (
				i < #name and
				self.parser_functions[snippet]
			) then
				if not template_calls[snippet] then
					template_calls[snippet] = function(self, param_1)
						if self[2] then
							for i, p in ipairs(self[2]) do
								self[2][i] = p
							end
							if not (self[2][1] and self[2][1][0]) then
								for i, param in ipairs(self[2]) do
									if not param[3] then
										param[1] = param[1] + 1
									end
								end
								param_1 = param_1 or self[1]:match(snippet .. ":(.*)")
								param_1 = {[0] = true, 1, Wikitext:new(param_1, cached_nodes[self] and "Wikitext")}
								table.insert(self[2], 1, param_1)
							end
						end
						self[1] = snippet
						return self.parser_functions[self[1]](self)
					end
				end
				local param_1 = table.concat(name, ":", i + 1)
				template_calls[self[1]] = template_calls[snippet]
				return template_calls[snippet](self, param_1)
			elseif(
				i == #name and
				len_event(self[2]) == 0 and
				self.parser_variables[snippet]
			) then
				if not template_calls[snippet] then
					template_calls[snippet] = function(self)
						self[1] = snippet
						return self.parser_variables[self[1]]
					end
				end
				template_calls[self[1]] = template_calls[snippet]
				return template_calls[snippet](self)
			else
				name = table.concat(name, ":", i)
				if not template_calls[name] then
					template_calls[name] = function(self)
						self[1] = name
						self:load_table_params()
						if template_trees[name] == nil then
							local title = mw.title.new(name, 10)
							title = title.redirectTarget or title
							local canonical_name = ":" .. title.fullText
							if template_trees[canonical_name] == nil then
								local content = title:getContent()
								if content then
									template_trees[canonical_name] = Parser:parse(content, true, title)
								else
									template_trees[canonical_name] = false
								end
								titles[canonical_name] = titles[canonical_name] or title.fullText
							end
							template_trees[name] = template_trees[canonical_name]
							titles[name] = titles[canonical_name]
						end
						local template = self:get_instance(template_trees[name], titles[name], self.params)
						return self:get_child(template, true)
					end
				end
				template_calls[self[1]] = template_calls[name]
				return template_calls[name](self)
			end
		until true
	end
end

------------------------------------------------------------------------------------
--
-- Builder
--
------------------------------------------------------------------------------------

local Builder = {
	nodes = {
		Argument = Argument,
		Template = Template,
		Wikitext = Wikitext
	},
	stack = {}
}

setmetatable(errors.MissedCloseToken , {
	__call = function(t, handler, title)
		errors.MissedCloseToken.handler = handler
		errors.MissedCloseToken.title = title
		error(errors.MissedCloseToken)
	end
})

function Builder:push(n)
	table.insert(self.stack, {})
	if n and n > 1 then
		self:push(n - 1)
	end
end

function Builder:pop(node)
	local stack = table.remove(self.stack)
	if node ~= false then
		while type(stack) == "table" do
			if node then
				stack = self.nodes[node]:new(stack, self.transcluded and node)
				break
			elseif getmetatable(stack) then
				break
			elseif #stack == 1 then
				stack = stack[1]
			else
				local ok, ret = pcall(table.concat, stack)
				stack = ok and ret or stack
				if not ok then
					stack = Wikitext:new(stack, self.transcluded and "Wikitext")
					break
				end
			end
		end
	end
	return stack
end

function Builder:read()
	return self.stack[#self.stack]
end

function Builder:write(...)
	table.insert(self.stack[#self.stack], ...)
end

function Builder:handle_other_token(token)
	self:write(self:handle_token(token))
end

function Builder:handle_template_name()
	self:push(2)
	while #self.tokens > 0 do
		local token = table.remove(self.tokens)
		if (
			token == tokens.TemplateParamSeparator or
			token == tokens.TemplateClose
		) then
			table.insert(self.tokens, token)
			return self:write(self:pop())
		else
			self:handle_other_token(token)
		end
	end
	errors.MissedCloseToken("handle_template_name", self.title)
end

function Builder:handle_parameter(default)
	self:push(2)
	while #self.tokens > 0 do
		local token = table.remove(self.tokens)
		if token == tokens.TemplateParamEquals then
			self:write(self:pop())
			self:push()
		elseif (
			token == tokens.TemplateParamSeparator or
			token == tokens.TemplateClose
		) then
			table.insert(self.tokens, token)
			self:write(self:pop())
			if #self:read() == 1 then
				self:write(1, tostring(default))
				default = default + 1
			else
				self:write(true)
			end
			self:write(self:pop(false))
			return default
		else
			self:handle_other_token(token)
		end
	end
	errors.MissedCloseToken("handle_parameter", self.title)
end

function Builder:handle_template()
	local default = 1
	self:handle_template_name()
	self:push()
	while #self.tokens > 0 do
		local token = table.remove(self.tokens)
		if token == tokens.TemplateParamSeparator then
			default = self:handle_parameter(default)
		elseif token == tokens.TemplateClose then
			self:write(self:pop(false))
			return self:pop("Template")
		else
			self:handle_other_token(token)
		end
	end
	errors.MissedCloseToken("handle_template", self.title)
end

function Builder:handle_argument()
	self:push(2)
	while #self.tokens > 0 do
		local token = table.remove(self.tokens)
		if token == tokens.ArgumentSeparator then
			self:write(self:pop())
			self:push()
		elseif token == tokens.ArgumentClose then
			self:write(self:pop())
			return self:pop("Argument")
		else
			self:handle_other_token(token)
		end
	end
	errors.MissedCloseToken("handle_argument", self.title)
end

Builder.handlers = {
	[tokens.TemplateOpen] = Builder.handle_template,
	[tokens.ArgumentOpen] = Builder.handle_argument
}

function Builder:handle_token(token)
	return select(2, xpcall(
		function()
			if not tokens[token] then
				return token
			end
			if not self.handlers[token] then
				error("Builder:handle_token() got unexpected " .. tostring(token) .. ".")
			else
				return self.handlers[token](self)
			end
		end,
		function(err)
			if err == errors.MissedCloseToken then
				error(debug.traceback("Builder:" .. errors.MissedCloseToken.handler .. "() missed a close token building " .. errors.MissedCloseToken.title.fullText .. "."))
			else
				error("Error building " .. self.title.fullText .. ": " .. debug.traceback(err), 2)
			end
		end
	))
end

function Builder:build(tokenlist, transcluded, title)
	self.tokens = reverse_table(tokenlist)
	self.title = title or Parser.title or current_title
	self.transcluded = transcluded
	self:push()
	while #self.tokens > 0 do
		local node = self:handle_token(
			table.remove(self.tokens)
		)
		self:write(node)
	end
	return self:pop()
end

------------------------------------------------------------------------------------
--
-- Parser
--
------------------------------------------------------------------------------------

function Parser.sort_tags(a, b)
	return a[1] > b[1]
end

function Parser:split_by_tags(text)
	local ret = {}
	local next_tags = {}
	local start = 1
	for _, tag in ipairs(tag_captures) do
		local m = {text:match("()" .. tag .. "()", start)}
		if #m > 0 then
			table.insert(m, tag)
			table.insert(next_tags, m)
		end
	end
	table.sort(next_tags, self.sort_tags)
	while #next_tags > 0 do
		local next_tag = table.remove(next_tags)
		local inter = text:sub(start, next_tag[1] - 1)
		if inter ~= "" then
			table.insert(ret, inter)
		end
		table.insert(ret, next_tag[2])
		local new_start = next_tag[3]
		local new_tags = {next_tag[4]}
		for i, tag in ipairs(next_tags) do
			if tag[1] < new_start then
				table.remove(next_tags, i)
				table.insert(new_tags, tag[4])
			end
		end
		start = new_start
		for _, tag in ipairs(new_tags) do
			local m = {text:match("()" .. tag .. "()", start)}
			if #m > 0 then
				table.insert(m, tag)
				table.insert(next_tags, m)
			end
		end
		table.sort(next_tags, self.sort_tags)
	end
	local inter = text:sub(start)
	if inter ~= "" then
		table.insert(ret, text:sub(start))
	end
	return ret
end

function Parser:handle_tags(text, transcluded)
	text = self:split_by_tags(text)
	if transcluded then
		local new_text, include = {}
		local open, close
		for _, this in ipairs(text) do
			if (
				not include and
				this == "<onlyinclude>"
			) then
				open = true
				include = true
			elseif include then
				if this == "</onlyinclude>" then
					close = true
					include = false
				else
					table.insert(new_text, this)
				end
			end
		end
		if open and close and #new_text > 0 then
			text = new_text
		end
	end
	local new_text = {}
	local current, current_tag = {}
	local include = true
	for _, this in ipairs(text) do
		if include and this == "<!--" then
			current_tag = this
			include = false
		elseif this == "-->" and current_tag == "<!--" then
			current_tag = nil
			include = true
		else
			local tag = (
				this:match("^<(.-)%s.->$") or
				this:match("^<(.-)>$")
			)
			tag = tag and tag:lower()
			if not current_tag then
				if include and tags[tag] then
					current_tag = tag
					table.insert(current, this)
				elseif tag == "includeonly" then
					if not transcluded then
						include = false
					end
				elseif tag == "noinclude" then
					if transcluded then
						include = false
					end
				elseif (
					tag == "onlyinclude" or
					tag == "/onlyinclude"
				) then
					if transcluded then
						table.insert(new_text, this)
					end
				elseif tag == "/includeonly" then
					if not transcluded then
						if not include then
							include = true
						else
							table.insert(new_text, this)
						end
					end
				elseif tag == "/noinclude" then
					if transcluded then
						if not include then
							include = true
						else
							table.insert(new_text, this)
						end
					end
				elseif include then
					table.insert(new_text, this)
				end
			elseif tag and include and tag:sub(2) == current_tag then
				table.insert(current, this)
				table.insert(
					new_text,
					Frame:really_preprocess(table.concat(current))
				)
				current, current_tag = {}
			elseif include then
				table.insert(current, this)
			end
		end
	end
	if #current > 0 then
		table.insert(
			new_text,
			table.concat(current)
		)
	end
	return table.concat(new_text)
end

function Parser:parse(text, transcluded, title)
	self.title = current_title
	text = self:handle_tags(text, transcluded)
	text = Tokenizer:tokenize(text, transcluded, title)
	text = Builder:build(text, transcluded, title)
	return Wikitext:get_child(text, true)
end

return setmetatable({}, Parser)