Robust/src/Analysis/SSJava/LocationInference.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedReader;
   4 import java.io.BufferedWriter;
   5 import java.io.FileReader;
   6 import java.io.FileWriter;
   7 import java.io.IOException;
   8 import java.util.ArrayList;
   9 import java.util.Collections;
  10 import java.util.Comparator;
  11 import java.util.HashMap;
  12 import java.util.HashSet;
  13 import java.util.Iterator;
  14 import java.util.LinkedList;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.Set;
  18 import java.util.Stack;
  19 import java.util.Vector;
  20
  21 import IR.ClassDescriptor;
  22 import IR.Descriptor;
  23 import IR.FieldDescriptor;
  24 import IR.MethodDescriptor;
  25 import IR.NameDescriptor;
  26 import IR.Operation;
  27 import IR.State;
  28 import IR.SymbolTable;
  29 import IR.TypeDescriptor;
  30 import IR.VarDescriptor;
  31 import IR.Tree.ArrayAccessNode;
  32 import IR.Tree.AssignmentNode;
  33 import IR.Tree.BlockExpressionNode;
  34 import IR.Tree.BlockNode;
  35 import IR.Tree.BlockStatementNode;
  36 import IR.Tree.CastNode;
  37 import IR.Tree.CreateObjectNode;
  38 import IR.Tree.DeclarationNode;
  39 import IR.Tree.ExpressionNode;
  40 import IR.Tree.FieldAccessNode;
  41 import IR.Tree.IfStatementNode;
  42 import IR.Tree.Kind;
  43 import IR.Tree.LiteralNode;
  44 import IR.Tree.LoopNode;
  45 import IR.Tree.MethodInvokeNode;
  46 import IR.Tree.NameNode;
  47 import IR.Tree.OpNode;
  48 import IR.Tree.ReturnNode;
  49 import IR.Tree.SubBlockNode;
  50 import IR.Tree.SwitchBlockNode;
  51 import IR.Tree.SwitchStatementNode;
  52 import IR.Tree.TertiaryNode;
  53 import IR.Tree.TreeNode;
  54 import Util.Pair;
  55
  56 public class LocationInference {
  57
  58   State state;
  59   SSJavaAnalysis ssjava;
  60
  61   List<ClassDescriptor> temp_toanalyzeList;
  62   List<MethodDescriptor> temp_toanalyzeMethodList;
  63   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  64
  65   LinkedList<MethodDescriptor> toanalyze_methodDescList;
  66
  67   // map a method descriptor to its set of parameter descriptors
  68   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  69
  70   // keep current descriptors to visit in fixed-point interprocedural analysis,
  71   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  72
  73   // map a class descriptor to a field lattice
  74   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  75
  76   // map a method descriptor to a method lattice
  77   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  78
  79   // map a method/class descriptor to a hierarchy graph
  80   private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
  81
  82   // map a method/class descriptor to a skeleton hierarchy graph
  83   private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
  84
  85   private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
  86
  87   // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
  88   private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
  89
  90   // map a descriptor to a simple lattice
  91   private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
  92
  93   // map a method descriptor to the set of method invocation nodes which are
  94   // invoked by the method descriptor
  95   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
  96
  97   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
  98
  99   private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
 100
 101   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
 102
 103   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
 104
 105   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
 106
 107   private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
 108
 109   private Map<String, Vector<String>> mapFileNameToLineVector;
 110
 111   private Map<Descriptor, Integer> mapDescToDefinitionLine;
 112
 113   private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
 114
 115   // maps a method descriptor to a sub global flow graph that captures all value flows caused by the
 116   // set of callees reachable from the method
 117   private Map<MethodDescriptor, GlobalFlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
 118
 119   private Map<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>> mapMethodInvokeNodeToMapCallerArgToCalleeArg;
 120
 121   public static final String GLOBALLOC = "GLOBALLOC";
 122
 123   public static final String INTERLOC = "INTERLOC";
 124
 125   public static final String PCLOC = "_PCLOC_";
 126
 127   public static final String RLOC = "_RLOC_";
 128
 129   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
 130
 131   public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP);
 132
 133   public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM);
 134
 135   public static final Descriptor RETURNLOC = new NameDescriptor(RLOC);
 136
 137   public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL");
 138
 139   public static final HNode TOPHNODE = new HNode(TOPDESC);
 140
 141   public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC);
 142
 143   public static String newline = System.getProperty("line.separator");
 144
 145   LocationInfo curMethodInfo;
 146
 147   boolean debug = true;
 148
 149   public static int locSeed = 0;
 150
 151   public LocationInference(SSJavaAnalysis ssjava, State state) {
 152     this.ssjava = ssjava;
 153     this.state = state;
 154     this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
 155     this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 156     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
 157     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
 158     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
 159     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 160     this.mapMethodDescriptorToMethodInvokeNodeSet =
 161         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 162     this.mapMethodInvokeNodeToArgIdxMap =
 163         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
 164     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
 165     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 166     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 167
 168     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
 169     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
 170     this.mapMethodDescToParamNodeFlowsToReturnValue =
 171         new HashMap<MethodDescriptor, Set<FlowNode>>();
 172
 173     this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 174     this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
 175
 176     this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 177     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 178     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 179
 180     this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
 181
 182     this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
 183
 184     this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
 185
 186     this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
 187         new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
 188
 189   }
 190
 191   public void setupToAnalyze() {
 192     SymbolTable classtable = state.getClassSymbolTable();
 193     temp_toanalyzeList.clear();
 194     temp_toanalyzeList.addAll(classtable.getValueSet());
 195     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 196     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 197     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 198     // }
 199     // });
 200   }
 201
 202   public void setupToAnalazeMethod(ClassDescriptor cd) {
 203
 204     SymbolTable methodtable = cd.getMethodTable();
 205     temp_toanalyzeMethodList.clear();
 206     temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
 207     Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 208       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 209         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 210       }
 211     });
 212   }
 213
 214   public boolean toAnalyzeMethodIsEmpty() {
 215     return temp_toanalyzeMethodList.isEmpty();
 216   }
 217
 218   public boolean toAnalyzeIsEmpty() {
 219     return temp_toanalyzeList.isEmpty();
 220   }
 221
 222   public ClassDescriptor toAnalyzeNext() {
 223     return temp_toanalyzeList.remove(0);
 224   }
 225
 226   public MethodDescriptor toAnalyzeMethodNext() {
 227     return temp_toanalyzeMethodList.remove(0);
 228   }
 229
 230   public void inference() {
 231
 232     ssjava.init();
 233
 234     // construct value flow graph
 235     constructFlowGraph();
 236
 237     assignCompositeLocation();
 238
 239     updateFlowGraph();
 240
 241     // calculate RETURNLOC,PCLOC
 242     calculateExtraLocations();
 243
 244     _debug_writeFlowGraph();
 245
 246     // System.exit(0);
 247
 248     constructHierarchyGraph();
 249
 250     debug_writeHierarchyDotFiles();
 251
 252     simplifyHierarchyGraph();
 253
 254     debug_writeSimpleHierarchyDotFiles();
 255
 256     constructSkeletonHierarchyGraph();
 257
 258     debug_writeSkeletonHierarchyDotFiles();
 259
 260     insertCombinationNodes();
 261
 262     debug_writeSkeletonCombinationHierarchyDotFiles();
 263
 264     buildLattice();
 265
 266     debug_writeLattices();
 267
 268     updateCompositeLocationAssignments();
 269
 270     generateMethodSummary();
 271
 272     generateAnnoatedCode();
 273
 274     System.exit(0);
 275
 276   }
 277
 278   private void updateFlowGraph() {
 279
 280     LinkedList<MethodDescriptor> methodDescList =
 281         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 282
 283     while (!methodDescList.isEmpty()) {
 284       MethodDescriptor md = methodDescList.removeLast();
 285       if (state.SSJAVADEBUG) {
 286         System.out.println();
 287         System.out.println("SSJAVA: Updating a flow graph: " + md);
 288         propagateFlowsFromCalleesWithNoCompositeLocation(md);
 289       }
 290     }
 291   }
 292
 293   public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
 294       MethodInvokeNode min) {
 295
 296     if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
 297       mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
 298           new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
 299     }
 300
 301     return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
 302   }
 303
 304   public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
 305       NTuple<Descriptor> calleeParam) {
 306     getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
 307   }
 308
 309   private void assignCompositeLocation() {
 310     calculateGlobalValueFlowCompositeLocation();
 311     translateCompositeLocationAssignmentToFlowGraph();
 312   }
 313
 314   private void translateCompositeLocationAssignmentToFlowGraph() {
 315     System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
 316     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
 317     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
 318   }
 319
 320   private void updateCompositeLocationAssignments() {
 321
 322     LinkedList<MethodDescriptor> methodDescList =
 323         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 324
 325     while (!methodDescList.isEmpty()) {
 326       MethodDescriptor md = methodDescList.removeLast();
 327
 328       System.out.println("\n#updateCompositeLocationAssignments=" + md);
 329
 330       FlowGraph flowGraph = getFlowGraph(md);
 331
 332       MethodSummary methodSummary = getMethodSummary(md);
 333
 334       Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 335       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 336         FlowNode node = (FlowNode) iterator.next();
 337         System.out.println("-node=" + node + "   node.getDescTuple=" + node.getDescTuple());
 338         if (node.getCompositeLocation() != null) {
 339           CompositeLocation compLoc = node.getCompositeLocation();
 340           CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc);
 341           node.setCompositeLocation(updatedCompLoc);
 342           System.out.println("---updatedCompLoc1=" + updatedCompLoc);
 343         } else {
 344           NTuple<Descriptor> descTuple = node.getDescTuple();
 345           System.out.println("update desc=" + descTuple);
 346           CompositeLocation compLoc = convertToCompositeLocation(md, descTuple);
 347           compLoc = updateCompositeLocation(compLoc);
 348           node.setCompositeLocation(compLoc);
 349           System.out.println("---updatedCompLoc2=" + compLoc);
 350         }
 351
 352         if (node.isDeclaratonNode()) {
 353           Descriptor localVarDesc = node.getDescTuple().get(0);
 354           CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation());
 355           methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc);
 356         }
 357       }
 358
 359       // update PCLOC and RETURNLOC if they have a composite location assignment
 360       if (methodSummary.getRETURNLoc() != null) {
 361         methodSummary.setRETURNLoc(updateCompositeLocation(methodSummary.getRETURNLoc()));
 362       }
 363       if (methodSummary.getPCLoc() != null) {
 364         methodSummary.setPCLoc(updateCompositeLocation(methodSummary.getPCLoc()));
 365       }
 366
 367     }
 368
 369   }
 370
 371   private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) {
 372     CompositeLocation updatedCompLoc = new CompositeLocation();
 373     for (int i = 0; i < compLoc.getSize(); i++) {
 374       Location loc = compLoc.get(i);
 375       String nodeIdentifier = loc.getLocIdentifier();
 376       Descriptor enclosingDesc = loc.getDescriptor();
 377       String locName;
 378       if (!enclosingDesc.equals(GLOBALDESC)) {
 379         LocationSummary locSummary = getLocationSummary(enclosingDesc);
 380         HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
 381         if (scGraph != null) {
 382           HNode curNode = scGraph.getCurrentHNode(nodeIdentifier);
 383           if (curNode != null) {
 384             nodeIdentifier = curNode.getName();
 385           }
 386         }
 387         locName = locSummary.getLocationName(nodeIdentifier);
 388       } else {
 389         locName = nodeIdentifier;
 390       }
 391       Location updatedLoc = new Location(enclosingDesc, locName);
 392       updatedCompLoc.addLocation(updatedLoc);
 393     }
 394
 395     return updatedCompLoc;
 396   }
 397
 398   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
 399
 400     // First, assign a composite location to a node in the flow graph
 401     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
 402
 403     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
 404     Map<Location, CompositeLocation> callerMapLocToCompLoc =
 405         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
 406     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
 407     for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
 408       Location methodLoc = (Location) iterator.next();
 409       if (methodLoc.getDescriptor().equals(mdCaller)) {
 410         CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
 411         assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
 412       }
 413     }
 414
 415     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
 416
 417     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
 418     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
 419       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 420       // need to translate a composite location that is started with the base
 421       // tuple of 'min'.
 422       translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
 423       calleeSet.add(min.getMethod());
 424     }
 425
 426     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
 427       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 428       translateCompositeLocationAssignmentToFlowGraph(callee);
 429     }
 430
 431   }
 432
 433   public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
 434       CompositeLocation inferCompLoc) {
 435     Descriptor localDesc = loc.getLocDescriptor();
 436
 437     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 438     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 439       FlowNode node = (FlowNode) iterator.next();
 440       if (node.getDescTuple().startsWith(localDesc)
 441           && !node.getDescTuple().get(0).equals(LITERALDESC)) {
 442         // need to assign the inferred composite location to this node
 443         CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
 444         node.setCompositeLocation(newCompLoc);
 445         System.out.println("SET Node=" + node + "  inferCompLoc=" + newCompLoc);
 446       }
 447     }
 448   }
 449
 450   private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
 451       CompositeLocation inferCompLoc) {
 452
 453     System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
 454         + inferCompLoc);
 455
 456     CompositeLocation newCompLoc = new CompositeLocation();
 457     for (int i = 0; i < inferCompLoc.getSize(); i++) {
 458       newCompLoc.addLocation(inferCompLoc.get(i));
 459     }
 460
 461     Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
 462     Descriptor enclosingDescriptor;
 463     if (lastDescOfPrefix instanceof InterDescriptor) {
 464       enclosingDescriptor = null;
 465     } else {
 466       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
 467     }
 468
 469     for (int i = 1; i < nodeDescTuple.size(); i++) {
 470       Descriptor desc = nodeDescTuple.get(i);
 471       Location locElement = new Location(enclosingDescriptor, desc);
 472       newCompLoc.addLocation(locElement);
 473
 474       enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
 475     }
 476
 477     return newCompLoc;
 478   }
 479
 480   private void translateMapLocationToInferCompositeLocationToCalleeGraph(
 481       GlobalFlowGraph callerGraph, MethodInvokeNode min) {
 482
 483     MethodDescriptor mdCallee = min.getMethod();
 484     MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
 485     Map<Location, CompositeLocation> callerMapLocToCompLoc =
 486         callerGraph.getMapLocationToInferCompositeLocation();
 487
 488     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
 489
 490     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
 491     GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
 492
 493     NTuple<Location> baseLocTuple = null;
 494     if (mapMethodInvokeNodeToBaseTuple.containsKey(min)) {
 495       baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
 496     }
 497
 498     System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee="
 499         + mdCallee + " baseLocTuple=" + baseLocTuple);
 500     // System.out.println("-mapIdxToArgTuple=" + mapIdxToArgTuple);
 501     // System.out.println("-callerMapLocToCompLoc=" + callerMapLocToCompLoc);
 502
 503     Set<Location> keySet = callerMapLocToCompLoc.keySet();
 504     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 505       Location key = (Location) iterator.next();
 506       CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
 507
 508       if (!key.getDescriptor().equals(mdCaller)) {
 509
 510         CompositeLocation newCalleeCompLoc;
 511         if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
 512           // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc
 513           // + " with baseTuple=" + baseLocTuple);
 514           newCalleeCompLoc =
 515               translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
 516
 517           calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
 518           System.out.println("---key=" + key + "  callerCompLoc=" + callerCompLoc
 519               + "  newCalleeCompLoc=" + newCalleeCompLoc);
 520           System.out.println("-----baseLoctuple=" + baseLocTuple);
 521           System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
 522         } else {
 523           System.out.println("2");
 524           // check if it is the global access
 525           Location compLocFirstElement = callerCompLoc.getTuple().get(0);
 526           if (compLocFirstElement.getDescriptor().equals(mdCallee)
 527               && compLocFirstElement.getLocDescriptor().equals(GLOBALDESC)) {
 528
 529             newCalleeCompLoc = new CompositeLocation();
 530             Location newMethodLoc = new Location(mdCallee, GLOBALDESC);
 531
 532             newCalleeCompLoc.addLocation(newMethodLoc);
 533             for (int i = 1; i < callerCompLoc.getSize(); i++) {
 534               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
 535             }
 536             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
 537             System.out.println("---key=" + key + "  callerCompLoc=" + callerCompLoc
 538                 + "  newCalleeCompLoc=" + newCalleeCompLoc);
 539             System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
 540
 541           } else {
 542             int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
 543             if (paramIdx == -1) {
 544               continue;
 545             }
 546             NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(paramIdx);
 547
 548             FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx);
 549             System.out.println("-----paramIdx=" + paramIdx + "  paramFlowNode=" + paramFlowNode);
 550             NTuple<Location> paramLocTuple =
 551                 translateToLocTuple(mdCallee, paramFlowNode.getDescTuple());
 552             newCalleeCompLoc = new CompositeLocation();
 553             for (int i = 0; i < paramLocTuple.size(); i++) {
 554               newCalleeCompLoc.addLocation(paramLocTuple.get(i));
 555             }
 556             for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) {
 557               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
 558             }
 559             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
 560             System.out.println("---key=" + key + "  callerCompLoc=" + callerCompLoc
 561                 + "  newCalleeCompLoc=" + newCalleeCompLoc);
 562             System.out.println("------argTuple=" + argTuple);
 563             System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
 564
 565           }
 566
 567         }
 568
 569       }
 570     }
 571
 572     // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING="
 573     // + calleeGlobalGraph.getMapLocationToInferCompositeLocation());
 574
 575     // If the location of an argument has a composite location
 576     // need to assign a proper composite location to the corresponding callee parameter
 577     // System.out.println("---translate arg composite location to callee param. min="
 578     // + min.printNode(0));
 579     Set<Integer> idxSet = mapIdxToArgTuple.keySet();
 580     for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
 581       Integer idx = (Integer) iterator.next();
 582
 583       if (idx == 0 && !min.getMethod().isStatic()) {
 584         continue;
 585       }
 586
 587       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
 588       if (argTuple.size() > 0) {
 589         // check if an arg tuple has been already assigned to a composite location
 590         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
 591         Location argLocalLoc = argLocTuple.get(0);
 592
 593         // if (!isPrimitiveType(argTuple)) {
 594         if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
 595
 596           CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
 597           for (int i = 1; i < argLocTuple.size(); i++) {
 598             callerCompLoc.addLocation(argLocTuple.get(i));
 599           }
 600
 601           if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
 602
 603             FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
 604             NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
 605             NTuple<Location> calleeParamLocTuple =
 606                 translateToLocTuple(mdCallee, calleeParamDescTuple);
 607
 608             System.out.println("---need to translate callerCompLoc=" + callerCompLoc
 609                 + " with baseTuple=" + baseLocTuple + "   calleeParamLocTuple="
 610                 + calleeParamLocTuple);
 611
 612             CompositeLocation newCalleeCompLoc =
 613                 translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
 614
 615             calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
 616                 newCalleeCompLoc);
 617
 618             System.out.println("---callee loc=" + calleeParamLocTuple.get(0)
 619                 + "  newCalleeCompLoc=" + newCalleeCompLoc);
 620
 621             // System.out.println("###need to assign composite location to=" + calleeParamDescTuple
 622             // + " with baseTuple=" + baseLocTuple);
 623           }
 624
 625         }
 626       }
 627
 628     }
 629
 630   }
 631
 632   private int getParamIdx(CompositeLocation compLoc,
 633       Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple) {
 634
 635     // if the composite location is started with the argument descriptor
 636     // return the argument's index. o.t. return -1
 637
 638     Set<Integer> keySet = mapIdxToArgTuple.keySet();
 639     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 640       Integer key = (Integer) iterator.next();
 641       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(key);
 642       if (translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) {
 643         return key.intValue();
 644       }
 645     }
 646
 647     return -1;
 648   }
 649
 650   private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
 651
 652     Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
 653
 654     if (lastDesc instanceof FieldDescriptor) {
 655       return ((FieldDescriptor) lastDesc).getType().isPrimitive();
 656     } else if (lastDesc instanceof VarDescriptor) {
 657       return ((VarDescriptor) lastDesc).getType().isPrimitive();
 658     } else if (lastDesc instanceof InterDescriptor) {
 659       return true;
 660     }
 661
 662     return false;
 663   }
 664
 665   private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
 666       NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
 667
 668     CompositeLocation newCalleeCompLoc = new CompositeLocation();
 669
 670     Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
 671     newCalleeCompLoc.addLocation(calleeThisLoc);
 672
 673     // remove the base tuple from the caller
 674     // ex; In the method invoation foo.bar.methodA(), the callee will have the composite location
 675     // ,which is relative to the 'this' variable, <THIS,...>
 676     for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
 677       newCalleeCompLoc.addLocation(callerCompLoc.get(i));
 678     }
 679
 680     return newCalleeCompLoc;
 681
 682   }
 683
 684   private void calculateGlobalValueFlowCompositeLocation() {
 685
 686     System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
 687     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
 688     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
 689
 690     Set<Location> calculatedPrefixSet = new HashSet<Location>();
 691
 692     Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
 693
 694     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 695       GlobalFlowNode node = (GlobalFlowNode) iterator.next();
 696
 697       Location prefixLoc = node.getLocTuple().get(0);
 698
 699       if (calculatedPrefixSet.contains(prefixLoc)) {
 700         // the prefix loc has been already assigned to a composite location
 701         continue;
 702       }
 703
 704       calculatedPrefixSet.add(prefixLoc);
 705
 706       // Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
 707       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
 708
 709       Set<GlobalFlowNode> reachableNodeSet =
 710           globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
 711       // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
 712
 713       // System.out.println("node=" + node + "    prefixList=" + prefixList + "   reachableNodeSet="
 714       // + reachableNodeSet);
 715
 716       for (int i = 0; i < prefixList.size(); i++) {
 717         NTuple<Location> curPrefix = prefixList.get(i);
 718         Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
 719
 720         for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
 721           GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
 722           if (reachNode.getLocTuple().startsWith(curPrefix)) {
 723             reachableCommonPrefixSet.add(reachNode.getLocTuple());
 724           }
 725         }
 726
 727         if (!reachableCommonPrefixSet.isEmpty()) {
 728
 729           MethodDescriptor curPrefixFirstElementMethodDesc =
 730               (MethodDescriptor) curPrefix.get(0).getDescriptor();
 731
 732           MethodDescriptor nodePrefixLocFirstElementMethodDesc =
 733               (MethodDescriptor) prefixLoc.getDescriptor();
 734
 735           if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
 736               || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
 737                   curPrefixFirstElementMethodDesc)) {
 738
 739             // TODO
 740             // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
 741
 742             Location curPrefixLocalLoc = curPrefix.get(0);
 743             if (globalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
 744               // in this case, the local variable of the current prefix has already got a composite
 745               // location
 746               // so we just ignore the current composite location.
 747
 748               // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
 749               // + " DUE TO " + curPrefix);
 750
 751               continue next;
 752             }
 753
 754             Location targetLocalLoc = node.getLocTuple().get(0);
 755             // CompositeLocation curCompLoc = globalFlowGraph.getCompositeLocation(targetLocalLoc);
 756             // if ((curPrefix.size() + 1) > curCompLoc.getSize()) {
 757
 758             CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
 759             System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
 760             System.out.println("- newCompLoc=" + newCompLoc);
 761             globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
 762             // }
 763
 764             continue next;
 765             // }
 766
 767           }
 768
 769         }
 770
 771       }
 772
 773     }
 774     // Set<GlobalFlowNode> inNodeSet =
 775     // graph.getIncomingNodeSetWithPrefix(prefix);
 776     // System.out.println("inNodeSet=" + inNodeSet + "  from=" + node);
 777   }
 778
 779   private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
 780     CompositeLocation newCompLoc = compLocPrefix.clone();
 781     NTuple<Location> locTuple = node.getLocTuple();
 782     for (int i = 1; i < locTuple.size(); i++) {
 783       newCompLoc.addLocation(locTuple.get(i));
 784     }
 785     node.setInferCompositeLocation(newCompLoc);
 786   }
 787
 788   private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
 789
 790     System.out.println("\n##### calculatePrefixList node=" + node);
 791
 792     Set<GlobalFlowNode> incomingNodeSetPrefix =
 793         graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0));
 794     // System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix);
 795     //
 796     // Set<GlobalFlowNode> reachableNodeSetPrefix =
 797     // graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
 798     // System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix);
 799
 800     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
 801
 802     for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
 803       GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
 804       NTuple<Location> inNodeTuple = inNode.getLocTuple();
 805
 806       for (int i = 1; i < inNodeTuple.size(); i++) {
 807         NTuple<Location> prefix = inNodeTuple.subList(0, i);
 808         if (!prefixList.contains(prefix)) {
 809           prefixList.add(prefix);
 810         }
 811       }
 812     }
 813
 814     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
 815       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
 816         int s0 = arg0.size();
 817         int s1 = arg1.size();
 818         if (s0 > s1) {
 819           return -1;
 820         } else if (s0 == s1) {
 821           return 0;
 822         } else {
 823           return 1;
 824         }
 825       }
 826     });
 827
 828     // remove a prefix which is not suitable for generating composite location
 829     Location localVarLoc = node.getLocTuple().get(0);
 830     MethodDescriptor md = (MethodDescriptor) localVarLoc.getDescriptor();
 831     ClassDescriptor cd = md.getClassDesc();
 832
 833     int idx = 0;
 834
 835     Set<NTuple<Location>> toberemoved = new HashSet<NTuple<Location>>();
 836     for (int i = 0; i < prefixList.size(); i++) {
 837       NTuple<Location> prefixLocTuple = prefixList.get(i);
 838       if (!containsClassDesc(cd, prefixLocTuple)) {
 839         toberemoved.add(prefixLocTuple);
 840       }
 841     }
 842
 843     prefixList.removeAll(toberemoved);
 844
 845     return prefixList;
 846
 847     // List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
 848     //
 849     // for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 850     // GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
 851     // NTuple<Location> inNodeTuple = inNode.getLocTuple();
 852     //
 853     // for (int i = 1; i < inNodeTuple.size(); i++) {
 854     // NTuple<Location> prefix = inNodeTuple.subList(0, i);
 855     // if (!prefixList.contains(prefix)) {
 856     // prefixList.add(prefix);
 857     // }
 858     // }
 859     // }
 860     //
 861     // Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
 862     // public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
 863     // int s0 = arg0.size();
 864     // int s1 = arg1.size();
 865     // if (s0 > s1) {
 866     // return -1;
 867     // } else if (s0 == s1) {
 868     // return 0;
 869     // } else {
 870     // return 1;
 871     // }
 872     // }
 873     // });
 874     // return prefixList;
 875   }
 876
 877   private boolean containsClassDesc(ClassDescriptor cd, NTuple<Location> prefixLocTuple) {
 878     for (int i = 0; i < prefixLocTuple.size(); i++) {
 879       Location loc = prefixLocTuple.get(i);
 880       Descriptor locDesc = loc.getLocDescriptor();
 881       if (locDesc != null) {
 882         ClassDescriptor type = getClassTypeDescriptor(locDesc);
 883         if (type != null && type.equals(cd)) {
 884           return true;
 885         }
 886       }
 887     }
 888     return false;
 889   }
 890
 891   private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
 892
 893     MethodDescriptor md = flowGraph.getMethodDescriptor();
 894
 895     GlobalFlowGraph globalGraph = new GlobalFlowGraph(md);
 896
 897     // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 898     Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
 899
 900     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 901
 902       FlowEdge edge = (FlowEdge) iterator.next();
 903       NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
 904       NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
 905
 906       // here only keep the first element(method location) of the descriptor
 907       // tuple
 908       NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
 909       // Location srcMethodLoc = srcLocTuple.get(0);
 910       // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor();
 911       // // if (flowGraph.isParamDesc(srcVarDesc) &&
 912       // (!srcVarDesc.equals(md.getThis()))) {
 913       // if (!srcVarDesc.equals(md.getThis())) {
 914       // srcLocTuple = new NTuple<Location>();
 915       // Location loc = new Location(md, srcVarDesc);
 916       // srcLocTuple.add(loc);
 917       // }
 918       //
 919       NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
 920       // Location dstMethodLoc = dstLocTuple.get(0);
 921       // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor();
 922       // if (!dstVarDesc.equals(md.getThis())) {
 923       // dstLocTuple = new NTuple<Location>();
 924       // Location loc = new Location(md, dstVarDesc);
 925       // dstLocTuple.add(loc);
 926       // }
 927
 928       globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
 929
 930     }
 931
 932     return globalGraph;
 933   }
 934
 935   private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
 936
 937     NTuple<Location> locTuple = new NTuple<Location>();
 938
 939     Descriptor enclosingDesc = md;
 940     // System.out.println("md=" + md + "  descTuple=" + descTuple);
 941     for (int i = 0; i < descTuple.size(); i++) {
 942       Descriptor desc = descTuple.get(i);
 943
 944       Location loc = new Location(enclosingDesc, desc);
 945       locTuple.add(loc);
 946
 947       if (desc instanceof VarDescriptor) {
 948         enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
 949       } else if (desc instanceof FieldDescriptor) {
 950         enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
 951       } else {
 952         // TODO: inter descriptor case
 953         enclosingDesc = desc;
 954       }
 955
 956     }
 957
 958     return locTuple;
 959
 960   }
 961
 962   private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller,
 963       GlobalFlowGraph subGlobalFlowGraph) {
 964
 965     // the transformation for a call site propagates flows through parameters
 966     // if the method is virtual, it also grab all relations from any possible
 967     // callees
 968
 969     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
 970
 971     for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
 972       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 973       MethodDescriptor mdCallee = min.getMethod();
 974       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 975       if (mdCallee.isStatic()) {
 976         setPossibleCallees.add(mdCallee);
 977       } else {
 978         Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
 979         // removes method descriptors that are not invoked by the caller
 980         calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
 981         setPossibleCallees.addAll(calleeSet);
 982       }
 983
 984       for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
 985         MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
 986         propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
 987       }
 988
 989     }
 990
 991   }
 992
 993   private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
 994       MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
 995
 996     System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller);
 997     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 998     Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
 999
1000     System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)="
1001         + mapMethodInvokeNodeToArgIdxMap.get(min));
1002     Set<Integer> keySet = mapIdxToArg.keySet();
1003     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1004       Integer idx = (Integer) iterator.next();
1005       NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
1006       if (argDescTuple.size() > 0) {
1007         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
1008         NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
1009         NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
1010         addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
1011       }
1012     }
1013
1014     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1015     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
1016     Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
1017     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
1018       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
1019       addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
1020     }
1021
1022     // int numParam = calleeFlowGraph.getNumParameters();
1023     // for (int idx = 0; idx < numParam; idx++) {
1024     //
1025     // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
1026     //
1027     // NTuple<Location> paramLocTuple =
1028     // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple());
1029     //
1030     // GlobalFlowNode globalParamNode =
1031     // calleeSubGlobalGraph.getFlowNode(paramLocTuple);
1032     //
1033     // NTuple<Descriptor> argTuple =
1034     // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
1035     //
1036     // NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
1037     //
1038     // System.out.println("argTupleSet=" + argLocTuple + "   param=" +
1039     // paramLocTuple);
1040     // // here, it adds all value flows reachable from the paramNode in the
1041     // callee's flow graph
1042     //
1043     // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple,
1044     // possibleMdCallee,
1045     // globalParamNode);
1046     // }
1047     //
1048     // // TODO
1049     // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
1050     // // FlowGraph calleeSubGlobalGraph =
1051     // getSubGlobalFlowGraph(possibleMdCallee);
1052     // //
1053     // // int numParam = calleeSubGlobalGraph.getNumParameters();
1054     // // for (int idx = 0; idx < numParam; idx++) {
1055     // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx);
1056     // // NTuple<Descriptor> argTuple =
1057     // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
1058     // // System.out.println("argTupleSet=" + argTuple + "   param=" +
1059     // paramNode);
1060     // // // here, it adds all value flows reachable from the paramNode in the
1061     // callee's flow graph
1062     // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode,
1063     // callerSubGlobalGraph,
1064     // // argTuple, baseTuple);
1065     // // }
1066
1067   }
1068
1069   private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
1070       MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
1071
1072     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1073     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
1074
1075     NTuple<Location> callerSrcNodeLocTuple =
1076         translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
1077
1078     if (callerSrcNodeLocTuple != null) {
1079       Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
1080
1081       for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
1082         GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
1083         NTuple<Location> callerDstNodeLocTuple =
1084             translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
1085         if (callerDstNodeLocTuple != null) {
1086           callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
1087         }
1088       }
1089     }
1090
1091   }
1092
1093   private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
1094       MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
1095     // this method will return the same nodeLocTuple if the corresponding argument is literal
1096     // value.
1097
1098     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1099
1100     NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
1101     if (calleeFlowGraph.isParameter(nodeDescTuple)) {
1102       int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
1103       NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
1104
1105       if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) {
1106         // the type of argument is primitive.
1107         return nodeLocTuple.clone();
1108       }
1109       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
1110
1111       NTuple<Location> callerLocTuple = new NTuple<Location>();
1112
1113       callerLocTuple.addAll(argLocTuple);
1114       for (int i = 1; i < nodeLocTuple.size(); i++) {
1115         callerLocTuple.add(nodeLocTuple.get(i));
1116       }
1117       return callerLocTuple;
1118     } else {
1119       return nodeLocTuple.clone();
1120     }
1121
1122   }
1123
1124   public static boolean isPrimitive(Descriptor desc) {
1125
1126     if (desc instanceof FieldDescriptor) {
1127       return ((FieldDescriptor) desc).getType().isPrimitive();
1128     } else if (desc instanceof VarDescriptor) {
1129       return ((VarDescriptor) desc).getType().isPrimitive();
1130     } else if (desc instanceof InterDescriptor) {
1131       return true;
1132     }
1133
1134     return false;
1135   }
1136
1137   private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
1138
1139     NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
1140     for (int i = 0; i < locTuple.size(); i++) {
1141       descTuple.add(locTuple.get(i).getLocDescriptor());
1142     }
1143     return descTuple;
1144
1145   }
1146
1147   private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
1148       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
1149       GlobalFlowNode globalParamNode) {
1150
1151     Set<GlobalFlowNode> visited = new HashSet<GlobalFlowNode>();
1152     visited.add(globalParamNode);
1153     recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee,
1154         globalParamNode);
1155
1156   }
1157
1158   private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
1159       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
1160       GlobalFlowNode calleeCurNode) {
1161
1162     // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1163     // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1164     //
1165     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
1166     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
1167     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
1168     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
1169     // }
1170     //
1171     // Set<GlobalFlowNode> outNodeSet =
1172     // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode);
1173     // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
1174     // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
1175     //
1176     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
1177     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
1178     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
1179     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
1180     // }
1181     //
1182     // outNode.getDescTuple();
1183     //
1184     // if (calleeFlowGraph.is)
1185     //
1186     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
1187     // // destination node is started with 'parameter'
1188     // // need to translate it in terms of the caller's a node
1189     // srcDescTuple =
1190     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple),
1191     // srcDescTuple);
1192     // }
1193     //
1194     // }
1195     //
1196     // Set<FlowEdge> edgeSet =
1197     // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
1198     // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1199     // FlowEdge flowEdge = (FlowEdge) iterator.next();
1200     //
1201     // NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
1202     // NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
1203     //
1204     // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
1205     //
1206     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
1207     // // destination node is started with 'parameter'
1208     // // need to translate it in terms of the caller's a node
1209     // srcDescTuple =
1210     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple),
1211     // srcDescTuple);
1212     // }
1213     //
1214     // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
1215     // // destination node is started with 'parameter'
1216     // // need to translate it in terms of the caller's a node
1217     // dstDescTuple =
1218     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple),
1219     // dstDescTuple);
1220     // }
1221     //
1222     // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
1223     //
1224     // if (!visited.contains(dstNode)) {
1225     // visited.add(dstNode);
1226     // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode,
1227     // callerSubGlobalGraph,
1228     // dstDescTuple, visited, baseTuple);
1229     // }
1230     //
1231     // }
1232
1233   }
1234
1235   private NTuple<Location> translateToCaller(NTuple<Location> argLocTuple,
1236       NTuple<Location> curNodeLocTuple) {
1237
1238     NTuple<Location> callerLocTuple = new NTuple<Location>();
1239
1240     callerLocTuple.addAll(argLocTuple);
1241     for (int i = 1; i < curNodeLocTuple.size(); i++) {
1242       callerLocTuple.add(curNodeLocTuple.get(i));
1243     }
1244
1245     return callerLocTuple;
1246   }
1247
1248   private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min,
1249       FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph,
1250       NTuple<Descriptor> callerSrcTuple, Set<FlowNode> visited, NTuple<Descriptor> baseTuple) {
1251
1252     MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor();
1253
1254     // Set<FlowEdge> edgeSet =
1255     // calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode);
1256     Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
1257     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1258       FlowEdge flowEdge = (FlowEdge) iterator.next();
1259
1260       NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
1261       NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
1262
1263       FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
1264
1265       if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
1266         // destination node is started with 'parameter'
1267         // need to translate it in terms of the caller's a node
1268         srcDescTuple =
1269             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple);
1270       }
1271
1272       if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
1273         // destination node is started with 'parameter'
1274         // need to translate it in terms of the caller's a node
1275         dstDescTuple =
1276             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple);
1277       }
1278
1279       callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
1280
1281       if (!visited.contains(dstNode)) {
1282         visited.add(dstNode);
1283         recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph,
1284             dstDescTuple, visited, baseTuple);
1285       }
1286
1287     }
1288
1289   }
1290
1291   private NTuple<Descriptor> translateToCaller(MethodInvokeNode min, int paramIdx,
1292       NTuple<Descriptor> srcDescTuple) {
1293
1294     NTuple<Descriptor> callerTuple = new NTuple<Descriptor>();
1295
1296     NTuple<Descriptor> argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
1297
1298     for (int i = 0; i < argTuple.size(); i++) {
1299       callerTuple.add(argTuple.get(i));
1300     }
1301
1302     for (int i = 1; i < srcDescTuple.size(); i++) {
1303       callerTuple.add(srcDescTuple.get(i));
1304     }
1305
1306     return callerTuple;
1307   }
1308
1309   private NTuple<Descriptor> traslateToCalleeParamTupleToCallerArgTuple(
1310       NTuple<Descriptor> calleeInitTuple, NTuple<Descriptor> callerSrcTuple) {
1311
1312     NTuple<Descriptor> callerInitTuple = new NTuple<Descriptor>();
1313
1314     for (int i = 0; i < callerSrcTuple.size(); i++) {
1315       callerInitTuple.add(callerSrcTuple.get(i));
1316     }
1317
1318     for (int i = 1; i < calleeInitTuple.size(); i++) {
1319       callerInitTuple.add(calleeInitTuple.get(i));
1320     }
1321
1322     return callerInitTuple;
1323   }
1324
1325   public LocationSummary getLocationSummary(Descriptor d) {
1326     if (!mapDescToLocationSummary.containsKey(d)) {
1327       if (d instanceof MethodDescriptor) {
1328         mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
1329       } else if (d instanceof ClassDescriptor) {
1330         mapDescToLocationSummary.put(d, new FieldSummary());
1331       }
1332     }
1333     return mapDescToLocationSummary.get(d);
1334   }
1335
1336   private void generateMethodSummary() {
1337
1338     Set<MethodDescriptor> keySet = md2lattice.keySet();
1339     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1340       MethodDescriptor md = (MethodDescriptor) iterator.next();
1341
1342       System.out.println("\nSSJAVA: generate method summary: " + md);
1343
1344       FlowGraph flowGraph = getFlowGraph(md);
1345       MethodSummary methodSummary = getMethodSummary(md);
1346
1347       HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md);
1348
1349       // set the 'this' reference location
1350       if (!md.isStatic()) {
1351         System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName());
1352         methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName());
1353       }
1354
1355       // set the 'global' reference location if needed
1356       if (methodSummary.hasGlobalAccess()) {
1357         methodSummary.setGlobalLocName(scGraph.getHNode(GLOBALDESC).getName());
1358       }
1359
1360       // construct a parameter mapping that maps a parameter descriptor to an
1361       // inferred composite location
1362       for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
1363         FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
1364         CompositeLocation inferredCompLoc =
1365             updateCompositeLocation(flowNode.getCompositeLocation());
1366         // NTuple<Descriptor> descTuple = flowNode.getDescTuple();
1367         //
1368         // CompositeLocation assignedCompLoc = flowNode.getCompositeLocation();
1369         // CompositeLocation inferredCompLoc;
1370         // if (assignedCompLoc != null) {
1371         // inferredCompLoc = translateCompositeLocation(assignedCompLoc);
1372         // } else {
1373         // Descriptor locDesc = descTuple.get(0);
1374         // Location loc = new Location(md, locDesc.getSymbol());
1375         // loc.setLocDescriptor(locDesc);
1376         // inferredCompLoc = new CompositeLocation(loc);
1377         // }
1378         System.out.println("-paramIdx=" + paramIdx + "   infer=" + inferredCompLoc + " original="
1379             + flowNode.getCompositeLocation());
1380
1381         Descriptor localVarDesc = flowNode.getDescTuple().get(0);
1382         methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc);
1383         methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
1384       }
1385
1386     }
1387
1388   }
1389
1390   private boolean hasOrderingRelation(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
1391
1392     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
1393
1394     for (int idx = 0; idx < size; idx++) {
1395       Location loc1 = locTuple1.get(idx);
1396       Location loc2 = locTuple2.get(idx);
1397
1398       Descriptor desc1 = loc1.getDescriptor();
1399       Descriptor desc2 = loc2.getDescriptor();
1400
1401       if (!desc1.equals(desc2)) {
1402         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
1403       }
1404
1405       Descriptor locDesc1 = loc1.getLocDescriptor();
1406       Descriptor locDesc2 = loc2.getLocDescriptor();
1407
1408       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
1409
1410       HNode node1 = hierarchyGraph.getHNode(locDesc1);
1411       HNode node2 = hierarchyGraph.getHNode(locDesc2);
1412
1413       System.out.println("---node1=" + node1 + "  node2=" + node2);
1414       System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
1415           + hierarchyGraph.getIncomingNodeSet(node2));
1416
1417       if (locDesc1.equals(locDesc2)) {
1418         continue;
1419       } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1)
1420           && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) {
1421         return false;
1422       } else {
1423         return true;
1424       }
1425
1426     }
1427
1428     return false;
1429
1430   }
1431
1432   private boolean isHigherThan(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
1433
1434     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
1435
1436     for (int idx = 0; idx < size; idx++) {
1437       Location loc1 = locTuple1.get(idx);
1438       Location loc2 = locTuple2.get(idx);
1439
1440       Descriptor desc1 = loc1.getDescriptor();
1441       Descriptor desc2 = loc2.getDescriptor();
1442
1443       if (!desc1.equals(desc2)) {
1444         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
1445       }
1446
1447       Descriptor locDesc1 = loc1.getLocDescriptor();
1448       Descriptor locDesc2 = loc2.getLocDescriptor();
1449
1450       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
1451
1452       HNode node1 = hierarchyGraph.getHNode(locDesc1);
1453       HNode node2 = hierarchyGraph.getHNode(locDesc2);
1454
1455       System.out.println("---node1=" + node1 + "  node2=" + node2);
1456       System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
1457           + hierarchyGraph.getIncomingNodeSet(node2));
1458
1459       if (locDesc1.equals(locDesc2)) {
1460         continue;
1461       } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) {
1462         return true;
1463       } else {
1464         return false;
1465       }
1466
1467     }
1468
1469     return false;
1470   }
1471
1472   private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) {
1473     CompositeLocation newCompLoc = new CompositeLocation();
1474
1475     // System.out.println("compLoc=" + compLoc);
1476     for (int i = 0; i < compLoc.getSize(); i++) {
1477       Location loc = compLoc.get(i);
1478       Descriptor enclosingDescriptor = loc.getDescriptor();
1479       Descriptor locDescriptor = loc.getLocDescriptor();
1480
1481       HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor);
1482       // System.out.println("-hnode=" + hnode + "    from=" + locDescriptor +
1483       // " enclosingDescriptor="
1484       // + enclosingDescriptor);
1485       // System.out.println("-getLocationSummary(enclosingDescriptor)="
1486       // + getLocationSummary(enclosingDescriptor));
1487       String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName());
1488       // System.out.println("-locName=" + locName);
1489       Location newLoc = new Location(enclosingDescriptor, locName);
1490       newLoc.setLocDescriptor(locDescriptor);
1491       newCompLoc.addLocation(newLoc);
1492     }
1493
1494     return newCompLoc;
1495   }
1496
1497   private void debug_writeLattices() {
1498
1499     Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
1500     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1501       Descriptor key = (Descriptor) iterator.next();
1502       SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
1503       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
1504       HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
1505       if (key instanceof ClassDescriptor) {
1506         writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
1507             "_SIMPLE");
1508       } else if (key instanceof MethodDescriptor) {
1509         MethodDescriptor md = (MethodDescriptor) key;
1510         writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
1511             "_SIMPLE");
1512       }
1513
1514       LocationSummary ls = getLocationSummary(key);
1515       System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
1516     }
1517
1518     Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
1519     for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
1520       ClassDescriptor cd = (ClassDescriptor) iterator.next();
1521       writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
1522           cd2lattice.get(cd), "");
1523     }
1524
1525     Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
1526     for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
1527       MethodDescriptor md = (MethodDescriptor) iterator.next();
1528       writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
1529           md2lattice.get(md), "");
1530     }
1531
1532   }
1533
1534   private void buildLattice() {
1535
1536     BuildLattice buildLattice = new BuildLattice(this);
1537
1538     Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
1539     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1540       Descriptor desc = (Descriptor) iterator.next();
1541
1542       SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
1543
1544       addMapDescToSimpleLattice(desc, simpleLattice);
1545
1546       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1547       System.out.println("\n## insertIntermediateNodesToStraightLine:"
1548           + simpleHierarchyGraph.getName());
1549       SSJavaLattice<String> lattice =
1550           buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
1551       lattice.removeRedundantEdges();
1552
1553       if (desc instanceof ClassDescriptor) {
1554         // field lattice
1555         cd2lattice.put((ClassDescriptor) desc, lattice);
1556         // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
1557       } else if (desc instanceof MethodDescriptor) {
1558         // method lattice
1559         md2lattice.put((MethodDescriptor) desc, lattice);
1560         MethodDescriptor md = (MethodDescriptor) desc;
1561         ClassDescriptor cd = md.getClassDesc();
1562         // ssjava.writeLatticeDotFile(cd, md, lattice);
1563       }
1564
1565       // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1566       // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1567       // HierarchyGraph skeletonGraphWithCombinationNode =
1568       // skeletonGraph.clone();
1569       // skeletonGraphWithCombinationNode.setName(desc + "_SC");
1570       //
1571       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1572       // System.out.println("Identifying Combination Nodes:");
1573       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1574       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1575       // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc,
1576       // skeletonGraphWithCombinationNode);
1577     }
1578
1579   }
1580
1581   public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
1582     mapDescriptorToSimpleLattice.put(desc, lattice);
1583   }
1584
1585   public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
1586     return mapDescriptorToSimpleLattice.get(desc);
1587   }
1588
1589   private void simplifyHierarchyGraph() {
1590     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1591     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1592       Descriptor desc = (Descriptor) iterator.next();
1593       System.out.println("SSJAVA: remove redundant edges: " + desc);
1594       HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
1595       simpleHierarchyGraph.setName(desc + "_SIMPLE");
1596       simpleHierarchyGraph.removeRedundantEdges();
1597       mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
1598     }
1599   }
1600
1601   private void insertCombinationNodes() {
1602     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
1603     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1604       Descriptor desc = (Descriptor) iterator.next();
1605       System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1606       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1607       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
1608       skeletonGraphWithCombinationNode.setName(desc + "_SC");
1609
1610       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1611       System.out.println("Identifying Combination Nodes:");
1612       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1613       skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1614       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
1615     }
1616   }
1617
1618   private void constructSkeletonHierarchyGraph() {
1619     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1620     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1621       Descriptor desc = (Descriptor) iterator.next();
1622       System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc);
1623       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
1624       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
1625       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
1626       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
1627       skeletonGraph.simplifyHierarchyGraph();
1628       // skeletonGraph.combineRedundantNodes(false);
1629       // skeletonGraph.removeRedundantEdges();
1630       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
1631     }
1632   }
1633
1634   private void debug_writeHierarchyDotFiles() {
1635
1636     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1637     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1638       Descriptor desc = (Descriptor) iterator.next();
1639       getHierarchyGraph(desc).writeGraph();
1640     }
1641
1642   }
1643
1644   private void debug_writeSimpleHierarchyDotFiles() {
1645
1646     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1647     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1648       Descriptor desc = (Descriptor) iterator.next();
1649       getHierarchyGraph(desc).writeGraph();
1650       getSimpleHierarchyGraph(desc).writeGraph();
1651     }
1652
1653   }
1654
1655   private void debug_writeSkeletonHierarchyDotFiles() {
1656
1657     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1658     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1659       Descriptor desc = (Descriptor) iterator.next();
1660       getSkeletonHierarchyGraph(desc).writeGraph();
1661     }
1662
1663   }
1664
1665   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
1666
1667     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1668     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1669       Descriptor desc = (Descriptor) iterator.next();
1670       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
1671     }
1672
1673   }
1674
1675   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
1676     return mapDescriptorToSimpleHierarchyGraph.get(d);
1677   }
1678
1679   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
1680     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
1681       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1682     }
1683     return mapDescriptorToSkeletonHierarchyGraph.get(d);
1684   }
1685
1686   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
1687     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
1688       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1689     }
1690     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
1691   }
1692
1693   private void constructHierarchyGraph() {
1694
1695     // do fixed-point analysis
1696
1697     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1698
1699     // Collections.sort(descriptorListToAnalyze, new
1700     // Comparator<MethodDescriptor>() {
1701     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
1702     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
1703     // }
1704     // });
1705
1706     // current descriptors to visit in fixed-point interprocedural analysis,
1707     // prioritized by dependency in the call graph
1708     methodDescriptorsToVisitStack.clear();
1709
1710     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1711     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1712
1713     while (!descriptorListToAnalyze.isEmpty()) {
1714       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1715       methodDescriptorsToVisitStack.add(md);
1716     }
1717
1718     // analyze scheduled methods until there are no more to visit
1719     while (!methodDescriptorsToVisitStack.isEmpty()) {
1720       // start to analyze leaf node
1721       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1722
1723       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
1724       // MethodSummary methodSummary = new MethodSummary(md);
1725
1726       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
1727       // curMethodInfo = methodInfo;
1728
1729       System.out.println();
1730       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
1731
1732       constructHierarchyGraph(md, hierarchyGraph);
1733
1734       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
1735       // MethodSummary prevMethodSummary = getMethodSummary(md);
1736
1737       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
1738
1739         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
1740         // mapDescToLocationSummary.put(md, methodSummary);
1741
1742         // results for callee changed, so enqueue dependents caller for
1743         // further analysis
1744         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
1745         while (depsItr.hasNext()) {
1746           MethodDescriptor methodNext = depsItr.next();
1747           if (!methodDescriptorsToVisitStack.contains(methodNext)
1748               && methodDescriptorToVistSet.contains(methodNext)) {
1749             methodDescriptorsToVisitStack.add(methodNext);
1750           }
1751         }
1752
1753       }
1754
1755     }
1756
1757     setupToAnalyze();
1758     while (!toAnalyzeIsEmpty()) {
1759       ClassDescriptor cd = toAnalyzeNext();
1760       HierarchyGraph graph = getHierarchyGraph(cd);
1761       for (Iterator iter = cd.getFields(); iter.hasNext();) {
1762         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
1763         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
1764           graph.getHNode(fieldDesc);
1765         }
1766       }
1767     }
1768
1769     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1770     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1771       Descriptor key = (Descriptor) iterator.next();
1772       HierarchyGraph graph = getHierarchyGraph(key);
1773
1774       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
1775       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
1776         HNode node = (HNode) iterator2.next();
1777         if (!node.isSkeleton() && !node.isCombinationNode()) {
1778           if (graph.getIncomingNodeSet(node).size() == 0) {
1779             nodeToBeConnected.add(node);
1780           }
1781         }
1782       }
1783
1784       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
1785         HNode node = (HNode) iterator2.next();
1786         System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
1787         graph.addEdge(graph.getHNode(TOPDESC), node);
1788       }
1789
1790     }
1791
1792   }
1793
1794   private HierarchyGraph getHierarchyGraph(Descriptor d) {
1795     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
1796       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
1797     }
1798     return mapDescriptorToHierarchyGraph.get(d);
1799   }
1800
1801   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
1802
1803     // visit each node of method flow graph
1804     FlowGraph fg = getFlowGraph(md);
1805     Set<FlowNode> nodeSet = fg.getNodeSet();
1806
1807     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
1808     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
1809       Descriptor desc = (Descriptor) iterator.next();
1810       methodGraph.getHNode(desc).setSkeleton(true);
1811     }
1812
1813     // for the method lattice, we need to look at the first element of
1814     // NTuple<Descriptor>
1815     boolean hasGlobalAccess = false;
1816     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1817       FlowNode srcNode = (FlowNode) iterator.next();
1818
1819       // if the srcNode is started with the global descriptor
1820       // need to set as a skeleton node
1821       if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) {
1822         hasGlobalAccess = true;
1823       }
1824
1825       Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(srcNode);
1826       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
1827         FlowEdge outEdge = (FlowEdge) iterator2.next();
1828         FlowNode dstNode = outEdge.getDst();
1829
1830         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
1831         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
1832
1833         if (outEdge.getInitTuple().equals(srcNodeTuple)
1834             && outEdge.getEndTuple().equals(dstNodeTuple)) {
1835
1836           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
1837           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
1838
1839           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
1840               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
1841
1842             // value flows between fields
1843             Descriptor desc = srcCurTuple.get(0);
1844             ClassDescriptor classDesc;
1845
1846             if (desc.equals(GLOBALDESC)) {
1847               classDesc = md.getClassDesc();
1848             } else {
1849               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
1850               classDesc = varDesc.getType().getClassDesc();
1851             }
1852             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
1853
1854           } else {
1855             // value flow between local var - local var or local var - field
1856
1857             Descriptor srcDesc = srcCurTuple.get(0);
1858             Descriptor dstDesc = dstCurTuple.get(0);
1859
1860             methodGraph.addEdge(srcDesc, dstDesc);
1861
1862             if (fg.isParamDesc(srcDesc)) {
1863               methodGraph.setParamHNode(srcDesc);
1864             }
1865             if (fg.isParamDesc(dstDesc)) {
1866               methodGraph.setParamHNode(dstDesc);
1867             }
1868
1869           }
1870
1871         }
1872       }
1873     }
1874
1875     // If the method accesses static fields
1876     // set hasGloabalAccess true in the method summary.
1877     if (hasGlobalAccess) {
1878       getMethodSummary(md).setHasGlobalAccess();
1879     }
1880     methodGraph.getHNode(GLOBALDESC).setSkeleton(true);
1881
1882     if (ssjava.getMethodContainingSSJavaLoop().equals(md)) {
1883       // if the current method contains the event loop
1884       // we need to set all nodes of the hierarchy graph as a skeleton node
1885       Set<HNode> hnodeSet = methodGraph.getNodeSet();
1886       for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) {
1887         HNode hnode = (HNode) iterator.next();
1888         hnode.setSkeleton(true);
1889       }
1890     }
1891
1892   }
1893
1894   private MethodSummary getMethodSummary(MethodDescriptor md) {
1895     if (!mapDescToLocationSummary.containsKey(md)) {
1896       mapDescToLocationSummary.put(md, new MethodSummary(md));
1897     }
1898     return (MethodSummary) mapDescToLocationSummary.get(md);
1899   }
1900
1901   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
1902
1903     String classSymbol = cd.getSymbol();
1904     int idx = classSymbol.lastIndexOf("$");
1905     if (idx != -1) {
1906       classSymbol = classSymbol.substring(idx + 1);
1907     }
1908
1909     String pattern = "class " + classSymbol + " ";
1910     if (strLine.indexOf(pattern) != -1) {
1911       mapDescToDefinitionLine.put(cd, lineNum);
1912     }
1913   }
1914
1915   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
1916       int lineNum) {
1917     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
1918       MethodDescriptor md = (MethodDescriptor) iterator.next();
1919       String pattern = md.getMethodDeclaration();
1920       if (strLine.indexOf(pattern) != -1) {
1921         mapDescToDefinitionLine.put(md, lineNum);
1922         methodSet.remove(md);
1923         return;
1924       }
1925     }
1926
1927   }
1928
1929   private void readOriginalSourceFiles() {
1930
1931     SymbolTable classtable = state.getClassSymbolTable();
1932
1933     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
1934     classDescSet.addAll(classtable.getValueSet());
1935
1936     try {
1937       // inefficient implement. it may re-visit the same file if the file
1938       // contains more than one class definitions.
1939       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
1940         ClassDescriptor cd = (ClassDescriptor) iterator.next();
1941
1942         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
1943         methodSet.addAll(cd.getMethodTable().getValueSet());
1944
1945         String sourceFileName = cd.getSourceFileName();
1946         Vector<String> lineVec = new Vector<String>();
1947
1948         mapFileNameToLineVector.put(sourceFileName, lineVec);
1949
1950         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
1951         String strLine;
1952         int lineNum = 1;
1953         lineVec.add(""); // the index is started from 1.
1954         while ((strLine = in.readLine()) != null) {
1955           lineVec.add(lineNum, strLine);
1956           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
1957           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
1958           lineNum++;
1959         }
1960
1961       }
1962
1963     } catch (IOException e) {
1964       e.printStackTrace();
1965     }
1966
1967   }
1968
1969   private String generateLatticeDefinition(Descriptor desc) {
1970
1971     Set<String> sharedLocSet = new HashSet<String>();
1972
1973     SSJavaLattice<String> lattice = getLattice(desc);
1974     String rtr = "@LATTICE(\"";
1975
1976     Map<String, Set<String>> map = lattice.getTable();
1977     Set<String> keySet = map.keySet();
1978     boolean first = true;
1979     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1980       String key = (String) iterator.next();
1981       if (!key.equals(lattice.getTopItem())) {
1982         Set<String> connectedSet = map.get(key);
1983
1984         if (connectedSet.size() == 1) {
1985           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
1986             if (!first) {
1987               rtr += ",";
1988             } else {
1989               rtr += "LOC,";
1990               first = false;
1991             }
1992             rtr += key;
1993             if (lattice.isSharedLoc(key)) {
1994               rtr += "," + key + "*";
1995             }
1996           }
1997         }
1998
1999         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
2000           String loc = (String) iterator2.next();
2001           if (!loc.equals(lattice.getBottomItem())) {
2002             if (!first) {
2003               rtr += ",";
2004             } else {
2005               rtr += "LOC,";
2006               first = false;
2007             }
2008             rtr += loc + "<" + key;
2009             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
2010               rtr += "," + key + "*";
2011               sharedLocSet.add(key);
2012             }
2013             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
2014               rtr += "," + loc + "*";
2015               sharedLocSet.add(loc);
2016             }
2017
2018           }
2019         }
2020       }
2021     }
2022
2023     rtr += "\")";
2024
2025     if (desc instanceof MethodDescriptor) {
2026       System.out.println("#EXTRA LOC DECLARATION GEN=" + desc);
2027
2028       MethodDescriptor md = (MethodDescriptor) desc;
2029       MethodSummary methodSummary = getMethodSummary(md);
2030
2031       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) {
2032         TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
2033         if (returnType != null && (!returnType.isVoid())) {
2034           rtr +=
2035               "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")";
2036         }
2037         CompositeLocation pcLoc = methodSummary.getPCLoc();
2038         if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
2039           rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
2040         }
2041       }
2042
2043       if (!md.isStatic()) {
2044         rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")";
2045       }
2046       rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")";
2047
2048     }
2049
2050     return rtr;
2051   }
2052
2053   private void generateAnnoatedCode() {
2054
2055     readOriginalSourceFiles();
2056
2057     setupToAnalyze();
2058     while (!toAnalyzeIsEmpty()) {
2059       ClassDescriptor cd = toAnalyzeNext();
2060
2061       setupToAnalazeMethod(cd);
2062
2063       String sourceFileName = cd.getSourceFileName();
2064
2065       if (cd.isInterface()) {
2066         continue;
2067       }
2068
2069       int classDefLine = mapDescToDefinitionLine.get(cd);
2070       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
2071
2072       LocationSummary fieldLocSummary = getLocationSummary(cd);
2073
2074       String fieldLatticeDefStr = generateLatticeDefinition(cd);
2075       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
2076       sourceVec.set(classDefLine, annoatedSrc);
2077
2078       // generate annotations for field declarations
2079       // Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
2080       Map<String, String> mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName();
2081
2082       for (Iterator iter = cd.getFields(); iter.hasNext();) {
2083         FieldDescriptor fd = (FieldDescriptor) iter.next();
2084
2085         String locAnnotationStr;
2086         // CompositeLocation inferLoc = inferLocMap.get(fd);
2087         String locName = mapFieldNameToLocName.get(fd.getSymbol());
2088
2089         if (locName != null) {
2090           // infer loc is null if the corresponding field is static and final
2091           // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2092           locAnnotationStr = "@LOC(\"" + locName + "\")";
2093           int fdLineNum = fd.getLineNum();
2094           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
2095           String fieldDeclaration = fd.toString();
2096           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
2097           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
2098           sourceVec.set(fdLineNum, annoatedStr);
2099         }
2100
2101       }
2102
2103       while (!toAnalyzeMethodIsEmpty()) {
2104         MethodDescriptor md = toAnalyzeMethodNext();
2105
2106         if (!ssjava.needTobeAnnotated(md)) {
2107           continue;
2108         }
2109
2110         SSJavaLattice<String> methodLattice = md2lattice.get(md);
2111         if (methodLattice != null) {
2112
2113           int methodDefLine = md.getLineNum();
2114
2115           // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
2116           // Map<Descriptor, CompositeLocation> methodInferLocMap =
2117           // methodLocInfo.getMapDescToInferLocation();
2118
2119           MethodSummary methodSummary = getMethodSummary(md);
2120
2121           Map<Descriptor, CompositeLocation> mapVarDescToInferLoc =
2122               methodSummary.getMapVarDescToInferCompositeLocation();
2123           System.out.println("-----md=" + md);
2124           System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc);
2125
2126           Set<Descriptor> localVarDescSet = mapVarDescToInferLoc.keySet();
2127
2128           Set<String> localLocElementSet = methodLattice.getElementSet();
2129
2130           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
2131             Descriptor localVarDesc = (Descriptor) iterator.next();
2132             System.out.println("-------localVarDesc=" + localVarDesc);
2133             CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc);
2134
2135             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
2136             if (!localLocElementSet.contains(localLocIdentifier)) {
2137               methodLattice.put(localLocIdentifier);
2138             }
2139
2140             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2141
2142             if (!isParameter(md, localVarDesc)) {
2143               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
2144                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
2145                 String orgSourceLine = sourceVec.get(varLineNum);
2146                 int idx =
2147                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
2148                 assert (idx != -1);
2149                 String annoatedStr =
2150                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
2151                         + orgSourceLine.substring(idx);
2152                 sourceVec.set(varLineNum, annoatedStr);
2153               }
2154             } else {
2155               String methodDefStr = sourceVec.get(methodDefLine);
2156
2157               int idx =
2158                   getParamLocation(methodDefStr,
2159                       generateVarDeclaration((VarDescriptor) localVarDesc));
2160               System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc
2161                   + " idx=" + idx);
2162               assert (idx != -1);
2163
2164               String annoatedStr =
2165                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
2166                       + methodDefStr.substring(idx);
2167               sourceVec.set(methodDefLine, annoatedStr);
2168             }
2169
2170           }
2171
2172           // check if the lattice has to have the location type for the this
2173           // reference...
2174
2175           // boolean needToAddthisRef = hasThisReference(md);
2176           // if (localLocElementSet.contains("this")) {
2177           // methodLattice.put("this");
2178           // }
2179
2180           String methodLatticeDefStr = generateLatticeDefinition(md);
2181           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
2182           sourceVec.set(methodDefLine, annoatedStr);
2183
2184         }
2185       }
2186
2187     }
2188
2189     codeGen();
2190   }
2191
2192   private boolean hasThisReference(MethodDescriptor md) {
2193
2194     FlowGraph fg = getFlowGraph(md);
2195     Set<FlowNode> nodeSet = fg.getNodeSet();
2196     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2197       FlowNode flowNode = (FlowNode) iterator.next();
2198       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
2199         return true;
2200       }
2201     }
2202
2203     return false;
2204   }
2205
2206   private int getParamLocation(String methodStr, String paramStr) {
2207
2208     String pattern = paramStr + ",";
2209
2210     int idx = methodStr.indexOf(pattern);
2211     if (idx != -1) {
2212       return idx;
2213     } else {
2214       pattern = paramStr + ")";
2215       return methodStr.indexOf(pattern);
2216     }
2217
2218   }
2219
2220   private String generateVarDeclaration(VarDescriptor varDesc) {
2221
2222     TypeDescriptor td = varDesc.getType();
2223     String rtr = td.toString();
2224     if (td.isArray()) {
2225       for (int i = 0; i < td.getArrayCount(); i++) {
2226         rtr += "[]";
2227       }
2228     }
2229     rtr += " " + varDesc.getName();
2230     return rtr;
2231
2232   }
2233
2234   private String generateLocationAnnoatation(CompositeLocation loc) {
2235     System.out.println("loc=" + loc);
2236     String rtr = "";
2237     // method location
2238     Location methodLoc = loc.get(0);
2239     rtr += methodLoc.getLocIdentifier();
2240
2241     for (int i = 1; i < loc.getSize(); i++) {
2242       Location element = loc.get(i);
2243       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
2244     }
2245
2246     return rtr;
2247   }
2248
2249   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
2250     return getFlowGraph(md).isParamDesc(localVarDesc);
2251   }
2252
2253   private String extractFileName(String fileName) {
2254     int idx = fileName.lastIndexOf("/");
2255     if (idx == -1) {
2256       return fileName;
2257     } else {
2258       return fileName.substring(idx + 1);
2259     }
2260
2261   }
2262
2263   private void codeGen() {
2264
2265     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
2266     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
2267       String orgFileName = (String) iterator.next();
2268       String outputFileName = extractFileName(orgFileName);
2269
2270       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
2271
2272       try {
2273
2274         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
2275         BufferedWriter out = new BufferedWriter(fileWriter);
2276
2277         for (int i = 0; i < sourceVec.size(); i++) {
2278           out.write(sourceVec.get(i));
2279           out.newLine();
2280         }
2281         out.close();
2282       } catch (IOException e) {
2283         e.printStackTrace();
2284       }
2285
2286     }
2287
2288   }
2289
2290   private void checkLattices() {
2291
2292     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
2293
2294     // current descriptors to visit in fixed-point interprocedural analysis,
2295     // prioritized by
2296     // dependency in the call graph
2297     methodDescriptorsToVisitStack.clear();
2298
2299     // descriptorListToAnalyze.removeFirst();
2300
2301     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2302     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2303
2304     while (!descriptorListToAnalyze.isEmpty()) {
2305       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2306       checkLatticesOfVirtualMethods(md);
2307     }
2308
2309   }
2310
2311   private void debug_writeLatticeDotFile() {
2312     // generate lattice dot file
2313
2314     setupToAnalyze();
2315
2316     while (!toAnalyzeIsEmpty()) {
2317       ClassDescriptor cd = toAnalyzeNext();
2318
2319       setupToAnalazeMethod(cd);
2320
2321       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
2322       if (classLattice != null) {
2323         ssjava.writeLatticeDotFile(cd, null, classLattice);
2324         debug_printDescriptorToLocNameMapping(cd);
2325       }
2326
2327       while (!toAnalyzeMethodIsEmpty()) {
2328         MethodDescriptor md = toAnalyzeMethodNext();
2329         SSJavaLattice<String> methodLattice = md2lattice.get(md);
2330         if (methodLattice != null) {
2331           ssjava.writeLatticeDotFile(cd, md, methodLattice);
2332           debug_printDescriptorToLocNameMapping(md);
2333         }
2334       }
2335     }
2336
2337   }
2338
2339   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
2340
2341     LocationInfo info = getLocationInfo(desc);
2342     System.out.println("## " + desc + " ##");
2343     System.out.println(info.getMapDescToInferLocation());
2344     LocationInfo locInfo = getLocationInfo(desc);
2345     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
2346     System.out.println("###################");
2347
2348   }
2349
2350   private void calculateExtraLocations() {
2351
2352     LinkedList<MethodDescriptor> methodDescList = ssjava.getSortedDescriptors();
2353     for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) {
2354       MethodDescriptor md = (MethodDescriptor) iterator.next();
2355       if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2356         calculateExtraLocations(md);
2357       }
2358     }
2359
2360   }
2361
2362   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
2363
2364     if (!md.isStatic()) {
2365       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2366       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
2367
2368       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
2369         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
2370         if (!md.equals(mdCallee)) {
2371           checkConsistency(md, mdCallee);
2372         }
2373       }
2374
2375     }
2376
2377   }
2378
2379   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
2380
2381     // check that two lattice have the same relations between parameters(+PC
2382     // LOC, GLOBAL_LOC RETURN LOC)
2383
2384     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
2385     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
2386
2387     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
2388     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
2389
2390     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
2391     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
2392
2393     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
2394
2395     // add location types of paramters
2396     for (int idx = 0; idx < numParam; idx++) {
2397       list1.add(paramMap1.get(Integer.valueOf(idx)));
2398       list2.add(paramMap2.get(Integer.valueOf(idx)));
2399     }
2400
2401     // add program counter location
2402     list1.add(locInfo1.getPCLoc());
2403     list2.add(locInfo2.getPCLoc());
2404
2405     if (!md1.getReturnType().isVoid()) {
2406       // add return value location
2407       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
2408       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
2409       list1.add(rtrLoc1);
2410       list2.add(rtrLoc2);
2411     }
2412
2413     // add global location type
2414     if (md1.isStatic()) {
2415       CompositeLocation globalLoc1 =
2416           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
2417       CompositeLocation globalLoc2 =
2418           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
2419       list1.add(globalLoc1);
2420       list2.add(globalLoc2);
2421     }
2422
2423     for (int i = 0; i < list1.size(); i++) {
2424       CompositeLocation locA1 = list1.get(i);
2425       CompositeLocation locA2 = list2.get(i);
2426       for (int k = 0; k < list1.size(); k++) {
2427         if (i != k) {
2428           CompositeLocation locB1 = list1.get(k);
2429           CompositeLocation locB2 = list2.get(k);
2430           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
2431
2432           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
2433
2434           if (r1 != r2) {
2435             throw new Error("The method " + md1 + " is not consistent with the method " + md2
2436                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
2437                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
2438           }
2439         }
2440       }
2441     }
2442
2443   }
2444
2445   private String getSymbol(int idx, FlowNode node) {
2446     Descriptor desc = node.getDescTuple().get(idx);
2447     return desc.getSymbol();
2448   }
2449
2450   private Descriptor getDescriptor(int idx, FlowNode node) {
2451     Descriptor desc = node.getDescTuple().get(idx);
2452     return desc;
2453   }
2454
2455   private void calculatePCLOC(MethodDescriptor md) {
2456
2457     System.out.println("#CalculatePCLOC");
2458     MethodSummary methodSummary = getMethodSummary(md);
2459     FlowGraph fg = getFlowGraph(md);
2460     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
2461
2462     // calculate the initial program counter location
2463     // PC location is higher than location types of parameters which has incoming flows.
2464
2465     Set<NTuple<Location>> paramLocTupleHavingInFlowSet = new HashSet<NTuple<Location>>();
2466     Set<Descriptor> paramDescNOTHavingInFlowSet = new HashSet<Descriptor>();
2467     // Set<FlowNode> paramNodeNOThavingInFlowSet = new HashSet<FlowNode>();
2468
2469     int numParams = fg.getNumParameters();
2470     for (int i = 0; i < numParams; i++) {
2471       FlowNode paramFlowNode = fg.getParamFlowNode(i);
2472       Descriptor prefix = paramFlowNode.getDescTuple().get(0);
2473       NTuple<Descriptor> paramDescTuple = paramFlowNode.getCurrentDescTuple();
2474       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
2475
2476       Set<FlowNode> inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix);
2477       if (inNodeToParamSet.size() > 0) {
2478         // parameter has in-value flows
2479
2480         for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) {
2481           FlowNode inNode = (FlowNode) iterator.next();
2482           Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(inNode);
2483           for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
2484             FlowEdge flowEdge = (FlowEdge) iterator2.next();
2485             if (flowEdge.getEndTuple().startsWith(prefix)) {
2486               NTuple<Location> paramLocTupleWithIncomingFlow =
2487                   translateToLocTuple(md, flowEdge.getEndTuple());
2488               paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow);
2489             }
2490           }
2491         }
2492
2493         // paramLocTupleHavingInFlowSet.add(paramLocTuple);
2494       } else {
2495         // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple));
2496         paramDescNOTHavingInFlowSet.add(prefix);
2497       }
2498     }
2499
2500     System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet);
2501
2502     if (paramLocTupleHavingInFlowSet.size() > 0
2503     /* && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet) */) {
2504
2505       // Here, generates a location in the method lattice that is higher than the
2506       // paramLocTupleHavingInFlowSet
2507       NTuple<Location> pcLocTuple =
2508           generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC);
2509
2510       NTuple<Descriptor> pcDescTuple = translateToDescTuple(pcLocTuple);
2511
2512       // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of
2513       // parameters that do not have incoming flows
2514
2515       for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) {
2516         FlowNode node = (FlowNode) iterator.next();
2517
2518         if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) {
2519           fg.addValueFlowEdge(pcDescTuple, node.getDescTuple());
2520         }
2521       }
2522
2523       System.out.println("pcLoc=" + pcLocTuple);
2524
2525       methodSummary.setPCLoc(new CompositeLocation(pcLocTuple));
2526     }
2527   }
2528
2529   private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg,
2530       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
2531
2532     int numParam = fg.getNumParameters();
2533     int size = paramLocTupleHavingInFlowSet.size();
2534
2535     if (!md.isStatic()) {
2536
2537       // if the method is not static && there is a parameter composite location &&
2538       // it is started with 'this',
2539       // paramLocTupleHavingInFlowSet need to have 'this' parameter.
2540
2541       FlowNode thisParamNode = fg.getParamFlowNode(0);
2542       NTuple<Location> thisParamLocTuple =
2543           translateToLocTuple(md, thisParamNode.getCurrentDescTuple());
2544
2545       if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) {
2546
2547         for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
2548           NTuple<Location> paramTuple = (NTuple<Location>) iterator.next();
2549           if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) {
2550             // paramLocTupleHavingInFlowSet.add(thisParamLocTuple);
2551             // break;
2552             size++;
2553           }
2554         }
2555
2556       }
2557     }
2558
2559     if (size == numParam) {
2560       return true;
2561     } else {
2562       return false;
2563     }
2564
2565   }
2566
2567   private void calculateRETURNLOC(MethodDescriptor md) {
2568
2569     System.out.println("#calculateRETURNLOC= " + md);
2570     // calculate a return location:
2571     // the return location type is lower than all parameters and the location of return values
2572     MethodSummary methodSummary = getMethodSummary(md);
2573     FlowGraph fg = getFlowGraph(md);
2574     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
2575     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
2576
2577     if (!md.getReturnType().isVoid()) {
2578       // first, generate the set of return value location types that starts
2579       // with 'this' reference
2580
2581       Set<FlowNode> paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md);
2582       System.out.println("paramFlowNodeFlowingToReturnValueSet="
2583           + paramFlowNodeFlowingToReturnValueSet);
2584
2585       Set<NTuple<Location>> tupleToBeHigherThanReturnLocSet = new HashSet<NTuple<Location>>();
2586       for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) {
2587         FlowNode fn = (FlowNode) iterator.next();
2588         NTuple<Descriptor> paramDescTuple = fn.getCurrentDescTuple();
2589         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple));
2590       }
2591
2592       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
2593       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2594         FlowNode returnNode = (FlowNode) iterator.next();
2595         NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
2596         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple));
2597       }
2598       System.out.println("-flow graph's returnNodeSet=" + returnNodeSet);
2599       System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet);
2600
2601       // Here, generates a return location in the method lattice that is lower than the
2602       // locFlowingToReturnValueSet
2603       NTuple<Location> returnLocTuple =
2604           generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC);
2605
2606       System.out.println("returnLocTuple=" + returnLocTuple);
2607
2608       NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnLocTuple);
2609       for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) {
2610         NTuple<Location> higherTuple = (NTuple<Location>) iterator.next();
2611         fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple);
2612       }
2613
2614       fg.getFlowNode(returnDescTuple).setSkeleton(true);
2615       System.out.println("fg node set=" + fg.getNodeSet());
2616
2617       methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple));
2618
2619       // skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2620       // FlowNode returnNode = (FlowNode) iterator.next();
2621       //
2622       // NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
2623       // NTuple<Location> returnLocTuple = translateToLocTuple(md, returnDescTuple);
2624       //
2625       // if (returnLocTuple.get(0).getLocDescriptor().equals(md.getThis())) {
2626       // // if the location type of the return value matches "this" reference
2627       // // then, check whether this return value is equal to/lower than all
2628       // // of parameters that possibly flow into the return values
2629       // for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
2630       // CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
2631       //
2632       // if ((!paramInferLoc.equals(returnLocTuple))
2633       // && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
2634       // continue skip;
2635       // }
2636       // }
2637       // inferFieldReturnLocSet.add(returnLocTuple);
2638       //
2639       // }
2640       // }
2641
2642       // if (inferFieldReturnLocSet.size() > 0) {
2643       //
2644       // // CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
2645       // CompositeLocation returnLoc = null;
2646       // if (returnLoc == null) {
2647       // // in this case, assign <'this',bottom> to the RETURNLOC
2648       // returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
2649       // returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
2650       // .getBottomItem()));
2651       // }
2652       // methodInfo.setReturnLoc(returnLoc);
2653       //
2654       // } else {
2655       // String returnLocSymbol = "RETURNLOC";
2656       // CompositeLocation returnLocInferLoc =
2657       // new CompositeLocation(new Location(md, returnLocSymbol));
2658       // methodInfo.setReturnLoc(returnLocInferLoc);
2659       //
2660       // for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2661       // Integer paramIdx = (Integer) iterator.next();
2662       // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2663       // String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
2664       // if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
2665       // // TODO
2666       // // addRelationHigherToLower(methodLattice, methodInfo,
2667       // // paramLocLocalSymbol,
2668       // // returnLocSymbol);
2669       // }
2670       // }
2671       //
2672       // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2673       // FlowNode returnNode = (FlowNode) iterator.next();
2674       // CompositeLocation inferLoc =
2675       // generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2676       // if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
2677       // // TODO
2678       // // addRelation(methodLattice, methodInfo, inferLoc,
2679       // // returnLocInferLoc);
2680       // }
2681       // }
2682       //
2683       // }
2684
2685     }
2686   }
2687
2688   private void calculateExtraLocations(MethodDescriptor md) {
2689     // calcualte pcloc, returnloc,...
2690
2691     System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md);
2692
2693     calculatePCLOC(md);
2694     calculateRETURNLOC(md);
2695
2696   }
2697
2698   private NTuple<Location> generateLocTupleRelativeTo(MethodDescriptor md,
2699       Set<NTuple<Location>> paramLocTupleHavingInFlowSet, String locNamePrefix) {
2700
2701     System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet);
2702
2703     NTuple<Location> higherLocTuple = new NTuple<Location>();
2704
2705     VarDescriptor thisVarDesc = md.getThis();
2706     // check if all paramter loc tuple is started with 'this' reference
2707     boolean hasParamNotStartedWithThisRef = false;
2708
2709     int minSize = 0;
2710
2711     Set<NTuple<Location>> paramLocTupleStartedWithThis = new HashSet<NTuple<Location>>();
2712
2713     next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
2714       NTuple<Location> paramLocTuple = (NTuple<Location>) iterator.next();
2715       Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor();
2716       if (!paramLocalDesc.equals(thisVarDesc)) {
2717
2718         Set<FlowNode> inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc);
2719         for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
2720           FlowNode flowNode = (FlowNode) iterator2.next();
2721           if (flowNode.getDescTuple().startsWith(thisVarDesc)) {
2722             System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS");
2723             continue next;
2724           }
2725         }
2726         hasParamNotStartedWithThisRef = true;
2727
2728       } else if (paramLocTuple.size() > 1) {
2729         paramLocTupleStartedWithThis.add(paramLocTuple);
2730         if (minSize == 0 || minSize > paramLocTuple.size()) {
2731           minSize = paramLocTuple.size();
2732         }
2733       }
2734     }
2735
2736     System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis);
2737     Descriptor enclosingDesc = md;
2738     if (hasParamNotStartedWithThisRef) {
2739       // in this case, PCLOC will be the local location
2740     } else {
2741       // all parameter is started with 'this', so PCLOC will be set relative to the composite
2742       // location started with 'this'.
2743       for (int idx = 0; idx < minSize - 1; idx++) {
2744         Set<Descriptor> locDescSet = new HashSet<Descriptor>();
2745         Location curLoc = null;
2746         NTuple<Location> paramLocTuple = null;
2747         for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) {
2748           paramLocTuple = (NTuple<Location>) iterator.next();
2749           System.out.println("-----paramLocTuple=" + paramLocTuple + "  idx=" + idx);
2750           curLoc = paramLocTuple.get(idx);
2751           Descriptor locDesc = curLoc.getLocDescriptor();
2752           locDescSet.add(locDesc);
2753         }
2754         System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx);
2755         if (locDescSet.size() != 1) {
2756           break;
2757         }
2758         Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor());
2759         higherLocTuple.add(newLocElement);
2760         enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor());
2761       }
2762
2763     }
2764
2765     String pcLocIdentifier = locNamePrefix + (locSeed++);
2766     NameDescriptor pcLocDesc = new NameDescriptor(pcLocIdentifier);
2767     Location newLoc = new Location(enclosingDesc, pcLocDesc);
2768     higherLocTuple.add(newLoc);
2769
2770     System.out.println("---new loc tuple=" + higherLocTuple);
2771
2772     return higherLocTuple;
2773
2774   }
2775
2776   public ClassDescriptor getClassTypeDescriptor(Descriptor in) {
2777
2778     if (in instanceof VarDescriptor) {
2779       return ((VarDescriptor) in).getType().getClassDesc();
2780     } else if (in instanceof FieldDescriptor) {
2781       return ((FieldDescriptor) in).getType().getClassDesc();
2782     }
2783     // else if (in instanceof LocationDescriptor) {
2784     // // here is the case that the descriptor 'in' is the last element of the assigned composite
2785     // // location
2786     // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc();
2787     // }
2788     else {
2789       return null;
2790     }
2791
2792   }
2793
2794   private Set<NTuple<Location>> calculateHighestLocTupleSet(
2795       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
2796
2797     Set<NTuple<Location>> highestSet = new HashSet<NTuple<Location>>();
2798
2799     Iterator<NTuple<Location>> iterator = paramLocTupleHavingInFlowSet.iterator();
2800     NTuple<Location> highest = iterator.next();
2801
2802     for (; iterator.hasNext();) {
2803       NTuple<Location> curLocTuple = (NTuple<Location>) iterator.next();
2804       if (isHigherThan(curLocTuple, highest)) {
2805         System.out.println(curLocTuple + " is greater than " + highest);
2806         highest = curLocTuple;
2807       }
2808     }
2809
2810     highestSet.add(highest);
2811
2812     MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor();
2813     VarDescriptor thisVarDesc = md.getThis();
2814
2815     System.out.println("highest=" + highest);
2816
2817     for (Iterator<NTuple<Location>> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) {
2818       NTuple<Location> curLocTuple = iter.next();
2819
2820       if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) {
2821
2822         System.out.println("add it to the highest set=" + curLocTuple);
2823         highestSet.add(curLocTuple);
2824
2825       }
2826     }
2827
2828     return highestSet;
2829
2830   }
2831
2832   private void calculateExtraLocations2(MethodDescriptor md) {
2833     // calcualte pcloc, returnloc,...
2834
2835     SSJavaLattice<String> methodLattice = getMethodLattice(md);
2836     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
2837     FlowGraph fg = getFlowGraph(md);
2838     Set<FlowNode> nodeSet = fg.getNodeSet();
2839
2840     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2841       FlowNode flowNode = (FlowNode) iterator.next();
2842       if (flowNode.isDeclaratonNode()) {
2843         CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
2844         String locIdentifier = inferLoc.get(0).getLocIdentifier();
2845         if (!methodLattice.containsKey(locIdentifier)) {
2846           methodLattice.put(locIdentifier);
2847         }
2848
2849       }
2850     }
2851
2852     Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
2853     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
2854
2855     if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2856       // calculate the initial program counter location
2857       // PC location is higher than location types of all parameters
2858       String pcLocSymbol = "PCLOC";
2859
2860       Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
2861
2862       for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2863         Integer paramIdx = (Integer) iterator.next();
2864
2865         FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
2866
2867         if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
2868           // parameter has in-value flows
2869           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2870           paramInFlowSet.add(inferLoc);
2871         }
2872       }
2873
2874       if (paramInFlowSet.size() > 0) {
2875         CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
2876         assert (lowestLoc != null);
2877         methodInfo.setPCLoc(lowestLoc);
2878       }
2879
2880     }
2881
2882     // calculate a return location
2883     // the return location type is lower than all parameters and location
2884     // types
2885     // of return values
2886     if (!md.getReturnType().isVoid()) {
2887       // first, generate the set of return value location types that starts
2888       // with
2889       // 'this' reference
2890
2891       Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
2892
2893       Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
2894       Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
2895       if (paramFlowNode != null) {
2896         for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
2897           FlowNode fn = (FlowNode) iterator.next();
2898           CompositeLocation inferLoc =
2899               generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
2900           inferParamLocSet.add(inferLoc);
2901         }
2902       }
2903
2904       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
2905
2906       skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2907         FlowNode returnNode = (FlowNode) iterator.next();
2908         CompositeLocation inferReturnLoc =
2909             generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2910         if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
2911           // if the location type of the return value matches "this" reference
2912           // then, check whether this return value is equal to/lower than all
2913           // of
2914           // parameters that possibly flow into the return values
2915           for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
2916             CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
2917
2918             if ((!paramInferLoc.equals(inferReturnLoc))
2919                 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
2920               continue skip;
2921             }
2922           }
2923           inferFieldReturnLocSet.add(inferReturnLoc);
2924
2925         }
2926       }
2927
2928       if (inferFieldReturnLocSet.size() > 0) {
2929
2930         CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
2931         if (returnLoc == null) {
2932           // in this case, assign <'this',bottom> to the RETURNLOC
2933           returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
2934           returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
2935               .getBottomItem()));
2936         }
2937         methodInfo.setReturnLoc(returnLoc);
2938
2939       } else {
2940         String returnLocSymbol = "RETURNLOC";
2941         CompositeLocation returnLocInferLoc =
2942             new CompositeLocation(new Location(md, returnLocSymbol));
2943         methodInfo.setReturnLoc(returnLocInferLoc);
2944
2945         for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2946           Integer paramIdx = (Integer) iterator.next();
2947           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2948           String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
2949           if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
2950             // TODO
2951             // addRelationHigherToLower(methodLattice, methodInfo,
2952             // paramLocLocalSymbol,
2953             // returnLocSymbol);
2954           }
2955         }
2956
2957         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2958           FlowNode returnNode = (FlowNode) iterator.next();
2959           CompositeLocation inferLoc =
2960               generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2961           if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
2962             // TODO
2963             // addRelation(methodLattice, methodInfo, inferLoc,
2964             // returnLocInferLoc);
2965           }
2966         }
2967
2968       }
2969
2970     }
2971   }
2972
2973   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
2974     Set<String> higherLocSet = new HashSet<String>();
2975
2976     Set<String> locSet = lattice.getTable().keySet();
2977     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
2978       String element = (String) iterator.next();
2979       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
2980         higherLocSet.add(element);
2981       }
2982     }
2983     return higherLocSet;
2984   }
2985
2986   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
2987       Set<CompositeLocation> set) {
2988
2989     CompositeLocation lowest = set.iterator().next();
2990
2991     if (set.size() == 1) {
2992       return lowest;
2993     }
2994
2995     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
2996       CompositeLocation loc = (CompositeLocation) iterator.next();
2997
2998       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
2999         // if there is a case where composite locations are incomparable, just
3000         // return null
3001         return null;
3002       }
3003
3004       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
3005         lowest = loc;
3006       }
3007     }
3008     return lowest;
3009   }
3010
3011   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3012       CompositeLocation comp2) {
3013
3014     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3015
3016     for (int idx = 0; idx < size; idx++) {
3017       Location loc1 = comp1.get(idx);
3018       Location loc2 = comp2.get(idx);
3019
3020       Descriptor desc1 = loc1.getDescriptor();
3021       Descriptor desc2 = loc2.getDescriptor();
3022
3023       if (!desc1.equals(desc2)) {
3024         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3025       }
3026
3027       String symbol1 = loc1.getLocIdentifier();
3028       String symbol2 = loc2.getLocIdentifier();
3029
3030       SSJavaLattice<String> lattice;
3031       if (idx == 0) {
3032         lattice = methodLattice;
3033       } else {
3034         lattice = getLattice(desc1);
3035       }
3036
3037       if (symbol1.equals(symbol2)) {
3038         continue;
3039       } else if (!lattice.isComparable(symbol1, symbol2)) {
3040         return false;
3041       }
3042
3043     }
3044
3045     return true;
3046   }
3047
3048   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3049       CompositeLocation comp2) {
3050
3051     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3052
3053     for (int idx = 0; idx < size; idx++) {
3054       Location loc1 = comp1.get(idx);
3055       Location loc2 = comp2.get(idx);
3056
3057       Descriptor desc1 = loc1.getDescriptor();
3058       Descriptor desc2 = loc2.getDescriptor();
3059
3060       if (!desc1.equals(desc2)) {
3061         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3062       }
3063
3064       String symbol1 = loc1.getLocIdentifier();
3065       String symbol2 = loc2.getLocIdentifier();
3066
3067       SSJavaLattice<String> lattice;
3068       if (idx == 0) {
3069         lattice = methodLattice;
3070       } else {
3071         lattice = getLattice(desc1);
3072       }
3073
3074       if (symbol1.equals(symbol2)) {
3075         continue;
3076       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
3077         return true;
3078       } else {
3079         return false;
3080       }
3081
3082     }
3083
3084     return false;
3085   }
3086
3087   private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller,
3088       MethodDescriptor mdCallee) {
3089
3090     System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller);
3091
3092     getSubGlobalFlowGraph(mdCallee);
3093
3094   }
3095
3096   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
3097     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
3098   }
3099
3100   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
3101       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
3102
3103     // if the parameter A reaches to the parameter B
3104     // then, add an edge the argument A -> the argument B to the caller's flow
3105     // graph
3106
3107     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
3108     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
3109     int numParam = calleeFlowGraph.getNumParameters();
3110
3111     for (int i = 0; i < numParam; i++) {
3112       for (int k = 0; k < numParam; k++) {
3113
3114         if (i != k) {
3115
3116           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
3117           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
3118
3119           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
3120           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
3121
3122           // check if the callee propagates an ordering constraints through
3123           // parameters
3124
3125           Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
3126           System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
3127           // System.out.println("-- localReachSet from param1=" + localReachSet);
3128
3129           NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
3130           NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
3131
3132           System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
3133               + paramDescTuple2);
3134           if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
3135             // if two parameters share the same prefix
3136             // it already has been assigned to a composite location
3137             // so we don't need to add an additional ordering relation caused by these two
3138             // paramters.
3139             continue;
3140           }
3141
3142           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 && localReachSet.contains(paramNode2)) {
3143             // need to propagate an ordering relation s.t. arg1 is higher
3144             // than arg2
3145
3146             // add a new flow between the corresponding arguments.
3147             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
3148             System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
3149
3150             // System.out
3151             // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
3152
3153           }
3154
3155           System.out.println();
3156         }
3157       }
3158     }
3159
3160     // if a parameter has a composite location and the first element of the parameter location
3161     // matches the callee's 'this'
3162     // we have a more specific constraint: the caller's corresponding argument is higher than the
3163     // parameter location which is translated into the caller
3164
3165     for (int idx = 0; idx < numParam; idx++) {
3166       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
3167       CompositeLocation compLoc = paramNode.getCompositeLocation();
3168       if (compLoc != null) {
3169         System.out.println("$$$COMPLOC CASE=" + compLoc);
3170         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
3171         NTuple<Descriptor> translatedParamTuple = translateCompositeLocationToCaller(min, compLoc);
3172         System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
3173         callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
3174       }
3175     }
3176
3177   }
3178
3179   private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
3180       MethodDescriptor mdCallee) {
3181
3182     System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
3183
3184     // if the parameter A reaches to the parameter B
3185     // then, add an edge the argument A -> the argument B to the caller's flow
3186     // graph
3187
3188     // TODO
3189     // also if a parameter is a composite location and is started with "this"
3190     // reference,
3191     // need to make sure that the corresponding argument is higher than the
3192     // translated location of
3193     // the parameter.
3194
3195     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
3196     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
3197     int numParam = calleeFlowGraph.getNumParameters();
3198
3199     for (int i = 0; i < numParam; i++) {
3200       for (int k = 0; k < numParam; k++) {
3201
3202         if (i != k) {
3203
3204           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
3205           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
3206
3207           System.out.println("param1=" + paramNode1 + " curDescTuple="
3208               + paramNode1.getCurrentDescTuple());
3209           System.out.println("param2=" + paramNode2 + " curDescTuple="
3210               + paramNode2.getCurrentDescTuple());
3211
3212           // TODO: deprecated method
3213           // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
3214           // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
3215           NodeTupleSet tupleSetArg1 = null;
3216           NodeTupleSet tupleSetArg2 = null;
3217
3218           for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
3219             NTuple<Descriptor> arg1Tuple = iter1.next();
3220
3221             for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
3222               NTuple<Descriptor> arg2Tuple = iter2.next();
3223
3224               // check if the callee propagates an ordering constraints through
3225               // parameters
3226
3227               Set<FlowNode> localReachSet =
3228                   calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
3229
3230               if (localReachSet.contains(paramNode2)) {
3231                 // need to propagate an ordering relation s.t. arg1 is higher
3232                 // than arg2
3233
3234                 System.out
3235                     .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
3236                 System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple="
3237                     + arg2Tuple);
3238
3239                 if (!min.getMethod().isStatic()) {
3240                   // check if this is the case that values flow to/from the
3241                   // current object reference 'this'
3242
3243                   NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
3244                   Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
3245
3246                   System.out.println("paramNode1.getCurrentDescTuple()="
3247                       + paramNode1.getCurrentDescTuple());
3248                   // calculate the prefix of the argument
3249
3250                   if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) {
3251                     // in this case, the callee flow causes a caller flow to the
3252                     // object whose method
3253                     // is invoked.
3254
3255                     if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
3256                       // check whether ???
3257
3258                       NTuple<Descriptor> param1Prefix =
3259                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
3260                               paramNode1);
3261
3262                       if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) {
3263                         // in this case, we need to create a new edge
3264                         // 'this.FIELD'->'this'
3265                         // but we couldn't... instead we assign a new composite
3266                         // location started
3267                         // with 'this' reference to the corresponding parameter
3268
3269                         CompositeLocation compLocForParam1 =
3270                             generateCompositeLocation(mdCallee, param1Prefix);
3271
3272                         System.out
3273                             .println("set comp loc=" + compLocForParam1 + " to " + paramNode1);
3274                         paramNode1.setCompositeLocation(compLocForParam1);
3275
3276                         // then, we need to make sure that the corresponding
3277                         // argument in the caller
3278                         // is required to be higher than or equal to the
3279                         // translated parameter
3280                         // location
3281
3282                         NTuple<Descriptor> translatedParamTuple =
3283                             translateCompositeLocationToCaller(min, compLocForParam1);
3284
3285                         // TODO : check if the arg >= the tranlated parameter
3286
3287                         System.out.println("add a flow edge= " + arg1Tuple + "->"
3288                             + translatedParamTuple);
3289                         callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
3290
3291                         continue;
3292
3293                       }
3294
3295                     } else {
3296                       // param1 has already been assigned a composite location
3297
3298                       System.out.println("--param1 has already been assigned a composite location");
3299                       CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation();
3300                       NTuple<Descriptor> translatedParamTuple =
3301                           translateCompositeLocationToCaller(min, compLocForParam1);
3302
3303                       // TODO : check if the arg >= the tranlated parameter
3304
3305                       System.out.println("add a flow edge= " + arg1Tuple + "->"
3306                           + translatedParamTuple);
3307                       callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
3308
3309                       continue;
3310
3311                     }
3312
3313                   } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) {
3314                     // in this case, the callee flow causes a caller flow
3315                     // originated from the object
3316                     // whose
3317                     // method is invoked.
3318
3319                     System.out.println("###FROM CASE");
3320
3321                     if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
3322
3323                       NTuple<Descriptor> param2Prefix =
3324                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple,
3325                               paramNode2);
3326
3327                       if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) {
3328                         // in this case, we need to create a new edge 'this' ->
3329                         // 'this.FIELD' but we couldn't... instead we assign the
3330                         // corresponding
3331                         // parameter a new composite location started with
3332                         // 'this' reference
3333
3334                         CompositeLocation compLocForParam2 =
3335                             generateCompositeLocation(mdCallee, param2Prefix);
3336
3337                         // System.out.println("set comp loc=" + compLocForParam2
3338                         // +
3339                         // " to " + paramNode2);
3340                         paramNode1.setCompositeLocation(compLocForParam2);
3341                         continue;
3342                       }
3343                     }
3344
3345                   }
3346                 }
3347
3348                 // otherwise, flows between method/field locations...
3349                 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
3350                 System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
3351
3352               }
3353
3354             }
3355
3356           }
3357           System.out.println();
3358         }
3359       }
3360     }
3361     System.out.println("##\n");
3362   }
3363
3364   private NTuple<Descriptor> translateCompositeLocationToCaller(MethodInvokeNode min,
3365       CompositeLocation compLocForParam1) {
3366     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
3367
3368     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
3369
3370     for (int i = 0; i < baseTuple.size(); i++) {
3371       tuple.add(baseTuple.get(i));
3372     }
3373
3374     for (int i = baseTuple.size(); i < compLocForParam1.getSize(); i++) {
3375       Location loc = compLocForParam1.get(i);
3376       tuple.add(loc.getLocDescriptor());
3377     }
3378
3379     return tuple;
3380   }
3381
3382   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
3383
3384     System.out.println("generateCompositeLocation=" + prefixLocTuple);
3385
3386     CompositeLocation newCompLoc = new CompositeLocation();
3387     for (int i = 0; i < prefixLocTuple.size(); i++) {
3388       newCompLoc.addLocation(prefixLocTuple.get(i));
3389     }
3390
3391     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
3392
3393     ClassDescriptor enclosingDescriptor;
3394     if (lastDescOfPrefix instanceof FieldDescriptor) {
3395       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3396       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3397     } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
3398       MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
3399       enclosingDescriptor = currentMethodDesc.getClassDesc();
3400     } else {
3401       // var descriptor case
3402       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3403     }
3404     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3405
3406     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3407     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3408
3409     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3410     newLoc.setLocDescriptor(newLocDescriptor);
3411     newCompLoc.addLocation(newLoc);
3412
3413     // System.out.println("--newCompLoc=" + newCompLoc);
3414     return newCompLoc;
3415   }
3416
3417   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
3418       NTuple<Descriptor> paramPrefix) {
3419
3420     System.out.println("generateCompositeLocation=" + paramPrefix);
3421
3422     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
3423
3424     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
3425     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
3426     // + lastDescOfPrefix.getClass());
3427     ClassDescriptor enclosingDescriptor;
3428     if (lastDescOfPrefix instanceof FieldDescriptor) {
3429       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3430       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3431     } else {
3432       // var descriptor case
3433       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3434     }
3435     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3436
3437     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3438     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3439
3440     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3441     newLoc.setLocDescriptor(newLocDescriptor);
3442     newCompLoc.addLocation(newLoc);
3443
3444     // System.out.println("--newCompLoc=" + newCompLoc);
3445     return newCompLoc;
3446   }
3447
3448   private NTuple<Descriptor> calculatePrefixForParam(FlowGraph callerFlowGraph,
3449       FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple<Descriptor> arg1Tuple,
3450       FlowNode paramNode1) {
3451
3452     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
3453     Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
3454     System.out.println("baseRef=" + baseRef);
3455
3456     FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple);
3457     List<NTuple<Descriptor>> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1);
3458     System.out.println("callerPrefixList=" + callerPrefixList);
3459
3460     List<NTuple<Descriptor>> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1);
3461     System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList);
3462
3463     List<NTuple<Descriptor>> calleePrefixList =
3464         translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList);
3465
3466     System.out.println("calleePrefixList=" + calleePrefixList);
3467
3468     Set<FlowNode> reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1);
3469     System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1);
3470
3471     for (int i = 0; i < calleePrefixList.size(); i++) {
3472       NTuple<Descriptor> curPrefix = calleePrefixList.get(i);
3473       Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
3474
3475       for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) {
3476         FlowNode reachNode = (FlowNode) iterator2.next();
3477         if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
3478           reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
3479         }
3480       }
3481
3482       if (!reachableCommonPrefixSet.isEmpty()) {
3483         System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet
3484             + " with curPreFix=" + curPrefix);
3485         return curPrefix;
3486       }
3487
3488     }
3489
3490     return null;
3491   }
3492
3493   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
3494       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
3495
3496     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
3497
3498     for (int i = 0; i < callerPrefixList.size(); i++) {
3499       NTuple<Descriptor> prefix = callerPrefixList.get(i);
3500       if (prefix.startsWith(baseRef)) {
3501         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
3502         calleePrefix.add(mdCallee.getThis());
3503         for (int k = 1; k < prefix.size(); k++) {
3504           calleePrefix.add(prefix.get(k));
3505         }
3506         calleePrefixList.add(calleePrefix);
3507       }
3508     }
3509
3510     return calleePrefixList;
3511
3512   }
3513
3514   private List<NTuple<Descriptor>> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) {
3515
3516     System.out.println("\n##### calculatePrefixList=" + flowNode);
3517
3518     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
3519     inNodeSet.add(flowNode);
3520
3521     System.out.println("inNodeSet=" + inNodeSet);
3522
3523     List<NTuple<Descriptor>> prefixList = new ArrayList<NTuple<Descriptor>>();
3524
3525     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
3526       FlowNode inNode = (FlowNode) iterator.next();
3527
3528       NTuple<Descriptor> inNodeTuple = inNode.getCurrentDescTuple();
3529
3530       // CompositeLocation inNodeInferredLoc =
3531       // generateInferredCompositeLocation(methodInfo, inNodeTuple);
3532       // NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
3533
3534       for (int i = 1; i < inNodeTuple.size(); i++) {
3535         NTuple<Descriptor> prefix = inNodeTuple.subList(0, i);
3536         if (!prefixList.contains(prefix)) {
3537           prefixList.add(prefix);
3538         }
3539       }
3540     }
3541
3542     Collections.sort(prefixList, new Comparator<NTuple<Descriptor>>() {
3543       public int compare(NTuple<Descriptor> arg0, NTuple<Descriptor> arg1) {
3544         int s0 = arg0.size();
3545         int s1 = arg1.size();
3546         if (s0 > s1) {
3547           return -1;
3548         } else if (s0 == s1) {
3549           return 0;
3550         } else {
3551           return 1;
3552         }
3553       }
3554     });
3555
3556     return prefixList;
3557
3558   }
3559
3560   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
3561
3562     CompositeLocation compLoc = new CompositeLocation();
3563
3564     Descriptor enclosingDescriptor = md;
3565
3566     for (int i = 0; i < tuple.size(); i++) {
3567       Descriptor curDescriptor = tuple.get(i);
3568       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
3569       locElement.setLocDescriptor(curDescriptor);
3570       compLoc.addLocation(locElement);
3571
3572       if (curDescriptor instanceof VarDescriptor) {
3573         enclosingDescriptor = md.getClassDesc();
3574       } else if (curDescriptor instanceof FieldDescriptor) {
3575         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
3576       } else if (curDescriptor instanceof NameDescriptor) {
3577         // it is "GLOBAL LOC" case!
3578         enclosingDescriptor = GLOBALDESC;
3579       } else {
3580         enclosingDescriptor = null;
3581       }
3582
3583     }
3584
3585     return compLoc;
3586   }
3587
3588   private LocationDescriptor generateNewLocationDescriptor() {
3589     return new LocationDescriptor("Loc" + (locSeed++));
3590   }
3591
3592   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
3593
3594     // return the index where the prefix shared by tuple1 and tuple2 is ended
3595     // if there is no prefix shared by both of them, return -1
3596
3597     int minSize = tuple1.size();
3598     if (minSize > tuple2.size()) {
3599       minSize = tuple2.size();
3600     }
3601
3602     int idx = -1;
3603     for (int i = 0; i < minSize; i++) {
3604       if (!tuple1.get(i).equals(tuple2.get(i))) {
3605         break;
3606       } else {
3607         idx++;
3608       }
3609     }
3610
3611     return idx;
3612   }
3613
3614   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
3615       NTuple<Location> tuple) {
3616
3617     // first, retrieve inferred location by the local var descriptor
3618     CompositeLocation inferLoc = new CompositeLocation();
3619
3620     CompositeLocation localVarInferLoc =
3621         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
3622
3623     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
3624
3625     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
3626       inferLoc.addLocation(localVarInferLoc.get(i));
3627     }
3628
3629     for (int i = 1; i < tuple.size(); i++) {
3630       Location cur = tuple.get(i);
3631       Descriptor enclosingDesc = cur.getDescriptor();
3632       Descriptor curDesc = cur.getLocDescriptor();
3633
3634       Location inferLocElement;
3635       if (curDesc == null) {
3636         // in this case, we have a newly generated location.
3637         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
3638       } else {
3639         String fieldLocSymbol =
3640             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
3641         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
3642         inferLocElement.setLocDescriptor(curDesc);
3643       }
3644
3645       inferLoc.addLocation(inferLocElement);
3646
3647     }
3648
3649     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
3650     return inferLoc;
3651   }
3652
3653   public LocationInfo getLocationInfo(Descriptor d) {
3654     if (d instanceof MethodDescriptor) {
3655       return getMethodLocationInfo((MethodDescriptor) d);
3656     } else {
3657       return getFieldLocationInfo((ClassDescriptor) d);
3658     }
3659   }
3660
3661   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
3662
3663     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
3664       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
3665     }
3666
3667     return mapMethodDescToMethodLocationInfo.get(md);
3668
3669   }
3670
3671   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
3672
3673     if (!mapClassToLocationInfo.containsKey(cd)) {
3674       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
3675     }
3676
3677     return mapClassToLocationInfo.get(cd);
3678
3679   }
3680
3681   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
3682       NTuple<Location> prefix, NTuple<Location> element) {
3683
3684     if (!map.containsKey(prefix)) {
3685       map.put(prefix, new HashSet<NTuple<Location>>());
3686     }
3687     map.get(prefix).add(element);
3688   }
3689
3690   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
3691     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
3692       Descriptor desc = (Descriptor) iterator.next();
3693
3694       if (desc.equals(LocationInference.GLOBALDESC)) {
3695         return true;
3696       } else if (desc instanceof VarDescriptor) {
3697         if (!((VarDescriptor) desc).getType().isPrimitive()) {
3698           return true;
3699         }
3700       } else if (desc instanceof FieldDescriptor) {
3701         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
3702           return true;
3703         }
3704       }
3705
3706     }
3707     return false;
3708   }
3709
3710   private SSJavaLattice<String> getLattice(Descriptor d) {
3711     if (d instanceof MethodDescriptor) {
3712       return getMethodLattice((MethodDescriptor) d);
3713     } else {
3714       return getFieldLattice((ClassDescriptor) d);
3715     }
3716   }
3717
3718   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
3719     if (!md2lattice.containsKey(md)) {
3720       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3721     }
3722     return md2lattice.get(md);
3723   }
3724
3725   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
3726     md2lattice.put(md, lattice);
3727   }
3728
3729   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
3730       int idx) {
3731
3732     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
3733     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
3734
3735     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
3736         && dstCurTuple.size() > (idx + 1)) {
3737       // value flow between fields: we don't need to add a binary relation
3738       // for this case
3739
3740       Descriptor desc = srcCurTuple.get(idx);
3741       ClassDescriptor classDesc;
3742
3743       if (idx == 0) {
3744         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
3745       } else {
3746         if (desc instanceof FieldDescriptor) {
3747           classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
3748         } else {
3749           // this case is that the local variable has a composite location assignment
3750           // the following element after the composite location to the local variable
3751           // has the enclosing descriptor of the local variable
3752           Descriptor localDesc = srcNode.getDescTuple().get(0);
3753           classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
3754         }
3755       }
3756       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
3757
3758     } else {
3759
3760       Descriptor srcFieldDesc = srcCurTuple.get(idx);
3761       Descriptor dstFieldDesc = dstCurTuple.get(idx);
3762
3763       // add a new edge
3764       getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
3765
3766     }
3767
3768   }
3769
3770   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
3771     if (!cd2lattice.containsKey(cd)) {
3772       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3773     }
3774     return cd2lattice.get(cd);
3775   }
3776
3777   public LinkedList<MethodDescriptor> computeMethodList() {
3778
3779     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
3780
3781     setupToAnalyze();
3782
3783     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
3784     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
3785
3786     while (!toAnalyzeIsEmpty()) {
3787       ClassDescriptor cd = toAnalyzeNext();
3788
3789       setupToAnalazeMethod(cd);
3790       temp_toanalyzeMethodList.removeAll(visited);
3791
3792       while (!toAnalyzeMethodIsEmpty()) {
3793         MethodDescriptor md = toAnalyzeMethodNext();
3794         if ((!visited.contains(md))
3795             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
3796
3797           // creates a mapping from a method descriptor to virtual methods
3798           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3799           if (md.isStatic()) {
3800             setPossibleCallees.add(md);
3801           } else {
3802             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3803           }
3804
3805           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
3806           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
3807
3808           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
3809             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
3810             if ((!ssjava.isTrustMethod(calleemd))
3811                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
3812               if (!visited.contains(calleemd)) {
3813                 temp_toanalyzeMethodList.add(calleemd);
3814               }
3815               reachableCallee.add(calleemd);
3816               needToAnalyzeCalleeSet.add(calleemd);
3817             }
3818           }
3819
3820           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
3821
3822           visited.add(md);
3823
3824           toSort.add(md);
3825         }
3826       }
3827     }
3828
3829     return ssjava.topologicalSort(toSort);
3830
3831   }
3832
3833   public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
3834     // if the callee is transitively invoked from the caller
3835     // return true;
3836
3837     int callerIdx = toanalyze_methodDescList.indexOf(caller);
3838     int calleeIdx = toanalyze_methodDescList.indexOf(callee);
3839
3840     if (callerIdx < calleeIdx) {
3841       return true;
3842     }
3843
3844     return false;
3845
3846   }
3847
3848   public void constructFlowGraph() {
3849
3850     System.out.println("");
3851     toanalyze_methodDescList = computeMethodList();
3852
3853     LinkedList<MethodDescriptor> methodDescList =
3854         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3855
3856     System.out.println("@@@methodDescList=" + methodDescList);
3857     // System.exit(0);
3858
3859     while (!methodDescList.isEmpty()) {
3860       MethodDescriptor md = methodDescList.removeLast();
3861       if (state.SSJAVADEBUG) {
3862         System.out.println();
3863         System.out.println("SSJAVA: Constructing a flow graph: " + md);
3864
3865         // creates a mapping from a parameter descriptor to its index
3866         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
3867         int offset = 0;
3868         if (!md.isStatic()) {
3869           offset = 1;
3870           mapParamDescToIdx.put(md.getThis(), 0);
3871         }
3872
3873         for (int i = 0; i < md.numParameters(); i++) {
3874           Descriptor paramDesc = (Descriptor) md.getParameter(i);
3875           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
3876         }
3877
3878         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
3879         mapMethodDescriptorToFlowGraph.put(md, fg);
3880
3881         analyzeMethodBody(md.getClassDesc(), md);
3882
3883         // System.out.println("##constructSubGlobalFlowGraph");
3884         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
3885         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
3886         //
3887         // // TODO
3888         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
3889         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
3890         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
3891         //
3892         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
3893
3894       }
3895     }
3896     // _debug_printGraph();
3897
3898     methodDescList = (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3899
3900     while (!methodDescList.isEmpty()) {
3901       MethodDescriptor md = methodDescList.removeLast();
3902       if (state.SSJAVADEBUG) {
3903         System.out.println();
3904         System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
3905
3906         GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md));
3907         mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
3908
3909         // TODO
3910         System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
3911         addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
3912         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
3913
3914         // System.out.println("-propagate Flows From Callees With No CompositeLocation");
3915         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
3916
3917       }
3918     }
3919
3920   }
3921
3922   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
3923     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
3924       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
3925     }
3926     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
3927   }
3928
3929   private void constructSubGlobalFlowGraph(MethodDescriptor md) {
3930
3931     FlowGraph flowGraph = getFlowGraph(md);
3932
3933     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(md);
3934
3935     for (Iterator<MethodInvokeNode> iter = setMethodInvokeNode.iterator(); iter.hasNext();) {
3936       MethodInvokeNode min = iter.next();
3937       propagateFlowsFromMethodInvokeNode(md, min);
3938     }
3939
3940   }
3941
3942   private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) {
3943     // the transformation for a call site propagates flows through parameters
3944     // if the method is virtual, it also grab all relations from any possible
3945     // callees
3946
3947     MethodDescriptor mdCallee = min.getMethod();
3948     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3949     if (mdCallee.isStatic()) {
3950       setPossibleCallees.add(mdCallee);
3951     } else {
3952       Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3953       // removes method descriptors that are not invoked by the caller
3954       calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3955       setPossibleCallees.addAll(calleeSet);
3956     }
3957
3958     for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3959       MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3960       contributeCalleeFlows(min, mdCaller, possibleMdCallee);
3961     }
3962
3963   }
3964
3965   private void assignCompositeLocation(MethodDescriptor md) {
3966
3967     FlowGraph flowGraph = getFlowGraph(md);
3968
3969     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
3970
3971     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3972       FlowNode flowNode = (FlowNode) iterator.next();
3973
3974       // assign a composite location only to the local variable
3975       if (flowNode.getCurrentDescTuple().size() == 1) {
3976
3977         List<NTuple<Descriptor>> prefixList = calculatePrefixList(flowGraph, flowNode);
3978         Set<FlowNode> reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
3979
3980         for (int i = 0; i < prefixList.size(); i++) {
3981           NTuple<Descriptor> curPrefix = prefixList.get(i);
3982           Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
3983
3984           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
3985             FlowNode reachNode = (FlowNode) iterator2.next();
3986             if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
3987               reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
3988             }
3989           }
3990
3991           if (!reachableCommonPrefixSet.isEmpty()) {
3992             System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix="
3993                 + curPrefix);
3994             CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix);
3995             flowNode.setCompositeLocation(newCompLoc);
3996             continue next;
3997           }
3998
3999         }
4000       }
4001
4002     }
4003
4004   }
4005
4006   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
4007
4008     // the transformation for a call site propagates flows through parameters
4009     // if the method is virtual, it also grab all relations from any possible
4010     // callees
4011
4012     Set<MethodInvokeNode> setMethodInvokeNode =
4013         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4014
4015     if (setMethodInvokeNode != null) {
4016
4017       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4018         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4019         MethodDescriptor mdCallee = min.getMethod();
4020         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4021         if (mdCallee.isStatic()) {
4022           setPossibleCallees.add(mdCallee);
4023         } else {
4024           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4025           // removes method descriptors that are not invoked by the caller
4026           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4027           setPossibleCallees.addAll(calleeSet);
4028         }
4029
4030         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4031           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4032           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
4033         }
4034
4035       }
4036     }
4037
4038   }
4039
4040   private void propagateFlowsFromCallees(MethodDescriptor mdCaller) {
4041
4042     // the transformation for a call site propagates flows through parameters
4043     // if the method is virtual, it also grab all relations from any possible
4044     // callees
4045
4046     Set<MethodInvokeNode> setMethodInvokeNode =
4047         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4048
4049     if (setMethodInvokeNode != null) {
4050
4051       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4052         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4053         MethodDescriptor mdCallee = min.getMethod();
4054         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4055         if (mdCallee.isStatic()) {
4056           setPossibleCallees.add(mdCallee);
4057         } else {
4058           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4059           // removes method descriptors that are not invoked by the caller
4060           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4061           setPossibleCallees.addAll(calleeSet);
4062         }
4063
4064         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4065           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4066           propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
4067         }
4068
4069       }
4070     }
4071
4072   }
4073
4074   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
4075     BlockNode bn = state.getMethodBody(md);
4076     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
4077     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
4078   }
4079
4080   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
4081       NodeTupleSet implicitFlowTupleSet) {
4082
4083     bn.getVarTable().setParent(nametable);
4084     for (int i = 0; i < bn.size(); i++) {
4085       BlockStatementNode bsn = bn.get(i);
4086       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4087     }
4088
4089   }
4090
4091   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
4092       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
4093
4094     switch (bsn.kind()) {
4095     case Kind.BlockExpressionNode:
4096       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
4097       break;
4098
4099     case Kind.DeclarationNode:
4100       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
4101       break;
4102
4103     case Kind.IfStatementNode:
4104       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
4105       break;
4106
4107     case Kind.LoopNode:
4108       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
4109       break;
4110
4111     case Kind.ReturnNode:
4112       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
4113       break;
4114
4115     case Kind.SubBlockNode:
4116       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
4117       break;
4118
4119     case Kind.ContinueBreakNode:
4120       break;
4121
4122     case Kind.SwitchStatementNode:
4123       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
4124       break;
4125
4126     }
4127
4128   }
4129
4130   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
4131       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4132
4133     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
4134
4135   }
4136
4137   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
4138       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
4139
4140     NodeTupleSet condTupleNode = new NodeTupleSet();
4141     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
4142         implicitFlowTupleSet, false);
4143
4144     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4145
4146     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4147     newImplicitTupleSet.addTupleSet(condTupleNode);
4148
4149     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4150       // need to create an intermediate node for the GLB of conditional
4151       // locations & implicit flows
4152
4153       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4154       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4155         NTuple<Descriptor> tuple = idxIter.next();
4156         addFlowGraphEdge(md, tuple, interTuple);
4157       }
4158       newImplicitTupleSet.clear();
4159       newImplicitTupleSet.addTuple(interTuple);
4160     }
4161
4162     BlockNode sbn = ssn.getSwitchBody();
4163     for (int i = 0; i < sbn.size(); i++) {
4164       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
4165     }
4166
4167   }
4168
4169   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
4170       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4171     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
4172   }
4173
4174   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
4175       NodeTupleSet implicitFlowTupleSet) {
4176
4177     System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
4178     ExpressionNode returnExp = rn.getReturnExpression();
4179
4180     if (returnExp != null) {
4181       NodeTupleSet nodeSet = new NodeTupleSet();
4182       // if a return expression returns a literal value, nodeSet is empty
4183       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
4184       FlowGraph fg = getFlowGraph(md);
4185
4186       // if (implicitFlowTupleSet.size() == 1
4187       // &&
4188       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
4189       // {
4190       //
4191       // // since there is already an intermediate node for the GLB of implicit
4192       // flows
4193       // // we don't need to create another intermediate node.
4194       // // just re-use the intermediate node for implicit flows.
4195       //
4196       // FlowNode meetNode =
4197       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
4198       //
4199       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
4200       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
4201       // iterator.next();
4202       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
4203       // }
4204       //
4205       // }
4206
4207       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
4208
4209       // add tuples from return node
4210       currentFlowTupleSet.addTupleSet(nodeSet);
4211
4212       // add tuples corresponding to the current implicit flows
4213       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
4214
4215       System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
4216
4217       if (needToGenerateInterLoc(currentFlowTupleSet)) {
4218         System.out.println("8");
4219         FlowNode meetNode = fg.createIntermediateNode();
4220         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4221           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4222           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
4223         }
4224         fg.addReturnFlowNode(meetNode.getDescTuple());
4225       } else {
4226         // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
4227         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4228           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4229           fg.addReturnFlowNode(currentFlowTuple);
4230         }
4231       }
4232
4233     }
4234
4235   }
4236
4237   private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
4238     NodeTupleSet tupleSet = new NodeTupleSet();
4239     for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
4240       NTuple<Descriptor> tuple = iter.next();
4241       if (!tuple.get(0).equals(LITERALDESC)) {
4242         tupleSet.addTuple(tuple);
4243       }
4244     }
4245     return tupleSet;
4246   }
4247
4248   private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
4249     int size = 0;
4250     for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
4251       NTuple<Descriptor> descTuple = iter.next();
4252       if (!descTuple.get(0).equals(LITERALDESC)) {
4253         size++;
4254       }
4255     }
4256     if (size > 1) {
4257       return true;
4258     } else {
4259       return false;
4260     }
4261   }
4262
4263   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
4264       NodeTupleSet implicitFlowTupleSet) {
4265
4266     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
4267
4268       NodeTupleSet condTupleNode = new NodeTupleSet();
4269       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
4270           implicitFlowTupleSet, false);
4271
4272       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4273
4274       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4275       newImplicitTupleSet.addTupleSet(condTupleNode);
4276
4277       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4278         // need to create an intermediate node for the GLB of conditional
4279         // locations & implicit flows
4280
4281         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4282         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4283             .hasNext();) {
4284           NTuple<Descriptor> tuple = idxIter.next();
4285           addFlowGraphEdge(md, tuple, interTuple);
4286         }
4287         newImplicitTupleSet.clear();
4288         newImplicitTupleSet.addTuple(interTuple);
4289
4290       }
4291
4292       // ///////////
4293       // System.out.println("condTupleNode="+condTupleNode);
4294       // NTuple<Descriptor> interTuple =
4295       // getFlowGraph(md).createIntermediateNode().getDescTuple();
4296       //
4297       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
4298       // idxIter.hasNext();) {
4299       // NTuple<Descriptor> tuple = idxIter.next();
4300       // addFlowGraphEdge(md, tuple, interTuple);
4301       // }
4302
4303       // for (Iterator<NTuple<Descriptor>> idxIter =
4304       // implicitFlowTupleSet.iterator(); idxIter
4305       // .hasNext();) {
4306       // NTuple<Descriptor> tuple = idxIter.next();
4307       // addFlowGraphEdge(md, tuple, interTuple);
4308       // }
4309
4310       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4311       // newImplicitSet.addTuple(interTuple);
4312       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
4313       // ///////////
4314
4315       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4316
4317       // add edges from condNodeTupleSet to all nodes of conditional nodes
4318       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
4319
4320     } else {
4321       // check 'for loop' case
4322       BlockNode bn = ln.getInitializer();
4323       bn.getVarTable().setParent(nametable);
4324       for (int i = 0; i < bn.size(); i++) {
4325         BlockStatementNode bsn = bn.get(i);
4326         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4327       }
4328
4329       NodeTupleSet condTupleNode = new NodeTupleSet();
4330       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
4331           implicitFlowTupleSet, false);
4332
4333       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4334       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4335       newImplicitTupleSet.addTupleSet(condTupleNode);
4336
4337       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4338         // need to create an intermediate node for the GLB of conditional
4339         // locations & implicit flows
4340
4341         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4342         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4343             .hasNext();) {
4344           NTuple<Descriptor> tuple = idxIter.next();
4345           addFlowGraphEdge(md, tuple, interTuple);
4346         }
4347         newImplicitTupleSet.clear();
4348         newImplicitTupleSet.addTuple(interTuple);
4349
4350       }
4351
4352       // ///////////
4353       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4354       //
4355       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
4356       // NTuple<Descriptor> tuple = idxIter.next();
4357       // addFlowGraphEdge(md, tuple, interTuple);
4358       // }
4359       //
4360       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
4361       // .hasNext();) {
4362       // NTuple<Descriptor> tuple = idxIter.next();
4363       // addFlowGraphEdge(md, tuple, interTuple);
4364       // }
4365       //
4366       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4367       // newImplicitSet.addTuple(interTuple);
4368       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
4369       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
4370       // ///////////
4371
4372       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4373       //
4374       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
4375       // condTupleNode);
4376       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
4377       // condTupleNode);
4378
4379     }
4380
4381   }
4382
4383   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
4384       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
4385
4386     System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
4387
4388     NodeTupleSet condTupleNode = new NodeTupleSet();
4389     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
4390         implicitFlowTupleSet, false);
4391
4392     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4393
4394     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4395     newImplicitTupleSet.addTupleSet(condTupleNode);
4396
4397     // System.out.println("-condTupleNode=" + condTupleNode);
4398     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4399     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
4400
4401     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4402
4403       // need to create an intermediate node for the GLB of conditional locations & implicit flows
4404       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4405       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4406         NTuple<Descriptor> tuple = idxIter.next();
4407         addFlowGraphEdge(md, tuple, interTuple);
4408       }
4409       newImplicitTupleSet.clear();
4410       newImplicitTupleSet.addTuple(interTuple);
4411     }
4412
4413     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
4414
4415     if (isn.getFalseBlock() != null) {
4416       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
4417     }
4418
4419   }
4420
4421   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
4422       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
4423
4424     VarDescriptor vd = dn.getVarDescriptor();
4425     mapDescToDefinitionLine.put(vd, dn.getNumLine());
4426     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
4427     tupleLHS.add(vd);
4428     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
4429     fn.setDeclarationNode();
4430
4431     if (dn.getExpression() != null) {
4432
4433       NodeTupleSet nodeSetRHS = new NodeTupleSet();
4434       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
4435           implicitFlowTupleSet, false);
4436
4437       // creates edges from RHS to LHS
4438       NTuple<Descriptor> interTuple = null;
4439       if (needToGenerateInterLoc(nodeSetRHS)) {
4440
4441         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4442       }
4443
4444       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
4445         NTuple<Descriptor> fromTuple = iter.next();
4446         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
4447       }
4448
4449       // creates edges from implicitFlowTupleSet to LHS
4450       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4451         NTuple<Descriptor> implicitTuple = iter.next();
4452         addFlowGraphEdge(md, implicitTuple, tupleLHS);
4453       }
4454
4455     }
4456
4457   }
4458
4459   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
4460       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
4461     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
4462         false);
4463   }
4464
4465   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4466       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
4467     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
4468   }
4469
4470   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4471       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4472       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
4473
4474     // note that expression node can create more than one flow node
4475     // nodeSet contains of flow nodes
4476     // base is always assigned to null except the case of a name node!
4477
4478     NTuple<Descriptor> flowTuple;
4479
4480     switch (en.kind()) {
4481
4482     case Kind.AssignmentNode:
4483       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
4484           implicitFlowTupleSet);
4485       break;
4486
4487     case Kind.FieldAccessNode:
4488       flowTuple =
4489           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
4490               implicitFlowTupleSet, isLHS);
4491       if (flowTuple != null) {
4492         nodeSet.addTuple(flowTuple);
4493       }
4494       return flowTuple;
4495
4496     case Kind.NameNode:
4497       NodeTupleSet nameNodeSet = new NodeTupleSet();
4498       flowTuple =
4499           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
4500       if (flowTuple != null) {
4501         nodeSet.addTuple(flowTuple);
4502       }
4503       return flowTuple;
4504
4505     case Kind.OpNode:
4506       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
4507       break;
4508
4509     case Kind.CreateObjectNode:
4510       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
4511       break;
4512
4513     case Kind.ArrayAccessNode:
4514       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
4515       break;
4516
4517     case Kind.LiteralNode:
4518       analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
4519       break;
4520
4521     case Kind.MethodInvokeNode:
4522       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
4523           implicitFlowTupleSet);
4524       break;
4525
4526     case Kind.TertiaryNode:
4527       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
4528       break;
4529
4530     case Kind.CastNode:
4531       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
4532       break;
4533     // case Kind.InstanceOfNode:
4534     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
4535     // return null;
4536
4537     // case Kind.ArrayInitializerNode:
4538     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
4539     // td);
4540     // return null;
4541
4542     // case Kind.ClassTypeNode:
4543     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
4544     // return null;
4545
4546     // case Kind.OffsetNode:
4547     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
4548     // return null;
4549
4550     }
4551     return null;
4552
4553   }
4554
4555   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
4556       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
4557
4558     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
4559         implicitFlowTupleSet, false);
4560
4561   }
4562
4563   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
4564       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4565
4566     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
4567     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
4568         implicitFlowTupleSet, false);
4569
4570     // add edges from tertiaryTupleNode to all nodes of conditional nodes
4571     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
4572     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
4573         implicitFlowTupleSet, false);
4574
4575     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
4576         implicitFlowTupleSet, false);
4577
4578     nodeSet.addTupleSet(tertiaryTupleNode);
4579
4580   }
4581
4582   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
4583       MethodInvokeNode min) {
4584     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
4585     if (set == null) {
4586       set = new HashSet<MethodInvokeNode>();
4587       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
4588     }
4589     set.add(min);
4590   }
4591
4592   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
4593
4594     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4595       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4596     }
4597     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
4598   }
4599
4600   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
4601
4602     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4603       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4604     }
4605
4606     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
4607   }
4608
4609   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
4610       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4611
4612     mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
4613
4614     if (nodeSet == null) {
4615       nodeSet = new NodeTupleSet();
4616     }
4617
4618     MethodDescriptor calleeMethodDesc = min.getMethod();
4619
4620     NameDescriptor baseName = min.getBaseName();
4621     boolean isSystemout = false;
4622     if (baseName != null) {
4623       isSystemout = baseName.getSymbol().equals("System.out");
4624     }
4625
4626     if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
4627         && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) {
4628
4629       addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
4630
4631       FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
4632       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
4633
4634       // System.out.println("-calleeReturnSet=" + calleeReturnSet);
4635
4636       if (min.getExpression() != null) {
4637
4638         NodeTupleSet baseNodeSet = new NodeTupleSet();
4639         analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
4640             implicitFlowTupleSet, false);
4641
4642         assert (baseNodeSet.size() == 1);
4643         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
4644         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
4645
4646         if (!min.getMethod().isStatic()) {
4647           addArgIdxMap(min, 0, baseTuple);
4648
4649           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
4650             FlowNode returnNode = (FlowNode) iterator.next();
4651             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
4652             if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
4653               // the location type of the return value is started with 'this'
4654               // reference
4655               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
4656               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
4657               nodeSet.addTuple(inFlowTuple);
4658             } else {
4659               // TODO
4660               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
4661               // System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
4662               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
4663                 FlowNode inFlowNode = (FlowNode) iterator2.next();
4664                 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
4665                   nodeSet.addTupleSet(baseNodeSet);
4666                 }
4667               }
4668             }
4669           }
4670         }
4671
4672       }
4673       // analyze parameter flows
4674
4675       if (min.numArgs() > 0) {
4676
4677         int offset;
4678         if (min.getMethod().isStatic()) {
4679           offset = 0;
4680         } else {
4681           offset = 1;
4682         }
4683
4684         for (int i = 0; i < min.numArgs(); i++) {
4685           ExpressionNode en = min.getArg(i);
4686           int idx = i + offset;
4687           NodeTupleSet argTupleSet = new NodeTupleSet();
4688           analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false);
4689           // if argument is liternal node, argTuple is set to NULL
4690
4691           NTuple<Descriptor> argTuple = new NTuple<Descriptor>();
4692           if (needToGenerateInterLoc(argTupleSet)) {
4693             NTuple<Descriptor> interTuple =
4694                 getFlowGraph(md).createIntermediateNode().getDescTuple();
4695             for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
4696               NTuple<Descriptor> tuple = idxIter.next();
4697               addFlowGraphEdge(md, tuple, interTuple);
4698             }
4699             argTuple = interTuple;
4700           } else if (argTupleSet.size() == 1) {
4701             argTuple = argTupleSet.iterator().next();
4702           } else {
4703             argTuple = new NTuple<Descriptor>();
4704           }
4705
4706           addArgIdxMap(min, idx, argTuple);
4707
4708           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4709
4710           // check whether a param node in the callee graph has incoming flows
4711           // if it has incoming flows, the corresponding arg should be lower than the current PC
4712           // Descriptor prefix = paramNode.getDescTuple().get(0);
4713           // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
4714           // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
4715           // .hasNext();) {
4716           // NTuple<Descriptor> pcTuple = iterator.next();
4717           // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
4718           // addFlowGraphEdge(md, pcTuple, argTuple);
4719           // }
4720           // }
4721
4722           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
4723               || calleeMethodDesc.getModifiers().isNative()) {
4724             addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
4725             nodeSet.addTupleSet(argTupleSet);
4726           }
4727         }
4728
4729       }
4730
4731       // propagateFlowsFromCallee(min, md, min.getMethod());
4732
4733       System.out.println("min nodeSet=" + nodeSet);
4734     }
4735
4736   }
4737
4738   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
4739     // return true if inNode has in-flows to nodeSet
4740
4741     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
4742     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
4743     // System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
4744
4745     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
4746       FlowNode fn = (FlowNode) iterator.next();
4747       if (nodeSet.contains(fn)) {
4748         return true;
4749       }
4750     }
4751     return false;
4752   }
4753
4754   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
4755     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
4756   }
4757
4758   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
4759                                                                                         * NodeTupleSet
4760                                                                                         * tupleSet
4761                                                                                         */) {
4762     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
4763     if (mapIdxToTuple == null) {
4764       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
4765       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
4766     }
4767     mapIdxToTuple.put(new Integer(idx), argTuple);
4768   }
4769
4770   private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
4771       NodeTupleSet nodeSet) {
4772     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
4773     tuple.add(LITERALDESC);
4774     nodeSet.addTuple(tuple);
4775   }
4776
4777   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
4778       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
4779
4780     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
4781     NTuple<Descriptor> base =
4782         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
4783
4784     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
4785     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
4786
4787     if (isLHS) {
4788       // need to create an edge from idx to array
4789       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
4790         NTuple<Descriptor> idxTuple = idxIter.next();
4791         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
4792           NTuple<Descriptor> arrTuple = arrIter.next();
4793           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
4794         }
4795       }
4796
4797       nodeSet.addTupleSet(expNodeTupleSet);
4798     } else {
4799
4800       NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
4801
4802       nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
4803       nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
4804
4805       if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
4806         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4807
4808         for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
4809           NTuple<Descriptor> higherTuple = iter.next();
4810           addFlowGraphEdge(md, higherTuple, interTuple);
4811         }
4812         nodeSetArrayAccessExp.clear();
4813         nodeSetArrayAccessExp.addTuple(interTuple);
4814       }
4815
4816       nodeSet.addTupleSet(nodeSetArrayAccessExp);
4817     }
4818   }
4819
4820   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
4821       CreateObjectNode en) {
4822     // TODO Auto-generated method stub
4823
4824   }
4825
4826   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
4827       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4828
4829     NodeTupleSet leftOpSet = new NodeTupleSet();
4830     NodeTupleSet rightOpSet = new NodeTupleSet();
4831
4832     // left operand
4833     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
4834         false);
4835
4836     if (on.getRight() != null) {
4837       // right operand
4838       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
4839           implicitFlowTupleSet, false);
4840     }
4841
4842     Operation op = on.getOp();
4843
4844     switch (op.getOp()) {
4845
4846     case Operation.UNARYPLUS:
4847     case Operation.UNARYMINUS:
4848     case Operation.LOGIC_NOT:
4849       // single operand
4850       nodeSet.addTupleSet(leftOpSet);
4851       break;
4852
4853     case Operation.LOGIC_OR:
4854     case Operation.LOGIC_AND:
4855     case Operation.COMP:
4856     case Operation.BIT_OR:
4857     case Operation.BIT_XOR:
4858     case Operation.BIT_AND:
4859     case Operation.ISAVAILABLE:
4860     case Operation.EQUAL:
4861     case Operation.NOTEQUAL:
4862     case Operation.LT:
4863     case Operation.GT:
4864     case Operation.LTE:
4865     case Operation.GTE:
4866     case Operation.ADD:
4867     case Operation.SUB:
4868     case Operation.MULT:
4869     case Operation.DIV:
4870     case Operation.MOD:
4871     case Operation.LEFTSHIFT:
4872     case Operation.RIGHTSHIFT:
4873     case Operation.URIGHTSHIFT:
4874
4875       // there are two operands
4876       nodeSet.addTupleSet(leftOpSet);
4877       nodeSet.addTupleSet(rightOpSet);
4878       break;
4879
4880     default:
4881       throw new Error(op.toString());
4882     }
4883
4884   }
4885
4886   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
4887       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
4888
4889     if (base == null) {
4890       base = new NTuple<Descriptor>();
4891     }
4892
4893     NameDescriptor nd = nn.getName();
4894
4895     if (nd.getBase() != null) {
4896       base =
4897           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
4898               implicitFlowTupleSet, false);
4899       if (base == null) {
4900         // base node has the top location
4901         return base;
4902       }
4903     } else {
4904       String varname = nd.toString();
4905       if (varname.equals("this")) {
4906         // 'this' itself!
4907         base.add(md.getThis());
4908         return base;
4909       }
4910
4911       Descriptor d = (Descriptor) nametable.get(varname);
4912
4913       if (d instanceof VarDescriptor) {
4914         VarDescriptor vd = (VarDescriptor) d;
4915         base.add(vd);
4916       } else if (d instanceof FieldDescriptor) {
4917         // the type of field descriptor has a location!
4918         FieldDescriptor fd = (FieldDescriptor) d;
4919         if (fd.isStatic()) {
4920           if (fd.isFinal()) {
4921             // if it is 'static final', no need to have flow node for the TOP
4922             // location
4923             System.out.println("STATIC FINAL");
4924             return null;
4925           } else {
4926             // if 'static', assign the default GLOBAL LOCATION to the first
4927             // element of the tuple
4928             base.add(GLOBALDESC);
4929           }
4930         } else {
4931           // the location of field access starts from this, followed by field
4932           // location
4933           base.add(md.getThis());
4934         }
4935
4936         base.add(fd);
4937       } else if (d == null) {
4938         // access static field
4939         base.add(GLOBALDESC);
4940         base.add(nn.getField());
4941         return base;
4942
4943         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
4944         //
4945         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
4946         // String globalLocId = localLattice.getGlobalLoc();
4947         // if (globalLocId == null) {
4948         // throw new
4949         // Error("Method lattice does not define global variable location at "
4950         // + generateErrorMessage(md.getClassDesc(), nn));
4951         // }
4952         // loc.addLocation(new Location(md, globalLocId));
4953         //
4954         // Location fieldLoc = (Location) fd.getType().getExtension();
4955         // loc.addLocation(fieldLoc);
4956         //
4957         // return loc;
4958
4959       }
4960     }
4961     getFlowGraph(md).createNewFlowNode(base);
4962
4963     return base;
4964
4965   }
4966
4967   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
4968       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4969       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
4970
4971     ExpressionNode left = fan.getExpression();
4972     TypeDescriptor ltd = left.getType();
4973     FieldDescriptor fd = fan.getField();
4974
4975     String varName = null;
4976     if (left.kind() == Kind.NameNode) {
4977       NameDescriptor nd = ((NameNode) left).getName();
4978       varName = nd.toString();
4979     }
4980
4981     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
4982       // using a class name directly or access using this
4983       if (fd.isStatic() && fd.isFinal()) {
4984         return null;
4985       }
4986     }
4987
4988     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
4989
4990     if (left instanceof ArrayAccessNode) {
4991
4992       ArrayAccessNode aan = (ArrayAccessNode) left;
4993       left = aan.getExpression();
4994       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
4995           implicitFlowTupleSet, isLHS);
4996
4997       nodeSet.addTupleSet(idxNodeTupleSet);
4998     }
4999     base =
5000         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
5001
5002     if (base == null) {
5003       // in this case, field is TOP location
5004       return null;
5005     } else {
5006
5007       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
5008
5009       if (!left.getType().isPrimitive()) {
5010
5011         if (!fd.getSymbol().equals("length")) {
5012           // array.length access, just have the location of the array
5013           flowFieldTuple.add(fd);
5014           nodeSet.removeTuple(base);
5015         }
5016
5017       }
5018       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
5019
5020       if (isLHS) {
5021         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5022           NTuple<Descriptor> idxTuple = idxIter.next();
5023           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
5024         }
5025       }
5026       return flowFieldTuple;
5027
5028     }
5029
5030   }
5031
5032   private void debug_printTreeNode(TreeNode tn) {
5033
5034     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
5035
5036   }
5037
5038   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
5039       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5040       NodeTupleSet implicitFlowTupleSet) {
5041
5042     NodeTupleSet nodeSetRHS = new NodeTupleSet();
5043     NodeTupleSet nodeSetLHS = new NodeTupleSet();
5044
5045     boolean postinc = true;
5046     if (an.getOperation().getBaseOp() == null
5047         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
5048             .getBaseOp().getOp() != Operation.POSTDEC)) {
5049       postinc = false;
5050     }
5051     // if LHS is array access node, need to capture value flows between an array
5052     // and its index value
5053     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
5054         true);
5055
5056     if (!postinc) {
5057       // analyze value flows of rhs expression
5058       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
5059           false);
5060
5061       // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
5062       // System.out.println("-nodeSetLHS=" + nodeSetLHS);
5063       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
5064       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5065       // System.out.println("-");
5066
5067       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
5068         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
5069
5070         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
5071           NTuple<Descriptor> fromTuple = iter.next();
5072           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5073             NTuple<Descriptor> toTuple = iter2.next();
5074             addFlowGraphEdge(md, fromTuple, toTuple);
5075           }
5076         }
5077       }
5078
5079       // creates edges from RHS to LHS
5080       NTuple<Descriptor> interTuple = null;
5081       if (needToGenerateInterLoc(nodeSetRHS)) {
5082         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5083       }
5084
5085       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5086         NTuple<Descriptor> fromTuple = iter.next();
5087         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5088           NTuple<Descriptor> toTuple = iter2.next();
5089           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
5090         }
5091       }
5092
5093       // creates edges from implicitFlowTupleSet to LHS
5094       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5095         NTuple<Descriptor> fromTuple = iter.next();
5096         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5097           NTuple<Descriptor> toTuple = iter2.next();
5098           addFlowGraphEdge(md, fromTuple, toTuple);
5099         }
5100       }
5101
5102     } else {
5103       // postinc case
5104
5105       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5106         NTuple<Descriptor> tuple = iter2.next();
5107         addFlowGraphEdge(md, tuple, tuple);
5108       }
5109
5110       // creates edges from implicitFlowTupleSet to LHS
5111       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5112         NTuple<Descriptor> fromTuple = iter.next();
5113         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5114           NTuple<Descriptor> toTuple = iter2.next();
5115           addFlowGraphEdge(md, fromTuple, toTuple);
5116         }
5117       }
5118
5119     }
5120
5121     if (nodeSet != null) {
5122       nodeSet.addTupleSet(nodeSetLHS);
5123     }
5124   }
5125
5126   public FlowGraph getFlowGraph(MethodDescriptor md) {
5127     return mapMethodDescriptorToFlowGraph.get(md);
5128   }
5129
5130   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5131       NTuple<Descriptor> to) {
5132     FlowGraph graph = getFlowGraph(md);
5133     graph.addValueFlowEdge(from, to);
5134     return true;
5135   }
5136
5137   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5138       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
5139
5140     FlowGraph graph = getFlowGraph(md);
5141
5142     if (inter != null) {
5143       graph.addValueFlowEdge(from, inter);
5144       graph.addValueFlowEdge(inter, to);
5145     } else {
5146       graph.addValueFlowEdge(from, to);
5147     }
5148
5149   }
5150
5151   public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
5152       SSJavaLattice<String> locOrder, String nameSuffix) {
5153     writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
5154   }
5155
5156   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
5157       HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
5158
5159     String fileName = "lattice_";
5160     if (md != null) {
5161       fileName +=
5162       /* cd.getSymbol().replaceAll("[\\W_]", "") + "_" + */md.toString().replaceAll("[\\W_]", "");
5163     } else {
5164       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
5165     }
5166
5167     fileName += nameSuffix;
5168
5169     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
5170
5171     Set<String> addedLocSet = new HashSet<String>();
5172
5173     if (pairSet.size() > 0) {
5174       try {
5175         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
5176
5177         bw.write("digraph " + fileName + " {\n");
5178
5179         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
5180           // pair is in the form of <higher, lower>
5181           Pair<String, String> pair = (Pair<String, String>) iterator.next();
5182
5183           String highLocId = pair.getFirst();
5184           String lowLocId = pair.getSecond();
5185
5186           if (!addedLocSet.contains(highLocId)) {
5187             addedLocSet.add(highLocId);
5188             drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
5189           }
5190
5191           if (!addedLocSet.contains(lowLocId)) {
5192             addedLocSet.add(lowLocId);
5193             drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
5194           }
5195
5196           bw.write(highLocId + " -> " + lowLocId + ";\n");
5197         }
5198         bw.write("}\n");
5199         bw.close();
5200
5201       } catch (IOException e) {
5202         e.printStackTrace();
5203       }
5204
5205     }
5206
5207   }
5208
5209   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
5210     String str = "";
5211     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
5212       HNode merged = (HNode) iterator.next();
5213       if (merged.isMergeNode()) {
5214         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
5215       } else {
5216         str += " " + merged.getName();
5217       }
5218     }
5219     return str;
5220   }
5221
5222   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
5223       String locName) throws IOException {
5224
5225     HNode node = graph.getHNode(locName);
5226
5227     if (node == null) {
5228       return;
5229     }
5230
5231     String prettyStr;
5232     if (lattice.isSharedLoc(locName)) {
5233       prettyStr = locName + "*";
5234     } else {
5235       prettyStr = locName;
5236     }
5237
5238     if (node.isMergeNode()) {
5239       Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
5240       prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
5241     }
5242     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
5243   }
5244
5245   public void _debug_writeFlowGraph() {
5246     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
5247
5248     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
5249       MethodDescriptor md = (MethodDescriptor) iterator.next();
5250       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
5251       try {
5252         fg.writeGraph();
5253       } catch (IOException e) {
5254         e.printStackTrace();
5255       }
5256     }
5257
5258   }
5259
5260 }
5261
5262 class CyclicFlowException extends Exception {
5263
5264 }
5265
5266 class InterDescriptor extends Descriptor {
5267
5268   public InterDescriptor(String name) {
5269     super(name);
5270   }
5271
5272 }