From f87153bc5d74f66e2fcf22dc7282da31813430da Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 7 Aug 2014 20:25:23 +0200 Subject: Detect cycles and protected legal ones with LazyRefs Cycles are now detected early, when an info is first completed. Legal, f-bounded cycles are broken by a LazyRef, which will construct its type lazily. This makes checkBounds validation of AppliedTypeTrees work (in FirstTransform). Formerly, this stackoverflowed despite the laziness precautions in findMember. Todo: Do the same for class files coming from Java and Scala 2.x. --- src/dotty/tools/dotc/core/SymDenotations.scala | 2 + src/dotty/tools/dotc/core/TypeComparer.scala | 7 +- src/dotty/tools/dotc/core/Types.scala | 31 ++++- .../tools/dotc/transform/FirstTransform.scala | 3 - src/dotty/tools/dotc/typer/Checking.scala | 144 +++++++++++++++++++-- src/dotty/tools/dotc/typer/ErrorReporting.scala | 14 +- src/dotty/tools/dotc/typer/Namer.scala | 6 +- 7 files changed, 179 insertions(+), 28 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala index fcc01503f..fd47ee4ec 100644 --- a/src/dotty/tools/dotc/core/SymDenotations.scala +++ b/src/dotty/tools/dotc/core/SymDenotations.scala @@ -1471,6 +1471,8 @@ object SymDenotations { def complete(denot: SymDenotation)(implicit ctx: Context): Unit = unsupported("complete") } + object NoCompleter extends NoCompleter + /** A lazy type for modules that points to the module class. * Needed so that `moduleClass` works before completion. * Completion of modules is always completion of the underlying diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 1e1d02be2..797712459 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -315,7 +315,8 @@ class TypeComparer(initctx: Context) extends DotClass { private def rebase(tp: NamedType): Type = { def rebaseFrom(prefix: Type): Type = { rebaseQual(prefix, tp.name, considerBoth = true) match { - case rt: RefinedType if rt ne prefix => tp.derivedSelect(RefinedThis(rt)) + case rt: RefinedType if rt ne prefix => + tp.derivedSelect(RefinedThis(rt)).dealias // dealias to short-circuit cycles spanning type aliases or LazyRefs case _ => tp } } @@ -511,6 +512,8 @@ class TypeComparer(initctx: Context) extends DotClass { case NoType => true } compareWild + case tp2: LazyRef => + isSubType(tp1, tp2.ref) case tp2: AnnotatedType => isSubType(tp1, tp2.tpe) // todo: refine? case AndType(tp21, tp22) => @@ -568,6 +571,8 @@ class TypeComparer(initctx: Context) extends DotClass { case _ => true } compareWild + case tp1: LazyRef => + isSubType(tp1.ref, tp2) case tp1: AnnotatedType => isSubType(tp1.tpe, tp2) case ErrorType => diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 592b7b55f..a81d200d3 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -31,6 +31,8 @@ import language.implicitConversions object Types { + private var recCount = 0 + /** The class of types. * The principal subclasses and sub-objects are as follows: * @@ -379,6 +381,8 @@ object Types { * flags in `excluded` from consideration. */ final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = try { + recCount += 1 + assert(recCount < 20) @tailrec def go(tp: Type): Denotation = tp match { case tp: RefinedType => if (name eq tp.refinedName) goRefined(tp) else go(tp.parent) @@ -436,8 +440,10 @@ object Types { case ex: MergeError => throw new MergeError(s"${ex.getMessage} as members of type ${pre.show}") case ex: Throwable => - println(s"error occurred during: $this: ${this.widen} member $name") + println(i"findMember exception for $this: ${this.widen} member $name") throw ex // DEBUG + } finally { + recCount -= 1 } /** The set of names of members of this type that pass the given name filter @@ -599,7 +605,9 @@ object Types { case _ => this } - /** Follow aliases until type is no longer an alias type. */ + /** Follow aliases and derefernces LazyRefs and instantiated TypeVars until type + * is no longer alias type, LazyRef, or instantiated type variable. + */ final def dealias(implicit ctx: Context): Type = this match { case tp: TypeRef => tp.info match { @@ -609,6 +617,8 @@ object Types { case tp: TypeVar => val tp1 = tp.instanceOpt if (tp1.exists) tp1.dealias else tp + case tp: LazyRef => + tp.ref.dealias case tp => tp } @@ -643,6 +653,14 @@ object Types { case _ => NoType } + /** The chain of underlying types as long as type is a TypeProxy. + * Useful for diagnostics + */ + def underlyingChain(implicit ctx: Context): List[Type] = this match { + case tp: TypeProxy => tp :: tp.underlying.underlyingChain + case _ => Nil + } + /** A prefix-less termRef to a new skolem symbol that has the given type as info */ def narrow(implicit ctx: Context): TermRef = TermRef(NoPrefix, ctx.newSkolem(this)) @@ -1469,6 +1487,12 @@ object Types { unique(new CachedConstantType(value)) } + case class LazyRef(refFn: () => Type) extends UncachedProxyType with TermType { + lazy val ref = refFn() + override def underlying(implicit ctx: Context) = ref + override def toString = s"LazyRef($ref)" + } + // --- Refined Type --------------------------------------------------------- /** A refined type parent { refinement } @@ -2408,6 +2432,9 @@ object Types { case tp @ SuperType(thistp, supertp) => tp.derivedSuperType(this(thistp), this(supertp)) + case tp: LazyRef => + LazyRef(() => this(tp.ref)) + case tp: ClassInfo => mapClassInfo(tp) diff --git a/src/dotty/tools/dotc/transform/FirstTransform.scala b/src/dotty/tools/dotc/transform/FirstTransform.scala index dbf4f3a2f..d7010e821 100644 --- a/src/dotty/tools/dotc/transform/FirstTransform.scala +++ b/src/dotty/tools/dotc/transform/FirstTransform.scala @@ -83,14 +83,11 @@ class FirstTransform extends TreeTransform with IdentityDenotTransformer { thisT override def transformOther(tree: Tree)(implicit ctx: Context, info: TransformerInfo) = tree match { case tree: Import => EmptyTree case tree: NamedArg => tree.arg -/* not yet enabled case AppliedTypeTree(tycon, args) => - val tparams = tycon.tpe.typeSymbol.typeParams Checking.checkBounds( args, tparams.map(_.info.bounds), (tp, argTypes) => tp.substDealias(tparams, argTypes)) TypeTree(tree.tpe).withPos(tree.pos) -*/ case tree => if (tree.isType) TypeTree(tree.tpe, tree).withPos(tree.pos) else tree diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala index 7da00e051..cd2e9b55f 100644 --- a/src/dotty/tools/dotc/typer/Checking.scala +++ b/src/dotty/tools/dotc/typer/Checking.scala @@ -4,8 +4,16 @@ package typer import core._ import ast._ -import Contexts._, Types._, Flags._, Denotations._, Names._, StdNames._, NameOps._, Symbols._ -import Trees._, ProtoTypes._ +import Contexts._ +import Types._ +import Flags._ +import Denotations._ +import Names._ +import StdNames._ +import NameOps._ +import Symbols._ +import Trees._ +import ProtoTypes._ import Constants._ import Scopes._ import annotation.unchecked @@ -14,13 +22,125 @@ import util.{Stats, SimpleMap} import util.common._ import Decorators._ import Uniques._ -import ErrorReporting.{errorType, DiagnosticString} +import ErrorReporting.{err, errorType, DiagnosticString} import config.Printers._ import collection.mutable +import SymDenotations.NoCompleter + +object Checking { + import tpd._ + + /** A general checkBounds method that can be used for TypeApply nodes as + * well as for AppliedTypeTree nodes. + */ + def checkBounds(args: List[tpd.Tree], bounds: List[TypeBounds], instantiate: (Type, List[Type]) => Type)(implicit ctx: Context) = { + val argTypes = args.tpes + for ((arg, bounds) <- args zip bounds) { + def notConforms(which: String, bound: Type) = { + ctx.error( + d"Type argument ${arg.tpe} does not conform to $which bound $bound ${err.whyNoMatchStr(arg.tpe, bound)}", + arg.pos) + } + def checkOverlapsBounds(lo: Type, hi: Type): Unit = { + //println(i"instantiating ${bounds.hi} with $argTypes") + //println(i" = ${instantiate(bounds.hi, argTypes)}") + val hiBound = instantiate(bounds.hi, argTypes) + if (!(lo <:< hiBound)) notConforms("upper", hiBound) + if (!(bounds.lo <:< hi)) notConforms("lower", bounds.lo) + } + arg.tpe match { + case TypeBounds(lo, hi) => checkOverlapsBounds(lo, hi) + case tp => checkOverlapsBounds(tp, tp) + } + } + } + + /** A type map which checks that the only cycles in a type are F-bounds + * and that protects all F-bounded references by LazyRefs. + */ + class CheckNonCyclicMap(implicit ctx: Context) extends TypeMap { + + /** Are cycles allowed within nested refinedInfos of currently checked type? */ + private var nestedCycleOK = false + + /** Are cycles allwoed within currently checked type? */ + private var cycleOK = false + + /** A diagnostic output string that indicates the position of the last + * part of a type bounds checked by checkInfo. Possible choices: + * alias, lower bound, upper bound. + */ + var where: String = "" + + /** Check info `tp` for cycles. Throw CyclicReference for illegal cycles, + * break direct cycle with a LazyRef for legal, F-bounded cycles. + */ + def checkInfo(tp: Type): Type = tp match { + case tp @ TypeBounds(lo, hi) => + if (lo eq hi) + try tp.derivedTypeAlias(apply(lo)) + finally where = "alias" + else { + val lo1 = try apply(lo) finally where = "lower bound" + val saved = nestedCycleOK + nestedCycleOK = true + try tp.derivedTypeBounds(lo1, apply(hi)) + finally { + nestedCycleOK = saved + where = "upper bound" + } + } + case _ => + tp + } + + def apply(tp: Type) = tp match { + case tp @ RefinedType(parent, name) => + val parent1 = this(parent) + val saved = cycleOK + cycleOK = nestedCycleOK + try tp.derivedRefinedType(parent1, name, this(tp.refinedInfo)) + finally cycleOK = saved + case tp @ TypeRef(pre, name) => + try { + // Check info of typeref recursively, marking the referred symbol + // with NoCompleter. This provokes a CyclicReference when the symbol + // is hit again. Without this precaution we could stackoverflow here. + val info = tp.info + val symInfo = tp.symbol.info + if (tp.symbol.exists) tp.symbol.info = SymDenotations.NoCompleter + try checkInfo(info) + finally if (tp.symbol.exists) tp.symbol.info = symInfo + tp + } catch { + case ex: CyclicReference => + ctx.debuglog(i"cycle detected for $tp, $nestedCycleOK, $cycleOK") + if (cycleOK) LazyRef(() => tp) else throw ex + } + case _ => mapOver(tp) + } + } +} trait Checking { import tpd._ + import Checking._ + + /** Check that `info` of symbol `sym` is not cyclic. + * @pre sym is not yet initialized (i.e. its type is a Completer). + * @return `info` where every legal F-bounded reference is proctected + * by a `LazyRef`, or `ErrorType` if a cycle was detected and reported. + */ + def checkNonCyclic(sym: Symbol, info: TypeBounds)(implicit ctx: Context): Type = { + val checker = new CheckNonCyclicMap + try checker.checkInfo(info) + catch { + case ex: CyclicReference => + ctx.error(i"illegal cyclic reference: ${checker.where} $info of $sym refers back to the type itself", sym.pos) + ErrorType + } + } /** Check that Java statics and packages can only be used in selections. */ @@ -32,17 +152,13 @@ trait Checking { tree } - /** Check that type arguments `args` conform to corresponding bounds in `poly` */ - def checkBounds(args: List[tpd.Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit = { - val argTypes = args.tpes - def substituted(tp: Type) = tp.substParams(poly, argTypes) - for ((arg, bounds) <- args zip poly.paramBounds) { - def notConforms(which: String, bound: Type) = - ctx.error(d"Type argument ${arg.tpe} does not conform to $which bound $bound", arg.pos) - if (!(arg.tpe <:< substituted(bounds.hi))) notConforms("upper", bounds.hi) - if (!(bounds.lo <:< arg.tpe)) notConforms("lower", bounds.lo) - } - } + /** Check that type arguments `args` conform to corresponding bounds in `poly` + * Note: This does not check the bounds of AppliedTypeTrees. These + * are handled by method checkBounds in FirstTransform + * TODO: remove pos parameter + */ + def checkBounds(args: List[tpd.Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit = Checking.checkBounds( + args, poly.paramBounds, (tp, argTypes) => tp.substParams(poly, argTypes)) /** Check that type `tp` is stable. */ def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Unit = diff --git a/src/dotty/tools/dotc/typer/ErrorReporting.scala b/src/dotty/tools/dotc/typer/ErrorReporting.scala index f20d25792..1f55df2bc 100644 --- a/src/dotty/tools/dotc/typer/ErrorReporting.scala +++ b/src/dotty/tools/dotc/typer/ErrorReporting.scala @@ -97,19 +97,21 @@ object ErrorReporting { errorTree(tree, typeMismatchStr(tree.tpe, pt) + implicitFailure.postscript) } + /** A subtype log explaining why `found` does not conform to `expected` */ + def whyNoMatchStr(found: Type, expected: Type) = + if (ctx.settings.explaintypes.value) + "\n" + ctx.typerState.show + "\n" + TypeComparer.explained((found <:< expected)(_)) + else + "" + def typeMismatchStr(found: Type, expected: Type) = disambiguated { implicit ctx => - val (typerStateStr, explanationStr) = - if (ctx.settings.explaintypes.value) - ("\n" + ctx.typerState.show, "\n" + TypeComparer.explained((found <:< expected)(_))) - else - ("", "") def infoStr = found match { // DEBUG case tp: TypeRef => s"with info ${tp.info} / ${tp.prefix.toString} / ${tp.prefix.dealias.toString}" case _ => "" } d"""type mismatch: | found : $found - | required: $expected""".stripMargin + typerStateStr + explanationStr + | required: $expected""".stripMargin + whyNoMatchStr(found, expected) } } diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index 14404e220..afa270d46 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -674,9 +674,11 @@ class Namer { typer: Typer => if (needsLambda) rhsType.LambdaAbstract(tparamSyms) else if (toParameterize) rhsType.parameterizeWith(tparamSyms) else rhsType - rhsType match { - case _: TypeBounds => abstractedRhsType + val unsafeInfo = rhsType match { + case _: TypeBounds => abstractedRhsType.asInstanceOf[TypeBounds] case _ => TypeAlias(abstractedRhsType, if (sym is Local) sym.variance else 0) } + sym.info = NoCompleter + checkNonCyclic(sym, unsafeInfo) } } \ No newline at end of file -- cgit v1.2.3