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