Module:etymon

local export = {}

local m_links = require("Module:links")
local m_utilities = require("Module:utilities")
local page_data = mw.loadData("Module:headword/data").page

local check_ancestor = require("Module:etymology").check_ancestor
local concat = table.concat
local find = string.find
local findTemplates = require("Module:template parser").findTemplates
local format_categories = m_utilities.format_categories
local get_section = m_utilities.get_section
local full_link = m_links.full_link
local get_lang = require("Module:languages").getByCode
local get_link_page = m_links.get_link_page
local insert = table.insert
local ipairs = ipairs
local max = math.max
local new_title = mw.title.new
local process_params = require("Module:parameters").process
local split = require("Module:string utilities").split
local sub = string.sub
local type = type
local unpack = unpack

-- Normalize the language so that special handling of Chinese is accounted for.
-- This is everything in the Sinitic family which isn't a creole or pidgin.
local function getNormLang(lang)
	if lang:inFamily("zhx") and not lang:inFamily("crp") then
		return get_lang("zh")
	else 
		return lang
	end
end

-- Given an etymon param, return its parts.
local function getParts(templateLang, etymonParam)
	local etymonLang, etymonLangcode, etymonPage, etymonId
	local parts = split(etymonParam, ">", true, true)
	if #parts == 2 then
		-- Assume language is the same as the template call if none is provided.
		etymonLang, etymonPage, etymonId = templateLang, unpack(parts)
	else
		etymonLangcode, etymonPage, etymonId = unpack(parts)
		etymonLang = get_lang(etymonLangcode, true, true)
	end

	return etymonLang, etymonPage, etymonId
end

local argsOf = {}
local disambiguationCount = {}
local function scrapePage(etymonPage, etymonTitle, key, etymonLangcode, etymonId, redirect)
	local pageContent = etymonTitle:getContent()
	local redirectTarget = etymonTitle.redirectTarget
	local L2_key

	if pageContent == nil then
		argsOf = "redlink"
		return
	end

	-- TODO: it is really necessary to convert the language object to the code and back into the object?
	local langSection = get_section(pageContent, get_lang(etymonLangcode, true, true):getCanonicalName(), 2)

	-- Search the entire entry if it is a redirect.
	if redirectTarget then
		langSection = pageContent
	elseif langSection == nil then
		return "missing"
	end

	-- Search for the template on the page (even if this is a redirect page).
	for name, templateArgs in findTemplates(langSection) do
		if name == "etymon" then
			L2_key = templateArgs .. ">" .. etymonPage
			argsOf] = templateArgs
			if disambiguationCount == nil then
				disambiguationCount = 1
			else
				disambiguationCount = disambiguationCount + 1
			end
		end
	end

	-- If scraping produced a result, there's nothing left to do.
	if argsOf then
		return
	-- Else if we've already followed a redirect and still found nothing, record the template as missing.
	elseif redirect then
		argsOf = "missing"
		return
	end

	-- Check if the page is a redirect, and if not record the template as missing.
	if not redirectTarget then
		argsOf = "missing"
		return
	end

	-- Otherwise, try again with the redirect target.
	etymonPage = redirectTarget.prefixedText
	local newKey = etymonLangcode .. ">" .. etymonPage .. ">" .. etymonId
	scrapePage(etymonPage, redirectTarget, newKey, etymonLangcode, etymonId, true)

	-- Record the value as the same as the redirect's.
	argsOf = argsOf
end

-- Given an etymon, scrape the page and get its parameters.
-- This function returns either: a table of the params, "missing", "redlink", or "nolink"
local function getArgs(templateLang, etymonParam)
	-- Get normalized parts of the etymon parameter.
	local etymonLang, etymonPage, etymonId = getParts(templateLang, etymonParam)
	-- "?" is a special value that unlinks the page.
	if etymonId == "?" then
		return "nolink"
	end
	etymonPage = get_link_page(etymonPage, etymonLang)
	local etymonLangcode = getNormLang(etymonLang):getFullCode()

	-- Find the parameters by scraping etymonPage.
	-- Store data in the argsOf table to save time in case the same etymon is accessed again.
	-- The key is a normalized version of etymonParam.
	local key = etymonLangcode .. ">" .. etymonPage .. ">" .. etymonId
	if argsOf == nil then
		local etymonTitle = new_title(etymonPage)
		if not etymonTitle then
			-- This shouldn't happen: all unsupported titles should be resolved at this stage.
			error("Invalid page title \"" .. etymonPage .. "\" encountered.")
		end
		scrapePage(etymonPage, etymonTitle, key, etymonLangcode, etymonId)
	end

	return argsOf
end

-- : {abbreviation, label glossary anchor, start text, start text plus, middle text, forms groups}
-- Note: the keywords `afeq`, `conf`, and `unc` are also recognized, but do not use this dictionary.
-- Please do not add any new keywords without discussion or this list will get extremely unwieldy.
-- If we decide to add keywords for each thing I will have to figure out a systematic way to organize them.
local keywordDict = {
	 = {false, false, "From", "From", "from", false, false},
	 = {false, false, "From", "] from", "from", false},
	 = {false, false, "From", "From", "from", true},
	 = {"blend.", "blend", "Blend of", "] of", "a blend of", true},
	 = {"bor.", "borrowing", "Borrowed from", "] from", "borrowed from", false},
	 = {"lbor.", "learned_borrowing", "Learned borrowing from", "] from", "borrowed from", false},
	 = {"obor.", "orthographic_borrowing", "Orthographic borrowing from", "] from", "borrowed from", false},
	 = {"slbor.", "semi-learned_borrowing", "Semi-learned borrowing from", "] from", "borrowed from", false},
	 = {"der.", "derived_terms", "Derived from", "] from", "from", false},
	 = {"calq.", "calque", "Calque of", "] of", "a calque of", false},
	 = {"sl.", "semantic loan", "Semantic loan of", "] of", "a semantic loan of", false},
	 = {"influ.", "contamination", "", "", "", false}
}

-- This function takes an etymon and recursively builds a tree to display in an entry.
local function etyTree(currTitle, lang, args, alreadySeen, isTopLevel, isUncertain, label)
	local maxDepth = 0
	local subtree, subtreeDepth, etymonLang, etymonPage, etymonArgs
	local subtrees = {}
	local currId = ""
	if type(args) == "table" then
		currId = args
	end
	local key = getNormLang(lang):getFullCode() .. ">" .. get_link_page(currTitle, lang) .. ">" .. currId
	local derType, confidence, ignoreEtymons = "from", "conf", false
	
	-- Only recurse when an etymon has params and was not included in the tree previously.
	if type(args) == "table" and alreadySeen == nil then
		local templateLang = get_lang(args, true, true)
		-- Add the page to alreadySeen, which keeps track of what's already been added to the tree and the depth reached.
		alreadySeen = true
		-- Loop over each parameter in the current template.
		for i, param in ipairs(args) do
			if i > 1 and find(param, ">") and not ignoreEtymons then
				etymonLang, etymonPage = getParts(templateLang, param)

				-- Scrape the page and get the parameters.
				etymonArgs = getArgs(templateLang, param)

				-- Recurse into the etymon and append its tree to the list of subtrees.
				subtree, subtreeDepth = etyTree(etymonPage, etymonLang, etymonArgs, alreadySeen, false, confidence == "unc", derType)
				insert(subtrees, subtree)
				maxDepth = max(maxDepth, subtreeDepth)
			elseif i > 1 then
				-- Reached a keyword.
				if param == "conf" or param == "unc" then
					confidence = param
				elseif keywordDict ~= nil then
					ignoreEtymons = false
					confidence = "conf"
					derType = param
				else
					ignoreEtymons = true
				end
			end
		end
	end

	-- Create term block.
	local link
	if isTopLevel then
		link = lang:getCanonicalName() .. " " .. full_link({lang=lang, alt="'''" .. currTitle .. "'''"}, "term")
	elseif currId == "" then
		link = lang:getCanonicalName() .. " " .. full_link({lang=lang, term=currTitle}, "term")	
	else
		link = lang:getCanonicalName() .. " " .. full_link({lang=lang, term=currTitle, id=currId}, "term")
	end

	-- Create tree.
	local tree = "<div style=\"position:relative;display:inline;z-index:1;vertical-align:bottom;margin:0 4px 0\"><p style=\"position:relative;margin:8px 0;display:inline-block;padding:5px 10px;background-color:#fffbf2;border:1px solid #ccc;border-radius:4px\">" .. link

	-- Add a short top connector if multiple subtrees exist.
	if #subtrees >= 2 then
		tree = tree .. "<span style=\"position:absolute;z-index:-1;inset:-10px 50% 0 auto;border-right:2px solid #9e9e9e\"></span>"
	end

	tree = tree .. "</p>"

	-- Add derivation and uncertainty labels.
	if (label ~= "" and keywordDict ~= false) or isUncertain then
		tree = tree .. "<span style=\"position:absolute;z-index:2;transform:translate(-50%);top:calc(100% + 9px);left:50%;border-radius:2px;background-color:rgba(234,255,255,0.85);font-size:12px;height:10px;line-height:10px\">"
		if label ~= "" and keywordDict ~= false then
			tree = tree .. " .. "|<abbr title=\"" .. string.gsub(keywordDict, "_", " ") .. "\" style=\"color:black;font-style:italic;text-decoration:none\">" .. keywordDict .. "</abbr>]]"
			if isUncertain then
				-- Add uncertainty label next to the derivation label.
				tree = tree .. "<abbr title=\"uncertain\" style=\"position:absolute;top:50%;transform:translate(0,-48%);left:calc(100% + 2px);font-size:10px;border-radius:2px;background-color:rgba(255,224,240,0.85);padding:1px 2px;font-weight:bold;text-decoration:none\">?</abbr>"
			end
		elseif isUncertain then
			-- Add uncertainty label in the middle.
			tree = tree .. "<abbr title=\"uncertain\" style=\"position:absolute;top:50%;left:50%;transform:translate(calc(-50% - 1px),-48%);font-size:10px;border-radius:2px;background-color:rgba(255,224,240,0.85);padding:1px 2px;font-weight:bold;text-decoration:none\">?</span>"
		end
		tree = tree .. "</span>"
	end

	tree = tree .. "</div>"

	-- Add line break if parents exist.
	if #subtrees >= 1 then
		tree = "<br>" .. tree
	end

	-- Append subtrees. For cleaner HTML, only add text-align:center div when necessary.
	local subtreeString = ""
	if #subtrees == 1 then
		-- Add a long bottom connector to the subtree.
		-- Use sub() to insert it right before the </div>, which is a little hacky.
		subtreeString = sub(subtrees, 1, -7) .. "<span style=\"position:absolute;z-index:-1;inset:0 50% 0 auto;height:50px;border-right:2px solid #9e9e9e\"></span></div>"
	elseif #subtrees >= 2 then
		for i,v in ipairs(subtrees) do
			if i == 1 then
				-- Add left connector.
				v = v .. "<span style=\"position:absolute;inset:calc(100% - 9px) -20px 0 calc(50% - 2px);border-bottom:2px solid #9e9e9e;border-left:2px solid #9e9e9e;border-bottom-left-radius:4px\"></span>"
			elseif i == #subtrees then
				-- Add right connector.
				v = v .. "<span style=\"position:absolute;inset:calc(100% - 9px) 50% 0 -20px;border-bottom:2px solid #9e9e9e;border-right:2px solid #9e9e9e;border-bottom-right-radius:4px\"></span>"
			else
				-- Add a short bottom connector before the </div>.
				v = sub(v, 1, -7) .. "<span style=\"position:absolute;z-index:-1;inset:0 50% -14px auto;border-right:2px solid #9e9e9e\"></span></div>"
				-- Add middle connector.
				v = v .. "<span style=\"position:absolute;inset:calc(100% - 9px) -20px 0;border-bottom:2px solid #9e9e9e\"></span>"
			end
			subtreeString = subtreeString .. "<div style=\"position:relative;display:inline-block\">" .. v .. "</div>"
		end
	end
	tree = subtreeString .. tree

	-- Add outer divs.
	if isTopLevel then
		tree = "<div style=\"font-size:14px;white-space:nowrap;line-height:1.1;display:inline-block;text-align:center;margin-left:0.5em\">" .. tree .. "</div>"
		tree = "<div class=\"NavFrame etytree\"><div class=\"NavHead\" style=\"background:#eee\">Etymology tree</div><div class=\"NavContent\" style=\"overflow:auto;text-align:left\">" .. tree .. "</div></div>"
	end

	return tree, maxDepth + 1
end

-- This function takes an etymon and generates some text to display in an entry.
-- Currently, it is only able to handle simple combinations of parameters.
local function etyText(title, lang, args, usePlusTemplates, maxDepth)
	local text = ""
	local depth = 1
	local alreadyWritten = {}
	local key, currLang, group, groupType, groupConfidence, confidence, derType, foundGroup, complexParams, ignoreEtymons, etymonLang, etymonTitle, etymonId, templateLang

	-- Loop and continuously expand the sentence until we reach the end of the chain.
	while not maxDepth or depth <= maxDepth do
		group, groupType, groupConfidence, confidence, derType, foundGroup, complexParams, ignoreEtymons, currLang = {}, "from", "conf", "conf", "from", false, false, false, lang
		key = getNormLang(lang):getFullCode() .. ">" .. get_link_page(title, lang) .. ">" .. args
		templateLang = get_lang(args, true, true)
		-- Stop if we encounter an already-seen term.
		if alreadyWritten ~= nil then
			break
		end
		alreadyWritten = true
		
		for i, param in ipairs(args) do
			if i > 1 and find(param, ">") and not ignoreEtymons then
				-- The text should only continue if `args` is either (not including `influence` or `afeq` etymons):
				-- A single etymon, or single `af` group. Otherwise the parameters are too "complex" and are rejected.
				-- TODO: add smarter handling for complex parameters.
				if foundGroup or (#group == 1 and not keywordDict) then
					complexParams = true
					break
				end
				groupType = derType
				if confidence == "unc" then
					groupConfidence = "unc"
				end
				insert(group, param)
			elseif i > 1 then
				-- Reached a keyword.
				if param == "unc" then
					confidence = param
				elseif param == "afeq" or param == "influence" then
					ignoreEtymons = true
					if #group == 1 then
						foundGroup = true
					end
				else
					ignoreEtymons = false
					confidence = "conf"
					derType = param
					if #group == 1 then
						foundGroup = true
					end
				end
			end
		end
		if complexParams or #group == 0 then
			break
		end
		if #group == 1 then
			args = getArgs(templateLang, group)
		end
		if text == "" then
			-- Start the sentence.
			if groupConfidence == "conf" and not usePlusTemplates then
				text = keywordDict
			elseif groupConfidence == "conf" and usePlusTemplates then
				text = keywordDict
			else
				text = "Possibly " .. keywordDict
			end
		else
			-- Add a phrase onto the sentence.
			if groupConfidence == "conf" then
				text = text .. ", " .. keywordDict
			else
				text = text .. ", possibly " .. keywordDict
			end
		end
		-- Add the links.
		for i = 1,#group do
			etymonLang, etymonTitle, etymonId = getParts(templateLang, group)
			if etymonLang ~= currLang then
				group = etymonLang:makeWikipediaLink() .. " " .. full_link({lang=etymonLang, term=etymonTitle, id=etymonId}, "term")
				currLang = etymonLang
			else
				group = full_link({lang=etymonLang, term=etymonTitle, id=etymonId}, "term")
			end
		end
		text = text .. " " .. concat(group, " + ")
		depth = depth + 1
		if #group == 2 then
			break
		end
		lang = etymonLang
		title = etymonTitle
		if type(args) ~= "table" then
			break
		end
	end
	-- Add a period at the end of the sentence.
	if text ~= "" then
		text = text .. "."
	end
	return text
end

-- This function take an etymon and recursively generates categories to add to the entry.
-- Currently the behaviour tries to emulate existing templates including {{dercat}}.
-- More specific and useful categories are planned pending consensus (e.g. take confidence into account).
local categories = {}
local alreadySeenByEtyCategories = {}
local function etyCategories(title, lang, args, isTopLevel, passedThroughOtherLanguage, inInhChain)
	local etymonLang, etymonTitle, normTitle, etymonId, etymonLangName, etymonNormLangName, etymonArgs, key, L2_key, etymonPassedThroughOtherLanguage, etymonInInhChain
	local currGroupLength = 0
	local derType = "from"
	local templateLang = get_lang(args, true, true)
	local langName = lang:getFullName()

	for i, param in ipairs(args) do
		if i > 1 and find(param, ">") then
			currGroupLength = currGroupLength + 1
			etymonLang, etymonTitle, etymonId = getParts(templateLang, param)
			normTitle = get_link_page(etymonTitle, etymonLang)
			L2_key = getNormLang(etymonLang):getFullCode() .. ">" .. normTitle
			key = L2_key .. ">" .. etymonId

			etymonLangName = etymonLang:getCanonicalName()
			etymonNormLangName = getNormLang(etymonLang):getFullName()
			etymonInInhChain = inInhChain and (derType == "from" or derType == "inh")
			etymonPassedThroughOtherLanguage = passedThroughOtherLanguage or langName ~= etymonNormLangName
			etymonArgs = getArgs(templateLang, param)

			if isTopLevel then
				if derType == "bor" or derType == "lbor" or derType == "slbor" then
					categories = true
				end
				if derType == "lbor" then
					categories = true
				elseif derType == "calque" then
					categories = true
				elseif derType == "sl" then
					categories = true
				elseif derType == "slbor" then
					categories = true
				elseif derType == "blend" then
					categories = true
				elseif derType == "obor" then
					categories = true
				end
			end

			if not etymonPassedThroughOtherLanguage then
				if (derType == "afeq" or keywordDict) and sub(normTitle, #normTitle) == "-" then
					if type(etymonArgs) == "table" and disambiguationCount > 1 then
						categories = true
					else
						categories = true
					end
				elseif (derType == "afeq" or keywordDict) and currGroupLength > 1 and sub(normTitle, 1, 1) == "-" then
					if type(etymonArgs) == "table" and disambiguationCount > 1 then
						categories = true
					else
						categories = true
					end
				end
				--TODO: figure out what to do about infixes, interfixes, circumfixes, etc.
			elseif etymonPassedThroughOtherLanguage and langName == etymonNormLangName then
				categories = true
			elseif etymonNormLangName ~= langName then
				categories = true
				if etymonInInhChain then
					categories = true
				end
			end

			-- PIE roots and words, excluding suffixes.
			if etymonLangName == "Proto-Indo-European" then
				if sub(normTitle, #normTitle) == "-" then
					if type(etymonArgs) == "table" and disambiguationCount > 1 then
						categories = true
					else
						categories = true
					end
				elseif sub(etymonTitle, 1, 2) ~= "*-" then
					if type(etymonArgs) == "table" and disambiguationCount > 1 then
						categories = true
					else
						categories = true
					end
				end
			end

			if derType ~= "afeq" and derType ~= "influence" and alreadySeenByEtyCategories == nil and type(etymonArgs) == "table" then
				alreadySeenByEtyCategories = true
				etyCategories(title, lang, etymonArgs, false, etymonPassedThroughOtherLanguage, etymonInInhChain)
			end
		elseif i > 1 and param ~= "unc" and param ~= "conf" then
			derType = param
			currGroupLength = 0
		end
	end
	if isTopLevel then
		local output = {}
		local sortkey = lang:makeSortKey(title)
		for category, _ in pairs(categories) do
			insert(output, "]")
		end
		return concat(output)
	end
end

local function paramsSanityCheck(lang, params, id, title)
	if mw.ustring.len(id) < 2 then
		error("The `id` parameter must have at least two characters. See the ] for more details.")
	elseif id == title or id == page_data.pagename then
		error("The `id` parameter must not be the same as the page title. Be more creative. See the ] for more details.")
	end

	local paramLang, paramTitle, paramId
	local currKeyword = "from"
	local singleAfParam = "not in group"
	local output = ""
	for _, param in ipairs(params) do
		if find(param, ">") then
			--In this case, `templateLang` is the same as `lang` because we are at the top level.
			paramLang, paramTitle, paramId = getParts(lang, param)

			-- Check for link errors.
			full_link({lang=lang, term=paramTitle, id=paramId}, "term")

			--Add a maintenance category if an invalid ID is provided.
			if getArgs(lang, param) == "missing" or getArgs(lang, param) == "redlink" then
				if page_data.namespace == "" or page_data.namespace == "Reconstruction" or page_data.namespace == "Appendix" then
					output = "]"
				else
					output = "]"
				end
			end

			if currKeyword == "from" then		
				if paramLang:getFullCode() ~= lang:getFullCode() then
					error("Error: " .. param .. " is associated with `from` (same-language derivation) but is of language `" .. paramLang:getFullCode() .. "`, which does not match the current entry language (`" .. lang:getFullCode() .. "`); see the ] for more details.")
				end
			elseif currKeyword == "inh" then
				check_ancestor(lang, paramLang)
			elseif currKeyword == "afeq" or keywordDict then
				if singleAfParam == "not in group" then
					singleAfParam = param
				else
					singleAfParam = "found group"
				end
			elseif (currKeyword == "bor" or currKeyword == "lbor" or currKeyword == "obor" or currKeyword == "slbor" or currKeyword == "der" or currKeyword == "calque" or currKeyword == "sl") and (paramLang:getCode() == lang:getCode()) then
				error("Error: " .. param .. " is associated with `" .. currKeyword .. "` but has the same language (`" .. paramLang:getCode() .. "`) as the current entry; see the ] for more details.")
			end
		elseif param ~= "unc" and param ~= "conf" and param ~= "afeq" and keywordDict == nil then
			error("Received unknown keyword: " .. param)
		elseif param ~= "unc" and param ~= "conf" then
			currKeyword = param
			if singleAfParam == "found group" then
				singleAfParam = "not in group"
			end
		end
	end
	if singleAfParam ~= "not in group" and singleAfParam ~= "found group" then
		error("Detected `af` or `afeq` group containing only a single etymon: `" .. singleAfParam .. "`; note that `af` and `afeq` groups must have at least two etymons. See the ] for more details.")
	end
	return output
end

function export.main(frame)
	-- Process argument input.
	local boolean = {type = "boolean"}
	local args = process_params(frame:getParent().args, {
		 = {required = true, type = "language", default = "und"},
		 = {list = true, disallow_holes = true},
		 = {required = true},
		 = {},
		 = boolean,
		 = boolean,
	})
	local lang = args
	-- Store non-numeric parameters as locals, then treat the main numeric list as `args`.
	local id = args
	local title = args
	local text = args
	local tree = args
	args = args
	
	-- The `title` parameter is used for overriding the page title.
	if title == nil then
		-- Get the canonical pagename.
		title = page_data.pagename
		-- Determine if current term is reconstructed.
		if page_data.namespace == "Reconstruction" or lang:hasType("reconstructed") then
			title = "*" .. title
		end
	end
	
	local output = {paramsSanityCheck(lang, args, id, title)}
	
	-- Add the langcode and `id`, to match the format of scraped parameters.
	insert(args, 1, lang:getCode())
	args = id
	argsOf .. ">" .. title .. ">" .. id] = args

	-- Add anchor and categories to output.
	local fulllang_name = lang:getFullName()
	insert(output, "<ul id=\"" .. fulllang_name .. ":_" .. id .. "\"></ul>")
	if page_data.namespace == "" or page_data.namespace == "Reconstruction" or page_data.namespace == "Appendix" then
		insert(output, etyCategories(title, lang, args, true, false, true))
	end

	-- Insert tree.
	if tree then
		insert(output, frame:extensionTag("templatestyles", "", {src="Module:etymon/styles.css"}))
		insert(output, (etyTree(title, lang, args, {}, true, false, "")))
		insert(output, format_categories({fulllang_name .. " entries with etymology trees"}, lang))
	end

	-- Insert text.
	if text == "++" then
		insert(output, etyText(title, lang, args, true, false))
	elseif text == "+" then
		insert(output, etyText(title, lang, args, true, 1))
	elseif text == "-" then
		insert(output, etyText(title, lang, args, false, 1))
	elseif text ~= nil then
		insert(output, etyText(title, lang, args, false, false))
	end

	return concat(output)
end

return export