Robust/src/Analysis/CallGraph/CallGraph.java

   1 package Analysis.CallGraph;
   2 import IR.State;
   3 import IR.Flat.FlatMethod;
   4 import IR.Flat.FlatNode;
   5 import IR.Flat.FlatCall;
   6 import IR.Flat.FKind;
   7 import IR.Descriptor;
   8 import IR.ClassDescriptor;
   9 import IR.MethodDescriptor;
  10 import IR.TaskDescriptor;
  11 import IR.TypeDescriptor;
  12 import java.util.*;
  13 import java.io.*;
  14
  15 public class CallGraph {
  16     private State state;
  17
  18     // MethodDescriptor maps to HashSet<MethodDescriptor>
  19     private Hashtable mapVirtual2ImplementationSet;
  20
  21     // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
  22     private Hashtable mapCaller2CalleeSet;
  23
  24     // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
  25     private Hashtable mapCallee2CallerSet;
  26
  27     public CallGraph(State state) {
  28         this.state=state;
  29         mapVirtual2ImplementationSet = new Hashtable();
  30         mapCaller2CalleeSet          = new Hashtable();
  31         mapCallee2CallerSet          = new Hashtable();
  32         buildVirtualMap();
  33         buildGraph();
  34     }
  35
  36     // this method returns the set of Descriptors
  37     // (MethodDescriptors and/or TaskDescriptors)
  38     //  that call the given method
  39     public Set getCallerSet( MethodDescriptor md ) {
  40         return (Set) mapCallee2CallerSet.get( md );
  41     }
  42
  43     // this method returns the set of MethodDescriptors that
  44     // are called by the given method or task
  45     public Set getCalleeSet( Descriptor d ) {
  46         assert (d instanceof MethodDescriptor) ||
  47                (d instanceof   TaskDescriptor);
  48
  49         return (Set) mapCaller2CalleeSet.get( d );
  50     }
  51
  52     // build a mapping of virtual methods to all
  53     // possible implementations of that method
  54     private void buildVirtualMap() {
  55         //Iterator through classes
  56         Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
  57         while(it.hasNext()) {
  58             ClassDescriptor cn=(ClassDescriptor)it.next();
  59             Iterator methodit=cn.getMethods();
  60             //Iterator through methods
  61             while(methodit.hasNext()) {
  62                 MethodDescriptor md=(MethodDescriptor)methodit.next();
  63                 if (md.isStatic()||md.getReturnType()==null)
  64                     continue;
  65                 ClassDescriptor superdesc=cn.getSuperDesc();
  66                 if (superdesc!=null) {
  67                     Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol());
  68                     boolean foundmatch=false;
  69                     for(Iterator matchit=possiblematches.iterator();matchit.hasNext();) {
  70                         MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
  71                         if (md.matches(matchmd)) {
  72                             if (!mapVirtual2ImplementationSet.containsKey(matchmd))
  73                                 mapVirtual2ImplementationSet.put(matchmd,new HashSet());
  74                             ((HashSet)mapVirtual2ImplementationSet.get(matchmd)).add(md);
  75                             break;
  76                         }
  77                     }
  78                 }
  79             }
  80         }
  81     }
  82
  83     public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
  84         return getMethods(md);
  85     }
  86
  87     /** Given a call to MethodDescriptor, lists the methods which
  88         could actually be called due to virtual dispatch. */
  89     public Set getMethods(MethodDescriptor md) {
  90         HashSet ns=new HashSet();
  91         ns.add(md);
  92         Set s=(Set)mapVirtual2ImplementationSet.get(md);
  93         if (s!=null)
  94             for(Iterator it=s.iterator();it.hasNext();) {
  95                 MethodDescriptor md2=(MethodDescriptor)it.next();
  96                 ns.addAll(getMethods(md2));
  97             }
  98         return ns;
  99     }
 100
 101     /** Given a call to MethodDescriptor, lists the methods which
 102         could actually be call by that method. */
 103     public Set getMethodCalls(MethodDescriptor md) {
 104         HashSet ns=new HashSet();
 105         ns.add(md);
 106         Set s=(Set)mapCaller2CalleeSet.get(md);
 107         if (s!=null)
 108             for(Iterator it=s.iterator();it.hasNext();) {
 109                 MethodDescriptor md2=(MethodDescriptor)it.next();
 110                 ns.addAll(getMethodCalls(md2));
 111             }
 112         return ns;
 113     }
 114
 115     private void buildGraph() {
 116         Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
 117         while(it.hasNext()) {
 118             ClassDescriptor cn=(ClassDescriptor)it.next();
 119             Iterator methodit=cn.getMethods();
 120             //Iterator through methods
 121             while(methodit.hasNext()) {
 122                 MethodDescriptor md=(MethodDescriptor)methodit.next();
 123                 analyzeMethod( (Object)md, state.getMethodFlat(md) );
 124             }
 125         }
 126         it=state.getTaskSymbolTable().getDescriptorsIterator();
 127         while(it.hasNext()) {
 128             TaskDescriptor td=(TaskDescriptor)it.next();
 129             analyzeMethod( (Object)td, state.getMethodFlat(td) );
 130         }
 131     }
 132
 133     private void analyzeMethod(Object caller, FlatMethod fm) {
 134         HashSet toexplore=new HashSet();
 135         toexplore.add(fm);
 136         HashSet explored=new HashSet();
 137         //look at all the nodes in the flat representation
 138         while(!toexplore.isEmpty()) {
 139             FlatNode fn=(FlatNode)(toexplore.iterator()).next();
 140             toexplore.remove(fn);
 141             explored.add(fn);
 142             for(int i=0;i<fn.numNext();i++) {
 143                 FlatNode fnnext=fn.getNext(i);
 144                 if (!explored.contains(fnnext))
 145                     toexplore.add(fnnext);
 146             }
 147             if (fn.kind()==FKind.FlatCall) {
 148                 FlatCall fc=(FlatCall)fn;
 149                 MethodDescriptor calledmethod=fc.getMethod();
 150                 Set methodsthatcouldbecalled=fc.getThis()==null?getMethods(calledmethod):
 151                     getMethods(calledmethod, fc.getThis().getType());
 152
 153                 // add caller -> callee maps
 154                 if( !mapCaller2CalleeSet.containsKey( caller ) ) {
 155                     mapCaller2CalleeSet.put( caller, new HashSet() );
 156                 }
 157                 ((HashSet)mapCaller2CalleeSet.get( caller )).addAll( methodsthatcouldbecalled );
 158
 159                 // add callee -> caller maps
 160                 Iterator calleeItr = methodsthatcouldbecalled.iterator();
 161                 while( calleeItr.hasNext() ) {
 162                     MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 163                     if( !mapCallee2CallerSet.containsKey( callee ) ) {
 164                         mapCallee2CallerSet.put( callee, new HashSet() );
 165                     }
 166                     ((HashSet)mapCallee2CallerSet.get( callee )).add( caller );
 167                 }
 168             }
 169         }
 170     }
 171
 172     public void writeToDot( String graphName )  throws java.io.IOException {
 173         // each task or method only needs to be labeled once
 174         // in a dot file
 175         HashSet labeledInDot = new HashSet();
 176
 177         // write out the call graph using the callees mapping
 178         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+"byCallees.dot" ) );
 179         bw.write( "digraph "+graphName+"byCallees {\n" );
 180         Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
 181         while( mapItr.hasNext() ) {
 182             Map.Entry        me        = (Map.Entry)        mapItr.next();
 183             MethodDescriptor callee    = (MethodDescriptor) me.getKey();
 184             HashSet          callerSet = (HashSet)          me.getValue();
 185
 186             if( !labeledInDot.contains( callee ) ) {
 187                 labeledInDot.add( callee );
 188                 bw.write( "  " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
 189             }
 190
 191             Iterator callerItr = callerSet.iterator();
 192             while( callerItr.hasNext() ) {
 193                 Descriptor caller = (Descriptor) callerItr.next();
 194
 195                 if( !labeledInDot.contains( caller ) ) {
 196                     labeledInDot.add( caller );
 197                     bw.write( "  " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
 198                 }
 199
 200                 bw.write( "  " + callee.getNum() + "->" + caller.getNum() + ";\n" );
 201             }
 202         }
 203         bw.write( "}\n" );
 204         bw.close();
 205
 206         // write out the call graph (should be equivalent) by
 207         // using the callers mapping
 208         labeledInDot = new HashSet();
 209         bw = new BufferedWriter( new FileWriter( graphName+"byCallers.dot" ) );
 210         bw.write( "digraph "+graphName+"byCallers {\n" );
 211         mapItr = mapCaller2CalleeSet.entrySet().iterator();
 212         while( mapItr.hasNext() ) {
 213             Map.Entry  me        = (Map.Entry)  mapItr.next();
 214             Descriptor caller    = (Descriptor) me.getKey();
 215             HashSet    calleeSet = (HashSet)    me.getValue();
 216
 217             if( !labeledInDot.contains( caller ) ) {
 218                 labeledInDot.add( caller );
 219                 bw.write( "  " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
 220             }
 221
 222             Iterator calleeItr = calleeSet.iterator();
 223             while( calleeItr.hasNext() ) {
 224                 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 225
 226                 if( !labeledInDot.contains( callee ) ) {
 227                     labeledInDot.add( callee );
 228                     bw.write( "  " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
 229                 }
 230
 231                 bw.write( "  " + callee.getNum() + "->" + caller.getNum() + ";\n" );
 232             }
 233         }
 234         bw.write( "}\n" );
 235         bw.close();
 236     }
 237 }