1 package Analysis.SSJava;
3 import java.util.ArrayList;
4 import java.util.HashSet;
5 import java.util.Hashtable;
6 import java.util.Iterator;
10 import java.util.StringTokenizer;
11 import java.util.Vector;
13 import IR.AnnotationDescriptor;
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.TertiaryNode;
44 import IR.Tree.TreeNode;
47 public class FlowDownCheck {
51 Hashtable<Descriptor, Location> td2loc; // mapping from 'type descriptor'
53 Hashtable<String, ClassDescriptor> id2cd; // mapping from 'locID' to 'class
56 public FlowDownCheck(State state) {
58 this.toanalyze = new HashSet();
59 this.td2loc = new Hashtable<Descriptor, Location>();
64 id2cd = new Hashtable<String, ClassDescriptor>();
65 Hashtable cd2lattice = state.getCd2LocationOrder();
67 Set cdSet = cd2lattice.keySet();
68 for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
69 ClassDescriptor cd = (ClassDescriptor) iterator.next();
70 Lattice<String> lattice = (Lattice<String>) cd2lattice.get(cd);
72 Set<String> locIdSet = lattice.getKeySet();
73 for (Iterator iterator2 = locIdSet.iterator(); iterator2.hasNext();) {
74 String locID = (String) iterator2.next();
81 public void flowDownCheck() {
82 SymbolTable classtable = state.getClassSymbolTable();
84 // phase 1 : checking declaration node and creating mapping of 'type
85 // desciptor' & 'location'
86 toanalyze.addAll(classtable.getValueSet());
87 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
88 while (!toanalyze.isEmpty()) {
89 Object obj = toanalyze.iterator().next();
90 ClassDescriptor cd = (ClassDescriptor) obj;
93 if (!cd.isInterface()) {
94 checkDeclarationInClass(cd);
95 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
96 MethodDescriptor md = (MethodDescriptor) method_it.next();
98 checkDeclarationInMethodBody(cd, md);
100 System.out.println("Error in " + md);
108 // post-processing for delta location
109 // for a nested delta location, assigning a concrete reference to delta
111 Set<Descriptor> tdSet = td2loc.keySet();
112 for (Iterator iterator = tdSet.iterator(); iterator.hasNext();) {
113 Descriptor td = (Descriptor) iterator.next();
114 Location loc = td2loc.get(td);
116 if (loc.getType() == Location.DELTA) {
117 // if it contains delta reference pointing to another location element
118 CompositeLocation compLoc = (CompositeLocation) loc;
120 Location locElement = compLoc.getTuple().at(0);
121 assert (locElement instanceof DeltaLocation);
123 DeltaLocation delta = (DeltaLocation) locElement;
124 Descriptor refType = delta.getRefLocationId();
125 if (refType != null) {
126 Location refLoc = td2loc.get(refType);
128 assert (refLoc instanceof CompositeLocation);
129 CompositeLocation refCompLoc = (CompositeLocation) refLoc;
131 assert (refCompLoc.getTuple().at(0) instanceof DeltaLocation);
132 DeltaLocation refDelta = (DeltaLocation) refCompLoc.getTuple().at(0);
134 delta.addDeltaOperand(refDelta);
135 // compLoc.addLocation(refDelta);
141 // phase2 : checking assignments
142 toanalyze.addAll(classtable.getValueSet());
143 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
144 while (!toanalyze.isEmpty()) {
145 Object obj = toanalyze.iterator().next();
146 ClassDescriptor cd = (ClassDescriptor) obj;
147 toanalyze.remove(cd);
150 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
151 MethodDescriptor md = (MethodDescriptor) method_it.next();
153 checkMethodBody(cd, md);
155 System.out.println("Error in " + md);
163 public Hashtable getMap() {
167 private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
168 BlockNode bn = state.getMethodBody(md);
169 for (int i = 0; i < md.numParameters(); i++) {
170 // process annotations on method parameters
171 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
172 assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
174 checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
177 private void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
178 bn.getVarTable().setParent(nametable);
179 for (int i = 0; i < bn.size(); i++) {
180 BlockStatementNode bsn = bn.get(i);
181 checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
185 private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
186 BlockStatementNode bsn) {
188 switch (bsn.kind()) {
189 case Kind.SubBlockNode:
190 checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
193 case Kind.DeclarationNode:
194 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
198 checkDeclarationInLoopNode(md, nametable, (LoopNode) bsn);
203 private void checkDeclarationInLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
205 if (ln.getType() == LoopNode.FORLOOP) {
206 // check for loop case
207 ClassDescriptor cd = md.getClassDesc();
208 BlockNode bn = ln.getInitializer();
209 for (int i = 0; i < bn.size(); i++) {
210 BlockStatementNode bsn = bn.get(i);
211 checkDeclarationInBlockStatementNode(md, nametable, bsn);
216 checkDeclarationInBlockNode(md, nametable, ln.getBody());
219 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
220 BlockNode bn = state.getMethodBody(md);
221 checkLocationFromBlockNode(md, md.getParameterTable(), bn);
224 private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
227 bn.getVarTable().setParent(nametable);
228 // it will return the lowest location in the block node
229 CompositeLocation lowestLoc = null;
230 for (int i = 0; i < bn.size(); i++) {
231 BlockStatementNode bsn = bn.get(i);
232 CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
234 if (lowestLoc == null) {
237 if (CompositeLattice.isGreaterThan(lowestLoc, bLoc, md.getClassDesc())) {
245 private CompositeLocation checkLocationFromBlockStatementNode(MethodDescriptor md,
246 SymbolTable nametable, BlockStatementNode bsn) {
248 CompositeLocation compLoc = null;
249 switch (bsn.kind()) {
250 case Kind.BlockExpressionNode:
251 compLoc = checkLocationFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
254 case Kind.DeclarationNode:
255 compLoc = checkLocationFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
258 case Kind.IfStatementNode:
259 compLoc = checkLocationFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
263 compLoc = checkLocationFromLoopNode(md, nametable, (LoopNode) bsn);
266 case Kind.ReturnNode:
267 compLoc = checkLocationFromReturnNode(md, nametable, (ReturnNode) bsn);
270 case Kind.SubBlockNode:
271 compLoc = checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
274 // case Kind.ContinueBreakNode:
275 // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
282 private CompositeLocation checkLocationFromReturnNode(MethodDescriptor md, SymbolTable nametable,
284 ClassDescriptor cd = md.getClassDesc();
285 CompositeLocation loc = new CompositeLocation(cd);
287 ExpressionNode returnExp = rn.getReturnExpression();
289 if (rn == null || hasOnlyLiteralValue(returnExp)) {
290 // when it returns literal value, return node has "bottom" location no
291 // matter what it is going to return.
292 loc.addLocation(Location.createBottomLocation(cd));
294 loc = checkLocationFromExpressionNode(md, nametable, returnExp, loc);
299 private boolean hasOnlyLiteralValue(ExpressionNode returnExp) {
300 if (returnExp.kind() == Kind.LiteralNode) {
307 private CompositeLocation checkLocationFromLoopNode(MethodDescriptor md, SymbolTable nametable,
310 ClassDescriptor cd = md.getClassDesc();
311 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
313 CompositeLocation condLoc =
314 checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation(
316 addTypeLocation(ln.getCondition().getType(), (condLoc));
318 CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
320 if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc, cd)) {
321 // loop condition should be higher than loop body
323 "The location of the while-condition statement is lower than the loop body at "
324 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
330 // check for loop case
331 BlockNode bn = ln.getInitializer();
332 bn.getVarTable().setParent(nametable);
334 // calculate glb location of condition and update statements
335 CompositeLocation condLoc =
336 checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
337 new CompositeLocation(cd));
338 addTypeLocation(ln.getCondition().getType(), condLoc);
340 CompositeLocation updateLoc =
341 checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
343 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
344 glbInputSet.add(condLoc);
345 glbInputSet.add(updateLoc);
347 CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
349 // check location of 'forloop' body
350 CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
352 if (blockLoc == null) {
353 // when there is no statement in the loop body
354 return glbLocOfForLoopCond;
357 if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc, cd)) {
359 "The location of the for-condition statement is lower than the for-loop body at "
360 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
367 private CompositeLocation checkLocationFromSubBlockNode(MethodDescriptor md,
368 SymbolTable nametable, SubBlockNode sbn) {
369 CompositeLocation compLoc = checkLocationFromBlockNode(md, nametable, sbn.getBlockNode());
373 private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md,
374 SymbolTable nametable, IfStatementNode isn) {
376 ClassDescriptor localCD = md.getClassDesc();
377 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
379 CompositeLocation condLoc =
380 checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation(
382 addTypeLocation(isn.getCondition().getType(), condLoc);
383 glbInputSet.add(condLoc);
385 CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
386 glbInputSet.add(locTrueBlock);
388 // here, the location of conditional block should be higher than the
389 // location of true/false blocks
391 if (!CompositeLattice.isGreaterThan(condLoc, locTrueBlock, localCD)) {
394 "The location of the if-condition statement is lower than the conditional block at "
395 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
398 if (isn.getFalseBlock() != null) {
399 CompositeLocation locFalseBlock =
400 checkLocationFromBlockNode(md, nametable, isn.getFalseBlock());
401 glbInputSet.add(locFalseBlock);
403 if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock, localCD)) {
406 "The location of the if-condition statement is lower than the conditional block at "
407 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
412 // return GLB location of condition, true, and false block
413 CompositeLocation glbLoc = CompositeLattice.calculateGLB(localCD, glbInputSet, localCD);
418 private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
419 SymbolTable nametable, DeclarationNode dn) {
420 VarDescriptor vd = dn.getVarDescriptor();
422 Location destLoc = td2loc.get(vd);
424 ClassDescriptor localCD = md.getClassDesc();
425 if (dn.getExpression() != null) {
426 CompositeLocation expressionLoc =
427 checkLocationFromExpressionNode(md, nametable, dn.getExpression(), new CompositeLocation(
429 addTypeLocation(dn.getExpression().getType(), expressionLoc);
431 if (expressionLoc != null) {
432 // checking location order
433 if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc, localCD)) {
434 throw new Error("The value flow from " + expressionLoc + " to " + destLoc
435 + " does not respect location hierarchy on the assignment " + dn.printNode(0)
436 + " at " + md.getClassDesc().getSourceFileName() + "::" + dn.getNumLine());
439 return expressionLoc;
443 if (destLoc instanceof Location) {
444 CompositeLocation comp = new CompositeLocation(localCD);
445 comp.addLocation(destLoc);
448 return (CompositeLocation) destLoc;
455 private void checkDeclarationInSubBlockNode(MethodDescriptor md, SymbolTable nametable,
457 checkDeclarationInBlockNode(md, nametable.getParent(), sbn.getBlockNode());
460 private CompositeLocation checkLocationFromBlockExpressionNode(MethodDescriptor md,
461 SymbolTable nametable, BlockExpressionNode ben) {
462 CompositeLocation compLoc =
463 checkLocationFromExpressionNode(md, nametable, ben.getExpression(), null);
464 addTypeLocation(ben.getExpression().getType(), compLoc);
468 private CompositeLocation checkLocationFromExpressionNode(MethodDescriptor md,
469 SymbolTable nametable, ExpressionNode en, CompositeLocation loc) {
471 CompositeLocation compLoc = null;
474 case Kind.AssignmentNode:
475 compLoc = checkLocationFromAssignmentNode(md, nametable, (AssignmentNode) en, loc);
478 case Kind.FieldAccessNode:
479 compLoc = checkLocationFromFieldAccessNode(md, nametable, (FieldAccessNode) en, loc);
483 compLoc = checkLocationFromNameNode(md, nametable, (NameNode) en, loc);
487 compLoc = checkLocationFromOpNode(md, nametable, (OpNode) en);
490 case Kind.CreateObjectNode:
491 compLoc = checkLocationFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
494 case Kind.ArrayAccessNode:
495 compLoc = checkLocationFromArrayAccessNode(md, nametable, (ArrayAccessNode) en);
498 case Kind.LiteralNode:
499 compLoc = checkLocationFromLiteralNode(md, nametable, (LiteralNode) en, loc);
502 case Kind.MethodInvokeNode:
503 compLoc = checkLocationFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
506 case Kind.TertiaryNode:
507 compLoc = checkLocationFromTertiaryNode(md, nametable, (TertiaryNode) en);
511 compLoc = checkLocationFromCastNode(md, nametable, (CastNode) en);
514 // case Kind.InstanceOfNode:
515 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
518 // case Kind.ArrayInitializerNode:
519 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
523 // case Kind.ClassTypeNode:
524 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
527 // case Kind.OffsetNode:
528 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
536 addTypeLocation(en.getType(), compLoc);
541 private CompositeLocation checkLocationFromCastNode(MethodDescriptor md, SymbolTable nametable,
544 ExpressionNode en = cn.getExpression();
545 return checkLocationFromExpressionNode(md, nametable, en,
546 new CompositeLocation(md.getClassDesc()));
550 private CompositeLocation checkLocationFromTertiaryNode(MethodDescriptor md,
551 SymbolTable nametable, TertiaryNode tn) {
552 ClassDescriptor cd = md.getClassDesc();
554 CompositeLocation condLoc =
555 checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation(cd));
556 addTypeLocation(tn.getCond().getType(), condLoc);
557 CompositeLocation trueLoc =
558 checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation(cd));
559 addTypeLocation(tn.getTrueExpr().getType(), trueLoc);
560 CompositeLocation falseLoc =
561 checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation(cd));
562 addTypeLocation(tn.getFalseExpr().getType(), falseLoc);
564 // check if condLoc is higher than trueLoc & falseLoc
565 if (!CompositeLattice.isGreaterThan(condLoc, trueLoc, cd)) {
567 "The location of the condition expression is lower than the true expression at "
568 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
571 if (!CompositeLattice.isGreaterThan(condLoc, falseLoc, cd)) {
573 "The location of the condition expression is lower than the true expression at "
574 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
577 // then, return glb of trueLoc & falseLoc
578 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
579 glbInputSet.add(trueLoc);
580 glbInputSet.add(falseLoc);
582 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
585 private CompositeLocation convertCompositeLocation(Location l, ClassDescriptor c) {
586 if (l instanceof CompositeLocation) {
587 return (CompositeLocation) l;
589 CompositeLocation returnLoc = new CompositeLocation(c);
590 returnLoc.addLocation(l);
595 private CompositeLocation checkLocationFromMethodInvokeNode(MethodDescriptor md,
596 SymbolTable nametable, MethodInvokeNode min) {
598 ClassDescriptor cd = md.getClassDesc();
600 CompositeLocation baseLoc = null;
601 if (min.getBaseName() != null) {
602 if (nametable.contains(min.getBaseName().getSymbol())) {
603 Location loc = td2loc.get(nametable.get(min.getBaseName().getSymbol()));
605 baseLoc = convertCompositeLocation(loc, cd);
610 Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
611 for (int i = 0; i < min.numArgs(); i++) {
612 ExpressionNode en = min.getArg(i);
613 CompositeLocation callerArg =
614 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
615 inputGLBSet.add(callerArg);
618 // ex) base.method(arg1,arg2,arg3) -> the location of base should be lower
620 // GLB(arg1,arg2,arg3)
621 CompositeLocation argGLBLoc = null;
622 if (inputGLBSet.size() > 0) {
623 argGLBLoc = CompositeLattice.calculateGLB(cd, inputGLBSet, cd);
624 if (baseLoc != null) {
625 if (!CompositeLattice.isGreaterThan(argGLBLoc, baseLoc, cd)) {
626 throw new Error("The base location of method invocation " + min.printNode(0)
627 + " is higher than its argument's location at " + cd.getSourceFileName() + "::"
633 if (min.numArgs() > 1) {
635 // caller needs to guarantee that it passes arguments in regarding to
636 // callee's hierarchy
638 for (int i = 0; i < min.numArgs(); i++) {
639 ExpressionNode en = min.getArg(i);
640 CompositeLocation callerArg1 =
641 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
643 ClassDescriptor calleecd = min.getMethod().getClassDesc();
644 VarDescriptor calleevd = (VarDescriptor) min.getMethod().getParameter(i);
645 Location calleeLoc1 = td2loc.get(calleevd);
647 if (!callerArg1.getLocation(cd).isTop()) {
648 // here, check if ordering relations among caller's args respect
649 // ordering relations in-between callee's args
650 for (int currentIdx = 0; currentIdx < min.numArgs(); currentIdx++) {
651 if (currentIdx != i) { // skip itself
652 ExpressionNode argExp = min.getArg(currentIdx);
653 CompositeLocation callerArg2 =
654 checkLocationFromExpressionNode(md, nametable, argExp, new CompositeLocation(cd));
656 VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
657 Location calleeLoc2 = td2loc.get(calleevd2);
658 boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2, cd);
659 boolean calleeResult =
660 CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2, calleecd);
662 if (calleeResult && !callerResult) {
663 // in callee, calleeLoc1 is higher than calleeLoc2
664 // then, caller should have same ordering relation in-bet
665 // callerLoc1 & callerLoc2
667 throw new Error("Caller doesn't respect ordering relations among method arguments:"
668 + cd.getSourceFileName() + ":" + min.getNumLine());
679 // all arguments should be higher than the location of return value
681 if (inputGLBSet.size() > 0) {
682 if (baseLoc != null) {
683 inputGLBSet.add(baseLoc);
684 return CompositeLattice.calculateGLB(cd, inputGLBSet, cd);
689 // if there are no arguments,
690 if (baseLoc != null) {
693 // method invocation from the same class
694 CompositeLocation returnLoc = new CompositeLocation(cd);
695 returnLoc.addLocation(Location.createTopLocation(cd));
701 private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
702 SymbolTable nametable, ArrayAccessNode aan) {
704 // return glb location of array itself and index
706 ClassDescriptor cd = md.getClassDesc();
708 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
710 CompositeLocation arrayLoc =
711 checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation(
713 addTypeLocation(aan.getExpression().getType(), arrayLoc);
714 glbInputSet.add(arrayLoc);
715 CompositeLocation indexLoc =
716 checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(cd));
717 glbInputSet.add(indexLoc);
718 addTypeLocation(aan.getIndex().getType(), indexLoc);
720 CompositeLocation glbLoc = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
724 private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
725 SymbolTable nametable, CreateObjectNode con) {
727 ClassDescriptor cd = md.getClassDesc();
730 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
731 for (int i = 0; i < con.numArgs(); i++) {
732 ExpressionNode en = con.getArg(i);
733 CompositeLocation argLoc =
734 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
735 glbInputSet.add(argLoc);
736 addTypeLocation(en.getType(), argLoc);
739 // check array initializers
740 // if ((con.getArrayInitializer() != null)) {
741 // checkLocationFromArrayInitializerNode(md, nametable,
742 // con.getArrayInitializer());
745 if (glbInputSet.size() > 0) {
746 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
749 CompositeLocation compLoc = new CompositeLocation(cd);
750 compLoc.addLocation(Location.createTopLocation(cd));
755 private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
758 ClassDescriptor cd = md.getClassDesc();
759 CompositeLocation leftLoc = new CompositeLocation(cd);
760 leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
761 addTypeLocation(on.getLeft().getType(), leftLoc);
763 CompositeLocation rightLoc = new CompositeLocation(cd);
764 if (on.getRight() != null) {
765 rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
766 addTypeLocation(on.getRight().getType(), rightLoc);
769 // System.out.println("checking op node=" + on.printNode(0));
770 // System.out.println("left loc=" + leftLoc + " from " +
771 // on.getLeft().getClass());
772 // System.out.println("right loc=" + rightLoc + " from " +
773 // on.getLeft().getClass());
775 Operation op = on.getOp();
777 switch (op.getOp()) {
779 case Operation.UNARYPLUS:
780 case Operation.UNARYMINUS:
781 case Operation.LOGIC_NOT:
785 case Operation.LOGIC_OR:
786 case Operation.LOGIC_AND:
788 case Operation.BIT_OR:
789 case Operation.BIT_XOR:
790 case Operation.BIT_AND:
791 case Operation.ISAVAILABLE:
792 case Operation.EQUAL:
793 case Operation.NOTEQUAL:
803 case Operation.LEFTSHIFT:
804 case Operation.RIGHTSHIFT:
805 case Operation.URIGHTSHIFT:
807 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
808 inputSet.add(leftLoc);
809 inputSet.add(rightLoc);
810 CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(cd, inputSet, cd);
814 throw new Error(op.toString());
819 private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
820 SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
822 // literal value has the top location so that value can be flowed into any
824 Location literalLoc = Location.createTopLocation(md.getClassDesc());
825 loc.addLocation(literalLoc);
830 private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
831 NameNode nn, CompositeLocation loc) {
833 NameDescriptor nd = nn.getName();
834 if (nd.getBase() != null) {
835 loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
836 addTypeLocation(nn.getExpression().getType(), loc);
839 String varname = nd.toString();
840 if (varname.equals("this")) {
841 // 'this' itself is top location in the local hierarchy
842 loc.addLocation(Location.createTopLocation(md.getClassDesc()));
845 Descriptor d = (Descriptor) nametable.get(varname);
847 Location localLoc = null;
848 if (d instanceof VarDescriptor) {
849 VarDescriptor vd = (VarDescriptor) d;
850 localLoc = td2loc.get(vd);
851 } else if (d instanceof FieldDescriptor) {
852 FieldDescriptor fd = (FieldDescriptor) d;
853 localLoc = td2loc.get(fd);
855 assert (localLoc != null);
857 if (localLoc instanceof CompositeLocation) {
858 loc = (CompositeLocation) localLoc;
860 loc.addLocation(localLoc);
867 private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
868 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
870 ExpressionNode left = fan.getExpression();
871 loc = checkLocationFromExpressionNode(md, nametable, left, loc);
872 addTypeLocation(left.getType(), loc);
874 if (!left.getType().isPrimitive()) {
875 FieldDescriptor fd = fan.getField();
876 Location fieldLoc = td2loc.get(fd);
878 // in the case of "this.field", need to get rid of 'this' location from
879 // the composite location
880 if (loc.getCd2Loc().containsKey(md.getClassDesc())) {
881 loc.removieLocation(md.getClassDesc());
883 loc.addLocation(fieldLoc);
889 private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
890 SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
891 ClassDescriptor cd = md.getClassDesc();
893 boolean postinc = true;
894 if (an.getOperation().getBaseOp() == null
895 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
896 .getBaseOp().getOp() != Operation.POSTDEC))
899 CompositeLocation destLocation =
900 checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(cd));
902 CompositeLocation srcLocation = new CompositeLocation(cd);
904 srcLocation = new CompositeLocation(cd);
905 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
906 // System.out.println("an=" + an.printNode(0) + " an.getSrc()=" +
907 // an.getSrc().getClass()
908 // + " at " + cd.getSourceFileName() + "::" + an.getNumLine());
909 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, cd)) {
910 throw new Error("The value flow from " + srcLocation + " to " + destLocation
911 + " does not respect location hierarchy on the assignment " + an.printNode(0) + "at "
912 + cd.getSourceFileName() + "::" + an.getNumLine());
916 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
918 if (!((Set<String>) state.getCd2LocationPropertyMap().get(cd)).contains(destLocation
919 .getLocation(cd).getLocIdentifier())) {
920 throw new Error("Location " + destLocation + " is not allowed to have spinning values at "
921 + cd.getSourceFileName() + ":" + an.getNumLine());
925 if (an.getSrc() != null) {
926 addTypeLocation(an.getSrc().getType(), srcLocation);
928 addTypeLocation(an.getDest().getType(), destLocation);
933 private void assignLocationOfVarDescriptor(VarDescriptor vd, MethodDescriptor md,
934 SymbolTable nametable, TreeNode n) {
936 ClassDescriptor cd = md.getClassDesc();
937 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
939 // currently enforce every variable to have corresponding location
940 if (annotationVec.size() == 0) {
941 throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
942 + md.getSymbol() + " of the class " + cd.getSymbol());
945 if (annotationVec.size() > 1) {
946 // variable can have at most one location
947 throw new Error(vd.getSymbol() + " has more than one location.");
950 AnnotationDescriptor ad = annotationVec.elementAt(0);
952 if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
954 if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
955 String locationID = ad.getValue();
956 // check if location is defined
957 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
958 if (lattice == null || (!lattice.containsKey(locationID))) {
959 throw new Error("Location " + locationID
960 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
962 Location loc = new Location(cd, locationID);
964 addTypeLocation(vd.getType(), loc);
966 } else if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
968 CompositeLocation compLoc = new CompositeLocation(cd);
970 if (ad.getValue().length() == 0) {
971 throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: "
972 + cd.getSymbol() + ".");
975 String deltaStr = ad.getValue();
976 if (deltaStr.startsWith("LOC(")) {
978 if (!deltaStr.endsWith(")")) {
979 throw new Error("The declaration of the delta location is wrong at "
980 + cd.getSourceFileName() + ":" + n.getNumLine());
982 String locationOperand = deltaStr.substring(4, deltaStr.length() - 1);
984 nametable.get(locationOperand);
985 Descriptor d = (Descriptor) nametable.get(locationOperand);
987 if (d instanceof VarDescriptor) {
988 VarDescriptor varDescriptor = (VarDescriptor) d;
989 DeltaLocation deltaLoc = new DeltaLocation(cd, varDescriptor);
990 // td2loc.put(vd.getType(), compLoc);
991 compLoc.addLocation(deltaLoc);
992 } else if (d instanceof FieldDescriptor) {
993 throw new Error("Applying delta operation to the field " + locationOperand
994 + " is not allowed at " + cd.getSourceFileName() + ":" + n.getNumLine());
997 StringTokenizer token = new StringTokenizer(deltaStr, ",");
998 DeltaLocation deltaLoc = new DeltaLocation(cd);
1000 while (token.hasMoreTokens()) {
1001 String deltaOperand = token.nextToken();
1002 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
1003 if (deltaCD == null) {
1004 // delta operand is not defined in the location hierarchy
1005 throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd
1006 + "' is not defined by location hierarchies.");
1009 Location loc = new Location(deltaCD, deltaOperand);
1010 deltaLoc.addDeltaOperand(loc);
1012 compLoc.addLocation(deltaLoc);
1016 td2loc.put(vd, compLoc);
1017 addTypeLocation(vd.getType(), compLoc);
1024 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
1025 VarDescriptor vd = dn.getVarDescriptor();
1026 assignLocationOfVarDescriptor(vd, md, nametable, dn);
1029 private void checkClass(ClassDescriptor cd) {
1030 // Check to see that methods respects ss property
1031 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
1032 MethodDescriptor md = (MethodDescriptor) method_it.next();
1033 checkMethodDeclaration(cd, md);
1037 private void checkDeclarationInClass(ClassDescriptor cd) {
1038 // Check to see that fields are okay
1039 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
1040 FieldDescriptor fd = (FieldDescriptor) field_it.next();
1041 checkFieldDeclaration(cd, fd);
1045 private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
1049 private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
1051 Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
1053 // currently enforce every field to have corresponding location
1054 if (annotationVec.size() == 0) {
1055 throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
1059 if (annotationVec.size() > 1) {
1060 // variable can have at most one location
1061 throw new Error("Field " + fd.getSymbol() + " of class " + cd
1062 + " has more than one location.");
1065 AnnotationDescriptor ad = annotationVec.elementAt(0);
1067 if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
1069 if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
1070 String locationID = ad.getValue();
1071 // check if location is defined
1072 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
1073 if (lattice == null || (!lattice.containsKey(locationID))) {
1074 throw new Error("Location " + locationID
1075 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
1077 Location loc = new Location(cd, locationID);
1078 td2loc.put(fd, loc);
1079 addTypeLocation(fd.getType(), loc);
1081 } else if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
1083 if (ad.getValue().length() == 0) {
1084 throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: "
1085 + cd.getSymbol() + ".");
1088 CompositeLocation compLoc = new CompositeLocation(cd);
1089 DeltaLocation deltaLoc = new DeltaLocation(cd);
1091 StringTokenizer token = new StringTokenizer(ad.getValue(), ",");
1092 while (token.hasMoreTokens()) {
1093 String deltaOperand = token.nextToken();
1094 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
1095 if (deltaCD == null) {
1096 // delta operand is not defined in the location hierarchy
1097 throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd
1098 + "' is not defined by location hierarchies.");
1101 Location loc = new Location(deltaCD, deltaOperand);
1102 deltaLoc.addDeltaOperand(loc);
1104 compLoc.addLocation(deltaLoc);
1105 td2loc.put(fd, compLoc);
1106 addTypeLocation(fd.getType(), compLoc);
1113 private void addTypeLocation(TypeDescriptor type, Location loc) {
1115 type.setExtension(loc);
1119 static class CompositeLattice {
1121 public static boolean isGreaterThan(Location loc1, Location loc2, ClassDescriptor priorityCD) {
1123 // System.out.println("\nisGreaterThan=" + loc1 + " ? " + loc2);
1124 CompositeLocation compLoc1;
1125 CompositeLocation compLoc2;
1127 if (loc1 instanceof CompositeLocation) {
1128 compLoc1 = (CompositeLocation) loc1;
1130 // create a bogus composite location for a single location
1131 compLoc1 = new CompositeLocation(loc1.getClassDescriptor());
1132 compLoc1.addLocation(loc1);
1135 if (loc2 instanceof CompositeLocation) {
1136 compLoc2 = (CompositeLocation) loc2;
1138 // create a bogus composite location for a single location
1139 compLoc2 = new CompositeLocation(loc2.getClassDescriptor());
1140 compLoc2.addLocation(loc2);
1143 // comparing two composite locations
1144 // System.out.println("compare base location=" + compLoc1 + " ? " +
1147 int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2, priorityCD);
1148 if (baseCompareResult == ComparisonResult.EQUAL) {
1149 if (compareDelta(compLoc1, compLoc2) == ComparisonResult.GREATER) {
1154 } else if (baseCompareResult == ComparisonResult.GREATER) {
1162 private static int compareDelta(CompositeLocation compLoc1, CompositeLocation compLoc2) {
1163 if (compLoc1.getNumofDelta() < compLoc2.getNumofDelta()) {
1164 return ComparisonResult.GREATER;
1166 return ComparisonResult.LESS;
1170 private static int compareBaseLocationSet(CompositeLocation compLoc1,
1171 CompositeLocation compLoc2, ClassDescriptor priorityCD) {
1173 // if compLoc1 is greater than compLoc2, return true
1174 // else return false;
1176 Map<ClassDescriptor, Location> cd2loc1 = compLoc1.getCd2Loc();
1177 Map<ClassDescriptor, Location> cd2loc2 = compLoc2.getCd2Loc();
1179 // compare first the priority loc elements
1180 Location priorityLoc1 = cd2loc1.get(priorityCD);
1181 Location priorityLoc2 = cd2loc2.get(priorityCD);
1183 assert (priorityLoc1.getClassDescriptor().equals(priorityLoc2.getClassDescriptor()));
1185 ClassDescriptor cd = priorityLoc1.getClassDescriptor();
1186 Lattice<String> locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd);
1188 if (priorityLoc1.getLocIdentifier().equals(priorityLoc2.getLocIdentifier())) {
1189 // have the same level of local hierarchy
1191 Set<String> spinSet = (Set<String>) state.getCd2LocationPropertyMap().get(cd);
1192 if (spinSet != null && spinSet.contains(priorityLoc1.getLocIdentifier())) {
1193 // this location can be spinning
1194 return ComparisonResult.GREATER;
1197 } else if (locationOrder.isGreaterThan(priorityLoc1.getLocIdentifier(),
1198 priorityLoc2.getLocIdentifier())) {
1199 // if priority loc of compLoc1 is higher than compLoc2
1200 // then, compLoc 1 is higher than compLoc2
1201 return ComparisonResult.GREATER;
1203 // if priority loc of compLoc1 is NOT higher than compLoc2
1204 // then, compLoc 1 is NOT higher than compLoc2
1205 return ComparisonResult.LESS;
1208 // compare base locations except priority by class descriptor
1209 Set<ClassDescriptor> keySet1 = cd2loc1.keySet();
1210 int numEqualLoc = 0;
1212 for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) {
1213 ClassDescriptor cd1 = (ClassDescriptor) iterator.next();
1215 Location loc1 = cd2loc1.get(cd1);
1216 Location loc2 = cd2loc2.get(cd1);
1218 if (priorityLoc1.equals(loc1)) {
1223 // if comploc2 doesn't have corresponding location,
1224 // then we determines that comploc1 is lower than comploc 2
1225 return ComparisonResult.LESS;
1228 System.out.println("lattice comparison:" + loc1.getLocIdentifier() + " ? "
1229 + loc2.getLocIdentifier());
1230 locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd1);
1231 if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1232 // have the same level of local hierarchy
1234 } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1235 // if one element of composite location 1 is not higher than composite
1237 // then, composite loc 1 is not higher than composite loc 2
1239 System.out.println(compLoc1 + " < " + compLoc2);
1240 return ComparisonResult.LESS;
1245 if (numEqualLoc == (compLoc1.getBaseLocationSize() - 1)) {
1246 return ComparisonResult.EQUAL;
1249 System.out.println(compLoc1 + " > " + compLoc2);
1250 return ComparisonResult.GREATER;
1253 public static CompositeLocation calculateGLB(ClassDescriptor cd,
1254 Set<CompositeLocation> inputSet, ClassDescriptor priorityCD) {
1256 CompositeLocation glbCompLoc = new CompositeLocation(cd);
1257 int maxDeltaFunction = 0;
1259 // calculate GLB of priority element first
1261 Hashtable<ClassDescriptor, Set<Location>> cd2locSet =
1262 new Hashtable<ClassDescriptor, Set<Location>>();
1264 // creating mapping from class to set of locations
1265 for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1266 CompositeLocation compLoc = (CompositeLocation) iterator.next();
1268 int numOfDelta = compLoc.getNumofDelta();
1269 if (numOfDelta > maxDeltaFunction) {
1270 maxDeltaFunction = numOfDelta;
1273 Set<Location> baseLocationSet = compLoc.getBaseLocationSet();
1274 for (Iterator iterator2 = baseLocationSet.iterator(); iterator2.hasNext();) {
1275 Location locElement = (Location) iterator2.next();
1276 ClassDescriptor locCD = locElement.getClassDescriptor();
1278 Set<Location> locSet = cd2locSet.get(locCD);
1279 if (locSet == null) {
1280 locSet = new HashSet<Location>();
1282 locSet.add(locElement);
1284 cd2locSet.put(locCD, locSet);
1289 Set<Location> locSetofClass = cd2locSet.get(priorityCD);
1290 Set<String> locIdentifierSet = new HashSet<String>();
1292 for (Iterator<Location> locIterator = locSetofClass.iterator(); locIterator.hasNext();) {
1293 Location locElement = locIterator.next();
1294 locIdentifierSet.add(locElement.getLocIdentifier());
1297 Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(priorityCD);
1298 String glbLocIdentifer = locOrder.getGLB(locIdentifierSet);
1300 Location priorityGLB = new Location(priorityCD, glbLocIdentifer);
1302 Set<CompositeLocation> sameGLBLoc = new HashSet<CompositeLocation>();
1304 for (Iterator<CompositeLocation> iterator = inputSet.iterator(); iterator.hasNext();) {
1305 CompositeLocation inputComploc = iterator.next();
1306 Location locElement = inputComploc.getLocation(priorityCD);
1308 if (locElement.equals(priorityGLB)) {
1309 sameGLBLoc.add(inputComploc);
1312 glbCompLoc.addLocation(priorityGLB);
1313 if (sameGLBLoc.size() > 0) {
1314 // if more than one location shares the same priority GLB
1315 // need to calculate the rest of GLB loc
1317 Set<Location> glbElementSet = new HashSet<Location>();
1319 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1320 ClassDescriptor localCD = iterator.next();
1321 if (!localCD.equals(priorityCD)) {
1322 Set<Location> localLocSet = cd2locSet.get(localCD);
1323 Set<String> LocalLocIdSet = new HashSet<String>();
1325 for (Iterator<Location> locIterator = localLocSet.iterator(); locIterator.hasNext();) {
1326 Location locElement = locIterator.next();
1327 LocalLocIdSet.add(locElement.getLocIdentifier());
1330 Lattice<String> localOrder = (Lattice<String>) state.getCd2LocationOrder().get(localCD);
1331 Location localGLBLoc = new Location(localCD, localOrder.getGLB(LocalLocIdSet));
1332 glbCompLoc.addLocation(localGLBLoc);
1336 // if priority glb loc is lower than all of input loc
1337 // assign top location to the rest of loc element
1339 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1340 ClassDescriptor localCD = iterator.next();
1341 if (!localCD.equals(priorityCD)) {
1342 Location localGLBLoc = Location.createTopLocation(localCD);
1343 glbCompLoc.addLocation(localGLBLoc);
1356 class ComparisonResult {
1358 public static final int GREATER = 0;
1359 public static final int EQUAL = 1;
1360 public static final int LESS = 2;