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