package dotty.tools.dotc
package core
import SymDenotations.{SymDenotation, NoDenotation}
import Contexts.Context
import Names.Name
import Names.TypeName
import Symbols.NoSymbol
import Symbols.Symbol
import Types._, Periods._, Flags._, Transformers._
/** 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
* | | v
* | | 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 {
/** 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 a reference to a term symbol? */
def isTerm: Boolean = !isType
/** Is this denotation overloaded? */
def isOverloaded = isInstanceOf[MultiDenotation]
/** The signature of the denotation */
def signature: Signature
/** Resolve overloaded denotation to pick the one with the given signature */
def atSignature(sig: Signature): SingleDenotation
/** The variant of this denotation that's current in the given context. */
def current(implicit ctx: Context): Denotation
def exists: Boolean = true
/** 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
}
/** 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 | (that: Denotation)(pre: Type)(implicit ctx: Context): Denotation = {
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"$this | $that")
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
}
}
}
}
/** The class of overloaded denotations
* @param variants The overloaded variants indexed by thheir signatures.
*/
case class MultiDenotation(denot1: Denotation, denot2: Denotation) extends Denotation {
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 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)
}
abstract class SingleDenotation extends Denotation with DenotationSet {
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 derivedSingleDenotation(s: Symbol, i: Type): SingleDenotation =
if ((s eq symbol) && (i eq info)) this else copy(s, i)
protected def copy(s: Symbol, i: Type): SingleDenotation = this
def orElse(that: => SingleDenotation) = if (this.exists) this else that
def atSignature(sig: Signature): SingleDenotation =
if (sig == signature) this else NoDenotation
// ------ Transformations -----------------------------------------
private[this] var _validFor: Period = Nowhere
def validFor = _validFor
def validFor_=(p: Period) =
_validFor = p
/** 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.
*/
var nextInRun: SingleDenotation = this
/** The version of this SingleDenotation that was valid in the first phase
* of this run.
*/
def initial: SingleDenotation = {
var current = nextInRun
while (current.validFor.code > this._validFor.code) current = current.nextInRun
current
}
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 {
// 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)
}
} else {
// currentPeriod < valid; in this case a version must exist
do {
current = current.nextInRun
} while (!(current.validFor contains currentPeriod))
}
current
}
def asSymDenotation = asInstanceOf[SymDenotation]
// ------ DenotationSet ops ----------------------------------------------
def toDenot(implicit ctx: Context) = this
def containsSig(sig: Signature)(implicit ctx: Context) =
signature == sig
def filter(p: Symbol => Boolean)(implicit ctx: Context): DenotationSet =
if (p(symbol)) this else NoDenotation
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.hasFlag(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))
}
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)
}
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)
}
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 filter(p: Symbol => Boolean)(implicit ctx: Context): DenotationSet
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)
}
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))
}
}
