path: root/src/dotty/tools/dotc/core/Denotations.scala

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._
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 {

  /** 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

    /** 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

    def filter(p: Symbol => Boolean)(implicit ctx: Context): Denotation

    /** 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 is Deferred) || (sym2 is Deferred) || !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 findSymbol qualifies
      }

      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 {
    final override def isType = false
    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)
  }

  abstract class SingleDenotation extends Denotation with DenotationSet {
    override def isType = info.isInstanceOf[TypeType]
    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 newLikeThis(s, i)

    protected def newLikeThis(s: Symbol, i: Type): SingleDenotation = this

    def orElse(that: => SingleDenotation) = if (this.exists) this else that

    def filter(p: Symbol => Boolean)(implicit ctx: Context): SingleDenotation =
      if (p(symbol)) this else NoDenotation

    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.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
    }

    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))
  }

  class UniqueRefDenotation(val symbol: Symbol,
                     val info: Type,
                     initValidFor: Period) extends SingleDenotation {
    validFor = initValidFor
    override protected def newLikeThis(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 newLikeThis(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 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))
  }
}