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 < md.numParameters(); i++) {
506 // process annotations on method parameters
507 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
508 // assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
511 for (int i = 0; i < min.numArgs(); i++) {
512 ExpressionNode en = min.getArg(i);
513 CompositeLocation callerArg1 =
514 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
516 ClassDescriptor calleecd = min.getMethod().getClassDesc();
517 VarDescriptor calleevd = (VarDescriptor) min.getMethod().getParameter(i);
518 Location calleeLoc1 = td2loc.get(calleevd);
520 if (!callerArg1.getLocation(cd).isTop()) {
521 // here, check if ordering relations among caller's args respect
522 // ordering relations in-between callee's args
523 for (int currentIdx = 0; currentIdx < min.numArgs(); currentIdx++) {
524 if (currentIdx != i) {// skip itself
525 ExpressionNode argExp = min.getArg(currentIdx);
526 CompositeLocation callerArg2 =
527 checkLocationFromExpressionNode(md, nametable, argExp, new CompositeLocation(cd));
529 VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
530 Location calleeLoc2 = td2loc.get(calleevd2);
531 boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2, cd);
532 boolean calleeResult =
533 CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2, calleecd);
535 if (callerResult != calleeResult) {
536 throw new Error("Caller doesn't respect ordering relations among method arguments:"
537 + cd.getSourceFileName() + ":" + min.getNumLine());
547 // all arguments should be higher than the location of return value
549 // first, calculate glb of arguments
550 Set<CompositeLocation> argLocSet = new HashSet<CompositeLocation>();
551 for (int i = 0; i < min.numArgs(); i++) {
552 ExpressionNode en = min.getArg(i);
553 CompositeLocation argLoc =
554 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
555 argLocSet.add(argLoc);
558 if (argLocSet.size() > 0) {
559 CompositeLocation argGLBLoc = CompositeLattice.calculateGLB(cd, argLocSet, cd);
562 // if there are no arguments,
563 CompositeLocation returnLoc = new CompositeLocation(cd);
564 returnLoc.addLocation(Location.createTopLocation(cd));
569 private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
570 SymbolTable nametable, ArrayAccessNode aan) {
572 // return glb location of array itself and index
574 ClassDescriptor cd = md.getClassDesc();
576 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
578 CompositeLocation arrayLoc =
579 checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation(
581 glbInputSet.add(arrayLoc);
583 CompositeLocation indexLoc =
584 checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(cd));
585 glbInputSet.add(indexLoc);
587 CompositeLocation glbLoc = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
591 private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
592 SymbolTable nametable, CreateObjectNode con) {
594 ClassDescriptor cd = md.getClassDesc();
597 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
598 for (int i = 0; i < con.numArgs(); i++) {
599 ExpressionNode en = con.getArg(i);
600 CompositeLocation argLoc =
601 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
602 glbInputSet.add(argLoc);
605 // check array initializers
606 // if ((con.getArrayInitializer() != null)) {
607 // checkLocationFromArrayInitializerNode(md, nametable,
608 // con.getArrayInitializer());
611 if (glbInputSet.size() > 0) {
612 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
615 CompositeLocation compLoc = new CompositeLocation(cd);
616 compLoc.addLocation(Location.createTopLocation(cd));
621 private CompositeLocation checkLocationFromArrayInitializerNode(MethodDescriptor md,
622 SymbolTable nametable, ArrayInitializerNode ain) {
624 ClassDescriptor cd = md.getClassDesc();
625 Vector<TypeDescriptor> vec_type = new Vector<TypeDescriptor>();
626 for (int i = 0; i < ain.numVarInitializers(); ++i) {
627 checkLocationFromExpressionNode(md, nametable, ain.getVarInitializer(i),
628 new CompositeLocation(cd));
629 vec_type.add(ain.getVarInitializer(i).getType());
635 private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
638 ClassDescriptor cd = md.getClassDesc();
639 CompositeLocation leftLoc = new CompositeLocation(cd);
640 leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
642 CompositeLocation rightLoc = new CompositeLocation(cd);
643 if (on.getRight() != null) {
644 rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
647 System.out.println("checking op node=" + on.printNode(0));
648 System.out.println("left loc=" + leftLoc + " from " + on.getLeft().getClass());
649 System.out.println("right loc=" + rightLoc);
651 Operation op = on.getOp();
653 switch (op.getOp()) {
655 case Operation.UNARYPLUS:
656 case Operation.UNARYMINUS:
657 case Operation.LOGIC_NOT:
659 on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN));
662 case Operation.LOGIC_OR:
663 case Operation.LOGIC_AND:
665 case Operation.BIT_OR:
666 case Operation.BIT_XOR:
667 case Operation.BIT_AND:
668 case Operation.ISAVAILABLE:
669 case Operation.EQUAL:
670 case Operation.NOTEQUAL:
680 case Operation.LEFTSHIFT:
681 case Operation.RIGHTSHIFT:
682 case Operation.URIGHTSHIFT:
684 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
685 inputSet.add(leftLoc);
686 inputSet.add(rightLoc);
687 CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(cd, inputSet, cd);
691 throw new Error(op.toString());
698 private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
699 SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
701 // literal value has the top location so that value can be flowed into any
703 Location literalLoc = Location.createTopLocation(md.getClassDesc());
704 loc.addLocation(literalLoc);
709 private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
710 NameNode nn, CompositeLocation loc) {
712 NameDescriptor nd = nn.getName();
713 if (nd.getBase() != null) {
714 loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
717 String varname = nd.toString();
718 Descriptor d = (Descriptor) nametable.get(varname);
720 Location localLoc = null;
721 if (d instanceof VarDescriptor) {
722 VarDescriptor vd = (VarDescriptor) d;
723 localLoc = td2loc.get(vd);
724 } else if (d instanceof FieldDescriptor) {
725 FieldDescriptor fd = (FieldDescriptor) d;
726 localLoc = td2loc.get(fd);
728 assert (localLoc != null);
730 if (localLoc instanceof CompositeLocation) {
731 loc = (CompositeLocation) localLoc;
733 loc.addLocation(localLoc);
740 private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
741 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
742 FieldDescriptor fd = fan.getField();
743 Location fieldLoc = td2loc.get(fd);
744 loc.addLocation(fieldLoc);
746 ExpressionNode left = fan.getExpression();
747 return checkLocationFromExpressionNode(md, nametable, left, loc);
750 private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
751 SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
753 ClassDescriptor cd = md.getClassDesc();
755 boolean postinc = true;
756 if (an.getOperation().getBaseOp() == null
757 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
758 .getBaseOp().getOp() != Operation.POSTDEC))
761 CompositeLocation destLocation =
762 checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(cd));
764 CompositeLocation srcLocation = new CompositeLocation(cd);
766 srcLocation = new CompositeLocation(cd);
767 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
769 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, cd)) {
770 throw new Error("The value flow from " + srcLocation + " to " + destLocation
771 + " does not respect location hierarchy on the assignment " + an.printNode(0));
775 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
777 if (!((Set<String>) state.getCd2LocationPropertyMap().get(cd)).contains(destLocation
778 .getLocation(cd).getLocIdentifier())) {
779 throw new Error("Location " + destLocation + " is not allowed to have spinning values at "
780 + cd.getSourceFileName() + ":" + an.getNumLine());
788 private Location createCompositeLocation(FieldAccessNode fan, Location loc) {
790 FieldDescriptor field = fan.getField();
791 ClassDescriptor fieldCD = field.getClassDescriptor();
793 assert (field.getType().getAnnotationMarkers().size() == 1);
795 AnnotationDescriptor locAnnotation = field.getType().getAnnotationMarkers().elementAt(0);
796 if (locAnnotation.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
803 // Location localLoc=new Location(field.getClassDescriptor(),field.get)
805 // System.out.println("creatingComposite's field="+field+" localLoc="+localLoc);
806 ExpressionNode leftNode = fan.getExpression();
807 System.out.println("creatingComposite's leftnode=" + leftNode.printNode(0));
812 private void assignLocationOfVarDescriptor(VarDescriptor vd, MethodDescriptor md,
813 SymbolTable nametable, TreeNode n) {
815 ClassDescriptor cd = md.getClassDesc();
816 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
818 // currently enforce every variable to have corresponding location
819 if (annotationVec.size() == 0) {
820 throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
821 + md.getSymbol() + " of the class " + cd.getSymbol());
824 if (annotationVec.size() > 1) {
825 // variable can have at most one location
826 throw new Error(vd.getSymbol() + " has more than one location.");
829 AnnotationDescriptor ad = annotationVec.elementAt(0);
831 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
833 // check if location is defined
834 String locationID = ad.getMarker();
835 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
837 if (lattice == null || (!lattice.containsKey(locationID))) {
838 throw new Error("Location " + locationID
839 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
842 Location loc = new Location(cd, locationID);
845 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
846 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
848 CompositeLocation compLoc = new CompositeLocation(cd);
850 if (ad.getData().length() == 0) {
851 throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: "
852 + cd.getSymbol() + ".");
855 String deltaStr = ad.getData();
856 if (deltaStr.startsWith("LOC(")) {
858 if (!deltaStr.endsWith(")")) {
859 throw new Error("The declaration of the delta location is wrong at "
860 + cd.getSourceFileName() + ":" + n.getNumLine());
862 String locationOperand = deltaStr.substring(4, deltaStr.length() - 1);
864 nametable.get(locationOperand);
865 Descriptor d = (Descriptor) nametable.get(locationOperand);
867 if (d instanceof VarDescriptor) {
868 VarDescriptor varDescriptor = (VarDescriptor) d;
869 DeltaLocation deltaLoc = new DeltaLocation(cd, varDescriptor);
870 // td2loc.put(vd.getType(), compLoc);
871 compLoc.addLocation(deltaLoc);
872 } else if (d instanceof FieldDescriptor) {
873 throw new Error("Applying delta operation to the field " + locationOperand
874 + " is not allowed at " + cd.getSourceFileName() + ":" + n.getNumLine());
877 StringTokenizer token = new StringTokenizer(deltaStr, ",");
878 DeltaLocation deltaLoc = new DeltaLocation(cd);
880 while (token.hasMoreTokens()) {
881 String deltaOperand = token.nextToken();
882 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
883 if (deltaCD == null) {
884 // delta operand is not defined in the location hierarchy
885 throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd
886 + "' is not defined by location hierarchies.");
889 Location loc = new Location(deltaCD, deltaOperand);
890 deltaLoc.addDeltaOperand(loc);
892 compLoc.addLocation(deltaLoc);
896 td2loc.put(vd, compLoc);
897 System.out.println("vd=" + vd + " is assigned by " + compLoc);
904 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
906 VarDescriptor vd = dn.getVarDescriptor();
907 assignLocationOfVarDescriptor(vd, md, nametable, dn);
909 * Vector<AnnotationDescriptor> annotationVec =
910 * vd.getType().getAnnotationMarkers();
912 * // currently enforce every variable to have corresponding location if
913 * (annotationVec.size() == 0) { throw new
914 * Error("Location is not assigned to variable " + vd.getSymbol() +
915 * " in the method " + md.getSymbol() + " of the class " + cd.getSymbol());
918 * if (annotationVec.size() > 1) { // variable can have at most one location
919 * throw new Error(vd.getSymbol() + " has more than one location."); }
921 * AnnotationDescriptor ad = annotationVec.elementAt(0);
923 * if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
925 * // check if location is defined String locationID = ad.getMarker();
926 * Lattice<String> lattice = (Lattice<String>)
927 * state.getCd2LocationOrder().get(cd);
929 * if (lattice == null || (!lattice.containsKey(locationID))) { throw new
930 * Error("Location " + locationID +
931 * " is not defined in the location hierarchy of class " + cd.getSymbol() +
934 * Location loc = new Location(cd, locationID); td2loc.put(vd.getType(),
937 * } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) { if
938 * (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
940 * CompositeLocation compLoc = new CompositeLocation(cd);
942 * if (ad.getData().length() == 0) { throw new Error("Delta function of " +
943 * vd.getSymbol() + " does not have any locations: " + cd.getSymbol() +
946 * String deltaStr = ad.getData(); if (deltaStr.startsWith("LOC(")) {
948 * if (!deltaStr.endsWith(")")) { throw new
949 * Error("The declaration of the delta location is wrong at " +
950 * cd.getSourceFileName() + ":" + dn.getNumLine()); } String locationOperand
951 * = deltaStr.substring(4, deltaStr.length() - 1);
953 * nametable.get(locationOperand); Descriptor d = (Descriptor)
954 * nametable.get(locationOperand);
956 * if (d instanceof VarDescriptor) { VarDescriptor varDescriptor =
957 * (VarDescriptor) d; DeltaLocation deltaLoc = new DeltaLocation(cd,
958 * varDescriptor.getType()); // td2loc.put(vd.getType(), compLoc);
959 * compLoc.addLocation(deltaLoc); } else if (d instanceof FieldDescriptor) {
960 * throw new Error("Applying delta operation to the field " +
961 * locationOperand + " is not allowed at " + cd.getSourceFileName() + ":" +
962 * dn.getNumLine()); } } else { StringTokenizer token = new
963 * StringTokenizer(deltaStr, ","); DeltaLocation deltaLoc = new
966 * while (token.hasMoreTokens()) { String deltaOperand = token.nextToken();
967 * ClassDescriptor deltaCD = id2cd.get(deltaOperand); if (deltaCD == null) {
968 * // delta operand is not defined in the location hierarchy throw new
969 * Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd +
970 * "' is not defined by location hierarchies."); }
972 * Location loc = new Location(deltaCD, deltaOperand);
973 * deltaLoc.addDeltaOperand(loc); } compLoc.addLocation(deltaLoc);
977 * td2loc.put(vd.getType(), compLoc); System.out.println("vd=" + vd +
978 * " is assigned by " + compLoc);
985 private void checkClass(ClassDescriptor cd) {
986 // Check to see that methods respects ss property
987 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
988 MethodDescriptor md = (MethodDescriptor) method_it.next();
989 checkMethodDeclaration(cd, md);
993 private void checkDeclarationInClass(ClassDescriptor cd) {
994 // Check to see that fields are okay
995 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
996 FieldDescriptor fd = (FieldDescriptor) field_it.next();
997 checkFieldDeclaration(cd, fd);
1001 private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
1005 private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
1007 Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
1009 // currently enforce every variable to have corresponding location
1010 if (annotationVec.size() == 0) {
1011 throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
1015 if (annotationVec.size() > 1) {
1016 // variable can have at most one location
1017 throw new Error("Field " + fd.getSymbol() + " of class " + cd
1018 + " has more than one location.");
1021 // check if location is defined
1022 AnnotationDescriptor ad = annotationVec.elementAt(0);
1023 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
1024 String locationID = annotationVec.elementAt(0).getMarker();
1025 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
1027 if (lattice == null || (!lattice.containsKey(locationID))) {
1028 throw new Error("Location " + locationID
1029 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
1032 Location localLoc = new Location(cd, locationID);
1033 td2loc.put(fd, localLoc);
1035 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
1036 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
1038 if (ad.getData().length() == 0) {
1039 throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: "
1040 + cd.getSymbol() + ".");
1043 CompositeLocation compLoc = new CompositeLocation(cd);
1044 DeltaLocation deltaLoc = new DeltaLocation(cd);
1046 StringTokenizer token = new StringTokenizer(ad.getData(), ",");
1047 while (token.hasMoreTokens()) {
1048 String deltaOperand = token.nextToken();
1049 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
1050 if (deltaCD == null) {
1051 // delta operand is not defined in the location hierarchy
1052 throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd
1053 + "' is not defined by location hierarchies.");
1056 Location loc = new Location(deltaCD, deltaOperand);
1057 deltaLoc.addDeltaOperand(loc);
1059 compLoc.addLocation(deltaLoc);
1060 td2loc.put(fd, compLoc);
1067 static class CompositeLattice {
1069 public static boolean isGreaterThan(Location loc1, Location loc2, ClassDescriptor priorityCD) {
1071 // System.out.println("isGreaterThan=" + loc1 + " ? " + loc2);
1072 CompositeLocation compLoc1;
1073 CompositeLocation compLoc2;
1075 if (loc1 instanceof CompositeLocation) {
1076 compLoc1 = (CompositeLocation) loc1;
1078 // create a bogus composite location for a single location
1079 compLoc1 = new CompositeLocation(loc1.getClassDescriptor());
1080 compLoc1.addLocation(loc1);
1083 if (loc2 instanceof CompositeLocation) {
1084 compLoc2 = (CompositeLocation) loc2;
1086 // create a bogus composite location for a single location
1087 compLoc2 = new CompositeLocation(loc2.getClassDescriptor());
1088 compLoc2.addLocation(loc2);
1091 // comparing two composite locations
1092 // System.out.println("compare base location=" + compLoc1 + " ? " +
1095 int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2, priorityCD);
1096 if (baseCompareResult == ComparisonResult.EQUAL) {
1097 if (compareDelta(compLoc1, compLoc2) == ComparisonResult.GREATER) {
1102 } else if (baseCompareResult == ComparisonResult.GREATER) {
1110 private static int compareDelta(CompositeLocation compLoc1, CompositeLocation compLoc2) {
1111 if (compLoc1.getNumofDelta() < compLoc2.getNumofDelta()) {
1112 return ComparisonResult.GREATER;
1114 return ComparisonResult.LESS;
1118 private static int compareBaseLocationSet(CompositeLocation compLoc1,
1119 CompositeLocation compLoc2, ClassDescriptor priorityCD) {
1121 // if compLoc1 is greater than compLoc2, return true
1122 // else return false;
1124 Map<ClassDescriptor, Location> cd2loc1 = compLoc1.getCd2Loc();
1125 Map<ClassDescriptor, Location> cd2loc2 = compLoc2.getCd2Loc();
1127 // compare first the priority loc elements
1128 Location priorityLoc1 = cd2loc1.get(priorityCD);
1129 Location priorityLoc2 = cd2loc2.get(priorityCD);
1131 assert (priorityLoc1.getClassDescriptor().equals(priorityLoc2.getClassDescriptor()));
1133 ClassDescriptor cd = priorityLoc1.getClassDescriptor();
1134 Lattice<String> locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd);
1136 if (priorityLoc1.getLocIdentifier().equals(priorityLoc2.getLocIdentifier())) {
1137 // have the same level of local hierarchy
1139 Set<String> spinSet = (Set<String>) state.getCd2LocationPropertyMap().get(cd);
1140 if (spinSet != null && spinSet.contains(priorityLoc1.getLocIdentifier())) {
1141 // this location can be spinning
1142 return ComparisonResult.GREATER;
1145 } else if (locationOrder.isGreaterThan(priorityLoc1.getLocIdentifier(),
1146 priorityLoc2.getLocIdentifier())) {
1147 // if priority loc of compLoc1 is higher than compLoc2
1148 // then, compLoc 1 is higher than compLoc2
1149 return ComparisonResult.GREATER;
1151 // if priority loc of compLoc1 is NOT higher than compLoc2
1152 // then, compLoc 1 is NOT higher than compLoc2
1153 return ComparisonResult.LESS;
1156 // compare base locations except priority by class descriptor
1157 Set<ClassDescriptor> keySet1 = cd2loc1.keySet();
1158 int numEqualLoc = 0;
1160 for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) {
1161 ClassDescriptor cd1 = (ClassDescriptor) iterator.next();
1163 Location loc1 = cd2loc1.get(cd1);
1164 Location loc2 = cd2loc2.get(cd1);
1166 if (priorityLoc1.equals(loc1)) {
1171 // if comploc2 doesn't have corresponding location,
1172 // then we determines that comploc1 is lower than comploc 2
1173 return ComparisonResult.LESS;
1176 System.out.println("lattice comparison:" + loc1.getLocIdentifier() + " ? "
1177 + loc2.getLocIdentifier());
1178 locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd1);
1179 if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1180 // have the same level of local hierarchy
1182 } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1183 // if one element of composite location 1 is not higher than composite
1185 // then, composite loc 1 is not higher than composite loc 2
1187 System.out.println(compLoc1 + " < " + compLoc2);
1188 return ComparisonResult.LESS;
1193 if (numEqualLoc == (compLoc1.getBaseLocationSize() - 1)) {
1194 return ComparisonResult.EQUAL;
1197 System.out.println(compLoc1 + " > " + compLoc2);
1198 return ComparisonResult.GREATER;
1201 public static CompositeLocation calculateGLB(ClassDescriptor cd,
1202 Set<CompositeLocation> inputSet, ClassDescriptor priorityCD) {
1204 CompositeLocation glbCompLoc = new CompositeLocation(cd);
1205 int maxDeltaFunction = 0;
1207 // calculate GLB of priority element first
1209 Hashtable<ClassDescriptor, Set<Location>> cd2locSet =
1210 new Hashtable<ClassDescriptor, Set<Location>>();
1212 // creating mapping from class to set of locations
1213 for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1214 CompositeLocation compLoc = (CompositeLocation) iterator.next();
1216 int numOfDelta = compLoc.getNumofDelta();
1217 if (numOfDelta > maxDeltaFunction) {
1218 maxDeltaFunction = numOfDelta;
1221 Set<Location> baseLocationSet = compLoc.getBaseLocationSet();
1222 for (Iterator iterator2 = baseLocationSet.iterator(); iterator2.hasNext();) {
1223 Location locElement = (Location) iterator2.next();
1224 ClassDescriptor locCD = locElement.getClassDescriptor();
1226 Set<Location> locSet = cd2locSet.get(locCD);
1227 if (locSet == null) {
1228 locSet = new HashSet<Location>();
1230 locSet.add(locElement);
1232 cd2locSet.put(locCD, locSet);
1237 Set<Location> locSetofClass = cd2locSet.get(priorityCD);
1238 Set<String> locIdentifierSet = new HashSet<String>();
1240 for (Iterator<Location> locIterator = locSetofClass.iterator(); locIterator.hasNext();) {
1241 Location locElement = locIterator.next();
1242 locIdentifierSet.add(locElement.getLocIdentifier());
1245 Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(priorityCD);
1246 String glbLocIdentifer = locOrder.getGLB(locIdentifierSet);
1248 Location priorityGLB = new Location(priorityCD, glbLocIdentifer);
1250 Set<CompositeLocation> sameGLBLoc = new HashSet<CompositeLocation>();
1252 for (Iterator<CompositeLocation> iterator = inputSet.iterator(); iterator.hasNext();) {
1253 CompositeLocation inputComploc = iterator.next();
1254 Location locElement = inputComploc.getLocation(priorityCD);
1256 if (locElement.equals(priorityGLB)) {
1257 sameGLBLoc.add(inputComploc);
1260 glbCompLoc.addLocation(priorityGLB);
1261 if (sameGLBLoc.size() > 0) {
1262 // if more than one location shares the same priority GLB
1263 // need to calculate the rest of GLB loc
1265 Set<Location> glbElementSet = new HashSet<Location>();
1267 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1268 ClassDescriptor localCD = iterator.next();
1269 if (!localCD.equals(priorityCD)) {
1270 Set<Location> localLocSet = cd2locSet.get(localCD);
1271 Set<String> LocalLocIdSet = new HashSet<String>();
1273 for (Iterator<Location> locIterator = localLocSet.iterator(); locIterator.hasNext();) {
1274 Location locElement = locIterator.next();
1275 LocalLocIdSet.add(locElement.getLocIdentifier());
1278 Lattice<String> localOrder = (Lattice<String>) state.getCd2LocationOrder().get(localCD);
1279 Location localGLBLoc = new Location(localCD, localOrder.getGLB(LocalLocIdSet));
1280 glbCompLoc.addLocation(localGLBLoc);
1284 // if priority glb loc is lower than all of input loc
1285 // assign top location to the rest of loc element
1287 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1288 ClassDescriptor localCD = iterator.next();
1289 if (!localCD.equals(priorityCD)) {
1290 Location localGLBLoc = Location.createTopLocation(localCD);
1291 glbCompLoc.addLocation(localGLBLoc);
1304 class ComparisonResult {
1306 public static final int GREATER = 0;
1307 public static final int EQUAL = 1;
1308 public static final int LESS = 2;