Type inference for dependent type class breaks (regression from Scala 2)

[LPTK]

Minimized code

infix abstract class TupleOf[T, +A]:
  type Mapped[+A] <: Tuple
  def map[B](x: T)(f: A => B): Mapped[B]

object TupleOf:
  
  given TupleOf[EmptyTuple, Nothing] with
    type Mapped[+A] = EmptyTuple
    def map[B](x: EmptyTuple)(f: Nothing => B): Mapped[B] = x
  
  given [A, Rest <: Tuple](using tup: Rest TupleOf A): TupleOf[A *: Rest, A] with
    type Mapped[+A] = A *: tup.Mapped[A]
    def map[B](x: A *: Rest)(f: A => B): Mapped[B] =
      (f(x.head) *: tup.map(x.tail)(f))

def foo[T](xs: T)(using tup: T TupleOf Int): tup.Mapped[Int] = tup.map(xs)(_ + 1)

@main def test =
  foo(EmptyTuple): EmptyTuple // ok
  foo(1 *: EmptyTuple): Int *: EmptyTuple // nope

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

It works in Scala 2 : https://scastie.scala-lang.org/XTg2Thj5QYSyEzSNL5xUpQ

Output

Found:    ?1.Mapped[Int]
Required: Int *: EmptyTuple
where:    ?1 is an unknown value of type TupleOf.given_TupleOf_A_A[Int, EmptyTuple.type]

Expectation

Compiles. The Mapped type of any TupleOf.given_TupleOf_A_A[Int, EmptyTuple.type] value is [A] =>> A *: EmptyTuple. So ?1.Mapped[Int] should be reduced to Int *: EmptyTuple.

[odersky]

It looks that this exhibits a difference in how we deal with capture conversion. Scala 2 uses existential types for that which are unavailable in Scala 3. This could make up the difference. If that's the case then I am not sure something can be done about this.

[LPTK]

I found a temporary workaround:

  given [A, Rest <: Tuple, T <: Rest TupleOf A](using tup: T): TupleOf[A *: Rest, A] with
    type Mapped[A] = A *: tup.Mapped[A]
    def map[B](x: A *: Rest)(f: A => B): Mapped[B] =
      (f(x.head) *: tup.map(x.tail)(f))

The problem was that the precise type of tup was not preserved in the original program. So this issue is related to #3920 and its successor #3964 (both opened by @liufengyun).

I'd say the issue is more pronounced here than in the general case, because dependent givens "feel like" dependent methods, not classes, so we don't expect that they would lose information about their parameter types.

I wonder if something could be done about this issue, at least for the special case of given. Dependent implicits are quite important, and they somehow work in Scala 2.

[smarter]

So in other words the issue is that:

  given [A, Rest <: Tuple](using tup: Rest TupleOf A): TupleOf[A *: Rest, A] with
    type Mapped[+A] = A *: tup.Mapped[A]
    def map[B](x: A *: Rest)(f: A => B): Mapped[B] =
      (f(x.head) *: tup.map(x.tail)(f))

is desugared into:

  class given_TupleOf_A_A[A, Rest <: Tuple](using val tup: Rest TupleOf A) extends TupleOf[A *: Rest, A] {
    type Mapped[+A] = A *: tup.Mapped[A]
    def map[B](x: A *: Rest)(f: A => B): Mapped[B] =
      (f(x.head) *: tup.map(x.tail)(f))
  }
  implicit def given_TupleOf_A_A[A, Rest <: Tuple](using tup: Rest TupleOf A): TupleOf[A *: Rest, A] =
    new given_TupleOf_A_A(using tup)

which loses any information about tup in the result type, whereas you'd like instead to have:

  implicit def given_TupleOf_A_A[A, Rest <: Tuple](using tup: Rest TupleOf A): TupleOf[A *: Rest, A] { type Mapped[+A] = A *: tup.Mapped[A] } =
    new given_TupleOf_A_A(using tup).asInstanceOf

where the asInstanceOf is needed because we don't have a solution for #3964

[LPTK]

@smarter alternatively, would it make sense to just automatically add type parameters for each given parameter?

  class given_TupleOf_A_A[A, Rest <: Tuple, tup <: Rest TupleOf A](using val tup: tup) extends TupleOf[A *: Rest, A] {
    type Mapped[+A] = A *: tup.Mapped[A]
    def map[B](x: A *: Rest)(f: A => B): Mapped[B] =
      (f(x.head) *: tup.map(x.tail)(f))
  }
  implicit def given_TupleOf_A_A[A, Rest <: Tuple](using tup: Rest TupleOf A): given_TupleOf_A_A[A, Rest, tup.type] =
    new given_TupleOf_A_A(using tup)

[smarter]

Not sure, that would mean the generated given classes could appear in public signatures due to inference whereas now they're mostly hidden.

[LPTK]

@smarter the generated given_* classes are most definitely not hidden. They appear in error messages, and you can even write things like new TupleOf.given_TupleOf_A_A. This is by design, as it's often useful that the refinements present in the class be exposed to the code that uses it (as opposed to being hidden behind an upcast to, here, TupleOf[A *: Rest, A] ).

[odersky]

Instead of fiddling with the encoding I'd rather like us to take the plunge and work towards a solution of #3964.

[cchantep]

Maybe related, considering:

import scala.deriving.Mirror

class Foo(val s: String)

object Foo {

  given Mirror.ProductOf[Foo] = new Mirror.Product {
    type MirroredType = Foo
    type MirroredElemTypes = Tuple1[String]
    type MirroredMonoType = Foo
    type MirroredLabel = "Foo"
    type MirroredElemLabels = Tuple1["s"]

    def fromProduct(p: Product): MirroredMonoType =
      new Foo(p.productElement(0).asInstanceOf[String])
  }
}

def test[T <: *:[_, EmptyTuple]]: Unit = println("ok")

Then test[Foo.given_ProductOf_Foo.MirroredElemLabels] raises the following error

-- [E057] Type Mismatch Error: -------------------------------------------------
1 |test[Foo.given_ProductOf_Foo.MirroredElemLabels]
  |                             ^
  |Type argument Foo.given_ProductOf_Foo.MirroredElemLabels does not conform to upper bound ? *: EmptyTuple

Whereas:

test[Tuple1["s"]]
// ok

If the given instance is defined using non-anonymous class, it's ok.

import scala.deriving.Mirror

class Foo(val s: String)

object Foo {

  final class FooProduct extends Mirror.Product {
    type MirroredType = Foo
    type MirroredElemTypes = Tuple1[String]
    type MirroredMonoType = Foo
    type MirroredLabel = "Foo"
    type MirroredElemLabels = Tuple1["s"]

    def fromProduct(p: Product): MirroredMonoType =
      new Foo(p.productElement(0).asInstanceOf[String])
  }

  given pof: FooProduct = new FooProduct
}

def test[T <: *:[_, EmptyTuple]]: Unit = println("ok")

test[Foo.pof.MirroredElemLabels]
// ok

[bishabosha]

given Mirror.ProductOf[Foo] =

this type will not carry the refinements of the right hand side, you need to give them explicitly:

given (Mirror.ProductOf[Foo] {type MirroredElemLabels = Tuple1["s"]}) = new Mirror.Product {

[odersky]

@mbovel Adding to your pile since it's about dependent classes. Not expecting a fix anytime soon though.