[scala-user] Upper bound unification

[Jason Zaugg]

On Thu, Jul 30, 2015 at 4:41 AM Christophe Calvès <christop...@gmail.com> wrote:

 Hi all,

  Does anyone tried to fix the issue https://issues.scala-lang.org/browse/SI-4043 or have any idea about how to do it? I would be more than happy to give some help but my understanding of the compiler internals is still very low. Where could i find an up-to-date documentation of the type-checker code? Reading the code is very nice but progresses are slow without a map.

Hi Christophe,

Moving to scala-internals, feel free to post these sort of questions here!

I took a look at the bug again (which I reported many moons ago…) to see if I could offer you any pointers. I ended up going a little too far and produced a patch :)

Here’s the process I went through to find a fix.

I first took a look at when the compiler issued the error. It was in the refchecks phase (you can run -Xprint:all to see the ASTs after each compiler phase to see how far it gets).

I know that some kind conformance checking is performed after the main typechecking phase. This is done to avoid tripping cyclic errors during typechecking.

I then attached a debugger to the compiler and took a look at what types had made it into checkKindBounds0, which issues the error. These had already lost track of the fact that H1 = Int, so I turned my attention to what had happened earlier in typechecking itself.

I took a look at the typer debug output:

% scala -Ytyper-debug test.scala
...
-- GC[PA[Int]#Apply, Int] TYPEmode (site: object TypeParam)
    |-- PA[Int]#Apply NOmode (site: object TypeParam)
    |    |-- PA[Int] TYPEmode (site: object TypeParam)
    |    |    |-- Int TYPEmode (site: object TypeParam)
    |    |    |    \-> Int
    |    |    \-> TypeParam.PA[Int]
    |    [adapt] PA.this.Apply[A] is now a TypeTree([A <: H1]Any)
    |    \-> [A <: H1]Any
    |-- Int TYPEmode (site: object TypeParam)
    |    \-> Int
    \-> TypeParam.GC[[A <: H1]Any,Int]

Aha, we can see that typechecking the SelectFromTypeTree(<<PA[Int]>>, <<Apply>) node has been assigned a PolyType, representing an anonymous type function, but the bounds of its type parameter were not substituted.

Generic substitution in scalac is referred to as asSeenFrom. This forms the basis for the method memberType, and that is used by the typer in checkAccessible to compute the type of Select or SelectFromTypeTree AST nodes.

One can play around with the compiler API directly in the REPL’s :power mode.

Here’s an example:

scala> :power

scala> val Option_get = typeOf[Option[_]].member(TermName("get"))
Option_get: $r.intp.global.Symbol = method get

scala> Option_get.info
res16: $r.intp.global.Type = => A

scala> val prefix = typeOf[Option[Int]]
prefix: $r.intp.global.Type = Option[Int]

scala> prefix memberType Option_get
res17: $r.intp.global.Type = => Int

Back to our problem, so I tried:

scala> :paste -raw
// Entering paste mode (ctrl-D to finish)

object TypeParam {
  trait GC[K[_ <: H0], H0]

  trait PA[H1] {
    type Apply[A <: H1] = Any
  }
 }

// Exiting paste mode, now interpreting.

warning: there was one feature warning; re-run with -feature for details

scala> val pInt = typeOf[TypeParam.PA[Int]]
pInt: $r.intp.global.Type = TypeParam.PA[Int]

scala> val Apply = pInt member TypeName("Apply")
Apply: $r.intp.global.Symbol = type Apply

scala> pInt memberType Apply
res0: $r.intp.global.Type = [A <: H1]Any

Okay, that looks wrong to me.

Interestingly enough, a similar operation does give the result we want.

scala> pInt memberInfo Apply
res2: $r.intp.global.Type = [A <: Int]Any

Expanding the code for memberInfo, we see why:

scala> Apply.info
res10: $r.intp.global.Type = [A <: H1]Any

scala> res10 asSeenFrom (pre = pInt, clazz = Apply.owner)
res11: $r.intp.global.Type = [A <: Int]Any

Turning our attention back to the problem with memberType for now.

I suppose if you debugged through memberType a little, you’d find that it calls into etaExpand. I jumped straight to that method, as I knew that it was the code that converts AliasTypeRef-s to PolyTypes.

BTW, you can get a lower-level rendering of any tree or type with showRaw, that will reveal that res0 is a PolyType

scala> showRaw(res0)
res12: String = PolyType(List(TypeName("A")), TypeRef(ThisType(scala), scala.Any, List()))

We can form a TypeRef to apply from the given prefix and call etaExand on it directly.

scala> val ref = typeRef(pre = pInt, sym = Apply, args = Nil)
ref: $r.intp.global.Type = TypeParam.PA[Int]#Apply

scala> showRaw(ref)
res13: String = TypeRef(TypeRef(SingleType(ThisType(<empty>), TypeParam), TypeParam.PA, List(TypeRef(ThisType(scala), scala.Int, List()))), TypeName("Apply"), List())

scala> ref.etaExpand
res4: $r.intp.global.Type = [A <: H1]TypeParam.PA[Int]#Apply[A]

The implementation of eta expand:

    final override def etaExpand: Type = {
      // must initialise symbol, see test/files/pos/ticket0137.scala
      val tpars = initializedTypeParams
      if (tpars.isEmpty) this
      else typeFunAnon(tpars, copyTypeRef(this, pre, sym, tpars map (_.tpeHK))) // todo: also beta-reduce?
    }

The type parameters of the TypeRef here are just used directly as the type parameters of the eta-expanded PolyType. The prefix (PA[Int] in our running example) is ignored.

My patch creates a cloned set of symbols whose types have substituted with the prefix, and uses these instead as the type params of the anonymous type function. I found another spot in typechecker that was already doing this, so refactored to share the code.

I’ll need to get my proposal reviewed by Adriaan to see if it makes sense, if so we’ll get it Scala 2.12.

Hope this has been useful, despite being a tour through some pretty low-level areas of the compiler. Take a look at the Reflection Guide for a gentler introduction to the data structures used in the compiler. We are a bit lacking in more docs of the internals, but feel free to ask questions here or in our gitter channel.

​

-jason