Apparent "regression" between 3.4.0 RC1 and RC4 around recursive given defn

Question
1

I experimented with upgrading a codebase to 3.4.0 RC4 that previously was compiling OK on RC1.

I hit a new compiler error in a recursive given definition that compiles fine under RC1. The code in question is a clause in the definition of an cats.kernel.Order[circe.io.Json] instance (alas an ordering is not defined by Circe out of the box).

  given jsonOrder: Order[Json] = Order.from:
    case (IsJsonObj(a), IsJsonObj(b)) => jsonObjOrder.compare(a, b)
    case (IsJsonString(a), IsJsonString(b)) => Order[String].compare(a, b)
    case (IsJsonNumber(a), IsJsonNumber(b)) => jsonNumberOrder.compare(a, b)
    case (IsJsonBoolean(a), IsJsonBoolean(b)) => Order[Boolean].compare(a, b)
    case (IsJsonArray(a), IsJsonArray(b)) => Order[Vector[Json]].compare(a, b)
    case (IsJsonNull(), IsJsonNull()) => 0
    case (a, b) => jsonSubtypeTag(a) - jsonSubtypeTag(b)

The error is in Order[Vector[Json]].compare(a, b):

[error]    |I found:
[error]    |
[error]    |    cats.kernel.Eq.catsKernelOrderForVector[io.circe.Json](
[error]    |      /* missing */summon[cats.kernel.Order[io.circe.Json]])
[error]    |
[error]    |But no implicit values were found that match type cats.kernel.Order[io.circe.Json].

To resolve this code will recursively need the instance being defined, when building an instance of Order[Vector[Json]].

I noticed RC2 had some changes that look relevant. Presumably, recursive givens are still supported (?), but I may need to set some compiler flags (current "-source", "future") or other tweaks to port this code to RC4…?

Is someone familiar with the changes to recursive givens able to advise? Or if this ought to “just work”, I can file an issue with a bigger self-contained example…

2

It would be good to file an issue for this. Hard to see what might be the cause with the info given so far.

3

Hi Martin,

Here’s a self-contained scala-cli example below. I had source future On so it simply reported an error, but with that Off it gives more details:

[warn] Result of implicit search for cats.kernel.Order[io.circe.Json] will change.
[warn] Current result recursive_given.Example.jsonOrder will be no longer eligible
[warn]   because it is not defined before the search position.
[warn] Result with new rules: No Matching Implicit.
[warn] To opt into the new rules, compile with `-source future` or use
[warn] the `scala.language.future` language import.
[warn]
[warn] To fix the problem without the language import, you could try one of the following:
[warn]   - use a `given ... with` clause as the enclosing given,
[warn]   - rearrange definitions so that recursive_given.Example.jsonOrder comes earlier,
[warn]   - use an explicit argument.
[warn] This will be an error in Scala 3.5 and later.
[warn]     case (IsJsonArray(a), IsJsonArray(b)) => Order[Vector[Json]].compare(a, b)

The suggestion I find confusing in above is to rearrange definitions so that recursive_given.Example.jsonOrder comes earlier… because the missing implicit happening is inside the definition of jsonOrder.

Is it because the jsonOrder isn’t used directly in resolving Order[Vector[Json]], but indirectly via other implict params?

//> using scala 3.4.0
//> using dep io.circe::circe-core:0.14.6
package recursive_given

import cats.*
import io.circe.*
//import scala.language.future

object Example:

  given Ordering[Json] = Order.catsKernelOrderingForOrder[Json]

  given jsonOrder: Order[Json] = Order.from:
    case (IsJsonObj(a), IsJsonObj(b)) => jsonObjOrder.compare(a, b)
    case (IsJsonString(a), IsJsonString(b)) => Order[String].compare(a, b)
    case (IsJsonNumber(a), IsJsonNumber(b)) => jsonNumberOrder.compare(a, b)
    case (IsJsonBoolean(a), IsJsonBoolean(b)) => Order[Boolean].compare(a, b)
    case (IsJsonArray(a), IsJsonArray(b)) => Order[Vector[Json]].compare(a, b)
    case (IsJsonNull(), IsJsonNull()) => 0
    case (a, b) => jsonSubtypeTag(a) - jsonSubtypeTag(b)

  given jsonObjOrder: Order[JsonObject] = Order.from:
    case (obj1, obj2) => obj1.toIterable.iterator.compareWith(obj2.toIterable.iterator)

  given jsonNumberOrder: Order[JsonNumber] = Order.from:
    case (jn1, jn2) => jn1.toDouble.compare(jn2.toDouble)

  //arbitrarily, more complex json structures have a "bigger" ordering than simpler ones
  inline def jsonSubtypeTag(json: Json): Int = (json: @unchecked) match
    case IsJsonNull() => 0
    case IsJsonBoolean(_) => 1
    case IsJsonNumber(_) => 2
    case IsJsonString(_) => 3
    case IsJsonArray(_) => 4
    case IsJsonObj(_) => 5

  extension [A](i1: Iterator[A])
    def compareWith(i2: Iterator[A])(using oa: Ordering[A]): Int =
      @annotation.tailrec
      def loop: Int =
        (i1.hasNext, i2.hasNext) match
        case (false, false) => 0
        case (false, true) => -1
        case (true, false) => 1
        case (true, true) =>
          val c = oa.compare(i1.next(), i2.next())
          if c == 0 then loop
          else c
      loop

  object IsJsonObj:
    def unapply(json: Json): Option[JsonObject] = json.asObject
  object IsJsonArray:
    def unapply(json: Json): Option[Vector[Json]] = json.asArray
  object IsJsonNumber:
    def unapply(json: Json): Option[JsonNumber] = json.asNumber
  object IsJsonBoolean:
    def unapply(json: Json): Option[Boolean] = json.asBoolean
  object IsJsonString:
    def unapply(json: Json): Option[String] = json.asString
  object IsJsonNull:
    def unapply(json: Json): Boolean = json.isNull
4

I pursued the other suggestion use an explicit argument. I successfully tied the knot, but the code reads rather awkwardly:

    case (IsJsonArray(a), IsJsonArray(b)) => Order[Vector[Json]](
      using cats.kernel.instances.all.catsKernelStdOrderForVector[Json](using jsonOrder)).compare(a, b)

It would be nice for future Scala to find ways not to do this; such instances were not named to be called explicitly.

5

The issue is that there is a high risk that synthesized givens in this style will lead to a infinite recursion at runtime. Not for the code you showed, but for code similar to it. That’s why we will tighten the screws and disallow implicit forward references in alias givens.

To fix this, you could also try to reformulate jsonOrder a given ... with. Maybe that’s less overhead than the explicit references.