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

KSRDirectedAcyclicGraph.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.

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

--[[

KSRDirectedAcyclicGraph:

	This module provides a routine for creating a table full of functions for
	manipulating a DAG built out of tables with private keys. The DAG recognizes
	both strong and weak nodes where weak nodes are not kept alive by their
	predecessors but nodes always keep their predecessors alive.
	
	When we create the table of functions, we supply it with a table of
	customization options including:
	
		nodeName: A function to take a node table and return a string for debugging
			-- GRUNGE [mhamburg 2011-01-12]: This could just use __tostring.
			
		gainedFirstSuccessor: A function taking a node. This will be called
			when a node gains its first successor.
			
		lostSuccessor: A function taking a node to be called if the node loses
			a successor.
			
	The functions created in the table include:
	
		function allocNode( optStrongSuccessor )
			This creates a table with various fields filled in. The strong flag
			indicates whether this will be a strong node. The node is not
			actually ready for use until you also call:
			
		function initNode( node, nodeKind, isBase, ...predecessors... )
			This finishes the node initialization and wires it up appropriately.
			The varargs section lists its predecessors. This returns the node.
			
			So the allocation pattern is:
			
				node = allocNode( optStrongSuccessor )
				... set values before initialization completes ...
				initNode( node, nodeKind, isBase, ... predecessors... )
				
			A short version with no extra initialization is:
			
				return initNode( allocNode( strong ), nodeKind, isBase, ...predecessors... )
			
		function addLink( predecessor, successor )
			Add a link from predecessor to successor.
			
		function removeLink( predecessor, successor )
			Remove the link if any from predecessor to successor.
			
		function iterSuccessors( node )
			Returns an iterator for the successors of a node. It is an error
			(undetected at present) to add successors while iterating successors.
			
		function getNodeDepth( node )
			Get the current depth for node.
			
		function isNode( v )
			Returns true iff v is a node. (Note done nodes are still nodes.)
			
	It also includes the following debugging functions. This is where the node
	name actually matters.
	
		function assertNode( node [ , optExtraMessage ] )
			Check that node is a valid node for this DAG. Throw if it is not.
			
		function checkDepths( rootNode )
			Makes sure that the depth values are all properly increasing as
			we move from predecessors to successors.
			
		function checkSuccessors( node, ...successors... )
			Check that the successors to node are exactly the listed nodes.

]]

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

local assertf = require 'KSLuaUtils'.assertf
local pairs = pairs
local select = select
local assert = assert
local string_format = string.format
local math_max = math.max

local KSTableUtils = require 'KSTableUtils'
local KSTableUtils_makeFullyWeak = KSTableUtils.makeFullyWeak

local KSFunctionUtils = require 'KSFunctionUtils'

local KSLeaks = require 'KSLeaks'

local nop = assert( KSFunctionUtils.nop )

local KSLeaks_registerObject = assert( KSLeaks.registerObject )

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

-- FIXME [mhamburg 2011-01-12]: We could optimize the predecessors case for
-- single predecessors I haven't done that yet, because it isn't critical
-- in order to get this working.

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

-- FIXME [mhamburg 2011-01-12]: Move to KSRIterators

local function iterNone()
	return nil
end

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

-- Add element to a set at t[ k ] creating the set if need be. Returns true
-- if the set didn't exist before (which is akin to it being empty though
-- not quite the same).

local function addSetFieldElement( t, k, element )
	local s = rawget( t, k )
	local result = false
	if not s then
		s = { }
		rawset( t, k, s )
		result = true
	end
	s[ element ] = element
	return result
end

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

-- Remove an element from an optional set at t[ k ]. Removes the set if it is
-- now empty and returns true.

local function removeSetFieldElement( t, k, element )
	local s = rawget( t, k )
	if s and s[ element ] then
		s[ element ] = nil
		if next( s ) == nil then
			rawset( t, k, false )
			return true
		end
	end
	return false
end

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

-- Iterate a set field if not empty.

local function iterSetField( t, k )
	local s = rawget( t, k )
	if not s then
		return iterNone
	else
		return pairs( s )
	end
end

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

local function makeDAGFunctions( params )

	-- FIXME [mhamburg 2011-03-14]
	-- This code makes a private namespace of functions so that it could be
	-- used by something other than the reactive code. This is design overkill
	-- and should probably go away.

	local pairs = pairs
	local string_format = string_format
	
	-- We need to track whether or not something is a node for debugging purposes.
	-- We store the node kind as the value.
	
	local allNodes = KSTableUtils_makeFullyWeak()
	
	local function isNode( node )
		return not not allNodes[ node ]
	end
	
	local function assertNode( node, msg )
		if isNode( node ) then
			return node
		end
		local tback = debug.traceback()
		local errMsg
		if msg then
			errMsg = string_format( "Expected to be passed a node (%s): %s", tostring( msg ), tback )
		else
			errMsg = string_format( "Expected to be passed a node: %s", tback )
		end
		error( errMsg, 0 )
	end
	
	local function wrapAssertNode( msg, fn )
		return function( node )
			assertNode( node, msg )
			return fn( node )
		end
	end
	
	-- Set up a default node name function for debugging.

	local nodeName = params.nodeName
	
	if not nodeName then
		nodeName = function() return "< >" end
		-- FIXME [mhamburg 2011-03-14]: [scouten 2011-03-11]: Use the constant function?
	end
	
	-- We iterate successors using the optional set field logic. Note, however,
	-- that because we apply different rules to successors, we do not use those
	-- routines for adding and removing successors.

	-- FIXME [mhamburg 2011-03-14] : [scouten 2011-03-11]: Scratching my head over this comment. Perhaps
	-- you could explain what is different about successors and how that impacts
	-- the add/remove logic.
	
	local function node_iterSuccessors( node )
		return iterSetField( node, 'private:allSuccessors' )
	end
	
	local function node_iterPredecessors( node )
		return iterSetField( node, 'private:predecessors' )
	end
	
	-- Notification and update for a node achieving strong status by gaining its first
	-- strong successor.
		
	local function node_becameStrong( node )
		for pred in node_iterPredecessors( node ) do
			if addSetFieldElement( pred, 'private:strongSuccessors', node ) then
				if not rawget( pred, 'private:nodeIsStrongSuccessor' ) then
					node_becameStrong( pred )
				end
			end
		end
	end
	
	-- Notification and update for a node losing strong status by losing all of its
	-- strong successors.
		
	local function node_becameWeak( node )
		for pred in node_iterPredecessors( node ) do
			if removeSetFieldElement( pred, 'private:strongSuccessors', node ) then
				if not rawget( pred, 'private:nodeIsStrongSuccessor' ) then
					node_becameWeak( pred )
				end
			end
		end
	end
	
	-- Does the node have a predecessor? This relies on the clearing logic dropping
	-- us down to false instead of a table.
	
	local function node_hasPredecessor( node )
		return not not rawget( node, 'private:predecessors' )
	end
	
	-- We use the depth field to mark nodes as done by setting it to -1. Since we won't
	-- allow done nodes in links, this shouldn't matter.
	
	local function node_isDone( node )
		return rawget( node, 'private:depth' ) == -1
	end
	
	-- We can force a node to be a base node. When this is the case, it has depth zero.
	
	-- FIXME [mhamburg 2011-03-14] : [scouten 2011-03-11]: What does it mean to be a base node? Is this an init-time
	-- operation, or can you mark a node as base at any time? If init-time, perhaps this
	-- condition should be tested/verified?
	
	local function node_markAsBase( node )
		assert( not node_isDone( node ), "Cannot change base status for a done node." )
		rawset( node, 'private:depth', 0 )
	end
	
	local function node_isBase( node )
		return rawget( node, 'private:depth' ) == 0
	end
	
	-- Recursively walk the successor links from a node making sure that the depth
	-- is at least the supplied depth and increases by at least one each time we
	-- follow a link. This will run forever if the graph has cycles, but we use it
	-- in addLink to prevent that.
	
	local function node_raiseDepth( node, newDepth )
	
		if node_isBase( node ) then
			return
		end
	
		if newDepth <= rawget( node, 'private:depth' ) then
			return
		end
		
		rawset( node, 'private:depth', newDepth )
		
		local nextDepth = newDepth + 1
		
		for successor in node_iterSuccessors( node ) do
			node_raiseDepth( successor, nextDepth )
		end
		
	end
	
	-- Notification function for nodes that transition from having no successors
	-- to having one successor.
	
	local gainedFirstSuccessor = params.gainedFirstSuccessor or nop
	
	-- Add a link from pred to succ.
	
	local function addLink( pred, succ )
	
		-- Check that we've got nodes
		
		assertNode( pred, "addLink: predecessor" )
		assertNode( succ, "addLink: successor" )
		
		-- The successor should not be done.
		
		assert( not node_isDone( succ ), "addLink: successor should not be done" )
		
		-- If the predecessor is done, we simply fail to construct the link.
		
		if node_isDone( pred ) then
			return
		end
		
		-- Make sure the depth is right (this also detects cycles though in doing so it leaves the depths incremented)

		local predDepth = rawget( pred, 'private:depth' )
		
		node_raiseDepth( succ, predDepth + 1 )

		assert( rawget( pred, 'private:depth' ) == predDepth, "Cannot add cyclic link" )
		
		-- Check the strong status for each node. We may be changing the status for the
		-- predecessor node, so we only check whether the local flag would block
		-- propagation.

		local succIsStrong = rawget( succ, 'private:nodeIsStrongSuccessor' ) or rawget( succ, 'private:strongSuccessors' )
		local predNodeIsStrong = rawget( pred, 'private:nodeIsStrongSuccessor' )
	
		local allSuccessors = rawget( pred, 'private:allSuccessors' )
		
		if not allSuccessors then
			allSuccessors = KSTableUtils_makeFullyWeak()
			rawset( pred, 'private:allSuccessors', allSuccessors )
			gainedFirstSuccessor( pred )
		end
		
		allSuccessors[ succ ] = succ
		
		addSetFieldElement( succ, 'private:predecessors', pred )
	
		-- If strong, then we need to add it to the set of strong successors and
		-- possibly run up the tree adding strong successors.
		
		if succIsStrong then
			if addSetFieldElement( pred, 'private:strongSuccessors', succ ) then
				if not predNodeIsStrong then
					node_becameStrong( pred )
				end
			end
		end
		
	end
	
	-- Notification function for nodes that explicitly lose successors (as opposed to losing
	-- them via garbage collection).

	local lostSuccessor = params.lostSuccessor
	
	-- Remove the link if any from pred to succ.
	
	local function nodes_removeLink( pred, succ )
	
		-- We exit early if there isn't a link from pred to succ

		local allSuccessors = rawget( pred, 'private:allSuccessors' )
		
		if not allSuccessors then
			return
		end
		
		if not allSuccessors[ succ ] then
			return
		end
		
		-- Deal with strong status first.
		
		if removeSetFieldElement( pred, 'private:strongSuccessors', succ ) then
			if not rawget( pred, 'private:nodeIsStrongSuccessor' ) then
				node_becameWeak( pred )
			end
		end
		
		-- Now break the weak link.
		
		allSuccessors[ succ ] = nil
		
		-- Remove the predecessor link.
		
		removeSetFieldElement( succ, 'private:predecessors', pred )
		
		-- And do any necessary notification.

		if lostSuccessor then
			lostSuccessor( succ )
		end
	
	end
	
	-- Get the depth for a node.
	
	local function getNodeDepth( node )
		assertNode( node, "getNodeDepth" )
		return rawget( node, 'private:depth' )
	end
	
	-- Get the kind for a node
	
	local function getNodeKind( node )
		assertNode( node, "getNodeKind" )
		return allNodes[ node ]
	end
	
	-- Check that a link exists both ways between pred and succ.
	
	local function checkLink( pred, succ )

		local successors = rawget( pred, 'private:allSuccessors' )
		assertf( successors and successors[ succ ], "Successor not linked (%s -> %s)", nodeName( pred ), nodeName( succ ) )

		local predecessors = rawget( succ, 'private:predecessors' )
		assert( predecessors and predecessors[ pred ], "Predecessor not linked (%s <- %s)", nodeName( pred ), nodeName( succ ) )

	end
	
	-- Check that the depth values are properly increasing as we follow successor chains.
	-- helper which handles recursion and API routine that hides extra parameters for recursion.
	
	local function checkDepths_helper( node, minDepth )
		local nodeDepth = rawget( node, 'private:depth' )
		assert( node_isBase( node ) or ( minDepth <= nodeDepth ), "node depth is too small" )
		local nextDepth = nodeDepth + 1
		for successor in node_iterSuccessors( node ) do
			checkDepths_helper( successor, nextDepth )
		end
	end
	
	-- Check that the depth values are properly increasing as we follow successor chains.
	-- Exported function.

	local function checkDepths( node )

		assertNode( node, "checkDepths" )

		checkDepths_helper( node, 0 )

	end
	
	-- Check that node has exactly the expected successors.
	
	local function checkSuccessors( node, ... )
	
		assertNode( node, "checkSuccessors: node" )

		local successors = { }
	
		for i = 1, select( '#', ... ) do
			local succ = select( i, ... )
			assertNode( succ, "checkSuccessors: successor" )
			successors[ succ ] = false
			checkLink( node, succ )
		end
		
		for succ in node_iterSuccessors( node ) do
			local status = successors[ succ ]
			assert( status ~= nil, "Only expected successors in list" )
			assert( status == false, "Only expected to visit successors once" )
			successors[ succ ] = true
		end
		
		for succ, value in pairs( successors ) do
			assertf( value, "Failed to find successor for %s", nodeName( succ ) )
		end
	
	end
	
	-- A utility function for making a pre-initialized node table. This needs to be
	-- handed to initNode to finish the initialization.
	
	local function allocNode( optStrongSuccessor, optWeakPredecessor )
	
		return {
			[ 'private:depth' ] = 1,
			[ 'private:predecessors' ] = false,
			[ 'private:allSuccessors' ] = false,
			[ 'private:strongSuccessors' ] = false,
			[ 'private:nodeIsStrongSuccessor' ] = not not optStrongSuccessor,
		}
	
	end
	
	-- Finish node construction potentially wiring the node into the graph based on the
	-- list of predecessors.
	
	local function initNode( node, nodeKind, isBase, ... )
	
		assert( rawget( node, 'private:depth' ), "Table does not appear to have come from allocNode." )
		assert( not allNodes[ node ], "Node table appears to have already been used." )
	
		-- The varargs section provides us with a list of predecessors. We use those
		-- to determine the initial depth and after construction we wire them up as
		-- predecessors.
		
		local predDepth = 0
		
		local predCount = select( '#', ... )
		
		for i = 1, predCount do
			local pred = select( i, ... )
			if pred then
				assertNode( pred, "initNode: predecessor" )
				if not node_isDone( pred ) then
					predDepth = math_max( predDepth, rawget( pred, 'private:depth' ) )
				end
			end
		end
		
		-- We don't actually raise the depth for base nodes. We leave in the computation
		-- because it also does some validation.
		
		if isBase then
			node_markAsBase( node )
		else
			rawset( node, 'private:depth', predDepth + 1 )
		end
		
		-- Mark it as a node

		allNodes[ node ] = nodeKind
		
		-- Handle counting
		
		KSLeaks_registerObject( nodeKind, node )
		
		-- Wire up the predecessors
		
		for i = 1, predCount do
			local pred = select( i, ... )
			if pred and not node_isDone( pred ) then
				addLink( pred, node )
			end
		end
		
		-- Return it for chaining
		
		return node

	end
	
	-- Mark the node as done. This disconnects it in both directions and adjusts
	-- the depth.
		
	local function disconnectNodeAndMarkAsDone( node )
	
		assertNode( node, "disconnectNodeAndMarkAsDone" )
		
		if node_isDone( node ) then
			return
		end
		
		-- Remove successor links
		
		for succ in node_iterSuccessors( node ) do
			nodes_removeLink( node, succ )
		end
		
		-- Remove predecessor links
		
		for pred in node_iterPredecessors( node ) do
			nodes_removeLink( pred, node )
		end
		
		-- Set the depth to mark the node as done

		rawset( node, 'private:depth', -1 )
	
	end
	
	local function removeLink( pred, succ )
	
		assertNode( pred, "removeLink: predecessor" )
		assertNode( succ, "removeLink: successor" )
		
		return nodes_removeLink( pred, succ )
		
	end
	
	return {
		allocNode = allocNode,
		initNode = initNode,
		isNode = isNode,
		addLink = addLink,
		removeLink = removeLink,
		iterSuccessors = wrapAssertNode( "iterSuccessors", node_iterSuccessors ),
		markNodeAsBase = wrapAssertNode( "markNodeAsBase", node_markAsBase ),
		nodeIsBase = wrapAssertNode( "nodeIsBase", node_isBase ),
		getNodeDepth = getNodeDepth,
		getNodeKind = getNodeKind,
		disconnectNodeAndMarkAsDone = disconnectNodeAndMarkAsDone,
		nodeIsDone = wrapAssertNode( "nodeIsDone", node_isDone ),
		nodeHasPredecessor = wrapAssertNode( "nodeHasPredecessor", node_hasPredecessor ),
		-- Debugging functions
		assertNode = assertNode,
		checkDepths = checkDepths,
		checkSuccessors = checkSuccessors,
	}

end

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

return {
	makeDAGFunctions = makeDAGFunctions
}
