X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FSSJavaLattice.java;h=4343f2de3576345407918939954d5dd4da8a08f9;hb=d421edc382984588192603ed519923beadeb4d3a;hp=d30aa3998cd1775afd96c6b08393fd01d2c2de49;hpb=dfaefc442488f69bf9f33038ddafb7ff47a67d8d;p=IRC.git

diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java
index d30aa399..4343f2de 100644
--- 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;
@@ -28,6 +30,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 +110,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();
 
@@ -111,8 +127,9 @@ public class SSJavaLattice<T> extends Lattice<T> {
           removeSet.add(cur);
         }
       }
+
       if (!removeSet.isEmpty()) {
-        // remove relations of locationElement -> cycle
+        // // remove relations of locationElement -> cycle
         connectedSet.removeAll(removeSet);
         // add a new relation of location Element -> shared loc
         connectedSet.add(newLoc);
@@ -135,10 +152,52 @@ public class SSJavaLattice<T> extends Lattice<T> {
     Set<T> set = getTable().get(newLoc);
     set.addAll(newConnectedSet);
 
+    // clean up lattice
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T keyElement = (T) iterator.next();
+      get(keyElement).removeAll(cycleSet);
+    }
+
+    for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
+      T cycleElement = (T) iterator.next();
+      getTable().remove(cycleElement);
+    }
+
+  }
+
+  public void remove(T loc) {
+
+    Set<T> keySet = getKeySet();
+
+    Set<T> inSet = new HashSet<T>();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T keyElement = (T) iterator.next();
+      Set<T> connectedSet = get(keyElement);
+      if (connectedSet.contains(loc)) {
+        inSet.add(loc);
+        connectedSet.remove(loc);
+      }
+    }
+
+    Set<T> outSet = get(loc);
+
+    for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
+      T in = (T) iterator.next();
+      for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
+        T out = (T) iterator2.next();
+        put(in, out);
+      }
+    }
+
+    getTable().remove(loc);
+
   }
 
   public void substituteLocation(T oldLoc, T newLoc) {
     // the new location is going to take all relations of the old location
+    if (!getKeySet().contains(newLoc)) {
+      put(newLoc);
+    }
 
     // consider the set of location s.t. LOC is greater than oldLoc
     Set<T> keySet = getKeySet();
@@ -172,6 +231,92 @@ public class SSJavaLattice<T> extends Lattice<T> {
       }
     }
 
+    getTable().remove(oldLoc);
+
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T key = (T) iterator.next();
+      getTable().get(key).remove(oldLoc);
+    }
+
+  }
+
+  public void removeRedundantEdges() {
+    boolean isUpdated;
+    do {
+      isUpdated = recurRemoveRedundant();
+    } while (isUpdated);
+  }
+
+  public boolean recurRemoveRedundant() {
+
+    Set<T> keySet = getKeySet();
+    Set<T> visited = new HashSet<T>();
+
+    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);
+            }
+          }
+        }
+        if (toberemovedSet.size() > 0) {
+          connectedSet.removeAll(toberemovedSet);
+          return true;
+        }
+      }
+    }
+
+    return false;
+
   }
 
+  private boolean isReachable(T neighbor, Set<T> visited, T dst) {
+    Set<T> connectedSet = getTable().get(neighbor);
+    if (connectedSet != null) {
+      for (Iterator<T> iterator = connectedSet.iterator(); iterator.hasNext();) {
+        T n = iterator.next();
+        if (n.equals(dst)) {
+          return true;
+        }
+        if (!visited.contains(n)) {
+          visited.add(n);
+          if (isReachable(n, visited, dst)) {
+            return true;
+          }
+        }
+      }
+    }
+    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;
+  }
 }