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