git.maemo.org Git - monky/blob - lua_scripts/luatraverse.lua

   1 -------------------------------------------------------------------------------\r
   2 -- This module implements a function that traverses all live objects.\r
   3 -- You can implement your own function to pass as a parameter of traverse\r
   4 -- and give you the information you want. As an example we have implemented\r
   5 -- countreferences and findallpaths\r
   6 --\r
   7 -- Alexandra Barros - 2006.03.15\r
   8 -------------------------------------------------------------------------------\r
   9 \r
  10 module("traverse", package.seeall)\r
  11 \r
  12 local List = {}\r
  13 \r
  14 function List.new ()\r
  15         return {first = 0, last = -1}\r
  16 end\r
  17 \r
  18 function List.push (list, value)\r
  19         local last = list.last + 1\r
  20     list.last = last\r
  21     list[last] = value\r
  22 end\r
  23 \r
  24 function List.pop (list)        \r
  25     local first = list.first\r
  26     if first > list.last then error("list is empty") end\r
  27     local value = list[first]\r
  28     list[first] = nil        \r
  29     list.first = first + 1\r
  30     return value\r
  31 end\r
  32 \r
  33 function List.isempty (list)\r
  34         return list.first > list.last\r
  35 end\r
  36 \r
  37 -- Counts all references for a given object\r
  38 function countreferences(value)\r
  39         local count = -1 \r
  40         local f = function(from, to, how, v)\r
  41                 if to == value then \r
  42                         count = count + 1\r
  43                 end \r
  44         end     \r
  45         traverse({edge=f}, {count, f})\r
  46         return count\r
  47 end\r
  48 \r
  49 -- Main function\r
  50 -- 'funcs' is a table that contains a funcation for every lua type and also the\r
  51 -- function edge edge (traverseedge).\r
  52 function traverse(funcs, ignoreobjs)\r
  53 \r
  54         -- The keys of the marked table are the objetcts (for example, table: 00442330).\r
  55         -- The value of each key is true if the object has been found and false\r
  56         -- otherwise.\r
  57         local env = {marked = {}, list=List.new(), funcs=funcs}\r
  58         \r
  59         if ignoreobjs then\r
  60                 for i=1, #ignoreobjs do\r
  61                         env.marked[ignoreobjs[i]] = true\r
  62                 end\r
  63         end\r
  64         \r
  65         env.marked["traverse"] = true\r
  66         env.marked[traverse] = true\r
  67         \r
  68         -- marks and inserts on the list\r
  69         edge(env, nil, "_G", "isname", nil)\r
  70         edge(env, nil, _G, "value", "_G")\r
  71 \r
  72         -- traverses the active thread\r
  73         -- inserts the local variables\r
  74         -- interates over the function on the stack, starting from the one that\r
  75         -- called traverse\r
  76         \r
  77         for i=2, math.huge do\r
  78                 local info = debug.getinfo(i, "f") \r
  79                 if not info then break end \r
  80                 for j=1, math.huge do\r
  81                         local n, v = debug.getlocal(i, j)\r
  82                         if not n then break end\r
  83                 \r
  84                         edge(env, nil, n, "isname", nil)\r
  85                         edge(env, nil, v, "local", n)\r
  86                 end\r
  87         end\r
  88         \r
  89         while not List.isempty(env.list) do                     \r
  90         \r
  91                 local obj = List.pop(env.list)\r
  92                 local t = type(obj)\r
  93                 _M["traverse" .. t](env, obj)\r
  94                         \r
  95         end                     \r
  96         \r
  97 end\r
  98 \r
  99 function traversetable(env, obj)\r
 100         \r
 101         local f = env.funcs.table\r
 102         if f then f(obj) end\r
 103         \r
 104         for key, value in pairs(obj) do \r
 105                 edge(env, obj, key, "key", nil)\r
 106                 edge(env, obj, value, "value", key)\r
 107         end\r
 108         \r
 109         local mtable = debug.getmetatable(obj)\r
 110         if mtable then edge(env, obj, mtable, "ismetatable", nil) end\r
 111 \r
 112 end\r
 113                         \r
 114 function traversestring(env, obj)\r
 115         local f = env.funcs.string\r
 116         if f then f(obj) end\r
 117         \r
 118 end\r
 119 \r
 120 function traverseuserdata(env, obj)\r
 121         local f = env.funcs.userdata\r
 122         if f then f(obj) end\r
 123         \r
 124         local mtable = debug.getmetatable(obj)\r
 125         if mtable then edge(env, obj, mtable, "ismetatable", nil) end\r
 126         \r
 127         local fenv = debug.getfenv(obj)\r
 128         if fenv then edge(env, obj, fenv, "environment", nil) end\r
 129         \r
 130 end\r
 131 \r
 132 function traversefunction(env, obj)\r
 133         local f = env.funcs.func\r
 134         if f then f(obj) end\r
 135         \r
 136         -- gets the upvalues\r
 137         local i = 1     \r
 138         while true do\r
 139                 local n, v = debug.getupvalue(obj, i)\r
 140                 if not n then break end -- when there is no upvalues\r
 141                 edge(env, obj, n, "isname", nil)\r
 142                 edge(env, obj, v, "upvalue", n)\r
 143                 i = i + 1\r
 144         end\r
 145                 \r
 146         local fenv = debug.getfenv(obj)\r
 147         edge(env, obj, fenv, "environment", nil)\r
 148         \r
 149 end\r
 150                         \r
 151 function traversethread(env, t)\r
 152         local f = env.funcs.thread\r
 153         if f then f(t) end\r
 154         \r
 155         for i=1, math.huge do\r
 156                 local info = debug.getinfo(t, i, "f") \r
 157                 if not info then break end \r
 158                 for j=1, math.huge do\r
 159                         local n, v = debug.getlocal(t, i , j)\r
 160                         if not n then break end\r
 161                         print(n, v)\r
 162                 \r
 163                         edge(env, nil, n, "isname", nil)\r
 164                         edge(env, nil, v, "local", n)\r
 165                 end\r
 166         end\r
 167         \r
 168         local fenv = debug.getfenv(t)\r
 169         edge(env, t, fenv, "environment", nil)\r
 170         \r
 171 end\r
 172 \r
 173 \r
 174 -- 'how' is a string that identifies the content of 'to' and 'value':\r
 175 --              if 'how' is "key", then 'to' is a key and 'name' is nil.\r
 176 --              if 'how' is "value", then 'to' is an object and 'name' is the name of the\r
 177 --              key.\r
 178 function edge(env, from, to, how, name)\r
 179         \r
 180         local t = type(to)      \r
 181         \r
 182         if to and (t~="boolean") and (t~="number") and (t~="new") then\r
 183                 -- If the destination object has not been found yet\r
 184                 if not env.marked[to] then \r
 185                         env.marked[to] = true\r
 186                         List.push(env.list, to) -- puts on the list to be traversed\r
 187                 end\r
 188                 \r
 189                 local f = env.funcs.edge\r
 190                 if f then f(from, to, how, name) end\r
 191                 \r
 192         end     \r
 193 end\r
 194 \r
 195 return _M;\r