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 analyzeBlockNode(md, md.getParameterTable(), bn);
136 private void analyzeBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
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);
146 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
147 BlockStatementNode bsn) {
149 switch (bsn.kind()) {
150 case Kind.BlockExpressionNode:
151 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
154 case Kind.DeclarationNode:
155 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn);
158 case Kind.IfStatementNode:
159 analyzeIfStatementNode(md, nametable, (IfStatementNode) bsn);
163 analyzeLoopNode(md, nametable, (LoopNode) bsn);
166 case Kind.ReturnNode:
167 analyzeReturnNode(md, nametable, (ReturnNode) bsn);
170 case Kind.SubBlockNode:
171 analyzeSubBlockNode(md, nametable, (SubBlockNode) bsn);
174 case Kind.ContinueBreakNode:
177 case Kind.SwitchStatementNode:
178 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
185 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
186 SwitchStatementNode bsn) {
187 // TODO Auto-generated method stub
191 private void analyzeSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode bsn) {
192 // TODO Auto-generated method stub
196 private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
197 // TODO Auto-generated method stub
201 private void analyzeLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode bsn) {
202 // TODO Auto-generated method stub
206 private void analyzeIfStatementNode(MethodDescriptor md, SymbolTable nametable,
207 IfStatementNode bsn) {
208 // TODO Auto-generated method stub
212 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
213 DeclarationNode dn) {
215 VarDescriptor vd = dn.getVarDescriptor();
216 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
218 getFlowGraph(md).createNewFlowNode(tupleLHS);
220 if (dn.getExpression() != null) {
222 NodeTupleSet tupleSetRHS = new NodeTupleSet();
223 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null);
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);
235 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
236 BlockExpressionNode ben) {
237 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null);
240 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
241 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
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!
247 NTuple<Descriptor> flowTuple;
251 case Kind.AssignmentNode:
252 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base);
255 case Kind.FieldAccessNode:
256 flowTuple = analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base);
257 nodeSet.addTuple(flowTuple);
261 NodeTupleSet nameNodeSet = new NodeTupleSet();
262 flowTuple = analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base);
263 nodeSet.addTuple(flowTuple);
267 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet);
270 case Kind.CreateObjectNode:
271 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
274 case Kind.ArrayAccessNode:
275 analyzeArrayAccessNode(md, nametable, (ArrayAccessNode) en);
278 case Kind.LiteralNode:
279 analyzeLiteralNode(md, nametable, (LiteralNode) en);
282 case Kind.MethodInvokeNode:
283 analyzeMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
286 case Kind.TertiaryNode:
287 analyzeTertiaryNode(md, nametable, (TertiaryNode) en);
291 analyzeCastNode(md, nametable, (CastNode) en);
294 // case Kind.InstanceOfNode:
295 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
298 // case Kind.ArrayInitializerNode:
299 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
303 // case Kind.ClassTypeNode:
304 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
307 // case Kind.OffsetNode:
308 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
316 private void analyzeCastNode(MethodDescriptor md, SymbolTable nametable, CastNode en) {
317 // TODO Auto-generated method stub
321 private void analyzeTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
322 // TODO Auto-generated method stub
326 private void analyzeMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
327 MethodInvokeNode en) {
328 // TODO Auto-generated method stub
332 private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
333 // TODO Auto-generated method stub
337 private void analyzeArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
338 // TODO Auto-generated method stub
342 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
343 CreateObjectNode en) {
344 // TODO Auto-generated method stub
348 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
349 NodeTupleSet nodeSet) {
351 System.out.println("### OPNode=" + on.printNode(0));
353 NodeTupleSet leftOpSet = new NodeTupleSet();
354 NodeTupleSet rightOpSet = new NodeTupleSet();
357 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null);
358 System.out.println("leftOpSet=" + leftOpSet);
360 if (on.getRight() != null) {
362 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null);
363 System.out.println("rightOpSet=" + rightOpSet);
366 Operation op = on.getOp();
368 switch (op.getOp()) {
370 case Operation.UNARYPLUS:
371 case Operation.UNARYMINUS:
372 case Operation.LOGIC_NOT:
374 nodeSet.addTupleSet(leftOpSet);
377 case Operation.LOGIC_OR:
378 case Operation.LOGIC_AND:
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:
395 case Operation.LEFTSHIFT:
396 case Operation.RIGHTSHIFT:
397 case Operation.URIGHTSHIFT:
399 // there are two operands
400 nodeSet.addTupleSet(leftOpSet);
401 nodeSet.addTupleSet(rightOpSet);
405 throw new Error(op.toString());
409 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
410 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
413 base = new NTuple<Descriptor>();
416 NameDescriptor nd = nn.getName();
417 if (nd.getBase() != null) {
418 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base);
420 String varname = nd.toString();
421 if (varname.equals("this")) {
423 base.add(md.getThis());
427 Descriptor d = (Descriptor) nametable.get(varname);
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();
437 } else if (d instanceof FieldDescriptor) {
438 // the type of field descriptor has a location!
439 FieldDescriptor fd = (FieldDescriptor) d;
442 // if it is 'static final', the location has TOP since no one can
444 // loc.addLocation(Location.createTopLocation(md));
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) {
452 // Error("Global location element is not defined in the method " +
455 // Location globalLoc = new Location(md, globalLocId);
457 // loc.addLocation(globalLoc);
460 // the location of field access starts from this, followed by field
462 base.add(md.getThis());
466 } else if (d == null) {
467 // access static field
468 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
470 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
471 // String globalLocId = localLattice.getGlobalLoc();
472 // if (globalLocId == null) {
474 // Error("Method lattice does not define global variable location at "
475 // + generateErrorMessage(md.getClassDesc(), nn));
477 // loc.addLocation(new Location(md, globalLocId));
479 // Location fieldLoc = (Location) fd.getType().getExtension();
480 // loc.addLocation(fieldLoc);
487 getFlowGraph(md).createNewFlowNode(base);
493 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
494 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
496 ExpressionNode left = fan.getExpression();
497 TypeDescriptor ltd = left.getType();
498 FieldDescriptor fd = fan.getField();
500 String varName = null;
501 if (left.kind() == Kind.NameNode) {
502 NameDescriptor nd = ((NameNode) left).getName();
503 varName = nd.toString();
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));
514 // if (left instanceof ArrayAccessNode) {
515 // ArrayAccessNode aan = (ArrayAccessNode) left;
516 // left = aan.getExpression();
519 base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base);
521 if (!left.getType().isPrimitive()) {
523 if (fd.getSymbol().equals("length")) {
525 // array.length access, return the location of the array
536 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
537 AssignmentNode an, NTuple<Descriptor> base) {
539 System.out.println("analyzeFlowAssignmentNode=" + an);
541 ClassDescriptor cd = md.getClassDesc();
543 NodeTupleSet nodeSetRHS = new NodeTupleSet();
544 NodeTupleSet nodeSetLHS = new NodeTupleSet();
546 boolean postinc = true;
547 if (an.getOperation().getBaseOp() == null
548 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
549 .getBaseOp().getOp() != Operation.POSTDEC)) {
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);
561 // analyze value flows of rhs expression
562 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null);
563 System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
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);
576 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
577 NTuple<Descriptor> tuple = iter2.next();
578 addFlowGraphEdge(md, tuple, tuple);
585 public FlowGraph getFlowGraph(MethodDescriptor md) {
586 return mapMethodDescriptorToFlowGraph.get(md);
589 public void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from, NTuple<Descriptor> to) {
590 FlowGraph graph = getFlowGraph(md);
591 graph.addValueFlowEdge(from, to);
594 public void _debug_printGraph() {
595 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
597 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
598 MethodDescriptor md = (MethodDescriptor) iterator.next();
599 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
602 } catch (IOException e) {