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