Scala 3.5.x compiler crash with java.lang.UnsupportedOperationException: empty.reduceLeft

[alexandru]

Compiler version

Since 3.5.0, with 3.5.1 included.

Minimized code

//> using scala "3.5.1"
//> using dep "com.softwaremill.sttp.tapir::tapir-sttp-client:1.11.5"

import sttp.tapir.*
import sttp.tapir.client.sttp.SttpClientInterpreter

@main def run = 
    lazy val pingGET = endpoint.get
        .in("ping")
        .out(stringBody)

    SttpClientInterpreter()
        .toRequest(pingGET, Some(uri"http://localhost:8080"))

The above gets compiled with:

% scala --version
Scala code runner version: 1.4.3
Scala version (default): 3.5.1

% scala compile ./scala-tapir-bug.scala
...

Output

Compilation (via Scala CLI) crashes the compiler:

Compiling project (Scala 3.5.1, JVM (17))

  exception occurred while typechecking /Users/alex/.../.scala-build/scala-libs_f810e72c65-830a9b3ad2/src_generated/main/scala-tapir-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: /Users/alex/.../.scala-build/scala-libs_f810e72c65-830a9b3ad2/src_generated/main/scala-tapir-bug.scala
        during phase: typer
                mode: Mode(ImplicitsEnabled)
     library version: version 2.13.14
    compiler version: version 3.5.1
            settings: -bootclasspath /opt/homebrew/Cellar/scala/3.5.1/libexec/maven2/org/scala-lang/scala3-library_3/3.5.1/scala3-library_3-3.5.1.jar:/opt/homebrew/Cellar/scala/3.5.1/libexec/maven2/org/scala-lang/scala-library/2.13.14/scala-library-2.13.14.jar -classpath /Users/alex/.../.scala-build/.bloop/scala-libs_f810e72c65-830a9b3ad2/bloop-internal-classes/main-akG9r1HBTvyyhESwBvePTA==:/Users/alex/.../.scala-build/.bloop/scala-libs_f810e72c65-830a9b3ad2/bloop-internal-classes/main-Bal3yVMQQqaAiCb0X6eKHg==:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/tapir/tapir-sttp-client_3/1.11.5/tapir-sttp-client_3-1.11.5.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/tapir/tapir-client_3/1.11.5/tapir-client_3-1.11.5.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/client3/core_3/3.9.8/core_3-3.9.8.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/tapir/tapir-core_3/1.11.5/tapir-core_3-1.11.5.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/model/core_3/1.7.11/core_3-1.7.11.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/shared/core_3/1.3.22/core_3-1.3.22.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/sttp/shared/ws_3/1.3.22/ws_3-1.3.22.jar:/Users/alex/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/softwaremill/magnolia1_3/magnolia_3/1.3.7/magnolia_3-1.3.7.jar -d /Users/alex/.../.scala-build/.bloop/scala-libs_f810e72c65-830a9b3ad2/bloop-internal-classes/main-akG9r1HBTvyyhESwBvePTA== -java-output-version 17 -sourceroot /Users/alex/...

Error compiling project (Scala 3.5.1, JVM (17))
Error: Unexpected error when compiling scala-libs_f810e72c65-830a9b3ad2: java.lang.UnsupportedOperationException: empty.reduceLeft
	at scala.collection.IterableOnceOps.reduceLeft(IterableOnce.scala:853)
	at scala.collection.IterableOnceOps.reduceLeft$(IterableOnce.scala:851)
	at scala.collection.AbstractIterable.reduceLeft(Iterable.scala:935)
	at dotty.tools.dotc.typer.Applications.widenPrefix$1(Applications.scala:1945)
	at dotty.tools.dotc.typer.Applications.comparePrefixes$1(Applications.scala:1963)
	at dotty.tools.dotc.typer.Applications.compareWithTypes$1(Applications.scala:1993)
	at dotty.tools.dotc.typer.Applications.compare(Applications.scala:2005)
	at dotty.tools.dotc.typer.Applications.compare$(Applications.scala:434)
	at dotty.tools.dotc.typer.Typer.compare(Typer.scala:145)
	at dotty.tools.dotc.typer.ImportSuggestions.best$$anonfun$1(ImportSuggestions.scala:299)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.immutable.List.foreach(List.scala:334)
	at dotty.tools.dotc.typer.ImportSuggestions.best(ImportSuggestions.scala:295)
	at dotty.tools.dotc.typer.ImportSuggestions.best$(ImportSuggestions.scala:22)
	at dotty.tools.dotc.typer.Typer.best(Typer.scala:145)
	at dotty.tools.dotc.typer.ImportSuggestions.importSuggestionAddendum(ImportSuggestions.scala:343)
	at dotty.tools.dotc.typer.ImportSuggestions.importSuggestionAddendum$(ImportSuggestions.scala:22)
	at dotty.tools.dotc.typer.Typer.importSuggestionAddendum(Typer.scala:145)
	at dotty.tools.dotc.typer.TypeAssigner.addendum$1$$anonfun$1(TypeAssigner.scala:182)
	at dotty.tools.dotc.typer.ErrorReporting$Errors.selectErrorAddendum(ErrorReporting.scala:279)
	at dotty.tools.dotc.typer.TypeAssigner.addendum$1(TypeAssigner.scala:182)
	at dotty.tools.dotc.typer.TypeAssigner.$anonfun$1(TypeAssigner.scala:185)
	at dotty.tools.dotc.reporting.NotAMember.msg(messages.scala:380)
	at dotty.tools.dotc.reporting.Message.message$$anonfun$1(Message.scala:372)
	at dotty.tools.dotc.reporting.Message.inMessageContext(Message.scala:368)
	at dotty.tools.dotc.reporting.Message.message(Message.scala:372)
	at dotty.tools.xsbt.DelegatingReporter.doReport(DelegatingReporter.java:56)
	at dotty.tools.dotc.reporting.Reporter.issueUnconfigured(Reporter.scala:160)
	at dotty.tools.dotc.reporting.Reporter.go$1(Reporter.scala:191)
	at dotty.tools.dotc.reporting.Reporter.issueIfNotSuppressed(Reporter.scala:210)
	at dotty.tools.dotc.reporting.Reporter.report(Reporter.scala:213)
	at dotty.tools.dotc.reporting.Reporter.flush$$anonfun$1(Reporter.scala:277)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.immutable.List.foreach(List.scala:334)
	at dotty.tools.dotc.reporting.Reporter.flush(Reporter.scala:277)
	at dotty.tools.dotc.core.TyperState.commit(TyperState.scala:176)
	at dotty.tools.dotc.typer.Applications.fail$1(Applications.scala:1183)
	at dotty.tools.dotc.typer.Applications.realApply$1$$anonfun$3$$anonfun$1(Applications.scala:1191)
	at scala.Option.getOrElse(Option.scala:201)
	at dotty.tools.dotc.typer.Applications.realApply$1$$anonfun$3(Applications.scala:1192)
	at dotty.tools.dotc.typer.Typer$.tryEither(Typer.scala:121)
	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.typedBlock(Typer.scala:1406)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3422)
	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.defDefSig(Namer.scala:1959)
	at dotty.tools.dotc.typer.Namer$Completer.typeSig(Namer.scala:827)
	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.xsbt.CompilerBridgeDriver.run(CompilerBridgeDriver.java:141)
	at dotty.tools.xsbt.CompilerBridge.run(CompilerBridge.java:22)
	at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:91)
	at sbt.internal.inc.bloop.internal.BloopHighLevelCompiler.compileSources$1(BloopHighLevelCompiler.scala:133)
	at sbt.internal.inc.bloop.internal.BloopHighLevelCompiler.$anonfun$compile$7(BloopHighLevelCompiler.scala:159)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
	at sbt.internal.inc.bloop.internal.BloopHighLevelCompiler.$anonfun$compile$1(BloopHighLevelCompiler.scala:71)
	at bloop.tracing.NoopTracer$.trace(BraveTracer.scala:53)
	at sbt.internal.inc.bloop.internal.BloopHighLevelCompiler.timed$1(BloopHighLevelCompiler.scala:70)
	at sbt.internal.inc.bloop.internal.BloopHighLevelCompiler.$anonfun$compile$6(BloopHighLevelCompiler.scala:159)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
	at monix.eval.internal.TaskRunLoop$.startFull(TaskRunLoop.scala:81)
	at monix.eval.internal.TaskRestartCallback.syncOnSuccess(TaskRestartCallback.scala:101)
	at monix.eval.internal.TaskRestartCallback.onSuccess(TaskRestartCallback.scala:74)
	at monix.eval.internal.TaskExecuteOn$AsyncRegister$$anon$1.run(TaskExecuteOn.scala:71)
	at java.base/java.util.concurrent.ForkJoinTask$RunnableExecuteAction.exec(ForkJoinTask.java:1423)
	at java.base/java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:387)
	at java.base/java.util.concurrent.ForkJoinPool$WorkQueue.topLevelExec(ForkJoinPool.java:1312)
	at java.base/java.util.concurrent.ForkJoinPool.scan(ForkJoinPool.java:1843)
	at java.base/java.util.concurrent.ForkJoinPool.runWorker(ForkJoinPool.java:1808)
	at java.base/java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:188)

Compilation failed

Expectation

If we change Scala's version to 3.4.2:

Compiling project (Scala 3.4.2, JVM (17))
[error] ./.scala-build/scala-libs_d876299f00-830a9b3ad2/src_generated/main/scala-tapir-bug.scala:15:34
[error] value uri is not a member of StringContext, but could be made available as an extension method.
[error]
[error] One of the following imports might fix the problem:
[error]
[error]   import sttp.client3.UriContext
[error]   import sttp.client3.quick.UriContext
[error]   import sttp.model.Uri.UriContext
[error]
[error]         .toRequest(pingGET, Some(uri"http://localhost:8080"))
[error]                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^
Error compiling project (Scala 3.4.2, JVM (17))
Compilation failed

[Gedochao]

still happens for 3.5.2-RC1 and 3.6.0-RC1-bin-20240927-5ec1e8b-NIGHTLY.
doesn't crash on 3.4.3.
We need to minimize it to a snippet without the tapir dependency.

[noti0na1]

It seems we just need to ensure pre.parents is not empty before calling reduceLeft in widenPrefix.

[noti0na1]

@Gedochao I have tested my fix locally, and it works for this code.

But I'm not able to produce a stanblone test, because it is hard to trigger the case, where the prefix is a module with empty parent.