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

StackOverflowError in typer with AnnotatedType #10081

Closed
scabug opened this Issue Nov 29, 2016 · 7 comments

Comments

Projects
None yet
3 participants
@scabug
Copy link

scabug commented Nov 29, 2016

The following code crashes typer:

trait A[_]
trait B[X] extends A[B[X @unchecked]] { this.x }

A is not essential (any type constructor will do), neither is x (any name lookup in "this" suffices) nor unchecked (any annotation does the trick).

The problem appears to be in Implicits.companionImplicitMap (at least that's where it manifests itself), with an endless recursion between getClassParts and getParts, called with types that appear to be the same but not identical. In the reproduction above, the bts(i) as seen in getClassParts are always:

bts(1) = A[B[... @... @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked @unchecked]]
@scabug

This comment has been minimized.

Copy link

scabug commented Nov 29, 2016

Imported From: https://issues.scala-lang.org/browse/SI-10081?orig=1
Reporter: @szeiger
Affected Versions: 2.12.0

@scabug

This comment has been minimized.

Copy link

scabug commented Nov 30, 2016

@retronym said:
That's a good one.

Something like this avoids the problem:

scala/scala@2.12.x...retronym:ticket/10081

Not sure if that changes semantics at all (ie, if any programs have fewer members in the implicit scope after this change).

@scabug

This comment has been minimized.

Copy link

scabug commented Feb 21, 2017

Julien Richard-Foy (julienrf) said:
Hey, what’s the status on this fix? (This issue blocks our work on the collections so I would love to see it fixed!)

@scabug

This comment has been minimized.

Copy link

scabug commented Mar 15, 2017

@SethTisue said:
Is this still a blocker on collections stuff?

@scabug

This comment has been minimized.

Copy link

scabug commented Mar 16, 2017

Julien Richard-Foy (julienrf) said:
Yes.

@scabug

This comment has been minimized.

Copy link

scabug commented Mar 16, 2017

@lrytz said (edited on Mar 16, 2017 8:53:57 AM UTC):
Jason's fix was submitted in scala/scala#5734

@scabug

This comment has been minimized.

Copy link

scabug commented Mar 16, 2017

@lrytz said:
Alternative by Stefan in scala/scala#5742

@scabug scabug added the typer label Apr 7, 2017

@scabug scabug added this to the Backlog milestone Apr 7, 2017

retronym added a commit to retronym/scala that referenced this issue Jan 13, 2018

Fixes over aggressive pruning of implicit scope.
When the implicit scope is constructed an initial pruning phase attempts to
discard implicit members which it is believed would later be rejected as
ambiguous. Members of a companion are discarded if they can be reached via
more than one prefix, on the assumption that being visible via two or more
paths means that the multiple values must conflict with one another. However,
this does not take into account the possibility that the implicit members
might depend on the prefix in a way which renders them non-ambiguous. This
scenario is illustrated in scala/bug#4947 and
scala/bug#5340. This PR address that by only pruning
implicits which are independent of the prefix.

Whilst this PR tries to stay as close as possible to the current behaviour, I
believe that it would be desirable to drop the early pruning of even the
prefix-independent implicits. If we do that then we get improved error
messages reporting ambiguity rather the ambiguous members being silently
ignored which leads to otherwise unexplained failures of implicit resolution.
For instance in the case of `test/files/neg/t5340.scala` which currently
reports,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

we would get the following report,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
Note that implicit conversions are not applicable because they are ambiguous:
 both method conv in object E of type [T, U](b: Quux[T,U])Int
 and method conv in object E of type [T, U](b: Quux[T,U])Int
 are possible conversion functions from Quux[MyApp.r.E,MyApp.s.E] to Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

Which is clearly more informative (even if also a little baffling). I think
that ambiguity via multiple paths is sufficiently rare that the performance
benefits of this early pruning are likely to minimal and not enough to
outweigh improved error messages.

Because this change can result in a symbol _legitimately_ being revisited, via
a different prefix, we need to change the way that the a pruned path is
represented. Instead of using empty lists, as introduced in scala#5951 (which fixes
scala/bug#10081) we use explicit sentinels to mark
that a symbol has been visited at a given prefix yielding no additional
implicits. Testing this yielded scala/bug#10425
which appears to be a regression relative to 2.12.x. That's also fixed in this
PR.

milessabin added a commit to milessabin/scala that referenced this issue Jan 13, 2018

Fixes over aggressive pruning of implicit scope.
When the implicit scope is constructed an initial pruning phase attempts to
discard implicit members which it is believed would later be rejected as
ambiguous. Members of a companion are discarded if they can be reached via
more than one prefix, on the assumption that being visible via two or more
paths means that the multiple values must conflict with one another. However,
this does not take into account the possibility that the implicit members
might depend on the prefix in a way which renders them non-ambiguous. This
scenario is illustrated in scala/bug#4947 and
scala/bug#5340. This PR address that by only pruning
implicits which are independent of the prefix.

Whilst this PR tries to stay as close as possible to the current behaviour, I
believe that it would be desirable to drop the early pruning of even the
prefix-independent implicits. If we do that then we get improved error
messages reporting ambiguity rather the ambiguous members being silently
ignored which leads to otherwise unexplained failures of implicit resolution.
For instance in the case of `test/files/neg/t5340.scala` which currently
reports,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

we would get the following report,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
Note that implicit conversions are not applicable because they are ambiguous:
 both method conv in object E of type [T, U](b: Quux[T,U])Int
 and method conv in object E of type [T, U](b: Quux[T,U])Int
 are possible conversion functions from Quux[MyApp.r.E,MyApp.s.E] to Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

Which is clearly more informative (even if also a little baffling). I think
that ambiguity via multiple paths is sufficiently rare that the performance
benefits of this early pruning are likely to minimal and not enough to
outweigh improved error messages.

Because this change can result in a symbol _legitimately_ being revisited, via
a different prefix, we need to change the way that the a pruned path is
represented. Instead of using empty lists, as introduced in scala#5951 (which fixes
scala/bug#10081) we use explicit sentinels to mark
that a symbol has been visited at a given prefix yielding no additional
implicits. Testing this yielded scala/bug#10425
which appears to be a regression relative to 2.12.x. That's also fixed in this
PR.

@SethTisue SethTisue modified the milestones: Backlog, 2.13.0-M3 Jan 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment