Robust/src/Analysis/SSJava/LocationInference.java

   1 package Analysis.SSJava;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collections;
   5 import java.util.Comparator;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.List;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.ClassDescriptor;
  13 import IR.Descriptor;
  14 import IR.FieldDescriptor;
  15 import IR.MethodDescriptor;
  16 import IR.NameDescriptor;
  17 import IR.Operation;
  18 import IR.State;
  19 import IR.SymbolTable;
  20 import IR.VarDescriptor;
  21 import IR.Tree.ArrayAccessNode;
  22 import IR.Tree.AssignmentNode;
  23 import IR.Tree.BlockExpressionNode;
  24 import IR.Tree.BlockNode;
  25 import IR.Tree.BlockStatementNode;
  26 import IR.Tree.CastNode;
  27 import IR.Tree.CreateObjectNode;
  28 import IR.Tree.DeclarationNode;
  29 import IR.Tree.ExpressionNode;
  30 import IR.Tree.FieldAccessNode;
  31 import IR.Tree.IfStatementNode;
  32 import IR.Tree.Kind;
  33 import IR.Tree.LiteralNode;
  34 import IR.Tree.LoopNode;
  35 import IR.Tree.MethodInvokeNode;
  36 import IR.Tree.NameNode;
  37 import IR.Tree.OpNode;
  38 import IR.Tree.ReturnNode;
  39 import IR.Tree.SubBlockNode;
  40 import IR.Tree.SwitchStatementNode;
  41 import IR.Tree.TertiaryNode;
  42
  43 public class LocationInference {
  44
  45   State state;
  46   SSJavaAnalysis ssjava;
  47
  48   List<ClassDescriptor> toanalyzeList;
  49   List<MethodDescriptor> toanalyzeMethodList;
  50   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  51
  52   boolean debug = true;
  53
  54   public LocationInference(SSJavaAnalysis ssjava, State state) {
  55     this.ssjava = ssjava;
  56     this.state = state;
  57     this.toanalyzeList = new ArrayList<ClassDescriptor>();
  58     this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
  59     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
  60   }
  61
  62   public void setupToAnalyze() {
  63     SymbolTable classtable = state.getClassSymbolTable();
  64     toanalyzeList.clear();
  65     toanalyzeList.addAll(classtable.getValueSet());
  66     Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
  67       public int compare(ClassDescriptor o1, ClassDescriptor o2) {
  68         return o1.getClassName().compareToIgnoreCase(o2.getClassName());
  69       }
  70     });
  71   }
  72
  73   public void setupToAnalazeMethod(ClassDescriptor cd) {
  74
  75     SymbolTable methodtable = cd.getMethodTable();
  76     toanalyzeMethodList.clear();
  77     toanalyzeMethodList.addAll(methodtable.getValueSet());
  78     Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
  79       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
  80         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
  81       }
  82     });
  83   }
  84
  85   public boolean toAnalyzeMethodIsEmpty() {
  86     return toanalyzeMethodList.isEmpty();
  87   }
  88
  89   public boolean toAnalyzeIsEmpty() {
  90     return toanalyzeList.isEmpty();
  91   }
  92
  93   public ClassDescriptor toAnalyzeNext() {
  94     return toanalyzeList.remove(0);
  95   }
  96
  97   public MethodDescriptor toAnalyzeMethodNext() {
  98     return toanalyzeMethodList.remove(0);
  99   }
 100
 101   public void inference() {
 102
 103     // 2) construct value flow graph
 104
 105     setupToAnalyze();
 106
 107     while (!toAnalyzeIsEmpty()) {
 108       ClassDescriptor cd = toAnalyzeNext();
 109
 110       setupToAnalazeMethod(cd);
 111       while (!toAnalyzeMethodIsEmpty()) {
 112         MethodDescriptor md = toAnalyzeMethodNext();
 113         if (ssjava.needTobeAnnotated(md)) {
 114           if (state.SSJAVADEBUG) {
 115             System.out.println("SSJAVA: Constructing a flow graph: " + md);
 116           }
 117           FlowGraph fg = new FlowGraph(md);
 118           mapMethodDescriptorToFlowGraph.put(md, fg);
 119           analyzeMethodBody(cd, md);
 120         }
 121       }
 122     }
 123
 124   }
 125
 126   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 127     BlockNode bn = state.getMethodBody(md);
 128     analyzeBlockNode(md, md.getParameterTable(), bn);
 129   }
 130
 131   private void analyzeBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 132
 133     bn.getVarTable().setParent(nametable);
 134     for (int i = 0; i < bn.size(); i++) {
 135       BlockStatementNode bsn = bn.get(i);
 136       analyzeBlockStatementNode(md, bn.getVarTable(), bsn);
 137     }
 138
 139   }
 140
 141   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 142       BlockStatementNode bsn) {
 143
 144     switch (bsn.kind()) {
 145     case Kind.BlockExpressionNode:
 146       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 147       break;
 148
 149     case Kind.DeclarationNode:
 150       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, new NTuple<Descriptor>());
 151       break;
 152
 153     case Kind.IfStatementNode:
 154       analyzeIfStatementNode(md, nametable, (IfStatementNode) bsn);
 155       break;
 156
 157     case Kind.LoopNode:
 158       analyzeLoopNode(md, nametable, (LoopNode) bsn);
 159       break;
 160
 161     case Kind.ReturnNode:
 162       analyzeReturnNode(md, nametable, (ReturnNode) bsn);
 163       break;
 164
 165     case Kind.SubBlockNode:
 166       analyzeSubBlockNode(md, nametable, (SubBlockNode) bsn);
 167       break;
 168
 169     case Kind.ContinueBreakNode:
 170       break;
 171
 172     case Kind.SwitchStatementNode:
 173       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 174       break;
 175
 176     }
 177
 178   }
 179
 180   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 181       SwitchStatementNode bsn) {
 182     // TODO Auto-generated method stub
 183
 184   }
 185
 186   private void analyzeSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode bsn) {
 187     // TODO Auto-generated method stub
 188
 189   }
 190
 191   private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
 192     // TODO Auto-generated method stub
 193
 194   }
 195
 196   private void analyzeLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode bsn) {
 197     // TODO Auto-generated method stub
 198
 199   }
 200
 201   private void analyzeIfStatementNode(MethodDescriptor md, SymbolTable nametable,
 202       IfStatementNode bsn) {
 203     // TODO Auto-generated method stub
 204
 205   }
 206
 207   private NTuple<Descriptor> analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
 208       DeclarationNode dn, NTuple<Descriptor> base) {
 209
 210     VarDescriptor vd = dn.getVarDescriptor();
 211     base.add(vd);
 212     getFlowGraph(md).createNewFlowNode(base);
 213
 214     if (dn.getExpression() != null) {
 215
 216       NTuple<Descriptor> rhsDescTuple =
 217           analyzeFlowExpressionNode(md, nametable, dn.getExpression(), new NTuple<Descriptor>());
 218
 219       // add a new flow edge from rhs to lhs
 220       if (rhsDescTuple != null) { // rhs is null when values come from the top
 221                                   // location
 222         getFlowGraph(md).addValueFlowEdge(rhsDescTuple, base);
 223       }
 224
 225     }
 226
 227     return null;
 228
 229   }
 230
 231   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 232       BlockExpressionNode ben) {
 233     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null);
 234   }
 235
 236   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
 237       ExpressionNode en, NTuple<Descriptor> base) {
 238
 239     switch (en.kind()) {
 240
 241     case Kind.AssignmentNode:
 242       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base);
 243       break;
 244
 245     case Kind.FieldAccessNode:
 246       analyzeFieldAccessNode(md, nametable, (FieldAccessNode) en);
 247       break;
 248
 249     case Kind.NameNode:
 250       return analyzeFlowNameNode(md, nametable, (NameNode) en, base);
 251
 252     case Kind.OpNode:
 253       // return analyzeOpNode(md, nametable, (OpNode) en, new
 254       // HashSet<FlowNode>());
 255       break;
 256
 257     case Kind.CreateObjectNode:
 258       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
 259       break;
 260
 261     case Kind.ArrayAccessNode:
 262       analyzeArrayAccessNode(md, nametable, (ArrayAccessNode) en);
 263       break;
 264
 265     case Kind.LiteralNode:
 266       analyzeLiteralNode(md, nametable, (LiteralNode) en);
 267       break;
 268
 269     case Kind.MethodInvokeNode:
 270       analyzeMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
 271       break;
 272
 273     case Kind.TertiaryNode:
 274       analyzeTertiaryNode(md, nametable, (TertiaryNode) en);
 275       break;
 276
 277     case Kind.CastNode:
 278       analyzeCastNode(md, nametable, (CastNode) en);
 279       break;
 280
 281     // case Kind.InstanceOfNode:
 282     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 283     // return null;
 284
 285     // case Kind.ArrayInitializerNode:
 286     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 287     // td);
 288     // return null;
 289
 290     // case Kind.ClassTypeNode:
 291     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 292     // return null;
 293
 294     // case Kind.OffsetNode:
 295     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 296     // return null;
 297
 298     }
 299     return null;
 300
 301   }
 302
 303   private void analyzeCastNode(MethodDescriptor md, SymbolTable nametable, CastNode en) {
 304     // TODO Auto-generated method stub
 305
 306   }
 307
 308   private void analyzeTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
 309     // TODO Auto-generated method stub
 310
 311   }
 312
 313   private void analyzeMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
 314       MethodInvokeNode en) {
 315     // TODO Auto-generated method stub
 316
 317   }
 318
 319   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
 320     // TODO Auto-generated method stub
 321
 322   }
 323
 324   private void analyzeArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
 325     // TODO Auto-generated method stub
 326
 327   }
 328
 329   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
 330       CreateObjectNode en) {
 331     // TODO Auto-generated method stub
 332
 333   }
 334
 335   private Set<FlowNode> analyzeOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
 336       Set<FlowNode> nodeSet) {
 337
 338     ClassDescriptor cd = md.getClassDesc();
 339
 340     // left operand
 341     NTuple<Descriptor> leftOpTuple =
 342         analyzeFlowExpressionNode(md, nametable, on.getLeft(), new NTuple<Descriptor>());
 343
 344     if (on.getRight() != null) {
 345       // right operand
 346       NTuple<Descriptor> rightOpTuple =
 347           analyzeFlowExpressionNode(md, nametable, on.getRight(), new NTuple<Descriptor>());
 348     }
 349
 350     Operation op = on.getOp();
 351
 352     switch (op.getOp()) {
 353
 354     case Operation.UNARYPLUS:
 355     case Operation.UNARYMINUS:
 356     case Operation.LOGIC_NOT:
 357       // single operand
 358       // return leftLoc;
 359
 360     case Operation.LOGIC_OR:
 361     case Operation.LOGIC_AND:
 362     case Operation.COMP:
 363     case Operation.BIT_OR:
 364     case Operation.BIT_XOR:
 365     case Operation.BIT_AND:
 366     case Operation.ISAVAILABLE:
 367     case Operation.EQUAL:
 368     case Operation.NOTEQUAL:
 369     case Operation.LT:
 370     case Operation.GT:
 371     case Operation.LTE:
 372     case Operation.GTE:
 373     case Operation.ADD:
 374     case Operation.SUB:
 375     case Operation.MULT:
 376     case Operation.DIV:
 377     case Operation.MOD:
 378     case Operation.LEFTSHIFT:
 379     case Operation.RIGHTSHIFT:
 380     case Operation.URIGHTSHIFT:
 381
 382       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 383       // inputSet.add(leftLoc);
 384       // inputSet.add(rightLoc);
 385       // CompositeLocation glbCompLoc =
 386       // CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
 387       // return glbCompLoc;
 388
 389     default:
 390       throw new Error(op.toString());
 391     }
 392   }
 393
 394   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
 395       NameNode nn, NTuple<Descriptor> base) {
 396
 397     NameDescriptor nd = nn.getName();
 398     if (nd.getBase() != null) {
 399       analyzeFlowExpressionNode(md, nametable, nn.getExpression(), base);
 400     } else {
 401       String varname = nd.toString();
 402       if (varname.equals("this")) {
 403         // 'this' itself!
 404         base.add(md.getThis());
 405         return base;
 406       }
 407
 408       Descriptor d = (Descriptor) nametable.get(varname);
 409
 410       // CompositeLocation localLoc = null;
 411       if (d instanceof VarDescriptor) {
 412         VarDescriptor vd = (VarDescriptor) d;
 413         // localLoc = d2loc.get(vd);
 414         // the type of var descriptor has a composite location!
 415         // loc = ((SSJavaType)
 416         // vd.getType().getExtension()).getCompLoc().clone();
 417         base.add(vd);
 418       } else if (d instanceof FieldDescriptor) {
 419         // the type of field descriptor has a location!
 420         FieldDescriptor fd = (FieldDescriptor) d;
 421         if (fd.isStatic()) {
 422           if (fd.isFinal()) {
 423             // if it is 'static final', the location has TOP since no one can
 424             // change its value
 425             // loc.addLocation(Location.createTopLocation(md));
 426             // return loc;
 427           } else {
 428             // if 'static', the location has pre-assigned global loc
 429             // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 430             // String globalLocId = localLattice.getGlobalLoc();
 431             // if (globalLocId == null) {
 432             // throw new
 433             // Error("Global location element is not defined in the method " +
 434             // md);
 435             // }
 436             // Location globalLoc = new Location(md, globalLocId);
 437             //
 438             // loc.addLocation(globalLoc);
 439           }
 440         } else {
 441           // the location of field access starts from this, followed by field
 442           // location
 443           base.add(md.getThis());
 444         }
 445
 446         // Location fieldLoc = (Location) fd.getType().getExtension();
 447         // loc.addLocation(fieldLoc);
 448         base.add(fd);
 449       } else if (d == null) {
 450         // access static field
 451         // FieldDescriptor fd = nn.getField();
 452         //
 453         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 454         // String globalLocId = localLattice.getGlobalLoc();
 455         // if (globalLocId == null) {
 456         // throw new
 457         // Error("Method lattice does not define global variable location at "
 458         // + generateErrorMessage(md.getClassDesc(), nn));
 459         // }
 460         // loc.addLocation(new Location(md, globalLocId));
 461         //
 462         // Location fieldLoc = (Location) fd.getType().getExtension();
 463         // loc.addLocation(fieldLoc);
 464         //
 465         // return loc;
 466
 467       }
 468     }
 469
 470     getFlowGraph(md).createNewFlowNode(base);
 471
 472     return base;
 473
 474   }
 475
 476   private void analyzeFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode en) {
 477     // TODO Auto-generated method stub
 478
 479   }
 480
 481   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
 482       AssignmentNode an, NTuple<Descriptor> base) {
 483
 484     System.out.println("analyzeFlowAssignmentNode=" + an);
 485
 486     ClassDescriptor cd = md.getClassDesc();
 487
 488     boolean postinc = true;
 489     if (an.getOperation().getBaseOp() == null
 490         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 491             .getBaseOp().getOp() != Operation.POSTDEC)) {
 492       postinc = false;
 493     }
 494
 495     // if LHS is array access node, need to capture value flows between an array
 496     // and its index value
 497     analyzeFlowExpressionNode(md, nametable, an.getDest(), base);
 498     // NTuple<Descriptor> lhsDescTuple = analyzeFlowExpressionNode(md,
 499     // nametable, an.getDest(), base);
 500
 501     if (!postinc) {
 502       // analyze value flows of rhs expression
 503       NTuple<Descriptor> rhsDescTuple =
 504           analyzeFlowExpressionNode(md, nametable, an.getSrc(), new NTuple<Descriptor>());
 505
 506     } else {
 507
 508       // postinc case
 509       // src & dest are same
 510
 511     }
 512
 513   }
 514
 515   public FlowGraph getFlowGraph(MethodDescriptor md) {
 516     return mapMethodDescriptorToFlowGraph.get(md);
 517   }
 518
 519 }