diff options
Diffstat (limited to 'src')
17 files changed, 700 insertions, 470 deletions
diff --git a/src/compiler/scala/reflect/internal/Kinds.scala b/src/compiler/scala/reflect/internal/Kinds.scala new file mode 100644 index 0000000000..15fcb5f94d --- /dev/null +++ b/src/compiler/scala/reflect/internal/Kinds.scala @@ -0,0 +1,223 @@ +/* NSC -- new scala compiler + * Copyright 2005-2011 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.reflect +package internal + +import scala.collection.{ mutable, immutable } +import scala.tools.util.StringOps.{ countAsString, countElementsAsString } + +trait Kinds { + self: SymbolTable => + + import definitions._ + + private type SymPair = ((Symbol, Symbol)) // ((Argument, Parameter)) + + case class KindErrors( + arity: List[SymPair] = Nil, + variance: List[SymPair] = Nil, + strictness: List[SymPair] = Nil + ) { + def isEmpty = arity.isEmpty && variance.isEmpty && strictness.isEmpty + + def arityError(syms: SymPair) = copy(arity = arity :+ syms) + def varianceError(syms: SymPair) = copy(variance = variance :+ syms) + def strictnessError(syms: SymPair) = copy(strictness = strictness :+ syms) + + def ++(errs: KindErrors) = KindErrors( + arity ++ errs.arity, + variance ++ errs.variance, + strictness ++ errs.strictness + ) + // @M TODO this method is duplicated all over the place (varianceString) + private def varStr(s: Symbol): String = + if (s.isCovariant) "covariant" + else if (s.isContravariant) "contravariant" + else "invariant"; + + private def qualify(a0: Symbol, b0: Symbol): String = if (a0.toString != b0.toString) "" else { + if((a0 eq b0) || (a0.owner eq b0.owner)) "" + else { + var a = a0; var b = b0 + while (a.owner.name == b.owner.name) { a = a.owner; b = b.owner} + if (a.locationString ne "") " (" + a.locationString.trim + ")" else "" + } + } + private def kindMessage(a: Symbol, p: Symbol)(f: (String, String) => String): String = + f(a+qualify(a,p), p+qualify(p,a)) + + private def strictnessMessage(a: Symbol, p: Symbol) = + kindMessage(a, p)("%s's bounds %s are stricter than %s's declared bounds %s".format( + _, a.info, _, p.info)) + + private def varianceMessage(a: Symbol, p: Symbol) = + kindMessage(a, p)("%s is %s, but %s is declared %s".format(_, varStr(a), _, varStr(p))) + + private def arityMessage(a: Symbol, p: Symbol) = + kindMessage(a, p)("%s has %s, but %s has %s".format( + _, countElementsAsString(a.typeParams.length, "type parameter"), + _, countAsString(p.typeParams.length)) + ) + + def errorMessage(targ: Type, tparam: Symbol): String = ( + (targ+"'s type parameters do not match "+tparam+"'s expected parameters: ") + + (arity map { case (a, p) => arityMessage(a, p) } mkString ", ") + + (variance map { case (a, p) => varianceMessage(a, p) } mkString ", ") + + (strictness map { case (a, p) => strictnessMessage(a, p) } mkString ", ") + ) + } + val NoKindErrors = KindErrors(Nil, Nil, Nil) + + // 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 whether `sym1`'s variance conforms to `sym2`'s variance. + * + * If `sym2` is invariant, `sym1`'s variance is irrelevant. Otherwise they must be equal. + */ + private def variancesMatch(sym1: Symbol, sym2: Symbol) = ( + 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 checkKindBounds0( + tparams: List[Symbol], + targs: List[Type], + pre: Type, + owner: Symbol, + explainErrors: Boolean + ): List[(Type, Symbol, KindErrors)] = { + + // instantiate type params that come from outside the abstract type we're currently checking + def transform(tp: Type, clazz: Symbol): Type = + tp.asSeenFrom(pre, clazz) + 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] + ): KindErrors = { + + var kindErrors: KindErrors = NoKindErrors + 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 + def kindCheck(cond: Boolean, f: KindErrors => KindErrors) { + if (!cond) + kindErrors = f(kindErrors) + } + + if (settings.debug.value) { + log("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner) + log("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner) + log("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs) + } + + if (!sameLength(hkargs, hkparams)) { + // Any and Nothing are kind-overloaded + if (arg == AnyClass || arg == NothingClass) NoKindErrors + // shortcut: always set error, whether explainTypesOrNot + else return kindErrors.arityError(arg -> param) + } + else foreach2(hkargs, hkparams) { (hkarg, hkparam) => + if (hkparam.typeParams.isEmpty && hkarg.typeParams.isEmpty) { // base-case: kind * + kindCheck(variancesMatch(hkarg, hkparam), _ varianceError (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. + val declaredBounds = transformedBounds(hkparam, paramowner) + val declaredBoundsInst = bindHKParams(declaredBounds) + val argumentBounds = transform(hkarg.info.bounds, owner) + + kindCheck(declaredBoundsInst <:< argumentBounds, _ strictnessError (hkarg -> hkparam)) + + debuglog( + "checkKindBoundsHK base case: " + hkparam + + " declared bounds: " + declaredBounds + + " after instantiating earlier hkparams: " + declaredBoundsInst + "\n" + + "checkKindBoundsHK base case: "+ hkarg + + " has bounds: " + argumentBounds + ) + } + else { + debuglog("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg) + kindErrors ++= checkKindBoundsHK( + hkarg.typeParams, + hkarg, + hkparam, + paramowner, + underHKParams ++ hkparam.typeParams, + withHKArgs ++ hkarg.typeParams + ) + } + if (!explainErrors && !kindErrors.isEmpty) + return kindErrors + } + if (explainErrors) kindErrors + else NoKindErrors + } + + if (settings.debug.value && (tparams.nonEmpty || targs.nonEmpty)) log( + "checkKindBounds0(" + tparams + ", " + targs + ", " + pre + ", " + + owner + ", " + explainErrors + ")" + ) + + flatMap2(tparams, targs) { (tparam, targ) => + // Prevent WildcardType from causing kind errors, as typevars may be higher-order + if (targ == WildcardType) Nil else { + // force symbol load for #4205 + targ.typeSymbolDirect.info + // @M must use the typeParams of the *type* targ, not of the *symbol* of targ!! + val tparamsHO = targ.typeParams + if (targ.isHigherKinded || tparam.typeParams.nonEmpty) { + // NOTE: *not* targ.typeSymbol, which normalizes + val kindErrors = checkKindBoundsHK( + tparamsHO, targ.typeSymbolDirect, tparam, + tparam.owner, tparam.typeParams, tparamsHO + ) + if (kindErrors.isEmpty) Nil else { + if (explainErrors) List((targ, tparam, kindErrors)) + // Return as soon as an error is seen if there's nothing to explain. + else return List((NoType, NoSymbol, NoKindErrors)) + } + } + else Nil + } + } + } +}
\ No newline at end of file diff --git a/src/compiler/scala/reflect/internal/SymbolTable.scala b/src/compiler/scala/reflect/internal/SymbolTable.scala index 29ac5fe539..5be69e06ad 100644 --- a/src/compiler/scala/reflect/internal/SymbolTable.scala +++ b/src/compiler/scala/reflect/internal/SymbolTable.scala @@ -10,9 +10,11 @@ import scala.collection.{ mutable, immutable } import util._ abstract class SymbolTable extends api.Universe + with Collections with Names with Symbols with Types + with Kinds with Scopes with Definitions with Constants diff --git a/src/compiler/scala/reflect/internal/TreeInfo.scala b/src/compiler/scala/reflect/internal/TreeInfo.scala index 1dc93a7add..14bf36fb47 100644 --- a/src/compiler/scala/reflect/internal/TreeInfo.scala +++ b/src/compiler/scala/reflect/internal/TreeInfo.scala @@ -107,7 +107,15 @@ abstract class TreeInfo { @deprecated("Use isExprSafeToInline instead", "2.10.0") def isPureExpr(tree: Tree) = isExprSafeToInline(tree) - def zipMethodParamsAndArgs(params: List[Symbol], args: List[Tree]): List[(Symbol, Tree)] = { + def zipMethodParamsAndArgs(params: List[Symbol], args: List[Tree]): List[(Symbol, Tree)] = + mapMethodParamsAndArgs(params, args)((param, arg) => ((param, arg))) + + def mapMethodParamsAndArgs[R](params: List[Symbol], args: List[Tree])(f: (Symbol, Tree) => R): List[R] = { + val b = List.newBuilder[R] + foreachMethodParamAndArg(params, args)((param, arg) => b += f(param, arg)) + b.result + } + def foreachMethodParamAndArg(params: List[Symbol], args: List[Tree])(f: (Symbol, Tree) => Unit): Boolean = { val plen = params.length val alen = args.length def fail() = { @@ -116,27 +124,29 @@ abstract class TreeInfo { " params = " + params + "\n" + " args = " + args + "\n" ) - params zip args + false } - if (plen == alen) params zip args - else if (params.isEmpty) fail + if (plen == alen) foreach2(params, args)(f) + else if (params.isEmpty) return fail else if (isVarArgsList(params)) { val plenInit = plen - 1 if (alen == plenInit) { if (alen == 0) Nil // avoid calling mismatched zip - else params.init zip args + else foreach2(params.init, args)(f) } - else if (alen < plenInit) fail + else if (alen < plenInit) return fail else { - val front = params.init zip (args take plenInit) - val back = args drop plenInit map (a => (params.last, a)) - front ++ back + foreach2(params.init, args take plenInit)(f) + val remainingArgs = args drop plenInit + foreach2(List.fill(remainingArgs.size)(params.last), remainingArgs)(f) } } - else fail - } + else return fail + true + } + /** * Selects the correct parameter list when there are nested applications. * Given Apply(fn, args), args might correspond to any of fn.symbol's parameter @@ -144,22 +154,28 @@ abstract class TreeInfo { * applies: for instance Apply(fn @ Apply(Apply(_, _), _), args) implies args * correspond to the third parameter list. * + * The argument fn is the function part of the apply node being considered. + * * Also accounts for varargs. */ + private def applyMethodParameters(fn: Tree): List[Symbol] = { + val depth = applyDepth(fn) + // There could be applies which go beyond the parameter list(s), + // being applied to the result of the method call. + // !!! Note that this still doesn't seem correct, although it should + // be closer than what it replaced. + if (depth < fn.symbol.paramss.size) fn.symbol.paramss(depth) + else if (fn.symbol.paramss.isEmpty) Nil + else fn.symbol.paramss.last + } + def zipMethodParamsAndArgs(t: Tree): List[(Symbol, Tree)] = t match { - case Apply(fn, args) => - val depth = applyDepth(fn) - // There could be applies which go beyond the parameter list(s), - // being applied to the result of the method call. - // !!! Note that this still doesn't seem correct, although it should - // be closer than what it replaced. - val params = ( - if (depth < fn.symbol.paramss.size) fn.symbol.paramss(depth) - else if (fn.symbol.paramss.isEmpty) Nil - else fn.symbol.paramss.last - ) - zipMethodParamsAndArgs(params, args) - case _ => Nil + case Apply(fn, args) => zipMethodParamsAndArgs(applyMethodParameters(fn), args) + case _ => Nil + } + def foreachMethodParamAndArg(t: Tree)(f: (Symbol, Tree) => Unit): Unit = t match { + case Apply(fn, args) => foreachMethodParamAndArg(applyMethodParameters(fn), args)(f) + case _ => } /** Is symbol potentially a getter of a variable? diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala index d7caebbb0a..690f9b7204 100644 --- a/src/compiler/scala/reflect/internal/Types.scala +++ b/src/compiler/scala/reflect/internal/Types.scala @@ -578,7 +578,7 @@ trait Types extends api.Types { self: SymbolTable => * T.asSeenFrom(ThisType(C), D) (where D is owner of m) * = Int */ - def asSeenFrom(pre: Type, clazz: Symbol): Type = + def asSeenFrom(pre: Type, clazz: Symbol): Type = { if (isTrivial || phase.erasedTypes && pre.typeSymbol != ArrayClass) this else { // scala.tools.nsc.util.trace.when(pre.isInstanceOf[ExistentialType])("X "+this+".asSeenfrom("+pre+","+clazz+" = ") { @@ -594,6 +594,7 @@ trait Types extends api.Types { self: SymbolTable => stopTimer(asSeenFromNanos, start) result } + } /** The info of `sym`, seen as a member of this type. * @@ -1623,29 +1624,40 @@ trait Types extends api.Types { self: SymbolTable => // (this can happen only for erroneous programs). } + private object enterRefs extends TypeMap { + private var tparam: Symbol = _ + + def apply(tp: Type): Type = { + tp match { + case TypeRef(_, sym, args) if args.nonEmpty => + if (settings.debug.value && !sameLength(sym.info.typeParams, args)) + debugwarn("Mismatched zip in computeRefs(): " + sym.info.typeParams + ", " + args) + + foreach2(sym.info.typeParams, args) { (tparam1, arg) => + if (arg contains tparam) { + addRef(NonExpansive, tparam, tparam1) + if (arg.typeSymbol != tparam) + addRef(Expansive, tparam, tparam1) + } + } + case _ => + } + mapOver(tp) + } + def enter(tparam0: Symbol, parent: Type) { + this.tparam = tparam0 + this(parent) + } + } + /** Compute initial (one-step) references and set state to `Initializing`. */ private def computeRefs() { refs = Array(Map(), Map()) - for (tparam <- typeSymbol.typeParams) { - val enterRefs = new TypeMap { - def apply(tp: Type): Type = { - tp match { - case TypeRef(_, sym, args) if args.nonEmpty => - if (settings.debug.value && !sameLength(sym.info.typeParams, args)) - debugwarn("Mismatched zip in computeRefs(): " + sym.info.typeParams + ", " + args) - - for ((tparam1, arg) <- sym.info.typeParams zip args; if arg contains tparam) { - addRef(NonExpansive, tparam, tparam1) - if (arg.typeSymbol != tparam) - addRef(Expansive, tparam, tparam1) - } - case _ => - } - mapOver(tp) - } + typeSymbol.typeParams foreach { tparam => + parents foreach { p => + enterRefs.enter(tparam, p) } - for (p <- parents) enterRefs(p) } state = Initializing } @@ -3592,9 +3604,9 @@ A type's typeSymbol should never be inspected directly. // val containsContravariantExistentialCollector = new ContainsVariantExistentialCollector(-1) def typeParamsToExistentials(clazz: Symbol, tparams: List[Symbol]): List[Symbol] = { - val eparams = for ((tparam, i) <- tparams.zipWithIndex) yield { - clazz.newExistential(clazz.pos, newTypeName("?"+i)).setInfo(tparam.info.bounds) - } + val eparams = mapWithIndex(tparams)((tparam, i) => + clazz.newExistential(clazz.pos, newTypeName("?"+i)) setInfo tparam.info.bounds) + eparams map (_ substInfo (tparams, eparams)) } @@ -4425,8 +4437,7 @@ A type's typeSymbol should never be inspected directly. case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) => assert(sym1 == sym2) pre1 =:= pre2 && - ((args1, args2, sym1.typeParams).zipped forall { - (arg1, arg2, tparam) => + forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) => //if (tparam.variance == 0 && !(arg1 =:= arg2)) Console.println("inconsistent: "+arg1+"!="+arg2)//DEBUG if (tparam.variance == 0) arg1 =:= arg2 else if (arg1.isInstanceOf[TypeVar]) @@ -4436,7 +4447,7 @@ A type's typeSymbol should never be inspected directly. // also: think what happens if there are embedded typevars? if (tparam.variance < 0) arg1 <:< arg2 else arg2 <:< arg1 else true - }) + } case (et: ExistentialType, _) => et.withTypeVars(isConsistent(_, tp2)) case (_, et: ExistentialType) => @@ -4959,19 +4970,11 @@ A type's typeSymbol should never be inspected directly. // --> thus, cannot be subtypes (Any/Nothing has already been checked) })) - /** True if all three arguments have the same number of elements and - * the function is true for all the triples. - */ - @tailrec final def corresponds3[A, B, C](xs1: List[A], xs2: List[B], xs3: List[C], f: (A, B, C) => Boolean): Boolean = { - if (xs1.isEmpty) xs2.isEmpty && xs3.isEmpty - else !xs2.isEmpty && !xs3.isEmpty && f(xs1.head, xs2.head, xs3.head) && corresponds3(xs1.tail, xs2.tail, xs3.tail, f) - } - def isSubArg(t1: Type, t2: Type, variance: Int) = (variance > 0 || t2 <:< t1) && (variance < 0 || t1 <:< t2) def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol]): Boolean = - corresponds3(tps1, tps2, tparams map (_.variance), isSubArg) + corresponds3(tps1, tps2, tparams map (_.variance))(isSubArg) def differentOrNone(tp1: Type, tp2: Type) = if (tp1 eq tp2) NoType else tp1 @@ -5343,7 +5346,6 @@ A type's typeSymbol should never be inspected directly. def solve(tvars: List[TypeVar], tparams: List[Symbol], variances: List[Int], upper: Boolean, depth: Int): Boolean = { - val config = tvars zip (tparams zip variances) def solveOne(tvar: TypeVar, tparam: Symbol, variance: Int) { if (tvar.constr.inst == NoType) { @@ -5352,15 +5354,17 @@ A type's typeSymbol should never be inspected directly. val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo //Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound)) var cyclic = bound contains tparam - for ((tvar2, (tparam2, variance2)) <- config) { - if (tparam2 != tparam && - ((bound contains tparam2) || - up && (tparam2.info.bounds.lo =:= tparam.tpe) || - !up && (tparam2.info.bounds.hi =:= tparam.tpe))) { + foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => { + val ok = (tparam2 != tparam) && ( + (bound contains tparam2) + || up && (tparam2.info.bounds.lo =:= tparam.tpe) + || !up && (tparam2.info.bounds.hi =:= tparam.tpe) + ) + if (ok) { if (tvar2.constr.inst eq null) cyclic = true solveOne(tvar2, tparam2, variance2) } - } + }) if (!cyclic) { if (up) { if (bound.typeSymbol != AnyClass) @@ -5399,9 +5403,7 @@ A type's typeSymbol should never be inspected directly. } // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info))) - for ((tvar, (tparam, variance)) <- config) - solveOne(tvar, tparam, variance) - + foreach3(tvars, tparams, variances)(solveOne) tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst)) } @@ -5684,8 +5686,8 @@ A type's typeSymbol should never be inspected directly. case List() => NothingClass.tpe case List(t) => t case ts @ PolyType(tparams, _) :: _ => - val tparams1 = (tparams, matchingBounds(ts, tparams).transpose).zipped map - ((tparam, bounds) => tparam.cloneSymbol.setInfo(glb(bounds, depth))) + val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => + tparam.cloneSymbol.setInfo(glb(bounds, depth))) PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1))) case ts @ MethodType(params, _) :: rest => MethodType(params, lub0(matchingRestypes(ts, params map (_.tpe)))) @@ -5724,7 +5726,7 @@ A type's typeSymbol should never be inspected directly. if (syms contains NoSymbol) NoSymbol else { val symtypes = - (narrowts, syms).zipped map ((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType)) + map2(narrowts, syms)((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType)) if (proto.isTerm) // possible problem: owner of info is still the old one, instead of new refinement class proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(lub(symtypes, decr(depth))) else if (symtypes.tail forall (symtypes.head =:=)) @@ -5829,8 +5831,8 @@ A type's typeSymbol should never be inspected directly. case List() => AnyClass.tpe case List(t) => t case ts @ PolyType(tparams, _) :: _ => - val tparams1 = (tparams, matchingBounds(ts, tparams).transpose).zipped map - ((tparam, bounds) => tparam.cloneSymbol.setInfo(lub(bounds, depth))) + val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) => + tparam.cloneSymbol.setInfo(lub(bounds, depth))) PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth)) case ts @ MethodType(params, _) :: rest => MethodType(params, glbNorm(matchingRestypes(ts, params map (_.tpe)), depth)) @@ -5961,38 +5963,39 @@ A type's typeSymbol should never be inspected directly. else if (args exists (arg => isValueClass(arg.typeSymbol))) Some(ObjectClass.tpe) else Some(typeRef(pre, sym, List(lub(args)))) } - } else { - val args = (sym.typeParams, argss.transpose).zipped map { (tparam, as) => - if (depth == 0) { - if (tparam.variance == variance) { - // Take the intersection of the upper bounds of the type parameters - // rather than falling all the way back to "Any", otherwise we end up not - // conforming to bounds. - val bounds0 = sym.typeParams map (_.info.bounds.hi) filterNot (_.typeSymbol == AnyClass) - if (bounds0.isEmpty) AnyClass.tpe - else intersectionType(bounds0) - } - else if (tparam.variance == -variance) NothingClass.tpe - else NoType + } + else { + val args = map2(sym.typeParams, argss.transpose) { (tparam, as) => + if (depth == 0) { + if (tparam.variance == variance) { + // Take the intersection of the upper bounds of the type parameters + // rather than falling all the way back to "Any", otherwise we end up not + // conforming to bounds. + val bounds0 = sym.typeParams map (_.info.bounds.hi) filterNot (_.typeSymbol == AnyClass) + if (bounds0.isEmpty) AnyClass.tpe + else intersectionType(bounds0) } + else if (tparam.variance == -variance) NothingClass.tpe + else NoType + } + else { + if (tparam.variance == variance) lub(as, decr(depth)) + else if (tparam.variance == -variance) glb(as, decr(depth)) else { - if (tparam.variance == variance) lub(as, decr(depth)) - else if (tparam.variance == -variance) glb(as, decr(depth)) - else { - val l = lub(as, decr(depth)) - val g = glb(as, decr(depth)) - if (l <:< g) l - else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we - // just err on the conservative side, i.e. with a bound that is too high. - // if(!(tparam.info.bounds contains tparam)){ //@M can't deal with f-bounds, see #2251 - - val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l) - capturedParams += qvar - qvar.tpe - } + val l = lub(as, decr(depth)) + val g = glb(as, decr(depth)) + if (l <:< g) l + else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we + // just err on the conservative side, i.e. with a bound that is too high. + // if(!(tparam.info.bounds contains tparam)) //@M can't deal with f-bounds, see #2251 + + val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l) + capturedParams += qvar + qvar.tpe } } } + } if (args contains NoType) None else Some(existentialAbstraction(capturedParams.toList, typeRef(pre, sym, args))) } @@ -6077,148 +6080,6 @@ 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 <arg>hkargs</arg> to a higher-kinded type conform to the expected params <arg>hkparams</arg> - 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) { - log("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner) - log("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner) - log("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs) - } - - if (!sameLength(hkargs, hkparams)) { - 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 && hkarg.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) - val declaredBounds = transformedBounds(hkparam, paramowner) - val declaredBoundsInst = bindHKParams(declaredBounds) - val argumentBounds = transform(hkarg.info.bounds, owner) - if (!(declaredBoundsInst <:< argumentBounds)) - stricterBound(hkarg, hkparam) - - debuglog( - "checkKindBoundsHK base case: " + hkparam + - " declared bounds: " + declaredBounds + - " after instantiating earlier hkparams: " + declaredBoundsInst + "\n" + - "checkKindBoundsHK base case: "+ hkarg + - " has bounds: " + argumentBounds - ) - } - else { - debuglog("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)])] - if (settings.debug.value &&(tparams.nonEmpty || targs.nonEmpty)) - log("checkKindBounds0(" + tparams + ", " + targs + ", " + pre + ", " + owner + ", " + explainErrors + ")") - - for { - (tparam, targ) <- tparams zip targs - // Prevent WildcardType from causing kind errors, as typevars may be higher-order - if (targ != WildcardType) && (targ.isHigherKinded || tparam.typeParams.nonEmpty) - } { - // @M must use the typeParams of the *type* targ, not of the *symbol* of targ!! - targ.typeSymbolDirect.info // force symbol load for #4205 - val tparamsHO = targ.typeParams - - val (arityMismatches, varianceMismatches, stricterBounds) = ( - // NOTE: *not* targ.typeSymbol, which normalizes - checkKindBoundsHK(tparamsHO, targ.typeSymbolDirect, tparam, tparam.owner, tparam.typeParams, tparamsHO) - ) - if (explainErrors) { - if (arityMismatches.nonEmpty || varianceMismatches.nonEmpty || stricterBounds.nonEmpty) { - errors += ((targ, tparam, arityMismatches, varianceMismatches, stricterBounds)) - } - } - else if (error) - return List((NoType, NoSymbol, Nil, Nil, Nil)) - } - - errors.toList - } - // Errors and Diagnostics ----------------------------------------------------- /** A throwable signalling a type error */ diff --git a/src/compiler/scala/reflect/internal/util/Collections.scala b/src/compiler/scala/reflect/internal/util/Collections.scala new file mode 100644 index 0000000000..28a17c7821 --- /dev/null +++ b/src/compiler/scala/reflect/internal/util/Collections.scala @@ -0,0 +1,138 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2011 LAMP/EPFL + * @author Paul Phillips + */ + +package scala.reflect.internal.util + +import scala.collection.{ mutable, immutable } +import scala.annotation.tailrec +import mutable.ListBuffer + +/** Profiler driven changes. + */ +trait Collections { + /** True if all three arguments have the same number of elements and + * the function is true for all the triples. + */ + @tailrec final def corresponds3[A, B, C](xs1: List[A], xs2: List[B], xs3: List[C]) + (f: (A, B, C) => Boolean): Boolean = ( + if (xs1.isEmpty) xs2.isEmpty && xs3.isEmpty + else !xs2.isEmpty && !xs3.isEmpty && f(xs1.head, xs2.head, xs3.head) && corresponds3(xs1.tail, xs2.tail, xs3.tail)(f) + ) + + final def map2[A, B, C](xs1: List[A], xs2: List[B])(f: (A, B) => C): List[C] = { + val lb = new ListBuffer[C] + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + lb += f(ys1.head, ys2.head) + ys1 = ys1.tail + ys2 = ys2.tail + } + lb.toList + } + final def map3[A, B, C, D](xs1: List[A], xs2: List[B], xs3: List[C])(f: (A, B, C) => D): List[D] = { + if (xs1.isEmpty || xs2.isEmpty || xs3.isEmpty) Nil + else f(xs1.head, xs2.head, xs3.head) :: map3(xs1.tail, xs2.tail, xs3.tail)(f) + } + final def flatMap2[A, B, C](xs1: List[A], xs2: List[B])(f: (A, B) => List[C]): List[C] = { + val lb = new ListBuffer[C] + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + lb ++= f(ys1.head, ys2.head) + ys1 = ys1.tail + ys2 = ys2.tail + } + lb.toList + } + + final def mapWithIndex[A, B](xs: List[A])(f: (A, Int) => B): List[B] = { + val lb = new ListBuffer[B] + var index = 0 + var ys = xs + while (!ys.isEmpty) { + lb += f(ys.head, index) + ys = ys.tail + index += 1 + } + lb.toList + } + final def collectMap2[A, B, C](xs1: List[A], xs2: List[B])(p: (A, B) => Boolean): Map[A, B] = { + if (xs1.isEmpty || xs2.isEmpty) + return Map() + + val buf = immutable.Map.newBuilder[A, B] + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + val x1 = ys1.head + val x2 = ys2.head + if (p(x1, x2)) + buf += ((x1, x2)) + + ys1 = ys1.tail + ys2 = ys2.tail + } + buf.result + } + final def foreach2[A, B](xs1: List[A], xs2: List[B])(f: (A, B) => Unit): Unit = { + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + f(ys1.head, ys2.head) + ys1 = ys1.tail + ys2 = ys2.tail + } + } + final def foreach3[A, B, C](xs1: List[A], xs2: List[B], xs3: List[C])(f: (A, B, C) => Unit): Unit = { + var ys1 = xs1 + var ys2 = xs2 + var ys3 = xs3 + while (!ys1.isEmpty && !ys2.isEmpty && !ys3.isEmpty) { + f(ys1.head, ys2.head, ys3.head) + ys1 = ys1.tail + ys2 = ys2.tail + ys3 = ys3.tail + } + } + final def exists2[A, B](xs1: List[A], xs2: List[B])(f: (A, B) => Boolean): Boolean = { + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + if (f(ys1.head, ys2.head)) + return true + + ys1 = ys1.tail + ys2 = ys2.tail + } + false + } + final def forall2[A, B](xs1: List[A], xs2: List[B])(f: (A, B) => Boolean): Boolean = { + var ys1 = xs1 + var ys2 = xs2 + while (!ys1.isEmpty && !ys2.isEmpty) { + if (!f(ys1.head, ys2.head)) + return false + + ys1 = ys1.tail + ys2 = ys2.tail + } + true + } + final def forall3[A, B, C](xs1: List[A], xs2: List[B], xs3: List[C])(f: (A, B, C) => Boolean): Boolean = { + var ys1 = xs1 + var ys2 = xs2 + var ys3 = xs3 + while (!ys1.isEmpty && !ys2.isEmpty && !ys3.isEmpty) { + if (!f(ys1.head, ys2.head, ys3.head)) + return false + + ys1 = ys1.tail + ys2 = ys2.tail + ys3 = ys3.tail + } + true + } +} diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala index f3eaff8db0..30ee7fc885 100644 --- a/src/compiler/scala/tools/nsc/ast/Trees.scala +++ b/src/compiler/scala/tools/nsc/ast/Trees.scala @@ -77,16 +77,17 @@ trait Trees extends reflect.internal.Trees { self: Global => }}) val (edefs, rest) = body span treeInfo.isEarlyDef val (evdefs, etdefs) = edefs partition treeInfo.isEarlyValDef - val (lvdefs, gvdefs) = evdefs map { + val gvdefs = evdefs map { case vdef @ ValDef(mods, name, tpt, rhs) => - val fld = treeCopy.ValDef( + treeCopy.ValDef( vdef.duplicate, mods, name, atPos(focusPos(vdef.pos)) { TypeTree() setOriginal tpt setPos focusPos(tpt.pos) }, // atPos in case EmptyTree) - val local = treeCopy.ValDef(vdef, Modifiers(PRESUPER), name, tpt, rhs) - (local, fld) - } unzip - + } + val lvdefs = evdefs map { + case vdef @ ValDef(mods, name, tpt, rhs) => + treeCopy.ValDef(vdef, Modifiers(PRESUPER), name, tpt, rhs) + } val constrs = { if (constrMods hasFlag TRAIT) { if (body forall treeInfo.isInterfaceMember) List() diff --git a/src/compiler/scala/tools/nsc/symtab/SymbolTable.scala b/src/compiler/scala/tools/nsc/symtab/SymbolTable.scala index 9fbf649525..a47bfda8c1 100644 --- a/src/compiler/scala/tools/nsc/symtab/SymbolTable.scala +++ b/src/compiler/scala/tools/nsc/symtab/SymbolTable.scala @@ -7,7 +7,6 @@ package scala.tools.nsc package symtab import ast.{Trees, TreePrinters, DocComments} - import util._ -abstract class SymbolTable extends reflect.internal.SymbolTable +abstract class SymbolTable extends reflect.internal.SymbolTable
\ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/transform/LiftCode.scala b/src/compiler/scala/tools/nsc/transform/LiftCode.scala index 9404f0f699..720509644b 100644 --- a/src/compiler/scala/tools/nsc/transform/LiftCode.scala +++ b/src/compiler/scala/tools/nsc/transform/LiftCode.scala @@ -202,7 +202,7 @@ abstract class LiftCode extends Transform with TypingTransformers { /** A method call with a by-name parameter represents escape. */ case Apply(fn, args) if fn.symbol.paramss.nonEmpty => traverse(fn) - for ((param, arg) <- treeInfo.zipMethodParamsAndArgs(tree)) { + treeInfo.foreachMethodParamAndArg(tree) { (param, arg) => if (param.tpe != null && isByNameParamType(param.tpe)) withEscaping(traverse(arg)) else diff --git a/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala b/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala index 9c4889eba9..bbe803a3fb 100644 --- a/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala +++ b/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala @@ -102,7 +102,7 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { def fromSpecialization(sym: Symbol, args: List[Type]): TypeEnv = { ifDebug(assert(sym.info.typeParams.length == args.length, sym + " args: " + args)) - emptyEnv ++ (sym.info.typeParams zip args filter (kv => isSpecialized(kv._1))) + emptyEnv ++ collectMap2(sym.info.typeParams, args)((k, v) => isSpecialized(k)) } /** Does typeenv `t1` include `t2`? All type variables in `t1` @@ -255,7 +255,7 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { val pre1 = this(pre) // when searching for a specialized class, take care to map all // type parameters that are subtypes of AnyRef to AnyRef - val args1 = (args zip sym.typeParams) map { + val args1 = map2(args, sym.typeParams) { case (tp, orig) if isSpecializedAnyRefSubtype(tp, orig) => AnyRefClass.tpe case (tp, _) => tp } @@ -341,7 +341,7 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { case set :: sets => for (x <- set ; xs <- loop(sets)) yield x :: xs } // zip the keys with each permutation to create a TypeEnv - loop(keys map concreteTypes) map (keys zip _ toMap) + loop(keys map concreteTypes) map (xss => Map(keys zip xss: _*)) } /** Does the given 'sym' need to be specialized in the environment 'env'? @@ -445,7 +445,7 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { def produceTypeParameters(syms: List[Symbol], nowner: Symbol, env: TypeEnv) = { val cloned = for (s <- syms) yield if (!env.contains(s)) s.cloneSymbol(nowner) else env(s).typeSymbol // log("producing type params: " + cloned.map(t => (t, t.tpe.bounds.hi))) - for ((orig, cln) <- syms zip cloned) { + foreach2(syms, cloned) { (orig, cln) => cln.removeAnnotation(SpecializedClass) if (env.contains(orig)) cln modifyInfo (info => TypeBounds(info.bounds.lo, AnyRefClass.tpe)) @@ -889,7 +889,7 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { */ def needsSpecialOverride(overriding: Symbol): (Symbol, TypeEnv) = { def checkOverriddenTParams(overridden: Symbol) { - for ((baseTvar, derivedTvar) <- overridden.info.typeParams.zip(overriding.info.typeParams)) { + foreach2(overridden.info.typeParams, overriding.info.typeParams) { (baseTvar, derivedTvar) => val missing = concreteTypes(baseTvar).toSet -- concreteTypes(derivedTvar).toSet if (missing.nonEmpty) { reporter.error(derivedTvar.pos, @@ -1391,9 +1391,9 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { val specMembers = makeSpecializedMembers(tree.symbol.enclClass) ::: (implSpecClasses(body) map localTyper.typed) if (!symbol.isPackageClass) (new CollectMethodBodies)(tree) - val parents1 = currentOwner.info.parents.zipWithIndex.map { - case (tpe, idx) => TypeTree(tpe) setPos parents(idx).pos - } + val parents1 = map2(currentOwner.info.parents, parents)((tpe, parent) => + TypeTree(tpe) setPos parent.pos) + treeCopy.Template(tree, parents1 /*currentOwner.info.parents.map(tpe => TypeTree(tpe) setPos parents.head.pos)*/ , self, diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index 90f46206c5..13516037f5 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -461,7 +461,7 @@ abstract class UnCurry extends InfoTransform val args1 = if (isVarArgTypes(formals)) transformVarargs(formals.last.typeArgs.head) else args - (formals, args1).zipped map { (formal, arg) => + map2(formals, args1) { (formal, arg) => if (!isByNameParamType(formal)) { arg } else if (isByNameRef(arg)) { @@ -771,7 +771,7 @@ abstract class UnCurry extends InfoTransform case p => p.symbol.tpe } val forwresult = dd.symbol.tpe.finalResultType - val forwformsyms = (forwformals, flatparams).zipped map ((tp, oldparam) => + val forwformsyms = map2(forwformals, flatparams)((tp, oldparam) => currentClass.newValueParameter(oldparam.symbol.pos, oldparam.name).setInfo(tp) ) def mono = MethodType(forwformsyms, forwresult) @@ -789,7 +789,7 @@ abstract class UnCurry extends InfoTransform // create the tree val forwtree = theTyper.typedPos(dd.pos) { - val locals = (forwsym ARGS, flatparams).zipped map { + val locals = map2(forwsym ARGS, flatparams) { case (_, fp) if !rpsymbols(fp.symbol) => null case (argsym, fp) => Block(Nil, @@ -799,7 +799,7 @@ abstract class UnCurry extends InfoTransform ) ) } - val seqargs = (locals, forwsym ARGS).zipped map { + val seqargs = map2(locals, forwsym ARGS) { case (null, argsym) => Ident(argsym) case (l, _) => l } diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 67fa67b0f3..2bd307e31a 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -9,7 +9,6 @@ package typechecker import scala.collection.{ mutable, immutable } import scala.collection.mutable.ListBuffer import scala.util.control.ControlThrowable -import scala.tools.util.StringOps.{ countAsString, countElementsAsString } import symtab.Flags._ import scala.annotation.tailrec @@ -459,13 +458,14 @@ trait Infer { } val tvars = tparams map freshVar if (isConservativelyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt)) - (tparams, tvars).zipped map ((tparam, tvar) => + map2(tparams, tvars)((tparam, tvar) => instantiateToBound(tvar, varianceInTypes(formals)(tparam))) else tvars map (tvar => WildcardType) } object AdjustedTypeArgs { + val Result = collection.mutable.LinkedHashMap type Result = collection.mutable.LinkedHashMap[Symbol, Option[Type]] def unapply(m: Result): Some[(List[Symbol], List[Type])] = Some(toLists( @@ -508,24 +508,27 @@ trait Infer { * type parameters that are inferred as `scala.Nothing` and that are not covariant in <code>restpe</code> are taken to be undetermined */ def adjustTypeArgs(tparams: List[Symbol], tvars: List[TypeVar], targs: List[Type], restpe: Type = WildcardType): AdjustedTypeArgs.Result = { - @inline def keep(targ: Type, tparam: Symbol) = ( - targ.typeSymbol != NothingClass // definitely not retracting, it's not Nothing! - || (!restpe.isWildcard && (varianceInType(restpe)(tparam) & COVARIANT) != 0)) // occured covariantly --> don't retract - - @inline def adjusted(targ: Type, tvar: TypeVar) = - if (targ.typeSymbol == RepeatedParamClass) - targ.baseType(SeqClass) - else if (targ.typeSymbol == JavaRepeatedParamClass) - targ.baseType(ArrayClass) - // checks opt.virtPatmat directly so one need not run under -Xexperimental to use virtpatmat - else if (targ.typeSymbol.isModuleClass || ((opt.experimental || opt.virtPatmat) && tvar.constr.avoidWiden)) - targ // this infers Foo.type instead of "object Foo" (see also widenIfNecessary) - else - targ.widen + val buf = AdjustedTypeArgs.Result.newBuilder[Symbol, Option[Type]] + + foreach3(tparams, tvars, targs) { (tparam, tvar, targ) => + val retract = ( + targ.typeSymbol == NothingClass // only retract Nothings + && (restpe.isWildcard || (varianceInType(restpe)(tparam) & COVARIANT) == 0) // don't retract covariant occurrences + ) - (tparams, tvars, targs).zipped.map { (tparam, tvar, targ) => - tparam -> (if(keep(targ, tparam)) Some(adjusted(targ, tvar)) else None) - }(collection.breakOut) + // checks opt.virtPatmat directly so one need not run under -Xexperimental to use virtpatmat + buf += ((tparam, + if (retract) None + else Some( + if (targ.typeSymbol == RepeatedParamClass) targ.baseType(SeqClass) + else if (targ.typeSymbol == JavaRepeatedParamClass) targ.baseType(ArrayClass) + // this infers Foo.type instead of "object Foo" (see also widenIfNecessary) + else if (targ.typeSymbol.isModuleClass || ((opt.experimental || opt.virtPatmat) && tvar.constr.avoidWiden)) targ + else targ.widen + ) + )) + } + buf.result } /** Return inferred type arguments, given type parameters, formal parameters, @@ -584,7 +587,7 @@ trait Infer { if (!isFullyDefined(tvar)) tvar.constr.inst = NoType // Then define remaining type variables from argument types. - (argtpes, formals).zipped map { (argtpe, formal) => + map2(argtpes, formals) { (argtpe, formal) => val tp1 = argtpe.deconst.instantiateTypeParams(tparams, tvars) val pt1 = formal.instantiateTypeParams(tparams, tvars) @@ -756,7 +759,8 @@ trait Infer { typesCompatible(reorderArgs(argtpes1, argPos)) ) } - } else { + } + else { // not enough arguments, check if applicable using defaults val missing = missingParams[Type](argtpes0, params, { case NamedType(name, _) => Some(name) @@ -994,39 +998,13 @@ trait Infer { } } - def checkKindBounds(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): List[String] = { - // @M TODO this method is duplicated all over the place (varianceString) - def varStr(s: Symbol): String = - if (s.isCovariant) "covariant" - else if (s.isContravariant) "contravariant" - else "invariant"; - - def qualify(a0: Symbol, b0: Symbol): String = if (a0.toString != b0.toString) "" else { - if((a0 eq b0) || (a0.owner eq b0.owner)) "" - else { - var a = a0; var b = b0 - while (a.owner.name == b.owner.name) { a = a.owner; b = b.owner} - if (a.locationString ne "") " (" + a.locationString.trim + ")" else "" - } + checkKindBounds0(tparams, targs, pre, owner, true) map { + case (targ, tparam, kindErrors) => + kindErrors.errorMessage(targ, tparam) } - - 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 "+countElementsAsString(a.typeParams.length, "type parameter")+", but "+ - p+qualify(p,a)+" has "+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(", ")) - } - errorMessages.toList } + /** Substitute 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/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala index 8611fafe52..a8dfea02ec 100644 --- a/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala +++ b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala @@ -260,7 +260,7 @@ trait NamesDefaults { self: Analyzer => */ def argValDefs(args: List[Tree], paramTypes: List[Type], blockTyper: Typer): List[ValDef] = { val context = blockTyper.context - val symPs = (args, paramTypes).zipped map ((arg, tpe) => { + val symPs = map2(args, paramTypes)((arg, tpe) => { val byName = isByNameParamType(tpe) val (argTpe, repeated) = if (isScalaRepeatedParamType(tpe)) arg match { @@ -276,7 +276,7 @@ trait NamesDefaults { self: Analyzer => s.setInfo(valType) (context.scope.enter(s), byName, repeated) }) - (symPs, args).zipped map { + map2(symPs, args) { case ((sym, byName, repeated), arg) => val body = if (byName) { @@ -326,13 +326,15 @@ trait NamesDefaults { self: Analyzer => reorderArgsInv(formals, argPos), blockTyper) // refArgs: definition-site order again - val refArgs = (reorderArgs(valDefs, argPos), formals).zipped map ((vDef, tpe) => { + val refArgs = map2(reorderArgs(valDefs, argPos), formals)((vDef, tpe) => { val ref = gen.mkAttributedRef(vDef.symbol) atPos(vDef.pos.focus) { // for by-name parameters, the local value is a nullary function returning the argument - if (isByNameParamType(tpe)) Apply(ref, List()) - else if (isScalaRepeatedParamType(tpe)) Typed(ref, Ident(tpnme.WILDCARD_STAR)) - else ref + tpe.typeSymbol match { + case ByNameParamClass => Apply(ref, Nil) + case RepeatedParamClass => Typed(ref, Ident(tpnme.WILDCARD_STAR)) + case _ => ref + } } }) // cannot call blockTyper.typedBlock here, because the method expr might be partially applied only @@ -340,7 +342,7 @@ trait NamesDefaults { self: Analyzer => res.setPos(res.pos.makeTransparent) val block = Block(stats ::: valDefs, res).setType(res.tpe).setPos(tree.pos) context.namedApplyBlockInfo = - Some((block, NamedApplyInfo(qual, targs, vargss ::: List(refArgs), blockTyper))) + Some((block, NamedApplyInfo(qual, targs, vargss :+ refArgs, blockTyper))) block } } @@ -430,6 +432,80 @@ trait NamesDefaults { self: Analyzer => } } else NoSymbol } + + private def savingUndeterminedTParams[T](context: Context)(fn: List[Symbol] => T): T = { + val savedParams = context.extractUndetparams() + val savedReporting = context.reportAmbiguousErrors + + context.reportAmbiguousErrors = false + try fn(savedParams) + finally { + context.reportAmbiguousErrors = savedReporting + //@M note that we don't get here when an ambiguity was detected (during the computation of res), + // as errorTree throws an exception + context.undetparams = savedParams + } + } + + /** Fast path for ambiguous assignment check. + */ + private def isNameInScope(context: Context, name: Name) = ( + context.enclosingContextChain exists (ctx => + (ctx.scope.lookupEntry(name) != null) + || (ctx.owner.rawInfo.member(name) != NoSymbol) + ) + ) + + /** A full type check is very expensive; let's make sure there's a name + * somewhere which could potentially be ambiguous before we go that route. + */ + private def isAmbiguousAssignment(typer: Typer, param: Symbol, arg: Tree) = { + import typer.context + isNameInScope(context, param.name) && { + // for named arguments, check whether the assignment expression would + // typecheck. if it does, report an ambiguous error. + val paramtpe = param.tpe.cloneInfo(param) + // replace type parameters by wildcard. in the below example we need to + // typecheck (x = 1) with wildcard (not T) so that it succeeds. + // def f[T](x: T) = x + // var x = 0 + // f(x = 1) << "x = 1" typechecks with expected type WildcardType + savingUndeterminedTParams(context) { udp => + val subst = new SubstTypeMap(udp, udp map (_ => WildcardType)) { + override def apply(tp: Type): Type = super.apply(tp match { + case TypeRef(_, ByNameParamClass, x :: Nil) => x + case _ => tp + }) + } + // This throws an exception which is caught in `tryTypedApply` (as it + // uses `silent`) - unfortunately, tryTypedApply recovers from the + // exception if you use errorTree(arg, ...) and conforms is allowed as + // a view (see tryImplicit in Implicits) because it tries to produce a + // new qualifier (if the old one was P, the new one will be + // conforms.apply(P)), and if that works, it pretends nothing happened. + // + // To make sure tryTypedApply fails, we would like to pass EmptyTree + // instead of arg, but can't do that because eventually setType(ErrorType) + // is called, and EmptyTree can only be typed NoType. Thus we need to + // disable conforms as a view... + try typer.silent(_.typed(arg, subst(paramtpe))) match { + case t: Tree => !t.isErroneous + case _ => false + } + catch { + // `silent` only catches and returns TypeErrors which are not + // CyclicReferences. Fix for #3685 + case cr @ CyclicReference(sym, _) => + (sym.name == param.name) && sym.accessedOrSelf.isVariable && { + context.error(sym.pos, + "variable definition needs type because '%s' is used as a named argument in its body.".format(sym.name)) + typer.infer.setError(arg) + true + } + } + } + } + } /** * Removes name assignments from args. Additionally, returns an array mapping @@ -439,71 +515,38 @@ trait NamesDefaults { self: Analyzer => * after named ones. */ def removeNames(typer: Typer)(args: List[Tree], params: List[Symbol]): (List[Tree], Array[Int]) = { - import typer.infer.errorTree - - // maps indicies from (order written by user) to (order of definition) - val argPos = (new Array[Int](args.length)) map (x => -1) + import typer.context + // maps indices from (order written by user) to (order of definition) + val argPos = Array.fill(args.length)(-1) var positionalAllowed = true - val namelessArgs = for ((arg, index) <- (args.zipWithIndex)) yield arg match { - case a @ AssignOrNamedArg(Ident(name), rhs) => - val (pos, newName) = paramPos(params, name) - newName.foreach(n => { - typer.context.unit.deprecationWarning(arg.pos, "the parameter name "+ name +" has been deprecated. Use "+ n +" instead.") - }) - if (pos == -1) { - if (positionalAllowed) { - argPos(index) = index - // prevent isNamed from being true when calling doTypedApply recursively, - // treat the arg as an assignment of type Unit - Assign(a.lhs, rhs).setPos(arg.pos) - } else { - errorTree(arg, "unknown parameter name: "+ name) - } - } else if (argPos contains pos) { - errorTree(arg, "parameter specified twice: "+ name) - } else { - // for named arguments, check whether the assignment expression would - // typecheck. if it does, report an ambiguous error. - val param = params(pos) - val paramtpe = params(pos).tpe.cloneInfo(param) - // replace type parameters by wildcard. in the below example we need to - // typecheck (x = 1) with wildcard (not T) so that it succeeds. - // def f[T](x: T) = x - // var x = 0 - // f(x = 1) << "x = 1" typechecks with expected type WildcardType - val udp = typer.context.extractUndetparams() - val subst = new SubstTypeMap(udp, udp map (_ => WildcardType)) { - override def apply(tp: Type): Type = tp match { - case TypeRef(_, ByNameParamClass, List(arg)) => super.apply(arg) - case _ => super.apply(tp) + val namelessArgs = mapWithIndex(args) { (arg, index) => + def fail(msg: String) = typer.infer.errorTree(arg, msg) + arg match { + case arg @ AssignOrNamedArg(Ident(name), rhs) => + def matchesName(param: Symbol) = !param.isSynthetic && ( + (param.name == name) || (param.deprecatedParamName match { + case Some(`name`) => + context.unit.deprecationWarning(arg.pos, + "the parameter name "+ name +" has been deprecated. Use "+ param.name +" instead.") + true + case _ => false + }) + ) + val pos = params indexWhere matchesName + if (pos == -1) { + if (positionalAllowed) { + argPos(index) = index + // prevent isNamed from being true when calling doTypedApply recursively, + // treat the arg as an assignment of type Unit + Assign(arg.lhs, rhs) setPos arg.pos } + else fail("unknown parameter name: " + name) } - val reportAmbiguousErrors = typer.context.reportAmbiguousErrors - typer.context.reportAmbiguousErrors = false - - var variableNameClash = false - val typedAssign = try { - typer.silent(_.typed(arg, subst(paramtpe))) - } catch { - // `silent` only catches and returns TypeErrors which are not - // CyclicReferences. Fix for #3685 - case cr @ CyclicReference(sym, info) if sym.name == param.name => - if (sym.isVariable || sym.isGetter && sym.accessed.isVariable) { - // named arg not allowed - variableNameClash = true - typer.context.error(sym.pos, - "%s definition needs %s because '%s' is used as a named argument in its body.".format( - "variable", // "method" - "type", // "result type" - sym.name - ) - ) - typer.infer.setError(arg) - } - else cr - } - - def applyNamedArg = { + else if (argPos contains pos) + fail("parameter specified twice: " + name) + else if (isAmbiguousAssignment(typer, params(pos), arg)) + fail("reference to " + name + " is ambiguous; it is both a method parameter and a variable in scope.") + else { // if the named argument is on the original parameter // position, positional after named is allowed. if (index != pos) @@ -511,63 +554,13 @@ trait NamesDefaults { self: Analyzer => argPos(index) = pos rhs } - - val res = typedAssign match { - case _: TypeError => applyNamedArg - - case t: Tree => - if (t.isErroneous && !variableNameClash) { - applyNamedArg - } else if (t.isErroneous) { - t // name clash with variable. error was already reported above. - } else { - // This throws an exception which is caught in `tryTypedApply` (as it - // uses `silent`) - unfortunately, tryTypedApply recovers from the - // exception if you use errorTree(arg, ...) and conforms is allowed as - // a view (see tryImplicit in Implicits) because it tries to produce a - // new qualifier (if the old one was P, the new one will be - // conforms.apply(P)), and if that works, it pretends nothing happened. - // - // To make sure tryTypedApply fails, we would like to pass EmptyTree - // instead of arg, but can't do that because eventually setType(ErrorType) - // is called, and EmptyTree can only be typed NoType. Thus we need to - // disable conforms as a view... - errorTree(arg, "reference to "+ name +" is ambiguous; it is both, a parameter\n"+ - "name of the method and the name of a variable currently in scope.") - } - } - - typer.context.reportAmbiguousErrors = reportAmbiguousErrors - //@M note that we don't get here when an ambiguity was detected (during the computation of res), - // as errorTree throws an exception - typer.context.undetparams = udp - res - } - case _ => - argPos(index) = index - if (positionalAllowed) arg - else errorTree(arg, "positional after named argument.") - } - (namelessArgs, argPos) - } - - /** - * Returns - * - the position of the parameter named `name` - * - optionally, if `name` is @deprecatedName, the new name - */ - def paramPos(params: List[Symbol], name: Name): (Int, Option[Name]) = { - var i = 0 - var rest = params - while (!rest.isEmpty) { - val p = rest.head - if (!p.isSynthetic) { - if (p.name == name) return (i, None) - if (p.deprecatedParamName == Some(name)) return (i, Some(p.name)) + case _ => + argPos(index) = index + if (positionalAllowed) arg + else fail("positional after named argument.") } - i += 1 - rest = rest.tail } - (-1, None) + + (namelessArgs, argPos) } } diff --git a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala index 59a1a254c6..ace38bb4cb 100644 --- a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala +++ b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala @@ -410,8 +410,6 @@ abstract class RefChecks extends InfoTransform with reflect.internal.transform.R } } - - def checkOverrideTypes() { if (other.isAliasType) { //if (!member.typeParams.isEmpty) (1.5) @MAT @@ -420,14 +418,14 @@ abstract class RefChecks extends InfoTransform with reflect.internal.transform.R // overrideError("may not override parameterized type"); // @M: substSym - if( !(sameLength(member.typeParams, other.typeParams) && (self.memberType(member).substSym(member.typeParams, other.typeParams) =:= self.memberType(other))) ) // (1.6) + if( !(sameLength(member.typeParams, other.typeParams) && (memberTp.substSym(member.typeParams, other.typeParams) =:= otherTp)) ) // (1.6) overrideTypeError(); - } else if (other.isAbstractType) { + } + else if (other.isAbstractType) { //if (!member.typeParams.isEmpty) // (1.7) @MAT // overrideError("may not be parameterized"); - - val memberTp = self.memberType(member) val otherTp = self.memberInfo(other) + if (!(otherTp.bounds containsType memberTp)) { // (1.7.1) overrideTypeError(); // todo: do an explaintypes with bounds here explainTypes(_.bounds containsType _, otherTp, memberTp) diff --git a/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala b/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala index c9991614e4..a0ef2f5e2e 100644 --- a/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala +++ b/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala @@ -43,7 +43,7 @@ abstract class SuperAccessors extends transform.Transform with transform.TypingT } private def transformArgs(params: List[Symbol], args: List[Tree]) = { - treeInfo.zipMethodParamsAndArgs(params, args) map { case (param, arg) => + treeInfo.mapMethodParamsAndArgs(params, args) { (param, arg) => if (isByNameParamType(param.tpe)) withInvalidOwner { checkPackedConforms(transform(arg), param.tpe.typeArgs.head) } else transform(arg) diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index a4c00e9f89..6b6b905e16 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -1207,7 +1207,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { if (preSuperVals.isEmpty && preSuperStats.nonEmpty) debugwarn("Wanted to zip empty presuper val list with " + preSuperStats) else - (preSuperStats, preSuperVals).zipped map { case (ldef, gdef) => gdef.tpt.tpe = ldef.symbol.tpe } + map2(preSuperStats, preSuperVals)((ldef, gdef) => gdef.tpt.tpe = ldef.symbol.tpe) case _ => if (!supertparams.isEmpty) error(supertpt.pos, "missing type arguments") @@ -1959,7 +1959,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { if (argpts.lengthCompare(numVparams) != 0) errorTree(fun, "wrong number of parameters; expected = " + argpts.length) else { - val vparamSyms = (fun.vparams, argpts).zipped map { (vparam, argpt) => + val vparamSyms = map2(fun.vparams, argpts) { (vparam, argpt) => if (vparam.tpt.isEmpty) { vparam.tpt.tpe = if (isFullyDefined(argpt)) argpt @@ -2195,15 +2195,16 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { def needsInstantiation(tparams: List[Symbol], formals: List[Type], args: List[Tree]) = { def isLowerBounded(tparam: Symbol) = !tparam.info.bounds.lo.typeSymbol.isBottomClass - (formals, args).zipped exists { + exists2(formals, args) { case (formal, Function(vparams, _)) => (vparams exists (_.tpt.isEmpty)) && vparams.length <= MaxFunctionArity && (formal baseType FunctionClass(vparams.length) match { case TypeRef(_, _, formalargs) => - (formalargs, vparams).zipped.exists ((formalarg, vparam) => - vparam.tpt.isEmpty && (tparams exists (formalarg contains))) && - (tparams forall isLowerBounded) + ( exists2(formalargs, vparams)((formal, vparam) => + vparam.tpt.isEmpty && (tparams exists formal.contains)) + && (tparams forall isLowerBounded) + ) case _ => false }) @@ -2460,7 +2461,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } else { assert(!inPatternMode(mode)) // this case cannot arise for patterns val lenientTargs = protoTypeArgs(tparams, formals, mt.resultApprox, pt) - val strictTargs = (lenientTargs, tparams).zipped map ((targ, tparam) => + val strictTargs = map2(lenientTargs, tparams)((targ, tparam) => if (targ == WildcardType) tparam.tpe else targ) //@M TODO: should probably be .tpeHK var remainingParams = paramTypes def typedArgToPoly(arg: Tree, formal: Type): Tree = { //TR TODO: cleanup @@ -2477,7 +2478,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } arg1 } - val args1 = (args, formals).zipped map typedArgToPoly + val args1 = map2(args, formals)(typedArgToPoly) if (args1 exists (_.tpe.isError)) errTree else { debuglog("infer method inst "+fun+", tparams = "+tparams+", args = "+args1.map(_.tpe)+", pt = "+pt+", lobounds = "+tparams.map(_.tpe.bounds.lo)+", parambounds = "+tparams.map(_.info)) //debug @@ -2926,7 +2927,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { override val typeParams = tparams map (_.symbol) val typeSkolems = typeParams map (_.newTypeSkolem setInfo this) // Replace the symbols - def substitute() = (tparams, typeSkolems).zipped map (_ setSymbol _) + def substitute() = map2(tparams, typeSkolems)(_ setSymbol _) override def complete(sym: Symbol) { // The info of a skolem is the skolemized info of the // actual type parameter of the skolem @@ -3972,7 +3973,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } val argtypes = args1 map (_.tpe) - (args, tparams).zipped foreach { (arg, tparam) => arg match { + foreach2(args, tparams)((arg, tparam) => arg match { // note: can't use args1 in selector, because Bind's got replaced case Bind(_, _) => if (arg.symbol.isAbstractType) @@ -3981,7 +3982,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { lub(List(arg.symbol.info.bounds.lo, tparam.info.bounds.lo.subst(tparams, argtypes))), glb(List(arg.symbol.info.bounds.hi, tparam.info.bounds.hi.subst(tparams, argtypes)))) case _ => - }} + }) val original = treeCopy.AppliedTypeTree(tree, tpt1, args1) val result = TypeTree(appliedType(tpt1.tpe, argtypes)) setOriginal original if(tpt1.tpe.isInstanceOf[PolyType]) // did the type application (performed by appliedType) involve an unchecked beta-reduction? @@ -4079,7 +4080,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { case UnApply(fun, args) => val fun1 = typed(fun) val tpes = formalTypes(unapplyTypeList(fun.symbol, fun1.tpe), args.length) - val args1 = (args, tpes).zipped map typedPattern + val args1 = map2(args, tpes)(typedPattern) treeCopy.UnApply(tree, fun1, args1) setType pt case ArrayValue(elemtpt, elems) => diff --git a/src/compiler/scala/tools/util/EditDistance.scala b/src/compiler/scala/tools/util/EditDistance.scala index b705a1eac4..5067dce384 100644 --- a/src/compiler/scala/tools/util/EditDistance.scala +++ b/src/compiler/scala/tools/util/EditDistance.scala @@ -30,23 +30,37 @@ object EditDistance { if (m == 0) return n val d = Array.ofDim[Int](n + 1, m + 1) - 0 to n foreach (x => d(x)(0) = x) - 0 to m foreach (x => d(0)(x) = x) + var i = 0 + val max = math.max(m, n) + while (i <= max) { + if (i <= n) + d(i)(0) = i + if (i <= m) + d(0)(i) = i + i += 1 + } + i = 1 - for (i <- 1 to n ; s_i = s(i - 1) ; j <- 1 to m) { - val t_j = t(j - 1) - val cost = if (s_i == t_j) 0 else 1 + while (i <= n) { + val s_i = s(i - 1) + var j = 1 + while (j <= m) { + val t_j = t(j - 1) + val cost = if (s_i == t_j) 0 else 1 - val c1 = d(i - 1)(j) + 1 - val c2 = d(i)(j - 1) + 1 - val c3 = d(i - 1)(j - 1) + cost + val c1 = d(i - 1)(j) + 1 + val c2 = d(i)(j - 1) + 1 + val c3 = d(i - 1)(j - 1) + cost - d(i)(j) = c1 min c2 min c3 + d(i)(j) = c1 min c2 min c3 - if (transpositions) { - if (i > 1 && j > 1 && s(i - 1) == t(j - 2) && s(i - 2) == t(j - 1)) - d(i)(j) = d(i)(j) min (d(i - 2)(j - 2) + cost) + if (transpositions) { + if (i > 1 && j > 1 && s(i - 1) == t(j - 2) && s(i - 2) == t(j - 1)) + d(i)(j) = d(i)(j) min (d(i - 2)(j - 2) + cost) + } + j += 1 } + i += 1 } d(n)(m) diff --git a/src/library/scala/collection/LinearSeqLike.scala b/src/library/scala/collection/LinearSeqLike.scala index 75c1edac66..ceb980ff80 100644 --- a/src/library/scala/collection/LinearSeqLike.scala +++ b/src/library/scala/collection/LinearSeqLike.scala @@ -13,6 +13,7 @@ import generic._ import mutable.ListBuffer import immutable.List import scala.util.control.Breaks._ +import annotation.tailrec /** A template trait for linear sequences of type `LinearSeq[A]`. * @@ -69,4 +70,9 @@ trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr xs } } + + @tailrec override final def corresponds[B](that: GenSeq[B])(p: (A,B) => Boolean): Boolean = { + if (this.isEmpty) that.isEmpty + else that.nonEmpty && p(head, that.head) && (tail corresponds that.tail)(p) + } } |