package dotty.tools.dotc package core import util.HashSet import Symbols._ import TypeComparers._ import Flags._ import Names._ import Scopes._ import Constants._ import Contexts._ import Annotations._ import SymDenotations._ import Denotations._ import Periods._ import TypedTrees.tpd._, TypedTrees.TreeMapper import transform.Erasure import scala.util.hashing.{ MurmurHash3 => hashing } import collection.mutable object Types { /** A hash value indicating that the underlying type is not * cached in uniques. */ final val NotCached = 0 /** An alternative value returned from `hash` if the * computed hashCode would be `NotCached`. */ private final val NotCachedAlt = Int.MinValue /** The class of types. * The principal subclasses and sub-objects are as follows: * * Type -+- ProxyType --+- NamedType ----+--- TypeRef * | | \ * | +- SingletonType-+-+- TermRef * | | | * | | +--- ThisType * | | +--- SuperType * | | +--- ConstantType * | | +--- MethodParam * | | +--- RefinedThis * | | +--- NoPrefix * | +- PolyParam * | +- RefinedType * | +- TypeBounds * | +- ExprType * | +- AnnotatedType * | * +- GroundType -+- AndType * +- OrType * +- MethodType -----+- ImplicitMethodType * | +- JavaMethodType * +- PolyType * +- ClassInfo * | * +- NoType * +- ErrorType * +- WildcardType */ abstract class Type extends DotClass { /** The type symbol associated with the type */ final def typeSymbol(implicit ctx: Context): Symbol = this match { case tp: TypeRef => tp.symbol case tp: ClassInfo => tp.cls case tp: TypeProxy => tp.underlying.typeSymbol case _ => NoSymbol } /** The term symbol associated with the type */ final def termSymbol(implicit ctx: Context): Symbol = this match { case tp: TermRef => tp.symbol case tp: TypeProxy => tp.underlying.termSymbol case _ => NoSymbol } /** Does this type denote a stable reference (i.e. singleton type)? */ 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. */ final def isLegalPrefix(implicit ctx: Context): Boolean = isStable || memberNames(abstractTypeNameFilter).isEmpty /** 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`. */ final def memberNames(keepOnly: NameFilter, pre: Type = this)(implicit ctx: Context): Set[Name] = this match { case tp: ClassInfo => tp.cls.memberNames(keepOnly) filter (keepOnly(pre, _)) case tp: RefinedType => val ns = tp.parent.memberNames(keepOnly, pre) if (keepOnly(pre, tp.refinedName)) ns + tp.refinedName else ns case tp: AndType => tp.tp1.memberNames(keepOnly, pre) | tp.tp2.memberNames(keepOnly, pre) case tp: OrType => tp.tp1.memberNames(keepOnly, pre) & tp.tp2.memberNames(keepOnly, pre) case tp: TypeProxy => tp.underlying.memberNames(keepOnly, pre) case _ => Set() } /** The set of names that denote an abstract member of this type * which is also an abstract member of `pre`. */ final def abstractMemberNames(pre: Type = this)(implicit ctx: Context): Set[Name] = memberNames(abstractTypeNameFilter, pre) | memberNames(abstractTermNameFilter, pre) /** The set of abstract term members of this type. */ final def abstractTermMembers(implicit ctx: Context): Set[SingleDenotation] = memberNames(abstractTermNameFilter) .flatMap(member(_).altsWith(_ is Deferred)) /** The set of abstract type members of this type. */ final def abstractTypeMembers(implicit ctx: Context): Set[SingleDenotation] = memberNames(abstractTypeNameFilter) .map(member(_).asInstanceOf[SingleDenotation]) /** The set of abstract members of this type. */ final def abstractMembers(implicit ctx: Context): Set[SingleDenotation] = abstractTermMembers | abstractTypeMembers /** Is this type a value type? */ final def isValueType: Boolean = this.isInstanceOf[ValueType] /** Is this type a TypeBounds instance, with lower and upper bounds * that are not identical? */ 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) } /** The disjunctive normal form of this type. * This collects a set of alternatives, each alternative consisting * of a set of typerefs and a set of refinement names. Collected are * all type refs reachable by following aliases and type proxies, and * collecting the elements of conjunctions (&) and disjunctions (|). * The set of refinement names in each alternative * are the set of names in refinement types encountered during the collection. */ final def DNF(implicit ctx: Context): Set[(Set[TypeRef], Set[Name])] = this match { case tp: TypeRef => if (tp.info.isAliasTypeBounds) tp.info.bounds.hi.DNF else Set((Set(tp), Set())) case RefinedType(parent, name) => for ((ps, rs) <- parent.DNF) yield (ps, rs + name) case tp: TypeProxy => tp.underlying.DNF case AndType(l, r) => for ((lps, lrs) <- l.DNF; (rps, rrs) <- r.DNF) yield (lps | rps, lrs | rrs) case OrType(l, r) => l.DNF | r.DNF case tp => Set((Set(), Set())) } /** A type is volatile if its DNF contains an alternative of the form * {P1, ..., Pn}, {N1, ..., Nk}, where the Pi are parent typerefs and the * Nj are refinement names, and one the 4 following conditions is met: * * 1. At least two of the parents Pi are abstract types. * 2. One of the parents Pi is an abstract type, and one other type Pj, * j != i has an abstract member which has the same name as an * abstract member of the whole type. * 3. One of the parents Pi is an abstract type, and one of the refinement * names Nj refers to an abstract member of the whole type. * 4. One of the parents Pi is an abstract type with a volatile upper bound. * * Lazy values are not allowed to have volatile type, as otherwise * unsoundness can result. */ final def isVolatile(implicit ctx: Context): Boolean = ctx.isVolatile(this) /** Is this type guaranteed not to have `null` as a value? * For the moment this is only true for modules, but it could * be refined later. */ final def isNotNull(implicit ctx: Context): Boolean = widen.typeSymbol.isModuleClass /** Is this type produced as a repair for an 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? */ final def isErroneous(implicit ctx: Context): Boolean = exists(_.isError) /** Returns true if there is a part of this type that satisfies predicate `p`. */ final def exists(p: Type => Boolean): Boolean = new ExistsAccumulator(p)(false, this) /** Returns true if all parts of this type that satisfy predicate `p`. */ final def forall(p: Type => Boolean): Boolean = !exists(!p(_)) /** Substitute all types that refer in their symbol attribute to * one of the symbols in `from` by the corresponding types in `to`. */ 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) ctx.subst1(this, from.head, to.head, null) else { val from2 = from1.tail 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)`. */ final def subst(from: BindingType, to: BindingType)(implicit ctx: Context): Type = ctx.subst(this, from, to, null) /** Substitute all occurrences of `This(cls)` by `tp` */ final def substThis(cls: ClassSymbol, tp: Type)(implicit ctx: Context): Type = ctx.substThis(this, cls, 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) /** Substitute all occurrences of symbols in `from` by references to corresponding symbols in `to` */ final def substSym(from: List[Symbol], to: List[Symbol])(implicit ctx: Context): Type = ctx.substSym(this, from, to, null) /** For a ClassInfo type, its parents, * Inherited by all type proxies. Empty for all other types. * Overwritten in ClassInfo, where parents is cached. */ def parents(implicit ctx: Context): List[TypeRef] = this match { case tp: TypeProxy => tp.underlying.parents case _ => List() } /** If this is an alias type, its alias, otherwise the type itself */ final def dealias(implicit ctx: Context): Type = this match { case tp: TypeRef => tp.info match { case TypeBounds(lo, hi) if lo eq hi => hi.dealias case _ => this } case _ => this } /** The parameter types of a PolyType or MethodType, Empty list for others */ final def paramTypess: List[List[Type]] = this match { case mt: MethodType => mt.paramTypes :: mt.resultType.paramTypess case pt: PolyType => pt.paramTypess case _ => Nil } /** The resultType of a PolyType, MethodType, or ExprType, the type itself for others */ def resultType: Type = this /** Map function over elements of an AndType, rebuilding with & */ def mapAnd(f: Type => Type)(implicit ctx: Context): Type = this match { case AndType(tp1, tp2) => tp1.mapAnd(f) & tp2.mapAnd(f) case _ => f(this) } /** Map function over elements of an OrType, rebuilding with | */ final def mapOr(f: Type => Type)(implicit ctx: Context): Type = this match { case OrType(tp1, tp2) => tp1.mapOr(f) | tp2.mapOr(f) case _ => f(this) } /** The normalized prefix of this type is: * For an alias type, the normalized prefix of its alias * For all other named type and class infos: the prefix. * Inherited by all other type proxies. * `NoType` for all other types. */ final def normalizedPrefix(implicit ctx: Context): Type = this match { case tp: NamedType => if (tp.info.isAliasTypeBounds) 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. */ final def decls(implicit ctx: Context): Scope = this match { case tp: ClassInfo => tp.decls case tp: TypeProxy => tp.underlying.decls case _ => EmptyScope } /** A denotation containing the declaration(s) in this type with the given name */ final def decl(name: Name)(implicit ctx: Context): Denotation = findDecl(name, this, EmptyFlags) /** A denotation containing the non-private declaration(s) in this type with the given name */ final def nonPrivateDecl(name: Name)(implicit ctx: Context): Denotation = findDecl(name, this, Flags.Private) /** A denotation containing the declaration(s) in this type with the given * name, as seen from prefix type `pre`. Declarations that have a flag * in `excluded` are omitted. */ final def findDecl(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = this match { case tp: ClassInfo => tp.decls.denotsNamed(name).filterAsSeenFrom(pre, excluded).toDenot case tp: TypeProxy => tp.underlying.findDecl(name, pre, excluded) } /** The member of this type with the given name */ final def member(name: Name)(implicit ctx: Context): Denotation = findMember(name, this, EmptyFlags) /** The non-private member of this type with the given name. */ 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 denotation that contains the type of the member * as seen from given prefix `pre`. Exclude all members that have * flags in `excluded` from consideration. */ final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = this match { case tp: RefinedType => val pdenot = tp.parent.findMember(name, pre, excluded) if (name eq tp.refinedName) pdenot & new JointRefDenotation(NoSymbol, tp.refinedInfo.substThis(tp, pre), Period.allInRun(ctx.runId)) else pdenot case tp: TypeProxy => tp.underlying.findMember(name, pre, excluded) case tp: ClassInfo => val candidates = tp.cls.membersNamed(name) candidates.filterAsSeenFrom(pre, excluded).toDenot 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? */ 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`. */ 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 `denot`, seen as a member of this type. */ // final def memberInfo(denot: SymDenotation)(implicit ctx: Context): Type = { // denot.info.asSeenFrom(this, denot.owner) // } /** The info of `sym`, seen as a member of this type. */ final def memberInfo(sym: Symbol)(implicit ctx: Context): Type = { sym.info.asSeenFrom(this, sym.owner) } /** Widen from singleton type to its underlying non-singleton * base type by applying one or more `underlying` dereferences, * Also go from => T to T. * Identity for all other types. Example: * * class Outer { class C ; val x: C } * def o: Outer * .widen = o.C */ final def widen(implicit ctx: Context): Type = this match { case tp: SingletonType => tp.underlying.widen case tp: ExprType => tp.underlying.widen case _ => this } /** Widen from constant type to its underlying non-constant * base type. */ final def deconst(implicit ctx: Context): Type = this match { case tp: ConstantType => tp.value.tpe case _ => this } /** The base classes of this type as determined by ClassDenotation * in linearization order, with the class itself as first element. * Inherited by all type proxies. `Nil` for all other types. */ final def baseClasses(implicit ctx: Context): List[ClassSymbol] = this match { case tp: TypeProxy => tp.underlying.baseClasses case tp: ClassInfo => tp.cls.baseClasses case _ => Nil } final def asSeenFrom(pre: Type, cls: Symbol)(implicit ctx: Context): Type = if ((cls is PackageClass) || ctx.erasedTypes && cls != defn.ArrayClass || (pre eq cls.thisType)) this else ctx.asSeenFrom(this, pre, cls, null) /** The signature of this type. This is by default NotAMethod, * 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(implicit ctx: Context): Signature = NotAMethod 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. * Inherited by type proxies. * Empty list for all other types. */ final def typeParams(implicit ctx: Context): List[TypeSymbol] = this match { case tp: ClassInfo => tp.cls.typeParams case tp: TypeProxy => tp.underlying.typeParams case _ => Nil } /** Encode the type resulting from applying this type to given arguments */ final def appliedTo(args: List[Type])(implicit ctx: Context): Type = { def recur(tp: Type, tparams: List[TypeSymbol], args: List[Type]): Type = args match { case arg :: args1 => val tparam = tparams.head val tp1 = RefinedType(tp, tparam.name, arg.toRHS(tparam)) recur(tp1, tparams.tail, args1) case nil => tp } if (args.isEmpty) this else recur(this, typeParams, args) } final def appliedTo(arg: Type)(implicit ctx: Context): Type = appliedTo(arg :: Nil) final def appliedTo(arg1: Type, arg2: Type)(implicit ctx: Context): Type = appliedTo(arg1 :: arg2 :: Nil) final def objToAny(implicit ctx: Context) = if (typeSymbol == defn.ObjectClass && !ctx.phase.erasedTypes) defn.AnyType else this /** If this type equals `tycon applyToArgs args`, for some * non-refinement type `tycon` and (possibly partial) type arguments * `args`, return a pair consisting of `tycon` and `args`. * Otherwise return the dealiased type itself and `Nil`. */ final def splitArgs(implicit ctx: Context): (Type, List[Type]) = { def recur(tp: Type, nparams: Int): (Type, List[Type]) = tp.dealias match { case tp @ RefinedType(parent, name) => def fail = (NoType, Nil) if (nparams >= 0) { val result @ (tycon, args) = recur(parent, nparams - 1) if (tycon != NoType) { val tparam = tycon.typeParams.apply(nparams) if (tparam.name == name) { (tycon, args :+ tp.refinedInfo.argType(tparam)) } else fail } else fail } else fail case tp => (tp, Nil) } val result @ (tycon, args) = recur(this, typeParams.length) if (tycon != NoType) result else (this, Nil) } final def splitArgsCompletely(implicit ctx: Context): (Type, List[Type]) = { val result @ (tycon, args) = splitArgs if (args.length == tycon.typeParams.length) result else (NoType, Nil) } /** If this is an encoding of an applied type, return its arguments, * otherwise return Nil */ def typeArgs(implicit ctx: Context): List[Type] = splitArgs._2 /** If this type is of the normalized form Array[...[Array[T]...] * return the number of Array wrappers and T. * Otherwise return 0 and the type itself */ final def splitArray(implicit ctx: Context): (Int, Type) = { def recur(n: Int, tp: Type): (Int, Type) = tp.splitArgs match { case (arrayType, arg :: Nil) if arrayType == defn.ArrayType => recur(n + 1, arg) case (tp, Nil) => (n, tp) } recur(0, this) } /** Turn this type into a TypeBounds RHS */ final def toRHS(tparam: Symbol)(implicit ctx: Context): TypeBounds = { val v = tparam.variance if (v > 0) TypeBounds.upper(this) else if (v < 0) TypeBounds.lower(this) else TypeAlias(this) } /** If this is the image of a type argument, recover the type argument, * otherwise NoType. */ final def argType(tparam: Symbol)(implicit ctx: Context): Type = this match { case TypeBounds(lo, hi) => val v = tparam.variance if (v > 0 && lo.typeSymbol == defn.NothingClass) hi else if (v < 0 && hi.typeSymbol == defn.AnyClass) lo else if (v == 0 && (lo eq hi)) lo else NoType case _ => NoType } final def isWrong: Boolean = !exists // !!! needed? final def exists: Boolean = true final def &(that: Type)(implicit ctx: Context): Type = ctx.glb(this, that) def |(that: Type)(implicit ctx: Context): Type = ctx.lub(this, that) def show(implicit ctx: Context): String = ctx.show(this, Printers.GlobalPrec) // ----- hashing ------------------------------------------------------ /** customized hash code of this type. * NotCached for uncached types. Cached types * compute hash and use it as the type's hashCode. */ def hash: Int protected def hashSeed = getClass.hashCode private def finishHash(hashCode: Int, arity: Int): Int = { val h = hashing.finalizeHash(hashCode, arity) if (h == NotCached) NotCachedAlt else h } private def finishHash(seed: Int, arity: Int, tp: Type): Int = { val elemHash = tp.hash if (elemHash == NotCached) return NotCached finishHash(hashing.mix(seed, elemHash), arity + 1) } private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = { val elemHash = tp1.hash if (elemHash == NotCached) return NotCached finishHash(hashing.mix(seed, elemHash), arity + 1, tp2) } private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = { var h = seed var xs = tps var len = arity while (xs.nonEmpty) { val elemHash = xs.head.hash if (elemHash == NotCached) return NotCached h = hashing.mix(h, elemHash) xs = xs.tail len += 1 } finishHash(h, len) } private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = { val elemHash = tp.hash if (elemHash == NotCached) return NotCached finishHash(hashing.mix(seed, elemHash), arity + 1, tps) } protected def doHash(x: Any): Int = finishHash(hashing.mix(hashSeed, x.hashCode), 1) protected def doHash(tp: Type): Int = finishHash(hashSeed, 0, tp) protected def doHash(x1: Any, tp2: Type): Int = finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2) protected def doHash(tp1: Type, tp2: Type): Int = finishHash(hashSeed, 0, tp1, tp2) protected def doHash(x1: Any, tp2: Type, tp3: Type): Int = finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3) protected def doHash(tp1: Type, tps2: List[Type]): Int = finishHash(hashSeed, 0, tp1, tps2) protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int = finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3) } // end Type /** 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.uniques.findEntryOrUpdate(tp).asInstanceOf[T] } /** 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 } // 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 } /** 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 } /** Instances of this class are uncached and are proxies. */ abstract class UncachedProxyType extends TypeProxy { final def hash = NotCached } /** A marker trait for types that apply only to type symbols */ trait TypeType extends Type /** A marker trait for types that apply only to term symbols */ trait TermType extends Type /** A marker trait for types that can be types of values */ trait ValueType extends TermType /** 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 with ValueType /** A marker trait for types that bind other types that refer to them. * Instances are: PolyType, MethodType, RefinedType. */ trait BindingType extends Type // --- NamedTypes ------------------------------------------------------------------ /** A NamedType of the form Prefix # name */ abstract class NamedType extends CachedProxyType with ValueType { val prefix: Type val name: Name private[this] var lastDenotation: Denotation = null /** 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) { val checkPrefix = d.info.isRealTypeBounds || d.symbol.isClass if (checkPrefix && !prefix.isLegalPrefix) throw new MalformedType(prefix, d.symbol) d } else {// name has changed; try load in earlier phase and make current denot(ctx.fresh.withPhase(ctx.phaseId - 1)).current } } } lastDenotation } protected def loadDenot(implicit ctx: Context) = prefix.member(name) def isType = name.isTypeName def isTerm = name.isTermName def symbol(implicit ctx: Context): Symbol = denot.symbol def info(implicit ctx: Context): Type = denot.info override def underlying(implicit ctx: Context): Type = try { ctx.underlyingRecursions += 1 if (ctx.underlyingRecursions < LogUnderlyingThreshold) info else if (ctx.pendingUnderlying(this)) throw new CyclicReference(symbol) else try { ctx.pendingUnderlying += this info } finally { ctx.pendingUnderlying -= this } } finally { ctx.underlyingRecursions -= 1 } def derivedNamedType(prefix: Type)(implicit ctx: Context): Type = if (prefix eq this.prefix) this else newLikeThis(prefix) /** Create a NamedType of the same kind as this type, if possible, * but with a new prefix. For HasFixedSym instances another such * instance is only created if the symbol's owner is a base class of * the new prefix. If that is not the case, we fall back to a * NamedType or in the case of a TermRef, NamedType with signature. */ protected def newLikeThis(prefix: Type)(implicit ctx: Context): Type = NamedType(prefix, name) override def computeHash = doHash(name, prefix) } 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 trait HasFixedSym extends NamedType { protected val fixedSym: Symbol override def symbol(implicit ctx: Context): Symbol = fixedSym override def loadDenot(implicit ctx: Context) = { val denot = fixedSym.denot val owner = denot.owner if (owner.isTerm) denot else denot.asSeenFrom(prefix) } } final class TermRefBySym(prefix: Type, val fixedSym: TermSymbol)(initctx: Context) extends TermRef(prefix, fixedSym.name(initctx).asTermName) with HasFixedSym { override def newLikeThis(prefix: Type)(implicit ctx: Context): TermRef = if (prefix.baseType(fixedSym.owner).exists) TermRef(prefix, fixedSym) else TermRef(prefix, name, fixedSym.signature) } final class TermRefWithSignature(prefix: Type, name: TermName, sig: Signature) extends TermRef(prefix, name) { override def signature(implicit ctx: Context) = sig override def computeHash = doHash((name, sig), prefix) override def loadDenot(implicit ctx: Context): Denotation = super.loadDenot.atSignature(sig) override def newLikeThis(prefix: Type)(implicit ctx: Context): TermRefWithSignature = TermRef(prefix, name, sig) } final class TypeRefBySym(prefix: Type, val fixedSym: TypeSymbol)(initctx: Context) extends TypeRef(prefix, fixedSym.name(initctx).asTypeName) with HasFixedSym { override def newLikeThis(prefix: Type)(implicit ctx: Context): TypeRef = if (prefix.baseType(fixedSym.owner).exists) TypeRef(prefix, fixedSym) else 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) = if (name.isTermName) TermRef(prefix, name.asTermName) else TypeRef(prefix, name.asTypeName) def apply(prefix: Type, sym: Symbol)(implicit ctx: Context) = if (sym.isTerm) TermRef(prefix, sym.asTerm) else TypeRef(prefix, sym.asType) } object TermRef { def apply(prefix: Type, name: TermName)(implicit ctx: Context) = unique(new CachedTermRef(prefix, name)) def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context) = unique(new TermRefBySym(prefix, sym)(ctx)) def apply(prefix: Type, name: TermName, sig: Signature)(implicit ctx: Context) = unique(new TermRefWithSignature(prefix, name, sig)) } object TypeRef { def apply(prefix: Type, name: TypeName)(implicit ctx: Context) = unique(new CachedTypeRef(prefix, name)) def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context) = unique(new TypeRefBySym(prefix, sym)(ctx)) } // --- Other SingletonTypes: ThisType/SuperType/ConstantType --------------------------- abstract case class ThisType(cls: ClassSymbol) extends CachedProxyType with SingletonType { override def underlying(implicit ctx: Context) = cls.classInfo.selfType override def computeHash = doHash(cls) } final class CachedThisType(cls: ClassSymbol) extends ThisType(cls) object ThisType { def apply(cls: ClassSymbol)(implicit ctx: Context) = { assert(!(cls is PackageClass) || cls.isRoot) unique(new CachedThisType(cls)) } } 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 CachedSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe) object SuperType { def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context) = unique(new CachedSuperType(thistpe, supertpe)) } 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 CachedConstantType(value: Constant) extends ConstantType(value) object ConstantType { def apply(value: Constant)(implicit ctx: Context) = unique(new CachedConstantType(value)) } // --- Refined Type --------------------------------------------------------- abstract case class RefinedType(parent: Type, refinedName: Name)(infof: RefinedType => Type) extends CachedProxyType with BindingType with ValueType { val refinedInfo: Type = infof(this) override def underlying(implicit ctx: Context) = parent def derivedRefinedType(parent: Type, refinedName: Name, refinedInfo: Type)(implicit ctx: Context): RefinedType = if ((parent eq this.parent) && (refinedName eq this.refinedName) && (refinedInfo eq this.refinedInfo)) this else RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt))) override def computeHash = doHash(refinedName, refinedInfo, parent) } class CachedRefinedType(parent: Type, refinedName: Name, infof: RefinedType => Type) extends RefinedType(parent, refinedName)(infof) object RefinedType { def make(parent: Type, names: List[Name], infofs: List[RefinedType => Type])(implicit ctx: Context): Type = if (names.isEmpty) parent else make(RefinedType(parent, names.head, infofs.head), names.tail, infofs.tail) def apply(parent: Type, name: Name, infof: RefinedType => Type)(implicit ctx: Context): RefinedType = unique(new CachedRefinedType(parent, name, infof)) def apply(parent: Type, name: Name, info: Type)(implicit ctx: Context): RefinedType = apply(parent, name, scala.Function const info: (RefinedType => Type)) } // --- AndType/OrType --------------------------------------------------------------- abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType with ValueType { type This <: AndType def derivedAndType(t1: Type, t2: Type)(implicit ctx: Context) = if ((t1 eq tp1) && (t2 eq tp2)) this else AndType(t1, t2) override def computeHash = doHash(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 CachedAndType(tp1, tp2)) } abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with ValueType { def derivedOrType(t1: Type, t2: Type)(implicit ctx: Context) = if ((t1 eq tp1) && (t2 eq tp2)) this else OrType(t1, t2) override def computeHash = doHash(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 CachedOrType(tp1, tp2)) } // ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam --------------- // 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 with TermType { override lazy val resultType = resultTypeExp(this) def isJava = false def isImplicit = false lazy val isDependent = resultType exists { case MethodParam(mt, _) => mt eq this case _ => false } private[this] var _signature: Signature = _ private[this] var signatureRunId: Int = NoRunId override def signature(implicit ctx: Context): Signature = { if (ctx.runId != signatureRunId) { _signature = computeSignature signatureRunId = ctx.runId } _signature } private def computeSignature(implicit ctx: Context): Signature = { val followSig = resultType match { case rtp: MethodType => rtp.signature case _ => Nil } (paramTypes map Erasure.paramSignature) ++ 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 else { val restpeExpr = (x: MethodType) => restpe.subst(this, x) if (isJava) JavaMethodType(paramNames, paramTypes)(restpeExpr) else if (isImplicit) ImplicitMethodType(paramNames, paramTypes)(restpeExpr) else MethodType(paramNames, paramTypes)(restpeExpr) } def instantiate(argTypes: List[Type])(implicit ctx: Context): Type = if (isDependent) new InstMethodMap(this, argTypes) apply resultType else resultType override def computeHash = doHash(paramNames, resultType, paramTypes) } 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) { override def isImplicit = true } abstract class GenericMethodType { def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context): MethodType def apply(paramNames: List[TermName], paramTypes: List[Type], resultType: Type)(implicit ctx: Context): MethodType = apply(paramNames, paramTypes)(_ => resultType) def fromSymbols(params: List[Symbol], resultType: Type)(implicit ctx: Context) = { def transResult(mt: MethodType) = resultType.subst(params, (0 until params.length).toList map (MethodParam(mt, _))) apply(params map (_.name.asTermName), params map (_.info))(transResult _) } } object MethodType extends GenericMethodType { def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = unique(new CachedMethodType(paramNames, paramTypes)(resultTypeExp)) } object JavaMethodType extends GenericMethodType { def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = unique(new JavaMethodType(paramNames, paramTypes)(resultTypeExp)) } object ImplicitMethodType extends GenericMethodType { def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) = unique(new ImplicitMethodType(paramNames, paramTypes)(resultTypeExp)) } abstract case class ExprType(override val resultType: Type) extends CachedProxyType with TermType { override def underlying(implicit ctx: Context): Type = resultType override def signature(implicit ctx: Context): Signature = Nil def derivedExprType(rt: Type)(implicit ctx: Context) = if (rt eq resultType) this else ExprType(rt) override def computeHash = doHash(resultType) } final class CachedExprType(resultType: Type) extends ExprType(resultType) object ExprType { def apply(resultType: Type)(implicit ctx: Context) = unique(new CachedExprType(resultType)) } case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends UncachedGroundType with BindingType with TermType { lazy val paramBounds = paramBoundsExp(this) override lazy val resultType = resultTypeExp(this) override def signature(implicit ctx: Context) = resultType.signature def instantiate(argTypes: List[Type])(implicit ctx: Context): Type = new InstPolyMap(this, argTypes) apply resultType def instantiateBounds(argTypes: List[Type])(implicit ctx: Context): List[TypeBounds] = paramBounds mapConserve (new InstPolyMap(this, argTypes).apply) 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 PolyType(paramNames)( 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 case _ => false } } object PolyType { def fromSymbols(tparams: List[Symbol], resultType: Type)(implicit ctx: Context) = { def transform(pt: PolyType, tp: Type) = tp.subst(tparams, (0 until tparams.length).toList map (PolyParam(pt, _))) apply(tparams map (_.name.asTypeName))( pt => tparams map (tparam => transform(pt, tparam.info).bounds), pt => transform(pt, resultType)) } } abstract class BoundType extends UncachedProxyType with ValueType { type BT <: BindingType def binder: BT def copy(bt: BT): Type } 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(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 } 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)) } // ------ ClassInfo, Type Bounds ------------------------------------------------------------ /** The info of a class during a period. * @param pre The prefix on which all class attributes need to be rebased. * @param cls The class symbol. * @param classParents The parent types of this class. * These are all normalized to be TypeRefs by moving any refinements * to be member definitions of the class itself. * @param decls The symbols defined directly in this class. * @param optSelfType The type of `this` in this class, if explicitly given, NoType otherwise. */ abstract case class ClassInfo( prefix: Type, cls: ClassSymbol, classParents: List[TypeRef], decls: Scope, optSelfType: Type) extends CachedGroundType with TypeType { def selfType(implicit ctx: Context): Type = if (optSelfType.exists) optSelfType else cls.typeConstructor def typeConstructor(implicit ctx: Context): Type = NamedType(prefix, cls.name) // cached because baseType needs parents private var parentsCache: List[TypeRef] = null def rebase(tp: Type)(implicit ctx: Context): Type = tp.substThis(cls, prefix) override def parents(implicit ctx: Context): List[TypeRef] = { if (parentsCache == null) parentsCache = classParents.mapConserve(rebase(_).asInstanceOf[TypeRef]) parentsCache } def derivedClassInfo(prefix: Type, classParents: List[TypeRef], optSelfType: Type)(implicit ctx: Context) = if ((prefix eq this.prefix) && (classParents eq this.classParents) && (optSelfType eq this.optSelfType)) this else ClassInfo(prefix, cls, classParents, decls, optSelfType) override def computeHash = doHash(cls, prefix) } final class CachedClassInfo(prefix: Type, cls: ClassSymbol, classParents: List[TypeRef], decls: Scope, optSelfType: Type) extends ClassInfo(prefix, cls, classParents, decls, optSelfType) object ClassInfo { def apply(prefix: Type, cls: ClassSymbol, classParents: List[TypeRef], decls: Scope, optSelfType: Type = NoType)(implicit ctx: Context) = unique(new CachedClassInfo(prefix, cls, classParents, decls, optSelfType)) } abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType with TypeType { 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) def contains(tp: Type)(implicit ctx: Context) = lo <:< tp && tp <:< hi def &(that: TypeBounds)(implicit ctx: Context): TypeBounds = TypeBounds(this.lo | that.lo, this.hi & that.hi) 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) = subst(from, to).asInstanceOf[TypeBounds] def map(f: Type => Type)(implicit ctx: Context): TypeBounds = TypeBounds(f(lo), f(hi)) override def computeHash = doHash(lo, hi) } final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) object TypeBounds { def empty(implicit ctx: Context) = apply(defn.NothingType, defn.AnyType) def upper(hi: Type)(implicit ctx: Context) = apply(defn.NothingType, hi) def lower(lo: Type)(implicit ctx: Context) = apply(lo, defn.AnyType) def apply(lo: Type, hi: Type)(implicit ctx: Context) = unique(new CachedTypeBounds(lo, hi)) } object TypeAlias { def apply(tp: Type)(implicit ctx: Context) = TypeBounds(tp, tp) def unapply(tp: Type): Option[Type] = tp match { case TypeBounds(lo, hi) if lo eq hi => Some(lo) case _ => None } } // ----- Annotated and Import types ----------------------------------------------- case class AnnotatedType(annot: Annotation, tpe: Type) extends UncachedProxyType with ValueType { override def underlying(implicit ctx: Context): Type = tpe def derivedAnnotatedType(annot: Annotation, tpe: Type) = if ((annot eq this.annot) && (tpe eq this.tpe)) this else AnnotatedType(annot, tpe) } object AnnotatedType { def make(annots: List[Annotation], underlying: Type) = if (annots.isEmpty) underlying else (underlying /: annots)((tp, ann) => AnnotatedType(ann, tp)) } case class ImportType(expr: SharedTree) extends UncachedGroundType // Special type objects ------------------------------------------------------------ case object NoType extends UncachedGroundType { def symbol = NoSymbol def info = NoType } /** Cached for efficiency because hashing is faster */ case object NoPrefix extends CachedGroundType { override def computeHash = hashSeed } abstract class ErrorType extends UncachedGroundType with ValueType object ErrorType extends ErrorType case object WildcardType extends UncachedGroundType // ----- TypeMaps -------------------------------------------------------------------- abstract class TypeMap(implicit ctx: Context) extends (Type => Type) { thisMap => def apply(tp: Type): Type def applyToBounds(tp: TypeBounds): TypeBounds = apply(tp: Type).asInstanceOf[TypeBounds] /** Map this function over given type */ def mapOver(tp: Type): Type = tp match { case tp: NamedType => tp.derivedNamedType(this(tp.prefix)) case _: ThisType | _: BoundType => tp case tp: RefinedType => tp.derivedRefinedType(this(tp.parent), tp.refinedName, this(tp.refinedInfo)) case tp @ PolyType(pnames) => tp.derivedPolyType( pnames, tp.paramBounds mapConserve applyToBounds, this(tp.resultType)) case tp @ MethodType(pnames, ptypes) => tp.derivedMethodType(pnames, ptypes mapConserve this, this(tp.resultType)) case tp @ ExprType(restpe) => tp.derivedExprType(this(restpe)) case tp @ SuperType(thistp, supertp) => tp.derivedSuperType(this(thistp), this(supertp)) case tp @ TypeBounds(lo, hi) => if (lo eq hi) { val lo1 = this(lo) tp.derivedTypeBounds(lo1, lo1) } else { tp.derivedTypeBounds(this(lo), this(hi)) } case tp @ AnnotatedType(annot, underlying) => tp.derivedAnnotatedType(mapOver(annot), this(underlying)) case _ => tp } def mapOver(syms: List[Symbol]): List[Symbol] = ctx.mapSymbols(syms, this) def mapOver(scope: Scope): Scope = { val elems = scope.toList val elems1 = mapOver(elems) if (elems1 eq elems) scope else newScopeWith(elems1: _*) } def mapOver(annot: Annotation): Annotation = annot.derivedAnnotation(mapOver(annot.tree)) def mapOver(tree: Tree): Tree = new TreeMapper(this).apply(tree) def andThen(f: Type => Type): TypeMap = new TypeMap { def apply(tp: Type) = f(thisMap.apply(tp)) } } object IdentityTypeMap extends TypeMap()(NoContext) { def apply(tp: Type) = tp } class InstMethodMap(mt: MethodType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap { def apply(tp: Type) = tp match { case MethodParam(`mt`, n) => argtypes(n) case _ => mapOver(tp) } } class InstPolyMap(pt: PolyType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap { def apply(tp: Type) = tp match { case PolyParam(`pt`, n) => argtypes(n) case _ => mapOver(tp) } def apply(bounds: TypeBounds): TypeBounds = bounds.derivedTypeBounds(apply(bounds.lo), apply(bounds.hi)) } // ----- TypeAccumulators ---------------------------------------------------- abstract class TypeAccumulator[T] extends ((T, Type) => T) { def apply(x: T, tp: Type): T protected def apply(x: T, annot: Annotation): T = x // don't go into annotations def foldOver(x: T, tp: Type): T = tp match { case tp: NamedType => this(x, tp.prefix) case _: ThisType | _: BoundType => x case tp: RefinedType => this(this(x, tp.parent), tp.refinedInfo) case tp @ PolyType(pnames) => this((x /: tp.paramBounds)(this), tp.resultType) case tp @ MethodType(pnames, ptypes) => this((x /: ptypes)(this), tp.resultType) case ExprType(restpe) => this(x, restpe) case SuperType(thistp, supertp) => this(this(x, thistp), supertp) case TypeBounds(lo, hi) => this(this(x, lo), hi) case AnnotatedType(annot, underlying) => this(this(x, annot), underlying) case _ => x } } class ExistsAccumulator(p: Type => Boolean) extends TypeAccumulator[Boolean] { def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp) } // ----- 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 * following invariant: If `keep` is a name filter, and `pre` has * class `C` as a base class, then * * keep(pre, name) => keep(C.this, name) */ abstract class NameFilter { def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean } /** A filter for names of abstract types of a given type */ object abstractTypeNameFilter extends NameFilter { def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean = name.isTypeName && (pre member name).info.isRealTypeBounds } /** A filter for names of deferred term definitions of a given type */ object abstractTermNameFilter extends NameFilter { def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean = name.isTermName && (pre member name).hasAltWith(_ is Deferred) } // ----- 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") // ----- Misc utilities --------------------------------------------------------- /** like map2, but returns list `xs` itself - instead of a copy - if function * `f` maps all elements to themselves. */ def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] = if (xs.isEmpty) xs else { val x1 = f(xs.head, ys.head) val xs1 = map2Conserve(xs.tail, ys.tail)(f) if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs else x1 :: xs1 } /** True if two lists have the same length. Since calling length on linear sequences * is O(n), it is an inadvisable way to test length equality. */ final def sameLength[T](xs: List[T], ys: List[T]): Boolean = xs match { case _ :: xs1 => ys match { case _ :: ys1 => sameLength(xs1, ys1) case _ => false } case _ => ys.isEmpty } }