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 TOPLOC = "TOPLOC";
 124
 125   public static final String INTERLOC = "INTERLOC";
 126
 127   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
 128
 129   public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
 130
 131   public static String newline = System.getProperty("line.separator");
 132
 133   LocationInfo curMethodInfo;
 134
 135   boolean debug = true;
 136
 137   private static int locSeed = 0;
 138
 139   public LocationInference(SSJavaAnalysis ssjava, State state) {
 140     this.ssjava = ssjava;
 141     this.state = state;
 142     this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
 143     this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 144     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
 145     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
 146     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
 147     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 148     this.mapMethodDescriptorToMethodInvokeNodeSet =
 149         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 150     this.mapMethodInvokeNodeToArgIdxMap =
 151         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
 152     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
 153     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 154     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 155
 156     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
 157     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
 158     this.mapMethodDescToParamNodeFlowsToReturnValue =
 159         new HashMap<MethodDescriptor, Set<FlowNode>>();
 160
 161     this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 162     this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
 163
 164     this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 165     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 166     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 167
 168     this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
 169
 170     this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
 171
 172     this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
 173
 174     this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
 175         new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
 176
 177   }
 178
 179   public void setupToAnalyze() {
 180     SymbolTable classtable = state.getClassSymbolTable();
 181     temp_toanalyzeList.clear();
 182     temp_toanalyzeList.addAll(classtable.getValueSet());
 183     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 184     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 185     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 186     // }
 187     // });
 188   }
 189
 190   public void setupToAnalazeMethod(ClassDescriptor cd) {
 191
 192     SymbolTable methodtable = cd.getMethodTable();
 193     temp_toanalyzeMethodList.clear();
 194     temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
 195     Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 196       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 197         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 198       }
 199     });
 200   }
 201
 202   public boolean toAnalyzeMethodIsEmpty() {
 203     return temp_toanalyzeMethodList.isEmpty();
 204   }
 205
 206   public boolean toAnalyzeIsEmpty() {
 207     return temp_toanalyzeList.isEmpty();
 208   }
 209
 210   public ClassDescriptor toAnalyzeNext() {
 211     return temp_toanalyzeList.remove(0);
 212   }
 213
 214   public MethodDescriptor toAnalyzeMethodNext() {
 215     return temp_toanalyzeMethodList.remove(0);
 216   }
 217
 218   public void inference() {
 219
 220     // 1) construct value flow graph
 221     constructFlowGraph();
 222
 223     assignCompositeLocation();
 224
 225     // constructGlobalFlowGraph();
 226
 227     System.exit(0);
 228
 229     constructHierarchyGraph();
 230
 231     debug_writeHierarchyDotFiles();
 232
 233     simplifyHierarchyGraph();
 234
 235     debug_writeSimpleHierarchyDotFiles();
 236
 237     constructSkeletonHierarchyGraph();
 238
 239     debug_writeSkeletonHierarchyDotFiles();
 240
 241     insertCombinationNodes();
 242
 243     debug_writeSkeletonCombinationHierarchyDotFiles();
 244
 245     buildLattice();
 246
 247     debug_writeLattices();
 248
 249     generateMethodSummary();
 250
 251     System.exit(0);
 252
 253     // 2) construct lattices
 254     inferLattices();
 255
 256     // simplifyLattices();
 257
 258     // 3) check properties
 259     checkLattices();
 260
 261     // calculate RETURNLOC,PCLOC
 262     calculateExtraLocations();
 263
 264     debug_writeLatticeDotFile();
 265
 266     // 4) generate annotated source codes
 267     generateAnnoatedCode();
 268
 269   }
 270
 271   public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
 272       MethodInvokeNode min) {
 273
 274     if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
 275       mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
 276           new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
 277     }
 278
 279     return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
 280   }
 281
 282   public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
 283       NTuple<Descriptor> calleeParam) {
 284     // System.out.println("min=" + min + "  arg=" + callerArg + "   param=" + calleeParam);
 285     getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
 286   }
 287
 288   private void assignCompositeLocation() {
 289     calculateGlobalValueFlowCompositeLocation();
 290     translateCompositeLocationAssignmentToFlowGraph();
 291     _debug_printGraph();
 292   }
 293
 294   private void translateCompositeLocationAssignmentToFlowGraph() {
 295
 296     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
 297     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
 298
 299   }
 300
 301   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
 302
 303     System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + mdCaller);
 304
 305     // First, assign a composite location to a node in the flow graph
 306     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
 307
 308     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
 309     Map<Location, CompositeLocation> callerMapLocToCompLoc =
 310         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
 311     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
 312     for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
 313       Location methodLoc = (Location) iterator.next();
 314       if (methodLoc.getDescriptor().equals(mdCaller)) {
 315         CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
 316         assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
 317       }
 318     }
 319
 320     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
 321
 322     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
 323     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
 324       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 325       // need to translate a composite location that is started with the base tuple of 'min'.
 326       translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
 327       calleeSet.add(min.getMethod());
 328     }
 329
 330     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
 331       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 332       translateCompositeLocationAssignmentToFlowGraph(callee);
 333     }
 334
 335   }
 336
 337   public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
 338       CompositeLocation inferCompLoc) {
 339     Descriptor localDesc = loc.getLocDescriptor();
 340
 341     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 342     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 343       FlowNode node = (FlowNode) iterator.next();
 344       if (node.getDescTuple().startsWith(localDesc)) {
 345         // need to assign the inferred composite location to this node
 346         CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
 347         node.setCompositeLocation(newCompLoc);
 348         System.out.println("SET Node=" + node + "  inferCompLoc=" + newCompLoc);
 349       }
 350     }
 351   }
 352
 353   private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
 354       CompositeLocation inferCompLoc) {
 355
 356     System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
 357         + inferCompLoc);
 358
 359     CompositeLocation newCompLoc = new CompositeLocation();
 360     for (int i = 0; i < inferCompLoc.getSize(); i++) {
 361       newCompLoc.addLocation(inferCompLoc.get(i));
 362     }
 363
 364     Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
 365     Descriptor enclosingDescriptor;
 366     if (lastDescOfPrefix instanceof InterDescriptor) {
 367       enclosingDescriptor = null;
 368     } else {
 369       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
 370     }
 371
 372     for (int i = 1; i < nodeDescTuple.size(); i++) {
 373       Descriptor desc = nodeDescTuple.get(i);
 374       Location locElement = new Location(enclosingDescriptor, desc);
 375       newCompLoc.addLocation(locElement);
 376
 377       enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
 378     }
 379
 380     return newCompLoc;
 381   }
 382
 383   private void translateMapLocationToInferCompositeLocationToCalleeGraph(
 384       GlobalFlowGraph callerGraph, MethodInvokeNode min) {
 385
 386     MethodDescriptor mdCallee = min.getMethod();
 387     MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
 388     Map<Location, CompositeLocation> callerMapLocToCompLoc =
 389         callerGraph.getMapLocationToInferCompositeLocation();
 390
 391     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
 392     GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
 393
 394     NTuple<Location> baseLocTuple =
 395         translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
 396
 397     System.out.println("-translate caller infer composite loc to callee=" + mdCallee);
 398     Set<Location> keySet = callerMapLocToCompLoc.keySet();
 399     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 400       Location key = (Location) iterator.next();
 401       CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
 402
 403       if (!key.getDescriptor().equals(mdCaller)
 404           && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
 405         // need to translate to the callee side
 406         // System.out.println("need to translate callerCompLoc=" + callerCompLoc +
 407         // " with baseTuple="
 408         // + baseLocTuple);
 409         // TODO
 410         CompositeLocation newCalleeCompLoc =
 411             translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
 412         calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
 413         System.out.println("---callee loc=" + key + "  newCalleeCompLoc=" + newCalleeCompLoc);
 414       }
 415     }
 416
 417     // If the location of an argument has a composite location
 418     // need to assign a proper composite location to the corresponding callee parameter
 419     System.out.println("-translate arg composite location to callee param:");
 420     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
 421     Set<Integer> idxSet = mapIdxToArgTuple.keySet();
 422     for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
 423       Integer idx = (Integer) iterator.next();
 424
 425       if (idx == 0 && !min.getMethod().isStatic()) {
 426         continue;
 427       }
 428
 429       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
 430
 431       // check if an arg tuple has been already assigned to a composite location
 432       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
 433       Location argLocalLoc = argLocTuple.get(0);
 434
 435       // if (!isPrimitiveType(argTuple)) {
 436       if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
 437
 438         CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
 439         for (int i = 1; i < argLocTuple.size(); i++) {
 440           callerCompLoc.addLocation(argLocTuple.get(i));
 441         }
 442
 443         if (callerCompLoc.getTuple().startsWith(baseLocTuple)) {
 444
 445           FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
 446           NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
 447           NTuple<Location> calleeParamLocTuple =
 448               translateToLocTuple(mdCallee, calleeParamDescTuple);
 449
 450           CompositeLocation newCalleeCompLoc =
 451               translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
 452
 453           calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
 454               newCalleeCompLoc);
 455
 456           System.out.println("###need to assign composite location to=" + calleeParamDescTuple
 457               + " with baseTuple=" + baseLocTuple);
 458           System.out.println("---newCalleeCompLoc=" + newCalleeCompLoc);
 459         }
 460
 461       }
 462
 463     }
 464
 465   }
 466
 467   private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
 468
 469     Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
 470
 471     if (lastDesc instanceof FieldDescriptor) {
 472       return ((FieldDescriptor) lastDesc).getType().isPrimitive();
 473     } else if (lastDesc instanceof VarDescriptor) {
 474       return ((VarDescriptor) lastDesc).getType().isPrimitive();
 475     }
 476
 477     return true;
 478   }
 479
 480   private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
 481       NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
 482
 483     CompositeLocation newCalleeCompLoc = new CompositeLocation();
 484
 485     // replace the last element of the caller compLoc with the 'this' location of the callee
 486     for (int i = 0; i < baseLocTuple.size() - 1; i++) {
 487       newCalleeCompLoc.addLocation(baseLocTuple.get(i));
 488     }
 489
 490     Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
 491     newCalleeCompLoc.addLocation(calleeThisLoc);
 492
 493     for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
 494       newCalleeCompLoc.addLocation(callerCompLoc.get(i));
 495     }
 496
 497     return newCalleeCompLoc;
 498
 499   }
 500
 501   private void constructGlobalFlowGraph() {
 502
 503     System.out.println("");
 504     LinkedList<MethodDescriptor> methodDescList =
 505         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 506
 507     System.out.println("@@@methodDescList=" + methodDescList);
 508     // System.exit(0);
 509
 510     while (!methodDescList.isEmpty()) {
 511       MethodDescriptor md = methodDescList.removeLast();
 512       if (state.SSJAVADEBUG) {
 513         System.out.println();
 514         System.out.println("SSJAVA: Constructing a global flow graph: " + md);
 515
 516         FlowGraph flowGraph = getFlowGraph(md);
 517         FlowGraph subGlobalFlowGraph = flowGraph.clone();
 518
 519         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
 520
 521         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
 522
 523         // try {
 524         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
 525         // } catch (IOException e) {
 526         // e.printStackTrace();
 527         // }
 528         // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
 529         // mapMethodDescriptorToFlowGraph.put(md, fg);
 530         // analyzeMethodBody(md.getClassDesc(), md);
 531       }
 532
 533     }
 534
 535     // DEBUG: write a global flow graph
 536     MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
 537     // FlowGraph globalFlowGraph = getSubGlobalFlowGraph(mdContainingSSJavaLoop);
 538     // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet());
 539     // assignCompositeLocation(globalFlowGraph);
 540     // try {
 541     // globalFlowGraph.writeGraph("_GLOBAL");
 542     // } catch (IOException e) {
 543     // e.printStackTrace();
 544     // }
 545     // _debug_printGraph();
 546
 547   }
 548
 549   private void calculateGlobalValueFlowCompositeLocation() {
 550
 551     System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
 552     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
 553     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
 554
 555     Set<NTuple<Location>> prefixSet = new HashSet<NTuple<Location>>();
 556
 557     Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
 558
 559     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 560       GlobalFlowNode node = (GlobalFlowNode) iterator.next();
 561       Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
 562       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
 563       Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
 564
 565       // System.out.println("node=" + node + "    inNodeSet=" + incomingNodeSet
 566       // + "   reachableNodeSet=" + reachNodeSet);
 567
 568       for (int i = 0; i < prefixList.size(); i++) {
 569         NTuple<Location> curPrefix = prefixList.get(i);
 570         Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
 571
 572         for (Iterator iterator2 = reachNodeSet.iterator(); iterator2.hasNext();) {
 573           GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
 574           if (reachNode.getLocTuple().startsWith(curPrefix)) {
 575             reachableCommonPrefixSet.add(reachNode.getLocTuple());
 576           }
 577         }
 578
 579         if (!reachableCommonPrefixSet.isEmpty()) {
 580           CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
 581           System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
 582           System.out.println("- newCompLoc=" + newCompLoc);
 583
 584           Location targetLocalLoc = node.getLocTuple().get(0);
 585           globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
 586
 587           continue next;
 588         }
 589
 590       }
 591
 592     }
 593     // Set<GlobalFlowNode> inNodeSet = graph.getIncomingNodeSetWithPrefix(prefix);
 594     // System.out.println("inNodeSet=" + inNodeSet + "  from=" + node);
 595   }
 596
 597   private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
 598     CompositeLocation newCompLoc = compLocPrefix.clone();
 599     NTuple<Location> locTuple = node.getLocTuple();
 600     for (int i = 1; i < locTuple.size(); i++) {
 601       newCompLoc.addLocation(locTuple.get(i));
 602     }
 603     node.setInferCompositeLocation(newCompLoc);
 604   }
 605
 606   private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
 607
 608     System.out.println("\n##### calculatePrefixList=" + node);
 609
 610     Set<GlobalFlowNode> incomingNodeSet = graph.getIncomingNodeSet(node);
 611
 612     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
 613
 614     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 615       GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
 616       NTuple<Location> inNodeTuple = inNode.getLocTuple();
 617
 618       for (int i = 1; i < inNodeTuple.size(); i++) {
 619         NTuple<Location> prefix = inNodeTuple.subList(0, i);
 620         if (!prefixList.contains(prefix)) {
 621           prefixList.add(prefix);
 622         }
 623       }
 624     }
 625
 626     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
 627       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
 628         int s0 = arg0.size();
 629         int s1 = arg1.size();
 630         if (s0 > s1) {
 631           return -1;
 632         } else if (s0 == s1) {
 633           return 0;
 634         } else {
 635           return 1;
 636         }
 637       }
 638     });
 639     return prefixList;
 640   }
 641
 642   private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
 643
 644     MethodDescriptor md = flowGraph.getMethodDescriptor();
 645
 646     GlobalFlowGraph globalGraph = new GlobalFlowGraph(md);
 647
 648     // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 649     Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
 650
 651     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 652
 653       FlowEdge edge = (FlowEdge) iterator.next();
 654       NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
 655       NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
 656
 657       // here only keep the first element(method location) of the descriptor tuple
 658       NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
 659       // Location srcMethodLoc = srcLocTuple.get(0);
 660       // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor();
 661       // // if (flowGraph.isParamDesc(srcVarDesc) && (!srcVarDesc.equals(md.getThis()))) {
 662       // if (!srcVarDesc.equals(md.getThis())) {
 663       // srcLocTuple = new NTuple<Location>();
 664       // Location loc = new Location(md, srcVarDesc);
 665       // srcLocTuple.add(loc);
 666       // }
 667       //
 668       NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
 669       // Location dstMethodLoc = dstLocTuple.get(0);
 670       // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor();
 671       // if (!dstVarDesc.equals(md.getThis())) {
 672       // dstLocTuple = new NTuple<Location>();
 673       // Location loc = new Location(md, dstVarDesc);
 674       // dstLocTuple.add(loc);
 675       // }
 676
 677       globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
 678
 679     }
 680
 681     return globalGraph;
 682   }
 683
 684   private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
 685
 686     NTuple<Location> locTuple = new NTuple<Location>();
 687
 688     Descriptor enclosingDesc = md;
 689     System.out.println("md=" + md + "  descTuple=" + descTuple);
 690     for (int i = 0; i < descTuple.size(); i++) {
 691       Descriptor desc = descTuple.get(i);
 692
 693       Location loc = new Location(enclosingDesc, desc);
 694       locTuple.add(loc);
 695
 696       if (desc instanceof VarDescriptor) {
 697         enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
 698       } else if (desc instanceof FieldDescriptor) {
 699         enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
 700       } else {
 701         // TODO: inter descriptor case
 702         enclosingDesc = desc;
 703       }
 704
 705     }
 706
 707     return locTuple;
 708
 709   }
 710
 711   private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller,
 712       GlobalFlowGraph subGlobalFlowGraph) {
 713
 714     // the transformation for a call site propagates flows through parameters
 715     // if the method is virtual, it also grab all relations from any possible
 716     // callees
 717
 718     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
 719
 720     for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
 721       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 722       MethodDescriptor mdCallee = min.getMethod();
 723       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 724       if (mdCallee.isStatic()) {
 725         setPossibleCallees.add(mdCallee);
 726       } else {
 727         Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
 728         // removes method descriptors that are not invoked by the caller
 729         calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
 730         setPossibleCallees.addAll(calleeSet);
 731       }
 732
 733       for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
 734         MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
 735         propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
 736       }
 737
 738     }
 739
 740   }
 741
 742   private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
 743       MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
 744
 745     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 746     Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
 747
 748     Set<Integer> keySet = mapIdxToArg.keySet();
 749     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 750       Integer idx = (Integer) iterator.next();
 751       NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
 752       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
 753
 754       NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
 755       NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
 756       addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
 757     }
 758
 759     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
 760     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
 761     Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
 762     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
 763       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
 764       addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
 765     }
 766
 767     // int numParam = calleeFlowGraph.getNumParameters();
 768     // for (int idx = 0; idx < numParam; idx++) {
 769     //
 770     // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
 771     //
 772     // NTuple<Location> paramLocTuple =
 773     // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple());
 774     //
 775     // GlobalFlowNode globalParamNode = calleeSubGlobalGraph.getFlowNode(paramLocTuple);
 776     //
 777     // NTuple<Descriptor> argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
 778     //
 779     // NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
 780     //
 781     // System.out.println("argTupleSet=" + argLocTuple + "   param=" + paramLocTuple);
 782     // // here, it adds all value flows reachable from the paramNode in the callee's flow graph
 783     //
 784     // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, possibleMdCallee,
 785     // globalParamNode);
 786     // }
 787     //
 788     // // TODO
 789     // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
 790     // // FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
 791     // //
 792     // // int numParam = calleeSubGlobalGraph.getNumParameters();
 793     // // for (int idx = 0; idx < numParam; idx++) {
 794     // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx);
 795     // // NTuple<Descriptor> argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
 796     // // System.out.println("argTupleSet=" + argTuple + "   param=" + paramNode);
 797     // // // here, it adds all value flows reachable from the paramNode in the callee's flow graph
 798     // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph,
 799     // // argTuple, baseTuple);
 800     // // }
 801
 802   }
 803
 804   private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
 805       MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
 806
 807     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
 808     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
 809
 810     NTuple<Location> srcNodeLocTuple =
 811         translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
 812
 813     Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
 814
 815     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 816       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 817       NTuple<Location> dstNodeLocTuple =
 818           translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
 819       callerSubGlobalGraph.addValueFlowEdge(srcNodeLocTuple, dstNodeLocTuple);
 820     }
 821
 822   }
 823
 824   private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
 825       MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
 826
 827     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
 828
 829     NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
 830
 831     if (calleeFlowGraph.isParameter(nodeDescTuple)) {
 832       int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
 833       NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
 834       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
 835
 836       NTuple<Location> callerLocTuple = new NTuple<Location>();
 837
 838       callerLocTuple.addAll(argLocTuple);
 839       for (int i = 1; i < nodeLocTuple.size(); i++) {
 840         callerLocTuple.add(nodeLocTuple.get(i));
 841       }
 842       return callerLocTuple;
 843     } else {
 844       return nodeLocTuple;
 845     }
 846
 847   }
 848
 849   private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
 850
 851     NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
 852     for (int i = 0; i < locTuple.size(); i++) {
 853       descTuple.add(locTuple.get(i).getLocDescriptor());
 854     }
 855     return descTuple;
 856
 857   }
 858
 859   private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
 860       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
 861       GlobalFlowNode globalParamNode) {
 862
 863     Set<GlobalFlowNode> visited = new HashSet<GlobalFlowNode>();
 864     visited.add(globalParamNode);
 865     recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee,
 866         globalParamNode);
 867
 868   }
 869
 870   private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
 871       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
 872       GlobalFlowNode calleeCurNode) {
 873
 874     // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
 875     // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
 876     //
 877     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
 878     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
 879     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
 880     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
 881     // }
 882     //
 883     // Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeCurNode);
 884     // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 885     // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 886     //
 887     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
 888     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
 889     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
 890     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
 891     // }
 892     //
 893     // outNode.getDescTuple();
 894     //
 895     // if (calleeFlowGraph.is)
 896     //
 897     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
 898     // // destination node is started with 'parameter'
 899     // // need to translate it in terms of the caller's a node
 900     // srcDescTuple =
 901     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple);
 902     // }
 903     //
 904     // }
 905     //
 906     // Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
 907     // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 908     // FlowEdge flowEdge = (FlowEdge) iterator.next();
 909     //
 910     // NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
 911     // NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
 912     //
 913     // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
 914     //
 915     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
 916     // // destination node is started with 'parameter'
 917     // // need to translate it in terms of the caller's a node
 918     // srcDescTuple =
 919     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple);
 920     // }
 921     //
 922     // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
 923     // // destination node is started with 'parameter'
 924     // // need to translate it in terms of the caller's a node
 925     // dstDescTuple =
 926     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple);
 927     // }
 928     //
 929     // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
 930     //
 931     // if (!visited.contains(dstNode)) {
 932     // visited.add(dstNode);
 933     // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph,
 934     // dstDescTuple, visited, baseTuple);
 935     // }
 936     //
 937     // }
 938
 939   }
 940
 941   private NTuple<Location> translateToCaller(NTuple<Location> argLocTuple,
 942       NTuple<Location> curNodeLocTuple) {
 943
 944     NTuple<Location> callerLocTuple = new NTuple<Location>();
 945
 946     callerLocTuple.addAll(argLocTuple);
 947     for (int i = 1; i < curNodeLocTuple.size(); i++) {
 948       callerLocTuple.add(curNodeLocTuple.get(i));
 949     }
 950
 951     return callerLocTuple;
 952   }
 953
 954   private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min,
 955       FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph,
 956       NTuple<Descriptor> callerSrcTuple, Set<FlowNode> visited, NTuple<Descriptor> baseTuple) {
 957
 958     MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor();
 959
 960     // Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode);
 961     Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
 962     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 963       FlowEdge flowEdge = (FlowEdge) iterator.next();
 964
 965       NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
 966       NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
 967
 968       FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
 969
 970       if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
 971         // destination node is started with 'parameter'
 972         // need to translate it in terms of the caller's a node
 973         srcDescTuple =
 974             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple);
 975       }
 976
 977       if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
 978         // destination node is started with 'parameter'
 979         // need to translate it in terms of the caller's a node
 980         dstDescTuple =
 981             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple);
 982       }
 983
 984       callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
 985
 986       if (!visited.contains(dstNode)) {
 987         visited.add(dstNode);
 988         recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph,
 989             dstDescTuple, visited, baseTuple);
 990       }
 991
 992     }
 993
 994   }
 995
 996   private NTuple<Descriptor> translateToCaller(MethodInvokeNode min, int paramIdx,
 997       NTuple<Descriptor> srcDescTuple) {
 998
 999     NTuple<Descriptor> callerTuple = new NTuple<Descriptor>();
1000
1001     NTuple<Descriptor> argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
1002
1003     for (int i = 0; i < argTuple.size(); i++) {
1004       callerTuple.add(argTuple.get(i));
1005     }
1006
1007     for (int i = 1; i < srcDescTuple.size(); i++) {
1008       callerTuple.add(srcDescTuple.get(i));
1009     }
1010
1011     return callerTuple;
1012   }
1013
1014   private NTuple<Descriptor> traslateToCalleeParamTupleToCallerArgTuple(
1015       NTuple<Descriptor> calleeInitTuple, NTuple<Descriptor> callerSrcTuple) {
1016
1017     NTuple<Descriptor> callerInitTuple = new NTuple<Descriptor>();
1018
1019     for (int i = 0; i < callerSrcTuple.size(); i++) {
1020       callerInitTuple.add(callerSrcTuple.get(i));
1021     }
1022
1023     for (int i = 1; i < calleeInitTuple.size(); i++) {
1024       callerInitTuple.add(calleeInitTuple.get(i));
1025     }
1026
1027     return callerInitTuple;
1028   }
1029
1030   public LocationSummary getLocationSummary(Descriptor d) {
1031     if (!mapDescToLocationSummary.containsKey(d)) {
1032       if (d instanceof MethodDescriptor) {
1033         mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
1034       } else if (d instanceof ClassDescriptor) {
1035         mapDescToLocationSummary.put(d, new FieldSummary());
1036       }
1037     }
1038     return mapDescToLocationSummary.get(d);
1039   }
1040
1041   private void generateMethodSummary() {
1042
1043     Set<MethodDescriptor> keySet = md2lattice.keySet();
1044     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1045       MethodDescriptor md = (MethodDescriptor) iterator.next();
1046
1047       System.out.println("\nSSJAVA: generate method summary: " + md);
1048
1049       FlowGraph flowGraph = getFlowGraph(md);
1050       MethodSummary methodSummary = getMethodSummary(md);
1051
1052       // construct a parameter mapping that maps a parameter descriptor to an inferred composite
1053       // location
1054
1055       for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
1056         FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
1057         NTuple<Descriptor> descTuple = flowNode.getDescTuple();
1058
1059         CompositeLocation assignedCompLoc = flowNode.getCompositeLocation();
1060         CompositeLocation inferredCompLoc;
1061         if (assignedCompLoc != null) {
1062           inferredCompLoc = translateCompositeLocation(assignedCompLoc);
1063         } else {
1064           Descriptor locDesc = descTuple.get(0);
1065           Location loc = new Location(md, locDesc.getSymbol());
1066           loc.setLocDescriptor(locDesc);
1067           inferredCompLoc = new CompositeLocation(loc);
1068         }
1069         System.out.println("-paramIdx=" + paramIdx + "   infer=" + inferredCompLoc);
1070         methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
1071       }
1072
1073     }
1074
1075   }
1076
1077   private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) {
1078     CompositeLocation newCompLoc = new CompositeLocation();
1079
1080     // System.out.println("compLoc=" + compLoc);
1081     for (int i = 0; i < compLoc.getSize(); i++) {
1082       Location loc = compLoc.get(i);
1083       Descriptor enclosingDescriptor = loc.getDescriptor();
1084       Descriptor locDescriptor = loc.getLocDescriptor();
1085
1086       HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor);
1087       // System.out.println("-hnode=" + hnode + "    from=" + locDescriptor +
1088       // " enclosingDescriptor="
1089       // + enclosingDescriptor);
1090       // System.out.println("-getLocationSummary(enclosingDescriptor)="
1091       // + getLocationSummary(enclosingDescriptor));
1092       String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName());
1093       // System.out.println("-locName=" + locName);
1094       Location newLoc = new Location(enclosingDescriptor, locName);
1095       newLoc.setLocDescriptor(locDescriptor);
1096       newCompLoc.addLocation(newLoc);
1097     }
1098
1099     return newCompLoc;
1100   }
1101
1102   private void debug_writeLattices() {
1103
1104     Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
1105     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1106       Descriptor key = (Descriptor) iterator.next();
1107       SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
1108       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
1109       HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
1110       if (key instanceof ClassDescriptor) {
1111         writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
1112             "_SIMPLE");
1113       } else if (key instanceof MethodDescriptor) {
1114         MethodDescriptor md = (MethodDescriptor) key;
1115         writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
1116             "_SIMPLE");
1117       }
1118
1119       LocationSummary ls = getLocationSummary(key);
1120       System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
1121     }
1122
1123     Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
1124     for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
1125       ClassDescriptor cd = (ClassDescriptor) iterator.next();
1126       writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
1127           cd2lattice.get(cd), "");
1128     }
1129
1130     Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
1131     for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
1132       MethodDescriptor md = (MethodDescriptor) iterator.next();
1133       writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
1134           md2lattice.get(md), "");
1135     }
1136
1137   }
1138
1139   private void buildLattice() {
1140
1141     BuildLattice buildLattice = new BuildLattice(this);
1142
1143     Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
1144     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1145       Descriptor desc = (Descriptor) iterator.next();
1146
1147       SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
1148
1149       addMapDescToSimpleLattice(desc, simpleLattice);
1150
1151       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1152       System.out.println("## insertIntermediateNodesToStraightLine:"
1153           + simpleHierarchyGraph.getName());
1154       SSJavaLattice<String> lattice =
1155           buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
1156       lattice.removeRedundantEdges();
1157
1158       if (desc instanceof ClassDescriptor) {
1159         // field lattice
1160         cd2lattice.put((ClassDescriptor) desc, lattice);
1161         // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
1162       } else if (desc instanceof MethodDescriptor) {
1163         // method lattice
1164         md2lattice.put((MethodDescriptor) desc, lattice);
1165         MethodDescriptor md = (MethodDescriptor) desc;
1166         ClassDescriptor cd = md.getClassDesc();
1167         // ssjava.writeLatticeDotFile(cd, md, lattice);
1168       }
1169
1170       // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1171       // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1172       // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
1173       // skeletonGraphWithCombinationNode.setName(desc + "_SC");
1174       //
1175       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1176       // System.out.println("Identifying Combination Nodes:");
1177       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1178       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1179       // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
1180     }
1181
1182   }
1183
1184   public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
1185     mapDescriptorToSimpleLattice.put(desc, lattice);
1186   }
1187
1188   public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
1189     return mapDescriptorToSimpleLattice.get(desc);
1190   }
1191
1192   private void simplifyHierarchyGraph() {
1193     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1194     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1195       Descriptor desc = (Descriptor) iterator.next();
1196       HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
1197       simpleHierarchyGraph.setName(desc + "_SIMPLE");
1198       simpleHierarchyGraph.removeRedundantEdges();
1199       // simpleHierarchyGraph.simplifyHierarchyGraph();
1200       mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
1201     }
1202   }
1203
1204   private void insertCombinationNodes() {
1205     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
1206     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1207       Descriptor desc = (Descriptor) iterator.next();
1208       System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1209       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1210       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
1211       skeletonGraphWithCombinationNode.setName(desc + "_SC");
1212
1213       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1214       System.out.println("Identifying Combination Nodes:");
1215       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1216       skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1217       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
1218     }
1219   }
1220
1221   private void constructSkeletonHierarchyGraph() {
1222     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1223     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1224       Descriptor desc = (Descriptor) iterator.next();
1225       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
1226       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
1227       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
1228       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
1229       skeletonGraph.simplifyHierarchyGraph();
1230       // skeletonGraph.combineRedundantNodes(false);
1231       // skeletonGraph.removeRedundantEdges();
1232       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
1233     }
1234   }
1235
1236   private void debug_writeHierarchyDotFiles() {
1237
1238     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1239     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1240       Descriptor desc = (Descriptor) iterator.next();
1241       getHierarchyGraph(desc).writeGraph();
1242     }
1243
1244   }
1245
1246   private void debug_writeSimpleHierarchyDotFiles() {
1247
1248     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1249     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1250       Descriptor desc = (Descriptor) iterator.next();
1251       getHierarchyGraph(desc).writeGraph();
1252       getSimpleHierarchyGraph(desc).writeGraph();
1253     }
1254
1255   }
1256
1257   private void debug_writeSkeletonHierarchyDotFiles() {
1258
1259     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1260     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1261       Descriptor desc = (Descriptor) iterator.next();
1262       getSkeletonHierarchyGraph(desc).writeGraph();
1263     }
1264
1265   }
1266
1267   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
1268
1269     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1270     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1271       Descriptor desc = (Descriptor) iterator.next();
1272       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
1273     }
1274
1275   }
1276
1277   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
1278     return mapDescriptorToSimpleHierarchyGraph.get(d);
1279   }
1280
1281   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
1282     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
1283       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1284     }
1285     return mapDescriptorToSkeletonHierarchyGraph.get(d);
1286   }
1287
1288   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
1289     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
1290       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1291     }
1292     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
1293   }
1294
1295   private void constructHierarchyGraph() {
1296
1297     // do fixed-point analysis
1298
1299     ssjava.init();
1300     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1301
1302     // Collections.sort(descriptorListToAnalyze, new
1303     // Comparator<MethodDescriptor>() {
1304     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
1305     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
1306     // }
1307     // });
1308
1309     // current descriptors to visit in fixed-point interprocedural analysis,
1310     // prioritized by dependency in the call graph
1311     methodDescriptorsToVisitStack.clear();
1312
1313     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1314     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1315
1316     while (!descriptorListToAnalyze.isEmpty()) {
1317       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1318       methodDescriptorsToVisitStack.add(md);
1319     }
1320
1321     // analyze scheduled methods until there are no more to visit
1322     while (!methodDescriptorsToVisitStack.isEmpty()) {
1323       // start to analyze leaf node
1324       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1325
1326       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
1327       // MethodSummary methodSummary = new MethodSummary(md);
1328
1329       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
1330       // curMethodInfo = methodInfo;
1331
1332       System.out.println();
1333       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
1334
1335       constructHierarchyGraph(md, hierarchyGraph);
1336
1337       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
1338       // MethodSummary prevMethodSummary = getMethodSummary(md);
1339
1340       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
1341
1342         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
1343         // mapDescToLocationSummary.put(md, methodSummary);
1344
1345         // results for callee changed, so enqueue dependents caller for
1346         // further analysis
1347         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
1348         while (depsItr.hasNext()) {
1349           MethodDescriptor methodNext = depsItr.next();
1350           if (!methodDescriptorsToVisitStack.contains(methodNext)
1351               && methodDescriptorToVistSet.contains(methodNext)) {
1352             methodDescriptorsToVisitStack.add(methodNext);
1353           }
1354         }
1355
1356       }
1357
1358     }
1359
1360   }
1361
1362   private HierarchyGraph getHierarchyGraph(Descriptor d) {
1363     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
1364       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
1365     }
1366     return mapDescriptorToHierarchyGraph.get(d);
1367   }
1368
1369   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
1370
1371     // visit each node of method flow graph
1372     FlowGraph fg = getFlowGraph(md);
1373     Set<FlowNode> nodeSet = fg.getNodeSet();
1374
1375     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
1376     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
1377       Descriptor desc = (Descriptor) iterator.next();
1378       methodGraph.getHNode(desc).setSkeleton(true);
1379     }
1380
1381     // for the method lattice, we need to look at the first element of
1382     // NTuple<Descriptor>
1383     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1384       FlowNode srcNode = (FlowNode) iterator.next();
1385
1386       Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(srcNode);
1387       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
1388         FlowEdge outEdge = (FlowEdge) iterator2.next();
1389         FlowNode dstNode = outEdge.getDst();
1390
1391         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
1392         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
1393
1394         if (outEdge.getInitTuple().equals(srcNodeTuple)
1395             && outEdge.getEndTuple().equals(dstNodeTuple)) {
1396
1397           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
1398           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
1399
1400           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
1401               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
1402
1403             // value flows between fields
1404             Descriptor desc = srcCurTuple.get(0);
1405             ClassDescriptor classDesc;
1406
1407             if (desc.equals(GLOBALDESC)) {
1408               classDesc = md.getClassDesc();
1409             } else {
1410               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
1411               classDesc = varDesc.getType().getClassDesc();
1412             }
1413             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
1414
1415           } else {
1416             // value flow between local var - local var or local var - field
1417
1418             Descriptor srcDesc = srcCurTuple.get(0);
1419             Descriptor dstDesc = dstCurTuple.get(0);
1420
1421             methodGraph.addEdge(srcDesc, dstDesc);
1422
1423             if (fg.isParamDesc(srcDesc)) {
1424               methodGraph.setParamHNode(srcDesc);
1425             }
1426             if (fg.isParamDesc(dstDesc)) {
1427               methodGraph.setParamHNode(dstDesc);
1428             }
1429
1430           }
1431
1432         }
1433       }
1434     }
1435
1436   }
1437
1438   private MethodSummary getMethodSummary(MethodDescriptor md) {
1439     if (!mapDescToLocationSummary.containsKey(md)) {
1440       mapDescToLocationSummary.put(md, new MethodSummary(md));
1441     }
1442     return (MethodSummary) mapDescToLocationSummary.get(md);
1443   }
1444
1445   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
1446
1447     String classSymbol = cd.getSymbol();
1448     int idx = classSymbol.lastIndexOf("$");
1449     if (idx != -1) {
1450       classSymbol = classSymbol.substring(idx + 1);
1451     }
1452
1453     String pattern = "class " + classSymbol + " ";
1454     if (strLine.indexOf(pattern) != -1) {
1455       mapDescToDefinitionLine.put(cd, lineNum);
1456     }
1457   }
1458
1459   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
1460       int lineNum) {
1461     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
1462       MethodDescriptor md = (MethodDescriptor) iterator.next();
1463       String pattern = md.getMethodDeclaration();
1464       if (strLine.indexOf(pattern) != -1) {
1465         mapDescToDefinitionLine.put(md, lineNum);
1466         methodSet.remove(md);
1467         return;
1468       }
1469     }
1470
1471   }
1472
1473   private void readOriginalSourceFiles() {
1474
1475     SymbolTable classtable = state.getClassSymbolTable();
1476
1477     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
1478     classDescSet.addAll(classtable.getValueSet());
1479
1480     try {
1481       // inefficient implement. it may re-visit the same file if the file
1482       // contains more than one class definitions.
1483       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
1484         ClassDescriptor cd = (ClassDescriptor) iterator.next();
1485
1486         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
1487         methodSet.addAll(cd.getMethodTable().getValueSet());
1488
1489         String sourceFileName = cd.getSourceFileName();
1490         Vector<String> lineVec = new Vector<String>();
1491
1492         mapFileNameToLineVector.put(sourceFileName, lineVec);
1493
1494         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
1495         String strLine;
1496         int lineNum = 1;
1497         lineVec.add(""); // the index is started from 1.
1498         while ((strLine = in.readLine()) != null) {
1499           lineVec.add(lineNum, strLine);
1500           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
1501           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
1502           lineNum++;
1503         }
1504
1505       }
1506
1507     } catch (IOException e) {
1508       e.printStackTrace();
1509     }
1510
1511   }
1512
1513   private String generateLatticeDefinition(Descriptor desc) {
1514
1515     Set<String> sharedLocSet = new HashSet<String>();
1516
1517     SSJavaLattice<String> lattice = getLattice(desc);
1518     String rtr = "@LATTICE(\"";
1519
1520     Map<String, Set<String>> map = lattice.getTable();
1521     Set<String> keySet = map.keySet();
1522     boolean first = true;
1523     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1524       String key = (String) iterator.next();
1525       if (!key.equals(lattice.getTopItem())) {
1526         Set<String> connectedSet = map.get(key);
1527
1528         if (connectedSet.size() == 1) {
1529           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
1530             if (!first) {
1531               rtr += ",";
1532             } else {
1533               rtr += "LOC,";
1534               first = false;
1535             }
1536             rtr += key;
1537             if (lattice.isSharedLoc(key)) {
1538               rtr += "," + key + "*";
1539             }
1540           }
1541         }
1542
1543         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
1544           String loc = (String) iterator2.next();
1545           if (!loc.equals(lattice.getBottomItem())) {
1546             if (!first) {
1547               rtr += ",";
1548             } else {
1549               rtr += "LOC,";
1550               first = false;
1551             }
1552             rtr += loc + "<" + key;
1553             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
1554               rtr += "," + key + "*";
1555               sharedLocSet.add(key);
1556             }
1557             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
1558               rtr += "," + loc + "*";
1559               sharedLocSet.add(loc);
1560             }
1561
1562           }
1563         }
1564       }
1565     }
1566
1567     rtr += "\")";
1568
1569     if (desc instanceof MethodDescriptor) {
1570       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
1571
1572       MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
1573
1574       if (returnType != null && (!returnType.isVoid())) {
1575         rtr +=
1576             "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
1577       }
1578
1579       rtr += "\n@THISLOC(\"this\")";
1580       rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
1581
1582       CompositeLocation pcLoc = methodLocInfo.getPCLoc();
1583       if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
1584         rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
1585       }
1586
1587     }
1588
1589     return rtr;
1590   }
1591
1592   private void generateAnnoatedCode() {
1593
1594     readOriginalSourceFiles();
1595
1596     setupToAnalyze();
1597     while (!toAnalyzeIsEmpty()) {
1598       ClassDescriptor cd = toAnalyzeNext();
1599
1600       setupToAnalazeMethod(cd);
1601
1602       LocationInfo locInfo = mapClassToLocationInfo.get(cd);
1603       String sourceFileName = cd.getSourceFileName();
1604
1605       if (cd.isInterface()) {
1606         continue;
1607       }
1608
1609       int classDefLine = mapDescToDefinitionLine.get(cd);
1610       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
1611
1612       if (locInfo == null) {
1613         locInfo = getLocationInfo(cd);
1614       }
1615
1616       for (Iterator iter = cd.getFields(); iter.hasNext();) {
1617         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
1618         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
1619           String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
1620           if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
1621             getLattice(cd).put(locIdentifier);
1622           }
1623         }
1624       }
1625
1626       String fieldLatticeDefStr = generateLatticeDefinition(cd);
1627       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
1628       sourceVec.set(classDefLine, annoatedSrc);
1629
1630       // generate annotations for field declarations
1631       LocationInfo fieldLocInfo = getLocationInfo(cd);
1632       Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
1633
1634       for (Iterator iter = cd.getFields(); iter.hasNext();) {
1635         FieldDescriptor fd = (FieldDescriptor) iter.next();
1636
1637         String locAnnotationStr;
1638         CompositeLocation inferLoc = inferLocMap.get(fd);
1639
1640         if (inferLoc != null) {
1641           // infer loc is null if the corresponding field is static and final
1642           locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1643           int fdLineNum = fd.getLineNum();
1644           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
1645           String fieldDeclaration = fd.toString();
1646           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
1647           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
1648           sourceVec.set(fdLineNum, annoatedStr);
1649         }
1650
1651       }
1652
1653       while (!toAnalyzeMethodIsEmpty()) {
1654         MethodDescriptor md = toAnalyzeMethodNext();
1655
1656         if (!ssjava.needTobeAnnotated(md)) {
1657           continue;
1658         }
1659
1660         SSJavaLattice<String> methodLattice = md2lattice.get(md);
1661         if (methodLattice != null) {
1662
1663           int methodDefLine = md.getLineNum();
1664
1665           MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
1666
1667           Map<Descriptor, CompositeLocation> methodInferLocMap =
1668               methodLocInfo.getMapDescToInferLocation();
1669           Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
1670
1671           Set<String> localLocElementSet = methodLattice.getElementSet();
1672
1673           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
1674             Descriptor localVarDesc = (Descriptor) iterator.next();
1675             CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
1676
1677             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
1678             if (!localLocElementSet.contains(localLocIdentifier)) {
1679               methodLattice.put(localLocIdentifier);
1680             }
1681
1682             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1683
1684             if (!isParameter(md, localVarDesc)) {
1685               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
1686                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
1687                 String orgSourceLine = sourceVec.get(varLineNum);
1688                 int idx =
1689                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
1690                 assert (idx != -1);
1691                 String annoatedStr =
1692                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
1693                         + orgSourceLine.substring(idx);
1694                 sourceVec.set(varLineNum, annoatedStr);
1695               }
1696             } else {
1697               String methodDefStr = sourceVec.get(methodDefLine);
1698
1699               int idx =
1700                   getParamLocation(methodDefStr,
1701                       generateVarDeclaration((VarDescriptor) localVarDesc));
1702
1703               assert (idx != -1);
1704
1705               String annoatedStr =
1706                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
1707                       + methodDefStr.substring(idx);
1708               sourceVec.set(methodDefLine, annoatedStr);
1709             }
1710
1711           }
1712
1713           // check if the lattice has to have the location type for the this
1714           // reference...
1715
1716           // boolean needToAddthisRef = hasThisReference(md);
1717           if (localLocElementSet.contains("this")) {
1718             methodLattice.put("this");
1719           }
1720
1721           String methodLatticeDefStr = generateLatticeDefinition(md);
1722           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
1723           sourceVec.set(methodDefLine, annoatedStr);
1724
1725         }
1726       }
1727
1728     }
1729
1730     codeGen();
1731   }
1732
1733   private boolean hasThisReference(MethodDescriptor md) {
1734
1735     FlowGraph fg = getFlowGraph(md);
1736     Set<FlowNode> nodeSet = fg.getNodeSet();
1737     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1738       FlowNode flowNode = (FlowNode) iterator.next();
1739       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
1740         return true;
1741       }
1742     }
1743
1744     return false;
1745   }
1746
1747   private int getParamLocation(String methodStr, String paramStr) {
1748
1749     String pattern = paramStr + ",";
1750
1751     int idx = methodStr.indexOf(pattern);
1752     if (idx != -1) {
1753       return idx;
1754     } else {
1755       pattern = paramStr + ")";
1756       return methodStr.indexOf(pattern);
1757     }
1758
1759   }
1760
1761   private String generateVarDeclaration(VarDescriptor varDesc) {
1762
1763     TypeDescriptor td = varDesc.getType();
1764     String rtr = td.toString();
1765     if (td.isArray()) {
1766       for (int i = 0; i < td.getArrayCount(); i++) {
1767         rtr += "[]";
1768       }
1769     }
1770     rtr += " " + varDesc.getName();
1771     return rtr;
1772
1773   }
1774
1775   private String generateLocationAnnoatation(CompositeLocation loc) {
1776     String rtr = "";
1777     // method location
1778     Location methodLoc = loc.get(0);
1779     rtr += methodLoc.getLocIdentifier();
1780
1781     for (int i = 1; i < loc.getSize(); i++) {
1782       Location element = loc.get(i);
1783       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
1784     }
1785
1786     return rtr;
1787   }
1788
1789   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
1790     return getFlowGraph(md).isParamDesc(localVarDesc);
1791   }
1792
1793   private String extractFileName(String fileName) {
1794     int idx = fileName.lastIndexOf("/");
1795     if (idx == -1) {
1796       return fileName;
1797     } else {
1798       return fileName.substring(idx + 1);
1799     }
1800
1801   }
1802
1803   private void codeGen() {
1804
1805     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
1806     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
1807       String orgFileName = (String) iterator.next();
1808       String outputFileName = extractFileName(orgFileName);
1809
1810       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
1811
1812       try {
1813
1814         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
1815         BufferedWriter out = new BufferedWriter(fileWriter);
1816
1817         for (int i = 0; i < sourceVec.size(); i++) {
1818           out.write(sourceVec.get(i));
1819           out.newLine();
1820         }
1821         out.close();
1822       } catch (IOException e) {
1823         e.printStackTrace();
1824       }
1825
1826     }
1827
1828   }
1829
1830   private void checkLattices() {
1831
1832     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1833
1834     // current descriptors to visit in fixed-point interprocedural analysis,
1835     // prioritized by
1836     // dependency in the call graph
1837     methodDescriptorsToVisitStack.clear();
1838
1839     // descriptorListToAnalyze.removeFirst();
1840
1841     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1842     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1843
1844     while (!descriptorListToAnalyze.isEmpty()) {
1845       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1846       checkLatticesOfVirtualMethods(md);
1847     }
1848
1849   }
1850
1851   private void debug_writeLatticeDotFile() {
1852     // generate lattice dot file
1853
1854     setupToAnalyze();
1855
1856     while (!toAnalyzeIsEmpty()) {
1857       ClassDescriptor cd = toAnalyzeNext();
1858
1859       setupToAnalazeMethod(cd);
1860
1861       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1862       if (classLattice != null) {
1863         ssjava.writeLatticeDotFile(cd, null, classLattice);
1864         debug_printDescriptorToLocNameMapping(cd);
1865       }
1866
1867       while (!toAnalyzeMethodIsEmpty()) {
1868         MethodDescriptor md = toAnalyzeMethodNext();
1869         SSJavaLattice<String> methodLattice = md2lattice.get(md);
1870         if (methodLattice != null) {
1871           ssjava.writeLatticeDotFile(cd, md, methodLattice);
1872           debug_printDescriptorToLocNameMapping(md);
1873         }
1874       }
1875     }
1876
1877   }
1878
1879   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
1880
1881     LocationInfo info = getLocationInfo(desc);
1882     System.out.println("## " + desc + " ##");
1883     System.out.println(info.getMapDescToInferLocation());
1884     LocationInfo locInfo = getLocationInfo(desc);
1885     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
1886     System.out.println("###################");
1887
1888   }
1889
1890   private void inferLattices() {
1891   }
1892
1893   private void calculateExtraLocations() {
1894     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1895     for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) {
1896       MethodDescriptor md = (MethodDescriptor) iterator.next();
1897       calculateExtraLocations(md);
1898     }
1899   }
1900
1901   private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
1902     mapMethodDescToMethodLocationInfo.put(md, methodInfo);
1903   }
1904
1905   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
1906
1907     if (!md.isStatic()) {
1908       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1909       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1910
1911       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1912         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
1913         if (!md.equals(mdCallee)) {
1914           checkConsistency(md, mdCallee);
1915         }
1916       }
1917
1918     }
1919
1920   }
1921
1922   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
1923
1924     // check that two lattice have the same relations between parameters(+PC
1925     // LOC, GLOBAL_LOC RETURN LOC)
1926
1927     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
1928     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
1929
1930     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
1931     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
1932
1933     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
1934     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
1935
1936     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
1937
1938     // add location types of paramters
1939     for (int idx = 0; idx < numParam; idx++) {
1940       list1.add(paramMap1.get(Integer.valueOf(idx)));
1941       list2.add(paramMap2.get(Integer.valueOf(idx)));
1942     }
1943
1944     // add program counter location
1945     list1.add(locInfo1.getPCLoc());
1946     list2.add(locInfo2.getPCLoc());
1947
1948     if (!md1.getReturnType().isVoid()) {
1949       // add return value location
1950       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
1951       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
1952       list1.add(rtrLoc1);
1953       list2.add(rtrLoc2);
1954     }
1955
1956     // add global location type
1957     if (md1.isStatic()) {
1958       CompositeLocation globalLoc1 =
1959           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
1960       CompositeLocation globalLoc2 =
1961           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
1962       list1.add(globalLoc1);
1963       list2.add(globalLoc2);
1964     }
1965
1966     for (int i = 0; i < list1.size(); i++) {
1967       CompositeLocation locA1 = list1.get(i);
1968       CompositeLocation locA2 = list2.get(i);
1969       for (int k = 0; k < list1.size(); k++) {
1970         if (i != k) {
1971           CompositeLocation locB1 = list1.get(k);
1972           CompositeLocation locB2 = list2.get(k);
1973           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
1974
1975           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
1976
1977           if (r1 != r2) {
1978             throw new Error("The method " + md1 + " is not consistent with the method " + md2
1979                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
1980                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
1981           }
1982         }
1983       }
1984     }
1985
1986   }
1987
1988   private String getSymbol(int idx, FlowNode node) {
1989     Descriptor desc = node.getDescTuple().get(idx);
1990     return desc.getSymbol();
1991   }
1992
1993   private Descriptor getDescriptor(int idx, FlowNode node) {
1994     Descriptor desc = node.getDescTuple().get(idx);
1995     return desc;
1996   }
1997
1998   private void calculateExtraLocations(MethodDescriptor md) {
1999     // calcualte pcloc, returnloc,...
2000
2001     SSJavaLattice<String> methodLattice = getMethodLattice(md);
2002     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
2003     FlowGraph fg = getFlowGraph(md);
2004     Set<FlowNode> nodeSet = fg.getNodeSet();
2005
2006     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2007       FlowNode flowNode = (FlowNode) iterator.next();
2008       if (flowNode.isDeclaratonNode()) {
2009         CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
2010         String locIdentifier = inferLoc.get(0).getLocIdentifier();
2011         if (!methodLattice.containsKey(locIdentifier)) {
2012           methodLattice.put(locIdentifier);
2013         }
2014
2015       }
2016     }
2017
2018     Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
2019     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
2020
2021     if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2022       // calculate the initial program counter location
2023       // PC location is higher than location types of all parameters
2024       String pcLocSymbol = "PCLOC";
2025
2026       Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
2027
2028       for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2029         Integer paramIdx = (Integer) iterator.next();
2030
2031         FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
2032
2033         if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
2034           // parameter has in-value flows
2035           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2036           paramInFlowSet.add(inferLoc);
2037         }
2038       }
2039
2040       if (paramInFlowSet.size() > 0) {
2041         CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
2042         assert (lowestLoc != null);
2043         methodInfo.setPCLoc(lowestLoc);
2044       }
2045
2046     }
2047
2048     // calculate a return location
2049     // the return location type is lower than all parameters and location
2050     // types
2051     // of return values
2052     if (!md.getReturnType().isVoid()) {
2053       // first, generate the set of return value location types that starts
2054       // with
2055       // 'this' reference
2056
2057       Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
2058
2059       Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
2060       Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
2061       if (paramFlowNode != null) {
2062         for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
2063           FlowNode fn = (FlowNode) iterator.next();
2064           CompositeLocation inferLoc =
2065               generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
2066           inferParamLocSet.add(inferLoc);
2067         }
2068       }
2069
2070       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
2071
2072       skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2073         FlowNode returnNode = (FlowNode) iterator.next();
2074         CompositeLocation inferReturnLoc =
2075             generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2076         if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
2077           // if the location type of the return value matches "this" reference
2078           // then, check whether this return value is equal to/lower than all
2079           // of
2080           // parameters that possibly flow into the return values
2081           for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
2082             CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
2083
2084             if ((!paramInferLoc.equals(inferReturnLoc))
2085                 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
2086               continue skip;
2087             }
2088           }
2089           inferFieldReturnLocSet.add(inferReturnLoc);
2090
2091         }
2092       }
2093
2094       if (inferFieldReturnLocSet.size() > 0) {
2095
2096         CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
2097         if (returnLoc == null) {
2098           // in this case, assign <'this',bottom> to the RETURNLOC
2099           returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
2100           returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
2101               .getBottomItem()));
2102         }
2103         methodInfo.setReturnLoc(returnLoc);
2104
2105       } else {
2106         String returnLocSymbol = "RETURNLOC";
2107         CompositeLocation returnLocInferLoc =
2108             new CompositeLocation(new Location(md, returnLocSymbol));
2109         methodInfo.setReturnLoc(returnLocInferLoc);
2110
2111         for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2112           Integer paramIdx = (Integer) iterator.next();
2113           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2114           String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
2115           if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
2116             // TODO
2117             // addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol,
2118             // returnLocSymbol);
2119           }
2120         }
2121
2122         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2123           FlowNode returnNode = (FlowNode) iterator.next();
2124           CompositeLocation inferLoc =
2125               generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2126           if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
2127             // TODO
2128             // addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc);
2129           }
2130         }
2131
2132       }
2133
2134     }
2135   }
2136
2137   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
2138     Set<String> higherLocSet = new HashSet<String>();
2139
2140     Set<String> locSet = lattice.getTable().keySet();
2141     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
2142       String element = (String) iterator.next();
2143       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
2144         higherLocSet.add(element);
2145       }
2146     }
2147     return higherLocSet;
2148   }
2149
2150   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
2151       Set<CompositeLocation> set) {
2152
2153     CompositeLocation lowest = set.iterator().next();
2154
2155     if (set.size() == 1) {
2156       return lowest;
2157     }
2158
2159     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
2160       CompositeLocation loc = (CompositeLocation) iterator.next();
2161
2162       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
2163         // if there is a case where composite locations are incomparable, just
2164         // return null
2165         return null;
2166       }
2167
2168       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
2169         lowest = loc;
2170       }
2171     }
2172     return lowest;
2173   }
2174
2175   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
2176       CompositeLocation comp2) {
2177
2178     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
2179
2180     for (int idx = 0; idx < size; idx++) {
2181       Location loc1 = comp1.get(idx);
2182       Location loc2 = comp2.get(idx);
2183
2184       Descriptor desc1 = loc1.getDescriptor();
2185       Descriptor desc2 = loc2.getDescriptor();
2186
2187       if (!desc1.equals(desc2)) {
2188         throw new Error("Fail to compare " + comp1 + " and " + comp2);
2189       }
2190
2191       String symbol1 = loc1.getLocIdentifier();
2192       String symbol2 = loc2.getLocIdentifier();
2193
2194       SSJavaLattice<String> lattice;
2195       if (idx == 0) {
2196         lattice = methodLattice;
2197       } else {
2198         lattice = getLattice(desc1);
2199       }
2200
2201       if (symbol1.equals(symbol2)) {
2202         continue;
2203       } else if (!lattice.isComparable(symbol1, symbol2)) {
2204         return false;
2205       }
2206
2207     }
2208
2209     return true;
2210   }
2211
2212   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
2213       CompositeLocation comp2) {
2214
2215     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
2216
2217     for (int idx = 0; idx < size; idx++) {
2218       Location loc1 = comp1.get(idx);
2219       Location loc2 = comp2.get(idx);
2220
2221       Descriptor desc1 = loc1.getDescriptor();
2222       Descriptor desc2 = loc2.getDescriptor();
2223
2224       if (!desc1.equals(desc2)) {
2225         throw new Error("Fail to compare " + comp1 + " and " + comp2);
2226       }
2227
2228       String symbol1 = loc1.getLocIdentifier();
2229       String symbol2 = loc2.getLocIdentifier();
2230
2231       SSJavaLattice<String> lattice;
2232       if (idx == 0) {
2233         lattice = methodLattice;
2234       } else {
2235         lattice = getLattice(desc1);
2236       }
2237
2238       if (symbol1.equals(symbol2)) {
2239         continue;
2240       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
2241         return true;
2242       } else {
2243         return false;
2244       }
2245
2246     }
2247
2248     return false;
2249   }
2250
2251   private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller,
2252       MethodDescriptor mdCallee) {
2253
2254     System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller);
2255
2256     getSubGlobalFlowGraph(mdCallee);
2257
2258   }
2259
2260   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
2261     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
2262   }
2263
2264   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
2265       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
2266
2267     System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
2268
2269     // if the parameter A reaches to the parameter B
2270     // then, add an edge the argument A -> the argument B to the caller's flow
2271     // graph
2272
2273     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2274     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2275     int numParam = calleeFlowGraph.getNumParameters();
2276
2277     for (int i = 0; i < numParam; i++) {
2278       for (int k = 0; k < numParam; k++) {
2279
2280         if (i != k) {
2281
2282           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2283           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2284
2285           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
2286           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
2287
2288           // check if the callee propagates an ordering constraints through
2289           // parameters
2290
2291           Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2292
2293           if (localReachSet.contains(paramNode2)) {
2294             // need to propagate an ordering relation s.t. arg1 is higher
2295             // than arg2
2296
2297             System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2298             System.out
2299                 .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
2300
2301             // otherwise, flows between method/field locations...
2302             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2303             System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
2304
2305           }
2306
2307           System.out.println();
2308         }
2309       }
2310     }
2311     System.out.println("##\n");
2312
2313   }
2314
2315   private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
2316       MethodDescriptor mdCallee) {
2317
2318     System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
2319
2320     // if the parameter A reaches to the parameter B
2321     // then, add an edge the argument A -> the argument B to the caller's flow
2322     // graph
2323
2324     // TODO
2325     // also if a parameter is a composite location and is started with "this" reference,
2326     // need to make sure that the corresponding argument is higher than the translated location of
2327     // the parameter.
2328
2329     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2330     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2331     int numParam = calleeFlowGraph.getNumParameters();
2332
2333     for (int i = 0; i < numParam; i++) {
2334       for (int k = 0; k < numParam; k++) {
2335
2336         if (i != k) {
2337
2338           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2339           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2340
2341           System.out.println("param1=" + paramNode1 + " curDescTuple="
2342               + paramNode1.getCurrentDescTuple());
2343           System.out.println("param2=" + paramNode2 + " curDescTuple="
2344               + paramNode2.getCurrentDescTuple());
2345
2346           // TODO: deprecated method
2347           // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
2348           // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
2349           NodeTupleSet tupleSetArg1 = null;
2350           NodeTupleSet tupleSetArg2 = null;
2351
2352           for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
2353             NTuple<Descriptor> arg1Tuple = iter1.next();
2354
2355             for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
2356               NTuple<Descriptor> arg2Tuple = iter2.next();
2357
2358               // check if the callee propagates an ordering constraints through
2359               // parameters
2360
2361               Set<FlowNode> localReachSet =
2362                   calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2363
2364               if (localReachSet.contains(paramNode2)) {
2365                 // need to propagate an ordering relation s.t. arg1 is higher
2366                 // than arg2
2367
2368                 System.out
2369                     .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2370                 System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple="
2371                     + arg2Tuple);
2372
2373                 if (!min.getMethod().isStatic()) {
2374                   // check if this is the case that values flow to/from the
2375                   // current object reference 'this'
2376
2377                   NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2378                   Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2379
2380                   System.out.println("paramNode1.getCurrentDescTuple()="
2381                       + paramNode1.getCurrentDescTuple());
2382                   // calculate the prefix of the argument
2383
2384                   if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) {
2385                     // in this case, the callee flow causes a caller flow to the object whose method
2386                     // is invoked.
2387
2388                     if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2389                       // check whether ???
2390
2391                       NTuple<Descriptor> param1Prefix =
2392                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
2393                               paramNode1);
2394
2395                       if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) {
2396                         // in this case, we need to create a new edge 'this.FIELD'->'this'
2397                         // but we couldn't... instead we assign a new composite location started
2398                         // with 'this' reference to the corresponding parameter
2399
2400                         CompositeLocation compLocForParam1 =
2401                             generateCompositeLocation(mdCallee, param1Prefix);
2402
2403                         System.out
2404                             .println("set comp loc=" + compLocForParam1 + " to " + paramNode1);
2405                         paramNode1.setCompositeLocation(compLocForParam1);
2406
2407                         // then, we need to make sure that the corresponding argument in the caller
2408                         // is required to be higher than or equal to the translated parameter
2409                         // location
2410
2411                         NTuple<Descriptor> translatedParamTuple =
2412                             translateCompositeLocationToCaller(min, compLocForParam1);
2413
2414                         // TODO : check if the arg >= the tranlated parameter
2415
2416                         System.out.println("add a flow edge= " + arg1Tuple + "->"
2417                             + translatedParamTuple);
2418                         callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2419
2420                         continue;
2421
2422                       }
2423
2424                     } else {
2425                       // param1 has already been assigned a composite location
2426
2427                       System.out.println("--param1 has already been assigned a composite location");
2428                       CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation();
2429                       NTuple<Descriptor> translatedParamTuple =
2430                           translateCompositeLocationToCaller(min, compLocForParam1);
2431
2432                       // TODO : check if the arg >= the tranlated parameter
2433
2434                       System.out.println("add a flow edge= " + arg1Tuple + "->"
2435                           + translatedParamTuple);
2436                       callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2437
2438                       continue;
2439
2440                     }
2441
2442                   } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) {
2443                     // in this case, the callee flow causes a caller flow originated from the object
2444                     // whose
2445                     // method is invoked.
2446
2447                     System.out.println("###FROM CASE");
2448
2449                     if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2450
2451                       NTuple<Descriptor> param2Prefix =
2452                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple,
2453                               paramNode2);
2454
2455                       if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) {
2456                         // in this case, we need to create a new edge 'this' ->
2457                         // 'this.FIELD' but we couldn't... instead we assign the corresponding
2458                         // parameter a new composite location started with 'this' reference
2459
2460                         CompositeLocation compLocForParam2 =
2461                             generateCompositeLocation(mdCallee, param2Prefix);
2462
2463                         // System.out.println("set comp loc=" + compLocForParam2
2464                         // +
2465                         // " to " + paramNode2);
2466                         paramNode1.setCompositeLocation(compLocForParam2);
2467                         continue;
2468                       }
2469                     }
2470
2471                   }
2472                 }
2473
2474                 // otherwise, flows between method/field locations...
2475                 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2476                 System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
2477
2478               }
2479
2480             }
2481
2482           }
2483           System.out.println();
2484         }
2485       }
2486     }
2487     System.out.println("##\n");
2488   }
2489
2490   private NTuple<Descriptor> translateCompositeLocationToCaller(MethodInvokeNode min,
2491       CompositeLocation compLocForParam1) {
2492     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2493
2494     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
2495
2496     for (int i = 0; i < baseTuple.size(); i++) {
2497       tuple.add(baseTuple.get(i));
2498     }
2499
2500     for (int i = 1; i < compLocForParam1.getSize(); i++) {
2501       Location loc = compLocForParam1.get(i);
2502       tuple.add(loc.getLocDescriptor());
2503     }
2504
2505     return tuple;
2506   }
2507
2508   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
2509
2510     System.out.println("generateCompositeLocation=" + prefixLocTuple);
2511
2512     CompositeLocation newCompLoc = new CompositeLocation();
2513     for (int i = 0; i < prefixLocTuple.size(); i++) {
2514       newCompLoc.addLocation(prefixLocTuple.get(i));
2515     }
2516
2517     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
2518
2519     ClassDescriptor enclosingDescriptor;
2520     if (lastDescOfPrefix instanceof FieldDescriptor) {
2521       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
2522       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
2523     } else {
2524       // var descriptor case
2525       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
2526     }
2527     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
2528
2529     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
2530     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
2531
2532     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
2533     newLoc.setLocDescriptor(newLocDescriptor);
2534     newCompLoc.addLocation(newLoc);
2535
2536     // System.out.println("--newCompLoc=" + newCompLoc);
2537     return newCompLoc;
2538   }
2539
2540   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
2541       NTuple<Descriptor> paramPrefix) {
2542
2543     System.out.println("generateCompositeLocation=" + paramPrefix);
2544
2545     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
2546
2547     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
2548     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
2549     // + lastDescOfPrefix.getClass());
2550     ClassDescriptor enclosingDescriptor;
2551     if (lastDescOfPrefix instanceof FieldDescriptor) {
2552       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
2553       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
2554     } else {
2555       // var descriptor case
2556       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
2557     }
2558     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
2559
2560     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
2561     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
2562
2563     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
2564     newLoc.setLocDescriptor(newLocDescriptor);
2565     newCompLoc.addLocation(newLoc);
2566
2567     // System.out.println("--newCompLoc=" + newCompLoc);
2568     return newCompLoc;
2569   }
2570
2571   private NTuple<Descriptor> calculatePrefixForParam(FlowGraph callerFlowGraph,
2572       FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple<Descriptor> arg1Tuple,
2573       FlowNode paramNode1) {
2574
2575     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2576     Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2577     System.out.println("baseRef=" + baseRef);
2578
2579     FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple);
2580     List<NTuple<Descriptor>> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1);
2581     System.out.println("callerPrefixList=" + callerPrefixList);
2582
2583     List<NTuple<Descriptor>> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1);
2584     System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList);
2585
2586     List<NTuple<Descriptor>> calleePrefixList =
2587         translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList);
2588
2589     System.out.println("calleePrefixList=" + calleePrefixList);
2590
2591     Set<FlowNode> reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1);
2592     System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1);
2593
2594     for (int i = 0; i < calleePrefixList.size(); i++) {
2595       NTuple<Descriptor> curPrefix = calleePrefixList.get(i);
2596       Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
2597
2598       for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) {
2599         FlowNode reachNode = (FlowNode) iterator2.next();
2600         if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
2601           reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
2602         }
2603       }
2604
2605       if (!reachableCommonPrefixSet.isEmpty()) {
2606         System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet
2607             + " with curPreFix=" + curPrefix);
2608         return curPrefix;
2609       }
2610
2611     }
2612
2613     return null;
2614   }
2615
2616   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
2617       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
2618
2619     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
2620
2621     for (int i = 0; i < callerPrefixList.size(); i++) {
2622       NTuple<Descriptor> prefix = callerPrefixList.get(i);
2623       if (prefix.startsWith(baseRef)) {
2624         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
2625         calleePrefix.add(mdCallee.getThis());
2626         for (int k = 1; k < prefix.size(); k++) {
2627           calleePrefix.add(prefix.get(k));
2628         }
2629         calleePrefixList.add(calleePrefix);
2630       }
2631     }
2632
2633     return calleePrefixList;
2634
2635   }
2636
2637   private List<NTuple<Descriptor>> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) {
2638
2639     System.out.println("\n##### calculatePrefixList=" + flowNode);
2640
2641     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
2642     inNodeSet.add(flowNode);
2643
2644     System.out.println("inNodeSet=" + inNodeSet);
2645
2646     List<NTuple<Descriptor>> prefixList = new ArrayList<NTuple<Descriptor>>();
2647
2648     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
2649       FlowNode inNode = (FlowNode) iterator.next();
2650
2651       NTuple<Descriptor> inNodeTuple = inNode.getCurrentDescTuple();
2652
2653       // CompositeLocation inNodeInferredLoc =
2654       // generateInferredCompositeLocation(methodInfo, inNodeTuple);
2655       // NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
2656
2657       for (int i = 1; i < inNodeTuple.size(); i++) {
2658         NTuple<Descriptor> prefix = inNodeTuple.subList(0, i);
2659         if (!prefixList.contains(prefix)) {
2660           prefixList.add(prefix);
2661         }
2662       }
2663     }
2664
2665     Collections.sort(prefixList, new Comparator<NTuple<Descriptor>>() {
2666       public int compare(NTuple<Descriptor> arg0, NTuple<Descriptor> arg1) {
2667         int s0 = arg0.size();
2668         int s1 = arg1.size();
2669         if (s0 > s1) {
2670           return -1;
2671         } else if (s0 == s1) {
2672           return 0;
2673         } else {
2674           return 1;
2675         }
2676       }
2677     });
2678
2679     return prefixList;
2680
2681   }
2682
2683   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
2684
2685     CompositeLocation compLoc = new CompositeLocation();
2686
2687     Descriptor enclosingDescriptor = md;
2688
2689     for (int i = 0; i < tuple.size(); i++) {
2690       Descriptor curDescriptor = tuple.get(i);
2691       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
2692       locElement.setLocDescriptor(curDescriptor);
2693       compLoc.addLocation(locElement);
2694
2695       if (curDescriptor instanceof VarDescriptor) {
2696         enclosingDescriptor = md.getClassDesc();
2697       } else if (curDescriptor instanceof NameDescriptor) {
2698         // it is "GLOBAL LOC" case!
2699         enclosingDescriptor = GLOBALDESC;
2700       } else {
2701         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
2702       }
2703
2704     }
2705
2706     System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc);
2707
2708     return compLoc;
2709   }
2710
2711   private LocationDescriptor generateNewLocationDescriptor() {
2712     return new LocationDescriptor("Loc" + (locSeed++));
2713   }
2714
2715   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
2716
2717     // return the index where the prefix shared by tuple1 and tuple2 is ended
2718     // if there is no prefix shared by both of them, return -1
2719
2720     int minSize = tuple1.size();
2721     if (minSize > tuple2.size()) {
2722       minSize = tuple2.size();
2723     }
2724
2725     int idx = -1;
2726     for (int i = 0; i < minSize; i++) {
2727       if (!tuple1.get(i).equals(tuple2.get(i))) {
2728         break;
2729       } else {
2730         idx++;
2731       }
2732     }
2733
2734     return idx;
2735   }
2736
2737   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
2738       NTuple<Location> tuple) {
2739
2740     // first, retrieve inferred location by the local var descriptor
2741     CompositeLocation inferLoc = new CompositeLocation();
2742
2743     CompositeLocation localVarInferLoc =
2744         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
2745
2746     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
2747
2748     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
2749       inferLoc.addLocation(localVarInferLoc.get(i));
2750     }
2751
2752     for (int i = 1; i < tuple.size(); i++) {
2753       Location cur = tuple.get(i);
2754       Descriptor enclosingDesc = cur.getDescriptor();
2755       Descriptor curDesc = cur.getLocDescriptor();
2756
2757       Location inferLocElement;
2758       if (curDesc == null) {
2759         // in this case, we have a newly generated location.
2760         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
2761       } else {
2762         String fieldLocSymbol =
2763             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
2764         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
2765         inferLocElement.setLocDescriptor(curDesc);
2766       }
2767
2768       inferLoc.addLocation(inferLocElement);
2769
2770     }
2771
2772     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
2773     return inferLoc;
2774   }
2775
2776   public LocationInfo getLocationInfo(Descriptor d) {
2777     if (d instanceof MethodDescriptor) {
2778       return getMethodLocationInfo((MethodDescriptor) d);
2779     } else {
2780       return getFieldLocationInfo((ClassDescriptor) d);
2781     }
2782   }
2783
2784   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
2785
2786     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
2787       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
2788     }
2789
2790     return mapMethodDescToMethodLocationInfo.get(md);
2791
2792   }
2793
2794   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
2795
2796     if (!mapClassToLocationInfo.containsKey(cd)) {
2797       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
2798     }
2799
2800     return mapClassToLocationInfo.get(cd);
2801
2802   }
2803
2804   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
2805       NTuple<Location> prefix, NTuple<Location> element) {
2806
2807     if (!map.containsKey(prefix)) {
2808       map.put(prefix, new HashSet<NTuple<Location>>());
2809     }
2810     map.get(prefix).add(element);
2811   }
2812
2813   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
2814     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
2815       Descriptor desc = (Descriptor) iterator.next();
2816
2817       if (desc.equals(LocationInference.GLOBALDESC)) {
2818         return true;
2819       } else if (desc instanceof VarDescriptor) {
2820         if (!((VarDescriptor) desc).getType().isPrimitive()) {
2821           return true;
2822         }
2823       } else if (desc instanceof FieldDescriptor) {
2824         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
2825           return true;
2826         }
2827       }
2828
2829     }
2830     return false;
2831   }
2832
2833   private SSJavaLattice<String> getLattice(Descriptor d) {
2834     if (d instanceof MethodDescriptor) {
2835       return getMethodLattice((MethodDescriptor) d);
2836     } else {
2837       return getFieldLattice((ClassDescriptor) d);
2838     }
2839   }
2840
2841   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
2842     if (!md2lattice.containsKey(md)) {
2843       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2844     }
2845     return md2lattice.get(md);
2846   }
2847
2848   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
2849     md2lattice.put(md, lattice);
2850   }
2851
2852   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
2853       int idx) {
2854
2855     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
2856     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
2857
2858     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
2859         && dstCurTuple.size() > (idx + 1)) {
2860       // value flow between fields: we don't need to add a binary relation
2861       // for this case
2862
2863       Descriptor desc = srcCurTuple.get(idx);
2864       ClassDescriptor classDesc;
2865
2866       if (idx == 0) {
2867         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
2868       } else {
2869         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2870       }
2871
2872       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
2873
2874     } else {
2875
2876       Descriptor srcFieldDesc = srcCurTuple.get(idx);
2877       Descriptor dstFieldDesc = dstCurTuple.get(idx);
2878
2879       // add a new edge
2880       getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
2881
2882     }
2883
2884   }
2885
2886   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
2887     if (!cd2lattice.containsKey(cd)) {
2888       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2889     }
2890     return cd2lattice.get(cd);
2891   }
2892
2893   public LinkedList<MethodDescriptor> computeMethodList() {
2894
2895     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
2896
2897     setupToAnalyze();
2898
2899     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
2900     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
2901
2902     while (!toAnalyzeIsEmpty()) {
2903       ClassDescriptor cd = toAnalyzeNext();
2904
2905       setupToAnalazeMethod(cd);
2906       temp_toanalyzeMethodList.removeAll(visited);
2907
2908       while (!toAnalyzeMethodIsEmpty()) {
2909         MethodDescriptor md = toAnalyzeMethodNext();
2910         if ((!visited.contains(md))
2911             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
2912
2913           // creates a mapping from a method descriptor to virtual methods
2914           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2915           if (md.isStatic()) {
2916             setPossibleCallees.add(md);
2917           } else {
2918             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
2919           }
2920
2921           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
2922           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
2923
2924           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
2925             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
2926             if ((!ssjava.isTrustMethod(calleemd))
2927                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
2928               if (!visited.contains(calleemd)) {
2929                 temp_toanalyzeMethodList.add(calleemd);
2930               }
2931               reachableCallee.add(calleemd);
2932               needToAnalyzeCalleeSet.add(calleemd);
2933             }
2934           }
2935
2936           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
2937
2938           visited.add(md);
2939
2940           toSort.add(md);
2941         }
2942       }
2943     }
2944
2945     return ssjava.topologicalSort(toSort);
2946
2947   }
2948
2949   public void constructFlowGraph() {
2950
2951     System.out.println("");
2952     toanalyze_methodDescList = computeMethodList();
2953
2954     LinkedList<MethodDescriptor> methodDescList =
2955         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
2956
2957     System.out.println("@@@methodDescList=" + methodDescList);
2958     // System.exit(0);
2959
2960     while (!methodDescList.isEmpty()) {
2961       MethodDescriptor md = methodDescList.removeLast();
2962       if (state.SSJAVADEBUG) {
2963         System.out.println();
2964         System.out.println("SSJAVA: Constructing a flow graph: " + md);
2965
2966         // creates a mapping from a parameter descriptor to its index
2967         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
2968         int offset = 0;
2969         if (!md.isStatic()) {
2970           offset = 1;
2971           mapParamDescToIdx.put(md.getThis(), 0);
2972         }
2973
2974         for (int i = 0; i < md.numParameters(); i++) {
2975           Descriptor paramDesc = (Descriptor) md.getParameter(i);
2976           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
2977         }
2978
2979         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
2980         mapMethodDescriptorToFlowGraph.put(md, fg);
2981
2982         analyzeMethodBody(md.getClassDesc(), md);
2983
2984         System.out.println("##constructSubGlobalFlowGraph");
2985         GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
2986         mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
2987
2988         // TODO
2989         System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
2990         addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
2991         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
2992
2993         propagateFlowsFromCalleesWithNoCompositeLocation(md);
2994         // assignCompositeLocation(md);
2995
2996       }
2997     }
2998     // _debug_printGraph();
2999
3000   }
3001
3002   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
3003     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
3004       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
3005     }
3006     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
3007   }
3008
3009   private void constructSubGlobalFlowGraph(MethodDescriptor md) {
3010
3011     FlowGraph flowGraph = getFlowGraph(md);
3012
3013     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(md);
3014
3015     for (Iterator<MethodInvokeNode> iter = setMethodInvokeNode.iterator(); iter.hasNext();) {
3016       MethodInvokeNode min = iter.next();
3017       propagateFlowsFromMethodInvokeNode(md, min);
3018     }
3019
3020   }
3021
3022   private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) {
3023     // the transformation for a call site propagates flows through parameters
3024     // if the method is virtual, it also grab all relations from any possible
3025     // callees
3026
3027     MethodDescriptor mdCallee = min.getMethod();
3028     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3029     if (mdCallee.isStatic()) {
3030       setPossibleCallees.add(mdCallee);
3031     } else {
3032       Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3033       // removes method descriptors that are not invoked by the caller
3034       calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3035       setPossibleCallees.addAll(calleeSet);
3036     }
3037
3038     for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3039       MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3040       contributeCalleeFlows(min, mdCaller, possibleMdCallee);
3041     }
3042
3043   }
3044
3045   private void assignCompositeLocation(MethodDescriptor md) {
3046
3047     FlowGraph flowGraph = getFlowGraph(md);
3048
3049     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
3050
3051     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3052       FlowNode flowNode = (FlowNode) iterator.next();
3053
3054       // assign a composite location only to the local variable
3055       if (flowNode.getCurrentDescTuple().size() == 1) {
3056
3057         List<NTuple<Descriptor>> prefixList = calculatePrefixList(flowGraph, flowNode);
3058         Set<FlowNode> reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
3059
3060         for (int i = 0; i < prefixList.size(); i++) {
3061           NTuple<Descriptor> curPrefix = prefixList.get(i);
3062           Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
3063
3064           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
3065             FlowNode reachNode = (FlowNode) iterator2.next();
3066             if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
3067               reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
3068             }
3069           }
3070
3071           if (!reachableCommonPrefixSet.isEmpty()) {
3072             System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix="
3073                 + curPrefix);
3074             CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix);
3075             flowNode.setCompositeLocation(newCompLoc);
3076             continue next;
3077           }
3078
3079         }
3080       }
3081
3082     }
3083
3084   }
3085
3086   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
3087
3088     // the transformation for a call site propagates flows through parameters
3089     // if the method is virtual, it also grab all relations from any possible
3090     // callees
3091
3092     Set<MethodInvokeNode> setMethodInvokeNode =
3093         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3094
3095     if (setMethodInvokeNode != null) {
3096
3097       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3098         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3099         MethodDescriptor mdCallee = min.getMethod();
3100         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3101         if (mdCallee.isStatic()) {
3102           setPossibleCallees.add(mdCallee);
3103         } else {
3104           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3105           // removes method descriptors that are not invoked by the caller
3106           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3107           setPossibleCallees.addAll(calleeSet);
3108         }
3109
3110         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3111           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3112           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
3113         }
3114
3115       }
3116     }
3117
3118   }
3119
3120   private void propagateFlowsFromCallees(MethodDescriptor mdCaller) {
3121
3122     // the transformation for a call site propagates flows through parameters
3123     // if the method is virtual, it also grab all relations from any possible
3124     // callees
3125
3126     Set<MethodInvokeNode> setMethodInvokeNode =
3127         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3128
3129     if (setMethodInvokeNode != null) {
3130
3131       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3132         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3133         MethodDescriptor mdCallee = min.getMethod();
3134         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3135         if (mdCallee.isStatic()) {
3136           setPossibleCallees.add(mdCallee);
3137         } else {
3138           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3139           // removes method descriptors that are not invoked by the caller
3140           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3141           setPossibleCallees.addAll(calleeSet);
3142         }
3143
3144         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3145           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3146           propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
3147         }
3148
3149       }
3150     }
3151
3152   }
3153
3154   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
3155     BlockNode bn = state.getMethodBody(md);
3156     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
3157     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
3158   }
3159
3160   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
3161       NodeTupleSet implicitFlowTupleSet) {
3162
3163     bn.getVarTable().setParent(nametable);
3164     for (int i = 0; i < bn.size(); i++) {
3165       BlockStatementNode bsn = bn.get(i);
3166       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3167     }
3168
3169   }
3170
3171   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
3172       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
3173
3174     switch (bsn.kind()) {
3175     case Kind.BlockExpressionNode:
3176       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
3177       break;
3178
3179     case Kind.DeclarationNode:
3180       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
3181       break;
3182
3183     case Kind.IfStatementNode:
3184       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
3185       break;
3186
3187     case Kind.LoopNode:
3188       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
3189       break;
3190
3191     case Kind.ReturnNode:
3192       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
3193       break;
3194
3195     case Kind.SubBlockNode:
3196       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
3197       break;
3198
3199     case Kind.ContinueBreakNode:
3200       break;
3201
3202     case Kind.SwitchStatementNode:
3203       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
3204       break;
3205
3206     }
3207
3208   }
3209
3210   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
3211       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3212
3213     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
3214
3215   }
3216
3217   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
3218       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
3219
3220     NodeTupleSet condTupleNode = new NodeTupleSet();
3221     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
3222         implicitFlowTupleSet, false);
3223
3224     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3225
3226     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3227     newImplicitTupleSet.addTupleSet(condTupleNode);
3228
3229     if (newImplicitTupleSet.size() > 1) {
3230       // need to create an intermediate node for the GLB of conditional locations & implicit flows
3231       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3232       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3233         NTuple<Descriptor> tuple = idxIter.next();
3234         addFlowGraphEdge(md, tuple, interTuple);
3235       }
3236       newImplicitTupleSet.clear();
3237       newImplicitTupleSet.addTuple(interTuple);
3238     }
3239
3240     BlockNode sbn = ssn.getSwitchBody();
3241     for (int i = 0; i < sbn.size(); i++) {
3242       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
3243     }
3244
3245   }
3246
3247   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
3248       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3249     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
3250   }
3251
3252   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
3253       NodeTupleSet implicitFlowTupleSet) {
3254
3255     ExpressionNode returnExp = rn.getReturnExpression();
3256
3257     if (returnExp != null) {
3258       NodeTupleSet nodeSet = new NodeTupleSet();
3259       // if a return expression returns a literal value, nodeSet is empty
3260       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
3261       FlowGraph fg = getFlowGraph(md);
3262
3263       // if (implicitFlowTupleSet.size() == 1
3264       // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) {
3265       //
3266       // // since there is already an intermediate node for the GLB of implicit flows
3267       // // we don't need to create another intermediate node.
3268       // // just re-use the intermediate node for implicit flows.
3269       //
3270       // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next());
3271       //
3272       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3273       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>) iterator.next();
3274       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
3275       // }
3276       //
3277       // }
3278
3279       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
3280
3281       // add tuples from return node
3282       currentFlowTupleSet.addTupleSet(nodeSet);
3283
3284       // add tuples corresponding to the current implicit flows
3285       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
3286
3287       if (currentFlowTupleSet.size() > 1) {
3288         FlowNode meetNode = fg.createIntermediateNode();
3289         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
3290           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
3291           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
3292         }
3293         fg.addReturnFlowNode(meetNode.getDescTuple());
3294       } else if (currentFlowTupleSet.size() == 1) {
3295         NTuple<Descriptor> tuple = currentFlowTupleSet.iterator().next();
3296         fg.addReturnFlowNode(tuple);
3297       }
3298
3299     }
3300
3301   }
3302
3303   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
3304       NodeTupleSet implicitFlowTupleSet) {
3305
3306     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
3307
3308       NodeTupleSet condTupleNode = new NodeTupleSet();
3309       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
3310           implicitFlowTupleSet, false);
3311
3312       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3313
3314       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3315       newImplicitTupleSet.addTupleSet(condTupleNode);
3316
3317       if (newImplicitTupleSet.size() > 1) {
3318         // need to create an intermediate node for the GLB of conditional locations & implicit flows
3319         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3320         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
3321             .hasNext();) {
3322           NTuple<Descriptor> tuple = idxIter.next();
3323           addFlowGraphEdge(md, tuple, interTuple);
3324         }
3325         newImplicitTupleSet.clear();
3326         newImplicitTupleSet.addTuple(interTuple);
3327
3328       }
3329
3330       // ///////////
3331       // System.out.println("condTupleNode="+condTupleNode);
3332       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3333       //
3334       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3335       // NTuple<Descriptor> tuple = idxIter.next();
3336       // addFlowGraphEdge(md, tuple, interTuple);
3337       // }
3338
3339       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3340       // .hasNext();) {
3341       // NTuple<Descriptor> tuple = idxIter.next();
3342       // addFlowGraphEdge(md, tuple, interTuple);
3343       // }
3344
3345       // NodeTupleSet newImplicitSet = new NodeTupleSet();
3346       // newImplicitSet.addTuple(interTuple);
3347       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
3348       // ///////////
3349
3350       // condTupleNode.addTupleSet(implicitFlowTupleSet);
3351
3352       // add edges from condNodeTupleSet to all nodes of conditional nodes
3353       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
3354
3355     } else {
3356       // check 'for loop' case
3357       BlockNode bn = ln.getInitializer();
3358       bn.getVarTable().setParent(nametable);
3359       for (int i = 0; i < bn.size(); i++) {
3360         BlockStatementNode bsn = bn.get(i);
3361         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3362       }
3363
3364       NodeTupleSet condTupleNode = new NodeTupleSet();
3365       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
3366           implicitFlowTupleSet, false);
3367
3368       // ///////////
3369       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3370
3371       for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3372         NTuple<Descriptor> tuple = idxIter.next();
3373         addFlowGraphEdge(md, tuple, interTuple);
3374       }
3375
3376       for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3377           .hasNext();) {
3378         NTuple<Descriptor> tuple = idxIter.next();
3379         addFlowGraphEdge(md, tuple, interTuple);
3380       }
3381
3382       NodeTupleSet newImplicitSet = new NodeTupleSet();
3383       newImplicitSet.addTuple(interTuple);
3384       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet);
3385       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet);
3386       // ///////////
3387
3388       // condTupleNode.addTupleSet(implicitFlowTupleSet);
3389       //
3390       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
3391       // condTupleNode);
3392       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
3393       // condTupleNode);
3394
3395     }
3396
3397   }
3398
3399   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
3400       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
3401
3402     System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
3403
3404     NodeTupleSet condTupleNode = new NodeTupleSet();
3405     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
3406         implicitFlowTupleSet, false);
3407
3408     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3409
3410     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3411     newImplicitTupleSet.addTupleSet(condTupleNode);
3412
3413     System.out.println("condTupleNode=" + condTupleNode);
3414     System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet);
3415     System.out.println("newImplicitTupleSet=" + newImplicitTupleSet);
3416
3417     if (newImplicitTupleSet.size() > 1) {
3418
3419       // need to create an intermediate node for the GLB of conditional locations & implicit flows
3420       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3421       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3422         NTuple<Descriptor> tuple = idxIter.next();
3423         addFlowGraphEdge(md, tuple, interTuple);
3424       }
3425       newImplicitTupleSet.clear();
3426       newImplicitTupleSet.addTuple(interTuple);
3427     }
3428
3429     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
3430
3431     if (isn.getFalseBlock() != null) {
3432       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
3433     }
3434
3435   }
3436
3437   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
3438       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
3439
3440     VarDescriptor vd = dn.getVarDescriptor();
3441     mapDescToDefinitionLine.put(vd, dn.getNumLine());
3442     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
3443     tupleLHS.add(vd);
3444     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
3445     fn.setDeclarationNode();
3446
3447     if (dn.getExpression() != null) {
3448
3449       NodeTupleSet nodeSetRHS = new NodeTupleSet();
3450       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
3451           implicitFlowTupleSet, false);
3452
3453       // creates edges from RHS to LHS
3454       NTuple<Descriptor> interTuple = null;
3455       if (nodeSetRHS.size() > 1) {
3456         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3457       }
3458
3459       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
3460         NTuple<Descriptor> fromTuple = iter.next();
3461         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
3462       }
3463
3464       // creates edges from implicitFlowTupleSet to LHS
3465       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
3466         NTuple<Descriptor> implicitTuple = iter.next();
3467         addFlowGraphEdge(md, implicitTuple, tupleLHS);
3468       }
3469
3470     }
3471
3472   }
3473
3474   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
3475       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
3476     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
3477         false);
3478   }
3479
3480   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3481       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
3482     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
3483   }
3484
3485   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3486       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3487       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
3488
3489     // note that expression node can create more than one flow node
3490     // nodeSet contains of flow nodes
3491     // base is always assigned to null except the case of a name node!
3492
3493     NTuple<Descriptor> flowTuple;
3494
3495     switch (en.kind()) {
3496
3497     case Kind.AssignmentNode:
3498       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
3499           implicitFlowTupleSet);
3500       break;
3501
3502     case Kind.FieldAccessNode:
3503       flowTuple =
3504           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
3505               implicitFlowTupleSet, isLHS);
3506       if (flowTuple != null) {
3507         nodeSet.addTuple(flowTuple);
3508       }
3509       return flowTuple;
3510
3511     case Kind.NameNode:
3512       NodeTupleSet nameNodeSet = new NodeTupleSet();
3513       flowTuple =
3514           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
3515       if (flowTuple != null) {
3516         nodeSet.addTuple(flowTuple);
3517       }
3518       return flowTuple;
3519
3520     case Kind.OpNode:
3521       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
3522       break;
3523
3524     case Kind.CreateObjectNode:
3525       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
3526       break;
3527
3528     case Kind.ArrayAccessNode:
3529       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
3530       break;
3531
3532     case Kind.LiteralNode:
3533       analyzeLiteralNode(md, nametable, (LiteralNode) en);
3534       break;
3535
3536     case Kind.MethodInvokeNode:
3537       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
3538           implicitFlowTupleSet);
3539       break;
3540
3541     case Kind.TertiaryNode:
3542       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
3543       break;
3544
3545     case Kind.CastNode:
3546       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
3547       break;
3548     // case Kind.InstanceOfNode:
3549     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
3550     // return null;
3551
3552     // case Kind.ArrayInitializerNode:
3553     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
3554     // td);
3555     // return null;
3556
3557     // case Kind.ClassTypeNode:
3558     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
3559     // return null;
3560
3561     // case Kind.OffsetNode:
3562     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
3563     // return null;
3564
3565     }
3566     return null;
3567
3568   }
3569
3570   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
3571       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
3572
3573     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
3574         implicitFlowTupleSet, false);
3575
3576   }
3577
3578   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
3579       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3580
3581     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
3582     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
3583         implicitFlowTupleSet, false);
3584
3585     // add edges from tertiaryTupleNode to all nodes of conditional nodes
3586     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
3587     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
3588         implicitFlowTupleSet, false);
3589
3590     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
3591         implicitFlowTupleSet, false);
3592
3593     nodeSet.addTupleSet(tertiaryTupleNode);
3594
3595   }
3596
3597   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
3598       MethodInvokeNode min) {
3599     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
3600     if (set == null) {
3601       set = new HashSet<MethodInvokeNode>();
3602       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
3603     }
3604     set.add(min);
3605   }
3606
3607   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
3608
3609     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
3610       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
3611     }
3612     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
3613   }
3614
3615   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
3616     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
3617   }
3618
3619   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
3620       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3621
3622     System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
3623
3624     if (nodeSet == null) {
3625       nodeSet = new NodeTupleSet();
3626     }
3627
3628     MethodDescriptor calleeMethodDesc = min.getMethod();
3629
3630     NameDescriptor baseName = min.getBaseName();
3631     boolean isSystemout = false;
3632     if (baseName != null) {
3633       isSystemout = baseName.getSymbol().equals("System.out");
3634     }
3635
3636     if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
3637         && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) {
3638
3639       addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
3640
3641       FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
3642       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
3643
3644       System.out.println("#calleeReturnSet=" + calleeReturnSet);
3645
3646       if (min.getExpression() != null) {
3647
3648         NodeTupleSet baseNodeSet = new NodeTupleSet();
3649         analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
3650             implicitFlowTupleSet, false);
3651
3652         assert (baseNodeSet.size() == 1);
3653         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
3654         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
3655
3656         if (!min.getMethod().isStatic()) {
3657           addArgIdxMap(min, 0, baseTuple);
3658
3659           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
3660             FlowNode returnNode = (FlowNode) iterator.next();
3661             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
3662             if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
3663               // the location type of the return value is started with 'this'
3664               // reference
3665               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
3666               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
3667               nodeSet.addTuple(inFlowTuple);
3668             } else {
3669               // TODO
3670               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
3671               System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
3672               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
3673                 FlowNode inFlowNode = (FlowNode) iterator2.next();
3674                 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
3675                   nodeSet.addTupleSet(baseNodeSet);
3676                 }
3677               }
3678             }
3679           }
3680         }
3681
3682       }
3683
3684       // analyze parameter flows
3685
3686       if (min.numArgs() > 0) {
3687
3688         int offset;
3689         if (min.getMethod().isStatic()) {
3690           offset = 0;
3691         } else {
3692           offset = 1;
3693         }
3694
3695         for (int i = 0; i < min.numArgs(); i++) {
3696           ExpressionNode en = min.getArg(i);
3697           int idx = i + offset;
3698           NodeTupleSet argTupleSet = new NodeTupleSet();
3699           analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false);
3700           // if argument is liternal node, argTuple is set to NULL
3701
3702           NTuple<Descriptor> argTuple = new NTuple<Descriptor>();
3703           System.out.println("-argTupleSet=" + argTupleSet + "  from en=" + en.printNode(0));
3704           if (argTupleSet.size() > 1) {
3705             NTuple<Descriptor> interTuple =
3706                 getFlowGraph(md).createIntermediateNode().getDescTuple();
3707             for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
3708               NTuple<Descriptor> tuple = idxIter.next();
3709               addFlowGraphEdge(md, tuple, interTuple);
3710             }
3711             argTuple = interTuple;
3712           } else if (argTupleSet.size() == 1) {
3713             argTuple = argTupleSet.iterator().next();
3714           } else {
3715             argTuple = new NTuple<Descriptor>();
3716           }
3717
3718           if (argTuple.size() != 0) {
3719             addArgIdxMap(min, idx, argTuple);
3720           }
3721           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
3722           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
3723               || calleeMethodDesc.getModifiers().isNative()) {
3724             addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
3725             nodeSet.addTupleSet(argTupleSet);
3726           }
3727         }
3728
3729       }
3730
3731       // propagateFlowsFromCallee(min, md, min.getMethod());
3732
3733       System.out.println("min nodeSet=" + nodeSet);
3734     }
3735
3736   }
3737
3738   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
3739     // return true if inNode has in-flows to nodeSet
3740
3741     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
3742     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
3743     System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
3744
3745     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
3746       FlowNode fn = (FlowNode) iterator.next();
3747       if (nodeSet.contains(fn)) {
3748         return true;
3749       }
3750     }
3751     return false;
3752   }
3753
3754   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
3755     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
3756   }
3757
3758   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
3759                                                                                         * NodeTupleSet
3760                                                                                         * tupleSet
3761                                                                                         */) {
3762     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
3763     if (mapIdxToTuple == null) {
3764       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
3765       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
3766     }
3767     mapIdxToTuple.put(new Integer(idx), argTuple);
3768   }
3769
3770   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
3771
3772   }
3773
3774   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
3775       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
3776
3777     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
3778     NTuple<Descriptor> base =
3779         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
3780
3781     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
3782     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
3783
3784     if (isLHS) {
3785       // need to create an edge from idx to array
3786       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
3787         NTuple<Descriptor> idxTuple = idxIter.next();
3788         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
3789           NTuple<Descriptor> arrTuple = arrIter.next();
3790           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
3791         }
3792       }
3793
3794       nodeSet.addTupleSet(expNodeTupleSet);
3795     } else {
3796       nodeSet.addTupleSet(expNodeTupleSet);
3797       nodeSet.addTupleSet(idxNodeTupleSet);
3798     }
3799   }
3800
3801   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
3802       CreateObjectNode en) {
3803     // TODO Auto-generated method stub
3804
3805   }
3806
3807   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
3808       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3809
3810     NodeTupleSet leftOpSet = new NodeTupleSet();
3811     NodeTupleSet rightOpSet = new NodeTupleSet();
3812
3813     // left operand
3814     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
3815         false);
3816
3817     if (on.getRight() != null) {
3818       // right operand
3819       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
3820           implicitFlowTupleSet, false);
3821     }
3822
3823     Operation op = on.getOp();
3824
3825     switch (op.getOp()) {
3826
3827     case Operation.UNARYPLUS:
3828     case Operation.UNARYMINUS:
3829     case Operation.LOGIC_NOT:
3830       // single operand
3831       nodeSet.addTupleSet(leftOpSet);
3832       break;
3833
3834     case Operation.LOGIC_OR:
3835     case Operation.LOGIC_AND:
3836     case Operation.COMP:
3837     case Operation.BIT_OR:
3838     case Operation.BIT_XOR:
3839     case Operation.BIT_AND:
3840     case Operation.ISAVAILABLE:
3841     case Operation.EQUAL:
3842     case Operation.NOTEQUAL:
3843     case Operation.LT:
3844     case Operation.GT:
3845     case Operation.LTE:
3846     case Operation.GTE:
3847     case Operation.ADD:
3848     case Operation.SUB:
3849     case Operation.MULT:
3850     case Operation.DIV:
3851     case Operation.MOD:
3852     case Operation.LEFTSHIFT:
3853     case Operation.RIGHTSHIFT:
3854     case Operation.URIGHTSHIFT:
3855
3856       // there are two operands
3857       nodeSet.addTupleSet(leftOpSet);
3858       nodeSet.addTupleSet(rightOpSet);
3859       break;
3860
3861     default:
3862       throw new Error(op.toString());
3863     }
3864
3865   }
3866
3867   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
3868       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
3869
3870     // System.out.println("analyzeFlowNameNode=" + nn.printNode(0));
3871
3872     if (base == null) {
3873       base = new NTuple<Descriptor>();
3874     }
3875
3876     NameDescriptor nd = nn.getName();
3877
3878     if (nd.getBase() != null) {
3879       base =
3880           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
3881               implicitFlowTupleSet, false);
3882       if (base == null) {
3883         // base node has the top location
3884         return base;
3885       }
3886     } else {
3887       String varname = nd.toString();
3888       if (varname.equals("this")) {
3889         // 'this' itself!
3890         base.add(md.getThis());
3891         return base;
3892       }
3893
3894       Descriptor d = (Descriptor) nametable.get(varname);
3895
3896       if (d instanceof VarDescriptor) {
3897         VarDescriptor vd = (VarDescriptor) d;
3898         base.add(vd);
3899       } else if (d instanceof FieldDescriptor) {
3900         // the type of field descriptor has a location!
3901         FieldDescriptor fd = (FieldDescriptor) d;
3902         if (fd.isStatic()) {
3903           if (fd.isFinal()) {
3904             // if it is 'static final', no need to have flow node for the TOP
3905             // location
3906             return null;
3907           } else {
3908             // if 'static', assign the default GLOBAL LOCATION to the first
3909             // element of the tuple
3910             base.add(GLOBALDESC);
3911           }
3912         } else {
3913           // the location of field access starts from this, followed by field
3914           // location
3915           base.add(md.getThis());
3916         }
3917
3918         base.add(fd);
3919       } else if (d == null) {
3920         // access static field
3921         base.add(GLOBALDESC);
3922         base.add(nn.getField());
3923         return base;
3924
3925         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
3926         //
3927         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
3928         // String globalLocId = localLattice.getGlobalLoc();
3929         // if (globalLocId == null) {
3930         // throw new
3931         // Error("Method lattice does not define global variable location at "
3932         // + generateErrorMessage(md.getClassDesc(), nn));
3933         // }
3934         // loc.addLocation(new Location(md, globalLocId));
3935         //
3936         // Location fieldLoc = (Location) fd.getType().getExtension();
3937         // loc.addLocation(fieldLoc);
3938         //
3939         // return loc;
3940
3941       }
3942     }
3943     getFlowGraph(md).createNewFlowNode(base);
3944
3945     return base;
3946
3947   }
3948
3949   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
3950       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3951       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
3952
3953     ExpressionNode left = fan.getExpression();
3954     TypeDescriptor ltd = left.getType();
3955     FieldDescriptor fd = fan.getField();
3956
3957     String varName = null;
3958     if (left.kind() == Kind.NameNode) {
3959       NameDescriptor nd = ((NameNode) left).getName();
3960       varName = nd.toString();
3961     }
3962
3963     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
3964       // using a class name directly or access using this
3965       if (fd.isStatic() && fd.isFinal()) {
3966         return null;
3967       }
3968     }
3969
3970     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
3971
3972     if (left instanceof ArrayAccessNode) {
3973
3974       ArrayAccessNode aan = (ArrayAccessNode) left;
3975       left = aan.getExpression();
3976       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
3977           implicitFlowTupleSet, isLHS);
3978
3979       nodeSet.addTupleSet(idxNodeTupleSet);
3980     }
3981     base =
3982         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
3983
3984     if (base == null) {
3985       // in this case, field is TOP location
3986       return null;
3987     } else {
3988
3989       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
3990
3991       if (!left.getType().isPrimitive()) {
3992
3993         if (!fd.getSymbol().equals("length")) {
3994           // array.length access, just have the location of the array
3995           flowFieldTuple.add(fd);
3996           nodeSet.removeTuple(base);
3997         }
3998
3999       }
4000       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
4001
4002       if (isLHS) {
4003         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
4004           NTuple<Descriptor> idxTuple = idxIter.next();
4005           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
4006         }
4007       }
4008       return flowFieldTuple;
4009
4010     }
4011
4012   }
4013
4014   private void debug_printTreeNode(TreeNode tn) {
4015
4016     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
4017
4018   }
4019
4020   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
4021       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4022       NodeTupleSet implicitFlowTupleSet) {
4023
4024     NodeTupleSet nodeSetRHS = new NodeTupleSet();
4025     NodeTupleSet nodeSetLHS = new NodeTupleSet();
4026
4027     boolean postinc = true;
4028     if (an.getOperation().getBaseOp() == null
4029         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
4030             .getBaseOp().getOp() != Operation.POSTDEC)) {
4031       postinc = false;
4032     }
4033     // if LHS is array access node, need to capture value flows between an array
4034     // and its index value
4035     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
4036         true);
4037
4038     if (!postinc) {
4039       // analyze value flows of rhs expression
4040       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
4041           false);
4042
4043       // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
4044       // System.out.println("-nodeSetLHS=" + nodeSetLHS);
4045       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
4046       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4047       // System.out.println("-");
4048
4049       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
4050         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
4051
4052         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
4053           NTuple<Descriptor> fromTuple = iter.next();
4054           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4055             NTuple<Descriptor> toTuple = iter2.next();
4056             addFlowGraphEdge(md, fromTuple, toTuple);
4057           }
4058         }
4059       }
4060
4061       // creates edges from RHS to LHS
4062       NTuple<Descriptor> interTuple = null;
4063       if (nodeSetRHS.size() > 1) {
4064         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4065       }
4066
4067       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
4068         NTuple<Descriptor> fromTuple = iter.next();
4069         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4070           NTuple<Descriptor> toTuple = iter2.next();
4071           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
4072         }
4073       }
4074
4075       // creates edges from implicitFlowTupleSet to LHS
4076       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4077         NTuple<Descriptor> fromTuple = iter.next();
4078         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4079           NTuple<Descriptor> toTuple = iter2.next();
4080           addFlowGraphEdge(md, fromTuple, toTuple);
4081         }
4082       }
4083
4084     } else {
4085       // postinc case
4086
4087       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4088         NTuple<Descriptor> tuple = iter2.next();
4089         addFlowGraphEdge(md, tuple, tuple);
4090       }
4091
4092       // creates edges from implicitFlowTupleSet to LHS
4093       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4094         NTuple<Descriptor> fromTuple = iter.next();
4095         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4096           NTuple<Descriptor> toTuple = iter2.next();
4097           addFlowGraphEdge(md, fromTuple, toTuple);
4098         }
4099       }
4100
4101     }
4102
4103     if (nodeSet != null) {
4104       nodeSet.addTupleSet(nodeSetLHS);
4105     }
4106   }
4107
4108   public FlowGraph getFlowGraph(MethodDescriptor md) {
4109     return mapMethodDescriptorToFlowGraph.get(md);
4110   }
4111
4112   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
4113       NTuple<Descriptor> to) {
4114     FlowGraph graph = getFlowGraph(md);
4115     graph.addValueFlowEdge(from, to);
4116     return true;
4117   }
4118
4119   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
4120       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
4121
4122     FlowGraph graph = getFlowGraph(md);
4123
4124     if (inter != null) {
4125       graph.addValueFlowEdge(from, inter);
4126       graph.addValueFlowEdge(inter, to);
4127     } else {
4128       graph.addValueFlowEdge(from, to);
4129     }
4130
4131   }
4132
4133   public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
4134       SSJavaLattice<String> locOrder, String nameSuffix) {
4135     writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
4136   }
4137
4138   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
4139       HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
4140
4141     String fileName = "lattice_";
4142     if (md != null) {
4143       fileName +=
4144           cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
4145     } else {
4146       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
4147     }
4148
4149     fileName += nameSuffix;
4150
4151     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
4152
4153     Set<String> addedLocSet = new HashSet<String>();
4154
4155     if (pairSet.size() > 0) {
4156       try {
4157         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
4158
4159         bw.write("digraph " + fileName + " {\n");
4160
4161         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
4162           // pair is in the form of <higher, lower>
4163           Pair<String, String> pair = (Pair<String, String>) iterator.next();
4164
4165           String highLocId = pair.getFirst();
4166           String lowLocId = pair.getSecond();
4167
4168           if (!addedLocSet.contains(highLocId)) {
4169             addedLocSet.add(highLocId);
4170             drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
4171           }
4172
4173           if (!addedLocSet.contains(lowLocId)) {
4174             addedLocSet.add(lowLocId);
4175             drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
4176           }
4177
4178           bw.write(highLocId + " -> " + lowLocId + ";\n");
4179         }
4180         bw.write("}\n");
4181         bw.close();
4182
4183       } catch (IOException e) {
4184         e.printStackTrace();
4185       }
4186
4187     }
4188
4189   }
4190
4191   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
4192     String str = "";
4193     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
4194       HNode merged = (HNode) iterator.next();
4195       if (merged.isMergeNode()) {
4196         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
4197       } else {
4198         str += " " + merged.getName();
4199       }
4200     }
4201     return str;
4202   }
4203
4204   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
4205       String locName) throws IOException {
4206
4207     HNode node = graph.getHNode(locName);
4208
4209     if (node == null) {
4210       return;
4211     }
4212
4213     String prettyStr;
4214     if (lattice.isSharedLoc(locName)) {
4215       prettyStr = locName + "*";
4216     } else {
4217       prettyStr = locName;
4218     }
4219
4220     if (node.isMergeNode()) {
4221       Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
4222       prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
4223     }
4224     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
4225   }
4226
4227   public void _debug_printGraph() {
4228     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
4229
4230     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
4231       MethodDescriptor md = (MethodDescriptor) iterator.next();
4232       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
4233       try {
4234         fg.writeGraph();
4235       } catch (IOException e) {
4236         e.printStackTrace();
4237       }
4238     }
4239
4240   }
4241
4242 }
4243
4244 class CyclicFlowException extends Exception {
4245
4246 }
4247
4248 class InterDescriptor extends Descriptor {
4249
4250   public InterDescriptor(String name) {
4251     super(name);
4252   }
4253
4254 }