1/* 2 * Copyright (c) 2015, 2017, 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 26package com.sun.tools.javac.comp; 27 28import java.util.Collections; 29import java.util.EnumSet; 30import java.util.HashMap; 31import java.util.HashSet; 32import java.util.LinkedHashMap; 33import java.util.Map; 34import java.util.Set; 35 36import com.sun.tools.javac.code.Type; 37import com.sun.tools.javac.code.Type.ArrayType; 38import com.sun.tools.javac.code.Type.ClassType; 39import com.sun.tools.javac.code.Type.TypeVar; 40import com.sun.tools.javac.code.Type.UndetVar; 41import com.sun.tools.javac.code.Type.UndetVar.InferenceBound; 42import com.sun.tools.javac.code.Type.WildcardType; 43import com.sun.tools.javac.code.TypeTag; 44import com.sun.tools.javac.code.Types; 45import com.sun.tools.javac.comp.Infer.FreeTypeListener; 46import com.sun.tools.javac.comp.Infer.GraphSolver; 47import com.sun.tools.javac.comp.Infer.GraphStrategy; 48import com.sun.tools.javac.comp.Infer.InferenceException; 49import com.sun.tools.javac.comp.Infer.InferenceStep; 50import com.sun.tools.javac.tree.JCTree; 51import com.sun.tools.javac.util.Assert; 52import com.sun.tools.javac.util.Filter; 53import com.sun.tools.javac.util.List; 54import com.sun.tools.javac.util.ListBuffer; 55import com.sun.tools.javac.util.Warner; 56 57/** 58 * An inference context keeps track of the set of variables that are free 59 * in the current context. It provides utility methods for opening/closing 60 * types to their corresponding free/closed forms. It also provide hooks for 61 * attaching deferred post-inference action (see PendingCheck). Finally, 62 * it can be used as an entry point for performing upper/lower bound inference 63 * (see InferenceKind). 64 * 65 * <p><b>This is NOT part of any supported API. 66 * If you write code that depends on this, you do so at your own risk. 67 * This code and its internal interfaces are subject to change or 68 * deletion without notice.</b> 69 */ 70public class InferenceContext { 71 72 /** list of inference vars as undet vars */ 73 List<Type> undetvars; 74 75 Type update(Type t) { 76 return t; 77 } 78 79 /** list of inference vars in this context */ 80 List<Type> inferencevars; 81 82 Map<FreeTypeListener, List<Type>> freeTypeListeners = new LinkedHashMap<>(); 83 84 Types types; 85 Infer infer; 86 87 public InferenceContext(Infer infer, List<Type> inferencevars) { 88 this(infer, inferencevars, inferencevars.map(infer.fromTypeVarFun)); 89 } 90 91 public InferenceContext(Infer infer, List<Type> inferencevars, List<Type> undetvars) { 92 this.inferencevars = inferencevars; 93 this.undetvars = undetvars; 94 this.infer = infer; 95 this.types = infer.types; 96 } 97 98 /** 99 * add a new inference var to this inference context 100 */ 101 void addVar(TypeVar t) { 102 this.undetvars = this.undetvars.prepend(infer.fromTypeVarFun.apply(t)); 103 this.inferencevars = this.inferencevars.prepend(t); 104 } 105 106 /** 107 * returns the list of free variables (as type-variables) in this 108 * inference context 109 */ 110 List<Type> inferenceVars() { 111 return inferencevars; 112 } 113 114 /** 115 * returns the list of undetermined variables in this inference context 116 */ 117 public List<Type> undetVars() { 118 return undetvars; 119 } 120 121 /** 122 * returns the list of uninstantiated variables (as type-variables) in this 123 * inference context 124 */ 125 List<Type> restvars() { 126 return filterVars(uv -> uv.getInst() == null); 127 } 128 129 /** 130 * returns the list of instantiated variables (as type-variables) in this 131 * inference context 132 */ 133 List<Type> instvars() { 134 return filterVars(uv -> uv.getInst() != null); 135 } 136 137 /** 138 * Get list of bounded inference variables (where bound is other than 139 * declared bounds). 140 */ 141 final List<Type> boundedVars() { 142 return filterVars(uv -> uv.getBounds(InferenceBound.UPPER) 143 .diff(uv.getDeclaredBounds()) 144 .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty()); 145 } 146 147 /* Returns the corresponding inference variables. 148 */ 149 private List<Type> filterVars(Filter<UndetVar> fu) { 150 ListBuffer<Type> res = new ListBuffer<>(); 151 for (Type t : undetvars) { 152 UndetVar uv = (UndetVar)t; 153 if (fu.accepts(uv)) { 154 res.append(uv.qtype); 155 } 156 } 157 return res.toList(); 158 } 159 160 /** 161 * is this type free? 162 */ 163 final boolean free(Type t) { 164 return t.containsAny(inferencevars); 165 } 166 167 final boolean free(List<Type> ts) { 168 for (Type t : ts) { 169 if (free(t)) return true; 170 } 171 return false; 172 } 173 174 /** 175 * Returns a list of free variables in a given type 176 */ 177 final List<Type> freeVarsIn(Type t) { 178 ListBuffer<Type> buf = new ListBuffer<>(); 179 for (Type iv : inferenceVars()) { 180 if (t.contains(iv)) { 181 buf.add(iv); 182 } 183 } 184 return buf.toList(); 185 } 186 187 final List<Type> freeVarsIn(List<Type> ts) { 188 ListBuffer<Type> buf = new ListBuffer<>(); 189 for (Type t : ts) { 190 buf.appendList(freeVarsIn(t)); 191 } 192 ListBuffer<Type> buf2 = new ListBuffer<>(); 193 for (Type t : buf) { 194 if (!buf2.contains(t)) { 195 buf2.add(t); 196 } 197 } 198 return buf2.toList(); 199 } 200 201 /** 202 * Replace all free variables in a given type with corresponding 203 * undet vars (used ahead of subtyping/compatibility checks to allow propagation 204 * of inference constraints). 205 */ 206 public final Type asUndetVar(Type t) { 207 return types.subst(t, inferencevars, undetvars); 208 } 209 210 final List<Type> asUndetVars(List<Type> ts) { 211 ListBuffer<Type> buf = new ListBuffer<>(); 212 for (Type t : ts) { 213 buf.append(asUndetVar(t)); 214 } 215 return buf.toList(); 216 } 217 218 List<Type> instTypes() { 219 ListBuffer<Type> buf = new ListBuffer<>(); 220 for (Type t : undetvars) { 221 UndetVar uv = (UndetVar)t; 222 buf.append(uv.getInst() != null ? uv.getInst() : uv.qtype); 223 } 224 return buf.toList(); 225 } 226 227 /** 228 * Replace all free variables in a given type with corresponding 229 * instantiated types - if one or more free variable has not been 230 * fully instantiated, it will still be available in the resulting type. 231 */ 232 Type asInstType(Type t) { 233 return types.subst(t, inferencevars, instTypes()); 234 } 235 236 List<Type> asInstTypes(List<Type> ts) { 237 ListBuffer<Type> buf = new ListBuffer<>(); 238 for (Type t : ts) { 239 buf.append(asInstType(t)); 240 } 241 return buf.toList(); 242 } 243 244 /** 245 * Add custom hook for performing post-inference action 246 */ 247 void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) { 248 freeTypeListeners.put(ftl, freeVarsIn(types)); 249 } 250 251 /** 252 * Mark the inference context as complete and trigger evaluation 253 * of all deferred checks. 254 */ 255 void notifyChange() { 256 notifyChange(inferencevars.diff(restvars())); 257 } 258 259 void notifyChange(List<Type> inferredVars) { 260 InferenceException thrownEx = null; 261 for (Map.Entry<FreeTypeListener, List<Type>> entry : 262 new LinkedHashMap<>(freeTypeListeners).entrySet()) { 263 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) { 264 try { 265 entry.getKey().typesInferred(this); 266 freeTypeListeners.remove(entry.getKey()); 267 } catch (InferenceException ex) { 268 if (thrownEx == null) { 269 thrownEx = ex; 270 } 271 } 272 } 273 } 274 //inference exception multiplexing - present any inference exception 275 //thrown when processing listeners as a single one 276 if (thrownEx != null) { 277 throw thrownEx; 278 } 279 } 280 281 /** 282 * Save the state of this inference context 283 */ 284 public List<Type> save() { 285 ListBuffer<Type> buf = new ListBuffer<>(); 286 for (Type t : undetvars) { 287 buf.add(((UndetVar)t).dup(infer.types)); 288 } 289 return buf.toList(); 290 } 291 292 /** Restore the state of this inference context to the previous known checkpoint. 293 * Consider that the number of saved undetermined variables can be different to the current 294 * amount. This is because new captured variables could have been added. 295 */ 296 public void rollback(List<Type> saved_undet) { 297 Assert.check(saved_undet != null); 298 //restore bounds (note: we need to preserve the old instances) 299 ListBuffer<Type> newUndetVars = new ListBuffer<>(); 300 ListBuffer<Type> newInferenceVars = new ListBuffer<>(); 301 while (saved_undet.nonEmpty() && undetvars.nonEmpty()) { 302 UndetVar uv = (UndetVar)undetvars.head; 303 UndetVar uv_saved = (UndetVar)saved_undet.head; 304 if (uv.qtype == uv_saved.qtype) { 305 uv_saved.dupTo(uv, types); 306 undetvars = undetvars.tail; 307 saved_undet = saved_undet.tail; 308 newUndetVars.add(uv); 309 newInferenceVars.add(uv.qtype); 310 } else { 311 undetvars = undetvars.tail; 312 } 313 } 314 undetvars = newUndetVars.toList(); 315 inferencevars = newInferenceVars.toList(); 316 } 317 318 /** 319 * Copy variable in this inference context to the given context 320 */ 321 void dupTo(final InferenceContext that) { 322 dupTo(that, false); 323 } 324 325 void dupTo(final InferenceContext that, boolean clone) { 326 that.inferencevars = that.inferencevars.appendList(inferencevars.diff(that.inferencevars)); 327 List<Type> undetsToPropagate = clone ? save() : undetvars; 328 that.undetvars = that.undetvars.appendList(undetsToPropagate.diff(that.undetvars)); //propagate cloned undet!! 329 //set up listeners to notify original inference contexts as 330 //propagated vars are inferred in new context 331 for (Type t : inferencevars) { 332 that.freeTypeListeners.put(inferenceContext -> InferenceContext.this.notifyChange(), List.of(t)); 333 } 334 } 335 336 InferenceContext min(List<Type> roots, boolean shouldSolve, Warner warn) { 337 if (roots.length() == inferencevars.length()) { 338 return this; 339 } 340 ReachabilityVisitor rv = new ReachabilityVisitor(); 341 rv.scan(roots); 342 if (rv.min.size() == inferencevars.length()) { 343 return this; 344 } 345 346 List<Type> minVars = List.from(rv.min); 347 List<Type> redundantVars = inferencevars.diff(minVars); 348 349 //compute new undet variables (bounds associated to redundant variables are dropped) 350 ListBuffer<Type> minUndetVars = new ListBuffer<>(); 351 for (Type minVar : minVars) { 352 UndetVar uv = (UndetVar)asUndetVar(minVar); 353 Assert.check(uv.incorporationActions.isEmpty()); 354 UndetVar uv2 = uv.dup(types); 355 for (InferenceBound ib : InferenceBound.values()) { 356 List<Type> newBounds = uv.getBounds(ib).stream() 357 .filter(b -> !redundantVars.contains(b)) 358 .collect(List.collector()); 359 uv2.setBounds(ib, newBounds); 360 } 361 minUndetVars.add(uv2); 362 } 363 364 //compute new minimal inference context 365 InferenceContext minContext = new InferenceContext(infer, minVars, minUndetVars.toList()); 366 for (Type t : minContext.inferencevars) { 367 //add listener that forwards notifications to original context 368 minContext.addFreeTypeListener(List.of(t), (inferenceContext) -> { 369 ((UndetVar)asUndetVar(t)).setInst(inferenceContext.asInstType(t)); 370 infer.doIncorporation(inferenceContext, warn); 371 solve(List.from(rv.minMap.get(t)), warn); 372 notifyChange(); 373 }); 374 } 375 if (shouldSolve) { 376 //solve definitively unreachable variables 377 List<Type> unreachableVars = redundantVars.diff(List.from(rv.equiv)); 378 minContext.addFreeTypeListener(minVars, (inferenceContext) -> { 379 solve(unreachableVars, warn); 380 notifyChange(); 381 }); 382 } 383 return minContext; 384 } 385 386 class ReachabilityVisitor extends Types.UnaryVisitor<Void> { 387 388 Set<Type> equiv = new HashSet<>(); 389 Set<Type> min = new HashSet<>(); 390 Map<Type, Set<Type>> minMap = new HashMap<>(); 391 392 void scan(List<Type> roots) { 393 roots.stream().forEach(this::visit); 394 } 395 396 @Override 397 public Void visitType(Type t, Void _unused) { 398 return null; 399 } 400 401 @Override 402 public Void visitUndetVar(UndetVar t, Void _unused) { 403 if (min.add(t.qtype)) { 404 Set<Type> deps = minMap.getOrDefault(t.qtype, new HashSet<>(Collections.singleton(t.qtype))); 405 for (InferenceBound boundKind : InferenceBound.values()) { 406 for (Type b : t.getBounds(boundKind)) { 407 Type undet = asUndetVar(b); 408 if (!undet.hasTag(TypeTag.UNDETVAR)) { 409 visit(undet); 410 } else if (isEquiv(t, b, boundKind)) { 411 deps.add(b); 412 equiv.add(b); 413 } else { 414 visit(undet); 415 } 416 } 417 } 418 minMap.put(t.qtype, deps); 419 } 420 return null; 421 } 422 423 @Override 424 public Void visitWildcardType(WildcardType t, Void _unused) { 425 return visit(t.type); 426 } 427 428 @Override 429 public Void visitTypeVar(TypeVar t, Void aVoid) { 430 Type undet = asUndetVar(t); 431 if (undet.hasTag(TypeTag.UNDETVAR)) { 432 visitUndetVar((UndetVar)undet, null); 433 } 434 return null; 435 } 436 437 @Override 438 public Void visitArrayType(ArrayType t, Void _unused) { 439 return visit(t.elemtype); 440 } 441 442 @Override 443 public Void visitClassType(ClassType t, Void _unused) { 444 visit(t.getEnclosingType()); 445 for (Type targ : t.getTypeArguments()) { 446 visit(targ); 447 } 448 return null; 449 } 450 451 boolean isEquiv(UndetVar from, Type t, InferenceBound boundKind) { 452 UndetVar uv = (UndetVar)asUndetVar(t); 453 for (InferenceBound ib : InferenceBound.values()) { 454 List<Type> b1 = from.getBounds(ib); 455 if (ib == boundKind) { 456 b1 = b1.diff(List.of(t)); 457 } 458 List<Type> b2 = uv.getBounds(ib); 459 if (ib == boundKind.complement()) { 460 b2 = b2.diff(List.of(from.qtype)); 461 } 462 if (!b1.containsAll(b2) || !b2.containsAll(b1)) { 463 return false; 464 } 465 } 466 return true; 467 } 468 } 469 470 /** 471 * Solve with given graph strategy. 472 */ 473 private void solve(GraphStrategy ss, Warner warn) { 474 GraphSolver s = infer.new GraphSolver(this, warn); 475 s.solve(ss); 476 } 477 478 /** 479 * Solve all variables in this context. 480 */ 481 public void solve(Warner warn) { 482 solve(infer.new LeafSolver() { 483 public boolean done() { 484 return restvars().isEmpty(); 485 } 486 }, warn); 487 } 488 489 /** 490 * Solve all variables in the given list. 491 */ 492 public void solve(final List<Type> vars, Warner warn) { 493 solve(infer.new BestLeafSolver(vars) { 494 public boolean done() { 495 return !free(asInstTypes(vars)); 496 } 497 }, warn); 498 } 499 500 /** 501 * Solve at least one variable in given list. 502 */ 503 public void solveAny(List<Type> varsToSolve, Warner warn) { 504 solve(infer.new BestLeafSolver(varsToSolve.intersect(restvars())) { 505 public boolean done() { 506 return instvars().intersect(varsToSolve).nonEmpty(); 507 } 508 }, warn); 509 } 510 511 /** 512 * Apply a set of inference steps 513 */ 514 private List<Type> solveBasic(EnumSet<InferenceStep> steps) { 515 return solveBasic(inferencevars, steps); 516 } 517 518 List<Type> solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) { 519 ListBuffer<Type> solvedVars = new ListBuffer<>(); 520 for (Type t : varsToSolve.intersect(restvars())) { 521 UndetVar uv = (UndetVar)asUndetVar(t); 522 for (InferenceStep step : steps) { 523 if (step.accepts(uv, this)) { 524 uv.setInst(step.solve(uv, this)); 525 solvedVars.add(uv.qtype); 526 break; 527 } 528 } 529 } 530 return solvedVars.toList(); 531 } 532 533 /** 534 * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8). 535 * During overload resolution, instantiation is done by doing a partial 536 * inference process using eq/lower bound instantiation. During check, 537 * we also instantiate any remaining vars by repeatedly using eq/upper 538 * instantiation, until all variables are solved. 539 */ 540 public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) { 541 while (true) { 542 List<Type> solvedVars = solveBasic(steps); 543 if (restvars().isEmpty() || partial) { 544 //all variables have been instantiated - exit 545 break; 546 } else if (solvedVars.isEmpty()) { 547 //some variables could not be instantiated because of cycles in 548 //upper bounds - provide a (possibly recursive) default instantiation 549 infer.instantiateAsUninferredVars(restvars(), this); 550 break; 551 } else { 552 //some variables have been instantiated - replace newly instantiated 553 //variables in remaining upper bounds and continue 554 for (Type t : undetvars) { 555 UndetVar uv = (UndetVar)t; 556 uv.substBounds(solvedVars, asInstTypes(solvedVars), types); 557 } 558 } 559 } 560 infer.doIncorporation(this, warn); 561 } 562 563 @Override 564 public String toString() { 565 return "Inference vars: " + inferencevars + '\n' + 566 "Undet vars: " + undetvars; 567 } 568 569 /* Method Types.capture() generates a new type every time it's applied 570 * to a wildcard parameterized type. This is intended functionality but 571 * there are some cases when what you need is not to generate a new 572 * captured type but to check that a previously generated captured type 573 * is correct. There are cases when caching a captured type for later 574 * reuse is sound. In general two captures from the same AST are equal. 575 * This is why the tree is used as the key of the map below. This map 576 * stores a Type per AST. 577 */ 578 Map<JCTree, Type> captureTypeCache = new HashMap<>(); 579 580 Type cachedCapture(JCTree tree, Type t, boolean readOnly) { 581 Type captured = captureTypeCache.get(tree); 582 if (captured != null) { 583 return captured; 584 } 585 586 Type result = types.capture(t); 587 if (result != t && !readOnly) { // then t is a wildcard parameterized type 588 captureTypeCache.put(tree, result); 589 } 590 return result; 591 } 592} 593