1 package com.github.javaparser.symbolsolver.resolution.typeinference; 2 3 import com.github.javaparser.resolution.types.ResolvedReferenceType; 4 import com.github.javaparser.resolution.types.ResolvedType; 5 import com.github.javaparser.symbolsolver.model.resolution.TypeSolver; 6 import com.github.javaparser.symbolsolver.model.typesystem.ReferenceTypeImpl; 7 import com.github.javaparser.symbolsolver.resolution.typeinference.bounds.*; 8 import com.github.javaparser.symbolsolver.resolution.typeinference.constraintformulas.TypeSameAsType; 9 import com.github.javaparser.symbolsolver.resolution.typeinference.constraintformulas.TypeSubtypeOfType; 10 import com.github.javaparser.utils.Pair; 11 12 import java.util.*; 13 import java.util.function.Predicate; 14 import java.util.stream.Collectors; 15 16 import static com.github.javaparser.symbolsolver.resolution.typeinference.TypeHelper.*; 17 18 /** 19 * @author Federico Tomassetti 20 */ 21 public class BoundSet { 22 23 private List<Bound> bounds = new LinkedList<>(); 24 25 private static final BoundSet EMPTY = new BoundSet(); 26 27 @Override equals(Object o)28 public boolean equals(Object o) { 29 if (this == o) return true; 30 if (o == null || getClass() != o.getClass()) return false; 31 32 BoundSet boundSet = (BoundSet) o; 33 34 return new HashSet<>(bounds).equals(new HashSet<>(boundSet.bounds)); 35 } 36 37 @Override hashCode()38 public int hashCode() { 39 return bounds.hashCode(); 40 } 41 42 @Override toString()43 public String toString() { 44 return "BoundSet{" + 45 "bounds=" + bounds + 46 '}'; 47 } 48 49 /** 50 51 * It is sometimes convenient to refer to an empty bound set with the symbol true; this is merely out of 52 * convenience, and the two are interchangeable. 53 */ isTrue()54 public boolean isTrue() { 55 return bounds.isEmpty(); 56 } 57 empty()58 public static BoundSet empty() { 59 return EMPTY; 60 } 61 withBound(Bound bound)62 public BoundSet withBound(Bound bound) { 63 if (this.bounds.contains(bound)) { 64 return this; 65 } 66 BoundSet boundSet = new BoundSet(); 67 boundSet.bounds.addAll(this.bounds); 68 boundSet.bounds.add(bound); 69 return boundSet; 70 } 71 findPairSameAs(Predicate<Pair<SameAsBound, SameAsBound>> condition)72 private Optional<Pair<SameAsBound, SameAsBound>> findPairSameAs(Predicate<Pair<SameAsBound, SameAsBound>> condition) { 73 for (int i=0;i<bounds.size();i++) { 74 Bound bi = bounds.get(i); 75 if (bi instanceof SameAsBound) { 76 SameAsBound si = (SameAsBound)bi; 77 for (int j = i + 1; j < bounds.size(); j++) { 78 Bound bj = bounds.get(j); 79 if (bj instanceof SameAsBound) { 80 SameAsBound sj = (SameAsBound)bj; 81 Pair<SameAsBound, SameAsBound> pair = new Pair<SameAsBound, SameAsBound>(si, sj); 82 if (condition.test(pair)) { 83 return Optional.of(pair); 84 } 85 } 86 } 87 } 88 } 89 return Optional.empty(); 90 } 91 isEmpty()92 public boolean isEmpty() { 93 return bounds.isEmpty(); 94 } 95 96 interface Processor<B1 extends Bound, B2 extends Bound, R> { process(B1 a, B2 b, R initialValue)97 R process(B1 a, B2 b, R initialValue); 98 } 99 forEachPairSameAs(Processor<SameAsBound, SameAsBound, T> processor, T initialValue)100 private <T> T forEachPairSameAs(Processor<SameAsBound, SameAsBound, T> processor, T initialValue) { 101 T currentValue = initialValue; 102 for (int i=0;i<bounds.size();i++) { 103 Bound bi = bounds.get(i); 104 if (bi instanceof SameAsBound) { 105 SameAsBound si = (SameAsBound)bi; 106 for (int j = i + 1; j < bounds.size(); j++) { 107 Bound bj = bounds.get(j); 108 if (bj instanceof SameAsBound) { 109 SameAsBound sj = (SameAsBound)bj; 110 currentValue = processor.process(si, sj, currentValue); 111 } 112 } 113 } 114 } 115 return currentValue; 116 } 117 forEachPairSameAndSubtype(Processor<SameAsBound, SubtypeOfBound, T> processor, T initialValue)118 private <T> T forEachPairSameAndSubtype(Processor<SameAsBound, SubtypeOfBound, T> processor, T initialValue) { 119 T currentValue = initialValue; 120 for (int i=0;i<bounds.size();i++) { 121 Bound bi = bounds.get(i); 122 if (bi instanceof SameAsBound) { 123 SameAsBound si = (SameAsBound)bi; 124 for (int j = i + 1; j < bounds.size(); j++) { 125 Bound bj = bounds.get(j); 126 if (bj instanceof SubtypeOfBound) { 127 SubtypeOfBound sj = (SubtypeOfBound)bj; 128 currentValue = processor.process(si, sj, currentValue); 129 } 130 } 131 } 132 } 133 return currentValue; 134 } 135 forEachPairSubtypeAndSubtype(Processor<SubtypeOfBound, SubtypeOfBound, T> processor, T initialValue)136 private <T> T forEachPairSubtypeAndSubtype(Processor<SubtypeOfBound, SubtypeOfBound, T> processor, T initialValue) { 137 T currentValue = initialValue; 138 for (int i=0;i<bounds.size();i++) { 139 Bound bi = bounds.get(i); 140 if (bi instanceof SubtypeOfBound) { 141 SubtypeOfBound si = (SubtypeOfBound)bi; 142 for (int j = i + 1; j < bounds.size(); j++) { 143 Bound bj = bounds.get(j); 144 if (bj instanceof SubtypeOfBound) { 145 SubtypeOfBound sj = (SubtypeOfBound)bj; 146 currentValue = processor.process(si, sj, currentValue); 147 } 148 } 149 } 150 } 151 return currentValue; 152 } 153 areSameTypeInference(ResolvedType a, ResolvedType b)154 private boolean areSameTypeInference(ResolvedType a, ResolvedType b) { 155 return isInferenceVariable(a) && isInferenceVariable(b) && a.equals(b); 156 } 157 findPairsOfCommonAncestors(ResolvedReferenceType r1, ResolvedReferenceType r2)158 private List<Pair<ResolvedReferenceType, ResolvedReferenceType>> findPairsOfCommonAncestors(ResolvedReferenceType r1, ResolvedReferenceType r2) { 159 List<ResolvedReferenceType> set1 = new LinkedList<>(); 160 set1.add(r1); 161 set1.addAll(r1.getAllAncestors()); 162 List<ResolvedReferenceType> set2 = new LinkedList<>(); 163 set2.add(r2); 164 set2.addAll(r2.getAllAncestors()); 165 List<Pair<ResolvedReferenceType, ResolvedReferenceType>> pairs = new LinkedList<>(); 166 for (ResolvedReferenceType rtFrom1 : set1) { 167 for (ResolvedReferenceType rtFrom2 : set2) { 168 if (rtFrom1.getTypeDeclaration().equals(rtFrom2.getTypeDeclaration())) { 169 pairs.add(new Pair<>(rtFrom1, rtFrom2)); 170 } 171 } 172 } 173 return pairs; 174 } 175 176 /** 177 * Maintains a set of inference variable bounds, ensuring that these are consistent as new bounds are added. 178 * Because the bounds on one variable can sometimes impact the possible choices for another variable, this process 179 * propagates bounds between such interdependent variables. 180 */ incorporate(BoundSet otherBounds, TypeSolver typeSolver)181 public BoundSet incorporate(BoundSet otherBounds, TypeSolver typeSolver) { 182 BoundSet newBoundSet = this; 183 for (Bound b : otherBounds.bounds) { 184 newBoundSet = newBoundSet.withBound(b); 185 } 186 return newBoundSet.deriveImpliedBounds(typeSolver); 187 } 188 deriveImpliedBounds(TypeSolver typeSolver)189 public BoundSet deriveImpliedBounds(TypeSolver typeSolver) { 190 // As bound sets are constructed and grown during inference, it is possible that new bounds can be inferred 191 // based on the assertions of the original bounds. The process of incorporation identifies these new bounds 192 // and adds them to the bound set. 193 // 194 // Incorporation can happen in two scenarios. One scenario is that the bound set contains complementary pairs 195 // of bounds; this implies new constraint formulas, as specified in §18.3.1. The other scenario is that the 196 // bound set contains a bound involving capture conversion; this implies new bounds and may imply new 197 // constraint formulas, as specified in §18.3.2. In both scenarios, any new constraint formulas are reduced, 198 // and any new bounds are added to the bound set. This may trigger further incorporation; ultimately, the set 199 // will reach a fixed point and no further bounds can be inferred. 200 // 201 // If incorporation of a bound set has reached a fixed point, and the set does not contain the bound false, 202 // then the bound set has the following properties: 203 // 204 // - For each combination of a proper lower bound L and a proper upper bound U of an inference variable, L <: U. 205 // 206 // - If every inference variable mentioned by a bound has an instantiation, the bound is satisfied by the 207 // corresponding substitution. 208 // 209 // - Given a dependency α = β, every bound of α matches a bound of β, and vice versa. 210 // 211 // - Given a dependency α <: β, every lower bound of α is a lower bound of β, and every upper bound of β is an 212 // upper bound of α. 213 214 ConstraintFormulaSet newConstraintsSet = ConstraintFormulaSet.empty(); 215 216 // SECTION Complementary Pairs of Bounds 217 // (In this section, S and T are inference variables or types, and U is a proper type. For conciseness, a bound 218 // of the form α = T may also match a bound of the form T = α.) 219 // 220 // When a bound set contains a pair of bounds that match one of the following rules, a new constraint formula 221 // is implied: 222 // 223 // - α = S and α = T imply ‹S = T› 224 225 newConstraintsSet = forEachPairSameAs((a, b, currentConstraintSet) -> { 226 if (areSameTypeInference(a.getS(), b.getS())) { 227 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(a.getT(), b.getT())); 228 } 229 if (areSameTypeInference(a.getS(), b.getT())) { 230 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(a.getS(), b.getT())); 231 } 232 if (areSameTypeInference(a.getT(), b.getS())) { 233 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(a.getT(), b.getS())); 234 } 235 if (areSameTypeInference(a.getT(), b.getT())) { 236 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(a.getS(), b.getS())); 237 } 238 return currentConstraintSet; 239 }, newConstraintsSet); 240 241 // - α = S and α <: T imply ‹S <: T› 242 243 newConstraintsSet = forEachPairSameAndSubtype((a, b, currentConstraintSet) -> { 244 if (areSameTypeInference(a.getS(), b.getS())) { 245 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, a.getT(), b.getT())); 246 } 247 if (areSameTypeInference(a.getT(), b.getS())) { 248 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, a.getS(), b.getT())); 249 } 250 return currentConstraintSet; 251 }, newConstraintsSet); 252 253 // - α = S and T <: α imply ‹T <: S› 254 255 newConstraintsSet = forEachPairSameAndSubtype((a, b, currentConstraintSet) -> { 256 if (areSameTypeInference(a.getS(), b.getT())) { 257 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, b.getS(), a.getT())); 258 } 259 if (areSameTypeInference(a.getT(), b.getT())) { 260 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, b.getS(), a.getS())); 261 } 262 return currentConstraintSet; 263 }, newConstraintsSet); 264 265 // - S <: α and α <: T imply ‹S <: T› 266 267 newConstraintsSet = forEachPairSubtypeAndSubtype((a, b, currentConstraintSet) -> { 268 if (areSameTypeInference(a.getT(), b.getS())) { 269 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, b.getS(), a.getT())); 270 } 271 return currentConstraintSet; 272 }, newConstraintsSet); 273 274 // - α = U and S = T imply ‹S[α:=U] = T[α:=U]› 275 276 newConstraintsSet = forEachPairSameAs((a, b, currentConstraintSet) -> { 277 if (isInferenceVariable(a.getS()) && isProperType(a.getT())) { 278 InferenceVariable alpha = (InferenceVariable)a.getS(); 279 ResolvedType U = a.getT(); 280 ResolvedType S = b.getS(); 281 ResolvedType T = b.getT(); 282 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 283 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(sub.apply(S), sub.apply(T))); 284 } 285 if (isInferenceVariable(a.getT()) && isProperType(a.getS())) { 286 InferenceVariable alpha = (InferenceVariable)a.getT(); 287 ResolvedType U = a.getS(); 288 ResolvedType S = b.getS(); 289 ResolvedType T = b.getT(); 290 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 291 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(sub.apply(S), sub.apply(T))); 292 } 293 if (isInferenceVariable(b.getS()) && isProperType(b.getT())) { 294 InferenceVariable alpha = (InferenceVariable)b.getS(); 295 ResolvedType U = b.getT(); 296 ResolvedType S = a.getS(); 297 ResolvedType T = a.getT(); 298 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 299 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(sub.apply(S), sub.apply(T))); 300 } 301 if (isInferenceVariable(b.getT()) && isProperType(b.getS())) { 302 InferenceVariable alpha = (InferenceVariable)b.getT(); 303 ResolvedType U = b.getS(); 304 ResolvedType S = a.getS(); 305 ResolvedType T = a.getT(); 306 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 307 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(sub.apply(S), sub.apply(T))); 308 } 309 return currentConstraintSet; 310 }, newConstraintsSet); 311 312 // - α = U and S <: T imply ‹S[α:=U] <: T[α:=U]› 313 314 newConstraintsSet = forEachPairSameAndSubtype((a, b, currentConstraintSet) -> { 315 if (isInferenceVariable(a.getS()) && isProperType(a.getT())) { 316 InferenceVariable alpha = (InferenceVariable)a.getS(); 317 ResolvedType U = a.getT(); 318 ResolvedType S = b.getS(); 319 ResolvedType T = b.getT(); 320 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 321 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, sub.apply(S), sub.apply(T))); 322 } 323 if (isInferenceVariable(a.getT()) && isProperType(a.getS())) { 324 InferenceVariable alpha = (InferenceVariable)a.getT(); 325 ResolvedType U = a.getS(); 326 ResolvedType S = b.getS(); 327 ResolvedType T = b.getT(); 328 Substitution sub = Substitution.empty().withPair(alpha.getTypeParameterDeclaration(), U); 329 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSubtypeOfType(typeSolver, sub.apply(S), sub.apply(T))); 330 } 331 return currentConstraintSet; 332 }, newConstraintsSet); 333 334 // When a bound set contains a pair of bounds α <: S and α <: T, and there exists a supertype of S of the 335 // form G<S1, ..., Sn> and a supertype of T of the form G<T1, ..., Tn> (for some generic class or interface, G), 336 // then for all i (1 ≤ i ≤ n), if Si and Ti are types (not wildcards), the constraint formula ‹Si = Ti› is 337 // implied. 338 339 newConstraintsSet = forEachPairSubtypeAndSubtype((a, b, currentConstraintSet) -> { 340 if (isInferenceVariable(a.getS()) && isInferenceVariable(b.getS())) { 341 if (a.getT().isReferenceType() && b.getT().isReferenceType()) { 342 ResolvedReferenceType S = a.getT().asReferenceType(); 343 ResolvedReferenceType T = b.getT().asReferenceType(); 344 List<Pair<ResolvedReferenceType, ResolvedReferenceType>> pairs = findPairsOfCommonAncestors(S, T); 345 for (Pair<ResolvedReferenceType, ResolvedReferenceType> pair : pairs) { 346 for (int i=0;i<Math.min(pair.a.typeParametersValues().size(), pair.b.typeParametersValues().size()); i++) { 347 ResolvedType si = pair.a.typeParametersValues().get(i); 348 ResolvedType ti = pair.b.typeParametersValues().get(i); 349 if (!si.isWildcard() && !ti.isWildcard()) { 350 currentConstraintSet = currentConstraintSet.withConstraint(new TypeSameAsType(si, ti)); 351 } 352 } 353 } 354 } 355 } 356 return currentConstraintSet; 357 }, newConstraintsSet); 358 359 // SECTION Bounds Involving Capture Conversion 360 // 361 // When a bound set contains a bound of the form G<α1, ..., αn> = capture(G<A1, ..., An>), new bounds are 362 // implied and new constraint formulas may be implied, as follows. 363 364 for (Bound b : this.bounds.stream().filter(b -> b instanceof CapturesBound).collect(Collectors.toList())) { 365 CapturesBound capturesBound = (CapturesBound)b; 366 367 throw new UnsupportedOperationException(); 368 369 // Let P1, ..., Pn represent the type parameters of G and let B1, ..., Bn represent the bounds of these type 370 // parameters. Let θ represent the substitution [P1:=α1, ..., Pn:=αn]. Let R be a type that is not an inference 371 // variable (but is not necessarily a proper type). 372 // 373 // A set of bounds on α1, ..., αn is implied, constructed from the declared bounds of P1, ..., Pn as specified 374 // in §18.1.3. 375 // 376 // In addition, for all i (1 ≤ i ≤ n): 377 // 378 // - If Ai is not a wildcard, then the bound αi = Ai is implied. 379 // 380 // - If Ai is a wildcard of the form ?: 381 // 382 // - αi = R implies the bound false 383 // 384 // - αi <: R implies the constraint formula ‹Bi θ <: R› 385 // 386 // - R <: αi implies the bound false 387 // 388 // - If Ai is a wildcard of the form ? extends T: 389 // 390 // - αi = R implies the bound false 391 // 392 // - If Bi is Object, then αi <: R implies the constraint formula ‹T <: R› 393 // 394 // - If T is Object, then αi <: R implies the constraint formula ‹Bi θ <: R› 395 // 396 // - R <: αi implies the bound false 397 // 398 // - If Ai is a wildcard of the form ? super T: 399 // 400 // - αi = R implies the bound false 401 // 402 // - αi <: R implies the constraint formula ‹Bi θ <: R› 403 // 404 // - R <: αi implies the constraint formula ‹R <: T› 405 } 406 407 if (newConstraintsSet.isEmpty()) { 408 return this; 409 } else { 410 BoundSet newBounds = newConstraintsSet.reduce(typeSolver); 411 if (newBounds.isEmpty()) { 412 return this; 413 } 414 return this.incorporate(newBounds, typeSolver); 415 } 416 } 417 containsFalse()418 public boolean containsFalse() { 419 return bounds.stream().anyMatch(it -> it instanceof FalseBound); 420 } 421 422 private class VariableDependency { 423 private InferenceVariable depending; 424 private InferenceVariable dependedOn; 425 VariableDependency(InferenceVariable depending, InferenceVariable dependedOn)426 public VariableDependency(InferenceVariable depending, InferenceVariable dependedOn) { 427 this.depending = depending; 428 this.dependedOn = dependedOn; 429 } 430 getDepending()431 public InferenceVariable getDepending() { 432 return depending; 433 } 434 getDependedOn()435 public InferenceVariable getDependedOn() { 436 return dependedOn; 437 } 438 isReflexive()439 public boolean isReflexive() { 440 return dependedOn.equals(depending); 441 } 442 } 443 allInferenceVariables()444 private Set<InferenceVariable> allInferenceVariables() { 445 Set<InferenceVariable> variables = new HashSet<>(); 446 for (Bound b : bounds) { 447 variables.addAll(b.usedInferenceVariables()); 448 } 449 return variables; 450 } 451 hasInstantiationFor(InferenceVariable v)452 private boolean hasInstantiationFor(InferenceVariable v) { 453 for (Bound b : bounds) { 454 if (b.isAnInstantiationFor(v)) { 455 return true; 456 } 457 } 458 return false; 459 } 460 getInstantiationFor(InferenceVariable v)461 private Instantiation getInstantiationFor(InferenceVariable v) { 462 for (Bound b : bounds) { 463 if (b.isAnInstantiationFor(v)) { 464 return b.isAnInstantiation().get(); 465 } 466 } 467 throw new IllegalArgumentException(); 468 } 469 equalAlphaJ(Set<InferenceVariable> alphas, InferenceVariable beta)470 private boolean thereIsSomeJSuchThatβequalAlphaJ(Set<InferenceVariable> alphas, InferenceVariable beta) { 471 for (InferenceVariable alphaJ : alphas) { 472 for (Bound b : bounds) { 473 if (b instanceof SameAsBound) { 474 SameAsBound sameAsBound = (SameAsBound)b; 475 if (sameAsBound.getS().equals(alphaJ) && sameAsBound.getT().equals(beta)) { 476 return true; 477 } 478 if (sameAsBound.getT().equals(alphaJ) && sameAsBound.getS().equals(beta)) { 479 return true; 480 } 481 } 482 } 483 } 484 return false; 485 } 486 buildAllSubsetsOfSize(Set<T> allElements, int desiredSize)487 private <T> List<Set<T>> buildAllSubsetsOfSize(Set<T> allElements, int desiredSize) { 488 if (desiredSize == allElements.size()) { 489 return Arrays.asList(allElements); 490 } else { 491 List<Set<T>> res = new LinkedList<>(); 492 for (T element : allElements) { 493 Set<T> subset = allButOne(allElements, element); 494 res.addAll(buildAllSubsetsOfSize(subset, desiredSize)); 495 } 496 return res; 497 } 498 } 499 allButOne(Set<T> elements, T element)500 private <T> Set<T> allButOne(Set<T> elements, T element) { 501 Set<T> set = new HashSet<T>(elements); 502 set.remove(element); 503 return set; 504 } 505 506 /** 507 * there exists no non-empty proper subset of { α1, ..., αn } with this property. 508 */ smallestSetWithProperty(Set<InferenceVariable> uninstantiatedVariables, List<VariableDependency> dependencies)509 private Optional<Set<InferenceVariable>> smallestSetWithProperty(Set<InferenceVariable> uninstantiatedVariables, 510 List<VariableDependency> dependencies) { 511 for (int i=1;i<=uninstantiatedVariables.size();i++) { 512 for (Set<InferenceVariable> aSubSet : buildAllSubsetsOfSize(uninstantiatedVariables, i)){ 513 if (hasProperty(aSubSet, dependencies)) { 514 return Optional.of(aSubSet); 515 } 516 } 517 } 518 return Optional.empty(); 519 } 520 521 /** 522 * if αi depends on the resolution of a variable β, then either β has an instantiation 523 * or there is some j such that β = αj 524 * @return 525 */ hasProperty(Set<InferenceVariable> alphas, List<VariableDependency> dependencies)526 private boolean hasProperty(Set<InferenceVariable> alphas, List<VariableDependency> dependencies) { 527 for (InferenceVariable alphaI: alphas) { 528 for (InferenceVariable beta: dependencies.stream() 529 .filter(d -> d.depending.equals(alphaI)) 530 .filter(d -> !d.isReflexive()) 531 .map(d -> d.dependedOn) 532 .collect(Collectors.toList())) { 533 if (!hasInstantiationFor(beta) && !thereIsSomeJSuchThatβequalAlphaJ(alphas, beta)) { 534 return false; 535 } 536 } 537 } 538 return true; 539 } 540 541 /** 542 * Examines the bounds on an inference variable and determines an instantiation that is compatible with those 543 * bounds. It also decides the order in which interdependent inference variables are to be resolved. 544 */ performResolution(List<InferenceVariable> variablesToResolve, TypeSolver typeSolver)545 public Optional<InstantiationSet> performResolution(List<InferenceVariable> variablesToResolve, TypeSolver typeSolver) { 546 547 if (this.containsFalse()) { 548 return Optional.empty(); 549 } 550 551 List<VariableDependency> dependencies = new LinkedList<>(); 552 553 // Given a bound set that does not contain the bound false, a subset of the inference variables mentioned by 554 // the bound set may be resolved. This means that a satisfactory instantiation may be added to the set for each 555 // inference variable, until all the requested variables have instantiations. 556 // 557 // Dependencies in the bound set may require that the variables be resolved in a particular order, or that 558 // additional variables be resolved. Dependencies are specified as follows: 559 // 560 // - Given a bound of one of the following forms, where T is either an inference variable β or a type that 561 // mentions β: 562 // 563 // - α = T 564 // 565 // - α <: T 566 // 567 // - T = α 568 // 569 // - T <: α 570 // 571 // If α appears on the left-hand side of another bound of the form G<..., α, ...> = capture(G<...>), then β 572 // depends on the resolution of α. Otherwise, α depends on the resolution of β. 573 574 for (Bound b : bounds) { 575 if (b instanceof CapturesBound) { 576 throw new UnsupportedOperationException(); 577 } 578 } 579 580 // - An inference variable α appearing on the left-hand side of a bound of the form 581 // G<..., α, ...> = capture(G<...>) depends on the resolution of every other inference variable mentioned in 582 // this bound (on both sides of the = sign). 583 584 for (Bound b : bounds) { 585 if (b instanceof CapturesBound) { 586 throw new UnsupportedOperationException(); 587 } 588 } 589 590 // - An inference variable α depends on the resolution of an inference variable β if there exists an inference 591 // variable γ such that α depends on the resolution of γ and γ depends on the resolution of β. 592 593 for (int i=0;i<dependencies.size();i++) { 594 VariableDependency di = dependencies.get(i); 595 for (int j=i+1;j<dependencies.size();j++) { 596 VariableDependency dj = dependencies.get(j); 597 if (di.dependedOn.equals(dj.depending)) { 598 dependencies.add(new VariableDependency(di.getDepending(), dj.getDependedOn())); 599 } 600 } 601 } 602 603 // - An inference variable α depends on the resolution of itself. 604 605 for (InferenceVariable v : allInferenceVariables()) { 606 dependencies.add(new VariableDependency(v, v)); 607 } 608 609 // Given a set of inference variables to resolve, let V be the union of this set and all variables upon which 610 // the resolution of at least one variable in this set depends. 611 612 Set<InferenceVariable> V = new HashSet<>(); 613 V.addAll(variablesToResolve); 614 for (VariableDependency dependency : dependencies) { 615 if (variablesToResolve.contains(dependency.depending)) { 616 V.add(dependency.dependedOn); 617 } 618 } 619 620 // If every variable in V has an instantiation, then resolution succeeds and this procedure terminates. 621 622 boolean ok = true; 623 for (InferenceVariable v : V) { 624 if (!hasInstantiationFor(v)) { 625 ok = false; 626 } 627 } 628 if (ok) { 629 InstantiationSet instantiationSet = InstantiationSet.empty(); 630 for (InferenceVariable v : V) { 631 instantiationSet = instantiationSet.withInstantiation(getInstantiationFor(v)); 632 } 633 return Optional.of(instantiationSet); 634 } 635 636 // Otherwise, let { α1, ..., αn } be a non-empty subset of uninstantiated variables in V such that i) 637 // for all i (1 ≤ i ≤ n), if αi depends on the resolution of a variable β, then either β has an instantiation 638 // or there is some j such that β = αj; and ii) there exists no non-empty proper subset of { α1, ..., αn } 639 // with this property. 640 641 Set<InferenceVariable> uninstantiatedPortionOfV = new HashSet<>(); 642 for (InferenceVariable v : V) { 643 if (!hasInstantiationFor(v)) { 644 uninstantiatedPortionOfV.add(v); 645 } 646 } 647 for (Set<InferenceVariable> alphas: allSetsWithProperty(uninstantiatedPortionOfV, dependencies)) { 648 649 // Resolution proceeds by generating an instantiation for each of α1, ..., αn based on the 650 // bounds in the bound set: 651 652 boolean hasSomeCaptureForAlphas = alphas.stream().anyMatch( 653 alphaI -> appearInLeftPartOfCapture(alphaI) 654 ); 655 656 // - If the bound set does not contain a bound of the form G<..., αi, ...> = capture(G<...>) 657 // for all i (1 ≤ i ≤ n), then a candidate instantiation Ti is defined for each αi: 658 659 if (!hasSomeCaptureForAlphas) { 660 BoundSet newBounds = BoundSet.empty(); 661 for (InferenceVariable alphaI : alphas) { 662 Set<ResolvedType> properLowerBounds = bounds.stream() 663 .filter(b -> b.isProperLowerBoundFor(alphaI).isPresent()) 664 .map(b -> b.isProperLowerBoundFor(alphaI).get().getProperType()) 665 .collect(Collectors.toSet()); 666 667 ResolvedType Ti = null; 668 669 // - If αi has one or more proper lower bounds, L1, ..., Lk, then Ti = lub(L1, ..., Lk) (§4.10.4). 670 671 if (properLowerBounds.size() > 0) { 672 Ti = leastUpperBound(properLowerBounds); 673 } 674 675 // - Otherwise, if the bound set contains throws αi, and the proper upper bounds of αi are, at most, 676 // Exception, Throwable, and Object, then Ti = RuntimeException. 677 678 boolean throwsBound = bounds.stream().anyMatch(b -> b.isThrowsBoundOn(alphaI)); 679 if (Ti == null && throwsBound && properUpperBoundsAreAtMostExceptionThrowableAndObject(alphaI)) { 680 Ti = new ReferenceTypeImpl(typeSolver.solveType(RuntimeException.class.getCanonicalName()), typeSolver); 681 } 682 683 // - Otherwise, where αi has proper upper bounds U1, ..., Uk, Ti = glb(U1, ..., Uk) (§5.1.10). 684 685 if (Ti == null) { 686 Set<ResolvedType> properUpperBounds = bounds.stream() 687 .filter(b -> b.isProperUpperBoundFor(alphaI).isPresent()) 688 .map(b -> b.isProperUpperBoundFor(alphaI).get().getProperType()) 689 .collect(Collectors.toSet()); 690 if (properUpperBounds.size() == 0) { 691 throw new IllegalStateException(); 692 } 693 Ti = glb(properUpperBounds); 694 } 695 696 newBounds = newBounds.withBound(new SameAsBound(alphaI, Ti)); 697 } 698 699 // The bounds α1 = T1, ..., αn = Tn are incorporated with the current bound set. 700 701 BoundSet incorporatedBoundSet = this.incorporate(newBounds, typeSolver); 702 703 // If the result does not contain the bound false, then the result becomes the new bound set, and resolution 704 // proceeds by selecting a new set of variables to instantiate (if necessary), as described above. 705 706 if (!incorporatedBoundSet.containsFalse()) { 707 return incorporatedBoundSet.performResolution(variablesToResolve, typeSolver); 708 } 709 710 // Otherwise, the result contains the bound false, so a second attempt is made to instantiate { α1, ..., αn } 711 // by performing the step below. 712 713 throw new UnsupportedOperationException(); 714 } 715 716 // - If the bound set contains a bound of the form G<..., αi, ...> = capture(G<...>) for some i (1 ≤ i ≤ n), or; 717 718 else { 719 720 // If the bound set produced in the step above contains the bound false; 721 // 722 // then let Y1, ..., Yn be fresh type variables whose bounds are as follows: 723 // 724 // - For all i (1 ≤ i ≤ n), if αi has one or more proper lower bounds L1, ..., Lk, then let the lower bound 725 // of Yi be lub(L1, ..., Lk); if not, then Yi has no lower bound. 726 // 727 // - For all i (1 ≤ i ≤ n), where αi has upper bounds U1, ..., Uk, let the upper bound of Yi be 728 // glb(U1 θ, ..., Uk θ), where θ is the substitution [α1:=Y1, ..., αn:=Yn]. 729 // 730 // If the type variables Y1, ..., Yn do not have well-formed bounds (that is, a lower bound is not a subtype 731 // of an upper bound, or an intersection type is inconsistent), then resolution fails. 732 // 733 // Otherwise, for all i (1 ≤ i ≤ n), all bounds of the form G<..., αi, ...> = capture(G<...>) are removed 734 // from the current bound set, and the bounds α1 = Y1, ..., αn = Yn are incorporated. 735 // 736 // If the result does not contain the bound false, then the result becomes the new bound set, and resolution 737 // proceeds by selecting a new set of variables to instantiate (if necessary), as described above. 738 // 739 // Otherwise, the result contains the bound false, and resolution fails. 740 741 throw new UnsupportedOperationException(); 742 } 743 } 744 return Optional.empty(); 745 } 746 allPossibleSetsWithProperty(Set<InferenceVariable> allElements, List<VariableDependency> dependencies)747 private Set<Set<InferenceVariable>> allPossibleSetsWithProperty(Set<InferenceVariable> allElements, List<VariableDependency> dependencies) { 748 Set<Set<InferenceVariable>> result = new HashSet<>(); 749 for (int i=1;i<=allElements.size();i++) { 750 for (Set<InferenceVariable> aSubSet : buildAllSubsetsOfSize(allElements, i)){ 751 if (hasProperty(aSubSet, dependencies)) { 752 result.add(aSubSet); 753 } 754 } 755 } 756 return result; 757 } 758 thereAreProperSubsets(Set<InferenceVariable> aSet, Set<Set<InferenceVariable>> allPossibleSets)759 private boolean thereAreProperSubsets(Set<InferenceVariable> aSet, Set<Set<InferenceVariable>> allPossibleSets) { 760 for (Set<InferenceVariable> anotherSet : allPossibleSets) { 761 if (!anotherSet.equals(aSet)) { 762 if (isTheFirstAProperSubsetOfTheSecond(anotherSet, aSet)) { 763 return true; 764 } 765 } 766 } 767 return false; 768 } 769 isTheFirstAProperSubsetOfTheSecond(Set<InferenceVariable> subset, Set<InferenceVariable> originalSet)770 private boolean isTheFirstAProperSubsetOfTheSecond(Set<InferenceVariable> subset, Set<InferenceVariable> originalSet) { 771 return originalSet.containsAll(subset) && originalSet.size() > subset.size(); 772 } 773 allSetsWithProperty(Set<InferenceVariable> allElements, List<VariableDependency> dependencies)774 private Set<Set<InferenceVariable>> allSetsWithProperty(Set<InferenceVariable> allElements, List<VariableDependency> dependencies) { 775 Set<Set<InferenceVariable>> allPossibleSets = allPossibleSetsWithProperty(allElements, dependencies); 776 Set<Set<InferenceVariable>> selected = new HashSet<>(); 777 for (Set<InferenceVariable> aSet : allPossibleSets) { 778 if (!thereAreProperSubsets(aSet, allPossibleSets)) { 779 selected.add(aSet); 780 } 781 } 782 return selected; 783 } 784 properUpperBoundsAreAtMostExceptionThrowableAndObject(InferenceVariable inferenceVariable)785 private boolean properUpperBoundsAreAtMostExceptionThrowableAndObject(InferenceVariable inferenceVariable) { 786 throw new UnsupportedOperationException(); 787 } 788 appearInLeftPartOfCapture(InferenceVariable inferenceVariable)789 private boolean appearInLeftPartOfCapture(InferenceVariable inferenceVariable) { 790 for (Bound b : bounds) { 791 if (b instanceof CapturesBound) { 792 CapturesBound capturesBound = (CapturesBound)b; 793 if (capturesBound.getInferenceVariables().contains(inferenceVariable)) { 794 return true; 795 } 796 } 797 } 798 return false; 799 } 800 getProperUpperBoundsFor(InferenceVariable inferenceVariable)801 public List<Bound> getProperUpperBoundsFor(InferenceVariable inferenceVariable) { 802 return bounds.stream().filter(b -> b.isProperUpperBoundFor(inferenceVariable).isPresent()).collect(Collectors.toList()); 803 } 804 } 805