1 package Analysis.SSJava;
3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
8 import Analysis.Loops.LoopFinder;
9 import Analysis.Loops.Loops;
10 import IR.ClassDescriptor;
11 import IR.FieldDescriptor;
12 import IR.MethodDescriptor;
15 import IR.SymbolTable;
17 import IR.Flat.FlatFieldNode;
18 import IR.Flat.FlatLiteralNode;
19 import IR.Flat.FlatMethod;
20 import IR.Flat.FlatNode;
21 import IR.Flat.FlatOpNode;
22 import IR.Flat.TempDescriptor;
24 public class DefinitelyWrittenCheck {
29 // maintains analysis results in the form of <tempDesc,<read statement,flag>>
30 private Hashtable<FlatNode, Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
32 public DefinitelyWrittenCheck(State state) {
34 this.toanalyze = new HashSet();
35 this.definitelyWrittenResults =
36 new Hashtable<FlatNode, Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>>>();
39 public void definitelyWrittenCheck() {
42 SymbolTable classtable = state.getClassSymbolTable();
43 toanalyze.addAll(classtable.getValueSet());
44 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
45 while (!toanalyze.isEmpty()) {
46 Object obj = toanalyze.iterator().next();
47 ClassDescriptor cd = (ClassDescriptor) obj;
49 if (cd.isClassLibrary()) {
50 // doesn't care about class libraries now
53 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
54 MethodDescriptor md = (MethodDescriptor) method_it.next();
55 FlatMethod fm = state.getMethodFlat(md);
57 LoopFinder loopFinder = new LoopFinder(fm);
58 Loops loops = loopFinder.getRootloop(fm);
59 Set loopSet = loops.nestedLoops();
61 for (Iterator iterator = loopSet.iterator(); iterator.hasNext();) {
62 Loops rootLoops = (Loops) iterator.next();
63 Set loopEntranceSet = rootLoops.loopEntrances();
64 for (Iterator iterator2 = loopEntranceSet.iterator(); iterator2.hasNext();) {
65 FlatNode loopEnter = (FlatNode) iterator2.next();
66 definitelyWrittenForward(loopEnter);
72 // check if there is a read statement with flag=TRUE
73 toanalyze.addAll(classtable.getValueSet());
74 toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
75 while (!toanalyze.isEmpty()) {
76 Object obj = toanalyze.iterator().next();
77 ClassDescriptor cd = (ClassDescriptor) obj;
79 if (cd.isClassLibrary()) {
80 // doesn't care about class libraries now
83 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
84 MethodDescriptor md = (MethodDescriptor) method_it.next();
85 FlatMethod fm = state.getMethodFlat(md);
89 System.out.println("Error in " + md);
97 private void checkMethodBody(FlatMethod fm) {
99 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
100 Set<FlatNode> visited = new HashSet<FlatNode>();
101 flatNodesToVisit.add(fm);
103 while (!flatNodesToVisit.isEmpty()) {
104 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
106 flatNodesToVisit.remove(fn);
108 checkMethodBody_nodeAction(fn);
110 // if a new result, schedule forward nodes for analysis
111 for (int i = 0; i < fn.numNext(); i++) {
112 FlatNode nn = fn.getNext(i);
113 if (!visited.contains(nn)) {
114 flatNodesToVisit.add(nn);
121 private void checkMethodBody_nodeAction(FlatNode fn) {
129 case FKind.FlatOpNode: {
131 FlatOpNode fon = (FlatOpNode) fn;
132 if (fon.getOp().getOp() == Operation.ASSIGN) {
136 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> map =
137 definitelyWrittenResults.get(fn);
139 if (map.get(rhs).get(fn).booleanValue()) {
140 throw new Error("variable " + rhs
141 + " was not overwritten in-between the same read statement by the out-most loop.");
150 case FKind.FlatFieldNode: {
152 FlatFieldNode ffn = (FlatFieldNode) fn;
155 fld = ffn.getField();
160 case FKind.FlatElementNode: {
165 case FKind.FlatSetFieldNode: {
169 case FKind.FlatSetElementNode: {
174 case FKind.FlatCall: {
183 private void definitelyWrittenForward(FlatNode entrance) {
185 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
186 flatNodesToVisit.add(entrance);
188 while (!flatNodesToVisit.isEmpty()) {
189 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
190 flatNodesToVisit.remove(fn);
192 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> prev =
193 definitelyWrittenResults.get(fn);
195 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> curr =
196 new Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>>();
197 for (int i = 0; i < fn.numPrev(); i++) {
198 FlatNode nn = fn.getPrev(i);
199 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> dwIn =
200 definitelyWrittenResults.get(nn);
202 mergeResults(curr, dwIn);
206 definitelyWritten_nodeActions(fn, curr, entrance);
208 // if a new result, schedule forward nodes for analysis
209 if (!curr.equals(prev)) {
210 definitelyWrittenResults.put(fn, curr);
212 for (int i = 0; i < fn.numNext(); i++) {
213 FlatNode nn = fn.getNext(i);
214 flatNodesToVisit.add(nn);
220 private void mergeResults(Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> curr,
221 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> in) {
223 Set<TempDescriptor> inKeySet = in.keySet();
224 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
225 TempDescriptor inKey = (TempDescriptor) iterator.next();
226 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
228 Set<FlatNode> pairKeySet = inPair.keySet();
229 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
230 FlatNode pairKey = (FlatNode) iterator2.next();
231 Boolean inFlag = inPair.get(pairKey);
233 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
234 if (currPair == null) {
235 currPair = new Hashtable<FlatNode, Boolean>();
236 curr.put(inKey, currPair);
239 Boolean currFlag = currPair.get(pairKey);
240 // by default, flag is set by false
241 if (currFlag == null) {
242 currFlag = Boolean.FALSE;
244 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
245 currPair.put(pairKey, currFlag);
252 private void definitelyWritten_nodeActions(FlatNode fn,
253 Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> curr, FlatNode entrance) {
255 if (fn == entrance) {
257 Set<TempDescriptor> keySet = curr.keySet();
258 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
259 TempDescriptor key = (TempDescriptor) iterator.next();
260 Hashtable<FlatNode, Boolean> pair = curr.get(key);
262 Set<FlatNode> pairKeySet = pair.keySet();
263 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
264 FlatNode pairKey = (FlatNode) iterator2.next();
265 pair.put(pairKey, Boolean.TRUE);
277 case FKind.FlatOpNode: {
279 FlatOpNode fon = (FlatOpNode) fn;
281 if (fon.getOp().getOp() == Operation.ASSIGN) {
285 Hashtable<FlatNode, Boolean> gen = curr.get(rhs);
287 gen = new Hashtable<FlatNode, Boolean>();
291 Boolean currentStatus = gen.get(fn);
292 if (currentStatus == null) {
293 gen.put(fn, Boolean.FALSE);
297 curr.put(lhs, new Hashtable<FlatNode, Boolean>());
302 case FKind.FlatLiteralNode: {
303 FlatLiteralNode fln = (FlatLiteralNode) fn;
307 curr.put(lhs, new Hashtable<FlatNode, Boolean>());
312 case FKind.FlatFieldNode: {
314 FlatFieldNode ffn = (FlatFieldNode) fn;
317 fld = ffn.getField();
322 case FKind.FlatElementNode: {
327 case FKind.FlatSetFieldNode: {
331 case FKind.FlatSetElementNode: {
336 case FKind.FlatCall: {