Regression in implicit search in mixed implicit/givens sources

[WojciechMazur]

Extracted from discussion in #21226 introducing problems

@EugeneFlesselle this now causes a warning under -source:3.5 (so also in 3.5.x backports) in https://github.com/scala/scala3/blob/a64c2956f83f8dc53c0bfd7707df4a6e27cd0796/tests/pos/not-looping-implicit.scala
I wonder if this change might be more invasive than expected

-- Warning: /Users/wmazur/projects/sandbox/src/main/scala/test.scala:49:59 -----
49 |  implicit lazy val inputValueSchema: Schema[InputValue] = Schema.gen
   |                                                           ^^^^^^^^^^
   |Given search preference for Schema[List[InputValue]] between alternatives (Schema.gen : [A]: Schema[A]) and (Schema.listSchema : [A](implicit ev: Schema[A]): Schema[List[A]]) will change
   |Current choice           : the second alternative
   |New choice from Scala 3.6: the first alternative
   |----------------------------------------------------------------------------
   |Inline stack trace
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
23 |        val builder     = summonInline[Schema[t]].asInstanceOf[Schema[Any]]
   |                                       ^^^^^^^^^
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
34 |        lazy val fields           = recurse[m.MirroredElemLabels, m.MirroredElemTypes]()
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
38 |  inline given gen[A]: Schema[A] = derived[A]
   |                                   ^^^^^^^^^^
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
23 |        val builder     = summonInline[Schema[t]].asInstanceOf[Schema[Any]]
   |                                       ^
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
31 |        lazy val members     = recurse[m.MirroredElemLabels, m.MirroredElemTypes]()
   |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from test.scala:23
38 |  inline given gen[A]: Schema[A] = derived[A]
   |                                   ^^^^^^^^^^
    ----------------------------------------------------------------------------

I'll start the OpenCB to check it on the bigger number of codebases

Originally posted by @WojciechMazur in #21226 (comment)

This should not warn. The logic is wrong here. We should always prefer givens over implicits. The current logic makes implicits more general than givens, which means they will be chosen because we now prefer more general. It should probably be the reverse; we should make implicits more specific than givens.

EDIT: If we don't want to put this under a version flag (which would be cumbersome), we need to link in the choice with preferGeneral. Make implicits more specific than givens iff preferGeneral is true.

Originally posted by @odersky in #21226 (comment)

[WojciechMazur]

Related issue found in OpenCB build.

trait Context
class AutoDerivationMacro extends Reflection:
  implicit val context: Context = ???
  def usage = summon[Context] // error

trait Reflection:
  given Context = context
  val context: Context

yields warnings under -source:3.5 or errors in 3.6+:

[warn] ./src/main/scala/test.scala:4:30
[warn] Given search preference for Context between alternatives (AutoDerivationMacro.this.context : Context) and (AutoDerivationMacro.this.given_Context : Context) will change
[warn] Current choice           : the first alternative
[warn] New choice from Scala 3.6: none - it's ambiguous
[warn]   def usage = summon[Context] // error
[warn]                              ^

I belive a change to mitigate this issue in compiler codebase was done in the PR introducing the change

[WojciechMazur]

The issue seems to affect currently 17 projects in the Open CB:

Project	Version	Build URL	Notes
cchantep/acolyte	1.2.9	Open CB logs
com-lihaoyi/pprint	0.9.0	Open CB logs
foldables-io/skunk-tables	0.0.3	Open CB logs
ghostdogpr/caliban	2.8.1	Open CB logs
japgolly/microlibs-scala	4.2.1	Open CB logs
julianpeeters/dynamical	0.6.0	Open CB logs
lichess-org/lila	HEAD	Open CB logs
polyvariant/smithy4s-caliban	0.1.0	Open CB logs
sagifogel/proptics	0.5.2	Open CB logs
scala-cli/scala-cli-signing	0.1.14	Open CB logs
scala-tsi/scala-tsi	0.8.3	Open CB logs
thoughtworksinc/dsl.scala	2.0.0	Open CB logs
tkrs/mess	0.3.6	Open CB logs
tpolecat/doobie	1.0.0-RC5	Open CB logs
virtuslab/scala-cli-signing	0.2.3	Open CB logs
zeal18/zio-mongodb	0.10.4	Open CB logs
zio/zio-protoquill	4.8.5	Open CB logs

[odersky]

OK, looking at the original code before #21226 it looks to me that unless one of the participants was the Not given class, both alt1IsGiven and alt2IsGiven were always the same. Which means that given vs implicit did in fact not make a difference in prioritization. Since introducing the prioritization causes a lot of regressions, I think it's better we revert that change.

So this means the only given to de-prioritize is in fact Not. I wonder whether there is a more organic way to achieve that Not has low priority than threading alt{1/2}isImplicit through isAsGoodValueType?

[odersky]

While we are at it. Can we get rid of alt{1/2}isImplicit also here?

        if Feature.sourceVersion.isAtMost(SourceVersion.`3.4`)
            || oldResolution
            || alt1IsImplicit && alt2IsImplicit
        then
          // Intermediate rules: better means specialize, but map all type arguments downwards
          // These are enabled for 3.0-3.5, and for all comparisons between old-style implicits,
          // and in 3.5 and 3.6-migration when we compare with previous rules.

This test is now problematic since it violates the transitivity requirement. If we have a given G and implicits I1, I2 with
I1 < G < I2 where < means more specific, then from 3.6 on we pick I1 if we compare I1 with I2, yet pick I2 if we compare first I1 with G and then G with I2.

Previously this was not deemed a problem because we thought that the given G would always be picked over both I1 and I2. But that assumption was in fact false, because of the typo in isGiven.

[EugeneFlesselle]

OK, looking at the original code before #21226 it looks to me that unless one of the participants was the Not given class, both alt1IsGiven and alt2IsGiven were always the same.

This holds only in the case where alt1 is a given, otherwise alt1IsGiven and alt2IsGiven were always the same, i.e. there was a difference (before #21226) only if:

alt1.symbol.is(Given) && (alt1.symbol != defn.NotGivenClass) != (alt2.symbol != defn.NotGivenClass)

Which means there was even less of a difference and I would hence very much agree with

I think it's better we revert that change.

---

EDIT: even though alt1IsGiven != alt2IsGiven is rare (and might hence have had little influence), whether or not alt1.symbol.is(Implicit) had more of an impact: unless I'm mistaken, the behavior before #21226 was:

if alt1.symbol.is(Implicit) then old-style implicit comparison scheme between alts
else
  if (both alts are NotGivenClass) then old-style implicit comparison scheme between alts
  else if (neither alts are NotGivenClass) then new-style implicit comparison scheme between alts
  else the NotGivenClass alt loses

@odersky

[EugeneFlesselle]

This test is now problematic since it violates the transitivity requirement. If we have a given G and implicits I1, I2 with
I1 < G < I2 where < means more specific, then from 3.6 on we pick I1 if we compare I1 with I2, yet pick I2 if we compare first I1 with G and then G with I2.

Previously this was not deemed a problem because we thought that the given G would always be picked over both I1 and I2. But that assumption was in fact false, because of the typo in isGiven.

Making sure I understood correctly, this is now (after #21226) fixed right ?

[EugeneFlesselle]

While we are at it. Can we get rid of alt{1/2}isImplicit also here?

I don't see why not, I'll try it out

[odersky]

Making sure I understood correctly, this is now (after #21226) fixed right ?

Correct.

[odersky]

don't see why not, I'll try it out

But make a separate commit, so we can roll easily back of openCB chokes up.

[odersky]

I verified that both problems mentioned here will go away with #21305.

[EugeneFlesselle]

We went through a number of iterations (#21305, #21328, #21339) to mitigate the changes in resolution, which were warned about when compiling with -source:3.5, and merged the 3rd PR in the end.

I can confirm the original test case tests/pos/not-looping-implicit.scala for which this issue was opened is behaving as excepted (no warnings generated) for all source versions.
@WojciechMazur can you confirm we are also good w.r.t to CB, and we can close this issue?

[WojciechMazur]

I believe we can close it as completed.
The stats on how many warnings (mostly known and expected) and in which projects can be found in https://gist.github.com/WojciechMazur/e6f6946e1a51e3e12bb2ade5c568c429