StackOverflow during parsing of multi line comments by combinator parser

[scabug]

I try to parse simple string that contains a few hundreds of commented lines.

val str = (1 to 300).mkString("/* ", "\n", " */\n")

During parsing of this string by scala.util.parsing.combinator.syntactical.StandardTokenParsers there is an exception:

java.lang.StackOverflowError
at scala.util.parsing.input.CharSequenceReader.first(CharSequenceReader.scala:28)
at scala.util.parsing.combinator.Parsers$$anonfun$acceptIf$1.apply(Parsers.scala:488)
at scala.util.parsing.combinator.Parsers$$anonfun$acceptIf$1.apply(Parsers.scala:487)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:182)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:200)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:200)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:182)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:203)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:203)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:182)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:208)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:208)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:182)

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4824?orig=1
Reporter: Wojciech Durczyński (wojciech.durczynski)
Affected Versions: 2.8.1

[scabug]

@dcsobral said:
Please add the parser to the issue, so that it can be reproduced. Make it as small as possible while still displaying the problem.

[scabug]

Wojciech Durczyński (wojciech.durczynski) said:
val str = (1 to 300).mkString("/* ", "\n", " */\n")

val parser = new StandardTokenParsers
val scanner = new parser.lexical.Scanner(new CharSequenceReader(str))
val result = parser.numericLit(scanner)

[scabug]

Trond Olsen (tolsen77) said:
{noformat}Welcome to Scala version 2.9.1.RC1 (Java HotSpot(TM) Client VM, Java 1.6.0_24).

val str = (1 to 200).mkString("/* ", "\n", " */\n")
val parser = new scala.util.parsing.combinator.syntactical.StandardTokenParsers
val reader = new scala.util.parsing.input.CharSequenceReader(str)
val scanner = new parser.lexical.Scanner(reader)

Leads to stack overflow for the following calls (repeated twice):

at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Failure.append(Parsers.scala:163)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:204)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:204)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$Success.flatMapWithNext(Parsers.scala:114)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:201)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:201)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)

at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Failure.append(Parsers.scala:163)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:204)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(Parsers.scala:204)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$Success.flatMapWithNext(Parsers.scala:114)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:201)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(Parsers.scala:201)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
{noformat}

[scabug]

@paulp said:
Not sure how much can be done about this. Patches welcome.

[scabug]

Wojciech Durczyński (wojciech.durczynski) said (edited on Oct 28, 2011 8:41:42 AM UTC):
Problem is in class scala.util.parsing.combinator.lexical.StdLexical
method:

  protected def comment: Parser[Any] = (
      '*' ~ '/'  ^^ { case _ => ' '  }
    | chrExcept(EofCh) ~ comment
    )

causes recursion for every character in multiline comments.
Should be rather something like:

  protected def comment: Parser[Any] = (
      rep('*') ~ '/'  ^^ { case _ => ' '  }
    | rep('*') ~ comment //to avoid recursion for multiline comments filled with '*'
    | rep(chrExcept(EofCh, '*')) ~ comment
    )

[scabug]

Bodo Junglas (bjunglas) said (edited on Sep 9, 2013 9:55:15 PM UTC):
I've encountered the same problem and solved it this way:

protected def comment: Parser[Any] = 
  rep(chrExcept(EofCh, '*') | '*' ~ not('/')) ~ '*' ~ '/' 
    ^^^ ' '

Probably not the most performant solution, but without recursion whatsoever.

[scabug]

@gourlaysama said:
PR: scala/scala-parser-combinators#20

[scabug]

@gourlaysama said:
fixed in scala/scala-parser-combinators@f326847.