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.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) && doneTaints.get(taint) != null)
 178         return;
 179
 180       doneTaints.put(taint, traverserIDCounter++);
 181       createConcreteGraph(effectsLookupTable, created, varNode, taint);
 182
 183
 184       //This will add the taint to the printout, there will be NO duplicates (checked above)
 185       if(!created.isEmpty()) {
 186         //TODO change invocation to new format
 187         //rblock.addInVarForDynamicCoarseConflictResolution(invar);
 188         pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
 189       }
 190     }
 191   }
 192
 193
 194   private void traverseStallSite(
 195       FlatNode enterNode,
 196       TempDescriptor invar,
 197       ReachGraph rg) {
 198     TypeDescriptor type = invar.getType();
 199     if(type == null || type.isPrimitive()) {
 200       return;
 201     }
 202     Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
 203     VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 204     Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
 205
 206     if (taint == null) {
 207       printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
 208       return;
 209     }
 210
 211     if(doneTaints.containsKey(taint) && doneTaints.get(taint) != null)
 212       return;
 213
 214     doneTaints.put(taint, traverserIDCounter++);
 215     createConcreteGraph(effectsLookupTable, created, varNode, taint);
 216
 217     if (!created.isEmpty()) {
 218       pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
 219     }
 220   }
 221
 222   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
 223     String flatname;
 224     if(fn instanceof FlatSESEEnterNode) {
 225       flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
 226     }
 227     else {
 228       flatname = fn.toString();
 229     }
 230
 231     return "traverse___" + removeInvalidChars(invar.getSafeSymbol()) +
 232     removeInvalidChars(flatname) + "___("+varString+");";
 233   }
 234
 235   public String removeInvalidChars(String in) {
 236     StringBuilder s = new StringBuilder(in);
 237     for(int i = 0; i < s.length(); i++) {
 238       if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '=') {
 239         s.deleteCharAt(i);
 240         i--;
 241       }
 242     }
 243     return s.toString();
 244   }
 245
 246   public void close() {
 247     buildEffectsLookupStructure();
 248     runAllTraverserals();
 249
 250     //prints out all generated code
 251     for(TaintAndInternalHeapStructure ths: pendingPrintout) {
 252       printCMethod(ths.nodesInHeap, ths.t);
 253     }
 254
 255     //Prints out the master traverser Invocation that'll call all other traverser
 256     //based on traverserID
 257     printMasterTraverserInvocation();
 258
 259     //TODO this is only temporary, remove when thread local vars implemented.
 260     createMasterHashTableArray();
 261
 262     // Adds Extra supporting methods
 263     cFile.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       }
 288       else {
 289         if(t.invar == null) {
 290           System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
 291         }
 292         else {
 293           traverseStallSite(t.f, t.invar, t.rg);
 294         }
 295       }
 296
 297     }
 298   }
 299
 300   //TODO: This is only temporary, remove when thread local variables are functional.
 301   private void createMasterHashTableArray() {
 302     headerFile.println("void createAndFillMasterHashStructureArray();");
 303     cFile.println("void createAndFillMasterHashStructureArray() {\n" +
 304                 "  createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
 305
 306     for(int i = 0; i < weaklyConnectedHRCounter; i++) {
 307       cFile.println("  allHashStructures["+i+"] = (HashStructure *) createhashTable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");}");
 308     }
 309     cFile.println("}");
 310   }
 311
 312   //This will print the traverser invocation that takes in a traverserID and
 313   //starting ptr
 314   private void printMasterTraverserInvocation() {
 315     headerFile.println("\nint traverse(void * startingPtr, int traverserID);");
 316     cFile.println("\nint traverse(void * startingPtr, int traverserID) {");
 317     cFile.println(" switch(traverserID) {");
 318
 319     for(Taint t: doneTaints.keySet()) {
 320       cFile.println("  case " + doneTaints.get(t)+ ":");
 321       if(t.isRBlockTaint()) {
 322         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getSESE()));
 323       }
 324       else if (t.isStallSiteTaint()){
 325         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getStallSite()));
 326       } else {
 327         System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
 328       }
 329     }
 330
 331     if(RuntimeConflictResolver.cSideDebug) {
 332       cFile.println("  default:\n    printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n    break;");
 333     } else {
 334       cFile.println("  default:\n    break;");
 335     }
 336
 337     cFile.println(" }");
 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.println(methodName + " {");
 584     headerFile.println(methodName + ";");
 585
 586     if(cSideDebug) {
 587       cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
 588     }
 589
 590     if(cases.size() == 0) {
 591       cFile.println(" return; }");
 592     }
 593     else {
 594       //clears queue and hashtable that keeps track of where we've been.
 595       cFile.println(clearQueue + "; " + resetVisitedHashTable + ";");
 596
 597       //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
 598       cFile.println("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;  if(InVar != NULL) { " + queryVistedHashtable
 599           + "ptr); do { ");
 600
 601       cFile.println("switch(ptr->allocsite) { ");
 602
 603       for(AllocSite singleCase: cases.keySet())
 604         cFile.append(cases.get(singleCase));
 605
 606       cFile.println(" default : break; ");
 607       cFile.println("}} 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 {\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 + ";\n");
 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; } \n");
 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 + "==" + ref.allocSite + ") { \n");
 658
 659
 660         //Handles Direct Conflicts on child.
 661         if(ref.hasDirectObjConflict()) {
 662         //This method will touch the waiting queues if necessary.
 663           addCheckHashtableAndWaitingQ(currCase, taint, ref.child, childPtr, depth);
 664           //Else if we can continue continue.
 665           currCase.append(" } else {\n");
 666         }
 667
 668         //If there are no direct conflicts (determined by static + dynamic), finish check
 669         if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
 670           // Checks if we have visited the child before
 671           currCase.append(" if(" + queryVistedHashtable + childPtr + ")) {\n");
 672           if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
 673             addChecker(taint, ref.child, cases, currCase, childPtr, depth + 1);
 674           }
 675           else {
 676             currCase.append(" " + addToQueueInC + childPtr + ");\n ");
 677           }
 678
 679           currCase.append(" }\n");
 680         }
 681         //one more brace for the opening if
 682         if(ref.hasDirectObjConflict()) {
 683           currCase.append(" }\n");
 684         }
 685
 686         currCase.append(" }\n ");
 687       }
 688     }
 689
 690     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 691        (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 692        (node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict)) {
 693       currCase.append(" } break;\n");
 694     }
 695   }
 696
 697   //This method will touch the waiting queues if necessary.
 698   //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
 699   private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
 700     Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
 701
 702     currCase.append("int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
 703     currCase.append("if(retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
 704     checkWaitingQueue(currCase, t,  node);
 705     currCase.append(") {\n");
 706     //If cannot continue, then add all the undetermined references that lead from this child, including self.
 707     //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
 708     putIntoWaitingQueue(currCase, t, node, ptr);
 709
 710     ConcreteRuntimeObjNode related;
 711     while(it.hasNext()) {
 712       related = it.next();
 713       //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
 714       putIntoWaitingQueue(currCase, t, related, ptr);
 715     }
 716   }
 717
 718   /*
 719   private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
 720     currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
 721   }
 722
 723   private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
 724     currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
 725   }
 726   */
 727
 728   private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
 729       Hashtable<Taint, Set<Effect>> effects) {
 730     Set<Taint> taints = effects.keySet();
 731     for (Taint t : taints) {
 732       FlatSESEEnterNode sese = t.getSESE();
 733       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 734         return t;
 735       }
 736     }
 737     return null;
 738   }
 739
 740
 741   private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
 742       Hashtable<Taint, Set<Effect>> effects) {
 743     Set<Taint> taints = effects.keySet();
 744     for (Taint t : taints) {
 745       FlatNode flatnode = t.getStallSite();
 746       if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
 747         return t;
 748       }
 749     }
 750     return null;
 751   }
 752
 753   private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
 754       Set<Effect> localConflicts) {
 755     System.out.println("#### List of Effects/Conflicts ####");
 756     System.out.println("For Taint " + taint);
 757     System.out.println("Effects");
 758     if(localEffects != null) {
 759       for(Effect e: localEffects) {
 760        System.out.println(e);
 761       }
 762     }
 763     System.out.println("Conflicts");
 764     if(localConflicts != null) {
 765       for(Effect e: localConflicts) {
 766         System.out.println(e);
 767       }
 768     }
 769   }
 770
 771   private void printDebug(boolean guard, String debugStatements) {
 772     if(guard)
 773       System.out.println(debugStatements);
 774   }
 775
 776   //TODO finish this once waitingQueue side is figured out
 777   private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
 778     //Method looks like this: void put(int allocSiteID,  x
 779     //struct WaitingQueue * queue, //get this from hashtable
 780     //int effectType, //not so sure we would actually need this one.
 781     //void * resumePtr,
 782     //int traverserID);  }
 783     int heaprootNum = connectedHRHash.get(taint).id;
 784     assert heaprootNum != -1;
 785     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 786     int traverserID = doneTaints.get(taint);
 787
 788     //NOTE if the C-side is changed, this will have to be changed accordingly
 789     //TODO make sure this matches c-side
 790     sb.append("put("+allocSiteID+", " +
 791                 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
 792                 resumePtr + ", " +
 793                 traverserID+");\n");
 794   }
 795
 796   //TODO finish waitingQueue side
 797   /**
 798    * Inserts check to see if waitingQueue is occupied.
 799    *
 800    * On C-side, =0 means empty queue, else occupied.
 801    */
 802   private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
 803     //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
 804     assert sb != null && taint !=null;
 805     int heaprootNum = connectedHRHash.get(taint).id;
 806     assert heaprootNum != -1;
 807     int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
 808
 809     sb.append(" (check(" + "allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
 810   }
 811
 812   private void enumerateHeaproots() {
 813     //reset numbers jsut in case
 814     weaklyConnectedHRCounter = 0;
 815     num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
 816
 817     for(Taint t: connectedHRHash.keySet()) {
 818       if(connectedHRHash.get(t).id == -1) {
 819         WeaklyConectedHRGroup hg = connectedHRHash.get(t);
 820         hg.id = weaklyConnectedHRCounter;
 821         num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
 822         weaklyConnectedHRCounter++;
 823       }
 824     }
 825   }
 826
 827   private void printoutTable(EffectsTable table) {
 828
 829     System.out.println("==============EFFECTS TABLE PRINTOUT==============");
 830     for(AllocSite as: table.table.keySet()) {
 831       System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
 832
 833       BucketOfEffects boe = table.table.get(as);
 834
 835       if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
 836         System.out.println("\t\tPotentially conflicting roots: ");
 837         for(String key: boe.potentiallyConflictingRoots.keySet()) {
 838           System.out.println("\t\t-Field: " + key);
 839           System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
 840         }
 841       }
 842       for(Taint t: boe.taint2EffectsGroup.keySet()) {
 843         System.out.println("\t\t For Taint " + t);
 844         EffectsGroup eg = boe.taint2EffectsGroup.get(t);
 845
 846         if(eg.hasPrimativeConflicts()) {
 847           System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
 848           for(String field: eg.primativeConflictingFields) {
 849             System.out.print(field + " ");
 850           }
 851           System.out.println();
 852         }
 853         for(String fieldKey: eg.myEffects.keySet()) {
 854           CombinedObjEffects ce = eg.myEffects.get(fieldKey);
 855           System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
 856           System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 857               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 858               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 859           for(Effect ef: ce.originalEffects) {
 860             System.out.println("\t" + ef);
 861           }
 862         }
 863       }
 864
 865     }
 866
 867   }
 868
 869   private class EffectsGroup
 870   {
 871     Hashtable<String, CombinedObjEffects> myEffects;
 872     ArrayList<String> primativeConflictingFields;
 873
 874     public EffectsGroup() {
 875       myEffects = new Hashtable<String, CombinedObjEffects>();
 876       primativeConflictingFields = new ArrayList<String>();
 877     }
 878
 879     public void addPrimative(Effect e) {
 880       primativeConflictingFields.add(e.getField().toPrettyStringBrief());
 881     }
 882
 883     public void addObjEffect(Effect e, boolean conflict) {
 884       CombinedObjEffects effects;
 885       if((effects = myEffects.get(e.getField().getSymbol())) == null) {
 886         effects = new CombinedObjEffects();
 887         myEffects.put(e.getField().getSymbol(), effects);
 888       }
 889       effects.add(e, conflict);
 890     }
 891
 892     public boolean isEmpty() {
 893       return myEffects.isEmpty() && primativeConflictingFields.isEmpty();
 894     }
 895
 896     public boolean hasPrimativeConflicts(){
 897       return !primativeConflictingFields.isEmpty();
 898     }
 899
 900     public boolean hasObjectEffects() {
 901       return !myEffects.isEmpty();
 902     }
 903
 904     public CombinedObjEffects getObjEffect(String field) {
 905       return myEffects.get(field);
 906     }
 907   }
 908
 909   //Is the combined effects for all effects with the same affectedAllocSite and field
 910   private class CombinedObjEffects {
 911     ArrayList<Effect> originalEffects;
 912
 913     public boolean hasReadEffect;
 914     public boolean hasWriteEffect;
 915     public boolean hasStrongUpdateEffect;
 916
 917     public boolean hasReadConflict;
 918     public boolean hasWriteConflict;
 919     public boolean hasStrongUpdateConflict;
 920
 921
 922     public CombinedObjEffects() {
 923       originalEffects = new ArrayList<Effect>();
 924
 925       hasReadEffect = false;
 926       hasWriteEffect = false;
 927       hasStrongUpdateEffect = false;
 928
 929       hasReadConflict = false;
 930       hasWriteConflict = false;
 931       hasStrongUpdateConflict = false;
 932     }
 933
 934     public boolean add(Effect e, boolean conflict) {
 935       if(!originalEffects.add(e))
 936         return false;
 937
 938       switch(e.getType()) {
 939       case Effect.read:
 940         hasReadEffect = true;
 941         hasReadConflict = conflict;
 942         break;
 943       case Effect.write:
 944         hasWriteEffect = true;
 945         hasWriteConflict = conflict;
 946         break;
 947       case Effect.strongupdate:
 948         hasStrongUpdateEffect = true;
 949         hasStrongUpdateConflict = conflict;
 950         break;
 951       default:
 952         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
 953         assert false;
 954         break;
 955       }
 956       return true;
 957     }
 958
 959     public boolean hasConflict() {
 960       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
 961     }
 962   }
 963
 964   //This will keep track of a reference
 965   private class ObjRef {
 966     String field;
 967     int allocSite;
 968     CombinedObjEffects myEffects;
 969
 970     //This keeps track of the parent that we need to pass by inorder to get
 971     //to the conflicting child (if there is one).
 972     ConcreteRuntimeObjNode child;
 973
 974     public ObjRef(String fieldname,
 975                   ConcreteRuntimeObjNode ref,
 976                   CombinedObjEffects myEffects) {
 977       field = fieldname;
 978       allocSite = ref.getAllocationSite();
 979       child = ref;
 980
 981       this.myEffects = myEffects;
 982     }
 983
 984     public boolean hasConflictsDownThisPath() {
 985       return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
 986     }
 987
 988     public boolean hasDirectObjConflict() {
 989       return myEffects.hasConflict();
 990     }
 991   }
 992
 993   private class ConcreteRuntimeObjNode {
 994     ArrayList<ObjRef> objectRefs;
 995     ArrayList<String> conflictingPrimitiveFields;
 996     HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
 997     HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
 998     //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
 999     HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1000     boolean decendantsPrimConflict;
1001     boolean decendantsObjConflict;
1002     boolean hasPotentialToBeIncorrectDueToConflict;
1003     boolean isInsetVar;
1004     AllocSite allocSite;
1005     HeapRegionNode original;
1006
1007     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
1008       objectRefs = new ArrayList<ObjRef>();
1009       conflictingPrimitiveFields = null;
1010       parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1011       parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1012       enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1013       allocSite = me.getAllocSite();
1014       original = me;
1015       isInsetVar = isInVar;
1016       decendantsPrimConflict = false;
1017       decendantsObjConflict = false;
1018       hasPotentialToBeIncorrectDueToConflict = false;
1019     }
1020
1021     public void addReachableParent(ConcreteRuntimeObjNode curr) {
1022       parentsWithReadToNode.add(curr);
1023     }
1024
1025     @Override
1026     public boolean equals(Object obj) {
1027       return original.equals(obj);
1028     }
1029
1030     public int getAllocationSite() {
1031       return allocSite.getUniqueAllocSiteID();
1032     }
1033
1034     public int getNumOfReachableParents() {
1035       return parentsThatWillLeadToConflicts.size();
1036     }
1037
1038     public boolean hasPrimitiveConflicts() {
1039       return conflictingPrimitiveFields != null;
1040     }
1041
1042     public boolean decendantsConflict() {
1043       return decendantsPrimConflict || decendantsObjConflict;
1044     }
1045
1046
1047     //returns true if at least one of the objects in points of access has been added
1048     public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1049       boolean addedNew = false;
1050       for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1051         if(dec != null && dec != this){
1052           addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1053         }
1054       }
1055
1056       return addedNew;
1057     }
1058
1059     public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1060       if(pointOfAccess != null && pointOfAccess != this){
1061         return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1062       }
1063
1064       return false;
1065     }
1066
1067     public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1068       ObjRef ref = new ObjRef(field, child, ce);
1069       objectRefs.add(ref);
1070     }
1071
1072     public String toString()
1073     {
1074       return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1075               " decCon="+decendantsObjConflict+
1076               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1077     }
1078   }
1079
1080   private class EffectsTable {
1081     private Hashtable<AllocSite, BucketOfEffects> table;
1082
1083     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1084         Hashtable<Taint, Set<Effect>> conflicts) {
1085       table = new Hashtable<AllocSite, BucketOfEffects>();
1086
1087       // rehash all effects (as a 5-tuple) by their affected allocation site
1088       for (Taint t : effects.keySet()) {
1089         Set<Effect> localConflicts = conflicts.get(t);
1090         for (Effect e : effects.get(t)) {
1091           BucketOfEffects bucket;
1092           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1093             bucket = new BucketOfEffects();
1094             table.put(e.getAffectedAllocSite(), bucket);
1095           }
1096           printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false));
1097           bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1098         }
1099       }
1100     }
1101
1102     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1103       //This would get the proper bucket of effects and then get all the effects
1104       //for a parent for a specific taint
1105       return table.get(parentKey).taint2EffectsGroup.get(taint);
1106     }
1107
1108     // Run Analysis will walk the data structure and figure out the weakly
1109     // connected heap roots.
1110     public void runAnaylsis() {
1111       if(javaDebug) {
1112         printoutTable(this);
1113       }
1114
1115       //TODO is there a higher performance way to do this?
1116       for(AllocSite key: table.keySet()) {
1117         BucketOfEffects effects = table.get(key);
1118         //make sure there are actually conflicts in the bucket
1119         if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1120           for(String field: effects.potentiallyConflictingRoots.keySet()){
1121             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1122             //For simplicity, we just create a new group and add everything to it instead of
1123             //searching through all of them for the largest group and adding everyone in.
1124             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1125             group.add(taints); //This will automatically add the taint to the connectedHRhash
1126           }
1127         }
1128       }
1129     }
1130   }
1131
1132   private class WeaklyConectedHRGroup {
1133     HashSet<Taint> connectedHRs;
1134     //This is to keep track of unique waitingQueue positions for each allocsite.
1135     Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1136     int waitingQueueCounter;
1137     int id;
1138
1139     public WeaklyConectedHRGroup() {
1140       connectedHRs = new HashSet<Taint>();
1141       id = -1; //this will be later modified
1142       waitingQueueCounter = 0;
1143       allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1144     }
1145
1146     public void add(ArrayList<Taint> list) {
1147       for(Taint t: list) {
1148         this.add(t);
1149       }
1150     }
1151
1152     public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1153       if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1154         return allocSiteToWaitingQueueMap.get(node.allocSite);
1155       }
1156       else {
1157         allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1158         return waitingQueueCounter++;
1159       }
1160     }
1161
1162     public void add(Taint t) {
1163       connectedHRs.add(t);
1164       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1165       connectedHRHash.put(t, this); //put new group into hash
1166       //If the taint was already in another group, move all its buddies over.
1167       if(oldGroup != this && oldGroup != null) {
1168         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1169         Taint relatedTaint;
1170
1171         while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1172           this.add(relatedTaint);
1173         }
1174       }
1175     }
1176   }
1177
1178   //This is a class that stores all the effects for an affected allocation site
1179   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1180   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1181   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1182   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1183   //field.
1184   private class BucketOfEffects {
1185     // This table is used for lookup while creating the traversal.
1186     Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1187
1188     //This table is used to help identify weakly connected groups: Contains ONLY
1189     //conflicting effects AND is only initialized when needed
1190     //String stores the field
1191     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1192
1193     public BucketOfEffects() {
1194       taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1195     }
1196
1197     public void add(Taint t, Effect e, boolean conflict) {
1198       EffectsGroup effectsForGivenTaint;
1199
1200       if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1201         effectsForGivenTaint = new EffectsGroup();
1202         taint2EffectsGroup.put(t, effectsForGivenTaint);
1203       }
1204
1205       if (e.getField().getType().isPrimitive()) {
1206         if (conflict) {
1207           effectsForGivenTaint.addPrimative(e);
1208         }
1209       } else {
1210         effectsForGivenTaint.addObjEffect(e, conflict);
1211       }
1212
1213       if(conflict) {
1214         if(potentiallyConflictingRoots == null) {
1215           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1216         }
1217
1218         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1219         if(taintsForField == null) {
1220           taintsForField = new ArrayList<Taint>();
1221           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1222         }
1223
1224         if(!taintsForField.contains(t)) {
1225           taintsForField.add(t);
1226         }
1227       }
1228     }
1229   }
1230
1231   private class TaintAndInternalHeapStructure {
1232     public Taint t;
1233     public Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap;
1234
1235     public TaintAndInternalHeapStructure(Taint taint, Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap) {
1236       t = taint;
1237       this.nodesInHeap = nodesInHeap;
1238     }
1239   }
1240
1241   private class TraversalInfo {
1242     public FlatNode f;
1243     public ReachGraph rg;
1244     public TempDescriptor invar;
1245
1246     public TraversalInfo(FlatNode fn, ReachGraph g) {
1247       f = fn;
1248       rg =g;
1249       invar = null;
1250     }
1251
1252     public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {
1253       f = fn;
1254       rg =rg2;
1255       invar = tempDesc;
1256     }
1257   }
1258 }