Implementation of match/case def including GADT pattern matching.

6 files changed, 87 insertions, 7 deletions

diff --git a/src/dotty/tools/dotc/ast/Trees.scala b/src/dotty/tools/dotc/ast/Trees.scala
index 1941412c6..fd60a100e 100644
--- a/src/dotty/tools/dotc/ast/Trees.scala
+++ b/src/dotty/tools/dotc/ast/Trees.scala
@@ -455,7 +455,7 @@ object Trees {
     type ThisTree[-T >: Untyped] = Match[T]
   }
 
-  /** case pat if guard => body */
+  /** case pat if guard => body; only appears as child of a Match */
   case class CaseDef[-T >: Untyped] private[ast] (pat: Tree[T], guard: Tree[T], body: Tree[T])
     extends Tree[T] {
     type ThisTree[-T >: Untyped] = CaseDef[T]
@@ -663,6 +663,9 @@ object Trees {
     def forwardTo: Tree[T] = shared
   }
 
+  implicit class ListOfTreeDecorator[T <: untpd.Tree](val xs: List[T]) extends AnyVal {
+    def tpes: List[Type] = xs map (_.tpe)
+  }
 
   // ----- Generic Tree Instances, inherited from  `tpt` and `untpd`.
 
diff --git a/src/dotty/tools/dotc/ast/TypedTrees.scala b/src/dotty/tools/dotc/ast/TypedTrees.scala
index a597261ae..cce2f6ab6 100644
--- a/src/dotty/tools/dotc/ast/TypedTrees.scala
+++ b/src/dotty/tools/dotc/ast/TypedTrees.scala
@@ -129,7 +129,7 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo {
   }
 
   def Match(selector: Tree, cases: List[CaseDef])(implicit ctx: Context): Match =
-    untpd.Match(selector, cases).withType(ctx.lub(cases map (_.body.tpe))).checked
+    untpd.Match(selector, cases).withType(ctx.lub(cases.tpes)).checked
 
   def CaseDef(pat: Tree, guard: Tree, body: Tree)(implicit ctx: Context): CaseDef =
     untpd.CaseDef(pat, guard, body).withType(body.tpe).checked
@@ -145,7 +145,7 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo {
 
   def SeqLiteral(elems: List[Tree])(implicit ctx: Context): SeqLiteral =
     SeqLiteral(defn.SeqClass.typeConstructor.appliedTo(
-        ctx.lub(elems map (_.tpe)) :: Nil), elems)
+      ctx.lub(elems map (_.tpe)) :: Nil), elems)
 
   // TODO: Split into Java/Scala eq literals
   def SeqLiteral(tpe: Type, elems: List[Tree])(implicit ctx: Context): SeqLiteral =
@@ -270,7 +270,6 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo {
   def SharedTree(tree: Tree)(implicit ctx: Context): SharedTree =
     Trees.SharedTree(tree).withType(tree.tpe)
 
-
   // ------ Making references ------------------------------------------------------
 
   def refType(sym: Symbol)(implicit ctx: Context): NamedType = NamedType.withSym(sym.owner.thisType, sym)
diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala
index 045a511de..1477e7ab7 100644
--- a/src/dotty/tools/dotc/core/Flags.scala
+++ b/src/dotty/tools/dotc/core/Flags.scala
@@ -286,6 +286,9 @@ object Flags {
   /** Method is assumed to be stable */
   final val Stable = termFlag(25, "<stable>")
 
+  /** Info can be refined during GADT pattern match */
+  final val GADTFlexType = typeFlag(25, "<gadt-flex-type>")
+
   /** A case parameter (or its accessor, or a GADT skolem) */
   final val CaseAccessor = termFlag(26, "<caseaccessor>")
 
diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala
index 634be7cb7..6edc5c973 100644
--- a/src/dotty/tools/dotc/core/Symbols.scala
+++ b/src/dotty/tools/dotc/core/Symbols.scala
@@ -382,6 +382,33 @@ object Symbols {
      */
     def pos: Position = if (coord.isPosition) coord.toPosition else NoPosition
 
+// -------- GADT handling -----------------------------------------------
+
+    /** Perform given operation `op` where this symbol allows tightening of
+     *  its type bounds.
+     */
+    private[dotc] def withGADTFlexType[T](op: () => T)(implicit ctx: Context): () => T = { () =>
+      assert((denot is TypeParam) && denot.owner.isTerm)
+      val saved = denot
+      denot = denot.copySymDenotation(initFlags = denot.flags | GADTFlexType)
+      try op()
+      finally denot = saved
+    }
+
+    /** Disallow tightening of type bounds for this symbol from now on */
+    private[dotc] def resetGADTFlexType()(implicit ctx: Context): Unit = {
+      assert(denot is GADTFlexType)
+      denot = denot.copySymDenotation(initFlags = denot.flags &~ GADTFlexType)
+    }
+
+    /** Change info of this symbol to new, tightened type bounds */
+    private[core] def changeGADTInfo(bounds: TypeBounds)(implicit ctx: Context): Unit = {
+      assert(denot is GADTFlexType)
+      denot = denot.copySymDenotation(info = bounds)
+    }
+
+// -------- Printing --------------------------------------------------------
+
     /** The prefix string to be used when displaying this symbol without denotation */
     protected def prefixString = "Symbol"
 
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index ecd8ec0c4..b52824906 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -162,8 +162,9 @@ class TypeComparer(implicit val ctx: Context) extends DotClass {
   }
 
   def thirdTryNamed(tp1: Type, tp2: NamedType): Boolean = tp2.info match {
-    case TypeBounds(lo, _) =>
-      isSubType(tp1, lo)
+    case TypeBounds(lo2, hi2) =>
+      isSubType(tp1, lo2) ||
+      (tp2.symbol is GADTFlexType) && trySetType(tp2, TypeBounds(lo2 | tp1, hi2))
     case _ =>
       val cls2 = tp2.symbol
       (cls2 == defn.SingletonClass && tp1.isStable
@@ -234,7 +235,12 @@ class TypeComparer(implicit val ctx: Context) extends DotClass {
     case tp1: TypeRef =>
       ((tp1 eq defn.NothingType)
         || (tp1 eq defn.NullType) && tp2.dealias.typeSymbol.isNonValueClass
-        || !tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2))
+        || (tp1.info match {
+              case TypeBounds(lo1, hi1) =>
+                isSubType(hi1, tp2) ||
+                (tp1.symbol is GADTFlexType) && trySetType(tp1, TypeBounds(lo1, hi1 & tp2))
+              case _ => false
+           }))
     case tp1: SingletonType =>
       isSubType(tp1.underlying, tp2)
     case tp1: RefinedType =>
@@ -281,6 +287,10 @@ class TypeComparer(implicit val ctx: Context) extends DotClass {
     }
   }
 
+  def trySetType(tr: NamedType, bounds: TypeBounds): Boolean =
+    (bounds.lo <:< bounds.hi) &&
+    { tr.symbol.changeGADTInfo(bounds); true }
+
   /** A function implementing `tp1` matches `tp2`. */
   final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = tp1 match {
     case tp1: MethodType =>
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index ea1fa3729..32bb4f4d1 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -444,6 +444,44 @@ class Typer extends Namer with Applications with Implicits {
     cpy.Closure(tree, env1, meth1, EmptyTree).withType(ownType)
   }
 
+  def typedMatch(tree: untpd.Match, pt: Type)(implicit ctx: Context) = {
+    val sel1 = typedExpr(tree.selector)
+    val selType =
+      if (isFullyDefined(sel1.tpe)) sel1.tpe
+      else errorType("internal error: type of pattern selector is not fully defined", tree.pos)
+
+    /** gadtSyms = "all type parameters of enclosing methods that appear
+     *              non-variantly in the selector type */
+    val gadtSyms: Set[Symbol] = {
+      val accu = new TypeAccumulator[Set[Symbol]] {
+        def apply(tsyms: Set[Symbol], t: Type): Set[Symbol] = {
+          val tsyms1 = t match {
+            case tr: TypeRef if (tr.symbol is TypeParam) && tr.symbol.owner.isTerm && variance == 0 =>
+              tsyms + tr.symbol
+            case _ =>
+              tsyms
+          }
+          foldOver(tsyms1, t)
+        }
+      }
+      accu(Set.empty, selType)
+    }
+
+    def typedCase(tree: untpd.CaseDef)(implicit ctx: Context): CaseDef = {
+      val doCase: () => CaseDef = () => {
+        val pat1 = typedPattern(tree.pat, selType)
+        gadtSyms foreach (_.resetGADTFlexType)
+        val guard1 = typedExpr(tree.guard, defn.BooleanType)
+        val body1 = typedExpr(tree.body, pt)
+        cpy.CaseDef(tree, pat1, guard1, body1) withType body1.tpe
+      }
+      (doCase /: gadtSyms) ((op, tsym) => tsym.withGADTFlexType(op)) ()
+    }
+
+    val cases1 = tree.cases map (typedCase(_)(ctx.fresh.withNewScope))
+    cpy.Match(tree, sel1, cases1).withType(ctx.lub(cases1.tpes))
+  }
+
   def typedModifiers(mods: untpd.Modifiers)(implicit ctx: Context): Modifiers = {
     val annotations1 = mods.annotations mapconserve typedAnnotation
     if (annotations1 eq mods.annotations) mods.asInstanceOf[Modifiers]