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