diff options
| -rw-r--r-- | src/compiler/scala/reflect/internal/Types.scala | 147 | ||||
| -rw-r--r-- | src/compiler/scala/tools/nsc/Global.scala | 3 | ||||
| -rw-r--r-- | test/files/pos/hkrange.scala | 5 |
3 files changed, 107 insertions, 48 deletions
diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala index 34150069ad..3395787d08 100644 --- a/src/compiler/scala/reflect/internal/Types.scala +++ b/src/compiler/scala/reflect/internal/Types.scala @@ -87,7 +87,7 @@ trait Types extends api.Types { self: SymbolTable => /** Decrement depth unless it is a don't care. */ private final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1 - private final val printLubs = sys.props contains "scala.debug.lub" + 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 @@ -2390,13 +2390,20 @@ A type's typeSymbol should never be inspected directly. new TypeVar(origin, constr, args, params) } - /** A class representing a type variable - * Not used after phase `typer`. - * A higher-kinded type variable has type arguments (a list of Type's) and type parameters (list of Symbols) - * A TypeVar whose list of args is non-empty can only be instantiated by a higher-kinded type that can be applied to these args - * a typevar is much like a typeref, except it has special logic for type equality/subtyping + /** A class representing a type variable: not used after phase `typer`. + * + * A higher-kinded TypeVar has params (Symbols) and typeArgs (Types). + * A TypeVar with nonEmpty typeArgs can only be instantiated by a higher-kinded + * type that can be applied to those args. A TypeVar is much like a TypeRef, + * except it has special logic for equality and subtyping. */ - class TypeVar(val origin: Type, val constr0: TypeConstraint, override val typeArgs: List[Type], override val params: List[Symbol]) extends Type { + class TypeVar( + val origin: Type, + val constr0: TypeConstraint, + override val typeArgs: List[Type], + override val params: List[Symbol] + ) extends Type { + private val numArgs = typeArgs.length // params are needed to keep track of variance (see mapOverArgs in SubstMap) assert(typeArgs.isEmpty || sameLength(typeArgs, params)) // var tid = { tidCount += 1; tidCount } //DEBUG @@ -2409,14 +2416,16 @@ A type's typeSymbol should never be inspected directly. val level = skolemizationLevel /** Two occurrences of a higher-kinded typevar, e.g. `?CC[Int]` and `?CC[String]`, correspond to - * ''two instances'' of `TypeVar` that share the ''same'' `TypeConstraint` - * `constr` for `?CC` only tracks type constructors anyway, so when `?CC[Int] <:< List[Int]` and `?CC[String] <:< Iterable[String]` - * `?CC's` hibounds contains List and Iterable + * ''two instances'' of `TypeVar` that share the ''same'' `TypeConstraint`. + * + * `constr` for `?CC` only tracks type constructors anyway, + * so when `?CC[Int] <:< List[Int]` and `?CC[String] <:< Iterable[String]` + * `?CC's` hibounds contains List and Iterable. */ def applyArgs(newArgs: List[Type]): TypeVar = if (newArgs.isEmpty) this // SubstMap relies on this (though this check is redundant when called from appliedType...) else TypeVar(origin, constr, newArgs, params) // @M TODO: interaction with undoLog?? - // newArgs.length may differ from args.length (could've been empty before) + // newArgs.length may differ from args.length (could've been empty before) // example: when making new typevars, you start out with C[A], then you replace C by ?C, which should yield ?C[A], then A by ?A, ?C[?A] // we need to track a TypeVar's arguments, and map over them (see TypeMap::mapOver) // TypeVars get applied to different arguments over time (in asSeenFrom) @@ -2427,7 +2436,8 @@ A type's typeSymbol should never be inspected directly. // they share the same TypeConstraint instance // <region name="constraint mutators + undoLog"> - // invariant: before mutating constr, save old state in undoLog (undoLog is used to reset constraints to avoid piling up unrelated ones) + // invariant: before mutating constr, save old state in undoLog + // (undoLog is used to reset constraints to avoid piling up unrelated ones) def setInst(tp: Type) { // assert(!(tp containsTp this), this) undoLog record this @@ -2435,7 +2445,7 @@ A type's typeSymbol should never be inspected directly. } def addLoBound(tp: Type, isNumericBound: Boolean = false) { - assert(tp != this) // implies there is a cycle somewhere (?) + assert(tp != this, tp) // implies there is a cycle somewhere (?) //println("addLoBound: "+(safeToString, debugString(tp))) //DEBUG undoLog record this constr.addLoBound(tp, isNumericBound) @@ -2463,22 +2473,21 @@ A type's typeSymbol should never be inspected directly. */ def registerBound(tp: Type, isLowerBound: Boolean, isNumericBound: Boolean = false): Boolean = { // println("regBound: "+(safeToString, debugString(tp), isLowerBound)) //@MDEBUG - if (isLowerBound) assert(tp != this) - - def checkSubtypeLower(tp1: Type, tp2: Type) = - if (isNumericBound) tp1 weak_<:< tp2 - else tp1 <:< tp2 + if (isLowerBound) + assert(tp != this) - // swaps the arguments if it's an upper bound - def checkSubtype(tp1: Type, tp2: Type) = - if (isLowerBound) checkSubtypeLower(tp1, tp2) - else checkSubtypeLower(tp2, tp1) - - def addBound(tp: Type) = { + // side effect: adds the type to upper or lower bounds + def addBound(tp: Type) { if (isLowerBound) addLoBound(tp, isNumericBound) else addHiBound(tp, isNumericBound) - // println("addedBound: "+(this, tp)) // @MDEBUG - true + } + // swaps the arguments if it's an upper bound + def checkSubtype(tp1: Type, tp2: Type) = { + val lhs = if (isLowerBound) tp1 else tp2 + val rhs = if (isLowerBound) tp2 else tp1 + + if (isNumericBound) lhs weak_<:< rhs + else lhs <:< rhs } /** Simple case: type arguments can be ignored, because either this typevar has @@ -2494,8 +2503,12 @@ A type's typeSymbol should never be inspected directly. * ?TC[?T] <: Any * }}} */ - def unifySimple = (params.isEmpty || tp.typeSymbol == NothingClass || tp.typeSymbol == AnyClass) && - addBound(tp) + def unifySimple = ( + (params.isEmpty || tp.typeSymbol == NothingClass || tp.typeSymbol == AnyClass) && { + addBound(tp) + true + } + ) /** Full case: involving a check of the form * {{{ @@ -2504,27 +2517,67 @@ A type's typeSymbol should never be inspected directly. * Checks subtyping of higher-order type vars, and uses variances as defined in the * type parameter we're trying to infer (the result will be sanity-checked later). */ - def unifyFull(tp: Type) = sameLength(typeArgs, tp.typeArgs) && { // this is a higher-kinded type var with same arity as tp - // side effect: adds the type constructor itself as a bound - addBound(tp.typeConstructor) - if (isLowerBound) isSubArgs(tp.typeArgs, typeArgs, params) - else isSubArgs(typeArgs, tp.typeArgs, params) + def unifyFull(tpe: Type) = { + // Since the alias/widen variations are often no-ops, this + // keenly collects them in a Set to avoid redundant tests. + val tpes = ( + if (isLowerBound) Set(tpe, tpe.widen, tpe.dealias, tpe.widen.dealias) + else Set(tpe) + ) + tpes exists { tp => + val lhs = if (isLowerBound) tp.typeArgs else typeArgs + val rhs = if (isLowerBound) typeArgs else tp.typeArgs + + sameLength(lhs, rhs) && { + // this is a higher-kinded type var with same arity as tp. + // side effect: adds the type constructor itself as a bound + addBound(tp.typeConstructor) + isSubArgs(lhs, rhs, params) + } + } } - /** TODO: need positive/negative test cases demonstrating this is correct. */ - def unifyParents = - if (isLowerBound) tp.parents exists unifyFull - else tp.parents forall unifyFull - - // TODO: fancier unification, maybe rewrite constraint as follows? - // val sym = constr.hiBounds map {_.typeSymbol} find { _.typeParams.length == typeArgs.length} - // this <: tp.baseType(sym) - if (suspended) checkSubtype(tp, origin) - else if (constr.instValid) checkSubtype(tp, constr.inst) // type var is already set - else isRelatable(tp) && { // gradually let go of some type precision in hopes of finding a type that has the same shape as the type variable - // okay, this just screams "CLEAN ME UP" -- I think we could use tp.widen instead of tp straight from the get-go in registerBound, since we don't infer singleton types anyway (but maybe that'll change?) - unifySimple || unifyFull(tp) || unifyFull(tp.dealias) || unifyFull(tp.widen) || unifyFull(tp.widen.dealias) || unifyParents - } + // There's a <: test taking place right now, where tp is a concrete type and this is a typevar + // attempting to satisfy that test. Either the test will be unsatisfiable, in which case + // registerBound will return false; or the upper or lower bounds of this type var will be + // supplemented with the type being tested against. + // + // Eventually the types which have accumulated in the upper and lower bounds will be lubbed + // (resp. glbbed) to instantiate the typevar. + // + // The only types which are eligible for unification are those with the same number of + // typeArgs as this typevar, or Any/Nothing, which are kind-polymorphic. For the upper bound, + // any parent or base type of `tp` may be tested here (leading to a corresponding relaxation + // in the upper bound.) The universe of possible glbs, being somewhat more infinite, is not + // addressed here: all lower bounds are retained and their intersection calculated when the + // bounds are solved. + // + // In a side-effect free universe, checking tp and tp.parents beofre checking tp.baseTypeSeq + // would be pointless. In this case, each check we perform causes us to lose specificity: in + // the end the best we'll do is the least specific type we tested against, since the typevar + // does not see these checks as "probes" but as requirements to fulfill. + // + // So the strategy used here is to test first the type, then the direct parents, and finally + // to fall back on the individual base types. This warrants eventual re-examination. + + if (suspended) // constraint accumulation is disabled + checkSubtype(tp, origin) + else if (constr.instValid) // type var is already set + checkSubtype(tp, constr.inst) + else + // isRelatable checks for type skolems which cannot be understood at this level + isRelatable(tp) && ( + unifySimple || unifyFull(tp) || ( + // only look harder if our gaze is oriented toward Any + isLowerBound && ( + (tp.parents exists unifyFull) || ( + // @PP: Is it going to be faster to filter out the parents we just checked? + // That's what's done here but I'm not sure it matters. + tp.baseTypeSeq.toList.tail filterNot (tp.parents contains _) exists unifyFull + ) + ) + ) + ) } def registerTypeEquality(tp: Type, typeVarLHS: Boolean): Boolean = { diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index e2c53b9676..5847563a63 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -281,9 +281,10 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb def profileMem = settings.YprofileMem.value // shortish-term property based options - def timings = sys.props contains "scala.timings" + def timings = (sys.props contains "scala.timings") def inferDebug = (sys.props contains "scalac.debug.infer") || settings.Yinferdebug.value def typerDebug = (sys.props contains "scalac.debug.typer") || settings.Ytyperdebug.value + def lubDebug = (sys.props contains "scalac.debug.lub") } // True if -Xscript has been set, indicating a script run. diff --git a/test/files/pos/hkrange.scala b/test/files/pos/hkrange.scala new file mode 100644 index 0000000000..a6803230ed --- /dev/null +++ b/test/files/pos/hkrange.scala @@ -0,0 +1,5 @@ +class A { + def f[CC[X] <: Traversable[X]](x: CC[Int]) = () + + f(1 to 5) +} |