Robust/src/IR/Flat/RuntimeConflictResolver.java

   1 package IR.Flat;
   2 import java.io.File;
   3 import java.io.FileNotFoundException;
   4 import java.io.PrintWriter;
   5 import java.util.ArrayList;
   6 import java.util.Collection;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.Set;
  11 import Analysis.Disjoint.*;
  12 import IR.TypeDescriptor;
  13
  14 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
  15  * by generating C-code to either rule out the conflict at runtime or resolve one.
  16  *
  17  * How to Use:
  18  * 1) Instantiate singleton object (String input is to specify output dir)
  19  * 2) Call setGlobalEffects setGlobalEffects(Hashtable<Taint, Set<Effect>> ) ONCE
  20  * 3) Input SESE blocks, for each block:
  21  *    3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable<Taint, Set<Effect>>) for the seseBlock
  22  *    3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C
  23  * 4) Call void close()
  24  * Note: All computation is done upon closing the object. Steps 1-3 only input data
  25  */
  26 public class RuntimeConflictResolver {
  27   public static final boolean javaDebug = true;
  28   public static final boolean cSideDebug = false;
  29
  30   private PrintWriter cFile;
  31   private PrintWriter headerFile;
  32   private static final String hashAndQueueCFileDir = "oooJava/";
  33   //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
  34   //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
  35   private Hashtable<Taint, Integer> doneTaints;
  36   private Hashtable<Taint, Set<Effect>> globalEffects;
  37   private Hashtable<Taint, Set<Effect>> globalConflicts;
  38   private ArrayList<TraversalInfo> toTraverse;
  39
  40   // initializing variables can be found in printHeader()
  41   private static final String getAllocSiteInC = "->allocsite";
  42   private static final String queryVistedHashtable = "hashRCRInsert";
  43   private static final String addToQueueInC = "enqueueRCRQueue(";
  44   private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
  45   private static final String clearQueue = "resetRCRQueue()";
  46   // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
  47   private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
  48   private static final String deallocVisitedHashTable = "hashRCRDelete()";
  49   private static final String resetVisitedHashTable = "hashRCRreset()";
  50
  51   //TODO find correct strings for these
  52   private static final String addCheckFromHashStructure = "checkFromHashStructure(";
  53   private static final String putWaitingQueueBlock = "putWaitingQueueBlock(";  //lifting of blocks will be done by hashtable.
  54   private static final String putIntoAllocQueue = "putIntoWaitingQ(";
  55   private static final int noConflict = 0;
  56   private static final int conflictButTraverserCanContinue = 1;
  57   private static final int conflictButTraverserCannotContinue = 2;
  58   private static final int allocQueueIsNotEmpty = 0;
  59
  60   // Hashtable provides fast access to heaproot # lookups
  61   private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
  62   private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
  63   private int traverserIDCounter;
  64   private int weaklyConnectedHRCounter;
  65   private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
  66   private EffectsTable effectsLookupTable;
  67
  68   public RuntimeConflictResolver(String buildir)
  69   throws FileNotFoundException {
  70     String outputFile = buildir + "RuntimeConflictResolver";
  71
  72     cFile = new PrintWriter(new File(outputFile + ".c"));
  73     headerFile = new PrintWriter(new File(outputFile + ".h"));
  74
  75     cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
  76         + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
  77     cFile.println("#include \"classdefs.h\"");
  78     cFile.println("#include \"RuntimeConflictResolver.h\"");
  79     cFile.println("#include \"hashStructure.h\"");
  80
  81     headerFile.println("#ifndef __3_RCR_H_");
  82     headerFile.println("#define __3_RCR_H_");
  83
  84     doneTaints = new Hashtable<Taint, Integer>();
  85     connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
  86
  87     traverserIDCounter = 1;
  88     weaklyConnectedHRCounter = 0;
  89     pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
  90     toTraverse = new ArrayList<TraversalInfo>();
  91     globalConflicts = new Hashtable<Taint, Set<Effect>>();
  92     //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
  93   }
  94
  95   public void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
  96     globalEffects = effects;
  97
  98     if(javaDebug) {
  99       System.out.println("============EFFECTS LIST AS PASSED IN============");
 100       for(Taint t: globalEffects.keySet()) {
 101         System.out.println("For Taint " + t);
 102         for(Effect e: globalEffects.get(t)) {
 103           System.out.println("\t" + e);
 104         }
 105       }
 106       System.out.println("====================END  LIST====================");
 107     }
 108   }
 109
 110   /*
 111    * Basic Strategy:
 112    * 1) Get global effects and conflicts
 113    * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
 114    *     2a) Use Effects to verify we can access something (reads)
 115    *     2b) Use conflicts to mark conflicts (read/write/strongupdate)
 116    *     2c) At second level of hash, store Heaproots that can cause conflicts at the field
 117    * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots.
 118    * 4) Build internal representation of the rgs (pruned)
 119    * 5) Print c methods by walking internal representation
 120    */
 121
 122   public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
 123     //Add to todo list
 124     toTraverse.add(new TraversalInfo(rblock, rg));
 125
 126     //Add to Global conflicts
 127     for(Taint t: conflicts.keySet()) {
 128       if(globalConflicts.containsKey(t)) {
 129         globalConflicts.get(t).addAll(conflicts.get(t));
 130       } else {
 131         globalConflicts.put(t, conflicts.get(t));
 132       }
 133     }
 134   }
 135
 136
 137   public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc,
 138       ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
 139     toTraverse.add(new TraversalInfo(fn, rg, tempDesc));
 140
 141     for(Taint t: conflicts.keySet()) {
 142       if(globalConflicts.containsKey(t)) {
 143         globalConflicts.get(t).addAll(conflicts.get(t));
 144       } else {
 145         globalConflicts.put(t, conflicts.get(t));
 146       }
 147     }
 148   }
 149
 150   private void traverseSESEBlock(FlatSESEEnterNode rblock,
 151       ReachGraph rg) {
 152     Collection<TempDescriptor> inVars = rblock.getInVarSet();
 153
 154     if (inVars.size() == 0)
 155       return;
 156
 157     // For every non-primitive variable, generate unique method
 158     // Special Note: The Criteria for executing printCMethod in this loop should match
 159     // exactly the criteria in buildcode.java to invoke the generated C method(s).
 160     for (TempDescriptor invar : inVars) {
 161       TypeDescriptor type = invar.getType();
 162       if(type == null || type.isPrimitive()) {
 163         continue;
 164       }
 165
 166       //created stores nodes with specific alloc sites that have been traversed while building
 167       //internal data structure. It is later traversed sequentially to find inset variables and
 168       //build output code.
 169       Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
 170       VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 171       Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
 172       if (taint == null) {
 173         printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
 174         return;
 175       }
 176
 177       //This is to prevent duplicate traversals from being generated
 178       if(doneTaints.containsKey(taint))
 179         return;
 180
 181       doneTaints.put(taint, traverserIDCounter++);
 182       createConcreteGraph(effectsLookupTable, created, varNode, taint);
 183
 184
 185       //This will add the taint to the printout, there will be NO duplicates (checked above)
 186       if(!created.isEmpty()) {
 187         //TODO change invocation to new format
 188         //rblock.addInVarForDynamicCoarseConflictResolution(invar);
 189         pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
 190       }
 191     }
 192   }
 193
 194   private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
 195     TypeDescriptor type = invar.getType();
 196     if(type == null || type.isPrimitive()) {
 197       return;
 198     }
 199     Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
 200     VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 201     Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
 202
 203     if (taint == null) {
 204       printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
 205       return;
 206     }
 207
 208     if(doneTaints.containsKey(taint))
 209       return;
 210
 211     doneTaints.put(taint, traverserIDCounter++);
 212     createConcreteGraph(effectsLookupTable, created, varNode, taint);
 213
 214     if (!created.isEmpty()) {
 215       pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
 216     }
 217   }
 218
 219   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
 220     String flatname;
 221     if(fn instanceof FlatSESEEnterNode) {
 222       flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
 223     } else {
 224       flatname = fn.toString();
 225     }
 226
 227     return "traverse___" + removeInvalidChars(invar.getSafeSymbol()) +
 228     removeInvalidChars(flatname) + "___("+varString+");";
 229   }
 230
 231   public String removeInvalidChars(String in) {
 232     StringBuilder s = new StringBuilder(in);
 233     for(int i = 0; i < s.length(); i++) {
 234       if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '=') {
 235         s.deleteCharAt(i);
 236         i--;
 237       }
 238     }
 239     return s.toString();
 240   }
 241
 242   public void close() {
 243     buildEffectsLookupStructure();
 244     runAllTraverserals();
 245
 246     //prints out all generated code
 247     for(TaintAndInternalHeapStructure ths: pendingPrintout) {
 248       printCMethod(ths.nodesInHeap, ths.t);
 249     }
 250
 251     //Prints out the master traverser Invocation that'll call all other traverser
 252     //based on traverserID
 253     printMasterTraverserInvocation();
 254
 255     //TODO this is only temporary, remove when thread local vars implemented.
 256     createMasterHashTableArray();
 257
 258     // Adds Extra supporting methods
 259     cFile.println("void initializeStructsRCR() {\n  " + mallocVisitedHashtable + ";\n  " + clearQueue + ";\n}");
 260     cFile.println("void destroyRCR() {\n  " + deallocVisitedHashTable + ";\n}");
 261
 262     headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
 263     headerFile.println("#endif\n");
 264
 265     cFile.close();
 266     headerFile.close();
 267   }
 268
 269   //Builds Effects Table and runs the analysis on them to get weakly connected HRs
 270   //SPECIAL NOTE: Only runs after we've taken all the conflicts
 271   private void buildEffectsLookupStructure(){
 272     effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
 273     effectsLookupTable.runAnaylsis();
 274     enumerateHeaproots();
 275   }
 276
 277   private void runAllTraverserals() {
 278     for(TraversalInfo t: toTraverse) {
 279       printDebug(javaDebug, "Running Traversal a traversal on " + t.f);
 280
 281       if(t.f instanceof FlatSESEEnterNode) {
 282         traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg);
 283       } else {
 284         if(t.invar == null) {
 285           System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
 286         } else {
 287           traverseStallSite(t.f, t.invar, t.rg);
 288         }
 289       }
 290
 291     }
 292   }
 293
 294   //TODO: This is only temporary, remove when thread local variables are functional.
 295   private void createMasterHashTableArray() {
 296     headerFile.println("void createAndFillMasterHashStructureArray();");
 297     cFile.println("void createAndFillMasterHashStructureArray() {\n" +
 298                 "  rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
 299
 300     for(int i = 0; i < weaklyConnectedHRCounter; i++) {
 301       cFile.println("  allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");");
 302     }
 303     cFile.println("}");
 304   }
 305
 306   //This will print the traverser invocation that takes in a traverserID and
 307   //starting ptr
 308   private void printMasterTraverserInvocation() {
 309     headerFile.println("\nint traverse(void * startingPtr, int traverserID);");
 310     cFile.println("\nint traverse(void * startingPtr, int traverserID) {");
 311     cFile.println(" switch(traverserID) {");
 312
 313     for(Taint t: doneTaints.keySet()) {
 314       cFile.println("  case " + doneTaints.get(t)+ ":");
 315       if(t.isRBlockTaint()) {
 316         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getSESE()));
 317       } else if (t.isStallSiteTaint()){
 318         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getStallSite()));
 319       } else {
 320         System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
 321       }
 322     }
 323
 324     if(RuntimeConflictResolver.cSideDebug) {
 325       cFile.println("  default:\n    printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n    break;");
 326     } else {
 327       cFile.println("  default:\n    break;");
 328     }
 329
 330     cFile.println(" }");
 331     cFile.println("}");
 332   }
 333
 334   private void createConcreteGraph(
 335       EffectsTable table,
 336       Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
 337       VariableNode varNode,
 338       Taint t) {
 339
 340     // if table is null that means there's no conflicts, therefore we need not
 341     // create a traversal
 342     if (table == null)
 343       return;
 344
 345     Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
 346     while (possibleEdges.hasNext()) {
 347       RefEdge edge = possibleEdges.next();
 348       assert edge != null;
 349
 350       ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
 351       AllocSite rootKey = singleRoot.allocSite;
 352
 353       if (!created.containsKey(rootKey)) {
 354         created.put(rootKey, singleRoot);
 355         createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
 356       }
 357     }
 358   }
 359
 360   //This code is the old way of generating an effects lookup table.
 361   //The new way is to instantiate an EffectsGroup
 362   @Deprecated
 363   private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
 364       Taint taint, Hashtable<Taint,
 365       Set<Effect>> effects,
 366       Hashtable<Taint, Set<Effect>> conflicts) {
 367     if(taint == null)
 368       return null;
 369
 370     Set<Effect> localEffects = effects.get(taint);
 371     Set<Effect> localConflicts = conflicts.get(taint);
 372
 373     //Debug Code for manually checking effects
 374     if(javaDebug) {
 375       printEffectsAndConflictsSets(taint, localEffects, localConflicts);
 376     }
 377
 378     if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
 379       return null;
 380
 381     Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
 382
 383     for (Effect e : localEffects) {
 384       boolean conflict = localConflicts.contains(e);
 385       AllocSite key = e.getAffectedAllocSite();
 386       EffectsGroup myEffects = lookupTable.get(key);
 387
 388       if(myEffects == null) {
 389         myEffects = new EffectsGroup();
 390         lookupTable.put(key, myEffects);
 391       }
 392
 393       if(e.getField().getType().isPrimitive()) {
 394         if(conflict) {
 395           myEffects.addPrimitive(e, true);
 396         }
 397       }
 398       else {
 399         myEffects.addObjEffect(e, conflict);
 400       }
 401     }
 402
 403     return lookupTable;
 404   }
 405
 406   // Plan is to add stuff to the tree depth-first sort of way. That way, we can
 407   // propagate up conflicts
 408   private void createHelper(ConcreteRuntimeObjNode curr,
 409                             Iterator<RefEdge> edges,
 410                             Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
 411                             EffectsTable table,
 412                             Taint taint) {
 413     assert table != null;
 414     AllocSite parentKey = curr.allocSite;
 415     EffectsGroup currEffects = table.getEffects(parentKey, taint);
 416
 417     if (currEffects == null || currEffects.isEmpty())
 418       return;
 419
 420     //Handle Objects (and primitives if child is new)
 421     if(currEffects.hasObjectEffects()) {
 422       while(edges.hasNext()) {
 423         RefEdge edge = edges.next();
 424         String field = edge.getField();
 425         CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
 426         //If there are no effects, then there's no point in traversing this edge
 427         if(effectsForGivenField != null) {
 428           HeapRegionNode childHRN = edge.getDst();
 429           AllocSite childKey = childHRN.getAllocSite();
 430           boolean isNewChild = !created.containsKey(childKey);
 431           ConcreteRuntimeObjNode child;
 432
 433           if(isNewChild) {
 434             child = new ConcreteRuntimeObjNode(childHRN, false);
 435             created.put(childKey, child);
 436           } else {
 437             child = created.get(childKey);
 438           }
 439
 440           curr.addObjChild(field, child, effectsForGivenField);
 441
 442           if (effectsForGivenField.hasConflict()) {
 443             child.hasPotentialToBeIncorrectDueToConflict = true;
 444             propogateObjConflict(curr, child);
 445           }
 446
 447           if(effectsForGivenField.hasReadEffect) {
 448             child.addReachableParent(curr);
 449
 450             //If isNewChild, flag propagation will be handled at recursive call
 451             if(isNewChild) {
 452               createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
 453             } else {
 454             //This makes sure that all conflicts below the child is propagated up the referencers.
 455               if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
 456                 propogatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
 457               }
 458
 459               if(child.decendantsObjConflict) {
 460                 propogateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
 461               }
 462             }
 463           }
 464         }
 465       }
 466     }
 467
 468     //Handles primitives
 469     curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
 470     if(currEffects.hasPrimitiveConflicts()) {
 471       //Reminder: primitive conflicts are abstracted to object.
 472       propogatePrimConflict(curr, curr);
 473     }
 474   }
 475
 476   // This will propagate the conflict up the data structure.
 477   private void propogateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 478     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 479       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 480           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
 481       {
 482         referencer.decendantsObjConflict = true;
 483         propogateObjConflict(referencer, pointsOfAccess);
 484       }
 485     }
 486   }
 487
 488   private void propogateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 489     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 490       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 491           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
 492       {
 493         referencer.decendantsObjConflict = true;
 494         propogateObjConflict(referencer, pointOfAccess);
 495       }
 496     }
 497   }
 498
 499   private void propogatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 500     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 501       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 502           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
 503       {
 504         referencer.decendantsPrimConflict = true;
 505         propogatePrimConflict(referencer, pointsOfAccess);
 506       }
 507     }
 508   }
 509
 510   private void propogatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 511     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 512       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 513           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
 514       {
 515         referencer.decendantsPrimConflict = true;
 516         propogatePrimConflict(referencer, pointOfAccess);
 517       }
 518     }
 519   }
 520
 521
 522
 523   /*
 524    * This method generates a C method for every inset variable and rblock.
 525    *
 526    * The C method works by generating a large switch statement that will run the appropriate
 527    * checking code for each object based on its allocation site. The switch statement is
 528    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 529    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 530    *  and we came across it while checking through it's referencer. Because of this property,
 531    *  conflicts will be signaled by the referencer; the only exception is the inset variable which can
 532    *  signal a conflict within itself.
 533    */
 534
 535   private void printCMethod(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, Taint taint) {
 536     //This hash table keeps track of all the case statements generated. Although it may seem a bit much
 537     //for its purpose, I think it may come in handy later down the road to do it this way.
 538     //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
 539     String inVar = taint.getVar().getSafeSymbol();
 540     String rBlock;
 541
 542     if(taint.isStallSiteTaint()) {
 543       rBlock = taint.getStallSite().toString();
 544     } else if(taint.isRBlockTaint()) {
 545       rBlock = taint.getSESE().getPrettyIdentifier();
 546     } else {
 547       System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
 548       return;
 549     }
 550
 551     Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
 552
 553     //Generate C cases
 554     for (ConcreteRuntimeObjNode node : created.values()) {
 555       if (!cases.containsKey(node.allocSite) && (
 556           //insetVariable case
 557           (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 558           //non-inline-able code cases
 559           (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 560           //Cases where resumes are possible
 561           (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict)) {
 562
 563         printDebug(javaDebug, node.allocSite + " qualified for case statement");
 564         addChecker(taint, node, cases, null, "ptr", 0);
 565       }
 566     }
 567     //IMPORTANT: remember to change getTraverserInvocation if you change the line below
 568     String methodName = "void traverse___" + removeInvalidChars(inVar) +
 569                         removeInvalidChars(rBlock) + "___(void * InVar)";
 570
 571     cFile.println(methodName + " {");
 572     headerFile.println(methodName + ";");
 573
 574     if(cSideDebug) {
 575       cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
 576     }
 577
 578     if(cases.size() == 0) {
 579       cFile.println(" return; }");
 580     }
 581     else {
 582       //clears queue and hashtable that keeps track of where we've been.
 583       cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
 584
 585       //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
 586       cFile.println("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable
 587           + "(ptr);\n do {");
 588
 589       cFile.println("  switch(ptr->allocsite) {");
 590
 591       for(AllocSite singleCase: cases.keySet())
 592         cFile.append(cases.get(singleCase));
 593
 594       cFile.println("  default:\n    break; ");
 595       cFile.println("  }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}\n}\n");
 596     }
 597     cFile.flush();
 598   }
 599
 600   /*
 601    * addChecker creates a case statement for every object that is either an inset variable
 602    * or has multiple referencers (incoming edges). Else it just prints the checker for that object
 603    * so that its processing can be pushed up to the referencer node.
 604    */
 605   private void addChecker(Taint taint,
 606                           ConcreteRuntimeObjNode node,
 607                           Hashtable<AllocSite,StringBuilder> cases,
 608                           StringBuilder possibleContinuingCase,
 609                           String prefix,
 610                           int depth) {
 611     StringBuilder currCase = possibleContinuingCase;
 612     // We don't need a case statement for things with either 1 incoming or 0 out
 613     // going edges, because they can be processed when checking the parent.
 614     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 615        (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 616         node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict) {
 617       assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
 618       currCase = new StringBuilder();
 619       cases.put(node.allocSite, currCase);
 620       currCase.append("  case " + node.getAllocationSite() + ": {\n");
 621     }
 622     //either currCase is continuing off a parent case or is its own.
 623     assert currCase !=null;
 624     boolean primConfRead=false;
 625     boolean primConfWrite=false;
 626     boolean objConfRead=false;
 627     boolean objConfWrite=false;
 628
 629     //Primitives Test
 630     for(String field: node.primitiveConflictingFields.keySet()) {
 631       CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
 632       primConfRead|=effect.hasReadConflict;
 633       primConfWrite|=effect.hasWriteConflict;
 634     }
 635
 636     //Object Reference Test
 637     for(ObjRef ref: node.objectRefs) {
 638       CombinedObjEffects effect=ref.myEffects;
 639       objConfRead|=effect.hasReadConflict;
 640       objConfWrite|=effect.hasWriteConflict;
 641     }
 642
 643     if (objConfRead) {
 644       currCase.append("    if(");
 645       checkWaitingQueue(currCase, taint,  node);
 646       currCase.append("||");
 647     }
 648
 649     //Do call if we need it.
 650     if(primConfWrite||objConfWrite) {
 651       int heaprootNum = connectedHRHash.get(taint).id;
 652       assert heaprootNum != -1;
 653       int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 654       int traverserID = doneTaints.get(taint);
 655       currCase.append("rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+","+traverserID+",NULL,NULL)");
 656     } else if (primConfRead||objConfRead) {
 657       int heaprootNum = connectedHRHash.get(taint).id;
 658       assert heaprootNum != -1;
 659       int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 660       int traverserID = doneTaints.get(taint);
 661       currCase.append("rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+","+traverserID+",NULL,NULL)");
 662     }
 663
 664     if(objConfRead) {
 665       currCase.append(") {\n");
 666       putIntoWaitingQueue(currCase, taint, node, prefix);
 667       currCase.append("    break;\n");
 668       currCase.append("    }\n");
 669     } else if(primConfRead||primConfWrite||objConfWrite) {
 670       currCase.append(";\n");
 671     }
 672
 673     //Conflicts
 674     for(ObjRef ref: node.objectRefs) {
 675       // Will only process edge if there is some sort of conflict with the Child
 676       if (ref.hasConflictsDownThisPath()) {
 677         String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
 678         int pdepth=depth+1;
 679         String currPtr = "myPtr" + pdepth;
 680         String structType = ref.child.original.getType().getSafeSymbol();
 681         currCase.append("    struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
 682
 683
 684         // Checks if the child exists and has allocsite matching the conflict
 685         currCase.append("    if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
 686
 687         if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
 688           // Checks if we have visited the child before
 689
 690           currCase.append("    if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
 691           if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
 692             addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
 693           }
 694           else {
 695             currCase.append("      " + addToQueueInC + childPtr + ");\n ");
 696           }
 697
 698           currCase.append("    }\n");
 699         }
 700         //one more brace for the opening if
 701         if(ref.hasDirectObjConflict()) {
 702           currCase.append("   }\n");
 703         }
 704
 705         currCase.append("  }\n ");
 706       }
 707     }
 708
 709     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 710        (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 711        (node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict)) {
 712       currCase.append("  }\n  break;\n");
 713     }
 714   }
 715
 716   //This method will touch the waiting queues if necessary.
 717   //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
 718   private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
 719     Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
 720
 721     currCase.append("    int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
 722     currCase.append("    if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
 723     checkWaitingQueue(currCase, t,  node);
 724     currCase.append(") {\n");
 725     //If cannot continue, then add all the undetermined references that lead from this child, including self.
 726     //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
 727     putIntoWaitingQueue(currCase, t, node, ptr);
 728
 729     ConcreteRuntimeObjNode related;
 730     while(it.hasNext()) {
 731       related = it.next();
 732       //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
 733       putIntoWaitingQueue(currCase, t, related, ptr);
 734     }
 735   }
 736
 737   /*
 738   private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
 739     currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
 740   }
 741
 742   private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
 743     currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
 744   }
 745   */
 746
 747   private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
 748       Hashtable<Taint, Set<Effect>> effects) {
 749     Set<Taint> taints = effects.keySet();
 750     for (Taint t : taints) {
 751       FlatSESEEnterNode sese = t.getSESE();
 752       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 753         return t;
 754       }
 755     }
 756     return null;
 757   }
 758
 759
 760   private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
 761       Hashtable<Taint, Set<Effect>> effects) {
 762     Set<Taint> taints = effects.keySet();
 763     for (Taint t : taints) {
 764       FlatNode flatnode = t.getStallSite();
 765       if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
 766         return t;
 767       }
 768     }
 769     return null;
 770   }
 771
 772   private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
 773       Set<Effect> localConflicts) {
 774     System.out.println("#### List of Effects/Conflicts ####");
 775     System.out.println("For Taint " + taint);
 776     System.out.println("Effects");
 777     if(localEffects != null) {
 778       for(Effect e: localEffects) {
 779        System.out.println(e);
 780       }
 781     }
 782     System.out.println("Conflicts");
 783     if(localConflicts != null) {
 784       for(Effect e: localConflicts) {
 785         System.out.println(e);
 786       }
 787     }
 788   }
 789
 790   private void printDebug(boolean guard, String debugStatements) {
 791     if(guard)
 792       System.out.println(debugStatements);
 793   }
 794
 795   //TODO finish this once waitingQueue side is figured out
 796   private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
 797     //Method looks like this: void put(int allocSiteID,  x
 798     //struct WaitingQueue * queue, //get this from hashtable
 799     //int effectType, //not so sure we would actually need this one.
 800     //void * resumePtr,
 801     //int traverserID);  }
 802     int heaprootNum = connectedHRHash.get(taint).id;
 803     assert heaprootNum != -1;
 804     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 805     int traverserID = doneTaints.get(taint);
 806
 807     //NOTE if the C-side is changed, this will have to be changed accordingly
 808     //TODO make sure this matches c-side
 809     sb.append("      putIntoWaitingQueue("+allocSiteID+", " +
 810                 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
 811                 resumePtr + ", " +
 812                 traverserID+");\n");
 813   }
 814
 815   //TODO finish waitingQueue side
 816   /**
 817    * Inserts check to see if waitingQueue is occupied.
 818    *
 819    * On C-side, =0 means empty queue, else occupied.
 820    */
 821   private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
 822     //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
 823     assert sb != null && taint !=null;
 824     int heaprootNum = connectedHRHash.get(taint).id;
 825     assert heaprootNum != -1;
 826     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 827
 828     sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
 829   }
 830
 831   private void enumerateHeaproots() {
 832     //reset numbers jsut in case
 833     weaklyConnectedHRCounter = 0;
 834     num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
 835
 836     for(Taint t: connectedHRHash.keySet()) {
 837       if(connectedHRHash.get(t).id == -1) {
 838         WeaklyConectedHRGroup hg = connectedHRHash.get(t);
 839         hg.id = weaklyConnectedHRCounter;
 840         num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
 841         weaklyConnectedHRCounter++;
 842       }
 843     }
 844   }
 845
 846   private void printoutTable(EffectsTable table) {
 847
 848     System.out.println("==============EFFECTS TABLE PRINTOUT==============");
 849     for(AllocSite as: table.table.keySet()) {
 850       System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
 851
 852       BucketOfEffects boe = table.table.get(as);
 853
 854       if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
 855         System.out.println("\t\tPotentially conflicting roots: ");
 856         for(String key: boe.potentiallyConflictingRoots.keySet()) {
 857           System.out.println("\t\t-Field: " + key);
 858           System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
 859         }
 860       }
 861       for(Taint t: boe.taint2EffectsGroup.keySet()) {
 862         System.out.println("\t\t For Taint " + t);
 863         EffectsGroup eg = boe.taint2EffectsGroup.get(t);
 864
 865         if(eg.hasPrimitiveConflicts()) {
 866           System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
 867           for(String field: eg.primitiveConflictingFields.keySet()) {
 868             System.out.print(field + " ");
 869           }
 870           System.out.println();
 871         }
 872         for(String fieldKey: eg.myEffects.keySet()) {
 873           CombinedObjEffects ce = eg.myEffects.get(fieldKey);
 874           System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
 875           System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 876               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 877               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 878           for(Effect ef: ce.originalEffects) {
 879             System.out.println("\t" + ef);
 880           }
 881         }
 882       }
 883
 884     }
 885
 886   }
 887
 888   private class EffectsGroup {
 889     Hashtable<String, CombinedObjEffects> myEffects;
 890     Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
 891
 892     public EffectsGroup() {
 893       myEffects = new Hashtable<String, CombinedObjEffects>();
 894       primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
 895     }
 896
 897     public void addPrimitive(Effect e, boolean conflict) {
 898       CombinedObjEffects effects;
 899       if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
 900         effects = new CombinedObjEffects();
 901         primitiveConflictingFields.put(e.getField().getSymbol(), effects);
 902       }
 903       effects.add(e, conflict);
 904     }
 905
 906     public void addObjEffect(Effect e, boolean conflict) {
 907       CombinedObjEffects effects;
 908       if((effects = myEffects.get(e.getField().getSymbol())) == null) {
 909         effects = new CombinedObjEffects();
 910         myEffects.put(e.getField().getSymbol(), effects);
 911       }
 912       effects.add(e, conflict);
 913     }
 914
 915     public boolean isEmpty() {
 916       return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
 917     }
 918
 919     public boolean hasPrimitiveConflicts(){
 920       return !primitiveConflictingFields.isEmpty();
 921     }
 922
 923     public CombinedObjEffects getPrimEffect(String field) {
 924       return primitiveConflictingFields.get(field);
 925     }
 926
 927     public boolean hasObjectEffects() {
 928       return !myEffects.isEmpty();
 929     }
 930
 931     public CombinedObjEffects getObjEffect(String field) {
 932       return myEffects.get(field);
 933     }
 934   }
 935
 936   //Is the combined effects for all effects with the same affectedAllocSite and field
 937   private class CombinedObjEffects {
 938     ArrayList<Effect> originalEffects;
 939
 940     public boolean hasReadEffect;
 941     public boolean hasWriteEffect;
 942     public boolean hasStrongUpdateEffect;
 943
 944     public boolean hasReadConflict;
 945     public boolean hasWriteConflict;
 946     public boolean hasStrongUpdateConflict;
 947
 948
 949     public CombinedObjEffects() {
 950       originalEffects = new ArrayList<Effect>();
 951
 952       hasReadEffect = false;
 953       hasWriteEffect = false;
 954       hasStrongUpdateEffect = false;
 955
 956       hasReadConflict = false;
 957       hasWriteConflict = false;
 958       hasStrongUpdateConflict = false;
 959     }
 960
 961     public boolean add(Effect e, boolean conflict) {
 962       if(!originalEffects.add(e))
 963         return false;
 964
 965       switch(e.getType()) {
 966       case Effect.read:
 967         hasReadEffect = true;
 968         hasReadConflict = conflict;
 969         break;
 970       case Effect.write:
 971         hasWriteEffect = true;
 972         hasWriteConflict = conflict;
 973         break;
 974       case Effect.strongupdate:
 975         hasStrongUpdateEffect = true;
 976         hasStrongUpdateConflict = conflict;
 977         break;
 978       default:
 979         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
 980         assert false;
 981         break;
 982       }
 983       return true;
 984     }
 985
 986     public boolean hasConflict() {
 987       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
 988     }
 989   }
 990
 991   //This will keep track of a reference
 992   private class ObjRef {
 993     String field;
 994     int allocSite;
 995     CombinedObjEffects myEffects;
 996
 997     //This keeps track of the parent that we need to pass by inorder to get
 998     //to the conflicting child (if there is one).
 999     ConcreteRuntimeObjNode child;
1000
1001     public ObjRef(String fieldname,
1002                   ConcreteRuntimeObjNode ref,
1003                   CombinedObjEffects myEffects) {
1004       field = fieldname;
1005       allocSite = ref.getAllocationSite();
1006       child = ref;
1007
1008       this.myEffects = myEffects;
1009     }
1010
1011     public boolean hasConflictsDownThisPath() {
1012       return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1013     }
1014
1015     public boolean hasDirectObjConflict() {
1016       return myEffects.hasConflict();
1017     }
1018   }
1019
1020   private class ConcreteRuntimeObjNode {
1021     ArrayList<ObjRef> objectRefs;
1022     Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1023     HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1024     HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1025     //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1026     HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1027     boolean decendantsPrimConflict;
1028     boolean decendantsObjConflict;
1029     boolean hasPotentialToBeIncorrectDueToConflict;
1030     boolean isInsetVar;
1031     AllocSite allocSite;
1032     HeapRegionNode original;
1033
1034     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
1035       objectRefs = new ArrayList<ObjRef>();
1036       primitiveConflictingFields = null;
1037       parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1038       parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1039       enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1040       allocSite = me.getAllocSite();
1041       original = me;
1042       isInsetVar = isInVar;
1043       decendantsPrimConflict = false;
1044       decendantsObjConflict = false;
1045       hasPotentialToBeIncorrectDueToConflict = false;
1046     }
1047
1048     public void addReachableParent(ConcreteRuntimeObjNode curr) {
1049       parentsWithReadToNode.add(curr);
1050     }
1051
1052     @Override
1053     public boolean equals(Object obj) {
1054       return original.equals(obj);
1055     }
1056
1057     public int getAllocationSite() {
1058       return allocSite.getUniqueAllocSiteID();
1059     }
1060
1061     public int getNumOfReachableParents() {
1062       return parentsThatWillLeadToConflicts.size();
1063     }
1064
1065     public boolean hasPrimitiveConflicts() {
1066       return !primitiveConflictingFields.isEmpty();
1067     }
1068
1069     public boolean decendantsConflict() {
1070       return decendantsPrimConflict || decendantsObjConflict;
1071     }
1072
1073
1074     //returns true if at least one of the objects in points of access has been added
1075     public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1076       boolean addedNew = false;
1077       for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1078         if(dec != null && dec != this){
1079           addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1080         }
1081       }
1082
1083       return addedNew;
1084     }
1085
1086     public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1087       if(pointOfAccess != null && pointOfAccess != this){
1088         return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1089       }
1090
1091       return false;
1092     }
1093
1094     public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1095       ObjRef ref = new ObjRef(field, child, ce);
1096       objectRefs.add(ref);
1097     }
1098
1099     public String toString() {
1100       return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1101               " decCon="+decendantsObjConflict+
1102               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1103     }
1104   }
1105
1106   private class EffectsTable {
1107     private Hashtable<AllocSite, BucketOfEffects> table;
1108
1109     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1110         Hashtable<Taint, Set<Effect>> conflicts) {
1111       table = new Hashtable<AllocSite, BucketOfEffects>();
1112
1113       // rehash all effects (as a 5-tuple) by their affected allocation site
1114       for (Taint t : effects.keySet()) {
1115         Set<Effect> localConflicts = conflicts.get(t);
1116         for (Effect e : effects.get(t)) {
1117           BucketOfEffects bucket;
1118           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1119             bucket = new BucketOfEffects();
1120             table.put(e.getAffectedAllocSite(), bucket);
1121           }
1122           printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1123           bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1124         }
1125       }
1126     }
1127
1128     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1129       //This would get the proper bucket of effects and then get all the effects
1130       //for a parent for a specific taint
1131       return table.get(parentKey).taint2EffectsGroup.get(taint);
1132     }
1133
1134     // Run Analysis will walk the data structure and figure out the weakly
1135     // connected heap roots.
1136     public void runAnaylsis() {
1137       if(javaDebug) {
1138         printoutTable(this);
1139       }
1140
1141       //TODO is there a higher performance way to do this?
1142       for(AllocSite key: table.keySet()) {
1143         BucketOfEffects effects = table.get(key);
1144         //make sure there are actually conflicts in the bucket
1145         if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1146           for(String field: effects.potentiallyConflictingRoots.keySet()){
1147             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1148             //For simplicity, we just create a new group and add everything to it instead of
1149             //searching through all of them for the largest group and adding everyone in.
1150             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1151             group.add(taints); //This will automatically add the taint to the connectedHRhash
1152           }
1153         }
1154       }
1155     }
1156   }
1157
1158   private class WeaklyConectedHRGroup {
1159     HashSet<Taint> connectedHRs;
1160     //This is to keep track of unique waitingQueue positions for each allocsite.
1161     Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1162     int waitingQueueCounter;
1163     int id;
1164
1165     public WeaklyConectedHRGroup() {
1166       connectedHRs = new HashSet<Taint>();
1167       id = -1; //this will be later modified
1168       waitingQueueCounter = 0;
1169       allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1170     }
1171
1172     public void add(ArrayList<Taint> list) {
1173       for(Taint t: list) {
1174         this.add(t);
1175       }
1176     }
1177
1178     public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1179       if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1180         return allocSiteToWaitingQueueMap.get(node.allocSite);
1181       }
1182       else {
1183         allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1184         return waitingQueueCounter++;
1185       }
1186     }
1187
1188     public void add(Taint t) {
1189       connectedHRs.add(t);
1190       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1191       connectedHRHash.put(t, this); //put new group into hash
1192       //If the taint was already in another group, move all its buddies over.
1193       if(oldGroup != this && oldGroup != null) {
1194         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1195         Taint relatedTaint;
1196
1197         while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1198           this.add(relatedTaint);
1199         }
1200       }
1201     }
1202   }
1203
1204   //This is a class that stores all the effects for an affected allocation site
1205   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1206   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1207   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1208   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1209   //field.
1210   private class BucketOfEffects {
1211     // This table is used for lookup while creating the traversal.
1212     Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1213
1214     //This table is used to help identify weakly connected groups: Contains ONLY
1215     //conflicting effects AND is only initialized when needed
1216     //String stores the field
1217     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1218
1219     public BucketOfEffects() {
1220       taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1221     }
1222
1223     public void add(Taint t, Effect e, boolean conflict) {
1224       EffectsGroup effectsForGivenTaint;
1225
1226       if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1227         effectsForGivenTaint = new EffectsGroup();
1228         taint2EffectsGroup.put(t, effectsForGivenTaint);
1229       }
1230
1231       if (e.getField().getType().isPrimitive()) {
1232         if (conflict) {
1233           effectsForGivenTaint.addPrimitive(e, true);
1234         }
1235       } else {
1236         effectsForGivenTaint.addObjEffect(e, conflict);
1237       }
1238
1239       if(conflict) {
1240         if(potentiallyConflictingRoots == null) {
1241           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1242         }
1243
1244         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1245         if(taintsForField == null) {
1246           taintsForField = new ArrayList<Taint>();
1247           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1248         }
1249
1250         if(!taintsForField.contains(t)) {
1251           taintsForField.add(t);
1252         }
1253       }
1254     }
1255   }
1256
1257   private class TaintAndInternalHeapStructure {
1258     public Taint t;
1259     public Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap;
1260
1261     public TaintAndInternalHeapStructure(Taint taint, Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap) {
1262       t = taint;
1263       this.nodesInHeap = nodesInHeap;
1264     }
1265   }
1266
1267   private class TraversalInfo {
1268     public FlatNode f;
1269     public ReachGraph rg;
1270     public TempDescriptor invar;
1271
1272     public TraversalInfo(FlatNode fn, ReachGraph g) {
1273       f = fn;
1274       rg =g;
1275       invar = null;
1276     }
1277
1278     public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {
1279       f = fn;
1280       rg =rg2;
1281       invar = tempDesc;
1282     }
1283   }
1284 }