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.TypeUtil;
  31 import IR.VarDescriptor;
  32 import IR.Tree.ArrayAccessNode;
  33 import IR.Tree.AssignmentNode;
  34 import IR.Tree.BlockExpressionNode;
  35 import IR.Tree.BlockNode;
  36 import IR.Tree.BlockStatementNode;
  37 import IR.Tree.CastNode;
  38 import IR.Tree.CreateObjectNode;
  39 import IR.Tree.DeclarationNode;
  40 import IR.Tree.ExpressionNode;
  41 import IR.Tree.FieldAccessNode;
  42 import IR.Tree.IfStatementNode;
  43 import IR.Tree.Kind;
  44 import IR.Tree.LiteralNode;
  45 import IR.Tree.LoopNode;
  46 import IR.Tree.MethodInvokeNode;
  47 import IR.Tree.NameNode;
  48 import IR.Tree.OpNode;
  49 import IR.Tree.ReturnNode;
  50 import IR.Tree.SubBlockNode;
  51 import IR.Tree.SwitchBlockNode;
  52 import IR.Tree.SwitchStatementNode;
  53 import IR.Tree.TertiaryNode;
  54 import IR.Tree.TreeNode;
  55 import Util.Pair;
  56
  57 public class LocationInference {
  58
  59   static int COUNT = 0;
  60
  61   State state;
  62   SSJavaAnalysis ssjava;
  63   TypeUtil tu;
  64
  65   List<ClassDescriptor> temp_toanalyzeList;
  66   List<MethodDescriptor> temp_toanalyzeMethodList;
  67   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  68
  69   LinkedList<MethodDescriptor> toanalyze_methodDescList;
  70   Set<ClassDescriptor> toanalyze_classDescSet;
  71
  72   // InheritanceTree<ClassDescriptor> inheritanceTree;
  73
  74   // map a method descriptor to its set of parameter descriptors
  75   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  76
  77   // keep current descriptors to visit in fixed-point interprocedural analysis,
  78   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  79
  80   // map a class descriptor to a field lattice
  81   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  82
  83   // map a method descriptor to a method lattice
  84   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  85
  86   // map a method/class descriptor to a hierarchy graph
  87   private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
  88
  89   // map a method/class descriptor to a skeleton hierarchy graph
  90   private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
  91
  92   private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
  93
  94   // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
  95   private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
  96
  97   // map a descriptor to a simple lattice
  98   private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
  99
 100   // map a method descriptor to the set of method invocation nodes which are
 101   // invoked by the method descriptor
 102   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
 103
 104   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
 105
 106   private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
 107
 108   private Map<MethodInvokeNode, Set<NTuple<Location>>> mapMethodInvokeNodeToPCLocTupleSet;
 109
 110   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
 111
 112   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
 113
 114   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
 115
 116   private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
 117
 118   private Map<String, Vector<String>> mapFileNameToLineVector;
 119
 120   private Map<Descriptor, Integer> mapDescToDefinitionLine;
 121
 122   private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
 123
 124   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescToMethodInvokeNodeSet;
 125
 126   // maps a method descriptor to a sub global flow graph that captures all value flows caused by the
 127   // set of callees reachable from the method
 128   private Map<MethodDescriptor, GlobalFlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
 129
 130   private Map<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>> mapMethodInvokeNodeToMapCallerArgToCalleeArg;
 131
 132   private Map<MethodDescriptor, Boolean> mapMethodDescriptorToCompositeReturnCase;
 133
 134   private Map<MethodDescriptor, MethodDescriptor> mapMethodDescToHighestOverriddenMethodDesc;
 135
 136   private Map<MethodDescriptor, Set<MethodDescriptor>> mapHighestOverriddenMethodDescToMethodDescSet;
 137
 138   private Map<MethodDescriptor, NTuple<Descriptor>> mapHighestOverriddenMethodDescToReturnLocTuple;
 139
 140   private Map<MethodDescriptor, NTuple<Descriptor>> mapHighestOverriddenMethodDescToPCLocTuple;
 141
 142   private Map<MethodDescriptor, Set<NTuple<Descriptor>>> mapHighestOverriddenMethodDescToSetLowerThanPCLoc;
 143
 144   public static final String GLOBALLOC = "GLOBALLOC";
 145
 146   public static final String INTERLOC = "INTERLOC";
 147
 148   public static final String PCLOC = "_PCLOC_";
 149
 150   public static final String RLOC = "_RLOC_";
 151
 152   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
 153
 154   public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP);
 155
 156   public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM);
 157
 158   public static final Descriptor RETURNLOC = new NameDescriptor(RLOC);
 159
 160   public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL");
 161
 162   public static final HNode TOPHNODE = new HNode(TOPDESC);
 163
 164   public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC);
 165
 166   public static String newline = System.getProperty("line.separator");
 167
 168   LocationInfo curMethodInfo;
 169
 170   private boolean hasChanges = false;
 171
 172   boolean debug = true;
 173
 174   public static int locSeed = 0;
 175
 176   private Stack<String> arrayAccessNodeStack;
 177
 178   private ClassDescriptor rootClassDescriptor;
 179
 180   private BuildLattice buildLattice;
 181
 182   public LocationInference(SSJavaAnalysis ssjava, State state, TypeUtil tu) {
 183     this.ssjava = ssjava;
 184     this.state = state;
 185     this.tu = tu;
 186     this.toanalyze_classDescSet = new HashSet<ClassDescriptor>();
 187     this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
 188     this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 189     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
 190     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
 191     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
 192     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 193     this.mapMethodDescriptorToMethodInvokeNodeSet =
 194         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 195     this.mapMethodInvokeNodeToArgIdxMap =
 196         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
 197     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
 198     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 199     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 200
 201     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
 202     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
 203     this.mapMethodDescToParamNodeFlowsToReturnValue =
 204         new HashMap<MethodDescriptor, Set<FlowNode>>();
 205
 206     this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 207     this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
 208
 209     this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 210     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 211     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 212
 213     this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
 214
 215     this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
 216
 217     this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
 218
 219     this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
 220         new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
 221
 222     this.mapMethodInvokeNodeToPCLocTupleSet =
 223         new HashMap<MethodInvokeNode, Set<NTuple<Location>>>();
 224
 225     this.arrayAccessNodeStack = new Stack<String>();
 226
 227     this.mapMethodDescToMethodInvokeNodeSet =
 228         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 229
 230     this.mapMethodDescriptorToCompositeReturnCase = new HashMap<MethodDescriptor, Boolean>();
 231
 232     mapMethodDescToHighestOverriddenMethodDesc = new HashMap<MethodDescriptor, MethodDescriptor>();
 233
 234     mapHighestOverriddenMethodDescToSetLowerThanPCLoc =
 235         new HashMap<MethodDescriptor, Set<NTuple<Descriptor>>>();
 236
 237     mapHighestOverriddenMethodDescToMethodDescSet =
 238         new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 239
 240     mapHighestOverriddenMethodDescToReturnLocTuple =
 241         new HashMap<MethodDescriptor, NTuple<Descriptor>>();
 242
 243     mapHighestOverriddenMethodDescToPCLocTuple =
 244         new HashMap<MethodDescriptor, NTuple<Descriptor>>();
 245
 246     this.buildLattice = new BuildLattice(this);
 247
 248   }
 249
 250   public void setupToAnalyze() {
 251     SymbolTable classtable = state.getClassSymbolTable();
 252     temp_toanalyzeList.clear();
 253     temp_toanalyzeList.addAll(classtable.getValueSet());
 254     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 255     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 256     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 257     // }
 258     // });
 259   }
 260
 261   public void setupToAnalazeMethod(ClassDescriptor cd) {
 262
 263     SymbolTable methodtable = cd.getMethodTable();
 264     temp_toanalyzeMethodList.clear();
 265     temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
 266     Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 267       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 268         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 269       }
 270     });
 271   }
 272
 273   public boolean toAnalyzeMethodIsEmpty() {
 274     return temp_toanalyzeMethodList.isEmpty();
 275   }
 276
 277   public boolean toAnalyzeIsEmpty() {
 278     return temp_toanalyzeList.isEmpty();
 279   }
 280
 281   public ClassDescriptor toAnalyzeNext() {
 282     return temp_toanalyzeList.remove(0);
 283   }
 284
 285   public MethodDescriptor toAnalyzeMethodNext() {
 286     return temp_toanalyzeMethodList.remove(0);
 287   }
 288
 289   public void inference() {
 290
 291     ssjava.init();
 292
 293     // construct value flow graph
 294     constructFlowGraph();
 295
 296     constructGlobalFlowGraph();
 297
 298     checkReturnNodes();
 299
 300     assignCompositeLocation();
 301     updateFlowGraph();
 302     calculateExtraLocations();
 303     addAdditionalOrderingConstraints();
 304
 305     _debug_writeFlowGraph();
 306
 307     buildInheritanceTree();
 308     calculateReturnPCLocInheritance();
 309
 310     constructHierarchyGraph();
 311
 312     addInheritanceConstraintsToHierarchyGraph();
 313
 314     debug_writeHierarchyDotFiles();
 315
 316     simplifyHierarchyGraph();
 317
 318     debug_writeSimpleHierarchyDotFiles();
 319
 320     constructSkeletonHierarchyGraph();
 321
 322     debug_writeSkeletonHierarchyDotFiles();
 323
 324     insertCombinationNodes();
 325
 326     debug_writeSkeletonCombinationHierarchyDotFiles();
 327
 328     buildLatticeInheritanceTree();
 329     // buildLattice();
 330
 331     debug_writeLattices();
 332
 333     updateCompositeLocationAssignments();
 334
 335     generateMethodSummary();
 336
 337     generateAnnoatedCode();
 338
 339     for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) {
 340       ClassDescriptor cd = (ClassDescriptor) iterator.next();
 341       SSJavaLattice<String> lattice = getLattice(cd);
 342       HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(cd);
 343       // System.out.println("~~~\t" + cd + "\t" + lattice.getKeySet().size() + "\t"
 344       // + hg.getNodeSet().size());
 345     }
 346
 347     for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) {
 348       MethodDescriptor md = (MethodDescriptor) iterator.next();
 349       SSJavaLattice<String> locOrder = getLattice(md);
 350       // writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md));
 351       HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(md);
 352       // System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t"
 353       // + locOrder.getKeySet().size() + "\t" + hg.getNodeSet().size());
 354     }
 355
 356     System.exit(0);
 357
 358   }
 359
 360   private void calculateReturnPCLocInheritance() {
 361     calculateHighestPCLocInheritance();
 362     calculateLowestReturnLocInheritance();
 363     updateFlowGraphPCReturnLocInheritance();
 364   }
 365
 366   private void updateFlowGraphPCReturnLocInheritance() {
 367     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 368     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 369       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 370
 371       if (mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc).size() == 1) {
 372         continue;
 373       }
 374
 375       Set<MethodDescriptor> methodDescSet =
 376           mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 377
 378       NTuple<Descriptor> highestPCLoc =
 379           mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc);
 380
 381       NTuple<Descriptor> highestRETURNLoc =
 382           mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc);
 383
 384       System.out.println("---highestMethodDesc=" + highestMethodDesc);
 385
 386       for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 387         MethodDescriptor md = (MethodDescriptor) iterator2.next();
 388         FlowGraph flowGraph = getFlowGraph(md);
 389
 390         MethodSummary summary = getMethodSummary(md);
 391         CompositeLocation curPCLoc = summary.getPCLoc();
 392
 393         // update PCLOC
 394         if (highestPCLoc != null) {
 395           // handle the case that PCLOC is started with 'this'...
 396           NTuple<Descriptor> newPCLoc = new NTuple<Descriptor>();
 397           if (highestPCLoc.size() == 1) {
 398             newPCLoc.add(highestPCLoc.get(0));
 399           } else {
 400             newPCLoc.add(md.getThis());
 401             newPCLoc.add(highestPCLoc.get(1));
 402           }
 403
 404           FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple()));
 405           pcFlowNode.setBaseTuple(newPCLoc);
 406
 407           CompositeLocation newPCLocCompLoc =
 408               new CompositeLocation(translateToLocTuple(md, newPCLoc));
 409           summary.setPCLoc(newPCLocCompLoc);
 410         } else {
 411           // need to remove PCLOC if the overridden method defines it
 412           if (curPCLoc != null && !curPCLoc.get(0).isTop()) {
 413             System.out.println("md=" + md + "    curPCLoc=" + curPCLoc);
 414             FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple()));
 415             System.out.println("#######REMOVE PCLOCNODE=" + pcFlowNode);
 416             flowGraph.removeNode(pcFlowNode);
 417           }
 418         }
 419
 420         // need to update RETURNLOC
 421         if (highestRETURNLoc != null) {
 422
 423           CompositeLocation curRETURNLoc = summary.getRETURNLoc();
 424           System.out.println("curRETURNLoc=" + curRETURNLoc);
 425
 426           // handle the case that RETURNLOC is started with 'this'...
 427           NTuple<Descriptor> newRETURNLoc = new NTuple<Descriptor>();
 428           if (highestRETURNLoc.size() == 1) {
 429             newRETURNLoc.add(highestRETURNLoc.get(0));
 430           } else {
 431             newRETURNLoc.add(md.getThis());
 432             newRETURNLoc.add(highestRETURNLoc.get(1));
 433           }
 434
 435           FlowNode returnFlowNode =
 436               flowGraph.getFlowNode(translateToDescTuple(curRETURNLoc.getTuple()));
 437           returnFlowNode.setBaseTuple(newRETURNLoc);
 438
 439           CompositeLocation newRETURNLocCompLoc =
 440               new CompositeLocation(translateToLocTuple(md, newRETURNLoc));
 441           summary.setPCLoc(newRETURNLocCompLoc);
 442           System.out.println("md=" + md + "###newRETURNLocCompLoc=" + newRETURNLocCompLoc);
 443
 444         }
 445
 446       }
 447     }
 448   }
 449
 450   private void calculateHighestPCLocInheritance() {
 451
 452     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 453     next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 454       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 455
 456       NTuple<Descriptor> tempTuple = null;
 457
 458       if (getMethodSummary(highestMethodDesc).getPCLoc() != null) {
 459
 460         Set<MethodDescriptor> methodDescSet =
 461             mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 462
 463         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 464           MethodDescriptor md = (MethodDescriptor) iterator2.next();
 465
 466           FlowGraph flowGraph = getFlowGraph(md);
 467           if (flowGraph == null) {
 468             continue;
 469           }
 470           Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
 471           System.out.println("###md=" + md + "   paramNodeSet=" + paramNodeSet);
 472
 473           CompositeLocation pcLOC = getMethodSummary(md).getPCLoc();
 474
 475           if (!pcLOC.get(0).isTop()) {
 476             if (pcLOC.getSize() == 1) {
 477               // return location is not started with 'this'
 478               // check whether the return location is lower than all parameters.
 479
 480               FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple()));
 481
 482               int count = 0;
 483               for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) {
 484                 FlowNode paramNode = (FlowNode) iterator3.next();
 485                 if (flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1))
 486                     .contains(paramNode)) {
 487                   count++;
 488                   System.out.println("-------" + pcFlowNode + " -> " + paramNode);
 489                 }
 490               }
 491
 492               int offset = 0;
 493               if (!md.isStatic()) {
 494                 offset = 1;
 495               }
 496
 497               NTuple<Descriptor> rTuple = new NTuple<Descriptor>();
 498               rTuple.add(pcLOC.get(0).getLocDescriptor());
 499               if (count == (md.numParameters() + offset)) {
 500                 // means return loc is lower than a composite location starting with 'this'
 501                 mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, rTuple);
 502               } else {
 503                 if (tempTuple == null) {
 504                   tempTuple = rTuple;
 505                 }
 506               }
 507             } else {
 508               // if the current overridden method has a composite pc loc(size>1)
 509               // and it has not yet finalized the pc location,
 510               // the highest overridden method would have the composite pc location starting with
 511               // 'this'
 512               NTuple<Descriptor> rTuple = new NTuple<Descriptor>();
 513               for (int i = 0; i < pcLOC.getSize(); i++) {
 514                 rTuple.add(pcLOC.get(i).getLocDescriptor());
 515               }
 516               tempTuple = rTuple;
 517             }
 518           } else {
 519             mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc);
 520             System.out.println("highest=" + highestMethodDesc + "  HIGHEST PCLOC="
 521                 + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc));
 522             continue next;
 523           }
 524         }
 525
 526       }
 527
 528       if (!mapHighestOverriddenMethodDescToPCLocTuple.containsKey(highestMethodDesc)
 529           && tempTuple != null) {
 530         mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, tempTuple);
 531       }
 532       System.out.println("highest=" + highestMethodDesc + "  HIGHEST PCLOC="
 533           + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc));
 534     }
 535
 536   }
 537
 538   private void calculateLowestReturnLocInheritance() {
 539
 540     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 541     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 542       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 543
 544       NTuple<Descriptor> tempTuple = null;
 545
 546       if (getMethodSummary(highestMethodDesc).getRETURNLoc() != null) {
 547         Set<MethodDescriptor> methodDescSet =
 548             mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 549         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 550           MethodDescriptor md = (MethodDescriptor) iterator2.next();
 551
 552           FlowGraph flowGraph = getFlowGraph(md);
 553           Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
 554           System.out.println("###md=" + md + "   paramNodeSet=" + paramNodeSet);
 555
 556           CompositeLocation returnLoc = getMethodSummary(md).getRETURNLoc();
 557           if (returnLoc.getSize() == 1) {
 558             // return location is not started with 'this'
 559             // check whether the return location is lower than all parameters.
 560
 561             FlowNode returnFlowNode =
 562                 flowGraph.getFlowNode(translateToDescTuple(returnLoc.getTuple()));
 563
 564             int count = 0;
 565             for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) {
 566               FlowNode paramNode = (FlowNode) iterator3.next();
 567               if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1))
 568                   .contains(returnFlowNode)) {
 569                 count++;
 570                 System.out.println("-------" + paramNode + " -> " + returnFlowNode);
 571               }
 572             }
 573
 574             int offset = 0;
 575             if (!md.isStatic()) {
 576               offset = 1;
 577             }
 578
 579             NTuple<Descriptor> rTuple = new NTuple<Descriptor>();
 580             rTuple.add(returnLoc.get(0).getLocDescriptor());
 581             if (count == (md.numParameters() + offset)) {
 582               // means return loc is lower than a composite location starting with 'this'
 583               mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, rTuple);
 584             } else {
 585               if (tempTuple == null) {
 586                 tempTuple = rTuple;
 587               }
 588             }
 589           } else {
 590             // if the current overridden method has a composite return loc(size>1)
 591             // and it has not yet finalized the return location
 592             // the highest overridden method has the composite return location starting with
 593             // 'this'
 594             NTuple<Descriptor> rTuple = new NTuple<Descriptor>();
 595             for (int i = 0; i < returnLoc.getSize(); i++) {
 596               rTuple.add(returnLoc.get(i).getLocDescriptor());
 597             }
 598             tempTuple = rTuple;
 599           }
 600
 601         }
 602
 603       }
 604
 605       if (!mapHighestOverriddenMethodDescToReturnLocTuple.containsKey(highestMethodDesc)
 606           && tempTuple != null) {
 607         mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, tempTuple);
 608       }
 609       System.out.println("highest=" + highestMethodDesc + "  rTuple="
 610           + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc));
 611     }
 612
 613   }
 614
 615   private void addMapHighestMethodDescToMethodDesc(MethodDescriptor highest, MethodDescriptor md) {
 616     if (!mapHighestOverriddenMethodDescToMethodDescSet.containsKey(highest)) {
 617       mapHighestOverriddenMethodDescToMethodDescSet.put(highest, new HashSet<MethodDescriptor>());
 618     }
 619     mapHighestOverriddenMethodDescToMethodDescSet.get(highest).add(md);
 620   }
 621
 622   private void DFSInheritanceTreeCalculatingHighestOverriddenMethod(ClassDescriptor cd) {
 623
 624     // ClassDescriptor cd = node.getData();
 625
 626     for (Iterator iterator = cd.getMethods(); iterator.hasNext();) {
 627       MethodDescriptor md = (MethodDescriptor) iterator.next();
 628       MethodDescriptor highestMethodDesc = getHighestOverriddenMethod(md.getClassDesc(), md);
 629       mapMethodDescToHighestOverriddenMethodDesc.put(md, highestMethodDesc);
 630       addMapHighestMethodDescToMethodDesc(highestMethodDesc, md);
 631
 632     }
 633
 634     // traverse children
 635     Set<ClassDescriptor> children = getDirectSubClasses(cd);
 636     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
 637       ClassDescriptor child = (ClassDescriptor) iterator.next();
 638       DFSInheritanceTreeCalculatingHighestOverriddenMethod(child);
 639     }
 640
 641   }
 642
 643   private MethodDescriptor getHighestOverriddenMethod(ClassDescriptor curClassDesc,
 644       MethodDescriptor curMethodDesc) {
 645
 646     // Node<ClassDescriptor> curNode = inheritanceTree.getTreeNode(curClassDesc);
 647     // Node<ClassDescriptor> parentNode = curNode.getParent();
 648     ClassDescriptor parentClassDesc = curClassDesc.getSuperDesc();
 649
 650     if (parentClassDesc != null) {
 651       if (parentClassDesc.getMethodTable().contains(curMethodDesc.getSymbol())) {
 652         Set<MethodDescriptor> methodDescSet =
 653             parentClassDesc.getMethodTable().getSet(curMethodDesc.getSymbol());
 654         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
 655           MethodDescriptor md = (MethodDescriptor) iterator.next();
 656           if (md.matches(curMethodDesc)) {
 657             return getHighestOverriddenMethod(parentClassDesc, md);
 658           }
 659         }
 660       }
 661       // traverse to the parent!
 662       return getHighestOverriddenMethod(parentClassDesc, curMethodDesc);
 663     }
 664     return curMethodDesc;
 665   }
 666
 667   private void buildInheritanceTree() {
 668
 669     DFSInheritanceTreeCalculatingHighestOverriddenMethod(rootClassDescriptor);
 670
 671   }
 672
 673   private void addInheritanceConstraintsToHierarchyGraph() {
 674
 675     // DFS the inheritance tree and propagates nodes/edges of parent to child
 676
 677     // Node<ClassDescriptor> rootNode = inheritanceTree.getRootNode();
 678     DFSInheritanceTree(rootClassDescriptor);
 679
 680   }
 681
 682   private void DFSInheritanceTree(ClassDescriptor parentClassDescriptor) {
 683
 684     // ClassDescriptor parentClassDescriptor = parentNode.getData();
 685
 686     Set<ClassDescriptor> children = getDirectSubClasses(parentClassDescriptor);
 687     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
 688       ClassDescriptor childClassDescriptor = (ClassDescriptor) iterator.next();
 689
 690       HierarchyGraph parentGraph = getHierarchyGraph(parentClassDescriptor);
 691       HierarchyGraph childGraph = getHierarchyGraph(childClassDescriptor);
 692
 693       // copies extra information from the parent hierarchy graph
 694       Map<HNode, Set<HNode>> parentMergeNodeMap = parentGraph.getMapHNodetoMergeSet();
 695       Map<HNode, Set<HNode>> childMergeNodeMap = childGraph.getMapHNodetoMergeSet();
 696
 697       Set<HNode> keySet = parentMergeNodeMap.keySet();
 698       for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
 699         HNode parentKey = (HNode) iterator2.next();
 700         if (!childMergeNodeMap.containsKey(parentKey)) {
 701           childMergeNodeMap.put(parentKey, new HashSet<HNode>());
 702         }
 703         childMergeNodeMap.get(parentKey).addAll(parentMergeNodeMap.get(parentKey));
 704       }
 705
 706       // copies nodes/edges from the parent class...
 707       Set<HNode> parentNodeSet = parentGraph.getNodeSet();
 708       for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) {
 709         HNode parentHNode = (HNode) iterator2.next();
 710
 711         Set<HNode> parentIncomingHNode = parentGraph.getIncomingNodeSet(parentHNode);
 712         Set<HNode> parentOutgoingHNode = parentGraph.getOutgoingNodeSet(parentHNode);
 713
 714         for (Iterator iterator3 = parentIncomingHNode.iterator(); iterator3.hasNext();) {
 715           HNode inHNode = (HNode) iterator3.next();
 716           childGraph.addEdge(inHNode.getDescriptor(), parentHNode.getDescriptor());
 717         }
 718
 719         for (Iterator iterator3 = parentOutgoingHNode.iterator(); iterator3.hasNext();) {
 720           HNode outHNode = (HNode) iterator3.next();
 721           childGraph.addEdge(parentHNode.getDescriptor(), outHNode.getDescriptor());
 722         }
 723
 724       }
 725
 726       // copies nodes/edges from parent methods to overridden methods
 727
 728       for (Iterator iterator3 = childClassDescriptor.getMethods(); iterator3.hasNext();) {
 729         MethodDescriptor childMethodDescriptor = (MethodDescriptor) iterator3.next();
 730
 731         MethodDescriptor parentMethodDesc =
 732             getParentMethodDesc(childMethodDescriptor.getClassDesc(), childMethodDescriptor);
 733
 734         if (parentMethodDesc != null) {
 735
 736           HierarchyGraph parentMethodGraph = getHierarchyGraph(parentMethodDesc);
 737           HierarchyGraph childMethodGraph = getHierarchyGraph(childMethodDescriptor);
 738
 739           // copies extra information from the parent hierarchy graph
 740           Map<HNode, Set<HNode>> parentMethodMergeNodeMap =
 741               parentMethodGraph.getMapHNodetoMergeSet();
 742           Map<HNode, Set<HNode>> childMethodMergeNodeMap = childMethodGraph.getMapHNodetoMergeSet();
 743
 744           Set<HNode> methodKeySet = parentMethodMergeNodeMap.keySet();
 745           for (Iterator iterator2 = methodKeySet.iterator(); iterator2.hasNext();) {
 746             HNode parentKey = (HNode) iterator2.next();
 747             if (!childMethodMergeNodeMap.containsKey(parentKey)) {
 748               childMethodMergeNodeMap.put(parentKey, new HashSet<HNode>());
 749             }
 750             childMethodMergeNodeMap.get(parentKey).addAll(parentMethodMergeNodeMap.get(parentKey));
 751           }
 752
 753           // copies nodes/edges from the parent method...
 754           for (Iterator iterator2 = parentMethodGraph.getNodeSet().iterator(); iterator2.hasNext();) {
 755             HNode parentHNode = (HNode) iterator2.next();
 756
 757             Set<HNode> parentIncomingHNode = parentMethodGraph.getIncomingNodeSet(parentHNode);
 758             Set<HNode> parentOutgoingHNode = parentMethodGraph.getOutgoingNodeSet(parentHNode);
 759
 760             for (Iterator iterator4 = parentIncomingHNode.iterator(); iterator4.hasNext();) {
 761               HNode inHNode = (HNode) iterator4.next();
 762               childMethodGraph.addEdge(inHNode, parentHNode);
 763             }
 764
 765             for (Iterator iterator4 = parentOutgoingHNode.iterator(); iterator4.hasNext();) {
 766               HNode outHNode = (HNode) iterator4.next();
 767               childMethodGraph.addEdge(parentHNode, outHNode);
 768             }
 769
 770           }
 771
 772         }
 773
 774       }
 775
 776       DFSInheritanceTree(childClassDescriptor);
 777     }
 778
 779   }
 780
 781   public MethodDescriptor getParentMethodDesc(ClassDescriptor classDesc, MethodDescriptor methodDesc) {
 782
 783     // Node<ClassDescriptor> childNode = inheritanceTree.getTreeNode(classDesc);
 784     ClassDescriptor parentClassDesc = classDesc.getSuperDesc();
 785     // Node<ClassDescriptor> parentNode = childNode.getParent();
 786
 787     if (parentClassDesc != null) {
 788       // ClassDescriptor parentClassDesc = parentNode.getData();
 789       if (parentClassDesc.getMethodTable().contains(methodDesc.getSymbol())) {
 790         Set<MethodDescriptor> methodDescSet =
 791             parentClassDesc.getMethodTable().getSet(methodDesc.getSymbol());
 792         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
 793           MethodDescriptor md = (MethodDescriptor) iterator.next();
 794           if (md.matches(methodDesc)) {
 795             return md;
 796           }
 797         }
 798       }
 799
 800       // traverse to the parent!
 801       getParentMethodDesc(parentClassDesc, methodDesc);
 802
 803     }
 804
 805     return null;
 806   }
 807
 808   private void checkReturnNodes() {
 809     LinkedList<MethodDescriptor> methodDescList =
 810         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 811
 812     while (!methodDescList.isEmpty()) {
 813       MethodDescriptor md = methodDescList.removeLast();
 814
 815       if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
 816         checkFlowNodeReturnThisField(md);
 817       }
 818       // // in this case, this method will return the composite location that starts with 'this'
 819       // FlowGraph flowGraph = getFlowGraph(md);
 820       // Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
 821       // }
 822
 823     }
 824
 825   }
 826
 827   private void updateFlowGraph() {
 828
 829     LinkedList<MethodDescriptor> methodDescList =
 830         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 831
 832     while (!methodDescList.isEmpty()) {
 833       MethodDescriptor md = methodDescList.removeLast();
 834       if (state.SSJAVADEBUG) {
 835         System.out.println();
 836         System.out.println("SSJAVA: Updating a flow graph: " + md);
 837         propagateFlowsFromCalleesWithNoCompositeLocation(md);
 838       }
 839
 840       Set<FlowNode> nodeSet = getFlowGraph(md).getNodeSet();
 841       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 842         FlowNode flowNode = (FlowNode) iterator.next();
 843         NTuple<Descriptor> descTuple = flowNode.getCurrentDescTuple();
 844         NTuple<Location> locTuple = translateToLocTuple(md, descTuple);
 845         for (int i = 0; i < locTuple.size(); i++) {
 846           Location loc = locTuple.get(i);
 847           if (loc.getDescriptor() instanceof ClassDescriptor) {
 848             toanalyze_classDescSet.add((ClassDescriptor) loc.getDescriptor());
 849           } else if (loc.getDescriptor() instanceof MethodDescriptor) {
 850             toanalyze_classDescSet.add(((MethodDescriptor) loc.getDescriptor()).getClassDesc());
 851           }
 852         }
 853
 854       }
 855
 856     }
 857   }
 858
 859   public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
 860       MethodInvokeNode min) {
 861
 862     if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
 863       mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
 864           new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
 865     }
 866
 867     return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
 868   }
 869
 870   public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
 871       NTuple<Descriptor> calleeParam) {
 872     getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
 873   }
 874
 875   private void assignCompositeLocation() {
 876     calculateGlobalValueFlowCompositeLocation();
 877     translateCompositeLocationAssignmentToFlowGraph();
 878   }
 879
 880   private void translateCompositeLocationAssignmentToFlowGraph() {
 881     System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
 882     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
 883     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
 884   }
 885
 886   private void translateCompositeLocationAssignmentToFlowGraph2() {
 887     System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
 888     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
 889     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
 890   }
 891
 892   private void addAdditionalOrderingConstraints() {
 893     System.out.println("\nSSJAVA: Add addtional ordering constriants:");
 894     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
 895     addAddtionalOrderingConstraints(methodEventLoopDesc);
 896     // calculateReturnHolderLocation();
 897   }
 898
 899   private void calculateReturnHolderLocation() {
 900     LinkedList<MethodDescriptor> methodDescList =
 901         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 902
 903     while (!methodDescList.isEmpty()) {
 904       MethodDescriptor md = methodDescList.removeLast();
 905
 906       FlowGraph fg = getFlowGraph(md);
 907       Set<FlowNode> nodeSet = fg.getNodeSet();
 908       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 909         FlowNode flowNode = (FlowNode) iterator.next();
 910         if (flowNode.isFromHolder()) {
 911           calculateCompositeLocationFromFlowGraph(md, flowNode);
 912         }
 913       }
 914
 915     }
 916   }
 917
 918   private void updateCompositeLocationAssignments() {
 919
 920     LinkedList<MethodDescriptor> methodDescList =
 921         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 922
 923     while (!methodDescList.isEmpty()) {
 924       MethodDescriptor md = methodDescList.removeLast();
 925
 926       // System.out.println("\n#updateCompositeLocationAssignments=" + md);
 927
 928       FlowGraph flowGraph = getFlowGraph(md);
 929
 930       MethodSummary methodSummary = getMethodSummary(md);
 931
 932       Set<FlowNode> nodeSet = flowGraph.getNodeSet();
 933       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 934         FlowNode node = (FlowNode) iterator.next();
 935         System.out.println("-node=" + node + "   node.getDescTuple=" + node.getDescTuple());
 936         if (node.getCompositeLocation() != null) {
 937           CompositeLocation compLoc = node.getCompositeLocation();
 938           CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc);
 939           node.setCompositeLocation(updatedCompLoc);
 940           System.out.println("---updatedCompLoc1=" + updatedCompLoc);
 941         } else {
 942           NTuple<Descriptor> descTuple = node.getDescTuple();
 943           System.out.println("update desc=" + descTuple);
 944           CompositeLocation compLoc = convertToCompositeLocation(md, descTuple);
 945           compLoc = updateCompositeLocation(compLoc);
 946           node.setCompositeLocation(compLoc);
 947           System.out.println("---updatedCompLoc2=" + compLoc);
 948         }
 949
 950         if (node.isDeclaratonNode()) {
 951           Descriptor localVarDesc = node.getDescTuple().get(0);
 952           CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation());
 953           methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc);
 954         }
 955       }
 956
 957       // update PCLOC and RETURNLOC if they have a composite location assignment
 958       if (methodSummary.getRETURNLoc() != null) {
 959         methodSummary.setRETURNLoc(updateCompositeLocation(methodSummary.getRETURNLoc()));
 960       }
 961       if (methodSummary.getPCLoc() != null) {
 962         methodSummary.setPCLoc(updateCompositeLocation(methodSummary.getPCLoc()));
 963       }
 964
 965     }
 966
 967   }
 968
 969   private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) {
 970     CompositeLocation updatedCompLoc = new CompositeLocation();
 971     for (int i = 0; i < compLoc.getSize(); i++) {
 972       Location loc = compLoc.get(i);
 973       String nodeIdentifier = loc.getLocIdentifier();
 974       Descriptor enclosingDesc = loc.getDescriptor();
 975       String locName;
 976       if (!enclosingDesc.equals(GLOBALDESC)) {
 977         LocationSummary locSummary = getLocationSummary(enclosingDesc);
 978         // HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
 979         HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc);
 980         if (scGraph != null) {
 981           HNode curNode = scGraph.getCurrentHNode(nodeIdentifier);
 982           System.out.println("nodeID=" + nodeIdentifier + " curNode=" + curNode
 983               + "  enclosingDesc=" + enclosingDesc);
 984           if (curNode != null) {
 985             nodeIdentifier = curNode.getName();
 986           }
 987         }
 988         locName = locSummary.getLocationName(nodeIdentifier);
 989       } else {
 990         locName = nodeIdentifier;
 991       }
 992       Location updatedLoc = new Location(enclosingDesc, locName);
 993       updatedCompLoc.addLocation(updatedLoc);
 994     }
 995
 996     return updatedCompLoc;
 997   }
 998
 999   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
1000
1001     // System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller="
1002     // + mdCaller);
1003
1004     // First, assign a composite location to a node in the flow graph
1005     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
1006
1007     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1008     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1009         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
1010
1011     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
1012     for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
1013       Location methodLoc = (Location) iterator.next();
1014       if (methodLoc.getDescriptor().equals(mdCaller)) {
1015         CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
1016         assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
1017       }
1018     }
1019
1020     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1021
1022     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
1023     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1024       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1025       // need to translate a composite location that is started with the base
1026       // tuple of 'min'.
1027       translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
1028       MethodDescriptor mdCallee = min.getMethod();
1029       calleeSet.add(mdCallee);
1030
1031     }
1032
1033     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1034       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1035       translateCompositeLocationAssignmentToFlowGraph(callee);
1036     }
1037
1038   }
1039
1040   private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) {
1041
1042     // First, assign a composite location to a node in the flow graph
1043     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
1044
1045     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1046     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1047         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
1048     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
1049
1050     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1051
1052     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
1053     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1054       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1055       MethodDescriptor mdCallee = min.getMethod();
1056       calleeSet.add(mdCallee);
1057
1058       //
1059       // add an additional ordering constraint
1060       // if the first element of a parameter composite location matches 'this' reference,
1061       // the corresponding argument in the caller is required to be higher than the translated
1062       // parameter location in the caller lattice
1063       // TODO
1064       // addOrderingConstraintFromCompLocParamToArg(mdCaller, min);
1065
1066       //
1067       // update return flow nodes in the caller
1068       CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc();
1069       System.out.println("### min=" + min.printNode(0) + "  returnLoc=" + returnLoc);
1070       if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis())
1071           && returnLoc.getSize() > 1) {
1072         System.out.println("###RETURN COMP LOC=" + returnLoc);
1073         NTuple<Location> returnLocTuple = returnLoc.getTuple();
1074         NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1075         System.out.println("###basetuple=" + baseTuple);
1076         NTuple<Descriptor> newReturnTuple = baseTuple.clone();
1077         for (int i = 1; i < returnLocTuple.size(); i++) {
1078           newReturnTuple.add(returnLocTuple.get(i).getLocDescriptor());
1079         }
1080         System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple);
1081
1082         FlowReturnNode holderNode = callerFlowGraph.getFlowReturnNode(min);
1083         NodeTupleSet holderTupleSet =
1084             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), holderNode);
1085
1086         callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple);
1087
1088         // then need to remove old constraints
1089         // TODO SAT
1090         System.out.println("###REMOVE OLD CONSTRAINTS=" + holderNode);
1091         for (Iterator<NTuple<Descriptor>> iter = holderTupleSet.iterator(); iter.hasNext();) {
1092           NTuple<Descriptor> tupleFromHolder = iter.next();
1093           Set<FlowEdge> holderOutEdge = callerFlowGraph.getOutEdgeSet(holderNode);
1094           for (Iterator iterator2 = holderOutEdge.iterator(); iterator2.hasNext();) {
1095             FlowEdge outEdge = (FlowEdge) iterator2.next();
1096             NTuple<Descriptor> toberemovedTuple = outEdge.getEndTuple();
1097             // System.out.println("---remove " + tupleFromHolder + " -> " + toberemovedTuple);
1098             callerFlowGraph.removeEdge(tupleFromHolder, toberemovedTuple);
1099           }
1100         }
1101
1102       } else {
1103         // if the return loc set was empty and later pcloc was connected to the return loc
1104         // need to make sure that return loc reflects to this changes.
1105         FlowReturnNode flowReturnNode = callerFlowGraph.getFlowReturnNode(min);
1106         if (flowReturnNode != null && flowReturnNode.getReturnTupleSet().isEmpty()) {
1107
1108           if (needToUpdateReturnLocHolder(min.getMethod(), flowReturnNode)) {
1109             NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1110             NTuple<Descriptor> newReturnTuple = baseTuple.clone();
1111             flowReturnNode.addTuple(newReturnTuple);
1112           }
1113
1114         }
1115
1116       }
1117
1118     }
1119
1120     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1121       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1122       addAddtionalOrderingConstraints(callee);
1123     }
1124
1125   }
1126
1127   private boolean needToUpdateReturnLocHolder(MethodDescriptor mdCallee,
1128       FlowReturnNode flowReturnNode) {
1129     FlowGraph fg = getFlowGraph(mdCallee);
1130     MethodSummary summary = getMethodSummary(mdCallee);
1131     CompositeLocation returnCompLoc = summary.getRETURNLoc();
1132     NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnCompLoc.getTuple());
1133     Set<FlowNode> incomingNodeToReturnNode =
1134         fg.getIncomingFlowNodeSet(fg.getFlowNode(returnDescTuple));
1135     for (Iterator iterator = incomingNodeToReturnNode.iterator(); iterator.hasNext();) {
1136       FlowNode inNode = (FlowNode) iterator.next();
1137       if (inNode.getDescTuple().get(0).equals(mdCallee.getThis())) {
1138         return true;
1139       }
1140     }
1141     return false;
1142   }
1143
1144   private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) {
1145     MethodDescriptor md = min.getMethod();
1146     if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
1147       mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
1148     }
1149     mapMethodDescToMethodInvokeNodeSet.get(md).add(min);
1150   }
1151
1152   private Set<MethodInvokeNode> getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) {
1153     if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
1154       mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
1155     }
1156     return mapMethodDescToMethodInvokeNodeSet.get(md);
1157   }
1158
1159   private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller,
1160       MethodInvokeNode min) {
1161     System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0));
1162
1163     GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(ssjava.getMethodContainingSSJavaLoop());
1164
1165     Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
1166
1167     MethodDescriptor mdCallee = min.getMethod();
1168
1169     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1170     for (int idx = 0; idx < calleeFlowGraph.getNumParameters(); idx++) {
1171       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
1172       NTuple<Location> globalParamLocTuple =
1173           translateToLocTuple(mdCallee, paramNode.getDescTuple());
1174       translateToLocTuple(mdCallee, paramNode.getDescTuple());
1175       CompositeLocation compLoc = paramNode.getCompositeLocation();
1176       System.out.println("---paramNode=" + paramNode + "    compLoc=" + compLoc);
1177       if (compLoc != null) {
1178         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
1179         NTuple<Location> globalArgLocTuple = translateToLocTuple(mdCaller, argTuple);
1180
1181         if (!isLiteralValueLocTuple(globalArgLocTuple)
1182             && !isLiteralValueLocTuple(globalParamLocTuple)) {
1183           if (!globalGraph.hasValueFlowEdge(globalArgLocTuple, globalParamLocTuple)) {
1184             System.out.println("----- add global flow globalArgLocTuple=" + globalArgLocTuple
1185                 + "-> globalParamLocTuple=" + globalParamLocTuple);
1186             hasChanges = true;
1187             globalGraph.addValueFlowEdge(globalArgLocTuple, globalParamLocTuple);
1188           }
1189         }
1190
1191         for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
1192           NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
1193
1194           if (!isLiteralValueLocTuple(pcLocTuple) && !isLiteralValueLocTuple(globalParamLocTuple)) {
1195             if (!globalGraph.hasValueFlowEdge(pcLocTuple, globalParamLocTuple)) {
1196               System.out
1197                   .println("----- add global flow PCLOC="
1198                       + pcLocTuple
1199                       + "-> globalParamLocTu!globalArgLocTuple.get(0).getLocDescriptor().equals(LITERALDESC)ple="
1200                       + globalParamLocTuple);
1201               hasChanges = true;
1202
1203               globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple);
1204             }
1205           }
1206
1207         }
1208       }
1209     }
1210   }
1211
1212   private boolean isLiteralValueLocTuple(NTuple<Location> locTuple) {
1213     return locTuple.get(0).getLocDescriptor().equals(LITERALDESC);
1214   }
1215
1216   public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
1217       CompositeLocation inferCompLoc) {
1218     Descriptor localDesc = loc.getLocDescriptor();
1219
1220     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
1221     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1222       FlowNode node = (FlowNode) iterator.next();
1223       if (node.getDescTuple().startsWith(localDesc)
1224           && !node.getDescTuple().get(0).equals(LITERALDESC)) {
1225         // need to assign the inferred composite location to this node
1226         CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
1227         node.setCompositeLocation(newCompLoc);
1228         System.out.println("SET Node=" + node + "  inferCompLoc=" + newCompLoc);
1229       }
1230     }
1231   }
1232
1233   private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
1234       CompositeLocation inferCompLoc) {
1235
1236     System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
1237         + inferCompLoc);
1238
1239     MethodDescriptor md = (MethodDescriptor) inferCompLoc.get(0).getDescriptor();
1240
1241     CompositeLocation newCompLoc = new CompositeLocation();
1242     for (int i = 0; i < inferCompLoc.getSize(); i++) {
1243       newCompLoc.addLocation(inferCompLoc.get(i));
1244     }
1245
1246     Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
1247     Descriptor enclosingDescriptor;
1248     if (lastDescOfPrefix instanceof InterDescriptor) {
1249       enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(lastDescOfPrefix);
1250     } else {
1251       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
1252     }
1253
1254     for (int i = 1; i < nodeDescTuple.size(); i++) {
1255       Descriptor desc = nodeDescTuple.get(i);
1256       Location locElement = new Location(enclosingDescriptor, desc);
1257       newCompLoc.addLocation(locElement);
1258
1259       enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
1260     }
1261
1262     return newCompLoc;
1263   }
1264
1265   private void translateMapLocationToInferCompositeLocationToCalleeGraph(
1266       GlobalFlowGraph callerGraph, MethodInvokeNode min) {
1267
1268     MethodDescriptor mdCallee = min.getMethod();
1269     MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
1270     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1271         callerGraph.getMapLocationToInferCompositeLocation();
1272
1273     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
1274
1275     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1276     GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1277
1278     NTuple<Location> baseLocTuple = null;
1279     if (mapMethodInvokeNodeToBaseTuple.containsKey(min)) {
1280       baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
1281     }
1282
1283     // System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee="
1284     // + mdCallee + " baseLocTuple=" + baseLocTuple);
1285
1286     Set<Location> keySet = callerMapLocToCompLoc.keySet();
1287     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1288       Location key = (Location) iterator.next();
1289       CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
1290
1291       if (!key.getDescriptor().equals(mdCaller)) {
1292
1293         CompositeLocation newCalleeCompLoc;
1294         if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
1295           // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc
1296           // + " with baseTuple=" + baseLocTuple);
1297           newCalleeCompLoc =
1298               translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
1299
1300           calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1301           // System.out.println("1---key=" + key + "  callerCompLoc=" + callerCompLoc
1302           // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1303           // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1304           if (!newCalleeCompLoc.get(0).getDescriptor().equals(mdCallee)) {
1305             System.exit(0);
1306           }
1307
1308           // System.out.println("-----baseLoctuple=" + baseLocTuple);
1309         } else {
1310           // check if it is the global access
1311           Location compLocFirstElement = callerCompLoc.getTuple().get(0);
1312           if (compLocFirstElement.getDescriptor().equals(mdCallee)
1313               && compLocFirstElement.getLocDescriptor().equals(GLOBALDESC)) {
1314
1315             newCalleeCompLoc = new CompositeLocation();
1316             Location newMethodLoc = new Location(mdCallee, GLOBALDESC);
1317
1318             newCalleeCompLoc.addLocation(newMethodLoc);
1319             for (int i = 1; i < callerCompLoc.getSize(); i++) {
1320               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1321             }
1322             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1323             // System.out.println("2---key=" + key + "  callerCompLoc=" + callerCompLoc
1324             // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1325             // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1326
1327           } else {
1328             int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
1329             if (paramIdx == -1) {
1330               // here, the first element of the current composite location comes from the current
1331               // callee
1332               // so transfer the same composite location to the callee
1333               if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) {
1334                 if (callerCompLoc.get(0).getDescriptor().equals(mdCallee)) {
1335                   // System.out.println("3---key=" + key + "  callerCompLoc=" + callerCompLoc
1336                   // + "  newCalleeCompLoc=" + callerCompLoc);
1337                   // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1338                   calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc);
1339                 } else {
1340                   // System.out.println("3---SKIP key=" + key + " callerCompLoc=" + callerCompLoc);
1341                 }
1342               }
1343               continue;
1344             }
1345
1346             // It is the case where two parameters have relative orderings between them by having
1347             // composite locations
1348             // if we found the param idx, it means that the first part of the caller composite
1349             // location corresponds to the one of arguments.
1350             // for example, if the caller argument is <<caller.this>,<Decoder.br>>
1351             // and the current caller composite location mapping
1352             // <<caller.this>,<Decoder.br>,<Br.value>>
1353             // and the parameter which matches with the caller argument is 'Br brParam'
1354             // then, the translated callee composite location will be <<callee.brParam>,<Br.value>>
1355             NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(paramIdx);
1356
1357             FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx);
1358             NTuple<Location> paramLocTuple =
1359                 translateToLocTuple(mdCallee, paramFlowNode.getDescTuple());
1360             newCalleeCompLoc = new CompositeLocation();
1361             for (int i = 0; i < paramLocTuple.size(); i++) {
1362               newCalleeCompLoc.addLocation(paramLocTuple.get(i));
1363             }
1364             for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) {
1365               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1366             }
1367             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1368             // System.out.println("4---key=" + key + "  callerCompLoc=" + callerCompLoc
1369             // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1370             // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1371
1372           }
1373
1374         }
1375
1376       }
1377     }
1378
1379     System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + "  caller="
1380         + mdCaller);
1381     // If the location of an argument has a composite location
1382     // need to assign a proper composite location to the corresponding callee parameter
1383     Set<Integer> idxSet = mapIdxToArgTuple.keySet();
1384     for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
1385       Integer idx = (Integer) iterator.next();
1386
1387       if (idx == 0 && !min.getMethod().isStatic()) {
1388         continue;
1389       }
1390
1391       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
1392       System.out.println("-argTuple=" + argTuple + "   idx=" + idx);
1393       if (argTuple.size() > 0) {
1394         // check if an arg tuple has been already assigned to a composite location
1395         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
1396         Location argLocalLoc = argLocTuple.get(0);
1397
1398         // if (!isPrimitiveType(argTuple)) {
1399         if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
1400
1401           CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
1402           for (int i = 1; i < argLocTuple.size(); i++) {
1403             callerCompLoc.addLocation(argLocTuple.get(i));
1404           }
1405
1406           System.out.println("---callerCompLoc=" + callerCompLoc);
1407
1408           // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
1409
1410           FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
1411
1412           NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
1413           NTuple<Location> calleeParamLocTuple =
1414               translateToLocTuple(mdCallee, calleeParamDescTuple);
1415
1416           int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
1417           System.out.println("-----paramIdx=" + refParamIdx);
1418           if (refParamIdx == 0 && !mdCallee.isStatic()) {
1419
1420             System.out.println("-------need to translate callerCompLoc=" + callerCompLoc
1421                 + " with baseTuple=" + baseLocTuple + "   calleeParamLocTuple="
1422                 + calleeParamLocTuple);
1423
1424             CompositeLocation newCalleeCompLoc =
1425                 translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
1426
1427             calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1428                 newCalleeCompLoc);
1429
1430             System.out.println("---------key=" + calleeParamLocTuple.get(0) + "  callerCompLoc="
1431                 + callerCompLoc + "  newCalleeCompLoc=" + newCalleeCompLoc);
1432
1433           } else if (refParamIdx != -1) {
1434             // the first element of an argument composite location matches with one of paramtere
1435             // composite locations
1436
1437             System.out.println("-------param match case=");
1438
1439             NTuple<Descriptor> argTupleRef = mapIdxToArgTuple.get(refParamIdx);
1440             FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx);
1441             NTuple<Location> refParamLocTuple =
1442                 translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple());
1443
1444             System.out.println("---------refParamLocTuple=" + refParamLocTuple
1445                 + "  from argTupleRef=" + argTupleRef);
1446
1447             CompositeLocation newCalleeCompLoc = new CompositeLocation();
1448             for (int i = 0; i < refParamLocTuple.size(); i++) {
1449               newCalleeCompLoc.addLocation(refParamLocTuple.get(i));
1450             }
1451             for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) {
1452               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1453             }
1454
1455             calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1456                 newCalleeCompLoc);
1457
1458             calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc);
1459             System.out.println("-----------key=" + calleeParamLocTuple.get(0) + "  callerCompLoc="
1460                 + callerCompLoc + "  newCalleeCompLoc=" + newCalleeCompLoc);
1461
1462           } else {
1463             CompositeLocation newCalleeCompLoc =
1464                 calculateCompositeLocationFromSubGlobalGraph(mdCallee, calleeParamFlowNode);
1465             if (newCalleeCompLoc != null) {
1466               calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1467                   newCalleeCompLoc);
1468               calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc);
1469             }
1470           }
1471
1472           System.out.println("-----------------calleeParamFlowNode="
1473               + calleeParamFlowNode.getCompositeLocation());
1474
1475           // }
1476
1477         }
1478       }
1479
1480     }
1481
1482   }
1483
1484   private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md,
1485       FlowNode paramNode) {
1486
1487     System.out.println("#############################################################");
1488     System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode);
1489
1490     GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
1491     NTuple<Location> paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple());
1492     GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple);
1493
1494     List<NTuple<Location>> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode);
1495
1496     Location prefixLoc = paramLocTuple.get(0);
1497
1498     Set<GlobalFlowNode> reachableNodeSet =
1499         subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0));
1500     // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
1501
1502     // System.out.println("node=" + node + "    prefixList=" + prefixList);
1503
1504     for (int i = 0; i < prefixList.size(); i++) {
1505       NTuple<Location> curPrefix = prefixList.get(i);
1506       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1507
1508       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1509         GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
1510         if (reachNode.getLocTuple().startsWith(curPrefix)) {
1511           reachableCommonPrefixSet.add(reachNode.getLocTuple());
1512         }
1513       }
1514       // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
1515
1516       if (!reachableCommonPrefixSet.isEmpty()) {
1517
1518         MethodDescriptor curPrefixFirstElementMethodDesc =
1519             (MethodDescriptor) curPrefix.get(0).getDescriptor();
1520
1521         MethodDescriptor nodePrefixLocFirstElementMethodDesc =
1522             (MethodDescriptor) prefixLoc.getDescriptor();
1523
1524         // System.out.println("curPrefixFirstElementMethodDesc=" +
1525         // curPrefixFirstElementMethodDesc);
1526         // System.out.println("nodePrefixLocFirstElementMethodDesc="
1527         // + nodePrefixLocFirstElementMethodDesc);
1528
1529         if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
1530             || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
1531                 curPrefixFirstElementMethodDesc)) {
1532
1533           // TODO
1534           // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
1535
1536           Location curPrefixLocalLoc = curPrefix.get(0);
1537           if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
1538             // in this case, the local variable of the current prefix has already got a composite
1539             // location
1540             // so we just ignore the current composite location.
1541
1542             // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
1543             // + " DUE TO " + curPrefix);
1544             return null;
1545           }
1546
1547           if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) {
1548             System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode
1549                 + " with prefix=" + curPrefix);
1550             return null;
1551           }
1552
1553           Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0);
1554           CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
1555           System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix="
1556               + curPrefix);
1557           System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc=" + newCompLoc);
1558
1559           // makes sure that a newly generated location appears in the hierarchy graph
1560           for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) {
1561             Location curLoc = newCompLoc.get(compIdx);
1562             getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor());
1563           }
1564
1565           subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
1566
1567           return newCompLoc;
1568
1569         }
1570
1571       }
1572
1573     }
1574     return null;
1575   }
1576
1577   private int getParamIdx(CompositeLocation compLoc,
1578       Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple) {
1579
1580     // if the composite location is started with the argument descriptor
1581     // return the argument's index. o.t. return -1
1582
1583     Set<Integer> keySet = mapIdxToArgTuple.keySet();
1584     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1585       Integer key = (Integer) iterator.next();
1586       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(key);
1587       if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) {
1588         System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple);
1589         return key.intValue();
1590       }
1591     }
1592
1593     return -1;
1594   }
1595
1596   private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
1597
1598     Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
1599
1600     if (lastDesc instanceof FieldDescriptor) {
1601       return ((FieldDescriptor) lastDesc).getType().isPrimitive();
1602     } else if (lastDesc instanceof VarDescriptor) {
1603       return ((VarDescriptor) lastDesc).getType().isPrimitive();
1604     } else if (lastDesc instanceof InterDescriptor) {
1605       return true;
1606     }
1607
1608     return false;
1609   }
1610
1611   private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
1612       NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
1613
1614     CompositeLocation newCalleeCompLoc = new CompositeLocation();
1615
1616     Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
1617     newCalleeCompLoc.addLocation(calleeThisLoc);
1618
1619     // remove the base tuple from the caller
1620     // ex; In the method invoation foo.bar.methodA(), the callee will have the composite location
1621     // ,which is relative to the 'this' variable, <THIS,...>
1622     for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
1623       newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1624     }
1625
1626     return newCalleeCompLoc;
1627
1628   }
1629
1630   private void calculateGlobalValueFlowCompositeLocation() {
1631
1632     System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
1633     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1634     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1635
1636     Set<Location> calculatedPrefixSet = new HashSet<Location>();
1637
1638     Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
1639
1640     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1641       GlobalFlowNode node = (GlobalFlowNode) iterator.next();
1642
1643       Location prefixLoc = node.getLocTuple().get(0);
1644
1645       if (calculatedPrefixSet.contains(prefixLoc)) {
1646         // the prefix loc has been already assigned to a composite location
1647         continue;
1648       }
1649
1650       calculatedPrefixSet.add(prefixLoc);
1651
1652       // Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
1653       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
1654
1655       Set<GlobalFlowNode> reachableNodeSet =
1656           globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
1657       // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
1658
1659       // System.out.println("node=" + node + "    prefixList=" + prefixList);
1660       System.out.println("---prefixList=" + prefixList);
1661
1662       nextprefix: for (int i = 0; i < prefixList.size(); i++) {
1663         NTuple<Location> curPrefix = prefixList.get(i);
1664         System.out.println("---curPrefix=" + curPrefix);
1665         Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1666
1667         for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1668           GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
1669           if (reachNode.getLocTuple().startsWith(curPrefix)) {
1670             reachableCommonPrefixSet.add(reachNode.getLocTuple());
1671           }
1672         }
1673         // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
1674
1675         if (!reachableCommonPrefixSet.isEmpty()) {
1676
1677           MethodDescriptor curPrefixFirstElementMethodDesc =
1678               (MethodDescriptor) curPrefix.get(0).getDescriptor();
1679
1680           MethodDescriptor nodePrefixLocFirstElementMethodDesc =
1681               (MethodDescriptor) prefixLoc.getDescriptor();
1682
1683           // System.out.println("curPrefixFirstElementMethodDesc=" +
1684           // curPrefixFirstElementMethodDesc);
1685           // System.out.println("nodePrefixLocFirstElementMethodDesc="
1686           // + nodePrefixLocFirstElementMethodDesc);
1687
1688           if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
1689               || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
1690                   curPrefixFirstElementMethodDesc)) {
1691
1692             // TODO
1693             // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
1694
1695             Location curPrefixLocalLoc = curPrefix.get(0);
1696             if (globalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
1697               // in this case, the local variable of the current prefix has already got a composite
1698               // location
1699               // so we just ignore the current composite location.
1700
1701               // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
1702               // + " DUE TO " + curPrefix);
1703
1704               continue next;
1705             }
1706
1707             if (!needToGenerateCompositeLocation(node, curPrefix)) {
1708               System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix="
1709                   + curPrefix);
1710               // System.out.println("prefixList=" + prefixList);
1711               // System.out.println("reachableNodeSet=" + reachableNodeSet);
1712               continue nextprefix;
1713             }
1714
1715             Location targetLocalLoc = node.getLocTuple().get(0);
1716             CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
1717             System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
1718             System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc="
1719                 + newCompLoc);
1720             globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
1721             // }
1722
1723             continue next;
1724             // }
1725
1726           }
1727
1728         }
1729
1730       }
1731
1732     }
1733   }
1734
1735   private boolean checkFlowNodeReturnThisField(MethodDescriptor md) {
1736
1737     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1738     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1739
1740     FlowGraph flowGraph = getFlowGraph(md);
1741
1742     ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis());
1743     if (enclosingDesc == null) {
1744       return false;
1745     }
1746
1747     int count = 0;
1748     Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
1749     Set<GlobalFlowNode> globalReturnNodeSet = new HashSet<GlobalFlowNode>();
1750     for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1751       FlowNode flowNode = (FlowNode) iterator.next();
1752       NTuple<Location> locTuple = translateToLocTuple(md, flowNode.getDescTuple());
1753       GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple);
1754       globalReturnNodeSet.add(globalReturnNode);
1755
1756       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode);
1757       for (int i = 0; i < prefixList.size(); i++) {
1758         NTuple<Location> curPrefix = prefixList.get(i);
1759         ClassDescriptor cd =
1760             getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor());
1761         if (cd != null && cd.equals(enclosingDesc)) {
1762           count++;
1763           break;
1764         }
1765       }
1766
1767     }
1768
1769     if (count == returnNodeSet.size()) {
1770       // in this case, all return nodes in the method returns values coming from a location that
1771       // starts with "this"
1772
1773       System.out.println("$$$SET RETURN LOC TRUE=" + md);
1774       mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE);
1775
1776       // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++));
1777       // NTuple<Descriptor> rDescTuple = new NTuple<Descriptor>();
1778       // rDescTuple.add(md.getThis());
1779       // rDescTuple.add(returnLocDesc);
1780       //
1781       // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1782       // FlowNode rnode = (FlowNode) iterator.next();
1783       // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple);
1784       // }
1785       //
1786       // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md,
1787       // rDescTuple)));
1788
1789     } else {
1790       mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE);
1791     }
1792
1793     return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1794
1795   }
1796
1797   private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple<Location> curPrefix) {
1798     // return true if there is a path between a node to which we want to give a composite location
1799     // and nodes which start with curPrefix
1800
1801     System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix);
1802
1803     Location targetLocalLoc = node.getLocTuple().get(0);
1804
1805     MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor();
1806     FlowGraph flowGraph = getFlowGraph(md);
1807
1808     FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple());
1809     Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
1810
1811     Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
1812     for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) {
1813       FlowNode paramFlowNode = (FlowNode) iterator.next();
1814       if (curPrefix.startsWith(translateToLocTuple(md, paramFlowNode.getDescTuple()))) {
1815         return true;
1816       }
1817     }
1818
1819     if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) {
1820       Pair<MethodInvokeNode, Integer> pair =
1821           ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair();
1822
1823       if (pair != null) {
1824         System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc);
1825
1826         MethodInvokeNode min = pair.getFirst();
1827         Integer paramIdx = pair.getSecond();
1828         MethodDescriptor mdCallee = min.getMethod();
1829
1830         FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx);
1831         if (checkNodeReachToReturnNode(mdCallee, paramNode)) {
1832           return true;
1833         }
1834
1835       }
1836
1837     }
1838
1839     GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
1840     Set<GlobalFlowNode> subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node);
1841
1842     if (!md.isStatic()) {
1843       ClassDescriptor currentMethodThisType = getClassTypeDescriptor(md.getThis());
1844       for (int i = 0; i < curPrefix.size(); i++) {
1845         ClassDescriptor prefixType = getClassTypeDescriptor(curPrefix.get(i).getLocDescriptor());
1846         if (prefixType != null && prefixType.equals(currentMethodThisType)) {
1847           System.out.println("PREFIX TYPE MATCHES WITH=" + currentMethodThisType);
1848
1849           if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
1850             boolean hasCompReturnLocWithThis =
1851                 mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1852             if (hasCompReturnLocWithThis) {
1853               if (checkNodeReachToReturnNode(md, flowNode)) {
1854                 return true;
1855               }
1856             }
1857           }
1858
1859           for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) {
1860             GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next();
1861             if (subGlobalReachalbeNode.getLocTuple().get(0).getLocDescriptor().equals(md.getThis())) {
1862               System.out.println("PREFIX FOUND=" + subGlobalReachalbeNode);
1863               return true;
1864             }
1865           }
1866         }
1867       }
1868     }
1869
1870     Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1);
1871     // check whether prefix appears in the list of parameters
1872     Set<MethodInvokeNode> minSet = mapMethodDescToMethodInvokeNodeSet.get(md);
1873     System.out.println("$$$md=" + md + "   minSet=" + minSet);
1874     if (minSet == null) {
1875       return false;
1876     }
1877     found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1878       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1879       Map<Integer, NTuple<Descriptor>> map = mapMethodInvokeNodeToArgIdxMap.get(min);
1880       Set<Integer> keySet = map.keySet();
1881       // System.out.println("min=" + min.printNode(0));
1882
1883       for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1884         Integer argIdx = (Integer) iterator2.next();
1885         NTuple<Descriptor> argTuple = map.get(argIdx);
1886
1887         if (!(!md.isStatic() && argIdx == 0)) {
1888           // if the argTuple is empty, we don't need to do with anything(LITERAL CASE).
1889           if (argTuple.size() > 0
1890               && argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) {
1891             NTuple<Location> locTuple =
1892                 translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple());
1893             lastLocationOfPrefix = locTuple.get(0);
1894             System.out.println("ARG CASE=" + locTuple);
1895             for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) {
1896               GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next();
1897               // NTuple<Location> locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple());
1898               NTuple<Location> globalReachlocTuple = subGlobalReachalbeNode.getLocTuple();
1899               for (int i = 0; i < globalReachlocTuple.size(); i++) {
1900                 if (globalReachlocTuple.get(i).equals(lastLocationOfPrefix)) {
1901                   System.out.println("ARG  " + argTuple + "  IS MATCHED WITH="
1902                       + lastLocationOfPrefix);
1903                   return true;
1904                 }
1905               }
1906             }
1907           }
1908         }
1909       }
1910     }
1911
1912     return false;
1913   }
1914
1915   private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) {
1916
1917     FlowGraph flowGraph = getFlowGraph(md);
1918     Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(node);
1919     if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
1920       boolean hasCompReturnLocWithThis =
1921           mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1922
1923       if (hasCompReturnLocWithThis) {
1924         for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) {
1925           FlowNode returnFlowNode = (FlowNode) iterator.next();
1926           if (reachableSet.contains(returnFlowNode)) {
1927             return true;
1928           }
1929         }
1930       }
1931     }
1932     return false;
1933   }
1934
1935   private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
1936     CompositeLocation newCompLoc = compLocPrefix.clone();
1937     NTuple<Location> locTuple = node.getLocTuple();
1938     for (int i = 1; i < locTuple.size(); i++) {
1939       newCompLoc.addLocation(locTuple.get(i));
1940     }
1941     node.setInferCompositeLocation(newCompLoc);
1942   }
1943
1944   private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
1945
1946     System.out.println("\n##### calculatePrefixList node=" + node);
1947
1948     Set<GlobalFlowNode> incomingNodeSetPrefix =
1949         graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0));
1950     // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix);
1951
1952     Set<GlobalFlowNode> reachableNodeSetPrefix =
1953         graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
1954     // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix);
1955
1956     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
1957
1958     for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
1959       GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
1960       NTuple<Location> inNodeTuple = inNode.getLocTuple();
1961
1962       if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor
1963           || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) {
1964         continue;
1965       }
1966
1967       for (int i = 1; i < inNodeTuple.size(); i++) {
1968         NTuple<Location> prefix = inNodeTuple.subList(0, i);
1969         if (!prefixList.contains(prefix)) {
1970           prefixList.add(prefix);
1971         }
1972       }
1973     }
1974
1975     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
1976       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
1977         int s0 = arg0.size();
1978         int s1 = arg1.size();
1979         if (s0 > s1) {
1980           return -1;
1981         } else if (s0 == s1) {
1982           return 0;
1983         } else {
1984           return 1;
1985         }
1986       }
1987     });
1988
1989     return prefixList;
1990
1991   }
1992
1993   private CompositeLocation calculateCompositeLocationFromFlowGraph(MethodDescriptor md,
1994       FlowNode node) {
1995
1996     System.out.println("#############################################################");
1997     System.out.println("calculateCompositeLocationFromFlowGraph=" + node);
1998
1999     FlowGraph flowGraph = getFlowGraph(md);
2000     // NTuple<Location> paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple());
2001     // GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple);
2002
2003     List<NTuple<Location>> prefixList = calculatePrefixListFlowGraph(flowGraph, node);
2004
2005     // Set<GlobalFlowNode> reachableNodeSet =
2006     // subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0));
2007     //
2008     Set<FlowNode> reachableNodeSet =
2009         flowGraph.getReachableSetFrom(node.getDescTuple().subList(0, 1));
2010
2011     // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
2012
2013     // System.out.println("node=" + node + "    prefixList=" + prefixList);
2014
2015     for (int i = 0; i < prefixList.size(); i++) {
2016       NTuple<Location> curPrefix = prefixList.get(i);
2017       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
2018
2019       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
2020         FlowNode reachNode = (FlowNode) iterator2.next();
2021         NTuple<Location> reachLocTuple = translateToLocTuple(md, reachNode.getCurrentDescTuple());
2022         if (reachLocTuple.startsWith(curPrefix)) {
2023           reachableCommonPrefixSet.add(reachLocTuple);
2024         }
2025       }
2026       // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
2027
2028       if (!reachableCommonPrefixSet.isEmpty()) {
2029
2030         MethodDescriptor curPrefixFirstElementMethodDesc =
2031             (MethodDescriptor) curPrefix.get(0).getDescriptor();
2032
2033         Location curPrefixLocalLoc = curPrefix.get(0);
2034
2035         Location targetLocalLoc = new Location(md, node.getDescTuple().get(0));
2036         // Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0);
2037
2038         CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
2039         System.out.println("NEED2ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
2040         System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc=" + newCompLoc);
2041
2042         node.setCompositeLocation(newCompLoc);
2043
2044         return newCompLoc;
2045
2046       }
2047
2048     }
2049     return null;
2050   }
2051
2052   private List<NTuple<Location>> calculatePrefixListFlowGraph(FlowGraph graph, FlowNode node) {
2053
2054     System.out.println("\n##### calculatePrefixList node=" + node);
2055
2056     MethodDescriptor md = graph.getMethodDescriptor();
2057     Set<FlowNode> incomingNodeSetPrefix =
2058         graph.getIncomingNodeSetByPrefix(node.getDescTuple().get(0));
2059     // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix);
2060
2061     Set<FlowNode> reachableNodeSetPrefix =
2062         graph.getReachableSetFrom(node.getDescTuple().subList(0, 1));
2063     // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix);
2064
2065     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
2066
2067     for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
2068       FlowNode inNode = (FlowNode) iterator.next();
2069       NTuple<Location> inNodeTuple = translateToLocTuple(md, inNode.getCurrentDescTuple());
2070
2071       // if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor
2072       // || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) {
2073       // continue;
2074       // }
2075
2076       for (int i = 1; i < inNodeTuple.size(); i++) {
2077         NTuple<Location> prefix = inNodeTuple.subList(0, i);
2078         if (!prefixList.contains(prefix)) {
2079           prefixList.add(prefix);
2080         }
2081       }
2082     }
2083
2084     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
2085       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
2086         int s0 = arg0.size();
2087         int s1 = arg1.size();
2088         if (s0 > s1) {
2089           return -1;
2090         } else if (s0 == s1) {
2091           return 0;
2092         } else {
2093           return 1;
2094         }
2095       }
2096     });
2097
2098     return prefixList;
2099
2100   }
2101
2102   private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
2103
2104     MethodDescriptor md = flowGraph.getMethodDescriptor();
2105
2106     GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md);
2107
2108     // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
2109     Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
2110
2111     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
2112
2113       FlowEdge edge = (FlowEdge) iterator.next();
2114       NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
2115       NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
2116
2117       if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode
2118           || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) {
2119         continue;
2120       }
2121
2122       // here only keep the first element(method location) of the descriptor
2123       // tuple
2124       NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
2125       NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
2126
2127       globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
2128
2129     }
2130
2131     return globalGraph;
2132   }
2133
2134   private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
2135
2136     NTuple<Location> locTuple = new NTuple<Location>();
2137
2138     Descriptor enclosingDesc = md;
2139     for (int i = 0; i < descTuple.size(); i++) {
2140       Descriptor desc = descTuple.get(i);
2141
2142       Location loc = new Location(enclosingDesc, desc);
2143       locTuple.add(loc);
2144
2145       if (desc instanceof VarDescriptor) {
2146         enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
2147       } else if (desc instanceof FieldDescriptor) {
2148         enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2149       } else {
2150         enclosingDesc = desc;
2151       }
2152
2153     }
2154
2155     return locTuple;
2156
2157   }
2158
2159   private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller) {
2160
2161     // the transformation for a call site propagates flows through parameters
2162     // if the method is virtual, it also grab all relations from any possible
2163     // callees
2164
2165     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
2166
2167     for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
2168       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
2169       MethodDescriptor mdCallee = min.getMethod();
2170       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2171       if (mdCallee.isStatic()) {
2172         setPossibleCallees.add(mdCallee);
2173       } else {
2174         Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
2175         // removes method descriptors that are not invoked by the caller
2176         calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
2177         setPossibleCallees.addAll(calleeSet);
2178       }
2179
2180       for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
2181         MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
2182         propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
2183       }
2184
2185     }
2186
2187   }
2188
2189   private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
2190       MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
2191
2192     System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller);
2193     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
2194     Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
2195
2196     System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)="
2197         + mapMethodInvokeNodeToArgIdxMap.get(min));
2198
2199     Set<Integer> keySet = mapIdxToArg.keySet();
2200     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2201       Integer idx = (Integer) iterator.next();
2202       NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
2203       if (argDescTuple.size() > 0) {
2204         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
2205         NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
2206         NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
2207         System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple="
2208             + argDescTuple);
2209         addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
2210       }
2211     }
2212
2213     // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee);
2214
2215     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2216     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
2217     Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
2218     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
2219       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
2220       addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
2221     }
2222
2223     System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller);
2224     Set<NTuple<Location>> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min);
2225     System.out.println("---pcLocTupleSet=" + pcLocTupleSet);
2226     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
2227     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
2228       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
2229       if (calleeNode.isParamNodeWithIncomingFlows()) {
2230         System.out.println("calleeNode.getLocTuple()" + calleeNode.getLocTuple());
2231         NTuple<Location> callerSrcNodeLocTuple =
2232             translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple());
2233         System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
2234         if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
2235           for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) {
2236             NTuple<Location> pcLocTuple = (NTuple<Location>) iterator2.next();
2237
2238             callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple);
2239           }
2240         }
2241       }
2242
2243     }
2244
2245   }
2246
2247   private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
2248       MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
2249
2250     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
2251     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
2252
2253     System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode);
2254
2255     NTuple<Location> callerSrcNodeLocTuple =
2256         translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
2257     System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
2258
2259     if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
2260
2261       Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
2262
2263       for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
2264         GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
2265         NTuple<Location> callerDstNodeLocTuple =
2266             translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
2267         // System.out.println("outNode=" + outNode + "   callerDstNodeLocTuple="
2268         // + callerDstNodeLocTuple);
2269         if (callerSrcNodeLocTuple != null && callerDstNodeLocTuple != null
2270             && callerSrcNodeLocTuple.size() > 0 && callerDstNodeLocTuple.size() > 0) {
2271           callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
2272         }
2273       }
2274     }
2275
2276   }
2277
2278   private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
2279       MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
2280     // this method will return the same nodeLocTuple if the corresponding argument is literal
2281     // value.
2282
2283     // System.out.println("translateToCallerLocTuple=" + nodeLocTuple);
2284
2285     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2286     NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
2287     if (calleeFlowGraph.isParameter(nodeDescTuple)) {
2288       int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
2289       NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
2290
2291       // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) {
2292       // // the type of argument is primitive.
2293       // return nodeLocTuple.clone();
2294       // }
2295       // System.out.println("paramIdx=" + paramIdx + "  argDescTuple=" + argDescTuple + " from min="
2296       // + min.printNode(0));
2297       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
2298
2299       NTuple<Location> callerLocTuple = new NTuple<Location>();
2300
2301       callerLocTuple.addAll(argLocTuple);
2302       for (int i = 1; i < nodeLocTuple.size(); i++) {
2303         callerLocTuple.add(nodeLocTuple.get(i));
2304       }
2305       return callerLocTuple;
2306     } else {
2307       return nodeLocTuple.clone();
2308     }
2309
2310   }
2311
2312   public static boolean isPrimitive(Descriptor desc) {
2313
2314     if (desc instanceof FieldDescriptor) {
2315       return ((FieldDescriptor) desc).getType().isPrimitive();
2316     } else if (desc instanceof VarDescriptor) {
2317       return ((VarDescriptor) desc).getType().isPrimitive();
2318     } else if (desc instanceof InterDescriptor) {
2319       return true;
2320     }
2321
2322     return false;
2323   }
2324
2325   public static boolean isReference(Descriptor desc) {
2326
2327     if (desc instanceof FieldDescriptor) {
2328
2329       TypeDescriptor type = ((FieldDescriptor) desc).getType();
2330       if (type.isArray()) {
2331         return !type.isPrimitive();
2332       } else {
2333         return type.isPtr();
2334       }
2335
2336     } else if (desc instanceof VarDescriptor) {
2337       TypeDescriptor type = ((VarDescriptor) desc).getType();
2338       if (type.isArray()) {
2339         return !type.isPrimitive();
2340       } else {
2341         return type.isPtr();
2342       }
2343     }
2344
2345     return false;
2346   }
2347
2348   private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
2349
2350     NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
2351     for (int i = 0; i < locTuple.size(); i++) {
2352       descTuple.add(locTuple.get(i).getLocDescriptor());
2353     }
2354     return descTuple;
2355
2356   }
2357
2358   public LocationSummary getLocationSummary(Descriptor d) {
2359     if (!mapDescToLocationSummary.containsKey(d)) {
2360       if (d instanceof MethodDescriptor) {
2361         mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
2362       } else if (d instanceof ClassDescriptor) {
2363         mapDescToLocationSummary.put(d, new FieldSummary());
2364       }
2365     }
2366     return mapDescToLocationSummary.get(d);
2367   }
2368
2369   private void generateMethodSummary() {
2370
2371     Set<MethodDescriptor> keySet = md2lattice.keySet();
2372     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2373       MethodDescriptor md = (MethodDescriptor) iterator.next();
2374
2375       System.out.println("\nSSJAVA: generate method summary: " + md);
2376
2377       FlowGraph flowGraph = getFlowGraph(md);
2378       if (flowGraph == null) {
2379         continue;
2380       }
2381       MethodSummary methodSummary = getMethodSummary(md);
2382
2383       HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md);
2384
2385       // set the 'this' reference location
2386       if (!md.isStatic()) {
2387         System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName());
2388         methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName());
2389       }
2390
2391       // set the 'global' reference location if needed
2392       if (methodSummary.hasGlobalAccess()) {
2393         methodSummary.setGlobalLocName(scGraph.getHNode(GLOBALDESC).getName());
2394       }
2395
2396       // construct a parameter mapping that maps a parameter descriptor to an
2397       // inferred composite location
2398       for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
2399         FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
2400         CompositeLocation inferredCompLoc =
2401             updateCompositeLocation(flowNode.getCompositeLocation());
2402         System.out.println("-paramIdx=" + paramIdx + "   infer=" + inferredCompLoc + " original="
2403             + flowNode.getCompositeLocation());
2404
2405         Descriptor localVarDesc = flowNode.getDescTuple().get(0);
2406         methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc);
2407         methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
2408       }
2409
2410     }
2411
2412   }
2413
2414   private boolean hasOrderingRelation(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
2415
2416     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
2417
2418     for (int idx = 0; idx < size; idx++) {
2419       Location loc1 = locTuple1.get(idx);
2420       Location loc2 = locTuple2.get(idx);
2421
2422       Descriptor desc1 = loc1.getDescriptor();
2423       Descriptor desc2 = loc2.getDescriptor();
2424
2425       if (!desc1.equals(desc2)) {
2426         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
2427       }
2428
2429       Descriptor locDesc1 = loc1.getLocDescriptor();
2430       Descriptor locDesc2 = loc2.getLocDescriptor();
2431
2432       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
2433
2434       HNode node1 = hierarchyGraph.getHNode(locDesc1);
2435       HNode node2 = hierarchyGraph.getHNode(locDesc2);
2436
2437       System.out.println("---node1=" + node1 + "  node2=" + node2);
2438       System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
2439           + hierarchyGraph.getIncomingNodeSet(node2));
2440
2441       if (locDesc1.equals(locDesc2)) {
2442         continue;
2443       } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1)
2444           && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) {
2445         return false;
2446       } else {
2447         return true;
2448       }
2449
2450     }
2451
2452     return false;
2453
2454   }
2455
2456   private boolean isHigherThan(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
2457
2458     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
2459
2460     for (int idx = 0; idx < size; idx++) {
2461       Location loc1 = locTuple1.get(idx);
2462       Location loc2 = locTuple2.get(idx);
2463
2464       Descriptor desc1 = loc1.getDescriptor();
2465       Descriptor desc2 = loc2.getDescriptor();
2466
2467       if (!desc1.equals(desc2)) {
2468         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
2469       }
2470
2471       Descriptor locDesc1 = loc1.getLocDescriptor();
2472       Descriptor locDesc2 = loc2.getLocDescriptor();
2473
2474       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
2475
2476       HNode node1 = hierarchyGraph.getHNode(locDesc1);
2477       HNode node2 = hierarchyGraph.getHNode(locDesc2);
2478
2479       System.out.println("---node1=" + node1 + "  node2=" + node2);
2480       System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
2481           + hierarchyGraph.getIncomingNodeSet(node2));
2482
2483       if (locDesc1.equals(locDesc2)) {
2484         continue;
2485       } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) {
2486         return true;
2487       } else {
2488         return false;
2489       }
2490
2491     }
2492
2493     return false;
2494   }
2495
2496   private void debug_writeLattices() {
2497
2498     Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
2499     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2500       Descriptor key = (Descriptor) iterator.next();
2501       SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
2502       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
2503       HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
2504       if (key instanceof ClassDescriptor) {
2505         // writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
2506         // "_SIMPLE");
2507       } else if (key instanceof MethodDescriptor) {
2508         MethodDescriptor md = (MethodDescriptor) key;
2509         // writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
2510         // "_SIMPLE");
2511       }
2512
2513       LocationSummary ls = getLocationSummary(key);
2514       System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
2515     }
2516
2517     Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
2518     for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
2519       ClassDescriptor cd = (ClassDescriptor) iterator.next();
2520       System.out.println("########cd=" + cd);
2521       writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
2522           cd2lattice.get(cd), "");
2523       COUNT += cd2lattice.get(cd).getKeySet().size();
2524     }
2525
2526     Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
2527     for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
2528       MethodDescriptor md = (MethodDescriptor) iterator.next();
2529       writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
2530           md2lattice.get(md), "");
2531       COUNT += md2lattice.get(md).getKeySet().size();
2532     }
2533     System.out.println("###COUNT=" + COUNT);
2534   }
2535
2536   private void buildLattice(Descriptor desc) {
2537     System.out.println("buildLattice=" + desc);
2538     SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
2539
2540     addMapDescToSimpleLattice(desc, simpleLattice);
2541
2542     HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2543     System.out.println("\n## insertIntermediateNodesToStraightLine:"
2544         + simpleHierarchyGraph.getName());
2545     SSJavaLattice<String> lattice =
2546         buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
2547     lattice.removeRedundantEdges();
2548
2549     if (desc instanceof ClassDescriptor) {
2550       // field lattice
2551       cd2lattice.put((ClassDescriptor) desc, lattice);
2552       // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
2553     } else if (desc instanceof MethodDescriptor) {
2554       // method lattice
2555       md2lattice.put((MethodDescriptor) desc, lattice);
2556       MethodDescriptor md = (MethodDescriptor) desc;
2557       ClassDescriptor cd = md.getClassDesc();
2558       // ssjava.writeLatticeDotFile(cd, md, lattice);
2559     }
2560
2561   }
2562
2563   private void buildLattice() {
2564
2565     Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
2566     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2567       Descriptor desc = (Descriptor) iterator.next();
2568
2569       SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
2570
2571       addMapDescToSimpleLattice(desc, simpleLattice);
2572
2573       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2574       System.out.println("\n## insertIntermediateNodesToStraightLine:"
2575           + simpleHierarchyGraph.getName());
2576       SSJavaLattice<String> lattice =
2577           buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
2578       lattice.removeRedundantEdges();
2579
2580       if (desc instanceof ClassDescriptor) {
2581         // field lattice
2582         cd2lattice.put((ClassDescriptor) desc, lattice);
2583         // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
2584       } else if (desc instanceof MethodDescriptor) {
2585         // method lattice
2586         md2lattice.put((MethodDescriptor) desc, lattice);
2587         MethodDescriptor md = (MethodDescriptor) desc;
2588         ClassDescriptor cd = md.getClassDesc();
2589         // ssjava.writeLatticeDotFile(cd, md, lattice);
2590       }
2591
2592     }
2593
2594   }
2595
2596   private void buildLatticeInheritanceTree() {
2597     // DFS the inheritance tree and propagates lattice nodes/edges from the parent to children
2598     // Node<ClassDescriptor> rootNode = inheritanceTree.getRootNode();
2599     DFSBuildLatticeInheritanceTree(rootClassDescriptor);
2600   }
2601
2602   public Set<ClassDescriptor> getDirectSubClasses(ClassDescriptor parent) {
2603
2604     System.out.println("$$$toanalyze_classDescSet=" + toanalyze_classDescSet);
2605     Set<ClassDescriptor> result = new HashSet<ClassDescriptor>();
2606
2607     Set<ClassDescriptor> children = tu.getDirectSubClasses(parent);
2608     if (children == null) {
2609       children = new HashSet<ClassDescriptor>();
2610     }
2611
2612     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
2613       ClassDescriptor child = (ClassDescriptor) iterator.next();
2614       if (toanalyze_classDescSet.contains(child)) {
2615         result.add(child);
2616       }
2617     }
2618
2619     return result;
2620   }
2621
2622   private void DFSBuildLatticeInheritanceTree(ClassDescriptor cd) {
2623     // ClassDescriptor cd = node.getData();
2624
2625     ClassDescriptor parentClassDesc = cd.getSuperDesc();
2626     if (parentClassDesc != null) {
2627       Map<TripleItem, String> parentMap = buildLattice.getIntermediateLocMap(parentClassDesc);
2628       buildLattice.setIntermediateLocMap(cd, parentMap);
2629     }
2630
2631     buildLattice(cd);
2632
2633     for (Iterator iterator = cd.getMethods(); iterator.hasNext();) {
2634       MethodDescriptor md = (MethodDescriptor) iterator.next();
2635       if (toanalyze_methodDescList.contains(md)) {
2636         MethodDescriptor parentMethodDesc = getParentMethodDesc(md.getClassDesc(), md);
2637         if (parentMethodDesc != null) {
2638           Map<TripleItem, String> parentMap = buildLattice.getIntermediateLocMap(parentMethodDesc);
2639           buildLattice.setIntermediateLocMap(md, parentMap);
2640         }
2641         buildLattice(md);
2642       }
2643     }
2644
2645     // traverse children
2646     Set<ClassDescriptor> children = getDirectSubClasses(cd);
2647     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
2648       ClassDescriptor classDescriptor = (ClassDescriptor) iterator.next();
2649       if (toanalyze_classDescSet.contains(classDescriptor)) {
2650         DFSBuildLatticeInheritanceTree(classDescriptor);
2651       }
2652
2653     }
2654
2655   }
2656
2657   public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
2658     mapDescriptorToSimpleLattice.put(desc, lattice);
2659   }
2660
2661   public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
2662     return mapDescriptorToSimpleLattice.get(desc);
2663   }
2664
2665   private void simplifyHierarchyGraph() {
2666     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2667     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2668       Descriptor desc = (Descriptor) iterator.next();
2669       // System.out.println("SSJAVA: remove redundant edges: " + desc);
2670       HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
2671       simpleHierarchyGraph.setName(desc + "_SIMPLE");
2672       simpleHierarchyGraph.removeRedundantEdges();
2673       mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
2674     }
2675   }
2676
2677   private void insertCombinationNodes() {
2678     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
2679     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2680       Descriptor desc = (Descriptor) iterator.next();
2681       System.out.println("\nSSJAVA: Inserting Combination Nodes:" + desc);
2682       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
2683       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
2684       skeletonGraphWithCombinationNode.setName(desc + "_SC");
2685
2686       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2687       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
2688       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph,
2689       // skeletonGraph);
2690       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
2691       skeletonGraphWithCombinationNode.removeRedundantEdges();
2692       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
2693     }
2694   }
2695
2696   private void constructSkeletonHierarchyGraph() {
2697     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2698     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2699       Descriptor desc = (Descriptor) iterator.next();
2700       System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc);
2701       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
2702       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
2703       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
2704       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
2705       skeletonGraph.simplifyHierarchyGraph(this);
2706       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
2707     }
2708   }
2709
2710   private void recurUpAccumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2711
2712     if (curDesc instanceof ClassDescriptor) {
2713       ClassDescriptor cd = (ClassDescriptor) curDesc;
2714       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2715       if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) {
2716         set.add(parentClassDesc);
2717         recurUpAccumulateInheritanceDesc(parentClassDesc, set);
2718       }
2719     } else {
2720       MethodDescriptor md = (MethodDescriptor) curDesc;
2721       ClassDescriptor cd = md.getClassDesc();
2722
2723       // traverse up
2724       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2725       if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) {
2726
2727         Set<MethodDescriptor> methodDescSet =
2728             parentClassDesc.getMethodTable().getSet(md.getSymbol());
2729         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
2730           MethodDescriptor parentMethodDesc = (MethodDescriptor) iterator.next();
2731           if (parentMethodDesc.matches(md)) {
2732             set.add(parentMethodDesc);
2733             recurUpAccumulateInheritanceDesc(parentMethodDesc, set);
2734           }
2735         }
2736       }
2737
2738     }
2739
2740   }
2741
2742   private void recurDownAccumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2743
2744     if (curDesc instanceof ClassDescriptor) {
2745       ClassDescriptor cd = (ClassDescriptor) curDesc;
2746       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2747       Set<ClassDescriptor> directSubClasses = tu.getDirectSubClasses(cd);
2748       for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) {
2749         ClassDescriptor child = (ClassDescriptor) iterator.next();
2750         recurDownAccumulateInheritanceDesc(child, set);
2751       }
2752     } else {
2753       MethodDescriptor md = (MethodDescriptor) curDesc;
2754       ClassDescriptor cd = md.getClassDesc();
2755
2756       // traverse down
2757       Set<ClassDescriptor> directSubClasses = tu.getDirectSubClasses(cd);
2758       for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) {
2759         ClassDescriptor child = (ClassDescriptor) iterator.next();
2760
2761         Set<MethodDescriptor> methodDescSet = child.getMethodTable().getSet(md.getSymbol());
2762         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
2763           MethodDescriptor childMethodDesc = (MethodDescriptor) iterator2.next();
2764           if (childMethodDesc.matches(md)) {
2765             set.add(childMethodDesc);
2766             recurDownAccumulateInheritanceDesc(childMethodDesc, set);
2767           }
2768         }
2769       }
2770
2771     }
2772
2773   }
2774
2775   private void accumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2776
2777     recurUpAccumulateInheritanceDesc(curDesc, set);
2778     recurDownAccumulateInheritanceDesc(curDesc, set);
2779
2780   }
2781
2782   public boolean isValidMergeInheritanceCheck(Descriptor desc, Set<HNode> mergeSet) {
2783
2784     // set up inheritance chain set...
2785     Set<Descriptor> inheritanceDescSet = new HashSet<Descriptor>();
2786     recurUpAccumulateInheritanceDesc(desc, inheritanceDescSet);
2787
2788     nextgraph: for (Iterator iterator = inheritanceDescSet.iterator(); iterator.hasNext();) {
2789       Descriptor inheritDesc = (Descriptor) iterator.next();
2790
2791       if (!desc.equals(inheritDesc)) {
2792         HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(inheritDesc);
2793
2794         // first check whether this graph includes all elements of the merge set
2795         for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) {
2796           HNode node = (HNode) iterator2.next();
2797           if (!graph.contains(node)) {
2798             continue nextgraph;
2799           }
2800         }
2801
2802         HNode firstNode = mergeSet.iterator().next();
2803
2804         Set<HNode> incomingNode = graph.getIncomingNodeSet(firstNode);
2805         Set<HNode> outgoingNode = graph.getOutgoingNodeSet(firstNode);
2806
2807         for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) {
2808           HNode node = (HNode) iterator2.next();
2809
2810           if (!graph.getIncomingNodeSet(node).equals(incomingNode)
2811               || !graph.getOutgoingNodeSet(node).equals(outgoingNode)) {
2812             return false;
2813           }
2814
2815         }
2816       }
2817
2818     }
2819
2820     return true;
2821   }
2822
2823   private void debug_writeHierarchyDotFiles() {
2824
2825     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2826     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2827       Descriptor desc = (Descriptor) iterator.next();
2828       getHierarchyGraph(desc).writeGraph();
2829     }
2830
2831   }
2832
2833   private void debug_writeSimpleHierarchyDotFiles() {
2834
2835     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2836     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2837       Descriptor desc = (Descriptor) iterator.next();
2838       getHierarchyGraph(desc).writeGraph();
2839       getSimpleHierarchyGraph(desc).writeGraph();
2840       getSimpleHierarchyGraph(desc).writeGraph(true);
2841     }
2842
2843   }
2844
2845   private void debug_writeSkeletonHierarchyDotFiles() {
2846
2847     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2848     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2849       Descriptor desc = (Descriptor) iterator.next();
2850       getSkeletonHierarchyGraph(desc).writeGraph();
2851     }
2852
2853   }
2854
2855   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
2856
2857     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2858     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2859       Descriptor desc = (Descriptor) iterator.next();
2860       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
2861     }
2862
2863   }
2864
2865   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
2866     return mapDescriptorToSimpleHierarchyGraph.get(d);
2867   }
2868
2869   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
2870     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
2871       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2872     }
2873     return mapDescriptorToSkeletonHierarchyGraph.get(d);
2874   }
2875
2876   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
2877     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
2878       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2879     }
2880     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
2881   }
2882
2883   private void constructHierarchyGraph() {
2884
2885     LinkedList<MethodDescriptor> methodDescList =
2886         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
2887
2888     while (!methodDescList.isEmpty()) {
2889       MethodDescriptor md = methodDescList.removeLast();
2890       if (state.SSJAVADEBUG) {
2891         HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
2892         System.out.println();
2893         System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
2894         constructHierarchyGraph(md, hierarchyGraph);
2895         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
2896
2897       }
2898     }
2899
2900     setupToAnalyze();
2901     while (!toAnalyzeIsEmpty()) {
2902       ClassDescriptor cd = toAnalyzeNext();
2903       HierarchyGraph graph = getHierarchyGraph(cd);
2904       for (Iterator iter = cd.getFields(); iter.hasNext();) {
2905         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
2906         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
2907           graph.getHNode(fieldDesc);
2908         }
2909       }
2910     }
2911
2912     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2913     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2914       Descriptor key = (Descriptor) iterator.next();
2915       HierarchyGraph graph = getHierarchyGraph(key);
2916
2917       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
2918       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
2919         HNode node = (HNode) iterator2.next();
2920         if (!node.isSkeleton() && !node.isCombinationNode()) {
2921           if (graph.getIncomingNodeSet(node).size() == 0) {
2922             nodeToBeConnected.add(node);
2923           }
2924         }
2925       }
2926
2927       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
2928         HNode node = (HNode) iterator2.next();
2929         System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
2930         graph.addEdge(graph.getHNode(TOPDESC), node);
2931       }
2932
2933     }
2934
2935   }
2936
2937   private void constructHierarchyGraph2() {
2938
2939     // do fixed-point analysis
2940
2941     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
2942
2943     // Collections.sort(descriptorListToAnalyze, new
2944     // Comparator<MethodDescriptor>() {
2945     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
2946     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
2947     // }
2948     // });
2949
2950     // current descriptors to visit in fixed-point interprocedural analysis,
2951     // prioritized by dependency in the call graph
2952     methodDescriptorsToVisitStack.clear();
2953
2954     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2955     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2956
2957     while (!descriptorListToAnalyze.isEmpty()) {
2958       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2959       methodDescriptorsToVisitStack.add(md);
2960     }
2961
2962     // analyze scheduled methods until there are no more to visit
2963     while (!methodDescriptorsToVisitStack.isEmpty()) {
2964       // start to analyze leaf node
2965       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
2966
2967       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
2968       // MethodSummary methodSummary = new MethodSummary(md);
2969
2970       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
2971       // curMethodInfo = methodInfo;
2972
2973       System.out.println();
2974       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
2975
2976       constructHierarchyGraph(md, hierarchyGraph);
2977
2978       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
2979       // MethodSummary prevMethodSummary = getMethodSummary(md);
2980
2981       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
2982
2983         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
2984         // mapDescToLocationSummary.put(md, methodSummary);
2985
2986         // results for callee changed, so enqueue dependents caller for
2987         // further analysis
2988         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
2989         while (depsItr.hasNext()) {
2990           MethodDescriptor methodNext = depsItr.next();
2991           if (!methodDescriptorsToVisitStack.contains(methodNext)
2992               && methodDescriptorToVistSet.contains(methodNext)) {
2993             methodDescriptorsToVisitStack.add(methodNext);
2994           }
2995         }
2996
2997       }
2998
2999     }
3000
3001     setupToAnalyze();
3002     while (!toAnalyzeIsEmpty()) {
3003       ClassDescriptor cd = toAnalyzeNext();
3004       HierarchyGraph graph = getHierarchyGraph(cd);
3005       for (Iterator iter = cd.getFields(); iter.hasNext();) {
3006         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
3007         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
3008           graph.getHNode(fieldDesc);
3009         }
3010       }
3011     }
3012
3013     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
3014     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
3015       Descriptor key = (Descriptor) iterator.next();
3016       HierarchyGraph graph = getHierarchyGraph(key);
3017
3018       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
3019       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
3020         HNode node = (HNode) iterator2.next();
3021         if (!node.isSkeleton() && !node.isCombinationNode()) {
3022           if (graph.getIncomingNodeSet(node).size() == 0) {
3023             nodeToBeConnected.add(node);
3024           }
3025         }
3026       }
3027
3028       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
3029         HNode node = (HNode) iterator2.next();
3030         System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
3031         graph.addEdge(graph.getHNode(TOPDESC), node);
3032       }
3033
3034     }
3035
3036   }
3037
3038   private HierarchyGraph getHierarchyGraph(Descriptor d) {
3039     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
3040       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
3041     }
3042     return mapDescriptorToHierarchyGraph.get(d);
3043   }
3044
3045   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
3046
3047     // visit each node of method flow graph
3048     FlowGraph fg = getFlowGraph(md);
3049     // Set<FlowNode> nodeSet = fg.getNodeSet();
3050
3051     Set<FlowEdge> edgeSet = fg.getEdgeSet();
3052
3053     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
3054     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
3055       Descriptor desc = (Descriptor) iterator.next();
3056       methodGraph.getHNode(desc).setSkeleton(true);
3057     }
3058
3059     // for the method lattice, we need to look at the first element of
3060     // NTuple<Descriptor>
3061     boolean hasGlobalAccess = false;
3062     // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3063     // FlowNode originalSrcNode = (FlowNode) iterator.next();
3064     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
3065       FlowEdge edge = (FlowEdge) iterator.next();
3066
3067       FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple());
3068       Set<FlowNode> sourceNodeSet = new HashSet<FlowNode>();
3069       if (originalSrcNode instanceof FlowReturnNode) {
3070         FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
3071         System.out.println("rnode=" + rnode);
3072         Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
3073         for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) {
3074           NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator2.next();
3075           sourceNodeSet.add(fg.getFlowNode(nTuple));
3076           System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
3077         }
3078       } else {
3079         sourceNodeSet.add(originalSrcNode);
3080       }
3081
3082       // System.out.println("---sourceNodeSet=" + sourceNodeSet + "  from originalSrcNode="
3083       // + originalSrcNode);
3084
3085       for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) {
3086         FlowNode srcNode = (FlowNode) iterator3.next();
3087
3088         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
3089         Descriptor srcLocalDesc = srcNodeTuple.get(0);
3090
3091         if (srcLocalDesc instanceof InterDescriptor
3092             && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) {
3093
3094           if (srcNode.getCompositeLocation() == null) {
3095             continue;
3096           }
3097         }
3098
3099         // if the srcNode is started with the global descriptor
3100         // need to set as a skeleton node
3101         if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) {
3102           hasGlobalAccess = true;
3103         }
3104
3105         // Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(originalSrcNode);
3106         // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3107         // FlowEdge outEdge = (FlowEdge) iterator2.next();
3108         // FlowNode originalDstNode = outEdge.getDst();
3109         FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple());
3110
3111         Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
3112         if (originalDstNode instanceof FlowReturnNode) {
3113           FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
3114           // System.out.println("\n-returnNode=" + rnode);
3115           Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
3116           for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) {
3117             NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator4.next();
3118             dstNodeSet.add(fg.getFlowNode(nTuple));
3119             System.out.println("&&&DST fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
3120           }
3121         } else {
3122           dstNodeSet.add(originalDstNode);
3123         }
3124         // System.out.println("---dstNodeSet=" + dstNodeSet);
3125         for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) {
3126           FlowNode dstNode = (FlowNode) iterator4.next();
3127
3128           NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
3129           Descriptor dstLocalDesc = dstNodeTuple.get(0);
3130
3131           if (dstLocalDesc instanceof InterDescriptor
3132               && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) {
3133             if (dstNode.getCompositeLocation() == null) {
3134               System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode);
3135               continue;
3136             }
3137           }
3138
3139           // if (outEdge.getInitTuple().equals(srcNodeTuple)
3140           // && outEdge.getEndTuple().equals(dstNodeTuple)) {
3141
3142           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
3143           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
3144
3145           // //////////////////////////
3146           // inheritance check
3147           if (mapMethodDescToHighestOverriddenMethodDesc.containsKey(md)) {
3148
3149             MethodDescriptor highestOverriddenMethodDesc =
3150                 mapMethodDescToHighestOverriddenMethodDesc.get(md);
3151
3152             if (srcCurTuple.get(srcCurTuple.size() - 1).getSymbol().startsWith(PCLOC)) {
3153             }
3154
3155           }
3156           // //////////////////////////
3157
3158           System.out.println("-srcCurTuple=" + srcCurTuple + "  dstCurTuple=" + dstCurTuple
3159               + "  srcNode=" + srcNode + "   dstNode=" + dstNode);
3160
3161           // srcCurTuple = translateBaseTuple(srcNode, srcCurTuple);
3162           // dstCurTuple = translateBaseTuple(dstNode, dstCurTuple);
3163
3164           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
3165               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
3166
3167             // value flows between fields
3168             Descriptor desc = srcCurTuple.get(0);
3169             ClassDescriptor classDesc;
3170
3171             if (desc.equals(GLOBALDESC)) {
3172               classDesc = md.getClassDesc();
3173             } else {
3174               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
3175               classDesc = varDesc.getType().getClassDesc();
3176             }
3177             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
3178
3179           } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1)
3180               || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals(
3181                   dstCurTuple.get(0)))) {
3182
3183             // value flow between a primitive local var - a primitive local var or local var -
3184             // field
3185
3186             Descriptor srcDesc = srcCurTuple.get(0);
3187             Descriptor dstDesc = dstCurTuple.get(0);
3188
3189             methodGraph.addEdge(srcDesc, dstDesc);
3190
3191             if (fg.isParamDesc(srcDesc)) {
3192               methodGraph.setParamHNode(srcDesc);
3193             }
3194             if (fg.isParamDesc(dstDesc)) {
3195               methodGraph.setParamHNode(dstDesc);
3196             }
3197
3198           }
3199
3200           // }
3201           // }
3202
3203         }
3204
3205       }
3206
3207     }
3208
3209     // If the method accesses static fields
3210     // set hasGloabalAccess true in the method summary.
3211     if (hasGlobalAccess) {
3212       getMethodSummary(md).setHasGlobalAccess();
3213     }
3214     methodGraph.getHNode(GLOBALDESC).setSkeleton(true);
3215
3216     if (ssjava.getMethodContainingSSJavaLoop().equals(md)) {
3217       // if the current method contains the event loop
3218       // we need to set all nodes of the hierarchy graph as a skeleton node
3219       Set<HNode> hnodeSet = methodGraph.getNodeSet();
3220       for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) {
3221         HNode hnode = (HNode) iterator.next();
3222         hnode.setSkeleton(true);
3223       }
3224     }
3225
3226   }
3227
3228   private NTuple<Descriptor> translateBaseTuple(FlowNode flowNode, NTuple<Descriptor> inTuple) {
3229
3230     if (flowNode.getBaseTuple() != null) {
3231
3232       NTuple<Descriptor> translatedTuple = new NTuple<Descriptor>();
3233
3234       NTuple<Descriptor> baseTuple = flowNode.getBaseTuple();
3235
3236       for (int i = 0; i < baseTuple.size(); i++) {
3237         translatedTuple.add(baseTuple.get(i));
3238       }
3239
3240       for (int i = 1; i < inTuple.size(); i++) {
3241         translatedTuple.add(inTuple.get(i));
3242       }
3243
3244       System.out.println("------TRANSLATED " + inTuple + " -> " + translatedTuple);
3245       return translatedTuple;
3246
3247     } else {
3248       return inTuple;
3249     }
3250
3251   }
3252
3253   private MethodSummary getMethodSummary(MethodDescriptor md) {
3254     if (!mapDescToLocationSummary.containsKey(md)) {
3255       mapDescToLocationSummary.put(md, new MethodSummary(md));
3256     }
3257     return (MethodSummary) mapDescToLocationSummary.get(md);
3258   }
3259
3260   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
3261
3262     String classSymbol = cd.getSymbol();
3263     int idx = classSymbol.lastIndexOf("$");
3264     if (idx != -1) {
3265       classSymbol = classSymbol.substring(idx + 1);
3266     }
3267
3268     String pattern = "class " + classSymbol + " ";
3269     if (strLine.indexOf(pattern) != -1) {
3270       mapDescToDefinitionLine.put(cd, lineNum);
3271     }
3272   }
3273
3274   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
3275       int lineNum) {
3276     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
3277       MethodDescriptor md = (MethodDescriptor) iterator.next();
3278       String pattern = md.getMethodDeclaration();
3279       if (strLine.indexOf(pattern) != -1) {
3280         mapDescToDefinitionLine.put(md, lineNum);
3281         methodSet.remove(md);
3282         return;
3283       }
3284     }
3285
3286   }
3287
3288   private void readOriginalSourceFiles() {
3289
3290     SymbolTable classtable = state.getClassSymbolTable();
3291
3292     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
3293     classDescSet.addAll(classtable.getValueSet());
3294
3295     try {
3296       // inefficient implement. it may re-visit the same file if the file
3297       // contains more than one class definitions.
3298       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
3299         ClassDescriptor cd = (ClassDescriptor) iterator.next();
3300
3301         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
3302         methodSet.addAll(cd.getMethodTable().getValueSet());
3303
3304         String sourceFileName = cd.getSourceFileName();
3305         Vector<String> lineVec = new Vector<String>();
3306
3307         mapFileNameToLineVector.put(sourceFileName, lineVec);
3308
3309         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
3310         String strLine;
3311         int lineNum = 1;
3312         lineVec.add(""); // the index is started from 1.
3313         while ((strLine = in.readLine()) != null) {
3314           lineVec.add(lineNum, strLine);
3315           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
3316           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
3317           lineNum++;
3318         }
3319
3320       }
3321
3322     } catch (IOException e) {
3323       e.printStackTrace();
3324     }
3325
3326   }
3327
3328   private String generateLatticeDefinition(Descriptor desc) {
3329
3330     Set<String> sharedLocSet = new HashSet<String>();
3331
3332     SSJavaLattice<String> lattice = getLattice(desc);
3333     String rtr = "@LATTICE(\"";
3334
3335     Map<String, Set<String>> map = lattice.getTable();
3336     Set<String> keySet = map.keySet();
3337     boolean first = true;
3338     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
3339       String key = (String) iterator.next();
3340       if (!key.equals(lattice.getTopItem())) {
3341         Set<String> connectedSet = map.get(key);
3342
3343         if (connectedSet.size() == 1) {
3344           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
3345             if (!first) {
3346               rtr += ",";
3347             } else {
3348               rtr += "LOC,";
3349               first = false;
3350             }
3351             rtr += key;
3352             if (lattice.isSharedLoc(key)) {
3353               rtr += "," + key + "*";
3354             }
3355           }
3356         }
3357
3358         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
3359           String loc = (String) iterator2.next();
3360           if (!loc.equals(lattice.getBottomItem())) {
3361             if (!first) {
3362               rtr += ",";
3363             } else {
3364               rtr += "LOC,";
3365               first = false;
3366             }
3367             rtr += loc + "<" + key;
3368             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
3369               rtr += "," + key + "*";
3370               sharedLocSet.add(key);
3371             }
3372             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
3373               rtr += "," + loc + "*";
3374               sharedLocSet.add(loc);
3375             }
3376
3377           }
3378         }
3379       }
3380     }
3381
3382     if (desc instanceof MethodDescriptor) {
3383       System.out.println("#EXTRA LOC DECLARATION GEN=" + desc);
3384
3385       MethodDescriptor md = (MethodDescriptor) desc;
3386       MethodSummary methodSummary = getMethodSummary(md);
3387
3388       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
3389       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc) && returnType != null
3390           && (!returnType.isVoid())) {
3391         CompositeLocation returnLoc = methodSummary.getRETURNLoc();
3392         if (returnLoc.getSize() == 1) {
3393           String returnLocStr = generateLocationAnnoatation(methodSummary.getRETURNLoc());
3394           if (rtr.indexOf(returnLocStr) == -1) {
3395             rtr += "," + returnLocStr;
3396           }
3397         }
3398       }
3399       rtr += "\")";
3400
3401       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) {
3402         if (returnType != null && (!returnType.isVoid())) {
3403           rtr +=
3404               "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")";
3405         }
3406
3407         CompositeLocation pcLoc = methodSummary.getPCLoc();
3408         if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
3409           rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
3410         }
3411       }
3412
3413       if (!md.isStatic()) {
3414         rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")";
3415       }
3416       rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")";
3417
3418     } else {
3419       rtr += "\")";
3420     }
3421
3422     return rtr;
3423   }
3424
3425   private void generateAnnoatedCode() {
3426
3427     readOriginalSourceFiles();
3428
3429     setupToAnalyze();
3430     while (!toAnalyzeIsEmpty()) {
3431       ClassDescriptor cd = toAnalyzeNext();
3432
3433       setupToAnalazeMethod(cd);
3434
3435       String sourceFileName = cd.getSourceFileName();
3436
3437       if (cd.isInterface()) {
3438         continue;
3439       }
3440
3441       int classDefLine = mapDescToDefinitionLine.get(cd);
3442       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
3443
3444       LocationSummary fieldLocSummary = getLocationSummary(cd);
3445
3446       String fieldLatticeDefStr = generateLatticeDefinition(cd);
3447       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
3448       sourceVec.set(classDefLine, annoatedSrc);
3449
3450       // generate annotations for field declarations
3451       // Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
3452       Map<String, String> mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName();
3453
3454       for (Iterator iter = cd.getFields(); iter.hasNext();) {
3455         FieldDescriptor fd = (FieldDescriptor) iter.next();
3456
3457         String locAnnotationStr;
3458         // CompositeLocation inferLoc = inferLocMap.get(fd);
3459         String locName = mapFieldNameToLocName.get(fd.getSymbol());
3460
3461         if (locName != null) {
3462           // infer loc is null if the corresponding field is static and final
3463           // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
3464           locAnnotationStr = "@LOC(\"" + locName + "\")";
3465           int fdLineNum = fd.getLineNum();
3466           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
3467           String fieldDeclaration = fd.toString();
3468           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
3469           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
3470           sourceVec.set(fdLineNum, annoatedStr);
3471         }
3472
3473       }
3474
3475       while (!toAnalyzeMethodIsEmpty()) {
3476         MethodDescriptor md = toAnalyzeMethodNext();
3477
3478         if (!ssjava.needTobeAnnotated(md)) {
3479           continue;
3480         }
3481
3482         SSJavaLattice<String> methodLattice = md2lattice.get(md);
3483         if (methodLattice != null) {
3484
3485           int methodDefLine = md.getLineNum();
3486
3487           // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
3488           // Map<Descriptor, CompositeLocation> methodInferLocMap =
3489           // methodLocInfo.getMapDescToInferLocation();
3490
3491           MethodSummary methodSummary = getMethodSummary(md);
3492
3493           Map<Descriptor, CompositeLocation> mapVarDescToInferLoc =
3494               methodSummary.getMapVarDescToInferCompositeLocation();
3495           System.out.println("-----md=" + md);
3496           System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc);
3497
3498           Set<Descriptor> localVarDescSet = mapVarDescToInferLoc.keySet();
3499
3500           Set<String> localLocElementSet = methodLattice.getElementSet();
3501
3502           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
3503             Descriptor localVarDesc = (Descriptor) iterator.next();
3504             System.out.println("-------localVarDesc=" + localVarDesc);
3505             CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc);
3506
3507             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
3508             if (!localLocElementSet.contains(localLocIdentifier)) {
3509               methodLattice.put(localLocIdentifier);
3510             }
3511
3512             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
3513
3514             if (!isParameter(md, localVarDesc)) {
3515               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
3516                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
3517                 String orgSourceLine = sourceVec.get(varLineNum);
3518                 System.out.println("varLineNum=" + varLineNum + "  org src=" + orgSourceLine);
3519                 int idx =
3520                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
3521                 System.out.println("idx=" + idx
3522                     + "  generateVarDeclaration((VarDescriptor) localVarDesc)="
3523                     + generateVarDeclaration((VarDescriptor) localVarDesc));
3524                 assert (idx != -1);
3525                 String annoatedStr =
3526                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
3527                         + orgSourceLine.substring(idx);
3528                 sourceVec.set(varLineNum, annoatedStr);
3529               }
3530             } else {
3531               String methodDefStr = sourceVec.get(methodDefLine);
3532
3533               int idx =
3534                   getParamLocation(methodDefStr,
3535                       generateVarDeclaration((VarDescriptor) localVarDesc));
3536               System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc
3537                   + " idx=" + idx);
3538               assert (idx != -1);
3539
3540               String annoatedStr =
3541                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
3542                       + methodDefStr.substring(idx);
3543               sourceVec.set(methodDefLine, annoatedStr);
3544             }
3545
3546           }
3547
3548           // check if the lattice has to have the location type for the this
3549           // reference...
3550
3551           // boolean needToAddthisRef = hasThisReference(md);
3552           // if (localLocElementSet.contains("this")) {
3553           // methodLattice.put("this");
3554           // }
3555
3556           String methodLatticeDefStr = generateLatticeDefinition(md);
3557           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
3558           sourceVec.set(methodDefLine, annoatedStr);
3559
3560         }
3561       }
3562
3563     }
3564
3565     codeGen();
3566   }
3567
3568   private boolean hasThisReference(MethodDescriptor md) {
3569
3570     FlowGraph fg = getFlowGraph(md);
3571     Set<FlowNode> nodeSet = fg.getNodeSet();
3572     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3573       FlowNode flowNode = (FlowNode) iterator.next();
3574       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
3575         return true;
3576       }
3577     }
3578
3579     return false;
3580   }
3581
3582   private int getParamLocation(String methodStr, String paramStr) {
3583
3584     String pattern = paramStr + ",";
3585
3586     int idx = methodStr.indexOf(pattern);
3587     if (idx != -1) {
3588       return idx;
3589     } else {
3590       pattern = paramStr + ")";
3591       return methodStr.indexOf(pattern);
3592     }
3593
3594   }
3595
3596   private String generateVarDeclaration(VarDescriptor varDesc) {
3597
3598     TypeDescriptor td = varDesc.getType();
3599     String rtr = td.toString();
3600     if (td.isArray()) {
3601       for (int i = 0; i < td.getArrayCount(); i++) {
3602         rtr += "[]";
3603       }
3604     }
3605     rtr += " " + varDesc.getName();
3606     return rtr;
3607
3608   }
3609
3610   private String generateLocationAnnoatation(CompositeLocation loc) {
3611     String rtr = "";
3612     // method location
3613     Location methodLoc = loc.get(0);
3614     rtr += methodLoc.getLocIdentifier();
3615
3616     for (int i = 1; i < loc.getSize(); i++) {
3617       Location element = loc.get(i);
3618       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
3619     }
3620
3621     return rtr;
3622   }
3623
3624   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
3625     return getFlowGraph(md).isParamDesc(localVarDesc);
3626   }
3627
3628   private String extractFileName(String fileName) {
3629     int idx = fileName.lastIndexOf("/");
3630     if (idx == -1) {
3631       return fileName;
3632     } else {
3633       return fileName.substring(idx + 1);
3634     }
3635
3636   }
3637
3638   private void codeGen() {
3639
3640     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
3641     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
3642       String orgFileName = (String) iterator.next();
3643       String outputFileName = extractFileName(orgFileName);
3644
3645       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
3646
3647       try {
3648
3649         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
3650         BufferedWriter out = new BufferedWriter(fileWriter);
3651
3652         for (int i = 0; i < sourceVec.size(); i++) {
3653           out.write(sourceVec.get(i));
3654           out.newLine();
3655         }
3656         out.close();
3657       } catch (IOException e) {
3658         e.printStackTrace();
3659       }
3660
3661     }
3662
3663   }
3664
3665   private void checkLattices() {
3666
3667     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
3668
3669     // current descriptors to visit in fixed-point interprocedural analysis,
3670     // prioritized by
3671     // dependency in the call graph
3672     methodDescriptorsToVisitStack.clear();
3673
3674     // descriptorListToAnalyze.removeFirst();
3675
3676     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
3677     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
3678
3679     while (!descriptorListToAnalyze.isEmpty()) {
3680       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
3681       checkLatticesOfVirtualMethods(md);
3682     }
3683
3684   }
3685
3686   private void debug_writeLatticeDotFile() {
3687     // generate lattice dot file
3688
3689     setupToAnalyze();
3690
3691     while (!toAnalyzeIsEmpty()) {
3692       ClassDescriptor cd = toAnalyzeNext();
3693
3694       setupToAnalazeMethod(cd);
3695
3696       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
3697       if (classLattice != null) {
3698         ssjava.writeLatticeDotFile(cd, null, classLattice);
3699         debug_printDescriptorToLocNameMapping(cd);
3700       }
3701
3702       while (!toAnalyzeMethodIsEmpty()) {
3703         MethodDescriptor md = toAnalyzeMethodNext();
3704         SSJavaLattice<String> methodLattice = md2lattice.get(md);
3705         if (methodLattice != null) {
3706           ssjava.writeLatticeDotFile(cd, md, methodLattice);
3707           debug_printDescriptorToLocNameMapping(md);
3708         }
3709       }
3710     }
3711
3712   }
3713
3714   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
3715
3716     LocationInfo info = getLocationInfo(desc);
3717     System.out.println("## " + desc + " ##");
3718     System.out.println(info.getMapDescToInferLocation());
3719     LocationInfo locInfo = getLocationInfo(desc);
3720     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
3721     System.out.println("###################");
3722
3723   }
3724
3725   private void calculateExtraLocations() {
3726
3727     LinkedList<MethodDescriptor> methodDescList = ssjava.getSortedDescriptors();
3728     for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) {
3729       MethodDescriptor md = (MethodDescriptor) iterator.next();
3730       if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
3731         calculateExtraLocations(md);
3732       }
3733     }
3734
3735   }
3736
3737   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
3738
3739     if (!md.isStatic()) {
3740       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3741       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3742
3743       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
3744         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
3745         if (!md.equals(mdCallee)) {
3746           checkConsistency(md, mdCallee);
3747         }
3748       }
3749
3750     }
3751
3752   }
3753
3754   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
3755
3756     // check that two lattice have the same relations between parameters(+PC
3757     // LOC, GLOBAL_LOC RETURN LOC)
3758
3759     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
3760     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
3761
3762     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
3763     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
3764
3765     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
3766     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
3767
3768     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
3769
3770     // add location types of paramters
3771     for (int idx = 0; idx < numParam; idx++) {
3772       list1.add(paramMap1.get(Integer.valueOf(idx)));
3773       list2.add(paramMap2.get(Integer.valueOf(idx)));
3774     }
3775
3776     // add program counter location
3777     list1.add(locInfo1.getPCLoc());
3778     list2.add(locInfo2.getPCLoc());
3779
3780     if (!md1.getReturnType().isVoid()) {
3781       // add return value location
3782       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
3783       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
3784       list1.add(rtrLoc1);
3785       list2.add(rtrLoc2);
3786     }
3787
3788     // add global location type
3789     if (md1.isStatic()) {
3790       CompositeLocation globalLoc1 =
3791           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
3792       CompositeLocation globalLoc2 =
3793           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
3794       list1.add(globalLoc1);
3795       list2.add(globalLoc2);
3796     }
3797
3798     for (int i = 0; i < list1.size(); i++) {
3799       CompositeLocation locA1 = list1.get(i);
3800       CompositeLocation locA2 = list2.get(i);
3801       for (int k = 0; k < list1.size(); k++) {
3802         if (i != k) {
3803           CompositeLocation locB1 = list1.get(k);
3804           CompositeLocation locB2 = list2.get(k);
3805           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
3806
3807           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
3808
3809           if (r1 != r2) {
3810             throw new Error("The method " + md1 + " is not consistent with the method " + md2
3811                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
3812                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
3813           }
3814         }
3815       }
3816     }
3817
3818   }
3819
3820   private String getSymbol(int idx, FlowNode node) {
3821     Descriptor desc = node.getDescTuple().get(idx);
3822     return desc.getSymbol();
3823   }
3824
3825   private Descriptor getDescriptor(int idx, FlowNode node) {
3826     Descriptor desc = node.getDescTuple().get(idx);
3827     return desc;
3828   }
3829
3830   private void calculatePCLOC(MethodDescriptor md) {
3831
3832     System.out.println("#CalculatePCLOC");
3833     MethodSummary methodSummary = getMethodSummary(md);
3834     FlowGraph fg = getFlowGraph(md);
3835     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3836
3837     // calculate the initial program counter location
3838     // PC location is higher than location types of parameters which has incoming flows.
3839
3840     Set<NTuple<Location>> paramLocTupleHavingInFlowSet = new HashSet<NTuple<Location>>();
3841     Set<Descriptor> paramDescNOTHavingInFlowSet = new HashSet<Descriptor>();
3842     // Set<FlowNode> paramNodeNOThavingInFlowSet = new HashSet<FlowNode>();
3843
3844     int numParams = fg.getNumParameters();
3845     for (int i = 0; i < numParams; i++) {
3846       FlowNode paramFlowNode = fg.getParamFlowNode(i);
3847       Descriptor prefix = paramFlowNode.getDescTuple().get(0);
3848       NTuple<Descriptor> paramDescTuple = paramFlowNode.getCurrentDescTuple();
3849       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
3850
3851       Set<FlowNode> inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix);
3852       if (inNodeToParamSet.size() > 0) {
3853         // parameter has in-value flows
3854
3855         for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) {
3856           FlowNode inNode = (FlowNode) iterator.next();
3857           Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(inNode);
3858           for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3859             FlowEdge flowEdge = (FlowEdge) iterator2.next();
3860             if (flowEdge.getEndTuple().startsWith(prefix)) {
3861               NTuple<Location> paramLocTupleWithIncomingFlow =
3862                   translateToLocTuple(md, flowEdge.getEndTuple());
3863               paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow);
3864             }
3865           }
3866         }
3867
3868         // paramLocTupleHavingInFlowSet.add(paramLocTuple);
3869       } else {
3870         // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple));
3871         paramDescNOTHavingInFlowSet.add(prefix);
3872       }
3873     }
3874
3875     System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet);
3876
3877     if (paramLocTupleHavingInFlowSet.size() > 0
3878         && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) {
3879
3880       // Here, generates a location in the method lattice that is higher than the
3881       // paramLocTupleHavingInFlowSet
3882       NTuple<Location> pcLocTuple =
3883           generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC);
3884
3885       NTuple<Descriptor> pcDescTuple = translateToDescTuple(pcLocTuple);
3886
3887       // System.out.println("pcLoc=" + pcLocTuple);
3888
3889       CompositeLocation curPCLoc = methodSummary.getPCLoc();
3890       if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) {
3891         methodSummary.setPCLoc(new CompositeLocation(pcLocTuple));
3892
3893         Set<FlowNode> flowNodeLowerthanPCLocSet = new HashSet<FlowNode>();
3894         GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
3895         // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of
3896         // parameters that do not have incoming flows
3897         for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) {
3898           FlowNode node = (FlowNode) iterator.next();
3899
3900           if (!(node instanceof FlowReturnNode)) {
3901             if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) {
3902               flowNodeLowerthanPCLocSet.add(node);
3903               fg.addValueFlowEdge(pcDescTuple, node.getDescTuple());
3904
3905               subGlobalFlowGraph.addValueFlowEdge(pcLocTuple,
3906                   translateToLocTuple(md, node.getDescTuple()));
3907             }
3908           } else {
3909             System.out.println("***SKIP PCLOC -> RETURNLOC=" + node);
3910           }
3911
3912         }
3913         fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true);
3914
3915         if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) {
3916           System.out.println("#########################################");
3917           for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) {
3918             FlowNode lowerNode = (FlowNode) iterator.next();
3919             if (lowerNode.getDescTuple().size() == 1 && lowerNode.getCompositeLocation() == null) {
3920               NTuple<Location> lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple());
3921               CompositeLocation newComp =
3922                   calculateCompositeLocationFromSubGlobalGraph(md, lowerNode);
3923               if (newComp != null) {
3924                 subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0),
3925                     newComp);
3926                 lowerNode.setCompositeLocation(newComp);
3927                 System.out.println("NEW COMP LOC=" + newComp + "    to lowerNode=" + lowerNode);
3928               }
3929
3930             }
3931
3932           }
3933         }
3934
3935       }
3936
3937     }
3938   }
3939
3940   private int countFirstDescriptorSetSize(Set<NTuple<Location>> set) {
3941
3942     Set<Descriptor> descSet = new HashSet<Descriptor>();
3943
3944     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3945       NTuple<Location> locTuple = (NTuple<Location>) iterator.next();
3946       descSet.add(locTuple.get(0).getLocDescriptor());
3947     }
3948
3949     return descSet.size();
3950   }
3951
3952   private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg,
3953       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
3954
3955     int numParam = fg.getNumParameters();
3956     // int size = paramLocTupleHavingInFlowSet.size();
3957     int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet);
3958
3959     System.out.println("numParam=" + numParam + "     size=" + size);
3960
3961     // if (!md.isStatic()) {
3962     //
3963     // // if the method is not static && there is a parameter composite location &&
3964     // // it is started with 'this',
3965     // // paramLocTupleHavingInFlowSet need to have 'this' parameter.
3966     //
3967     // FlowNode thisParamNode = fg.getParamFlowNode(0);
3968     // NTuple<Location> thisParamLocTuple =
3969     // translateToLocTuple(md, thisParamNode.getCurrentDescTuple());
3970     //
3971     // if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) {
3972     //
3973     // for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
3974     // NTuple<Location> paramTuple = (NTuple<Location>) iterator.next();
3975     // if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) {
3976     // // paramLocTupleHavingInFlowSet.add(thisParamLocTuple);
3977     // // break;
3978     // size++;
3979     // }
3980     // }
3981     //
3982     // }
3983     // }
3984
3985     if (size == numParam) {
3986       return true;
3987     } else {
3988       return false;
3989     }
3990
3991   }
3992
3993   private void calculateRETURNLOC(MethodDescriptor md) {
3994
3995     System.out.println("#calculateRETURNLOC= " + md);
3996
3997     // calculate a return location:
3998     // the return location type is lower than all parameters and the location of return values
3999     MethodSummary methodSummary = getMethodSummary(md);
4000     // if (methodSummary.getRETURNLoc() != null) {
4001     // System.out.println("$HERE?");
4002     // return;
4003     // }
4004
4005     FlowGraph fg = getFlowGraph(md);
4006     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
4007     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
4008
4009     if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
4010       // first, generate the set of return value location types that starts
4011       // with 'this' reference
4012
4013       Set<FlowNode> paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md);
4014       // System.out.println("paramFlowNodeFlowingToReturnValueSet="
4015       // + paramFlowNodeFlowingToReturnValueSet);
4016
4017       Set<NTuple<Location>> tupleToBeHigherThanReturnLocSet = new HashSet<NTuple<Location>>();
4018       for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) {
4019         FlowNode fn = (FlowNode) iterator.next();
4020         NTuple<Descriptor> paramDescTuple = fn.getCurrentDescTuple();
4021         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple));
4022       }
4023
4024       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
4025       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
4026         FlowNode returnNode = (FlowNode) iterator.next();
4027         NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
4028         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple));
4029       }
4030       System.out.println("-flow graph's returnNodeSet=" + returnNodeSet);
4031       System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet);
4032
4033       // Here, generates a return location in the method lattice that is lower than the
4034       // locFlowingToReturnValueSet
4035       NTuple<Location> returnLocTuple =
4036           generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC);
4037
4038       // System.out.println("returnLocTuple=" + returnLocTuple);
4039       NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnLocTuple);
4040       CompositeLocation curReturnLoc = methodSummary.getRETURNLoc();
4041       if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) {
4042         methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple));
4043
4044         for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) {
4045           NTuple<Location> higherTuple = (NTuple<Location>) iterator.next();
4046           fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple);
4047         }
4048         fg.getFlowNode(returnDescTuple).setSkeleton(true);
4049
4050       }
4051
4052       // makes sure that PCLOC is higher than RETURNLOC
4053       CompositeLocation pcLoc = methodSummary.getPCLoc();
4054       if (!pcLoc.get(0).isTop()) {
4055         NTuple<Descriptor> pcLocDescTuple = translateToDescTuple(pcLoc.getTuple());
4056         fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple);
4057       }
4058
4059     }
4060
4061   }
4062
4063   private void calculateExtraLocations(MethodDescriptor md) {
4064     // calcualte pcloc, returnloc,...
4065
4066     System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md);
4067
4068     calculatePCLOC(md);
4069     calculateRETURNLOC(md);
4070
4071   }
4072
4073   private NTuple<Location> generateLocTupleRelativeTo(MethodDescriptor md,
4074       Set<NTuple<Location>> paramLocTupleHavingInFlowSet, String locNamePrefix) {
4075
4076     // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet);
4077
4078     NTuple<Location> higherLocTuple = new NTuple<Location>();
4079
4080     VarDescriptor thisVarDesc = md.getThis();
4081     // check if all paramter loc tuple is started with 'this' reference
4082     boolean hasParamNotStartedWithThisRef = false;
4083
4084     int minSize = 0;
4085
4086     Set<NTuple<Location>> paramLocTupleStartedWithThis = new HashSet<NTuple<Location>>();
4087
4088     next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
4089       NTuple<Location> paramLocTuple = (NTuple<Location>) iterator.next();
4090       Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor();
4091       if (!paramLocalDesc.equals(thisVarDesc)) {
4092
4093         Set<FlowNode> inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc);
4094         for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
4095           FlowNode flowNode = (FlowNode) iterator2.next();
4096           if (flowNode.getDescTuple().startsWith(thisVarDesc)) {
4097             // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS");
4098             continue next;
4099           }
4100         }
4101         hasParamNotStartedWithThisRef = true;
4102
4103       } else if (paramLocTuple.size() > 1) {
4104         paramLocTupleStartedWithThis.add(paramLocTuple);
4105         if (minSize == 0 || minSize > paramLocTuple.size()) {
4106           minSize = paramLocTuple.size();
4107         }
4108       }
4109     }
4110
4111     // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis);
4112     Descriptor enclosingDesc = md;
4113     if (hasParamNotStartedWithThisRef) {
4114       // in this case, PCLOC will be the local location
4115     } else {
4116       // all parameter is started with 'this', so PCLOC will be set relative to the composite
4117       // location started with 'this'.
4118       // for (int idx = 0; idx < minSize - 1; idx++) {
4119       for (int idx = 0; idx < 1; idx++) {
4120         Set<Descriptor> locDescSet = new HashSet<Descriptor>();
4121         Location curLoc = null;
4122         NTuple<Location> paramLocTuple = null;
4123         for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) {
4124           paramLocTuple = (NTuple<Location>) iterator.next();
4125           // System.out.println("-----paramLocTuple=" + paramLocTuple + "  idx=" + idx);
4126           curLoc = paramLocTuple.get(idx);
4127           Descriptor locDesc = curLoc.getLocDescriptor();
4128           locDescSet.add(locDesc);
4129         }
4130         // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx);
4131         if (locDescSet.size() != 1) {
4132           break;
4133         }
4134         Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor());
4135         System.out.println("newLocElement" + newLocElement);
4136         higherLocTuple.add(newLocElement);
4137         enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor());
4138       }
4139
4140     }
4141
4142     String locIdentifier = locNamePrefix + (locSeed++);
4143     NameDescriptor locDesc = new NameDescriptor(locIdentifier);
4144     Location newLoc = new Location(enclosingDesc, locDesc);
4145     higherLocTuple.add(newLoc);
4146     System.out.println("---new loc tuple=" + higherLocTuple);
4147
4148     return higherLocTuple;
4149
4150   }
4151
4152   public ClassDescriptor getClassTypeDescriptor(Descriptor in) {
4153
4154     if (in instanceof VarDescriptor) {
4155       return ((VarDescriptor) in).getType().getClassDesc();
4156     } else if (in instanceof FieldDescriptor) {
4157       return ((FieldDescriptor) in).getType().getClassDesc();
4158     }
4159     // else if (in instanceof LocationDescriptor) {
4160     // // here is the case that the descriptor 'in' is the last element of the assigned composite
4161     // // location
4162     // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc();
4163     // }
4164     else {
4165       return null;
4166     }
4167
4168   }
4169
4170   private Set<NTuple<Location>> calculateHighestLocTupleSet(
4171       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
4172
4173     Set<NTuple<Location>> highestSet = new HashSet<NTuple<Location>>();
4174
4175     Iterator<NTuple<Location>> iterator = paramLocTupleHavingInFlowSet.iterator();
4176     NTuple<Location> highest = iterator.next();
4177
4178     for (; iterator.hasNext();) {
4179       NTuple<Location> curLocTuple = (NTuple<Location>) iterator.next();
4180       if (isHigherThan(curLocTuple, highest)) {
4181         // System.out.println(curLocTuple + " is greater than " + highest);
4182         highest = curLocTuple;
4183       }
4184     }
4185
4186     highestSet.add(highest);
4187
4188     MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor();
4189     VarDescriptor thisVarDesc = md.getThis();
4190
4191     // System.out.println("highest=" + highest);
4192
4193     for (Iterator<NTuple<Location>> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) {
4194       NTuple<Location> curLocTuple = iter.next();
4195
4196       if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) {
4197
4198         // System.out.println("add it to the highest set=" + curLocTuple);
4199         highestSet.add(curLocTuple);
4200
4201       }
4202     }
4203
4204     return highestSet;
4205
4206   }
4207
4208   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
4209     Set<String> higherLocSet = new HashSet<String>();
4210
4211     Set<String> locSet = lattice.getTable().keySet();
4212     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
4213       String element = (String) iterator.next();
4214       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
4215         higherLocSet.add(element);
4216       }
4217     }
4218     return higherLocSet;
4219   }
4220
4221   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
4222       Set<CompositeLocation> set) {
4223
4224     CompositeLocation lowest = set.iterator().next();
4225
4226     if (set.size() == 1) {
4227       return lowest;
4228     }
4229
4230     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4231       CompositeLocation loc = (CompositeLocation) iterator.next();
4232
4233       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
4234         // if there is a case where composite locations are incomparable, just
4235         // return null
4236         return null;
4237       }
4238
4239       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
4240         lowest = loc;
4241       }
4242     }
4243     return lowest;
4244   }
4245
4246   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
4247       CompositeLocation comp2) {
4248
4249     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
4250
4251     for (int idx = 0; idx < size; idx++) {
4252       Location loc1 = comp1.get(idx);
4253       Location loc2 = comp2.get(idx);
4254
4255       Descriptor desc1 = loc1.getDescriptor();
4256       Descriptor desc2 = loc2.getDescriptor();
4257
4258       if (!desc1.equals(desc2)) {
4259         throw new Error("Fail to compare " + comp1 + " and " + comp2);
4260       }
4261
4262       String symbol1 = loc1.getLocIdentifier();
4263       String symbol2 = loc2.getLocIdentifier();
4264
4265       SSJavaLattice<String> lattice;
4266       if (idx == 0) {
4267         lattice = methodLattice;
4268       } else {
4269         lattice = getLattice(desc1);
4270       }
4271
4272       if (symbol1.equals(symbol2)) {
4273         continue;
4274       } else if (!lattice.isComparable(symbol1, symbol2)) {
4275         return false;
4276       }
4277
4278     }
4279
4280     return true;
4281   }
4282
4283   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
4284       CompositeLocation comp2) {
4285
4286     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
4287
4288     for (int idx = 0; idx < size; idx++) {
4289       Location loc1 = comp1.get(idx);
4290       Location loc2 = comp2.get(idx);
4291
4292       Descriptor desc1 = loc1.getDescriptor();
4293       Descriptor desc2 = loc2.getDescriptor();
4294
4295       if (!desc1.equals(desc2)) {
4296         throw new Error("Fail to compare " + comp1 + " and " + comp2);
4297       }
4298
4299       String symbol1 = loc1.getLocIdentifier();
4300       String symbol2 = loc2.getLocIdentifier();
4301
4302       SSJavaLattice<String> lattice;
4303       if (idx == 0) {
4304         lattice = methodLattice;
4305       } else {
4306         lattice = getLattice(desc1);
4307       }
4308
4309       if (symbol1.equals(symbol2)) {
4310         continue;
4311       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
4312         return true;
4313       } else {
4314         return false;
4315       }
4316
4317     }
4318
4319     return false;
4320   }
4321
4322   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
4323
4324     if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) {
4325       mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md));
4326     }
4327     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
4328   }
4329
4330   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
4331       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
4332
4333     System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0));
4334     // if the parameter A reaches to the parameter B
4335     // then, add an edge the argument A -> the argument B to the caller's flow
4336     // graph
4337
4338     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
4339     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
4340     int numParam = calleeFlowGraph.getNumParameters();
4341
4342     for (int i = 0; i < numParam; i++) {
4343       for (int k = 0; k < numParam; k++) {
4344
4345         if (i != k) {
4346
4347           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
4348           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
4349
4350           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
4351           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
4352
4353           // check if the callee propagates an ordering constraints through
4354           // parameters
4355
4356           // Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
4357           Set<FlowNode> localReachSet =
4358               calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple());
4359
4360           NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
4361           NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
4362
4363           // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
4364           // + paramDescTuple2);
4365           // System.out.println("-- localReachSet from param1=" + localReachSet);
4366
4367           if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
4368             // if two parameters share the same prefix
4369             // it already has been assigned to a composite location
4370             // so we don't need to add an additional ordering relation caused by these two
4371             // paramters.
4372             continue;
4373           }
4374
4375           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0
4376               && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) {
4377             // need to propagate an ordering relation s.t. arg1 is higher
4378             // than arg2
4379             // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
4380
4381             // add a new flow between the corresponding arguments.
4382             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
4383             // System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
4384
4385             // System.out
4386             // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
4387
4388           }
4389
4390           // System.out.println();
4391         }
4392       }
4393     }
4394
4395     // if a parameter has a composite location and the first element of the parameter location
4396     // matches the callee's 'this'
4397     // we have a more specific constraint: the caller's corresponding argument is higher than the
4398     // parameter location which is translated into the caller
4399
4400     for (int idx = 0; idx < numParam; idx++) {
4401       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4402       CompositeLocation compLoc = paramNode.getCompositeLocation();
4403       System.out.println("paramNode=" + paramNode + "   compLoc=" + compLoc);
4404       if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) {
4405         System.out.println("$$$COMPLOC CASE=" + compLoc + "  idx=" + idx);
4406
4407         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
4408         System.out.println("--- argTuple=" + argTuple + " current compLoc="
4409             + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation());
4410
4411         NTuple<Descriptor> translatedParamTuple =
4412             translateCompositeLocationToCaller(idx, min, compLoc);
4413         System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
4414         callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
4415
4416         Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
4417         for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
4418           NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
4419           callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple);
4420         }
4421
4422       }
4423     }
4424
4425   }
4426
4427   private boolean containsPrefix(Descriptor prefixDesc, Set<FlowNode> set) {
4428
4429     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4430       FlowNode flowNode = (FlowNode) iterator.next();
4431       if (flowNode.getDescTuple().startsWith(prefixDesc)) {
4432         System.out.println("FOUND=" + flowNode);
4433         return true;
4434       }
4435     }
4436     return false;
4437   }
4438
4439   private NTuple<Descriptor> translateCompositeLocationToCaller(int idx, MethodInvokeNode min,
4440       CompositeLocation compLocForParam1) {
4441
4442     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
4443
4444     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
4445     for (int i = 0; i < baseTuple.size(); i++) {
4446       tuple.add(baseTuple.get(i));
4447     }
4448
4449     for (int i = 1; i < compLocForParam1.getSize(); i++) {
4450       Location loc = compLocForParam1.get(i);
4451       tuple.add(loc.getLocDescriptor());
4452     }
4453
4454     return tuple;
4455   }
4456
4457   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
4458
4459     System.out.println("generateCompositeLocation=" + prefixLocTuple);
4460
4461     CompositeLocation newCompLoc = new CompositeLocation();
4462     for (int i = 0; i < prefixLocTuple.size(); i++) {
4463       newCompLoc.addLocation(prefixLocTuple.get(i));
4464     }
4465
4466     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
4467
4468     ClassDescriptor enclosingDescriptor;
4469     if (lastDescOfPrefix instanceof FieldDescriptor) {
4470       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4471       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4472     } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
4473       MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
4474       enclosingDescriptor = currentMethodDesc.getClassDesc();
4475     } else {
4476       // var descriptor case
4477       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4478     }
4479     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4480
4481     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4482     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4483
4484     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4485     newLoc.setLocDescriptor(newLocDescriptor);
4486     newCompLoc.addLocation(newLoc);
4487
4488     // System.out.println("--newCompLoc=" + newCompLoc);
4489     return newCompLoc;
4490   }
4491
4492   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
4493       NTuple<Descriptor> paramPrefix) {
4494
4495     System.out.println("generateCompositeLocation=" + paramPrefix);
4496
4497     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
4498
4499     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
4500     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
4501     // + lastDescOfPrefix.getClass());
4502     ClassDescriptor enclosingDescriptor;
4503     if (lastDescOfPrefix instanceof FieldDescriptor) {
4504       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4505       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4506     } else {
4507       // var descriptor case
4508       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4509     }
4510     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4511
4512     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4513     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4514
4515     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4516     newLoc.setLocDescriptor(newLocDescriptor);
4517     newCompLoc.addLocation(newLoc);
4518
4519     // System.out.println("--newCompLoc=" + newCompLoc);
4520     return newCompLoc;
4521   }
4522
4523   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
4524       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
4525
4526     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
4527
4528     for (int i = 0; i < callerPrefixList.size(); i++) {
4529       NTuple<Descriptor> prefix = callerPrefixList.get(i);
4530       if (prefix.startsWith(baseRef)) {
4531         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
4532         calleePrefix.add(mdCallee.getThis());
4533         for (int k = 1; k < prefix.size(); k++) {
4534           calleePrefix.add(prefix.get(k));
4535         }
4536         calleePrefixList.add(calleePrefix);
4537       }
4538     }
4539
4540     return calleePrefixList;
4541
4542   }
4543
4544   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
4545
4546     CompositeLocation compLoc = new CompositeLocation();
4547
4548     Descriptor enclosingDescriptor = md;
4549
4550     for (int i = 0; i < tuple.size(); i++) {
4551       Descriptor curDescriptor = tuple.get(i);
4552       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
4553       locElement.setLocDescriptor(curDescriptor);
4554       compLoc.addLocation(locElement);
4555
4556       if (curDescriptor instanceof VarDescriptor) {
4557         enclosingDescriptor = md.getClassDesc();
4558       } else if (curDescriptor instanceof FieldDescriptor) {
4559         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
4560       } else if (curDescriptor instanceof NameDescriptor) {
4561         // it is "GLOBAL LOC" case!
4562         enclosingDescriptor = GLOBALDESC;
4563       } else if (curDescriptor instanceof InterDescriptor) {
4564         enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor);
4565       } else {
4566         enclosingDescriptor = null;
4567       }
4568
4569     }
4570
4571     return compLoc;
4572   }
4573
4574   private LocationDescriptor generateNewLocationDescriptor() {
4575     return new LocationDescriptor("Loc" + (locSeed++));
4576   }
4577
4578   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
4579
4580     // return the index where the prefix shared by tuple1 and tuple2 is ended
4581     // if there is no prefix shared by both of them, return -1
4582
4583     int minSize = tuple1.size();
4584     if (minSize > tuple2.size()) {
4585       minSize = tuple2.size();
4586     }
4587
4588     int idx = -1;
4589     for (int i = 0; i < minSize; i++) {
4590       if (!tuple1.get(i).equals(tuple2.get(i))) {
4591         break;
4592       } else {
4593         idx++;
4594       }
4595     }
4596
4597     return idx;
4598   }
4599
4600   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
4601       NTuple<Location> tuple) {
4602
4603     // first, retrieve inferred location by the local var descriptor
4604     CompositeLocation inferLoc = new CompositeLocation();
4605
4606     CompositeLocation localVarInferLoc =
4607         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
4608
4609     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
4610
4611     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
4612       inferLoc.addLocation(localVarInferLoc.get(i));
4613     }
4614
4615     for (int i = 1; i < tuple.size(); i++) {
4616       Location cur = tuple.get(i);
4617       Descriptor enclosingDesc = cur.getDescriptor();
4618       Descriptor curDesc = cur.getLocDescriptor();
4619
4620       Location inferLocElement;
4621       if (curDesc == null) {
4622         // in this case, we have a newly generated location.
4623         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
4624       } else {
4625         String fieldLocSymbol =
4626             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
4627         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
4628         inferLocElement.setLocDescriptor(curDesc);
4629       }
4630
4631       inferLoc.addLocation(inferLocElement);
4632
4633     }
4634
4635     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
4636     return inferLoc;
4637   }
4638
4639   public LocationInfo getLocationInfo(Descriptor d) {
4640     if (d instanceof MethodDescriptor) {
4641       return getMethodLocationInfo((MethodDescriptor) d);
4642     } else {
4643       return getFieldLocationInfo((ClassDescriptor) d);
4644     }
4645   }
4646
4647   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
4648
4649     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
4650       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
4651     }
4652
4653     return mapMethodDescToMethodLocationInfo.get(md);
4654
4655   }
4656
4657   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
4658
4659     if (!mapClassToLocationInfo.containsKey(cd)) {
4660       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
4661     }
4662
4663     return mapClassToLocationInfo.get(cd);
4664
4665   }
4666
4667   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
4668       NTuple<Location> prefix, NTuple<Location> element) {
4669
4670     if (!map.containsKey(prefix)) {
4671       map.put(prefix, new HashSet<NTuple<Location>>());
4672     }
4673     map.get(prefix).add(element);
4674   }
4675
4676   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
4677     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
4678       Descriptor desc = (Descriptor) iterator.next();
4679
4680       if (desc.equals(LocationInference.GLOBALDESC)) {
4681         return true;
4682       } else if (desc instanceof VarDescriptor) {
4683         if (!((VarDescriptor) desc).getType().isPrimitive()) {
4684           return true;
4685         }
4686       } else if (desc instanceof FieldDescriptor) {
4687         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
4688           return true;
4689         }
4690       }
4691
4692     }
4693     return false;
4694   }
4695
4696   public SSJavaLattice<String> getLattice(Descriptor d) {
4697     if (d instanceof MethodDescriptor) {
4698       return getMethodLattice((MethodDescriptor) d);
4699     } else {
4700       return getFieldLattice((ClassDescriptor) d);
4701     }
4702   }
4703
4704   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
4705     if (!md2lattice.containsKey(md)) {
4706       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4707     }
4708     return md2lattice.get(md);
4709   }
4710
4711   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
4712     md2lattice.put(md, lattice);
4713   }
4714
4715   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
4716       int idx) {
4717
4718     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
4719     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
4720
4721     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
4722         && dstCurTuple.size() > (idx + 1)) {
4723       // value flow between fields: we don't need to add a binary relation
4724       // for this case
4725
4726       Descriptor desc = srcCurTuple.get(idx);
4727       ClassDescriptor classDesc;
4728
4729       if (idx == 0) {
4730         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
4731       } else {
4732         if (desc instanceof FieldDescriptor) {
4733           classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
4734         } else {
4735           // this case is that the local variable has a composite location assignment
4736           // the following element after the composite location to the local variable
4737           // has the enclosing descriptor of the local variable
4738           Descriptor localDesc = srcNode.getDescTuple().get(0);
4739           classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
4740         }
4741       }
4742       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
4743
4744     } else {
4745
4746       Descriptor srcFieldDesc = srcCurTuple.get(idx);
4747       Descriptor dstFieldDesc = dstCurTuple.get(idx);
4748
4749       System.out.println("srcFieldDesc=" + srcFieldDesc + "  dstFieldDesc=" + dstFieldDesc
4750           + "   idx=" + idx);
4751       if (!srcFieldDesc.equals(dstFieldDesc)) {
4752         // add a new edge
4753         System.out.println("-ADD EDGE");
4754         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4755       } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) {
4756         System.out.println("-ADD EDGE");
4757         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4758       }
4759
4760     }
4761
4762   }
4763
4764   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
4765     if (!cd2lattice.containsKey(cd)) {
4766       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4767     }
4768     return cd2lattice.get(cd);
4769   }
4770
4771   public LinkedList<MethodDescriptor> computeMethodList() {
4772
4773     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
4774
4775     setupToAnalyze();
4776
4777     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
4778     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
4779
4780     while (!toAnalyzeIsEmpty()) {
4781       ClassDescriptor cd = toAnalyzeNext();
4782
4783       if (cd.getClassName().equals("Object")) {
4784         rootClassDescriptor = cd;
4785         // inheritanceTree = new InheritanceTree<ClassDescriptor>(cd);
4786       }
4787
4788       setupToAnalazeMethod(cd);
4789       temp_toanalyzeMethodList.removeAll(visited);
4790
4791       while (!toAnalyzeMethodIsEmpty()) {
4792         MethodDescriptor md = toAnalyzeMethodNext();
4793         if ((!visited.contains(md))
4794             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
4795
4796           // creates a mapping from a method descriptor to virtual methods
4797           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4798           if (md.isStatic()) {
4799             setPossibleCallees.add(md);
4800           } else {
4801             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
4802           }
4803
4804           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
4805           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
4806
4807           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
4808             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
4809             if ((!ssjava.isTrustMethod(calleemd))
4810                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))
4811                 && (!calleemd.getModifiers().isNative())) {
4812               if (!visited.contains(calleemd)) {
4813                 temp_toanalyzeMethodList.add(calleemd);
4814               }
4815               reachableCallee.add(calleemd);
4816               needToAnalyzeCalleeSet.add(calleemd);
4817             }
4818           }
4819
4820           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
4821
4822           visited.add(md);
4823
4824           toSort.add(md);
4825         }
4826       }
4827     }
4828
4829     return ssjava.topologicalSort(toSort);
4830
4831   }
4832
4833   public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
4834     // if the callee is transitively invoked from the caller
4835     // return true;
4836
4837     int callerIdx = toanalyze_methodDescList.indexOf(caller);
4838     int calleeIdx = toanalyze_methodDescList.indexOf(callee);
4839
4840     if (callerIdx < calleeIdx) {
4841       return true;
4842     }
4843
4844     return false;
4845
4846   }
4847
4848   public void constructFlowGraph() {
4849
4850     System.out.println("");
4851     toanalyze_methodDescList = computeMethodList();
4852
4853     // hack... it seems that there is a problem with topological sorting.
4854     // so String.toString(Object o) is appeared too higher in the call chain.
4855     MethodDescriptor mdToString = null;
4856     for (Iterator iterator = toanalyze_methodDescList.iterator(); iterator.hasNext();) {
4857       MethodDescriptor md = (MethodDescriptor) iterator.next();
4858       if (md.toString().equals("public static String String.valueOf(Object o)")) {
4859         mdToString = md;
4860         break;
4861       }
4862     }
4863     if (mdToString != null) {
4864       toanalyze_methodDescList.remove(mdToString);
4865       toanalyze_methodDescList.addLast(mdToString);
4866     }
4867
4868     LinkedList<MethodDescriptor> methodDescList =
4869         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4870
4871     System.out.println("@@@methodDescList=" + methodDescList);
4872     // System.exit(0);
4873
4874     while (!methodDescList.isEmpty()) {
4875       MethodDescriptor md = methodDescList.removeLast();
4876       if (state.SSJAVADEBUG) {
4877         System.out.println();
4878         System.out.println("SSJAVA: Constructing a flow graph: " + md);
4879
4880         // creates a mapping from a parameter descriptor to its index
4881         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
4882         int offset = 0;
4883         if (!md.isStatic()) {
4884           offset = 1;
4885           mapParamDescToIdx.put(md.getThis(), 0);
4886         }
4887
4888         for (int i = 0; i < md.numParameters(); i++) {
4889           Descriptor paramDesc = (Descriptor) md.getParameter(i);
4890           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
4891         }
4892
4893         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
4894         mapMethodDescriptorToFlowGraph.put(md, fg);
4895
4896         analyzeMethodBody(md.getClassDesc(), md);
4897
4898         // System.out.println("##constructSubGlobalFlowGraph");
4899         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
4900         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
4901         //
4902         // // TODO
4903         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
4904         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
4905         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4906         //
4907         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4908       }
4909     }
4910     // _debug_printGraph();
4911
4912   }
4913
4914   private void constructGlobalFlowGraph() {
4915     LinkedList<MethodDescriptor> methodDescList =
4916         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4917
4918     while (!methodDescList.isEmpty()) {
4919       MethodDescriptor md = methodDescList.removeLast();
4920       if (state.SSJAVADEBUG) {
4921         System.out.println();
4922         System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
4923
4924         constructSubGlobalFlowGraph(getFlowGraph(md));
4925
4926         // TODO
4927         System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
4928         addValueFlowsFromCalleeSubGlobalFlowGraph(md);
4929         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4930
4931         // System.out.println("-propagate Flows From Callees With No CompositeLocation");
4932         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4933
4934         // mark if a parameter has incoming flows
4935         checkParamNodesInSubGlobalFlowGraph(md);
4936
4937       }
4938     }
4939   }
4940
4941   private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) {
4942     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4943     FlowGraph flowGraph = getFlowGraph(md);
4944
4945     Set<FlowNode> paramFlowNodeSet = flowGraph.getParamFlowNodeSet();
4946     for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) {
4947       FlowNode paramFlowNode = (FlowNode) iterator.next();
4948       System.out.println("paramFlowNode=" + paramFlowNode);
4949       NTuple<Descriptor> paramDescTuple = paramFlowNode.getDescTuple();
4950       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
4951       GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple);
4952
4953       Set<GlobalFlowNode> incomingNodeSet =
4954           globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0));
4955
4956       if (incomingNodeSet.size() > 0) {
4957         paramGlobalNode.setParamNodeWithIncomingFlows(true);
4958       }
4959
4960     }
4961   }
4962
4963   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
4964     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
4965       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
4966     }
4967     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
4968   }
4969
4970   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
4971
4972     // the transformation for a call site propagates flows through parameters
4973     // if the method is virtual, it also grab all relations from any possible
4974     // callees
4975
4976     Set<MethodInvokeNode> setMethodInvokeNode =
4977         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4978
4979     if (setMethodInvokeNode != null) {
4980
4981       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4982         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4983         MethodDescriptor mdCallee = min.getMethod();
4984         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4985         if (mdCallee.isStatic()) {
4986           setPossibleCallees.add(mdCallee);
4987         } else {
4988           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4989           // removes method descriptors that are not invoked by the caller
4990           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4991           setPossibleCallees.addAll(calleeSet);
4992         }
4993
4994         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4995           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4996           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
4997         }
4998
4999       }
5000     }
5001
5002   }
5003
5004   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
5005     BlockNode bn = state.getMethodBody(md);
5006     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
5007     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
5008   }
5009
5010   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
5011       NodeTupleSet implicitFlowTupleSet) {
5012
5013     bn.getVarTable().setParent(nametable);
5014     for (int i = 0; i < bn.size(); i++) {
5015       BlockStatementNode bsn = bn.get(i);
5016       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
5017     }
5018
5019   }
5020
5021   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
5022       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
5023
5024     switch (bsn.kind()) {
5025     case Kind.BlockExpressionNode:
5026       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
5027       break;
5028
5029     case Kind.DeclarationNode:
5030       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
5031       break;
5032
5033     case Kind.IfStatementNode:
5034       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
5035       break;
5036
5037     case Kind.LoopNode:
5038       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
5039       break;
5040
5041     case Kind.ReturnNode:
5042       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
5043       break;
5044
5045     case Kind.SubBlockNode:
5046       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
5047       break;
5048
5049     case Kind.ContinueBreakNode:
5050       break;
5051
5052     case Kind.SwitchStatementNode:
5053       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
5054       break;
5055
5056     }
5057
5058   }
5059
5060   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
5061       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
5062
5063     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
5064
5065   }
5066
5067   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
5068       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
5069
5070     NodeTupleSet condTupleNode = new NodeTupleSet();
5071     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
5072         implicitFlowTupleSet, false);
5073
5074     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5075
5076     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5077     newImplicitTupleSet.addTupleSet(condTupleNode);
5078
5079     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5080       // need to create an intermediate node for the GLB of conditional
5081       // locations & implicit flows
5082       System.out.println("10");
5083
5084       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5085       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5086         NTuple<Descriptor> tuple = idxIter.next();
5087         addFlowGraphEdge(md, tuple, interTuple);
5088       }
5089       newImplicitTupleSet.clear();
5090       newImplicitTupleSet.addTuple(interTuple);
5091     }
5092
5093     BlockNode sbn = ssn.getSwitchBody();
5094     for (int i = 0; i < sbn.size(); i++) {
5095       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
5096     }
5097
5098   }
5099
5100   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
5101       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
5102     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
5103   }
5104
5105   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
5106       NodeTupleSet implicitFlowTupleSet) {
5107
5108     // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
5109     ExpressionNode returnExp = rn.getReturnExpression();
5110
5111     if (returnExp != null) {
5112       NodeTupleSet nodeSet = new NodeTupleSet();
5113       // if a return expression returns a literal value, nodeSet is empty
5114       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
5115       FlowGraph fg = getFlowGraph(md);
5116
5117       // if (implicitFlowTupleSet.size() == 1
5118       // &&
5119       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
5120       // {
5121       //
5122       // // since there is already an intermediate node for the GLB of implicit
5123       // flows
5124       // // we don't need to create another intermediate node.
5125       // // just re-use the intermediate node for implicit flows.
5126       //
5127       // FlowNode meetNode =
5128       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
5129       //
5130       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
5131       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
5132       // iterator.next();
5133       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
5134       // }
5135       //
5136       // }
5137
5138       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
5139
5140       // add tuples from return node
5141       currentFlowTupleSet.addTupleSet(nodeSet);
5142
5143       // add tuples corresponding to the current implicit flows
5144       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
5145
5146       // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
5147
5148       if (needToGenerateInterLoc(currentFlowTupleSet)) {
5149         System.out.println("9");
5150
5151         FlowNode meetNode = fg.createIntermediateNode();
5152         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
5153           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
5154           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
5155         }
5156         fg.addReturnFlowNode(meetNode.getDescTuple());
5157       } else {
5158         // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
5159         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
5160           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
5161           fg.addReturnFlowNode(currentFlowTuple);
5162         }
5163       }
5164
5165     }
5166
5167   }
5168
5169   private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
5170     NodeTupleSet tupleSet = new NodeTupleSet();
5171     for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
5172       NTuple<Descriptor> tuple = iter.next();
5173       if (!tuple.get(0).equals(LITERALDESC)) {
5174         tupleSet.addTuple(tuple);
5175       }
5176     }
5177     return tupleSet;
5178   }
5179
5180   private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
5181     int size = 0;
5182     for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
5183       NTuple<Descriptor> descTuple = iter.next();
5184       if (!descTuple.get(0).equals(LITERALDESC)) {
5185         size++;
5186       }
5187     }
5188     if (size > 1) {
5189       System.out.println("needToGenerateInterLoc=" + tupleSet + "  size=" + size);
5190       return true;
5191     } else {
5192       return false;
5193     }
5194   }
5195
5196   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
5197       NodeTupleSet implicitFlowTupleSet) {
5198
5199     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
5200
5201       NodeTupleSet condTupleNode = new NodeTupleSet();
5202       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
5203           implicitFlowTupleSet, false);
5204
5205       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5206
5207       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5208       newImplicitTupleSet.addTupleSet(condTupleNode);
5209
5210       newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet());
5211       newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
5212
5213       if (needToGenerateInterLoc(newImplicitTupleSet)) {
5214         // need to create an intermediate node for the GLB of conditional
5215         // locations & implicit flows
5216         System.out.println("6");
5217
5218         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5219         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
5220             .hasNext();) {
5221           NTuple<Descriptor> tuple = idxIter.next();
5222           addFlowGraphEdge(md, tuple, interTuple);
5223         }
5224         newImplicitTupleSet.clear();
5225         newImplicitTupleSet.addTuple(interTuple);
5226
5227       }
5228
5229       // ///////////
5230       // System.out.println("condTupleNode="+condTupleNode);
5231       // NTuple<Descriptor> interTuple =
5232       // getFlowGraph(md).createIntermediateNode().getDescTuple();
5233       //
5234       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
5235       // idxIter.hasNext();) {
5236       // NTuple<Descriptor> tuple = idxIter.next();
5237       // addFlowGraphEdge(md, tuple, interTuple);
5238       // }
5239
5240       // for (Iterator<NTuple<Descriptor>> idxIter =
5241       // implicitFlowTupleSet.iterator(); idxIter
5242       // .hasNext();) {
5243       // NTuple<Descriptor> tuple = idxIter.next();
5244       // addFlowGraphEdge(md, tuple, interTuple);
5245       // }
5246
5247       // NodeTupleSet newImplicitSet = new NodeTupleSet();
5248       // newImplicitSet.addTuple(interTuple);
5249       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
5250       // ///////////
5251
5252       // condTupleNode.addTupleSet(implicitFlowTupleSet);
5253
5254       // add edges from condNodeTupleSet to all nodes of conditional nodes
5255       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
5256
5257     } else {
5258       // check 'for loop' case
5259       BlockNode bn = ln.getInitializer();
5260       bn.getVarTable().setParent(nametable);
5261       for (int i = 0; i < bn.size(); i++) {
5262         BlockStatementNode bsn = bn.get(i);
5263         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
5264       }
5265
5266       NodeTupleSet condTupleNode = new NodeTupleSet();
5267       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
5268           implicitFlowTupleSet, false);
5269
5270       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5271       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5272       newImplicitTupleSet.addTupleSet(condTupleNode);
5273
5274       if (needToGenerateInterLoc(newImplicitTupleSet)) {
5275         // need to create an intermediate node for the GLB of conditional
5276         // locations & implicit flows
5277         System.out.println("7");
5278
5279         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5280         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
5281             .hasNext();) {
5282           NTuple<Descriptor> tuple = idxIter.next();
5283           addFlowGraphEdge(md, tuple, interTuple);
5284         }
5285         newImplicitTupleSet.clear();
5286         newImplicitTupleSet.addTuple(interTuple);
5287
5288       }
5289
5290       // ///////////
5291       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5292       //
5293       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
5294       // NTuple<Descriptor> tuple = idxIter.next();
5295       // addFlowGraphEdge(md, tuple, interTuple);
5296       // }
5297       //
5298       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
5299       // .hasNext();) {
5300       // NTuple<Descriptor> tuple = idxIter.next();
5301       // addFlowGraphEdge(md, tuple, interTuple);
5302       // }
5303       //
5304       // NodeTupleSet newImplicitSet = new NodeTupleSet();
5305       // newImplicitSet.addTuple(interTuple);
5306       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
5307       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
5308       // ///////////
5309
5310       // condTupleNode.addTupleSet(implicitFlowTupleSet);
5311       //
5312       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
5313       // condTupleNode);
5314       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
5315       // condTupleNode);
5316
5317     }
5318
5319   }
5320
5321   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
5322       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
5323
5324     // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
5325
5326     NodeTupleSet condTupleNode = new NodeTupleSet();
5327     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
5328         implicitFlowTupleSet, false);
5329
5330     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5331
5332     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5333     newImplicitTupleSet.addTupleSet(condTupleNode);
5334
5335     // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet());
5336     // System.out.println("-condTupleNode=" + condTupleNode);
5337     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5338     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5339
5340     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5341       System.out.println("5");
5342
5343       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5344       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5345       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5346         NTuple<Descriptor> tuple = idxIter.next();
5347         addFlowGraphEdge(md, tuple, interTuple);
5348       }
5349       newImplicitTupleSet.clear();
5350       newImplicitTupleSet.addTuple(interTuple);
5351     }
5352
5353     // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5354     // for (Iterator<NTuple<Location>> iterator = condTupleNode.globalIterator();
5355     // iterator.hasNext();) {
5356     // NTuple<Location> calleeReturnLocTuple = iterator.next();
5357     // for (Iterator<NTuple<Descriptor>> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) {
5358     // NTuple<Descriptor> callerImplicitTuple = iter2.next();
5359     // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5360     // translateToLocTuple(md, callerImplicitTuple));
5361     // }
5362     // }
5363     newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
5364
5365     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
5366
5367     if (isn.getFalseBlock() != null) {
5368       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
5369     }
5370
5371   }
5372
5373   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
5374       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
5375
5376     VarDescriptor vd = dn.getVarDescriptor();
5377     mapDescToDefinitionLine.put(vd, dn.getNumLine());
5378     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
5379     tupleLHS.add(vd);
5380     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
5381     fn.setDeclarationNode();
5382
5383     if (dn.getExpression() != null) {
5384       System.out.println("-analyzeFlowDeclarationNode=" + dn.printNode(0));
5385
5386       NodeTupleSet nodeSetRHS = new NodeTupleSet();
5387       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
5388           implicitFlowTupleSet, false);
5389
5390       // creates edges from RHS to LHS
5391       NTuple<Descriptor> interTuple = null;
5392       if (needToGenerateInterLoc(nodeSetRHS)) {
5393         System.out.println("3");
5394         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5395       }
5396
5397       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5398         NTuple<Descriptor> fromTuple = iter.next();
5399         System.out.println("fromTuple=" + fromTuple + "  interTuple=" + interTuple + " tupleLSH="
5400             + tupleLHS);
5401         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
5402       }
5403
5404       // creates edges from implicitFlowTupleSet to LHS
5405       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5406         NTuple<Descriptor> implicitTuple = iter.next();
5407         addFlowGraphEdge(md, implicitTuple, tupleLHS);
5408       }
5409
5410       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5411       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
5412         NTuple<Location> calleeReturnLocTuple = iterator.next();
5413
5414         globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS));
5415       }
5416
5417       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5418           .hasNext();) {
5419         NTuple<Location> implicitGlobalTuple = iterator.next();
5420
5421         globalFlowGraph.addValueFlowEdge(implicitGlobalTuple, translateToLocTuple(md, tupleLHS));
5422       }
5423
5424       System.out.println("-nodeSetRHS=" + nodeSetRHS);
5425       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5426
5427     }
5428
5429   }
5430
5431   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
5432       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
5433     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
5434         false);
5435   }
5436
5437   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5438       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
5439     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
5440   }
5441
5442   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5443       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5444       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5445
5446     // System.out.println("en=" + en.printNode(0) + "   class=" + en.getClass());
5447
5448     // note that expression node can create more than one flow node
5449     // nodeSet contains of flow nodes
5450     // base is always assigned to null except the case of a name node!
5451     NTuple<Descriptor> flowTuple;
5452     switch (en.kind()) {
5453     case Kind.AssignmentNode:
5454       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
5455           implicitFlowTupleSet);
5456       break;
5457
5458     case Kind.FieldAccessNode:
5459       flowTuple =
5460           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
5461               implicitFlowTupleSet, isLHS);
5462       if (flowTuple != null) {
5463         nodeSet.addTuple(flowTuple);
5464       }
5465       return flowTuple;
5466
5467     case Kind.NameNode:
5468       NodeTupleSet nameNodeSet = new NodeTupleSet();
5469       flowTuple =
5470           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
5471       if (flowTuple != null) {
5472         nodeSet.addTuple(flowTuple);
5473       }
5474       return flowTuple;
5475
5476     case Kind.OpNode:
5477       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
5478       break;
5479
5480     case Kind.CreateObjectNode:
5481       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
5482       break;
5483
5484     case Kind.ArrayAccessNode:
5485       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
5486       break;
5487
5488     case Kind.LiteralNode:
5489       analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
5490       break;
5491
5492     case Kind.MethodInvokeNode:
5493       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
5494           implicitFlowTupleSet);
5495       break;
5496
5497     case Kind.TertiaryNode:
5498       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
5499       break;
5500
5501     case Kind.CastNode:
5502       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
5503       break;
5504     // case Kind.InstanceOfNode:
5505     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
5506     // return null;
5507
5508     // case Kind.ArrayInitializerNode:
5509     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
5510     // td);
5511     // return null;
5512
5513     // case Kind.ClassTypeNode:
5514     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
5515     // return null;
5516
5517     // case Kind.OffsetNode:
5518     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
5519     // return null;
5520
5521     }
5522
5523     return null;
5524
5525   }
5526
5527   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
5528       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5529
5530     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
5531         implicitFlowTupleSet, false);
5532
5533   }
5534
5535   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
5536       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5537
5538     // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0));
5539
5540     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
5541     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
5542         implicitFlowTupleSet, false);
5543
5544     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5545     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5546     newImplicitTupleSet.addTupleSet(tertiaryTupleNode);
5547
5548     // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet());
5549     // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode);
5550     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5551     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5552
5553     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5554       System.out.println("15");
5555       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5556       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5557       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5558         NTuple<Descriptor> tuple = idxIter.next();
5559         addFlowGraphEdge(md, tuple, interTuple);
5560       }
5561       newImplicitTupleSet.clear();
5562       newImplicitTupleSet.addTuple(interTuple);
5563     }
5564
5565     newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5566
5567     System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet);
5568     // add edges from tertiaryTupleNode to all nodes of conditional nodes
5569     // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
5570     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
5571         newImplicitTupleSet, false);
5572
5573     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
5574         newImplicitTupleSet, false);
5575
5576     nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5577     nodeSet.addTupleSet(tertiaryTupleNode);
5578
5579     System.out.println("#tertiary node set=" + nodeSet);
5580   }
5581
5582   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
5583       MethodInvokeNode min) {
5584     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
5585     if (set == null) {
5586       set = new HashSet<MethodInvokeNode>();
5587       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
5588     }
5589     set.add(min);
5590   }
5591
5592   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
5593
5594     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5595       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5596     }
5597     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
5598   }
5599
5600   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
5601
5602     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5603       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5604     }
5605
5606     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
5607   }
5608
5609   private Set<NTuple<Location>> getPCLocTupleSet(MethodInvokeNode min) {
5610     if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) {
5611       mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet<NTuple<Location>>());
5612     }
5613     return mapMethodInvokeNodeToPCLocTupleSet.get(min);
5614   }
5615
5616   private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable,
5617       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5618
5619     System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
5620
5621     if (!toanalyze_methodDescList.contains(min.getMethod())) {
5622       return;
5623     }
5624
5625     addMapMethodDescToMethodInvokeNodeSet(min);
5626
5627     Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
5628     for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) {
5629       NTuple<Descriptor> pcDescTuple = (NTuple<Descriptor>) iterator.next();
5630       if (!pcDescTuple.get(0).equals(LITERALDESC)) {
5631         // here we don't need to add the literal value as a PC location
5632         pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple));
5633       }
5634     }
5635
5636     mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
5637
5638     if (nodeSet == null) {
5639       nodeSet = new NodeTupleSet();
5640     }
5641
5642     MethodDescriptor mdCallee = min.getMethod();
5643
5644     NameDescriptor baseName = min.getBaseName();
5645     boolean isSystemout = false;
5646     if (baseName != null) {
5647       isSystemout = baseName.getSymbol().equals("System.out");
5648     }
5649
5650     if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee)
5651         && !isSystemout) {
5652
5653       addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min);
5654
5655       FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
5656       System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph);
5657       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
5658
5659       System.out.println("---calleeReturnSet=" + calleeReturnSet);
5660
5661       NodeTupleSet tupleSet = new NodeTupleSet();
5662
5663       if (min.getExpression() != null) {
5664
5665         NodeTupleSet baseNodeSet = new NodeTupleSet();
5666         analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null,
5667             implicitFlowTupleSet, false);
5668         System.out.println("baseNodeSet=" + baseNodeSet);
5669
5670         assert (baseNodeSet.size() == 1);
5671         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
5672         if (baseTuple.get(0) instanceof InterDescriptor) {
5673           if (baseTuple.size() > 1) {
5674             throw new Error();
5675           }
5676           FlowNode interNode = getFlowGraph(mdCaller).getFlowNode(baseTuple);
5677           baseTuple = translateBaseTuple(interNode, baseTuple);
5678         }
5679         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
5680
5681         if (!min.getMethod().isStatic()) {
5682           addArgIdxMap(min, 0, baseTuple);
5683
5684           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5685             FlowNode returnNode = (FlowNode) iterator.next();
5686             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
5687             if (returnDescTuple.startsWith(mdCallee.getThis())) {
5688               // the location type of the return value is started with 'this'
5689               // reference
5690               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
5691
5692               if (inFlowTuple.get(0) instanceof InterDescriptor) {
5693                 // min.getExpression()
5694               } else {
5695
5696               }
5697
5698               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
5699               // nodeSet.addTuple(inFlowTuple);
5700               System.out.println("1CREATE A NEW TUPLE=" + inFlowTuple + "  from="
5701                   + mdCallee.getThis());
5702               // tupleSet.addTuple(inFlowTuple);
5703               tupleSet.addTuple(baseTuple);
5704             } else {
5705               // TODO
5706               System.out.println("returnNode=" + returnNode);
5707               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
5708               // System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
5709               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
5710                 FlowNode inFlowNode = (FlowNode) iterator2.next();
5711                 if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) {
5712                   // nodeSet.addTupleSet(baseNodeSet);
5713                   System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + "  from="
5714                       + mdCallee.getThis());
5715                   tupleSet.addTupleSet(baseNodeSet);
5716                 }
5717               }
5718             }
5719           }
5720         }
5721
5722       }
5723       // analyze parameter flows
5724
5725       if (min.numArgs() > 0) {
5726
5727         int offset;
5728         if (min.getMethod().isStatic()) {
5729           offset = 0;
5730         } else {
5731           offset = 1;
5732         }
5733
5734         for (int i = 0; i < min.numArgs(); i++) {
5735           ExpressionNode en = min.getArg(i);
5736           int idx = i + offset;
5737           NodeTupleSet argTupleSet = new NodeTupleSet();
5738           analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false);
5739           // if argument is liternal node, argTuple is set to NULL
5740           System.out.println("---arg idx=" + idx + "   argTupleSet=" + argTupleSet);
5741           NTuple<Descriptor> argTuple = generateArgTuple(mdCaller, argTupleSet);
5742
5743           // if an argument is literal value,
5744           // we need to create an itermediate node so that we could assign a composite location to
5745           // that node if needed
5746           if (argTuple.size() > 0
5747               && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) {
5748             /*
5749              * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8");
5750              *
5751              * NTuple<Descriptor> interTuple =
5752              * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor)
5753              * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller,
5754              * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple);
5755              * System.out.println("new min mapping i=" + idx + "  ->" + argTuple);
5756              */
5757             argTuple = new NTuple<Descriptor>();
5758           }
5759
5760           addArgIdxMap(min, idx, argTuple);
5761
5762           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
5763
5764           // check whether a param node in the callee graph has incoming flows
5765           // if it has incoming flows, the corresponding arg should be lower than the current PC
5766           // Descriptor prefix = paramNode.getDescTuple().get(0);
5767           // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
5768           // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
5769           // .hasNext();) {
5770           // NTuple<Descriptor> pcTuple = iterator.next();
5771           // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
5772           // addFlowGraphEdge(md, pcTuple, argTuple);
5773           // }
5774           // }
5775
5776           System.out.println("paramNode=" + paramNode + "  calleeReturnSet=" + calleeReturnSet);
5777           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
5778               || mdCallee.getModifiers().isNative()) {
5779             addParamNodeFlowingToReturnValue(mdCallee, paramNode);
5780             // nodeSet.addTupleSet(argTupleSet);
5781             System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + "  from=" + paramNode);
5782             tupleSet.addTupleSet(argTupleSet);
5783           }
5784         }
5785
5786       }
5787
5788       if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) {
5789         FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min);
5790
5791         if (needToGenerateInterLoc(tupleSet)) {
5792           System.out.println("20");
5793           FlowGraph fg = getFlowGraph(mdCaller);
5794           FlowNode interNode = fg.createIntermediateNode();
5795           interNode.setFormHolder(true);
5796
5797           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5798
5799           for (Iterator iterator = tupleSet.iterator(); iterator.hasNext();) {
5800             NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5801
5802             Set<NTuple<Descriptor>> addSet = new HashSet<NTuple<Descriptor>>();
5803             FlowNode node = fg.getFlowNode(tuple);
5804             if (node instanceof FlowReturnNode) {
5805               addSet.addAll(fg.getReturnTupleSet(((FlowReturnNode) node).getReturnTupleSet()));
5806             } else {
5807               addSet.add(tuple);
5808             }
5809             for (Iterator iterator2 = addSet.iterator(); iterator2.hasNext();) {
5810               NTuple<Descriptor> higher = (NTuple<Descriptor>) iterator2.next();
5811               addFlowGraphEdge(mdCaller, higher, interTuple);
5812             }
5813           }
5814
5815           returnHolderNode.addTuple(interTuple);
5816
5817           nodeSet.addTuple(interTuple);
5818           System.out.println("ADD TUPLESET=" + interTuple + " to returnnode=" + returnHolderNode);
5819
5820         } else {
5821           returnHolderNode.addTupleSet(tupleSet);
5822           System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + returnHolderNode);
5823         }
5824         // setNode.addTupleSet(tupleSet);
5825         // NodeTupleSet setFromReturnNode=new NodeTupleSet();
5826         // setFromReturnNode.addTuple(tuple);
5827
5828         NodeTupleSet holderTupleSet =
5829             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), returnHolderNode);
5830
5831         System.out.println("HOLDER TUPLe SET=" + holderTupleSet);
5832         nodeSet.addTupleSet(holderTupleSet);
5833
5834         nodeSet.addTuple(returnHolderNode.getDescTuple());
5835       }
5836
5837       // propagateFlowsFromCallee(min, md, min.getMethod());
5838
5839       // when generating the global flow graph,
5840       // we need to add ordering relations from the set of callee return loc tuple to LHS of the
5841       // caller assignment
5842       for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5843         FlowNode calleeReturnNode = (FlowNode) iterator.next();
5844         NTuple<Location> calleeReturnLocTuple =
5845             translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple());
5846         System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple);
5847         NTuple<Location> transaltedToCaller =
5848             translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple);
5849         // System.out.println("translateToCallerLocTuple="
5850         // + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple));
5851         if (transaltedToCaller.size() > 0) {
5852           nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller,
5853               calleeReturnLocTuple));
5854         }
5855       }
5856
5857       System.out.println("min nodeSet=" + nodeSet);
5858
5859     }
5860
5861   }
5862
5863   private NodeTupleSet getNodeTupleSetFromReturnNode(FlowGraph fg, FlowReturnNode node) {
5864     NodeTupleSet nts = new NodeTupleSet();
5865
5866     Set<NTuple<Descriptor>> returnSet = node.getReturnTupleSet();
5867
5868     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5869       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5870       FlowNode flowNode = fg.getFlowNode(tuple);
5871       if (flowNode instanceof FlowReturnNode) {
5872         returnSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5873       } else {
5874         returnSet.add(tuple);
5875       }
5876     }
5877
5878     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5879       NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator.next();
5880       nts.addTuple(nTuple);
5881     }
5882
5883     return nts;
5884
5885   }
5886
5887   private Set<NTuple<Descriptor>> recurGetNode(FlowGraph fg, FlowReturnNode rnode) {
5888
5889     Set<NTuple<Descriptor>> tupleSet = new HashSet<NTuple<Descriptor>>();
5890
5891     Set<NTuple<Descriptor>> returnSet = rnode.getReturnTupleSet();
5892     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5893       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5894       FlowNode flowNode = fg.getFlowNode(tuple);
5895       if (flowNode instanceof FlowReturnNode) {
5896         tupleSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5897       }
5898       tupleSet.add(tuple);
5899     }
5900
5901     return tupleSet;
5902   }
5903
5904   private NTuple<Descriptor> generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) {
5905
5906     int size = 0;
5907
5908     // if argTupleSet is empty, it comes from the top location
5909     if (argTupleSet.size() == 0) {
5910       NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
5911       descTuple.add(LITERALDESC);
5912       return descTuple;
5913     }
5914
5915     Set<NTuple<Descriptor>> argTupleSetNonLiteral = new HashSet<NTuple<Descriptor>>();
5916
5917     for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
5918       NTuple<Descriptor> descTuple = iter.next();
5919       if (!descTuple.get(0).equals(LITERALDESC)) {
5920         argTupleSetNonLiteral.add(descTuple);
5921       }
5922     }
5923
5924     if (argTupleSetNonLiteral.size() > 1) {
5925       System.out.println("11");
5926
5927       NTuple<Descriptor> interTuple =
5928           getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
5929       for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
5930         NTuple<Descriptor> tuple = idxIter.next();
5931         addFlowGraphEdge(mdCaller, tuple, interTuple);
5932       }
5933       return interTuple;
5934     } else if (argTupleSetNonLiteral.size() == 1) {
5935       return argTupleSetNonLiteral.iterator().next();
5936     } else {
5937       return argTupleSet.iterator().next();
5938     }
5939
5940   }
5941
5942   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
5943     // return true if inNode has in-flows to nodeSet
5944
5945     if (nodeSet.contains(inNode)) {
5946       // in this case, the method directly returns a parameter variable.
5947       return true;
5948     }
5949     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
5950     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
5951     // System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
5952
5953     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
5954       FlowNode fn = (FlowNode) iterator.next();
5955       if (nodeSet.contains(fn)) {
5956         return true;
5957       }
5958     }
5959     return false;
5960   }
5961
5962   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
5963     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
5964   }
5965
5966   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
5967                                                                                         * NodeTupleSet
5968                                                                                         * tupleSet
5969                                                                                         */) {
5970     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
5971     if (mapIdxToTuple == null) {
5972       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
5973       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
5974     }
5975     mapIdxToTuple.put(new Integer(idx), argTuple);
5976   }
5977
5978   private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
5979       NodeTupleSet nodeSet) {
5980     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
5981     tuple.add(LITERALDESC);
5982     nodeSet.addTuple(tuple);
5983   }
5984
5985   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
5986       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
5987
5988     System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0));
5989     String currentArrayAccessNodeExpStr = aan.printNode(0);
5990     arrayAccessNodeStack.push(aan.printNode(0));
5991
5992     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
5993     NTuple<Descriptor> base =
5994         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
5995     System.out.println("-base=" + base);
5996
5997     nodeSet.setMethodInvokeBaseDescTuple(base);
5998     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5999     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
6000
6001     arrayAccessNodeStack.pop();
6002
6003     if (isLHS) {
6004       // need to create an edge from idx to array
6005       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
6006         NTuple<Descriptor> idxTuple = idxIter.next();
6007         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
6008           NTuple<Descriptor> arrTuple = arrIter.next();
6009           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
6010         }
6011       }
6012
6013       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6014       for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
6015           .hasNext();) {
6016         NTuple<Location> calleeReturnLocTuple = iterator.next();
6017         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
6018           NTuple<Descriptor> arrTuple = arrIter.next();
6019
6020           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple));
6021         }
6022       }
6023
6024       nodeSet.addTupleSet(expNodeTupleSet);
6025     } else {
6026
6027       NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
6028
6029       nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
6030       nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
6031
6032       if (arrayAccessNodeStack.isEmpty()
6033           || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
6034
6035         if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
6036           System.out.println("1");
6037           FlowNode interNode = getFlowGraph(md).createIntermediateNode();
6038           NTuple<Descriptor> interTuple = interNode.getDescTuple();
6039
6040           for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
6041             NTuple<Descriptor> higherTuple = iter.next();
6042             addFlowGraphEdge(md, higherTuple, interTuple);
6043           }
6044           nodeSetArrayAccessExp.clear();
6045           nodeSetArrayAccessExp.addTuple(interTuple);
6046           FlowGraph fg = getFlowGraph(md);
6047
6048           System.out.println("base=" + base);
6049           if (base != null) {
6050             fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
6051                 getClassTypeDescriptor(base.get(base.size() - 1)));
6052             interNode.setBaseTuple(base);
6053           }
6054         }
6055       }
6056
6057       nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
6058       nodeSet.addTupleSet(nodeSetArrayAccessExp);
6059
6060     }
6061
6062   }
6063
6064   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
6065       CreateObjectNode en) {
6066     // TODO Auto-generated method stub
6067
6068   }
6069
6070   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
6071       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
6072
6073     NodeTupleSet leftOpSet = new NodeTupleSet();
6074     NodeTupleSet rightOpSet = new NodeTupleSet();
6075
6076     System.out.println("analyzeFlowOpNode=" + on.printNode(0));
6077
6078     // left operand
6079     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
6080         false);
6081     System.out.println("--leftOpSet=" + leftOpSet);
6082
6083     if (on.getRight() != null) {
6084       // right operand
6085       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
6086           implicitFlowTupleSet, false);
6087     }
6088     System.out.println("--rightOpSet=" + rightOpSet);
6089
6090     Operation op = on.getOp();
6091
6092     switch (op.getOp()) {
6093
6094     case Operation.UNARYPLUS:
6095     case Operation.UNARYMINUS:
6096     case Operation.LOGIC_NOT:
6097       // single operand
6098       nodeSet.addTupleSet(leftOpSet);
6099       break;
6100
6101     case Operation.LOGIC_OR:
6102     case Operation.LOGIC_AND:
6103     case Operation.COMP:
6104     case Operation.BIT_OR:
6105     case Operation.BIT_XOR:
6106     case Operation.BIT_AND:
6107     case Operation.ISAVAILABLE:
6108     case Operation.EQUAL:
6109     case Operation.NOTEQUAL:
6110     case Operation.LT:
6111     case Operation.GT:
6112     case Operation.LTE:
6113     case Operation.GTE:
6114     case Operation.ADD:
6115     case Operation.SUB:
6116     case Operation.MULT:
6117     case Operation.DIV:
6118     case Operation.MOD:
6119     case Operation.LEFTSHIFT:
6120     case Operation.RIGHTSHIFT:
6121     case Operation.URIGHTSHIFT:
6122
6123       // there are two operands
6124       nodeSet.addTupleSet(leftOpSet);
6125       nodeSet.addTupleSet(rightOpSet);
6126
6127       nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet());
6128       nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet());
6129
6130       break;
6131
6132     default:
6133       throw new Error(op.toString());
6134     }
6135
6136   }
6137
6138   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
6139       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
6140
6141     if (base == null) {
6142       base = new NTuple<Descriptor>();
6143     }
6144
6145     NameDescriptor nd = nn.getName();
6146
6147     if (nd.getBase() != null) {
6148       base =
6149           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
6150               implicitFlowTupleSet, false);
6151       if (base == null) {
6152         // base node has the top location
6153         return base;
6154       }
6155     } else {
6156       String varname = nd.toString();
6157       if (varname.equals("this")) {
6158         // 'this' itself!
6159         base.add(md.getThis());
6160         return base;
6161       }
6162
6163       Descriptor d = (Descriptor) nametable.get(varname);
6164
6165       if (d instanceof VarDescriptor) {
6166         VarDescriptor vd = (VarDescriptor) d;
6167         base.add(vd);
6168       } else if (d instanceof FieldDescriptor) {
6169         // the type of field descriptor has a location!
6170         FieldDescriptor fd = (FieldDescriptor) d;
6171         if (fd.isStatic()) {
6172           if (fd.isFinal()) {
6173             // if it is 'static final', no need to have flow node for the TOP
6174             // location
6175             return null;
6176           } else {
6177             // if 'static', assign the default GLOBAL LOCATION to the first
6178             // element of the tuple
6179             base.add(GLOBALDESC);
6180           }
6181         } else {
6182           // the location of field access starts from this, followed by field
6183           // location
6184           base.add(md.getThis());
6185         }
6186
6187         base.add(fd);
6188       } else if (d == null) {
6189         // access static field
6190         base.add(GLOBALDESC);
6191         base.add(nn.getField());
6192         return base;
6193
6194         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
6195         //
6196         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
6197         // String globalLocId = localLattice.getGlobalLoc();
6198         // if (globalLocId == null) {
6199         // throw new
6200         // Error("Method lattice does not define global variable location at "
6201         // + generateErrorMessage(md.getClassDesc(), nn));
6202         // }
6203         // loc.addLocation(new Location(md, globalLocId));
6204         //
6205         // Location fieldLoc = (Location) fd.getType().getExtension();
6206         // loc.addLocation(fieldLoc);
6207         //
6208         // return loc;
6209
6210       }
6211     }
6212     getFlowGraph(md).createNewFlowNode(base);
6213
6214     return base;
6215
6216   }
6217
6218   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
6219       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
6220       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
6221     // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0));
6222
6223     String currentArrayAccessNodeExpStr = null;
6224     ExpressionNode left = fan.getExpression();
6225     TypeDescriptor ltd = left.getType();
6226     FieldDescriptor fd = fan.getField();
6227     ArrayAccessNode aan = null;
6228
6229     String varName = null;
6230     if (left.kind() == Kind.NameNode) {
6231       NameDescriptor nd = ((NameNode) left).getName();
6232       varName = nd.toString();
6233     }
6234
6235     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
6236       // using a class name directly or access using this
6237       if (fd.isStatic() && fd.isFinal()) {
6238         return null;
6239       }
6240     }
6241
6242     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
6243
6244     boolean isArrayCase = false;
6245     if (left instanceof ArrayAccessNode) {
6246
6247       isArrayCase = true;
6248       aan = (ArrayAccessNode) left;
6249
6250       currentArrayAccessNodeExpStr = aan.printNode(0);
6251       arrayAccessNodeStack.push(currentArrayAccessNodeExpStr);
6252
6253       left = aan.getExpression();
6254       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
6255           implicitFlowTupleSet, isLHS);
6256
6257     }
6258     base =
6259         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
6260
6261     if (base == null) {
6262       // in this case, field is TOP location
6263       return null;
6264     } else {
6265
6266       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
6267
6268       if (!left.getType().isPrimitive()) {
6269         if (!fd.getSymbol().equals("length")) {
6270           // array.length access, just have the location of the array
6271           flowFieldTuple.add(fd);
6272           nodeSet.removeTuple(base);
6273         }
6274       }
6275       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
6276
6277       if (isLHS) {
6278         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
6279           NTuple<Descriptor> idxTuple = idxIter.next();
6280           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
6281         }
6282
6283         GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6284         for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
6285             .hasNext();) {
6286           NTuple<Location> calleeReturnLocTuple = iterator.next();
6287
6288           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6289               translateToLocTuple(md, flowFieldTuple));
6290         }
6291
6292       } else {
6293         nodeSet.addTupleSet(idxNodeTupleSet);
6294
6295         // if it is the array case and not the LHS case
6296         if (isArrayCase) {
6297           arrayAccessNodeStack.pop();
6298
6299           if (arrayAccessNodeStack.isEmpty()
6300               || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
6301             NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
6302
6303             nodeSetArrayAccessExp.addTuple(flowFieldTuple);
6304             nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
6305             nodeSetArrayAccessExp.addTupleSet(nodeSet);
6306
6307             if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
6308               System.out.println("4");
6309               System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp);
6310               // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()="
6311               // + idxNodeTupleSet.getGlobalLocTupleSet());
6312
6313               NTuple<Descriptor> interTuple =
6314                   getFlowGraph(md).createIntermediateNode().getDescTuple();
6315
6316               for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter
6317                   .hasNext();) {
6318                 NTuple<Descriptor> higherTuple = iter.next();
6319                 addFlowGraphEdge(md, higherTuple, interTuple);
6320               }
6321
6322               FlowGraph fg = getFlowGraph(md);
6323               fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
6324                   getClassTypeDescriptor(base.get(base.size() - 1)));
6325
6326               nodeSet.clear();
6327               flowFieldTuple = interTuple;
6328             }
6329             nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
6330           }
6331
6332         }
6333
6334       }
6335       return flowFieldTuple;
6336     }
6337
6338   }
6339
6340   private void debug_printTreeNode(TreeNode tn) {
6341
6342     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
6343
6344   }
6345
6346   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
6347       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
6348       NodeTupleSet implicitFlowTupleSet) {
6349
6350     NodeTupleSet nodeSetRHS = new NodeTupleSet();
6351     NodeTupleSet nodeSetLHS = new NodeTupleSet();
6352
6353     boolean postinc = true;
6354     if (an.getOperation().getBaseOp() == null
6355         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
6356             .getBaseOp().getOp() != Operation.POSTDEC)) {
6357       postinc = false;
6358     }
6359     // if LHS is array access node, need to capture value flows between an array
6360     // and its index value
6361     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
6362         true);
6363
6364     if (!postinc) {
6365       // analyze value flows of rhs expression
6366       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
6367           false);
6368
6369       System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
6370       System.out.println("-nodeSetLHS=" + nodeSetLHS);
6371       System.out.println("-nodeSetRHS=" + nodeSetRHS);
6372       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
6373       // System.out.println("-");
6374
6375       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
6376         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
6377
6378         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
6379           NTuple<Descriptor> fromTuple = iter.next();
6380           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6381             NTuple<Descriptor> toTuple = iter2.next();
6382             addFlowGraphEdge(md, fromTuple, toTuple);
6383           }
6384         }
6385       }
6386
6387       // creates edges from RHS to LHS
6388       NTuple<Descriptor> interTuple = null;
6389       if (needToGenerateInterLoc(nodeSetRHS)) {
6390         System.out.println("2");
6391         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
6392       }
6393
6394       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
6395         NTuple<Descriptor> fromTuple = iter.next();
6396         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6397           NTuple<Descriptor> toTuple = iter2.next();
6398           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
6399         }
6400       }
6401
6402       // creates edges from implicitFlowTupleSet to LHS
6403       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6404         NTuple<Descriptor> fromTuple = iter.next();
6405         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6406           NTuple<Descriptor> toTuple = iter2.next();
6407           addFlowGraphEdge(md, fromTuple, toTuple);
6408         }
6409       }
6410
6411       // create global flow edges if the callee gives return value flows to the caller
6412       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6413       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
6414         NTuple<Location> calleeReturnLocTuple = iterator.next();
6415         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6416           NTuple<Descriptor> callerLHSTuple = iter2.next();
6417           System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> "
6418               + translateToLocTuple(md, callerLHSTuple));
6419
6420           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6421               translateToLocTuple(md, callerLHSTuple));
6422         }
6423       }
6424
6425       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6426           .hasNext();) {
6427         NTuple<Location> calleeReturnLocTuple = iterator.next();
6428         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6429           NTuple<Descriptor> callerLHSTuple = iter2.next();
6430
6431           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6432               translateToLocTuple(md, callerLHSTuple));
6433           System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> "
6434               + translateToLocTuple(md, callerLHSTuple));
6435         }
6436       }
6437
6438     } else {
6439       // postinc case
6440
6441       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6442         NTuple<Descriptor> tuple = iter2.next();
6443         addFlowGraphEdge(md, tuple, tuple);
6444       }
6445
6446       // creates edges from implicitFlowTupleSet to LHS
6447       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6448         NTuple<Descriptor> fromTuple = iter.next();
6449         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6450           NTuple<Descriptor> toTuple = iter2.next();
6451           addFlowGraphEdge(md, fromTuple, toTuple);
6452         }
6453       }
6454
6455       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6456       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6457           .hasNext();) {
6458         NTuple<Location> calleeReturnLocTuple = iterator.next();
6459         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6460           NTuple<Descriptor> callerLHSTuple = iter2.next();
6461           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6462               translateToLocTuple(md, callerLHSTuple));
6463           System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> "
6464               + translateToLocTuple(md, callerLHSTuple));
6465         }
6466       }
6467
6468     }
6469
6470     if (nodeSet != null) {
6471       nodeSet.addTupleSet(nodeSetLHS);
6472       nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet());
6473     }
6474   }
6475
6476   public FlowGraph getFlowGraph(MethodDescriptor md) {
6477     return mapMethodDescriptorToFlowGraph.get(md);
6478   }
6479
6480   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6481       NTuple<Descriptor> to) {
6482     FlowGraph graph = getFlowGraph(md);
6483     graph.addValueFlowEdge(from, to);
6484     return true;
6485   }
6486
6487   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6488       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
6489
6490     FlowGraph graph = getFlowGraph(md);
6491
6492     if (inter != null) {
6493       graph.addValueFlowEdge(from, inter);
6494       graph.addValueFlowEdge(inter, to);
6495     } else {
6496       graph.addValueFlowEdge(from, to);
6497     }
6498
6499   }
6500
6501   public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
6502       SSJavaLattice<String> locOrder, String nameSuffix) {
6503     System.out.println("@cd=" + cd);
6504     System.out.println("@sharedLoc=" + locOrder.getSharedLocSet());
6505     writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
6506   }
6507
6508   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
6509       HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
6510
6511     String fileName = "lattice_";
6512     if (md != null) {
6513       fileName +=
6514           cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
6515     } else {
6516       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
6517     }
6518
6519     fileName += nameSuffix;
6520
6521     System.out.println("***lattice=" + fileName + "    setsize=" + locOrder.getKeySet().size());
6522
6523     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
6524
6525     Set<String> addedLocSet = new HashSet<String>();
6526
6527     if (pairSet.size() > 0) {
6528       try {
6529         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
6530
6531         bw.write("digraph " + fileName + " {\n");
6532
6533         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
6534           // pair is in the form of <higher, lower>
6535           Pair<String, String> pair = (Pair<String, String>) iterator.next();
6536
6537           String highLocId = pair.getFirst();
6538           String lowLocId = pair.getSecond();
6539           if (!addedLocSet.contains(highLocId)) {
6540             addedLocSet.add(highLocId);
6541             drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
6542           }
6543
6544           if (!addedLocSet.contains(lowLocId)) {
6545             addedLocSet.add(lowLocId);
6546             drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
6547           }
6548
6549           bw.write(highLocId + " -> " + lowLocId + ";\n");
6550         }
6551         bw.write("}\n");
6552         bw.close();
6553
6554       } catch (IOException e) {
6555         e.printStackTrace();
6556       }
6557
6558     }
6559
6560   }
6561
6562   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
6563     String str = "";
6564     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
6565       HNode merged = (HNode) iterator.next();
6566       if (merged.isMergeNode()) {
6567         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
6568       } else {
6569         str += " " + merged.getName();
6570       }
6571     }
6572     return str;
6573   }
6574
6575   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
6576       String locName) throws IOException {
6577
6578     String prettyStr;
6579     if (lattice.isSharedLoc(locName)) {
6580       prettyStr = locName + "*";
6581     } else {
6582       prettyStr = locName;
6583     }
6584     // HNode node = graph.getHNode(locName);
6585     // if (node != null && node.isMergeNode()) {
6586     // Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
6587     // prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
6588     // }
6589     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
6590   }
6591
6592   public void _debug_writeFlowGraph() {
6593     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
6594
6595     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
6596       MethodDescriptor md = (MethodDescriptor) iterator.next();
6597       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
6598       GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
6599       try {
6600         fg.writeGraph();
6601         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
6602       } catch (IOException e) {
6603         e.printStackTrace();
6604       }
6605     }
6606
6607   }
6608
6609 }
6610
6611 class CyclicFlowException extends Exception {
6612
6613 }
6614
6615 class InterDescriptor extends Descriptor {
6616
6617   Pair<MethodInvokeNode, Integer> minArgIdxPair;
6618
6619   public InterDescriptor(String name) {
6620     super(name);
6621   }
6622
6623   public void setMethodArgIdxPair(MethodInvokeNode min, int idx) {
6624     minArgIdxPair = new Pair<MethodInvokeNode, Integer>(min, new Integer(idx));
6625   }
6626
6627   public Pair<MethodInvokeNode, Integer> getMethodArgIdxPair() {
6628     return minArgIdxPair;
6629   }
6630
6631 }