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 java.util.*;
   8 import IR.ClassDescriptor;
   9 import IR.MethodDescriptor;
  10
  11 public class CallGraph {
  12     State state;
  13     Hashtable methods;
  14     Hashtable methodmap;
  15
  16     public CallGraph(State state) {
  17         this.state=state;
  18         methods=new Hashtable();
  19         methodmap=new Hashtable();
  20         buildMethodTable();
  21         buildGraph();
  22     }
  23
  24     private void buildMethodTable() {
  25         //Iterator through classes
  26         Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
  27         while(it.hasNext()) {
  28             ClassDescriptor cn=(ClassDescriptor)it.next();
  29             Iterator methodit=cn.getMethods();
  30             //Iterator through methods
  31             while(methodit.hasNext()) {
  32                 MethodDescriptor md=(MethodDescriptor)methodit.next();
  33                 if (md.isStatic()||md.getReturnType()==null)
  34                     continue;
  35                 ClassDescriptor superdesc=cn.getSuperDesc();
  36                 if (superdesc!=null) {
  37                     Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol());
  38                     boolean foundmatch=false;
  39                     for(Iterator matchit=possiblematches.iterator();matchit.hasNext();) {
  40                         MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
  41                         if (md.matches(matchmd)) {
  42                             if (!methods.containsKey(matchmd))
  43                                 methods.put(matchmd,new HashSet());
  44                             ((HashSet)methods.get(matchmd)).add(md);
  45                             break;
  46                         }
  47                     }
  48                 }
  49             }
  50         }
  51     }
  52
  53     /** Given a call to MethodDescriptor, lists the methods which
  54         could actually be called due to virtual dispatch. */
  55     public Set getMethods(MethodDescriptor md) {
  56         HashSet ns=new HashSet();
  57         ns.add(md);
  58         Set s=(Set)methods.get(md);
  59         if (s!=null)
  60             for(Iterator it=s.iterator();it.hasNext();) {
  61                 MethodDescriptor md2=(MethodDescriptor)it.next();
  62                 ns.addAll(getMethods(md2));
  63             }
  64         return ns;
  65     }
  66
  67     private void buildGraph() {
  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                 analyzeMethod(md);
  76             }
  77         }
  78     }
  79
  80     private void analyzeMethod(MethodDescriptor md) {
  81         FlatMethod fm=state.getMethodFlat(md);
  82         HashSet toexplore=new HashSet();
  83         toexplore.add(fm);
  84         HashSet explored=new HashSet();
  85         //look at all the nodes in the flat representation
  86         while(!toexplore.isEmpty()) {
  87             FlatNode fn=(FlatNode)(toexplore.iterator()).next();
  88             toexplore.remove(fn);
  89             explored.add(fn);
  90             for(int i=0;i<fn.numNext();i++) {
  91                 FlatNode fnnext=fn.getNext(i);
  92                 if (!explored.contains(fnnext))
  93                     toexplore.add(fnnext);
  94             }
  95             if (fn.kind()==FKind.FlatCall) {
  96                 FlatCall fc=(FlatCall)fn;
  97                 MethodDescriptor calledmethod=fc.getMethod();
  98                 Set methodsthatcouldbecalled=getMethods(calledmethod);
  99                 if (!methodmap.containsKey(md))
 100                     methodmap.put(md,new HashSet());
 101                 ((HashSet)methodmap.get(md)).addAll(methodsthatcouldbecalled);
 102             }
 103         }
 104     }
 105 }