diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2014-02-01 17:59:34 +0100 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@typesafe.com> | 2014-02-18 21:02:50 -0800 |
commit | 917c49416133bd067c203f907e9fe9112a081ff4 (patch) | |
tree | eea69d042c59030ac663973b7013a12119763ae7 /src/reflect | |
parent | 3dbcb1b9d4daa5cba98747bbc66f898ba0f864fd (diff) | |
download | scala-917c49416133bd067c203f907e9fe9112a081ff4.tar.gz scala-917c49416133bd067c203f907e9fe9112a081ff4.tar.bz2 scala-917c49416133bd067c203f907e9fe9112a081ff4.zip |
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)
Diffstat (limited to 'src/reflect')
3 files changed, 34 insertions, 37 deletions
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) |