From 684e87427850053db58707e2b7f3f51e10f882a0 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 4 Apr 2013 13:53:00 -0700 Subject: Transcendent rewrite of isSameType. A highly satisfying rewrite of isSameType. It's faster, clearer, shorter, better commented, and closer to correct. I am especially pleased that t5580b stopped compiling, given that nobody seemed to have much idea why it compiled in the first place. --- .../scala/reflect/internal/tpe/TypeComparers.scala | 259 ++++++++------------- test/files/neg/t5580b.check | 6 + test/files/neg/t5580b.scala | 13 ++ test/files/pos/t5580b.scala | 19 -- 4 files changed, 120 insertions(+), 177 deletions(-) create mode 100644 test/files/neg/t5580b.check create mode 100644 test/files/neg/t5580b.scala delete mode 100644 test/files/pos/t5580b.scala diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala index d408857cf3..da8e64ea16 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -57,9 +57,12 @@ trait TypeComparers { } 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) + 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) + ) def isDifferentType(tp1: Type, tp2: Type): Boolean = try { @@ -126,7 +129,13 @@ trait TypeComparers { tp2.typeSymbol.isPackageClass else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec tp1.typeSymbol.isPackageClass + else if (tp1.isInstanceOf[AnnotatedType] || tp2.isInstanceOf[AnnotatedType]) + annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && (tp1.withoutAnnotations =:= tp2.withoutAnnotations) else { + // We flush out any AnnotatedTypes before calling isSameType2 because + // unlike most other subclasses of Type, we have to allow for equivalence of any + // combination of { tp1, tp2 } { is, is not } an AnnotatedType - this because the + // logic of "annotationsConform" is arbitrary and unknown. isSameType2(tp1, tp2) || { val tp1n = normalizePlus(tp1) val tp2n = normalizePlus(tp2) @@ -135,165 +144,99 @@ trait TypeComparers { } } - 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 _ => + private def isSameHKTypes(tp1: Type, tp2: Type) = ( + tp1.isHigherKinded + && tp2.isHigherKinded + && (tp1.normalize =:= tp2.normalize) + ) + private def isSameTypeRef(tr1: TypeRef, tr2: TypeRef) = ( + equalSymsAndPrefixes(tr1.sym, tr1.pre, tr2.sym, tr2.pre) + && (isSameHKTypes(tr1, tr2) || isSameTypes(tr1.args, tr2.args)) + ) + + private def isSameSingletonType(tp1: SingletonType, tp2: SingletonType): Boolean = { + // We don't use dealiasWiden here because we are looking for the SAME type, + // and widening leads to a less specific type. The logic is along the lines of + // dealiasAndFollowUnderlyingAsLongAsTheTypeIsEquivalent. This method is only + // called after a surface comparison has failed, so if chaseDealiasedUnderlying + // does not produce a type other than tp1 and tp2, return false. + @tailrec def chaseDealiasedUnderlying(tp: Type): Type = tp.underlying.dealias match { + case next: SingletonType if tp ne next => chaseDealiasedUnderlying(next) + case _ => tp } - tp1 match { - case _: AnnotatedType => - return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations - case _ => + val origin1 = chaseDealiasedUnderlying(tp1) + val origin2 = chaseDealiasedUnderlying(tp2) + ((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2) + } + + private def isSameMethodType(mt1: MethodType, mt2: MethodType) = ( + isSameTypes(mt1.paramTypes, mt2.paramTypes) + && (mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params)) + && (mt1.isImplicit == mt2.isImplicit) + ) + + private def equalTypeParamsAndResult(tparams1: List[Symbol], res1: Type, tparams2: List[Symbol], res2: Type) = { + def subst(info: Type) = info.substSym(tparams2, tparams1) + // corresponds does not check length of two sequences before checking the predicate, + // but SubstMap assumes it has been checked (SI-2956) + ( sameLength(tparams1, tparams2) + && (tparams1 corresponds tparams2)((p1, p2) => p1.info =:= subst(p2.info)) + && (res1 =:= subst(res2)) + ) + } + + def isSameType2(tp1: Type, tp2: Type): Boolean = { + /** Here we highlight those unfortunate type-like constructs which + * are hidden bundles of mutable state, cruising the type system picking + * up any type constraints naive enough to get into their hot rods. + */ + def mutateNonTypeConstructs(lhs: Type, rhs: Type) = lhs match { + case BoundedWildcardType(bounds) => bounds containsType rhs + case tv @ TypeVar(_, _) => tv.registerTypeEquality(rhs, typeVarLHS = lhs eq tp1) + case TypeRef(tv @ TypeVar(_, _), sym, _) => tv.registerTypeSelection(sym, rhs) + case _ => false } - tp2 match { - case _: AnnotatedType => - return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations - case _ => + /* SingletonType receives this additional scrutiny because there are + * a variety of Types which must be treated as equivalent even if they + * arrive in different guises. For instance, object Foo in the following + * might appear in (at least) the four given below. + * + * package pkg { object Foo ; type Bar = Foo.type } + * + * ModuleClassTypeRef(pkg.type, Foo: ModuleClassSymbol, Nil) + * ThisType(Foo: ModuleClassSymbol) + * SingleType(pkg.type, Foo: ModuleSymbol) + * AliasTypeRef(NoPrefix, sym: AliasSymbol, Nil) where sym.info is one of the above + */ + def sameSingletonType = tp1 match { + case tp1: SingletonType => tp2 match { + case tp2: SingletonType => isSameSingletonType(tp1, tp2) + case _ => false + } + case _ => false } - 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 + /** Those false cases certainly are ugly. There's a proposed SIP to deuglify it. + * https://docs.google.com/a/improving.org/document/d/1onPrzSqyDpHScc9PS_hpxJwa3FlPtthxw-bAuuEe8uA + */ + def sameTypeAndSameCaseClass = tp1 match { + case tp1: TypeRef => tp2 match { case tp2: TypeRef => isSameTypeRef(tp1, tp2) ; case _ => false } + case tp1: MethodType => tp2 match { case tp2: MethodType => isSameMethodType(tp1, tp2) ; case _ => false } + case RefinedType(ps1, decls1) => tp2 match { case RefinedType(ps2, decls2) => isSameTypes(ps1, ps2) && (decls1 isSameScope decls2) ; case _ => false } + 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 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 } + case _ => false } + + ( sameTypeAndSameCaseClass + || sameSingletonType + || mutateNonTypeConstructs(tp1, tp2) + || mutateNonTypeConstructs(tp2, tp1) + ) } def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth) diff --git a/test/files/neg/t5580b.check b/test/files/neg/t5580b.check new file mode 100644 index 0000000000..45fde46ff9 --- /dev/null +++ b/test/files/neg/t5580b.check @@ -0,0 +1,6 @@ +t5580b.scala:11: error: polymorphic expression cannot be instantiated to expected type; + found : [A]scala.collection.mutable.Set[A] + required: scala.collection.mutable.Map[bar,scala.collection.mutable.Set[bar]] + if (map.get(tmp).isEmpty) map.put(tmp,collection.mutable.Set()) + ^ +one error found diff --git a/test/files/neg/t5580b.scala b/test/files/neg/t5580b.scala new file mode 100644 index 0000000000..2161da4584 --- /dev/null +++ b/test/files/neg/t5580b.scala @@ -0,0 +1,13 @@ +import scala.collection.mutable.WeakHashMap +import scala.collection.JavaConversions._ + +class bar { } + +class foo { + val map = WeakHashMap[AnyRef, collection.mutable.Map[bar, collection.mutable.Set[bar]]]() + + def test={ + val tmp:bar=null + if (map.get(tmp).isEmpty) map.put(tmp,collection.mutable.Set()) + } +} diff --git a/test/files/pos/t5580b.scala b/test/files/pos/t5580b.scala deleted file mode 100644 index d5a4a0a2b2..0000000000 --- a/test/files/pos/t5580b.scala +++ /dev/null @@ -1,19 +0,0 @@ -/** It's a pos test because it does indeed compile, - * not so much because I'm glad it does. Testing - * that error messages created and discarded during - * implicit search don't blow it up. - */ - -import scala.collection.mutable.WeakHashMap -import scala.collection.JavaConversions._ - -class bar { } - -class foo { - val map = WeakHashMap[AnyRef, collection.mutable.Map[bar, collection.mutable.Set[bar]]]() - - def test={ - val tmp:bar=null - if (map.get(tmp).isEmpty) map.put(tmp,collection.mutable.Set()) - } -} -- cgit v1.2.3