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