import java.util.StringTokenizer;
import java.util.Vector;
+import Analysis.SSJava.FlowDownCheck.ComparisonResult;
+import Analysis.SSJava.FlowDownCheck.CompositeLattice;
import IR.AnnotationDescriptor;
import IR.ClassDescriptor;
import IR.Descriptor;
import IR.Tree.OpNode;
import IR.Tree.ReturnNode;
import IR.Tree.SubBlockNode;
+import IR.Tree.SwitchBlockNode;
+import IR.Tree.SwitchStatementNode;
import IR.Tree.TertiaryNode;
import IR.Tree.TreeNode;
import Util.Pair;
public class FlowDownCheck {
- static State state;
+ State state;
static SSJavaAnalysis ssjava;
HashSet toanalyze;
// mapping from 'descriptor' to 'composite location'
Hashtable<Descriptor, CompositeLocation> d2loc;
+ Hashtable<MethodDescriptor, CompositeLocation> md2ReturnLoc;
+ Hashtable<MethodDescriptor, ReturnLocGenerator> md2ReturnLocGen;
+
// mapping from 'locID' to 'class descriptor'
Hashtable<String, ClassDescriptor> fieldLocName2cd;
this.toanalyze = new HashSet();
this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
- init();
+ this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
+ this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
}
public void init() {
ClassDescriptor cd = (ClassDescriptor) obj;
toanalyze.remove(cd);
- if (!cd.isInterface()) {
+ if (ssjava.needToBeAnnoated(cd) && (!cd.isInterface())) {
ClassDescriptor superDesc = cd.getSuperDesc();
if (superDesc != null && (!superDesc.isInterface())
checkDeclarationInClass(cd);
for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
MethodDescriptor md = (MethodDescriptor) method_it.next();
- try {
+ if (ssjava.needTobeAnnotated(md)) {
checkDeclarationInMethodBody(cd, md);
- } catch (Error e) {
- System.out.println("Error in " + md);
- throw e;
}
}
}
checkClass(cd);
for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
MethodDescriptor md = (MethodDescriptor) method_it.next();
- try {
+ if (ssjava.needTobeAnnotated(md)) {
checkMethodBody(cd, md);
- } catch (Error e) {
- System.out.println("Error in " + md);
- throw e;
}
}
}
SSJavaLattice<String> superLattice = ssjava.getClassLattice(superCd);
SSJavaLattice<String> subLattice = ssjava.getClassLattice(cd);
- Set<Pair<String, String>> superPairSet = superLattice.getOrderingPairSet();
- Set<Pair<String, String>> subPairSet = subLattice.getOrderingPairSet();
+ if (superLattice != null) {
+
+ if (subLattice == null) {
+ throw new Error("If a parent class '" + superCd
+ + "' has a ordering lattice, its subclass '" + cd + "' should have one.");
+ }
- for (Iterator iterator = superPairSet.iterator(); iterator.hasNext();) {
- Pair<String, String> pair = (Pair<String, String>) iterator.next();
+ Set<Pair<String, String>> superPairSet = superLattice.getOrderingPairSet();
+ Set<Pair<String, String>> subPairSet = subLattice.getOrderingPairSet();
- if (!subPairSet.contains(pair)) {
- throw new Error("Subclass '" + cd + "' does not have the relative ordering '"
- + pair.getSecond() + " < " + pair.getFirst() + "' that is defined by its superclass '"
- + superCd + "'.");
+ for (Iterator iterator = superPairSet.iterator(); iterator.hasNext();) {
+ Pair<String, String> pair = (Pair<String, String>) iterator.next();
+
+ if (!subPairSet.contains(pair)) {
+ throw new Error("Subclass '" + cd + "' does not have the relative ordering '"
+ + pair.getSecond() + " < " + pair.getFirst()
+ + "' that is defined by its superclass '" + superCd + "'.");
+ }
}
+
}
+ // if super class doesn't define lattice, then we don't need to check its
+ // subclass
}
private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
BlockNode bn = state.getMethodBody(md);
+
+ // parsing returnloc annotation
+ if (ssjava.needTobeAnnotated(md)) {
+
+ Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
+ if (methodAnnotations != null) {
+ for (int i = 0; i < methodAnnotations.size(); i++) {
+ AnnotationDescriptor an = methodAnnotations.elementAt(i);
+ if (an.getMarker().equals(ssjava.RETURNLOC)) {
+ // developer explicitly defines method lattice
+ String returnLocDeclaration = an.getValue();
+ CompositeLocation returnLocComp =
+ parseLocationDeclaration(md, null, returnLocDeclaration);
+ md2ReturnLoc.put(md, returnLocComp);
+ }
+ }
+
+ if (!md.getReturnType().isVoid() && !md2ReturnLoc.containsKey(md)) {
+ throw new Error("Return location is not specified for the method " + md + " at "
+ + cd.getSourceFileName());
+ }
+
+ }
+ }
+
+ List<CompositeLocation> paramList = new ArrayList<CompositeLocation>();
+
+ boolean hasReturnValue = (!md.getReturnType().isVoid());
+ if (hasReturnValue) {
+ MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
+ String thisLocId = methodLattice.getThisLoc();
+ if (thisLocId == null) {
+ throw new Error("Method '" + md + "' does not have the definition of 'this' location at "
+ + md.getClassDesc().getSourceFileName());
+ }
+ CompositeLocation thisLoc = new CompositeLocation(new Location(md, thisLocId));
+ paramList.add(thisLoc);
+ }
+
for (int i = 0; i < md.numParameters(); i++) {
// process annotations on method parameters
VarDescriptor vd = (VarDescriptor) md.getParameter(i);
assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
+ if (hasReturnValue) {
+ paramList.add(d2loc.get(vd));
+ }
}
+
+ if (hasReturnValue) {
+ md2ReturnLocGen.put(md, new ReturnLocGenerator(md2ReturnLoc.get(md), paramList,
+ generateErrorMessage(cd, null)));
+ }
+
checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
}
checkLocationFromBlockNode(md, md.getParameterTable(), bn);
}
+ private String generateErrorMessage(ClassDescriptor cd, TreeNode tn) {
+ if (tn != null) {
+ return cd.getSourceFileName() + "::" + tn.getNumLine();
+ } else {
+ return cd.getSourceFileName();
+ }
+
+ }
+
private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
BlockNode bn) {
bn.getVarTable().setParent(nametable);
// it will return the lowest location in the block node
CompositeLocation lowestLoc = null;
+
for (int i = 0; i < bn.size(); i++) {
BlockStatementNode bsn = bn.get(i);
CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
- if (lowestLoc == null) {
- lowestLoc = bLoc;
- } else {
- if (!bLoc.isEmpty()) {
- if (CompositeLattice.isGreaterThan(lowestLoc, bLoc)) {
+ if (!bLoc.isEmpty()) {
+ if (lowestLoc == null) {
+ lowestLoc = bLoc;
+ } else {
+ if (CompositeLattice.isGreaterThan(lowestLoc, bLoc,
+ generateErrorMessage(md.getClassDesc(), bn))) {
lowestLoc = bLoc;
}
}
}
+
}
+
+ if (lowestLoc == null) {
+ lowestLoc = new CompositeLocation(Location.createBottomLocation(md));
+ }
+
return lowestLoc;
}
compLoc = checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
break;
- // case Kind.ContinueBreakNode:
- // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
- // bsn);
- // return null;
+ case Kind.ContinueBreakNode:
+ compLoc = new CompositeLocation();
+ break;
+
+ case Kind.SwitchStatementNode:
+ compLoc = checkLocationFromSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
+
}
return compLoc;
}
+ private CompositeLocation checkLocationFromSwitchStatementNode(MethodDescriptor md,
+ SymbolTable nametable, SwitchStatementNode ssn) {
+
+ ClassDescriptor cd = md.getClassDesc();
+ CompositeLocation condLoc =
+ checkLocationFromExpressionNode(md, nametable, ssn.getCondition(), new CompositeLocation());
+ BlockNode sbn = ssn.getSwitchBody();
+
+ Set<CompositeLocation> blockLocSet = new HashSet<CompositeLocation>();
+ for (int i = 0; i < sbn.size(); i++) {
+ CompositeLocation blockLoc =
+ checkLocationFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
+ if (!CompositeLattice.isGreaterThan(condLoc, blockLoc,
+ generateErrorMessage(cd, ssn.getCondition()))) {
+ throw new Error(
+ "The location of the switch-condition statement is lower than the conditional body at "
+ + cd.getSourceFileName() + ":" + ssn.getCondition().getNumLine());
+ }
+
+ blockLocSet.add(blockLoc);
+ }
+ return CompositeLattice.calculateGLB(blockLocSet);
+ }
+
+ private CompositeLocation checkLocationFromSwitchBlockNode(MethodDescriptor md,
+ SymbolTable nametable, SwitchBlockNode sbn) {
+
+ CompositeLocation blockLoc =
+ checkLocationFromBlockNode(md, nametable, sbn.getSwitchBlockStatement());
+
+ return blockLoc;
+
+ }
+
private CompositeLocation checkLocationFromReturnNode(MethodDescriptor md, SymbolTable nametable,
ReturnNode rn) {
ExpressionNode returnExp = rn.getReturnExpression();
- CompositeLocation expLoc =
- checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation());
-
- // callee should have a relative ordering in-between parameters and return
- // value, which is required by caller's constraint
- for (int i = 0; i < md.numParameters(); i++) {
- Descriptor calleevd = md.getParameter(i);
- CompositeLocation calleeParamLoc = d2loc.get(calleevd);
-
- // here, parameter(input value) should be higher than result(output)
- if ((!expLoc.get(0).isTop()) && !CompositeLattice.isGreaterThan(calleeParamLoc, expLoc)) {
- throw new Error("Callee " + md + " doesn't have the ordering relation between parameter '"
- + calleevd + "' and its return value '" + returnExp.printNode(0) + "'.");
+ CompositeLocation expLoc;
+ if (returnExp != null) {
+ expLoc = checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation());
+ // check if return value is equal or higher than RETRUNLOC of method
+ // declaration annotation
+ CompositeLocation returnLocAt = md2ReturnLoc.get(md);
+
+ if (CompositeLattice.isGreaterThan(returnLocAt, expLoc,
+ generateErrorMessage(md.getClassDesc(), rn))) {
+ throw new Error(
+ "Return value location is not equal or higher than the declaraed return location at "
+ + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
}
}
- // by default, return node has "bottom" location
- CompositeLocation loc = new CompositeLocation();
- loc.addLocation(Location.createBottomLocation(md));
- return loc;
+ return new CompositeLocation();
}
private boolean hasOnlyLiteralValue(ExpressionNode en) {
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation());
- addTypeLocation(ln.getCondition().getType(), (condLoc));
+ addLocationType(ln.getCondition().getType(), (condLoc));
CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
- if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc)) {
+ if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc, generateErrorMessage(cd, ln))) {
// loop condition should be higher than loop body
throw new Error(
"The location of the while-condition statement is lower than the loop body at "
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
new CompositeLocation());
- addTypeLocation(ln.getCondition().getType(), condLoc);
+ addLocationType(ln.getCondition().getType(), condLoc);
CompositeLocation updateLoc =
checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
glbInputSet.add(condLoc);
- glbInputSet.add(updateLoc);
+ // glbInputSet.add(updateLoc);
CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(glbInputSet);
// check location of 'forloop' body
CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
+ // compute glb of body including loop body and update statement
+ glbInputSet.clear();
+
if (blockLoc == null) {
// when there is no statement in the loop body
- return glbLocOfForLoopCond;
+
+ if (updateLoc == null) {
+ // also there is no update statement in the loop body
+ return glbLocOfForLoopCond;
+ }
+ glbInputSet.add(updateLoc);
+
+ } else {
+ glbInputSet.add(blockLoc);
+ glbInputSet.add(updateLoc);
}
- if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc)) {
+ CompositeLocation loopBodyLoc = CompositeLattice.calculateGLB(glbInputSet);
+
+ if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, loopBodyLoc,
+ generateErrorMessage(cd, ln))) {
throw new Error(
"The location of the for-condition statement is lower than the for-loop body at "
+ cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation());
- addTypeLocation(isn.getCondition().getType(), condLoc);
+ addLocationType(isn.getCondition().getType(), condLoc);
glbInputSet.add(condLoc);
CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
glbInputSet.add(locTrueBlock);
// here, the location of conditional block should be higher than the
// location of true/false blocks
- if (locTrueBlock != null && !CompositeLattice.isGreaterThan(condLoc, locTrueBlock)) {
+ if (locTrueBlock != null
+ && !CompositeLattice.isGreaterThan(condLoc, locTrueBlock,
+ generateErrorMessage(localCD, isn.getCondition()))) {
// error
throw new Error(
"The location of the if-condition statement is lower than the conditional block at "
if (locFalseBlock != null) {
glbInputSet.add(locFalseBlock);
- if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock)) {
+ if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock,
+ generateErrorMessage(localCD, isn.getCondition()))) {
// error
throw new Error(
"The location of the if-condition statement is lower than the conditional block at "
private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
SymbolTable nametable, DeclarationNode dn) {
+ System.out.println("DeclarationNode=" + dn.printNode(0));
+
VarDescriptor vd = dn.getVarDescriptor();
CompositeLocation destLoc = d2loc.get(vd);
if (expressionLoc != null) {
// checking location order
- if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc)) {
+ if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc,
+ generateErrorMessage(md.getClassDesc(), dn))) {
throw new Error("The value flow from " + expressionLoc + " to " + destLoc
+ " does not respect location hierarchy on the assignment " + dn.printNode(0)
+ " at " + md.getClassDesc().getSourceFileName() + "::" + dn.getNumLine());
} else {
- // if (destLoc instanceof Location) {
- // CompositeLocation comp = new CompositeLocation();
- // comp.addLocation(destLoc);
- // return comp;
- // } else {
- // return (CompositeLocation) destLoc;
- // }
- return destLoc;
+ return new CompositeLocation();
}
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation());
- addTypeLocation(tn.getCond().getType(), condLoc);
+ addLocationType(tn.getCond().getType(), condLoc);
CompositeLocation trueLoc =
checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation());
- addTypeLocation(tn.getTrueExpr().getType(), trueLoc);
+ addLocationType(tn.getTrueExpr().getType(), trueLoc);
CompositeLocation falseLoc =
checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation());
- addTypeLocation(tn.getFalseExpr().getType(), falseLoc);
+ addLocationType(tn.getFalseExpr().getType(), falseLoc);
+ // locations from true/false branches can be TOP when there are only literal values
+ // in this case, we don't need to check flow down rule!
+
// check if condLoc is higher than trueLoc & falseLoc
- if (!CompositeLattice.isGreaterThan(condLoc, trueLoc)) {
+ if (!trueLoc.get(0).isTop() && !CompositeLattice.isGreaterThan(condLoc, trueLoc, generateErrorMessage(cd, tn))) {
throw new Error(
"The location of the condition expression is lower than the true expression at "
+ cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
}
- if (!CompositeLattice.isGreaterThan(condLoc, falseLoc)) {
+ if (!falseLoc.get(0).isTop() && !CompositeLattice.isGreaterThan(condLoc, falseLoc, generateErrorMessage(cd, tn.getCond()))) {
throw new Error(
"The location of the condition expression is lower than the true expression at "
+ cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
checkCalleeConstraints(md, nametable, min);
- // all we need to care about is that
- // method output(return value) should be lower than input values(method
- // parameters)
- Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
+ CompositeLocation baseLocation = null;
+ if (min.getExpression() != null) {
+ baseLocation =
+ checkLocationFromExpressionNode(md, nametable, min.getExpression(),
+ new CompositeLocation());
+ } else {
+ String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
+ baseLocation = new CompositeLocation(new Location(md, thisLocId));
+ }
+
+ if (!min.getMethod().getReturnType().isVoid()) {
+ // If method has a return value, compute the highest possible return
+ // location in the caller's perspective
+ CompositeLocation ceilingLoc =
+ computeCeilingLocationForCaller(md, nametable, min, baseLocation);
+ return ceilingLoc;
+ }
+
+ return new CompositeLocation();
+
+ }
+
+ private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
+ SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation) {
+ List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
+
+ // by default, method has a THIS parameter
+ argList.add(baseLocation);
+
for (int i = 0; i < min.numArgs(); i++) {
ExpressionNode en = min.getArg(i);
CompositeLocation callerArg =
checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
- inputGLBSet.add(callerArg);
+ argList.add(callerArg);
}
- if (inputGLBSet.size() > 0) {
- return CompositeLattice.calculateGLB(inputGLBSet);
- } else {
- // if there are no arguments, just return TOP location
- CompositeLocation compLoc = new CompositeLocation();
- compLoc.addLocation(Location.createTopLocation(md));
- return compLoc;
- }
+ System.out.println("##");
+ System.out.println("min.getMethod()=" + min.getMethod());
+ System.out.println("md2ReturnLocGen.get(min.getMethod())="
+ + md2ReturnLocGen.get(min.getMethod()));
+
+ return md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
}
VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
CompositeLocation calleeLoc2 = d2loc.get(calleevd2);
- boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2);
- boolean calleeResult = CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2);
-
- if (calleeResult && !callerResult) {
+ int callerResult =
+ CompositeLattice.compare(callerArg1, callerArg2,
+ generateErrorMessage(md.getClassDesc(), min));
+ int calleeResult =
+ CompositeLattice.compare(calleeLoc1, calleeLoc2,
+ generateErrorMessage(md.getClassDesc(), min));
+ if (calleeResult == ComparisonResult.GREATER
+ && callerResult != ComparisonResult.GREATER) {
// If calleeLoc1 is higher than calleeLoc2
// then, caller should have same ordering relation in-bet
// callerLoc1 & callerLoc2
CompositeLocation argLoc =
checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
glbInputSet.add(argLoc);
- addTypeLocation(en.getType(), argLoc);
+ addLocationType(en.getType(), argLoc);
}
// check array initializers
ExpressionNode left = fan.getExpression();
loc = checkLocationFromExpressionNode(md, nametable, left, loc);
- // addTypeLocation(left.getType(), loc);
if (!left.getType().isPrimitive()) {
FieldDescriptor fd = fan.getField();
return destLocation;
}
srcLocation = new CompositeLocation();
+ System.out.println("checkLocationFromExpressionNode=" + an.getSrc().printNode(0));
srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
// System.out.println(" an= " + an.printNode(0) + " an.getSrc()=" +
// an.getSrc().getClass()
// + " at " + cd.getSourceFileName() + "::" + an.getNumLine());
// System.out.println("srcLocation=" + srcLocation);
// System.out.println("dstLocation=" + destLocation);
- if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
+ if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, generateErrorMessage(cd, an))) {
throw new Error("The value flow from " + srcLocation + " to " + destLocation
+ " does not respect location hierarchy on the assignment " + an.printNode(0) + " at "
+ cd.getSourceFileName() + "::" + an.getNumLine());
destLocation =
srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
- if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
+ if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, generateErrorMessage(cd, an))) {
throw new Error("Location " + destLocation
+ " is not allowed to have the value flow that moves within the same location at "
+ cd.getSourceFileName() + "::" + an.getNumLine());
ClassDescriptor cd = md.getClassDesc();
Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
- // currently enforce every variable to have corresponding location
- if (annotationVec.size() == 0) {
- throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
- + md.getSymbol() + " of the class " + cd.getSymbol());
- }
+ if (!md.getModifiers().isAbstract()) {
+ // currently enforce every variable to have corresponding location
+ if (annotationVec.size() == 0) {
+ throw new Error("Location is not assigned to variable " + vd.getSymbol()
+ + " in the method " + md.getSymbol() + " of the class " + cd.getSymbol());
+ }
- if (annotationVec.size() > 1) { // variable can have at most one location
- throw new Error(vd.getSymbol() + " has more than one location.");
- }
+ if (annotationVec.size() > 1) { // variable can have at most one location
+ throw new Error(vd.getSymbol() + " has more than one location.");
+ }
- AnnotationDescriptor ad = annotationVec.elementAt(0);
+ AnnotationDescriptor ad = annotationVec.elementAt(0);
- if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
+ if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
- if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
- String locDec = ad.getValue(); // check if location is defined
+ if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
+ String locDec = ad.getValue(); // check if location is defined
- if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
- DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
- d2loc.put(vd, deltaLoc);
- addTypeLocation(vd.getType(), deltaLoc);
- } else {
- CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
- d2loc.put(vd, compLoc);
- addTypeLocation(vd.getType(), compLoc);
- }
+ if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
+ DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
+ d2loc.put(vd, deltaLoc);
+ addLocationType(vd.getType(), deltaLoc);
+ } else {
+ CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
+
+ Location lastElement = compLoc.get(compLoc.getSize() - 1);
+ if (ssjava.isSharedLocation(lastElement)) {
+ ssjava.mapSharedLocation2Descriptor(lastElement, vd);
+ }
+
+ d2loc.put(vd, compLoc);
+ addLocationType(vd.getType(), compLoc);
+ }
+ }
}
}
return deltaLoc;
}
+ private Location parseFieldLocDeclaraton(String decl, String msg) {
+
+ int idx = decl.indexOf(".");
+ String className = decl.substring(0, idx);
+ String fieldName = decl.substring(idx + 1);
+
+ className.replaceAll(" ", "");
+ fieldName.replaceAll(" ", "");
+
+ Descriptor d = state.getClassSymbolTable().get(className);
+
+ if (d == null) {
+ System.out.println("className="+className+" to d="+d);
+ throw new Error("The class in the location declaration '" + decl + "' does not exist at "
+ + msg);
+ }
+
+ assert (d instanceof ClassDescriptor);
+ SSJavaLattice<String> lattice = ssjava.getClassLattice((ClassDescriptor) d);
+ if (!lattice.containsKey(fieldName)) {
+ throw new Error("The location " + fieldName + " is not defined in the field lattice of '"
+ + className + "' at "+msg);
+ }
+
+ return new Location(d, fieldName);
+ }
+
private CompositeLocation parseLocationDeclaration(MethodDescriptor md, TreeNode n, String locDec) {
CompositeLocation compLoc = new CompositeLocation();
if (localLattice == null || (!localLattice.containsKey(localLocId))) {
throw new Error("Location " + localLocId
+ " is not defined in the local variable lattice at "
- + md.getClassDesc().getSourceFileName() + "::" + n.getNumLine() + ".");
+ + md.getClassDesc().getSourceFileName() + "::" + (n != null ? n.getNumLine() : "") + ".");
}
compLoc.addLocation(localLoc);
for (int i = 1; i < locIdList.size(); i++) {
String locName = locIdList.get(i);
- ClassDescriptor cd = fieldLocName2cd.get(locName);
-
- SSJavaLattice<String> fieldLattice = CompositeLattice.getLatticeByDescriptor(cd);
- if (fieldLattice == null || (!fieldLattice.containsKey(locName))) {
- throw new Error("Location " + locName + " is not defined in the field lattice at "
- + cd.getSourceFileName() + ".");
- }
-
- Location fieldLoc = new Location(cd, locName);
+ Location fieldLoc =
+ parseFieldLocDeclaraton(locName, generateErrorMessage(md.getClassDesc(), n));
+ // ClassDescriptor cd = fieldLocName2cd.get(locName);
+ // SSJavaLattice<String> fieldLattice =
+ // CompositeLattice.getLatticeByDescriptor(cd);
+ //
+ // if (fieldLattice == null || (!fieldLattice.containsKey(locName))) {
+ // throw new Error("Location " + locName +
+ // " is not defined in the field lattice at "
+ // + cd.getSourceFileName() + ".");
+ // }
+ // Location fieldLoc = new Location(cd, locName);
compLoc.addLocation(fieldLoc);
}
// Check to see that fields are okay
for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
FieldDescriptor fd = (FieldDescriptor) field_it.next();
- checkFieldDeclaration(cd, fd);
+
+ if (!(fd.isFinal() && fd.isStatic())) {
+ checkFieldDeclaration(cd, fd);
+ }
}
}
// currently enforce every field to have corresponding location
if (annotationVec.size() == 0) {
- throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
- + cd.getSymbol());
+ throw new Error("Location is not assigned to the field '" + fd.getSymbol()
+ + "' of the class " + cd.getSymbol() + " at " + cd.getSourceFileName());
}
if (annotationVec.size() > 1) {
+ cd.getSourceFileName() + ".");
}
Location loc = new Location(cd, locationID);
- // d2loc.put(fd, loc);
- addTypeLocation(fd.getType(), loc);
+
+ if (ssjava.isSharedLocation(loc)) {
+ ssjava.mapSharedLocation2Descriptor(loc, fd);
+ }
+
+ addLocationType(fd.getType(), loc);
}
}
}
- private void addTypeLocation(TypeDescriptor type, CompositeLocation loc) {
+ private void addLocationType(TypeDescriptor type, CompositeLocation loc) {
if (type != null) {
type.setExtension(loc);
}
}
- private void addTypeLocation(TypeDescriptor type, Location loc) {
+ private void addLocationType(TypeDescriptor type, Location loc) {
if (type != null) {
type.setExtension(loc);
}
static class CompositeLattice {
- public static boolean isGreaterThan(CompositeLocation loc1, CompositeLocation loc2) {
+ public static boolean isGreaterThan(CompositeLocation loc1, CompositeLocation loc2, String msg) {
- // System.out.println("isGreaterThan= " + loc1 + " " + loc2);
-
- int baseCompareResult = compareBaseLocationSet(loc1, loc2);
+ System.out.println("isGreaterThan="+loc1+" "+loc2+" msg="+msg);
+ int baseCompareResult = compareBaseLocationSet(loc1, loc2, true, msg);
if (baseCompareResult == ComparisonResult.EQUAL) {
if (compareDelta(loc1, loc2) == ComparisonResult.GREATER) {
return true;
}
+ public static int compare(CompositeLocation loc1, CompositeLocation loc2, String msg) {
+
+ // System.out.println("compare=" + loc1 + " " + loc2);
+ int baseCompareResult = compareBaseLocationSet(loc1, loc2, false, msg);
+
+ if (baseCompareResult == ComparisonResult.EQUAL) {
+ return compareDelta(loc1, loc2);
+ } else {
+ return baseCompareResult;
+ }
+
+ }
+
private static int compareDelta(CompositeLocation dLoc1, CompositeLocation dLoc2) {
int deltaCount1 = 0;
}
- private static int compareBaseLocationSet(CompositeLocation compLoc1, CompositeLocation compLoc2) {
+ private static int compareBaseLocationSet(CompositeLocation compLoc1,
+ CompositeLocation compLoc2, boolean awareSharedLoc, String msg) {
// if compLoc1 is greater than compLoc2, return true
// else return false;
if (!loc1.getDescriptor().equals(loc2.getDescriptor())) {
throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
- + " because they are not comparable.");
+ + " because they are not comparable at "+msg);
}
Descriptor d1 = loc1.getDescriptor();
if (lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
if (i != (compLoc1.getSize() - 1)) {
throw new Error("The spin location " + loc1.getLocIdentifier()
- + " cannot be appeared in the middle of composite location.");
+ + " cannot be appeared in the middle of composite location at" + msg);
}
}
if (lattice2.getSpinLocSet().contains(loc2.getLocIdentifier())) {
if (i != (compLoc2.getSize() - 1)) {
throw new Error("The spin location " + loc2.getLocIdentifier()
- + " cannot be appeared in the middle of composite location.");
+ + " cannot be appeared in the middle of composite location at " + msg);
}
}
if (!lattice1.equals(lattice2)) {
throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
- + " because they are not comparable.");
+ + " because they are not comparable at " + msg);
}
if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
// check if the current location is the spinning location
// note that the spinning location only can be appeared in the last
// part of the composite location
- if (numOfTie == compLoc1.getSize()
+ if (awareSharedLoc && numOfTie == compLoc1.getSize()
&& lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
return ComparisonResult.GREATER;
}
if (numOfTie != compLoc2.getSize()) {
throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
- + " because they are not comparable.");
+ + " because they are not comparable at "+msg);
}
return ComparisonResult.EQUAL;
public static CompositeLocation calculateGLB(Set<CompositeLocation> inputSet) {
+ System.out.println("calculateGLB="+inputSet);
// System.out.println("Calculating GLB=" + inputSet);
CompositeLocation glbCompLoc = new CompositeLocation();
// mapping from the priority loc ID to its full representation by the
// composite location
+ int maxTupleSize = 0;
+ CompositeLocation maxCompLoc = null;
+
for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
CompositeLocation compLoc = (CompositeLocation) iterator.next();
+ if (compLoc.getSize() > maxTupleSize) {
+ maxTupleSize = compLoc.getSize();
+ maxCompLoc = compLoc;
+ }
Location priorityLoc = compLoc.get(0);
String priorityLocId = priorityLoc.getLocIdentifier();
priorityLocIdentifierSet.add(priorityLocId);
- if (locId2CompLocSet.contains(priorityLocId)) {
+ if (locId2CompLocSet.containsKey(priorityLocId)) {
locId2CompLocSet.get(priorityLocId).add(compLoc);
} else {
Set<CompositeLocation> newSet = new HashSet<CompositeLocation>();
glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc));
Set<CompositeLocation> compSet = locId2CompLocSet.get(glbOfPriorityLoc);
+ // here find out composite location that has a maximum length tuple
+ // if we have three input set: [A], [A,B], [A,B,C]
+ // maximum length tuple will be [A,B,C]
+ int max = 0;
+ CompositeLocation maxFromCompSet = null;
+ for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
+ CompositeLocation c = (CompositeLocation) iterator.next();
+ if (c.getSize() > max) {
+ max = c.getSize();
+ maxFromCompSet = c;
+ }
+ }
+
if (compSet == null) {
// when GLB(x1,x2)!=x1 and !=x2 : GLB case 4
// mean that the result is already lower than <x1,y1> and <x2,y2>
// assign TOP to the rest of the location elements
- CompositeLocation inputComp = inputSet.iterator().next();
+
+ // in this case, do not take care about delta
+ // CompositeLocation inputComp = inputSet.iterator().next();
+ CompositeLocation inputComp = maxCompLoc;
for (int i = 1; i < inputComp.getSize(); i++) {
glbCompLoc.addLocation(Location.createTopLocation(inputComp.get(i).getDescriptor()));
}
} else {
if (compSet.size() == 1) {
+
// if GLB(x1,x2)==x1 or x2 : GLB case 2,3
CompositeLocation comp = compSet.iterator().next();
for (int i = 1; i < comp.getSize(); i++) {
glbCompLoc.addLocation(comp.get(i));
}
+
+ // if input location corresponding to glb is a delta, need to apply
+ // delta to glb result
+ if (comp instanceof DeltaLocation) {
+ glbCompLoc = new DeltaLocation(glbCompLoc, 1);
+ }
+
} else {
// when GLB(x1,x2)==x1 and x2 : GLB case 1
// if more than one location shares the same priority GLB
// need to calculate the rest of GLB loc
- int compositeLocSize = compSet.iterator().next().getSize();
+ // int compositeLocSize = compSet.iterator().next().getSize();
+ int compositeLocSize = maxFromCompSet.getSize();
Set<String> glbInputSet = new HashSet<String>();
Descriptor currentD = null;
for (int i = 1; i < compositeLocSize; i++) {
for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
CompositeLocation compositeLocation = (CompositeLocation) iterator.next();
- Location currentLoc = compositeLocation.get(i);
- currentD = currentLoc.getDescriptor();
- // making set of the current location sharing the same idx
- glbInputSet.add(currentLoc.getLocIdentifier());
+ if (compositeLocation.getSize() > i) {
+ Location currentLoc = compositeLocation.get(i);
+ currentD = currentLoc.getDescriptor();
+ // making set of the current location sharing the same idx
+ glbInputSet.add(currentLoc.getLocIdentifier());
+ }
}
// calculate glb for the current lattice
glbCompLoc.addLocation(new Location(currentD, currentGLBLocId));
}
+ // if input location corresponding to glb is a delta, need to apply
+ // delta to glb result
+
+ for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
+ CompositeLocation compLoc = (CompositeLocation) iterator.next();
+ if (compLoc instanceof DeltaLocation) {
+ if (glbCompLoc.equals(compLoc)) {
+ glbCompLoc = new DeltaLocation(glbCompLoc, 1);
+ break;
+ }
+ }
+ }
+
}
}
public static final int GREATER = 0;
public static final int EQUAL = 1;
public static final int LESS = 2;
+ public static final int INCOMPARABLE = 3;
int result;
}
}
+
+class ReturnLocGenerator {
+
+ public static final int PARAMISHIGHER = 0;
+ public static final int PARAMISSAME = 1;
+ public static final int IGNORE = 2;
+
+ Hashtable<Integer, Integer> paramIdx2paramType;
+
+ public ReturnLocGenerator(CompositeLocation returnLoc, List<CompositeLocation> params, String msg) {
+ // creating mappings
+ paramIdx2paramType = new Hashtable<Integer, Integer>();
+ for (int i = 0; i < params.size(); i++) {
+ CompositeLocation param = params.get(i);
+ int compareResult = CompositeLattice.compare(param, returnLoc, msg);
+
+ int type;
+ if (compareResult == ComparisonResult.GREATER) {
+ type = 0;
+ } else if (compareResult == ComparisonResult.EQUAL) {
+ type = 1;
+ } else {
+ type = 2;
+ }
+ paramIdx2paramType.put(new Integer(i), new Integer(type));
+ }
+
+ }
+
+ public CompositeLocation computeReturnLocation(List<CompositeLocation> args) {
+
+ // compute the highest possible location in caller's side
+ assert paramIdx2paramType.keySet().size() == args.size();
+
+ Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
+ for (int i = 0; i < args.size(); i++) {
+ int type = (paramIdx2paramType.get(new Integer(i))).intValue();
+ CompositeLocation argLoc = args.get(i);
+ if (type == PARAMISHIGHER) {
+ // return loc is lower than param
+ DeltaLocation delta = new DeltaLocation(argLoc, 1);
+ inputGLB.add(delta);
+ } else if (type == PARAMISSAME) {
+ // return loc is equal or lower than param
+ inputGLB.add(argLoc);
+ }
+ }
+
+ // compute GLB of arguments subset that are same or higher than return
+ // location
+ CompositeLocation glb = CompositeLattice.calculateGLB(inputGLB);
+ return glb;
+ }
+}
projects / IRC.git / blobdiff