From 917c49416133bd067c203f907e9fe9112a081ff4 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Sat, 1 Feb 2014 17:59:34 +0100 Subject: SI-8224 Fix regression in f-bound aware LUBs Disable the heuristic approach to recursive bounds unless the compiler is running under `-Xstrict-inference`. [the above was not authored by the original author] In db46c71e88, steps were taken to avoid blowing up in the pathological LUB calculation needed for: def trav = List(List(), Stream()) This skipped a level in the base class sequence when f-bounds were detected at the current level. In that example, when `lublist` was about to: mergePrefixAndArgs( typeOf[LinearSeqOptimized[A, List[A]]], typeOf[LinearSeqOptimized[A, Stream[A]]], ) If it proceeded (as in 2.10.3), the LUB is invalid: error: type arguments [B[_ >: D with C <: B[_ >: D with C <: A]],s.c.immutable.LinearSeq[B[_ >: D with C <: A]] with s.c.AbstractSeq[B[_ >: D with C <: A]] with s.c.LinearSeqOptimized[B[_ >: D with C <: A],s.c.immutable.LinearSeq[A] with s.c.AbstractSeq[A] with s.c.LinearSeqOptimized[A,Immutable with Equals with java.io.Serializable] with java.io.Serializable] with java.io.Serializable] do not conform to trait LinearSeqOptimized's type parameter bounds [+A,+Repr <: s.c.LinearSeqOptimized[A,Repr]] To avoid this, the added code would skip to the first non-F-bounded base type of the same arity of each element in the list. This would get to: LinearSeqLike[D, Stream[D]] LinearSeqLike[C, List[C]] which are lubbable without violating the type constraints. I don't think this was the right remedy. For starters, as seen in this bug report, SI-8224, if the list of types are identical we have let a perfectly good lub slip through our fingers, and end up calculating too general a type. More generally, if the type arguments in f-bounded positions coincide, we don't risk calculating a ill-bounded LUB. Furthermore, the code was widening each of the types separately; this isn't something we want to do within `if (isUniformFrontier)`. AFAICT this was just wasteful and as all `ts0` start with the same type symbol, so `typeConstructorList` should be uniform. This commit restricts this base-class skipping to situations where the argument inferred for an type argument that is used as an f-bound is not: a) an existential (as created by `mergePrefixAndArgs` in invariant positions.), or b) equivalent to one of the corresponding input type arguments (this is the case that fixes the regression in pos/8224.scala) --- .../internal/settings/MutableSettings.scala | 1 + .../scala/reflect/internal/tpe/GlbLubs.scala | 69 ++++++++++------------ src/reflect/scala/reflect/runtime/Settings.scala | 1 + test/files/pos/t8224.scala | 12 ++++ test/files/run/t2251.flags | 1 + test/files/run/t2251b.flags | 1 + 6 files changed, 48 insertions(+), 37 deletions(-) create mode 100644 test/files/pos/t8224.scala create mode 100644 test/files/run/t2251.flags create mode 100644 test/files/run/t2251b.flags diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala index 048fe9ef37..a494c7f0d0 100644 --- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala +++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala @@ -37,6 +37,7 @@ abstract class MutableSettings extends AbsSettings { def XfullLubs: BooleanSetting def XnoPatmatAnalysis: BooleanSetting def Xprintpos: BooleanSetting + def strictInference: BooleanSetting def Yposdebug: BooleanSetting def Yrangepos: BooleanSetting def Yshowsymowners: BooleanSetting diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala index 1c4d05ae32..876685e24a 100644 --- a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala +++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala @@ -14,11 +14,11 @@ private[internal] trait GlbLubs { import TypesStats._ private final val printLubs = scala.sys.props contains "scalac.debug.lub" + private final val strictInference = settings.strictInference /** In case anyone wants to turn off lub verification without reverting anything. */ private final val verifyLubs = true - private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Depth) { import util.TableDef import TableDef.Column @@ -63,6 +63,26 @@ private[internal] trait GlbLubs { } } + // only called when strictInference + private def willViolateRecursiveBounds(tp: Type, ts: List[Type], tsElimSub: List[Type]) = { + val typeSym = ts.head.typeSymbol // we're uniform, the `.head` is as good as any. + def fbounds = findRecursiveBounds(ts) map (_._2) + def isRecursive = typeSym.typeParams exists fbounds.contains + + isRecursive && (transposeSafe(tsElimSub map (_.normalize.typeArgs)) match { + case Some(arggsTransposed) => + val mergedTypeArgs = (tp match { case et: ExistentialType => et.underlying; case _ => tp}).typeArgs + exists3(typeSym.typeParams, mergedTypeArgs, arggsTransposed) { + (param, arg, lubbedArgs) => + val isExistential = arg.typeSymbol.isExistentiallyBound + val isInFBound = fbounds contains param + val wasLubbed = !lubbedArgs.exists(_ =:= arg) + (!isExistential && isInFBound && wasLubbed) + } + case None => false + }) + } + /** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix), * compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types: * @@ -88,7 +108,8 @@ private[internal] trait GlbLubs { case _ => tp } // pretypes is a tail-recursion-preserving accumulator. - @tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = { + @tailrec + def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = { lubListDepth = lubListDepth.incr if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse @@ -110,28 +131,19 @@ private[internal] trait GlbLubs { // merging, strip targs that refer to bound tparams (when we're computing the lub of type // constructors.) Also filter out all types that are a subtype of some other type. if (isUniformFrontier) { - val fbounds = findRecursiveBounds(ts0) map (_._2) - val tcLubList = typeConstructorLubList(ts0) - def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains - - val ts1 = ts0 map { t => - if (isRecursive(t)) { - tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match { - case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n Was: $t\n Now")(tp) - case _ => t - } - } - else t - } val tails = tsBts map (_.tail) - mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match { + val ts1 = elimSub(ts0, depth) map elimHigherOrderTypeParam + mergePrefixAndArgs(ts1, Covariant, depth) match { case NoType => loop(pretypes, tails) - case tp => loop(tp :: pretypes, tails) + case tp if strictInference && willViolateRecursiveBounds(tp, ts0, ts1) => + log(s"Breaking recursion in lublist, advancing frontier and discaring merged prefix/args from $tp") + loop(pretypes, tails) + case tp => + loop(tp :: pretypes, tails) } - } - else { + } else { // frontier is not uniform yet, move it beyond the current minimal symbol; - // lather, rinSe, repeat + // lather, rinse, repeat val sym = minSym(ts0) val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts) if (printLubs) { @@ -257,23 +269,6 @@ private[internal] trait GlbLubs { private val _glbResults = new mutable.HashMap[(Depth, List[Type]), Type] def glbResults = _glbResults - /** Given a list of types, finds all the base classes they have in - * common, then returns a list of type constructors derived directly - * from the symbols (so any more specific type information is ignored.) - * The list is filtered such that every type constructor in the list - * expects the same number of type arguments, which is chosen based - * on the deepest class among the common baseclasses. - */ - def typeConstructorLubList(ts: List[Type]): List[Type] = { - val bcs = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _) - val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz)) - - tcons map (_.typeConstructor) match { - case Nil => Nil - case t :: ts => t :: ts.filter(_.typeParams.size == t.typeParams.size) - } - } - def lub(ts: List[Type]): Type = ts match { case Nil => NothingTpe case t :: Nil => t diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala index d46846fc21..27d574b1de 100644 --- a/src/reflect/scala/reflect/runtime/Settings.scala +++ b/src/reflect/scala/reflect/runtime/Settings.scala @@ -33,6 +33,7 @@ private[reflect] class Settings extends MutableSettings { val Xexperimental = new BooleanSetting(false) val XfullLubs = new BooleanSetting(false) val XnoPatmatAnalysis = new BooleanSetting(false) + val strictInference = new BooleanSetting(false) val Xprintpos = new BooleanSetting(false) val Yposdebug = new BooleanSetting(false) val Yrangepos = new BooleanSetting(false) diff --git a/test/files/pos/t8224.scala b/test/files/pos/t8224.scala new file mode 100644 index 0000000000..2fae925df3 --- /dev/null +++ b/test/files/pos/t8224.scala @@ -0,0 +1,12 @@ +import language.higherKinds + +trait P [N1, +E1[X <: N1]] +trait PIn[N2, +E2[X <: N2]] extends P[Int,Any] + +trait EI extends PIn[Int, Nothing] +trait NI extends PIn[Int, Nothing] + +object Test { + val lub = if (true) ??? : EI else ??? : NI + val pin: PIn[Int,Nothing] = lub +} diff --git a/test/files/run/t2251.flags b/test/files/run/t2251.flags new file mode 100644 index 0000000000..19243266d1 --- /dev/null +++ b/test/files/run/t2251.flags @@ -0,0 +1 @@ +-Xstrict-inference \ No newline at end of file diff --git a/test/files/run/t2251b.flags b/test/files/run/t2251b.flags new file mode 100644 index 0000000000..19243266d1 --- /dev/null +++ b/test/files/run/t2251b.flags @@ -0,0 +1 @@ +-Xstrict-inference \ No newline at end of file -- cgit v1.2.3