1 package Analysis.SSJava;
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;
18 import java.util.Stack;
19 import java.util.Vector;
21 import IR.ClassDescriptor;
23 import IR.FieldDescriptor;
24 import IR.MethodDescriptor;
25 import IR.NameDescriptor;
28 import IR.SymbolTable;
29 import IR.TypeDescriptor;
30 import IR.VarDescriptor;
31 import IR.Tree.ArrayAccessNode;
32 import IR.Tree.AssignmentNode;
33 import IR.Tree.BlockExpressionNode;
34 import IR.Tree.BlockNode;
35 import IR.Tree.BlockStatementNode;
36 import IR.Tree.CastNode;
37 import IR.Tree.CreateObjectNode;
38 import IR.Tree.DeclarationNode;
39 import IR.Tree.ExpressionNode;
40 import IR.Tree.FieldAccessNode;
41 import IR.Tree.IfStatementNode;
43 import IR.Tree.LiteralNode;
44 import IR.Tree.LoopNode;
45 import IR.Tree.MethodInvokeNode;
46 import IR.Tree.NameNode;
47 import IR.Tree.OpNode;
48 import IR.Tree.ReturnNode;
49 import IR.Tree.SubBlockNode;
50 import IR.Tree.SwitchBlockNode;
51 import IR.Tree.SwitchStatementNode;
52 import IR.Tree.TertiaryNode;
53 import IR.Tree.TreeNode;
56 public class LocationInference {
59 SSJavaAnalysis ssjava;
61 List<ClassDescriptor> temp_toanalyzeList;
62 List<MethodDescriptor> temp_toanalyzeMethodList;
63 Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
65 LinkedList<MethodDescriptor> toanalyze_methodDescList;
67 // map a method descriptor to its set of parameter descriptors
68 Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
70 // keep current descriptors to visit in fixed-point interprocedural analysis,
71 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
73 // map a class descriptor to a field lattice
74 private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
76 // map a method descriptor to a method lattice
77 private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
79 // map a method/class descriptor to a hierarchy graph
80 private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
82 // map a method/class descriptor to a skeleton hierarchy graph
83 private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
85 private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
87 // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
88 private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
90 // map a descriptor to a simple lattice
91 private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
93 // map a method descriptor to the set of method invocation nodes which are
94 // invoked by the method descriptor
95 private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
97 private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
99 private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
101 private Map<MethodInvokeNode, Set<NTuple<Location>>> mapMethodInvokeNodeToPCLocTupleSet;
103 private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
105 private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
107 private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
109 private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
111 private Map<String, Vector<String>> mapFileNameToLineVector;
113 private Map<Descriptor, Integer> mapDescToDefinitionLine;
115 private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
117 private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescToMethodInvokeNodeSet;
119 // maps a method descriptor to a sub global flow graph that captures all value flows caused by the
120 // set of callees reachable from the method
121 private Map<MethodDescriptor, GlobalFlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
123 private Map<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>> mapMethodInvokeNodeToMapCallerArgToCalleeArg;
125 private Map<MethodDescriptor, Boolean> mapMethodDescriptorToCompositeReturnCase;
127 public static final String GLOBALLOC = "GLOBALLOC";
129 public static final String INTERLOC = "INTERLOC";
131 public static final String PCLOC = "_PCLOC_";
133 public static final String RLOC = "_RLOC_";
135 public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
137 public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP);
139 public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM);
141 public static final Descriptor RETURNLOC = new NameDescriptor(RLOC);
143 public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL");
145 public static final HNode TOPHNODE = new HNode(TOPDESC);
147 public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC);
149 public static String newline = System.getProperty("line.separator");
151 LocationInfo curMethodInfo;
153 private boolean hasChanges = false;
155 boolean debug = true;
157 public static int locSeed = 0;
159 private Stack<String> arrayAccessNodeStack;
161 public LocationInference(SSJavaAnalysis ssjava, State state) {
162 this.ssjava = ssjava;
164 this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
165 this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
166 this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
167 this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
168 this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
169 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
170 this.mapMethodDescriptorToMethodInvokeNodeSet =
171 new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
172 this.mapMethodInvokeNodeToArgIdxMap =
173 new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
174 this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
175 this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
176 this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
178 this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
179 this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
180 this.mapMethodDescToParamNodeFlowsToReturnValue =
181 new HashMap<MethodDescriptor, Set<FlowNode>>();
183 this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
184 this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
186 this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
187 this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
188 this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
190 this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
192 this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
194 this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
196 this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
197 new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
199 this.mapMethodInvokeNodeToPCLocTupleSet =
200 new HashMap<MethodInvokeNode, Set<NTuple<Location>>>();
202 this.arrayAccessNodeStack = new Stack<String>();
204 this.mapMethodDescToMethodInvokeNodeSet =
205 new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
207 this.mapMethodDescriptorToCompositeReturnCase = new HashMap<MethodDescriptor, Boolean>();
211 public void setupToAnalyze() {
212 SymbolTable classtable = state.getClassSymbolTable();
213 temp_toanalyzeList.clear();
214 temp_toanalyzeList.addAll(classtable.getValueSet());
215 // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
216 // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
217 // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
222 public void setupToAnalazeMethod(ClassDescriptor cd) {
224 SymbolTable methodtable = cd.getMethodTable();
225 temp_toanalyzeMethodList.clear();
226 temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
227 Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
228 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
229 return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
234 public boolean toAnalyzeMethodIsEmpty() {
235 return temp_toanalyzeMethodList.isEmpty();
238 public boolean toAnalyzeIsEmpty() {
239 return temp_toanalyzeList.isEmpty();
242 public ClassDescriptor toAnalyzeNext() {
243 return temp_toanalyzeList.remove(0);
246 public MethodDescriptor toAnalyzeMethodNext() {
247 return temp_toanalyzeMethodList.remove(0);
250 public void inference() {
254 // construct value flow graph
255 constructFlowGraph();
257 constructGlobalFlowGraph();
261 assignCompositeLocation();
263 calculateExtraLocations();
264 addAdditionalOrderingConstraints();
266 _debug_writeFlowGraph();
270 constructHierarchyGraph();
272 debug_writeHierarchyDotFiles();
274 simplifyHierarchyGraph();
276 debug_writeSimpleHierarchyDotFiles();
278 constructSkeletonHierarchyGraph();
280 debug_writeSkeletonHierarchyDotFiles();
282 insertCombinationNodes();
284 debug_writeSkeletonCombinationHierarchyDotFiles();
288 debug_writeLattices();
290 updateCompositeLocationAssignments();
292 generateMethodSummary();
294 generateAnnoatedCode();
300 private void checkReturnNodes() {
301 LinkedList<MethodDescriptor> methodDescList =
302 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
304 while (!methodDescList.isEmpty()) {
305 MethodDescriptor md = methodDescList.removeLast();
307 if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
308 checkFlowNodeReturnThisField(md);
310 // // in this case, this method will return the composite location that starts with 'this'
311 // FlowGraph flowGraph = getFlowGraph(md);
312 // Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
319 private void updateFlowGraph() {
321 LinkedList<MethodDescriptor> methodDescList =
322 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
324 while (!methodDescList.isEmpty()) {
325 MethodDescriptor md = methodDescList.removeLast();
326 if (state.SSJAVADEBUG) {
327 System.out.println();
328 System.out.println("SSJAVA: Updating a flow graph: " + md);
329 propagateFlowsFromCalleesWithNoCompositeLocation(md);
334 public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
335 MethodInvokeNode min) {
337 if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
338 mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
339 new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
342 return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
345 public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
346 NTuple<Descriptor> calleeParam) {
347 getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
350 private void assignCompositeLocation() {
351 calculateGlobalValueFlowCompositeLocation();
352 translateCompositeLocationAssignmentToFlowGraph();
355 private void translateCompositeLocationAssignmentToFlowGraph() {
356 System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
357 MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
358 translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
361 private void translateCompositeLocationAssignmentToFlowGraph2() {
362 System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
363 MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
364 translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
367 private void addAdditionalOrderingConstraints() {
368 System.out.println("\nSSJAVA: Add addtional ordering constriants:");
369 MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
370 addAddtionalOrderingConstraints(methodEventLoopDesc);
373 private void updateCompositeLocationAssignments() {
375 LinkedList<MethodDescriptor> methodDescList =
376 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
378 while (!methodDescList.isEmpty()) {
379 MethodDescriptor md = methodDescList.removeLast();
381 System.out.println("\n#updateCompositeLocationAssignments=" + md);
383 FlowGraph flowGraph = getFlowGraph(md);
385 MethodSummary methodSummary = getMethodSummary(md);
387 Set<FlowNode> nodeSet = flowGraph.getNodeSet();
388 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
389 FlowNode node = (FlowNode) iterator.next();
390 System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple());
391 if (node.getCompositeLocation() != null) {
392 CompositeLocation compLoc = node.getCompositeLocation();
393 CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc);
394 node.setCompositeLocation(updatedCompLoc);
395 System.out.println("---updatedCompLoc1=" + updatedCompLoc);
397 NTuple<Descriptor> descTuple = node.getDescTuple();
398 System.out.println("update desc=" + descTuple);
399 CompositeLocation compLoc = convertToCompositeLocation(md, descTuple);
400 compLoc = updateCompositeLocation(compLoc);
401 node.setCompositeLocation(compLoc);
402 System.out.println("---updatedCompLoc2=" + compLoc);
405 if (node.isDeclaratonNode()) {
406 Descriptor localVarDesc = node.getDescTuple().get(0);
407 CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation());
408 methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc);
412 // update PCLOC and RETURNLOC if they have a composite location assignment
413 if (methodSummary.getRETURNLoc() != null) {
414 methodSummary.setRETURNLoc(updateCompositeLocation(methodSummary.getRETURNLoc()));
416 if (methodSummary.getPCLoc() != null) {
417 methodSummary.setPCLoc(updateCompositeLocation(methodSummary.getPCLoc()));
424 private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) {
425 CompositeLocation updatedCompLoc = new CompositeLocation();
426 for (int i = 0; i < compLoc.getSize(); i++) {
427 Location loc = compLoc.get(i);
428 String nodeIdentifier = loc.getLocIdentifier();
429 Descriptor enclosingDesc = loc.getDescriptor();
431 if (!enclosingDesc.equals(GLOBALDESC)) {
432 LocationSummary locSummary = getLocationSummary(enclosingDesc);
433 HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
434 if (scGraph != null) {
435 HNode curNode = scGraph.getCurrentHNode(nodeIdentifier);
436 if (curNode != null) {
437 nodeIdentifier = curNode.getName();
440 locName = locSummary.getLocationName(nodeIdentifier);
442 locName = nodeIdentifier;
444 Location updatedLoc = new Location(enclosingDesc, locName);
445 updatedCompLoc.addLocation(updatedLoc);
448 return updatedCompLoc;
451 private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
453 System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller="
456 // First, assign a composite location to a node in the flow graph
457 GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
459 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
460 Map<Location, CompositeLocation> callerMapLocToCompLoc =
461 callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
463 Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
464 for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
465 Location methodLoc = (Location) iterator.next();
466 if (methodLoc.getDescriptor().equals(mdCaller)) {
467 CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
468 assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
472 Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
474 Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
475 for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
476 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
477 // need to translate a composite location that is started with the base
479 translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
480 MethodDescriptor mdCallee = min.getMethod();
481 calleeSet.add(mdCallee);
483 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
485 NTuple<Descriptor> methodInvokeBaseDescTuple = mapMethodInvokeNodeToBaseTuple.get(min);
486 NTuple<Location> methodInvokeBaseLocTuple = null;
487 if (methodInvokeBaseDescTuple != null) {
488 methodInvokeBaseLocTuple = translateToLocTuple(mdCaller, methodInvokeBaseDescTuple);
494 // If the location of an argument has a composite location
495 // need to assign a proper composite location to the corresponding callee parameter
496 // System.out.println("---translate arg composite location to callee param. min="
497 // + min.printNode(0));
498 Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
499 Set<Integer> idxSet = mapIdxToArgTuple.keySet();
500 for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) {
501 Integer idx = (Integer) iterator2.next();
503 if (idx == 0 && !min.getMethod().isStatic()) {
507 NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
508 if (argTuple.size() > 0) {
509 // check if an arg tuple has been already assigned to a composite location
510 NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
511 Location argLocalLoc = argLocTuple.get(0);
513 // if (!isPrimitiveType(argTuple)) {
514 if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
516 CompositeLocation argLocalCompositeLocation = callerMapLocToCompLoc.get(argLocalLoc);
517 CompositeLocation argCompLoc = argLocalCompositeLocation.clone();
518 for (int i = 1; i < argLocTuple.size(); i++) {
519 argCompLoc.addLocation(argLocTuple.get(i));
522 FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
525 .println("----- argLocTuple=" + argLocTuple + " argLocalLoc=+" + argLocalLoc);
526 System.out.println("-------need to translate argCompLoc=" + argCompLoc
527 + " with baseTuple=" + methodInvokeBaseLocTuple + " calleeParamLocTuple="
528 + calleeParamFlowNode);
530 // CompositeLocation paramCompLoc = translateArgCompLocToParamCompLoc(min, argCompLoc);
531 // calleeParamFlowNode.setCompositeLocation(paramCompLoc);
533 // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
535 // FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
536 // NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
537 // NTuple<Location> calleeParamLocTuple
538 // =###translateCompositeLocationAssignmentToFlowGraph mdCaller=public static void
539 // huffcodetab.huffman_decoder(int htIdx, int x, BitReserve br)
541 // translateToLocTuple(mdCallee, calleeParamDescTuple);
543 // System.out.println("---need to translate callerCompLoc=" + callerCompLoc
544 // + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple="
545 // + calleeParamLocTuple);
547 // CompositeLocation newCalleeCompLoc =
548 // translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
550 // calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
551 // newCalleeCompLoc);
553 // System.out.println("---callee loc=" + calleeParamLocTuple.get(0)
554 // + " newCalleeCompLoc=" + newCalleeCompLoc);
556 // // System.out.println("###need to assign composite location to=" +
557 // // calleeParamDescTuple
558 // // + " with baseTuple=" + baseLocTuple);
568 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
569 MethodDescriptor callee = (MethodDescriptor) iterator.next();
570 translateCompositeLocationAssignmentToFlowGraph(callee);
573 // for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
574 // MethodInvokeNode min = (MethodInvokeNode) iterator.next();
575 // // add an additional ordering constraint
576 // // if the first element of a parameter composite location matches 'this' reference,
577 // // the corresponding argument in the caller is required to be higher than the translated
578 // // parameter location in the caller lattice
580 // // addOrderingConstraintFromCompLocParamToArg(mdCaller, min);
585 private CompositeLocation translateArgCompLocToParamCompLoc(MethodInvokeNode min,
586 CompositeLocation argCompLoc) {
588 System.out.println("--------translateArgCompLocToParamCompLoc argCompLoc=" + argCompLoc);
589 MethodDescriptor mdCallee = min.getMethod();
590 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
592 NTuple<Location> argLocTuple = argCompLoc.getTuple();
593 Location argLocalLoc = argLocTuple.get(0);
595 Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
596 Set<Integer> idxSet = mapIdxToArgTuple.keySet();
597 for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) {
598 Integer idx = (Integer) iterator2.next();
600 if (idx == 0 && !min.getMethod().isStatic()) {
604 NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
605 if (argTuple.size() > 0 && argTuple.get(0).equals(argLocalLoc.getLocDescriptor())) {
606 // it matches with the current argument composite location
607 // so what is the corresponding parameter local descriptor?
608 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
609 System.out.println("----------found paramNode=" + paramNode);
610 NTuple<Descriptor> paramDescTuple = paramNode.getCurrentDescTuple();
612 NTuple<Location> newParamTupleFromArgTuple = translateToLocTuple(mdCallee, paramDescTuple);
613 for (int i = 1; i < argLocTuple.size(); i++) {
614 newParamTupleFromArgTuple.add(argLocTuple.get(i));
617 System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple);
618 return new CompositeLocation(newParamTupleFromArgTuple);
625 private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) {
627 // First, assign a composite location to a node in the flow graph
628 GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
630 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
631 Map<Location, CompositeLocation> callerMapLocToCompLoc =
632 callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
633 Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
635 Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
637 Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
638 for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
639 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
640 MethodDescriptor mdCallee = min.getMethod();
641 calleeSet.add(mdCallee);
644 // add an additional ordering constraint
645 // if the first element of a parameter composite location matches 'this' reference,
646 // the corresponding argument in the caller is required to be higher than the translated
647 // parameter location in the caller lattice
649 // addOrderingConstraintFromCompLocParamToArg(mdCaller, min);
652 // update return flow nodes in the caller
653 CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc();
655 System.out.println("### min=" + min.printNode(0) + " returnLoc=" + returnLoc);
656 if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis())
657 && returnLoc.getSize() > 1) {
658 System.out.println("###RETURN COMP LOC=" + returnLoc);
659 NTuple<Location> returnLocTuple = returnLoc.getTuple();
660 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
661 NTuple<Descriptor> newReturnTuple = baseTuple.clone();
662 for (int i = 1; i < returnLocTuple.size(); i++) {
663 newReturnTuple.add(returnLocTuple.get(i).getLocDescriptor());
665 System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple);
666 callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple);
671 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
672 MethodDescriptor callee = (MethodDescriptor) iterator.next();
673 addAddtionalOrderingConstraints(callee);
678 private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) {
679 MethodDescriptor md = min.getMethod();
680 if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
681 mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
683 mapMethodDescToMethodInvokeNodeSet.get(md).add(min);
686 private Set<MethodInvokeNode> getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) {
687 if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
688 mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
690 return mapMethodDescToMethodInvokeNodeSet.get(md);
693 private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller,
694 MethodInvokeNode min) {
695 System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0));
697 GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(ssjava.getMethodContainingSSJavaLoop());
699 Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
701 MethodDescriptor mdCallee = min.getMethod();
703 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
704 for (int idx = 0; idx < calleeFlowGraph.getNumParameters(); idx++) {
705 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
706 NTuple<Location> globalParamLocTuple =
707 translateToLocTuple(mdCallee, paramNode.getDescTuple());
708 translateToLocTuple(mdCallee, paramNode.getDescTuple());
709 CompositeLocation compLoc = paramNode.getCompositeLocation();
710 System.out.println("---paramNode=" + paramNode + " compLoc=" + compLoc);
711 if (compLoc != null) {
712 NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
713 NTuple<Location> globalArgLocTuple = translateToLocTuple(mdCaller, argTuple);
715 if (!isLiteralValueLocTuple(globalArgLocTuple)
716 && !isLiteralValueLocTuple(globalParamLocTuple)) {
717 if (!globalGraph.hasValueFlowEdge(globalArgLocTuple, globalParamLocTuple)) {
718 System.out.println("----- add global flow globalArgLocTuple=" + globalArgLocTuple
719 + "-> globalParamLocTuple=" + globalParamLocTuple);
721 globalGraph.addValueFlowEdge(globalArgLocTuple, globalParamLocTuple);
725 for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
726 NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
728 if (!isLiteralValueLocTuple(pcLocTuple) && !isLiteralValueLocTuple(globalParamLocTuple)) {
729 if (!globalGraph.hasValueFlowEdge(pcLocTuple, globalParamLocTuple)) {
731 .println("----- add global flow PCLOC="
733 + "-> globalParamLocTu!globalArgLocTuple.get(0).getLocDescriptor().equals(LITERALDESC)ple="
734 + globalParamLocTuple);
736 globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple);
745 private boolean isLiteralValueLocTuple(NTuple<Location> locTuple) {
746 return locTuple.get(0).getLocDescriptor().equals(LITERALDESC);
749 public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
750 CompositeLocation inferCompLoc) {
751 Descriptor localDesc = loc.getLocDescriptor();
753 Set<FlowNode> nodeSet = flowGraph.getNodeSet();
754 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
755 FlowNode node = (FlowNode) iterator.next();
756 if (node.getDescTuple().startsWith(localDesc)
757 && !node.getDescTuple().get(0).equals(LITERALDESC)) {
758 // need to assign the inferred composite location to this node
759 CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
760 node.setCompositeLocation(newCompLoc);
761 System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc);
766 private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
767 CompositeLocation inferCompLoc) {
769 System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
772 CompositeLocation newCompLoc = new CompositeLocation();
773 for (int i = 0; i < inferCompLoc.getSize(); i++) {
774 newCompLoc.addLocation(inferCompLoc.get(i));
777 Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
778 Descriptor enclosingDescriptor;
779 if (lastDescOfPrefix instanceof InterDescriptor) {
780 enclosingDescriptor = null;
782 enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
785 for (int i = 1; i < nodeDescTuple.size(); i++) {
786 Descriptor desc = nodeDescTuple.get(i);
787 Location locElement = new Location(enclosingDescriptor, desc);
788 newCompLoc.addLocation(locElement);
790 enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
796 private void translateMapLocationToInferCompositeLocationToCalleeGraph(
797 GlobalFlowGraph callerGraph, MethodInvokeNode min) {
799 MethodDescriptor mdCallee = min.getMethod();
800 MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
801 Map<Location, CompositeLocation> callerMapLocToCompLoc =
802 callerGraph.getMapLocationToInferCompositeLocation();
804 Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
806 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
807 GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
809 NTuple<Location> baseLocTuple = null;
810 if (mapMethodInvokeNodeToBaseTuple.containsKey(min)) {
811 baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
814 System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee="
815 + mdCallee + " baseLocTuple=" + baseLocTuple);
816 // System.out.println("-mapIdxToArgTuple=" + mapIdxToArgTuple);
817 // System.out.println("-callerMapLocToCompLoc=" + callerMapLocToCompLoc);
819 Set<Location> keySet = callerMapLocToCompLoc.keySet();
820 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
821 Location key = (Location) iterator.next();
822 CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
824 if (!key.getDescriptor().equals(mdCaller)) {
826 CompositeLocation newCalleeCompLoc;
827 if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
828 // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc
829 // + " with baseTuple=" + baseLocTuple);
831 translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
833 calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
834 // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc
835 // + " newCalleeCompLoc=" + newCalleeCompLoc);
836 // System.out.println("-----baseLoctuple=" + baseLocTuple);
837 // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee);
839 // check if it is the global access
840 Location compLocFirstElement = callerCompLoc.getTuple().get(0);
841 if (compLocFirstElement.getDescriptor().equals(mdCallee)
842 && compLocFirstElement.getLocDescriptor().equals(GLOBALDESC)) {
844 newCalleeCompLoc = new CompositeLocation();
845 Location newMethodLoc = new Location(mdCallee, GLOBALDESC);
847 newCalleeCompLoc.addLocation(newMethodLoc);
848 for (int i = 1; i < callerCompLoc.getSize(); i++) {
849 newCalleeCompLoc.addLocation(callerCompLoc.get(i));
851 calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
852 // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc
853 // + " newCalleeCompLoc=" + newCalleeCompLoc);
854 // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee);
857 int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
858 if (paramIdx == -1) {
859 System.out.println("*****key=" + key + " callerCompLoc=" + callerCompLoc);
860 if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) {
861 calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc);
865 NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(paramIdx);
867 FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx);
868 NTuple<Location> paramLocTuple =
869 translateToLocTuple(mdCallee, paramFlowNode.getDescTuple());
870 newCalleeCompLoc = new CompositeLocation();
871 for (int i = 0; i < paramLocTuple.size(); i++) {
872 newCalleeCompLoc.addLocation(paramLocTuple.get(i));
874 for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) {
875 newCalleeCompLoc.addLocation(callerCompLoc.get(i));
877 calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
878 System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc
879 + " newCalleeCompLoc=" + newCalleeCompLoc);
880 System.out.println("-----argTuple=" + argTuple + " caller=" + mdCaller + " callee="
882 System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode);
891 // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING="
892 // + calleeGlobalGraph.getMapLocationToInferCompositeLocation());
894 System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + " caller="
896 // If the location of an argument has a composite location
897 // need to assign a proper composite location to the corresponding callee parameter
898 Set<Integer> idxSet = mapIdxToArgTuple.keySet();
899 for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
900 Integer idx = (Integer) iterator.next();
902 if (idx == 0 && !min.getMethod().isStatic()) {
906 NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
907 System.out.println("-argTuple=" + argTuple + " idx=" + idx);
908 if (argTuple.size() > 0) {
909 // check if an arg tuple has been already assigned to a composite location
910 NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
911 Location argLocalLoc = argLocTuple.get(0);
913 // if (!isPrimitiveType(argTuple)) {
914 if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
916 CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
917 for (int i = 1; i < argLocTuple.size(); i++) {
918 callerCompLoc.addLocation(argLocTuple.get(i));
921 System.out.println("---callerCompLoc=" + callerCompLoc);
923 // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
925 FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
927 NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
928 NTuple<Location> calleeParamLocTuple =
929 translateToLocTuple(mdCallee, calleeParamDescTuple);
931 int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
932 System.out.println("-----paramIdx=" + refParamIdx);
933 if (refParamIdx == 0 && !mdCallee.isStatic()) {
935 System.out.println("-------need to translate callerCompLoc=" + callerCompLoc
936 + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple="
937 + calleeParamLocTuple);
939 CompositeLocation newCalleeCompLoc =
940 translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
942 calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
945 System.out.println("---------key=" + calleeParamLocTuple.get(0) + " callerCompLoc="
946 + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc);
948 } else if (refParamIdx != -1) {
949 // the first element of an argument composite location matches with one of paramtere
950 // composite locations
952 System.out.println("-------param match case=");
954 NTuple<Descriptor> argTupleRef = mapIdxToArgTuple.get(refParamIdx);
955 FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx);
956 NTuple<Location> refParamLocTuple =
957 translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple());
959 System.out.println("---------refParamLocTuple=" + refParamLocTuple
960 + " from argTupleRef=" + argTupleRef);
962 CompositeLocation newCalleeCompLoc = new CompositeLocation();
963 for (int i = 0; i < refParamLocTuple.size(); i++) {
964 newCalleeCompLoc.addLocation(refParamLocTuple.get(i));
966 for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) {
967 newCalleeCompLoc.addLocation(callerCompLoc.get(i));
970 calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
973 System.out.println("-----------key=" + calleeParamLocTuple.get(0) + " callerCompLoc="
974 + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc);
978 System.out.println("-----------------calleeParamFlowNode="
979 + calleeParamFlowNode.getCompositeLocation());
990 private int getParamIdx(CompositeLocation compLoc,
991 Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple) {
993 // if the composite location is started with the argument descriptor
994 // return the argument's index. o.t. return -1
996 Set<Integer> keySet = mapIdxToArgTuple.keySet();
997 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
998 Integer key = (Integer) iterator.next();
999 NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(key);
1000 if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) {
1001 System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple);
1002 return key.intValue();
1009 private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
1011 Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
1013 if (lastDesc instanceof FieldDescriptor) {
1014 return ((FieldDescriptor) lastDesc).getType().isPrimitive();
1015 } else if (lastDesc instanceof VarDescriptor) {
1016 return ((VarDescriptor) lastDesc).getType().isPrimitive();
1017 } else if (lastDesc instanceof InterDescriptor) {
1024 private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
1025 NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
1027 CompositeLocation newCalleeCompLoc = new CompositeLocation();
1029 Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
1030 newCalleeCompLoc.addLocation(calleeThisLoc);
1032 // remove the base tuple from the caller
1033 // ex; In the method invoation foo.bar.methodA(), the callee will have the composite location
1034 // ,which is relative to the 'this' variable, <THIS,...>
1035 for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
1036 newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1039 return newCalleeCompLoc;
1043 private void calculateGlobalValueFlowCompositeLocation() {
1045 System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
1046 MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1047 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1049 Set<Location> calculatedPrefixSet = new HashSet<Location>();
1051 Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
1053 next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1054 GlobalFlowNode node = (GlobalFlowNode) iterator.next();
1056 Location prefixLoc = node.getLocTuple().get(0);
1058 if (calculatedPrefixSet.contains(prefixLoc)) {
1059 // the prefix loc has been already assigned to a composite location
1063 calculatedPrefixSet.add(prefixLoc);
1065 // Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
1066 List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
1068 Set<GlobalFlowNode> reachableNodeSet =
1069 globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
1070 // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
1072 // System.out.println("node=" + node + " prefixList=" + prefixList);
1074 for (int i = 0; i < prefixList.size(); i++) {
1075 NTuple<Location> curPrefix = prefixList.get(i);
1076 Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1078 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1079 GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
1080 if (reachNode.getLocTuple().startsWith(curPrefix)) {
1081 reachableCommonPrefixSet.add(reachNode.getLocTuple());
1084 // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
1086 if (!reachableCommonPrefixSet.isEmpty()) {
1088 MethodDescriptor curPrefixFirstElementMethodDesc =
1089 (MethodDescriptor) curPrefix.get(0).getDescriptor();
1091 MethodDescriptor nodePrefixLocFirstElementMethodDesc =
1092 (MethodDescriptor) prefixLoc.getDescriptor();
1094 // System.out.println("curPrefixFirstElementMethodDesc=" +
1095 // curPrefixFirstElementMethodDesc);
1096 // System.out.println("nodePrefixLocFirstElementMethodDesc="
1097 // + nodePrefixLocFirstElementMethodDesc);
1099 if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
1100 || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
1101 curPrefixFirstElementMethodDesc)) {
1104 // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
1106 Location curPrefixLocalLoc = curPrefix.get(0);
1107 if (globalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
1108 // in this case, the local variable of the current prefix has already got a composite
1110 // so we just ignore the current composite location.
1112 // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
1113 // + " DUE TO " + curPrefix);
1118 if (!needToGenerateCompositeLocation(node, curPrefix)) {
1119 System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix="
1121 // System.out.println("prefixList=" + prefixList);
1122 // System.out.println("reachableNodeSet=" + reachableNodeSet);
1126 Location targetLocalLoc = node.getLocTuple().get(0);
1127 CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
1128 System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
1129 System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc="
1131 globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
1146 private boolean checkFlowNodeReturnThisField(MethodDescriptor md) {
1148 MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1149 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1151 FlowGraph flowGraph = getFlowGraph(md);
1153 ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis());
1154 if (enclosingDesc == null) {
1159 Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
1160 Set<GlobalFlowNode> globalReturnNodeSet = new HashSet<GlobalFlowNode>();
1161 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1162 FlowNode flowNode = (FlowNode) iterator.next();
1163 NTuple<Location> locTuple = translateToLocTuple(md, flowNode.getDescTuple());
1164 GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple);
1165 globalReturnNodeSet.add(globalReturnNode);
1167 List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode);
1168 for (int i = 0; i < prefixList.size(); i++) {
1169 NTuple<Location> curPrefix = prefixList.get(i);
1170 ClassDescriptor cd =
1171 getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor());
1172 if (cd != null && cd.equals(enclosingDesc)) {
1180 if (count == returnNodeSet.size()) {
1181 // in this case, all return nodes in the method returns values coming from a location that
1182 // starts with "this"
1184 System.out.println("$$$SET RETURN LOC TRUE=" + md);
1185 mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE);
1187 // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++));
1188 // NTuple<Descriptor> rDescTuple = new NTuple<Descriptor>();
1189 // rDescTuple.add(md.getThis());
1190 // rDescTuple.add(returnLocDesc);
1192 // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1193 // FlowNode rnode = (FlowNode) iterator.next();
1194 // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple);
1197 // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md,
1201 mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE);
1204 return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1208 private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple<Location> curPrefix) {
1209 // return true if there is a path between a node to which we want to give a composite location
1210 // and nodes which start with curPrefix
1212 System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix);
1214 Location targetLocalLoc = node.getLocTuple().get(0);
1216 MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor();
1217 FlowGraph flowGraph = getFlowGraph(md);
1218 FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple());
1219 Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
1221 if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) {
1222 Pair<MethodInvokeNode, Integer> pair =
1223 ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair();
1226 System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc);
1228 MethodInvokeNode min = pair.getFirst();
1229 Integer paramIdx = pair.getSecond();
1230 MethodDescriptor mdCallee = min.getMethod();
1232 FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx);
1233 if (checkNodeReachToReturnNode(mdCallee, paramNode)) {
1241 if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
1242 boolean hasCompReturnLocWithThis =
1243 mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1245 if (hasCompReturnLocWithThis) {
1247 if (checkNodeReachToReturnNode(md, flowNode)) {
1251 // for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) {
1252 // FlowNode returnFlowNode = (FlowNode) iterator.next();
1253 // if (reachableSet.contains(returnFlowNode)) {
1261 // System.out.println("flowGraph.getReturnNodeSet()=" + flowGraph.getReturnNodeSet());
1262 // System.out.println("flowGraph.contains(node.getDescTuple())="
1263 // + flowGraph.contains(node.getDescTuple()) + " flowGraph.getFlowNode(node.getDescTuple())="
1264 // + flowGraph.getFlowNode(node.getDescTuple()));reachableSet
1266 // if (flowGraph.contains(node.getDescTuple())
1267 // && flowGraph.getReturnNodeSet().contains(flowGraph.getFlowNode(node.getDescTuple()))) {
1268 // // return checkFlowNodeReturnThisField(flowGraph);
1271 Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1);
1272 // check whether prefix appears in the list of parameters
1273 Set<MethodInvokeNode> minSet = mapMethodDescToMethodInvokeNodeSet.get(md);
1274 found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1275 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1276 Map<Integer, NTuple<Descriptor>> map = mapMethodInvokeNodeToArgIdxMap.get(min);
1277 Set<Integer> keySet = map.keySet();
1278 System.out.println("min=" + min.printNode(0));
1279 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1280 Integer argIdx = (Integer) iterator2.next();
1281 NTuple<Descriptor> argTuple = map.get(argIdx);
1282 if (argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) {
1283 NTuple<Location> locTuple =
1284 translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple());
1285 lastLocationOfPrefix = locTuple.get(0);
1292 if (lastLocationOfPrefix.getLocDescriptor() instanceof VarDescriptor) {
1293 cd = ((VarDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc();
1295 // it is a field descriptor
1296 cd = ((FieldDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc();
1299 GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
1300 Set<GlobalFlowNode> subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node);
1302 for (Iterator iterator2 = subGlobalReachableSet.iterator(); iterator2.hasNext();) {
1303 GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator2.next();
1304 // NTuple<Location> locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple());
1305 NTuple<Location> locTuple = subGlobalReachalbeNode.getLocTuple();
1307 for (int i = 0; i < locTuple.size(); i++) {
1308 if (locTuple.get(i).equals(lastLocationOfPrefix)) {
1312 Location lastLoc = locTuple.get(locTuple.size() - 1);
1313 Descriptor enclosingDescriptor = lastLoc.getDescriptor();
1315 if (enclosingDescriptor != null && enclosingDescriptor.equals(cd)) {
1316 System.out.println("# WHY HERE?");
1317 System.out.println("subGlobalReachalbeNode="+subGlobalReachalbeNode);
1325 private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) {
1327 FlowGraph flowGraph = getFlowGraph(md);
1328 Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(node);
1329 if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
1330 boolean hasCompReturnLocWithThis =
1331 mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1333 if (hasCompReturnLocWithThis) {
1334 for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) {
1335 FlowNode returnFlowNode = (FlowNode) iterator.next();
1336 if (reachableSet.contains(returnFlowNode)) {
1345 private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
1346 CompositeLocation newCompLoc = compLocPrefix.clone();
1347 NTuple<Location> locTuple = node.getLocTuple();
1348 for (int i = 1; i < locTuple.size(); i++) {
1349 newCompLoc.addLocation(locTuple.get(i));
1351 node.setInferCompositeLocation(newCompLoc);
1354 private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
1356 System.out.println("\n##### calculatePrefixList node=" + node);
1358 Set<GlobalFlowNode> incomingNodeSetPrefix =
1359 graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0));
1360 System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix);
1362 Set<GlobalFlowNode> reachableNodeSetPrefix =
1363 graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
1364 System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix);
1366 List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
1368 for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
1369 GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
1370 NTuple<Location> inNodeTuple = inNode.getLocTuple();
1372 if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor
1373 || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) {
1377 for (int i = 1; i < inNodeTuple.size(); i++) {
1378 NTuple<Location> prefix = inNodeTuple.subList(0, i);
1379 if (!prefixList.contains(prefix)) {
1380 prefixList.add(prefix);
1385 Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
1386 public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
1387 int s0 = arg0.size();
1388 int s1 = arg1.size();
1391 } else if (s0 == s1) {
1399 // remove a prefix which is not suitable for generating composite location
1400 Location localVarLoc = node.getLocTuple().get(0);
1401 MethodDescriptor md = (MethodDescriptor) localVarLoc.getDescriptor();
1402 ClassDescriptor cd = md.getClassDesc();
1405 Set<NTuple<Location>> toberemoved = new HashSet<NTuple<Location>>();
1406 // for (int i = 0; i < prefixList.size(); i++) {
1407 // NTuple<Location> prefixLocTuple = prefixList.get(i);
1408 // if (!containsClassDesc(cd, prefixLocTuple)) {
1409 // toberemoved.add(prefixLocTuple);
1413 // System.out.println("method class=" + cd + " toberemoved=" + toberemoved);
1415 prefixList.removeAll(toberemoved);
1419 // List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
1421 // for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
1422 // GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
1423 // NTuple<Location> inNodeTuple = inNode.getLocTuple();
1425 // for (int i = 1; i < inNodeTuple.size(); i++) {
1426 // NTuple<Location> prefix = inNodeTuple.subList(0, i);
1427 // if (!prefixList.contains(prefix)) {
1428 // prefixList.add(prefix);
1433 // Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
1434 // public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
1435 // int s0 = arg0.size();
1436 // int s1 = arg1.size();
1439 // } else if (s0 == s1) {
1446 // return prefixList;
1449 private boolean containsClassDesc(ClassDescriptor cd, NTuple<Location> prefixLocTuple) {
1450 for (int i = 0; i < prefixLocTuple.size(); i++) {
1451 Location loc = prefixLocTuple.get(i);
1452 Descriptor locDesc = loc.getLocDescriptor();
1453 if (locDesc != null) {
1454 ClassDescriptor type = getClassTypeDescriptor(locDesc);
1455 if (type != null && type.equals(cd)) {
1463 private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
1465 MethodDescriptor md = flowGraph.getMethodDescriptor();
1467 GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md);
1469 // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
1470 Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
1472 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1474 FlowEdge edge = (FlowEdge) iterator.next();
1475 NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
1476 NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
1478 if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode
1479 || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) {
1483 // here only keep the first element(method location) of the descriptor
1485 NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
1486 // Location srcMethodLoc = srcLocTuple.get(0);
1487 // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor();
1488 // // if (flowGraph.isParamDesc(srcVarDesc) &&
1489 // (!srcVarDesc.equals(md.getThis()))) {
1490 // if (!srcVarDesc.equals(md.getThis())) {
1491 // srcLocTuple = new NTuple<Location>();
1492 // Location loc = new Location(md, srcVarDesc);
1493 // srcLocTuple.add(loc);
1496 NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
1497 // Location dstMethodLoc = dstLocTuple.get(0);
1498 // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor();
1499 // if (!dstVarDesc.equals(md.getThis())) {
1500 // dstLocTuple = new NTuple<Location>();
1501 // Location loc = new Location(md, dstVarDesc);
1502 // dstLocTuple.add(loc);
1505 globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
1512 private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
1514 NTuple<Location> locTuple = new NTuple<Location>();
1516 Descriptor enclosingDesc = md;
1517 // System.out.println("md=" + md + " descTuple=" + descTuple);
1518 for (int i = 0; i < descTuple.size(); i++) {
1519 Descriptor desc = descTuple.get(i);
1521 Location loc = new Location(enclosingDesc, desc);
1524 if (desc instanceof VarDescriptor) {
1525 enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
1526 } else if (desc instanceof FieldDescriptor) {
1527 enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
1529 // TODO: inter descriptor case
1530 enclosingDesc = desc;
1539 private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller) {
1541 // the transformation for a call site propagates flows through parameters
1542 // if the method is virtual, it also grab all relations from any possible
1545 Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
1547 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
1548 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1549 MethodDescriptor mdCallee = min.getMethod();
1550 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1551 if (mdCallee.isStatic()) {
1552 setPossibleCallees.add(mdCallee);
1554 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
1555 // removes method descriptors that are not invoked by the caller
1556 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
1557 setPossibleCallees.addAll(calleeSet);
1560 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
1561 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
1562 propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
1569 private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
1570 MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
1572 System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller);
1573 FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
1574 Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
1576 System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)="
1577 + mapMethodInvokeNodeToArgIdxMap.get(min));
1579 Set<Integer> keySet = mapIdxToArg.keySet();
1580 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1581 Integer idx = (Integer) iterator.next();
1582 NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
1583 if (argDescTuple.size() > 0) {
1584 NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
1585 NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
1586 NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
1587 System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple="
1589 addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
1593 // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee);
1595 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1596 GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
1597 Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
1598 for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
1599 GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
1600 addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
1603 System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller);
1604 Set<NTuple<Location>> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min);
1605 System.out.println("---pcLocTupleSet=" + pcLocTupleSet);
1606 GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
1607 for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
1608 GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
1609 if (calleeNode.isParamNodeWithIncomingFlows()) {
1610 NTuple<Location> callerSrcNodeLocTuple =
1611 translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple());
1612 System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
1613 if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
1614 for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) {
1615 NTuple<Location> pcLocTuple = (NTuple<Location>) iterator2.next();
1616 callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple);
1625 private void addValueFlowBetweenParametersToCaller(MethodInvokeNode min,
1626 MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
1628 System.out.println("***addValueFlowBetweenParametersToCaller from mdCallee=" + mdCallee);
1630 Set<NTuple<Location>> PCLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min);
1631 System.out.println("-PCLocTupleSet=" + PCLocTupleSet);
1633 GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1634 GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
1636 // if the parameter A reaches to the parameter B
1637 // then, add an edge the argument A -> the argument B to the global flow graph
1638 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1639 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1640 int numParam = calleeFlowGraph.getNumParameters();
1642 for (int i = 0; i < numParam; i++) {
1643 for (int k = 0; k < numParam; k++) {
1647 System.out.println("i=" + i + " k=" + k);
1649 FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
1650 FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
1652 NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
1653 NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
1655 NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
1656 NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
1658 if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
1659 // if two parameters share the same prefix
1660 // it already has been assigned to a composite location
1661 // so we don't need to add an additional ordering relation caused by these two
1666 NTuple<Location> paramLocTuple1 = translateToLocTuple(mdCallee, paramDescTuple1);
1667 NTuple<Location> paramLocTuple2 = translateToLocTuple(mdCallee, paramDescTuple2);
1669 // check if the callee propagates an ordering constraints through
1672 // Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
1674 Set<GlobalFlowNode> reachToParam1Set =
1675 calleeSubGlobalGraph.getIncomingNodeSetByPrefix(paramLocTuple1.get(0));
1677 // System.out.println("-- localReachSet from param1=" + localReachSet);
1679 GlobalFlowNode globalFlowNodeParam1 = calleeSubGlobalGraph.getFlowNode(paramLocTuple1);
1680 GlobalFlowNode globalFlowNodeParam2 = calleeSubGlobalGraph.getFlowNode(paramLocTuple2);
1682 System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
1685 System.out.println("arg1Tuple=" + arg1Tuple + " arg2Tuple=" + arg2Tuple);
1686 // System.out.println("-reachToParam1Set=" + reachToParam1Set);
1688 if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0
1689 && reachToParam1Set.contains(globalFlowNodeParam2)) {
1690 // need to propagate an ordering relation s.t. arg1 is higher
1692 System.out.println("---param1=" + paramNode1 + " is higher than param2=" + paramNode2);
1694 NTuple<Location> callerSrcNodeLocTuple =
1695 translateToCallerLocTuple(min, mdCallee, mdCaller, paramLocTuple1);
1697 NTuple<Location> callerDstNodeLocTuple =
1698 translateToCallerLocTuple(min, mdCallee, mdCaller, paramLocTuple2);
1700 System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
1701 System.out.println("---callerDstNodeLocTuple=" + callerDstNodeLocTuple);
1703 System.out.println("-----add global value flow :" + callerSrcNodeLocTuple + "->"
1704 + callerDstNodeLocTuple);
1705 callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
1706 for (Iterator iterator = PCLocTupleSet.iterator(); iterator.hasNext();) {
1707 NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
1708 System.out.println("-----add global value flow PC :" + pcLocTuple + "->"
1709 + callerSrcNodeLocTuple);
1710 callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple);
1713 // add a new flow between the corresponding arguments.
1714 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
1715 System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple);
1718 // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
1722 System.out.println();
1729 private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
1730 MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
1732 GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1733 GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
1735 // System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode);
1737 NTuple<Location> callerSrcNodeLocTuple =
1738 translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
1739 // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
1741 if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
1743 Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
1745 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
1746 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
1747 NTuple<Location> callerDstNodeLocTuple =
1748 translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
1749 // System.out.println("outNode=" + outNode + " callerDstNodeLocTuple="
1750 // + callerDstNodeLocTuple);
1751 if (callerDstNodeLocTuple != null) {
1752 callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
1759 private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
1760 MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
1761 // this method will return the same nodeLocTuple if the corresponding argument is literal
1764 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1766 NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
1767 if (calleeFlowGraph.isParameter(nodeDescTuple)) {
1768 int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
1769 NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
1771 // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) {
1772 // // the type of argument is primitive.
1773 // return nodeLocTuple.clone();
1775 System.out.println("paramIdx=" + paramIdx + " argDescTuple=" + argDescTuple);
1776 NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
1778 NTuple<Location> callerLocTuple = new NTuple<Location>();
1780 callerLocTuple.addAll(argLocTuple);
1781 for (int i = 1; i < nodeLocTuple.size(); i++) {
1782 callerLocTuple.add(nodeLocTuple.get(i));
1784 return callerLocTuple;
1786 return nodeLocTuple.clone();
1791 public static boolean isPrimitive(Descriptor desc) {
1793 if (desc instanceof FieldDescriptor) {
1794 return ((FieldDescriptor) desc).getType().isPrimitive();
1795 } else if (desc instanceof VarDescriptor) {
1796 return ((VarDescriptor) desc).getType().isPrimitive();
1797 } else if (desc instanceof InterDescriptor) {
1804 private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
1806 NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
1807 for (int i = 0; i < locTuple.size(); i++) {
1808 descTuple.add(locTuple.get(i).getLocDescriptor());
1814 public LocationSummary getLocationSummary(Descriptor d) {
1815 if (!mapDescToLocationSummary.containsKey(d)) {
1816 if (d instanceof MethodDescriptor) {
1817 mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
1818 } else if (d instanceof ClassDescriptor) {
1819 mapDescToLocationSummary.put(d, new FieldSummary());
1822 return mapDescToLocationSummary.get(d);
1825 private void generateMethodSummary() {
1827 Set<MethodDescriptor> keySet = md2lattice.keySet();
1828 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1829 MethodDescriptor md = (MethodDescriptor) iterator.next();
1831 System.out.println("\nSSJAVA: generate method summary: " + md);
1833 FlowGraph flowGraph = getFlowGraph(md);
1834 MethodSummary methodSummary = getMethodSummary(md);
1836 HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md);
1838 // set the 'this' reference location
1839 if (!md.isStatic()) {
1840 System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName());
1841 methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName());
1844 // set the 'global' reference location if needed
1845 if (methodSummary.hasGlobalAccess()) {
1846 methodSummary.setGlobalLocName(scGraph.getHNode(GLOBALDESC).getName());
1849 // construct a parameter mapping that maps a parameter descriptor to an
1850 // inferred composite location
1851 for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
1852 FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
1853 CompositeLocation inferredCompLoc =
1854 updateCompositeLocation(flowNode.getCompositeLocation());
1855 // NTuple<Descriptor> descTuple = flowNode.getDescTuple();
1857 // CompositeLocation assignedCompLoc = flowNode.getCompositeLocation();
1858 // CompositeLocation inferredCompLoc;
1859 // if (assignedCompLoc != null) {
1860 // inferredCompLoc = translateCompositeLocation(assignedCompLoc);
1862 // Descriptor locDesc = descTuple.get(0);
1863 // Location loc = new Location(md, locDesc.getSymbol());
1864 // loc.setLocDescriptor(locDesc);
1865 // inferredCompLoc = new CompositeLocation(loc);
1867 System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc + " original="
1868 + flowNode.getCompositeLocation());
1870 Descriptor localVarDesc = flowNode.getDescTuple().get(0);
1871 methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc);
1872 methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
1879 private boolean hasOrderingRelation(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
1881 int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
1883 for (int idx = 0; idx < size; idx++) {
1884 Location loc1 = locTuple1.get(idx);
1885 Location loc2 = locTuple2.get(idx);
1887 Descriptor desc1 = loc1.getDescriptor();
1888 Descriptor desc2 = loc2.getDescriptor();
1890 if (!desc1.equals(desc2)) {
1891 throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
1894 Descriptor locDesc1 = loc1.getLocDescriptor();
1895 Descriptor locDesc2 = loc2.getLocDescriptor();
1897 HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
1899 HNode node1 = hierarchyGraph.getHNode(locDesc1);
1900 HNode node2 = hierarchyGraph.getHNode(locDesc2);
1902 System.out.println("---node1=" + node1 + " node2=" + node2);
1903 System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
1904 + hierarchyGraph.getIncomingNodeSet(node2));
1906 if (locDesc1.equals(locDesc2)) {
1908 } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1)
1909 && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) {
1921 private boolean isHigherThan(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
1923 int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
1925 for (int idx = 0; idx < size; idx++) {
1926 Location loc1 = locTuple1.get(idx);
1927 Location loc2 = locTuple2.get(idx);
1929 Descriptor desc1 = loc1.getDescriptor();
1930 Descriptor desc2 = loc2.getDescriptor();
1932 if (!desc1.equals(desc2)) {
1933 throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
1936 Descriptor locDesc1 = loc1.getLocDescriptor();
1937 Descriptor locDesc2 = loc2.getLocDescriptor();
1939 HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
1941 HNode node1 = hierarchyGraph.getHNode(locDesc1);
1942 HNode node2 = hierarchyGraph.getHNode(locDesc2);
1944 System.out.println("---node1=" + node1 + " node2=" + node2);
1945 System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
1946 + hierarchyGraph.getIncomingNodeSet(node2));
1948 if (locDesc1.equals(locDesc2)) {
1950 } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) {
1961 private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) {
1962 CompositeLocation newCompLoc = new CompositeLocation();
1964 // System.out.println("compLoc=" + compLoc);
1965 for (int i = 0; i < compLoc.getSize(); i++) {
1966 Location loc = compLoc.get(i);
1967 Descriptor enclosingDescriptor = loc.getDescriptor();
1968 Descriptor locDescriptor = loc.getLocDescriptor();
1970 HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor);
1971 // System.out.println("-hnode=" + hnode + " from=" + locDescriptor +
1972 // " enclosingDescriptor="
1973 // + enclosingDescriptor);
1974 // System.out.println("-getLocationSummary(enclosingDescriptor)="
1975 // + getLocationSummary(enclosingDescriptor));
1976 String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName());
1977 // System.out.println("-locName=" + locName);
1978 Location newLoc = new Location(enclosingDescriptor, locName);
1979 newLoc.setLocDescriptor(locDescriptor);
1980 newCompLoc.addLocation(newLoc);
1986 private void debug_writeLattices() {
1988 Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
1989 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1990 Descriptor key = (Descriptor) iterator.next();
1991 SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
1992 // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
1993 HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
1994 if (key instanceof ClassDescriptor) {
1995 writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
1997 } else if (key instanceof MethodDescriptor) {
1998 MethodDescriptor md = (MethodDescriptor) key;
1999 writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
2003 LocationSummary ls = getLocationSummary(key);
2004 System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
2007 Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
2008 for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
2009 ClassDescriptor cd = (ClassDescriptor) iterator.next();
2010 writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
2011 cd2lattice.get(cd), "");
2014 Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
2015 for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
2016 MethodDescriptor md = (MethodDescriptor) iterator.next();
2017 writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
2018 md2lattice.get(md), "");
2023 private void buildLattice() {
2025 BuildLattice buildLattice = new BuildLattice(this);
2027 Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
2028 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2029 Descriptor desc = (Descriptor) iterator.next();
2031 SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
2033 addMapDescToSimpleLattice(desc, simpleLattice);
2035 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2036 System.out.println("\n## insertIntermediateNodesToStraightLine:"
2037 + simpleHierarchyGraph.getName());
2038 SSJavaLattice<String> lattice =
2039 buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
2040 lattice.removeRedundantEdges();
2042 if (desc instanceof ClassDescriptor) {
2044 cd2lattice.put((ClassDescriptor) desc, lattice);
2045 // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
2046 } else if (desc instanceof MethodDescriptor) {
2048 md2lattice.put((MethodDescriptor) desc, lattice);
2049 MethodDescriptor md = (MethodDescriptor) desc;
2050 ClassDescriptor cd = md.getClassDesc();
2051 // ssjava.writeLatticeDotFile(cd, md, lattice);
2054 // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
2055 // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
2056 // HierarchyGraph skeletonGraphWithCombinationNode =
2057 // skeletonGraph.clone();
2058 // skeletonGraphWithCombinationNode.setName(desc + "_SC");
2060 // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2061 // System.out.println("Identifying Combination Nodes:");
2062 // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
2063 // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
2064 // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc,
2065 // skeletonGraphWithCombinationNode);
2070 public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
2071 mapDescriptorToSimpleLattice.put(desc, lattice);
2074 public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
2075 return mapDescriptorToSimpleLattice.get(desc);
2078 private void simplifyHierarchyGraph() {
2079 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2080 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2081 Descriptor desc = (Descriptor) iterator.next();
2082 // System.out.println("SSJAVA: remove redundant edges: " + desc);
2083 HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
2084 simpleHierarchyGraph.setName(desc + "_SIMPLE");
2085 simpleHierarchyGraph.removeRedundantEdges();
2086 mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
2090 private void insertCombinationNodes() {
2091 Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
2092 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2093 Descriptor desc = (Descriptor) iterator.next();
2094 System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
2095 HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
2096 HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
2097 skeletonGraphWithCombinationNode.setName(desc + "_SC");
2099 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2100 System.out.println("Identifying Combination Nodes:");
2101 skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
2102 skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
2103 mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
2107 private void constructSkeletonHierarchyGraph() {
2108 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2109 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2110 Descriptor desc = (Descriptor) iterator.next();
2111 System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc);
2112 HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
2113 HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
2114 skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
2115 skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
2116 skeletonGraph.simplifyHierarchyGraph();
2117 // skeletonGraph.combineRedundantNodes(false);
2118 // skeletonGraph.removeRedundantEdges();
2119 mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
2123 private void debug_writeHierarchyDotFiles() {
2125 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2126 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2127 Descriptor desc = (Descriptor) iterator.next();
2128 getHierarchyGraph(desc).writeGraph();
2133 private void debug_writeSimpleHierarchyDotFiles() {
2135 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2136 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2137 Descriptor desc = (Descriptor) iterator.next();
2138 getHierarchyGraph(desc).writeGraph();
2139 getSimpleHierarchyGraph(desc).writeGraph();
2144 private void debug_writeSkeletonHierarchyDotFiles() {
2146 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2147 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2148 Descriptor desc = (Descriptor) iterator.next();
2149 getSkeletonHierarchyGraph(desc).writeGraph();
2154 private void debug_writeSkeletonCombinationHierarchyDotFiles() {
2156 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2157 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2158 Descriptor desc = (Descriptor) iterator.next();
2159 getSkeletonCombinationHierarchyGraph(desc).writeGraph();
2164 public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
2165 return mapDescriptorToSimpleHierarchyGraph.get(d);
2168 private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
2169 if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
2170 mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2172 return mapDescriptorToSkeletonHierarchyGraph.get(d);
2175 public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
2176 if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
2177 mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2179 return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
2182 private void constructHierarchyGraph() {
2184 // do fixed-point analysis
2186 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
2188 // Collections.sort(descriptorListToAnalyze, new
2189 // Comparator<MethodDescriptor>() {
2190 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
2191 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
2195 // current descriptors to visit in fixed-point interprocedural analysis,
2196 // prioritized by dependency in the call graph
2197 methodDescriptorsToVisitStack.clear();
2199 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2200 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2202 while (!descriptorListToAnalyze.isEmpty()) {
2203 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2204 methodDescriptorsToVisitStack.add(md);
2207 // analyze scheduled methods until there are no more to visit
2208 while (!methodDescriptorsToVisitStack.isEmpty()) {
2209 // start to analyze leaf node
2210 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
2212 HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
2213 // MethodSummary methodSummary = new MethodSummary(md);
2215 // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
2216 // curMethodInfo = methodInfo;
2218 System.out.println();
2219 System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
2221 constructHierarchyGraph(md, hierarchyGraph);
2223 HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
2224 // MethodSummary prevMethodSummary = getMethodSummary(md);
2226 if (!hierarchyGraph.equals(prevHierarchyGraph)) {
2228 mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
2229 // mapDescToLocationSummary.put(md, methodSummary);
2231 // results for callee changed, so enqueue dependents caller for
2233 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
2234 while (depsItr.hasNext()) {
2235 MethodDescriptor methodNext = depsItr.next();
2236 if (!methodDescriptorsToVisitStack.contains(methodNext)
2237 && methodDescriptorToVistSet.contains(methodNext)) {
2238 methodDescriptorsToVisitStack.add(methodNext);
2247 while (!toAnalyzeIsEmpty()) {
2248 ClassDescriptor cd = toAnalyzeNext();
2249 HierarchyGraph graph = getHierarchyGraph(cd);
2250 for (Iterator iter = cd.getFields(); iter.hasNext();) {
2251 FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
2252 if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
2253 graph.getHNode(fieldDesc);
2258 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2259 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2260 Descriptor key = (Descriptor) iterator.next();
2261 HierarchyGraph graph = getHierarchyGraph(key);
2263 Set<HNode> nodeToBeConnected = new HashSet<HNode>();
2264 for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
2265 HNode node = (HNode) iterator2.next();
2266 if (!node.isSkeleton() && !node.isCombinationNode()) {
2267 if (graph.getIncomingNodeSet(node).size() == 0) {
2268 nodeToBeConnected.add(node);
2273 for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
2274 HNode node = (HNode) iterator2.next();
2275 System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
2276 graph.addEdge(graph.getHNode(TOPDESC), node);
2283 private HierarchyGraph getHierarchyGraph(Descriptor d) {
2284 if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
2285 mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
2287 return mapDescriptorToHierarchyGraph.get(d);
2290 private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
2292 // visit each node of method flow graph
2293 FlowGraph fg = getFlowGraph(md);
2294 // Set<FlowNode> nodeSet = fg.getNodeSet();
2296 Set<FlowEdge> edgeSet = fg.getEdgeSet();
2298 Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
2299 for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
2300 Descriptor desc = (Descriptor) iterator.next();
2301 methodGraph.getHNode(desc).setSkeleton(true);
2304 // for the method lattice, we need to look at the first element of
2305 // NTuple<Descriptor>
2306 boolean hasGlobalAccess = false;
2307 // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2308 // FlowNode originalSrcNode = (FlowNode) iterator.next();
2309 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
2310 FlowEdge edge = (FlowEdge) iterator.next();
2312 FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple());
2313 Set<FlowNode> sourceNodeSet = new HashSet<FlowNode>();
2314 if (originalSrcNode instanceof FlowReturnNode) {
2315 FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
2316 Set<NTuple<Descriptor>> tupleSet = rnode.getTupleSet();
2317 for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) {
2318 NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator2.next();
2319 sourceNodeSet.add(fg.getFlowNode(nTuple));
2320 System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
2323 sourceNodeSet.add(originalSrcNode);
2326 System.out.println("---sourceNodeSet=" + sourceNodeSet + " from originalSrcNode="
2329 for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) {
2330 FlowNode srcNode = (FlowNode) iterator3.next();
2332 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
2333 Descriptor srcLocalDesc = srcNodeTuple.get(0);
2335 if (srcLocalDesc instanceof InterDescriptor
2336 && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) {
2338 if (srcNode.getCompositeLocation() == null) {
2343 // if the srcNode is started with the global descriptor
2344 // need to set as a skeleton node
2345 if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) {
2346 hasGlobalAccess = true;
2349 // Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(originalSrcNode);
2350 // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
2351 // FlowEdge outEdge = (FlowEdge) iterator2.next();
2352 // FlowNode originalDstNode = outEdge.getDst();
2353 FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple());
2355 Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
2356 if (originalDstNode instanceof FlowReturnNode) {
2357 FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
2358 System.out.println("\n-returnNode=" + rnode);
2359 Set<NTuple<Descriptor>> tupleSet = rnode.getTupleSet();
2360 for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) {
2361 NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator4.next();
2362 dstNodeSet.add(fg.getFlowNode(nTuple));
2365 dstNodeSet.add(originalDstNode);
2367 System.out.println("---dstNodeSet=" + dstNodeSet);
2368 for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) {
2369 FlowNode dstNode = (FlowNode) iterator4.next();
2371 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
2372 Descriptor dstLocalDesc = dstNodeTuple.get(0);
2374 if (dstLocalDesc instanceof InterDescriptor
2375 && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) {
2376 if (dstNode.getCompositeLocation() == null) {
2377 System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode);
2382 // if (outEdge.getInitTuple().equals(srcNodeTuple)
2383 // && outEdge.getEndTuple().equals(dstNodeTuple)) {
2385 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
2386 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
2388 System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple);
2390 if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
2391 && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
2393 // value flows between fields
2394 Descriptor desc = srcCurTuple.get(0);
2395 ClassDescriptor classDesc;
2397 if (desc.equals(GLOBALDESC)) {
2398 classDesc = md.getClassDesc();
2400 VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
2401 classDesc = varDesc.getType().getClassDesc();
2403 extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
2405 } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1)
2406 || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals(
2407 dstCurTuple.get(0)))) {
2409 // value flow between a primitive local var - a primitive local var or local var -
2412 Descriptor srcDesc = srcCurTuple.get(0);
2413 Descriptor dstDesc = dstCurTuple.get(0);
2415 methodGraph.addEdge(srcDesc, dstDesc);
2417 if (fg.isParamDesc(srcDesc)) {
2418 methodGraph.setParamHNode(srcDesc);
2420 if (fg.isParamDesc(dstDesc)) {
2421 methodGraph.setParamHNode(dstDesc);
2435 // If the method accesses static fields
2436 // set hasGloabalAccess true in the method summary.
2437 if (hasGlobalAccess) {
2438 getMethodSummary(md).setHasGlobalAccess();
2440 methodGraph.getHNode(GLOBALDESC).setSkeleton(true);
2442 if (ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2443 // if the current method contains the event loop
2444 // we need to set all nodes of the hierarchy graph as a skeleton node
2445 Set<HNode> hnodeSet = methodGraph.getNodeSet();
2446 for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) {
2447 HNode hnode = (HNode) iterator.next();
2448 hnode.setSkeleton(true);
2454 private MethodSummary getMethodSummary(MethodDescriptor md) {
2455 if (!mapDescToLocationSummary.containsKey(md)) {
2456 mapDescToLocationSummary.put(md, new MethodSummary(md));
2458 return (MethodSummary) mapDescToLocationSummary.get(md);
2461 private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
2463 String classSymbol = cd.getSymbol();
2464 int idx = classSymbol.lastIndexOf("$");
2466 classSymbol = classSymbol.substring(idx + 1);
2469 String pattern = "class " + classSymbol + " ";
2470 if (strLine.indexOf(pattern) != -1) {
2471 mapDescToDefinitionLine.put(cd, lineNum);
2475 private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
2477 for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
2478 MethodDescriptor md = (MethodDescriptor) iterator.next();
2479 String pattern = md.getMethodDeclaration();
2480 if (strLine.indexOf(pattern) != -1) {
2481 mapDescToDefinitionLine.put(md, lineNum);
2482 methodSet.remove(md);
2489 private void readOriginalSourceFiles() {
2491 SymbolTable classtable = state.getClassSymbolTable();
2493 Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
2494 classDescSet.addAll(classtable.getValueSet());
2497 // inefficient implement. it may re-visit the same file if the file
2498 // contains more than one class definitions.
2499 for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
2500 ClassDescriptor cd = (ClassDescriptor) iterator.next();
2502 Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
2503 methodSet.addAll(cd.getMethodTable().getValueSet());
2505 String sourceFileName = cd.getSourceFileName();
2506 Vector<String> lineVec = new Vector<String>();
2508 mapFileNameToLineVector.put(sourceFileName, lineVec);
2510 BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
2513 lineVec.add(""); // the index is started from 1.
2514 while ((strLine = in.readLine()) != null) {
2515 lineVec.add(lineNum, strLine);
2516 addMapClassDefinitionToLineNum(cd, strLine, lineNum);
2517 addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
2523 } catch (IOException e) {
2524 e.printStackTrace();
2529 private String generateLatticeDefinition(Descriptor desc) {
2531 Set<String> sharedLocSet = new HashSet<String>();
2533 SSJavaLattice<String> lattice = getLattice(desc);
2534 String rtr = "@LATTICE(\"";
2536 Map<String, Set<String>> map = lattice.getTable();
2537 Set<String> keySet = map.keySet();
2538 boolean first = true;
2539 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2540 String key = (String) iterator.next();
2541 if (!key.equals(lattice.getTopItem())) {
2542 Set<String> connectedSet = map.get(key);
2544 if (connectedSet.size() == 1) {
2545 if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
2553 if (lattice.isSharedLoc(key)) {
2554 rtr += "," + key + "*";
2559 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
2560 String loc = (String) iterator2.next();
2561 if (!loc.equals(lattice.getBottomItem())) {
2568 rtr += loc + "<" + key;
2569 if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
2570 rtr += "," + key + "*";
2571 sharedLocSet.add(key);
2573 if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
2574 rtr += "," + loc + "*";
2575 sharedLocSet.add(loc);
2585 if (desc instanceof MethodDescriptor) {
2586 System.out.println("#EXTRA LOC DECLARATION GEN=" + desc);
2588 MethodDescriptor md = (MethodDescriptor) desc;
2589 MethodSummary methodSummary = getMethodSummary(md);
2591 if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) {
2592 TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
2593 if (returnType != null && (!returnType.isVoid())) {
2595 "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")";
2597 CompositeLocation pcLoc = methodSummary.getPCLoc();
2598 if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
2599 rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
2603 if (!md.isStatic()) {
2604 rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")";
2606 rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")";
2613 private void generateAnnoatedCode() {
2615 readOriginalSourceFiles();
2618 while (!toAnalyzeIsEmpty()) {
2619 ClassDescriptor cd = toAnalyzeNext();
2621 setupToAnalazeMethod(cd);
2623 String sourceFileName = cd.getSourceFileName();
2625 if (cd.isInterface()) {
2629 int classDefLine = mapDescToDefinitionLine.get(cd);
2630 Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
2632 LocationSummary fieldLocSummary = getLocationSummary(cd);
2634 String fieldLatticeDefStr = generateLatticeDefinition(cd);
2635 String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
2636 sourceVec.set(classDefLine, annoatedSrc);
2638 // generate annotations for field declarations
2639 // Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
2640 Map<String, String> mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName();
2642 for (Iterator iter = cd.getFields(); iter.hasNext();) {
2643 FieldDescriptor fd = (FieldDescriptor) iter.next();
2645 String locAnnotationStr;
2646 // CompositeLocation inferLoc = inferLocMap.get(fd);
2647 String locName = mapFieldNameToLocName.get(fd.getSymbol());
2649 if (locName != null) {
2650 // infer loc is null if the corresponding field is static and final
2651 // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2652 locAnnotationStr = "@LOC(\"" + locName + "\")";
2653 int fdLineNum = fd.getLineNum();
2654 String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
2655 String fieldDeclaration = fd.toString();
2656 fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
2657 String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
2658 sourceVec.set(fdLineNum, annoatedStr);
2663 while (!toAnalyzeMethodIsEmpty()) {
2664 MethodDescriptor md = toAnalyzeMethodNext();
2666 if (!ssjava.needTobeAnnotated(md)) {
2670 SSJavaLattice<String> methodLattice = md2lattice.get(md);
2671 if (methodLattice != null) {
2673 int methodDefLine = md.getLineNum();
2675 // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
2676 // Map<Descriptor, CompositeLocation> methodInferLocMap =
2677 // methodLocInfo.getMapDescToInferLocation();
2679 MethodSummary methodSummary = getMethodSummary(md);
2681 Map<Descriptor, CompositeLocation> mapVarDescToInferLoc =
2682 methodSummary.getMapVarDescToInferCompositeLocation();
2683 System.out.println("-----md=" + md);
2684 System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc);
2686 Set<Descriptor> localVarDescSet = mapVarDescToInferLoc.keySet();
2688 Set<String> localLocElementSet = methodLattice.getElementSet();
2690 for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
2691 Descriptor localVarDesc = (Descriptor) iterator.next();
2692 System.out.println("-------localVarDesc=" + localVarDesc);
2693 CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc);
2695 String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
2696 if (!localLocElementSet.contains(localLocIdentifier)) {
2697 methodLattice.put(localLocIdentifier);
2700 String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2702 if (!isParameter(md, localVarDesc)) {
2703 if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
2704 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
2705 String orgSourceLine = sourceVec.get(varLineNum);
2707 orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
2708 System.out.println("idx=" + idx
2709 + " generateVarDeclaration((VarDescriptor) localVarDesc)="
2710 + generateVarDeclaration((VarDescriptor) localVarDesc));
2712 String annoatedStr =
2713 orgSourceLine.substring(0, idx) + locAnnotationStr + " "
2714 + orgSourceLine.substring(idx);
2715 sourceVec.set(varLineNum, annoatedStr);
2718 String methodDefStr = sourceVec.get(methodDefLine);
2721 getParamLocation(methodDefStr,
2722 generateVarDeclaration((VarDescriptor) localVarDesc));
2723 System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc
2727 String annoatedStr =
2728 methodDefStr.substring(0, idx) + locAnnotationStr + " "
2729 + methodDefStr.substring(idx);
2730 sourceVec.set(methodDefLine, annoatedStr);
2735 // check if the lattice has to have the location type for the this
2738 // boolean needToAddthisRef = hasThisReference(md);
2739 // if (localLocElementSet.contains("this")) {
2740 // methodLattice.put("this");
2743 String methodLatticeDefStr = generateLatticeDefinition(md);
2744 String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
2745 sourceVec.set(methodDefLine, annoatedStr);
2755 private boolean hasThisReference(MethodDescriptor md) {
2757 FlowGraph fg = getFlowGraph(md);
2758 Set<FlowNode> nodeSet = fg.getNodeSet();
2759 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2760 FlowNode flowNode = (FlowNode) iterator.next();
2761 if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
2769 private int getParamLocation(String methodStr, String paramStr) {
2771 String pattern = paramStr + ",";
2773 int idx = methodStr.indexOf(pattern);
2777 pattern = paramStr + ")";
2778 return methodStr.indexOf(pattern);
2783 private String generateVarDeclaration(VarDescriptor varDesc) {
2785 TypeDescriptor td = varDesc.getType();
2786 String rtr = td.toString();
2788 for (int i = 0; i < td.getArrayCount(); i++) {
2792 rtr += " " + varDesc.getName();
2797 private String generateLocationAnnoatation(CompositeLocation loc) {
2800 Location methodLoc = loc.get(0);
2801 rtr += methodLoc.getLocIdentifier();
2803 for (int i = 1; i < loc.getSize(); i++) {
2804 Location element = loc.get(i);
2805 rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
2811 private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
2812 return getFlowGraph(md).isParamDesc(localVarDesc);
2815 private String extractFileName(String fileName) {
2816 int idx = fileName.lastIndexOf("/");
2820 return fileName.substring(idx + 1);
2825 private void codeGen() {
2827 Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
2828 for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
2829 String orgFileName = (String) iterator.next();
2830 String outputFileName = extractFileName(orgFileName);
2832 Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
2836 FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
2837 BufferedWriter out = new BufferedWriter(fileWriter);
2839 for (int i = 0; i < sourceVec.size(); i++) {
2840 out.write(sourceVec.get(i));
2844 } catch (IOException e) {
2845 e.printStackTrace();
2852 private void checkLattices() {
2854 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
2856 // current descriptors to visit in fixed-point interprocedural analysis,
2858 // dependency in the call graph
2859 methodDescriptorsToVisitStack.clear();
2861 // descriptorListToAnalyze.removeFirst();
2863 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2864 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2866 while (!descriptorListToAnalyze.isEmpty()) {
2867 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2868 checkLatticesOfVirtualMethods(md);
2873 private void debug_writeLatticeDotFile() {
2874 // generate lattice dot file
2878 while (!toAnalyzeIsEmpty()) {
2879 ClassDescriptor cd = toAnalyzeNext();
2881 setupToAnalazeMethod(cd);
2883 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
2884 if (classLattice != null) {
2885 ssjava.writeLatticeDotFile(cd, null, classLattice);
2886 debug_printDescriptorToLocNameMapping(cd);
2889 while (!toAnalyzeMethodIsEmpty()) {
2890 MethodDescriptor md = toAnalyzeMethodNext();
2891 SSJavaLattice<String> methodLattice = md2lattice.get(md);
2892 if (methodLattice != null) {
2893 ssjava.writeLatticeDotFile(cd, md, methodLattice);
2894 debug_printDescriptorToLocNameMapping(md);
2901 private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
2903 LocationInfo info = getLocationInfo(desc);
2904 System.out.println("## " + desc + " ##");
2905 System.out.println(info.getMapDescToInferLocation());
2906 LocationInfo locInfo = getLocationInfo(desc);
2907 System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
2908 System.out.println("###################");
2912 private void calculateExtraLocations() {
2914 LinkedList<MethodDescriptor> methodDescList = ssjava.getSortedDescriptors();
2915 for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) {
2916 MethodDescriptor md = (MethodDescriptor) iterator.next();
2917 if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2918 calculateExtraLocations(md);
2924 private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
2926 if (!md.isStatic()) {
2927 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2928 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
2930 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
2931 MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
2932 if (!md.equals(mdCallee)) {
2933 checkConsistency(md, mdCallee);
2941 private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
2943 // check that two lattice have the same relations between parameters(+PC
2944 // LOC, GLOBAL_LOC RETURN LOC)
2946 List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
2947 List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
2949 MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
2950 MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
2952 Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
2953 Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
2955 int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
2957 // add location types of paramters
2958 for (int idx = 0; idx < numParam; idx++) {
2959 list1.add(paramMap1.get(Integer.valueOf(idx)));
2960 list2.add(paramMap2.get(Integer.valueOf(idx)));
2963 // add program counter location
2964 list1.add(locInfo1.getPCLoc());
2965 list2.add(locInfo2.getPCLoc());
2967 if (!md1.getReturnType().isVoid()) {
2968 // add return value location
2969 CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
2970 CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
2975 // add global location type
2976 if (md1.isStatic()) {
2977 CompositeLocation globalLoc1 =
2978 new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
2979 CompositeLocation globalLoc2 =
2980 new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
2981 list1.add(globalLoc1);
2982 list2.add(globalLoc2);
2985 for (int i = 0; i < list1.size(); i++) {
2986 CompositeLocation locA1 = list1.get(i);
2987 CompositeLocation locA2 = list2.get(i);
2988 for (int k = 0; k < list1.size(); k++) {
2990 CompositeLocation locB1 = list1.get(k);
2991 CompositeLocation locB2 = list2.get(k);
2992 boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
2994 boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
2997 throw new Error("The method " + md1 + " is not consistent with the method " + md2
2998 + ".:: They have a different ordering relation between locations (" + locA1 + ","
2999 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
3007 private String getSymbol(int idx, FlowNode node) {
3008 Descriptor desc = node.getDescTuple().get(idx);
3009 return desc.getSymbol();
3012 private Descriptor getDescriptor(int idx, FlowNode node) {
3013 Descriptor desc = node.getDescTuple().get(idx);
3017 private void calculatePCLOC(MethodDescriptor md) {
3019 System.out.println("#CalculatePCLOC");
3020 MethodSummary methodSummary = getMethodSummary(md);
3021 FlowGraph fg = getFlowGraph(md);
3022 Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3024 // calculate the initial program counter location
3025 // PC location is higher than location types of parameters which has incoming flows.
3027 Set<NTuple<Location>> paramLocTupleHavingInFlowSet = new HashSet<NTuple<Location>>();
3028 Set<Descriptor> paramDescNOTHavingInFlowSet = new HashSet<Descriptor>();
3029 // Set<FlowNode> paramNodeNOThavingInFlowSet = new HashSet<FlowNode>();
3031 int numParams = fg.getNumParameters();
3032 for (int i = 0; i < numParams; i++) {
3033 FlowNode paramFlowNode = fg.getParamFlowNode(i);
3034 Descriptor prefix = paramFlowNode.getDescTuple().get(0);
3035 NTuple<Descriptor> paramDescTuple = paramFlowNode.getCurrentDescTuple();
3036 NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
3038 Set<FlowNode> inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix);
3039 if (inNodeToParamSet.size() > 0) {
3040 // parameter has in-value flows
3042 for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) {
3043 FlowNode inNode = (FlowNode) iterator.next();
3044 Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(inNode);
3045 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3046 FlowEdge flowEdge = (FlowEdge) iterator2.next();
3047 if (flowEdge.getEndTuple().startsWith(prefix)) {
3048 NTuple<Location> paramLocTupleWithIncomingFlow =
3049 translateToLocTuple(md, flowEdge.getEndTuple());
3050 paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow);
3055 // paramLocTupleHavingInFlowSet.add(paramLocTuple);
3057 // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple));
3058 paramDescNOTHavingInFlowSet.add(prefix);
3062 System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet);
3064 if (paramLocTupleHavingInFlowSet.size() > 0
3065 && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) {
3067 // Here, generates a location in the method lattice that is higher than the
3068 // paramLocTupleHavingInFlowSet
3069 NTuple<Location> pcLocTuple =
3070 generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC);
3072 NTuple<Descriptor> pcDescTuple = translateToDescTuple(pcLocTuple);
3074 // System.out.println("pcLoc=" + pcLocTuple);
3076 CompositeLocation curPCLoc = methodSummary.getPCLoc();
3077 if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) {
3078 methodSummary.setPCLoc(new CompositeLocation(pcLocTuple));
3080 // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of
3081 // parameters that do not have incoming flows
3082 for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) {
3083 FlowNode node = (FlowNode) iterator.next();
3085 if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) {
3086 fg.addValueFlowEdge(pcDescTuple, node.getDescTuple());
3089 fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true);
3095 private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg,
3096 Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
3098 int numParam = fg.getNumParameters();
3099 int size = paramLocTupleHavingInFlowSet.size();
3101 if (!md.isStatic()) {
3103 // if the method is not static && there is a parameter composite location &&
3104 // it is started with 'this',
3105 // paramLocTupleHavingInFlowSet need to have 'this' parameter.
3107 FlowNode thisParamNode = fg.getParamFlowNode(0);
3108 NTuple<Location> thisParamLocTuple =
3109 translateToLocTuple(md, thisParamNode.getCurrentDescTuple());
3111 if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) {
3113 for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
3114 NTuple<Location> paramTuple = (NTuple<Location>) iterator.next();
3115 if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) {
3116 // paramLocTupleHavingInFlowSet.add(thisParamLocTuple);
3125 if (size == numParam) {
3133 private void calculateRETURNLOC(MethodDescriptor md) {
3135 System.out.println("#calculateRETURNLOC= " + md);
3137 // calculate a return location:
3138 // the return location type is lower than all parameters and the location of return values
3139 MethodSummary methodSummary = getMethodSummary(md);
3140 if (methodSummary.getRETURNLoc() != null) {
3143 FlowGraph fg = getFlowGraph(md);
3144 Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3145 Set<Integer> paramIdxSet = mapParamToLoc.keySet();
3147 if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
3148 // first, generate the set of return value location types that starts
3149 // with 'this' reference
3151 Set<FlowNode> paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md);
3152 // System.out.println("paramFlowNodeFlowingToReturnValueSet="
3153 // + paramFlowNodeFlowingToReturnValueSet);
3155 Set<NTuple<Location>> tupleToBeHigherThanReturnLocSet = new HashSet<NTuple<Location>>();
3156 for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) {
3157 FlowNode fn = (FlowNode) iterator.next();
3158 NTuple<Descriptor> paramDescTuple = fn.getCurrentDescTuple();
3159 tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple));
3162 Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
3163 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
3164 FlowNode returnNode = (FlowNode) iterator.next();
3165 NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
3166 tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple));
3168 System.out.println("-flow graph's returnNodeSet=" + returnNodeSet);
3169 System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet);
3171 // Here, generates a return location in the method lattice that is lower than the
3172 // locFlowingToReturnValueSet
3173 NTuple<Location> returnLocTuple =
3174 generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC);
3176 // System.out.println("returnLocTuple=" + returnLocTuple);
3177 NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnLocTuple);
3178 CompositeLocation curReturnLoc = methodSummary.getRETURNLoc();
3179 if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) {
3180 methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple));
3182 for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) {
3183 NTuple<Location> higherTuple = (NTuple<Location>) iterator.next();
3184 fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple);
3186 fg.getFlowNode(returnDescTuple).setSkeleton(true);
3194 private void calculateExtraLocations(MethodDescriptor md) {
3195 // calcualte pcloc, returnloc,...
3197 System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md);
3200 calculateRETURNLOC(md);
3204 private NTuple<Location> generateLocTupleRelativeTo(MethodDescriptor md,
3205 Set<NTuple<Location>> paramLocTupleHavingInFlowSet, String locNamePrefix) {
3207 // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet);
3209 NTuple<Location> higherLocTuple = new NTuple<Location>();
3211 VarDescriptor thisVarDesc = md.getThis();
3212 // check if all paramter loc tuple is started with 'this' reference
3213 boolean hasParamNotStartedWithThisRef = false;
3217 Set<NTuple<Location>> paramLocTupleStartedWithThis = new HashSet<NTuple<Location>>();
3219 next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
3220 NTuple<Location> paramLocTuple = (NTuple<Location>) iterator.next();
3221 Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor();
3222 if (!paramLocalDesc.equals(thisVarDesc)) {
3224 Set<FlowNode> inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc);
3225 for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
3226 FlowNode flowNode = (FlowNode) iterator2.next();
3227 if (flowNode.getDescTuple().startsWith(thisVarDesc)) {
3228 // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS");
3232 hasParamNotStartedWithThisRef = true;
3234 } else if (paramLocTuple.size() > 1) {
3235 paramLocTupleStartedWithThis.add(paramLocTuple);
3236 if (minSize == 0 || minSize > paramLocTuple.size()) {
3237 minSize = paramLocTuple.size();
3242 // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis);
3243 Descriptor enclosingDesc = md;
3244 if (hasParamNotStartedWithThisRef) {
3245 // in this case, PCLOC will be the local location
3247 // all parameter is started with 'this', so PCLOC will be set relative to the composite
3248 // location started with 'this'.
3249 for (int idx = 0; idx < minSize - 1; idx++) {
3250 Set<Descriptor> locDescSet = new HashSet<Descriptor>();
3251 Location curLoc = null;
3252 NTuple<Location> paramLocTuple = null;
3253 for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) {
3254 paramLocTuple = (NTuple<Location>) iterator.next();
3255 // System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx);
3256 curLoc = paramLocTuple.get(idx);
3257 Descriptor locDesc = curLoc.getLocDescriptor();
3258 locDescSet.add(locDesc);
3260 // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx);
3261 if (locDescSet.size() != 1) {
3264 Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor());
3265 System.out.println("newLocElement" + newLocElement);
3266 higherLocTuple.add(newLocElement);
3267 enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor());
3272 String locIdentifier = locNamePrefix + (locSeed++);
3273 NameDescriptor locDesc = new NameDescriptor(locIdentifier);
3274 Location newLoc = new Location(enclosingDesc, locDesc);
3275 higherLocTuple.add(newLoc);
3276 System.out.println("---new loc tuple=" + higherLocTuple);
3278 return higherLocTuple;
3282 public ClassDescriptor getClassTypeDescriptor(Descriptor in) {
3284 if (in instanceof VarDescriptor) {
3285 return ((VarDescriptor) in).getType().getClassDesc();
3286 } else if (in instanceof FieldDescriptor) {
3287 return ((FieldDescriptor) in).getType().getClassDesc();
3289 // else if (in instanceof LocationDescriptor) {
3290 // // here is the case that the descriptor 'in' is the last element of the assigned composite
3292 // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc();
3300 private Set<NTuple<Location>> calculateHighestLocTupleSet(
3301 Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
3303 Set<NTuple<Location>> highestSet = new HashSet<NTuple<Location>>();
3305 Iterator<NTuple<Location>> iterator = paramLocTupleHavingInFlowSet.iterator();
3306 NTuple<Location> highest = iterator.next();
3308 for (; iterator.hasNext();) {
3309 NTuple<Location> curLocTuple = (NTuple<Location>) iterator.next();
3310 if (isHigherThan(curLocTuple, highest)) {
3311 // System.out.println(curLocTuple + " is greater than " + highest);
3312 highest = curLocTuple;
3316 highestSet.add(highest);
3318 MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor();
3319 VarDescriptor thisVarDesc = md.getThis();
3321 // System.out.println("highest=" + highest);
3323 for (Iterator<NTuple<Location>> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) {
3324 NTuple<Location> curLocTuple = iter.next();
3326 if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) {
3328 // System.out.println("add it to the highest set=" + curLocTuple);
3329 highestSet.add(curLocTuple);
3338 private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
3339 Set<String> higherLocSet = new HashSet<String>();
3341 Set<String> locSet = lattice.getTable().keySet();
3342 for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
3343 String element = (String) iterator.next();
3344 if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
3345 higherLocSet.add(element);
3348 return higherLocSet;
3351 private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
3352 Set<CompositeLocation> set) {
3354 CompositeLocation lowest = set.iterator().next();
3356 if (set.size() == 1) {
3360 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3361 CompositeLocation loc = (CompositeLocation) iterator.next();
3363 if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
3364 // if there is a case where composite locations are incomparable, just
3369 if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
3376 private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3377 CompositeLocation comp2) {
3379 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3381 for (int idx = 0; idx < size; idx++) {
3382 Location loc1 = comp1.get(idx);
3383 Location loc2 = comp2.get(idx);
3385 Descriptor desc1 = loc1.getDescriptor();
3386 Descriptor desc2 = loc2.getDescriptor();
3388 if (!desc1.equals(desc2)) {
3389 throw new Error("Fail to compare " + comp1 + " and " + comp2);
3392 String symbol1 = loc1.getLocIdentifier();
3393 String symbol2 = loc2.getLocIdentifier();
3395 SSJavaLattice<String> lattice;
3397 lattice = methodLattice;
3399 lattice = getLattice(desc1);
3402 if (symbol1.equals(symbol2)) {
3404 } else if (!lattice.isComparable(symbol1, symbol2)) {
3413 private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3414 CompositeLocation comp2) {
3416 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3418 for (int idx = 0; idx < size; idx++) {
3419 Location loc1 = comp1.get(idx);
3420 Location loc2 = comp2.get(idx);
3422 Descriptor desc1 = loc1.getDescriptor();
3423 Descriptor desc2 = loc2.getDescriptor();
3425 if (!desc1.equals(desc2)) {
3426 throw new Error("Fail to compare " + comp1 + " and " + comp2);
3429 String symbol1 = loc1.getLocIdentifier();
3430 String symbol2 = loc2.getLocIdentifier();
3432 SSJavaLattice<String> lattice;
3434 lattice = methodLattice;
3436 lattice = getLattice(desc1);
3439 if (symbol1.equals(symbol2)) {
3441 } else if (lattice.isGreaterThan(symbol1, symbol2)) {
3452 private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
3454 if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) {
3455 mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md));
3457 return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
3460 private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
3461 MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
3463 System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0));
3464 // if the parameter A reaches to the parameter B
3465 // then, add an edge the argument A -> the argument B to the caller's flow
3468 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
3469 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
3470 int numParam = calleeFlowGraph.getNumParameters();
3472 for (int i = 0; i < numParam; i++) {
3473 for (int k = 0; k < numParam; k++) {
3477 FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
3478 FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
3480 NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
3481 NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
3483 // check if the callee propagates an ordering constraints through
3486 Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
3488 NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
3489 NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
3491 System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
3493 System.out.println("-- localReachSet from param1=" + localReachSet);
3495 if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
3496 // if two parameters share the same prefix
3497 // it already has been assigned to a composite location
3498 // so we don't need to add an additional ordering relation caused by these two
3503 if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 && localReachSet.contains(paramNode2)) {
3504 // need to propagate an ordering relation s.t. arg1 is higher
3506 System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
3508 // add a new flow between the corresponding arguments.
3509 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
3510 System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple);
3513 // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
3517 System.out.println();
3522 // if a parameter has a composite location and the first element of the parameter location
3523 // matches the callee's 'this'
3524 // we have a more specific constraint: the caller's corresponding argument is higher than the
3525 // parameter location which is translated into the caller
3527 for (int idx = 0; idx < numParam; idx++) {
3528 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
3529 CompositeLocation compLoc = paramNode.getCompositeLocation();
3530 if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) {
3531 System.out.println("$$$COMPLOC CASE=" + compLoc);
3532 NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
3533 NTuple<Descriptor> translatedParamTuple =
3534 translateCompositeLocationToCaller(idx, min, compLoc);
3535 System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
3536 callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
3538 Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
3539 for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
3540 NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
3541 callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple);
3549 private NTuple<Descriptor> translateCompositeLocationToCaller(int idx, MethodInvokeNode min,
3550 CompositeLocation compLocForParam1) {
3552 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
3554 NTuple<Descriptor> tuple = new NTuple<Descriptor>();
3555 for (int i = 0; i < baseTuple.size(); i++) {
3556 tuple.add(baseTuple.get(i));
3559 for (int i = baseTuple.size(); i < compLocForParam1.getSize(); i++) {
3560 Location loc = compLocForParam1.get(i);
3561 tuple.add(loc.getLocDescriptor());
3567 private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
3569 System.out.println("generateCompositeLocation=" + prefixLocTuple);
3571 CompositeLocation newCompLoc = new CompositeLocation();
3572 for (int i = 0; i < prefixLocTuple.size(); i++) {
3573 newCompLoc.addLocation(prefixLocTuple.get(i));
3576 Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
3578 ClassDescriptor enclosingDescriptor;
3579 if (lastDescOfPrefix instanceof FieldDescriptor) {
3580 enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3581 // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3582 } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
3583 MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
3584 enclosingDescriptor = currentMethodDesc.getClassDesc();
3586 // var descriptor case
3587 enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3589 // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3591 LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3592 newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3594 Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3595 newLoc.setLocDescriptor(newLocDescriptor);
3596 newCompLoc.addLocation(newLoc);
3598 // System.out.println("--newCompLoc=" + newCompLoc);
3602 private CompositeLocation generateCompositeLocation(MethodDescriptor md,
3603 NTuple<Descriptor> paramPrefix) {
3605 System.out.println("generateCompositeLocation=" + paramPrefix);
3607 CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
3609 Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
3610 // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind="
3611 // + lastDescOfPrefix.getClass());
3612 ClassDescriptor enclosingDescriptor;
3613 if (lastDescOfPrefix instanceof FieldDescriptor) {
3614 enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3615 // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3617 // var descriptor case
3618 enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3620 // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3622 LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3623 newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3625 Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3626 newLoc.setLocDescriptor(newLocDescriptor);
3627 newCompLoc.addLocation(newLoc);
3629 // System.out.println("--newCompLoc=" + newCompLoc);
3633 private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
3634 MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
3636 List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
3638 for (int i = 0; i < callerPrefixList.size(); i++) {
3639 NTuple<Descriptor> prefix = callerPrefixList.get(i);
3640 if (prefix.startsWith(baseRef)) {
3641 NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
3642 calleePrefix.add(mdCallee.getThis());
3643 for (int k = 1; k < prefix.size(); k++) {
3644 calleePrefix.add(prefix.get(k));
3646 calleePrefixList.add(calleePrefix);
3650 return calleePrefixList;
3654 public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
3656 CompositeLocation compLoc = new CompositeLocation();
3658 Descriptor enclosingDescriptor = md;
3660 for (int i = 0; i < tuple.size(); i++) {
3661 Descriptor curDescriptor = tuple.get(i);
3662 Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
3663 locElement.setLocDescriptor(curDescriptor);
3664 compLoc.addLocation(locElement);
3666 if (curDescriptor instanceof VarDescriptor) {
3667 enclosingDescriptor = md.getClassDesc();
3668 } else if (curDescriptor instanceof FieldDescriptor) {
3669 enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
3670 } else if (curDescriptor instanceof NameDescriptor) {
3671 // it is "GLOBAL LOC" case!
3672 enclosingDescriptor = GLOBALDESC;
3674 enclosingDescriptor = null;
3682 private LocationDescriptor generateNewLocationDescriptor() {
3683 return new LocationDescriptor("Loc" + (locSeed++));
3686 private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
3688 // return the index where the prefix shared by tuple1 and tuple2 is ended
3689 // if there is no prefix shared by both of them, return -1
3691 int minSize = tuple1.size();
3692 if (minSize > tuple2.size()) {
3693 minSize = tuple2.size();
3697 for (int i = 0; i < minSize; i++) {
3698 if (!tuple1.get(i).equals(tuple2.get(i))) {
3708 private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
3709 NTuple<Location> tuple) {
3711 // first, retrieve inferred location by the local var descriptor
3712 CompositeLocation inferLoc = new CompositeLocation();
3714 CompositeLocation localVarInferLoc =
3715 methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
3717 localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
3719 for (int i = 0; i < localVarInferLoc.getSize(); i++) {
3720 inferLoc.addLocation(localVarInferLoc.get(i));
3723 for (int i = 1; i < tuple.size(); i++) {
3724 Location cur = tuple.get(i);
3725 Descriptor enclosingDesc = cur.getDescriptor();
3726 Descriptor curDesc = cur.getLocDescriptor();
3728 Location inferLocElement;
3729 if (curDesc == null) {
3730 // in this case, we have a newly generated location.
3731 inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
3733 String fieldLocSymbol =
3734 getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
3735 inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
3736 inferLocElement.setLocDescriptor(curDesc);
3739 inferLoc.addLocation(inferLocElement);
3743 assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
3747 public LocationInfo getLocationInfo(Descriptor d) {
3748 if (d instanceof MethodDescriptor) {
3749 return getMethodLocationInfo((MethodDescriptor) d);
3751 return getFieldLocationInfo((ClassDescriptor) d);
3755 private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
3757 if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
3758 mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
3761 return mapMethodDescToMethodLocationInfo.get(md);
3765 private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
3767 if (!mapClassToLocationInfo.containsKey(cd)) {
3768 mapClassToLocationInfo.put(cd, new LocationInfo(cd));
3771 return mapClassToLocationInfo.get(cd);
3775 private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
3776 NTuple<Location> prefix, NTuple<Location> element) {
3778 if (!map.containsKey(prefix)) {
3779 map.put(prefix, new HashSet<NTuple<Location>>());
3781 map.get(prefix).add(element);
3784 private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
3785 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
3786 Descriptor desc = (Descriptor) iterator.next();
3788 if (desc.equals(LocationInference.GLOBALDESC)) {
3790 } else if (desc instanceof VarDescriptor) {
3791 if (!((VarDescriptor) desc).getType().isPrimitive()) {
3794 } else if (desc instanceof FieldDescriptor) {
3795 if (!((FieldDescriptor) desc).getType().isPrimitive()) {
3804 private SSJavaLattice<String> getLattice(Descriptor d) {
3805 if (d instanceof MethodDescriptor) {
3806 return getMethodLattice((MethodDescriptor) d);
3808 return getFieldLattice((ClassDescriptor) d);
3812 private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
3813 if (!md2lattice.containsKey(md)) {
3814 md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3816 return md2lattice.get(md);
3819 private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
3820 md2lattice.put(md, lattice);
3823 private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
3826 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
3827 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
3829 if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
3830 && dstCurTuple.size() > (idx + 1)) {
3831 // value flow between fields: we don't need to add a binary relation
3834 Descriptor desc = srcCurTuple.get(idx);
3835 ClassDescriptor classDesc;
3838 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
3840 if (desc instanceof FieldDescriptor) {
3841 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
3843 // this case is that the local variable has a composite location assignment
3844 // the following element after the composite location to the local variable
3845 // has the enclosing descriptor of the local variable
3846 Descriptor localDesc = srcNode.getDescTuple().get(0);
3847 classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
3850 extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
3854 Descriptor srcFieldDesc = srcCurTuple.get(idx);
3855 Descriptor dstFieldDesc = dstCurTuple.get(idx);
3857 if (!srcFieldDesc.equals(dstFieldDesc)) {
3859 getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
3866 public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
3867 if (!cd2lattice.containsKey(cd)) {
3868 cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3870 return cd2lattice.get(cd);
3873 public LinkedList<MethodDescriptor> computeMethodList() {
3875 Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
3879 Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
3880 Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
3882 while (!toAnalyzeIsEmpty()) {
3883 ClassDescriptor cd = toAnalyzeNext();
3885 setupToAnalazeMethod(cd);
3886 temp_toanalyzeMethodList.removeAll(visited);
3888 while (!toAnalyzeMethodIsEmpty()) {
3889 MethodDescriptor md = toAnalyzeMethodNext();
3890 if ((!visited.contains(md))
3891 && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
3893 // creates a mapping from a method descriptor to virtual methods
3894 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3895 if (md.isStatic()) {
3896 setPossibleCallees.add(md);
3898 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3901 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
3902 Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
3904 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
3905 MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
3906 if ((!ssjava.isTrustMethod(calleemd))
3907 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
3908 if (!visited.contains(calleemd)) {
3909 temp_toanalyzeMethodList.add(calleemd);
3911 reachableCallee.add(calleemd);
3912 needToAnalyzeCalleeSet.add(calleemd);
3916 mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
3925 return ssjava.topologicalSort(toSort);
3929 public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
3930 // if the callee is transitively invoked from the caller
3933 int callerIdx = toanalyze_methodDescList.indexOf(caller);
3934 int calleeIdx = toanalyze_methodDescList.indexOf(callee);
3936 if (callerIdx < calleeIdx) {
3944 public void constructFlowGraph() {
3946 System.out.println("");
3947 toanalyze_methodDescList = computeMethodList();
3949 LinkedList<MethodDescriptor> methodDescList =
3950 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3952 System.out.println("@@@methodDescList=" + methodDescList);
3955 while (!methodDescList.isEmpty()) {
3956 MethodDescriptor md = methodDescList.removeLast();
3957 if (state.SSJAVADEBUG) {
3958 System.out.println();
3959 System.out.println("SSJAVA: Constructing a flow graph: " + md);
3961 // creates a mapping from a parameter descriptor to its index
3962 Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
3964 if (!md.isStatic()) {
3966 mapParamDescToIdx.put(md.getThis(), 0);
3969 for (int i = 0; i < md.numParameters(); i++) {
3970 Descriptor paramDesc = (Descriptor) md.getParameter(i);
3971 mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
3974 FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
3975 mapMethodDescriptorToFlowGraph.put(md, fg);
3977 analyzeMethodBody(md.getClassDesc(), md);
3979 // System.out.println("##constructSubGlobalFlowGraph");
3980 // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
3981 // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
3984 // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
3985 // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
3986 // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
3988 // propagateFlowsFromCalleesWithNoCompositeLocation(md);
3991 // _debug_printGraph();
3995 private void constructGlobalFlowGraph() {
3996 LinkedList<MethodDescriptor> methodDescList =
3997 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3999 while (!methodDescList.isEmpty()) {
4000 MethodDescriptor md = methodDescList.removeLast();
4001 if (state.SSJAVADEBUG) {
4002 System.out.println();
4003 System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
4005 constructSubGlobalFlowGraph(getFlowGraph(md));
4008 System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
4009 addValueFlowsFromCalleeSubGlobalFlowGraph(md);
4010 // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4012 // System.out.println("-propagate Flows From Callees With No CompositeLocation");
4013 // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4015 // mark if a parameter has incoming flows
4016 checkParamNodesInSubGlobalFlowGraph(md);
4022 private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) {
4023 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4024 FlowGraph flowGraph = getFlowGraph(md);
4026 Set<FlowNode> paramFlowNodeSet = flowGraph.getParamFlowNodeSet();
4027 for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) {
4028 FlowNode paramFlowNode = (FlowNode) iterator.next();
4029 System.out.println("paramFlowNode=" + paramFlowNode);
4030 NTuple<Descriptor> paramDescTuple = paramFlowNode.getDescTuple();
4031 NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
4032 GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple);
4034 Set<GlobalFlowNode> incomingNodeSet =
4035 globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0));
4037 if (incomingNodeSet.size() > 0) {
4038 paramGlobalNode.setParamNodeWithIncomingFlows(true);
4044 private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
4045 if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
4046 mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
4048 return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
4051 private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
4053 // the transformation for a call site propagates flows through parameters
4054 // if the method is virtual, it also grab all relations from any possible
4057 Set<MethodInvokeNode> setMethodInvokeNode =
4058 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4060 if (setMethodInvokeNode != null) {
4062 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4063 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4064 MethodDescriptor mdCallee = min.getMethod();
4065 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4066 if (mdCallee.isStatic()) {
4067 setPossibleCallees.add(mdCallee);
4069 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4070 // removes method descriptors that are not invoked by the caller
4071 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4072 setPossibleCallees.addAll(calleeSet);
4075 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4076 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4077 propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
4085 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
4086 BlockNode bn = state.getMethodBody(md);
4087 NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
4088 analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
4091 private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
4092 NodeTupleSet implicitFlowTupleSet) {
4094 bn.getVarTable().setParent(nametable);
4095 for (int i = 0; i < bn.size(); i++) {
4096 BlockStatementNode bsn = bn.get(i);
4097 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4102 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
4103 BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
4105 switch (bsn.kind()) {
4106 case Kind.BlockExpressionNode:
4107 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
4110 case Kind.DeclarationNode:
4111 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
4114 case Kind.IfStatementNode:
4115 analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
4119 analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
4122 case Kind.ReturnNode:
4123 analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
4126 case Kind.SubBlockNode:
4127 analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
4130 case Kind.ContinueBreakNode:
4133 case Kind.SwitchStatementNode:
4134 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
4141 private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
4142 SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4144 analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
4148 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
4149 SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
4151 NodeTupleSet condTupleNode = new NodeTupleSet();
4152 analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
4153 implicitFlowTupleSet, false);
4155 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4157 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4158 newImplicitTupleSet.addTupleSet(condTupleNode);
4160 if (needToGenerateInterLoc(newImplicitTupleSet)) {
4161 // need to create an intermediate node for the GLB of conditional
4162 // locations & implicit flows
4163 System.out.println("10");
4165 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4166 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4167 NTuple<Descriptor> tuple = idxIter.next();
4168 addFlowGraphEdge(md, tuple, interTuple);
4170 newImplicitTupleSet.clear();
4171 newImplicitTupleSet.addTuple(interTuple);
4174 BlockNode sbn = ssn.getSwitchBody();
4175 for (int i = 0; i < sbn.size(); i++) {
4176 analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
4181 private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
4182 SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4183 analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
4186 private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
4187 NodeTupleSet implicitFlowTupleSet) {
4189 // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
4190 ExpressionNode returnExp = rn.getReturnExpression();
4192 if (returnExp != null) {
4193 NodeTupleSet nodeSet = new NodeTupleSet();
4194 // if a return expression returns a literal value, nodeSet is empty
4195 analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
4196 FlowGraph fg = getFlowGraph(md);
4198 // if (implicitFlowTupleSet.size() == 1
4200 // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
4203 // // since there is already an intermediate node for the GLB of implicit
4205 // // we don't need to create another intermediate node.
4206 // // just re-use the intermediate node for implicit flows.
4208 // FlowNode meetNode =
4209 // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
4211 // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
4212 // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
4214 // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
4219 NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
4221 // add tuples from return node
4222 currentFlowTupleSet.addTupleSet(nodeSet);
4224 // add tuples corresponding to the current implicit flows
4225 currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
4227 // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
4229 if (needToGenerateInterLoc(currentFlowTupleSet)) {
4230 System.out.println("9");
4232 FlowNode meetNode = fg.createIntermediateNode();
4233 for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4234 NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4235 fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
4237 fg.addReturnFlowNode(meetNode.getDescTuple());
4239 // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
4240 for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4241 NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4242 fg.addReturnFlowNode(currentFlowTuple);
4250 private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
4251 NodeTupleSet tupleSet = new NodeTupleSet();
4252 for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
4253 NTuple<Descriptor> tuple = iter.next();
4254 if (!tuple.get(0).equals(LITERALDESC)) {
4255 tupleSet.addTuple(tuple);
4261 private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
4263 for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
4264 NTuple<Descriptor> descTuple = iter.next();
4265 if (!descTuple.get(0).equals(LITERALDESC)) {
4270 System.out.println("needToGenerateInterLoc=" + tupleSet + " size=" + size);
4277 private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
4278 NodeTupleSet implicitFlowTupleSet) {
4280 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
4282 NodeTupleSet condTupleNode = new NodeTupleSet();
4283 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
4284 implicitFlowTupleSet, false);
4286 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4288 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4289 newImplicitTupleSet.addTupleSet(condTupleNode);
4291 newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet());
4292 newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
4294 if (needToGenerateInterLoc(newImplicitTupleSet)) {
4295 // need to create an intermediate node for the GLB of conditional
4296 // locations & implicit flows
4297 System.out.println("6");
4299 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4300 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4302 NTuple<Descriptor> tuple = idxIter.next();
4303 addFlowGraphEdge(md, tuple, interTuple);
4305 newImplicitTupleSet.clear();
4306 newImplicitTupleSet.addTuple(interTuple);
4311 // System.out.println("condTupleNode="+condTupleNode);
4312 // NTuple<Descriptor> interTuple =
4313 // getFlowGraph(md).createIntermediateNode().getDescTuple();
4315 // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
4316 // idxIter.hasNext();) {
4317 // NTuple<Descriptor> tuple = idxIter.next();
4318 // addFlowGraphEdge(md, tuple, interTuple);
4321 // for (Iterator<NTuple<Descriptor>> idxIter =
4322 // implicitFlowTupleSet.iterator(); idxIter
4324 // NTuple<Descriptor> tuple = idxIter.next();
4325 // addFlowGraphEdge(md, tuple, interTuple);
4328 // NodeTupleSet newImplicitSet = new NodeTupleSet();
4329 // newImplicitSet.addTuple(interTuple);
4330 analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
4333 // condTupleNode.addTupleSet(implicitFlowTupleSet);
4335 // add edges from condNodeTupleSet to all nodes of conditional nodes
4336 // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
4339 // check 'for loop' case
4340 BlockNode bn = ln.getInitializer();
4341 bn.getVarTable().setParent(nametable);
4342 for (int i = 0; i < bn.size(); i++) {
4343 BlockStatementNode bsn = bn.get(i);
4344 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4347 NodeTupleSet condTupleNode = new NodeTupleSet();
4348 analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
4349 implicitFlowTupleSet, false);
4351 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4352 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4353 newImplicitTupleSet.addTupleSet(condTupleNode);
4355 if (needToGenerateInterLoc(newImplicitTupleSet)) {
4356 // need to create an intermediate node for the GLB of conditional
4357 // locations & implicit flows
4358 System.out.println("7");
4360 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4361 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4363 NTuple<Descriptor> tuple = idxIter.next();
4364 addFlowGraphEdge(md, tuple, interTuple);
4366 newImplicitTupleSet.clear();
4367 newImplicitTupleSet.addTuple(interTuple);
4372 // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4374 // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
4375 // NTuple<Descriptor> tuple = idxIter.next();
4376 // addFlowGraphEdge(md, tuple, interTuple);
4379 // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
4381 // NTuple<Descriptor> tuple = idxIter.next();
4382 // addFlowGraphEdge(md, tuple, interTuple);
4385 // NodeTupleSet newImplicitSet = new NodeTupleSet();
4386 // newImplicitSet.addTuple(interTuple);
4387 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
4388 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
4391 // condTupleNode.addTupleSet(implicitFlowTupleSet);
4393 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
4395 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
4402 private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
4403 IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
4405 // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
4407 NodeTupleSet condTupleNode = new NodeTupleSet();
4408 analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
4409 implicitFlowTupleSet, false);
4411 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4413 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4414 newImplicitTupleSet.addTupleSet(condTupleNode);
4416 // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet());
4417 // System.out.println("-condTupleNode=" + condTupleNode);
4418 // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4419 // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
4421 if (needToGenerateInterLoc(newImplicitTupleSet)) {
4422 System.out.println("5");
4424 // need to create an intermediate node for the GLB of conditional locations & implicit flows
4425 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4426 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4427 NTuple<Descriptor> tuple = idxIter.next();
4428 addFlowGraphEdge(md, tuple, interTuple);
4430 newImplicitTupleSet.clear();
4431 newImplicitTupleSet.addTuple(interTuple);
4434 // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4435 // for (Iterator<NTuple<Location>> iterator = condTupleNode.globalIterator();
4436 // iterator.hasNext();) {
4437 // NTuple<Location> calleeReturnLocTuple = iterator.next();
4438 // for (Iterator<NTuple<Descriptor>> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) {
4439 // NTuple<Descriptor> callerImplicitTuple = iter2.next();
4440 // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
4441 // translateToLocTuple(md, callerImplicitTuple));
4444 newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
4446 analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
4448 if (isn.getFalseBlock() != null) {
4449 analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
4454 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
4455 DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
4457 VarDescriptor vd = dn.getVarDescriptor();
4458 mapDescToDefinitionLine.put(vd, dn.getNumLine());
4459 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
4461 FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
4462 fn.setDeclarationNode();
4464 if (dn.getExpression() != null) {
4466 NodeTupleSet nodeSetRHS = new NodeTupleSet();
4467 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
4468 implicitFlowTupleSet, false);
4470 // creates edges from RHS to LHS
4471 NTuple<Descriptor> interTuple = null;
4472 if (needToGenerateInterLoc(nodeSetRHS)) {
4473 System.out.println("3");
4474 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4477 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
4478 NTuple<Descriptor> fromTuple = iter.next();
4479 System.out.println("fromTuple=" + fromTuple + " interTuple=" + interTuple + " tupleLSH="
4481 addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
4484 // creates edges from implicitFlowTupleSet to LHS
4485 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4486 NTuple<Descriptor> implicitTuple = iter.next();
4487 addFlowGraphEdge(md, implicitTuple, tupleLHS);
4490 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4491 for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
4492 NTuple<Location> calleeReturnLocTuple = iterator.next();
4493 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS));
4500 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
4501 BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
4502 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
4506 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4507 ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
4508 return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
4511 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4512 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4513 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
4515 // note that expression node can create more than one flow node
4516 // nodeSet contains of flow nodes
4517 // base is always assigned to null except the case of a name node!
4518 NTuple<Descriptor> flowTuple;
4519 switch (en.kind()) {
4521 case Kind.AssignmentNode:
4522 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
4523 implicitFlowTupleSet);
4526 case Kind.FieldAccessNode:
4528 analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
4529 implicitFlowTupleSet, isLHS);
4530 if (flowTuple != null) {
4531 nodeSet.addTuple(flowTuple);
4536 NodeTupleSet nameNodeSet = new NodeTupleSet();
4538 analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
4539 if (flowTuple != null) {
4540 nodeSet.addTuple(flowTuple);
4545 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
4548 case Kind.CreateObjectNode:
4549 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
4552 case Kind.ArrayAccessNode:
4553 analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
4556 case Kind.LiteralNode:
4557 analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
4560 case Kind.MethodInvokeNode:
4561 analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
4562 implicitFlowTupleSet);
4565 case Kind.TertiaryNode:
4566 analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
4570 analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
4572 // case Kind.InstanceOfNode:
4573 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
4576 // case Kind.ArrayInitializerNode:
4577 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
4581 // case Kind.ClassTypeNode:
4582 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
4585 // case Kind.OffsetNode:
4586 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
4595 private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
4596 NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
4598 analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
4599 implicitFlowTupleSet, false);
4603 private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
4604 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4606 System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0));
4608 NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
4609 analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
4610 implicitFlowTupleSet, false);
4612 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4613 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4614 newImplicitTupleSet.addTupleSet(tertiaryTupleNode);
4616 System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet());
4617 System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode);
4618 System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4619 System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
4621 if (needToGenerateInterLoc(newImplicitTupleSet)) {
4622 System.out.println("15");
4623 // need to create an intermediate node for the GLB of conditional locations & implicit flows
4624 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4625 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4626 NTuple<Descriptor> tuple = idxIter.next();
4627 addFlowGraphEdge(md, tuple, interTuple);
4629 newImplicitTupleSet.clear();
4630 newImplicitTupleSet.addTuple(interTuple);
4633 newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
4635 // add edges from tertiaryTupleNode to all nodes of conditional nodes
4636 // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
4637 analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
4638 newImplicitTupleSet, false);
4640 analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
4641 newImplicitTupleSet, false);
4643 nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
4644 nodeSet.addTupleSet(tertiaryTupleNode);
4646 System.out.println("#tertiary node set=" + nodeSet);
4649 private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
4650 MethodInvokeNode min) {
4651 Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
4653 set = new HashSet<MethodInvokeNode>();
4654 mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
4659 private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
4661 if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4662 mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4664 mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
4667 private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
4669 if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4670 mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4673 return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
4676 private Set<NTuple<Location>> getPCLocTupleSet(MethodInvokeNode min) {
4677 if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) {
4678 mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet<NTuple<Location>>());
4680 return mapMethodInvokeNodeToPCLocTupleSet.get(min);
4683 private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable,
4684 MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4686 System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
4688 if (!toanalyze_methodDescList.contains(min.getMethod())) {
4692 addMapMethodDescToMethodInvokeNodeSet(min);
4694 Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
4695 for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) {
4696 NTuple<Descriptor> pcDescTuple = (NTuple<Descriptor>) iterator.next();
4697 if (!pcDescTuple.get(0).equals(LITERALDESC)) {
4698 // here we don't need to add the literal value as a PC location
4699 pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple));
4703 mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
4705 if (nodeSet == null) {
4706 nodeSet = new NodeTupleSet();
4709 MethodDescriptor mdCallee = min.getMethod();
4711 NameDescriptor baseName = min.getBaseName();
4712 boolean isSystemout = false;
4713 if (baseName != null) {
4714 isSystemout = baseName.getSymbol().equals("System.out");
4717 if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee)
4720 addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min);
4722 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
4723 System.out.println("mdCallee=" + mdCallee);
4724 Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
4726 System.out.println("---calleeReturnSet=" + calleeReturnSet);
4728 NodeTupleSet tupleSet = new NodeTupleSet();
4730 if (min.getExpression() != null) {
4732 NodeTupleSet baseNodeSet = new NodeTupleSet();
4733 analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null,
4734 implicitFlowTupleSet, false);
4736 assert (baseNodeSet.size() == 1);
4737 NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
4738 mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
4740 if (!min.getMethod().isStatic()) {
4741 addArgIdxMap(min, 0, baseTuple);
4743 for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
4744 FlowNode returnNode = (FlowNode) iterator.next();
4745 NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
4746 if (returnDescTuple.startsWith(mdCallee.getThis())) {
4747 // the location type of the return value is started with 'this'
4749 NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
4750 inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
4751 // nodeSet.addTuple(inFlowTuple);
4752 tupleSet.addTuple(inFlowTuple);
4755 Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
4756 // System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode);
4757 for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
4758 FlowNode inFlowNode = (FlowNode) iterator2.next();
4759 if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) {
4760 // nodeSet.addTupleSet(baseNodeSet);
4761 tupleSet.addTupleSet(baseNodeSet);
4770 // analyze parameter flows
4772 if (min.numArgs() > 0) {
4775 if (min.getMethod().isStatic()) {
4781 for (int i = 0; i < min.numArgs(); i++) {
4782 ExpressionNode en = min.getArg(i);
4783 int idx = i + offset;
4784 NodeTupleSet argTupleSet = new NodeTupleSet();
4785 analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false);
4786 // if argument is liternal node, argTuple is set to NULL
4787 System.out.println("argTupleSet=" + argTupleSet);
4788 NTuple<Descriptor> argTuple = generateArgTuple(mdCaller, argTupleSet);
4790 // if an argument is literal value,
4791 // we need to create an itermediate node so that we could assign a composite location to
4792 // that node if needed
4793 if (argTuple.size() > 0
4794 && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) {
4795 System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple);
4796 System.out.println("8");
4798 NTuple<Descriptor> interTuple =
4799 getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
4800 ((InterDescriptor) interTuple.get(0)).setMethodArgIdxPair(min, idx);
4801 addFlowGraphEdge(mdCaller, argTuple, interTuple);
4802 argTuple = interTuple;
4803 addArgIdxMap(min, idx, argTuple);
4804 System.out.println("new min mapping i=" + idx + " ->" + argTuple);
4807 addArgIdxMap(min, idx, argTuple);
4809 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4811 // check whether a param node in the callee graph has incoming flows
4812 // if it has incoming flows, the corresponding arg should be lower than the current PC
4813 // Descriptor prefix = paramNode.getDescTuple().get(0);
4814 // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
4815 // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
4817 // NTuple<Descriptor> pcTuple = iterator.next();
4818 // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
4819 // addFlowGraphEdge(md, pcTuple, argTuple);
4823 if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
4824 || mdCallee.getModifiers().isNative()) {
4825 addParamNodeFlowingToReturnValue(mdCallee, paramNode);
4826 // nodeSet.addTupleSet(argTupleSet);
4827 tupleSet.addTupleSet(argTupleSet);
4833 if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) {
4834 FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min);
4835 setNode.addTupleSet(tupleSet);
4836 nodeSet.addTuple(setNode.getDescTuple());
4839 // propagateFlowsFromCallee(min, md, min.getMethod());
4841 // when generating the global flow graph,
4842 // we need to add ordering relations from the set of callee return loc tuple to LHS of the
4843 // caller assignment
4844 for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
4845 FlowNode calleeReturnNode = (FlowNode) iterator.next();
4846 NTuple<Location> calleeReturnLocTuple =
4847 translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple());
4848 System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple);
4849 nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller,
4850 calleeReturnLocTuple));
4853 System.out.println("min nodeSet=" + nodeSet);
4859 private NTuple<Descriptor> generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) {
4863 // if argTupleSet is empty, it comes from the top location
4864 if (argTupleSet.size() == 0) {
4865 NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
4866 descTuple.add(LITERALDESC);
4870 Set<NTuple<Descriptor>> argTupleSetNonLiteral = new HashSet<NTuple<Descriptor>>();
4872 for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
4873 NTuple<Descriptor> descTuple = iter.next();
4874 if (!descTuple.get(0).equals(LITERALDESC)) {
4875 argTupleSetNonLiteral.add(descTuple);
4879 if (argTupleSetNonLiteral.size() > 1) {
4880 System.out.println("11");
4882 NTuple<Descriptor> interTuple =
4883 getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
4884 for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
4885 NTuple<Descriptor> tuple = idxIter.next();
4886 addFlowGraphEdge(mdCaller, tuple, interTuple);
4889 } else if (argTupleSetNonLiteral.size() == 1) {
4890 return argTupleSetNonLiteral.iterator().next();
4892 return argTupleSet.iterator().next();
4897 private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
4898 // return true if inNode has in-flows to nodeSet
4900 // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
4901 Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
4902 // System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet);
4904 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
4905 FlowNode fn = (FlowNode) iterator.next();
4906 if (nodeSet.contains(fn)) {
4913 private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
4914 return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
4917 private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
4921 Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
4922 if (mapIdxToTuple == null) {
4923 mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
4924 mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
4926 mapIdxToTuple.put(new Integer(idx), argTuple);
4929 private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
4930 NodeTupleSet nodeSet) {
4931 NTuple<Descriptor> tuple = new NTuple<Descriptor>();
4932 tuple.add(LITERALDESC);
4933 nodeSet.addTuple(tuple);
4936 private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
4937 ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
4939 // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0));
4940 String currentArrayAccessNodeExpStr = aan.printNode(0);
4941 arrayAccessNodeStack.push(aan.printNode(0));
4943 NodeTupleSet expNodeTupleSet = new NodeTupleSet();
4944 NTuple<Descriptor> base =
4945 analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
4947 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
4948 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
4950 arrayAccessNodeStack.pop();
4953 // need to create an edge from idx to array
4954 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
4955 NTuple<Descriptor> idxTuple = idxIter.next();
4956 for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
4957 NTuple<Descriptor> arrTuple = arrIter.next();
4958 getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
4962 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4963 for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
4965 NTuple<Location> calleeReturnLocTuple = iterator.next();
4966 for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
4967 NTuple<Descriptor> arrTuple = arrIter.next();
4968 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple));
4972 nodeSet.addTupleSet(expNodeTupleSet);
4975 NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
4977 nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
4978 nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
4980 if (arrayAccessNodeStack.isEmpty()
4981 || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
4983 if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
4984 System.out.println("1");
4985 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4987 for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
4988 NTuple<Descriptor> higherTuple = iter.next();
4989 addFlowGraphEdge(md, higherTuple, interTuple);
4991 nodeSetArrayAccessExp.clear();
4992 nodeSetArrayAccessExp.addTuple(interTuple);
4996 nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
4997 nodeSet.addTupleSet(nodeSetArrayAccessExp);
5003 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
5004 CreateObjectNode en) {
5005 // TODO Auto-generated method stub
5009 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
5010 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5012 NodeTupleSet leftOpSet = new NodeTupleSet();
5013 NodeTupleSet rightOpSet = new NodeTupleSet();
5016 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
5019 if (on.getRight() != null) {
5021 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
5022 implicitFlowTupleSet, false);
5025 Operation op = on.getOp();
5027 switch (op.getOp()) {
5029 case Operation.UNARYPLUS:
5030 case Operation.UNARYMINUS:
5031 case Operation.LOGIC_NOT:
5033 nodeSet.addTupleSet(leftOpSet);
5036 case Operation.LOGIC_OR:
5037 case Operation.LOGIC_AND:
5038 case Operation.COMP:
5039 case Operation.BIT_OR:
5040 case Operation.BIT_XOR:
5041 case Operation.BIT_AND:
5042 case Operation.ISAVAILABLE:
5043 case Operation.EQUAL:
5044 case Operation.NOTEQUAL:
5051 case Operation.MULT:
5054 case Operation.LEFTSHIFT:
5055 case Operation.RIGHTSHIFT:
5056 case Operation.URIGHTSHIFT:
5058 // there are two operands
5059 nodeSet.addTupleSet(leftOpSet);
5060 nodeSet.addTupleSet(rightOpSet);
5062 nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet());
5063 nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet());
5068 throw new Error(op.toString());
5073 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
5074 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5077 base = new NTuple<Descriptor>();
5080 NameDescriptor nd = nn.getName();
5082 if (nd.getBase() != null) {
5084 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
5085 implicitFlowTupleSet, false);
5087 // base node has the top location
5091 String varname = nd.toString();
5092 if (varname.equals("this")) {
5094 base.add(md.getThis());
5098 Descriptor d = (Descriptor) nametable.get(varname);
5100 if (d instanceof VarDescriptor) {
5101 VarDescriptor vd = (VarDescriptor) d;
5103 } else if (d instanceof FieldDescriptor) {
5104 // the type of field descriptor has a location!
5105 FieldDescriptor fd = (FieldDescriptor) d;
5106 if (fd.isStatic()) {
5108 // if it is 'static final', no need to have flow node for the TOP
5112 // if 'static', assign the default GLOBAL LOCATION to the first
5113 // element of the tuple
5114 base.add(GLOBALDESC);
5117 // the location of field access starts from this, followed by field
5119 base.add(md.getThis());
5123 } else if (d == null) {
5124 // access static field
5125 base.add(GLOBALDESC);
5126 base.add(nn.getField());
5129 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
5131 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
5132 // String globalLocId = localLattice.getGlobalLoc();
5133 // if (globalLocId == null) {
5135 // Error("Method lattice does not define global variable location at "
5136 // + generateErrorMessage(md.getClassDesc(), nn));
5138 // loc.addLocation(new Location(md, globalLocId));
5140 // Location fieldLoc = (Location) fd.getType().getExtension();
5141 // loc.addLocation(fieldLoc);
5147 getFlowGraph(md).createNewFlowNode(base);
5153 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
5154 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5155 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5156 // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0));
5158 String currentArrayAccessNodeExpStr = null;
5159 ExpressionNode left = fan.getExpression();
5160 TypeDescriptor ltd = left.getType();
5161 FieldDescriptor fd = fan.getField();
5162 ArrayAccessNode aan = null;
5164 String varName = null;
5165 if (left.kind() == Kind.NameNode) {
5166 NameDescriptor nd = ((NameNode) left).getName();
5167 varName = nd.toString();
5170 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
5171 // using a class name directly or access using this
5172 if (fd.isStatic() && fd.isFinal()) {
5177 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5179 boolean isArrayCase = false;
5180 if (left instanceof ArrayAccessNode) {
5183 aan = (ArrayAccessNode) left;
5185 currentArrayAccessNodeExpStr = aan.printNode(0);
5186 arrayAccessNodeStack.push(currentArrayAccessNodeExpStr);
5188 left = aan.getExpression();
5189 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
5190 implicitFlowTupleSet, isLHS);
5192 nodeSet.addTupleSet(idxNodeTupleSet);
5195 analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
5198 // in this case, field is TOP location
5202 NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
5204 if (!left.getType().isPrimitive()) {
5205 if (!fd.getSymbol().equals("length")) {
5206 // array.length access, just have the location of the array
5207 flowFieldTuple.add(fd);
5208 nodeSet.removeTuple(base);
5211 getFlowGraph(md).createNewFlowNode(flowFieldTuple);
5214 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5215 NTuple<Descriptor> idxTuple = idxIter.next();
5216 getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
5219 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5220 for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
5222 NTuple<Location> calleeReturnLocTuple = iterator.next();
5223 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5224 translateToLocTuple(md, flowFieldTuple));
5229 // if it is the array case and not the LHS case
5231 arrayAccessNodeStack.pop();
5233 if (arrayAccessNodeStack.isEmpty()
5234 || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
5235 NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
5237 nodeSetArrayAccessExp.addTuple(flowFieldTuple);
5238 nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
5239 nodeSetArrayAccessExp.addTupleSet(nodeSet);
5241 if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
5242 System.out.println("4");
5243 System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp);
5244 // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()="
5245 // + idxNodeTupleSet.getGlobalLocTupleSet());
5247 NTuple<Descriptor> interTuple =
5248 getFlowGraph(md).createIntermediateNode().getDescTuple();
5250 for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter
5252 NTuple<Descriptor> higherTuple = iter.next();
5253 addFlowGraphEdge(md, higherTuple, interTuple);
5256 flowFieldTuple = interTuple;
5259 nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
5265 return flowFieldTuple;
5270 private void debug_printTreeNode(TreeNode tn) {
5272 System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine());
5276 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
5277 AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5278 NodeTupleSet implicitFlowTupleSet) {
5280 NodeTupleSet nodeSetRHS = new NodeTupleSet();
5281 NodeTupleSet nodeSetLHS = new NodeTupleSet();
5283 boolean postinc = true;
5284 if (an.getOperation().getBaseOp() == null
5285 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
5286 .getBaseOp().getOp() != Operation.POSTDEC)) {
5289 // if LHS is array access node, need to capture value flows between an array
5290 // and its index value
5291 analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
5295 // analyze value flows of rhs expression
5296 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
5299 // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
5300 // System.out.println("-nodeSetLHS=" + nodeSetLHS);
5301 // System.out.println("-nodeSetRHS=" + nodeSetRHS);
5302 // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5303 // System.out.println("-");
5305 if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
5306 // if assignment contains OP+EQ operator, creates edges from LHS to LHS
5308 for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
5309 NTuple<Descriptor> fromTuple = iter.next();
5310 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5311 NTuple<Descriptor> toTuple = iter2.next();
5312 addFlowGraphEdge(md, fromTuple, toTuple);
5317 // creates edges from RHS to LHS
5318 NTuple<Descriptor> interTuple = null;
5319 if (needToGenerateInterLoc(nodeSetRHS)) {
5320 System.out.println("2");
5322 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5325 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5326 NTuple<Descriptor> fromTuple = iter.next();
5327 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5328 NTuple<Descriptor> toTuple = iter2.next();
5329 addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
5333 // creates edges from implicitFlowTupleSet to LHS
5334 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5335 NTuple<Descriptor> fromTuple = iter.next();
5336 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5337 NTuple<Descriptor> toTuple = iter2.next();
5338 addFlowGraphEdge(md, fromTuple, toTuple);
5342 // create global flow edges if the callee gives return value flows to the caller
5343 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5344 for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
5345 NTuple<Location> calleeReturnLocTuple = iterator.next();
5346 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5347 NTuple<Descriptor> callerLHSTuple = iter2.next();
5348 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5349 translateToLocTuple(md, callerLHSTuple));
5350 System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> "
5351 + translateToLocTuple(md, callerLHSTuple));
5355 for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5357 NTuple<Location> calleeReturnLocTuple = iterator.next();
5358 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5359 NTuple<Descriptor> callerLHSTuple = iter2.next();
5360 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5361 translateToLocTuple(md, callerLHSTuple));
5362 System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> "
5363 + translateToLocTuple(md, callerLHSTuple));
5370 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5371 NTuple<Descriptor> tuple = iter2.next();
5372 addFlowGraphEdge(md, tuple, tuple);
5375 // creates edges from implicitFlowTupleSet to LHS
5376 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5377 NTuple<Descriptor> fromTuple = iter.next();
5378 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5379 NTuple<Descriptor> toTuple = iter2.next();
5380 addFlowGraphEdge(md, fromTuple, toTuple);
5384 GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5385 for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5387 NTuple<Location> calleeReturnLocTuple = iterator.next();
5388 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5389 NTuple<Descriptor> callerLHSTuple = iter2.next();
5390 globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5391 translateToLocTuple(md, callerLHSTuple));
5392 System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> "
5393 + translateToLocTuple(md, callerLHSTuple));
5399 if (nodeSet != null) {
5400 nodeSet.addTupleSet(nodeSetLHS);
5401 nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet());
5405 public FlowGraph getFlowGraph(MethodDescriptor md) {
5406 return mapMethodDescriptorToFlowGraph.get(md);
5409 private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5410 NTuple<Descriptor> to) {
5411 FlowGraph graph = getFlowGraph(md);
5412 graph.addValueFlowEdge(from, to);
5416 private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5417 NTuple<Descriptor> inter, NTuple<Descriptor> to) {
5419 FlowGraph graph = getFlowGraph(md);
5421 if (inter != null) {
5422 graph.addValueFlowEdge(from, inter);
5423 graph.addValueFlowEdge(inter, to);
5425 graph.addValueFlowEdge(from, to);
5430 public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
5431 SSJavaLattice<String> locOrder, String nameSuffix) {
5432 System.out.println("@cd=" + cd);
5433 System.out.println("@sharedLoc=" + locOrder.getSharedLocSet());
5434 writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
5437 public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
5438 HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
5440 String fileName = "lattice_";
5443 /* cd.getSymbol().replaceAll("[\\W_]", "") + "_" + */md.toString().replaceAll("[\\W_]", "");
5445 fileName += cd.getSymbol().replaceAll("[\\W_]", "");
5448 fileName += nameSuffix;
5450 Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
5452 Set<String> addedLocSet = new HashSet<String>();
5454 if (pairSet.size() > 0) {
5456 BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
5458 bw.write("digraph " + fileName + " {\n");
5460 for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
5461 // pair is in the form of <higher, lower>
5462 Pair<String, String> pair = (Pair<String, String>) iterator.next();
5464 String highLocId = pair.getFirst();
5465 String lowLocId = pair.getSecond();
5466 System.out.println("addedLocSet=" + addedLocSet);
5467 if (!addedLocSet.contains(highLocId)) {
5468 addedLocSet.add(highLocId);
5469 drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
5472 if (!addedLocSet.contains(lowLocId)) {
5473 addedLocSet.add(lowLocId);
5474 drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
5477 bw.write(highLocId + " -> " + lowLocId + ";\n");
5482 } catch (IOException e) {
5483 e.printStackTrace();
5490 private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
5492 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
5493 HNode merged = (HNode) iterator.next();
5494 if (merged.isMergeNode()) {
5495 str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
5497 str += " " + merged.getName();
5503 private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
5504 String locName) throws IOException {
5507 if (lattice.isSharedLoc(locName)) {
5508 prettyStr = locName + "*";
5510 prettyStr = locName;
5512 // HNode node = graph.getHNode(locName);
5513 // if (node != null && node.isMergeNode()) {
5514 // Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
5515 // prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
5517 bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
5520 public void _debug_writeFlowGraph() {
5521 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
5523 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
5524 MethodDescriptor md = (MethodDescriptor) iterator.next();
5525 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
5526 GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
5529 subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
5530 } catch (IOException e) {
5531 e.printStackTrace();
5539 class CyclicFlowException extends Exception {
5543 class InterDescriptor extends Descriptor {
5545 Pair<MethodInvokeNode, Integer> minArgIdxPair;
5547 public InterDescriptor(String name) {
5551 public void setMethodArgIdxPair(MethodInvokeNode min, int idx) {
5552 minArgIdxPair = new Pair<MethodInvokeNode, Integer>(min, new Integer(idx));
5555 public Pair<MethodInvokeNode, Integer> getMethodArgIdxPair() {
5556 return minArgIdxPair;