Combination of if, recursion, val binding and match crashes Typer with failed assertion

[fhackett]

minimized code

class Computes[T]

case class Result[T](val computes : Computes[T])

def impl[T](computes : Computes[T]) : Result[T] = {
  val result =
    if ??? then {
      impl(??? : Computes[_])
    } else {
      Result(computes)
    }
  result match {
    case Result(r) => {
      Result(r)
    }
  }
}

It is worth noting that this code would not compile even if it didn't cause the crash; in the code this is minimised from, I had forgotten to cast from a Computes[_] to a Computes[T]. Fixing that error prevents the crash.

Looking at the stacktrace, it seems I hit some edge case the GADT solver doesn't handle?

Stack trace

[error] java.lang.AssertionError: assertion failed
[error]         at scala.Predef$.assert(Predef.scala:208)
[error]         at scala.Predef$Ensuring$.ensuring$extension2(Predef.scala:320)
[error]         at dotty.tools.dotc.core.ProperGadtConstraint.fullBounds(GadtConstraint.scala:195)
[error]         at dotty.tools.dotc.typer.Typer$$anon$1.transform(Typer.scala:1092)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform$$anonfun$2(Trees.scala:1348)
[error]         at scala.collection.immutable.List.mapConserve(List.scala:179)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1348)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1260)
[error]         at dotty.tools.dotc.typer.Typer$$anon$1.transform(Typer.scala:1085)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1315)
[error]         at dotty.tools.dotc.typer.Typer$$anon$1.transform(Typer.scala:1085)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1266)
[error]         at dotty.tools.dotc.typer.Typer$$anon$1.transform(Typer.scala:1085)
[error]         at dotty.tools.dotc.typer.Typer.caseRest$1(Typer.scala:1106)
[error]         at dotty.tools.dotc.typer.Typer.typedCase(Typer.scala:1115)
[error]         at dotty.tools.dotc.typer.Typer.typedCases$$anonfun$1(Typer.scala:1073)
[error]         at dotty.tools.dotc.core.Decorators$ListDecorator$.loop$1(Decorators.scala:62)
[error]         at dotty.tools.dotc.core.Decorators$ListDecorator$.mapconserve$extension(Decorators.scala:78)
[error]         at dotty.tools.dotc.typer.Typer.typedCases(Typer.scala:1073)
[error]         at dotty.tools.dotc.typer.Typer.$anonfun$17(Typer.scala:1067)
[error]         at dotty.tools.dotc.typer.Applications.harmonic(Applications.scala:1826)
[error]         at dotty.tools.dotc.typer.Typer.harmonic(Typer.scala:87)
[error]         at dotty.tools.dotc.typer.Typer.typedMatchFinish(Typer.scala:1067)
[error]         at dotty.tools.dotc.typer.Typer.typedMatch(Typer.scala:1048)
[error]         at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2159)
[error]         at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2201)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2235)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2247)
[error]         at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2325)
[error]         at dotty.tools.dotc.typer.Typer.typedBlock(Typer.scala:711)
[error]         at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2154)
[error]         at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2201)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2235)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2247)
[error]         at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2325)
[error]         at dotty.tools.dotc.typer.Typer.typedDefDef(Typer.scala:1545)
[error]         at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2134)
[error]         at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2200)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2235)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2247)
[error]         at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2266)
[error]         at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2312)
[error]         at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:1674)
[error]         at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2137)
[error]         at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2200)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2235)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2247)
[error]         at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2266)
[error]         at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2312)
[error]         at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:1798)
[error]         at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2177)
[error]         at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2201)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2235)
[error]         at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2247)
[error]         at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2325)
[error]         at dotty.tools.dotc.typer.FrontEnd.typeCheck$$anonfun$1(FrontEnd.scala:75)
[error]         at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
[error]         at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:41)
[error]         at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:79)
[error]         at dotty.tools.dotc.typer.FrontEnd.runOn$$anonfun$3(FrontEnd.scala:109)
[error]         at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
[error]         at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
[error]         at scala.collection.immutable.List.foreach(List.scala:392)
[error]         at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:109)
[error]         at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:158)
[error]         at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
[error]         at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
[error]         at scala.collection.IndexedSeqOptimized.foreach(IndexedSeqOptimized.scala:36)
[error]         at scala.collection.IndexedSeqOptimized.foreach$(IndexedSeqOptimized.scala:33)
[error]         at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:198)
[error]         at dotty.tools.dotc.Run.runPhases$5(Run.scala:170)
[error]         at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:178)
[error]         at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
[error]         at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:102)
[error]         at dotty.tools.dotc.Run.compileUnits(Run.scala:185)
[error]         at dotty.tools.dotc.Run.compileSources(Run.scala:120)
[error]         at dotty.tools.dotc.Run.compile(Run.scala:104)
[error]         at dotty.tools.dotc.Driver.doCompile(Driver.scala:34)
[error]         at dotty.tools.dotc.Driver.process(Driver.scala:172)
[error]         at dotty.tools.dotc.Main.process(Main.scala)
[error]         at xsbt.CachedCompilerImpl.run(CachedCompilerImpl.java:69)
[error]         at xsbt.CompilerInterface.run(CompilerInterface.java:41)
[error]         at sun.reflect.GeneratedMethodAccessor10.invoke(Unknown Source)
[error]         at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
[error]         at java.lang.reflect.Method.invoke(Method.java:498)
[error]         at sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:237)
[error]         at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:111)
[error]         at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:90)
[error]         at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
[error]         at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
[error]         at sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
[error]         at sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
[error]         at sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.sc
ala:307)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompile
rImpl.scala:307)
[error]         at sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
[error]         at sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
[error]         at sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
[error]         at sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
[error]         at sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
[error]         at sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)
[error]         at sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
[error]         at sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerIm
pl.scala:269)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:
159)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:23
8)
[error]         at sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
[error]         at sbt.Defaults$.compileIncrementalTaskImpl(Defaults.scala:1549)
[error]         at sbt.Defaults$.$anonfun$compileIncrementalTask$1(Defaults.scala:1523)
[error]         at scala.Function1.$anonfun$compose$1(Function1.scala:44)
[error]         at sbt.internal.util.$tilde$greater.$anonfun$$u2219$1(TypeFunctions.scala:40)
[error]         at sbt.std.Transform$$anon$4.work(System.scala:67)
[error]         at sbt.Execute.$anonfun$submit$2(Execute.scala:269)
[error]         at sbt.internal.util.ErrorHandling$.wideConvert(ErrorHandling.scala:16)
[error]         at sbt.Execute.work(Execute.scala:278)
[error]         at sbt.Execute.$anonfun$submit$1(Execute.scala:269)
[error]         at sbt.ConcurrentRestrictions$$anon$4.$anonfun$submitValid$1(ConcurrentRestrictions.scala:178)
[error]         at sbt.CompletionService$$anon$2.call(CompletionService.scala:37)
[error]         at java.util.concurrent.FutureTask.run(FutureTask.java:266)
[error]         at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
[error]         at java.util.concurrent.FutureTask.run(FutureTask.java:266)
[error]         at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
[error]         at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
[error]         at java.lang.Thread.run(Thread.java:748)

[abgruszecki]

@smarter part of the problem seems to be that the type inferred for result is:

            Result[_
               >: Nothing & T <: scala.internal.TypeBox[Nothing, Any]#CAP | T
            ]

Is this intended? (The TypeBox part, that is). If we annotate result : Result[_], then everything compiles.

(To get the original code to compile, a sanity check @ https://github.com/lampepfl/dotty/blob/master/compiler/src/dotty/tools/dotc/core/GadtConstraint.scala#L194 needs to be commented out)

[smarter]

The typebox thing happens because we're doing wildcard capture of the type of ??? : Computes[_]: https://github.com/lampepfl/dotty/blob/76dabb90c7da883ef5eeb1bcfaa044419640a38c/compiler/src/dotty/tools/dotc/typer/Typer.scala#L2809-L2814 This is needed because we pass ??? : Computes[_] to impl which takes a type argument, and wildcard capture will make up one for us. The type inferred for result is then the approximation of the union of Result[$i.CAP] and Result[T]. It might be possible to realize this isn't any more precise than Result[_] to produce a nicer type, but I don't think it's wrong as is, though I'm not really sure what your sanity check in GadtConstraint is for, some documentation would help :).

[abgruszecki]

I just said that in case you wanted to experiment - the check is to ensure that no "fictional" type variables invented by GadtConstraint escape.

I'll see why exactly TypeBox in particular makes that check fail.