View Javadoc

1   // RootedCHACallGraph.java, created Sat Mar 29  0:56:01 2003 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Quad;
5   
6   import java.io.BufferedWriter;
7   import java.io.FileWriter;
8   import java.io.IOException;
9   import java.util.Arrays;
10  import java.util.Collection;
11  import java.util.Set;
12  import joeq.Class.jq_Class;
13  import joeq.Class.jq_Type;
14  import joeq.Main.HostedVM;
15  import jwutil.graphs.CountPaths;
16  import jwutil.graphs.Navigator;
17  import jwutil.graphs.SCCTopSortedGraph;
18  import jwutil.graphs.SCComponent;
19  
20  /***
21   * @author John Whaley <jwhaley@alum.mit.edu>
22   * @version $Id: RootedCHACallGraph.java 2295 2005-08-18 01:56:59Z livshits $
23   */
24  public class RootedCHACallGraph extends CHACallGraph {
25      
26      private static final boolean DUMP_CALLGRAPH = false;
27      Collection roots;
28      
29      public RootedCHACallGraph() { }
30      public RootedCHACallGraph(Set classes) {
31          super(classes);
32      }
33      
34      /* (non-Javadoc)
35       * @see joeq.Compiler.Quad.CallGraph#getRoots()
36       */
37      public Collection getRoots() {
38          return roots;
39      }
40  
41      /* (non-Javadoc)
42       * @see Compiler.Quad.CallGraph#setRoots(java.util.Collection)
43       */
44      public void setRoots(Collection roots) {
45          this.roots = roots;
46      }
47  
48      public static void main(String[] args) {
49          long time;
50          
51          HostedVM.initialize();
52          
53          jq_Class c = (jq_Class) jq_Type.parseType(args[0]);
54          c.prepare();
55          
56          System.out.print("Building call graph...");
57          time = System.currentTimeMillis();
58          CallGraph cg = new RootedCHACallGraph();
59          cg = new CachedCallGraph(cg);
60          Collection roots = Arrays.asList(c.getDeclaredStaticMethods());
61          cg.setRoots(roots);
62          time = System.currentTimeMillis() - time;
63          System.out.println("done. ("+(time/1000.)+" seconds)");
64          
65          if(DUMP_CALLGRAPH) {
66              String callgraphFileName = "callgraph";
67              BufferedWriter dos;
68              try {
69                  dos = new BufferedWriter(new FileWriter(callgraphFileName ));
70                  LoadedCallGraph.write(cg, dos);            
71              } catch (IOException e) {
72                  e.printStackTrace();
73              }
74          }
75          test(cg);
76      }
77      
78      public static void test(CallGraph cg) {
79          long time;
80          if (true) {
81              System.out.print("Building navigator...");
82              time = System.currentTimeMillis();
83              Navigator n = cg.getNavigator();
84              time = System.currentTimeMillis() - time;
85              System.out.println("done. ("+(time/1000.)+" seconds)");
86              
87              System.out.print("Building strongly-connected components...");
88              time = System.currentTimeMillis();
89              Set s = SCComponent.buildSCC(cg.getRoots(), n);
90              time = System.currentTimeMillis() - time;
91              System.out.println("done. ("+(time/1000.)+" seconds)");
92              
93              System.out.print("Topologically sorting strongly-connected components...");
94              time = System.currentTimeMillis();
95              SCCTopSortedGraph g = SCCTopSortedGraph.topSort(s);
96              time = System.currentTimeMillis() - time;
97              System.out.println("done. ("+(time/1000.)+" seconds)");
98              
99              /*
100             for (Iterator j=g.getFirst().listTopSort().iterator(); j.hasNext(); ) {
101                 SCComponent d = (SCComponent) j.next();
102                 System.out.println(d);
103             }
104             */
105             
106             /*
107             long paths = 0L;
108             for (int i=1; ; ++i) {
109                 long paths2 = joeq.Util.Graphs.CountPaths.countPaths(g.getNavigator(), s, i);
110                 if (paths2 == paths) break;
111                 paths = paths2;
112                 System.out.println("Number of paths (k="+i+") = "+paths);
113             }
114             */
115             System.out.println("Number of paths (k=infinity) = "+CountPaths.countPaths(g.getNavigator(), s));
116         }
117         
118         if (false) {
119             Collection[] depths = INSTANCE.findDepths();
120             for (int i=0; i<depths.length; ++i) {
121                 System.out.println(">>>>> Depth "+i);
122                 System.out.println(depths[i]);
123             }
124         }
125     }
126 
127 }