Compiler fails to spot disguised infinite recursion

[ShahOdin]

Compiler version

3.3.1

Minimized code

trait Encoder[A]:
  def encode(a: A): String

object Encoder:
  def summon[A](using encoder: Encoder[A]): Encoder[A] = encoder
  object Instances:
      given intEncoder: Encoder[Int] = _.toString

implicit class EncoderOps[A](value: A):
  def encoded(using encoder: Encoder[A]): String = encoder.encode(value)

opaque type Foo = Int
object Foo:
  val instance: Foo = 42
  import Encoder.Instances.given
  /*fails to compile: Infinite loop in function body Playground.Encoder.apply[Int](Playground.Foo.given_Encoder_Foo)*/
  //given Encoder[Foo] = Encoder.summon[Int]

  /*this is the same problem in disguise. compiler fails to spot it. it shouldn't!*/
  given Encoder[Foo]= a => EncoderOps[Int](a).encoded

  /*this works*/
  //given Encoder[Foo] = intEncoder

import Foo.given

println(s"Foo.instance is: ${Foo.instance.encoded}")

Output

hangs

Expectation

The first commented out impl is correctly picked up by the cmpiler as leading to infinite recursion. The impl left in code however, even though essentially equivalent, is not seen as suffering from the same problem. It should be easy to spot though: if the RHS refers to LHS, warn about it. incidentally, I noticed the following less convoluted version of the encoder impl above:

given Encoder[Foo] = a => Encoder.summon[Int].encode

outputs a different error:

Ambiguous given instances: both given instance intEncoder in object Instances and given instance given_Encoder_Foo in object Foo match type Playground.Encoder[Int] of parameter encoder of method summon in object Encoder

Ideally all three cases should have a unified behaviour imo.

[som-snytt]

The opaque alias should be made opaque to the rest of the example code:

object Domain:
  opaque type Foo = Int
  object Foo
end Domain
import Domain.Foo, Foo.given

The correct compiler error is:

Ambiguous given instances: both given instance intEncoder in object Instances and given instance given_Encoder_Foo in object Foo match type Encoder[Int] of parameter encoder of method summon in object Encoder

In Foo, Foo is just an alias for Int.

It's not necessary to import Foo.given because the implicit is discovered in the "companion" of the anchoring opaque type.

[ShahOdin]

It's not necessary to import Foo.given because the implicit is discovered in the "companion" of the anchoring opaque type.

Yes that was my expectation too but I was struggling getting it to work on scastie for some reason so I added the explicit import.

Not sure what to make of your response. Are you saying that this is a none issue?

[som-snytt]

Yes, I'd suggest asking at one of https://scala-lang.org/community/ where you can post a scastie.

[ShahOdin]

You have not addressed my point though. Perhaps this can be simplified further but the problem isn't about imports or opaque types.

[som-snytt]

I pointed out a couple of problems with your example, but maybe someone else can explain better.

[joroKr21]

It should be easy to spot though: if the RHS refers to LHS, warn about it.

It's not so simple. I might have a recursive data structure.

case class Tree(value: Int, children: List[Tree])
object Tree:
  given Encoder[Tree] = t => ??? // encode value and children

[ShahOdin]

I might have a recursive data structure.

Oh yeah good point! I know almost nothing about how the compiler works, but rulling out recursive structures should be easy enough, no?

I wonder if there are other more difficult examples. 🤔

[jchyb]

All 3 examples here compile and run without any unexpected runtime errors on main and the newest 3.4.0 nightly (3.4.0-RC1-bin-20240114-bfabc31-NIGHTLY). I'm unsure what changes fixed this and whether they will be backported to 3.3.2, so I am leaving this issue open for now.

[odersky]

Oh yeah good point! I know almost nothing how the compiler works, but rulling out recursive structures should be easy enough, no?

Maybe google "halting problem"?

[ShahOdin]

Maybe google "halting problem"?

I presume you mean the problem isn't just rulling out:

case class Tree(value: Int, children: List[Tree])

as was suggested: https://github.com/lampepfl/dotty/issues/19439#issuecomment-1890915126 but also:

case class Tree(value: Int, hasNestedTree: HasNestedTree)
case class HasNestedTree(tree: Tree)

and so on?

[odersky]

Yes, in general you can't spot all possible recursion scenarios. And it's tricky to have a conservative approximation.