Skip to content
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

Closed
scabug opened this issue Jan 13, 2014 · 28 comments
Closed

Non-deterministic type errors and non-termination of scalac #8146

scabug opened this issue Jan 13, 2014 · 28 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Jan 13, 2014

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):

  1. The code compiles as excepted (~80% of the time):
$ rm *.class 2>/dev/null; time ~/scala/scala-2.11.0-M7/bin/scalac HListBench.scala

real	0m4.678s
user	0m8.699s
sys	0m0.205s
  1. The compiler does not terminate (in ~10% of the runs):
$ rm *.class 2>/dev/null; time ~/scala/scala-2.11.0-M7/bin/scalac HListBench.scala
^C
real	0m22.536s
user	0m25.562s
sys	0m0.214s

-Ystatistics confirms that it's stuck in the typer (the last output is the summary for phase parser).

  1. The compiler aborts with a spurious type error (apparently a failure to find the required implicit conversion) (~10% of cases):
$ rm *.class 2>/dev/null; time ~/scala/scala-2.11.0-M7/bin/scalac HListBench.scala
HListBench.scala:65: error: type mismatch;
 found   : HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HNil.type]]]]]]]]]]]]]]]]]]]]]]]]]]]
 required: ProvenShape[syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.HNil]]]]]]]]]]]]]]]]]]]]]]]]]]]]
    (which expands to)  ProvenShape[HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HNil.type]]]]]]]]]]]]]]]]]]]]]]]]]]]]
    def * = c :: c :: c :: c :: c ::
              ^
one error found

real	0m4.406s
user	0m7.618s
sys	0m0.172s

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)

@scabug
Copy link
Author

scabug commented Jan 13, 2014

Imported From: https://issues.scala-lang.org/browse/SI-8146?orig=1
Reporter: @szeiger
Affected Versions: 2.10.3, 2.11.0-M7
Other Milestones: 2.11.0-RC1
See #8152
Attachments:

@scabug
Copy link
Author

scabug commented Jan 13, 2014

@paulp said:
If you're in the market for workarounds, writing hconsShape as follows makes the problem disappear for me. I doubled the number of ::s and it still compiles successfully each time.

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)
for i in {1..10}; do time scalac3 -d /tmp a.scala ; done
5.661 real, 10.450 user, 0.195 sys
5.671 real, 10.395 user, 0.197 sys
5.638 real, 10.366 user, 0.191 sys
5.655 real, 10.386 user, 0.196 sys
5.744 real, 10.547 user, 0.192 sys
5.706 real, 10.555 user, 0.193 sys
5.781 real, 10.750 user, 0.209 sys
5.766 real, 10.536 user, 0.216 sys
5.778 real, 10.678 user, 0.204 sys
5.779 real, 10.638 user, 0.196 sys

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 ] {

@scabug
Copy link
Author

scabug commented Jan 13, 2014

@paulp said:
If I give the jvm more stack I can compile it with 200 ::s. Then I introduced a type error (200 ::s in the type, 199 ::s in the value) and it found it no problem. Error message wrapped for jira's displaying pleasure.

// 200 and 200 
% time scalac3 -J-Xss8m a.scala
50.707 real, 58.355 user, 0.363 sys
// 200 and 199
% scalac3 -J-Xss8m -b.scala
b.scala:59: error: type mismatch; found :
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],HCons[Column[Int],
HCons[Column[...],HCons[...,...]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
]]]]]]]]] required:
ProvenShape[syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,synt
ax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax
.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.:
:[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[
Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[In
t,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,
syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,sy
ntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,synt
ax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[Int,syntax
.::[Int,syntax.::[Int,syntax.::[Int,syntax.::[...,...]]]]]]]]]]]]]]]]]]]
]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] (which expands to)
ProvenShape[HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,
HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HC
ons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCon
s[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[
Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[In
t,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,
HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[Int,HCons[...,..
.]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] def * = c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c
:: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c :: c ::
c :: c :: c :: c :: c :: c :: c :: c :: HNil ^ one error found

@scabug
Copy link
Author

scabug commented Jan 13, 2014

@retronym said:
Bumping LogPendingSubTypesThreshold from 50 to 500 avoids running into the problem. Well, that would just defer the problem.

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 isSubType.

What is this funny flag? After 50 recursions into isSubType, it starts tracking further recursions and breaks a cycle by returning false.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
[adding @adriaanm]

Pushing the threshold in the other direction, so that this bookkeeping is turned on all the time, shines a spotlight on the problem:

  • SubTypePair has an inconsistent equals and hashCode
  • We falsely flag a cycle a normally progressing subtype computation like (T1 @ann) <:< (T2 @ann) to T1 <:< T2, as =:= ignores annotations.

The first point, linked with our use of a HashSet for pendingSubtypes, is the likely cause of non-determinism.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@paulp said:
I guess that's 1b198fadd1, which includes this gem

 -      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.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
This code dates back to 2007, "make subtyping decidable". scala/scala@152563b

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@paulp said:
What's inconsistent about equals/hashCode at that point?

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
My last comment was a reply to myself, not to Paul's comment, which I hadn't read.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:

That's so good you'd almost think it was me.

The lowercase-letter-philia suggests @m :)

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
Type.hashCode is consistent with Type#equals.

I don't believe that automatically makes it consistent with Type#=:=, but I haven't constructed a counter example.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
e.g. AnnotatedType#hashCode included the hash codes of the annotations. But these are not considered in =:=.

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?

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said (edited on Jan 14, 2014 9:39:03 AM UTC):
Oh, BTW, my comments above I implied that was a regression from 2.10.x. I assumed that without testing. In fact, I get non-termination on 2.10.3 first time around.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said (edited on Jan 14, 2014 9:42:15 AM UTC):
Any now I've made another false claim. 2.10.x gives "slow-termination"

real 1m16.198s
user 1m24.131s
sys 0m0.649s

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@szeiger said:
Indeed, we first noticed this issue on 2.10 (slick/slick#541 (comment)). I used 2.11 to minimize it because of slow compilation of this kind of code on 2.10 (slick/slick#577)

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
Here's what I was trying to say about equals/hashCode of SubTypePair.

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.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
I've added another smaller test case in this branch:

https://github.com/retronym/scala/tree/ticket/8146

The seas are rough beyond the horizon of 50 levels of recursion.

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
scala/scala#3363

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
Stefan:

Using your test case, I've pinpointed the performance progression in 2.11 to scala/scala@882f8e64:

% cat sandbox/test.scala
class HListBench {

  class A[H, T]

  type B[H, T] = A[H, T]

  type T2 = B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, B[Int, Nothing]]]]]]]]]]]]]]]]]]]]]]]]]]]]
}

% time scalac-hash 882f8e64 sandbox/test.scala

real	0m2.345s
user	0m4.025s
sys	0m0.371s
% time scalac-hash 882f8e64~1 sandbox/test.scala

real	1m15.689s
user	1m17.290s
sys	0m0.988s

Massive! I'm going to look at to see if we can backport to 2.10.x

@scabug
Copy link
Author

scabug commented Jan 14, 2014

@retronym said:
I've identified the magic line in that patch and will backport. Tracking that as #8152.

@scabug
Copy link
Author

scabug commented Jan 15, 2014

@retronym said:
Backporting for 2.10.4: scala/scala#3367

@scabug
Copy link
Author

scabug commented Feb 5, 2014

@szeiger said:
It looks like there is still some remaining issue: https://groups.google.com/forum/#!topic/scalaquery/GIptm2LUExg. I have not been able to reproduce it anymore myself.

@scabug
Copy link
Author

scabug commented Feb 5, 2014

Timur Yusupov (ttyusupov) said:
You can get test case project from https://github.com/ttyusupov/slick-examples/tree/hlist_compile_issue:

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.

@scabug
Copy link
Author

scabug commented Feb 5, 2014

@retronym said (edited on Feb 5, 2014 8:46:38 PM UTC):
I can reproduce. You had me worrying with your "at most about 20th", but the suspense was worth it:

-----------------------
Build number: 19
-----------------------
[info] Loading global plugins from /Users/jason/.sbt/0.13/plugins
[info] Loading project definition from /Users/jason/code/slick-examples-ttyusupov/project
[info] Set current project to slick-examples (in build file:/Users/jason/code/slick-examples-ttyusupov/)
[success] Total time: 0 s, completed Feb 5, 2014 9:43:38 PM
[info] Updating {file:/Users/jason/code/slick-examples-ttyusupov/}slick-examples-ttyusupov...
[info] Resolving org.fusesource.jansi#jansi;1.4 ...
[info] Done updating.
[info] Compiling 1 Scala source to /Users/jason/code/slick-examples-ttyusupov/target/scala-2.10/classes...
[error] /Users/jason/code/slick-examples-ttyusupov/src/main/scala/org/ty/Tables.scala:23: type mismatch;
[error]  found   : scala.slick.collection.heterogenous.HCons[Long,scala.slick.collection.heterogenous.HCons[Long,scala.slick.collection.heterogenous.HCons[Option[String],scala.slick.collection.heterogenous.HCons[Option[String],scala.slick.collection.heterogenous.HCons[Option[String],scala.slick.collection.heterogenous.HCons[Option[String],scala.slick.collection.heterogenous.HCons[Option[St

Thanks you so much for making it so easy to reproduce the failure! I'll take a deeper look tomorrow.

@scabug
Copy link
Author

scabug commented Feb 5, 2014

@retronym said:
Darn. Just realised that the tag from which I build 2.10.4-RC2 didn't contain this fix. I'll need to cut another RC.

@scabug
Copy link
Author

scabug commented Feb 5, 2014

@adriaanm said:
Drad. Let's have a 1-week cycle for this RC. In general, I think RC1 (2 weeks) RC2 (1 week) RCn (1 week) final is a good rhythm.

@scabug
Copy link
Author

scabug commented Feb 7, 2014

@retronym said (edited on Feb 7, 2014 7:38:08 AM UTC):
I just confirmed that the test case builds every* time (*where N=30) with 2.10.4-SNAPSHOT. We'll cut RC3 from that. I'll wear the dunce hat for the day as penance for my mistagging...

@scabug
Copy link
Author

scabug commented Feb 10, 2014

@adriaanm said:
Now you're donning your scalac bug wizard cap again: can this be closed (as fixed for 2.10.4-RC3 and 2.11.0-RC1)? It looks like the only commits not merged into master from 2.10.x are marked [nomaster] or [backport].

@scabug scabug closed this as completed Feb 10, 2014
@scabug scabug added the blocker label Apr 7, 2017
@scabug scabug added the typer label Apr 7, 2017
@scabug scabug added this to the 2.10.4-RC3 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants