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