1 /*
2 * Copyright (c) 1999, 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 com.sun.tools.javac.code.Source.Feature;
29 import com.sun.tools.javac.code.Type.UndetVar.UndetVarListener;
30 import com.sun.tools.javac.code.Types.TypeMapping;
31 import com.sun.tools.javac.comp.Attr.CheckMode;
32 import com.sun.tools.javac.resources.CompilerProperties.Fragments;
33 import com.sun.tools.javac.resources.CompilerProperties.Notes;
34 import com.sun.tools.javac.tree.JCTree;
35 import com.sun.tools.javac.tree.JCTree.JCTypeCast;
36 import com.sun.tools.javac.tree.TreeInfo;
37 import com.sun.tools.javac.util.*;
38 import com.sun.tools.javac.util.GraphUtils.DottableNode;
39 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
40 import com.sun.tools.javac.util.JCDiagnostic.Fragment;
41 import com.sun.tools.javac.util.List;
42 import com.sun.tools.javac.code.*;
43 import com.sun.tools.javac.code.Type.*;
44 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
45 import com.sun.tools.javac.code.Symbol.*;
46 import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
47 import com.sun.tools.javac.comp.DeferredAttr.DeferredAttrContext;
48 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
49 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
50 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
51 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
52
53 import java.io.IOException;
54 import java.io.Writer;
55 import java.nio.file.Files;
56 import java.nio.file.Path;
57 import java.nio.file.Paths;
58 import java.util.ArrayList;
59 import java.util.Collection;
60 import java.util.Collections;
61 import java.util.EnumSet;
62 import java.util.HashMap;
63 import java.util.HashSet;
64 import java.util.LinkedHashSet;
65 import java.util.Map;
66 import java.util.Optional;
67 import java.util.Properties;
68 import java.util.Set;
69 import java.util.function.BiFunction;
70 import java.util.function.BiPredicate;
71
72 import static com.sun.tools.javac.code.TypeTag.*;
73
74 /** Helper class for type parameter inference, used by the attribution phase.
75 *
76 * <p><b>This is NOT part of any supported API.
77 * If you write code that depends on this, you do so at your own risk.
78 * This code and its internal interfaces are subject to change or
79 * deletion without notice.</b>
80 */
81 public class Infer {
82 protected static final Context.Key<Infer> inferKey = new Context.Key<>();
83
84 Resolve rs;
85 Check chk;
86 Symtab syms;
87 Types types;
88 JCDiagnostic.Factory diags;
89 Log log;
90
91 /** should the graph solver be used? */
92 boolean allowGraphInference;
93
94 /**
95 * folder in which the inference dependency graphs should be written.
96 */
97 private final String dependenciesFolder;
98
99 /**
100 * List of graphs awaiting to be dumped to a file.
101 */
102 private List<String> pendingGraphs;
103
104 public static Infer instance(Context context) {
105 Infer instance = context.get(inferKey);
106 if (instance == null)
107 instance = new Infer(context);
108 return instance;
109 }
110
111 protected Infer(Context context) {
112 context.put(inferKey, this);
113
114 rs = Resolve.instance(context);
115 chk = Check.instance(context);
116 syms = Symtab.instance(context);
117 types = Types.instance(context);
118 diags = JCDiagnostic.Factory.instance(context);
119 log = Log.instance(context);
120 Options options = Options.instance(context);
121 Source source = Source.instance(context);
122 allowGraphInference = Feature.GRAPH_INFERENCE.allowedInSource(source)
123 && options.isUnset("useLegacyInference");
124 dependenciesFolder = options.get("debug.dumpInferenceGraphsTo");
125 pendingGraphs = List.nil();
126
127 emptyContext = new InferenceContext(this, List.nil());
128 }
129
130 /** A value for prototypes that admit any type, including polymorphic ones. */
131 public static final Type anyPoly = new JCNoType();
132
133 /**
134 * This exception class is design to store a list of diagnostics corresponding
135 * to inference errors that can arise during a method applicability check.
136 */
137 public static class InferenceException extends InapplicableMethodException {
138 private static final long serialVersionUID = 0;
139
140 transient List<JCDiagnostic> messages = List.nil();
141
142 InferenceException() {
143 super(null);
144 }
145
146 @Override
147 public JCDiagnostic getDiagnostic() {
148 return messages.head;
149 }
150 }
151
152 InferenceException error(JCDiagnostic diag) {
153 InferenceException result = new InferenceException();
154 if (diag != null) {
155 result.messages = result.messages.append(diag);
156 }
157 return result;
158 }
159
160 // <editor-fold defaultstate="collapsed" desc="Inference routines">
161 /**
162 * Main inference entry point - instantiate a generic method type
163 * using given argument types and (possibly) an expected target-type.
164 */
165 Type instantiateMethod( Env<AttrContext> env,
166 List<Type> tvars,
167 MethodType mt,
168 Attr.ResultInfo resultInfo,
169 MethodSymbol msym,
170 List<Type> argtypes,
171 boolean allowBoxing,
172 boolean useVarargs,
173 Resolve.MethodResolutionContext resolveContext,
174 Warner warn) throws InferenceException {
175 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
176 final InferenceContext inferenceContext = new InferenceContext(this, tvars); //B0
177 try {
178 DeferredAttr.DeferredAttrContext deferredAttrContext =
179 resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
180
181 resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2
182 argtypes, mt.getParameterTypes(), warn);
183
184 if (allowGraphInference && resultInfo != null && resultInfo.pt == anyPoly) {
185 doIncorporation(inferenceContext, warn);
186 //we are inside method attribution - just return a partially inferred type
187 return new PartiallyInferredMethodType(mt, inferenceContext, env, warn);
188 } else if (allowGraphInference && resultInfo != null) {
189
190 //inject return constraints earlier
191 doIncorporation(inferenceContext, warn); //propagation
192
193 if (!warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
194 boolean shouldPropagate = shouldPropagate(mt.getReturnType(), resultInfo, inferenceContext);
195
196 InferenceContext minContext = shouldPropagate ?
197 inferenceContext.min(roots(mt, deferredAttrContext), true, warn) :
198 inferenceContext;
199
200 Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3
201 mt, minContext);
202 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
203
204 //propagate outwards if needed
205 if (shouldPropagate) {
206 //propagate inference context outwards and exit
207 minContext.dupTo(resultInfo.checkContext.inferenceContext());
208 deferredAttrContext.complete();
209 return mt;
210 }
211 }
212 }
213
214 deferredAttrContext.complete();
215
216 // minimize as yet undetermined type variables
217 if (allowGraphInference) {
218 inferenceContext.solve(warn);
219 } else {
220 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
221 }
222
223 mt = (MethodType)inferenceContext.asInstType(mt);
224
225 if (!allowGraphInference &&
226 inferenceContext.restvars().nonEmpty() &&
227 resultInfo != null &&
228 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
229 generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext);
230 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
231 mt = (MethodType)inferenceContext.asInstType(mt);
232 }
233
234 if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
235 log.note(env.tree.pos, Notes.DeferredMethodInst(msym, mt, resultInfo.pt));
236 }
237
238 // return instantiated version of method type
239 return mt;
240 } finally {
241 if (resultInfo != null || !allowGraphInference) {
242 inferenceContext.notifyChange();
243 } else {
244 inferenceContext.notifyChange(inferenceContext.boundedVars());
245 }
246 if (resultInfo == null) {
247 /* if the is no result info then we can clear the capture types
248 * cache without affecting any result info check
249 */
250 inferenceContext.captureTypeCache.clear();
251 }
252 dumpGraphsIfNeeded(env.tree, msym, resolveContext);
253 }
254 }
255 //where
256 private boolean shouldPropagate(Type restype, Attr.ResultInfo target, InferenceContext inferenceContext) {
257 return target.checkContext.inferenceContext() != emptyContext && //enclosing context is a generic method
258 inferenceContext.free(restype) && //return type contains inference vars
259 (!inferenceContext.inferencevars.contains(restype) || //no eager instantiation is required (as per 18.5.2)
260 !needsEagerInstantiation((UndetVar)inferenceContext.asUndetVar(restype), target.pt, inferenceContext));
261 }
262
263 private List<Type> roots(MethodType mt, DeferredAttrContext deferredAttrContext) {
264 if (deferredAttrContext != null && deferredAttrContext.mode == AttrMode.CHECK) {
265 ListBuffer<Type> roots = new ListBuffer<>();
266 roots.add(mt.getReturnType());
267 for (DeferredAttr.DeferredAttrNode n : deferredAttrContext.deferredAttrNodes) {
268 roots.addAll(n.deferredStuckPolicy.stuckVars());
269 roots.addAll(n.deferredStuckPolicy.depVars());
270 }
271 List<Type> thrownVars = deferredAttrContext.inferenceContext.inferencevars.stream()
272 .filter(tv -> (tv.tsym.flags() & Flags.THROWS) != 0).collect(List.collector());
273 List<Type> result = roots.toList();
274 result = result.appendList(thrownVars.diff(result));
275 return result;
276 } else {
277 return List.of(mt.getReturnType());
278 }
279 }
280
281 /**
282 * A partially infered method/constructor type; such a type can be checked multiple times
283 * against different targets.
284 */
285 public class PartiallyInferredMethodType extends MethodType {
286 public PartiallyInferredMethodType(MethodType mtype, InferenceContext inferenceContext, Env<AttrContext> env, Warner warn) {
287 super(mtype.getParameterTypes(), mtype.getReturnType(), mtype.getThrownTypes(), mtype.tsym);
288 this.inferenceContext = inferenceContext;
289 this.env = env;
290 this.warn = warn;
291 }
292
293 /** The inference context. */
294 final InferenceContext inferenceContext;
295
296 /** The attribution environment. */
297 Env<AttrContext> env;
298
299 /** The warner. */
300 final Warner warn;
301
302 @Override
303 public boolean isPartial() {
304 return true;
305 }
306
307 /**
308 * Checks this type against a target; this means generating return type constraints, solve
309 * and then roll back the results (to avoid poolluting the context).
310 */
311 Type check(Attr.ResultInfo resultInfo) {
312 Warner noWarnings = new Warner(null);
313 List<Type> saved_undet = null;
314 try {
315 /** we need to save the inference context before generating target type constraints.
316 * This constraints may pollute the inference context and make it useless in case we
317 * need to use it several times: with several targets.
318 */
319 saved_undet = inferenceContext.save();
320 boolean unchecked = warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED);
321 if (!unchecked) {
322 boolean shouldPropagate = shouldPropagate(getReturnType(), resultInfo, inferenceContext);
323
324 InferenceContext minContext = shouldPropagate ?
325 inferenceContext.min(roots(asMethodType(), null), false, warn) :
326 inferenceContext;
327
328 MethodType other = (MethodType)minContext.update(asMethodType());
329 Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3
330 other, minContext);
331
332 if (shouldPropagate) {
333 //propagate inference context outwards and exit
334 minContext.dupTo(resultInfo.checkContext.inferenceContext(),
335 resultInfo.checkContext.deferredAttrContext().insideOverloadPhase());
336 return newRestype;
337 }
338 }
339 inferenceContext.solve(noWarnings);
340 Type ret = inferenceContext.asInstType(this).getReturnType();
341 if (unchecked) {
342 //inline logic from Attr.checkMethod - if unchecked conversion was required, erase
343 //return type _after_ resolution, and check against target
344 ret = types.erasure(ret);
345 }
346 return resultInfo.check(env.tree, ret);
347 } catch (InferenceException ex) {
348 resultInfo.checkContext.report(null, ex.getDiagnostic());
349 Assert.error(); //cannot get here (the above should throw)
350 return null;
351 } finally {
352 if (saved_undet != null) {
353 inferenceContext.rollback(saved_undet);
354 }
355 }
356 }
357 }
358
359 private void dumpGraphsIfNeeded(DiagnosticPosition pos, Symbol msym, Resolve.MethodResolutionContext rsContext) {
360 int round = 0;
361 try {
362 for (String graph : pendingGraphs.reverse()) {
363 Assert.checkNonNull(dependenciesFolder);
364 Name name = msym.name == msym.name.table.names.init ?
365 msym.owner.name : msym.name;
366 String filename = String.format("%s@%s[mode=%s,step=%s]_%d.dot",
367 name,
368 pos.getStartPosition(),
369 rsContext.attrMode(),
370 rsContext.step,
371 round);
372 Path dotFile = Paths.get(dependenciesFolder, filename);
373 try (Writer w = Files.newBufferedWriter(dotFile)) {
374 w.append(graph);
375 }
376 round++;
377 }
378 } catch (IOException ex) {
379 Assert.error("Error occurred when dumping inference graph: " + ex.getMessage());
380 } finally {
381 pendingGraphs = List.nil();
382 }
383 }
384
385 /**
386 * Generate constraints from the generic method's return type. If the method
387 * call occurs in a context where a type T is expected, use the expected
388 * type to derive more constraints on the generic method inference variables.
389 */
390 Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo,
391 MethodType mt, InferenceContext inferenceContext) {
392 InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext();
393 Type from = mt.getReturnType();
394 if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
395 rsInfoInfContext != emptyContext) {
396 from = types.capture(from);
397 //add synthetic captured ivars
398 for (Type t : from.getTypeArguments()) {
399 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
400 inferenceContext.addVar((TypeVar)t);
401 }
402 }
403 }
404 Type qtype = inferenceContext.asUndetVar(from);
405 Type to = resultInfo.pt;
406
407 if (qtype.hasTag(VOID)) {
408 to = syms.voidType;
409 } else if (to.hasTag(NONE)) {
410 to = from.isPrimitive() ? from : syms.objectType;
411 } else if (qtype.hasTag(UNDETVAR)) {
412 if (needsEagerInstantiation((UndetVar)qtype, to, inferenceContext) &&
413 (allowGraphInference || !to.isPrimitive())) {
414 to = generateReferenceToTargetConstraint(tree, (UndetVar)qtype, to, resultInfo, inferenceContext);
415 }
416 } else if (rsInfoInfContext.free(resultInfo.pt)) {
417 //propagation - cache captured vars
418 qtype = inferenceContext.asUndetVar(rsInfoInfContext.cachedCapture(tree, from, !resultInfo.checkMode.updateTreeType()));
419 }
420 Assert.check(allowGraphInference || !rsInfoInfContext.free(to),
421 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
422 //we need to skip capture?
423 Warner retWarn = new Warner();
424 if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) ||
425 //unchecked conversion is not allowed in source 7 mode
426 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
427 throw error(diags.fragment(Fragments.InferNoConformingInstanceExists(inferenceContext.restvars(), mt.getReturnType(), to)));
428 }
429 return from;
430 }
431
432 private boolean needsEagerInstantiation(UndetVar from, Type to, InferenceContext inferenceContext) {
433 if (to.isPrimitive()) {
434 /* T is a primitive type, and one of the primitive wrapper classes is an instantiation,
435 * upper bound, or lower bound for alpha in B2.
436 */
437 for (Type t : from.getBounds(InferenceBound.values())) {
438 Type boundAsPrimitive = types.unboxedType(t);
439 if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) {
440 continue;
441 }
442 return true;
443 }
444 return false;
445 }
446
447 Type captureOfTo = types.capture(to);
448 /* T is a reference type, but is not a wildcard-parameterized type, and either
449 */
450 if (captureOfTo == to) { //not a wildcard parameterized type
451 /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha,
452 * where S is a wildcard-parameterized type, or
453 */
454 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
455 Type captureOfBound = types.capture(t);
456 if (captureOfBound != t) {
457 return true;
458 }
459 }
460
461 /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
462 * where S1 and S2 have supertypes that are two different
463 * parameterizations of the same generic class or interface.
464 */
465 for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) {
466 for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) {
467 if (aLowerBound != anotherLowerBound &&
468 !inferenceContext.free(aLowerBound) &&
469 !inferenceContext.free(anotherLowerBound) &&
470 commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) {
471 return true;
472 }
473 }
474 }
475 }
476
477 /* T is a parameterization of a generic class or interface, G,
478 * and B2 contains a bound of one of the forms alpha = S or S <: alpha,
479 * where there exists no type of the form G<...> that is a
480 * supertype of S, but the raw type G is a supertype of S
481 */
482 if (to.isParameterized()) {
483 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
484 Type sup = types.asSuper(t, to.tsym);
485 if (sup != null && sup.isRaw()) {
486 return true;
487 }
488 }
489 }
490 return false;
491 }
492
493 private boolean commonSuperWithDiffParameterization(Type t, Type s) {
494 for (Pair<Type, Type> supers : getParameterizedSupers(t, s)) {
495 if (!types.isSameType(supers.fst, supers.snd)) return true;
496 }
497 return false;
498 }
499
500 private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from,
501 Type to, Attr.ResultInfo resultInfo,
502 InferenceContext inferenceContext) {
503 inferenceContext.solve(List.of(from.qtype), new Warner());
504 inferenceContext.notifyChange();
505 Type capturedType = resultInfo.checkContext.inferenceContext()
506 .cachedCapture(tree, from.getInst(), !resultInfo.checkMode.updateTreeType());
507 if (types.isConvertible(capturedType,
508 resultInfo.checkContext.inferenceContext().asUndetVar(to))) {
509 //effectively skip additional return-type constraint generation (compatibility)
510 return syms.objectType;
511 }
512 return to;
513 }
514
515 /**
516 * Infer cyclic inference variables as described in 15.12.2.8.
517 */
518 void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
519 ListBuffer<Type> todo = new ListBuffer<>();
520 //step 1 - create fresh tvars
521 for (Type t : vars) {
522 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
523 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
524 if (Type.containsAny(upperBounds, vars)) {
525 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
526 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeIntersectionType(uv.getBounds(InferenceBound.UPPER)), syms.botType);
527 todo.append(uv);
528 uv.setInst(fresh_tvar.type);
529 } else if (upperBounds.nonEmpty()) {
530 uv.setInst(types.glb(upperBounds));
531 } else {
532 uv.setInst(syms.objectType);
533 }
534 }
535 //step 2 - replace fresh tvars in their bounds
536 List<Type> formals = vars;
537 for (Type t : todo) {
538 UndetVar uv = (UndetVar)t;
539 TypeVar ct = (TypeVar)uv.getInst();
540 ct.setUpperBound( types.glb(inferenceContext.asInstTypes(types.getBounds(ct))) );
541 if (ct.getUpperBound().isErroneous()) {
542 //report inference error if glb fails
543 reportBoundError(uv, InferenceBound.UPPER);
544 }
545 formals = formals.tail;
546 }
547 }
548
549 /**
550 * Compute a synthetic method type corresponding to the requested polymorphic
551 * method signature. The target return type is computed from the immediately
552 * enclosing scope surrounding the polymorphic-signature call.
553 */
554 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
555 MethodSymbol spMethod, // sig. poly. method or null if none
556 Resolve.MethodResolutionContext resolveContext,
557 List<Type> argtypes) {
558 final Type restype;
559
560 if (spMethod == null || types.isSameType(spMethod.getReturnType(), syms.objectType)) {
561 // The return type of the polymorphic signature is polymorphic,
562 // and is computed from the enclosing tree E, as follows:
563 // if E is a cast, then use the target type of the cast expression
564 // as a return type; if E is an expression statement, the return
565 // type is 'void'; otherwise
566 // the return type is simply 'Object'. A correctness check ensures
567 // that env.next refers to the lexically enclosing environment in
568 // which the polymorphic signature call environment is nested.
569
570 switch (env.next.tree.getTag()) {
571 case TYPECAST:
572 JCTypeCast castTree = (JCTypeCast)env.next.tree;
573 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
574 castTree.clazz.type :
575 syms.objectType;
576 break;
577 case EXEC:
578 JCTree.JCExpressionStatement execTree =
579 (JCTree.JCExpressionStatement)env.next.tree;
580 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
581 syms.voidType :
582 syms.objectType;
583 break;
584 default:
585 restype = syms.objectType;
586 }
587 } else {
588 // The return type of the polymorphic signature is fixed
589 // (not polymorphic)
590 restype = spMethod.getReturnType();
591 }
592
593 List<Type> paramtypes = argtypes.map(new ImplicitArgType(spMethod, resolveContext.step));
594 List<Type> exType = spMethod != null ?
595 spMethod.getThrownTypes() :
596 List.of(syms.throwableType); // make it throw all exceptions
597
598 MethodType mtype = new MethodType(paramtypes,
599 restype,
600 exType,
601 syms.methodClass);
602 return mtype;
603 }
604 //where
605 class ImplicitArgType extends DeferredAttr.DeferredTypeMap<Void> {
606
607 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
608 (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase);
609 }
610
611 @Override
612 public Type visitClassType(ClassType t, Void aVoid) {
613 return types.erasure(t);
614 }
615
616 @Override
617 public Type visitType(Type t, Void _unused) {
618 if (t.hasTag(DEFERRED)) {
619 return visit(super.visitType(t, null));
620 } else if (t.hasTag(BOT))
621 // nulls type as the marker type Null (which has no instances)
622 // infer as java.lang.Void for now
623 t = types.boxedClass(syms.voidType).type;
624 return t;
625 }
626 }
627
628 TypeMapping<Void> fromTypeVarFun = new StructuralTypeMapping<Void>() {
629 @Override
630 public Type visitTypeVar(TypeVar tv, Void aVoid) {
631 UndetVar uv = new UndetVar(tv, incorporationEngine(), types);
632 if ((tv.tsym.flags() & Flags.THROWS) != 0) {
633 uv.setThrow();
634 }
635 return uv;
636 }
637 };
638
639 /**
640 * This method is used to infer a suitable target SAM in case the original
641 * SAM type contains one or more wildcards. An inference process is applied
642 * so that wildcard bounds, as well as explicit lambda/method ref parameters
643 * (where applicable) are used to constraint the solution.
644 */
645 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
646 List<Type> paramTypes, Check.CheckContext checkContext) {
647 if (types.capture(funcInterface) == funcInterface) {
648 //if capture doesn't change the type then return the target unchanged
649 //(this means the target contains no wildcards!)
650 return funcInterface;
651 } else {
652 Type formalInterface = funcInterface.tsym.type;
653 InferenceContext funcInterfaceContext =
654 new InferenceContext(this, funcInterface.tsym.type.getTypeArguments());
655
656 Assert.check(paramTypes != null);
657 //get constraints from explicit params (this is done by
658 //checking that explicit param types are equal to the ones
659 //in the functional interface descriptors)
660 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
661 if (descParameterTypes.size() != paramTypes.size()) {
662 checkContext.report(pos, diags.fragment(Fragments.IncompatibleArgTypesInLambda));
663 return types.createErrorType(funcInterface);
664 }
665 for (Type p : descParameterTypes) {
666 if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) {
667 checkContext.report(pos, diags.fragment(Fragments.NoSuitableFunctionalIntfInst(funcInterface)));
668 return types.createErrorType(funcInterface);
669 }
670 paramTypes = paramTypes.tail;
671 }
672
673 List<Type> actualTypeargs = funcInterface.getTypeArguments();
674 for (Type t : funcInterfaceContext.undetvars) {
675 UndetVar uv = (UndetVar)t;
676 Optional<Type> inst = uv.getBounds(InferenceBound.EQ).stream()
677 .filter(b -> !b.containsAny(formalInterface.getTypeArguments())).findFirst();
678 uv.setInst(inst.orElse(actualTypeargs.head));
679 actualTypeargs = actualTypeargs.tail;
680 }
681
682 Type owntype = funcInterfaceContext.asInstType(formalInterface);
683 if (!chk.checkValidGenericType(owntype)) {
684 //if the inferred functional interface type is not well-formed,
685 //or if it's not a subtype of the original target, issue an error
686 checkContext.report(pos, diags.fragment(Fragments.NoSuitableFunctionalIntfInst(funcInterface)));
687 }
688 //propagate constraints as per JLS 18.2.1
689 checkContext.compatible(owntype, funcInterface, types.noWarnings);
690 return owntype;
691 }
692 }
693 // </editor-fold>
694
695 // <editor-fold defaultstate="collapsed" desc="Incorporation">
696
697 /**
698 * This class is the root of all incorporation actions.
699 */
700 public abstract class IncorporationAction {
701 UndetVar uv;
702 Type t;
703
704 IncorporationAction(UndetVar uv, Type t) {
705 this.uv = uv;
706 this.t = t;
707 }
708
709 public abstract IncorporationAction dup(UndetVar that);
710
711 /**
712 * Incorporation action entry-point. Subclasses should define the logic associated with
713 * this incorporation action.
714 */
715 abstract void apply(InferenceContext ic, Warner warn);
716
717 /**
718 * Helper function: perform subtyping through incorporation cache.
719 */
720 boolean isSubtype(Type s, Type t, Warner warn) {
721 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn);
722 }
723
724 /**
725 * Helper function: perform type-equivalence through incorporation cache.
726 */
727 boolean isSameType(Type s, Type t) {
728 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null);
729 }
730
731 @Override
732 public String toString() {
733 return String.format("%s[undet=%s,t=%s]", getClass().getSimpleName(), uv.qtype, t);
734 }
735 }
736
737 /**
738 * Bound-check incorporation action. A newly added bound is checked against existing bounds,
739 * to verify its compatibility; each bound is checked using either subtyping or type equivalence.
740 */
741 class CheckBounds extends IncorporationAction {
742
743 InferenceBound from;
744 BiFunction<InferenceContext, Type, Type> typeFunc;
745 BiPredicate<InferenceContext, Type> optFilter;
746
747 CheckBounds(UndetVar uv, Type t, InferenceBound from) {
748 this(uv, t, InferenceContext::asUndetVar, null, from);
749 }
750
751 CheckBounds(UndetVar uv, Type t, BiFunction<InferenceContext, Type, Type> typeFunc,
752 BiPredicate<InferenceContext, Type> typeFilter, InferenceBound from) {
753 super(uv, t);
754 this.from = from;
755 this.typeFunc = typeFunc;
756 this.optFilter = typeFilter;
757 }
758
759 @Override
760 public IncorporationAction dup(UndetVar that) {
761 return new CheckBounds(that, t, typeFunc, optFilter, from);
762 }
763
764 @Override
765 void apply(InferenceContext inferenceContext, Warner warn) {
766 t = typeFunc.apply(inferenceContext, t);
767 if (optFilter != null && optFilter.test(inferenceContext, t)) return;
768 for (InferenceBound to : boundsToCheck()) {
769 for (Type b : uv.getBounds(to)) {
770 b = typeFunc.apply(inferenceContext, b);
771 if (optFilter != null && optFilter.test(inferenceContext, b)) continue;
772 boolean success = checkBound(t, b, from, to, warn);
773 if (!success) {
774 report(from, to);
775 }
776 }
777 }
778 }
779
780 /**
781 * The list of bound kinds to be checked.
782 */
783 EnumSet<InferenceBound> boundsToCheck() {
784 return (from == InferenceBound.EQ) ?
785 EnumSet.allOf(InferenceBound.class) :
786 EnumSet.complementOf(EnumSet.of(from));
787 }
788
789 /**
790 * Is source type 's' compatible with target type 't' given source and target bound kinds?
791 */
792 boolean checkBound(Type s, Type t, InferenceBound ib_s, InferenceBound ib_t, Warner warn) {
793 if (ib_s.lessThan(ib_t)) {
794 return isSubtype(s, t, warn);
795 } else if (ib_t.lessThan(ib_s)) {
796 return isSubtype(t, s, warn);
797 } else {
798 return isSameType(s, t);
799 }
800 }
801
802 /**
803 * Report a bound check error.
804 */
805 void report(InferenceBound from, InferenceBound to) {
806 //this is a workaround to preserve compatibility with existing messages
807 if (from == to) {
808 reportBoundError(uv, from);
809 } else if (from == InferenceBound.LOWER || to == InferenceBound.EQ) {
810 reportBoundError(uv, to, from);
811 } else {
812 reportBoundError(uv, from, to);
813 }
814 }
815
816 @Override
817 public String toString() {
818 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, from);
819 }
820 }
821
822 /**
823 * Custom check executed by the legacy incorporation engine. Newly added bounds are checked
824 * against existing eq bounds.
825 */
826 class EqCheckLegacy extends CheckBounds {
827 EqCheckLegacy(UndetVar uv, Type t, InferenceBound from) {
828 super(uv, t, InferenceContext::asInstType, InferenceContext::free, from);
829 }
830
831 @Override
832 public IncorporationAction dup(UndetVar that) {
833 return new EqCheckLegacy(that, t, from);
834 }
835
836 @Override
837 EnumSet<InferenceBound> boundsToCheck() {
838 return (from == InferenceBound.EQ) ?
839 EnumSet.allOf(InferenceBound.class) :
840 EnumSet.of(InferenceBound.EQ);
841 }
842 }
843
844 /**
845 * Check that the inferred type conforms to all bounds.
846 */
847 class CheckInst extends CheckBounds {
848
849 EnumSet<InferenceBound> to;
850
851 CheckInst(UndetVar uv, InferenceBound ib, InferenceBound... rest) {
852 this(uv, EnumSet.of(ib, rest));
853 }
854
855 CheckInst(UndetVar uv, EnumSet<InferenceBound> to) {
856 super(uv, uv.getInst(), InferenceBound.EQ);
857 this.to = to;
858 }
859
860 @Override
861 public IncorporationAction dup(UndetVar that) {
862 return new CheckInst(that, to);
863 }
864
865 @Override
866 EnumSet<InferenceBound> boundsToCheck() {
867 return to;
868 }
869
870 @Override
871 void report(InferenceBound from, InferenceBound to) {
872 reportInstError(uv, to);
873 }
874 }
875
876 /**
877 * Replace undetvars in bounds and check that the inferred type conforms to all bounds.
878 */
879 class SubstBounds extends CheckInst {
880 SubstBounds(UndetVar uv) {
881 super(uv, InferenceBound.LOWER, InferenceBound.EQ, InferenceBound.UPPER);
882 }
883
884 @Override
885 public IncorporationAction dup(UndetVar that) {
886 return new SubstBounds(that);
887 }
888
889 @Override
890 void apply(InferenceContext inferenceContext, Warner warn) {
891 for (Type undet : inferenceContext.undetvars) {
892 //we could filter out variables not mentioning uv2...
893 UndetVar uv2 = (UndetVar)undet;
894 uv2.substBounds(List.of(uv.qtype), List.of(uv.getInst()), types);
895 checkCompatibleUpperBounds(uv2, inferenceContext);
896 }
897 super.apply(inferenceContext, warn);
898 }
899
900 /**
901 * Make sure that the upper bounds we got so far lead to a solvable inference
902 * variable by making sure that a glb exists.
903 */
904 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
905 List<Type> hibounds =
906 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
907 final Type hb;
908 if (hibounds.isEmpty())
909 hb = syms.objectType;
910 else if (hibounds.tail.isEmpty())
911 hb = hibounds.head;
912 else
913 hb = types.glb(hibounds);
914 if (hb == null || hb.isErroneous())
915 reportBoundError(uv, InferenceBound.UPPER);
916 }
917 }
918
919 /**
920 * Perform pairwise comparison between common generic supertypes of two upper bounds.
921 */
922 class CheckUpperBounds extends IncorporationAction {
923
924 public CheckUpperBounds(UndetVar uv, Type t) {
925 super(uv, t);
926 }
927
928 @Override
929 public IncorporationAction dup(UndetVar that) {
930 return new CheckUpperBounds(that, t);
931 }
932
933 @Override
934 void apply(InferenceContext inferenceContext, Warner warn) {
935 List<Type> boundList = uv.getBounds(InferenceBound.UPPER).stream()
936 .collect(types.closureCollector(true, types::isSameType));
937 for (Type b2 : boundList) {
938 if (t == b2) continue;
939 /* This wildcard check is temporary workaround. This code may need to be
940 * revisited once spec bug JDK-7034922 is fixed.
941 */
942 if (t != b2 && !t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) {
943 for (Pair<Type, Type> commonSupers : getParameterizedSupers(t, b2)) {
944 List<Type> allParamsSuperBound1 = commonSupers.fst.allparams();
945 List<Type> allParamsSuperBound2 = commonSupers.snd.allparams();
946 while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) {
947 //traverse the list of all params comparing them
948 if (!allParamsSuperBound1.head.hasTag(WILDCARD) &&
949 !allParamsSuperBound2.head.hasTag(WILDCARD)) {
950 if (!isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head),
951 inferenceContext.asUndetVar(allParamsSuperBound2.head))) {
952 reportBoundError(uv, InferenceBound.UPPER);
953 }
954 }
955 allParamsSuperBound1 = allParamsSuperBound1.tail;
956 allParamsSuperBound2 = allParamsSuperBound2.tail;
957 }
958 Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty());
959 }
960 }
961 }
962 }
963 }
964
965 /**
966 * Perform propagation of bounds. Given a constraint of the kind {@code alpha <: T}, three
967 * kind of propagation occur:
968 *
969 * <li>T is copied into all matching bounds (i.e. lower/eq bounds) B of alpha such that B=beta (forward propagation)</li>
970 * <li>if T=beta, matching bounds (i.e. upper bounds) of beta are copied into alpha (backwards propagation)</li>
971 * <li>if T=beta, sets a symmetric bound on beta (i.e. beta :> alpha) (symmetric propagation) </li>
972 */
973 class PropagateBounds extends IncorporationAction {
974
975 InferenceBound ib;
976
977 public PropagateBounds(UndetVar uv, Type t, InferenceBound ib) {
978 super(uv, t);
979 this.ib = ib;
980 }
981
982 @Override
983 public IncorporationAction dup(UndetVar that) {
984 return new PropagateBounds(that, t, ib);
985 }
986
987 void apply(InferenceContext inferenceContext, Warner warner) {
988 Type undetT = inferenceContext.asUndetVar(t);
989 if (undetT.hasTag(UNDETVAR) && !((UndetVar)undetT).isCaptured()) {
990 UndetVar uv2 = (UndetVar)undetT;
991 //symmetric propagation
992 uv2.addBound(ib.complement(), uv, types);
993 //backwards propagation
994 for (InferenceBound ib2 : backwards()) {
995 for (Type b : uv2.getBounds(ib2)) {
996 uv.addBound(ib2, b, types);
997 }
998 }
999 }
1000 //forward propagation
1001 for (InferenceBound ib2 : forward()) {
1002 for (Type l : uv.getBounds(ib2)) {
1003 Type undet = inferenceContext.asUndetVar(l);
1004 if (undet.hasTag(TypeTag.UNDETVAR) && !((UndetVar)undet).isCaptured()) {
1005 UndetVar uv2 = (UndetVar)undet;
1006 uv2.addBound(ib, inferenceContext.asInstType(t), types);
1007 }
1008 }
1009 }
1010 }
1011
1012 EnumSet<InferenceBound> forward() {
1013 return (ib == InferenceBound.EQ) ?
1014 EnumSet.of(InferenceBound.EQ) : EnumSet.complementOf(EnumSet.of(ib));
1015 }
1016
1017 EnumSet<InferenceBound> backwards() {
1018 return (ib == InferenceBound.EQ) ?
1019 EnumSet.allOf(InferenceBound.class) : EnumSet.of(ib);
1020 }
1021
1022 @Override
1023 public String toString() {
1024 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, ib);
1025 }
1026 }
1027
1028 /**
1029 * This class models an incorporation engine. The engine is responsible for listening to
1030 * changes in inference variables and register incorporation actions accordingly.
1031 */
1032 abstract class AbstractIncorporationEngine implements UndetVarListener {
1033
1034 @Override
1035 public void varInstantiated(UndetVar uv) {
1036 uv.incorporationActions.addFirst(new SubstBounds(uv));
1037 }
1038
1039 @Override
1040 public void varBoundChanged(UndetVar uv, InferenceBound ib, Type bound, boolean update) {
1041 if (uv.isCaptured()) return;
1042 uv.incorporationActions.addAll(getIncorporationActions(uv, ib, bound, update));
1043 }
1044
1045 abstract List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update);
1046 }
1047
1048 /**
1049 * A legacy incorporation engine. Used for source <= 7.
1050 */
1051 AbstractIncorporationEngine legacyEngine = new AbstractIncorporationEngine() {
1052
1053 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) {
1054 ListBuffer<IncorporationAction> actions = new ListBuffer<>();
1055 Type inst = uv.getInst();
1056 if (inst != null) {
1057 actions.add(new CheckInst(uv, ib));
1058 }
1059 actions.add(new EqCheckLegacy(uv, t, ib));
1060 return actions.toList();
1061 }
1062 };
1063
1064 /**
1065 * The standard incorporation engine. Used for source >= 8.
1066 */
1067 AbstractIncorporationEngine graphEngine = new AbstractIncorporationEngine() {
1068
1069 @Override
1070 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) {
1071 ListBuffer<IncorporationAction> actions = new ListBuffer<>();
1072 Type inst = uv.getInst();
1073 if (inst != null) {
1074 actions.add(new CheckInst(uv, ib));
1075 }
1076 actions.add(new CheckBounds(uv, t, ib));
1077
1078 if (update) {
1079 return actions.toList();
1080 }
1081
1082 if (ib == InferenceBound.UPPER) {
1083 actions.add(new CheckUpperBounds(uv, t));
1084 }
1085
1086 actions.add(new PropagateBounds(uv, t, ib));
1087
1088 return actions.toList();
1089 }
1090 };
1091
1092 /**
1093 * Get the incorporation engine to be used in this compilation.
1094 */
1095 AbstractIncorporationEngine incorporationEngine() {
1096 return allowGraphInference ? graphEngine : legacyEngine;
1097 }
1098
1099 /** max number of incorporation rounds. */
1100 static final int MAX_INCORPORATION_STEPS = 10000;
1101
1102 /**
1103 * Check bounds and perform incorporation.
1104 */
1105 void doIncorporation(InferenceContext inferenceContext, Warner warn) throws InferenceException {
1106 try {
1107 boolean progress = true;
1108 int round = 0;
1109 while (progress && round < MAX_INCORPORATION_STEPS) {
1110 progress = false;
1111 for (Type t : inferenceContext.undetvars) {
1112 UndetVar uv = (UndetVar)t;
1113 if (!uv.incorporationActions.isEmpty()) {
1114 progress = true;
1115 uv.incorporationActions.removeFirst().apply(inferenceContext, warn);
1116 }
1117 }
1118 round++;
1119 }
1120 } finally {
1121 incorporationCache.clear();
1122 }
1123 }
1124
1125 /* If for two types t and s there is a least upper bound that contains
1126 * parameterized types G1, G2 ... Gn, then there exists supertypes of 't' of the form
1127 * G1<T1, ..., Tn>, G2<T1, ..., Tn>, ... Gn<T1, ..., Tn> and supertypes of 's' of the form
1128 * G1<S1, ..., Sn>, G2<S1, ..., Sn>, ... Gn<S1, ..., Sn> which will be returned by this method.
1129 * If no such common supertypes exists then an empty list is returned.
1130 *
1131 * As an example for the following input:
1132 *
1133 * t = java.util.ArrayList<java.lang.String>
1134 * s = java.util.List<T>
1135 *
1136 * we get this ouput (singleton list):
1137 *
1138 * [Pair[java.util.List<java.lang.String>,java.util.List<T>]]
1139 */
1140 private List<Pair<Type, Type>> getParameterizedSupers(Type t, Type s) {
1141 Type lubResult = types.lub(t, s);
1142 if (lubResult == syms.errType || lubResult == syms.botType) {
1143 return List.nil();
1144 }
1145 List<Type> supertypesToCheck = lubResult.isIntersection() ?
1146 ((IntersectionClassType)lubResult).getComponents() :
1147 List.of(lubResult);
1148 ListBuffer<Pair<Type, Type>> commonSupertypes = new ListBuffer<>();
1149 for (Type sup : supertypesToCheck) {
1150 if (sup.isParameterized()) {
1151 Type asSuperOfT = asSuper(t, sup);
1152 Type asSuperOfS = asSuper(s, sup);
1153 commonSupertypes.add(new Pair<>(asSuperOfT, asSuperOfS));
1154 }
1155 }
1156 return commonSupertypes.toList();
1157 }
1158 //where
1159 private Type asSuper(Type t, Type sup) {
1160 return (sup.hasTag(ARRAY)) ?
1161 new ArrayType(asSuper(types.elemtype(t), types.elemtype(sup)), syms.arrayClass) :
1162 types.asSuper(t, sup.tsym);
1163 }
1164
1165 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn) {
1166 IncorporationBinaryOp newOp = new IncorporationBinaryOp(opKind, op1, op2);
1167 Boolean res = incorporationCache.get(newOp);
1168 if (res == null) {
1169 incorporationCache.put(newOp, res = newOp.apply(warn));
1170 }
1171 return res;
1172 }
1173
1174 /**
1175 * Three kinds of basic operation are supported as part of an incorporation step:
1176 * (i) subtype check, (ii) same type check and (iii) bound addition (either
1177 * upper/lower/eq bound).
1178 */
1179 enum IncorporationBinaryOpKind {
1180 IS_SUBTYPE() {
1181 @Override
1182 boolean apply(Type op1, Type op2, Warner warn, Types types) {
1183 return types.isSubtypeUnchecked(op1, op2, warn);
1184 }
1185 },
1186 IS_SAME_TYPE() {
1187 @Override
1188 boolean apply(Type op1, Type op2, Warner warn, Types types) {
1189 return types.isSameType(op1, op2);
1190 }
1191 };
1192
1193 abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
1194 }
1195
1196 /**
1197 * This class encapsulates a basic incorporation operation; incorporation
1198 * operations takes two type operands and a kind. Each operation performed
1199 * during an incorporation round is stored in a cache, so that operations
1200 * are not executed unnecessarily (which would potentially lead to adding
1201 * same bounds over and over).
1202 */
1203 class IncorporationBinaryOp {
1204
1205 IncorporationBinaryOpKind opKind;
1206 Type op1;
1207 Type op2;
1208
1209 IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
1210 this.opKind = opKind;
1211 this.op1 = op1;
1212 this.op2 = op2;
1213 }
1214
1215 @Override
1216 public boolean equals(Object o) {
1217 if (!(o instanceof IncorporationBinaryOp)) {
1218 return false;
1219 } else {
1220 IncorporationBinaryOp that = (IncorporationBinaryOp)o;
1221 return opKind == that.opKind &&
1222 types.isSameType(op1, that.op1) &&
1223 types.isSameType(op2, that.op2);
1224 }
1225 }
1226
1227 @Override
1228 public int hashCode() {
1229 int result = opKind.hashCode();
1230 result *= 127;
1231 result += types.hashCode(op1);
1232 result *= 127;
1233 result += types.hashCode(op2);
1234 return result;
1235 }
1236
1237 boolean apply(Warner warn) {
1238 return opKind.apply(op1, op2, warn, types);
1239 }
1240 }
1241
1242 /** an incorporation cache keeps track of all executed incorporation-related operations */
1243 Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>();
1244
1245 protected static class BoundFilter implements Filter<Type> {
1246
1247 InferenceContext inferenceContext;
1248
1249 public BoundFilter(InferenceContext inferenceContext) {
1250 this.inferenceContext = inferenceContext;
1251 }
1252
1253 @Override
1254 public boolean accepts(Type t) {
1255 return !t.isErroneous() && !inferenceContext.free(t) &&
1256 !t.hasTag(BOT);
1257 }
1258 }
1259
1260 /**
1261 * Incorporation error: mismatch between inferred type and given bound.
1262 */
1263 void reportInstError(UndetVar uv, InferenceBound ib) {
1264 switch (ib) {
1265 case EQ:
1266 throw error(diags.fragment(Fragments.InferredDoNotConformToEqBounds(uv.getInst(), uv.getBounds(ib))));
1267 case LOWER:
1268 throw error(diags.fragment(Fragments.InferredDoNotConformToLowerBounds(uv.getInst(), uv.getBounds(ib))));
1269 case UPPER:
1270 throw error(diags.fragment(Fragments.InferredDoNotConformToUpperBounds(uv.getInst(), uv.getBounds(ib))));
1271 }
1272 }
1273
1274 /**
1275 * Incorporation error: mismatch between two (or more) bounds of same kind.
1276 */
1277 void reportBoundError(UndetVar uv, InferenceBound ib) {
1278 switch (ib) {
1279 case EQ:
1280 throw error(diags.fragment(Fragments.IncompatibleEqBounds(uv.qtype, uv.getBounds(ib))));
1281 case UPPER:
1282 throw error(diags.fragment(Fragments.IncompatibleUpperBounds(uv.qtype, uv.getBounds(ib))));
1283 case LOWER:
1284 throw new AssertionError("this case shouldn't happen");
1285 }
1286 }
1287
1288 /**
1289 * Incorporation error: mismatch between two (or more) bounds of different kinds.
1290 */
1291 void reportBoundError(UndetVar uv, InferenceBound ib1, InferenceBound ib2) {
1292 throw error(diags.fragment(Fragments.IncompatibleBounds(
1293 uv.qtype,
1294 getBoundFragment(ib1, uv.getBounds(ib1)),
1295 getBoundFragment(ib2, uv.getBounds(ib2)))));
1296 }
1297
1298 Fragment getBoundFragment(InferenceBound ib, List<Type> types) {
1299 switch (ib) {
1300 case EQ: return Fragments.EqBounds(types);
1301 case LOWER: return Fragments.LowerBounds(types);
1302 case UPPER: return Fragments.UpperBounds(types);
1303 }
1304 throw new AssertionError("can't get to this place");
1305 }
1306
1307 // </editor-fold>
1308
1309 // <editor-fold defaultstate="collapsed" desc="Inference engine">
1310 /**
1311 * Graph inference strategy - act as an input to the inference solver; a strategy is
1312 * composed of two ingredients: (i) find a node to solve in the inference graph,
1313 * and (ii) tell th engine when we are done fixing inference variables
1314 */
1315 interface GraphStrategy {
1316
1317 /**
1318 * A NodeNotFoundException is thrown whenever an inference strategy fails
1319 * to pick the next node to solve in the inference graph.
1320 */
1321 public static class NodeNotFoundException extends RuntimeException {
1322 private static final long serialVersionUID = 0;
1323
1324 transient InferenceGraph graph;
1325
1326 public NodeNotFoundException(InferenceGraph graph) {
1327 this.graph = graph;
1328 }
1329 }
1330 /**
1331 * Pick the next node (leaf) to solve in the graph
1332 */
1333 Node pickNode(InferenceGraph g) throws NodeNotFoundException;
1334 /**
1335 * Is this the last step?
1336 */
1337 boolean done();
1338 }
1339
1340 /**
1341 * Simple solver strategy class that locates all leaves inside a graph
1342 * and picks the first leaf as the next node to solve
1343 */
1344 abstract class LeafSolver implements GraphStrategy {
1345 public Node pickNode(InferenceGraph g) {
1346 if (g.nodes.isEmpty()) {
1347 //should not happen
1348 throw new NodeNotFoundException(g);
1349 }
1350 return g.nodes.get(0);
1351 }
1352 }
1353
1354 /**
1355 * This solver uses an heuristic to pick the best leaf - the heuristic
1356 * tries to select the node that has maximal probability to contain one
1357 * or more inference variables in a given list
1358 */
1359 abstract class BestLeafSolver extends LeafSolver {
1360
1361 /** list of ivars of which at least one must be solved */
1362 List<Type> varsToSolve;
1363
1364 BestLeafSolver(List<Type> varsToSolve) {
1365 this.varsToSolve = varsToSolve;
1366 }
1367
1368 /**
1369 * Computes a path that goes from a given node to the leafs in the graph.
1370 * Typically this will start from a node containing a variable in
1371 * {@code varsToSolve}. For any given path, the cost is computed as the total
1372 * number of type-variables that should be eagerly instantiated across that path.
1373 */
1374 Pair<List<Node>, Integer> computeTreeToLeafs(Node n) {
1375 Pair<List<Node>, Integer> cachedPath = treeCache.get(n);
1376 if (cachedPath == null) {
1377 //cache miss
1378 if (n.isLeaf()) {
1379 //if leaf, stop
1380 cachedPath = new Pair<>(List.of(n), n.data.length());
1381 } else {
1382 //if non-leaf, proceed recursively
1383 Pair<List<Node>, Integer> path = new Pair<>(List.of(n), n.data.length());
1384 for (Node n2 : n.getAllDependencies()) {
1385 if (n2 == n) continue;
1386 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2);
1387 path = new Pair<>(path.fst.prependList(subpath.fst),
1388 path.snd + subpath.snd);
1389 }
1390 cachedPath = path;
1391 }
1392 //save results in cache
1393 treeCache.put(n, cachedPath);
1394 }
1395 return cachedPath;
1396 }
1397
1398 /** cache used to avoid redundant computation of tree costs */
1399 final Map<Node, Pair<List<Node>, Integer>> treeCache = new HashMap<>();
1400
1401 /** constant value used to mark non-existent paths */
1402 final Pair<List<Node>, Integer> noPath = new Pair<>(null, Integer.MAX_VALUE);
1403
1404 /**
1405 * Pick the leaf that minimize cost
1406 */
1407 @Override
1408 public Node pickNode(final InferenceGraph g) {
1409 treeCache.clear(); //graph changes at every step - cache must be cleared
1410 Pair<List<Node>, Integer> bestPath = noPath;
1411 for (Node n : g.nodes) {
1412 if (!Collections.disjoint(n.data, varsToSolve)) {
1413 Pair<List<Node>, Integer> path = computeTreeToLeafs(n);
1414 //discard all paths containing at least a node in the
1415 //closure computed above
1416 if (path.snd < bestPath.snd) {
1417 bestPath = path;
1418 }
1419 }
1420 }
1421 if (bestPath == noPath) {
1422 //no path leads there
1423 throw new NodeNotFoundException(g);
1424 }
1425 return bestPath.fst.head;
1426 }
1427 }
1428
1429 /**
1430 * The inference process can be thought of as a sequence of steps. Each step
1431 * instantiates an inference variable using a subset of the inference variable
1432 * bounds, if certain condition are met. Decisions such as the sequence in which
1433 * steps are applied, or which steps are to be applied are left to the inference engine.
1434 */
1435 enum InferenceStep {
1436
1437 /**
1438 * Instantiate an inference variables using one of its (ground) equality
1439 * constraints
1440 */
1441 EQ(InferenceBound.EQ) {
1442 @Override
1443 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1444 return filterBounds(uv, inferenceContext).head;
1445 }
1446 },
1447 /**
1448 * Instantiate an inference variables using its (ground) lower bounds. Such
1449 * bounds are merged together using lub().
1450 */
1451 LOWER(InferenceBound.LOWER) {
1452 @Override
1453 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1454 Infer infer = inferenceContext.infer;
1455 List<Type> lobounds = filterBounds(uv, inferenceContext);
1456 //note: lobounds should have at least one element
1457 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds);
1458 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
1459 throw infer.error(infer.diags.fragment(Fragments.NoUniqueMinimalInstanceExists(uv.qtype, lobounds)));
1460 } else {
1461 return owntype;
1462 }
1463 }
1464 },
1465 /**
1466 * Infer uninstantiated/unbound inference variables occurring in 'throws'
1467 * clause as RuntimeException
1468 */
1469 THROWS(InferenceBound.UPPER) {
1470 @Override
1471 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1472 if (!t.isThrows()) {
1473 //not a throws undet var
1474 return false;
1475 }
1476 Types types = inferenceContext.types;
1477 Symtab syms = inferenceContext.infer.syms;
1478 return t.getBounds(InferenceBound.UPPER).stream()
1479 .filter(b -> !inferenceContext.free(b))
1480 .allMatch(u -> types.isSubtype(syms.runtimeExceptionType, u));
1481 }
1482
1483 @Override
1484 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1485 return inferenceContext.infer.syms.runtimeExceptionType;
1486 }
1487 },
1488 /**
1489 * Instantiate an inference variables using its (ground) upper bounds. Such
1490 * bounds are merged together using glb().
1491 */
1492 UPPER(InferenceBound.UPPER) {
1493 @Override
1494 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1495 Infer infer = inferenceContext.infer;
1496 List<Type> hibounds = filterBounds(uv, inferenceContext);
1497 //note: hibounds should have at least one element
1498 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds);
1499 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
1500 throw infer.error(infer.diags.fragment(Fragments.NoUniqueMaximalInstanceExists(uv.qtype, hibounds)));
1501 } else {
1502 return owntype;
1503 }
1504 }
1505 },
1506 /**
1507 * Like the former; the only difference is that this step can only be applied
1508 * if all upper bounds are ground.
1509 */
1510 UPPER_LEGACY(InferenceBound.UPPER) {
1511 @Override
1512 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1513 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
1514 }
1515
1516 @Override
1517 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1518 return UPPER.solve(uv, inferenceContext);
1519 }
1520 },
1521 /**
1522 * Like the former; the only difference is that this step can only be applied
1523 * if all upper/lower bounds are ground.
1524 */
1525 CAPTURED(InferenceBound.UPPER) {
1526 @Override
1527 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1528 return t.isCaptured() &&
1529 !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
1530 }
1531
1532 @Override
1533 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1534 Infer infer = inferenceContext.infer;
1535 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
1536 UPPER.solve(uv, inferenceContext) :
1537 infer.syms.objectType;
1538 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
1539 LOWER.solve(uv, inferenceContext) :
1540 infer.syms.botType;
1541 CapturedType prevCaptured = (CapturedType)uv.qtype;
1542 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner,
1543 upper, lower, prevCaptured.wildcard);
1544 }
1545 };
1546
1547 final InferenceBound ib;
1548
1549 InferenceStep(InferenceBound ib) {
1550 this.ib = ib;
1551 }
1552
1553 /**
1554 * Find an instantiated type for a given inference variable within
1555 * a given inference context
1556 */
1557 abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
1558
1559 /**
1560 * Can the inference variable be instantiated using this step?
1561 */
1562 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1563 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
1564 }
1565
1566 /**
1567 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
1568 */
1569 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
1570 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
1571 }
1572 }
1573
1574 /**
1575 * This enumeration defines the sequence of steps to be applied when the
1576 * solver works in legacy mode. The steps in this enumeration reflect
1577 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1578 */
1579 enum LegacyInferenceSteps {
1580
1581 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1582 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
1583
1584 final EnumSet<InferenceStep> steps;
1585
1586 LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
1587 this.steps = steps;
1588 }
1589 }
1590
1591 /**
1592 * This enumeration defines the sequence of steps to be applied when the
1593 * graph solver is used. This order is defined so as to maximize compatibility
1594 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1595 */
1596 enum GraphInferenceSteps {
1597
1598 EQ(EnumSet.of(InferenceStep.EQ)),
1599 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1600 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
1601
1602 final EnumSet<InferenceStep> steps;
1603
1604 GraphInferenceSteps(EnumSet<InferenceStep> steps) {
1605 this.steps = steps;
1606 }
1607 }
1608
1609 /**
1610 * There are two kinds of dependencies between inference variables. The basic
1611 * kind of dependency (or bound dependency) arises when a variable mention
1612 * another variable in one of its bounds. There's also a more subtle kind
1613 * of dependency that arises when a variable 'might' lead to better constraints
1614 * on another variable (this is typically the case with variables holding up
1615 * stuck expressions).
1616 */
1617 enum DependencyKind implements GraphUtils.DependencyKind {
1618
1619 /** bound dependency */
1620 BOUND("dotted"),
1621 /** stuck dependency */
1622 STUCK("dashed");
1623
1624 final String dotSyle;
1625
1626 private DependencyKind(String dotSyle) {
1627 this.dotSyle = dotSyle;
1628 }
1629 }
1630
1631 /**
1632 * This is the graph inference solver - the solver organizes all inference variables in
1633 * a given inference context by bound dependencies - in the general case, such dependencies
1634 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
1635 * an acyclic graph, where all cyclic variables are bundled together. An inference
1636 * step corresponds to solving a node in the acyclic graph - this is done by
1637 * relying on a given strategy (see GraphStrategy).
1638 */
1639 class GraphSolver {
1640
1641 InferenceContext inferenceContext;
1642 Warner warn;
1643
1644 GraphSolver(InferenceContext inferenceContext, Warner warn) {
1645 this.inferenceContext = inferenceContext;
1646 this.warn = warn;
1647 }
1648
1649 /**
1650 * Solve variables in a given inference context. The amount of variables
1651 * to be solved, and the way in which the underlying acyclic graph is explored
1652 * depends on the selected solver strategy.
1653 */
1654 void solve(GraphStrategy sstrategy) {
1655 doIncorporation(inferenceContext, warn); //initial propagation of bounds
1656 InferenceGraph inferenceGraph = new InferenceGraph();
1657 while (!sstrategy.done()) {
1658 if (dependenciesFolder != null) {
1659 //add this graph to the pending queue
1660 pendingGraphs = pendingGraphs.prepend(inferenceGraph.toDot());
1661 }
1662 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
1663 List<Type> varsToSolve = List.from(nodeToSolve.data);
1664 List<Type> saved_undet = inferenceContext.save();
1665 try {
1666 //repeat until all variables are solved
1667 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
1668 //for each inference phase
1669 for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
1670 if (inferenceContext.solveBasic(varsToSolve, step.steps).nonEmpty()) {
1671 doIncorporation(inferenceContext, warn);
1672 continue outer;
1673 }
1674 }
1675 //no progress
1676 throw error(null);
1677 }
1678 }
1679 catch (InferenceException ex) {
1680 //did we fail because of interdependent ivars?
1681 inferenceContext.rollback(saved_undet);
1682 instantiateAsUninferredVars(varsToSolve, inferenceContext);
1683 doIncorporation(inferenceContext, warn);
1684 }
1685 inferenceGraph.deleteNode(nodeToSolve);
1686 }
1687 }
1688
1689 /**
1690 * The dependencies between the inference variables that need to be solved
1691 * form a (possibly cyclic) graph. This class reduces the original dependency graph
1692 * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
1693 */
1694 class InferenceGraph {
1695
1696 /**
1697 * This class represents a node in the graph. Each node corresponds
1698 * to an inference variable and has edges (dependencies) on other
1699 * nodes. The node defines an entry point that can be used to receive
1700 * updates on the structure of the graph this node belongs to (used to
1701 * keep dependencies in sync).
1702 */
1703 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements DottableNode<ListBuffer<Type>, Node> {
1704
1705 /** node dependencies */
1706 Set<Node> deps;
1707
1708 Node(Type ivar) {
1709 super(ListBuffer.of(ivar));
1710 this.deps = new LinkedHashSet<>();
1711 }
1712
1713 @Override
1714 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
1715 return new GraphUtils.DependencyKind[] { DependencyKind.BOUND };
1716 }
1717
1718 public Iterable<? extends Node> getAllDependencies() {
1719 return deps;
1720 }
1721
1722 @Override
1723 public Collection<? extends Node> getDependenciesByKind(GraphUtils.DependencyKind dk) {
1724 if (dk == DependencyKind.BOUND) {
1725 return deps;
1726 } else {
1727 throw new IllegalStateException();
1728 }
1729 }
1730
1731 /**
1732 * Adds dependency with given kind.
1733 */
1734 protected void addDependency(Node depToAdd) {
1735 deps.add(depToAdd);
1736 }
1737
1738 /**
1739 * Add multiple dependencies of same given kind.
1740 */
1741 protected void addDependencies(Set<Node> depsToAdd) {
1742 for (Node n : depsToAdd) {
1743 addDependency(n);
1744 }
1745 }
1746
1747 /**
1748 * Remove a dependency, regardless of its kind.
1749 */
1750 protected boolean removeDependency(Node n) {
1751 return deps.remove(n);
1752 }
1753
1754 /**
1755 * Compute closure of a give node, by recursively walking
1756 * through all its dependencies.
1757 */
1758 protected Set<Node> closure() {
1759 Set<Node> closure = new HashSet<>();
1760 closureInternal(closure);
1761 return closure;
1762 }
1763
1764 private void closureInternal(Set<Node> closure) {
1765 if (closure.add(this)) {
1766 for (Node n : deps) {
1767 n.closureInternal(closure);
1768 }
1769 }
1770 }
1771
1772 /**
1773 * Is this node a leaf? This means either the node has no dependencies,
1774 * or it just has self-dependencies.
1775 */
1776 protected boolean isLeaf() {
1777 //no deps, or only one self dep
1778 if (deps.isEmpty()) return true;
1779 for (Node n : deps) {
1780 if (n != this) {
1781 return false;
1782 }
1783 }
1784 return true;
1785 }
1786
1787 /**
1788 * Merge this node with another node, acquiring its dependencies.
1789 * This routine is used to merge all cyclic node together and
1790 * form an acyclic graph.
1791 */
1792 protected void mergeWith(List<? extends Node> nodes) {
1793 for (Node n : nodes) {
1794 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
1795 data.appendList(n.data);
1796 addDependencies(n.deps);
1797 }
1798 //update deps
1799 Set<Node> deps2 = new LinkedHashSet<>();
1800 for (Node d : deps) {
1801 if (data.contains(d.data.first())) {
1802 deps2.add(this);
1803 } else {
1804 deps2.add(d);
1805 }
1806 }
1807 deps = deps2;
1808 }
1809
1810 /**
1811 * Notify all nodes that something has changed in the graph
1812 * topology.
1813 */
1814 private void graphChanged(Node from, Node to) {
1815 if (removeDependency(from)) {
1816 if (to != null) {
1817 addDependency(to);
1818 }
1819 }
1820 }
1821
1822 @Override
1823 public Properties nodeAttributes() {
1824 Properties p = new Properties();
1825 p.put("label", "\"" + toString() + "\"");
1826 return p;
1827 }
1828
1829 @Override
1830 public Properties dependencyAttributes(Node sink, GraphUtils.DependencyKind dk) {
1831 Properties p = new Properties();
1832 p.put("style", ((DependencyKind)dk).dotSyle);
1833 StringBuilder buf = new StringBuilder();
1834 String sep = "";
1835 for (Type from : data) {
1836 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from);
1837 for (Type bound : uv.getBounds(InferenceBound.values())) {
1838 if (bound.containsAny(List.from(sink.data))) {
1839 buf.append(sep);
1840 buf.append(bound);
1841 sep = ",";
1842 }
1843 }
1844 }
1845 p.put("label", "\"" + buf.toString() + "\"");
1846 return p;
1847 }
1848 }
1849
1850 /** the nodes in the inference graph */
1851 ArrayList<Node> nodes;
1852
1853 InferenceGraph() {
1854 initNodes();
1855 }
1856
1857 /**
1858 * Basic lookup helper for retrieving a graph node given an inference
1859 * variable type.
1860 */
1861 public Node findNode(Type t) {
1862 for (Node n : nodes) {
1863 if (n.data.contains(t)) {
1864 return n;
1865 }
1866 }
1867 return null;
1868 }
1869
1870 /**
1871 * Delete a node from the graph. This update the underlying structure
1872 * of the graph (including dependencies) via listeners updates.
1873 */
1874 public void deleteNode(Node n) {
1875 Assert.check(nodes.contains(n));
1876 nodes.remove(n);
1877 notifyUpdate(n, null);
1878 }
1879
1880 /**
1881 * Notify all nodes of a change in the graph. If the target node is
1882 * {@code null} the source node is assumed to be removed.
1883 */
1884 void notifyUpdate(Node from, Node to) {
1885 for (Node n : nodes) {
1886 n.graphChanged(from, to);
1887 }
1888 }
1889
1890 /**
1891 * Create the graph nodes. First a simple node is created for every inference
1892 * variables to be solved. Then Tarjan is used to found all connected components
1893 * in the graph. For each component containing more than one node, a super node is
1894 * created, effectively replacing the original cyclic nodes.
1895 */
1896 void initNodes() {
1897 //add nodes
1898 nodes = new ArrayList<>();
1899 for (Type t : inferenceContext.restvars()) {
1900 nodes.add(new Node(t));
1901 }
1902 //add dependencies
1903 for (Node n_i : nodes) {
1904 Type i = n_i.data.first();
1905 for (Node n_j : nodes) {
1906 Type j = n_j.data.first();
1907 // don't compare a variable to itself
1908 if (i != j) {
1909 UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i);
1910 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
1911 //update i's bound dependencies
1912 n_i.addDependency(n_j);
1913 }
1914 }
1915 }
1916 }
1917 //merge cyclic nodes
1918 ArrayList<Node> acyclicNodes = new ArrayList<>();
1919 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
1920 if (conSubGraph.length() > 1) {
1921 Node root = conSubGraph.head;
1922 root.mergeWith(conSubGraph.tail);
1923 for (Node n : conSubGraph) {
1924 notifyUpdate(n, root);
1925 }
1926 }
1927 acyclicNodes.add(conSubGraph.head);
1928 }
1929 nodes = acyclicNodes;
1930 }
1931
1932 /**
1933 * Debugging: dot representation of this graph
1934 */
1935 String toDot() {
1936 StringBuilder buf = new StringBuilder();
1937 for (Type t : inferenceContext.undetvars) {
1938 UndetVar uv = (UndetVar)t;
1939 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
1940 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
1941 uv.getBounds(InferenceBound.EQ)));
1942 }
1943 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
1944 }
1945 }
1946 }
1947 // </editor-fold>
1948
1949 // <editor-fold defaultstate="collapsed" desc="Inference context">
1950 /**
1951 * Functional interface for defining inference callbacks. Certain actions
1952 * (i.e. subtyping checks) might need to be redone after all inference variables
1953 * have been fixed.
1954 */
1955 interface FreeTypeListener {
1956 void typesInferred(InferenceContext inferenceContext);
1957 }
1958
1959 final InferenceContext emptyContext;
1960 // </editor-fold>
1961 }