Robust/src/Analysis/Pointer/Graph.java

   1 package Analysis.Pointer;
   2 import java.util.*;
   3 import Analysis.Disjoint.PointerMethod;
   4 import Analysis.Pointer.AllocFactory.AllocNode;
   5 import IR.Flat.*;
   6 import IR.MethodDescriptor;
   7 import java.io.PrintWriter;
   8
   9 public class Graph {
  10   /* This is field is set is this Graph is just a delta on the parent
  11    * graph. */
  12
  13   Graph parent;
  14   HashMap<AllocNode, MySet<Edge>> nodeMap;
  15   HashMap<TempDescriptor, MySet<Edge>> varMap;
  16   HashMap<AllocNode, MySet<Edge>> backMap;
  17   MySet<Edge> strongUpdateSet;
  18   HashMap<AllocNode, MySet<Edge>> callNewEdges;
  19   HashMap<Edge, MySet<Edge>> callOldEdges;
  20
  21   public void addCallEdge(Edge e) {
  22     MySet<Edge> eset;
  23     if ((eset=callNewEdges.get(e.src))==null) {
  24       eset=new MySet<Edge>();
  25       callNewEdges.put(e.src, eset);
  26     }
  27     if (eset.contains(e)) {
  28       e=e.merge(eset.get(e));
  29     }
  30     eset.add(e);
  31
  32     if ((eset=callNewEdges.get(e.dst))==null) {
  33       eset=new MySet<Edge>();
  34       callNewEdges.put(e.dst, eset);
  35     }
  36     if (eset.contains(e)) {
  37       e=e.merge(eset.get(e));
  38     }
  39     eset.add(e);
  40   }
  41
  42   public void check() {
  43     for(Map.Entry<AllocNode, MySet<Edge>> entry:nodeMap.entrySet()) {
  44       AllocNode node=entry.getKey();
  45       if (node==null)
  46         throw new Error("Null node key");
  47       for(Edge e:entry.getValue())
  48         if (e.src!=node)
  49           throw new Error();
  50     }
  51     for(Map.Entry<TempDescriptor, MySet<Edge>> entry:varMap.entrySet()) {
  52       TempDescriptor tmp=entry.getKey();
  53       if (tmp==null)
  54         throw new Error("Null tmp key");
  55       for(Edge e:entry.getValue())
  56         if (e.srcvar!=tmp)
  57           throw new Error();
  58     }
  59   }
  60
  61   /* Need this information for mapping in callee results */
  62   MySet<Edge> reachEdge;
  63   HashSet<AllocNode> reachNode;
  64   MySet<Edge> externalEdgeSet;
  65   /* These edges were created by the caller */
  66   MySet<Edge> callerEdges;
  67
  68   /* Need this information for mapping in callee results */
  69   HashSet<AllocNode> nodeAges;
  70   HashMap<AllocNode, Boolean> oldNodes;
  71
  72   /* Need this information for mapping in callee results */
  73   HashSet<AllocNode> callNodeAges;
  74   HashSet<AllocNode> callOldNodes;
  75   HashSet<MethodDescriptor> callTargets;
  76
  77   public Graph(Graph parent) {
  78     nodeMap=new HashMap<AllocNode, MySet<Edge>>();
  79     varMap=new HashMap<TempDescriptor, MySet<Edge>>();
  80     nodeAges=new HashSet<AllocNode>();
  81     oldNodes=new HashMap<AllocNode, Boolean>();
  82     this.parent=parent;
  83   }
  84
  85   public MySet<Edge> getBackEdges(AllocNode node) {
  86     MySet<Edge> edgeset=new MySet<Edge>();
  87     edgeset.addAll(backMap.get(node));
  88     edgeset.addAll(parent.backMap.get(node));
  89     return edgeset;
  90   }
  91
  92   public boolean containsNode(AllocNode node) {
  93     return nodeAges.contains(node)||parent!=null&&parent.nodeAges.contains(node);
  94   }
  95
  96   public Edge getMatch(Edge old) {
  97     if (old.srcvar!=null) {
  98       MySet<Edge> edges=varMap.get(old.srcvar);
  99       if (edges==null)
 100         edges=parent.varMap.get(old.srcvar);
 101       if (edges==null)
 102         return null;
 103       return edges.get(old);
 104     } else {
 105       MySet<Edge> edges=nodeMap.get(old.src);
 106       if (edges==null)
 107         edges=parent.nodeMap.get(old.src);
 108       if (edges==null)
 109         return null;
 110       return edges.get(old);
 111     }
 112   }
 113
 114   public MySet<Edge> getEdges(TempDescriptor tmp) {
 115     if (varMap.containsKey(tmp))
 116       return varMap.get(tmp);
 117     else if (parent!=null&&parent.varMap.containsKey(tmp))
 118       return parent.varMap.get(tmp);
 119     else return emptySet;
 120   }
 121
 122   public MySet<Edge> getEdges(AllocNode node) {
 123     if (nodeMap.containsKey(node))
 124       return nodeMap.get(node);
 125     else if (parent!=null&&parent.nodeMap.containsKey(node))
 126       return parent.nodeMap.get(node);
 127     else return emptySet;
 128   }
 129
 130   public static MySet<Edge> emptySet=new MySet<Edge>(true);
 131
 132   public void printGraph(PrintWriter output, String name) {
 133     output.println("digraph \""+name+"\" {");
 134     output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 135     output.println("\tedge [fontsize=6];");
 136     outputTempEdges(output, varMap, null);
 137     if (parent!=null)
 138       outputTempEdges(output, parent.varMap, varMap);
 139     outputHeapEdges(output, nodeMap, null);
 140     if (parent!=null)
 141       outputHeapEdges(output, parent.nodeMap, nodeMap);
 142     output.println("}\n");
 143   }
 144
 145   private void outputTempEdges(PrintWriter output, HashMap<TempDescriptor, MySet<Edge>> varMap,
 146                                HashMap<TempDescriptor, MySet<Edge>> childvarMap) {
 147     for(Map.Entry<TempDescriptor, MySet<Edge>> entry:varMap.entrySet()) {
 148       TempDescriptor tmp=entry.getKey();
 149       if (childvarMap!=null&&childvarMap.containsKey(tmp))
 150         continue;
 151       output.println(tmp.getSymbol()+"[shape=rectangle];");
 152       for(Edge e:entry.getValue()) {
 153         if (e.srcvar!=tmp)
 154           throw new Error(e.srcvar +" is not equal to "+tmp);
 155         AllocNode n=e.dst;
 156         output.println("\t"+tmp.getSymbol()+"->"+n.getID()+"[label=\""+e.taintString()+"\"];");
 157       }
 158     }
 159   }
 160
 161   private void outputHeapEdges(PrintWriter output, HashMap<AllocNode, MySet<Edge>> nodeMap,
 162                                HashMap<AllocNode, MySet<Edge>> childNodeMap) {
 163     for(Map.Entry<AllocNode, MySet<Edge>> entry:nodeMap.entrySet()) {
 164       AllocNode node=entry.getKey();
 165       if (childNodeMap!=null&&childNodeMap.containsKey(node))
 166         continue;
 167       for(Edge e:entry.getValue()) {
 168         if (e.src!=node)
 169           throw new Error(e.src+" is not equal to "+node);
 170         AllocNode n=e.dst;
 171         String src=node.getID();
 172         String dst=n.getID();
 173         String field=e.fd!=null?e.fd.getSymbol():"[]";
 174         String taint=e.taints!=null?":"+e.taintString():"";
 175         output.println("\t"+src+"->"+dst+"[label=\""+field+" "+taint+"\"];");
 176       }
 177     }
 178   }
 179 }