001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * as published by the Free Software Foundation; either version 2
008: * of the License, or (at your option) any later version.
009: *
010: * This program is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013: * GNU General Public License for more details.
014: *
015: * You should have received a copy of the GNU General Public License
016: * along with this program; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
018: */
019: package xtc.tree;
020:
021: import java.lang.reflect.Field;
022: import java.lang.reflect.Method;
023: import java.lang.reflect.InvocationTargetException;
024:
025: import java.util.LinkedHashMap;
026: import java.util.Map;
027:
028: /**
029: * A node visitor. In contrast to the basic visitor pattern (which
030: * only works for a fixed set of object types), the node visitor is
031: * extensible. As described in <a
032: * href="http://www.javaworld.com/javaworld/javatips/jw-javatip98.html">this
033: * JavaWorld tip</a>, the implementation relies on Java reflection to
034: * dispatch to the appropriate <code>visit()</code> method. Note that
035: * the node visitor does not recognize method names that append the
036: * object type to the word "visit", rather it relies on the argument
037: * type alone to identify the appropriate <code>visit()</code> method.
038: *
039: * <p>Note that to improve performance of dynamic dispatch, this class
040: * uses a static method lookup cache. As a result, dispatch is not
041: * thread-safe.
042: *
043: * @author Robert Grimm
044: * @version $Revision: 1.1 $
045: */
046: public abstract class Visitor {
047:
048: /** Key for the method lookup cache. */
049: static class CacheKey {
050:
051: /** The visitor. */
052: public Visitor visitor;
053:
054: /** The class of the node. */
055: public Class nodeT;
056:
057: /**
058: * Create a new cache key.
059: *
060: * @param visitor The visitor.
061: * @param nodeT The class of the node.
062: */
063: public CacheKey(Visitor visitor, Class nodeT) {
064: this .visitor = visitor;
065: this .nodeT = nodeT;
066: }
067:
068: public int hashCode() {
069: return (37 * System.identityHashCode(visitor) + System
070: .identityHashCode(nodeT));
071: }
072:
073: public boolean equals(Object o) {
074: if (!(o instanceof CacheKey))
075: return false;
076: CacheKey other = (CacheKey) o;
077: if (visitor != other.visitor)
078: return false;
079: return (nodeT == other.nodeT);
080: }
081:
082: }
083:
084: /** Flag for whether to use the method lookup cache. */
085: private static final boolean USE_CACHE = true;
086:
087: /** The size of the method lookup cache. */
088: private static final int CACHE_SIZE = 300;
089:
090: /** The capacity of the method lookup cache. */
091: private static final int CACHE_CAPACITY = 400;
092:
093: /** The load factor of the method lookup cache. */
094: private static final float CACHE_LOAD = (float) 0.75;
095:
096: /** The method lookup cache. */
097: private static final LinkedHashMap theCache;
098:
099: /** The pre-allocated cache key for looking up methods. */
100: private static final CacheKey theKey;
101:
102: /** The pre-allocated array for passing the node to invoke(). */
103: private static final Object[] theNode;
104:
105: /** The pre-allocated array for passing the node type to getMethod(). */
106: private static final Class[] theNodeType;
107:
108: static {
109: if (USE_CACHE) {
110: theCache = new LinkedHashMap(CACHE_CAPACITY, CACHE_LOAD,
111: true) {
112: protected boolean removeEldestEntry(Map.Entry e) {
113: return size() > CACHE_SIZE;
114: }
115: };
116: theKey = new CacheKey(null, null);
117: } else {
118: theCache = null;
119: theKey = null;
120: }
121: theNode = new Object[] { null };
122: theNodeType = new Class[] { null };
123: }
124:
125: /** Create a new visitor. */
126: public Visitor() {
127: }
128:
129: /**
130: * Find the closest matching <code>visit()</code> method for the
131: * specified node and invoke it. Optionally, a <code>visit()</code>
132: * method may return a value, thus making it possible, for example,
133: * to replace nodes or to construct entirely new trees. If the
134: * <code>visit()</code> method does not return a value, this method
135: * returns <code>null</code>.
136: *
137: * @param node The node.
138: * @return The (optional) return value.
139: * @throws VisitorException
140: * Signals that this visitor does not have a matching
141: * <code>visit()</code> method.
142: * @throws VisitingException
143: * Signals an exceptional condition while visiting the specified
144: * node.
145: */
146: public Object dispatch(Node node) {
147: Class nodeT = node.getClass();
148: Method m;
149:
150: if (USE_CACHE) {
151: theKey.visitor = this ;
152: theKey.nodeT = nodeT;
153: m = (Method) theCache.get(theKey);
154:
155: if (null == m) {
156: m = getMethod(nodeT);
157: theCache.put(new CacheKey(this , nodeT), m);
158: }
159: } else {
160: m = getMethod(nodeT);
161: }
162:
163: theNode[0] = node;
164: try {
165: return m.invoke(this , theNode);
166: } catch (IllegalAccessException x) {
167: // Shouldn't happen b/c m is public.
168: throw new VisitingException(
169: "Exceptional condition while visiting node " + node
170: + " with visitor " + this , x);
171: } catch (IllegalArgumentException x) {
172: // Shouldn't happen b/c this must be an instance of its own class.
173: throw new VisitingException(
174: "Exceptional condition while visiting node " + node
175: + " with visitor " + this , x);
176: } catch (ClassCastException x) {
177: throw new VisitingException(
178: "Invalid result while from visiting node " + node
179: + " with visitor " + this , x);
180: } catch (InvocationTargetException x) {
181: Throwable cause = x.getCause();
182:
183: if (cause instanceof VisitingException) {
184: // Rethrow.
185: throw (VisitingException) cause;
186: } else if (cause instanceof VisitorException) {
187: // Rethrow.
188: throw (VisitorException) cause;
189: } else if (null != cause) {
190: throw new VisitingException(
191: "Exceptional condition while visiting node "
192: + node + " with visitor " + this , cause);
193: } else {
194: throw new VisitingException(
195: "Exceptional condition while visiting node "
196: + node + " with visitor " + this , x);
197: }
198: }
199: }
200:
201: /**
202: * Find the closest matching <code>visit()</code> method for the
203: * specified type of node. The implementation of this method walks
204: * the class chain until it finds an appropriate method.
205: *
206: * @param node The node's class (which must be a subtype of Node).
207: * @throws VisitorException
208: * Signals that this visitor does not have a matching
209: * <code>visit()</code> method.
210: */
211: private Method getMethod(Class nodeT) {
212: Class visiT = getClass();
213: Class c = nodeT;
214: Method m = null;
215:
216: do {
217: theNodeType[0] = c;
218: try {
219: m = visiT.getMethod("visit", theNodeType);
220: } catch (NoSuchMethodException x) {
221: // Try the interfaces implemented by c.
222: Class[] interfaces = c.getInterfaces();
223: for (int i = 0; i < interfaces.length; i++) {
224: theNodeType[0] = interfaces[i];
225: try {
226: m = visiT.getMethod("visit", theNodeType);
227: } catch (NoSuchMethodException xx) {
228: // Ignore.
229: }
230: if (null != m) {
231: break;
232: }
233: }
234:
235: if (null == m) {
236: c = c.getSuperclass();
237: }
238: }
239: } while ((null == m) && (Object.class != c));
240:
241: if (null == m) {
242: throw new VisitorException(
243: "No method to visit nodes of type "
244: + nodeT.toString() + " in visitor "
245: + this.toString());
246: } else {
247: return m;
248: }
249: }
250:
251: }
|