View Javadoc

1   /*
2    * Created on Sep 25, 2003
3    *
4    * To change the template for this generated file go to
5    * Window>Preferences>Java>Code Generation>Code and Comments
6    */
7   package joeq.Compiler.Analysis.IPSSA;
8   
9   import java.util.HashMap;
10  import java.util.HashSet;
11  import java.util.Iterator;
12  import java.util.LinkedList;
13  import java.util.Set;
14  import java.io.PrintStream;
15  import joeq.Compiler.Analysis.IPSSA.Utils.IteratorHelper;
16  import jwutil.collections.LinearSet;
17  import jwutil.util.Assert;
18  
19  /***
20   * This is a graph consisting of definitions that uses as much sharing as possible.
21   * 
22   * Provides a dot printer.
23   * 
24   *  @author V.Benjamin Livshits
25   */
26  public abstract class DefinitionGraph {
27      private HashSet _nodes;
28      protected int   _edgeCount = 0;
29  
30      public DefinitionGraph(){
31          _nodes = new HashSet();        
32      }
33      
34      protected void addNode(SSADefinition def){
35          _nodes.add(def);        // duplicates don't matter
36      }
37      
38      public int getEdgeCount(){return _edgeCount;}
39      public int getNodeCount(){return _nodes.size();}
40      
41      public abstract void    addEdge(SSADefinition def1, SSADefinition def2, EdgeInfo ei);
42      public abstract boolean isRootNode(SSADefinition def);
43      public abstract boolean isTerminalNode(SSADefinition def);
44      
45      /*** Retrieves all roots of the forest that we are constructing */
46      public Set getRoots(){
47          LinearSet set = new LinearSet();
48          for(Iterator iter = _nodes.iterator(); iter.hasNext();){
49              SSADefinition def = (SSADefinition)iter.next();
50              
51              if(isRootNode(def)){
52                  set.add(def);
53              }
54          }
55          return set;
56      }
57      
58      public Set getTerminals(){
59          LinearSet set = new LinearSet();
60          for(Iterator iter = _nodes.iterator(); iter.hasNext();){
61              SSADefinition def = (SSADefinition)iter.next();
62          
63              if(isTerminalNode(def)){
64                  set.add(def);
65              }
66          }
67          return set;
68      }
69  
70      /// Forward links
71      public abstract SSAIterator.DefinitionIterator getReached(SSADefinition def);    
72      /*** All reaching definitions */
73      public abstract SSAIterator.DefinitionIterator getAllReached(SSADefinition def);
74  
75      
76      /// Backward links
77      /*** One level of pointees */
78      public abstract SSAIterator.DefinitionIterator getReaching(SSADefinition def);    
79      /*** All reaching definitions */
80      public abstract SSAIterator.DefinitionIterator getAllReaching(SSADefinition def);
81      
82  
83      public String toString(){
84          return "DefinitionGraph: " + _nodes.size() + "nodes, " + _edgeCount + " edges";
85      }
86          
87      /***
88       * Prints the subtree starting at definition def in a dot graph form.
89       * */
90      public void printDot(PrintStream out){
91          printDot(_nodes.iterator(), out, true);
92      }
93      public void printReachedToDot(SSADefinition def, PrintStream out){
94          printDot(new IteratorHelper.SingleIterator(def), out, true);
95      }    
96      public void printReachingToDot(SSADefinition def, PrintStream out){
97          printDot(new IteratorHelper.SingleIterator(def), out, false);
98      }
99      
100     protected void printDot(Iterator iter, PrintStream out, final boolean direction){
101         joeq.Util.SyntheticGraphs.Graph g = new joeq.Util.SyntheticGraphs.Graph();
102         
103         while(iter.hasNext()){
104             SSADefinition def = (SSADefinition)iter.next();
105         
106             (new Object(){
107                 void makeDotAux(joeq.Util.SyntheticGraphs.Graph g, SSADefinition def){
108                     g.addNode(def.getID(), def.toString());
109                     Iterator iter = direction ? getReached(def) : getReaching(def);
110                     if(iter != null){
111                         while(iter.hasNext()){
112                             SSADefinition def2 = (SSADefinition) iter.next();
113                             g.addEdge(def.getID(), def2.getID());                            
114                         
115                             makeDotAux(g, def2);                
116                         }
117                     }
118                 }            
119             }).makeDotAux(g, def);
120         
121             g.printDot(out);
122         }
123     }
124     
125     /*** By default a true predicate edge is added */
126     public void addEdge(SSADefinition def1, SSADefinition def2){
127         addEdge(def1, def2, PredicateEdge.TrueEdge.FACTORY.get());
128     }
129     
130     /*** null returned means that there is no edge */
131     public abstract EdgeInfo getEdgeInfo(SSADefinition def1, SSADefinition def2);
132     
133     //public abstract boolean isTerminalNode(SSADefinition def);
134         
135     public interface EdgeInfo {};
136     
137     class EmptyEdge implements EdgeInfo {}
138     
139     static class PredicateEdge implements EdgeInfo {
140         SSAValue.Predicate _predicate;
141         
142         PredicateEdge(SSAValue.Predicate predicate){
143             this._predicate = predicate;
144         }
145         
146         static class TrueEdge extends PredicateEdge {
147             SSAValue.Predicate _predicate;
148             
149             private TrueEdge(){
150                 super(SSAValue.Predicate.True());
151             }
152             
153             static class FACTORY {
154                 static TrueEdge _sample;
155                 
156                 /*** Use this method instead of the TrueEdge constructor */
157                 static TrueEdge get(){
158                     if(_sample == null){
159                         _sample = new TrueEdge();
160                     }
161                     return _sample;
162                 }
163             }
164         }
165     }
166     
167     class ContextEdge implements EdgeInfo {
168         ContextSet _context;
169     
170         ContextEdge(ContextSet context){
171             this._context = context;
172         }
173     }
174     
175     class IPEdge implements EdgeInfo {
176         // TODO: don't really know what the representation might be like
177         // maybe this is not necessary...
178     
179         IPEdge(){
180             // TODO: 
181         }
182     }
183 
184     /***
185      * The representation consists of an bunch of adjecently lists pointing 
186      * to and from a node. We can only have one edge between any two definitions. 
187      * */    
188     class EfficientDefinitionGraph extends DefinitionGraph {
189         private HashMap/*<SSADefinition, Map<SSADefinition, EdgeInfo> >*/ _adjacencyLists = new HashMap();
190         private HashMap/*<SSADefinition, LinkedList<SSADefinition> >*/    _reverseAdjacencyLists = new HashMap();
191         
192         EfficientDefinitionGraph(){}
193         
194         public void addEdge(SSADefinition def1, SSADefinition def2, EdgeInfo ei){
195             // Adjust direct adjancency lists
196             HashMap map = (HashMap)_adjacencyLists.get(def2);
197             if(map == null){
198                 map = new HashMap();
199                 _adjacencyLists.put(def2, map);
200             }
201             
202             Assert._assert(!map.containsKey(def1), "Already have a an edge " + 
203                 def1.toString() + " -> " + def2.toString() + 
204                 " with edge information " + ei.toString());
205                 
206             map.put(def1, ei);
207             
208             // Adjust reverse adjancency lists
209             LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def1);
210             if(list == null){
211                 list = new LinkedList();                 
212             }
213             list.addLast(def2);
214             _edgeCount++;
215         }
216         
217         public EdgeInfo getEdgeInfo(SSADefinition def1, SSADefinition def2){
218             HashMap map = (HashMap)_adjacencyLists.get(def2);
219             if(map == null){
220                 return null;
221             }
222             return (EdgeInfo)map.get(def1);        
223         }
224                 
225         /*** True is this nodes doesn't point to anyone */ 
226         public boolean isTerminalNode(SSADefinition def){
227             LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def);
228             if(list == null){
229                 return true;
230             }
231             
232             return list.isEmpty();
233         }
234         
235         /*** True if nobody points to this node */
236         public boolean isRootNode(SSADefinition def){
237             HashMap map = (HashMap)_adjacencyLists.get(def);
238             if(map == null){
239                 return true;
240             }
241             
242             return map.isEmpty();
243         }
244 
245         // Follow the forward links        
246         public SSAIterator.DefinitionIterator getReached(SSADefinition def){
247             LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def);
248             if(list == null){
249                 return null;
250             }
251             
252             return new SSAIterator.DefinitionIterator(list.iterator());
253         }        
254         public SSAIterator.DefinitionIterator getAllReached(SSADefinition def){
255             HashSet set = new HashSet();
256     
257             (new Object(){
258                 Set getReachedAux(SSADefinition def, Set set){
259                     set.add(def);
260                     Iterator iter = getReached(def);
261                     if(iter != null){
262                         while(iter.hasNext()){
263                             SSADefinition def2 = (SSADefinition)iter.next();
264                     
265                             getReachedAux(def2, set);
266                         }            
267                     }            
268             
269                     return set; 
270                 }
271             }).getReachedAux(def, set);            // fill the set with reaching definitions
272     
273             return new SSAIterator.DefinitionIterator(set.iterator());
274         }
275         
276         // Follow the backward links        
277         public SSAIterator.DefinitionIterator getReaching(SSADefinition def){
278             HashMap map = (HashMap)_adjacencyLists.get(def);
279             if(map == null){
280                 return null;
281             }
282             
283             return new SSAIterator.DefinitionIterator(map.values().iterator());
284         }
285         public SSAIterator.DefinitionIterator getAllReaching(SSADefinition def){
286             HashSet set = new HashSet();
287             
288             (new Object(){
289                 Set getReachingAux(SSADefinition def, Set set){
290                     set.add(def);
291                     Iterator iter = getReaching(def);
292                     if(iter != null){
293                         while(iter.hasNext()){
294                             SSADefinition def2 = (SSADefinition)iter.next();
295                             
296                             getReachingAux(def2, set);
297                         }            
298                     }            
299                     
300                     return set; 
301                 }
302             }).getReachingAux(def, set);            // fill the set with reaching definitions
303             
304             return new SSAIterator.DefinitionIterator(set.iterator());
305         }                
306     }
307 }