1 package Analysis.SSJava;
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;
14 import IR.ClassDescriptor;
16 import IR.FieldDescriptor;
17 import IR.MethodDescriptor;
18 import IR.NameDescriptor;
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;
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;
46 public class LocationInference {
49 SSJavaAnalysis ssjava;
51 List<ClassDescriptor> toanalyzeList;
52 List<MethodDescriptor> toanalyzeMethodList;
53 Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
57 public LocationInference(SSJavaAnalysis ssjava, State state) {
60 this.toanalyzeList = new ArrayList<ClassDescriptor>();
61 this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
62 this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
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());
76 public void setupToAnalazeMethod(ClassDescriptor cd) {
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());
88 public boolean toAnalyzeMethodIsEmpty() {
89 return toanalyzeMethodList.isEmpty();
92 public boolean toAnalyzeIsEmpty() {
93 return toanalyzeList.isEmpty();
96 public ClassDescriptor toAnalyzeNext() {
97 return toanalyzeList.remove(0);
100 public MethodDescriptor toAnalyzeMethodNext() {
101 return toanalyzeMethodList.remove(0);
104 public void inference() {
106 // 2) construct value flow graph
110 while (!toAnalyzeIsEmpty()) {
111 ClassDescriptor cd = toAnalyzeNext();
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);
120 FlowGraph fg = new FlowGraph(md);
121 mapMethodDescriptorToFlowGraph.put(md, fg);
122 analyzeMethodBody(cd, md);
131 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
132 BlockNode bn = state.getMethodBody(md);
133 analyzeFlowBlockNode(md, md.getParameterTable(), bn, null);
136 private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
137 NodeTupleSet implicitFlowTupleSet) {
139 bn.getVarTable().setParent(nametable);
140 for (int i = 0; i < bn.size(); i++) {
141 BlockStatementNode bsn = bn.get(i);
142 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
147 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
148 BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
150 switch (bsn.kind()) {
151 case Kind.BlockExpressionNode:
152 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
155 case Kind.DeclarationNode:
156 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
159 case Kind.IfStatementNode:
160 analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
164 analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
167 case Kind.ReturnNode:
168 analyzeReturnNode(md, nametable, (ReturnNode) bsn);
171 case Kind.SubBlockNode:
172 analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
175 case Kind.ContinueBreakNode:
178 case Kind.SwitchStatementNode:
179 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
186 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
187 SwitchStatementNode bsn) {
188 // TODO Auto-generated method stub
192 private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
193 SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
194 analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
197 private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
198 // TODO Auto-generated method stub
202 private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
203 NodeTupleSet implicitFlowTupleSet) {
205 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
207 NodeTupleSet condTupleNode = new NodeTupleSet();
208 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
209 implicitFlowTupleSet);
210 condTupleNode.addTupleSet(implicitFlowTupleSet);
211 System.out.println("condTupleNode=" + condTupleNode);
213 // add edges from condNodeTupleSet to all nodes of conditional nodes
214 analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
217 // check 'for loop' case
218 BlockNode bn = ln.getInitializer();
219 analyzeFlowBlockNode(md, nametable, bn, implicitFlowTupleSet);
220 bn.getVarTable().setParent(nametable);
222 NodeTupleSet condTupleNode = new NodeTupleSet();
223 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
224 implicitFlowTupleSet);
225 condTupleNode.addTupleSet(implicitFlowTupleSet);
226 System.out.println("condTupleNode=" + condTupleNode);
228 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
229 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
235 private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
236 IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
238 NodeTupleSet condTupleNode = new NodeTupleSet();
239 analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
240 implicitFlowTupleSet);
242 // add edges from condNodeTupleSet to all nodes of conditional nodes
243 condTupleNode.addTupleSet(implicitFlowTupleSet);
244 analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
246 if (isn.getFalseBlock() != null) {
247 analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
252 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
253 DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
255 VarDescriptor vd = dn.getVarDescriptor();
256 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
258 getFlowGraph(md).createNewFlowNode(tupleLHS);
260 if (dn.getExpression() != null) {
262 NodeTupleSet tupleSetRHS = new NodeTupleSet();
263 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
264 implicitFlowTupleSet);
266 // add a new flow edge from rhs to lhs
267 for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
268 NTuple<Descriptor> from = iter.next();
269 addFlowGraphEdge(md, from, tupleLHS);
276 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
277 BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
278 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet);
281 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
282 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
283 NodeTupleSet implicitFlowTupleSet) {
285 // note that expression node can create more than one flow node
286 // nodeSet contains of flow nodes
287 // base is always assigned to null except name node case!
289 NTuple<Descriptor> flowTuple;
293 case Kind.AssignmentNode:
294 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
297 case Kind.FieldAccessNode:
299 analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
300 implicitFlowTupleSet);
301 nodeSet.addTuple(flowTuple);
305 NodeTupleSet nameNodeSet = new NodeTupleSet();
307 analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
308 nodeSet.addTuple(flowTuple);
312 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
315 case Kind.CreateObjectNode:
316 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
319 case Kind.ArrayAccessNode:
320 analyzeArrayAccessNode(md, nametable, (ArrayAccessNode) en);
323 case Kind.LiteralNode:
324 analyzeLiteralNode(md, nametable, (LiteralNode) en);
327 case Kind.MethodInvokeNode:
328 analyzeMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
331 case Kind.TertiaryNode:
332 analyzeTertiaryNode(md, nametable, (TertiaryNode) en);
336 analyzeCastNode(md, nametable, (CastNode) en);
339 // case Kind.InstanceOfNode:
340 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
343 // case Kind.ArrayInitializerNode:
344 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
348 // case Kind.ClassTypeNode:
349 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
352 // case Kind.OffsetNode:
353 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
361 private void analyzeCastNode(MethodDescriptor md, SymbolTable nametable, CastNode en) {
362 // TODO Auto-generated method stub
366 private void analyzeTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
367 // TODO Auto-generated method stub
371 private void analyzeMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
372 MethodInvokeNode en) {
373 // TODO Auto-generated method stub
377 private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
378 // TODO Auto-generated method stub
382 private void analyzeArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
383 // TODO Auto-generated method stub
387 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
388 CreateObjectNode en) {
389 // TODO Auto-generated method stub
393 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
394 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
396 NodeTupleSet leftOpSet = new NodeTupleSet();
397 NodeTupleSet rightOpSet = new NodeTupleSet();
400 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet);
401 System.out.println("leftOpSet=" + leftOpSet);
403 if (on.getRight() != null) {
405 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
406 implicitFlowTupleSet);
407 System.out.println("rightOpSet=" + rightOpSet);
410 Operation op = on.getOp();
412 switch (op.getOp()) {
414 case Operation.UNARYPLUS:
415 case Operation.UNARYMINUS:
416 case Operation.LOGIC_NOT:
418 nodeSet.addTupleSet(leftOpSet);
421 case Operation.LOGIC_OR:
422 case Operation.LOGIC_AND:
424 case Operation.BIT_OR:
425 case Operation.BIT_XOR:
426 case Operation.BIT_AND:
427 case Operation.ISAVAILABLE:
428 case Operation.EQUAL:
429 case Operation.NOTEQUAL:
439 case Operation.LEFTSHIFT:
440 case Operation.RIGHTSHIFT:
441 case Operation.URIGHTSHIFT:
443 // there are two operands
444 nodeSet.addTupleSet(leftOpSet);
445 nodeSet.addTupleSet(rightOpSet);
449 throw new Error(op.toString());
453 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
454 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
457 base = new NTuple<Descriptor>();
460 NameDescriptor nd = nn.getName();
461 if (nd.getBase() != null) {
462 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
463 implicitFlowTupleSet);
465 String varname = nd.toString();
466 if (varname.equals("this")) {
468 base.add(md.getThis());
472 Descriptor d = (Descriptor) nametable.get(varname);
474 // CompositeLocation localLoc = null;
475 if (d instanceof VarDescriptor) {
476 VarDescriptor vd = (VarDescriptor) d;
477 // localLoc = d2loc.get(vd);
478 // the type of var descriptor has a composite location!
479 // loc = ((SSJavaType)
480 // vd.getType().getExtension()).getCompLoc().clone();
482 } else if (d instanceof FieldDescriptor) {
483 // the type of field descriptor has a location!
484 FieldDescriptor fd = (FieldDescriptor) d;
487 // if it is 'static final', the location has TOP since no one can
489 // loc.addLocation(Location.createTopLocation(md));
492 // if 'static', the location has pre-assigned global loc
493 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
494 // String globalLocId = localLattice.getGlobalLoc();
495 // if (globalLocId == null) {
497 // Error("Global location element is not defined in the method " +
500 // Location globalLoc = new Location(md, globalLocId);
502 // loc.addLocation(globalLoc);
505 // the location of field access starts from this, followed by field
507 base.add(md.getThis());
511 } else if (d == null) {
512 // access static field
513 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
515 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
516 // String globalLocId = localLattice.getGlobalLoc();
517 // if (globalLocId == null) {
519 // Error("Method lattice does not define global variable location at "
520 // + generateErrorMessage(md.getClassDesc(), nn));
522 // loc.addLocation(new Location(md, globalLocId));
524 // Location fieldLoc = (Location) fd.getType().getExtension();
525 // loc.addLocation(fieldLoc);
532 getFlowGraph(md).createNewFlowNode(base);
538 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
539 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
540 NodeTupleSet implicitFlowTupleSet) {
542 ExpressionNode left = fan.getExpression();
543 TypeDescriptor ltd = left.getType();
544 FieldDescriptor fd = fan.getField();
546 String varName = null;
547 if (left.kind() == Kind.NameNode) {
548 NameDescriptor nd = ((NameNode) left).getName();
549 varName = nd.toString();
552 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
553 // using a class name directly or access using this
554 if (fd.isStatic() && fd.isFinal()) {
555 // loc.addLocation(Location.createTopLocation(md));
560 // if (left instanceof ArrayAccessNode) {
561 // ArrayAccessNode aan = (ArrayAccessNode) left;
562 // left = aan.getExpression();
565 base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet);
567 if (!left.getType().isPrimitive()) {
569 if (fd.getSymbol().equals("length")) {
571 // array.length access, return the location of the array
582 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
583 AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
585 System.out.println("analyzeFlowAssignmentNode=" + an);
587 NodeTupleSet nodeSetRHS = new NodeTupleSet();
588 NodeTupleSet nodeSetLHS = new NodeTupleSet();
590 boolean postinc = true;
591 if (an.getOperation().getBaseOp() == null
592 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
593 .getBaseOp().getOp() != Operation.POSTDEC)) {
597 // if LHS is array access node, need to capture value flows between an array
598 // and its index value
599 analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet);
600 System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);
601 // NTuple<Descriptor> lhsDescTuple = analyzeFlowExpressionNode(md,
602 // nametable, an.getDest(), base);
605 // analyze value flows of rhs expression
606 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet);
607 System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
609 // creates edges from RHS to LHS
610 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
611 NTuple<Descriptor> fromTuple = iter.next();
612 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
613 NTuple<Descriptor> toTuple = iter2.next();
614 addFlowGraphEdge(md, fromTuple, toTuple);
618 // creates edges from implicitFlowTupleSet to LHS
619 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
620 NTuple<Descriptor> fromTuple = iter.next();
621 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
622 NTuple<Descriptor> toTuple = iter2.next();
623 addFlowGraphEdge(md, fromTuple, toTuple);
629 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
630 NTuple<Descriptor> tuple = iter2.next();
631 addFlowGraphEdge(md, tuple, tuple);
638 public FlowGraph getFlowGraph(MethodDescriptor md) {
639 return mapMethodDescriptorToFlowGraph.get(md);
642 public void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from, NTuple<Descriptor> to) {
643 FlowGraph graph = getFlowGraph(md);
644 graph.addValueFlowEdge(from, to);
647 public void _debug_printGraph() {
648 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
650 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
651 MethodDescriptor md = (MethodDescriptor) iterator.next();
652 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
655 } catch (IOException e) {