Robust/src/Analysis/SSJava/FlowGraph.java

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