Eliminate some N^2 performance in type checking

Where N is the number of members of the enclosing package.

Double definition errors for top level classes/objects are issued
elsewhere, as demonstrated by the enclosed test. So we can
omit the call to `checkNoDoubleDefs` in this content.

We can't omit the call to `addSynthetics` for package
class owners (case- and value-class synthetic companions
are added here), but we can make the process cheaper by
moving the expensive-but-usually-true call to `shouldAdd`.

Here's an example of the improvement.

    % rm -rf /tmp/pkg; (for i in {1..50}; do for j in {1..100}; do echo "package pkg { class A_${i}_${j}___(val a: Int, val b: Int) }"; done; done) > sandbox/A1.scala && time scalac-hash v2.11.0 -Ybackend:GenASM -J-Xmx1G -J-XX:MaxPermSize=400M -d /tmp sandbox/A1.scala;

    real    0m49.762s
    user    1m12.376s
    sys 0m2.371s

    % rm -rf /tmp/pkg; (for i in {1..50}; do for j in {1..100}; do echo "package pkg { class A_${i}_${j}___(val a: Int, val b: Int) }"; done; done) > sandbox/A1.scala && time qbin/scalac -Ybackend:GenASM -J-Xmx1G -J-XX:MaxPermSize=400M -d /tmp sandbox/A1.scala;

    real    0m35.662s
    user    0m58.275s
    sys 0m2.355s

We've still got another source of pathological performance in
creating nested scopes that I'll fix in the next commit.

6 files changed, 24 insertions, 4 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 9fe693ce2a..66b1c2d87a 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -3022,7 +3022,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
         || (looker.hasAccessorFlag && !accessed.hasAccessorFlag && accessed.isPrivate)
       )
 
-      def checkNoDoubleDefs(stats: List[Tree]): Unit = {
+      def checkNoDoubleDefs: Unit = {
         val scope = if (inBlock) context.scope else context.owner.info.decls
         var e = scope.elems
         while ((e ne null) && e.owner == scope) {
@@ -3057,8 +3057,8 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
           //         the corresponding synthetics to the package class, only to the package object class.
           def shouldAdd(sym: Symbol) =
             inBlock || !context.isInPackageObject(sym, context.owner)
-          for (sym <- scope if shouldAdd(sym))
-            for (tree <- context.unit.synthetics get sym) {
+          for (sym <- scope)
+            for (tree <- context.unit.synthetics get sym if shouldAdd(sym)) { // OPT: shouldAdd is usually true. Call it here, rather than in the outer loop
               newStats += typedStat(tree) // might add even more synthetics to the scope
               context.unit.synthetics -= sym
             }
@@ -3104,7 +3104,10 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
       val stats1 = stats mapConserve typedStat
       if (phase.erasedTypes) stats1
       else {
-        checkNoDoubleDefs(stats1)
+        // As packages are open, it doesn't make sense to check double definitions here. Furthermore,
+        // it is expensive if the package is large. Instead, such double defininitions are checked in `Namers.enterInScope`
+        if (!context.owner.isPackageClass)
+          checkNoDoubleDefs
         addSynthetics(stats1)
       }
     }
diff --git a/test/files/neg/double-def-top-level.check b/test/files/neg/double-def-top-level.check
new file mode 100644
index 0000000000..85b16e81e5
--- /dev/null
+++ b/test/files/neg/double-def-top-level.check
@@ -0,0 +1,7 @@
+D_3.scala:1: error: C is already defined as class C
+class C
+      ^
+D_3.scala:2: error: O is already defined as object O
+object O
+       ^
+two errors found
diff --git a/test/files/neg/double-def-top-level/A_1.scala b/test/files/neg/double-def-top-level/A_1.scala
new file mode 100644
index 0000000000..c3d68d9d05
--- /dev/null
+++ b/test/files/neg/double-def-top-level/A_1.scala
@@ -0,0 +1,4 @@
+package p
+
+class C
+object O
diff --git a/test/files/neg/double-def-top-level/B_2.scala b/test/files/neg/double-def-top-level/B_2.scala
new file mode 100644
index 0000000000..c328e8c964
--- /dev/null
+++ b/test/files/neg/double-def-top-level/B_2.scala
@@ -0,0 +1,2 @@
+class C /* noerror */
+object O /* noerror */
\ No newline at end of file
diff --git a/test/files/neg/double-def-top-level/C_3.scala b/test/files/neg/double-def-top-level/C_3.scala
new file mode 100644
index 0000000000..e1c327c15a
--- /dev/null
+++ b/test/files/neg/double-def-top-level/C_3.scala
@@ -0,0 +1,2 @@
+class C
+object O
\ No newline at end of file
diff --git a/test/files/neg/double-def-top-level/D_3.scala b/test/files/neg/double-def-top-level/D_3.scala
new file mode 100644
index 0000000000..518e0d1c54
--- /dev/null
+++ b/test/files/neg/double-def-top-level/D_3.scala
@@ -0,0 +1,2 @@
+class C
+object O