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 
  26 package com.sun.tools.javac.comp;
  27 
  28 import java.util.Collections;
  29 import java.util.EnumSet;
  30 import java.util.HashMap;
  31 import java.util.HashSet;
  32 import java.util.LinkedHashMap;
  33 import java.util.Map;
  34 import java.util.Set;
  35 
  36 import com.sun.tools.javac.code.Type;
  37 import com.sun.tools.javac.code.Type.ArrayType;
  38 import com.sun.tools.javac.code.Type.ClassType;
  39 import com.sun.tools.javac.code.Type.TypeVar;
  40 import com.sun.tools.javac.code.Type.UndetVar;
  41 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
  42 import com.sun.tools.javac.code.Type.WildcardType;
  43 import com.sun.tools.javac.code.TypeTag;
  44 import com.sun.tools.javac.code.Types;
  45 import com.sun.tools.javac.comp.Infer.FreeTypeListener;
  46 import com.sun.tools.javac.comp.Infer.GraphSolver;
  47 import com.sun.tools.javac.comp.Infer.GraphStrategy;
  48 import com.sun.tools.javac.comp.Infer.InferenceException;
  49 import com.sun.tools.javac.comp.Infer.InferenceStep;
  50 import com.sun.tools.javac.tree.JCTree;
  51 import com.sun.tools.javac.util.Assert;
  52 import com.sun.tools.javac.util.Filter;
  53 import com.sun.tools.javac.util.List;
  54 import com.sun.tools.javac.util.ListBuffer;
  55 import 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  */
  70 public 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 }