diff options
19 files changed, 2806 insertions, 1650 deletions
diff --git a/src/dotty/tools/dotc/core/Annotations.scala b/src/dotty/tools/dotc/core/Annotations.scala index 48165f488..ead92409e 100644 --- a/src/dotty/tools/dotc/core/Annotations.scala +++ b/src/dotty/tools/dotc/core/Annotations.scala @@ -1,7 +1,11 @@ package dotty.tools.dotc.core +import Symbols._ + object Annotations { - abstract class AnnotationInfo + abstract class Annotation { + def matches(cls: Symbol) = ??? + } }
\ 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 873bbf377..645820792 100644 --- a/src/dotty/tools/dotc/core/Contexts.scala +++ b/src/dotty/tools/dotc/core/Contexts.scala @@ -6,45 +6,52 @@ import Periods._ import Names._ import Phases._ import Types._ -import SubTypers._ +import Symbols._ +import TypeComparers._, Printers._ +import collection.mutable +import collection.immutable.BitSet object Contexts { val NoContext: Context = null - abstract class Context extends Periods { + abstract class Context extends Periods with Substituters with TypeOps { + implicit val ctx: Context = this val underlying: Context val root: RootContext val period: Period def constraints: Constraints - def subTyper: SubTyper + def typeComparer: TypeComparer + def printer: Printer = ??? def names: NameTable + def enclClass: Context = ??? def phase: Phase = ??? - def stableInterval: Interval = ??? + def owner: Symbol = ??? def erasedTypes: Boolean = ??? } + abstract class DiagnosticsContext(ctx: Context) extends SubContext(ctx) { + var diagnostics: () => String + } + abstract class SubContext(val underlying: Context) extends Context { val root: RootContext = underlying.root val period: Period = underlying.period val constraints = underlying.constraints def names: NameTable = root.names - lazy val subTyper = - if (constraints eq underlying.constraints) underlying.subTyper - else new SubTyper(this) + lazy val typeComparer = + if (constraints eq underlying.constraints) underlying.typeComparer + else new TypeComparer(this) } class RootContext extends Context - with Symbols - with Denotations - with DenotationTransformers - with Types { + with Transformers { val underlying: Context = throw new UnsupportedOperationException("RootContext.underlying") - def subTyper: SubTyper = ??? + def typeComparer: TypeComparer = ??? val root: RootContext = this - val period = periodOf(NoRunId, NoPhaseId) + val period = Nowhere val names: NameTable = new NameTable val variance = 1 @@ -52,7 +59,49 @@ object Contexts { lazy val definitions = new Definitions()(this) val constraints: Constraints = Map() + + // Symbols state + /** A map from a superclass id to the class that has it */ + private[core] var classOfId = new Array[ClassSymbol](InitialSuperIdsSize) + + /** A map from a superclass to its superclass id */ + private[core] val superIdOfClass = new mutable.HashMap[ClassSymbol, Int] + + /** The last allocate superclass id */ + private[core] var lastSuperId = -1 + + /** Allocate and return next free superclass id */ + private[core] def nextSuperId: Int = { + lastSuperId += 1; + if (lastSuperId >= classOfId.length) { + val tmp = new Array[ClassSymbol](classOfId.length * 2) + classOfId.copyToArray(tmp) + classOfId = tmp + } + lastSuperId + } + + // SymDenotations state + private[core] val uniqueBits = new util.HashSet[BitSet]("superbits", 1024) + + // Types state + private[core] val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) { + override def hash(x: Type): Int = x.hash + } + + // TypeOps state + private[core] var volatileRecursions: Int = 0 + private[core] val pendingVolatiles = new mutable.HashSet[Type] } - private final val initialUniquesCapacity = 4096 -}
\ No newline at end of file + /** Initial size of superId table */ + private final val InitialSuperIdsSize = 4096 + + /** Initial capacity of uniques HashMap */ + private[core] final val initialUniquesCapacity = 50000 + + /** How many recursive calls to isVolatile are performed before + * logging starts. + */ + private[core] final val LogVolatileThreshold = 50 +} diff --git a/src/dotty/tools/dotc/core/Decorators.scala b/src/dotty/tools/dotc/core/Decorators.scala index ba3123358..d0ce3efe0 100644 --- a/src/dotty/tools/dotc/core/Decorators.scala +++ b/src/dotty/tools/dotc/core/Decorators.scala @@ -1,6 +1,9 @@ package dotty.tools.dotc package core +import annotation.tailrec +import Symbols._ + import Contexts._, Names._ object Decorators { @@ -15,6 +18,16 @@ object Decorators { context.names.newTermName(s) } + implicit class SymbolIteratorDecorator(val it: Iterator[Symbol]) extends AnyVal { + final def findSymbol(p: Symbol => Boolean): Symbol = { + while (it.hasNext) { + val sym = it.next + if (p(sym)) return sym + } + NoSymbol + } + } + final val MaxRecursions = 1000 implicit class ListDecorator[T](val xs: List[T]) extends AnyVal { diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index 8e76282a3..9bf1e88c3 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -6,6 +6,7 @@ class Definitions(implicit ctx: Context) { private var _isInitialized = false def isInitialized = _isInitialized + lazy val RootClass: ClassSymbol = ??? lazy val AnyClass: ClassSymbol = ??? lazy val AnyType = AnyClass.typeConstructor lazy val AnyValClass: ClassSymbol = ??? @@ -18,6 +19,7 @@ class Definitions(implicit ctx: Context) { lazy val SingletonClass: ClassSymbol = ??? lazy val SingletonType = SingletonClass.typeConstructor lazy val ArrayClass: ClassSymbol = ??? + lazy val uncheckedStableClass: ClassSymbol = ??? def init() = if (!isInitialized) { diff --git a/src/dotty/tools/dotc/core/Denotations.scala b/src/dotty/tools/dotc/core/Denotations.scala index 75f040e1d..12b522427 100644 --- a/src/dotty/tools/dotc/core/Denotations.scala +++ b/src/dotty/tools/dotc/core/Denotations.scala @@ -1,335 +1,436 @@ package dotty.tools.dotc package core -import Periods._, Contexts._, Symbols._, References._, Names._ -import Types._, Flags._, Decorators._ -import Scopes.Scope -import collection.mutable -import collection.immutable.BitSet - -trait Denotations { self: Context => - - /** A set for hash consing superclass bitsets */ - private val uniqueBits = new util.HashSet[BitSet]("superbits", 1024) - -} - +import SymDenotations.{SymDenotation, NoDenotation} +import Contexts.Context +import Names.Name +import Names.TypeName +import Symbols.NoSymbol +import Symbols.Symbol +import Types._, Periods._, Flags._, Transformers._ +import Decorators.SymbolIteratorDecorator + + +/** Denotations represent the meaning of symbols and named types. + * The following diagram shows how the principal types of denotations + * and their denoting entities relate to each other. Lines ending in + * a down-arrow `v` are member methods. The two methods shown in the diagram are + * "symbol" and "deref". Both methods are parameterized by the current context, + * and are effectively indexed by current period. + * + * Lines ending in a horizontal line mean subtying (right is a subtype of left). + * + * NamedType------NamedTypeWithSignature + + * | | Symbol---------ClassSymbol + * | | | | + * | denot | denot | denot | denot + * v v v v + * Denotation-+-----SingleDenotation-+------SymDenotation-+----ClassDenotation-+--CompleteClassDenotation + * | | | +--LazyClassDenotation + * +-----MultiDenotation | | + * | +--CompleteSymDenotation + * | +--LazySymDenotation + * | + * +--UniqueRefDenotation + * +--JointRefDenotation + * + * Here's a short summary of the classes in this diagram. + * + * NamedType A type consisting of a prefix type and a name, with fields + * prefix: Type + * name: Name + * NamedTypeWithSignature A named type that has in addition a signature to select an overloaded variant, with new field + * signature: Signature + * Symbol A label for a definition or declaration in one compiler run + * ClassSymbol A symbol representing a class + * Denotation The meaning of a named type or symbol during a period + * MultiDenotation A denotation representing several overloaded members + * SingleDenotation A denotation representing a non-overloaded member or definition, with main fields + * symbol: Symbol + * info: Type + * UniqueRefDenotation A denotation referring to a single definition with some member type + * JointRefDenotation A denotation referring to a member that could resolve to several definitions + * SymDenotation A denotation representing a single definition with its original type, with main fields + * name: Name + * owner: Symbol + * flags: Flags + * privateWithin: Symbol + * annotations: List[Annotation] + * ClassDenotation A denotation representing a single class definition, with new fields + * typeParams: List[TypeSymbol] + * parents: List[Type] + * decls: Scope + * LazySymDenotation A sym-denotation with fields that are computed on demand + * CompleteSymDenotation A sym-denotation that has all fields completed + * LazyClassDenotation A class denotation with fields that are computed on demand + * CompleteClassDenotation A class denotation that has all fields completed + */ object Denotations { - abstract class Denotation { - - /** The validity interval of this symbol */ - var valid: Interval = Nowhere - - /** The next instance of this symbol in the same run */ - private[core] var nextInRun: Denotation = this - - /** - * The version of this symbol that was valid in the first phase - * of this run - */ - def initial: Denotation = { - var sym = nextInRun - while (sym.valid > this.valid) sym = sym.nextInRun - sym - } - - def owner: Symbol = ??? - - def name: Name = ??? - - def flags: FlagSet = ??? - - def setFlag(flag: FlagSet): Unit = ??? - - def tpe: Type = ??? - - def info: Type = ??? - - /* Validity and instance handling: - * - * Symbols have an interval of validity, defined - * by their `valid` fields. - * - * There may be several symbols with different validity - * representing the same underlying symbol at different phases. - * These are called a "flock". Flock members are generated by - * @see SymRef.trackSym. Flock members are connected in a ring - * with their `nextInFlock` fields. - * - * There are the following invariants converning flock members - * - * 1) validity intervals must be non-overlapping - * 2) the union of all validity intervals must be a contiguous - * interval starting in FirstPhaseId. - */ - - /** is this symbol a type? */ + /** The signature of a denotation. + * Overloaded denotations with the same name are distinguished by + * their signatures. A signature is a list of the fully qualified names + * of the type symbols of the erasure of the parameters of the + * denotation. For instance a definition + * + * def f(x: Int)(y: List[String]): String + * + * would have signature + * + * List("scala.Int".toTypeName, "scala.collection.immutable.List".toTypeName) + */ + type Signature = List[TypeName] + + /** The signature of a val or parameterless def, as opposed + * to List(), which is the signature of a zero-parameter def. + */ + val NullSignature = List(Names.EmptyTypeName) + + /** A denotation is the result of resolving + * a name (either simple identifier or select) during a given period. + * + * Denotation has two subclasses: MultiDenotation and SingleDenotation. + * + * A SingleDenotation refers to a `symbol` and a type (`info`) that the symbol has + * when seen from the reference. + * + * Denotations can be combined with `&` and `|`. + * & is conjunction, | is disjunction. + * + * `&` will create an overloaded denotation from two + * non-overloaded denotations if their signatures differ. + * Analogously `|` of two denotations with different signatures will give + * an empty denotation `NoDenotation`. + * + * A denotation might refer to `NoSymbol`. This is the case if the denotation + * was produced from a disjunction of two denotations with different symbols + * and there was no common symbol in a superclass that could substitute for + * both symbols. Here is an example: + * + * Say, we have: + * + * class A { def f: A } + * class B { def f: B } + * val x: A | B = if (???) new A else new B + * val y = x.f + * + * Then the denotation of `y` is `SingleDenotation(NoSymbol, A | B)`. + */ + abstract class Denotation extends DotClass { + + /** The referencing symbol, exists only for non-overloaded denotations */ + def symbol: Symbol + + /** The type info of the denotation, exists only for non-overloaded denotations */ + def info: Type + + /** The period during which this denotation is valid. */ + def validFor: Period + + /** Is this a reference to a type symbol? */ def isType: Boolean = false - /** is this symbol a class? */ - def isClass: Boolean = false + /** Is this a reference to a term symbol? */ + def isTerm: Boolean = false - /** is this symbol a method? */ - def isMethod: Boolean = false + /** Is this denotation overloaded? */ + def isOverloaded = isInstanceOf[MultiDenotation] - /** is this symbol the result of an erroneous definition? */ - def isError: Boolean = false + /** The signature of the denotation */ + def signature: Signature - def withType(tp: Type): Denotation = ??? - } + /** Resolve overloaded denotation to pick the one with the given signature */ + def atSignature(sig: Signature): SingleDenotation - object NameFilter { - final val WordSizeLog = 6 - final val DefinedNamesWords = 16 - final val DefinedNamesSize = DefinedNamesWords << WordSizeLog - final val DefinedNamesMask = DefinedNamesSize - 1 + /** The variant of this denotation that's current in the given context. */ + def current(implicit ctx: Context): Denotation - type FingerPrint = Array[Long] + def exists: Boolean = true - def includeName(bits: FingerPrint, name: Name): Unit = { - val hash = name.start & DefinedNamesMask - bits(hash >> 6) |= (1 << hash) - } + def filter(p: Symbol => Boolean)(implicit ctx: Context): Denotation - def includeFingerPrint(bits1: FingerPrint, bits2: FingerPrint): Unit = - for (i <- 0 until DefinedNamesWords) bits1(i) |= bits2(i) + /** Form a denotation by conjoining with denotation `that` */ + def & (that: Denotation)(implicit ctx: Context): Denotation = + if (this eq that) this + else if (!this.exists) that + else if (!that.exists) this + else that match { + case that: SingleDenotation => + val r = mergeDenot(this, that) + if (r ne NoDenotation) r else MultiDenotation(this, that) + case that @ MultiDenotation(denot1, denot2) => + this & denot1 & denot2 + } - def containsName(bits: FingerPrint, name: Name): Boolean = { - val hash = name.start & DefinedNamesMask - (bits(hash >> 6) & (1 << hash)) != 0 + /** Try to merge denot1 and denot2 without adding a new signature. + * If unsuccessful, return NoDenotation. + */ + private def mergeDenot(denot1: Denotation, denot2: SingleDenotation)(implicit ctx: Context): Denotation = denot1 match { + case denot1 @ MultiDenotation(denot11, denot12) => + val d1 = mergeDenot(denot11, denot2) + if (d1 ne NoDenotation) d1 else mergeDenot(denot12, denot2) + case denot1: SingleDenotation => + if (denot1 eq denot2) denot1 + else if (denot1.signature == denot2.signature) { + def isEligible(sym1: Symbol, sym2: Symbol) = + if (sym1.isType) !sym1.isClass + else sym1.isConcrete || sym2.isDeferred || !sym2.exists + def normalize(info: Type) = + if (isType) info.bounds else info + val sym1 = denot1.symbol + val info1 = denot1.info + val sym2 = denot2.symbol + val info2 = denot2.info + val sym1Eligible = isEligible(sym1, sym2) + val sym2Eligible = isEligible(sym2, sym1) + val bounds1 = normalize(info1) + val bounds2 = normalize(info2) + if (sym2Eligible && bounds2 <:< bounds1) denot2 + else if (sym1Eligible && bounds1 <:< bounds2) denot1 + else new JointRefDenotation( + if (sym2Eligible) sym2 else sym1, + bounds1 & bounds2, + denot1.validFor & denot2.validFor) + } else NoDenotation } - def newNameFilter: FingerPrint = new Array[Long](DefinedNamesWords) - } - - class ClassDenotation(val parents: List[Type], val decls: Scope, val clazz: ClassSymbol) extends Denotation { - import NameFilter._ - import util.LRU8Cache + def | (that: Denotation)(pre: Type)(implicit ctx: Context): Denotation = { - def typeParams: List[TypeSymbol] = ??? + def lubSym(sym1: Symbol, sym2: Symbol): Symbol = { + def qualifies(sym: Symbol) = + sym.isAccessibleFrom(pre) && sym2.owner.isSubClass(sym.owner) + sym1.allOverriddenSymbols findSymbol qualifies + } - private var memberCacheVar: LRU8Cache[Name, RefSet] = null + def throwError = throw new MatchError(s"$this | $that") - private def memberCache: LRU8Cache[Name, RefSet] = { - if (memberCacheVar == null) memberCacheVar = new LRU8Cache - memberCacheVar + if (this eq that) this + else if (!this.exists) this + else if (!that.exists) that + else this match { + case denot1 @ MultiDenotation(denot11, denot12) => + denot1.derivedMultiDenotation((denot11 | that)(pre), (denot12 | that)(pre)) + case _ => + that match { + case denot2 @ MultiDenotation(denot21, denot22) => + denot2.derivedMultiDenotation((this | denot21)(pre), (this | denot22)(pre)) + case denot2: SingleDenotation => + this match { + case denot1: SingleDenotation => + if (denot1.signature != denot2.signature) NoDenotation + else new JointRefDenotation( + lubSym(denot1.symbol, denot2.symbol), + denot1.info | denot2.info, + denot1.validFor & denot2.validFor) + case _ => + throwError + } + case _ => + throwError + } + } } + } - private var thisTypeCache: ThisType = null - - def thisType(implicit ctx: Context): Type = { - if (thisTypeCache == null) - thisTypeCache = ThisType(clazz) - thisTypeCache - } + /** The class of overloaded denotations + * @param variants The overloaded variants indexed by thheir signatures. + */ + case class MultiDenotation(denot1: Denotation, denot2: Denotation) extends Denotation { + final override def isType = false + final override def isTerm = true + def derivedMultiDenotation(d1: Denotation, d2: Denotation) = + if ((d1 eq denot1) && (d2 eq denot2)) this else MultiDenotation(d1, d2) + def symbol = unsupported("symbol") + def info = unsupported("info") + def signature = unsupported("signature") + def filter(p: Symbol => Boolean)(implicit ctx: Context): Denotation = + (denot1 filter p) & (denot2 filter p) + def atSignature(sig: Signature): SingleDenotation = + denot1.atSignature(sig) orElse denot2.atSignature(sig) + def validFor = denot1.validFor & denot2.validFor + def current(implicit ctx: Context): Denotation = + derivedMultiDenotation(denot1.current, denot2.current) + } - private var typeConstructorCache: Type = null + abstract class SingleDenotation extends Denotation with DenotationSet { - def typeConstructor(implicit ctx: Context): Type = { - if (typeConstructorCache == null) - typeConstructorCache = NamedType(thisType, clazz.name) - typeConstructorCache + override def isType = symbol.isType + override def isTerm = symbol.isTerm + override def signature: Signature = { + def sig(tp: Type): Signature = tp match { + case tp: PolyType => + tp.resultType match { + case mt: MethodType => mt.signature + case _ => List() + } + case mt: MethodType => mt.signature + case _ => NullSignature + } + if (isType) NullSignature else sig(info) } - private var typeTemplateCache: Type = null + def derivedSingleDenotation(s: Symbol, i: Type): SingleDenotation = + if ((s eq symbol) && (i eq info)) this else copy(s, i) - def typeTemplate(implicit ctx: Context): Type = { - if (typeTemplateCache == null) - AppliedType.make(typeConstructor, typeParams map (_.typeConstructor)) - typeTemplateCache - } + protected def copy(s: Symbol, i: Type): SingleDenotation = this - private var baseClassesVar: List[ClassSymbol] = null - private var superClassBitsVar: BitSet = null - - private def computeSuperClassBits(implicit ctx: Context): Unit = { - val seen = new mutable.BitSet - val locked = new mutable.BitSet - def addBaseClasses(bcs: List[ClassSymbol], to: List[ClassSymbol]) - : List[ClassSymbol] = bcs match { - case bc :: bcs1 => - val id = bc.superId - if (seen contains id) to - else if (locked contains id) throw new CyclicReference(clazz) - else { - locked += id - val bcs1added = addBaseClasses(bcs1, to) - seen += id - if (bcs1added eq bcs1) bcs else bc :: bcs1added - } - case _ => - to - } - def addParentBaseClasses(ps: List[Type], to: List[ClassSymbol]): List[ClassSymbol] = ps match { - case p :: ps1 => - addBaseClasses(p.baseClasses, addParentBaseClasses(ps1, to)) - case _ => - to - } - baseClassesVar = clazz :: addParentBaseClasses(parents, Nil) - superClassBitsVar = ctx.root.uniqueBits.findEntryOrUpdate(seen.toImmutable) - } + def orElse(that: => SingleDenotation) = if (this.exists) this else that - def superClassBits(implicit ctx: Context): BitSet = { - if (superClassBitsVar == null) computeSuperClassBits - superClassBitsVar - } + def filter(p: Symbol => Boolean)(implicit ctx: Context): SingleDenotation = + if (p(symbol)) this else NoDenotation - def baseClasses(implicit ctx: Context): List[ClassSymbol] = { - if (baseClassesVar == null) computeSuperClassBits - baseClassesVar - } + def atSignature(sig: Signature): SingleDenotation = + if (sig == signature) this else NoDenotation - /** Is this class a subclass of `clazz`? */ - final def isSubClass(clazz: ClassSymbol)(implicit ctx: Context): Boolean = { - superClassBits contains clazz.superId - } + // ------ Transformations ----------------------------------------- - private var definedFingerPrintCache: FingerPrint = null + private[this] var _validFor: Period = Nowhere - private def computeDefinedFingerPrint(implicit ctx: Context): FingerPrint = { - var bits = newNameFilter - var e = decls.lastEntry - while (e != null) { - includeName(bits, clazz.name) - e = e.prev - } - var ps = parents - while (ps.nonEmpty) { - val parent = ps.head.typeSymbol - parent.deref match { - case classd: ClassDenotation => - includeFingerPrint(bits, classd.definedFingerPrint) - parent.deref setFlag Frozen - case _ => - } - ps = ps.tail - } - definedFingerPrintCache = bits - bits - } + def validFor = _validFor + def validFor_=(p: Period) = + _validFor = p - /** Enter a symbol in current scope. - * Note: We require that this does not happen after the first time - * someone does a findMember on a subclass. + /** The next SingleDenotation in this run, with wrap-around from last to first. + * + * There may be several `SingleDenotation`s with different validity + * representing the same underlying definition at different phases. + * These are called a "flock". Flock members are generated by + * @See current. Flock members are connected in a ring + * with their `nextInRun` fields. + * + * There are the following invariants converning flock members + * + * 1) validity periods must be non-overlapping + * 2) the union of all validity periods must be a contiguous + * interval starting in FirstPhaseId. */ - def enter(sym: Symbol)(implicit ctx: Context) = { - require((clazz.flags & Frozen) == Flags.Empty) - decls enter sym - if (definedFingerPrintCache != null) - includeName(definedFingerPrintCache, sym.name) - if (memberCacheVar != null) - memberCache invalidate sym.name - } + var nextInRun: SingleDenotation = this - /** Delete symbol from current scope. - * Note: We require that this does not happen after the first time - * someone does a findMember on a subclass. + /** The version of this SingleDenotation that was valid in the first phase + * of this run. */ - def delete(sym: Symbol)(implicit ctx: Context) = { - require((clazz.flags & Frozen) == Flags.Empty) - decls unlink sym - if (definedFingerPrintCache != null) - computeDefinedFingerPrint - if (memberCacheVar != null) - memberCache invalidate sym.name + def initial: SingleDenotation = { + var current = nextInRun + while (current.validFor.code > this._validFor.code) current = current.nextInRun + current } - def definedFingerPrint(implicit ctx: Context): FingerPrint = { - val fp = definedFingerPrintCache - if (fp != null) fp else computeDefinedFingerPrint - } - - final def memberRefsNamed(name: Name)(implicit ctx: Context): RefSet = { - var refs: RefSet = memberCache lookup name - if (refs == null) { - if (containsName(definedFingerPrint, name)) { - val ownRefs = decls.refsNamed(name) - refs = ownRefs - var ps = parents - while (ps.nonEmpty) { - val parentSym = ps.head.typeSymbol - parentSym.deref match { - case parentd: ClassDenotation => - refs = refs union - parentd.memberRefsNamed(name) - .filterExcluded(Flags.Private) - .asSeenFrom(thisType, parentSym) - .filterDisjoint(ownRefs) - case _ => - } - } + def current(implicit ctx: Context): SingleDenotation = { + val currentPeriod = ctx.period + val valid = _validFor + var current = this + if (currentPeriod.code > valid.code) { + // search for containing period as long as nextInRun increases. + var next = nextInRun + while (next.validFor.code > valid.code && + !(next.validFor contains currentPeriod)) { + current = next + next = next.nextInRun + } + if (next.validFor.code > valid.code) { + // in this case, containsPeriod(next._validFor, currentPeriod) + current = next } else { - refs = NoRef + // not found, current points to highest existing variant + var startPid = current.validFor.lastPhaseId + 1 + val trans = ctx.root.transformersFor(current) + val endPid = trans.nextTransformer(startPid + 1).phaseId - 1 + next = trans.nextTransformer(startPid) transform current + if (next eq current) + startPid = current.validFor.firstPhaseId + else { + current.nextInRun = next + current = next + } + current.validFor = Period(currentPeriod.runId, startPid, endPid) } - memberCache enter (name, refs) + } else { + // currentPeriod < valid; in this case a version must exist + do { + current = current.nextInRun + } while (!(current.validFor contains currentPeriod)) } - refs + current } - private var baseTypeCache: java.util.HashMap[UniqueType, Type] = null - - final def baseTypeOf(tp: Type)(implicit ctx: Context): Type = { - - def computeBaseTypeOf(tp: Type): Type = tp match { - case AppliedType(tycon, args) => - baseTypeOf(tycon).subst(tycon.typeParams, args) - case tp: TypeProxy => - baseTypeOf(tp.underlying) - case AndType(tp1, tp2) => - baseTypeOf(tp1) & baseTypeOf(tp2) - case OrType(tp1, tp2) => - baseTypeOf(tp1) | baseTypeOf(tp2) - case tp @ ClassInfo(pre, classd) => - def reduce(bt: Type, ps: List[Type]): Type = ps match { - case p :: ps1 => reduce(bt & baseTypeOf(p), ps1) - case _ => bt - } - if (classd.clazz == clazz) tp.typeTemplate - else reduce(NoType, classd.parents).substThis(classd.clazz, tp.prefix) - } + //final def asSymDenotation = asInstanceOf[SymDenotation] + + // ------ DenotationSet ops ---------------------------------------------- + + def toDenot(implicit ctx: Context) = this + def containsSig(sig: Signature)(implicit ctx: Context) = + signature == sig + def filterDisjoint(denots: DenotationSet)(implicit ctx: Context): DenotationSet = + if (denots.containsSig(signature)) NoDenotation else this + def filterExcluded(flags: FlagSet)(implicit ctx: Context): DenotationSet = + if (symbol is flags) NoDenotation else this + def filterAccessibleFrom(pre: Type)(implicit ctx: Context): DenotationSet = + if (symbol.isAccessibleFrom(pre)) this else NoDenotation + def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): DenotationSet = + derivedSingleDenotation(symbol, info.asSeenFrom(pre, owner)) + } - if (clazz.isStatic && clazz.typeParams.isEmpty) clazz.typeConstructor - else tp match { - case tp: UniqueType => - if (baseTypeCache == null) - baseTypeCache = new java.util.HashMap[UniqueType, Type] - var basetp = baseTypeCache get tp - if (basetp == null) { - baseTypeCache.put(tp, NoType) - basetp = computeBaseTypeOf(tp) - baseTypeCache.put(tp, basetp) - } else if (basetp == NoType) { - throw new CyclicReference(clazz) - } - basetp - case _ => - computeBaseTypeOf(tp) - } - } + class UniqueRefDenotation(val symbol: Symbol, + val info: Type, + initValidFor: Period) extends SingleDenotation { + validFor = initValidFor + override protected def copy(s: Symbol, i: Type): SingleDenotation = new UniqueRefDenotation(s, i, validFor) + } - private var memberNamesCache: Map[NameFilter, Set[Name]] = Map() + class JointRefDenotation(val symbol: Symbol, + val info: Type, + initValidFor: Period) extends SingleDenotation { + validFor = initValidFor + override protected def copy(s: Symbol, i: Type): SingleDenotation = new JointRefDenotation(s, i, validFor) + } - def memberNames(keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - memberNamesCache get keepOnly match { - case Some(names) => - names - case _ => - val inheritedNames = (parents flatMap (_.memberNames(thisType, keepOnly))).toSet - val ownNames = decls.iterator map (_.name) - val candidates = inheritedNames ++ ownNames - val names = candidates filter (keepOnly(thisType, _)) - memberNamesCache += (keepOnly -> names) - names - } + class ErrorDenotation(implicit ctx: Context) extends SingleDenotation { + val symbol = NoSymbol + val info = NoType + validFor = Period.allInRun(ctx.runId) + } + +// --------------- DenotationSets ------------------------------------------------- + + /** A DenotationSet represents a set of single denotations + * It is used as an optimization to avoid forming MultiDenotations too eagerly. + */ + trait DenotationSet { + def exists: Boolean + def toDenot(implicit ctx: Context): Denotation + def containsSig(sig: Signature)(implicit ctx: Context): Boolean + def filterDisjoint(denots: DenotationSet)(implicit ctx: Context): DenotationSet + def filterExcluded(flags: FlagSet)(implicit ctx: Context): DenotationSet + def filterAccessibleFrom(pre: Type)(implicit ctx: Context): DenotationSet + def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): DenotationSet + def union(that: DenotationSet) = + if (!this.exists) that + else if (that.exists) this + else DenotUnion(this, that) } - object NoDenotation extends Denotation { - override def owner: Symbol = throw new AssertionError("NoDenotation.owner") - override def name: Name = BootNameTable.newTermName("<none>") - override def flags = Flags.Empty - override def tpe: Type = NoType - override def info: Type = NoType + case class DenotUnion(denots1: DenotationSet, denots2: DenotationSet) extends DenotationSet { + assert(denots1.exists && denots2.exists) + private def derivedUnion(s1: DenotationSet, s2: DenotationSet) = + if (!s1.exists) s2 + else if (!s2.exists) s1 + else if ((s1 eq denots2) && (s2 eq denots2)) this + else new DenotUnion(s1, s2) + def exists = true + def toDenot(implicit ctx: Context) = denots1.toDenot & denots2.toDenot + def containsSig(sig: Signature)(implicit ctx: Context) = + (denots1 containsSig sig) || (denots2 containsSig sig) + //def filter(p: Symbol => Boolean)(implicit ctx: Context) = + // derivedUnion(denots1 filter p, denots2 filter p) + def filterDisjoint(denots: DenotationSet)(implicit ctx: Context): DenotationSet = + derivedUnion(denots1 filterDisjoint denots, denots2 filterDisjoint denots) + def filterExcluded(flags: FlagSet)(implicit ctx: Context): DenotationSet = + derivedUnion(denots1 filterExcluded flags, denots2 filterExcluded flags) + def filterAccessibleFrom(pre: Type)(implicit ctx: Context): DenotationSet = + derivedUnion(denots1 filterAccessibleFrom pre, denots2 filterAccessibleFrom pre) + def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): DenotationSet = + derivedUnion(denots1.asSeenFrom(pre, owner), denots2.asSeenFrom(pre, owner)) } -}
\ No newline at end of file +} + diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala index fc9a1b4d3..0e995f756 100644 --- a/src/dotty/tools/dotc/core/Flags.scala +++ b/src/dotty/tools/dotc/core/Flags.scala @@ -2,16 +2,351 @@ package dotty.tools.dotc.core object Flags { + /** A FlagSet represents a set of flags. Flags are encoded as follows: + * The first two bits indicate whether a flagset applies to terms, + * to types, or to both. Bits 2..63 are available for properties + * and can be doubly used for terms and types. + * Combining two FlagSets with `|` will give a FlagSet + * that has the intersection of the applicability to terms/types + * of the two flag sets. It is checked that the intersection is not empty. + */ case class FlagSet(val bits: Long) extends AnyVal { - def | (that: FlagSet) = FlagSet(this.bits | that.bits) - def & (that: FlagSet) = FlagSet(this.bits & that.bits) + + /** The union of this flag set and the given flag set + */ + def | (that: FlagSet): FlagSet = + if (bits == 0) that + else if (that.bits == 0) this + else { + val tbits = bits & that.bits & KINDFLAGS + assert(tbits != 0, s"illegal flagset combination: $this and $that") + FlagSet(tbits | ((this.bits | that.bits) & ~KINDFLAGS)) + } + + /** The union of this flag set and the given flag conjunction seen as + * a flag set. + */ + def | (that: FlagConjunction): FlagSet = this | FlagSet(that.bits) + + /** The intersection of this flag set and the given flag set */ + def & (that: FlagSet) = FlagSet(bits & that.bits) + + /** The intersection of this flag set with the complement of the given flag set */ + def &~ (that: FlagSet) = { + val tbits = bits & KINDFLAGS + if ((tbits & that.bits) == 0) this + else FlagSet(tbits | ((this.bits & ~that.bits) & ~KINDFLAGS)) + } + + /** Does this flag set have a non-empty intersection with the given flag set? + * Pre: The intersection of the typeflags of both sets must be non-empty. + */ + def is(flags: FlagSet) = { + val fs = bits & flags.bits + (fs & KINDFLAGS) != 0 && + fs > KINDFLAGS + } + + /** Does this flag set have a non-empty intersection with the given flag set, + * and at the same time contain none of the flags in the `butNot` set? + * Pre: The intersection of the typeflags of both sets must be non-empty. + */ + def is(flags: FlagSet, butNot: FlagSet) = { + val fs = bits & flags.bits + (fs & KINDFLAGS) != 0 && + fs > KINDFLAGS && + (bits & butNot.bits) == 0 + } + + /** Does this flag set have all of the flags in given flag conjunction? + * Pre: The intersection of the typeflags of both sets must be non-empty. + */ + def is(flags: FlagConjunction) = { + val fs = bits & flags.bits + (fs & KINDFLAGS) != 0 && + (fs >> TYPESHIFT) == (flags.bits >> TYPESHIFT) + } + + /** Does this flag set have all of the flags in given flag conjunction? + * and at the same time contain none of the flags in the `butNot` set? + * Pre: The intersection of the typeflags of both sets must be non-empty. + */ + def is(flags: FlagConjunction, butNot: FlagSet) = { + val fs = bits & (flags.bits | butNot.bits) + (fs & KINDFLAGS) != 0 && + (fs >> TYPESHIFT) == (flags.bits >> TYPESHIFT) + } + + /** This flag set with all flags transposed to be type flags */ + def toTypeFlags = FlagSet(bits & ~KINDFLAGS | TYPES) + + /** This flag set with all flags transposed to be term flags */ + def toTermFlags = FlagSet(bits & ~KINDFLAGS | TERMS) + + /** This flag set with all flags transposed to be common flags */ + def toCommonFlags = FlagSet(bits | KINDFLAGS) + + /** The number of non-kind flags in this set */ + def numFlags: Int = java.lang.Long.bitCount(bits & ~KINDFLAGS) + + /** The set of all non-empty strings that are associated + * as term or type flags with this index + */ + private def flagString(idx: Int): Set[String] = + kindIndices.map(flagName(idx)).filterNot(_.isEmpty) + + /** The string representation of this flag set */ + override def toString = + (2 to MaxFlag).flatMap(flagString).mkString(" ") + } + + /** A class representing flag sets that should be tested + * conjunctively. I.e. for a flag conjunction `fc`, + * `x is fc` tests whether `x` contains all flags in `fc`. + */ + case class FlagConjunction(bits: Long) + + private final val TYPESHIFT = 2 + private final val TERMindex = 0 + private final val TYPEindex = 1 + private final val TERMS = 1 << TERMindex + private final val TYPES = 1 << TYPEindex + private final val KINDFLAGS = TERMS | TYPES + + private final val MaxFlag = 63 + + private var flagName = Array.fill(64, 2)("") + + private val kindIndices = Set(TERMindex, TYPEindex) + + /** The flag with given index between 2 and 63 which applies to terms. + * Installs given name as the name of the flag. */ + def termFlag(index: Int, name: String): FlagSet = { + flagName(index)(TERMindex) = name + FlagSet(TERMS | (1L << index)) + } + + /** The flag with given index between 2 and 63 which applies to types. + * Installs given name as the name of the flag. */ + def typeFlag(index: Int, name: String): FlagSet = { + flagName(index)(TYPEindex) = name + FlagSet(TYPES | (1L << index)) + } + + /** The flag with given index between 2 and 63 which applies to both terms and types */ + def commonFlag(index: Int, name: String): FlagSet = { + flagName(index)(TERMindex) = name + flagName(index)(TYPEindex) = name + FlagSet(TERMS | TYPES | (1L << index)) } + /** The conjunction of all flags in given flag set */ + def allOf(flagss: FlagSet*) = { + assert(flagss forall (_.numFlags == 1)) + FlagConjunction(oneOf(flagss: _*).bits) + } + /** The disjunction of all flags in given flag set */ + def oneOf(flagss: FlagSet*) = (Empty /: flagss) (_ | _) + + /** The disjunction of all flags in given flag set */ + def commonFlags(flagss: FlagSet*) = oneOf(flagss map (_.toCommonFlags): _*) + + /** The empty flag set */ final val Empty = FlagSet(0) - final val Error = FlagSet(1 << 32) - final val Frozen = FlagSet(???) - final val Private = FlagSet(???) - final val Package = FlagSet(???) + // Available flags: + + /** Labeled with `private` modifier */ + final val Private = commonFlag(2, "private") + + /** Labeled with `protected` modifier */ + final val Protected = commonFlag(3, "protected") + + /** Labeled with `override` modifier */ + final val Override = commonFlag(4, "override") + + /** A declared, but not defined member */ + final val Deferred = commonFlag(5, "<deferred>") + + /** Labeled with `final` modifier */ + final val Final = commonFlag(6, "final") + + /** A method. !!! needed? */ + final val Method = termFlag(7, "<method>") + + /** Labeled with `abstract` modifier (an abstract class) */ + final val Abstract = typeFlag(8, "abstract") + + /** A trait that has only abstract methods as members + * (and therefore can be represented by a Java interface + */ + final val Interface = typeFlag(9, "interface") + + /** A value or class implementing a module */ + final val Module = commonFlag(10, "module") + final val ModuleObj = Module.toTermFlags + final val ModuleClass = Module.toTypeFlags + + /** Labeled with `implicit` modifier (implicit value) */ + final val Implicit = termFlag(11, "implicit") + + /** Labeled with `sealed` modifier (sealed class) */ + final val Sealed = typeFlag(12, "sealed") + + /** A case class or its companion object */ + final val Case = commonFlag(13, "case") + final val CaseClass = Case.toTypeFlags + final val CaseObj = Case.toTermFlags + + /** Labeled with `lazy` (a lazy val). */ + final val Lazy = termFlag(14, "lazy") + + /** A mutable var */ + final val Mutable = termFlag(14, "mutable") + + /** A (term or type) parameter to a class or method */ + final val Param = commonFlag(15, "<param>") + final val TermParam = Param.toTermFlags + final val TypeParam = Param.toTypeFlags + + /** A value or class representing a package */ + final val Package = commonFlag(16, "<package>") + final val PackageObj = Package.toTermFlags + final val PackageClass = Package.toTypeFlags + + /** A by-name parameter !!! needed? */ + final val ByNameParam = termFlag(17, "<by-name>") + + /** A covariant type variable */ + final val Covariant = typeFlag(17, "<covariant>") + + /** Method is a label. */ + final val Label = termFlag(18, "<label>") + + /** Symbol is a macro */ + final val Macro = commonFlag(???, "<macro>") + + /** A contravariant type variable */ + final val Contravariant = typeFlag(18, "<contravariant>") + + /** Labeled with of abstract & override */ + final val AbsOverride = termFlag(19, "abstract override") + + /** Symbol is local to current class (i.e. private[this] or protected[this] + * pre: Private or Protected are also set + */ + final val Local = commonFlag(20, "<local>") + + /** Symbol is defined by a Java class */ + final val JavaDefined = commonFlag(21, "<java>") + + /** A compiler-generated symbol. which is visible for type-checking + * (compare with artifact) + */ + final val Synthetic = commonFlag(22, "<synthetic>") + + /** Method is assumed to be stable */ + final val Stable = termFlag(23, "<stable>") + + final val Static = commonFlag(24, "<static>") + + /** A value or variable accessor (getter or setter) */ + final val Accessor = termFlag(25, "<accessor>") + + /** A case parameter (or its accessor, or a GADT skolem) */ + final val CaseAccessor = termFlag(26, "<caseaccessor>") + + /** A super accessor */ + final val SuperAccessor = termFlag(27, "<superaccessor>") + + /** A field generated for a primary constructor parameter (no matter if it's a 'val' or not), + * or an accessor of such a field. + */ + final val ParamAccessor = termFlag(28, "<paramaccessor>") + + /** A parameter with a default value */ + final val DefaultParam = termFlag(27, "<defaultparam>") + + /** A trait */ + final val Trait = typeFlag(27, "<trait>") + + /** A bridge method. Set by Erasure */ + final val Bridge = termFlag(28, "<bridge>") + + /** Symbol is initialized to the default value, e.g. var x: T = _ */ + final val DefaultInit = termFlag(29, "<defaultinit>") + + /** An error symbol */ + final val Erroneous = commonFlag(???, "<is-error>") + + /** Denotation is in train of being loaded and completed, flag to catch cyclic dependencies */ + final val Locked = commonFlag(???, "<locked>") + + /** Variable is accessed from nested function. */ + final val Captured = termFlag(???, "<captured>") + + /** Class symbol is defined in this/superclass constructor. */ + final val Inconstructor = typeFlag(???, "<in-constructor>") + + /** Class is not allowed to accept new members because fingerprint of subclass has been taken */ + final val Frozen = typeFlag(???, "<frozen>") + + /** Class has been lifted out to package level, local value has been lifted out to class level */ + final val Lifted = termFlag(???, "<lifted>") + + /** Term member has been mixed in */ + final val MixedIn = termFlag(???, "<mixedin>") + + /** Symbol is a generated specialized member */ + final val Specialized = commonFlag(???, "<specialized>") + + /** Symbol is a Java-style varargs method */ + final val JavaVarargs = termFlag(???, "<varargs>") + + /** Symbol is a Java varargs bridge */ + final val VBridge = termFlag(???, "<vbridge>") + + /** Symbol is a method which should be marked ACC_SYNCHRONIZED */ + final val Synchronized = termFlag(???, "<synchronized>") + + /** Symbol should be ignored when typechecking; will be marked ACC_SYNTHETIC in bytecode */ + final val Artifact = commonFlag(???, "<artifact>") + + /** Symbol is an implementation class */ + final val ImplClass = typeFlag(???, "<implclass>") + +// --------- Combined Flag Sets and Conjunctions ---------------------- + + /** Flags representing source modifiers */ + final val ModifierFlags = commonFlags( + Private, Protected, Abstract, Final, Sealed, Case, Implicit, AbsOverride, Lazy) + + /** Flags representing access rights */ + final val AccessFlags = Private | Protected | Local + + /** These flags are enabled from phase 1 */ + final val InitialFlags: FlagSet = ??? + + /** These flags are not pickled */ + final val FlagsNotPickled = commonFlags( + Erroneous, Lifted, Frozen) + + /** These flags are pickled */ + final val PickledFlags = InitialFlags &~ FlagsNotPickled + + /** A value that's unstable unless complemented with a Stable flag */ + final val UnstableValue = oneOf(Mutable, Method, ByNameParam) + + /** Labeled private[this] */ + final val PrivateLocal = allOf(Private, Local) + + /** Labeled `private` or `protected[local]` */ + final val PrivateOrLocal = oneOf(Private, Local) + + /** Java symbol which is `protected` and `static` */ + final val StaticProtected = allOf(JavaDefined, Protected, Static) + + /** Labeled `protected[this]` */ + final val ProtectedLocal = allOf(Protected, Local) }
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Names.scala b/src/dotty/tools/dotc/core/Names.scala index 291dc2877..30d80a938 100644 --- a/src/dotty/tools/dotc/core/Names.scala +++ b/src/dotty/tools/dotc/core/Names.scala @@ -3,8 +3,8 @@ package core import scala.io.Codec import util.NameTransformer +import Periods._ import Decorators._ -import Contexts._ object Names { @@ -16,7 +16,7 @@ object Names { * 3. Names are intended to be encoded strings. @see dotc.util.NameTransformer. * The encoding will be applied when converting a string to a name. */ - abstract class Name { + abstract class Name extends DotClass { /** The basis in which this name is stored */ val basis: NameTable @@ -59,7 +59,7 @@ object Names { * to other entities (e.g. strings). * One always should use the ==(Name) method instead. */ - final override def equals(that: Any): Boolean = ??? // do not implement + final override def equals(that: Any): Boolean = unsupported("equals") /** The only authorized == method on names */ def == (that: Name): Boolean = ( diff --git a/src/dotty/tools/dotc/core/Periods.scala b/src/dotty/tools/dotc/core/Periods.scala index c2779b4f7..97384e509 100644 --- a/src/dotty/tools/dotc/core/Periods.scala +++ b/src/dotty/tools/dotc/core/Periods.scala @@ -11,10 +11,10 @@ abstract class Periods { self: Context => import Periods._ /** The current phase identifier */ - def phaseId = phaseIdOf(period) + def phaseId = period.phaseId /** The current run identifier */ - def runId = runIdOf(period) + def runId = period.runId /** A new context that differs from the current one in its period */ def withPeriod(pd: Period): Context = @@ -23,18 +23,21 @@ abstract class Periods { self: Context => override val period = pd } + /** A new context that differs from the current one in its phase */ + def withPhase(pid: PhaseId): Context = withPeriod(Period(runId, pid)) + /** Execute `op` at given period */ - def atPeriod[T](pd: Period)(op: Context => T)(implicit ctx: Context) = + def atPeriod[T](pd: Period)(op: Context => T) = op(ctx withPeriod pd) /** Execute `op` at given phase id */ - def atPhase[T](pid: PhaseId)(op: Context => T)(implicit ctx: Context) = - op(ctx withPeriod periodOf(period, pid)) + def atPhase[T](pid: PhaseId)(op: Context => T) = + op(ctx withPhase pid) } object Periods { - /** A period is an ordinal number for a phase in a run. + /** A period is represented by an ordinal number for a phase in a run. * Phases in later runs have higher periods than phases in earlier runs. * Later phases have higher periods than earlier phases in the same run. * Periods are coded (in big endian) as: @@ -43,11 +46,8 @@ object Periods { * runid 21 bits * phase id: 5 bits * unused: 5 bits - */ - type Period = Int - final val NoPeriod = 0 - - /** A period interval is an interval between two periods that share the same runid. + * + * A period interval is an interval between two periods that share the same runid. * It is coded as follows: * * sign, always 0 1 bit @@ -55,8 +55,65 @@ object Periods { * last phase id: 5 bits * #phases before last: 5 bits */ - type Interval = Int - final val Nowhere = NoPeriod + class Period(val code: Int) extends AnyVal { + + /** The run identifier of this period. */ + def runId: Int = code >>> (PhaseWidth * 2) + + /** The phase identifier of this single-phase period. */ + def phaseId: Int = { + assert((code & PhaseMask) == 0) + (code >>> PhaseWidth) & PhaseMask + } + + /** The last phase of this period */ + def lastPhaseId: Int = + (code >>> PhaseWidth) & PhaseMask + + /** The first phase of this period */ + def firstPhaseId = lastPhaseId - (code & PhaseMask) + + /** Does this period contain given period? + * this = A .. B + */ + def contains(that: Period): Boolean = { + val lastDiff = (code - that.code) >>> PhaseWidth + lastDiff + (that.code & PhaseMask ) <= (this.code & PhaseMask) + } + + /** Does this period overlpa with given period? */ + def overlaps(that: Period): Boolean = + this.runId == that.runId && + this.firstPhaseId <= that.lastPhaseId && + that.firstPhaseId <= this.lastPhaseId + + def & (that: Period): Period = + if (this overlaps that) + Period( + this.runId, + this.firstPhaseId max that.firstPhaseId, + this.lastPhaseId min that.lastPhaseId) + else + Nowhere + } + + object Period { + + /** The single-phase period consisting of given run id and phase id */ + def apply(rid: RunId, pid: PhaseId): Period = + new Period(((rid << PhaseWidth) | pid) << PhaseWidth) + + /** The period consisting of given run id, and lo/hi phase ids */ + def apply(rid: RunId, loPid: PhaseId, hiPid: PhaseId): Period = + new Period(((rid << PhaseWidth) | hiPid) << PhaseWidth | (hiPid - loPid)) + + /** The interval consisting of all periods of given run id */ + def allInRun(rid: RunId) = + apply(rid, 0, PhaseMask) + + } + + final val Nowhere = new Period(0) /** An ordinal number for compiler runs. First run has number 1. */ type RunId = Int @@ -71,33 +128,4 @@ object Periods { final val PhaseWidth = 5 final val PhaseMask = (1 << PhaseWidth) - 1 - /** The run identifier of the given period. */ - final def runIdOf(period: Period): RunId = period >>> (PhaseWidth * 2) - - /** The phase identifier of the given period. */ - final def phaseIdOf(period: Period): PhaseId = (period >>> PhaseWidth) & PhaseMask - - /** The last phase of the given interval */ - final def lastPhaseIdOf(ivl: Interval) = phaseIdOf(ivl) - - /** The first phase of the given interval */ - final def firstPhaseIdOf(ivl: Interval) = lastPhaseIdOf(ivl) - (ivl & PhaseMask) - - /** Does given interval contain given period */ - final def containsPeriod(ivl: Interval, period: Period): Boolean = - ((ivl - period) >>> PhaseWidth) <= (ivl & PhaseMask) - - final def intervalsOverlap(ivl1: Interval, ivl2: Interval): Boolean = ??? - - /** The period consisting of given run id and phase id */ - final def periodOf(rid: RunId, pid: PhaseId): Period = - ((rid << PhaseWidth) | pid) << PhaseWidth - - /** The interval consisting of given run id, and lo/hi phase ids */ - final def intervalOf(rid: RunId, loPid: PhaseId, hiPid: PhaseId): Interval = - periodOf(rid, hiPid) | (hiPid - loPid) - - /** The interval consisting of all periods of given run id */ - def allPeriods(rid: RunId): Interval = intervalOf(rid, 0, PhaseMask) - }
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Printers.scala b/src/dotty/tools/dotc/core/Printers.scala new file mode 100644 index 000000000..67d4d3422 --- /dev/null +++ b/src/dotty/tools/dotc/core/Printers.scala @@ -0,0 +1,26 @@ +package dotty.tools.dotc +package core + +import Types._, Symbols._, Contexts._, Scopes._ + +object Printers { + + abstract class Printer { + def show(tp: Type)(implicit ctx: Context): String + def show(sym: Symbol)(implicit ctx: Context): String + def showLocated(sym: Symbol)(implicit ctx: Context): String + def showDef(sym: Symbol)(implicit ctx: Context): String + def show(sc: Scope)(implicit ctx: Context): String + } + + class StdPrinter extends Printer { + def show(tp: Type)(implicit ctx: Context): String = ??? + def show(sym: Symbol)(implicit ctx: Context): String = ??? + def showLocated(sym: Symbol)(implicit ctx: Context): String = ??? + def showDef(sym: Symbol)(implicit ctx: Context): String = ??? + def show(sc: Scope)(implicit ctx: Context): String = + sc.toList.map(_.showDef).mkString("Scope{\n ", ";\n ", "\n}") + } + + +}
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/References.scala b/src/dotty/tools/dotc/core/References.scala deleted file mode 100644 index a5756ebec..000000000 --- a/src/dotty/tools/dotc/core/References.scala +++ /dev/null @@ -1,274 +0,0 @@ -package dotty.tools.dotc -package core - -import Denotations.Denotation -import Contexts.Context -import Names.Name -import Names.TypeName -import Periods.containsPeriod -import Symbols.NoSymbol -import Symbols.Symbol -import Types._ -import Flags._ - - -/** Classes that implement references and sets of references - */ -object References { - - /** The signature of a reference. - * Overloaded references with the same name are distinguished by - * their signatures. A signature is a list of the fully qualified names - * of the type symbols of the erasure of the parameters of the - * reference. For instance a reference to the definition - * - * def f(x: Int)(y: List[String]): String - * - * would have signature - * - * List("scala.Int".toTypeName, "scala.collection.immutable.List".toTypeName) - */ - type Signature = List[TypeName] - - /** The signature of a val or parameterless def, as opposed - * to List(), which is the signature of a zero-parameter def. - */ - val NullSignature = List(Names.EmptyTypeName) - - /** A reference is the result of resolving a name (either simple identifier or select). - * - * Reference has two subclasses: OverloadedRef and SymRef. - * - * A SymRef refers to a `symbol` and a type (`info`) that the symbol has - * when referred through this reference. - * - * References (`SymRef`s) can be combined with `&` and `|`. - * & is conjunction, | is disjunction. - * - * `&` will create an overloaded reference from two - * non-overloaded references if their signatures differ. - * Analogously `|` of two references with different signatures will give - * an empty reference `NoRef`. - * - * A reference might refer to `NoSymbo`. This is the case if the reference - * was produced from a disjunction of two references with different symbols - * and there was no common symbol in a superclass that could substitute for - * both symbols. Here is an example: - * - * Say, we have: - * - * class A { def f: A } - * class B { def f: B } - * val x: A | B = if (???) new A else new B - * val y = x.f - * - * Then the reference of `y` is `SymRef(NoSymbol, A | B)`. - */ - abstract class Reference { - - /** The referenced symbol, exists only for non-overloaded references */ - def symbol: Symbol = - throw new UnsupportedOperationException(this.getClass + ".symbol") - - /** The type info of the reference, exists only for non-overloaded references */ - def info: Type = - throw new UnsupportedOperationException(this.getClass+".info") - - /** Is this a reference to a type symbol? */ - def isType: Boolean = false - - /** The signature of the reference */ - def signature: Signature = - throw new UnsupportedOperationException(this.getClass+".signature") - - /** Resolve overloaded reference to pick the one with the given signature */ - def atSignature(sig: Signature): Reference - - def exists: Boolean = true - - def orElse(that: => Reference) = if (this.exists) this else that - - /** Form a reference by conjoining with reference `that` */ - def & (that: Reference)(implicit ctx: Context): Reference = - if (this eq that) this - else if (!this.exists) that - else if (!that.exists) this - else that match { - case that @ SymRef(sym2, info2) => - val r = mergeRef(this, that) - if (r ne NoRef) r else OverloadedRef(this, that) - case that @ OverloadedRef(ref1, ref2) => - this & ref1 & ref2 - } - - /** Try to merge ref1 and ref2 without adding a new signature. - * If unsuccessful, return NoRef. - */ - private def mergeRef(ref1: Reference, ref2: SymRef)(implicit ctx: Context): Reference = ref1 match { - case ref1 @ OverloadedRef(ref11, ref12) => - val r1 = mergeRef(ref11, ref2) - if (r1 ne NoRef) r1 else mergeRef(ref12, ref2) - case ref1 @ SymRef(sym1, info1) => - if (ref1 eq ref2) ref1 - else if (ref1.signature == ref2.signature) { - val SymRef(sym2, info2) = ref2 - def isEligible(sym1: Symbol, sym2: Symbol) = - if (sym1.isType) !sym1.isClass - else sym1.isConcrete || sym2.isDeferred || !sym2.exists - def normalize(info: Type) = - if (isType) info.bounds else info - val sym1Eligible = isEligible(sym1, sym2) - val sym2Eligible = isEligible(sym2, sym1) - val bounds1 = normalize(info1) - val bounds2 = normalize(info2) - if (sym2Eligible && bounds2 <:< bounds1) ref2 - else if (sym1Eligible && bounds1 <:< bounds2) ref1 - else new JointSymRef(if (sym2Eligible) sym2 else sym1, bounds1 & bounds2) - } else NoRef - } - - def | (that: Reference)(pre: Type)(implicit ctx: Context): Reference = { - - def lubSym(sym1: Symbol, sym2: Symbol): Symbol = { - def qualifies(sym: Symbol) = - (sym isAccessibleFrom pre) && (sym2.owner isSubClass sym.owner) - sym1.allOverriddenSymbols find qualifies getOrElse NoSymbol - } - - def throwError = throw new MatchError(s"orRef($this, $that)") - - if (this eq that) this - else if (!this.exists) this - else if (!that.exists) that - else this match { - case ref1 @ OverloadedRef(ref11, ref12) => - ref1.derivedOverloadedRef((ref11 | that)(pre), (ref12 | that)(pre)) - case _ => - that match { - case ref2 @ OverloadedRef(ref21, ref22) => - ref2.derivedOverloadedRef((this | ref21)(pre), (this | ref22)(pre)) - case ref2: SymRef => - this match { - case ref1: SymRef => - if (ref1.signature != ref2.signature) NoRef - else new JointSymRef(lubSym(ref1.symbol, ref2.symbol), ref1.info | ref2.info) - case _ => - throwError - } - case _ => - throwError - } - } - } - } - - /** The class of overloaded references - * @param variants The overloaded variants indexed by thheir signatures. - */ - case class OverloadedRef(ref1: Reference, ref2: Reference) extends Reference { - def derivedOverloadedRef(r1: Reference, r2: Reference) = - if ((r1 eq ref1) && (r2 eq ref2)) this else OverloadedRef(r1, r2) - def atSignature(sig: Signature): Reference = - ref1.atSignature(sig) orElse ref2.atSignature(sig) - } - - abstract case class SymRef(override val symbol: Symbol, - override val info: Type) extends Reference with RefSet { - override def isType = symbol.isType - override def signature: Signature = { - def sig(tp: Type): Signature = tp match { - case tp: PolyType => - tp.resultType match { - case mt: MethodType => mt.signature - case _ => List() - } - case mt: MethodType => mt.signature - case _ => NullSignature - } - if (isType) NullSignature else sig(info) - } - - def derivedSymRef(s: Symbol, i: Type): SymRef = - if ((s eq symbol) && (i eq info)) this else copy(s, i) - - protected def copy(s: Symbol, i: Type): SymRef = this - - def atSignature(sig: Signature): Reference = - if (sig == signature) this else NoRef - - // ------ RefSet ops ---------------------------------------------- - - def toRef(implicit ctx: Context) = this - def containsSig(sig: Signature)(implicit ctx: Context) = - signature == sig - def filter(p: Symbol => Boolean)(implicit ctx: Context): RefSet = - if (p(symbol)) this else NoRef - def filterDisjoint(refs: RefSet)(implicit ctx: Context): RefSet = - if (refs.containsSig(signature)) NoRef else this - def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet = - if (symbol.hasFlag(flags)) NoRef else this - def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet = - if (symbol.isAccessibleFrom(pre)) this else NoRef - def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet = - derivedSymRef(symbol, info.asSeenFrom(pre, owner)) - } - - class UniqueSymRef(symbol: Symbol, info: Type)(implicit ctx: Context) extends SymRef(symbol, info) { - private val denot = symbol.deref - private val runid = ctx.runId - override protected def copy(s: Symbol, i: Type): SymRef = new UniqueSymRef(s, i) - } - - class JointSymRef(symbol: Symbol, info: Type)(implicit ctx: Context) extends SymRef(symbol, info) { - private val period = ctx.period - override protected def copy(s: Symbol, i: Type): SymRef = new JointSymRef(s, i) - } - - object ErrorRef extends SymRef(NoSymbol, NoType) { - } - - object NoRef extends SymRef(NoSymbol, NoType) { - override def exists = false - } - -// --------------- RefSets ------------------------------------------------- - - trait RefSet { - def exists: Boolean - def toRef(implicit ctx: Context): Reference - def containsSig(sig: Signature)(implicit ctx: Context): Boolean - def filter(p: Symbol => Boolean)(implicit ctx: Context): RefSet - def filterDisjoint(refs: RefSet)(implicit ctx: Context): RefSet - def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet - def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet - def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet - def union(that: RefSet) = - if (!this.exists) that - else if (that.exists) this - else RefUnion(this, that) - } - - case class RefUnion(refs1: RefSet, refs2: RefSet) extends RefSet { - assert(refs1.exists && !refs2.exists) - private def derivedUnion(s1: RefSet, s2: RefSet) = - if (!s1.exists) s2 - else if (!s2.exists) s1 - else if ((s1 eq refs2) && (s2 eq refs2)) this - else new RefUnion(s1, s2) - def exists = true - def toRef(implicit ctx: Context) = refs1.toRef & refs2.toRef - def containsSig(sig: Signature)(implicit ctx: Context) = - (refs1 containsSig sig) || (refs2 containsSig sig) - def filter(p: Symbol => Boolean)(implicit ctx: Context) = - derivedUnion(refs1 filter p, refs2 filter p) - def filterDisjoint(refs: RefSet)(implicit ctx: Context): RefSet = - derivedUnion(refs1 filterDisjoint refs, refs2 filterDisjoint refs) - def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet = - derivedUnion(refs1 filterExcluded flags, refs2 filterExcluded flags) - def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet = - derivedUnion(refs1 filterAccessibleFrom pre, refs2 filterAccessibleFrom pre) - def asSeenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet = - derivedUnion(refs1.asSeenFrom(pre, owner), refs2.asSeenFrom(pre, owner)) - } -} - diff --git a/src/dotty/tools/dotc/core/Scopes.scala b/src/dotty/tools/dotc/core/Scopes.scala index e3d3c29ce..0eadb8cb9 100644 --- a/src/dotty/tools/dotc/core/Scopes.scala +++ b/src/dotty/tools/dotc/core/Scopes.scala @@ -11,7 +11,8 @@ import Names._ import Periods._ import Decorators._ import Contexts._ -import References._ +import Denotations._ +import SymDenotations.NoDenotation object Scopes { @@ -113,7 +114,7 @@ object Scopes { * @param sym ... */ def enterUnique(sym: Symbol)(implicit ctx: Context) { - assert(lookup(sym.name) == NoSymbol, (sym.locatedFullString, lookup(sym.name).locatedFullString)) + assert(lookup(sym.name) == NoSymbol, (sym.showLocated, lookup(sym.name).showLocated)) enter(sym) } @@ -194,12 +195,12 @@ object Scopes { def next(): Symbol = { val r = e.sym; e = lookupNextEntry(e); r } } - /** The reference set of all the symbols with given name in this scope */ - def refsNamed(name: Name)(implicit ctx: Context): RefSet = { - var syms: RefSet = NoRef + /** The denotation set of all the symbols with given name in this scope */ + def denotsNamed(name: Name)(implicit ctx: Context): DenotationSet = { + var syms: DenotationSet = NoDenotation var e = lookupEntry(name) while (e != null) { - syms = syms union e.sym.thisRef + syms = syms union e.sym.denot e = lookupNextEntry(e) } syms @@ -269,11 +270,6 @@ object Scopes { @deprecated("Use `toList.reverse` instead", "2.10.0") def reverse: List[Symbol] = toList.reverse - - override def mkString(start: String, sep: String, end: String) = - toList.map(_.defString).mkString(start, sep, end) - - override def toString(): String = mkString("Scope{\n ", ";\n ", "\n}") } /** Create a new scope */ diff --git a/src/dotty/tools/dotc/core/Substituters.scala b/src/dotty/tools/dotc/core/Substituters.scala index 9036e52c6..a78b31571 100644 --- a/src/dotty/tools/dotc/core/Substituters.scala +++ b/src/dotty/tools/dotc/core/Substituters.scala @@ -5,203 +5,201 @@ import Types._, Symbols._, Contexts._ /** Substitution operations on types. See the corresponding `subst` and * `substThis` methods on class Type for an explanation. */ -object Substituters { - - class SubstOps(val tp: Type) extends AnyVal { - - def subst(from: PolyType, to: PolyType, map: SubstPolyMap = null)(implicit ctx: Context): Type = - tp match { - case tp @ PolyParam(pt, n) => - if (pt eq from) PolyParam(to, n) else tp - case tp: NamedType => - if (tp.symbol.isStatic) tp - else tp.derivedNamedType(tp.prefix.subst(from, to, map), tp.name) - case ThisType(_) - | MethodParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new SubstPolyMap(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } - - def subst(from: MethodType, to: MethodType, map: SubstMethodMap)(implicit ctx: Context): Type = - tp match { - case tp @ MethodParam(mt, n) => - if (mt eq from) MethodParam(to, n) else tp - case tp: NamedType => - if (tp.symbol.isStatic) tp - else tp.derivedNamedType(tp.prefix.subst(from, to, map), tp.name) - case ThisType(_) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new SubstMethodMap(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } - - def subst1(from: Symbol, to: Type, map: Subst1Map)(implicit ctx: Context): Type = { - tp match { - case tp: NamedType => - val sym = tp.symbol - if (tp.prefix eq NoPrefix) { - if (sym eq from) return to - } - if (sym.isStatic) tp - else tp.derivedNamedType(tp.prefix.subst1(from, to, map), tp.name) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new Subst1Map(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } +trait Substituters { this: Context => + + final def subst(tp: Type, from: BindingType, to: BindingType, map: SubstBindingMap): Type = + tp match { + case tp: BoundType => + if (tp.binder eq from) tp.copy(to.asInstanceOf[tp.BT]) else tp + case tp: NamedType => + if (tp.symbol.isStatic) tp + else tp.derivedNamedType(subst(tp.prefix, from, to, map), tp.name) + case _: ThisType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + subst(tp.parent, from, to, map), + tp.name1, + subst(tp.info1, from, to, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + subst(tp.parent, from, to, map), + tp.name1, + subst(tp.info1, from, to, map), + tp.name2, + subst(tp.info2, from, to, map)) + case _ => + (if (map != null) map else new SubstBindingMap(from, to)) + .mapOver(tp) } - def subst2(from1: Symbol, to1: Type, from2: Symbol, to2: Type, map: Subst2Map)(implicit ctx: Context): Type = { - tp match { - case tp: NamedType => - val sym = tp.symbol - if (tp.prefix eq NoPrefix) { - if (sym eq from1) return to1 - if (sym eq from2) return to2 - } - if (sym.isStatic) tp - else tp.derivedNamedType(tp.prefix.subst2(from1, to1, from2, to2, map), tp.name) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new Subst2Map(from1, to1, from2, to2) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } + final def subst1(tp: Type, from: Symbol, to: Type, map: Subst1Map): Type = { + tp match { + case tp: NamedType => + val sym = tp.symbol + if (tp.prefix eq NoPrefix) { + if (sym eq from) return to + } + if (sym.isStatic) tp + else tp.derivedNamedType(subst1(tp.prefix, from, to, map), tp.name) + case _: ThisType | _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + subst1(tp.parent, from, to, map), + tp.name1, + subst1(tp.info1, from, to, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + subst1(tp.parent, from, to, map), + tp.name1, + subst1(tp.info1, from, to, map), + tp.name2, + subst1 (tp.info2, from, to, map)) + case _ => + (if (map != null) map else new Subst1Map(from, to)) + .mapOver(tp) } + } - def subst(from: List[Symbol], to: List[Type], map: SubstMap)(implicit ctx: Context): Type = { - tp match { - case tp: NamedType => - val sym = tp.symbol - if (tp.prefix eq NoPrefix) { - var fs = from - var ts = to - while (fs.nonEmpty) { - if (fs.head eq sym) return ts.head - fs = fs.tail - ts = ts.tail - } - } - if (sym.isStatic) tp - else tp.derivedNamedType(tp.prefix.subst(from, to, map), tp.name) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new SubstMap(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } + final def subst2(tp: Type, from1: Symbol, to1: Type, from2: Symbol, to2: Type, map: Subst2Map): Type = { + tp match { + case tp: NamedType => + val sym = tp.symbol + if (tp.prefix eq NoPrefix) { + if (sym eq from1) return to1 + if (sym eq from2) return to2 + } + if (sym.isStatic) tp + else tp.derivedNamedType(subst2(tp.prefix, from1, to1, from2, to2, map), tp.name) + case _: ThisType | _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + subst2(tp.parent, from1, to1, from2, to2, map), + tp.name1, + subst2(tp.info1, from1, to1, from2, to2, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + subst2(tp.parent, from1, to1, from2, to2, map), + tp.name1, + subst2(tp.info1, from1, to1, from2, to2, map), + tp.name2, + subst2(tp.info2, from1, to1, from2, to2, map)) + case _ => + (if (map != null) map else new Subst2Map(from1, to1, from2, to2)) + .mapOver(tp) } + } - def substThis(from: ClassSymbol, to: Type, map: SubstThisMap)(implicit ctx: Context): Type = - tp match { - case tp @ ThisType(clazz) => - if (clazz eq from) to else tp - case tp: NamedType => - if (tp.symbol.isStatic) tp - else tp.derivedNamedType(tp.prefix.substThis(from, to, map), tp.name) - case MethodParam(_, _) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new SubstThisMap(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp - } - } - - def substThis(from: RefinedType, to: Type, map: SubstRefinedThisMap)(implicit ctx: Context): Type = - tp match { - case tp @ RefinedThis(rt) => - if (rt eq from) to else tp - case tp: NamedType => - if (tp.symbol.isStatic) tp - else tp.derivedNamedType(tp.prefix.substThis(from, to, map), tp.name) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) - | NoPrefix => tp - case _ => - val substMap = if (map != null) map else new SubstRefinedThisMap(from, to) - tp match { - case tp: AppliedType => - tp.derivedAppliedType( - substMap(tp.tycon), tp.typeArgs mapConserve substMap) - case _ => - substMap mapOver tp + final def subst(tp: Type, from: List[Symbol], to: List[Type], map: SubstMap): Type = { + tp match { + case tp: NamedType => + val sym = tp.symbol + if (tp.prefix eq NoPrefix) { + var fs = from + var ts = to + while (fs.nonEmpty) { + if (fs.head eq sym) return ts.head + fs = fs.tail + ts = ts.tail } - } + } + if (sym.isStatic) tp + else tp.derivedNamedType(subst(tp.prefix, from, to, map), tp.name) + case _: ThisType | _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + subst(tp.parent, from, to, map), + tp.name1, + subst(tp.info1, from, to, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + subst(tp.parent, from, to, map), + tp.name1, + subst(tp.info1, from, to, map), + tp.name2, + subst(tp.info2, from, to, map)) + case _ => + (if (map != null) map else new SubstMap(from, to)) + .mapOver(tp) + } } - class SubstPolyMap(from: PolyType, to: PolyType)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp.subst(from, to, this) - } + final def substThis(tp: Type, from: ClassSymbol, to: Type, map: SubstThisMap): Type = + tp match { + case tp @ ThisType(clazz) => + if (clazz eq from) to else tp + case tp: NamedType => + if (tp.symbol.isStatic) tp + else tp.derivedNamedType(substThis(tp.prefix, from, to, map), tp.name) + case _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + substThis(tp.parent, from, to, map), + tp.name1, + substThis(tp.info1, from, to, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + substThis(tp.parent, from, to, map), + tp.name1, + substThis(tp.info1, from, to, map), + tp.name2, + substThis(tp.info2, from, to, map)) + case _ => + (if (map != null) map else new SubstThisMap(from, to)) + .mapOver(tp) + } + + final def substThis(tp: Type, from: RefinedType, to: Type, map: SubstRefinedThisMap): Type = + tp match { + case tp @ RefinedThis(rt) => + if (rt eq from) to else tp + case tp: NamedType => + if (tp.symbol.isStatic) tp + else tp.derivedNamedType(substThis(tp.prefix, from, to, map), tp.name) + case _: ThisType | _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + substThis(tp.parent, from, to, map), + tp.name1, + substThis(tp.info1, from, to, map)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + substThis(tp.parent, from, to, map), + tp.name1, + substThis(tp.info1, from, to, map), + tp.name2, + substThis(tp.info2, from, to, map)) + case _ => + (if (map != null) map else new SubstRefinedThisMap(from, to)) + .mapOver(tp) + } - class SubstMethodMap(from: MethodType, to: MethodType)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp.subst(from, to, this) + final class SubstBindingMap(from: BindingType, to: BindingType) extends TypeMap { + def apply(tp: Type) = subst(tp, from, to, this) } - class Subst1Map(from: Symbol, to: Type)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp.subst1(from, to, this) + final class Subst1Map(from: Symbol, to: Type) extends TypeMap { + def apply(tp: Type) = subst1(tp, from, to, this) } - class Subst2Map(from1: Symbol, to1: Type, from2: Symbol, to2: Type)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp.subst2(from1, to1, from2, to2, this) + final class Subst2Map(from1: Symbol, to1: Type, from2: Symbol, to2: Type) extends TypeMap { + def apply(tp: Type) = subst2(tp, from1, to1, from2, to2, this) } - class SubstMap(from: List[Symbol], to: List[Type])(implicit ctx: Context) extends TypeMap { - def apply(tp: Type): Type = tp.subst(from, to, this) + final class SubstMap(from: List[Symbol], to: List[Type]) extends TypeMap { + def apply(tp: Type): Type = subst(tp, from, to, this) } - class SubstThisMap(from: ClassSymbol, to: Type)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type): Type = tp.substThis(from, to, this) + final class SubstThisMap(from: ClassSymbol, to: Type) extends TypeMap { + def apply(tp: Type): Type = substThis(tp, from, to, this) } - class SubstRefinedThisMap(from: RefinedType, to: Type)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type): Type = tp.substThis(from, to, this) + final class SubstRefinedThisMap(from: RefinedType, to: Type) extends TypeMap { + def apply(tp: Type): Type = substThis(tp, from, to, this) } }
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala new file mode 100644 index 000000000..8dbf43f00 --- /dev/null +++ b/src/dotty/tools/dotc/core/SymDenotations.scala @@ -0,0 +1,662 @@ +package dotty.tools.dotc +package core + +import Periods._, Contexts._, Symbols._, Denotations._, Names._, Annotations._ +import Types._, Flags._, Decorators._, Transformers._ +import Scopes.Scope +import collection.mutable +import collection.immutable.BitSet +import scala.reflect.io.AbstractFile +import Decorators.SymbolIteratorDecorator +import annotation.tailrec + +object SymDenotations { + + /** A denotation represents the contents of a definition + * during a period. + */ + abstract class SymDenotation(initFlags: FlagSet) extends SingleDenotation { + + def owner: Symbol + + def name: Name + + def symbol: Symbol + + def info: Type + + private[this] var _flags: FlagSet = initFlags + + def flags: FlagSet = _flags + + def flags_=(flags: FlagSet): Unit = + _flags |= flags + + def setFlags(flags: FlagSet): Unit = + _flags |= flags + + def resetFlags(flags: FlagSet): Unit = + _flags &~= flags + + private[this] var _privateWithin: Symbol = NoSymbol + + def privateWithin: Symbol = _privateWithin + + def privateWithin_=(sym: Symbol): Unit = + _privateWithin = sym + + final def isLoaded = _privateWithin != null + + private[this] var _annotations: List[Annotation] = Nil + + def annotations: List[Annotation] = _annotations + + def annotations_=(annots: List[Annotation]): Unit = + _annotations = annots + + def hasAnnotation(cls: Symbol) = dropOtherAnnotations(annotations, cls).nonEmpty + + @tailrec + private def dropOtherAnnotations(anns: List[Annotation], cls: Symbol): List[Annotation] = anns match { + case ann :: rest => if (ann matches cls) anns else dropOtherAnnotations(rest, cls) + case Nil => Nil + } + + final def isCompleted = _annotations != null + + /** is this denotation a class? */ + final def isClass: Boolean = symbol.isInstanceOf[ClassSymbol] + + /** Special case tests for flags that are known a-priori and do not need loading + * flags. + */ + final def isModule = _flags is Module + final def isModuleObj = _flags is ModuleObj + final def isModuleClass = _flags is ModuleClass + final def isPackage = _flags is Package + final def isPackageObj = _flags is PackageObj + final def isPackageClass = _flags is PackageClass + + /** is this denotation a method? */ + //def isMethod: Boolean = false + + def isSubClass(cls: Symbol)(implicit ctx: Context) = false + + def isNonBottomSubClass(cls: Symbol)(implicit ctx: Context) = false + + final def isSubClassOrCompanion(base: Symbol)(implicit ctx: Context): Boolean = + isNonBottomSubClass(base) || + isModuleClass && linkedClass.isNonBottomSubClass(base) + + final def enclosingSubClass(implicit ctx: Context) = { + val thissym = symbol + ctx.owner.ownersIterator.findSymbol(_.isSubClass(thissym)) + } + + /** is this symbol the result of an erroneous definition? */ + def isError: Boolean = false + + final def ownersIterator(implicit ctx: Context) = new Iterator[Symbol] { + private var current = symbol + def hasNext = current.exists + def next: Symbol = { + val result = current + current = current.owner + result + } + } + + final def hasTransOwner(sym: Symbol)(implicit ctx: Context): Boolean = { + var o = symbol + while ((o ne sym) && (o ne NoSymbol)) o = o.owner + (o eq sym) + } + + def withType(tp: Type): SymDenotation = ??? + + override protected def copy(s: Symbol, i: Type): SingleDenotation = new UniqueRefDenotation(s, i, validFor) + + def moduleClass(implicit ctx: Context): Symbol = + if (this.isModuleObj) info.typeSymbol else NoSymbol + + /** Desire to re-use the field in ClassSymbol which stores the source + * file to also store the classfile, but without changing the behavior + * of sourceFile (which is expected at least in the IDE only to + * return actual source code.) So sourceFile has classfiles filtered out. + */ + private def sourceFileOnly(file: AbstractFile): AbstractFile = + if ((file eq null) || (file.path endsWith ".class")) null else file + + private def binaryFileOnly(file: AbstractFile): AbstractFile = + if ((file eq null) || !(file.path endsWith ".class")) null else file + + final def topLevelClass(implicit ctx: Context): Symbol = + if (!(owner.isPackageClass)) owner.topLevelClass + else if (isClass) symbol + else moduleClass + + final def enclosingPackage(implicit ctx: Context): Symbol = + if (isPackageClass) symbol else owner.enclosingPackage + + def associatedFile(implicit ctx: Context): AbstractFile = topLevelClass.associatedFile + final def binaryFile(implicit ctx: Context): AbstractFile = binaryFileOnly(associatedFile) + final def sourceFile(implicit ctx: Context): AbstractFile = sourceFileOnly(associatedFile) + + /** Is this symbol a type or stable term? */ + final def isStable(implicit ctx: Context) = !( + isTerm && + this.is(UnstableValue, butNot = Stable) || + info.isVolatile && !hasAnnotation(defn.uncheckedStableClass) + ) + + final def matchingSymbol(inClass: Symbol, site: Type)(implicit ctx: Context): Symbol = { + var denot = inClass.info.nonPrivateDecl(name) + if (denot.isTerm) { + val targetType = site.memberInfo(this) + if (denot.isOverloaded) + denot = denot.atSignature(targetType.signature) + if (!(site.memberInfo(denot.asInstanceOf[SymDenotation]) matches targetType)) + denot = NoDenotation + } + denot.symbol + } + + final def overriddenSymbol(inClass: ClassSymbol)(implicit ctx: Context): Symbol = + if (owner isSubClass inClass) matchingSymbol(inClass, owner.thisType) + else NoSymbol + + final def allOverriddenSymbols(implicit ctx: Context): Iterator[Symbol] = + info.baseClasses.tail.iterator map overriddenSymbol filter (_.exists) + + /** Is this symbol defined in the same scope and compilation unit as `that` symbol? */ + private def isCoDefinedWith(that: Symbol)(implicit ctx: Context) = + (this.owner == that.owner) && + ( !(this.owner.isPackageClass) + || (this.sourceFile == null) + || (that.sourceFile == null) + || (this.sourceFile.path == that.sourceFile.path) // Cheap possibly wrong check, then expensive normalization + || (this.sourceFile.canonicalPath == that.sourceFile.canonicalPath) + ) + + def companionModule(implicit ctx: Context): Symbol = + owner.info.decl(name.toTermName).filter(_.isModule).symbol + + def companionClass(implicit ctx: Context): Symbol = + owner.info.decl(name.toTypeName).filter(_.isClass).symbol + + def linkedClass(implicit ctx: Context): Symbol = + if (this.isModuleClass) companionClass + else if (this.isClass) companionModule.moduleClass + else NoSymbol + + final def accessBoundary(base: Symbol)(implicit ctx: Context): Symbol = { + val fs = flags + if (fs is PrivateOrLocal) owner + else if (fs is StaticProtected) defn.RootClass + else if (privateWithin.exists && !ctx.phase.erasedTypes) privateWithin + else if (fs is Protected) base + else defn.RootClass + } + + final def isContainedIn(boundary: Symbol)(implicit ctx: Context): Boolean = + if (symbol eq boundary) true + else if (!this.exists || + (this.isPackageClass) && !(boundary.isPackageClass)) false + else owner.isContainedIn(boundary) + + def isAsAccessibleAs(that: Symbol)(implicit ctx: Context): Boolean = + (that.accessBoundary(NoSymbol) isContainedIn this.accessBoundary(NoSymbol)) && + (this.isStable || !that.isStable) + + def isAccessibleFrom(pre: Type, superAccess: Boolean = false)(implicit ctx: Context): Boolean = { + + def accessWithinLinked(boundary: Symbol) = { + val linked = boundary.linkedClass + (linked ne NoSymbol) && accessWithin(linked) + } + + /** Are we inside definition of `boundary`? */ + def accessWithin(boundary: Symbol) = + owner.hasTransOwner(boundary) && + (!(this is JavaDefined) || + owner.enclosingPackage == boundary.enclosingPackage) + + def isCorrectThisType(pre: Type): Boolean = pre match { + case ThisType(pclazz) => + (pclazz eq owner) || + (this is Protected) && pclazz.isNonBottomSubClass(owner) + case _ => false + } + + /** Is protected access to target symbol permitted? */ + def isProtectedAccessOK = { + def fail(diagnostics: () => String): Boolean = { + ctx match { + case ctx: DiagnosticsContext => ctx.diagnostics = diagnostics + case _ => + } + false + } + val cls = owner.enclosingSubClass + if (!cls.exists) + fail(() => + s"""Access to protected $this not permitted because + |enclosing ${ctx.enclClass.owner.showLocated} is not a subclass of + |${owner.showLocated} where target is defined""".stripMargin) + else if (!(isType || // allow accesses to types from arbitrary subclasses fixes #4737 + pre.widen.typeSymbol.isSubClassOrCompanion(cls) || + cls.isModuleClass && + pre.widen.typeSymbol.isSubClassOrCompanion(cls.linkedClass))) + fail(() => + s"""Access to protected $show not permitted because + |prefix type ${pre.widen.show} does not conform to + |${cls.showLocated} where the access takes place""".stripMargin) + else true + } + + (pre == NoPrefix) || { + val boundary = accessBoundary(owner) + + ( (boundary.isTerm + || (boundary eq defn.RootClass)) + || (accessWithin(boundary) || accessWithinLinked(boundary)) && + ( !(this is Local) + || (owner is ImplClass) // allow private local accesses to impl class members + || isCorrectThisType(pre) + ) + || (this is Protected) && + ( superAccess + || pre.isInstanceOf[ThisType] + || ctx.phase.erasedTypes + || isProtectedAccessOK + ) + ) + } + } + + def isNonValueClass(implicit ctx: Context): Boolean = + isClass && !isSubClass(defn.AnyValClass) + + def show(implicit ctx: Context): String = ??? + def showLocated(implicit ctx: Context): String = ??? + } + + class CompleteSymDenotation( + val symbol: Symbol, + val owner: Symbol, + val name: Name, + initFlags: FlagSet, + val info: Type + ) extends SymDenotation(initFlags) + + trait LazyCompletion extends SymDenotation { + privateWithin = null + annotations = null + + override final def flags = { + if (!isLoaded) tryLoad() + super.flags + } + + override final def privateWithin = { + if (!isLoaded) tryLoad() + super.privateWithin + } + + override final def annotations: List[Annotation] = { + val annots = super.annotations + if (annots != null) annots else { tryComplete(); annotations } + } + + protected def tryLoad(): Unit = try { + if (flags is Locked) throw new CyclicReference(symbol) + setFlags(Locked) + load() + } catch { + case ex: CyclicReference => handleCycle() + } finally { + flags &~= Locked + } + + protected def tryComplete() = try { + if (flags is Locked) throw new CyclicReference(symbol) + complete() + } catch { + case ex: CyclicReference => handleCycle() + } finally { + flags &~= Locked + } + + protected def handleCycle(): Unit + protected def load(): Unit + protected def complete(): Unit + } + + abstract class LazySymDenotation( + val symbol: Symbol, + val owner: Symbol, + val name: Name, + initFlags: FlagSet + ) extends SymDenotation(initFlags) with LazyCompletion { + + private var currentInfo: Type = null + + override def info = { + if (currentInfo == null) complete() + currentInfo + } + } + + abstract class ClassDenotation(initFlags: FlagSet, assocFile: AbstractFile)(implicit ctx: Context) + extends SymDenotation(initFlags) { + import NameFilter._ + import util.LRU8Cache + + val symbol: ClassSymbol + + def typeParams: List[TypeSymbol] + + def parents: List[TypeRef] + + def decls: Scope + + val info = ClassInfo(owner.thisType, this) + + override def associatedFile(implicit ctx: Context): AbstractFile = assocFile + + private var memberCacheVar: LRU8Cache[Name, DenotationSet] = null + + private def memberCache: LRU8Cache[Name, DenotationSet] = { + if (memberCacheVar == null) memberCacheVar = new LRU8Cache + memberCacheVar + } + + private var thisTypeCache: ThisType = null + + def thisType(implicit ctx: Context): Type = { + if (thisTypeCache == null) + thisTypeCache = ThisType(symbol) + thisTypeCache + } + + private var typeConstructorCache: Type = null + + def typeConstructor(implicit ctx: Context): Type = { + if (typeConstructorCache == null) + typeConstructorCache = NamedType(thisType, symbol.name) + typeConstructorCache + } + + /* + private var typeTemplateCache: Type = null + + def typeTemplate(implicit ctx: Context): Type = { + if (typeTemplateCache == null) + AppliedType.make(typeConstructor, typeParams map (_.typeConstructor)) + typeTemplateCache + } +*/ + private var baseClassesVar: List[ClassSymbol] = null + private var superClassBitsVar: BitSet = null + + private def computeSuperClassBits(implicit ctx: Context): Unit = { + val seen = new mutable.BitSet + val locked = new mutable.BitSet + def addBaseClasses(bcs: List[ClassSymbol], to: List[ClassSymbol]) + : List[ClassSymbol] = bcs match { + case bc :: bcs1 => + val id = bc.superId + if (seen contains id) to + else if (locked contains id) throw new CyclicReference(symbol) + else { + locked += id + val bcs1added = addBaseClasses(bcs1, to) + seen += id + if (bcs1added eq bcs1) bcs else bc :: bcs1added + } + case _ => + to + } + def addParentBaseClasses(ps: List[Type], to: List[ClassSymbol]): List[ClassSymbol] = ps match { + case p :: ps1 => + addBaseClasses(p.baseClasses, addParentBaseClasses(ps1, to)) + case _ => + to + } + baseClassesVar = symbol :: addParentBaseClasses(parents, Nil) + superClassBitsVar = ctx.root.uniqueBits.findEntryOrUpdate(seen.toImmutable) + } + + def superClassBits(implicit ctx: Context): BitSet = { + if (superClassBitsVar == null) computeSuperClassBits + superClassBitsVar + } + + def baseClasses(implicit ctx: Context): List[ClassSymbol] = { + if (baseClassesVar == null) computeSuperClassBits + baseClassesVar + } + + final override def isNonBottomSubClass(cls: Symbol)(implicit ctx: Context): Boolean = + (symbol eq cls) || + (superClassBits contains cls.superId) || + (this is Erroneous) || + (cls is Erroneous) && cls.isClass + + final override def isSubClass(cls: Symbol)(implicit ctx: Context) = + isNonBottomSubClass(cls) || + cls.isClass && ((symbol eq defn.NothingClass) || (symbol eq defn.NullClass)) + + private var definedFingerPrintCache: FingerPrint = null + + private def computeDefinedFingerPrint(implicit ctx: Context): FingerPrint = { + var bits = newNameFilter + var e = decls.lastEntry + while (e != null) { + includeName(bits, name) + e = e.prev + } + var ps = parents + while (ps.nonEmpty) { + val parent = ps.head.typeSymbol + parent.denot match { + case classd: ClassDenotation => + includeFingerPrint(bits, classd.definedFingerPrint) + parent.denot.setFlags(Frozen) + case _ => + } + ps = ps.tail + } + definedFingerPrintCache = bits + bits + } + + /** Enter a symbol in current scope. + * Note: We require that this does not happen after the first time + * someone does a findMember on a subclass. + */ + def enter(sym: Symbol)(implicit ctx: Context) = { + require(!(this is Frozen)) + decls enter sym + if (definedFingerPrintCache != null) + includeName(definedFingerPrintCache, sym.name) + if (memberCacheVar != null) + memberCache invalidate sym.name + } + + /** Delete symbol from current scope. + * Note: We require that this does not happen after the first time + * someone does a findMember on a subclass. + */ + def delete(sym: Symbol)(implicit ctx: Context) = { + require(!(this is Frozen)) + decls unlink sym + if (definedFingerPrintCache != null) + computeDefinedFingerPrint + if (memberCacheVar != null) + memberCache invalidate sym.name + } + + def definedFingerPrint(implicit ctx: Context): FingerPrint = { + val fp = definedFingerPrintCache + if (fp != null) fp else computeDefinedFingerPrint + } + + final def membersNamed(name: Name)(implicit ctx: Context): DenotationSet = { + var denots: DenotationSet = memberCache lookup name + if (denots == null) { + if (containsName(definedFingerPrint, name)) { + val ownDenots = decls.denotsNamed(name) + denots = ownDenots + var ps = parents + while (ps.nonEmpty) { + val parentSym = ps.head.typeSymbol + parentSym.denot match { + case parentd: ClassDenotation => + denots = denots union + parentd.membersNamed(name) + .filterExcluded(Flags.Private) + .asSeenFrom(thisType, parentSym) + .filterDisjoint(ownDenots) + case _ => + } + } + } else { + denots = NoDenotation + } + memberCache enter (name, denots) + } + denots + } + + private var baseTypeCache: java.util.HashMap[CachedType, Type] = null + private var baseTypeValid: RunId = NoRunId + + final def baseTypeOf(tp: Type)(implicit ctx: Context): Type = { + + def computeBaseTypeOf(tp: Type): Type = tp match { + case tp: TypeProxy => + baseTypeOf(tp.underlying) + case AndType(tp1, tp2) => + baseTypeOf(tp1) & baseTypeOf(tp2) + case OrType(tp1, tp2) => + baseTypeOf(tp1) | baseTypeOf(tp2) + case tp @ ClassInfo(pre, classd) => + def reduce(bt: Type, ps: List[Type]): Type = ps match { + case p :: ps1 => reduce(bt & baseTypeOf(p), ps1) + case _ => bt + } + if (classd.symbol == symbol) tp.typeConstructor // was: typeTemplate + else reduce(NoType, classd.parents).substThis(classd.symbol, tp.prefix) + } + + if (symbol.isStaticMono) symbol.typeConstructor + else tp match { + case tp: CachedType => + if (baseTypeValid != ctx.runId) { + baseTypeCache = new java.util.HashMap[CachedType, Type] + baseTypeValid = ctx.runId + } + var basetp = baseTypeCache get tp + if (basetp == null) { + baseTypeCache.put(tp, NoType) + basetp = computeBaseTypeOf(tp) + baseTypeCache.put(tp, basetp) + } else if (basetp == NoType) { + throw new CyclicReference(symbol) + } + basetp + case _ => + computeBaseTypeOf(tp) + } + } + + private var memberNamesCache: Map[NameFilter, Set[Name]] = Map() + + def memberNames(keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = + memberNamesCache get keepOnly match { + case Some(names) => + names + case _ => + val inheritedNames = (parents flatMap (_.memberNames(thisType, keepOnly))).toSet + val ownNames = decls.iterator map (_.name) + val candidates = inheritedNames ++ ownNames + val names = candidates filter (keepOnly(thisType, _)) + memberNamesCache += (keepOnly -> names) + names + } + } + + class CompleteClassDenotation( + val symbol: ClassSymbol, + val owner: Symbol, + val name: Name, + initFlags: FlagSet, + val typeParams: List[TypeSymbol], + val parents: List[TypeRef], + val decls: Scope, + assocFile: AbstractFile = null + )(implicit ctx: Context) extends ClassDenotation(initFlags, assocFile) + + abstract class LazyClassDenotation( + val symbol: ClassSymbol, + val owner: Symbol, + val name: Name, + initFlags: FlagSet, + assocFile: AbstractFile = null + )(implicit ctx: Context) extends ClassDenotation(initFlags, assocFile) with LazyCompletion { + + protected var _typeParams: List[TypeSymbol] = null + protected var _parents: List[TypeRef] = null + protected var _decls: Scope = null + + final def typeParams: List[TypeSymbol] = { + val tparams = _typeParams + if (tparams != null) tparams else { tryLoad(); typeParams } + } + + final def parents: List[TypeRef] = { + val ps = _parents + if (ps != null) ps else { tryComplete(); parents } + } + + final def decls: Scope = { + val ds = _decls + if (ds != null) ds else { tryComplete(); decls } + } + } + + object NoDenotation extends SymDenotation(Flags.Empty) { + override def symbol: Symbol = NoSymbol + override def owner: Symbol = throw new AssertionError("NoDenotation.owner") + override def name: Name = BootNameTable.newTermName("<none>") + override def info: Type = NoType + } + + object NameFilter { + final val WordSizeLog = 6 + final val DefinedNamesWords = 16 + final val DefinedNamesSize = DefinedNamesWords << WordSizeLog + final val DefinedNamesMask = DefinedNamesSize - 1 + + type FingerPrint = Array[Long] + + def includeName(bits: FingerPrint, name: Name): Unit = { + val hash = name.start & DefinedNamesMask + bits(hash >> 6) |= (1 << hash) + } + + def includeFingerPrint(bits1: FingerPrint, bits2: FingerPrint): Unit = + for (i <- 0 until DefinedNamesWords) bits1(i) |= bits2(i) + + def containsName(bits: FingerPrint, name: Name): Boolean = { + val hash = name.start & DefinedNamesMask + (bits(hash >> 6) & (1 << hash)) != 0 + } + + def newNameFilter: FingerPrint = new Array[Long](DefinedNamesWords) + } + + implicit def toFlagSet(denot: SymDenotation): FlagSet = denot.flags + +} diff --git a/src/dotty/tools/dotc/core/SymTransformers.scala b/src/dotty/tools/dotc/core/SymTransformers.scala deleted file mode 100644 index ec2e4d357..000000000 --- a/src/dotty/tools/dotc/core/SymTransformers.scala +++ /dev/null @@ -1,39 +0,0 @@ -package dotty.tools.dotc.core - -import Periods._, Denotations._, Contexts._ -import java.lang.AssertionError - -trait DenotationTransformers { self: RootContext => - - import DenotationTransformers._ - - def lastPhaseId: PhaseId - - private val nxTransformer = - Array.fill[DenotationTransformer](lastPhaseId + 1)(NoTransformer) - - object NoTransformer extends DenotationTransformer { - val phaseId = lastPhaseId + 1 - def transform(enot: Denotation): Denotation = - throw new AssertionError("NoTransformer.transform") - } - - def install(pid: PhaseId, trans: DenotationTransformer): Unit = { - if ((pid > NoPhaseId) && (nxTransformer(pid).phaseId > pid)) { - nxTransformer(pid) = trans - install(pid - 1, trans) - } - } - - def nextTransformer(i: Int) = nxTransformer(i) -} - -object DenotationTransformers { - - abstract class DenotationTransformer { - val phaseId: PhaseId - def transform(denot: Denotation): Denotation - } - - -}
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala index 6073fa230..84ffc53a7 100644 --- a/src/dotty/tools/dotc/core/Symbols.scala +++ b/src/dotty/tools/dotc/core/Symbols.scala @@ -2,195 +2,181 @@ package dotty.tools.dotc package core import Periods._ -import DenotationTransformers._ +import Transformers._ import Names._ import Flags._ import java.lang.AssertionError import Decorators._ import Symbols._ import Contexts._ -import Denotations._ -import Types._ -import References.{Reference, SymRef, UniqueSymRef, OverloadedRef} +import SymDenotations._ +import Types._, Annotations._ +import Denotations.{Denotation, SingleDenotation, MultiDenotation} import collection.mutable +import reflect.io.AbstractFile -trait Symbols { self: Context => +object Symbols { - import Symbols._ - // Infrastructure to assign unique superclass idents to class symbols that are superclasses of - // some other class + /** A Symbol represents a Scala definition/declaration or a package. + */ + abstract class Symbol(denotf: Symbol => SymDenotation) { - private final val InitialSuperIdsSize = 4096 + /** Is symbol different from NoSymbol? */ + def exists = true - /** A map from a superclass id to the class that has it */ - private var classOfId = Array.ofDim[ClassSymbol](InitialSuperIdsSize) + /** This symbol, if it exists, otherwise the result of evaluating `that` */ + def orElse(that: => Symbol) = if (exists) this else that - /** A map from a superclass to its superclass id */ - private val superIdOfClass = new mutable.HashMap[ClassSymbol, Int] + def filter(p: Symbol => Boolean): Symbol = if (p(this)) this else NoSymbol - /** The last allocate superclass id */ - private var lastSuperId = -1 + /** The last denotation of this symbol */ + private[this] var lastDenot: SymDenotation = denotf(this) - /** Allocate and return next free superclass id */ - private def nextSuperId: Int = { lastSuperId += 1; lastSuperId } -} + final def denot(implicit ctx: Context): SymDenotation = { + var denot = lastDenot + if (!(denot.validFor contains ctx.period)) denot = denot.current.asInstanceOf[SymDenotation] + denot + } -object Symbols { + def isType: Boolean = false + def isTerm: Boolean = false + def isClass: Boolean = false + /** Special case tests for flags that are known a-priori and do not need loading + * flags. + */ + def isModule(implicit ctx: Context) = denot.isModule + def isModuleObj(implicit ctx: Context) = denot.isModuleObj + def isModuleClass(implicit ctx: Context) = denot.isModuleClass + def isPackage(implicit ctx: Context) = denot.isPackage + def isPackageObj(implicit ctx: Context) = denot.isPackageObj + def isPackageClass(implicit ctx: Context) = denot.isPackageClass + + /** A unique, densely packed integer tag for each class symbol, -1 + * for all other symbols. To save memory, this method + * should be called only if class is a super class of some other class. + */ + def superId: Int = -1 - /** - * A SymRef is a period-dependent reference to a denotation. - * Given a period, its `deref` method resolves to a Symbol. - */ - abstract class Symbol { +// --------- Forwarders for sym methods -------------------------- - def overriddenSymbol(inclass: ClassSymbol)(implicit ctx: Context): Symbol = - if (owner isSubClass inclass) ??? - else NoSymbol + /** The current owner of this symbol */ + final def owner(implicit ctx: Context): Symbol = denot.owner - def isProtected: Boolean = ??? - def isStable: Boolean = ??? - def accessBoundary: ClassSymbol = ??? - def isContainedIn(boundary: ClassSymbol) = ??? - def baseClasses: List[ClassSymbol] = ??? - def exists = true + /** The current name of this symbol */ + final def name(implicit ctx: Context): Name = denot.name + /** The current type info of this symbol */ + final def info(implicit ctx: Context): Type = denot.info - def orElse(that: => Symbol) = if (exists) this else that + /** The current flag set of this symbol */ + final def flags(implicit ctx: Context): FlagSet = denot.flags + + /** The current privateWithin boundary of this symbol, NoSymbol if no boundary is given. */ + final def privateWithin(implicit ctx: Context): Symbol = denot.privateWithin + + /** The current annotations of this symbol */ + final def annotations(implicit ctx: Context): List[Annotation] = denot.annotations + + /** Does this symbol have an annotation matching the given class symbol? */ + final def hasAnnotation(cls: Symbol)(implicit ctx: Context): Boolean = denot.hasAnnotation(cls) + + /** The chain of owners of this symbol, starting with the symbol itself */ + final def ownersIterator(implicit ctx: Context): Iterator[Symbol] = denot.ownersIterator + + /** Same as `ownersIterator contains sym` but more efficient. */ + final def hasTransOwner(sym: Symbol)(implicit ctx: Context): Boolean = denot.hasTransOwner(sym) - /** A isAbove B iff A can always be used instead of B + /** The top-level class containing this symbol, except for a toplevel module + * its module class */ - def isAbove(that: Symbol)(implicit ctx: Context): Boolean = - (that.owner isSubClass this.owner) && - (this isAsAccessible that) + def topLevelClass(implicit ctx: Context): Symbol = denot.topLevelClass + + /** The package containing this symbol */ + def enclosingPackage(implicit ctx: Context): Symbol = denot.enclosingPackage + + final def associatedFile(implicit ctx: Context): AbstractFile = denot.associatedFile + final def binaryFile(implicit ctx: Context): AbstractFile = denot.binaryFile + final def sourceFile(implicit ctx: Context): AbstractFile = denot.sourceFile + + final def companionClass(implicit ctx: Context): Symbol = denot.companionClass + + final def companionModule(implicit ctx: Context): Symbol = denot.companionModule + + final def linkedClass(implicit ctx: Context): Symbol = denot.linkedClass + + /** Is this symbol a subclass of the given class? */ + final def isSubClass(cls: Symbol)(implicit ctx: Context): Boolean = denot.isSubClass(cls) - /** A isBelow B iff the reference A & B can always be simplified to A + /** Is this class symbol a subclass of `cls`, + * and is this class symbol also different from Null or Nothing? */ - def isBelow(that: Symbol)(implicit ctx: Context): Boolean = - (this.owner isSubClass that.owner) || - (this isAsAccessible that) + final def isNonBottomSubClass(cls: Symbol)(implicit ctx: Context): Boolean = denot.isNonBottomSubClass(cls) - def isAsAccessible(that: Symbol)(implicit ctx: Context): Boolean = - !this.isProtected && !that.isProtected && // protected members are incomparable - (that.accessBoundary isContainedIn this.accessBoundary) && - this.isStable || !that.isStable + /** Is this symbol a subclass of `base` or a companion object of such a subclass? */ + final def isSubClassOrCompanion(base: Symbol)(implicit ctx: Context): Boolean = denot.isSubClassOrCompanion(base) + /** The class that encloses the owner of the current context + * and that is a subclass of this class. + */ + final def enclosingSubClass(implicit ctx: Context) = denot.enclosingSubClass + + ///** Is this symbol a proper subclass of the given class? */ + //def isProperSubClass(cls: ClassSymbol)(implicit ctx: Context): Boolean = (this ne cls) && this.isSubClass(cls) - /** Set the denotation of this symbol. + /** The non-private symbol whose type matches the type of this symbol + * in in given class. + * + * @param inClass The class containing the symbol's definition + * @param site The base type from which member types are computed */ - def setDenotation(denot: Denotation) = - lastDenot = denot + final def matchingSymbol(inClass: Symbol, site: Type)(implicit ctx: Context): Symbol = denot.matchingSymbol(inClass, site) - /** The last denotation of this symbol */ - protected[this] var lastDenot: Denotation = null + /** The symbol, in class `inClass`, that is overridden by this symbol. */ + final def overriddenSymbol(inClass: ClassSymbol)(implicit ctx: Context): Symbol = denot.overriddenSymbol(inClass) - /** Load denotation of this symbol */ - protected def loadDenot(implicit ctx: Context): Denotation + /** All symbols overriden by this symbol. */ + final def allOverriddenSymbols(implicit ctx: Context): Iterator[Symbol] = denot.allOverriddenSymbols - /** The denotation of this symbol + /** The class or term symbol up to which this symbol is accessible, + * or RootClass if it is public. As java protected statics are + * otherwise completely inaccessible in scala, they are treated + * as public. + * @param base */ - def deref(implicit ctx: Context): Denotation = { - val denot = lastDenot - if (denot != null && containsPeriod(denot.valid, ctx.period)) - denot - else - trackedDenot - } + final def accessBoundary(base: Symbol)(implicit ctx: Context): Symbol = denot.accessBoundary(base) - /** Get referenced denotation if lastDenot points to a different instance */ - private def trackedDenot(implicit ctx: Context): Denotation = { - var denot = lastDenot - if (denot == null) { - denot = loadDenot - } else { - val currentPeriod = ctx.period - val valid = denot.valid - val currentRunId = runIdOf(currentPeriod) - val validRunId = runIdOf(valid) - if (currentRunId != validRunId) { - reloadDenot - } else if (currentPeriod > valid) { - // search for containing interval as long as nextInRun - // increases. - var nextDenot = denot.nextInRun - while (nextDenot.valid > valid && !containsPeriod(nextDenot.valid, currentPeriod)) { - denot = nextDenot - nextDenot = nextDenot.nextInRun - } - if (nextDenot.valid > valid) { - // in this case, containsPeriod(nextDenot.valid, currentPeriod) - denot = nextDenot - } else { - // not found, denot points to highest existing variant - var startPid = lastPhaseIdOf(denot.valid) + 1 - val endPid = ctx.root.nextTransformer(startPid + 1).phaseId - 1 - nextDenot = ctx.root.nextTransformer(startPid) transform denot - if (nextDenot eq denot) - startPid = firstPhaseIdOf(denot.valid) - else { - denot.nextInRun = nextDenot - denot = nextDenot - } - denot.valid = intervalOf(currentRunId, startPid, endPid) - } - } else { - // currentPeriod < valid; in this case a denotation must exist - do { - denot = denot.nextInRun - } while (!containsPeriod(denot.valid, currentPeriod)) - } - } - denot - } + /** Is this symbol contained in `boundary`? */ + final def isContainedIn(boundary: Symbol)(implicit ctx: Context): Boolean = denot.isContainedIn(boundary) - /** - * Get loaded denotation if lastDenot points to a denotation from - * a different run. + /** Is this symbol accessible whenever `that` symbol is accessible? + * Does not take into account status of protected members. */ - private def reloadDenot(implicit ctx: Context): Denotation = { - val initDenot = lastDenot.initial - val newSym: Symbol = - ctx.atPhase(FirstPhaseId) { implicit ctx => - initDenot.owner.info.decl(initDenot.name) - .atSignature(thisRef.signature).symbol - } - if (newSym eq this) { // no change, change validity - var d = initDenot - do { - d.valid = intervalOf(ctx.runId, firstPhaseIdOf(d.valid), lastPhaseIdOf(d.valid)) - d = d.nextInRun - } while (d ne initDenot) - } - newSym.deref - } + final def isAsAccessibleAs(that: Symbol)(implicit ctx: Context): Boolean = denot.isAsAccessibleAs(that) - def isType: Boolean - def isTerm = !isType + /** Is this symbol a non-value class? */ + final def isNonValueClass(implicit ctx: Context): Boolean = denot.isNonValueClass - def thisRef(implicit ctx: Context): SymRef = new UniqueSymRef(this, info) + /** Is this symbol accessible as a member of tree with type `pre`? + * @param pre The type of the tree from which the selection is made + * @param superAccess Access is via super + */ + final def isAccessibleFrom(pre: Type, superAccess: Boolean = false)(implicit ctx: Context): Boolean = denot.isAccessibleFrom(pre, superAccess) - // forwarders for sym methods - def owner(implicit ctx: Context): Symbol = deref.owner - def name(implicit ctx: Context): Name = deref.name - def flags(implicit ctx: Context): FlagSet = deref.flags - def info(implicit ctx: Context): Type = deref.info + def show(implicit ctx: Context): String = ctx.printer.show(this) + def showLocated(implicit ctx: Context): String = ctx.printer.showLocated(this) + def showDef(implicit ctx: Context): String = ctx.printer.showDef(this) - def prefix(implicit ctx: Context) = owner.thisType - def allOverriddenSymbols: Iterator[Symbol] = ??? - def isAsAccessibleAs(other: Symbol): Boolean = ??? - def isAccessibleFrom(pre: Type)(implicit ctx: Context): Boolean = ??? - def locationString: String = ??? - def locatedFullString: String = ??? - def defString: String = ??? def typeParams: List[TypeSymbol] = ??? def unsafeTypeParams: List[TypeSymbol] = ??? def thisType: Type = ??? def isStaticMono = isStatic && typeParams.isEmpty - def isPackageClass: Boolean = ??? def isRoot: Boolean = ??? def moduleClass: Symbol = ??? def cloneSymbol: Symbol = ??? + def hasAnnotation(ann: Annotation): Boolean = ??? + def hasAnnotation(ann: ClassSymbol): Boolean = ??? def asTerm: TermSymbol = ??? def asType: TypeSymbol = ??? @@ -205,41 +191,24 @@ object Symbols { def isConcrete = !isDeferred def isJava: Boolean = ??? - def isSubClass(that: Symbol): Boolean = ??? - def isNonBottomSubClass(that: Symbol): Boolean = ??? - def isProperSubClass(that: Symbol): Boolean = - (this ne that) && (this isSubClass that) - def isAbstractType: Boolean = ??? def newAbstractType(name: TypeName, info: TypeBounds): TypeSymbol = ??? def newAbstractTerm(name: TermName, tpe: Type): TypeSymbol = ??? - def isClass: Boolean = false - def isMethod(implicit ctx: Context): Boolean = deref.isMethod - def hasFlag(required: FlagSet)(implicit ctx: Context): Boolean = (flags & required) != Flags.Empty - def hasAllFlags(required: FlagSet)(implicit ctx: Context): Boolean = (flags & required) == flags + //def isMethod(implicit ctx: Context): Boolean = denot.isMethod - def containsNull(implicit ctx: Context): Boolean = - isClass && !(isSubClass(defn.AnyValClass)) + def isStable(implicit ctx: Context): Boolean = denot.isStable } - abstract class TermSymbol extends Symbol { + abstract class TermSymbol(denotf: Symbol => SymDenotation) extends Symbol(denotf) { def name: TermName - def isType = true - } - - trait RefinementSymbol extends Symbol { - override def deref(implicit ctx: Context) = lastDenot + override def isTerm = true } - abstract class RefinementTermSymbol extends TermSymbol with RefinementSymbol - - abstract class RefinementTypeSymbol extends TypeSymbol with RefinementSymbol - - abstract class TypeSymbol extends Symbol { + abstract class TypeSymbol(denotf: Symbol => SymDenotation) extends Symbol(denotf) { def name: TypeName - def isType = false + override def isType = true def variance: Int = ??? @@ -247,21 +216,20 @@ object Symbols { def typeTemplate(implicit ctx: Context): Type = ??? } - abstract class ClassSymbol extends TypeSymbol { + abstract class ClassSymbol(denotf: Symbol => ClassDenotation) extends TypeSymbol(denotf) { override def isClass = true private var superIdHint: Int = -1 - override def deref(implicit ctx: Context): ClassDenotation = - super.deref.asInstanceOf[ClassDenotation] + final def classDenot(implicit ctx: Context): ClassDenotation = + denot.asInstanceOf[ClassDenotation] def typeOfThis(implicit ctx: Context): Type = ??? - override def typeConstructor(implicit ctx: Context): Type = deref.typeConstructor - override def typeTemplate(implicit ctx: Context): Type = deref.typeTemplate + def baseClasses(implicit ctx: Context): List[ClassSymbol] = classDenot.baseClasses + + override def typeConstructor(implicit ctx: Context): Type = classDenot.typeConstructor +// override def typeTemplate(implicit ctx: Context): Type = classDenot.typeTemplate - /** The unique, densely packed identifier of this class symbol. Should be called - * only if class is a super class of some other class. - */ def superId(implicit ctx: Context): Int = { val hint = superIdHint val rctx = ctx.root @@ -282,11 +250,17 @@ object Symbols { } } - object NoSymbol extends Symbol { - def loadDenot(implicit ctx: Context): Denotation = NoDenotation + class ErrorSymbol(underlying: Symbol, msg: => String)(implicit ctx: Context) extends Symbol(sym => underlying.denot) { + override def isType = underlying.isType + override def isTerm = underlying.isTerm + } + + object NoSymbol extends Symbol(sym => NoDenotation) { override def exists = false - def isType = false } implicit def defn(implicit ctx: Context): Definitions = ctx.root.definitions -}
\ No newline at end of file + + implicit def toFlagSet(sym: Symbol)(implicit ctx: Context): FlagSet = sym.flags + +} diff --git a/src/dotty/tools/dotc/core/Transformers.scala b/src/dotty/tools/dotc/core/Transformers.scala new file mode 100644 index 000000000..ee943e13e --- /dev/null +++ b/src/dotty/tools/dotc/core/Transformers.scala @@ -0,0 +1,51 @@ +package dotty.tools.dotc +package core + +import Periods._, SymDenotations._, Contexts._, Types._, Denotations._ +import java.lang.AssertionError + +trait Transformers { self: RootContext => + + import Transformers._ + + def transformersFor(ref: SingleDenotation): TransformerGroup = ref match { + case _: SymDenotation => denotTransformers + case _ => refTransformers + } + + val denotTransformers = new TransformerGroup + val refTransformers = new TransformerGroup +} + +object Transformers { + + val lastPhaseId = 31 + + class TransformerGroup { + + abstract class Transformer extends DotClass { + val phaseId: Int + def lastPhaseId = nextTransformer(phaseId).phaseId - 1 + def validFor(implicit ctx: Context): Period = + Period(ctx.runId, phaseId, lastPhaseId) + def transform(ref: SingleDenotation)(implicit ctx: Context): SingleDenotation + } + + object NoTransformer extends Transformer { + val phaseId = lastPhaseId + 1 + def transform(ref: SingleDenotation)(implicit ctx: Context): SingleDenotation = + unsupported("transform") + } + + private val nxTransformer = + Array.fill[Transformer](lastPhaseId + 1)(NoTransformer) + + def nextTransformer(i: Int) = nxTransformer(i) + + def install(pid: PhaseId, trans: Transformer): Unit = + if ((pid > NoPhaseId) && (nxTransformer(pid).phaseId > pid)) { + nxTransformer(pid) = trans + install(pid - 1, trans) + } + } +} diff --git a/src/dotty/tools/dotc/core/SubTypers.scala b/src/dotty/tools/dotc/core/TypeComparers.scala index 602b380f4..22ba680ca 100644 --- a/src/dotty/tools/dotc/core/SubTypers.scala +++ b/src/dotty/tools/dotc/core/TypeComparers.scala @@ -1,18 +1,18 @@ package dotty.tools.dotc.core -import Types._, Contexts._, Symbols._ +import Types._, Contexts._, Symbols._, Flags._ import collection.mutable -object SubTypers { +object TypeComparers { type Constraints = Map[PolyParam, TypeBounds] - object SubTyper { + object TypeComparer { private final val LogPendingSubTypesThreshold = 50 } - class SubTyper(_ctx: Context) extends DotClass { - import SubTyper._ + class TypeComparer(_ctx: Context) extends DotClass { + import TypeComparer._ implicit val ctx = _ctx @@ -72,7 +72,7 @@ object SubTypers { val pre2 = tp2.prefix (sym1 == sym2 && ( ctx.erasedTypes || - sym1.owner.hasFlag(Flags.Package) || + (sym1.owner.isPackage) || isSubType(pre1, pre2)) || tp1.name == tp2.name && @@ -117,11 +117,13 @@ object SubTypers { def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match { case tp2: TypeRef => thirdTryRef(tp1, tp2) - case AppliedType(tycon, targs) => - val clazz2 = tycon.typeSymbol - val base = tp1.baseType(clazz2) - base.exists && isSubArgs(base.typeArgs, tp2.typeArgs, clazz2.typeParams) || - fourthTry(tp1, tp2) + case tp2: RefinedType1 => + isSubType(tp1, tp2.parent) && + isSubType(tp1.member(tp2.name1).info, tp2.info1) + case tp2: RefinedType2 => + isSubType(tp1, tp2.parent) && + isSubType(tp1.member(tp2.name1).info, tp2.info1) && + isSubType(tp1.member(tp2.name2).info, tp2.info2) case tp2: RefinedType => isSubType(tp1, tp2.parent) && ((tp2.names, tp2.infos).zipped forall ((name, info) => @@ -162,7 +164,7 @@ object SubTypers { case TypeBounds(lo1, hi1) => isSubType(lo2, lo1) && isSubType(hi1, hi2) case tp1: ClassInfo => - val tt = tp1.typeTemplate + val tt = tp1.typeConstructor // was typeTemplate lo2 <:< tt && tt <:< hi2 case _ => false @@ -175,11 +177,11 @@ object SubTypers { case tp1: TypeRef => ((tp1 eq defn.NothingType) || - (tp1 eq defn.NullType) && tp2.typeSymbol.containsNull + (tp1 eq defn.NullType) && tp2.typeSymbol.isNonValueClass || (!tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2))) - case RefinedType(parent, _) => - isSubType(parent, tp2) + case tp1: RefinedType => + isSubType(tp1.parent, tp2) case AndType(tp11, tp12) => isSubType(tp11, tp2) || isSubType(tp12, tp2) case OrType(tp11, tp12) => @@ -203,6 +205,47 @@ object SubTypers { true } + /** A function implementing `tp1` matches `tp2`. */ + final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = tp1 match { + case tp1: MethodType => + tp2 match { + case tp2: MethodType => + tp1.isImplicit == tp2.isImplicit && + matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) && + matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple) + case tp2: ExprType => + tp1.paramNames.isEmpty && + matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple) + case _ => + false + } + case tp1: ExprType => + tp2 match { + case tp2: MethodType => + tp2.paramNames.isEmpty && + matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple) + case tp2: ExprType => + matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple) + case _ => + matchesType(tp1.resultType, tp2, alwaysMatchSimple) + } + case tp1: PolyType => + tp2 match { + case tp2: PolyType => + sameLength(tp1.paramNames, tp2.paramNames) && + matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple) + case _ => + false + } + case _ => + tp2 match { + case _: MethodType | _: PolyType => + false + case _ => + alwaysMatchSimple || isSameType(tp1, tp2) + } + } + /** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */ private def matchingParams(formals1: List[Type], formals2: List[Type], isJava1: Boolean, isJava2: Boolean): Boolean = formals1 match { case Nil => diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala new file mode 100644 index 000000000..08d7c0cd6 --- /dev/null +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -0,0 +1,200 @@ +package dotty.tools.dotc.core + +import Contexts._, Types._, Symbols._, Names._ + +trait TypeOps { this: Context => + + final def asSeenFrom(tp: Type, pre: Type, clazz: Symbol, theMap: AsSeenFromMap): Type = { + + def skipPrefixOf(pre: Type, clazz: Symbol) = + (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass + + def toPrefix(pre: Type, clazz: Symbol, thisclazz: ClassSymbol): Type = + if (skipPrefixOf(pre, clazz)) + tp + else if ((thisclazz isNonBottomSubClass clazz) && + (pre.widen.typeSymbol isNonBottomSubClass thisclazz)) + pre match { + case SuperType(thispre, _) => thispre + case _ => pre + } + else + toPrefix(pre.baseType(clazz).normalizedPrefix, clazz.owner, thisclazz) + + tp match { + case tp: NamedType => + val sym = tp.symbol + if (sym.isStatic) tp + else { + val pre0 = tp.prefix + val pre1 = asSeenFrom(pre0, pre, clazz, theMap) + if (pre1 eq pre0) tp + else { + val tp1 = NamedType(pre1, tp.name) + if (sym.isTypeParameter) { + // short-circuit instantiated type parameters + // by replacing pre.tp with its alias, if it has one. + val tp2 = tp1.info + if (tp2.isAliasTypeBounds) return tp2.bounds.hi + } + tp1 + } + } + case ThisType(thisclazz) => + toPrefix(pre, clazz, thisclazz) + case _: BoundType | NoPrefix => + tp + case tp: RefinedType1 => + tp.derivedRefinedType1( + asSeenFrom(tp.parent, pre, clazz, theMap), + tp.name1, + asSeenFrom(tp.info1, pre, clazz, theMap)) + case tp: RefinedType2 => + tp.derivedRefinedType2( + asSeenFrom(tp.parent, pre, clazz, theMap), + tp.name1, + asSeenFrom(tp.info1, pre, clazz, theMap), + tp.name2, + asSeenFrom(tp.info2, pre, clazz, theMap)) + case _ => + (if (theMap != null) theMap else new AsSeenFromMap(pre, clazz)) + .mapOver(tp) + } + } + + class AsSeenFromMap(pre: Type, clazz: Symbol) extends TypeMap { + def apply(tp: Type) = asSeenFrom(tp, pre, clazz, this) + } + + final def isVolatile(tp: Type): Boolean = { + def isAbstractIntersection(tp: Type): Boolean = tp match { + case tp: TypeRef => tp.isAbstractType + case AndType(l, r) => isAbstractIntersection(l) | isAbstractIntersection(l) + case OrType(l, r) => isAbstractIntersection(l) & isAbstractIntersection(r) + case _ => false + } + def containsName(names: Set[Name], tp: RefinedType): Boolean = tp match { + case tp: RefinedType1 => names contains tp.name1 + case tp: RefinedType2 => (names contains tp.name1) || (names contains tp.name2) + case _ => tp.names exists (names contains) + } + def test = { + tp match { + case ThisType(_) => + false + case tp: RefinedType => + tp.parent.isVolatile || + isAbstractIntersection(tp.parent) && + containsName(tp.abstractMemberNames(tp), tp) + case tp: TypeProxy => + tp.underlying.isVolatile + case AndType(l, r) => + l.isVolatile || r.isVolatile || + isAbstractIntersection(l) && r.abstractMemberNames(tp).nonEmpty + case OrType(l, r) => + l.isVolatile && r.isVolatile + case _ => + false + } + } + // need to be careful not to fall into an infinite recursion here + // because volatile checking is done before all cycles are detected. + // the case to avoid is an abstract type directly or + // indirectly upper-bounded by itself. See #2918 + import ctx.root.{ volatileRecursions, pendingVolatiles } + try { + volatileRecursions += 1 + if (volatileRecursions < LogVolatileThreshold) + test + else if (pendingVolatiles(tp)) + false // we can return false here, because a cycle will be detected + // here afterwards and an error will result anyway. + else + try { + pendingVolatiles += tp + test + } finally { + pendingVolatiles -= tp + } + } finally { + volatileRecursions -= 1 + } + } + + final def glb(tp1: Type, tp2: Type): Type = + if (tp1 eq tp2) tp1 + else if (tp1.isWrong) tp2 + else if (tp2.isWrong) tp1 + else tp2 match { + case OrType(tp21, tp22) => + tp1 & tp21 | tp1 & tp22 + case _ => + tp1 match { + case OrType(tp11, tp12) => + tp11 & tp2 | tp12 & tp2 + case _ => + val t1 = mergeIfSub(tp1, tp2) + if (t1.exists) t1 + else { + val t2 = mergeIfSub(tp2, tp1) + if (t2.exists) t2 + else AndType(tp1, tp2) + } + } + } + + def lub(tp1: Type, tp2: Type): Type = + if (tp1 eq tp2) tp1 + else if (tp1.isWrong) tp1 + else if (tp2.isWrong) tp2 + else { + val t1 = mergeIfSuper(tp1, tp2) + if (t1.exists) t1 + else { + val t2 = mergeIfSuper(tp2, tp1) + if (t2.exists) t2 + else OrType(tp1, tp2) + } + } + + /** Merge `t1` into `tp2` if t1 is a subtype of some part of tp2. + */ + private def mergeIfSub(tp1: Type, tp2: Type)(implicit ctx: Context): Type = + if (tp1 <:< tp2) + if (tp2 <:< tp1) tp2 else tp1 + else tp2 match { + case tp2 @ AndType(tp21, tp22) => + val lower1 = mergeIfSub(tp1, tp21) + if (lower1 eq tp21) tp2 + else if (lower1.exists) lower1 & tp22 + else { + val lower2 = mergeIfSub(tp1, tp22) + if (lower2 eq tp22) tp2 + else if (lower2.exists) tp21 & lower2 + else NoType + } + case _ => + NoType + } + + /** Merge `tp1` into `tp2` if tp1 is a supertype of some part of tp2. + */ + private def mergeIfSuper(tp1: Type, tp2: Type)(implicit ctx: Context): Type = + if (tp2 <:< tp1) + if (tp1 <:< tp2) tp2 else tp1 + else tp2 match { + case tp2 @ OrType(tp21, tp22) => + val higher1 = mergeIfSuper(tp1, tp21) + if (higher1 eq tp21) tp2 + else if (higher1.exists) higher1 | tp22 + else { + val higher2 = mergeIfSuper(tp1, tp22) + if (higher2 eq tp22) tp2 + else if (higher2.exists) tp21 | higher2 + else NoType + } + case _ => + NoType + } +} + diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 9dc87711c..d55afcca6 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -3,35 +3,19 @@ package core import util.HashSet import Symbols._ -import SubTypers._ +import TypeComparers._ import Flags._ import Names._ import Scopes._ -import Substituters._ import Constants._ import Contexts._ import Annotations._ +import SymDenotations._ import Denotations._ -import References._ import Periods._ -import References.{Reference, RefSet, RefUnion, ErrorRef} -import scala.util.hashing.{MurmurHash3 => hashing} +import scala.util.hashing.{ MurmurHash3 => hashing } import collection.mutable -trait Types { self: Context => - - import Types._ - - private val initialUniquesCapacity = 50000 - - private val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) { - override def hash(x: Type): Int = x.hash - } - - private var volatileRecursions: Int = 0 - private val pendingVolatiles = new mutable.HashSet[Type] -} - object Types { /** A hash value indicating that the underlying type is not @@ -44,88 +28,129 @@ object Types { */ private final val NotCachedAlt = Int.MinValue - /** How many recursive calls to isVolatile are performed before - * logging starts. - */ - private final val LogVolatileThreshold = 50 - /** The class of types. * The principal subclasses and sub-objects are as follows: * - * Type -+- TypeProxy -+- NamedType ----+--- TypeRef - * | | \ - * | +- SingletonType---+- TermRef - * | | - * | +- SingletonType --+- ThisType - * | | +- SuperType - * | | +- ConstantType - * | | +- MethodParam - * | | +- RefinedThis - * | | +- TypeBounds - * | | +- ExprType - * | | +- AnnotatedType - * | +- PolyParam - * | +- AppliedType - * | +- RefinedType - * +- AndType - * +- OrType - * +- MethodType -+- ImplicitMethodType - * | +- JavaMethodType - * +- PolyType - * +- ClassInfo - * | - * +- NoType - * +- ErrorType - * +- WildcardType + * Type -+- ProxyType --+- NamedType ----+--- TypeRef + * | | \ + * | +- SingletonType---+- TermRef + * | | + * | +- SingletonType --+- ThisType + * | +- SuperType + * | +- ConstantType + * | +- MethodParam + * | +- RefinedThis + * | +- TypeBounds + * | +- ExprType + * | +- AnnotatedType + * +- GroundType -+- PolyParam + * +- RefinedType + * +- AndType + * +- OrType + * +- MethodType -----+- ImplicitMethodType + * | +- JavaMethodType + * +- PolyType + * +- ClassInfo + * | + * +- NoType + * +- ErrorType + * +- WildcardType */ abstract class Type extends DotClass { - def hash = NotCached - /** The type symbol associated with the type */ - def typeSymbol(implicit ctx: Context): Symbol = NoSymbol + final def typeSymbol(implicit ctx: Context): Symbol = this match { + case tp: TypeRef => tp.symbol + case tp: ClassInfo => tp.classd.symbol + case _ => NoSymbol + } /** The term symbol associated with the type */ - def termSymbol(implicit ctx: Context): Symbol = NoSymbol + final def termSymbol(implicit ctx: Context): Symbol = this match { + case tp: TermRef => tp.symbol + case _ => NoSymbol + } /** Does this type denote a stable reference (i.e. singleton type)? */ - def isStable(implicit ctx: Context): Boolean = false + final def isStable(implicit ctx: Context): Boolean = this match { + case tp: TermRef => tp.prefix.isStable && tp.termSymbol.isStable + case _: SingletonType => true + case _ => false + } /** A type T is a legal prefix in a type selection T#A if * T is stable or T contains no uninstantiated type variables. */ - def isLegalPrefix(implicit ctx: Context): Boolean = + final def isLegalPrefix(implicit ctx: Context): Boolean = isStable || abstractTypeNames(this).isEmpty /** The set of names that denote an abstract type member of this type * which is also an abstract type member of `pre` */ - def abstractTypeNames(pre: Type)(implicit ctx: Context): Set[Name] = + final def abstractTypeNames(pre: Type)(implicit ctx: Context): Set[Name] = memberNames(pre, abstractTypeNameFilter) /** The set of names that denote an abstract term member of this type * which is also an abstract term member of `pre` */ - def abstractTermNames(pre: Type)(implicit ctx: Context): Set[Name] = + final def abstractTermNames(pre: Type)(implicit ctx: Context): Set[Name] = memberNames(pre, abstractTermNameFilter) /** The set of names that denote an abstract member of this type * which is also an abstract member of `pre` */ - def abstractMemberNames(pre: Type)(implicit ctx: Context): Set[Name] = + final def abstractMemberNames(pre: Type)(implicit ctx: Context): Set[Name] = abstractTypeNames(pre) | abstractTermNames(pre) /** The set of names of members of this type that pass the given name filter * when seen as members of `pre`. More precisely, these are all * of members `name` such that `keepOnly(pre, name)` is `true`. */ - def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - Set() + final def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = this match { + case tp: ClassInfo => + tp.classd.memberNames(keepOnly) filter (keepOnly(pre, _)) + case tp: RefinedType1 => + var ns = tp.parent.memberNames(pre, keepOnly) + if (keepOnly(pre, tp.name1)) ns += tp.name1 + ns + case tp: RefinedType2 => + var ns = tp.parent.memberNames(pre, keepOnly) + if (keepOnly(pre, tp.name1)) ns += tp.name1 + if (keepOnly(pre, tp.name2)) ns += tp.name2 + ns + case tp: RefinedTypeN => + tp.parent.memberNames(pre, keepOnly) ++ (tp.names filter (keepOnly(pre, _))).toSet + case tp: AndType => + tp.tp1.memberNames(pre, keepOnly) | tp.tp2.memberNames(pre, keepOnly) + case tp: OrType => + tp.tp1.memberNames(pre, keepOnly) & tp.tp2.memberNames(pre, keepOnly) + case tp: TypeProxy => + tp.underlying.memberNames(pre, keepOnly) + case _ => + Set() + } /** Is this type a TypeBounds instance, with lower and upper bounds * that are not identical? */ - def isRealTypeBounds: Boolean = false + final def isRealTypeBounds: Boolean = this match { + case tp: TypeBounds => tp.lo ne tp.hi + case _ => false + } + + /** Is this type a TypeBounds instance, with lower and upper bounds + * that are identical? + */ + final def isAliasTypeBounds: Boolean = this match { + case tp: TypeBounds => tp.lo eq tp.hi + case _ => false + } + + /** This type seen as a TypeBounds */ + final def bounds(implicit ctx: Context): TypeBounds = this match { + case tp: TypeBounds => tp + case _ => TypeBounds(this, this) + } /** A type is volatile if it has an underlying type of the * form P1 with ... with Pn { decls } (where n may be 1 or decls may @@ -141,112 +166,79 @@ object Types { * Lazy values are not allowed to have volatile type, as otherwise * unsoundness can result. */ - def isVolatile(implicit ctx: Context): Boolean = { - def isAbstractIntersection(tp: Type): Boolean = tp match { - case tp: TypeRef => tp.isAbstractType - case AndType(l, r) => isAbstractIntersection(l) | isAbstractIntersection(l) - case OrType(l, r) => isAbstractIntersection(l) & isAbstractIntersection(r) - case _ => false - } - def test = { - this match { - case ThisType(_) => - false - case RefinedType(p, names) => - p.isVolatile || - isAbstractIntersection(p) && - (names exists (abstractMemberNames(this) contains)) - case tp: TypeProxy => - tp.underlying.isVolatile - case AndType(l, r) => - l.isVolatile || r.isVolatile || - isAbstractIntersection(l) && r.abstractMemberNames(this).nonEmpty - case OrType(l, r) => - l.isVolatile && r.isVolatile - case _ => - false - } - } - // need to be careful not to fall into an infinite recursion here - // because volatile checking is done before all cycles are detected. - // the case to avoid is an abstract type directly or - // indirectly upper-bounded by itself. See #2918 - import ctx.root.{volatileRecursions, pendingVolatiles} - try { - volatileRecursions += 1 - if (volatileRecursions < LogVolatileThreshold) - test - else if (pendingVolatiles(this)) - false // we can return false here, because a cycle will be detected - // here afterwards and an error will result anyway. - else - try { - pendingVolatiles += this - test - } finally { - pendingVolatiles -= this - } - } finally { - volatileRecursions -= 1 - } - } + final def isVolatile(implicit ctx: Context): Boolean = + ctx.isVolatile(this) /** Is this type guaranteed not to have `null` as a value? */ - def isNotNull: Boolean = false + final def isNotNull: Boolean = false /** Is this type produced as a repair for an error? */ - def isError(implicit ctx: Context): Boolean = (typeSymbol hasFlag Error) || (termSymbol hasFlag Error) + final def isError(implicit ctx: Context): Boolean = + (typeSymbol is Erroneous) || (termSymbol is Erroneous) /** Is some part of this type produced as a repair for an error? */ - def isErroneous(implicit ctx: Context): Boolean = exists(_.isError) + final def isErroneous(implicit ctx: Context): Boolean = exists(_.isError) /** Returns true if there is a part of this type that satisfies predicate `p`. */ - def exists(p: Type => Boolean): Boolean = + final def exists(p: Type => Boolean): Boolean = new ExistsAccumulator(p)(false, this) /** Substitute all types that refer in their symbol attribute to * one of the symbols in `from` by the corresponding types in `to` */ - def subst(from: List[Symbol], to: List[Type])(implicit ctx: Context): Type = + final def subst(from: List[Symbol], to: List[Type])(implicit ctx: Context): Type = if (from.isEmpty) this else { val from1 = from.tail - if (from1.isEmpty) new SubstOps(this).subst1(from.head, to.head, null) + if (from1.isEmpty) ctx.subst1(this, from.head, to.head, null) else { val from2 = from1.tail - if (from2.isEmpty) new SubstOps(this).subst2(from.head, to.head, from.tail.head, to.tail.head, null) - else new SubstOps(this).subst(from, to, null) + if (from2.isEmpty) ctx.subst2(this, from.head, to.head, from.tail.head, to.tail.head, null) + else ctx.subst(this, from, to, null) } } /** Substitute all types of the form `PolyParam(from, N)` by * `PolyParam(to, N)`. */ - def subst(from: PolyType, to: PolyType)(implicit ctx: Context): Type = - new SubstOps(this).subst(from, to, null) - - /** Substitute all types of the form `MethodParam(from, N)` by - * `MethodParam(to, N)`. - */ - def subst(from: MethodType, to: MethodType)(implicit ctx: Context): Type = - if (from.isDependent) new SubstOps(this).subst(from, to, null) - else this + final def subst(from: BindingType, to: BindingType)(implicit ctx: Context): Type = + ctx.subst(this, from, to, null) - /** Substitute all references of the form `This(clazz)` by `tp` */ - def substThis(clazz: ClassSymbol, tp: Type)(implicit ctx: Context): Type = - new SubstOps(this).substThis(clazz, tp, null) + /** Substitute all occurrences of `This(clazz)` by `tp` */ + final def substThis(clazz: ClassSymbol, tp: Type)(implicit ctx: Context): Type = + ctx.substThis(this, clazz, tp, null) - /** Substitute all references of the form `RefinedThis(from)` by `tp` */ - def substThis(from: RefinedType, tp: Type)(implicit ctx: Context): Type = - new SubstOps(this).substThis(from, tp, null) + /** Substitute all occurrences of `RefinedThis(rt)` by `tp` */ + final def substThis(rt: RefinedType, tp: Type)(implicit ctx: Context): Type = + ctx.substThis(this, rt, tp, null) /** For a ClassInfo type, its parents, - * For an AndType, its operands, - * For an applied type, the instantiated parents of its base type. * Inherited by all type proxies. Empty for all other types. + * Overwritten in ClassInfo, where parents is cached. */ - def parents(implicit ctx: Context): List[Type] = List() + def parents(implicit ctx: Context): List[TypeRef] = this match { + case tp: TypeProxy => + tp.underlying.parents + case _ => List() + } + + /** The elements of an AndType or OrType */ + def factors(implicit ctx: Context): List[Type] = this match { + case tp: AndType => + def components(tp: Type): List[Type] = tp match { + case AndType(tp1, tp2) => components(tp1) ++ components(tp2) + case _ => List(tp) + } + components(tp) + case tp: OrType => + def components(tp: Type): List[Type] = tp match { + case OrType(tp1, tp2) => components(tp1) ++ components(tp2) + case _ => List(tp) + } + components(tp) + case _ => List() + } /** The normalized prefix of this type is: * For an alias type, the normalized prefix of its alias @@ -254,46 +246,123 @@ object Types { * Inherited by all other type proxies. * `NoType` for all other types. */ - def normalizedPrefix(implicit ctx: Context): Type = NoType - - /** This type seen as a TypeBounds */ - def bounds(implicit ctx: Context): TypeBounds = TypeBounds(this, this) + final def normalizedPrefix(implicit ctx: Context): Type = this match { + case tp: NamedType => + if (tp.isAbstractType) tp.info.normalizedPrefix else tp.prefix + case tp: ClassInfo => + tp.prefix + case tp: TypeProxy => + tp.underlying.normalizedPrefix + case _ => + NoType + } /** The scope of all declarations of this type. * Defined by ClassInfo, inherited by type proxies. * Empty scope for all other types. */ - def decls(implicit ctx: Context): Scope = EmptyScope + final def decls(implicit ctx: Context): Scope = this match { + case tp: ClassInfo => + tp.classd.decls + case tp: TypeProxy => + tp.underlying.decls + case _ => + EmptyScope + } /** The declaration of this type with given name */ - def decl(name: Name)(implicit ctx: Context): Reference = - decls.refsNamed(name).toRef + final def decl(name: Name)(implicit ctx: Context): Denotation = + findDecl(name, this, Flags.Empty) + + /** The non-private declaration of this type with given name */ + final def nonPrivateDecl(name: Name)(implicit ctx: Context): Denotation = + findDecl(name, this, Flags.Private) + + /** The non-private declaration of this type with given name */ + final def findDecl(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = this match { + case tp: RefinedType => + tp.findDecl(name, pre) + case tp: ClassInfo => + tp.classd.decls + .denotsNamed(name) + .filterAccessibleFrom(pre) + .filterExcluded(excluded) + .asSeenFrom(pre, tp.classd.symbol) + .toDenot + case tp: TypeProxy => + tp.underlying.findDecl(name, pre, excluded) + } /** The member of this type with given name */ - def member(name: Name)(implicit ctx: Context): Reference = + final def member(name: Name)(implicit ctx: Context): Denotation = findMember(name, this, Flags.Empty) /** The non-private member of this type with given name */ - def nonPrivateMember(name: Name)(implicit ctx: Context): Reference = + final def nonPrivateMember(name: Name)(implicit ctx: Context): Denotation = findMember(name, this, Flags.Private) /** Find member of this type with given name and - * produce a reference that contains the type of the member + * produce a denotation that contains the type of the member * as seen from given prefix `pre`. Exclude all members with one * of the flags in `excluded` from consideration. */ - def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = - unsupported("findMember") + final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = this match { + case tp: RefinedType => + val denot = tp.findDecl(name, pre) + if ((denot.symbol is TypeParam) && denot.info.isAliasTypeBounds) + denot + else + tp.parent.findMember(name, pre, excluded | Flags.Private) & denot + case tp: TypeProxy => + tp.underlying.findMember(name, pre, excluded) + case tp: ClassInfo => + val classd = tp.classd + val candidates = classd.membersNamed(name) + val results = candidates + .filterAccessibleFrom(pre) + .filterExcluded(excluded) + .asSeenFrom(pre, classd.symbol) + if (results.exists) results.toDenot + else new ErrorDenotation // todo: refine + case tp: AndType => + tp.tp1.findMember(name, pre, excluded) & tp.tp2.findMember(name, pre, excluded) + case tp: OrType => + (tp.tp1.findMember(name, pre, excluded) | tp.tp2.findMember(name, pre, excluded))(pre) + } /** Is this type a subtype of that type? */ - def <:< (that: Type)(implicit ctx: Context): Boolean = - ctx.subTyper.isSubType(this, that) + final def <:<(that: Type)(implicit ctx: Context): Boolean = + ctx.typeComparer.isSubType(this, that) /** Is this type the same as that type? * This is the case iff `this <:< that` and `that <:< this`. */ - def =:= (that: Type)(implicit ctx: Context): Boolean = - ctx.subTyper.isSameType(this, that) + final def =:=(that: Type)(implicit ctx: Context): Boolean = + ctx.typeComparer.isSameType(this, that) + + /** Is this type close enough to that type so that members + * with the two type would override each other? + * This means: + * - Either both types are polytypes with the same number of + * type parameters and their result types match after renaming + * corresponding type parameters + * - Or both types are (possibly nullary) method types with equivalent type parameter types + * and matching result types + * - Or both types are equivalent + * - Or phase.erasedTypes is false and both types are neither method nor + * poly types. + */ + def matches(that: Type)(implicit ctx: Context): Boolean = + ctx.typeComparer.matchesType(this, that, !ctx.phase.erasedTypes) + + /** Does this type match that type + * + */ + + /** The info of `sym`, seen as a member of this type. */ + final def memberInfo(denot: SymDenotation)(implicit ctx: Context): Type = { + denot.info.asSeenFrom(this, denot.owner) + } /** Widen from singleton type to its underlying non-singleton * base type by applying one or more `underlying` dereferences, @@ -303,12 +372,18 @@ object Types { * val o: Outer * <o.x.type>.widen = o.C */ - def widen(implicit ctx: Context): Type = this + final def widen(implicit ctx: Context): Type = this match { + case tp: SingletonType => tp.underlying.widen + case _ => this + } /** Widen from constant type to its underlying non-constant * base type. */ - def deconst: Type = this + final def deconst: Type = this match { + case tp: ConstantType => tp.value.tpe + case _ => this + } //def resultType: Type = ??? @@ -316,190 +391,64 @@ object Types { * Inherited by all type proxies. * `Nil` for all other types. */ - def baseClasses(implicit ctx: Context): List[ClassSymbol] = Nil - - - def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type = - if (clazz.isStaticMono || ctx.erasedTypes && clazz != defn.ArrayClass ) this - else asSeenFrom(pre, clazz, null) - - def asSeenFrom(pre: Type, clazz: Symbol, theMap: AsSeenFromMap)(implicit ctx: Context): Type = { - - def skipPrefixOf(pre: Type, clazz: Symbol) = - (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass - - def toPrefix(pre: Type, clazz: Symbol, thisclazz: ClassSymbol): Type = - if (skipPrefixOf(pre, clazz)) - this - else if ((thisclazz isNonBottomSubClass clazz) && - (pre.widen.typeSymbol isNonBottomSubClass thisclazz)) - pre match { - case SuperType(thistp, _) => thistp - case _ => pre - } - else - toPrefix(pre.baseType(clazz).normalizedPrefix, clazz.owner, thisclazz) - - def toInstance(pre: Type, clazz: Symbol, tparam: Symbol): Type = { - if (skipPrefixOf(pre, clazz)) this - else { - val tparamOwner = tparam.owner - - def throwError = - if (tparamOwner.info.parents exists (_.isErroneous)) - ErrorType // don't be overzealous with throwing exceptions, see #2641 - else - throw new Error( - s"something is wrong (wrong class file?): tp ${tparam.locationString} cannot be instantiated from ${pre.widen}") - - def prefixMatches = pre.typeSymbol isNonBottomSubClass tparamOwner - - val basePre = pre.baseType(clazz) - - def instParamFrom(typeInst: Type): Type = typeInst match { - case ConstantType(_) => - // have to deconst because it may be a Class[T]. - instParamFrom(typeInst.deconst) - case AppliedType(tycon, baseArgs) => - instParam(tycon.typeParams, baseArgs) - case _ => - throwError - } - - def instParam(ps: List[Symbol], as: List[Type]): Type = - if (ps.isEmpty || as.isEmpty) throwError - else if (tparam eq ps.head) as.head - else throwError - - if (tparamOwner == clazz && prefixMatches) instParamFrom(basePre) - else toInstance(basePre.normalizedPrefix, clazz.owner, tparam) - } - } - - this match { - case tp: NamedType => - val sym = tp.symbol - if (tp.symbol.isTypeParameter) toInstance(pre, clazz, sym) - else if (sym.isStatic) this - else tp.derivedNamedType(tp.prefix.asSeenFrom(pre, clazz, theMap), tp.name) - case ThisType(thisclazz) => - toPrefix(pre, clazz, thisclazz) - case _ => - val asSeenFromMap = if (theMap != null) theMap else new AsSeenFromMap(pre, clazz) - this match { - case tp: AppliedType => - tp.derivedAppliedType( - asSeenFromMap(tp.tycon), tp.targs mapConserve asSeenFromMap) - case _ => - asSeenFromMap mapOver this - } - } + final def baseClasses(implicit ctx: Context): List[ClassSymbol] = this match { + case tp: TypeProxy => + tp.underlying.baseClasses + case tp: ClassInfo => + tp.classd.baseClasses + case _ => Nil } + final def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type = + if (clazz.isStaticMono || + ctx.erasedTypes && clazz != defn.ArrayClass || + (pre eq clazz.thisType)) this + else ctx.asSeenFrom(this, pre, clazz, null) + + /** The signature of this type. This is by default NullSignature, + * but is overridden for PolyTypes, MethodTypes, and TermRefWithSignature types. + * (the reason why we deviate from the "final-method-with-pattern-match-in-base-class" + * pattern is that method signatures use caching, so encapsulation + * is improved using an OO scheme). + */ def signature: Signature = NullSignature - def subSignature: Signature = List() - def baseType(base: Symbol)(implicit ctx: Context): Type = base.deref match { + final def baseType(base: Symbol)(implicit ctx: Context): Type = base.denot match { case classd: ClassDenotation => classd.baseTypeOf(this) case _ => NoType } /** The type parameters of this type are: * For a ClassInfo type, the type parameters of its denotation. - * For an applied type, the type parameters of its constructor - * that have not been instantiated yet. * Inherited by type proxies. * Empty list for all other types. */ - def typeParams(implicit ctx: Context): List[TypeSymbol] = Nil + final def typeParams(implicit ctx: Context): List[TypeSymbol] = this match { + case tp: ClassInfo => + tp.classd.typeParams + case tp: TypeProxy => + tp.underlying.typeParams + case _ => Nil + } - /** The type arguments of this type are: - * For an Applied type, its type arguments. - * Inherited by type proxies. - * Empty list for all other types. - */ - def typeArgs(implicit ctx: Context): List[Type] = Nil - - def isWrong: Boolean = !exists // !!! needed? - def exists: Boolean = true - - def & (that: Type)(implicit ctx: Context): Type = - if (this eq that) this - else if (this.isWrong) that - else if (that.isWrong) this - else that match { - case OrType(that1, that2) => - this & that1 | this & that2 - case _ => - this match { - case OrType(this1, this2) => - this1 & that | this2 & that - case _ => - val t1 = mergeIfSub(this, that) - if (t1.exists) t1 - else { - val t2 = mergeIfSub(that, this) - if (t2.exists) t2 - else AndType(this, that) - } - } - } + final def isWrong: Boolean = !exists // !!! needed? + final def exists: Boolean = true - def | (that: Type)(implicit ctx: Context): Type = - if (this eq that) this - else if (this.isWrong) this - else if (that.isWrong) that - else { - val t1 = mergeIfSuper(this, that) - if (t1.exists) t1 - else { - val t2 = mergeIfSuper(that, this) - if (t2.exists) t2 - else OrType(this, that) - } - } + final def &(that: Type)(implicit ctx: Context): Type = + ctx.glb(this, that) - /** Merge `t1` into `t2` if t1 is a subtype of some part of t2. - */ - private def mergeIfSub(t1: Type, t2: Type)(implicit ctx: Context): Type = - if (t1 <:< t2) - if (t2 <:< t1) t2 else t1 - else t2 match { - case t2 @ AndType(t21, t22) => - val lower1 = mergeIfSub(t1, t21) - if (lower1 eq t21) t2 - else if (lower1.exists) lower1 & t22 - else { - val lower2 = mergeIfSub(t1, t22) - if (lower2 eq t22) t2 - else if (lower2.exists) t21 & lower2 - else NoType - } - case _ => - NoType - } + def |(that: Type)(implicit ctx: Context): Type = + ctx.lub(this, that) - /** Merge `t1` into `t2` if t1 is a supertype of some part of t2. - */ - private def mergeIfSuper(t1: Type, t2: Type)(implicit ctx: Context): Type = - if (t2 <:< t1) - if (t1 <:< t2) t2 else t1 - else t2 match { - case t2 @ OrType(t21, t22) => - val higher1 = mergeIfSuper(t1, t21) - if (higher1 eq t21) t2 - else if (higher1.exists) higher1 | t22 - else { - val higher2 = mergeIfSuper(t1, t22) - if (higher2 eq t22) t2 - else if (higher2.exists) t21 | higher2 - else NoType - } - case _ => - NoType - } + def show(implicit ctx: Context): String = ctx.printer.show(this) + +// ----- hashing ------------------------------------------------------ - // 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 @@ -514,6 +463,18 @@ object Types { 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, tp1: Type, tp2: Type, tp3: Type): Int = { + val elemHash = tp1.hash + if (elemHash == NotCached) return NotCached + finishHash(hashing.mix(seed, elemHash), arity + 1, tp2, tp3) + } + private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = { var h = seed var xs = tps @@ -540,99 +501,125 @@ object Types { protected def doHash(tp: Type): Int = finishHash(hashSeed, 0, tp) - protected def doHash(tp1: Type, tp2: Type): Int = { - val elemHash = tp1.hash - if (elemHash == NotCached) return NotCached - finishHash(hashing.mix(hashSeed, elemHash), 1, tp2) - } - 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) + + protected def doHash(x1: Any, x2: Any, tp3: Type, tp4: Type, tp5: Type) = + finishHash(hashing.mix(hashing.mix(hashSeed, x1.hashCode), x2.hashCode), 2, tp3, tp4, tp5) + } // end Type - abstract class UniqueType extends Type { - final override val hash = computeHash - override def hashCode = hash - def computeHash: Int - } + /** A marker trait for cached types */ + trait CachedType extends Type def unique[T <: Type](tp: T)(implicit ctx: Context): T = { if (tp.hash == NotCached) tp else ctx.root.uniques.findEntryOrUpdate(tp).asInstanceOf[T] } - trait TypeProxy extends Type { + /** A marker trait for type proxies. + * Each implementation is expected to redefine the `underlying` method. + */ + abstract class TypeProxy extends Type { + /** The type to which this proxy forwards operations. */ def underlying(implicit ctx: Context): Type - override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = - underlying.findMember(name, pre, excluded) - override def parents(implicit ctx: Context) = underlying.parents - override def decls(implicit ctx: Context) = underlying.decls - override def baseClasses(implicit ctx: Context) = underlying.baseClasses - override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context) = - underlying.memberNames(pre, keepOnly) - override def isVolatile(implicit ctx: Context): Boolean = underlying.isVolatile - override def normalizedPrefix(implicit ctx: Context) = underlying.normalizedPrefix - override def typeParams(implicit ctx: Context) = underlying.typeParams - override def typeArgs(implicit ctx: Context) = underlying.typeArgs } - trait TransformingProxy extends TypeProxy { - // needed? + // Every type has to inherit one of the following four abstract type classes., + // which determine whether the type is cached, and whether + // it is a proxy of some other type. The duplication in their methods + // is for efficiency. + + /** Instances of this class are cached and are not proxies. */ + abstract class CachedGroundType extends Type with CachedType { + final val hash = computeHash + override final def hashCode = hash + def computeHash: Int } - trait SubType extends UniqueType with TypeProxy { + /** Instances of this class are cached and are proxies. */ + abstract class CachedProxyType extends TypeProxy with CachedType { + final val hash = computeHash + override final def hashCode = hash + def computeHash: Int + } + /** Instances of this class are uncached and are not proxies. */ + abstract class UncachedGroundType extends Type { + final def hash = NotCached } - trait SingletonType extends SubType { - override def isStable(implicit ctx: Context) = true - override def widen(implicit ctx: Context): Type = underlying.widen + /** Instances of this class are uncached and are proxies. */ + abstract class UncachedProxyType extends TypeProxy { + final def hash = NotCached } -// --- NamedTypes ------------------------------------------------------------------ + /** A marker trait for types that are guaranteed to contain only a + * single non-null value (they might contain null in addition). + */ + trait SingletonType extends TypeProxy + + // --- NamedTypes ------------------------------------------------------------------ /** A NamedType of the form Prefix # name */ - abstract class NamedType extends UniqueType with TypeProxy { + abstract class NamedType extends CachedProxyType { val prefix: Type val name: Name - private[this] var referencedVar: Reference = null - protected[this] var validPeriods = Nowhere + private[this] var lastDenotation: Denotation = null private def checkPrefix(sym: Symbol) = sym.isAbstractType || sym.isClass - def referenced(implicit ctx: Context): Reference = { - if (!containsPeriod(validPeriods, ctx.period)) { - referencedVar = prefix.member(name) - validPeriods = ctx.stableInterval - if (checkPrefix(referencedVar.symbol) && !prefix.isLegalPrefix) - throw new MalformedType(prefix, referencedVar.symbol) + /** The denotation currently denoted by this type */ + def denot(implicit ctx: Context): Denotation = { + val validPeriods = + if (lastDenotation != null) lastDenotation.validFor else Nowhere + if (!(validPeriods contains ctx.period)) { + val thisPeriod = ctx.period + lastDenotation = + if (validPeriods.runId == thisPeriod.runId) { + lastDenotation.current + } else { + val d = loadDenot + if (d.exists || ctx.phaseId == FirstPhaseId) { + if (checkPrefix(d.symbol) && !prefix.isLegalPrefix) + throw new MalformedType(prefix, d.symbol) + d + } else {// name has changed; try load in earlier phase and make current + denot(ctx.withPhase(ctx.phaseId - 1)).current + } + } } - referencedVar + lastDenotation } + protected def loadDenot(implicit ctx: Context) = prefix.member(name) + def isType = name.isTypeName def isTerm = name.isTermName - def symbol(implicit ctx: Context): Symbol = referenced.symbol - def info(implicit ctx: Context): Type = referenced.info + def symbol(implicit ctx: Context): Symbol = denot.symbol + def info(implicit ctx: Context): Type = denot.info - def underlying(implicit ctx: Context): Type = info + override def underlying(implicit ctx: Context): Type = info def isAbstractType(implicit ctx: Context) = info.isRealTypeBounds - override def normalizedPrefix(implicit ctx: Context) = - if (isAbstractType) info.normalizedPrefix else prefix - def derivedNamedType(prefix: Type, name: Name)(implicit ctx: Context): Type = if (prefix eq this.prefix) this else NamedType(prefix, name) @@ -640,40 +627,33 @@ object Types { override def computeHash = doHash(name, prefix) } - abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType { - override def termSymbol(implicit ctx: Context): Symbol = symbol - override def isStable(implicit ctx: Context) = prefix.isStable && termSymbol.isStable - } + abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType - abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType { - override def typeSymbol(implicit ctx: Context): Symbol = symbol - } + abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType trait NamedNoPrefix extends NamedType { protected val fixedSym: Symbol override def symbol(implicit ctx: Context): Symbol = fixedSym override def info(implicit ctx: Context): Type = fixedSym.info - override def referenced(implicit ctx: Context): Reference = new UniqueSymRef(fixedSym, info) + override def denot(implicit ctx: Context): Denotation = fixedSym.denot } final class TermRefNoPrefix(val fixedSym: TermSymbol)(implicit ctx: Context) - extends TermRef(NoPrefix, fixedSym.name) with NamedNoPrefix { - validPeriods = allPeriods(ctx.runId) + extends TermRef(NoPrefix, fixedSym.name) with NamedNoPrefix { } final class TermRefWithSignature(prefix: Type, name: TermName, override val signature: Signature) extends TermRef(prefix, name) { override def computeHash = doHash((name, signature), prefix) - override def referenced(implicit ctx: Context): Reference = - super.referenced.atSignature(signature) + override def loadDenot(implicit ctx: Context): Denotation = + super.loadDenot.atSignature(signature) } final class TypeRefNoPrefix(val fixedSym: TypeSymbol)(implicit ctx: Context) - extends TypeRef(NoPrefix, fixedSym.name) with NamedNoPrefix { - validPeriods = allPeriods(ctx.runId) + extends TypeRef(NoPrefix, fixedSym.name) with NamedNoPrefix { } - final class UniqueTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name) - final class UniqueTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name) + final class CachedTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name) + final class CachedTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name) object NamedType { def apply(prefix: Type, name: Name)(implicit ctx: Context) = @@ -683,7 +663,7 @@ object Types { object TermRef { def apply(prefix: Type, name: TermName)(implicit ctx: Context) = - unique(new UniqueTermRef(prefix, name)) + unique(new CachedTermRef(prefix, name)) def apply(sym: TermSymbol)(implicit ctx: Context) = unique(new TermRefNoPrefix(sym)) def apply(prefix: Type, name: TermName, signature: Signature)(implicit ctx: Context) = @@ -692,127 +672,166 @@ object Types { object TypeRef { def apply(prefix: Type, name: TypeName)(implicit ctx: Context) = - unique(new UniqueTypeRef(prefix, name)) + unique(new CachedTypeRef(prefix, name)) def apply(sym: TypeSymbol)(implicit ctx: Context) = unique(new TypeRefNoPrefix(sym)) } -// --- Other SingletonTypes: ThisType/SuperType/ConstantType --------------------------- + // --- Other SingletonTypes: ThisType/SuperType/ConstantType --------------------------- - abstract case class ThisType(clazz: ClassSymbol) extends SingletonType { - def underlying(implicit ctx: Context) = clazz.typeOfThis - override def isVolatile(implicit ctx: Context): Boolean = false + abstract case class ThisType(clazz: ClassSymbol) extends CachedProxyType with SingletonType { + override def underlying(implicit ctx: Context) = clazz.typeOfThis override def computeHash = doHash(clazz) } - final class UniqueThisType(clazz: ClassSymbol) extends ThisType(clazz) + final class CachedThisType(clazz: ClassSymbol) extends ThisType(clazz) object ThisType { def apply(clazz: ClassSymbol)(implicit ctx: Context) = - unique(new UniqueThisType(clazz)) + unique(new CachedThisType(clazz)) } - abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType { - def underlying(implicit ctx: Context) = supertpe + abstract case class SuperType(thistpe: Type, supertpe: Type) extends CachedProxyType with SingletonType { + override def underlying(implicit ctx: Context) = supertpe def derivedSuperType(thistp: Type, supertp: Type)(implicit ctx: Context) = if ((thistp eq thistpe) && (supertp eq supertpe)) this else SuperType(thistp, supertp) override def computeHash = doHash(thistpe, supertpe) } - final class UniqueSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe) + final class CachedSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe) object SuperType { def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context) = - unique(new UniqueSuperType(thistpe, supertpe)) + unique(new CachedSuperType(thistpe, supertpe)) } - abstract case class ConstantType(value: Constant) extends SingletonType { - def underlying(implicit ctx: Context) = value.tpe - override def deconst: Type = value.tpe + abstract case class ConstantType(value: Constant) extends CachedProxyType with SingletonType { + override def underlying(implicit ctx: Context) = value.tpe override def computeHash = doHash(value) } - final class UniqueConstantType(value: Constant) extends ConstantType(value) + final class CachedConstantType(value: Constant) extends ConstantType(value) object ConstantType { def apply(value: Constant)(implicit ctx: Context) = - unique(new UniqueConstantType(value)) + unique(new CachedConstantType(value)) } - // --- AppliedType ----------------------------------------------------------------- + // --- Refined Type --------------------------------------------------------- - abstract case class AppliedType(tycon: Type, targs: List[Type]) extends UniqueType with TypeProxy { + abstract case class RefinedType(parent: Type) extends CachedProxyType with BindingType { - def underlying(implicit ctx: Context) = tycon + override def underlying(implicit ctx: Context) = parent - def derivedAppliedType(tycon: Type, targs: List[Type])(implicit ctx: Context): Type = - if ((tycon eq this.tycon) && (targs eq this.targs)) this - else AppliedType(tycon, targs) + def derivedRefinedType(parent: Type, names: List[Name], infos: List[Type])(implicit ctx: Context): RefinedType = + if ((parent eq this.parent) && (names eq this.names) && (infos eq this.infos)) this + else + RefinedType(parent, names, infos map (info => (rt: RefinedType) => info.subst(this, rt))) - override def computeHash = doHash(tycon, targs) + def names: List[Name] - override def typeParams(implicit ctx: Context): List[TypeSymbol] = - tycon.typeParams drop targs.length + def infos: List[Type] - override def typeArgs(implicit ctx: Context): List[Type] = targs + def info(name: Name): Type - override def parents(implicit ctx: Context) = - tycon.parents.mapConserve(_.subst(tycon.typeParams, targs)) + // needed??? + //def refine(tp: Type)(implicit ctx: Context): Type + def findDecl(name: Name, pre: Type)(implicit ctx: Context): Denotation = { + val tpe = info(name) + if (tpe == NoType) NoDenotation + else new JointRefDenotation(NoSymbol, tpe.substThis(this, pre), Period.allInRun(ctx.runId)) + } } - final class UniqueAppliedType(tycon: Type, targs: List[Type]) extends AppliedType(tycon, targs) - object AppliedType { - def apply(tycon: Type, targs: List[Type])(implicit ctx: Context) = - unique(new UniqueAppliedType(tycon, targs)) - def make(tycon: Type, targs: List[Type])(implicit ctx: Context) = - if (targs.isEmpty) tycon else apply(tycon, targs) - } + object RefinedType { -// --- Refined Type --------------------------------------------------------- + def make(parent: Type, names: List[Name], infofs: List[RefinedType => Type])(implicit ctx: Context): Type = + if (names.isEmpty) parent + else apply(parent, names, infofs) - case class RefinedType(parent: Type, names: List[Name])(infosExpr: RefinedType => List[Type]) extends UniqueType with TypeProxy { + def apply(parent: Type, names: List[Name], infofs: List[RefinedType => Type])(implicit ctx: Context): RefinedType = + names.length match { + case 1 => apply(parent, names.head, infofs.head) + case 2 => apply(parent, names.head, infofs.head, names.tail.head, infofs.tail.head) + case _ => unique(new RefinedTypeN(parent, names, infofs)) + } - def underlying(implicit ctx: Context) = parent + def apply(parent: Type, name1: Name, infof1: RefinedType => Type)(implicit ctx: Context): RefinedType1 = + unique(new RefinedType1(parent, name1, infof1)) - lazy val infos = infosExpr(this) + def apply(parent: Type, name1: Name, infof1: RefinedType => Type, name2: Name, infof2: RefinedType => Type)(implicit ctx: Context): RefinedType2 = + unique(new RefinedType2(parent, name1, infof1, name2, infof2)) + } - def derivedRefinedType(parent1: Type, names1: List[Name], infos1: List[Type])(implicit ctx: Context): RefinedType = - if ((parent1 eq parent) && (names1 eq names) && (infos1 eq infos)) this - else - RefinedType(parent1, names1) { rt => - val thistp = RefinedThis(rt) - infos1 map (_.substThis(this, thistp)) - } + class RefinedType1(parent: Type, val name1: Name, infof1: RefinedType => Type) extends RefinedType(parent) { + val info1 = infof1(this) + def names = name1 :: Nil + def infos = info1 :: Nil + def info(name: Name) = + if (name == name1) info1 + else NoType + def derivedRefinedType1(parent: Type, name1: Name, info1: Type)(implicit ctx: Context): RefinedType1 = + if ((parent eq this.parent) && (name1 eq this.name1) && (info1 eq this.info1)) this + else RefinedType(parent, name1, rt => info1.substThis(this, RefinedThis(rt))) + + /*def refine(parent: Type)(implicit ctx: Context) = + if (parent.nonPrivateMember(name1).exists) + derivedRefinedType1(parent, name1, info1) + else parent*/ + + override def computeHash = doHash(name1, info1, parent) + } + + class RefinedType2(parent: Type, val name1: Name, infof1: RefinedType => Type, val name2: Name, infof2: RefinedType => Type) extends RefinedType(parent) { + val info1 = infof1(this) + val info2 = infof2(this) + def names = name1 :: name2 :: Nil + def infos = info1 :: info2 :: Nil + def info(name: Name) = + if (name == name1) info1 + else if (name == name2) info2 + else NoType + + def derivedRefinedType2(parent: Type, name1: Name, info1: Type, name2: Name, info2: Type)(implicit ctx: Context): RefinedType2 = + if ((parent eq this.parent) && (name1 eq this.name1) && (info1 eq this.info1) && (name2 eq this.name2) && (info2 eq this.info2)) this + else RefinedType(parent, name1, rt => info1.substThis(this, RefinedThis(rt)), name2, rt => info2.substThis(this, RefinedThis(rt))) + + /*def refine(parent: Type)(implicit ctx: Context) = + if (parent.nonPrivateMember(name1).exists || + parent.nonPrivateMember(name2).exists) + derivedRefinedType2(parent, name1, info1, name2, info2) + else parent*/ + + override def computeHash = doHash(name1, name2, info1, info2, parent) + } + + class RefinedTypeN(parent: Type, val names: List[Name], infofs: List[RefinedType => Type]) extends RefinedType(parent) { + val infos = infofs map (_(this)) - def findDecl(name: Name, pre: Type)(implicit ctx: Context): Reference = { + def info(name: Name): Type = { var ns = names var is = infos - var ref: Reference = NoRef - while (ns.nonEmpty && (ref eq NoRef)) { - if (ns.head == name) - ref = new JointSymRef(NoSymbol, is.head.substThis(this, pre)) + while (ns.nonEmpty) { + if (ns.head == name) return is.head ns = ns.tail is = is.tail } - ref + NoType } - override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = - parent.findMember(name, pre, excluded | Flags.Private) & - findDecl(name, pre) + /*def refine(parent: Type)(implicit ctx: Context) = + if (names exists (parent.nonPrivateMember(_).exists)) + derivedRefinedType(parent, names, infos) + else parent*/ - override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - parent.memberNames(pre, keepOnly) ++ (names filter (keepOnly(pre, _))).toSet - - def computeHash = doHash(names, parent, infos) + override def computeHash = doHash(names, parent, infos) } + // --- AndType/OrType --------------------------------------------------------------- -// --- AndType/OrType --------------------------------------------------------------- - - abstract case class AndType(tp1: Type, tp2: Type) extends UniqueType { + abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType { type This <: AndType @@ -820,65 +839,57 @@ object Types { if ((t1 eq tp1) && (t2 eq tp2)) this else AndType(t1, t2) - override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = - tp1.findMember(name, pre, excluded) & tp2.findMember(name, pre, excluded) - - override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - tp1.memberNames(pre, keepOnly) | tp2.memberNames(pre, keepOnly) - - override def parents(implicit ctx: Context): List[Type] = { - def components(tp: Type): List[Type] = tp match { - case AndType(tp1, tp2) => components(tp1) ++ components(tp2) - case _ => List(tp) - } - components(this) - } - override def computeHash = doHash(tp1, tp2) } - final class UniqueAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2) + final class CachedAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2) object AndType { def apply(tp1: Type, tp2: Type)(implicit ctx: Context) = - unique(new UniqueAndType(tp1, tp2)) + unique(new CachedAndType(tp1, tp2)) } - abstract case class OrType(tp1: Type, tp2: Type) extends UniqueType { + abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType { def derivedOrType(t1: Type, t2: Type)(implicit ctx: Context) = if ((t1 eq tp1) && (t2 eq tp2)) this else OrType(t1, t2) - override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = { - (tp1.findMember(name, pre, excluded) | tp2.findMember(name, pre, excluded))(pre) - } - - override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - tp1.memberNames(pre, keepOnly) & tp2.memberNames(pre, keepOnly) - override def computeHash = doHash(tp1, tp2) } - final class UniqueOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2) + final class CachedOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2) object OrType { def apply(tp1: Type, tp2: Type)(implicit ctx: Context) = - unique(new UniqueOrType(tp1, tp2)) + unique(new CachedOrType(tp1, tp2)) } -// ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam --------------- + // ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam --------------- + + trait BindingType extends Type - abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends UniqueType { + // Note: method types are cached whereas poly types are not. + // The reason is that most poly types are cyclic via poly params, + // and therefore two different poly types would never be equal. + + abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends CachedGroundType with BindingType { lazy val resultType = resultTypeExp(this) def isJava = false def isImplicit = false + lazy val isDependent = resultType exists { case MethodParam(mt, _) => mt eq this case _ => false } - def paramSig(tp: Type): TypeName = ??? - override lazy val signature: Signature = - (paramTypes map paramSig) ++ resultType.subSignature + + override lazy val signature: List[TypeName] = { + def paramSig(tp: Type): TypeName = ??? + val followSig = resultType match { + case rtp: MethodType => rtp.signature + case _ => Nil + } + (paramTypes map paramSig) ++ followSig + } def derivedMethodType(paramNames: List[TermName], paramTypes: List[Type], restpe: Type)(implicit ctx: Context) = if ((paramNames eq this.paramNames) && (paramTypes eq this.paramTypes) && (restpe eq this.resultType)) this @@ -896,52 +907,55 @@ object Types { override def computeHash = doHash(paramNames, resultType, paramTypes) } - final class UniqueMethodType(paramNames: List[TermName], paramTypes: List[Type]) - (resultTypeExp: MethodType => Type) - extends MethodType(paramNames, paramTypes)(resultTypeExp) - final class JavaMethodType(paramNames: List[TermName], paramTypes: List[Type]) - (resultTypeExp: MethodType => Type) - extends MethodType(paramNames, paramTypes)(resultTypeExp) { + final class CachedMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) + extends MethodType(paramNames, paramTypes)(resultTypeExp) + + final class JavaMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) + extends MethodType(paramNames, paramTypes)(resultTypeExp) { override def isJava = true } - final class ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type]) - (resultTypeExp: MethodType => Type) - extends MethodType(paramNames, paramTypes)(resultTypeExp) { + + final class ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) + extends MethodType(paramNames, paramTypes)(resultTypeExp) { override def isImplicit = true } object MethodType { def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = - unique(new UniqueMethodType(paramNames, paramTypes)(resultTypeExp)) + unique(new CachedMethodType(paramNames, paramTypes)(resultTypeExp)) } + def JavaMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = unique(new JavaMethodType(paramNames, paramTypes)(resultTypeExp)) + def ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = unique(new ImplicitMethodType(paramNames, paramTypes)(resultTypeExp)) - abstract case class ExprType(resultType: Type) extends UniqueType with TypeProxy { - def underlying(implicit ctx: Context): Type = resultType + abstract case class ExprType(resultType: Type) extends CachedProxyType { + override def underlying(implicit ctx: Context): Type = resultType + override def signature: Signature = Nil def derivedExprType(rt: Type)(implicit ctx: Context) = if (rt eq resultType) this else ExprType(rt) override def computeHash = doHash(resultType) } - final class UniqueExprType(resultType: Type) extends ExprType(resultType) + final class CachedExprType(resultType: Type) extends ExprType(resultType) object ExprType { def apply(resultType: Type)(implicit ctx: Context) = - unique(new UniqueExprType(resultType)) + unique(new CachedExprType(resultType)) } - case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends Type { + case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) + extends UncachedGroundType with BindingType { lazy val paramBounds = paramBoundsExp(this) lazy val resultType = resultTypeExp(this) + override def signature = resultType.signature + def instantiate(argTypes: List[Type])(implicit ctx: Context): Type = new InstPolyMap(this, argTypes) apply resultType - override def signature: Signature = resultType.subSignature - def derivedPolyType(paramNames: List[TypeName], paramBounds: List[TypeBounds], restpe: Type)(implicit ctx: Context) = if ((paramNames eq this.paramNames) && (paramBounds eq this.paramBounds) && (restpe eq this.resultType)) this else @@ -949,6 +963,8 @@ object Types { x => paramBounds mapConserve (_.substBounds(this, x)), x => restpe.subst(this, x)) + // need to override hashCode and equals to be object identity + // because paramNames by itself is not discriminatory enough override def hashCode = System.identityHashCode(this) override def equals(other: Any) = other match { case that: PolyType => this eq that @@ -956,87 +972,71 @@ object Types { } } - case class MethodParam(mt: MethodType, paramNum: Int) extends SingletonType { - def underlying(implicit ctx: Context) = mt.paramTypes(paramNum) - override def computeHash = NotCached + abstract class BoundType extends UncachedProxyType { + type BT <: BindingType + def binder: BT + def copy(bt: BT): Type } - case class RefinedThis(rt: RefinedType) extends SingletonType { - def underlying(implicit ctx: Context) = rt.parent - override def computeHash = NotCached + case class MethodParam(binder: MethodType, paramNum: Int) extends BoundType with SingletonType { + type BT = MethodType + override def underlying(implicit ctx: Context) = binder.paramTypes(paramNum) + override def hashCode = doHash(System.identityHashCode(binder) + paramNum) + def copy(bt: BT) = MethodParam(bt, paramNum) } - case class PolyParam(pt: PolyType, paramNum: Int) extends TypeProxy { - def underlying(implicit ctx: Context) = pt.paramBounds(paramNum).hi + case class PolyParam(binder: PolyType, paramNum: Int) extends BoundType { + type BT = PolyType + override def underlying(implicit ctx: Context) = binder.paramBounds(paramNum).hi + def copy(bt: BT) = PolyParam(bt, paramNum) + // no hashCode needed because cycle is broken in PolyType } -// ------ ClassInfo, Type Bounds ------------------------------------------------------------ + case class RefinedThis(binder: RefinedType) extends BoundType with SingletonType { + type BT = RefinedType + override def underlying(implicit ctx: Context) = binder.parent + def copy(bt: BT) = RefinedThis(bt) + override def hashCode = doHash(System.identityHashCode(binder)) + } - abstract case class ClassInfo(prefix: Type, classd: ClassDenotation) extends UniqueType { - override def typeSymbol(implicit ctx: Context) = classd.clazz + // ------ ClassInfo, Type Bounds ------------------------------------------------------------ - def typeTemplate(implicit ctx: Context): Type = - classd.typeTemplate asSeenFrom (prefix, classd.clazz) + abstract case class ClassInfo(prefix: Type, classd: ClassDenotation) extends CachedGroundType { +/* def typeTemplate(implicit ctx: Context): Type = + classd.typeTemplate asSeenFrom (prefix, classd.symbol) +*/ def typeConstructor(implicit ctx: Context): Type = - NamedType(prefix, classd.clazz.name) - - override def normalizedPrefix(implicit ctx: Context) = prefix - - override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = - findMemberAmong(classd.memberRefsNamed(name), pre, classd.clazz, excluded) - - private def findMemberAmong(candidates: RefSet, pre: Type, owner: ClassSymbol, excluded: FlagSet) - (implicit ctx: Context): Reference = { - val resultSyms = candidates - .filterAccessibleFrom(pre) - .filterExcluded(excluded) - .asSeenFrom(pre, owner) - if (resultSyms.exists) resultSyms.toRef - else ErrorRef // todo: refine - } - - override def baseClasses(implicit ctx: Context): List[ClassSymbol] = - classd.baseClasses + NamedType(prefix, classd.symbol.name) - override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = - classd.memberNames(keepOnly) filter (keepOnly(pre, _)) + // cached because baseType needs parents + private var parentsCache: List[TypeRef] = null - private var parentsCache: List[Type] = null - // !!! caching needed here? If yes, cache AppliedType as well? - - override def decls(implicit ctx: Context) = classd.decls - - override def parents(implicit ctx: Context) = { + override def parents(implicit ctx: Context): List[TypeRef] = { if (parentsCache == null) - parentsCache = classd.parents.mapConserve(_.substThis(classd.clazz, prefix)) + parentsCache = classd.parents.mapConserve(_.substThis(classd.symbol, prefix).asInstanceOf[TypeRef]) parentsCache } - override def typeParams(implicit ctx: Context) = classd.typeParams - - override def computeHash = doHash(classd.clazz, prefix) + override def computeHash = doHash(classd.symbol, prefix) } - final class UniqueClassInfo(prefix: Type, classd: ClassDenotation) extends ClassInfo(prefix, classd) + final class CachedClassInfo(prefix: Type, classd: ClassDenotation) extends ClassInfo(prefix, classd) object ClassInfo { def apply(prefix: Type, classd: ClassDenotation)(implicit ctx: Context) = - unique(new UniqueClassInfo(prefix, classd)) + unique(new CachedClassInfo(prefix, classd)) } - abstract case class TypeBounds(lo: Type, hi: Type) extends UniqueType with TypeProxy { - def underlying(implicit ctx: Context): Type = hi + abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType { + override def underlying(implicit ctx: Context): Type = hi def derivedTypeBounds(lo1: Type, hi1: Type)(implicit ctx: Context) = if ((lo1 eq lo) && (hi1 eq hi)) this else TypeBounds(lo, hi) - override def isRealTypeBounds = lo ne hi - override def bounds(implicit ctx: Context): TypeBounds = this - - def & (that: TypeBounds)(implicit ctx: Context): TypeBounds = + def &(that: TypeBounds)(implicit ctx: Context): TypeBounds = TypeBounds(this.lo | that.lo, this.hi & that.hi) - def | (that: TypeBounds)(implicit ctx: Context): TypeBounds = + def |(that: TypeBounds)(implicit ctx: Context): TypeBounds = TypeBounds(this.lo & that.lo, this.hi | that.hi) def substBounds(from: PolyType, to: PolyType)(implicit ctx: Context) = @@ -1044,49 +1044,51 @@ object Types { def map(f: Type => Type)(implicit ctx: Context): TypeBounds = TypeBounds(f(lo), f(hi)) + override def computeHash = doHash(lo, hi) } - final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) + final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) object TypeBounds { def apply(lo: Type, hi: Type)(implicit ctx: Context) = - unique(new UniqueTypeBounds(lo, hi)) + unique(new CachedTypeBounds(lo, hi)) } -// ----- AnnotatedTypes ----------------------------------------------------------- + // ----- AnnotatedTypes ----------------------------------------------------------- - case class AnnotatedType(annots: List[AnnotationInfo], tpe: Type) extends TypeProxy { - def underlying(implicit ctx: Context): Type = tpe - def derivedAnnotatedType(annots1: List[AnnotationInfo], tpe1: Type) = + case class AnnotatedType(annots: List[Annotation], tpe: Type) extends UncachedProxyType { + override def underlying(implicit ctx: Context): Type = tpe + def derivedAnnotatedType(annots1: List[Annotation], tpe1: Type) = if ((annots1 eq annots) && (tpe1 eq tpe)) this else AnnotatedType.make(annots1, tpe1) } object AnnotatedType { - def make(annots: List[AnnotationInfo], underlying: Type) = + def make(annots: List[Annotation], underlying: Type) = if (annots.isEmpty) underlying else AnnotatedType(annots, underlying) } -// Special type objects ------------------------------------------------------------ + // Special type objects ------------------------------------------------------------ - case object NoType extends Type { + case object NoType extends UncachedGroundType { def symbol = NoSymbol def info = NoType } - case object NoPrefix extends UniqueType { + /** Cached for efficiency because hashing is faster */ + case object NoPrefix extends CachedGroundType { override def computeHash = hashSeed } - abstract class ErrorType extends Type + abstract class ErrorType extends UncachedGroundType object ErrorType extends ErrorType - case object WildcardType extends Type + case object WildcardType extends UncachedGroundType -// ----- TypeMaps -------------------------------------------------------------------- + // ----- TypeMaps -------------------------------------------------------------------- abstract class TypeMap(implicit ctx: Context) extends (Type => Type) { def apply(tp: Type): Type @@ -1096,15 +1098,20 @@ object Types { /** Map this function over given type */ def mapOver(tp: Type): Type = tp match { - case tp: NamedType => + case tp: NamedType => tp.derivedNamedType(this(tp.prefix), tp.name) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) => tp + case _: ThisType + | _: BoundType => tp - case tp @ AppliedType(tycon, targs) => - tp.derivedAppliedType(this(tycon), targs mapConserve this) + case tp: RefinedType1 => + tp.derivedRefinedType1(this(tp.parent), tp.name1, this(tp.info1)) + + case tp: RefinedType2 => + tp.derivedRefinedType2(this(tp.parent), tp.name1, this(tp.info1), tp.name2, this(tp.info2)) + + case tp: RefinedTypeN => + tp.derivedRefinedType(this(tp.parent), tp.names, tp.infos mapConserve this) case tp @ PolyType(pnames) => tp.derivedPolyType( @@ -1127,9 +1134,6 @@ object Types { tp.derivedTypeBounds(this(lo), this(hi)) } - case tp @ RefinedType(parent, names) => - tp.derivedRefinedType(this(parent), names, tp.infos mapConserve this) - case tp @ AnnotatedType(annots, underlying) => tp.derivedAnnotatedType(mapOverAnnotations(annots), this(underlying)) @@ -1137,7 +1141,7 @@ object Types { tp } - def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = ??? + def mapOverAnnotations(annots: List[Annotation]): List[Annotation] = ??? } @@ -1155,45 +1159,35 @@ object Types { } } - class InstRefinedMap(rt: RefinedType)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp match { - case RefinedThis(`rt`) => rt.parent - case _ => mapOver(tp) - } - } - - class AsSeenFromMap(pre: Type, clazz: Symbol)(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = tp.asSeenFrom(pre, clazz, this) - } -// todo: prevent unstable prefixes in variables? - - -// ----- TypeAccumulators ---------------------------------------------------- + // ----- TypeAccumulators ---------------------------------------------------- abstract class TypeAccumulator[T] extends ((T, Type) => T) { def apply(x: T, tp: Type): T - def apply(x: T, annot: AnnotationInfo): T = ??? + def apply(x: T, annot: Annotation): T = ??? def foldOver(x: T, tp: Type): T = tp match { case tp: NamedType => this(x, tp.prefix) - case ThisType(_) - | MethodParam(_, _) - | PolyParam(_, _) - | ConstantType(_) - | NoPrefix => x + case _: ThisType + | _: BoundType => x + + case tp: RefinedType1 => + this(this(x, tp.parent), tp.info1) - case AppliedType(tycon, targs) => - (this(x, tycon) /: targs) (this) + case tp: RefinedType2 => + this(this(this(x, tp.parent), tp.info1), tp.info2) + + case tp: RefinedTypeN => + (this(x, tp.parent) /: tp.infos)(apply) case tp @ PolyType(pnames) => - this((x /: tp.paramBounds) (this), tp.resultType) + this((x /: tp.paramBounds)(this), tp.resultType) case tp @ MethodType(pnames, ptypes) => - this((x /: ptypes) (this), tp.resultType) + this((x /: ptypes)(this), tp.resultType) case ExprType(restpe) => this(x, restpe) @@ -1204,11 +1198,8 @@ object Types { case TypeBounds(lo, hi) => this(this(x, lo), hi) - case tp @ RefinedType(parent, names) => - (this(x, parent) /: tp.infos) (apply) - case AnnotatedType(annots, underlying) => - this((x /: annots) (apply), underlying) + this((x /: annots)(apply), underlying) case _ => x } @@ -1218,7 +1209,7 @@ object Types { def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp) } -// ----- Name Filters -------------------------------------------------- + // ----- Name Filters -------------------------------------------------- /** A name filter selects or discards a member name of a type `pre`. * To enable efficient caching, name filters have to satisfy the @@ -1243,18 +1234,14 @@ object Types { name.isTermName && (pre member name).symbol.isDeferred } -// ----- Exceptions ------------------------------------------------------------- + // ----- Exceptions ------------------------------------------------------------- class TypeError(msg: String) extends Exception(msg) class FatalTypeError(msg: String) extends TypeError(msg) class MalformedType(pre: Type, sym: Symbol) extends FatalTypeError(s"malformed type: $pre.$sym") class CyclicReference(sym: Symbol) extends FatalTypeError("cyclic reference involving $sym") -// ----- Implicit decorators --------------------------------------------------- - - implicit def substOps(tp: Type): SubstOps = new SubstOps(tp) - -// ----- Misc utilities --------------------------------------------------------- + // ----- Misc utilities --------------------------------------------------------- /** like map2, but returns list `xs` itself - instead of a copy - if function * `f` maps all elements to themselves. @@ -1279,4 +1266,4 @@ object Types { } case _ => ys.isEmpty } -}
\ No newline at end of file +} |