bug war: type parameters, type aliases, type refinements, type selections

[scabug]

This is related to #8177, but it is not amenable to the workaround of using named type aliases instead of type refinements, because type aliases are equally hopeless.

package p {
  class ViewEnv[AIn] {
    type A = AIn
    class SubView { def has(x: A): Boolean = ??? }
    def get: SubView = new SubView
  }

  trait HasA { type A }
  trait Indexable[R] extends HasA
  class ArrayTC[AIn] extends Indexable[Array[AIn]] { type A = AIn }
}

package object p {
  implicit def arrayTypeClass[A] : ArrayTC[A] = new ArrayTC[A]
  object intArrayTC extends ArrayTC[Int]

  type EnvAlias[W <: HasA] = ViewEnv[W#A]
  type SubAlias[W <: HasA] = ViewEnv[W#A]#SubView

  def f0[R](xs: R)(implicit tc: Indexable[R]): ViewEnv[tc.A]#SubView     = new ViewEnv[tc.A]() get
  def f1[R](xs: R)(implicit tc: Indexable[R]): EnvAlias[tc.type]#SubView = new ViewEnv[tc.A]() get
  def f2[R](xs: R)(implicit tc: Indexable[R]): SubAlias[tc.type]         = new ViewEnv[tc.A]() get

  def g0 = f0(Array(1)) has 2                   // ok
  def g1 = f1(Array(1)) has 2                   // ok
  def g2 = f2(Array(1)) has 2                   // "found: Int(2), required: tc.A"
  def g3 = f2(Array(1))(new ArrayTC[Int]) has 2 // "found: Int(2), required: tc.A"
  def g4 = f2(Array(1))(intArrayTC) has 2       // ok
}

Notice that f1 and f2 are identical except for where the type selection takes place.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8223?orig=1
Reporter: @paulp
See #8177, #7753

[scabug]

@retronym said (edited on Feb 1, 2014 9:58:48 AM UTC):
This looks to be the same "not-a-bug" scenario that I described to Miles in #7753.

InstantiateDependentMap will not substitute the unstable tc = new Array[Int] or tc = arrayTypeClass[Int] into of tc.type

[scabug]

@retronym said:
Marking as a duplicate, but I'll try to think about this to see if there is a way to make this work.

[scabug]

@paulp said:
There has to be a bug. If it's not that too little works it's that too much works. Plus I think it should be considered a bug that it's damn near impossible to know what the compiler has in mind. If it is specifically excluding this it would be great if it would tell me so rather than issuing an error which is indistinguishable from your choice of fifty different compiler bugs.

[scabug]

@paulp said:
g3 compiles like this:

def g3 = f2(Array(1))({ val x = new ArrayTC[Int] ; (x: x.type) }) has 2

I am very interested to know what manner of unsoundness could be rendered sound in this fashion. And then, regardless, can't the compiler make that transformation for me?

[scabug]

@paulp said:
And of course g2 like this.

def g2 = f2(Array(1))({ val x = arrayTypeClass[Int]; (x: x.type) }) has 2

[scabug]

@paulp said:
I made a change which causes this test case to compile as-is without apparent effect on anything else. In particular all the neg and tcpoly tests still pass (that's as much of the test suite as I ran) and the test for #3873 still passes. A couple neg tests slightly changed their output, that's it.

Strangely, or not so strangely, it's essentially the same change as I made for #8177, only in a different spot. Here's the whole change, this time in InstantiateDependentMap.

      case tp1 if tp1 ne tp1.dealias => apply(tp1.dealias)

I really have a great deal of trouble believing this is a soundness issue and not simply compiler bugs. Perhaps someone could demonstrate the unsoundness for me.

[scabug]

@paulp said (edited on Feb 1, 2014 11:03:36 AM UTC):
Also, this is definitively not a duplicate of #7753, since that change makes this compile but leaves that untouched (both the reported version and your modified one.)

[scabug]

@paulp said:
I log the intervention when dealiasing. In the #7753 case, we see

[log typer] InstantiateDependentMap recycling foo.Out: Int
[log typer] InstantiateDependentMap recycling foo.Out: Int
[log typer] InstantiateDependentMap recycling converted.instance.Out: Int
[log typer] InstantiateDependentMap recycling converted.instance.Out: Int
[log typer] InstantiateDependentMap recycling converted.instance.Out: Int
[log typer] InstantiateDependentMap recycling foo.Out: Int
[log typer] InstantiateDependentMap recycling foo.Out: Int
b.scala:26: error: type mismatch;
 found   : Int(23)
 required: si.instance.Out
    val v2: Int = indirect(conv(foo))(23)  // Fails.
                                      ^
b.scala:26: error: type mismatch;
 found   : si.instance.Out
 required: Int
    val v2: Int = indirect(conv(foo))(23)  // Fails.
                          ^
two errors found

In this ticket's test case, we see

[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.SubAlias[tc.type]: p.ViewEnv[tc.A]#SubView
[log typer] InstantiateDependentMap recycling p.package.intArrayTC.A: Int

[scabug]

@paulp said:
With a little more finesse (if dealiased eq apply(dealiased), return the type before dealiasing, so the result only changes if there's good reason) then the three minor output changes go away. The log of successfully compiling this test case then looks like

[log typer] InstantiateDependentMap dealias p.package.SubAlias[tc.type] to p.ViewEnv[tc.A]#SubView and discovered: p.ViewEnv[Int]#SubView
[log typer] InstantiateDependentMap dealias p.package.SubAlias[tc.type] to p.ViewEnv[tc.A]#SubView and discovered: p.ViewEnv[Int]#SubView

[scabug]

@retronym said:
Thanks for digging deeper! I'll take a look at this in the next day or two to see if I can figure out a more precise soundness boundary.

[scabug]

@paulp said:
As an observation, there appears to be to be a massive and devastating conflation between "types as aliases" and "types as type functions". In most cases I am using type aliases with approximately the sophistication of the C preprocessor. I'm just trying to avoid 400 character types being duplicated verbatim all over the place, and that road leads to the current collections. There's no way to juggle the demands of this level without being able to factor types.

A type alias like 'type Foo = Bar', how can it be right that there is not even a distinction drawn between it and some nutty type function involving variance and partial type application and nested type members and dependent this and that. And yet, within the compiler pretty much without exception the check which is performed will lump all type aliases into the same bucket. Which means even if one restricts oneself to using type aliases in the soundest and most straightforward fashion, one is treated by the compiler like a type criminal who might rip off the sound system at any moment.

Another example of the consequences of all the bundling scala does with its features: say you're staring at some code like this:

trait Something[+A]
trait SomethingElse[+B]
trait Foo[+A, B] {
  def reverse: Something[A] with SomethingElse[B]
  def filter(p: A => Boolean): Something[A] with SomethingElse[B]
  def partition(p: A => Boolean): (Something[A] with SomethingElse[B], Something[A] with SomethingElse[B])
}

Now any sane person will want to rewrite that something like

trait Foo[+A, B] {
  private[this] type This = Something[A] with SomethingElse[B]
  def reverse: This
  def filter(p: A => Boolean): This
  def partition(p: A => Boolean): (This, This)
}

Naturally it has to be private[this] or you fail the variance check:

<console>:11: error: covariant type A occurs in invariant position in type Something[A] with SomethingElse[B] of type This
         private type This = Something[A] with SomethingElse[B]
                      ^

Now lucky you are taking on the whole universe of bugs which accompany private[this] for something which has nothing to do with access, members, inheritance. I fully expected it to reject the attempt within a value class because "there is no this there" - maybe it's even a bug that it didn't. But when one just wants less trivially compressible code, all of this is simply language failure.

Between that sort of thing and the many bugs like this one which come with type aliases, I honestly believe using the C preprocessor wherever possible would deliver an overall improvement. That's a pretty sad statement. In scala, separate things are never kept separate; many different intentions are multiplexed through the same lossy facilities; static analysis becomes hopeless.

Here's a bug I discovered while writing this, in case it's not already among the 1600+ open tickets.

scala> final class Foo[+A, B](val x: A) extends AnyVal { private[this] def reverse = ??? }
scala.reflect.internal.Types$TypeError: method reverse$extension in object Foo cannot be accessed in object Foo
	at scala.tools.nsc.typechecker.Contexts$Context.issueCommon(Contexts.scala:547)
	at scala.tools.nsc.typechecker.Contexts$Context.issue(Contexts.scala:552)
	at scala.tools.nsc.typechecker.Infer$Inferencer.issue(Infer.scala:201)
	at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$normalTypedApply$1$1$$anonfun$apply$48.apply(Typers.scala:4465)

[scabug]

@retronym said:
Type aliases have to live somewhere. If it has to capture a class type parameter, and you want to use it through a template, it has to be a member. When you make something a member, you have to make decisions about its visibility.

If there are bugs with private[this] and type members, please lodge them. It would be timely as I've just given findMember an overhaul which flushed out a few problems.

Now, while its true that you can sometimes work around a bug by adding some tactical dealias-es around the compiler (as in your patch for #8177), that doesn't mean that its the right approach. tp.dealias.memberType(sym) might work around a problem with tp.memberType(sym).dealias, but we have to get to the root of the problem.

In #8177, that seemed to be two problems: 1) the assumption that if a type is a subtype of a refinement class it must also be a subclass of the corresponding refinement class symbols; and 2) refinement class symbols of synthetic getters had incoherent owners (and I'll wager at even money that separate compilation could exhibit the same symptom.) The first is easy enough to fix, but the second seemed riskier.

For this bug, we have to answer: Why is the restriction on dependent method type instantiation in place? What are the range of unsound programs that it prevents? What are examples of sound programs that it prevents? Can we find a better rule?

Oh btw, in:

def g2 = f2(Array(1))({ val x = arrayTypeClass[Int]; (x: x.type) }) has 2

I'm a touch surprised that the argument tree is considered stable. I would have expected it to be typed with x.type forSome { val x: TC[Int] } so as not to leak a references to the locally scoped x.

[scabug]

@paulp said:
"I'm a touch surprised that the argument tree is considered stable"

I assume it's a bug. If not I expect to be fascinated by the explanation.

[scabug]

@paulp said:
"Type aliases have to live somewhere." There's your problem right there. The whole ball of spaghetti arises from this requirement. But the requirement is a requirement of man, not of nature.

[scabug]

@paulp said:
Oh yeah, another thing of exactly the same stripe is "package is not a value." Packages aren't values so if you want to refer to "scala.collection.mutable" as "scm" you can re-perform that import/rename in every single file you touch until you die. You are not allowed to give a NAME any meaning, there simply has to be a blob of bits stored in a bucket somewhere or otherwise we wouldn't have enough deadlocks and NPEs.

[scabug]

@paulp said:
Coming back to the (x: x.type), now I think it's not a bug, because it preserves stability without leaking the x.

scala> def f = ({ val x = "" ; identity[x.type] _ })
f: x.type => x.type forSome { val x: String }

scala> def f = ({ val x = "" ; Set[x.type]() })
f: scala.collection.immutable.Set[_ <: String with Singleton]

And naturally I expect it to be stable or I wouldn't have opened the ticket. So if it happened to infer the singleton type, g2 and g3 would work without the intermediate values.

[scabug]

@adriaanm said:
Sorry, I haven't read the whole thread yet, but I can't think of any scenario where eager dealiasing could cause unsoundness -- in the end, the aliased type and its expansion cannot be distinguished by observing the run-time behavior. If there would be a problem with this, the definition of the alias should not be allowed in the first place (e.g., variance must be tracked of course, but that's enforced at the definition).

Now, the issue of cycles is problematic and it's not only an implementation detail. Types may depend on (the type checking of) terms. In most cases, though, cycles in the expansion of type aliases indicate actual typing errors.

[scabug]

@retronym said:
Here's my proposal: scala/scala#3486

[scabug]

@adriaanm said (edited on Feb 13, 2014 4:09:58 AM UTC):
scala/scala#3518