@global nsgraph_defined; if (nsgraph_defined == nil) { @local canonical, isstructptr, hasstructptr, cachehelper, cacheptrlist; @local type_debug; @global gentypegraph, printtypegraph_dot,typegraph_edge_iter; @global typegraph_node_iter,printtypegraph; nsgraph_defined = 1; @include type_debug = 0; // remove typedefs @define canonical(t) { if (istypedef(t)) return canonical(typedeftype(t)); return t; } // pointers to structures @define isstructptr(t) { if (isptr(t) && issu(canonical(subtype(t)))) return 1; return 0; } // matches pointers to structures or structures with pointers @define hasstructptr(t) { if (isstructptr(t)) { return 1; } else if (istypedef(t)) { return hasstructptr(typedeftype(t)); } else if (isarray(t)) { return hasstructptr(subtype(t)); } else if (issu(t)) { @local flds,i; flds = fields(t); for(i=0; i < length(flds); i++) { if (hasstructptr(fieldtype(vecref(flds, i)))) return 1; } } return 0; } @defloc types_with_ptrs(ns) { printf("The following types contain struct pointers:\n"); nsiter(ns, @lambda(x) { if (hasstructptr(x)) printf("\t%t\n", x); }); } // handle struct members, sometimes recursively @define cachehelper(t, cache) { // embedded structures if (issu(t)) { return cacheptrlist(t, cache); } else if (isstructptr(t)) return mkvec(1, canonical(subtype(t))); else if (isarray(t)) return cachehelper(subtype(t), cache); else if (istypedef(t)) return cachehelper(typedeftype(t), cache); if (type_debug) { printf("\t\tcachehelper(%t,...) returning NONE\n",t); } return mkvec(0); } // t must be an su type // go through all members of a struct, // look for pointers to other structs @define cacheptrlist(t, cache) { @local ptrtab, vals, cachedval,flds,i,ft,plist,j; ptrtab = mktab(); if (type_debug) { printf("cacheptrlist(%s, ...)\n", suetag(t)); } cachedval = tablook(cache, t); if (!isnil(cachedval)) { if (type_debug) { printf(" - DONE %s. Found cache of len %d\n", suetag(t), length(cachedval)); } return cachedval; } // didn't find in cache flds = fields(t); for (i=0; i < length(flds); i++) { ft = fieldtype(vecref(flds, i)); plist = cachehelper(ft, cache); for (j = 0; j < length(plist); j++) { tabinsert(ptrtab, vecref(plist, j), 1); } } vals = tabkeys(ptrtab); if (type_debug) { printf(" - DONE %s. Built cache of len %d\n", suetag(t), length(vals)); } tabinsert(cache, t, vals); return vals; } /* * a type graph is a representation of struct->struct * points-to relationships encoded in C struct types. * param: ns - the namespace * returns: a table representing the graph of structures and union * relationships in the given namespace */ @define gentypegraph(ns) { @local tg; tg = mktab(); nsiter(ns, @lambda(t) { if (issu(t)) { cacheptrlist(t, tg); } }); return tg; } /** * call fn(from_node, to_nodes) for all nodes in type graph * param: tg - the table representation of the type graph * param: fn - the function to run * returns: nil */ @define typegraph_node_iter(tg, fn) { @local entries, numentries, i; entries = tabenum(tg); numentries = length(entries) / 2; for (i = 0; i < numentries; i++) { fn(vecref(entries, i), vecref(entries, i + numentries)); } } /** * call fn(from_node, to_node) for all edges in type graph * param: tg - table representation of the type graph * param: fn - the function to be run * returns: nil */ @define typegraph_edge_iter(tg, fn) { @local edgefn; edgefn = @lambda(from, tolist) { @local j; for (j = 0; j < length(tolist); j++) { fn(from, vecref(tolist, j)); } }; typegraph_node_iter(tg, edgefn); } @define printtypegraph(ns) { @local tg, printfn; tg = gentypegraph(ns); printfn = @lambda(from, tolist) { @local j; if (0 == length(tolist)) return; printf("%16s: ", suetag(from)); for (j = 0; j < length(tolist); j++) { printf(" %s", suetag(vecref(tolist, j))); } printf("\n"); }; typegraph_node_iter(tg, printfn); } @define printtypegraph_dot(ns) { @local tg, printfn; tg = gentypegraph(ns); printfn = @lambda(from,to) { printf("\t%s -> %s;\n", suetag(from), suetag(to)); }; printf("digraph foo {\n"); typegraph_edge_iter(tg, printfn); printf("}\n"); } }