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.ContinueBreakNode;
29 import IR.Tree.CreateObjectNode;
30 import IR.Tree.DeclarationNode;
31 import IR.Tree.ExpressionNode;
32 import IR.Tree.FieldAccessNode;
33 import IR.Tree.IfStatementNode;
35 import IR.Tree.LiteralNode;
36 import IR.Tree.LoopNode;
37 import IR.Tree.MethodInvokeNode;
38 import IR.Tree.NameNode;
39 import IR.Tree.OpNode;
40 import IR.Tree.SubBlockNode;
41 import IR.Tree.TertiaryNode;
44 public class FlowDownCheck {
48 Hashtable<TypeDescriptor, Location> td2loc; // mapping from 'type descriptor'
50 Hashtable<String, ClassDescriptor> id2cd; // mapping from 'locID' to 'class
54 public FlowDownCheck(State state) {
56 this.toanalyze = new HashSet();
57 this.td2loc = new Hashtable<TypeDescriptor, Location>();
62 id2cd = new Hashtable<String, ClassDescriptor>();
63 Hashtable cd2lattice = state.getCd2LocationOrder();
65 Set cdSet = cd2lattice.keySet();
66 for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
67 ClassDescriptor cd = (ClassDescriptor) iterator.next();
68 Lattice<String> lattice = (Lattice<String>) cd2lattice.get(cd);
70 Set<String> locIdSet = lattice.getKeySet();
71 for (Iterator iterator2 = locIdSet.iterator(); iterator2.hasNext();) {
72 String locID = (String) iterator2.next();
79 public void flowDownCheck() {
80 SymbolTable classtable = state.getClassSymbolTable();
82 // phase 1 : checking declaration node and creating mapping of 'type
83 // desciptor' & 'location'
84 toanalyze.addAll(classtable.getValueSet());
85 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
86 while (!toanalyze.isEmpty()) {
87 Object obj = toanalyze.iterator().next();
88 ClassDescriptor cd = (ClassDescriptor) obj;
90 if (cd.isClassLibrary()) {
91 // doesn't care about class libraries now
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);
106 // post-processing for delta location
107 // for a nested delta location, assigning a concrete reference to delta
109 Set<TypeDescriptor> tdSet = td2loc.keySet();
110 for (Iterator iterator = tdSet.iterator(); iterator.hasNext();) {
111 TypeDescriptor td = (TypeDescriptor) iterator.next();
112 Location loc = td2loc.get(td);
114 if (loc.getType() == Location.DELTA) {
115 // if it contains delta reference pointing to another location element
116 CompositeLocation compLoc = (CompositeLocation) loc;
118 Location locElement = compLoc.getTuple().at(0);
119 assert (locElement instanceof DeltaLocation);
121 DeltaLocation delta = (DeltaLocation) locElement;
122 TypeDescriptor refType = delta.getRefLocationId();
123 if (refType != null) {
124 Location refLoc = td2loc.get(refType);
126 assert (refLoc instanceof CompositeLocation);
127 CompositeLocation refCompLoc = (CompositeLocation) refLoc;
129 assert (refCompLoc.getTuple().at(0) instanceof DeltaLocation);
130 DeltaLocation refDelta = (DeltaLocation) refCompLoc.getTuple().at(0);
132 delta.addDeltaOperand(refDelta);
133 // compLoc.addLocation(refDelta);
139 // phase2 : checking assignments
140 toanalyze.addAll(classtable.getValueSet());
141 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
142 while (!toanalyze.isEmpty()) {
143 Object obj = toanalyze.iterator().next();
144 ClassDescriptor cd = (ClassDescriptor) obj;
145 toanalyze.remove(cd);
146 if (cd.isClassLibrary()) {
147 // doesn't care about class libraries now
151 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
152 MethodDescriptor md = (MethodDescriptor) method_it.next();
154 checkMethodBody(cd, md);
156 System.out.println("Error in " + md);
164 private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
165 BlockNode bn = state.getMethodBody(md);
166 checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
169 private void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
170 bn.getVarTable().setParent(nametable);
171 for (int i = 0; i < bn.size(); i++) {
172 BlockStatementNode bsn = bn.get(i);
173 checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
177 private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
178 BlockStatementNode bsn) {
180 switch (bsn.kind()) {
181 case Kind.SubBlockNode:
182 checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
184 case Kind.DeclarationNode:
185 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
188 checkDeclarationInLoopNode(md, nametable, (LoopNode) bsn);
193 private void checkDeclarationInLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
195 if (ln.getType() == LoopNode.FORLOOP) {
196 // check for loop case
197 ClassDescriptor cd = md.getClassDesc();
198 BlockNode bn = ln.getInitializer();
199 for (int i = 0; i < bn.size(); i++) {
200 BlockStatementNode bsn = bn.get(i);
201 checkDeclarationInBlockStatementNode(md, nametable, bsn);
206 checkDeclarationInBlockNode(md, nametable, ln.getBody());
209 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
210 BlockNode bn = state.getMethodBody(md);
211 checkLocationFromBlockNode(md, md.getParameterTable(), bn);
214 private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
216 // it will return the lowest location in the block node
217 CompositeLocation lowestLoc = null;
218 for (int i = 0; i < bn.size(); i++) {
219 BlockStatementNode bsn = bn.get(i);
220 CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
222 if (lowestLoc == null) {
225 if (CompositeLattice.isGreaterThan(lowestLoc, bLoc, md.getClassDesc())) {
233 private CompositeLocation checkLocationFromBlockStatementNode(MethodDescriptor md,
234 SymbolTable nametable, BlockStatementNode bsn) {
236 switch (bsn.kind()) {
237 case Kind.BlockExpressionNode:
238 return checkLocationFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
240 case Kind.DeclarationNode:
241 return checkLocationFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
243 case Kind.IfStatementNode:
244 return checkLocationFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
247 return checkLocationFromLoopNode(md, nametable, (LoopNode) bsn);
249 case Kind.ReturnNode:
250 // checkLocationFromReturnNode(md, nametable, (ReturnNode) bsn);
253 case Kind.SubBlockNode:
254 return checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
256 // case Kind.ContinueBreakNode:
257 // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
264 private CompositeLocation checkLocationFromLoopNode(MethodDescriptor md, SymbolTable nametable,
267 ClassDescriptor cd = md.getClassDesc();
268 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
270 CompositeLocation condLoc =
271 checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation(
273 CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
275 if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc, cd)) {
276 // loop condition should be higher than loop body
278 "The location of the while-condition statement is lower than the loop body at "
279 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
285 // check for loop case
286 BlockNode bn = ln.getInitializer();
288 // calculate glb location of condition and update statements
289 CompositeLocation condLoc =
290 checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
291 new CompositeLocation(cd));
292 CompositeLocation updateLoc =
293 checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
295 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
296 glbInputSet.add(condLoc);
297 glbInputSet.add(updateLoc);
299 CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
300 CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
302 if (blockLoc == null) {
303 // when there is no statement in the loop body
304 return glbLocOfForLoopCond;
307 if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc, cd)) {
309 "The location of the for-condition statement is lower than the for-loop body at "
310 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
317 private CompositeLocation checkLocationFromSubBlockNode(MethodDescriptor md,
318 SymbolTable nametable, SubBlockNode sbn) {
319 return checkLocationFromBlockNode(md, nametable, sbn.getBlockNode());
322 private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md,
323 SymbolTable nametable, IfStatementNode isn) {
325 ClassDescriptor localCD = md.getClassDesc();
326 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
328 CompositeLocation condLoc = new CompositeLocation(localCD);
329 condLoc = checkLocationFromExpressionNode(md, nametable, isn.getCondition(), condLoc);
330 glbInputSet.add(condLoc);
332 System.out.println(isn.getCondition().printNode(0) + ":::condLoc=" + condLoc);
334 CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
335 glbInputSet.add(locTrueBlock);
336 System.out.println(isn.getTrueBlock().printNode(0) + ":::trueLoc=" + locTrueBlock);
338 // here, the location of conditional block should be higher than the
339 // location of true/false blocks
341 if (!CompositeLattice.isGreaterThan(condLoc, locTrueBlock, localCD)) {
344 "The location of the if-condition statement is lower than the conditional block at "
345 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
348 if (isn.getFalseBlock() != null) {
349 CompositeLocation locFalseBlock =
350 checkLocationFromBlockNode(md, nametable, isn.getFalseBlock());
351 glbInputSet.add(locFalseBlock);
352 System.out.println(isn.getFalseBlock().printNode(0) + ":::falseLoc=" + locFalseBlock);
354 if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock, localCD)) {
357 "The location of the if-condition statement is lower than the conditional block at "
358 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
363 // return GLB location of condition, true, and false block
364 CompositeLocation glbLoc = CompositeLattice.calculateGLB(localCD, glbInputSet, localCD);
369 private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
370 SymbolTable nametable, DeclarationNode dn) {
371 VarDescriptor vd = dn.getVarDescriptor();
373 Location destLoc = td2loc.get(vd.getType());
375 ClassDescriptor localCD = md.getClassDesc();
376 if (dn.getExpression() != null) {
377 CompositeLocation expressionLoc = new CompositeLocation(localCD);
379 checkLocationFromExpressionNode(md, nametable, dn.getExpression(), expressionLoc);
381 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 // all arguments should be higher than the location of return value
499 ClassDescriptor cd = md.getClassDesc();
501 // first, calculate glb of arguments
502 Set<CompositeLocation> argLocSet = new HashSet<CompositeLocation>();
503 for (int i = 0; i < min.numArgs(); i++) {
504 ExpressionNode en = min.getArg(i);
505 CompositeLocation argLoc =
506 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
507 argLocSet.add(argLoc);
510 if (argLocSet.size() > 0) {
511 CompositeLocation argGLBLoc = CompositeLattice.calculateGLB(cd, argLocSet, cd);
514 // if there are no arguments,
515 CompositeLocation returnLoc = new CompositeLocation(cd);
516 returnLoc.addLocation(Location.createTopLocation(cd));
521 private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
522 SymbolTable nametable, ArrayAccessNode aan) {
524 // return glb location of array itself and index
526 ClassDescriptor cd = md.getClassDesc();
528 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
530 CompositeLocation arrayLoc =
531 checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation(
533 glbInputSet.add(arrayLoc);
535 CompositeLocation indexLoc =
536 checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(cd));
537 glbInputSet.add(indexLoc);
539 CompositeLocation glbLoc = CompositeLattice.calculateGLB(cd, glbInputSet, cd);
543 private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
544 SymbolTable nametable, CreateObjectNode con) {
546 ClassDescriptor cd = md.getClassDesc();
549 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
550 for (int i = 0; i < con.numArgs(); i++) {
551 ExpressionNode en = con.getArg(i);
552 CompositeLocation argLoc =
553 checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation(cd));
554 glbInputSet.add(argLoc);
557 // check array initializers
558 // if ((con.getArrayInitializer() != null)) {
559 // checkLocationFromArrayInitializerNode(md, nametable,
560 // con.getArrayInitializer());
563 if (glbInputSet.size() > 0) {
564 return CompositeLattice.calculateGLB(cd, glbInputSet, cd);
567 CompositeLocation compLoc = new CompositeLocation(cd);
568 compLoc.addLocation(Location.createTopLocation(cd));
573 private CompositeLocation checkLocationFromArrayInitializerNode(MethodDescriptor md,
574 SymbolTable nametable, ArrayInitializerNode ain) {
576 ClassDescriptor cd = md.getClassDesc();
577 Vector<TypeDescriptor> vec_type = new Vector<TypeDescriptor>();
578 for (int i = 0; i < ain.numVarInitializers(); ++i) {
579 checkLocationFromExpressionNode(md, nametable, ain.getVarInitializer(i),
580 new CompositeLocation(cd));
581 vec_type.add(ain.getVarInitializer(i).getType());
587 private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
590 ClassDescriptor cd = md.getClassDesc();
591 CompositeLocation leftLoc = new CompositeLocation(cd);
592 leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
594 CompositeLocation rightLoc = new CompositeLocation(cd);
595 if (on.getRight() != null) {
596 rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
599 System.out.println("checking op node=" + on.printNode(0));
600 System.out.println("left loc=" + leftLoc + " from " + on.getLeft().getClass());
601 System.out.println("right loc=" + rightLoc);
603 Operation op = on.getOp();
605 switch (op.getOp()) {
607 case Operation.UNARYPLUS:
608 case Operation.UNARYMINUS:
609 case Operation.LOGIC_NOT:
611 on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN));
614 case Operation.LOGIC_OR:
615 case Operation.LOGIC_AND:
617 case Operation.BIT_OR:
618 case Operation.BIT_XOR:
619 case Operation.BIT_AND:
620 case Operation.ISAVAILABLE:
621 case Operation.EQUAL:
622 case Operation.NOTEQUAL:
632 case Operation.LEFTSHIFT:
633 case Operation.RIGHTSHIFT:
634 case Operation.URIGHTSHIFT:
636 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
637 inputSet.add(leftLoc);
638 inputSet.add(rightLoc);
639 CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(cd, inputSet, cd);
643 throw new Error(op.toString());
650 private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
651 SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
653 // literal value has the top location so that value can be flowed into any
655 Location literalLoc = Location.createTopLocation(md.getClassDesc());
656 loc.addLocation(literalLoc);
661 private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
662 NameNode nn, CompositeLocation loc) {
664 NameDescriptor nd = nn.getName();
665 if (nd.getBase() != null) {
666 loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
669 String varname = nd.toString();
670 Descriptor d = (Descriptor) nametable.get(varname);
672 Location localLoc = null;
673 if (d instanceof VarDescriptor) {
674 VarDescriptor vd = (VarDescriptor) d;
675 localLoc = td2loc.get(vd.getType());
676 } else if (d instanceof FieldDescriptor) {
677 FieldDescriptor fd = (FieldDescriptor) d;
678 localLoc = td2loc.get(fd.getType());
680 assert (localLoc != null);
682 if (localLoc instanceof CompositeLocation) {
683 loc = (CompositeLocation) localLoc;
685 loc.addLocation(localLoc);
692 private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
693 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
694 FieldDescriptor fd = fan.getField();
695 Location fieldLoc = td2loc.get(fd.getType());
696 loc.addLocation(fieldLoc);
698 ExpressionNode left = fan.getExpression();
699 return checkLocationFromExpressionNode(md, nametable, left, loc);
702 private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
703 SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
705 ClassDescriptor localCD = md.getClassDesc();
707 boolean postinc = true;
708 if (an.getOperation().getBaseOp() == null
709 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
710 .getBaseOp().getOp() != Operation.POSTDEC))
713 CompositeLocation destLocation =
714 checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(localCD));
716 CompositeLocation srcLocation = new CompositeLocation(localCD);
718 srcLocation = new CompositeLocation(localCD);
719 srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
720 if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, localCD)) {
721 throw new Error("The value flow from " + srcLocation + " to " + destLocation
722 + " does not respect location hierarchy on the assignment " + an.printNode(0));
729 private Location createCompositeLocation(FieldAccessNode fan, Location loc) {
731 FieldDescriptor field = fan.getField();
732 ClassDescriptor fieldCD = field.getClassDescriptor();
734 assert (field.getType().getAnnotationMarkers().size() == 1);
736 AnnotationDescriptor locAnnotation = field.getType().getAnnotationMarkers().elementAt(0);
737 if (locAnnotation.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
744 // Location localLoc=new Location(field.getClassDescriptor(),field.get)
746 // System.out.println("creatingComposite's field="+field+" localLoc="+localLoc);
747 ExpressionNode leftNode = fan.getExpression();
748 System.out.println("creatingComposite's leftnode=" + leftNode.printNode(0));
753 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
755 ClassDescriptor cd = md.getClassDesc();
756 VarDescriptor vd = dn.getVarDescriptor();
757 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
759 // currently enforce every variable to have corresponding location
760 if (annotationVec.size() == 0) {
761 throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
762 + md.getSymbol() + " of the class " + cd.getSymbol());
765 if (annotationVec.size() > 1) {
766 // variable can have at most one location
767 throw new Error(vd.getSymbol() + " has more than one location.");
770 AnnotationDescriptor ad = annotationVec.elementAt(0);
772 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
774 // check if location is defined
775 String locationID = ad.getMarker();
776 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
778 if (lattice == null || (!lattice.containsKey(locationID))) {
779 throw new Error("Location " + locationID
780 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
783 Location loc = new Location(cd, locationID);
784 td2loc.put(vd.getType(), loc);
786 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
787 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
789 CompositeLocation compLoc = new CompositeLocation(cd);
791 if (ad.getData().length() == 0) {
792 throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: "
793 + cd.getSymbol() + ".");
796 String deltaStr = ad.getData();
797 if (deltaStr.startsWith("LOC(")) {
799 if (!deltaStr.endsWith(")")) {
800 throw new Error("The declaration of the delta location is wrong at "
801 + cd.getSourceFileName() + ":" + dn.getNumLine());
803 String locationOperand = deltaStr.substring(4, deltaStr.length() - 1);
805 nametable.get(locationOperand);
806 Descriptor d = (Descriptor) nametable.get(locationOperand);
808 if (d instanceof VarDescriptor) {
809 VarDescriptor varDescriptor = (VarDescriptor) d;
810 DeltaLocation deltaLoc = new DeltaLocation(cd, varDescriptor.getType());
811 // td2loc.put(vd.getType(), compLoc);
812 compLoc.addLocation(deltaLoc);
813 } else if (d instanceof FieldDescriptor) {
814 throw new Error("Applying delta operation to the field " + locationOperand
815 + " is not allowed at " + cd.getSourceFileName() + ":" + dn.getNumLine());
818 StringTokenizer token = new StringTokenizer(deltaStr, ",");
819 DeltaLocation deltaLoc = new DeltaLocation(cd);
821 while (token.hasMoreTokens()) {
822 String deltaOperand = token.nextToken();
823 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
824 if (deltaCD == null) {
825 // delta operand is not defined in the location hierarchy
826 throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd
827 + "' is not defined by location hierarchies.");
830 Location loc = new Location(deltaCD, deltaOperand);
831 deltaLoc.addDeltaOperand(loc);
833 compLoc.addLocation(deltaLoc);
837 td2loc.put(vd.getType(), compLoc);
838 System.out.println("vd=" + vd + " is assigned by " + compLoc);
845 private void checkClass(ClassDescriptor cd) {
846 // Check to see that methods respects ss property
847 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
848 MethodDescriptor md = (MethodDescriptor) method_it.next();
849 checkMethodDeclaration(cd, md);
853 private void checkDeclarationInClass(ClassDescriptor cd) {
854 // Check to see that fields are okay
855 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
856 FieldDescriptor fd = (FieldDescriptor) field_it.next();
857 checkFieldDeclaration(cd, fd);
861 private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
865 private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
867 Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
869 // currently enforce every variable to have corresponding location
870 if (annotationVec.size() == 0) {
871 throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
875 if (annotationVec.size() > 1) {
876 // variable can have at most one location
877 throw new Error("Field " + fd.getSymbol() + " of class " + cd
878 + " has more than one location.");
881 // check if location is defined
882 AnnotationDescriptor ad = annotationVec.elementAt(0);
883 if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
884 String locationID = annotationVec.elementAt(0).getMarker();
885 Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
887 if (lattice == null || (!lattice.containsKey(locationID))) {
888 throw new Error("Location " + locationID
889 + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
892 Location localLoc = new Location(cd, locationID);
893 td2loc.put(fd.getType(), localLoc);
895 } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
896 if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
898 if (ad.getData().length() == 0) {
899 throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: "
900 + cd.getSymbol() + ".");
903 CompositeLocation compLoc = new CompositeLocation(cd);
904 DeltaLocation deltaLoc = new DeltaLocation(cd);
906 StringTokenizer token = new StringTokenizer(ad.getData(), ",");
907 while (token.hasMoreTokens()) {
908 String deltaOperand = token.nextToken();
909 ClassDescriptor deltaCD = id2cd.get(deltaOperand);
910 if (deltaCD == null) {
911 // delta operand is not defined in the location hierarchy
912 throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd
913 + "' is not defined by location hierarchies.");
916 Location loc = new Location(deltaCD, deltaOperand);
917 deltaLoc.addDeltaOperand(loc);
919 compLoc.addLocation(deltaLoc);
920 td2loc.put(fd.getType(), compLoc);
927 static class CompositeLattice {
929 public static boolean isGreaterThan(Location loc1, Location loc2, ClassDescriptor priorityCD) {
931 // System.out.println("isGreaterThan=" + loc1 + " ? " + loc2);
932 CompositeLocation compLoc1;
933 CompositeLocation compLoc2;
935 if (loc1 instanceof CompositeLocation) {
936 compLoc1 = (CompositeLocation) loc1;
938 // create a bogus composite location for a single location
939 compLoc1 = new CompositeLocation(loc1.getClassDescriptor());
940 compLoc1.addLocation(loc1);
943 if (loc2 instanceof CompositeLocation) {
944 compLoc2 = (CompositeLocation) loc2;
946 // create a bogus composite location for a single location
947 compLoc2 = new CompositeLocation(loc2.getClassDescriptor());
948 compLoc2.addLocation(loc2);
951 // comparing two composite locations
952 // System.out.println("compare base location=" + compLoc1 + " ? " +
955 int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2, priorityCD);
956 if (baseCompareResult == ComparisonResult.EQUAL) {
957 if (compareDelta(compLoc1, compLoc2) == ComparisonResult.GREATER) {
962 } else if (baseCompareResult == ComparisonResult.GREATER) {
970 private static int compareDelta(CompositeLocation compLoc1, CompositeLocation compLoc2) {
971 if (compLoc1.getNumofDelta() < compLoc2.getNumofDelta()) {
972 return ComparisonResult.GREATER;
974 return ComparisonResult.LESS;
978 private static int compareBaseLocationSet(CompositeLocation compLoc1,
979 CompositeLocation compLoc2, ClassDescriptor priorityCD) {
981 // if compLoc1 is greater than compLoc2, return true
982 // else return false;
984 Map<ClassDescriptor, Location> cd2loc1 = compLoc1.getCd2Loc();
985 Map<ClassDescriptor, Location> cd2loc2 = compLoc2.getCd2Loc();
987 // compare first the priority loc elements
988 Location priorityLoc1 = cd2loc1.get(priorityCD);
989 Location priorityLoc2 = cd2loc2.get(priorityCD);
991 assert (priorityLoc1.getClassDescriptor().equals(priorityLoc2.getClassDescriptor()));
993 ClassDescriptor cd = priorityLoc1.getClassDescriptor();
994 Lattice<String> locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd);
996 if (priorityLoc1.getLocIdentifier().equals(priorityLoc2.getLocIdentifier())) {
997 // have the same level of local hierarchy
998 } else if (locationOrder.isGreaterThan(priorityLoc1.getLocIdentifier(),
999 priorityLoc2.getLocIdentifier())) {
1000 // if priority loc of compLoc1 is higher than compLoc2
1001 // then, compLoc 1 is higher than compLoc2
1002 return ComparisonResult.GREATER;
1004 // if priority loc of compLoc1 is NOT higher than compLoc2
1005 // then, compLoc 1 is NOT higher than compLoc2
1006 return ComparisonResult.LESS;
1009 // compare base locations except priority by class descriptor
1010 Set<ClassDescriptor> keySet1 = cd2loc1.keySet();
1011 int numEqualLoc = 0;
1013 for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) {
1014 ClassDescriptor cd1 = (ClassDescriptor) iterator.next();
1016 Location loc1 = cd2loc1.get(cd1);
1017 Location loc2 = cd2loc2.get(cd1);
1019 if (priorityLoc1.equals(loc1)) {
1024 // if comploc2 doesn't have corresponding location,
1025 // then we determines that comploc1 is lower than comploc 2
1026 return ComparisonResult.LESS;
1029 System.out.println("lattice comparison:" + loc1.getLocIdentifier() + " ? "
1030 + loc2.getLocIdentifier());
1031 locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd1);
1032 if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1033 // have the same level of local hierarchy
1035 } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1036 // if one element of composite location 1 is not higher than composite
1038 // then, composite loc 1 is not higher than composite loc 2
1040 System.out.println(compLoc1 + " < " + compLoc2);
1041 return ComparisonResult.LESS;
1046 if (numEqualLoc == (compLoc1.getBaseLocationSize() - 1)) {
1047 return ComparisonResult.EQUAL;
1050 System.out.println(compLoc1 + " > " + compLoc2);
1051 return ComparisonResult.GREATER;
1054 public static CompositeLocation calculateGLB(ClassDescriptor cd,
1055 Set<CompositeLocation> inputSet, ClassDescriptor priorityCD) {
1057 CompositeLocation glbCompLoc = new CompositeLocation(cd);
1058 int maxDeltaFunction = 0;
1060 // calculate GLB of priority element first
1062 Hashtable<ClassDescriptor, Set<Location>> cd2locSet =
1063 new Hashtable<ClassDescriptor, Set<Location>>();
1065 // creating mapping from class to set of locations
1066 for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1067 CompositeLocation compLoc = (CompositeLocation) iterator.next();
1069 int numOfDelta = compLoc.getNumofDelta();
1070 if (numOfDelta > maxDeltaFunction) {
1071 maxDeltaFunction = numOfDelta;
1074 Set<Location> baseLocationSet = compLoc.getBaseLocationSet();
1075 for (Iterator iterator2 = baseLocationSet.iterator(); iterator2.hasNext();) {
1076 Location locElement = (Location) iterator2.next();
1077 ClassDescriptor locCD = locElement.getClassDescriptor();
1079 Set<Location> locSet = cd2locSet.get(locCD);
1080 if (locSet == null) {
1081 locSet = new HashSet<Location>();
1083 locSet.add(locElement);
1085 cd2locSet.put(locCD, locSet);
1090 Set<Location> locSetofClass = cd2locSet.get(priorityCD);
1091 Set<String> locIdentifierSet = new HashSet<String>();
1093 for (Iterator<Location> locIterator = locSetofClass.iterator(); locIterator.hasNext();) {
1094 Location locElement = locIterator.next();
1095 locIdentifierSet.add(locElement.getLocIdentifier());
1098 Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(priorityCD);
1099 String glbLocIdentifer = locOrder.getGLB(locIdentifierSet);
1101 Location priorityGLB = new Location(priorityCD, glbLocIdentifer);
1103 Set<CompositeLocation> sameGLBLoc = new HashSet<CompositeLocation>();
1105 for (Iterator<CompositeLocation> iterator = inputSet.iterator(); iterator.hasNext();) {
1106 CompositeLocation inputComploc = iterator.next();
1107 Location locElement = inputComploc.getLocation(priorityCD);
1109 if (locElement.equals(priorityGLB)) {
1110 sameGLBLoc.add(inputComploc);
1113 glbCompLoc.addLocation(priorityGLB);
1114 if (sameGLBLoc.size() > 0) {
1115 // if more than one location shares the same priority GLB
1116 // need to calculate the rest of GLB loc
1118 Set<Location> glbElementSet = new HashSet<Location>();
1120 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1121 ClassDescriptor localCD = iterator.next();
1122 if (!localCD.equals(priorityCD)) {
1123 Set<Location> localLocSet = cd2locSet.get(localCD);
1124 Set<String> LocalLocIdSet = new HashSet<String>();
1126 for (Iterator<Location> locIterator = localLocSet.iterator(); locIterator.hasNext();) {
1127 Location locElement = locIterator.next();
1128 LocalLocIdSet.add(locElement.getLocIdentifier());
1131 Lattice<String> localOrder = (Lattice<String>) state.getCd2LocationOrder().get(localCD);
1132 Location localGLBLoc = new Location(localCD, localOrder.getGLB(LocalLocIdSet));
1133 glbCompLoc.addLocation(localGLBLoc);
1137 // if priority glb loc is lower than all of input loc
1138 // assign top location to the rest of loc element
1140 for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
1141 ClassDescriptor localCD = iterator.next();
1142 if (!localCD.equals(priorityCD)) {
1143 Location localGLBLoc = Location.createTopLocation(localCD);
1144 glbCompLoc.addLocation(localGLBLoc);
1157 class ComparisonResult {
1159 public static final int GREATER = 0;
1160 public static final int EQUAL = 1;
1161 public static final int LESS = 2;