vcs.maemo.org Git - monky/blob - data/luatraverse.lua

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