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