What does 'do not conform to trait Builder's type parameter bounds' mean in scala?

Question

I have the following simple program that defines 2 identical upper bounds for type parameter and abstract type alias respectively:

package scala.spike.typeBoundInference

object Example1 {
  trait Domain {
  }

  trait Impl {

    type DD <: Domain
    type GG <: StaticGraph[DD]

    type A1
    type A2
    type A3
    // ... this type list can go very long
    // so inlining them as generic type parameters is impossible


    final type Builder = StaticGraph.Builder[DD, GG]
  }

  trait DSL[I <: Impl] {

    val impl: StaticGraph.Builder[I#DD, I#GG]
  }

  trait StaticGraph[T <: Domain] {}

  object StaticGraph {

    trait Builder[D <: Domain, G <: StaticGraph[D]] {}

  }
}

However, scala refuse to compile it:

Error:(16, 27) type arguments [I#DD,I#GG] do not conform to trait Builder's type parameter bounds [D <: scala.spike.typeBoundInference.Example1.Domain,G <: scala.spike.typeBoundInference.Example1.StaticGraph[D]] val impl: StaticGraph.Builder[I#DD, I#GG]

What could possibly go wrong here?

DD <: Domain check
GG <: StaticGraph[DD] check

there is no reason scala think it is unsafe.

In the meantime, I found that if class StaticGraph[T] is declared as covariant scala compiler will run successfully. This is even worse (for some reason StaticGraph[T] has to be invariant), as type bound GG <: StaticGraph[DD] means that if type DD is determined, then GG is a subclass of StaticGraph[DD], but not necessary a subclass of StaticGraph[Domain], which is exactly what I want here.

UPDATE 1: I've read all the answers and comments and somehow got the impression that the core reason is that there is no guarantee that for any instance i of Impl, the type bound only guarantee that type

i.DD <:< Impl#DD and Imp#GG <:< StaticGraph[Impl#DD]

but not StaticGraph[i.DD] <:< StaticGraph[Impl#GG]

thus i.GG <:< StaticGraph[i.DD] is also not guaranteed.

However, I've done a quick experiment to verify this idea, which turns out to be not ture:

object Example1 {

  trait Domain {}
  class D1 extends Domain {}

  trait Impl {

    type DD <: Domain
    type GG <: StaticGraph[DD]
  }

  class StaticGraph[T <: Domain] {}

  object Impl1 extends Impl {

    type DD = D1
    type GG = StaticGraph[Domain]
  }

  //or this:

  val impl = new Impl {

    type DD = D1
    type GG = StaticGraph[Domain]
  }
}

In this case compiler throw an error:

Error:(19, 10) overriding type GG in trait Impl with bounds <: scala.spike.TypeBoundInference.Example1.StaticGraph[scala.spike.TypeBoundInference.Example1.Impl1.DD]; type GG has incompatible type type GG = StaticGraph[Domain]

If you think the type constraint doesn't hold for some instances, could you give me counter example?

UPDATE2: turns out that according to the answer, this is true:

i.GG <:< StaticGraph[i.DD]

but this maybe false:

Impl#GG <:< StaticGraph[Impl#GG].

so in the context of DSL this may also be false:

I#GG <:< StaticGraph[I#GG] (3)

But this is only part of the puzzle, to prove that it is type unsafe, we have to construct a counter example of DSL[I] that invalidates condition (3). So the old question remains: is it possible to construct a counter example?

Shorter example: trait StaticGraph[T]; trait Impl { type DD; type GG <: StaticGraph[DD] }; def f[I <: Impl]: Unit = { implicitly[I#GG <:< StaticGraph[I#DD]] } — Andrey Tyukin
Nice! your example is much better, as the error information directly shows the irony: Error:(12, 40) Cannot prove that I#GG <:< scala.spike.TypeBoundInference.Example3.StaticGraph[I#DD] — tribbloid
@LuisMiguelMejíaSuárez yeah it is a valid bypass, but they are the same thing, so theoretically I don't have to do it. — tribbloid
They aren't the same thing: I#Builder is (approximately) StaticGraph.Builder[i.DD, i.GG] forSome { val i: I }, and StaticGraph.Builder[I#DD, I#GG] is StaticGraph.Builder[i1.DD forSome { val i1: I }, i2.GG forSome { val i2: I} ]. — Alexey Romanov

Alexey Romanov Alexey Romanov · Accepted Answer · 2019-03-12T22:55:07

What could possibly go wrong here?

GG <: StaticGraph[DD] check

By declaring type GG <: StaticGraph[DD] you establish a relationship between member types (it's the same as <: StaticGraph[this.DD]). This means that you need to consider instances of Impl.

For any val i: Impl, you have i.DD <: Domain and i.GG <: StaticGraph[i.DD]. You also have i.DD <: I#DD. But you don't have i.DD =:= I#DD! So StaticGraph[i.DD] and StaticGraph[I#DD] are not related (for invariant StaticGraph). And so neither are i.GG (or I#GG) and StaticGraph[I#DD].

To make it compile, you need to require that all i.DD are the same (which also guarantee i.DD =:= I#DD). And there is a way to do that:

trait DSL[T <: Domain, I <: Impl { type DD = T } ]

will make the code compile (without any other changes).

If StaticGraph is covariant, the relationships work out:

I#GG =:= (kind of)
i.GG forSome { val i: I } <:
StaticGraph[i.DD] forSome { val i: I } <:
StaticGraph[I#DD] forSome { val i: I } =:=
StaticGraph[I#DD]

What does 'do not conform to trait Builder's type parameter bounds' mean in scala?

2 Answers