Unapplicable implicit conversion in scope incorrectly masks applicable implicit conversion in outer scope.

[dwijnand]

EDIT: This no longer loops but emits an error when it shouldn't, see discussion starting at #13900 (comment)

Originally posted by @soronpo in #13878 (comment)

Minimized code:
https://scastie.scala-lang.org/5GNoOjh1SwSUuVMBTzRqFA

import compiletime.ops.int.Max
import scala.annotation.targetName
opaque type Inlined[T] = T
object Inlined:
  extension [T](inlined: Inlined[T]) def value: T = inlined
  inline given fromValue[T <: Singleton]: Conversion[T, Inlined[T]] =
    value => value
  @targetName("fromValueWide")
  given fromValue[Wide]: Conversion[Wide, Inlined[Wide]] = value => value

  def forced[T](value: Any): Inlined[T] = value.asInstanceOf[T]
  extension [T <: Int](lhs: Inlined[T])
    def max[R <: Int](rhs: Inlined[R]) =
      forced[Max[T, R]](lhs.value max rhs.value)

[error] 14 |      forced[Max[T, R]](lhs.value max rhs.value)
[error]    |                        ^^^^^^^^^^^^^
[error]    |value max is not a member of Inlined[
[error]    |  Inlined[
[error]    |    Inlined[
[error]    |      Inlined[
[error]    |        Inlined[
[error]    |          Inlined[
[error]    |            Inlined[
[error]    |              Inlined[
[error]    |                Inlined[
[error]    |                  Inlined[
[error]    |                    Inlined[
[error]    |                      Inlined[
[error]    |                        Inlined[
[error]    |                          Inlined[
[error]    |                            Inlined[
[error]    |                              Inlined[
[error]    |                                Inlined[
[error]    |                                  Inlined[
[error]    |                                    Inlined[Inlined[Inlined[Inlined[...[...]]]]]
[error]    |                                  ]
[error]    |                                ]
[error]    |                              ]
[error]    |                            ]
[error]    |                          ]
[error]    |                        ]
[error]    |                      ]
[error]    |                    ]
[error]    |                  ]
[error]    |                ]
[error]    |              ]
[error]    |            ]
[error]    |          ]
[error]    |        ]
[error]    |      ]
[error]    |    ]
[error]    |  ]
[error]    |].
[error]    |Extension methods were tried, but the search failed with:
[error]    |
[error]    |    Recursion limit exceeded.
[error]    |Maybe there is an illegal cyclic reference?
[error]    |If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
[error]    |A recurring operation is (inner to outer):
[error]    |
[error]    |  subtype Inlined[
[error]    |  Inlined[
[error]    |    Inlined[
[error]    |      Inlined[
[error]    |        Inlined[
[error]    |          Inlined[
[error]    |            Inlined[
[error]    |              Inlined[
[error]    |                Inlined[
[error]    |                  Inlined[
[error]    |                    Inlined[
[error]    |                      Inlined[
[error]    |                        Inlined[
[error]    |                          Inlined[
[error]    |                            Inlined[
[error]    |                              Inlined[
[error]    |                                Inlined[
[error]    |                                  Inlined[
[error]    |                                    Inlined[
[error]    |                                      Inlined[
[error]    |                                        Inlined[
[error]    |                                          Inlined[
[error]    |                                            Inlined[
[error]    |                                              Inlined[
[error]    |                                                Inlined[
[error]    |                                                  Inlined[
[error]    |                                                    Inlined[
[error]    |                                                      Inlined[
[error]    |                                                        Inlined[
[error]    |                                                          Inlined[
[error]    |                                                            Inlined[
[error]    |                                                              Inlined[
[error]    |                                                                Inlined[
[error]    |                                                                  Inlined[
[error]    |                                                                    Inlined[
[error]    |                                                                      Inlined[
[error]    |                                                                        Inlined[
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          Inlined
[error]    |                                                                            [
[error]    |                                                                          ...
[error]    |                                                                            Inlined
[error]    |                                                                          [
[error]    |                                                                            ...[
[error]    |                                                                              ...
[error]    |                                                                            ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                          ]
[error]    |                                                                        ]
[error]    |                                                                      ]
[error]    |                                                                    ]
[error]    |                                                                  ]
[error]    |                                                                ]
[error]    |                                                              ]
[error]    |                                                            ]
[error]    |                                                          ]
[error]    |                                                        ]
[error]    |                                                      ]
[error]    |                                                    ]
[error]    |                                                  ]
[error]    |                                                ]
[error]    |                                              ]
[error]    |                                            ]
[error]    |                                          ]
[error]    |                                        ]
[error]    |                                      ]
[error]    |                                    ]
[error]    |                                  ]
[error]    |                                ]
[error]    |                              ]
[error]    |                            ]
[error]    |                          ]
[error]    |                        ]
[error]    |                      ]
[error]    |                    ]
[error]    |                  ]
[error]    |                ]
[error]    |              ]
[error]    |            ]
[error]    |          ]
[error]    |        ]
[error]    |      ]
[error]    |    ]
[error]    |  ]
[error]    |] <:< Boolean
[error] one error found

The code works in 3.1.1-RC1, but fails on master.
The workaround was to change the last line to forced[Max[T, R]](math.max(lhs.value, rhs.value))

[odersky]

Can we identify the commit that broke this?

[dwijnand]

Looks to me like a reasonable spree ticket, if anyone is interested in an investigative task.

[ghostbuster91]

Minimized to:

opaque type Inlined[T] = T

object Inlined:
  
  given fromValueWide[Wide]: Conversion[Wide, Inlined[Wide]] = ???

  def myMax: Int = 1 max 2

[nicolasstucki]

it looks like we apply many times fromValueWide implicit conversion before using the wrapedInt conversion to call max. It overflows in PostTyper due to the large tree.

[ghostbuster91]

I run git bisect between 3.1.1 and current master(0b4e96c) and the first commit which breaks it is 0182e06

which clearly states at the end of commit message:

This change breaks a test which involves an unlikely combination of
implicit conversion, overloading and apply insertion. Given that there
is always a tension between type inference and implicit conversion, and
that we're discouraging uses of implicit conversions, I think that's an
acceptable trade-off.

So, it is unclear for me what should the next step be. Should we detect such cases and fail fast?

[smarter]

Implicit conversions should never be chained, this is probably an underlying bug which was exposed by 0182e06 but is otherwise unrelated to it.
The same thing happens with old-style implicit conversions:

opaque type Inlined[T] = T

object Inlined:
  
  implicit def fromValueWide[Wide](x: Wide): Inlined[Wide] = ???

  def myMax: Int = 1 max 2

Dumping the stack while the compiler is running reveals the loop (I didn't check how we break out of it):

        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:616)
        at dotty.tools.dotc.typer.Typer.tryExtensionOrConversion(Typer.scala:3274)
        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:619)
        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:616)
        at dotty.tools.dotc.typer.Typer.tryExtensionOrConversion(Typer.scala:3274)
        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:619)
        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:616)

I tried turning off recursive implicit searches in this codepath:

diff --git compiler/src/dotty/tools/dotc/typer/Typer.scala compiler/src/dotty/tools/dotc/typer/Typer.scala
index d092568fc06..0f847a9b623 100644
--- compiler/src/dotty/tools/dotc/typer/Typer.scala
+++ compiler/src/dotty/tools/dotc/typer/Typer.scala
@@ -3270,7 +3270,7 @@ class Typer(@constructorOnly nestingLevel: Int = 0) extends Namer
               if isExtension then return found
               else
                 checkImplicitConversionUseOK(found)
-                return typedSelect(tree, pt, found)
+                return withoutMode(Mode.ImplicitsEnabled)(typedSelect(tree, pt, found))
             case failure: SearchFailure =>
               if failure.isAmbiguous then
                 return

With that change, the original example compiles after adding an explicit result type to def max (EDIT: actually even without this change the original example compiles with an explicit result type), but the minimized example fails with:

-- [E008] Not Found Error: tests/neg/i13900.scala:9:21 -------------------------
9 |  def myMax: Int = 1 max 2
  |                   ^^^^^
  |value max is not a member of Inlined[Int], but could be made available as an extension method.

Which is weird, since there's no member max in Inlined[Int] (which is equal to Int), we should just disregard it in the implicit search and it shouldn't fail. The check for the presence of max in the type we're converting to is done using SelectionProto#isMatchedBy:
https://github.com/lampepfl/dotty/blob/e54a93465e3c22aefe88c7ffb897224f0b3f4f1e/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L1082
... which always returns true if a type has unknown members:
https://github.com/lampepfl/dotty/blob/e54a93465e3c22aefe88c7ffb897224f0b3f4f1e/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala#L183-L184
... which is considered to be the case if it dealiases to an uninstantiated type variable:
https://github.com/lampepfl/dotty/blob/e54a93465e3c22aefe88c7ffb897224f0b3f4f1e/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala#L160-L165
... which is true in our case, because we typecheck fromValueWide(1) as fromValueWide[?Wide](1) where ?Wide is an uninstantiated type variable lower-bounded by 1.

Of course the implicit conversion doesn't really have unknown members: since it's lower-bounded by 1, it cannot contain members which are not defined in Int, so maybe we could tweak SelectionProto#isMatchedBy to take this into account, but I'm afraid I won't be able to look into this more any time soon.