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