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.Descriptor;
  12 import IR.FieldDescriptor;
  13 import IR.MethodDescriptor;
  14 import IR.Operation;
  15 import IR.State;
  16 import IR.SymbolTable;
  17 import IR.VarDescriptor;
  18 import IR.Flat.FKind;
  19 import IR.Flat.FlatFieldNode;
  20 import IR.Flat.FlatLiteralNode;
  21 import IR.Flat.FlatMethod;
  22 import IR.Flat.FlatNode;
  23 import IR.Flat.FlatOpNode;
  24 import IR.Flat.FlatSetFieldNode;
  25 import IR.Flat.TempDescriptor;
  26
  27 public class DefinitelyWrittenCheck {
  28
  29   static State state;
  30   HashSet toanalyze;
  31
  32   private Hashtable<FlatNode, Hashtable<Descriptor, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  33
  34   public DefinitelyWrittenCheck(State state) {
  35     this.state = state;
  36     this.toanalyze = new HashSet();
  37     this.definitelyWrittenResults =
  38       new Hashtable<FlatNode, Hashtable<Descriptor, Hashtable<FlatNode, Boolean>>>();
  39   }
  40
  41   public void definitelyWrittenCheck() {
  42
  43     SymbolTable classtable = state.getClassSymbolTable();
  44     toanalyze.addAll(classtable.getValueSet());
  45     toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
  46     while (!toanalyze.isEmpty()) {
  47       Object obj = toanalyze.iterator().next();
  48       ClassDescriptor cd = (ClassDescriptor) obj;
  49       toanalyze.remove(cd);
  50
  51 //      if (cd.isClassLibrary()) {
  52       // doesn't care about class libraries now
  53 //        continue;
  54 //      }
  55       for (Iterator method_it = cd.getMethods(); method_it.hasNext(); ) {
  56         MethodDescriptor md = (MethodDescriptor) method_it.next();
  57         FlatMethod fm = state.getMethodFlat(md);
  58         if (fm != null) {
  59
  60         }
  61
  62       }
  63     }
  64
  65
  66
  67     /*
  68        // creating map
  69        SymbolTable classtable = state.getClassSymbolTable();
  70        toanalyze.addAll(classtable.getValueSet());
  71        toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
  72        while (!toanalyze.isEmpty()) {
  73        Object obj = toanalyze.iterator().next();
  74        ClassDescriptor cd = (ClassDescriptor) obj;
  75        toanalyze.remove(cd);
  76
  77        if (cd.isClassLibrary()) {
  78         // doesn't care about class libraries now
  79         continue;
  80        }
  81        for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  82         MethodDescriptor md = (MethodDescriptor) method_it.next();
  83         FlatMethod fm = state.getMethodFlat(md);
  84         if (fm != null) {
  85           LoopFinder loopFinder = new LoopFinder(fm);
  86           Loops loops = loopFinder.getRootloop(fm);
  87           Set loopSet = loops.nestedLoops();
  88
  89           for (Iterator iterator = loopSet.iterator(); iterator.hasNext();) {
  90             Loops rootLoops = (Loops) iterator.next();
  91             Set loopEntranceSet = rootLoops.loopEntrances();
  92             for (Iterator iterator2 = loopEntranceSet.iterator(); iterator2.hasNext();) {
  93               FlatNode loopEnter = (FlatNode) iterator2.next();
  94               String flatNodeLabel = (String) state.fn2labelMap.get(loopEnter);
  95               if (flatNodeLabel != null && flatNodeLabel.equals("ssjava")) {
  96                 System.out.println("encounting ss loop:" + loopEnter);
  97                 definitelyWrittenForward(loopEnter);
  98               }
  99             }
 100           }
 101         }
 102
 103        }
 104        }
 105
 106        // check if there is a read statement with flag=TRUE
 107        toanalyze.addAll(classtable.getValueSet());
 108        toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
 109        while (!toanalyze.isEmpty()) {
 110        Object obj = toanalyze.iterator().next();
 111        ClassDescriptor cd = (ClassDescriptor) obj;
 112        toanalyze.remove(cd);
 113        if (cd.isClassLibrary()) {
 114         // doesn't care about class libraries now
 115         continue;
 116        }
 117        for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 118         MethodDescriptor md = (MethodDescriptor) method_it.next();
 119         FlatMethod fm = state.getMethodFlat(md);
 120         try {
 121           checkMethodBody(fm);
 122         } catch (Error e) {
 123           System.out.println("Error in " + md);
 124           throw e;
 125         }
 126        }
 127        }
 128      */
 129
 130   }
 131
 132
 133
 134
 135   private void checkMethodBody(FlatMethod fm) {
 136
 137     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 138     Set<FlatNode> visited = new HashSet<FlatNode>();
 139     flatNodesToVisit.add(fm);
 140
 141     while (!flatNodesToVisit.isEmpty()) {
 142       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 143       visited.add(fn);
 144       flatNodesToVisit.remove(fn);
 145
 146       checkMethodBody_nodeAction(fn);
 147
 148       // if a new result, schedule forward nodes for analysis
 149       for (int i = 0; i < fn.numNext(); i++) {
 150         FlatNode nn = fn.getNext(i);
 151         if (!visited.contains(nn)) {
 152           flatNodesToVisit.add(nn);
 153         }
 154       }
 155     }
 156
 157   }
 158
 159   private void checkMethodBody_nodeAction(FlatNode fn) {
 160
 161     TempDescriptor lhs;
 162     TempDescriptor rhs;
 163     FieldDescriptor fld;
 164
 165     switch (fn.kind()) {
 166
 167     case FKind.FlatOpNode: {
 168
 169       FlatOpNode fon = (FlatOpNode) fn;
 170       if (fon.getOp().getOp() == Operation.ASSIGN) {
 171         lhs = fon.getDest();
 172         rhs = fon.getLeft();
 173         // read(rhs)
 174         Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> map = definitelyWrittenResults.get(fn);
 175         if (map != null) {
 176           if (map.get(rhs).get(fn).booleanValue()) {
 177             // throw new Error("variable " + rhs
 178             // +
 179             // " was not overwritten in-between the same read statement by the out-most loop.");
 180           }
 181         }
 182
 183       }
 184
 185     }
 186     break;
 187
 188     case FKind.FlatFieldNode: {
 189
 190       FlatFieldNode ffn = (FlatFieldNode) fn;
 191       lhs = ffn.getDst();
 192       rhs = ffn.getSrc();
 193       fld = ffn.getField();
 194
 195     }
 196     break;
 197
 198     case FKind.FlatElementNode: {
 199
 200     }
 201     break;
 202
 203     case FKind.FlatSetFieldNode: {
 204     }
 205     break;
 206
 207     case FKind.FlatSetElementNode: {
 208
 209     }
 210     break;
 211
 212     case FKind.FlatCall: {
 213
 214     }
 215     break;
 216
 217     }
 218
 219   }
 220
 221   private void definitelyWrittenForward(FlatNode entrance) {
 222
 223     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 224     flatNodesToVisit.add(entrance);
 225
 226     while (!flatNodesToVisit.isEmpty()) {
 227       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 228       flatNodesToVisit.remove(fn);
 229
 230       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> prev = definitelyWrittenResults.get(fn);
 231
 232       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr =
 233         new Hashtable<Descriptor, Hashtable<FlatNode, Boolean>>();
 234       for (int i = 0; i < fn.numPrev(); i++) {
 235         FlatNode nn = fn.getPrev(i);
 236         Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> dwIn = definitelyWrittenResults.get(nn);
 237         if (dwIn != null) {
 238           mergeResults(curr, dwIn);
 239         }
 240       }
 241
 242       definitelyWritten_nodeActions(fn, curr, entrance);
 243
 244       // if a new result, schedule forward nodes for analysis
 245       if (!curr.equals(prev)) {
 246         definitelyWrittenResults.put(fn, curr);
 247
 248         for (int i = 0; i < fn.numNext(); i++) {
 249           FlatNode nn = fn.getNext(i);
 250           flatNodesToVisit.add(nn);
 251         }
 252       }
 253     }
 254   }
 255
 256   private void mergeResults(Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr,
 257                             Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> in) {
 258
 259     Set<Descriptor> inKeySet = in.keySet();
 260     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext(); ) {
 261       Descriptor inKey = (Descriptor) iterator.next();
 262       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 263
 264       Set<FlatNode> pairKeySet = inPair.keySet();
 265       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext(); ) {
 266         FlatNode pairKey = (FlatNode) iterator2.next();
 267         Boolean inFlag = inPair.get(pairKey);
 268
 269         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 270         if (currPair == null) {
 271           currPair = new Hashtable<FlatNode, Boolean>();
 272           curr.put(inKey, currPair);
 273         }
 274
 275         Boolean currFlag = currPair.get(pairKey);
 276         // by default, flag is set by false
 277         if (currFlag == null) {
 278           currFlag = Boolean.FALSE;
 279         }
 280         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 281         currPair.put(pairKey, currFlag);
 282       }
 283
 284     }
 285
 286   }
 287
 288   private void definitelyWritten_nodeActions(FlatNode fn,
 289                                              Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr, FlatNode entrance) {
 290
 291     if (fn == entrance) {
 292
 293       Set<Descriptor> keySet = curr.keySet();
 294       for (Iterator iterator = keySet.iterator(); iterator.hasNext(); ) {
 295         Descriptor key = (Descriptor) iterator.next();
 296         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 297         if (pair != null) {
 298           Set<FlatNode> pairKeySet = pair.keySet();
 299           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext(); ) {
 300             FlatNode pairKey = (FlatNode) iterator2.next();
 301             pair.put(pairKey, Boolean.TRUE);
 302           }
 303         }
 304       }
 305
 306     } else {
 307       TempDescriptor lhs;
 308       TempDescriptor rhs;
 309       FieldDescriptor fld;
 310
 311       switch (fn.kind()) {
 312
 313       case FKind.FlatOpNode: {
 314
 315         FlatOpNode fon = (FlatOpNode) fn;
 316         lhs = fon.getDest();
 317         rhs = fon.getLeft();
 318         System.out.println("\nfon=" + fon);
 319
 320         if (fon.getOp().getOp() == Operation.ASSIGN) {
 321
 322           // read(rhs)
 323           Hashtable<FlatNode, Boolean> gen = curr.get(rhs);
 324           if (gen == null) {
 325             gen = new Hashtable<FlatNode, Boolean>();
 326             curr.put(rhs, gen);
 327           }
 328           System.out.println("READ LOC=" + rhs.getType().getExtension());
 329
 330           Boolean currentStatus = gen.get(fn);
 331           if (currentStatus == null) {
 332             gen.put(fn, Boolean.FALSE);
 333           }
 334         }
 335         // write(lhs)
 336         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 337         System.out.println("WRITING LOC=" + lhs.getType().getExtension());
 338
 339       }
 340       break;
 341
 342       case FKind.FlatLiteralNode: {
 343         FlatLiteralNode fln = (FlatLiteralNode) fn;
 344         lhs = fln.getDst();
 345
 346         // write(lhs)
 347         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 348
 349         System.out.println("WRITING LOC=" + lhs.getType().getExtension());
 350
 351       }
 352       break;
 353
 354       case FKind.FlatFieldNode:
 355       case FKind.FlatElementNode: {
 356
 357         FlatFieldNode ffn = (FlatFieldNode) fn;
 358         lhs = ffn.getSrc();
 359         fld = ffn.getField();
 360
 361         // read field
 362         Hashtable<FlatNode, Boolean> gen = curr.get(fld);
 363         if (gen == null) {
 364           gen = new Hashtable<FlatNode, Boolean>();
 365           curr.put(fld, gen);
 366         }
 367         Boolean currentStatus = gen.get(fn);
 368         if (currentStatus == null) {
 369           gen.put(fn, Boolean.FALSE);
 370         }
 371
 372         System.out.println("\nffn=" + ffn);
 373         System.out.println("READ LOCfld=" + fld.getType().getExtension());
 374         System.out.println("READ LOClhs=" + lhs.getType().getExtension());
 375
 376       }
 377       break;
 378
 379       case FKind.FlatSetFieldNode:
 380       case FKind.FlatSetElementNode: {
 381
 382         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 383         fld = fsfn.getField();
 384
 385         // write(field)
 386         curr.put(fld, new Hashtable<FlatNode, Boolean>());
 387
 388         System.out.println("\nfsfn=" + fsfn);
 389         System.out.println("WRITELOC LOC=" + fld.getType().getExtension());
 390
 391       }
 392       break;
 393
 394       case FKind.FlatCall: {
 395
 396       }
 397       break;
 398
 399       }
 400     }
 401
 402   }
 403
 404 }