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