Deduplicate union types

[agluszak]

Minimized code

def test[A, B](a: A, b: B): A | B = a                                    
val v0 = test("string", 1)
val v1 = test(1, "string")
val v2 = test(v0, v1)
val v3 = test(v1, v0)
val v4 = test(v2, v3)
val v5 = test(v3, v2)
val v6 = test(v4, v5)

Output

val v0: String | Int = string
val v1: Int | String = 1
val v2: String | Int | (Int | String) = string
val v3: Int | String | (String | Int) = 1
val v4: String | Int | (Int | String) | (Int | String | (String | Int)) = string
val v5: Int | String | (String | Int) | (String | Int | (Int | String)) = 1
val v6: String | Int | (Int | String) | (Int | String | (String | Int)) | (Int | String | (String | Int) | (String | Int | (Int | String))) = string

Expectation

I'd expect all vN values to have type String | Int. Initially I thought that only printing in the REPL was affected, but compilation time also grows exponentially.

[abgruszecki]

I'd expect our compilation time to be worst-case exponential anyway, this is just another way to trigger worst-case behaviour. I believe one can do similar things with tuples.

Arguably the example is almost abusive, though we clearly could do slightly better when instantiating unions of type parameters.

[odersky]

Any concrete ideas how to do better that do not increase compilation times for normal cases?

[abgruszecki]

We discussed this during the lab meeting. One thing which seems feasible to do is to "deduplicate" union types when instantiating polymorphic definitions. We could flatten union types, and then compare all union members and remove those that have the same identity. We don't want to do subtype comparisons b/c of perf concerns. The implementation probably should modify the .simplify method for simplifying unions.

[tpolecat]

Another example

scala> ("a","b").toList
val res0: List[String | (String | Nothing)] = List(a, b)

[griggt]

scala> (1,2,3).toList
val res0: 
  List[Int | (Int | (Int | 
    scala.Tuple.Fold[scala.Tuple$package.EmptyTuple.type, Nothing, 
      [x, y] =>> x | y
    ]
  ))] = List(1, 2, 3)

[tpolecat]

ok that is sweet

[soronpo]

Maybe the examples should also cover commutative and distributive with &.
X & Y | Y & X
X & (Y | Z) | (X & Y | X & Z)

[johnynek]

In this example: #10693 (comment) we are also missing, what I expect is a law, that A | Nothing == A. Similarly, A | Any = Any.

[Swoorup]

inline def tupleValues[A <: Tuple]: A = 
    inline erasedValue[A] match
        case _ : (t *: ts) => 
            summonInline[t *: ts <:< A](valueOf[t] *: tupleValues[ts])
        case _ : EmptyTuple => 
            summonInline[EmptyTuple <:< A](EmptyTuple)

case class TradeEvent()
case class OrderEvent()

type Trades = "trades"
type Orders = "orders"
type Channel = Trades | Orders

type EventSelector[C] = C match 
  case Trades => TradeEvent 
  case Orders => OrderEvent 

type SelChannel[C] = C match 
  case x *: xs => EventSelector[x] | SelChannel[xs]
  case EmptyTuple => Nothing

inline def subscribe[Channels <: Tuple](using Tuple.Union[Channels] <:< Channel): List[SelChannel[Channels]] = 
  // val channels: List[Channel] = tupleValues[Channels].toList.asInstanceOf[List[Channel]]
  val channels: List[Channel] = tupleValues[Channels].toList
  val s = List(TradeEvent(), OrderEvent())
  s.asInstanceOf[List[SelChannel[Channels]]]

The line

val channels: List[Channel] = tupleValues[Channels].toList

gives the error

Found:    List[
  Channels match {
    case EmptyTuple => Nothing
    case 
      [h, t <: Tuple] =>> 
        scala.runtime.MatchCase[h *: t, h | 
          scala.Tuple.Fold[t, Nothing, [x, y] =>> x | y]
        ]
  }
]
Required: List[Channel]

where:    Channels is a type in method subscribe with bounds <: Tuple

Wonder that should just work too?