From 72c11c60b14685648b2bf3d6b5a6a6230323f099 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Sat, 14 Aug 2010 08:19:56 +0000 Subject: closes #3691. TODO: clean this up, introduce datatypes to denote kinds, split checkKindBounds into kind inference and subkind checking review by odersky --- src/compiler/scala/tools/nsc/symtab/Types.scala | 117 ++++++++++++++++++++- .../scala/tools/nsc/typechecker/Infer.scala | 115 +++----------------- test/files/neg/t3691.check | 16 +++ test/files/neg/t3691.scala | 11 ++ 4 files changed, 155 insertions(+), 104 deletions(-) create mode 100644 test/files/neg/t3691.check create mode 100644 test/files/neg/t3691.scala diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala index acf4f6d43d..057bf45107 100644 --- a/src/compiler/scala/tools/nsc/symtab/Types.scala +++ b/src/compiler/scala/tools/nsc/symtab/Types.scala @@ -4241,9 +4241,8 @@ A type's typeSymbol should never be inspected directly. // this optimisation holds because inlining cloneSymbols in `val tpsFresh = cloneSymbols(tparams1)` gives: // val tpsFresh = tparams1 map (_.cloneSymbol) // for (tpFresh <- tpsFresh) tpFresh.setInfo(tpFresh.info.substSym(tparams1, tpsFresh)) - } } - + } case (_, _) => false // @assume !tp1.isHigherKinded || !tp2.isHigherKinded // --> thus, cannot be subtypes (Any/Nothing has already been checked) })) @@ -4479,7 +4478,12 @@ A type's typeSymbol should never be inspected directly. val info2 = tp2.memberInfo(sym2).substThis(tp2.typeSymbol, tp1) //System.out.println("specializes "+tp1+"."+sym1+":"+info1+sym1.locationString+" AND "+tp2+"."+sym2+":"+info2)//DEBUG sym2.isTerm && (info1 <:< info2) /*&& (!sym2.isStable || sym1.isStable) */ || - sym2.isAbstractType && info2.bounds.containsType(tp1.memberType(sym1)) || + sym2.isAbstractType && { + val memberTp1 = tp1.memberType(sym1) + // println("kinds conform? "+(memberTp1, tp1, sym2, kindsConform(List(sym2), List(memberTp1), tp2, sym2.owner))) + info2.bounds.containsType(memberTp1) && + kindsConform(List(sym2), List(memberTp1), tp1, sym1.owner) + } || sym2.isAliasType && tp2.memberType(sym2).substThis(tp2.typeSymbol, tp1) =:= tp1.memberType(sym1) //@MAT ok } @@ -5185,6 +5189,113 @@ A type's typeSymbol should never be inspected directly. throw new NoCommonType(tps) } + +// TODO: this desperately needs to be cleaned up +// plan: split into kind inference and subkinding +// every Type has a (cached) Kind + def kindsConform(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): Boolean = checkKindBounds0(tparams, targs, pre, owner, false).isEmpty + + /** Check well-kindedness of type application (assumes arities are already checked) -- @M + * + * This check is also performed when abstract type members become concrete (aka a "type alias") -- then tparams.length==1 + * (checked one type member at a time -- in that case, prefix is the name of the type alias) + * + * Type application is just like value application: it's "contravariant" in the sense that + * the type parameters of the supplied type arguments must conform to the type parameters of + * the required type parameters: + * - their bounds must be less strict + * - variances must match (here, variances are absolute, the variance of a type parameter does not influence the variance of its higher-order parameters) + * - @M TODO: are these conditions correct,sufficient&necessary? + * + * e.g. class Iterable[t, m[+x <: t]] --> the application Iterable[Int, List] is okay, since + * List's type parameter is also covariant and its bounds are weaker than <: Int + */ + def checkKindBounds0(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol, explainErrors: Boolean): List[(Type, Symbol, List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)])] = { + var error = false + + def transform(tp: Type, clazz: Symbol): Type = tp.asSeenFrom(pre, clazz) // instantiate type params that come from outside the abstract type we're currently checking + def transformedBounds(p: Symbol, o: Symbol) = transform(p.info.instantiateTypeParams(tparams, targs).bounds, o) + + /** Check whether sym1's variance conforms to sym2's variance + * + * If sym2 is invariant, sym1's variance is irrelevant. Otherwise they must be equal. + */ + def variancesMatch(sym1: Symbol, sym2: Symbol): Boolean = (sym2.variance==0 || sym1.variance==sym2.variance) + + // check that the type parameters hkargs to a higher-kinded type conform to the expected params hkparams + def checkKindBoundsHK(hkargs: List[Symbol], arg: Symbol, param: Symbol, paramowner: Symbol, underHKParams: List[Symbol], withHKArgs: List[Symbol]): (List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)]) = { + def bindHKParams(tp: Type) = tp.substSym(underHKParams, withHKArgs) + // @M sometimes hkargs != arg.typeParams, the symbol and the type may have very different type parameters + val hkparams = param.typeParams + + if(settings.debug.value) { + println("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner) + println("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner) + println("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs) + } + + if(hkargs.length != hkparams.length) { + if(arg == AnyClass || arg == NothingClass) (Nil, Nil, Nil) // Any and Nothing are kind-overloaded + else {error = true; (List((arg, param)), Nil, Nil)} // shortcut: always set error, whether explainTypesOrNot + } else { + val _arityMismatches = if(explainErrors) new ListBuffer[(Symbol, Symbol)] else null + val _varianceMismatches = if(explainErrors) new ListBuffer[(Symbol, Symbol)] else null + val _stricterBounds = if(explainErrors)new ListBuffer[(Symbol, Symbol)] else null + def varianceMismatch(a: Symbol, p: Symbol) { if(explainErrors) _varianceMismatches += ((a, p)) else error = true} + def stricterBound(a: Symbol, p: Symbol) { if(explainErrors) _stricterBounds += ((a, p)) else error = true } + def arityMismatches(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _arityMismatches ++= as } + def varianceMismatches(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _varianceMismatches ++= as } + def stricterBounds(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _stricterBounds ++= as } + + for ((hkarg, hkparam) <- hkargs zip hkparams) { + if (hkparam.typeParams.isEmpty) { // base-case: kind * + if (!variancesMatch(hkarg, hkparam)) + varianceMismatch(hkarg, hkparam) + + // instantiateTypeParams(tparams, targs) --> higher-order bounds may contain references to type arguments + // substSym(hkparams, hkargs) --> these types are going to be compared as types of kind * + // --> their arguments use different symbols, but are conceptually the same + // (could also replace the types by polytypes, but can't just strip the symbols, as ordering is lost then) + if (!(bindHKParams(transformedBounds(hkparam, paramowner)) <:< transform(hkarg.info.bounds, owner))) + stricterBound(hkarg, hkparam) + + if(settings.debug.value) { + println("checkKindBoundsHK base case: "+ hkparam +" declared bounds: "+ transformedBounds(hkparam, paramowner) +" after instantiating earlier hkparams: "+ bindHKParams(transformedBounds(hkparam, paramowner))) + println("checkKindBoundsHK base case: "+ hkarg +" has bounds: "+ transform(hkarg.info.bounds, owner)) + } + } else { + if(settings.debug.value) println("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg) + val (am, vm, sb) = checkKindBoundsHK(hkarg.typeParams, hkarg, hkparam, paramowner, underHKParams ++ hkparam.typeParams, withHKArgs ++ hkarg.typeParams) + arityMismatches(am) + varianceMismatches(vm) + stricterBounds(sb) + } + if(!explainErrors && error) return (Nil, Nil, Nil) // stop as soon as we encountered an error + } + if(!explainErrors) (Nil, Nil, Nil) + else (_arityMismatches.toList, _varianceMismatches.toList, _stricterBounds.toList) + } + } + + val errors = new ListBuffer[(Type, Symbol, List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)])] + (tparams zip targs).foreach{ case (tparam, targ) if (targ.isHigherKinded || !tparam.typeParams.isEmpty) => + // @M must use the typeParams of the type targ, not the typeParams of the symbol of targ!! + val tparamsHO = targ.typeParams + + val (arityMismatches, varianceMismatches, stricterBounds) = + checkKindBoundsHK(tparamsHO, targ.typeSymbolDirect, tparam, tparam.owner, tparam.typeParams, tparamsHO) // NOTE: *not* targ.typeSymbol, which normalizes + + if(!explainErrors) {if(error) return List((NoType, NoSymbol, Nil, Nil, Nil))} + else if (arityMismatches.nonEmpty || varianceMismatches.nonEmpty || stricterBounds.nonEmpty) { + errors += ((targ, tparam, arityMismatches, varianceMismatches, stricterBounds)) + } + // case (tparam, targ) => println("no check: "+(tparam, targ, tparam.typeParams.isEmpty)) + case _ => + } + + errors.toList + } + // Errors and Diagnostics ----------------------------------------------------- /** A throwable signalling a type error */ diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 081f0053ec..d4979b0589 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -1023,85 +1023,8 @@ trait Infer { } } - /** Check whether sym1's variance conforms to sym2's variance - * - * If sym2 is invariant, sym1's variance is irrelevant. Otherwise they must be equal. - */ - def variancesMatch(sym1: Symbol, sym2: Symbol): Boolean = (sym2.variance==0 || sym1.variance==sym2.variance) - /** Check well-kindedness of type application (assumes arities are already checked) -- @M - * - * This check is also performed when abstract type members become concrete (aka a "type alias") -- then tparams.length==1 - * (checked one type member at a time -- in that case, prefix is the name of the type alias) - * - * Type application is just like value application: it's "contravariant" in the sense that - * the type parameters of the supplied type arguments must conform to the type parameters of - * the required type parameters: - * - their bounds must be less strict - * - variances must match (here, variances are absolute, the variance of a type parameter does not influence the variance of its higher-order parameters) - * - @M TODO: are these conditions correct,sufficient&necessary? - * - * e.g. class Iterable[t, m[+x <: t]] --> the application Iterable[Int, List] is okay, since - * List's type parameter is also covariant and its bounds are weaker than <: Int - */ def checkKindBounds(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): List[String] = { - def transform(tp: Type, clazz: Symbol): Type = tp.asSeenFrom(pre, clazz) // instantiate type params that come from outside the abstract type we're currently checking - def transformedBounds(p: Symbol, o: Symbol) = transform(p.info.instantiateTypeParams(tparams, targs).bounds, o) - - // check that the type parameters hkargs to a higher-kinded type conform to the expected params hkparams - def checkKindBoundsHK(hkargs: List[Symbol], arg: Symbol, param: Symbol, paramowner: Symbol, underHKParams: List[Symbol], withHKArgs: List[Symbol]): (List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)]) = { - def bindHKParams(tp: Type) = tp.substSym(underHKParams, withHKArgs) - // @M sometimes hkargs != arg.typeParams, the symbol and the type may have very different type parameters - val hkparams = param.typeParams - - if(printTypings) { - println("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner) - println("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner) - println("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs) - } - - if(hkargs.length != hkparams.length) { - if(arg == AnyClass || arg == NothingClass) (Nil, Nil, Nil) // Any and Nothing are kind-overloaded - else (List((arg, param)), Nil, Nil) - } else { - val _arityMismatches = new ListBuffer[(Symbol, Symbol)] - val _varianceMismatches = new ListBuffer[(Symbol, Symbol)] - val _stricterBounds = new ListBuffer[(Symbol, Symbol)] - def varianceMismatch(a: Symbol, p: Symbol) { _varianceMismatches += ((a, p)) } - def stricterBound(a: Symbol, p: Symbol) { _stricterBounds += ((a, p)) } - def arityMismatches(as: Iterable[(Symbol, Symbol)]) { _arityMismatches ++= as } - def varianceMismatches(as: Iterable[(Symbol, Symbol)]) { _varianceMismatches ++= as } - def stricterBounds(as: Iterable[(Symbol, Symbol)]) { _stricterBounds ++= as } - - for ((hkarg, hkparam) <- hkargs zip hkparams) { - if (hkparam.typeParams.isEmpty) { // base-case: kind * - if (!variancesMatch(hkarg, hkparam)) - varianceMismatch(hkarg, hkparam) - - // instantiateTypeParams(tparams, targs) --> higher-order bounds may contain references to type arguments - // substSym(hkparams, hkargs) --> these types are going to be compared as types of kind * - // --> their arguments use different symbols, but are conceptually the same - // (could also replace the types by polytypes, but can't just strip the symbols, as ordering is lost then) - if (!(bindHKParams(transformedBounds(hkparam, paramowner)) <:< transform(hkarg.info.bounds, owner))) - stricterBound(hkarg, hkparam) - - if(printTypings) { - println("checkKindBoundsHK base case: "+ hkparam +" declared bounds: "+ transformedBounds(hkparam, paramowner) +" after instantiating earlier hkparams: "+ bindHKParams(transformedBounds(hkparam, paramowner))) - println("checkKindBoundsHK base case: "+ hkarg +" has bounds: "+ transform(hkarg.info.bounds, owner)) - } - } else { - if(printTypings) println("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg) - val (am, vm, sb) = checkKindBoundsHK(hkarg.typeParams, hkarg, hkparam, paramowner, underHKParams ++ hkparam.typeParams, withHKArgs ++ hkarg.typeParams) - arityMismatches(am) - varianceMismatches(vm) - stricterBounds(sb) - } - } - - (_arityMismatches.toList, _varianceMismatches.toList, _stricterBounds.toList) - } - } - // @M TODO this method is duplicated all over the place (varianceString) def varStr(s: Symbol): String = if (s.isCovariant) "covariant" @@ -1117,32 +1040,22 @@ trait Infer { } } - val errors = new ListBuffer[String] - (tparams zip targs).foreach{ case (tparam, targ) if (targ.isHigherKinded || !tparam.typeParams.isEmpty) => - // @M must use the typeParams of the type targ, not the typeParams of the symbol of targ!! - val tparamsHO = targ.typeParams - - val (arityMismatches, varianceMismatches, stricterBounds) = - checkKindBoundsHK(tparamsHO, targ.typeSymbolDirect, tparam, tparam.owner, tparam.typeParams, tparamsHO) // NOTE: *not* targ.typeSymbol, which normalizes - if (!(arityMismatches.isEmpty && varianceMismatches.isEmpty && stricterBounds.isEmpty)){ - errors += (targ+"'s type parameters do not match "+tparam+"'s expected parameters: "+ - (for ((a, p) <- arityMismatches) - yield a+qualify(a,p)+ " has "+reporter.countElementsAsString(a.typeParams.length, "type parameter")+", but "+ - p+qualify(p,a)+" has "+reporter.countAsString(p.typeParams.length)).toList.mkString(", ") + - (for ((a, p) <- varianceMismatches) - yield a+qualify(a,p)+ " is "+varStr(a)+", but "+ - p+qualify(p,a)+" is declared "+varStr(p)).toList.mkString(", ") + - (for ((a, p) <- stricterBounds) - yield a+qualify(a,p)+"'s bounds "+a.info+" are stricter than "+ - p+qualify(p,a)+"'s declared bounds "+p.info).toList.mkString(", ")) - } - // case (tparam, targ) => println("no check: "+(tparam, targ, tparam.typeParams.isEmpty)) - case _ => + val errors = checkKindBounds0(tparams, targs, pre, owner, true) + val errorMessages = new ListBuffer[String] + errors foreach {case (targ, tparam, arityMismatches, varianceMismatches, stricterBounds) => errorMessages += + (targ+"'s type parameters do not match "+tparam+"'s expected parameters: "+ + (for ((a, p) <- arityMismatches) + yield a+qualify(a,p)+ " has "+reporter.countElementsAsString(a.typeParams.length, "type parameter")+", but "+ + p+qualify(p,a)+" has "+reporter.countAsString(p.typeParams.length)).toList.mkString(", ") + + (for ((a, p) <- varianceMismatches) + yield a+qualify(a,p)+ " is "+varStr(a)+", but "+ + p+qualify(p,a)+" is declared "+varStr(p)).toList.mkString(", ") + + (for ((a, p) <- stricterBounds) + yield a+qualify(a,p)+"'s bounds "+a.info+" are stricter than "+ + p+qualify(p,a)+"'s declared bounds "+p.info).toList.mkString(", ")) } - - errors.toList + errorMessages.toList } - /** Substitite free type variables `undetparams' of polymorphic argument * expression `tree', given two prototypes `strictPt', and `lenientPt'. * `strictPt' is the first attempt prototype where type parameters diff --git a/test/files/neg/t3691.check b/test/files/neg/t3691.check new file mode 100644 index 0000000000..1b548cc84d --- /dev/null +++ b/test/files/neg/t3691.check @@ -0,0 +1,16 @@ +t3691.scala:4: error: type mismatch; + found : java.lang.Object with Test.A[String] + required: AnyRef{type A[x]} + val b = (new A[String]{}): { type A[x] } // not ok + ^ +t3691.scala:5: error: type mismatch; + found : java.lang.Object with Test.A[String] + required: AnyRef{type A} + val c = (new A[String]{}): { type A } // not ok + ^ +t3691.scala:7: error: type mismatch; + found : java.lang.Object{type A = String} + required: AnyRef{type A[X]} + val x = (new { type A = String }): { type A[X] } // not ok + ^ +three errors found diff --git a/test/files/neg/t3691.scala b/test/files/neg/t3691.scala new file mode 100644 index 0000000000..69e8bef630 --- /dev/null +++ b/test/files/neg/t3691.scala @@ -0,0 +1,11 @@ +object Test { + trait A[X] { type A[x <: X] = x } + val a = (new A[String]{}): { type A[x <: String] } // ok + val b = (new A[String]{}): { type A[x] } // not ok + val c = (new A[String]{}): { type A } // not ok + + val x = (new { type A = String }): { type A[X] } // not ok +//a: AnyRef{type A[X]} + + identity[x.A[Any]] _ +} \ No newline at end of file -- cgit v1.2.3