Find all the paths to an object hopefully

paths.lua

local debug = debug
local coroutine = coroutine
local type = type
local next = next
local pairs = pairs
local package = package
local rawequal = rawequal

-- todo: lightuserdata?
local all_types = {
  1,
  true,
  "hello",
  function() return type end,
  coroutine.create(function() end)
}

local function maybe_visit_verbose(visited, to_visit, edges, parents, parent, edge, item)
  local typ = type(item)
  if (typ == "table" or typ == "thread" or typ == "function") and not visited[item] then
    to_visit[typ][item] = true
    if not edges[item] then
      edges[item] = edge
      parents[item] = parent
    end
  end
end

local function maybe_visit(visited, to_visit, edges, parents, parent, edge, item)
  local typ = type(item)
  if (typ == "table" or typ == "thread" or typ == "function") and not visited[item] then
    to_visit[typ][item] = true
  end
end

local function get_path_verbose(edges, parents, edge, parent)
  local ret,n = {edge},1
  while parent do
    n = n + 1
    ret[n] = parent
    n = n + 1
    ret[n] = edges[parent]
    parent = parents[parent]
  end
  for i=1,n/2 do
    ret[i], ret[n-i+1] = ret[n-i+1], ret[i]
  end
  return ret
end

local function get_path(edges, parents, edge, parent)
  return parent
end

local function real_find_paths(f, verbose)
  local maybe_visit, get_path = maybe_visit, get_path
  if verbose then
    maybe_visit = maybe_visit_verbose
    get_path = get_path_verbose
  end
  local needle = f()
  local to_visit = {table={},["function"]={},thread={}}
  local visited = {}
  local edge = {}
  local parent = {}
  local ret = {}
  local ret_set = {}
  local nr = 0
  visited[coroutine.running()] = true
  for i=0,#all_types do
    local mt = debug.getmetatable(all_types[i])
    maybe_visit(visited, to_visit, mt)
    if needle == mt then
      nr = nr + 1
      ret[nr] = "As the metatable of "..type(all_types[i])
    end
    if verbose and mt ~= nil then
      edge[mt] = "The metatable of "..type(all_types[i])
    end
  end
  roots = {_G, debug.getregistry()}
  if verbose then
    edge[_G] = "_G"
    edge[debug.getregistry()] = "debug.getregistry()"
  end
  for i=1,2 do
    local root = roots[i]
    if root == needle then
      nr = nr + 1
      ret[nr] = edge[root]
    end
  end
  for i=1,2 do
    if not visited[roots[i]] then to_visit.table[roots[i]] = true end
    while true do
      local item = next(to_visit.table)
      if item ~= nil then
        local mt = debug.getmetatable(item)
        maybe_visit(visited, to_visit, edge, parent, item, "metatable", mt)
        if mt == needle and not ret_set[item] then
          nr = nr + 1
          ret[nr] = get_path(edge, parent, "metatable", item)
          ret_set[item] = true
        end
        debug.setmetatable(item, nil)
        for k,v in pairs(item) do
          maybe_visit(visited, to_visit, edge, parent, item, "key", k)
          if verbose then
            maybe_visit(visited, to_visit, edge, parent, item, "value at slot "..tostring(k), v)
          else
            maybe_visit(visited, to_visit, edge, parent, item, "value", v)
          end
          if k == needle and not ret_set[item] then
            nr = nr + 1
            ret[nr] = get_path(edge, parent, "key", item)
            ret_set[item] = true
          end
          if v == needle and not ret_set[item] then
            nr = nr + 1
            if verbose then
              ret[nr] = get_path(edge, parent, "value at slot "..tostring(k), item)
            else
              ret[nr] = get_path(edge, parent, "value", item)
            end
            ret_set[item] = true
          end
        end
        debug.setmetatable(item, mt)
      elseif next(to_visit.thread) ~= nil then
        item = next(to_visit.thread)
        for qq=0,1e99 do
          local info = debug.getinfo(item, qq)
          if not info then break end
          for i=1,1e99 do
            local name,value = debug.getlocal(item, qq, i)
            if name == nil then break end
            maybe_visit(visited, to_visit, edge, parent, item, "local", value)
            if value == needle and not ret_set[item] then
              nr = nr + 1
              ret[nr] = get_path(edge, parent, "local", item)
              ret_set[item] = true
            end
          end
          for i=-1,-1e99,-1 do
            local name,value = debug.getlocal(item, qq, i)
            if name == nil then break end
            maybe_visit(visited, to_visit, edge, parent, item, "vararg", value)
            if value == needle and not ret_set[item] then
              nr = nr + 1
              ret[nr] = get_path(edge, parent, "vararg", item)
              ret_set[item] = true
            end
          end
        end
      elseif next(to_visit["function"]) ~= nil then
        item = next(to_visit["function"])
        for i=1,1e99 do
          local name,value = debug.getupvalue(item, i)
          if name == nil then break end
          maybe_visit(visited, to_visit, edge, parent, item, "upvalue", value)
          if value == needle and not ret_set[item] then
            nr = nr + 1
            ret[nr] = get_path(edge, parent, "upvalue", item)
            ret_set[item] = true
          end
        end
      else
        break
      end
      to_visit[type(item)][item] = nil
      visited[item] = true
    end
  end
  return ret
end

local function find_paths(f, verbose)
  local g = coroutine.wrap(real_find_paths)
  return g(f, verbose)
end

return {
  get_referrers = function(f) return find_paths(f, false) end,
  find_paths = function(f) return find_paths(f, true) end,
}

Usage:

paths=require"paths"
blorp = {}
do
  local x = blorp
  function f() return x end
end
for _,path in ipairs(paths.find_paths(function() return blorp end)) do
  print()
  for _,entry in ipairs(path) do
    print(tostring(entry))
  end
end

Please note that it takes a function that returns the thing you want to look for.

Over here that prints:

$ lua pathtest.lua

_G
table: 0x7fbf44504360
value at slot blorp

_G
table: 0x7fbf44504360
value at slot f
function: 0x7fbf4450a9b0
upvalue