-------------------------------------------------------------------------------
-- This module implements a function that traverses all live objects.
-- You can implement your own function to pass as a parameter of traverse
-- and give you the information you want. As an example we have implemented
-- countreferences and findallpaths
--
-- Alexandra Barros - 2006.03.15
-------------------------------------------------------------------------------

module("traverse", package.seeall)

local List = {}

function List.new ()
	return {first = 0, last = -1}
end

function List.push (list, value)
	local last = list.last + 1
    list.last = last
    list[last] = value
end

function List.pop (list)	
    local first = list.first
    if first > list.last then error("list is empty") end
    local value = list[first]
    list[first] = nil        
    list.first = first + 1
    return value
end

function List.isempty (list)
	return list.first > list.last
end

-- Counts all references for a given object
function countreferences(value)
	local count = -1 
	local f = function(from, to, how, v)
		if to == value then 
			count = count + 1
		end 
	end	
	traverse({edge=f}, {count, f})
	return count
end

-- Main function
-- 'funcs' is a table that contains a funcation for every lua type and also the
-- function edge edge (traverseedge).
function traverse(funcs, ignoreobjs)

	-- The keys of the marked table are the objetcts (for example, table: 00442330).
	-- The value of each key is true if the object has been found and false
	-- otherwise.
	local env = {marked = {}, list=List.new(), funcs=funcs}
	
	if ignoreobjs then
		for i=1, #ignoreobjs do
			env.marked[ignoreobjs[i]] = true
		end
	end
	
	env.marked["traverse"] = true
	env.marked[traverse] = true
	
	-- marks and inserts on the list
	edge(env, nil, "_G", "isname", nil)
	edge(env, nil, _G, "value", "_G")

	-- traverses the active thread
	-- inserts the local variables
	-- interates over the function on the stack, starting from the one that
	-- called traverse
	
	for i=2, math.huge do
		local info = debug.getinfo(i, "f") 
		if not info then break end 
		for j=1, math.huge do
			local n, v = debug.getlocal(i, j)
			if not n then break end
		
			edge(env, nil, n, "isname", nil)
			edge(env, nil, v, "local", n)
		end
	end
	
	while not List.isempty(env.list) do	 		
	
		local obj = List.pop(env.list)
		local t = type(obj)
		_M["traverse" .. t](env, obj)
			
	end			
	
end

function traversetable(env, obj)
	
	local f = env.funcs.table
	if f then f(obj) end
	
	for key, value in pairs(obj) do	
		edge(env, obj, key, "key", nil)
		edge(env, obj, value, "value", key)
	end
	
	local mtable = debug.getmetatable(obj)
	if mtable then edge(env, obj, mtable, "ismetatable", nil) end

end
			
function traversestring(env, obj)
	local f = env.funcs.string
	if f then f(obj) end
	
end

function traverseuserdata(env, obj)
	local f = env.funcs.userdata
	if f then f(obj) end
	
	local mtable = debug.getmetatable(obj)
	if mtable then edge(env, obj, mtable, "ismetatable", nil) end
	
	local fenv = debug.getfenv(obj)
	if fenv then edge(env, obj, fenv, "environment", nil) end
	
end

function traversefunction(env, obj)
	local f = env.funcs.func
	if f then f(obj) end
	
	-- gets the upvalues
	local i = 1	
	while true do
		local n, v = debug.getupvalue(obj, i)
		if not n then break end -- when there is no upvalues
		edge(env, obj, n, "isname", nil)
		edge(env, obj, v, "upvalue", n)
		i = i + 1
	end
		
	local fenv = debug.getfenv(obj)
	edge(env, obj, fenv, "environment", nil)
	
end
			
function traversethread(env, t)
	local f = env.funcs.thread
	if f then f(t) end
	
	for i=1, math.huge do
		local info = debug.getinfo(t, i, "f") 
		if not info then break end 
		for j=1, math.huge do
			local n, v = debug.getlocal(t, i , j)
			if not n then break end
			print(n, v)
		
			edge(env, nil, n, "isname", nil)
			edge(env, nil, v, "local", n)
		end
	end
	
	local fenv = debug.getfenv(t)
	edge(env, t, fenv, "environment", nil)
	
end


-- 'how' is a string that identifies the content of 'to' and 'value':
-- 		if 'how' is "key", then 'to' is a key and 'name' is nil.
-- 		if 'how' is "value", then 'to' is an object and 'name' is the name of the
--		key.
function edge(env, from, to, how, name)
	
	local t = type(to)	
	
	if to and (t~="boolean") and (t~="number") and (t~="new") then
		-- If the destination object has not been found yet
		if not env.marked[to] then 
			env.marked[to] = true
			List.push(env.list, to) -- puts on the list to be traversed
		end
		
		local f = env.funcs.edge
		if f then f(from, to, how, name) end
		
	end	
end

return _M;