001 /* Copyright (c) 2005-2008, Torbjorn Ekman 002 * All rights reserved. 003 * 004 * Redistribution and use in source and binary forms, with or without 005 * modification, are permitted provided that the following conditions are met: 006 * 007 * 1. Redistributions of source code must retain the above copyright notice, 008 * this list of conditions and the following disclaimer. 009 * 010 * 2. Redistributions in binary form must reproduce the above copyright notice, 011 * this list of conditions and the following disclaimer in the documentation 012 * and/or other materials provided with the distribution. 013 * 014 * 3. Neither the name of the copyright holder nor the names of its 015 * contributors may be used to endorse or promote products derived from this 016 * software without specific prior written permission. 017 * 018 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 019 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 020 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 021 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 022 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 023 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 024 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 025 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 026 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 027 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 028 * POSSIBILITY OF SUCH DAMAGE. 029 */ 030 031 import java.util.*; 032 033 aspect GenericMethodsInference { 034 syn boolean TypeDecl.isUnboxedPrimitive() = this instanceof PrimitiveType && isPrimitive(); 035 036 syn boolean TypeDecl.involvesTypeParameters() circular [false] = false; 037 eq TypeVariable.involvesTypeParameters() = true; 038 eq ArrayDecl.involvesTypeParameters() = componentType().involvesTypeParameters(); 039 eq ParClassDecl.involvesTypeParameters() { 040 for (int i = 0; i < getNumArgument(); i++) { 041 if (getArgument(i).type().involvesTypeParameters()) { 042 return true; 043 } 044 } 045 return false; 046 } 047 eq ParInterfaceDecl.involvesTypeParameters() { 048 for (int i = 0; i < getNumArgument(); i++) { 049 if (getArgument(i).type().involvesTypeParameters()) { 050 return true; 051 } 052 } 053 return false; 054 } 055 eq WildcardExtendsType.involvesTypeParameters() = extendsType().involvesTypeParameters(); 056 eq WildcardSuperType.involvesTypeParameters() = superType().involvesTypeParameters(); 057 058 inh TypeDecl Expr.assignConvertedType(); 059 eq VariableDeclaration.getInit().assignConvertedType() = type(); 060 eq FieldDeclaration.getInit().assignConvertedType() = type(); 061 eq AssignSimpleExpr.getSource().assignConvertedType() = getDest().type(); 062 eq ArrayInit.getInit().assignConvertedType() = declType().componentType(); 063 eq ReturnStmt.getResult().assignConvertedType() = returnType(); 064 eq Program.getChild().assignConvertedType() = typeNull(); 065 066 eq MethodAccess.getArg().assignConvertedType() = typeObject(); 067 068 inh TypeDecl Expr.typeObject(); 069 070 /** 071 * Infer type arguments based on the actual arguments and result assignment type. 072 */ 073 public Collection<TypeDecl> Expr.computeConstraints( 074 TypeDecl resultType, 075 List<ParameterDeclaration> params, 076 List<Expr> args, 077 List<TypeVariable> typeParams) { 078 Constraints c = new Constraints(); 079 // Store type parameters. 080 for (int i = 0; i < typeParams.getNumChild(); i++) { 081 c.addTypeVariable(typeParams.getChild(i)); 082 } 083 084 // Add initial constraints. 085 for (int i = 0; i < args.getNumChild(); i++) { 086 TypeDecl A = args.getChild(i).type(); 087 int index = i >= params.getNumChild() ? params.getNumChild() - 1 : i; 088 TypeDecl F = params.getChild(index).type(); 089 if (params.getChild(index) instanceof VariableArityParameterDeclaration 090 && (args.getNumChild() != params.getNumChild() || !A.isArrayDecl())) { 091 F = F.componentType(); 092 } 093 c.convertibleTo(A, F); 094 } 095 096 if (c.rawAccess) { 097 return new ArrayList<TypeDecl>(); 098 } 099 100 //c.printConstraints(); 101 //System.err.println("Resolving equality constraints"); 102 c.resolveEqualityConstraints(); 103 //c.printConstraints(); 104 105 //System.err.println("Resolving supertype constraints"); 106 c.resolveSupertypeConstraints(); 107 //c.printConstraints(); 108 109 //System.err.println("Resolving unresolved type arguments"); 110 //c.resolveBounds(); 111 //c.printConstraints(); 112 113 if (c.unresolvedTypeArguments()) { 114 TypeDecl S = assignConvertedType(); 115 if (S.isUnboxedPrimitive()) { 116 S = S.boxed(); 117 } 118 TypeDecl R = resultType; 119 // TODO: replace all uses of type variables in R with their inferred types 120 TypeDecl Rprime = R; 121 if (R.isVoid()) { 122 R = typeObject(); 123 } 124 c.convertibleFrom(S, R); 125 // TODO: additional constraints 126 127 c.resolveEqualityConstraints(); 128 c.resolveSupertypeConstraints(); 129 //c.resolveBounds(); 130 131 c.resolveSubtypeConstraints(); 132 } 133 134 return c.typeArguments(); 135 } 136 137 class Constraints { 138 static class ConstraintSet { 139 public Collection supertypeConstraints = new HashSet(4); 140 public Collection subtypeConstraints = new HashSet(4); 141 public Collection equaltypeConstraints = new HashSet(4); 142 public TypeDecl typeArgument; 143 } 144 private Collection typeVariables; 145 private Map constraintsMap; 146 public boolean rawAccess = false; 147 148 public Constraints() { 149 typeVariables = new ArrayList(4); 150 constraintsMap = new HashMap(); 151 } 152 153 public void addTypeVariable(TypeVariable T) { 154 if (!typeVariables.contains(T)) { 155 typeVariables.add(T); 156 constraintsMap.put(T, new ConstraintSet()); 157 } 158 } 159 160 public boolean unresolvedTypeArguments() { 161 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 162 TypeVariable T = (TypeVariable) iter.next(); 163 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 164 if (set.typeArgument == null) { 165 return true; 166 } 167 } 168 return false; 169 } 170 171 public void printConstraints() { 172 System.err.println("Current constraints:"); 173 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 174 TypeVariable T = (TypeVariable) iter.next(); 175 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 176 for (Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) { 177 TypeDecl U = (TypeDecl) i2.next(); 178 System.err.println(" " + T.fullName() + " :> " + U.fullName()); 179 } 180 for (Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) { 181 TypeDecl U = (TypeDecl) i2.next(); 182 System.err.println(" " + T.fullName() + " <: " + U.fullName()); 183 } 184 for (Iterator i2 = set.equaltypeConstraints.iterator(); i2.hasNext(); ) { 185 TypeDecl U = (TypeDecl) i2.next(); 186 System.err.println(" " + T.fullName() + " = " + U.fullName()); 187 } 188 } 189 } 190 191 192 public void resolveBounds() { 193 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 194 TypeVariable T = (TypeVariable) iter.next(); 195 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 196 if (set.typeArgument == null) { 197 set.typeArgument = T.getTypeBound(0).type(); 198 } 199 } 200 } 201 202 public void resolveEqualityConstraints() { 203 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 204 TypeVariable T = (TypeVariable) iter.next(); 205 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 206 boolean done = false; 207 for (Iterator i2 = set.equaltypeConstraints.iterator(); !done && i2.hasNext(); ) { 208 TypeDecl U = (TypeDecl) i2.next(); 209 if (!typeVariables.contains(U)) { 210 replaceEqualityConstraints(T, U); // replace equality constraints for other type variables 211 set.equaltypeConstraints.clear(); 212 set.equaltypeConstraints.add(U); // make U is the only equality constraint for T 213 set.typeArgument = U; 214 done = true; // continue on next type variable 215 } else if (T == U) { 216 //i2.remove(); // discard constraint 217 } else { 218 replaceAllConstraints(T, U); // rewrite all constraints involving T to use U instead 219 done = true; // continue on next type variable 220 } 221 } 222 if (set.typeArgument == null && set.equaltypeConstraints.size() == 1 && set.equaltypeConstraints.contains(T)) { 223 set.typeArgument = T; 224 } 225 } 226 } 227 228 public void replaceEqualityConstraints(TypeDecl before, TypeDecl after) { 229 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 230 TypeVariable T = (TypeVariable) iter.next(); 231 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 232 replaceConstraints(set.equaltypeConstraints, before, after); 233 } 234 } 235 236 public void replaceAllConstraints(TypeDecl before, TypeDecl after) { 237 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 238 TypeVariable T = (TypeVariable) iter.next(); 239 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 240 replaceConstraints(set.supertypeConstraints, before, after); 241 replaceConstraints(set.subtypeConstraints, before, after); 242 replaceConstraints(set.equaltypeConstraints, before, after); 243 } 244 } 245 246 private void replaceConstraints(Collection constraints, TypeDecl before, TypeDecl after) { 247 Collection newConstraints = new ArrayList(); 248 for (Iterator i2 = constraints.iterator(); i2.hasNext(); ) { 249 TypeDecl U = (TypeDecl) i2.next(); 250 if (U == before) { // TODO: fix parameterized type 251 i2.remove(); 252 newConstraints.add(after); 253 } 254 } 255 constraints.addAll(newConstraints); 256 } 257 258 public void resolveSubtypeConstraints() { 259 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 260 TypeVariable T = (TypeVariable) iter.next(); 261 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 262 if ((!set.subtypeConstraints.isEmpty() || T.getNumTypeBound() > 0) && set.typeArgument == null) { 263 ArrayList bounds = new ArrayList(); 264 for (Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) { 265 bounds.add(i2.next()); 266 } 267 for (int i = 0; i < T.getNumTypeBound(); i++) { 268 bounds.add(T.getTypeBound(i).type()); 269 } 270 set.typeArgument = GLBTypeFactory.glb(bounds); 271 } 272 } 273 } 274 275 public void resolveSupertypeConstraints() { 276 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 277 TypeVariable T = (TypeVariable) iter.next(); 278 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 279 if (!set.supertypeConstraints.isEmpty() && set.typeArgument == null) { 280 //TypeDecl typeDecl = lub(set.supertypeConstraints); 281 TypeDecl typeDecl = T.lookupLUBType(set.supertypeConstraints).lub(); 282 set.typeArgument = typeDecl; 283 /* 284 TypeDecl EC = (TypeDecl) set.supertypeConstraints.get(0); 285 for (Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) { 286 TypeDecl U = (TypeDecl) i2.next(); 287 TypeDecl ST = U; 288 TypeDecl EST = ST.erasure(); 289 EC = intersect(EC, EST); 290 } 291 TypeDecl MEC = EC; 292 //System.err.println(" MEC(" + T.fullName() + ") = " + MEC.fullName()); 293 set.typeArgument = MEC; 294 */ 295 } 296 } 297 } 298 299 /* 300 // operates only on erased types. does it matter? (no type variables, no partypedecl) 301 private TypeDecl intersect(TypeDecl t1, TypeDecl t2) { 302 if (t1.instanceOf(t2)) { 303 return t1; 304 } else if (t2.instanceOf(t1)) { 305 return t2; 306 } else { 307 HashSet set = new HashSet(); 308 for (Iterator iter = directSupertypes(t1).iterator(); iter.hasNext(); ) { 309 TypeDecl t1Super = (TypeDecl) iter.next(); 310 set.add(intersect(t1Super, t2)); 311 } 312 if (set.isEmpty()) { 313 throw new Error("Empty intersection of " + t1.fullName() + " and " + t2.fullName()); 314 } 315 TypeDecl lowestType = (TypeDecl) set.iterator().next(); 316 for (Iterator iter = set.iterator(); iter.hasNext(); ) { 317 TypeDecl type = (TypeDecl) iter.next(); 318 if (type.instanceOf(lowestType)) { 319 lowestType = type; 320 } else if (!lowestType.instanceOf(type)) { 321 throw new Error("Several leaf types in intersection, " + lowestType.fullName() + " and " + type.fullName()); 322 } 323 } 324 return lowestType; 325 } 326 } 327 */ 328 329 public static HashSet directSupertypes(TypeDecl t) { 330 if (t instanceof ClassDecl) { 331 ClassDecl type = (ClassDecl) t; 332 HashSet set = new HashSet(); 333 if (type.hasSuperclass()) { 334 set.add(type.superclass()); 335 } 336 for (int i = 0; i < type.getNumImplements(); i++) { 337 set.add(type.getImplements(i).type()); 338 } 339 return set; 340 } else if (t instanceof InterfaceDecl) { 341 InterfaceDecl type = (InterfaceDecl) t; 342 HashSet set = new HashSet(); 343 for (int i = 0; i < type.getNumSuperInterface(); i++) { 344 set.add(type.getSuperInterface(i).type()); 345 } 346 return set; 347 } else if (t instanceof TypeVariable) { 348 TypeVariable type = (TypeVariable) t; 349 HashSet set = new HashSet(); 350 for (int i = 0; i < type.getNumTypeBound(); i++) { 351 set.add(type.getTypeBound(i).type()); 352 } 353 return set; 354 } else { 355 throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName()); 356 } 357 } 358 359 public static HashSet parameterizedSupertypes(TypeDecl t) { 360 HashSet result = new HashSet(); 361 addParameterizedSupertypes(t, new HashSet(), result); 362 return result; 363 } 364 public static void addParameterizedSupertypes(TypeDecl t, HashSet processed, HashSet result) { 365 if (!processed.contains(t)) { 366 processed.add(t); 367 if (t.isParameterizedType() /*&& !t.isRawType()*/) { 368 result.add(t); 369 } 370 for (Iterator iter = directSupertypes(t).iterator(); iter.hasNext(); ) { 371 TypeDecl typeDecl = (TypeDecl) iter.next(); 372 addParameterizedSupertypes(typeDecl, processed, result); 373 } 374 } 375 } 376 377 public Collection<TypeDecl> typeArguments() { 378 Collection<TypeDecl> list = new ArrayList<TypeDecl>(typeVariables.size()); 379 for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) { 380 TypeVariable T = (TypeVariable) iter.next(); 381 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 382 list.add(set.typeArgument); 383 } 384 return list; 385 } 386 387 public void addSupertypeConstraint(TypeDecl T, TypeDecl A) { 388 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 389 set.supertypeConstraints.add(A); 390 //System.out.println(T.name() + " :> " + A.fullName()); 391 } 392 public void addSubtypeConstraint(TypeDecl T, TypeDecl A) { 393 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 394 set.subtypeConstraints.add(A); 395 //System.out.println(T.name() + " <: " + A.fullName()); 396 } 397 public void addEqualConstraint(TypeDecl T, TypeDecl A) { 398 ConstraintSet set = (ConstraintSet) constraintsMap.get(T); 399 set.equaltypeConstraints.add(A); 400 //System.out.println(T.name() + " = " + A.fullName()); 401 } 402 403 public void convertibleTo(TypeDecl A, TypeDecl F) { 404 //System.out.println("Convertible to called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")"); 405 // If F does not involve a type parameter Tj then con constraint is implied on Tj 406 if (!F.involvesTypeParameters()) { 407 return; 408 } 409 // If A is the type of null, no constraint is implied on Tj. 410 if (A.isNull()) { 411 return; 412 } 413 // If A is a primitive type, then A is converted to a reference type U via boxing conversion 414 // and this algorithm is applied recursively to the constraint U << F. 415 if (A.isUnboxedPrimitive()) { 416 TypeDecl U = A.boxed(); 417 convertibleTo(U, F); 418 } 419 // If F = Tj, then the constrint Tj :> A is implied 420 else if (F instanceof TypeVariable) { 421 if (typeVariables.contains(F)) { 422 addSupertypeConstraint(F, A); 423 } 424 } 425 // If F = U[], where the type U involves Tj, then if A is an array type V[] 426 // or a type variable with an upper bound that is an array type V[], 427 // where V is a reference type, this algorithm is applied recursively 428 // to the constraint V << U 429 else if (F.isArrayDecl()) { 430 //System.out.println("convertibleTo array decl"); 431 TypeDecl U = ((ArrayDecl) F).componentType(); 432 if (!U.involvesTypeParameters()) { 433 return; 434 } 435 if (A.isArrayDecl()) { 436 TypeDecl V = ((ArrayDecl) A).componentType(); 437 if (V.isReferenceType()) { 438 convertibleTo(V, U); 439 } 440 } else if (A.isTypeVariable()) { 441 TypeVariable t = (TypeVariable) A; 442 for (int i = 0; i < t.getNumTypeBound(); i++) { 443 TypeDecl typeBound = t.getTypeBound(i).type(); 444 if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) { 445 TypeDecl V = ((ArrayDecl) typeBound).componentType(); 446 convertibleTo(V, U); 447 } 448 } 449 } 450 } else if (F instanceof ParTypeDecl && !F.isRawType()) { 451 for (Iterator iter = parameterizedSupertypes(A).iterator(); iter.hasNext(); ) { 452 ParTypeDecl PF = (ParTypeDecl) F; 453 ParTypeDecl PA = (ParTypeDecl) iter.next(); 454 if (PF.genericDecl() == PA.genericDecl()) { 455 if (A.isRawType()) { 456 rawAccess = true; 457 } else 458 for (int i = 0; i < PF.getNumArgument(); i++) { 459 TypeDecl T = PF.getArgument(i).type(); 460 if (T.involvesTypeParameters()) { 461 if (!T.isWildcard()) { 462 TypeDecl U = T; 463 TypeDecl V = PA.getArgument(i).type(); 464 constraintEqual(V, U); 465 } else if (T instanceof WildcardExtendsType) { 466 TypeDecl U = ((WildcardExtendsType) T).getAccess().type(); 467 TypeDecl S = PA.getArgument(i).type(); 468 if (!S.isWildcard()) { 469 TypeDecl V = S; 470 convertibleTo(V, U); 471 } else if (S instanceof WildcardExtendsType) { 472 TypeDecl V = ((WildcardExtendsType) S).getAccess().type(); 473 convertibleTo(V, U); 474 } 475 } else if (T instanceof WildcardSuperType) { 476 TypeDecl U = ((WildcardSuperType) T).getAccess().type(); 477 TypeDecl S = PA.getArgument(i).type(); 478 if (!S.isWildcard()) { 479 TypeDecl V = S; 480 convertibleFrom(V, U); 481 } else if (S instanceof WildcardSuperType) { 482 TypeDecl V = ((WildcardSuperType) S).getAccess().type(); 483 convertibleFrom(V, U); 484 } 485 } 486 } 487 } 488 } 489 } 490 } 491 } 492 493 494 public void convertibleFrom(TypeDecl A, TypeDecl F) { 495 //System.out.println("ConvertibleFrom called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")"); 496 // If F does not involve a type parameter Tj then con constraint is implied on Tj 497 if (!F.involvesTypeParameters()) { 498 return; 499 } 500 // If A is the type of null, no constraint is implied on Tj. 501 else if (A.isNull()) { 502 return; 503 } else if (F instanceof TypeVariable) { 504 if (typeVariables.contains(F)) { 505 addSubtypeConstraint(F, A); 506 } 507 } else if (F.isArrayDecl()) { 508 TypeDecl U = ((ArrayDecl) F).componentType(); 509 if (A.isArrayDecl()) { 510 TypeDecl V = ((ArrayDecl) A).componentType(); 511 convertibleFrom(V, U); 512 } else if (A.isTypeVariable()) { 513 TypeVariable t = (TypeVariable) A; 514 for (int i = 0; i < t.getNumTypeBound(); i++) { 515 TypeDecl typeBound = t.getTypeBound(i).type(); 516 if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) { 517 TypeDecl V = ((ArrayDecl) typeBound).componentType(); 518 convertibleFrom(V, U); 519 } 520 } 521 } 522 } else if (F instanceof ParTypeDecl && !F.isRawType() && A instanceof ParTypeDecl && !A.isRawType()) { 523 ParTypeDecl PF = (ParTypeDecl) F; 524 ParTypeDecl PA = (ParTypeDecl) A; 525 TypeDecl G = PF.genericDecl(); 526 TypeDecl H = PA.genericDecl(); 527 for (int i = 0; i < PF.getNumArgument(); i++) { 528 TypeDecl T = PF.getArgument(i).type(); 529 if (T.involvesTypeParameters()) { 530 // If F has the form G<...,U,...> where U is a type expression that involves Tj 531 if (!T.isWildcard()) { 532 TypeDecl U = T; 533 if (G.instanceOf(H)) { 534 if (H != G) { 535 for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) { 536 TypeDecl V = (TypeDecl) iter.next(); 537 if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) { 538 if (F.instanceOf(V)) { 539 convertibleFrom(A, V); 540 } 541 } 542 } 543 } else if (PF.getNumArgument() == PA.getNumArgument()) { 544 TypeDecl X = PA.getArgument(i).type(); 545 if (!X.isWildcard()) { 546 TypeDecl W = X; 547 constraintEqual(W, U); 548 } else if (X instanceof WildcardExtendsType) { 549 TypeDecl W = ((WildcardExtendsType) X).getAccess().type(); 550 convertibleFrom(W, U); 551 } else if (X instanceof WildcardSuperType) { 552 TypeDecl W = ((WildcardSuperType) X).getAccess().type(); 553 convertibleTo(W, U); 554 } 555 } 556 } 557 } else if (T instanceof WildcardExtendsType) { 558 TypeDecl U = ((WildcardExtendsType) T).getAccess().type(); 559 if (G.instanceOf(H)) { 560 if (H != G) { 561 for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) { 562 TypeDecl V = (TypeDecl) iter.next(); 563 if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) { 564 // replace type argument Un with ? extends Un in V 565 ArrayList list = new ArrayList(); 566 for (int j = 0; j < ((ParTypeDecl) V).getNumArgument(); j++) { 567 list.add(((ParTypeDecl) V).getArgument(j).type().asWildcardExtends()); 568 } 569 V = ((GenericTypeDecl) H).lookupParTypeDecl(list); 570 convertibleFrom(A, V); 571 } 572 } 573 } else if (PF.getNumArgument() == PA.getNumArgument()) { 574 TypeDecl X = PA.getArgument(i).type(); 575 if (X instanceof WildcardExtendsType) { 576 TypeDecl W = ((WildcardExtendsType) X).getAccess().type(); 577 convertibleFrom(W, U); 578 } 579 } 580 } 581 } else if (T instanceof WildcardSuperType) { 582 TypeDecl U = ((WildcardSuperType) T).getAccess().type(); 583 if (G.instanceOf(H)) { 584 if (H != G) { 585 for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) { 586 TypeDecl V = (TypeDecl) iter.next(); 587 if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) { 588 // replace type argument Un with ? super Un in V 589 ArrayList list = new ArrayList(); 590 for (int j = 0; j < ((ParTypeDecl) V).getNumArgument(); j++) { 591 list.add(((ParTypeDecl) V).getArgument(j).type().asWildcardExtends()); 592 } 593 V = ((GenericTypeDecl) H).lookupParTypeDecl(list); 594 convertibleFrom(A, V); 595 } 596 } 597 } else if (PF.getNumArgument() == PA.getNumArgument()) { 598 TypeDecl X = PA.getArgument(i).type(); 599 if (X instanceof WildcardSuperType) { 600 TypeDecl W = ((WildcardSuperType) X).getAccess().type(); 601 convertibleTo(W, U); 602 } 603 } 604 } 605 } 606 } 607 } 608 } else if (F.isRawType()) { 609 rawAccess = true; 610 } 611 } 612 613 public void constraintEqual(TypeDecl A, TypeDecl F) { 614 //System.out.println("ConstraintEqual called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")"); 615 // If F does not involve a type parameter Tj then con constraint is implied on Tj 616 if (!F.involvesTypeParameters()) { 617 return; 618 } 619 // If A is the type of null, no constraint is implied on Tj. 620 else if (A.isNull()) { 621 return; 622 } else if (F instanceof TypeVariable) { 623 if (typeVariables.contains(F)) { 624 addEqualConstraint(F, A); 625 } 626 } else if (F.isArrayDecl()) { 627 TypeDecl U = ((ArrayDecl) F).componentType(); 628 if (A.isArrayDecl()) { 629 TypeDecl V = ((ArrayDecl) A).componentType(); 630 constraintEqual(V, U); 631 } else if (A.isTypeVariable()) { 632 TypeVariable t = (TypeVariable) A; 633 for (int i = 0; i < t.getNumTypeBound(); i++) { 634 TypeDecl typeBound = t.getTypeBound(i).type(); 635 if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) { 636 TypeDecl V = ((ArrayDecl) typeBound).componentType(); 637 constraintEqual(V, U); 638 } 639 } 640 } 641 } else if (F instanceof ParTypeDecl && !F.isRawType()) { 642 if (A instanceof ParTypeDecl) { 643 ParTypeDecl PF = (ParTypeDecl) F; 644 ParTypeDecl PA = (ParTypeDecl) A; 645 if (PF.genericDecl() == PA.genericDecl()) { 646 if (A.isRawType()) { 647 rawAccess = true; 648 } else 649 for (int i = 0; i < PF.getNumArgument(); i++) { 650 TypeDecl T = PF.getArgument(i).type(); 651 if (T.involvesTypeParameters()) { 652 if (!T.isWildcard()) { 653 TypeDecl U = T; 654 TypeDecl V = PA.getArgument(i).type(); 655 constraintEqual(V, U); 656 } else if (T instanceof WildcardExtendsType) { 657 TypeDecl U = ((WildcardExtendsType) T).getAccess().type(); 658 TypeDecl S = PA.getArgument(i).type(); 659 if (S instanceof WildcardExtendsType) { 660 TypeDecl V = ((WildcardExtendsType) S).getAccess().type(); 661 constraintEqual(V, U); 662 } 663 } else if (T instanceof WildcardSuperType) { 664 TypeDecl U = ((WildcardSuperType) T).getAccess().type(); 665 TypeDecl S = PA.getArgument(i).type(); 666 if (S instanceof WildcardSuperType) { 667 TypeDecl V = ((WildcardSuperType) S).getAccess().type(); 668 constraintEqual(V, U); 669 } 670 } 671 } 672 } 673 } 674 } 675 } 676 } 677 } 678 679 syn lazy TypeDecl LUBType.lub() { 680 ArrayList list = new ArrayList(); 681 for (int i = 0; i < getNumTypeBound(); i++) { 682 list.add(getTypeBound(i).type()); 683 } 684 ArrayList bounds = new ArrayList(); 685 for (Iterator iter = LUBType.MEC(list).iterator(); iter.hasNext(); ) { 686 TypeDecl W = (TypeDecl) iter.next(); 687 TypeDecl C = W instanceof GenericTypeDecl ? lci(Inv(W, list), W) : W; 688 bounds.add(C); 689 } 690 if (bounds.size() == 1) { 691 return (TypeDecl) bounds.iterator().next(); 692 } 693 return lookupLUBType(bounds); 694 } 695 696 // the erased candidate set for type parameter Tj, EC, 697 // is the intersection of all the sets EST(U) for each 698 // U in U1...Uk 699 public static HashSet LUBType.EC(ArrayList list) { 700 HashSet result = new HashSet(); 701 boolean first = true; 702 for (Iterator iter = list.iterator(); iter.hasNext(); ) { 703 TypeDecl U = (TypeDecl) iter.next(); 704 // erased supertype set of U 705 HashSet EST = LUBType.EST(U); 706 if (first) { 707 result.addAll(EST); 708 first = false; 709 } else { 710 result.retainAll(EST); 711 } 712 } 713 return result; 714 } 715 716 /** 717 * The minimal erased candidate set for Tj 718 * is MEC = {V | V in EC, forall W != V in EC, not W <: V} 719 * @return minimal erased candidate set for Tj 720 */ 721 public static HashSet LUBType.MEC(ArrayList list) { 722 HashSet EC = LUBType.EC(list); 723 if (EC.size() == 1) { 724 return EC; 725 } 726 HashSet MEC = new HashSet(); 727 for (Iterator iter = EC.iterator(); iter.hasNext(); ) { 728 TypeDecl V = (TypeDecl) iter.next(); 729 boolean keep = true; 730 for (Iterator i2 = EC.iterator(); i2.hasNext(); ) { 731 TypeDecl W = (TypeDecl) i2.next(); 732 if (!(V instanceof TypeVariable) && V != W && W.instanceOf(V)) { 733 keep = false; 734 } 735 } 736 if (keep) { 737 MEC.add(V); 738 } 739 } 740 return MEC; 741 } 742 743 /** 744 * relevant invocations of G, Inv(G) 745 * Inv(G) = {V | 1 <= i <= k, V in ST(Ui), V = G<...>} 746 * @return set of relevant invocations of G, Inv(G) 747 */ 748 public static HashSet LUBType.Inv(TypeDecl G, ArrayList Us) { 749 HashSet result = new HashSet(); 750 for (Iterator iter = Us.iterator(); iter.hasNext(); ) { 751 TypeDecl U = (TypeDecl) iter.next(); 752 for (Iterator i2 = LUBType.ST(U).iterator(); i2.hasNext(); ) { 753 TypeDecl V = (TypeDecl) i2.next(); 754 if (V instanceof ParTypeDecl && !V.isRawType() && ((ParTypeDecl) V).genericDecl() == G) { 755 result.add(V); 756 } 757 } 758 } 759 return result; 760 } 761 762 /** 763 * @return least containing invocation (lci) 764 */ 765 public TypeDecl LUBType.lci(HashSet set, TypeDecl G) { 766 ArrayList list = new ArrayList(); 767 boolean first = true; 768 for (Iterator iter = set.iterator(); iter.hasNext(); ) { 769 ParTypeDecl decl = (ParTypeDecl) iter.next(); 770 if (first) { 771 first = false; 772 for (int i = 0; i < decl.getNumArgument(); i++) { 773 list.add(decl.getArgument(i).type()); 774 } 775 } else { 776 for (int i = 0; i < decl.getNumArgument(); i++) { 777 list.set(i, lcta((TypeDecl) list.get(i), decl.getArgument(i).type())); 778 } 779 } 780 } 781 return ((GenericTypeDecl) G).lookupParTypeDecl(list); 782 } 783 784 /** 785 * least containing type arguments 786 */ 787 public TypeDecl LUBType.lcta(TypeDecl X, TypeDecl Y) { 788 //System.err.println("Computing lcta for " + X.typeName() + " and " + Y.typeName()); 789 if (!X.isWildcard() && !Y.isWildcard()) { 790 TypeDecl U = X; 791 TypeDecl V = Y; 792 return U == V ? U : lub(U, V).asWildcardExtends(); 793 } else if (!X.isWildcard() && Y instanceof WildcardExtendsType) { 794 TypeDecl U = X; 795 TypeDecl V = ((WildcardExtendsType) Y).getAccess().type(); 796 return lub(U, V).asWildcardExtends(); 797 } else if (!Y.isWildcard() && X instanceof WildcardExtendsType) { 798 TypeDecl U = Y; 799 TypeDecl V = ((WildcardExtendsType) X).getAccess().type(); 800 return lub(U, V).asWildcardExtends(); 801 } else if (!X.isWildcard() && Y instanceof WildcardSuperType) { 802 TypeDecl U = X; 803 TypeDecl V = ((WildcardSuperType) Y).getAccess().type(); 804 ArrayList bounds = new ArrayList(); 805 bounds.add(U); 806 bounds.add(V); 807 return GLBTypeFactory.glb(bounds).asWildcardSuper(); 808 } else if (!Y.isWildcard() && X instanceof WildcardSuperType) { 809 TypeDecl U = Y; 810 TypeDecl V = ((WildcardSuperType) X).getAccess().type(); 811 ArrayList bounds = new ArrayList(); 812 bounds.add(U); 813 bounds.add(V); 814 return GLBTypeFactory.glb(bounds).asWildcardSuper(); 815 } else if (X instanceof WildcardExtendsType && Y instanceof WildcardExtendsType) { 816 TypeDecl U = ((WildcardExtendsType) X).getAccess().type(); 817 TypeDecl V = ((WildcardExtendsType) Y).getAccess().type(); 818 return lub(U, V).asWildcardExtends(); 819 } else if (X instanceof WildcardExtendsType && Y instanceof WildcardSuperType) { 820 TypeDecl U = ((WildcardExtendsType) X).getAccess().type(); 821 TypeDecl V = ((WildcardSuperType) Y).getAccess().type(); 822 return U == V ? U : U.typeWildcard(); 823 } else if (Y instanceof WildcardExtendsType && X instanceof WildcardSuperType) { 824 TypeDecl U = ((WildcardExtendsType) Y).getAccess().type(); 825 TypeDecl V = ((WildcardSuperType) X).getAccess().type(); 826 return U == V ? U : U.typeWildcard(); 827 } else if (X instanceof WildcardSuperType && Y instanceof WildcardSuperType) { 828 TypeDecl U = ((WildcardSuperType) X).getAccess().type(); 829 TypeDecl V = ((WildcardSuperType) Y).getAccess().type(); 830 ArrayList bounds = new ArrayList(); 831 bounds.add(U); 832 bounds.add(V); 833 return GLBTypeFactory.glb(bounds).asWildcardSuper(); 834 } else { 835 throw new Error("lcta not defined for (" + X.getClass().getName() + ", " + Y.getClass().getName() + ")"); 836 } 837 } 838 839 public TypeDecl LUBType.lub(TypeDecl X, TypeDecl Y) { 840 ArrayList list = new ArrayList(2); 841 list.add(X); 842 list.add(Y); 843 return lub(list); 844 } 845 846 public TypeDecl LUBType.lub(ArrayList list) { 847 return lookupLUBType(list); 848 } 849 850 // erased supertype set of T 851 public static HashSet LUBType.EST(TypeDecl t) { 852 HashSet result = new HashSet(); 853 for (Iterator iter = LUBType.ST(t).iterator(); iter.hasNext(); ) { 854 TypeDecl typeDecl = (TypeDecl) iter.next(); 855 if (typeDecl instanceof TypeVariable) { 856 result.add(typeDecl); 857 } else { 858 result.add(typeDecl.erasure()); 859 } 860 } 861 return result; 862 } 863 864 /** 865 * @return supertype set of T 866 */ 867 public static HashSet LUBType.ST(TypeDecl t) { 868 HashSet result = new HashSet(); 869 LUBType.addSupertypes(result, t); 870 return result; 871 } 872 873 public static void LUBType.addSupertypes(HashSet set, TypeDecl t) { 874 set.add(t); 875 if (t instanceof ClassDecl) { 876 ClassDecl type = (ClassDecl) t; 877 if (type.hasSuperclass()) { 878 addSupertypes(set, type.superclass()); 879 } 880 for (int i = 0; i < type.getNumImplements(); i++) { 881 addSupertypes(set, type.getImplements(i).type()); 882 } 883 } else if (t instanceof InterfaceDecl) { 884 InterfaceDecl type = (InterfaceDecl) t; 885 for (int i = 0; i < type.getNumSuperInterface(); i++) { 886 addSupertypes(set, type.getSuperInterface(i).type()); 887 } 888 if (type.getNumSuperInterface() == 0) { 889 set.add(type.typeObject()); 890 } 891 } else if (t instanceof TypeVariable) { 892 TypeVariable type = (TypeVariable) t; 893 for (int i = 0; i < type.getNumTypeBound(); i++) { 894 addSupertypes(set, type.getTypeBound(i).type()); 895 } 896 if (type.getNumTypeBound() == 0) { 897 set.add(type.typeObject()); 898 } 899 } else if (t instanceof LUBType) { 900 LUBType type = (LUBType) t; 901 for (int i = 0; i < type.getNumTypeBound(); i++) { 902 addSupertypes(set, type.getTypeBound(i).type()); 903 } 904 if (type.getNumTypeBound() == 0) { 905 set.add(type.typeObject()); 906 } 907 } else if (! (t instanceof NullType)) { 908 throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName()); 909 } 910 } 911 912 }