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.addPrimative(e);
 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           }
 440           else {
 441             child = created.get(childKey);
 442           }
 443
 444           curr.addObjChild(field, child, effectsForGivenField);
 445
 446           if (effectsForGivenField.hasConflict()) {
 447             child.hasPotentialToBeIncorrectDueToConflict = true;
 448             propogateObjConflict(curr, child);
 449           }
 450
 451           if(effectsForGivenField.hasReadEffect) {
 452             child.addReachableParent(curr);
 453
 454             //If isNewChild, flag propagation will be handled at recursive call
 455             if(isNewChild) {
 456               createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
 457             }
 458             else {
 459             //This makes sure that all conflicts below the child is propagated up the referencers.
 460               if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
 461                 propogatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
 462               }
 463
 464               if(child.decendantsObjConflict) {
 465                 propogateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
 466               }
 467             }
 468           }
 469         }
 470       }
 471     }
 472
 473     //Handles primitives
 474     if(currEffects.hasPrimativeConflicts()) {
 475       curr.conflictingPrimitiveFields = currEffects.primativeConflictingFields;
 476       //Reminder: primitive conflicts are abstracted to object.
 477       curr.hasPotentialToBeIncorrectDueToConflict = true;
 478       propogatePrimConflict(curr, curr);
 479     }
 480   }
 481
 482   // This will propagate the conflict up the data structure.
 483   private void propogateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 484     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 485       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 486           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
 487       {
 488         referencer.decendantsObjConflict = true;
 489         propogateObjConflict(referencer, pointsOfAccess);
 490       }
 491     }
 492   }
 493
 494   private void propogateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 495     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 496       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 497           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
 498       {
 499         referencer.decendantsObjConflict = true;
 500         propogateObjConflict(referencer, pointOfAccess);
 501       }
 502     }
 503   }
 504
 505   private void propogatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 506     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 507       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 508           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
 509       {
 510         referencer.decendantsPrimConflict = true;
 511         propogatePrimConflict(referencer, pointsOfAccess);
 512       }
 513     }
 514   }
 515
 516   private void propogatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 517     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 518       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 519           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
 520       {
 521         referencer.decendantsPrimConflict = true;
 522         propogatePrimConflict(referencer, pointOfAccess);
 523       }
 524     }
 525   }
 526
 527
 528
 529   /*
 530    * This method generates a C method for every inset variable and rblock.
 531    *
 532    * The C method works by generating a large switch statement that will run the appropriate
 533    * checking code for each object based on its allocation site. The switch statement is
 534    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 535    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 536    *  and we came across it while checking through it's referencer. Because of this property,
 537    *  conflicts will be signaled by the referencer; the only exception is the inset variable which can
 538    *  signal a conflict within itself.
 539    */
 540
 541   private void printCMethod(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, Taint taint) {
 542     //This hash table keeps track of all the case statements generated. Although it may seem a bit much
 543     //for its purpose, I think it may come in handy later down the road to do it this way.
 544     //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
 545     String inVar = taint.getVar().getSafeSymbol();
 546     String rBlock;
 547
 548     if(taint.isStallSiteTaint()) {
 549       rBlock = taint.getStallSite().toString();
 550     } else if(taint.isRBlockTaint()) {
 551       rBlock = taint.getSESE().getPrettyIdentifier();
 552     } else {
 553       System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
 554       return;
 555     }
 556
 557     Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
 558
 559     //Generate C cases
 560     for (ConcreteRuntimeObjNode node : created.values()) {
 561       if (!cases.containsKey(node.allocSite) && (
 562           //insetVariable case
 563           (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 564           //non-inline-able code cases
 565           (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 566           //Cases where resumes are possible
 567           (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict)) {
 568
 569         printDebug(javaDebug, node.allocSite + " qualified for case statement");
 570         addChecker(taint, node, cases, null, "ptr", 0);
 571       }
 572     }
 573     //IMPORTANT: remember to change getTraverserInvocation if you change the line below
 574     String methodName = "void traverse___" + removeInvalidChars(inVar) +
 575                         removeInvalidChars(rBlock) + "___(void * InVar)";
 576
 577     cFile.println(methodName + " {");
 578     headerFile.println(methodName + ";");
 579
 580     if(cSideDebug) {
 581       cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
 582     }
 583
 584     if(cases.size() == 0) {
 585       cFile.println(" return; }");
 586     }
 587     else {
 588       //clears queue and hashtable that keeps track of where we've been.
 589       cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
 590
 591       //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
 592       cFile.println("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable
 593           + "(ptr);\n do {");
 594
 595       cFile.println("  switch(ptr->allocsite) {");
 596
 597       for(AllocSite singleCase: cases.keySet())
 598         cFile.append(cases.get(singleCase));
 599
 600       cFile.println("  default:\n    break; ");
 601       cFile.println("  }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}\n}\n");
 602     }
 603     cFile.flush();
 604   }
 605
 606   /*
 607    * addChecker creates a case statement for every object that is either an inset variable
 608    * or has multiple referencers (incoming edges). Else it just prints the checker for that object
 609    * so that its processing can be pushed up to the referencer node.
 610    */
 611   private void addChecker(Taint taint,
 612                           ConcreteRuntimeObjNode node,
 613                           Hashtable<AllocSite,StringBuilder> cases,
 614                           StringBuilder possibleContinuingCase,
 615                           String prefix,
 616                           int depth) {
 617     StringBuilder currCase = possibleContinuingCase;
 618     // We don't need a case statement for things with either 1 incoming or 0 out
 619     // going edges, because they can be processed when checking the parent.
 620     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 621        (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 622         node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict) {
 623       assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
 624       currCase = new StringBuilder();
 625       cases.put(node.allocSite, currCase);
 626       currCase.append("  case " + node.getAllocationSite() + ": {\n");
 627     }
 628     //either currCase is continuing off a parent case or is its own.
 629     assert currCase !=null;
 630
 631     //Primitives Test
 632     if(node.hasPrimitiveConflicts()) {
 633       //This will check hashstructure, if cannot continue, add all to waiting queue and break; s
 634       addCheckHashtableAndWaitingQ(currCase, taint, node, prefix, depth);
 635       currCase.append("      break;\n    }\n");
 636     }
 637
 638     //Conflicts
 639     for (ObjRef ref : node.objectRefs) {
 640       // Will only process edge if there is some sort of conflict with the Child
 641       if (ref.hasConflictsDownThisPath()) {
 642         String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
 643         int pdepth=depth+1;
 644         String currPtr = "myPtr" + pdepth;
 645         String structType = ref.child.original.getType().getSafeSymbol();
 646         currCase.append("    struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
 647
 648
 649         // Checks if the child exists and has allocsite matching the conflict
 650         currCase.append("    if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
 651         //Handles Direct Conflicts on child.
 652         if(ref.hasDirectObjConflict()) {
 653         //This method will touch the waiting queues if necessary.
 654           addCheckHashtableAndWaitingQ(currCase, taint, ref.child, childPtr, depth);
 655           //Else if we can continue continue.
 656           currCase.append("    } else {\n");
 657         }
 658
 659         //If there are no direct conflicts (determined by static + dynamic), finish check
 660         if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
 661           // Checks if we have visited the child before
 662
 663           currCase.append("    if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
 664           if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
 665             addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
 666           }
 667           else {
 668             currCase.append("      " + addToQueueInC + childPtr + ");\n ");
 669           }
 670
 671           currCase.append("    }\n");
 672         }
 673         //one more brace for the opening if
 674         if(ref.hasDirectObjConflict()) {
 675           currCase.append("   }\n");
 676         }
 677
 678         currCase.append("  }\n ");
 679       }
 680     }
 681
 682     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 683        (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 684        (node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict)) {
 685       currCase.append("  }\n  break;\n");
 686     }
 687   }
 688
 689   //This method will touch the waiting queues if necessary.
 690   //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
 691   private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
 692     Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
 693
 694     currCase.append("    int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
 695     currCase.append("    if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
 696     checkWaitingQueue(currCase, t,  node);
 697     currCase.append(") {\n");
 698     //If cannot continue, then add all the undetermined references that lead from this child, including self.
 699     //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
 700     putIntoWaitingQueue(currCase, t, node, ptr);
 701
 702     ConcreteRuntimeObjNode related;
 703     while(it.hasNext()) {
 704       related = it.next();
 705       //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
 706       putIntoWaitingQueue(currCase, t, related, ptr);
 707     }
 708   }
 709
 710   /*
 711   private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
 712     currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
 713   }
 714
 715   private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
 716     currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
 717   }
 718   */
 719
 720   private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
 721       Hashtable<Taint, Set<Effect>> effects) {
 722     Set<Taint> taints = effects.keySet();
 723     for (Taint t : taints) {
 724       FlatSESEEnterNode sese = t.getSESE();
 725       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 726         return t;
 727       }
 728     }
 729     return null;
 730   }
 731
 732
 733   private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
 734       Hashtable<Taint, Set<Effect>> effects) {
 735     Set<Taint> taints = effects.keySet();
 736     for (Taint t : taints) {
 737       FlatNode flatnode = t.getStallSite();
 738       if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
 739         return t;
 740       }
 741     }
 742     return null;
 743   }
 744
 745   private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
 746       Set<Effect> localConflicts) {
 747     System.out.println("#### List of Effects/Conflicts ####");
 748     System.out.println("For Taint " + taint);
 749     System.out.println("Effects");
 750     if(localEffects != null) {
 751       for(Effect e: localEffects) {
 752        System.out.println(e);
 753       }
 754     }
 755     System.out.println("Conflicts");
 756     if(localConflicts != null) {
 757       for(Effect e: localConflicts) {
 758         System.out.println(e);
 759       }
 760     }
 761   }
 762
 763   private void printDebug(boolean guard, String debugStatements) {
 764     if(guard)
 765       System.out.println(debugStatements);
 766   }
 767
 768   //TODO finish this once waitingQueue side is figured out
 769   private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
 770     //Method looks like this: void put(int allocSiteID,  x
 771     //struct WaitingQueue * queue, //get this from hashtable
 772     //int effectType, //not so sure we would actually need this one.
 773     //void * resumePtr,
 774     //int traverserID);  }
 775     int heaprootNum = connectedHRHash.get(taint).id;
 776     assert heaprootNum != -1;
 777     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 778     int traverserID = doneTaints.get(taint);
 779
 780     //NOTE if the C-side is changed, this will have to be changed accordingly
 781     //TODO make sure this matches c-side
 782     sb.append("      putIntoWaitingQueue("+allocSiteID+", " +
 783                 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
 784                 resumePtr + ", " +
 785                 traverserID+");\n");
 786   }
 787
 788   //TODO finish waitingQueue side
 789   /**
 790    * Inserts check to see if waitingQueue is occupied.
 791    *
 792    * On C-side, =0 means empty queue, else occupied.
 793    */
 794   private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
 795     //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
 796     assert sb != null && taint !=null;
 797     int heaprootNum = connectedHRHash.get(taint).id;
 798     assert heaprootNum != -1;
 799     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 800
 801     sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
 802   }
 803
 804   private void enumerateHeaproots() {
 805     //reset numbers jsut in case
 806     weaklyConnectedHRCounter = 0;
 807     num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
 808
 809     for(Taint t: connectedHRHash.keySet()) {
 810       if(connectedHRHash.get(t).id == -1) {
 811         WeaklyConectedHRGroup hg = connectedHRHash.get(t);
 812         hg.id = weaklyConnectedHRCounter;
 813         num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
 814         weaklyConnectedHRCounter++;
 815       }
 816     }
 817   }
 818
 819   private void printoutTable(EffectsTable table) {
 820
 821     System.out.println("==============EFFECTS TABLE PRINTOUT==============");
 822     for(AllocSite as: table.table.keySet()) {
 823       System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
 824
 825       BucketOfEffects boe = table.table.get(as);
 826
 827       if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
 828         System.out.println("\t\tPotentially conflicting roots: ");
 829         for(String key: boe.potentiallyConflictingRoots.keySet()) {
 830           System.out.println("\t\t-Field: " + key);
 831           System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
 832         }
 833       }
 834       for(Taint t: boe.taint2EffectsGroup.keySet()) {
 835         System.out.println("\t\t For Taint " + t);
 836         EffectsGroup eg = boe.taint2EffectsGroup.get(t);
 837
 838         if(eg.hasPrimativeConflicts()) {
 839           System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
 840           for(String field: eg.primativeConflictingFields) {
 841             System.out.print(field + " ");
 842           }
 843           System.out.println();
 844         }
 845         for(String fieldKey: eg.myEffects.keySet()) {
 846           CombinedObjEffects ce = eg.myEffects.get(fieldKey);
 847           System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
 848           System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 849               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 850               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 851           for(Effect ef: ce.originalEffects) {
 852             System.out.println("\t" + ef);
 853           }
 854         }
 855       }
 856
 857     }
 858
 859   }
 860
 861   private class EffectsGroup
 862   {
 863     Hashtable<String, CombinedObjEffects> myEffects;
 864     ArrayList<String> primativeConflictingFields;
 865
 866     public EffectsGroup() {
 867       myEffects = new Hashtable<String, CombinedObjEffects>();
 868       primativeConflictingFields = new ArrayList<String>();
 869     }
 870
 871     public void addPrimative(Effect e) {
 872       primativeConflictingFields.add(e.getField().toPrettyStringBrief());
 873     }
 874
 875     public void addObjEffect(Effect e, boolean conflict) {
 876       CombinedObjEffects effects;
 877       if((effects = myEffects.get(e.getField().getSymbol())) == null) {
 878         effects = new CombinedObjEffects();
 879         myEffects.put(e.getField().getSymbol(), effects);
 880       }
 881       effects.add(e, conflict);
 882     }
 883
 884     public boolean isEmpty() {
 885       return myEffects.isEmpty() && primativeConflictingFields.isEmpty();
 886     }
 887
 888     public boolean hasPrimativeConflicts(){
 889       return !primativeConflictingFields.isEmpty();
 890     }
 891
 892     public boolean hasObjectEffects() {
 893       return !myEffects.isEmpty();
 894     }
 895
 896     public CombinedObjEffects getObjEffect(String field) {
 897       return myEffects.get(field);
 898     }
 899   }
 900
 901   //Is the combined effects for all effects with the same affectedAllocSite and field
 902   private class CombinedObjEffects {
 903     ArrayList<Effect> originalEffects;
 904
 905     public boolean hasReadEffect;
 906     public boolean hasWriteEffect;
 907     public boolean hasStrongUpdateEffect;
 908
 909     public boolean hasReadConflict;
 910     public boolean hasWriteConflict;
 911     public boolean hasStrongUpdateConflict;
 912
 913
 914     public CombinedObjEffects() {
 915       originalEffects = new ArrayList<Effect>();
 916
 917       hasReadEffect = false;
 918       hasWriteEffect = false;
 919       hasStrongUpdateEffect = false;
 920
 921       hasReadConflict = false;
 922       hasWriteConflict = false;
 923       hasStrongUpdateConflict = false;
 924     }
 925
 926     public boolean add(Effect e, boolean conflict) {
 927       if(!originalEffects.add(e))
 928         return false;
 929
 930       switch(e.getType()) {
 931       case Effect.read:
 932         hasReadEffect = true;
 933         hasReadConflict = conflict;
 934         break;
 935       case Effect.write:
 936         hasWriteEffect = true;
 937         hasWriteConflict = conflict;
 938         break;
 939       case Effect.strongupdate:
 940         hasStrongUpdateEffect = true;
 941         hasStrongUpdateConflict = conflict;
 942         break;
 943       default:
 944         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
 945         assert false;
 946         break;
 947       }
 948       return true;
 949     }
 950
 951     public boolean hasConflict() {
 952       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
 953     }
 954   }
 955
 956   //This will keep track of a reference
 957   private class ObjRef {
 958     String field;
 959     int allocSite;
 960     CombinedObjEffects myEffects;
 961
 962     //This keeps track of the parent that we need to pass by inorder to get
 963     //to the conflicting child (if there is one).
 964     ConcreteRuntimeObjNode child;
 965
 966     public ObjRef(String fieldname,
 967                   ConcreteRuntimeObjNode ref,
 968                   CombinedObjEffects myEffects) {
 969       field = fieldname;
 970       allocSite = ref.getAllocationSite();
 971       child = ref;
 972
 973       this.myEffects = myEffects;
 974     }
 975
 976     public boolean hasConflictsDownThisPath() {
 977       return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
 978     }
 979
 980     public boolean hasDirectObjConflict() {
 981       return myEffects.hasConflict();
 982     }
 983   }
 984
 985   private class ConcreteRuntimeObjNode {
 986     ArrayList<ObjRef> objectRefs;
 987     ArrayList<String> conflictingPrimitiveFields;
 988     HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
 989     HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
 990     //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
 991     HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
 992     boolean decendantsPrimConflict;
 993     boolean decendantsObjConflict;
 994     boolean hasPotentialToBeIncorrectDueToConflict;
 995     boolean isInsetVar;
 996     AllocSite allocSite;
 997     HeapRegionNode original;
 998
 999     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
1000       objectRefs = new ArrayList<ObjRef>();
1001       conflictingPrimitiveFields = null;
1002       parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1003       parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1004       enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1005       allocSite = me.getAllocSite();
1006       original = me;
1007       isInsetVar = isInVar;
1008       decendantsPrimConflict = false;
1009       decendantsObjConflict = false;
1010       hasPotentialToBeIncorrectDueToConflict = false;
1011     }
1012
1013     public void addReachableParent(ConcreteRuntimeObjNode curr) {
1014       parentsWithReadToNode.add(curr);
1015     }
1016
1017     @Override
1018     public boolean equals(Object obj) {
1019       return original.equals(obj);
1020     }
1021
1022     public int getAllocationSite() {
1023       return allocSite.getUniqueAllocSiteID();
1024     }
1025
1026     public int getNumOfReachableParents() {
1027       return parentsThatWillLeadToConflicts.size();
1028     }
1029
1030     public boolean hasPrimitiveConflicts() {
1031       return conflictingPrimitiveFields != null;
1032     }
1033
1034     public boolean decendantsConflict() {
1035       return decendantsPrimConflict || decendantsObjConflict;
1036     }
1037
1038
1039     //returns true if at least one of the objects in points of access has been added
1040     public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1041       boolean addedNew = false;
1042       for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1043         if(dec != null && dec != this){
1044           addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1045         }
1046       }
1047
1048       return addedNew;
1049     }
1050
1051     public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1052       if(pointOfAccess != null && pointOfAccess != this){
1053         return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1054       }
1055
1056       return false;
1057     }
1058
1059     public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1060       ObjRef ref = new ObjRef(field, child, ce);
1061       objectRefs.add(ref);
1062     }
1063
1064     public String toString()
1065     {
1066       return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1067               " decCon="+decendantsObjConflict+
1068               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1069     }
1070   }
1071
1072   private class EffectsTable {
1073     private Hashtable<AllocSite, BucketOfEffects> table;
1074
1075     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1076         Hashtable<Taint, Set<Effect>> conflicts) {
1077       table = new Hashtable<AllocSite, BucketOfEffects>();
1078
1079       // rehash all effects (as a 5-tuple) by their affected allocation site
1080       for (Taint t : effects.keySet()) {
1081         Set<Effect> localConflicts = conflicts.get(t);
1082         for (Effect e : effects.get(t)) {
1083           BucketOfEffects bucket;
1084           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1085             bucket = new BucketOfEffects();
1086             table.put(e.getAffectedAllocSite(), bucket);
1087           }
1088           printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1089           bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1090         }
1091       }
1092     }
1093
1094     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1095       //This would get the proper bucket of effects and then get all the effects
1096       //for a parent for a specific taint
1097       return table.get(parentKey).taint2EffectsGroup.get(taint);
1098     }
1099
1100     // Run Analysis will walk the data structure and figure out the weakly
1101     // connected heap roots.
1102     public void runAnaylsis() {
1103       if(javaDebug) {
1104         printoutTable(this);
1105       }
1106
1107       //TODO is there a higher performance way to do this?
1108       for(AllocSite key: table.keySet()) {
1109         BucketOfEffects effects = table.get(key);
1110         //make sure there are actually conflicts in the bucket
1111         if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1112           for(String field: effects.potentiallyConflictingRoots.keySet()){
1113             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1114             //For simplicity, we just create a new group and add everything to it instead of
1115             //searching through all of them for the largest group and adding everyone in.
1116             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1117             group.add(taints); //This will automatically add the taint to the connectedHRhash
1118           }
1119         }
1120       }
1121     }
1122   }
1123
1124   private class WeaklyConectedHRGroup {
1125     HashSet<Taint> connectedHRs;
1126     //This is to keep track of unique waitingQueue positions for each allocsite.
1127     Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1128     int waitingQueueCounter;
1129     int id;
1130
1131     public WeaklyConectedHRGroup() {
1132       connectedHRs = new HashSet<Taint>();
1133       id = -1; //this will be later modified
1134       waitingQueueCounter = 0;
1135       allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1136     }
1137
1138     public void add(ArrayList<Taint> list) {
1139       for(Taint t: list) {
1140         this.add(t);
1141       }
1142     }
1143
1144     public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1145       if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1146         return allocSiteToWaitingQueueMap.get(node.allocSite);
1147       }
1148       else {
1149         allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1150         return waitingQueueCounter++;
1151       }
1152     }
1153
1154     public void add(Taint t) {
1155       connectedHRs.add(t);
1156       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1157       connectedHRHash.put(t, this); //put new group into hash
1158       //If the taint was already in another group, move all its buddies over.
1159       if(oldGroup != this && oldGroup != null) {
1160         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1161         Taint relatedTaint;
1162
1163         while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1164           this.add(relatedTaint);
1165         }
1166       }
1167     }
1168   }
1169
1170   //This is a class that stores all the effects for an affected allocation site
1171   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1172   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1173   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1174   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1175   //field.
1176   private class BucketOfEffects {
1177     // This table is used for lookup while creating the traversal.
1178     Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1179
1180     //This table is used to help identify weakly connected groups: Contains ONLY
1181     //conflicting effects AND is only initialized when needed
1182     //String stores the field
1183     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1184
1185     public BucketOfEffects() {
1186       taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1187     }
1188
1189     public void add(Taint t, Effect e, boolean conflict) {
1190       EffectsGroup effectsForGivenTaint;
1191
1192       if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1193         effectsForGivenTaint = new EffectsGroup();
1194         taint2EffectsGroup.put(t, effectsForGivenTaint);
1195       }
1196
1197       if (e.getField().getType().isPrimitive()) {
1198         if (conflict) {
1199           effectsForGivenTaint.addPrimative(e);
1200         }
1201       } else {
1202         effectsForGivenTaint.addObjEffect(e, conflict);
1203       }
1204
1205       if(conflict) {
1206         if(potentiallyConflictingRoots == null) {
1207           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1208         }
1209
1210         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1211         if(taintsForField == null) {
1212           taintsForField = new ArrayList<Taint>();
1213           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1214         }
1215
1216         if(!taintsForField.contains(t)) {
1217           taintsForField.add(t);
1218         }
1219       }
1220     }
1221   }
1222
1223   private class TaintAndInternalHeapStructure {
1224     public Taint t;
1225     public Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap;
1226
1227     public TaintAndInternalHeapStructure(Taint taint, Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap) {
1228       t = taint;
1229       this.nodesInHeap = nodesInHeap;
1230     }
1231   }
1232
1233   private class TraversalInfo {
1234     public FlatNode f;
1235     public ReachGraph rg;
1236     public TempDescriptor invar;
1237
1238     public TraversalInfo(FlatNode fn, ReachGraph g) {
1239       f = fn;
1240       rg =g;
1241       invar = null;
1242     }
1243
1244     public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {
1245       f = fn;
1246       rg =rg2;
1247       invar = tempDesc;
1248     }
1249   }
1250 }