infinite loop when evaluating a recursive given definition

[Swoorup]

When running a program which consumes opaque types as follows, it appears to be stuck on an infinite loop. Not sure what is going on here.

Minimized code

object Prices {
  opaque type Price = BigDecimal

  object Price{
    given Ordering[Price] = summon[Ordering[BigDecimal]]
  }

}

extension[K,V] (m1: Map[K,V]) def computeDiff(m2: Map[K,V])(using Ordering[K])(using orderAsc: Boolean = true): Unit = println("Ok....")

import Prices._
@main def mainz = {
    println("begin")
    val result = Map.empty[Price,Int].computeDiff(Map.empty[Price,Int])
    println(s"end $result")
}

Scastie link: https://scastie.scala-lang.org/ajEagvzvTbitmzbqFt0Oxw

Output

begin

Expectation

Should successfully print the following:

begin
Ok....
end

This works if the Price was swapped with BigDecimal in the line

  val result = Map.empty[Price,Int].computeDiff(Map.empty[Price,Int])

This is happening on 3.0.0-M3

[som-snytt]

WFM

➜  snips scalac -version
Scala compiler version 3.0.0-M3 -- Copyright 2002-2020, LAMP/EPFL
➜  snips scalac -d /tmp i10947.scala
➜  snips scala -classpath /tmp mainz
begin
Ok....
end ()

Sorry I didn't look closely. Corrected...

➜  snips cat i10947.scala

object Prices:
  opaque type Price = BigDecimal

  object Price:
    given Ordering[Price] = summon[Ordering[BigDecimal]]

  extension[K,V] (m1: Map[K,V]) def computeDiff(m2: Map[K,V])(using Ordering[K])(using orderAsc: Boolean = true): Unit =
    println("Ok....")
end Prices

import Prices._

@main def mainz =
  println("begin")
  val result = Map.empty[Price,Int].computeDiff(Map.empty[Price,Int])
  println(s"end $result")

[griggt]

Seems like the issue occurs on Scastie but not locally (works for me too)

[Swoorup]

@som-snytt @griggt please remove the indentation on the import and mainz block, i.e It appears it should not be on the same block as where the opaque type is defined for the issue to occur.

It should occur then. I'll update the example to use curlies for clarity.

import Prices._

@main def mainz =
  println("begin")
  val result = Map.empty[Price,Int].computeDiff(Map.empty[Price,Int])
  println(s"end $result")

[griggt]

Still works for me locally, formatted with the curly braces (I had it indented as you intended without them also).

I am able to reproduce it on Scastie, however.

EDIT: nvm, it hangs at runtime, not compile time

[julienrf]

object Prices {
  opaque type Price = BigDecimal

  object Price{
    given Ordering[Price] = summon[Ordering[BigDecimal]]
  }

}

What happens here is that you have a recursive given definition. summon[Ordering[BigDecimal]] returns Price.given_Ordering_Price since the opaque type Price is equal to BigDecimal at that place.

What you need to do is to summon the Ordering[BigDecimal] instance at a place where the type Price is opaque (not transparent), or at a place where Price.given_Ordering_Price is not in scope.

It seems that the following works fine:

object Prices {
  opaque type Price = BigDecimal

  private val orderingBigDecimal = summon[Ordering[BigDecimal]]
  object Price{
    given Ordering[Price] = orderingBigDecimal
  }

}

extension[K,V] (m1: Map[K,V]) def computeDiff(m2: Map[K,V])(using Ordering[K])(using orderAsc: Boolean = true): Unit = println("Ok....")

import Prices._
@main def mainz =
    println("begin")
    val result = Map.empty[Price,Int].computeDiff(Map.empty[Price,Int])
    println(s"end $result")

https://scastie.scala-lang.org/6gIRy2nwSLGcsIAvlvTVKw

[julienrf]

I am not sure what we should do about this problem. I think the current behavior is expected. I don’t think we can reliably implement a detection mechanism for such loops at compilation time so I’m closing the issue. Feel free to re-open it if I miss something.

[Swoorup]

It seems like an easy pitfall to fall into, but then again I am not sure how to best prevent these kind of issue myself.

I wonder there is any chance to eagarly evaluate givens for opaque type at compile time? I don't know if thats possible.

[julienrf]

This is not specific to opaque types, the same issue can happen with regular type aliases, abstract type members, etc. It is easy to construct a recursive instance, but it is known to be a hard problem to detect such constructions at compile-time. Also, not all the recursive given definitions are wrong. Some of them are correct (this is how we define instances for recursive data types).

[Swoorup]

😦 That is a bit worrying, hope we can think of something in the future.

[liufengyun]

We could enhance the initialization check to check for possible non-termination of lazy fields. A related issue #9668.

[tel]

What's interesting about this one is that one common use case is derivation (a la Haskell's generalize newtype deriving). Would it be possible to hook something into the derivation mechanism?