all fixed...

[IRC.git] / Robust / src / Analysis / SSJava / SSJavaLattice.java

diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java
index e2c85f299c768dc678e7307992767f4abcc92a20..406b72eca8c2671f0f1e326d4c72039819976848 100644 (file)
--- a/Robust/src/Analysis/SSJava/SSJavaLattice.java
+++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java
@@ -1,7 +1,9 @@
 package Analysis.SSJava;
 
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.Map;
 import java.util.Set;
 
 import Util.Lattice;
@@ -16,6 +18,10 @@ public class SSJavaLattice<T> extends Lattice<T> {
     sharedLocSet = new HashSet<T>();
   }
 
+  public void setSharedLocSet(Set<T> in) {
+    sharedLocSet.addAll(in);
+  }
+
   public Set<T> getSharedLocSet() {
     return sharedLocSet;
   }
@@ -28,6 +34,21 @@ public class SSJavaLattice<T> extends Lattice<T> {
     return sharedLocSet.contains(loc);
   }
 
+  public Set<T> getElementSet() {
+    Set<T> set = new HashSet<T>();
+
+    Set<T> keySet = getKeySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T key = (T) iterator.next();
+      set.add(key);
+      set.addAll(getTable().get(key));
+    }
+
+    set.remove(getTopItem());
+    set.remove(getBottomItem());
+    return set;
+  }
+
   public boolean addRelationHigherToLower(T higher, T lower) {
 
     System.out.println("add a relation: " + lower + "<" + higher);
@@ -93,11 +114,10 @@ public class SSJavaLattice<T> extends Lattice<T> {
     }
   }
 
-  public void mergeIntoSharedLocation(Set<T> cycleSet, T newLoc) {
+  public void mergeIntoNewLocation(Set<T> cycleSet, T newLoc) {
 
-    // add a new shared loc
+    // add a new loc
     put(newLoc);
-    addSharedLoc(newLoc);
 
     Set<T> keySet = getKeySet();
 
@@ -225,43 +245,30 @@ public class SSJavaLattice<T> extends Lattice<T> {
   }
 
   public void removeRedundantEdges() {
-    boolean isUpdated;
-    do {
-      isUpdated = recurRemoveRedundant();
-    } while (isUpdated);
-  }
-
-  public boolean recurRemoveRedundant() {
 
-    Set<T> keySet = getKeySet();
-    Set<T> visited = new HashSet<T>();
+    Set<T> keySet = getTable().keySet();
 
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
-      T key = (T) iterator.next();
-      Set<T> connectedSet = getTable().get(key);
-      if (connectedSet != null) {
-        Set<T> toberemovedSet = new HashSet<T>();
-        for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
-          T dst = (T) iterator2.next();
-          Set<T> otherNeighborSet = new HashSet<T>();
-          otherNeighborSet.addAll(connectedSet);
-          otherNeighborSet.remove(dst);
-          for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
-            T neighbor = (T) iterator3.next();
-            if (isReachable(neighbor, visited, dst)) {
-              toberemovedSet.add(dst);
-            }
+      T src = (T) iterator.next();
+      Set<T> connectedSet = getTable().get(src);
+      Set<T> toberemovedSet = new HashSet<T>();
+      for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
+        T dst = (T) iterator2.next();
+        Set<T> otherNeighborSet = new HashSet<T>();
+        otherNeighborSet.addAll(connectedSet);
+        otherNeighborSet.remove(dst);
+        for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
+          T neighbor = (T) iterator3.next();
+          if (isReachable(neighbor, new HashSet<T>(), dst)) {
+            toberemovedSet.add(dst);
           }
         }
-        if (toberemovedSet.size() > 0) {
-          connectedSet.removeAll(toberemovedSet);
-          return true;
-        }
+      }
+      if (toberemovedSet.size() > 0) {
+        connectedSet.removeAll(toberemovedSet);
       }
     }
 
-    return false;
-
   }
 
   private boolean isReachable(T neighbor, Set<T> visited, T dst) {
@@ -282,4 +289,94 @@ public class SSJavaLattice<T> extends Lattice<T> {
     }
     return false;
   }
+
+  public Map<T, Set<T>> getIncomingElementMap() {
+    Map<T, Set<T>> map = new HashMap<T, Set<T>>();
+
+    Set<T> keySet = getKeySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T key = (T) iterator.next();
+
+      Set<T> incomingSet = new HashSet<T>();
+
+      for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
+        T in = (T) iterator2.next();
+        if (!in.equals(key) && get(in).contains(key)) {
+          incomingSet.add(in);
+        }
+      }
+      map.put(key, incomingSet);
+    }
+
+    return map;
+  }
+
+  public void insertNewLocationBetween(T higher, T lower, T newLoc) {
+    Set<T> connectedSet = get(higher);
+    connectedSet.remove(lower);
+    connectedSet.add(newLoc);
+
+    put(newLoc, lower);
+  }
+
+  public void insertNewLocationBetween(T higher, Set<T> lowerSet, T newLoc) {
+    // System.out.println("---insert new location=" + newLoc + "   between=" + higher + "<->"
+    // + lowerSet);
+    Set<T> connectedSet = get(higher);
+    if (connectedSet == null) {
+      connectedSet = new HashSet<T>();
+    } else {
+      connectedSet.removeAll(lowerSet);
+    }
+    connectedSet.add(newLoc);
+
+    for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
+      T lower = (T) iterator.next();
+      put(newLoc, lower);
+    }
+  }
+
+  public SSJavaLattice<T> clone() {
+
+    SSJavaLattice<T> clone = new SSJavaLattice<T>(getTopItem(), getBottomItem());
+    clone.setTable(getTable());
+    clone.setSharedLocSet(getSharedLocSet());
+    return clone;
+  }
+
+  public int countPaths() {
+    T bottom = getBottomItem();
+
+    Map<T, Set<T>> map = getIncomingElementMap();
+    Map<T, Integer> countMap = new HashMap<T, Integer>();
+
+    Set<T> visited = new HashSet<T>();
+    visited.add(bottom);
+
+    countMap.put(bottom, new Integer(1));
+    recur_countPaths(bottom, map, countMap, visited);
+    if (countMap.containsKey(getTopItem())) {
+      return countMap.get(getTopItem());
+    }
+    return 0;
+  }
+
+  private void recur_countPaths(T cur, Map<T, Set<T>> map, Map<T, Integer> countMap, Set<T> visited) {
+    int curCount = countMap.get(cur).intValue();
+    Set<T> inSet = map.get(cur);
+
+    for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
+      T in = (T) iterator.next();
+      int inCount = 0;
+      if (countMap.containsKey(in)) {
+        inCount = countMap.get(in).intValue();
+      }
+      inCount += curCount;
+      countMap.put(in, inCount);
+      if (visited.containsAll(get(in))) {
+        visited.add(in);
+        recur_countPaths(in, map, countMap, visited);
+      }
+    }
+  }
 }