From 7ff290c43f9c25db803983f88bddff7dd7d84360 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 13 Jul 2009 10:38:37 +0000 Subject: Trying to make typechecker faster by (1) new su... Trying to make typechecker faster by (1) new subtyping (2) better implicit caches. Disallowed '42 as a symbol. Added cache method to Mutable Maps. Better complietion in interactive. --- src/compiler/scala/tools/nsc/Global.scala | 8 +- src/compiler/scala/tools/nsc/Settings.scala | 2 +- .../scala/tools/nsc/ast/parser/Scanners.scala | 3 +- .../scala/tools/nsc/backend/opt/Inliners.scala | 2 +- .../tools/nsc/interactive/CompilerControl.scala | 5 +- .../scala/tools/nsc/interactive/Global.scala | 4 +- src/compiler/scala/tools/nsc/symtab/Scopes.scala | 40 ++- src/compiler/scala/tools/nsc/symtab/Symbols.scala | 2 +- src/compiler/scala/tools/nsc/symtab/Types.scala | 323 ++++++++++++++++++--- .../tools/nsc/symtab/classfile/UnPickler.scala | 14 +- .../scala/tools/nsc/transform/AddInterfaces.scala | 2 +- .../scala/tools/nsc/transform/Erasure.scala | 8 +- .../scala/tools/nsc/typechecker/Analyzer.scala | 30 +- .../scala/tools/nsc/typechecker/Implicits.scala | 79 +++-- src/compiler/scala/tools/nsc/util/Statistics.scala | 72 +++-- .../collection/generic/MutableMapTemplate.scala | 9 + test/files/neg/badtok-1.check | 6 +- 17 files changed, 455 insertions(+), 154 deletions(-) diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 51a8495ece..c4ce109946 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -103,6 +103,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable val global: Global.this.type = Global.this } with Statistics + util.Statistics.enabled = settings.Ystatistics.value + /** Computing pairs of overriding/overridden symbols */ object overridingPairs extends { val global: Global.this.type = Global.this @@ -641,6 +643,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable */ class Run { + var isDefined = false + private val firstPhase = { // ----------- Initialization code ------------------------- curRunId += 1 @@ -731,6 +735,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable val mixinPhase = phaseNamed("mixin") val icodePhase = phaseNamed("icode") + isDefined = true + /** A test whether compilation should stop at phase with given name */ protected def stopPhase(name : String) = settings.stop.contains(name) @@ -800,7 +806,7 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable warning("It is not possible to check the result of the "+globalPhase.name+" phase") } } - if (settings.statistics.value) statistics.print(phase) + if (settings.Ystatistics.value) statistics.print(phase) advancePhase } diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index d098989906..8ef1ee0939 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -785,7 +785,7 @@ trait ScalacSettings { val skip = PhasesSetting ("-Yskip", "Skip") val Xsqueeze = ChoiceSetting ("-Ysqueeze", "if on, creates compact code in matching", List("on","off"), "on") . withHelpSyntax("-Ysqueeze:") - val statistics = BooleanSetting ("-Ystatistics", "Print compiler statistics") + val Ystatistics = BooleanSetting ("-Ystatistics", "Print compiler statistics") val stop = PhasesSetting ("-Ystop", "Stop after phase") val refinementMethodDispatch = ChoiceSetting ("-Ystruct-dispatch", "Selects dispatch method for structural refinement method calls", diff --git a/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala b/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala index 6c40c1f0a6..e29c055911 100755 --- a/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala @@ -3,7 +3,6 @@ * @author Martin Odersky */ // $Id: Scanners.scala 17285 2009-03-11 13:51:56Z rytz $ - package scala.tools.nsc.ast.parser import scala.tools.nsc.util._ @@ -329,7 +328,7 @@ trait Scanners { } case '\'' => nextChar() - if (isIdentifierStart(ch) || '0' <= ch && ch <= '9') + if (isIdentifierStart(ch)) charLitOr(getIdentRest) else if (isSpecial(ch)) charLitOr(getOperatorRest) diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 47a8410ae0..114054aaeb 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -277,7 +277,7 @@ abstract class Inliners extends SubComponent { val tfa = new analysis.MethodTFA(); - tfa.stat = settings.statistics.value + tfa.stat = settings.Ystatistics.value // how many times have we already inlined this method here? private val inlinedMethods: Map[Symbol, Int] = new HashMap[Symbol, Int] { diff --git a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala index c1e6747f8c..d264632bd5 100644 --- a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala +++ b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala @@ -18,7 +18,10 @@ trait CompilerControl { self: Global => /** Info given for every member found by completion */ - case class Member(val sym: Symbol, val tpe: Type, val accessible: Boolean, val inherited: Boolean, val viaView: Symbol) + case class Member(val sym: Symbol, val tpe: Type, val accessible: Boolean, val inherited: Boolean, val viaView: Symbol) { + def shadows(other: Member) = + sym.name == other.sym.name && (sym.tpe matches other.sym.tpe) + } /** The scheduler by which client and compiler communicate * Must be initialized before starting compilerRunner diff --git a/src/compiler/scala/tools/nsc/interactive/Global.scala b/src/compiler/scala/tools/nsc/interactive/Global.scala index ee8865dec5..51ba19951e 100755 --- a/src/compiler/scala/tools/nsc/interactive/Global.scala +++ b/src/compiler/scala/tools/nsc/interactive/Global.scala @@ -319,7 +319,9 @@ self => val decls = tree.tpe.decls.toList map (member(_, false)) val inherited = tree.tpe.members.toList diff decls map (member(_, true)) val implicits = applicableViews(tree, context) flatMap implicitMembers - decls ::: inherited ::: implicits + def isVisible(m: Member) = + !(decls exists (_.shadows(m))) && !(inherited exists (_.shadows(m))) + decls ::: inherited ::: (implicits filter isVisible) case None => throw new FatalError("no context found for "+pos) } diff --git a/src/compiler/scala/tools/nsc/symtab/Scopes.scala b/src/compiler/scala/tools/nsc/symtab/Scopes.scala index 3becf477b4..cbe514d775 100644 --- a/src/compiler/scala/tools/nsc/symtab/Scopes.scala +++ b/src/compiler/scala/tools/nsc/symtab/Scopes.scala @@ -60,7 +60,9 @@ trait Scopes { * @return ... */ def newScope(initElems: ScopeEntry): Scope = new NormalScope(initElems) + final def newScope: Scope = newScope(null: ScopeEntry) + trait PackageScopeDependMap { def createDepend(from : Symbol, name : Name) : Unit } @@ -306,22 +308,38 @@ trait Scopes { def lookupWithContext(name : Name)(from : Symbol) : Symbol = lookup(name) /** lookup a symbol entry matching given name. - * - * @param name ... - * @return ... + * @note from Martin: I believe this is a hotspot or will be one + * in future versions of the type system. I have reverted the previous + * change to use iterators as too costly. */ def lookupEntry(name: Name): ScopeEntry = { - val it = - if (hashtable != null) hashtableIterator(name.start & HASHMASK) - else entryIterator(elems) - - it find (_.sym.name == name) orNull + var e: ScopeEntry = null + if (hashtable ne null) { + e = hashtable(name.start & HASHMASK) + while ((e ne null) && e.sym.name != name) { + e = e.tail + } + } else { + e = elems + while ((e ne null) && e.sym.name != name) { + e = e.next + } + } + e } - /** lookup next entry with same name as this one */ + /** lookup next entry with same name as this one + * @note from Martin: I believe this is a hotspot or will be one + * in future versions of the type system. I have reverted the previous + * change to use iterators as too costly. + */ def lookupNextEntry(entry: ScopeEntry): ScopeEntry = { - val it = if (hashtable == null) entry.entryIterator else entry.bucketIterator - (it drop 1) find (_.sym.name == entry.sym.name) orNull + var e = entry + if (hashtable ne null) + do { e = e.tail } while ((e ne null) && e.sym.name != entry.sym.name) + else + do { e = e.next } while ((e ne null) && e.sym.name != entry.sym.name); + e } /** Return all symbols as a list in the order they were entered in this scope. diff --git a/src/compiler/scala/tools/nsc/symtab/Symbols.scala b/src/compiler/scala/tools/nsc/symtab/Symbols.scala index af6f45e095..d5608dd334 100644 --- a/src/compiler/scala/tools/nsc/symtab/Symbols.scala +++ b/src/compiler/scala/tools/nsc/symtab/Symbols.scala @@ -749,7 +749,7 @@ trait Symbols { /** Return info without checking for initialization or completing */ def rawInfo: Type = { var infos = this.infos - assert(infos != null, name) + assert(infos != null) val curPeriod = currentPeriod val curPid = phaseId(curPeriod) diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala index 1b3b93eb2c..9c5367b29d 100644 --- a/src/compiler/scala/tools/nsc/symtab/Types.scala +++ b/src/compiler/scala/tools/nsc/symtab/Types.scala @@ -8,7 +8,6 @@ package scala.tools.nsc.symtab import scala.collection.immutable import scala.collection.mutable.{ListBuffer, HashMap, WeakHashMap} -import scala.compat.Platform.currentTime import scala.tools.nsc.ast.TreeGen import scala.tools.nsc.util.{HashSet, Position, NoPosition} import Flags._ @@ -70,9 +69,10 @@ trait Types { var findMemberCount = 0 var noMemberCount = 0 var multMemberCount = 0 - var findMemberMillis = 0l + var findMemberNanos = 0l var subtypeCount = 0 - var subtypeMillis = 0l + var sametypeCount = 0 + var subtypeNanos = 0l private var explainSwitch = false @@ -511,14 +511,15 @@ trait Types { /** Is this type a subtype of that type? */ def <:<(that: Type): Boolean = { - if (util.Statistics.enabled) subtypeCount += 1 - val startTime = if (util.Statistics.enabled) currentTime else 0l +// val startTime = if (util.Statistics.enabled) System.nanoTime() else 0l val result = ((this eq that) || (if (explainSwitch) explain("<", isSubType, this, that) else isSubType(this, that, AnyDepth))) - if (util.Statistics.enabled) - subtypeMillis = subtypeMillis + currentTime - startTime +// if (util.Statistics.enabled) { +// subtypeNanos += System.nanoTime() - startTime +// subtypeCount += 1 +// } result } @@ -686,7 +687,7 @@ trait Types { if (!this.isGround) return typeVarToOriginMap(this).findMember(name, excludedFlags, requiredFlags, stableOnly)(from) if (util.Statistics.enabled) findMemberCount += 1 - val startTime = if (util.Statistics.enabled) currentTime else 0l +// val startTime = if (util.Statistics.enabled) System.nanoTime() else 0l //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG var members: Scope = null @@ -712,8 +713,7 @@ trait Types { sym.getFlag(PRIVATE | LOCAL) != (PRIVATE | LOCAL) || (bcs0.head.hasTransOwner(bcs.head)))) { if (name.isTypeName || stableOnly && sym.isStable) { - if (util.Statistics.enabled) - findMemberMillis = findMemberMillis + currentTime - startTime +// if (util.Statistics.enabled) findMemberNanos += System.nanoTime() - startTime return sym } else if (member == NoSymbol) { member = sym @@ -753,8 +753,7 @@ trait Types { } // while (!bcs.isEmpty) excluded = excludedFlags } // while (continue) - if (util.Statistics.enabled) - findMemberMillis = findMemberMillis + currentTime - startTime +// if (util.Statistics.enabled) findMemberNanos += System.nanoTime() - startTime if (members eq null) { if (util.Statistics.enabled) if (member == NoSymbol) noMemberCount += 1; member @@ -1491,29 +1490,34 @@ A type's typeSymbol should never be inspected directly. private var normalized: Type = null - override def normalize: Type = { - if (normalized == null) { - normalized = if (sym.isAliasType) { // beta-reduce - if (sym.info.typeParams.length == args.length || !isHigherKinded) { - /* !isHigherKinded && sym.info.typeParams.length != args.length only happens when compiling e.g., - `val x: Class' with -Xgenerics, while `type Class = java.lang.Class' had already been compiled without -Xgenerics */ - val xform = transform(sym.info.resultType) - assert(xform ne this, this) - xform.normalize // cycles have been checked in typeRef - } else PolyType(typeParams, transform(sym.info.resultType).normalize) // eta-expand - // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function* - } else if (isHigherKinded) { - // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function* - // @M: initialize needed (see test/files/pos/ticket0137.scala) - PolyType(typeParams, typeRef(pre, sym.initialize, higherKindedArgs)) - } else if (sym.isRefinementClass) { - sym.info.normalize // @MO to AM: OK? - } else { - super.normalize - } + def normalize0: Type = + if (sym.isAliasType) { // beta-reduce + if (sym.info.typeParams.length == args.length || !isHigherKinded) { + /* !isHigherKinded && sym.info.typeParams.length != args.length only happens when compiling e.g., + `val x: Class' with -Xgenerics, while `type Class = java.lang.Class' had already been compiled without -Xgenerics */ + val xform = transform(sym.info.resultType) + assert(xform ne this, this) + xform.normalize // cycles have been checked in typeRef + } else { + PolyType(typeParams, transform(sym.info.resultType).normalize) // eta-expand + // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function* + } + } else if (isHigherKinded) { + // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function* + // @M: initialize needed (see test/files/pos/ticket0137.scala) + PolyType(typeParams, typeRef(pre, sym.initialize, higherKindedArgs)) + } else if (sym.isRefinementClass) { + sym.info.normalize // @MO to AM: OK? + } else { + super.normalize + } + + override def normalize: Type = + if (phase.erasedTypes) normalize0 + else { + if (normalized == null) normalized = normalize0 + normalized } - normalized - } override def decls: Scope = { sym.info match { @@ -2325,7 +2329,7 @@ A type's typeSymbol should never be inspected directly. // Hash consing -------------------------------------------------------------- - private var uniques: HashSet[AnyRef] = _ + var uniques: HashSet[AnyRef] = _ private var uniqueRunId = NoRunId def uniqueTypeCount = uniques.size // for statistics @@ -2649,6 +2653,17 @@ A type's typeSymbol should never be inspected directly. eparams } + def isRaw(sym: Symbol, args: List[Type]) = + !phase.erasedTypes && !sym.typeParams.isEmpty && sym.hasFlag(JAVA) && args.isEmpty + // note: it's important to write the two first tests in this order, + // as only typeParams forces the classfile to be read. See #400 + + /** Is type tp a ``raw type''? */ + def isRawType(tp: Type) = tp match { + case TypeRef(_, sym, args) => isRaw(sym, args) + case _ => false + } + /** The raw to existential map converts a ``raw type'' to an existential type. * It is necessary because we might have read a raw type of a * parameterized Java class from a class file. At the time we read the type @@ -3446,6 +3461,7 @@ A type's typeSymbol should never be inspected directly. subsametypeRecursions += 1 val lastUndoLog = undoLog val result = isSameType0(tp1, tp2) + sametypeCount += 1 if (!result) undoTo(lastUndoLog) result } finally { @@ -3464,11 +3480,9 @@ A type's typeSymbol should never be inspected directly. if (subsametypeRecursions == 0) undoLog = List() } - def normalizePlus(tp: Type) = tp match { - case TypeRef(pre, sym, List()) if (sym.isInitialized && sym.hasFlag(JAVA) && !sym.typeParams.isEmpty) => - rawToExistential(tp) - case _ => tp.normalize - } + def normalizePlus(tp: Type) = + if (isRawType(tp)) rawToExistential(tp) + else tp.normalize /* todo: change to: @@ -3623,7 +3637,6 @@ A type's typeSymbol should never be inspected directly. if (subsametypeRecursions == 0) undoLog = List() } - /** Does this type have a prefix that begins with a type variable */ def beginsWithTypeVar(tp: Type): Boolean = tp match { case SingleType(pre, sym) => @@ -3645,9 +3658,235 @@ A type's typeSymbol should never be inspected directly. tp } + def isErrorOrWildcard(tp: Type) = (tp eq ErrorType) || (tp eq WildcardType) + + def isSingleType(tp: Type) = tp match { + case ThisType(_) | SuperType(_, _) | SingleType(_, _) => true + case _ => false + } + + def isConstantType(tp: Type) = tp match { + case ConstantType(_) => true + case _ => false + } + + def isHKSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = ( + tp1.typeSymbol == NothingClass + || + tp2.typeSymbol == AnyClass // @M Any and Nothing are super-type resp. subtype of every well-kinded type + || // @M! normalize reduces higher-kinded case to PolyType's + ((tp1.normalize, tp2.normalize) match { + case (PolyType(tparams1, res1), PolyType(tparams2, res2)) => + tparams1.length == tparams2.length && + List.forall2(tparams1, tparams2) ( + (p1, p2) => p2.info.substSym(tparams2, tparams1) <:< p1.info) && + res1 <:< res2.substSym(tparams2, tparams1) + + case (tp1a, tp2a) => + (isDifferentType(tp1a, tp1) || isDifferentType(tp2a, tp2)) && + isSubType(tp1a, tp2a, depth) + })) + + def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol]): Boolean = ( + tps1.isEmpty && tps2.isEmpty + || + !tps1.isEmpty && !tps2.isEmpty && + (tparams.head.isCovariant || (tps2.head <:< tps1.head)) && + (tparams.head.isContravariant || (tps1.head <:< tps2.head)) && + isSubArgs(tps1.tail, tps2.tail, tparams.tail) + ) + + def isSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = { + isSubType1(tp1, tp2, depth) + } + + def differentOrNone(tp1: Type, tp2: Type) = if (tp1 eq tp2) NoType else tp1 + + /** Does type `tp1' conform to `tp2'? + */ + private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = { + if (isErrorOrWildcard(tp1)) return true + if (isErrorOrWildcard(tp2)) return true + if (tp1 eq NoType) return false + if (tp2 eq NoType) return false + if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass + if (tp2 eq NoPrefix) return (tp1 eq NoPrefix) || tp1.typeSymbol.isPackageClass + if (isSingleType(tp1) && isSingleType(tp2) || + isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2 + if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType0(tp1, tp2, depth) + + /** First try, on the right: + * - unwrap Annotated types, BoundedWildcardTypes, + * - bind TypeVars on the right, if lhs is not Annotated nor BoundedWildcard + * - handle common cases for first-kind TypeRefs on both sides as a fast path. + */ + def firstTry = tp2 match { + // fast path: two typerefs, none of them HK + case tr2: TypeRef => + tp1 match { + case tr1: TypeRef => + val sym1 = tr1.sym + val sym2 = tr2.sym + val pre1 = tr1.pre + val pre2 = tr2.pre + ((if (sym1 == sym2) phase.erasedTypes || pre1 <:< pre2 + else (sym1.name == sym2.name && isUnifiable(pre1, pre2))) && + isSubArgs(tr1.args, tr2.args, sym1.typeParams) + || + sym2.isClass && { + val base = tr1 baseType sym2 + (base ne tr1) && base <:< tr2 + } + || + thirdTryRef(tr1, tr2)) + case _ => + secondTry + } + case AnnotatedType(_, _, _) => + tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2) + case BoundedWildcardType(bounds) => + tp1 <:< bounds.hi + case tv2 @ TypeVar(_, constr2) => + tp1 match { + case AnnotatedType(_, _, _) | BoundedWildcardType(_) => + secondTry + case _ => + if (constr2.inst != NoType) tp1 <:< constr2.inst + else isRelatable(tv2, tp1) && { constr2.lobounds = tp1 :: constr2.lobounds; true } + } + case _ => + secondTry + } + + /** Second try, on the left: + * - unwrap AnnotatedTypes, BoundedWildcardTypes, + * - bind typevars, + * - handle existential types by skolemization. + */ + def secondTry = tp1 match { + case AnnotatedType(_, _, _) => + tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2) + case BoundedWildcardType(bounds) => + tp1.bounds.lo <:< tp2 + case tv1 @ TypeVar(_, constr1) => + if (constr1.inst != NoType) constr1.inst <:< tp2 + else isRelatable(tv1, tp2) && { constr1.hibounds = tp2 :: constr1.hibounds; true } + case ExistentialType(_, _) => + try { + skolemizationLevel += 1 + tp1.skolemizeExistential(NoSymbol, null) <:< tp2 + } finally { + skolemizationLevel -= 1 + } + case _ => + thirdTry + } + + def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = { + val sym2 = tp2.sym + if (sym2.isAliasType) { + isSubType(tp1.normalize, tp2.normalize, depth) + } else if (sym2.isAbstractType) { + val tp2a = tp2.bounds.lo + isDifferentType(tp2, tp2a) && tp1 <:< tp2a || fourthTry + } else if (sym2 == NotNullClass) { + tp1.isNotNull + } else if (sym2 == SingletonClass) { + tp1.isStable + } else if (isRaw(sym2, tp2.args)) { + isSubType(tp1, rawToExistential(tp2), depth) + } else if (sym2.isRefinementClass) { + isSubType(tp1, sym2.info, depth) + } else { + fourthTry + } + } + + /** Third try, on the right: + * - decompose refined types. + * - handle typerefs, existentials, and notnull types. + * - handle left+right method types, polytypes, typebounds + */ + def thirdTry = tp2 match { + case tr2: TypeRef => + thirdTryRef(tp1, tr2) + case RefinedType(parents2, ref2) => + (parents2 forall (tp1 <:< _)) && + (ref2.toList forall tp1.specializes) + case et: ExistentialType => + et.withTypeVars(tp1 <:< _, depth) || fourthTry + case NotNullType(ntp2) => + tp1.isNotNull && tp1 <:< ntp2 + case MethodType(params2, res2) => + tp1 match { + case MethodType(params1, res1) => + (params1.length == params2.length && + matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isInstanceOf[JavaMethodType], tp2.isInstanceOf[JavaMethodType]) && + (res1 <:< res2) && + tp1.isInstanceOf[ImplicitMethodType] == tp2.isInstanceOf[ImplicitMethodType]) + case _ => + false + } + case PolyType(List(), res2) => + tp1 match { + case PolyType(List(), res1) => + // other polytypes were already checked in isHKSubType + res1 <:< res2 + case _ => + false + } + case TypeBounds(lo2, hi2) => + tp1 match { + case TypeBounds(lo1, hi1) => + lo2 <:< lo1 && hi1 <:< hi2 + case _ => + false + } + case _ => + fourthTry + } + + /** Fourth try, on the left: + * - handle typerefs, refined types, notnull and singleton types. + */ + def fourthTry = tp1 match { + case TypeRef(pre1, sym1, args1) => + if (sym1.isAliasType) { + isSubType(tp1.normalize, tp2.normalize, depth) + } else if (sym1.isAbstractType) { + val tp1a = tp1.bounds.hi + isDifferentType(tp1, tp1a) && tp1a <:< tp2 + } else if (sym1 == NothingClass) { + true + } else if (sym1 == NullClass) { + tp2 match { + case TypeRef(_, sym2, _) => + (sym2 isNonBottomSubClass ObjectClass) && + !(tp2.normalize.typeSymbol isNonBottomSubClass NotNullClass) + case _ => + isSingleType(tp2) && tp1 <:< tp2.widen + } + } else if (isRaw(sym1, args1)) { + isSubType(rawToExistential(tp1), tp2, depth) + } else if (sym1.isRefinementClass) { + isSubType(sym1.info, tp2, depth) + } else { + false + } + case RefinedType(parents1, ref1) => + parents1 exists (_ <:< tp2) + case _: SingletonType | _: NotNullType => + tp1.underlying <:< tp2 + case _ => + false + } + + firstTry + } + /** Does type `tp1' conform to `tp2'? */ - private def isSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = { + private def isSubType1(tp1: Type, tp2: Type, depth: Int): Boolean = { ((tp1, tp2) match { case (ErrorType, _) => true case (WildcardType, _) => true diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala b/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala index dbdb4e1ad7..8122177365 100644 --- a/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala +++ b/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala @@ -35,12 +35,18 @@ abstract class UnPickler { */ def unpickle(bytes: Array[Byte], offset: Int, classRoot: Symbol, moduleRoot: Symbol, filename: String) { try { - new UnPickle(bytes, offset, classRoot, moduleRoot, filename) + val p = if (currentRun.isDefined && + currentRun.picklerPhase != NoPhase && + phase.id > currentRun.picklerPhase.id) currentRun.picklerPhase + else phase + atPhase(p) { + new UnPickle(bytes, offset, classRoot, moduleRoot, filename) + } } catch { case ex: IOException => throw ex case ex: Throwable => - if (settings.debug.value) ex.printStackTrace() + /*if (settings.debug.value)*/ ex.printStackTrace() throw new RuntimeException("error reading Scala signature of "+filename+": "+ex.getMessage()) } } @@ -798,11 +804,13 @@ abstract class UnPickler { private class LazyTypeRef(i: Int) extends LazyType { private val definedAtRunId = currentRunId + private val p = phase // In IDE, captures class files dependencies so they can be reloaded when their dependencies change. private val ideHook = unpickleIDEHook override def complete(sym: Symbol) : Unit = { val tp = ideHook(at(i, readType)) - sym setInfo tp + if (p != phase) atPhase(p) (sym setInfo tp) + else sym setInfo tp if (currentRunId != definedAtRunId) sym.setInfo(adaptToNewRunMap(tp)) } override def load(sym: Symbol) { complete(sym) } diff --git a/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala b/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala index ccae9578b9..e95c8b69bd 100644 --- a/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala +++ b/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala @@ -154,7 +154,7 @@ abstract class AddInterfaces extends InfoTransform { override def complete(sym: Symbol) { def implType(tp: Type): Type = tp match { case ClassInfoType(parents, decls, _) => - assert(phase == implClassPhase, sym) + assert(phase == implClassPhase) ClassInfoType( ObjectClass.tpe :: (parents.tail map mixinToImplClass) ::: List(iface.tpe), implDecls(sym, decls), diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala index 19f1c737cc..747c1fb902 100644 --- a/src/compiler/scala/tools/nsc/transform/Erasure.scala +++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala @@ -1037,10 +1037,10 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast. case MyError(n,ex) => Console.println(tree1) throw MyError(n + 1, ex) - case ex : AssertionError => - Console.println(tree1) - throw MyError(0, ex) - case ex => throw ex +// case ex : AssertionError => +// Console.println(tree1) +// throw MyError(0, ex) +// case ex => throw ex } } } diff --git a/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala b/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala index f341dd0df9..16287bfc45 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala @@ -46,34 +46,10 @@ trait Analyzer extends AnyRef def newPhase(_prev: Phase): StdPhase = new StdPhase(_prev) { resetTyper() override def run { - val start = System.nanoTime() + val start = if (util.Statistics.enabled) System.nanoTime() else 0L currentRun.units foreach applyPhase - /* - typerTime += System.nanoTime() - start - def show(time: Long) = "%2.1f".format(time.toDouble / typerTime * 100)+" / "+time+"ns" - println("time spent typechecking: "+show(typerTime)) - println("time spent in implicits: "+show(implicitTime)) - println(" successful in scope: "+show(inscopeSucceed)) - println(" failed in scope: "+show(inscopeFail)) - println(" successful of type: "+show(oftypeSucceed)) - println(" failed of type: "+show(oftypeFail)) - println(" successful manifest: "+show(manifSucceed)) - println(" failed manifest: "+show(manifFail)) - println("implicit cache hitratio: "+"%2.1f".format(hits.toDouble / (hits + misses) * 100)) - println("time spent in failed : "+show(failedSilent)) - println(" failed op= : "+show(failedOpEqs)) - println(" failed applu : "+show(failedApplies)) - */ - typerTime = 0L - implicitTime = 0L - inscopeSucceed = 0L - inscopeFail = 0L - oftypeSucceed = 0L - oftypeFail = 0L - manifSucceed = 0L - manifFail = 0L - hits = 0 - misses = 0 + if (util.Statistics.enabled) + typerTime += System.nanoTime() - start } def apply(unit: CompilationUnit) { try { diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index 29c30bb285..d24f641fb4 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -10,8 +10,7 @@ //todo: treat :::= correctly package scala.tools.nsc.typechecker -import scala.collection.mutable.{HashMap, ListBuffer} -import scala.compat.Platform.currentTime +import scala.collection.mutable.{LinkedHashMap, ListBuffer} import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile} import symtab.Flags._ import util.HashSet @@ -38,6 +37,7 @@ self: Analyzer => var manifFail = 0L var hits = 0 var misses = 0 + var uncached = 0 /** Search for an implicit value. See the comment on `result` at the end of class `ImplicitSearch` * for more info how the search is conducted. @@ -60,8 +60,8 @@ self: Analyzer => result } - final val sizeLimit = 100 - val implicitsCache = new HashMap[Type, SearchResult] + final val sizeLimit = 50000 + val implicitsCache = new LinkedHashMap[AnyRef, SearchResult] def resetImplicits() { implicitsCache.clear() } @@ -210,7 +210,6 @@ self: Analyzer => } 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, @@ -639,6 +638,37 @@ self: Analyzer => } } + /** An extractor for types of the form ? { name: ? } + */ + object WildcardName { + def unapply(pt: Type): Option[Name] = pt match { + case RefinedType(List(WildcardType), decls) => + decls.toList match { + case List(sym) if (sym.tpe == WildcardType) => Some(sym.name) + case _ => None + } + case _ => + None + } + } + + /** Return cached search result if found. Otherwise update cache + * but keep within sizeLimit entries + */ + def cacheResult(key: AnyRef): SearchResult = implicitsCache get key match { + case Some(r) => + hits += 1 + r + case None => + misses += 1 + val r = searchImplicit(implicitsOfExpectedType, false) + //println("new fact: search implicit of "+key+" = "+r) + implicitsCache(key) = r + if (implicitsCache.size >= sizeLimit) + implicitsCache -= implicitsCache.keysIterator.next + r + } + /** The result of the implicit search: * First search implicits visible in current context. * If that fails, search implicits in expected type `pt`. @@ -646,40 +676,29 @@ self: Analyzer => * If all fails return SearchFailure */ def bestImplicit: SearchResult = { - //val start = System.nanoTime() + val start = System.nanoTime() var result = searchImplicit(context.implicitss, true) - //val timer1 = System.nanoTime() - //if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start + val timer1 = System.nanoTime() + if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start if (result == SearchFailure) { - if (pt.isInstanceOf[UniqueType]) - implicitsCache get pt match { - case Some(r) => - hits += 1 - result = r - case None => - misses += 1 - result = searchImplicit(implicitsOfExpectedType, false) - // println("new fact: search implicit of "+pt+" = "+result) - // if (implicitsCache.size >= sizeLimit) - // implicitsCache -= implicitsCache.values.next - implicitsCache(pt) = result - } - else - result = searchImplicit(implicitsOfExpectedType, false) + result = pt match { + case _: UniqueType => cacheResult(pt) + case WildcardName(name) => cacheResult(name) + case _ => uncached += 1; searchImplicit(implicitsOfExpectedType, false) + } } - //val timer2 = System.nanoTime() - //if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1 + + val timer2 = System.nanoTime() + if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1 if (result == SearchFailure) { val resultTree = implicitManifest(pt) if (resultTree != EmptyTree) result = new SearchResult(resultTree, EmptyTreeTypeSubstituter) } - //val timer3 = System.nanoTime() - //if (result == SearchFailure) manifFail += timer3 - timer2 else manifSucceed += timer3 - timer2 + val timer3 = System.nanoTime() + if (result == SearchFailure) manifFail += timer3 - timer2 else manifSucceed += timer3 - timer2 if (result == SearchFailure && settings.debug.value) println("no implicits found for "+pt+" "+pt.typeSymbol.info.baseClasses+" "+parts(pt)+implicitsOfExpectedType) - //implicitTime += System.nanoTime() - start - - if (util.Statistics.enabled) impltime += (currentTime - startTime) + implicitTime += System.nanoTime() - start result } diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala index 758760cd08..10a344911c 100644 --- a/src/compiler/scala/tools/nsc/util/Statistics.scala +++ b/src/compiler/scala/tools/nsc/util/Statistics.scala @@ -8,7 +8,7 @@ package scala.tools.nsc.util object Statistics { - final val enabled = false + var enabled = false } abstract class Statistics { @@ -16,30 +16,52 @@ abstract class Statistics { val global: Global import global._ + def showRelative(base: Long)(time: Long) = "%2.1f".format(time.toDouble / base * 100)+" / "+time+"ns" + def showRelTyper(time: Long) = showRelative(analyzer.typerTime)(time) + def print(phase: Phase) = { - inform("*** Cumulative statistics at phase " + phase) - inform("#tree nodes : " + nodeCount) - inform("#identifiers : " + analyzer.idcnt) - inform("#selections : " + analyzer.selcnt) - inform("#applications: " + analyzer.appcnt) - inform("#implicits : " + analyzer.implcnt) - inform("ms implicits : " + analyzer.impltime) - inform("#uniquetypes : " + uniqueTypeCount) - inform("#symbols : " + symbolCount) - inform("#type symbols: " + typeSymbolCount) - inform("#class symbols: " + classSymbolCount) - inform("#singleton closures: " + singletonBaseTypeSeqCount) - inform("#compound closures : " + compoundBaseTypeSeqCount) - inform("#typeref closures : " + typerefBaseTypeSeqCount) - inform("#findMember : " + findMemberCount) - inform("#notfound member: " + noMemberCount) - inform("#mulitple member: " + multMemberCount) - inform("time findMember: " + findMemberMillis) - inform("#norm meth : " + analyzer.normM) - inform("#norm poly : " + analyzer.normP) - inform("#norm other: " + analyzer.normO) - inform("#subtype : " + subtypeCount) - inform("ms subtype: " + subtypeMillis) - inform("ms type-flow-analysis: " + analysis.timer.millis) + if (List("typer", "erasure", "cleanup") contains phase.name) { + inform("*** Cumulative statistics at phase " + phase) + inform("#tree nodes : " + nodeCount) + inform("#identifiers : " + analyzer.idcnt) + inform("#selections : " + analyzer.selcnt) + inform("#applications: " + analyzer.appcnt) + inform("#implicits : " + analyzer.implcnt) + inform("#uniquetypes : " + uniqueTypeCount) + inform("#symbols : " + symbolCount) + inform("#type symbols: " + typeSymbolCount) + inform("#class symbols: " + classSymbolCount) + inform("#singleton closures: " + singletonBaseTypeSeqCount) + inform("#compound closures : " + compoundBaseTypeSeqCount) + inform("#typeref closures : " + typerefBaseTypeSeqCount) + inform("#findMember : " + findMemberCount) + inform("#notfound member: " + noMemberCount) + inform("#multiple member: " + multMemberCount) + inform("time findMember: " + findMemberNanos) + inform("#norm meth : " + analyzer.normM) + inform("#norm poly : " + analyzer.normP) + inform("#norm other : " + analyzer.normO) + inform("#subtype : " + subtypeCount) + inform("ns subtype : " + subtypeNanos) + inform("#sametype : " + sametypeCount) + inform("#unique types: " + uniques.size) + inform("ms type-flow-analysis: " + analysis.timer.millis) + if (phase.name == "typer") { + inform("time spent typechecking: "+showRelTyper(analyzer.typerTime)) + inform("time spent in implicits: "+showRelTyper(analyzer.implicitTime)) + inform(" successful in scope: "+showRelTyper(analyzer.inscopeSucceed)) + inform(" failed in scope: "+showRelTyper(analyzer.inscopeFail)) + inform(" successful of type: "+showRelTyper(analyzer.oftypeSucceed)) + inform(" failed of type: "+showRelTyper(analyzer.oftypeFail)) + inform(" successful manifest: "+showRelTyper(analyzer.manifSucceed)) + inform(" failed manifest: "+showRelTyper(analyzer.manifFail)) + inform("implicit cache hitratio: "+"%2.1f".format(analyzer.hits.toDouble / (analyzer.hits + analyzer.misses) * 100)) + inform("implicit cache coverage: "+"%2.1f".format((analyzer.hits + analyzer.misses).toDouble / (analyzer.uncached + analyzer.hits + analyzer.misses) * 100)) + inform("time spent in failed : "+showRelTyper(analyzer.failedSilent)) + inform(" failed op= : "+showRelTyper(analyzer.failedOpEqs)) + inform(" failed apply : "+showRelTyper(analyzer.failedApplies)) + } + //for (t <- uniques.iterator) println("unique: "+t) + } } } diff --git a/src/library/scala/collection/generic/MutableMapTemplate.scala b/src/library/scala/collection/generic/MutableMapTemplate.scala index 62ae9671c7..334fa937a4 100644 --- a/src/library/scala/collection/generic/MutableMapTemplate.scala +++ b/src/library/scala/collection/generic/MutableMapTemplate.scala @@ -96,6 +96,15 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta */ override def updated[B1 >: B](key: A, value: B1): mutable.Map[A, B1] = this + ((key, value)) + /** If given key is already in this map, returns associated value + * Otherwise, computes value from given expression `op`, stores with key + * in map and returns that value. + */ + def cached(key: A, op: => B) = get(key) match { + case Some(v) => v + case None => val v = op; update(key, v); v + } + /** Add a new key/value mapping and return the map itself. * * @param kv the key/value mapping to be added diff --git a/test/files/neg/badtok-1.check b/test/files/neg/badtok-1.check index 3bd93c47f5..b05bc60161 100644 --- a/test/files/neg/badtok-1.check +++ b/test/files/neg/badtok-1.check @@ -1,7 +1,7 @@ badtok-1.scala:2: error: unclosed character literal -'42' - ^ -badtok-1.scala:2: error: expected class or object definition '42' ^ +badtok-1.scala:2: error: unclosed character literal +'42' + ^ two errors found -- cgit v1.2.3