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