From a6d26a142672c47b457b6ef7d042e4880ad3345a Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 22 Jan 2014 18:51:00 +0100 Subject: wip on typecomparers --- src/dotty/tools/dotc/core/TypeComparer.scala | 347 ++++++++++++++++++++++++--- 1 file changed, 311 insertions(+), 36 deletions(-) (limited to 'src/dotty/tools/dotc/core/TypeComparer.scala') diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 3a15a50e1..8762cf637 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -23,6 +23,8 @@ class TypeComparer(initctx: Context) extends DotClass { private var pendingSubTypes: mutable.Set[(Type, Type)] = null private var recCount = 0 + final val oldCompare = true // ### + /** If the constraint is frozen we cannot add new bounds to the constraint. */ protected var frozenConstraint = false @@ -102,34 +104,40 @@ class TypeComparer(initctx: Context) extends DotClass { * @return Whether the augmented constraint is still satisfiable. */ def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { - param == bound || - !frozenConstraint && { - constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}") - val res = bound match { - case bound: PolyParam if constraint contains bound => - val TypeBounds(lo, hi) = constraint.bounds(bound) - if (lo eq hi) - addConstraint(param, lo, fromBelow) - else if (fromBelow && param.occursIn(lo, fromBelow = true)) - unify(param, bound) - else if (!fromBelow && param.occursIn(hi, fromBelow = false)) - unify(bound, param) - else - addConstraint1(param, bound, fromBelow) && - addConstraint1(bound, param, !fromBelow) - case bound: AndOrType if fromBelow != bound.isAnd => - addConstraint(param, bound.tp1, fromBelow) && - addConstraint(param, bound.tp2, fromBelow) - case bound: WildcardType => + param == bound || // ### + !frozenConstraint && { // ### + + constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}") + val res = bound.dealias.stripTypeVar match { + case bound: PolyParam if constraint contains bound => + val TypeBounds(lo, hi) = constraint.bounds(bound) + if (lo eq hi) + addConstraint(param, lo, fromBelow) + else if (param == bound) true - case _ => - addConstraint1(param, bound, fromBelow) - } - constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}") - res + else if (fromBelow && param.occursIn(lo, fromBelow = true)) + unify(param, bound) + else if (!fromBelow && param.occursIn(hi, fromBelow = false)) + unify(bound, param) + else + addConstraint1(param, bound, fromBelow) && + addConstraint1(bound, param, !fromBelow) + case bound: AndOrType if fromBelow != bound.isAnd => + addConstraint(param, bound.tp1, fromBelow) && + addConstraint(param, bound.tp2, fromBelow) + case bound: WildcardType => + true + case bound => // !!! remove to keep the originals + addConstraint1(param, bound, fromBelow) } + constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}") + res + } // ### } + def isConstrained(param: PolyParam): Boolean = + !frozenConstraint && (constraint contains param) + /** Solve constraint set for given type parameter `param`. * If `fromBelow` is true the parameter is approximated by its lower bound, * otherwise it is approximated by its upper bound. However, any occurrences @@ -162,6 +170,9 @@ class TypeComparer(initctx: Context) extends DotClass { finally frozenConstraint = saved } + def isNonBottomSubType(tp1: Type, tp2: Type): Boolean = + !(tp2 isRef NothingClass) && isSubType(tp1, tp2) + def isSubType(tp1: Type, tp2: Type): Boolean = if (tp1 == NoType || tp2 == NoType) false else if (tp1 eq tp2) true @@ -177,7 +188,8 @@ class TypeComparer(initctx: Context) extends DotClass { } */ val result = - if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2) + if (recCount < LogPendingSubTypesThreshold) + if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2) else monitoredIsSubType(tp1, tp2) recCount -= 1 if (!result) constraint = saved @@ -212,14 +224,277 @@ class TypeComparer(initctx: Context) extends DotClass { !pendingSubTypes(p) && { try { pendingSubTypes += p - firstTry(tp1, tp2) + if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2) } finally { pendingSubTypes -= p } } } - def firstTry(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") { + def compare(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") { + tp2 match { + case tp2: ProtoType => + isMatchedByProto(tp2, tp1) + case tp2: TypeVar => + isSubType(tp1, tp2.underlying) + case tp2: WildcardType => + def compareWildcard = tp2.optBounds match { + case TypeBounds(_, hi2) => isSubType(tp1, hi2) + case NoType => true + } + compareWildcard + case tp2: AnnotatedType => + isSubType(tp1, tp2.tpe) // todo: refine? + case ErrorType => + true + case AndType(left2, right2) => + isSubType(tp1, left2) && isSubType(tp1, right2) + case _ => + compare1(tp1, tp2) + } + } + + def compare1(tp1: Type, tp2: Type): Boolean = { + tp1 match { + case tref1: TypeRef => + val sym1 = tref1.symbol + tref1.info match { + case TypeBounds(lo1, hi1) => + if (lo1 eq hi1) return compare(hi1, tp2) + else if (sym1 is GADTFlexType) + return isSubType(hi1, tp2) || + trySetType(tref1, TypeBounds(lo1, hi1 & tp2)) + case _ => + if ((sym1 eq NothingClass) && tp2.isInstanceOf[ValueType]) return true + if ((sym1 eq NullClass) && tp2.dealias.typeSymbol.isNullableClass) return true + } + case param1: PolyParam if isConstrained(param1) => + def comparePoly = ( + param1 == tp2 + || isSubTypeWhenFrozen(bounds(param1).hi, tp2) + || { if ((tp2 isRef defn.NothingClass) && ctx.typerState.isGlobalCommittable) + ctx.log(s"!!! instantiating to Nothing: $tp1") + addConstraint(param1, tp2, fromBelow = false) + } + ) + return comparePoly + case tp1 @ ThisType(cls) if cls is ModuleClass => + tp2 match { + case tp2: TermRef => + return tp2.symbol.moduleClass == cls && cls.owner.thisType <:< tp2.prefix + case _ => + } + case tp1: TypeVar => + return compare(tp1.underlying, tp2) + case tp1: WildcardType => + def compareWildcard = tp1.optBounds match { + case TypeBounds(lo1, _) => isSubType(lo1, tp2) // todo: use short-circuiting to current method more often? + case NoType => true + } + return compareWildcard + case tp1: AnnotatedType => + return isSubType(tp1.tpe, tp2) + case ErrorType => + return true + case OrType(left1, right1) => + return isSubType(left1, tp2) && isSubType(right1, tp2) + case _ => + } + rightIsSuper(tp1, tp2) + } + + def rightIsSuper(tp1: Type, tp2: Type): Boolean = tp2 match { + case tp2: NamedType => + def compareNamed: Boolean = { + val sym2 = tp2.symbol + val pre2 = tp2.prefix + tp1 match { + case tp1: NamedType => + val sym1 = tp1.symbol + val pre1 = tp1.prefix + if (sym1 == sym2) { + if ( ctx.erasedTypes + || sym1.isStaticOwner + || isSubType(pre1, pre2) + || pre1.isInstanceOf[ThisType] && pre2.isInstanceOf[ThisType]) return true + } else if (tp1.name == tp2.name && isSubType(pre1, pre2)) return true + case _ => + } + if (sym2.isClass) { + val base = tp1.baseType(sym2) + if (base.exists && (base ne tp1)) isSubType(base, tp2) + else + (sym2 == defn.SingletonClass) && tp1.isStable || + (defn.hkTraits contains sym2) && isSubTypeHK(tp1.widen, tp2) || + leftIsSub2(tp1, tp2) + } + else tp2.info match { + case TypeBounds(lo2, hi2) => + if (lo2 eq hi2) + isSubType(tp1.dealias, hi2.dealias) + else if (sym2 is GADTFlexType) + isSubType(tp1, lo2) || trySetType(tp2, TypeBounds(lo2 | tp1, hi2)) + else { + (frozenConstraint || !isCappable(tp1)) && isSubType(tp1, lo2) || + leftIsSub(tp1, tp2) + } + case _ => + leftIsSub(tp1, tp2) + } + } + compareNamed + + case tp2 @ RefinedType(parent2, name2) => + def compareRefined: Boolean = tp1.widen match { + case tp1 @ RefinedType(parent1, name1) if nameMatches(name1, name2, tp1, tp2) => + // optimized case; all info on tp1.name2 is in refinement tp1.refinedInfo. + isSubType(tp1, parent2) && isSubType(tp1.refinedInfo, tp2.refinedInfo) + case _ => + def hasMatchingMember(name: Name): Boolean = traceIndented(s"hasMatchingMember($name) ${tp1.member(name)}") ( + tp1.member(name).hasAltWith(alt => isSubType(alt.info, tp2.refinedInfo)) + || + { // special case for situations like: + // foo <: C { type T = foo.T } + tp2.refinedInfo match { + case TypeBounds(lo, hi) if lo eq hi => + val ref = tp1 select name + isSubType(ref, lo) && isSubType(hi, ref) + case _ => false + } + } + || + name.isHkParamName && { + val idx = name.hkParamIndex + val tparams = tp1.typeParams + idx < tparams.length && hasMatchingMember(tparams(idx).name) + } + ) + isSubType(tp1, parent2) && ( + name2 == nme.WILDCARD + || hasMatchingMember(name2) + || leftIsSub2(tp1, tp2)) + } + compareRefined + + case param2: PolyParam => + def comparePoly = + param2 == tp1 || { + if (isConstrained(param2)) + isSubTypeWhenFrozen(tp1, bounds(param2).lo) || + addConstraint(param2, tp1.widen, fromBelow = true) + else + (ctx.mode is Mode.TypevarsMissContext) || + isNonBottomSubType(tp1, bounds(param2).lo) || + leftIsSub(tp1, tp2) + } + comparePoly + + case ThisType(cls) if (cls is ModuleClass) => + def compareThis: Boolean = { + tp1 match { + case tp1: TermRef => + if (tp1.symbol.moduleClass == cls) + return tp1.prefix <:< cls.owner.thisType + case _ => + } + leftIsSub(tp1, tp2) + } + compareThis + + case tp2: BoundType => + tp1 == tp2 || leftIsSub(tp1, tp2) + case OrType(tp21, tp22) => + isSubType(tp1, tp21) || isSubType(tp1, tp22) + + case tp2 @ MethodType(_, formals2) => + def compareMethod = tp1 match { + case tp1 @ MethodType(_, formals1) => + tp1.signature == tp2.signature && + (if (Config.newMatch) subsumeParams(formals1, formals2, tp1.isJava, tp2.isJava) + else matchingParams(formals1, formals2, tp1.isJava, tp2.isJava)) && + tp1.isImplicit == tp2.isImplicit && // needed? + isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1)) + case _ => + false + } + compareMethod + + case tp2: PolyType => + def comparePoly = tp1 match { + case tp1: PolyType => + (tp1.signature sameParams tp2.signature) && + matchingTypeParams(tp1, tp2) && + isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1)) + case _ => + false + } + comparePoly + + case tp2 @ ExprType(restpe2) => + def compareExpr = tp1 match { + // We allow ()T to be a subtype of => T. + // We need some subtype relationship between them so that e.g. + // def toString and def toString() don't clash when seen + // as members of the same type. And it seems most logical to take + // ()T <:< => T, since everything one can do with a => T one can + // also do with a ()T by automatic () insertion. + case tp1 @ MethodType(Nil, _) => isSubType(tp1.resultType, restpe2) + case _ => isSubType(tp1.widenExpr, restpe2) + } + compareExpr + + case tp2 @ TypeBounds(lo2, hi2) => + def compareBounds = tp1 match { + case tp1 @ TypeBounds(lo1, hi1) => + val v = tp1.variance + tp2.variance + ((v > 0) || (lo2 isRef NothingClass) || isSubType(lo2, lo1)) && + ((v < 0) || (hi2 isRef AnyClass) || isSubType(hi1, hi2)) + case tp1: ClassInfo => + val tt = tp1.typeRef + isSubType(lo2, tt) && isSubType(tt, hi2) + case _ => + false + } + compareBounds + + case ClassInfo(pre2, cls2, _, _, _) => + def compareClassInfo = tp1 match { + case ClassInfo(pre1, cls1, _, _, _) => + (cls1 eq cls2) && isSubType(pre2, pre1) + case _ => + false + } + compareClassInfo + + case _ => + leftIsSub(tp1, tp2) + } + + def leftIsSub(tp1: Type, tp2: Type): Boolean = tp1 match { + case tp1: TypeRef => + tp1.info match { + case TypeBounds(lo1, hi1) => isSubType(hi1, tp2) + case _ => false + } + case tp1: SingletonType => + isSubType(tp1.underlying.widenExpr, tp2) + case tp1: RefinedType => + isSubType(tp1.parent, tp2) + case _ => + leftIsSub2(tp1, tp2) + } + + def leftIsSub2(tp1: Type, tp2: Type): Boolean = tp1 match { + case param1: PolyParam => + assert(!isConstrained(param1)) + (ctx.mode is Mode.TypevarsMissContext) || isSubType(bounds(param1).hi, tp2) + case AndType(tp11, tp12) => + isSubType(tp11, tp2) || isSubType(tp12, tp2) + case _ => + false + } + + def firstTry(tp1: Type, tp2: Type): Boolean = { tp2 match { case tp2: NamedType => tp1 match { @@ -250,7 +525,7 @@ class TypeComparer(initctx: Context) extends DotClass { if (cls is ModuleClass) tp1 match { case tp1: TermRef => - return tp1.symbol.moduleClass == cls && tp1.prefix <:< cls.owner.thisType // ??? + if (tp1.symbol.moduleClass == cls) return tp1.prefix <:< cls.owner.thisType case _ => } secondTry(tp1, tp2) @@ -263,7 +538,7 @@ class TypeComparer(initctx: Context) extends DotClass { case tp2: BoundType => tp2 == tp1 || secondTry(tp1, tp2) case tp2: TypeVar => - (tp1 eq tp2) || isSubType(tp1, tp2.underlying) + isSubType(tp1, tp2.underlying) case tp2: ProtoType => isMatchedByProto(tp2, tp1) case tp2: WildcardType => @@ -273,6 +548,8 @@ class TypeComparer(initctx: Context) extends DotClass { } case tp2: AnnotatedType => isSubType(tp1, tp2.tpe) // todo: refine? + case AndType(tp21, tp22) => + isSubType(tp1, tp21) && isSubType(tp1, tp22) case ErrorType => true case _ => @@ -285,7 +562,7 @@ class TypeComparer(initctx: Context) extends DotClass { if (cls is ModuleClass) tp2 match { case tp2: TermRef => - return tp2.symbol.moduleClass == cls && cls.owner.thisType <:< tp2.prefix + if (tp2.symbol.moduleClass == cls) return cls.owner.thisType <:< tp2.prefix case _ => } thirdTry(tp1, tp2) @@ -310,6 +587,8 @@ class TypeComparer(initctx: Context) extends DotClass { } case tp1: AnnotatedType => isSubType(tp1.tpe, tp2) + case OrType(tp11, tp12) => + isSubType(tp11, tp2) && isSubType(tp12, tp2) case ErrorType => true case _ => @@ -362,8 +641,6 @@ class TypeComparer(initctx: Context) extends DotClass { || hasMatchingMember(name2) || fourthTry(tp1, tp2)) } - case AndType(tp21, tp22) => - isSubType(tp1, tp21) && isSubType(tp1, tp22) case OrType(tp21, tp22) => isSubType(tp1, tp21) || isSubType(tp1, tp22) || fourthTry(tp1, tp2) case tp2 @ MethodType(_, formals2) => @@ -427,8 +704,8 @@ class TypeComparer(initctx: Context) extends DotClass { isSubType(hi1, tp2) || (tp1.symbol is GADTFlexType) && trySetType(tp1, TypeBounds(lo1, hi1 & tp2)) case _ => - (tp1.symbol eq NothingClass) || - (tp1.symbol eq NullClass) && tp2.dealias.typeSymbol.isNonValueClass + (tp1.symbol eq NothingClass) && tp2.isInstanceOf[ValueType] || + (tp1.symbol eq NullClass) && tp2.dealias.typeSymbol.isNullableClass } case tp1: SingletonType => isSubType(tp1.underlying.widenExpr, tp2) @@ -436,8 +713,6 @@ class TypeComparer(initctx: Context) extends DotClass { isSubType(tp1.parent, tp2) case AndType(tp11, tp12) => isSubType(tp11, tp2) || isSubType(tp12, tp2) - case OrType(tp11, tp12) => - isSubType(tp11, tp2) && isSubType(tp12, tp2) case _ => false } -- cgit v1.2.3