From dbb4b3f7923427af4ba6e04f258309421d5ee1ab Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 1 Aug 2013 18:21:23 +0200 Subject: Handling typevars in inference. Fleshed out handling of typevars for type inference. Also added some more methods to typer, for blocks, ifs and assignments. (Closures are still wip). --- src/dotty/tools/dotc/ast/CheckTrees.scala | 43 ++--- src/dotty/tools/dotc/ast/TreeInfo.scala | 5 + src/dotty/tools/dotc/ast/Trees.scala | 6 +- src/dotty/tools/dotc/ast/TypedTrees.scala | 24 +-- src/dotty/tools/dotc/ast/UntypedTrees.scala | 2 +- src/dotty/tools/dotc/core/Denotations.scala | 2 +- src/dotty/tools/dotc/core/SymDenotations.scala | 6 - src/dotty/tools/dotc/core/TyperState.scala | 42 ++++- src/dotty/tools/dotc/core/Types.scala | 138 +++++++++++++--- src/dotty/tools/dotc/core/pickling/UnPickler.scala | 2 +- src/dotty/tools/dotc/printing/PlainPrinter.scala | 2 + src/dotty/tools/dotc/typer/ErrorReporting.scala | 2 +- src/dotty/tools/dotc/typer/Inferencing.scala | 77 +++++---- src/dotty/tools/dotc/typer/Typer.scala | 177 +++++++++++++++------ src/dotty/tools/dotc/util/SimpleMap.scala | 8 + 15 files changed, 388 insertions(+), 148 deletions(-) diff --git a/src/dotty/tools/dotc/ast/CheckTrees.scala b/src/dotty/tools/dotc/ast/CheckTrees.scala index a004789e6..b1806df4b 100644 --- a/src/dotty/tools/dotc/ast/CheckTrees.scala +++ b/src/dotty/tools/dotc/ast/CheckTrees.scala @@ -17,6 +17,27 @@ object CheckTrees { check(bounds contains arg.tpe) } + def escapingRefs(block: Block)(implicit ctx: Context): Set[NamedType] = { + var hoisted: Set[Symbol] = Set() + lazy val locals = localSyms(block.stats).toSet + def isNonLocal(sym: Symbol): Boolean = + !(locals contains sym) || isHoistableClass(sym) + def isHoistableClass(sym: Symbol) = + sym.isClass && { + (hoisted contains sym) || { + hoisted += sym + !classLeaks(sym.asClass) + } + } + def leakingTypes(tp: Type): Set[NamedType] = + tp namedPartsWith (tp => isNonLocal(tp.symbol)) + def typeLeaks(tp: Type) = leakingTypes(tp).isEmpty + def classLeaks(sym: ClassSymbol): Boolean = + (sym.info.parents exists typeLeaks) || + (sym.decls.toList exists (t => typeLeaks(t.info))) + leakingTypes(block.tpe) + } + def checkType(tree: Tree)(implicit ctx: Context): Unit = tree match { case Ident(name) => case Select(qualifier, name) => @@ -79,27 +100,9 @@ object CheckTrees { check(false) } check(rhs.tpe <:< lhs.tpe.widen) - case Block(stats, expr) => - var hoisted: Set[Symbol] = Set() - lazy val locals = localSyms(stats).toSet + case tree @ Block(stats, expr) => check(expr.isValue) - def isNonLocal(sym: Symbol): Boolean = - !(locals contains sym) || isHoistableClass(sym) - def isHoistableClass(sym: Symbol) = - sym.isClass && { - (hoisted contains sym) || { - hoisted += sym - noLeaksInClass(sym.asClass) - } - } - def noLeaksIn(tp: Type): Boolean = tp forallParts { - case tp: NamedType => isNonLocal(tp.symbol) - case _ => true - } - def noLeaksInClass(sym: ClassSymbol): Boolean = - (sym.info.parents forall noLeaksIn) && - (sym.decls.toList forall (t => noLeaksIn(t.info))) - check(noLeaksIn(tree.tpe)) + check(escapingRefs(tree).isEmpty) case If(cond, thenp, elsep) => check(cond.isValue); check(thenp.isValue); check(elsep.isValue) check(cond.tpe.derivesFrom(defn.BooleanClass)) diff --git a/src/dotty/tools/dotc/ast/TreeInfo.scala b/src/dotty/tools/dotc/ast/TreeInfo.scala index de00cee7e..9fcbeeea4 100644 --- a/src/dotty/tools/dotc/ast/TreeInfo.scala +++ b/src/dotty/tools/dotc/ast/TreeInfo.scala @@ -99,6 +99,11 @@ trait TreeInfo[T >: Untyped] { self: Trees.Instance[T] => case _ => false } + def isSuperSelection(tree: untpd.Tree) = tree match { + case Select(Super(_, _), _) => true + case _ => false + } + def isSelfOrSuperConstrCall(tree: Tree): Boolean = methPart(tree) match { case Ident(nme.CONSTRUCTOR) | Select(This(_), nme.CONSTRUCTOR) diff --git a/src/dotty/tools/dotc/ast/Trees.scala b/src/dotty/tools/dotc/ast/Trees.scala index 74f792220..cfc603501 100644 --- a/src/dotty/tools/dotc/ast/Trees.scala +++ b/src/dotty/tools/dotc/ast/Trees.scala @@ -436,7 +436,7 @@ object Trees { } /** A closure with an environment and a reference to a method */ - case class Closure[-T >: Untyped] private[ast] (env: List[Tree[T]], meth: RefTree[T]) + case class Closure[-T >: Untyped] private[ast] (env: List[Tree[T]], meth: Tree[T]) extends TermTree[T] { type ThisTree[-T >: Untyped] = Closure[T] } @@ -847,7 +847,7 @@ object Trees { case tree: If if (cond eq tree.cond) && (thenp eq tree.thenp) && (elsep eq tree.elsep) => tree case _ => finalize(tree, untpd.If(cond, thenp, elsep)) } - def Closure(tree: Tree, env: List[Tree], meth: RefTree): Closure = tree match { + def Closure(tree: Tree, env: List[Tree], meth: Tree): Closure = tree match { case tree: Closure if (env eq tree.env) && (meth eq tree.meth) => tree case _ => finalize(tree, untpd.Closure(env, meth)) } @@ -986,7 +986,7 @@ object Trees { case If(cond, thenp, elsep) => cpy.If(tree, transform(cond), transform(thenp), transform(elsep)) case Closure(env, meth) => - cpy.Closure(tree, transform(env), transformSub(meth)) + cpy.Closure(tree, transform(env), transform(meth)) case Match(selector, cases) => cpy.Match(tree, transform(selector), transformSub(cases)) case CaseDef(pat, guard, body) => diff --git a/src/dotty/tools/dotc/ast/TypedTrees.scala b/src/dotty/tools/dotc/ast/TypedTrees.scala index cea799116..037180161 100644 --- a/src/dotty/tools/dotc/ast/TypedTrees.scala +++ b/src/dotty/tools/dotc/ast/TypedTrees.scala @@ -85,15 +85,17 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo { def Assign(lhs: Tree, rhs: Tree)(implicit ctx: Context): Assign = untpd.Assign(lhs, rhs).withType(defn.UnitType).checked - def Block(stats: List[Tree], expr: Tree)(implicit ctx: Context): Block = { + def Block(stats: List[Tree], expr: Tree)(implicit ctx: Context): Block = + untpd.Block(stats, expr).withType(blockType(stats, expr.tpe)).checked + + def blockType(stats: List[Tree], exprType: Type)(implicit ctx: Context): Type = { lazy val locals = localSyms(stats).toSet - val blk = untpd.Block(stats, expr) def widen(tp: Type): Type = tp match { case tp: TermRef if locals contains tp.symbol => widen(tp.info) case _ => tp } - blk.withType(widen(expr.tpe)) + widen(exprType) } def maybeBlock(stats: List[Tree], expr: Tree)(implicit ctx: Context): Tree = @@ -102,14 +104,14 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo { def If(cond: Tree, thenp: Tree, elsep: Tree)(implicit ctx: Context): If = untpd.If(cond, thenp, elsep).withType(thenp.tpe | elsep.tpe).checked - def Closure(env: List[Tree], meth: RefTree)(implicit ctx: Context): Closure = { - val ownType = meth.tpe.widen match { - case mt @ MethodType(_, formals) => - assert(!mt.isDependent) - val formals1 = formals mapConserve (_.underlyingIfRepeated) - defn.FunctionType(formals1, mt.resultType) - } - untpd.Closure(env, meth).withType(ownType).checked + def Closure(env: List[Tree], meth: RefTree)(implicit ctx: Context): Closure = + untpd.Closure(env, meth).withType(closureType(meth.tpe.widen)).checked + + def closureType(tp: Type)(implicit ctx: Context) = tp match { + case mt @ MethodType(_, formals) => + assert(!mt.isDependent) + val formals1 = formals mapConserve (_.underlyingIfRepeated) + defn.FunctionType(formals1, mt.resultType) } /** A function def diff --git a/src/dotty/tools/dotc/ast/UntypedTrees.scala b/src/dotty/tools/dotc/ast/UntypedTrees.scala index 22e8ab56e..79bef00e8 100644 --- a/src/dotty/tools/dotc/ast/UntypedTrees.scala +++ b/src/dotty/tools/dotc/ast/UntypedTrees.scala @@ -63,7 +63,7 @@ object untpd extends Trees.Instance[Untyped] with TreeInfo[Untyped] { def Assign(lhs: Tree, rhs: Tree): Assign = new Assign(lhs, rhs) def Block(stats: List[Tree], expr: Tree): Block = new Block(stats, expr) def If(cond: Tree, thenp: Tree, elsep: Tree): If = new If(cond, thenp, elsep) - def Closure(env: List[Tree], meth: RefTree): Closure = new Closure(env, meth) + def Closure(env: List[Tree], meth: Tree): Closure = new Closure(env, meth) def Match(selector: Tree, cases: List[CaseDef]): Match = new Match(selector, cases) def CaseDef(pat: Tree, guard: Tree, body: Tree): CaseDef = new CaseDef(pat, guard, body) def Return(expr: Tree, from: Tree): Return = new Return(expr, from) diff --git a/src/dotty/tools/dotc/core/Denotations.scala b/src/dotty/tools/dotc/core/Denotations.scala index 16c75e38b..8b5dcc5dc 100644 --- a/src/dotty/tools/dotc/core/Denotations.scala +++ b/src/dotty/tools/dotc/core/Denotations.scala @@ -659,7 +659,7 @@ object Denotations { def recur(path: Name, len: Int): Denotation = { val point = path.lastIndexOf('.', len - 1) val owner = - if (point > 0) recur(path.toTermName, point).disambiguate(_.isParameterless) + if (point > 0) recur(path.toTermName, point).disambiguate(_.info.isParameterless) else if (path.isTermName) defn.RootClass.denot else defn.EmptyPackageClass.denot if (!owner.exists) owner diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala index 258604df4..d2be45444 100644 --- a/src/dotty/tools/dotc/core/SymDenotations.scala +++ b/src/dotty/tools/dotc/core/SymDenotations.scala @@ -287,12 +287,6 @@ object SymDenotations { /** Is this a user defined "def" method? Excluded are accessors and stable values */ final def isSourceMethod = this is (Method, butNot = Accessor) - /** Is this either not a method at all, or a parameterless method? */ - final def isParameterless(implicit ctx: Context) = info match { - case _: MethodType | _: PolyType => false - case _ => true - } - /** Is this a setter? */ final def isGetter = (this is Accessor) && !originalName.isSetterName diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index e492eee60..b00e55e29 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -14,10 +14,17 @@ class TyperState(val reporter: Reporter = ThrowingReporter) extends DotClass { def constraint: Constraint = new Constraint(SimpleMap.Empty) /** The currently uninstantiated TypeVars */ - def undetVars: List[TypeVar] = Nil + def undetVars: Set[TypeVar] = Set() + + /** A map that records for instantiated type vars their instance type. + * Used only in a temporary way for contexts that may be retracted + * without also retracting the type var. + */ + def instType: SimpleMap[TypeVar, Type] = SimpleMap.Empty def constraint_=(c: Constraint): Unit = {} - def undetVars_=(vs: List[TypeVar]): Unit = unsupported("undetVars_=") + def undetVars_=(vs: Set[TypeVar]): Unit = unsupported("undetVars_=") + def instType_=(m: SimpleMap[TypeVar, Type]): Unit = unsupported("instType_=") def fresh: TyperState = this @@ -28,19 +35,42 @@ class MutableTyperState(previous: TyperState, reporter: Reporter) extends TyperState(reporter) { private var myConstraint: Constraint = previous.constraint - private var myUndetVars: List[TypeVar] = previous.undetVars + private var myUndetVars: Set[TypeVar] = previous.undetVars + private var myInstType: SimpleMap[TypeVar, Type] = previous.instType override def constraint = myConstraint override def undetVars = myUndetVars + override def instType = myInstType override def constraint_=(c: Constraint) = myConstraint = c - override def undetVars_=(vs: List[TypeVar]) = myUndetVars = vs + override def undetVars_=(vs: Set[TypeVar]) = myUndetVars = vs + override def instType_=(m: SimpleMap[TypeVar, Type]): Unit = myInstType = m override def fresh: TyperState = new MutableTyperState(this, new StoreReporter) + /** Commit typer state so that its information is copied into current typer state + * In addition (1) the owning state of undetermined or temporarily instantiated + * type variables changes from this typer state to the current one. (2) Variables + * that were temporarily instantiated in the current typer state are permanently + * instantiated instead. + */ override def commit()(implicit ctx: Context) = { - ctx.typerState.constraint = constraint - ctx.typerState.undetVars = undetVars + var targetState = ctx.typerState + targetState.constraint = constraint + targetState.undetVars = undetVars + targetState.instType = instType + + def adjustOwningState(tvar: TypeVar) = + if (tvar.owningState eq this) tvar.owningState = targetState + undetVars foreach adjustOwningState + instType foreachKey { case tvar: TypeVar => + adjustOwningState(tvar) + if (tvar.owningState == targetState) { + tvar.inst = instType(tvar) + targetState.instType = targetState.instType remove tvar + } + } + reporter.flush() } } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index c3e15d94c..8df651180 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -150,7 +150,8 @@ object Types { } /** Does this type occur as a part of type `that`? */ - final def occursIn(that: Type): Boolean = that.existsPart(this == _) + final def occursIn(that: Type)(implicit ctx: Context): Boolean = + that.existsPart(this == _) def isRepeatedParam(implicit ctx: Context): Boolean = defn.RepeatedParamAliases contains typeSymbol @@ -159,16 +160,21 @@ object Types { /** Returns true if there is a part of this type that satisfies predicate `p`. */ - final def existsPart(p: Type => Boolean): Boolean = - new ExistsAccumulator(p)(false, this) + final def existsPart(p: Type => Boolean)(implicit ctx: Context): Boolean = + new ExistsAccumulator(p).apply(false, this) /** Returns true if all parts of this type satisfy predicate `p`. */ - final def forallParts(p: Type => Boolean): Boolean = !existsPart(!p(_)) + final def forallParts(p: Type => Boolean)(implicit ctx: Context): Boolean = !existsPart(!p(_)) /** The parts of this type which are type or term refs */ final def namedParts(implicit ctx: Context): Set[NamedType] = - new PartsAccumulator().apply(Set(), this) + namedPartsWith(Function.const(true)) + + final def namedPartsWith(p: NamedType => Boolean)(implicit ctx: Context): Set[NamedType] = + new NamedPartsAccumulator(p).apply(Set(), this) + + final def foreach(f: Type => Unit): Unit = ??? /** Map function over elements of an AndType, rebuilding with & */ def mapAnd(f: Type => Type)(implicit ctx: Context): Type = thisInstance match { @@ -498,7 +504,7 @@ object Types { /** Map a TypeVar to either its instance if it is instantiated, or its origin, * if not. Identity on all other types. */ - def thisInstance: Type = this + def thisInstance(implicit ctx: Context): Type = this /** Widen from singleton type to its underlying non-singleton * base type by applying one or more `underlying` dereferences, @@ -535,7 +541,7 @@ object Types { /** If this is a refinement type, the unrefined parent, * else the type itself. */ - final def unrefine: Type = thisInstance match { + final def unrefine(implicit ctx: Context): Type = thisInstance match { case tp @ RefinedType(tycon, _) => tycon.unrefine case tp => tp } @@ -594,6 +600,15 @@ object Types { case pt: PolyType => pt.resultType.paramTypess case _ => Nil } + + /** Is this either not a method at all, or a parameterless method? */ + final def isParameterless: Boolean = this match { + case mt: MethodType => false + case pt: PolyType => pt.resultType.isParameterless + case _ => true + } + + /* Not sure whether we'll need this final def firstParamTypes: List[Type] = this match { case mt: MethodType => mt.paramTypes @@ -908,6 +923,12 @@ object Types { def toText(printer: Printer): Text = printer.toText(this) + /** `tp` is either a type variable or poly param. Returns + * Covariant if all occurrences of `tp` in this type are covariant + * Contravariant if all occurrences of `tp` in this type are contravariant + * Covariant | Contravariant if there are no occurrences of `tp` in this type + * EmptyFlags if `tp` occurs noon-variantly in this type + */ def varianceOf(tp: Type): FlagSet = ??? // ----- hashing ------------------------------------------------------ @@ -1403,9 +1424,18 @@ object Types { def isJava = false def isImplicit = false - lazy val isDependent = resultType existsPart { - case MethodParam(mt, _) => mt eq this - case _ => false + private[this] var myIsDependent: Boolean = _ + private[this] var isDepKnown = false + + def isDependent(implicit ctx: Context) = { + if (!isDepKnown) { + myIsDependent = resultType existsPart { + case MethodParam(mt, _) => mt eq this + case _ => false + } + isDepKnown = true + } + myIsDependent } private[this] var _signature: Signature = _ @@ -1623,14 +1653,76 @@ object Types { override def toString = s"RefinedThis(${binder.hashCode})" } - final case class TypeVar(origin: PolyParam) extends UncachedProxyType with ValueType { - private var inst: Type = NoType - def isInstantiated = inst ne NoType - def instantiateWith(tp: Type) = inst = tp - override def thisInstance = if (isInstantiated) inst else origin + /** A type variable is essentially a switch that models some part of a substitution. + * It is first linked to `origin`, a poly param that's in the current constraint set. + * It can then be (once) instantiated to some other type. The instantiation is + * recorded in the type variable itself, or else, if the current type state + * is different from the variable's creation state (meaning unrolls are possible) + * in the current typer state. Every type variable is referred to by exactly + * one inferred type parameter in a TypeApply tree. + * + * @param origin The parameter that's tracked by the type variable. + * @param creatorState The typer state in which the variable was created. + * @param pos The position of the TypeApply tree that introduces + * the type variable. + */ + final class TypeVar(val origin: PolyParam, creatorState: TyperState, val pos: Position) extends UncachedProxyType with ValueType { + + /** The permanent instance type of the the variable, or NoType is none is given yet */ + private[core] var inst: Type = NoType + + /** The state owning the variable. This is at first creationState, but it can + * be changed to an enclosing state on a commit + */ + private[core] var owningState = creatorState + + assert(!(creatorState.undetVars contains this)) + creatorState.undetVars += this + + /** The instance type of this variable, or NoType if the variable is currently + * uninstantiated + */ + def instanceOpt(implicit ctx: Context): Type = + if (inst.exists) inst + else { + val i = ctx.typerState.instType(this) + if (i == null) NoType else i + } + + /** Is the variable already instantiated? */ + def isInstantiated(implicit ctx: Context) = instanceOpt.exists + + /** Instantiate variable with given type */ + def instantiateWith(tp: Type)(implicit ctx: Context): Type = { + assert(owningState.undetVars contains this) + owningState.undetVars -= this + if (ctx.typerState eq creatorState) inst = tp + else ctx.typerState.instType = ctx.typerState.instType.updated(this, tp) + tp + } + + /** Instantiate variable from the constraints over its `origin`. + * If `fromBelow` is true, the variable is instantiated to the lub + * of its lower bounds in the current constraint; otherwie it is + * instantiated to the glb of its upper bounds. + */ + def instantiate(fromBelow: Boolean)(implicit ctx: Context): Type = + instantiateWith(ctx.typeComparer.approximate(origin, fromBelow)) + + /** If the variable is instantiated, its instance, otherwise its origin */ + override def thisInstance(implicit ctx: Context) = { + val inst = instanceOpt + if (inst.exists) inst else origin + } + + /** Same as `thisInstance` */ override def underlying(implicit ctx: Context): Type = thisInstance + + override def hashCode: Int = System.identityHashCode(this) override def equals(that: Any) = this eq that.asInstanceOf[AnyRef] - override def toString = thisInstance.toString + + override def toString = + if (inst.exists) inst.toString else s"TypeVar($origin)" } // ------ ClassInfo, Type Bounds ------------------------------------------------------------ @@ -1871,12 +1963,12 @@ object Types { case _ => false } - def unapply(tp: Type)(implicit ctx: Context): Option[(SingleDenotation, List[Type], Type)] = + def unapply(tp: Type)(implicit ctx: Context): Option[SingleDenotation] = if (isInstantiatable(tp)) { val absMems = tp.abstractTermMembers if (absMems.size == 1) absMems.head.info match { - case mt: MethodType if !mt.isDependent => Some((absMems.head, mt.paramTypes, mt.resultType)) + case mt: MethodType if !mt.isDependent => Some(absMems.head) case _=> None } else None @@ -1927,7 +2019,7 @@ object Types { case tp @ AnnotatedType(annot, underlying) => tp.derivedAnnotatedType(mapOver(annot), this(underlying)) - case tp @ TypeVar(_) => + case tp: TypeVar => apply(tp.thisInstance) case tp @ WildcardType => @@ -1980,7 +2072,7 @@ object Types { // ----- TypeAccumulators ---------------------------------------------------- - abstract class TypeAccumulator[T] extends ((T, Type) => T) { + abstract class TypeAccumulator[T](implicit ctx: Context) extends ((T, Type) => T) { def apply(x: T, tp: Type): T protected def apply(x: T, annot: Annotation): T = x // don't go into annotations @@ -2024,13 +2116,13 @@ object Types { } } - class ExistsAccumulator(p: Type => Boolean) extends TypeAccumulator[Boolean] { + class ExistsAccumulator(p: Type => Boolean)(implicit ctx: Context) extends TypeAccumulator[Boolean] { def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp) } - class PartsAccumulator(implicit ctx: Context) extends TypeAccumulator[Set[NamedType]] { + class NamedPartsAccumulator(p: NamedType => Boolean)(implicit ctx: Context) extends TypeAccumulator[Set[NamedType]] { def apply(x: Set[NamedType], tp: Type): Set[NamedType] = tp match { - case tp: NamedType => + case tp: NamedType if (p(tp)) => foldOver(x + tp, tp) case tp: ThisType => apply(x, tp.underlying) diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala index a488e0e18..4c96c5e4b 100644 --- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala +++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala @@ -596,7 +596,7 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: else ThisType(cls) case SINGLEtpe => val pre = readTypeRef() - val sym = readDisambiguatedSymbolRef(_.isParameterless) + val sym = readDisambiguatedSymbolRef(_.info.isParameterless) if (isLocal(sym) || (pre == NoPrefix)) TermRef.withSym(pre, sym.asTerm) else TermRef.withSig(pre, sym.name.asTermName, NotAMethod) case SUPERtpe => diff --git a/src/dotty/tools/dotc/printing/PlainPrinter.scala b/src/dotty/tools/dotc/printing/PlainPrinter.scala index b903a5ce1..04afa5709 100644 --- a/src/dotty/tools/dotc/printing/PlainPrinter.scala +++ b/src/dotty/tools/dotc/printing/PlainPrinter.scala @@ -137,6 +137,8 @@ class PlainPrinter(_ctx: Context) extends Printer { toText(polyParamName(pt.paramNames(n))) case AnnotatedType(annot, tpe) => toTextLocal(tpe) ~ " " ~ toText(annot) + case tp: TypeVar => + toTextLocal(tp.underlying) case _ => tp.fallbackToText(this) } diff --git a/src/dotty/tools/dotc/typer/ErrorReporting.scala b/src/dotty/tools/dotc/typer/ErrorReporting.scala index e0ff8e351..7a91adde6 100644 --- a/src/dotty/tools/dotc/typer/ErrorReporting.scala +++ b/src/dotty/tools/dotc/typer/ErrorReporting.scala @@ -13,7 +13,7 @@ object ErrorReporting { import tpd._ - def errorTree(tree: Tree, msg: => String)(implicit ctx: Context): tpd.Tree = + def errorTree(tree: untpd.Tree, msg: => String)(implicit ctx: Context): tpd.Tree = tree withType errorType(msg, tree.pos) def errorType(msg: => String, pos: Position)(implicit ctx: Context): ErrorType = { diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 1ae33d87a..5c9c86c0c 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -14,11 +14,39 @@ object Inferencing { import tpd._ + /** Is type fully defined, meaning the type does not contain wildcard types + * or uninstantiated type variables. As a side effect, this will minimize + * any uninstantiated type variables, provided that + * - the instance type for the variable is not Nothing or Null + * - the overall result of `isFullYDefined` is `true`. + * Variables that are succesfully minimized do not count as uninstantiated. + */ + def isFullyDefined(tp: Type)(implicit ctx: Context): Boolean = { + val nestedCtx = ctx.fresh.withNewTyperState + val result = new IsFullyDefinedAccumulator()(nestedCtx).traverse(tp) + if (result) nestedCtx.typerState.commit() + result + } + + private class IsFullyDefinedAccumulator(implicit ctx: Context) extends TypeAccumulator[Boolean] { + def traverse(tp: Type): Boolean = apply(true, tp) + def apply(x: Boolean, tp: Type) = !x || isOK(tp) && foldOver(x, tp) + def isOK(tp: Type): Boolean = tp match { + case _: WildcardType => + false + case tvar: TypeVar if !tvar.isInstantiated => + val inst = tvar.instantiate(fromBelow = true) + inst != defn.NothingType && inst != defn.NullType + case _ => + true + } + } + def checkBounds(args: List[Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit = { } - def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Unit = { + def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Type = { if (!tp.isStable) ctx.error(s"Prefix ${tp.show} is not stable", pos) tp @@ -57,38 +85,27 @@ object Inferencing { tracked } - /** Interpolate undetermined variables. - * If a variable appears covariantly in type `tp`, approximate it by - * its lower bound. Otherwise, if it appears contravariantly in type `tp`, - * approximate it by its upper bound. Otherwise, if `always` is true, - * approximate it also by its lower bound. - * Instantiated variables are removed from `undetVars`. + /** Interpolate those undetermined type variables whose position + * is included in the position `pos` of the current tree. + * If such a variable appears covariantly in type `tp` or does not appear at all, + * approximate it by its lower bound. Otherwise, if it appears contravariantly + * in type `tp` approximate it by its upper bound. */ - def interpolateUndetVars(upTo: List[TypeVar], tp: Type, always: Boolean = false): Unit = { - def recur(undets: List[TypeVar]): List[TypeVar] = - if (undets eq upTo) undets - else (undets: @unchecked) match { - case tvar :: rest => - def instantiate(fromBelow: Boolean) = { - tvar.instantiateWith(ctx.typeComparer.approximate(tvar.origin, fromBelow)) - recur(rest) - } - val v = tp varianceOf tvar - if (v is Covariant) instantiate(fromBelow = true) - else if (v is Contravariant) instantiate(fromBelow = false) - else if (always) instantiate(fromBelow = true) - else tvar :: recur(rest) + def interpolateUndetVars(tp: Type, pos: Position): Unit = + for (tvar <- ctx.typerState.undetVars) + if (pos contains tvar.pos) { + val v = tp varianceOf tvar + if (v is Covariant) tvar.instantiate(fromBelow = true) + else if (v is Contravariant) tvar.instantiate(fromBelow = false) } - state.undetVars = recur(state.undetVars) - } - def newTypeVars(pt: PolyType): List[TypeVar] = { - val tvars = - for (n <- (0 until pt.paramNames.length).toList) - yield TypeVar(PolyParam(pt, n)) - state.undetVars = tvars ++ state.undetVars - tvars - } + /** Create new type variables for the parameters of a poly type. + * @param pos The position of the new type variables (relevant for + * interpolateUndetVars + */ + def newTypeVars(pt: PolyType, pos: Position): List[TypeVar] = + for (n <- (0 until pt.paramNames.length).toList) + yield new TypeVar(PolyParam(pt, n), ctx.typerState, pos) def isSubTypes(actuals: List[Type], formals: List[Type])(implicit ctx: Context): Boolean = formals match { case formal :: formals1 => diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index 733eac739..ffd4b2ce1 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -346,21 +346,106 @@ class Typer extends Namer with Applications with Implicits { cpy.Pair(tree, left1, right1).withType(defn.PairType.appliedTo(left1.tpe :: right1.tpe :: Nil)) } - def TypedTyped(tree: untpd.Typed)(implicit ctx: Context) = { + def typedTyped(tree: untpd.Typed)(implicit ctx: Context) = { val tpt1 = typedType(tree.tpt) val expr1 = typedExpr(tree.expr, tpt1.tpe) cpy.Typed(tree, tpt1, expr1).withType(tpt1.tpe) } - def NamedArg(tree: untpd.NamedArg, pt: Type)(implicit ctx: Context) = { + def typedNamedArg(tree: untpd.NamedArg, pt: Type)(implicit ctx: Context) = { val arg1 = typed(tree.arg, pt) cpy.NamedArg(tree, tree.name, arg1).withType(arg1.tpe) } - def Assign(tree: untpd.Assign)(implicit ctx: Context) = { + def typedAssign(tree: untpd.Assign)(implicit ctx: Context) = tree.lhs match { + case lhs @ Apply(fn, args) => + typed(cpy.Apply(lhs, untpd.Select(fn, nme.update), args :+ tree.rhs)) + case lhs => + val lhs1 = typed(lhs) + def reassignmentToVal = + errorTree(cpy.Assign(tree, lhs1, typed(tree.rhs, lhs1.tpe.widen)), + "reassignment to val") + lhs1.tpe match { + case ref: TermRef if ref.symbol is Mutable => + cpy.Assign(tree, lhs1, typed(tree.rhs, ref.info)).withType(defn.UnitType) + case ref: TermRef if ref.info.isParameterless => + val pre = ref.prefix + val setterName = ref.name.getterToSetter + val setter = pre.member(setterName) + lhs1 match { + case lhs1: RefTree if setter.exists => + val setterTypeRaw = TermRef(pre, setterName).withDenot(setter) + val setterType = checkAccessible(setterTypeRaw, isSuperSelection(tree), tree.pos) + val lhs2 = lhs1.withName(setterName).withType(setterType) + typed(cpy.Apply(tree, untpd.TypedSplice(lhs2), tree.rhs :: Nil)) + case _ => + reassignmentToVal + } + case _ => + reassignmentToVal + } + } + + def typedBlock(tree: Block, pt: Type)(implicit ctx: Context) = { + val exprCtx = enterSyms(tree.stats) + val stats1 = typedStats(tree.stats, ctx.owner) + val expr1 = typedExpr(tree.expr, pt)(exprCtx) + val result = cpy.Block(tree, stats1, expr1).withType(blockType(stats1, expr1.tpe)) + val leaks = CheckTrees.escapingRefs(result) + if (leaks.isEmpty) result + else if (isFullyDefined(pt)) { + val expr2 = typed(untpd.Typed(untpd.TypedSplice(expr1), untpd.TypeTree(pt))) + untpd.Block(stats1, expr2) withType expr2.tpe + } else errorTree(result, + s"local definition of ${leaks.head.name} escapes as part of block's type ${result.tpe.show}") + } + + def typedIf(tree: untpd.If, pt: Type)(implicit ctx: Context) = { + val cond1 = typed(tree.cond, defn.BooleanType) + val thenp1 = typed(tree.thenp, pt) + val elsep1 = typed(tree.elsep, pt) + cpy.If(tree, cond1, thenp1, elsep1).withType(thenp1.tpe | elsep1.tpe) + } + + def typedFunction(tree: untpd.Function, pt: Type)(implicit ctx: Context) = { + val params = tree.args.asInstanceOf[List[ValDef]] + val protoFormals: List[Type] = pt match { + case _ if pt.typeSymbol == defn.FunctionClass(params.length) => + pt.typeArgs take params.length + case MethodType(_, paramTypes) => + paramTypes + case _ => + params map Function.const(WildcardType) + } + val inferredParams = + for ((param, formal) <- (params, protoFormals).zipped) + if (param.tpt.isEmpty && isFullyDefined(formal)) + cpy.ValDef(param, param.mods, param.name, untpd.TypeTree(formal), param.rhs) + else + param + ??? } + def typedClosure(tree: untpd.Closure, pt: Type)(implicit ctx: Context) = { + val env1 = tree.env map (typed(_)) + val meth1 = typed(tree.meth) + pt match { + case SAMType(meth) if !defn.isFunctionType(pt) => + ??? + case _ => + val ownType = meth1.tpe.widen match { + case mt: MethodType if !mt.isDependent => + closureType(mt) + case mt: MethodType => + errorType(s"cannot turn dependent method types into closures", tree.pos) + case tp => + errorType(s"internal error: closing over non-method $tp", tree.pos) + } + cpy.Closure(tree, env1, meth1).withType(ownType) + } + } + def typedModifiers(mods: untpd.Modifiers)(implicit ctx: Context): Modifiers = { val annotations1 = mods.annotations mapconserve typedAnnotation if (annotations1 eq mods.annotations) mods.asInstanceOf[Modifiers] @@ -464,8 +549,10 @@ class Typer extends Namer with Applications with Implicits { case none => tree } case _ => tree - } - typedExpanded(xtree, pt) + } + val tree1 = typedExpanded(xtree, pt) + ctx.interpolateUndetVars(tree1.tpe.widen, tree1.pos) + adapt(tree1, pt) } def typedTrees(trees: List[untpd.Tree])(implicit ctx: Context): List[Tree] = @@ -482,7 +569,8 @@ class Typer extends Namer with Applications with Implicits { buf += typed(mdef) traverse(rest) case stat :: rest => - buf += typed(stat)(ctx.fresh.withOwner(exprOwner)) + val nestedCtx = if (exprOwner == ctx.owner) ctx else ctx.fresh.withOwner(exprOwner) + buf += typed(stat)(nestedCtx) traverse(rest) case _ => buf.toList @@ -515,45 +603,44 @@ class Typer extends Namer with Applications with Implicits { fallBack } - /** - * (-1) For expressions with annotated types, let AnnotationCheckers decide what to do - * (0) Convert expressions with constant types to literals (unless in interactive/scaladoc mode) - */ + /** (-1) For expressions with annotated types, let AnnotationCheckers decide what to do + * (0) Convert expressions with constant types to literals (unless in interactive/scaladoc mode) + */ - /** Perform the following adaptations of expression, pattern or type `tree` wrt to - * given prototype `pt`: - * (1) Resolve overloading - * (2) Apply parameterless functions - * (3) Apply polymorphic types to fresh instances of their type parameters and - * store these instances in context.undetparams, - * unless followed by explicit type application. - * (4) Do the following to unapplied methods used as values: - * (4.1) If the method has only implicit parameters pass implicit arguments - * (4.2) otherwise, if `pt` is a function type and method is not a constructor, - * convert to function by eta-expansion, - * (4.3) otherwise, if the method is nullary with a result type compatible to `pt` - * and it is not a constructor, apply it to () - * otherwise issue an error - * (5) Convert constructors in a pattern as follows: - * (5.1) If constructor refers to a case class factory, set tree's type to the unique - * instance of its primary constructor that is a subtype of the expected type. - * (5.2) If constructor refers to an extractor, convert to application of - * unapply or unapplySeq method. - * - * (6) Convert all other types to TypeTree nodes. - * (7) When in TYPEmode but not FUNmode or HKmode, check that types are fully parameterized - * (7.1) In HKmode, higher-kinded types are allowed, but they must have the expected kind-arity - * (8) When in both EXPRmode and FUNmode, add apply method calls to values of object type. - * (9) If there are undetermined type variables and not POLYmode, infer expression instance - * Then, if tree's type is not a subtype of expected type, try the following adaptations: - * (10) If the expected type is Byte, Short or Char, and the expression - * is an integer fitting in the range of that type, convert it to that type. - * (11) Widen numeric literals to their expected type, if necessary - * (12) When in mode EXPRmode, convert E to { E; () } if expected type is scala.Unit. - * (13) When in mode EXPRmode, apply AnnotationChecker conversion if expected type is annotated. - * (14) When in mode EXPRmode, apply a view - * If all this fails, error - */ + /** Perform the following adaptations of expression, pattern or type `tree` wrt to + * given prototype `pt`: + * (1) Resolve overloading + * (2) Apply parameterless functions + * (3) Apply polymorphic types to fresh instances of their type parameters and + * store these instances in context.undetparams, + * unless followed by explicit type application. + * (4) Do the following to unapplied methods used as values: + * (4.1) If the method has only implicit parameters pass implicit arguments + * (4.2) otherwise, if `pt` is a function type and method is not a constructor, + * convert to function by eta-expansion, + * (4.3) otherwise, if the method is nullary with a result type compatible to `pt` + * and it is not a constructor, apply it to () + * otherwise issue an error + * (5) Convert constructors in a pattern as follows: + * (5.1) If constructor refers to a case class factory, set tree's type to the unique + * instance of its primary constructor that is a subtype of the expected type. + * (5.2) If constructor refers to an extractor, convert to application of + * unapply or unapplySeq method. + * + * (6) Convert all other types to TypeTree nodes. + * (7) When in TYPEmode but not FUNmode or HKmode, check that types are fully parameterized + * (7.1) In HKmode, higher-kinded types are allowed, but they must have the expected kind-arity + * (8) When in both EXPRmode and FUNmode, add apply method calls to values of object type. + * (9) If there are undetermined type variables and not POLYmode, infer expression instance + * Then, if tree's type is not a subtype of expected type, try the following adaptations: + * (10) If the expected type is Byte, Short or Char, and the expression + * is an integer fitting in the range of that type, convert it to that type. + * (11) Widen numeric literals to their expected type, if necessary + * (12) When in mode EXPRmode, convert E to { E; () } if expected type is scala.Unit. + * (13) When in mode EXPRmode, apply AnnotationChecker conversion if expected type is annotated. + * (14) When in mode EXPRmode, apply a view + * If all this fails, error + */ def adapt(tree: Tree, pt: Type)(implicit ctx: Context): Tree = { def adaptOverloaded(ref: TermRef) = { @@ -630,7 +717,7 @@ class Typer extends Namer with Applications with Implicits { if (pt.isInstanceOf[PolyProtoType]) tree else { val tracked = ctx.track(poly) - val tvars = ctx.newTypeVars(tracked) + val tvars = ctx.newTypeVars(tracked, tree.pos) adapt(tpd.TypeApply(tree, tvars map (tpd.TypeTree(_))), pt) } case tp => diff --git a/src/dotty/tools/dotc/util/SimpleMap.scala b/src/dotty/tools/dotc/util/SimpleMap.scala index 218af2fc5..3acc5c4b8 100644 --- a/src/dotty/tools/dotc/util/SimpleMap.scala +++ b/src/dotty/tools/dotc/util/SimpleMap.scala @@ -6,6 +6,7 @@ abstract class SimpleMap[-K, +V >: Null] { def updated[V1 >: V](k: K, v: V1): SimpleMap[K, V1] def contains(k: K): Boolean = apply(k) != null def mapValues[V1 >: V](f: V1 => V1): SimpleMap[K, V1] + def foreachKey(f: Any => Unit): Unit } object SimpleMap { @@ -15,6 +16,7 @@ object SimpleMap { def remove(k: Any) = this def updated[V1 >: Null](k: Any, v: V1) = new Map1(k, v) def mapValues[V1 >: Null](f: V1 => V1) = this + def foreachKey(f: Any => Unit) = () } class Map1[-K, +V >: Null] (k1: K, v1: V) extends SimpleMap[K, V] { @@ -29,6 +31,7 @@ object SimpleMap { else new Map2(k1, v1, k, v) def mapValues[V1 >: V](f: V1 => V1) = new Map1(k1, f(v1)) + def foreachKey(f: Any => Unit) = f(k1) } class Map2[-K, +V >: Null] (k1: K, v1: V, k2: K, v2: V) extends SimpleMap[K, V] { @@ -46,6 +49,7 @@ object SimpleMap { else new Map3(k1, v1, k2, v2, k, v) def mapValues[V1 >: V](f: V1 => V1) = new Map2(k1, f(v1), k2, f(v2)) + def foreachKey(f: Any => Unit) = { f(k1); f(k2) } } class Map3[-K, +V >: Null] (k1: K, v1: V, k2: K, v2: V, k3: K, v3: V) extends SimpleMap[K, V] { @@ -66,6 +70,7 @@ object SimpleMap { else new Map4(k1, v1, k2, v2, k3, v3, k, v) def mapValues[V1 >: V](f: V1 => V1) = new Map3(k1, f(v1), k2, f(v2), k3, f(v3)) + def foreachKey(f: Any => Unit) = { f(k1); f(k2); f(k3) } } class Map4[-K, +V >: Null] (k1: K, v1: V, k2: K, v2: V, k3: K, v3: V, k4: K, v4: V) extends SimpleMap[K, V] { @@ -89,6 +94,7 @@ object SimpleMap { else new Map5(k1, v1, k2, v2, k3, v3, k4, v4, k, v) def mapValues[V1 >: V](f: V1 => V1) = new Map4(k1, f(v1), k2, f(v2), k3, f(v3), k4, f(v4)) + def foreachKey(f: Any => Unit) = { f(k1); f(k2); f(k3); f(k4) } } class Map5[-K, +V >: Null] (k1: K, v1: V, k2: K, v2: V, k3: K, v3: V, k4: K, v4: V, k5: K, v5: V) extends SimpleMap[K, V] { @@ -115,6 +121,7 @@ object SimpleMap { else new MapMore(Map(k1 -> v1, k2 -> v2, k3 -> v3, k4 -> v4, k5 -> v5, k -> v)) def mapValues[V1 >: V](f: V1 => V1) = new Map5(k1, f(v1), k2, f(v2), k3, f(v3), k4, f(v4), k5, f(v5)) + def foreachKey(f: Any => Unit) = { f(k1); f(k2); f(k3); f(k4); f(k5) } } class MapMore[-K, +V >: Null] (m: Map[K, V]) extends SimpleMap[K, V] { @@ -135,5 +142,6 @@ object SimpleMap { override def contains(k: K) = m contains k def mapValues[V1 >: V](f: V1 => V1) = new MapMore(m mapValues f) + def foreachKey(f: Any => Unit) = { m.keysIterator foreach f } } } -- cgit v1.2.3