where.lua - traverses a lua state and finds a path to a given object or hex address.

where.lua

local _G, assert, newproxy, pairs, tostring, type = _G, assert, newproxy, pairs, tostring, type
local coroutine_create = coroutine.create
local debug_getfenv, debug_gethook, debug_getinfo, debug_getlocal, debug_getmetatable, debug_getregistry, debug_getupvalue, debug_upvalueid, debug_getuservalue = debug.getfenv, debug.gethook, debug.getinfo, debug.getlocal, debug.getmetatable, debug.getregistry, debug.getupvalue, debug.upvalueid, debug.getuservalue
local string_byte, string_format, string_gsub, string_match = string.byte, string.format, string.gsub, string.match
local where = {}

-- Auxiliary functions for finding the n'th key and n'th value in a table. Note
-- that the index may be invalidated even if the table is not modified, for
-- example if the table is weak
function where.nthkey(t, n)
	for k in pairs(t) do
		n = n - 1
		if n == 0 then
			return k
		end
	end
end
function where.nthvalue(t, n)
	for _, v in pairs(t) do
		n = n - 1
		if n == 0 then
			return v
		end
	end
end

-- Check equality of 2 objects or an object and its address
local function equal(a, b)
	if type(a) == "string" then
		return string_match(tostring(b), "%S*$") == string_match(a, "%S*$")
	else
		return b == a
	end
end

local seen

local searchobject

-- Traverse a table object
local function searchtable(v, obj, name)
	local n = 0
	for k, val in pairs(obj) do
		n = n + 1
		-- Try the key
		local path = searchobject(v, k, "where.nthkey(" .. name .."," .. n .. ")")
		if path then return path end
		-- Construct a nice-looking index name
		local newname = "where.nthvalue(" .. name .. "," .. n ..")"
		if type(k) == "string" then
			if string_match(k, "^[a-zA-Z_][a-zA-Z0-9_]*$") then
				newname = name .. "." .. k
			else
				k = string_gsub(k, "[\a\b\f\n\r\t\\\"]", {["\a"] = "\\a", ["\b"] = "\\b", ["\f"] = "\\f", ["\n"] = "\\n", ["\r"] = "\\r", ["\t"] = "\\t", ["\\"] = "\\\\", ["\""] = "\\\""})
				k = string_gsub(k, "[^ -~]", function(x) return string_format("\\%03d", string_byte(x)) end) 
				newname = name .. "[\"" .. k .. "\"]"
			end
		elseif type(k) == "number" or type(k) == "boolean" then
			newname = name .. "[" .. tostring(k) .. "]"
		end
		-- Try the value
		local path = searchobject(v, val, newname)
		if path then return path end
	end
	-- Try the metatable
	local mt = debug_getmetatable(obj)
	if mt then
		return searchobject(v, mt, "debug.getmetatable(" .. name .. ")")
	end
end

-- Traverse a function object
local function searchfunction(v, obj, name)
	local n = 0
	while true do
		n = n + 1
		local k, val = debug_getupvalue(obj, n)
		if not k then break end
		local path = searchobject(v, val, "select(2,debug.getupvalue(" .. name .. "," .. n .. "))")
		if path then return path end
		if debug_upvalueid then
			local path = searchobject(v, debug_upvalueid(obj, n), "debug.upvalueid(" .. name .. "," .. n .. ")")
			if path then return path end
		end
	end
	if debug_getfenv then
		return searchobject(v, debug_getfenv(obj), "debug.getfenv(" .. name ..")")
	end
end

-- Traverse a userdata object
local function searchuserdata(v, obj, name)
	if debug_getuservalue then
		local path = searchobject(v, debug_getuservalue(obj), "debug.getuservalue(" .. name .. ")")
		if path then return path end
	end
	local mt = debug_getmetatable(obj)
	if mt then
		return searchobject(v, mt, "debug.getmetatable(" .. name .. ")")
	end
end

-- Traverse a coroutine object or the main stack
local function searchstack(v, obj, name, stack_unwind)
	local path = searchobject(v, debug_gethook(obj), "debug.gethook(" .. (name or "") .. ")")
	if path then return path end
	local level = name and 0 or 3
	while true do
		if name then
			if not debug_getinfo(obj, level) then break end
		else
			if not debug_getinfo(level) then break end
		end
		local n = 0
		while true do
			n = n + 1
			local k, val
			if name then
				k, val = debug_getlocal(obj, level, n)
			else
				k, val = debug_getlocal(level, n)
			end
			if not k then break end
			local path = searchobject(v, val, "select(2,debug.getlocal(" .. (name and name .. "," or "") .. (name and level or level - 3 + stack_unwind) .. "," .. n .. "))")
			if path then return path end
		end
		if name then
			local path = searchobject(v, debug_getinfo(obj, level, "f").func , "debug.getinfo(" .. name .. "," .. level .. ",\"f\").func")
			if path then return path end
		else
			local path = searchobject(v, debug_getinfo(level, "f").func , "debug.getinfo(" .. level .. ",\"f\").func")
			if path then return path end
		end
		level = level + 1
	end
end

searchobject = function(v, obj, name)
	if type(obj) == "table" or type(obj) == "function" or type(obj) == "userdata" or type(obj) == "thread" then
		if equal(v, obj) then
			return name
		end
		if not seen[obj] then
			seen[obj] = true
			if type(obj) == "table" then
				return searchtable(v, obj, name)
			elseif type(obj) == "function" then
				return searchfunction(v, obj, name)
			elseif type(obj) == "userdata" then
				return searchuserdata(v, obj, name)
			elseif type(obj) == "thread" then
				return searchstack(v, obj, name)
			end
		end
	end
end

-- Find a lua-like code representing a way to obtain the object v, or the
-- object with the address v. In case stack backreferences (debug.getlocal) have
-- to be used, stack_unwind adjusts the level. Default is 1 and corresponds to
-- debug.getlocal being called at the same level as where.where
function where.where(v, stack_unwind)
	assert(type(v) == "string" or type(v) == "table" or type(v) == "function" or type(v) == "thread" or type(v) == "userdata", "Bad argument #1 to 'where.where' (table, function, thread, userdata, or address string expected, got " .. type(v) .. ")")
	stack_unwind = stack_unwind or 1
	assert(type(stack_unwind) == "number", "Bad argument #2 to 'where.where' (number expected, got " .. type(stack_unwind) .. ")")
	seen = {}
	-- Start by looking in the global table
	local path = searchobject(v, _G, "_G")
	if path then return path end
	-- Then check the main call stack
	path = searchstack(v, nil, nil, stack_unwind)
	if path then return path end
	-- The registry
	path = searchobject(v, debug_getregistry(), "debug.getregistry()")
	if path then return path end
	-- Metatables of built-in types
	local mt = debug_getmetatable(false)
	if mt then
		path = searchobject(v, mt, "debug.getmetatable(false)")
		if path then return path end
	end
	local mt = debug_getmetatable(0)
	if mt then
		path = searchobject(v, mt, "debug.getmetatable(0)")
		if path then return path end
	end
	local mt = debug_getmetatable""
	if mt then
		path = searchobject(v, mt, "debug.getmetatable\"\"")
		if path then return path end
	end
	local mt = debug_getmetatable(function()end)
	if mt then
		path = searchobject(v, mt, "debug.getmetatable(function()end)")
		if path then return path end
	end
	local mt = debug_getmetatable(coroutine_create(function()end))
	if mt then
		path = searchobject(v, mt, "debug.getmetatable(coroutine.create(function()end))")
		if path then return path end
	end
	return nil
end

return where