1/*
2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package java.lang;
24
25import jdk.internal.reflect.ReflectionFactory;
26
27import java.lang.reflect.Method;
28import java.lang.reflect.Modifier;
29import java.security.AccessController;
30import java.util.Arrays;
31import java.util.LinkedHashMap;
32import java.util.Map;
33
34/**
35 * A collection of most specific public methods. Methods are added to it using
36 * {@link #merge(Method)} method. Only the most specific methods for a
37 * particular signature are kept.
38 */
39final class PublicMethods {
40
41    /**
42     * a map of (method name, parameter types) -> linked list of Method(s)
43     */
44    private final Map<Key, MethodList> map = new LinkedHashMap<>();
45
46    /**
47     * keeps track of the number of collected methods
48     */
49    private int methodCount;
50
51    /**
52     * Merges new method with existing methods. New method is either
53     * ignored (if a more specific method with same signature exists) or added
54     * to the collection. When it is added to the collection, it may replace one
55     * or more existing methods with same signature if they are less specific
56     * than added method.
57     * See comments in code...
58     */
59    void merge(Method method) {
60        Key key = new Key(method);
61        MethodList existing = map.get(key);
62        int xLen = existing == null ? 0 : existing.length();
63        MethodList merged = MethodList.merge(existing, method);
64        methodCount += merged.length() - xLen;
65        // replace if head of list changed
66        if (merged != existing) {
67            map.put(key, merged);
68        }
69    }
70
71    /**
72     * Dumps methods to array.
73     */
74    Method[] toArray() {
75        Method[] array = new Method[methodCount];
76        int i = 0;
77        for (MethodList ml : map.values()) {
78            for (; ml != null; ml = ml.next) {
79                array[i++] = ml.method;
80            }
81        }
82        return array;
83    }
84
85    /**
86     * Method (name, parameter types) tuple.
87     */
88    private static final class Key {
89        private static final ReflectionFactory reflectionFactory =
90            AccessController.doPrivileged(
91                new ReflectionFactory.GetReflectionFactoryAction());
92
93        private final String name; // must be interned (as from Method.getName())
94        private final Class<?>[] ptypes;
95
96        Key(Method method) {
97            name = method.getName();
98            ptypes = reflectionFactory.getExecutableSharedParameterTypes(method);
99        }
100
101        static boolean matches(Method method,
102                               String name, // may not be interned
103                               Class<?>[] ptypes) {
104            return method.getName().equals(name) &&
105                   Arrays.equals(
106                       reflectionFactory.getExecutableSharedParameterTypes(method),
107                       ptypes
108                   );
109        }
110
111        @Override
112        public boolean equals(Object o) {
113            if (this == o) return true;
114            if (!(o instanceof Key)) return false;
115            Key that = (Key) o;
116            //noinspection StringEquality (guaranteed interned String(s))
117            return name == that.name &&
118                   Arrays.equals(ptypes, that.ptypes);
119        }
120
121        @Override
122        public int hashCode() {
123            return System.identityHashCode(name) + // guaranteed interned String
124                   31 * Arrays.hashCode(ptypes);
125        }
126    }
127
128    /**
129     * Node of a inked list containing Method(s) sharing the same
130     * (name, parameter types) tuple.
131     */
132    static final class MethodList {
133        Method method;
134        MethodList next;
135
136        private MethodList(Method method) {
137            this.method = method;
138        }
139
140        /**
141         * @return the head of a linked list containing given {@code methods}
142         *         filtered by given method {@code name}, parameter types
143         *         {@code ptypes} and including or excluding static methods as
144         *         requested by {@code includeStatic} flag.
145         */
146        static MethodList filter(Method[] methods, String name,
147                                 Class<?>[] ptypes, boolean includeStatic) {
148            MethodList head = null, tail = null;
149            for (Method method : methods) {
150                if ((includeStatic || !Modifier.isStatic(method.getModifiers())) &&
151                    Key.matches(method, name, ptypes)) {
152                    if (tail == null) {
153                        head = tail = new MethodList(method);
154                    } else {
155                        tail = tail.next = new MethodList(method);
156                    }
157                }
158            }
159            return head;
160        }
161
162        /**
163         * This method should only be called with the {@code head} (possibly null)
164         * of a list of Method(s) that share the same (method name, parameter types)
165         * and another {@code methodList} that also contains Method(s) with the
166         * same and equal (method name, parameter types) as the 1st list.
167         * It modifies the 1st list and returns the head of merged list
168         * containing only the most specific methods for each signature
169         * (i.e. return type). The returned head of the merged list may or
170         * may not be the same as the {@code head} of the given list.
171         * The given {@code methodList} is not modified.
172         */
173        static MethodList merge(MethodList head, MethodList methodList) {
174            for (MethodList ml = methodList; ml != null; ml = ml.next) {
175                head = merge(head, ml.method);
176            }
177            return head;
178        }
179
180        private static MethodList merge(MethodList head, Method method) {
181            Class<?> dclass = method.getDeclaringClass();
182            Class<?> rtype = method.getReturnType();
183            MethodList prev = null;
184            for (MethodList l = head; l != null; l = l.next) {
185                // eXisting method
186                Method xmethod = l.method;
187                // only merge methods with same signature:
188                // (return type, name, parameter types) tuple
189                // as we only keep methods with same (name, parameter types)
190                // tuple together in one list, we only need to check return type
191                if (rtype == xmethod.getReturnType()) {
192                    Class<?> xdclass = xmethod.getDeclaringClass();
193                    if (dclass.isInterface() == xdclass.isInterface()) {
194                        // both methods are declared by interfaces
195                        // or both by classes
196                        if (dclass.isAssignableFrom(xdclass)) {
197                            // existing method is the same or overrides
198                            // new method - ignore new method
199                            return head;
200                        }
201                        if (xdclass.isAssignableFrom(dclass)) {
202                            // new method overrides existing
203                            // method - knock out existing method
204                            if (prev != null) {
205                                prev.next = l.next;
206                            } else {
207                                head = l.next;
208                            }
209                            // keep iterating
210                        } else {
211                            // unrelated (should only happen for interfaces)
212                            prev = l;
213                            // keep iterating
214                        }
215                    } else if (dclass.isInterface()) {
216                        // new method is declared by interface while
217                        // existing method is declared by class -
218                        // ignore new method
219                        return head;
220                    } else /* xdclass.isInterface() */ {
221                        // new method is declared by class while
222                        // existing method is declared by interface -
223                        // knock out existing method
224                        if (prev != null) {
225                            prev.next = l.next;
226                        } else {
227                            head = l.next;
228                        }
229                        // keep iterating
230                    }
231                } else {
232                    // distinct signatures
233                    prev = l;
234                    // keep iterating
235                }
236            }
237            // append new method to the list
238            if (prev == null) {
239                head = new MethodList(method);
240            } else {
241                prev.next = new MethodList(method);
242            }
243            return head;
244        }
245
246        private int length() {
247            int len = 1;
248            for (MethodList ml = next; ml != null; ml = ml.next) {
249                len++;
250            }
251            return len;
252        }
253
254        /**
255         * @return 1st method in list with most specific return type
256         */
257        Method getMostSpecific() {
258            Method m = method;
259            Class<?> rt = m.getReturnType();
260            for (MethodList ml = next; ml != null; ml = ml.next) {
261                Method m2 = ml.method;
262                Class<?> rt2 = m2.getReturnType();
263                if (rt2 != rt && rt.isAssignableFrom(rt2)) {
264                    // found more specific return type
265                    m = m2;
266                    rt = rt2;
267                }
268            }
269            return m;
270        }
271    }
272}
273