adding a test case
[IRC.git] / Robust / src / Analysis / SSJava / FlowGraph.java
1 package Analysis.SSJava;
2
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.HashMap;
7 import java.util.HashSet;
8 import java.util.Iterator;
9 import java.util.Map;
10 import java.util.Set;
11
12 import IR.ClassDescriptor;
13 import IR.Descriptor;
14 import IR.FieldDescriptor;
15 import IR.MethodDescriptor;
16 import IR.NameDescriptor;
17 import IR.VarDescriptor;
18 import IR.Tree.MethodInvokeNode;
19
20 public class FlowGraph {
21
22   MethodDescriptor md;
23
24   Set<FlowNode> returnNodeSet;
25   FlowNode thisVarNode;
26
27   Map<FlowNode, Set<FlowEdge>> mapFlowNodeToInEdgeSet;
28   Map<FlowNode, Set<FlowEdge>> mapFlowNodeToOutEdgeSet;
29
30   Map<NTuple<Location>, FlowNode> mapLocTupleToFlowNode;
31   Map<FlowNode, NTuple<Location>> mapFlowNodeToLocTuple;
32
33   // maps the composite representation of field/var descriptors to infer nodes
34   Map<NTuple<Descriptor>, FlowNode> mapDescTupleToInferNode;
35
36   // maps a paramter descriptor to its index
37   Map<Descriptor, Integer> mapParamDescToIdx;
38
39   // DS for the lattice generation
40   Map<Integer, FlowNode> mapIdxToFlowNode;
41
42   Map<MethodInvokeNode, FlowReturnNode> mapMethodInvokeNodeToFlowReturnNode;
43
44   Map<Descriptor, ClassDescriptor> mapIntersectionDescToEnclosingDescriptor;
45
46   public static int interseed = 0;
47
48   boolean debug = true;
49
50   public FlowGraph(MethodDescriptor md, Map<Descriptor, Integer> mapParamDescToIdx) {
51     this.md = md;
52     this.mapFlowNodeToLocTuple = new HashMap<FlowNode, NTuple<Location>>();
53     this.mapLocTupleToFlowNode = new HashMap<NTuple<Location>, FlowNode>();
54     this.mapDescTupleToInferNode = new HashMap<NTuple<Descriptor>, FlowNode>();
55     this.mapParamDescToIdx = new HashMap<Descriptor, Integer>();
56     this.mapParamDescToIdx.putAll(mapParamDescToIdx);
57     this.returnNodeSet = new HashSet<FlowNode>();
58     this.mapIdxToFlowNode = new HashMap<Integer, FlowNode>();
59     this.mapFlowNodeToOutEdgeSet = new HashMap<FlowNode, Set<FlowEdge>>();
60     this.mapFlowNodeToInEdgeSet = new HashMap<FlowNode, Set<FlowEdge>>();
61     this.mapMethodInvokeNodeToFlowReturnNode = new HashMap<MethodInvokeNode, FlowReturnNode>();
62     this.mapIntersectionDescToEnclosingDescriptor = new HashMap<Descriptor, ClassDescriptor>();
63
64     if (!md.isStatic()) {
65       // create a node for 'this' varialbe
66       // NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();
67       // thisDescTuple.add(md.getThis());
68
69       NTuple<Descriptor> thisVarTuple = new NTuple<Descriptor>();
70       thisVarTuple.add(md.getThis());
71       FlowNode thisNode = createNewFlowNode(thisVarTuple);
72       thisNode.setSkeleton(true);
73       thisVarNode = thisNode;
74     }
75
76     setupMapIdxToDesc();
77
78   }
79
80   public void addMapInterLocNodeToEnclosingDescriptor(Descriptor interDesc, ClassDescriptor desc) {
81     mapIntersectionDescToEnclosingDescriptor.put(interDesc, desc);
82   }
83
84   public ClassDescriptor getEnclosingDescriptor(Descriptor interDesc) {
85     return mapIntersectionDescToEnclosingDescriptor.get(interDesc);
86   }
87
88   public Map<NTuple<Descriptor>, FlowNode> getMapDescTupleToInferNode() {
89     return mapDescTupleToInferNode;
90   }
91
92   public void setMapDescTupleToInferNode(Map<NTuple<Descriptor>, FlowNode> in) {
93     this.mapDescTupleToInferNode.putAll(in);
94   }
95
96   public Map<NTuple<Location>, FlowNode> getMapLocTupleToFlowNode() {
97     return mapLocTupleToFlowNode;
98   }
99
100   public void setMapLocTupleToFlowNode(Map<NTuple<Location>, FlowNode> in) {
101     this.mapLocTupleToFlowNode.putAll(in);
102   }
103
104   public void setReturnNodeSet(Set<FlowNode> in) {
105     this.returnNodeSet.addAll(in);
106   }
107
108   public void setThisVarNode(FlowNode thisVarNode) {
109     this.thisVarNode = thisVarNode;
110   }
111
112   public Map<Descriptor, Integer> getMapParamDescToIdx() {
113     return mapParamDescToIdx;
114   }
115
116   public FlowNode createIntermediateNode() {
117     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
118     Descriptor interDesc = new InterDescriptor(LocationInference.INTERLOC + interseed);
119     tuple.add(interDesc);
120     interseed++;
121
122     FlowNode newNode = new FlowNode(tuple);
123     newNode.setIntermediate(true);
124
125     mapDescTupleToInferNode.put(tuple, newNode);
126     // nodeSet.add(newNode);
127
128     // System.out.println("create new intsermediate node= " + newNode);
129
130     return newNode;
131   }
132
133   public FlowReturnNode getFlowReturnNode(MethodInvokeNode min) {
134     return mapMethodInvokeNodeToFlowReturnNode.get(min);
135   }
136
137   public FlowReturnNode createReturnNode(MethodInvokeNode min) {
138     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
139     NameDescriptor n = new NameDescriptor("RETURNLOC" + (LocationInference.locSeed++));
140     tuple.add(n);
141
142     FlowReturnNode newNode = new FlowReturnNode(tuple, min);
143     mapDescTupleToInferNode.put(tuple, newNode);
144     mapMethodInvokeNodeToFlowReturnNode.put(min, newNode);
145     // nodeSet.add(newNode);
146
147     // System.out.println("create new set node= " + newNode);
148
149     return newNode;
150   }
151
152   private void setupMapIdxToDesc() {
153
154     Set<Descriptor> descSet = mapParamDescToIdx.keySet();
155     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
156       Descriptor paramDesc = (Descriptor) iterator.next();
157       int idx = mapParamDescToIdx.get(paramDesc);
158       NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
159       descTuple.add(paramDesc);
160       FlowNode paramNode = getFlowNode(descTuple);
161       mapIdxToFlowNode.put(idx, paramNode);
162       paramNode.setSkeleton(true);
163     }
164
165   }
166
167   public int getNumParameters() {
168     return mapIdxToFlowNode.keySet().size();
169   }
170
171   public FlowNode getParamFlowNode(int idx) {
172     return mapIdxToFlowNode.get(idx);
173   }
174
175   public Set<FlowEdge> getEdgeSet() {
176     Set<FlowEdge> edgeSet = new HashSet<FlowEdge>();
177
178     Set<FlowNode> nodeSet = getNodeSet();
179     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
180       FlowNode flowNode = (FlowNode) iterator.next();
181       edgeSet.addAll(getOutEdgeSet(flowNode));
182     }
183     return edgeSet;
184   }
185
186   public Set<FlowNode> getParamFlowNodeSet() {
187     Set<FlowNode> setParamFlowNode = new HashSet<FlowNode>();
188     setParamFlowNode.addAll(mapIdxToFlowNode.values());
189     return setParamFlowNode;
190   }
191
192   public Set<FlowNode> getNodeSet() {
193     Set<FlowNode> set = new HashSet<FlowNode>();
194     set.addAll(mapDescTupleToInferNode.values());
195     return set;
196   }
197
198   public MethodDescriptor getMethodDescriptor() {
199     return md;
200   }
201
202   public boolean isParamDesc(Descriptor desc) {
203
204     if (mapParamDescToIdx.containsKey(desc)) {
205       int idx = mapParamDescToIdx.get(desc);
206       if (!md.isStatic() && idx == 0) {
207         return false;
208       }
209       return true;
210     }
211
212     return false;
213   }
214
215   public boolean hasEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
216
217     FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);
218     FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple);
219
220     Set<FlowEdge> fromNodeOutEdgeSet = getOutEdgeSet(fromNode);
221     for (Iterator iterator = fromNodeOutEdgeSet.iterator(); iterator.hasNext();) {
222       FlowEdge flowEdge = (FlowEdge) iterator.next();
223       if (flowEdge.getDst().equals(toNode)) {
224         return true;
225       } else {
226         if (hasEdge(flowEdge.getDst().getDescTuple(), toDescTuple)) {
227           return true;
228         }
229       }
230     }
231
232     return false;
233   }
234
235   public Set<FlowEdge> getOutEdgeSetStartingFrom(FlowNode startNode) {
236
237     Descriptor prefixDesc = startNode.getCurrentDescTuple().get(0);
238
239     // returns the set of edges that share the same prefix of startNode
240     Set<FlowEdge> edgeSet = new HashSet<FlowEdge>();
241
242     for (Iterator<Set<FlowEdge>> iter = mapFlowNodeToOutEdgeSet.values().iterator(); iter.hasNext();) {
243       Set<FlowEdge> nodeEdgeSet = iter.next();
244       for (Iterator<FlowEdge> iter2 = nodeEdgeSet.iterator(); iter2.hasNext();) {
245         FlowEdge edge = iter2.next();
246         if (edge.getInitTuple().get(0).equals(prefixDesc)) {
247           edgeSet.add(edge);
248         }
249       }
250     }
251
252     return edgeSet;
253   }
254
255   public Set<FlowEdge> getOutEdgeSet(FlowNode node) {
256     if (!mapFlowNodeToOutEdgeSet.containsKey(node)) {
257       mapFlowNodeToOutEdgeSet.put(node, new HashSet<FlowEdge>());
258     }
259     return mapFlowNodeToOutEdgeSet.get(node);
260   }
261
262   public Set<FlowEdge> getInEdgeSet(FlowNode node) {
263     if (!mapFlowNodeToInEdgeSet.containsKey(node)) {
264       mapFlowNodeToInEdgeSet.put(node, new HashSet<FlowEdge>());
265     }
266     return mapFlowNodeToInEdgeSet.get(node);
267   }
268
269   public void addValueFlowEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
270
271     FlowNode fromNode = getFlowNode(fromDescTuple);
272     FlowNode toNode = getFlowNode(toDescTuple);
273
274     if (toNode.getDescTuple().get(0).equals(LocationInference.LITERALDESC)) {
275       return;
276     }
277
278     // System.out.println("create an edge from " + fromNode + " to " + toNode);
279
280     int fromTupleSize = fromDescTuple.size();
281     NTuple<Descriptor> curFromTuple = new NTuple<Descriptor>();
282     for (int i = 0; i < fromTupleSize; i++) {
283       Descriptor desc = fromDescTuple.get(i);
284       curFromTuple.add(desc);
285       int toTupleSize = toDescTuple.size();
286       NTuple<Descriptor> curToTuple = new NTuple<Descriptor>();
287       for (int k = 0; k < toTupleSize; k++) {
288         Descriptor toDesc = toDescTuple.get(k);
289         curToTuple.add(toDesc);
290         addFlowEdge(getFlowNode(curFromTuple), getFlowNode(curToTuple), fromDescTuple, toDescTuple);
291       }
292     }
293
294     // int fromTupleSize = fromDescTuple.size();
295     // NTuple<Descriptor> curTuple = new NTuple<Descriptor>();
296     // for (int i = 0; i < fromTupleSize; i++) {
297     // Descriptor desc = fromDescTuple.get(i);
298     // curTuple.add(desc);
299     // addFlowEdge(getFlowNode(curTuple), toNode, fromDescTuple, toDescTuple);
300     // }
301     //
302     // int toTupleSize = toDescTuple.size();
303     // curTuple = new NTuple<Descriptor>();
304     // for (int i = 0; i < toTupleSize; i++) {
305     // Descriptor desc = toDescTuple.get(i);
306     // curTuple.add(desc);
307     // addFlowEdge(fromNode, getFlowNode(curTuple), fromDescTuple, toDescTuple);
308     // }
309
310   }
311
312   private void addFlowEdge(FlowNode fromNode, FlowNode toNode, NTuple<Descriptor> initTuple,
313       NTuple<Descriptor> endTuple) {
314
315     FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
316     addOutEdge(fromNode, edge);
317     addInEdge(toNode, edge);
318
319     // System.out.println("add a new edge=" + edge);
320   }
321
322   private void addInEdge(FlowNode toNode, FlowEdge edge) {
323     getInEdgeSet(toNode).add(edge);
324   }
325
326   private void addOutEdge(FlowNode fromNode, FlowEdge edge) {
327     if (!mapFlowNodeToOutEdgeSet.containsKey(fromNode)) {
328       mapFlowNodeToOutEdgeSet.put(fromNode, new HashSet<FlowEdge>());
329     }
330     mapFlowNodeToOutEdgeSet.get(fromNode).add(edge);
331   }
332
333   public boolean contains(NTuple<Descriptor> descTuple) {
334     return mapDescTupleToInferNode.containsKey(descTuple);
335   }
336
337   public FlowNode getFlowNode(NTuple<Descriptor> descTuple) {
338     if (!mapDescTupleToInferNode.containsKey(descTuple)) {
339       FlowNode node = createNewFlowNode(descTuple);
340       mapDescTupleToInferNode.put(descTuple, node);
341     }
342     return mapDescTupleToInferNode.get(descTuple);
343   }
344
345   public FlowNode getThisVarNode() {
346     return thisVarNode;
347   }
348
349   public FlowNode createNewFlowNode(NTuple<Descriptor> tuple) {
350
351     // System.out.println("createNewFlowNode=" + tuple);
352     if (!mapDescTupleToInferNode.containsKey(tuple)) {
353       FlowNode node = new FlowNode(tuple);
354       mapDescTupleToInferNode.put(tuple, node);
355       // nodeSet.add(node);
356
357       mapLocTupleToFlowNode.put(getLocationTuple(node), node);
358
359       if (tuple.size() > 1) {
360         NTuple<Descriptor> baseTuple = tuple.subList(0, tuple.size() - 1);
361         getFlowNode(baseTuple).addFieldNode(node);
362       }
363
364       // System.out.println("Creating new node=" + node);
365       return node;
366     } else {
367       return mapDescTupleToInferNode.get(tuple);
368     }
369
370   }
371
372   public void addReturnFlowNode(NTuple<Descriptor> tuple) {
373
374     if (!mapDescTupleToInferNode.containsKey(tuple)) {
375       createNewFlowNode(tuple);
376     }
377
378     FlowNode node = mapDescTupleToInferNode.get(tuple);
379     returnNodeSet.add(node);
380   }
381
382   public Set<FlowNode> getReturnNodeSet() {
383     return returnNodeSet;
384   }
385
386   public Set<FlowNode> getLocalReachFlowNodeSetFrom(FlowNode fn) {
387     Set<FlowNode> set = new HashSet<FlowNode>();
388     recurLocalReachFlowNodeSet(fn, set);
389     return set;
390   }
391
392   private void recurLocalReachFlowNodeSet(FlowNode fn, Set<FlowNode> visited) {
393
394     Set<FlowEdge> outEdgeSet = getOutEdgeSet(fn);
395     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
396       FlowEdge edge = (FlowEdge) iterator.next();
397       FlowNode originalDstNode = edge.getDst();
398
399       Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
400       if (originalDstNode instanceof FlowReturnNode) {
401         FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
402         Set<NTuple<Descriptor>> rtupleSetFromRNode = rnode.getReturnTupleSet();
403         Set<NTuple<Descriptor>> rtupleSet = getReturnTupleSet(rtupleSetFromRNode);
404         for (Iterator iterator2 = rtupleSet.iterator(); iterator2.hasNext();) {
405           NTuple<Descriptor> rtuple = (NTuple<Descriptor>) iterator2.next();
406           dstNodeSet.add(getFlowNode(rtuple));
407         }
408       } else {
409         dstNodeSet.add(originalDstNode);
410       }
411
412       for (Iterator iterator2 = dstNodeSet.iterator(); iterator2.hasNext();) {
413         FlowNode dstNode = (FlowNode) iterator2.next();
414         if (!visited.contains(dstNode)) {
415           visited.add(dstNode);
416           recurLocalReachFlowNodeSet(dstNode, visited);
417         }
418       }
419
420     }
421
422   }
423
424   private void getReachFlowNodeSetFrom(FlowNode fn, Set<FlowNode> visited) {
425
426     Set<FlowEdge> outEdgeSet = getOutEdgeSet(fn);
427     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
428       FlowEdge edge = (FlowEdge) iterator.next();
429
430       if (fn.equals(getFlowNode(edge.getInitTuple()))) {
431         FlowNode dstNode = getFlowNode(edge.getEndTuple());
432         if (!visited.contains(dstNode)) {
433           visited.add(dstNode);
434           getReachFlowNodeSetFrom(dstNode, visited);
435         }
436       }
437     }
438
439   }
440
441   public Set<FlowNode> getReachFlowNodeSetFrom(FlowNode fn) {
442     Set<FlowNode> set = new HashSet<FlowNode>();
443     getReachFlowNodeSetFrom(fn, set);
444     return set;
445   }
446
447   public Set<FlowNode> getReachableSetFrom(NTuple<Descriptor> prefix) {
448     Set<FlowNode> reachableSet = new HashSet<FlowNode>();
449
450     Set<FlowNode> nodeSet = getNodeSet();
451     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
452       FlowNode originalSrcNode = (FlowNode) iterator.next();
453
454       Set<FlowNode> srcNodeSet = new HashSet<FlowNode>();
455       if (originalSrcNode instanceof FlowReturnNode) {
456         FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
457         Set<NTuple<Descriptor>> rtupleSetFromRNode = rnode.getReturnTupleSet();
458         Set<NTuple<Descriptor>> rtupleSet = getReturnTupleSet(rtupleSetFromRNode);
459         // System.out.println("#rnode=" + rnode + "  rtupleSet=" + rtupleSet);
460         for (Iterator iterator2 = rtupleSet.iterator(); iterator2.hasNext();) {
461           NTuple<Descriptor> rtuple = (NTuple<Descriptor>) iterator2.next();
462           if (rtuple.startsWith(prefix)) {
463             // System.out.println("rtuple=" + rtuple + "   give it to recur=" + originalSrcNode);
464             recurReachableSetFrom(originalSrcNode, reachableSet);
465           }
466         }
467       } else {
468         if (originalSrcNode.getCurrentDescTuple().startsWith(prefix)) {
469           recurReachableSetFrom(originalSrcNode, reachableSet);
470         }
471       }
472
473     }
474
475     return reachableSet;
476   }
477
478   public Set<NTuple<Descriptor>> getReturnTupleSet(Set<NTuple<Descriptor>> in) {
479
480     Set<NTuple<Descriptor>> normalTupleSet = new HashSet<NTuple<Descriptor>>();
481     for (Iterator iterator2 = in.iterator(); iterator2.hasNext();) {
482       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator2.next();
483       FlowNode tupleNode = getFlowNode(tuple);
484       if (tupleNode instanceof FlowReturnNode) {
485         normalTupleSet.addAll(getReturnTupleSet(((FlowReturnNode) tupleNode).getReturnTupleSet()));
486       } else {
487         normalTupleSet.add(tuple);
488       }
489     }
490     return normalTupleSet;
491   }
492
493   // private void getReachFlowNodeSetFrom(FlowNode fn, Set<FlowNode> visited) {
494   //
495   // for (Iterator iterator = fn.getOutEdgeSet().iterator();
496   // iterator.hasNext();) {
497   // FlowEdge edge = (FlowEdge) iterator.next();
498   //
499   // if (fn.equals(getFlowNode(edge.getInitTuple()))) {
500   //
501   // FlowNode dstNode = getFlowNode(edge.getEndTuple());
502   //
503   // if (!visited.contains(dstNode)) {
504   // visited.add(dstNode);
505   // getReachFlowNodeSetFrom(dstNode, visited);
506   // }
507   // }
508   // }
509   //
510   // }
511
512   private void recurReachableSetFrom(FlowNode curNode, Set<FlowNode> reachableSet) {
513
514     Set<FlowEdge> edgeSet = getOutEdgeSet(curNode);
515     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
516       FlowEdge edge = (FlowEdge) iterator.next();
517       FlowNode dstNode = getFlowNode(edge.getEndTuple());
518       if (!reachableSet.contains(dstNode)) {
519         reachableSet.add(dstNode);
520         recurReachableSetFrom(dstNode, reachableSet);
521       }
522     }
523
524   }
525
526   public Set<NTuple<Location>> getReachableFlowTupleSet(Set<NTuple<Location>> visited, FlowNode fn) {
527
528     Set<FlowEdge> outEdgeSet = getOutEdgeSet(fn);
529
530     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
531       FlowEdge edge = (FlowEdge) iterator.next();
532
533       if (fn.getDescTuple().equals(edge.getInitTuple())) {
534         FlowNode dstNode = getFlowNode(edge.getEndTuple());
535         NTuple<Location> dstTuple = getLocationTuple(dstNode);
536
537         if (!visited.contains(dstTuple)) {
538           visited.add(dstTuple);
539           visited.addAll(getReachableFlowTupleSet(visited, dstNode));
540         }
541
542       }
543     }
544     return visited;
545   }
546
547   public NTuple<Location> getLocationTuple(NTuple<Descriptor> descTuple) {
548     return getLocationTuple(getFlowNode(descTuple));
549   }
550
551   public NTuple<Location> getLocationTuple(FlowNode fn) {
552
553     if (!mapFlowNodeToLocTuple.containsKey(fn)) {
554       NTuple<Descriptor> descTuple = fn.getDescTuple();
555       NTuple<Location> locTuple = new NTuple<Location>();
556       ClassDescriptor cd = null;
557
558       Descriptor localDesc = fn.getDescTuple().get(0);
559
560       if (fn.isIntermediate() && fn.getDescTuple().size() == 1) {
561         Location interLoc = new Location(md, localDesc.getSymbol());
562         interLoc.setLocDescriptor(localDesc);
563         locTuple.add(interLoc);
564       } else if (localDesc.getSymbol().equals(SSJavaAnalysis.TOP)) {
565         Location topLoc = new Location(md, Location.TOP);
566         topLoc.setLocDescriptor(LocationInference.TOPDESC);
567         locTuple.add(topLoc);
568       } else if (localDesc.getSymbol().equals(LocationInference.GLOBALLOC)) {
569         Location globalLoc = new Location(md, LocationInference.GLOBALLOC);
570         globalLoc.setLocDescriptor(LocationInference.GLOBALDESC);
571         locTuple.add(globalLoc);
572       } else {
573         // normal case
574         for (int i = 0; i < descTuple.size(); i++) {
575           Descriptor curDesc = descTuple.get(i);
576           Location loc;
577           if (i == 0) {
578             loc = new Location(md, curDesc.getSymbol());
579             loc.setLocDescriptor(curDesc);
580             if (curDesc instanceof VarDescriptor) {
581               cd = ((VarDescriptor) curDesc).getType().getClassDesc();
582             } else if (curDesc instanceof InterDescriptor) {
583               cd = mapIntersectionDescToEnclosingDescriptor.get(curDesc);
584             } else {
585               // otherwise it should be the last element
586               cd = null;
587             }
588           } else {
589             loc = new Location(cd, curDesc.getSymbol());
590             loc.setLocDescriptor(curDesc);
591
592             if (curDesc instanceof FieldDescriptor) {
593               cd = ((FieldDescriptor) curDesc).getType().getClassDesc();
594             } else if (curDesc instanceof LocationDescriptor) {
595               cd = ((LocationDescriptor) curDesc).getEnclosingClassDesc();
596             } else {
597               // otherwise it should be the last element of the tuple
598               cd = null;
599             }
600
601           }
602           locTuple.add(loc);
603         }
604       }
605
606       mapFlowNodeToLocTuple.put(fn, locTuple);
607     }
608     return mapFlowNodeToLocTuple.get(fn);
609   }
610
611   public Set<FlowNode> getIncomingFlowNodeSet(FlowNode node) {
612     Set<FlowNode> set = new HashSet<FlowNode>();
613     getIncomingFlowNodeSet(node, set);
614     return set;
615   }
616
617   public void getIncomingFlowNodeSet(FlowNode node, Set<FlowNode> visited) {
618
619     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
620       FlowNode curNode = (FlowNode) iterator.next();
621       Set<FlowEdge> edgeSet = getOutEdgeSet(curNode);
622
623       for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
624         FlowEdge flowEdge = (FlowEdge) iterator2.next();
625
626         if (node.equals(getFlowNode(flowEdge.getEndTuple()))) {
627           FlowNode incomingNode = getFlowNode(flowEdge.getInitTuple());
628
629           if (incomingNode instanceof FlowReturnNode) {
630             FlowReturnNode rnode = (FlowReturnNode) incomingNode;
631             Set<NTuple<Descriptor>> nodeTupleSet = rnode.getReturnTupleSet();
632             Set<NTuple<Descriptor>> rtupleSet = getReturnTupleSet(nodeTupleSet);
633             for (Iterator iterator3 = rtupleSet.iterator(); iterator3.hasNext();) {
634               NTuple<Descriptor> nodeTuple = (NTuple<Descriptor>) iterator3.next();
635               FlowNode fn = getFlowNode(nodeTuple);
636               if (!visited.contains(fn)) {
637                 visited.add(fn);
638                 getIncomingFlowNodeSet(fn, visited);
639               }
640             }
641           } else {
642             if (!visited.contains(incomingNode)) {
643               visited.add(incomingNode);
644               getIncomingFlowNodeSet(incomingNode, visited);
645             }
646           }
647
648         }
649       }
650     }
651
652   }
653
654   public boolean isParameter(NTuple<Descriptor> tuple) {
655     // return true if a descriptor tuple is started with a parameter descriptor
656     Descriptor firstIdxDesc = tuple.get(0);
657     return mapParamDescToIdx.containsKey(firstIdxDesc);
658   }
659
660   public int getParamIdx(NTuple<Descriptor> tuple) {
661     Descriptor firstIdxDesc = tuple.get(0);
662     return mapParamDescToIdx.get(firstIdxDesc);
663   }
664
665   public FlowGraph clone() {
666     FlowGraph clone = new FlowGraph(md, mapParamDescToIdx);
667
668     // clone.setNodeSet(getNodeSet());
669     clone.setMapLocTupleToFlowNode(getMapLocTupleToFlowNode());
670     clone.setMapFlowNodeToLocTuple(getMapFlowNodeToLocTuple());
671     clone.setMapDescTupleToInferNode(getMapDescTupleToInferNode());
672
673     clone.setMapFlowNodeToOutEdgeSet(getMapFlowNodeToOutEdgeSet());
674     clone.setReturnNodeSet(getReturnNodeSet());
675     clone.setThisVarNode(getThisVarNode());
676
677     return clone;
678   }
679
680   public Map<FlowNode, NTuple<Location>> getMapFlowNodeToLocTuple() {
681     return mapFlowNodeToLocTuple;
682   }
683
684   public void setMapFlowNodeToLocTuple(Map<FlowNode, NTuple<Location>> in) {
685     this.mapFlowNodeToLocTuple.putAll(in);
686   }
687
688   public Map<FlowNode, Set<FlowEdge>> getMapFlowNodeToOutEdgeSet() {
689     return mapFlowNodeToOutEdgeSet;
690   }
691
692   public Set<FlowNode> getIncomingNodeSetByPrefix(Descriptor prefix) {
693
694     Set<FlowNode> incomingNodeSet = new HashSet<FlowNode>();
695
696     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
697       FlowNode curNode = (FlowNode) iterator.next();
698       Set<FlowEdge> outEdgeSet = getOutEdgeSet(curNode);
699
700       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
701         FlowEdge outEdge = (FlowEdge) iterator2.next();
702
703         if (outEdge.getEndTuple().startsWith(prefix)) {
704           incomingNodeSet.add(curNode);
705           recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
706
707         }
708
709       }
710     }
711
712     return incomingNodeSet;
713
714   }
715
716   private void recurIncomingNodeSetByPrefix(Descriptor prefix, FlowNode node, Set<FlowNode> visited) {
717
718     Set<FlowEdge> inEdgeSet = getInEdgeSet(node);
719
720     for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) {
721       FlowEdge inEdge = (FlowEdge) iterator.next();
722
723       FlowNode inNode = getFlowNode(inEdge.getInitTuple());
724       if (!inEdge.getInitTuple().startsWith(prefix) && !visited.contains(inNode)) {
725         visited.add(inNode);
726         recurIncomingNodeSetByPrefix(prefix, inNode, visited);
727       }
728     }
729
730   }
731
732   public void setMapFlowNodeToOutEdgeSet(Map<FlowNode, Set<FlowEdge>> inMap) {
733     Set<FlowNode> keySet = inMap.keySet();
734     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
735       FlowNode key = (FlowNode) iterator.next();
736       Set<FlowEdge> newEdgeSet = new HashSet<FlowEdge>();
737       newEdgeSet.addAll(inMap.get(key));
738       mapFlowNodeToOutEdgeSet.put(key, newEdgeSet);
739     }
740   }
741
742   private void drawEdges(FlowNode node, BufferedWriter bw, Set<FlowNode> addedNodeSet,
743       Set<FlowEdge> addedEdgeSet) throws IOException {
744
745     Set<FlowEdge> edgeSet = getOutEdgeSet(node);
746
747     for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
748       FlowEdge flowEdge = iterator.next();
749
750       FlowNode u = flowEdge.getSrc();
751       FlowNode v = flowEdge.getDst();
752
753       if (u.getDescTuple().equals(flowEdge.getInitTuple())
754           && v.getDescTuple().equals(flowEdge.getEndTuple())) {
755         // only draw an edge of the actual value flow
756
757         if (!addedEdgeSet.contains(flowEdge)) {
758
759           if (!addedNodeSet.contains(u)) {
760             drawNode(u, bw);
761             addedNodeSet.add(u);
762           }
763           if (!addedNodeSet.contains(v)) {
764             drawNode(v, bw);
765             addedNodeSet.add(v);
766           }
767
768           bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
769           addedEdgeSet.add(flowEdge);
770         }
771       }
772
773     }
774
775   }
776
777   private void drawNode(FlowNode node, BufferedWriter bw) throws IOException {
778     if (node instanceof FlowReturnNode) {
779       FlowReturnNode rnode = (FlowReturnNode) node;
780       bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
781     } else {
782       bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
783     }
784
785   }
786
787   public void writeGraph() throws java.io.IOException {
788     writeGraph("");
789   }
790
791   public void writeGraph(String suffix) throws java.io.IOException {
792
793     String graphName = "flowgraph_" + md.toString() + suffix;
794     graphName = graphName.replaceAll("[\\W]", "");
795
796     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
797     bw.write("digraph " + graphName + " {\n");
798     bw.write("compound=true;\n");
799
800     // then visit every flow node
801
802     // Iterator<FlowNode> iter = nodeSet.iterator();
803     Iterator<FlowNode> iter = getNodeSet().iterator();
804
805     Set<FlowEdge> addedEdgeSet = new HashSet<FlowEdge>();
806     Set<FlowNode> addedNodeSet = new HashSet<FlowNode>();
807
808     while (iter.hasNext()) {
809       FlowNode node = iter.next();
810
811       if (node.getDescTuple().size() == 1) {
812         // here, we just care about the local variable
813         if (node.getFieldNodeSet().size() > 0) {
814           drawSubgraph(node, bw, addedEdgeSet);
815         }
816       }
817       drawEdges(node, bw, addedNodeSet, addedEdgeSet);
818
819     }
820
821     bw.write("}\n");
822     bw.close();
823
824   }
825
826   public boolean constainsNode(FlowNode node) {
827     return getNodeSet().contains(node);
828   }
829
830   private void drawSubgraph(FlowNode node, BufferedWriter bw, Set<FlowEdge> addedSet)
831       throws IOException {
832
833     bw.write("subgraph cluster_" + node.getID() + "{\n");
834     bw.write("label=\"" + node.getPrettyID() + "\";\n");
835
836     Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
837     for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
838       FlowNode fieldNode = (FlowNode) iterator.next();
839       if (fieldNode.getFieldNodeSet().size() > 0) {
840         drawSubgraph(fieldNode, bw, addedSet);
841       } else {
842         Descriptor desc = fieldNode.getDescTuple().getLastElement();
843         if (desc instanceof VarDescriptor) {
844           VarDescriptor varDesc = (VarDescriptor) desc;
845           if (varDesc.getType().isPrimitive()) {
846             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
847           }
848         } else if (desc instanceof FieldDescriptor) {
849           FieldDescriptor fieldDesc = (FieldDescriptor) desc;
850           if (fieldDesc.getType().isPrimitive()) {
851             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
852           }
853         }
854       }
855     }
856
857     bw.write("}\n");
858   }
859
860   public void removeEdge(NTuple<Descriptor> from, NTuple<Descriptor> to) {
861
862     Set<FlowEdge> toberemoved = new HashSet<FlowEdge>();
863     Set<FlowEdge> edgeSet = getOutEdgeSet(getFlowNode(from));
864
865     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
866       FlowEdge flowEdge = (FlowEdge) iterator.next();
867       if (flowEdge.getInitTuple().equals(from) && flowEdge.getEndTuple().equals(to)) {
868         toberemoved.add(flowEdge);
869       }
870     }
871
872     edgeSet.removeAll(toberemoved);
873
874   }
875
876   public void updateTuple(FlowNode node, NTuple<Descriptor> newTuple) {
877
878     NTuple<Descriptor> curTuple = node.getCurrentDescTuple();
879     Set<FlowEdge> inEdgeSet = getInEdgeSet(node);
880     for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) {
881       FlowEdge flowEdge = (FlowEdge) iterator.next();
882       if (flowEdge.getEndTuple().equals(curTuple)) {
883         flowEdge.setEndTuple(newTuple);
884       }
885     }
886
887     Set<FlowEdge> outEdgeSet = getOutEdgeSet(node);
888     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
889       FlowEdge flowEdge = (FlowEdge) iterator.next();
890       if (flowEdge.getInitTuple().equals(curTuple)) {
891         flowEdge.setInitTuple(newTuple);
892       }
893     }
894
895     node.setBaseTuple(newTuple);
896
897   }
898
899   public void removeNode(FlowNode node) {
900
901     NTuple<Descriptor> tuple = node.getCurrentDescTuple();
902
903     Set<FlowEdge> inEdgeSet = getInEdgeSet(node);
904     for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) {
905       FlowEdge flowEdge = (FlowEdge) iterator.next();
906       if (flowEdge.getEndTuple().equals(tuple)) {
907
908         Set<FlowEdge> outSet = getOutEdgeSet(getFlowNode(flowEdge.getInitTuple()));
909         Set<FlowEdge> toberemoved = new HashSet<FlowEdge>();
910         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
911           FlowEdge outEdge = (FlowEdge) iterator2.next();
912           if (outEdge.getEndTuple().equals(tuple)) {
913             toberemoved.add(outEdge);
914           }
915         }
916         outSet.removeAll(toberemoved);
917       }
918     }
919
920     Set<FlowEdge> outEdgeSet = getOutEdgeSet(node);
921     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
922       FlowEdge flowEdge = (FlowEdge) iterator.next();
923       if (flowEdge.getInitTuple().equals(tuple)) {
924
925         Set<FlowEdge> inSet = getInEdgeSet(getFlowNode(flowEdge.getEndTuple()));
926         Set<FlowEdge> toberemoved = new HashSet<FlowEdge>();
927         for (Iterator iterator2 = inSet.iterator(); iterator2.hasNext();) {
928           FlowEdge inEdge = (FlowEdge) iterator2.next();
929           if (inEdge.getInitTuple().equals(tuple)) {
930             toberemoved.add(inEdge);
931           }
932         }
933         inSet.removeAll(toberemoved);
934       }
935     }
936
937     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
938       FlowNode flowNode = (FlowNode) iterator.next();
939       Set<FlowEdge> outSet = getOutEdgeSet(flowNode);
940       Set<FlowEdge> toberemoved = new HashSet<FlowEdge>();
941       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
942         FlowEdge flowEdge = (FlowEdge) iterator2.next();
943         if (flowEdge.getInitTuple().equals(tuple) || flowEdge.getEndTuple().equals(tuple)) {
944           toberemoved.add(flowEdge);
945         }
946       }
947       outSet.removeAll(toberemoved);
948     }
949
950     mapFlowNodeToOutEdgeSet.remove(node);
951     mapFlowNodeToInEdgeSet.remove(node);
952     System.out.println("REMOVING NODE=" + mapDescTupleToInferNode.get(tuple) + " from tuple="
953         + tuple);
954     mapDescTupleToInferNode.remove(tuple);
955     System.out.println("mapDescTupleToInferNode=" + mapDescTupleToInferNode);
956   }
957 }