fundamentals of base type sequences [ci:last-only]#5041
fundamentals of base type sequences [ci:last-only]#5041paulp wants to merge 7 commits intoscala:2.12.xfrom paulp:pr/6161
Conversation
ASF was failing to recognize the correspondence between a
prefix if it has an abstract type symbol, even if it is bounded by
the currently considered class.
Distilling the test cases, this led to incorrect typechecking of the
RHS of `G` in:
```
trait T {
type A
trait HasH { type H[U] <: U }
type F[N <: HasH] = N#H[T]
type G[N <: HasH] = F[N]#A // RHS was incorrectly reduced to T.this.A
}
```
In the fuller examples (included as test cases), this meant that
type level functions written as members of `HList` could not be
implemented in terms of each other, e.g. defining `Apply[N]` as
`Drop[N]#Head` had the wrong semantics.
This commit checks checks if the prefix has the candidate class
as a base type, rather than checking if its type symbol has this
as a base class. The latter formulation discarded information about
the instantation of the abstract type.
Using the example above:
```
scala> val F = typeOf[T].member(TypeName("F")).info
F: $r.intp.global.Type = [N <: T.this.HasH]N#H[T]
scala> F.resultType.typeSymbol.baseClasses // old approach
res14: List[$r.intp.global.Symbol] = List(class Any)
scala> F.resultType.baseClasses // new approach
res13: List[$r.intp.global.Symbol] = List(trait T, class Object, class Any)
```
It is worth noting that dotty rejects some of these programs,
as it introduces the rule that:
> // A type T is a legal prefix in a type selection T#A if
> // T is stable or T contains no abstract types except possibly A.
> final def isLegalPrefixFor(selector: Name)(implicit ctx: Context)
However, typechecking the program above in this comment in dotty
yields:
<trait> trait T() extends Object {
type A
<trait> trait HasH() extends Object {
type H <: [HK$0] => <: HK$0
}
type F = [HK$0] => HK$0#H{HK$0 = T}#Apply
type G = [HK$0] => HK$0#H{HK$0 = T}#Apply#A
}
As the equivalent code [1] in dotc's `asSeenFrom` already looks for a base type
of the prefix, rather than looking for a superclass of the prefix's
type symbol.
[1] https://github.com/lampepfl/dotty/blob/d2c96d02fccef3a82b88ee1ff31253b6ef17f900/src/dotty/tools/dotc/core/TypeOps.scala#L62
This test case is my minimization from the ticket comments.
I've manually verified that the original version also works now,
but haven't used that as a test case as it depends too intimately
on the structure of `Global`.
```
% cat sandbox/test.scala
trait Namers {
val global: scala.tools.nsc.Global
import global.{ Name, Symbol }
// Relevant definitions in Names
//
// def encode: ThisNameType
// type ThisNameType >: Null <: Name
//
def f(x: Symbol): Name = x.name.encode
}
% qscalac sandbox/test.scala
%
```
At this point it builds, with six test failures. !! 1 - pos/t8177.scala [compilation failed] !! 2 - pos/t8177d.scala [compilation failed] !! 3 - pos/t8177a.scala [compilation failed] !! 4 - pos/t7688.scala [compilation failed] !! 1 - run/t3425.scala [compilation failed] !! 2 - run/t8177f.scala [non-zero exit code]
baseTypeIndex uses binary search, which depends on certain
attributes of the sequence being searched. In particular, it
depends on there being no equal elements among the sequence
being searched. This invariant was not maintained, leading to
the search failing to find matching types.
The intention is that every type in a BaseTypeSeq has a distinct
typeSymbol. I made this true by intercepting when two types with
the same typeSymbol were being placed into a base type sequence,
and rather than letting them both in, intersecting them.
At this point there's one failure, pos/t7688.scala.
t7688.scala:6: error: no type parameters for constructor A: (position: C#Position)A[C] exist so that it can be applied to arguments (c.universe.Position)
--- because ---
argument expression's type is not compatible with formal parameter type;
found : c.universe.Position
required: ?C#Position
(which expands to) Aliases.this.universe.Position
def apply(c: Context)(in: c.Tree): A[c.type] = new A(in.pos)
^
t7688.scala:6: error: type mismatch;
found : c.universe.Position
required: C#Position
(which expands to) C#universe.Position
def apply(c: Context)(in: c.Tree): A[c.type] = new A(in.pos)
^
two errors found
Prefix was not being solved correctly because the constraint acquiring mechanism depends on subtype tests taking place, so if the process is short circuited it can underconstrain the type to be inferred.
| pre match { | ||
| // We may be solving for the prefix, in which case we need the | ||
| // subclass test to add the constraint. See pos/t7688 for an example. | ||
| case _: TypeVar => pre.typeSymbol isSubClass clazz |
There was a problem hiding this comment.
I wonder if we need to generalize this to !pre.isGround.
|
As you can see in the comments it's expected that the commits other than the last one don't pass the tests. I'm not sure what else to do with it given that I started from retronym's branch which didn't even compile, but I'm not about to smoosh his code into mine. I understand some people don't mind discarding ten years of repository history and reimporting everything under their own name, but I believe people should receive credit for their work. |
|
Thanks for picking this one up, it has been hanging over my head. This presentation of commits is good starting point for review. I've tweaked the metadata of this PR to only build the last commit in the future, but marked as on-hold so we don't merge until we agree on how to write the history books. Just to set expectations, we're currently trying to tie off the changes to the trait encoding and cut 2.12.0-M4. We'll target this one for M5. |
|
/synch |
|
I can't even find the console output from those details links, so I'll just note for the record that the tests pass for me. |
|
https://scala-ci.typesafe.com/job/scala-2.12.x-validate-test/1273/consoleFull: |
|
That's the very last commit which I added afterward (reverting retronym's type annotation) which shows why I'm smart not to trust my dulled scala build reflexes. But it's the previous commit where the tests pass for me. |
|
Also, it makes me very suspicious of the sbt build that "sbt test" passes from clean checkout on that same commit. Which indicates it is not building the compiler with itself like the ant build does. Don't know if that's expected. |
|
I reverted the reversion so now we're back at ec41931, the one which should pass. |
it is expected. building-with-itself is handled by Lines 41 to 53 in 99a82be |
|
Talk about rolling out the blue carpet. |
|
What needs to happen to move this along? |
|
It's in my radar... I'm coming back online this week after 👶 -leave My goal is with this PR is to make the original problem with base type seqs more understandable/distilled so that we evaluate the right way to fix it. |
|
Okay, I'm going to post some examples that show what's wrong with the status quo to discussion about how things ought to look. Here's the code to pretty print the base type seq import scala.language.higherKinds
import scala.language.existentials
object p {
type Problem = /* Type Goes Here*/
}
object Test {
def main(args: Array[String]): Unit = {
val settings = new scala.tools.nsc.Settings()
settings.usejavacp.value = true
// settings.debug.value = true
val global = new scala.tools.nsc.Global(settings)
import global._, definitions._
def formatBTS(t: Type): String = {
val bts = t.baseTypeSeq
import scala.reflect.internal.util.TableDef, TableDef.Column
val cols = List[Column[Int]](
Column[Int]("i", i => i, false),
Column[Int]("baseClass", i => t.typeSymbolDirect.baseClasses(i), false),
Column[Int]("baseTypeIndex($bc)", i => t.baseTypeIndex(t.typeSymbolDirect.baseClasses(i)), false),
Column[Int]("typeSymbol", i => bts.typeSymbol(i), false),
// Column[Int]("apply", i => bts(i), false),
Column[Int]("rawElem.getClass", i => bts.rawElem(i).getClass.getSimpleName, false)
)
TableDef(cols: _*).table(bts.toList.indices).toString
}
new Run
println(formatBTS(typeOf[p.Problem]))
}
}
Let's start with a simplified version of one of my test cases in this PR. This shows how an existential type wrapping a refinement type is enough to lead to an inconsistent base type seq. This was what motivated my original attempt to fix things by adding calls to object p {
trait T[A, B]
type Problem = (T[X,String] with T[X,Int]) forSome { type X }
}Simplifying further: trait T[A, B]
type Problem = (T[X,String]{}) forSome { type X }Removing the existential to contrast with a coherent BTS: trait T[A, B]
type Problem = (T[Int,String]{})Wrapping a refinement in another: And now an existental that wraps a regular typeref: trait T[A, B]
type Problem = (T[X,String]) forSome { type X } |
I attemted to make this change in: scala/src/reflect/scala/reflect/internal/BaseTypeSeqs.scala Lines 60 to 81 in 4c4c5e6 scala/src/reflect/scala/reflect/internal/BaseTypeSeqs.scala Lines 90 to 93 in 4c4c5e6 I have since found similar looking special cases might also need to be adapted. scala/src/reflect/scala/reflect/internal/BaseTypeSeqs.scala Lines 204 to 220 in 4c4c5e6 |
|
@adriaanm What is your view on how the errant base type seqs ought to be arranged? My gut feel is that we should have a single entry for the |
|
Running that test with the code in this PR: type Problem = (T[X,String]{}) forSome { type X } |
|
Now that I finally have my big PRs (indysammy and fields refactoring) in decent enough shape, I'll find some time to work on understanding this one. Unfortunately, I have travel and meetings coming up next for Scala Days etc. |
|
For slightly easier debuggability, you can express my test above in JUnit with: diff --git a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
index 38285fb..4e8d561 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
@@ -113,4 +113,33 @@ class DirectCompileTest extends BytecodeTesting {
compiler.compileToBytes("", a)
compiler.compileToBytes(b)
}
+
+ @Test
+ def baseTypeSeq(): Unit = {
+ val compiler = newCompiler(extraArgs = "-language:_")
+ import compiler.global._
+ compiler.compileToBytes("package pack; object p {\n trait T[A, B]\n type Problem = (T[X,String] with T[X,Int]) forSome { type X }\n}")
+
+
+ def formatBTS(t: Type): String = {
+ val bts = t.baseTypeSeq
+ import scala.reflect.internal.util.TableDef, TableDef.Column
+
+ val cols = List[Column[Int]](
+ Column[Int]("i", i => i, false),
+ Column[Int]("baseClass", i => t.typeSymbolDirect.baseClasses(i), false),
+ Column[Int]("baseTypeIndex($bc)", i => t.baseTypeIndex(t.typeSymbolDirect.baseClasses(i)), false),
+ Column[Int]("typeSymbol", i => bts.typeSymbol(i), false),
+ // Column[Int]("apply", i => bts(i), false),
+ Column[Int]("rawElem.getClass", i => bts.rawElem(i).getClass.getSimpleName, false)
+ )
+ TableDef(cols: _*).table(bts.toList.indices).toString
+ }
+ new Run
+
+ val root = rootMirror.findMemberFromRoot(TypeName("pack.p.Problem"))
+ println(root)
+ println(formatBTS(root.info))
+
+ }
}
|
|
I've honed in on: |
|
Maybe I honed in too far there. We have an entry for a typeref for the refinement class itself ( On my travels, I noticed some suspicious code in // I think this is okay, but see #1241 (r12414), #2208, and typedTypeConstructor in Typers
override protected def normalizeImpl: Type = sym.info.normalizeThat discards the prefix. Maybe something like this would be better: // I think this is okay, but see #1241 (r12414), #2208, and typedTypeConstructor in Typers
override protected def normalizeImpl: Type = {
if (sym.info.normalize eq sym.info)
this
else TypeRef(pre0, sym.cloneSymbol.modifyInfo(_.normalize), Nil)
} |
|
Are there any published invariants about how symbols and types are supposed to relate? It seems unlikely progress can be made without that. Anyway, here is some test code I just wrote to illuminate some of the mysteries. Under what conditions should a type be allowed like import scala.language.dynamics
object Typ {
abstract class WType extends Dynamic {
def pre: Type
def sym(name: String): Symbol
def sym1(name: String): Symbol = pre member TypeName(name)
def sym2(name: String): Symbol = sym1(name).info.typeSymbolDirect
def sym3(name: String): Symbol = pre memberInfo sym1(name) typeSymbolDirect
def selectDynamic(name: String): Type = TypeRef(pre, sym(name), Nil)
def applyDynamic(name: String)(targs: Type*): Type = TypeRef(pre, sym(name), targs.toList)
}
case class WType1(val pre: Type) extends WType { def sym(name: String) = sym1(name) }
case class WType2(val pre: Type) extends WType { def sym(name: String) = sym2(name) }
case class WType3(val pre: Type) extends WType { def sym(name: String) = sym3(name) }
}
import Typ._
def show(tp: Type): Unit = println(s"$tp has prefix ${tp.prefix}")
class C[A] { type T = { def foo: A } }
{
show(typeOf[C[Int]#T])
show(WType1(typeOf[C[Int]]).T)
show(WType2(typeOf[C[Int]]).T)
show(WType3(typeOf[C[Int]]).T)
}
// Object{def foo: Int} has prefix <notype>
// C[Int]#T has prefix <notype>
// AnyRef{def foo: A} has prefix C[Int]
// AnyRef{def foo: Int} has prefix C[Int] |
|
My test was just showing that the invariant Conceptually, a refined type ref is the same as a type ref to a regular class. In those cases, we don't substitute the prefix into the members of a nested class, you have to use the prefix again to intepret the types of those members. |
I guess I'm wondering exactly how often that happens when it's necessary. It's hard to believe these sorts of tweaks will ever converge. But my advocacy has even less point than usual here, so I'll return to the observation deck. |
|
This still needs some sorting out, but I've made some progress here: 2.12.x...retronym:review/5041 A base type sequence of an existential type is computed by mapping The status quo: On my latest branch: |
|
An alternative approach to my fix above (which ensures that we preserve ... to something that distinguished this special |
|
Moving over to #5263. |
Builds on retronym's branch ticket/5294 (rebased onto 2.12.x) to fix SI-6161 and other tickets with which it is entangled.