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