diff options
author | Martin Odersky <odersky@gmail.com> | 2009-03-15 14:25:51 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2009-03-15 14:25:51 +0000 |
commit | ff9887891f8f865617c60351a3afc8daced2db0e (patch) | |
tree | 476ebe03d60807f0de5a41835efe9926faff5faa /src | |
parent | a14b43742168c3dae77cafeb2ed7862e8890945e (diff) | |
download | scala-ff9887891f8f865617c60351a3afc8daced2db0e.tar.gz scala-ff9887891f8f865617c60351a3afc8daced2db0e.tar.bz2 scala-ff9887891f8f865617c60351a3afc8daced2db0e.zip |
Better inference for implicits; some preparatio...
Better inference for implicits; some preparations for new collections.
Diffstat (limited to 'src')
5 files changed, 133 insertions, 56 deletions
diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala index 06c59d6133..65510ea363 100644 --- a/src/compiler/scala/tools/nsc/ast/Trees.scala +++ b/src/compiler/scala/tools/nsc/ast/Trees.scala @@ -1641,6 +1641,7 @@ trait Trees { super.traverse(tree) } override def apply[T <: Tree](tree: T): T = super.apply(tree.duplicate) + override def toString() = "TreeTypeSubstituter("+from+","+to+")" } lazy val EmptyTreeTypeSubstituter = new TreeTypeSubstituter(List(), List()) @@ -1658,6 +1659,7 @@ trait Trees { super.traverse(tree) } override def apply[T <: Tree](tree: T): T = super.apply(tree.duplicate) + override def toString() = "TreeSymSubstituter("+from+","+to+")" } class ChangeOwnerTraverser(val oldowner: Symbol, val newowner: Symbol) extends Traverser { diff --git a/src/compiler/scala/tools/nsc/symtab/Definitions.scala b/src/compiler/scala/tools/nsc/symtab/Definitions.scala index 013c5be3d0..0c37a9574b 100644 --- a/src/compiler/scala/tools/nsc/symtab/Definitions.scala +++ b/src/compiler/scala/tools/nsc/symtab/Definitions.scala @@ -102,19 +102,20 @@ trait Definitions { /* lazy val ByNameFunctionClass: Symbol = getClass("scala.ByNameFunction") */ - lazy val IterableClass: Symbol = getClass("scala.Iterable") + lazy val IterableClass: Symbol = getClass2("scala.Iterable", "scala.collection.Iterable") def Iterable_next = getMember(IterableClass, nme.next) def Iterable_hasNext = getMember(IterableClass, nme.hasNext) - lazy val IteratorClass: Symbol = getClass("scala.Iterator") - lazy val SeqClass: Symbol = getClass("scala.Seq") - lazy val RandomAccessSeqMutableClass: Symbol = getMember(getModule("scala.RandomAccessSeq"), nme.Mutable) + lazy val IteratorClass: Symbol = getClass2("scala.Iterator", "scala.collection.Iterator") + lazy val SeqClass: Symbol = getClass2("scala.Seq", "scala.collection.Sequence") + lazy val RandomAccessSeqMutableClass: Symbol = getMember( + getModule2("scala.RandomAccessSeq", "scala.collection.Vector"), nme.Mutable) def Seq_length = getMember(SeqClass, nme.length) - lazy val ListClass: Symbol = getClass("scala.List") + lazy val ListClass: Symbol = getClass2("scala.List", "scala.collection.immutable.List") def List_isEmpty = getMember(ListClass, nme.isEmpty) def List_head = getMember(ListClass, nme.head) def List_tail = getMember(ListClass, nme.tail) - lazy val ListModule: Symbol = getModule("scala.List") + lazy val ListModule: Symbol = getModule2("scala.List", "scala.collection.immutable.List") def List_apply = getMember(ListModule, nme.apply) lazy val ArrayClass: Symbol = getClass("scala.Array") def Array_apply = getMember(ArrayClass, nme.apply) @@ -269,8 +270,8 @@ trait Definitions { def seqType(arg: Type) = typeRef(SeqClass.typeConstructor.prefix, SeqClass, List(arg)) - def NilModule: Symbol = getModule("scala.Nil") - def ConsClass: Symbol = getClass("scala.$colon$colon") + def NilModule: Symbol = getModule2("scala.Nil", "scala.collection.immutable.Nil") + def ConsClass: Symbol = getClass2("scala.$colon$colon", "scala.collection.immutable.$colon$colon") // members of class scala.Any var Any_== : Symbol = _ @@ -331,8 +332,34 @@ trait Definitions { lazy val VolatileAttr: Symbol = getClass("scala.volatile") def getModule(fullname: Name): Symbol = getModuleOrClass(fullname, true) + def getModule2(name1: Name, name2: Name) = try { + getModuleOrClass(name1, true) + } catch { + case ex1: FatalError => + try { + getModuleOrClass(name2, true) + } catch { + case ex2: FatalError => throw ex1 + } + } - def getClass(fullname: Name): Symbol = getModuleOrClass(fullname, false) + def getClass(fullname: Name): Symbol = { + var result = getModuleOrClass(fullname, false) + while (result.isAliasType) result = result.info.typeSymbol + result + } + + def getClass2(name1: Name, name2: Name) = try { + var result = getModuleOrClass(name1, false) + if (result.isAliasType) getClass(name2) else result + } catch { + case ex1: FatalError => + try { + getModuleOrClass(name2, false) + } catch { + case ex2: FatalError => throw ex1 + } + } def getMember(owner: Symbol, name: Name): Symbol = { if (owner == NoSymbol) return NoSymbol @@ -704,7 +731,7 @@ trait Definitions { CodeModule = getModule(sn.Code) RepeatedParamClass = newCovariantPolyClass( ScalaPackageClass, nme.REPEATED_PARAM_CLASS_NAME, - tparam => typeRef(SeqClass.typeConstructor.prefix, SeqClass, List(tparam.typeConstructor))) + tparam => seqType(tparam.typeConstructor)) ByNameParamClass = newCovariantPolyClass( ScalaPackageClass, nme.BYNAME_PARAM_CLASS_NAME, tparam => AnyClass.typeConstructor) diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index 9f200c94cf..6d91179c3d 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -28,6 +28,8 @@ self: Analyzer => import definitions._ import posAssigner.atPos + final val traceImplicits = false + /** Search for an implicit value. See the comment on `result` at the end of class `ImplicitSearch` * for more info how the search is conducted. * @param tree The tree for which the implicit needs to be inserted. @@ -43,7 +45,7 @@ self: Analyzer => * @return A search result */ def inferImplicit(tree: Tree, pt0: Type, reportAmbiguous: Boolean, context: Context): SearchResult = { - if (!tree.isEmpty && !context.undetparams.isEmpty) + if (traceImplicits && !tree.isEmpty && !context.undetparams.isEmpty) println("typing implicit with undetermined type params: "+context.undetparams+"\n"+tree) val search = new ImplicitSearch(tree, pt0, context.makeImplicit(reportAmbiguous)) context.undetparams = context.undetparams remove (search.result.subst.from contains _) @@ -55,7 +57,9 @@ self: Analyzer => * @param subst A substituter that represents the undetermined type parameters * that were instantiated by the winning implicit. */ - class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter) + class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter) { + override def toString = "SearchResult("+tree+", "+subst+")" + } lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) @@ -110,7 +114,7 @@ self: Analyzer => def improves(info1: ImplicitInfo, info2: ImplicitInfo) = (info2 == NoImplicitInfo) || (info1 != NoImplicitInfo) && - isStrictlyMoreSpecific(info1.tpe, info2.tpe) + isStrictlyMoreSpecific(info1.tpe, info2.tpe, info1.sym, info2.sym) /** Map all type params in given list to WildcardType * @param tp The type in which to do the mapping @@ -230,11 +234,13 @@ self: Analyzer => private def typedImplicit(info: ImplicitInfo): SearchResult = context.openImplicits find (dominates(pt, _)) match { case Some(pending) => + println("Pending implicit "+pending+" dominates "+pt) throw DivergentImplicit SearchFailure case None => try { context.openImplicits = pt :: context.openImplicits + //println(" "*context.openImplicits.length+"typed implicit "+info+" for "+pt) typedImplicit0(info) } catch { case DivergentImplicit => @@ -263,32 +269,44 @@ self: Analyzer => case _ => tp.isStable } - if (!isPlausiblyCompatible(info.tpe, pt) || !isStable(info.pre)) return SearchFailure + /** Replace undetParams in type `tp` by Any/Nothing, according to variance */ + def approximate(tp: Type) = + tp.instantiateTypeParams(undetParams, undetParams map (_ => WildcardType)) + + /** Instantiated `pt' so that covariant occurrences of undetermined + * type parameters are replaced by Any, and all other occurrences + * are replaced by Nothing + */ + val wildPt = approximate(pt) - val tvars = undetParams map freshVar + if (traceImplicits) println("typed impl for "+wildPt+"? "+info.name+":"+info.tpe+"/"+undetParams) + if (isPlausiblyCompatible(info.tpe, wildPt) && + isCompatible(depoly(info.tpe), wildPt) && + isStable(info.pre)) { - // println("typed impl for "+pt+"? "+info.name+":"+info.tpe+(isPlausiblyCompatible(info.tpe, pt))+isCompatible(depoly(info.tpe), pt)+isStable(info.pre)) - if (isCompatible(depoly(info.tpe), pt.instantiateTypeParams(undetParams, tvars))) { val itree = atPos(tree.pos) { if (info.pre == NoPrefix) Ident(info.name) else Select(gen.mkAttributedQualifier(info.pre), info.name) } - // println("typed impl?? "+info.name+":"+info.tpe+" ==> "+itree+" with "+pt) + if (traceImplicits) println("typed impl?? "+info.name+":"+info.tpe+" ==> "+itree+" with "+wildPt) def fail(reason: String): SearchResult = { if (settings.XlogImplicits.value) - inform(itree+" is not a valid implicit value for "+pt+" because:\n"+reason) + inform(itree+" is not a valid implicit value for "+pt0+" because:\n"+reason) SearchFailure } try { val itree1 = if (isView) - typed1(Apply(itree, List(Ident("<argument>") setType pt0.paramTypes.head)), EXPRmode, pt0.resultType) + typed1( + Apply(itree, List(Ident("<argument>").setType(approximate(pt0.paramTypes.head)))), + EXPRmode, approximate(pt0.resultType)) else - typed1(itree, EXPRmode, pt) - //if (settings.debug.value) println("typed implicit "+itree1+":"+itree1.tpe+", pt = "+pt) + typed1(itree, EXPRmode, wildPt) + + if (traceImplicits) println("typed implicit "+itree1+":"+itree1.tpe+", pt = "+wildPt) val itree2 = if (isView) (itree1: @unchecked) match { case Apply(fun, _) => fun } - else adapt(itree1, EXPRmode, pt) - //if (settings.debug.value) println("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+pt)("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+pt) + else adapt(itree1, EXPRmode, wildPt) + if (traceImplicits) println("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+wildPt) def hasMatchingSymbol(tree: Tree): Boolean = (tree.symbol == info.sym) || { tree match { case Apply(fun, _) => hasMatchingSymbol(fun) @@ -297,15 +315,25 @@ self: Analyzer => case _ => false } } + if (itree2.tpe.isError) SearchFailure else if (hasMatchingSymbol(itree1)) { - val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt), - false, lubDepth(List(depoly(info.tpe), pt))) - val subst = new TreeTypeSubstituter(undetParams, targs) - subst traverse itree2 - // todo: remove type params that have been instantiated to Nothing, similar - // to methTypeArgs - new SearchResult(itree2, subst) + val tvars = undetParams map freshVar + if (isCompatible(itree2.tpe, pt.instantiateTypeParams(undetParams, tvars))) { + if (traceImplicits) println("tvars = "+tvars+"/"+(tvars map (_.constr))) + val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt), + false, lubDepth(List(itree2.tpe, pt))) + val subst = new TreeTypeSubstituter(undetParams, targs) + subst traverse itree2 + // todo: remove type params that have been instantiated to Nothing, similar + // to methTypeArgs + val result = new SearchResult(itree2, subst) + if (traceImplicits) println("RESULT = "+result) + result + } else { + if (traceImplicits) println("incompatible???") + SearchFailure + } } else if (settings.XlogImplicits.value) fail("candidate implicit "+info.sym+info.sym.locationString+ " is shadowed by other implicit: "+itree1.symbol+itree1.symbol.locationString) diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 1af310cc6b..db43125ccc 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -518,6 +518,22 @@ trait Infer { tvars map (tvar => WildcardType) } + /** Retract any Nothing arguments which appear covariantly in result type, + * and treat them as uninstantiated parameters instead. + * Map T* entries to Seq[T]. + */ + def adjustTypeArgs(tparams: List[Symbol], targs: List[Type], restpe: Type, uninstantiated: ListBuffer[Symbol]): List[Type] = + List.map2(tparams, targs) {(tparam, targ) => + if (targ.typeSymbol == NothingClass && (varianceInType(restpe)(tparam) & COVARIANT) == 0) { + uninstantiated += tparam + tparam.tpe + } else if (targ.typeSymbol == RepeatedParamClass) { + targ.baseType(SeqClass) + } else { + targ.widen + } + } + /** Return inferred type arguments, given type parameters, formal parameters, * argument types, result type and expected result type. * If this is not possible, throw a <code>NoInstance</code> exception. @@ -572,16 +588,7 @@ trait Infer { val targs = solvedTypes(tvars, tparams, tparams map varianceInTypes(formals), false, lubDepth(formals) max lubDepth(argtpes)) // val res = - List.map2(tparams, targs) {(tparam, targ) => - if (targ.typeSymbol == NothingClass && (varianceInType(restpe)(tparam) & COVARIANT) == 0) { - uninstantiated += tparam - tparam.tpe //@M TODO: might be affected by change to tpe in Symbol - } else if (targ.typeSymbol == RepeatedParamClass) { - targ.baseType(SeqClass) - } else { - targ.widen - } - } + adjustTypeArgs(tparams, targs, restpe, uninstantiated) // println("meth type args "+", tparams = "+tparams+", formals = "+formals+", restpe = "+restpe+", argtpes = "+argtpes+", underlying = "+(argtpes map (_.widen))+", pt = "+pt+", uninstantiated = "+uninstantiated.toList+", result = "+res) //DEBUG // res } @@ -672,7 +679,7 @@ trait Infer { case OverloadedType(pre, alts) => alts exists (alt => isMoreSpecific(pre.memberType(alt), ftpe2)) case et: ExistentialType => - et.withTypeVars(isStrictlyMoreSpecific(_, ftpe2)) + et.withTypeVars(isMoreSpecific(_, ftpe2)) // !!! why isStrictly? case MethodType(formals @ (x :: xs), _) => isApplicable(List(), ftpe2, formals, WildcardType) case PolyType(_, MethodType(formals @ (x :: xs), _)) => @@ -684,19 +691,26 @@ trait Infer { case OverloadedType(pre, alts) => alts forall (alt => isMoreSpecific(ftpe1, pre.memberType(alt))) case et: ExistentialType => - et.withTypeVars(isStrictlyMoreSpecific(ftpe1, _)) + et.withTypeVars(isMoreSpecific(ftpe1, _)) case MethodType(_, _) | PolyType(_, MethodType(_, _)) => true case _ => isMoreSpecificValueType(ftpe1, ftpe2, List(), List()) } } - +/* def isStrictlyMoreSpecific(ftpe1: Type, ftpe2: Type): Boolean = ftpe1.isError || isMoreSpecific(ftpe1, ftpe2) && (!isMoreSpecific(ftpe2, ftpe1) || !ftpe1.isInstanceOf[OverloadedType] && ftpe2.isInstanceOf[OverloadedType] || phase.erasedTypes && covariantReturnOverride(ftpe1, ftpe2)) +*/ + def isStrictlyMoreSpecific(ftpe1: Type, ftpe2: Type, sym1: Symbol, sym2: Symbol): Boolean = + ftpe1.isError || isMoreSpecific(ftpe1, ftpe2) && + (!isMoreSpecific(ftpe2, ftpe1) || + (sym1.owner isSubClass sym2.owner) && (sym1.owner != sym2.owner) || + !ftpe1.isInstanceOf[OverloadedType] && ftpe2.isInstanceOf[OverloadedType] || + phase.erasedTypes && covariantReturnOverride(ftpe1, ftpe2)) private def covariantReturnOverride(ftpe1: Type, ftpe2: Type): Boolean = (ftpe1, ftpe2) match { case (MethodType(_, rtpe1), MethodType(_, rtpe2)) => @@ -921,14 +935,21 @@ trait Infer { * @param undetparams ... * @param pt ... */ - def inferExprInstance(tree: Tree, undetparams: List[Symbol], pt: Type) { + def inferExprInstance(tree: Tree, tparams: List[Symbol], pt: Type, keepNothings: Boolean): List[Symbol] = { if (inferInfo) println("infer expr instance "+tree+":"+tree.tpe+"\n"+ - " undetparams = "+undetparams+"\n"+ + " tparams = "+tparams+"\n"+ " pt = "+pt) - substExpr(tree, undetparams, exprTypeArgs(undetparams, tree.tpe, pt), pt) + val targs = exprTypeArgs(tparams, tree.tpe, pt) + val uninstantiated = new ListBuffer[Symbol] + val detargs = if (keepNothings) targs + else adjustTypeArgs(tparams, targs, pt, uninstantiated) + val undetparams = uninstantiated.toList + val detparams = tparams remove (undetparams contains _) + substExpr(tree, detparams, detargs, pt) if (inferInfo) println("inferred expr instance "+tree) + undetparams } /** Substitite free type variables `undetparams' of polymorphic argument @@ -1300,7 +1321,7 @@ trait Infer { val tp2 = pre.memberType(sym2) (tp2 == ErrorType || !global.typer.infer.isWeaklyCompatible(tp2, pt) && global.typer.infer.isWeaklyCompatible(tp1, pt) || - isStrictlyMoreSpecific(tp1, tp2)) } + isStrictlyMoreSpecific(tp1, tp2, sym1, sym2)) } val best = ((NoSymbol: Symbol) /: alts1) ((best, alt) => if (improves(alt, best)) alt else best) val competing = alts1 dropWhile (alt => best == alt || improves(best, alt)) @@ -1348,7 +1369,7 @@ trait Infer { val applicable = alts filter (alt => isApplicable(undetparams, followApply(pre.memberType(alt)), argtpes, pt)) def improves(sym1: Symbol, sym2: Symbol) = sym2 == NoSymbol || sym2.isError || - isStrictlyMoreSpecific(followApply(pre.memberType(sym1)), followApply(pre.memberType(sym2))) + isStrictlyMoreSpecific(followApply(pre.memberType(sym1)), followApply(pre.memberType(sym2)), sym1, sym2) val best = ((NoSymbol: Symbol) /: applicable) ((best, alt) => if (improves(alt, best)) alt else best) val competing = applicable dropWhile (alt => best == alt || improves(best, alt)) diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index d878c3700d..955bd9ee4c 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -746,12 +746,11 @@ trait Typers { self: Analyzer => adapt(tree1 setType restpe.substSym(tparams, tparams1), mode, pt) case mt: ImplicitMethodType if ((mode & (EXPRmode | FUNmode | LHSmode)) == EXPRmode) => // (4.1) if (!context.undetparams.isEmpty && (mode & POLYmode) == 0) { // (9) - inferExprInstance(tree, context.extractUndetparams(), pt) - adapt(tree, mode, pt) - } else { - val typer1 = constrTyperIf(treeInfo.isSelfOrSuperConstrCall(tree)) - typer1.typed(typer1.applyImplicitArgs(tree), mode, pt) + context.undetparams = inferExprInstance( + tree, context.extractUndetparams(), pt, false) } + val typer1 = constrTyperIf(treeInfo.isSelfOrSuperConstrCall(tree)) + typer1.typed(typer1.applyImplicitArgs(tree), mode, pt) case mt: MethodType if (((mode & (EXPRmode | FUNmode | LHSmode)) == EXPRmode) && (context.undetparams.isEmpty || (mode & POLYmode) != 0)) => @@ -936,7 +935,7 @@ trait Typers { self: Analyzer => * @return ... */ def instantiate(tree: Tree, mode: Int, pt: Type): Tree = { - inferExprInstance(tree, context.extractUndetparams(), pt) + inferExprInstance(tree, context.extractUndetparams(), pt, true) adapt(tree, mode, pt) } @@ -1906,7 +1905,7 @@ trait Typers { self: Analyzer => } else if (needsInstantiation(tparams, formals, args1)) { //println("needs inst "+fun+" "+tparams+"/"+(tparams map (_.info))) - inferExprInstance(fun, tparams, WildcardType) + inferExprInstance(fun, tparams, WildcardType, true) doTypedApply(tree, fun, args1, mode, pt) } else { assert((mode & PATTERNmode) == 0); // this case cannot arise for patterns |