From 3bbffde3033aa8fecae6f23140421c04cf215544 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 13 Mar 2009 19:20:46 +0000 Subject: added missing Implicits.scala file --- .../scala/tools/nsc/typechecker/Implicits.scala | 574 +++++++++++++++++++++ 1 file changed, 574 insertions(+) create mode 100644 src/compiler/scala/tools/nsc/typechecker/Implicits.scala diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala new file mode 100644 index 0000000000..9f200c94cf --- /dev/null +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -0,0 +1,574 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2009 LAMP/EPFL + * @author Martin Odersky + */ +// $Id: Typers.scala 17229 2009-03-02 19:09:42Z extempore $ + +//todo: rewrite or disllow new T where T is a mixin (currently: not a member of T) +//todo: use inherited type info also for vars and values +//todo: disallow C#D in superclass +//todo: treat :::= correctly +package scala.tools.nsc.typechecker + +import scala.collection.mutable.{HashMap, ListBuffer} +import scala.compat.Platform.currentTime +import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile} +import symtab.Flags._ +import util.HashSet + +/** This trait provides methods to find various kinds of implicits. + * + * @author Martin Odersky + * @version 1.0 + */ +trait Implicits { +self: Analyzer => + + import global._ + import definitions._ + import posAssigner.atPos + + /** 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. + * (the inference might instantiate some of the undetermined + * type parameters of that tree. + * @param pt0 The original expected type of the implicit. A method type + * for `pt0` implies we are looking for a view, any other type implies + * we are looking for an implicit parameter. + * @param reportAmbiguous Should ambiguous implicit errors be reported? + * False iff we search for a view to find out + * whether one type is coercible to another. + * @param context The current context + * @return A search result + */ + def inferImplicit(tree: Tree, pt0: Type, reportAmbiguous: Boolean, context: Context): SearchResult = { + if (!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 _) + search.result + } + + /** The result of an implicit search + * @param tree The tree representing the implicit + * @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) + + lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) + + /** A class that records an available implicit + * @param name The name of the implicit + * @param pre The prefix type of the implicit + * @param sym The symbol of the implicit + */ + class ImplicitInfo(val name: Name, val pre: Type, val sym: Symbol) { + private var tpeCache: Type = null + + /** Computes member type of implicit from prefix `pre` (cached). */ + def tpe: Type = { + if (tpeCache eq null) tpeCache = pre.memberType(sym) + tpeCache + } + + override def equals(other: Any) = other match { + case that: ImplicitInfo => + if (this eq NoImplicitInfo) that eq this + else + this.name == that.name && + this.pre =:= that.pre && + this.sym == that.sym + case _ => + false + } + + override def hashCode = + name.hashCode + pre.hashCode + sym.hashCode + + override def toString = "ImplicitInfo(" + name + "," + pre + "," + sym + ")" + } + + /** A sentinel indicating no implicit was found */ + val NoImplicitInfo = new ImplicitInfo(null, null, null) + + /** A class that sets up an implicit search. For more info, see comments for `inferImplicit`. + * @param tree The tree for which the implicit needs to be inserted. + * @param pt0 The original expected type of the implicit. A method type + * for `pt0` implies we are looking for a view, any other type implies + * we are looking for an implicit parameter. + * @param context0 The context used for the implicit search + */ + private class ImplicitSearch(tree: Tree, pt0: Type, context0: Context) + extends Typer(context0) { + + import infer._ + + /** Is implicit info `info1` better than implicit info `info2`? + */ + def improves(info1: ImplicitInfo, info2: ImplicitInfo) = + (info2 == NoImplicitInfo) || + (info1 != NoImplicitInfo) && + isStrictlyMoreSpecific(info1.tpe, info2.tpe) + + /** Map all type params in given list to WildcardType + * @param tp The type in which to do the mapping + * @param tparams The list of type parameters to map + */ + private def tparamsToWildcards(tp: Type, tparams: List[Symbol]) = + tp.instantiateTypeParams(tparams, tparams map (t => WildcardType)) + + /* Map a polytype to one in which all type parameters are replaced by wildcards. + */ + private def depoly(tp: Type): Type = tp match { + case PolyType(tparams, restpe) => tparamsToWildcards(restpe, tparams) + case _ => tp + } + + /** Does type `tp` contain an Error type as parameter or result? + */ + private def containsError(tp: Type): Boolean = tp match { + case PolyType(tparams, restpe) => containsError(restpe) + case MethodType(formals, restpe) => (formals exists (_.isError)) || containsError(restpe) + case _ => tp.isError + } + + /** Does type `dtor` dominate type `dted`? + * This is the case if the stripped cores `dtor1` and `dted1` of both types are + * the same wrt `=:=`, or if they overlap and the complexity of `dtor1` is higher + * than the complexity of `dted1`. + * The _stripped core_ of a type is the type where + * - all refinements and annotations are dropped, + * - all universal and existential quantification is eliminated + * by replacing variables by their upper bounds, + * - all remaining free type parameters in the type are replaced by WildcardType. + * The _complexity_ of a stripped core type corresponds roughly to the number of + * nodes in its ast, except that singleton types are widened befoe taking the complexity. + * Two types overlap if they have the same type symbol, or + * if one or both are intersection types with a pair of overlapiing parent types. + */ + private def dominates(dtor: Type, dted: Type): Boolean = { + def core(tp: Type): Type = tp.normalize match { + case RefinedType(parents, defs) => intersectionType(parents map core, tp.typeSymbol.owner) + case AnnotatedType(attribs, tp, selfsym) => core(tp) + case ExistentialType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) + case PolyType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) + case _ => tp + } + def stripped(tp: Type): Type = { + val tparams = freeTypeParametersNoSkolems.collect(tp) + tp.subst(tparams, tparams map (t => WildcardType)) + } + def sum(xs: List[Int]) = (0 /: xs)(_ + _) + def complexity(tp: Type): Int = tp.normalize match { + case NoPrefix => + 0 + case SingleType(pre, sym) => + if (sym.isPackage) 0 else complexity(tp.widen) + case TypeRef(pre, sym, args) => + complexity(pre) + sum(args map complexity) + 1 + case RefinedType(parents, _) => + sum(parents map complexity) + 1 + case _ => + 1 + } + def overlaps(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match { + case (RefinedType(parents, _), _) => parents exists (overlaps(_, tp2)) + case (_, RefinedType(parents, _)) => parents exists (overlaps(tp1, _)) + case _ => tp1.typeSymbol == tp2.typeSymbol + } + val dtor1 = stripped(core(dtor)) + val dted1 = stripped(core(dted)) + overlaps(dtor1, dted1) && (dtor1 =:= dted1 || complexity(dtor1) > complexity(dted1)) + } + + /** The normalized expected type (which is a value type). */ + private val pt = normalize(pt0) + + /** Are we looking for an implicit view? This is signalled by the original expected type + * being a method or a polymorphic type. + */ + private val isView = pt0 match { + case MethodType(_, _) | PolyType(_, _) => true + case _ => false + } + + if (util.Statistics.enabled) implcnt += 1 + private val startTime = if (util.Statistics.enabled) currentTime else 0l + + /** Issues an error signalling ambiguous implicits */ + private def ambiguousImplicitError(info1: ImplicitInfo, info2: ImplicitInfo, + pre1: String, pre2: String, trailer: String) = + if (!info1.tpe.isErroneous && !info2.tpe.isErroneous) { + val coreMsg = + pre1+" "+info1.sym+info1.sym.locationString+" of type "+info1.tpe+"\n "+ + pre2+" "+info2.sym+info2.sym.locationString+" of type "+info2.tpe+"\n "+ + trailer + error(tree.pos, + if (isView) { + val found = pt.typeArgs(0) + val req = pt.typeArgs(1) + typeErrorMsg(found, req)+ + "\nNote that implicit conversions are not applicable because they are ambiguous:\n "+ + coreMsg+"are possible conversion functions from "+ found+" to "+req + } else { + "ambiguous implicit values:\n "+coreMsg + "match expected type "+pt + }) + } + + /** The type parameters to instantiate */ + val undetParams = if (isView) List() else context.outer.undetparams + + /** Try to construct a typed tree from given implicit info with given + * expected type. + * Detect infinite search trees for implicits. + * + * @param info The given implicit info describing the implicit definition + * @pre info.tpe does not contain an error + */ + private def typedImplicit(info: ImplicitInfo): SearchResult = + context.openImplicits find (dominates(pt, _)) match { + case Some(pending) => + throw DivergentImplicit + SearchFailure + case None => + try { + context.openImplicits = pt :: context.openImplicits + typedImplicit0(info) + } catch { + case DivergentImplicit => + if (context.openImplicits.tail.isEmpty) { + if (!(pt.isErroneous)) + context.unit.error( + tree.pos, "diverging implicit expansion for type "+pt+"\nstarting with "+ + info.sym+info.sym.locationString) + SearchFailure + } else { + throw DivergentImplicit + } + } finally { + context.openImplicits = context.openImplicits.tail + } + } + + private def typedImplicit0(info: ImplicitInfo): SearchResult = { + + /** Todo reconcile with definition of stability given in Types.scala */ + def isStable(tp: Type): Boolean = tp match { + case TypeRef(pre, sym, _) => + sym.isPackageClass || + sym.isModuleClass && isStable(pre) /*|| + sym.isAliasType && isStable(tp.normalize)*/ + case _ => tp.isStable + } + + if (!isPlausiblyCompatible(info.tpe, pt) || !isStable(info.pre)) return SearchFailure + + val tvars = undetParams map freshVar + + // 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) + def fail(reason: String): SearchResult = { + if (settings.XlogImplicits.value) + inform(itree+" is not a valid implicit value for "+pt+" because:\n"+reason) + SearchFailure + } + try { + val itree1 = + if (isView) + typed1(Apply(itree, List(Ident("") setType pt0.paramTypes.head)), EXPRmode, pt0.resultType) + else + typed1(itree, EXPRmode, pt) + //if (settings.debug.value) println("typed implicit "+itree1+":"+itree1.tpe+", pt = "+pt) + 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) + def hasMatchingSymbol(tree: Tree): Boolean = (tree.symbol == info.sym) || { + tree match { + case Apply(fun, _) => hasMatchingSymbol(fun) + case TypeApply(fun, _) => hasMatchingSymbol(fun) + case Select(pre, name) => name == nme.apply && pre.symbol == info.sym + 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) + } else if (settings.XlogImplicits.value) + fail("candidate implicit "+info.sym+info.sym.locationString+ + " is shadowed by other implicit: "+itree1.symbol+itree1.symbol.locationString) + else SearchFailure + } catch { + case ex: TypeError => fail(ex.getMessage()) + } + } else { + SearchFailure + } + } + + /** Search list of implicit info lists for one matching prototype + * pt. If found return a search result with a tree from found implicit info + * which is typed with expected type pt. + * Otherwise return SearchFailure. + * + * @param implicitInfoss The given list of lists of implicit infos + * @param isLocal Is implicit definition visible without prefix? + * If this is the case then symbols in preceding lists shadow + * symbols of the same name in succeeding lists. + */ + def searchImplicit(implicitInfoss: List[List[ImplicitInfo]], isLocal: Boolean): SearchResult = { + + /** A set containing names that are shadowed by implicit infos */ + val shadowed = new HashSet[Name](8) + + /** Should implicit definition symbol `sym' be considered for applicability testing? + * This is the case if one of the following holds: + * - the symbol's type is initialized + * - the symbol comes from a classfile + * - the symbol comes from a different sourcefile than the current one + * - the symbol's definition comes before, and does not contain the closest enclosing definition, + * - the symbol's definition is a val, var, or def with an explicit result type + * The aim of this method is to prevent premature cyclic reference errors + * by computing the types of only those implicitis for which one of these + * conditions is true. + */ + def isValid(sym: Symbol) = { + def hasExplicitResultType(sym: Symbol) = { + def hasExplicitRT(tree: Tree) = tree match { + case ValDef(_, _, tpt, _) => !tpt.isEmpty + case DefDef(_, _, _, _, tpt, _) => !tpt.isEmpty + case _ => false + } + sym.rawInfo match { + case tc: TypeCompleter => hasExplicitRT(tc.tree) + case PolyType(_, tc: TypeCompleter) => hasExplicitRT(tc.tree) + case _ => true + } + } + def comesBefore(sym: Symbol, owner: Symbol) = + sym.pos.offset.getOrElse(0) < owner.pos.offset.getOrElse(Integer.MAX_VALUE) && + !(owner.ownerChain contains sym) + + sym.isInitialized || + sym.sourceFile == null || + (sym.sourceFile ne context.unit.source.file) || + hasExplicitResultType(sym) || + comesBefore(sym, context.owner) + } + + /** The implicits that are not valid because they come later in the source + * and lack an explicit result type. Used for error diagnostics only. + */ + val invalidImplicits = new ListBuffer[Symbol] + + /** Try implicit `info` to see whether it is applicable for expected type `pt`. + * This is the case if all of the following holds: + * - the info's type is not erroneous, + * - the info is not shadowed by another info with the same name, + * - if the symbol is Predef.identity, then we are not looking for a view, + * - the result of typedImplicit is non-empty. + * @return A search result with an attributed tree containing the implicit if succeeded, + * SearchFailure if not. + */ + def tryImplicit(info: ImplicitInfo): SearchResult = + if (!containsError(info.tpe) && + !(isLocal && shadowed.contains(info.name)) && + (!isView || info.sym != Predef_identity)) typedImplicit(info) + else SearchFailure + + /** Computes from a list of implicit infos a map which takes + * infos which are applicable for given expected type `pt` to their attributed trees. + * Computes invalid implicits as a side effect (used for better error message). + */ + def applicableInfos(is: List[ImplicitInfo]): Map[ImplicitInfo, SearchResult] = { + var applicable = Map[ImplicitInfo, SearchResult]() + for (i <- is) + if (!isValid(i.sym)) invalidImplicits += i.sym + else { + val result = tryImplicit(i) + if (result != SearchFailure) applicable += (i -> result) + } + if (isLocal) + for (i <- is) shadowed addEntry i.name + applicable + } + + /** A map which takes applicable infos to their attributed trees. */ + val applicable: Map[ImplicitInfo, SearchResult] = + (Map[ImplicitInfo, SearchResult]() /: (implicitInfoss map applicableInfos))(_ ++ _) + + if (applicable.isEmpty && !invalidImplicits.isEmpty) { + infer.setAddendum(tree.pos, () => + "\n Note: implicit "+invalidImplicits.first+" is not applicable here"+ + "\n because it comes after the application point and it lacks an explicit result type") + } + + /** A candidate for best applicable info wrt `improves` */ + val best = (NoImplicitInfo /: applicable.keySet) ( + (best, alt) => if (improves(alt, best)) alt else best) + if (best == NoImplicitInfo) SearchFailure + else { + /** The list of all applicable infos which are not improved upon by `best`. */ + val competing = applicable.keySet dropWhile (alt => best == alt || improves(best, alt)) + if (!competing.isEmpty) ambiguousImplicitError(best, competing.elements.next, "both", "and", "") // !!! streamline when new collection is there + + // Also check that applicable infos that did not get selected are not + // in (a companion object of) a subclass of (a companion object of) the class + // containing the winning info. + for (alt <- applicable.keySet) { + /** Is (the companion class of) `sym1` a subclass of (the compansion class of) `sym2`? */ + def isSubClassOrObject(sym1: Symbol, sym2: Symbol): Boolean = + sym1 != NoSymbol && (sym1 isSubClass sym2) || + sym1.isModuleClass && isSubClassOrObject(sym1.linkedClassOfClass, sym2) || + sym2.isModuleClass && isSubClassOrObject(sym1, sym2.linkedClassOfClass) + + if (alt.sym.owner != best.sym.owner && isSubClassOrObject(alt.sym.owner, best.sym.owner)) { + ambiguousImplicitError(best, alt, + "most specific definition is:", + "yet alternative definition ", + "is defined in a subclass.\n Both definitions ") + } + } + applicable(best) + } + } // end searchImplicit + + /** The implicits made available directly by class type `tp`. + * If `tp` refers to class C, these are all implicit members of the companion object of C. + */ + private def implicitsOfClass(tp: Type): List[ImplicitInfo] = tp match { + case TypeRef(pre, clazz, _) => + clazz.initialize.linkedClassOfClass.info.members.toList.filter(_.hasFlag(IMPLICIT)) map + (sym => new ImplicitInfo(sym.name, pre.memberType(clazz.linkedModuleOfClass), sym)) + case _ => + List() + } + + /** The implicits made available by type `pt`. + * These are all implicits found in companion objects of classes C + * such that some part of `tp` has C as one of its superclasses. + */ + private def implicitsOfExpectedType: List[List[ImplicitInfo]] = { + def getParts(tp: Type, s: collection.jcl.Set[Type]) { + tp match { + case TypeRef(pre, sym, args) if (!sym.isPackageClass) => + for (bc <- sym.info.baseClasses) + if (sym.isClass) s add (tp.baseType(bc)) + getParts(pre, s) + for (arg <- args) getParts(arg, s) + case ThisType(_) => + getParts(tp.widen, s) + case _: SingletonType => + getParts(tp.widen, s) + case RefinedType(ps, _) => + for (p <- ps) getParts(p, s) + case AnnotatedType(_, t, _) => + getParts(t, s) + case _ => + } + } + val tps = new collection.jcl.LinkedHashSet[Type] + getParts(pt, tps) + tps.elements.map(implicitsOfClass).toList + } + + /** The manifest corresponding to type `pt`, provided `pt` is an instance of Manifest. + */ + private def implicitManifest(pt: Type): Tree = pt match { + case TypeRef(_, ManifestClass, List(arg)) => + manifestOfType(arg) + case TypeRef(_, OptManifestClass, List(arg)) => + val itree = manifestOfType(arg) + if (itree == EmptyTree) gen.mkAttributedRef(NoManifest) else itree + case TypeRef(_, tsym, _) if (tsym.isAbstractType) => + implicitManifest(pt.bounds.lo) + case _ => + EmptyTree + } + + /** Creates a tree that calls the relevant factory method in object + * reflect.Manifest for type 'tp'. An EmptyTree is returned if + * no manifest is found. todo: make this instantiate take type params as well? + */ + private def manifestOfType(tp: Type): Tree = { + + /** Creates a tree that calls the factory method called constructor in object reflect.Manifest */ + def manifestFactoryCall(constructor: String, args: Tree*): Tree = + if (args contains EmptyTree) EmptyTree + else + typed(atPos(tree.pos) { + Apply( + TypeApply( + Select(gen.mkAttributedRef(ManifestModule), constructor), + List(TypeTree(tp)) + ), + args.toList + ) + }) + + /** Re-wraps a type in a manifest before calling inferImplicit on the result */ + def findManifest(tp: Type): Tree = + inferImplicit(tree, appliedType(ManifestClass.typeConstructor, List(tp)), true, context).tree + + tp.normalize match { + case ThisType(_) | SingleType(_, _) => + manifestFactoryCall("singleType", gen.mkAttributedQualifier(tp)) + case ConstantType(value) => + findManifest(tp.deconst) + case TypeRef(pre, sym, args) => + if (sym.isClass) { + val suffix = gen.mkClassOf(tp) :: (args map findManifest) + manifestFactoryCall( + "classType", + (if ((pre eq NoPrefix) || pre.typeSymbol.isStaticOwner) suffix + else findManifest(pre) :: suffix): _*) + } + else if (sym.isTypeParameterOrSkolem) { + EmptyTree // a manifest should have been found by normal searchImplicit + } + else { + manifestFactoryCall( + "abstractType", + findManifest(pre) :: Literal(sym.name.toString) :: findManifest(tp.bounds.hi) :: (args map findManifest): _*) + } + case RefinedType(parents, decls) => + // refinement is not generated yet + if (parents.length == 1) findManifest(parents.head) + else manifestFactoryCall("intersectionType", parents map findManifest: _*) + case _ => + EmptyTree + } + } + + /** The result of the implicit search: + * First search implicits visible in current context. + * If that fails, search implicits in expected type `pt`. + * If that fails, and `pt` is an instance of Manifest, try to construct a manifest. + * If all fails return SearchFailure + */ + var result = searchImplicit(context.implicitss, true) + if (result == SearchFailure) { + result = searchImplicit(implicitsOfExpectedType, false) + } + if (result == SearchFailure) { + val resultTree = implicitManifest(pt) + if (resultTree != EmptyTree) result = new SearchResult(resultTree, EmptyTreeTypeSubstituter) + } + if (util.Statistics.enabled) impltime += (currentTime - startTime) + result + } + + private val DivergentImplicit = new Exception() +} -- cgit v1.2.3