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