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.LinkedList;
   7 import java.util.Set;
   8 import java.util.Stack;
   9
  10 import Analysis.CallGraph.CallGraph;
  11 import Analysis.Loops.LoopFinder;
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14 import IR.MethodDescriptor;
  15 import IR.Operation;
  16 import IR.State;
  17 import IR.TypeDescriptor;
  18 import IR.Flat.FKind;
  19 import IR.Flat.FlatCall;
  20 import IR.Flat.FlatFieldNode;
  21 import IR.Flat.FlatLiteralNode;
  22 import IR.Flat.FlatMethod;
  23 import IR.Flat.FlatNode;
  24 import IR.Flat.FlatOpNode;
  25 import IR.Flat.FlatSetFieldNode;
  26 import IR.Flat.TempDescriptor;
  27 import Util.Pair;
  28
  29 public class DefinitelyWrittenCheck {
  30
  31   SSJavaAnalysis ssjava;
  32   State state;
  33   CallGraph callGraph;
  34
  35   // maps a descriptor to its known dependents: namely
  36   // methods or tasks that call the descriptor's method
  37   // AND are part of this analysis (reachable from main)
  38   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  39
  40   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  41   // previously.
  42   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  43
  44   // maps a temp descriptor to its heap path
  45   // each temp descriptor has a unique heap path since we do not allow any
  46   // alias.
  47   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  48
  49   // maps a flat method to the READ that is the set of heap path that is
  50   // expected to be written before method invocation
  51   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  52
  53   // maps a flat method to the OVERWRITE that is the set of heap path that is
  54   // overwritten on every possible path during method invocation
  55   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  56
  57   // points to method containing SSJAVA Loop
  58   private MethodDescriptor methodContainingSSJavaLoop;
  59
  60   // maps a flatnode to definitely written analysis mapping M
  61   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  62
  63   // maps a method descriptor to its current summary during the analysis
  64   // then analysis reaches fixed-point, this mapping will have the final summary
  65   // for each method descriptor
  66   private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToCompleteClearingSummary;
  67
  68   // maps a method descriptor to the merged incoming caller's current
  69   // overwritten status
  70   private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToInitialClearingSummary;
  71
  72   // maps a flat node to current partial results
  73   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>> mapFlatNodeToClearingSummary;
  74
  75   // maps shared location to the set of descriptors which belong to the shared
  76   // location
  77   private Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
  78
  79   // keep current descriptors to visit in fixed-point interprocedural analysis,
  80   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  81
  82   // when analyzing flatcall, need to re-schedule set of callee
  83   private Set<MethodDescriptor> calleesToEnqueue;
  84
  85   private Set<Hashtable<NTuple<Descriptor>, SharedLocState>> possibleCalleeCompleteSummarySetToCaller;
  86
  87   private LinkedList<MethodDescriptor> sortedDescriptors;
  88
  89   private FlatNode ssjavaLoopEntrance;
  90   private LoopFinder ssjavaLoop;
  91   private Set<FlatNode> loopIncElements;
  92
  93   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  94   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  95
  96   private TempDescriptor LOCAL;
  97
  98   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  99     this.state = state;
 100     this.ssjava = ssjava;
 101     this.callGraph = ssjava.getCallGraph();
 102     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 103     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 104     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
 105     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 106     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 107     this.definitelyWrittenResults =
 108         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
 109     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 110     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
 111
 112     this.mapMethodDescriptorToCompleteClearingSummary =
 113         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 114     this.mapMethodDescriptorToInitialClearingSummary =
 115         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 116     this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
 117     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 118     this.calleesToEnqueue = new HashSet<MethodDescriptor>();
 119     this.possibleCalleeCompleteSummarySetToCaller =
 120         new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
 121     this.LOCAL = new TempDescriptor("LOCAL");
 122   }
 123
 124   public void definitelyWrittenCheck() {
 125     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 126       methodReadOverWriteAnalysis();
 127       writtenAnalyis();
 128       sharedLocationAnalysis();
 129       checkSharedLocationResult();
 130     }
 131   }
 132
 133   private void checkSharedLocationResult() {
 134
 135     // mapping of method containing ssjava loop has the final result of
 136     // shared location analysis
 137     Hashtable<NTuple<Descriptor>, SharedLocState> result =
 138         mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
 139
 140     System.out.println("checkSharedLocationResult=" + result);
 141
 142     Set<NTuple<Descriptor>> hpKeySet = result.keySet();
 143     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 144       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 145       SharedLocState state = result.get(hpKey);
 146       Set<Location> locKeySet = state.getLocationSet();
 147       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 148         Location locKey = (Location) iterator2.next();
 149         if (!state.getFlag(locKey)) {
 150           throw new Error(
 151               "Some concrete locations of the shared abstract location are not cleared at the same time.");
 152         }
 153       }
 154     }
 155
 156   }
 157
 158   private void sharedLocationAnalysis() {
 159     // verify that all concrete locations of shared location are cleared out at
 160     // the same time once per the out-most loop
 161
 162     computeReadSharedDescriptorSet();
 163     System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet);
 164
 165     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 166
 167     methodDescriptorsToVisitStack.clear();
 168     methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 169     methodDescriptorToVistSet.add(sortedDescriptors.peekFirst());
 170
 171     // analyze scheduled methods until there are no more to visit
 172     while (!methodDescriptorsToVisitStack.isEmpty()) {
 173       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 174       methodDescriptorToVistSet.remove(md);
 175
 176       Hashtable<NTuple<Descriptor>, SharedLocState> completeSummary =
 177           sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 178
 179       Hashtable<NTuple<Descriptor>, SharedLocState> prevCompleteSummary =
 180           mapMethodDescriptorToCompleteClearingSummary.get(md);
 181
 182       if (!completeSummary.equals(prevCompleteSummary)) {
 183
 184         mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 185
 186         Set<MethodDescriptor> dependentsSet = getDependents(md);
 187         if (dependentsSet.size() == 0) {
 188           dependentsSet.add(methodContainingSSJavaLoop);
 189         }
 190
 191         // results for callee changed, so enqueue dependents caller for
 192         // further analysis
 193         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 194         while (depsItr.hasNext()) {
 195           MethodDescriptor methodNext = depsItr.next();
 196           if (!methodDescriptorsToVisitStack.contains(methodNext)
 197               && !methodDescriptorToVistSet.contains(methodNext)) {
 198             methodDescriptorsToVisitStack.add(methodNext);
 199           }
 200         }
 201
 202         // if there is set of callee to be analyzed,
 203         // add this set into the top of stack
 204         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 205         while (calleeIter.hasNext()) {
 206           MethodDescriptor mdNext = calleeIter.next();
 207           methodDescriptorsToVisitStack.add(mdNext);
 208         }
 209         calleesToEnqueue.clear();
 210
 211       }
 212
 213     }
 214
 215     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 216     flatNodesToVisit.add(ssjavaLoopEntrance);
 217
 218   }
 219
 220   private Hashtable<NTuple<Descriptor>, SharedLocState> sharedLocation_analyzeMethod(
 221       MethodDescriptor md, boolean onlyVisitSSJavaLoop) {
 222
 223     if (state.SSJAVADEBUG) {
 224       System.out.println("Definitely written for shared locations Analyzing: " + md + " "
 225           + onlyVisitSSJavaLoop);
 226     }
 227
 228     FlatMethod fm = state.getMethodFlat(md);
 229
 230     // intraprocedural analysis
 231     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 232
 233     // start a new mapping of partial results for each flat node
 234     mapFlatNodeToClearingSummary =
 235         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 236
 237     if (onlyVisitSSJavaLoop) {
 238       flatNodesToVisit.add(ssjavaLoopEntrance);
 239     } else {
 240       flatNodesToVisit.add(fm);
 241     }
 242
 243     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 244
 245     while (!flatNodesToVisit.isEmpty()) {
 246       FlatNode fn = flatNodesToVisit.iterator().next();
 247       flatNodesToVisit.remove(fn);
 248
 249       Hashtable<NTuple<Descriptor>, SharedLocState> curr =
 250           new Hashtable<NTuple<Descriptor>, SharedLocState>();
 251
 252       Set<Hashtable<NTuple<Descriptor>, SharedLocState>> prevSet =
 253           new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
 254       for (int i = 0; i < fn.numPrev(); i++) {
 255         FlatNode prevFn = fn.getPrev(i);
 256         Hashtable<NTuple<Descriptor>, SharedLocState> in = mapFlatNodeToClearingSummary.get(prevFn);
 257         if (in != null) {
 258           prevSet.add(in);
 259         }
 260       }
 261       mergeSharedLocationAnaylsis(curr, prevSet);
 262
 263       sharedLocation_nodeActions(fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 264       Hashtable<NTuple<Descriptor>, SharedLocState> clearingPrev =
 265           mapFlatNodeToClearingSummary.get(fn);
 266
 267       if (!curr.equals(clearingPrev)) {
 268         mapFlatNodeToClearingSummary.put(fn, curr);
 269
 270         for (int i = 0; i < fn.numNext(); i++) {
 271           FlatNode nn = fn.getNext(i);
 272
 273           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 274             flatNodesToVisit.add(nn);
 275           }
 276
 277         }
 278       }
 279
 280     }
 281
 282     Hashtable<NTuple<Descriptor>, SharedLocState> completeSummary =
 283         new Hashtable<NTuple<Descriptor>, SharedLocState>();
 284
 285     Set<Hashtable<NTuple<Descriptor>, SharedLocState>> summarySet =
 286         new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
 287     if (onlyVisitSSJavaLoop) {
 288       // when analyzing ssjava loop,
 289       // complete summary is merging of all previous nodes of ssjava loop
 290       // entrance
 291       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 292         Hashtable<NTuple<Descriptor>, SharedLocState> frnSummary =
 293             mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
 294         if (frnSummary != null) {
 295           summarySet.add(frnSummary);
 296         }
 297       }
 298     } else {
 299       // merging all exit node summary into the complete summary
 300       if (!returnNodeSet.isEmpty()) {
 301         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 302           FlatNode frn = (FlatNode) iterator.next();
 303           Hashtable<NTuple<Descriptor>, SharedLocState> frnSummary =
 304               mapFlatNodeToClearingSummary.get(frn);
 305           summarySet.add(frnSummary);
 306         }
 307       }
 308     }
 309     mergeSharedLocationAnaylsis(completeSummary, summarySet);
 310     return completeSummary;
 311   }
 312
 313   private void sharedLocation_nodeActions(FlatNode fn,
 314       Hashtable<NTuple<Descriptor>, SharedLocState> curr, Set<FlatNode> returnNodeSet,
 315       boolean isSSJavaLoop) {
 316
 317     TempDescriptor lhs;
 318     TempDescriptor rhs;
 319     FieldDescriptor fld;
 320     switch (fn.kind()) {
 321
 322     case FKind.FlatMethod: {
 323       FlatMethod fm = (FlatMethod) fn;
 324
 325       Hashtable<NTuple<Descriptor>, SharedLocState> summaryFromCaller =
 326           mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
 327
 328       Set<Hashtable<NTuple<Descriptor>, SharedLocState>> inSet =
 329           new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
 330       inSet.add(summaryFromCaller);
 331       mergeSharedLocationAnaylsis(curr, inSet);
 332
 333     }
 334       break;
 335
 336     case FKind.FlatOpNode: {
 337       FlatOpNode fon = (FlatOpNode) fn;
 338       lhs = fon.getDest();
 339       rhs = fon.getLeft();
 340
 341       if (fon.getOp().getOp() == Operation.ASSIGN) {
 342         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 343           // in ssjavaloop, we need to take care about reading local variables!
 344           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 345           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 346           rhsHeapPath.add(LOCAL);
 347           lhsHeapPath.add(LOCAL);
 348           if (!lhs.getSymbol().startsWith("neverused")) {
 349             readLocation(curr, rhsHeapPath, rhs);
 350             writeLocation(curr, lhsHeapPath, lhs);
 351           }
 352         }
 353       }
 354
 355     }
 356       break;
 357
 358     case FKind.FlatFieldNode:
 359     case FKind.FlatElementNode: {
 360
 361       FlatFieldNode ffn = (FlatFieldNode) fn;
 362       lhs = ffn.getDst();
 363       rhs = ffn.getSrc();
 364       fld = ffn.getField();
 365
 366       // read field
 367       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 368       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 369
 370       if (fld.getType().isImmutable()) {
 371         readLocation(curr, fldHeapPath, fld);
 372       }
 373
 374     }
 375       break;
 376
 377     case FKind.FlatSetFieldNode:
 378     case FKind.FlatSetElementNode: {
 379
 380       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 381       lhs = fsfn.getDst();
 382       fld = fsfn.getField();
 383
 384       // write(field)
 385       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 386       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 387       if (fld.getType().isImmutable()) {
 388         writeLocation(curr, fldHeapPath, fld);
 389       }
 390
 391     }
 392       break;
 393
 394     case FKind.FlatCall: {
 395
 396       FlatCall fc = (FlatCall) fn;
 397
 398       // find out the set of callees
 399       MethodDescriptor mdCallee = fc.getMethod();
 400       FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 401       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 402       TypeDescriptor typeDesc = fc.getThis().getType();
 403       setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 404
 405       possibleCalleeCompleteSummarySetToCaller.clear();
 406
 407       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 408         MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 409         FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 410
 411         calleesToEnqueue.add(mdPossibleCallee);
 412
 413         // updates possible callee's initial summary using caller's current
 414         // writing status
 415         Hashtable<NTuple<Descriptor>, SharedLocState> prevCalleeInitSummary =
 416             mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 417
 418         Hashtable<NTuple<Descriptor>, SharedLocState> calleeInitSummary =
 419             bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 420
 421         // if changes, update the init summary
 422         // and reschedule the callee for analysis
 423         if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 424           methodDescriptorsToVisitStack.add(mdPossibleCallee);
 425           mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 426         }
 427
 428       }
 429
 430       // contribute callee's writing effects to the caller
 431       mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 432
 433     }
 434       break;
 435
 436     case FKind.FlatReturnNode: {
 437       returnNodeSet.add(fn);
 438     }
 439       break;
 440
 441     }
 442
 443   }
 444
 445   private Hashtable<NTuple<Descriptor>, SharedLocState> bindHeapPathOfCalleeCallerEffects(
 446       FlatCall fc, FlatMethod calleeFlatMethod, Hashtable<NTuple<Descriptor>, SharedLocState> curr) {
 447
 448     Hashtable<NTuple<Descriptor>, SharedLocState> boundSet =
 449         new Hashtable<NTuple<Descriptor>, SharedLocState>();
 450
 451     // create mapping from arg idx to its heap paths
 452     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 453         new Hashtable<Integer, NTuple<Descriptor>>();
 454
 455     // arg idx is starting from 'this' arg
 456     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 457     if (thisHeapPath == null) {
 458       // method is called without creating new flat node representing 'this'
 459       thisHeapPath = new NTuple<Descriptor>();
 460       thisHeapPath.add(fc.getThis());
 461     }
 462
 463     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 464
 465     for (int i = 0; i < fc.numArgs(); i++) {
 466       TempDescriptor arg = fc.getArg(i);
 467       NTuple<Descriptor> argHeapPath = computePath(arg);
 468       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 469     }
 470
 471     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 472         new Hashtable<Integer, TempDescriptor>();
 473     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 474       TempDescriptor param = calleeFlatMethod.getParameter(i);
 475       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 476     }
 477
 478     // binding caller's writing effects to callee's params
 479     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 480       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 481       TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 482
 483       // iterate over caller's writing effect set
 484       Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 485       for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 486         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 487         // current element is reachable caller's arg
 488         // so need to bind it to the caller's side and add it to the callee's
 489         // init summary
 490         if (hpKey.startsWith(argHeapPath)) {
 491           NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 492           boundSet.put(boundHeapPath, curr.get(hpKey).clone());
 493         }
 494
 495       }
 496
 497     }
 498
 499     // contribute callee's complete summary into the caller's current summary
 500     Hashtable<NTuple<Descriptor>, SharedLocState> calleeCompleteSummary =
 501         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
 502
 503     if (calleeCompleteSummary != null) {
 504       Hashtable<NTuple<Descriptor>, SharedLocState> boundCalleeEfffects =
 505           new Hashtable<NTuple<Descriptor>, SharedLocState>();
 506       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 507         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 508         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 509
 510         // iterate over callee's writing effect set
 511         Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
 512         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 513           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 514           // current element is reachable caller's arg
 515           // so need to bind it to the caller's side and add it to the callee's
 516           // init summary
 517           if (hpKey.startsWith(calleeParamHeapPath)) {
 518
 519             NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 520
 521             boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
 522                 .clone());
 523
 524           }
 525         }
 526       }
 527       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
 528     }
 529
 530     return boundSet;
 531   }
 532
 533   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
 534
 535     // replace the head of heap path with caller's arg path
 536     // for example, heap path 'param.a.b' in callee's side will be replaced with
 537     // (corresponding arg heap path).a.b for caller's side
 538
 539     NTuple<Descriptor> bound = new NTuple<Descriptor>();
 540
 541     for (int i = 0; i < argHeapPath.size(); i++) {
 542       bound.add(argHeapPath.get(i));
 543     }
 544
 545     for (int i = 1; i < hpKey.size(); i++) {
 546       bound.add(hpKey.get(i));
 547     }
 548
 549     return bound;
 550   }
 551
 552   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
 553       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
 554     // replace the head of caller's heap path with callee's param heap path
 555
 556     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
 557     boundHeapPath.add(calleeParamHeapPath);
 558
 559     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
 560       boundHeapPath.add(effectHeapPath.get(i));
 561     }
 562
 563     return boundHeapPath;
 564   }
 565
 566   private void computeReadSharedDescriptorSet() {
 567     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 568     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 569
 570     for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
 571       MethodDescriptor md = (MethodDescriptor) iterator.next();
 572       FlatMethod fm = state.getMethodFlat(md);
 573       computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
 574     }
 575
 576   }
 577
 578   private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
 579       boolean onlyVisitSSJavaLoop) {
 580
 581     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 582     Set<FlatNode> visited = new HashSet<FlatNode>();
 583
 584     if (onlyVisitSSJavaLoop) {
 585       flatNodesToVisit.add(ssjavaLoopEntrance);
 586     } else {
 587       flatNodesToVisit.add(fm);
 588     }
 589
 590     while (!flatNodesToVisit.isEmpty()) {
 591       FlatNode fn = flatNodesToVisit.iterator().next();
 592       flatNodesToVisit.remove(fn);
 593       visited.add(fn);
 594
 595       computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
 596
 597       for (int i = 0; i < fn.numNext(); i++) {
 598         FlatNode nn = fn.getNext(i);
 599         if (!visited.contains(nn)) {
 600           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 601             flatNodesToVisit.add(nn);
 602           }
 603         }
 604       }
 605
 606     }
 607
 608   }
 609
 610   private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
 611
 612     TempDescriptor lhs;
 613     TempDescriptor rhs;
 614     FieldDescriptor fld;
 615
 616     switch (fn.kind()) {
 617     case FKind.FlatOpNode: {
 618       FlatOpNode fon = (FlatOpNode) fn;
 619       lhs = fon.getDest();
 620       rhs = fon.getLeft();
 621
 622       if (fon.getOp().getOp() == Operation.ASSIGN) {
 623         if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
 624           // in ssjavaloop, we need to take care about reading local variables!
 625           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 626           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 627           rhsHeapPath.add(LOCAL);
 628           addReadDescriptor(rhsHeapPath, rhs);
 629         }
 630       }
 631
 632     }
 633       break;
 634
 635     case FKind.FlatFieldNode:
 636     case FKind.FlatElementNode: {
 637
 638       FlatFieldNode ffn = (FlatFieldNode) fn;
 639       lhs = ffn.getDst();
 640       rhs = ffn.getSrc();
 641       fld = ffn.getField();
 642
 643       // read field
 644       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 645       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 646       // fldHeapPath.add(fld);
 647
 648       if (fld.getType().isImmutable()) {
 649         addReadDescriptor(fldHeapPath, fld);
 650       }
 651
 652       // propagate rhs's heap path to the lhs
 653       mapHeapPath.put(lhs, fldHeapPath);
 654
 655     }
 656       break;
 657
 658     case FKind.FlatSetFieldNode:
 659     case FKind.FlatSetElementNode: {
 660
 661       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 662       lhs = fsfn.getDst();
 663       fld = fsfn.getField();
 664
 665       // write(field)
 666       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 667       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 668       // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 669
 670     }
 671       break;
 672
 673     }
 674   }
 675
 676   private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
 677     if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
 678       return false;
 679     } else {
 680       return mapSharedLocation2DescriptorSet.get(loc).contains(d);
 681     }
 682   }
 683
 684   private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
 685
 686     Location loc = getLocation(d);
 687
 688     if (loc != null && ssjava.isSharedLocation(loc)) {
 689
 690       Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
 691       if (set == null) {
 692         set = new HashSet<Descriptor>();
 693         mapSharedLocation2DescriptorSet.put(loc, set);
 694       }
 695       set.add(d);
 696     }
 697
 698   }
 699
 700   private Location getLocation(Descriptor d) {
 701
 702     if (d instanceof FieldDescriptor) {
 703       return (Location) ((FieldDescriptor) d).getType().getExtension();
 704     } else {
 705       assert d instanceof TempDescriptor;
 706       CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
 707       if (comp == null) {
 708         return null;
 709       } else {
 710         return comp.get(comp.getSize() - 1);
 711       }
 712     }
 713
 714   }
 715
 716   private void writeLocation(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 717       NTuple<Descriptor> hp, Descriptor d) {
 718     Location loc = getLocation(d);
 719     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 720       SharedLocState state = getState(curr, hp);
 721       state.addVar(loc, d);
 722
 723       // if the set v contains all of variables belonging to the shared
 724       // location, set flag to true
 725
 726       Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
 727
 728       if (state.getVarSet(loc).containsAll(sharedVarSet)) {
 729         state.updateFlag(loc, true);
 730       }
 731     }
 732   }
 733
 734   private void readLocation(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 735       NTuple<Descriptor> hp, Descriptor d) {
 736     // remove reading var x from written set
 737     Location loc = getLocation(d);
 738     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 739       SharedLocState state = getState(curr, hp);
 740       state.removeVar(loc, d);
 741     }
 742   }
 743
 744   private SharedLocState getState(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 745       NTuple<Descriptor> hp) {
 746     SharedLocState state = curr.get(hp);
 747     if (state == null) {
 748       state = new SharedLocState();
 749       curr.put(hp, state);
 750     }
 751     return state;
 752   }
 753
 754   private void writtenAnalyis() {
 755     // perform second stage analysis: intraprocedural analysis ensure that
 756     // all
 757     // variables are definitely written in-between the same read
 758
 759     // First, identify ssjava loop entrace
 760     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 761     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 762     flatNodesToVisit.add(fm);
 763
 764     LoopFinder loopFinder = new LoopFinder(fm);
 765
 766     while (!flatNodesToVisit.isEmpty()) {
 767       FlatNode fn = flatNodesToVisit.iterator().next();
 768       flatNodesToVisit.remove(fn);
 769
 770       String label = (String) state.fn2labelMap.get(fn);
 771       if (label != null) {
 772
 773         if (label.equals(ssjava.SSJAVA)) {
 774           ssjavaLoopEntrance = fn;
 775           break;
 776         }
 777       }
 778
 779       for (int i = 0; i < fn.numNext(); i++) {
 780         FlatNode nn = fn.getNext(i);
 781         flatNodesToVisit.add(nn);
 782       }
 783     }
 784
 785     assert ssjavaLoopEntrance != null;
 786
 787     // assume that ssjava loop is top-level loop in method, not nested loop
 788     Set nestedLoop = loopFinder.nestedLoops();
 789     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 790       LoopFinder lf = (LoopFinder) loopIter.next();
 791       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 792         ssjavaLoop = lf;
 793       }
 794     }
 795
 796     assert ssjavaLoop != null;
 797
 798     writtenAnalysis_analyzeLoop();
 799
 800   }
 801
 802   private void writtenAnalysis_analyzeLoop() {
 803
 804     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 805     flatNodesToVisit.add(ssjavaLoopEntrance);
 806
 807     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 808
 809     while (!flatNodesToVisit.isEmpty()) {
 810       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 811       flatNodesToVisit.remove(fn);
 812
 813       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 814           definitelyWrittenResults.get(fn);
 815
 816       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 817           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 818       for (int i = 0; i < fn.numPrev(); i++) {
 819         FlatNode nn = fn.getPrev(i);
 820         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 821             definitelyWrittenResults.get(nn);
 822         if (dwIn != null) {
 823           merge(curr, dwIn);
 824         }
 825       }
 826
 827       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 828
 829       // if a new result, schedule forward nodes for analysis
 830       if (!curr.equals(prev)) {
 831         definitelyWrittenResults.put(fn, curr);
 832
 833         for (int i = 0; i < fn.numNext(); i++) {
 834           FlatNode nn = fn.getNext(i);
 835           if (loopIncElements.contains(nn)) {
 836             flatNodesToVisit.add(nn);
 837           }
 838
 839         }
 840       }
 841     }
 842   }
 843
 844   private void writtenAnalysis_nodeAction(FlatNode fn,
 845       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 846
 847     if (fn.equals(loopEntrance)) {
 848       // it reaches loop entrance: changes all flag to true
 849       Set<NTuple<Descriptor>> keySet = curr.keySet();
 850       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 851         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 852         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 853         if (pair != null) {
 854           Set<FlatNode> pairKeySet = pair.keySet();
 855           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 856             FlatNode pairKey = (FlatNode) iterator2.next();
 857             pair.put(pairKey, Boolean.TRUE);
 858           }
 859         }
 860       }
 861     } else {
 862       TempDescriptor lhs;
 863       TempDescriptor rhs;
 864       FieldDescriptor fld;
 865
 866       switch (fn.kind()) {
 867       case FKind.FlatOpNode: {
 868         FlatOpNode fon = (FlatOpNode) fn;
 869         lhs = fon.getDest();
 870         rhs = fon.getLeft();
 871
 872         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 873         if (!rhs.getType().isImmutable()) {
 874           mapHeapPath.put(lhs, rhsHeapPath);
 875         } else {
 876           if (fon.getOp().getOp() == Operation.ASSIGN) {
 877             // read(rhs)
 878             readValue(fn, rhsHeapPath, curr);
 879           }
 880           // write(lhs)
 881           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 882           removeHeapPath(curr, lhsHeapPath);
 883         }
 884       }
 885         break;
 886
 887       case FKind.FlatLiteralNode: {
 888         FlatLiteralNode fln = (FlatLiteralNode) fn;
 889         lhs = fln.getDst();
 890
 891         // write(lhs)
 892         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 893         removeHeapPath(curr, lhsHeapPath);
 894
 895       }
 896         break;
 897
 898       case FKind.FlatFieldNode:
 899       case FKind.FlatElementNode: {
 900
 901         FlatFieldNode ffn = (FlatFieldNode) fn;
 902         lhs = ffn.getDst();
 903         rhs = ffn.getSrc();
 904         fld = ffn.getField();
 905
 906         // read field
 907         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 908         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 909         fldHeapPath.add(fld);
 910
 911         if (fld.getType().isImmutable()) {
 912           readValue(fn, fldHeapPath, curr);
 913         }
 914
 915         // propagate rhs's heap path to the lhs
 916         mapHeapPath.put(lhs, fldHeapPath);
 917
 918       }
 919         break;
 920
 921       case FKind.FlatSetFieldNode:
 922       case FKind.FlatSetElementNode: {
 923
 924         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 925         lhs = fsfn.getDst();
 926         fld = fsfn.getField();
 927
 928         // write(field)
 929         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 930         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 931         fldHeapPath.add(fld);
 932         removeHeapPath(curr, fldHeapPath);
 933
 934       }
 935         break;
 936
 937       case FKind.FlatCall: {
 938         FlatCall fc = (FlatCall) fn;
 939         bindHeapPathCallerArgWithCaleeParam(fc);
 940
 941         // add <hp,statement,false> in which hp is an element of
 942         // READ_bound set
 943         // of callee: callee has 'read' requirement!
 944         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 945           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 946
 947           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 948           if (gen == null) {
 949             gen = new Hashtable<FlatNode, Boolean>();
 950             curr.put(read, gen);
 951           }
 952           Boolean currentStatus = gen.get(fn);
 953           if (currentStatus == null) {
 954             gen.put(fn, Boolean.FALSE);
 955           } else {
 956             checkFlag(currentStatus.booleanValue(), fn, read);
 957           }
 958         }
 959
 960         // removes <hp,statement,flag> if hp is an element of
 961         // OVERWRITE_bound
 962         // set of callee. it means that callee will overwrite it
 963         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 964           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 965           removeHeapPath(curr, write);
 966         }
 967       }
 968         break;
 969
 970       }
 971     }
 972
 973   }
 974
 975   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 976       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 977     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 978     if (gen == null) {
 979       gen = new Hashtable<FlatNode, Boolean>();
 980       curr.put(hp, gen);
 981     }
 982     Boolean currentStatus = gen.get(fn);
 983     if (currentStatus == null) {
 984       gen.put(fn, Boolean.FALSE);
 985     } else {
 986       checkFlag(currentStatus.booleanValue(), fn, hp);
 987     }
 988
 989   }
 990
 991   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 992       NTuple<Descriptor> hp) {
 993
 994     // removes all of heap path that starts with prefix 'hp'
 995     // since any reference overwrite along heap path gives overwriting side
 996     // effects on the value
 997
 998     Set<NTuple<Descriptor>> keySet = curr.keySet();
 999     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1000       NTuple<Descriptor> key = iter.next();
1001       if (key.startsWith(hp)) {
1002         curr.put(key, new Hashtable<FlatNode, Boolean>());
1003       }
1004     }
1005
1006   }
1007
1008   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1009     // compute all possible callee set
1010     // transform all READ/OVERWRITE set from the any possible
1011     // callees to the
1012     // caller
1013
1014     calleeUnionBoundReadSet.clear();
1015     calleeIntersectBoundOverWriteSet.clear();
1016
1017     MethodDescriptor mdCallee = fc.getMethod();
1018     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1019     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1020     TypeDescriptor typeDesc = fc.getThis().getType();
1021     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1022
1023     // create mapping from arg idx to its heap paths
1024     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1025         new Hashtable<Integer, NTuple<Descriptor>>();
1026
1027     // arg idx is starting from 'this' arg
1028     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1029     if (thisHeapPath == null) {
1030       // method is called without creating new flat node representing 'this'
1031       thisHeapPath = new NTuple<Descriptor>();
1032       thisHeapPath.add(fc.getThis());
1033     }
1034
1035     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1036
1037     for (int i = 0; i < fc.numArgs(); i++) {
1038       TempDescriptor arg = fc.getArg(i);
1039       NTuple<Descriptor> argHeapPath = computePath(arg);
1040       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1041     }
1042
1043     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1044       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1045       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1046
1047       // binding caller's args and callee's params
1048
1049       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1050       if (calleeReadSet == null) {
1051         calleeReadSet = new HashSet<NTuple<Descriptor>>();
1052         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1053       }
1054       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1055       if (calleeOverWriteSet == null) {
1056         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1057         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1058       }
1059
1060       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1061           new Hashtable<Integer, TempDescriptor>();
1062       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1063         TempDescriptor param = calleeFlatMethod.getParameter(i);
1064         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1065       }
1066
1067       Set<NTuple<Descriptor>> calleeBoundReadSet =
1068           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1069       // union of the current read set and the current callee's
1070       // read set
1071       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1072       Set<NTuple<Descriptor>> calleeBoundWriteSet =
1073           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1074       // intersection of the current overwrite set and the current
1075       // callee's
1076       // overwrite set
1077       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1078     }
1079
1080   }
1081
1082   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1083     if (booleanValue) {
1084       throw new Error(
1085           "There is a variable, which is reachable through references "
1086               + hp
1087               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1088               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1089               + fn.getNumLine());
1090     }
1091   }
1092
1093   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1094       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1095
1096     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1097     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1098       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1099       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1100
1101       Set<FlatNode> pairKeySet = inPair.keySet();
1102       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1103         FlatNode pairKey = (FlatNode) iterator2.next();
1104         Boolean inFlag = inPair.get(pairKey);
1105
1106         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1107         if (currPair == null) {
1108           currPair = new Hashtable<FlatNode, Boolean>();
1109           curr.put(inKey, currPair);
1110         }
1111
1112         Boolean currFlag = currPair.get(pairKey);
1113         // by default, flag is set by false
1114         if (currFlag == null) {
1115           currFlag = Boolean.FALSE;
1116         }
1117         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1118         currPair.put(pairKey, currFlag);
1119       }
1120
1121     }
1122
1123   }
1124
1125   private void methodReadOverWriteAnalysis() {
1126     // perform method READ/OVERWRITE analysis
1127     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1128     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1129
1130     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1131
1132     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1133         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1134
1135     // no need to analyze method having ssjava loop
1136     methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1137
1138     // current descriptors to visit in fixed-point interprocedural analysis,
1139     // prioritized by
1140     // dependency in the call graph
1141     methodDescriptorsToVisitStack.clear();
1142
1143     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1144     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1145
1146     while (!descriptorListToAnalyze.isEmpty()) {
1147       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1148       methodDescriptorsToVisitStack.add(md);
1149     }
1150
1151     // analyze scheduled methods until there are no more to visit
1152     while (!methodDescriptorsToVisitStack.isEmpty()) {
1153       // start to analyze leaf node
1154       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1155       FlatMethod fm = state.getMethodFlat(md);
1156
1157       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1158       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1159
1160       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1161
1162       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1163       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1164
1165       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1166         mapFlatMethodToRead.put(fm, readSet);
1167         mapFlatMethodToOverWrite.put(fm, overWriteSet);
1168
1169         // results for callee changed, so enqueue dependents caller for
1170         // further
1171         // analysis
1172         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1173         while (depsItr.hasNext()) {
1174           MethodDescriptor methodNext = depsItr.next();
1175           if (!methodDescriptorsToVisitStack.contains(methodNext)
1176               && methodDescriptorToVistSet.contains(methodNext)) {
1177             methodDescriptorsToVisitStack.add(methodNext);
1178           }
1179
1180         }
1181
1182       }
1183
1184     }
1185
1186   }
1187
1188   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1189       Set<NTuple<Descriptor>> overWriteSet) {
1190     if (state.SSJAVADEBUG) {
1191       System.out.println("Definitely written Analyzing: " + fm);
1192     }
1193
1194     // intraprocedural analysis
1195     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1196     flatNodesToVisit.add(fm);
1197
1198     while (!flatNodesToVisit.isEmpty()) {
1199       FlatNode fn = flatNodesToVisit.iterator().next();
1200       flatNodesToVisit.remove(fn);
1201
1202       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1203
1204       for (int i = 0; i < fn.numPrev(); i++) {
1205         FlatNode prevFn = fn.getPrev(i);
1206         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1207         if (in != null) {
1208           merge(curr, in);
1209         }
1210       }
1211
1212       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1213
1214       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1215       if (!curr.equals(writtenSetPrev)) {
1216         mapFlatNodeToWrittenSet.put(fn, curr);
1217         for (int i = 0; i < fn.numNext(); i++) {
1218           FlatNode nn = fn.getNext(i);
1219           flatNodesToVisit.add(nn);
1220         }
1221       }
1222
1223     }
1224
1225   }
1226
1227   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1228       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1229     TempDescriptor lhs;
1230     TempDescriptor rhs;
1231     FieldDescriptor fld;
1232
1233     switch (fn.kind()) {
1234     case FKind.FlatMethod: {
1235
1236       // set up initial heap paths for method parameters
1237       FlatMethod fm = (FlatMethod) fn;
1238       for (int i = 0; i < fm.numParameters(); i++) {
1239         TempDescriptor param = fm.getParameter(i);
1240         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1241         heapPath.add(param);
1242         mapHeapPath.put(param, heapPath);
1243       }
1244     }
1245       break;
1246
1247     case FKind.FlatOpNode: {
1248       FlatOpNode fon = (FlatOpNode) fn;
1249       // for a normal assign node, need to propagate lhs's heap path to
1250       // rhs
1251       if (fon.getOp().getOp() == Operation.ASSIGN) {
1252         rhs = fon.getLeft();
1253         lhs = fon.getDest();
1254
1255         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1256         if (rhsHeapPath != null) {
1257           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1258         }
1259
1260       }
1261     }
1262       break;
1263
1264     case FKind.FlatFieldNode:
1265     case FKind.FlatElementNode: {
1266
1267       // y=x.f;
1268
1269       FlatFieldNode ffn = (FlatFieldNode) fn;
1270       lhs = ffn.getDst();
1271       rhs = ffn.getSrc();
1272       fld = ffn.getField();
1273
1274       // set up heap path
1275       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1276       if (srcHeapPath != null) {
1277         // if lhs srcHeapPath is null, it means that it is not reachable from
1278         // callee's parameters. so just ignore it
1279
1280         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1281         readingHeapPath.add(fld);
1282         mapHeapPath.put(lhs, readingHeapPath);
1283
1284         // read (x.f)
1285         if (fld.getType().isImmutable()) {
1286           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1287           if (!writtenSet.contains(readingHeapPath)) {
1288             readSet.add(readingHeapPath);
1289           }
1290         }
1291
1292         // need to kill hp(x.f) from WT
1293         writtenSet.remove(readingHeapPath);
1294       }
1295
1296     }
1297       break;
1298
1299     case FKind.FlatSetFieldNode:
1300     case FKind.FlatSetElementNode: {
1301
1302       // x.f=y;
1303       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1304       lhs = fsfn.getDst();
1305       fld = fsfn.getField();
1306       rhs = fsfn.getSrc();
1307
1308       // set up heap path
1309       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1310       if (lhsHeapPath != null) {
1311         // if lhs heap path is null, it means that it is not reachable from
1312         // callee's parameters. so just ignore it
1313         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1314         newHeapPath.add(fld);
1315         mapHeapPath.put(fld, newHeapPath);
1316
1317         // write(x.f)
1318         // need to add hp(y) to WT
1319         writtenSet.add(newHeapPath);
1320       }
1321
1322     }
1323       break;
1324
1325     case FKind.FlatCall: {
1326
1327       FlatCall fc = (FlatCall) fn;
1328
1329       bindHeapPathCallerArgWithCaleeParam(fc);
1330
1331       // add heap path, which is an element of READ_bound set and is not
1332       // an
1333       // element of WT set, to the caller's READ set
1334       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1335         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1336         if (!writtenSet.contains(read)) {
1337           readSet.add(read);
1338         }
1339       }
1340       writtenSet.removeAll(calleeUnionBoundReadSet);
1341
1342       // add heap path, which is an element of OVERWRITE_bound set, to the
1343       // caller's WT set
1344       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1345         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1346         writtenSet.add(write);
1347       }
1348
1349     }
1350       break;
1351
1352     case FKind.FlatExit: {
1353       // merge the current written set with OVERWRITE set
1354       merge(overWriteSet, writtenSet);
1355     }
1356       break;
1357
1358     }
1359
1360   }
1361
1362   private void mergeSharedLocationAnaylsis(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
1363       Set<Hashtable<NTuple<Descriptor>, SharedLocState>> inSet) {
1364
1365     if (inSet.size() == 0) {
1366       return;
1367     }
1368
1369     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1370         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1371
1372     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1373
1374       Hashtable<NTuple<Descriptor>, SharedLocState> inTable =
1375           (Hashtable<NTuple<Descriptor>, SharedLocState>) inIterator.next();
1376
1377       Set<NTuple<Descriptor>> keySet = inTable.keySet();
1378
1379       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1380         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1381         SharedLocState inState = inTable.get(hpKey);
1382
1383         SharedLocState currState = curr.get(hpKey);
1384         if (currState == null) {
1385           currState = new SharedLocState();
1386           curr.put(hpKey, currState);
1387         }
1388         currState.merge(inState);
1389
1390         Set<Location> locSet = inState.getMap().keySet();
1391         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1392           Location loc = (Location) iterator2.next();
1393           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1394           boolean inFlag = pair.getSecond().booleanValue();
1395
1396           Pair<NTuple<Descriptor>, Location> flagKey =
1397               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1398           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1399           if (current == null) {
1400             current = new Boolean(true);
1401           }
1402           boolean newInFlag = current.booleanValue() & inFlag;
1403           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1404         }
1405
1406       }
1407
1408     }
1409
1410     // merge flag status
1411     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1412     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1413       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1414       SharedLocState currState = curr.get(hpKey);
1415       Set<Location> locKeySet = currState.getMap().keySet();
1416       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1417         Location locKey = (Location) iterator2.next();
1418         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1419         boolean currentFlag = pair.getSecond().booleanValue();
1420         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1421         if (inFlag != null) {
1422           boolean newFlag = currentFlag | inFlag.booleanValue();
1423           if (currentFlag != newFlag) {
1424             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1425           }
1426         }
1427       }
1428     }
1429
1430   }
1431
1432   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1433     if (curr.isEmpty()) {
1434       // WrittenSet has a special initial value which covers all possible
1435       // elements
1436       // For the first time of intersection, we can take all previous set
1437       curr.addAll(in);
1438     } else {
1439       // otherwise, current set is the intersection of the two sets
1440       curr.retainAll(in);
1441     }
1442
1443   }
1444
1445   // combine two heap path
1446   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1447     NTuple<Descriptor> combined = new NTuple<Descriptor>();
1448
1449     for (int i = 0; i < callerIn.size(); i++) {
1450       combined.add(callerIn.get(i));
1451     }
1452
1453     // the first element of callee's heap path represents parameter
1454     // so we skip the first one since it is already added from caller's heap
1455     // path
1456     for (int i = 1; i < calleeIn.size(); i++) {
1457       combined.add(calleeIn.get(i));
1458     }
1459
1460     return combined;
1461   }
1462
1463   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1464       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1465       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1466
1467     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1468
1469     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1470     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1471       Integer idx = (Integer) iterator.next();
1472
1473       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1474       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1475
1476       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1477         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1478         if (element.startsWith(calleeParam)) {
1479           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1480           boundedCalleeSet.add(boundElement);
1481         }
1482
1483       }
1484
1485     }
1486     return boundedCalleeSet;
1487
1488   }
1489
1490   // Borrowed it from disjoint analysis
1491   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1492
1493     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1494
1495     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1496
1497     Iterator<MethodDescriptor> itr = toSort.iterator();
1498     while (itr.hasNext()) {
1499       MethodDescriptor d = itr.next();
1500
1501       if (!discovered.contains(d)) {
1502         dfsVisit(d, toSort, sorted, discovered);
1503       }
1504     }
1505
1506     return sorted;
1507   }
1508
1509   // While we're doing DFS on call graph, remember
1510   // dependencies for efficient queuing of methods
1511   // during interprocedural analysis:
1512   //
1513   // a dependent of a method decriptor d for this analysis is:
1514   // 1) a method or task that invokes d
1515   // 2) in the descriptorsToAnalyze set
1516   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1517       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1518
1519     discovered.add(md);
1520
1521     Iterator itr = callGraph.getCallerSet(md).iterator();
1522     while (itr.hasNext()) {
1523       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1524       // only consider callers in the original set to analyze
1525       if (!toSort.contains(dCaller)) {
1526         continue;
1527       }
1528       if (!discovered.contains(dCaller)) {
1529         addDependent(md, // callee
1530             dCaller // caller
1531         );
1532
1533         dfsVisit(dCaller, toSort, sorted, discovered);
1534       }
1535     }
1536
1537     // for leaf-nodes last now!
1538     sorted.addLast(md);
1539   }
1540
1541   // a dependent of a method decriptor d for this analysis is:
1542   // 1) a method or task that invokes d
1543   // 2) in the descriptorsToAnalyze set
1544   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1545     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1546     if (deps == null) {
1547       deps = new HashSet<MethodDescriptor>();
1548     }
1549     deps.add(caller);
1550     mapDescriptorToSetDependents.put(callee, deps);
1551   }
1552
1553   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1554     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1555     if (deps == null) {
1556       deps = new HashSet<MethodDescriptor>();
1557       mapDescriptorToSetDependents.put(callee, deps);
1558     }
1559     return deps;
1560   }
1561
1562   private NTuple<Descriptor> computePath(TempDescriptor td) {
1563     // generate proper path fot input td
1564     // if td is local variable, it just generate one element tuple path
1565     if (mapHeapPath.containsKey(td)) {
1566       return mapHeapPath.get(td);
1567     } else {
1568       NTuple<Descriptor> path = new NTuple<Descriptor>();
1569       path.add(td);
1570       return path;
1571     }
1572   }
1573
1574 }