java.lang.AssertionError: Failure to join alternatives F and F

[DolphinChips]

Compiler version

3.6.4

Minimized code

trait Applicative[F[_]]:
  def empty: F[?]
  def pure[A](a: A): F[A]

def a[F[_]]: Applicative[F] = ???

def crash[F[_]: Applicative, T](f: F[T]) =
  if false then
    a[F].pure(a[T].empty)
  else
    f

val x =
  for
    _ <- crash(())
  yield ()

Output (click arrow to expand)

  exception occurred while typechecking Bug.scala

  An unhandled exception was thrown in the compiler.
  Please file a crash report here:
  https://github.com/scala/scala3/issues/new/choose
  For non-enriched exceptions, compile with -Xno-enrich-error-messages.

     while compiling: Bug.scala
        during phase: typer
                mode: Mode(ImplicitsEnabled)
     library version: version 2.13.14
    compiler version: version 3.5.1
            settings: 

Exception in thread "main" java.lang.AssertionError: Failure to join alternatives F and F
        at dotty.tools.dotc.core.TypeOps$.fail$1(TypeOps.scala:250)
        at dotty.tools.dotc.core.TypeOps$.mergeRefinedOrApplied$1(TypeOps.scala:282)
        at dotty.tools.dotc.core.TypeOps$.mergeRefinedOrApplied$1(TypeOps.scala:269)
        at dotty.tools.dotc.core.TypeOps$.orDominator(TypeOps.scala:392)
        at dotty.tools.dotc.core.TypeOps$.approximateOr$1(TypeOps.scala:369)
        at dotty.tools.dotc.core.TypeOps$.orDominator(TypeOps.scala:396)
        at dotty.tools.dotc.core.Types$OrType.join(Types.scala:3679)
        at dotty.tools.dotc.core.Types$Type.goOr$1(Types.scala:952)
        at dotty.tools.dotc.core.Types$Type.go$1(Types.scala:823)
        at dotty.tools.dotc.core.Types$Type.findMember(Types.scala:968)
        at dotty.tools.dotc.core.Types$Type.memberBasedOnFlags(Types.scala:760)
        at dotty.tools.dotc.core.Types$Type.member(Types.scala:744)
        at dotty.tools.dotc.typer.ProtoTypes$SelectionProto.isMatchedBy(ProtoTypes.scala:243)
        at dotty.tools.dotc.core.TypeComparer.isMatchedByProto(TypeComparer.scala:2206)
        at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:345)
        at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1574)
        at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
        at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:224)
        at dotty.tools.dotc.core.TypeComparer.topLevelSubType(TypeComparer.scala:132)
        at dotty.tools.dotc.core.TypeComparer.necessarySubType(TypeComparer.scala:143)
        at dotty.tools.dotc.core.TypeComparer$.necessarySubType(TypeComparer.scala:3198)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.necessarilyCompatible(ProtoTypes.scala:52)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.necessarilyCompatible$(ProtoTypes.scala:31)
        at dotty.tools.dotc.typer.ProtoTypes$NoViewsAllowed$.necessarilyCompatible(ProtoTypes.scala:159)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.constrainResult(ProtoTypes.scala:102)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.constrainResult$(ProtoTypes.scala:31)
        at dotty.tools.dotc.typer.ProtoTypes$NoViewsAllowed$.constrainResult(ProtoTypes.scala:159)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.constrainResult(ProtoTypes.scala:153)
        at dotty.tools.dotc.typer.ProtoTypes$Compatibility.constrainResult$(ProtoTypes.scala:31)
        at dotty.tools.dotc.typer.ProtoTypes$NoViewsAllowed$.constrainResult(ProtoTypes.scala:159)
        at dotty.tools.dotc.typer.Applications$Application.init(Applications.scala:567)
        at dotty.tools.dotc.typer.Applications$TypedApply.<init>(Applications.scala:878)
        at dotty.tools.dotc.typer.Applications$ApplyToUntyped.<init>(Applications.scala:995)
        at dotty.tools.dotc.typer.Applications.ApplyTo(Applications.scala:1257)
        at dotty.tools.dotc.typer.Applications.ApplyTo$(Applications.scala:434)
        at dotty.tools.dotc.typer.Typer.ApplyTo(Typer.scala:145)
        at dotty.tools.dotc.typer.Applications.simpleApply$1(Applications.scala:1068)
        at dotty.tools.dotc.typer.Applications.realApply$1$$anonfun$2(Applications.scala:1178)
        at dotty.tools.dotc.typer.Typer$.tryEither(Typer.scala:118)
        at dotty.tools.dotc.typer.Applications.realApply$1(Applications.scala:1193)
        at dotty.tools.dotc.typer.Applications.typedApply(Applications.scala:1231)
        at dotty.tools.dotc.typer.Applications.typedApply$(Applications.scala:434)
        at dotty.tools.dotc.typer.Typer.typedApply(Typer.scala:145)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3414)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3499)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3691)
        at dotty.tools.dotc.typer.Typer.typeSelectOnTerm$1(Typer.scala:961)
        at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:1003)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3389)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3498)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3691)
        at dotty.tools.dotc.typer.Applications.realApply$1(Applications.scala:1040)
        at dotty.tools.dotc.typer.Applications.typedApply(Applications.scala:1231)
        at dotty.tools.dotc.typer.Applications.typedApply$(Applications.scala:434)
        at dotty.tools.dotc.typer.Typer.typedApply(Typer.scala:145)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3414)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3499)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3465)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3499)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3691)
        at dotty.tools.dotc.typer.Namer.typedAheadExpr$$anonfun$1(Namer.scala:1747)
        at dotty.tools.dotc.typer.Namer.typedAhead(Namer.scala:1737)
        at dotty.tools.dotc.typer.Namer.typedAheadExpr(Namer.scala:1747)
        at dotty.tools.dotc.typer.Namer.typedAheadRhs$1$$anonfun$1(Namer.scala:2073)
        at dotty.tools.dotc.inlines.PrepareInlineable$.dropInlineIfError(PrepareInlineable.scala:256)
        at dotty.tools.dotc.typer.Namer.typedAheadRhs$1(Namer.scala:2073)
        at dotty.tools.dotc.typer.Namer.rhsType$1(Namer.scala:2081)
        at dotty.tools.dotc.typer.Namer.cookedRhsType$1(Namer.scala:2100)
        at dotty.tools.dotc.typer.Namer.lhsType$1(Namer.scala:2101)
        at dotty.tools.dotc.typer.Namer.inferredResultType(Namer.scala:2112)
        at dotty.tools.dotc.typer.Namer.inferredType$1(Namer.scala:1779)
        at dotty.tools.dotc.typer.Namer.valOrDefDefSig(Namer.scala:1785)
        at dotty.tools.dotc.typer.Namer$Completer.typeSig(Namer.scala:823)
        at dotty.tools.dotc.typer.Namer$Completer.completeInCreationContext(Namer.scala:974)
        at dotty.tools.dotc.typer.Namer$Completer.complete(Namer.scala:850)
        at dotty.tools.dotc.core.SymDenotations$SymDenotation.completeFrom(SymDenotations.scala:175)
        at dotty.tools.dotc.core.Denotations$Denotation.completeInfo$1(Denotations.scala:190)
        at dotty.tools.dotc.core.Denotations$Denotation.info(Denotations.scala:192)
        at dotty.tools.dotc.core.SymDenotations$SymDenotation.ensureCompleted(SymDenotations.scala:393)
        at dotty.tools.dotc.typer.Typer.retrieveSym(Typer.scala:3361)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3386)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3498)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:3602)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:3648)
        at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:3096)
        at dotty.tools.dotc.typer.Typer.typedTypeOrClassDef$1(Typer.scala:3402)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3406)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3498)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:3602)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:3648)
        at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:3229)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3448)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3499)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3576)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3580)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3691)
        at dotty.tools.dotc.typer.TyperPhase.typeCheck$$anonfun$1(TyperPhase.scala:47)
        at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at dotty.tools.dotc.core.Phases$Phase.monitor(Phases.scala:503)
        at dotty.tools.dotc.typer.TyperPhase.typeCheck(TyperPhase.scala:53)
        at dotty.tools.dotc.typer.TyperPhase.$anonfun$4(TyperPhase.scala:99)
        at scala.collection.Iterator$$anon$6.hasNext(Iterator.scala:479)
        at scala.collection.Iterator$$anon$9.hasNext(Iterator.scala:583)
        at scala.collection.immutable.List.prependedAll(List.scala:152)
        at scala.collection.immutable.List$.from(List.scala:685)
        at scala.collection.immutable.List$.from(List.scala:682)
        at scala.collection.IterableOps$WithFilter.map(Iterable.scala:900)
        at dotty.tools.dotc.typer.TyperPhase.runOn(TyperPhase.scala:98)
        at dotty.tools.dotc.Run.runPhases$1$$anonfun$1(Run.scala:343)
        at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
        at dotty.tools.dotc.Run.runPhases$1(Run.scala:336)
        at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:384)
        at dotty.tools.dotc.Run.compileUnits$$anonfun$adapted$1(Run.scala:396)
        at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:69)
        at dotty.tools.dotc.Run.compileUnits(Run.scala:396)
        at dotty.tools.dotc.Run.compileSources(Run.scala:282)
        at dotty.tools.dotc.Run.compile(Run.scala:267)
        at dotty.tools.dotc.Driver.doCompile(Driver.scala:37)
        at dotty.tools.dotc.Driver.process(Driver.scala:201)
        at dotty.tools.dotc.Driver.process(Driver.scala:169)
        at dotty.tools.dotc.Driver.process(Driver.scala:181)
        at dotty.tools.dotc.Driver.main(Driver.scala:211)
        at dotty.tools.MainGenericCompiler$.run$1(MainGenericCompiler.scala:162)
        at dotty.tools.MainGenericCompiler$.main(MainGenericCompiler.scala:186)
        at dotty.tools.MainGenericCompiler.main(MainGenericCompiler.scala)

Additional information

Manual bisecting shows that this crash was introduced somewhere between versions 3.4.3 and 3.5.0. Above stacktrace is from 3.5.1 and looks identical to what can be seen in 3.5.0 and 3.6.4. I'll try to bisect an exact commit where this was introduced later today.

[DolphinChips]

Update:
I was able to minimize this code further to

trait Applicative[F[_]]:
  def pure[A](a: A): F[A]

def a[F[_]]: Applicative[F] = ???

def crash[F[_]: Applicative, T](f: F[T]) =
  if false then
    a[F].pure(())
  else
    f

val x = crash(()).foo

With bisect.scala I was able to determine that offending commit is somewhere between 1cdf99f and b10d64e. I wasn't able to pinpoint an exact commit because a lot of commits between those two do not compile.

[DolphinChips]

Another update:
Even more minimal form is

def f[F[_], T]: F[Unit] | F[T] = ???
def x[F[_]] = f.toString

This one compiles in 3.3.5, but crashes even 3.4.0.

The following patch fixes the crush, but I can't verify that all tests still pass with it:

iff --git a/compiler/src/dotty/tools/dotc/core/TypeOps.scala b/compiler/src/dotty/tools/dotc/core/TypeOps.scala
index a1e26c20fd..735d87a98d 100644
--- a/compiler/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/compiler/src/dotty/tools/dotc/core/TypeOps.scala
@@ -278,7 +278,7 @@ object TypeOps:
           }
         case AndType(tp11, tp12) =>
           mergeRefinedOrApplied(tp11, tp2) & mergeRefinedOrApplied(tp12, tp2)
-        case tp1: TypeParamRef if tp1 == tp2 => tp1
+        case tp1: TypeParamRef if tp1 =:= tp2 => tp1
         case _ => fail
       }
     }

[Gedochao]

Another update: Even more minimal form is

def f[F[_], T]: F[Unit] | F[T] = ???
def x[F[_]] = f.toString

This one compiles in 3.3.5, but crashes even 3.4.0.

The following patch fixes the crush, but I can't verify that all tests still pass with it:

iff --git a/compiler/src/dotty/tools/dotc/core/TypeOps.scala b/compiler/src/dotty/tools/dotc/core/TypeOps.scala
index a1e26c20fd..735d87a98d 100644
--- a/compiler/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/compiler/src/dotty/tools/dotc/core/TypeOps.scala
@@ -278,7 +278,7 @@ object TypeOps:
}
case AndType(tp11, tp12) =>
mergeRefinedOrApplied(tp11, tp2) & mergeRefinedOrApplied(tp12, tp2)

•    case tp1: TypeParamRef if tp1 == tp2 => tp1
  

•    case tp1: TypeParamRef if tp1 =:= tp2 => tp1
     case _ => fail
   }
  

  }

@DolphinChips feel free to contribute a PR.