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