# HG changeset patch
# User Matthew Wild <mwild1@gmail.com>
# Date 1600860577 -3600
# Node ID 1e2c945346ca32bba7074a503f50c8c9ee9b831c
# Parent  cafaa46928c85d4040b3e4c68daf47b5c38098e2
Major update and refactor to support Lua 5.1, 5.2, 5.3 and 5.4.

Many thanks to Philipp Janda and his lua-microscope project from
which most of the compatibility code was borrowed.

diff -r cafaa46928c8 -r 1e2c945346ca examples/luastate.lua
--- a/examples/luastate.lua	Wed Sep 25 15:00:13 2013 +0100
+++ b/examples/luastate.lua	Wed Sep 23 12:29:37 2020 +0100
@@ -18,7 +18,7 @@
 -- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 -- THE SOFTWARE.
 
-local ltraverse = require"traverse"
+local ltraverse = require"luatraverse"
 local sformat = string.format
 local have_getsize = false
 local getsize = function()
diff -r cafaa46928c8 -r 1e2c945346ca luatraverse.lua
--- a/luatraverse.lua	Wed Sep 25 15:00:13 2013 +0100
+++ b/luatraverse.lua	Wed Sep 23 12:29:37 2020 +0100
@@ -7,7 +7,7 @@
 -- Alexandra Barros - 2006.03.15
 -------------------------------------------------------------------------------
 
-module("traverse", package.seeall)
+--luacheck: ignore 143/debug 113/getfenv
 
 local List = {}
 
@@ -21,11 +21,11 @@
     list[last] = value
 end
 
-function List.pop (list)	
+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] = nil
     list.first = first + 1
     return value
 end
@@ -34,140 +34,323 @@
 	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
+local traverse, edge;
+local types = {};
+local get_metatable, get_environment, get_registry, get_locals, upvalues
+
+
+-- select implementation of get_metatable depending on available API
+if type( debug ) == "table" and
+   type( debug.getmetatable ) == "function" then
+
+  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
-	
-	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	 		
-	
+	handle_locals(env, nil);
+
+	while not List.isempty(env.list) do
+
 		local obj = List.pop(env.list)
 		local t = type(obj)
-		_M["traverse" .. t](env, obj)
-			
-	end			
-	
+		types[t](env, obj)
+
+	end
 end
 
-function traversetable(env, obj)
-	
+function types.table(env, obj)
 	local f = env.funcs.table
 	if f then f(obj) end
-	
-	for key, value in pairs(obj) do	
+
+	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
 
+	handle_metatable(env, obj)
 end
-			
-function traversestring(env, obj)
+
+function types.string(env, obj)
 	local f = env.funcs.string
 	if f then f(obj) end
-	
 end
 
-function traverseuserdata(env, obj)
+function types.userdata(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
-	
+
+	handle_metatable(env, obj)
+	handle_environment(env, obj)
 end
 
-function traversefunction(env, obj)
+types["function"] = function (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
+
+	handle_environment(env, obj)
+
+	-- handle upvalues
+	for name, value in upvalues(obj, true, true) do
+		edge(env, obj, name, "isname", nil)
+		edge(env, obj, value, "upvalue", name)
 	end
-		
-	local fenv = debug.getfenv(obj)
-	edge(env, obj, fenv, "environment", nil)
-	
 end
-			
-function traversethread(env, t)
+
+function types.thread(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)
-	
+
+	handle_environment(env, t)
+	handle_locals(env, t);
+
 end
 
 
@@ -176,20 +359,22 @@
 -- 		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)	
-	
+
+	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 
+		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
 end
 
-return _M;
+return {
+	traverse = traverse;
+};