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