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   protected State state;
  17
  18   // MethodDescriptor maps to HashSet<MethodDescriptor>
  19   protected Hashtable mapVirtual2ImplementationSet;
  20
  21   // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
  22   protected Hashtable mapCaller2CalleeSet;
  23
  24   // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
  25   protected Hashtable mapCallee2CallerSet;
  26
  27   protected CallGraph() {}
  28
  29   public CallGraph(State state) {
  30     this.state=state;
  31     mapVirtual2ImplementationSet = new Hashtable();
  32     mapCaller2CalleeSet          = new Hashtable();
  33     mapCallee2CallerSet          = new Hashtable();
  34     buildVirtualMap();
  35     buildGraph();
  36   }
  37
  38   // this method returns the set of Descriptors
  39   // (MethodDescriptors and/or TaskDescriptors)
  40   //  that call the given method
  41   public Set getCallerSet(MethodDescriptor md) {
  42     Set s = (Set) mapCallee2CallerSet.get(md);
  43
  44     if( s == null ) {
  45       return new HashSet();
  46     }
  47     return s;
  48   }
  49
  50   // this method returns the set of MethodDescriptors that
  51   // are called by the given method or task
  52   public Set getCalleeSet(Descriptor d) {
  53     assert(d instanceof MethodDescriptor) ||
  54     (d instanceof TaskDescriptor);
  55
  56     Set s = (Set) mapCaller2CalleeSet.get(d);
  57
  58     if( s == null ) {
  59       return new HashSet();
  60     }
  61     return s;
  62   }
  63
  64   // build a mapping of virtual methods to all
  65   // possible implementations of that method
  66   protected void buildVirtualMap() {
  67     //Iterator through classes
  68     Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
  69     while(it.hasNext()) {
  70       ClassDescriptor cn=(ClassDescriptor)it.next();
  71       Iterator methodit=cn.getMethods();
  72       //Iterator through methods
  73       while(methodit.hasNext()) {
  74         MethodDescriptor md=(MethodDescriptor)methodit.next();
  75         if (md.isStatic()||md.getReturnType()==null)
  76           continue;
  77         ClassDescriptor superdesc=cn.getSuperDesc();
  78         if (superdesc!=null) {
  79           Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol());
  80           boolean foundmatch=false;
  81           for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) {
  82             MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
  83             if (md.matches(matchmd)) {
  84               if (!mapVirtual2ImplementationSet.containsKey(matchmd))
  85                 mapVirtual2ImplementationSet.put(matchmd,new HashSet());
  86               ((HashSet)mapVirtual2ImplementationSet.get(matchmd)).add(md);
  87               break;
  88             }
  89           }
  90         }
  91       }
  92     }
  93   }
  94
  95   public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
  96     return getMethods(md);
  97   }
  98
  99   /** Given a call to MethodDescriptor, lists the methods which
 100       could actually be called due to virtual dispatch. */
 101   public Set getMethods(MethodDescriptor md) {
 102     HashSet ns=new HashSet();
 103     ns.add(md);
 104     Set s=(Set)mapVirtual2ImplementationSet.get(md);
 105     if (s!=null)
 106       for(Iterator it=s.iterator(); it.hasNext();) {
 107         MethodDescriptor md2=(MethodDescriptor)it.next();
 108         ns.addAll(getMethods(md2));
 109       }
 110     return ns;
 111   }
 112
 113   /** Given a call to MethodDescriptor, lists the methods which
 114       could actually be call by that method. */
 115   public Set getMethodCalls(TaskDescriptor td) {
 116     return getMethodCalls( (Descriptor) td);
 117   }
 118
 119   public Set getMethodCalls(MethodDescriptor md) {
 120     return getMethodCalls( (Descriptor) md);
 121   }
 122
 123   public Set getMethodCalls(Descriptor d) {
 124     assert d instanceof MethodDescriptor ||
 125     d instanceof TaskDescriptor;
 126
 127     HashSet ns=new HashSet();
 128     ns.add(d);
 129     return getMoreMethodCalls(ns, d);
 130   }
 131
 132   private Set getMoreMethodCalls(HashSet found, Descriptor d) {
 133     HashSet ns=new HashSet();
 134     ns.add(d);
 135     found.add(d);
 136     Set s=(Set)mapCaller2CalleeSet.get(d);
 137     if (s!=null)
 138       for(Iterator it=s.iterator(); it.hasNext();) {
 139         MethodDescriptor md=(MethodDescriptor)it.next();
 140         if( !found.contains(md) ) {
 141           ns.addAll(getMoreMethodCalls(found, md));
 142         }
 143       }
 144     return ns;
 145   }
 146
 147   /** Returns all methods transitively callable from d */
 148
 149   public Set getAllMethods(Descriptor d) {
 150     HashSet tovisit=new HashSet();
 151     tovisit.add(d);
 152     HashSet callable=new HashSet();
 153     while(!tovisit.isEmpty()) {
 154       Descriptor md=(Descriptor)tovisit.iterator().next();
 155       tovisit.remove(md);
 156       Set s=(Set)mapCaller2CalleeSet.get(md);
 157       if (s!=null) {
 158         for(Iterator it=s.iterator(); it.hasNext();) {
 159           MethodDescriptor md2=(MethodDescriptor)it.next();
 160           if( !callable.contains(md2) ) {
 161             callable.add(md2);
 162             tovisit.add(md2);
 163           }
 164         }
 165       }
 166     }
 167     return callable;
 168   }
 169
 170   // Returns a set of methods containing SESEs and located at the first
 171   // in transitive call chain starting from d
 172   public Set getFirstReachableMethodContainingSESE(Descriptor d,
 173       Set<MethodDescriptor> methodsContainingSESEs) {
 174     HashSet tovisit = new HashSet();
 175     tovisit.add(d);
 176     HashSet callable = new HashSet();
 177     while (!tovisit.isEmpty()) {
 178       Descriptor md = (Descriptor) tovisit.iterator().next();
 179       tovisit.remove(md);
 180       Set s = (Set) mapCaller2CalleeSet.get(md);
 181
 182       if (s != null) {
 183         for (Iterator it = s.iterator(); it.hasNext();) {
 184           MethodDescriptor md2 = (MethodDescriptor) it.next();
 185           if (!callable.contains(md2)) {
 186             callable.add(md2);
 187             if (!methodsContainingSESEs.contains(md2)) {
 188               // if current method has sese, do not need to go down
 189               tovisit.add(md2);
 190             }
 191           }
 192         }
 193       }
 194     }
 195 //    callable.retainAll(methodsContainingSESEs);
 196     return callable;
 197   }
 198
 199
 200   private void buildGraph() {
 201     Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
 202     while(it.hasNext()) {
 203       ClassDescriptor cn=(ClassDescriptor)it.next();
 204       Iterator methodit=cn.getMethods();
 205       //Iterator through methods
 206       while(methodit.hasNext()) {
 207         MethodDescriptor md=(MethodDescriptor)methodit.next();
 208         analyzeMethod( (Object)md, state.getMethodFlat(md) );
 209       }
 210     }
 211     it=state.getTaskSymbolTable().getDescriptorsIterator();
 212     while(it.hasNext()) {
 213       TaskDescriptor td=(TaskDescriptor)it.next();
 214       analyzeMethod( (Object)td, state.getMethodFlat(td) );
 215     }
 216   }
 217
 218   protected void analyzeMethod(Object caller, FlatMethod fm) {
 219     HashSet toexplore=new HashSet();
 220     toexplore.add(fm);
 221     HashSet explored=new HashSet();
 222     //look at all the nodes in the flat representation
 223     while(!toexplore.isEmpty()) {
 224       FlatNode fn=(FlatNode)(toexplore.iterator()).next();
 225       toexplore.remove(fn);
 226       explored.add(fn);
 227       for(int i=0; i<fn.numNext(); i++) {
 228         FlatNode fnnext=fn.getNext(i);
 229         if (!explored.contains(fnnext))
 230           toexplore.add(fnnext);
 231       }
 232       if (fn.kind()==FKind.FlatCall) {
 233         FlatCall fc=(FlatCall)fn;
 234         MethodDescriptor calledmethod=fc.getMethod();
 235         Set methodsthatcouldbecalled=fc.getThis()==null ? getMethods(calledmethod) :
 236                                       getMethods(calledmethod, fc.getThis().getType());
 237
 238         // add caller -> callee maps
 239         if( !mapCaller2CalleeSet.containsKey(caller) ) {
 240           mapCaller2CalleeSet.put(caller, new HashSet() );
 241         }
 242         ((HashSet)mapCaller2CalleeSet.get(caller)).addAll(methodsthatcouldbecalled);
 243
 244         // add callee -> caller maps
 245         Iterator calleeItr = methodsthatcouldbecalled.iterator();
 246         while( calleeItr.hasNext() ) {
 247           MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 248           if( !mapCallee2CallerSet.containsKey(callee) ) {
 249             mapCallee2CallerSet.put(callee, new HashSet() );
 250           }
 251           ((HashSet)mapCallee2CallerSet.get(callee)).add(caller);
 252         }
 253       }
 254     }
 255   }
 256
 257
 258   public void writeVirtual2ImplemToDot(String graphName)  throws java.io.IOException {
 259     HashSet labeledInDot = new HashSet();
 260
 261     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
 262     bw.write("digraph "+graphName+" {\n");
 263     Iterator mapItr =  mapVirtual2ImplementationSet.entrySet().iterator();
 264     while( mapItr.hasNext() ) {
 265       Map.Entry me        = (Map.Entry)mapItr.next();
 266       MethodDescriptor virtual   = (MethodDescriptor) me.getKey();
 267       HashSet implemSet = (HashSet)          me.getValue();
 268
 269       if( !labeledInDot.contains(virtual) ) {
 270         labeledInDot.add(virtual);
 271         bw.write("  "+virtual.getNum()+"[label=\""+virtual+"\"];\n");
 272       }
 273
 274       Iterator implemItr = implemSet.iterator();
 275       while( implemItr.hasNext() ) {
 276         Descriptor implem = (Descriptor) implemItr.next();
 277
 278         if( !labeledInDot.contains(implem) ) {
 279           labeledInDot.add(implem);
 280           bw.write("  "+implem.getNum()+"[label=\""+implem+"\"];\n");
 281         }
 282
 283         bw.write("  "+virtual.getNum()+"->"+implem.getNum()+";\n");
 284       }
 285     }
 286     bw.write("}\n");
 287     bw.close();
 288   }
 289
 290
 291   public void writeCaller2CalleesToDot(String graphName)  throws java.io.IOException {
 292     // write out the call graph (should be equivalent) by
 293     // using the callers mapping
 294     HashSet labeledInDot = new HashSet();
 295     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallers.dot") );
 296     bw.write("digraph "+graphName+"byCallers {\n");
 297     Iterator mapItr = mapCaller2CalleeSet.entrySet().iterator();
 298     while( mapItr.hasNext() ) {
 299       Map.Entry me      = (Map.Entry)mapItr.next();
 300       Descriptor caller = (Descriptor) me.getKey();
 301       HashSet calleeSet = (HashSet)    me.getValue();
 302
 303       if( !labeledInDot.contains(caller) ) {
 304         labeledInDot.add(caller);
 305         bw.write("  "+caller.getNum()+"[label=\"" +caller+"\"];\n");
 306       }
 307
 308       Iterator calleeItr = calleeSet.iterator();
 309       while( calleeItr.hasNext() ) {
 310         MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 311
 312         if( !labeledInDot.contains(callee) ) {
 313           labeledInDot.add(callee);
 314           bw.write("  "+callee.getNum()+"[label=\""+callee+"\"];\n");
 315         }
 316
 317         bw.write("  "+caller.getNum()+"->"+callee.getNum()+";\n");
 318       }
 319     }
 320     bw.write("}\n");
 321     bw.close();
 322   }
 323
 324
 325   public void writeCallee2CallersToDot(String graphName)  throws java.io.IOException {
 326     // each task or method only needs to be labeled once
 327     // in a dot file
 328     HashSet labeledInDot = new HashSet();
 329
 330     // write out the call graph using the callees mapping
 331     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallees.dot") );
 332     bw.write("digraph "+graphName+"byCallees {\n");
 333     Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
 334     while( mapItr.hasNext() ) {
 335       Map.Entry me        = (Map.Entry)mapItr.next();
 336       MethodDescriptor callee    = (MethodDescriptor) me.getKey();
 337       HashSet callerSet = (HashSet)          me.getValue();
 338
 339       if( !labeledInDot.contains(callee) ) {
 340         labeledInDot.add(callee);
 341         bw.write("  "+callee.getNum()+"[label=\""+callee+"\"];\n");
 342       }
 343
 344       Iterator callerItr = callerSet.iterator();
 345       while( callerItr.hasNext() ) {
 346         Descriptor caller = (Descriptor) callerItr.next();
 347
 348         if( !labeledInDot.contains(caller) ) {
 349           labeledInDot.add(caller);
 350           bw.write("  "+caller.getNum()+"[label=\""+caller+"\"];\n");
 351         }
 352
 353         bw.write("  "+caller.getNum()+"->"+callee.getNum()+";\n");
 354       }
 355     }
 356     bw.write("}\n");
 357     bw.close();
 358   }
 359 }