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 Set<T> getElementSet(){
32 Set<T> set=new HashSet<T>();
34 Set<T> keySet=getKeySet();
35 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
36 T key = (T) iterator.next();
38 set.addAll(getTable().get(key));
41 set.remove(getTopItem());
42 set.remove(getBottomItem());
46 public boolean addRelationHigherToLower(T higher, T lower) {
48 System.out.println("add a relation: " + lower + "<" + higher);
50 return put(higher, lower);
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>();
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);
70 addRelationHigherToLower(newLoc, lowerLoc);
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);
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>();
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);
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)) {
106 getInBetweenElements(cur, end, elementSet);
111 public void mergeIntoSharedLocation(Set<T> cycleSet, T newLoc) {
113 // add a new shared loc
115 addSharedLoc(newLoc);
117 Set<T> keySet = getKeySet();
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)) {
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);
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);
146 getTable().remove(cycleElement);
148 newConnectedSet.removeAll(cycleSet);
149 newConnectedSet.remove(newLoc);
151 Set<T> set = getTable().get(newLoc);
152 set.addAll(newConnectedSet);
155 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
156 T keyElement = (T) iterator.next();
157 get(keyElement).removeAll(cycleSet);
160 for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) {
161 T cycleElement = (T) iterator.next();
162 getTable().remove(cycleElement);
167 public void remove(T loc) {
169 Set<T> keySet = getKeySet();
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)) {
177 connectedSet.remove(loc);
181 Set<T> outSet = get(loc);
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();
191 getTable().remove(loc);
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)) {
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>();
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);
213 Set<T> connctedLowerSet = getTable().get(oldLoc);
214 Set<T> directedConnctedLowerLocSet = new HashSet<T>();
215 if (connctedLowerSet != null) {
216 directedConnctedLowerLocSet.addAll(connctedLowerSet);
219 for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) {
220 T higher = (T) iterator.next();
221 if (!higher.equals(newLoc)) {
222 addRelationHigherToLower(higher, newLoc);
226 for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) {
227 T lower = (T) iterator.next();
228 if (!lower.equals(newLoc)) {
229 addRelationHigherToLower(newLoc, lower);
233 getTable().remove(oldLoc);
235 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
236 T key = (T) iterator.next();
237 getTable().get(key).remove(oldLoc);
242 public void removeRedundantEdges() {
245 isUpdated = recurRemoveRedundant();
249 public boolean recurRemoveRedundant() {
251 Set<T> keySet = getKeySet();
252 Set<T> visited = new HashSet<T>();
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);
271 if (toberemovedSet.size() > 0) {
272 connectedSet.removeAll(toberemovedSet);
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();
290 if (!visited.contains(n)) {
292 if (isReachable(n, visited, dst)) {