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