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