Bug in type of `|` rule combinator?

[Alexander Myltsev]

Hi,

looking at README section https://github.com/sirthias/parboiled2/#rule-combinators-and-modifiers on "a | b",

This operator can only be used on compatible rules.

what does it mean exactly "compatible rules"? Current typing rules allows parser as follows:

class SomeParser extends Parser {
  def test = rule { push("x") ~ (a1 | b1) }
  def a1 = rule { str("a") ~> { (i: Int) => push("a1") } }  
  def b1 = rule { str("b") ~> { (i: String) => push("b1") } }
}

But it would fail on:

scala> new org.parboiled2.examples.ABCParser1().test.run("b")
res2: scala.util.Try[String] = Success(b1)
scala> new org.parboiled2.examples.ABCParser1().test.run("a")
res3: scala.util.Try[String] = Failure(java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer)

The reason is in weird type of `|` operator. Why corresponding `Input` types of left and right `Rule` should not be equal?

A.

[Alexander Myltsev]

Are those rules should work together?

def test2 = rule { a2 | b2 }
def a2 = rule { str("a") ~ push(22) }
def b2 = rule { str("b") ~ push("abc") }

It actually works. What does `CanBeOred` prevent from?

A.

[Mathias Doenitz]

Alex,

good catch!
This is indeed a bug.

The reason for the fact that the illegal grammar in your example is actually compiling when it shouldn't is that the compiler infers the type of `a1 | b1` to be

Rule[(Int :: HNil) with (String :: HNil), String :: HNil]

where I was hoping that it would simply give up with a type error because the inferred type is uninhabitable.

Here is a simpler example demonstrating the problem directly in the REPL:

Welcome to Scala 2.11.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_92).
Type in expressions for evaluation. Or try :help.

scala> :paste
// Entering paste mode (ctrl-D to finish)

class Foo[-A, +B] {
def |[AA <: A, BB >: B](that: Foo[AA, BB]): Foo[AA, BB] = that
}
val a = new Foo[CharSequence, Unit]
val b = new Foo[String, Unit]
val c = new Foo[Int, Unit]

// Exiting paste mode, now interpreting.

defined class Foo
a: Foo[CharSequence,Unit] = Foo@762efe5d
b: Foo[String,Unit] = Foo@5d22bbb7
c: Foo[Int,Unit] = Foo@41a4555e

scala> a | b
res0: Foo[String,Unit] = Foo@5d22bbb7

scala> b | a
res1: Foo[String,Unit] = Foo@762efe5d

scala> b | c
res2: Foo[String with Int,Unit] = Foo@41a4555e

scala>

As you can see everything works as expected in the happy cases `a | b` and `b | a`.
But in the illegal case `b | c` the compiler infers `String with Int` for the first type parameter rather than producing an error.

One way to fix the problem is to compute the result type more manually, e.g. like this:

Welcome to Scala 2.11.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_92).
Type in expressions for evaluation. Or try :help.

scala> :paste
// Entering paste mode (ctrl-D to finish)

class Foo[-A, +B] {
def |[AA, BB >: B](that: Foo[AA, BB])
(implicit ev: MoreSpecific[AA, A @annotation.unchecked.uncheckedVariance]): Foo[ev.Out, BB] =
that.asInstanceOf[Foo[ev.Out, BB]]
}

@annotation.implicitNotFound("Illegal `|` operation")
sealed trait MoreSpecific[A, B] {
type Out
}
object MoreSpecific extends MoreSpecific0 {
implicit def _1[A, B <: A]: MoreSpecific[A, B] { type Out = B } = null
}
sealed abstract class MoreSpecific0 {
implicit def _2[A, B <: A]: MoreSpecific[B, A] { type Out = B } = null
}

val a = new Foo[CharSequence, Unit]
val b = new Foo[String, Unit]
val c = new Foo[Int, Unit]

// Exiting paste mode, now interpreting.

defined class Foo
defined trait MoreSpecific
defined object MoreSpecific
defined class MoreSpecific0
a: Foo[CharSequence,Unit] = Foo@2f410acf
b: Foo[String,Unit] = Foo@47089e5f
c: Foo[Int,Unit] = Foo@4141d797

scala> a | b
res0: Foo[String,Unit] = Foo@47089e5f

scala> b | a
res1: Foo[String,Unit] = Foo@2f410acf

scala> b | c
<console>:15: error: Illegal `|` operation
b | c
^

scala>

As you can see the happy cases still work as expected but the illegal case is now nicely detected and reported.

I think we can use this strategy to fix this bug in the pb2 DSL.

Cheers,
Mathias

PS: The `CanBeOred` doesn't exist in parboiled 2.1.x (which lives in the `release-2.1` branch, not the master branch)!
You are looking at the `master` branch, which I started version 2.2 in quite a while back. The idea here is to do all the type computations on the macro-level rather than through fancy type magic. However, so far I've not had time to actually explore this further and I'm not even sure that it'll work or that I'll really find the time to really complete version 2.2. Maybe I should simply switch the branches back and make `release-2.1` the master and the current master `release-2.2`.

---
mat...@parboiled.org
http://www.parboiled.org

> --
> You received this message because you are subscribed to the Google Groups "parboiled2.org User List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to parboiled-use...@googlegroups.com.
> Visit this group at https://groups.google.com/group/parboiled-user.
> To view this discussion on the web visit https://groups.google.com/d/msgid/parboiled-user/baad774e-5f23-4542-9c20-c0d881427ffe%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Alexander Myltsev]

OK, fired issue: https://github.com/sirthias/parboiled2/issues/171 

[Mathias Doenitz]

Great.
Thanks!

---
mat...@parboiled.org
http://www.parboiled.org

> To view this discussion on the web visit https://groups.google.com/d/msgid/parboiled-user/6706217b-98fb-44cf-8dfd-75772d70a67c%40googlegroups.com.