From 4611bdf0972fc01dfdfa647a0e84e3bccf98ea05 Mon Sep 17 00:00:00 2001
From: Martin Odersky <odersky@gmail.com>
Date: Sat, 8 Mar 2014 19:05:54 +0100
Subject: Appromiximate union types by intersections.

Appromiximate union types by intersections of their common base classes. Controlled by option -Xkeep-unions.
If option is set, no approximation is done.

Motivations for approximating: There are two. First, union types are departure from Scala 2. From time to
time they lead to failure of inference. One example experiences in Dotty was in a foldLeft, where the accumulator
type was inferred to be Tree before and was now a union of two tree specific kinds. Tree was the correct type, whereas
the union type was too specific. These failures are not common (in the Dotty codebase there were 3, I believe), but
they cause considerable difficulty to diagnose. So it seems safer to have a compatibility mode with Scala 2.
The second motivation is that union types can become large and unwieldy. A function like TreeCopier has a result
type consisting of ~ 40 alternatives, where the alternative type would be just Tree.

Once we gain more experience with union types, we might consider flipping the option, and making union types the
default. But for now it is safer this way, I believe.
---
 src/dotty/tools/dotc/core/TypeOps.scala | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

(limited to 'src/dotty/tools/dotc/core/TypeOps.scala')

diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 22a86766b..f9ff42709 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -77,6 +77,37 @@ trait TypeOps { this: Context =>
     def apply(tp: Type) = simplify(tp, this)
   }
 
+  /** Approximate union type by intersection of its dominators.
+   *  See Type#approximateUnion for an explanation.
+   */
+  def approximateUnion(tp: Type): Type = {
+    /** a faster version of cs1 intersect cs2 */
+    def intersect(cs1: List[ClassSymbol], cs2: List[ClassSymbol]): List[ClassSymbol] = {
+      val cs2AsSet = new util.HashSet[ClassSymbol](100)
+      cs2.foreach(cs2AsSet.addEntry)
+      cs1.filter(cs2AsSet.contains)
+    }
+    /** The minimal set of classes in `cs` which derive all other classes in `cs` */
+    def dominators(cs: List[ClassSymbol], accu: List[ClassSymbol]): List[ClassSymbol] = (cs: @unchecked) match {
+      case c :: rest =>
+        val accu1 = if (accu exists (_ derivesFrom c)) accu else c :: accu
+        if (cs == c.baseClasses) accu1 else dominators(rest, accu1)
+    }
+    if (ctx.featureEnabled(defn.LanguageModuleClass, nme.keepUnions)) tp
+    else tp match {
+      case tp: OrType =>
+        val commonBaseClasses = tp.mapReduceOr(_.baseClasses)(intersect)
+        val doms = dominators(commonBaseClasses, Nil)
+        doms.map(tp.baseTypeWithArgs).reduceLeft(AndType.apply)
+      case tp @ AndType(tp1, tp2) =>
+        tp derived_& (approximateUnion(tp1), approximateUnion(tp2))
+      case tp: RefinedType =>
+        tp.derivedRefinedType(approximateUnion(tp.parent), tp.refinedName, tp.refinedInfo)
+      case _ =>
+        tp
+    }
+  }
+
   /** A type is volatile if its DNF contains an alternative of the form
    *  {P1, ..., Pn}, {N1, ..., Nk}, where the Pi are parent typerefs and the
    *  Nj are refinement names, and one the 4 following conditions is met:
-- 
cgit v1.2.3