From 56592cc31f611aead0817dde7a891ca83d7b43ed Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 15 Mar 2011 02:05:04 +0000 Subject: [PATCH] refactoring the lattice implementation / having a way to declare the variable with delta locations(declared by using single-value annotation) / working on comparison of single,composite, and delta locations. --- .../Analysis/SSJava/CompositeLocation.java | 17 ++ Robust/src/Analysis/SSJava/FlowDownCheck.java | 169 ++++++++++++++++-- Robust/src/Analysis/SSJava/Location.java | 73 ++++++++ Robust/src/Analysis/SSJava/NTuple.java | 45 +++++ .../src/Analysis/SSJava/SSJavaAnalysis.java | 1 + Robust/src/IR/AnnotationDescriptor.java | 14 +- Robust/src/IR/Tree/BuildIR.java | 63 +++---- Robust/src/Parse/java14.cup | 2 +- Robust/src/Util/Lattice.java | 40 ++++- 9 files changed, 376 insertions(+), 48 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/CompositeLocation.java create mode 100644 Robust/src/Analysis/SSJava/Location.java create mode 100644 Robust/src/Analysis/SSJava/NTuple.java diff --git a/Robust/src/Analysis/SSJava/CompositeLocation.java b/Robust/src/Analysis/SSJava/CompositeLocation.java new file mode 100644 index 00000000..a93d1639 --- /dev/null +++ b/Robust/src/Analysis/SSJava/CompositeLocation.java @@ -0,0 +1,17 @@ +package Analysis.SSJava; + +import IR.ClassDescriptor; + +public class CompositeLocation extends Location { + + private NTuple locTuple; + + public CompositeLocation(ClassDescriptor cd) { + super(cd); + } + + public void addSingleLocation(Location loc) { + locTuple.addElement(loc); + } + +} diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index a4b0e6f7..d31bac8c 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -3,12 +3,14 @@ package Analysis.SSJava; import java.util.HashSet; import java.util.Iterator; import java.util.Set; +import java.util.StringTokenizer; import java.util.Vector; import IR.AnnotationDescriptor; import IR.ClassDescriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.Operation; import IR.State; import IR.SymbolTable; import IR.TypeDescriptor; @@ -20,6 +22,7 @@ import IR.Tree.BlockStatementNode; import IR.Tree.DeclarationNode; import IR.Tree.ExpressionNode; import IR.Tree.Kind; +import IR.Tree.OpNode; import Util.Lattice; public class FlowDownCheck { @@ -154,6 +157,10 @@ public class FlowDownCheck { case Kind.AssignmentNode: checkAssignmentNode(md, nametable, (AssignmentNode) en, td); return; + + case Kind.OpNode: + checkOpNode(md, nametable, (OpNode) en, td); + return; } /* * switch(en.kind()) { case Kind.AssignmentNode: @@ -197,18 +204,114 @@ public class FlowDownCheck { */ } + void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, TypeDescriptor td) { + + Lattice locOrder = (Lattice) state.getCd2LocationOrder().get(md.getClassDesc()); + + checkExpressionNode(md, nametable, on.getLeft(), null); + if (on.getRight() != null) + checkExpressionNode(md, nametable, on.getRight(), null); + + TypeDescriptor ltd = on.getLeft().getType(); + TypeDescriptor rtd = on.getRight() != null ? on.getRight().getType() : null; + + if (ltd.getAnnotationMarkers().size() == 0) { + // constant value + // TODO + // ltd.addAnnotationMarker(new AnnotationDescriptor(Lattice.TOP)); + } + if (rtd != null && rtd.getAnnotationMarkers().size() == 0) { + // constant value + // TODO + // rtd.addAnnotationMarker(new AnnotationDescriptor(Lattice.TOP)); + } + + System.out.println("checking op node"); + System.out.println("td=" + td); + System.out.println("ltd=" + ltd); + System.out.println("rtd=" + rtd); + + Operation op = on.getOp(); + + switch (op.getOp()) { + + case Operation.UNARYPLUS: + case Operation.UNARYMINUS: + case Operation.LOGIC_NOT: + // single operand + on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN)); + break; + + case Operation.LOGIC_OR: + case Operation.LOGIC_AND: + case Operation.COMP: + case Operation.BIT_OR: + case Operation.BIT_XOR: + case Operation.BIT_AND: + case Operation.ISAVAILABLE: + case Operation.EQUAL: + case Operation.NOTEQUAL: + case Operation.LT: + case Operation.GT: + case Operation.LTE: + case Operation.GTE: + case Operation.ADD: + case Operation.SUB: + case Operation.MULT: + case Operation.DIV: + case Operation.MOD: + case Operation.LEFTSHIFT: + case Operation.RIGHTSHIFT: + case Operation.URIGHTSHIFT: + + Set operandSet = new HashSet(); + String leftLoc = ltd.getAnnotationMarkers().get(0).getMarker(); + String rightLoc = rtd.getAnnotationMarkers().get(0).getMarker(); + + operandSet.add(leftLoc); + operandSet.add(rightLoc); + + // TODO + // String glbLoc = locOrder.getGLB(operandSet); + // on.getType().addAnnotationMarker(new AnnotationDescriptor(glbLoc)); + // System.out.println(glbLoc + "<-" + leftLoc + " " + rightLoc); + + break; + + default: + throw new Error(op.toString()); + } + + if (td != null) { + String lhsLoc = td.getAnnotationMarkers().get(0).getMarker(); + if (locOrder.isGreaterThan(lhsLoc, on.getType().getAnnotationMarkers().get(0).getMarker())) { + throw new Error("The location of LHS is higher than RHS: " + on.printNode(0)); + } + } + + } + void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, TypeDescriptor td) { + boolean postinc = true; + if (an.getOperation().getBaseOp() == null + || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation() + .getBaseOp().getOp() != Operation.POSTDEC)) + postinc = false; + if (!postinc) + checkExpressionNode(md, nametable, an.getSrc(), td); + ClassDescriptor cd = md.getClassDesc(); Lattice locOrder = (Lattice) state.getCd2LocationOrder().get(cd); + System.out.println("an=" + an.printNode(0)); String destLocation = an.getDest().getType().getAnnotationMarkers().elementAt(0).getMarker(); String srcLocation = an.getSrc().getType().getAnnotationMarkers().elementAt(0).getMarker(); if (!locOrder.isGreaterThan(srcLocation, destLocation)) { - throw new Error("Value flow from " + srcLocation + " to " + destLocation - + "does not respect location hierarchy."); + throw new Error("The value flow from " + srcLocation + " to " + destLocation + + " does not respect location hierarchy."); } } @@ -230,13 +333,35 @@ public class FlowDownCheck { throw new Error(vd.getSymbol() + " has more than one location."); } - // check if location is defined - String locationID = annotationVec.elementAt(0).getMarker(); - Lattice lattice = (Lattice) state.getCd2LocationOrder().get(cd); + AnnotationDescriptor ad = annotationVec.elementAt(0); + + if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) { - if (lattice == null || (!lattice.containsKey(locationID))) { - throw new Error("Location " + locationID - + " is not defined in the location hierarchy of class " + cd.getSymbol() + "."); + // check if location is defined + String locationID = ad.getMarker(); + Lattice lattice = (Lattice) state.getCd2LocationOrder().get(cd); + + + if (lattice == null || (!lattice.containsKey(locationID))) { + throw new Error("Location " + locationID + + " is not defined in the location hierarchy of class " + cd.getSymbol() + "."); + } + + } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) { + if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) { + + if (ad.getData().length() == 0) { + throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: " + + cd.getSymbol() + "."); + } + + StringTokenizer token = new StringTokenizer(ad.getData(), ","); + while (token.hasMoreTokens()) { + String deltaOperand = token.nextToken(); + + } + + } } } @@ -276,12 +401,30 @@ public class FlowDownCheck { } // check if location is defined - String locationID = annotationVec.elementAt(0).getMarker(); - Lattice lattice = (Lattice) state.getCd2LocationOrder().get(cd); + AnnotationDescriptor ad = annotationVec.elementAt(0); + if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) { + String locationID = annotationVec.elementAt(0).getMarker(); + Lattice lattice = (Lattice) state.getCd2LocationOrder().get(cd); + + + if (lattice == null || (!lattice.containsKey(locationID))) { + throw new Error("Location " + locationID + + " is not defined in the location hierarchy of class " + cd.getSymbol() + "."); + } + } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) { + if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) { - if (lattice == null || (!lattice.containsKey(locationID))) { - throw new Error("Location " + locationID - + " is not defined in the location hierarchy of class " + cd.getSymbol() + "."); + if (ad.getData().length() == 0) { + throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: " + + cd.getSymbol() + "."); + } + + StringTokenizer token = new StringTokenizer(ad.getData(), ","); + while (token.hasMoreTokens()) { + String deltaOperand = token.nextToken(); + // TODO: set delta operand to corresponding type descriptor + } + } } } diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java new file mode 100644 index 00000000..ca0ec5a0 --- /dev/null +++ b/Robust/src/Analysis/SSJava/Location.java @@ -0,0 +1,73 @@ +package Analysis.SSJava; + +import IR.ClassDescriptor; + +public class Location { + + public static final int TOP = 1; + public static final int NORMAL = 2; + public static final int BOTTOM = 3; + + private int type; + private ClassDescriptor cd; + private String loc; + + public Location(ClassDescriptor cd, String loc) { + this.cd = cd; + this.loc = loc; + this.type = NORMAL; + } + + public Location(ClassDescriptor cd) { + this.cd = cd; + } + + public void setType(int type) { + this.type = type; + } + + public ClassDescriptor getClassDescriptor() { + return cd; + } + + public String getLocIdentifier() { + return loc; + } + + public int getType() { + return this.type; + } + + public boolean equals(Object o) { + if (!(o instanceof Location)) { + return false; + } + + Location loc = (Location) o; + + if (loc.getClassDescriptor().equals(getClassDescriptor())) { + if (loc.getLocIdentifier() == null || getLocIdentifier() == null) { + if (loc.getType() == getType()) { + return true; + } + } else { + if (loc.getLocIdentifier().equals(getLocIdentifier())) { + return true; + } + } + } + + return false; + } + + public int hashCode() { + + int hash = cd.hashCode(); + if (loc != null) { + hash += loc.hashCode(); + } + return hash; + + } + +} diff --git a/Robust/src/Analysis/SSJava/NTuple.java b/Robust/src/Analysis/SSJava/NTuple.java new file mode 100644 index 00000000..77c81fd9 --- /dev/null +++ b/Robust/src/Analysis/SSJava/NTuple.java @@ -0,0 +1,45 @@ +package Analysis.SSJava; + +import java.util.Arrays; +import java.util.List; + +public class NTuple { + + private List elements; + + public NTuple(T ... elements) { + this.elements = Arrays.asList(elements); + } + + public String toString() { + return elements.toString(); + } + + public T at(int index) { + return elements.get(index); + } + + public int size() { + return elements.size(); + } + + public void addElement(T newElement) { + this.elements.add(newElement); + } + + public boolean equals(Object o) { + if (this == o) { + return true; + } + + if (o == null || o.getClass() != this.getClass()) { + return false; + } + return (((NTuple) o).elements).equals(elements); + } + + public int hashCode() { + return elements.hashCode(); + } + +} diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 35cd5500..68065bf8 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -6,6 +6,7 @@ import IR.State; public class SSJavaAnalysis { + public static final String DELTA = "delta"; State state; HashSet toanalyze; diff --git a/Robust/src/IR/AnnotationDescriptor.java b/Robust/src/IR/AnnotationDescriptor.java index f831378d..1f814968 100644 --- a/Robust/src/IR/AnnotationDescriptor.java +++ b/Robust/src/IR/AnnotationDescriptor.java @@ -9,7 +9,7 @@ public class AnnotationDescriptor extends Descriptor { public static final int FULL_ANNOTATION = 3; private String marker; - private Set arrayedValues; // for single annotation + private String data; // for single annotation private int type; public AnnotationDescriptor(String annotationName) { @@ -19,6 +19,14 @@ public class AnnotationDescriptor extends Descriptor { this.type = MARKER_ANNOTATION; } + public AnnotationDescriptor(String annotationName, String data) { + // constructor for marker annotation + super(annotationName); + this.marker = annotationName; + this.type = SINGLE_ANNOTATION; + this.data = data; + } + public int getType() { return type; } @@ -38,6 +46,10 @@ public class AnnotationDescriptor extends Descriptor { public String getMarker() { return marker; } + + public String getData(){ + return data; + } public boolean equals(Object o) { if (o instanceof AnnotationDescriptor) { diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java index b2e2a1ec..ef028a61 100644 --- a/Robust/src/IR/Tree/BuildIR.java +++ b/Robust/src/IR/Tree/BuildIR.java @@ -4,7 +4,6 @@ import Util.Lattice; import java.util.*; -import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction; public class BuildIR { @@ -142,12 +141,12 @@ public class BuildIR { } } - public void parseInitializers(ClassDescriptor cn){ - Vector fv=cn.getFieldVec(); +public void parseInitializers(ClassDescriptor cn){ + Vector fv=cn.getFieldVec(); int pos = 0; - for(int i=0;i locOrder=new Lattice(); - for(int i=0; i locOrder = + new Lattice("_top_","_bottom_"); + for (int i = 0; i < pnv.size(); i++) { + ParseNode loc = pnv.elementAt(i); String lowerLoc=loc.getChildren().elementAt(0).getLabel(); - String higherLoc=loc.getChildren().elementAt(1).getLabel(); + String higherLoc= loc.getChildren().elementAt(1).getLabel(); locOrder.put(higherLoc, lowerLoc); - locOrder.put(lowerLoc,null); - if(locOrder.isIntroducingCycle(higherLoc)){ - throw new Error("Error: the order relation "+lowerLoc+" < "+higherLoc+" introduces a cycle."); + if (locOrder.isIntroducingCycle(higherLoc)) { + throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc + + " introduces a cycle."); } } state.addLocationOrder(cd, locOrder); @@ -1369,21 +1369,22 @@ public class BuildIR { return m; } - private void parseAnnotationList(ParseNode pn, Modifiers m){ - ParseNodeVector pnv=pn.getChildren(); - for(int i=0; i { + private Hashtable> table; int size; - public Lattice() { + private T top; + private T bottom; + + public Lattice(T top, T bottom) { table = new Hashtable>(); + this.top = top; + this.bottom = bottom; + + table.put(top, new HashSet()); + + } + + public T getTopItem() { + return top; + } + + public T getBottomItem() { + return bottom; } public boolean put(T key, T value) { Set s; + + Set topNeighbor = table.get(top); + if (table.containsKey(key)) { s = table.get(key); } else { + // new key, need to be connected with top + topNeighbor.add(key); + s = new HashSet(); table.put(key, s); } - if (value!=null && !s.contains(value)) { + if (value != null && !s.contains(value)) { size++; s.add(value); + + if (!table.containsKey(value)) { + Set lowerNeighbor = new HashSet(); + lowerNeighbor.add(bottom); + table.put(value, lowerNeighbor); + } + + // if value is already connected with top, it is no longer to be + topNeighbor.remove(value); + + // if key is already connected with bottom,, it is no longer to be + table.get(key).remove(getBottomItem()); + return true; } else return false; -- 2.34.1