From 24bd6dcd943f27667970487afc3dbe965172177b Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 20 Feb 2013 15:28:07 +0100 Subject: Refined tree typing and started on checks MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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. --- src/dotty/tools/dotc/config/ScalaSettings.scala | 1 + src/dotty/tools/dotc/core/Flags.scala | 2 + src/dotty/tools/dotc/core/Trees.scala | 21 +-- src/dotty/tools/dotc/core/TypedTrees.scala | 202 ++++++++++++++++----- src/dotty/tools/dotc/core/pickling/UnPickler.scala | 2 +- 5 files changed, 162 insertions(+), 66 deletions(-) (limited to 'src') 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) } } -- cgit v1.2.3