From b7bdf048b1feb39b3e4f30cabfbc49a2cb535d28 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Tue, 19 Apr 2011 09:52:59 +0000 Subject: Trying to get build times down by refining impl... Trying to get build times down by refining implicit searches. Implicit infos associated with toplevel classes are cached now. Review by rompf. --- .../scala/tools/nsc/typechecker/Implicits.scala | 127 ++++++++++++++++++++- 1 file changed, 121 insertions(+), 6 deletions(-) (limited to '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 index 3fc8344d8d..647bbd01ab 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -65,12 +65,18 @@ trait Implicits { result } - final val sizeLimit = 50000 + private final val sizeLimit = 50000 private type Infos = List[ImplicitInfo] private type Infoss = List[List[ImplicitInfo]] - val implicitsCache = new LinkedHashMap[Type, Infoss] + private type InfoMap = LinkedHashMap[Symbol, List[ImplicitInfo]] + private val implicitsCache = new LinkedHashMap[Type, Infoss] + private val infoMapCache = new LinkedHashMap[Symbol, InfoMap] + + def resetImplicits() { + implicitsCache.clear() + infoMapCache.clear() + } - def resetImplicits() { implicitsCache.clear() } private val ManifestSymbols = Set(PartialManifestClass, FullManifestClass, OptManifestClass) /** The result of an implicit search @@ -745,6 +751,106 @@ trait Implicits { * can be accessed with unambiguous stable prefixes, the implicits infos * which are members of these companion objects. */ + private def companionImplicitMap(tp: Type): InfoMap = { + val infoMap = new InfoMap + val seen = mutable.HashSet[Type]() // cycle detection + + def getClassParts(tp: Type, infoMap: InfoMap, seen: mutable.Set[Type]) = tp match { + case TypeRef(pre, sym, args) => + infoMap get sym match { + case Some(infos1) => + if (infos1.nonEmpty && !(pre =:= infos1.head.pre.prefix)) { + println("amb prefix: "+pre+"#"+sym+" "+infos1.head.pre.prefix+"#"+sym) + infoMap(sym) = List() // ambiguous prefix - ignore implicit members + } + case None => + if (pre.isStable) { + val companion = sym.companionModule + companion.moduleClass match { + case mc: ModuleClassSymbol => + val infos = + for (im <- mc.implicitMembers) yield new ImplicitInfo(im.name, singleType(pre, companion), im) + if (infos.nonEmpty) + infoMap += (sym -> infos) + case _ => + } + } + val bts = tp.baseTypeSeq + var i = 1 + while (i < bts.length) { + getParts(bts(i), infoMap, seen) + i += 1 + } + getParts(pre, infoMap, seen) + } + } + + /** Enter all parts of `tp` into `parts` set. + * This method is performance critical: about 2-4% of all type checking is spent here + */ + def getParts(tp: Type, infoMap: InfoMap, seen: mutable.Set[Type]) { + if (seen(tp)) + return + seen += tp + tp match { + case TypeRef(pre, sym, args) => + if (sym.isClass) { + if (!((sym.name == tpnme.REFINE_CLASS_NAME) || + (sym.name startsWith tpnme.ANON_CLASS_NAME) || + (sym.name == tpnme.ROOT))) { + if (sym.isStatic) + infoMap ++= { + infoMapCache get sym match { + case Some(imap) => imap + case None => + infoMapCache(sym) = LinkedHashMap.empty // to break cycles + val result = new InfoMap + getClassParts(sym.tpe, result, new mutable.HashSet[Type]()) + infoMapCache(sym) = result + result + } + } + else + getClassParts(tp, infoMap, seen) + args foreach (getParts(_, infoMap, seen)) + } + } else if (sym.isAliasType) { + getParts(tp.normalize, infoMap, seen) + } else if (sym.isAbstractType) { + getParts(tp.bounds.hi, infoMap, seen) + } + case ThisType(_) => + getParts(tp.widen, infoMap, seen) + case _: SingletonType => + getParts(tp.widen, infoMap, seen) + case RefinedType(ps, _) => + for (p <- ps) getParts(p, infoMap, seen) + case AnnotatedType(_, t, _) => + getParts(t, infoMap, seen) + case ExistentialType(_, t) => + getParts(t, infoMap, seen) + case PolyType(_, t) => + getParts(t, infoMap, seen) + case _ => + } + } + + getParts(tp, infoMap, seen) + if (settings.verbose.value) + println("companion implicits of "+tp+" = "+infoMap) // DEBUG + infoMap + } + + /** The parts of a type is the smallest set of types that contains + * - the type itself + * - the parts of its immediate components (prefix and argument) + * - the parts of its base types + * - for alias types and abstract types, we take instead the parts + * - of their upper bounds. + * @return For those parts that refer to classes with companion objects that + * can be accessed with unambiguous stable prefixes, the implicits infos + * which are members of these companion objects. + private def companionImplicits(tp: Type): Infoss = { val partMap = new LinkedHashMap[Symbol, Type] val seen = mutable.HashSet[Type]() // cycle detection @@ -815,6 +921,8 @@ trait Implicits { buf.toList } +*/ + /** 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. @@ -826,12 +934,19 @@ trait Implicits { case None => incCounter(implicitCacheMisses) val start = startTimer(subtypeETNanos) - val implicitInfoss = companionImplicits(pt) +// val implicitInfoss = companionImplicits(pt) + val implicitInfoss1 = companionImplicitMap(pt).valuesIterator.toList +// val is1 = implicitInfoss.flatten.toSet +// val is2 = implicitInfoss1.flatten.toSet +// for (i <- is1) +// if (!(is2 contains i)) println("!!! implicit infos of "+pt+" differ, new does not contain "+i+",\nold: "+implicitInfoss+",\nnew: "+implicitInfoss1) +// for (i <- is2) +// if (!(is1 contains i)) println("!!! implicit infos of "+pt+" differ, old does not contain "+i+",\nold: "+implicitInfoss+",\nnew: "+implicitInfoss1) stopTimer(subtypeETNanos, start) - implicitsCache(pt) = implicitInfoss + implicitsCache(pt) = implicitInfoss1 if (implicitsCache.size >= sizeLimit) implicitsCache -= implicitsCache.keysIterator.next - implicitInfoss + implicitInfoss1 } /** Creates a tree that calls the relevant factory method in object -- cgit v1.2.3