Recursive parser creates infinite loop.

[Ktedon]

Scala Version: 3.1.0
Cats-Parse Version: 0.3.6

I wrote a parser for Java-esque types but it seems be failing when I call it from itself to handle nested constructors.

trait Token

case class Identifier(token: String) extends Token
case class ArbitraryOrderType(name: Identifier, types: ArbitraryOrderType*)
case class TypeLiteral(token: ArbitraryOrderType) extends Token

val identifier: Parser[Identifier] = 
  (alpha | digit).rep.map(id => new Identifier(id.toString))

val singleOrderType: Parser[ArbitraryOrderType] = (
  identifier
).map(id => new ArbitraryOrderType(id))

lazy val typeLiteral: Parser[TypeLiteral] = (
  singleOrderType ~ (singleOrderType.backtrack | typeLiteral)
    .between(Parser.char('<'), Parser.char('>'))
).map(literal => new TypeLiteral(literal._1))

When I run something like this:

println(typeLiteral.parse("type1<type2<type3>>"))

The program does not appear to terminate. I could be doing something wrong because I'm not too familiar with Scala 3 yet but this seems pretty straightforward to me. Am I being silly or is this something wrong with the library?

[johnynek]

You can't actually evaluate that lazy val because to evaluate it you need it.

Try using Parser.recursive

val typeLiteral = Parser.recursive[TypeLiteral] { rec =>
  (singleOrderType ~ (singleOrderType.backtrack | rec)
    .between(Parser.char('<'), Parser.char('>'))
).map(literal => new TypeLiteral(literal._1))
}

see:

scala> val typeLiteral = Parser.recursive[TypeLiteral] { rec =>
     |   (singleOrderType ~ (singleOrderType.backtrack | rec)
     |     .between(Parser.char('<'), Parser.char('>'))
     | ).map(literal => new TypeLiteral(literal._1)) }
val typeLiteral: cats.parse.Parser[TypeLiteral] = Map(Prod(Map(Rep(CharIn(48, bitSet = ..., NonEmptyList((0,9), (A,Z), (a,z))),1,2147483647,cats.parse.Accumulator$$anon$12@55f487f4),AndThen$1484182628),Map(Prod(Void(CharIn(60, bitSet = ..., NonEmptyList((<,<)))),Prod(OneOf(List(Backtrack(Map(Rep(CharIn(48, bitSet = ..., NonEmptyList((0,9), (A,Z), (a,z))),1,2147483647,cats.parse.Accumulator$$anon$12@55f487f4),AndThen$1484182628)), Defer(cats.parse.Parser$$$Lambda$9736/1881068785@5e9a50ab))),Void(CharIn(62, bitSet = ..., NonEmptyList((>,>)))))),cats.parse.Parser$$Lambda$9737/449419071@51914cf2)),$Lambda$9738/1560428785@7375990)

scala> typeLiteral.parse("foo<bar>")
val res4: Either[cats.parse.Parser.Error,(String, TypeLiteral)] = Right((,TypeLiteral(ArbitraryOrderType(Identifier(NonEmptyList(f, o, o)),List()))))

scala> typeLiteral.parse("foo")
val res5: Either[cats.parse.Parser.Error,(String, TypeLiteral)] = Left(Error(3,NonEmptyList(InRange(3,<,<))))

scala> typeLiteral.parse("foo<foo2<bar>>")
val res6: Either[cats.parse.Parser.Error,(String, TypeLiteral)] = Left(Error(8,NonEmptyList(InRange(8,>,>))))

you still have some issues with the parser however. I think you want .? on the between.