--[[
* Look for single edits surrounded on both sides by equalities
* which can be shifted sideways to align the edit to a word boundary.
* e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples.
--]]

_diff_cleanupSemanticLossless = function(diffs: Array<Diff>)
	local pointer = 2
	-- Intentionally ignore the first and last element (don't need checking).
	while diffs[pointer + 1] do
		local prevDiff, nextDiff = diffs[pointer - 1], diffs[pointer + 1]
		if prevDiff[1] == DIFF_EQUAL and nextDiff[1] == DIFF_EQUAL then
			-- This is a single edit surrounded by equalities.
			local diff = diffs[pointer]

			local equality1 = prevDiff[2]
			local edit = diff[2]
			local equality2 = nextDiff[2]

			-- First, shift the edit as far left as possible.
			local commonOffset = _diff_commonSuffix(equality1, edit)
			if commonOffset > 0 then
				local commonString = strsub(edit, -commonOffset)
				equality1 = strsub(equality1, 1, -commonOffset - 1)
				edit = commonString .. strsub(edit, 1, -commonOffset - 1)
				equality2 = commonString .. equality2
			end

			-- Second, step character by character right, looking for the best fit.
			local bestEquality1 = equality1
			local bestEdit = edit
			local bestEquality2 = equality2
			local bestScore = _diff_cleanupSemanticScore(equality1, edit) + _diff_cleanupSemanticScore(edit, equality2)

			while strbyte(edit, 1) == strbyte(equality2, 1) do
				equality1 = equality1 .. strsub(edit, 1, 1)
				edit = strsub(edit, 2) .. strsub(equality2, 1, 1)
				equality2 = strsub(equality2, 2)
				local score = _diff_cleanupSemanticScore(equality1, edit) + _diff_cleanupSemanticScore(edit, equality2)
				-- The >= encourages trailing rather than leading whitespace on edits.
				if score >= bestScore then
					bestScore = score
					bestEquality1 = equality1
					bestEdit = edit
					bestEquality2 = equality2
				end
			end
			if prevDiff[2] ~= bestEquality1 then
				-- We have an improvement, save it back to the diff.
				if #bestEquality1 > 0 then
					diffs[pointer - 1][2] = bestEquality1
				else
					tremove(diffs, pointer - 1)
					pointer = pointer - 1
				end
				diffs[pointer][2] = bestEdit
				if #bestEquality2 > 0 then
					diffs[pointer + 1][2] = bestEquality2
				else
					tremove(diffs, pointer + 1)
					pointer -= 1
				end
			end
		end
		pointer += 1
	end
end
