From 6c8a12fbfe02db2890fefd60546dd43230e34bc3 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Wed, 10 Feb 2016 15:03:49 -0800 Subject: Less distribution of logic across TypeRef subclasses Redeem myself for e1c732db44 -- hopefully. I inlined `thisInfo` (== `sym.info`), and made sure to use `relativeInfo` wherever prefix and args influence the result of the query that we're delegating to the underlying type. For type aliases, use `normalize` for `baseClasses` and `decls`, since `relativeInfo` breaks the gnarly SI-8177. I think normalize is okay for aliases, as the prefix should not matter when computing base classes, and infos for the members in `decls` are given the `asSeenFrom` treatment individually downstream. (It's a tight rope between rewriting too many symbols and maintaining correctness. Documented the trade-off in the code.) Renamed the unimaginative `transform` to `relativize`, which, although everything is relative, hopefully says a bit more about its usage than `transform`. Removed a lot of over-factoring in the TypeRef hierarchy. Ultimately, we need to reduce the number of TypeRef subclasses further, I think. It's really hard to follow what's going on. Removed the `thisInfo` cache, since `sym.info` and `relativeInfo` are both cached. Made the cache invalidation hooks a bit more OO-y. Compare `Symbol`s with `eq` -- they don't define an `equals` method. Also, don't recurse in isSubtype when a `baseType` results in `NoType`. This happens a lot and is cheap to check, so I posit (without proof), that it's better for performance (and clarity) to check before recursing. --- src/reflect/scala/reflect/internal/Types.scala | 218 +++++++++++---------- .../scala/reflect/internal/tpe/TypeComparers.scala | 18 +- 2 files changed, 128 insertions(+), 108 deletions(-) (limited to 'src/reflect') diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 1b0251a642..0b0e851d69 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -1882,7 +1882,8 @@ trait Types narrowedCache } - private[Types] def invalidateModuleTypeRefCaches(): Unit = { + override private[Types] def invalidateTypeRefCaches(): Unit = { + super.invalidateTypeRefCaches() narrowedCache = null } override protected def finishPrefix(rest: String) = objectPrefix + rest @@ -1900,7 +1901,7 @@ trait Types // I think this is okay, but see #1241 (r12414), #2208, and typedTypeConstructor in Typers override protected def normalizeImpl: Type = sym.info.normalize - override protected def finishPrefix(rest: String) = "" + thisInfo + override protected def finishPrefix(rest: String) = "" + sym.info } class NoArgsTypeRef(pre0: Type, sym0: Symbol) extends TypeRef(pre0, sym0, Nil) { @@ -1937,36 +1938,71 @@ trait Types trait NonClassTypeRef extends TypeRef { require(sym.isNonClassType, sym) - /* Syncnote: These are pure caches for performance; no problem to evaluate these - * several times. Hence, no need to protected with synchronized in a multi-threaded - * usage scenario. - */ + /** Syncnote: These are pure caches for performance; no problem to evaluate these + * several times. Hence, no need to protected with synchronized in a multi-threaded + * usage scenario. + */ private var relativeInfoCache: Type = _ - private var relativeInfoPeriod: Period = NoPeriod - private[Types] def invalidateNonClassTypeRefCaches(): Unit = { + private var relativeInfoCacheValidForPeriod: Period = NoPeriod + private var relativeInfoCacheValidForSymInfo: Type = _ + + override private[Types] def invalidateTypeRefCaches(): Unit = { + super.invalidateTypeRefCaches() relativeInfoCache = NoType - relativeInfoPeriod = NoPeriod + relativeInfoCacheValidForPeriod = NoPeriod + relativeInfoCacheValidForSymInfo = null } - private[Types] def relativeInfo = /*trace(s"relativeInfo(${safeToString}})")*/{ - if (relativeInfoPeriod != currentPeriod) { - relativeInfoCache = memberInfoInstantiated - relativeInfoPeriod = currentPeriod + final override protected def relativeInfo = { + val symInfo = sym.info + if ((relativeInfoCache eq null) || (relativeInfoCacheValidForSymInfo ne symInfo) || (relativeInfoCacheValidForPeriod != currentPeriod)) { + relativeInfoCache = super.relativeInfo + + if (this.isInstanceOf[AbstractTypeRef]) validateRelativeInfo() + + relativeInfoCacheValidForSymInfo = symInfo + relativeInfoCacheValidForPeriod = currentPeriod } relativeInfoCache } + + private def validateRelativeInfo(): Unit = relativeInfoCache match { + // If a subtyping cycle is not detected here, we'll likely enter an infinite + // loop before a sensible error can be issued. SI-5093 is one example. + case x: SubType if x.supertype eq this => + relativeInfoCache = null + throw new RecoverableCyclicReference(sym) + case _ => + } } + trait AliasTypeRef extends NonClassTypeRef { require(sym.isAliasType, sym) override def dealias = if (typeParamsMatchArgs) betaReduce.dealias else super.dealias override def narrow = normalize.narrow - override def thisInfo = normalize override def prefix = if (this ne normalize) normalize.prefix else pre override def termSymbol = if (this ne normalize) normalize.termSymbol else super.termSymbol override def typeSymbol = if (this ne normalize) normalize.typeSymbol else sym + + // `baseClasses` is sensitive to type args when referencing type members + // consider `type foo[x] = x`, `typeOf[foo[String]].baseClasses` should be the same as `typeOf[String].baseClasses`, + // which would be lost by looking at `sym.info` without propagating args + // since classes cannot be overridden, the prefix can be ignored + // (in fact, taking the prefix into account by replacing `normalize` + // with `relativeInfo` breaks pos/t8177g.scala, which is probably a bug, but a tricky one... + override def baseClasses = normalize.baseClasses + + // similar reasoning holds here as for baseClasses + // as another example, consider the type alias `Foo` in `class O { o => type Foo = X { val bla: o.Bar }; type Bar }` + // o1.Foo and o2.Foo have different decls `val bla: o1.Bar` versus `val bla: o2.Bar` + // In principle, you should only call `sym.info.decls` when you know `sym.isClass`, + // and you should `relativize` the infos of the resulting members. + // The latter is certainly violated in multiple spots in the codebase (the members are usually transformed correctly, though). + override def decls: Scope = normalize.decls + // beta-reduce, but don't do partial application -- cycles have been checked in typeRef override protected def normalizeImpl = if (typeParamsMatchArgs) betaReduce.normalize @@ -1989,7 +2025,7 @@ trait Types // // this crashes pos/depmet_implicit_tpbetareduce.scala // appliedType(sym.info, typeArgs).asSeenFrom(pre, sym.owner) - override def betaReduce = transform(sym.info.resultType) + override def betaReduce = relativize(sym.info.resultType) /** SI-3731, SI-8177: when prefix is changed to `newPre`, maintain consistency of prefix and sym * (where the symbol refers to a declaration "embedded" in the prefix). @@ -2039,31 +2075,12 @@ trait Types trait AbstractTypeRef extends NonClassTypeRef { require(sym.isAbstractType, sym) - /** Syncnote: Pure performance caches; no need to synchronize in multi-threaded environment - */ - private var symInfoCache: Type = _ - private var thisInfoCache: Type = _ + override def baseClasses = relativeInfo.baseClasses + override def decls = relativeInfo.decls + override def bounds = relativeInfo.bounds + + override protected[Types] def baseTypeSeqImpl: BaseTypeSeq = bounds.hi.baseTypeSeq prepend this - override def thisInfo = { - val symInfo = sym.info - if (thisInfoCache == null || (symInfo ne symInfoCache)) { - symInfoCache = symInfo - thisInfoCache = memberInfoInstantiated match { - // If a subtyping cycle is not detected here, we'll likely enter an infinite - // loop before a sensible error can be issued. SI-5093 is one example. - case x: SubType if x.supertype eq this => - throw new RecoverableCyclicReference(sym) - case tp => tp - } - } - thisInfoCache - } - private[Types] def invalidateAbstractTypeRefCaches(): Unit = { - symInfoCache = null - thisInfoCache = null - } - override def bounds = thisInfo.bounds - override protected[Types] def baseTypeSeqImpl: BaseTypeSeq = transform(bounds.hi).baseTypeSeq prepend this override def kind = "AbstractTypeRef" } @@ -2107,23 +2124,32 @@ trait Types finalizeHash(h, 2) } + // interpret symbol's info in terms of the type's prefix and type args + protected def relativeInfo: Type = appliedType(sym.info.asSeenFrom(pre, sym.owner), argsOrDummies) + // @M: propagate actual type params (args) to `tp`, by replacing // formal type parameters with actual ones. If tp is higher kinded, // the "actual" type arguments are types that simply reference the // corresponding type parameters (unbound type variables) - final def transform(tp: Type): Type = - if (args.isEmpty) { - if (isHigherKinded && (phase.erasedTypes || !isRawIfWithoutArgs(sym))) - tp.asSeenFrom(pre, sym.owner).instantiateTypeParams(typeParams, dummyArgs) - else - tp.asSeenFrom(pre, sym.owner) - } else { - // This situation arises when a typevar is encountered for which + // + // NOTE: for performance, as well as correctness, we do not attempt + // to reframe trivial types in terms of our prefix and args. + // asSeenFrom, by construction, is the identity for trivial types, + // and substitution cannot change them either (abstract types are non-trivial, specifically because they may need to be replaced) + // For correctness, the result for `tp == NoType` must be `NoType`, + // if we don't shield against this, and apply instantiateTypeParams to it, + // this would result in an ErrorType, which behaves differently during subtyping + // (and thus on recursion, subtyping would go from false -- since a NoType is involved -- + // to true, as ErrorType is always a sub/super type....) + final def relativize(tp: Type): Type = + if (tp.isTrivial) tp + else if (args.isEmpty && (phase.erasedTypes || !isHigherKinded || isRawIfWithoutArgs(sym))) tp.asSeenFrom(pre, sym.owner) + else { + // The type params and type args should always match in length, + // though a mismatch can arise when a typevar is encountered for which // too little information is known to determine its kind, and - // it later turns out not to have kind *. See SI-4070. Only - // logging it for now. - val tparams = sym.typeParams - if (!sameLength(tparams, args)) devWarning(s"$this.transform($tp), but tparams.isEmpty and args=$args") + // it later turns out not to have kind *. See SI-4070. + val formals = sym.typeParams // If we're called with a poly type, and we were to run the `asSeenFrom`, over the entire // type, we can end up with new symbols for the type parameters (clones from TypeMap). @@ -2149,31 +2175,39 @@ trait Types // It's kind of a helper for computing baseType (since it tries to propagate our type args to some // other type, which has to be related to this type for that to make sense). // + def seenFromOwnerInstantiated(tp: Type): Type = + tp.asSeenFrom(pre, sym.owner).instantiateTypeParams(formals, argsOrDummies) + tp match { - case PolyType(`tparams`, result) => PolyType(tparams, result.asSeenFrom(pre, sym.owner).instantiateTypeParams(tparams, args)) - case _ => tp.asSeenFrom(pre, sym.owner).instantiateTypeParams(tparams, args) + case PolyType(`formals`, result) => PolyType(formals, seenFromOwnerInstantiated(result)) + case _ => seenFromOwnerInstantiated(tp) } } + private def argsOrDummies = if (args.isEmpty) dummyArgs else args + final override def baseType(clazz: Symbol): Type = - if (sym == clazz) this - else if (sym.isClass) transform(sym.info.baseType(clazz)) + if (clazz eq sym) this + // NOTE: this first goes to requested base type, *then* does asSeenFrom prefix & instantiates args + else if (sym.isClass) relativize(sym.info.baseType(clazz)) else baseTypeOfNonClassTypeRef(clazz) - //@M! use appliedType on the polytype that represents the bounds (or if aliastype, the rhs) - final protected def memberInfoInstantiated: Type = - appliedType(sym.info.asSeenFrom(pre, sym.owner), if (args.isEmpty) dummyArgs else args) - + // two differences with class type basetype: + // (1) first relativize the type, then go to the requested base type + // (2) cache for cycle robustness private def baseTypeOfNonClassTypeRef(clazz: Symbol) = try { basetypeRecursions += 1 if (basetypeRecursions >= LogPendingBaseTypesThreshold) baseTypeOfNonClassTypeRefLogged(clazz) - else memberInfoInstantiated.baseType(clazz) + else relativeInfo.baseType(clazz) } finally basetypeRecursions -= 1 private def baseTypeOfNonClassTypeRefLogged(clazz: Symbol) = - if (pendingBaseTypes add this) try memberInfoInstantiated.baseType(clazz) finally pendingBaseTypes -= this - else if (clazz == AnyClass) clazz.tpe + if (pendingBaseTypes add this) try relativeInfo.baseType(clazz) finally { pendingBaseTypes remove this } + // TODO: is this optimization for AnyClass worth it? (or is it playing last-ditch cycle defense?) + // NOTE: for correctness, it only applies for non-class types + // (e.g., a package class should not get AnyTpe as its supertype, ever) + else if (clazz eq AnyClass) AnyTpe else NoType // eta-expand, subtyping relies on eta-expansion of higher-kinded types @@ -2207,17 +2241,16 @@ trait Types // (they are allowed to be rebound more liberally) def coevolveSym(pre1: Type): Symbol = sym - def thisInfo = sym.info def initializedTypeParams = sym.info.typeParams def typeParamsMatchArgs = sameLength(initializedTypeParams, args) - override def baseClasses = thisInfo.baseClasses + override def baseTypeSeqDepth = baseTypeSeq.maxDepth override def prefix = pre override def termSymbol = super.termSymbol override def termSymbolDirect = super.termSymbol override def typeArgs = args - override def typeOfThis = transform(sym.typeOfThis) + override def typeOfThis = relativize(sym.typeOfThis) override def typeSymbol = sym override def typeSymbolDirect = sym @@ -2230,22 +2263,24 @@ trait Types } } - override def decls: Scope = { - sym.info match { - case TypeRef(_, sym1, _) => - assert(sym1 != sym, this) // @MAT was != typeSymbol - case _ => - } - thisInfo.decls - } + // Since type parameters cannot occur in super types, no need to relativize before looking at base *classes*. + // Similarly, our prefix can occur in super class types, but it cannot influence which classes those types resolve to. + // For example, `class Outer { outer => class Inner extends outer.Foo; class Foo }` + // `outer`'s value has no impact on which `Foo` is selected, since classes cannot be overridden. + // besides being faster, we can't use relativeInfo because it causes cycles + override def baseClasses = sym.info.baseClasses + + // in principle, we should use `relativeInfo.decls`, but I believe all uses of `decls` will correctly `relativize` the individual members + override def decls: Scope = sym.info.decls + protected[Types] def baseTypeSeqImpl: BaseTypeSeq = if (sym.info.baseTypeSeq exists (_.typeSymbolDirect.isAbstractType)) // SI-8046 base type sequence might have more elements in a subclass, we can't map it element wise. - transform(sym.info).baseTypeSeq + relativize(sym.info).baseTypeSeq else // Optimization: no abstract types, we can compute the BTS of this TypeRef as an element-wise map // of the BTS of the referenced symbol. - sym.info.baseTypeSeq map transform + sym.info.baseTypeSeq map relativize override def baseTypeSeq: BaseTypeSeq = { val cache = baseTypeSeqCache @@ -2276,9 +2311,10 @@ trait Types ) protected def finishPrefix(rest: String) = ( if (sym.isInitialized && sym.isAnonymousClass && !phase.erasedTypes) - parentsString(thisInfo.parents) + refinementString + parentsString(sym.info.parents) + refinementString else rest - ) + ) + private def noArgsString = finishPrefix(preString + sym.nameString) private def tupleTypeString: String = args match { case Nil => noArgsString @@ -2368,7 +2404,7 @@ trait Types if (period != currentPeriod) { tpe.parentsPeriod = currentPeriod if (!isValidForBaseClasses(period)) { - tpe.parentsCache = tpe.thisInfo.parents map tpe.transform + tpe.parentsCache = tpe.sym.info.parents map tpe.relativize } else if (tpe.parentsCache == null) { // seems this can happen if things are corrupted enough, see #2641 tpe.parentsCache = List(AnyTpe) } @@ -4580,32 +4616,14 @@ trait Types invalidateCaches(tp, updatedSyms) } - def invalidateCaches(t: Type, updatedSyms: List[Symbol]) = { - t match { - case st: SingleType if updatedSyms.contains(st.sym) => st.invalidateSingleTypeCaches() - case _ => - } - t match { - case tr: NonClassTypeRef if updatedSyms.contains(tr.sym) => tr.invalidateNonClassTypeRefCaches() - case _ => - } - t match { - case tr: AbstractTypeRef if updatedSyms.contains(tr.sym) => tr.invalidateAbstractTypeRefCaches() - case _ => - } - t match { - case tr: TypeRef if updatedSyms.contains(tr.sym) => tr.invalidateTypeRefCaches() - case _ => - } - t match { - case tr: ModuleTypeRef if updatedSyms.contains(tr.sym) => tr.invalidateModuleTypeRefCaches() - case _ => - } + def invalidateCaches(t: Type, updatedSyms: List[Symbol]) = t match { + case st: SingleType if updatedSyms.contains(st.sym) => st.invalidateSingleTypeCaches() + case tr: TypeRef if updatedSyms.contains(tr.sym) => tr.invalidateTypeRefCaches() case ct: CompoundType if ct.baseClasses.exists(updatedSyms.contains) => ct.invalidatedCompoundTypeCaches() case _ => } - } + val shorthands = Set( "scala.collection.immutable.List", diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala index e6d7b11cad..cf274f24bb 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -58,7 +58,7 @@ trait TypeComparers { false private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean = ( - if (sym1 == sym2) + if (sym1 eq sym2) sym1.hasPackageFlag || sym1.owner.hasPackageFlag || phase.erasedTypes || pre1 =:= pre2 else (sym1.name == sym2.name) && isUnifiable(pre1, pre2) @@ -79,7 +79,7 @@ trait TypeComparers { def isDifferentTypeConstructor(tp1: Type, tp2: Type) = !isSameTypeConstructor(tp1, tp2) private def isSameTypeConstructor(tr1: TypeRef, tr2: TypeRef): Boolean = ( - (tr1.sym == tr2.sym) + (tr1.sym eq tr2.sym) && !isDifferentType(tr1.pre, tr2.pre) ) private def isSameTypeConstructor(tp1: Type, tp2: Type): Boolean = ( @@ -222,7 +222,7 @@ trait TypeComparers { case SingleType(pre1, sym1) => tp2 match { case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1, pre1, sym2, pre2) ; case _ => false } case PolyType(ps1, res1) => tp2 match { case PolyType(ps2, res2) => equalTypeParamsAndResult(ps1, res1, ps2, res2) ; case _ => false } case ExistentialType(qs1, res1) => tp2 match { case ExistentialType(qs2, res2) => equalTypeParamsAndResult(qs1, res1, qs2, res2) ; case _ => false } - case ThisType(sym1) => tp2 match { case ThisType(sym2) => sym1 == sym2 ; case _ => false } + case ThisType(sym1) => tp2 match { case ThisType(sym2) => sym1 eq sym2 ; case _ => false } case ConstantType(c1) => tp2 match { case ConstantType(c2) => c1 == c2 ; case _ => false } case NullaryMethodType(res1) => tp2 match { case NullaryMethodType(res2) => res1 =:= res2 ; case _ => false } case TypeBounds(lo1, hi1) => tp2 match { case TypeBounds(lo2, hi2) => lo1 =:= lo2 && hi1 =:= hi2 ; case _ => false } @@ -344,7 +344,7 @@ trait TypeComparers { // in the same class, and the 'x' in the ThisType has in its override chain // the 'x' in the SuperType, then the types conform. private def isThisAndSuperSubtype(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match { - case (SingleType(ThisType(lpre), v1), SingleType(SuperType(ThisType(rpre), _), v2)) => (lpre == rpre) && (v1.overrideChain contains v2) + case (SingleType(ThisType(lpre), v1), SingleType(SuperType(ThisType(rpre), _), v2)) => (lpre eq rpre) && (v1.overrideChain contains v2) case _ => false } @@ -361,8 +361,8 @@ trait TypeComparers { 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?) + ( (tp1.typeSymbol eq NothingClass) // @M Nothing is subtype of every well-kinded type + || (tp2.typeSymbol eq 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 ) } @@ -394,7 +394,7 @@ trait TypeComparers { val sym2 = tr2.sym val pre1 = tr1.pre val pre2 = tr2.pre - (((if (sym1 == sym2) phase.erasedTypes || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth) + (((if (sym1 eq 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) || @@ -403,7 +403,9 @@ trait TypeComparers { || sym2.isClass && { val base = tr1 baseType sym2 - (base ne tr1) && isSubType(base, tr2, depth) + // During bootstrap, `base eq NoType` occurs about 2.5 times as often as `base ne NoType`. + // The extra check seems like a worthwhile optimization (about 2.5M useless calls to isSubtype saved during that run). + (base ne tr1) && (base ne NoType) && isSubType(base, tr2, depth) } || thirdTryRef(tr1, tr2)) -- cgit v1.2.3