Unexpected Illegal cyclic reference error since Scala 3.1.2

[jchyb]

Problem found when migrating sangria to Scala 3.

Compiler version

3.1.3-RC4
Runs correctly in 3.1.1, broken since 3.1.2, dottyCompileBisect gave me 40ae7ee as the first bad commit and 3.1.2-RC1-bin-20211217-b3ab102-NIGHTLY as the first bad release.

Minimized code

Problematic code:

//> using scala "3.1.3-RC4"

import scala.annotation.implicitNotFound

sealed trait Tagged[U]
type @@[+T, U] = T with Tagged[U] // intersection type seems to be the culprit, compiles if removed

@implicitNotFound(
  "Type ${Val} cannot be used as an input. Please consider defining an implicit instance of `FromInput` for it.")
trait FromInput[Val]

private object ScalarFromInput extends FromInput[Any] {}

implicit def coercedScalaInput[T]: FromInput[T @@ CoercedScalaResult] =
  ScalarFromInput.asInstanceOf[FromInput[T @@ CoercedScalaResult]]

implicit def optionInput[T](implicit ev: FromInput[T]): FromInput[Option[T]] = { // inline here fixes the issue
  ev.asInstanceOf[FromInput[Option[T]]]
}

trait CoercedScalaResult

sealed trait InputType[+T]

trait WithoutInputTypeTags[T] {
  type Res
}

object WithoutInputTypeTags {
  implicit def coercedArgTpe[T]: WithoutInputTypeTags[T @@ CoercedScalaResult] { type Res = T } =
    new WithoutInputTypeTags[T @@ CoercedScalaResult] {
      type Res = T
    }

  implicit def coercedOptArgTpe[T]
      : WithoutInputTypeTags[Option[T @@ CoercedScalaResult]] { type Res = Option[T] } =
    new WithoutInputTypeTags[Option[T @@ CoercedScalaResult]] {
      type Res = Option[T]
    }
}

case class OptionInputType[T](ofType: InputType[T]) extends InputType[Option[T]]

case class ScalarType[T](name: String) extends InputType[T @@ CoercedScalaResult]

val BooleanType: ScalarType[Boolean] = ScalarType[Boolean]("Boolean")

case class Argument[T](
  name: String, // seemingly important argument for this issue, compiles without it
  argumentType: InputType[_],
  fromInput: FromInput[_]
)

object Argument {
  inline def apply[T](name: String, argumentType: InputType[T])(implicit // inline here makes no difference, added for MacroHelp
      fromInput: FromInput[T],
      res: WithoutInputTypeTags[T]): Argument[res.Res] = { // returned type seems to be the issue here
    println(MacroHelp.showType[T]) // added for debugging
    Argument(name, argumentType, fromInput)
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    Argument("name", OptionInputType(BooleanType)) :: Nil // List.apply works correctly but still infers weird
  }
}

Macro I added to check inferred types:

import scala.quoted._
object MacroHelp {
  inline def showType[T] = ${showTypeImpl[T]}

  def showTypeImpl[T](using Quotes)(using t: Type[T]): Expr[String] = {
    import quotes.reflect.*
    val tpe = TypeRepr.of[T].show
    Expr(tpe)
  }
}

Output

[error] ./Cyclic.scala:66:52: Recursion limit exceeded.
[error] Maybe there is an illegal cyclic reference?
[error] If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
[error] A recurring operation is (inner to outer):
[error] 
[error]   subtype Tagged[CoercedScalaResult] <:< T
[error]     Argument("name", OptionInputType(BooleanType)) :: Nil // List.apply works correctly but still infers weird
[error]  

Expectation

The code should compile and run, like it does in 3.1.1. I added a macro that shows that inside of Argument.apply type T is inferred as scala.Option[Cyclic$package.@@[scala.Nothing, CoercedScalaResult] & Tagged[CoercedScalaResult]], whereas in scala 3.1.1 it was scala.Option[Test2$package.@@[scala.Any, CoercedScalaResult] & Tagged[CoercedScalaResult]]. However, my intuition tells me that the type should be scala.Option[Cyclic$package.@@[scala.Boolean, CoercedScalaResult]]]. It is also worth noting that since the code originally comes from Scala 2, the previously-compound-now-intersection type does not work like it did there, where it was possible to cast T to T @@ Tagged[SomeOtherType] - an operation on which Sangria’s internal type system relies heavily. Since that does not work as well, I imagine I will have to slightly rethink the api there for Scala 3, which may (or may not) make this issue less important. There are a lot of factors that make the problem appear and I had trouble minimizing code further, so I tried to add comments showing how things affect each other.

[Kordyjan]

Have you tried running it with the current nightly build? It might have the same root cause as one of the other regressions that have been fixed recently.

Also, 40ae7ee doesn't seem like something that could have introduced your problem.

[nicolasstucki]

Minimized

trait Tagged[U]
type WithTag[+T, U] = T & Tagged[U]

trait FromInput[Val]
implicit def coercedScalaInput[T]: FromInput[WithTag[T, Int]] = ???
implicit def optionInput[T](implicit ev: FromInput[T]): FromInput[Option[T]] = ???

trait WithoutInputTypeTags[T]
implicit def coercedOptArgTpe[T]: WithoutInputTypeTags[Option[WithTag[T, Int]]] = ???

trait InputType[+T]
class OptionInputType[T](ofType: InputType[T]) extends InputType[Option[T]]

type Argument[T]
def argument[T](argumentType: InputType[T])(implicit fromInput: FromInput[T], res: WithoutInputTypeTags[T]): Argument[Option[T]] = ???

def test = argument(OptionInputType(??? : InputType[WithTag[Boolean, Int]])) :: Nil

[error] ./Foo.scala:18:78: Recursion limit exceeded.
[error] Maybe there is an illegal cyclic reference?
[error] If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
[error] A recurring operation is (inner to outer):
[error] 
[error]   subtype Tagged[Int] <:< T
[error] def test = argument(OptionInputType(??? : InputType[WithTag[Boolean, Int]])) :: Nil // List.apply works correctly but still infers weird
[error]    

[griggt]

Bisecting the original example shows 3ab18a9 from #14026 as the first bad commit.

Unlike the original example, the minimized one fails to compile with 3.1.1.

They both fail to compile on latest nightly 3.2.0-RC1-bin-20220602-42b5941-NIGHTLY.

[odersky]

To see a bit more a changed the minimized example to unique type parameter names:

trait Tagged[U]
type WithTag[+TT, UU] = TT & Tagged[UU]

trait FromInput[Val]
implicit def coercedScalaInput[Tc1]: FromInput[WithTag[Tc1, Int]] = ???
implicit def optionInput[To](implicit ev: FromInput[To]): FromInput[Option[To]] = ???

trait WithoutInputTypeTags[TW]
implicit def coercedOptArgTpe[Tc]: WithoutInputTypeTags[Option[WithTag[Tc, Int]]] = ???

trait InputType[+TI]
class OptionInputType[TO](ofType: InputType[TO]) extends InputType[Option[TO]]

type Argument[TA]
def argument[Ta](argumentType: InputType[Ta])(implicit fromInput: FromInput[Ta], res: WithoutInputTypeTags[Ta]): Argument[Option[Ta]] = ???

def test = argument(OptionInputType(??? : InputType[WithTag[Boolean, Int]])) :: Nil

The root of the avoidance is that we run the map over List[B] with element to avoid $elem1 (which does not appear in List[B], but we don't know that.). AvoidMap instantiates type variables. I traced the instantiations with the following result:

INST B to Argument[Option[Option[Tc1 & Tagged[Int]]]]
INST Tc1 to WithTag[Tc, Int]
INST Tc to Tc1 & Tagged[Int]
INST Tc1 to WithTag[Tc, Int]
INST Tc to Tc1 & Tagged[Int]
INST Tc1 to WithTag[Tc, Int]
INST Tc to Tc1 & Tagged[Int]

So there's a recursion involving type variables Tc and Tc1. This happens even if level checking is turned off. So I am not what other part of #14026 has caused this.

[jchyb]

Fixed by #15642

[odersky]

Need to re-open because of #16344