Robust/src/Analysis/SSJava/SSJavaLattice.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashMap;
   4 import java.util.HashSet;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 import Util.Lattice;
  10
  11 public class SSJavaLattice<T> extends Lattice<T> {
  12
  13   Set<T> sharedLocSet;
  14   public static int seed = 0;
  15
  16   public SSJavaLattice(T top, T bottom) {
  17     super(top, bottom);
  18     sharedLocSet = new HashSet<T>();
  19   }
  20
  21   public void setSharedLocSet(Set<T> in) {
  22     sharedLocSet.addAll(in);
  23   }
  24
  25   public Set<T> getSharedLocSet() {
  26     return sharedLocSet;
  27   }
  28
  29   public void addSharedLoc(T loc) {
  30     sharedLocSet.add(loc);
  31   }
  32
  33   public boolean isSharedLoc(T loc) {
  34     return sharedLocSet.contains(loc);
  35   }
  36
  37   public Set<T> getElementSet() {
  38     Set<T> set = new HashSet<T>();
  39
  40     Set<T> keySet = getKeySet();
  41     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  42       T key = (T) iterator.next();
  43       set.add(key);
  44       set.addAll(getTable().get(key));
  45     }
  46
  47     set.remove(getTopItem());
  48     set.remove(getBottomItem());
  49     return set;
  50   }
  51
  52   public boolean addRelationHigherToLower(T higher, T lower) {
  53
  54     System.out.println("add a relation: " + lower + "<" + higher);
  55
  56     return put(higher, lower);
  57   }
  58
  59   public void insertNewLocationAtOneLevelHigher(T lowerLoc, T newLoc) {
  60     // first identifying which location is connected to the input loc
  61     Set<T> keySet = getKeySet();
  62     Set<T> oneLevelHigherLocSet = new HashSet<T>();
  63
  64     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  65       T locKey = (T) iterator.next();
  66       Set<T> conntectedSet = get(locKey);
  67       for (Iterator iterator2 = conntectedSet.iterator(); iterator2.hasNext();) {
  68         T connectedLoc = (T) iterator2.next();
  69         if (connectedLoc.equals(lowerLoc)) {
  70           oneLevelHigherLocSet.add(locKey);
  71         }
  72       }
  73     }
  74
  75     put(newLoc);
  76     addRelationHigherToLower(newLoc, lowerLoc);
  77
  78     for (Iterator iterator = oneLevelHigherLocSet.iterator(); iterator.hasNext();) {
  79       T higherLoc = (T) iterator.next();
  80       // remove an existing edge between the higher loc and the input loc
  81       get(higherLoc).remove(lowerLoc);
  82       // add a new edge from the higher loc to the new location
  83       put(higherLoc, newLoc);
  84     }
  85
  86   }
  87
  88   public Set<T> getPossibleCycleElements(T higherLoc, T lowerLoc) {
  89     // if a relation of higherloc & lowerloc introduces a new cycle flow,
  90     // return the set of elements consisting of the cycle
  91     Set<T> cycleElemetns = new HashSet<T>();
  92
  93     // if lowerLoc has already been higher than higherLoc, the new relation
  94     // introduces a cycle to the lattice
  95     if (lowerLoc.equals(higherLoc)) {
  96       cycleElemetns.add(lowerLoc);
  97       cycleElemetns.add(higherLoc);
  98     } else if (isGreaterThan(lowerLoc, higherLoc)) {
  99       cycleElemetns.add(lowerLoc);
 100       cycleElemetns.add(higherLoc);
 101       getInBetweenElements(lowerLoc, higherLoc, cycleElemetns);
 102     }
 103     return cycleElemetns;
 104   }
 105
 106   private void getInBetweenElements(T start, T end, Set<T> elementSet) {
 107     Set<T> connectedSet = get(start);
 108     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 109       T cur = (T) iterator.next();
 110       if ((!start.equals(cur)) && (!cur.equals(end)) && isGreaterThan(cur, end)) {
 111         elementSet.add(cur);
 112         getInBetweenElements(cur, end, elementSet);
 113       }
 114     }
 115   }
 116
 117   public void mergeIntoNewLocation(Set<T> cycleSet, T newLoc) {
 118
 119     // add a new loc
 120     put(newLoc);
 121
 122     Set<T> keySet = getKeySet();
 123
 124     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 125       T keyElement = (T) iterator.next();
 126       Set<T> connectedSet = get(keyElement);
 127       Set<T> removeSet = new HashSet<T>();
 128       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 129         T cur = (T) iterator2.next();
 130         if (cycleSet.contains(cur)) {
 131           removeSet.add(cur);
 132         }
 133       }
 134
 135       if (!removeSet.isEmpty()) {
 136         // // remove relations of locationElement -> cycle
 137         connectedSet.removeAll(removeSet);
 138         // add a new relation of location Element -> shared loc
 139         connectedSet.add(newLoc);
 140         getTable().put(keyElement, connectedSet);
 141       }
 142     }
 143
 144     Set<T> newConnectedSet = new HashSet<T>();
 145     for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
 146       T cycleElement = (T) iterator.next();
 147       Set<T> connectedSet = get(cycleElement);
 148       if (connectedSet != null) {
 149         newConnectedSet.addAll(connectedSet);
 150       }
 151       getTable().remove(cycleElement);
 152     }
 153     newConnectedSet.removeAll(cycleSet);
 154     newConnectedSet.remove(newLoc);
 155
 156     Set<T> set = getTable().get(newLoc);
 157     set.addAll(newConnectedSet);
 158
 159     // clean up lattice
 160     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 161       T keyElement = (T) iterator.next();
 162       get(keyElement).removeAll(cycleSet);
 163     }
 164
 165     for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
 166       T cycleElement = (T) iterator.next();
 167       getTable().remove(cycleElement);
 168     }
 169
 170   }
 171
 172   public void remove(T loc) {
 173
 174     Set<T> keySet = getKeySet();
 175
 176     Set<T> inSet = new HashSet<T>();
 177     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 178       T keyElement = (T) iterator.next();
 179       Set<T> connectedSet = get(keyElement);
 180       if (connectedSet.contains(loc)) {
 181         inSet.add(loc);
 182         connectedSet.remove(loc);
 183       }
 184     }
 185
 186     Set<T> outSet = get(loc);
 187
 188     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 189       T in = (T) iterator.next();
 190       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 191         T out = (T) iterator2.next();
 192         put(in, out);
 193       }
 194     }
 195
 196     getTable().remove(loc);
 197
 198   }
 199
 200   public void substituteLocation(T oldLoc, T newLoc) {
 201     // the new location is going to take all relations of the old location
 202     if (!getKeySet().contains(newLoc)) {
 203       put(newLoc);
 204     }
 205
 206     // consider the set of location s.t. LOC is greater than oldLoc
 207     Set<T> keySet = getKeySet();
 208     Set<T> directedConnctedHigherLocSet = new HashSet<T>();
 209
 210     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 211       T key = (T) iterator.next();
 212       Set<T> connectedSet = getTable().get(key);
 213       if (connectedSet.contains(oldLoc)) {
 214         directedConnctedHigherLocSet.add(key);
 215       }
 216     }
 217
 218     Set<T> connctedLowerSet = getTable().get(oldLoc);
 219     Set<T> directedConnctedLowerLocSet = new HashSet<T>();
 220     if (connctedLowerSet != null) {
 221       directedConnctedLowerLocSet.addAll(connctedLowerSet);
 222     }
 223
 224     for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) {
 225       T higher = (T) iterator.next();
 226       if (!higher.equals(newLoc)) {
 227         addRelationHigherToLower(higher, newLoc);
 228       }
 229     }
 230
 231     for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) {
 232       T lower = (T) iterator.next();
 233       if (!lower.equals(newLoc)) {
 234         addRelationHigherToLower(newLoc, lower);
 235       }
 236     }
 237
 238     getTable().remove(oldLoc);
 239
 240     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 241       T key = (T) iterator.next();
 242       getTable().get(key).remove(oldLoc);
 243     }
 244
 245   }
 246
 247   public void removeRedundantEdges() {
 248
 249     Set<T> keySet = getTable().keySet();
 250
 251     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 252       T src = (T) iterator.next();
 253       Set<T> connectedSet = getTable().get(src);
 254       Set<T> toberemovedSet = new HashSet<T>();
 255       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 256         T dst = (T) iterator2.next();
 257         Set<T> otherNeighborSet = new HashSet<T>();
 258         otherNeighborSet.addAll(connectedSet);
 259         otherNeighborSet.remove(dst);
 260         for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 261           T neighbor = (T) iterator3.next();
 262           if (isReachable(neighbor, new HashSet<T>(), dst)) {
 263             toberemovedSet.add(dst);
 264           }
 265         }
 266       }
 267       if (toberemovedSet.size() > 0) {
 268         connectedSet.removeAll(toberemovedSet);
 269       }
 270     }
 271
 272   }
 273
 274   private boolean isReachable(T neighbor, Set<T> visited, T dst) {
 275     Set<T> connectedSet = getTable().get(neighbor);
 276     if (connectedSet != null) {
 277       for (Iterator<T> iterator = connectedSet.iterator(); iterator.hasNext();) {
 278         T n = iterator.next();
 279         if (n.equals(dst)) {
 280           return true;
 281         }
 282         if (!visited.contains(n)) {
 283           visited.add(n);
 284           if (isReachable(n, visited, dst)) {
 285             return true;
 286           }
 287         }
 288       }
 289     }
 290     return false;
 291   }
 292
 293   public Map<T, Set<T>> getIncomingElementMap() {
 294     Map<T, Set<T>> map = new HashMap<T, Set<T>>();
 295
 296     Set<T> keySet = getKeySet();
 297     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 298       T key = (T) iterator.next();
 299
 300       Set<T> incomingSet = new HashSet<T>();
 301
 302       for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
 303         T in = (T) iterator2.next();
 304         if (!in.equals(key) && get(in).contains(key)) {
 305           incomingSet.add(in);
 306         }
 307       }
 308       map.put(key, incomingSet);
 309     }
 310
 311     return map;
 312   }
 313
 314   public void insertNewLocationBetween(T higher, T lower, T newLoc) {
 315     Set<T> connectedSet = get(higher);
 316     connectedSet.remove(lower);
 317     connectedSet.add(newLoc);
 318
 319     put(newLoc, lower);
 320   }
 321
 322   public void insertNewLocationBetween(T higher, Set<T> lowerSet, T newLoc) {
 323     // System.out.println("---insert new location=" + newLoc + "   between=" + higher + "<->"
 324     // + lowerSet);
 325     Set<T> connectedSet = get(higher);
 326     if (connectedSet == null) {
 327       connectedSet = new HashSet<T>();
 328     } else {
 329       connectedSet.removeAll(lowerSet);
 330     }
 331     connectedSet.add(newLoc);
 332
 333     for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 334       T lower = (T) iterator.next();
 335       put(newLoc, lower);
 336     }
 337   }
 338
 339   public SSJavaLattice<T> clone() {
 340
 341     SSJavaLattice<T> clone = new SSJavaLattice<T>(getTopItem(), getBottomItem());
 342     clone.setTable(getTable());
 343     clone.setSharedLocSet(getSharedLocSet());
 344     return clone;
 345   }
 346
 347   public int countPaths() {
 348     T bottom = getBottomItem();
 349
 350     Map<T, Set<T>> map = getIncomingElementMap();
 351     Map<T, Integer> countMap = new HashMap<T, Integer>();
 352
 353     Set<T> visited = new HashSet<T>();
 354     visited.add(bottom);
 355
 356     countMap.put(bottom, new Integer(1));
 357     recur_countPaths(bottom, map, countMap, visited);
 358     if (countMap.containsKey(getTopItem())) {
 359       return countMap.get(getTopItem());
 360     }
 361     return 0;
 362   }
 363
 364   private void recur_countPaths(T cur, Map<T, Set<T>> map, Map<T, Integer> countMap, Set<T> visited) {
 365     int curCount = countMap.get(cur).intValue();
 366     Set<T> inSet = map.get(cur);
 367
 368     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 369       T in = (T) iterator.next();
 370       int inCount = 0;
 371       if (countMap.containsKey(in)) {
 372         inCount = countMap.get(in).intValue();
 373       }
 374       inCount += curCount;
 375       countMap.put(in, inCount);
 376       if (visited.containsAll(get(in))) {
 377         visited.add(in);
 378         recur_countPaths(in, map, countMap, visited);
 379       }
 380     }
 381   }
 382 }