Compiler ignores instance of typeclass and tries to derive it instead

[WojciechMazur]

Regression found in Open CB #4758 for wangzaixiang/wjson
Part of the 3.2.1-RC1 regressions tracker #15949

There seem to be 2 reasons why code now fails to compile:

1. In Scala 3.2.0 compiler used defined instance of given [T:JsValueMapper]: JsValueMapper[Map[String, T]] in 3.2.1 it tries to derive type class instead using given [T: JsValueMapper, CC[x] <: IterableOps[x, CC, CC[x]]]: Conversion[CC[T], JsArray]. See AST below
2. While deriving Map[String, Int] TypeTree.of[T].symbol where T=Tuple2[String, Int] returns NoSymbol

Compiler version

3.2.1-RC1

Minimized code

// test.scala
import scala.collection.IterableOps

enum JsValue:
    case JsNumber(value: Double|Long)
    case JsString(value: String)
    case JsArray(elements: Seq[JsValue])
    case JsObject(fields: Map[String, JsValue])
    
object JsValue:
  given [T: JsValueMapper]: Conversion[T, JsValue] = ???
  given [T: JsValueMapper, CC[x] <: IterableOps[x, CC, CC[x]]]: Conversion[CC[T], JsArray] = ???

trait JsValueMapper[T]:
  def toJson(t: T): JsValue

object JsValueMapper:
  inline given[T](using deriving.Mirror.ProductOf[T]): JsValueMapper[T] = ${JsValueMapperMacro.generateImpl[T]}

  given JsValueMapper[Int] = ???
  given JsValueMapper[String] = ???
  given [T:JsValueMapper]: JsValueMapper[Map[String, T]] = ???

extension [T: JsValueMapper](obj: T)
  inline def toJson: JsValue = summon[JsValueMapper[T]].toJson(obj)

@main def Test = 
  val works = Map("a"->1,"b"->2,"c"->3).toJson
  val fails = Map("a"->1,"b"->2,"c"->3): JsValue // error

// macro.scala
import scala.quoted.*
import scala.deriving.*

object JsValueMapperMacro:
  def generateImpl[T: Type](using Quotes): Expr[JsValueMapper[T]] =
    import quotes.reflect.*
    import JsValueMapper.*
    val sym = TypeTree.of[T].symbol // no symbol for Tuple2[String,Int]
    val module = Ref(sym.companionModule)
    ???

Output

[error] java.lang.AssertionError: assertion failed
[error]         at scala.runtime.Scala3RunTime$.assertFailed(Scala3RunTime.scala:11)
[error]         at scala.quoted.runtime.impl.QuotesImpl$reflect$Ref$.apply(QuotesImpl.scala:435)
[error]         at scala.quoted.runtime.impl.QuotesImpl$reflect$Ref$.apply(QuotesImpl.scala:434)
[error]         at JsValueMapperMacro$.generateImpl(macro.scala:9)
[error] 
[error]   val fails = Map("a"->1,"b"->2,"c"->3): JsValue // error
[error]               ^

AST in Scala 3.2.0

val fails: wjson.JsValue = 
   wjson.JsValue.given_Conversion_T_JsValue[Map[String, Int]](
     wjson.JsValueMapper.given_JsValueMapper_Map[Int](
       wjson.JsValueMapper.given_JsValueMapper_Int
     )
   ).apply(
     Map.apply[String, Int](
       [ArrowAssoc[String]("a").->[Int](1),
         ArrowAssoc[String]("b").->[Int](2)
       ,ArrowAssoc[String]("c").->[Int](3) : (String, Int)]*
     )
   ):wjson.JsValue

AST in Scala 3.2.1-RC1

val fails: wjson.JsValue = 
  wjson.JsValue.given_Conversion_CC_JsArray[(String, Int), 
    scala.collection.immutable.Iterable
  ](
    wjson.JsValueMapper.given_JsValueMapper_T[(String, Int)](
      new scala.runtime.TupleMirror(2).$asInstanceOf[
        
          scala.deriving.Mirror.Product{
            MirroredMonoType = (String, Int); 
              MirroredType = (String, Int)
            ; MirroredLabel = ("Tuple2" : String); 
              MirroredElemTypes = (String, Int)
            ; MirroredElemLabels = (("_1" : String), ("_2" : String))
          }
        
      ]
    )
  ).apply(
    Map.apply[String, Int](
      [ArrowAssoc[String]("a").->[Int](1),
        ArrowAssoc[String]("b").->[Int](2)
      ,ArrowAssoc[String]("c").->[Int](3) : (String, Int)]*
    )
  ):wjson.JsValue

Expectation

Should compile

[bishabosha]

I'm not sure what this has to do with type class derivation, isn't it implicit resolution that drives the method selected?

[anatoliykmetyuk]

This issue was picked for the Issue Spree No. 23 of 08 November 2022 which takes place in a week from now. @dwijnand, @nmcb, @markehammons will be working on it. If you have any insight into the issue or guidance on how to fix it, please leave it here.

[markehammons]

At this moment, we don't think this is a bug, but it's a definite change in implicit resolution order.

At issue are 4 givens:

1. given [T: JsValueMapper]: Conversion[T, JsValue] = ???
2. given [T: JsValueMapper, CC[x] <: IterableOps[x, CC, CC[x]]]: Conversion[CC[T], JsArray] = ???
3. inline given[T](using deriving.Mirror.ProductOf[T]): JsValueMapper[T] = ${JsValueMapperMacro.generateImpl[T]}
4. given [T:JsValueMapper]: JsValueMapper[Map[String, T]] = ???

Previously, given 1 was higher priority than given 2, but in Scala 3.2.1, 2 is being selected to convert Map[String,Int] to a JsValue. Since 2 has been chosen in Scala 3.2.1, given 3 is chosen instead of given 4, as T in this case is Tuple2[String,Int] rather than Map[String, Int].

The NoSymbol issue is a red-herring. Tuple2[String, Int] has no symbol, because it's an applied type rather than a concrete definition like Tuple2, String, or Int.

We may revisit this issue later to ascertain what exactly this new ordering is, and why 2 is chosen over 1 when converting Map[String, Int] to JsValue.

In the short term, the desired behavior can be achieved by shoving given 2 into a trait that is extended by object JsValue.

[markehammons]

After further review, it appears to me that the fact your code works in 3.2.0 at all is a bug in 3.2.0. As stated in the other comment, the inline given is chosen because the given given [T: JsValueMapper, CC[x] <: IterableOps[x, CC, CC[x]]]: Conversion[CC[T], JsArray] = ???(known from here on as given_Conversion_CC_JsArray) is chosen over the one you want to be chosen, given_Conversion_T_JsValue.

When given_Conversion_CC_JsArray is in use, the JsValueMapper being searched for is of type JsValueMapper[(String,Int)], which your inline given is the only possible match for.

One of the precedence rules for implicit resolution (or maybe we should be calling it context resolution now) is that the more specific context result is chosen. On a basic level, that means that given [T]: T = ??? won't ever be chosen over given Int = ??? when we're trying to summon an Int. Looking at given_Conversion_CC_JsArray and given_Conversion_T_JsValue, one might conclude that given_Conversion_T_JsValue is more specific, and will always be chosen first since it has only one type parameter. However, the number of type parameters is a red-herring. given_Conversion_CC_JsArray is more specific because it's result type matches less types in total compared to given_Conversion_T_JsValue. given_Conversion_T_JsValue can have as a result Conversion[T,JsValue] where T is any type which has a JsValueMapper defined for it and available in the current scope. given_Conversion_CC_JsArray can have as a result Conversion[CC[T], JsArray], where CC must be a type that implements IterableOps and T must be a type for which JsValueMapper is defined. The number of types that can match CC[T] is lower than the T is given_Conversion_T_JsValue. As a result, given_Conversion_CC_JsArray will always be higher precedence if both givens match the type to be summoned.

To see this in action:

given [A]: Option[A] = ???
given [B[_], A]: Option[B[A]] = ???

summon[Option[List[Int]]] 
//scala.NotImplementedError: an implementation is missing
//  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:344)
//  at rs$line$5$.given_Option_B(rs$line$5:1)
//  ... 32 elided

In this code, given_Option_B will always be chosen over given_Option_A when both can apply because B's return type is the more specific Option[B[A]].

Applying this principle to a facsimile of your code yields the same results:

import scala.collection.IterableOps                                                                                                                                                                                                                                                                                                                              

enum JsValue:
  case JsArray(a: Int)
object JsValue:
  given a[A]: Conversion[A, JsValue] = 
    println("a")
    ???
  given b[A, B[x] <: IterableOps[x, B, B[x]]]: Conversion[B[A], JsArray] = 
     println("b")
     ???

val x = Map(4 -> 3): JsValue //b is printed

This precedence applies on both Scala 3.2.0 and 3.2.1. It seems to be a bug in the context resolution of 3.2.0 that given_Conversion_T_JsValue was selected over the more specific given_Conversion_CC_JsArray.

In any case, like said before, if you want given_Conversion_CC_JsArray to be lower priority than given_Conversion_T_JsValue, you will need to force it by defining it inside a trait that the JsValue object extends.

[bishabosha]

@odersky do you agree with @markehammons summary? (TL;DR current 3.2.1 behaviour is correct)

[odersky]

@markehammons Thanks for the analysis, which looks correct to me. Nevertheless, it would be good to know what commit caused the difference since AFAIK implicit search rules have not changed in the recent past. Can we do a bisect?

[markehammons]

I will try to do a bisect this evening.

[markehammons]

926d5bd is the commit that caused the change between 3.2.0 and 3.2.1. Double checked that its parent commit still behaves the way the author expects, and it does.

[odersky]

@markehammons Thanks for digging this out! Very interesting. So it is due to a change in derivation after all, not a change to implicit resolution. The question is: Should we demand a fully defined type before going searching for a mirror? I think it's reasonable but maybe @bishabosha wants to comment, too.

[markehammons]

@odersky I'm not really the expert here, but I prefer the behavior of 3.2.1 here compared to 3.2.0. implicit search precedence is already really complicated, and one more exception that can change precedence so drastically makes the rules even harder to grasp.

Just in my opinion.

[bishabosha]

I think it was important to add fullyDefinedType because otherwise contravariant types could not be derived, in contrast this example still works when you "correct" the precedence.

perhaps there could be an alternative solution to the contravariance issue - but if indeed not using it causes incorrect implicit precedence then it seems 926d5bd fixed two bugs, not one

[odersky]

@bishabosha Yes, looks like this was the right move. I think wjson needs to be updated.