changes.
authorYong hun eom <yeom@uci.edu>
Tue, 5 Mar 2013 04:46:34 +0000 (20:46 -0800)
committerYong hun eom <yeom@uci.edu>
Tue, 5 Mar 2013 04:46:34 +0000 (20:46 -0800)
Robust/src/Analysis/SSJava/BuildLattice.java
Robust/src/Analysis/SSJava/HierarchyGraph.java
Robust/src/Analysis/SSJava/SSJavaAnalysis.java

index adce54e..4320144 100644 (file)
@@ -30,6 +30,10 @@ public class BuildLattice {
 
   private Map<Descriptor, Map<LineIdentifier, LinkedList<LocPair>>> mapDescToLineListMap;
 
+  public BuildLattice() {
+    this(null);
+  }
+
   public BuildLattice(LocationInference infer) {
     this.infer = infer;
     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
@@ -86,7 +90,7 @@ public class BuildLattice {
 
       SSJavaLattice<String> naive_lattice =
           buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
-      int numLocs = naive_lattice.getKeySet().size();
+      int numLocs = naive_lattice.getKeySet().size() ;
       LocationInference.numLocationsNaive += numLocs;
       infer.mapNumLocsMapNaive.put(desc, new Integer(numLocs));
 
@@ -97,6 +101,15 @@ public class BuildLattice {
           + naive_lattice.getKeySet().size());
 
       infer.addNaiveLattice(desc, naive_lattice);
+
+      // write a dot file before everything is done
+      if (desc instanceof ClassDescriptor) {
+        infer.writeInferredLatticeDotFile((ClassDescriptor) desc, null, naive_lattice, "_naive");
+      } else {
+        MethodDescriptor md = (MethodDescriptor) desc;
+        infer.writeInferredLatticeDotFile(md.getClassDesc(), md, naive_lattice, "_naive");
+      }
+
     }
 
     // /////////////////////////////////////////////////////////////////////////////////////
@@ -134,6 +147,79 @@ public class BuildLattice {
     }
   }
 
+  private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
+      Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
+
+    System.out.println("\nBuild Complete Lattice:" + inputGraph.getName());
+
+    SSJavaLattice<String> completeLattice =
+        new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
+
+    Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
+
+    Set<Set<Integer>> keySet = mapImSucc.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Set<Integer> higher = (Set<Integer>) iterator.next();
+
+      String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
+
+      HNode higherNode = inputGraph.getHNode(higherName);
+
+      if (higherNode == null) {
+        NameDescriptor d = new NameDescriptor(higherName);
+        higherNode = inputGraph.getHNode(d);
+        higherNode.setSkeleton(true);
+      }
+
+      if (higherNode != null && higherNode.isSharedNode()) {
+        completeLattice.addSharedLoc(higherName);
+      }
+      Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
+      // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
+      // + descSet);
+
+      // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
+
+      Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
+      for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
+        Set<Integer> lower = (Set<Integer>) iterator2.next();
+
+        String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
+        HNode lowerNode = inputGraph.getHNode(lowerName);
+
+        if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
+          NameDescriptor d = new NameDescriptor(lowerName);
+          lowerNode = inputGraph.getHNode(d);
+          lowerNode.setSkeleton(true);
+        }
+
+        if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
+          inputGraph.addEdge(higherNode, lowerNode);
+        }
+
+        if (lowerNode != null && lowerNode.isSharedNode()) {
+          completeLattice.addSharedLoc(lowerName);
+        }
+
+        Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
+        // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
+        // + lowerDescSet);
+        // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
+
+        if (higher.size() == 0) {
+          // empty case
+          completeLattice.put(lowerName);
+        } else {
+          completeLattice.addRelationHigherToLower(higherName, lowerName);
+        }
+
+      }
+
+    }
+
+    return completeLattice;
+  }
+
   private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
       HierarchyGraph inputGraph, LocationSummary locSummary,
       Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
@@ -328,7 +414,11 @@ public class BuildLattice {
             // System.out.println("   hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
             // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
 
+            
+            //TODO attempt to use  non-transitive reachToSet
+//            Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachToNoTransitive(hNode);
             Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode);
+//            System.out.println("reachToSet=" + reachToSet);
             for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
               HNode reachToNode = (HNode) iterator2.next();
               aboveSet.add(scGraph.getCurrentHNode(reachToNode));
@@ -345,7 +435,7 @@ public class BuildLattice {
             endSet.add(hierarchyGraph.getCurrentHNode(aboveNode));
           }
 
-          trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet);
+          trace = hierarchyGraph.computeDistance(hNode, endSet, scGraph, combineSkeletonNodeSet);
 
           System.out.println("   COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace="
               + trace);
@@ -1143,6 +1233,16 @@ public class BuildLattice {
     System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
   }
 
+  public SSJavaLattice<String> buildLattice(HierarchyGraph hierarchyGraph) {
+    BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet<HNode>());
+
+    Family family = generateFamily(basisSet);
+    Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
+
+    SSJavaLattice<String> completeLattice = buildLattice(basisSet, hierarchyGraph, mapImSucc);
+    return completeLattice;
+  }
+
 }
 
 class Identifier {
index f39ac73..d790093 100644 (file)
@@ -893,6 +893,22 @@ public class HierarchyGraph {
 
   }
 
+  public Set<HNode> getSkeleteNodeSetReachToNoTransitive(HNode node) {
+
+    Set<HNode> reachToSet = new HashSet<HNode>();
+    Set<HNode> visited = new HashSet<HNode>();
+    // visited.add(node);
+    recurSkeletonReachTo(node, reachToSet, visited);
+
+    // obsolete!
+    // if a node reaches to one of elements in the reachToSet, we do not need to keep it
+    // because the node is not directly connected to the combination node
+    // removeRedundantReachToNodes(reachToSet);
+
+    return removeTransitivelyReachToSet(reachToSet);
+    // return reachToSet;
+  }
+
   public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 
     Set<HNode> reachToSet = new HashSet<HNode>();
@@ -905,6 +921,7 @@ public class HierarchyGraph {
     // because the node is not directly connected to the combination node
     // removeRedundantReachToNodes(reachToSet);
 
+    // TODO
     return removeTransitivelyReachToSet(reachToSet);
     // return reachToSet;
   }
@@ -1422,9 +1439,18 @@ public class HierarchyGraph {
     return max;
   }
 
-  public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
-    // System.out.println("#####computeDistanceance startNode=" + startNode + " endNode=" +
-    // endNodeSet);
+  public Stack<String> computeDistance2(HNode startNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, Set<HNode> combineSet) {
+    System.out
+        .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
+    Stack<String> trace = new Stack<String>();
+    return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace);
+  }
+
+  public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, Set<HNode> combineSet) {
+    System.out
+        .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
     Stack<String> trace = new Stack<String>();
     return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
   }
@@ -1462,7 +1488,7 @@ public class HierarchyGraph {
         }
       }
 
-      System.out.println("    traverse more to" + inNode + "  before-trace=" + trace);
+      // System.out.println("    traverse more to" + inNode + "  before-trace=" + trace);
       Stack<String> newTrace = (Stack<String>) trace.clone();
       Stack<String> curTrace =
           recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
@@ -1474,24 +1500,34 @@ public class HierarchyGraph {
       }
     }
     return curMaxTrace;
+
   }
 
-  private int recur_computeDistance2(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
-      int count, Set<HNode> combineSet) {
+  private Stack<String> recur_computeDistance2(HNode curNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, int count, Set<HNode> combineSet, Stack<String> trace) {
 
-    if (!curNode.equals(startNode)) {
-      // do not count the start node
-      count++;
+    if (!curNode.isSkeleton()) {
+      if (curNode.isSharedNode()) {
+        trace.add("S");
+      } else {
+        trace.add("N");
+      }
     }
 
-    if (endNodeSet.contains(curNode)) {
+    System.out.println("   curNode=" + curNode + "  curTrace=" + trace);
+    // System.out.println("     curNode=" + curNode + "  curSCNode="
+    // + scGraph.getCurrentHNode(curNode) + " contains="
+    // + endNodeSet.contains(scGraph.getCurrentHNode(curNode)));
+    if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) {
       // it reaches to one of endNodeSet
-      return count;
+      return trace;
     }
 
     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
 
     int curMaxDistance = 0;
+    Stack<String> curMaxTrace = (Stack<String>) trace.clone();
+    ;
     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
       HNode inNode = (HNode) iterator.next();
       // traverse more...
@@ -1504,66 +1540,39 @@ public class HierarchyGraph {
         }
       }
 
-      System.out.println("    traverse more to" + inNode + "  before-count=" + count);
-      int dist = recur_computeDistance2(startNode, inNode, endNodeSet, count, combineSet);
-      if (dist > curMaxDistance) {
-        curMaxDistance = dist;
-      }
-    }
-    return curMaxDistance;
-  }
-
-  public int computeDistance2(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
-    System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet);
-    return recur_computeDistance2(startNode, startNode, endNodeSet, 0, 0, combineSet);
-  }
-
-  private int recur_computeDistance2(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
-      int sharedCount, int nonSharedCount, Set<HNode> combineSet) {
+      // Stack<String> newTrace = (Stack<String>) trace.clone();
+      // Stack<String> curTrace =
+      // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
+      // if (curTrace != null) {
+      // return curTrace;
+      // }
 
-    if (!curNode.equals(startNode)) {
-      // do not count the start node
-      if (curNode.isSharedNode()) {
-        sharedCount++;
-      } else {
-        nonSharedCount++;
+      Set<HNode> inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode);
+      Set<HNode> inCurReachToNodeSet = new HashSet<HNode>();
+      for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) {
+        HNode aboveNode = (HNode) iterator2.next();
+        inCurReachToNodeSet.add(getCurrentHNode(aboveNode));
       }
-    }
 
-    if (endNodeSet.contains(curNode)) {
-      // it reaches to one of endNodeSet
-      if (sharedCount > nonSharedCount) {
-        return sharedCount;
-      } else {
-        return nonSharedCount;
-      }
-    }
+      if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) {
+        System.out
+            .println("        traverse to incomingNode=" + inNode + "  before-trace=" + trace);
 
-    Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+        Stack<String> newTrace = (Stack<String>) trace.clone();
+        Stack<String> curTrace =
+            recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
 
-    int curMaxDistance = 0;
-    for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
-      HNode inNode = (HNode) iterator.next();
-      // traverse more...
-
-      if (inNode.isCombinationNode() && combineSet != null) {
-        // check if inNode have the same combination set of the starting node
-        Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
-        if (!inNodeCombineSet.equals(combineSet)) {
-          continue;
+        if (curTrace != null && curTrace.size() > curMaxDistance) {
+          curMaxTrace = curTrace;
+          curMaxDistance = curTrace.size();
         }
+      } else {
+        System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet="
+            + inCurReachToNodeSet);
       }
 
-      System.out.println("    traverse more to" + inNode + "  sC=" + sharedCount + " nC="
-          + nonSharedCount);
-      int dist =
-          recur_computeDistance2(startNode, inNode, endNodeSet, sharedCount, nonSharedCount,
-              combineSet);
-      if (dist > curMaxDistance) {
-        curMaxDistance = dist;
-      }
     }
-    return curMaxDistance;
+    return curMaxTrace;
   }
 
   public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
index fb9d4d5..61a90d0 100644 (file)
@@ -26,6 +26,7 @@ import IR.ClassDescriptor;
 import IR.Descriptor;
 import IR.FieldDescriptor;
 import IR.MethodDescriptor;
+import IR.NameDescriptor;
 import IR.State;
 import IR.SymbolTable;
 import IR.TypeUtil;
@@ -112,6 +113,10 @@ public class SSJavaAnalysis {
 
   private Map<Location, Set<Descriptor>> mapSharedLocToDescSet;
 
+  private Map<Descriptor, SSJavaLattice<String>> mapDescToCompleteLattice;
+  public Map<Descriptor, Integer> mapNumLocsMapManual;
+  public Map<Descriptor, Integer> mapNumPathsMapManual;
+
   public SSJavaAnalysis(State state, TypeUtil tu, BuildFlat bf, CallGraph callgraph) {
     this.state = state;
     this.tu = tu;
@@ -132,6 +137,9 @@ public class SSJavaAnalysis {
     this.sortedDescriptors = new LinkedList<MethodDescriptor>();
     this.md2pcLoc = new HashMap<MethodDescriptor, CompositeLocation>();
     this.mapSharedLocToDescSet = new HashMap<Location, Set<Descriptor>>();
+    this.mapDescToCompleteLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
+    this.mapNumLocsMapManual = new HashMap<Descriptor, Integer>();
+    this.mapNumPathsMapManual = new HashMap<Descriptor, Integer>();
   }
 
   public void doCheck() {
@@ -151,6 +159,8 @@ public class SSJavaAnalysis {
       System.exit(0);
     } else {
       parseLocationAnnotation();
+      debug_countNumLocations();
+      // System.exit(0);
       doFlowDownCheck();
       doDefinitelyWrittenCheck();
       doLoopCheck();
@@ -160,9 +170,113 @@ public class SSJavaAnalysis {
       MethodDescriptor md = (MethodDescriptor) iterator.next();
       MethodLattice<String> locOrder = getMethodLattice(md);
       writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md));
-      // System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t"
-      // + locOrder.getKeySet().size());
+      System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t"
+          + locOrder.getKeySet().size());
+    }
+
+  }
+
+  private void debug_countNumLocations() {
+
+    BuildLattice buildLattice = new BuildLattice();
+
+    for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) {
+      ClassDescriptor cd = (ClassDescriptor) iterator.next();
+      SSJavaLattice<String> lattice = cd2lattice.get(cd).clone();
+      SSJavaLattice<String> completeLattice = debug_buildCompleteLattice(buildLattice, cd, lattice);
+      mapDescToCompleteLattice.put(cd, completeLattice);
+      writeLatticeDotFile(cd, null, completeLattice);
+    }
+
+    for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) {
+      MethodDescriptor md = (MethodDescriptor) iterator.next();
+      SSJavaLattice<String> lattice = md2lattice.get(md).clone();
+      SSJavaLattice<String> completeLattice = debug_buildCompleteLattice(buildLattice, md, lattice);
+      mapDescToCompleteLattice.put(md, completeLattice);
+      writeLatticeDotFile(md.getClassDesc(), md, completeLattice);
+    }
+
+    for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
+      MethodDescriptor md = (MethodDescriptor) iterator.next();
+      SSJavaLattice<String> lattice = getMethodLattice(md).clone();
+      if (!mapDescToCompleteLattice.containsKey(md)) {
+        System.out.println("@NOT FOUND!");
+        SSJavaLattice<String> completeLattice =
+            debug_buildCompleteLattice(buildLattice, md, lattice);
+        mapDescToCompleteLattice.put(md, completeLattice);
+        writeLatticeDotFile(md.getClassDesc(), md, completeLattice);
+      }
+    }
+
+    writeNumLocsPathsCSVFile();
+
+  }
+
+  public SSJavaLattice<String> debug_buildCompleteLattice(BuildLattice buildLattice,
+      Descriptor desc, SSJavaLattice<String> lattice) {
+
+    // First, create a hierarchy graph
+    HierarchyGraph hierarchyGraph = new HierarchyGraph();
+    Set<String> keySet = lattice.getKeySet();
+
+    Map<String, Descriptor> mapLocNameToDesc = new HashMap<String, Descriptor>();
+
+    for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
+      String higher = (String) iterator2.next();
+      Set<String> lowerSet = lattice.get(higher);
+      if (!mapLocNameToDesc.containsKey(higher)) {
+        mapLocNameToDesc.put(higher, new NameDescriptor(higher));
+      }
+
+      Descriptor higherDesc = mapLocNameToDesc.get(higher);
+
+      for (Iterator iterator3 = lowerSet.iterator(); iterator3.hasNext();) {
+        String lower = (String) iterator3.next();
+        if (!mapLocNameToDesc.containsKey(lower)) {
+          mapLocNameToDesc.put(lower, new NameDescriptor(lower));
+        }
+        Descriptor lowerDesc = mapLocNameToDesc.get(lower);
+        hierarchyGraph.addEdge(higherDesc, lowerDesc);
+      }
     }
+
+    BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet<HNode>());
+
+    SSJavaLattice<String> completeLattice = buildLattice.buildLattice(hierarchyGraph);
+
+    int numLocs = completeLattice.getKeySet().size() + 1;
+    LocationInference.numLocationsSInfer += numLocs;
+    mapNumLocsMapManual.put(desc, new Integer(numLocs));
+
+    System.out.println(desc + "::" + "lattice=" + lattice.getKeySet().size() + " complete="
+        + numLocs);
+
+    int numPaths = completeLattice.countPaths();
+    LocationInference.numLocationsSInfer += numPaths;
+    mapNumPathsMapManual.put(desc, new Integer(numPaths));
+
+    return completeLattice;
+  }
+
+  public void writeNumLocsPathsCSVFile() {
+
+    try {
+      BufferedWriter bw = new BufferedWriter(new FileWriter("manualnumbers.csv"));
+
+      Set<Descriptor> keySet = mapNumLocsMapManual.keySet();
+      for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+        Descriptor desc = (Descriptor) iterator.next();
+        int numLocs = mapNumLocsMapManual.get(desc);
+        int numPaths = mapNumPathsMapManual.get(desc);
+        bw.write(desc.getSymbol().replaceAll("[,]", "") + "," + numLocs + "," + numPaths + "\n");
+      }
+      bw.close();
+
+    } catch (IOException e) {
+      // TODO Auto-generated catch block
+      e.printStackTrace();
+    }
+
   }
 
   public void init() {