Robust/src/Analysis/SSJava/LocationInference.java

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