When solving type variables propagate solutions to bounds of variables left undetermined by milessabin · Pull Request #6140 · scala/scala

milessabin · 2017-10-19T15:02:46Z

When instantiating type parameters and retracting unsolved ones via adjustTypeArgs and friends we end up with a list of solved type params/variables and a list of still-undetermined type parameters. Typically this is followed by a substitution of the solved variables into the positions of the corresponding parameters, and type checking proceeds with the substitutions eliminated from the list of undetermined type parameters.

However, the substituted parameters might occur as components of the bounds of the type parameters which are yet to be determined and, prior to this PR, these occurrences are not substituted into with the solved variables. This leads to issues of the form seen in scala/bug#10528. This PR performs the substitution similarly to the way it is done in enhanceBounds in typedAppliedTypeTree and fixes scala/bug#10528.

I didn't attempt to move this functionality into AdjustedTypeArgs where it probably belongs, because the way the latter is structured would mean that we'd be performing side effects in a pattern match, albeit an irrefutable one. I think some restructuring of this logic would be worthwhile. I think that it should also be possible now to reinstate a commented out call to checkBounds here with something similar, but I think that would also benefit from some reworking of AdjustedTypeArgs.

All (par)tests pass.

lrytz

LGTM, passing to @adriaanm for a final look.

adriaanm

The required change is likely small, but I'd like you to explore the potential regression outlined in my comment.

adriaanm · 2018-01-12T10:38:18Z

src/compiler/scala/tools/nsc/typechecker/Infer.scala

+        val bounds = undet.info.bounds
+        val substBounds = bounds.subst(okparams, okargs)
+        if(bounds ne substBounds)
+          undet.setInfo(substBounds)


I think we should use updateInfo instead of setInfo. The latter is problematic here because it wipes out undet's type history. Since we didn't create the undet symbol, we can't be sure that's ok.. In practice, this isn't a problem if we're early on in the compiler and there is no type history to wipe out anyway (which is already a tenuous assumption in typedAppliedTypeTree). However, type inference definitely can be triggered in later phases.

I seem to remember fixing bugs resulting of similar abuse of setInfo in the GADT arena. It's also possible, as always, that I'm mistaken, but I'd like you to investigate this (e.g., by trying to construct a run where the type history is non-empty and dumping it before calling setInfo), and hear what @lrytz and @retronym think before merging.

I'm pretty much convinced that updateInfo is the right thing to do rather than setInfo, but I've not been able to construct an example with a non-trivial TypeHistory. Prior to the setInfo call above we have a single entry either for namer or typer, and afterwards the entry is overwritten yielding exactly the same result as if updateInfo was called. Clearly this could go wrong if the TypeHistory was more interesting, but I can't see a way to get that to happen. I think that might be because these are all undetermined params, and will have been freshly cloned (eg. in Inferencer.isApplicable).

I'm happy to follow up on this if anyone can suggest a way of accumulating a more interesting TypeHistory, but for now I'm just going to switch to updateInfo because that appears to be the right thing to do in any case.

The TypeHistory would become more interesting (and relevant) if this method is called later during compilation. Let's say specialization. It's certainly far from trivial to come up with an example (or I would have included it in my comment). If nothing comes up after playing around some more in a debugger and observing what happens, I'm happy to conclude this thread with the side effect of leaving this breadcrumb in the mind of future contributors :-)

milessabin · 2018-01-12T11:49:19Z

This appears to be fine with updateInfo in place of setInfo.

milessabin · 2018-01-12T12:47:36Z

Also rebased.

adriaanm · 2018-01-12T15:47:20Z

Thanks for the quick updates to the code. Please also take into account the style guide for commit messages, as explained in the other PR. Squash the commits, and add a comment to the code that makes it clear enhanceBounds is duplicated, albeit with a deviation to avoid blowing away infos. Add a TODO to the original one to investigate whether setInfo is the right choice there too.

When instantiating type parameters and retracting unsolved ones via adjustTypeArgs and friends we end up with a list of solved type params/variables and a list of still-undetermined type parameters. Typically this is followed by a substitution of the solved variables into the positions of the corresponding parameters, and type checking proceeds with the substitutions eliminated from the list of undetermined type parameters. However, the substituted parameters might occur as components of the bounds of the type parameters which are yet to be determined and, prior to this commit, these occurrences are not substituted into with the solved variables. This leads to issues of the form seen in scala/bug#10528. This commit performs the substitution similarly to the way it is done in enhanceBounds in typedAppliedTypeTree and fixes scala/bug#10528. The new addition is largely a duplicate of the existing mechanism in part to enable it to use updateInfo rather than setInfo and so preserve type histories. There is a TODO to investigate whether the original mechanism should also attempt to preserve type histories and whether the two methods can be combined.

milessabin · 2018-01-12T20:26:26Z

Added comments, squashed and commit message massaged.

adriaanm

❤️

retronym · 2018-01-25T04:33:15Z

This one seems to have caused a regression (maybe, by unearthing an latent bug)

scala/scala-java8-compat#97

trait BaseStream[T, S <: BaseStream[T, S]]
trait Stream[T] extends BaseStream[T, Stream[T]]
trait IntStream extends BaseStream[Integer, IntStream]

sealed trait SS[T, S <: BaseStream[_, S]]
object SSImplicits extends Low {
  implicit val IntValue: SS[Int, IntStream] = null
}
trait Low {
  implicit def anyStreamShape[T]: SS[T, Stream[T]] = null
}

import SSImplicits.{IntValue, anyStreamShape}

class Test {
  implicit def f[A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A, S]): S = ???

  // switch these lines and typechecking the body of `def x` fails in 2.13.x
  x
  y

  def x = f(0): IntStream
  def y = f[String, Stream[String], Vector[String]]("")

}

retronym · 2018-01-25T05:36:50Z

src/compiler/scala/tools/nsc/typechecker/Infer.scala

+        val bounds = undet.info.bounds
+        val substBounds = bounds.subst(okparams, okargs)
+        if(bounds ne substBounds)
+          undet.updateInfo(substBounds)


The problem is likely that these sharpened bounds are only intended to be seen for a single candidate in typedImplicit0, but end up leaking into later candidates.

Yep, seems to be the case:

| | | | [search #7] start `[A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S`, searching for adaptation to pt=Stream[Int] => IntStream (silent: method x in Test) implicits disabled | | | | [search #7] considering f | | | | |-- f BYVALmode-EXPRmode-FUNmode-POLYmode (silent: method x in Test) implicits disabled | | | | | [adapt] [A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S adapted to [A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S | | | | | \-> (a: A)(implicit ss: SS[A,S])S | | | | solving for (A: ?A, S: ?S, CC: ?CC) enhanceBounds(type S#21256) updated <: BaseStream#6553[_, S#21256] to <: BaseStream#6553[_, S#21256] | | | | [search #8] start `[A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S` inferring type S, searching for adaptation to pt=SS[Stream[Int],S] (silent: method x in Test) implicits disabled | | | | [search #8] considering anyStreamShape | | | | solving for (T: ?T) | | | | [adapt] anyStreamShape adapted to [T]=> SS[T,Stream[T]] based on pt SS[Stream[Int],S] | | | | [search #8] solve tvars=?S, tvars.constr= >: Stream[Stream[Int]] <: Stream[Stream[Int]] | | | | solving for (S: ?S) enhanceBounds(type S#21256) updated <: BaseStream#6553[_, S#21256] to <: BaseStream#6553[_, Stream#6580[Stream#6580[Int#1192]]] | | | | [search #8] success inferred value of type SS[Stream[Int],=?Stream[Stream[Int]]] is SearchResult(SSImplicits.anyStreamShape[Stream[Int]], TreeTypeSubstituter(List(type S),List(Stream[Stream[Int]]))) | | | | [adapt] f adapted to [A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S based on pt Stream[Int] => IntStream | | | | [search #9] start `[A, S <: BaseStream[_, S], CC](a: A)(implicit ss: SS[A,S])S`, searching for adaptation to pt=(=> Stream[Int]) => IntStream (silent: method x in Test) implicits disabled sandbox/test.scala:23: error: type mismatch; found : Stream[Int] required: IntStream def x = f(0): IntStream ^

⚡ git diff diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 481307467c..4c1994ef61 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -723,6 +723,9 @@ trait Infer extends Checkable { val substBounds = bounds.subst(okparams, okargs) if(bounds ne substBounds) undet.updateInfo(substBounds) + settings.uniqid.value = true + println(s"enhanceBounds($undet) updated $bounds to $substBounds") + settings.uniqid.value = false }

I'll take a look.

Hmm, sounds like we need to clone the undetermined params for each run of the search? Hopefully not too expensive

Yup, that was my thought too. I'm surprised I wasn't doing that already.

Do you think undoLog could be used for this?

The bounds propagation introduced in scala#6140 caused a regression in scala/scala-java8-compat#97 because bounds sharpened while ranking implicit candidates leaked from candidates tested earlier to those tested later. This commit fixes that by saving and restoring the infos of the symbols of the undetermined type parameters around the call to type check the implicit candidate which tests for it's applicability. Initially it seemed like this ought to be a job for undoLog or Context#savingUndeteriminedTypeParams, but neither of those do the right thing here. UndoLog doesn't help because it affects the constraint on the corresponding TypeVar rather than the info of the symbol; and savingUndeterminedTypeParams doesn't help because the relevant call to typedImplicit shares the enclosing ImplicitSearch#undetParams rather than looking at the context.

milessabin · 2018-02-03T12:20:16Z

Bug identified by @retronym reported here: scala/bug#10708. PR fixing it here: #6308.

In inferMethodInstance a new list of undetermined symbols is computed and returned. However, the bounds enhancement introduced in scala#6140 is applied to the list of previously undetermined symbols, rather than the new list. This commit applies the bounds enhancement to the newly computed list. None of the other callsites of enhanceBounds appear to have the same issue. Fixes scala/bug#10758.

milessabin requested a review from adriaanm October 19, 2017 15:02

scala-jenkins added this to the 2.13.0-M3 milestone Oct 19, 2017

milessabin mentioned this pull request Nov 29, 2017

BUG/FeatureRequest: Type Inference doesn't always use expected Return Type scala/bug#10633

Open

milessabin force-pushed the topic/si-10528 branch from e7179bd to 756c810 Compare December 9, 2017 21:34

lrytz approved these changes Jan 10, 2018

View reviewed changes

lrytz assigned lrytz and adriaanm and unassigned lrytz Jan 10, 2018

adriaanm suggested changes Jan 12, 2018

View reviewed changes

milessabin force-pushed the topic/si-10528 branch from 756c810 to 5cc229c Compare January 12, 2018 12:47

milessabin force-pushed the topic/si-10528 branch from 5cc229c to dd31672 Compare January 12, 2018 20:25

adriaanm approved these changes Jan 15, 2018

View reviewed changes

adriaanm merged commit 68d6696 into scala:2.13.x Jan 15, 2018

SethTisue added the release-notes worth highlighting in next release notes label Jan 16, 2018

retronym mentioned this pull request Jan 25, 2018

compilation failures on tests in Scala 2.13 community build scala/scala-java8-compat#97

Closed

retronym reviewed Jan 25, 2018

View reviewed changes

milessabin mentioned this pull request Feb 2, 2018

Bounds sharpened during implicit search leak between candidates scala/bug#10708

Closed

milessabin mentioned this pull request Feb 3, 2018

Don't leak sharpened bounds between implicit candidates #6308

Merged

soronpo mentioned this pull request Jul 12, 2018

Reflection regression from 2.13.0-M2(or 2.12.4) to 2.13.0-M3, 2.13.0-M4 scala/bug#10758

Closed

milessabin mentioned this pull request Jul 12, 2018

Enhance the right set of type bounds #6927

Merged

joroKr21 mentioned this pull request Oct 7, 2018

Code involving Aux pattern and inheritance fails in most recent 2.13 milestones scala/bug#11193

Open

Conversation

milessabin commented Oct 19, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lrytz left a comment

Choose a reason for hiding this comment

Uh oh!

adriaanm left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

milessabin commented Jan 12, 2018

Uh oh!

milessabin commented Jan 12, 2018

Uh oh!

adriaanm commented Jan 12, 2018

Uh oh!

milessabin commented Jan 12, 2018

Uh oh!

adriaanm left a comment

Choose a reason for hiding this comment

Uh oh!

retronym commented Jan 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

milessabin commented Feb 3, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

milessabin commented Oct 19, 2017 •

edited

Loading

retronym commented Jan 25, 2018 •

edited

Loading