Expression of type Parser.Parser[Nonterminal] doesn't conform to Parser.Parser[TypeParameter]

Question

I'm messing around with Scala's parser combinators, and I'm stumped by an error I don't quite seem to understand.

Here's the relevant code:

trait ASTNode
trait Terminal extends ASTNode
trait Nonterminal extends ASTNode
case class Identifier(id: String) extends Terminal
case class TypeDefinition(identifier: Identifier, optionalType: Option[TypeParameters]) extends Nonterminal
case class TypeParameters(params: List[TypeParameter]) extends Nonterminal
case class TypeParameter(typeDef: Either[TypeDefinition, Identifier]) extends Nonterminal

object Parser extends RegexParsers {
  def identifier: Parser[Identifier] = """([a-zA-Z_][\w'-]*)""".r ^^ Identifier

  def typeDef: Parser[TypeDefinition] = identifier ~ opt("of" ~> typeParams) ^^ {
    case id ~ optional => TypeDefinition(id, optional)
  }

// the bit causing the error
  def typeParam: Parser[TypeParameter] = "(" ~> typeDef <~ ")" | identifier ^^ {
    case td: TypeDefinition => TypeParameter(Left(td))
    case id: Identifier => TypeParameter(Right(id))
  }

What's bugging me about the error, is that a) both cases of typeParam return a TypeParameter, and b) TypeParameter is an implementation of Nonterminal, so from what I can see, no error should be produced.

What's going on here and how do I fix this error?

Answer 1

Due to precedence the cases aren't what you think they are. Your two cases are:

"(" ~> typeDef <~ ")"

and

identifier ^^ {
  case td: TypeDefinition => TypeParameter(Left(td))
  case id: Identifier => TypeParameter(Right(id))
}

So since the anime smiley only applies to identifier, the type of "(" ~> typeDef <~ ")" is Parser[TypeDefinition], not Parser[TypeParameter]. So Scala sees you ORing a Parser[TypeDefinition] with a Parser[TypeParameter] and decides that the result must be a Parser[NonTerminal] as that's their most specific common superclass.

To fix this you can just add parentheses around "(" ~> typeDef <~ ")" | identifier to make the precedence what you intended it to be or apply the anime smiley to both cases individually, which also saves you from having to pattern match:

def typeParam: Parser[TypeParameter] =
  "(" ~> typeDef <~ ")" ^^ {
    td => TypeParameter(Left(td))
  } | identifier ^^ {
    id => TypeParameter(Right(id))
  }