local CASE_INSENSITIVE_NOWIKI = '[Nn][Oo][Ww][Ii][Kk][Ii]'
local DEADZONE_TAGS = {
	'[Pp][Rr][Ee]',
	CASE_INSENSITIVE_NOWIKI,
	'[Ss][Oo][Uu][Rr][Cc][Ee]',
	'[Ss][Yy][Nn][Tt][Aa][Xx][Hh][Ii][Gg][Hh][Ll][Ii][Gg][Hh][Tt]'
}

local function _isEmpty(value) return value == nil or value == '' end

local function _notEmpty(value) return not _isEmpty(value) end

-- Unescape functionality grabbed from https://stackoverflow.com/a/14899740/1832568
local function _unescape(str)
	str = mw.ustring.gsub(str, '&#(%d+);', string.char)
	str = mw.ustring.gsub(str, '&#x(%d+);', function(d) return string.char(tonumber(d, 16)) end)

	return str
end

local function _hashDelimitedListIterator(list_string)
	return mw.text.gsplit(_unescape(list_string), '%s-#%s-')
end

local function _alarmingMessage(message)
	return '<span class="error">[[Module:Find templates in use]] '..message..'.</span>'
	-- TODO ..'[[Category:Pages displaying alarming messages about Module:Find templates in use]]'
end

-- "template name" --> "[Tt]emplate[ _]+name"
local function _patternizeTemplateName(template_name)
	local first_char = mw.ustring.sub(template_name, 1, 1)

	return '['..mw.ustring.upper(first_char)..mw.ustring.lower(first_char)..
		']'..mw.ustring.gsub(mw.ustring.sub(template_name, 2), '[ _]+', '[ _]+')
end

local function _onlyActiveContent(page_content)
	page_content = mw.ustring.gsub(page_content, '<!%-%-.-%-%->', '')

	for _, dz_tag in pairs(DEADZONE_TAGS) do
		page_content = mw.ustring.gsub(page_content, '<'..dz_tag..'[^>]-%b></%s-'..dz_tag..'>', '')
	end

	return page_content
end

local function _notDeadzoneTag(template)
	template = mw.ustring.lower(template)

	for _, dz_tag in pairs(DEADZONE_TAGS) do
		if mw.ustring.match(template, '^{{%s-#tag:%s-'..dz_tag..'%s-|') then
			return false
		end
	end

	return true
end

local function _getAllDoubleBracedBlocks(content, include_inactive, include_nestled, all_DBB)
	all_DBB = all_DBB or {}

	for template in content:gmatch('{%b{}}') do
		if include_inactive or _notDeadzoneTag(template) then
			table.insert(all_DBB, template)
			if include_nestled then
				content = mw.ustring.match(template, '^{{%s-[^|]+%s-|%s-(.-)%s-}}$')
				if _notEmpty(content) then
					_getAllDoubleBracedBlocks(content, include_inactive, include_nestled, all_DBB)
				end
			end
		end
	end

	return all_DBB
end

local function _getParams(DBB_params)
	local params = {}

	if DBB_params then
		local current = {}
		local nested = 0
		local cha, chacha

		for i = 1, #DBB_params do
			cha = mw.ustring.sub(DBB_params, i, i)
			chacha = mw.ustring.sub(DBB_params, i, i+1)

			if chacha == "{{" or chacha == "[[" then
				nested = nested + 1
			elseif (chacha == "}}" or chacha == "]]") and nested > 0 then
				nested = nested - 1
			end

			if cha == "|" and nested == 0 then
				table.insert(params, table.concat(current))
				current = {}
			else
				table.insert(current, cha)
			end
		end

		if #current > 0 then
			table.insert(params, table.concat(current))
		end
	end

	return params
end

local function _getTemplates(page_content, template_names, include_inactive, include_nestled, get_params, all_in_use)
	local templates = {}
	local template_name_patterns = {}
	local template_name_pattern,
				all_DBB,
				params

	for template_name in _hashDelimitedListIterator(template_names) do
		template_name_pattern = _patternizeTemplateName(template_name)

		-- Filter out duplicate template_names
		if not template_name_patterns[template_name_pattern] then
			template_name_patterns[template_name_pattern] = true

			-- Get all double braced blocks only once, and only if necessary
			all_DBB = all_DBB or _getAllDoubleBracedBlocks(page_content, include_inactive, include_nestled)

			for _, DBB in pairs(all_DBB) do
				local DBB_name, DBB_params = mw.ustring.match(DBB, '^{{%s-([^|]+)%s-|%s-(.-)%s-}}$')
				if not DBB_name then
					DBB_name = mw.ustring.match(DBB, '^{{%s-(.-)%s-}}$')
				end

				if include_inactive then
					DBB_name = mw.ustring.gsub(
						mw.ustring.gsub(DBB_name, '<'..CASE_INSENSITIVE_NOWIKI..'%s-/>', ''),
						'</%s-'..CASE_INSENSITIVE_NOWIKI..'>', ''
					)
				end

				if mw.ustring.match(DBB_name, '^'..template_name_pattern..'$') then
					if get_params then
						params = _getParams(DBB_params)
						if all_in_use then
							if not templates[template_name] then
								templates[template_name] = {}
							end
							table.insert(templates[template_name], params)
						else
							templates[template_name] = params
							break
						end
					else
						if all_in_use then
							templates[template_name] = (templates[template_name] or 0) + 1
						else
							-- Allows for a more efficient return if the use count isn't needed,
							-- while also making it possible to query the table i.e. table[key].
							templates[template_name] = true
							break
						end
					end
				end
			end
		end
	end

	return templates
end

local function _main(args)
	local template_names = args.templates
	if _isEmpty(template_names) then
		return _alarmingMessage('requires a |templates= value')
	end

	local page_name = args.page
	if _isEmpty(page_name) then
		return _alarmingMessage('requires a |page= value')
	end

	local title_table = mw.title.new(page_name)
	if _isEmpty(title_table) then
		return _alarmingMessage('could not get title_table for '..page_name)
	end

	local page_content = title_table:getContent()
	if _isEmpty(page_content) then
		return _alarmingMessage('found no content at '..page_name)
	end

	local _yesno = require('Module:Yesno')

	local include_inactive = _yesno(args.inactive)
	if not include_inactive then
		page_content = _onlyActiveContent(page_content)
		if _isEmpty(page_content) then
			return _alarmingMessage('found no active content at '..page_name)
		end
	end

	local include_nestled = _yesno(args.nestled)

	local get_params = _yesno(args.params)

	local all_in_use = _yesno(args.all)

	return _getTemplates(page_content, template_names, include_inactive, include_nestled, get_params, all_in_use)
end

local p = {}

function p.main(frame)
	local args = require('Module:Arguments').getArgs(frame)
	if _isEmpty(args) then
		return _alarmingMessage('could not getArgs') -- This really would be alarming.
	end

	return _main(args)
end

return p