a bunch of fixes.

diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java
index fb051631db47bd80b07f5f845d38adf2d444bebd..ce0021cadcfa6c7ea3f79e5b9583cc604b8cedff 100644 (file)
--- a/Robust/src/Analysis/SSJava/FlowGraph.java
+++ b/Robust/src/Analysis/SSJava/FlowGraph.java
@@ -23,6 +23,7 @@ public class FlowGraph {
   MethodDescriptor md;
 
   Set<FlowNode> nodeSet;
   MethodDescriptor md;
 
   Set<FlowNode> nodeSet;

+  Set<FlowNode> returnNodeSet;

   FlowNode thisVarNode;
 
   // maps the composite representation of field/var descriptors to infer nodes
   FlowNode thisVarNode;
 
   // maps the composite representation of field/var descriptors to infer nodes


@@ -37,11 +38,12 @@ public class FlowGraph {
 
   public FlowGraph(MethodDescriptor md, Map<Descriptor, Integer> mapParamDescToIdx) {
     this.md = md;
 
   public FlowGraph(MethodDescriptor md, Map<Descriptor, Integer> mapParamDescToIdx) {
     this.md = md;

-    nodeSet = new HashSet<FlowNode>();
-    mapDescTupleToInferNode = new HashMap<NTuple<Descriptor>, FlowNode>();
-    mapNodeToNeighborSet = new HashMap<NTuple<Descriptor>, Set<FlowNode>>();
+    this.nodeSet = new HashSet<FlowNode>();
+    this.mapDescTupleToInferNode = new HashMap<NTuple<Descriptor>, FlowNode>();
+    this.mapNodeToNeighborSet = new HashMap<NTuple<Descriptor>, Set<FlowNode>>();

     this.mapParamDescToIdx = new HashMap<Descriptor, Integer>();
     this.mapParamDescToIdx.putAll(mapParamDescToIdx);
     this.mapParamDescToIdx = new HashMap<Descriptor, Integer>();
     this.mapParamDescToIdx.putAll(mapParamDescToIdx);

+    this.returnNodeSet = new HashSet<FlowNode>();

 
     // create a node for 'this' varialbe
     NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();
 
     // create a node for 'this' varialbe
     NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();


@@ -168,6 +170,22 @@ public class FlowGraph {
 
   }
 
 
   }
 

+  public void setReturnFlowNode(NTuple<Descriptor> tuple) {
+
+    if (!mapDescTupleToInferNode.containsKey(tuple)) {
+      createNewFlowNode(tuple);
+    }
+
+    FlowNode node = mapDescTupleToInferNode.get(tuple);
+    node.setReturn(true);
+
+    returnNodeSet.add(node);
+  }
+
+  public Set<FlowNode> getReturnNodeSet() {
+    return returnNodeSet;
+  }
+

   public boolean isParamter(NTuple<Descriptor> tuple) {
     // return true if a descriptor tuple is started with a parameter descriptor
     Descriptor firstIdxDesc = tuple.get(0);
   public boolean isParamter(NTuple<Descriptor> tuple) {
     // return true if a descriptor tuple is started with a parameter descriptor
     Descriptor firstIdxDesc = tuple.get(0);


@@ -220,7 +238,7 @@ public class FlowGraph {
 
   public void writeGraph() throws java.io.IOException {
 
 
   public void writeGraph() throws java.io.IOException {
 

-    String graphName = md.toString();
+    String graphName = "flowgraph_" + md.toString();

     graphName = graphName.replaceAll("[\\W]", "");
 
     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
     graphName = graphName.replaceAll("[\\W]", "");
 
     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));

diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java
index 21a2e089be9da54397dd6729c0b5fec0431d513c..eb9c2a7e9a7a5fa581183e50e8a2fcd643812eca 100644 (file)
--- a/Robust/src/Analysis/SSJava/FlowNode.java
+++ b/Robust/src/Analysis/SSJava/FlowNode.java
@@ -18,6 +18,9 @@ public class FlowNode {
   // set true if this node is driven from a paramter
   private boolean isParameter;
 
   // set true if this node is driven from a paramter
   private boolean isParameter;
 

+  // set true if this node stores a return value
+  private boolean isReturn;
+

   public Set<FlowNode> getFieldNodeSet() {
     return fieldNodeSet;
   }
   public Set<FlowNode> getFieldNodeSet() {
     return fieldNodeSet;
   }


@@ -63,6 +66,14 @@ public class FlowNode {
     return descTuple.get(descTuple.size() - 1);
   }
 
     return descTuple.get(descTuple.size() - 1);
   }
 

+  public boolean isReturn() {
+    return isReturn;
+  }
+
+  public void setReturn(boolean isReturn) {
+    this.isReturn = isReturn;
+  }
+

   public String toString() {
     String rtr = "[FlowNode]:";
     if (isParameter()) {
   public String toString() {
     String rtr = "[FlowNode]:";
     if (isParameter()) {

diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java
index 271b447f9e769f2ed79dd1c2e7013ae43ac40dcd..fbab568eb355b668ea24dfdd6f2f3273d691d810 100644 (file)
--- a/Robust/src/Analysis/SSJava/Location.java
+++ b/Robust/src/Analysis/SSJava/Location.java
@@ -23,9 +23,9 @@ public class Location implements TypeExtension {
     this.d = d;
     this.type = type;
     if (type == TOP) {
     this.d = d;
     this.type = type;
     if (type == TOP) {

-      loc = SSJavaLattice.TOP;
+      loc = SSJavaAnalysis.TOP;

     } else if (type == BOTTOM) {
     } else if (type == BOTTOM) {

-      loc = SSJavaLattice.BOTTOM;
+      loc = SSJavaAnalysis.BOTTOM;

     }
   }
 
     }
   }
 

diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java
index daa435f0e7f80b3df722698c69bc55d4ce44a7cb..089e7f8bd7f887d07989135c48ce35a08eda8515 100644 (file)
--- a/Robust/src/Analysis/SSJava/LocationInference.java
+++ b/Robust/src/Analysis/SSJava/LocationInference.java
@@ -25,7 +25,6 @@ import IR.State;
 import IR.SymbolTable;
 import IR.TypeDescriptor;
 import IR.VarDescriptor;
 import IR.SymbolTable;
 import IR.TypeDescriptor;
 import IR.VarDescriptor;

-import IR.Flat.FlatMethod;

 import IR.Tree.ArrayAccessNode;
 import IR.Tree.AssignmentNode;
 import IR.Tree.BlockExpressionNode;
 import IR.Tree.ArrayAccessNode;
 import IR.Tree.AssignmentNode;
 import IR.Tree.BlockExpressionNode;


@@ -69,22 +68,16 @@ public class LocationInference {
   // map a method descriptor to a method lattice
   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
 
   // map a method descriptor to a method lattice
   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
 

-  // map a method descriptor to a lattice mapping
-  private Map<MethodDescriptor, Map<VarDescriptor, String>> md2LatticeMapping;
-
-  // map a method descriptor to a lattice mapping
-  private Map<MethodDescriptor, Map<FieldDescriptor, String>> cd2LatticeMapping;
-
-  // map a method descriptor to the set of hierarchy relations that are
-  // contributed from the callee
-  private Map<MethodDescriptor, Set<ParamIndexRelation>> mapMethodDescriptorToCalleeParamRelationSet;
-

   // map a method descriptor to the set of method invocation nodes which are
   // invoked by the method descriptor
   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
 
   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
 
   // map a method descriptor to the set of method invocation nodes which are
   // invoked by the method descriptor
   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
 
   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
 

+  private Map<MethodDescriptor, MethodLocationInfo> mapLatticeToMethodLocationInfo;
+
+  private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodDescToPossibleMethodDescSet;
+

   boolean debug = true;
 
   public LocationInference(SSJavaAnalysis ssjava, State state) {
   boolean debug = true;
 
   public LocationInference(SSJavaAnalysis ssjava, State state) {


@@ -96,15 +89,13 @@ public class LocationInference {
     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();

-    this.md2LatticeMapping = new HashMap<MethodDescriptor, Map<VarDescriptor, String>>();
-    this.cd2LatticeMapping = new HashMap<MethodDescriptor, Map<FieldDescriptor, String>>();
-    this.mapMethodDescriptorToCalleeParamRelationSet =
-        new HashMap<MethodDescriptor, Set<ParamIndexRelation>>();

     this.mapMethodDescriptorToMethodInvokeNodeSet =
         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
     this.mapMethodInvokeNodeToArgIdxMap =
         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
     this.mapMethodDescriptorToMethodInvokeNodeSet =
         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
     this.mapMethodInvokeNodeToArgIdxMap =
         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();

-
+    this.mapLatticeToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
+    this.mapMethodDescToPossibleMethodDescSet =
+        new HashMap<MethodDescriptor, Set<MethodDescriptor>>();

   }
 
   public void setupToAnalyze() {
   }
 
   public void setupToAnalyze() {


@@ -156,6 +147,30 @@ public class LocationInference {
 
     debug_writeLatticeDotFile();
 
 
     debug_writeLatticeDotFile();
 

+    // 3) check properties
+    checkLattices();
+
+  }
+
+  private void checkLattices() {
+
+    LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
+
+    // current descriptors to visit in fixed-point interprocedural analysis,
+    // prioritized by
+    // dependency in the call graph
+    methodDescriptorsToVisitStack.clear();
+
+    descriptorListToAnalyze.removeFirst();
+
+    Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
+    methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
+
+    while (!descriptorListToAnalyze.isEmpty()) {
+      MethodDescriptor md = descriptorListToAnalyze.removeFirst();
+      checkLatticesOfVirtualMethods(md);
+    }
+

   }
 
   private void debug_writeLatticeDotFile() {
   }
 
   private void debug_writeLatticeDotFile() {


@@ -190,7 +205,6 @@ public class LocationInference {
 
     // do fixed-point analysis
 
 
     // do fixed-point analysis
 

-    // perform method READ/OVERWRITE analysis

     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 
     // current descriptors to visit in fixed-point interprocedural analysis,
     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 
     // current descriptors to visit in fixed-point interprocedural analysis,


@@ -214,7 +228,7 @@ public class LocationInference {
       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 
       SSJavaLattice<String> methodLattice =
       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 
       SSJavaLattice<String> methodLattice =

-          new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
+          new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);

 
       System.out.println();
       System.out.println("SSJAVA: Inferencing the lattice from " + md);
 
       System.out.println();
       System.out.println("SSJAVA: Inferencing the lattice from " + md);


@@ -224,7 +238,8 @@ public class LocationInference {
       SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 
       if (!methodLattice.equals(prevMethodLattice)) {
       SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 
       if (!methodLattice.equals(prevMethodLattice)) {

-        md2lattice.put(md, methodLattice);
+
+        setMethodLattice(md, methodLattice);

 
         // results for callee changed, so enqueue dependents caller for
         // further analysis
 
         // results for callee changed, so enqueue dependents caller for
         // further analysis


@@ -243,6 +258,61 @@ public class LocationInference {
 
   }
 
 
   }
 

+  private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
+
+    if (!md.isStatic()) {
+      Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
+      setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
+
+      for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
+        MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
+        if (!md.equals(mdCallee)) {
+          checkConsistency(md, mdCallee);
+        }
+      }
+
+    }
+
+  }
+
+  private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
+
+    // check that two lattice have the same relations between parameters(+PC
+    // LOC, RETURN LOC)
+
+    MethodLocationInfo methodInfo1 = getMethodLocationInfo(md1);
+
+    SSJavaLattice<String> lattice1 = getMethodLattice(md1);
+    SSJavaLattice<String> lattice2 = getMethodLattice(md2);
+
+    Set<String> paramLocNameSet1 = methodInfo1.getParameterLocNameSet();
+
+    for (Iterator iterator = paramLocNameSet1.iterator(); iterator.hasNext();) {
+      String locName1 = (String) iterator.next();
+      for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) {
+        String locName2 = (String) iterator2.next();
+
+        // System.out.println("COMPARE " + locName1 + " - " + locName2 + " "
+        // + lattice1.isGreaterThan(locName1, locName2) + "-"
+        // + lattice2.isGreaterThan(locName1, locName2));
+
+        if (!locName1.equals(locName2)) {
+
+          boolean r1 = lattice1.isGreaterThan(locName1, locName2);
+          boolean r2 = lattice2.isGreaterThan(locName1, locName2);
+
+          if (r1 != r2) {
+            throw new Error("The method " + md1 + " is not consistent with the method " + md2
+                + ".:: They have a different ordering relation between parameters " + locName1
+                + " and " + locName2 + ".");
+          }
+        }
+
+      }
+    }
+
+  }
+

   private String getSymbol(int idx, FlowNode node) {
     Descriptor desc = node.getDescTuple().get(idx);
     return desc.getSymbol();
   private String getSymbol(int idx, FlowNode node) {
     Descriptor desc = node.getDescTuple().get(idx);
     return desc.getSymbol();


@@ -250,12 +320,13 @@ public class LocationInference {
 
   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 
 
   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 

+    MethodLocationInfo methodInfo = getMethodLocationInfo(md);
+

     // first take a look at method invocation nodes to newly added relations
     // from the callee
     analyzeLatticeMethodInvocationNode(md);
 
     // visit each node of method flow graph
     // first take a look at method invocation nodes to newly added relations
     // from the callee
     analyzeLatticeMethodInvocationNode(md);
 
     // visit each node of method flow graph

-

     FlowGraph fg = getFlowGraph(md);
     Set<FlowNode> nodeSet = fg.getNodeSet();
 
     FlowGraph fg = getFlowGraph(md);
     Set<FlowNode> nodeSet = fg.getNodeSet();
 


@@ -264,18 +335,65 @@ public class LocationInference {
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       FlowNode srcNode = (FlowNode) iterator.next();
 
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       FlowNode srcNode = (FlowNode) iterator.next();
 

-      // first, take a look at directly connected nodes

       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
         FlowEdge outEdge = (FlowEdge) iterator2.next();
         FlowNode dstNode = outEdge.getDst();
 
       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
         FlowEdge outEdge = (FlowEdge) iterator2.next();
         FlowNode dstNode = outEdge.getDst();
 

-        addRelationToLattice(md, methodLattice, srcNode, dstNode);
+        NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
+        NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
+
+        if (outEdge.getInitTuple().equals(srcNodeTuple)
+            && outEdge.getEndTuple().equals(dstNodeTuple)) {
+
+          if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
+              && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
+
+            // value flows between fields
+            VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
+            ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+            extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
+
+          } else {
+            // in this case, take a look at connected nodes at the local level
+            addRelationToLattice(md, methodLattice, srcNode, dstNode);
+          }
+
+        }

 
       }
 
     }
 
 
       }
 
     }
 

+    // grab the this location if the method use the 'this' reference
+    String thisLocSymbol = md.getThis().getSymbol();
+    if (methodLattice.getKeySet().contains(thisLocSymbol)) {
+      methodInfo.setThisLocName(thisLocSymbol);
+    }
+
+    // calculate a return location
+    if (!md.getReturnType().isVoid()) {
+      Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
+      Set<String> returnVarSymbolSet = new HashSet<String>();
+
+      for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
+        FlowNode rtrNode = (FlowNode) iterator.next();
+        String localSymbol = rtrNode.getDescTuple().get(0).getSymbol();
+        returnVarSymbolSet.add(localSymbol);
+      }
+
+      String returnGLB = methodLattice.getGLB(returnVarSymbolSet);
+      if (returnGLB.equals(SSJavaAnalysis.BOTTOM)) {
+        // need to insert a new location in-between the bottom and all locations
+        // that is directly connected to the bottom
+        String returnNewLocationSymbol = "Loc" + (SSJavaLattice.seed++);
+        methodLattice.insertNewLocationAtOneLevelHigher(returnGLB, returnNewLocationSymbol);
+        methodInfo.setReturnLocName(returnNewLocationSymbol);
+      } else {
+        methodInfo.setReturnLocName(returnGLB);
+      }
+    }
+

   }
 
   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) {
   }
 
   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) {


@@ -327,9 +445,10 @@ public class LocationInference {
 
         String paramSymbol1 = getSymbol(0, paramFlowNode1);
         String paramSymbol2 = getSymbol(0, paramFlowNode2);
 
         String paramSymbol1 = getSymbol(0, paramFlowNode1);
         String paramSymbol2 = getSymbol(0, paramFlowNode2);

-        // if two parameters have relation, we need to propagate this relation
+        // if two parameters have a relation, we need to propagate this relation

         // to the caller
         // to the caller

-        if (calleeLattice.isComparable(paramSymbol1, paramSymbol2)) {
+        if (!(paramSymbol1.equals(paramSymbol2))
+            && calleeLattice.isComparable(paramSymbol1, paramSymbol2)) {

           int higherLocIdxCallee;
           int lowerLocIdxCallee;
           if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) {
           int higherLocIdxCallee;
           int lowerLocIdxCallee;
           if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) {


@@ -353,55 +472,86 @@ public class LocationInference {
 
   }
 
 
   }
 

-  private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
-      FlowNode srcNode, FlowNode dstNode) {
-    if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1)
-        && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) {
-      // value flow between fields: we don't need to add a binary relation
-      // for this case
-
-      VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0);
-      ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+  private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {

 
 

-      extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
-      return;
+    if (!mapLatticeToMethodLocationInfo.containsKey(md)) {
+      mapLatticeToMethodLocationInfo.put(md, new MethodLocationInfo(md));

     }
 
     }
 

-    // add a new binary relation of dstNode < srcNode
+    return mapLatticeToMethodLocationInfo.get(md);
+
+  }

 
 

+  private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
+      FlowNode srcNode, FlowNode dstNode) {
+
+    // add a new binary relation of dstNode < srcNode

     String srcSymbol = getSymbol(0, srcNode);
     String dstSymbol = getSymbol(0, dstNode);
 
     String srcSymbol = getSymbol(0, srcNode);
     String dstSymbol = getSymbol(0, dstNode);
 

-    methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
+    FlowGraph flowGraph = getFlowGraph(md);
+    MethodLocationInfo methodInfo = getMethodLocationInfo(md);
+
+    if (srcNode.isParameter()) {
+      int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple());
+      methodInfo.addParameter(srcSymbol, srcNode, paramIdx);
+    }
+    if (dstNode.isParameter()) {
+      int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple());
+      methodInfo.addParameter(dstSymbol, dstNode, paramIdx);
+    }
+
+    if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) {
+      // if the lattice does not have this relation, add it
+      methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
+    }

 
   }
 
   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
 
   }
 
   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {

-

     if (!md2lattice.containsKey(md)) {
     if (!md2lattice.containsKey(md)) {

-      md2lattice.put(md, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
+      md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));

     }
     return md2lattice.get(md);
   }
 
     }
     return md2lattice.get(md);
   }
 

+  private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
+    md2lattice.put(md, lattice);
+  }
+

   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
       FlowNode dstNode, int idx) {
 
   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
       FlowNode dstNode, int idx) {
 

-    if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))) {
+    if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
+        && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {

       // value flow between fields: we don't need to add a binary relation
       // for this case
       // value flow between fields: we don't need to add a binary relation
       // for this case

-      VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(idx);
-      ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
-      extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, idx + 1);
+
+      Descriptor desc = srcNode.getDescTuple().get(idx);
+      ClassDescriptor classDesc;
+
+      if (idx == 0) {
+        classDesc = ((VarDescriptor) desc).getType().getClassDesc();
+      } else {
+        classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
+      }
+
+      extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
+

     } else {
 
       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
 
       // add a new binary relation of dstNode < srcNode
     } else {
 
       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
 
       // add a new binary relation of dstNode < srcNode

-

       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);

-      fieldLattice.addRelationHigherToLower(srcFieldDesc.getSymbol(), dstFieldDesc.getSymbol());
+
+      String srcSymbol = srcFieldDesc.getSymbol();
+      String dstSymbol = dstFieldDesc.getSymbol();
+
+      if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) {
+        fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
+      }

 
     }
 
 
     }
 


@@ -409,7 +559,7 @@ public class LocationInference {
 
   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
     if (!cd2lattice.containsKey(cd)) {
 
   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
     if (!cd2lattice.containsKey(cd)) {

-      cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
+      cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));

     }
     return cd2lattice.get(cd);
   }
     }
     return cd2lattice.get(cd);
   }


@@ -426,11 +576,20 @@ public class LocationInference {
         MethodDescriptor md = toAnalyzeMethodNext();
         if (ssjava.needTobeAnnotated(md)) {
           if (state.SSJAVADEBUG) {
         MethodDescriptor md = toAnalyzeMethodNext();
         if (ssjava.needTobeAnnotated(md)) {
           if (state.SSJAVADEBUG) {

+            System.out.println();

             System.out.println("SSJAVA: Constructing a flow graph: " + md);
           }
 
             System.out.println("SSJAVA: Constructing a flow graph: " + md);
           }
 

-          // creates a mapping from a parameter descriptor to its index
+          // creates a mapping from a method descriptor to virtual methods
+          Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
+          if (md.isStatic()) {
+            setPossibleCallees.add(md);
+          } else {
+            setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
+          }
+          mapMethodDescToPossibleMethodDescSet.put(md, setPossibleCallees);

 
 

+          // creates a mapping from a parameter descriptor to its index

           Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
           int offset = md.isStatic() ? 0 : 1;
           for (int i = 0; i < md.numParameters(); i++) {
           Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
           int offset = md.isStatic() ? 0 : 1;
           for (int i = 0; i < md.numParameters(); i++) {


@@ -487,7 +646,7 @@ public class LocationInference {
       break;
 
     case Kind.ReturnNode:
       break;
 
     case Kind.ReturnNode:

-      analyzeReturnNode(md, nametable, (ReturnNode) bsn);
+      analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);

       break;
 
     case Kind.SubBlockNode:
       break;
 
     case Kind.SubBlockNode:


@@ -515,8 +674,25 @@ public class LocationInference {
     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
   }
 
     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
   }
 

-  private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
-    // TODO Auto-generated method stub
+  private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
+      NodeTupleSet implicitFlowTupleSet) {
+
+    ExpressionNode returnExp = rn.getReturnExpression();
+
+    NodeTupleSet nodeSet = new NodeTupleSet();
+    analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
+
+    FlowGraph fg = getFlowGraph(md);
+
+    // annotate the elements of the node set as the return location
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
+      fg.setReturnFlowNode(returnDescTuple);
+      for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
+        NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
+        fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
+      }
+    }

 
   }
 
 
   }
 


@@ -609,7 +785,7 @@ public class LocationInference {
 
     // note that expression node can create more than one flow node
     // nodeSet contains of flow nodes
 
     // note that expression node can create more than one flow node
     // nodeSet contains of flow nodes

-    // base is always assigned to null except name node case!
+    // base is always assigned to null except the case of a name node!

 
     NTuple<Descriptor> flowTuple;
 
 
     NTuple<Descriptor> flowTuple;
 


@@ -694,15 +870,12 @@ public class LocationInference {
   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 
   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 

-    System.out.println("### analyzeFlowTertiaryNode=" + tn.printNode(0));
-

     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
         implicitFlowTupleSet, false);
 
     // add edges from tertiaryTupleNode to all nodes of conditional nodes
     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
         implicitFlowTupleSet, false);
 
     // add edges from tertiaryTupleNode to all nodes of conditional nodes
     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);

-    System.out.println("### TertiarayNode's condition=" + tertiaryTupleNode);

     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
         implicitFlowTupleSet, false);
 
     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
         implicitFlowTupleSet, false);
 


@@ -743,7 +916,6 @@ public class LocationInference {
       if (min.getExpression() != null) {
 
         NodeTupleSet baseNodeSet = new NodeTupleSet();
       if (min.getExpression() != null) {
 
         NodeTupleSet baseNodeSet = new NodeTupleSet();

-        System.out.println("Analyzing base of method=" + min.getExpression());

         analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null,
             implicitFlowTupleSet, false);
 
         analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null,
             implicitFlowTupleSet, false);
 


@@ -880,17 +1052,13 @@ public class LocationInference {
     NodeTupleSet rightOpSet = new NodeTupleSet();
 
     // left operand
     NodeTupleSet rightOpSet = new NodeTupleSet();
 
     // left operand

-    System.out.println("Analyzing left op=" + on.getLeft().printNode(0) + "::"
-        + on.getLeft().getClass());

     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
         false);
     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
         false);

-    System.out.println("leftOpSet=" + leftOpSet);

 
     if (on.getRight() != null) {
       // right operand
       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
           implicitFlowTupleSet, false);
 
     if (on.getRight() != null) {
       // right operand
       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
           implicitFlowTupleSet, false);

-      System.out.println("rightOpSet=" + rightOpSet);

     }
 
     Operation op = on.getOp();
     }
 
     Operation op = on.getOp();


@@ -1058,6 +1226,7 @@ public class LocationInference {
       base.add(fd);
     }
 
       base.add(fd);
     }
 

+    getFlowGraph(md).createNewFlowNode(base);

     return base;
 
   }
     return base;
 
   }


@@ -1065,8 +1234,6 @@ public class LocationInference {
   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
       AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 
   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
       AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 

-    System.out.println("analyzeFlowAssignmentNode=" + an);
-

     NodeTupleSet nodeSetRHS = new NodeTupleSet();
     NodeTupleSet nodeSetLHS = new NodeTupleSet();
 
     NodeTupleSet nodeSetRHS = new NodeTupleSet();
     NodeTupleSet nodeSetLHS = new NodeTupleSet();
 


@@ -1081,13 +1248,11 @@ public class LocationInference {
     // and its index value
     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
         true);
     // and its index value
     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
         true);

-    System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);

 
     if (!postinc) {
       // analyze value flows of rhs expression
       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
           false);
 
     if (!postinc) {
       // analyze value flows of rhs expression
       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
           false);

-      System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);

 
       // creates edges from RHS to LHS
       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
 
       // creates edges from RHS to LHS
       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {


@@ -1122,7 +1287,7 @@ public class LocationInference {
     return mapMethodDescriptorToFlowGraph.get(md);
   }
 
     return mapMethodDescriptorToFlowGraph.get(md);
   }
 

-  public boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
+  private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,

       NTuple<Descriptor> to) {
     // TODO
     // return true if it adds a new edge
       NTuple<Descriptor> to) {
     // TODO
     // return true if it adds a new edge


@@ -1147,8 +1312,3 @@ public class LocationInference {
   }
 
 }
   }
 
 }

-
-class ParamIndexRelation {
-  private Integer higherIdx;
-  private Integer lowerIdx;
-}

diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java
new file mode 100644 (file)
index 0000000..ad78508
--- /dev/null
+++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java
@@ -0,0 +1,73 @@
+package Analysis.SSJava;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import IR.MethodDescriptor;
+
+public class MethodLocationInfo {
+
+  String returnLocName;
+  String thisLocName;
+  String PCLocName;
+  Map<Integer, String> mapParamIdxToLocName;
+  Map<String, FlowNode> mapLocNameToFlowNode;
+  MethodDescriptor md;
+
+  public MethodLocationInfo(MethodDescriptor md) {
+    this.md = md;
+    this.mapParamIdxToLocName = new HashMap<Integer, String>();
+    this.mapLocNameToFlowNode = new HashMap<String, FlowNode>();
+    this.PCLocName = SSJavaAnalysis.TOP;
+  }
+
+  public String getReturnLocName() {
+    return returnLocName;
+  }
+
+  public void setReturnLocName(String returnLocName) {
+    this.returnLocName = returnLocName;
+  }
+
+  public String getThisLocName() {
+    return thisLocName;
+  }
+
+  public void setThisLocName(String thisLocName) {
+    this.thisLocName = thisLocName;
+  }
+
+  public String getPCLocName() {
+    return PCLocName;
+  }
+
+  public void setPCLocName(String pCLocName) {
+    PCLocName = pCLocName;
+  }
+
+  public void addParameter(String name, FlowNode node, int idx) {
+    mapParamIdxToLocName.put(new Integer(idx), name);
+    mapLocNameToFlowNode.put(name, node);
+  }
+
+  public Set<String> getParameterLocNameSet() {
+    Set<String> paramSet = new HashSet<String>();
+
+    paramSet.add(PCLocName);
+
+    if (thisLocName != null) {
+      paramSet.add(thisLocName);
+    }
+
+    if (returnLocName != null) {
+      paramSet.add(returnLocName);
+    }
+
+    paramSet.addAll(mapLocNameToFlowNode.keySet());
+
+    return paramSet;
+  }
+
+}

diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java
index 6850960485f676def5fdab549dd21111e98d8c01..3040a15ae80d8a2b5389020abcab6cb39fb062da 100644 (file)
--- a/Robust/src/Analysis/SSJava/NodeTupleSet.java
+++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java
@@ -1,51 +1,53 @@
 package Analysis.SSJava;
 
 package Analysis.SSJava;
 

+import java.util.ArrayList;

 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.HashSet;
 import java.util.Iterator;

+import java.util.List;

 import java.util.Set;
 
 import IR.Descriptor;
 
 public class NodeTupleSet {
 
 import java.util.Set;
 
 import IR.Descriptor;
 
 public class NodeTupleSet {
 

-  private Set<NTuple<Descriptor>> set;
+  private List<NTuple<Descriptor>> list;

 
   public NodeTupleSet() {
 
   public NodeTupleSet() {

-    set = new HashSet<NTuple<Descriptor>>();
+    list = new ArrayList<NTuple<Descriptor>>();

   }
 
   public void addTuple(NTuple<Descriptor> tuple) {
 
   }
 
   public void addTuple(NTuple<Descriptor> tuple) {
 

-    // need to add additional elements because we need to create edges even from
-    // the base
-    // for example, if we have input <a,b,c>, we need to add additional element
-    // <a,b> and <a> to the set
-
-    // NTuple<Descriptor> cur = new NTuple<Descriptor>();
-    // for (int i = 0; i < tuple.size(); i++) {
-    // Descriptor d = tuple.get(i);
-    // cur.add(d);
-    // set.add(new NTuple<Descriptor>(cur));
-    // }
+    for (Iterator iterator = list.iterator(); iterator.hasNext();) {
+      NTuple<Descriptor> t = (NTuple<Descriptor>) iterator.next();
+      if (t.equals(tuple)) {
+        return;
+      }
+    }

 
 

-    set.add(tuple);
+    list.add(tuple);

   }
 
   public Iterator<NTuple<Descriptor>> iterator() {
   }
 
   public Iterator<NTuple<Descriptor>> iterator() {

-    return set.iterator();
+    return list.iterator();

   }
 
   public String toString() {
   }
 
   public String toString() {

-    return set.toString();
+    return list.toString();

   }
 
   public Set<NTuple<Descriptor>> getSet() {
   }
 
   public Set<NTuple<Descriptor>> getSet() {

+    Set<NTuple<Descriptor>> set = new HashSet<NTuple<Descriptor>>();
+    set.addAll(list);

     return set;
   }
 
   public void addTupleSet(NodeTupleSet in) {
     if (in != null) {
     return set;
   }
 
   public void addTupleSet(NodeTupleSet in) {
     if (in != null) {

-      set.addAll(in.getSet());
+      for (Iterator iterator = in.iterator(); iterator.hasNext();) {
+        NTuple<Descriptor> inTuple = (NTuple<Descriptor>) iterator.next();
+        addTuple(inTuple);
+      }

     }
   }
 }
     }
   }
 }

diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
index b72f077a82cb5f17030ab78073040c3a14d23097..c0fa9b3f5bceaef18dbc2420c86e180ac5d497cb 100644 (file)
--- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
+++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
@@ -48,6 +48,9 @@ public class SSJavaAnalysis {
   public static final String DELEGATETHIS = "DELEGATETHIS";
   public static final String TRUST = "TRUST";
 
   public static final String DELEGATETHIS = "DELEGATETHIS";
   public static final String TRUST = "TRUST";
 

+  public static final String TOP = "_top_";
+  public static final String BOTTOM = "_bottom_";
+

   State state;
   TypeUtil tu;
   FlowDownCheck flowDownChecker;
   State state;
   TypeUtil tu;
   FlowDownCheck flowDownChecker;


@@ -277,7 +280,7 @@ public class SSJavaAnalysis {
         String marker = an.getMarker();
         if (marker.equals(LATTICE)) {
           SSJavaLattice<String> locOrder =
         String marker = an.getMarker();
         if (marker.equals(LATTICE)) {
           SSJavaLattice<String> locOrder =

-              new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
+              new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);

           cd2lattice.put(cd, locOrder);
           parseClassLatticeDefinition(cd, an.getValue(), locOrder);
 
           cd2lattice.put(cd, locOrder);
           parseClassLatticeDefinition(cd, an.getValue(), locOrder);
 


@@ -288,7 +291,7 @@ public class SSJavaAnalysis {
 
         } else if (marker.equals(METHODDEFAULT)) {
           MethodLattice<String> locOrder =
 
         } else if (marker.equals(METHODDEFAULT)) {
           MethodLattice<String> locOrder =

-              new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
+              new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);

           cd2methodDefault.put(cd, locOrder);
           parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
         }
           cd2methodDefault.put(cd, locOrder);
           parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
         }


@@ -306,7 +309,7 @@ public class SSJavaAnalysis {
               if (an.getMarker().equals(LATTICE)) {
                 // developer explicitly defines method lattice
                 MethodLattice<String> locOrder =
               if (an.getMarker().equals(LATTICE)) {
                 // developer explicitly defines method lattice
                 MethodLattice<String> locOrder =

-                    new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
+                    new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);

                 md2lattice.put(md, locOrder);
                 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
               } else if (an.getMarker().equals(TERMINATE)) {
                 md2lattice.put(md, locOrder);
                 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
               } else if (an.getMarker().equals(TERMINATE)) {


@@ -327,8 +330,8 @@ public class SSJavaAnalysis {
     }
   }
 
     }
   }
 

-  public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
-      SSJavaLattice<String> locOrder) {
+  public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
+      SSJavaLattice<T> locOrder) {

 
     String fileName = "lattice_";
     if (md != null) {
 
     String fileName = "lattice_";
     if (md != null) {


@@ -338,32 +341,40 @@ public class SSJavaAnalysis {
       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
     }
 
       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
     }
 

-    Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
+    Set<Pair<T, T>> pairSet = locOrder.getOrderingPairSet();

 
 

-    try {
-      BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
+    if (pairSet.size() > 0) {
+      try {
+        BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));

 
 

-      bw.write("digraph " + fileName + " {\n");
+        bw.write("digraph " + fileName + " {\n");

 
 

-      for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
-        // pair is in the form of <higher, lower>
-        Pair<String, String> pair = (Pair<String, String>) iterator.next();
+        for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
+          // pair is in the form of <higher, lower>
+          Pair<T, T> pair = (Pair<T, T>) iterator.next();

 
 

-        String highLocId = pair.getFirst();
-        if (locOrder.isSharedLoc(highLocId)) {
-          highLocId = "\"" + highLocId + "*\"";
-        }
-        String lowLocId = pair.getSecond();
-        if (locOrder.isSharedLoc(lowLocId)) {
-          lowLocId = "\"" + lowLocId + "*\"";
+          T highLocId = pair.getFirst();
+          String highLocStr, lowLocStr;
+          if (locOrder.isSharedLoc(highLocId)) {
+            highLocStr = "\"" + highLocId + "*\"";
+          } else {
+            highLocStr = highLocId.toString();
+          }
+          T lowLocId = pair.getSecond();
+          if (locOrder.isSharedLoc(lowLocId)) {
+            lowLocStr = "\"" + lowLocId + "*\"";
+          } else {
+            lowLocStr = lowLocId.toString();
+          }
+          bw.write(highLocId + " -> " + lowLocId + ";\n");

         }
         }

-        bw.write(highLocId + " -> " + lowLocId + ";\n");
+        bw.write("}\n");
+        bw.close();
+
+      } catch (IOException e) {
+        e.printStackTrace();

       }
       }

-      bw.write("}\n");
-      bw.close();

 
 

-    } catch (IOException e) {
-      e.printStackTrace();

     }
 
   }
     }
 
   }

diff --git a/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java b/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java
deleted file mode 100644 (file)
index 369473c..0000000
--- a/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java
+++ /dev/null
@@ -1,921 +0,0 @@
-package Analysis.SSJava;
-
-import java.io.FileWriter;
-import java.io.IOException;
-import java.io.PrintWriter;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashSet;
-import java.util.Hashtable;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Set;
-
-import IR.ClassDescriptor;
-import IR.Descriptor;
-import IR.FieldDescriptor;
-import IR.MethodDescriptor;
-import IR.NameDescriptor;
-import IR.Operation;
-import IR.State;
-import IR.SymbolTable;
-import IR.VarDescriptor;
-import IR.Tree.ArrayAccessNode;
-import IR.Tree.AssignmentNode;
-import IR.Tree.BlockExpressionNode;
-import IR.Tree.BlockNode;
-import IR.Tree.BlockStatementNode;
-import IR.Tree.CastNode;
-import IR.Tree.DeclarationNode;
-import IR.Tree.ExpressionNode;
-import IR.Tree.IfStatementNode;
-import IR.Tree.Kind;
-import IR.Tree.LiteralNode;
-import IR.Tree.LoopNode;
-import IR.Tree.NameNode;
-import IR.Tree.OpNode;
-import IR.Tree.ReturnNode;
-import IR.Tree.SubBlockNode;
-import IR.Tree.SwitchStatementNode;
-import IR.Tree.SwitchBlockNode;
-
-public class SSJavaInferenceEngine {
-
-  State state;
-  static SSJavaAnalysis ssjava;
-
-  Set<ClassDescriptor> toanalyze;
-  List<ClassDescriptor> toanalyzeList;
-
-  Set<MethodDescriptor> toanalyzeMethod;
-  List<MethodDescriptor> toanalyzeMethodList;
-
-  // 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;
-
-  private Set<ImplicitTuple> implicitFlowSet; /*
-                                               * should maybe be
-                                               * hashtable<ExpressionNode
-                                               * ,Set<VarID>>
-                                               */
-  private RelationSet rSet;
-
-  boolean deterministic = true;
-
-  public SSJavaInferenceEngine(SSJavaAnalysis ssjava, State state) {
-    this.ssjava = ssjava;
-    this.state = state;
-    if (deterministic) {
-      this.toanalyzeList = new ArrayList<ClassDescriptor>();
-    } else {
-      this.toanalyze = new HashSet<ClassDescriptor>();
-    }
-    if (deterministic) {
-      this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
-    } else {
-      this.toanalyzeMethod = new HashSet<MethodDescriptor>();
-    }
-    this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
-    this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
-    this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
-    this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
-    this.implicitFlowSet = new HashSet<ImplicitTuple>();
-    this.rSet = new RelationSet();
-  }
-
-  public void init() {
-
-    // construct mapping from the location name to the class descriptor
-    // assume that the location name is unique through the whole program
-
-    Set<ClassDescriptor> cdSet = ssjava.getCd2lattice().keySet();
-    for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
-      ClassDescriptor cd = (ClassDescriptor) iterator.next();
-      SSJavaLattice<String> lattice = ssjava.getCd2lattice().get(cd);
-      Set<String> fieldLocNameSet = lattice.getKeySet();
-
-      for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) {
-        String fieldLocName = (String) iterator2.next();
-        fieldLocName2cd.put(fieldLocName, cd);
-      }
-
-    }
-
-  }
-
-  public boolean toAnalyzeIsEmpty() {
-    if (deterministic) {
-      return toanalyzeList.isEmpty();
-    } else {
-      return toanalyze.isEmpty();
-    }
-  }
-
-  public ClassDescriptor toAnalyzeNext() {
-    if (deterministic) {
-      return toanalyzeList.remove(0);
-    } else {
-      ClassDescriptor cd = toanalyze.iterator().next();
-      toanalyze.remove(cd);
-      return cd;
-    }
-  }
-
-  public void setupToAnalyze() {
-    SymbolTable classtable = state.getClassSymbolTable();
-    if (deterministic) {
-      toanalyzeList.clear();
-      toanalyzeList.addAll(classtable.getValueSet());
-      Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
-        public int compare(ClassDescriptor o1, ClassDescriptor o2) {
-          return o1.getClassName().compareTo(o2.getClassName());
-        }
-      });
-    } else {
-      toanalyze.clear();
-      toanalyze.addAll(classtable.getValueSet());
-    }
-  }
-
-  public void setupToAnalazeMethod(ClassDescriptor cd) {
-
-    SymbolTable methodtable = cd.getMethodTable();
-    if (deterministic) {
-      toanalyzeMethodList.clear();
-      toanalyzeMethodList.addAll(methodtable.getValueSet());
-      Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
-        public int compare(MethodDescriptor o1, MethodDescriptor o2) {
-          return o1.getSymbol().compareTo(o2.getSymbol());
-        }
-      });
-    } else {
-      toanalyzeMethod.clear();
-      toanalyzeMethod.addAll(methodtable.getValueSet());
-    }
-  }
-
-  public boolean toAnalyzeMethodIsEmpty() {
-    if (deterministic) {
-      return toanalyzeMethodList.isEmpty();
-    } else {
-      return toanalyzeMethod.isEmpty();
-    }
-  }
-
-  public MethodDescriptor toAnalyzeMethodNext() {
-    if (deterministic) {
-      return toanalyzeMethodList.remove(0);
-    } else {
-      MethodDescriptor md = toanalyzeMethod.iterator().next();
-      toanalyzeMethod.remove(md);
-      return md;
-    }
-  }
-
-  public void inference() {
-    FileWriter latticeFile;
-    PrintWriter latticeOut;
-    setupToAnalyze();
-
-    while (!toAnalyzeIsEmpty()) {
-      ClassDescriptor cd = toAnalyzeNext();
-      try {
-        latticeFile = new FileWriter(cd.getClassName() + ".lat");
-      } catch (IOException e) {
-        System.out.println("File Fail");
-        return;
-      }
-      latticeOut = new PrintWriter(latticeFile);
-      if (ssjava.needToBeAnnoated(cd)) {
-        setupToAnalazeMethod(cd);
-        while (!toAnalyzeMethodIsEmpty()) {
-          MethodDescriptor md = toAnalyzeMethodNext();
-          if (ssjava.needTobeAnnotated(md)) {
-            inferRelationsFromBlockNode(md, md.getParameterTable(), state.getMethodBody(md));
-            latticeOut.println(md.getClassMethodName() + "\n");
-            latticeOut.println(rSet.toString());
-            rSet = new RelationSet();
-          }
-        }
-      }
-      latticeOut.flush();
-      latticeOut.close();
-    }
-  }
-
-  private void inferRelationsFromBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
-
-    bn.getVarTable().setParent(nametable);
-    for (int i = 0; i < bn.size(); i++) {
-      BlockStatementNode bsn = bn.get(i);
-      inferRelationsFromBlockStatementNode(md, bn.getVarTable(), bsn);
-    }
-
-  }
-
-  private void inferRelationsFromBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
-      BlockStatementNode bsn) {
-
-    switch (bsn.kind()) {
-    case Kind.BlockExpressionNode:
-      inferRelationsFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
-      break;
-
-    case Kind.DeclarationNode:
-      inferRelationsFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
-      break;
-
-    case Kind.IfStatementNode:
-      inferRelationsFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
-      break;
-
-    case Kind.LoopNode:
-      inferRelationsFromLoopNode(md, nametable, (LoopNode) bsn);
-      break;
-
-    case Kind.ReturnNode:
-      inferRelationsFromReturnNode(md, nametable, (ReturnNode) bsn);
-      break;
-
-    case Kind.SubBlockNode:
-      inferRelationsFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
-      break;
-  
-    case Kind.SwitchStatementNode:
-      inferRelationsFromSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
-      break;
-
-    default:
-      System.out.println(bsn.kind() + " not handled...");
-      break;
-    }
-  }
-
-  private void inferRelationsFromSwitchStatementNode(MethodDescriptor md,
-      SymbolTable nametable, SwitchStatementNode ssn) {
-
-    ClassDescriptor cd = md.getClassDesc();
-    VarID condID =
-        inferRelationsFromExpressionNode(md, nametable, ssn.getCondition(), null, (BlockStatementNode) ssn, false);
-    BlockNode sbn = ssn.getSwitchBody();
-
-    for (int i = 0; i < sbn.size(); i++) {
-       inferRelationsFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
-    }
-
-    for(ImplicitTuple tuple: implicitFlowSet){
-      if(tuple.isFromBranch((BlockStatementNode) ssn)){
-        implicitFlowSet.remove(tuple);
-      }
-    }
-  }
-
-  private void inferRelationsFromSwitchBlockNode(MethodDescriptor md,
-      SymbolTable nametable, SwitchBlockNode sbn) {
-    inferRelationsFromBlockNode(md, nametable, sbn.getSwitchBlockStatement());
-  }
-
-  private void inferRelationsFromReturnNode(MethodDescriptor md, SymbolTable nametable,
-      ReturnNode rn) {
-
-    ExpressionNode returnExp = rn.getReturnExpression();
-
-    // interim fixes
-    VarID returnID = new VarID(md);
-    returnID.setReturn();
-    if (returnExp != null) {
-      inferRelationsFromExpressionNode(md, nametable, returnExp, returnID, null, false);
-    }
-  }
-
-  private void inferRelationsFromLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
-
-    ClassDescriptor cd = md.getClassDesc();
-    if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
-
-      inferRelationsFromExpressionNode(md, nametable, ln.getCondition(), null, ln, false);
-
-      inferRelationsFromBlockNode(md, nametable, ln.getBody());
-
-      for (ImplicitTuple tuple : implicitFlowSet) {
-        if (tuple.isFromBranch(ln)) {
-          implicitFlowSet.remove(tuple);
-        }
-      }
-
-    } else {
-      // check 'for loop' case
-      BlockNode bn = ln.getInitializer();
-      bn.getVarTable().setParent(nametable);
-
-      inferRelationsFromBlockNode(md, nametable, bn);
-      inferRelationsFromExpressionNode(md, bn.getVarTable(), ln.getCondition(), null, ln, false);
-
-      inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
-      inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getBody());
-
-      for (ImplicitTuple tuple : implicitFlowSet) {
-        if (tuple.isFromBranch(ln)) {
-          implicitFlowSet.remove(tuple);
-        }
-      }
-
-    }
-
-  }
-
-  private void inferRelationsFromSubBlockNode(MethodDescriptor md,
-      SymbolTable nametable, SubBlockNode sbn) {
-      inferRelationsFromBlockNode(md, nametable.getParent(), sbn.getBlockNode());
-  }
-
-  private void inferRelationsFromIfStatementNode(MethodDescriptor md, SymbolTable nametable,
-      IfStatementNode isn) {
-
-    inferRelationsFromExpressionNode(md, nametable, isn.getCondition(), null, isn, false);
-
-    inferRelationsFromBlockNode(md, nametable, isn.getTrueBlock());
-
-    if (isn.getFalseBlock() != null) {
-      inferRelationsFromBlockNode(md, nametable, isn.getFalseBlock());
-    }
-
-    for (ImplicitTuple tuple : implicitFlowSet) {
-      if (tuple.isFromBranch(isn)) {
-        implicitFlowSet.remove(tuple);
-      }
-    }
-  }
-
-  private void inferRelationsFromDeclarationNode(MethodDescriptor md, SymbolTable nametable,
-      DeclarationNode dn) {
-  }
-
-  private void inferRelationsFromBlockExpressionNode(MethodDescriptor md,
-      SymbolTable nametable, BlockExpressionNode ben) {
-      inferRelationsFromExpressionNode(md, nametable, ben.getExpression(), null, null, false);
-  }
-
-  private VarID inferRelationsFromExpressionNode(MethodDescriptor md, SymbolTable nametable,
-      ExpressionNode en, VarID flowTo, BlockStatementNode implicitTag, boolean isLHS) {
-
-    VarID var = null;
-    switch (en.kind()) {
-
-    case Kind.AssignmentNode:
-      var =
-          inferRelationsFromAssignmentNode(md, nametable, (AssignmentNode) en, flowTo, implicitTag);
-      break;
-
-    // case Kind.FieldAccessNode:
-    // var =
-    // inferRelationsFromFieldAccessNode(md, nametable, (FieldAccessNode) en,
-    // flowTo);
-    // break;
-
-    case Kind.NameNode:
-      var = inferRelationsFromNameNode(md, nametable, (NameNode) en, flowTo, implicitTag);
-      break;
-
-    case Kind.OpNode:
-      var = inferRelationsFromOpNode(md, nametable, (OpNode) en, flowTo, implicitTag);
-      break;
-    /*
-     * case Kind.CreateObjectNode: var = inferRelationsFromCreateObjectNode(md,
-     * nametable, (CreateObjectNode) en); break;
-     */ 
-    case Kind.ArrayAccessNode: 
-      var = inferRelationsFromArrayAccessNode(md, nametable, (ArrayAccessNode) en, flowTo, implicitTag, isLHS); 
-      break;
-    
-    case Kind.LiteralNode:
-      var = inferRelationsFromLiteralNode(md, nametable, (LiteralNode) en);
-      break;
-    /*
-     * case Kind.MethodInvokeNode: var = inferRelationsFromMethodInvokeNode(md,
-     * nametable, (MethodInvokeNode) en, flowTo); break;
-     * 
-     * case Kind.TertiaryNode: var = inferRelationsFromTertiaryNode(md,
-     * nametable, (TertiaryNode) en); break;
-     */ 
-      case Kind.CastNode: 
-       var = inferRelationsFromCastNode(md, nametable, (CastNode) en, flowTo, implicitTag); 
-       break;
-
-    default:
-      System.out.println("expressionnode not handled...");
-      return null;
-
-    }
-    // addTypeLocation(en.getType(), compLoc);
-    return var;
-
-  }
-
-  
-   private VarID inferRelationsFromCastNode(MethodDescriptor md,
-      SymbolTable nametable, CastNode cn, VarID flowTo, BlockStatementNode implicitTag) {
-    
-    ExpressionNode en = cn.getExpression();
-    return inferRelationsFromExpressionNode(md, nametable, en, flowTo, implicitTag, false);
-    
-   }
-  /* 
-   * private CompositeLocation inferRelationsFromTertiaryNode(MethodDescriptor
-   * md, SymbolTable nametable, TertiaryNode tn, CompositeLocation constraint) {
-   * ClassDescriptor cd = md.getClassDesc();
-   * 
-   * CompositeLocation condLoc = inferRelationsFromExpressionNode(md, nametable,
-   * tn.getCond(), new CompositeLocation(), constraint, false); //
-   * addLocationType(tn.getCond().getType(), condLoc); CompositeLocation trueLoc
-   * = inferRelationsFromExpressionNode(md, nametable, tn.getTrueExpr(), new
-   * CompositeLocation(), constraint, false); //
-   * addLocationType(tn.getTrueExpr().getType(), trueLoc); CompositeLocation
-   * falseLoc = inferRelationsFromExpressionNode(md, nametable,
-   * tn.getFalseExpr(), new CompositeLocation(), constraint, false); //
-   * 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
-   * (!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 (!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()); }
-   * 
-   * // then, return glb of trueLoc & falseLoc Set<CompositeLocation>
-   * glbInputSet = new HashSet<CompositeLocation>(); glbInputSet.add(trueLoc);
-   * glbInputSet.add(falseLoc);
-   * 
-   * return CompositeLattice.calculateGLB(glbInputSet, generateErrorMessage(cd,
-   * tn)); }
-   * 
-   * private CompositeLocation
-   * inferRelationsFromMethodInvokeNode(MethodDescriptor md, SymbolTable
-   * nametable, MethodInvokeNode min, CompositeLocation loc, CompositeLocation
-   * constraint) {
-   * 
-   * CompositeLocation baseLocation = null; if (min.getExpression() != null) {
-   * baseLocation = inferRelationsFromExpressionNode(md, nametable,
-   * min.getExpression(), new CompositeLocation(), constraint, false); } else {
-   * 
-   * if (min.getMethod().isStatic()) { String globalLocId =
-   * ssjava.getMethodLattice(md).getGlobalLoc(); if (globalLocId == null) {
-   * throw new
-   * Error("Method lattice does not define global variable location at " +
-   * generateErrorMessage(md.getClassDesc(), min)); } baseLocation = new
-   * CompositeLocation(new Location(md, globalLocId)); } else { String thisLocId
-   * = ssjava.getMethodLattice(md).getThisLoc(); baseLocation = new
-   * CompositeLocation(new Location(md, thisLocId)); } }
-   * 
-   * checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
-   * 
-   * checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation,
-   * constraint);
-   * 
-   * 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,
-   * constraint); return ceilingLoc; }
-   * 
-   * return new CompositeLocation();
-   * 
-   * }
-   * 
-   * private void checkCallerArgumentLocationConstraints(MethodDescriptor md,
-   * SymbolTable nametable, MethodInvokeNode min, CompositeLocation
-   * callerBaseLoc, CompositeLocation constraint) { // if parameter location
-   * consists of THIS and FIELD location, // caller should pass an argument that
-   * is comparable to the declared // parameter location // and is not lower
-   * than the declared parameter location in the field // lattice.
-   * 
-   * MethodDescriptor calleemd = min.getMethod();
-   * 
-   * List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
-   * List<CompositeLocation> calleeParamList = new
-   * ArrayList<CompositeLocation>();
-   * 
-   * MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
-   * Location calleeThisLoc = new Location(calleemd,
-   * calleeLattice.getThisLoc());
-   * 
-   * for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en =
-   * min.getArg(i); CompositeLocation callerArgLoc =
-   * inferRelationsFromExpressionNode(md, nametable, en, new
-   * CompositeLocation(), constraint, false); callerArgList.add(callerArgLoc); }
-   * 
-   * // setup callee params set for (int i = 0; i < calleemd.numParameters();
-   * i++) { VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
-   * CompositeLocation calleeLoc = d2loc.get(calleevd);
-   * calleeParamList.add(calleeLoc); }
-   * 
-   * String errorMsg = generateErrorMessage(md.getClassDesc(), min);
-   * 
-   * System.out.println("checkCallerArgumentLocationConstraints=" +
-   * min.printNode(0)); System.out.println("base location=" + callerBaseLoc);
-   * 
-   * for (int i = 0; i < calleeParamList.size(); i++) { CompositeLocation
-   * calleeParamLoc = calleeParamList.get(i); if
-   * (calleeParamLoc.get(0).equals(calleeThisLoc) && calleeParamLoc.getSize() >
-   * 1) {
-   * 
-   * // callee parameter location has field information CompositeLocation
-   * callerArgLoc = callerArgList.get(i);
-   * 
-   * CompositeLocation paramLocation = translateCalleeParamLocToCaller(md,
-   * calleeParamLoc, callerBaseLoc, errorMsg);
-   * 
-   * Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>(); if
-   * (constraint != null) { inputGLBSet.add(callerArgLoc);
-   * inputGLBSet.add(constraint); callerArgLoc =
-   * CompositeLattice.calculateGLB(inputGLBSet,
-   * generateErrorMessage(md.getClassDesc(), min)); }
-   * 
-   * if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg))
-   * { throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : "
-   * + callerArgLoc +
-   * "' should be higher than corresponding callee's parameter : " +
-   * paramLocation + " at " + errorMsg); }
-   * 
-   * } }
-   * 
-   * }
-   * 
-   * private CompositeLocation translateCalleeParamLocToCaller(MethodDescriptor
-   * md, CompositeLocation calleeParamLoc, CompositeLocation callerBaseLocation,
-   * String errorMsg) {
-   * 
-   * CompositeLocation translate = new CompositeLocation();
-   * 
-   * for (int i = 0; i < callerBaseLocation.getSize(); i++) {
-   * translate.addLocation(callerBaseLocation.get(i)); }
-   * 
-   * for (int i = 1; i < calleeParamLoc.getSize(); i++) {
-   * translate.addLocation(calleeParamLoc.get(i)); }
-   * 
-   * System.out.println("TRANSLATED=" + translate + " from calleeParamLoc=" +
-   * calleeParamLoc);
-   * 
-   * return translate; }
-   * 
-   * private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor
-   * md, SymbolTable nametable, MethodInvokeNode min, CompositeLocation
-   * baseLocation, CompositeLocation constraint) { 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 =
-   * inferRelationsFromExpressionNode(md, nametable, en, new
-   * CompositeLocation(), constraint, false); argList.add(callerArg); }
-   * 
-   * System.out.println("\n## computeReturnLocation=" + min.getMethod() +
-   * " argList=" + argList); CompositeLocation compLoc =
-   * md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
-   * DeltaLocation delta = new DeltaLocation(compLoc, 1);
-   * System.out.println("##computeReturnLocation=" + delta);
-   * 
-   * return delta;
-   * 
-   * }
-   * 
-   * private void checkCalleeConstraints(MethodDescriptor md, SymbolTable
-   * nametable, MethodInvokeNode min, CompositeLocation callerBaseLoc,
-   * CompositeLocation constraint) {
-   * 
-   * System.out.println("checkCalleeConstraints="+min.printNode(0));
-   * 
-   * MethodDescriptor calleemd = min.getMethod();
-   * 
-   * MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
-   * CompositeLocation calleeThisLoc = new CompositeLocation(new
-   * Location(calleemd, calleeLattice.getThisLoc()));
-   * 
-   * List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
-   * List<CompositeLocation> calleeParamList = new
-   * ArrayList<CompositeLocation>();
-   * 
-   * if (min.numArgs() > 0) { // caller needs to guarantee that it passes
-   * arguments in regarding to // callee's hierarchy
-   * 
-   * // setup caller args set // first, add caller's base(this) location
-   * callerArgList.add(callerBaseLoc); // second, add caller's arguments for
-   * (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = min.getArg(i);
-   * CompositeLocation callerArgLoc = inferRelationsFromExpressionNode(md,
-   * nametable, en, new CompositeLocation(), constraint, false);
-   * callerArgList.add(callerArgLoc); }
-   * 
-   * // setup callee params set // first, add callee's this location
-   * calleeParamList.add(calleeThisLoc); // second, add callee's parameters for
-   * (int i = 0; i < calleemd.numParameters(); i++) { VarDescriptor calleevd =
-   * (VarDescriptor) calleemd.getParameter(i); CompositeLocation calleeLoc =
-   * d2loc.get(calleevd);
-   * System.out.println("calleevd="+calleevd+" loc="+calleeLoc);
-   * calleeParamList.add(calleeLoc); }
-   * 
-   * // here, check if ordering relations among caller's args respect //
-   * ordering relations in-between callee's args CHECK: for (int i = 0; i <
-   * calleeParamList.size(); i++) { CompositeLocation calleeLoc1 =
-   * calleeParamList.get(i); CompositeLocation callerLoc1 =
-   * callerArgList.get(i);
-   * 
-   * for (int j = 0; j < calleeParamList.size(); j++) { if (i != j) {
-   * CompositeLocation calleeLoc2 = calleeParamList.get(j); CompositeLocation
-   * callerLoc2 = callerArgList.get(j);
-   * 
-   * if (callerLoc1.get(callerLoc1.getSize() - 1).isTop() ||
-   * callerLoc2.get(callerLoc2.getSize() - 1).isTop()) { continue CHECK; }
-   * 
-   * System.out.println("calleeLoc1="+calleeLoc1);
-   * System.out.println("calleeLoc2="
-   * +calleeLoc2+"calleeParamList="+calleeParamList);
-   * 
-   * int callerResult = CompositeLattice.compare(callerLoc1, callerLoc2, true,
-   * generateErrorMessage(md.getClassDesc(), min)); int calleeResult =
-   * CompositeLattice.compare(calleeLoc1, calleeLoc2, true,
-   * 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
-   * 
-   * String paramName1, paramName2;
-   * 
-   * if (i == 0) { paramName1 = "'THIS'"; } else { paramName1 = "'parameter " +
-   * calleemd.getParamName(i - 1) + "'"; }
-   * 
-   * if (j == 0) { paramName2 = "'THIS'"; } else { paramName2 = "'parameter " +
-   * calleemd.getParamName(j - 1) + "'"; }
-   * 
-   * throw new Error(
-   * "Caller doesn't respect an ordering relation among method arguments: callee expects that "
-   * + paramName1 + " should be higher than " + paramName2 + " in " + calleemd +
-   * " at " + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine()); }
-   * }
-   * 
-   * } }
-   * 
-   * }
-   * 
-   * }
-   */ 
-    private VarID inferRelationsFromArrayAccessNode(MethodDescriptor md, SymbolTable
-      nametable, ArrayAccessNode aan, VarID flowTo, BlockStatementNode implicitTag, boolean isLHS) {
-    
-    
-      VarID arrayID = inferRelationsFromExpressionNode(md, nametable, aan.getExpression(), flowTo, implicitTag, isLHS);
-    
-      if (isLHS) { 
-       VarID indexID = inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), arrayID, implicitTag, isLHS);
-      }
-      else{
-       VarID indexID = inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), flowTo, implicitTag, isLHS);
-      }
-      return arrayID;
-    }
-
-    /*
-    private CompositeLocation
-    inferRelationsFromCreateObjectNode(MethodDescriptor md, SymbolTable
-    nametable, CreateObjectNode con) {
-    
-    ClassDescriptor cd = md.getClassDesc();
-    
-    CompositeLocation compLoc = new CompositeLocation();
-    compLoc.addLocation(Location.createTopLocation(md)); return compLoc;
-    
-    }
-    */
-  private VarID inferRelationsFromOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
-      VarID flowTo, BlockStatementNode implicitTag) {
-
-    VarID var =
-        inferRelationsFromExpressionNode(md, nametable, on.getLeft(), flowTo, implicitTag, false);
-
-    if (on.getRight() != null) {
-      inferRelationsFromExpressionNode(md, nametable, on.getRight(), flowTo, implicitTag, false);
-    }
-
-    Operation op = on.getOp();
-
-    switch (op.getOp()) {
-
-    case Operation.UNARYPLUS:
-    case Operation.UNARYMINUS:
-    case Operation.LOGIC_NOT:
-      // single operand
-      return var;
-
-    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:
-
-      return var;
-
-    default:
-      throw new Error(op.toString());
-    }
-
-  }
-
-  private VarID inferRelationsFromLiteralNode(MethodDescriptor md, SymbolTable nametable,
-      LiteralNode ln) {
-    // literal data flow does not matter
-    return null;
-
-  }
-
-  private VarID inferRelationsFromNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn,
-      VarID flowTo, BlockStatementNode implicitTag) {
-    VarID var = null;
-    NameDescriptor nd = nn.getName();
-    if (nd.getBase() != null) {
-      var =
-          inferRelationsFromExpressionNode(md, nametable, nn.getExpression(), flowTo, implicitTag,
-              false);
-    } else {
-      String varname = nd.toString();
-      if (varname.equals("this")) {
-        var = new VarID(nd);
-        if (flowTo != null) {
-          rSet.addRelation(new BinaryRelation(var, flowTo));
-        }
-        if (implicitTag != null) {
-          implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-        }
-        var.setThis();
-        return var;
-      }
-
-      Descriptor d = (Descriptor) nametable.get(varname);
-
-      if (d instanceof VarDescriptor) {
-        var = new VarID(nd);
-        if (flowTo != null) {
-          rSet.addRelation(new BinaryRelation(var, flowTo));
-        }
-        if (implicitTag != null) {
-          implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-        }
-      } else if (d instanceof FieldDescriptor) {
-        FieldDescriptor fd = (FieldDescriptor) d;
-        if (fd.isStatic()) {
-          if (fd.isFinal()) {
-            var = new VarID(nd);
-            if (flowTo != null) {
-              rSet.addRelation(new BinaryRelation(var, flowTo));
-            }
-            if (implicitTag != null) {
-              implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-            }
-            var.setTop();
-            return var;
-          } else {
-            var = new VarID(nd);
-            if (flowTo != null) {
-              rSet.addRelation(new BinaryRelation(var, flowTo));
-            }
-            if (implicitTag != null) {
-              implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-            }
-            var.setGlobal();
-          }
-        } else {
-          var = new VarID(nd);
-          if (flowTo != null) {
-            rSet.addRelation(new BinaryRelation(var, flowTo));
-          }
-          if (implicitTag != null) {
-            implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-          }
-          var.setThis();
-        }
-      } else if (d == null) {
-        var = new VarID(nd);
-        if (flowTo != null) {
-          rSet.addRelation(new BinaryRelation(var, flowTo));
-        }
-        if (implicitTag != null) {
-          implicitFlowSet.add(new ImplicitTuple(var, implicitTag));
-        }
-        var.setGlobal();
-        return var;
-      }
-    }
-    return var;
-  }
-
-  /*
-   * private CompositeLocation
-   * inferRelationsFromFieldAccessNode(MethodDescriptor md, SymbolTable
-   * nametable, FieldAccessNode fan, CompositeLocation loc, CompositeLocation
-   * constraint) {
-   * 
-   * ExpressionNode left = fan.getExpression(); TypeDescriptor ltd =
-   * left.getType();
-   * 
-   * FieldDescriptor fd = fan.getField();
-   * 
-   * String varName = null; if (left.kind() == Kind.NameNode) { NameDescriptor
-   * nd = ((NameNode) left).getName(); varName = nd.toString(); }
-   * 
-   * if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
-   * // using a class name directly or access using this if (fd.isStatic() &&
-   * fd.isFinal()) { loc.addLocation(Location.createTopLocation(md)); return
-   * loc; } }
-   * 
-   * loc = inferRelationsFromExpressionNode(md, nametable, left, loc,
-   * constraint, false);
-   * System.out.println("### inferRelationsFromFieldAccessNode=" +
-   * fan.printNode(0)); System.out.println("### left=" + left.printNode(0)); if
-   * (!left.getType().isPrimitive()) { Location fieldLoc = getFieldLocation(fd);
-   * loc.addLocation(fieldLoc); }
-   * 
-   * return loc; }
-   * 
-   * private Location getFieldLocation(FieldDescriptor fd) {
-   * 
-   * System.out.println("### getFieldLocation=" + fd);
-   * System.out.println("### fd.getType().getExtension()=" +
-   * fd.getType().getExtension());
-   * 
-   * Location fieldLoc = (Location) fd.getType().getExtension();
-   * 
-   * // handle the case that method annotation checking skips checking field //
-   * declaration if (fieldLoc == null) { fieldLoc =
-   * checkFieldDeclaration(fd.getClassDescriptor(), fd); }
-   * 
-   * return fieldLoc;
-   * 
-   * }
-   */
-
-  private VarID inferRelationsFromAssignmentNode(MethodDescriptor md, SymbolTable nametable,
-      AssignmentNode an, VarID flowTo, BlockStatementNode implicitTag) {
-    ClassDescriptor cd = md.getClassDesc();
-    boolean postinc = true;
-
-    if (an.getOperation().getBaseOp() == null
-        || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
-            .getBaseOp().getOp() != Operation.POSTDEC))
-      postinc = false;
-    // get ID for leftside
-    VarID destID =
-        inferRelationsFromExpressionNode(md, nametable, an.getDest(), flowTo, implicitTag, true);
-
-    if (!postinc) {
-      // recursively add relations from RHS to LHS
-      inferRelationsFromExpressionNode(md, nametable, an.getSrc(), destID, null, false);
-
-    } else {
-      // add relation to self
-      destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), destID, null, false);
-    }
-
-    // checks if flow to anythin and adds relation
-    if (flowTo != null) {
-      rSet.addRelation(new BinaryRelation(destID, flowTo));
-    }
-
-    // add relations for implicit flow
-    for (ImplicitTuple it : implicitFlowSet) {
-      rSet.addRelation(new BinaryRelation(it.getVar(), destID));
-    }
-
-    return destID;
-  }
-}
\ No newline at end of file

diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java
index cbbae46c8ffb2ae6a59c547a615a10bbd6fcb8ff..be1a342ec9ff6d2630cf5cc7d0b8908829c48559 100644 (file)
--- a/Robust/src/Analysis/SSJava/SSJavaLattice.java
+++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java
@@ -1,16 +1,15 @@
 package Analysis.SSJava;
 
 import java.util.HashSet;
 package Analysis.SSJava;
 
 import java.util.HashSet;

+import java.util.Iterator;

 import java.util.Set;
 
 import Util.Lattice;
 
 public class SSJavaLattice<T> extends Lattice<T> {
 
 import java.util.Set;
 
 import Util.Lattice;
 
 public class SSJavaLattice<T> extends Lattice<T> {
 

-  public static final String TOP = "_top_";
-  public static final String BOTTOM = "_bottom_";
-

   Set<T> sharedLocSet;
   Set<T> sharedLocSet;

+  public static int seed = 0;

 
   public SSJavaLattice(T top, T bottom) {
     super(top, bottom);
 
   public SSJavaLattice(T top, T bottom) {
     super(top, bottom);


@@ -36,4 +35,32 @@ public class SSJavaLattice<T> extends Lattice<T> {
     return put(higher, lower);
   }
 
     return put(higher, lower);
   }
 

+  public void insertNewLocationAtOneLevelHigher(T lowerLoc, T newLoc) {
+    // first identifying which location is connected to the input loc
+    Set<T> keySet = getKeySet();
+    Set<T> oneLevelHigherLocSet = new HashSet<T>();
+
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T locKey = (T) iterator.next();
+      Set<T> conntectedSet = get(locKey);
+      for (Iterator iterator2 = conntectedSet.iterator(); iterator2.hasNext();) {
+        T connectedLoc = (T) iterator2.next();
+        if (connectedLoc.equals(lowerLoc)) {
+          oneLevelHigherLocSet.add(locKey);
+        }
+      }
+    }
+
+    put(newLoc);
+    addRelationHigherToLower(newLoc, lowerLoc);
+
+    for (Iterator iterator = oneLevelHigherLocSet.iterator(); iterator.hasNext();) {
+      T higherLoc = (T) iterator.next();
+      // remove an existing edge between the higher loc and the input loc
+      get(higherLoc).remove(lowerLoc);
+      // add a new edge from the higher loc to the new location
+      put(higherLoc, newLoc);
+    }
+
+  }

 }
 }

diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java
index 22ed8d64f99c711882b2c9728e1f6390c54bd00c..bc024cfad9cd95f58d7b06bea451823bb879915b 100644 (file)
--- a/Robust/src/Util/Lattice.java
+++ b/Robust/src/Util/Lattice.java
@@ -76,7 +76,9 @@ public class Lattice<T> {
       topNeighbor.remove(value);
 
       // if key is already connected with bottom,, 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());
+      if (!value.equals(getBottomItem())) {
+        table.get(key).remove(getBottomItem());
+      }

 
       return true;
     } else
 
       return true;
     } else


@@ -129,7 +131,9 @@ public class Lattice<T> {
 
     Set<T> neighborSet = get(a);
 
 
     Set<T> neighborSet = get(a);
 

-    if (neighborSet == null) {
+    if (a.equals(b)) {
+      return true;
+    } else if (neighborSet == null) {

       return false;
     } else if (neighborSet.contains(b)) {
       return true;
       return false;
     } else if (neighborSet.contains(b)) {
       return true;


@@ -146,6 +150,10 @@ public class Lattice<T> {
 
   public boolean isGreaterThan(T a, T b) {
 
 
   public boolean isGreaterThan(T a, T b) {
 

+    if (a.equals(b)) {
+      return false;
+    }
+

     if (a.equals(top)) {
       if (b.equals(top)) {
         return false;
     if (a.equals(top)) {
       if (b.equals(top)) {
         return false;