TreeHighlighter crash while generating an xml string at the console

[AlexITC]

I have tried sbt console as well as scala-cli console, in both cases, generating some valid xml strings crashes with a StackOverflowError. Running the same code without the console works as expected.

Also, generating a non-xml string just works ((1 to 200).foldRight("x") { case (_, n) => s"< $n >" }).

Previously, I was able to generate a different error which I can't reproduce again because I can't find which Scala version I used in that session:

Compiler version

3.3.0

Minimized example

(1 to 200).foldRight("x") { case (_, n) => s"<x>$n</x>" }

Output

Exception in thread "main" java.lang.StackOverflowError
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1545)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1545)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1545)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1557)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1545)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1551)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:808)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1565)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:809)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)

Expectation

The console mustn't crash.

[nicolasstucki]

When I tried it it got stuck in an infinite loop.

[AlexITC]

I played a bit with this and the behavior seems non-deterministic, for example, I have got the crash with 50 iterations but the next time it just works.

[mbovel]

Reproduced today:

sbt:scala3> repl
[info] compiling 11 Scala sources to /Users/mbovel/dotty/out/bootstrap/scala3-compiler-bootstrapped/scala-3.4.2-RC1-bin-SNAPSHOT-nonbootstrapped/classes ...
[info] compiling 28 Scala sources to /Users/mbovel/dotty/out/bootstrap/scala3-compiler-bootstrapped/scala-3.4.2-RC1-bin-SNAPSHOT-nonbootstrapped/classes ...
Welcome to Scala 3.4.2-RC1-bin-SNAPSHOT-nonbootstrapped-git-678c16b (17.0.8, Java OpenJDK 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.
                                                                                                                                                                              
scala> (1 to 200).foldRight("x") { case (_, n) => s"<x>$n</x>" }
[error] java.lang.StackOverflowError
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1665)
[error]         at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:814)
[error]         at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
[error]         at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:813)
[error]         at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.apply(untpd.scala:813)
[error]         at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1673)

[mbovel]

I believe there is nothing wrong per se in the implementation: the highlighter just overflows the stack if the expression is too deep.

Should we maybe catch StackOverflow exceptions at the top to make it more robust?

[mbovel]

We could add a unit test for this:

diff --git a/compiler/test/dotty/tools/repl/ReplCompilerTests.scala b/compiler/test/dotty/tools/repl/ReplCompilerTests.scala
index 26092b73f1..4b4aca7dc0 100644
--- a/compiler/test/dotty/tools/repl/ReplCompilerTests.scala
+++ b/compiler/test/dotty/tools/repl/ReplCompilerTests.scala
@@ -421,6 +421,10 @@ object ReplCompilerTests:
 
 end ReplCompilerTests
 
+class ReplHighlightTests extends ReplTest(ReplTest.defaultOptions.filterNot(_.startsWith("-color")) :+ "-color:always"):
+  @Test def i18596: Unit = initially:
+    run("""(1 to 500).foldRight("x") { case (_, n) => s"<x>$n</x>" }""")
+
 class ReplXPrintTyperTests extends ReplTest(ReplTest.defaultOptions :+ "-Xprint:typer"):
   @Test def i9111 = initially {
     run("""|enum E {

To be run with:

sbt:scala3> scala3-compiler / Test / testOnly *ReplHighlightTests

[AlexITC]

I believe there is nothing wrong per se in the implementation: the highlighter just overflows the stack if the expression is too deep.

While this makes sense, the behavior I experience was non-deterministic.

[mbovel]

While this makes sense, the behavior I experience was non-deterministic.

Oh, I missed that, interesting. I just tried again and got different results depending on the sequence of expressions entered in the REPL.

For example, trying with to 60 directly seem to always fail for me:

➜  ~ scala-cli repl -S "3.nightly" --jvm 17
Welcome to Scala 3.4.2-RC1-bin-20240219-9a79c14-NIGHTLY-git-9a79c14 (17.0.6, Java OpenJDK 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.
                                                                                                                      
scala> (1 to 60).foldRight("x") { case (_, n) => s"<x>$n</x>" }
Exception in thread "main" java.lang.StackOverflowError
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1665)
	at dotty.tools.dotc.ast.untpd$UntypedTreeTraverser.traverseChildren(untpd.scala:814)
	at dotty.tools.dotc.printing.SyntaxHighlighting$TreeHighlighter$2$.traverse(SyntaxHighlighting.scala:123)
        ...

While trying with to 40 first and then with to 60 seem to always work:

➜  ~ scala-cli repl -S "3.3.2" --jvm 17    
Welcome to Scala 3.3.2 (17.0.6, Java OpenJDK 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.
                                                                                                                      
scala> (1 to 40).foldRight("x") { case (_, n) => s"<x>$n</x>" }
val res0: String = <x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x>x</x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x>
                                                                                                                      
scala> (1 to 60).foldRight("x") { case (_, n) => s"<x>$n</x>" }
val res1: String = <x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x><x>x</x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x></x>

So maybe the result is deterministic but dependent on previous steps? Or did you observe otherwise?

[AlexITC]

So maybe the result is deterministic but dependent on previous steps? Or did you observe otherwise?

I remember experiencing that, trying this right now leads to this (new session per line scala-cli console):

1. 600 fails
2. 500 then 600, both worh.
3. 590 fails
4. 590 works

Case 3 and 4 weren't simple to hit.