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 */
017package org.apache.commons.jexl2.internal.introspection;
018
019import java.util.List;
020import java.util.LinkedList;
021import java.util.Iterator;
022import java.lang.reflect.Constructor;
023import java.lang.reflect.Method;
024import 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 &amp; uses less memory.
044 */
045public 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}