From 2a1b15ea5d8b9e4060846135e8a7adf74b9c398f Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Fri, 14 Feb 2014 16:08:23 +0100 Subject: SI-8283 mutation-free bound inference for existentials A safer version of the fix for SI-6169 (#3471) Only modify the skolems to avoid leaking the sharper bounds to `quantified`. The included test case was minimized from akka-camel (src/main/scala/akka/camel/Consumer.scala). --- src/reflect/scala/reflect/internal/Symbols.scala | 42 ++++++++++++- src/reflect/scala/reflect/internal/Types.scala | 79 ++++++++++++------------ 2 files changed, 80 insertions(+), 41 deletions(-) (limited to 'src') diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala index 81e78d4c5d..c5c104a2fc 100644 --- a/src/reflect/scala/reflect/internal/Symbols.scala +++ b/src/reflect/scala/reflect/internal/Symbols.scala @@ -384,9 +384,14 @@ 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): TypeSkolem = { - val skolem = newTypeSkolemSymbol(basis.name.toTypeName, origin, basis.pos, (basis.flags | EXISTENTIAL) & ~PARAM) - skolem setInfo (basis.info cloneInfo skolem) + def newExistentialSkolem(basis: Symbol, origin: AnyRef): TypeSkolem = + newExistentialSkolem(basis.name.toTypeName, basis.info, basis.flags, basis.pos, origin) + + /** Create a new existential type skolem with this symbol its owner, and the given other properties. + */ + def newExistentialSkolem(name: TypeName, info: Type, flags: Long, pos: Position, origin: AnyRef): TypeSkolem = { + val skolem = newTypeSkolemSymbol(name.toTypeName, origin, pos, (flags | EXISTENTIAL) & ~PARAM) + skolem setInfo (info cloneInfo skolem) } // don't test directly -- use isGADTSkolem @@ -3419,6 +3424,21 @@ trait Symbols extends api.Symbols { self: SymbolTable => mapList(syms1)(_ substInfo (syms, syms1)) } + /** Derives a new list of symbols from the given list by mapping the given + * list of `syms` and `as` across the given function. + * Then fixes the info of all the new symbols + * by substituting the new symbols for the original symbols. + * + * @param syms the prototypical symbols + * @param as arguments to be passed to symFn together with symbols from syms (must be same length) + * @param symFn the function to create new symbols + * @return the new list of info-adjusted symbols + */ + def deriveSymbols2[A](syms: List[Symbol], as: List[A], symFn: (Symbol, A) => Symbol): List[Symbol] = { + val syms1 = map2(syms, as)(symFn) + mapList(syms1)(_ substInfo (syms, syms1)) + } + /** Derives a new Type by first deriving new symbols as in deriveSymbols, * then performing the same oldSyms => newSyms substitution on `tpe` as is * performed on the symbol infos in deriveSymbols. @@ -3432,6 +3452,22 @@ trait Symbols extends api.Symbols { self: SymbolTable => val syms1 = deriveSymbols(syms, symFn) tpe.substSym(syms, syms1) } + + /** Derives a new Type by first deriving new symbols as in deriveSymbols2, + * then performing the same oldSyms => newSyms substitution on `tpe` as is + * performed on the symbol infos in deriveSymbols. + * + * @param syms the prototypical symbols + * @param as arguments to be passed to symFn together with symbols from syms (must be same length) + * @param symFn the function to create new symbols based on `as` + * @param tpe the prototypical type + * @return the new symbol-subsituted type + */ + def deriveType2[A](syms: List[Symbol], as: List[A], symFn: (Symbol, A) => Symbol)(tpe: Type): Type = { + val syms1 = deriveSymbols2(syms, as, symFn) + tpe.substSym(syms, syms1) + } + /** Derives a new Type by instantiating the given list of symbols as * WildcardTypes. * diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 6010d4eb12..ad451f6e0d 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -93,10 +93,11 @@ trait Types private final val traceTypeVars = sys.props contains "scalac.debug.tvar" private final val breakCycles = settings.breakCycles.value - /** In case anyone wants to turn off type parameter bounds being used + /** In case anyone wants to turn on type parameter bounds being used * to seed type constraints. */ private final val propagateParameterBoundsToTypeVars = sys.props contains "scalac.debug.prop-constraints" + private final val sharperSkolems = sys.props contains "scalac.experimental.sharper-skolems" protected val enableTypeVarExperimentals = settings.Xexperimental.value @@ -2551,56 +2552,58 @@ trait Types override def baseTypeSeq = underlying.baseTypeSeq map maybeRewrap override def isHigherKinded = false + // TODO: check invariant that all quantifiers have the same (existing) owner + private def quantifierOwner = quantified collectFirst { case q if q.owner.exists => q.owner } getOrElse NoSymbol + + // Is this existential of the form: T[Q1, ..., QN] forSome { type Q1 >: L1 <: U1, ..., QN >: LN <: UN} + private def isStraightApplication = (quantified corresponds underlying.typeArgs){ (q, a) => q.tpe =:= a } + /** [SI-6169, SI-8197 -- companion to SI-1786] * - * Approximation to improve the bounds of a Java-defined existential type, - * based on the bounds of the type parameters of the quantified type - * In Scala syntax, given a java-defined class C[T <: String], the existential type C[_] - * is improved to C[_ <: String] before skolemization, which captures (get it?) what Java does: - * enter the type paramers' bounds into the context when checking subtyping/type equality of existential types + * Approximation to improve the bounds of a Java-defined existential type, + * based on the bounds of the type parameters of the quantified type + * In Scala syntax, given a java-defined class C[T <: String], the existential type C[_] + * is improved to C[_ <: String] before skolemization, which captures (get it?) what Java does: + * enter the type paramers' bounds into the context when checking subtyping/type equality of existential types * - * (Also tried doing this once during class file parsing or when creating the existential type, - * but that causes cyclic errors because it happens too early.) + * Also tried doing this once during class file parsing or when creating the existential type, + * but that causes cyclic errors because it happens too early. + * + * NOTE: we're only modifying the skolems to avoid leaking the sharper bounds to `quantified` (SI-8283) * * TODO: figure out how to do this earlier without running into cycles, so this can subsume the fix for SI-1786 */ - private def sharpenQuantifierBounds(): Unit = { - /* Check that we're looking at rawToExistential's handiwork - * (`existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe)))`). - * We can't do this sharpening there because we'll run into cycles. - */ - def rawToExistentialCreatedMe = (quantified corresponds underlying.typeArgs){ (q, a) => q.tpe =:= a } - - if (underlying.typeSymbol.isJavaDefined && rawToExistentialCreatedMe) { - val tpars = underlying.typeSymbol.initialize.typeParams // TODO: is initialize needed? - debuglog(s"sharpen bounds: $this | ${underlying.typeArgs.map(_.typeSymbol)} <-- ${tpars.map(_.info)}") - - foreach2(quantified, tpars) { (quant, tparam) => - // TODO: check `tparam.info.substSym(tpars, quantified) <:< quant.info` instead (for some weird reason not working for test/t6169/ExistF) - // for now, crude approximation for the common case - if (quant.info.bounds.isEmptyBounds && !tparam.info.bounds.isEmptyBounds) { - // avoid creating cycles [pos/t2940] that consist of an existential quantifier's - // bounded by an existential type that unhygienically has that quantifier as its own quantifier - // (TODO: clone latter existential with fresh quantifiers -- not covering this case for now) - if ((existentialsInType(tparam.info) intersect quantified).isEmpty) - quant setInfo tparam.info.substSym(tpars, quantified) - } - } - } + override def skolemizeExistential(owner0: Symbol, origin: AnyRef) = { + val owner = owner0 orElse quantifierOwner - _sharpenQuantifierBounds = false - } - private[this] var _sharpenQuantifierBounds = true - - override def skolemizeExistential(owner: Symbol, origin: AnyRef) = { // do this here because it's quite close to what Java does: // when checking subtyping/type equality, enter constraints // derived from the existentially quantified type into the typing environment // (aka \Gamma, which tracks types for variables and constraints/kinds for types) // as a nice bonus, delaying this until we need it avoids cyclic errors - if (_sharpenQuantifierBounds) sharpenQuantifierBounds + def tpars = underlying.typeSymbol.initialize.typeParams + + def newSkolem(quant: Symbol) = owner.newExistentialSkolem(quant, origin) + def newSharpenedSkolem(quant: Symbol, tparam: Symbol): Symbol = { + def emptyBounds(sym: Symbol) = sym.info.bounds.isEmptyBounds + + // avoid creating cycles [pos/t2940] that consist of an existential quantifier's + // bounded by an existential type that unhygienically has that quantifier as its own quantifier + // (TODO: clone latter existential with fresh quantifiers -- not covering this case for now) + val canSharpen = ( + emptyBounds(quant) && !emptyBounds(tparam) + && (existentialsInType(tparam.info) intersect quantified).isEmpty + ) + + val skolemInfo = if (!canSharpen) quant.info else tparam.info.substSym(tpars, quantified) + + owner.newExistentialSkolem(quant.name.toTypeName, skolemInfo, quant.flags, quant.pos, origin) + } + + val canSharpenBounds = (underlying.typeSymbol.isJavaDefined || sharperSkolems) && isStraightApplication - deriveType(quantified, tparam => (owner orElse tparam.owner).newExistentialSkolem(tparam, origin))(underlying) + if (canSharpenBounds) deriveType2(quantified, tpars, newSharpenedSkolem)(underlying) + else deriveType(quantified, newSkolem)(underlying) } private def wildcardArgsString(qset: Set[Symbol], args: List[Type]): List[String] = args map { -- cgit v1.2.3