1 package Analysis.SSJava;
3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
8 import java.util.StringTokenizer;
9 import java.util.Vector;
11 import IR.AnnotationDescriptor;
12 import IR.ClassDescriptor;
14 import IR.FieldDescriptor;
15 import IR.MethodDescriptor;
16 import IR.NameDescriptor;
19 import IR.SymbolTable;
20 import IR.TypeDescriptor;
21 import IR.VarDescriptor;
22 import IR.Tree.ArrayAccessNode;
23 import IR.Tree.ArrayInitializerNode;
24 import IR.Tree.AssignmentNode;
25 import IR.Tree.BlockExpressionNode;
26 import IR.Tree.BlockNode;
27 import IR.Tree.BlockStatementNode;
28 import IR.Tree.CreateObjectNode;
29 import IR.Tree.DeclarationNode;
30 import IR.Tree.ExpressionNode;
31 import IR.Tree.FieldAccessNode;
32 import IR.Tree.IfStatementNode;
34 import IR.Tree.LiteralNode;
35 import IR.Tree.LoopNode;
36 import IR.Tree.MethodInvokeNode;
37 import IR.Tree.NameNode;
38 import IR.Tree.OpNode;
39 import IR.Tree.SubBlockNode;
40 import IR.Tree.TertiaryNode;
41 import IR.Tree.TreeNode;
44 public class FlowDownCheck {
48 Hashtable<Descriptor, Location> td2loc; // mapping from 'type descriptor'
50 Hashtable<String, ClassDescriptor> id2cd; // mapping from 'locID' to 'class
53 public FlowDownCheck(State state) {
55 this.toanalyze = new HashSet();
56 this.td2loc = new Hashtable<Descriptor, Location>();
61 id2cd = new Hashtable<String, ClassDescriptor>();
62 Hashtable cd2lattice = state.getCd2LocationOrder();
64 Set cdSet = cd2lattice.keySet();
65 for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
66 ClassDescriptor cd = (ClassDescriptor) iterator.next();
67 Lattice<String> lattice = (Lattice<String>) cd2lattice.get(cd);
69 Set<String> locIdSet = lattice.getKeySet();
70 for (Iterator iterator2 = locIdSet.iterator(); iterator2.hasNext();) {
71 String locID = (String) iterator2.next();
78 public void flowDownCheck() {
79 SymbolTable classtable = state.getClassSymbolTable();
81 // phase 1 : checking declaration node and creating mapping of 'type
82 // desciptor' & 'location'
83 toanalyze.addAll(classtable.getValueSet());
84 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
85 while (!toanalyze.isEmpty()) {
86 Object obj = toanalyze.iterator().next();
87 ClassDescriptor cd = (ClassDescriptor) obj;
89 if (cd.isClassLibrary()) {
90 // doesn't care about class libraries now
93 checkDeclarationInClass(cd);
94 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
95 MethodDescriptor md = (MethodDescriptor) method_it.next();
97 checkDeclarationInMethodBody(cd, md);
99 System.out.println("Error in " + md);
105 // post-processing for delta location
106 // for a nested delta location, assigning a concrete reference to delta
108 Set<Descriptor> tdSet = td2loc.keySet();
109 for (Iterator iterator = tdSet.iterator(); iterator.hasNext();) {
110 Descriptor td = (Descriptor) iterator.next();
111 Location loc = td2loc.get(td);
113 if (loc.getType() == Location.DELTA) {
114 // if it contains delta reference pointing to another location element
115 CompositeLocation compLoc = (CompositeLocation) loc;
117 Location locElement = compLoc.getTuple().at(0);
118 assert (locElement instanceof DeltaLocation);
120 DeltaLocation delta = (DeltaLocation) locElement;
121 Descriptor refType = delta.getRefLocationId();
122 if (refType != null) {
123 Location refLoc = td2loc.get(refType);
125 assert (refLoc instanceof CompositeLocation);
126 CompositeLocation refCompLoc = (CompositeLocation) refLoc;
128 assert (refCompLoc.getTuple().at(0) instanceof DeltaLocation);
129 DeltaLocation refDelta = (DeltaLocation) refCompLoc.getTuple().at(0);
131 delta.addDeltaOperand(refDelta);
132 // compLoc.addLocation(refDelta);
138 // phase2 : checking assignments
139 toanalyze.addAll(classtable.getValueSet());
140 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
141 while (!toanalyze.isEmpty()) {
142 Object obj = toanalyze.iterator().next();
143 ClassDescriptor cd = (ClassDescriptor) obj;
144 toanalyze.remove(cd);
145 if (cd.isClassLibrary()) {
146 // doesn't care about class libraries now
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 private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
164 BlockNode bn = state.getMethodBody(md);
165 for (int i = 0; i < md.numParameters(); i++) {
166 // process annotations on method parameters
167 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
168 assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
170 checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
173 private void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
174 bn.getVarTable().setParent(nametable);
175 for (int i = 0; i < bn.size(); i++) {
176 BlockStatementNode bsn = bn.get(i);
177 checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
181 private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
182 BlockStatementNode bsn) {
184 switch (bsn.kind()) {
185 case Kind.SubBlockNode:
186 checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
188 case Kind.DeclarationNode:
189 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
192 checkDeclarationInLoopNode(md, nametable, (LoopNode) bsn);
197 private void checkDeclarationInLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
199 if (ln.getType() == LoopNode.FORLOOP) {
200 // check for loop case
201 ClassDescriptor cd = md.getClassDesc();
202 BlockNode bn = ln.getInitializer();
203 for (int i = 0; i < bn.size(); i++) {
204 BlockStatementNode bsn = bn.get(i);
205 checkDeclarationInBlockStatementNode(md, nametable, bsn);
210 checkDeclarationInBlockNode(md, nametable, ln.getBody());
213 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
214 BlockNode bn = state.getMethodBody(md);
215 checkLocationFromBlockNode(md, md.getParameterTable(), bn);
218 private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
220 // it will return the lowest location in the block node
221 CompositeLocation lowestLoc = null;
222 for (int i = 0; i < bn.size(); i++) {
223 BlockStatementNode bsn = bn.get(i);
224 CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
226 if (lowestLoc == null) {
229 if (CompositeLattice.isGreaterThan(lowestLoc, bLoc, md.getClassDesc())) {
237 private CompositeLocation checkLocationFromBlockStatementNode(MethodDescriptor md,
238 SymbolTable nametable, BlockStatementNode bsn) {
240 switch (bsn.kind()) {
241 case Kind.BlockExpressionNode:
242 return checkLocationFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
244 case Kind.DeclarationNode:
245 return checkLocationFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
247 case Kind.IfStatementNode:
248 return checkLocationFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
251 return checkLocationFromLoopNode(md, nametable, (LoopNode) bsn);
253 case Kind.ReturnNode:
254 // checkLocationFromReturnNode(md, nametable, (ReturnNode) bsn);
257 case Kind.SubBlockNode:
258 return checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
260 // case Kind.ContinueBreakNode:
261 // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
268 private CompositeLocation checkLocationFromLoopNode(MethodDescriptor md, SymbolTable nametable,
271 ClassDescriptor cd = md.getClassDesc();
272 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
274 CompositeLocation condLoc =
275 checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation(
277 CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
279 if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc, cd)) {
280 // loop condition should be higher than loop body
282 "The location of the while-condition statement is lower than the loop body at "
283 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
289 // check for loop case
290 BlockNode bn = ln.getInitializer();
292 // calculate glb location of condition and update statements
293 CompositeLocation condLoc =
294 checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
295 new CompositeLocation(cd));
296 CompositeLocation updateLoc =
297 checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
299 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
300 glbInputSet.add(condLoc);
301 glbInputSet.add(updateLoc);
303 CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
304 CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
306 if (blockLoc == null) {
307 // when there is no statement in the loop body
308 return glbLocOfForLoopCond;
311 if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc, cd)) {
313 "The location of the for-condition statement is lower than the for-loop body at "
314 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
321 private CompositeLocation checkLocationFromSubBlockNode(MethodDescriptor md,
322 SymbolTable nametable, SubBlockNode sbn) {
323 return checkLocationFromBlockNode(md, nametable, sbn.getBlockNode());
326 private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md,
327 SymbolTable nametable, IfStatementNode isn) {
329 ClassDescriptor localCD = md.getClassDesc();
330 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
332 CompositeLocation condLoc = new CompositeLocation(localCD);
333 condLoc = checkLocationFromExpressionNode(md, nametable, isn.getCondition(), condLoc);
334 glbInputSet.add(condLoc);
336 CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
337 glbInputSet.add(locTrueBlock);
339 // here, the location of conditional block should be higher than the
340 // location of true/false blocks
342 if (!CompositeLattice.isGreaterThan(condLoc, locTrueBlock, localCD)) {
345 "The location of the if-condition statement is lower than the conditional block at "
346 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
349 if (isn.getFalseBlock() != null) {
350 CompositeLocation locFalseBlock =
351 checkLocationFromBlockNode(md, nametable, isn.getFalseBlock());
352 glbInputSet.add(locFalseBlock);
353 System.out.println(isn.getFalseBlock().printNode(0) + ":::falseLoc=" + locFalseBlock);
355 if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock, localCD)) {
358 "The location of the if-condition statement is lower than the conditional block at "
359 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
364 // return GLB location of condition, true, and false block
365 CompositeLocation glbLoc = CompositeLattice.calculateGLB(localCD, glbInputSet, localCD);
370 private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
371 SymbolTable nametable, DeclarationNode dn) {
372 VarDescriptor vd = dn.getVarDescriptor();
374 Location destLoc = td2loc.get(vd);
376 ClassDescriptor localCD = md.getClassDesc();
377 if (dn.getExpression() != null) {
378 CompositeLocation expressionLoc = new CompositeLocation(localCD);
380 checkLocationFromExpressionNode(md, nametable, dn.getExpression(), expressionLoc);
382 if (expressionLoc != null) {
383 // checking location order
384 if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc, localCD)) {
385 throw new Error("The value flow from " + expressionLoc + " to " + destLoc
386 + " does not respect location hierarchy on the assignment " + dn.printNode(0));
389 return expressionLoc;
397 private void checkDeclarationInSubBlockNode(MethodDescriptor md, SymbolTable nametable,
399 checkDeclarationInBlockNode(md, nametable, sbn.getBlockNode());
402 private CompositeLocation checkLocationFromBlockExpressionNode(MethodDescriptor md,
403 SymbolTable nametable, BlockExpressionNode ben) {
404 return checkLocationFromExpressionNode(md, nametable, ben.getExpression(), null);
407 private CompositeLocation checkLocationFromExpressionNode(MethodDescriptor md,
408 SymbolTable nametable, ExpressionNode en, CompositeLocation loc) {
412 case Kind.AssignmentNode:
413 return checkLocationFromAssignmentNode(md, nametable, (AssignmentNode) en, loc);
415 case Kind.FieldAccessNode:
416 return checkLocationFromFieldAccessNode(md, nametable, (FieldAccessNode) en, loc);
419 return checkLocationFromNameNode(md, nametable, (NameNode) en, loc);
422 return checkLocationFromOpNode(md, nametable, (OpNode) en);
424 case Kind.CreateObjectNode:
425 return checkLocationFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
427 case Kind.ArrayAccessNode:
428 return checkLocationFromArrayAccessNode(md, nametable, (ArrayAccessNode) en);
430 case Kind.LiteralNode:
431 return checkLocationFromLiteralNode(md, nametable, (LiteralNode) en, loc);
433 case Kind.MethodInvokeNode:
434 return checkLocationFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
436 case Kind.TertiaryNode:
437 return checkLocationFromTertiaryNode(md, nametable, (TertiaryNode) en);
439 // case Kind.InstanceOfNode:
440 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
443 // case Kind.ArrayInitializerNode:
444 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
448 // case Kind.ClassTypeNode:
449 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
452 // case Kind.OffsetNode:
453 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
463 private CompositeLocation checkLocationFromTertiaryNode(MethodDescriptor md,
464 SymbolTable nametable, TertiaryNode tn) {
465 ClassDescriptor cd = md.getClassDesc();
467 CompositeLocation condLoc =
468 checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation(cd));
469 CompositeLocation trueLoc =
470 checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation(cd));
471 CompositeLocation falseLoc =
472 checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation(cd));
474 // check if condLoc is higher than trueLoc & falseLoc
475 if (!CompositeLattice.isGreaterThan(condLoc, trueLoc, cd)) {
477 "The location of the condition expression is lower than the true expression at "
478 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
481 if (!CompositeLattice.isGreaterThan(condLoc, falseLoc, cd)) {
483 "The location of the condition expression is lower than the true expression at "
484 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
487 // then, return glb of trueLoc & falseLoc
488 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
489 glbInputSet.add(trueLoc);
490 glbInputSet.add(falseLoc);
492 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
495 private CompositeLocation checkLocationFromMethodInvokeNode(MethodDescriptor md,
496 SymbolTable nametable, MethodInvokeNode min) {
498 ClassDescriptor cd = md.getClassDesc();
500 if (min.numArgs() > 1) {
502 // caller needs to guarantee that it passes arguments in regarding to
503 // callee's hierarchy
505 for (int i = 0; i < min.numArgs(); i++) {
506 ExpressionNode en = min.getArg(i);
507 CompositeLocation callerArg1 =
508 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
510 ClassDescriptor calleecd = min.getMethod().getClassDesc();
511 VarDescriptor calleevd = (VarDescriptor) min.getMethod().getParameter(i);
512 Location calleeLoc1 = td2loc.get(calleevd);
514 if (!callerArg1.getLocation(cd).isTop()) {
515 // here, check if ordering relations among caller's args respect
516 // ordering relations in-between callee's args
517 for (int currentIdx = 0; currentIdx < min.numArgs(); currentIdx++) {
518 if (currentIdx != i) {// skip itself
519 ExpressionNode argExp = min.getArg(currentIdx);
520 CompositeLocation callerArg2 =
521 checkLocationFromExpressionNode(md, nametable, argExp, new CompositeLocation(cd));
523 VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
524 Location calleeLoc2 = td2loc.get(calleevd2);
525 boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2, cd);
526 boolean calleeResult =
527 CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2, calleecd);
529 if (calleeResult && !callerResult) {
530 // in callee, calleeLoc1 is higher than calleeLoc2
531 // then, caller should have same ordering relation in-bet
532 // callerLoc1 & callerLoc2
534 throw new Error("Caller doesn't respect ordering relations among method arguments:"
535 + cd.getSourceFileName() + ":" + min.getNumLine());
546 // all arguments should be higher than the location of return value
548 // first, calculate glb of arguments
549 Set<CompositeLocation> argLocSet = new HashSet<CompositeLocation>();
550 for (int i = 0; i < min.numArgs(); i++) {
551 ExpressionNode en = min.getArg(i);
552 CompositeLocation argLoc =
553 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
554 argLocSet.add(argLoc);
557 if (argLocSet.size() > 0) {
558 CompositeLocation argGLBLoc = CompositeLattice.calculateGLB(cd, argLocSet, cd);
561 // if there are no arguments,
562 CompositeLocation returnLoc = new CompositeLocation(cd);
563 returnLoc.addLocation(Location.createTopLocation(cd));
568 private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
569 SymbolTable nametable, ArrayAccessNode aan) {
571 // return glb location of array itself and index
573 ClassDescriptor cd = md.getClassDesc();
575 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
577 CompositeLocation arrayLoc =
578 checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation(
580 glbInputSet.add(arrayLoc);
582 CompositeLocation indexLoc =
583 checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(cd));
584 glbInputSet.add(indexLoc);
586 CompositeLocation glbLoc = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
590 private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
591 SymbolTable nametable, CreateObjectNode con) {
593 ClassDescriptor cd = md.getClassDesc();
596 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
597 for (int i = 0; i < con.numArgs(); i++) {
598 ExpressionNode en = con.getArg(i);
599 CompositeLocation argLoc =
600 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
601 glbInputSet.add(argLoc);
604 // check array initializers
605 // if ((con.getArrayInitializer() != null)) {
606 // checkLocationFromArrayInitializerNode(md, nametable,
607 // con.getArrayInitializer());
610 if (glbInputSet.size() > 0) {
611 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
614 CompositeLocation compLoc = new CompositeLocation(cd);
615 compLoc.addLocation(Location.createTopLocation(cd));
620 private CompositeLocation checkLocationFromArrayInitializerNode(MethodDescriptor md,
621 SymbolTable nametable, ArrayInitializerNode ain) {
623 ClassDescriptor cd = md.getClassDesc();
624 Vector<TypeDescriptor> vec_type = new Vector<TypeDescriptor>();
625 for (int i = 0; i < ain.numVarInitializers(); ++i) {
626 checkLocationFromExpressionNode(md, nametable, ain.getVarInitializer(i),
627 new CompositeLocation(cd));
628 vec_type.add(ain.getVarInitializer(i).getType());
634 private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
637 ClassDescriptor cd = md.getClassDesc();
638 CompositeLocation leftLoc = new CompositeLocation(cd);
639 leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
641 CompositeLocation rightLoc = new CompositeLocation(cd);
642 if (on.getRight() != null) {
643 rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
646 System.out.println("checking op node=" + on.printNode(0));
647 System.out.println("left loc=" + leftLoc + " from " + on.getLeft().getClass());
648 System.out.println("right loc=" + rightLoc);
650 Operation op = on.getOp();
652 switch (op.getOp()) {
654 case Operation.UNARYPLUS:
655 case Operation.UNARYMINUS:
656 case Operation.LOGIC_NOT:
658 on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN));
661 case Operation.LOGIC_OR:
662 case Operation.LOGIC_AND:
664 case Operation.BIT_OR:
665 case Operation.BIT_XOR:
666 case Operation.BIT_AND:
667 case Operation.ISAVAILABLE:
668 case Operation.EQUAL:
669 case Operation.NOTEQUAL:
679 case Operation.LEFTSHIFT:
680 case Operation.RIGHTSHIFT:
681 case Operation.URIGHTSHIFT:
683 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
684 inputSet.add(leftLoc);
685 inputSet.add(rightLoc);
686 CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(cd, inputSet, cd);
690 throw new Error(op.toString());
697 private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
698 SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
700 // literal value has the top location so that value can be flowed into any
702 Location literalLoc = Location.createTopLocation(md.getClassDesc());
703 loc.addLocation(literalLoc);
708 private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
709 NameNode nn, CompositeLocation loc) {
711 NameDescriptor nd = nn.getName();
712 if (nd.getBase() != null) {
713 loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
716 String varname = nd.toString();
717 Descriptor d = (Descriptor) nametable.get(varname);
719 Location localLoc = null;
720 if (d instanceof VarDescriptor) {
721 VarDescriptor vd = (VarDescriptor) d;
722 localLoc = td2loc.get(vd);
723 } else if (d instanceof FieldDescriptor) {
724 FieldDescriptor fd = (FieldDescriptor) d;
725 localLoc = td2loc.get(fd);
727 assert (localLoc != null);
729 if (localLoc instanceof CompositeLocation) {
730 loc = (CompositeLocation) localLoc;
732 loc.addLocation(localLoc);
739 private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
740 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
741 FieldDescriptor fd = fan.getField();
742 Location fieldLoc = td2loc.get(fd);
743 loc.addLocation(fieldLoc);
745 ExpressionNode left = fan.getExpression();
746 return checkLocationFromExpressionNode(md, nametable, left, loc);
749 private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
750 SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
752 ClassDescriptor cd = md.getClassDesc();
754 boolean postinc = true;
755 if (an.getOperation().getBaseOp() == null
756 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
757 .getBaseOp().getOp() != Operation.POSTDEC))
760 CompositeLocation destLocation =
761 checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(cd));
763 CompositeLocation srcLocation = new CompositeLocation(cd);
765 srcLocation = new CompositeLocation(cd);
766 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
768 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, cd)) {
769 throw new Error("The value flow from " + srcLocation + " to " + destLocation
770 + " does not respect location hierarchy on the assignment " + an.printNode(0));
774 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
776 if (!((Set<String>) state.getCd2LocationPropertyMap().get(cd)).contains(destLocation
777 .getLocation(cd).getLocIdentifier())) {
778 throw new Error("Location " + destLocation + " is not allowed to have spinning values at "
779 + cd.getSourceFileName() + ":" + an.getNumLine());
787 private Location createCompositeLocation(FieldAccessNode fan, Location loc) {
789 FieldDescriptor field = fan.getField();
790 ClassDescriptor fieldCD = field.getClassDescriptor();
792 assert (field.getType().getAnnotationMarkers().size() == 1);
794 AnnotationDescriptor locAnnotation = field.getType().getAnnotationMarkers().elementAt(0);
795 if (locAnnotation.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
802 // Location localLoc=new Location(field.getClassDescriptor(),field.get)
804 // System.out.println("creatingComposite's field="+field+" localLoc="+localLoc);
805 ExpressionNode leftNode = fan.getExpression();
806 System.out.println("creatingComposite's leftnode=" + leftNode.printNode(0));
811 private void assignLocationOfVarDescriptor(VarDescriptor vd, MethodDescriptor md,
812 SymbolTable nametable, TreeNode n) {
814 ClassDescriptor cd = md.getClassDesc();
815 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
817 // currently enforce every variable to have corresponding location
818 if (annotationVec.size() == 0) {
819 throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
820 + md.getSymbol() + " of the class " + cd.getSymbol());
823 if (annotationVec.size() > 1) {
824 // variable can have at most one location
825 throw new Error(vd.getSymbol() + " has more than one location.");
828 AnnotationDescriptor ad = annotationVec.elementAt(0);
830 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
832 // check if location is defined
833 String locationID = ad.getMarker();
834 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
836 if (lattice == null || (!lattice.containsKey(locationID))) {
837 throw new Error("Location " + locationID
838 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
841 Location loc = new Location(cd, locationID);
844 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
845 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
847 CompositeLocation compLoc = new CompositeLocation(cd);
849 if (ad.getData().length() == 0) {
850 throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: "
851 + cd.getSymbol() + ".");
854 String deltaStr = ad.getData();
855 if (deltaStr.startsWith("LOC(")) {
857 if (!deltaStr.endsWith(")")) {
858 throw new Error("The declaration of the delta location is wrong at "
859 + cd.getSourceFileName() + ":" + n.getNumLine());
861 String locationOperand = deltaStr.substring(4, deltaStr.length() - 1);
863 nametable.get(locationOperand);
864 Descriptor d = (Descriptor) nametable.get(locationOperand);
866 if (d instanceof VarDescriptor) {
867 VarDescriptor varDescriptor = (VarDescriptor) d;
868 DeltaLocation deltaLoc = new DeltaLocation(cd, varDescriptor);
869 // td2loc.put(vd.getType(), compLoc);
870 compLoc.addLocation(deltaLoc);
871 } else if (d instanceof FieldDescriptor) {
872 throw new Error("Applying delta operation to the field " + locationOperand
873 + " is not allowed at " + cd.getSourceFileName() + ":" + n.getNumLine());
876 StringTokenizer token = new StringTokenizer(deltaStr, ",");
877 DeltaLocation deltaLoc = new DeltaLocation(cd);
879 while (token.hasMoreTokens()) {
880 String deltaOperand = token.nextToken();
881 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
882 if (deltaCD == null) {
883 // delta operand is not defined in the location hierarchy
884 throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd
885 + "' is not defined by location hierarchies.");
888 Location loc = new Location(deltaCD, deltaOperand);
889 deltaLoc.addDeltaOperand(loc);
891 compLoc.addLocation(deltaLoc);
895 td2loc.put(vd, compLoc);
896 System.out.println("vd=" + vd + " is assigned by " + compLoc);
903 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
904 VarDescriptor vd = dn.getVarDescriptor();
905 assignLocationOfVarDescriptor(vd, md, nametable, dn);
908 private void checkClass(ClassDescriptor cd) {
909 // Check to see that methods respects ss property
910 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
911 MethodDescriptor md = (MethodDescriptor) method_it.next();
912 checkMethodDeclaration(cd, md);
916 private void checkDeclarationInClass(ClassDescriptor cd) {
917 // Check to see that fields are okay
918 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
919 FieldDescriptor fd = (FieldDescriptor) field_it.next();
920 checkFieldDeclaration(cd, fd);
924 private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
928 private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
930 Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
932 // currently enforce every variable to have corresponding location
933 if (annotationVec.size() == 0) {
934 throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
938 if (annotationVec.size() > 1) {
939 // variable can have at most one location
940 throw new Error("Field " + fd.getSymbol() + " of class " + cd
941 + " has more than one location.");
944 // check if location is defined
945 AnnotationDescriptor ad = annotationVec.elementAt(0);
946 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
947 String locationID = annotationVec.elementAt(0).getMarker();
948 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
950 if (lattice == null || (!lattice.containsKey(locationID))) {
951 throw new Error("Location " + locationID
952 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
955 Location localLoc = new Location(cd, locationID);
956 td2loc.put(fd, localLoc);
958 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
959 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
961 if (ad.getData().length() == 0) {
962 throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: "
963 + cd.getSymbol() + ".");
966 CompositeLocation compLoc = new CompositeLocation(cd);
967 DeltaLocation deltaLoc = new DeltaLocation(cd);
969 StringTokenizer token = new StringTokenizer(ad.getData(), ",");
970 while (token.hasMoreTokens()) {
971 String deltaOperand = token.nextToken();
972 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
973 if (deltaCD == null) {
974 // delta operand is not defined in the location hierarchy
975 throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd
976 + "' is not defined by location hierarchies.");
979 Location loc = new Location(deltaCD, deltaOperand);
980 deltaLoc.addDeltaOperand(loc);
982 compLoc.addLocation(deltaLoc);
983 td2loc.put(fd, compLoc);
990 static class CompositeLattice {
992 public static boolean isGreaterThan(Location loc1, Location loc2, ClassDescriptor priorityCD) {
994 // System.out.println("isGreaterThan=" + loc1 + " ? " + loc2);
995 CompositeLocation compLoc1;
996 CompositeLocation compLoc2;
998 if (loc1 instanceof CompositeLocation) {
999 compLoc1 = (CompositeLocation) loc1;
1001 // create a bogus composite location for a single location
1002 compLoc1 = new CompositeLocation(loc1.getClassDescriptor());
1003 compLoc1.addLocation(loc1);
1006 if (loc2 instanceof CompositeLocation) {
1007 compLoc2 = (CompositeLocation) loc2;
1009 // create a bogus composite location for a single location
1010 compLoc2 = new CompositeLocation(loc2.getClassDescriptor());
1011 compLoc2.addLocation(loc2);
1014 // comparing two composite locations
1015 // System.out.println("compare base location=" + compLoc1 + " ? " +
1018 int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2, priorityCD);
1019 if (baseCompareResult == ComparisonResult.EQUAL) {
1020 if (compareDelta(compLoc1, compLoc2) == ComparisonResult.GREATER) {
1025 } else if (baseCompareResult == ComparisonResult.GREATER) {
1033 private static int compareDelta(CompositeLocation compLoc1, CompositeLocation compLoc2) {
1034 if (compLoc1.getNumofDelta() < compLoc2.getNumofDelta()) {
1035 return ComparisonResult.GREATER;
1037 return ComparisonResult.LESS;
1041 private static int compareBaseLocationSet(CompositeLocation compLoc1,
1042 CompositeLocation compLoc2, ClassDescriptor priorityCD) {
1044 // if compLoc1 is greater than compLoc2, return true
1045 // else return false;
1047 Map<ClassDescriptor, Location> cd2loc1 = compLoc1.getCd2Loc();
1048 Map<ClassDescriptor, Location> cd2loc2 = compLoc2.getCd2Loc();
1050 // compare first the priority loc elements
1051 Location priorityLoc1 = cd2loc1.get(priorityCD);
1052 Location priorityLoc2 = cd2loc2.get(priorityCD);
1054 assert (priorityLoc1.getClassDescriptor().equals(priorityLoc2.getClassDescriptor()));
1056 ClassDescriptor cd = priorityLoc1.getClassDescriptor();
1057 Lattice<String> locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd);
1059 if (priorityLoc1.getLocIdentifier().equals(priorityLoc2.getLocIdentifier())) {
1060 // have the same level of local hierarchy
1062 Set<String> spinSet = (Set<String>) state.getCd2LocationPropertyMap().get(cd);
1063 if (spinSet != null && spinSet.contains(priorityLoc1.getLocIdentifier())) {
1064 // this location can be spinning
1065 return ComparisonResult.GREATER;
1068 } else if (locationOrder.isGreaterThan(priorityLoc1.getLocIdentifier(),
1069 priorityLoc2.getLocIdentifier())) {
1070 // if priority loc of compLoc1 is higher than compLoc2
1071 // then, compLoc 1 is higher than compLoc2
1072 return ComparisonResult.GREATER;
1074 // if priority loc of compLoc1 is NOT higher than compLoc2
1075 // then, compLoc 1 is NOT higher than compLoc2
1076 return ComparisonResult.LESS;
1079 // compare base locations except priority by class descriptor
1080 Set<ClassDescriptor> keySet1 = cd2loc1.keySet();
1081 int numEqualLoc = 0;
1083 for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) {
1084 ClassDescriptor cd1 = (ClassDescriptor) iterator.next();
1086 Location loc1 = cd2loc1.get(cd1);
1087 Location loc2 = cd2loc2.get(cd1);
1089 if (priorityLoc1.equals(loc1)) {
1094 // if comploc2 doesn't have corresponding location,
1095 // then we determines that comploc1 is lower than comploc 2
1096 return ComparisonResult.LESS;
1099 System.out.println("lattice comparison:" + loc1.getLocIdentifier() + " ? "
1100 + loc2.getLocIdentifier());
1101 locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd1);
1102 if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1103 // have the same level of local hierarchy
1105 } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1106 // if one element of composite location 1 is not higher than composite
1108 // then, composite loc 1 is not higher than composite loc 2
1110 System.out.println(compLoc1 + " < " + compLoc2);
1111 return ComparisonResult.LESS;
1116 if (numEqualLoc == (compLoc1.getBaseLocationSize() - 1)) {
1117 return ComparisonResult.EQUAL;
1120 System.out.println(compLoc1 + " > " + compLoc2);
1121 return ComparisonResult.GREATER;
1124 public static CompositeLocation calculateGLB(ClassDescriptor cd,
1125 Set<CompositeLocation> inputSet, ClassDescriptor priorityCD) {
1127 CompositeLocation glbCompLoc = new CompositeLocation(cd);
1128 int maxDeltaFunction = 0;
1130 // calculate GLB of priority element first
1132 Hashtable<ClassDescriptor, Set<Location>> cd2locSet =
1133 new Hashtable<ClassDescriptor, Set<Location>>();
1135 // creating mapping from class to set of locations
1136 for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1137 CompositeLocation compLoc = (CompositeLocation) iterator.next();
1139 int numOfDelta = compLoc.getNumofDelta();
1140 if (numOfDelta > maxDeltaFunction) {
1141 maxDeltaFunction = numOfDelta;
1144 Set<Location> baseLocationSet = compLoc.getBaseLocationSet();
1145 for (Iterator iterator2 = baseLocationSet.iterator(); iterator2.hasNext();) {
1146 Location locElement = (Location) iterator2.next();
1147 ClassDescriptor locCD = locElement.getClassDescriptor();
1149 Set<Location> locSet = cd2locSet.get(locCD);
1150 if (locSet == null) {
1151 locSet = new HashSet<Location>();
1153 locSet.add(locElement);
1155 cd2locSet.put(locCD, locSet);
1160 Set<Location> locSetofClass = cd2locSet.get(priorityCD);
1161 Set<String> locIdentifierSet = new HashSet<String>();
1163 for (Iterator<Location> locIterator = locSetofClass.iterator(); locIterator.hasNext();) {
1164 Location locElement = locIterator.next();
1165 locIdentifierSet.add(locElement.getLocIdentifier());
1168 Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(priorityCD);
1169 String glbLocIdentifer = locOrder.getGLB(locIdentifierSet);
1171 Location priorityGLB = new Location(priorityCD, glbLocIdentifer);
1173 Set<CompositeLocation> sameGLBLoc = new HashSet<CompositeLocation>();
1175 for (Iterator<CompositeLocation> iterator = inputSet.iterator(); iterator.hasNext();) {
1176 CompositeLocation inputComploc = iterator.next();
1177 Location locElement = inputComploc.getLocation(priorityCD);
1179 if (locElement.equals(priorityGLB)) {
1180 sameGLBLoc.add(inputComploc);
1183 glbCompLoc.addLocation(priorityGLB);
1184 if (sameGLBLoc.size() > 0) {
1185 // if more than one location shares the same priority GLB
1186 // need to calculate the rest of GLB loc
1188 Set<Location> glbElementSet = new HashSet<Location>();
1190 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1191 ClassDescriptor localCD = iterator.next();
1192 if (!localCD.equals(priorityCD)) {
1193 Set<Location> localLocSet = cd2locSet.get(localCD);
1194 Set<String> LocalLocIdSet = new HashSet<String>();
1196 for (Iterator<Location> locIterator = localLocSet.iterator(); locIterator.hasNext();) {
1197 Location locElement = locIterator.next();
1198 LocalLocIdSet.add(locElement.getLocIdentifier());
1201 Lattice<String> localOrder = (Lattice<String>) state.getCd2LocationOrder().get(localCD);
1202 Location localGLBLoc = new Location(localCD, localOrder.getGLB(LocalLocIdSet));
1203 glbCompLoc.addLocation(localGLBLoc);
1207 // if priority glb loc is lower than all of input loc
1208 // assign top location to the rest of loc element
1210 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1211 ClassDescriptor localCD = iterator.next();
1212 if (!localCD.equals(priorityCD)) {
1213 Location localGLBLoc = Location.createTopLocation(localCD);
1214 glbCompLoc.addLocation(localGLBLoc);
1227 class ComparisonResult {
1229 public static final int GREATER = 0;
1230 public static final int EQUAL = 1;
1231 public static final int LESS = 2;