Regression in community build: collection-strawman

[allanrenucci]

https://travis-ci.org/lampepfl/dotty-community-build/jobs/336895282

[allanrenucci]

trait SortedSet[A] extends SortedSetOps[A, SortedSet, SortedSet[A]]

trait SortedSetOps[A, +CC[X] <: SortedSet[X], +C <: SortedSetOps[A, CC, C]]

class TreeSet[A]
  extends SortedSet[A]
    with SortedSetOps[A, TreeSet, TreeSet[A]]

class Test {
  def optionSequence1[CC[X] <: SortedSet[X] with SortedSetOps[X, CC, CC[X]], A : Ordering](xs: CC[A]): Unit = ()

  def test(xs2: TreeSet[String]) = {
    optionSequence1(xs2)
  }
}

Compiling this code snippet results in an infinite loop

[allanrenucci]

This one results in an IndexOutOfBoundsException:

trait Iterable[+A] extends  IterableOps[A, Iterable, Iterable[A]]
trait IterableOps[+A, +CC[_], +C]

trait SortedSet[A] extends Iterable[A] with SortedSetOps[A, SortedSet, SortedSet[A]]

trait SortedSetOps[A, +CC[X] <: SortedSet[X], +C <: SortedSetOps[A, CC, C]]

class TreeSet[A]
  extends SortedSet[A]
    with SortedSetOps[A, TreeSet, TreeSet[A]]

class Test {
  def optionSequence1[CC[X] <: IterableOps[X, CC, _], A](xs: CC[Option[A]]): Option[CC[A]] = ???
  def optionSequence1[CC[X] <: SortedSet[X] with SortedSetOps[X, CC, CC[X]], A : Ordering](xs: CC[Option[A]]): Option[CC[A]] = ???

  def test(xs2: TreeSet[Option[String]]) = {
    optionSequence1(xs2)
  }
}

Stack trace

exception occurred while compiling tests/allan/Test.scala
Exception in thread "main" java.lang.IndexOutOfBoundsException: 1
	at scala.collection.LinearSeqOptimized.apply(LinearSeqOptimized.scala:63)
	at scala.collection.LinearSeqOptimized.apply$(LinearSeqOptimized.scala:61)
	at scala.collection.immutable.List.apply(List.scala:86)
	at dotty.tools.dotc.core.Types$NamedType.argDenot(Types.scala:1762)
	at dotty.tools.dotc.core.Types$NamedType.fromDesignator$1(Types.scala:1685)
	at dotty.tools.dotc.core.Types$NamedType.computeDenot(Types.scala:1706)
	at dotty.tools.dotc.core.Types$NamedType.denotAt(Types.scala:1657)
	at dotty.tools.dotc.core.Types$NamedType.denot(Types.scala:1646)
	at dotty.tools.dotc.core.Types$NamedType.info(Types.scala:1640)
	at dotty.tools.dotc.core.TypeComparer.compareNamed$1(TypeComparer.scala:169)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.$anonfun$recur$2(TypeComparer.scala:845)
	at scala.runtime.java8.JFunction0$mcZ$sp.apply(JFunction0$mcZ$sp.java:12)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:32)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:124)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:119)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:122)
	at dotty.tools.dotc.core.TypeComparer.isSubArg$1(TypeComparer.scala:891)
	at dotty.tools.dotc.core.TypeComparer.isSubArgs(TypeComparer.scala:897)
	at dotty.tools.dotc.core.TypeComparer.isSubArgs(TypeComparer.scala:903)
	at dotty.tools.dotc.core.TypeComparer.isMatchingApply$1(TypeComparer.scala:677)
	at dotty.tools.dotc.core.TypeComparer.compareAppliedType2$1(TypeComparer.scala:781)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:394)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:358)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:280)
	at dotty.tools.dotc.core.TypeComparer.$anonfun$recur$2(TypeComparer.scala:845)
	at scala.runtime.java8.JFunction0$mcZ$sp.apply(JFunction0$mcZ$sp.java:12)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:32)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:124)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:119)
	at dotty.tools.dotc.core.TypeComparer.compareAppliedType1$1(TypeComparer.scala:815)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:594)
	at dotty.tools.dotc.core.TypeComparer.compareAppliedType2$1(TypeComparer.scala:789)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:394)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:358)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:280)
	at dotty.tools.dotc.core.TypeComparer.$anonfun$recur$2(TypeComparer.scala:845)
	at scala.runtime.java8.JFunction0$mcZ$sp.apply(JFunction0$mcZ$sp.java:12)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:32)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:124)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:119)
	at dotty.tools.dotc.core.TypeComparer.compareAppliedType2$1(TypeComparer.scala:788)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:394)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:292)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:280)
	at dotty.tools.dotc.core.TypeComparer.$anonfun$recur$2(TypeComparer.scala:845)
	at scala.runtime.java8.JFunction0$mcZ$sp.apply(JFunction0$mcZ$sp.java:12)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:32)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:124)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:119)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:122)
	at dotty.tools.dotc.core.TypeComparer.topLevelSubType(TypeComparer.scala:105)
	at dotty.tools.dotc.core.Types$Type.$anonfun$$less$colon$less$1(Types.scala:767)
	at scala.runtime.java8.JFunction0$mcZ$sp.apply(JFunction0$mcZ$sp.java:12)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.core.Types$Type.$less$colon$less(Types.scala:767)
	at dotty.tools.dotc.core.Types$SAMType$.isInstantiatable(Types.scala:3704)
	at dotty.tools.dotc.core.Types$SAMType$.unapply(Types.scala:3709)
	at dotty.tools.dotc.typer.Applications$TestApplication.SAMargOK$1(Applications.scala:485)
	at dotty.tools.dotc.typer.Applications$TestApplication.argOK(Applications.scala:488)
	at dotty.tools.dotc.typer.Applications$TestApplication.addArg(Applications.scala:495)
	at dotty.tools.dotc.typer.Applications$Application.addTyped$1(Applications.scala:414)
	at dotty.tools.dotc.typer.Applications$Application.matchArgs(Applications.scala:454)
	at dotty.tools.dotc.typer.Applications$Application.init(Applications.scala:235)
	at dotty.tools.dotc.typer.Applications$TestApplication.(Applications.scala:503)
	at dotty.tools.dotc.typer.Applications$ApplicableToTrees.(Applications.scala:510)
	at dotty.tools.dotc.typer.Applications.$anonfun$isApplicable$1(Applications.scala:1007)
	at dotty.tools.dotc.typer.Applications.$anonfun$isApplicable$1$adapted(Applications.scala:1007)
	at dotty.tools.dotc.core.TyperState.test(TyperState.scala:111)
	at dotty.tools.dotc.core.Contexts$Context.test(Contexts.scala:293)
	at dotty.tools.dotc.typer.Applications.isApplicable(Applications.scala:1007)
	at dotty.tools.dotc.typer.Applications.isApplicable$(Applications.scala:1006)
	at dotty.tools.dotc.typer.Typer.isApplicable(Typer.scala:82)
	at dotty.tools.dotc.typer.Applications.$anonfun$resolveOverloaded$14(Applications.scala:1372)
	at dotty.tools.dotc.typer.Applications.$anonfun$resolveOverloaded$14$adapted(Applications.scala:1371)
	at scala.collection.TraversableLike.$anonfun$filterImpl$1(TraversableLike.scala:248)
	at scala.collection.immutable.List.foreach(List.scala:389)
	at scala.collection.TraversableLike.filterImpl(TraversableLike.scala:247)
	at scala.collection.TraversableLike.filterImpl$(TraversableLike.scala:245)
	at scala.collection.AbstractTraversable.filterImpl(Traversable.scala:104)
	at scala.collection.TraversableLike.filter(TraversableLike.scala:259)
	at scala.collection.TraversableLike.filter$(TraversableLike.scala:259)
	at scala.collection.AbstractTraversable.filter(Traversable.scala:104)
	at dotty.tools.dotc.typer.Applications.narrowByTrees$1(Applications.scala:1371)
	at dotty.tools.dotc.typer.Applications.$anonfun$resolveOverloaded$5(Applications.scala:1387)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Applications.resolveOverloaded(Applications.scala:1305)
	at dotty.tools.dotc.typer.Applications.$anonfun$resolveOverloaded$1(Applications.scala:1293)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Applications.resolveOverloaded(Applications.scala:1246)
	at dotty.tools.dotc.typer.Applications.resolveOverloaded$(Applications.scala:1246)
	at dotty.tools.dotc.typer.Typer.resolveOverloaded(Typer.scala:82)
	at dotty.tools.dotc.typer.Typer.adaptOverloaded$1(Typer.scala:2048)
	at dotty.tools.dotc.typer.Typer.adaptInterpolated(Typer.scala:2446)
	at dotty.tools.dotc.typer.Typer.$anonfun$adapt$3(Typer.scala:1991)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.$anonfun$adapt$1(Typer.scala:1984)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Typer.adapt(Typer.scala:1984)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:1876)
	at dotty.tools.dotc.typer.Applications.$anonfun$typedApply$1(Applications.scala:676)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Applications.realApply$1(Applications.scala:674)
	at dotty.tools.dotc.typer.Applications.typedApply(Applications.scala:774)
	at dotty.tools.dotc.typer.Applications.typedApply$(Applications.scala:672)
	at dotty.tools.dotc.typer.Typer.typedApply(Typer.scala:82)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:1752)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:1803)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:1876)
	at dotty.tools.dotc.typer.Typer.$anonfun$typedBlock$1(Typer.scala:668)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Typer.typedBlock(Typer.scala:665)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:1759)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:1803)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Namer.$anonfun$typedAheadExpr$1(Namer.scala:982)
	at dotty.tools.dotc.typer.Namer.typedAheadImpl(Namer.scala:972)
	at dotty.tools.dotc.typer.Namer.typedAheadExpr(Namer.scala:982)
	at dotty.tools.dotc.typer.Namer.rhsType$1(Namer.scala:1100)
	at dotty.tools.dotc.typer.Namer.cookedRhsType$1(Namer.scala:1112)
	at dotty.tools.dotc.typer.Namer.lhsType$lzycompute$1(Namer.scala:1113)
	at dotty.tools.dotc.typer.Namer.lhsType$1(Namer.scala:1113)
	at dotty.tools.dotc.typer.Namer.inferredType$1(Namer.scala:1126)
	at dotty.tools.dotc.typer.Namer.valOrDefDefSig(Namer.scala:1134)
	at dotty.tools.dotc.typer.Namer.defDefSig(Namer.scala:1200)
	at dotty.tools.dotc.typer.Namer$Completer.typeSig(Namer.scala:769)
	at dotty.tools.dotc.typer.Namer$Completer.completeInCreationContext(Namer.scala:816)
	at dotty.tools.dotc.typer.Namer$Completer.complete(Namer.scala:794)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.completeFrom(SymDenotations.scala:247)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.completeInfo$1(SymDenotations.scala:210)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.info(SymDenotations.scala:212)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.ensureCompleted(SymDenotations.scala:353)
	at dotty.tools.dotc.typer.Typer.retrieveSym(Typer.scala:1705)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:1730)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:1802)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:1841)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:1864)
	at dotty.tools.dotc.typer.Typer.$anonfun$typedClassDef$1(Typer.scala:1499)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:1429)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:1743)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:1802)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:1841)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:1864)
	at dotty.tools.dotc.typer.Typer.$anonfun$typedPackageDef$1(Typer.scala:1613)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:1600)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:1783)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:1803)
	at dotty.tools.dotc.typer.Typer.$anonfun$typed$2(Typer.scala:1819)
	at dotty.tools.dotc.reporting.trace$.op1$2(trace.scala:25)
	at dotty.tools.dotc.reporting.trace$.apply(trace.scala:26)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:1815)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:1876)
	at dotty.tools.dotc.typer.FrontEnd.$anonfun$typeCheck$1(FrontEnd.scala:66)
	at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:34)
	at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:64)
	at dotty.tools.dotc.typer.FrontEnd.$anonfun$runOn$7(FrontEnd.scala:95)
	at dotty.tools.dotc.typer.FrontEnd.$anonfun$runOn$7$adapted(FrontEnd.scala:95)
	at scala.collection.immutable.List.foreach(List.scala:389)
	at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:95)
	at dotty.tools.dotc.Run.$anonfun$compileUnits$3(Run.scala:170)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
	at dotty.tools.dotc.util.Stats$.trackTime(Stats.scala:47)
	at dotty.tools.dotc.Run.$anonfun$compileUnits$2(Run.scala:167)
	at dotty.tools.dotc.Run.$anonfun$compileUnits$2$adapted(Run.scala:165)
	at scala.collection.IndexedSeqOptimized.foreach(IndexedSeqOptimized.scala:32)
	at scala.collection.IndexedSeqOptimized.foreach$(IndexedSeqOptimized.scala:29)
	at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:191)
	at dotty.tools.dotc.Run.runPhases$1(Run.scala:165)
	at dotty.tools.dotc.Run.$anonfun$compileUnits$1(Run.scala:190)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
	at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:88)
	at dotty.tools.dotc.Run.compileUnits(Run.scala:149)

[allanrenucci]

Here is the commit that introduced the regression: 3ca1171. Before that the two test cases above compiled. More precisely, this patch makes the tests compile on master:

diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala
index 24802412a..6cada0c0a 100644
--- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -25,7 +25,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
 
   private[this] var pendingSubTypes: mutable.Set[(Type, Type)] = null
   private[this] var recCount = 0
-  private[this] var monitored = false
 
   private[this] var needsGc = false
 
@@ -104,7 +103,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
     if ((tp2 eq tp1) || (tp2 eq WildcardType)) return true
     try isSubType(tp1, tp2)
     finally {
-      monitored = false
       if (Config.checkConstraintsSatisfiable)
         assert(isSatisfiable, constraint.show)
     }
@@ -841,8 +839,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       val savedSuccessCount = successCount
       try {
         recCount = recCount + 1
-        if (recCount >= Config.LogPendingSubTypesThreshold) monitored = true
-        val result = if (monitored) monitoredIsSubType else firstTry
+        val result =
+          if (recCount < Config.LogPendingSubTypesThreshold) firstTry
+          else monitoredIsSubType
         recCount = recCount - 1
         if (!result) state.resetConstraintTo(saved)
         else if (recCount == 0 && needsGc) {

But then i3627.scala loops forever

[julienrf]

Can we increase the priority of this issue since it is blocking us?

[smarter]

There's a PR for it, it just needs to be reviewed.