diff options
Diffstat (limited to 'src/reflect/scala/reflect')
7 files changed, 442 insertions, 55 deletions
diff --git a/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala b/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala index 3bcb793926..2c2ed351c9 100644 --- a/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala +++ b/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala @@ -19,6 +19,9 @@ trait ExistentialsAndSkolems { * can be deskolemized to the original type parameter. (A skolem is a * representation of a bound variable when viewed inside its scope.) * !!!Adriaan: this does not work for hk types. + * + * Skolems will be created at level 0, rather than the current value + * of `skolemizationLevel`. (See SI-7782) */ def deriveFreshSkolems(tparams: List[Symbol]): List[Symbol] = { class Deskolemizer extends LazyType { @@ -30,7 +33,11 @@ trait ExistentialsAndSkolems { sym setInfo sym.deSkolemize.info.substSym(typeParams, typeSkolems) } } - (new Deskolemizer).typeSkolems + + val saved = skolemizationLevel + skolemizationLevel = 0 + try new Deskolemizer().typeSkolems + finally skolemizationLevel = saved } def isRawParameter(sym: Symbol) = // is it a type parameter leaked by a raw type? diff --git a/src/reflect/scala/reflect/internal/HasFlags.scala b/src/reflect/scala/reflect/internal/HasFlags.scala index 4a3663b8ea..12fd3a31cd 100644 --- a/src/reflect/scala/reflect/internal/HasFlags.scala +++ b/src/reflect/scala/reflect/internal/HasFlags.scala @@ -115,6 +115,9 @@ trait HasFlags { def isSynthetic = hasFlag(SYNTHETIC) def isTrait = hasFlag(TRAIT) && !hasFlag(PARAM) + def isDeferredOrDefault = hasFlag(DEFERRED | DEFAULTMETHOD) + def isDeferredNotDefault = isDeferred && !hasFlag(DEFAULTMETHOD) + def flagBitsToString(bits: Long): String = { // Fast path for common case if (bits == 0L) "" else { diff --git a/src/reflect/scala/reflect/internal/StdNames.scala b/src/reflect/scala/reflect/internal/StdNames.scala index de7af4340d..c3b7f24a9d 100644 --- a/src/reflect/scala/reflect/internal/StdNames.scala +++ b/src/reflect/scala/reflect/internal/StdNames.scala @@ -44,6 +44,7 @@ trait StdNames { } } + private[reflect] def compactifyName(orig: String): String = compactify(orig) private final object compactify extends (String => String) { val md5 = MessageDigest.getInstance("MD5") diff --git a/src/reflect/scala/reflect/internal/SymbolTable.scala b/src/reflect/scala/reflect/internal/SymbolTable.scala index 5ccf81b4b5..6ca8900d7c 100644 --- a/src/reflect/scala/reflect/internal/SymbolTable.scala +++ b/src/reflect/scala/reflect/internal/SymbolTable.scala @@ -302,28 +302,21 @@ abstract class SymbolTable extends macros.Universe } object perRunCaches { - import java.lang.ref.WeakReference import scala.runtime.ScalaRunTime.stringOf import scala.collection.generic.Clearable // Weak references so the garbage collector will take care of // letting us know when a cache is really out of commission. - private val caches = mutable.HashSet[WeakReference[Clearable]]() + private val caches = WeakHashSet[Clearable]() def recordCache[T <: Clearable](cache: T): T = { - caches += new WeakReference(cache) + caches += cache cache } def clearAll() = { debuglog("Clearing " + caches.size + " caches.") - caches foreach { ref => - val cache = ref.get() - if (cache == null) - caches -= ref - else - cache.clear() - } + caches foreach (_.clear) } def newWeakMap[K, V]() = recordCache(mutable.WeakHashMap[K, V]()) diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index cd9f3d23c9..cfa6f927b5 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -3935,13 +3935,13 @@ trait Types extends api.Types { self: SymbolTable => // Hash consing -------------------------------------------------------------- private val initialUniquesCapacity = 4096 - private var uniques: util.HashSet[Type] = _ + private var uniques: util.WeakHashSet[Type] = _ private var uniqueRunId = NoRunId protected def unique[T <: Type](tp: T): T = { if (Statistics.canEnable) Statistics.incCounter(rawTypeCount) if (uniqueRunId != currentRunId) { - uniques = util.HashSet[Type]("uniques", initialUniquesCapacity) + uniques = util.WeakHashSet[Type](initialUniquesCapacity) perRunCaches.recordCache(uniques) uniqueRunId = currentRunId } diff --git a/src/reflect/scala/reflect/internal/util/WeakHashSet.scala b/src/reflect/scala/reflect/internal/util/WeakHashSet.scala index 9882aad5e5..fc12e31360 100644 --- a/src/reflect/scala/reflect/internal/util/WeakHashSet.scala +++ b/src/reflect/scala/reflect/internal/util/WeakHashSet.scala @@ -1,61 +1,430 @@ -package scala.reflect.internal.util +package scala +package reflect.internal.util -import scala.collection.mutable -import scala.collection.mutable.ArrayBuffer -import scala.collection.mutable.Builder -import scala.collection.mutable.SetBuilder +import java.lang.ref.{WeakReference, ReferenceQueue} +import scala.annotation.tailrec import scala.collection.generic.Clearable -import scala.runtime.AbstractFunction1 +import scala.collection.mutable.{Set => mSet} -/** A bare-bones implementation of a mutable `Set` that uses weak references - * to hold the elements. +/** + * A HashSet where the elements are stored weakly. Elements in this set are elligible for GC if no other + * hard references are associated with them. Its primary use case is as a canonical reference + * identity holder (aka "hash-consing") via findEntryOrUpdate * - * This implementation offers only add/remove/test operations, - * therefore it does not fulfill the contract of Scala collection sets. + * This Set implementation cannot hold null. Any attempt to put a null in it will result in a NullPointerException + * + * This set implmeentation is not in general thread safe without external concurrency control. However it behaves + * properly when GC concurrently collects elements in this set. */ -class WeakHashSet[T <: AnyRef] extends AbstractFunction1[T, Boolean] with Clearable { - private val underlying = mutable.HashSet[WeakReferenceWithEquals[T]]() +final class WeakHashSet[A <: AnyRef](val initialCapacity: Int, val loadFactor: Double) extends Set[A] with Function1[A, Boolean] with mSet[A] { + + import WeakHashSet._ + + def this() = this(initialCapacity = WeakHashSet.defaultInitialCapacity, loadFactor = WeakHashSet.defaultLoadFactor) + + type This = WeakHashSet[A] + + /** + * queue of Entries that hold elements scheduled for GC + * the removeStaleEntries() method works through the queue to remeove + * stale entries from the table + */ + private[this] val queue = new ReferenceQueue[A] + + /** + * the number of elements in this set + */ + private[this] var count = 0 + + /** + * from a specified initial capacity compute the capacity we'll use as being the next + * power of two equal to or greater than the specified initial capacity + */ + private def computeCapacity = { + if (initialCapacity < 0) throw new IllegalArgumentException("initial capacity cannot be less than 0"); + var candidate = 1 + while (candidate < initialCapacity) { + candidate *= 2 + } + candidate + } + + /** + * the underlying table of entries which is an array of Entry linked lists + */ + private[this] var table = new Array[Entry[A]](computeCapacity) + + /** + * the limit at which we'll increase the size of the hash table + */ + var threshhold = computeThreshHold + + private[this] def computeThreshHold: Int = (table.size * loadFactor).ceil.toInt - /** Add the given element to this set. */ - def +=(elem: T): this.type = { - underlying += new WeakReferenceWithEquals(elem) - this + /** + * find the bucket associated with an elements's hash code + */ + private[this] def bucketFor(hash: Int): Int = { + // spread the bits around to try to avoid accidental collisions using the + // same algorithm as java.util.HashMap + var h = hash + h ^= h >>> 20 ^ h >>> 12 + h ^= h >>> 7 ^ h >>> 4 + + // this is finding h % table.length, but takes advantage of the + // fact that table length is a power of 2, + // if you don't do bit flipping in your head, if table.length + // is binary 100000.. (with n 0s) then table.length - 1 + // is 1111.. with n 1's. + // In other words this masks on the last n bits in the hash + h & (table.length - 1) } - /** Remove the given element from this set. */ - def -=(elem: T): this.type = { - underlying -= new WeakReferenceWithEquals(elem) - this + /** + * remove a single entry from a linked list in a given bucket + */ + private[this] def remove(bucket: Int, prevEntry: Entry[A], entry: Entry[A]) { + prevEntry match { + case null => table(bucket) = entry.tail + case _ => prevEntry.tail = entry.tail + } + count -= 1 } - /** Does the given element belong to this set? */ - def contains(elem: T): Boolean = - underlying.contains(new WeakReferenceWithEquals(elem)) + /** + * remove entries associated with elements that have been gc'ed + */ + private[this] def removeStaleEntries() { + def poll(): Entry[A] = queue.poll().asInstanceOf[Entry[A]] - /** Does the given element belong to this set? */ - def apply(elem: T): Boolean = contains(elem) + @tailrec + def queueLoop { + val stale = poll() + if (stale != null) { + val bucket = bucketFor(stale.hash) - /** Return the number of elements in this set, including reclaimed elements. */ - def size = underlying.size + @tailrec + def linkedListLoop(prevEntry: Entry[A], entry: Entry[A]): Unit = if (stale eq entry) remove(bucket, prevEntry, entry) + else if (entry != null) linkedListLoop(entry, entry.tail) - /** Remove all elements in this set. */ - def clear() = underlying.clear() -} + linkedListLoop(null, table(bucket)) -/** A WeakReference implementation that implements equals and hashCode by - * delegating to the referent. - */ -class WeakReferenceWithEquals[T <: AnyRef](ref: T) { - def get(): T = underlying.get() + queueLoop + } + } + + queueLoop + } + + /** + * Double the size of the internal table + */ + private[this] def resize() { + val oldTable = table + table = new Array[Entry[A]](oldTable.size * 2) + threshhold = computeThreshHold + + @tailrec + def tableLoop(oldBucket: Int): Unit = if (oldBucket < oldTable.size) { + @tailrec + def linkedListLoop(entry: Entry[A]): Unit = entry match { + case null => () + case _ => { + val bucket = bucketFor(entry.hash) + val oldNext = entry.tail + entry.tail = table(bucket) + table(bucket) = entry + linkedListLoop(oldNext) + } + } + linkedListLoop(oldTable(oldBucket)) + + tableLoop(oldBucket + 1) + } + tableLoop(0) + } + + // from scala.reflect.internal.Set, find an element or null if it isn't contained + override def findEntry(elem: A): A = elem match { + case null => throw new NullPointerException("WeakHashSet cannot hold nulls") + case _ => { + removeStaleEntries() + val hash = elem.hashCode + val bucket = bucketFor(hash) + + @tailrec + def linkedListLoop(entry: Entry[A]): A = entry match { + case null => null.asInstanceOf[A] + case _ => { + val entryElem = entry.get + if (elem == entryElem) entryElem + else linkedListLoop(entry.tail) + } + } + + linkedListLoop(table(bucket)) + } + } + // add an element to this set unless it's already in there and return the element + def findEntryOrUpdate(elem: A): A = elem match { + case null => throw new NullPointerException("WeakHashSet cannot hold nulls") + case _ => { + removeStaleEntries() + val hash = elem.hashCode + val bucket = bucketFor(hash) + val oldHead = table(bucket) + + def add() = { + table(bucket) = new Entry(elem, hash, oldHead, queue) + count += 1 + if (count > threshhold) resize() + elem + } + + @tailrec + def linkedListLoop(entry: Entry[A]): A = entry match { + case null => add() + case _ => { + val entryElem = entry.get + if (elem == entryElem) entryElem + else linkedListLoop(entry.tail) + } + } + + linkedListLoop(oldHead) + } + } + + // add an element to this set unless it's already in there and return this set + override def +(elem: A): this.type = elem match { + case null => throw new NullPointerException("WeakHashSet cannot hold nulls") + case _ => { + removeStaleEntries() + val hash = elem.hashCode + val bucket = bucketFor(hash) + val oldHead = table(bucket) + + def add() { + table(bucket) = new Entry(elem, hash, oldHead, queue) + count += 1 + if (count > threshhold) resize() + } + + @tailrec + def linkedListLoop(entry: Entry[A]): Unit = entry match { + case null => add() + case _ if (elem == entry.get) => () + case _ => linkedListLoop(entry.tail) + } + + linkedListLoop(oldHead) + this + } + } + + def +=(elem: A) = this + elem + + // from scala.reflect.interanl.Set + override def addEntry(x: A) { this += x } + + // remove an element from this set and return this set + override def -(elem: A): this.type = elem match { + case null => this + case _ => { + removeStaleEntries() + val bucket = bucketFor(elem.hashCode) - override val hashCode = ref.hashCode - override def equals(other: Any): Boolean = other match { - case wf: WeakReferenceWithEquals[_] => - underlying.get() == wf.get() - case _ => - false + + @tailrec + def linkedListLoop(prevEntry: Entry[A], entry: Entry[A]): Unit = entry match { + case null => () + case _ if (elem == entry.get) => remove(bucket, prevEntry, entry) + case _ => linkedListLoop(entry, entry.tail) + } + + linkedListLoop(null, table(bucket)) + this + } } - private val underlying = new java.lang.ref.WeakReference(ref) + def -=(elem: A) = this - elem + + // empty this set + override def clear(): Unit = { + table = new Array[Entry[A]](table.size) + threshhold = computeThreshHold + count = 0 + + // drain the queue - doesn't do anything because we're throwing away all the values anyway + @tailrec def queueLoop(): Unit = if (queue.poll() != null) queueLoop() + queueLoop() + } + + // true if this set is empty + override def empty: This = new WeakHashSet[A](initialCapacity, loadFactor) + + // the number of elements in this set + override def size: Int = { + removeStaleEntries() + count + } + + override def apply(x: A): Boolean = this contains x + + override def foreach[U](f: A => U): Unit = iterator foreach f + + override def toList(): List[A] = iterator.toList + + // Iterator over all the elements in this set in no particular order + override def iterator: Iterator[A] = { + removeStaleEntries() + + new Iterator[A] { + + /** + * the bucket currently being examined. Initially it's set past the last bucket and will be decremented + */ + private[this] var currentBucket: Int = table.size + + /** + * the entry that was last examined + */ + private[this] var entry: Entry[A] = null + + /** + * the element that will be the result of the next call to next() + */ + private[this] var lookaheadelement: A = null.asInstanceOf[A] + + @tailrec + def hasNext: Boolean = { + while (entry == null && currentBucket > 0) { + currentBucket -= 1 + entry = table(currentBucket) + } + + if (entry == null) false + else { + lookaheadelement = entry.get + if (lookaheadelement == null) { + // element null means the weakref has been cleared since we last did a removeStaleEntries(), move to the next entry + entry = entry.tail + hasNext + } else { + true + } + } + } + + def next(): A = if (lookaheadelement == null) + throw new IndexOutOfBoundsException("next on an empty iterator") + else { + val result = lookaheadelement + lookaheadelement = null.asInstanceOf[A] + entry = entry.tail + result + } + } + } + + /** + * Diagnostic information about the internals of this set. Not normally + * needed by ordinary code, but may be useful for diagnosing performance problems + */ + private[util] class Diagnostics { + /** + * Verify that the internal structure of this hash set is fully consistent. + * Throws an assertion error on any problem. In order for it to be reliable + * the entries must be stable. If any are garbage collected during validation + * then an assertion may inappropriately fire. + */ + def fullyValidate { + var computedCount = 0 + var bucket = 0 + while (bucket < table.size) { + var entry = table(bucket) + while (entry != null) { + assert(entry.get != null, s"$entry had a null value indicated that gc activity was happening during diagnostic validation or that a null value was inserted") + computedCount += 1 + val cachedHash = entry.hash + val realHash = entry.get.hashCode + assert(cachedHash == realHash, s"for $entry cached hash was $cachedHash but should have been $realHash") + val computedBucket = bucketFor(realHash) + assert(computedBucket == bucket, s"for $entry the computed bucket was $computedBucket but should have been $bucket") + + entry = entry.tail + } + + bucket += 1 + } + + assert(computedCount == count, s"The computed count was $computedCount but should have been $count") + } + + /** + * Produces a diagnostic dump of the table that underlies this hash set. + */ + def dump = table.deep + + /** + * Number of buckets that hold collisions. Useful for diagnosing performance issues. + */ + def collisionBucketsCount: Int = + (table filter (entry => entry != null && entry.tail != null)).size + + /** + * Number of buckets that are occupied in this hash table. + */ + def fullBucketsCount: Int = + (table filter (entry => entry != null)).size + + /** + * Number of buckets in the table + */ + def bucketsCount: Int = table.size + + /** + * Number of buckets that don't hold anything + */ + def emptyBucketsCount = bucketsCount - fullBucketsCount + + /** + * Number of elements that are in collision. Useful for diagnosing performance issues. + */ + def collisionsCount = size - (fullBucketsCount - collisionBucketsCount) + + /** + * A map from a count of elements to the number of buckets with that count + */ + def elementCountDistribution = table map linkedListSize groupBy identity map {case (size, list) => (size, list.size)} + + private def linkedListSize(entry: Entry[A]) = { + var e = entry + var count = 0 + while (e != null) { + count += 1 + e = e.tail + } + count + } + } + + private[util] def diagnostics = new Diagnostics +} + +/** + * Companion object for WeakHashSet + */ +object WeakHashSet { + /** + * A single entry in a WeakHashSet. It's a WeakReference plus a cached hash code and + * a link to the next Entry in the same bucket + */ + private class Entry[A](element: A, val hash:Int, var tail: Entry[A], queue: ReferenceQueue[A]) extends WeakReference[A](element, queue) + + val defaultInitialCapacity = 16 + val defaultLoadFactor = .75 + + def apply[A <: AnyRef](initialCapacity: Int = WeakHashSet.defaultInitialCapacity, loadFactor: Double = WeakHashSet.defaultLoadFactor) = new WeakHashSet[A](initialCapacity, defaultLoadFactor) } diff --git a/src/reflect/scala/reflect/runtime/JavaMirrors.scala b/src/reflect/scala/reflect/runtime/JavaMirrors.scala index 22fe7f098c..6fdb238462 100644 --- a/src/reflect/scala/reflect/runtime/JavaMirrors.scala +++ b/src/reflect/scala/reflect/runtime/JavaMirrors.scala @@ -1178,6 +1178,17 @@ private[reflect] trait JavaMirrors extends internal.SymbolTable with api.JavaUni var fullNameOfJavaClass = ownerClazz.getName if (childOfClass || childOfTopLevel) fullNameOfJavaClass += "$" fullNameOfJavaClass += clazz.name + + // compactify (see SI-7779) + fullNameOfJavaClass = fullNameOfJavaClass match { + case PackageAndClassPattern(pack, clazzName) => + // in a package + pack + compactifyName(clazzName) + case _ => + // in the empty package + compactifyName(fullNameOfJavaClass) + } + if (clazz.isModuleClass) fullNameOfJavaClass += "$" // println(s"ownerChildren = ${ownerChildren.toList}") @@ -1187,6 +1198,8 @@ private[reflect] trait JavaMirrors extends internal.SymbolTable with api.JavaUni noClass } + private val PackageAndClassPattern = """(.*\.)(.*)$""".r + private def expandedName(sym: Symbol): String = if (sym.isPrivate) nme.expandedName(sym.name.toTermName, sym.owner).toString else sym.name.toString @@ -1241,6 +1254,7 @@ private[reflect] trait JavaMirrors extends internal.SymbolTable with api.JavaUni case TypeRef(_, ArrayClass, List(elemtpe)) => jArrayClass(typeToJavaClass(elemtpe)) case TypeRef(_, sym: ClassSymbol, _) => classToJava(sym.asClass) case tpe @ TypeRef(_, sym: AliasTypeSymbol, _) => typeToJavaClass(tpe.dealias) + case SingleType(_, sym: ModuleSymbol) => classToJava(sym.moduleClass.asClass) case _ => throw new NoClassDefFoundError("no Java class corresponding to "+tpe+" found") } } |