From 910a701fcc93e0663f0a6a15ac11499beb1ca6a9 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Mon, 12 Mar 2012 17:58:34 +0100 Subject: SI-5189: refined GADT soundness fix extrapolate GADT skolems: only complicate types when needed make sure we only deskolemize GADT skolems after typedCase --- src/compiler/scala/reflect/internal/Flags.scala | 2 +- src/compiler/scala/reflect/internal/Symbols.scala | 22 +++++++--- src/compiler/scala/reflect/internal/Types.scala | 7 ++-- .../scala/tools/nsc/typechecker/Infer.scala | 2 +- .../tools/nsc/typechecker/TypeDiagnostics.scala | 2 +- .../scala/tools/nsc/typechecker/Typers.scala | 47 +++++++++++++--------- test/files/neg/t3015.check | 2 +- test/files/neg/t3481.check | 6 +-- test/files/neg/t4515.check | 2 +- test/files/neg/t5189b.check | 11 +++-- test/files/neg/t5189b.scala | 18 +++++++++ 11 files changed, 83 insertions(+), 38 deletions(-) diff --git a/src/compiler/scala/reflect/internal/Flags.scala b/src/compiler/scala/reflect/internal/Flags.scala index 8aae80eed4..3110d73461 100644 --- a/src/compiler/scala/reflect/internal/Flags.scala +++ b/src/compiler/scala/reflect/internal/Flags.scala @@ -107,7 +107,7 @@ class ModifierFlags { // pre: PRIVATE or PROTECTED are also set final val JAVA = 0x00100000 // symbol was defined by a Java class final val STATIC = 0x00800000 // static field, method or class - final val CASEACCESSOR = 0x01000000 // symbol is a case parameter (or its accessor) + final val CASEACCESSOR = 0x01000000 // symbol is a case parameter (or its accessor, or a GADT skolem) final val TRAIT = 0x02000000 // symbol is a trait final val DEFAULTPARAM = 0x02000000 // the parameter has a default value final val PARAMACCESSOR = 0x20000000 // for field definitions generated for primary constructor diff --git a/src/compiler/scala/reflect/internal/Symbols.scala b/src/compiler/scala/reflect/internal/Symbols.scala index 9678d2b8cd..7673aec4c7 100644 --- a/src/compiler/scala/reflect/internal/Symbols.scala +++ b/src/compiler/scala/reflect/internal/Symbols.scala @@ -269,11 +269,17 @@ trait Symbols extends api.Symbols { self: SymbolTable => /** Create a new existential type skolem with this symbol its owner, * based on the given symbol and origin. */ - def newExistentialSkolem(basis: Symbol, origin: AnyRef, name: TypeName = null, info: Type = null): TypeSkolem = { - val skolem = newTypeSkolemSymbol(if (name eq null) basis.name.toTypeName else name, origin, basis.pos, (basis.flags | EXISTENTIAL) & ~PARAM) - skolem setInfo (if (info eq null) basis.info cloneInfo skolem else info) + def newExistentialSkolem(basis: Symbol, origin: AnyRef): TypeSkolem = { + val skolem = newTypeSkolemSymbol(basis.name.toTypeName, origin, basis.pos, (basis.flags | EXISTENTIAL) & ~PARAM) + skolem setInfo (basis.info cloneInfo skolem) } + // flags set up to maintain TypeSkolem's invariant: origin.isInstanceOf[Symbol] == !hasFlag(EXISTENTIAL) + // CASEACCESSOR | SYNTHETIC used to single this symbol out in deskolemizeGADT + def newGADTSkolem(name: TypeName, origin: Symbol, info: Type): TypeSkolem = + newTypeSkolemSymbol(name, origin, origin.pos, origin.flags & ~(EXISTENTIAL | PARAM) | CASEACCESSOR | SYNTHETIC) setInfo info + + final def newExistential(name: TypeName, pos: Position = NoPosition, newFlags: Long = 0L): Symbol = newAbstractType(name, pos, EXISTENTIAL | newFlags) @@ -495,6 +501,7 @@ trait Symbols extends api.Symbols { self: SymbolTable => // List[T] forSome { type T } final def isExistentialSkolem = isExistentiallyBound && isSkolem final def isExistentialQuantified = isExistentiallyBound && !isSkolem + final def isGADTSkolem = isSkolem && hasFlag(CASEACCESSOR | SYNTHETIC) // class C extends D( { class E { ... } ... } ). Here, E is a class local to a constructor final def isClassLocalToConstructor = isClass && hasFlag(INCONSTRUCTOR) @@ -2129,12 +2136,17 @@ trait Symbols extends api.Symbols { self: SymbolTable => else if (owner.isRefinementClass) ExplicitFlags & ~OVERRIDE else ExplicitFlags + // make the error message more googlable + def flagsExplanationString = + if (isGADTSkolem) " (this is a GADT skolem)" + else "" + def accessString = hasFlagsToString(PRIVATE | PROTECTED | LOCAL) def defaultFlagString = hasFlagsToString(defaultFlagMask) private def defStringCompose(infoString: String) = compose( defaultFlagString, keyString, - varianceString + nameString + infoString + varianceString + nameString + infoString + flagsExplanationString ) /** String representation of symbol's definition. It uses the * symbol's raw info to avoid forcing types. @@ -2477,7 +2489,7 @@ trait Symbols extends api.Symbols { self: SymbolTable => * where the skolem was introduced (this is important for knowing when to pack it * again into ab Existential). origin is `null` only in skolemizeExistentials called * from <:< or isAsSpecific, because here its value does not matter. - * I elieve the following invariant holds: + * I believe the following invariant holds: * * origin.isInstanceOf[Symbol] == !hasFlag(EXISTENTIAL) */ diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala index 2382413a9a..549c9e4607 100644 --- a/src/compiler/scala/reflect/internal/Types.scala +++ b/src/compiler/scala/reflect/internal/Types.scala @@ -1041,8 +1041,8 @@ trait Types extends api.Types { self: SymbolTable => baseClasses.head.newOverloaded(this, members.toList) } } - /** The existential skolems and existentially quantified variables which are free in this type */ - def existentialSkolems: List[Symbol] = { + /** The (existential or otherwise) skolems and existentially quantified variables which are free in this type */ + def skolemsExceptMethodTypeParams: List[Symbol] = { var boundSyms: List[Symbol] = List() var skolems: List[Symbol] = List() for (t <- this) { @@ -1050,7 +1050,8 @@ trait Types extends api.Types { self: SymbolTable => case ExistentialType(quantified, qtpe) => boundSyms = boundSyms ::: quantified case TypeRef(_, sym, _) => - if ((sym hasFlag EXISTENTIAL) && !(boundSyms contains sym) && !(skolems contains sym)) + if ((sym.isExistentialSkolem || sym.isGADTSkolem) && // treat GADT skolems like existential skolems + !((boundSyms contains sym) || (skolems contains sym))) skolems = sym :: skolems case _ => } diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 8b3bc253fd..a59622d4df 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -1099,7 +1099,7 @@ trait Infer { // since instantiateTypeVar wants to modify the skolem that corresponds to the method's type parameter, // and it uses the TypeVar's origin to locate it, deskolemize the existential skolem to the method tparam skolem // (the existential skolem was created by adaptConstrPattern to introduce the type slack necessary to soundly deal with variant type parameters) - case skolem if skolem.isExistentialSkolem => freshVar(skolem.deSkolemize.asInstanceOf[TypeSymbol]) + case skolem if skolem.isGADTSkolem => freshVar(skolem.deSkolemize.asInstanceOf[TypeSymbol]) case p => freshVar(p) } diff --git a/src/compiler/scala/tools/nsc/typechecker/TypeDiagnostics.scala b/src/compiler/scala/tools/nsc/typechecker/TypeDiagnostics.scala index 1434002121..e17a271dd0 100644 --- a/src/compiler/scala/tools/nsc/typechecker/TypeDiagnostics.scala +++ b/src/compiler/scala/tools/nsc/typechecker/TypeDiagnostics.scala @@ -157,7 +157,7 @@ trait TypeDiagnostics { } // todo: use also for other error messages - def existentialContext(tp: Type) = tp.existentialSkolems match { + def existentialContext(tp: Type) = tp.skolemsExceptMethodTypeParams match { case Nil => "" case xs => " where " + (disambiguate(xs map (_.existentialToString)) mkString ", ") } diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index 25f3e7af5c..0dd4b37131 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -909,8 +909,9 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { def apply(tp: Type) = mapOver(tp) match { case TypeRef(NoPrefix, tpSym, Nil) if variance != 0 && tpSym.isTypeParameterOrSkolem && tpSym.owner.isTerm => val bounds = if (variance == 1) TypeBounds.upper(tpSym.tpe) else TypeBounds.lower(tpSym.tpe) - val skolem = context.owner.newExistentialSkolem(tpSym, tpSym, unit.freshTypeName("?"+tpSym.name), bounds) - // println("mapping "+ tpSym +" to "+ skolem + " : "+ bounds +" -- pt= "+ pt) + // origin must be the type param so we can deskolemize + val skolem = context.owner.newGADTSkolem(unit.freshTypeName("?"+tpSym.name), tpSym, bounds) + // println("mapping "+ tpSym +" to "+ skolem + " : "+ bounds +" -- pt= "+ pt +" in "+ context.owner +" at "+ context.tree ) skolems += skolem skolem.tpe case tp1 => tp1 @@ -928,9 +929,19 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { freeVars foreach ctorContext.scope.enter newTyper(ctorContext).infer.inferConstructorInstance(tree1, clazz.typeParams, ptSafe) - // tree1's type-slack skolems will be deskolemized (to the method type parameter skolems) - // once the containing CaseDef has been type checked (see typedCase) - tree1 + // simplify types without losing safety, + // so that error messages don't unnecessarily refer to skolems + val extrapolate = new ExistentialExtrapolation(freeVars) extrapolate (_: Type) + val extrapolated = tree1.tpe match { + case MethodType(ctorArgs, res) => // ctorArgs are actually in a covariant position, since this is the type of the subpatterns of the pattern represented by this Apply node + ctorArgs foreach (p => p.info = extrapolate(p.info)) // no need to clone, this is OUR method type + copyMethodType(tree1.tpe, ctorArgs, extrapolate(res)) + case tp => tp + } + + // once the containing CaseDef has been type checked (see typedCase), + // tree1's remaining type-slack skolems will be deskolemized (to the method type parameter skolems) + tree1 setType extrapolated } else { tree } @@ -1095,7 +1106,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { val found = tree.tpe val req = pt if (!found.isErroneous && !req.isErroneous) { - if (!context.reportErrors && isPastTyper && req.existentialSkolems.nonEmpty) { + if (!context.reportErrors && isPastTyper && req.skolemsExceptMethodTypeParams.nonEmpty) { // Ignore type errors raised in later phases that are due to mismatching types with existential skolems // We have lift crashing in 2.9 with an adapt failure in the pattern matcher. // Here's my hypothsis why this happens. The pattern matcher defines a variable of type @@ -1112,7 +1123,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { // // val x = expr context.unit.warning(tree.pos, "recovering from existential Skolem type error in tree \n" + tree + "\nwith type " + tree.tpe + "\n expected type = " + pt + "\n context = " + context.tree) - adapt(tree, mode, deriveTypeWithWildcards(pt.existentialSkolems)(pt)) + adapt(tree, mode, deriveTypeWithWildcards(pt.skolemsExceptMethodTypeParams)(pt)) } else { // create an actual error AdaptTypeError(tree, found, req) @@ -2112,21 +2123,21 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { // body1 = checkNoEscaping.locals(context.scope, pt, body1) val treeWithSkolems = treeCopy.CaseDef(cdef, pat1, guard1, body1) setType body1.tpe - // undo adaptConstrPattern's evil deeds, as they confuse the old pattern matcher - // TODO: Paul, can we do the deskolemization lazily in the old pattern matcher - object deskolemizeOnce extends TypeMap { - def apply(tp: Type): Type = mapOver(tp) match { - case TypeRef(pre, sym, args) if sym.isExistentialSkolem && sym.deSkolemize.isSkolem && sym.deSkolemize.owner.isTerm => - typeRef(NoPrefix, sym.deSkolemize, args) - case tp1 => tp1 - } - } - - new TypeMapTreeSubstituter(deskolemizeOnce).traverse(treeWithSkolems) + new TypeMapTreeSubstituter(deskolemizeGADTSkolems).traverse(treeWithSkolems) treeWithSkolems // now without skolems, actually } + // undo adaptConstrPattern's evil deeds, as they confuse the old pattern matcher + // the flags are used to avoid accidentally deskolemizing unrelated skolems of skolems + object deskolemizeGADTSkolems extends TypeMap { + def apply(tp: Type): Type = mapOver(tp) match { + case TypeRef(pre, sym, args) if sym.isGADTSkolem => + typeRef(NoPrefix, sym.deSkolemize, args) + case tp1 => tp1 + } + } + def typedCases(cases: List[CaseDef], pattp: Type, pt: Type): List[CaseDef] = cases mapConserve { cdef => newTyper(context.makeNewScope(cdef, context.owner)).typedCase(cdef, pattp, pt) diff --git a/test/files/neg/t3015.check b/test/files/neg/t3015.check index 53221b7ca0..6948392bb0 100644 --- a/test/files/neg/t3015.check +++ b/test/files/neg/t3015.check @@ -1,5 +1,5 @@ t3015.scala:7: error: scrutinee is incompatible with pattern type; - found : _$1 where type +_$1 + found : _$1 required: String val b(foo) = "foo" ^ diff --git a/test/files/neg/t3481.check b/test/files/neg/t3481.check index 48e6ff357b..debe07275b 100644 --- a/test/files/neg/t3481.check +++ b/test/files/neg/t3481.check @@ -1,17 +1,17 @@ t3481.scala:5: error: type mismatch; found : String("hello") - required: _$1 where type +_$1 + required: _$1 f[A[Int]]("hello") ^ t3481.scala:11: error: type mismatch; - found : _$2 where type +_$2 + found : _$2 required: b.T (which expands to) _$2 def f[T <: B[_]](a: T#T, b: T) = b.m(a) ^ t3481.scala:12: error: type mismatch; found : String("Hello") - required: _$2 where type +_$2 + required: _$2 f("Hello", new B[Int]) ^ t3481.scala:18: error: type mismatch; diff --git a/test/files/neg/t4515.check b/test/files/neg/t4515.check index ce5350b35f..a60d16295f 100644 --- a/test/files/neg/t4515.check +++ b/test/files/neg/t4515.check @@ -1,6 +1,6 @@ t4515.scala:37: error: type mismatch; found : _0(in value $anonfun) where type _0(in value $anonfun) - required: (some other)_0(in value $anonfun) where type +(some other)_0(in value $anonfun) + required: (some other)_0(in value $anonfun) handler.onEvent(target, ctx.getEvent, node, ctx) ^ one error found diff --git a/test/files/neg/t5189b.check b/test/files/neg/t5189b.check index 7f78cbb438..46996e96d0 100644 --- a/test/files/neg/t5189b.check +++ b/test/files/neg/t5189b.check @@ -1,8 +1,11 @@ -t5189b.scala:25: error: type mismatch; - found : TestNeg.Wrapped[?T2] where type ?T2 <: T +t5189b.scala:38: error: type mismatch; + found : TestNeg.Wrapped[?T7] where type ?T7 <: T (this is a GADT skolem) required: TestNeg.Wrapped[T] -Note: ?T2 <: T, but class Wrapped is invariant in type W. +Note: ?T7 <: T, but class Wrapped is invariant in type W. You may wish to define W as +W instead. (SLS 4.5) case Wrapper/*[_ <: T ]*/(wrapped) => wrapped // : Wrapped[_ <: T], which is a subtype of Wrapped[T] if and only if Wrapped is covariant in its type parameter ^ -one error found +t5189b.scala:51: error: value foo is not a member of type parameter T + case Some(xs) => xs.foo // the error message should not refer to a skolem (testing extrapolation) + ^ +two errors found diff --git a/test/files/neg/t5189b.scala b/test/files/neg/t5189b.scala index 1750f14084..7c1871dc97 100644 --- a/test/files/neg/t5189b.scala +++ b/test/files/neg/t5189b.scala @@ -5,8 +5,21 @@ class TestPos { def unwrap[T](x: AbsWrapperCov[T]): T = x match { case Wrapper/*[_ <: T ]*/(x) => x // _ <: T, which is a subtype of T } + + def unwrapOption[T](x: Option[T]): T = x match { + case Some(xs) => xs + } + + + case class Down[+T](x: T) + case class Up[-T](f: T => Unit) + + def f1[T](x1: Down[T])(x2: Up[T]) = ((x1, x2)) match { + case (Down(x), Up(f)) => f(x) + } } + object TestNeg extends App { class AbsWrapperCov[+A] case class Wrapper[B](x: Wrapped[B]) extends AbsWrapperCov[B] @@ -33,6 +46,11 @@ object TestNeg extends App { // val w = new Wrapped(new A) // unwrap[Any](Wrapper(w)).cell = new B // w.cell.imNotAB + + def unwrapOption[T](x: Option[T]): T = x match { + case Some(xs) => xs.foo // the error message should not refer to a skolem (testing extrapolation) + } + } // class TestPos1 { -- cgit v1.2.3