From 5103f1720a26ac16c2b6b8bde1fe5717b3e5b78f Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 11 Dec 2015 19:59:04 +0100 Subject: Make asSeenFrom idempotent Let asSeenFrom generate a marker annotated type for any unsafe instantiation. Then cleanup in typedSelect. --- .../annotation/internal/UnsafeNonvariant.scala | 8 ++++ src/dotty/tools/dotc/core/Contexts.scala | 8 +++- src/dotty/tools/dotc/core/Definitions.scala | 2 + src/dotty/tools/dotc/core/TypeOps.scala | 51 ++++++++++------------ src/dotty/tools/dotc/core/Types.scala | 20 +++++++++ src/dotty/tools/dotc/typer/Typer.scala | 34 ++++++++++++--- 6 files changed, 88 insertions(+), 35 deletions(-) create mode 100644 src/dotty/annotation/internal/UnsafeNonvariant.scala (limited to 'src') diff --git a/src/dotty/annotation/internal/UnsafeNonvariant.scala b/src/dotty/annotation/internal/UnsafeNonvariant.scala new file mode 100644 index 000000000..43a0a114b --- /dev/null +++ b/src/dotty/annotation/internal/UnsafeNonvariant.scala @@ -0,0 +1,8 @@ +package dotty.annotation.internal + +import scala.annotation.Annotation + +/** This annotation is used as a marker for unsafe + * instantiations in asSeenFrom. See TypeOps.asSeenfrom for an explanation. + */ +class UnsafeNonvariant extends Annotation diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala index 1a471537e..ae221cc3e 100644 --- a/src/dotty/tools/dotc/core/Contexts.scala +++ b/src/dotty/tools/dotc/core/Contexts.scala @@ -600,10 +600,16 @@ object Contexts { * of underlying during a controlled operation exists. */ private[core] val pendingUnderlying = new mutable.HashSet[Type] + /** A flag that some unsafe nonvariant instantiation was encountered + * in this run. Used as a shortcut to a avoid scans of types in + * Typer.typedSelect. + */ + private[dotty] var unsafeNonvariant: RunId = NoRunId + + // Phases state private[core] var phasesPlan: List[List[Phase]] = _ - // Phases state /** Phases by id */ private[core] var phases: Array[Phase] = _ diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index 5f794f2d5..609cce189 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -475,6 +475,8 @@ class Definitions { def UncheckedStableAnnot(implicit ctx: Context) = UncheckedStableAnnotType.symbol.asClass lazy val UncheckedVarianceAnnotType = ctx.requiredClassRef("scala.annotation.unchecked.uncheckedVariance") def UncheckedVarianceAnnot(implicit ctx: Context) = UncheckedVarianceAnnotType.symbol.asClass + lazy val UnsafeNonvariantAnnotType = ctx.requiredClassRef("dotty.annotation.internal.UnsafeNonvariant") + def UnsafeNonvariantAnnot(implicit ctx: Context) = UnsafeNonvariantAnnotType.symbol.asClass lazy val VolatileAnnotType = ctx.requiredClassRef("scala.volatile") def VolatileAnnot(implicit ctx: Context) = VolatileAnnotType.symbol.asClass lazy val FieldMetaAnnotType = ctx.requiredClassRef("scala.annotation.meta.field") diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index 3dfe698f0..9232bd185 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -8,6 +8,7 @@ import config.Printers._ import util.Positions._ import Decorators._ import StdNames._ +import Annotations._ import util.SimpleMap import collection.mutable import ast.tpd._ @@ -23,31 +24,29 @@ trait TypeOps { this: Context => // TODO: Make standalone object. * * and an expression `e` of type `C`. Then computing the type of `e.f` leads * to the query asSeenFrom(`C`, `(x: T)T`). What should its result be? The - * naive answer `(x: C.T)C.T` is incorrect given that we treat `C.T` as the existential + * naive answer `(x: C#T)C#T` is incorrect given that we treat `C#T` as the existential * `exists(c: C)c.T`. What we need to do instead is to skolemize the existential. So * the answer would be `(x: c.T)c.T` for some (unknown) value `c` of type `C`. * `c.T` is expressed in the compiler as a skolem type `Skolem(C)`. * * Now, skolemization is messy and expensive, so we want to do it only if we absolutely - * must. We must skolemize if an unstable prefix is used in nonvariant or - * contravariant position of the return type of asSeenFrom. + * must. Also, skolemizing immediately would mean that asSeenFrom was no longer + * idempotent - each call would return a type with a different skolem. + * Instead we produce an annotated type that marks the prefix as unsafe: * - * In the implementation of asSeenFrom, we first try to run asSeenFrom without - * skolemizing. If that would be incorrect we will be told by the fact that - * `unstable` is set in the passed AsSeenFromMap. In that case we run asSeenFrom - * again with a skolemized prefix. + * (x: (C @ UnsafeNonvariant)#T)C#T + + * We also set a global state flag `unsafeNonvariant` to the current run. + * When typing a Select node, typer will check that flag, and if it + * points to the current run will scan the result type of the select for + * @UnsafeNonvariant annotations. If it finds any, it will introduce a skolem + * constant for the prefix and try again. * - * In the interest of speed we want to avoid creating an AsSeenFromMap every time - * asSeenFrom is called. So we do this here only if the prefix is unstable - * (because then we need the map as a container for the unstable field). For - * stable prefixes the map is `null`; it might however be instantiated later - * for more complicated types. + * The scheme is efficient in particular because we expect that unsafe situations are rare; + * most compiles would contain none, so no scanning would be necessary. */ - final def asSeenFrom(tp: Type, pre: Type, cls: Symbol): Type = { - val m = if (isLegalPrefix(pre)) null else new AsSeenFromMap(pre, cls) - var res = asSeenFrom(tp, pre, cls, m) - if (m != null && m.unstable) asSeenFrom(tp, SkolemType(pre), cls) else res - } + final def asSeenFrom(tp: Type, pre: Type, cls: Symbol): Type = + asSeenFrom(tp, pre, cls, null) /** Helper method, taking a map argument which is instantiated only for more * complicated cases of asSeenFrom. @@ -65,9 +64,11 @@ trait TypeOps { this: Context => // TODO: Make standalone object. case pre: SuperType => toPrefix(pre.thistpe, cls, thiscls) case _ => if (thiscls.derivesFrom(cls) && pre.baseTypeRef(thiscls).exists) { - if (theMap != null && theMap.currentVariance <= 0 && !isLegalPrefix(pre)) - theMap.unstable = true - pre + if (theMap != null && theMap.currentVariance <= 0 && !isLegalPrefix(pre)) { + ctx.base.unsafeNonvariant = ctx.runId + AnnotatedType(pre, Annotation(defn.UnsafeNonvariantAnnot, Nil)) + } + else pre } else if ((pre.termSymbol is Package) && !(thiscls is Package)) toPrefix(pre.select(nme.PACKAGE), cls, thiscls) @@ -82,17 +83,14 @@ trait TypeOps { this: Context => // TODO: Make standalone object. val sym = tp.symbol if (sym.isStatic) tp else { - val prevStable = theMap == null || !theMap.unstable val pre1 = asSeenFrom(tp.prefix, pre, cls, theMap) - if (theMap != null && theMap.unstable && prevStable) { + if (pre1.isUnsafeNonvariant) pre1.member(tp.name).info match { case TypeAlias(alias) => // try to follow aliases of this will avoid skolemization. - theMap.unstable = false return alias case _ => } - } tp.derivedSelect(pre1) } case tp: ThisType => @@ -122,11 +120,6 @@ trait TypeOps { this: Context => // TODO: Make standalone object. /** A method to export the current variance of the map */ def currentVariance = variance - - /** A field which indicates whether an unstable argument in nonvariant - * or contravariant position was encountered. - */ - var unstable = false } /** Approximate a type `tp` with a type that does not contain skolem types. diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 624549bac..e0e9a535f 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -190,6 +190,16 @@ object Types { def isRepeatedParam(implicit ctx: Context): Boolean = typeSymbol eq defn.RepeatedParamClass + /** Does this type carry an UnsafeNonvariant annotation? */ + final def isUnsafeNonvariant(implicit ctx: Context): Boolean = this match { + case AnnotatedType(_, annot) => annot.symbol == defn.UnsafeNonvariantAnnot + case _ => false + } + + /** Does this type have an UnsafeNonvariant annotation on one of its parts? */ + final def hasUnsafeNonvariant(implicit ctx: Context): Boolean = + new HasUnsafeNonAccumulator().apply(false, this) + /** Is this the type of a method that has a repeated parameter type as * last parameter type? */ @@ -755,6 +765,12 @@ object Types { case _ => this } + /** If this is a skolem, its underlying type, otherwise the type itself */ + final def widenSkolem(implicit ctx: Context): Type = this match { + case tp: SkolemType => tp.underlying + case _ => this + } + /** Follow aliases and dereferences LazyRefs and instantiated TypeVars until type * is no longer alias type, LazyRef, or instantiated type variable. */ @@ -3239,6 +3255,10 @@ object Types { def apply(x: Unit, tp: Type): Unit = foldOver(p(tp), tp) } + class HasUnsafeNonAccumulator(implicit ctx: Context) extends TypeAccumulator[Boolean] { + def apply(x: Boolean, tp: Type) = x || tp.isUnsafeNonvariant || foldOver(x, tp) + } + class NamedPartsAccumulator(p: NamedType => Boolean)(implicit ctx: Context) extends TypeAccumulator[mutable.Set[NamedType]] { override def stopAtStatic = false def maybeAdd(x: mutable.Set[NamedType], tp: NamedType) = if (p(tp)) x += tp else x diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index e5509d50f..1747d1442 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -282,12 +282,35 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit checkValue(tree1, pt) } + private def typedSelect(tree: untpd.Select, pt: Type, qual: Tree)(implicit ctx: Context): Select = + healNonvariant( + checkValue(assignType(cpy.Select(tree)(qual, tree.name), qual), pt), + pt) + + /** Let `tree = p.n` where `p: T`. If tree's type is an unsafe instantiation + * (see TypeOps#asSeenFrom for how this can happen), rewrite the prefix `p` + * to `(p: )` and try again with the new (stable) + * prefix. If the result has another unsafe instantiation, raise an error. + */ + private def healNonvariant[T <: Tree](tree: T, pt: Type)(implicit ctx: Context): T = + if (ctx.unsafeNonvariant == ctx.runId && tree.tpe.widen.hasUnsafeNonvariant) + tree match { + case tree @ Select(qual, _) if !qual.tpe.isStable => + val alt = typedSelect(tree, pt, Typed(qual, TypeTree(SkolemType(qual.tpe.widen)))) + /*typr.*/println(d"healed type: ${tree.tpe} --> $alt") + alt.asInstanceOf[T] + case _ => + ctx.error(d"unsafe instantiation of type ${tree.tpe}", tree.pos) + tree + } + else tree + def typedSelect(tree: untpd.Select, pt: Type)(implicit ctx: Context): Tree = track("typedSelect") { def asSelect(implicit ctx: Context): Tree = { val qual1 = typedExpr(tree.qualifier, selectionProto(tree.name, pt, this)) if (tree.name.isTypeName) checkStable(qual1.tpe, qual1.pos) - checkValue(assignType(cpy.Select(tree)(qual1, tree.name), qual1), pt) - } + typedSelect(tree, pt, qual1) + } def asJavaSelectFromTypeTree(implicit ctx: Context): Tree = { // Translate names in Select/Ident nodes to type names. @@ -382,7 +405,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit checkSimpleKinded(typedType(tree.tpt)) val expr1 = if (isWildcard) tree.expr withType tpt1.tpe - else typed(tree.expr, tpt1.tpe) + else typed(tree.expr, tpt1.tpe.widenSkolem) assignType(cpy.Typed(tree)(expr1, tpt1), tpt1) } tree.expr match { @@ -438,9 +461,10 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit val setter = pre.member(setterName) lhsCore match { case lhsCore: RefTree if setter.exists => - val setterTypeRaw = pre select (setterName, setter) + val setterTypeRaw = pre.select(setterName, setter) val setterType = ensureAccessible(setterTypeRaw, isSuperSelection(lhsCore), tree.pos) - val lhs2 = untpd.rename(lhsCore, setterName).withType(setterType) + val lhs2 = healNonvariant( + untpd.rename(lhsCore, setterName).withType(setterType), WildcardType) typedUnadapted(cpy.Apply(tree)(untpd.TypedSplice(lhs2), tree.rhs :: Nil)) case _ => reassignmentToVal -- cgit v1.2.3