1 /*
2 * Copyright (c) 1994, 2014, 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.lang;
27
28 import sun.reflect.ReflectionFactory;
29
30 import java.lang.reflect.Method;
31 import java.lang.reflect.Modifier;
32 import java.security.AccessController;
33 import java.util.Arrays;
34 import java.util.Iterator;
35 import java.util.NoSuchElementException;
36
37 /**
38 * A table of methods with different operations for adding and removing methods.
39 * It implements {@link Iterable} which iterates {@link java.lang.reflect.Method} objects
40 * in order they were added to the table.
41 */
42 interface MethodTable extends Iterable<Method> {
43
44 /**
45 * When requested {@code expectedMaxSize <= MAX_ARRAY_SIZE} then
46 * {@link java.lang.MethodTable.SimpleArrayImpl} is created
47 * else {@link HashArrayImpl} is created.
48 */
49 int MAX_ARRAY_SIZE = 20;
50
51 /**
52 * Constructs new instance of MethodTable with enough capacity to
53 * hold {@code expectedMaxSize} methods.
54 *
55 * @param expectedMaxSize expected maximum size of MethodTable
56 * @return new instance of MethodTable
57 */
58 static MethodTable newInstance(int expectedMaxSize) {
59 return expectedMaxSize <= MAX_ARRAY_SIZE
60 ? new SimpleArrayImpl(expectedMaxSize)
61 : new HashArrayImpl(expectedMaxSize);
62 }
63
64 /**
65 * Unconditionally adds given {@code method} to this MethodTable.
66 *
67 * @param method a method to add
68 */
69 void add(Method method);
70
71 /**
72 * Adds given {@code method} to this MethodTable unless a method
73 * with same signature already exists and it's
74 * {@link java.lang.reflect.Method#getDeclaringClass() declaring class}
75 * is equal to given {@code declaringClass}.
76 *
77 * @param method a method to add
78 * @param declaringClass the class to check against declaring classes
79 * of existing methods with same signature
80 */
81 void addUnlessDeclaredExists(Method method, Class<?> declaringClass);
82
83 /**
84 * Each existing method with same signature as given {@code method}
85 * is compared in turn with it and the following actions are taken:
86 * <ul>
87 * <li>if given method is same method as existing method,
88 * the operation completes without adding given method.</li>
89 * <li>if existing method is declared by given {@code declaringClass},
90 * the operation completes without adding given method.</li>
91 * <li>if existing method is not abstract and either existing method
92 * overrides given method or existing method is declared by class and given
93 * method is declared by interface, the operation completes without
94 * adding given method.</li>
95 * <li>if given method is not abstract and either given method overrides
96 * existing method or given method is declared by class and existing
97 * method is declared by interface, then existing method is removed
98 * from this MethodTable.</li>
99 * <li>if there are no more existing methods then given method is added
100 * to this MethodTable and operation completes else next existing
101 * method is taken into consideration.</li>
102 * </ul>
103 *
104 * @param method a method to consolidate with existing methods of same
105 * signature
106 */
107 void consolidate(Method method, Class<?> declaringClass);
108
109 /**
110 * @return the size of this MethodTable
111 */
112 int getSize();
113
114 /**
115 * Clears this MethodTable.
116 */
117 void clear();
118
119 /**
120 * @return new array of methods contained in this MethodTable
121 * in order they were added to this table.
122 */
123 default Method[] getMethods() {
124 Method[] methods = new Method[getSize()];
125 int i = 0;
126 for (Method m : this) {
127 methods[i++] = m;
128 }
129 return methods;
130 }
131
132
133 /**
134 * @return the 1st among the methods with the most specific return type
135 * if there is one or null if there are no methods in this MethodTable.
136 */
137 default Method getFirstMethodWithMostSpecificReturnType() {
138 Method res = null;
139 for (Method m : this) {
140 if (res == null || (
141 res.getReturnType() != m.getReturnType() &&
142 res.getReturnType().isAssignableFrom(m.getReturnType())
143 )) {
144 res = m;
145 }
146 }
147 return res;
148 }
149
150 /**
151 * A doubly-linked list of nodes. Each DLNode starts life as
152 * it's own doubly-linked singleton list.<p>
153 * {@link #unlink(Anchor anchor)} un-links a DLNode from a doubly-linked
154 * list with other nodes and liberates it so that it forms it's
155 * own singleton list. It also decrements {@code anchor}'s size.<p>
156 * {@link #linkBefore(Anchor anchor)} inserts a DLNode into the doubly-linked
157 * list before the {@code anchor} and increments it's size.
158 */
159 interface DLNode {
160 DLNode getNextDln();
161
162 void setNextDln(DLNode nextDln);
163
164 DLNode getPrevDln();
165
166 void setPrevDln(DLNode prevDln);
167
168 /**
169 * Insert {@code this} DLNode before {@code anchor}
170 */
171 default void linkBefore(Anchor anchor) {
172 // should be free before linking
173 assert this.getNextDln() == this &&
174 this.getPrevDln() == this;
175 DLNode prev = anchor.getPrevDln();
176 this.setNextDln(anchor);
177 anchor.setPrevDln(this);
178 prev.setNextDln(this);
179 this.setPrevDln(prev);
180 anchor.addToSize(1);
181 }
182
183 /**
184 * Remove {@code this} DLNode from doubly-linked list
185 */
186 default void unlink(Anchor anchor) {
187 DLNode next = this.getNextDln();
188 DLNode prev = this.getPrevDln();
189 // should be linked before un-linking
190 assert next != this && prev != this;
191 next.setPrevDln(prev);
192 prev.setNextDln(next);
193 this.setNextDln(this);
194 this.setPrevDln(this);
195 anchor.addToSize(-1);
196 }
197
198 /**
199 * Anchor is a {@link DLNode} which keeps track
200 * of doubly-linked list size.
201 */
202 interface Anchor extends DLNode {
203 void addToSize(int increment);
204 }
205 }
206
207 /**
208 * A node forming a linked-list of Method objects that share the same signature
209 * and a key with equals/hashCode that compares method signature.
210 * It also implements {@link DLNode} so it forms a separate doubly-linked list
211 * with other DLNode(s) to keep insertion order.
212 */
213 final class MethodNode implements DLNode {
214 final Method method;
215 private final int hash;
216 MethodNode next;
217
218 MethodNode(Method method) {
219 this.method = method;
220 this.hash = method.getReturnType().hashCode() ^
221 method.getName().hashCode() ^
222 reflectionFactory.methodParameterTypesHashCode(method);
223 }
224
225 void add(MethodNode other, Anchor anchor) {
226 other.next = this.next;
227 this.next = other;
228 other.linkBefore(anchor);
229 }
230
231 void addUnlessDeclaredExists(MethodNode other,
232 Class<?> declaringClass,
233 Anchor anchor) {
234 for (MethodNode node = this;
235 node.method.getDeclaringClass() != declaringClass;
236 node = node.next
237 ) {
238 if (node.next == null) {
239 node.next = other;
240 other.linkBefore(anchor);
241 break;
242 }
243 }
244 }
245
246 MethodNode consolidate(MethodNode other,
247 Class<?> declaringClass,
248 Anchor anchor) {
249 Class<?> thisCl = this.method.getDeclaringClass();
250 Class<?> otherCl = other.method.getDeclaringClass();
251
252 if (thisCl == otherCl || // this.method is the same as other.method OR
253 thisCl == declaringClass) { // this.method is declared by declaringClass
254 // complete without adding other
255 return this;
256 }
257
258 boolean thisAbstract = Modifier.isAbstract(this.method.getModifiers());
259
260 if (!thisAbstract && // this.method is non-abstract...
261 otherCl.isAssignableFrom(thisCl)) { // ...and overrides other.method
262 // complete without adding other
263 return this;
264 }
265
266 boolean thisInterface = thisCl.isInterface();
267 boolean otherInterface = otherCl.isInterface();
268
269 if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
270 otherInterface) { //...which wins over interface other.method
271 // complete without adding other
272 return this;
273 }
274
275 boolean otherAbstract = Modifier.isAbstract(other.method.getModifiers());
276
277 if (!otherAbstract && // other.method is non-abstract...
278 thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
279 // remove this and...
280 this.unlink(anchor);
281 if (next == null) { // ...add other
282 other.linkBefore(anchor);
283 return other;
284 } else { // ...continue with other
285 return next.consolidate(other, declaringClass, anchor);
286 }
287 }
288
289 if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
290 thisInterface) { //...which wins over interface this.method
291 // remove this and...
292 this.unlink(anchor);
293 if (next == null) { // ...add other
294 other.linkBefore(anchor);
295 return other;
296 } else { // ...continue with other
297 return next.consolidate(other, declaringClass, anchor);
298 }
299 }
300
301 // else keep this and...
302 if (next == null) { // ...add other
303 other.linkBefore(anchor);
304 next = other;
305 } else { //...continue with other
306 next = next.consolidate(other, declaringClass, anchor);
307 }
308 return this;
309 }
310
311 @Override
312 public int hashCode() {
313 return hash;
314 }
315
316 @Override
317 public boolean equals(Object obj) {
318 if (obj == this) return true;
319 if (!(obj instanceof MethodNode)) return false;
320 MethodNode other = (MethodNode) obj;
321 return this.method.getReturnType() == other.method.getReturnType() &&
322 this.method.getName() == other.method.getName() && // Method.name is interned
323 reflectionFactory.methodParameterTypesEquals(this.method, other.method);
324 }
325
326 // we just need to compare method parameter types
327
328 private static final ReflectionFactory reflectionFactory
329 = AccessController.doPrivileged(new ReflectionFactory.GetReflectionFactoryAction());
330
331 // DLNode implementation
332
333 private DLNode nextDln = this;
334 private DLNode prevDln = this;
335
336 @Override
337 public DLNode getNextDln() {
338 return nextDln;
339 }
340
341 @Override
342 public void setNextDln(DLNode nextDln) {
343 this.nextDln = nextDln;
344 }
345
346 @Override
347 public DLNode getPrevDln() {
348 return prevDln;
349 }
350
351 @Override
352 public void setPrevDln(DLNode prevDln) {
353 this.prevDln = prevDln;
354 }
355 }
356
357 /**
358 * MethodTable implementation based on {@link HashArray}.
359 * It also implements {@link DLNode.Anchor} to
360 * form a doubly-linked list with other DLNode(s).
361 */
362 final class HashArrayImpl extends HashArray<MethodNode> implements MethodTable, DLNode.Anchor {
363
364 HashArrayImpl(int expectedMaxSize) {
365 super(expectedMaxSize);
366 }
367
368 @Override
369 public void add(Method method) {
370 MethodNode n = new MethodNode(method);
371 MethodNode n0 = putIfAbsent(n);
372 if (n0 == null) {
373 n.linkBefore(this);
374 } else {
375 n0.add(n, this);
376 }
377 }
378
379 @Override
380 public void addUnlessDeclaredExists(Method method, Class<?> declaringClass) {
381 MethodNode n = new MethodNode(method);
382 MethodNode n0 = putIfAbsent(n);
383 if (n0 == null) {
384 n.linkBefore(this);
385 } else {
386 n0.addUnlessDeclaredExists(n, declaringClass, this);
387 }
388 }
389
390 @Override
391 public void consolidate(Method method, Class<?> declaringClass) {
392 MethodNode n = new MethodNode(method);
393 MethodNode n0 = putIfAbsent(n);
394 if (n0 == null) {
395 n.linkBefore(this);
396 } else {
397 MethodNode n1 = n0.consolidate(n, declaringClass, this);
398 if (n1 != n0) {
399 put(n1);
400 }
401 }
402 }
403
404 @Override
405 public int getSize() {
406 return size;
407 }
408
409 @Override
410 public void clear() {
411 super.clear();
412 nextDln = prevDln = this;
413 size = 0;
414 }
415
416 // Iterable<Method> implementation
417
418 @Override
419 public Iterator<Method> iterator() {
420 return new Iterator<Method>() {
421
422 DLNode dln = HashArrayImpl.this.getNextDln();
423
424 @Override
425 public boolean hasNext() {
426 return dln != HashArrayImpl.this;
427 }
428
429 @Override
430 public Method next() {
431 if (!hasNext()) {
432 throw new NoSuchElementException();
433 }
434 Method result = ((MethodNode) dln).method;
435 dln = dln.getNextDln();
436 return result;
437 }
438 };
439 }
440
441 // DLNode.Anchor implementation
442
443 private DLNode nextDln = this;
444 private DLNode prevDln = this;
445 private int size;
446
447 @Override
448 public DLNode getNextDln() {
449 return nextDln;
450 }
451
452 @Override
453 public void setNextDln(DLNode nextDln) {
454 this.nextDln = nextDln;
455 }
456
457 @Override
458 public DLNode getPrevDln() {
459 return prevDln;
460 }
461
462 @Override
463 public void setPrevDln(DLNode prevDln) {
464 this.prevDln = prevDln;
465 }
466
467 @Override
468 public void addToSize(int increment) {
469 size += increment;
470 }
471 }
472
473 /**
474 * Simple array based MethodTable implementation for small number of methods.
475 */
476 final class SimpleArrayImpl implements MethodTable {
477
478 private final Method[] methods;
479 private int hwm; // High Water Mark
480
481 SimpleArrayImpl(int expectedMaxSize) {
482 methods = new Method[expectedMaxSize];
483 }
484
485 @Override
486 public void add(Method method) {
487 methods[hwm++] = method;
488 }
489
490 @Override
491 public void addUnlessDeclaredExists(Method otherM, Class<?> declaringClass) {
492 for (int i = 0; i < hwm; i++) {
493 Method thisM = methods[i];
494 if (thisM == null || // mind the gap
495 thisM.getReturnType() != otherM.getReturnType() || // not same signature
496 thisM.getName() != otherM.getName() || // Method.name is interned
497 !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
498 continue;
499 }
500 // thisM has same signature as otherM
501
502 if (thisM.getDeclaringClass() == declaringClass) {
503 return;
504 }
505 // continue with next thisM
506 }
507 // add otherM
508 methods[hwm++] = otherM;
509 }
510
511 @Override
512 public void consolidate(Method otherM, Class<?> declaringClass) {
513 for (int i = 0; i < hwm; i++) {
514 Method thisM = methods[i];
515 if (thisM == null || // mind the gap
516 thisM.getReturnType() != otherM.getReturnType() || // not same signature
517 thisM.getName() != otherM.getName() || // Method.name is interned
518 !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
519 continue;
520 }
521 // thisM has same signature as otherM
522
523 Class<?> thisCl = thisM.getDeclaringClass();
524 Class<?> otherCl = otherM.getDeclaringClass();
525
526 if (thisCl == otherCl || // thisM is the same as otherM OR
527 thisCl == declaringClass) { // thisM is declared by declaringClass
528 // complete without adding otherM
529 return;
530 }
531
532 boolean thisAbstract = Modifier.isAbstract(thisM.getModifiers());
533
534 if (!thisAbstract && // thisM is non-abstract...
535 otherCl.isAssignableFrom(thisCl)) { // ...and overrides otherM
536 // complete without adding otherM
537 return;
538 }
539
540 boolean thisInterface = thisCl.isInterface();
541 boolean otherInterface = otherCl.isInterface();
542
543 if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
544 otherInterface) { //...which wins over interface other.method
545 // complete without adding otherM
546 return;
547 }
548
549 boolean otherAbstract = Modifier.isAbstract(otherM.getModifiers());
550
551 if (!otherAbstract && // other.method is non-abstract...
552 thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
553 // remove this
554 methods[i] = null;
555 continue;
556 }
557
558 if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
559 thisInterface) { //...which wins over interface this.method
560 // remove this
561 methods[i] = null;
562 }
563 // continue with next thisM
564 }
565 // add otherM
566 methods[hwm++] = otherM;
567 }
568
569 @Override
570 public int getSize() {
571 int size = 0;
572 for (int i = 0; i < hwm; i++) {
573 if (methods[i] != null) {
574 size++;
575 }
576 }
577 return size;
578 }
579
580 @Override
581 public void clear() {
582 Arrays.fill(methods, null);
583 hwm = 0;
584 }
585
586 @Override
587 public Iterator<Method> iterator() {
588 return new Iterator<Method>() {
589 int i = 0;
590 Method next;
591
592 private Method nextMethod() {
593 while (next == null && i < hwm) next = methods[i++];
594 return next;
595 }
596
597 @Override
598 public boolean hasNext() {
599 return nextMethod() != null;
600 }
601
602 @Override
603 public Method next() {
604 Method m = nextMethod();
605 if (m == null) throw new NoSuchElementException();
606 next = null;
607 return m;
608 }
609 };
610 }
611 }
612 }