1 package Analysis.SSJava;
3 import java.util.ArrayList;
4 import java.util.HashSet;
5 import java.util.Hashtable;
6 import java.util.Iterator;
9 import java.util.StringTokenizer;
10 import java.util.Vector;
12 import IR.AnnotationDescriptor;
13 import IR.ClassDescriptor;
15 import IR.FieldDescriptor;
16 import IR.MethodDescriptor;
17 import IR.NameDescriptor;
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;
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.TertiaryNode;
43 import IR.Tree.TreeNode;
45 public class FlowDownCheck {
48 static SSJavaAnalysis ssjava;
52 // mapping from 'descriptor' to 'composite location'
53 Hashtable<Descriptor, CompositeLocation> d2loc;
55 // mapping from 'locID' to 'class descriptor'
56 Hashtable<String, ClassDescriptor> fieldLocName2cd;
58 public FlowDownCheck(SSJavaAnalysis ssjava, State state) {
61 this.toanalyze = new HashSet();
62 this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
63 this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
69 // construct mapping from the location name to the class descriptor
70 // assume that the location name is unique through the whole program
72 Set<ClassDescriptor> cdSet = ssjava.getCd2lattice().keySet();
73 for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
74 ClassDescriptor cd = (ClassDescriptor) iterator.next();
75 SSJavaLattice<String> lattice = ssjava.getCd2lattice().get(cd);
76 Set<String> fieldLocNameSet = lattice.getKeySet();
78 for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) {
79 String fieldLocName = (String) iterator2.next();
80 fieldLocName2cd.put(fieldLocName, cd);
87 public void flowDownCheck() {
88 SymbolTable classtable = state.getClassSymbolTable();
90 // phase 1 : checking declaration node and creating mapping of 'type
91 // desciptor' & 'location'
92 toanalyze.addAll(classtable.getValueSet());
93 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
94 while (!toanalyze.isEmpty()) {
95 Object obj = toanalyze.iterator().next();
96 ClassDescriptor cd = (ClassDescriptor) obj;
99 if (!cd.isInterface()) {
100 checkDeclarationInClass(cd);
101 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
102 MethodDescriptor md = (MethodDescriptor) method_it.next();
104 checkDeclarationInMethodBody(cd, md);
106 System.out.println("Error in " + md);
114 // phase2 : checking assignments
115 toanalyze.addAll(classtable.getValueSet());
116 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
117 while (!toanalyze.isEmpty()) {
118 Object obj = toanalyze.iterator().next();
119 ClassDescriptor cd = (ClassDescriptor) obj;
120 toanalyze.remove(cd);
123 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
124 MethodDescriptor md = (MethodDescriptor) method_it.next();
126 checkMethodBody(cd, md);
128 System.out.println("Error in " + md);
136 public Hashtable getMap() {
140 private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
141 BlockNode bn = state.getMethodBody(md);
142 for (int i = 0; i < md.numParameters(); i++) {
143 // process annotations on method parameters
144 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
145 assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
147 checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
150 private void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
151 bn.getVarTable().setParent(nametable);
152 for (int i = 0; i < bn.size(); i++) {
153 BlockStatementNode bsn = bn.get(i);
154 checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
158 private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
159 BlockStatementNode bsn) {
161 switch (bsn.kind()) {
162 case Kind.SubBlockNode:
163 checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
166 case Kind.DeclarationNode:
167 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
171 checkDeclarationInLoopNode(md, nametable, (LoopNode) bsn);
176 private void checkDeclarationInLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
178 if (ln.getType() == LoopNode.FORLOOP) {
179 // check for loop case
180 ClassDescriptor cd = md.getClassDesc();
181 BlockNode bn = ln.getInitializer();
182 for (int i = 0; i < bn.size(); i++) {
183 BlockStatementNode bsn = bn.get(i);
184 checkDeclarationInBlockStatementNode(md, nametable, bsn);
189 checkDeclarationInBlockNode(md, nametable, ln.getBody());
192 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
193 BlockNode bn = state.getMethodBody(md);
194 checkLocationFromBlockNode(md, md.getParameterTable(), bn);
197 private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
200 bn.getVarTable().setParent(nametable);
201 // it will return the lowest location in the block node
202 CompositeLocation lowestLoc = null;
203 for (int i = 0; i < bn.size(); i++) {
204 BlockStatementNode bsn = bn.get(i);
205 CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
206 if (lowestLoc == null) {
209 if (!bLoc.isEmpty()) {
210 if (CompositeLattice.isGreaterThan(lowestLoc, bLoc)) {
219 private CompositeLocation checkLocationFromBlockStatementNode(MethodDescriptor md,
220 SymbolTable nametable, BlockStatementNode bsn) {
222 CompositeLocation compLoc = null;
223 switch (bsn.kind()) {
224 case Kind.BlockExpressionNode:
225 compLoc = checkLocationFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
228 case Kind.DeclarationNode:
229 compLoc = checkLocationFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
232 case Kind.IfStatementNode:
233 compLoc = checkLocationFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
237 compLoc = checkLocationFromLoopNode(md, nametable, (LoopNode) bsn);
240 case Kind.ReturnNode:
241 compLoc = checkLocationFromReturnNode(md, nametable, (ReturnNode) bsn);
244 case Kind.SubBlockNode:
245 compLoc = checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
248 // case Kind.ContinueBreakNode:
249 // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
256 private CompositeLocation checkLocationFromReturnNode(MethodDescriptor md, SymbolTable nametable,
258 ClassDescriptor cd = md.getClassDesc();
259 CompositeLocation loc = new CompositeLocation();
261 ExpressionNode returnExp = rn.getReturnExpression();
263 if (rn == null || hasOnlyLiteralValue(returnExp)) {
264 // when it returns literal value, return node has "bottom" location no
265 // matter what it is going to return.
266 loc.addLocation(Location.createBottomLocation(md));
268 loc = checkLocationFromExpressionNode(md, nametable, returnExp, loc);
273 private boolean hasOnlyLiteralValue(ExpressionNode returnExp) {
274 if (returnExp.kind() == Kind.LiteralNode) {
281 private CompositeLocation checkLocationFromLoopNode(MethodDescriptor md, SymbolTable nametable,
284 ClassDescriptor cd = md.getClassDesc();
285 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
287 CompositeLocation condLoc =
288 checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation());
289 addTypeLocation(ln.getCondition().getType(), (condLoc));
291 CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
293 if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc)) {
294 // loop condition should be higher than loop body
296 "The location of the while-condition statement is lower than the loop body at "
297 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
303 // check for loop case
304 BlockNode bn = ln.getInitializer();
305 bn.getVarTable().setParent(nametable);
307 // calculate glb location of condition and update statements
308 CompositeLocation condLoc =
309 checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
310 new CompositeLocation());
311 addTypeLocation(ln.getCondition().getType(), condLoc);
313 CompositeLocation updateLoc =
314 checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
316 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
317 glbInputSet.add(condLoc);
318 glbInputSet.add(updateLoc);
320 CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(glbInputSet);
322 // check location of 'forloop' body
323 CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
325 if (blockLoc == null) {
326 // when there is no statement in the loop body
327 return glbLocOfForLoopCond;
330 if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc)) {
332 "The location of the for-condition statement is lower than the for-loop body at "
333 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
340 private CompositeLocation checkLocationFromSubBlockNode(MethodDescriptor md,
341 SymbolTable nametable, SubBlockNode sbn) {
342 CompositeLocation compLoc = checkLocationFromBlockNode(md, nametable, sbn.getBlockNode());
346 private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md,
347 SymbolTable nametable, IfStatementNode isn) {
349 ClassDescriptor localCD = md.getClassDesc();
350 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
352 CompositeLocation condLoc =
353 checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation());
355 addTypeLocation(isn.getCondition().getType(), condLoc);
356 glbInputSet.add(condLoc);
358 CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
359 glbInputSet.add(locTrueBlock);
361 // here, the location of conditional block should be higher than the
362 // location of true/false blocks
364 if (!CompositeLattice.isGreaterThan(condLoc, locTrueBlock)) {
367 "The location of the if-condition statement is lower than the conditional block at "
368 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
371 if (isn.getFalseBlock() != null) {
372 CompositeLocation locFalseBlock =
373 checkLocationFromBlockNode(md, nametable, isn.getFalseBlock());
374 glbInputSet.add(locFalseBlock);
376 if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock)) {
379 "The location of the if-condition statement is lower than the conditional block at "
380 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
385 // return GLB location of condition, true, and false block
386 CompositeLocation glbLoc = CompositeLattice.calculateGLB(glbInputSet);
391 private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
392 SymbolTable nametable, DeclarationNode dn) {
394 VarDescriptor vd = dn.getVarDescriptor();
396 CompositeLocation destLoc = d2loc.get(vd);
398 ClassDescriptor localCD = md.getClassDesc();
399 if (dn.getExpression() != null) {
400 CompositeLocation expressionLoc =
401 checkLocationFromExpressionNode(md, nametable, dn.getExpression(),
402 new CompositeLocation());
403 addTypeLocation(dn.getExpression().getType(), expressionLoc);
405 if (expressionLoc != null) {
406 // checking location order
407 if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc)) {
408 throw new Error("The value flow from " + expressionLoc + " to " + destLoc
409 + " does not respect location hierarchy on the assignment " + dn.printNode(0)
410 + " at " + md.getClassDesc().getSourceFileName() + "::" + dn.getNumLine());
413 return expressionLoc;
417 // if (destLoc instanceof Location) {
418 // CompositeLocation comp = new CompositeLocation();
419 // comp.addLocation(destLoc);
422 // return (CompositeLocation) destLoc;
430 private void checkDeclarationInSubBlockNode(MethodDescriptor md, SymbolTable nametable,
432 checkDeclarationInBlockNode(md, nametable.getParent(), sbn.getBlockNode());
435 private CompositeLocation checkLocationFromBlockExpressionNode(MethodDescriptor md,
436 SymbolTable nametable, BlockExpressionNode ben) {
437 CompositeLocation compLoc =
438 checkLocationFromExpressionNode(md, nametable, ben.getExpression(), null);
439 // addTypeLocation(ben.getExpression().getType(), compLoc);
443 private CompositeLocation checkLocationFromExpressionNode(MethodDescriptor md,
444 SymbolTable nametable, ExpressionNode en, CompositeLocation loc) {
446 CompositeLocation compLoc = null;
449 case Kind.AssignmentNode:
450 compLoc = checkLocationFromAssignmentNode(md, nametable, (AssignmentNode) en, loc);
453 case Kind.FieldAccessNode:
454 compLoc = checkLocationFromFieldAccessNode(md, nametable, (FieldAccessNode) en, loc);
458 compLoc = checkLocationFromNameNode(md, nametable, (NameNode) en, loc);
462 compLoc = checkLocationFromOpNode(md, nametable, (OpNode) en);
465 case Kind.CreateObjectNode:
466 compLoc = checkLocationFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
469 case Kind.ArrayAccessNode:
470 compLoc = checkLocationFromArrayAccessNode(md, nametable, (ArrayAccessNode) en);
473 case Kind.LiteralNode:
474 compLoc = checkLocationFromLiteralNode(md, nametable, (LiteralNode) en, loc);
477 case Kind.MethodInvokeNode:
478 compLoc = checkLocationFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
481 case Kind.TertiaryNode:
482 compLoc = checkLocationFromTertiaryNode(md, nametable, (TertiaryNode) en);
486 compLoc = checkLocationFromCastNode(md, nametable, (CastNode) en);
489 // case Kind.InstanceOfNode:
490 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
493 // case Kind.ArrayInitializerNode:
494 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
498 // case Kind.ClassTypeNode:
499 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
502 // case Kind.OffsetNode:
503 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
510 // addTypeLocation(en.getType(), compLoc);
515 private CompositeLocation checkLocationFromCastNode(MethodDescriptor md, SymbolTable nametable,
518 ExpressionNode en = cn.getExpression();
519 return checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
523 private CompositeLocation checkLocationFromTertiaryNode(MethodDescriptor md,
524 SymbolTable nametable, TertiaryNode tn) {
525 ClassDescriptor cd = md.getClassDesc();
527 CompositeLocation condLoc =
528 checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation());
529 addTypeLocation(tn.getCond().getType(), condLoc);
530 CompositeLocation trueLoc =
531 checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation());
532 addTypeLocation(tn.getTrueExpr().getType(), trueLoc);
533 CompositeLocation falseLoc =
534 checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation());
535 addTypeLocation(tn.getFalseExpr().getType(), falseLoc);
537 // check if condLoc is higher than trueLoc & falseLoc
538 if (!CompositeLattice.isGreaterThan(condLoc, trueLoc)) {
540 "The location of the condition expression is lower than the true expression at "
541 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
544 if (!CompositeLattice.isGreaterThan(condLoc, falseLoc)) {
546 "The location of the condition expression is lower than the true expression at "
547 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
550 // then, return glb of trueLoc & falseLoc
551 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
552 glbInputSet.add(trueLoc);
553 glbInputSet.add(falseLoc);
555 return CompositeLattice.calculateGLB(glbInputSet);
558 private CompositeLocation checkLocationFromMethodInvokeNode(MethodDescriptor md,
559 SymbolTable nametable, MethodInvokeNode min) {
561 // Location baseLoc = null;
562 // if (min.getBaseName() != null) {
563 // Descriptor d = nametable.get(min.getBaseName().getSymbol());
564 // if (d instanceof VarDescriptor) {
565 // CompositeLocation varLoc = (CompositeLocation) ((VarDescriptor)
566 // d).getType().getExtension();
569 // // it is field descriptor
570 // assert (d instanceof FieldDescriptor);
571 // CompositeLocation fieldLoc =
572 // (CompositeLocation) min.getExpression().getType().getExtension();
576 // // method invocation starting from this
577 // MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
578 // System.out.println("md=" + md + " lattice=" + methodLattice);
579 // String thisLocId = methodLattice.getThisLoc();
580 // baseLoc = new Location(md, thisLocId);
582 // System.out.println("BASE LOC=" + baseLoc);
584 if (min.numArgs() > 1) {
585 // caller needs to guarantee that it passes arguments in regarding to
586 // callee's hierarchy
587 for (int i = 0; i < min.numArgs(); i++) {
588 ExpressionNode en = min.getArg(i);
589 CompositeLocation callerArg1 =
590 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
592 ClassDescriptor calleecd = min.getMethod().getClassDesc();
593 VarDescriptor calleevd = (VarDescriptor) min.getMethod().getParameter(i);
594 CompositeLocation calleeLoc1 = d2loc.get(calleevd);
596 if (!callerArg1.get(0).isTop()) {
597 // here, check if ordering relations among caller's args respect
598 // ordering relations in-between callee's args
599 for (int currentIdx = 0; currentIdx < min.numArgs(); currentIdx++) {
600 if (currentIdx != i) { // skip itself
601 ExpressionNode argExp = min.getArg(currentIdx);
603 CompositeLocation callerArg2 =
604 checkLocationFromExpressionNode(md, nametable, argExp, new CompositeLocation());
606 VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
607 CompositeLocation calleeLoc2 = d2loc.get(calleevd2);
609 boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2);
610 boolean calleeResult = CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2);
612 if (calleeResult && !callerResult) {
613 // If calleeLoc1 is higher than calleeLoc2
614 // then, caller should have same ordering relation in-bet
615 // callerLoc1 & callerLoc2
617 throw new Error("Caller doesn't respect ordering relations among method arguments:"
618 + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine());
629 // all arguments should be higher than the location of return value
631 Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
632 for (int i = 0; i < min.numArgs(); i++) {
633 ExpressionNode en = min.getArg(i);
634 CompositeLocation callerArg =
635 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
636 inputGLBSet.add(callerArg);
639 if (inputGLBSet.size() > 0) {
640 return CompositeLattice.calculateGLB(inputGLBSet);
642 // if there are no arguments,
643 // method invocation from the same class
644 CompositeLocation compLoc = new CompositeLocation();
650 private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
651 SymbolTable nametable, ArrayAccessNode aan) {
653 // return glb location of array itself and index
655 ClassDescriptor cd = md.getClassDesc();
657 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
659 CompositeLocation arrayLoc =
660 checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation());
661 addTypeLocation(aan.getExpression().getType(), arrayLoc);
662 glbInputSet.add(arrayLoc);
663 CompositeLocation indexLoc =
664 checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation());
665 glbInputSet.add(indexLoc);
666 addTypeLocation(aan.getIndex().getType(), indexLoc);
668 CompositeLocation glbLoc = CompositeLattice.calculateGLB(glbInputSet);
672 private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
673 SymbolTable nametable, CreateObjectNode con) {
675 ClassDescriptor cd = md.getClassDesc();
678 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
679 for (int i = 0; i < con.numArgs(); i++) {
680 ExpressionNode en = con.getArg(i);
681 CompositeLocation argLoc =
682 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
683 glbInputSet.add(argLoc);
684 addTypeLocation(en.getType(), argLoc);
687 // check array initializers
688 // if ((con.getArrayInitializer() != null)) {
689 // checkLocationFromArrayInitializerNode(md, nametable,
690 // con.getArrayInitializer());
693 if (glbInputSet.size() > 0) {
694 return CompositeLattice.calculateGLB(glbInputSet);
697 CompositeLocation compLoc = new CompositeLocation();
698 compLoc.addLocation(Location.createTopLocation(md));
703 private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
706 ClassDescriptor cd = md.getClassDesc();
707 CompositeLocation leftLoc = new CompositeLocation();
708 leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
709 // addTypeLocation(on.getLeft().getType(), leftLoc);
711 CompositeLocation rightLoc = new CompositeLocation();
712 if (on.getRight() != null) {
713 rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
714 // addTypeLocation(on.getRight().getType(), rightLoc);
717 // System.out.println("checking op node=" + on.printNode(0));
718 // System.out.println("left loc=" + leftLoc + " from " +
719 // on.getLeft().getClass());
720 // System.out.println("right loc=" + rightLoc + " from " +
721 // on.getRight().getClass());
723 Operation op = on.getOp();
725 switch (op.getOp()) {
727 case Operation.UNARYPLUS:
728 case Operation.UNARYMINUS:
729 case Operation.LOGIC_NOT:
733 case Operation.LOGIC_OR:
734 case Operation.LOGIC_AND:
736 case Operation.BIT_OR:
737 case Operation.BIT_XOR:
738 case Operation.BIT_AND:
739 case Operation.ISAVAILABLE:
740 case Operation.EQUAL:
741 case Operation.NOTEQUAL:
751 case Operation.LEFTSHIFT:
752 case Operation.RIGHTSHIFT:
753 case Operation.URIGHTSHIFT:
755 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
756 inputSet.add(leftLoc);
757 inputSet.add(rightLoc);
758 CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(inputSet);
762 throw new Error(op.toString());
767 private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
768 SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
770 // literal value has the top location so that value can be flowed into any
772 Location literalLoc = Location.createTopLocation(md);
773 loc.addLocation(literalLoc);
778 private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
779 NameNode nn, CompositeLocation loc) {
781 NameDescriptor nd = nn.getName();
782 if (nd.getBase() != null) {
783 loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
784 // addTypeLocation(nn.getExpression().getType(), loc);
786 String varname = nd.toString();
788 if (varname.equals("this")) {
790 MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
791 Location locElement = new Location(md, methodLattice.getThisLoc());
792 loc.addLocation(locElement);
795 Descriptor d = (Descriptor) nametable.get(varname);
797 // CompositeLocation localLoc = null;
798 if (d instanceof VarDescriptor) {
799 VarDescriptor vd = (VarDescriptor) d;
800 // localLoc = d2loc.get(vd);
801 // the type of var descriptor has a composite location!
802 loc = (CompositeLocation) vd.getType().getExtension();
803 } else if (d instanceof FieldDescriptor) {
804 // the type of field descriptor has a location!
805 FieldDescriptor fd = (FieldDescriptor) d;
807 // the location of field access starts from this, followed by field
809 MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
810 Location thisLoc = new Location(md, localLattice.getThisLoc());
811 loc.addLocation(thisLoc);
812 Location fieldLoc = (Location) fd.getType().getExtension();
813 loc.addLocation(fieldLoc);
820 private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
821 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
823 ExpressionNode left = fan.getExpression();
824 loc = checkLocationFromExpressionNode(md, nametable, left, loc);
825 // addTypeLocation(left.getType(), loc);
827 if (!left.getType().isPrimitive()) {
828 FieldDescriptor fd = fan.getField();
829 Location fieldLoc = (Location) fd.getType().getExtension();
830 loc.addLocation(fieldLoc);
836 private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
837 SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
839 ClassDescriptor cd = md.getClassDesc();
841 boolean postinc = true;
842 if (an.getOperation().getBaseOp() == null
843 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
844 .getBaseOp().getOp() != Operation.POSTDEC))
847 CompositeLocation destLocation =
848 checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation());
850 CompositeLocation srcLocation = new CompositeLocation();
852 srcLocation = new CompositeLocation();
853 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
854 // System.out.println("an=" + an.printNode(0) + " an.getSrc()=" +
855 // an.getSrc().getClass()
856 // + " at " + cd.getSourceFileName() + "::" + an.getNumLine());
857 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
858 throw new Error("The value flow from " + srcLocation + " to " + destLocation
859 + " does not respect location hierarchy on the assignment " + an.printNode(0) + " at "
860 + cd.getSourceFileName() + "::" + an.getNumLine());
864 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
866 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
867 throw new Error("Location " + destLocation
868 + " is not allowed to have the value flow that moves within the same location at "
869 + cd.getSourceFileName() + "::" + an.getNumLine());
877 private void assignLocationOfVarDescriptor(VarDescriptor vd, MethodDescriptor md,
878 SymbolTable nametable, TreeNode n) {
880 ClassDescriptor cd = md.getClassDesc();
881 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
883 // currently enforce every variable to have corresponding location
884 if (annotationVec.size() == 0) {
885 throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
886 + md.getSymbol() + " of the class " + cd.getSymbol());
889 if (annotationVec.size() > 1) { // variable can have at most one location
890 throw new Error(vd.getSymbol() + " has more than one location.");
893 AnnotationDescriptor ad = annotationVec.elementAt(0);
895 if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
897 if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
898 String locDec = ad.getValue(); // check if location is defined
900 if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
901 DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
902 d2loc.put(vd, deltaLoc);
903 addTypeLocation(vd.getType(), deltaLoc);
905 CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
906 d2loc.put(vd, compLoc);
907 addTypeLocation(vd.getType(), compLoc);
915 private DeltaLocation parseDeltaDeclaration(MethodDescriptor md, TreeNode n, String locDec) {
918 int dIdx = locDec.indexOf(SSJavaAnalysis.DELTA);
921 int beginIdx = dIdx + 6;
922 locDec = locDec.substring(beginIdx, locDec.length() - 1);
923 dIdx = locDec.indexOf(SSJavaAnalysis.DELTA);
926 CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
927 DeltaLocation deltaLoc = new DeltaLocation(compLoc, deltaCount);
932 private CompositeLocation parseLocationDeclaration(MethodDescriptor md, TreeNode n, String locDec) {
934 CompositeLocation compLoc = new CompositeLocation();
936 StringTokenizer tokenizer = new StringTokenizer(locDec, ",");
937 List<String> locIdList = new ArrayList<String>();
938 while (tokenizer.hasMoreTokens()) {
939 String locId = tokenizer.nextToken();
940 locIdList.add(locId);
943 // at least,one location element needs to be here!
944 assert (locIdList.size() > 0);
946 // assume that loc with idx 0 comes from the local lattice
947 // loc with idx 1 comes from the field lattice
949 String localLocId = locIdList.get(0);
950 SSJavaLattice<String> localLattice = CompositeLattice.getLatticeByDescriptor(md);
951 Location localLoc = new Location(md, localLocId);
952 if (localLattice == null || (!localLattice.containsKey(localLocId))) {
953 throw new Error("Location " + localLocId
954 + " is not defined in the local variable lattice at "
955 + md.getClassDesc().getSourceFileName() + "::" + n.getNumLine() + ".");
957 compLoc.addLocation(localLoc);
959 for (int i = 1; i < locIdList.size(); i++) {
960 String locName = locIdList.get(i);
961 ClassDescriptor cd = fieldLocName2cd.get(locName);
963 SSJavaLattice<String> fieldLattice = CompositeLattice.getLatticeByDescriptor(cd);
965 if (fieldLattice == null || (!fieldLattice.containsKey(locName))) {
966 throw new Error("Location " + locName + " is not defined in the field lattice at "
967 + cd.getSourceFileName() + ".");
970 Location fieldLoc = new Location(cd, locName);
971 compLoc.addLocation(fieldLoc);
978 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
979 VarDescriptor vd = dn.getVarDescriptor();
980 assignLocationOfVarDescriptor(vd, md, nametable, dn);
983 private void checkClass(ClassDescriptor cd) {
984 // Check to see that methods respects ss property
985 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
986 MethodDescriptor md = (MethodDescriptor) method_it.next();
987 checkMethodDeclaration(cd, md);
991 private void checkDeclarationInClass(ClassDescriptor cd) {
992 // Check to see that fields are okay
993 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
994 FieldDescriptor fd = (FieldDescriptor) field_it.next();
995 checkFieldDeclaration(cd, fd);
999 private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
1003 private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
1005 Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
1007 // currently enforce every field to have corresponding location
1008 if (annotationVec.size() == 0) {
1009 throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
1013 if (annotationVec.size() > 1) {
1014 // variable can have at most one location
1015 throw new Error("Field " + fd.getSymbol() + " of class " + cd
1016 + " has more than one location.");
1019 AnnotationDescriptor ad = annotationVec.elementAt(0);
1021 if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
1023 if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
1024 String locationID = ad.getValue();
1025 // check if location is defined
1026 SSJavaLattice<String> lattice = ssjava.getClassLattice(cd);
1027 if (lattice == null || (!lattice.containsKey(locationID))) {
1028 throw new Error("Location " + locationID
1029 + " is not defined in the field lattice of class " + cd.getSymbol() + " at"
1030 + cd.getSourceFileName() + ".");
1032 Location loc = new Location(cd, locationID);
1033 // d2loc.put(fd, loc);
1034 addTypeLocation(fd.getType(), loc);
1041 private void addTypeLocation(TypeDescriptor type, CompositeLocation loc) {
1043 type.setExtension(loc);
1047 private void addTypeLocation(TypeDescriptor type, Location loc) {
1049 type.setExtension(loc);
1053 static class CompositeLattice {
1055 public static boolean isGreaterThan(CompositeLocation loc1, CompositeLocation loc2) {
1057 int baseCompareResult = compareBaseLocationSet(loc1, loc2);
1058 if (baseCompareResult == ComparisonResult.EQUAL) {
1059 if (compareDelta(loc1, loc2) == ComparisonResult.GREATER) {
1064 } else if (baseCompareResult == ComparisonResult.GREATER) {
1072 private static int compareDelta(CompositeLocation dLoc1, CompositeLocation dLoc2) {
1074 int deltaCount1 = 0;
1075 int deltaCount2 = 0;
1076 if (dLoc1 instanceof DeltaLocation) {
1077 deltaCount1 = ((DeltaLocation) dLoc1).getNumDelta();
1080 if (dLoc2 instanceof DeltaLocation) {
1081 deltaCount2 = ((DeltaLocation) dLoc2).getNumDelta();
1083 if (deltaCount1 < deltaCount2) {
1084 return ComparisonResult.GREATER;
1085 } else if (deltaCount1 == deltaCount2) {
1086 return ComparisonResult.EQUAL;
1088 return ComparisonResult.LESS;
1093 private static int compareBaseLocationSet(CompositeLocation compLoc1, CompositeLocation compLoc2) {
1095 // if compLoc1 is greater than compLoc2, return true
1096 // else return false;
1098 // compare one by one in according to the order of the tuple
1100 for (int i = 0; i < compLoc1.getSize(); i++) {
1101 Location loc1 = compLoc1.get(i);
1102 if (i >= compLoc2.getSize()) {
1103 throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1104 + " because they are not comparable.");
1106 Location loc2 = compLoc2.get(i);
1108 if (!loc1.getDescriptor().equals(loc2.getDescriptor())) {
1109 throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1110 + " because they are not comparable.");
1113 Descriptor d1 = loc1.getDescriptor();
1114 Descriptor d2 = loc2.getDescriptor();
1116 SSJavaLattice<String> lattice1 = getLatticeByDescriptor(d1);
1117 SSJavaLattice<String> lattice2 = getLatticeByDescriptor(d2);
1119 if (!lattice1.equals(lattice2)) {
1120 throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1121 + " because they are not comparable.");
1124 if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1125 // check if the current location is the spinning location
1126 if (lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
1127 return ComparisonResult.GREATER;
1131 } else if (lattice1.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1132 return ComparisonResult.GREATER;
1134 return ComparisonResult.LESS;
1139 if (numOfTie == compLoc1.getSize()) {
1141 if (numOfTie != compLoc2.getSize()) {
1142 throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1143 + " because they are not comparable.");
1146 return ComparisonResult.EQUAL;
1149 return ComparisonResult.LESS;
1153 public static CompositeLocation calculateGLB(Set<CompositeLocation> inputSet) {
1155 // System.out.println("Calculating GLB=" + inputSet);
1156 CompositeLocation glbCompLoc = new CompositeLocation();
1158 // calculate GLB of the first(priority) element
1159 Set<String> priorityLocIdentifierSet = new HashSet<String>();
1160 Descriptor priorityDescriptor = null;
1162 Hashtable<String, Set<CompositeLocation>> locId2CompLocSet =
1163 new Hashtable<String, Set<CompositeLocation>>();
1164 // mapping from the priority loc ID to its full representation by the
1165 // composite location
1167 for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1168 CompositeLocation compLoc = (CompositeLocation) iterator.next();
1169 Location priorityLoc = compLoc.get(0);
1170 String priorityLocId = priorityLoc.getLocIdentifier();
1171 priorityLocIdentifierSet.add(priorityLocId);
1173 if (locId2CompLocSet.contains(priorityLocId)) {
1174 locId2CompLocSet.get(priorityLocId).add(compLoc);
1176 Set<CompositeLocation> newSet = new HashSet<CompositeLocation>();
1177 newSet.add(compLoc);
1178 locId2CompLocSet.put(priorityLocId, newSet);
1181 // check if priority location are coming from the same lattice
1182 if (priorityDescriptor == null) {
1183 priorityDescriptor = priorityLoc.getDescriptor();
1184 } else if (!priorityDescriptor.equals(priorityLoc.getDescriptor())) {
1185 throw new Error("Failed to calculate GLB of " + inputSet
1186 + " because they are from different lattices.");
1190 SSJavaLattice<String> locOrder = getLatticeByDescriptor(priorityDescriptor);
1191 String glbOfPriorityLoc = locOrder.getGLB(priorityLocIdentifierSet);
1193 glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc));
1195 Set<CompositeLocation> compSet = locId2CompLocSet.get(glbOfPriorityLoc);
1197 if (compSet.size() == 1) {
1198 // if GLB(x1,x2)==x1 or x2 : GLB case 2,3
1199 CompositeLocation comp = compSet.iterator().next();
1200 for (int i = 1; i < comp.getSize(); i++) {
1201 glbCompLoc.addLocation(comp.get(i));
1203 } else if (compSet.size() == 0) {
1204 // when GLB(x1,x2)!=x1 and !=x2 : GLB case 4
1205 // mean that the result is already lower than <x1,y1> and <x2,y2>
1206 // assign TOP to the rest of the location elements
1207 CompositeLocation inputComp = inputSet.iterator().next();
1208 for (int i = 1; i < inputComp.getSize(); i++) {
1209 glbCompLoc.addLocation(Location.createTopLocation(inputComp.get(i).getDescriptor()));
1212 // when GLB(x1,x2)==x1 and x2 : GLB case 1
1213 // if more than one location shares the same priority GLB
1214 // need to calculate the rest of GLB loc
1216 int compositeLocSize = compSet.iterator().next().getSize();
1218 Set<String> glbInputSet = new HashSet<String>();
1219 Descriptor currentD = null;
1220 for (int i = 1; i < compositeLocSize; i++) {
1221 for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
1222 CompositeLocation compositeLocation = (CompositeLocation) iterator.next();
1223 Location currentLoc = compositeLocation.get(i);
1224 currentD = currentLoc.getDescriptor();
1225 // making set of the current location sharing the same idx
1226 glbInputSet.add(currentLoc.getLocIdentifier());
1228 // calculate glb for the current lattice
1230 SSJavaLattice<String> currentLattice = getLatticeByDescriptor(currentD);
1231 String currentGLBLocId = currentLattice.getGLB(glbInputSet);
1232 glbCompLoc.addLocation(new Location(currentD, currentGLBLocId));
1241 static SSJavaLattice<String> getLatticeByDescriptor(Descriptor d) {
1243 SSJavaLattice<String> lattice = null;
1245 if (d instanceof ClassDescriptor) {
1246 lattice = ssjava.getCd2lattice().get(d);
1247 } else if (d instanceof MethodDescriptor) {
1248 if (ssjava.getMd2lattice().containsKey(d)) {
1249 lattice = ssjava.getMd2lattice().get(d);
1251 // use default lattice for the method
1252 lattice = ssjava.getCd2methodDefault().get(((MethodDescriptor) d).getClassDesc());
1261 class ComparisonResult {
1263 public static final int GREATER = 0;
1264 public static final int EQUAL = 1;
1265 public static final int LESS = 2;