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 originalDstNode = edge.getDst();
 387
 388       Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
 389       if (originalDstNode instanceof FlowReturnNode) {
 390         FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
 391         Set<NTuple<Descriptor>> rtupleSet = rnode.getReturnTupleSet();
 392         for (Iterator iterator2 = rtupleSet.iterator(); iterator2.hasNext();) {
 393           NTuple<Descriptor> rtuple = (NTuple<Descriptor>) iterator2.next();
 394           dstNodeSet.add(getFlowNode(rtuple));
 395         }
 396       } else {
 397         dstNodeSet.add(originalDstNode);
 398       }
 399
 400       for (Iterator iterator2 = dstNodeSet.iterator(); iterator2.hasNext();) {
 401         FlowNode dstNode = (FlowNode) iterator2.next();
 402         if (!visited.contains(dstNode)) {
 403           visited.add(dstNode);
 404           recurLocalReachFlowNodeSet(dstNode, visited);
 405         }
 406       }
 407
 408     }
 409
 410   }
 411
 412   private void getReachFlowNodeSetFrom(FlowNode fn, Set<FlowNode> visited) {
 413
 414     Set<FlowEdge> outEdgeSet = getOutEdgeSet(fn);
 415     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
 416       FlowEdge edge = (FlowEdge) iterator.next();
 417
 418       if (fn.equals(getFlowNode(edge.getInitTuple()))) {
 419         FlowNode dstNode = getFlowNode(edge.getEndTuple());
 420         if (!visited.contains(dstNode)) {
 421           visited.add(dstNode);
 422           getReachFlowNodeSetFrom(dstNode, visited);
 423         }
 424       }
 425     }
 426
 427   }
 428
 429   public Set<FlowNode> getReachFlowNodeSetFrom(FlowNode fn) {
 430     Set<FlowNode> set = new HashSet<FlowNode>();
 431     getReachFlowNodeSetFrom(fn, set);
 432     return set;
 433   }
 434
 435   public Set<FlowNode> getReachableSetFrom(NTuple<Descriptor> prefix) {
 436     Set<FlowNode> reachableSet = new HashSet<FlowNode>();
 437
 438     Set<FlowNode> nodeSet = getNodeSet();
 439     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 440       FlowNode originalSrcNode = (FlowNode) iterator.next();
 441
 442       Set<FlowNode> srcNodeSet = new HashSet<FlowNode>();
 443       if (originalSrcNode instanceof FlowReturnNode) {
 444         FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
 445         Set<NTuple<Descriptor>> rtupleSet = rnode.getReturnTupleSet();
 446         for (Iterator iterator2 = rtupleSet.iterator(); iterator2.hasNext();) {
 447           NTuple<Descriptor> rtuple = (NTuple<Descriptor>) iterator2.next();
 448           if (rtuple.startsWith(prefix)) {
 449             System.out.println("rtuple=" + rtuple + "   give it to recur=" + originalSrcNode);
 450             recurReachableSetFrom(originalSrcNode, reachableSet);
 451           }
 452         }
 453       } else {
 454         if (originalSrcNode.getCurrentDescTuple().startsWith(prefix)) {
 455           recurReachableSetFrom(originalSrcNode, reachableSet);
 456         }
 457       }
 458
 459     }
 460
 461     return reachableSet;
 462   }
 463
 464   // private void getReachFlowNodeSetFrom(FlowNode fn, Set<FlowNode> visited) {
 465   //
 466   // for (Iterator iterator = fn.getOutEdgeSet().iterator();
 467   // iterator.hasNext();) {
 468   // FlowEdge edge = (FlowEdge) iterator.next();
 469   //
 470   // if (fn.equals(getFlowNode(edge.getInitTuple()))) {
 471   //
 472   // FlowNode dstNode = getFlowNode(edge.getEndTuple());
 473   //
 474   // if (!visited.contains(dstNode)) {
 475   // visited.add(dstNode);
 476   // getReachFlowNodeSetFrom(dstNode, visited);
 477   // }
 478   // }
 479   // }
 480   //
 481   // }
 482
 483   private void recurReachableSetFrom(FlowNode curNode, Set<FlowNode> reachableSet) {
 484
 485     Set<FlowEdge> edgeSet = getOutEdgeSet(curNode);
 486     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 487       FlowEdge edge = (FlowEdge) iterator.next();
 488       FlowNode dstNode = getFlowNode(edge.getEndTuple());
 489       if (!reachableSet.contains(dstNode)) {
 490         reachableSet.add(dstNode);
 491         recurReachableSetFrom(dstNode, reachableSet);
 492       }
 493     }
 494
 495   }
 496
 497   public Set<NTuple<Location>> getReachableFlowTupleSet(Set<NTuple<Location>> visited, FlowNode fn) {
 498
 499     Set<FlowEdge> outEdgeSet = getOutEdgeSet(fn);
 500
 501     for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) {
 502       FlowEdge edge = (FlowEdge) iterator.next();
 503
 504       if (fn.getDescTuple().equals(edge.getInitTuple())) {
 505         FlowNode dstNode = getFlowNode(edge.getEndTuple());
 506         NTuple<Location> dstTuple = getLocationTuple(dstNode);
 507
 508         if (!visited.contains(dstTuple)) {
 509           visited.add(dstTuple);
 510           visited.addAll(getReachableFlowTupleSet(visited, dstNode));
 511         }
 512
 513       }
 514     }
 515     return visited;
 516   }
 517
 518   public NTuple<Location> getLocationTuple(NTuple<Descriptor> descTuple) {
 519     return getLocationTuple(getFlowNode(descTuple));
 520   }
 521
 522   public NTuple<Location> getLocationTuple(FlowNode fn) {
 523
 524     if (!mapFlowNodeToLocTuple.containsKey(fn)) {
 525       NTuple<Descriptor> descTuple = fn.getDescTuple();
 526       NTuple<Location> locTuple = new NTuple<Location>();
 527       ClassDescriptor cd = null;
 528
 529       Descriptor localDesc = fn.getDescTuple().get(0);
 530
 531       if (fn.isIntermediate()) {
 532         Location interLoc = new Location(md, localDesc.getSymbol());
 533         interLoc.setLocDescriptor(localDesc);
 534         locTuple.add(interLoc);
 535       } else if (localDesc.getSymbol().equals(SSJavaAnalysis.TOP)) {
 536         Location topLoc = new Location(md, Location.TOP);
 537         topLoc.setLocDescriptor(LocationInference.TOPDESC);
 538         locTuple.add(topLoc);
 539       } else if (localDesc.getSymbol().equals(LocationInference.GLOBALLOC)) {
 540         Location globalLoc = new Location(md, LocationInference.GLOBALLOC);
 541         globalLoc.setLocDescriptor(LocationInference.GLOBALDESC);
 542         locTuple.add(globalLoc);
 543       } else {
 544         // normal case
 545         for (int i = 0; i < descTuple.size(); i++) {
 546           Descriptor curDesc = descTuple.get(i);
 547           Location loc;
 548           if (i == 0) {
 549             loc = new Location(md, curDesc.getSymbol());
 550             loc.setLocDescriptor(curDesc);
 551             if (curDesc instanceof VarDescriptor) {
 552               cd = ((VarDescriptor) curDesc).getType().getClassDesc();
 553             } else {
 554               // otherwise it should be the last element
 555               cd = null;
 556             }
 557           } else {
 558             loc = new Location(cd, curDesc.getSymbol());
 559             loc.setLocDescriptor(curDesc);
 560
 561             if (curDesc instanceof FieldDescriptor) {
 562               cd = ((FieldDescriptor) curDesc).getType().getClassDesc();
 563             } else if (curDesc instanceof LocationDescriptor) {
 564               cd = ((LocationDescriptor) curDesc).getEnclosingClassDesc();
 565             } else {
 566               // otherwise it should be the last element of the tuple
 567               cd = null;
 568             }
 569
 570           }
 571           locTuple.add(loc);
 572         }
 573       }
 574
 575       mapFlowNodeToLocTuple.put(fn, locTuple);
 576     }
 577     return mapFlowNodeToLocTuple.get(fn);
 578   }
 579
 580   public Set<FlowNode> getIncomingFlowNodeSet(FlowNode node) {
 581     Set<FlowNode> set = new HashSet<FlowNode>();
 582     getIncomingFlowNodeSet(node, set);
 583     return set;
 584   }
 585
 586   public void getIncomingFlowNodeSet(FlowNode node, Set<FlowNode> visited) {
 587
 588     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 589       FlowNode curNode = (FlowNode) iterator.next();
 590       Set<FlowEdge> edgeSet = getOutEdgeSet(curNode);
 591
 592       for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
 593         FlowEdge flowEdge = (FlowEdge) iterator2.next();
 594
 595         if (node.equals(getFlowNode(flowEdge.getEndTuple()))) {
 596           FlowNode incomingNode = getFlowNode(flowEdge.getInitTuple());
 597
 598           if (incomingNode instanceof FlowReturnNode) {
 599             FlowReturnNode rnode = (FlowReturnNode) incomingNode;
 600             Set<NTuple<Descriptor>> nodeTupleSet = rnode.getReturnTupleSet();
 601             for (Iterator iterator3 = nodeTupleSet.iterator(); iterator3.hasNext();) {
 602               NTuple<Descriptor> nodeTuple = (NTuple<Descriptor>) iterator3.next();
 603               FlowNode fn = getFlowNode(nodeTuple);
 604               if (!visited.contains(fn)) {
 605                 visited.add(fn);
 606                 getIncomingFlowNodeSet(fn, visited);
 607               }
 608             }
 609           } else {
 610             if (!visited.contains(incomingNode)) {
 611               visited.add(incomingNode);
 612               getIncomingFlowNodeSet(incomingNode, visited);
 613             }
 614           }
 615
 616         }
 617       }
 618     }
 619
 620   }
 621
 622   public boolean isParameter(NTuple<Descriptor> tuple) {
 623     // return true if a descriptor tuple is started with a parameter descriptor
 624     Descriptor firstIdxDesc = tuple.get(0);
 625     return mapParamDescToIdx.containsKey(firstIdxDesc);
 626   }
 627
 628   public int getParamIdx(NTuple<Descriptor> tuple) {
 629     Descriptor firstIdxDesc = tuple.get(0);
 630     return mapParamDescToIdx.get(firstIdxDesc);
 631   }
 632
 633   public FlowGraph clone() {
 634     FlowGraph clone = new FlowGraph(md, mapParamDescToIdx);
 635
 636     // clone.setNodeSet(getNodeSet());
 637     clone.setMapLocTupleToFlowNode(getMapLocTupleToFlowNode());
 638     clone.setMapFlowNodeToLocTuple(getMapFlowNodeToLocTuple());
 639     clone.setMapDescTupleToInferNode(getMapDescTupleToInferNode());
 640
 641     clone.setMapFlowNodeToOutEdgeSet(getMapFlowNodeToOutEdgeSet());
 642     clone.setReturnNodeSet(getReturnNodeSet());
 643     clone.setThisVarNode(getThisVarNode());
 644
 645     return clone;
 646   }
 647
 648   public Map<FlowNode, NTuple<Location>> getMapFlowNodeToLocTuple() {
 649     return mapFlowNodeToLocTuple;
 650   }
 651
 652   public void setMapFlowNodeToLocTuple(Map<FlowNode, NTuple<Location>> in) {
 653     this.mapFlowNodeToLocTuple.putAll(in);
 654   }
 655
 656   public Map<FlowNode, Set<FlowEdge>> getMapFlowNodeToOutEdgeSet() {
 657     return mapFlowNodeToOutEdgeSet;
 658   }
 659
 660   public Set<FlowNode> getIncomingNodeSetByPrefix(Descriptor prefix) {
 661
 662     Set<FlowNode> incomingNodeSet = new HashSet<FlowNode>();
 663
 664     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 665       FlowNode curNode = (FlowNode) iterator.next();
 666       Set<FlowEdge> outEdgeSet = getOutEdgeSet(curNode);
 667
 668       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
 669         FlowEdge outEdge = (FlowEdge) iterator2.next();
 670
 671         if (outEdge.getEndTuple().startsWith(prefix)) {
 672           incomingNodeSet.add(curNode);
 673           recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
 674
 675         }
 676
 677       }
 678     }
 679
 680     return incomingNodeSet;
 681
 682   }
 683
 684   private void recurIncomingNodeSetByPrefix(Descriptor prefix, FlowNode node, Set<FlowNode> visited) {
 685
 686     Set<FlowEdge> inEdgeSet = getInEdgeSet(node);
 687
 688     for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) {
 689       FlowEdge inEdge = (FlowEdge) iterator.next();
 690
 691       FlowNode inNode = getFlowNode(inEdge.getInitTuple());
 692       if (!inEdge.getInitTuple().startsWith(prefix) && !visited.contains(inNode)) {
 693         visited.add(inNode);
 694         recurIncomingNodeSetByPrefix(prefix, inNode, visited);
 695       }
 696     }
 697
 698   }
 699
 700   public void setMapFlowNodeToOutEdgeSet(Map<FlowNode, Set<FlowEdge>> inMap) {
 701     Set<FlowNode> keySet = inMap.keySet();
 702     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 703       FlowNode key = (FlowNode) iterator.next();
 704       Set<FlowEdge> newEdgeSet = new HashSet<FlowEdge>();
 705       newEdgeSet.addAll(inMap.get(key));
 706       mapFlowNodeToOutEdgeSet.put(key, newEdgeSet);
 707     }
 708   }
 709
 710   private void drawEdges(FlowNode node, BufferedWriter bw, Set<FlowNode> addedNodeSet,
 711       Set<FlowEdge> addedEdgeSet) throws IOException {
 712
 713     Set<FlowEdge> edgeSet = getOutEdgeSet(node);
 714
 715     for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
 716       FlowEdge flowEdge = iterator.next();
 717
 718       FlowNode u = flowEdge.getSrc();
 719       FlowNode v = flowEdge.getDst();
 720
 721       if (u.getDescTuple().equals(flowEdge.getInitTuple())
 722           && v.getDescTuple().equals(flowEdge.getEndTuple())) {
 723         // only draw an edge of the actual value flow
 724
 725         if (!addedEdgeSet.contains(flowEdge)) {
 726
 727           if (!addedNodeSet.contains(u)) {
 728             drawNode(u, bw);
 729             addedNodeSet.add(u);
 730           }
 731           if (!addedNodeSet.contains(v)) {
 732             drawNode(v, bw);
 733             addedNodeSet.add(v);
 734           }
 735
 736           bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
 737           addedEdgeSet.add(flowEdge);
 738         }
 739       }
 740
 741     }
 742
 743   }
 744
 745   private void drawNode(FlowNode node, BufferedWriter bw) throws IOException {
 746     if (node instanceof FlowReturnNode) {
 747       FlowReturnNode rnode = (FlowReturnNode) node;
 748       bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 749     } else {
 750       bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 751     }
 752
 753   }
 754
 755   public void writeGraph() throws java.io.IOException {
 756     writeGraph("");
 757   }
 758
 759   public void writeGraph(String suffix) throws java.io.IOException {
 760
 761     String graphName = "flowgraph_" + md.toString() + suffix;
 762     graphName = graphName.replaceAll("[\\W]", "");
 763
 764     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 765     bw.write("digraph " + graphName + " {\n");
 766     bw.write("compound=true;\n");
 767
 768     // then visit every flow node
 769
 770     // Iterator<FlowNode> iter = nodeSet.iterator();
 771     Iterator<FlowNode> iter = getNodeSet().iterator();
 772
 773     Set<FlowEdge> addedEdgeSet = new HashSet<FlowEdge>();
 774     Set<FlowNode> addedNodeSet = new HashSet<FlowNode>();
 775
 776     while (iter.hasNext()) {
 777       FlowNode node = iter.next();
 778
 779       if (node.getDescTuple().size() == 1) {
 780         // here, we just care about the local variable
 781         if (node.getFieldNodeSet().size() > 0) {
 782           drawSubgraph(node, bw, addedEdgeSet);
 783         }
 784       }
 785       drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 786
 787     }
 788
 789     bw.write("}\n");
 790     bw.close();
 791
 792   }
 793
 794   public boolean constainsNode(FlowNode node) {
 795     return getNodeSet().contains(node);
 796   }
 797
 798   private void drawSubgraph(FlowNode node, BufferedWriter bw, Set<FlowEdge> addedSet)
 799       throws IOException {
 800
 801     bw.write("subgraph cluster_" + node.getID() + "{\n");
 802     bw.write("label=\"" + node.getPrettyID() + "\";\n");
 803
 804     Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
 805     for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
 806       FlowNode fieldNode = (FlowNode) iterator.next();
 807       if (fieldNode.getFieldNodeSet().size() > 0) {
 808         drawSubgraph(fieldNode, bw, addedSet);
 809       } else {
 810         Descriptor desc = fieldNode.getDescTuple().getLastElement();
 811         if (desc instanceof VarDescriptor) {
 812           VarDescriptor varDesc = (VarDescriptor) desc;
 813           if (varDesc.getType().isPrimitive()) {
 814             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
 815           }
 816         } else if (desc instanceof FieldDescriptor) {
 817           FieldDescriptor fieldDesc = (FieldDescriptor) desc;
 818           if (fieldDesc.getType().isPrimitive()) {
 819             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
 820           }
 821         }
 822       }
 823     }
 824
 825     bw.write("}\n");
 826   }
 827
 828 }