Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Set;
   7
   8 import Analysis.Loops.LoopFinder;
   9 import Analysis.Loops.Loops;
  10 import IR.ClassDescriptor;
  11 import IR.FieldDescriptor;
  12 import IR.MethodDescriptor;
  13 import IR.Operation;
  14 import IR.State;
  15 import IR.SymbolTable;
  16 import IR.Flat.FKind;
  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;
  23
  24 public class DefinitelyWrittenCheck {
  25
  26   static State state;
  27   HashSet toanalyze;
  28
  29   // maintains analysis results in the form of <tempDesc,<read statement,flag>>
  30   private Hashtable<FlatNode, Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  31
  32   public DefinitelyWrittenCheck(State state) {
  33     this.state = state;
  34     this.toanalyze = new HashSet();
  35     this.definitelyWrittenResults =
  36         new Hashtable<FlatNode, Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>>>();
  37   }
  38
  39   public void definitelyWrittenCheck() {
  40
  41     // creating map
  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;
  48       toanalyze.remove(cd);
  49       if (cd.isClassLibrary()) {
  50         // doesn't care about class libraries now
  51         continue;
  52       }
  53       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  54         MethodDescriptor md = (MethodDescriptor) method_it.next();
  55         FlatMethod fm = state.getMethodFlat(md);
  56
  57         LoopFinder loopFinder = new LoopFinder(fm);
  58         Loops loops = loopFinder.getRootloop(fm);
  59         Set loopSet = loops.nestedLoops();
  60
  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);
  67           }
  68         }
  69       }
  70     }
  71
  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;
  78       toanalyze.remove(cd);
  79       if (cd.isClassLibrary()) {
  80         // doesn't care about class libraries now
  81         continue;
  82       }
  83       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  84         MethodDescriptor md = (MethodDescriptor) method_it.next();
  85         FlatMethod fm = state.getMethodFlat(md);
  86         try {
  87           checkMethodBody(fm);
  88         } catch (Error e) {
  89           System.out.println("Error in " + md);
  90           throw e;
  91         }
  92       }
  93     }
  94
  95   }
  96
  97   private void checkMethodBody(FlatMethod fm) {
  98
  99     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 100     Set<FlatNode> visited = new HashSet<FlatNode>();
 101     flatNodesToVisit.add(fm);
 102
 103     while (!flatNodesToVisit.isEmpty()) {
 104       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 105       visited.add(fn);
 106       flatNodesToVisit.remove(fn);
 107
 108       checkMethodBody_nodeAction(fn);
 109
 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);
 115         }
 116       }
 117     }
 118
 119   }
 120
 121   private void checkMethodBody_nodeAction(FlatNode fn) {
 122
 123     TempDescriptor lhs;
 124     TempDescriptor rhs;
 125     FieldDescriptor fld;
 126
 127     switch (fn.kind()) {
 128
 129     case FKind.FlatOpNode: {
 130
 131       FlatOpNode fon = (FlatOpNode) fn;
 132       if (fon.getOp().getOp() == Operation.ASSIGN) {
 133         lhs = fon.getDest();
 134         rhs = fon.getLeft();
 135         // read(rhs)
 136         Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> map =
 137             definitelyWrittenResults.get(fn);
 138         if (map != null) {
 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.");
 142           }
 143         }
 144
 145       }
 146
 147     }
 148       break;
 149
 150     case FKind.FlatFieldNode: {
 151
 152       FlatFieldNode ffn = (FlatFieldNode) fn;
 153       lhs = ffn.getDst();
 154       rhs = ffn.getSrc();
 155       fld = ffn.getField();
 156
 157     }
 158       break;
 159
 160     case FKind.FlatElementNode: {
 161
 162     }
 163       break;
 164
 165     case FKind.FlatSetFieldNode: {
 166     }
 167       break;
 168
 169     case FKind.FlatSetElementNode: {
 170
 171     }
 172       break;
 173
 174     case FKind.FlatCall: {
 175
 176     }
 177       break;
 178
 179     }
 180
 181   }
 182
 183   private void definitelyWrittenForward(FlatNode entrance) {
 184
 185     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 186     flatNodesToVisit.add(entrance);
 187
 188     while (!flatNodesToVisit.isEmpty()) {
 189       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 190       flatNodesToVisit.remove(fn);
 191
 192       Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> prev =
 193           definitelyWrittenResults.get(fn);
 194
 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);
 201         if (dwIn != null) {
 202           mergeResults(curr, dwIn);
 203         }
 204       }
 205
 206       definitelyWritten_nodeActions(fn, curr, entrance);
 207
 208       // if a new result, schedule forward nodes for analysis
 209       if (!curr.equals(prev)) {
 210         definitelyWrittenResults.put(fn, curr);
 211
 212         for (int i = 0; i < fn.numNext(); i++) {
 213           FlatNode nn = fn.getNext(i);
 214           flatNodesToVisit.add(nn);
 215         }
 216       }
 217     }
 218   }
 219
 220   private void mergeResults(Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> curr,
 221       Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> in) {
 222
 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);
 227
 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);
 232
 233         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 234         if (currPair == null) {
 235           currPair = new Hashtable<FlatNode, Boolean>();
 236           curr.put(inKey, currPair);
 237         }
 238
 239         Boolean currFlag = currPair.get(pairKey);
 240         // by default, flag is set by false
 241         if (currFlag == null) {
 242           currFlag = Boolean.FALSE;
 243         }
 244         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 245         currPair.put(pairKey, currFlag);
 246       }
 247
 248     }
 249
 250   }
 251
 252   private void definitelyWritten_nodeActions(FlatNode fn,
 253       Hashtable<TempDescriptor, Hashtable<FlatNode, Boolean>> curr, FlatNode entrance) {
 254
 255     if (fn == entrance) {
 256
 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);
 261         if (pair != null) {
 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);
 266           }
 267         }
 268       }
 269
 270     } else {
 271       TempDescriptor lhs;
 272       TempDescriptor rhs;
 273       FieldDescriptor fld;
 274
 275       switch (fn.kind()) {
 276
 277       case FKind.FlatOpNode: {
 278
 279         FlatOpNode fon = (FlatOpNode) fn;
 280         lhs = fon.getDest();
 281         if (fon.getOp().getOp() == Operation.ASSIGN) {
 282           rhs = fon.getLeft();
 283
 284           // read(rhs)
 285           Hashtable<FlatNode, Boolean> gen = curr.get(rhs);
 286           if (gen == null) {
 287             gen = new Hashtable<FlatNode, Boolean>();
 288             curr.put(rhs, gen);
 289           }
 290
 291           Boolean currentStatus = gen.get(fn);
 292           if (currentStatus == null) {
 293             gen.put(fn, Boolean.FALSE);
 294           }
 295         }
 296         // write(lhs)
 297         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 298
 299       }
 300         break;
 301
 302       case FKind.FlatLiteralNode: {
 303         FlatLiteralNode fln = (FlatLiteralNode) fn;
 304         lhs = fln.getDst();
 305
 306         // write(lhs)
 307         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 308
 309       }
 310         break;
 311
 312       case FKind.FlatFieldNode: {
 313
 314         FlatFieldNode ffn = (FlatFieldNode) fn;
 315         lhs = ffn.getDst();
 316         rhs = ffn.getSrc();
 317         fld = ffn.getField();
 318
 319       }
 320         break;
 321
 322       case FKind.FlatElementNode: {
 323
 324       }
 325         break;
 326
 327       case FKind.FlatSetFieldNode: {
 328       }
 329         break;
 330
 331       case FKind.FlatSetElementNode: {
 332
 333       }
 334         break;
 335
 336       case FKind.FlatCall: {
 337
 338       }
 339         break;
 340
 341       }
 342     }
 343
 344   }
 345
 346 }