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.util.Arrays;
33 import java.util.HashMap;
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 else {@link HashArrayImpl} is created.
47 */
48 int MAX_ARRAY_SIZE = 20;
49
50 /**
51 * Constructs new instance of MethodTable with enough capacity to
52 * hold {@code expectedMaxSize} methods.
53 *
54 * @param expectedMaxSize expected maximum size of MethodTable
55 * @return new instance of MethodTable
56 */
57 static MethodTable newInstance(int expectedMaxSize) {
58 return expectedMaxSize <= MAX_ARRAY_SIZE
59 ? new SimpleArrayImpl(expectedMaxSize)
60 : new HashArrayImpl(expectedMaxSize);
61 }
62
63 /**
64 * Unconditionally adds the {@code method} to this MethodTable.
65 *
66 * @param method a method to add
67 */
68 void add(Method method);
69
70 /**
71 * Adds the {@code method} to this MethodTable unless a method with same
72 * signature already exists and it's
73 * {@link java.lang.reflect.Method#getDeclaringClass() declaring class}
74 * is equal to given {@code declaringClass}.
75 *
76 * @param method a method to add
77 * @param declaringClass the class to check against declaring classes
78 * of existing methods with same signature
79 * @return true if method has been added or false if not
80 */
81 boolean addUnlessDeclaredExists(Method method, Class<?> declaringClass);
82
83 /**
84 * Each existing method with same signature as new {@code method}
85 * is compared in turn with it and one of the following actions is taken:
86 * <ul>
87 * <li>if new method is same method as existing method,
88 * the operation completes without adding new method.</li>
89 * <li>if existing method is declared by given {@code declaringClass},
90 * the operation completes without adding new method.</li>
91 * <li>if existing method is not abstract and either existing method
92 * overrides new method or existing method is declared by class and new
93 * method is declared by interface, the operation completes without
94 * adding new method.</li>
95 * <li>if new method is not abstract and either new method overrides
96 * existing method or new 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 new 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 * @return new array of methods contained in this MethodTable
116 * in order they were added to this table.
117 */
118 default Method[] getMethods() {
119 Method[] methods = new Method[getSize()];
120 int i = 0;
121 for (Method m : this) {
122 methods[i++] = m;
123 }
124 return methods;
125 }
126
127
128 /**
129 * @return the 1st among the methods with the most specific return type
130 * if there is one or null if there are no methods in this MethodTable.
131 */
132 default Method getFirstMethodWithMostSpecificReturnType() {
133 Method res = null;
134 for (Method m : this) {
135 if (res == null || (
136 res.getReturnType() != m.getReturnType() &&
137 res.getReturnType().isAssignableFrom(m.getReturnType())
138 )) {
139 res = m;
140 }
141 }
142 return res;
143 }
144
145 /**
146 * A doubly-linked list of nodes. Each DLNode starts life as
147 * it's own doubly-linked singleton list.<p>
148 * {@link #unlink(Anchor anchor)} un-links a DLNode from a doubly-linked
149 * list with other nodes and liberates it so that it forms it's
150 * own singleton list. It also decrements {@code anchor}'s size.<p>
151 * {@link #linkBefore(Anchor anchor)} inserts a DLNode into the doubly-linked
152 * list before the {@code anchor} and increments it's size.
153 */
154 interface DLNode {
155 DLNode getNextDln();
156
157 void setNextDln(DLNode nextDln);
158
159 DLNode getPrevDln();
160
161 void setPrevDln(DLNode prevDln);
162
163 /**
164 * Insert {@code this} DLNode before {@code anchor}
165 */
166 default void linkBefore(Anchor anchor) {
167 // should be free before linking
168 assert this.getNextDln() == this &&
169 this.getPrevDln() == this;
170 DLNode prev = anchor.getPrevDln();
171 this.setNextDln(anchor);
172 anchor.setPrevDln(this);
173 prev.setNextDln(this);
174 this.setPrevDln(prev);
175 anchor.addToSize(1);
176 }
177
178 /**
179 * Remove {@code this} DLNode from doubly-linked list
180 */
181 default void unlink(Anchor anchor) {
182 DLNode next = this.getNextDln();
183 DLNode prev = this.getPrevDln();
184 // should be linked before un-linking
185 assert next != this && prev != this;
186 next.setPrevDln(prev);
187 prev.setNextDln(next);
188 this.setNextDln(this);
189 this.setPrevDln(this);
190 anchor.addToSize(-1);
191 }
192
193 /**
194 * Anchor is a {@link DLNode} which keeps track
195 * of doubly-linked list size.
196 */
197 interface Anchor extends DLNode {
198 void addToSize(int increment);
199 }
200 }
201
202 /**
203 * A node forming a linked-list of Method objects that share the same signature
204 * and a key with equals/hashCode that compares method signature.
205 * It also implements {@link DLNode} so it forms a separate doubly-linked list
206 * with other DLNode(s) to keep insertion order.
207 */
208 final class MethodNode implements DLNode {
209 final Method method;
210 private final int hash;
211 MethodNode next;
212
213 MethodNode(Method method) {
214 this.method = method;
215 this.hash = method.getReturnType().hashCode() ^
216 method.getName().hashCode() ^
217 reflectionFactory.methodParameterTypesHashCode(method);
218 }
219
220 void add(MethodNode other, Anchor anchor) {
221 other.next = this.next;
222 this.next = other;
223 other.linkBefore(anchor);
224 }
225
226 boolean addUnlessDeclaredExists(
227 MethodNode other,
228 Class<?> declaringClass,
229 Anchor anchor
230 ) {
231 for (
232 MethodNode node = this;
233 node.method.getDeclaringClass() != declaringClass;
234 node = node.next
235 ) {
236 if (node.next == null) {
237 node.next = other;
238 other.linkBefore(anchor);
239 return true;
240 }
241 }
242 return false;
243 }
244
245 MethodNode consolidate(
246 MethodNode other,
247 Class<?> declaringClass,
248 Anchor anchor
249 ) {
250 Class<?> thisCl = this.method.getDeclaringClass();
251 Class<?> otherCl = other.method.getDeclaringClass();
252
253 if (thisCl == otherCl || // this.method is the same as other.method OR
254 thisCl == declaringClass) { // this.method is declared by declaringClass
255 // complete without adding other
256 return this;
257 }
258
259 boolean thisAbstract = Modifier.isAbstract(this.method.getModifiers());
260
261 if (!thisAbstract && // this.method is non-abstract...
262 otherCl.isAssignableFrom(thisCl)) { // ...and overrides other.method
263 // complete without adding other
264 return this;
265 }
266
267 boolean thisInterface = thisCl.isInterface();
268 boolean otherInterface = otherCl.isInterface();
269
270 if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
271 otherInterface) { //...which wins over interface other.method
272 // complete without adding other
273 return this;
274 }
275
276 boolean otherAbstract = Modifier.isAbstract(other.method.getModifiers());
277
278 if (!otherAbstract && // other.method is non-abstract...
279 thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
280 // remove this and...
281 this.unlink(anchor);
282 if (next == null) { // ...add other
283 other.linkBefore(anchor);
284 return other;
285 } else { // ...continue with other
286 return next.consolidate(other, declaringClass, anchor);
287 }
288 }
289
290 if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
291 thisInterface) { //...which wins over interface this.method
292 // remove this and...
293 this.unlink(anchor);
294 if (next == null) { // ...add other
295 other.linkBefore(anchor);
296 return other;
297 } else { // ...continue with other
298 return next.consolidate(other, declaringClass, anchor);
299 }
300 }
301
302 // else keep this and...
303 if (next == null) { // ...add other
304 other.linkBefore(anchor);
305 next = other;
306 } else { //...continue with other
307 next = next.consolidate(other, declaringClass, anchor);
308 }
309 return this;
310 }
311
312 @Override
313 public int hashCode() {
314 return hash;
315 }
316
317 @Override
318 public boolean equals(Object obj) {
319 if (obj == this) return true;
320 if (!(obj instanceof MethodNode)) return false;
321 MethodNode other = (MethodNode) obj;
322 return this.method.getReturnType() == other.method.getReturnType() &&
323 this.method.getName() == other.method.getName() && // Method.name is interned
324 reflectionFactory.methodParameterTypesEquals(this.method, other.method);
325 }
326
327 // we just need to compare method parameter types
328
329 private static final ReflectionFactory reflectionFactory;
330 static {
331 reflectionFactory =
332 java.security.AccessController.doPrivileged
333 (new sun.reflect.ReflectionFactory.GetReflectionFactoryAction());
334 }
335
336 // DLNode implementation
337
338 private DLNode nextDln = this;
339 private DLNode prevDln = this;
340
341 @Override
342 public DLNode getNextDln() {
343 return nextDln;
344 }
345
346 @Override
347 public void setNextDln(DLNode nextDln) {
348 this.nextDln = nextDln;
349 }
350
351 @Override
352 public DLNode getPrevDln() {
353 return prevDln;
354 }
355
356 @Override
357 public void setPrevDln(DLNode prevDln) {
358 this.prevDln = prevDln;
359 }
360 }
361
362 /**
363 * MethodTable implementation based on {@link java.util.HashMap}.
364 * It also implements {@link DLNode.Anchor} to
365 * form a doubly-linked list with other DLNode(s).
366 */
367 final class HashMapImpl extends HashMap<MethodNode, MethodNode> implements MethodTable, DLNode.Anchor {
368
369 public HashMapImpl(int expectedMaxSize) {
370 super(expectedMaxSize * 4 / 3);
371 }
372
373 @Override
374 public void add(Method method) {
375 MethodNode n = new MethodNode(method);
376 MethodNode n0 = putIfAbsent(n, n);
377 if (n0 == null) {
378 n.linkBefore(this);
379 } else {
380 n0.add(n, this);
381 }
382 }
383
384 @Override
385 public boolean addUnlessDeclaredExists(Method method, Class<?> declaringClass) {
386 MethodNode n = new MethodNode(method);
387 MethodNode n0 = putIfAbsent(n, n);
388 if (n0 == null) {
389 n.linkBefore(this);
390 return true;
391 } else {
392 return n0.addUnlessDeclaredExists(n, declaringClass, this);
393 }
394 }
395
396 @Override
397 public void consolidate(Method method, Class<?> declaringClass) {
398 MethodNode n = new MethodNode(method);
399 MethodNode n0 = putIfAbsent(n, n);
400 if (n0 == null) {
401 n.linkBefore(this);
402 } else {
403 MethodNode n1 = n0.consolidate(n, declaringClass, this);
404 if (n1 != n0) {
405 put(n1, n1);
406 }
407 }
408 }
409
410 @Override
411 public int getSize() {
412 return size;
413 }
414
415 // Iterable<Method> implementation
416
417 @Override
418 public Iterator<Method> iterator() {
419 return new Iterator<Method>() {
420
421 DLNode dln = getNextDln();
422
423 @Override
424 public boolean hasNext() {
425 return dln != HashMapImpl.this;
426 }
427
428 @Override
429 public Method next() {
430 if (!hasNext()) {
431 throw new NoSuchElementException();
432 }
433 Method result = ((MethodNode) dln).method;
434 dln = dln.getNextDln();
435 return result;
436 }
437 };
438 }
439
440 // DLNode.Anchor implementation
441
442 private DLNode nextDln = this;
443 private DLNode prevDln = this;
444 private int size;
445
446 @Override
447 public DLNode getNextDln() {
448 return nextDln;
449 }
450
451 @Override
452 public void setNextDln(DLNode nextDln) {
453 this.nextDln = nextDln;
454 }
455
456 @Override
457 public DLNode getPrevDln() {
458 return prevDln;
459 }
460
461 @Override
462 public void setPrevDln(DLNode prevDln) {
463 this.prevDln = prevDln;
464 }
465
466 @Override
467 public void addToSize(int increment) {
468 size += increment;
469 }
470 }
471
472 /**
473 * MethodTable implementation based on {@link HashArray}.
474 * It also implements {@link DLNode.Anchor} to
475 * form a doubly-linked list with other DLNode(s).
476 */
477 final class HashArrayImpl extends HashArray<MethodNode> implements MethodTable, DLNode.Anchor {
478
479 public HashArrayImpl(int expectedMaxSize) {
480 super(expectedMaxSize);
481 }
482
483 @Override
484 public void add(Method method) {
485 MethodNode n = new MethodNode(method);
486 MethodNode n0 = putIfAbsent(n);
487 if (n0 == null) {
488 n.linkBefore(this);
489 } else {
490 n0.add(n, this);
491 }
492 }
493
494 @Override
495 public boolean addUnlessDeclaredExists(Method method, Class<?> declaringClass) {
496 MethodNode n = new MethodNode(method);
497 MethodNode n0 = putIfAbsent(n);
498 if (n0 == null) {
499 n.linkBefore(this);
500 return true;
501 } else {
502 return n0.addUnlessDeclaredExists(n, declaringClass, this);
503 }
504 }
505
506 @Override
507 public void consolidate(Method method, Class<?> declaringClass) {
508 MethodNode n = new MethodNode(method);
509 MethodNode n0 = putIfAbsent(n);
510 if (n0 == null) {
511 n.linkBefore(this);
512 } else {
513 MethodNode n1 = n0.consolidate(n, declaringClass, this);
514 if (n1 != n0) {
515 put(n1);
516 }
517 }
518 }
519
520 @Override
521 public int getSize() {
522 return size;
523 }
524
525 // Iterable<Method> implementation
526
527 @Override
528 public Iterator<Method> iterator() {
529 return new Iterator<Method>() {
530
531 DLNode dln = getNextDln();
532
533 @Override
534 public boolean hasNext() {
535 return dln != HashArrayImpl.this;
536 }
537
538 @Override
539 public Method next() {
540 if (!hasNext()) {
541 throw new NoSuchElementException();
542 }
543 Method result = ((MethodNode) dln).method;
544 dln = dln.getNextDln();
545 return result;
546 }
547 };
548 }
549
550 // DLNode.Anchor implementation
551
552 private DLNode nextDln = this;
553 private DLNode prevDln = this;
554 private int size;
555
556 @Override
557 public DLNode getNextDln() {
558 return nextDln;
559 }
560
561 @Override
562 public void setNextDln(DLNode nextDln) {
563 this.nextDln = nextDln;
564 }
565
566 @Override
567 public DLNode getPrevDln() {
568 return prevDln;
569 }
570
571 @Override
572 public void setPrevDln(DLNode prevDln) {
573 this.prevDln = prevDln;
574 }
575
576 @Override
577 public void addToSize(int increment) {
578 size += increment;
579 }
580 }
581
582 /**
583 * Simple array based MethodTable implementation for small number of methods.
584 */
585 final class SimpleArrayImpl implements MethodTable {
586
587 private final Method[] methods;
588 private int hwm; // High Water Mark
589
590 SimpleArrayImpl(int expectedMaxSize) {
591 methods = new Method[expectedMaxSize];
592 }
593
594 @Override
595 public void add(Method method) {
596 methods[hwm++] = method;
597 }
598
599 @Override
600 public boolean addUnlessDeclaredExists(Method otherM, Class<?> declaringClass) {
601 for (int i = 0; i < hwm; i++) {
602 Method thisM = methods[i];
603 if (thisM == null || // mind the gap
604 thisM.getReturnType() != otherM.getReturnType() || // not same signature
605 thisM.getName() != otherM.getName() || // Method.name is interned
606 !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
607 continue;
608 }
609 // thisM has same signature as otherM
610
611 if (thisM.getDeclaringClass() == declaringClass) {
612 return false;
613 }
614 // continue with next thisM
615 }
616 // add otherM
617 methods[hwm++] = otherM;
618 return true;
619 }
620
621 @Override
622 public void consolidate(Method otherM, Class<?> declaringClass) {
623 for (int i = 0; i < hwm; i++) {
624 Method thisM = methods[i];
625 if (thisM == null || // mind the gap
626 thisM.getReturnType() != otherM.getReturnType() || // not same signature
627 thisM.getName() != otherM.getName() || // Method.name is interned
628 !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
629 continue;
630 }
631 // thisM has same signature as otherM
632
633 Class<?> thisCl = thisM.getDeclaringClass();
634 Class<?> otherCl = otherM.getDeclaringClass();
635
636 if (thisCl == otherCl || // thisM is the same as otherM OR
637 thisCl == declaringClass) { // thisM is declared by declaringClass
638 // complete without adding otherM
639 return;
640 }
641
642 boolean thisAbstract = Modifier.isAbstract(thisM.getModifiers());
643
644 if (!thisAbstract && // thisM is non-abstract...
645 otherCl.isAssignableFrom(thisCl)) { // ...and overrides otherM
646 // complete without adding otherM
647 return;
648 }
649
650 boolean thisInterface = thisCl.isInterface();
651 boolean otherInterface = otherCl.isInterface();
652
653 if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
654 otherInterface) { //...which wins over interface other.method
655 // complete without adding otherM
656 return;
657 }
658
659 boolean otherAbstract = Modifier.isAbstract(otherM.getModifiers());
660
661 if (!otherAbstract && // other.method is non-abstract...
662 thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
663 // remove this
664 methods[i] = null;
665 continue;
666 }
667
668 if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
669 thisInterface) { //...which wins over interface this.method
670 // remove this
671 methods[i] = null;
672 }
673 // continue with next thisM
674 }
675 // add otherM
676 methods[hwm++] = otherM;
677 }
678
679 @Override
680 public int getSize() {
681 int size = 0;
682 for (int i = 0; i < hwm; i++) {
683 if (methods[i] != null) {
684 size++;
685 }
686 }
687 return size;
688 }
689
690 @Override
691 public Iterator<Method> iterator() {
692 return new Iterator<Method>() {
693 int i = 0;
694 Method next;
695
696 private Method nextMethod() {
697 while (i < hwm && next == null) next = methods[i++];
698 return next;
699 }
700
701 @Override
702 public boolean hasNext() {
703 return nextMethod() != null;
704 }
705
706 @Override
707 public Method next() {
708 Method m = nextMethod();
709 if (m == null) throw new NoSuchElementException();
710 next = null;
711 return m;
712 }
713 };
714 }
715 }
716 }