diff options
Diffstat (limited to 'src/dotty/tools/dotc')
-rw-r--r-- | src/dotty/tools/dotc/core/Contexts.scala | 18 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Hashable.scala | 92 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/SymDenotations.scala | 2 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Symbols.scala | 6 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 174 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Uniques.scala | 124 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/Implicits.scala | 1 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/Inferencing.scala | 3 | ||||
-rw-r--r-- | src/dotty/tools/dotc/util/HashSet.scala | 23 | ||||
-rw-r--r-- | src/dotty/tools/dotc/util/Stats.scala | 2 |
10 files changed, 300 insertions, 145 deletions
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala index 8c2e0fbb3..d9116d2b6 100644 --- a/src/dotty/tools/dotc/core/Contexts.scala +++ b/src/dotty/tools/dotc/core/Contexts.scala @@ -10,6 +10,7 @@ import Types._ import Symbols._ import Scopes._ import NameOps._ +import Uniques._ import SymDenotations._ import util.Positions._ import ast.Trees._ @@ -427,7 +428,20 @@ object Contexts { override def hash(x: Type): Int = x.hash } - private[dotc] def uniquesSize = uniques.size + /** A table for hash consing unique refined types */ + private[core] val uniqueRefinedTypes = new RefinedUniques + + /** A table for hash consing unique named types */ + private[core] val uniqueNamedTypes = new NamedTypeUniques + + /** A table for hash consing unique type bounds */ + private[core] val uniqueTypeBounds = new TypeBoundsUniques + + private def uniqueMaps = List(uniques, uniqueRefinedTypes, uniqueNamedTypes, 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 /** The number of recursive invocation of underlying on a NamedType * during a controlled operation. @@ -475,7 +489,7 @@ object Contexts { private final val InitialSuperIdsSize = 4096 /** Initial capacity of uniques HashMap */ - private[core] final val initialUniquesCapacity = 50000 + private[core] final val initialUniquesCapacity = 40000 /** How many recursive calls to NamedType#underlying are performed before * logging starts. diff --git a/src/dotty/tools/dotc/core/Hashable.scala b/src/dotty/tools/dotc/core/Hashable.scala new file mode 100644 index 000000000..2f55ef70a --- /dev/null +++ b/src/dotty/tools/dotc/core/Hashable.scala @@ -0,0 +1,92 @@ +package dotty.tools.dotc +package core + +import Types._ +import scala.util.hashing.{ MurmurHash3 => hashing } + +object Hashable { + + /** A hash value indicating that the underlying type is not + * cached in uniques. + */ + final val NotCached = 0 + + /** An alternative value returned from `hash` if the + * computed hashCode would be `NotCached`. + */ + private[core] final val NotCachedAlt = Int.MinValue + + /** A value that indicates that the hash code is unknown + */ + private[core] final val HashUnknown = 1234 + + /** An alternative value if computeHash would otherwise yield HashUnknown + */ + private[core] final val HashUnknownAlt = 4321 +} + +trait Hashable { + import Hashable._ + + protected def hashSeed: Int = getClass.hashCode + + private def finishHash(hashCode: Int, arity: Int): Int = + avoidNotCached(hashing.finalizeHash(hashCode, arity)) + + protected final def identityHash = avoidNotCached(System.identityHashCode(this)) + + protected final def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h + + private def finishHash(seed: Int, arity: Int, tp: Type): Int = { + val elemHash = tp.hash + if (elemHash == NotCached) return NotCached + finishHash(hashing.mix(seed, elemHash), arity + 1) + } + + private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = { + val elemHash = tp1.hash + if (elemHash == NotCached) return NotCached + finishHash(hashing.mix(seed, elemHash), arity + 1, tp2) + } + + private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = { + var h = seed + var xs = tps + var len = arity + while (xs.nonEmpty) { + val elemHash = xs.head.hash + if (elemHash == NotCached) return NotCached + h = hashing.mix(h, elemHash) + xs = xs.tail + len += 1 + } + finishHash(h, len) + } + + private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = { + val elemHash = tp.hash + if (elemHash == NotCached) return NotCached + finishHash(hashing.mix(seed, elemHash), arity + 1, tps) + } + + protected final def doHash(x: Any): Int = + finishHash(hashing.mix(hashSeed, x.hashCode), 1) + + protected final def doHash(tp: Type): Int = + finishHash(hashSeed, 0, tp) + + protected final def doHash(x1: Any, tp2: Type): Int = + finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2) + + protected final def doHash(tp1: Type, tp2: Type): Int = + finishHash(hashSeed, 0, tp1, tp2) + + protected final def doHash(x1: Any, tp2: Type, tp3: Type): Int = + finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3) + + protected final def doHash(tp1: Type, tps2: List[Type]): Int = + finishHash(hashSeed, 0, tp1, tps2) + + protected final def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int = + finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3) +} diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala index 886024325..5278a08d2 100644 --- a/src/dotty/tools/dotc/core/SymDenotations.scala +++ b/src/dotty/tools/dotc/core/SymDenotations.scala @@ -730,7 +730,7 @@ object SymDenotations { // ----- denotation fields and accessors ------------------------------ - if (initFlags is (Module, butNot = Package)) assert(name.isModuleClassName, this) + if (initFlags is (Module, butNot = Package)) assert(name.isModuleClassName) /** The symbol asserted to have type ClassSymbol */ def classSymbol: ClassSymbol = symbol.asInstanceOf[ClassSymbol] diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala index b454add44..53cb38b48 100644 --- a/src/dotty/tools/dotc/core/Symbols.scala +++ b/src/dotty/tools/dotc/core/Symbols.scala @@ -338,8 +338,8 @@ object Symbols { final def isType(implicit ctx: Context): Boolean = denot.isType final def isClass: Boolean = isInstanceOf[ClassSymbol] - final def asTerm(implicit ctx: Context): TermSymbol = { assert(isTerm, this); asInstanceOf[TermSymbol] } - final def asType(implicit ctx: Context): TypeSymbol = { assert(isType, this); asInstanceOf[TypeSymbol] } + final def asTerm(implicit ctx: Context): TermSymbol = { assert(isTerm); asInstanceOf[TermSymbol] } + final def asType(implicit ctx: Context): TypeSymbol = { assert(isType); asInstanceOf[TypeSymbol] } final def asClass: ClassSymbol = asInstanceOf[ClassSymbol] /** A unique, densely packed integer tag for each class symbol, -1 @@ -350,7 +350,7 @@ object Symbols { /** This symbol entered into owner's scope (owner must be a class). */ final def entered(implicit ctx: Context): this.type = { - assert(this.owner.isClass, this.owner.denot) // !!! DEBUG + assert(this.owner.isClass) // !!! DEBUG this.owner.asClass.enter(this) if (this is Module) this.owner.asClass.enter(this.moduleClass) this diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 0cda02a6e..38ed09ebd 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1,7 +1,6 @@ package dotty.tools.dotc package core -import util.HashSet import util.common._ import Symbols._ import Flags._ @@ -22,7 +21,8 @@ import ast.tpd._, printing.Texts._ import ast.untpd import transform.Erasure import printing.Printer -import scala.util.hashing.{ MurmurHash3 => hashing } +import Hashable._ +import Uniques._ import collection.{mutable, Seq, breakOut} import config.Config import config.Printers._ @@ -30,24 +30,6 @@ import language.implicitConversions object Types { - /** A hash value indicating that the underlying type is not - * cached in uniques. - */ - final val NotCached = 0 - - /** An alternative value returned from `hash` if the - * computed hashCode would be `NotCached`. - */ - private final val NotCachedAlt = Int.MinValue - - /** A value that indicates that the hash code is unknown - */ - private final val HashUnknown = 1234 - - /** An alternative value if computeHash would otherwise yield HashUnknown - */ - private final val HashUnknownAlt = 4321 - /** The class of types. * The principal subclasses and sub-objects are as follows: * @@ -79,7 +61,7 @@ object Types { * +- ErrorType * +- WildcardType */ - abstract class Type extends DotClass with printing.Showable { + abstract class Type extends DotClass with Hashable with printing.Showable { // ----- Tests ----------------------------------------------------- @@ -880,105 +862,20 @@ object Types { } } new Simplify().apply(this) - } - -// ----- hashing ------------------------------------------------------ + } /** customized hash code of this type. * NotCached for uncached types. Cached types * compute hash and use it as the type's hashCode. */ def hash: Int - - protected def hashSeed = getClass.hashCode - - private def finishHash(hashCode: Int, arity: Int): Int = - avoidNotCached(hashing.finalizeHash(hashCode, arity)) - - protected def identityHash = avoidNotCached(System.identityHashCode(this)) - - protected def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h - - private def finishHash(seed: Int, arity: Int, tp: Type): Int = { - val elemHash = tp.hash - if (elemHash == NotCached) return NotCached - finishHash(hashing.mix(seed, elemHash), arity + 1) - } - - private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = { - val elemHash = tp1.hash - if (elemHash == NotCached) return NotCached - finishHash(hashing.mix(seed, elemHash), arity + 1, tp2) - } - - private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = { - var h = seed - var xs = tps - var len = arity - while (xs.nonEmpty) { - val elemHash = xs.head.hash - if (elemHash == NotCached) return NotCached - h = hashing.mix(h, elemHash) - xs = xs.tail - len += 1 - } - finishHash(h, len) - } - - private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = { - val elemHash = tp.hash - if (elemHash == NotCached) return NotCached - finishHash(hashing.mix(seed, elemHash), arity + 1, tps) - } - - protected def doHash(x: Any): Int = - finishHash(hashing.mix(hashSeed, x.hashCode), 1) - - protected def doHash(tp: Type): Int = - finishHash(hashSeed, 0, tp) - - protected def doHash(x1: Any, tp2: Type): Int = - finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2) - - protected def doHash(tp1: Type, tp2: Type): Int = - finishHash(hashSeed, 0, tp1, tp2) - - protected def doHash(x1: Any, tp2: Type, tp3: Type): Int = - finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3) - - protected def doHash(tp1: Type, tps2: List[Type]): Int = - finishHash(hashSeed, 0, tp1, tps2) - - protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int = - finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3) - } // end Type +// ----- Type categories ---------------------------------------------- + /** A marker trait for cached types */ trait CachedType extends Type - def unique[T <: Type](tp: T)(implicit ctx: Context): T = { - if (monitored) - if (tp.hash == NotCached) { - record("uncached-types") - record(s"uncached: ${tp.getClass}") - } else { - record("cached-types") - record(s"cached: ${tp.getClass}") - } - if (tp.hash == NotCached) tp - else ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T] - } /* !!! DEBUG - ensuring ( - result => tp.toString == result.toString || { - println(s"cache mismatch; tp = $tp, cached = $result") - false - } - ) - */ - -// ----- Type categories ---------------------------------------------- - /** A marker trait for type proxies. * Each implementation is expected to redefine the `underlying` method. */ @@ -1009,7 +906,7 @@ object Types { /** Instances of this class are cached and are proxies. */ abstract class CachedProxyType extends TypeProxy with CachedType { - private[this] var myHash = HashUnknown + protected[this] var myHash = HashUnknown final def hash = { if (myHash == HashUnknown) { myHash = computeHash @@ -1076,8 +973,7 @@ object Types { val prefix: Type val name: Name - assert(prefix.isValueType || - (prefix eq NoPrefix), s"bad prefix in $prefix.$name") + assert(prefix.isValueType || (prefix eq NoPrefix)) private[this] var lastDenotationOrSym: AnyRef = null @@ -1194,7 +1090,6 @@ object Types { case _ => false } - override def computeHash = doHash(name, prefix) } abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType { @@ -1251,12 +1146,16 @@ object Types { override def computeHash = doHash(fixedSym) } - final class CachedTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name) { + final class CachedTermRef(prefix: Type, name: TermName, hc: Int) extends TermRef(prefix, name) { assert(prefix ne NoPrefix) + myHash = hc + override def computeHash = unsupported("computeHash") } - final class CachedTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name) { + final class CachedTypeRef(prefix: Type, name: TypeName, hc: Int) extends TypeRef(prefix, name) { assert(prefix ne NoPrefix) + myHash = hc + override def computeHash = unsupported("computeHash") } final class NoPrefixTermRef(name: TermName, val fixedSym: TermSymbol) extends TermRef(NoPrefix, name) with WithNoPrefix @@ -1273,7 +1172,7 @@ object Types { object TermRef { def apply(prefix: Type, name: TermName)(implicit ctx: Context): TermRef = - unique(new CachedTermRef(prefix, name)) + ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TermRef] def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef = if (prefix eq NoPrefix) unique(new NoPrefixTermRef(sym.name, sym)) else apply(prefix, sym.name) withSym sym @@ -1288,7 +1187,7 @@ object Types { object TypeRef { def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef = - unique(new CachedTypeRef(prefix, name)) + ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TypeRef] def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef = if (prefix eq NoPrefix) unique(new NoPrefixTypeRef(sym.name, sym)) else apply(prefix, sym.name) withSym sym @@ -1400,19 +1299,22 @@ object Types { val refinedInfo = infoFn(this) } - class DirectRefinedType(parent: Type, refinedName: Name, override val refinedInfo: Type) extends RefinedType(parent, refinedName) + class PreHashedRefinedType(parent: Type, refinedName: Name, override val refinedInfo: Type, hc: Int) + extends RefinedType(parent, refinedName) { + myHash = hc + override def computeHash = unsupported("computeHash") + } object RefinedType { def make(parent: Type, names: List[Name], infoFns: List[RefinedType => Type])(implicit ctx: Context): Type = if (names.isEmpty) parent else make(RefinedType(parent, names.head, infoFns.head), names.tail, infoFns.tail) - def apply(parent: Type, name: Name, infoFn: RefinedType => Type)(implicit ctx: Context): RefinedType = { - unique(new CachedRefinedType(parent, name, infoFn)) - } + def apply(parent: Type, name: Name, infoFn: RefinedType => Type)(implicit ctx: Context): RefinedType = + ctx.base.uniqueRefinedTypes.enterIfNew(new CachedRefinedType(parent, name, infoFn)) def apply(parent: Type, name: Name, info: Type)(implicit ctx: Context): RefinedType = { - unique(new DirectRefinedType(parent, name, info)) + ctx.base.uniqueRefinedTypes.enterIfNew(parent, name, info) } } @@ -1444,7 +1346,7 @@ object Types { object AndType { def apply(tp1: Type, tp2: Type)(implicit ctx: Context) = { - assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 & $tp2") + assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType]) unchecked(tp1, tp2) } def unchecked(tp1: Type, tp2: Type)(implicit ctx: Context) = { @@ -1453,7 +1355,7 @@ object Types { } abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType { - assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 | $tp2") + assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType]) def isAnd = false @@ -1509,7 +1411,7 @@ object Types { extends CachedGroundType with BindingType with TermType with MethodOrPoly { thisMethodType => override val resultType = resultTypeExp(this) - assert(resultType != NoType, this) + assert(resultType != NoType) def isJava = false def isImplicit = false @@ -1927,8 +1829,8 @@ object Types { /** Type bounds >: lo <: hi */ abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType with TypeType { - assert(lo.isInstanceOf[TermType], lo+" "+lo.getClass) - assert(hi.isInstanceOf[TermType], hi+" "+hi.getClass) + assert(lo.isInstanceOf[TermType]) + assert(hi.isInstanceOf[TermType]) def variance: Int = 0 @@ -2000,29 +1902,27 @@ object Types { TypeBounds(substBoundSyms(lo)(hkBound), AndType(hkBound, substBoundSyms(hi)(hkBound))) } - override def computeHash = doHash(lo, hi) - override def toString = if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)" } - final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) - final class CoTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) { + class CachedTypeBounds(lo: Type, hi: Type, hc: Int) extends TypeBounds(lo, hi) { + myHash = hc + override def computeHash = unsupported("computeHash") + } + + final class CoTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) { override def variance = 1 override def toString = "Co" + super.toString } - final class ContraTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) { + final class ContraTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) { override def variance = -1 override def toString = "Contra" + super.toString } object TypeBounds { def apply(lo: Type, hi: Type, variance: Int = 0)(implicit ctx: Context): TypeBounds = - unique( - if (variance == 0) new CachedTypeBounds(lo, hi) - else if (variance == 1) new CoTypeBounds(lo, hi) - else new ContraTypeBounds(lo, hi) - ) + ctx.uniqueTypeBounds.enterIfNew(lo, hi, variance) def empty(implicit ctx: Context) = apply(defn.NothingType, defn.AnyType) def upper(hi: Type, variance: Int = 0)(implicit ctx: Context) = apply(defn.NothingType, hi, variance) def lower(lo: Type, variance: Int = 0)(implicit ctx: Context) = apply(lo, defn.AnyType, variance) diff --git a/src/dotty/tools/dotc/core/Uniques.scala b/src/dotty/tools/dotc/core/Uniques.scala new file mode 100644 index 000000000..765b5d73f --- /dev/null +++ b/src/dotty/tools/dotc/core/Uniques.scala @@ -0,0 +1,124 @@ +package dotty.tools.dotc +package core + +import Types._, Contexts._, util.Stats._, Hashable._, Names._ +import util.HashSet + +/** Defines operation `unique` for hash-consing types. + * Also defines specialized hash sets for hash consing uniques of a specific type. + * All sets offer a `enterIfNew` method which checks whether a type + * with the given parts exists already and creates a new one if not. + */ +object Uniques { + + private def recordCaching(tp: Type): Unit = recordCaching(tp.hash, tp.getClass) + private def recordCaching(h: Int, clazz: Class[_]): Unit = + if (h == NotCached) { + record("uncached-types") + record(s"uncached: $clazz") + } else { + record("cached-types") + record(s"cached: $clazz") + } + + def unique[T <: Type](tp: T)(implicit ctx: Context): T = { + if (monitored) recordCaching(tp) + if (tp.hash == NotCached) tp + else ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T] + } /* !!! DEBUG + ensuring ( + result => tp.toString == result.toString || { + println(s"cache mismatch; tp = $tp, cached = $result") + false + } + ) + */ + + final class NamedTypeUniques extends HashSet[NamedType]("uniqueNamedTypes", initialUniquesCapacity) with Hashable { + override def hash(x: NamedType): Int = x.hash + + private def findPrevious(h: Int, prefix: Type, name: Name): NamedType = { + var e = findEntryByHash(h) + while (e != null) { + if ((e.prefix == prefix) && (e.name eq name)) return e + e = nextEntryByHash(h) + } + e + } + + def enterIfNew(prefix: Type, name: Name): NamedType = { + val h = doHash(name, prefix) + if (monitored) recordCaching(h, classOf[CachedTermRef]) + def newType = + if (name.isTypeName) new CachedTypeRef(prefix, name.asTypeName, h) + else new CachedTermRef(prefix, name.asTermName, h) + if (h == NotCached) newType + else { + val r = findPrevious(h, prefix, name) + if (r ne null) r else addEntryAfterScan(newType) + } + } + } + + final class TypeBoundsUniques extends HashSet[TypeBounds]("uniqueTypeBounds", initialUniquesCapacity) with Hashable { + override def hash(x: TypeBounds): Int = x.hash + + private def findPrevious(h: Int, lo: Type, hi: Type, variance: Int): TypeBounds = { + var e = findEntryByHash(h) + while (e != null) { + if ((e.lo == lo) && (e.hi == hi) && (e.variance == variance)) return e + e = nextEntryByHash(h) + } + e + } + + def enterIfNew(lo: Type, hi: Type, variance: Int): TypeBounds = { + val h = doHash(variance, lo, hi) + if (monitored) recordCaching(h, classOf[TypeBounds]) + def newBounds = + if (variance == 0) new CachedTypeBounds(lo, hi, h) + else if (variance == 1) new CoTypeBounds(lo, hi, h) + else new ContraTypeBounds(lo, hi, h) + if (h == NotCached) newBounds + else { + val r = findPrevious(h, lo, hi, variance) + if (r ne null) r else addEntryAfterScan(newBounds) + } + } + } + + final class RefinedUniques extends HashSet[RefinedType]("uniqueRefinedTypes", 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 + + private def findPrevious(h: Int, parent: Type, refinedName: Name, refinedInfo: Type): RefinedType = { + var e = findEntryByHash(h) + while (e != null) { + if ((e.parent == parent) && (e.refinedName eq refinedName) && (e.refinedInfo == refinedInfo)) + return e + e = nextEntryByHash(h) + } + e + } + + def enterIfNew(parent: Type, refinedName: Name, refinedInfo: Type): RefinedType = { + val h = doHash(refinedName, refinedInfo, parent) + def newType = new PreHashedRefinedType(parent, refinedName, refinedInfo, h) + if (monitored) recordCaching(h, classOf[PreHashedRefinedType]) + if (h == NotCached) newType + else { + val r = findPrevious(h, parent, refinedName, refinedInfo) + if (r ne null) r else addEntryAfterScan(newType) + } + } + + def enterIfNew(rt: RefinedType) = { + if (monitored) recordCaching(rt) + if (rt.hash == NotCached) rt + else { + val r = findPrevious(rt.hash, rt.parent, rt.refinedName, rt.refinedInfo) + if (r ne null) r else addEntryAfterScan(rt) + } + } + } +}
\ No newline at end of file diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala index 8a1b9f554..a8985cf36 100644 --- a/src/dotty/tools/dotc/typer/Implicits.scala +++ b/src/dotty/tools/dotc/typer/Implicits.scala @@ -23,6 +23,7 @@ import Constants._ import Inferencing._ import Applications._ import ErrorReporting._ +import Hashable._ import config.Config import config.Printers._ import collection.mutable diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 3ef9f42a6..4986d257e 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -73,7 +73,8 @@ object Inferencing { * [ ].name: proto */ class SelectionProto(val name: Name, proto: Type, compat: Compatibility) - extends DirectRefinedType(WildcardType, name, proto) with ProtoType { + extends RefinedType(WildcardType, name) with ProtoType { + override val refinedInfo = proto override def isMatchedBy(tp1: Type)(implicit ctx: Context) = name == nme.WILDCARD || { val mbr = tp1.member(name) diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala index 8d809cdf4..32c3dbc3d 100644 --- a/src/dotty/tools/dotc/util/HashSet.scala +++ b/src/dotty/tools/dotc/util/HashSet.scala @@ -36,6 +36,10 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte h = index(h + 1) entry = table(h) } + addEntryAt(h, x) + } + + private def addEntryAt(h: Int, x: T) = { table(h) = x used += 1 if (used > (table.length >> 2)) growTable() @@ -52,6 +56,25 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte entry.asInstanceOf[T] } + 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) + def addEntry(x: T): Unit = { var h = index(hash(x)) var entry = table(h) diff --git a/src/dotty/tools/dotc/util/Stats.scala b/src/dotty/tools/dotc/util/Stats.scala index 95b50cf58..a535f203c 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"unique types: ${ctx.base.uniquesSize}") + println(s"sizes: ${ctx.base.uniquesSize}") } } else op } |