Lazy entering of names with internal $'s in package scopes

Names with internal $'s are entered in package scopes only if

  - we look for a name with internal $'s.
  - we want to know all the members of a package scope

 This optimization seems to be fairly effective. The typical range
 of package scopes that need $-names is between 0 and 20%. The optimization
seems to improve execution time of all unit tests by about 3%.

Also. drop the inheritance from Iterable to Scope. The reason
is that we now need a context parameter for toList and
other Iterable operations which makes them impossible to
fit into the Iterable framework.

13 files changed, 113 insertions, 66 deletions

diff --git a/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala b/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala
index a300857ec..8e054c9c2 100644
--- a/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala
+++ b/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala
@@ -794,7 +794,7 @@ class DottyBackendInterface(outputDirectory: AbstractFile, val superCallsMap: Ma
 
     def memberInfo(s: Symbol): Type = tp.memberInfo(s)
 
-    def decls: List[Symbol] = tp.decls.map(_.symbol).toList
+    def decls: List[Symbol] = tp.decls.toList
 
     def members: List[Symbol] =
       tp.memberDenots(takeAllFilter, (name, buf) => buf ++= tp.member(name).alternatives).map(_.symbol).toList
diff --git a/compiler/src/dotty/tools/dotc/core/Contexts.scala b/compiler/src/dotty/tools/dotc/core/Contexts.scala
index c80ad876a..b299de434 100644
--- a/compiler/src/dotty/tools/dotc/core/Contexts.scala
+++ b/compiler/src/dotty/tools/dotc/core/Contexts.scala
@@ -294,7 +294,7 @@ object Contexts {
 
     /** Is this a context that introduces a non-empty scope? */
     def isNonEmptyScopeContext: Boolean =
-      (this.scope ne outer.scope) && this.scope.nonEmpty
+      (this.scope ne outer.scope) && !this.scope.isEmpty
 
     /** Leave message in diagnostics buffer if it exists */
     def diagnose(str: => String) =
diff --git a/compiler/src/dotty/tools/dotc/core/Scopes.scala b/compiler/src/dotty/tools/dotc/core/Scopes.scala
index c256e7071..205798474 100644
--- a/compiler/src/dotty/tools/dotc/core/Scopes.scala
+++ b/compiler/src/dotty/tools/dotc/core/Scopes.scala
@@ -60,7 +60,7 @@ object Scopes {
    *  or to delete them. These methods are provided by subclass
    *  MutableScope.
    */
-  abstract class Scope extends DotClass with printing.Showable with Iterable[Symbol] {
+  abstract class Scope extends DotClass with printing.Showable {
 
     /** The last scope-entry from which all others are reachable via `prev` */
     private[dotc] def lastEntry: ScopeEntry
@@ -76,18 +76,37 @@ object Scopes {
     /** The symbols in this scope in the order they were entered;
      *  inherited from outer ones first.
      */
-    def toList: List[Symbol]
+    def toList(implicit ctx: Context): List[Symbol]
 
     /** Return all symbols as an iterator in the order they were entered in this scope.
      */
-    def iterator: Iterator[Symbol] = toList.iterator
+    def iterator(implicit ctx: Context): Iterator[Symbol] = toList.iterator
+
+    /** Is the scope empty? */
+    def isEmpty: Boolean = lastEntry eq null
+
+    def foreach[U](p: Symbol => U)(implicit ctx: Context): Unit = toList foreach p
+
+    def filter(p: Symbol => Boolean)(implicit ctx: Context): List[Symbol] = {
+      ensureComplete()
+      var syms: List[Symbol] = Nil
+      var e = lastEntry
+      while ((e ne null) && e.owner == this) {
+        val sym = e.sym
+        if (p(sym)) syms = sym :: syms
+        e = e.prev
+      }
+      syms
+    }
+
+    def find(p: Symbol => Boolean)(implicit ctx: Context): Symbol = filter(p) match {
+      case sym :: _ => sym
+      case _ => NoSymbol
+    }
 
     /** Returns a new mutable scope with the same content as this one. */
     def cloneScope(implicit ctx: Context): MutableScope
 
-    /** Is the scope empty? */
-    override def isEmpty: Boolean = lastEntry eq null
-
     /** Lookup a symbol entry matching given name. */
     def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry
 
@@ -144,6 +163,12 @@ object Scopes {
     final def toText(printer: Printer): Text = printer.toText(this)
 
     def checkConsistent()(implicit ctx: Context) = ()
+
+    /** Ensure that all elements of this scope have been entered.
+     *  Overridden by SymbolLoaders.PackageLoader#PackageScope, where it
+     *  makes sure that all names with `$`'s have been added.
+     */
+    protected def ensureComplete()(implicit ctx: Context): Unit = ()
   }
 
   /** A subclass of Scope that defines methods for entering and
@@ -341,8 +366,9 @@ object Scopes {
     /** Returns all symbols as a list in the order they were entered in this scope.
      *  Does _not_ include the elements of inherited scopes.
      */
-    override final def toList: List[Symbol] = {
+    override final def toList(implicit ctx: Context): List[Symbol] = {
       if (elemsCache eq null) {
+        ensureComplete()
         elemsCache = Nil
         var e = lastEntry
         while ((e ne null) && e.owner == this) {
@@ -354,6 +380,7 @@ object Scopes {
     }
 
     override def implicitDecls(implicit ctx: Context): List[TermRef] = {
+      ensureComplete()
       var irefs = new mutable.ListBuffer[TermRef]
       var e = lastEntry
       while (e ne null) {
@@ -368,25 +395,13 @@ object Scopes {
 
     /** Vanilla scope - symbols are stored in declaration order.
      */
-    final def sorted: List[Symbol] = toList
-
-    override def foreach[U](p: Symbol => U): Unit = toList foreach p
-
-    override def filter(p: Symbol => Boolean): List[Symbol] = {
-      var syms: List[Symbol] = Nil
-      var e = lastEntry
-      while ((e ne null) && e.owner == this) {
-        val sym = e.sym
-        if (p(sym)) syms = sym :: syms
-        e = e.prev
-      }
-      syms
-    }
+    final def sorted(implicit ctx: Context): List[Symbol] = toList
 
     override def openForMutations: MutableScope = this
 
     /** Check that all symbols in this scope are in their correct hashtable buckets. */
     override def checkConsistent()(implicit ctx: Context) = {
+      ensureComplete()
       var e = lastEntry
       while (e != null) {
         var e1 = lookupEntry(e.name)
@@ -425,7 +440,7 @@ object Scopes {
     override private[dotc] def lastEntry = null
     override def size = 0
     override def nestingLevel = 0
-    override def toList = Nil
+    override def toList(implicit ctx: Context) = Nil
     override def cloneScope(implicit ctx: Context): MutableScope = unsupported("cloneScope")
     override def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = null
     override def lookupNextEntry(entry: ScopeEntry)(implicit ctx: Context): ScopeEntry = null
diff --git a/compiler/src/dotty/tools/dotc/core/SymDenotations.scala b/compiler/src/dotty/tools/dotc/core/SymDenotations.scala
index b8cd7bb18..5a277cacb 100644
--- a/compiler/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/compiler/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -930,14 +930,15 @@ object SymDenotations {
       *  and which is also defined in the same scope and compilation unit.
       *  NoSymbol if this class does not exist.
       */
-    final def companionClass(implicit ctx: Context): Symbol = {
-      val companionMethod = info.decls.denotsNamed(nme.COMPANION_CLASS_METHOD, selectPrivate).first
-
-      if (companionMethod.exists)
-        companionMethod.info.resultType.classSymbol
-      else
-        NoSymbol
-    }
+    final def companionClass(implicit ctx: Context): Symbol =
+      if (is(Package)) NoSymbol
+      else {
+        val companionMethod = info.decls.denotsNamed(nme.COMPANION_CLASS_METHOD, selectPrivate).first
+        if (companionMethod.exists)
+          companionMethod.info.resultType.classSymbol
+        else
+          NoSymbol
+      }
 
     final def scalacLinkedClass(implicit ctx: Context): Symbol =
       if (this is ModuleClass) companionNamed(effectiveName.toTypeName)
@@ -1777,8 +1778,8 @@ object SymDenotations {
       def constrNamed(cname: TermName) = info.decls.denotsNamed(cname).last.symbol
         // denotsNamed returns Symbols in reverse order of occurrence
       if (this.is(ImplClass)) constrNamed(nme.TRAIT_CONSTRUCTOR) // ignore normal constructor
-      else
-        constrNamed(nme.CONSTRUCTOR).orElse(constrNamed(nme.TRAIT_CONSTRUCTOR))
+      else if (this.is(Package)) NoSymbol
+      else constrNamed(nme.CONSTRUCTOR).orElse(constrNamed(nme.TRAIT_CONSTRUCTOR))
     }
 
     /** The parameter accessors of this class. Term and type accessors,
diff --git a/compiler/src/dotty/tools/dotc/core/SymbolLoaders.scala b/compiler/src/dotty/tools/dotc/core/SymbolLoaders.scala
index 168908ced..e4d2d446f 100644
--- a/compiler/src/dotty/tools/dotc/core/SymbolLoaders.scala
+++ b/compiler/src/dotty/tools/dotc/core/SymbolLoaders.scala
@@ -14,6 +14,7 @@ import Contexts._, Symbols._, Flags._, SymDenotations._, Types._, Scopes._, util
 import StdNames._, NameOps._
 import Decorators.{PreNamedString, StringInterpolators}
 import classfile.ClassfileParser
+import util.Stats
 import scala.util.control.NonFatal
 
 object SymbolLoaders {
@@ -148,46 +149,79 @@ class SymbolLoaders {
     override def sourceModule(implicit ctx: Context) = _sourceModule
     def description = "package loader " + classpath.name
 
+    private var enterFlatClasses: Option[Context => Unit] = None
+
+    Stats.record("package scopes")
+
     /** The scope of a package. This is different from a normal scope
-	 *  in three aspects:
-	 *
-	 *   1. Names of scope entries are kept in mangled form.
-	 *   2. Some function types in the `scala` package are synthesized.
+  	 *  in three aspects:
+	   *
+	   *   1. Names of scope entries are kept in mangled form.
+	   *   2. Some function types in the `scala` package are synthesized.
   	 */
     final class PackageScope extends MutableScope {
       override def newScopeEntry(name: Name, sym: Symbol)(implicit ctx: Context): ScopeEntry =
         super.newScopeEntry(name.mangled, sym)
 
       override def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = {
-        val e = super.lookupEntry(name.mangled)
-        if (e == null &&
-            _sourceModule.name == nme.scala_ && _sourceModule == defn.ScalaPackageVal &&
-            name.isTypeName && name.isSyntheticFunction)
+        val mangled = name.mangled
+        val e = super.lookupEntry(mangled)
+        if (e != null) e
+        else if (_sourceModule.initialDenot.name == nme.scala_ && _sourceModule == defn.ScalaPackageVal &&
+                 name.isTypeName && name.isSyntheticFunction)
           newScopeEntry(defn.newFunctionNTrait(name.asTypeName))
+        else if (isFlatName(mangled.toSimpleName) && enterFlatClasses.isDefined) {
+          Stats.record("package scopes with flatnames entered")
+          enterFlatClasses.get(ctx)
+          lookupEntry(name)
+        }
         else e
       }
 
+      override def ensureComplete()(implicit ctx: Context) =
+        for (enter <- enterFlatClasses) enter(ctx)
+
       override def newScopeLikeThis() = new PackageScope
     }
 
     private[core] val currentDecls: MutableScope = new PackageScope()
 
+    def isFlatName(name: SimpleTermName) = name.lastIndexOf('$', name.length - 2) >= 0
+
+    def isFlatName(classRep: ClassPath#ClassRep) = {
+      val idx = classRep.name.indexOf('$')
+      idx >= 0 && idx < classRep.name.length - 1
+    }
+
+    def maybeModuleClass(classRep: ClassPath#ClassRep) = classRep.name.last == '$'
+
+    private def enterClasses(root: SymDenotation, flat: Boolean)(implicit ctx: Context) = {
+      def isAbsent(classRep: ClassPath#ClassRep) =
+        !root.unforcedDecls.lookup(classRep.name.toTypeName).exists
+
+      if (!root.isRoot) {
+        for (classRep <- classpath.classes)
+          if (!maybeModuleClass(classRep) && isFlatName(classRep) == flat &&
+            (!flat || isAbsent(classRep))) // on 2nd enter of flat names, check that the name has not been entered before
+            initializeFromClassPath(root.symbol, classRep)
+        for (classRep <- classpath.classes)
+          if (maybeModuleClass(classRep) && isFlatName(classRep) == flat &&
+              isAbsent(classRep))
+            initializeFromClassPath(root.symbol, classRep)
+      }
+    }
+
     def doComplete(root: SymDenotation)(implicit ctx: Context): Unit = {
       assert(root is PackageClass, root)
-      def maybeModuleClass(classRep: ClassPath#ClassRep) = classRep.name.last == '$'
       val pre = root.owner.thisType
       root.info = ClassInfo(pre, root.symbol.asClass, Nil, currentDecls, pre select sourceModule)
       if (!sourceModule.isCompleted)
         sourceModule.completer.complete(sourceModule)
-      if (!root.isRoot) {
-        for (classRep <- classpath.classes)
-          if (!maybeModuleClass(classRep))
-            initializeFromClassPath(root.symbol, classRep)
-        for (classRep <- classpath.classes)
-          if (maybeModuleClass(classRep) &&
-              !root.unforcedDecls.lookup(classRep.name.toTypeName).exists)
-            initializeFromClassPath(root.symbol, classRep)
+      enterFlatClasses = Some { ctx =>
+        enterFlatClasses = None
+        enterClasses(root, flat = true)(ctx)
       }
+      enterClasses(root, flat = false)
       if (!root.isEmptyPackage)
         for (pkg <- classpath.packages)
           enterPackage(root.symbol, pkg)
diff --git a/compiler/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala b/compiler/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
index f3bb99b27..1db3ebcb0 100644
--- a/compiler/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
+++ b/compiler/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
@@ -363,7 +363,7 @@ class Scala2Unpickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClas
       }
 
       def slowSearch(name: Name): Symbol =
-        owner.info.decls.find(_.name == name).getOrElse(NoSymbol)
+        owner.info.decls.find(_.name == name)
 
       def nestedObjectSymbol: Symbol = {
         // If the owner is overloaded (i.e. a method), it's not possible to select the
diff --git a/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala b/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala
index 87837fd82..20cd08426 100644
--- a/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala
+++ b/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala
@@ -237,7 +237,7 @@ object messages {
     val msg = {
       import core.Flags._
       val maxDist = 3
-      val decls = site.decls.flatMap { sym =>
+      val decls = site.decls.toList.flatMap { sym =>
         if (sym.flagsUNSAFE.is(Synthetic | PrivateOrLocal) || sym.isConstructor) Nil
         else List((sym.name.show, sym))
       }
diff --git a/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala b/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala
index db19bf6b6..5488d1979 100644
--- a/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala
+++ b/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala
@@ -214,7 +214,7 @@ private class ExtractAPICollector(implicit val ctx: Context) extends ThunkHolder
     // and can therefore be ignored.
     def alwaysPresent(s: Symbol) =
       s.isCompanionMethod || (csym.is(ModuleClass) && s.isConstructor)
-    val decls = cinfo.decls.filterNot(alwaysPresent).toList
+    val decls = cinfo.decls.filter(!alwaysPresent(_)).toList
     val apiDecls = apiDefinitions(decls)
 
     val declSet = decls.toSet
@@ -224,7 +224,7 @@ private class ExtractAPICollector(implicit val ctx: Context) extends ThunkHolder
       // We cannot filter out `LegacyApp` because it contains the main method,
       // see the comment about main class discovery in `computeType`.
       .filter(bc => !bc.is(Scala2x) || bc.eq(LegacyAppClass))
-      .flatMap(_.classInfo.decls.filterNot(s => s.is(Private) || declSet.contains(s)))
+      .flatMap(_.classInfo.decls.filter(s => !(s.is(Private) || declSet.contains(s))))
     // Inherited members need to be computed lazily because a class might contain
     // itself as an inherited member, like in `class A { class B extends A }`,
     // this works because of `classLikeCache`
diff --git a/compiler/src/dotty/tools/dotc/transform/ExplicitOuter.scala b/compiler/src/dotty/tools/dotc/transform/ExplicitOuter.scala
index c302aa61b..7ad7fb348 100644
--- a/compiler/src/dotty/tools/dotc/transform/ExplicitOuter.scala
+++ b/compiler/src/dotty/tools/dotc/transform/ExplicitOuter.scala
@@ -217,7 +217,7 @@ object ExplicitOuter {
   def outerAccessor(cls: ClassSymbol)(implicit ctx: Context): Symbol =
     if (cls.isStatic) NoSymbol // fast return to avoid scanning package decls
     else cls.info.member(outerAccName(cls)).suchThat(_ is OuterAccessor).symbol orElse
-      cls.info.decls.find(_ is OuterAccessor).getOrElse(NoSymbol)
+      cls.info.decls.find(_ is OuterAccessor)
 
   /** Class has an outer accessor. Can be called only after phase ExplicitOuter. */
   private def hasOuter(cls: ClassSymbol)(implicit ctx: Context): Boolean =
diff --git a/compiler/src/dotty/tools/dotc/transform/PrimitiveForwarders.scala b/compiler/src/dotty/tools/dotc/transform/PrimitiveForwarders.scala
index d752ce8e7..7c51ba593 100644
--- a/compiler/src/dotty/tools/dotc/transform/PrimitiveForwarders.scala
+++ b/compiler/src/dotty/tools/dotc/transform/PrimitiveForwarders.scala
@@ -43,7 +43,7 @@ class PrimitiveForwarders extends MiniPhaseTransform with IdentityDenotTransform
     import ops._
 
     def methodPrimitiveForwarders: List[Tree] =
-      for (meth <- mixins.flatMap(_.info.decls.flatMap(needsPrimitiveForwarderTo)).distinct)
+      for (meth <- mixins.flatMap(_.info.decls.toList.flatMap(needsPrimitiveForwarderTo)).distinct)
         yield polyDefDef(implementation(meth.asTerm), forwarder(meth))
 
     cpy.Template(impl)(body = methodPrimitiveForwarders ::: impl.body)
diff --git a/compiler/src/dotty/tools/dotc/transform/TreeChecker.scala b/compiler/src/dotty/tools/dotc/transform/TreeChecker.scala
index 44c26ecd9..eb7773ef3 100644
--- a/compiler/src/dotty/tools/dotc/transform/TreeChecker.scala
+++ b/compiler/src/dotty/tools/dotc/transform/TreeChecker.scala
@@ -391,11 +391,11 @@ class TreeChecker extends Phase with SymTransformer {
           !x.isCompanionMethod &&
           !x.isValueClassConvertMethod
 
-      val symbolsNotDefined = cls.classInfo.decls.toSet.filter(isNonMagicalMethod) -- impl.body.map(_.symbol) - constr.symbol
+      val symbolsNotDefined = cls.classInfo.decls.toList.toSet.filter(isNonMagicalMethod) -- impl.body.map(_.symbol) - constr.symbol
 
       assert(symbolsNotDefined.isEmpty,
           i" $cls tree does not define methods: ${symbolsNotDefined.toList}%, %\n" +
-          i"expected: ${cls.classInfo.decls.toSet.filter(isNonMagicalMethod).toList}%, %\n" +
+          i"expected: ${cls.classInfo.decls.toList.toSet.filter(isNonMagicalMethod)}%, %\n" +
           i"defined: ${impl.body.map(_.symbol)}%, %")
 
       super.typedClassDef(cdef, cls)
diff --git a/compiler/src/dotty/tools/dotc/transform/ValueClasses.scala b/compiler/src/dotty/tools/dotc/transform/ValueClasses.scala
index b398c2767..00d491486 100644
--- a/compiler/src/dotty/tools/dotc/transform/ValueClasses.scala
+++ b/compiler/src/dotty/tools/dotc/transform/ValueClasses.scala
@@ -28,13 +28,10 @@ object ValueClasses {
       !d.isSuperAccessor &&
       !d.is(Macro)
 
-  /** The member that of a derived value class that unboxes it. */
+  /** The member of a derived value class that unboxes it. */
   def valueClassUnbox(d: ClassDenotation)(implicit ctx: Context): Symbol =
     // (info.decl(nme.unbox)).orElse(...)      uncomment once we accept unbox methods
-    d.classInfo.decls
-      .find(d => d.isTerm && d.symbol.is(ParamAccessor))
-      .map(_.symbol)
-      .getOrElse(NoSymbol)
+    d.classInfo.decls.find(_.is(TermParamAccessor))
 
   /** For a value class `d`, this returns the synthetic cast from the underlying type to
    *  ErasedValueType defined in the companion module. This method is added to the module
diff --git a/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala b/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala
index ead4ad5cb..ec6fb1770 100644
--- a/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala
+++ b/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala
@@ -91,8 +91,8 @@ trait TypeAssigner {
                 else
                   parent
               }
-              val refinableDecls = info.decls.filterNot(
-                sym => sym.is(TypeParamAccessor | Private) || sym.isConstructor)
+              val refinableDecls = info.decls.filter(
+                sym => !(sym.is(TypeParamAccessor | Private) || sym.isConstructor))
               val fullType = (parentType /: refinableDecls)(addRefinement)
               mapOver(fullType)
             case TypeBounds(lo, hi) if variance > 0 =>