Refined tree typing and started on checks

Function nodes are now no longre typed trees; they are represented instead as blocks: { def $anonfun(…) = …; $anonfun }.

Refined block typing to autiomatically widen some types when they occur as result type of a block.

Started writing check code that enforces Scala's typesystem rules oin typed trees.

5 files changed, 162 insertions, 66 deletions

diff --git a/src/dotty/tools/dotc/config/ScalaSettings.scala b/src/dotty/tools/dotc/config/ScalaSettings.scala
index a6083d7f7..3b3f22406 100644
--- a/src/dotty/tools/dotc/config/ScalaSettings.scala
+++ b/src/dotty/tools/dotc/config/ScalaSettings.scala
@@ -97,6 +97,7 @@ class ScalaSettings extends Settings.SettingGroup {
   val Yhelp = BooleanSetting("-Y", "Print a synopsis of private options.")
   val browse = PhasesSetting("-Ybrowse", "Browse the abstract syntax tree after")
   val check = PhasesSetting("-Ycheck", "Check the tree at the end of")
+  val YcheckTypedTrees = BooleanSetting("-YcheckTypedTrees", "Check all constructured typed trees for type correctness")
   val Yshow = PhasesSetting("-Yshow", "(Requires -Xshow-class or -Xshow-object) Show after")
   val Xcloselim = BooleanSetting("-Yclosure-elim", "Perform closure elimination.")
   val Ycompacttrees = BooleanSetting("-Ycompact-trees", "Use compact tree printer when displaying trees.")
diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala
index ac4f51167..710771fa5 100644
--- a/src/dotty/tools/dotc/core/Flags.scala
+++ b/src/dotty/tools/dotc/core/Flags.scala
@@ -388,6 +388,8 @@ object Flags {
   /** The flags of a type parameter */
   final val TypeParamFlags = Protected | Local
 
+  final val AbstractOrTrait = Trait | Abstract
+
   /** Labeled `private` or `protected[local]` */
   final val PrivateOrLocal = oneOf(Private, Local)
 
diff --git a/src/dotty/tools/dotc/core/Trees.scala b/src/dotty/tools/dotc/core/Trees.scala
index c477a35fe..9b5b2b247 100644
--- a/src/dotty/tools/dotc/core/Trees.scala
+++ b/src/dotty/tools/dotc/core/Trees.scala
@@ -259,13 +259,6 @@ object Trees {
     val pos = cpos union lhs.pos union rhs.pos
   }
 
-  /** (vparams) => body */
-  case class Function[T](vparams: List[ValDef[T]], body: Tree[T])(implicit cpos: Position)
-    extends SymTree[T] with TermTree[T] {
-    type ThisTree[T] = Function[T]
-    val pos = unionPos(cpos union body.pos, vparams)
-  }
-
   /** { stats; expr } */
   case class Block[T](stats: List[Tree[T]], expr: Tree[T])(implicit cpos: Position)
     extends TermTree[T] {
@@ -523,6 +516,12 @@ object Trees {
     val pos = cpos union impl.pos
   }
 
+  /** (vparams) => body */
+  case class Function(vparams: List[ValDef[Nothing]], body: Tree[Nothing])(implicit cpos: Position)
+    extends TermTree[Nothing] {
+    val pos = unionPos(cpos union body.pos, vparams)
+  }
+
   // ----- Helper functions and classes ---------------------------------------
 
   @tailrec final def unionPos(base: Position, trees: List[Tree[_]]): Position = trees match {
@@ -580,10 +579,6 @@ object Trees {
       case tree: Assign[_] if (lhs eq tree.lhs) && (rhs eq tree.rhs) => tree
       case _ => Assign(lhs, rhs).copyAttr(tree)
     }
-    def derivedFunction(vparams: List[ValDef[T]], body: Tree[T]): Function[T] = tree match {
-      case tree: Function[_] if (vparams eq tree.vparams) && (body eq tree.body) => tree
-      case _ => Function(vparams, body).copyAttr(tree)
-    }
     def derivedBlock(stats: List[Tree[T]], expr: Tree[T]): Block[T] = tree match {
       case tree: Block[_] if (stats eq tree.stats) && (expr eq tree.expr) => tree
       case _ => Block(stats, expr).copyAttr(tree)
@@ -726,8 +721,6 @@ object Trees {
         finishNamedArg(tree.derivedNamedArg(name, transform(arg, c)), tree, c, plugins)
       case Assign(lhs, rhs) =>
         finishAssign(tree.derivedAssign(transform(lhs, c), transform(rhs, c)), tree, c, plugins)
-      case Function(vparams, body) =>
-        finishFunction(tree.derivedFunction(transformSub(vparams, c), transform(body, c)), tree, c, plugins)
       case Block(stats, expr) =>
         finishBlock(tree.derivedBlock(transform(stats, c), transform(expr, c)), tree, c, plugins)
       case If(cond, thenp, elsep) =>
@@ -878,8 +871,6 @@ object Trees {
         this(x, arg)
       case Assign(lhs, rhs) =>
         this(this(x, lhs), rhs)
-      case Function(vparams, body) =>
-        this(this(x, vparams), body)
       case Block(stats, expr) =>
         this(this(x, stats), expr)
       case If(cond, thenp, elsep) =>
diff --git a/src/dotty/tools/dotc/core/TypedTrees.scala b/src/dotty/tools/dotc/core/TypedTrees.scala
index eabd2911b..b2df92f50 100644
--- a/src/dotty/tools/dotc/core/TypedTrees.scala
+++ b/src/dotty/tools/dotc/core/TypedTrees.scala
@@ -34,7 +34,6 @@ object TypedTrees {
     type Typed = Trees.Typed[Type]
     type NamedArg = Trees.NamedArg[Type]
     type Assign = Trees.Assign[Type]
-    type Function = Trees.Function[Type]
     type Block = Trees.Block[Type]
     type If = Trees.If[Type]
     type Match = Trees.Match[Type]
@@ -75,132 +74,139 @@ object TypedTrees {
       sym.annotations map (_.tree))
 
     def Ident(tp: NamedType)(implicit ctx: Context): Ident =
-      Trees.Ident(tp.name).withType(tp)
+      Trees.Ident(tp.name).withType(tp).checked
 
     def Select(pre: Tree, tp: NamedType)(implicit ctx: Context): Select =
-      Trees.Select(pre, tp.name).withType(tp)
+      Trees.Select(pre, tp.name).withType(tp).checked
 
     def This(cls: ClassSymbol)(implicit ctx: Context): This =
-      Trees.This(cls.name).withType(cls.thisType)
+      Trees.This(cls.name).withType(cls.thisType).checked
 
     def Super(qual: Tree, mixin: Symbol = NoSymbol)(implicit ctx: Context): Super = {
       val cls = qual.tpe.typeSymbol
       val (owntype, mix) =
         if (mixin.exists) (mixin.typeConstructor, mixin.asType.name)
         else (ctx.glb(cls.info.parents), tpnme.EMPTY)
-      Trees.Super(qual, mix).withType(SuperType(qual.tpe, owntype))
+      Trees.Super(qual, mix).withType(SuperType(qual.tpe, owntype)).checked
     }
 
     def Apply(fn: Tree, args: List[Tree])(implicit ctx: Context): Apply = {
       val fntpe @ MethodType(pnames, ptypes) = fn.tpe
       assert(sameLength(ptypes, args))
-      Trees.Apply(fn, args).withType(fntpe.instantiate(args map (_.tpe)))
+      Trees.Apply(fn, args).withType(fntpe.instantiate(args map (_.tpe))).checked
     }
 
     def TypeApply(fn: Tree, args: List[Tree])(implicit ctx: Context): TypeApply = {
       val fntpe @ PolyType(pnames) = fn.tpe
       assert(sameLength(pnames, args))
-      Trees.TypeApply(fn, args).withType(fntpe.instantiate(args map (_.tpe)))
+      Trees.TypeApply(fn, args).withType(fntpe.instantiate(args map (_.tpe))).checked
     }
 
     def Literal(const: Constant)(implicit ctx: Context): Literal =
-      Trees.Literal(const).withType(const.tpe)
+      Trees.Literal(const).withType(const.tpe).checked
 
     def New(tp: Type)(implicit ctx: Context): New =
-      Trees.New(TypeTree(tp))
+      Trees.New(TypeTree(tp)).withType(tp).checked
 
     def Pair(left: Tree, right: Tree)(implicit ctx: Context): Pair =
-      Trees.Pair(left, right).withType(defn.PairType.appliedTo(left.tpe, right.tpe))
+      Trees.Pair(left, right).withType(defn.PairType.appliedTo(left.tpe, right.tpe)).checked
 
     def Typed(expr: Tree, tpt: Tree)(implicit ctx: Context): Typed =
-      Trees.Typed(expr, tpt).withType(tpt.tpe)
+      Trees.Typed(expr, tpt).withType(tpt.tpe).checked
 
-    def NamedArg(name: Name, arg: Tree)(implicit ctx: Context) =
-      Trees.NamedArg(name, arg).withType(arg.tpe)
+    def NamedArg(name: TermName, arg: Tree)(implicit ctx: Context) =
+      Trees.NamedArg(name, arg).withType(arg.tpe).checked
 
     def Assign(lhs: Tree, rhs: Tree)(implicit ctx: Context): Assign =
-      Trees.Assign(lhs, rhs).withType(defn.UnitType)
-
-    def Function(vparams: List[ValDef], body: Tree)(implicit ctx: Context): Function =
-      Trees.Function(vparams, body)
-        .withType(defn.FunctionType(vparams map (_.tpt.tpe), body.tpe))
-
-    def Block(stats: List[Tree], expr: Tree)(implicit ctx: Context): Block =
-      Trees.Block(stats, expr).withType(expr.tpe) // !!! need to make sure that type does not refer to locals
+      Trees.Assign(lhs, rhs).withType(defn.UnitType).checked
+
+    def Block(stats: List[Tree], expr: Tree)(implicit ctx: Context): Block = {
+      lazy val locals = localSyms(stats)
+      val blk = Trees.Block(stats, expr)
+      def widen(tp: Type): Type = tp match {
+        case tp: TermRef if locals contains tp.symbol =>
+          widen(tp.info)
+        case tp: MethodType =>
+          assert(!tp.isDependent, s"Dependent method type in result of block $blk")
+          defn.FunctionType(tp.paramTypes, widen(tp.resultType))
+        case tp: PolyType =>
+          throw new AssertionError(s"Uninstantiated polytype in result of block $blk")
+        case _ => tp
+      }
+      blk.withType(widen(expr.tpe))
+    }
 
     def If(cond: Tree, thenp: Tree, elsep: Tree)(implicit ctx: Context): If =
-      Trees.If(cond, thenp, elsep).withType(thenp.tpe | elsep.tpe)
+      Trees.If(cond, thenp, elsep).withType(thenp.tpe | elsep.tpe).checked
 
     def Match(selector: Tree, cases: List[CaseDef])(implicit ctx: Context): Match =
-      Trees.Match(selector, cases).withType(ctx.lub(cases map (_.body.tpe)))
+      Trees.Match(selector, cases).withType(ctx.lub(cases map (_.body.tpe))).checked
 
     def CaseDef(pat: Tree, guard: Tree, body: Tree)(implicit ctx: Context): CaseDef =
-      Trees.CaseDef(pat, guard, body).withType(body.tpe)
+      Trees.CaseDef(pat, guard, body).withType(body.tpe).checked
 
     def Return(expr: Tree, from: Ident)(implicit ctx: Context): Return =
-      Trees.Return(expr, from).withType(defn.NothingType)
+      Trees.Return(expr, from).withType(defn.NothingType).checked
 
     def Throw(expr: Tree)(implicit ctx: Context): Throw =
-      Trees.Throw(expr).withType(defn.NothingType)
+      Trees.Throw(expr).withType(defn.NothingType).checked
 
     def ArrayValue(elemtpt: Tree, elems: List[Tree])(implicit ctx: Context): ArrayValue =
-      Trees.ArrayValue(elemtpt, elems).withType(defn.ArrayType.appliedTo(elemtpt.tpe))
+      Trees.ArrayValue(elemtpt, elems).withType(defn.ArrayType.appliedTo(elemtpt.tpe)).checked
 
     def TypeTree(tp: Type, original: Tree = EmptyTree)(implicit ctx: Context): TypeTree =
-      Trees.TypeTree(original).withType(tp)
+      Trees.TypeTree(original).withType(tp).checked
 
     def SingletonTypeTree(ref: Tree)(implicit ctx: Context): SingletonTypeTree =
-      Trees.SingletonTypeTree(ref).withType(ref.tpe)
+      Trees.SingletonTypeTree(ref).withType(ref.tpe).checked
 
     def SelectFromTypeTree(qualifier: Tree, name: TypeName)(implicit ctx: Context): SelectFromTypeTree =
-      Trees.SelectFromTypeTree(qualifier, name).withType(TypeRef(qualifier.tpe, name))
+      Trees.SelectFromTypeTree(qualifier, name).withType(TypeRef(qualifier.tpe, name)).checked
 
     def AndTypeTree(left: Tree, right: Tree)(implicit ctx: Context): AndTypeTree =
-      Trees.AndTypeTree(left, right).withType(left.tpe & right.tpe)
+      Trees.AndTypeTree(left, right).withType(left.tpe & right.tpe).checked
 
     def OrTypeTree(left: Tree, right: Tree)(implicit ctx: Context): OrTypeTree =
-      Trees.OrTypeTree(left, right).withType(left.tpe | right.tpe)
+      Trees.OrTypeTree(left, right).withType(left.tpe | right.tpe).checked
 
     def RefineTypeTree(tpt: Tree, refinements: List[DefTree])(implicit ctx: Context): RefineTypeTree = {
       def refineType(tp: Type, refinement: Symbol): Type =
         RefinedType(tp, refinement.name, refinement.info)
       Trees.RefineTypeTree(tpt, refinements)
-        .withType((tpt.tpe /: (refinements map (_.symbol)))(refineType))
+        .withType((tpt.tpe /: (refinements map (_.symbol)))(refineType)).checked
     }
 
     def refineType(tp: Type, refinement: Symbol)(implicit ctx: Context): Type =
       RefinedType(tp, refinement.name, refinement.info)
 
     def AppliedTypeTree(tpt: Tree, args: List[Tree])(implicit ctx: Context): AppliedTypeTree =
-      Trees.AppliedTypeTree(tpt, args).withType(tpt.tpe.appliedTo(args map (_.tpe)))
+      Trees.AppliedTypeTree(tpt, args).withType(tpt.tpe.appliedTo(args map (_.tpe))).checked
 
     def TypeBoundsTree(lo: Tree, hi: Tree)(implicit ctx: Context): TypeBoundsTree =
-      Trees.TypeBoundsTree(lo, hi).withType(TypeBounds(lo.tpe, hi.tpe))
+      Trees.TypeBoundsTree(lo, hi).withType(TypeBounds(lo.tpe, hi.tpe)).checked
 
     def Bind(sym: Symbol, body: Tree)(implicit ctx: Context): Bind =
-      Trees.Bind(sym.name, body)(defPos(sym)).withType(sym.info)
+      Trees.Bind(sym.name, body)(defPos(sym)).withType(sym.info).checked
 
     def Alternative(trees: List[Tree])(implicit ctx: Context): Alternative =
-      Trees.Alternative(trees).withType(ctx.lub(trees map (_.tpe)))
+      Trees.Alternative(trees).withType(ctx.lub(trees map (_.tpe))).checked
 
     def UnApply(fun: Tree, args: List[Tree])(implicit ctx: Context): UnApply =
       Trees.UnApply(fun, args).withType(fun.tpe match {
         case MethodType(_, paramTypes) => paramTypes.head
-      })
+      }).checked
 
     def refType(sym: Symbol)(implicit ctx: Context) = NamedType(sym.owner.thisType, sym)
 
     def ValDef(sym: TermSymbol, rhs: Tree = EmptyTree)(implicit ctx: Context): ValDef =
       Trees.ValDef(Modifiers(sym), sym.name, TypeTree(sym.info), rhs)(defPos(sym))
-        .withType(refType(sym))
+        .withType(refType(sym)).checked
 
     def DefDef(sym: TermSymbol, rhs: Tree = EmptyTree)(implicit ctx: Context): DefDef = {
 
       val (tparams, mtp) = sym.info match {
         case tp: PolyType =>
-          def paramBounds(trefs: List[TypeRef]): List[Type] =
-            tp.paramBounds map new InstPolyMap(tp, trefs)
-          val tparams = ctx.newTypeParams(sym, tp.paramNames, EmptyFlags, paramBounds)
+          val tparams = ctx.newTypeParams(sym, tp.paramNames, EmptyFlags, tp.instantiateBounds)
           (tparams, tp.instantiate(tparams map (_.typeConstructor)))
         case tp => (Nil, tp)
       }
@@ -219,12 +225,12 @@ object TypedTrees {
       Trees.DefDef(
         Modifiers(sym), sym.name, tparams map TypeDef,
         vparamss map (_ map (ValDef(_))), TypeTree(rtp), rhs)(defPos(sym))
-        .withType(refType(sym))
+        .withType(refType(sym)).checked
     }
 
     def TypeDef(sym: TypeSymbol)(implicit ctx: Context): TypeDef =
       Trees.TypeDef(Modifiers(sym), sym.name, TypeTree(sym.info))(defPos(sym))
-        .withType(refType(sym))
+        .withType(refType(sym)).checked
 
     def ClassDef(cls: ClassSymbol, typeParams: List[TypeSymbol], body: List[Tree])(implicit ctx: Context): ClassDef = {
       val parents = cls.info.parents map (TypeTree(_))
@@ -243,19 +249,19 @@ object TypedTrees {
       val localDummy = ((NoSymbol: Symbol) /: body)(findLocalDummy)
         .orElse(ctx.newLocalDummy(cls))
       val impl = Trees.Template(parents, selfType, rest)
-        .withType(refType(localDummy))
+        .withType(refType(localDummy)).checked
       Trees.ClassDef(Modifiers(cls), cls.name, tparams, impl)(defPos(cls))
-        .withType(refType(cls))
+        .withType(refType(cls)).checked
     }
 
     def Import(expr: Tree, selectors: List[Trees.UntypedTree])(implicit ctx: Context): Import =
-      Trees.Import(expr, selectors).withType(refType(ctx.newImportSymbol(expr)))
+      Trees.Import(expr, selectors).withType(refType(ctx.newImportSymbol(expr))).checked
 
     def PackageDef(pid: RefTree, stats: List[Tree])(implicit ctx: Context): PackageDef =
-      Trees.PackageDef(pid, stats).withType(refType(pid.symbol))
+      Trees.PackageDef(pid, stats).withType(refType(pid.symbol)).checked
 
     def Annotated(annot: Tree, arg: Tree)(implicit ctx: Context): Annotated =
-      Trees.Annotated(annot, arg).withType(AnnotatedType(List(Annotation(annot)), arg.tpe))
+      Trees.Annotated(annot, arg).withType(AnnotatedType(List(Annotation(annot)), arg.tpe)).checked
 
     val EmptyTree: Tree = Trees.EmptyTree[Type]
 
@@ -264,7 +270,7 @@ object TypedTrees {
     def Shared(tree: Tree): Shared =
       Trees.Shared(tree).withType(tree.tpe)
 
-    // -----------------------------------------------------------------------------
+    // ------ Creating typed equivalents of trees that exist only in untyped form -------
 
     def New(tp: Type, args: List[Tree])(implicit ctx: Context): Apply =
       Apply(
@@ -280,6 +286,9 @@ object TypedTrees {
       ValDef(sym, rhs)
     }
 
+    def Function(meth: TermSymbol, body: Tree)(implicit ctx: Context): Block =
+      Block(DefDef(meth, body) :: Nil, Ident(TermRef(NoPrefix, meth)))
+
     private class FindLocalDummyAccumulator(cls: ClassSymbol)(implicit ctx: Context) extends TreeAccumulator[Symbol] {
       def apply(sym: Symbol, tree: Tree) =
         if (sym.exists) sym
@@ -290,6 +299,99 @@ object TypedTrees {
           else sym
         } else foldOver(sym, tree)
     }
+
+    implicit class addChecked[T <: Tree](val tree: T) extends AnyVal {
+      def checked(implicit ctx: Context): T = {
+        if (ctx.settings.YcheckTypedTrees.value) checkType(tree)
+        tree
+      }
+    }
+  }
+
+  import Trees._
+
+  def check(p: Boolean): Unit = assert(p)
+
+  def checkType(tree: tpd.Tree)(implicit ctx: Context): Unit = tree match {
+    case Ident(name) =>
+    case Select(pre, name) =>
+      val mt = pre.tpe.member(name)
+      check(pre.isTerm)
+      check(mt.exists)
+      check((mt filter (_.info <:< tree.tpe)).exists)
+    case This(cls) =>
+    case Super(qual, mixin) =>
+      check(qual.isTerm)
+      val cls = qual.tpe.typeSymbol
+      check(cls.isClass)
+      check(mixin == NoSymbol || (cls.asClass.parents map (_.typeSymbol) contains mixin))
+    case Apply(fn, args) =>
+      def checkArg(arg: tpd.Tree, name: Name, tpe: Type): Unit = {
+        check(arg.isTerm)
+        check(arg.tpe <:< tpe)
+        arg match {
+          case NamedArg(argName, _) => check(argName == name)
+          case _ =>
+        }
+      }
+      fn.tpe match {
+        case MethodType(paramNames, paramTypes) =>
+          (args, paramNames, paramTypes).zipped foreach checkArg
+        case _ =>
+          check(false)
+      }
+    case TypeApply(fn, args) =>
+      fn.tpe match {
+        case pt: PolyType =>
+          val argTypes = args map (_.tpe)
+          check((pt.instantiateBounds(argTypes) corresponds argTypes) (_ contains _))
+        case _ =>
+          check(false)
+      }
+    case Literal(const: Constant) =>
+      try const.tag catch { case ex: Throwable => check(false) }
+    case New(tpt) =>
+      check(tpt.isType)
+      val cls = tpt.tpe.typeSymbol
+      check(cls.isClass)
+      check(!(cls is (AbstractOrTrait)))
+    case Pair(left, right) =>
+      check(left.isTerm)
+      check(right.isTerm)
+    case Typed(expr, tpt) =>
+      check(expr.isTerm)
+      check(tpt.isType)
+      check(expr.tpe <:< tpt.tpe)
+    case NamedArg(name, arg) =>
+      // missing because it cannot be done easily bottom-up:
+      // check that NamedArgs only occur in parameter lists
+    case Assign(lhs, rhs) =>
+      check(rhs.isTerm)
+      lhs.tpe match {
+        case ltpe: TermRef =>
+          check(ltpe.symbol is Mutable)
+        case _ =>
+          check(false)
+      }
+      check(rhs.tpe <:< lhs.tpe)
+    case Block(stats, expr) =>
+      lazy val locals = localSyms(stats)
+      def isNonLocal(sym: Symbol): Boolean =
+        !(locals contains sym) || isHoistableClass(sym)
+      def isHoistableClass(sym: Symbol) =
+        sym.isClass && noLeaksIn(sym.info)
+      def noLeaksIn(tp: Type): Boolean = tp forall {
+        case tp: NamedType => isNonLocal(tp.symbol)
+        case tp: ClassInfo =>
+          noLeaksIn(tp.prefix) &&
+          (tp.parents forall noLeaksIn) &&
+          (tp.decls.toList forall (t => noLeaksIn(t.info)))
+        case _ => true
+      }
+      check(noLeaksIn(tree.tpe))
   }
+
+  def localSyms(stats: List[tpd.Tree])(implicit ctx: Context) =
+    for (stat <- stats if (stat.isDef)) yield stat.symbol
 }
 
diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala
index b12054570..62d970899 100644
--- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala
+++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala
@@ -667,7 +667,7 @@ class UnPickler(bytes: Array[Byte], classRoot: LazyClassDenotation, moduleRoot:
         if (isNameEntry(argref)) {
           val name = at(argref, readName)
           val arg = readClassfileAnnotArg(readNat())
-          NamedArg(name, arg)
+          NamedArg(name.asTermName, arg)
         } else readAnnotArg(argref)
       }
     }