path: root/src/main/java/org/grothoff/Runabout.java

/*
 * (C) 2002, 2003, 2004, 2005, 2006 Christian Grothoff
 *
 * The Runabout is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; either version 2, or (at your option) any later version. The
 * Runabout is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License along with
 * the Runabout; see the file COPYING. If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * This software is also licensed under the Eclipse Public License v1.0 
 * available at http://www.eclipse.org/legal/epl-v10.html.
 */
package org.grothoff;

import java.io.UnsupportedEncodingException;
import java.lang.reflect.Array;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Modifier;
import java.util.HashMap;

/**
 * Runabout is a fast implementation of the Walkabout which is a variant of the
 * Visitor Pattern that does not require an accept method and uses reflection
 * instead.
 * <p/>
 * An instance of Runabout is able to walk over an arbitrary object graph using
 * visit methods which take arguments of the specific type of the object to
 * visit. For each node in the object graph the Runabout invokes the most
 * appropriate visit method.
 * <p/>
 * Using the Runabout typically involves subclassing Runabout and adding a
 * couple of visit methods. The Runabout provides a 'visitAppropriate' method
 * which will invoke the most appropriate visit method of the current Runabout
 * instance. If no visit method is applicable, visitAppropriate calls
 * visitDefault() which, if not overridden, throws an exception.
 * <p/>
 * The elements of the object graph typically extend the Element class, which
 * provides a generic way to quickly invoke the Runabout on all the fields of
 * the Element.
 * <p/>
 * Note that the Runabout uses dynamic code generation and dynamic loading in
 * order to be quickly able to invoke the appropriate visit methods. To make the
 * dynamic code generation fast, the code inlines parts of Java class-files in
 * binary form (ugly!).<br>
 * A per-thread Cache is used to speed-up the creation of the Runabout by
 * caching reflection, code creation and dynamic loading operations.
 * <p/>
 * <bf>Restrictions:</bf> Java semantics require:
 * <ul>
 * <li>all subclasses must be public, sadly this also means that <strong>you
 * can not use an anonymous inner class</strong> (!)</li>
 * <li>the types_length to all arguments of visit methods must be public</li>
 * <li>all visit methods must be public (!)</li>
 * </ul>
 * Otherwise the visitor will die with an IllegalAccessError during execution.
 * <p/>
 *
 * @author Christian Grothoff
 * @version 5.0
 */
public class Runabout {

    /**
     * Singleton of the Runabout.Cache. We cache reflective information per VM;
     * this avoids the need for repeated reflection, code generation and
     * dispatching map updates.
     */
    private static final Runabout.Cache cache_ = new Runabout.Cache();

    /**
     * map_ contains a mapping from a class to the appropriate visit method.
     * Note that at the beginning, map_ only contains the explicit mappings as
     * given by the visit methods. Over time, map_ will be amended to also
     * contain direct mappings for subclasses to the appropriate visit methods
     * if they are used.
     */
    private final HashMap<Class, Runabout.Code> map_;

    /**
     * Code to invoke if no visitor is found (used to avoid scanning the
     * hierarchy again and again).
     */
    private final Code noCode = new NoCode();

    /**
     * Set when the subclass of the runabout is not public.
     */
    private final boolean isPublic;

    /**
     * Create a Runabout.
     */
    public Runabout() {
        this.isPublic = Modifier.isPublic(getClass().getModifiers());
        map_ = cache_.get(this);
    }

    /**
     * Call the appropriate visit method. Use this method if you are visiting a
     * graph of objects (no primitives).
     *
     * @param o the object to visit
     */
    public void visitAppropriate(Object o) {
        getAppropriateCodeInternal(o.getClass()).visit(this, o);
    }

    /**
     * Obtain the appropriate code to call for class c. The method either
     * obtains the code quickly from the code map (fast path) or by calling the
     * lookup method getAppropriateCode.
     *
     * @return the code, never returns null
     */
    private Code getAppropriateCodeInternal(Class c) {
        synchronized (cache_) {
            Code co = map_.get(c);
            if (co != null)
                return co;
            co = getAppropriateCode(c);
            if (co == null)
                co = noCode;
            map_.put(c, co);
            return co;
        }
    }

    /**
     * Find the appropriate Code to call in the map. If no code is found, return
     * null. This lookup strategy first attempts to find a visit method defined
     * for the parent classes of c. If no such method exists, it attempts to
     * find an unambiguous visit method matching any interface transitively
     * implemented by c. If that does not exist either, null is returned. If
     * only an ambiguous visit method exists, an exception is raised.
     *
     * @param c the class for which to find the code
     * @return the code to run, or null if no code was found
     * @throws RunaboutException if the lookup would be ambiguous
     */
    private Code getAppropriateCode(Class c) {
        if (c.isArray()) {
            // uh uh, array subtyping in action...
            int dims = 1;
            Class component = c.getComponentType();
            while (component.isArray()) {
                dims++;
                component = component.getComponentType();
            }
            Class superComp = component.getSuperclass();
            while (superComp != null) {
                Code co = map_.get(Array.newInstance(superComp, new int[dims]).getClass());
                if (co != null)
                    return co;
                superComp = superComp.getSuperclass();
            }
            // now try subtyping with multi-dimensional Object[]
            // (see crazy runabout test).
            Class objectClass = c.getSuperclass();
            while (dims > 1) {
                Code co = map_.get(Array.newInstance(objectClass, new int[dims]).getClass());
                if (co != null)
                    return co;
                dims--;
            }
        }
        Class cl = c.getSuperclass();
        while (cl != null) {
            Code co = map_.get(cl);
            if (co != null)
                return co;
            cl = cl.getSuperclass();
        }
        return getAppropriateCode_ifc(c, c);
    }

    /**
     * Find the appropriate Code to call in the map. If no code is found, return
     * null.
     *
     * @param c  the class for which to find the code
     * @param cl the class where to start looking from
     * @return the code to run, or null if no code was found
     */
    private Code getAppropriateCode_ifc(Class c, Class cl) {
        Code co = null;
        while (cl != null) {
            Class[] ifc = cl.getInterfaces();
            for (Class anIfc : ifc) {
                Code r = map_.get(anIfc);
                if (r != null) {
                    if ((co != null) && (r != co))
                        throw new RunaboutException("Ambiguous resolution for visit call to "
                                + c + " in " + this.getClass().getName());
                    co = r;
                }
            }
            for (Class anIfc : ifc) {
                Code r = getAppropriateCode_ifc(c, anIfc);
                if (r != null) {
                    if ((co != null) && (r != co))
                        throw new RunaboutException("Ambiguous resolution for visit call to "
                                + c + " in " + this.getClass().getName());
                    co = r;
                }
            }
            cl = cl.getSuperclass();
        }
        return co;
    }

    /**
     * Generate the initial version of the map that maps classes to Code to call
     * the appropriate visit method.
     */
    final HashMap<Class, Runabout.Code> makeMap() {
        // get number of methods
        int size = 0;
        Class me = this.getClass();
        while (me != null) {
            size += me.getDeclaredMethods().length;
            me = me.getSuperclass();
        }
        // create map with slight over-estimate
        HashMap<Class, Runabout.Code> result = new HashMap<Class, Runabout.Code>(size * 2);
        // for all methods - create call code, put
        me = this.getClass();
        while (me != null) {
            Method[] methods = me.getDeclaredMethods();
            for (final Method m : methods) {
                if ((m.getName().equals("visit"))
                        && (!Modifier.isStatic(m.getModifiers()))) {
                    Class[] args = m.getParameterTypes();
                    if (args.length != 1)
                        throw new RunaboutException("Invalid number of arguments for Runabout in method "
                                + m);
                    final Class viC = args[0];
                    if (result.get(viC) != null)
                        continue;
                    Code co;
                    if (isPublic) {
                        // invoke the visitor with generated code
                        co = makeCode(viC);
                        if (co == null) {
                            throw new RunaboutException("Could not create/load dynamic code!");
                        }
                    } else {
                        if (!m.isAccessible()) {
                            m.setAccessible(true);
                        }
                        // invoke the visitor with an anonymous inner class,
                        // allows for the runabout to be public as the method made accessible
                        // by the Method instance.
                        // For Java 7+ the performance of this could be improved by using a MethodHandle
                        co = new Code() {
                            @Override
                            public void visit(Runabout r, Object o) {
                                try {

                                    m.invoke(r, o);
                                } catch (IllegalAccessException e) {
                                    throw new RunaboutException(e.toString());
                                } catch (InvocationTargetException e) {
                                    System.err.println("stacktrace:");
                                    e.getCause().printStackTrace(System.err);
                                    throw new RunaboutException(e.getCause().toString());
                                }
                            }
                        };
                    }

                    result.put(viC, co);

                }
            }
            me = me.getSuperclass();
        }
        return result;
    }

    /**
     * Create the code to invoke a visit method.
     *
     * @param c the type of the argument to the visit method
     */
    private Code makeCode(Class c) {
        byte[] myName // Lovm/util/RunaboutExample; substitute
                = canonicalName(getClass(), false);
        final int myNameLen = myName.length;
        final int myNameLenM2 = myNameLen - 2;
        byte[] cName // Ljava/lang/String; substitute
                = canonicalName(c, false);
        byte[] cNameCast = canonicalName(c, true);
        final int cNameLen = cName.length;
        final int cNameLenCast = cNameCast.length - 2;
        byte[] code = new byte[genCodeTemplate.length - 62 + myNameLenM2
                + cNameLenCast + cNameLen];

        // Build code by substituting a few strings in genCodeTemplate.
        // 117-145: org/grothoff/RunaboutExample => myName
        // 148-164: java/lang/String => cName
        // 192-200: XXXXXXXX => number
        // 250-271: (Ljava/lang/String;)V => "("+cName+")V"

        System.arraycopy(genCodeTemplate, 0, code, 0, 115);
        code[115] = (byte) ((myNameLenM2) >> 8);
        code[116] = (byte) ((myNameLenM2) & 255);
        System.arraycopy(myName, 1, code, 117, myNameLenM2);
        code[117 + myNameLenM2] = 1; // tag for string
        code[118 + myNameLenM2] = (byte) ((cNameLenCast) >> 8);
        code[119 + myNameLenM2] = (byte) ((cNameLenCast) & 255);
        System.arraycopy(cNameCast, 1, code, 120 + myNameLenM2, cNameLenCast);
        System.arraycopy(genCodeTemplate, 164, code, 120 + myNameLenM2
                + cNameLenCast, 248 - 164);
        code[120 + myNameLenM2 + cNameLenCast + 248 - 164] = (byte) ((cNameLen + 3) >> 8);
        code[120 + myNameLenM2 + cNameLenCast + 249 - 164] = (byte) ((cNameLen + 3) & 255);
        code[120 + myNameLenM2 + cNameLenCast + 250 - 164] = (byte) '(';
        System.arraycopy(cName, 0, code, 120 + myNameLenM2 + cNameLenCast + 251
                - 164, cNameLen);
        code[120 + myNameLenM2 + cNameLenCast + 250 - 164 + cNameLen + 1] = (byte) ')';
        code[120 + myNameLenM2 + cNameLenCast + 250 - 164 + cNameLen + 2] = (byte) 'V';
        System.arraycopy(genCodeTemplate,
                271,
                code,
                120 + myNameLenM2 + cNameLenCast + 250 - 164
                        + cNameLen + 3,
                genCodeTemplate.length - 271);
        return cache_.loadCode(code, 120 + myNameLenM2 + cNameLenCast + 192
                - 164);
    }

    /**
     * Get the class name in canonical form.
     *
     * @param cls the class, may not be primitive
     * @return the ovm name, following the convention of
     *         {@code java.util.Class.forName} according to the JavaDoc
     *         specification (JDK 1.2.2/1.3/1.4) which differs from the actual
     *         implementation in both SUN and IBM VMs.
     */
    private static byte[] canonicalName(Class cls, boolean forCast) {
        String cname = cls.getName();
        try {
            byte[] utf = cname.getBytes("UTF-8");
            int len = utf.length; // may be > cname.length()!
            if ((cname.charAt(0) != '[') || (forCast)) {
                byte[] ret = new byte[len + 2];
                ret[0] = (byte) 'L';
                System.arraycopy(utf, 0, ret, 1, len);
                ret[len + 1] = (byte) ';';
                for (int i = len; i > 0; i--)
                    if (ret[i] == (byte) '.')
                        ret[i] = (byte) '/';
                return ret;
            }
            for (int i = len - 1; i >= 0; i--)
                if (utf[i] == (byte) '.')
                    utf[i] = (byte) '/';
            return utf;
        } catch (UnsupportedEncodingException uee) {
            throw new RunaboutException("UTF8 encoding not supported!?: " + uee);
        }
    }

    /**
     * The Runabout.Cache is essentially a per-class cache of the internal
     * constant state of a Runabout instance. It contains the generated code to
     * quicly invoke the appropriate visit methods.
     *
     * @author Christian Grothoff
     */
    static final class Cache {

        /**
         * ClassLoader to use to load the code.
         */
        private final ClassLoader loader_;

        /**
         * Last name used by the class loader.
         */
        private final byte[] lastName_;

        /**
         * Mapping of classes to Maps.
         */
        private final HashMap<Class, HashMap<Class, Runabout.Code>> cachemap_;

        /**
         * Code that the loader should use.
         */
        byte[] code;

        /**
         * Create the Cache.
         */
        Cache() {
            loader_ = new ClassLoader() {
                public Class<?> loadClass(String name)
                        throws ClassNotFoundException {
                    //noinspection StringEquality
                    if (name == "Code") // == works here, as both strings are guaranteed to be interned
                        return defineClass(null, code, 0, code.length);
                    return Thread.currentThread().getContextClassLoader().loadClass(name);
                }
            };
            cachemap_ = new HashMap<Class, HashMap<Class, Runabout.Code>>();
            lastName_ = new byte[8];
            for (int i = 0; i < 8; i++)
                lastName_[i] = (byte) '0';
        }

        /**
         * Create a class from the given bytecode. Since classes loaded by the
         * same Loader must have a unique name, this method patches the bytecode
         * at the given offset, changing the next 8 characters to a unique Java
         * classname.
         *
         * @param byteCode the bytecode of the class which must describe a class
         *                 of type 'Code'. The class must contain a sequence XXXXXXXX at
         *                 offset xIdx where the classname is to be patched
         * @param xIdx     the index of the XXXXXXXX sequence
         * @return an instance of the loaded class, null on error
         * @throws ArrayIndexOutOfBoundsException if more than 62<sup>8</sup>
         *                                        classes are loaded :-)
         * @throws RunaboutException              if there are problems with dynamic loading
         *                                        of the byteCode
         */
        Code loadCode(byte[] byteCode, int xIdx) {
            boolean overflow = true;
            int index = 7;
            while (overflow) {
                overflow = false;
                lastName_[index]++;
                if (lastName_[index] == (byte) ('9' + 1))
                    lastName_[index] = (byte) 'A';
                if (lastName_[index] == (byte) ('Z' + 1))
                    lastName_[index] = (byte) 'a';
                if (lastName_[index] == (byte) ('z' + 1)) {
                    lastName_[index] = (byte) '0';
                    overflow = true;
                    index--;
                }
            }
            System.arraycopy(lastName_, 0, byteCode, xIdx, 8);
            code = byteCode;

            Code co;
            try {
                co = (Code) loader_.loadClass("Code").newInstance();
            } catch (InstantiationException ie) {
                throw new RunaboutException(ie.toString());
            } catch (ClassNotFoundException cnfe) {
                throw new RunaboutException(cnfe.toString());
            } catch (IllegalArgumentException iae) {
                throw new RunaboutException(iae.toString());
            } catch (ClassFormatError cfe) {
                throw new RunaboutException(cfe.toString());
            } catch (IllegalAccessException iae) {
                throw new RunaboutException(iae.toString());
            }
            code = null; // help GC
            return co;
        }

        /**
         * Obtain a map from the cache.
         */
        synchronized HashMap<Class, Runabout.Code> get(Runabout r) {
            Class c = r.getClass();
            HashMap<Class, Runabout.Code> map = cachemap_.get(c);
            if (map == null) {
                map = r.makeMap();
                cachemap_.put(c, map);
            }
            return map;
        }

    } // end of Runabout.Cache

    /**
     * Code is the generic interface that all generated classes implement. It is
     * used to quickly map a given class to the appropriate visit method.
     *
     * @author Christian Grothoff
     */
    public static abstract class Code {
        public Code() {
        }

        public abstract void visit(Runabout r, Object o);

    } // end of Runabout.Code

    /**
     * Implementation of Code that is called if no visit method matches (calls
     * visitDefault).
     *
     * @author Christian Grothoff
     */
    static final class NoCode extends Code {
        public final void visit(Runabout r, Object o) {
            r.visitDefault(o);
        }
    } // end of Runabout.NoCode

    /**
     * Override this method to provide a default behavior when no other visit
     * matches. The Runabout semantics are to search for a visit(X) and if there
     * is no match, call visitDefault(). As usual with the Runabout, visit(X)
     * looks at classes before interfaces. By default, visitDefault throws an
     * exception.
     */
    protected void visitDefault(Object o) {
        throw new RunaboutException("No visit method defined in "
                + this.getClass() + " for " + o.getClass());
    }

    /**
     * Generic Exception for problems in the Runabout.
     *
     * @author Christian Grothoff
     */
    public static final class RunaboutException extends RuntimeException {
        RunaboutException(String s) {
            super(s);
        }
    }

    /**
     * Compile 'GenCodeXXXXXXXX.java' with the option '-g:none' to tell javac
     * not to include any debugging information. This is the generated class
     * file.
     */
    private final static byte genCodeTemplate[] = {-54, -2, -70, -66, 0, 0, 0,
            49, 0, 22, 10, 0, 6, 0, 12, 7, 0, 13, 7, 0, 14, 10, 0, 2, 0, 15, 7,
            0, 16, 7, 0, 18, 1, 0, 6, 60, 105, 110, 105, 116, 62, 1, 0, 3, 40,
            41, 86, 1, 0, 4, 67, 111, 100, 101, 1, 0, 5, 118, 105, 115, 105,
            116, 1, 0, 44, 40, 76, 111, 114, 103, 47, 103, 114, 111, 116, 104,
            111, 102, 102, 47, 82, 117, 110, 97, 98, 111, 117, 116, 59, 76,
            106, 97, 118, 97, 47, 108, 97, 110, 103, 47, 79, 98, 106, 101, 99,
            116, 59, 41, 86, 12, 0, 7, 0, 8, 1, 0, 28, 111, 114, 103, 47, 103,
            114, 111, 116, 104, 111, 102, 102, 47, 82, 117, 110, 97, 98, 111,
            117, 116, 69, 120, 97, 109, 112, 108, 101, 1, 0, 16, 106, 97, 118,
            97, 47, 108, 97, 110, 103, 47, 83, 116, 114, 105, 110, 103, 12, 0,
            10, 0, 20, 1, 0, 28, 111, 114, 103, 47, 103, 114, 111, 116, 104,
            111, 102, 102, 47, 71, 101, 110, 67, 111, 100, 101, 88, 88, 88, 88,
            88, 88, 88, 88, 7, 0, 21, 1, 0, 26, 111, 114, 103, 47, 103, 114,
            111, 116, 104, 111, 102, 102, 47, 82, 117, 110, 97, 98, 111, 117,
            116, 36, 67, 111, 100, 101, 1, 0, 12, 73, 110, 110, 101, 114, 67,
            108, 97, 115, 115, 101, 115, 1, 0, 21, 40, 76, 106, 97, 118, 97,
            47, 108, 97, 110, 103, 47, 83, 116, 114, 105, 110, 103, 59, 41, 86,
            1, 0, 21, 111, 114, 103, 47, 103, 114, 111, 116, 104, 111, 102,
            102, 47, 82, 117, 110, 97, 98, 111, 117, 116, 0, 33, 0, 5, 0, 6, 0,
            0, 0, 0, 0, 2, 0, 1, 0, 7, 0, 8, 0, 1, 0, 9, 0, 0, 0, 17, 0, 1, 0,
            1, 0, 0, 0, 5, 42, -73, 0, 1, -79, 0, 0, 0, 0, 0, 1, 0, 10, 0, 11,
            0, 1, 0, 9, 0, 0, 0, 24, 0, 2, 0, 3, 0, 0, 0, 12, 43, -64, 0, 2,
            44, -64, 0, 3, -74, 0, 4, -79, 0, 0, 0, 0, 0, 1, 0, 19, 0, 0, 0,
            10, 0, 1, 0, 6, 0, 17, 0, 9, 4, 9}; // GenCodeXXXXXXXX.class

    public static void main(String[] args) {
        Runabout r = new Runabout() {
            public void visit(String s) {
                System.out.println("hi!!");
            }
        };
        r.visitAppropriate("foo");
    }

} // end of Runabout