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