1 package Analysis.SSJava;
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.Comparator;
6 import java.util.HashSet;
7 import java.util.Hashtable;
8 import java.util.Iterator;
11 import java.util.StringTokenizer;
12 import java.util.Vector;
13 import java.io.FileWriter;
14 import java.io.PrintWriter;
15 import java.io.IOException;
17 import Analysis.SSJava.FlowDownCheck.ComparisonResult;
18 import Analysis.SSJava.FlowDownCheck.CompositeLattice;
19 import IR.AnnotationDescriptor;
20 import IR.ClassDescriptor;
22 import IR.FieldDescriptor;
23 import IR.MethodDescriptor;
24 import IR.NameDescriptor;
27 import IR.SymbolTable;
28 import IR.TypeDescriptor;
29 import IR.VarDescriptor;
30 import IR.Tree.ArrayAccessNode;
31 import IR.Tree.AssignmentNode;
32 import IR.Tree.BlockExpressionNode;
33 import IR.Tree.BlockNode;
34 import IR.Tree.BlockStatementNode;
35 import IR.Tree.CastNode;
36 import IR.Tree.CreateObjectNode;
37 import IR.Tree.DeclarationNode;
38 import IR.Tree.ExpressionNode;
39 import IR.Tree.FieldAccessNode;
40 import IR.Tree.IfStatementNode;
42 import IR.Tree.LiteralNode;
43 import IR.Tree.LoopNode;
44 import IR.Tree.MethodInvokeNode;
45 import IR.Tree.NameNode;
46 import IR.Tree.OpNode;
47 import IR.Tree.ReturnNode;
48 import IR.Tree.SubBlockNode;
49 import IR.Tree.SwitchBlockNode;
50 import IR.Tree.SwitchStatementNode;
51 import IR.Tree.SynchronizedNode;
52 import IR.Tree.TertiaryNode;
53 import IR.Tree.TreeNode;
56 public class SSJavaInferenceEngine {
59 static SSJavaAnalysis ssjava;
61 Set<ClassDescriptor> toanalyze;
62 List<ClassDescriptor> toanalyzeList;
64 Set<MethodDescriptor> toanalyzeMethod;
65 List<MethodDescriptor> toanalyzeMethodList;
67 // mapping from 'descriptor' to 'composite location'
68 Hashtable<Descriptor, CompositeLocation> d2loc;
70 Hashtable<MethodDescriptor, CompositeLocation> md2ReturnLoc;
71 Hashtable<MethodDescriptor, ReturnLocGenerator> md2ReturnLocGen;
73 // mapping from 'locID' to 'class descriptor'
74 Hashtable<String, ClassDescriptor> fieldLocName2cd;
76 private Set<ImplicitTuple> implicitFlowSet; /*should maybe be hashtable<ExpressionNode,Set<VarID>>*/
77 private RelationSet rSet;
79 boolean deterministic = true;
81 public SSJavaInferenceEngine(SSJavaAnalysis ssjava, State state) {
85 this.toanalyzeList = new ArrayList<ClassDescriptor>();
87 this.toanalyze = new HashSet<ClassDescriptor>();
90 this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
92 this.toanalyzeMethod = new HashSet<MethodDescriptor>();
94 this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
95 this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
96 this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
97 this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
98 this.implicitFlowSet = new HashSet<ImplicitTuple>();
99 this.rSet = new RelationSet();
104 // construct mapping from the location name to the class descriptor
105 // assume that the location name is unique through the whole program
107 Set<ClassDescriptor> cdSet = ssjava.getCd2lattice().keySet();
108 for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
109 ClassDescriptor cd = (ClassDescriptor) iterator.next();
110 SSJavaLattice<String> lattice = ssjava.getCd2lattice().get(cd);
111 Set<String> fieldLocNameSet = lattice.getKeySet();
113 for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) {
114 String fieldLocName = (String) iterator2.next();
115 fieldLocName2cd.put(fieldLocName, cd);
122 public boolean toAnalyzeIsEmpty() {
124 return toanalyzeList.isEmpty();
126 return toanalyze.isEmpty();
130 public ClassDescriptor toAnalyzeNext() {
132 return toanalyzeList.remove(0);
134 ClassDescriptor cd = toanalyze.iterator().next();
135 toanalyze.remove(cd);
140 public void setupToAnalyze() {
141 SymbolTable classtable = state.getClassSymbolTable();
143 toanalyzeList.clear();
144 toanalyzeList.addAll(classtable.getValueSet());
145 Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
146 public int compare(ClassDescriptor o1, ClassDescriptor o2) {
147 return o1.getClassName().compareTo(o2.getClassName());
152 toanalyze.addAll(classtable.getValueSet());
156 public void setupToAnalazeMethod(ClassDescriptor cd) {
158 SymbolTable methodtable = cd.getMethodTable();
160 toanalyzeMethodList.clear();
161 toanalyzeMethodList.addAll(methodtable.getValueSet());
162 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
163 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
164 return o1.getSymbol().compareTo(o2.getSymbol());
168 toanalyzeMethod.clear();
169 toanalyzeMethod.addAll(methodtable.getValueSet());
173 public boolean toAnalyzeMethodIsEmpty() {
175 return toanalyzeMethodList.isEmpty();
177 return toanalyzeMethod.isEmpty();
181 public MethodDescriptor toAnalyzeMethodNext() {
183 return toanalyzeMethodList.remove(0);
185 MethodDescriptor md = toanalyzeMethod.iterator().next();
186 toanalyzeMethod.remove(md);
191 public void inference() {
192 FileWriter latticeFile;
193 PrintWriter latticeOut;
196 while (!toAnalyzeIsEmpty()) {
197 ClassDescriptor cd = toAnalyzeNext();
199 latticeFile = new FileWriter(cd.getClassName()+".lat");
200 } catch(IOException e){
201 System.out.println("File Fail");
204 latticeOut = new PrintWriter(latticeFile);
205 if (ssjava.needToBeAnnoated(cd)) {
206 setupToAnalazeMethod(cd);
207 while (!toAnalyzeMethodIsEmpty()) {
208 MethodDescriptor md = toAnalyzeMethodNext();
209 if (ssjava.needTobeAnnotated(md)) {
210 inferRelationsFromBlockNode(md, md.getParameterTable(), state.getMethodBody(md));
211 latticeOut.println(md.getClassMethodName() + "\n");
212 latticeOut.println(rSet.toString());
213 rSet = new RelationSet();
222 private void inferRelationsFromBlockNode(MethodDescriptor md, SymbolTable nametable,
225 bn.getVarTable().setParent(nametable);
226 for (int i = 0; i < bn.size(); i++) {
227 BlockStatementNode bsn = bn.get(i);
228 inferRelationsFromBlockStatementNode(md, bn.getVarTable(), bsn);
233 private void inferRelationsFromBlockStatementNode(MethodDescriptor md,
234 SymbolTable nametable, BlockStatementNode bsn) {
236 switch (bsn.kind()) {
237 case Kind.BlockExpressionNode:
238 inferRelationsFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
241 case Kind.DeclarationNode:
242 inferRelationsFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
245 case Kind.IfStatementNode:
246 inferRelationsFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
250 inferRelationsFromLoopNode(md, nametable, (LoopNode) bsn, constraint);
253 case Kind.ReturnNode:
254 inferRelationsFromReturnNode(md, nametable, (ReturnNode) bsn, constraint);
257 case Kind.SubBlockNode:
258 inferRelationsFromSubBlockNode(md, nametable, (SubBlockNode) bsn, constraint);
261 case Kind.ContinueBreakNode:
262 compLoc = new CompositeLocation();
265 case Kind.SwitchStatementNode:
266 inferRelationsFromSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, constraint);
271 /*private CompositeLocation inferRelationsFromSwitchStatementNode(MethodDescriptor md,
272 SymbolTable nametable, SwitchStatementNode ssn, CompositeLocation constraint) {
274 ClassDescriptor cd = md.getClassDesc();
275 CompositeLocation condLoc =
276 inferRelationsFromExpressionNode(md, nametable, ssn.getCondition(), new CompositeLocation(),
278 BlockNode sbn = ssn.getSwitchBody();
280 constraint = generateNewConstraint(constraint, condLoc);
282 for (int i = 0; i < sbn.size(); i++) {
283 inferRelationsFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), constraint);
285 return new CompositeLocation();
288 private CompositeLocation inferRelationsFromSwitchBlockNode(MethodDescriptor md,
289 SymbolTable nametable, SwitchBlockNode sbn, CompositeLocation constraint) {
291 CompositeLocation blockLoc =
292 inferRelationsFromBlockNode(md, nametable, sbn.getSwitchBlockStatement(), constraint);
298 private CompositeLocation inferRelationsFromReturnNode(MethodDescriptor md, SymbolTable nametable,
299 ReturnNode rn, CompositeLocation constraint) {
301 ExpressionNode returnExp = rn.getReturnExpression();
303 CompositeLocation returnValueLoc;
304 if (returnExp != null) {
306 inferRelationsFromExpressionNode(md, nametable, returnExp, new CompositeLocation(),
309 // if this return statement is inside branch, return value has an implicit
310 // flow from conditional location
311 if (constraint != null) {
312 Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
313 inputGLB.add(returnValueLoc);
314 inputGLB.add(constraint);
316 CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(md.getClassDesc(), rn));
319 // check if return value is equal or higher than RETRUNLOC of method
320 // declaration annotation
321 CompositeLocation declaredReturnLoc = md2ReturnLoc.get(md);
324 CompositeLattice.compare(returnValueLoc, declaredReturnLoc, false,
325 generateErrorMessage(md.getClassDesc(), rn));
327 if (compareResult == ComparisonResult.LESS || compareResult == ComparisonResult.INCOMPARABLE) {
329 "Return value location is not equal or higher than the declaraed return location at "
330 + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
334 return new CompositeLocation();
337 private boolean hasOnlyLiteralValue(ExpressionNode en) {
338 if (en.kind() == Kind.LiteralNode) {
345 private CompositeLocation inferRelationsFromLoopNode(MethodDescriptor md, SymbolTable nametable,
346 LoopNode ln, CompositeLocation constraint) {
348 ClassDescriptor cd = md.getClassDesc();
349 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
351 CompositeLocation condLoc =
352 inferRelationsFromExpressionNode(md, nametable, ln.getCondition(),
353 new CompositeLocation(), constraint, false);
354 // addLocationType(ln.getCondition().getType(), (condLoc));
356 constraint = generateNewConstraint(constraint, condLoc);
357 inferRelationsFromBlockNode(md, nametable, ln.getBody(), constraint);
359 return new CompositeLocation();
362 // check 'for loop' case
363 BlockNode bn = ln.getInitializer();
364 bn.getVarTable().setParent(nametable);
366 // calculate glb location of condition and update statements
367 CompositeLocation condLoc =
368 inferRelationsFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
369 new CompositeLocation(), constraint, false);
370 // addLocationType(ln.getCondition().getType(), condLoc);
372 constraint = generateNewConstraint(constraint, condLoc);
374 inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getUpdate(), constraint);
375 inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getBody(), constraint);
377 return new CompositeLocation();
383 private CompositeLocation inferRelationsFromSubBlockNode(MethodDescriptor md,
384 SymbolTable nametable, SubBlockNode sbn, CompositeLocation constraint) {
385 CompositeLocation compLoc =
386 inferRelationsFromBlockNode(md, nametable, sbn.getBlockNode(), constraint);
390 private CompositeLocation generateNewConstraint(CompositeLocation currentCon,
391 CompositeLocation newCon) {
393 if (currentCon == null) {
396 // compute GLB of current constraint and new constraint
397 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
398 inputSet.add(currentCon);
399 inputSet.add(newCon);
400 return CompositeLattice.calculateGLB(inputSet, "");
405 private void inferRelationsFromIfStatementNode(MethodDescriptor md,
406 SymbolTable nametable, IfStatementNode isn) {
408 inferRelationsFromExpressionNode(md, nametable, isn.getCondition(), null, false);
410 constraint = generateNewConstraint(constraint, condLoc);
411 inferRelationFromBlockNode(md, nametable, isn.getTrueBlock(), constraint);
413 if (isn.getFalseBlock() != null) {
414 inferRelationsFromBlockNode(md, nametable, isn.getFalseBlock(), constraint);
418 private void inferRelationsFromDeclarationNode(MethodDescriptor md,
419 SymbolTable nametable, DeclarationNode dn) {
422 /*private void inferRelationsFromSubBlockNode(MethodDescriptor md, SymbolTable nametable,
424 inferRelationsFromBlockNode(md, nametable.getParent(), sbn.getBlockNode());
427 private void inferRelationsFromBlockExpressionNode(MethodDescriptor md,
428 SymbolTable nametable, BlockExpressionNode ben) {
429 inferRelationsFromExpressionNode(md, nametable, ben.getExpression(), null, false);
430 // addTypeLocation(ben.getExpression().getType(), compLoc);
433 private VarID inferRelationsFromExpressionNode(MethodDescriptor md,
434 SymbolTable nametable, ExpressionNode en, VarID flowTo, boolean isLHS) {
439 case Kind.AssignmentNode:
441 inferRelationsFromAssignmentNode(md, nametable, (AssignmentNode) en, flowTo);
444 // case Kind.FieldAccessNode:
446 // inferRelationsFromFieldAccessNode(md, nametable, (FieldAccessNode) en, flowTo);
450 var = inferRelationsFromNameNode(md, nametable, (NameNode) en, flowTo);
454 var = inferRelationsFromOpNode(md, nametable, (OpNode) en, flowTo);
457 case Kind.CreateObjectNode:
458 var = inferRelationsFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
461 case Kind.ArrayAccessNode:
463 inferRelationsFromArrayAccessNode(md, nametable, (ArrayAccessNode) en, flowTo, isLHS);
466 case Kind.LiteralNode:
467 var = inferRelationsFromLiteralNode(md, nametable, (LiteralNode) en);
470 case Kind.MethodInvokeNode:
472 inferRelationsFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en, flowTo);
475 case Kind.TertiaryNode:
476 var = inferRelationsFromTertiaryNode(md, nametable, (TertiaryNode) en);
480 var = inferRelationsFromCastNode(md, nametable, (CastNode) en);
483 // case Kind.InstanceOfNode:
484 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
487 // case Kind.ArrayInitializerNode:
488 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
492 // case Kind.ClassTypeNode:
493 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
496 // case Kind.OffsetNode:
497 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
504 // addTypeLocation(en.getType(), compLoc);
509 private CompositeLocation inferRelationsFromCastNode(MethodDescriptor md, SymbolTable nametable,
510 CastNode cn, CompositeLocation constraint) {
512 ExpressionNode en = cn.getExpression();
513 return inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
518 private CompositeLocation inferRelationsFromTertiaryNode(MethodDescriptor md,
519 SymbolTable nametable, TertiaryNode tn, CompositeLocation constraint) {
520 ClassDescriptor cd = md.getClassDesc();
522 CompositeLocation condLoc =
523 inferRelationsFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation(),
525 // addLocationType(tn.getCond().getType(), condLoc);
526 CompositeLocation trueLoc =
527 inferRelationsFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation(),
529 // addLocationType(tn.getTrueExpr().getType(), trueLoc);
530 CompositeLocation falseLoc =
531 inferRelationsFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation(),
533 // addLocationType(tn.getFalseExpr().getType(), falseLoc);
535 // locations from true/false branches can be TOP when there are only literal
537 // in this case, we don't need to check flow down rule!
539 // check if condLoc is higher than trueLoc & falseLoc
540 if (!trueLoc.get(0).isTop()
541 && !CompositeLattice.isGreaterThan(condLoc, trueLoc, generateErrorMessage(cd, tn))) {
543 "The location of the condition expression is lower than the true expression at "
544 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
547 if (!falseLoc.get(0).isTop()
548 && !CompositeLattice.isGreaterThan(condLoc, falseLoc,
549 generateErrorMessage(cd, tn.getCond()))) {
551 "The location of the condition expression is lower than the true expression at "
552 + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
555 // then, return glb of trueLoc & falseLoc
556 Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
557 glbInputSet.add(trueLoc);
558 glbInputSet.add(falseLoc);
560 return CompositeLattice.calculateGLB(glbInputSet, generateErrorMessage(cd, tn));
563 private CompositeLocation inferRelationsFromMethodInvokeNode(MethodDescriptor md,
564 SymbolTable nametable, MethodInvokeNode min, CompositeLocation loc,
565 CompositeLocation constraint) {
567 CompositeLocation baseLocation = null;
568 if (min.getExpression() != null) {
570 inferRelationsFromExpressionNode(md, nametable, min.getExpression(),
571 new CompositeLocation(), constraint, false);
574 if (min.getMethod().isStatic()) {
575 String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
576 if (globalLocId == null) {
577 throw new Error("Method lattice does not define global variable location at "
578 + generateErrorMessage(md.getClassDesc(), min));
580 baseLocation = new CompositeLocation(new Location(md, globalLocId));
582 String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
583 baseLocation = new CompositeLocation(new Location(md, thisLocId));
587 checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
589 checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation, constraint);
591 if (!min.getMethod().getReturnType().isVoid()) {
592 // If method has a return value, compute the highest possible return
593 // location in the caller's perspective
594 CompositeLocation ceilingLoc =
595 computeCeilingLocationForCaller(md, nametable, min, baseLocation, constraint);
599 return new CompositeLocation();
603 private void checkCallerArgumentLocationConstraints(MethodDescriptor md, SymbolTable nametable,
604 MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
605 // if parameter location consists of THIS and FIELD location,
606 // caller should pass an argument that is comparable to the declared
607 // parameter location
608 // and is not lower than the declared parameter location in the field
611 MethodDescriptor calleemd = min.getMethod();
613 List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
614 List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
616 MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
617 Location calleeThisLoc = new Location(calleemd, calleeLattice.getThisLoc());
619 for (int i = 0; i < min.numArgs(); i++) {
620 ExpressionNode en = min.getArg(i);
621 CompositeLocation callerArgLoc =
622 inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
624 callerArgList.add(callerArgLoc);
627 // setup callee params set
628 for (int i = 0; i < calleemd.numParameters(); i++) {
629 VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
630 CompositeLocation calleeLoc = d2loc.get(calleevd);
631 calleeParamList.add(calleeLoc);
634 String errorMsg = generateErrorMessage(md.getClassDesc(), min);
636 System.out.println("checkCallerArgumentLocationConstraints=" + min.printNode(0));
637 System.out.println("base location=" + callerBaseLoc);
639 for (int i = 0; i < calleeParamList.size(); i++) {
640 CompositeLocation calleeParamLoc = calleeParamList.get(i);
641 if (calleeParamLoc.get(0).equals(calleeThisLoc) && calleeParamLoc.getSize() > 1) {
643 // callee parameter location has field information
644 CompositeLocation callerArgLoc = callerArgList.get(i);
646 CompositeLocation paramLocation =
647 translateCalleeParamLocToCaller(md, calleeParamLoc, callerBaseLoc, errorMsg);
649 Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
650 if (constraint != null) {
651 inputGLBSet.add(callerArgLoc);
652 inputGLBSet.add(constraint);
654 CompositeLattice.calculateGLB(inputGLBSet,
655 generateErrorMessage(md.getClassDesc(), min));
658 if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) {
659 throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : " + callerArgLoc
660 + "' should be higher than corresponding callee's parameter : " + paramLocation
661 + " at " + errorMsg);
669 private CompositeLocation translateCalleeParamLocToCaller(MethodDescriptor md,
670 CompositeLocation calleeParamLoc, CompositeLocation callerBaseLocation, String errorMsg) {
672 CompositeLocation translate = new CompositeLocation();
674 for (int i = 0; i < callerBaseLocation.getSize(); i++) {
675 translate.addLocation(callerBaseLocation.get(i));
678 for (int i = 1; i < calleeParamLoc.getSize(); i++) {
679 translate.addLocation(calleeParamLoc.get(i));
682 System.out.println("TRANSLATED=" + translate + " from calleeParamLoc=" + calleeParamLoc);
687 private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
688 SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation,
689 CompositeLocation constraint) {
690 List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
692 // by default, method has a THIS parameter
693 argList.add(baseLocation);
695 for (int i = 0; i < min.numArgs(); i++) {
696 ExpressionNode en = min.getArg(i);
697 CompositeLocation callerArg =
698 inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
700 argList.add(callerArg);
703 System.out.println("\n## computeReturnLocation=" + min.getMethod() + " argList=" + argList);
704 CompositeLocation compLoc = md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
705 DeltaLocation delta = new DeltaLocation(compLoc, 1);
706 System.out.println("##computeReturnLocation=" + delta);
712 private void checkCalleeConstraints(MethodDescriptor md, SymbolTable nametable,
713 MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
715 System.out.println("checkCalleeConstraints="+min.printNode(0));
717 MethodDescriptor calleemd = min.getMethod();
719 MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
720 CompositeLocation calleeThisLoc =
721 new CompositeLocation(new Location(calleemd, calleeLattice.getThisLoc()));
723 List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
724 List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
726 if (min.numArgs() > 0) {
727 // caller needs to guarantee that it passes arguments in regarding to
728 // callee's hierarchy
730 // setup caller args set
731 // first, add caller's base(this) location
732 callerArgList.add(callerBaseLoc);
733 // second, add caller's arguments
734 for (int i = 0; i < min.numArgs(); i++) {
735 ExpressionNode en = min.getArg(i);
736 CompositeLocation callerArgLoc =
737 inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
739 callerArgList.add(callerArgLoc);
742 // setup callee params set
743 // first, add callee's this location
744 calleeParamList.add(calleeThisLoc);
745 // second, add callee's parameters
746 for (int i = 0; i < calleemd.numParameters(); i++) {
747 VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
748 CompositeLocation calleeLoc = d2loc.get(calleevd);
749 System.out.println("calleevd="+calleevd+" loc="+calleeLoc);
750 calleeParamList.add(calleeLoc);
753 // here, check if ordering relations among caller's args respect
754 // ordering relations in-between callee's args
755 CHECK: for (int i = 0; i < calleeParamList.size(); i++) {
756 CompositeLocation calleeLoc1 = calleeParamList.get(i);
757 CompositeLocation callerLoc1 = callerArgList.get(i);
759 for (int j = 0; j < calleeParamList.size(); j++) {
761 CompositeLocation calleeLoc2 = calleeParamList.get(j);
762 CompositeLocation callerLoc2 = callerArgList.get(j);
764 if (callerLoc1.get(callerLoc1.getSize() - 1).isTop()
765 || callerLoc2.get(callerLoc2.getSize() - 1).isTop()) {
769 System.out.println("calleeLoc1="+calleeLoc1);
770 System.out.println("calleeLoc2="+calleeLoc2+"calleeParamList="+calleeParamList);
773 CompositeLattice.compare(callerLoc1, callerLoc2, true,
774 generateErrorMessage(md.getClassDesc(), min));
776 CompositeLattice.compare(calleeLoc1, calleeLoc2, true,
777 generateErrorMessage(md.getClassDesc(), min));
779 if (calleeResult == ComparisonResult.GREATER
780 && callerResult != ComparisonResult.GREATER) {
781 // If calleeLoc1 is higher than calleeLoc2
782 // then, caller should have same ordering relation in-bet
783 // callerLoc1 & callerLoc2
785 String paramName1, paramName2;
788 paramName1 = "'THIS'";
790 paramName1 = "'parameter " + calleemd.getParamName(i - 1) + "'";
794 paramName2 = "'THIS'";
796 paramName2 = "'parameter " + calleemd.getParamName(j - 1) + "'";
800 "Caller doesn't respect an ordering relation among method arguments: callee expects that "
801 + paramName1 + " should be higher than " + paramName2 + " in " + calleemd
802 + " at " + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine());
813 private CompositeLocation inferRelationsFromArrayAccessNode(MethodDescriptor md,
814 SymbolTable nametable, ArrayAccessNode aan, CompositeLocation constraint, boolean isLHS) {
816 ClassDescriptor cd = md.getClassDesc();
818 CompositeLocation arrayLoc =
819 inferRelationsFromExpressionNode(md, nametable, aan.getExpression(),
820 new CompositeLocation(), constraint, isLHS);
821 // addTypeLocation(aan.getExpression().getType(), arrayLoc);
822 CompositeLocation indexLoc =
823 inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(),
825 // addTypeLocation(aan.getIndex().getType(), indexLoc);
828 if (!CompositeLattice.isGreaterThan(indexLoc, arrayLoc, generateErrorMessage(cd, aan))) {
829 throw new Error("Array index value is not higher than array location at "
830 + generateErrorMessage(cd, aan));
834 Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
835 inputGLB.add(arrayLoc);
836 inputGLB.add(indexLoc);
837 return CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(cd, aan));
842 private CompositeLocation inferRelationsFromCreateObjectNode(MethodDescriptor md,
843 SymbolTable nametable, CreateObjectNode con) {
845 ClassDescriptor cd = md.getClassDesc();
847 CompositeLocation compLoc = new CompositeLocation();
848 compLoc.addLocation(Location.createTopLocation(md));
853 private CompositeLocation inferRelationsFromOpNode(MethodDescriptor md, SymbolTable nametable,
854 OpNode on, CompositeLocation constraint) {
856 ClassDescriptor cd = md.getClassDesc();
857 CompositeLocation leftLoc = new CompositeLocation();
859 inferRelationsFromExpressionNode(md, nametable, on.getLeft(), leftLoc, constraint, false);
860 // addTypeLocation(on.getLeft().getType(), leftLoc);
862 CompositeLocation rightLoc = new CompositeLocation();
863 if (on.getRight() != null) {
865 inferRelationsFromExpressionNode(md, nametable, on.getRight(), rightLoc, constraint, false);
866 // addTypeLocation(on.getRight().getType(), rightLoc);
869 System.out.println("\n# OP NODE=" + on.printNode(0));
870 System.out.println("# left loc=" + leftLoc + " from " + on.getLeft().getClass());
871 if (on.getRight() != null) {
872 System.out.println("# right loc=" + rightLoc + " from " + on.getRight().getClass());
875 Operation op = on.getOp();
877 switch (op.getOp()) {
879 case Operation.UNARYPLUS:
880 case Operation.UNARYMINUS:
881 case Operation.LOGIC_NOT:
885 case Operation.LOGIC_OR:
886 case Operation.LOGIC_AND:
888 case Operation.BIT_OR:
889 case Operation.BIT_XOR:
890 case Operation.BIT_AND:
891 case Operation.ISAVAILABLE:
892 case Operation.EQUAL:
893 case Operation.NOTEQUAL:
903 case Operation.LEFTSHIFT:
904 case Operation.RIGHTSHIFT:
905 case Operation.URIGHTSHIFT:
907 Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
908 inputSet.add(leftLoc);
909 inputSet.add(rightLoc);
910 CompositeLocation glbCompLoc =
911 CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
912 System.out.println("# glbCompLoc=" + glbCompLoc);
916 throw new Error(op.toString());
921 private VarID inferRelationsFromLiteralNode(MethodDescriptor md,
922 SymbolTable nametable, LiteralNode ln) {
923 //literal data flow does not matter
928 private VarID inferRelationsFromNameNode(MethodDescriptor md, SymbolTable nametable,
929 NameNode nn, VarID flowTo) {
931 NameDescriptor nd = nn.getName();
932 if (nd.getBase() != null) {
934 inferRelationsFromExpressionNode(md, nametable, nn.getExpression(), flowTo, false);
936 String varname = nd.toString();
937 if (varname.equals("this")) {
940 rSet.addRelation(new BinaryRelation(var,flowTo));
946 Descriptor d = (Descriptor) nametable.get(varname);
948 if (d instanceof VarDescriptor) {
951 rSet.addRelation(new BinaryRelation(var,flowTo));
953 } else if (d instanceof FieldDescriptor) {
954 FieldDescriptor fd = (FieldDescriptor) d;
959 rSet.addRelation(new BinaryRelation(var,flowTo));
966 rSet.addRelation(new BinaryRelation(var,flowTo));
973 rSet.addRelation(new BinaryRelation(var,flowTo));
977 } else if (d == null) {
980 rSet.addRelation(new BinaryRelation(var,flowTo));
989 private CompositeLocation inferRelationsFromFieldAccessNode(MethodDescriptor md,
990 SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc,
991 CompositeLocation constraint) {
993 ExpressionNode left = fan.getExpression();
994 TypeDescriptor ltd = left.getType();
996 FieldDescriptor fd = fan.getField();
998 String varName = null;
999 if (left.kind() == Kind.NameNode) {
1000 NameDescriptor nd = ((NameNode) left).getName();
1001 varName = nd.toString();
1004 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
1005 // using a class name directly or access using this
1006 if (fd.isStatic() && fd.isFinal()) {
1007 loc.addLocation(Location.createTopLocation(md));
1012 loc = inferRelationsFromExpressionNode(md, nametable, left, loc, constraint, false);
1013 System.out.println("### inferRelationsFromFieldAccessNode=" + fan.printNode(0));
1014 System.out.println("### left=" + left.printNode(0));
1015 if (!left.getType().isPrimitive()) {
1016 Location fieldLoc = getFieldLocation(fd);
1017 loc.addLocation(fieldLoc);
1023 private Location getFieldLocation(FieldDescriptor fd) {
1025 System.out.println("### getFieldLocation=" + fd);
1026 System.out.println("### fd.getType().getExtension()=" + fd.getType().getExtension());
1028 Location fieldLoc = (Location) fd.getType().getExtension();
1030 // handle the case that method annotation checking skips checking field
1032 if (fieldLoc == null) {
1033 fieldLoc = checkFieldDeclaration(fd.getClassDescriptor(), fd);
1040 private VarID inferRelationsFromAssignmentNode(MethodDescriptor md,
1041 SymbolTable nametable, AssignmentNode an, VarID flowTo) {
1042 ClassDescriptor cd = md.getClassDesc();
1043 boolean postinc = true;
1045 if (an.getOperation().getBaseOp() == null
1046 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
1047 .getBaseOp().getOp() != Operation.POSTDEC))
1049 //get ID for leftside
1050 VarID destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), flowTo, true);
1053 //recursively add relations from RHS to LHS
1054 inferRelationsFromExpressionNode(md, nametable, an.getSrc(), destID, false);
1057 //add relation to self
1058 destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), destID, false);
1061 //checks if flow to anythin and adds relation
1063 rSet.addRelation(new BinaryRelation(destID, flowTo));
1066 //add relations for implicit flow
1067 for(ImplicitTuple it: implicitFlowSet){
1068 rSet.addRelation(new BinaryRelation(it.getVar(),destID));