--[[
* Reduce the number of edits by eliminating semantically trivial equalities.
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples.
--]]

local function diff_cleanupSemantic(diffs: Array<Diff>)
	local changes = false
	local equalities = {} -- Stack of indices where equalities are found.
	local equalitiesLength = 0 -- Keeping our own length var is faster.
	local lastEquality = nil
	-- Always equal to diffs[equalities[equalitiesLength]][2]
	local pointer = 1 -- Index of current position.
	-- Number of characters that changed prior to the equality.
	local length_insertions1 = 0
	local length_deletions1 = 0
	-- Number of characters that changed after the equality.
	local length_insertions2 = 0
	local length_deletions2 = 0

	while diffs[pointer] do
		if diffs[pointer][1] == DIFF_EQUAL then -- Equality found.
			equalitiesLength = equalitiesLength + 1
			equalities[equalitiesLength] = pointer
			length_insertions1 = length_insertions2
			length_deletions1 = length_deletions2
			length_insertions2 = 0
			length_deletions2 = 0
			lastEquality = diffs[pointer][2]
		else -- An insertion or deletion.
			if diffs[pointer][1] == DIFF_INSERT then
				length_insertions2 = length_insertions2 + #diffs[pointer][2]
			else
				length_deletions2 = length_deletions2 + #diffs[pointer][2]
			end
			-- Eliminate an equality that is smaller or equal to the edits on both
			-- sides of it.
			if
				lastEquality
				and #lastEquality <= max(length_insertions1, length_deletions1)
				and #lastEquality <= max(length_insertions2, length_deletions2)
			then
				-- Duplicate record.
				tinsert(diffs, equalities[equalitiesLength], Diff.new(DIFF_DELETE, lastEquality))
				-- Change second copy to insert.
				diffs[equalities[equalitiesLength] + 1][1] = DIFF_INSERT
				-- Throw away the equality we just deleted.
				equalitiesLength = equalitiesLength - 1
				-- Throw away the previous equality (it needs to be reevaluated).
				equalitiesLength = equalitiesLength - 1
				pointer = (equalitiesLength > 0) and equalities[equalitiesLength] or 0
				length_insertions1, length_deletions1 = 0, 0 -- Reset the counters.
				length_insertions2, length_deletions2 = 0, 0
				lastEquality = nil
				changes = true
			end
		end
		pointer = pointer + 1
	end

	-- Normalize the diff.
	if changes then
		_diff_cleanupMerge(diffs)
	end
	_diff_cleanupSemanticLossless(diffs)

	-- Find any overlaps between deletions and insertions.
	-- e.g: <del>abcxxx</del><ins>xxxdef</ins>
	--   -> <del>abc</del>xxx<ins>def</ins>
	-- e.g: <del>xxxabc</del><ins>defxxx</ins>
	--   -> <ins>def</ins>xxx<del>abc</del>
	-- Only extract an overlap if it is as big as the edit ahead or behind it.
	pointer = 2
	while diffs[pointer] do
		if diffs[pointer - 1][1] == DIFF_DELETE and diffs[pointer][1] == DIFF_INSERT then
			local deletion = diffs[pointer - 1][2]
			local insertion = diffs[pointer][2]
			local overlap_length1 = _diff_commonOverlap(deletion, insertion)
			local overlap_length2 = _diff_commonOverlap(insertion, deletion)
			if overlap_length1 >= overlap_length2 then
				if overlap_length1 >= #deletion / 2 or overlap_length1 >= #insertion / 2 then
					-- Overlap found.  Insert an equality and trim the surrounding edits.
					tinsert(diffs, pointer, Diff.new(DIFF_EQUAL, strsub(insertion, 1, overlap_length1)))
					diffs[pointer - 1][2] = strsub(deletion, 1, #deletion - overlap_length1)
					diffs[pointer + 1][2] = strsub(insertion, overlap_length1 + 1)
					pointer = pointer + 1
				end
			else
				if overlap_length2 >= #deletion / 2 or overlap_length2 >= #insertion / 2 then
					-- Reverse overlap found.
					-- Insert an equality and swap and trim the surrounding edits.
					tinsert(diffs, pointer, Diff.new(DIFF_EQUAL, strsub(deletion, 1, overlap_length2)))
					diffs[pointer - 1] = { DIFF_INSERT, strsub(insertion, 1, #insertion - overlap_length2) }
					diffs[pointer + 1] = { DIFF_DELETE, strsub(deletion, overlap_length2 + 1) }
					pointer = pointer + 1
				end
			end
			pointer = pointer + 1
		end
		pointer = pointer + 1
	end
end
