js.| union type

[sjrd]

Edit: the original proposal was to name it \/.

It would be worth thinking about a union type constructor for facade types. Similar to js.UndefOr[+A] in its construction, js.|[+A, +B], or whatever it's called, would represent a value of type A or B. It would have zero API, though. The basic idea is the following:

@RawJSType // don't do this at home
sealed trait |[+A, +B]

object | {
  implicit def fromA[A](a: A): A | Nothing = a.asInstanceOf[A | Nothing]
  implicit def fromB[B](b: B): Nothing | B = b.asInstanceOf[Nothing | B]
}

Then of course we need ways to transitively convert an A, a B, or a C to an A | B | C. This probably needs a bit of recursive implicit magic. Even trickier: convert A | B, A | C and B | C to A | B | C ^^

[guersam]

+1, it would cover some tricky cases that can't be solved by overloading.

[sjrd]

So, I had this almost working implicit magic:

@scala.scalajs.js.annotation.RawJSType // Don't do this at home!
sealed trait \/[+A, +B]

object \/ {
  trait Evidence[-A, +B] {
    def apply(a: A): B
  }

  private object CastEvidence extends Evidence[Any, Any] {
    def apply(a: Any): Any = a
  }

  implicit def evBase[A]: Evidence[A, A] =
    CastEvidence.asInstanceOf[Evidence[A, A]]

  implicit def evA[A, A2](implicit ev: Evidence[A, A2]): Evidence[A, (A2 \/ Nothing)] =
    CastEvidence.asInstanceOf[Evidence[A, (A2 \/ Nothing)]]

  implicit def evB[B, B2](implicit ev: Evidence[B, B2]): Evidence[B, (Nothing \/ B2)] =
    CastEvidence.asInstanceOf[Evidence[B, (Nothing \/ B2)]]

  implicit def from[A, B <: _ \/ _](a: A)(implicit ev: Evidence[A, B]): B =
    ev(a)
}

which is basically able to resolve everything if from is called explicitly. For example, this works:

val x: Int \/ String \/ Boolean = from("hello")

but it cannot call from implicitly. So this does not work:

val x: Int \/ String \/ Boolean = "hello"

After investigation with Denys, it appears that the latter results in a diverging implicit expansion, which is caused by the heuristics that the compiler uses to detect infinite expansion. Although it's not infinite in this case, the compiler thinks so. This is because the implicit Evidence required by from (Evidence[String, Int \/ String \/ Boolean]) is "bigger" (or equal I guess) than the initial implicit conversion required (String => Int \/ String \/ Boolean).

Denys thinks that implementing from as macro that does not take any implicit evidence, but that asks for an implicit evidence itself, will work. Because then the "initial" implicit search is already the big Evidence.

[sjrd]

I nailed it, and without any macro! :D I had to abandon covariance of \/, though. But that's fine, because I can "restore" it using an additional implicit conversion ^^

@scala.scalajs.js.annotation.RawJSType // Don't do this at home!
sealed trait \/[A, B]

object \/ {
  /** Evidence that `A <: B`, taking top-level `\/`-types into account. */
  sealed trait Evidence[-A, +B]

  object Evidence {
    /** A unique (and typically dead-code-eliminated away) instance of
     *  `Evidence`.
     */
    private object ReusableEvidence extends Evidence[Any, Any]

    /** `A <: A`. */
    implicit def base[A]: Evidence[A, A] =
      ReusableEvidence.asInstanceOf[Evidence[A, A]]

    /** If `A <: B1`, then `A <: B1 \/ B2`. */
    implicit def left[A, B1, B2](implicit ev: Evidence[A, B1]): Evidence[A, B1 \/ B2] =
      ReusableEvidence.asInstanceOf[Evidence[A, B1 \/ B2]]

    /** If `A <: B2`, then `A <: B1 \/ B2`. */
    implicit def right[A, B1, B2](implicit ev: Evidence[A, B2]): Evidence[A, B1 \/ B2] =
      ReusableEvidence.asInstanceOf[Evidence[A, B1 \/ B2]]

    /** If `A1 <: B1` and `A2 <: B2`, then `A1 \/ A2 <: B1 \/ B2`.
     *  This basically encodes covariance.
     */
    implicit def upcast[A1, A2, B1, B2](implicit ev1: Evidence[A1, B1],
        ev2: Evidence[A2, B2]): Evidence[A1 \/ A2, B1 \/ B2] =
      ReusableEvidence.asInstanceOf[Evidence[A1 \/ A2, B1 \/ B2]]

    /** `Int <: Double`, because that's true in Scala.js. */
    implicit def intDouble: Evidence[Int, Double] =
      ReusableEvidence.asInstanceOf[Evidence[Int, Double]]
  }

  /** Upcast `A` to `B1 \/ B2`.
   *
   *  This needs evidence that `A <: B1 \/ B2`.
   */
  implicit def from[A, B1, B2](a: A)(implicit ev: Evidence[A, B1 \/ B2]): B1 \/ B2 =
    a.asInstanceOf[B1 \/ B2]
}

[gzm0]

Hmm... I guess abandoning covariance is fine, because the union type won't play well in variant positions inside generics anyways:

val s0 = Seq.empty[Int]
val s1: Seq[Int \/ String] = s0 // type error, needs a (noop) map

[sjrd]

Yes, that too.

[sjrd]

Oh, and for the record, a WiP implem is available at master...sjrd:union-type
It includes positive test cases.

[sjrd]

I pushed the thing further, and now it supports arbitrary permutations of base types, as well as arbitrary subsetting of base types, and even partial "aggregation" of subsets of base types with upper bounds.

It's available on the same branch (see previous comment)

[godenji]

Really nice.

Question:
A \/ B, ok, but why not the everyone-immediately-gets-it, A Or B?

Scala has a bad rep in the operator overloading department; don't see a reason to choose \/ over Or in this case beyond it being known to Scalaz users. Certainly neither easier to type nor easier to read...

[gzm0]

I think that's a very valid point. I think this would also align nicer with UndefOr.

[sjrd]

True, it makes more sense wrt. UndefOr ...

[gzm0]

Note that having a js. prefix does not work with infix notation. So we might want to consider jsOr.

[benjaminjackman]

I only had aspirations to get this to type the input variables to functions for facades, the motivator being making the Typescript translator work. (To that end #1820 also helps a great deal, one remaining one would be to get the "string literal".type stuff working but i think that is more gimmicky and less frequently encountered).

1. I'd suggest using | rather than jsOr or or or \/ for the name then the syntax will be identical to typescript. Unlike a lot of uses of symbolic operators this | is actually doing exactly what everyone would expect with regard to types and is similar to the syntax used in other languages.
2. Here was my type-checker friendly only (as much as I wish scala had a union types, I was just using it for facades) version
   Note that I add to keep adding higher arities of implicits to get it to work for higher levels of |.
3. BY FAR The biggest problem I have encountered in adding unions into the scala language using the method is the lack of exhaustiveness checking on matching (this is going on several failed attempts over the last 5 years). We settled on just making single value case class wrappers with sealed traits at the top, ie we used inheritance, however that ends up being tons of boilerplate.

edit: clean things up a bit.
edit2: cleaned things up a lot ... sorry.

[benjaminjackman]

Here is the version I have been experimenting with:

object | {
  implicit def t1ToU2[T](x: T): T | Nothing = x.asInstanceOf[T | Nothing]
  implicit def t2ToU2[T](x: T): Nothing | T = x.asInstanceOf[Nothing | T]

  implicit def t1ToU3[T](x: T): T | Nothing | Nothing = x.asInstanceOf[T | Nothing | Nothing]
  implicit def t2ToU3[T](x: T): Nothing | T | Nothing = x.asInstanceOf[Nothing | T | Nothing]

  implicit def t1ToU4[T](x: T): T | Nothing | Nothing | Nothing = x.asInstanceOf[T | Nothing | Nothing | Nothing]
  implicit def t2ToU4[T](x: T): Nothing | T | Nothing | Nothing = x.asInstanceOf[Nothing | T | Nothing | Nothing]
}

trait |[+T1, +T2] extends js.Object

class A
class B
class C
class D

trait Foo extends js.Object {
  def ab(x: A | B): js.Any = js.native
  def abc(x: A | B | C): js.Any = js.native
  def abcd(x: A | B | C | D): js.Any = js.native
}

object Bar {

  val a = new A
  val b = new B
  val c = new C
  val d = new D

  val x: Foo = null

  x.ab(a) //Compiles
  x.ab(b) //This too

  //  x.stringOrInt(5.0) //Nope

  x.abc(a) //Ok
  x.abc(b) //Ok
  x.abc(c) //Ok

  x.abcd(a) //Ok
  x.abcd(b) //Ok
  x.abcd(c) //Ok
  x.abcd(d) //Ok
}