From b1c9f6cd7988f0f987afa80e7265aa9629b2136f Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 14 Jun 2011 00:01:51 +0000 Subject: [PATCH] fixes on GLB and returnloc calculation, etc. gets more class libraries --- Robust/src/Analysis/SSJava/FlowDownCheck.java | 89 +++++++++---- .../SSJava/MethodAnnotationCheck.java | 8 +- .../src/Analysis/SSJava/SSJavaAnalysis.java | 18 +-- .../Analysis/SSJava/SingleReferenceCheck.java | 9 +- Robust/src/ClassLibrary/SSJava/Integer.java | 117 ++++++++++++++++++ Robust/src/ClassLibrary/SSJava/Object.java | 15 ++- Robust/src/ClassLibrary/SSJava/String.java | 79 ++++++++---- Robust/src/ClassLibrary/SSJava/System.java | 62 ++++++++++ 8 files changed, 332 insertions(+), 65 deletions(-) create mode 100644 Robust/src/ClassLibrary/SSJava/Integer.java create mode 100644 Robust/src/ClassLibrary/SSJava/System.java diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index 46374bcd..c017ea49 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -114,7 +114,7 @@ public class FlowDownCheck { checkDeclarationInClass(cd); for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { MethodDescriptor md = (MethodDescriptor) method_it.next(); - if (ssjava.hasAnnotation(md)) { + if (ssjava.needAnnotation(md)) { checkDeclarationInMethodBody(cd, md); } } @@ -133,7 +133,7 @@ public class FlowDownCheck { checkClass(cd); for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { MethodDescriptor md = (MethodDescriptor) method_it.next(); - if (ssjava.hasAnnotation(md)) { + if (ssjava.needAnnotation(md)) { checkMethodBody(cd, md); } } @@ -176,7 +176,8 @@ public class FlowDownCheck { BlockNode bn = state.getMethodBody(md); // parsing returnloc annotation - if (ssjava.hasAnnotation(md)) { + if (ssjava.needAnnotation(md)) { + Vector methodAnnotations = md.getModifiers().getAnnotations(); if (methodAnnotations != null) { for (int i = 0; i < methodAnnotations.size(); i++) { @@ -340,10 +341,17 @@ public class FlowDownCheck { CompositeLocation expLoc = checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation()); - // by default, return node has "bottom" location - CompositeLocation loc = new CompositeLocation(); - loc.addLocation(Location.createBottomLocation(md)); - return loc; + // check if return value is equal or higher than RETRUNLOC of method + // declaration annotation + CompositeLocation returnLocAt = md2ReturnLoc.get(md); + + if (CompositeLattice.isGreaterThan(returnLocAt, expLoc)) { + throw new Error( + "Return value location is not equal or higher than the declaraed return location at " + + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine()); + } + + return new CompositeLocation(); } private boolean hasOnlyLiteralValue(ExpressionNode en) { @@ -630,8 +638,22 @@ public class FlowDownCheck { SymbolTable nametable, MethodInvokeNode min, CompositeLocation loc) { checkCalleeConstraints(md, nametable, min); + + 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()) { - CompositeLocation ceilingLoc = computeCeilingLocationForCaller(md, nametable, min); + // 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; } @@ -640,13 +662,11 @@ public class FlowDownCheck { } private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md, - SymbolTable nametable, MethodInvokeNode min) { - + SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation) { List argList = new ArrayList(); - String thisLocId = ssjava.getMethodLattice(md).getThisLoc(); - CompositeLocation thisLoc = new CompositeLocation(new Location(md, thisLocId)); - argList.add(thisLoc); + // by default, method has a THIS parameter + argList.add(baseLocation); for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = min.getArg(i); @@ -1120,8 +1140,8 @@ public class FlowDownCheck { // 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) { @@ -1187,7 +1207,7 @@ public class FlowDownCheck { public static int compare(CompositeLocation loc1, CompositeLocation loc2) { -// System.out.println("compare=" + loc1 + " " + loc2); + // System.out.println("compare=" + loc1 + " " + loc2); int baseCompareResult = compareBaseLocationSet(loc1, loc2); if (baseCompareResult == ComparisonResult.EQUAL) { @@ -1312,8 +1332,15 @@ public class FlowDownCheck { // 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); @@ -1341,13 +1368,27 @@ public class FlowDownCheck { glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc)); Set 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 and // assign TOP to the rest of the location elements // in this case, do not take care about delta - CompositeLocation inputComp = inputSet.iterator().next(); + // CompositeLocation inputComp = inputSet.iterator().next(); + CompositeLocation inputComp = maxCompLoc; for (int i = 1; i < inputComp.getSize(); i++) { glbCompLoc.addLocation(Location.createTopLocation(inputComp.get(i).getDescriptor())); } @@ -1371,17 +1412,20 @@ public class FlowDownCheck { // 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 glbInputSet = new HashSet(); 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 @@ -1482,7 +1526,6 @@ class ReturnLocGenerator { CompositeLocation argLoc = args.get(i); if (type == PARAMISHIGHER) { // return loc is lower than param - System.out.println("argLoc=" + argLoc); DeltaLocation delta = new DeltaLocation(argLoc, 1); inputGLB.add(delta); } else if (type == PARAMISSAME) { diff --git a/Robust/src/Analysis/SSJava/MethodAnnotationCheck.java b/Robust/src/Analysis/SSJava/MethodAnnotationCheck.java index 9f61ee21..fa628062 100644 --- a/Robust/src/Analysis/SSJava/MethodAnnotationCheck.java +++ b/Robust/src/Analysis/SSJava/MethodAnnotationCheck.java @@ -59,17 +59,19 @@ public class MethodAnnotationCheck { Object obj = toanalyze.iterator().next(); ClassDescriptor cd = (ClassDescriptor) obj; toanalyze.remove(cd); + if (!cd.isInterface()) { for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { MethodDescriptor md = (MethodDescriptor) method_it.next(); checkMethodBody(cd, md); } } + } for (Iterator iterator = annotatedMDSet.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); - ssjava.putHasAnnotation(md); + ssjava.putNeedAnnotation(md); } Set visited = new HashSet(); @@ -87,7 +89,7 @@ public class MethodAnnotationCheck { if (!visited.contains(p)) { visited.add(p); tovisit.add(calleeMD); - ssjava.putHasAnnotation(calleeMD); + ssjava.putNeedAnnotation(calleeMD); } } } @@ -117,7 +119,7 @@ public class MethodAnnotationCheck { MethodDescriptor matchmd = (MethodDescriptor) methodit.next(); if (md.matches(matchmd)) { if (matchmd.getClassDesc().equals(subCD)) { - ssjava.putHasAnnotation(matchmd); + ssjava.putNeedAnnotation(matchmd); } } } diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 772d6868..c2a71cba 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -28,7 +28,7 @@ public class SSJavaAnalysis { MethodAnnotationCheck methodAnnotationChecker; // if a method has annotations, the mapping has true - Hashtable md2hasAnnotation; + Hashtable md2needAnnotation; // class -> field lattice Hashtable> cd2lattice; @@ -45,7 +45,7 @@ public class SSJavaAnalysis { this.cd2lattice = new Hashtable>(); this.cd2methodDefault = new Hashtable>(); this.md2lattice = new Hashtable>(); - this.md2hasAnnotation = new Hashtable(); + this.md2needAnnotation = new Hashtable(); } public void doCheck() { @@ -73,7 +73,7 @@ public class SSJavaAnalysis { } public void doSingleReferenceCheck() { - SingleReferenceCheck checker = new SingleReferenceCheck(state); + SingleReferenceCheck checker = new SingleReferenceCheck(this, state); checker.singleReferenceCheck(); } @@ -103,7 +103,7 @@ public class SSJavaAnalysis { MethodDescriptor md = (MethodDescriptor) method_it.next(); // parsing location hierarchy declaration for the method - if (hasAnnotation(md)) { + if (needAnnotation(md)) { Vector methodAnnotations = md.getModifiers().getAnnotations(); if (methodAnnotations != null) { for (int i = 0; i < methodAnnotations.size(); i++) { @@ -232,16 +232,16 @@ public class SSJavaAnalysis { } } - public boolean hasAnnotation(MethodDescriptor md) { - return md2hasAnnotation.containsKey(md); + public boolean needAnnotation(MethodDescriptor md) { + return md2needAnnotation.containsKey(md); } - public void putHasAnnotation(MethodDescriptor md) { - md2hasAnnotation.put(md, new Boolean(true)); + public void putNeedAnnotation(MethodDescriptor md) { + md2needAnnotation.put(md, new Boolean(true)); } public Hashtable getMd2hasAnnotation() { - return md2hasAnnotation; + return md2needAnnotation; } } diff --git a/Robust/src/Analysis/SSJava/SingleReferenceCheck.java b/Robust/src/Analysis/SSJava/SingleReferenceCheck.java index 5053e29e..5ef3452c 100644 --- a/Robust/src/Analysis/SSJava/SingleReferenceCheck.java +++ b/Robust/src/Analysis/SSJava/SingleReferenceCheck.java @@ -10,7 +10,6 @@ import IR.Tree.BlockExpressionNode; import IR.Tree.BlockNode; import IR.Tree.BlockStatementNode; import IR.Tree.CastNode; -import IR.Tree.CreateObjectNode; import IR.Tree.DeclarationNode; import IR.Tree.ExpressionNode; import IR.Tree.Kind; @@ -20,9 +19,11 @@ import IR.Tree.SubBlockNode; public class SingleReferenceCheck { static State state; + SSJavaAnalysis ssjava; String needToNullify = null; - public SingleReferenceCheck(State state) { + public SingleReferenceCheck(SSJavaAnalysis ssjava, State state) { + this.ssjava = ssjava; this.state = state; } @@ -32,7 +33,9 @@ public class SingleReferenceCheck { ClassDescriptor cd = (ClassDescriptor) it.next(); for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { MethodDescriptor md = (MethodDescriptor) method_it.next(); - checkMethodBody(cd, md); + if (ssjava.needAnnotation(md)) { + checkMethodBody(cd, md); + } } } } diff --git a/Robust/src/ClassLibrary/SSJava/Integer.java b/Robust/src/ClassLibrary/SSJava/Integer.java new file mode 100644 index 00000000..bfed63aa --- /dev/null +++ b/Robust/src/ClassLibrary/SSJava/Integer.java @@ -0,0 +1,117 @@ +@LATTICE("V> offset) & 0xFF); + } + return b; + } + + public int byteArrayToInt(byte[] b) { + int value = 0; + for (int i = 0; i < 4; i++) { + int shift = (4 - 1 - i) * 8; + value += (b[i] & 0x000000FF) << shift; + } + return value; + } + + public static int parseInt(String str) { + return Integer.parseInt(str, 10); + } + + public static int parseInt(String str, int radix) { + int value = 0; + boolean isNeg = false; + int start = 0; + byte[] chars = str.getBytes(); + + while (chars[start] == ' ' || chars[start] == '\t') + start++; + + if (chars[start] == '-') { + isNeg = true; + start++; + } + boolean cont = true; + for (int i = start; cont && i < str.length(); i++) { + byte b = chars[i]; + int val; + if (b >= '0' && b <= '9') + val = b - '0'; + else if (b >= 'a' && b <= 'z') + val = 10 + b - 'a'; + else if (b >= 'A' && b <= 'Z') + val = 10 + b - 'A'; + else { + cont = false; + } + if (cont) { + if (val >= radix) + System.error(); + value = value * radix + val; + } + } + if (isNeg) + value = -value; + return value; + } + + @RETURNLOC("V") + public String toString() { + return String.valueOf(value); + } + + @RETURNLOC("V") + public static String toString(int i) { + Integer I = new Integer(i); + return I.toString(); + } + + @RETURNLOC("V") + public int hashCode() { + return value; + } + + public boolean equals(Object o) { + if (o.getType() != getType()) + return false; + Integer s = (Integer) o; + if (s.intValue() != this.value) + return false; + return true; + } + + public int compareTo(Integer i) { + if (value == i.value) + return 0; + // Returns just -1 or 1 on inequality; doing math might overflow. + return value > i.value ? 1 : -1; + } +} diff --git a/Robust/src/ClassLibrary/SSJava/Object.java b/Robust/src/ClassLibrary/SSJava/Object.java index 388a20f8..4bc8ac35 100644 --- a/Robust/src/ClassLibrary/SSJava/Object.java +++ b/Robust/src/ClassLibrary/SSJava/Object.java @@ -1,7 +1,10 @@ +import String; + @LATTICE("") -@METHODDEFAULT("THIS