alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Scala example source code file (TypeMaps.scala)

This example Scala source code file (TypeMaps.scala) is included in my "Source Code Warehouse" project. The intent of this project is to help you more easily find Scala source code examples by using tags.

All credit for the original source code belongs to scala-lang.org; I'm just trying to make examples easier to find. (For my Scala work, see my Scala examples and tutorials.)

Scala tags/keywords

annotation, boolean, collection, list, singletype, some, symbol, t, tree, type, typemap, typeref

The TypeMaps.scala Scala example source code

package scala
package reflect
package internal
package tpe

import scala.collection.{ mutable, immutable }
import Flags._
import scala.annotation.tailrec
import Variance._

private[internal] trait TypeMaps {
  self: SymbolTable =>
  import definitions._

  /** Normalize any type aliases within this type (@see Type#normalize).
    *  Note that this depends very much on the call to "normalize", not "dealias",
    *  so it is no longer carries the too-stealthy name "deAlias".
    */
  object normalizeAliases extends TypeMap {
    def apply(tp: Type): Type = mapOver(tp match {
      case TypeRef(_, sym, _) if sym.isAliasType && tp.isHigherKinded => logResult(s"Normalized type alias function $tp")(tp.normalize)
      case TypeRef(_, sym, _) if sym.isAliasType                      => tp.normalize
      case tp                                                         => tp
    })
  }

  /** Remove any occurrence of type <singleton> from this type and its parents */
  object dropSingletonType extends TypeMap {
    def apply(tp: Type): Type = {
      tp match {
        case TypeRef(_, SingletonClass, _) =>
          AnyTpe
        case tp1 @ RefinedType(parents, decls) =>
          parents filter (_.typeSymbol != SingletonClass) match {
            case Nil                       => AnyTpe
            case p :: Nil if decls.isEmpty => mapOver(p)
            case ps                        => mapOver(copyRefinedType(tp1, ps, decls))
          }
        case tp1 =>
          mapOver(tp1)
      }
    }
  }

  /** Type with all top-level occurrences of abstract types replaced by their bounds */
  object abstractTypesToBounds extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case TypeRef(_, sym, _) if sym.isAliasType    => apply(tp.dealias)
      case TypeRef(_, sym, _) if sym.isAbstractType => apply(tp.bounds.hi)
      case rtp @ RefinedType(parents, decls)        => copyRefinedType(rtp, parents mapConserve this, decls)
      case AnnotatedType(_, _)                      => mapOver(tp)
      case _                                        => tp             // no recursion - top level only
    }
  }

  // Set to true for A* => Seq[A]
  //   (And it will only rewrite A* in method result types.)
  //   This is the pre-existing behavior.
  // Or false for Seq[A] => Seq[A]
  //   (It will rewrite A* everywhere but method parameters.)
  //   This is the specified behavior.
  protected def etaExpandKeepsStar = false

  /** Turn any T* types into Seq[T] except when
    *  in method parameter position.
    */
  object dropIllegalStarTypes extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case MethodType(params, restpe) =>
        // Not mapping over params
        val restpe1 = apply(restpe)
        if (restpe eq restpe1) tp
        else MethodType(params, restpe1)
      case TypeRef(_, RepeatedParamClass, arg :: Nil) =>
        seqType(arg)
      case _ =>
        if (etaExpandKeepsStar) tp else mapOver(tp)
    }
  }

  trait AnnotationFilter extends TypeMap {
    def keepAnnotation(annot: AnnotationInfo): Boolean

    override def mapOver(annot: AnnotationInfo) =
      if (keepAnnotation(annot)) super.mapOver(annot)
      else UnmappableAnnotation
  }

  trait KeepOnlyTypeConstraints extends AnnotationFilter {
    // filter keeps only type constraint annotations
    def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass
  }

  // todo. move these into scala.reflect.api

  /** A prototype for mapping a function over all possible types
    */
  abstract class TypeMap(trackVariance: Boolean) extends (Type => Type) {
    def this() = this(trackVariance = false)
    def apply(tp: Type): Type

    private[this] var _variance: Variance = if (trackVariance) Covariant else Invariant

    def variance_=(x: Variance) = { assert(trackVariance, this) ; _variance = x }
    def variance = _variance

    /** Map this function over given type */
    def mapOver(tp: Type): Type = tp match {
      case tr @ TypeRef(pre, sym, args) =>
        val pre1 = this(pre)
        val args1 = (
          if (trackVariance && args.nonEmpty && !variance.isInvariant && sym.typeParams.nonEmpty)
            mapOverArgs(args, sym.typeParams)
          else
            args mapConserve this
          )
        if ((pre1 eq pre) && (args1 eq args)) tp
        else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), args1)
      case ThisType(_) => tp
      case SingleType(pre, sym) =>
        if (sym.isPackageClass) tp // short path
        else {
          val pre1 = this(pre)
          if (pre1 eq pre) tp
          else singleType(pre1, sym)
        }
      case MethodType(params, result) =>
        val params1 = flipped(mapOver(params))
        val result1 = this(result)
        if ((params1 eq params) && (result1 eq result)) tp
        else copyMethodType(tp, params1, result1.substSym(params, params1))
      case PolyType(tparams, result) =>
        val tparams1 = flipped(mapOver(tparams))
        val result1 = this(result)
        if ((tparams1 eq tparams) && (result1 eq result)) tp
        else PolyType(tparams1, result1.substSym(tparams, tparams1))
      case NullaryMethodType(result) =>
        val result1 = this(result)
        if (result1 eq result) tp
        else NullaryMethodType(result1)
      case ConstantType(_) => tp
      case SuperType(thistp, supertp) =>
        val thistp1 = this(thistp)
        val supertp1 = this(supertp)
        if ((thistp1 eq thistp) && (supertp1 eq supertp)) tp
        else SuperType(thistp1, supertp1)
      case TypeBounds(lo, hi) =>
        val lo1 = flipped(this(lo))
        val hi1 = this(hi)
        if ((lo1 eq lo) && (hi1 eq hi)) tp
        else TypeBounds(lo1, hi1)
      case BoundedWildcardType(bounds) =>
        val bounds1 = this(bounds)
        if (bounds1 eq bounds) tp
        else BoundedWildcardType(bounds1.asInstanceOf[TypeBounds])
      case rtp @ RefinedType(parents, decls) =>
        val parents1 = parents mapConserve this
        val decls1 = mapOver(decls)
        copyRefinedType(rtp, parents1, decls1)
      case ExistentialType(tparams, result) =>
        val tparams1 = mapOver(tparams)
        val result1 = this(result)
        if ((tparams1 eq tparams) && (result1 eq result)) tp
        else newExistentialType(tparams1, result1.substSym(tparams, tparams1))
      case OverloadedType(pre, alts) =>
        val pre1 = if (pre.isInstanceOf[ClassInfoType]) pre else this(pre)
        if (pre1 eq pre) tp
        else OverloadedType(pre1, alts)
      case AntiPolyType(pre, args) =>
        val pre1 = this(pre)
        val args1 = args mapConserve this
        if ((pre1 eq pre) && (args1 eq args)) tp
        else AntiPolyType(pre1, args1)
      case tv@TypeVar(_, constr) =>
        if (constr.instValid) this(constr.inst)
        else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params))  //@M !args.isEmpty implies !typeParams.isEmpty
      case AnnotatedType(annots, atp) =>
        val annots1 = mapOverAnnotations(annots)
        val atp1 = this(atp)
        if ((annots1 eq annots) && (atp1 eq atp)) tp
        else if (annots1.isEmpty) atp1
        else AnnotatedType(annots1, atp1)
      /*
            case ErrorType => tp
            case WildcardType => tp
            case NoType => tp
            case NoPrefix => tp
            case ErasedSingleType(sym) => tp
      */
      case _ =>
        tp
      // throw new Error("mapOver inapplicable for " + tp);
    }

    def withVariance[T](v: Variance)(body: => T): T = {
      val saved = variance
      variance = v
      try body finally variance = saved
    }
    @inline final def flipped[T](body: => T): T = {
      if (trackVariance) variance = variance.flip
      try body
      finally if (trackVariance) variance = variance.flip
    }
    protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = (
      if (trackVariance)
        map2Conserve(args, tparams)((arg, tparam) => withVariance(variance * tparam.variance)(this(arg)))
      else
        args mapConserve this
      )
    /** Applies this map to the symbol's info, setting variance = Invariant
      *  if necessary when the symbol is an alias.
      */
    private def applyToSymbolInfo(sym: Symbol): Type = {
      if (trackVariance && !variance.isInvariant && sym.isAliasType)
        withVariance(Invariant)(this(sym.info))
      else
        this(sym.info)
    }

    /** Called by mapOver to determine whether the original symbols can
      *  be returned, or whether they must be cloned.
      */
    protected def noChangeToSymbols(origSyms: List[Symbol]): Boolean = {
      @tailrec def loop(syms: List[Symbol]): Boolean = syms match {
        case Nil     => true
        case x :: xs => (x.info eq applyToSymbolInfo(x)) && loop(xs)
      }
      loop(origSyms)
    }

    /** Map this function over given scope */
    def mapOver(scope: Scope): Scope = {
      val elems = scope.toList
      val elems1 = mapOver(elems)
      if (elems1 eq elems) scope
      else newScopeWith(elems1: _*)
    }

    /** Map this function over given list of symbols */
    def mapOver(origSyms: List[Symbol]): List[Symbol] = {
      // fast path in case nothing changes due to map
      if (noChangeToSymbols(origSyms)) origSyms
      // map is not the identity --> do cloning properly
      else cloneSymbolsAndModify(origSyms, TypeMap.this)
    }

    def mapOver(annot: AnnotationInfo): AnnotationInfo = {
      val AnnotationInfo(atp, args, assocs) = annot
      val atp1  = mapOver(atp)
      val args1 = mapOverAnnotArgs(args)
      // there is no need to rewrite assocs, as they are constants

      if ((args eq args1) && (atp eq atp1)) annot
      else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation  // some annotation arg was unmappable
      else AnnotationInfo(atp1, args1, assocs) setPos annot.pos
    }

    def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = {
      val annots1 = annots mapConserve mapOver
      if (annots1 eq annots) annots
      else annots1 filterNot (_ eq UnmappableAnnotation)
    }

    /** Map over a set of annotation arguments.  If any
      *  of the arguments cannot be mapped, then return Nil.  */
    def mapOverAnnotArgs(args: List[Tree]): List[Tree] = {
      val args1 = args mapConserve mapOver
      if (args1 contains UnmappableTree) Nil
      else args1
    }

    def mapOver(tree: Tree): Tree =
      mapOver(tree, () => return UnmappableTree)

    /** Map a tree that is part of an annotation argument.
      *  If the tree cannot be mapped, then invoke giveup().
      *  The default is to transform the tree with
      *  TypeMapTransformer.
      */
    def mapOver(tree: Tree, giveup: ()=>Nothing): Tree =
      (new TypeMapTransformer).transform(tree)

    /** This transformer leaves the tree alone except to remap
      *  its types. */
    class TypeMapTransformer extends Transformer {
      override def transform(tree: Tree) = {
        val tree1 = super.transform(tree)
        val tpe1 = TypeMap.this(tree1.tpe)
        if ((tree eq tree1) && (tree.tpe eq tpe1))
          tree
        else
          tree1.shallowDuplicate.setType(tpe1)
      }
    }
  }

  abstract class TypeTraverser extends TypeMap {
    def traverse(tp: Type): Unit
    def apply(tp: Type): Type = { traverse(tp); tp }
  }

  abstract class TypeTraverserWithResult[T] extends TypeTraverser {
    def result: T
    def clear(): Unit
  }

  abstract class TypeCollector[T](initial: T) extends TypeTraverser {
    var result: T = _
    def collect(tp: Type) = {
      result = initial
      traverse(tp)
      result
    }
  }

  /** The raw to existential map converts a ''raw type'' to an existential type.
    *  It is necessary because we might have read a raw type of a
    *  parameterized Java class from a class file. At the time we read the type
    *  the corresponding class file might still not be read, so we do not
    *  know what the type parameters of the type are. Therefore
    *  the conversion of raw types to existential types might not have taken place
    *  in ClassFileparser.sigToType (where it is usually done).
    */
  def rawToExistential = new TypeMap {
    private var expanded = immutable.Set[Symbol]()
    def apply(tp: Type): Type = tp match {
      case TypeRef(pre, sym, List()) if isRawIfWithoutArgs(sym) =>
        if (expanded contains sym) AnyRefTpe
        else try {
          expanded += sym
          val eparams = mapOver(typeParamsToExistentials(sym))
          existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe)))
        } finally {
          expanded -= sym
        }
      case _ =>
        mapOver(tp)
    }
  }
  /***
    *@M: I think this is more desirable, but Martin prefers to leave raw-types as-is as much as possible
    object rawToExistentialInJava extends TypeMap {
      def apply(tp: Type): Type = tp match {
        // any symbol that occurs in a java sig, not just java symbols
        // see http://lampsvn.epfl.ch/trac/scala/ticket/2454#comment:14
        case TypeRef(pre, sym, List()) if !sym.typeParams.isEmpty =>
          val eparams = typeParamsToExistentials(sym, sym.typeParams)
          existentialAbstraction(eparams, TypeRef(pre, sym, eparams map (_.tpe)))
        case _ =>
          mapOver(tp)
      }
    }
    */

  /** Used by existentialAbstraction.
    */
  class ExistentialExtrapolation(tparams: List[Symbol]) extends TypeMap(trackVariance = true) {
    private val occurCount = mutable.HashMap[Symbol, Int]()
    private def countOccs(tp: Type) = {
      tp foreach {
        case TypeRef(_, sym, _) =>
          if (tparams contains sym)
            occurCount(sym) += 1
        case _ => ()
      }
    }
    def extrapolate(tpe: Type): Type = {
      tparams foreach (t => occurCount(t) = 0)
      countOccs(tpe)
      for (tparam <- tparams)
        countOccs(tparam.info)

      apply(tpe)
    }

    /** If these conditions all hold:
      *   1) we are in covariant (or contravariant) position
      *   2) this type occurs exactly once in the existential scope
      *   3) the widened upper (or lower) bound of this type contains no references to tparams
      *  Then we replace this lone occurrence of the type with the widened upper (or lower) bound.
      *  All other types pass through unchanged.
      */
    def apply(tp: Type): Type = {
      val tp1 = mapOver(tp)
      if (variance.isInvariant) tp1
      else tp1 match {
        case TypeRef(pre, sym, args) if tparams contains sym =>
          val repl = if (variance.isPositive) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo
          val count = occurCount(sym)
          val containsTypeParam = tparams exists (repl contains _)
          def msg = {
            val word = if (variance.isPositive) "upper" else "lower"
            s"Widened lone occurrence of $tp1 inside existential to $word bound"
          }
          if (!repl.typeSymbol.isBottomClass && count == 1 && !containsTypeParam)
            debuglogResult(msg)(repl)
          else
            tp1
        case _ =>
          tp1
      }
    }
    override def mapOver(tp: Type): Type = tp match {
      case SingleType(pre, sym) =>
        if (sym.isPackageClass) tp // short path
        else {
          val pre1 = this(pre)
          if ((pre1 eq pre) || !pre1.isStable) tp
          else singleType(pre1, sym)
        }
      case _ => super.mapOver(tp)
    }

    // Do not discard the types of existential ident's. The
    // symbol of the Ident itself cannot be listed in the
    // existential's parameters, so the resulting existential
    // type would be ill-formed.
    override def mapOver(tree: Tree) = tree match {
      case Ident(_) if tree.tpe.isStable => tree
      case _                             => super.mapOver(tree)
    }
  }

  /** Might the given symbol be important when calculating the prefix
    *  of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`,
    *  the result will be `tp` unchanged if `pre` is trivial and `clazz`
    *  is a symbol such that isPossiblePrefix(clazz) == false.
    */
  def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass

  protected[internal] def skipPrefixOf(pre: Type, clazz: Symbol) = (
    (pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz)
    )

  def newAsSeenFromMap(pre: Type, clazz: Symbol): AsSeenFromMap =
    new AsSeenFromMap(pre, clazz)

  /** A map to compute the asSeenFrom method.
    */
  class AsSeenFromMap(seenFromPrefix: Type, seenFromClass: Symbol) extends TypeMap with KeepOnlyTypeConstraints {
    // Some example source constructs relevant in asSeenFrom:
    //
    // object CaptureThis {
    //   trait X[A] { def f: this.type = this }
    //   class Y[A] { def f: this.type = this }
    //   // Created new existential to represent This(CaptureThis.X) seen from CaptureThis.X[B]: type _1.type <: CaptureThis.X[B] with Singleton
    //   def f1[B] = new X[B] { }
    //   // TODO - why is the behavior different when it's a class?
    //   def f2[B] = new Y[B] { }
    // }
    // class CaptureVal[T] {
    //   val f: java.util.List[_ <: T] = null
    //   // Captured existential skolem for type _$1 seen from CaptureVal.this.f.type: type _$1
    //   def g = f get 0
    // }
    // class ClassParam[T] {
    //   // AsSeenFromMap(Inner.this.type, class Inner)/classParameterAsSeen(T)#loop(ClassParam.this.type, class ClassParam)
    //   class Inner(lhs: T) { def f = lhs }
    // }
    def capturedParams: List[Symbol]  = _capturedParams
    def capturedSkolems: List[Symbol] = _capturedSkolems

    def apply(tp: Type): Type = tp match {
      case tp @ ThisType(_)                                            => thisTypeAsSeen(tp)
      case tp @ SingleType(_, sym)                                     => if (sym.isPackageClass) tp else singleTypeAsSeen(tp)
      case tp @ TypeRef(_, sym, _) if isTypeParamOfEnclosingClass(sym) => classParameterAsSeen(tp)
      case _                                                           => mapOver(tp)
    }

    private var _capturedSkolems: List[Symbol] = Nil
    private var _capturedParams: List[Symbol]  = Nil
    private val isStablePrefix = seenFromPrefix.isStable

    // isBaseClassOfEnclosingClassOrInfoIsNotYetComplete would be a more accurate
    // but less succinct name.
    private def isBaseClassOfEnclosingClass(base: Symbol) = {
      def loop(encl: Symbol): Boolean = (
        isPossiblePrefix(encl)
          && ((encl isSubClass base) || loop(encl.owner.enclClass))
        )
      // The hasCompleteInfo guard is necessary to avoid cycles during the typing
      // of certain classes, notably ones defined inside package objects.
      !base.hasCompleteInfo || loop(seenFromClass)
    }

    /** Is the symbol a class type parameter from one of the enclosing
      *  classes, or a base class of one of them?
      */
    private def isTypeParamOfEnclosingClass(sym: Symbol): Boolean = (
      sym.isTypeParameter
        && sym.owner.isClass
        && isBaseClassOfEnclosingClass(sym.owner)
      )

    /** Creates an existential representing a type parameter which appears
      *  in the prefix of a ThisType.
      */
    protected def captureThis(pre: Type, clazz: Symbol): Type = {
      capturedParams find (_.owner == clazz) match {
        case Some(p) => p.tpe
        case _       =>
          val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
          _capturedParams ::= qvar
          debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}")
          qvar.tpe
      }
    }
    protected def captureSkolems(skolems: List[Symbol]) {
      for (p <- skolems; if !(capturedSkolems contains p)) {
        debuglog(s"Captured $p seen from $seenFromPrefix")
        _capturedSkolems ::= p
      }
    }

    /** Find the type argument in an applied type which corresponds to a type parameter.
      *  The arguments are required to be related as follows, through intermediary `clazz`.
      *  An exception will be thrown if this is violated.
      *
      *  @param   lhs    its symbol is a type parameter of `clazz`
      *  @param   rhs    a type application constructed from `clazz`
      */
    private def correspondingTypeArgument(lhs: Type, rhs: Type): Type = {
      val TypeRef(_, lhsSym, lhsArgs) = lhs
      val TypeRef(_, rhsSym, rhsArgs) = rhs
      require(lhsSym.owner == rhsSym, s"$lhsSym is not a type parameter of $rhsSym")

      // Find the type parameter position; we'll use the corresponding argument.
      // Why are we checking by name rather than by equality? Because for
      // reasons which aren't yet fully clear, we can arrive here holding a type
      // parameter whose owner is rhsSym, and which shares the name of an actual
      // type parameter of rhsSym, but which is not among the type parameters of
      // rhsSym. One can see examples of it at SI-4365.
      val argIndex = rhsSym.typeParams indexWhere (lhsSym.name == _.name)
      // don't be too zealous with the exceptions, see #2641
      if (argIndex < 0 && rhs.parents.exists(typeIsErroneous))
        ErrorType
      else {
        // It's easy to get here when working on hardcore type machinery (not to
        // mention when not doing so, see above) so let's provide a standout error.
        def own_s(s: Symbol) = s.nameString + " in " + s.owner.nameString
        def explain =
          sm"""|   sought  ${own_s(lhsSym)}
               | classSym  ${own_s(rhsSym)}
               |  tparams  ${rhsSym.typeParams map own_s mkString ", "}
               |"""

        if (argIndex < 0)
          abort(s"Something is wrong: cannot find $lhs in applied type $rhs\n" + explain)
        else {
          val targ   = rhsArgs(argIndex)
          // @M! don't just replace the whole thing, might be followed by type application
          val result = appliedType(targ, lhsArgs mapConserve this)
          def msg = s"Created $result, though could not find ${own_s(lhsSym)} among tparams of ${own_s(rhsSym)}"
          if (!rhsSym.typeParams.contains(lhsSym))
            devWarning(s"Inconsistent tparam/owner views: had to fall back on names\n$msg\n$explain")

          result
        }
      }
    }

    // 0) @pre: `classParam` is a class type parameter
    // 1) Walk the owner chain of `seenFromClass` until we find the class which owns `classParam`
    // 2) Take the base type of the prefix at that point with respect to the owning class
    // 3) Solve for the type parameters through correspondence with the type args of the base type
    //
    // Only class type parameters (and not skolems) are considered, because other type parameters
    // are not influenced by the prefix through which they are seen. Note that type params of
    // anonymous type functions, which currently can only arise from normalising type aliases, are
    // owned by the type alias of which they are the eta-expansion.
    private def classParameterAsSeen(classParam: Type): Type = {
      val TypeRef(_, tparam, _) = classParam

      def loop(pre: Type, clazz: Symbol): Type = {
        // have to deconst because it may be a Class[T]
        def nextBase = (pre baseType clazz).deconst
        //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
        if (skipPrefixOf(pre, clazz))
          mapOver(classParam)
        else if (!matchesPrefixAndClass(pre, clazz)(tparam.owner))
          loop(nextBase.prefix, clazz.owner)
        else nextBase match {
          case NoType                         => loop(NoType, clazz.owner) // backstop for SI-2797, must remove `SingletonType#isHigherKinded` and run pos/t2797.scala to get here.
          case applied @ TypeRef(_, _, _)     => correspondingTypeArgument(classParam, applied)
          case ExistentialType(eparams, qtpe) => captureSkolems(eparams) ; loop(qtpe, clazz)
          case t                              => abort(s"$tparam in ${tparam.owner} cannot be instantiated from ${seenFromPrefix.widen}")
        }
      }
      loop(seenFromPrefix, seenFromClass)
    }

    // Does the candidate symbol match the given prefix and class?
    // Since pre may be something like ThisType(A) where trait A { self: B => },
    // we have to test the typeSymbol of the widened type, not pre.typeSymbol, or
    // B will not be considered.
    private def matchesPrefixAndClass(pre: Type, clazz: Symbol)(candidate: Symbol) =
      (clazz == candidate) && (pre.widen.typeSymbol isSubClass clazz)

    // Whether the annotation tree currently being mapped over has had a This(_) node rewritten.
    private[this] var wroteAnnotation = false
    private object annotationArgRewriter extends TypeMapTransformer {
      private def matchesThis(thiz: Symbol) = matchesPrefixAndClass(seenFromPrefix, seenFromClass)(thiz)

      // what symbol should really be used?
      private def newThis(): Tree = {
        wroteAnnotation = true
        val presym      = seenFromPrefix.widen.typeSymbol
        val thisSym     = presym.owner.newValue(presym.name.toTermName, presym.pos) setInfo seenFromPrefix
        gen.mkAttributedQualifier(seenFromPrefix, thisSym)
      }

      /** Rewrite `This` trees in annotation argument trees */
      override def transform(tree: Tree): Tree = super.transform(tree) match {
        case This(_) if matchesThis(tree.symbol) => newThis()
        case tree                                => tree
      }
    }

    // This becomes considerably cheaper if we optimize for the common cases:
    // where the prefix is stable and where no This nodes are rewritten. If
    // either is true, then we don't need to worry about calling giveup. So if
    // the prefix is unstable, use a stack variable to indicate whether the tree
    // was touched. This takes us to one allocation per AsSeenFromMap rather
    // than an allocation on every call to mapOver, and no extra work when the
    // tree only has its types remapped.
    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
      if (isStablePrefix)
        annotationArgRewriter transform tree
      else {
        val saved = wroteAnnotation
        wroteAnnotation = false
        try annotationArgRewriter transform tree
        finally if (wroteAnnotation) giveup() else wroteAnnotation = saved
      }
    }

    private def thisTypeAsSeen(tp: ThisType): Type = {
      def loop(pre: Type, clazz: Symbol): Type = {
        val pre1 = pre match {
          case SuperType(thistpe, _) => thistpe
          case _                     => pre
        }
        if (skipPrefixOf(pre, clazz))
          mapOver(tp) // TODO - is mapOver necessary here?
        else if (!matchesPrefixAndClass(pre, clazz)(tp.sym))
          loop((pre baseType clazz).prefix, clazz.owner)
        else if (pre1.isStable)
          pre1
        else
          captureThis(pre1, clazz)
      }
      loop(seenFromPrefix, seenFromClass)
    }

    private def singleTypeAsSeen(tp: SingleType): Type = {
      val SingleType(pre, sym) = tp

      val pre1 = this(pre)
      if (pre1 eq pre) tp
      else if (pre1.isStable) singleType(pre1, sym)
      else pre1.memberType(sym).resultType //todo: this should be rolled into existential abstraction
    }

    override def toString = s"AsSeenFromMap($seenFromPrefix, $seenFromClass)"
  }

  /** A base class to compute all substitutions */
  abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap {
    // OPT this check was 2-3% of some profiles, demoted to -Xdev
    if (isDeveloper) assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to)

    /** Are `sym` and `sym1` the same? Can be tuned by subclasses. */
    protected def matches(sym: Symbol, sym1: Symbol): Boolean = sym eq sym1

    /** Map target to type, can be tuned by subclasses */
    protected def toType(fromtp: Type, tp: T): Type

    protected def renameBoundSyms(tp: Type): Type = tp match {
      case MethodType(ps, restp) =>
        createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1)))
      case PolyType(bs, restp) =>
        createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1)))
      case ExistentialType(bs, restp) =>
        createFromClonedSymbols(bs, restp)(newExistentialType)
      case _ =>
        tp
    }

    @tailrec private def subst(tp: Type, sym: Symbol, from: List[Symbol], to: List[T]): Type = (
      if (from.isEmpty) tp
      // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(tp, from))
      else if (matches(from.head, sym)) toType(tp, to.head)
      else subst(tp, sym, from.tail, to.tail)
      )

    def apply(tp0: Type): Type = if (from.isEmpty) tp0 else {
      val boundSyms             = tp0.boundSyms
      val tp1                   = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0
      val tp                    = mapOver(tp1)
      def substFor(sym: Symbol) = subst(tp, sym, from, to)

      tp match {
        // @M
        // 1) arguments must also be substituted (even when the "head" of the
        // applied type has already been substituted)
        // example: (subst RBound[RT] from [type RT,type RBound] to
        // [type RT&,type RBound&]) = RBound&[RT&]
        // 2) avoid loops (which occur because alpha-conversion is
        // not performed properly imo)
        // e.g. if in class Iterable[a] there is a new Iterable[(a,b)],
        // we must replace the a in Iterable[a] by (a,b)
        // (must not recurse --> loops)
        // 3) replacing m by List in m[Int] should yield List[Int], not just List
        case TypeRef(NoPrefix, sym, args) =>
          val tcon = substFor(sym)
          if ((tp eq tcon) || args.isEmpty) tcon
          else appliedType(tcon.typeConstructor, args)
        case SingleType(NoPrefix, sym) =>
          substFor(sym)
        case ClassInfoType(parents, decls, sym) =>
          val parents1 = parents mapConserve this
          // We don't touch decls here; they will be touched when an enclosing TreeSubstitutor
          // transforms the tree that defines them.
          if (parents1 eq parents) tp
          else ClassInfoType(parents1, decls, sym)
        case _ =>
          tp
      }
    }
  }

  /** A map to implement the `substSym` method. */
  class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) {
    def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2))

    protected def toType(fromtp: Type, sym: Symbol) = fromtp match {
      case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args)
      case SingleType(pre, _) => singleType(pre, sym)
    }
    @tailrec private def subst(sym: Symbol, from: List[Symbol], to: List[Symbol]): Symbol = (
      if (from.isEmpty) sym
      // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(sym, from))
      else if (matches(from.head, sym)) to.head
      else subst(sym, from.tail, to.tail)
      )
    private def substFor(sym: Symbol) = subst(sym, from, to)

    override def apply(tp: Type): Type = (
      if (from.isEmpty) tp
      else tp match {
        case TypeRef(pre, sym, args) if pre ne NoPrefix =>
          val newSym = substFor(sym)
          // mapOver takes care of subst'ing in args
          mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) )
        // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams))
        case SingleType(pre, sym) if pre ne NoPrefix =>
          val newSym = substFor(sym)
          mapOver( if (sym eq newSym) tp else singleType(pre, newSym) )
        case _ =>
          super.apply(tp)
      }
      )

    object mapTreeSymbols extends TypeMapTransformer {
      val strictCopy = newStrictTreeCopier

      def termMapsTo(sym: Symbol) = from indexOf sym match {
        case -1   => None
        case idx  => Some(to(idx))
      }

      // if tree.symbol is mapped to another symbol, passes the new symbol into the
      // constructor `trans` and sets the symbol and the type on the resulting tree.
      def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match {
        case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe
        case None => tree
      }

      // changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified.
      override def transform(tree: Tree) = {
        // super.transform maps symbol references in the types of `tree`. it also copies trees where necessary.
        super.transform(tree) match {
          case id @ Ident(_) =>
            transformIfMapped(id)(toSym =>
              strictCopy.Ident(id, toSym.name))

          case sel @ Select(qual, name) =>
            transformIfMapped(sel)(toSym =>
              strictCopy.Select(sel, qual, toSym.name))

          case tree => tree
        }
      }
    }
    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
      mapTreeSymbols.transform(tree)
    }
  }

  /** A map to implement the `subst` method. */
  class SubstTypeMap(val from: List[Symbol], val to: List[Type]) extends SubstMap(from, to) {
    protected def toType(fromtp: Type, tp: Type) = tp

    override def mapOver(tree: Tree, giveup: () => Nothing): Tree = {
      object trans extends TypeMapTransformer {
        override def transform(tree: Tree) = tree match {
          case Ident(name) =>
            from indexOf tree.symbol match {
              case -1   => super.transform(tree)
              case idx  =>
                val totpe = to(idx)
                if (totpe.isStable) tree.duplicate setType totpe
                else giveup()
            }
          case _ =>
            super.transform(tree)
        }
      }
      trans.transform(tree)
    }
  }

  /** A map to implement the `substThis` method. */
  class SubstThisMap(from: Symbol, to: Type) extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case ThisType(sym) if (sym == from) => to
      case _ => mapOver(tp)
    }
  }

  class SubstWildcardMap(from: List[Symbol]) extends TypeMap {
    def apply(tp: Type): Type = try {
      tp match {
        case TypeRef(_, sym, _) if from contains sym =>
          BoundedWildcardType(sym.info.bounds)
        case _ =>
          mapOver(tp)
      }
    } catch {
      case ex: MalformedType =>
        WildcardType
    }
  }

  // dependent method types
  object IsDependentCollector extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (tp.isImmediatelyDependent) result = true
      else if (!result) mapOver(tp.dealias)
    }
  }

  object ApproximateDependentMap extends TypeMap {
    def apply(tp: Type): Type =
      if (tp.isImmediatelyDependent) WildcardType
      else mapOver(tp)
  }

  /** Note: This map is needed even for non-dependent method types, despite what the name might imply.
    */
  class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints {
    private val actuals      = actuals0.toIndexedSeq
    private val existentials = new Array[Symbol](actuals.size)
    def existentialsNeeded: List[Symbol] = existentials.iterator.filter(_ ne null).toList

    private object StableArgTp {
      // type of actual arg corresponding to param -- if the type is stable
      def unapply(param: Symbol): Option[Type] = (params indexOf param) match {
        case -1  => None
        case pid =>
          val tp = actuals(pid)
          if (tp.isStable && (tp.typeSymbol != NothingClass)) Some(tp)
          else None
      }
    }

    /** Return the type symbol for referencing a parameter that's instantiated to an unstable actual argument.
     *
     * To soundly abstract over an unstable value (x: T) while retaining the most type information,
     * use `x.type forSome { type x.type <: T with Singleton}`
     * `typeOf[T].narrowExistentially(symbolOf[x])`.
     *
     * See also: captureThis in AsSeenFromMap.
     */
    private def existentialFor(pid: Int) = {
      if (existentials(pid) eq null) {
        val param = params(pid)
        existentials(pid) = (
          param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags)
            setInfo singletonBounds(actuals(pid))
          )
      }
      existentials(pid)
    }

    private object UnstableArgTp {
      // existential quantifier and type of corresponding actual arg with unstable type
      def unapply(param: Symbol): Option[(Symbol, Type)] = (params indexOf param) match {
        case -1  => None
        case pid =>
          val sym = existentialFor(pid)
          Some((sym, sym.tpe_*)) // refers to an actual value, must be kind-*
      }
    }

    private object StabilizedArgTp {
      def unapply(param: Symbol): Option[Type] =
        param match {
          case StableArgTp(tp)      => Some(tp)  // (1)
          case UnstableArgTp(_, tp) => Some(tp)  // (2)
          case _ => None
        }
    }

    /** instantiate `param.type` to the (sound approximation of the) type `T`
     * of the actual argument `arg` that was passed in for `param`
     *
     * (1) If `T` is stable, we can just use that.
     *
     * (2) SI-3873: it'd be unsound to instantiate `param.type` to an unstable `T`,
     * so we approximate to `X forSome {type X <: T with Singleton}` -- we can't soundly say more.
     */
    def apply(tp: Type): Type = tp match {
      case SingleType(NoPrefix, StabilizedArgTp(tp)) => tp
      case _                                         => mapOver(tp)
    }

    //AM propagate more info to annotations -- this seems a bit ad-hoc... (based on code by spoon)
    override def mapOver(arg: Tree, giveup: ()=>Nothing): Tree = {
      // TODO: this should be simplified; in the stable case, one can
      // probably just use an Ident to the tree.symbol.
      //
      // @PP: That leads to failure here, where stuff no longer has type
      // 'String @Annot("stuff")' but 'String @Annot(x)'.
      //
      //   def m(x: String): String @Annot(x) = x
      //   val stuff = m("stuff")
      //
      // (TODO cont.) Why an existential in the non-stable case?
      //
      // @PP: In the following:
      //
      //   def m = { val x = "three" ; val y: String @Annot(x) = x; y }
      //
      // m is typed as 'String @Annot(x) forSome { val x: String }'.
      //
      // Both examples are from run/constrained-types.scala.
      object treeTrans extends Transformer {
        override def transform(tree: Tree): Tree = tree.symbol match {
          case StableArgTp(tp)          => gen.mkAttributedQualifier(tp, tree.symbol)
          case UnstableArgTp(quant, tp) => Ident(quant) copyAttrs tree setType tp
          case _                        => super.transform(tree)
        }
      }
      treeTrans transform arg
    }
  }

  /** A map to convert every occurrence of a wildcard type to a fresh
    *  type variable */
  object wildcardToTypeVarMap extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case WildcardType =>
        TypeVar(tp, new TypeConstraint)
      case BoundedWildcardType(bounds) =>
        TypeVar(tp, new TypeConstraint(bounds))
      case _ =>
        mapOver(tp)
    }
  }

  /** A map to convert each occurrence of a type variable to its origin. */
  object typeVarToOriginMap extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case TypeVar(origin, _) => origin
      case _ => mapOver(tp)
    }
  }

  /** A map to implement the `contains` method. */
  class ContainsCollector(sym: Symbol) extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (!result) {
        tp.normalize match {
          case TypeRef(_, sym1, _) if (sym == sym1) => result = true
          case SingleType(_, sym1) if (sym == sym1) => result = true
          case _ => mapOver(tp)
        }
      }
    }

    override def mapOver(arg: Tree) = {
      for (t <- arg) {
        traverse(t.tpe)
        if (t.symbol == sym)
          result = true
      }
      arg
    }
  }

  /** A map to implement the `filter` method. */
  class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) {
    override def collect(tp: Type) = super.collect(tp).reverse

    def traverse(tp: Type) {
      if (p(tp)) result ::= tp
      mapOver(tp)
    }
  }

  /** A map to implement the `collect` method. */
  class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) {
    override def collect(tp: Type) = super.collect(tp).reverse

    def traverse(tp: Type) {
      if (pf.isDefinedAt(tp)) result ::= pf(tp)
      mapOver(tp)
    }
  }

  class ForEachTypeTraverser(f: Type => Unit) extends TypeTraverser {
    def traverse(tp: Type) {
      f(tp)
      mapOver(tp)
    }
  }

  /** A map to implement the `filter` method. */
  class FindTypeCollector(p: Type => Boolean) extends TypeCollector[Option[Type]](None) {
    def traverse(tp: Type) {
      if (result.isEmpty) {
        if (p(tp)) result = Some(tp)
        mapOver(tp)
      }
    }
  }

  /** A map to implement the `contains` method. */
  object ErroneousCollector extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (!result) {
        result = tp.isError
        mapOver(tp)
      }
    }
  }

  object adaptToNewRunMap extends TypeMap {

    private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = {
      if (phase.flatClasses || sym.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass)
        sym
      else if (sym.isModuleClass) {
        val sourceModule1 = adaptToNewRun(pre, sym.sourceModule)

        sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse {
          val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s"
          debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass))
          sym
        }
      }
      else {
        var rebind0 = pre.findMember(sym.name, BRIDGE, 0, stableOnly = true) orElse {
          if (sym.isAliasType) throw missingAliasException
          devWarning(s"$pre.$sym no longer exist at phase $phase")
          throw new MissingTypeControl // For build manager and presentation compiler purposes
        }
        /* The two symbols have the same fully qualified name */
        def corresponds(sym1: Symbol, sym2: Symbol): Boolean =
          sym1.name == sym2.name && (sym1.isPackageClass || corresponds(sym1.owner, sym2.owner))
        if (!corresponds(sym.owner, rebind0.owner)) {
          debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString)
          val bcs = pre.baseClasses.dropWhile(bc => !corresponds(bc, sym.owner))
          if (bcs.isEmpty)
            assert(pre.typeSymbol.isRefinementClass, pre) // if pre is a refinementclass it might be a structural type => OK to leave it in.
          else
            rebind0 = pre.baseType(bcs.head).member(sym.name)
          debuglog(
            "ADAPT2 pre = " + pre +
              ", bcs.head = " + bcs.head +
              ", sym = " + sym.fullLocationString +
              ", rebind = " + rebind0.fullLocationString
          )
        }
        rebind0.suchThat(sym => sym.isType || sym.isStable) orElse {
          debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType)
          throw new MalformedType(pre, sym.nameString)
        }
      }
    }
    def apply(tp: Type): Type = tp match {
      case ThisType(sym) =>
        try {
          val sym1 = adaptToNewRun(sym.owner.thisType, sym)
          if (sym1 == sym) tp else ThisType(sym1)
        } catch {
          case ex: MissingTypeControl =>
            tp
        }
      case SingleType(pre, sym) =>
        if (sym.hasPackageFlag) tp
        else {
          val pre1 = this(pre)
          try {
            val sym1 = adaptToNewRun(pre1, sym)
            if ((pre1 eq pre) && (sym1 eq sym)) tp
            else singleType(pre1, sym1)
          } catch {
            case _: MissingTypeControl =>
              tp
          }
        }
      case TypeRef(pre, sym, args) =>
        if (sym.isPackageClass) tp
        else {
          val pre1 = this(pre)
          val args1 = args mapConserve (this)
          try {
            val sym1 = adaptToNewRun(pre1, sym)
            if ((pre1 eq pre) && (sym1 eq sym) && (args1 eq args)/* && sym.isExternal*/) {
              tp
            } else if (sym1 == NoSymbol) {
              devWarning(s"adapt to new run failed: pre=$pre pre1=$pre1 sym=$sym")
              tp
            } else {
              copyTypeRef(tp, pre1, sym1, args1)
            }
          } catch {
            case ex: MissingAliasControl =>
              apply(tp.dealias)
            case _: MissingTypeControl =>
              tp
          }
        }
      case MethodType(params, restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else copyMethodType(tp, params, restp1)
      case NullaryMethodType(restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else NullaryMethodType(restp1)
      case PolyType(tparams, restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else PolyType(tparams, restp1)

      // Lukas: we need to check (together) whether we should also include parameter types
      // of PolyType and MethodType in adaptToNewRun

      case ClassInfoType(parents, decls, clazz) =>
        if (clazz.isPackageClass) tp
        else {
          val parents1 = parents mapConserve (this)
          if (parents1 eq parents) tp
          else ClassInfoType(parents1, decls, clazz)
        }
      case RefinedType(parents, decls) =>
        val parents1 = parents mapConserve (this)
        if (parents1 eq parents) tp
        else refinedType(parents1, tp.typeSymbol.owner, decls, tp.typeSymbol.owner.pos)
      case SuperType(_, _) => mapOver(tp)
      case TypeBounds(_, _) => mapOver(tp)
      case TypeVar(_, _) => mapOver(tp)
      case AnnotatedType(_, _) => mapOver(tp)
      case ExistentialType(_, _) => mapOver(tp)
      case _ => tp
    }
  }

}

Other Scala source code examples

Here is a short list of links related to this Scala TypeMaps.scala source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2024 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.