1 package Analysis.SSJava;
3 import java.util.HashMap;
4 import java.util.HashSet;
5 import java.util.Iterator;
11 public class SSJavaLattice<T> extends Lattice<T> {
14 public static int seed = 0;
16 public SSJavaLattice(T top, T bottom) {
18 sharedLocSet = new HashSet<T>();
21 public void setSharedLocSet(Set<T> in) {
22 sharedLocSet.addAll(in);
25 public Set<T> getSharedLocSet() {
29 public void addSharedLoc(T loc) {
30 sharedLocSet.add(loc);
33 public boolean isSharedLoc(T loc) {
34 return sharedLocSet.contains(loc);
37 public Set<T> getElementSet() {
38 Set<T> set = new HashSet<T>();
40 Set<T> keySet = getKeySet();
41 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
42 T key = (T) iterator.next();
44 set.addAll(getTable().get(key));
47 set.remove(getTopItem());
48 set.remove(getBottomItem());
52 public boolean addRelationHigherToLower(T higher, T lower) {
54 System.out.println("add a relation: " + lower + "<" + higher);
56 return put(higher, lower);
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>();
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);
76 addRelationHigherToLower(newLoc, lowerLoc);
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);
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>();
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);
103 return cycleElemetns;
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)) {
112 getInBetweenElements(cur, end, elementSet);
117 public void mergeIntoNewLocation(Set<T> cycleSet, T newLoc) {
122 Set<T> keySet = getKeySet();
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)) {
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);
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);
151 getTable().remove(cycleElement);
153 newConnectedSet.removeAll(cycleSet);
154 newConnectedSet.remove(newLoc);
156 Set<T> set = getTable().get(newLoc);
157 set.addAll(newConnectedSet);
160 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
161 T keyElement = (T) iterator.next();
162 get(keyElement).removeAll(cycleSet);
165 for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
166 T cycleElement = (T) iterator.next();
167 getTable().remove(cycleElement);
172 public void remove(T loc) {
174 Set<T> keySet = getKeySet();
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)) {
182 connectedSet.remove(loc);
186 Set<T> outSet = get(loc);
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();
196 getTable().remove(loc);
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)) {
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>();
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);
218 Set<T> connctedLowerSet = getTable().get(oldLoc);
219 Set<T> directedConnctedLowerLocSet = new HashSet<T>();
220 if (connctedLowerSet != null) {
221 directedConnctedLowerLocSet.addAll(connctedLowerSet);
224 for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) {
225 T higher = (T) iterator.next();
226 if (!higher.equals(newLoc)) {
227 addRelationHigherToLower(higher, newLoc);
231 for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) {
232 T lower = (T) iterator.next();
233 if (!lower.equals(newLoc)) {
234 addRelationHigherToLower(newLoc, lower);
238 getTable().remove(oldLoc);
240 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
241 T key = (T) iterator.next();
242 getTable().get(key).remove(oldLoc);
247 public void removeRedundantEdges() {
249 Set<T> keySet = getTable().keySet();
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);
267 if (toberemovedSet.size() > 0) {
268 connectedSet.removeAll(toberemovedSet);
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();
282 if (!visited.contains(n)) {
284 if (isReachable(n, visited, dst)) {
293 public Map<T, Set<T>> getIncomingElementMap() {
294 Map<T, Set<T>> map = new HashMap<T, Set<T>>();
296 Set<T> keySet = getKeySet();
297 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
298 T key = (T) iterator.next();
300 Set<T> incomingSet = new HashSet<T>();
302 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
303 T in = (T) iterator2.next();
304 if (!in.equals(key) && get(in).contains(key)) {
308 map.put(key, incomingSet);
314 public void insertNewLocationBetween(T higher, T lower, T newLoc) {
315 Set<T> connectedSet = get(higher);
316 connectedSet.remove(lower);
317 connectedSet.add(newLoc);
322 public void insertNewLocationBetween(T higher, Set<T> lowerSet, T newLoc) {
323 // System.out.println("---insert new location=" + newLoc + " between=" + higher + "<->"
325 Set<T> connectedSet = get(higher);
326 if (connectedSet == null) {
327 connectedSet = new HashSet<T>();
329 connectedSet.removeAll(lowerSet);
331 connectedSet.add(newLoc);
333 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
334 T lower = (T) iterator.next();
339 public SSJavaLattice<T> clone() {
341 SSJavaLattice<T> clone = new SSJavaLattice<T>(getTopItem(), getBottomItem());
342 clone.setTable(getTable());
343 clone.setSharedLocSet(getSharedLocSet());