Eliminate TypeVars and Wildcards early in glb/lub by joroKr21 · Pull Request #6257 · scala/scala

joroKr21 · 2018-01-10T00:45:57Z

Type variables and wildcards can act both as subtypes and
supertypes depending on the direction of the test. This means
types with variables and/or wildcards can shadow other types in
glb/lub.

Consider the following examples:

lub((Int, ? ) :: (Int, String) :: Nil)
glb((Int, ?A) :: (Int, String) :: Nil)

Intuitively both should return (Int, String), but this depends
on the order of types in the list passed to glb/lub.
This commit incorporates the simple heuristic of moving types that
contain variables and/or wildcards to the end of the list.

Fixes scala/bug#10686 and fixes scala/bug#10740

joroKr21 · 2018-01-10T00:46:16Z

I'm not sure how this would affect performance

joroKr21 · 2018-01-10T09:32:32Z

Is it possible that there is a deadlock somewhere in concurrent.TrieMap that is sometimes triggered by the scalacheck tests?

joroKr21 · 2018-01-10T09:33:14Z

/rebuild

joroKr21 · 2018-01-11T11:09:00Z

@retronym how does this look?

retronym · 2018-01-15T03:57:21Z

To help me understand your patch, I've attempted to split it into a refactoring and a behavior change.

Does that split look faithful to your intent?

I still need a bit more time to understand the change.

joroKr21 · 2018-01-15T09:31:25Z

Your split is almost correct. Apologies for not doing this myself.

The semantic change is just the addition of this switch of the current type from t to t1:

if (lteq(t, t1) && t.exists(_.isWildcard)) t1 else t

Note that if we're not going to check for wildcards the switch is pointless and there would be no need to compare lteq(t, t1).

The (tail)-recursive version of the "find all maximal elements in a list given a partial order" (here maxTypes) made it easier for me to understand what it's actually doing. Here the worst running time is inherently O(n^2). There is a difference in the order that types are compared. In maxTypes if we find a bigger element than the current one, we immediately switch to it and go back to the beginning of the list. The old implementation always uses the head of the list to eliminate smaller elements and then recurses into the tail.

joroKr21 · 2018-01-15T12:15:25Z

Hold on, it looks to me that maxTypes doesn't do enough comparisons, so there must be a bug.
The most annoying part is to preserve the original order of the list. This shouldn't matter right?

joroKr21 · 2018-01-15T15:11:34Z

Should be good now

joroKr21 · 2018-01-15T15:31:26Z

src/reflect/scala/reflect/internal/tpe/GlbLubs.scala

+        @tailrec def inner(work: List[Type], done: List[Type]): List[Type] = work match {
+          case t2 :: ts2 if po(t1, t2) => // found a bigger type, we're done here
+            if (!t2.exists(_.isWildcard) || !po(t2, t1)) max
+            else t1 :: (ts2 reverse_::: done)


Could also do ts2 reverse_::: t1 :: done here, but it doesn't seem to matter.

Huh, I guess it does matter after all - so frustrating that with is not symmetric.

joroKr21 · 2018-01-15T20:53:48Z

@retronym It looks like the list passed to lub/glb can contain TypeVars which depend on the exact order of comparisons as being called in the current implementation to be constrained 😭 so I can't change it in any way whatsoever. All I can do is push the partition on ? inside.

joroKr21 · 2018-02-20T23:52:39Z

/sync

joroKr21 · 2018-02-21T09:29:49Z

Updated to fix scala/bug#10740

An alternative would be to use a Queue for type constraints and prepend / append as needed.

Note that this also compiles in Dotty, but neither on Scala 2.13.x nor with this PR:

def foo[A, B](implicit ev: (Int, A) =:= (B, String)) = 42
foo

This would require a redesign of how type variables and constraints are handled.

Edit: Should I add it as a negative test case?

joroKr21 · 2018-03-20T06:26:56Z

/sync

joroKr21 · 2018-04-30T15:44:15Z

/sync

Type variables and wildcards can act both as subtypes and supertypes depending on the direction of the test. This means types with variables and/or wildcards can shadow other types in `glb/lub`. Consider the following examples: ```scala lub((Int, ? ) :: (Int, String) :: Nil) glb((Int, ?A) :: (Int, String) :: Nil) ``` Intuitively both should return `(Int, String)`, but this depends on the order of types in the list passed to `glb/lub`. This commit incorporates the simple heuristic of moving types that contain variables and/or wildcards to the end of the list. Fixes scala/bug#10686 and fixes scala/bug#10740

src/reflect/scala/reflect/internal/tpe/GlbLubs.scala


+  /** From a list of types, retain only maximal types as determined by the partial order `po`. */
+  private def maxTypes(ts: List[Type])(po: (Type, Type) => Boolean): List[Type] = {
+    def loop(ts: List[Type]): List[Type] = ts match {


adriaanm · 2018-05-25T08:51:35Z

src/reflect/scala/reflect/internal/tpe/GlbLubs.scala

+      case t :: ts1 =>
+        val ts2 = loop(ts1.filterNot(po(_, t)))
+        if (ts2.exists(po(t, _))) ts2 else t :: ts2
+      case Nil => Nil


I assume we special-cased Nil and the singleton list based on profiling before? Before we drop these cases, let's gather some statistics on the frequency with which they occur (from casual inspection, not all callers ensure the list's length is >= 2).

It would be a good exercise for me - any pointers how to do this?

Check out Statistics.incCounter

adriaanm · 2018-05-25T14:16:12Z

src/reflect/scala/reflect/internal/tpe/GlbLubs.scala

-    loop(ts)
+    // The order here matters because type variables and
+    // wildcards can act both as subtypes and supertypes.
+    val (ts2, ts1) = ts.partition(_ exists {


I don't think this is the right solution. We shouldn't be calling lub/glb with a list of types that includes type variables or wildcards. These test cases are a great help in debugging this.

Any idea how we could avoid that?

Recalling my experiments here, the current tests exercise this code path, i.e. type variables being inferred by virtue of participating in the lub/glb.

The complete solution would probably come with Dotty but in the mean time it's unsatisfactory explaining to people that they have to swap the arguments to =:= to make their code compile 😄 (due to scala/bug#10686). How about approximating just the wildcards?

I agree we should improve, but I'd like to take a look at the actual code paths that lead here, and how to remove those non-sensical types from the beginning. The type checker already approximates the expected type using wildcards (as wildPt), which shares a similar motiviation.

One code path is via ExistentialType.withTypeVars in subtyping checks when the other type also has type vars. Try this and see a few of the pos partests fail with "trying to do lub/glb of typevar":

--- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -529,7 +529,7 @@ trait TypeComparers { (rt2.parents forall (isSubType(tp1, _, depth))) && (rt2.decls forall (specializesSym(tp1, _, depth))) case et2: ExistentialType => - et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry + suspendingTypeVars(typeVarsInType(tp1))(et2.withTypeVars(isSubType(tp1, _, depth), depth)) || fourthTry case mt2: MethodType => tp1 match { case mt1 @ MethodType(params1, res1) =>

I'm not sure what is the correct thing to do here. Since we only care if there is any solution to the existential skolems but not what that solution is, if feels unexpected that this would affect the inference of some unrelated type variables.

Agreed that those unrelated type vars should not be constrained -- they should act like skolems, I guess. I'm reluctant to change this until I fully understand how this works, which is not likely to happen anymore for 2.13.0, sadly.

My initial comment was wrong -- I see now from your ltr/rtl test case that we get into the situation with wildcards in types. I can't think of a better way to make this more consistent, so, let's go with yours.

adriaanm · 2018-06-04T12:43:40Z

Also, I was poking around here and was reminded of stripExistentialsAndTypeVars. Maybe that method is the right target for this PR?

joroKr21 · 2018-06-06T05:51:45Z

In its current form it doesn't help, because it handles only top-level type variables and it just bails out, but I will try out something similar with a TypeMap.

adriaanm · 2018-06-13T11:57:57Z

Yes, I meant this PR could "target" that method so that it also handles the general case. Maybe it was a mistake that it only handles top-level ones?

adriaanm

Agreed this is a problem, and I can't think of a better way to solve it. So, let's book the progress. Would like to make sure performance is not affected before merging /cc @retronym.

adriaanm · 2018-08-08T13:38:16Z

Since we have a lot going on, optimistically merging -- if performance is affected, we can fix before RC1.

scala-jenkins added this to the 2.13.0-M4 milestone Jan 10, 2018

joroKr21 force-pushed the solve-wildcards branch from 5f6d4e1 to d6f3d9f Compare January 11, 2018 02:45

joroKr21 changed the title ~~Avoid instantiating TypeVars with types containing Wildcards~~ Avoid returning types containing ? from glb/lub Jan 11, 2018

joroKr21 force-pushed the solve-wildcards branch 2 times, most recently from 44df6c6 to 5730ed1 Compare January 15, 2018 15:10

joroKr21 commented Jan 15, 2018

View reviewed changes

joroKr21 force-pushed the solve-wildcards branch 2 times, most recently from 0ecd58f to bd71ab8 Compare January 15, 2018 20:46

joroKr21 force-pushed the solve-wildcards branch from bd71ab8 to 86a16d3 Compare February 20, 2018 21:36

joroKr21 changed the title ~~Avoid returning types containing ? from glb/lub~~ Eliminate TypeVars and Wildcards early in glb/lub Feb 20, 2018

joroKr21 mentioned this pull request Mar 13, 2018

Handle unrelatable skolems in TypeVar bounds #6421

Merged

joroKr21 force-pushed the solve-wildcards branch from 86a16d3 to 3cd2525 Compare March 18, 2018 19:54

joroKr21 mentioned this pull request Mar 18, 2018

misguided type inference with explicit pt and compound types scala/bug#7976

Open

joroKr21 force-pushed the solve-wildcards branch 2 times, most recently from 2fd6ffd to f56e2e5 Compare April 26, 2018 21:54

adriaanm modified the milestones: 2.13.0-M4, 2.13.0-M5 Apr 30, 2018

adriaanm added this to the 2.13.0-M4 milestone Apr 30, 2018

adriaanm self-requested a review April 30, 2018 14:29

szeiger modified the milestones: 2.13.0-M4, 2.13.0-M5 May 2, 2018

joroKr21 added 2 commits May 13, 2018 08:51

Factor out duplicated logic from elimSub/elimSuper

8c9c70d

joroKr21 force-pushed the solve-wildcards branch from f56e2e5 to 6bbef4e Compare May 13, 2018 06:52

adriaanm reviewed May 25, 2018

View reviewed changes

lrytz assigned adriaanm Jun 1, 2018

adriaanm approved these changes Aug 7, 2018

View reviewed changes

adriaanm requested a review from retronym August 7, 2018 13:45

adriaanm merged commit 30e689c into scala:2.13.x Aug 8, 2018

Conversation

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

Uh oh!

Uh oh!

joroKr21 commented Jan 10, 2018

Uh oh!

joroKr21 commented Jan 10, 2018

Uh oh!

joroKr21 commented Jan 10, 2018

Uh oh!

joroKr21 commented Jan 11, 2018

Uh oh!

retronym commented Jan 15, 2018

Uh oh!

joroKr21 commented Jan 15, 2018

Uh oh!

joroKr21 commented Jan 15, 2018

Uh oh!

joroKr21 commented Jan 15, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Uh oh!

joroKr21 commented Feb 20, 2018

Uh oh!

joroKr21 commented Feb 21, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

joroKr21 commented Mar 20, 2018

Uh oh!

joroKr21 commented Apr 30, 2018

Uh oh!

This comment was marked as resolved.

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!

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!

adriaanm commented Jun 4, 2018

Uh oh!

joroKr21 commented Jun 6, 2018

Uh oh!

adriaanm commented Jun 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

adriaanm left a comment

Choose a reason for hiding this comment

Uh oh!

adriaanm commented Aug 8, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

joroKr21 commented Jan 10, 2018 •

edited

Loading

joroKr21 commented Jan 15, 2018 •

edited

Loading

joroKr21 commented Feb 21, 2018 •

edited

Loading

adriaanm commented Jun 13, 2018 •

edited

Loading