001: /*
002: * @(#)DepgenUtil.java 1.21 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package util;
029:
030: import dependenceAnalyzer.*;
031: import java.util.Enumeration;
032: import java.util.Vector;
033:
034: /*
035: * Dependence-generation utility functions.
036: * Specific to the interfaces defined in dependenceAnalyzer,
037: * and to the external (String) representation of some of those things.
038: * Actually, this the the framework for building any member-
039: * dependence-analysis-based stuff.
040: */
041:
042: public class DepgenUtil extends LinkerUtil implements
043: dependenceAnalyzer.MemberArcTypes {
044: protected ClassFileFinder finder = new ClassFileFinder();
045: protected ClassnameFilter filter = new ClassnameFilter();
046: protected ClassnameFilter wholeClass;
047: protected ClassnameFilter wholeData;
048:
049: protected MemberDependenceAnalyzer analyzer = new MemberDependenceAnalyzer(
050: finder, filter);
051:
052: protected MemberName stringToName(String nameAndType) {
053: int nameDivision = methodOff(nameAndType);
054: String classname = nameAndType.substring(0, nameDivision);
055: String membername = nameAndType.substring(nameDivision + 1);
056: return new MemberName(analyzer
057: .classByName(sanitizeClassname(classname)),
058: sanitizeClassname(membername) // may include signature.
059: );
060: }
061:
062: protected MemberDependenceNode stringToNode(String nameAndType) {
063: return (MemberDependenceNode) (analyzer
064: .addNodeByName(stringToName(nameAndType)));
065: }
066:
067: /*
068: * Similar to stringToName, but permits us
069: * to name constructors (in context) without the bother of
070: * the magic name. Thus
071: * "java.lang.String([C)" is, in context, a synonym for
072: * the more perfectly general "java.lang.String.<init>([C)"
073: * We will also use the default signature if none is found.
074: */
075: protected MemberName stringToConstructorName(String classAndType) {
076: int sigDivision = sigOff(classAndType);
077: String classname;
078: String signature;
079: if (sigDivision == -1) {
080: classname = classAndType;
081: signature = constructorSig;
082: } else {
083: classname = classAndType.substring(0, sigDivision);
084: signature = classAndType.substring(sigDivision);
085: }
086: return new MemberName(analyzer
087: .classByName(sanitizeClassname(classname)),
088: constructorName + sanitizeClassname(signature));
089: }
090:
091: protected MemberDependenceNode stringToConstructorNode(
092: String classAndType) {
093: return (MemberDependenceNode) (analyzer
094: .addNodeByName(stringToConstructorName(classAndType)));
095: }
096:
097: /*
098: * Start with a String, return a ClassEntry. Very simple.
099: */
100: protected ClassEntry stringToClass(String classname) {
101: return analyzer.classByName(sanitizeClassname(classname));
102: }
103:
104: /*
105: * To exclude a class or package named by the given string.
106: * If it ends in *, we treat it as a package name.
107: * otherwise, it is a class.
108: */
109: protected void excludeClass(String xclassname) {
110: String classname = sanitizeClassname(xclassname);
111: filter.includeName(classname);
112: }
113:
114: /*
115: * This is the guts of dependence-based analysis.
116: * It is only slightly parameterized to allow
117: * for multiple target sets. In reality,
118: * there will most likely be only one.
119: *
120: * processNode is called after we have determined that the given
121: * node has not yet be added to our target set, but should be.
122: * It adds the node to targetList, then processes it,
123: * looking for other things to be added to the worklist.
124: * It is called by processNodeList, below.
125: */
126:
127: protected void processNode(DependenceNode node, int inclusionFlag,
128: int initIncludedFlag, int requiredMask, Vector targetlist,
129: Vector worklist) {
130: if (node.state() == DependenceNode.UNANALYZED)
131: analyzer.analyzeDependences(node);
132: if (node.state() == DependenceNode.ERROR)
133: return; // cannot cope.
134: if ((node.flags & MemberDependenceNode.EXCLUDED) != 0)
135: return; // not wanted.
136:
137: targetlist.addElement(node);
138: node.flags |= inclusionFlag;
139:
140: if (node instanceof ClassEntry) {
141: // if we require a class, what we really require is its <clinit>, if any.
142: ClassEntry classNode = (ClassEntry) node;
143: MemberDependenceNode clinit = classNode
144: .lookupMember(staticInitializerName
145: + staticInitializerSig);
146: if (clinit != null) {
147: if ((clinit.flags & requiredMask) == 0)
148: worklist.addElement(clinit);
149: // if we were clever, we'd assign node=clinit and fall through...
150: }
151: // we also need its superclass
152: ClassEntry mySuper = classNode.super Class();
153: if (mySuper != null) {
154: if ((mySuper.flags & requiredMask) == 0)
155: worklist.addElement(mySuper);
156: }
157: //
158: // we also believe that we need its interfaces.
159: // I personally believe this is an incorrect requirement
160: // by the current JVM implementation, but what can you do?
161: //
162: Enumeration ilist = classNode.interfaces();
163: while (ilist.hasMoreElements()) {
164: ClassEntry iface = (ClassEntry) (ilist.nextElement());
165: if ((iface.flags & requiredMask) == 0)
166: worklist.addElement(iface);
167: }
168:
169: //
170: // finally (?), if the class is named as one for which we
171: // want-all-members or want-all-data, then put all those
172: // things on the worklist, as appropriate.
173: String className = (String) (classNode.name());
174: boolean wantAllMembers = wholeClass.accept(null, className);
175: boolean wantAllData = wantAllMembers
176: || wholeData.accept(null, className);
177: if (wantAllData) { // ... which is the OR of two conditions...
178: Enumeration members = classNode.members();
179: if (members != null) {
180: while (members.hasMoreElements()) {
181: MemberDependenceNode mnode = (MemberDependenceNode) (members
182: .nextElement());
183: if (wantAllMembers
184: || ((mnode.flags & MemberDependenceNode.FIELD) != 0)) {
185: // either we want absolutely everything, or
186: // this is data ( and we implcitly want data )
187: // so, either way, we want mnode.
188: if ((mnode.flags & requiredMask) == 0) {
189: worklist.addElement(mnode);
190: }
191: }
192: }
193: }
194: }
195:
196: return;
197: }
198: MemberDependenceNode mNode = (MemberDependenceNode) node; // the only other kind we recognize.
199: if ((mNode.flags & MemberDependenceNode.OVERRIDDEN) != 0) {
200: /*
201: * Any methods which override this one, and are members of classes having constructors
202: * loaded, must themselves be loaded.
203: */
204: Enumeration overriders = mNode.overriddenBy();
205: while (overriders.hasMoreElements()) {
206: MemberDependenceNode t = (MemberDependenceNode) (overriders
207: .nextElement());
208: if ((t.flags & requiredMask) != 0)
209: continue; // already loaded.
210: if ((((MemberName) (t.name())).classEntry.flags & initIncludedFlag) != 0) {
211: // constructor is loaded but the overriding member is not.
212: // put it on the list.
213: worklist.addElement(t);
214: }
215: }
216: } else if ((mNode.flags & MemberDependenceNode.INIT) != 0) {
217: // this is a constructor.
218: // if its our first, check for necessary and overriding methods.
219: // then note that a constructor has been loaded
220: ClassEntry mClass = ((MemberName) (mNode.name())).classEntry;
221: if (((mClass.flags & initIncludedFlag) == 0)
222: && (mClass.flags & ClassEntry.HAS_OVERRIDING) != 0) {
223: Enumeration mMembers = mClass.members();
224: while (mMembers.hasMoreElements()) {
225: MemberDependenceNode t = (MemberDependenceNode) (mMembers
226: .nextElement());
227: if ((t.flags & (MemberDependenceNode.NO_OVERRIDING | MemberDependenceNode.EXCLUDED)) != 0)
228: continue; // not a candidate
229: Enumeration tover = t.overrides();
230: overriders: while (tover.hasMoreElements()) {
231: MemberDependenceNode u = (MemberDependenceNode) (tover
232: .nextElement());
233: if ((u.flags & requiredMask) != 0) {
234: worklist.addElement(t);
235: break overriders; // enough!
236: }
237: }
238: }
239: mClass.flags |= initIncludedFlag;
240: }
241: }
242:
243: Enumeration e = node.dependsOn();
244: while (e.hasMoreElements()) {
245: DependenceNode t = ((DependenceArc) (e.nextElement())).to();
246: if ((t.flags & requiredMask) == 0) {
247: worklist.addElement(t);
248: }
249: }
250: }
251:
252: /*
253: * The main entry point to dependence analysis.
254: * The vector of dependence nodes is used as a starting point,
255: * and they and everything they depend on are included in the
256: * resulting vector. This is parameterized by flags used so
257: * we can work with multiple sets at a time. In practice, this
258: * will probably never happen.
259: *
260: * Parameters are:
261: * worklist -- a Vector of DependenceNode's for which we need to
262: * build the dependence graphs
263: * inclusionFlag -- a 1-bit mask. This gets ORed into the flag word
264: * of all nodes that are required (i.e. are in the
265: * dependence set we're
266: * calculating. (By using different bits, we allow you
267: * to calculate multiple sets within the same graph.)
268: * We use this to avoid infinitely recalculating dependences
269: * for nodes we've already visited.
270: * initIncludedFlag -- a 1-bit mask. This gets ORed into the flag
271: * word of all classes for which at least one constructor
272: * is required. Is used for part of the overriding
273: * induced implicit-dependence calculation.
274: * requiredMask -- a multi-bit mask, which will certainly include
275: * inclusionFlag. Will also include, for instance, a
276: * bit noting that a node is part of an interface. This
277: * is used to test overridden members, to see if
278: * overriders must be required.
279: * verbosity -- a small integer value. Currently, there is only
280: * one message, and it is only printed if (verbosity>1)
281: *
282: * Return value is:
283: * a vector of all the nodes added to the required list by this
284: * calculation.
285: *
286: * Caveats:
287: * Note that we keep a lot of state in each node's flag word.
288: * We let the caller determine which bits we use, so it is the caller's
289: * responsibility to choose reasonable non-interfering sets.
290: * This algorithm might not work if some flag bits are
291: * unexpectedly set. If necessary, use clearUserFlags, below.
292: */
293:
294: protected Vector processList(Vector worklist, int inclusionFlag,
295: int initIncludedFlag, int requiredMask, int verbosity) {
296: Vector target = new Vector();
297: int targetsize = 0;
298: while (worklist.size() != 0) {
299: Enumeration working = worklist.elements();
300: Vector newlist = new Vector();
301: while (working.hasMoreElements()) {
302: DependenceNode node = (DependenceNode) (working
303: .nextElement());
304: if ((node.flags & requiredMask) == 0) {
305: processNode(node, inclusionFlag, initIncludedFlag,
306: requiredMask, target, newlist);
307: }
308: }
309: int newsize = target.size();
310: if (verbosity > 1) {
311: System.out.println(Localizer.getString(
312: "depgenutil.iteration_added_new_elements",
313: new Integer(newsize - targetsize)));
314: }
315: targetsize = newsize;
316: worklist = newlist;
317: }
318: return target;
319: }
320:
321: /*
322: * If we are asking multiple, hypothetical questions about
323: * dependence sets, we might want to re-use the same membership
324: * flags. This requires clearing them before re-use.
325: * clearUserFlags will iterate through all classes and members,
326: * clearing the flags given as input.
327: * This is NOT built into the operation of processList, as multiple
328: * questions is NOT the expected normal behavior, and has some cost.
329: */
330: protected void clearUserFlags(int flagset) {
331: int flagmask = ~flagset;
332: Enumeration classlist = analyzer.allClasses();
333: while (classlist.hasMoreElements()) {
334: ClassEntry c = (ClassEntry) (classlist.nextElement());
335: c.flags &= flagmask;
336: Enumeration memberlist = c.members();
337: if (memberlist == null)
338: continue;
339: while (memberlist.hasMoreElements()) {
340: DependenceNode m = (DependenceNode) (memberlist
341: .nextElement());
342: m.flags &= flagmask;
343: }
344: }
345: }
346:
347: }
|