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