Robust/src/IR/Flat/RuntimeConflictResolver.java

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