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