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