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

WFFindSymbolInUniverse.lua

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

ADOBE CONFIDENTIAL
------------------
Copyright 2009 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 WFFindSymbolInUniverse = {}

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

local function makeQueue()
	
	local i, o = 0, 0
	
	return {
		pushBack = function( self, x )
			o = o + 1
			self[ o ] = x
		end,
		isEmpty = function( self )
			return o == 0
		end,
		popFront = function( self )
			if o > 0 then
				i = i + 1
				local result = self[ i ]
				self[ i ] = nil
				if i == o then
					i,o = 0,0
				end
				return result
			end
		end,
	}
	
end

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

local function default_pToString( val )
	
	local success, message = pcall( tostring, val )
	
	if not success then
		message = 'noname_' .. type( val )
	end

	return message

end

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

local function isContainer( val )
	local valType = type( val )
	return (valType == "function") or (valType == "table") or (valType == "userdata") or (valType == "thread")
end

local function addContainerToList( queue, val, identifier, optTraverse, depth )
	if val == nil then
		return
	end
	
	identifier = identifier .. "/"
	assert( type( depth ) == 'number' )
	if optTraverse then
		if not optTraverse( val, depth ) then
			return
		end
	end
	queue:pushBack( { container = val, identifier = identifier, depth = depth } )
end

--------------------------------------------------------------------------------
-- This is the function that does all the work.
-- queue: the queue of containers we have found, but not yet examined.
-- val: the value we are trying to find somewhere in the universe
-- searched: a table of conainers we have already seen (so we don't infinitely recurse)
-- results: the table of search "hits" we build up as we search
local function process (queue, context, searched, optTraverse )
	
	local callback0 = context.callback
	local includeWeaks = context.includeWeaks
	local done = false
	
	local pToString = context.pToString or default_pToString
	local nameForVal = context.nameForVal or default_pToString
	
	local callback = function( ... )
		if callback0( ... ) then
			done = true
		end
	end
	
	while not done and not queue:isEmpty() do
	
		local queueEntry = queue:popFront()
		local container = queueEntry.container
		local identifier = queueEntry.identifier
		local depth = ( queueEntry.depth or 0 ) + 1
		
		local containerType = type( container )
				
		-- If we've already seen this container, bail now.
		-- Otherwise we might recurse indefinitely.
		local prevSeen = container == nil or searched[ container ]
		if not prevSeen then
			-- remember this container, so we never search it again
			searched[ container ] = true
			
			if containerType == "function" then
		
				-- examine all the upvalues of this function
				local i = 1
				while true do
					local n, val = debug.getupvalue( container, i )
					if not n then break end
					
					local name =  "upval_" .. nameForVal(n)
					callback( identifier, name, val )
					
					if isContainer( val ) then
						addContainerToList( queue, val, identifier .. name, optTraverse, depth )
					end
					
					i = i + 1
				end
				local fenv = debug.getfenv( container )
				if fenv then
					addContainerToList( queue, fenv, identifier .. "fenv" .. nameForVal( fenv ), optTraverse, depth )
				end

			end
			
			if containerType == "thread" then
				
				local level = 0
				while true do
					local funcInfo = debug.getinfo( container, level )
					if not funcInfo then break end
					
					addContainerToList( queue, funcInfo.func, identifier .. "func_" .. nameForVal( funcInfo.func ), optTraverse, depth )
					
					-- examine all the locals of this thread
					local i = 1
					while true do
						local n, val = debug.getlocal( container, level, i )
						if not n then break end
						
						local name =  "local_" .. nameForVal(n)
						callback( identifier, name, val )
						
						if isContainer( val ) then
							addContainerToList( queue, val, identifier .. name, optTraverse, depth )
						end
						
						i = i + 1
					end
					local fenv = debug.getfenv( container )
					if fenv then
						addContainerToList( queue, fenv, identifier .. "fenv" .. nameForVal( fenv ), optTraverse, depth )
					end
					
					level = level + 1
				end

			end
			
			if containerType == "userdata" then
				local fenv = debug.getfenv( container )
				if fenv then
					addContainerToList( queue, fenv, identifier .. "fenv_" .. nameForVal( fenv ), optTraverse, depth )
				end
				local mt = debug.getmetatable( container )
				if mt then
					addContainerToList( queue, mt, identifier .. "metatable_" .. nameForVal( mt ), optTraverse, depth )
				end
			end
			
			if containerType == "table" then

				local mt = debug.getmetatable( container )
				local weakKeys, weakValues
				local tblType = "KV"

				if mt then
					if isContainer( mt ) then
						
						local mode = mt.__mode
						if mode == 'k' then
							tblType = "kV"
							weakKeys = true
						elseif mode == 'kv' then
							tblType = "kv"
							weakKeys = true
							weakValues = true
						elseif mode == 'v' then
							tblType = "Kv"
							weakValues = true
						elseif mode == nil then
							tblType = "KV"
						else
							tblType = "WTF_" .. tostring( mode )
						end

						addContainerToList( queue, mt, identifier .. "metatable_" .. nameForVal( mt ), optTraverse, depth )

					end
				end
				
				local keys = {}
				for k in pairs( container ) do
					table.insert( keys, { pToString( k ), k } )
				end
				table.sort( keys, function( a, b )
					return a[ 1 ] < b[ 1 ]
				end )
				for _, zz in ipairs( keys ) do
					local k = zz[ 2 ]
					local val = container[ k ]
					if includeWeaks or not weakKeys then
						callback( identifier, tblType .. "_key", k, weakValues, val )
					
						if isContainer( k ) then
							local nuPath = identifier .. tblType .. "_key_" .. nameForVal(k)
							addContainerToList( queue, k, nuPath, optTraverse, depth )
						end
					end

					if includeWeaks or not weakValues then
						callback( identifier, tblType  .. "_value_" .. nameForVal(k), val, weakKeys, k )

						if isContainer( val ) then
							local nuPath = identifier .. tblType .. "_value_" .. nameForVal(k)
							addContainerToList( queue, val, nuPath, optTraverse, depth )
						end
					end
				end
			end
		end
	end  -- while not queue:isEmpty() do
			
end

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

function WFFindSymbolInUniverse.iterateUniverse( callback, moreContainers, options )
	
	local context = {
		callback = callback,
	}
	
	for k, v in pairs( options or {} ) do
		context[ k ] = v
	end
	
	local queue = makeQueue()

--	local namespaces = {}
--	for k in pairs( import 'AgToolkitLoader'.exportedNamespaces ) do
--		namespaces[ k ] = import 'AgNamespace'.importExisting( k )
--	end
	
	for k, v in pairs( moreContainers or {} ) do
		addContainerToList( queue, v, k, nil, 1 )
	end

--	addContainerToList( queue, namespaces, "namespaces", nil, 1 )
	addContainerToList( queue, _G, "_G", nil, 1 )
	addContainerToList( queue, debug.getregistry(), "registry", nil, 1 )

	local searched = {}
	
	local searchKey = coroutine.running() or "< root lua state >"
	searched[ searchKey ] = true
	
	process( queue, context, searched )

end

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

local valueTypes = {
	[ 'string' ] = true,
	[ 'number' ] = true,
	[ 'boolean' ] = true,
	[ 'nil' ] = true,
}

function WFFindSymbolInUniverse.findObjectInContainer( object, container, optIncludeWeaklyReferencedValues, optDepthLimit )

	optDepthLimit = optDepthLimit or 2
	
	local objType = type( object )
	if valueTypes[ objType ] then
		return false
	end

	local queue = makeQueue()
	local searched = {}
	
	local traverse = function( obj, depth )
		
		-- for the initial go around, only scan simple
		-- tables that arent _G.  _B and namespaces
		-- all have metatables, so this test skips them.
		-- also don't go further than 2 levels deep.
		-- Depth limiting is a hack to avoid accidentally traversing
		-- into the afterDelay function's delayFn.  delayFns
		-- can reasonably hold upvalues that from our
		-- leak checking perspective appear suspicious.
		
		if depth > 2 then
			return false
		end
		
		local objType = type( obj )
		if objType == 'table' then
			if debug.getmetatable( obj ) then
				return false
			end
			return obj ~= _G
		end
		return objType == 'function'
		
	end
	
	local paths = {}
	
	local function callback( identifier, name, val )
		if val == object then
			table.insert( paths, string.format( "%s%s", identifier, name ) )
		end
	end
	
	local context = {
		callback = callback,
		includeWeaks = optIncludeWeaklyReferencedValues,
	}
	addContainerToList( queue, container, type( container ), nil, 1 )

	process( queue, context, searched, traverse )
	
	if #paths > 0 then
		return table.concat( paths, ", " )
	end
	
end

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

function WFFindSymbolInUniverse.findContainers( x )

	local results = {}
	
	WFFindSymbolInUniverse.iterateUniverse( function( path, name, value )
		
		if x == value then
			table.insert( results, {
				path = path,
				name = name,
			} )
		end
		
	end )
	
	return results
	
end

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

return WFFindSymbolInUniverse
