--[[----------------------------------------------------------------------------

WFTableMerge.lua

--------------------------------------------------------------------------------

ADOBE CONFIDENTIAL
------------------
Copyright 2013 Adobe Systems Incorporated
All Rights Reserved.

NOTICE: All information contained herein is, and remain the property of
Adobe Systems Incorporated and its suppliers, if any. The intellectual and
technical concepts contained herein are proprietary to Adobe Systems
Incorporated and its suppliers and may be covered by U.S. and Foreign
Patents, patents in process, and are protected by trade secret or copyright
law.  Dissemination of this information or reproduction of this material is
strictly forbidden unless prior written permission is obtained from
Adobe Systems Incorporated.

------------------------------------------------------------------------------]]

	-- WF.core.logging
local WFLogger = require 'WFLogger'

	-- WF.core.utils
local KSTableUtils = require 'KSTableUtils'
local WFArguments = require 'WFArguments'


--------------------------------------------------------------------------------

local check = assert( WFArguments.check )

local logger = WFLogger 'WFTableMerge'
--	:setLevel 'debug'


--============================================================================--

-- @mark WFTableMerge namespace

local WFTableMerge = {}

--------------------------------------------------------------------------------

local function validateMaxDepth( optMaxDepth )

	if not optMaxDepth then
		optMaxDepth = 20
	end

	if optMaxDepth < 1 or optMaxDepth > 100 then
		error( "WFTableMerge.createOverlay: optMaxDepth, if specified, must be between 1 and 100", 2 )
	end
	
	return optMaxDepth
	
end

--------------------------------------------------------------------------------

local function assertTableHasNoMetatable( funcName, t )

	if getmetatable( t ) ~= nil then

		error( string.format( "WFTableMerge.%s: does not support tables with metatables",
							  funcName ), 3 )

	end

end

--------------------------------------------------------------------------------

local function applyOverlayImp( tableToModify, overlay, depth )

	local tableHasChanged = false

	if depth > 20 then
		error "WFTableMerge.applyOverlay: Apparent infinite recursion"
	end

	for k, v in pairs( overlay ) do

		if type( v ) == 'table' then

			if v._delete == true then

				if not tableHasChanged and tableToModify[ k ] ~= nil then
					tableHasChanged = true
				end

				tableToModify[ k ] = nil

			else

				local subTable

				if v._replace then

					subTable = {}

				else

					subTable = tableToModify[ k ]

					if subTable then
						if type( subTable ) ~= 'table' then
							logger:warnf( "Replacing key %s with a table", k )
							tableHasChanged = true
							subTable = {}
						end
					else
						tableHasChanged = true
						subTable = {}
					end

				end

				local nestedTableHasChanged = false
				
				tableToModify[ k ], nestedTableHasChanged = applyOverlayImp( subTable, v, depth + 1 )

				if nestedTableHasChanged then
					tableHasChanged = true
				end

				subTable._replace = nil

			end

		else

			if not tableHasChanged  then
			
				local oldValue = tableToModify[ k ]
				
				if oldValue ~= v then
					tableHasChanged = true
				end
				
			end
			
			tableToModify[ k ] = v
			
		end

	end

	return tableToModify, tableHasChanged

end

--------------------------------------------------------------------------------
--[[!
	\brief Applies a set of deltas to an existing table.

	Replace each value in \c tableToModify with the correspnding value in
	\c overlay if there is any. Any keys not present in \c overlay will be
	left with their existing value.

	For example, given:

\code
tableToModify = {
	a = "alpha",
	b = {
		b1 = 42,
		b2 = 45,
	},
}

overlay = {
	abc = "alphabet",
	b = {
		b2 = 51,
	},
}
\code

	this will return the following table:

\code
return {
	a = "alpha", -- unchanged
	abc = "alphabet",  -- taken from overlay
	b = {
		b1 = 42,  -- unchanged
		b2 = 51,  -- overwritten from overlay
	},
}
\code

	To delete a key at an existing position, use the magic table
	<code>{ _delete = true }</code>.

	To replace one table completely with another table, add the key
	<code>{ _replace = true }</code> at the root of the replacement
	table. This may be used at any level in the hierarchy except at
	the topmost level.

	\param tableToModify (optional, table) starting table
	\param overlay (optional, table) delta to apply

	\warning The existing table is modified in place!

	\return modified table, true/false (indicates content change)
]]--

function WFTableMerge.applyOverlay( tableToModify, overlay )

	check( '?table', '?table' )

	assertTableHasNoMetatable( 'applyOverlay', tableToModify )
	assertTableHasNoMetatable( 'applyOverlay' ,overlay )

	tableToModify = tableToModify or {}

	if not overlay then
		return tableToModify, false
	end

	if overlay._delete then
		error( "WFTableMerge.applyOverlay: _delete not allowed at top level", 2 )
	end

	return applyOverlayImp( tableToModify, overlay, 1 )

end

--------------------------------------------------------------------------------
-- SPAM [matthewj 2016-08-01]: Note that a noEmptyTables value of true will break
-- being able to apply the result to the base to get an exact match with the 
-- modified table. This parameter is strictly used when creating diffs to send to 
-- Oz. Those diffs are not allowed to create or produce an empty table in the json
-- on Oz. Additionally, arrays should be treated atomically. The parameter
-- noPartialArray is defined for taking care of the same.
local function createOverlayImp( base, modified, depth, maxDepth, noEmptyTables, noPartialArray )

	if depth > maxDepth then
		error "WFTableMerge.createOverlay: Apparent infinite recursion"
	end

	local allKeys = {}
	for k in pairs( base ) do
		allKeys[ k ] = true
	end

	for k in pairs( modified ) do
		allKeys[ k ] = true
	end
	
	local totalKeys, keysDeleted = 0, 0

	local result = {}
	
	for k in pairs( allKeys ) do
		
		totalKeys = totalKeys + 1
		
		local baseValue = base[ k ]
		local modifiedValue = modified[ k ]

		if baseValue == modifiedValue then

			-- Do nothing. No value to overlay.

		elseif baseValue ~= nil and modifiedValue == nil then
			
			result[ k ] = { _delete = true }
			keysDeleted = keysDeleted + 1

		elseif type( modifiedValue ) == 'table' then
			
			if noEmptyTables and not next( modifiedValue ) then
				-- the modified value is an empty table, so it 
				-- doesn't really matter what the base value is, 
				-- we need to delete the whole table
				result[ k ] = { _delete = true }
				keysDeleted = keysDeleted + 1
				
			elseif type( baseValue ) == 'table' then

				if noPartialArray and modifiedValue[ 1 ] then
					-- the modified value is an array,
					-- overwrite the entire array, if they
					-- are different.
					if not KSTableUtils.deepEquals( baseValue, modifiedValue ) then
						result[ k ] = modifiedValue
					end
					
				else
					local subOverlay = createOverlayImp( baseValue, modifiedValue, depth + 1, maxDepth, noEmptyTables, noPartialArray )

					-- Only place the sub-overlay into the result table
					-- if there are actual deltas we need to transfer.

					if next( subOverlay ) then
						result[ k ] = subOverlay
					end
					
					-- if the subOverlay is a delete, count it
					if subOverlay._delete == true then
						keysDeleted = keysDeleted + 1
					end
				end
				
			else

				-- Base value was scalar and modified is table.
				-- Just overwrite the value with modified's table.

				result[ k ] = modifiedValue

			end

		else

			result[ k ] = modifiedValue

		end
	
	end
	
	if noEmptyTables and totalKeys == keysDeleted then
		-- if we shouldn't allow empty tables and all 
		-- keys were deleted, the containing element 
		-- should be marked deleted
		result = { _delete = true }
	end
	
	return result

end

--------------------------------------------------------------------------------
--[[!
	\brief Given two tables, create an overlay such that \c applyOverlay
		could be used to reconstruct the second table.

	\param base (table) original table
	\param modified (table) modified table
	\param optMaxDepth (number) optional limit for table depth; if not specified,
		defaults to 20
	
	\return (table) overlay such that <code>applyOverlay( base, overlay )</code>
		would match \c modified
]]--

function WFTableMerge.createOverlay( base, modified, optMaxDepth )

	check( 'table', 'table', '?number' )

	optMaxDepth = validateMaxDepth( optMaxDepth )

	assertTableHasNoMetatable( 'createOverlay', base )
	assertTableHasNoMetatable( 'createOverlay', modified )

	return createOverlayImp( base, modified, 1, optMaxDepth, false, false )

end

--------------------------------------------------------------------------------
--[[!
	\brief Given two tables, create a diff between the two. This is just an
		alias for <code>createOverlay</code>

	\param base (table) original table
	\param modified (table) modified table
	\param optMaxDepth (number) optional limit for table depth; if not specified,
		defaults to 20
	
	\return (table) overlay such that <code>applyOverlay( base, overlay )</code>
		would match \c modified
]]--

function WFTableMerge.createDiff( base, modified, optMaxDepth )
	
	check( 'table', 'table', '?number' )
		
	return WFTableMerge.createOverlay( base, modified, optMaxDepth )

end

--------------------------------------------------------------------------------
--[[!
	\brief Given two tables, create a diff suitable to be sent to Oz. This is 
		very similar to \c createOverlay, but ensures that any modifications 
		resulting from applying the diff to Oz will not result in empty hashes
		on Oz. Additionally, the diff via this method cannot be applied via 
		\c applyOverlay to the base table to reconstruct the second table. As
		the result will differ from the modified table wherever the modified 
		table has empty subtables
		
	\param base (table) original table
	\param modified (table) modified table
	\param optMaxDepth (number) optional limit for table dept; if not specified,
		defaults to 20
		
	\return (table) diff between the base and modified tables that still maintains
		a valid document structure on Oz (notably, no empty hashes)
]]--

function WFTableMerge.createDiffForOz( base, modified, optMaxDepth )
	
	check( 'table', 'table', '?number' )
	
	optMaxDepth = validateMaxDepth( optMaxDepth )

	assertTableHasNoMetatable( 'createOverlay', base )
	assertTableHasNoMetatable( 'createOverlay', modified )

	return createOverlayImp( base, modified, 1, optMaxDepth, true, true )
	
end


--------------------------------------------------------------------------------

local function threeWayMerge_atomic( base, a, b )

	-- If only one side evolved compared to base, use the other side.

	local aEvolved = not KSTableUtils.deepEquals( base, a )
	local bEvolved = not KSTableUtils.deepEquals( base, b )

	if not aEvolved and not bEvolved then

		return a -- arbitrary choice

	elseif aEvolved and not bEvolved then

		return a

	elseif not aEvolved and bEvolved then

		return b

	end

	-- Both sides evolved from base. If they both evolved to the same
	-- value, we don't care what base was, we just accept that new value.

	if KSTableUtils.deepEquals( a, b ) then
		return a
	end

	-- Both evolved from base but are not equal to each other: We have a conflict.

	return a, b

end

--------------------------------------------------------------------------------

local function threeWayMergeImp( base, a, b )

	if base._merge == 'atomic' or a._merge == 'atomic' or b._merge == 'atomic' then

		-- At least one of the tables called for atomic merge so we have to compare
		-- the entire hierarchy from here down as a unit.

		return threeWayMerge_atomic( base, a, b )

	end

	if base[ 1 ] ~= nil or a[ 1 ] ~= nil or b[ 1 ] ~= nil then

		-- At least one of the tables has a value at index 1, so we think it's an array.
		-- This is also a reason to switch over to atomic merge.

		return threeWayMerge_atomic( base, a, b )

	end

	-- Non-atomic merge is actually the complicated case.

	local allKeys = {}
	for k in pairs( base ) do
		allKeys[ k ] = true
	end

	for k in pairs( a ) do
		allKeys[ k ] = true
	end

	for k in pairs( b ) do
		allKeys[ k ] = true
	end

	local result = {}
	local conflicts = nil

	for k in pairs( allKeys ) do

		local baseValue = base[ k ]
		local aValue = a[ k ]
		local bValue = b[ k ]

		-- Let's take care of the easy (scalar) cases first.

		if aValue == bValue then

			-- Doesn't matter if baseValue was different.
			-- If both a and b co-evolved to same value, accept it.

			result[ k ] = aValue

		elseif baseValue == aValue then

			result[ k ] = bValue

		elseif baseValue == bValue then

			result[ k ] = aValue

		else

			-- All three values are different.
			-- Might be a table or it might be a scalar conflict.

			local baseType = type( baseValue )
			local aType = type( aValue )
			local bType = type( bValue )

			-- Special case: If base + one of the deltas are a table
			-- with identical values and the other is a non-table,
			-- accept the other.

			if baseType == 'table' and bType == 'table' and aType ~= 'table'
				and KSTableUtils.deepEquals( baseValue, bValue )
			then

				result[ k ] = aValue

			elseif baseType == 'table' and aType == 'table' and bType ~= 'table'
				and KSTableUtils.deepEquals( baseValue, aValue )
			then

				result[ k ] = bValue

			else

				local conflictingValue

				if aType == 'table' and bType == 'table' then

					-- If a and b are both tables, then we descend into those
					-- tables and perform three-way merge on those. This may or
					-- may not generate a merge conflict.

					result[ k ], conflictingValue = threeWayMergeImp(
														baseType == 'table'
															and baseValue or {},
														aValue, bValue )

				else

					-- Values from a and b aren't even of the same type.
					-- Accept a's value and flag b's value as a conflict.

					result[ k ] = aValue

					if type( bValue ) == 'table' then

						if KSTableUtils.deepEquals( baseValue, bValue ) then

							-- base == b, but a is a different type. We can
							-- accept the value from a.

						else

							conflictingValue = {}
							for bk, bv in pairs( bValue ) do
								conflictingValue[ bk ] = bv
							end

							-- Assuming this conflict table is going to be used as
							-- an overlay, we want to toss any existing table completely.

							conflictingValue._replace = true

						end

					elseif bValue ~= nil then

						conflictingValue = bValue

					else

						conflictingValue = { _delete = true }

					end

				end

				if conflictingValue ~= nil then
					conflicts = conflicts or {}
					conflicts[ k ] = conflictingValue
				end

			end

		end

	end

	return result, conflicts

end

--------------------------------------------------------------------------------
--[[!
	\brief Perform a three-way merge on table values.

	\param base (table) common base value
	\param a (table) a table to merge
	\param b (table) another table to merge

	Recursively compares the contents of the three tables.

	If, for any key, base and either a or b have the same value, the result
	will contain the value that does not match base. (In other words, it assumed
	that the "intentional" change was performed in the one that differs from base.)

	If, for any key, all three tables contain different values, the result
	will contain the value that was in table "a" and the conflict (second) result
	will contain the value that was in table "b".

	\return (table) merged results, favoring table a in the event of a conflict
	\return (optional, table) conflicting results from table b that could not
		be merged (this will be in the form of an overlay against a)
]]--

function WFTableMerge.threeWayMerge( base, a, b )

	check( 'table', 'table', 'table' )

	assertTableHasNoMetatable( 'threeWayMerge', base )
	assertTableHasNoMetatable( 'threeWayMerge', a )
	assertTableHasNoMetatable( 'threeWayMerge', b )

	return threeWayMergeImp( base, a, b )

end

--------------------------------------------------------------------------------

return WFTableMerge
