luatraverse: comparison luatraverse.lua

-:cafaa46928c8
+:1e2c945346ca
 -- countreferences and findallpaths
 --
 -- Alexandra Barros - 2006.03.15
 -------------------------------------------------------------------------------
-module("traverse", package.seeall)
+--luacheck: ignore 143/debug 113/getfenv
 local List = {}
 function List.new ()
 	return {first = 0, last = -1}
 	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
+local traverse, edge;
-function countreferences(value)
+local types = {};
-	local count = -1
+local get_metatable, get_environment, get_registry, get_locals, upvalues
-	local f = function(from, to, how, v)
-		if to == value then
-			count = count + 1
+-- select implementation of get_metatable depending on available API
-		end
+if type( debug ) == "table" and
-	end
+type( debug.getmetatable ) == "function" then
-	traverse({edge=f}, {count, f})
-	return count
+local get_mt = debug.getmetatable
+function get_metatable( val, enabled )
+if enabled then return get_mt( val ) end
+end
+elseif type( getmetatable ) == "function" then
+function get_metatable( val, enabled )
+if enabled then return getmetatable( val ) end
+end
+else
+function get_metatable() end
+end
+-- select implementation of get_environment depending on available API
+if type( debug ) == "table" and
+type( debug.getfenv ) == "function" then
+local get_fe = debug.getfenv
+function get_environment( val, n, enabled )
+if enabled and n == 1 then
+local uv = get_fe( val )
+return uv, uv ~= nil
+end
+return nil, false
+end
+elseif type( debug ) == "table" and
+type( debug.getuservalue ) == "function" then
+local get_uv = debug.getuservalue
+if _VERSION < "Lua 5.4" then
+local get_uv_noindex = get_uv
+function get_uv( val, n )
+if n == 1 then
+local uv = get_uv_noindex( val )
+return uv, uv ~= nil
+end
+return nil, false
+end
+end
+function get_environment( val, n, enabled )
+if enabled then
+-- getuservalue in Lua 5.2 throws on light userdata!
+local ok, res1, res2 = pcall( get_uv, val, n )
+if ok then return res1, res2 end
+return nil, false
+end
+end
+elseif type( getfenv ) == "function" then
+function get_environment( val, n, enabled )
+if enabled and n == 1 and type( val ) == "function" then
+local uv = getfenv( val )
+return uv, uv ~= nil
+end
+return nil, false
+end
+else
+function get_environment() return nil, false end
+end
+-- select implementation of get_registry
+if type( debug ) == "table" and
+type( debug.getregistry ) == "function" then
+get_registry = debug.getregistry
+else
+function get_registry() end
+end
+-- select implementation of get_locals
+-- locs = {
+--   {
+--      name = "example_function";
+--      func = <function>;
+--      [1] = { "local_name", <local value> };
+--      [2] = ...;
+--   };
+-- }
+if type( debug ) == "table" and
+type( debug.getinfo ) == "function" and
+type( debug.getlocal ) == "function" then
+local getinfo, getlocal = debug.getinfo, debug.getlocal
+local function getinfo_nothread( _, func, what )
+return getinfo( func, what )
+end
+local function getlocal_nothread( _, level, loc )
+return getlocal( level, loc )
+end
+function get_locals( thread, enabled )
+if enabled then
+local locs = {}
+local start = 1
+local gi, gl = getinfo, getlocal
+if not thread then
+gi, gl = getinfo_nothread, getlocal_nothread
+end
+local info, i = gi( thread, 0, "nf" ), 0
+while info do
+local t = { name = info.name, func = info.func }
+local j, n,v = 1, gl( thread, i, 1 )
+while n ~= nil do
+t[ j ] = { n, v }
+j = j + 1
+n,v = gl( thread, i, j )
+end
+i = i + 1
+locs[ i ] = t
+-- We skip the currently-executing traverse() function
+-- and anything that is only referenced through it
+if info.func == traverse then start = i+1 end
+info = gi( thread, i, "nf" )
+end
+return locs, start
+end
+end
+else
+function get_locals() end
+end
+-- select implementation of upvalues depending on available API
+local function dummy_iter() end
+if type( debug ) == "table" and
+type( debug.getupvalue ) == "function" then
+local get_up, uv_iter = debug.getupvalue
+if _VERSION == "Lua 5.1" then
+function uv_iter( state )
+local name, uv = get_up( state.value, state.n )
+state.n = state.n + 1
+return name, uv, nil
+end
+else -- Lua 5.2 (and later) mixes upvalues and environments
+local get_upid
+if type( debug.upvalueid ) == "function" then
+get_upid = debug.upvalueid
+end
+function uv_iter( state )
+local name, uv = get_up( state.value, state.n )
+state.n = state.n + 1
+if name == "_ENV" and not state.show_env then
+return uv_iter( state )
+end
+local id = nil
+if get_upid ~= nil and name ~= nil then
+id = get_upid( state.value, state.n - 1 )
+end
+return name, uv, id
+end
+end
+function upvalues( val, enabled, show_env )
+if enabled then
+return uv_iter, { value = val, n = 1, show_env = show_env }
+else
+return dummy_iter
+end
+end
+else
+function upvalues()
+return dummy_iter
+end
+end
+local function handle_metatable(env, obj)
+	local mtable = get_metatable(obj)
+	if mtable ~= nil then
+		edge(env, obj, mtable, "ismetatable", nil)
+	end
+end
+local function handle_environment(env, obj)
+	local n = 0
+	repeat
+		n = n + 1
+		local fenv, has_env = get_environment(obj, n)
+		if has_env and fenv ~= nil then
+			edge(env, obj, fenv, "environment", nil)
+		end
+	until not has_env
+end
+local function handle_locals(env, obj)
+	local stack = get_locals(obj);
+	if not stack then return; end
+	for _, frame in ipairs(stack) do
+		for local_entry in ipairs(frame) do
+			local local_name, local_value = local_entry[1], local_entry[2];
+			edge(env, nil, local_name, "isname", nil);
+			edge(env, nil, local_value, "local", local_name);
+		end
+	end
 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)
+function traverse(funcs, ignoreobjs, seenobjs)
-	-- The keys of the marked table are the objetcts (for example, table: 00442330).
+	-- The keys of the marked table are the objects (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}
+	local env = {marked = seenobjs or {}, 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")
+	-- traverse the registry
+	local registry = get_registry();
+	if registry ~= nil then
+		edge(env, nil, registry, "value", "REGISTRY");
+	end
 	-- traverses the active thread
 	-- inserts the local variables
 	-- interates over the function on the stack, starting from the one that
 	-- called traverse
+	handle_locals(env, nil);
-	for i=2, math.huge do
-		local info = debug.getinfo(i, "f")
+	while not List.isempty(env.list) do
-		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)
+		types[t](env, obj)
 	end
+end
-end
+function types.table(env, obj)
-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)
+	handle_metatable(env, obj)
-	if mtable then edge(env, obj, mtable, "ismetatable", nil) end
+end
-end
+function types.string(env, obj)
-function traversestring(env, obj)
 	local f = env.funcs.string
 	if f then f(obj) end
+end
-end
+function types.userdata(env, obj)
-function traverseuserdata(env, obj)
 	local f = env.funcs.userdata
 	if f then f(obj) end
-	local mtable = debug.getmetatable(obj)
+	handle_metatable(env, obj)
-	if mtable then edge(env, obj, mtable, "ismetatable", nil) end
+	handle_environment(env, obj)
+end
-	local fenv = debug.getfenv(obj)
-	if fenv then edge(env, obj, fenv, "environment", nil) end
+types["function"] = function (env, obj)
-end
-function traversefunction(env, obj)
 	local f = env.funcs.func
 	if f then f(obj) end
-	-- gets the upvalues
+	handle_environment(env, obj)
-	local i = 1
-	while true do
+	-- handle upvalues
-		local n, v = debug.getupvalue(obj, i)
+	for name, value in upvalues(obj, true, true) do
-		if not n then break end -- when there is no upvalues
+		edge(env, obj, name, "isname", nil)
-		edge(env, obj, n, "isname", nil)
+		edge(env, obj, value, "upvalue", name)
-		edge(env, obj, v, "upvalue", n)
+	end
-		i = i + 1
+end
-	end
+function types.thread(env, t)
-	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
+	handle_environment(env, t)
-		local info = debug.getinfo(t, i, "f")
+	handle_locals(env, t);
-		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;
+return {
+	traverse = traverse;
+};

Mercurial > luatraverse / file comparison

comparison: luatraverse.lua

luatraverse.lua