Resetting uniques and hashset reorg.

Uniques are now cleared after each run. Also, HashSets get a more standard API, without a label, but with configurable load factor.

5 files changed, 83 insertions, 59 deletions

diff --git a/src/dotty/tools/dotc/Compiler.scala b/src/dotty/tools/dotc/Compiler.scala
index f6723ddf4..38e3c8fd8 100644
--- a/src/dotty/tools/dotc/Compiler.scala
+++ b/src/dotty/tools/dotc/Compiler.scala
@@ -30,6 +30,8 @@ class Compiler {
     (start.withRunInfo(new RunInfo(start)) /: defn.RootImports)(addImport)
   }
 
-  def newRun(implicit ctx: Context): Run =
-    new Run(this)(rootContext)
+  def newRun(implicit ctx: Context): Run = {
+    try new Run(this)(rootContext)
+    finally ctx.base.reset()
+  }
 }
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index 859475cd5..cfaa3720f 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -422,7 +422,7 @@ object Contexts {
 
     // Types state
     /** A table for hash consing unique types */
-    private[core] val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) {
+    private[core] val uniques = new util.HashSet[Type](initialUniquesCapacity) {
       override def hash(x: Type): Int = x.hash
     }
 
@@ -435,11 +435,14 @@ object Contexts {
     /** A table for hash consing unique type bounds */
     private[core] val uniqueTypeBounds = new TypeBoundsUniques
 
-    private def uniqueMaps = List(uniques, uniqueRefinedTypes, uniqueNamedTypes, uniqueTypeBounds)
+    private def uniqueSets = Map(
+        "uniques" -> uniques,
+        "uniqueRefinedTypes" -> uniqueRefinedTypes,
+        "uniqueNamedTypes" -> uniqueNamedTypes,
+        "uniqueTypeBounds" -> uniqueTypeBounds)
 
     /** A map that associates label and size of all uniques sets */
-    def uniquesSize: Map[String, Int] =
-      uniqueMaps.map(m => m.label -> m.size).toMap
+    def uniquesSizes: Map[String, Int] = uniqueSets.mapValues(_.size)
 
     /** The number of recursive invocation of underlying on a NamedType
      *  during a controlled operation.
@@ -465,6 +468,10 @@ object Contexts {
 
     /** Should warnings and errors containing non-sensical strings be suppressed? */
     private[dotc] var suppressNonSensicalErrors = true
+
+    def reset() = {
+      for ((_, set) <- uniqueSets) set.clear()
+    }
   }
 
   object Context {
diff --git a/src/dotty/tools/dotc/core/Uniques.scala b/src/dotty/tools/dotc/core/Uniques.scala
index 9ad736c9c..5e5b3e225 100644
--- a/src/dotty/tools/dotc/core/Uniques.scala
+++ b/src/dotty/tools/dotc/core/Uniques.scala
@@ -39,7 +39,7 @@ object Uniques {
   )
  */
 
-  final class NamedTypeUniques extends HashSet[NamedType]("uniqueNamedTypes", initialUniquesCapacity) with Hashable {
+  final class NamedTypeUniques extends HashSet[NamedType](initialUniquesCapacity) with Hashable {
     override def hash(x: NamedType): Int = x.hash
 
     private def findPrevious(h: Int, prefix: Type, name: Name): NamedType = {
@@ -65,7 +65,7 @@ object Uniques {
     }
   }
 
-  final class TypeBoundsUniques extends HashSet[TypeBounds]("uniqueTypeBounds", initialUniquesCapacity) with Hashable {
+  final class TypeBoundsUniques extends HashSet[TypeBounds](initialUniquesCapacity) with Hashable {
     override def hash(x: TypeBounds): Int = x.hash
 
     private def findPrevious(h: Int, lo: Type, hi: Type, variance: Int): TypeBounds = {
@@ -92,7 +92,7 @@ object Uniques {
     }
   }
 
-  final class RefinedUniques extends HashSet[RefinedType]("uniqueRefinedTypes", initialUniquesCapacity) with Hashable {
+  final class RefinedUniques extends HashSet[RefinedType](initialUniquesCapacity) with Hashable {
     override val hashSeed = classOf[CachedRefinedType].hashCode // some types start life as CachedRefinedTypes, need to have same hash seed
     override def hash(x: RefinedType): Int = x.hash
 
diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala
index 44646e2ba..3c8ffa251 100644
--- a/src/dotty/tools/dotc/util/HashSet.scala
+++ b/src/dotty/tools/dotc/util/HashSet.scala
@@ -1,51 +1,57 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2012 LAMP/EPFL
- * @author  Martin Odersky
- */
-
 package dotty.tools.dotc.util
 
-object HashSet {
-  def apply[T >: Null <: AnyRef](): HashSet[T] = this(16)
-  def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16)
-  def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity)
-  def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] =
-    new HashSet[T](label, initialCapacity)
-}
-
-class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable {
-  private var used = 0
-  private var table = new Array[AnyRef](initialCapacity)
-  private def index(x: Int): Int = math.abs(x % table.length)
+/** A hash set that allows some priviliged protected access to its internals
+ */
+class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] with scala.collection.generic.Clearable {
+  private var used: Int = _
+  private var limit: Int = _
+  private var table: Array[AnyRef] = _
 
-  def hash(x: T): Int = x.hashCode
+  clear()
 
+  /** The number of elements in the set */
   def size: Int = used
+
+  private def allocate(size: Int) = {
+    table = new Array[AnyRef](size)
+    limit = (size * loadFactor).toInt
+  }
+
+  /** Remove all elements from this set and set back to initial configuration */
   def clear(): Unit = {
     used = 0
-    table = new Array[AnyRef](initialCapacity)
+    allocate(initialCapacity)
   }
 
+  /** Turn hashode `x` into a table index */
+  private def index(x: Int): Int = math.abs(x % table.length)
+
+  /** Hashcode, can be overridden */
+  def hash(x: T): Int = x.hashCode
+
+  /** Find entry such that `x equals entry`. If it exists, return it.
+   *  If not, enter `x` in set and return `x`.
+   */
   def findEntryOrUpdate(x: T): T = {
     var h = index(hash(x))
     var entry = table(h)
     while (entry ne null) {
-      if (x equals entry)
-        return entry.asInstanceOf[T]
-
+      if (x equals entry) return entry.asInstanceOf[T]
       h = index(h + 1)
       entry = table(h)
     }
     addEntryAt(h, x)
   }
 
-  private def addEntryAt(h: Int, x: T) = {
-    table(h) = x
+  /** Add entry at `x` at index `idx` */
+  private def addEntryAt(idx: Int, x: T) = {
+    table(idx) = x
     used += 1
-    if (used > (table.length >> 2)) growTable()
+    if (used > limit) growTable()
     x
   }
 
+  /** The entry in the set such that `x equals entry`, or else `null`. */
   def findEntry(x: T): T = {
     var h = index(hash(x))
     var entry = table(h)
@@ -58,23 +64,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
 
   private var rover: Int = -1
 
-  protected def findEntryByHash(hashCode: Int): T = {
-    rover = index(hashCode)
-    nextEntryByHash(hashCode)
-  }
-
-  protected def nextEntryByHash(hashCode: Int): T = {
-    var entry = table(rover)
-    while (entry ne null) {
-      rover = index(rover + 1)
-      if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T]
-      entry = table(rover)
-    }
-    null
-  }
-
-  protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x)
-
+  /** Add entry `x` to set */
   def addEntry(x: T): Unit = {
     var h = index(hash(x))
     var entry = table(h)
@@ -87,10 +77,13 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
     used += 1
     if (used > (table.length >> 2)) growTable()
   }
+
+  /** Add all entries in `xs` to set */
   def addEntries(xs: TraversableOnce[T]): Unit = {
     xs foreach addEntry
   }
 
+  /** The iterator of all elements in the set */
   def iterator = new Iterator[T] {
     private var i = 0
     def hasNext: Boolean = {
@@ -102,6 +95,32 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
       else null
   }
 
+  /** Privileged access: Find first entry with given hashcode */
+  protected def findEntryByHash(hashCode: Int): T = {
+    rover = index(hashCode)
+    nextEntryByHash(hashCode)
+  }
+
+  /** Privileged access: Find next entry with given hashcode. Needs to immediately
+   *  follow a `findEntryByhash` or `nextEntryByHash` operation.
+   */
+  protected def nextEntryByHash(hashCode: Int): T = {
+    var entry = table(rover)
+    while (entry ne null) {
+      rover = index(rover + 1)
+      if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T]
+      entry = table(rover)
+    }
+    null
+  }
+
+  /** Privileged access: Add entry `x` at the last position where an unsuccsessful
+   *  `findEntryByHash` or `nextEntryByhash` operation returned. Needs to immediately
+   *  follow a `findEntryByhash` or `nextEntryByHash` operation that was unsucessful,
+   *  i.e. that returned `null`.
+   */
+  protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x)
+
   private def addOldEntry(x: T): Unit = {
     var h = index(hash(x))
     var entry = table(h)
@@ -114,12 +133,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
 
   private def growTable(): Unit = {
     val oldtable = table
-    val growthFactor =
-      if (table.length <= initialCapacity) 8
-      else if (table.length <= (initialCapacity * 8)) 4
-      else 2
-
-    table = new Array[AnyRef](table.length * growthFactor)
+    allocate(table.length * 2)
     var i = 0
     while (i < oldtable.length) {
       val entry = oldtable(i)
@@ -127,5 +141,6 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
       i += 1
     }
   }
-  override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length)
+
+  override def toString() = "HashSet(%d / %d)".format(used, table.length)
 }
diff --git a/src/dotty/tools/dotc/util/Stats.scala b/src/dotty/tools/dotc/util/Stats.scala
index a535f203c..09dfd894d 100644
--- a/src/dotty/tools/dotc/util/Stats.scala
+++ b/src/dotty/tools/dotc/util/Stats.scala
@@ -63,7 +63,7 @@ object Stats {
         hb.continue = false
         println()
         println(hits.toList.sortBy(_._2).map{ case (x, y) => s"$x -> $y" } mkString "\n")
-        println(s"sizes: ${ctx.base.uniquesSize}")
+        println(s"sizes: ${ctx.base.uniquesSizes}")
       }
     } else op
   }