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 }