Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
dwijnand opened this issue Nov 7, 2021 · 8 comments · Fixed by #14750 or #14762
Labels
area:implicits related to implicits itype:bug
Milestone

Comments

@dwijnand
Copy link
Member

dwijnand commented Nov 7, 2021

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
Copy link
Contributor

odersky commented Dec 9, 2021

Can we identify the commit that broke this?

@dwijnand dwijnand added the Spree Suitable for a future Spree label Dec 12, 2021
@dwijnand
Copy link
Member Author

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

@ghostbuster91
Copy link
Contributor

ghostbuster91 commented Mar 22, 2022

Minimized to:

opaque type Inlined[T] = T

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

  def myMax: Int = 1 max 2

@nicolasstucki nicolasstucki removed the Spree Suitable for a future Spree label Mar 22, 2022
@nicolasstucki
Copy link
Contributor

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
Copy link
Contributor

ghostbuster91 commented Mar 22, 2022

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?

@nicolasstucki nicolasstucki assigned smarter and unassigned odersky Mar 22, 2022
@smarter
Copy link
Member

smarter commented Mar 22, 2022

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.

@smarter smarter removed their assignment Mar 22, 2022
@smarter smarter added the area:implicits related to implicits label Mar 22, 2022
smarter added a commit to dotty-staging/dotty that referenced this issue Mar 22, 2022
Just like in tryInsertImplicitOnQualifier, we need to turn off implicit search
when typing a selection after instert an implicit conversion on the qualifier in
tryExtensionOrConversion.

Partially fixes scala#13900, see tests/neg/i13900.scala.
smarter added a commit to dotty-staging/dotty that referenced this issue Mar 22, 2022
Just like in tryInsertImplicitOnQualifier, we need to turn off implicit search
when typing a selection after instert an implicit conversion on the qualifier in
tryExtensionOrConversion.

Partially fixes scala#13900, see tests/neg/i13900.scala.
smarter added a commit to dotty-staging/dotty that referenced this issue Mar 22, 2022
Just like in tryInsertImplicitOnQualifier, we need to turn off implicit search
when typing a selection after instert an implicit conversion on the qualifier in
tryExtensionOrConversion.

Partially fixes scala#13900, see test case.
smarter added a commit to dotty-staging/dotty that referenced this issue Mar 22, 2022
Just like in tryInsertImplicitOnQualifier, we need to turn off implicit search
when typing a selection after inserting an implicit conversion on the qualifier in
tryExtensionOrConversion.

Partially fixes scala#13900, see test case.
@smarter
Copy link
Member

smarter commented Mar 22, 2022

I've opened #14750 to at least fix the loop.

@smarter
Copy link
Member

smarter commented Mar 23, 2022

Re-opening to keep track of the error in https://github.com/lampepfl/dotty/blob/main/tests/neg/i13900.scala.

@smarter smarter changed the title Wrong function invoked leading to Infinite recursion, in master? Unapplicable implicit conversion in scope incorrectly masks applicable implicit conversion in outer scope. Mar 23, 2022
@griggt griggt reopened this Mar 23, 2022
odersky added a commit to dotty-staging/dotty that referenced this issue Mar 23, 2022
As observed in scala#13900, hasKnownMembers gives problematic false positives. What we are
really after is a (nontrivial) upper approximation of known members. Even uninstantiated
type variables have such an approximation if their lower bound is defined and different
from Nothing.

Fixes scala#13900
@Kordyjan Kordyjan added this to the 3.1.3 milestone Aug 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area:implicits related to implicits itype:bug
Projects
None yet
7 participants