Stack overflow regression in typer

[scabug]

I changed my Kiama library's sbt build scalaVersion from 2.10.0 to 2.10.1-RC1 and now when I compile I get a stack overflow in the typer. All was fine with 2.10.0.

I'm still narrowing the code down but I wanted to report it quickly since this is an RC.

The attached file Rewriter.scala contains the childSeq method in which the crash occurs (line 438). I've attached the crash report and the top of the stack trace is:

[error] uncaught exception during compilation: java.lang.StackOverflowError
java.lang.StackOverflowError
at scala.reflect.internal.Symbols$Symbol.info(Symbols.scala:1239)
at scala.reflect.internal.Types$TypeRef.initializedTypeParams(Types.scala:2400)
at scala.reflect.internal.Types$TypeRef.typeParamsMatchArgs(Types.scala:2401)
at scala.reflect.internal.Types$AliasTypeRef$class.dealias(Types.scala:2224)
at scala.reflect.internal.Types$TypeRef$$anon$1.dealias(Types.scala:2526)
at scala.tools.nsc.typechecker.Typers$Typer.dropExistential(Typers.scala:224)
at scala.tools.nsc.typechecker.Typers$Typer.dropExistential(Typers.scala:225)
at scala.tools.nsc.typechecker.Typers$Typer.dropExistential(Typers.scala:225)
at scala.tools.nsc.typechecker.Typers$Typer.dropExistential(Typers.scala:225)
at scala.tools.nsc.typechecker.Typers$Typer.dropExistential(Typers.scala:225)

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-7126?orig=1
Reporter: Tony Sloane (asloane)
Affected Versions: 2.10.1-RC1
Attachments:

• report.txt (created on Feb 14, 2013 4:41:07 AM UTC, 10074 bytes)
• Rewriter.scala (created on Feb 14, 2013 4:41:07 AM UTC, 58825 bytes)

[scabug]

@retronym said:
scala/scala@3bf511 ?

[scabug]

@JamesIry said:
Whether dealias or normalize, dropExistential needs to protect itself against the x.dealias/normalize/whatever returning x.

[scabug]

@paulp said:
I think it's a bug if x.dealias eq x on an AliasTypeRef; you shouldn't have to check at every call site that calling dealias on an alias makes progress. Which is not to say we should not play defense when necessary. But we should not be creating alias cycles.

This line suggests that normalize should indeed be called, and it also doesn't look at all sensible to me that super.dealias when the condition is hit (which is not often, apparently.) By inspection, it looks like it will only mask bugs.

    override def dealias    = if (typeParamsMatchArgs) betaReduce.dealias else super.dealias

[scabug]

@paulp said:
The super.dealias path is hit when compiling the library 6 times total, generally going through either typedTypeConstructor or typedHigherKindedType. For instance, the line containing GenPolyType below.

        val args1 = if (sameLength(args, tparams)) {
          //@M: in case TypeApply we can't check the kind-arities of the type arguments,
          // as we don't know which alternative to choose... here we do
          map2Conserve(args, tparams) {
            //@M! the polytype denotes the expected kind
            (arg, tparam) => typedHigherKindedType(arg, mode, GenPolyType(tparam.typeParams, AnyClass.tpe))
          }
        } else // @M: there's probably something wrong when args.length != tparams.length... (triggered by bug #320)
         // Martin, I'm using fake trees, because, if you use args or arg.map(typedType),
         // inferPolyAlternatives loops...  -- I have no idea why :-(
         // ...actually this was looping anyway, see bug #278.
          return TypedApplyWrongNumberOfTpeParametersError(fun, fun)

One of those old beloved comments, "there's probably something wrong when args.length != tparams.length", yeah. Notice the usage of Any, which is kind-polymorphic, a code phrase which means "there will be bugs" in the mother tongue. We shouldn't have to work so hard to prevent type constructors which are being checked for well-kindedness from being confused with applied types and/or types undergoing other checks like bounds conformance. Aka explicit kinds.

[scabug]

@retronym said:
Here's a test case extracted from Kiama:

type T = Any
boom(???): Option[T] // SOE
def boom[CC[U]](t : CC[T]): Option[CC[T]] = None

// okay
foo(???): Option[Any]
def foo[CC[U]](t : CC[Any]): Option[CC[Any]] = None

Is there an in-flight patch for this? If not I can submit one.

[scabug]

@paulp said:
I don't have one in flight; it should be one line, as I believe you know.

[scabug]

@retronym said:
Here's the superficial remedy: scala/scala#2167

[scabug]

Tony Sloane (asloane) said:
Thanks all for tracking this one down, particularly Jason for narrowing the test case.

I'm curious the fix version is now Scala 2.11.0-M2. Since this is a regression from 2.10.0 I was hoping to see a fix in 2.10.1.

[scabug]

@retronym said (edited on Feb 26, 2013 6:05:24 PM UTC):

 Notice the usage of Any, which is kind-polymorphic, a code phrase which means "there will be bugs" in the mother tongue

Any is a bit of a red herring there, the for type checking higher kinded types, expected kind is sneakily encoded an expected type (ie pt). In that encoding, the return type is unused.

What happens is that we have a higher kinded type ref encoded (again) as an AliasTypeRef without args. This can't be dealiased, the only way to reveal anything further is via etaExpand (which is behind normalize for these.

For example:

type L[X] = Any
// <L>.dealias eq <L>
// <L>.etaExpand == <[X]Any>

I'm not sure what conclusions to draw from all of this. Maybe a split AliasTypeRef into a HK and regular version?

I'm running a test now to see with:

    final def typeParamsMatchArgs  = if (typeParamsMatchArgs0) true
                                     else if (isHigherKinded && args.isEmpty) false
                                     else { debugwarn(s"$this.typeParamsMatchArgs = false for non-higher-kinded type"); false}

to see if there are any ground type refs that that get into this spot.

[scabug]

@adriaanm said:
I thought we used a PolyType to denote the expected kind. It looks like it gets normalized to the AliasTypeRef, which is/was necessary for higher-order subtyping to work.

[scabug]

@paulp said:
Hey, we're only half a decade overdue to have the expected Kind denoted by something which has a name containing "Kind". I swear sometimes we program like the only available data type is "String".

[scabug]

@retronym said:
Switching the fix version back to 2.10.1, as I think was always intended. We're still nutting out the details of what fix to apply over in the comments of the GitHub PR.

[scabug]

@gkossakowski said:
Elevated to blocker as it blocks 2.10.1 release.

[scabug]

@adriaanm said:
scala/scala#2167