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
Non-deterministic type errors and non-termination of scalac #8146
Comments
Imported From: https://issues.scala-lang.org/browse/SI-8146?orig=1
|
@paulp said: implicit def hconsShape[Level <: ShapeLevel, X1 <: Level, X2 <: Level, M1, M2 <: HList, U1, U2 <: HList, P1, P2 <: HList]
(implicit s1: Shape[X1, M1, U1, P1], s2: HListShape[X2, M2, U2, P2]) =
new HListShape[Level, M1 :: M2, U1 :: U2, P1 :: P2](s1 +: s2.shapes)
That's with trait B extends A[
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: Int :: Int :: Int ::
Int :: Int :: HNil ] { |
@paulp said:
|
@retronym said: We'll have to look for something that's changed behind: class SubTypePair(val tp1: Type, val tp2: Type) {
override def hashCode = tp1.hashCode * 41 + tp2.hashCode
override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match {
// suspend TypeVars in types compared by =:=,
// since we don't want to mutate them simply to check whether a subtype test is pending
// in addition to making subtyping "more correct" for type vars,
// it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion)
// this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold)
case stp: SubTypePair =>
val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t))
suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2)
case _ =>
false
})
override def toString = tp1+" <:<? "+tp2
} Another theory: we're hitting the recursion limit sooner in 2.11.x after refactorings in TypeComparers and the way retries are threaded through What is this funny flag? After 50 recursions into isSubType, it starts tracking further recursions and breaks a cycle by returning false. |
@retronym said: Pushing the threshold in the other direction, so that this bookkeeping is turned on all the time, shines a spotlight on the problem:
The first point, linked with our use of a HashSet for |
@paulp said: - if (name contains "_$") origin.typeSymbolDirect.decodedName else name
+ if (name contains "_$") origin.typeSymbolDirect.decodedName else name // wait, what? - what? That's so good you'd almost think it was me. |
@retronym said: |
@paulp said: |
@retronym said: |
@retronym said: I don't believe that automatically makes it consistent with Type#=:=, but I haven't constructed a counter example. |
@retronym said: I would think that == would do the job of detecting cycles. What wouldn't be caught under that approach? Is there is a subtype computation that spawns some infinite sequence of different representations of equivalent types? |
@retronym said (edited on Jan 14, 2014 9:39:03 AM UTC): |
@retronym said (edited on Jan 14, 2014 9:42:15 AM UTC): real 1m16.198s |
@szeiger said: |
@retronym said: scala> trait C { def apply: (Int @unchecked) }
defined trait C
scala> val intUnchecked = typeOf[C].decls.head.info.finalResultType
intUnchecked: $r.intp.global.Type = Int @unchecked
scala> val p1 = new SubTypePair(intUnchecked, intUnchecked)
p1: $r.intp.global.SubTypePair = Int @unchecked <:<? Int @unchecked
scala> val p2 = new SubTypePair(intUnchecked.withoutAnnotations, intUnchecked.withoutAnnotations)
p2: $r.intp.global.SubTypePair = Int <:<? Int
scala> p1 == p2
res0: Boolean = true
scala> p1.hashCode == p2.hashCode
res1: Boolean = false Annotated types are just an example; you could construct another with type aliases, which is probably what is hitting this example. |
@retronym said: https://github.com/retronym/scala/tree/ticket/8146 The seas are rough beyond the horizon of 50 levels of recursion. |
@retronym said: |
@retronym said: Using your test case, I've pinpointed the performance progression in 2.11 to scala/scala@882f8e64:
Massive! I'm going to look at to see if we can backport to 2.10.x |
@retronym said: |
@szeiger said: |
Timur Yusupov (ttyusupov) said: git clone -b hlist_compile_issue https://github.com/ttyusupov/slick-examples slick-examples-ttyusupov Then just run script which will repeat clean+compilation until it is failed: cd slick-examples-ttyusupov
chmod +x repeat_build.sh
./repeat_build.sh For me it failed at least at 3rd try and at most about 20th. |
@retronym said (edited on Feb 5, 2014 8:46:38 PM UTC):
Thanks you so much for making it so easy to reproduce the failure! I'll take a deeper look tomorrow. |
@retronym said: |
@adriaanm said: |
@retronym said (edited on Feb 7, 2014 7:38:08 AM UTC): |
@adriaanm said: |
The attached source code triggers non-deterministic behavior in the compiler. Trying to compile it has three possible results (not equally likely but all easily reproducible with a few dozen runs at most):
-Ystatistics confirms that it's stuck in the typer (the last output is the summary for phase parser).
This is possibly related to #4539. I tried to minimize the test case further but any attempt tipped the scales in one direction or the other, making it harder to reproduce all three cases reliably.
(@moors, this is the issue I told you about last week)
The text was updated successfully, but these errors were encountered: