How to implement usage site variance in implicits?

Question

Large redaction of the original question: now I present the whole code upfront, without showing the variants explaining my motivation. Apologies for the confusion.

I need a simple type class implementing a projection on one of type's member types - for the purpose of this example lets make it a straightforward cast:

trait Subject {
    type E
    type Const 
}

object Subject {
    implicit def projection :Projection[Subject] { type Project[X] = Subject { type E = X } } = ???
}

abstract class Projection[S <: Subject] {
    type Project[X] <: Subject { type E = X }
}

implicit class ProjectSubject[S <: Subject](private val self :S) extends AnyVal {
    def project[X](implicit p :Projection[S]) :p.Project[X] = ???
}

class Box[X] extends Subject { type E = X }

object Box {
    implicit def projection[A] :Projection[Box[A]] { type Project[X] = Box[X] } = ???
}

class Adapter[S <: Subject] extends Subject { type E = S#E }

object Adapter {
    implicit def adapterProjection[S <: Subject](implicit p :Projection[S])
        :Projection[Adapter[S]] { type Project[X] = Adapter[p.Project[X]] } = ???
}

val res = new Adapter[Box["E"]].project["F"]

In the example above, it is clear that the projection should be recursive, with Subject subclasses declaring their own rules. Obviously, I'd like the projection to be contravariant in effect:

class Specific extends Adapter[Box["E"]]
val spec = (new Specific).project["F"] //doesn't compile

If Specific does not provide its own projection, the one for Adapter should be used, with the last expression evaluating to Adapter[Box["F"]]. This works nicely if I declaer Projection[-S <: Subject], but the problem is that I need the projections to preserve some properties, here expressed as the Const member type:

class Projection[S <: Subject] { 
    type Project[X] <: Subject { type E = X; type Const = S#Const }
}

I dropped this constraint from the code above for clarity, as it doesn't contribute to the problem.

In the previous example, the compiler will complain about the lack of an implicit Projection[Specific], without trying to upcast the value. How to make it compile with usage site variance?

Not with existentials:

implicit class ProjectSubject[S <: Subject](private val self :S) extends AnyVal {
    def project[X](implicit p :Projection[_ >: S <: Subject]) = ???
}

My guess was that the wildcard here is equivalent to Subject and no implicits other than Projection[Subject] will be searched for from the compiler -Xlog-implicits logs of the unabridged problem (which had a large Subject hierarchy with more implicit projection declarations).

I then tried the trick with an intermediate contravariant implicit, which sometimes works:

abstract class ProjectionAvailable[-S <: T, T <: Subject] //extends (S => T)
implicit def ProjectionAvailable[S <: Subject](implicit p :Projection[S]) :ProjectionAvailable[S, S] = ??? //(s :S) => s

implicit def ProjectionSubject[S <: T, T <: Subject](s :S)(implicit witness :ProjectionAvailable[S, T]) =
    new ProjectionSubject[T](s)

class ProjectionSubject[S <: Subject](private val self :S) extends AnyVal {
    def project[X](implicit p :Projection[S]) :p.Project[X] = p.asInstanceOf[p.Project[X]]
}

This looked promising, but unfortunately the compiler goes about this exactly as before: looks at the available implicit, instantiates type parameters as ProjectionAvailable[Specific, T] and complains for the lack of Projection, without taking advantage of its contravariance. I tried a variant with

class ProjectionAvailable[S <: T, T <: Subject]

without any real difference apart for a more clear error. I tried integrating the ProjectionAvailable into Projection, but it also changed nothing:

class Projection[-S <: T, T] { /* as before */ }
 

My hunch is that it probably is doable, but requires crafty guiding the compiler by hand in type inference and for now I am out of new avenues to explore.

Answer 1

I can't reproduce behavior you mentioned (that's why I asked in comments how you test that def project[X](implicit p :Projection[_ >: S <: Subject]) = ??? or approach with ProjectionAvailable do not work for you).

With your approach with existential Projection in ProjectSubject I additionally defined Projection[Specific] and the code doesn't compile with error

Error: ambiguous implicit values:
 both value specificProjection in object App of type App.Projection[App.Specific]{type Project[X] = App.Specific}
 and method adapterProjection in object App of type [S <: App.Subject](implicit p: App.Projection[S]): App.Projection[App.Adapter[S]]{type Project[X] = App.Adapter[p.Project[X]]}
 match expected type App.Projection[_ >: App.Specific <: App.Subject]
  val spec = (new Specific).project["F"]

so the implicit for Projection[Specific] is among candidates and I can't see how the following can be true

The wildcard here is equivalent to Subject and no implicits other than Projection[Subject] will be searched for.

If I make adapterProjection of lower priority than my additional implicit Projection[Specific] then

println(scala.reflect.runtime.universe.reify{
  (new Specific).project["F"]
}.tree)

prints

App.this.ProjectSubject(new App.this.Specific()).project["F".type](App.this.Implicits.specificProjection)

so it's Projection[Specific] that is selected.

Scala 2.13.3.

https://scastie.scala-lang.org/Ts9UOx0aSfWuQJNOoVnSAA

Behavior for your original contravariant Projection (without type type Const) and the first ProjectSubject (with non-existential Projection) is the same.

(My answer in In scala 2.13, how to use implicitly[value singleton type]? can be relevant.)

By the way, with invariant Projection and ProjectionAvailable I don't have to prioritize implicits and Projection[Specific] is selected.

https://scastie.scala-lang.org/nePYqjKGSWm8IRGLmYCwAA

And when I don't define additional implicit Projection[Specific] your approach with existential Projection seems to work, adapterProjection is selected. What's wrong with this behavior?

https://scastie.scala-lang.org/GiLoerYgT0OtxKyechezvA