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

KrTableArchiver.lua

********************************************************************************

ADOBE CONFIDENTIAL
------------------
Copyright 2003 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 string_find = string.find
local string_len = string.len

local type = type
local pairs = pairs

local table_insert = table.insert

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

--@mark	-
--@mark	Utilities

---------------------------------------------------------------------------------
--[[
	Generic compare of any two values. If the two types are not the same type,
	then the types are compared (thus ensuring that all values of each type
	will sort together).
]]--

local function compareValues( a, b )

	local typeA = type( a )
	local typeB = type( b )

	if typeA ~= typeB then
		return typeA < typeB
	end

	return a < b

end

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

local function indentString( indent )

	return string.rep( '\t', indent )

end

---------------------------------------------------------------------------------
--[[
	Return an array of all the keys in a table.
]]--

local function allKeys( t )

	local result = {}

	for k, _ in pairs( t ) do
		table.insert( result, k )
	end

	return result

end

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

local function sortedKeys( t )

	local result = allKeys( t )
	table.sort( result, compareValues )
	return result

end

---------------------------------------------------------------------------------
--[[
	I'm not using table.getn due to potential changes to the behavior of
	that function in Lua 5.1 where it might not stop after finding the first
	hole in the array.
]]--

local function getNumSuccessiveIntKeys( t )

	local intKey = 1
	while t[ intKey ] do
		intKey = intKey + 1
	end

	return intKey - 1

end

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

local kLuaKeywords = {
	[ "and" ] = true,
	[ "break" ] = true,
	[ "do" ] = true,
	[ "else" ] = true,
	[ "elseif" ] = true,
	[ "end" ] = true,
	[ "false" ] = true,
	[ "for" ] = true,
	[ "function" ] = true,
	[ "if" ] = true,
	[ "in" ] = true,
	[ "local" ] = true,
	[ "nil" ] = true,
	[ "not" ] = true,
	[ "or" ] = true,
	[ "repeat" ] = true,
	[ "return" ] = true,
	[ "then" ] = true,
	[ "true" ] = true,
	[ "until" ] = true,
	[ "while" ] = true,

		-- [tgaul 2008-01-31]: technically, these aren't keywords,
		-- but it seems prudent to protect them as well.
	[ "arg" ] = true,
	[ "self" ] = true,
	
	-- [tgaul 2008-01-31]: Note that if a future version of Lua adds keywords,
	-- this code won't be preventing those from being written as an identifier.
	--
	-- We could quote all key string using the clumsy ["foo"] syntax in our
	-- serialized tables, but that would make them appear much less pretty, so
	-- I'm inclined to just live with this exclusion list and that possibility.
	--
	-- What we probably really need is a serialized table format that doesn't
	-- require a Lua interpreter to expand...
}

local gValidIdentifiers = {}

local gInvalidIdentifiers = setmetatable( {}, { __mode = 'kv' } )
	-- A map from invalid strings to tables. Cleared at GC time.

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

local function isStringValidIdentifier( v )

	if gValidIdentifiers[ v ] then
		return true
	end
	
	if kLuaKeywords[ v ] then
		return false
	end
	
	if gInvalidIdentifiers[ v ] then
		return false
	end
	
	if #v == 0 then
		return false
	end
	
	local first, last = string_find( v, '[%w_]*' )
	
	if first ~= 1 or last ~= string_len( v ) or string_find( v, '%d' ) == 1 then
		gInvalidIdentifiers[ v ] = { }
		return false
	end
	
	gValidIdentifiers[ v ] = true
	
	return true

end

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

local function isValueValidIdentifier( v )
	return type( v ) == 'string' and isStringValidIdentifier( v )
end

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

local function isScalarType( theType )
	return theType == 'number' or theType == 'string' or theType == 'boolean'
end

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

local function isScalarValue( val )
	return isScalarType( type( val ) )
end

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

local function isSimpleValue( val )
	return isScalarValue( val )
end

---------------------------------------------------------------------------------
-- See chapter 12 in "Programming in Lua" for some of these ideas

local function serializeSimpleValue( v )
	
	local theType = type( v )
	
	if theType == 'string' then

		return string.format( '%q', v )

	elseif theType == 'number' or theType == 'boolean' then
		if v == 1 / 0 then -- inf (aka math.huge) the same regardless of numerator
			return "1 / 0"
		elseif v == -1 / 0 then -- -inf (aka -math.huge)
			return "-1 / 0"
		elseif v ~= v then -- NaN is the only value not equal to itself
			return "0 / 0"
		else
			return tostring( v )
		end
	end
	
	return nil
		
end

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

local function countAppearances( val, appearanceCounts )

	local theType = type( val )
	if theType == 'table' or theType == 'userdata' then

		appearanceCounts[ val ] = 1 + ( appearanceCounts[ val ] or 0 )
		
		-- Only walk into the table and account for its children the first time
		-- we see the table. (Prevents infinite recursion.)

		if theType == 'table' and appearanceCounts[ val ] == 1 then
			for k, v in pairs( val ) do
				countAppearances( v, appearanceCounts )
			end
		end

	end

end

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

local function isScalarOrSimpleObjectOrSingleton( val, appearanceCounts )
	
	return isSimpleValue( val ) or appearanceCounts[ val ] == 1
	
end

--------------------------------------------------------------------------------
--[[
	A table is "simple" if all of its subtables (and their subtables) and
	userdata are referenced only ONCE. Any multiple references kills the "simple"
	property, and prohibits the use of "constructor syntax" for writing tables
	out to strings. [tgogolin]

	Returns a bool if the passed in table is simple.
]]--

local function allChildrenAreSingleton( val, appearanceCounts, singletonTables )

	if isSimpleValue( val ) then
		return true
	end

	-- It's a table or userdata; have we already cached the answer to this question?

	local precomputed = singletonTables[ val ]
	if type( precomputed ) == 'boolean' then
		return precomputed
	end
	
	-- Not already computed before, so do the work now.
	
	if type( val ) == 'table' then

		local result = true

		for k, v in pairs( val ) do

			local ImOK = isScalarOrSimpleObjectOrSingleton( v, appearanceCounts )
			result = ImOK and allChildrenAreSingleton( v, appearanceCounts, singletonTables )

			if result == false then
				singletonTables[ val ] = false
				return false
			end

		end
		
		singletonTables[ val ] = true
		return true

	end
	
	return false
	
end


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

--@mark	-

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

local doSave
local saveSimple

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

local function topLevelSave( stream, val )

	local appearanceCounts = {}
	local singletonTables = {}
	local saved = {}
	countAppearances( val, appearanceCounts )
	doSave( stream, nil, val, saved, appearanceCounts, singletonTables )
	
end

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

function doSave( stream, name, value, saved, appearanceCounts, singletonTables )

	if name then
		table_insert( stream, name )
		table_insert( stream, ' = ' )
	end
	
	if isSimpleValue( value ) then

		table_insert( stream, serializeSimpleValue( value ) )
		table_insert( stream, '\n' )

	elseif type( value ) == 'table' then

		if saved[ value ] then
			table_insert( stream, saved[ value ] ) -- use its previous name
			table_insert( stream, '\n' )
		else

			saved[ value ] = name   		-- save name for next time
	
			if allChildrenAreSingleton( value, appearanceCounts, singletonTables ) then

				-- All of this table's children are singletons, but this table itself may be
				-- referred to again; remember it in the "saved" table so the next usage will
				-- be output as an assignment.
				
				saveSimple( stream, value )
				table_insert( stream, '\n' )

			else

				-- First time we've seen this table, so create a new one.
				
				table_insert( stream, '{}\n' )

				for k, v in pairs( value ) do	-- save its fields

					local fieldname
					if isValueValidIdentifier( k ) then
						fieldname = string.format( '%s.%s', name, k )
					else
						fieldname = string.format( '%s[ %s ]', name, serializeSimpleValue( k ) )
					end

					doSave( stream, fieldname, v, saved, appearanceCounts, singletonTables )

				end

			end

		end

	else
		error( "Cannot save a " .. type( value ) )
	end
	
end


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

--@mark	-

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

local function archiveTable( inTable )
	--( string table -- string )

	-- Write it out to a stream.

	os.setlocale( 'C', 'all' )
		-- [tgaul 2007-09-10]: Seems some code is changing the C locale out from
		-- under us.  This is a stopgap to make sure at least our table archiving
		-- code is immune to that nastiness.  We don't set it back to what it
		-- used to be, since our app assumes its C anyway.
	
	local stream = {}
	
	-- Stream the pure table out to a text stream.
	
	topLevelSave( stream, inTable )
	
	-- Get the stream results.
	
	return table.concat( stream )

end

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

local function writeKeyWithBrackets( stream, k )

	table_insert( stream, '[' )
	saveSimple( stream, k, 0 )
	table_insert( stream, ']' )

end

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

local function writeTableKey( stream, k )

	local kType = type( k )

	if isValueValidIdentifier( k ) then

		-- If the key is an identifier, use the simple "k = val" table syntax.

		table_insert( stream, k )

	elseif isSimpleValue( k ) then

		-- Key is not an identifier string, so use more cumbersome "[k] = val" syntax.

		writeKeyWithBrackets( stream, k )

	else

		error( "can't write key with type ".. kType ..": "..tostring( k ) )

	end

end


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

--@mark	-

---------------------------------------------------------------------------------
--[[
	This function is only good for serializing simple tables. It can handle
	nested tables. It can NOT handle tables that shares subtable references.
	It can NOT handle circular references. For those "simple" tables that don't
	have a complex topology though, the output of this function is very readable.
	It is also reproducible and reliably diffable, since the keys to all tables
	are sorted before outputting them. [tgogolin]
	
	All UserData should be removed from this hierarchy before we get here.
]]--

local function saveSimpleTable( stream, value, indent )

	assert( type( value ) == 'table' )

	indent = indent or 0

	table_insert( stream, '{\n' )
	indent = indent + 1
	
	-- Sort the table keys, then output the entries in the sorted order.
	
	local theSortedKeys = sortedKeys( value )
	
	-- First write out all of the array values that can be written without
	-- a key (i.e. 1..n consecutive).
	
	local numIntKeys = getNumSuccessiveIntKeys( value )
	
	-- Now write the other keys in sorted order (skipping the ones
	-- we've already written).

	for _, k in ipairs( theSortedKeys ) do
		
		table_insert( stream, indentString( indent ) )

		if type( k ) ~= 'number' or k > numIntKeys or k < 1  or k % 1 ~= 0 then
			writeTableKey( stream, k )
			table_insert( stream, ' = ' )
		end
		
		saveSimple( stream, value[ k ], indent )
		table_insert( stream, ',\n' )
		
	end
			
	indent = indent - 1
	table_insert( stream, indentString( indent ) )
	table_insert( stream, '}' )

end

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

saveSimple = function( stream, value, indent )

	if isSimpleValue( value ) then
		table_insert( stream, serializeSimpleValue( value ) )
	elseif type( value ) == 'table' then
		saveSimpleTable( stream, value, indent )
	else
		error( "Cannot save a " .. type( value ) )
	end

end

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

return archiveTable
