Mercurial > luatraverse / file comparison
comparison: luatraverse.lua
luatraverse.lua
- changeset 0
- 907015aa722f
- child 1
- 036168493972
equal
deleted
inserted
replaced
| -1:000000000000 | 0:907015aa722f |
|---|---|
| 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("gc", 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 -- Prints all paths to an object | |
| 50 function findallpaths(obj) | |
| 51 | |
| 52 local comefrom = {} | |
| 53 local f = function(from, to, how, value) | |
| 54 if not comefrom[to] then comefrom[to] = {} end | |
| 55 table.insert(comefrom[to], 1, {f = from, h = how, v=value}) | |
| 56 end | |
| 57 | |
| 58 traverse({edge=f}, {comefrom, f}) | |
| 59 | |
| 60 | |
| 61 local function printpath(to) | |
| 62 if not to or comefrom[to].visited or to == _G then | |
| 63 print("-----") | |
| 64 return | |
| 65 end | |
| 66 comefrom[to].visited = true | |
| 67 for i=1, #comefrom[to] do | |
| 68 local tfrom = comefrom[to][i].f | |
| 69 print("from: ", tfrom, "\nhow:", comefrom[to][i].h, | |
| 70 "\nvalue:", comefrom[to][i].v) | |
| 71 printpath(tfrom) | |
| 72 end | |
| 73 end | |
| 74 | |
| 75 printpath(obj) | |
| 76 | |
| 77 end | |
| 78 | |
| 79 -- Main function | |
| 80 -- 'funcs' is a table that contains a funcation for every lua type and also the | |
| 81 -- function edge edge (traverseedge). | |
| 82 function traverse(funcs, ignoreobjs) | |
| 83 | |
| 84 -- The keys of the marked table are the objetcts (for example, table: 00442330). | |
| 85 -- The value of each key is true if the object has been found and false | |
| 86 -- otherwise. | |
| 87 local env = {marked = {}, list=List.new(), funcs=funcs} | |
| 88 | |
| 89 if ignoreobjs then | |
| 90 for i=1, #ignoreobjs do | |
| 91 env.marked[ignoreobjs[i]] = true | |
| 92 end | |
| 93 end | |
| 94 | |
| 95 env.marked["gc"] = true | |
| 96 env.marked[gc] = true | |
| 97 | |
| 98 -- marks and inserts on the list | |
| 99 edge(env, nil, "_G", "isname", nil) | |
| 100 edge(env, nil, _G, "key", "_G") | |
| 101 | |
| 102 -- traverses the active thread | |
| 103 -- inserts the local variables | |
| 104 -- interates over the function on the stack, starting from the one that | |
| 105 -- called traverse | |
| 106 for i=2, math.huge do | |
| 107 local info = debug.getinfo(i, "f") | |
| 108 if not info then break end | |
| 109 for j=1, math.huge do | |
| 110 local n, v = debug.getlocal(i, j) | |
| 111 if not n then break end | |
| 112 | |
| 113 edge(env, nil, n, "isname", nil) | |
| 114 edge(env, nil, v, "local", n) | |
| 115 end | |
| 116 end | |
| 117 | |
| 118 while not List.isempty(env.list) do | |
| 119 | |
| 120 local obj = List.pop(env.list) | |
| 121 local t = type(obj) | |
| 122 gc["traverse" .. t](env, obj) | |
| 123 | |
| 124 end | |
| 125 | |
| 126 end | |
| 127 | |
| 128 function traversetable(env, obj) | |
| 129 | |
| 130 local f = env.funcs.table | |
| 131 if f then f(obj) end | |
| 132 | |
| 133 for key, value in pairs(obj) do | |
| 134 edge(env, obj, key, "iskey", nil) | |
| 135 edge(env, obj, value, "key", key) | |
| 136 end | |
| 137 | |
| 138 local mtable = debug.getmetatable(obj) | |
| 139 if mtable then edge(env, obj, mtable, "ismetatable", nil) end | |
| 140 | |
| 141 end | |
| 142 | |
| 143 function traversestring(env, obj) | |
| 144 local f = env.funcs.string | |
| 145 if f then f(obj) end | |
| 146 | |
| 147 end | |
| 148 | |
| 149 function traverseuserdata(env, obj) | |
| 150 local f = env.funcs.userdata | |
| 151 if f then f(obj) end | |
| 152 | |
| 153 local mtable = debug.getmetatable(obj) | |
| 154 if mtable then edge(env, obj, mtable, "ismetatable", nil) end | |
| 155 | |
| 156 local fenv = debug.getfenv(obj) | |
| 157 if fenv then edge(env, obj, fenv, "environment", nil) end | |
| 158 | |
| 159 end | |
| 160 | |
| 161 function traversefunction(env, obj) | |
| 162 local f = env.funcs.func | |
| 163 if f then f(obj) end | |
| 164 | |
| 165 -- gets the upvalues | |
| 166 local i = 1 | |
| 167 while true do | |
| 168 local n, v = debug.getupvalue(obj, i) | |
| 169 if not n then break end -- when there is no upvalues | |
| 170 edge(env, obj, n, "isname", nil) | |
| 171 edge(env, obj, v, "upvalue", n) | |
| 172 i = i + 1 | |
| 173 end | |
| 174 | |
| 175 local fenv = debug.getfenv(obj) | |
| 176 edge(env, obj, fenv, "enviroment", nil) | |
| 177 | |
| 178 end | |
| 179 | |
| 180 function traversethread(env, t) | |
| 181 local f = env.funcs.thread | |
| 182 if f then f(t) end | |
| 183 | |
| 184 for i=1, math.huge do | |
| 185 local info = debug.getinfo(t, i, "f") | |
| 186 if not info then break end | |
| 187 for j=1, math.huge do | |
| 188 local n, v = debug.getlocal(t, i , j) | |
| 189 if not n then break end | |
| 190 print(n, v) | |
| 191 | |
| 192 edge(env, nil, n, "isname", nil) | |
| 193 edge(env, nil, v, "local", n) | |
| 194 end | |
| 195 end | |
| 196 | |
| 197 local fenv = debug.getfenv(t) | |
| 198 edge(env, t, fenv, "enviroment", nil) | |
| 199 | |
| 200 end | |
| 201 | |
| 202 | |
| 203 -- 'how' is a string that identifies the content of 'to' and 'value': | |
| 204 -- if 'how' is "iskey", then 'to' é is a key and 'value' is nil. | |
| 205 -- if 'how' is "key", then 'to' is an object and 'value' is the name of the | |
| 206 -- key. | |
| 207 function edge(env, from, to, how, value) | |
| 208 | |
| 209 local t = type(to) | |
| 210 | |
| 211 if to and (t~="boolean") and (t~="number") and (t~="new") then | |
| 212 -- If the destination object has not been found yet | |
| 213 if not env.marked[to] then | |
| 214 env.marked[to] = true | |
| 215 List.push(env.list, to) -- puts on the list to be traversed | |
| 216 end | |
| 217 | |
| 218 local f = env.funcs.edge | |
| 219 if f then f(from, to, how, value) end | |
| 220 | |
| 221 end | |
| 222 | |
| 223 end |
