KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > api > java > source > query > CallGraph


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */

19
20 package org.netbeans.api.java.source.query;
21
22 import org.netbeans.modules.java.source.engine.EngineEnvironment;
23 import javax.lang.model.element.Element;
24 import javax.lang.model.element.TypeElement;
25 import org.netbeans.modules.java.source.engine.ASTModel;
26 import org.netbeans.modules.java.source.engine.EngineEnvironment;
27
28 import com.sun.source.tree.*;
29 import com.sun.source.util.TreeScanner;
30
31 import java.util.BitSet JavaDoc;
32 import java.util.HashMap JavaDoc;
33 import java.util.HashSet JavaDoc;
34 import java.util.Map JavaDoc;
35 import java.util.Stack JavaDoc;
36
37 /**
38  * Create a callgraph for a specified method. Subclasses can
39  * accept or reject nodes during scanning, to minimize memory
40  * requirements.
41  */

42 public class CallGraph {
43
44     private Element rootMethod;
45     private Node[] nodes;
46     private int nnodes;
47     private ASTModel model;
48
49     public CallGraph(Element method, QueryEnvironment env) {
50         this.model = ((EngineEnvironment)env).getModel();
51     nodes = new Node[1];
52     rootMethod = method;
53     }
54
55     public Node find(Element method) {
56     int inode = findNode(method);
57     return (inode != -1) ? nodes[inode] : null;
58     }
59
60     public Node[] getNodes() {
61     Node[] newa = new Node[nnodes];
62     System.arraycopy(nodes, 0, newa, 0, nnodes);
63     return newa;
64     }
65
66     private int findNode(Element method) {
67     for (int i = 0; i < nnodes; i++) {
68         if (method.equals(nodes[i].sym))
69         return i;
70     }
71     return -1;
72     }
73
74     public Node[] getPath(Element method) {
75     int meth = findNode(method);
76     if (meth == -1)
77         return new Node[0];
78     Stack JavaDoc stack = new Stack JavaDoc();
79     BitSet JavaDoc visited = new BitSet JavaDoc(nnodes);
80     getPath(0, meth, stack, visited);
81     Node[] ret = new Node[stack.size()];
82     stack.toArray(ret);
83     return ret;
84     }
85
86     public String JavaDoc getPathString(Element method) {
87     Node[] nodes = getPath(method);
88     if (nodes.length == 0)
89         return "<no path>";
90     StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
91     Element clazz = method.getEnclosingElement();
92     for (int i = 0; i < nodes.length; i++) {
93         Element m = nodes[i].sym;
94         Element ec = m.getEnclosingElement();
95         if (!ec.equals(clazz)) {
96         sb.append(ec.getSimpleName());
97         sb.append('.');
98         }
99         sb.append(m.getSimpleName());
100         if (i < nodes.length-1)
101         sb.append("->");
102     }
103     return sb.toString();
104     }
105
106     private static String JavaDoc makeNodeName(Element meth, TypeElement clazz) {
107         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
108     TypeElement encClz = (TypeElement)meth.getEnclosingElement();
109         if (!encClz.equals(clazz)) {
110             sb.append(encClz.getQualifiedName());
111             sb.append('.');
112         }
113         sb.append(meth.getSimpleName());
114         return sb.toString();
115     }
116
117     /**
118      * Depth-first recursive search for the "to" node. Return whether
119      * to keep searching or not.
120      */

121     private boolean getPath(int from, int to, Stack JavaDoc path, BitSet JavaDoc visited) {
122     Node n = nodes[from];
123     path.push(n);
124     visited.set(from);
125     if (from == to)
126         return false;
127     else
128         for (int i = 0; i < n.ncalls; i++) {
129         int inode = n.calls[i];
130         if (!visited.get(inode))
131             if (!getPath(inode, to, path, visited))
132             return false;
133         }
134     path.pop();
135     return true;
136     }
137
138     /**
139      * Add a new node if it isn't already in the nodes list, returning
140      * its index.
141      */

142     private int addNode(Element method) {
143     int inode = findNode(method);
144     if (inode == -1) {
145         if (nnodes == nodes.length) {
146         Node[] newa = new Node[nnodes * 2 + 1];
147         System.arraycopy(nodes, 0, newa, 0, nnodes);
148         nodes = newa;
149         }
150         inode = nnodes++;
151         nodes[inode] = new Node(method);
152     }
153     return inode;
154     }
155
156     public void buildGraph() {
157     symbols = new HashMap JavaDoc<Element, Tree>(); // rebuild each time for accuracy ...
158
addTrees(symbols, model.getRoot());
159     scanCalls(rootMethod, null);
160     symbols = null; // ... and release afterwards.
161
}
162
163     private void addTrees(Map JavaDoc<Element, Tree> map, Tree t) {
164     Element sym = model.getElement(t);
165     if (sym != null) {
166         map.put(sym, t);
167             for (Tree child : model.getChildren(t))
168                 addTrees(map, child);
169         }
170     }
171     
172     private Map JavaDoc<Element, Tree> symbols;
173
174     private void scanCalls(Element method, Node callingNode) {
175     int inode = findNode(method);
176     boolean needsScan = inode == -1;
177     if (needsScan)
178         inode = addNode(method);
179
180     if (callingNode != null)
181         callingNode.addCall(inode);
182
183     if (!needsScan)
184         return;
185
186     final Node node = nodes[inode];
187
188     Tree tree = symbols.get(method);
189     if (tree == null)
190         return;
191     tree.accept(new TreeScanner<Void JavaDoc,Object JavaDoc>() {
192                 @Override JavaDoc
193         public Void JavaDoc visitMethodInvocation(MethodInvocationTree t, Object JavaDoc p) {
194             Element meth = model.getElement(t.getMethodSelect());
195             if (meth != null && acceptCall(meth, t))
196             scanCalls(meth, node);
197             super.visitMethodInvocation(t, p);
198                     return null;
199         }
200                 @Override JavaDoc
201         public Void JavaDoc visitNewClass(NewClassTree t, Object JavaDoc p) {
202                     Element constructor = model.getElement(t);
203             if (acceptCall(constructor, t))
204             scanCalls(constructor, node);
205             super.visitNewClass(t, p);
206                     return null;
207         }
208         }, null);
209     }
210
211     /**
212      * Returns true if this method should be added to the graph.
213      * By overriding this method, a client can "pre-prune" the
214      * graph to avoid the inclusion of uninteresting nodes.
215      *
216      * Note: if a node isn't accepted (this method returns false),
217      * then it won't be scanned and so any child calls won't be
218      * scanned either.
219      */

220     public boolean acceptCall(Element symbol, Tree tree) {
221     return true;
222     }
223
224     public void list() {
225     list(find(rootMethod), 0, new HashSet JavaDoc());
226     }
227
228     private void list(Node node, int indent, HashSet JavaDoc listed) {
229     for (int i = 0 ; i < indent ; i++) {
230         System.out.print(" ");
231     }
232     if (listed.contains(node))
233         System.out.println("<" + node.getElement() + ">");
234     else {
235         listed.add(node);
236         System.out.println(node.getElement());
237         Node[] calls = node.getCalls(this);
238         for (int i = 0; i < calls.length; i++)
239         list(calls[i], indent + 1, listed);
240     }
241     }
242
243     /**
244      * An individual node in a ClassGraph.
245      */

246     public static class Node {
247     Element sym; // the element of this node
248
int[] calls = new int[0]; // child node indices
249
int ncalls = 0;
250
251     Node(Element sym) {
252         this.sym = sym;
253     }
254
255     public Element getElement() {
256         return sym;
257     }
258
259     Node[] getCalls(CallGraph cg) {
260         Node[] newa = new Node[ncalls];
261         for (int i = 0; i < ncalls; i++)
262         newa[i] = cg.nodes[calls[i]];
263         return newa;
264     }
265
266     void addCall(int inode) {
267         assert ncalls <= calls.length;
268         if (ncalls == calls.length) {
269         int[] newa = new int[ncalls * 2 + 1];
270         System.arraycopy(calls, 0, newa, 0, ncalls);
271         calls = newa;
272         }
273         calls[ncalls++] = inode;
274     }
275
276     public String JavaDoc toString() {
277         return sym.getSimpleName().toString();
278     }
279     }
280 }
281
Popular Tags