--- /dev/null
+-------------------------------------------------------------------------------\r
+-- This module implements a function that traverses all live objects.\r
+-- You can implement your own function to pass as a parameter of traverse\r
+-- and give you the information you want. As an example we have implemented\r
+-- countreferences and findallpaths\r
+--\r
+-- Alexandra Barros - 2006.03.15\r
+-------------------------------------------------------------------------------\r
+\r
+module("traverse", package.seeall)\r
+\r
+local List = {}\r
+\r
+function List.new ()\r
+ return {first = 0, last = -1}\r
+end\r
+\r
+function List.push (list, value)\r
+ local last = list.last + 1\r
+ list.last = last\r
+ list[last] = value\r
+end\r
+\r
+function List.pop (list) \r
+ local first = list.first\r
+ if first > list.last then error("list is empty") end\r
+ local value = list[first]\r
+ list[first] = nil \r
+ list.first = first + 1\r
+ return value\r
+end\r
+\r
+function List.isempty (list)\r
+ return list.first > list.last\r
+end\r
+\r
+-- Counts all references for a given object\r
+function countreferences(value)\r
+ local count = -1 \r
+ local f = function(from, to, how, v)\r
+ if to == value then \r
+ count = count + 1\r
+ end \r
+ end \r
+ traverse({edge=f}, {count, f})\r
+ return count\r
+end\r
+\r
+-- Main function\r
+-- 'funcs' is a table that contains a funcation for every lua type and also the\r
+-- function edge edge (traverseedge).\r
+function traverse(funcs, ignoreobjs)\r
+\r
+ -- The keys of the marked table are the objetcts (for example, table: 00442330).\r
+ -- The value of each key is true if the object has been found and false\r
+ -- otherwise.\r
+ local env = {marked = {}, list=List.new(), funcs=funcs}\r
+ \r
+ if ignoreobjs then\r
+ for i=1, #ignoreobjs do\r
+ env.marked[ignoreobjs[i]] = true\r
+ end\r
+ end\r
+ \r
+ env.marked["traverse"] = true\r
+ env.marked[traverse] = true\r
+ \r
+ -- marks and inserts on the list\r
+ edge(env, nil, "_G", "isname", nil)\r
+ edge(env, nil, _G, "value", "_G")\r
+\r
+ -- traverses the active thread\r
+ -- inserts the local variables\r
+ -- interates over the function on the stack, starting from the one that\r
+ -- called traverse\r
+ \r
+ for i=2, math.huge do\r
+ local info = debug.getinfo(i, "f") \r
+ if not info then break end \r
+ for j=1, math.huge do\r
+ local n, v = debug.getlocal(i, j)\r
+ if not n then break end\r
+ \r
+ edge(env, nil, n, "isname", nil)\r
+ edge(env, nil, v, "local", n)\r
+ end\r
+ end\r
+ \r
+ while not List.isempty(env.list) do \r
+ \r
+ local obj = List.pop(env.list)\r
+ local t = type(obj)\r
+ _M["traverse" .. t](env, obj)\r
+ \r
+ end \r
+ \r
+end\r
+\r
+function traversetable(env, obj)\r
+ \r
+ local f = env.funcs.table\r
+ if f then f(obj) end\r
+ \r
+ for key, value in pairs(obj) do \r
+ edge(env, obj, key, "key", nil)\r
+ edge(env, obj, value, "value", key)\r
+ end\r
+ \r
+ local mtable = debug.getmetatable(obj)\r
+ if mtable then edge(env, obj, mtable, "ismetatable", nil) end\r
+\r
+end\r
+ \r
+function traversestring(env, obj)\r
+ local f = env.funcs.string\r
+ if f then f(obj) end\r
+ \r
+end\r
+\r
+function traverseuserdata(env, obj)\r
+ local f = env.funcs.userdata\r
+ if f then f(obj) end\r
+ \r
+ local mtable = debug.getmetatable(obj)\r
+ if mtable then edge(env, obj, mtable, "ismetatable", nil) end\r
+ \r
+ local fenv = debug.getfenv(obj)\r
+ if fenv then edge(env, obj, fenv, "environment", nil) end\r
+ \r
+end\r
+\r
+function traversefunction(env, obj)\r
+ local f = env.funcs.func\r
+ if f then f(obj) end\r
+ \r
+ -- gets the upvalues\r
+ local i = 1 \r
+ while true do\r
+ local n, v = debug.getupvalue(obj, i)\r
+ if not n then break end -- when there is no upvalues\r
+ edge(env, obj, n, "isname", nil)\r
+ edge(env, obj, v, "upvalue", n)\r
+ i = i + 1\r
+ end\r
+ \r
+ local fenv = debug.getfenv(obj)\r
+ edge(env, obj, fenv, "environment", nil)\r
+ \r
+end\r
+ \r
+function traversethread(env, t)\r
+ local f = env.funcs.thread\r
+ if f then f(t) end\r
+ \r
+ for i=1, math.huge do\r
+ local info = debug.getinfo(t, i, "f") \r
+ if not info then break end \r
+ for j=1, math.huge do\r
+ local n, v = debug.getlocal(t, i , j)\r
+ if not n then break end\r
+ print(n, v)\r
+ \r
+ edge(env, nil, n, "isname", nil)\r
+ edge(env, nil, v, "local", n)\r
+ end\r
+ end\r
+ \r
+ local fenv = debug.getfenv(t)\r
+ edge(env, t, fenv, "environment", nil)\r
+ \r
+end\r
+\r
+\r
+-- 'how' is a string that identifies the content of 'to' and 'value':\r
+-- if 'how' is "key", then 'to' is a key and 'name' is nil.\r
+-- if 'how' is "value", then 'to' is an object and 'name' is the name of the\r
+-- key.\r
+function edge(env, from, to, how, name)\r
+ \r
+ local t = type(to) \r
+ \r
+ if to and (t~="boolean") and (t~="number") and (t~="new") then\r
+ -- If the destination object has not been found yet\r
+ if not env.marked[to] then \r
+ env.marked[to] = true\r
+ List.push(env.list, to) -- puts on the list to be traversed\r
+ end\r
+ \r
+ local f = env.funcs.edge\r
+ if f then f(from, to, how, name) end\r
+ \r
+ end \r
+end\r
+\r
+return _M;\r