From e3b36c71b8cd5ef02390651ef64892fcd6606b77 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Mon, 4 Mar 2013 13:35:15 +0100 Subject: Carve up Types.scala Step one of a plan to bring some order and thread safety to this neck of the woods. More info: https://gist.github.com/retronym/5081754 https://groups.google.com/forum/?fromgroups=#!topic/scala-internals/MOvmcnbyb_g Note that the sub package is named 'tpe' and not 'Types' to avoid potential problems on case insensitive file systems, given the existing trait 'Types.' --- src/reflect/scala/reflect/internal/Types.scala | 2869 +------------------- .../scala/reflect/internal/tpe/CommonOwners.scala | 50 + .../scala/reflect/internal/tpe/GlbLubs.scala | 592 ++++ .../scala/reflect/internal/tpe/TypeComparers.scala | 617 +++++ .../reflect/internal/tpe/TypeConstraints.scala | 282 ++ .../scala/reflect/internal/tpe/TypeMaps.scala | 1144 ++++++++ .../scala/reflect/internal/tpe/TypeToStrings.scala | 29 + 7 files changed, 2833 insertions(+), 2750 deletions(-) create mode 100644 src/reflect/scala/reflect/internal/tpe/CommonOwners.scala create mode 100644 src/reflect/scala/reflect/internal/tpe/GlbLubs.scala create mode 100644 src/reflect/scala/reflect/internal/tpe/TypeComparers.scala create mode 100644 src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala create mode 100644 src/reflect/scala/reflect/internal/tpe/TypeMaps.scala create mode 100644 src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 365e9a1682..a14938eeb5 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -14,7 +14,6 @@ import Flags._ import scala.util.control.ControlThrowable import scala.annotation.tailrec import util.Statistics -import scala.runtime.ObjectRef import util.ThreeValues._ import Variance._ @@ -73,28 +72,33 @@ import Variance._ // only used during erasure of derived value classes. */ -trait Types extends api.Types { self: SymbolTable => +trait Types + extends api.Types + with tpe.TypeComparers + with tpe.TypeToStrings + with tpe.CommonOwners + with tpe.GlbLubs + with tpe.TypeMaps + with tpe.TypeConstraints { self: SymbolTable => + import definitions._ import TypesStats._ private var explainSwitch = false private final val emptySymbolSet = immutable.Set.empty[Symbol] - private final val LogPendingSubTypesThreshold = 50 - private final val LogPendingBaseTypesThreshold = 50 - private final val LogVolatileThreshold = 50 + protected[internal] final val DefaultLogThreshhold = 50 + private final val LogPendingBaseTypesThreshold = DefaultLogThreshhold + private final val LogVolatileThreshold = DefaultLogThreshhold /** A don't care value for the depth parameter in lubs/glbs and related operations. */ - private final val AnyDepth = -3 + protected[internal] final val AnyDepth = -3 /** Decrement depth unless it is a don't care. */ - private final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1 + protected[internal] final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1 - private final val printLubs = sys.props contains "scalac.debug.lub" private final val traceTypeVars = sys.props contains "scalac.debug.tvar" private final val breakCycles = settings.breakCycles.value - /** In case anyone wants to turn off lub verification without reverting anything. */ - private final val verifyLubs = true /** In case anyone wants to turn off type parameter bounds being used * to seed type constraints. */ @@ -107,80 +111,6 @@ trait Types extends api.Types { self: SymbolTable => */ var skolemizationLevel = 0 - /** A log of type variable with their original constraints. Used in order - * to undo constraints in the case of isSubType/isSameType failure. - */ - lazy val undoLog = newUndoLog - - protected def newUndoLog = new UndoLog - - class UndoLog extends Clearable { - private type UndoPairs = List[(TypeVar, TypeConstraint)] - //OPT this method is public so we can do `manual inlining` - var log: UndoPairs = List() - - /* - * These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog. - * - * The idea behind explicit locking mechanism is that all public methods that access mutable state - * will have to obtain the lock for their entire execution so both reads and writes can be kept in - * right order. Originally, that was achieved by overriding those public methods in - * `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take - * thunk as argument and if we keep them non-final there's no way to make them inlined so thunks - * can go away. - * - * By using explicit locking we can achieve inlining. - * - * NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot - * places implementation of `undo` or `undoUnless`). This should be changed back to protected - * once inliner is fixed. - */ - def lock(): Unit = () - def unlock(): Unit = () - - // register with the auto-clearing cache manager - perRunCaches.recordCache(this) - - /** Undo all changes to constraints to type variables upto `limit`. */ - //OPT this method is public so we can do `manual inlining` - def undoTo(limit: UndoPairs) { - assertCorrectThread() - while ((log ne limit) && log.nonEmpty) { - val (tv, constr) = log.head - tv.constr = constr - log = log.tail - } - } - - /** No sync necessary, because record should only - * be called from within an undo or undoUnless block, - * which is already synchronized. - */ - private[reflect] def record(tv: TypeVar) = { - log ::= ((tv, tv.constr.cloneInternal)) - } - - def clear() { - lock() - try { - if (settings.debug.value) - self.log("Clearing " + log.size + " entries from the undoLog.") - log = Nil - } finally unlock() - } - - // `block` should not affect constraints on typevars - def undo[T](block: => T): T = { - lock() - try { - val before = log - - try block - finally undoTo(before) - } finally unlock() - } - } - /** A map from lists to compound types that have the given list as parents. * This is used to avoid duplication in the computation of base type sequences and baseClasses. * It makes use of the fact that these two operations depend only on the parents, @@ -3725,72 +3655,7 @@ trait Types extends api.Types { self: SymbolTable => newExistentialType(tparams1, tpe1) } - /** Normalize any type aliases within this type (@see Type#normalize). - * Note that this depends very much on the call to "normalize", not "dealias", - * so it is no longer carries the too-stealthy name "deAlias". - */ - object normalizeAliases extends TypeMap { - def apply(tp: Type): Type = tp match { - case TypeRef(_, sym, _) if sym.isAliasType => - def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp" - mapOver(logResult(msg)(tp.normalize)) - case _ => mapOver(tp) - } - } - - /** Remove any occurrence of type from this type and its parents */ - object dropSingletonType extends TypeMap { - def apply(tp: Type): Type = { - tp match { - case TypeRef(_, SingletonClass, _) => - AnyClass.tpe - case tp1 @ RefinedType(parents, decls) => - parents filter (_.typeSymbol != SingletonClass) match { - case Nil => AnyClass.tpe - case p :: Nil if decls.isEmpty => mapOver(p) - case ps => mapOver(copyRefinedType(tp1, ps, decls)) - } - case tp1 => - mapOver(tp1) - } - } - } - - /** Type with all top-level occurrences of abstract types replaced by their bounds */ - object abstractTypesToBounds extends TypeMap { - def apply(tp: Type): Type = tp match { - case TypeRef(_, sym, _) if sym.isAliasType => apply(tp.dealias) - case TypeRef(_, sym, _) if sym.isAbstractType => apply(tp.bounds.hi) - case rtp @ RefinedType(parents, decls) => copyRefinedType(rtp, parents mapConserve this, decls) - case AnnotatedType(_, _, _) => mapOver(tp) - case _ => tp // no recursion - top level only - } - } - - // Set to true for A* => Seq[A] - // (And it will only rewrite A* in method result types.) - // This is the pre-existing behavior. - // Or false for Seq[A] => Seq[A] - // (It will rewrite A* everywhere but method parameters.) - // This is the specified behavior. - protected def etaExpandKeepsStar = false - /** Turn any T* types into Seq[T] except when - * in method parameter position. - */ - object dropIllegalStarTypes extends TypeMap { - def apply(tp: Type): Type = tp match { - case MethodType(params, restpe) => - // Not mapping over params - val restpe1 = apply(restpe) - if (restpe eq restpe1) tp - else MethodType(params, restpe1) - case TypeRef(_, RepeatedParamClass, arg :: Nil) => - seqType(arg) - case _ => - if (etaExpandKeepsStar) tp else mapOver(tp) - } - } // Hash consing -------------------------------------------------------------- @@ -3810,121 +3675,6 @@ trait Types extends api.Types { self: SymbolTable => // Helper Classes --------------------------------------------------------- - /** @PP: Unable to see why these apparently constant types should need vals - * in every TypeConstraint, I lifted them out. - */ - private lazy val numericLoBound = IntClass.tpe - private lazy val numericHiBound = intersectionType(List(ByteClass.tpe, CharClass.tpe), ScalaPackageClass) - - /** A class expressing upper and lower bounds constraints of type variables, - * as well as their instantiations. - */ - class TypeConstraint(lo0: List[Type], hi0: List[Type], numlo0: Type, numhi0: Type, avoidWidening0: Boolean = false) { - def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType) - def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi)) - def this() = this(List(), List()) - - /* Syncnote: Type constraints are assumed to be used from only one - * thread. They are not exposed in api.Types and are used only locally - * in operations that are exposed from types. Hence, no syncing of any - * variables should be ncessesary. - */ - - /** Guard these lists against AnyClass and NothingClass appearing, - * else loBounds.isEmpty will have different results for an empty - * constraint and one with Nothing as a lower bound. [Actually - * guarding addLoBound/addHiBound somehow broke raw types so it - * only guards against being created with them.] - */ - private var lobounds = lo0 filterNot typeIsNothing - private var hibounds = hi0 filterNot typeIsAny - private var numlo = numlo0 - private var numhi = numhi0 - private var avoidWidening = avoidWidening0 - - def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds - def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds - def avoidWiden: Boolean = avoidWidening - - def addLoBound(tp: Type, isNumericBound: Boolean = false) { - // For some reason which is still a bit fuzzy, we must let Nothing through as - // a lower bound despite the fact that Nothing is always a lower bound. My current - // supposition is that the side-effecting type constraint accumulation mechanism - // depends on these subtype tests being performed to make forward progress when - // there are mutally recursive type vars. - // See pos/t6367 and pos/t6499 for the competing test cases. - val mustConsider = tp.typeSymbol match { - case NothingClass => true - case _ => !(lobounds contains tp) - } - if (mustConsider) { - if (isNumericBound && isNumericValueType(tp)) { - if (numlo == NoType || isNumericSubType(numlo, tp)) - numlo = tp - else if (!isNumericSubType(tp, numlo)) - numlo = numericLoBound - } - else lobounds ::= tp - } - } - - def checkWidening(tp: Type) { - if(tp.isStable) avoidWidening = true - else tp match { - case HasTypeMember(_, _) => avoidWidening = true - case _ => - } - } - - def addHiBound(tp: Type, isNumericBound: Boolean = false) { - // My current test case only demonstrates the need to let Nothing through as - // a lower bound, but I suspect the situation is symmetrical. - val mustConsider = tp.typeSymbol match { - case AnyClass => true - case _ => !(hibounds contains tp) - } - if (mustConsider) { - checkWidening(tp) - if (isNumericBound && isNumericValueType(tp)) { - if (numhi == NoType || isNumericSubType(tp, numhi)) - numhi = tp - else if (!isNumericSubType(numhi, tp)) - numhi = numericHiBound - } - else hibounds ::= tp - } - } - - def isWithinBounds(tp: Type): Boolean = - lobounds.forall(_ <:< tp) && - hibounds.forall(tp <:< _) && - (numlo == NoType || (numlo weak_<:< tp)) && - (numhi == NoType || (tp weak_<:< numhi)) - - var inst: Type = NoType // @M reduce visibility? - - def instValid = (inst ne null) && (inst ne NoType) - - def cloneInternal = { - val tc = new TypeConstraint(lobounds, hibounds, numlo, numhi, avoidWidening) - tc.inst = inst - tc - } - - override def toString = { - val boundsStr = { - val lo = loBounds filterNot typeIsNothing - val hi = hiBounds filterNot typeIsAny - val lostr = if (lo.isEmpty) Nil else List(lo.mkString(" >: (", ", ", ")")) - val histr = if (hi.isEmpty) Nil else List(hi.mkString(" <: (", ", ", ")")) - - lostr ++ histr mkString ("[", " | ", "]") - } - if (inst eq NoType) boundsStr - else boundsStr + " _= " + inst.safeToString - } - } - class TypeUnwrapper(poly: Boolean, existential: Boolean, annotated: Boolean, nullary: Boolean) extends (Type => Type) { def apply(tp: Type): Type = tp match { case AnnotatedType(_, underlying, _) if annotated => apply(underlying) @@ -3942,246 +3692,6 @@ trait Types extends api.Types { self: SymbolTable => object unwrapToStableClass extends ClassUnwrapper(existential = false) { } object unwrapWrapperTypes extends TypeUnwrapper(true, true, true, true) { } - trait AnnotationFilter extends TypeMap { - def keepAnnotation(annot: AnnotationInfo): Boolean - - override def mapOver(annot: AnnotationInfo) = - if (keepAnnotation(annot)) super.mapOver(annot) - else UnmappableAnnotation - } - - trait KeepOnlyTypeConstraints extends AnnotationFilter { - // filter keeps only type constraint annotations - def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass - } - - // todo. move these into scala.reflect.api - - /** A prototype for mapping a function over all possible types - */ - abstract class TypeMap(trackVariance: Boolean) extends (Type => Type) { - def this() = this(trackVariance = false) - def apply(tp: Type): Type - - private[this] var _variance: Variance = if (trackVariance) Covariant else Invariant - - def variance_=(x: Variance) = { assert(trackVariance, this) ; _variance = x } - def variance = _variance - - /** Map this function over given type */ - def mapOver(tp: Type): Type = tp match { - case tr @ TypeRef(pre, sym, args) => - val pre1 = this(pre) - val args1 = ( - if (trackVariance && args.nonEmpty && !variance.isInvariant && sym.typeParams.nonEmpty) - mapOverArgs(args, sym.typeParams) - else - args mapConserve this - ) - if ((pre1 eq pre) && (args1 eq args)) tp - else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), args1) - case ThisType(_) => tp - case SingleType(pre, sym) => - if (sym.isPackageClass) tp // short path - else { - val pre1 = this(pre) - if (pre1 eq pre) tp - else singleType(pre1, sym) - } - case MethodType(params, result) => - val params1 = flipped(mapOver(params)) - val result1 = this(result) - if ((params1 eq params) && (result1 eq result)) tp - else copyMethodType(tp, params1, result1.substSym(params, params1)) - case PolyType(tparams, result) => - val tparams1 = flipped(mapOver(tparams)) - val result1 = this(result) - if ((tparams1 eq tparams) && (result1 eq result)) tp - else PolyType(tparams1, result1.substSym(tparams, tparams1)) - case NullaryMethodType(result) => - val result1 = this(result) - if (result1 eq result) tp - else NullaryMethodType(result1) - case ConstantType(_) => tp - case SuperType(thistp, supertp) => - val thistp1 = this(thistp) - val supertp1 = this(supertp) - if ((thistp1 eq thistp) && (supertp1 eq supertp)) tp - else SuperType(thistp1, supertp1) - case TypeBounds(lo, hi) => - val lo1 = flipped(this(lo)) - val hi1 = this(hi) - if ((lo1 eq lo) && (hi1 eq hi)) tp - else TypeBounds(lo1, hi1) - case BoundedWildcardType(bounds) => - val bounds1 = this(bounds) - if (bounds1 eq bounds) tp - else BoundedWildcardType(bounds1.asInstanceOf[TypeBounds]) - case rtp @ RefinedType(parents, decls) => - val parents1 = parents mapConserve this - val decls1 = mapOver(decls) - copyRefinedType(rtp, parents1, decls1) - case ExistentialType(tparams, result) => - val tparams1 = mapOver(tparams) - val result1 = this(result) - if ((tparams1 eq tparams) && (result1 eq result)) tp - else newExistentialType(tparams1, result1.substSym(tparams, tparams1)) - case OverloadedType(pre, alts) => - val pre1 = if (pre.isInstanceOf[ClassInfoType]) pre else this(pre) - if (pre1 eq pre) tp - else OverloadedType(pre1, alts) - case AntiPolyType(pre, args) => - val pre1 = this(pre) - val args1 = args mapConserve this - if ((pre1 eq pre) && (args1 eq args)) tp - else AntiPolyType(pre1, args1) - case tv@TypeVar(_, constr) => - if (constr.instValid) this(constr.inst) - else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params)) //@M !args.isEmpty implies !typeParams.isEmpty - case NotNullType(tp) => - val tp1 = this(tp) - if (tp1 eq tp) tp - else NotNullType(tp1) - case AnnotatedType(annots, atp, selfsym) => - val annots1 = mapOverAnnotations(annots) - val atp1 = this(atp) - if ((annots1 eq annots) && (atp1 eq atp)) tp - else if (annots1.isEmpty) atp1 - else AnnotatedType(annots1, atp1, selfsym) -/* - case ErrorType => tp - case WildcardType => tp - case NoType => tp - case NoPrefix => tp - case ErasedSingleType(sym) => tp -*/ - case _ => - tp - // throw new Error("mapOver inapplicable for " + tp); - } - - def withVariance[T](v: Variance)(body: => T): T = { - val saved = variance - variance = v - try body finally variance = saved - } - @inline final def flipped[T](body: => T): T = { - if (trackVariance) variance = variance.flip - try body - finally if (trackVariance) variance = variance.flip - } - protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = ( - if (trackVariance) - map2Conserve(args, tparams)((arg, tparam) => withVariance(variance * tparam.variance)(this(arg))) - else - args mapConserve this - ) - /** Applies this map to the symbol's info, setting variance = Invariant - * if necessary when the symbol is an alias. - */ - private def applyToSymbolInfo(sym: Symbol): Type = { - if (trackVariance && !variance.isInvariant && sym.isAliasType) - withVariance(Invariant)(this(sym.info)) - else - this(sym.info) - } - - /** Called by mapOver to determine whether the original symbols can - * be returned, or whether they must be cloned. - */ - protected def noChangeToSymbols(origSyms: List[Symbol]): Boolean = { - @tailrec def loop(syms: List[Symbol]): Boolean = syms match { - case Nil => true - case x :: xs => (x.info eq applyToSymbolInfo(x)) && loop(xs) - } - loop(origSyms) - } - - /** Map this function over given scope */ - def mapOver(scope: Scope): Scope = { - val elems = scope.toList - val elems1 = mapOver(elems) - if (elems1 eq elems) scope - else newScopeWith(elems1: _*) - } - - /** Map this function over given list of symbols */ - def mapOver(origSyms: List[Symbol]): List[Symbol] = { - // fast path in case nothing changes due to map - if (noChangeToSymbols(origSyms)) origSyms - // map is not the identity --> do cloning properly - else cloneSymbolsAndModify(origSyms, TypeMap.this) - } - - def mapOver(annot: AnnotationInfo): AnnotationInfo = { - val AnnotationInfo(atp, args, assocs) = annot - val atp1 = mapOver(atp) - val args1 = mapOverAnnotArgs(args) - // there is no need to rewrite assocs, as they are constants - - if ((args eq args1) && (atp eq atp1)) annot - else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation // some annotation arg was unmappable - else AnnotationInfo(atp1, args1, assocs) setPos annot.pos - } - - def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = { - val annots1 = annots mapConserve mapOver - if (annots1 eq annots) annots - else annots1 filterNot (_ eq UnmappableAnnotation) - } - - /** Map over a set of annotation arguments. If any - * of the arguments cannot be mapped, then return Nil. */ - def mapOverAnnotArgs(args: List[Tree]): List[Tree] = { - val args1 = args mapConserve mapOver - if (args1 contains UnmappableTree) Nil - else args1 - } - - def mapOver(tree: Tree): Tree = - mapOver(tree, () => return UnmappableTree) - - /** Map a tree that is part of an annotation argument. - * If the tree cannot be mapped, then invoke giveup(). - * The default is to transform the tree with - * TypeMapTransformer. - */ - def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = - (new TypeMapTransformer).transform(tree) - - /** This transformer leaves the tree alone except to remap - * its types. */ - class TypeMapTransformer extends Transformer { - override def transform(tree: Tree) = { - val tree1 = super.transform(tree) - val tpe1 = TypeMap.this(tree1.tpe) - if ((tree eq tree1) && (tree.tpe eq tpe1)) - tree - else - tree1.shallowDuplicate.setType(tpe1) - } - } - } - - abstract class TypeTraverser extends TypeMap { - def traverse(tp: Type): Unit - def apply(tp: Type): Type = { traverse(tp); tp } - } - - abstract class TypeTraverserWithResult[T] extends TypeTraverser { - def result: T - def clear(): Unit - } - - abstract class TypeCollector[T](initial: T) extends TypeTraverser { - var result: T = _ - def collect(tp: Type) = { - result = initial - traverse(tp) - result - } - } - /** Repack existential types, otherwise they sometimes get unpacked in the * wrong location (type inference comes up with an unexpected skolem) */ @@ -4227,995 +3737,112 @@ trait Types extends api.Types { self: SymbolTable => && isRawIfWithoutArgs(sym) ) - /** The raw to existential map converts a ''raw type'' to an existential type. - * It is necessary because we might have read a raw type of a - * parameterized Java class from a class file. At the time we read the type - * the corresponding class file might still not be read, so we do not - * know what the type parameters of the type are. Therefore - * the conversion of raw types to existential types might not have taken place - * in ClassFileparser.sigToType (where it is usually done). + def singletonBounds(hi: Type) = TypeBounds.upper(intersectionType(List(hi, SingletonClass.tpe))) + + /** + * A more persistent version of `Type#memberType` which does not require + * that the symbol is a direct member of the prefix. + * + * For instance: + * + * {{{ + * class C[T] { + * sealed trait F[A] + * object X { + * object S1 extends F[T] + * } + * class S2 extends F[T] + * } + * object O extends C[Int] { + * def foo(f: F[Int]) = f match {...} // need to enumerate sealed subtypes of the scrutinee here. + * } + * class S3 extends O.F[String] + * + * nestedMemberType(, , ) = O.X.S1.type + * nestedMemberType(, , ) = O.S2.type + * nestedMemberType(, , ) = S3.type + * }}} + * + * @param sym The symbol of the subtype + * @param pre The prefix from which the symbol is seen + * @param owner */ - def rawToExistential = new TypeMap { - private var expanded = immutable.Set[Symbol]() - def apply(tp: Type): Type = tp match { - case TypeRef(pre, sym, List()) if isRawIfWithoutArgs(sym) => - if (expanded contains sym) AnyRefClass.tpe - else try { - expanded += sym - val eparams = mapOver(typeParamsToExistentials(sym)) - existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe))) - } finally { - expanded -= sym + def nestedMemberType(sym: Symbol, pre: Type, owner: Symbol): Type = { + def loop(tp: Type): Type = + if (tp.isTrivial) tp + else if (tp.prefix.typeSymbol isNonBottomSubClass owner) { + val widened = tp match { + case _: ConstantType => tp // Java enum constants: don't widen to the enum type! + case _ => tp.widen // C.X.type widens to C.this.X.type, otherwise `tp asSeenFrom (pre, C)` has no effect. } - case _ => - mapOver(tp) - } - } - /*** - *@M: I think this is more desirable, but Martin prefers to leave raw-types as-is as much as possible - object rawToExistentialInJava extends TypeMap { - def apply(tp: Type): Type = tp match { - // any symbol that occurs in a java sig, not just java symbols - // see http://lampsvn.epfl.ch/trac/scala/ticket/2454#comment:14 - case TypeRef(pre, sym, List()) if !sym.typeParams.isEmpty => - val eparams = typeParamsToExistentials(sym, sym.typeParams) - existentialAbstraction(eparams, TypeRef(pre, sym, eparams map (_.tpe))) - case _ => - mapOver(tp) + widened asSeenFrom (pre, tp.typeSymbol.owner) } - } - */ + else loop(tp.prefix) memberType tp.typeSymbol - /** Used by existentialAbstraction. - */ - class ExistentialExtrapolation(tparams: List[Symbol]) extends TypeMap(trackVariance = true) { - private val occurCount = mutable.HashMap[Symbol, Int]() - private def countOccs(tp: Type) = { - tp foreach { - case TypeRef(_, sym, _) => - if (tparams contains sym) - occurCount(sym) += 1 - case _ => () - } - } - def extrapolate(tpe: Type): Type = { - tparams foreach (t => occurCount(t) = 0) - countOccs(tpe) - for (tparam <- tparams) - countOccs(tparam.info) + val result = loop(sym.tpeHK) + assert(sym.isTerm || result.typeSymbol == sym, s"($result).typeSymbol = ${result.typeSymbol}; expected ${sym}") + result + } - apply(tpe) - } + class MissingAliasControl extends ControlThrowable + val missingAliasException = new MissingAliasControl + class MissingTypeControl extends ControlThrowable - /** If these conditions all hold: - * 1) we are in covariant (or contravariant) position - * 2) this type occurs exactly once in the existential scope - * 3) the widened upper (or lower) bound of this type contains no references to tparams - * Then we replace this lone occurrence of the type with the widened upper (or lower) bound. - * All other types pass through unchanged. - */ - def apply(tp: Type): Type = { - val tp1 = mapOver(tp) - if (variance.isInvariant) tp1 - else tp1 match { - case TypeRef(pre, sym, args) if tparams contains sym => - val repl = if (variance.isPositive) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo - val count = occurCount(sym) - val containsTypeParam = tparams exists (repl contains _) - def msg = { - val word = if (variance.isPositive) "upper" else "lower" - s"Widened lone occurrence of $tp1 inside existential to $word bound" - } - if (!repl.typeSymbol.isBottomClass && count == 1 && !containsTypeParam) - logResult(msg)(repl) - else - tp1 - case _ => - tp1 - } - } - override def mapOver(tp: Type): Type = tp match { - case SingleType(pre, sym) => - if (sym.isPackageClass) tp // short path - else { - val pre1 = this(pre) - if ((pre1 eq pre) || !pre1.isStable) tp - else singleType(pre1, sym) - } - case _ => super.mapOver(tp) - } +// Helper Methods ------------------------------------------------------------- - // Do not discard the types of existential ident's. The - // symbol of the Ident itself cannot be listed in the - // existential's parameters, so the resulting existential - // type would be ill-formed. - override def mapOver(tree: Tree) = tree match { - case Ident(_) if tree.tpe.isStable => tree - case _ => super.mapOver(tree) - } + /** The maximum allowable depth of lubs or glbs over types `ts`. + */ + def lubDepth(ts: List[Type]): Int = { + val td = typeDepth(ts) + val bd = baseTypeSeqDepth(ts) + lubDepthAdjust(td, td max bd) } - def singletonBounds(hi: Type) = TypeBounds.upper(intersectionType(List(hi, SingletonClass.tpe))) - - /** Might the given symbol be important when calculating the prefix - * of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`, - * the result will be `tp` unchanged if `pre` is trivial and `clazz` - * is a symbol such that isPossiblePrefix(clazz) == false. + /** The maximum allowable depth of lubs or glbs over given types, + * as a function over the maximum depth `td` of these types, and + * the maximum depth `bd` of all types in the base type sequences of these types. */ - def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass - - private def skipPrefixOf(pre: Type, clazz: Symbol) = ( - (pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz) - ) + private def lubDepthAdjust(td: Int, bd: Int): Int = + if (settings.XfullLubs.value) bd + else if (bd <= 3) bd + else if (bd <= 5) td max (bd - 1) + else if (bd <= 7) td max (bd - 2) + else (td - 1) max (bd - 3) - def newAsSeenFromMap(pre: Type, clazz: Symbol): AsSeenFromMap = - new AsSeenFromMap(pre, clazz) + private def symTypeDepth(syms: List[Symbol]): Int = typeDepth(syms map (_.info)) + private def typeDepth(tps: List[Type]): Int = maxDepth(tps) + private def baseTypeSeqDepth(tps: List[Type]): Int = maxBaseTypeSeqDepth(tps) - /** A map to compute the asSeenFrom method. + /** Is intersection of given types populated? That is, + * for all types tp1, tp2 in intersection + * for all common base classes bc of tp1 and tp2 + * let bt1, bt2 be the base types of tp1, tp2 relative to class bc + * Then: + * bt1 and bt2 have the same prefix, and + * any corresponding non-variant type arguments of bt1 and bt2 are the same */ - class AsSeenFromMap(seenFromPrefix: Type, seenFromClass: Symbol) extends TypeMap with KeepOnlyTypeConstraints { - // Some example source constructs relevant in asSeenFrom: - // - // object CaptureThis { - // trait X[A] { def f: this.type = this } - // class Y[A] { def f: this.type = this } - // // Created new existential to represent This(CaptureThis.X) seen from CaptureThis.X[B]: type _1.type <: CaptureThis.X[B] with Singleton - // def f1[B] = new X[B] { } - // // TODO - why is the behavior different when it's a class? - // def f2[B] = new Y[B] { } - // } - // class CaptureVal[T] { - // val f: java.util.List[_ <: T] = null - // // Captured existential skolem for type _$1 seen from CaptureVal.this.f.type: type _$1 - // def g = f get 0 - // } - // class ClassParam[T] { - // // AsSeenFromMap(Inner.this.type, class Inner)/classParameterAsSeen(T)#loop(ClassParam.this.type, class ClassParam) - // class Inner(lhs: T) { def f = lhs } - // } - def capturedParams: List[Symbol] = _capturedParams - def capturedSkolems: List[Symbol] = _capturedSkolems - - def apply(tp: Type): Type = tp match { - case tp @ ThisType(_) => thisTypeAsSeen(tp) - case tp @ SingleType(_, sym) => if (sym.isPackageClass) tp else singleTypeAsSeen(tp) - case tp @ TypeRef(_, sym, _) if isTypeParamOfEnclosingClass(sym) => classParameterAsSeen(tp) - case _ => mapOver(tp) - } - - private var _capturedSkolems: List[Symbol] = Nil - private var _capturedParams: List[Symbol] = Nil - private val isStablePrefix = seenFromPrefix.isStable - - // isBaseClassOfEnclosingClassOrInfoIsNotYetComplete would be a more accurate - // but less succinct name. - private def isBaseClassOfEnclosingClass(base: Symbol) = { - def loop(encl: Symbol): Boolean = ( - isPossiblePrefix(encl) - && ((encl isSubClass base) || loop(encl.owner.enclClass)) - ) - // The hasCompleteInfo guard is necessary to avoid cycles during the typing - // of certain classes, notably ones defined inside package objects. - !base.hasCompleteInfo || loop(seenFromClass) - } - - /** Is the symbol a class type parameter from one of the enclosing - * classes, or a base class of one of them? - */ - private def isTypeParamOfEnclosingClass(sym: Symbol): Boolean = ( - sym.isTypeParameter - && sym.owner.isClass - && isBaseClassOfEnclosingClass(sym.owner) - ) - - /** Creates an existential representing a type parameter which appears - * in the prefix of a ThisType. - */ - protected def captureThis(pre: Type, clazz: Symbol): Type = { - capturedParams find (_.owner == clazz) match { - case Some(p) => p.tpe - case _ => - val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre) - _capturedParams ::= qvar - debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}") - qvar.tpe - } - } - protected def captureSkolems(skolems: List[Symbol]) { - for (p <- skolems; if !(capturedSkolems contains p)) { - debuglog(s"Captured $p seen from $seenFromPrefix") - _capturedSkolems ::= p - } - } - - /** Find the type argument in an applied type which corresponds to a type parameter. - * The arguments are required to be related as follows, through intermediary `clazz`. - * An exception will be thrown if this is violated. - * - * @param lhs its symbol is a type parameter of `clazz` - * @param rhs a type application constructed from `clazz` - */ - private def correspondingTypeArgument(lhs: Type, rhs: Type): Type = { - val TypeRef(_, lhsSym, lhsArgs) = lhs - val TypeRef(_, rhsSym, rhsArgs) = rhs - require(lhsSym.safeOwner == rhsSym, s"$lhsSym is not a type parameter of $rhsSym") - - // Find the type parameter position; we'll use the corresponding argument - val argIndex = rhsSym.typeParams indexOf lhsSym - - if (argIndex >= 0 && argIndex < rhsArgs.length) // @M! don't just replace the whole thing, might be followed by type application - appliedType(rhsArgs(argIndex), lhsArgs mapConserve this) - else if (rhsSym.tpe_*.parents exists typeIsErroneous) // don't be too zealous with the exceptions, see #2641 - ErrorType - else - abort(s"something is wrong: cannot make sense of type application\n $lhs\n $rhs") - } - - // 0) @pre: `classParam` is a class type parameter - // 1) Walk the owner chain of `seenFromClass` until we find the class which owns `classParam` - // 2) Take the base type of the prefix at that point with respect to the owning class - // 3) Solve for the type parameters through correspondence with the type args of the base type - // - // Only class type parameters (and not skolems) are considered, because other type parameters - // are not influenced by the prefix through which they are seen. Note that type params of - // anonymous type functions, which currently can only arise from normalising type aliases, are - // owned by the type alias of which they are the eta-expansion. - private def classParameterAsSeen(classParam: Type): Type = { - val TypeRef(_, tparam, _) = classParam - - def loop(pre: Type, clazz: Symbol): Type = { - // have to deconst because it may be a Class[T] - def nextBase = (pre baseType clazz).deconst - //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary - if (skipPrefixOf(pre, clazz)) - mapOver(classParam) - else if (!matchesPrefixAndClass(pre, clazz)(tparam.owner)) - loop(nextBase.prefix, clazz.owner) - else nextBase match { - case applied @ TypeRef(_, _, _) => correspondingTypeArgument(classParam, applied) - case ExistentialType(eparams, qtpe) => captureSkolems(eparams) ; loop(qtpe, clazz) - case t => abort(s"$tparam in ${tparam.owner} cannot be instantiated from ${seenFromPrefix.widen}") - } - } - loop(seenFromPrefix, seenFromClass) - } - - // Does the candidate symbol match the given prefix and class? - // Since pre may be something like ThisType(A) where trait A { self: B => }, - // we have to test the typeSymbol of the widened type, not pre.typeSymbol, or - // B will not be considered. - private def matchesPrefixAndClass(pre: Type, clazz: Symbol)(candidate: Symbol) = pre.widen match { - case _: TypeVar => false - case wide => (clazz == candidate) && (wide.typeSymbol isSubClass clazz) - } - - // Whether the annotation tree currently being mapped over has had a This(_) node rewritten. - private[this] var wroteAnnotation = false - private object annotationArgRewriter extends TypeMapTransformer { - private def matchesThis(thiz: Symbol) = matchesPrefixAndClass(seenFromPrefix, seenFromClass)(thiz) - - // what symbol should really be used? - private def newThis(): Tree = { - wroteAnnotation = true - val presym = seenFromPrefix.widen.typeSymbol - val thisSym = presym.owner.newValue(presym.name.toTermName, presym.pos) setInfo seenFromPrefix - gen.mkAttributedQualifier(seenFromPrefix, thisSym) - } - - /** Rewrite `This` trees in annotation argument trees */ - override def transform(tree: Tree): Tree = super.transform(tree) match { - case This(_) if matchesThis(tree.symbol) => newThis() - case tree => tree - } - } - - // This becomes considerably cheaper if we optimize for the common cases: - // where the prefix is stable and where no This nodes are rewritten. If - // either is true, then we don't need to worry about calling giveup. So if - // the prefix is unstable, use a stack variable to indicate whether the tree - // was touched. This takes us to one allocation per AsSeenFromMap rather - // than an allocation on every call to mapOver, and no extra work when the - // tree only has its types remapped. - override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = { - if (isStablePrefix) - annotationArgRewriter transform tree - else { - val saved = wroteAnnotation - wroteAnnotation = false - try annotationArgRewriter transform tree - finally if (wroteAnnotation) giveup() else wroteAnnotation = saved - } - } - - private def thisTypeAsSeen(tp: ThisType): Type = { - def loop(pre: Type, clazz: Symbol): Type = { - val pre1 = pre match { - case SuperType(thistpe, _) => thistpe - case _ => pre - } - if (skipPrefixOf(pre, clazz)) - mapOver(tp) // TODO - is mapOver necessary here? - else if (!matchesPrefixAndClass(pre, clazz)(tp.sym)) - loop((pre baseType clazz).prefix, clazz.owner) - else if (pre1.isStable) - pre1 - else - captureThis(pre1, clazz) - } - loop(seenFromPrefix, seenFromClass) - } - - private def singleTypeAsSeen(tp: SingleType): Type = { - val SingleType(pre, sym) = tp - - val pre1 = this(pre) - if (pre1 eq pre) tp - else if (pre1.isStable) singleType(pre1, sym) - else pre1.memberType(sym).resultType //todo: this should be rolled into existential abstraction - } - - override def toString = s"AsSeenFromMap($seenFromPrefix, $seenFromClass)" - } - - /** A base class to compute all substitutions */ - abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap { - assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to) - - /** Are `sym` and `sym1` the same? Can be tuned by subclasses. */ - protected def matches(sym: Symbol, sym1: Symbol): Boolean = sym eq sym1 - - /** Map target to type, can be tuned by subclasses */ - protected def toType(fromtp: Type, tp: T): Type - - protected def renameBoundSyms(tp: Type): Type = tp match { - case MethodType(ps, restp) => - createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1))) - case PolyType(bs, restp) => - createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1))) - case ExistentialType(bs, restp) => - createFromClonedSymbols(bs, restp)(newExistentialType) - case _ => - tp - } - - @tailrec private def subst(tp: Type, sym: Symbol, from: List[Symbol], to: List[T]): Type = ( - if (from.isEmpty) tp - // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(tp, from)) - else if (matches(from.head, sym)) toType(tp, to.head) - else subst(tp, sym, from.tail, to.tail) - ) - - def apply(tp0: Type): Type = if (from.isEmpty) tp0 else { - val boundSyms = tp0.boundSyms - val tp1 = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0 - val tp = mapOver(tp1) - def substFor(sym: Symbol) = subst(tp, sym, from, to) - - tp match { - // @M - // 1) arguments must also be substituted (even when the "head" of the - // applied type has already been substituted) - // example: (subst RBound[RT] from [type RT,type RBound] to - // [type RT&,type RBound&]) = RBound&[RT&] - // 2) avoid loops (which occur because alpha-conversion is - // not performed properly imo) - // e.g. if in class Iterable[a] there is a new Iterable[(a,b)], - // we must replace the a in Iterable[a] by (a,b) - // (must not recurse --> loops) - // 3) replacing m by List in m[Int] should yield List[Int], not just List - case TypeRef(NoPrefix, sym, args) => - val tcon = substFor(sym) - if ((tp eq tcon) || args.isEmpty) tcon - else appliedType(tcon.typeConstructor, args) - case SingleType(NoPrefix, sym) => - substFor(sym) - case _ => - tp - } - } - } - - /** A map to implement the `substSym` method. */ - class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) { - def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2)) - - protected def toType(fromtp: Type, sym: Symbol) = fromtp match { - case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args) - case SingleType(pre, _) => singleType(pre, sym) - } - @tailrec private def subst(sym: Symbol, from: List[Symbol], to: List[Symbol]): Symbol = ( - if (from.isEmpty) sym - // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(sym, from)) - else if (matches(from.head, sym)) to.head - else subst(sym, from.tail, to.tail) - ) - private def substFor(sym: Symbol) = subst(sym, from, to) - - override def apply(tp: Type): Type = ( - if (from.isEmpty) tp - else tp match { - case TypeRef(pre, sym, args) if pre ne NoPrefix => - val newSym = substFor(sym) - // mapOver takes care of subst'ing in args - mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) ) - // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams)) - case SingleType(pre, sym) if pre ne NoPrefix => - val newSym = substFor(sym) - mapOver( if (sym eq newSym) tp else singleType(pre, newSym) ) - case _ => - super.apply(tp) - } - ) - - object mapTreeSymbols extends TypeMapTransformer { - val strictCopy = newStrictTreeCopier - - def termMapsTo(sym: Symbol) = from indexOf sym match { - case -1 => None - case idx => Some(to(idx)) - } - - // if tree.symbol is mapped to another symbol, passes the new symbol into the - // constructor `trans` and sets the symbol and the type on the resulting tree. - def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match { - case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe - case None => tree - } - - // changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified. - override def transform(tree: Tree) = { - // super.transform maps symbol references in the types of `tree`. it also copies trees where necessary. - super.transform(tree) match { - case id @ Ident(_) => - transformIfMapped(id)(toSym => - strictCopy.Ident(id, toSym.name)) - - case sel @ Select(qual, name) => - transformIfMapped(sel)(toSym => - strictCopy.Select(sel, qual, toSym.name)) - - case tree => tree - } - } - } - override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = { - mapTreeSymbols.transform(tree) - } - } - - /** A map to implement the `subst` method. */ - class SubstTypeMap(from: List[Symbol], to: List[Type]) - extends SubstMap(from, to) { - protected def toType(fromtp: Type, tp: Type) = tp - - override def mapOver(tree: Tree, giveup: () => Nothing): Tree = { - object trans extends TypeMapTransformer { - override def transform(tree: Tree) = tree match { - case Ident(name) => - from indexOf tree.symbol match { - case -1 => super.transform(tree) - case idx => - val totpe = to(idx) - if (totpe.isStable) tree.duplicate setType totpe - else giveup() - } - case _ => - super.transform(tree) - } - } - trans.transform(tree) - } - } - - /** A map to implement the `substThis` method. */ - class SubstThisMap(from: Symbol, to: Type) extends TypeMap { - def apply(tp: Type): Type = tp match { - case ThisType(sym) if (sym == from) => to - case _ => mapOver(tp) - } - } - - class SubstWildcardMap(from: List[Symbol]) extends TypeMap { - def apply(tp: Type): Type = try { - tp match { - case TypeRef(_, sym, _) if from contains sym => - BoundedWildcardType(sym.info.bounds) - case _ => - mapOver(tp) - } - } catch { - case ex: MalformedType => - WildcardType - } - } - -// dependent method types - object IsDependentCollector extends TypeCollector(false) { - def traverse(tp: Type) { - if (tp.isImmediatelyDependent) result = true - else if (!result) mapOver(tp) - } - } - - object ApproximateDependentMap extends TypeMap { - def apply(tp: Type): Type = - if (tp.isImmediatelyDependent) WildcardType - else mapOver(tp) - } - - /** Note: This map is needed even for non-dependent method types, despite what the name might imply. - */ - class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints { - private val actuals = actuals0.toIndexedSeq - private val existentials = new Array[Symbol](actuals.size) - def existentialsNeeded: List[Symbol] = existentials.filter(_ ne null).toList - - private object StableArg { - def unapply(param: Symbol) = Arg unapply param map actuals filter (tp => - tp.isStable && (tp.typeSymbol != NothingClass) - ) - } - private object Arg { - def unapply(param: Symbol) = Some(params indexOf param) filter (_ >= 0) - } - - def apply(tp: Type): Type = mapOver(tp) match { - // unsound to replace args by unstable actual #3873 - case SingleType(NoPrefix, StableArg(arg)) => arg - // (soundly) expand type alias selections on implicit arguments, - // see depmet_implicit_oopsla* test cases -- typically, `param.isImplicit` - case tp1 @ TypeRef(SingleType(NoPrefix, Arg(pid)), sym, targs) => - val arg = actuals(pid) - val res = typeRef(arg, sym, targs) - if (res.typeSymbolDirect.isAliasType) res.dealias else tp1 - // don't return the original `tp`, which may be different from `tp1`, - // due to dropping annotations - case tp1 => tp1 - } - - /* Return the type symbol for referencing a parameter inside the existential quantifier. - * (Only needed if the actual is unstable.) - */ - private def existentialFor(pid: Int) = { - if (existentials(pid) eq null) { - val param = params(pid) - existentials(pid) = ( - param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags) - setInfo singletonBounds(actuals(pid)) - ) - } - existentials(pid) - } - - //AM propagate more info to annotations -- this seems a bit ad-hoc... (based on code by spoon) - override def mapOver(arg: Tree, giveup: ()=>Nothing): Tree = { - // TODO: this should be simplified; in the stable case, one can - // probably just use an Ident to the tree.symbol. - // - // @PP: That leads to failure here, where stuff no longer has type - // 'String @Annot("stuff")' but 'String @Annot(x)'. - // - // def m(x: String): String @Annot(x) = x - // val stuff = m("stuff") - // - // (TODO cont.) Why an existential in the non-stable case? - // - // @PP: In the following: - // - // def m = { val x = "three" ; val y: String @Annot(x) = x; y } - // - // m is typed as 'String @Annot(x) forSome { val x: String }'. - // - // Both examples are from run/constrained-types.scala. - object treeTrans extends Transformer { - override def transform(tree: Tree): Tree = tree.symbol match { - case StableArg(actual) => - gen.mkAttributedQualifier(actual, tree.symbol) - case Arg(pid) => - val sym = existentialFor(pid) - Ident(sym) copyAttrs tree setType typeRef(NoPrefix, sym, Nil) - case _ => - super.transform(tree) - } - } - treeTrans transform arg - } - } - - /** A map to convert every occurrence of a wildcard type to a fresh - * type variable */ - object wildcardToTypeVarMap extends TypeMap { - def apply(tp: Type): Type = tp match { - case WildcardType => - TypeVar(tp, new TypeConstraint) - case BoundedWildcardType(bounds) => - TypeVar(tp, new TypeConstraint(bounds)) - case _ => - mapOver(tp) - } - } - - /** A map to convert every occurrence of a type variable to a wildcard type. */ - object typeVarToOriginMap extends TypeMap { - def apply(tp: Type): Type = tp match { - case TypeVar(origin, _) => origin - case _ => mapOver(tp) - } - } - - /** A map to implement the `contains` method. */ - class ContainsCollector(sym: Symbol) extends TypeCollector(false) { - def traverse(tp: Type) { - if (!result) { - tp.normalize match { - case TypeRef(_, sym1, _) if (sym == sym1) => result = true - case SingleType(_, sym1) if (sym == sym1) => result = true - case _ => mapOver(tp) - } - } - } - - override def mapOver(arg: Tree) = { - for (t <- arg) { - traverse(t.tpe) - if (t.symbol == sym) - result = true - } - arg - } - } - - /** A map to implement the `contains` method. */ - class ContainsTypeCollector(t: Type) extends TypeCollector(false) { - def traverse(tp: Type) { - if (!result) { - if (tp eq t) result = true - else mapOver(tp) - } - } - override def mapOver(arg: Tree) = { - for (t <- arg) - traverse(t.tpe) - - arg - } - } - - /** A map to implement the `filter` method. */ - class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) { - override def collect(tp: Type) = super.collect(tp).reverse - - def traverse(tp: Type) { - if (p(tp)) result ::= tp - mapOver(tp) - } - } - - /** A map to implement the `collect` method. */ - class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) { - override def collect(tp: Type) = super.collect(tp).reverse - - def traverse(tp: Type) { - if (pf.isDefinedAt(tp)) result ::= pf(tp) - mapOver(tp) - } - } - - class ForEachTypeTraverser(f: Type => Unit) extends TypeTraverser { - def traverse(tp: Type) { - f(tp) - mapOver(tp) - } - } - - /** A map to implement the `filter` method. */ - class FindTypeCollector(p: Type => Boolean) extends TypeCollector[Option[Type]](None) { - def traverse(tp: Type) { - if (result.isEmpty) { - if (p(tp)) result = Some(tp) - mapOver(tp) - } - } - } - - /** A map to implement the `contains` method. */ - object ErroneousCollector extends TypeCollector(false) { - def traverse(tp: Type) { - if (!result) { - result = tp.isError - mapOver(tp) - } - } - } - - /** - * A more persistent version of `Type#memberType` which does not require - * that the symbol is a direct member of the prefix. - * - * For instance: - * - * {{{ - * class C[T] { - * sealed trait F[A] - * object X { - * object S1 extends F[T] - * } - * class S2 extends F[T] - * } - * object O extends C[Int] { - * def foo(f: F[Int]) = f match {...} // need to enumerate sealed subtypes of the scrutinee here. - * } - * class S3 extends O.F[String] - * - * nestedMemberType(, , ) = O.X.S1.type - * nestedMemberType(, , ) = O.S2.type - * nestedMemberType(, , ) = S3.type - * }}} - * - * @param sym The symbol of the subtype - * @param pre The prefix from which the symbol is seen - * @param owner - */ - def nestedMemberType(sym: Symbol, pre: Type, owner: Symbol): Type = { - def loop(tp: Type): Type = - if (tp.isTrivial) tp - else if (tp.prefix.typeSymbol isNonBottomSubClass owner) { - val widened = tp match { - case _: ConstantType => tp // Java enum constants: don't widen to the enum type! - case _ => tp.widen // C.X.type widens to C.this.X.type, otherwise `tp asSeenFrom (pre, C)` has no effect. - } - widened asSeenFrom (pre, tp.typeSymbol.owner) - } - else loop(tp.prefix) memberType tp.typeSymbol - - val result = loop(sym.tpeHK) - assert(sym.isTerm || result.typeSymbol == sym, s"($result).typeSymbol = ${result.typeSymbol}; expected ${sym}") - result - } - - /** The most deeply nested owner that contains all the symbols - * of thistype or prefixless typerefs/singletype occurrences in given type. - */ - private def commonOwner(t: Type): Symbol = commonOwner(t :: Nil) - - /** The most deeply nested owner that contains all the symbols - * of thistype or prefixless typerefs/singletype occurrences in given list - * of types. - */ - private def commonOwner(tps: List[Type]): Symbol = { - if (tps.isEmpty) NoSymbol - else { - commonOwnerMap.clear() - tps foreach (commonOwnerMap traverse _) - if (commonOwnerMap.result ne null) commonOwnerMap.result else NoSymbol - } - } - - protected def commonOwnerMap: CommonOwnerMap = commonOwnerMapObj - - protected class CommonOwnerMap extends TypeTraverserWithResult[Symbol] { - var result: Symbol = _ - - def clear() { result = null } - - private def register(sym: Symbol) { - // First considered type is the trivial result. - if ((result eq null) || (sym eq NoSymbol)) - result = sym - else - while ((result ne NoSymbol) && (result ne sym) && !(sym isNestedIn result)) - result = result.owner - } - def traverse(tp: Type) = tp.normalize match { - case ThisType(sym) => register(sym) - case TypeRef(NoPrefix, sym, args) => register(sym.owner) ; args foreach traverse - case SingleType(NoPrefix, sym) => register(sym.owner) - case _ => mapOver(tp) - } - } - - private lazy val commonOwnerMapObj = new CommonOwnerMap - - class MissingAliasControl extends ControlThrowable - val missingAliasException = new MissingAliasControl - class MissingTypeControl extends ControlThrowable - - object adaptToNewRunMap extends TypeMap { - - private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = { - if (phase.flatClasses || sym.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass) - sym - else if (sym.isModuleClass) { - val sourceModule1 = adaptToNewRun(pre, sym.sourceModule) - - sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse { - val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s" - debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass)) - sym - } - } - else { - var rebind0 = pre.findMember(sym.name, BRIDGE, 0, stableOnly = true) orElse { - if (sym.isAliasType) throw missingAliasException - devWarning(s"$pre.$sym no longer exist at phase $phase") - throw new MissingTypeControl // For build manager and presentation compiler purposes - } - /** The two symbols have the same fully qualified name */ - def corresponds(sym1: Symbol, sym2: Symbol): Boolean = - sym1.name == sym2.name && (sym1.isPackageClass || corresponds(sym1.owner, sym2.owner)) - if (!corresponds(sym.owner, rebind0.owner)) { - debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString) - val bcs = pre.baseClasses.dropWhile(bc => !corresponds(bc, sym.owner)) - if (bcs.isEmpty) - assert(pre.typeSymbol.isRefinementClass, pre) // if pre is a refinementclass it might be a structural type => OK to leave it in. - else - rebind0 = pre.baseType(bcs.head).member(sym.name) - debuglog( - "ADAPT2 pre = " + pre + - ", bcs.head = " + bcs.head + - ", sym = " + sym.fullLocationString + - ", rebind = " + rebind0.fullLocationString - ) - } - rebind0.suchThat(sym => sym.isType || sym.isStable) orElse { - debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType) - throw new MalformedType(pre, sym.nameString) - } - } - } - def apply(tp: Type): Type = tp match { - case ThisType(sym) => - try { - val sym1 = adaptToNewRun(sym.owner.thisType, sym) - if (sym1 == sym) tp else ThisType(sym1) - } catch { - case ex: MissingTypeControl => - tp - } - case SingleType(pre, sym) => - if (sym.isPackage) tp - else { - val pre1 = this(pre) - try { - val sym1 = adaptToNewRun(pre1, sym) - if ((pre1 eq pre) && (sym1 eq sym)) tp - else singleType(pre1, sym1) - } catch { - case _: MissingTypeControl => - tp - } - } - case TypeRef(pre, sym, args) => - if (sym.isPackageClass) tp - else { - val pre1 = this(pre) - val args1 = args mapConserve (this) - try { - val sym1 = adaptToNewRun(pre1, sym) - if ((pre1 eq pre) && (sym1 eq sym) && (args1 eq args)/* && sym.isExternal*/) { - tp - } else if (sym1 == NoSymbol) { - devWarning(s"adapt to new run failed: pre=$pre pre1=$pre1 sym=$sym") - tp - } else { - copyTypeRef(tp, pre1, sym1, args1) - } - } catch { - case ex: MissingAliasControl => - apply(tp.dealias) - case _: MissingTypeControl => - tp - } - } - case MethodType(params, restp) => - val restp1 = this(restp) - if (restp1 eq restp) tp - else copyMethodType(tp, params, restp1) - case NullaryMethodType(restp) => - val restp1 = this(restp) - if (restp1 eq restp) tp - else NullaryMethodType(restp1) - case PolyType(tparams, restp) => - val restp1 = this(restp) - if (restp1 eq restp) tp - else PolyType(tparams, restp1) - - // Lukas: we need to check (together) whether we should also include parameter types - // of PolyType and MethodType in adaptToNewRun - - case ClassInfoType(parents, decls, clazz) => - if (clazz.isPackageClass) tp - else { - val parents1 = parents mapConserve (this) - if (parents1 eq parents) tp - else ClassInfoType(parents1, decls, clazz) - } - case RefinedType(parents, decls) => - val parents1 = parents mapConserve (this) - if (parents1 eq parents) tp - else refinedType(parents1, tp.typeSymbol.owner, decls, tp.typeSymbol.owner.pos) - case SuperType(_, _) => mapOver(tp) - case TypeBounds(_, _) => mapOver(tp) - case TypeVar(_, _) => mapOver(tp) - case AnnotatedType(_,_,_) => mapOver(tp) - case NotNullType(_) => mapOver(tp) - case ExistentialType(_, _) => mapOver(tp) - case _ => tp - } - } - - class SubTypePair(val tp1: Type, val tp2: Type) { - override def hashCode = tp1.hashCode * 41 + tp2.hashCode - override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match { - // suspend TypeVars in types compared by =:=, - // since we don't want to mutate them simply to check whether a subtype test is pending - // in addition to making subtyping "more correct" for type vars, - // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion) - // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold) - case stp: SubTypePair => - val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t)) - suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2) - case _ => - false - }) - override def toString = tp1+" <: - assert(sym1 == sym2, (sym1, sym2)) - ( pre1 =:= pre2 - && forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) => - // if left-hand argument is a typevar, make it compatible with variance - // this is for more precise pattern matching - // todo: work this in the spec of this method - // also: think what happens if there are embedded typevars? - if (tparam.variance.isInvariant) - arg1 =:= arg2 - else !arg1.isInstanceOf[TypeVar] || { - if (tparam.variance.isContravariant) arg1 <:< arg2 - else arg2 <:< arg1 - } - } - ) - case (et: ExistentialType, _) => - et.withTypeVars(isConsistent(_, tp2)) - case (_, et: ExistentialType) => - et.withTypeVars(isConsistent(tp1, _)) + def isPopulated(tp1: Type, tp2: Type): Boolean = { + def isConsistent(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match { + case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) => + assert(sym1 == sym2, (sym1, sym2)) + ( pre1 =:= pre2 + && forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) => + // if left-hand argument is a typevar, make it compatible with variance + // this is for more precise pattern matching + // todo: work this in the spec of this method + // also: think what happens if there are embedded typevars? + if (tparam.variance.isInvariant) + arg1 =:= arg2 + else !arg1.isInstanceOf[TypeVar] || { + if (tparam.variance.isContravariant) arg1 <:< arg2 + else arg2 <:< arg1 + } + } + ) + case (et: ExistentialType, _) => + et.withTypeVars(isConsistent(_, tp2)) + case (_, et: ExistentialType) => + et.withTypeVars(isConsistent(tp1, _)) } def check(tp1: Type, tp2: Type) = ( @@ -5266,279 +3893,21 @@ trait Types extends api.Types { self: SymbolTable => } } - private var subsametypeRecursions: Int = 0 - - private def isUnifiable(pre1: Type, pre2: Type) = - (beginsWithTypeVarOrIsRefined(pre1) || beginsWithTypeVarOrIsRefined(pre2)) && (pre1 =:= pre2) - - /** Returns true iff we are past phase specialize, - * sym1 and sym2 are two existential skolems with equal names and bounds, - * and pre1 and pre2 are equal prefixes - */ - private def isSameSpecializedSkolem(sym1: Symbol, sym2: Symbol, pre1: Type, pre2: Type) = { - sym1.isExistentialSkolem && sym2.isExistentialSkolem && - sym1.name == sym2.name && - phase.specialized && - sym1.info =:= sym2.info && - pre1 =:= pre2 - } - - private def isSubPre(pre1: Type, pre2: Type, sym: Symbol) = - if ((pre1 ne pre2) && (pre1 ne NoPrefix) && (pre2 ne NoPrefix) && pre1 <:< pre2) { - if (settings.debug.value) println(s"new isSubPre $sym: $pre1 <:< $pre2") - true - } else - false - - private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean = - if (sym1 == sym2) sym1.hasPackageFlag || sym1.owner.hasPackageFlag || phase.erasedTypes || pre1 =:= pre2 - else (sym1.name == sym2.name) && isUnifiable(pre1, pre2) - - /** Do `tp1` and `tp2` denote equivalent types? */ - def isSameType(tp1: Type, tp2: Type): Boolean = try { - if (Statistics.canEnable) Statistics.incCounter(sametypeCount) - subsametypeRecursions += 1 - //OPT cutdown on Function0 allocation - //was: -// undoLog undoUnless { -// isSameType1(tp1, tp2) -// } - - undoLog.lock() - try { - val before = undoLog.log - var result = false - try { - result = isSameType1(tp1, tp2) - } - finally if (!result) undoLog.undoTo(before) - result - } - finally undoLog.unlock() - } - finally { - subsametypeRecursions -= 1 - // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866) - // it doesn't help to keep separate recursion counts for the three methods that now share it - // if (subsametypeRecursions == 0) undoLog.clear() - } - - def isDifferentType(tp1: Type, tp2: Type): Boolean = try { - subsametypeRecursions += 1 - undoLog undo { // undo type constraints that arise from operations in this block - !isSameType1(tp1, tp2) - } - } finally { - subsametypeRecursions -= 1 - // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866) - // it doesn't help to keep separate recursion counts for the three methods that now share it - // if (subsametypeRecursions == 0) undoLog.clear() - } - - def isDifferentTypeConstructor(tp1: Type, tp2: Type): Boolean = tp1 match { - case TypeRef(pre1, sym1, _) => - tp2 match { - case TypeRef(pre2, sym2, _) => sym1 != sym2 || isDifferentType(pre1, pre2) - case _ => true - } - case _ => true - } - def normalizePlus(tp: Type) = if (isRawType(tp)) rawToExistential(tp) else tp.normalize /* todo: change to: - def normalizePlus(tp: Type) = tp match { - case TypeRef(pre, sym, List()) => - if (!sym.isInitialized) sym.rawInfo.load(sym) - if (sym.isJavaDefined && !sym.typeParams.isEmpty) rawToExistential(tp) - else tp.normalize - case _ => tp.normalize - } - */ - - private def isSameType1(tp1: Type, tp2: Type): Boolean = { - if ((tp1 eq tp2) || - (tp1 eq ErrorType) || (tp1 eq WildcardType) || - (tp2 eq ErrorType) || (tp2 eq WildcardType)) - true - else if ((tp1 eq NoType) || (tp2 eq NoType)) - false - else if (tp1 eq NoPrefix) // !! I do not see how this would be warranted by the spec - tp2.typeSymbol.isPackageClass - else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec - tp1.typeSymbol.isPackageClass - else { - isSameType2(tp1, tp2) || { - val tp1n = normalizePlus(tp1) - val tp2n = normalizePlus(tp2) - ((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n) - } - } - } - - def isSameType2(tp1: Type, tp2: Type): Boolean = { - tp1 match { - case tr1: TypeRef => - tp2 match { - case tr2: TypeRef => - return (equalSymsAndPrefixes(tr1.sym, tr1.pre, tr2.sym, tr2.pre) && - ((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) || - isSameTypes(tr1.args, tr2.args))) || - ((tr1.pre, tr2.pre) match { - case (tv @ TypeVar(_,_), _) => tv.registerTypeSelection(tr1.sym, tr2) - case (_, tv @ TypeVar(_,_)) => tv.registerTypeSelection(tr2.sym, tr1) - case _ => false - }) - case _: SingleType => - return isSameType2(tp2, tp1) // put singleton type on the left, caught below - case _ => - } - case tt1: ThisType => - tp2 match { - case tt2: ThisType => - if (tt1.sym == tt2.sym) return true - case _ => - } - case st1: SingleType => - tp2 match { - case st2: SingleType => - if (equalSymsAndPrefixes(st1.sym, st1.pre, st2.sym, st2.pre)) return true - case TypeRef(pre2, sym2, Nil) => - if (sym2.isModuleClass && equalSymsAndPrefixes(st1.sym, st1.pre, sym2.sourceModule, pre2)) return true - case _ => - } - case ct1: ConstantType => - tp2 match { - case ct2: ConstantType => - return (ct1.value == ct2.value) - case _ => - } - case rt1: RefinedType => - tp2 match { - case rt2: RefinedType => // - def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall { - sym2 => - var e1 = s1.lookupEntry(sym2.name) - (e1 ne null) && { - val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner) - var isEqual = false - while (!isEqual && (e1 ne null)) { - isEqual = e1.sym.info =:= substSym - e1 = s1.lookupNextEntry(e1) - } - isEqual - } - } - //Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG - return isSameTypes(rt1.parents, rt2.parents) && { - val decls1 = rt1.decls - val decls2 = rt2.decls - isSubScope(decls1, decls2) && isSubScope(decls2, decls1) - } - case _ => - } - case mt1: MethodType => - tp2 match { - case mt2: MethodType => - return isSameTypes(mt1.paramTypes, mt2.paramTypes) && - mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params) && - mt1.isImplicit == mt2.isImplicit - // note: no case NullaryMethodType(restpe) => return mt1.params.isEmpty && mt1.resultType =:= restpe - case _ => - } - case NullaryMethodType(restpe1) => - tp2 match { - // note: no case mt2: MethodType => return mt2.params.isEmpty && restpe =:= mt2.resultType - case NullaryMethodType(restpe2) => - return restpe1 =:= restpe2 - case _ => - } - case PolyType(tparams1, res1) => - tp2 match { - case PolyType(tparams2, res2) => -// assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length))) - // @M looks like it might suffer from same problem as #2210 - return ( - (sameLength(tparams1, tparams2)) && // corresponds does not check length of two sequences before checking the predicate - (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && - res1 =:= res2.substSym(tparams2, tparams1) - ) - case _ => - } - case ExistentialType(tparams1, res1) => - tp2 match { - case ExistentialType(tparams2, res2) => - // @M looks like it might suffer from same problem as #2210 - return ( - // corresponds does not check length of two sequences before checking the predicate -- faster & needed to avoid crasher in #2956 - sameLength(tparams1, tparams2) && - (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && - res1 =:= res2.substSym(tparams2, tparams1) - ) - case _ => - } - case TypeBounds(lo1, hi1) => - tp2 match { - case TypeBounds(lo2, hi2) => - return lo1 =:= lo2 && hi1 =:= hi2 - case _ => - } - case BoundedWildcardType(bounds) => - return bounds containsType tp2 - case _ => - } - tp2 match { - case BoundedWildcardType(bounds) => - return bounds containsType tp1 - case _ => - } - tp1 match { - case tv @ TypeVar(_,_) => - return tv.registerTypeEquality(tp2, typeVarLHS = true) - case _ => - } - tp2 match { - case tv @ TypeVar(_,_) => - return tv.registerTypeEquality(tp1, typeVarLHS = false) - case _ => - } - tp1 match { - case _: AnnotatedType => - return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations - case _ => - } - tp2 match { - case _: AnnotatedType => - return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations - case _ => - } - tp1 match { - case _: SingletonType => - tp2 match { - case _: SingletonType => - def chaseDealiasedUnderlying(tp: Type): Type = { - var origin = tp - var next = origin.underlying.dealias - while (next.isInstanceOf[SingletonType]) { - assert(origin ne next, origin) - origin = next - next = origin.underlying.dealias - } - origin - } - val origin1 = chaseDealiasedUnderlying(tp1) - val origin2 = chaseDealiasedUnderlying(tp2) - ((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2) - case _ => - false - } - case _ => - false - } + def normalizePlus(tp: Type) = tp match { + case TypeRef(pre, sym, List()) => + if (!sym.isInitialized) sym.rawInfo.load(sym) + if (sym.isJavaDefined && !sym.typeParams.isEmpty) rawToExistential(tp) + else tp.normalize + case _ => tp.normalize } + */ + /** Are `tps1` and `tps2` lists of pairwise equivalent types? */ def isSameTypes(tps1: List[Type], tps2: List[Type]): Boolean = (tps1 corresponds tps2)(_ =:= _) @@ -5556,64 +3925,9 @@ trait Types extends api.Types { self: SymbolTable => */ final def hasLength(xs: List[_], len: Int) = xs.lengthCompare(len) == 0 - private val pendingSubTypes = new mutable.HashSet[SubTypePair] private var basetypeRecursions: Int = 0 private val pendingBaseTypes = new mutable.HashSet[Type] - def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth) - - def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean = try { - subsametypeRecursions += 1 - - //OPT cutdown on Function0 allocation - //was: -// undoLog undoUnless { // if subtype test fails, it should not affect constraints on typevars -// if (subsametypeRecursions >= LogPendingSubTypesThreshold) { -// val p = new SubTypePair(tp1, tp2) -// if (pendingSubTypes(p)) -// false -// else -// try { -// pendingSubTypes += p -// isSubType2(tp1, tp2, depth) -// } finally { -// pendingSubTypes -= p -// } -// } else { -// isSubType2(tp1, tp2, depth) -// } -// } - - undoLog.lock() - try { - val before = undoLog.log - var result = false - - try result = { // if subtype test fails, it should not affect constraints on typevars - if (subsametypeRecursions >= LogPendingSubTypesThreshold) { - val p = new SubTypePair(tp1, tp2) - if (pendingSubTypes(p)) - false - else - try { - pendingSubTypes += p - isSubType2(tp1, tp2, depth) - } finally { - pendingSubTypes -= p - } - } else { - isSubType2(tp1, tp2, depth) - } - } finally if (!result) undoLog.undoTo(before) - - result - } finally undoLog.unlock() - } finally { - subsametypeRecursions -= 1 - // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866) - // it doesn't help to keep separate recursion counts for the three methods that now share it - // if (subsametypeRecursions == 0) undoLog.clear() - } /** Does this type have a prefix that begins with a type variable, * or is it a refinement type? For type prefixes that fulfil this condition, @@ -5746,42 +4060,6 @@ trait Types extends api.Types { self: SymbolTable => case _ => false } - private def isPolySubType(tp1: PolyType, tp2: PolyType): Boolean = { - val PolyType(tparams1, res1) = tp1 - val PolyType(tparams2, res2) = tp2 - - sameLength(tparams1, tparams2) && { - // fast-path: polymorphic method type -- type params cannot be captured - val isMethod = tparams1.head.owner.isMethod - //@M for an example of why we need to generate fresh symbols otherwise, see neg/tcpoly_ticket2101.scala - val substitutes = if (isMethod) tparams1 else cloneSymbols(tparams1) - def sub1(tp: Type) = if (isMethod) tp else tp.substSym(tparams1, substitutes) - def sub2(tp: Type) = tp.substSym(tparams2, substitutes) - def cmp(p1: Symbol, p2: Symbol) = sub2(p2.info) <:< sub1(p1.info) - - (tparams1 corresponds tparams2)(cmp) && (sub1(res1) <:< sub2(res2)) - } - } - - // @assume tp1.isHigherKinded || tp2.isHigherKinded - def isHKSubType(tp1: Type, tp2: Type, depth: Int): Boolean = { - def isSub(ntp1: Type, ntp2: Type) = (ntp1.withoutAnnotations, ntp2.withoutAnnotations) match { - case (TypeRef(_, AnyClass, _), _) => false // avoid some warnings when Nothing/Any are on the other side - case (_, TypeRef(_, NothingClass, _)) => false - case (pt1: PolyType, pt2: PolyType) => isPolySubType(pt1, pt2) // @assume both .isHigherKinded (both normalized to PolyType) - case (_: PolyType, MethodType(ps, _)) if ps exists (_.tpe.isWildcard) => false // don't warn on HasMethodMatching on right hand side - case _ => // @assume !(both .isHigherKinded) thus cannot be subtypes - def tp_s(tp: Type): String = f"$tp%-20s ${util.shortClassOfInstance(tp)}%s" - devWarning(s"HK subtype check on $tp1 and $tp2, but both don't normalize to polytypes:\n tp1=${tp_s(ntp1)}\n tp2=${tp_s(ntp2)}") - false - } - - ( tp1.typeSymbol == NothingClass // @M Nothing is subtype of every well-kinded type - || tp2.typeSymbol == AnyClass // @M Any is supertype of every well-kinded type (@PP: is it? What about continuations plugin?) - || isSub(tp1.normalize, tp2.normalize) && annotationsConform(tp1, tp2) // @M! normalize reduces higher-kinded case to PolyType's - ) - } - def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol], depth: Int): Boolean = { def isSubArg(t1: Type, t2: Type, variance: Variance) = ( (variance.isContravariant || isSubType(t1, t2, depth)) @@ -5791,205 +4069,7 @@ trait Types extends api.Types { self: SymbolTable => corresponds3(tps1, tps2, tparams map (_.variance))(isSubArg) } - /** Does type `tp1` conform to `tp2`? */ - private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = { - if ((tp1 eq tp2) || isErrorOrWildcard(tp1) || isErrorOrWildcard(tp2)) return true - if ((tp1 eq NoType) || (tp2 eq NoType)) return false - if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass // !! I do not see how the "isPackageClass" would be warranted by the spec - if (tp2 eq NoPrefix) return tp1.typeSymbol.isPackageClass - if (isSingleType(tp1) && isSingleType(tp2) || isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2 - if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType(tp1, tp2, depth) - - /** First try, on the right: - * - unwrap Annotated types, BoundedWildcardTypes, - * - bind TypeVars on the right, if lhs is not Annotated nor BoundedWildcard - * - handle common cases for first-kind TypeRefs on both sides as a fast path. - */ - def firstTry = tp2 match { - // fast path: two typerefs, none of them HK - case tr2: TypeRef => - tp1 match { - case tr1: TypeRef => - val sym1 = tr1.sym - val sym2 = tr2.sym - val pre1 = tr1.pre - val pre2 = tr2.pre - (((if (sym1 == sym2) phase.erasedTypes || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth) - else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass && - (isUnifiable(pre1, pre2) || - isSameSpecializedSkolem(sym1, sym2, pre1, pre2) || - sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) && - isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth)) - || - sym2.isClass && { - val base = tr1 baseType sym2 - (base ne tr1) && isSubType(base, tr2, depth) - } - || - thirdTryRef(tr1, tr2)) - case _ => - secondTry - } - case AnnotatedType(_, _, _) => - isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) && - annotationsConform(tp1, tp2) - case BoundedWildcardType(bounds) => - isSubType(tp1, bounds.hi, depth) - case tv2 @ TypeVar(_, constr2) => - tp1 match { - case AnnotatedType(_, _, _) | BoundedWildcardType(_) => - secondTry - case _ => - tv2.registerBound(tp1, isLowerBound = true) - } - case _ => - secondTry - } - - /** Second try, on the left: - * - unwrap AnnotatedTypes, BoundedWildcardTypes, - * - bind typevars, - * - handle existential types by skolemization. - */ - def secondTry = tp1 match { - case AnnotatedType(_, _, _) => - isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) && - annotationsConform(tp1, tp2) - case BoundedWildcardType(bounds) => - isSubType(tp1.bounds.lo, tp2, depth) - case tv @ TypeVar(_,_) => - tv.registerBound(tp2, isLowerBound = false) - case ExistentialType(_, _) => - try { - skolemizationLevel += 1 - isSubType(tp1.skolemizeExistential, tp2, depth) - } finally { - skolemizationLevel -= 1 - } - case _ => - thirdTry - } - - def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = { - val sym2 = tp2.sym - sym2 match { - case NotNullClass => tp1.isNotNull - case SingletonClass => tp1.isStable || fourthTry - case _: ClassSymbol => - if (isRawType(tp2)) - isSubType(tp1, rawToExistential(tp2), depth) - else if (sym2.name == tpnme.REFINE_CLASS_NAME) - isSubType(tp1, sym2.info, depth) - else - fourthTry - case _: TypeSymbol => - if (sym2 hasFlag DEFERRED) { - val tp2a = tp2.bounds.lo - isDifferentTypeConstructor(tp2, tp2a) && - isSubType(tp1, tp2a, depth) || - fourthTry - } else { - isSubType(tp1.normalize, tp2.normalize, depth) - } - case _ => - fourthTry - } - } - - /** Third try, on the right: - * - decompose refined types. - * - handle typerefs, existentials, and notnull types. - * - handle left+right method types, polytypes, typebounds - */ - def thirdTry = tp2 match { - case tr2: TypeRef => - thirdTryRef(tp1, tr2) - case rt2: RefinedType => - (rt2.parents forall (isSubType(tp1, _, depth))) && - (rt2.decls forall (specializesSym(tp1, _, depth))) - case et2: ExistentialType => - et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry - case nn2: NotNullType => - tp1.isNotNull && isSubType(tp1, nn2.underlying, depth) - case mt2: MethodType => - tp1 match { - case mt1 @ MethodType(params1, res1) => - val params2 = mt2.params - val res2 = mt2.resultType - (sameLength(params1, params2) && - mt1.isImplicit == mt2.isImplicit && - matchingParams(params1, params2, mt1.isJava, mt2.isJava) && - isSubType(res1.substSym(params1, params2), res2, depth)) - // TODO: if mt1.params.isEmpty, consider NullaryMethodType? - case _ => - false - } - case pt2 @ NullaryMethodType(_) => - tp1 match { - // TODO: consider MethodType mt for which mt.params.isEmpty?? - case pt1 @ NullaryMethodType(_) => - isSubType(pt1.resultType, pt2.resultType, depth) - case _ => - false - } - case TypeBounds(lo2, hi2) => - tp1 match { - case TypeBounds(lo1, hi1) => - isSubType(lo2, lo1, depth) && isSubType(hi1, hi2, depth) - case _ => - false - } - case _ => - fourthTry - } - - /** Fourth try, on the left: - * - handle typerefs, refined types, notnull and singleton types. - */ - def fourthTry = tp1 match { - case tr1 @ TypeRef(pre1, sym1, _) => - sym1 match { - case NothingClass => true - case NullClass => - tp2 match { - case TypeRef(_, sym2, _) => - containsNull(sym2) - case _ => - isSingleType(tp2) && isSubType(tp1, tp2.widen, depth) - } - case _: ClassSymbol => - if (isRawType(tp1)) - isSubType(rawToExistential(tp1), tp2, depth) - else if (sym1.isModuleClass) tp2 match { - case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2) - case _ => false - } - else if (sym1.isRefinementClass) - isSubType(sym1.info, tp2, depth) - else false - - case _: TypeSymbol => - if (sym1 hasFlag DEFERRED) { - val tp1a = tp1.bounds.hi - isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth) - } else { - isSubType(tp1.normalize, tp2.normalize, depth) - } - case _ => - false - } - case RefinedType(parents1, _) => - parents1 exists (isSubType(_, tp2, depth)) - case _: SingletonType | _: NotNullType => - isSubType(tp1.underlying, tp2, depth) - case _ => - false - } - - firstTry - } - - private def containsNull(sym: Symbol): Boolean = + protected[internal] def containsNull(sym: Symbol): Boolean = sym.isClass && sym != NothingClass && !(sym isNonBottomSubClass AnyValClass) && !(sym isNonBottomSubClass NotNullClass) @@ -6011,7 +4091,7 @@ trait Types extends api.Types { self: SymbolTable => /** Does member `sym1` of `tp1` have a stronger type * than member `sym2` of `tp2`? */ - private def specializesSym(tp1: Type, sym1: Symbol, tp2: Type, sym2: Symbol, depth: Int): Boolean = { + protected[internal] def specializesSym(tp1: Type, sym1: Symbol, tp2: Type, sym2: Symbol, depth: Int): Boolean = { require((sym1 ne NoSymbol) && (sym2 ne NoSymbol), ((tp1, sym1, tp2, sym2, depth))) val info1 = tp1.memberInfo(sym1) val info2 = tp2.memberInfo(sym2).substThis(tp2.typeSymbol, tp1) @@ -6145,7 +4225,7 @@ trait Types extends api.Types { self: SymbolTable => */ /** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */ - private def matchingParams(syms1: List[Symbol], syms2: List[Symbol], syms1isJava: Boolean, syms2isJava: Boolean): Boolean = syms1 match { + protected[internal] def matchingParams(syms1: List[Symbol], syms2: List[Symbol], syms1isJava: Boolean, syms2isJava: Boolean): Boolean = syms1 match { case Nil => syms2.isEmpty case sym1 :: rest1 => @@ -6174,87 +4254,6 @@ trait Types extends api.Types { self: SymbolTable => else x1 :: xs1 } - /** Solve constraint collected in types `tvars`. - * - * @param tvars All type variables to be instantiated. - * @param tparams The type parameters corresponding to `tvars` - * @param variances The variances of type parameters; need to reverse - * solution direction for all contravariant variables. - * @param upper When `true` search for max solution else min. - */ - def solve(tvars: List[TypeVar], tparams: List[Symbol], - variances: List[Variance], upper: Boolean): Boolean = - solve(tvars, tparams, variances, upper, AnyDepth) - - def solve(tvars: List[TypeVar], tparams: List[Symbol], - variances: List[Variance], upper: Boolean, depth: Int): Boolean = { - - def solveOne(tvar: TypeVar, tparam: Symbol, variance: Variance) { - if (tvar.constr.inst == NoType) { - val up = if (variance.isContravariant) !upper else upper - tvar.constr.inst = null - val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo - //Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound)) - var cyclic = bound contains tparam - foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => { - val ok = (tparam2 != tparam) && ( - (bound contains tparam2) - || up && (tparam2.info.bounds.lo =:= tparam.tpeHK) - || !up && (tparam2.info.bounds.hi =:= tparam.tpeHK) - ) - if (ok) { - if (tvar2.constr.inst eq null) cyclic = true - solveOne(tvar2, tparam2, variance2) - } - }) - if (!cyclic) { - if (up) { - if (bound.typeSymbol != AnyClass) { - log(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)") - tvar addHiBound bound.instantiateTypeParams(tparams, tvars) - } - for (tparam2 <- tparams) - tparam2.info.bounds.lo.dealias match { - case TypeRef(_, `tparam`, _) => - log(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)") - tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars) - case _ => - } - } else { - if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) { - log(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)") - tvar addLoBound bound.instantiateTypeParams(tparams, tvars) - } - for (tparam2 <- tparams) - tparam2.info.bounds.hi.dealias match { - case TypeRef(_, `tparam`, _) => - log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)") - tvar addLoBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars) - case _ => - } - } - } - tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar - - //println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))) - val newInst = ( - if (up) { - if (depth != AnyDepth) glb(tvar.constr.hiBounds, depth) else glb(tvar.constr.hiBounds) - } else { - if (depth != AnyDepth) lub(tvar.constr.loBounds, depth) else lub(tvar.constr.loBounds) - } - ) - log(s"$tvar setInst $newInst") - tvar setInst newInst - //Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG - } - } - - // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info))) - foreach3(tvars, tparams, variances)(solveOne) - tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst)) - } - /** Do type arguments `targs` conform to formal parameters `tparams`? */ def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): Boolean = { @@ -6267,168 +4266,6 @@ trait Types extends api.Types { self: SymbolTable => def instantiatedBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): List[TypeBounds] = tparams map (_.info.asSeenFrom(pre, owner).instantiateTypeParams(tparams, targs).bounds) -// Lubs and Glbs --------------------------------------------------------- - - private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Int) { - import util.TableDef - import TableDef.Column - def str(tp: Type) = { - if (tp == NoType) "" - else { - val s = ("" + tp).replaceAll("""[\w.]+\.(\w+)""", "$1") - if (s.length < 60) s - else (s take 57) + "..." - } - } - - val sorted = btsMap.toList.sortWith((x, y) => x._1.typeSymbol isLess y._1.typeSymbol) - val maxSeqLength = sorted.map(_._2.size).max - val padded = sorted map (_._2.padTo(maxSeqLength, NoType)) - val transposed = padded.transpose - - val columns: List[Column[List[Type]]] = mapWithIndex(sorted) { - case ((k, v), idx) => - Column(str(k), (xs: List[Type]) => str(xs(idx)), left = true) - } - - val tableDef = TableDef(columns: _*) - val formatted = tableDef.table(transposed) - println("** Depth is " + depth + "\n" + formatted) - } - - /** From a list of types, find any which take type parameters - * where the type parameter bounds contain references to other - * any types in the list (including itself.) - * - * @return List of symbol pairs holding the recursive type - * parameter and the parameter which references it. - */ - def findRecursiveBounds(ts: List[Type]): List[(Symbol, Symbol)] = { - if (ts.isEmpty) Nil - else { - val sym = ts.head.typeSymbol - require(ts.tail forall (_.typeSymbol == sym), ts) - for (p <- sym.typeParams ; in <- sym.typeParams ; if in.info.bounds contains p) yield - p -> in - } - } - - /** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix), - * compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types: - * - * xs <= ys iff forall y in ys exists x in xs such that x <: y - * - * @arg tsParams for each type in the original list of types `ts0`, its list of type parameters (if that type is a type constructor) - * (these type parameters may be referred to by type arguments in the BTS column of those types, - * and must be interpreted as bound variables; i.e., under a type lambda that wraps the types that refer to these type params) - * @arg tsBts a matrix whose columns are basetype sequences - * the first row is the original list of types for which we're computing the lub - * (except that type constructors have been applied to their dummyArgs) - * @See baseTypeSeq for a definition of sorted and upwards closed. - */ - private def lubList(ts: List[Type], depth: Int): List[Type] = { - var lubListDepth = 0 - // This catches some recursive situations which would otherwise - // befuddle us, e.g. pos/hklub0.scala - def isHotForTs(xs: List[Type]) = ts exists (_.typeParams == xs.map(_.typeSymbol)) - - def elimHigherOrderTypeParam(tp: Type) = tp match { - case TypeRef(_, _, args) if args.nonEmpty && isHotForTs(args) => - logResult("Retracting dummies from " + tp + " in lublist")(tp.typeConstructor) - case _ => tp - } - // pretypes is a tail-recursion-preserving accumulator. - @annotation.tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = { - lubListDepth += 1 - - if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse - else if (tsBts.tail.isEmpty) pretypes.reverse ++ tsBts.head - else { - // ts0 is the 1-dimensional frontier of symbols cutting through 2-dimensional tsBts. - // Invariant: all symbols "under" (closer to the first row) the frontier - // are smaller (according to _.isLess) than the ones "on and beyond" the frontier - val ts0 = tsBts map (_.head) - - // Is the frontier made up of types with the same symbol? - val isUniformFrontier = (ts0: @unchecked) match { - case t :: ts => ts forall (_.typeSymbol == t.typeSymbol) - } - - // Produce a single type for this frontier by merging the prefixes and arguments of those - // typerefs that share the same symbol: that symbol is the current maximal symbol for which - // the invariant holds, i.e., the one that conveys most information regarding subtyping. Before - // merging, strip targs that refer to bound tparams (when we're computing the lub of type - // constructors.) Also filter out all types that are a subtype of some other type. - if (isUniformFrontier) { - val fbounds = findRecursiveBounds(ts0) map (_._2) - val tcLubList = typeConstructorLubList(ts0) - def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains - - val ts1 = ts0 map { t => - if (isRecursive(t)) { - tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match { - case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n Was: $t\n Now")(tp) - case _ => t - } - } - else t - } - val tails = tsBts map (_.tail) - mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match { - case Some(tp) => loop(tp :: pretypes, tails) - case _ => loop(pretypes, tails) - } - } - else { - // frontier is not uniform yet, move it beyond the current minimal symbol; - // lather, rinSe, repeat - val sym = minSym(ts0) - val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts) - if (printLubs) { - val str = (newtps.zipWithIndex map { case (tps, idx) => - tps.map(" " + _ + "\n").mkString(" (" + idx + ")\n", "", "\n") - }).mkString("") - - println("Frontier(\n" + str + ")") - printLubMatrix((ts zip tsBts).toMap, lubListDepth) - } - - loop(pretypes, newtps) - } - } - } - - val initialBTSes = ts map (_.baseTypeSeq.toList) - if (printLubs) - printLubMatrix((ts zip initialBTSes).toMap, depth) - - loop(Nil, initialBTSes) - } - - /** The minimal symbol of a list of types (as determined by `Symbol.isLess`). */ - private def minSym(tps: List[Type]): Symbol = - (tps.head.typeSymbol /: tps.tail) { - (sym1, tp2) => if (tp2.typeSymbol isLess sym1) tp2.typeSymbol else sym1 - } - - /** A minimal type list which has a given list of types as its base type sequence */ - def spanningTypes(ts: List[Type]): List[Type] = ts match { - case List() => List() - case first :: rest => - first :: spanningTypes( - rest filter (t => !first.typeSymbol.isSubClass(t.typeSymbol))) - } - - /** Eliminate from list of types all elements which are a supertype - * of some other element of the list. */ - private def elimSuper(ts: List[Type]): List[Type] = ts match { - case List() => List() - case List(t) => List(t) - case t :: ts1 => - val rest = elimSuper(ts1 filter (t1 => !(t <:< t1))) - if (rest exists (t1 => t1 <:< t)) rest else t :: rest - } - def elimAnonymousClass(t: Type) = t match { case TypeRef(pre, clazz, Nil) if clazz.isAnonymousClass => clazz.classBound.asSeenFrom(pre, clazz.owner) @@ -6436,406 +4273,6 @@ trait Types extends api.Types { self: SymbolTable => t } - /** Eliminate from list of types all elements which are a subtype - * of some other element of the list. */ - private def elimSub(ts: List[Type], depth: Int): List[Type] = { - def elimSub0(ts: List[Type]): List[Type] = ts match { - case List() => List() - case List(t) => List(t) - case t :: ts1 => - val rest = elimSub0(ts1 filter (t1 => !isSubType(t1, t, decr(depth)))) - if (rest exists (t1 => isSubType(t, t1, decr(depth)))) rest else t :: rest - } - val ts0 = elimSub0(ts) - if (ts0.isEmpty || ts0.tail.isEmpty) ts0 - else { - val ts1 = ts0 mapConserve (t => elimAnonymousClass(t.dealiasWiden)) - if (ts1 eq ts0) ts0 - else elimSub(ts1, depth) - } - } - - private def stripExistentialsAndTypeVars(ts: List[Type]): (List[Type], List[Symbol]) = { - val quantified = ts flatMap { - case ExistentialType(qs, _) => qs - case t => List() - } - def stripType(tp: Type): Type = tp match { - case ExistentialType(_, res) => - res - case tv@TypeVar(_, constr) => - if (tv.instValid) stripType(constr.inst) - else if (tv.untouchable) tv - else abort("trying to do lub/glb of typevar "+tp) - case t => t - } - val strippedTypes = ts mapConserve stripType - (strippedTypes, quantified) - } - - def weakLub(ts: List[Type]) = - if (ts.nonEmpty && (ts forall isNumericValueType)) (numericLub(ts), true) - else if (ts exists typeHasAnnotations) - (annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true) - else (lub(ts), false) - - def numericLub(ts: List[Type]) = - ts reduceLeft ((t1, t2) => - if (isNumericSubType(t1, t2)) t2 - else if (isNumericSubType(t2, t1)) t1 - else IntClass.tpe) - - def isWeakSubType(tp1: Type, tp2: Type) = - tp1.deconst.normalize match { - case TypeRef(_, sym1, _) if isNumericValueClass(sym1) => - tp2.deconst.normalize match { - case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => - isNumericSubClass(sym1, sym2) - case tv2 @ TypeVar(_, _) => - tv2.registerBound(tp1, isLowerBound = true, isNumericBound = true) - case _ => - isSubType(tp1, tp2) - } - case tv1 @ TypeVar(_, _) => - tp2.deconst.normalize match { - case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => - tv1.registerBound(tp2, isLowerBound = false, isNumericBound = true) - case _ => - isSubType(tp1, tp2) - } - case _ => - isSubType(tp1, tp2) - } - - /** The isNumericValueType tests appear redundant, but without them - * test/continuations-neg/function3.scala goes into an infinite loop. - * (Even if the calls are to typeSymbolDirect.) - */ - def isNumericSubType(tp1: Type, tp2: Type): Boolean = ( - isNumericValueType(tp1) - && isNumericValueType(tp2) - && isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol) - ) - - private val lubResults = new mutable.HashMap[(Int, List[Type]), Type] - private val glbResults = new mutable.HashMap[(Int, List[Type]), Type] - - /** Given a list of types, finds all the base classes they have in - * common, then returns a list of type constructors derived directly - * from the symbols (so any more specific type information is ignored.) - * The list is filtered such that every type constructor in the list - * expects the same number of type arguments, which is chosen based - * on the deepest class among the common baseclasses. - */ - def typeConstructorLubList(ts: List[Type]): List[Type] = { - val bcs = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _) - val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz)) - - tcons map (_.typeConstructor) match { - case Nil => Nil - case t :: ts => t :: ts.filter(_.typeParams.size == t.typeParams.size) - } - } - - def lub(ts: List[Type]): Type = ts match { - case List() => NothingClass.tpe - case List(t) => t - case _ => - if (Statistics.canEnable) Statistics.incCounter(lubCount) - val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null - try { - val res = lub(ts, lubDepth(ts)) - // If the number of unapplied type parameters in all incoming - // types is consistent, and the lub does not match that, return - // the type constructor of the calculated lub instead. This - // is because lubbing type constructors tends to result in types - // which have been applied to dummies or Nothing. - ts.map(_.typeParams.size).distinct match { - case x :: Nil if res.typeParams.size != x => - logResult(s"Stripping type args from lub because $res is not consistent with $ts")(res.typeConstructor) - case _ => - res - } - } - finally { - lubResults.clear() - glbResults.clear() - if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) - } - } - - /** The least upper bound wrt <:< of a list of types */ - private def lub(ts: List[Type], depth: Int): Type = { - def lub0(ts0: List[Type]): Type = elimSub(ts0, depth) match { - case List() => NothingClass.tpe - case List(t) => t - case ts @ PolyType(tparams, _) :: _ => - val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => - tparam.cloneSymbol.setInfo(glb(bounds, depth))) - PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1))) - case ts @ (mt @ MethodType(params, _)) :: rest => - MethodType(params, lub0(matchingRestypes(ts, mt.paramTypes))) - case ts @ NullaryMethodType(_) :: rest => - NullaryMethodType(lub0(matchingRestypes(ts, Nil))) - case ts @ TypeBounds(_, _) :: rest => - TypeBounds(glb(ts map (_.bounds.lo), depth), lub(ts map (_.bounds.hi), depth)) - case ts @ AnnotatedType(annots, tpe, _) :: rest => - annotationsLub(lub0(ts map (_.withoutAnnotations)), ts) - case ts => - lubResults get (depth, ts) match { - case Some(lubType) => - lubType - case None => - lubResults((depth, ts)) = AnyClass.tpe - val res = if (depth < 0) AnyClass.tpe else lub1(ts) - lubResults((depth, ts)) = res - res - } - } - def lub1(ts0: List[Type]): Type = { - val (ts, tparams) = stripExistentialsAndTypeVars(ts0) - val lubBaseTypes: List[Type] = lubList(ts, depth) - val lubParents = spanningTypes(lubBaseTypes) - val lubOwner = commonOwner(ts) - val lubBase = intersectionType(lubParents, lubOwner) - val lubType = - if (phase.erasedTypes || depth == 0 ) lubBase - else { - val lubRefined = refinedType(lubParents, lubOwner) - val lubThisType = lubRefined.typeSymbol.thisType - val narrowts = ts map (_.narrow) - def excludeFromLub(sym: Symbol) = ( - sym.isClass - || sym.isConstructor - || !sym.isPublic - || isGetClass(sym) - || sym.isFinal - || narrowts.exists(t => !refines(t, sym)) - ) - def lubsym(proto: Symbol): Symbol = { - val prototp = lubThisType.memberInfo(proto) - val syms = narrowts map (t => - t.nonPrivateMember(proto.name).suchThat(sym => - sym.tpe matches prototp.substThis(lubThisType.typeSymbol, t))) - - if (syms contains NoSymbol) NoSymbol - else { - val symtypes = - map2(narrowts, syms)((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType)) - if (proto.isTerm) // possible problem: owner of info is still the old one, instead of new refinement class - proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(lub(symtypes, decr(depth))) - else if (symtypes.tail forall (symtypes.head =:= _)) - proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(symtypes.head) - else { - def lubBounds(bnds: List[TypeBounds]): TypeBounds = - TypeBounds(glb(bnds map (_.lo), decr(depth)), lub(bnds map (_.hi), decr(depth))) - lubRefined.typeSymbol.newAbstractType(proto.name.toTypeName, proto.pos) - .setInfoOwnerAdjusted(lubBounds(symtypes map (_.bounds))) - } - } - } - def refines(tp: Type, sym: Symbol): Boolean = { - val syms = tp.nonPrivateMember(sym.name).alternatives - !syms.isEmpty && (syms forall (alt => - // todo alt != sym is strictly speaking not correct, but without it we lose - // efficiency. - alt != sym && !specializesSym(lubThisType, sym, tp, alt, depth))) - } - // add a refinement symbol for all non-class members of lubBase - // which are refined by every type in ts. - for (sym <- lubBase.nonPrivateMembers ; if !excludeFromLub(sym)) { - try lubsym(sym) andAlso (addMember(lubThisType, lubRefined, _, depth)) - catch { - case ex: NoCommonType => - } - } - if (lubRefined.decls.isEmpty) lubBase - else if (!verifyLubs) lubRefined - else { - // Verify that every given type conforms to the calculated lub. - // In theory this should not be necessary, but higher-order type - // parameters are not handled correctly. - val ok = ts forall { t => - isSubType(t, lubRefined, depth) || { - if (settings.debug.value || printLubs) { - Console.println( - "Malformed lub: " + lubRefined + "\n" + - "Argument " + t + " does not conform. Falling back to " + lubBase - ) - } - false - } - } - // If not, fall back on the more conservative calculation. - if (ok) lubRefined - else lubBase - } - } - // dropIllegalStarTypes is a localized fix for SI-6897. We should probably - // integrate that transformation at a lower level in master, but lubs are - // the likely and maybe only spot they escape, so fixing here for 2.10.1. - existentialAbstraction(tparams, dropIllegalStarTypes(lubType)) - } - if (printLubs) { - println(indent + "lub of " + ts + " at depth "+depth)//debug - indent = indent + " " - assert(indent.length <= 100) - } - if (Statistics.canEnable) Statistics.incCounter(nestedLubCount) - val res = lub0(ts) - if (printLubs) { - indent = indent stripSuffix " " - println(indent + "lub of " + ts + " is " + res)//debug - } - if (ts forall typeIsNotNull) res.notNull else res - } - - val GlbFailure = new Throwable - - /** A global counter for glb calls in the `specializes` query connected to the `addMembers` - * call in `glb`. There's a possible infinite recursion when `specializes` calls - * memberType, which calls baseTypeSeq, which calls mergePrefixAndArgs, which calls glb. - * The counter breaks this recursion after two calls. - * If the recursion is broken, no member is added to the glb. - */ - private var globalGlbDepth = 0 - private final val globalGlbLimit = 2 - - /** The greatest lower bound of a list of types (as determined by `<:<`). */ - def glb(ts: List[Type]): Type = elimSuper(ts) match { - case List() => AnyClass.tpe - case List(t) => t - case ts0 => - if (Statistics.canEnable) Statistics.incCounter(lubCount) - val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null - try { - glbNorm(ts0, lubDepth(ts0)) - } finally { - lubResults.clear() - glbResults.clear() - if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) - } - } - - private def glb(ts: List[Type], depth: Int): Type = elimSuper(ts) match { - case List() => AnyClass.tpe - case List(t) => t - case ts0 => glbNorm(ts0, depth) - } - - /** The greatest lower bound of a list of types (as determined by `<:<`), which have been normalized - * with regard to `elimSuper`. */ - protected def glbNorm(ts: List[Type], depth: Int): Type = { - def glb0(ts0: List[Type]): Type = ts0 match { - case List() => AnyClass.tpe - case List(t) => t - case ts @ PolyType(tparams, _) :: _ => - val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => - tparam.cloneSymbol.setInfo(lub(bounds, depth))) - PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth)) - case ts @ (mt @ MethodType(params, _)) :: rest => - MethodType(params, glbNorm(matchingRestypes(ts, mt.paramTypes), depth)) - case ts @ NullaryMethodType(_) :: rest => - NullaryMethodType(glbNorm(matchingRestypes(ts, Nil), depth)) - case ts @ TypeBounds(_, _) :: rest => - TypeBounds(lub(ts map (_.bounds.lo), depth), glb(ts map (_.bounds.hi), depth)) - case ts => - glbResults get (depth, ts) match { - case Some(glbType) => - glbType - case _ => - glbResults((depth, ts)) = NothingClass.tpe - val res = if (depth < 0) NothingClass.tpe else glb1(ts) - glbResults((depth, ts)) = res - res - } - } - def glb1(ts0: List[Type]): Type = { - try { - val (ts, tparams) = stripExistentialsAndTypeVars(ts0) - val glbOwner = commonOwner(ts) - def refinedToParents(t: Type): List[Type] = t match { - case RefinedType(ps, _) => ps flatMap refinedToParents - case _ => List(t) - } - def refinedToDecls(t: Type): List[Scope] = t match { - case RefinedType(ps, decls) => - val dss = ps flatMap refinedToDecls - if (decls.isEmpty) dss else decls :: dss - case _ => List() - } - val ts1 = ts flatMap refinedToParents - val glbBase = intersectionType(ts1, glbOwner) - val glbType = - if (phase.erasedTypes || depth == 0) glbBase - else { - val glbRefined = refinedType(ts1, glbOwner) - val glbThisType = glbRefined.typeSymbol.thisType - def glbsym(proto: Symbol): Symbol = { - val prototp = glbThisType.memberInfo(proto) - val syms = for (t <- ts; - alt <- (t.nonPrivateMember(proto.name).alternatives) - if glbThisType.memberInfo(alt) matches prototp - ) yield alt - val symtypes = syms map glbThisType.memberInfo - assert(!symtypes.isEmpty) - proto.cloneSymbol(glbRefined.typeSymbol).setInfoOwnerAdjusted( - if (proto.isTerm) glb(symtypes, decr(depth)) - else { - def isTypeBound(tp: Type) = tp match { - case TypeBounds(_, _) => true - case _ => false - } - def glbBounds(bnds: List[Type]): TypeBounds = { - val lo = lub(bnds map (_.bounds.lo), decr(depth)) - val hi = glb(bnds map (_.bounds.hi), decr(depth)) - if (lo <:< hi) TypeBounds(lo, hi) - else throw GlbFailure - } - val symbounds = symtypes filter isTypeBound - var result: Type = - if (symbounds.isEmpty) - TypeBounds.empty - else glbBounds(symbounds) - for (t <- symtypes if !isTypeBound(t)) - if (result.bounds containsType t) result = t - else throw GlbFailure - result - }) - } - if (globalGlbDepth < globalGlbLimit) - try { - globalGlbDepth += 1 - val dss = ts flatMap refinedToDecls - for (ds <- dss; sym <- ds.iterator) - if (globalGlbDepth < globalGlbLimit && !specializesSym(glbThisType, sym, depth)) - try { - addMember(glbThisType, glbRefined, glbsym(sym), depth) - } catch { - case ex: NoCommonType => - } - } finally { - globalGlbDepth -= 1 - } - if (glbRefined.decls.isEmpty) glbBase else glbRefined - } - existentialAbstraction(tparams, glbType) - } catch { - case GlbFailure => - if (ts forall (t => NullClass.tpe <:< t)) NullClass.tpe - else NothingClass.tpe - } - } - // if (settings.debug.value) { println(indent + "glb of " + ts + " at depth "+depth); indent = indent + " " } //DEBUG - - if (Statistics.canEnable) Statistics.incCounter(nestedLubCount) - val res = glb0(ts) - - // if (settings.debug.value) { indent = indent.substring(0, indent.length() - 2); log(indent + "glb of " + ts + " is " + res) }//DEBUG - - if (ts exists typeIsNotNull) res.notNull else res - } - /** A list of the typevars in a type. */ def typeVarsInType(tp: Type): List[TypeVar] = { var tvs: List[TypeVar] = Nil @@ -6970,51 +4407,6 @@ trait Types extends api.Types { self: SymbolTable => def inheritsJavaVarArgsMethod(clazz: Symbol) = clazz.thisType.baseClasses exists isJavaVarargsAncestor - /** All types in list must be polytypes with type parameter lists of - * same length as tparams. - * Returns list of list of bounds infos, where corresponding type - * parameters are renamed to tparams. - */ - private def matchingBounds(tps: List[Type], tparams: List[Symbol]): List[List[Type]] = { - def getBounds(tp: Type): List[Type] = tp match { - case PolyType(tparams1, _) if sameLength(tparams1, tparams) => - tparams1 map (tparam => tparam.info.substSym(tparams1, tparams)) - case tp => - if (tp ne tp.normalize) getBounds(tp.normalize) - else throw new NoCommonType(tps) - } - tps map getBounds - } - - /** All types in list must be polytypes with type parameter lists of - * same length as tparams. - * Returns list of instance types, where corresponding type - * parameters are renamed to tparams. - */ - private def matchingInstTypes(tps: List[Type], tparams: List[Symbol]): List[Type] = { - def transformResultType(tp: Type): Type = tp match { - case PolyType(tparams1, restpe) if sameLength(tparams1, tparams) => - restpe.substSym(tparams1, tparams) - case tp => - if (tp ne tp.normalize) transformResultType(tp.normalize) - else throw new NoCommonType(tps) - } - tps map transformResultType - } - - /** All types in list must be method types with equal parameter types. - * Returns list of their result types. - */ - private def matchingRestypes(tps: List[Type], pts: List[Type]): List[Type] = - tps map { - case mt @ MethodType(params1, res) if isSameTypes(mt.paramTypes, pts) => - res - case NullaryMethodType(res) if pts.isEmpty => - res - case _ => - throw new NoCommonType(tps) - } - // Errors and Diagnostics ----------------------------------------------------- /** A throwable signalling a type error */ @@ -7039,7 +4431,7 @@ trait Types extends api.Types { self: SymbolTable => } /** The current indentation string for traces */ - private var indent: String = "" + protected[internal] var indent: String = "" /** Perform operation `p` on arguments `tp1`, `arg2` and print trace of computation. */ protected def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean = { @@ -7105,29 +4497,6 @@ trait Types extends api.Types { self: SymbolTable => "scala.collection.IndexedSeq", "scala.collection.Iterator") - - /** The maximum number of recursions allowed in toString - */ - final val maxTostringRecursions = 50 - - private var tostringRecursions = 0 - - protected def typeToString(tpe: Type): String = - if (tostringRecursions >= maxTostringRecursions) { - devWarning("Exceeded recursion depth attempting to print " + util.shortClassOfInstance(tpe)) - if (settings.debug.value) - (new Throwable).printStackTrace - - "..." - } - else - try { - tostringRecursions += 1 - tpe.safeToString - } finally { - tostringRecursions -= 1 - } - // ----- Hoisted closures and convenience methods, for compile time reductions ------- private[scala] val typeIsNotNull = (tp: Type) => tp.isNotNull diff --git a/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala b/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala new file mode 100644 index 0000000000..e5ddd8f359 --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala @@ -0,0 +1,50 @@ +package scala.reflect +package internal +package tpe + +private[internal] trait CommonOwners { + self: SymbolTable => + + /** The most deeply nested owner that contains all the symbols + * of thistype or prefixless typerefs/singletype occurrences in given type. + */ + protected[internal] def commonOwner(t: Type): Symbol = commonOwner(t :: Nil) + + /** The most deeply nested owner that contains all the symbols + * of thistype or prefixless typerefs/singletype occurrences in given list + * of types. + */ + protected[internal] def commonOwner(tps: List[Type]): Symbol = { + if (tps.isEmpty) NoSymbol + else { + commonOwnerMap.clear() + tps foreach (commonOwnerMap traverse _) + if (commonOwnerMap.result ne null) commonOwnerMap.result else NoSymbol + } + } + + protected def commonOwnerMap: CommonOwnerMap = commonOwnerMapObj + + protected class CommonOwnerMap extends TypeTraverserWithResult[Symbol] { + var result: Symbol = _ + + def clear() { result = null } + + private def register(sym: Symbol) { + // First considered type is the trivial result. + if ((result eq null) || (sym eq NoSymbol)) + result = sym + else + while ((result ne NoSymbol) && (result ne sym) && !(sym isNestedIn result)) + result = result.owner + } + def traverse(tp: Type) = tp.normalize match { + case ThisType(sym) => register(sym) + case TypeRef(NoPrefix, sym, args) => register(sym.owner) ; args foreach traverse + case SingleType(NoPrefix, sym) => register(sym.owner) + case _ => mapOver(tp) + } + } + + private lazy val commonOwnerMapObj = new CommonOwnerMap +} diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala new file mode 100644 index 0000000000..bdccc75d6d --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala @@ -0,0 +1,592 @@ +package scala.reflect +package internal +package tpe + +import scala.collection.{ mutable } +import util.Statistics +import Variance._ + +private[internal] trait GlbLubs { + self: SymbolTable => + import definitions._ + import TypesStats._ + + private final val printLubs = sys.props contains "scalac.debug.lub" + + /** In case anyone wants to turn off lub verification without reverting anything. */ + private final val verifyLubs = true + + + private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Int) { + import util.TableDef + import TableDef.Column + def str(tp: Type) = { + if (tp == NoType) "" + else { + val s = ("" + tp).replaceAll("""[\w.]+\.(\w+)""", "$1") + if (s.length < 60) s + else (s take 57) + "..." + } + } + + val sorted = btsMap.toList.sortWith((x, y) => x._1.typeSymbol isLess y._1.typeSymbol) + val maxSeqLength = sorted.map(_._2.size).max + val padded = sorted map (_._2.padTo(maxSeqLength, NoType)) + val transposed = padded.transpose + + val columns: List[Column[List[Type]]] = mapWithIndex(sorted) { + case ((k, v), idx) => + Column(str(k), (xs: List[Type]) => str(xs(idx)), left = true) + } + + val tableDef = TableDef(columns: _*) + val formatted = tableDef.table(transposed) + println("** Depth is " + depth + "\n" + formatted) + } + + /** From a list of types, find any which take type parameters + * where the type parameter bounds contain references to other + * any types in the list (including itself.) + * + * @return List of symbol pairs holding the recursive type + * parameter and the parameter which references it. + */ + def findRecursiveBounds(ts: List[Type]): List[(Symbol, Symbol)] = { + if (ts.isEmpty) Nil + else { + val sym = ts.head.typeSymbol + require(ts.tail forall (_.typeSymbol == sym), ts) + for (p <- sym.typeParams ; in <- sym.typeParams ; if in.info.bounds contains p) yield + p -> in + } + } + + /** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix), + * compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types: + * + * xs <= ys iff forall y in ys exists x in xs such that x <: y + * + * @arg tsParams for each type in the original list of types `ts0`, its list of type parameters (if that type is a type constructor) + * (these type parameters may be referred to by type arguments in the BTS column of those types, + * and must be interpreted as bound variables; i.e., under a type lambda that wraps the types that refer to these type params) + * @arg tsBts a matrix whose columns are basetype sequences + * the first row is the original list of types for which we're computing the lub + * (except that type constructors have been applied to their dummyArgs) + * @See baseTypeSeq for a definition of sorted and upwards closed. + */ + def lubList(ts: List[Type], depth: Int): List[Type] = { + var lubListDepth = 0 + // This catches some recursive situations which would otherwise + // befuddle us, e.g. pos/hklub0.scala + def isHotForTs(xs: List[Type]) = ts exists (_.typeParams == xs.map(_.typeSymbol)) + + def elimHigherOrderTypeParam(tp: Type) = tp match { + case TypeRef(_, _, args) if args.nonEmpty && isHotForTs(args) => + logResult("Retracting dummies from " + tp + " in lublist")(tp.typeConstructor) + case _ => tp + } + // pretypes is a tail-recursion-preserving accumulator. + @annotation.tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = { + lubListDepth += 1 + + if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse + else if (tsBts.tail.isEmpty) pretypes.reverse ++ tsBts.head + else { + // ts0 is the 1-dimensional frontier of symbols cutting through 2-dimensional tsBts. + // Invariant: all symbols "under" (closer to the first row) the frontier + // are smaller (according to _.isLess) than the ones "on and beyond" the frontier + val ts0 = tsBts map (_.head) + + // Is the frontier made up of types with the same symbol? + val isUniformFrontier = (ts0: @unchecked) match { + case t :: ts => ts forall (_.typeSymbol == t.typeSymbol) + } + + // Produce a single type for this frontier by merging the prefixes and arguments of those + // typerefs that share the same symbol: that symbol is the current maximal symbol for which + // the invariant holds, i.e., the one that conveys most information regarding subtyping. Before + // merging, strip targs that refer to bound tparams (when we're computing the lub of type + // constructors.) Also filter out all types that are a subtype of some other type. + if (isUniformFrontier) { + val fbounds = findRecursiveBounds(ts0) map (_._2) + val tcLubList = typeConstructorLubList(ts0) + def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains + + val ts1 = ts0 map { t => + if (isRecursive(t)) { + tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match { + case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n Was: $t\n Now")(tp) + case _ => t + } + } + else t + } + val tails = tsBts map (_.tail) + mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match { + case Some(tp) => loop(tp :: pretypes, tails) + case _ => loop(pretypes, tails) + } + } + else { + // frontier is not uniform yet, move it beyond the current minimal symbol; + // lather, rinSe, repeat + val sym = minSym(ts0) + val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts) + if (printLubs) { + val str = (newtps.zipWithIndex map { case (tps, idx) => + tps.map(" " + _ + "\n").mkString(" (" + idx + ")\n", "", "\n") + }).mkString("") + + println("Frontier(\n" + str + ")") + printLubMatrix((ts zip tsBts).toMap, lubListDepth) + } + + loop(pretypes, newtps) + } + } + } + + val initialBTSes = ts map (_.baseTypeSeq.toList) + if (printLubs) + printLubMatrix((ts zip initialBTSes).toMap, depth) + + loop(Nil, initialBTSes) + } + + /** The minimal symbol of a list of types (as determined by `Symbol.isLess`). */ + private def minSym(tps: List[Type]): Symbol = + (tps.head.typeSymbol /: tps.tail) { + (sym1, tp2) => if (tp2.typeSymbol isLess sym1) tp2.typeSymbol else sym1 + } + + /** A minimal type list which has a given list of types as its base type sequence */ + def spanningTypes(ts: List[Type]): List[Type] = ts match { + case List() => List() + case first :: rest => + first :: spanningTypes( + rest filter (t => !first.typeSymbol.isSubClass(t.typeSymbol))) + } + + /** Eliminate from list of types all elements which are a supertype + * of some other element of the list. */ + private def elimSuper(ts: List[Type]): List[Type] = ts match { + case List() => List() + case List(t) => List(t) + case t :: ts1 => + val rest = elimSuper(ts1 filter (t1 => !(t <:< t1))) + if (rest exists (t1 => t1 <:< t)) rest else t :: rest + } + + /** Eliminate from list of types all elements which are a subtype + * of some other element of the list. */ + private def elimSub(ts: List[Type], depth: Int): List[Type] = { + def elimSub0(ts: List[Type]): List[Type] = ts match { + case List() => List() + case List(t) => List(t) + case t :: ts1 => + val rest = elimSub0(ts1 filter (t1 => !isSubType(t1, t, decr(depth)))) + if (rest exists (t1 => isSubType(t, t1, decr(depth)))) rest else t :: rest + } + val ts0 = elimSub0(ts) + if (ts0.isEmpty || ts0.tail.isEmpty) ts0 + else { + val ts1 = ts0 mapConserve (t => elimAnonymousClass(t.dealiasWiden)) + if (ts1 eq ts0) ts0 + else elimSub(ts1, depth) + } + } + + private def stripExistentialsAndTypeVars(ts: List[Type]): (List[Type], List[Symbol]) = { + val quantified = ts flatMap { + case ExistentialType(qs, _) => qs + case t => List() + } + def stripType(tp: Type): Type = tp match { + case ExistentialType(_, res) => + res + case tv@TypeVar(_, constr) => + if (tv.instValid) stripType(constr.inst) + else if (tv.untouchable) tv + else abort("trying to do lub/glb of typevar "+tp) + case t => t + } + val strippedTypes = ts mapConserve stripType + (strippedTypes, quantified) + } + + def weakLub(ts: List[Type]) = + if (ts.nonEmpty && (ts forall isNumericValueType)) (numericLub(ts), true) + else if (ts exists typeHasAnnotations) + (annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true) + else (lub(ts), false) + + def numericLub(ts: List[Type]) = + ts reduceLeft ((t1, t2) => + if (isNumericSubType(t1, t2)) t2 + else if (isNumericSubType(t2, t1)) t1 + else IntClass.tpe) + + private val lubResults = new mutable.HashMap[(Int, List[Type]), Type] + private val glbResults = new mutable.HashMap[(Int, List[Type]), Type] + + /** Given a list of types, finds all the base classes they have in + * common, then returns a list of type constructors derived directly + * from the symbols (so any more specific type information is ignored.) + * The list is filtered such that every type constructor in the list + * expects the same number of type arguments, which is chosen based + * on the deepest class among the common baseclasses. + */ + def typeConstructorLubList(ts: List[Type]): List[Type] = { + val bcs = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _) + val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz)) + + tcons map (_.typeConstructor) match { + case Nil => Nil + case t :: ts => t :: ts.filter(_.typeParams.size == t.typeParams.size) + } + } + + def lub(ts: List[Type]): Type = ts match { + case List() => NothingClass.tpe + case List(t) => t + case _ => + if (Statistics.canEnable) Statistics.incCounter(lubCount) + val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null + try { + val res = lub(ts, lubDepth(ts)) + // If the number of unapplied type parameters in all incoming + // types is consistent, and the lub does not match that, return + // the type constructor of the calculated lub instead. This + // is because lubbing type constructors tends to result in types + // which have been applied to dummies or Nothing. + ts.map(_.typeParams.size).distinct match { + case x :: Nil if res.typeParams.size != x => + logResult(s"Stripping type args from lub because $res is not consistent with $ts")(res.typeConstructor) + case _ => + res + } + } + finally { + lubResults.clear() + glbResults.clear() + if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + } + } + + /** The least upper bound wrt <:< of a list of types */ + protected[internal] def lub(ts: List[Type], depth: Int): Type = { + def lub0(ts0: List[Type]): Type = elimSub(ts0, depth) match { + case List() => NothingClass.tpe + case List(t) => t + case ts @ PolyType(tparams, _) :: _ => + val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => + tparam.cloneSymbol.setInfo(glb(bounds, depth))) + PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1))) + case ts @ (mt @ MethodType(params, _)) :: rest => + MethodType(params, lub0(matchingRestypes(ts, mt.paramTypes))) + case ts @ NullaryMethodType(_) :: rest => + NullaryMethodType(lub0(matchingRestypes(ts, Nil))) + case ts @ TypeBounds(_, _) :: rest => + TypeBounds(glb(ts map (_.bounds.lo), depth), lub(ts map (_.bounds.hi), depth)) + case ts @ AnnotatedType(annots, tpe, _) :: rest => + annotationsLub(lub0(ts map (_.withoutAnnotations)), ts) + case ts => + lubResults get (depth, ts) match { + case Some(lubType) => + lubType + case None => + lubResults((depth, ts)) = AnyClass.tpe + val res = if (depth < 0) AnyClass.tpe else lub1(ts) + lubResults((depth, ts)) = res + res + } + } + def lub1(ts0: List[Type]): Type = { + val (ts, tparams) = stripExistentialsAndTypeVars(ts0) + val lubBaseTypes: List[Type] = lubList(ts, depth) + val lubParents = spanningTypes(lubBaseTypes) + val lubOwner = commonOwner(ts) + val lubBase = intersectionType(lubParents, lubOwner) + val lubType = + if (phase.erasedTypes || depth == 0 ) lubBase + else { + val lubRefined = refinedType(lubParents, lubOwner) + val lubThisType = lubRefined.typeSymbol.thisType + val narrowts = ts map (_.narrow) + def excludeFromLub(sym: Symbol) = ( + sym.isClass + || sym.isConstructor + || !sym.isPublic + || isGetClass(sym) + || sym.isFinal + || narrowts.exists(t => !refines(t, sym)) + ) + def lubsym(proto: Symbol): Symbol = { + val prototp = lubThisType.memberInfo(proto) + val syms = narrowts map (t => + t.nonPrivateMember(proto.name).suchThat(sym => + sym.tpe matches prototp.substThis(lubThisType.typeSymbol, t))) + + if (syms contains NoSymbol) NoSymbol + else { + val symtypes = + map2(narrowts, syms)((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType)) + if (proto.isTerm) // possible problem: owner of info is still the old one, instead of new refinement class + proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(lub(symtypes, decr(depth))) + else if (symtypes.tail forall (symtypes.head =:= _)) + proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(symtypes.head) + else { + def lubBounds(bnds: List[TypeBounds]): TypeBounds = + TypeBounds(glb(bnds map (_.lo), decr(depth)), lub(bnds map (_.hi), decr(depth))) + lubRefined.typeSymbol.newAbstractType(proto.name.toTypeName, proto.pos) + .setInfoOwnerAdjusted(lubBounds(symtypes map (_.bounds))) + } + } + } + def refines(tp: Type, sym: Symbol): Boolean = { + val syms = tp.nonPrivateMember(sym.name).alternatives + !syms.isEmpty && (syms forall (alt => + // todo alt != sym is strictly speaking not correct, but without it we lose + // efficiency. + alt != sym && !specializesSym(lubThisType, sym, tp, alt, depth))) + } + // add a refinement symbol for all non-class members of lubBase + // which are refined by every type in ts. + for (sym <- lubBase.nonPrivateMembers ; if !excludeFromLub(sym)) { + try lubsym(sym) andAlso (addMember(lubThisType, lubRefined, _, depth)) + catch { + case ex: NoCommonType => + } + } + if (lubRefined.decls.isEmpty) lubBase + else if (!verifyLubs) lubRefined + else { + // Verify that every given type conforms to the calculated lub. + // In theory this should not be necessary, but higher-order type + // parameters are not handled correctly. + val ok = ts forall { t => + isSubType(t, lubRefined, depth) || { + if (settings.debug.value || printLubs) { + Console.println( + "Malformed lub: " + lubRefined + "\n" + + "Argument " + t + " does not conform. Falling back to " + lubBase + ) + } + false + } + } + // If not, fall back on the more conservative calculation. + if (ok) lubRefined + else lubBase + } + } + // dropIllegalStarTypes is a localized fix for SI-6897. We should probably + // integrate that transformation at a lower level in master, but lubs are + // the likely and maybe only spot they escape, so fixing here for 2.10.1. + existentialAbstraction(tparams, dropIllegalStarTypes(lubType)) + } + if (printLubs) { + println(indent + "lub of " + ts + " at depth "+depth)//debug + indent = indent + " " + assert(indent.length <= 100) + } + if (Statistics.canEnable) Statistics.incCounter(nestedLubCount) + val res = lub0(ts) + if (printLubs) { + indent = indent stripSuffix " " + println(indent + "lub of " + ts + " is " + res)//debug + } + if (ts forall typeIsNotNull) res.notNull else res + } + + val GlbFailure = new Throwable + + /** A global counter for glb calls in the `specializes` query connected to the `addMembers` + * call in `glb`. There's a possible infinite recursion when `specializes` calls + * memberType, which calls baseTypeSeq, which calls mergePrefixAndArgs, which calls glb. + * The counter breaks this recursion after two calls. + * If the recursion is broken, no member is added to the glb. + */ + private var globalGlbDepth = 0 + private final val globalGlbLimit = 2 + + /** The greatest lower bound of a list of types (as determined by `<:<`). */ + def glb(ts: List[Type]): Type = elimSuper(ts) match { + case List() => AnyClass.tpe + case List(t) => t + case ts0 => + if (Statistics.canEnable) Statistics.incCounter(lubCount) + val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null + try { + glbNorm(ts0, lubDepth(ts0)) + } finally { + lubResults.clear() + glbResults.clear() + if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + } + } + + protected[internal] def glb(ts: List[Type], depth: Int): Type = elimSuper(ts) match { + case List() => AnyClass.tpe + case List(t) => t + case ts0 => glbNorm(ts0, depth) + } + + /** The greatest lower bound of a list of types (as determined by `<:<`), which have been normalized + * with regard to `elimSuper`. */ + protected def glbNorm(ts: List[Type], depth: Int): Type = { + def glb0(ts0: List[Type]): Type = ts0 match { + case List() => AnyClass.tpe + case List(t) => t + case ts @ PolyType(tparams, _) :: _ => + val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => + tparam.cloneSymbol.setInfo(lub(bounds, depth))) + PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth)) + case ts @ (mt @ MethodType(params, _)) :: rest => + MethodType(params, glbNorm(matchingRestypes(ts, mt.paramTypes), depth)) + case ts @ NullaryMethodType(_) :: rest => + NullaryMethodType(glbNorm(matchingRestypes(ts, Nil), depth)) + case ts @ TypeBounds(_, _) :: rest => + TypeBounds(lub(ts map (_.bounds.lo), depth), glb(ts map (_.bounds.hi), depth)) + case ts => + glbResults get (depth, ts) match { + case Some(glbType) => + glbType + case _ => + glbResults((depth, ts)) = NothingClass.tpe + val res = if (depth < 0) NothingClass.tpe else glb1(ts) + glbResults((depth, ts)) = res + res + } + } + def glb1(ts0: List[Type]): Type = { + try { + val (ts, tparams) = stripExistentialsAndTypeVars(ts0) + val glbOwner = commonOwner(ts) + def refinedToParents(t: Type): List[Type] = t match { + case RefinedType(ps, _) => ps flatMap refinedToParents + case _ => List(t) + } + def refinedToDecls(t: Type): List[Scope] = t match { + case RefinedType(ps, decls) => + val dss = ps flatMap refinedToDecls + if (decls.isEmpty) dss else decls :: dss + case _ => List() + } + val ts1 = ts flatMap refinedToParents + val glbBase = intersectionType(ts1, glbOwner) + val glbType = + if (phase.erasedTypes || depth == 0) glbBase + else { + val glbRefined = refinedType(ts1, glbOwner) + val glbThisType = glbRefined.typeSymbol.thisType + def glbsym(proto: Symbol): Symbol = { + val prototp = glbThisType.memberInfo(proto) + val syms = for (t <- ts; + alt <- (t.nonPrivateMember(proto.name).alternatives) + if glbThisType.memberInfo(alt) matches prototp + ) yield alt + val symtypes = syms map glbThisType.memberInfo + assert(!symtypes.isEmpty) + proto.cloneSymbol(glbRefined.typeSymbol).setInfoOwnerAdjusted( + if (proto.isTerm) glb(symtypes, decr(depth)) + else { + def isTypeBound(tp: Type) = tp match { + case TypeBounds(_, _) => true + case _ => false + } + def glbBounds(bnds: List[Type]): TypeBounds = { + val lo = lub(bnds map (_.bounds.lo), decr(depth)) + val hi = glb(bnds map (_.bounds.hi), decr(depth)) + if (lo <:< hi) TypeBounds(lo, hi) + else throw GlbFailure + } + val symbounds = symtypes filter isTypeBound + var result: Type = + if (symbounds.isEmpty) + TypeBounds.empty + else glbBounds(symbounds) + for (t <- symtypes if !isTypeBound(t)) + if (result.bounds containsType t) result = t + else throw GlbFailure + result + }) + } + if (globalGlbDepth < globalGlbLimit) + try { + globalGlbDepth += 1 + val dss = ts flatMap refinedToDecls + for (ds <- dss; sym <- ds.iterator) + if (globalGlbDepth < globalGlbLimit && !specializesSym(glbThisType, sym, depth)) + try { + addMember(glbThisType, glbRefined, glbsym(sym), depth) + } catch { + case ex: NoCommonType => + } + } finally { + globalGlbDepth -= 1 + } + if (glbRefined.decls.isEmpty) glbBase else glbRefined + } + existentialAbstraction(tparams, glbType) + } catch { + case GlbFailure => + if (ts forall (t => NullClass.tpe <:< t)) NullClass.tpe + else NothingClass.tpe + } + } + // if (settings.debug.value) { println(indent + "glb of " + ts + " at depth "+depth); indent = indent + " " } //DEBUG + + if (Statistics.canEnable) Statistics.incCounter(nestedLubCount) + val res = glb0(ts) + + // if (settings.debug.value) { indent = indent.substring(0, indent.length() - 2); log(indent + "glb of " + ts + " is " + res) }//DEBUG + + if (ts exists typeIsNotNull) res.notNull else res + } + + /** All types in list must be polytypes with type parameter lists of + * same length as tparams. + * Returns list of list of bounds infos, where corresponding type + * parameters are renamed to tparams. + */ + private def matchingBounds(tps: List[Type], tparams: List[Symbol]): List[List[Type]] = { + def getBounds(tp: Type): List[Type] = tp match { + case PolyType(tparams1, _) if sameLength(tparams1, tparams) => + tparams1 map (tparam => tparam.info.substSym(tparams1, tparams)) + case tp => + if (tp ne tp.normalize) getBounds(tp.normalize) + else throw new NoCommonType(tps) + } + tps map getBounds + } + + /** All types in list must be polytypes with type parameter lists of + * same length as tparams. + * Returns list of instance types, where corresponding type + * parameters are renamed to tparams. + */ + private def matchingInstTypes(tps: List[Type], tparams: List[Symbol]): List[Type] = { + def transformResultType(tp: Type): Type = tp match { + case PolyType(tparams1, restpe) if sameLength(tparams1, tparams) => + restpe.substSym(tparams1, tparams) + case tp => + if (tp ne tp.normalize) transformResultType(tp.normalize) + else throw new NoCommonType(tps) + } + tps map transformResultType + } + + /** All types in list must be method types with equal parameter types. + * Returns list of their result types. + */ + private def matchingRestypes(tps: List[Type], pts: List[Type]): List[Type] = + tps map { + case mt @ MethodType(params1, res) if isSameTypes(mt.paramTypes, pts) => + res + case NullaryMethodType(res) if pts.isEmpty => + res + case _ => + throw new NoCommonType(tps) + } +} diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala new file mode 100644 index 0000000000..82321f61c2 --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -0,0 +1,617 @@ +package scala.reflect +package internal +package tpe + +import scala.collection.{ mutable } +import Flags._ +import util.Statistics + +trait TypeComparers { + self: SymbolTable => + import definitions._ + import TypesStats._ + + private final val LogPendingSubTypesThreshold = DefaultLogThreshhold + + private val pendingSubTypes = new mutable.HashSet[SubTypePair] + + class SubTypePair(val tp1: Type, val tp2: Type) { + override def hashCode = tp1.hashCode * 41 + tp2.hashCode + override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match { + // suspend TypeVars in types compared by =:=, + // since we don't want to mutate them simply to check whether a subtype test is pending + // in addition to making subtyping "more correct" for type vars, + // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion) + // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold) + case stp: SubTypePair => + val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t)) + suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2) + case _ => + false + }) + override def toString = tp1+" <: + tp2 match { + case TypeRef(pre2, sym2, _) => sym1 != sym2 || isDifferentType(pre1, pre2) + case _ => true + } + case _ => true + } + + /** Do `tp1` and `tp2` denote equivalent types? */ + def isSameType(tp1: Type, tp2: Type): Boolean = try { + if (Statistics.canEnable) Statistics.incCounter(sametypeCount) + subsametypeRecursions += 1 + //OPT cutdown on Function0 allocation + //was: + // undoLog undoUnless { + // isSameType1(tp1, tp2) + // } + + undoLog.lock() + try { + val before = undoLog.log + var result = false + try { + result = isSameType1(tp1, tp2) + } + finally if (!result) undoLog.undoTo(before) + result + } + finally undoLog.unlock() + } + finally { + subsametypeRecursions -= 1 + // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866) + // it doesn't help to keep separate recursion counts for the three methods that now share it + // if (subsametypeRecursions == 0) undoLog.clear() + } + + private def isSameType1(tp1: Type, tp2: Type): Boolean = { + if ((tp1 eq tp2) || + (tp1 eq ErrorType) || (tp1 eq WildcardType) || + (tp2 eq ErrorType) || (tp2 eq WildcardType)) + true + else if ((tp1 eq NoType) || (tp2 eq NoType)) + false + else if (tp1 eq NoPrefix) // !! I do not see how this would be warranted by the spec + tp2.typeSymbol.isPackageClass + else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec + tp1.typeSymbol.isPackageClass + else { + isSameType2(tp1, tp2) || { + val tp1n = normalizePlus(tp1) + val tp2n = normalizePlus(tp2) + ((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n) + } + } + } + + def isSameType2(tp1: Type, tp2: Type): Boolean = { + tp1 match { + case tr1: TypeRef => + tp2 match { + case tr2: TypeRef => + return (equalSymsAndPrefixes(tr1.sym, tr1.pre, tr2.sym, tr2.pre) && + ((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) || + isSameTypes(tr1.args, tr2.args))) || + ((tr1.pre, tr2.pre) match { + case (tv @ TypeVar(_,_), _) => tv.registerTypeSelection(tr1.sym, tr2) + case (_, tv @ TypeVar(_,_)) => tv.registerTypeSelection(tr2.sym, tr1) + case _ => false + }) + case _: SingleType => + return isSameType2(tp2, tp1) // put singleton type on the left, caught below + case _ => + } + case tt1: ThisType => + tp2 match { + case tt2: ThisType => + if (tt1.sym == tt2.sym) return true + case _ => + } + case st1: SingleType => + tp2 match { + case st2: SingleType => + if (equalSymsAndPrefixes(st1.sym, st1.pre, st2.sym, st2.pre)) return true + case TypeRef(pre2, sym2, Nil) => + if (sym2.isModuleClass && equalSymsAndPrefixes(st1.sym, st1.pre, sym2.sourceModule, pre2)) return true + case _ => + } + case ct1: ConstantType => + tp2 match { + case ct2: ConstantType => + return (ct1.value == ct2.value) + case _ => + } + case rt1: RefinedType => + tp2 match { + case rt2: RefinedType => // + def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall { + sym2 => + var e1 = s1.lookupEntry(sym2.name) + (e1 ne null) && { + val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner) + var isEqual = false + while (!isEqual && (e1 ne null)) { + isEqual = e1.sym.info =:= substSym + e1 = s1.lookupNextEntry(e1) + } + isEqual + } + } + //Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG + return isSameTypes(rt1.parents, rt2.parents) && { + val decls1 = rt1.decls + val decls2 = rt2.decls + isSubScope(decls1, decls2) && isSubScope(decls2, decls1) + } + case _ => + } + case mt1: MethodType => + tp2 match { + case mt2: MethodType => + return isSameTypes(mt1.paramTypes, mt2.paramTypes) && + mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params) && + mt1.isImplicit == mt2.isImplicit + // note: no case NullaryMethodType(restpe) => return mt1.params.isEmpty && mt1.resultType =:= restpe + case _ => + } + case NullaryMethodType(restpe1) => + tp2 match { + // note: no case mt2: MethodType => return mt2.params.isEmpty && restpe =:= mt2.resultType + case NullaryMethodType(restpe2) => + return restpe1 =:= restpe2 + case _ => + } + case PolyType(tparams1, res1) => + tp2 match { + case PolyType(tparams2, res2) => + // assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length))) + // @M looks like it might suffer from same problem as #2210 + return ( + (sameLength(tparams1, tparams2)) && // corresponds does not check length of two sequences before checking the predicate + (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && + res1 =:= res2.substSym(tparams2, tparams1) + ) + case _ => + } + case ExistentialType(tparams1, res1) => + tp2 match { + case ExistentialType(tparams2, res2) => + // @M looks like it might suffer from same problem as #2210 + return ( + // corresponds does not check length of two sequences before checking the predicate -- faster & needed to avoid crasher in #2956 + sameLength(tparams1, tparams2) && + (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && + res1 =:= res2.substSym(tparams2, tparams1) + ) + case _ => + } + case TypeBounds(lo1, hi1) => + tp2 match { + case TypeBounds(lo2, hi2) => + return lo1 =:= lo2 && hi1 =:= hi2 + case _ => + } + case BoundedWildcardType(bounds) => + return bounds containsType tp2 + case _ => + } + tp2 match { + case BoundedWildcardType(bounds) => + return bounds containsType tp1 + case _ => + } + tp1 match { + case tv @ TypeVar(_,_) => + return tv.registerTypeEquality(tp2, typeVarLHS = true) + case _ => + } + tp2 match { + case tv @ TypeVar(_,_) => + return tv.registerTypeEquality(tp1, typeVarLHS = false) + case _ => + } + tp1 match { + case _: AnnotatedType => + return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations + case _ => + } + tp2 match { + case _: AnnotatedType => + return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations + case _ => + } + tp1 match { + case _: SingletonType => + tp2 match { + case _: SingletonType => + def chaseDealiasedUnderlying(tp: Type): Type = { + var origin = tp + var next = origin.underlying.dealias + while (next.isInstanceOf[SingletonType]) { + assert(origin ne next, origin) + origin = next + next = origin.underlying.dealias + } + origin + } + val origin1 = chaseDealiasedUnderlying(tp1) + val origin2 = chaseDealiasedUnderlying(tp2) + ((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2) + case _ => + false + } + case _ => + false + } + } + + def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth) + + def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean = try { + subsametypeRecursions += 1 + + //OPT cutdown on Function0 allocation + //was: + // undoLog undoUnless { // if subtype test fails, it should not affect constraints on typevars + // if (subsametypeRecursions >= LogPendingSubTypesThreshold) { + // val p = new SubTypePair(tp1, tp2) + // if (pendingSubTypes(p)) + // false + // else + // try { + // pendingSubTypes += p + // isSubType2(tp1, tp2, depth) + // } finally { + // pendingSubTypes -= p + // } + // } else { + // isSubType2(tp1, tp2, depth) + // } + // } + + undoLog.lock() + try { + val before = undoLog.log + var result = false + + try result = { // if subtype test fails, it should not affect constraints on typevars + if (subsametypeRecursions >= LogPendingSubTypesThreshold) { + val p = new SubTypePair(tp1, tp2) + if (pendingSubTypes(p)) + false + else + try { + pendingSubTypes += p + isSubType2(tp1, tp2, depth) + } finally { + pendingSubTypes -= p + } + } else { + isSubType2(tp1, tp2, depth) + } + } finally if (!result) undoLog.undoTo(before) + + result + } finally undoLog.unlock() + } finally { + subsametypeRecursions -= 1 + // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866) + // it doesn't help to keep separate recursion counts for the three methods that now share it + // if (subsametypeRecursions == 0) undoLog.clear() + } + + private def isPolySubType(tp1: PolyType, tp2: PolyType): Boolean = { + val PolyType(tparams1, res1) = tp1 + val PolyType(tparams2, res2) = tp2 + + sameLength(tparams1, tparams2) && { + // fast-path: polymorphic method type -- type params cannot be captured + val isMethod = tparams1.head.owner.isMethod + //@M for an example of why we need to generate fresh symbols otherwise, see neg/tcpoly_ticket2101.scala + val substitutes = if (isMethod) tparams1 else cloneSymbols(tparams1) + def sub1(tp: Type) = if (isMethod) tp else tp.substSym(tparams1, substitutes) + def sub2(tp: Type) = tp.substSym(tparams2, substitutes) + def cmp(p1: Symbol, p2: Symbol) = sub2(p2.info) <:< sub1(p1.info) + + (tparams1 corresponds tparams2)(cmp) && (sub1(res1) <:< sub2(res2)) + } + } + + // @assume tp1.isHigherKinded || tp2.isHigherKinded + def isHKSubType(tp1: Type, tp2: Type, depth: Int): Boolean = { + def isSub(ntp1: Type, ntp2: Type) = (ntp1.withoutAnnotations, ntp2.withoutAnnotations) match { + case (TypeRef(_, AnyClass, _), _) => false // avoid some warnings when Nothing/Any are on the other side + case (_, TypeRef(_, NothingClass, _)) => false + case (pt1: PolyType, pt2: PolyType) => isPolySubType(pt1, pt2) // @assume both .isHigherKinded (both normalized to PolyType) + case (_: PolyType, MethodType(ps, _)) if ps exists (_.tpe.isWildcard) => false // don't warn on HasMethodMatching on right hand side + case _ => // @assume !(both .isHigherKinded) thus cannot be subtypes + def tp_s(tp: Type): String = f"$tp%-20s ${util.shortClassOfInstance(tp)}%s" + devWarning(s"HK subtype check on $tp1 and $tp2, but both don't normalize to polytypes:\n tp1=${tp_s(ntp1)}\n tp2=${tp_s(ntp2)}") + false + } + + ( tp1.typeSymbol == NothingClass // @M Nothing is subtype of every well-kinded type + || tp2.typeSymbol == AnyClass // @M Any is supertype of every well-kinded type (@PP: is it? What about continuations plugin?) + || isSub(tp1.normalize, tp2.normalize) && annotationsConform(tp1, tp2) // @M! normalize reduces higher-kinded case to PolyType's + ) + } + + /** Does type `tp1` conform to `tp2`? */ + private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = { + if ((tp1 eq tp2) || isErrorOrWildcard(tp1) || isErrorOrWildcard(tp2)) return true + if ((tp1 eq NoType) || (tp2 eq NoType)) return false + if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass // !! I do not see how the "isPackageClass" would be warranted by the spec + if (tp2 eq NoPrefix) return tp1.typeSymbol.isPackageClass + if (isSingleType(tp1) && isSingleType(tp2) || isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2 + if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType(tp1, tp2, depth) + + /** First try, on the right: + * - unwrap Annotated types, BoundedWildcardTypes, + * - bind TypeVars on the right, if lhs is not Annotated nor BoundedWildcard + * - handle common cases for first-kind TypeRefs on both sides as a fast path. + */ + def firstTry = tp2 match { + // fast path: two typerefs, none of them HK + case tr2: TypeRef => + tp1 match { + case tr1: TypeRef => + val sym1 = tr1.sym + val sym2 = tr2.sym + val pre1 = tr1.pre + val pre2 = tr2.pre + (((if (sym1 == sym2) phase.erasedTypes || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth) + else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass && + (isUnifiable(pre1, pre2) || + isSameSpecializedSkolem(sym1, sym2, pre1, pre2) || + sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) && + isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth)) + || + sym2.isClass && { + val base = tr1 baseType sym2 + (base ne tr1) && isSubType(base, tr2, depth) + } + || + thirdTryRef(tr1, tr2)) + case _ => + secondTry + } + case AnnotatedType(_, _, _) => + isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) && + annotationsConform(tp1, tp2) + case BoundedWildcardType(bounds) => + isSubType(tp1, bounds.hi, depth) + case tv2 @ TypeVar(_, constr2) => + tp1 match { + case AnnotatedType(_, _, _) | BoundedWildcardType(_) => + secondTry + case _ => + tv2.registerBound(tp1, isLowerBound = true) + } + case _ => + secondTry + } + + /** Second try, on the left: + * - unwrap AnnotatedTypes, BoundedWildcardTypes, + * - bind typevars, + * - handle existential types by skolemization. + */ + def secondTry = tp1 match { + case AnnotatedType(_, _, _) => + isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) && + annotationsConform(tp1, tp2) + case BoundedWildcardType(bounds) => + isSubType(tp1.bounds.lo, tp2, depth) + case tv @ TypeVar(_,_) => + tv.registerBound(tp2, isLowerBound = false) + case ExistentialType(_, _) => + try { + skolemizationLevel += 1 + isSubType(tp1.skolemizeExistential, tp2, depth) + } finally { + skolemizationLevel -= 1 + } + case _ => + thirdTry + } + + def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = { + val sym2 = tp2.sym + sym2 match { + case NotNullClass => tp1.isNotNull + case SingletonClass => tp1.isStable || fourthTry + case _: ClassSymbol => + if (isRawType(tp2)) + isSubType(tp1, rawToExistential(tp2), depth) + else if (sym2.name == tpnme.REFINE_CLASS_NAME) + isSubType(tp1, sym2.info, depth) + else + fourthTry + case _: TypeSymbol => + if (sym2 hasFlag DEFERRED) { + val tp2a = tp2.bounds.lo + isDifferentTypeConstructor(tp2, tp2a) && + isSubType(tp1, tp2a, depth) || + fourthTry + } else { + isSubType(tp1.normalize, tp2.normalize, depth) + } + case _ => + fourthTry + } + } + + /** Third try, on the right: + * - decompose refined types. + * - handle typerefs, existentials, and notnull types. + * - handle left+right method types, polytypes, typebounds + */ + def thirdTry = tp2 match { + case tr2: TypeRef => + thirdTryRef(tp1, tr2) + case rt2: RefinedType => + (rt2.parents forall (isSubType(tp1, _, depth))) && + (rt2.decls forall (specializesSym(tp1, _, depth))) + case et2: ExistentialType => + et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry + case nn2: NotNullType => + tp1.isNotNull && isSubType(tp1, nn2.underlying, depth) + case mt2: MethodType => + tp1 match { + case mt1 @ MethodType(params1, res1) => + val params2 = mt2.params + val res2 = mt2.resultType + (sameLength(params1, params2) && + mt1.isImplicit == mt2.isImplicit && + matchingParams(params1, params2, mt1.isJava, mt2.isJava) && + isSubType(res1.substSym(params1, params2), res2, depth)) + // TODO: if mt1.params.isEmpty, consider NullaryMethodType? + case _ => + false + } + case pt2 @ NullaryMethodType(_) => + tp1 match { + // TODO: consider MethodType mt for which mt.params.isEmpty?? + case pt1 @ NullaryMethodType(_) => + isSubType(pt1.resultType, pt2.resultType, depth) + case _ => + false + } + case TypeBounds(lo2, hi2) => + tp1 match { + case TypeBounds(lo1, hi1) => + isSubType(lo2, lo1, depth) && isSubType(hi1, hi2, depth) + case _ => + false + } + case _ => + fourthTry + } + + /** Fourth try, on the left: + * - handle typerefs, refined types, notnull and singleton types. + */ + def fourthTry = tp1 match { + case tr1 @ TypeRef(pre1, sym1, _) => + sym1 match { + case NothingClass => true + case NullClass => + tp2 match { + case TypeRef(_, sym2, _) => + containsNull(sym2) + case _ => + isSingleType(tp2) && isSubType(tp1, tp2.widen, depth) + } + case _: ClassSymbol => + if (isRawType(tp1)) + isSubType(rawToExistential(tp1), tp2, depth) + else if (sym1.isModuleClass) tp2 match { + case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2) + case _ => false + } + else if (sym1.isRefinementClass) + isSubType(sym1.info, tp2, depth) + else false + + case _: TypeSymbol => + if (sym1 hasFlag DEFERRED) { + val tp1a = tp1.bounds.hi + isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth) + } else { + isSubType(tp1.normalize, tp2.normalize, depth) + } + case _ => + false + } + case RefinedType(parents1, _) => + parents1 exists (isSubType(_, tp2, depth)) + case _: SingletonType | _: NotNullType => + isSubType(tp1.underlying, tp2, depth) + case _ => + false + } + + firstTry + } + + + def isWeakSubType(tp1: Type, tp2: Type) = + tp1.deconst.normalize match { + case TypeRef(_, sym1, _) if isNumericValueClass(sym1) => + tp2.deconst.normalize match { + case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => + isNumericSubClass(sym1, sym2) + case tv2 @ TypeVar(_, _) => + tv2.registerBound(tp1, isLowerBound = true, isNumericBound = true) + case _ => + isSubType(tp1, tp2) + } + case tv1 @ TypeVar(_, _) => + tp2.deconst.normalize match { + case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => + tv1.registerBound(tp2, isLowerBound = false, isNumericBound = true) + case _ => + isSubType(tp1, tp2) + } + case _ => + isSubType(tp1, tp2) + } + + /** The isNumericValueType tests appear redundant, but without them + * test/continuations-neg/function3.scala goes into an infinite loop. + * (Even if the calls are to typeSymbolDirect.) + */ + def isNumericSubType(tp1: Type, tp2: Type): Boolean = ( + isNumericValueType(tp1) + && isNumericValueType(tp2) + && isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol) + ) + +} diff --git a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala new file mode 100644 index 0000000000..a002b01f70 --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala @@ -0,0 +1,282 @@ +package scala.reflect +package internal +package tpe + +import scala.collection.{ generic } +import generic.Clearable + + +private[internal] trait TypeConstraints { + self: SymbolTable => + import definitions._ + + /** A log of type variable with their original constraints. Used in order + * to undo constraints in the case of isSubType/isSameType failure. + */ + lazy val undoLog = newUndoLog + + protected def newUndoLog = new UndoLog + + class UndoLog extends Clearable { + private type UndoPairs = List[(TypeVar, TypeConstraint)] + //OPT this method is public so we can do `manual inlining` + var log: UndoPairs = List() + + /* + * These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog. + * + * The idea behind explicit locking mechanism is that all public methods that access mutable state + * will have to obtain the lock for their entire execution so both reads and writes can be kept in + * right order. Originally, that was achieved by overriding those public methods in + * `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take + * thunk as argument and if we keep them non-final there's no way to make them inlined so thunks + * can go away. + * + * By using explicit locking we can achieve inlining. + * + * NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot + * places implementation of `undo` or `undoUnless`). This should be changed back to protected + * once inliner is fixed. + */ + def lock(): Unit = () + def unlock(): Unit = () + + // register with the auto-clearing cache manager + perRunCaches.recordCache(this) + + /** Undo all changes to constraints to type variables upto `limit`. */ + //OPT this method is public so we can do `manual inlining` + def undoTo(limit: UndoPairs) { + assertCorrectThread() + while ((log ne limit) && log.nonEmpty) { + val (tv, constr) = log.head + tv.constr = constr + log = log.tail + } + } + + /** No sync necessary, because record should only + * be called from within an undo or undoUnless block, + * which is already synchronized. + */ + private[reflect] def record(tv: TypeVar) = { + log ::= ((tv, tv.constr.cloneInternal)) + } + + def clear() { + lock() + try { + if (settings.debug.value) + self.log("Clearing " + log.size + " entries from the undoLog.") + log = Nil + } finally unlock() + } + + // `block` should not affect constraints on typevars + def undo[T](block: => T): T = { + lock() + try { + val before = log + + try block + finally undoTo(before) + } finally unlock() + } + } + + /** @PP: Unable to see why these apparently constant types should need vals + * in every TypeConstraint, I lifted them out. + */ + private lazy val numericLoBound = IntClass.tpe + private lazy val numericHiBound = intersectionType(List(ByteClass.tpe, CharClass.tpe), ScalaPackageClass) + + /** A class expressing upper and lower bounds constraints of type variables, + * as well as their instantiations. + */ + class TypeConstraint(lo0: List[Type], hi0: List[Type], numlo0: Type, numhi0: Type, avoidWidening0: Boolean = false) { + def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType) + def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi)) + def this() = this(List(), List()) + + /* Syncnote: Type constraints are assumed to be used from only one + * thread. They are not exposed in api.Types and are used only locally + * in operations that are exposed from types. Hence, no syncing of any + * variables should be ncessesary. + */ + + /** Guard these lists against AnyClass and NothingClass appearing, + * else loBounds.isEmpty will have different results for an empty + * constraint and one with Nothing as a lower bound. [Actually + * guarding addLoBound/addHiBound somehow broke raw types so it + * only guards against being created with them.] + */ + private var lobounds = lo0 filterNot typeIsNothing + private var hibounds = hi0 filterNot typeIsAny + private var numlo = numlo0 + private var numhi = numhi0 + private var avoidWidening = avoidWidening0 + + def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds + def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds + def avoidWiden: Boolean = avoidWidening + + def addLoBound(tp: Type, isNumericBound: Boolean = false) { + // For some reason which is still a bit fuzzy, we must let Nothing through as + // a lower bound despite the fact that Nothing is always a lower bound. My current + // supposition is that the side-effecting type constraint accumulation mechanism + // depends on these subtype tests being performed to make forward progress when + // there are mutally recursive type vars. + // See pos/t6367 and pos/t6499 for the competing test cases. + val mustConsider = tp.typeSymbol match { + case NothingClass => true + case _ => !(lobounds contains tp) + } + if (mustConsider) { + if (isNumericBound && isNumericValueType(tp)) { + if (numlo == NoType || isNumericSubType(numlo, tp)) + numlo = tp + else if (!isNumericSubType(tp, numlo)) + numlo = numericLoBound + } + else lobounds ::= tp + } + } + + def checkWidening(tp: Type) { + if(tp.isStable) avoidWidening = true + else tp match { + case HasTypeMember(_, _) => avoidWidening = true + case _ => + } + } + + def addHiBound(tp: Type, isNumericBound: Boolean = false) { + // My current test case only demonstrates the need to let Nothing through as + // a lower bound, but I suspect the situation is symmetrical. + val mustConsider = tp.typeSymbol match { + case AnyClass => true + case _ => !(hibounds contains tp) + } + if (mustConsider) { + checkWidening(tp) + if (isNumericBound && isNumericValueType(tp)) { + if (numhi == NoType || isNumericSubType(tp, numhi)) + numhi = tp + else if (!isNumericSubType(numhi, tp)) + numhi = numericHiBound + } + else hibounds ::= tp + } + } + + def isWithinBounds(tp: Type): Boolean = + lobounds.forall(_ <:< tp) && + hibounds.forall(tp <:< _) && + (numlo == NoType || (numlo weak_<:< tp)) && + (numhi == NoType || (tp weak_<:< numhi)) + + var inst: Type = NoType // @M reduce visibility? + + def instValid = (inst ne null) && (inst ne NoType) + + def cloneInternal = { + val tc = new TypeConstraint(lobounds, hibounds, numlo, numhi, avoidWidening) + tc.inst = inst + tc + } + + override def toString = { + val boundsStr = { + val lo = loBounds filterNot typeIsNothing + val hi = hiBounds filterNot typeIsAny + val lostr = if (lo.isEmpty) Nil else List(lo.mkString(" >: (", ", ", ")")) + val histr = if (hi.isEmpty) Nil else List(hi.mkString(" <: (", ", ", ")")) + + lostr ++ histr mkString ("[", " | ", "]") + } + if (inst eq NoType) boundsStr + else boundsStr + " _= " + inst.safeToString + } + } + + /** Solve constraint collected in types `tvars`. + * + * @param tvars All type variables to be instantiated. + * @param tparams The type parameters corresponding to `tvars` + * @param variances The variances of type parameters; need to reverse + * solution direction for all contravariant variables. + * @param upper When `true` search for max solution else min. + */ + def solve(tvars: List[TypeVar], tparams: List[Symbol], + variances: List[Variance], upper: Boolean): Boolean = + solve(tvars, tparams, variances, upper, AnyDepth) + + def solve(tvars: List[TypeVar], tparams: List[Symbol], + variances: List[Variance], upper: Boolean, depth: Int): Boolean = { + + def solveOne(tvar: TypeVar, tparam: Symbol, variance: Variance) { + if (tvar.constr.inst == NoType) { + val up = if (variance.isContravariant) !upper else upper + tvar.constr.inst = null + val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo + //Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound)) + var cyclic = bound contains tparam + foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => { + val ok = (tparam2 != tparam) && ( + (bound contains tparam2) + || up && (tparam2.info.bounds.lo =:= tparam.tpeHK) + || !up && (tparam2.info.bounds.hi =:= tparam.tpeHK) + ) + if (ok) { + if (tvar2.constr.inst eq null) cyclic = true + solveOne(tvar2, tparam2, variance2) + } + }) + if (!cyclic) { + if (up) { + if (bound.typeSymbol != AnyClass) { + log(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)") + tvar addHiBound bound.instantiateTypeParams(tparams, tvars) + } + for (tparam2 <- tparams) + tparam2.info.bounds.lo.dealias match { + case TypeRef(_, `tparam`, _) => + log(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)") + tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars) + case _ => + } + } else { + if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) { + log(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)") + tvar addLoBound bound.instantiateTypeParams(tparams, tvars) + } + for (tparam2 <- tparams) + tparam2.info.bounds.hi.dealias match { + case TypeRef(_, `tparam`, _) => + log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)") + tvar addLoBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars) + case _ => + } + } + } + tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar + + //println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))) + val newInst = ( + if (up) { + if (depth != AnyDepth) glb(tvar.constr.hiBounds, depth) else glb(tvar.constr.hiBounds) + } else { + if (depth != AnyDepth) lub(tvar.constr.loBounds, depth) else lub(tvar.constr.loBounds) + } + ) + log(s"$tvar setInst $newInst") + tvar setInst newInst + //Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG + } + } + + // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info))) + foreach3(tvars, tparams, variances)(solveOne) + tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst)) + } +} diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala new file mode 100644 index 0000000000..51363c0f82 --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala @@ -0,0 +1,1144 @@ +package scala.reflect +package internal +package tpe + +import scala.collection.{ mutable, immutable } +import Flags._ +import scala.annotation.tailrec +import Variance._ + +private[internal] trait TypeMaps { + self: SymbolTable => + import definitions._ + + /** Normalize any type aliases within this type (@see Type#normalize). + * Note that this depends very much on the call to "normalize", not "dealias", + * so it is no longer carries the too-stealthy name "deAlias". + */ + object normalizeAliases extends TypeMap { + def apply(tp: Type): Type = tp match { + case TypeRef(_, sym, _) if sym.isAliasType => + def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp" + mapOver(logResult(msg)(tp.normalize)) + case _ => mapOver(tp) + } + } + + /** Remove any occurrence of type from this type and its parents */ + object dropSingletonType extends TypeMap { + def apply(tp: Type): Type = { + tp match { + case TypeRef(_, SingletonClass, _) => + AnyClass.tpe + case tp1 @ RefinedType(parents, decls) => + parents filter (_.typeSymbol != SingletonClass) match { + case Nil => AnyClass.tpe + case p :: Nil if decls.isEmpty => mapOver(p) + case ps => mapOver(copyRefinedType(tp1, ps, decls)) + } + case tp1 => + mapOver(tp1) + } + } + } + + /** Type with all top-level occurrences of abstract types replaced by their bounds */ + object abstractTypesToBounds extends TypeMap { + def apply(tp: Type): Type = tp match { + case TypeRef(_, sym, _) if sym.isAliasType => apply(tp.dealias) + case TypeRef(_, sym, _) if sym.isAbstractType => apply(tp.bounds.hi) + case rtp @ RefinedType(parents, decls) => copyRefinedType(rtp, parents mapConserve this, decls) + case AnnotatedType(_, _, _) => mapOver(tp) + case _ => tp // no recursion - top level only + } + } + + // Set to true for A* => Seq[A] + // (And it will only rewrite A* in method result types.) + // This is the pre-existing behavior. + // Or false for Seq[A] => Seq[A] + // (It will rewrite A* everywhere but method parameters.) + // This is the specified behavior. + protected def etaExpandKeepsStar = false + + /** Turn any T* types into Seq[T] except when + * in method parameter position. + */ + object dropIllegalStarTypes extends TypeMap { + def apply(tp: Type): Type = tp match { + case MethodType(params, restpe) => + // Not mapping over params + val restpe1 = apply(restpe) + if (restpe eq restpe1) tp + else MethodType(params, restpe1) + case TypeRef(_, RepeatedParamClass, arg :: Nil) => + seqType(arg) + case _ => + if (etaExpandKeepsStar) tp else mapOver(tp) + } + } + + trait AnnotationFilter extends TypeMap { + def keepAnnotation(annot: AnnotationInfo): Boolean + + override def mapOver(annot: AnnotationInfo) = + if (keepAnnotation(annot)) super.mapOver(annot) + else UnmappableAnnotation + } + + trait KeepOnlyTypeConstraints extends AnnotationFilter { + // filter keeps only type constraint annotations + def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass + } + + // todo. move these into scala.reflect.api + + /** A prototype for mapping a function over all possible types + */ + abstract class TypeMap(trackVariance: Boolean) extends (Type => Type) { + def this() = this(trackVariance = false) + def apply(tp: Type): Type + + private[this] var _variance: Variance = if (trackVariance) Covariant else Invariant + + def variance_=(x: Variance) = { assert(trackVariance, this) ; _variance = x } + def variance = _variance + + /** Map this function over given type */ + def mapOver(tp: Type): Type = tp match { + case tr @ TypeRef(pre, sym, args) => + val pre1 = this(pre) + val args1 = ( + if (trackVariance && args.nonEmpty && !variance.isInvariant && sym.typeParams.nonEmpty) + mapOverArgs(args, sym.typeParams) + else + args mapConserve this + ) + if ((pre1 eq pre) && (args1 eq args)) tp + else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), args1) + case ThisType(_) => tp + case SingleType(pre, sym) => + if (sym.isPackageClass) tp // short path + else { + val pre1 = this(pre) + if (pre1 eq pre) tp + else singleType(pre1, sym) + } + case MethodType(params, result) => + val params1 = flipped(mapOver(params)) + val result1 = this(result) + if ((params1 eq params) && (result1 eq result)) tp + else copyMethodType(tp, params1, result1.substSym(params, params1)) + case PolyType(tparams, result) => + val tparams1 = flipped(mapOver(tparams)) + val result1 = this(result) + if ((tparams1 eq tparams) && (result1 eq result)) tp + else PolyType(tparams1, result1.substSym(tparams, tparams1)) + case NullaryMethodType(result) => + val result1 = this(result) + if (result1 eq result) tp + else NullaryMethodType(result1) + case ConstantType(_) => tp + case SuperType(thistp, supertp) => + val thistp1 = this(thistp) + val supertp1 = this(supertp) + if ((thistp1 eq thistp) && (supertp1 eq supertp)) tp + else SuperType(thistp1, supertp1) + case TypeBounds(lo, hi) => + val lo1 = flipped(this(lo)) + val hi1 = this(hi) + if ((lo1 eq lo) && (hi1 eq hi)) tp + else TypeBounds(lo1, hi1) + case BoundedWildcardType(bounds) => + val bounds1 = this(bounds) + if (bounds1 eq bounds) tp + else BoundedWildcardType(bounds1.asInstanceOf[TypeBounds]) + case rtp @ RefinedType(parents, decls) => + val parents1 = parents mapConserve this + val decls1 = mapOver(decls) + copyRefinedType(rtp, parents1, decls1) + case ExistentialType(tparams, result) => + val tparams1 = mapOver(tparams) + val result1 = this(result) + if ((tparams1 eq tparams) && (result1 eq result)) tp + else newExistentialType(tparams1, result1.substSym(tparams, tparams1)) + case OverloadedType(pre, alts) => + val pre1 = if (pre.isInstanceOf[ClassInfoType]) pre else this(pre) + if (pre1 eq pre) tp + else OverloadedType(pre1, alts) + case AntiPolyType(pre, args) => + val pre1 = this(pre) + val args1 = args mapConserve this + if ((pre1 eq pre) && (args1 eq args)) tp + else AntiPolyType(pre1, args1) + case tv@TypeVar(_, constr) => + if (constr.instValid) this(constr.inst) + else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params)) //@M !args.isEmpty implies !typeParams.isEmpty + case NotNullType(tp) => + val tp1 = this(tp) + if (tp1 eq tp) tp + else NotNullType(tp1) + case AnnotatedType(annots, atp, selfsym) => + val annots1 = mapOverAnnotations(annots) + val atp1 = this(atp) + if ((annots1 eq annots) && (atp1 eq atp)) tp + else if (annots1.isEmpty) atp1 + else AnnotatedType(annots1, atp1, selfsym) + /* + case ErrorType => tp + case WildcardType => tp + case NoType => tp + case NoPrefix => tp + case ErasedSingleType(sym) => tp + */ + case _ => + tp + // throw new Error("mapOver inapplicable for " + tp); + } + + def withVariance[T](v: Variance)(body: => T): T = { + val saved = variance + variance = v + try body finally variance = saved + } + @inline final def flipped[T](body: => T): T = { + if (trackVariance) variance = variance.flip + try body + finally if (trackVariance) variance = variance.flip + } + protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = ( + if (trackVariance) + map2Conserve(args, tparams)((arg, tparam) => withVariance(variance * tparam.variance)(this(arg))) + else + args mapConserve this + ) + /** Applies this map to the symbol's info, setting variance = Invariant + * if necessary when the symbol is an alias. + */ + private def applyToSymbolInfo(sym: Symbol): Type = { + if (trackVariance && !variance.isInvariant && sym.isAliasType) + withVariance(Invariant)(this(sym.info)) + else + this(sym.info) + } + + /** Called by mapOver to determine whether the original symbols can + * be returned, or whether they must be cloned. + */ + protected def noChangeToSymbols(origSyms: List[Symbol]): Boolean = { + @tailrec def loop(syms: List[Symbol]): Boolean = syms match { + case Nil => true + case x :: xs => (x.info eq applyToSymbolInfo(x)) && loop(xs) + } + loop(origSyms) + } + + /** Map this function over given scope */ + def mapOver(scope: Scope): Scope = { + val elems = scope.toList + val elems1 = mapOver(elems) + if (elems1 eq elems) scope + else newScopeWith(elems1: _*) + } + + /** Map this function over given list of symbols */ + def mapOver(origSyms: List[Symbol]): List[Symbol] = { + // fast path in case nothing changes due to map + if (noChangeToSymbols(origSyms)) origSyms + // map is not the identity --> do cloning properly + else cloneSymbolsAndModify(origSyms, TypeMap.this) + } + + def mapOver(annot: AnnotationInfo): AnnotationInfo = { + val AnnotationInfo(atp, args, assocs) = annot + val atp1 = mapOver(atp) + val args1 = mapOverAnnotArgs(args) + // there is no need to rewrite assocs, as they are constants + + if ((args eq args1) && (atp eq atp1)) annot + else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation // some annotation arg was unmappable + else AnnotationInfo(atp1, args1, assocs) setPos annot.pos + } + + def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = { + val annots1 = annots mapConserve mapOver + if (annots1 eq annots) annots + else annots1 filterNot (_ eq UnmappableAnnotation) + } + + /** Map over a set of annotation arguments. If any + * of the arguments cannot be mapped, then return Nil. */ + def mapOverAnnotArgs(args: List[Tree]): List[Tree] = { + val args1 = args mapConserve mapOver + if (args1 contains UnmappableTree) Nil + else args1 + } + + def mapOver(tree: Tree): Tree = + mapOver(tree, () => return UnmappableTree) + + /** Map a tree that is part of an annotation argument. + * If the tree cannot be mapped, then invoke giveup(). + * The default is to transform the tree with + * TypeMapTransformer. + */ + def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = + (new TypeMapTransformer).transform(tree) + + /** This transformer leaves the tree alone except to remap + * its types. */ + class TypeMapTransformer extends Transformer { + override def transform(tree: Tree) = { + val tree1 = super.transform(tree) + val tpe1 = TypeMap.this(tree1.tpe) + if ((tree eq tree1) && (tree.tpe eq tpe1)) + tree + else + tree1.shallowDuplicate.setType(tpe1) + } + } + } + + abstract class TypeTraverser extends TypeMap { + def traverse(tp: Type): Unit + def apply(tp: Type): Type = { traverse(tp); tp } + } + + abstract class TypeTraverserWithResult[T] extends TypeTraverser { + def result: T + def clear(): Unit + } + + abstract class TypeCollector[T](initial: T) extends TypeTraverser { + var result: T = _ + def collect(tp: Type) = { + result = initial + traverse(tp) + result + } + } + + /** The raw to existential map converts a ''raw type'' to an existential type. + * It is necessary because we might have read a raw type of a + * parameterized Java class from a class file. At the time we read the type + * the corresponding class file might still not be read, so we do not + * know what the type parameters of the type are. Therefore + * the conversion of raw types to existential types might not have taken place + * in ClassFileparser.sigToType (where it is usually done). + */ + def rawToExistential = new TypeMap { + private var expanded = immutable.Set[Symbol]() + def apply(tp: Type): Type = tp match { + case TypeRef(pre, sym, List()) if isRawIfWithoutArgs(sym) => + if (expanded contains sym) AnyRefClass.tpe + else try { + expanded += sym + val eparams = mapOver(typeParamsToExistentials(sym)) + existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe))) + } finally { + expanded -= sym + } + case _ => + mapOver(tp) + } + } + /*** + *@M: I think this is more desirable, but Martin prefers to leave raw-types as-is as much as possible + object rawToExistentialInJava extends TypeMap { + def apply(tp: Type): Type = tp match { + // any symbol that occurs in a java sig, not just java symbols + // see http://lampsvn.epfl.ch/trac/scala/ticket/2454#comment:14 + case TypeRef(pre, sym, List()) if !sym.typeParams.isEmpty => + val eparams = typeParamsToExistentials(sym, sym.typeParams) + existentialAbstraction(eparams, TypeRef(pre, sym, eparams map (_.tpe))) + case _ => + mapOver(tp) + } + } + */ + + /** Used by existentialAbstraction. + */ + class ExistentialExtrapolation(tparams: List[Symbol]) extends TypeMap(trackVariance = true) { + private val occurCount = mutable.HashMap[Symbol, Int]() + private def countOccs(tp: Type) = { + tp foreach { + case TypeRef(_, sym, _) => + if (tparams contains sym) + occurCount(sym) += 1 + case _ => () + } + } + def extrapolate(tpe: Type): Type = { + tparams foreach (t => occurCount(t) = 0) + countOccs(tpe) + for (tparam <- tparams) + countOccs(tparam.info) + + apply(tpe) + } + + /** If these conditions all hold: + * 1) we are in covariant (or contravariant) position + * 2) this type occurs exactly once in the existential scope + * 3) the widened upper (or lower) bound of this type contains no references to tparams + * Then we replace this lone occurrence of the type with the widened upper (or lower) bound. + * All other types pass through unchanged. + */ + def apply(tp: Type): Type = { + val tp1 = mapOver(tp) + if (variance.isInvariant) tp1 + else tp1 match { + case TypeRef(pre, sym, args) if tparams contains sym => + val repl = if (variance.isPositive) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo + val count = occurCount(sym) + val containsTypeParam = tparams exists (repl contains _) + def msg = { + val word = if (variance.isPositive) "upper" else "lower" + s"Widened lone occurrence of $tp1 inside existential to $word bound" + } + if (!repl.typeSymbol.isBottomClass && count == 1 && !containsTypeParam) + logResult(msg)(repl) + else + tp1 + case _ => + tp1 + } + } + override def mapOver(tp: Type): Type = tp match { + case SingleType(pre, sym) => + if (sym.isPackageClass) tp // short path + else { + val pre1 = this(pre) + if ((pre1 eq pre) || !pre1.isStable) tp + else singleType(pre1, sym) + } + case _ => super.mapOver(tp) + } + + // Do not discard the types of existential ident's. The + // symbol of the Ident itself cannot be listed in the + // existential's parameters, so the resulting existential + // type would be ill-formed. + override def mapOver(tree: Tree) = tree match { + case Ident(_) if tree.tpe.isStable => tree + case _ => super.mapOver(tree) + } + } + + /** Might the given symbol be important when calculating the prefix + * of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`, + * the result will be `tp` unchanged if `pre` is trivial and `clazz` + * is a symbol such that isPossiblePrefix(clazz) == false. + */ + def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass + + protected[internal] def skipPrefixOf(pre: Type, clazz: Symbol) = ( + (pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz) + ) + + def newAsSeenFromMap(pre: Type, clazz: Symbol): AsSeenFromMap = + new AsSeenFromMap(pre, clazz) + + /** A map to compute the asSeenFrom method. + */ + class AsSeenFromMap(seenFromPrefix: Type, seenFromClass: Symbol) extends TypeMap with KeepOnlyTypeConstraints { + // Some example source constructs relevant in asSeenFrom: + // + // object CaptureThis { + // trait X[A] { def f: this.type = this } + // class Y[A] { def f: this.type = this } + // // Created new existential to represent This(CaptureThis.X) seen from CaptureThis.X[B]: type _1.type <: CaptureThis.X[B] with Singleton + // def f1[B] = new X[B] { } + // // TODO - why is the behavior different when it's a class? + // def f2[B] = new Y[B] { } + // } + // class CaptureVal[T] { + // val f: java.util.List[_ <: T] = null + // // Captured existential skolem for type _$1 seen from CaptureVal.this.f.type: type _$1 + // def g = f get 0 + // } + // class ClassParam[T] { + // // AsSeenFromMap(Inner.this.type, class Inner)/classParameterAsSeen(T)#loop(ClassParam.this.type, class ClassParam) + // class Inner(lhs: T) { def f = lhs } + // } + def capturedParams: List[Symbol] = _capturedParams + def capturedSkolems: List[Symbol] = _capturedSkolems + + def apply(tp: Type): Type = tp match { + case tp @ ThisType(_) => thisTypeAsSeen(tp) + case tp @ SingleType(_, sym) => if (sym.isPackageClass) tp else singleTypeAsSeen(tp) + case tp @ TypeRef(_, sym, _) if isTypeParamOfEnclosingClass(sym) => classParameterAsSeen(tp) + case _ => mapOver(tp) + } + + private var _capturedSkolems: List[Symbol] = Nil + private var _capturedParams: List[Symbol] = Nil + private val isStablePrefix = seenFromPrefix.isStable + + // isBaseClassOfEnclosingClassOrInfoIsNotYetComplete would be a more accurate + // but less succinct name. + private def isBaseClassOfEnclosingClass(base: Symbol) = { + def loop(encl: Symbol): Boolean = ( + isPossiblePrefix(encl) + && ((encl isSubClass base) || loop(encl.owner.enclClass)) + ) + // The hasCompleteInfo guard is necessary to avoid cycles during the typing + // of certain classes, notably ones defined inside package objects. + !base.hasCompleteInfo || loop(seenFromClass) + } + + /** Is the symbol a class type parameter from one of the enclosing + * classes, or a base class of one of them? + */ + private def isTypeParamOfEnclosingClass(sym: Symbol): Boolean = ( + sym.isTypeParameter + && sym.owner.isClass + && isBaseClassOfEnclosingClass(sym.owner) + ) + + /** Creates an existential representing a type parameter which appears + * in the prefix of a ThisType. + */ + protected def captureThis(pre: Type, clazz: Symbol): Type = { + capturedParams find (_.owner == clazz) match { + case Some(p) => p.tpe + case _ => + val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre) + _capturedParams ::= qvar + debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}") + qvar.tpe + } + } + protected def captureSkolems(skolems: List[Symbol]) { + for (p <- skolems; if !(capturedSkolems contains p)) { + debuglog(s"Captured $p seen from $seenFromPrefix") + _capturedSkolems ::= p + } + } + + /** Find the type argument in an applied type which corresponds to a type parameter. + * The arguments are required to be related as follows, through intermediary `clazz`. + * An exception will be thrown if this is violated. + * + * @param lhs its symbol is a type parameter of `clazz` + * @param rhs a type application constructed from `clazz` + */ + private def correspondingTypeArgument(lhs: Type, rhs: Type): Type = { + val TypeRef(_, lhsSym, lhsArgs) = lhs + val TypeRef(_, rhsSym, rhsArgs) = rhs + require(lhsSym.safeOwner == rhsSym, s"$lhsSym is not a type parameter of $rhsSym") + + // Find the type parameter position; we'll use the corresponding argument + val argIndex = rhsSym.typeParams indexOf lhsSym + + if (argIndex >= 0 && argIndex < rhsArgs.length) // @M! don't just replace the whole thing, might be followed by type application + appliedType(rhsArgs(argIndex), lhsArgs mapConserve this) + else if (rhsSym.tpe_*.parents exists typeIsErroneous) // don't be too zealous with the exceptions, see #2641 + ErrorType + else + abort(s"something is wrong: cannot make sense of type application\n $lhs\n $rhs") + } + + // 0) @pre: `classParam` is a class type parameter + // 1) Walk the owner chain of `seenFromClass` until we find the class which owns `classParam` + // 2) Take the base type of the prefix at that point with respect to the owning class + // 3) Solve for the type parameters through correspondence with the type args of the base type + // + // Only class type parameters (and not skolems) are considered, because other type parameters + // are not influenced by the prefix through which they are seen. Note that type params of + // anonymous type functions, which currently can only arise from normalising type aliases, are + // owned by the type alias of which they are the eta-expansion. + private def classParameterAsSeen(classParam: Type): Type = { + val TypeRef(_, tparam, _) = classParam + + def loop(pre: Type, clazz: Symbol): Type = { + // have to deconst because it may be a Class[T] + def nextBase = (pre baseType clazz).deconst + //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary + if (skipPrefixOf(pre, clazz)) + mapOver(classParam) + else if (!matchesPrefixAndClass(pre, clazz)(tparam.owner)) + loop(nextBase.prefix, clazz.owner) + else nextBase match { + case applied @ TypeRef(_, _, _) => correspondingTypeArgument(classParam, applied) + case ExistentialType(eparams, qtpe) => captureSkolems(eparams) ; loop(qtpe, clazz) + case t => abort(s"$tparam in ${tparam.owner} cannot be instantiated from ${seenFromPrefix.widen}") + } + } + loop(seenFromPrefix, seenFromClass) + } + + // Does the candidate symbol match the given prefix and class? + // Since pre may be something like ThisType(A) where trait A { self: B => }, + // we have to test the typeSymbol of the widened type, not pre.typeSymbol, or + // B will not be considered. + private def matchesPrefixAndClass(pre: Type, clazz: Symbol)(candidate: Symbol) = pre.widen match { + case _: TypeVar => false + case wide => (clazz == candidate) && (wide.typeSymbol isSubClass clazz) + } + + // Whether the annotation tree currently being mapped over has had a This(_) node rewritten. + private[this] var wroteAnnotation = false + private object annotationArgRewriter extends TypeMapTransformer { + private def matchesThis(thiz: Symbol) = matchesPrefixAndClass(seenFromPrefix, seenFromClass)(thiz) + + // what symbol should really be used? + private def newThis(): Tree = { + wroteAnnotation = true + val presym = seenFromPrefix.widen.typeSymbol + val thisSym = presym.owner.newValue(presym.name.toTermName, presym.pos) setInfo seenFromPrefix + gen.mkAttributedQualifier(seenFromPrefix, thisSym) + } + + /** Rewrite `This` trees in annotation argument trees */ + override def transform(tree: Tree): Tree = super.transform(tree) match { + case This(_) if matchesThis(tree.symbol) => newThis() + case tree => tree + } + } + + // This becomes considerably cheaper if we optimize for the common cases: + // where the prefix is stable and where no This nodes are rewritten. If + // either is true, then we don't need to worry about calling giveup. So if + // the prefix is unstable, use a stack variable to indicate whether the tree + // was touched. This takes us to one allocation per AsSeenFromMap rather + // than an allocation on every call to mapOver, and no extra work when the + // tree only has its types remapped. + override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = { + if (isStablePrefix) + annotationArgRewriter transform tree + else { + val saved = wroteAnnotation + wroteAnnotation = false + try annotationArgRewriter transform tree + finally if (wroteAnnotation) giveup() else wroteAnnotation = saved + } + } + + private def thisTypeAsSeen(tp: ThisType): Type = { + def loop(pre: Type, clazz: Symbol): Type = { + val pre1 = pre match { + case SuperType(thistpe, _) => thistpe + case _ => pre + } + if (skipPrefixOf(pre, clazz)) + mapOver(tp) // TODO - is mapOver necessary here? + else if (!matchesPrefixAndClass(pre, clazz)(tp.sym)) + loop((pre baseType clazz).prefix, clazz.owner) + else if (pre1.isStable) + pre1 + else + captureThis(pre1, clazz) + } + loop(seenFromPrefix, seenFromClass) + } + + private def singleTypeAsSeen(tp: SingleType): Type = { + val SingleType(pre, sym) = tp + + val pre1 = this(pre) + if (pre1 eq pre) tp + else if (pre1.isStable) singleType(pre1, sym) + else pre1.memberType(sym).resultType //todo: this should be rolled into existential abstraction + } + + override def toString = s"AsSeenFromMap($seenFromPrefix, $seenFromClass)" + } + + /** A base class to compute all substitutions */ + abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap { + assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to) + + /** Are `sym` and `sym1` the same? Can be tuned by subclasses. */ + protected def matches(sym: Symbol, sym1: Symbol): Boolean = sym eq sym1 + + /** Map target to type, can be tuned by subclasses */ + protected def toType(fromtp: Type, tp: T): Type + + protected def renameBoundSyms(tp: Type): Type = tp match { + case MethodType(ps, restp) => + createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1))) + case PolyType(bs, restp) => + createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1))) + case ExistentialType(bs, restp) => + createFromClonedSymbols(bs, restp)(newExistentialType) + case _ => + tp + } + + @tailrec private def subst(tp: Type, sym: Symbol, from: List[Symbol], to: List[T]): Type = ( + if (from.isEmpty) tp + // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(tp, from)) + else if (matches(from.head, sym)) toType(tp, to.head) + else subst(tp, sym, from.tail, to.tail) + ) + + def apply(tp0: Type): Type = if (from.isEmpty) tp0 else { + val boundSyms = tp0.boundSyms + val tp1 = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0 + val tp = mapOver(tp1) + def substFor(sym: Symbol) = subst(tp, sym, from, to) + + tp match { + // @M + // 1) arguments must also be substituted (even when the "head" of the + // applied type has already been substituted) + // example: (subst RBound[RT] from [type RT,type RBound] to + // [type RT&,type RBound&]) = RBound&[RT&] + // 2) avoid loops (which occur because alpha-conversion is + // not performed properly imo) + // e.g. if in class Iterable[a] there is a new Iterable[(a,b)], + // we must replace the a in Iterable[a] by (a,b) + // (must not recurse --> loops) + // 3) replacing m by List in m[Int] should yield List[Int], not just List + case TypeRef(NoPrefix, sym, args) => + val tcon = substFor(sym) + if ((tp eq tcon) || args.isEmpty) tcon + else appliedType(tcon.typeConstructor, args) + case SingleType(NoPrefix, sym) => + substFor(sym) + case _ => + tp + } + } + } + + /** A map to implement the `substSym` method. */ + class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) { + def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2)) + + protected def toType(fromtp: Type, sym: Symbol) = fromtp match { + case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args) + case SingleType(pre, _) => singleType(pre, sym) + } + @tailrec private def subst(sym: Symbol, from: List[Symbol], to: List[Symbol]): Symbol = ( + if (from.isEmpty) sym + // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(sym, from)) + else if (matches(from.head, sym)) to.head + else subst(sym, from.tail, to.tail) + ) + private def substFor(sym: Symbol) = subst(sym, from, to) + + override def apply(tp: Type): Type = ( + if (from.isEmpty) tp + else tp match { + case TypeRef(pre, sym, args) if pre ne NoPrefix => + val newSym = substFor(sym) + // mapOver takes care of subst'ing in args + mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) ) + // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams)) + case SingleType(pre, sym) if pre ne NoPrefix => + val newSym = substFor(sym) + mapOver( if (sym eq newSym) tp else singleType(pre, newSym) ) + case _ => + super.apply(tp) + } + ) + + object mapTreeSymbols extends TypeMapTransformer { + val strictCopy = newStrictTreeCopier + + def termMapsTo(sym: Symbol) = from indexOf sym match { + case -1 => None + case idx => Some(to(idx)) + } + + // if tree.symbol is mapped to another symbol, passes the new symbol into the + // constructor `trans` and sets the symbol and the type on the resulting tree. + def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match { + case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe + case None => tree + } + + // changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified. + override def transform(tree: Tree) = { + // super.transform maps symbol references in the types of `tree`. it also copies trees where necessary. + super.transform(tree) match { + case id @ Ident(_) => + transformIfMapped(id)(toSym => + strictCopy.Ident(id, toSym.name)) + + case sel @ Select(qual, name) => + transformIfMapped(sel)(toSym => + strictCopy.Select(sel, qual, toSym.name)) + + case tree => tree + } + } + } + override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = { + mapTreeSymbols.transform(tree) + } + } + + /** A map to implement the `subst` method. */ + class SubstTypeMap(from: List[Symbol], to: List[Type]) + extends SubstMap(from, to) { + protected def toType(fromtp: Type, tp: Type) = tp + + override def mapOver(tree: Tree, giveup: () => Nothing): Tree = { + object trans extends TypeMapTransformer { + override def transform(tree: Tree) = tree match { + case Ident(name) => + from indexOf tree.symbol match { + case -1 => super.transform(tree) + case idx => + val totpe = to(idx) + if (totpe.isStable) tree.duplicate setType totpe + else giveup() + } + case _ => + super.transform(tree) + } + } + trans.transform(tree) + } + } + + /** A map to implement the `substThis` method. */ + class SubstThisMap(from: Symbol, to: Type) extends TypeMap { + def apply(tp: Type): Type = tp match { + case ThisType(sym) if (sym == from) => to + case _ => mapOver(tp) + } + } + + class SubstWildcardMap(from: List[Symbol]) extends TypeMap { + def apply(tp: Type): Type = try { + tp match { + case TypeRef(_, sym, _) if from contains sym => + BoundedWildcardType(sym.info.bounds) + case _ => + mapOver(tp) + } + } catch { + case ex: MalformedType => + WildcardType + } + } + + // dependent method types + object IsDependentCollector extends TypeCollector(false) { + def traverse(tp: Type) { + if (tp.isImmediatelyDependent) result = true + else if (!result) mapOver(tp) + } + } + + object ApproximateDependentMap extends TypeMap { + def apply(tp: Type): Type = + if (tp.isImmediatelyDependent) WildcardType + else mapOver(tp) + } + + /** Note: This map is needed even for non-dependent method types, despite what the name might imply. + */ + class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints { + private val actuals = actuals0.toIndexedSeq + private val existentials = new Array[Symbol](actuals.size) + def existentialsNeeded: List[Symbol] = existentials.filter(_ ne null).toList + + private object StableArg { + def unapply(param: Symbol) = Arg unapply param map actuals filter (tp => + tp.isStable && (tp.typeSymbol != NothingClass) + ) + } + private object Arg { + def unapply(param: Symbol) = Some(params indexOf param) filter (_ >= 0) + } + + def apply(tp: Type): Type = mapOver(tp) match { + // unsound to replace args by unstable actual #3873 + case SingleType(NoPrefix, StableArg(arg)) => arg + // (soundly) expand type alias selections on implicit arguments, + // see depmet_implicit_oopsla* test cases -- typically, `param.isImplicit` + case tp1 @ TypeRef(SingleType(NoPrefix, Arg(pid)), sym, targs) => + val arg = actuals(pid) + val res = typeRef(arg, sym, targs) + if (res.typeSymbolDirect.isAliasType) res.dealias else tp1 + // don't return the original `tp`, which may be different from `tp1`, + // due to dropping annotations + case tp1 => tp1 + } + + /* Return the type symbol for referencing a parameter inside the existential quantifier. + * (Only needed if the actual is unstable.) + */ + private def existentialFor(pid: Int) = { + if (existentials(pid) eq null) { + val param = params(pid) + existentials(pid) = ( + param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags) + setInfo singletonBounds(actuals(pid)) + ) + } + existentials(pid) + } + + //AM propagate more info to annotations -- this seems a bit ad-hoc... (based on code by spoon) + override def mapOver(arg: Tree, giveup: ()=>Nothing): Tree = { + // TODO: this should be simplified; in the stable case, one can + // probably just use an Ident to the tree.symbol. + // + // @PP: That leads to failure here, where stuff no longer has type + // 'String @Annot("stuff")' but 'String @Annot(x)'. + // + // def m(x: String): String @Annot(x) = x + // val stuff = m("stuff") + // + // (TODO cont.) Why an existential in the non-stable case? + // + // @PP: In the following: + // + // def m = { val x = "three" ; val y: String @Annot(x) = x; y } + // + // m is typed as 'String @Annot(x) forSome { val x: String }'. + // + // Both examples are from run/constrained-types.scala. + object treeTrans extends Transformer { + override def transform(tree: Tree): Tree = tree.symbol match { + case StableArg(actual) => + gen.mkAttributedQualifier(actual, tree.symbol) + case Arg(pid) => + val sym = existentialFor(pid) + Ident(sym) copyAttrs tree setType typeRef(NoPrefix, sym, Nil) + case _ => + super.transform(tree) + } + } + treeTrans transform arg + } + } + + /** A map to convert every occurrence of a wildcard type to a fresh + * type variable */ + object wildcardToTypeVarMap extends TypeMap { + def apply(tp: Type): Type = tp match { + case WildcardType => + TypeVar(tp, new TypeConstraint) + case BoundedWildcardType(bounds) => + TypeVar(tp, new TypeConstraint(bounds)) + case _ => + mapOver(tp) + } + } + + /** A map to convert every occurrence of a type variable to a wildcard type. */ + object typeVarToOriginMap extends TypeMap { + def apply(tp: Type): Type = tp match { + case TypeVar(origin, _) => origin + case _ => mapOver(tp) + } + } + + /** A map to implement the `contains` method. */ + class ContainsCollector(sym: Symbol) extends TypeCollector(false) { + def traverse(tp: Type) { + if (!result) { + tp.normalize match { + case TypeRef(_, sym1, _) if (sym == sym1) => result = true + case SingleType(_, sym1) if (sym == sym1) => result = true + case _ => mapOver(tp) + } + } + } + + override def mapOver(arg: Tree) = { + for (t <- arg) { + traverse(t.tpe) + if (t.symbol == sym) + result = true + } + arg + } + } + + /** A map to implement the `contains` method. */ + class ContainsTypeCollector(t: Type) extends TypeCollector(false) { + def traverse(tp: Type) { + if (!result) { + if (tp eq t) result = true + else mapOver(tp) + } + } + override def mapOver(arg: Tree) = { + for (t <- arg) + traverse(t.tpe) + + arg + } + } + + /** A map to implement the `filter` method. */ + class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) { + override def collect(tp: Type) = super.collect(tp).reverse + + def traverse(tp: Type) { + if (p(tp)) result ::= tp + mapOver(tp) + } + } + + /** A map to implement the `collect` method. */ + class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) { + override def collect(tp: Type) = super.collect(tp).reverse + + def traverse(tp: Type) { + if (pf.isDefinedAt(tp)) result ::= pf(tp) + mapOver(tp) + } + } + + class ForEachTypeTraverser(f: Type => Unit) extends TypeTraverser { + def traverse(tp: Type) { + f(tp) + mapOver(tp) + } + } + + /** A map to implement the `filter` method. */ + class FindTypeCollector(p: Type => Boolean) extends TypeCollector[Option[Type]](None) { + def traverse(tp: Type) { + if (result.isEmpty) { + if (p(tp)) result = Some(tp) + mapOver(tp) + } + } + } + + /** A map to implement the `contains` method. */ + object ErroneousCollector extends TypeCollector(false) { + def traverse(tp: Type) { + if (!result) { + result = tp.isError + mapOver(tp) + } + } + } + + object adaptToNewRunMap extends TypeMap { + + private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = { + if (phase.flatClasses || sym.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass) + sym + else if (sym.isModuleClass) { + val sourceModule1 = adaptToNewRun(pre, sym.sourceModule) + + sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse { + val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s" + debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass)) + sym + } + } + else { + var rebind0 = pre.findMember(sym.name, BRIDGE, 0, stableOnly = true) orElse { + if (sym.isAliasType) throw missingAliasException + devWarning(s"$pre.$sym no longer exist at phase $phase") + throw new MissingTypeControl // For build manager and presentation compiler purposes + } + /** The two symbols have the same fully qualified name */ + def corresponds(sym1: Symbol, sym2: Symbol): Boolean = + sym1.name == sym2.name && (sym1.isPackageClass || corresponds(sym1.owner, sym2.owner)) + if (!corresponds(sym.owner, rebind0.owner)) { + debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString) + val bcs = pre.baseClasses.dropWhile(bc => !corresponds(bc, sym.owner)) + if (bcs.isEmpty) + assert(pre.typeSymbol.isRefinementClass, pre) // if pre is a refinementclass it might be a structural type => OK to leave it in. + else + rebind0 = pre.baseType(bcs.head).member(sym.name) + debuglog( + "ADAPT2 pre = " + pre + + ", bcs.head = " + bcs.head + + ", sym = " + sym.fullLocationString + + ", rebind = " + rebind0.fullLocationString + ) + } + rebind0.suchThat(sym => sym.isType || sym.isStable) orElse { + debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType) + throw new MalformedType(pre, sym.nameString) + } + } + } + def apply(tp: Type): Type = tp match { + case ThisType(sym) => + try { + val sym1 = adaptToNewRun(sym.owner.thisType, sym) + if (sym1 == sym) tp else ThisType(sym1) + } catch { + case ex: MissingTypeControl => + tp + } + case SingleType(pre, sym) => + if (sym.isPackage) tp + else { + val pre1 = this(pre) + try { + val sym1 = adaptToNewRun(pre1, sym) + if ((pre1 eq pre) && (sym1 eq sym)) tp + else singleType(pre1, sym1) + } catch { + case _: MissingTypeControl => + tp + } + } + case TypeRef(pre, sym, args) => + if (sym.isPackageClass) tp + else { + val pre1 = this(pre) + val args1 = args mapConserve (this) + try { + val sym1 = adaptToNewRun(pre1, sym) + if ((pre1 eq pre) && (sym1 eq sym) && (args1 eq args)/* && sym.isExternal*/) { + tp + } else if (sym1 == NoSymbol) { + devWarning(s"adapt to new run failed: pre=$pre pre1=$pre1 sym=$sym") + tp + } else { + copyTypeRef(tp, pre1, sym1, args1) + } + } catch { + case ex: MissingAliasControl => + apply(tp.dealias) + case _: MissingTypeControl => + tp + } + } + case MethodType(params, restp) => + val restp1 = this(restp) + if (restp1 eq restp) tp + else copyMethodType(tp, params, restp1) + case NullaryMethodType(restp) => + val restp1 = this(restp) + if (restp1 eq restp) tp + else NullaryMethodType(restp1) + case PolyType(tparams, restp) => + val restp1 = this(restp) + if (restp1 eq restp) tp + else PolyType(tparams, restp1) + + // Lukas: we need to check (together) whether we should also include parameter types + // of PolyType and MethodType in adaptToNewRun + + case ClassInfoType(parents, decls, clazz) => + if (clazz.isPackageClass) tp + else { + val parents1 = parents mapConserve (this) + if (parents1 eq parents) tp + else ClassInfoType(parents1, decls, clazz) + } + case RefinedType(parents, decls) => + val parents1 = parents mapConserve (this) + if (parents1 eq parents) tp + else refinedType(parents1, tp.typeSymbol.owner, decls, tp.typeSymbol.owner.pos) + case SuperType(_, _) => mapOver(tp) + case TypeBounds(_, _) => mapOver(tp) + case TypeVar(_, _) => mapOver(tp) + case AnnotatedType(_,_,_) => mapOver(tp) + case NotNullType(_) => mapOver(tp) + case ExistentialType(_, _) => mapOver(tp) + case _ => tp + } + } + +} diff --git a/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala new file mode 100644 index 0000000000..263b0f5a3e --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala @@ -0,0 +1,29 @@ +package scala.reflect +package internal +package tpe + +private[internal] trait TypeToStrings { + self: SymbolTable => + + /** The maximum number of recursions allowed in toString + */ + final val maxTostringRecursions = 50 + + private var tostringRecursions = 0 + + protected def typeToString(tpe: Type): String = + if (tostringRecursions >= maxTostringRecursions) { + devWarning("Exceeded recursion depth attempting to print " + util.shortClassOfInstance(tpe)) + if (settings.debug.value) + (new Throwable).printStackTrace + + "..." + } + else + try { + tostringRecursions += 1 + tpe.safeToString + } finally { + tostringRecursions -= 1 + } +} -- cgit v1.2.3