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

KSRDirectedAcyclicGraphTest.lua

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

ADOBE CONFIDENTIAL
------------------
Copyright 2010 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.

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

local KSRDirectedAcyclicGraphTest = { }

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

-- local assertf = require 'KSLuaUtils'.assertf
local string_format = string.format

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

local function makeDAGFunctions( params )

	local KSRDirectedAcyclicGraph = require 'KSRDirectedAcyclicGraph'
	
	local KSRDirectedAcyclicGraph_makeDAGFunctions = assert( KSRDirectedAcyclicGraph.makeDAGFunctions, "makeDAGFunctions not found" )
	
	return KSRDirectedAcyclicGraph_makeDAGFunctions( params )

end

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

-- We disallow hitting the __index and __newindex metamethods on nodes in the
-- test case because we don't want to preclude node designs that use them.

local nodeMT = {
	__index = function()
		local msg = "Invalid call to __index metamethod for DAG node: " .. debug.traceback()
		error( msg, 0 )
	end,
	__index = function()
		local msg = "Invalid call to __newindex metamethod for DAG node: " .. debug.traceback()
		error( msg, 0 )
	end,
}

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

local function makeNode( dag, strong, isBase, idx, ... )
	local node = dag.allocNode( strong )
	node.name = string_format( "Node %d", idx )
	setmetatable( node, nodeMT )
	return dag.initNode( node, "test", isBase, ... )
end

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

local function nodeName( node )
	return node.name or "< >"
end

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

local function testDAGFunctions( params )

	-- FIXME [mhamburg 2011-03-14]:
	-- [scouten 2011-03-11]: This test is long and hard to read through.
	-- Probably not worth the effort to change it, but I'd prefer to have seen
	-- it as a series of separate tests if possible.
	-- [scouten 2011-03-11]: One thing that might help would be to name
	-- the nodes by their characteristics (i.e. node5 would be node5_strong or
	-- similar). I found myself having to refer back to this initial declaration
	-- area frequently to make sure I wasn't missing something.

	params.nodeName = nodeName

	local dag = makeDAGFunctions( params )

	local node1 = makeNode( dag, false, false, 1 )
	local node2 = makeNode( dag, false, false, 2 )
	local node3 = makeNode( dag, false, false, 3 )
	local node4 = makeNode( dag, false, false, 4 )
	local node5 = makeNode( dag, true,  false, 5 )
	local node6 = makeNode( dag, false, false, 6 )
	local node7 = makeNode( dag, false, false, 7 )
	
	local node8 = makeNode( dag, false, false, 8, node7 )
	
	local node9 = makeNode( dag, false, false, 9 )
	local node10 = makeNode( dag, false, false, 10 )
	local node11 = makeNode( dag, false, false, 11, node9, node10 )
	local node12 = makeNode( dag, false, false, 12, node11 )
	local node13 = makeNode( dag, false, false, 13, node11 )
	
	local node14 = makeNode( dag, false, false, 14 )
	local node15 = makeNode( dag, false, false, 15, node14 )
	local node16 = makeNode( dag, false, false, 16, node15 )
	local node17 = makeNode( dag, false, true, 17 ) -- Our test of base nodes
	local node18 = makeNode( dag, false, false, 18 )
	
	local nodes = setmetatable( { node1, node2, node3, node4, node5, node6, node7, node8 }, { __mode = "kv" } )

	dag.checkSuccessors( node1 )
	dag.checkSuccessors( node2 )
	
	assert( not dag.nodeHasPredecessor( node2 ), "Node should have no predecessor initially." )
	
	dag.addLink( node1, node2 )
	
	assert( dag.nodeHasPredecessor( node2 ), "Node should have predecessor after link." )
		
	dag.checkDepths( node1 )

	dag.checkSuccessors( node1, node2 )
	dag.checkSuccessors( node2 )
	
	assert( dag.nodeHasPredecessor( node2 ), "Node should have predecessor after link." )
		
	dag.addLink( node1, node3 )
			
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node2, node3 )
	dag.checkSuccessors( node2 )
	dag.checkSuccessors( node3 )
	
	dag.addLink( node2, node3 )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node2, node3 )
	dag.checkSuccessors( node2, node3 )
	dag.checkSuccessors( node3 )
	
	assert( pcall( dag.addLink, node3, node1 ) == false, "Should not be able to add cyclic link" )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node2, node3 )
	dag.checkSuccessors( node2, node3 )
	dag.checkSuccessors( node3 )

	assert( pcall( dag.addLink, node3, node2 ) == false, "Should not be able to add cyclic link (2)" )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node2, node3 )
	dag.checkSuccessors( node2, node3 )
	dag.checkSuccessors( node3 )
	
	dag.removeLink( node2, node3 )
	dag.addLink( node3, node2 )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node2, node3 )
	dag.checkSuccessors( node2 )
	dag.checkSuccessors( node3, node2 )
	
	assert( dag.nodeHasPredecessor( node3 ), "Node 3 should still be preceded by node 1." )

	-- Check that the weak logic work.
	
	node2 = nil
	node3 = nil
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( nodes[ 1 ], "Node 1 should have survived" )
	assert( not nodes[ 2 ], "Node 2 should not have survived" )
	assert( not nodes[ 3 ], "Node 3 should not have survived" )
	
	dag.checkSuccessors( node1 )
	
	-- Now, we'll check that the strong links work
	
	dag.addLink( node1, node4 )
	dag.addLink( node4, node5 )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node4 )
	dag.checkSuccessors( node4, node5 )
	
	node4 = nil
	node5 = nil
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( nodes[ 1 ], "Node 1 should have survived" )
	assert( nodes[ 4 ], "Node 4 should have survived" )
	assert( nodes[ 5 ], "Node 5 should have survived" )
	
	dag.removeLink( nodes[ 4 ], nodes[ 5 ] )
	
	assert( not dag.nodeHasPredecessor( nodes[ 5 ], "Node 5 should no longer have a predecessor." ))
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( nodes[ 1 ], "Node 1 should have survived" )
	assert( not nodes[ 4 ], "Node 4 should not have survived" )
	assert( not nodes[ 5 ], "Node 5 should not have survived" )
	
	-- Now, we'll check that predecessor links work to keep nodes alive. This is
	-- only semi-desirable since essentially for non-strong links we really only
	-- want to keep a node alive if it is reachable from both ends by code
	-- outside the system. But proper use of tear down should handle most of
	-- this.
		
	dag.addLink( node1, node6 )
	dag.addLink( node6, node7 )
	
	dag.checkDepths( node1 )
	
	dag.checkSuccessors( node1, node6 )
	dag.checkSuccessors( node6, node7 )
	dag.checkSuccessors( node7, node8 )
	
	-- Test getNodeDepth.
	
	assert( 4 <= dag.getNodeDepth( node8 ), "node 8 is too shallow" )
	
	node1 = nil
	node6 = nil
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( nodes[ 1 ], "Node 1 should have survived" )
	assert( nodes[ 6 ], "Node 6 should have survived" )
	assert( nodes[ 7 ], "Node 7 should have survived" )
	assert( nodes[ 8 ], "Node 8 should have survived" )
	
	node8 = nil
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( nodes[ 1 ], "Node 1 should have survived" )
	assert( nodes[ 6 ], "Node 6 should have survived" )
	assert( nodes[ 7 ], "Node 7 should have survived" )
	assert( not nodes[ 8 ], "Node 8 should not have survived" )
	
	dag.checkSuccessors( nodes[ 1 ], nodes[ 6 ] )
	dag.checkSuccessors( nodes[ 6 ], nodes[ 7 ] )
	dag.checkSuccessors( nodes[ 7 ] )
	
	node7 = nil
	
	collectgarbage()
	collectgarbage()
	collectgarbage()
	
	assert( not nodes[ 1 ], "Node 1 should not have survived" )
	assert( not nodes[ 6 ], "Node 6 should not have survived" )
	assert( not nodes[ 7 ], "Node 7 should not have survived" )
	
	dag.checkSuccessors( node9, node11 )
	dag.checkSuccessors( node10, node11 )
	dag.checkSuccessors( node11, node12, node13 )
	
	assert( not dag.nodeIsDone( node11 ), "Node 11 should not already be closed." )
	
	dag.disconnectNodeAndMarkAsDone( node11 )
	
	assert( dag.nodeIsDone( node11 ), "Node 11 should be closed now." )
	
	dag.checkSuccessors( node9 )
	dag.checkSuccessors( node10 )
	dag.checkSuccessors( node11 )
	assert( not dag.nodeHasPredecessor( node12 ) )
	assert( not dag.nodeHasPredecessor( node13 ) )
	
	assert( not dag.nodeIsDone( node12 ), "Node 12 should not already be closed." )
	
	dag.disconnectNodeAndMarkAsDone( node12 )
	
	assert( dag.nodeIsDone( node12 ), "Node 12 should be closed now." )
	
	-- Check the base logic.
	
	assert( dag.nodeIsBase( node17 ), "Node 17 should be a base" )
	assert( not dag.nodeIsBase( node14 ), "Node 14 should not be a base" )
	
	dag.addLink( node17, node18 )
	dag.addLink( node15, node17 )
	
	dag.checkSuccessors( node14, node15 )
	dag.checkSuccessors( node15, node16, node17 )
	dag.checkSuccessors( node16 )
	dag.checkSuccessors( node17, node18 )
	dag.checkSuccessors( node18 )
	
	assert( dag.getNodeDepth( node18 ) == 1, "Node 18 should have depth one because it is preceded by a base node" )
	
	dag.addLink( node18, node14 ) -- Safe because the base node lets us have a cycle
	
end

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

function KSRDirectedAcyclicGraphTest.testMakeDAGFunctions()

	testDAGFunctions { }

end

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

return KSRDirectedAcyclicGraphTest
