1 package Analysis.SSJava;
3 import java.util.HashSet;
4 import java.util.Iterator;
9 public class SSJavaLattice<T> extends Lattice<T> {
12 public static int seed = 0;
14 public SSJavaLattice(T top, T bottom) {
16 sharedLocSet = new HashSet<T>();
19 public Set<T> getSharedLocSet() {
23 public void addSharedLoc(T loc) {
24 sharedLocSet.add(loc);
27 public boolean isSharedLoc(T loc) {
28 return sharedLocSet.contains(loc);
31 public boolean addRelationHigherToLower(T higher, T lower) {
33 System.out.println("add a relation: " + lower + "<" + higher);
35 return put(higher, lower);
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>();
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);
55 addRelationHigherToLower(newLoc, lowerLoc);
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);
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>();
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);
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)) {
91 getInBetweenElements(cur, end, elementSet);
94 System.out.println(" start=" + start + " end=" + end + " element=" + elementSet);
97 public void mergeIntoSharedLocation(Set<T> cycleSet, T newLoc) {
99 // add a new shared loc
101 addSharedLoc(newLoc);
103 Set<T> keySet = getKeySet();
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)) {
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);
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);
132 getTable().remove(cycleElement);
134 newConnectedSet.removeAll(cycleSet);
135 newConnectedSet.remove(newLoc);
137 Set<T> set = getTable().get(newLoc);
138 set.addAll(newConnectedSet);
141 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
142 T keyElement = (T) iterator.next();
143 get(keyElement).removeAll(cycleSet);
146 for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
147 T cycleElement = (T) iterator.next();
148 getTable().remove(cycleElement);
153 public void remove(T loc) {
155 Set<T> keySet = getKeySet();
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)) {
163 connectedSet.remove(loc);
167 Set<T> outSet = get(loc);
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();
177 getTable().remove(loc);
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)) {
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>();
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);
199 Set<T> connctedLowerSet = getTable().get(oldLoc);
200 Set<T> directedConnctedLowerLocSet = new HashSet<T>();
201 if (connctedLowerSet != null) {
202 directedConnctedLowerLocSet.addAll(connctedLowerSet);
205 for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) {
206 T higher = (T) iterator.next();
207 if (!higher.equals(newLoc)) {
208 addRelationHigherToLower(higher, newLoc);
212 for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) {
213 T lower = (T) iterator.next();
214 if (!lower.equals(newLoc)) {
215 addRelationHigherToLower(newLoc, lower);
219 getTable().remove(oldLoc);
221 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
222 T key = (T) iterator.next();
223 getTable().get(key).remove(oldLoc);
228 public void removeRedundantEdges() {
231 isUpdated = recurRemoveRedundant();
235 public boolean recurRemoveRedundant() {
237 Set<T> keySet = getKeySet();
238 Set<T> visited = new HashSet<T>();
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);
257 if (toberemovedSet.size() > 0) {
258 connectedSet.removeAll(toberemovedSet);
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();
276 if (!visited.contains(n)) {
278 if (isReachable(n, visited, dst)) {