1 /******************************************************************************* 2 * Copyright (c) 2000, 2016 IBM Corporation and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * IBM Corporation - initial API and implementation 13 *******************************************************************************/ 14 15 package org.eclipse.jdt.internal.corext.util; 16 17 import java.util.HashMap; 18 import java.util.Map; 19 20 import org.eclipse.core.runtime.Assert; 21 22 import org.eclipse.jdt.core.Flags; 23 import org.eclipse.jdt.core.IJavaElement; 24 import org.eclipse.jdt.core.IMember; 25 import org.eclipse.jdt.core.IMethod; 26 import org.eclipse.jdt.core.IType; 27 import org.eclipse.jdt.core.ITypeHierarchy; 28 import org.eclipse.jdt.core.ITypeParameter; 29 import org.eclipse.jdt.core.JavaModelException; 30 import org.eclipse.jdt.core.Signature; 31 32 33 /** 34 * Finds overriding and overridden methods based on the Java model. 35 */ 36 // @see JDTUIHelperClasses 37 public class MethodOverrideTester { 38 private static class Substitutions { 39 40 public static final Substitutions EMPTY_SUBST= new Substitutions(); 41 42 private HashMap<String, String[]> fMap; 43 Substitutions()44 public Substitutions() { 45 fMap= null; 46 } 47 addSubstitution(String typeVariable, String substitution, String erasure)48 public void addSubstitution(String typeVariable, String substitution, String erasure) { 49 if (fMap == null) { 50 fMap= new HashMap<>(3); 51 } 52 fMap.put(typeVariable, new String[] { substitution, erasure }); 53 } 54 getSubstArray(String typeVariable)55 private String[] getSubstArray(String typeVariable) { 56 if (fMap != null) { 57 return fMap.get(typeVariable); 58 } 59 return null; 60 } 61 getSubstitution(String typeVariable)62 public String getSubstitution(String typeVariable) { 63 String[] subst= getSubstArray(typeVariable); 64 if (subst != null) { 65 return subst[0]; 66 } 67 return null; 68 } 69 getErasure(String typeVariable)70 public String getErasure(String typeVariable) { 71 String[] subst= getSubstArray(typeVariable); 72 if (subst != null) { 73 return subst[1]; 74 } 75 return null; 76 } 77 } 78 79 private final IType fFocusType; 80 private final ITypeHierarchy fHierarchy; 81 82 private Map <IMethod, Substitutions> fMethodSubstitutions; 83 private Map<IType, Substitutions> fTypeVariableSubstitutions; 84 MethodOverrideTester(IType focusType, ITypeHierarchy hierarchy)85 public MethodOverrideTester(IType focusType, ITypeHierarchy hierarchy) { 86 if (focusType == null || hierarchy == null) { 87 throw new IllegalArgumentException(); 88 } 89 fFocusType= focusType; 90 fHierarchy= hierarchy; 91 fTypeVariableSubstitutions= null; 92 fMethodSubstitutions= null; 93 } 94 getFocusType()95 public IType getFocusType() { 96 return fFocusType; 97 } 98 getTypeHierarchy()99 public ITypeHierarchy getTypeHierarchy() { 100 return fHierarchy; 101 } 102 103 /** 104 * Finds the method that declares the given method. A declaring method is the 'original' method declaration that does 105 * not override nor implement a method. <code>null</code> is returned it the given method does not override 106 * a method. When searching, super class are examined before implemented interfaces. 107 * @param overriding the overriding method 108 * @param testVisibility If true the result is tested on visibility. Null is returned if the method is not visible. 109 * @return the declaring method, or <code>null</code> 110 * @throws JavaModelException if a problem occurs 111 */ findDeclaringMethod(IMethod overriding, boolean testVisibility)112 public IMethod findDeclaringMethod(IMethod overriding, boolean testVisibility) throws JavaModelException { 113 IMethod result= null; 114 IMethod overridden= findOverriddenMethod(overriding, testVisibility); 115 while (overridden != null) { 116 result= overridden; 117 overridden= findOverriddenMethod(result, testVisibility); 118 } 119 return result; 120 } 121 122 /** 123 * Finds the method that is overridden by the given method. 124 * First the super class is examined and then the implemented interfaces. 125 * @param overriding the overriding method 126 * @param testVisibility If true the result is tested on visibility. Null is returned if the method is not visible. 127 * @return a method that is directly overridden by the given method, or <code>null</code> 128 * @throws JavaModelException if a problem occurs 129 */ findOverriddenMethod(IMethod overriding, boolean testVisibility)130 public IMethod findOverriddenMethod(IMethod overriding, boolean testVisibility) throws JavaModelException { 131 int flags= overriding.getFlags(); 132 if (Flags.isPrivate(flags) || Flags.isStatic(flags) || overriding.isConstructor()) { 133 return null; 134 } 135 136 IType type= overriding.getDeclaringType(); 137 IType superClass= fHierarchy.getSuperclass(type); 138 if (superClass != null) { 139 IMethod res= findOverriddenMethodInHierarchy(superClass, overriding); 140 if (res != null) { 141 if (!testVisibility || JavaModelUtil.isVisibleInHierarchy(res, type.getPackageFragment())) { 142 return res; 143 } 144 } 145 } 146 for (IType intf : fHierarchy.getSuperInterfaces(type)) { 147 IMethod res= findOverriddenMethodInHierarchy(intf, overriding); 148 if (res != null) { 149 return res; // methods from interfaces are always public and therefore visible 150 } 151 } 152 return null; 153 } 154 155 /** 156 * Finds the directly overridden method in a type and its super types. First the super class is examined and then the implemented interfaces. 157 * With generics it is possible that 2 methods in the same type are overidden at the same time. In that case, the first overridden method found is returned. 158 * @param type The type to find methods in 159 * @param overriding The overriding method 160 * @return The first overridden method or <code>null</code> if no method is overridden 161 * @throws JavaModelException if a problem occurs 162 */ findOverriddenMethodInHierarchy(IType type, IMethod overriding)163 public IMethod findOverriddenMethodInHierarchy(IType type, IMethod overriding) throws JavaModelException { 164 IMethod method= findOverriddenMethodInType(type, overriding); 165 if (method != null) { 166 return method; 167 } 168 IType superClass= fHierarchy.getSuperclass(type); 169 if (superClass != null) { 170 IMethod res= findOverriddenMethodInHierarchy(superClass, overriding); 171 if (res != null) { 172 return res; 173 } 174 } 175 for (IType superInterface : fHierarchy.getSuperInterfaces(type)) { 176 IMethod res= findOverriddenMethodInHierarchy(superInterface, overriding); 177 if (res != null) { 178 return res; 179 } 180 } 181 return method; 182 } 183 184 /** 185 * Finds an overridden method in a type. With generics it is possible that 2 methods in the same type are overridden at the same time. 186 * In that case the first overridden method found is returned. 187 * @param overriddenType The type to find methods in 188 * @param overriding The overriding method 189 * @return The first overridden method or <code>null</code> if no method is overridden 190 * @throws JavaModelException if a problem occurs 191 */ findOverriddenMethodInType(IType overriddenType, IMethod overriding)192 public IMethod findOverriddenMethodInType(IType overriddenType, IMethod overriding) throws JavaModelException { 193 int flags= overriding.getFlags(); 194 if (Flags.isPrivate(flags) || Flags.isStatic(flags) || overriding.isConstructor()) 195 return null; 196 for (IMethod overridden : overriddenType.getMethods()) { 197 flags= overridden.getFlags(); 198 if (Flags.isPrivate(flags) || Flags.isStatic(flags) || overridden.isConstructor()) 199 continue; 200 if (isSubsignature(overriding, overridden)) { 201 return overridden; 202 } 203 } 204 return null; 205 } 206 207 /** 208 * Finds an overriding method in a type. 209 * @param overridingType The type to find methods in 210 * @param overridden The overridden method 211 * @return The overriding method or <code>null</code> if no method is overriding. 212 * @throws JavaModelException if a problem occurs 213 */ findOverridingMethodInType(IType overridingType, IMethod overridden)214 public IMethod findOverridingMethodInType(IType overridingType, IMethod overridden) throws JavaModelException { 215 int flags= overridden.getFlags(); 216 if (Flags.isPrivate(flags) || Flags.isStatic(flags) || overridden.isConstructor()) 217 return null; 218 for (IMethod overriding : overridingType.getMethods()) { 219 flags= overriding.getFlags(); 220 if (Flags.isPrivate(flags) || Flags.isStatic(flags) || overriding.isConstructor()) 221 continue; 222 if (isSubsignature(overriding, overridden)) { 223 return overriding; 224 } 225 } 226 return null; 227 } 228 229 /** 230 * Tests if a method is a subsignature of another method. 231 * @param overriding overriding method (m1) 232 * @param overridden overridden method (m2) 233 * @return <code>true</code> iff the method <code>m1</code> is a subsignature of the method <code>m2</code>. 234 * This is one of the requirements for m1 to override m2. 235 * Accessibility and return types are not taken into account. 236 * Note that subsignature is <em>not</em> symmetric! 237 * @throws JavaModelException if a problem occurs 238 */ isSubsignature(IMethod overriding, IMethod overridden)239 public boolean isSubsignature(IMethod overriding, IMethod overridden) throws JavaModelException { 240 if (!overridden.getElementName().equals(overriding.getElementName())) { 241 return false; 242 } 243 int nParameters= overridden.getNumberOfParameters(); 244 if (nParameters != overriding.getNumberOfParameters()) { 245 return false; 246 } 247 248 if (!hasCompatibleTypeParameters(overriding, overridden)) { 249 return false; 250 } 251 252 return nParameters == 0 || hasCompatibleParameterTypes(overriding, overridden); 253 } 254 hasCompatibleTypeParameters(IMethod overriding, IMethod overridden)255 private boolean hasCompatibleTypeParameters(IMethod overriding, IMethod overridden) throws JavaModelException { 256 ITypeParameter[] overriddenTypeParameters= overridden.getTypeParameters(); 257 ITypeParameter[] overridingTypeParameters= overriding.getTypeParameters(); 258 int nOverridingTypeParameters= overridingTypeParameters.length; 259 if (overriddenTypeParameters.length != nOverridingTypeParameters) { 260 return nOverridingTypeParameters == 0; 261 } 262 Substitutions overriddenSubst= getMethodSubstitions(overridden); 263 Substitutions overridingSubst= getMethodSubstitions(overriding); 264 for (int i= 0; i < nOverridingTypeParameters; i++) { 265 String erasure1= overriddenSubst.getErasure(overriddenTypeParameters[i].getElementName()); 266 String erasure2= overridingSubst.getErasure(overridingTypeParameters[i].getElementName()); 267 if (erasure1 == null || !erasure1.equals(erasure2)) { 268 return false; 269 } 270 // comparing only the erasure is not really correct: Need to compare all bounds, that can be in different order 271 int nBounds= overriddenTypeParameters[i].getBounds().length; 272 if (nBounds > 1 && nBounds != overridingTypeParameters[i].getBounds().length) { 273 return false; 274 } 275 } 276 return true; 277 } 278 hasCompatibleParameterTypes(IMethod overriding, IMethod overridden)279 private boolean hasCompatibleParameterTypes(IMethod overriding, IMethod overridden) throws JavaModelException { 280 String[] overriddenParamTypes= overridden.getParameterTypes(); 281 String[] overridingParamTypes= overriding.getParameterTypes(); 282 283 String[] substitutedOverriding= new String[overridingParamTypes.length]; 284 boolean testErasure= false; 285 286 for (int i= 0; i < overridingParamTypes.length; i++) { 287 String overriddenParamSig= overriddenParamTypes[i]; 288 String overriddenParamName= getSubstitutedTypeName(overriddenParamSig, overridden); 289 String overridingParamName= getSubstitutedTypeName(overridingParamTypes[i], overriding); 290 substitutedOverriding[i]= overridingParamName; 291 if (!overriddenParamName.equals(overridingParamName)) { 292 testErasure= true; 293 break; 294 } 295 } 296 if (testErasure) { 297 for (int i= 0; i < overridingParamTypes.length; i++) { 298 String overriddenParamSig= overriddenParamTypes[i]; 299 String overriddenParamName= getErasedTypeName(overriddenParamSig, overridden); 300 String overridingParamName= substitutedOverriding[i]; 301 if (overridingParamName == null) 302 overridingParamName= getSubstitutedTypeName(overridingParamTypes[i], overriding); 303 if (!overriddenParamName.equals(overridingParamName)) { 304 return false; 305 } 306 } 307 } 308 return true; 309 } 310 getVariableSubstitution(IMember context, String variableName)311 private String getVariableSubstitution(IMember context, String variableName) throws JavaModelException { 312 IType type; 313 if (context instanceof IMethod) { 314 String subst= getMethodSubstitions((IMethod) context).getSubstitution(variableName); 315 if (subst != null) { 316 return subst; 317 } 318 type= context.getDeclaringType(); 319 } else { 320 type= (IType) context; 321 } 322 String subst= getTypeSubstitions(type).getSubstitution(variableName); 323 if (subst != null) { 324 return subst; 325 } 326 IJavaElement parent= type.getParent(); 327 if (parent instanceof IMethod) { 328 return getVariableSubstitution((IMethod) parent, variableName); 329 } else if (type.getDeclaringType() != null) { 330 return getVariableSubstitution(type.getDeclaringType(), variableName); 331 } 332 return variableName; // not a type variable 333 } 334 getVariableErasure(IMember context, String variableName)335 private String getVariableErasure(IMember context, String variableName) throws JavaModelException { 336 IType type; 337 if (context instanceof IMethod) { 338 String subst= getMethodSubstitions((IMethod) context).getErasure(variableName); 339 if (subst != null) { 340 return subst; 341 } 342 type= context.getDeclaringType(); 343 } else { 344 type= (IType) context; 345 } 346 String subst= getTypeSubstitions(type).getErasure(variableName); 347 if (subst != null) { 348 return subst; 349 } 350 IJavaElement parent= type.getParent(); 351 if (parent instanceof IMethod) { 352 return getVariableErasure((IMethod) parent, variableName); 353 } else if (type.getDeclaringType() != null) { 354 return getVariableErasure(type.getDeclaringType(), variableName); 355 } 356 return variableName; // not a type variable 357 } 358 359 /* 360 * Returns the substitutions for a method's type parameters 361 */ getMethodSubstitions(IMethod method)362 private Substitutions getMethodSubstitions(IMethod method) throws JavaModelException { 363 if (fMethodSubstitutions == null) { 364 fMethodSubstitutions= new LRUMap<>(3); 365 } 366 367 Substitutions s= fMethodSubstitutions.get(method); 368 if (s == null) { 369 ITypeParameter[] typeParameters= method.getTypeParameters(); 370 if (typeParameters.length == 0) { 371 s= Substitutions.EMPTY_SUBST; 372 } else { 373 IType instantiatedType= method.getDeclaringType(); 374 s= new Substitutions(); 375 for (int i= 0; i < typeParameters.length; i++) { 376 ITypeParameter curr= typeParameters[i]; 377 s.addSubstitution(curr.getElementName(), '+' + String.valueOf(i), getTypeParameterErasure(curr, instantiatedType)); 378 } 379 } 380 fMethodSubstitutions.put(method, s); 381 } 382 return s; 383 } 384 385 /* 386 * Returns the substitutions for a type's type parameters 387 */ getTypeSubstitions(IType type)388 private Substitutions getTypeSubstitions(IType type) throws JavaModelException { 389 if (fTypeVariableSubstitutions == null) { 390 fTypeVariableSubstitutions= new HashMap<>(); 391 computeSubstitutions(fFocusType, null, null); 392 } 393 Substitutions subst= fTypeVariableSubstitutions.get(type); 394 if (subst == null) { 395 return Substitutions.EMPTY_SUBST; 396 } 397 return subst; 398 } 399 computeSubstitutions(IType instantiatedType, IType instantiatingType, String[] typeArguments)400 private void computeSubstitutions(IType instantiatedType, IType instantiatingType, String[] typeArguments) throws JavaModelException { 401 Substitutions s= new Substitutions(); 402 fTypeVariableSubstitutions.put(instantiatedType, s); 403 404 ITypeParameter[] typeParameters= instantiatedType.getTypeParameters(); 405 406 if (instantiatingType == null) { // the focus type 407 for (ITypeParameter curr : typeParameters) { 408 // use star to make type variables different from type refs 409 s.addSubstitution(curr.getElementName(), '*' + curr.getElementName(), getTypeParameterErasure(curr, instantiatedType)); 410 } 411 } else { 412 if (typeParameters.length == typeArguments.length) { 413 for (int i= 0; i < typeParameters.length; i++) { 414 ITypeParameter curr= typeParameters[i]; 415 String substString= getSubstitutedTypeName(typeArguments[i], instantiatingType); // substitute in the context of the instantiatingType 416 String erasure= getErasedTypeName(typeArguments[i], instantiatingType); // get the erasure from the type argument 417 s.addSubstitution(curr.getElementName(), substString, erasure); 418 } 419 } else if (typeArguments.length == 0) { // raw type reference 420 for (ITypeParameter curr : typeParameters) { 421 String erasure= getTypeParameterErasure(curr, instantiatedType); 422 s.addSubstitution(curr.getElementName(), erasure, erasure); 423 } 424 } else { 425 // code with errors 426 } 427 } 428 String superclassTypeSignature= instantiatedType.getSuperclassTypeSignature(); 429 if (superclassTypeSignature != null) { 430 String[] superTypeArguments= Signature.getTypeArguments(superclassTypeSignature); 431 IType superclass= fHierarchy.getSuperclass(instantiatedType); 432 if (superclass != null && !fTypeVariableSubstitutions.containsKey(superclass)) { 433 computeSubstitutions(superclass, instantiatedType, superTypeArguments); 434 } 435 } 436 String[] superInterfacesTypeSignature; 437 if (instantiatedType.isAnonymous()) { 438 // special case: superinterface is also returned by IType#getSuperclassTypeSignature() 439 superInterfacesTypeSignature= new String[] { superclassTypeSignature }; 440 } else { 441 superInterfacesTypeSignature= instantiatedType.getSuperInterfaceTypeSignatures(); 442 } 443 int nInterfaces= superInterfacesTypeSignature.length; 444 if (nInterfaces > 0) { 445 IType[] superInterfaces= fHierarchy.getSuperInterfaces(instantiatedType); 446 if (superInterfaces.length == nInterfaces) { 447 for (int i= 0; i < nInterfaces; i++) { 448 String[] superTypeArguments= Signature.getTypeArguments(superInterfacesTypeSignature[i]); 449 IType superInterface= superInterfaces[i]; 450 if (!fTypeVariableSubstitutions.containsKey(superInterface)) { 451 computeSubstitutions(superInterface, instantiatedType, superTypeArguments); 452 } 453 } 454 } 455 } 456 } 457 getTypeParameterErasure(ITypeParameter typeParameter, IType context)458 private String getTypeParameterErasure(ITypeParameter typeParameter, IType context) throws JavaModelException { 459 String[] bounds= typeParameter.getBounds(); 460 if (bounds.length > 0) { 461 return getErasedTypeName(Signature.createTypeSignature(bounds[0], false), context); 462 } 463 return "Object"; //$NON-NLS-1$ 464 } 465 466 467 /** 468 * Translates the type signature to a 'normalized' type name where all variables are substituted for the given type or method context. 469 * The returned name contains only simple names and can be used to compare against other substituted type names 470 * @param typeSig The type signature to translate 471 * @param context The context for the substitution 472 * @return a type name 473 * @throws JavaModelException if a problem occurs 474 */ getSubstitutedTypeName(String typeSig, IMember context)475 private String getSubstitutedTypeName(String typeSig, IMember context) throws JavaModelException { 476 return internalGetSubstitutedTypeName(typeSig, context, false, new StringBuffer()).toString(); 477 } 478 getErasedTypeName(String typeSig, IMember context)479 private String getErasedTypeName(String typeSig, IMember context) throws JavaModelException { 480 return internalGetSubstitutedTypeName(typeSig, context, true, new StringBuffer()).toString(); 481 } 482 internalGetSubstitutedTypeName(String typeSig, IMember context, boolean erasure, StringBuffer buf)483 private StringBuffer internalGetSubstitutedTypeName(String typeSig, IMember context, boolean erasure, StringBuffer buf) throws JavaModelException { 484 int sigKind= Signature.getTypeSignatureKind(typeSig); 485 switch (sigKind) { 486 case Signature.BASE_TYPE_SIGNATURE: 487 return buf.append(Signature.toString(typeSig)); 488 case Signature.ARRAY_TYPE_SIGNATURE: 489 internalGetSubstitutedTypeName(Signature.getElementType(typeSig), context, erasure, buf); 490 for (int i= Signature.getArrayCount(typeSig); i > 0; i--) { 491 buf.append('[').append(']'); 492 } 493 return buf; 494 case Signature.CLASS_TYPE_SIGNATURE: { 495 String erasureSig= Signature.getTypeErasure(typeSig); 496 String erasureName= Signature.getSimpleName(Signature.toString(erasureSig)); 497 498 char ch= erasureSig.charAt(0); 499 if (ch == Signature.C_RESOLVED) { 500 buf.append(erasureName); 501 } else if (ch == Signature.C_UNRESOLVED) { // could be a type variable 502 if (erasure) { 503 buf.append(getVariableErasure(context, erasureName)); 504 } else { 505 buf.append(getVariableSubstitution(context, erasureName)); 506 } 507 } else { 508 Assert.isTrue(false, "Unknown class type signature"); //$NON-NLS-1$ 509 } 510 if (!erasure) { 511 String[] typeArguments= Signature.getTypeArguments(typeSig); 512 if (typeArguments.length > 0) { 513 buf.append('<'); 514 for (int i= 0; i < typeArguments.length; i++) { 515 if (i > 0) { 516 buf.append(','); 517 } 518 internalGetSubstitutedTypeName(typeArguments[i], context, erasure, buf); 519 } 520 buf.append('>'); 521 } 522 } 523 return buf; 524 } 525 case Signature.TYPE_VARIABLE_SIGNATURE: 526 String varName= Signature.toString(typeSig); 527 if (erasure) { 528 return buf.append(getVariableErasure(context, varName)); 529 } else { 530 return buf.append(getVariableSubstitution(context, varName)); 531 } 532 case Signature.WILDCARD_TYPE_SIGNATURE: { 533 buf.append('?'); 534 char ch= typeSig.charAt(0); 535 if (ch == Signature.C_STAR) { 536 return buf; 537 } else if (ch == Signature.C_EXTENDS) { 538 buf.append(" extends "); //$NON-NLS-1$ 539 } else { 540 buf.append(" super "); //$NON-NLS-1$ 541 } 542 return internalGetSubstitutedTypeName(typeSig.substring(1), context, erasure, buf); 543 } 544 case Signature.CAPTURE_TYPE_SIGNATURE: 545 return internalGetSubstitutedTypeName(typeSig.substring(1), context, erasure, buf); 546 default: 547 Assert.isTrue(false, "Unhandled type signature kind"); //$NON-NLS-1$ 548 return buf; 549 } 550 } 551 552 } 553