diff options
author | odersky <odersky@gmail.com> | 2015-10-07 15:07:28 +0200 |
---|---|---|
committer | odersky <odersky@gmail.com> | 2015-10-07 15:07:28 +0200 |
commit | 8532c98672e6dcde4d350f253b46892cc0ece34c (patch) | |
tree | b834f8e32776b62c0224607e1664f65f39893108 /src/dotty/tools/dotc/typer | |
parent | a8c8bdad57941071b85caa54bc57b84d8ca7d526 (diff) | |
parent | 22a2c79adf3acb8b5dd341b552e499bced58c537 (diff) | |
download | dotty-8532c98672e6dcde4d350f253b46892cc0ece34c.tar.gz dotty-8532c98672e6dcde4d350f253b46892cc0ece34c.tar.bz2 dotty-8532c98672e6dcde4d350f253b46892cc0ece34c.zip |
Merge pull request #799 from dotty-staging/change-inference
Change inference
Diffstat (limited to 'src/dotty/tools/dotc/typer')
-rw-r--r-- | src/dotty/tools/dotc/typer/Inferencing.scala | 109 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/Typer.scala | 2 |
2 files changed, 97 insertions, 14 deletions
diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 8df544dd6..0a76f45c5 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -17,6 +17,7 @@ import Decorators._ import Uniques._ import ErrorReporting.{errorType, DiagnosticString} import config.Printers._ +import annotation.tailrec import collection.mutable trait Inferencing { this: Checking => @@ -43,9 +44,26 @@ trait Inferencing { this: Checking => if (isFullyDefined(tp, ForceDegree.all)) tp else throw new Error(i"internal error: type of $what $tp is not fully defined, pos = $pos") // !!! DEBUG + + /** Instantiate selected type variables `tvars` in type `tp` */ + def instantiateSelected(tp: Type, tvars: List[Type])(implicit ctx: Context): Unit = + new IsFullyDefinedAccumulator(new ForceDegree.Value(tvars.contains)).process(tp) + /** The accumulator which forces type variables using the policy encoded in `force` - * and returns whether the type is fully defined. Two phases: - * 1st Phase: Try to instantiate covariant and non-variant type variables to + * and returns whether the type is fully defined. The direction in which + * a type variable is instantiated is determined as follows: + * 1. T is minimized if the constraint over T is only from below (i.e. + * constrained lower bound != given lower bound and + * constrained upper bound == given upper bound). + * 2. T is maximized if the constraint over T is only from above (i.e. + * constrained upper bound != given upper bound and + * constrained lower bound == given lower bound). + * If (1) and (2) do not apply: + * 3. T is maximized if it appears only contravariantly in the given type. + * 4. T is minimized in all other cases. + * + * The instantiation is done in two phases: + * 1st Phase: Try to instantiate minimizable type variables to * their lower bound. Record whether successful. * 2nd Phase: If first phase was successful, instantiate all remaining type variables * to their upper bound. @@ -61,14 +79,20 @@ trait Inferencing { this: Checking => case _: WildcardType | _: ProtoType => false case tvar: TypeVar if !tvar.isInstantiated => - if (force == ForceDegree.none) false - else { - val minimize = - variance >= 0 && !( - force == ForceDegree.noBottom && - isBottomType(ctx.typeComparer.approximation(tvar.origin, fromBelow = true))) - if (minimize) instantiate(tvar, fromBelow = true) - else toMaximize = true + force.appliesTo(tvar) && { + val direction = instDirection(tvar.origin) + if (direction != 0) { + if (direction > 0) println(s"inst $tvar dir = up") + instantiate(tvar, direction < 0) + } + else { + val minimize = + variance >= 0 && !( + force == ForceDegree.noBottom && + isBottomType(ctx.typeComparer.approximation(tvar.origin, fromBelow = true))) + if (minimize) instantiate(tvar, fromBelow = true) + else toMaximize = true + } foldOver(x, tvar) } case tp => @@ -93,6 +117,62 @@ trait Inferencing { this: Checking => } } + /** The list of uninstantiated type variables bound by some prefix of type `T` which + * occur in at least one formal parameter type of a prefix application. + * Considered prefixes are: + * - The function `f` of an application node `f(e1, .., en)` + * - The function `f` of a type application node `f[T1, ..., Tn]` + * - The prefix `p` of a selection `p.f`. + * - The result expression `e` of a block `{s1; .. sn; e}`. + */ + def tvarsInParams(tree: Tree)(implicit ctx: Context): List[TypeVar] = { + @tailrec def boundVars(tree: Tree, acc: List[TypeVar]): List[TypeVar] = tree match { + case Apply(fn, _) => boundVars(fn, acc) + case TypeApply(fn, targs) => + val tvars = targs.tpes.collect { + case tvar: TypeVar if !tvar.isInstantiated => tvar + } + boundVars(fn, acc ::: tvars) + case Select(pre, _) => boundVars(pre, acc) + case Block(_, expr) => boundVars(expr, acc) + case _ => acc + } + @tailrec def occurring(tree: Tree, toTest: List[TypeVar], acc: List[TypeVar]): List[TypeVar] = + if (toTest.isEmpty) acc + else tree match { + case Apply(fn, _) => + fn.tpe match { + case mtp: MethodType => + val (occ, nocc) = toTest.partition(tvar => mtp.paramTypes.exists(tvar.occursIn)) + occurring(fn, nocc, occ ::: acc) + case _ => + occurring(fn, toTest, acc) + } + case TypeApply(fn, targs) => occurring(fn, toTest, acc) + case Select(pre, _) => occurring(pre, toTest, acc) + case Block(_, expr) => occurring(expr, toTest, acc) + case _ => acc + } + occurring(tree, boundVars(tree, Nil), Nil) + } + + /** The instantiation direction for given poly param computed + * from the constraint: + * @return 1 (maximize) if constraint is uniformly from above, + * -1 (minimize) if constraint is uniformly from below, + * 0 if unconstrained, or constraint is from below and above. + */ + private def instDirection(param: PolyParam)(implicit ctx: Context): Int = { + val constrained = ctx.typerState.constraint.fullBounds(param) + val original = param.binder.paramBounds(param.paramNum) + val cmp = ctx.typeComparer + val approxBelow = + if (!cmp.isSubTypeWhenFrozen(constrained.lo, original.lo)) 1 else 0 + val approxAbove = + if (!cmp.isSubTypeWhenFrozen(original.hi, constrained.hi)) 1 else 0 + approxAbove - approxBelow + } + def isBottomType(tp: Type)(implicit ctx: Context) = tp == defn.NothingType || tp == defn.NullType @@ -257,9 +337,10 @@ trait Inferencing { this: Checking => } /** An enumeration controlling the degree of forcing in "is-dully-defined" checks. */ -@sharable object ForceDegree extends Enumeration { - val none, // don't force type variables - noBottom, // force type variables, fail if forced to Nothing or Null - all = Value // force type variables, don't fail +@sharable object ForceDegree { + class Value(val appliesTo: TypeVar => Boolean) + val none = new Value(_ => false) + val all = new Value(_ => true) + val noBottom = new Value(_ => true) } diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index b28ac9bc5..3bb7a6505 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -1352,6 +1352,8 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit case wtp: ExprType => adaptInterpolated(tree.withType(wtp.resultType), pt, original) case wtp: ImplicitMethodType if constrainResult(wtp, followAlias(pt)) => + val tvarsToInstantiate = tvarsInParams(tree) + wtp.paramTypes.foreach(instantiateSelected(_, tvarsToInstantiate)) val constr = ctx.typerState.constraint def addImplicitArgs = { def implicitArgError(msg: => String): Tree = { |