Robust/src/Analysis/SSJava/SSJavaLattice.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Iterator;
   5 import java.util.Set;
   6
   7 import Util.Lattice;
   8
   9 public class SSJavaLattice<T> extends Lattice<T> {
  10
  11   Set<T> sharedLocSet;
  12   public static int seed = 0;
  13
  14   public SSJavaLattice(T top, T bottom) {
  15     super(top, bottom);
  16     sharedLocSet = new HashSet<T>();
  17   }
  18
  19   public Set<T> getSharedLocSet() {
  20     return sharedLocSet;
  21   }
  22
  23   public void addSharedLoc(T loc) {
  24     sharedLocSet.add(loc);
  25   }
  26
  27   public boolean isSharedLoc(T loc) {
  28     return sharedLocSet.contains(loc);
  29   }
  30
  31   public boolean addRelationHigherToLower(T higher, T lower) {
  32
  33     System.out.println("add a relation: " + lower + "<" + higher);
  34
  35     return put(higher, lower);
  36   }
  37
  38   public void insertNewLocationAtOneLevelHigher(T lowerLoc, T newLoc) {
  39     // first identifying which location is connected to the input loc
  40     Set<T> keySet = getKeySet();
  41     Set<T> oneLevelHigherLocSet = new HashSet<T>();
  42
  43     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  44       T locKey = (T) iterator.next();
  45       Set<T> conntectedSet = get(locKey);
  46       for (Iterator iterator2 = conntectedSet.iterator(); iterator2.hasNext();) {
  47         T connectedLoc = (T) iterator2.next();
  48         if (connectedLoc.equals(lowerLoc)) {
  49           oneLevelHigherLocSet.add(locKey);
  50         }
  51       }
  52     }
  53
  54     put(newLoc);
  55     addRelationHigherToLower(newLoc, lowerLoc);
  56
  57     for (Iterator iterator = oneLevelHigherLocSet.iterator(); iterator.hasNext();) {
  58       T higherLoc = (T) iterator.next();
  59       // remove an existing edge between the higher loc and the input loc
  60       get(higherLoc).remove(lowerLoc);
  61       // add a new edge from the higher loc to the new location
  62       put(higherLoc, newLoc);
  63     }
  64
  65   }
  66
  67   public Set<T> getPossibleCycleElements(T higherLoc, T lowerLoc) {
  68     // if a relation of higherloc & lowerloc introduces a new cycle flow,
  69     // return the set of elements consisting of the cycle
  70     Set<T> cycleElemetns = new HashSet<T>();
  71
  72     // if lowerLoc has already been higher than higherLoc, the new relation
  73     // introduces a cycle to the lattice
  74     if (lowerLoc.equals(higherLoc)) {
  75       cycleElemetns.add(lowerLoc);
  76       cycleElemetns.add(higherLoc);
  77     } else if (isGreaterThan(lowerLoc, higherLoc)) {
  78       cycleElemetns.add(lowerLoc);
  79       cycleElemetns.add(higherLoc);
  80       getInBetweenElements(lowerLoc, higherLoc, cycleElemetns);
  81     }
  82     return cycleElemetns;
  83   }
  84
  85   private void getInBetweenElements(T start, T end, Set<T> elementSet) {
  86     Set<T> connectedSet = get(start);
  87     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
  88       T cur = (T) iterator.next();
  89       if ((!start.equals(cur)) && (!cur.equals(end)) && isGreaterThan(cur, end)) {
  90         elementSet.add(cur);
  91         getInBetweenElements(cur, end, elementSet);
  92       }
  93     }
  94     System.out.println("            start=" + start + " end=" + end + "   element=" + elementSet);
  95   }
  96
  97   public void mergeIntoSharedLocation(Set<T> cycleSet, T newLoc) {
  98
  99     // add a new shared loc
 100     put(newLoc);
 101     addSharedLoc(newLoc);
 102
 103     Set<T> keySet = getKeySet();
 104
 105     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 106       T keyElement = (T) iterator.next();
 107       Set<T> connectedSet = get(keyElement);
 108       Set<T> removeSet = new HashSet<T>();
 109       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 110         T cur = (T) iterator2.next();
 111         if (cycleSet.contains(cur)) {
 112           removeSet.add(cur);
 113         }
 114       }
 115
 116       if (!removeSet.isEmpty()) {
 117         // // remove relations of locationElement -> cycle
 118         connectedSet.removeAll(removeSet);
 119         // add a new relation of location Element -> shared loc
 120         connectedSet.add(newLoc);
 121         getTable().put(keyElement, connectedSet);
 122       }
 123     }
 124
 125     Set<T> newConnectedSet = new HashSet<T>();
 126     for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
 127       T cycleElement = (T) iterator.next();
 128       Set<T> connectedSet = get(cycleElement);
 129       if (connectedSet != null) {
 130         newConnectedSet.addAll(connectedSet);
 131       }
 132       getTable().remove(cycleElement);
 133     }
 134     newConnectedSet.removeAll(cycleSet);
 135     newConnectedSet.remove(newLoc);
 136
 137     Set<T> set = getTable().get(newLoc);
 138     set.addAll(newConnectedSet);
 139
 140     // clean up lattice
 141     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 142       T keyElement = (T) iterator.next();
 143       get(keyElement).removeAll(cycleSet);
 144     }
 145
 146     for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
 147       T cycleElement = (T) iterator.next();
 148       getTable().remove(cycleElement);
 149     }
 150
 151   }
 152
 153   public void remove(T loc) {
 154
 155     Set<T> keySet = getKeySet();
 156
 157     Set<T> inSet = new HashSet<T>();
 158     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 159       T keyElement = (T) iterator.next();
 160       Set<T> connectedSet = get(keyElement);
 161       if (connectedSet.contains(loc)) {
 162         inSet.add(loc);
 163         connectedSet.remove(loc);
 164       }
 165     }
 166
 167     Set<T> outSet = get(loc);
 168
 169     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 170       T in = (T) iterator.next();
 171       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 172         T out = (T) iterator2.next();
 173         put(in, out);
 174       }
 175     }
 176
 177     getTable().remove(loc);
 178
 179   }
 180
 181   public void substituteLocation(T oldLoc, T newLoc) {
 182     // the new location is going to take all relations of the old location
 183     if (!getKeySet().contains(newLoc)) {
 184       put(newLoc);
 185     }
 186
 187     // consider the set of location s.t. LOC is greater than oldLoc
 188     Set<T> keySet = getKeySet();
 189     Set<T> directedConnctedHigherLocSet = new HashSet<T>();
 190
 191     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 192       T key = (T) iterator.next();
 193       Set<T> connectedSet = getTable().get(key);
 194       if (connectedSet.contains(oldLoc)) {
 195         directedConnctedHigherLocSet.add(key);
 196       }
 197     }
 198
 199     Set<T> connctedLowerSet = getTable().get(oldLoc);
 200     Set<T> directedConnctedLowerLocSet = new HashSet<T>();
 201     if (connctedLowerSet != null) {
 202       directedConnctedLowerLocSet.addAll(connctedLowerSet);
 203     }
 204
 205     for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) {
 206       T higher = (T) iterator.next();
 207       if (!higher.equals(newLoc)) {
 208         addRelationHigherToLower(higher, newLoc);
 209       }
 210     }
 211
 212     for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) {
 213       T lower = (T) iterator.next();
 214       if (!lower.equals(newLoc)) {
 215         addRelationHigherToLower(newLoc, lower);
 216       }
 217     }
 218
 219     getTable().remove(oldLoc);
 220
 221     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 222       T key = (T) iterator.next();
 223       getTable().get(key).remove(oldLoc);
 224     }
 225
 226   }
 227
 228   public void removeRedundantEdges() {
 229     boolean isUpdated;
 230     do {
 231       isUpdated = recurRemoveRedundant();
 232     } while (isUpdated);
 233   }
 234
 235   public boolean recurRemoveRedundant() {
 236
 237     Set<T> keySet = getKeySet();
 238     Set<T> visited = new HashSet<T>();
 239
 240     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 241       T key = (T) iterator.next();
 242       Set<T> connectedSet = getTable().get(key);
 243       if (connectedSet != null) {
 244         Set<T> toberemovedSet = new HashSet<T>();
 245         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 246           T dst = (T) iterator2.next();
 247           Set<T> otherNeighborSet = new HashSet<T>();
 248           otherNeighborSet.addAll(connectedSet);
 249           otherNeighborSet.remove(dst);
 250           for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 251             T neighbor = (T) iterator3.next();
 252             if (isReachable(neighbor, visited, dst)) {
 253               toberemovedSet.add(dst);
 254             }
 255           }
 256         }
 257         if (toberemovedSet.size() > 0) {
 258           connectedSet.removeAll(toberemovedSet);
 259           return true;
 260         }
 261       }
 262     }
 263
 264     return false;
 265
 266   }
 267
 268   private boolean isReachable(T neighbor, Set<T> visited, T dst) {
 269     Set<T> connectedSet = getTable().get(neighbor);
 270     if (connectedSet != null) {
 271       for (Iterator<T> iterator = connectedSet.iterator(); iterator.hasNext();) {
 272         T n = iterator.next();
 273         if (n.equals(dst)) {
 274           return true;
 275         }
 276         if (!visited.contains(n)) {
 277           visited.add(n);
 278           if (isReachable(n, visited, dst)) {
 279             return true;
 280           }
 281         }
 282       }
 283     }
 284     return false;
 285   }
 286 }