Compiling large collections of strings literals using scala 2.13 leads to StackOverFlow

[eejbyfeldt]

Reproduction steps

Using this helper program create_strings.scala

import java.io._

val pw = new PrintWriter(new File("large_list_of_string_literals.scala"))
pw.write("object Test {\nval myStrigns: List[String] = List(\n")
(0 to 4000).foreach( i =>
  pw.write(s"  \"$i\",\n")
)
pw.write(")}")
pw.close

and compiling the results

$ scalac --version
Scala compiler version 2.13.10 -- Copyright 2002-2021, LAMP/EPFL and Lightbend, Inc.
scala create_strings.scala
scalac large_list_of_string_literals.scala
error: java.lang.StackOverflowError
    at scala.reflect.internal.tpe.TypeComparers.secondTry$1(TypeComparers.scala:519)
    at scala.reflect.internal.tpe.TypeComparers.firstTry$1(TypeComparers.scala:495)
    at scala.reflect.internal.tpe.TypeComparers.isSubType2(TypeComparers.scala:615)
    at scala.reflect.internal.tpe.TypeComparers.isSubType1(TypeComparers.scala:347)
    at scala.reflect.internal.tpe.TypeComparers.isSubType(TypeComparers.scala:305)
    at scala.reflect.internal.tpe.TypeComparers.isSubType$(TypeComparers.scala:267)
    at scala.reflect.internal.SymbolTable.isSubType(SymbolTable.scala:28)
    at scala.reflect.internal.tpe.TypeComparers.retry$2(TypeComparers.scala:440)
    at scala.reflect.internal.tpe.TypeComparers.isSubType2(TypeComparers.scala:443)
    at scala.reflect.internal.tpe.TypeComparers.isSubType1(TypeComparers.scala:347)
    at scala.reflect.internal.tpe.TypeComparers.isSubType(TypeComparers.scala:305)
    at scala.reflect.internal.tpe.TypeComparers.isSubType$(TypeComparers.scala:267)
    at scala.reflect.internal.SymbolTable.isSubType(SymbolTable.scala:28)
    at scala.reflect.internal.tpe.GlbLubs.$anonfun$elimSub$1(GlbLubs.scala:225)
    at scala.reflect.internal.tpe.GlbLubs.$anonfun$elimSub$1$adapted(GlbLubs.scala:225)
    at scala.reflect.internal.tpe.GlbLubs.$anonfun$maxTypes$1(GlbLubs.scala:203)
    at scala.reflect.internal.tpe.GlbLubs.$anonfun$maxTypes$1$adapted(GlbLubs.scala:203)
    at scala.collection.immutable.List.noneIn$1(List.scala:515)
    at scala.collection.immutable.List.filterCommon(List.scala:581)
    at scala.collection.immutable.List.filterNot(List.scala:504)
    at scala.reflect.internal.tpe.GlbLubs.loop$1(GlbLubs.scala:203)
    at scala.reflect.internal.tpe.GlbLubs.loop$1(GlbLubs.scala:203)
...

Problem

I would expect scala to compile the program with the default jvm stack size.

Some more information

This is only problem in 2.13 both scala 2.12 and scala 3 seems to compile the code without issues. This seems to be lated to literal types I think the overflow seems to happen we call the function scala.reflect.internal.tpe.GlbLubs.loop$1 with literal types in the collection.

Doing the same instead with ints we do not get a stackoverflow. e.g program create_int.scala

import java.io._

val pw = new PrintWriter(new File("large_list_of_int_literals.scala"))
pw.write("object Test {\nval myInts: List[Int] = List(\n")
(0 to 4000).foreach( i =>
  pw.write(s"  $i,\n")
)
pw.write(")}")
pw.close

compiles without issues

scala create_int.scala
scalac large_list_of_int_literals.scala 

[som-snytt]

Maybe I'm not the only person excited to see escaped quote in an interpolated string in the example code. It represents so many years of labor and frustration.

[som-snytt]

It works for me. What stack size are we talking? Anyway, easy to reproduce to see the non-tailrec loop.

➜  snips scala -Xlint example-writer.scala
➜  snips scala -Xlint list-test.scala
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17, [snip]
➜  snips scala -Xlint -J-Xss256k list-test.scala
Exception in thread "main" java.lang.StackOverflowError
        at scala.reflect.internal.tpe.TypeComparers.thirdTry$1(TypeComparers.scala:582)
        at scala.reflect.internal.tpe.TypeComparers.secondTry$1(TypeComparers.scala:519)
        at scala.reflect.internal.tpe.TypeComparers.firstTry$1(TypeComparers.scala:495)
        at scala.reflect.internal.tpe.TypeComparers.isSubType2(TypeComparers.scala:615)
        at scala.reflect.internal.tpe.TypeComparers.isSubType1(TypeComparers.scala:347)
        at scala.reflect.internal.tpe.TypeComparers.isSubType(TypeComparers.scala:305)
        at scala.reflect.internal.tpe.TypeComparers.isSubType$(TypeComparers.scala:267)
        at scala.reflect.internal.SymbolTable.isSubType(SymbolTable.scala:28)
        at scala.reflect.internal.tpe.TypeComparers.retry$2(TypeComparers.scala:440)
        at scala.reflect.internal.tpe.TypeComparers.isSubType2(TypeComparers.scala:443)
        at scala.reflect.internal.tpe.TypeComparers.isSubType1(TypeComparers.scala:347)
        at scala.reflect.internal.tpe.TypeComparers.isSubType(TypeComparers.scala:305)
        at scala.reflect.internal.tpe.TypeComparers.isSubType$(TypeComparers.scala:267)
        at scala.reflect.internal.SymbolTable.isSubType(SymbolTable.scala:28)
        at scala.reflect.internal.tpe.GlbLubs.$anonfun$elimSub$1(GlbLubs.scala:225)
        at scala.reflect.internal.tpe.GlbLubs.$anonfun$elimSub$1$adapted(GlbLubs.scala:225)
        at scala.reflect.internal.tpe.GlbLubs.loop$1(GlbLubs.scala:203)

Minimized

import scala.jdk.CollectionConverters._
import java.nio.file.{Files, Path}

object Test extends App {
  val header = """|object Test extends App {
                  |  val myStrings: List[String] = List(""".stripMargin.linesIterator
  val footer = """|  )
                  |  println(myStrings.mkString(","))
                  |}""".stripMargin.linesIterator
  val values = Iterator.tabulate(4000)(i => s"    \"$i\",")

  val lines  = header ++ values ++ footer
  Files.write(Path.of("list-test.scala"), lines.to(Iterable).asJava)
}

[eejbyfeldt]

The stack size it failed for me was 1M using

$ java --version
openjdk 17.0.6 2023-01-17
OpenJDK Runtime Environment (Red_Hat-17.0.6.0.10-1.fc37) (build 17.0.6+10)
OpenJDK 64-Bit Server VM (Red_Hat-17.0.6.0.10-1.fc37) (build 17.0.6+10, mixed mode, sharing)