    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.jexl2.internal.introspection;
    018
    019    import java.util.List;
    020    import java.util.LinkedList;
    021    import java.util.Iterator;
    022    import java.lang.reflect.Constructor;
    023    import java.lang.reflect.Method;
    024    import java.util.Arrays;
    025
    026    /**
    027     * A method key usable by the introspector cache.
    028     * <p>
    029     * This stores a method (or class) name and parameters.
    030     * </p>
    031     * <p>
    032     * This replaces the original key scheme which used to build the key
    033     * by concatenating the method name and parameters class names as one string
    034     * with the exception that primitive types were converted to their object class equivalents.
    035     * </p>
    036     * <p>
    037     * The key is still based on the same information, it is just wrapped in an object instead.
    038     * Primitive type classes are converted to they object equivalent to make a key;
    039     * int foo(int) and int foo(Integer) do generate the same key.
    040     * </p>
    041     * A key can be constructed either from arguments (array of objects) or from parameters
    042     * (array of class).
    043     * Roughly 3x faster than string key to access the map & uses less memory.
    044     */
    045    public final class MethodKey {
    046        /** The hash code. */
    047        private final int hashCode;
    048        /** The method name. */
    049        private final String method;
    050        /** The parameters. */
    051        private final Class<?>[] params;
    052        /** A marker for empty parameter list. */
    053        private static final Class<?>[] NOARGS = new Class<?>[0];
    054        /** The hash code constants. */
    055        private static final int HASH = 37;
    056
    057        /**
    058         * Creates a key from a method name and a set of arguments.
    059         * @param aMethod the method to generate the key from
    060         * @param args the intended method arguments
    061         */
    062        public MethodKey(String aMethod, Object[] args) {
    063            super();
    064            // !! keep this in sync with the other ctor (hash code) !!
    065            this.method = aMethod;
    066            int hash = this.method.hashCode();
    067            final int size;
    068            // CSOFF: InnerAssignment
    069            if (args != null && (size = args.length) > 0) {
    070                this.params = new Class<?>[size];
    071                for (int p = 0; p < size; ++p) {
    072                    Object arg = args[p];
    073                    // null arguments use void as Void.class as marker
    074                    Class<?> parm = arg == null ? Void.class : arg.getClass();
    075                    hash = (HASH * hash) + parm.hashCode();
    076                    this.params[p] = parm;
    077                }
    078            } else {
    079                this.params = NOARGS;
    080            }
    081            this.hashCode = hash;
    082        }
    083
    084        /**
    085         * Creates a key from a method.
    086         * @param aMethod the method to generate the key from.
    087         */
    088        MethodKey(Method aMethod) {
    089            this(aMethod.getName(), aMethod.getParameterTypes());
    090        }
    091
    092        /**
    093         * Creates a key from a method name and a set of parameters.
    094         * @param aMethod the method to generate the key from
    095         * @param args the intended method parameters
    096         */
    097        MethodKey(String aMethod, Class<?>[] args) {
    098            super();
    099            // !! keep this in sync with the other ctor (hash code) !!
    100            this.method = aMethod.intern();
    101            int hash = this.method.hashCode();
    102            final int size;
    103            // CSOFF: InnerAssignment
    104            if (args != null && (size = args.length) > 0) {
    105                this.params = new Class<?>[size];
    106                for (int p = 0; p < size; ++p) {
    107                    Class<?> parm = ClassMap.MethodCache.primitiveClass(args[p]);
    108                    hash = (HASH * hash) + parm.hashCode();
    109                    this.params[p] = parm;
    110                }
    111            } else {
    112                this.params = NOARGS;
    113            }
    114            this.hashCode = hash;
    115        }
    116
    117        /**
    118         * Gets this key's method name.
    119         * @return the method name
    120         */
    121        String getMethod() {
    122            return method;
    123        }
    124
    125        /**
    126         * Gets this key's method parameter classes.
    127         * @return the parameters
    128         */
    129        Class<?>[] getParameters() {
    130            return params;
    131        }
    132
    133        /** {@inheritDoc} */
    134        @Override
    135        public int hashCode() {
    136            return hashCode;
    137        }
    138
    139        /** {@inheritDoc} */
    140        @Override
    141        public boolean equals(Object obj) {
    142            if (obj instanceof MethodKey) {
    143                MethodKey key = (MethodKey) obj;
    144                return method.equals(key.method) && Arrays.equals(params, key.params);
    145            }
    146            return false;
    147        }
    148
    149        /** {@inheritDoc} */
    150        @Override
    151        public String toString() {
    152            StringBuilder builder = new StringBuilder(method);
    153            for (Class<?> c : params) {
    154                builder.append(c == Void.class ? "null" : c.getName());
    155            }
    156            return builder.toString();
    157        }
    158
    159        /**
    160         * Outputs a human readable debug representation of this key.
    161         * @return method(p0, p1, ...)
    162         */
    163        public String debugString() {
    164            StringBuilder builder = new StringBuilder(method);
    165            builder.append('(');
    166            for (int i = 0; i < params.length; i++) {
    167                if (i > 0) {
    168                    builder.append(", ");
    169                }
    170                builder.append(Void.class == params[i] ? "null" : params[i].getName());
    171            }
    172            builder.append(')');
    173            return builder.toString();
    174        }
    175
    176        /**
    177         * Gets the most specific method that is applicable to the parameters of this key.
    178         * @param methods a list of methods.
    179         * @return the most specific method.
    180         * @throws MethodKey.AmbiguousException if there is more than one.
    181         */
    182        public Method getMostSpecificMethod(List<Method> methods) {
    183            return METHODS.getMostSpecific(methods, params);
    184        }
    185
    186        /**
    187         * Gets the most specific constructor that is applicable to the parameters of this key.
    188         * @param methods a list of constructors.
    189         * @return the most specific constructor.
    190         * @throws MethodKey.AmbiguousException if there is more than one.
    191         */
    192        public Constructor<?> getMostSpecificConstructor(List<Constructor<?>> methods) {
    193            return CONSTRUCTORS.getMostSpecific(methods, params);
    194        }
    195
    196        /**
    197         * Determines whether a type represented by a class object is
    198         * convertible to another type represented by a class object using a
    199         * method invocation conversion, treating object types of primitive
    200         * types as if they were primitive types (that is, a Boolean actual
    201         * parameter type matches boolean primitive formal type). This behavior
    202         * is because this method is used to determine applicable methods for
    203         * an actual parameter list, and primitive types are represented by
    204         * their object duals in reflective method calls.
    205         *
    206         * @param formal         the formal parameter type to which the actual
    207         *                       parameter type should be convertible
    208         * @param actual         the actual parameter type.
    209         * @param possibleVarArg whether or not we're dealing with the last parameter
    210         *                       in the method declaration
    211         * @return true if either formal type is assignable from actual type,
    212         *         or formal is a primitive type and actual is its corresponding object
    213         *         type or an object type of a primitive type that can be converted to
    214         *         the formal type.
    215         */
    216        public static boolean isInvocationConvertible(Class<?> formal,
    217                Class<?> actual,
    218                boolean possibleVarArg) {
    219            /* if it's a null, it means the arg was null */
    220            if (actual == null && !formal.isPrimitive()) {
    221                return true;
    222            }
    223
    224            /* Check for identity or widening reference conversion */
    225            if (actual != null && formal.isAssignableFrom(actual)) {
    226                return true;
    227            }
    228
    229            /* Check for boxing with widening primitive conversion. Note that
    230             * actual parameters are never primitives. */
    231            if (formal.isPrimitive()) {
    232                if (formal == Boolean.TYPE && actual == Boolean.class) {
    233                    return true;
    234                }
    235                if (formal == Character.TYPE && actual == Character.class) {
    236                    return true;
    237                }
    238                if (formal == Byte.TYPE && actual == Byte.class) {
    239                    return true;
    240                }
    241                if (formal == Short.TYPE
    242                        && (actual == Short.class || actual == Byte.class)) {
    243                    return true;
    244                }
    245                if (formal == Integer.TYPE
    246                        && (actual == Integer.class || actual == Short.class
    247                        || actual == Byte.class)) {
    248                    return true;
    249                }
    250                if (formal == Long.TYPE
    251                        && (actual == Long.class || actual == Integer.class
    252                        || actual == Short.class || actual == Byte.class)) {
    253                    return true;
    254                }
    255                if (formal == Float.TYPE
    256                        && (actual == Float.class || actual == Long.class
    257                        || actual == Integer.class || actual == Short.class
    258                        || actual == Byte.class)) {
    259                    return true;
    260                }
    261                if (formal == Double.TYPE
    262                        && (actual == Double.class || actual == Float.class
    263                        || actual == Long.class || actual == Integer.class
    264                        || actual == Short.class || actual == Byte.class)) {
    265                    return true;
    266                }
    267            }
    268
    269            /* Check for vararg conversion. */
    270            if (possibleVarArg && formal.isArray()) {
    271                if (actual != null && actual.isArray()) {
    272                    actual = actual.getComponentType();
    273                }
    274                return isInvocationConvertible(formal.getComponentType(),
    275                        actual, false);
    276            }
    277            return false;
    278        }
    279
    280        /**
    281         * Determines whether a type represented by a class object is
    282         * convertible to another type represented by a class object using a
    283         * method invocation conversion, without matching object and primitive
    284         * types. This method is used to determine the more specific type when
    285         * comparing signatures of methods.
    286         *
    287         * @param formal         the formal parameter type to which the actual
    288         *                       parameter type should be convertible
    289         * @param actual         the actual parameter type.
    290         * @param possibleVarArg whether or not we're dealing with the last parameter
    291         *                       in the method declaration
    292         * @return true if either formal type is assignable from actual type,
    293         *         or formal and actual are both primitive types and actual can be
    294         *         subject to widening conversion to formal.
    295         */
    296        public static boolean isStrictInvocationConvertible(Class<?> formal,
    297                Class<?> actual,
    298                boolean possibleVarArg) {
    299            /* we shouldn't get a null into, but if so */
    300            if (actual == null && !formal.isPrimitive()) {
    301                return true;
    302            }
    303
    304            /* Check for identity or widening reference conversion */
    305            if (formal.isAssignableFrom(actual)) {
    306                return true;
    307            }
    308
    309            /* Check for widening primitive conversion. */
    310            if (formal.isPrimitive()) {
    311                if (formal == Short.TYPE && (actual == Byte.TYPE)) {
    312                    return true;
    313                }
    314                if (formal == Integer.TYPE
    315                        && (actual == Short.TYPE || actual == Byte.TYPE)) {
    316                    return true;
    317                }
    318                if (formal == Long.TYPE
    319                        && (actual == Integer.TYPE || actual == Short.TYPE
    320                        || actual == Byte.TYPE)) {
    321                    return true;
    322                }
    323                if (formal == Float.TYPE
    324                        && (actual == Long.TYPE || actual == Integer.TYPE
    325                        || actual == Short.TYPE || actual == Byte.TYPE)) {
    326                    return true;
    327                }
    328                if (formal == Double.TYPE
    329                        && (actual == Float.TYPE || actual == Long.TYPE
    330                        || actual == Integer.TYPE || actual == Short.TYPE
    331                        || actual == Byte.TYPE)) {
    332                    return true;
    333                }
    334            }
    335
    336            /* Check for vararg conversion. */
    337            if (possibleVarArg && formal.isArray()) {
    338                if (actual != null && actual.isArray()) {
    339                    actual = actual.getComponentType();
    340                }
    341                return isStrictInvocationConvertible(formal.getComponentType(),
    342                        actual, false);
    343            }
    344            return false;
    345        }
    346
    347        /**
    348         * whether a method/ctor is more specific than a previously compared one.
    349         */
    350        private static final int MORE_SPECIFIC = 0;
    351        /**
    352         * whether a method/ctor is less specific than a previously compared one.
    353         */
    354        private static final int LESS_SPECIFIC = 1;
    355        /**
    356         * A method/ctor doesn't match a previously compared one.
    357         */
    358        private static final int INCOMPARABLE = 2;
    359
    360        /**
    361         * Simple distinguishable exception, used when
    362         * we run across ambiguous overloading.  Caught
    363         * by the introspector.
    364         */
    365        public static class AmbiguousException extends RuntimeException {
    366            /**
    367             * Version Id for serializable.
    368             */
    369            private static final long serialVersionUID = -2314636505414551664L;
    370        }
    371
    372        /**
    373         * Utility for parameters matching.
    374         * @param <T> Method or Constructor
    375         */
    376        private abstract static class Parameters<T> {
    377            /**
    378             * Extract the parameter types from its applicable argument.
    379             * @param app a method or constructor
    380             * @return the parameters
    381             */
    382            protected abstract Class<?>[] getParameterTypes(T app);
    383
    384            // CSOFF: RedundantThrows
    385            /**
    386             * Gets the most specific method that is applicable to actual argument types.
    387             * @param methods a list of methods.
    388             * @param classes list of argument types.
    389             * @return the most specific method.
    390             * @throws MethodKey.AmbiguousException if there is more than one.
    391             */
    392            private T getMostSpecific(List<T> methods, Class<?>[] classes) {
    393                LinkedList<T> applicables = getApplicables(methods, classes);
    394
    395                if (applicables.isEmpty()) {
    396                    return null;
    397                }
    398
    399                if (applicables.size() == 1) {
    400                    return applicables.getFirst();
    401                }
    402
    403                /*
    404                 * This list will contain the maximally specific methods. Hopefully at
    405                 * the end of the below loop, the list will contain exactly one method,
    406                 * (the most specific method) otherwise we have ambiguity.
    407                 */
    408
    409                LinkedList<T> maximals = new LinkedList<T>();
    410
    411                for (Iterator<T> applicable = applicables.iterator();
    412                        applicable.hasNext();) {
    413                    T app = applicable.next();
    414                    Class<?>[] appArgs = getParameterTypes(app);
    415
    416                    boolean lessSpecific = false;
    417
    418                    for (Iterator<T> maximal = maximals.iterator();
    419                            !lessSpecific && maximal.hasNext();) {
    420                        T max = maximal.next();
    421
    422                        // CSOFF: MissingSwitchDefault
    423                        switch (moreSpecific(appArgs, getParameterTypes(max))) {
    424                            case MORE_SPECIFIC:
    425                                /*
    426                                 * This method is more specific than the previously
    427                                 * known maximally specific, so remove the old maximum.
    428                                 */
    429                                maximal.remove();
    430                                break;
    431
    432                            case LESS_SPECIFIC:
    433                                /*
    434                                 * This method is less specific than some of the
    435                                 * currently known maximally specific methods, so we
    436                                 * won't add it into the set of maximally specific
    437                                 * methods
    438                                 */
    439
    440                                lessSpecific = true;
    441                                break;
    442                        }
    443                    } // CSON: MissingSwitchDefault
    444
    445                    if (!lessSpecific) {
    446                        maximals.addLast(app);
    447                    }
    448                }
    449                if (maximals.size() > 1) {
    450                    // We have more than one maximally specific method
    451                    throw new AmbiguousException();
    452                }
    453                return maximals.getFirst();
    454            } // CSON: RedundantThrows
    455
    456            /**
    457             * Determines which method signature (represented by a class array) is more
    458             * specific. This defines a partial ordering on the method signatures.
    459             *
    460             * @param c1 first signature to compare
    461             * @param c2 second signature to compare
    462             * @return MORE_SPECIFIC if c1 is more specific than c2, LESS_SPECIFIC if
    463             *         c1 is less specific than c2, INCOMPARABLE if they are incomparable.
    464             */
    465            private int moreSpecific(Class<?>[] c1, Class<?>[] c2) {
    466                boolean c1MoreSpecific = false;
    467                boolean c2MoreSpecific = false;
    468
    469                // compare lengths to handle comparisons where the size of the arrays
    470                // doesn't match, but the methods are both applicable due to the fact
    471                // that one is a varargs method
    472                if (c1.length > c2.length) {
    473                    return MORE_SPECIFIC;
    474                }
    475                if (c2.length > c1.length) {
    476                    return LESS_SPECIFIC;
    477                }
    478
    479                // ok, move on and compare those of equal lengths
    480                for (int i = 0; i < c1.length; ++i) {
    481                    if (c1[i] != c2[i]) {
    482                        boolean last = (i == c1.length - 1);
    483                        c1MoreSpecific = c1MoreSpecific || isStrictConvertible(c2[i], c1[i], last);
    484                        c2MoreSpecific = c2MoreSpecific || isStrictConvertible(c1[i], c2[i], last);
    485                    }
    486                }
    487
    488                if (c1MoreSpecific) {
    489                    if (c2MoreSpecific) {
    490                        // Incomparable due to cross-assignable arguments (i.e. foo(String, Object) vs. foo(Object, String))
    491                        return INCOMPARABLE;
    492                    }
    493                    return MORE_SPECIFIC;
    494                }
    495                if (c2MoreSpecific) {
    496                    return LESS_SPECIFIC;
    497                }
    498
    499                // attempt to choose by picking the one with the greater number of primitives or latest primitive parameter
    500                int primDiff = 0;
    501                for (int c = 0; c < c1.length; ++c) {
    502                    if (c1[c].isPrimitive()) {
    503                        primDiff += 1 << c;
    504                    }
    505                    if (c2[c].isPrimitive()) {
    506                        primDiff -= 1 << c;
    507                    }
    508                }
    509                if (primDiff > 0) {
    510                    return MORE_SPECIFIC;
    511                } else if (primDiff < 0) {
    512                    return LESS_SPECIFIC;
    513                }
    514                /*
    515                 * Incomparable due to non-related arguments (i.e.
    516                 * foo(Runnable) vs. foo(Serializable))
    517                 */
    518                return INCOMPARABLE;
    519            }
    520
    521            /**
    522             * Returns all methods that are applicable to actual argument types.
    523             *
    524             * @param methods list of all candidate methods
    525             * @param classes the actual types of the arguments
    526             * @return a list that contains only applicable methods (number of
    527             *         formal and actual arguments matches, and argument types are assignable
    528             *         to formal types through a method invocation conversion).
    529             */
    530            private LinkedList<T> getApplicables(List<T> methods, Class<?>[] classes) {
    531                LinkedList<T> list = new LinkedList<T>();
    532
    533                for (Iterator<T> imethod = methods.iterator(); imethod.hasNext();) {
    534                    T method = imethod.next();
    535                    if (isApplicable(method, classes)) {
    536                        list.add(method);
    537                    }
    538
    539                }
    540                return list;
    541            }
    542
    543            /**
    544             * Returns true if the supplied method is applicable to actual
    545             * argument types.
    546             *
    547             * @param method  method that will be called
    548             * @param classes arguments to method
    549             * @return true if method is applicable to arguments
    550             */
    551            private boolean isApplicable(T method, Class<?>[] classes) {
    552                Class<?>[] methodArgs = getParameterTypes(method);
    553                // if samee number or args or
    554                // there's just one more methodArg than class arg
    555                // and the last methodArg is an array, then treat it as a vararg
    556                if (methodArgs.length == classes.length
    557                        || methodArgs.length == classes.length + 1 && methodArgs[methodArgs.length - 1].isArray()) {
    558                    // this will properly match when the last methodArg
    559                    // is an array/varargs and the last class is the type of array
    560                    // (e.g. String when the method is expecting String...)
    561                    for (int i = 0; i < classes.length; ++i) {
    562                        if (!isConvertible(methodArgs[i], classes[i], false)) {
    563                            // if we're on the last arg and the method expects an array
    564                            if (i == classes.length - 1 && methodArgs[i].isArray()) {
    565                                // check to see if the last arg is convertible
    566                                // to the array's component type
    567                                return isConvertible(methodArgs[i], classes[i], true);
    568                            }
    569                            return false;
    570                        }
    571                    }
    572                    return true;
    573                }
    574                // more arguments given than the method accepts; check for varargs
    575                if (methodArgs.length > 0) {
    576                    // check that the last methodArg is an array
    577                    Class<?> lastarg = methodArgs[methodArgs.length - 1];
    578                    if (!lastarg.isArray()) {
    579                        return false;
    580                    }
    581
    582                    // check that they all match up to the last method arg
    583                    for (int i = 0; i < methodArgs.length - 1; ++i) {
    584                        if (!isConvertible(methodArgs[i], classes[i], false)) {
    585                            return false;
    586                        }
    587                    }
    588
    589                    // check that all remaining arguments are convertible to the vararg type
    590                    Class<?> vararg = lastarg.getComponentType();
    591                    for (int i = methodArgs.length - 1; i < classes.length; ++i) {
    592                        if (!isConvertible(vararg, classes[i], false)) {
    593                            return false;
    594                        }
    595                    }
    596                    return true;
    597                }
    598                // no match
    599                return false;
    600            }
    601
    602            /**
    603             * @see #isInvocationConvertible(Class, Class, boolean)
    604             * @param formal         the formal parameter type to which the actual
    605             *                       parameter type should be convertible
    606             * @param actual         the actual parameter type.
    607             * @param possibleVarArg whether or not we're dealing with the last parameter
    608             *                       in the method declaration
    609             * @return see isMethodInvocationConvertible.
    610             */
    611            private boolean isConvertible(Class<?> formal, Class<?> actual,
    612                    boolean possibleVarArg) {
    613                // if we see Void.class, the argument was null
    614                return isInvocationConvertible(formal, actual.equals(Void.class) ? null : actual, possibleVarArg);
    615            }
    616
    617            /**
    618             * @see #isStrictInvocationConvertible(Class, Class, boolean)
    619             * @param formal         the formal parameter type to which the actual
    620             *                       parameter type should be convertible
    621             * @param actual         the actual parameter type.
    622             * @param possibleVarArg whether or not we're dealing with the last parameter
    623             *                       in the method declaration
    624             * @return see isStrictMethodInvocationConvertible.
    625             */
    626            private boolean isStrictConvertible(Class<?> formal, Class<?> actual,
    627                    boolean possibleVarArg) {
    628                // if we see Void.class, the argument was null
    629                return isStrictInvocationConvertible(formal, actual.equals(Void.class) ? null : actual, possibleVarArg);
    630            }
    631        }
    632
    633        /**
    634         * The parameter matching service for methods.
    635         */
    636        private static final Parameters<Method> METHODS = new Parameters<Method>() {
    637            @Override
    638            protected Class<?>[] getParameterTypes(Method app) {
    639                return app.getParameterTypes();
    640            }
    641        };
    642
    643        /**
    644         * The parameter matching service for constructors.
    645         */
    646        private static final Parameters<Constructor<?>> CONSTRUCTORS = new Parameters<Constructor<?>>() {
    647            @Override
    648            protected Class<?>[] getParameterTypes(Constructor<?> app) {
    649                return app.getParameterTypes();
    650            }
    651        };
    652    }