From b1b6837bb2f357b5d576029b71ffe80e5f81144c Mon Sep 17 00:00:00 2001 From: yeom Date: Thu, 17 Mar 2011 01:39:34 +0000 Subject: [PATCH] keep the current snapshot before making further changes. --- .../Analysis/SSJava/CompositeLocation.java | 98 ++++++++- Robust/src/Analysis/SSJava/DeltaLocation.java | 62 ++++++ Robust/src/Analysis/SSJava/FlowDownCheck.java | 207 +++++++++++++++++- Robust/src/Analysis/SSJava/Location.java | 10 +- Robust/src/Analysis/SSJava/NTuple.java | 7 +- Robust/src/IR/Flat/FlatNode.java | 9 + Robust/src/IR/Tree/NameNode.java | 2 +- Robust/src/IR/Tree/TreeNode.java | 10 + Robust/src/IR/TypeDescriptor.java | 1 + Robust/src/Util/Lattice.java | 4 + 10 files changed, 394 insertions(+), 16 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/DeltaLocation.java diff --git a/Robust/src/Analysis/SSJava/CompositeLocation.java b/Robust/src/Analysis/SSJava/CompositeLocation.java index a93d1639..bed509d8 100644 --- a/Robust/src/Analysis/SSJava/CompositeLocation.java +++ b/Robust/src/Analysis/SSJava/CompositeLocation.java @@ -1,17 +1,113 @@ package Analysis.SSJava; +import java.util.HashSet; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + import IR.ClassDescriptor; public class CompositeLocation extends Location { private NTuple locTuple; + private Hashtable cd2loc; + private int size; public CompositeLocation(ClassDescriptor cd) { super(cd); + locTuple = new NTuple(); + cd2loc = new Hashtable(); + size = 0; + } + + public NTuple getTuple() { + return locTuple; + } + + public int getTupleSize() { + return size; } - public void addSingleLocation(Location loc) { + public void addLocation(Location loc) { locTuple.addElement(loc); + + if (loc instanceof DeltaLocation) { + DeltaLocation deltaLoc = (DeltaLocation) loc; + for (Iterator iterator = deltaLoc.getDeltaOperandLocationVec().iterator(); iterator.hasNext();) { + Location opLoc = (Location) iterator.next(); + cd2loc.put(opLoc.getClassDescriptor(), opLoc); + size++; + } + } else { + cd2loc.put(loc.getClassDescriptor(), loc); + size += 1; + } + } + + public Map getCd2Loc() { + return cd2loc; + } + + public Location getLocation(ClassDescriptor cd) { + return cd2loc.get(cd); + } + + public Set getBaseLocationSet() { + + Set baseLocationSet = new HashSet(); + + int tupleSize = locTuple.size(); + for (int i = 0; i < tupleSize; i++) { + Location locElement = locTuple.at(i); + + if (locElement instanceof DeltaLocation) { + baseLocationSet.addAll(((DeltaLocation) locElement).getDeltaOperandLocationVec()); + } else { + baseLocationSet.add(locElement); + } + } + return baseLocationSet; + } + + public String toString() { + String rtr = "CompLoc["; + + int tupleSize = locTuple.size(); + for (int i = 0; i < tupleSize; i++) { + Location locElement = locTuple.at(i); + if (i != 0) { + rtr += ","; + } + rtr += locElement; + } + rtr += "]"; + + return rtr; + } + + public boolean equals(Object o) { + + if (!(o instanceof CompositeLocation)) { + return false; + } + + CompositeLocation compLoc = (CompositeLocation) o; + + if (compLoc.getClassDescriptor().equals(getClassDescriptor()) + && compLoc.getTuple().equals(getTuple())) { + return true; + } else { + return false; + } + + } + + public int hashCode() { + + int hashCode = getClassDescriptor().hashCode(); + return hashCode + locTuple.hashCode(); + } } diff --git a/Robust/src/Analysis/SSJava/DeltaLocation.java b/Robust/src/Analysis/SSJava/DeltaLocation.java new file mode 100644 index 00000000..8e71c86c --- /dev/null +++ b/Robust/src/Analysis/SSJava/DeltaLocation.java @@ -0,0 +1,62 @@ +package Analysis.SSJava; + +import java.util.List; +import java.util.Vector; + +import IR.ClassDescriptor; + +public class DeltaLocation extends Location { + + private Vector operandVec; + + public DeltaLocation(ClassDescriptor cd) { + super(cd); + operandVec = new Vector(); + } + + public void addDeltaOperand(Location op) { + operandVec.add(op); + } + + public List getDeltaOperandLocationVec() { + return operandVec; + } + + public boolean equals(Object o) { + + if (!(o instanceof DeltaLocation)) { + return false; + } + + DeltaLocation deltaLoc = (DeltaLocation) o; + + if (deltaLoc.getDeltaOperandLocationVec().equals(getDeltaOperandLocationVec())) { + return true; + } + return false; + } + + public int hashCode() { + int hash = cd.hashCode(); + if (loc != null) { + hash += operandVec.hashCode(); + } + return hash; + } + + public String toString() { + String rtr = "delta("; + + int tupleSize = operandVec.size(); + for (int i = 0; i < tupleSize; i++) { + Location locElement = operandVec.elementAt(i); + if (i != 0) { + rtr += ","; + } + rtr += locElement; + } + rtr += ")"; + return rtr; + } + +} diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index d31bac8c..292641ee 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -1,15 +1,19 @@ package Analysis.SSJava; import java.util.HashSet; +import java.util.Hashtable; import java.util.Iterator; +import java.util.Map; import java.util.Set; import java.util.StringTokenizer; import java.util.Vector; import IR.AnnotationDescriptor; import IR.ClassDescriptor; +import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.NameDescriptor; import IR.Operation; import IR.State; import IR.SymbolTable; @@ -21,18 +25,42 @@ import IR.Tree.BlockNode; import IR.Tree.BlockStatementNode; import IR.Tree.DeclarationNode; import IR.Tree.ExpressionNode; +import IR.Tree.FieldAccessNode; import IR.Tree.Kind; +import IR.Tree.NameNode; import IR.Tree.OpNode; import Util.Lattice; public class FlowDownCheck { - State state; + static State state; HashSet toanalyze; + Hashtable td2loc; + Hashtable id2cd; public FlowDownCheck(State state) { this.state = state; this.toanalyze = new HashSet(); + this.td2loc = new Hashtable(); + init(); + } + + public void init() { + id2cd = new Hashtable(); + Hashtable cd2lattice = state.getCd2LocationOrder(); + + Set cdSet = cd2lattice.keySet(); + for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + Lattice lattice = (Lattice) cd2lattice.get(cd); + + Set locIdSet = lattice.getKeySet(); + for (Iterator iterator2 = locIdSet.iterator(); iterator2.hasNext();) { + String locID = (String) iterator2.next(); + id2cd.put(locID, cd); + } + } + } public void flowDownCheck() { @@ -161,7 +189,17 @@ public class FlowDownCheck { case Kind.OpNode: checkOpNode(md, nametable, (OpNode) en, td); return; + + case Kind.FieldAccessNode: + checkFieldAccessNode(md, nametable, (FieldAccessNode) en, td); + return; + + case Kind.NameNode: + checkNameNode(md, nametable, (NameNode) en, td); + return; + } + /* * switch(en.kind()) { case Kind.AssignmentNode: * checkAssignmentNode(md,nametable,(AssignmentNode)en,td); return; @@ -204,6 +242,21 @@ public class FlowDownCheck { */ } + void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, TypeDescriptor td) { + + } + + void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, + TypeDescriptor td) { + + ExpressionNode left = fan.getExpression(); + checkExpressionNode(md, nametable, left, null); + TypeDescriptor ltd = left.getType(); + String fieldname = fan.getFieldName(); + + + } + void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, TypeDescriptor td) { Lattice locOrder = (Lattice) state.getCd2LocationOrder().get(md.getClassDesc()); @@ -302,18 +355,21 @@ public class FlowDownCheck { 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)) { + Location destLocation = td2loc.get(an.getDest().getType()); + Location srcLocation = td2loc.get(an.getSrc().getType()); + + + if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) { throw new Error("The value flow from " + srcLocation + " to " + destLocation - + " does not respect location hierarchy."); + + " does not respect location hierarchy on the assignment " + an.printNode(0)); } + } void checkDeclarationNode(MethodDescriptor md, DeclarationNode dn) { @@ -341,12 +397,14 @@ public class FlowDownCheck { 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() + "."); } + Location loc = new Location(cd, locationID); + td2loc.put(vd.getType(), loc); + } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) { if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) { @@ -356,11 +414,24 @@ public class FlowDownCheck { } StringTokenizer token = new StringTokenizer(ad.getData(), ","); + + CompositeLocation compLoc = new CompositeLocation(cd); + DeltaLocation deltaLoc = new DeltaLocation(cd); + while (token.hasMoreTokens()) { String deltaOperand = token.nextToken(); + ClassDescriptor deltaCD = id2cd.get(deltaOperand); + if (deltaCD == null) { + // delta operand is not defined in the location hierarchy + throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd + + "' is not defined by location hierarchies."); + } + Location loc = new Location(deltaCD, deltaOperand); + deltaLoc.addDeltaOperand(loc); } - + compLoc.addLocation(deltaLoc); + td2loc.put(vd.getType(), compLoc); } } @@ -406,7 +477,6 @@ public class FlowDownCheck { 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() + "."); @@ -419,13 +489,130 @@ public class FlowDownCheck { + cd.getSymbol() + "."); } + CompositeLocation compLoc = new CompositeLocation(cd); + DeltaLocation deltaLoc = new DeltaLocation(cd); + StringTokenizer token = new StringTokenizer(ad.getData(), ","); while (token.hasMoreTokens()) { String deltaOperand = token.nextToken(); - // TODO: set delta operand to corresponding type descriptor + ClassDescriptor deltaCD = id2cd.get(deltaOperand); + if (deltaCD == null) { + // delta operand is not defined in the location hierarchy + throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd + + "' is not defined by location hierarchies."); + } + + Location loc = new Location(deltaCD, deltaOperand); + deltaLoc.addDeltaOperand(loc); } + compLoc.addLocation(deltaLoc); + td2loc.put(fd.getType(), compLoc); + } } } + + static class CompositeLattice { + + public static boolean isGreaterThan(Location loc1, Location loc2) { + + CompositeLocation compLoc1; + CompositeLocation compLoc2; + + if (loc1 instanceof CompositeLocation) { + compLoc1 = (CompositeLocation) loc1; + } else { + // create a bogus composite location for a single location + compLoc1 = new CompositeLocation(loc1.getClassDescriptor()); + compLoc1.addLocation(loc1); + } + + if (loc2 instanceof CompositeLocation) { + compLoc2 = (CompositeLocation) loc2; + } else { + // create a bogus composite location for a single location + compLoc2 = new CompositeLocation(loc2.getClassDescriptor()); + compLoc2.addLocation(loc2); + } + + // comparing two composite locations + + System.out.println("compare base location=" + compLoc1 + " ? " + compLoc2); + + int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2); + if (baseCompareResult == ComparisonResult.EQUAL) { + // TODO + // need to compare # of delta operand + } else if (baseCompareResult == ComparisonResult.GREATER) { + return true; + } else { + return false; + } + + return false; + } + + private static int compareBaseLocationSet(CompositeLocation compLoc1, CompositeLocation compLoc2) { + + // if compLoc1 is greater than compLoc2, return true + // else return false; + + Map cd2loc1 = compLoc1.getCd2Loc(); + Map cd2loc2 = compLoc2.getCd2Loc(); + + // compare base locations by class descriptor + + Set keySet1 = cd2loc1.keySet(); + + int numEqualLoc = 0; + + for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) { + ClassDescriptor cd1 = (ClassDescriptor) iterator.next(); + + Location loc1 = cd2loc1.get(cd1); + Location loc2 = cd2loc2.get(cd1); + + if (loc2 == null) { + // if comploc2 doesn't have corresponding location, then ignore this + // element + numEqualLoc++; + continue; + } + + Lattice locationOrder = (Lattice) state.getCd2LocationOrder().get(cd1); + if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) { + // have the same level of local hierarchy + numEqualLoc++; + } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) { + // if one element of composite location 1 is not higher than composite + // location 2 + // then, composite loc 1 is not higher than composite loc 2 + + System.out.println(compLoc1 + " < " + compLoc2); + return ComparisonResult.LESS; + } + + } + + if (numEqualLoc == compLoc1.getTupleSize()) { + System.out.println(compLoc1 + " == " + compLoc2); + return ComparisonResult.EQUAL; + } + + System.out.println(compLoc1 + " > " + compLoc2); + return ComparisonResult.GREATER; + } + + } + + class ComparisonResult { + + public static final int GREATER = 0; + public static final int EQUAL = 1; + public static final int LESS = 2; + int result; + + } + } diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java index ca0ec5a0..11c3f086 100644 --- a/Robust/src/Analysis/SSJava/Location.java +++ b/Robust/src/Analysis/SSJava/Location.java @@ -8,9 +8,9 @@ public class Location { public static final int NORMAL = 2; public static final int BOTTOM = 3; - private int type; - private ClassDescriptor cd; - private String loc; + int type; + ClassDescriptor cd; + String loc; public Location(ClassDescriptor cd, String loc) { this.cd = cd; @@ -70,4 +70,8 @@ public class Location { } + public String toString() { + return "Loc[" + cd.getSymbol() + "." + loc + "]"; + } + } diff --git a/Robust/src/Analysis/SSJava/NTuple.java b/Robust/src/Analysis/SSJava/NTuple.java index 77c81fd9..8b026633 100644 --- a/Robust/src/Analysis/SSJava/NTuple.java +++ b/Robust/src/Analysis/SSJava/NTuple.java @@ -1,5 +1,6 @@ package Analysis.SSJava; +import java.util.ArrayList; import java.util.Arrays; import java.util.List; @@ -7,10 +8,14 @@ public class NTuple { private List elements; - public NTuple(T ... elements) { + public NTuple(T... elements) { this.elements = Arrays.asList(elements); } + public NTuple() { + this.elements = new ArrayList(); + } + public String toString() { return elements.toString(); } diff --git a/Robust/src/IR/Flat/FlatNode.java b/Robust/src/IR/Flat/FlatNode.java index 3af3893a..26056234 100644 --- a/Robust/src/IR/Flat/FlatNode.java +++ b/Robust/src/IR/Flat/FlatNode.java @@ -9,6 +9,7 @@ public class FlatNode { protected Vector prev; static int idcounter=0; public final int nodeid; + public int lineNum; public FlatNode() { next=new Vector(); @@ -135,4 +136,12 @@ public class FlatNode { next=null; prev=null; } + + public void setLineNum(int lineNum){ + this.lineNum=lineNum; + } + + public int getLineNume(){ + return this.lineNum; + } } diff --git a/Robust/src/IR/Tree/NameNode.java b/Robust/src/IR/Tree/NameNode.java index 40487d0c..b087e3c6 100644 --- a/Robust/src/IR/Tree/NameNode.java +++ b/Robust/src/IR/Tree/NameNode.java @@ -90,7 +90,7 @@ public class NameNode extends ExpressionNode { return null; } - NameDescriptor getName() { + public NameDescriptor getName() { return name; } diff --git a/Robust/src/IR/Tree/TreeNode.java b/Robust/src/IR/Tree/TreeNode.java index 578cc6c6..25b16795 100644 --- a/Robust/src/IR/Tree/TreeNode.java +++ b/Robust/src/IR/Tree/TreeNode.java @@ -2,6 +2,7 @@ package IR.Tree; public class TreeNode { public static final int INDENT=2; + int numLine; public String printNode(int indent) { return null; @@ -15,4 +16,13 @@ public class TreeNode { public int kind() { throw new Error(); } + + public void setNumLine(int numLine){ + this.numLine=numLine; + } + + public int getNumLine(){ + return this.numLine; + } + } diff --git a/Robust/src/IR/TypeDescriptor.java b/Robust/src/IR/TypeDescriptor.java index fdd46fd6..39186acf 100644 --- a/Robust/src/IR/TypeDescriptor.java +++ b/Robust/src/IR/TypeDescriptor.java @@ -69,6 +69,7 @@ public class TypeDescriptor extends Descriptor { public int hashCode() { int hashcode=type^arraycount; + hashcode+=annotationSet.hashCode(); if (type==CLASS) hashcode^=getSymbol().hashCode(); return hashcode; diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index feb71d79..0d701f0b 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -29,6 +29,10 @@ public class Lattice { public T getBottomItem() { return bottom; } + + public Set getKeySet(){ + return table.keySet(); + } public boolean put(T key, T value) { Set s; -- 2.34.1